Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
· оно должно быть линейным;
· должно отсекать найденный оптимальный нецелочисленный план;
· не должно отсекать ни одного целочисленного плана.
Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением.
Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.
Геометрически добавление каждого линейного ограничения отвечает проведению прямой (гиперплоскости), которая отсекает от многоугольника (многогранника) решений некоторую его часть вместе с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранника. В результате новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений и соответственно полученное при этом многограннике оптимальное решение будет целочисленным (рис. 6.24).
|
|
Один из алгоритмов решения задачи линейного целочисленного программирования (6.59)…(6.62), предложенный Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.
Рис. 6.18. Графическая иллюстрация целочисленного решения
Пусть задача линейного программирования (6.52)…(6.55) имеет конечный оптимум и на последнем шаге ее решения симплексным методом получены следующие уравнения, выражающие основные переменные через неосновные переменные оптимального решения
(6.56)
так, что оптимальным решением задачи (6.52)…(6.55) является , в котором, например β i − нецелая компонента. В этом случае можно доказать, что неравенство
, (6.57)
сформированное по i -му уравнению системы (6.56), обладает всеми свойствами правильного отсечения.
В неравенстве (6.57) присутствует символ , означающий дробную часть числа. Число а называется конгруэнтным числу в (обозначается ) тогда и только тогда, когда разность а - в − целое число.
Целой частью числа а называется наибольшее целое число , не превосходящее а. Дробная часть числа определяется как разность между этим числом и его целой частью, т.е. . Например, для = 2, ; для = -3 и .
Для решения задачи целочисленного линейного программирования (6.52)…(6.55) методом Гомори используется следующий алгоритм:
1. Симплексным методом решить задачу (6.52)…(6.55) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (6.52)…(6.55). Если первая задача (6.52)…(6.54) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то вторая задача (6.52)…(6.55) также неразрешима.
|
|
2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (6.56) сформировать правильное отсечение (6.57).
3. Неравенство (6.57) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение
(6.58)
и включить его в систему ограничений (6.53).
4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (6.52)…(6.55) решена. В противном случае вернуться к п. 2 алгоритма.
Если задача разрешима в целых числах, то после конечного числа шагов (итераций) оптимальный целочисленный план будет найден.
Если в процессе решения появится уравнение (выражающее основную переменную через неосновные) с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В этом случае и данная задача не имеет целочисленного оптимального решения.
Недостатком метода Гомори является требование целочисленности для всех переменных − как основных (выражающих, например, в задаче об использовании ресурсов единицы продукции), так и дополнительных переменных (выражающих величину неиспользованных ресурсов, которые могут быть и дробными).
Отметим, что переход к каноническому виду в полностью целочисленной задаче линейного программирования, содержащей ограничения − неравенства
, (6.59)
не приводит, вообще говоря, к полностью целочисленной задаче в каноническом виде, так как в преобразованных ограничениях (6.59)
вспомогательные переменные xn+i не подчинены требованию целочисленности.
Однако если все коэффициенты aij, bi в (6.59) − целые числа, то условие целочисленности можно распространить и на xn+i, как это сделано при решении примера 6.10.
Полностью целочисленную задачу в каноническом виде можно получить также, если в (6.59) aij, bi − рациональные числа. Для этого следует умножить (6.59) на общее кратное знаменателей коэффициентов − aij, bi (т.е. перейти к целым коэффициентам в (6.59)) и лишь после этого ввести вспомогательные переменные .
Пример 6.20. Решить задачу полностью целочисленного программирования
(6.52')
при ограничениях
Решение. Приведем задачу к каноническому виду, введя дополнительные неотрицательные переменные . Получим систему ограничений:
Решаем задачу симплексным методом. Для наглядности решение иллюстрируем графически (рис. 6.19).
Рис. 6.19. Графическая иллюстрация решения задачи
На рис. 6.19 0 KLM – область допустимых решений задачи ограниченная прямыми (1), (2), (3) и осями координат; L (2/3;8) – точка оптимального, но нецелочисленного решения задачи ; (4) – прямая, отсекающая это нецелочисленное решение; 0 KNM – область допустимых решений расширенной задачи (6.64') N (2; 7) – точка оптимального целочисленного решения.
I шаг. Основные переменные ; неосновные переменные .
х 1 | х 2 | ||
х 3 | |||
х 4 | |||
х 5 | |||
↑
Первое базисное решение Х 1 = (0;0;60;34;8) – допустимое. Соответствующее значение линейной функции f 1 = 0.
Переводим в основные переменные переменную х 2, которая входит в выражение линейной функции с наибольшим положительным коэффициентом. Находим максимально возможное значение переменной х 2, которое позволяет принять система ограничений, из условия минимума соответствующих отношений:
,
т.е. разрешающим (выделенным) является третье уравнение. При х 2 = 8 в этом уравнении х 5 = 0, и в неосновные переменные переходит х 5.
|
|
II шаг. Основные переменные ; неосновные переменные .
х 1 | х 5 | ||
х 3 | -5 | ||
х 4 | -4 | ||
х 2 | |||
-3 | -24 |
Х 2 = (0;8;20;2;0); f = 24. Переводим в основные переменные х 1, , а в неосновные х 4.
Ш шаг. Основные переменные ; неосновные переменные . После преобразований получим:
х 4 | х 5 | х 4 | х 5 | |||||
х 3 | -3 | -3 | х 3 | -1 | -1 | |||
х 1 | -4 | х 1 | 1/3 | -4/3 | 2/3 | |||
х 2 | х 2 | |||||||
-2 | -1 | -76 | -2/3 | -1/3 | -76/3 |
Базисное решение Х 3 оптимально для задачи , так как в выражении линейной функции отсутствуют неосновные переменные с положительными коэффициентами.
Однако решение Х 3 не удовлетворяет условию целочисленности (6.55'). По первому уравнению с переменной х 1, получившей нецелочисленное значение в оптимальном решении (2/3), составляем дополнительное ограничение (6.57):
Обращаем внимание на то, что согласно (6.56) и (6.57) берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при неосновных переменных х 4 и х 5 − с противоположными знаками.
Так как дробные части
то последнее неравенство запишем в виде
Введя дополнительную целочисленную переменную х 6 ≥ 0, получим равносильное неравенству (6.57') уравнение
Уравнение (6.58) необходимо включить в систему ограничений (6.56') исходной канонической задачи, после чего повторить процесс решения задачи симплексным методом применительно к расширенной задаче. При этом для сокращения числа шагов (итераций) рекомендуется вводить дополнительное уравнение (6.58') в систему, полученную на последнем шаге решения задачи (без условия целочисленности).
IV шаг. Основные переменные ; неосновные переменные .
х 4 | х 5 | ||
х 1 | 1/3 | -4/3 | 2/3 |
х 2 | |||
х 3 | -1 | -1 | |
х 6 | -1/3 | -2/3 | -2/3 |
-2/3 | -1/3 | -76/3 |
Базисное решение − недопустимое. Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение.
|
|
Для получения допустимого базисного решения необходимо перевести в основные переменную, входящую с положительным коэффициентом в уравнение, в котором свободный член отрицательный, т.е. х 4 или х 5 (на этом этапе линейную функцию не рассматриваем). Переводим в основные, например, переменную х 5.
V шаг. Основные переменные ; неосновные переменные . Получим после преобразований:
х 4 | х 6 | х 4 | х 6 | |||||
х 1 | -6/9 | 4/3 | -12/9 | х 1 | -2 | |||
х 2 | 1/3 | -1 | -14/3 | х 2 | -1/2 | 3/2 | ||
х 3 | 1/3 | 38/3 | х 3 | -1/2 | -3/2 | |||
х 5 | -1/3 | -2/3 | х 5 | 1/2 | -3/2 | |||
3/9 | 1/3 | 150/9 | -1/2 | -1/2 | -25 |
Х 5 = (2;7;19;0;1;0); f 5 = 25.
Так как в выражении линейной функции нет основных переменных с положительными коэффициентами, то Х 5 − оптимальное решение.
Итак, f max = 25 при оптимальном целочисленном решении Шестая компонента содержательного смысла не имеет.
Для геометрической интерпретации на плоскости 0 х 1 х 2 (см. рис. 6.19) отсечения (6.57') необходимо входящие в него переменные х 4 и х 5 выразить через переменные х 1 и х 2. Получим (см. 2-е и 3-е уравнения системы ограничений (6.56'):
(см. отсечение прямой (4) на рис. 6.19).