Целочисленное программирование

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

1.2. Целочисленные и частично целочисленные задачи линейного программирования

Определение 2.1. Экстремальная задача линейного программирования, в которой на решение налагается целочисленность компонент, является задачей целочисленного программирования и называется целочисленной задачей.

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

Общий алгоритм метода Гомори

Определение 2.3. Правильное отсечение - отсечение, которое удовлетворяют следующим требованиям:

1. линейно;

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

Алгоритм метода Гомори в общем виде

Этап 1

Решается - задача, соответствующая исходной задаче.

Если -задача не имеет решения, т.е. G пуста или неограниченна в положительном направлении возрастания (убывания) F, то устанавливается неразрешимость целочисленной задачи.

Этап 2

Оптимальное решение Оптимальное решение Если решение целочисленное, то задача решена.

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

Этап 3

Дополнительное ограничение, которое

1. линейно;

2. отсекает часть области, не содержащей допустимых решений целочисленной - задачи;

3. не отсекает ни одного целочисленного оптимального плана, который входит в систему ограничений.

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

В общем виде ЗНЛП состоит в определении макс. или мин. значений функции f(x1,x2,…,xn) (1) при условии, что её переменные удовлетворяют соотношениям:

,

где f и g - некоторые известные функции n переменных, а - заданные числа.

Метод множителей Лагранжа

Включает следующие этапы:

1) составл. фкц. Лагранжа

2) находим частн. произв. подфункции Лагранжа по перем. xj и xi, и приравниваем их нулю

3) решая систему ур-й (10), находим точки, в которых целевая функция задачи может иметь экстремум

4) среди точек, подозрительных на экстремум, находим такие, в к-х достиг. экстремум и вычисляем знач. функции (7) в этих точках.

Метод множит. Лагранжа можно применять и в том случае, когда условные связи (ограничения) представляют собой неравенства. Если треб. найти экстремум z=f(x), при условии g(x)£b, то сначала следует найти т. экстремума функции z из уравнений , , затем среди этих точек отобрать те, координаты которых удовл-ют системе уравнений

точки, найденные в результате реш-я этой системы вместе с точками опред. на 1 этапе и ужовл. условию g(x)<b подлежат дальнейщему исследованию.

Выпуклое программирование

Задачи выпуклого програмирования

Рассмотрим ЗНЛП

f(x1,…,xn)àmax (11)

gi(x1,…,xn) £bi (12)

xj³0 (13)

Для решения сформулированной задачи в такой общей подстановке не сущ-ет универсальных методов. Однако для отд-х классов задач, в к-х сделаны доп. ограничения относительно свойств функций f, gi, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения ЗНЛП (11)-(13) при условии, что f вогнутая (выпуклая) функция и ОДР, определённая ограничениями (12)-(13) – выпуклая.