Примеры решения задач оптимизации методом Гомори

Задача: Для приобретения нового оборудования предприятие выделяет 19 ден.ед. Оборудование должно быть размещено на площади, не превышающей 16 кв.м. Предприятие может заказать оборудование двух видов: машины типа “А” стоимостью 2 ден.ед., требующие производственную площадь 4 кв.м и обеспечивающие производительность за смену 8 т продукции, и машины типа “В” стоимостью 5 ден.ед., занимающие площадь 1 кв.м и обеспечивающие производительность за смену 6 т продукции.

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

Решение: Обозначим через x₁, x₂ количество машин соответственно типа “А” и “В”, через L - их общую производительность. Тогда математическая модель задачи:

max L = 8x₁ + 6x₂

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

x₁, x₂ - целые числа

решаем задачу симплексным методом без учета целочисленности.

Получен оптимальный нецелочисленный план Х_опт = (61/18;22/9). L_max = 376/9.

Т.к. у компоненты плана х₂ максимальная дробная часть:
max(4/9;7/18) = 4/9, то дополнительное ограничение записываем по первой строке.

22/9 - [22/9] = (2/9 - [2/9])x₃ + (-1/9 - [-1/9])x₄ - S₁, S₁ 0
22/9 - 2 = (2/9 - 0)x₃ + (-1/9 - (-1))x₄ - S₁, S₁ 0
4/9 = 2/9x₃ + 8/9x₄ - S₁, S₁ 0 - первое ограничение Гомори.

Составленное ограничение дописываем к имеющимся в симплексной таблице.

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

, следовательно, в базис вводим вектор х₄.

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

Найденный план оптимален, но нецелочисленный. Строим новое ограничение Гомори.

Т.к. максимальная дробная часть среди компонент плана равна 1/2, записываем дополнительное ограничение по первой строке (можно и по третьей).

5/2 - [5/2] = (1/4 - [1/4])x₃ + (-1/8 - [-1/8])S₁ - S₂, S₂ 0
1/2 = 1/4x₃ + 7/8S₁ - S₂, S₂ 0 - второе ограничение Гомори

Это ограничение добавляем в последнюю симплексную таблицу.

Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора.

Определяем вектор, вводимый в базис: . Можно ввести либо x₃, либо S₁. Введем вектор S₁.

Тогда значение соответствует дополнительному ограничению.

Получаем новый оптимальный нецелочисленный план. Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие переменной S₁.

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

4/7 = 2/7х₃ + 6/7S₂ - S₃, S₃ 0 - третье ограничение Гомори.

Определяем вектор, вводимый в базис: . Это вектор х₃. Минимальное значение q = 2, что соответствует дополнительной строке.

После проведения очередных симплексных преобразований получили:

План Х₅ - оптимальный нецелочисленный.

Дополнительное ограничение запишем по второй строке:

1/2 = 1/4S₃ - S₄, S₄ 0 - четвертое ограничение Гомори.

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

Минимальное значение получилось по 3 строке, а не по строке Гомори, следовательно, переходим к М-задаче: введем дополнительную переменную х₅ в ограничение Гомори.

Дробная часть = max(1/3; 2/3) = 2/3, следовательно, дополнительное ограничение записываем по второй строке.

2/3 = 1/3х₄ + 2/3S₄ - S₅,S₅ 0 - пятое ограничение Гомори.

Вектор, вводимый в базис: , вводим х₄.

Тогда значение соответствует строке Гомори.

План Х₈ = (3; 2; 3; 2) - оптимальный целочисленный. L_max = 36.

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

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

Первое ограничение Гомори: 2/9x₃ + 8/9x₄ - S₁ = 4/9, S₁ 0
Из первого ограничения задачи: х₃ = 19 - 2х₁ - 5х₂
Из второго ограничения задачи: х₄ = 16 - 4х₁ - х₂

Подставляем х₃ и х₄ в первое ограничение Гомори и после преобразований получаем: 4х₁ + 2х₂ + S₁ = 18, S₁ 0.

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

Второе ограничение Гомори: 1/4x₃ + 7/8S₁ - S₂ = 1/2, S₂ 0
Из первого ограничения задачи: х₃ = 19 - 2х₁ - 5х₂
Из первого ограничения Гомори: S₁ = 18 - 4х₁ - 2х₂

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

Третье ограничение Гомори: 2/7x₃ + 6/7S2 - S₃ = 4/7, S₃ 0
Из первого ограничения задачи: х₃ = 19 - 2х₁ - 5х₂
Из второго ограничения Гомори: S₂ = 20 - 4х₁ - 3х₂

После подстановки x₃ и S₂ в третье ограничение Гомори получаем: 4х₁ + 4х₂ 22. Это ограничение отсекает от множества планов область, содержащую точку 3. Новый оптимальный нецелочисленный план - точка 4.

Четвертое ограничение Гомори: 1/4S₃ - S₄ = 1/2, S₄ 0
Из третьего ограничения Гомори: S₃ = 22 - 4х₁ - 4х₂

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

Пятое ограничение Гомори: 1/3x₄ + 2/3S₄ - S₅ = 2/3, S₅ 0
Из второго ограничения задачи: х₄ = 16 - 4х₁ - х₂
Из четвертого ограничения Гомори: S₄ = 5 - х₁ - х₂

Получаем: 2х₁ + х₂ + S₅ = 8, S₅ 0. Отсюда: 2х₁ + х₂ 8. Это ограничение отсекает от множества планов область, содержащую точку 5. Оптимальный целочисленный план - точка 6 с координатами (3;2).

Заштрихованная часть - целочисленное множество планов.

Поиск по сайту: