Метод Гомори

Варианты заданий

Четырем торговым базам поставляется однотипное оборудование с трех заводов. Исходные данные представлены в нижеследующей таблице.

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

Таблица 6.24

Варианты заданий

1)		2)		3)
4)		5)		6)
7)		8)		9)
10)		11)		12)
13)		14)		15)
16)		17)		18)
19)		20)		21)
22)		23)		24)
25)		26)		27)
28)		29)		30)
31)		32)		33)

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

оно должно быть линейным;

должно отсекать найденный оптимальный нецелочисленный план;

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

Дополнительное ограничение, обладающее указанными свойствами, называют правильным отсечением.

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.

Одним из методов отсечения является метод Гомори, который можно представить в виде следующих этапов:

1 этап: решение исходной задачи с ослабленными ограничениями симплекс-методом.

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

2 этап: формирование правильного отсечения.

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

, (6.22)

где S – множество индексов свободных переменных;

(6.23)

, – коэффициенты при свободных переменных и свободное число, соответствующие строке с выбранной компонентой, имеющей наибольшую дробную часть (берутся со своими знаками из последней симплекс-таблицы, содержащей оптимальное решение). Величина в фигурных скобках обозначает дробную часть данной величины[3].

Z – множество целых чисел.

3 этап: корректировка исходной задачи с ослабленными ограничениями с учетом правильного отсечения.

Правильное отсечение (6.22) введением дополнительной неотрицательной переменной преобразовывается в равносильное уравнение и включается в систему ограничений задачи (6.1).

4 этап: решение скорректированной задачи.

Полученная расширенная задача решается симплекс-методом. Если найденный план удовлетворяет условию целочисленности, то задача целочисленного линейного программирования (6.1) решена. В противном случае повторяются этапы 2-4.

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

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

Пример 6.2. Решить следующую задачу целочисленного линейного программирования методом Гомори:

.

Решение:

Дата добавления: 2014-01-04