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

10

Первое ограничение Гомори: 2/9x3 + 8/9x4 - S1 = 4/9, S1 ≥ 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2 Из второго ограничения задачи: х4 = 16 - 4х1 - х2

Подставляем х3 и х4 в первое ограничение Гомори и после преобразований получаем: 4х1 + 2х2 + S1 = 18, S1 ≥ 0.

Отсюда имеем: 4х1 + 2х2 ≤ 18. Это ограничение отсекает от множества планов область, содержащую точку 1. Новый оптимальный нецелочисленный план - точка 2.

Второе ограничение Гомори : 1/4x3 + 7/8S1 - S2 = 1/2, S2 ≥ 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2 Из первого ограничения Гомори: S1 = 18 - 4х1 - 2х2

Получаем: 4х1 + 3х2 + S2 = 20, S2 ≥ 0 или 4х1 + 3х2 ≤ 20. Это ограничение отсекает от множества планов область, содержащую точку 2. Новый

оптимальный нецелочисленный план - точка 3.

Третье ограничение Гомори : 2/7x3 + 6/7S2 - S3 = 4/7, S3 ≥ 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2 Из второго ограничения Гомори: S2 = 20 - 4х1 - 3х2

После подстановки x3 и S2 в третье ограничение Гомори получаем: 4х1 + 4х2 ≤ 22. Это ограничение отсекает от множества планов область, содержащую точку 3. Новый оптимальный нецелочисленный план - точка 4.

Четвертое ограничение Гомори : 1/4S3 - S4 = 1/2, S4 ≥ 0

Из третьего ограничения Гомори: S3 = 22 - 4х1 - 4х2

Получаем: х1 + х2 + S4 = 5, S4 ≥ 0. Отсюда имеем: х1 + х2 ≤ 5. Это ограничение отсекает от множества планов область, содержащую точку 4. Новый оптимальный нецелочисленный план - точка 5.

Пятое ограничение Гомори : 1/3x4 + 2/3S4 - S5 = 2/3, S5 ≥ 0

Из второго ограничения задачи: х4 = 16 - 4х1 - х2 Из четвертого ограничения Гомори: S4 = 5 - х1 - х2

Получаем: 2х1 + х2 + S5 = 8, S5 ≥ 0. Отсюда: 2х1 + х2 ≤ 8. Это ограничение отсекает от множества планов область, содержащую точку 5.

Оптимальный целочисленный план - точка 6 с координатами (3;2). Заштрихованная часть - целочисленное множество планов.

11

3. ЗАДАНИЯ

Решить задачу линейного целочисленного программирования при xj ≥ 0 (j = 1, 2, ..., n). В вариантах, где n = 2, дать геометрическую интерпретацию метода Гомори.

43.max L = 4,4x1 + 2,7x2 + 3,2x3 + 2,8x4 + 3,5x5 + 3,9x6

при ограничениях

80х1 + 62х2 + 92x3 + 82x4 + 65x5 + 90x6 ≤ 800 95х1 + 90х2 + 96x3 + 110x4 + 120x5 + 80x6 ≤ 600

44.max L = 5x1 + 2x2 - 3x3 + 2x4 + 3x5 - 3x6

при ограничениях

5х1 + 6х2 + 4x3 + 2x4 - 3x5 + 5x6 = 11

45.max L = 4x1 + 7x2 - x3 + 2x4

при ограничениях

х1 + х2 + x3 + x4 = 15

4.КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Может ли задача линейного целочисленного программирования иметь несколько решений?

2.Может ли ограничение Гомори быть записано следующим обра-

зом: 1/5x5 - 7/8x6 ≥ 1/3?

15

3.Среди ограничений задачи линейного целочисленного програм-

мирования есть такие: x1 + x2 + x3 ≥ 10 и x1 + x2 + x3 ≤ 20. Дайте экономическую интерпретацию данных ограничений.

4.На основании чего мы можем говорить, что задача с ограничениями Гомори не имеет ни одного плана?

5.В каких случаях задача линейного целочисленного программирования неразрешима?

6.В задаче линейного целочисленного программирования переменные принимают лишь 2 значения: 0 или 1. Какой экономический смысл данного решения? Приведите примеры.

7.Отвечает ли требованиям, предъявляемым к ограничениям Го-

8. Каков максимальный размер симплексных таблиц при использовании метода Гомори?

СПИСОК ЛИТЕРАТУРЫ

1.Тынкевич М.А., Ветрова Г.С., Бияков О.А. Экономикоматематические методы (исследование операций). –Кемерово : КузГТУ, 1997. –176 с.

2.Акулич И.Л. Математическое программирование в примерах и задачах: Учеб.пособие для студентов эконом. спец. вузов. – М.: Высш.

шк., 1986.- 319 с.

Составитель Наталья Юрьевна Коломарова

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ГОМОРИ

Методические указания и задания к практическим занятиям по курсу

«Экономико-математические методы» для студентов экономических специальностей

Редактор З.М.Савина

ЛР № 020313 от 23.12.96

Подписано в печать 29.12.99. Формат 60х84/16.

Бумага офсетная. Отпечатано на ризографе. Уч.-изд.л. 1,0. Тираж 200 экз. Заказ .

Кузбасский государственный технический университет. 650026, Кемерово, ул. Весенняя, 28.

Типография Кузбасского государственного технического университета. 650099, Кемерово, ул. Д.Бедного, 4А.