Зависимости между переменными

Искомые переменные

Непрерывные Дискретные

Непрерывными называются такие величины, которые в заданных граничных условиях могут принимать любые значения.

Дискретными называются такие переменные, которые могут принимать только заданные значения.

Линейные Нелинейные

Линейными называются такие зависимости, в которые переменные входят в первой степени, и с ними выполняются только действия сложения или вычитания.

Нелинейными называются такие зависимости, в которые переменные входят не в первой степени и с ними выполняются другие действия.

Рис. 1.1. Основные классы задач оптимизации

Задача линейного программирования

Задача линейного программирования решается аналитическими и графическими методами.

Аналитические методы, которые представляют собой последовательность вычислений по некоторым правилам, являются основой для решения задачи на компьютере.

Графические методы пригодны лишь для решения таких задач, в которых число переменных .

Аналитический метод решения задач линейного программирования:

1) найти вершины МДР, как точки пересечения ограничений;

2) определить последовательно значения целевой функции в вершинах;

3) вершина, в которой целевая функция приобретает оптимальное (максимальное или минимальное) значение, является оптимальной вершиной;

4) координаты этой вершины и являются искомыми оптимальными значениями переменных.

Эти правила, сформулированные на основании графического решения задачи в двухмерном и трехмерном пространстве, справедливы и для мерного. В этом случае МДР представляет собой многогранник. Координаты каждой его вершины - это допустимые решения. Координаты той вершины, в которой целевая функция имеет максимальное (или минимальное) значение, являются оптимальным решением задачи.

Для аналитического решения задач линейного программирования разработан специальный алгоритм направленного перебора вершин. Этот алгоритм обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается.

В геометрии есть такое понятие "симплекс". Симплексом тела в k-мерном пространстве называют совокупность k+1 его вершин. С учетом этого понятия аналитический метод решения задачи линейного программирования называют симплекс-методом. Вычисления, обеспечивающие определение значения целевой функции и переменных в одной вершине, называются итерацией.

Решение задачи с помощью симплекс-метода подробно изложены в работе [44].

1.2.2. Задача дискретного программирования

Рассмотрим общую задачу дискретного программирования:

где D - некоторое множество.

Если множество D является конечным или счетным, то условие - это условие дискретности, и данная задача является задачей дискретного программирования.

Если вводится ограничение - целые числа (), то приходят к задачам целочисленного программирования (ЦП), которое является частным случаем дискретного программирования.

В задачах дискретного программирования область допустимых решений является невыпуклой и несвязной. Поэтому отыскание решения таких задач сопряжено со значительными трудностями. В частности, невозможно применение стандартных приемов, состоящих в замене дискретной задачи ее непрерывным аналогом, в дальнейшем округлении найденного решения до ближайшего целочисленного.

Проверка показывает, что никакое округление компонент этого плана не дает допустимого решения, удовлетворяющего ограничениям этой задачи. Таким образом, для решения задач дискретного программирования необходимы специальные методы.

Методы решения задач дискретного программирования по принципу подхода к проблеме можно разделить на две группы [44]: 1) методы отсечения или отсекающих плоскостей; 2) метод ветвей и границ.

Математические модели задач дискретного программирования по структуре модели можно разделить на два класса [44]: 1) целочисленные задачи; 2) экстремальные комбинаторные задачи.

Математические модели задач с неделимостями (целочисленные задачи) основаны на требовании целочисленности переменных {}, вытекающем из физических условий практических задач. К таким задачам относятся: задача об определении оптимальной структуры производственной программы, где - объемы выпуска продукции; задача о ранце, где необходимо определить, сколько предметов () каждого типа должен турист положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной.

В том случае, когда ограничения и целевая функция представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования.

Математическая формулировка такой задачи имеет вид:

Для решения задач подобного типа применяются методы отсечения (в частности метод Гомори) и модифицированный метод ветвей и границ для задач целочисленного программирования. Подробно об этих методах можно узнать в литературе [43], [44].

В экстремальных комбинаторных задачах необходимо найти экстремум некоторой целевой функции, заданной на конечном множестве, элементами которого служат перестановки из п символов (объектов).

Наиболее распространенными задачами этого класса являются:задача о коммивояжере,в которой имеется n городов, расстояния между которыми заданы матрицей . Выезжая из некоторого города, коммивояжер должен побывать во всех остальных городах по кратчайшему замкнутому маршруту, проходящему через каждый пункт по одному разу, и вернуться назад; задача о трех станках, где n деталей последовательно обрабатывается на трех станках, причем технологические маршруты всех деталей одинаковы, известны длительности обработки i-й детали на первом, втором и третьем станке соответственно, необходимо определить порядок запуска деталей на обработку, при котором минимизируется суммарное время обработки всех деталей.

Метод ветвей и границ был разработан именно для комбинаторных задач дискретного программирования. Алгоритм решения задачи коммивояжера и задачи о трех станках по данному методу можно узнать в литературе [42], [44].