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

7

План Х5 - оптимальный нецелочисленный. Дополнительное ограничение запишем по второй строке:

строке, а не по строке Гомори, следовательно, переходим к М-задаче:

9

Экономическая интерпретация: согласно полученному решению предприятию необходимо закупить 3 машины типа «А» и 2 машины типа «В». При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден.ед. можно будет направить на какие-либо иные цели, например, на премирование рабочих, которые будут заниматься отладкой полученного оборудования. На излишнюю площадь в 2 кв.м можно поставить ящик с цветами.

Геометрическая интерпретация метода Гомори: строим множе-

ство планов (см. рисунок). В точке 1 - оптимальный нецелочисленный план.

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, дать геометрическую интерпретацию метода Гомори.