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

Алгоритм Гомори

ГП С помощью симплекс-метода находим оптимальную программу. Если получились целочисленные значения для всех Xj , то задача решена. В противном случае среди Xj имеются нецслочисленные значения.

|~2~1 Среди нецелых Xj выбираем произвольный элемент х г и в задаче добавляем еще одно ограничение

что равносильно добавлению в симплекс-таблице еще одной строки, после чего она перестает соответствовать допустимому базисному решению новой задачи линейного программирования, которую она описывает. В ограничении применяются дробные части элементов строки, в которой находится х г. Применяемое обозначение для дробной части исходит из того, что всякое действительное число у можно представить в виде суммы у = [у] + {?у}, где [у] - целая часть и {у} = У ~ [у] ~ дробная часть.

[з] Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I = п + 1.

• а) Если все коэффициенты уц > 0, то задача не имеет решения (т.е. целочисленная задача решена).
• б) В противном случае находим индекс к такой, что

(критерий входа в новый базис). Заметим, что выбор разрешающего элемента у и* не изменяет знак у критериев Aj.

[4] Если в новой таблице имеется хотя бы один х 3 s и повторить указанные процедуры необходимое число раз.

[~5~| Если полученное оптимальное решение целочисленно, то поставленная задача решена. В противном случае надо вернуться к пункту .

Пример 4.6.1. Решить методом Гомори целочисленную задачу

Решение. После добавления вспомогательных переменных имеется следующая задача линейного программирования в стандартной форме:

с матрицами

Таблица 1
	Х 4

к = 1 Т

С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 6*.

Таблица 2				х 2
		„ _ 1 Ж Z ~_3_

к" = 2 Т

Разрешающий элемент - 1/2*.

Х в ^ 0). Следовательно, программа {xi = 11/3, х 2 = 5} даст максимум экономической функции z, равный 1370/3 = 45б|, т.с. z = z max = 456§. "

Так как эта оптимальная программа не является целочисленной, применим алгоритм Гомори для нахождения целочисленной оптимальной программы. В качестве строки, на базе которой образуем дополнительную строку из дробных частей се элементов, выбираем вторую строку (индекс 7’ = 1). Заполним таблицу 3", добавив в таблицу 3 дополнительную строку (4.14) с дробными частями для дополнительной переменной Ж5 и дополнительный столбец. Получаем

к" = 4 Т

После добавления новой строки симплекс-таблица 3" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. /" = 5.

Находим разрешающий столбец, т.с. индекс к" такой, что

(критерий входа в новый базис). Разрешающий элемент - (-2/3*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.

Заполним симплекс-таблицу 4.

Таблица 4				Х 2
	Х 2

Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 3, ж 2 = 6, х± = 1} дает максимум экономической функции г, равный 450, т.с. z = z ma ^ = 450. Эта оптимальная программа является целочисленной. ?

Пример 4.6.2. Решить методом Гомори целочисленную задачу

Решение. Имеется задача линейного программирования с матрицами

Заполним симплекс-таблицу с начальной программой.

Таблица 1

к = 1 Т

С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 1*.

Таблица 2				Х 2

Разрешающий элемент - 5*.

Таблица 3

Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 12/5, 24 = 1/5, 25 = 28/5} дает минимум экономической функции г, равный -11/5 = -2.2, т.с. z =

~min = -2.2.

Так как эта оптимальная программа не является целочисленной, применим алгоритм Гомори для нахождения целочисленной оптимальной программы. В качестве строки, на базе которой образуем дополнительную строку из дробных частей сс элементов, выбираем, например, третью етроку (индекс г = 5) с максимальной дробной частью. Заполним таблицу 3", добавив в таблицу 3 дополнительную строку (4.14) с дробными частями третьей строки для дополнительной переменной xq (эта строка позволяет отсечь от области программ части, содержащие точки с нецслочислснными координатами) и дополнительный столбец. Получаем

Таблица 3"
		г - -И

к" = 3 Т

После добавления новой строки симплекс-таблица 3" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I" = 6.

Находим разрешающий столбец, т.е. индекс к" такой, что

(критерий входа в новый базис). Разрешающий элемент - (-3/5*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.

Заполним симплекс-таблицу 4.

Таблица 4

Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {х = 2, Х 2 = 0, хз = 1, х 4 = 0, ж 5 = 5} даст минимум экономической функции z 9 равный (-2), т.с. z = -min = - 2. Эта оптимальная программа является целочисленной. ?

Задача 4.6.1. Решить методом Гомори целочисленную задачу

Ответ. Программа

дает минимум экономической функции z, равный (-31), т.с. z = 2 m i n = -31. Эта оптимальная программа является целочисленной.

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

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

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

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

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

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

жающие основные переменные *1, *2, новные переменные Хт+1, Хт+2, ..., Хт+1, решения

Хт через неос- х„ оптимального

(8.5)

нецелая компонента. В этом случае можно доказать, что неравен­ство

{Р, } - {а," т+\}хт+1 ■ -~{ат }Хп ^ 0, (* )

сформированное по /-му уравнению системы (8.5), обладает всеми свойствами правильного отсечения.

Для решения задачи целочисленного линейного программиро­вания (8.1)-(8.4) методом Гомори используется следующий ал­горитм:

1. Симплексным методом решить задачу (8.1)-(8.3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочис­ленного программирования (8.1)-(8.4). Если первая задача (8.1)-

(8.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и вторая задача (8.1)-(8.4) также неразре­шима.

2. Если среди компонент оптимального решения есть неце­лые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (8.5) сформировать пра­вильное отсечение (8.6).

3. Неравенство (8.6) введением дополнительной неотрицатель­ной целочисленной переменной преобразовать в равносильное уравнение

{Р(} - |а/ т+1 }*т+1- ■-{а|"л }хп + хп+1 > (®*^)

и включить его в систему ограничений (8.2).

4. Полученную расширенную задачу решить симплексным ме­тодом. Если найденный оптимальный план будет целочисленным,

то задача целочисленного программирования (8.1)-(8.4) решена. В противном случае вернуться к п. 2 алгоритма.

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

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

^ 8.1. Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Фермер может заказать обо­рудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед., требующие производственную площадь 3 кв. м (с уче­том проходов) и обеспечивающие производительность за смену 2 т зерна, и более мощные машины типа В стоимостью 4 ден. ед., занимающие площадь 5 кв. м и обеспечивающие производитель­ность за смену 3 т сортового зерна.

Требуется составить оптимальный план приобретения оборудо­вания, обеспечивающий максимальную общую производитель­ность при условии, что фермер может приобрести не более 8 ма­шин типа В.

Решение. Обозначим через х\, х2 количество машин соот­ветственно типа А и В, через Z - общую производительность. Тогда математическая модель задачи примет вид:

На рис. 8.2 ОКЬМ - область допустимых решений задачи (8.1") - (8.3"), ограниченная прямыми (1), (2), (3) и осями координат; />(2/3; 8) - точка оптимального, но нецелочисленного решения зада­чи (8.1") - (8.3"); (4) - прямая, отсекающая это нецелочисленное решение; 0№М - область допустимых решений расширенной зада­чи (8.1’) - (8.3’), (8.61); М2; 7) - точка оптимального целочисленно­го решения.

I шаг. Основные переменные х3, х4, *5; неосновные перемен­ные Х\, Х2.

х3	= 60 -	Зх! - 5х2,
х4	= 34 -	Зх) - 4х2,
х5	= 8	- *2>
	Z = 2х)	+ Зх2.

Первое базисное решение Х\ = (0; 0; 60; 34; 8) - допустимое. Соответствующее значение линейной функции = 0.

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

Хг = 1ШП|т;т;Т| = 8,

т.е. разрешающим (выделенным) является третье уравнение. При *2 = 8 в этом уравнении Х5 = 0, и в неосновные переходит пере­менная Х5.

II шаг. Основные переменные х2, х3, х*; неосновные пере­менные Хь Х5.

{

(8.6)

Введя дополнительную целочисленную переменную х6 > О, получим равносильное неравенству (8.6") уравнение

~1*5 + Хб = °" ^8"7 ^

Уравнение (8.7") необходимо включить в систему ограничений (8.5") исходной канонической задачи, после чего повторить про­цесс решения задачи симплексным методом применительно к расширенной задаче. При этом для сокращения числа шагов (итераций) рекомендуется вводить дополнительное уравнение (8.7") в систему, полученную на последнем шаге решения задачи (без условия целочисленности).

IV шаг. Основные переменные Х), *2, хз> *б‘> неосновные пе­ременные *1, *2-

Х1 = з - 3*4 +

х3 = 18 + х4 +___ х5,

х6 - + ^х4 + з"х5-

Базисное решение Х4 = (у; 8; 18; 0; 0; -у) - недопусти­мое. (Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение).

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

V шаг. Основные переменные Х\, Х2, Х3, Х5; неосновные пере­менные Я], Х£

Получим после преобразований:

ЛГ| = 2 - х4 + 2х6,

*2 = 7 + 2х* ~ 2Х("

х3 = 19 + -х4 + -х6,

*5 = 1 - 2х* + 2Х6’

2 = 25-|х4--|х6.

^5 =(2; 7; 19; 0; 1;0);^ = 25.

Так как в выражении линейной функции нет основных пере­менных с положительными коэффициентами, то Х5 - оптималь­ное решение.

Итак, 2тах = 25 при оптимальном целочисленном решении X* - Х$ =(2; 7; 19; 0; 1; 0), т.е. максимальную производительность 25 т сортового зерна за смену можно получить приобретением 2 машин типа А и 7 машин типа В\ при этом незанятая площадь помещения составит 19 кв. м, остатки денежных средств из выде­ленных равны 0, в резерве для покупки - 1 машина типа В (шестая компонента содержательного смысла не имеет).

Замечание. Для геометрической интерпретации на плос­кости Ох\Хг (см. рис.8.2) отсечения (8.6") необходимо вхо­дящие в него переменные х4 и х$ выразить через перемен­ные XI и х2. Получим (см. 2-е и 3-е уравнения системы ог­раничений (8.5")):

у - у (34 - Зх, - 4х2) - у (8 - х2) £ 0 или х, + 2х2 £ 16.

(см. отсечение прямой (4) на рис 8.2)>

^ 8.2. Имеется достаточно большое количество бревен длиной 3 м. Бревна следует распилить на заготовки двух видов: длиной 1,2 м и длиной 0,9 м, причем заготовок каждого вида должно быть полу­чено не менее 50 шт. и 81 шт. соответственно. Каждое бревно можно распилить на указанные заготовки несколькими способа­ми: 1) на 2 заготовки по 1,2 м; 2) на 1 заготовку по 1,2 м и 2 заго­товки по 0,9 м; 3) на 3 заготовки по 0,9 м. Найти число бревен,

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

Решение. Обозначим через х\, хі, хт, число бревен, распили­ваемых соответственно 1,"2-и 3-м способами. Из них можно полу­чить 2хі + *2 заготовок по 1,2 м и 2л\ + Зх2 заготовок по 0,9 м. Общее количество бревен обозначим I. Тогда математическая модель задачи примет вид:

I 2х, + х2 - х4 = 50, }