Метод Гомори

Задача целочисленного линейного программирования

Определение 9.1. Дискретное программирование – раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные налагается условие дискретности, а область допустимых решений конечна.

Если управляющие переменные в ЗЛП определяют количество единиц неделимой продукции, то оптимальное решение должно быть получено в целых числах. Такие задачи называются ЗЦЛП. Целочисленное программирование является частным случаем дискретного.

К ЗЦЛП относится большое число экономических задач. Например, распределение производственных заказов между предприятиями, оптимальный раскрой материалов, определение загрузки оборудования, распределение транспортных средств по рейсам, задачи производства и реализации неделимой продукции.

ЗЦЛП может быть сформулировано следующим образом: найти максимум или минимум функции при условиях , .

В некоторых случаях последнее условие распространяется только на часть переменных. Такие задачи называют частично целочисленными.

Для решения ЗЦЛП разработаны специальные методы: метод сечений (метод Гомори) и метод ветвей и границ.

Алгоритм метода:

1) Отбрасывается условие целочисленности и полученная ЗЛП решается симплекс-методом.

2) Если оптимальное решение ЗЛП удовлетворяет ограничению целочисленности, то оно и является решением исходной задачи.

3) Если оптимальное решение ЗЛП не удовлетворяет ограничению целочисленности, то к основным ограничениям добавляется новое линейное ограничение, обладающее следующими свойствами:

а) оптимальный нецелочисленный план задачи ему не удовлетворяет;

б) любой целочисленный план задачи ему удовлетворяет.

4) Решается расширенная задача.

5) Процесс повторяется до получения целочисленного решения.

Определение 9.2. Дополнительное ограничение , где фигурные скобки означают дробную часть соответствующего числа, называется сечением Гомори, а метод Гомори – методом сечения.

Задача. Контейнер объемом помещен на контейнеровоз грузоподъемностью 12т. Контейнер требуется заполнить грузом двух наименований. Масса единицы груза, объем единицы груза, стоимости приведены в таблице:

Вид груза	т		ден.ед.

Требуется загрузить контейнеровоз таким образом, чтобы стоимость перевозимого груза была максимальной.

Решим задачу методом Гомори.

Введем обозначения: х ₁ – количество груза первого вида, х ₂ – количество груза второго вида. Тогда экономико-математическая модель задачи примет вид:

.

Преобразуем математическую модель ЗЛП без учета целочисленности переменных к допустимому предпочтительному виду канонической формы:

.

По алгоритму основного симплекс-метода заполним симплексную таблицу решения ЗЛП:

*
	-10	-12*
	*	5/2			-1/2	19/2
	1/2			1/2	5/2
	-4*				-30
				2/5	-1/5	19/5
			-1/5	3/5	3/5
			8/5	26/5	-226/5

Оптимальное решение ЗЛП не удовлетворяет ограничению целочисленности, следовательно, к основным ограничениям необходимо добавить новое линейное ограничение.

Замечание 9.1. Если имеется несколько дробных , то для той у которой дробная часть больше всего составляется ограничение.

Составим сечение Гомори для первого ограничения оптимальной симплекс-таблицы решения ЗЛП (так как ):

,

иначе

.

Преобразуем полученное ограничение к канонической форме с предпочтительной переменной:

.

Продолжим решение задачи двойственным симплекс-методом, включив новое ограничение в оптимальную симплекс-таблицу решения ЗЛП:

				2/5	-1/5		19/5
			-1/5	3/5		3/5
			-2/5	-4/5		-4/5
			8/5*	26/5		-226/5
					-5/2
						-42

Оптимальное решение расширенной ЗЛП удовлетворяет ограничению целочисленности.

Ответ: , .

Таким образом, контейнер надо загрузить 3 ед. груза первого вида и 1 ед. второго вида, при этом стоимость перевозимого груза максимальна и равна 42 ден. ед.

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

Дата добавления: 2014-12-07