Какие задачи относятся к зцлп?
ЗЦЛП – задача, в которой переменные должны принимать целочисленные значения, а целевая функция и ограничения линейны.
Если в ЗЦЛП переменные принимают значение 0 и 1, то они называются Булевы переменные.
В общем виде ЗЦЛП может быть сформулировано следующим образом:
К ЗЦЛП относится также транспортная задача, если её параметры целочислены.
Для решения ЗЦЛП применяется ряд методов; если рассматривается большое количество единиц (товара, груза и т.д.), то задачу можно решить симплексным методом и полученное решение округлить до целых.
Если рассматриваются крупные единицы товара, груза, изделия и их число не велико, то данный метод решения не годится.
Сущность метода Гомори.
Первый метод решения PWKG – метод отсечений.
Основная идея метода отсечений состоит в том, что исходная задача первоначально решается без требования целочисленности переменных. Если полученное оптимальное решение целочисленно, то оно является решением исходной задачи. В противном случае по определенному алгоритму строится некоторое дополнительное линейное ограничение удовлетворяющее следующим свойствам:
Оно отсекает полученное не целочисленное оптимальное решение.
Оно не отсекает ни одного целочисленного решения. Дополнительное линейное ограничение, удовлетворяющее таким свойствам, называется правильным отсечением. Далее задача решается с учётом нового ограничения.
Алгоритм метода Гомори.
Алгоритм правильных отсечений впервые был предложен Гомори и состоит в следующем: пусть решение исходной задачи без требования целочисленности симплексным методом на последнем шаге имеет вид
…………………………………….
Оптимальное
решение в этом случае
Пусть
среди компонент вектора Ч* имеется хотя
бы одна нецелочисленная, например
-
нецелочисленная.
Из
соответствующей строки симплексной
таблицы получаем
-
берется дробная часть числа
{a} = a – [a]; [a] – целая часть числа а
[a] – это наибольшее целое число не превосходящее числа а.
Пример:
Неравенство (*) задаёт правильное отсечение.
Если в оптимальном решении Х* несколько нецелочисленный компонент, то правильное отсечение строится по компоненте с наибольшей дробной частью.
Неравенство (*) преобразуется в равенство путём добавления новой неотрицательной переменной и добавляется к ограничениям задачи. Если решение новой задачи целочисленно, то оно является решением исходной задачи. Если решение не целочисленно строится новое правильное отсечение. И т.д.
Геометрическая интерпретация метода Гомори.
Геометрически добавление каждого линейного ограничения отвечает проведению прямой (гиперплоскости), которая отсекает от многоугольника (многогранника) решении некоторую его часть вместе с оптимальной точкой с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранника. В результате новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решении и соответственно полученное при этом многограннике оптимальное решение будет целочисленным.