|
ибо ТЗ всегда имеет решение.
7. Постановка задачи целочисленного программирования (ЗЦЛП). Метод Гомори.
Мат. модель ЗЦЛП имеет вид:
 , где Z – множество целых чисел
Разложенные задачи полностью целочисленные, в которых условие целочисленности
распространяются на все переменные и частично целочисленны, в целочисленности
налагается только на часть переменных.
Если в (2) среди  и 
есть дробные числа, то каждое уравнение или неравенство с дробными
коэффициентами может привести к общему знаменателю и затем обе части умножить
на этот общий знаменатель, поэтому не нарушив общности рассуждений, можно
предполагать, что коэффициенты целочислены.
Решение целочисленных и непрерывных задач оптимизации имеет принципиальные
различия, суть которого заключается в следующем: непрерывные задачи обычно
решаются симплекс-методом с построением симплекс-таблиц.
Известно, что для ЗЛП экстремум достигается в крайней точке выпуклого
множества или в точке, в которой является выпуклой линейной комбинацией
крайних точек. Для ЗЦЛП точкой оптимума может быть любая точка области
допустимых решений, поэтому невозможно заменить дискретную задачу непрерывным
аналогом, и найдя соответствующее решение и округлить его значение до
ближайших целых значений.
Пусть целая часть числа x – [x], огромная – {x}, тогда 
Если даже оптимальный непрерывной задачи, округлённой до целых значений
компонент окажется допустимым, то целевая функция может вести себя так, что её
значение будет на нём значительно хуже, чем на оптимальном плане целочисленной
задачи.
Перечисленные проблемы предопределяли необходимость разработки специальных
методов решения ЗЦЛП, ибо методы последовательного улучшения приводит к
целочисленному решению лишь для немногих задач. Методы ЦЛП можно разделить на
3 основные группы:
1. Метод отсечения.
2. Комбинаторные.
3. Приближённые
Сущность 1 состоит в том, что сначала задача решается без условия
целочисленности. Если полученный план будет целочисленным, то задача решена.
Решение обладает следующими свойствами:
1) Оно должно быть линейным.
2) Должно отсекать найденный оптимальный нецелочисленный
план.
3) Не должно отсекать ни одного целочисленного плана.
Дополнительные ограничения, обладающие указанными свойствами, называются
правильным отсечением. Затем полученные оптимизационные задачи решаются с
учётом нового ограничения. После этого в случае необходимости добавляется
новое ограничение.
Геометрическое добавление каждого линейного ограничения отвечает проведению
плоскости (гиперплоскости), которая отсекает от многоугольника
(многогранника) некоторую его часть вместе с оптимальной точкой с нецелевыми
координатами, но не затрагивая ни одной из целочисленных точек этого
многоугольника.
Метод Гомори.
Основная идея метода отсекающих плоскостей состоит в том, что на каждом шаге
рассматривается задача с ослабленными ограничениями без требования
целочисленности, для которой по специальному алгоритму строится некоторое
дополнительное ограничение, отсекающее только некоторые нецелочисленные
точки. Если полученный в результате оптимальный план содержит только целые
компоненты, то автоматически получается соответст. решению ЗЦЛП. В противном
случае к системе ограничений задачи должно быть добавлено такое ограничение,
для которого:
1) Найденный нецелочисленный оптимальный план не
удовлетворяет вновь добавленному ограничению;
2) Любой допустимый целочисленный план непрерывной
задачи 1-4 удовлетворяет вновь добавленному ограничению.
Приведём обобщённую схему алгоритма Гомори. Структурно он делится на, т. н.,
большие итерации, каждая из которых содержит этапы:
1. Решение текущей задачи 1, 2 отбросит условия неотрицательности 3
симплекс-методом (малая итерация). Пусть решение исходной задачи с ослабленными
ограничениями дало на последнем шаге, соответствующему оптимальному решению,
следующие выражения, основных переменных 
через свободные переменные 
Кратко это записывается в виде:
Как следует из теории симплекс-метода оптимальным решением задачи в этом случае
является вектор 
2. Если все компоненты оптимального плана, полученного на первой итерации в
целом, то он является оптимальным и для ЗЦЛП 1-4. Если задача ЛП 1-3 не
разрешима, то и ЗЦЛП 1-4 также не разрешима. Если среди компонентов
оптимального плана есть не целая, то перейдём к следующему этапу.
3. Среди базисных нецелых компонентов оптимального плана следует выбрать
компоненту с наибольшей дробной частью.
Пусть компонента  не
целое число. Рассмотрим уравнение, в котором 
базисная переменная:
 , где R – множество индексов свободных переменных.
Разобьем все коэффициенты и свободные члены уравнения (5) на 2 слагаемых:
целую и дробную часть.
или
Для любого целочисленного решения задачи левая часть (6) – есть целое число,
следовательно и правая часть равенства также будет целое число, причём правая
часть равенства (6) должна удовлетворяет неравенству:
Это будет сечение Гомори. Т. о., третья итерация состоит в построении для
нецелевой базисной компоненты условия отсечения.
4. Неравенство (7) выделением дополнительной неотрицательной целочисленной
переменной преобразуется в уравнение и присоединяется к ранее решённой задаче
(включить его в симплекс-таблицу с нецелочисленным оптимальным планом).
Формируется новая текущая задача. Переход на начало следующей большой
итерации.
5. Полученная расширенная ЗЛП решается симплекс-методом. Если полученный
оптимальный план будет целочисленным, то ЗЦЛП 1-4 решена. В противном случае
следует вернуться к пункту алгоритма 3. Если задача разрешима в целых числах,
то после конечного числа итерации оптимальный целочисленный план будет
найден.
Замечание:
· Если в процессе решения появится строка с
нецелым свободным членом и целыми остальными коэффициентами, то
соответствующее уравнение не имеет решения в целых числах. В таком случае и
данная задача не имеет целочисленного оптимального плана.
· Если число 
с наибольшей дробной частью окажется несколько то из них выбирается 
первое по коэффициенту.
· Несмотря на точность, методы отсечения имеют
весьма ограниченную применимость, с их помощью нельзя решить задачи большой
размерности.
· При практической реализации метода Гомори на ЭВМ
следует считаться с ошибками округления.
8. Пример решения ЗЦЛП методом Гомори.
 
Находим общее решение системы:
Выразим целевую функцию через свободные переменные x1 и x3:
Полученный стандартный вид ЦФ применим для решения задач симплекс-методом.
Итерация 1. Используя обычный симплекс-алгоритм решаем непрерывный аналог
исходной задачи в котором игнорируются условия целочисленности.
| X1 | X2 | X3 | X4 | X5 | Bi | X2 | 2 | 1 | -3 | 0 | 0 | 10 | X4 | 1 | 0 | 1 | 1 | 0 | 7 | X5 | 3 | 0 | -2 | 0 | 1 | 4 | | f | -3 | 0 | 1 | 0 | 0 | -3 |
| X1 | X2 | X3 | X4 | X5 | Bi | X2 | 0 | 1 | -5/3 | 0 | -2/3 | 22/3 | X4 | 0 | 0 | 5/3 | 1 | -1/3 | 17/3 | X1 | 1 | 0 | -2/3 | 0 | 1/3 | 4/3 | | f | 0 | 0 | 1 | 0 | 1 | 1 |
| X1 | X2 | X3 | X4 | X5 | Bi | X2 | 0 | 1 | 0 | 1 | -1 | 13 | X3 | 1 | 0 | 1 | 3/5 | -1/5 | 17/5 | X1 | 0 | 0 | 0 | 2/5 | 1/5 | 18/5 | | f | 0 | 0 | 0 | 3/5 | 4/5 | 22/5 |
Страницы: 1, 2, 3, 4, 5
| 
