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. Пример решения ЗЦЛП методом Гомори.

Находим общее решение системы:

Выразим целевую функцию через свободные переменные x₁ и x₃:

Полученный стандартный вид ЦФ применим для решения задач симплекс-методом.

Итерация 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

Как видно из последней симплекс-таблицы полученный план: является оптимальным, при котором ЦФ .

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

Выбираем базисная переменная x₁. Из последней симплексной таблицы выписываем строку с базисной переменной

Тогда с учётом (7) сечение запишется в виде:

или где x₆ – дополнительная неотрицательная переменная.

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

Итерация 2. Исходная симплекс-таблица для поставленной задачи получается путём добавления к симплекс-таблице 3 первой задачи строки соответст. введённому сечению.

	X1	X2	X3	X4	X5	X6	bi
X2	0	1	0	1	-1	0	13
X3	0	0	1	3/5	-1/5	0	17/5
X1	1	0	0	2/5	1/5	0	18/5
X6	0	0	0	-2/5	-1/5	1	-3/5
f	0	0	0	3/5	4/5	0	22/5

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

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

Цель этой итерации: не увеличивать значение ЦФ как в симплекс-методе, а получить опорное решение новой задачи, выводя из базиса переменную x₆, т. к. в базис вместо x₀ введём переменную x₄, получим следующую симплекс-таблицу:

	X1	X2	X3	X4	X5	X6	bi
X2	0	1	0	0	-3/2	5/2	23/2
X3	0	0	1	0	-1/2	3/2	5/2
X1	1	0	0	0	0	1	3
X4	0	0	0	1	-1/2	-5/2	3/2
f	0	0	0	0	1/2	3/2	7/2

Полученный план является целочисленным. Выбираем из чисел 23/2; 5/2; 3/2 число с наибольшей дробной частью. У всех у них дробная часть равняется ½.

Выбираем 1 строку:

Используя формулу (7) строим сечение:

Добавим 2-е сечение к таблице 5, получаем таблицу 6.

	X1	X2	X3	X4	X5	X6	X7	bi
X2	0	1	0	0	-3/2	5/2	0	23/2
X3	0	0	1	0	-1/2	3/2	0	5/2
X1	1	0	0	0	0	1	0	23
X4	0	0	0	1	1/2	-5/2	0	3/2
X7	0	0	0	0	-1/2	-1/2	1	-1/2
F	0	0	0	0	1/2	3/2	0	7/2

План базисное решение новой задачи, но не опорное. Введём в базис переменную x₅ вместо x₇, т. к.

	X1	X2	X3	X4	X5	X6	X7	bi
X2	0	1	0	0	0	4	-13	13
X3	0	0	1	0	0	2	-1	3
X1	1	0	0	0	0	0	0	3
X4	0	0	0	1	0	-3	1	1
X5	0	0	0	0	1	1	-2	1
F	0	0	0	0	0	1	1	3

Получим целочисленное решение 3 задачи, оно будет оптимально и для исходной задачи, т. е. при

9. Сущность метода отсечений - один из методов ЦЛП

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

1. оно должно быть линейным,

2. должно отсекать найденный нецелочисленный план,

3. не должно отсекать ни одного целочисленного плана.

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

Данный метод впервые был предложен Р.Е. Гомори в 1957-1958гг.,который также носит название метода отсекающих плоскостей, предназначен для ЗЛП в канонической форме 1-4. Т.о., основная идея метода состоит в том, что на каждом шаге рассматривается задача с ослабленными ограничениями без требования целочисленности, для которой по специальному алгоритму строится некоторое дополнительное линейное ограничение (отсечение), отсекающее только некоторые нецелочисленные точки. Он существенно использует известную симплексную процедуру. Отправной точкой для решения задачи 1-4 является решение ее непрерывного аналога, т.е. ЗЛП без учета целочисленности. Если получаемый в результате оптимальный план содержит только целые компоненты, то автоматически получается ЗЦЛП. В противном случае в системе ограничений задачи д/б добавлено такое ограничение, для которого:

1)найденный нецелочисленный оптимальный план не удовлетворяет вновь добавляемому ограничению,

2)любой допустимый целочисленный план задачи 1-4 удовлетворяет вновь добавляемому ограничению