Метод Гомори
Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования.Пусть найдено решение задачи ЛП:
. Решение Li будет целым числом, если 
т.е. 
. {βi} - дробная часть нецелочисленного оптимального решения xi, {di} - дробная часть не базисных переменных. Данное соотношение определяет правильное отсечение Гомори (см. рисунок).
Назначение сервиса. Онлайн-калькулятор применяется для решения задач целочисленного линейного программирования методом отсечений. В ходе решения используются симплексные таблицы.
Виды алгоритма Гомори
- Первый алгоритм Гомори решения полностью целочисленных задач.
- Второй алгоритм Гомори для частично целочисленных задач линейного программирования.
Алгоритм Гомори для полностью целочисленных задач включает в себя следующие этапы:
- Решается задача линейного программирования без учета целочисленности.
- Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение.
- Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной.
- Полученная задача решается двойственным симплекс-методом.
Пример. Научно-производственное объединение «Стрела» занимается изготовлением комплектующих изделий для предприятий ВПК. При изготовлении изделий типа А и типа В используются сталь и цветные металлы. Технологический процесс также включает обработку изделий на токарных и фрезерных станках. По технологическим нормам на производство одного изделия типа А и одного изделия типа В требуется определенное количество сырья и некоторый объем станко-часов для обработки на станках в цеху. Технологические данные производственного процесса приведены в таблице.
В течение месяца цеха НПО «Стрела» располагает ограниченными ресурсами по сырью и по времени работы в производственных цехах (см. таблицу). Прибыль от реализации одного изделия типа А составляет 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