Метод Гомори

Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования.
Пусть найдено решение задачи ЛП: . Решение Li будет целым числом, если Метод Гомори т.е. правильное отсечение Гомори. {βi} - дробная часть нецелочисленного оптимального решения xi, {di} - дробная часть не базисных переменных. Данное соотношение определяет правильное отсечение Гомори (см. рисунок).

Назначение сервиса. Онлайн-калькулятор применяется для решения задач целочисленного линейного программирования методом отсечений. В ходе решения используются симплексные таблицы. (см. пример).

Инструкция. Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения методом Гомори). Дополнительно создается шаблон решения в формате Excel.
Количество переменных
Количество строк (количество ограничений)
При этом ограничения типа xi ≥ 0 не учитывайте.

Виды алгоритма Гомори

  1. Первый алгоритм Гомори решения полностью целочисленных задач.
  2. Второй алгоритм Гомори для частично целочисленных задач линейного программирования.

Алгоритм Гомори для полностью целочисленных задач включает в себя следующие этапы:

  1. Решается задача линейного программирования без учета целочисленности.
  2. Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение.
  3. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной.
  4. Полученная задача решается двойственным симплекс-методом.
Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членов bi и целыми коэффициентами aij, то данная задача не имеет целочисленного оптимального решения.
Геометрическая интерпретация отсечения Гомори
Геометрическая интерпретация отсечения Гомори

Пример. Научно-производственное объединение «Стрела» занимается изготовлением комплектующих изделий для предприятий ВПК. При изготовлении изделий типа А и типа В используются сталь и цветные металлы. Технологический процесс также включает обработку изделий на токарных и фрезерных станках. По технологическим нормам на производство одного изделия типа А и одного изделия типа В требуется определенное количество сырья и некоторый объем станко-часов для обработки на станках в цеху. Технологические данные производственного процесса приведены в таблице.
В течение месяца цеха НПО «Стрела» располагает ограниченными ресурсами по сырью и по времени работы в производственных цехах (см. таблицу). Прибыль от реализации одного изделия типа А составляет 100 руб., а от единицы изделия типа В – 250 руб.

  Сырье Работа в цеху, станко-час Прибыль от реализации, руб.
Цветные металлы Сталь Токарные работы Фрезерные работы
Изделие А 10 25 41 90 100
Изделие В 30 25 90 50 250
Ресурсы 4500 6250 14100 18000  

Найти оптимальный план производства для НПО «Стрела» (количество изделия типа А и типа В – целые числа), дающий наибольшую прибыль.

Решение.
Экономико-математическая модель задачи.
x1 – план производства изделий типа А, x2 – план производства изделий типа В,
x1, x2  - целые числа.
Ограничения по ресурсам
10x1 +  30x2 ≤ 4500
25x1 +  25x2 ≤ 6250
41x1 +  90x2 ≤ 14100
90x1 +  50x2 ≤ 18000
Целевая функция
100x1 +  250x2 → max

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

Базис B x1 x2 x3 x4 x5 x6
x2 1450/11 0 1 41/330 0 -1/33 0
x4 17500/11 0 0 245/66 1 -50/33 0
x1 600/11 1 0 -3/11 0 1/11 0
x6 6500 0 0 55/3 0 -20/3 1
F(X3) 422500/11 0 0 125/33 0 50/33 0

x1 = 546/11, x2 = 1319/11
F(X) = 250•1319/11 + 100•546/11 = 384091/11

Полученный оптимальный план не является целочисленным, поэтому применяем метод Гомори. Наибольшая дробная часть находится во втором уравнении у переменной x4 (10/11). Составляем дополнительное ограничение:
q2 - q21•x1 - q22•x2 - q23•x3 - q24•x4 - q25•x5 - q26•x6≤0
q2 = b2 - [b2] = 159010/11 - 1590 = 10/11
q21 = a21 - [a21] = 0 - 0 = 0
q22 = a22 - [a22] = 0 - 0 = 0
q23 = a23 - [a23] = 347/66 - 3 = 47/66
q24 = a24 - [a24] = 1 - 1 = 0
q25 = a25 - [a25] = -117/33 + 2 = 16/33
q26 = a26 - [a26] = 0 - 0 = 0
Дополнительное ограничение имеет вид:
10/11-47/66x3-16/33x5 ≤ 0
Преобразуем полученное неравенство в уравнение:
10/11-47/66x3-16/33x5 + x7 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F(x) = -F(X).

Базис B x1 x2 x3 x4 x5 x6 x7
x2 1450/11 0 1 41/330 0 -1/33 0 0
x4 17500/11 0 0 245/66 1 -50/33 0 0
x1 600/11 1 0 -3/11 0 1/11 0 0
x6 6500 0 0 55/3 0 -20/3 1 0
x7 -10/11 0 0 -47/66 0 -16/33 0 1
F(X0) -422500/11 0 0 -125/33 0 -50/33 0 0

Первая итерация Гомори. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольшее по модулю. Ведущей будет пятая строка, а переменную x7 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует пятому столбцу, т.е. переменную x5 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-16/33).
Базис B x1 x2 x3 x4 x5 x6 x7
x2 1319/11 0 1 41/330 0 -1/33 0 0
x4 159010/11 0 0 347/66 1 -117/33 0 0
x1 546/11 1 0 -3/11 0 1/11 0 0
x6 6500 0 0 181/3 0 -62/3 1 0
x7 -10/11 0 0 -47/66 0-16/33 0 1
F(X0) -384091/11 0 0 -326/33 0-117/33 0 0
θ - - -326/33 : (-47/66) = 515/47 - -117/33 : (-16/33) = 31/8 - -

4. Пересчет симплекс-таблицы выполняем с помощью метода Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5 x6 x7
x2 1055/8 0 1 27/160 0 0 0 -1/16
x4 6375/4 0 0 95/16 1 0 0 -25/8
x1 435/8 1 0 -13/32 0 0 0 3/16
x6 13025/2 0 0 225/8 0 0 1 -55/4
x5 15/8 0 0 47/32 0 1 0 -33/16
F(X0) -153625/4 0 0 -25/16 0 0 0 -25/8

В полученном оптимальном плане присутствуют дробные числа. По первому уравнению с переменной x2, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 7/8, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5 - q16•x6 - q17•x7≤0
q1 = b1 - [b1] = 1317/8 - 131 = 7/8
q11 = a11 - [a11] = 0 - 0 = 0
q12 = a12 - [a12] = 1 - 1 = 0
q13 = a13 - [a13] = 27/160 - 0 = 27/160
q14 = a14 - [a14] = 0 - 0 = 0
q15 = a15 - [a15] = 0 - 0 = 0
q16 = a16 - [a16] = 0 - 0 = 0
q17 = a17 - [a17] = -1/16 + 1 = 15/16
Дополнительное ограничение имеет вид:
7/8-27/160x3-15/16x7 ≤ 0
Преобразуем полученное неравенство в уравнение:
7/8-27/160x3-15/16x7 + x8 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 1055/8 0 1 27/160 0 0 0 -1/16 0
x4 6375/4 0 0 95/16 1 0 0 -25/8 0
x1 435/8 1 0 -13/32 0 0 0 3/16 0
x6 13025/2 0 0 225/8 0 0 1 -55/4 0
x5 15/8 0 0 47/32 0 1 0 -33/16 0
x8 -7/8 0 0 -27/160 0 0 0 -15/16 1
F(X0) -153625/4 0 0 -25/16 0 0 0 -25/8 0

Вторая итерация Гомрои. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных наибольшей по модулю является переменная x8. Ее следует вывести из базиса.
3. Минимальное значение θ соответствует седьмому столбцу, т.е. переменную x7 необходимо ввести в базис.
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 1317/8 0 1 27/160 0 0 0 -1/16 0
x4 15933/4 0 0 515/16 1 0 0 -31/8 0
x1 543/8 1 0 -13/32 0 0 0 3/16 0
x6 65121/2 0 0 281/8 0 0 1 -133/4 0
x5 17/8 0 0 115/32 0 1 0 -21/16 0
x8 -7/8 0 0 -27/160 0 0 0-15/16 1
F(X0) -384061/4 0 0 -19/16 0 0 0-31/8 0
θ - - -19/16 : (-27/160) = 97/27 - - - -31/8 : (-15/16) = 31/3 -

4. Выполняем преобразование Новых отсечений Гомори.
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 1979/15 0 1 9/50 0 0 0 0 -1/15
x4 4790/3 0 0 13/2 1 0 0 0 -10/3
x1 271/5 1 0 -11/25 0 0 0 0 1/5
x6 19576/3 0 0 153/5 0 0 1 0 -44/3
x5 19/5 0 0 46/25 0 1 0 0 -11/5
x7 14/15 0 0 9/50 0 0 0 1 -16/15
F(X0) -115210/3 0 0 -1 0 0 0 0 -10/3

В оптимальном плане присутствуют дробные числа. Наибольшая дробная часть у переменной x2 (14/15). Составляем дополнительное ограничение: q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5 - q16•x6 - q17•x7 - q18•x8≤0
q1 = b1 - [b1] = 13114/15 - 131 = 14/15
q11 = a11 - [a11] = 0 - 0 = 0
q12 = a12 - [a12] = 1 - 1 = 0
q13 = a13 - [a13] = 9/50 - 0 = 9/50
q14 = a14 - [a14] = 0 - 0 = 0
q15 = a15 - [a15] = 0 - 0 = 0
q16 = a16 - [a16] = 0 - 0 = 0
q17 = a17 - [a17] = 0 - 0 = 0
q18 = a18 - [a18] = -1/15 + 1 = 14/15
Дополнительное ограничение имеет вид:
14/15-9/50x3-14/15x8 ≤ 0
Преобразуем полученное неравенство в уравнение:
14/15-9/50x3-14/15x8 + x9 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x2 1979/15 0 1 9/50 0 0 0 0 -1/15 0
x4 4790/3 0 0 13/2 1 0 0 0 -10/3 0
x1 271/5 1 0 -11/25 0 0 0 0 1/5 0
x6 19576/3 0 0 153/5 0 0 1 0 -44/3 0
x5 19/5 0 0 46/25 0 1 0 0 -11/5 0
x7 14/15 0 0 9/50 0 0 0 1 -16/15 0
x9 -14/15 0 0 -9/50 0 0 0 0 -14/15 1
F(X0) -115210/3 0 0 -1 0 0 0 0 -10/3 0

Третья итерация методом Гомори. Переменную x9 следует вывести из базиса. Минимальное значение θ соответствует восьмому столбцу, т.е. переменную x8 необходимо ввести в базис.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x2 13114/15 0 1 9/50 0 0 0 0 -1/15 0
x4 15962/3 0 0 61/2 1 0 0 0 -31/3 0
x1 541/5 1 0 -11/25 0 0 0 0 1/5 0
x6 65251/3 0 0 303/5 0 0 1 0 -142/3 0
x5 34/5 0 0 121/25 0 1 0 0 -21/5 0
x7 14/15 0 0 9/50 0 0 0 1 -11/15 0
x9 -14/15 0 0 -9/50 0 0 0 0 -14/15 1
F(X0) -384031/3 0 0 -1 0 0 0 0 -31/3 0
θ - - -1 : (-9/50) = 55/9 - - - - -31/3 : (-14/15) = 34/7 -

4. Выполняем преобразование.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x2 132 0 1 27/140 0 0 0 0 0 -1/14
x4 1600 0 0 50/7 1 0 0 0 0 -25/7
x1 54 1 0 -67/140 0 0 0 0 0 3/14
x6 6540 0 0 234/7 0 0 1 0 0 -110/7
x5 6 0 0 317/140 0 1 0 0 0 -33/14
x7 2 0 0 27/70 0 0 0 1 0 -8/7
x8 1 0 0 27/140 0 0 0 0 1 -15/14
F(X0) -38400 0 0 -5/14 0 0 0 0 0 -25/7

Решение получилось целочисленным. Оптимальный целочисленный план можно записать так: x1 = 54, x2 = 132. F(X) = 38400
Открыть диалог Discus Помощь в решении контрольных