Метод Гомори
Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования.
Пусть найдено решение задачи ЛП: . Решение Li будет целым числом, если т.е. . i> — дробная часть нецелочисленного оптимального решения xi, i> — дробная часть не базисных переменных. Данное соотношение определяет правильное отсечение Гомори (см. рисунок).
Инструкция . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее . Полученное решение сохраняется в файле Word . Дополнительно создается шаблон решения в формате Excel . При этом ограничения типа xi ≥ 0 не учитывайте.
Виды алгоритма Гомори
- Первый алгоритм Гомори решения полностью целочисленных задач.
- Второй алгоритм Гомори для частично целочисленных задач линейного программирования.
- Решается задача линейного программирования без учета целочисленности.
- Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение.
- Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной.
- Полученная задача решается двойственным симплекс-методом.
Геометрическая интерпретация отсечения Гомори Пример . Научно-производственное объединение «Стрела» занимается изготовлением комплектующих изделий для предприятий ВПК. При изготовлении изделий типа А и типа В используются сталь и цветные металлы. Технологический процесс также включает обработку изделий на токарных и фрезерных станках. По технологическим нормам на производство одного изделия типа А и одного изделия типа В требуется определенное количество сырья и некоторый объем станко-часов для обработки на станках в цеху. Технологические данные производственного процесса приведены в таблице.
В течение месяца цеха НПО «Стрела» располагает ограниченными ресурсами по сырью и по времени работы в производственных цехах (см. таблицу). Прибыль от реализации одного изделия типа А составляет 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 = 54 6 /11, x2 = 131 9 /11
F(X) = 250•131 9 /11 + 100•54 6 /11 = 38409 1 /11 Полученный оптимальный план не является целочисленным, поэтому применяем метод Гомори. Наибольшая дробная часть находится во втором уравнении у переменной x4 ( 10 /11). Составляем дополнительное ограничение:
q2 — q21•x1 — q22•x2 — q23•x3 — q24•x4 — q25•x5 — q26•x6≤0
q2 = b2 — [b2] = 1590 10 /11 — 1590 = 10 /11
q21 = a21 — [a21] = 0 — 0 = 0
q22 = a22 — [a22] = 0 — 0 = 0
q23 = a23 — [a23] = 3 47 /66 — 3 = 47 /66
q24 = a24 — [a24] = 1 — 1 = 0
q25 = a25 — [a25] = -1 17 /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 | 131 9 /11 | 0 | 1 | 41 /330 | 0 | -1 /33 | 0 | 0 |
| x4 | 1590 10 /11 | 0 | 0 | 3 47 /66 | 1 | -1 17 /33 | 0 | 0 |
| x1 | 54 6 /11 | 1 | 0 | -3 /11 | 0 | 1 /11 | 0 | 0 |
| x6 | 6500 | 0 | 0 | 18 1 /3 | 0 | -6 2 /3 | 1 | 0 |
| x7 | -10 /11 | 0 | 0 | -47 /66 | 0 | -16 /33 | 0 | 1 |
| F(X0) | -38409 1 /11 | 0 | 0 | -3 26 /33 | 0 | -1 17 /33 | 0 | 0 |
| θ | — | — | -3 26 /33 : ( -47 /66) = 5 15 /47 | — | -1 17 /33 : ( -16 /33) = 3 1 /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] = 131 7 /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 | 131 7 /8 | 0 | 1 | 27 /160 | 0 | 0 | 0 | -1 /16 | 0 |
| x4 | 1593 3 /4 | 0 | 0 | 5 15 /16 | 1 | 0 | 0 | -3 1 /8 | 0 |
| x1 | 54 3 /8 | 1 | 0 | -13 /32 | 0 | 0 | 0 | 3 /16 | 0 |
| x6 | 6512 1 /2 | 0 | 0 | 28 1 /8 | 0 | 0 | 1 | -13 3 /4 | 0 |
| x5 | 1 7 /8 | 0 | 0 | 1 15 /32 | 0 | 1 | 0 | -2 1 /16 | 0 |
| x8 | -7 /8 | 0 | 0 | -27 /160 | 0 | 0 | 0 | -15 /16 | 1 |
| F(X0) | -38406 1 /4 | 0 | 0 | -1 9 /16 | 0 | 0 | 0 | -3 1 /8 | 0 |
| θ | — | — | -1 9 /16 : ( -27 /160) = 9 7 /27 | — | — | — | -3 1 /8 : ( -15 /16) = 3 1 /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] = 131 14 /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 | 131 14 /15 | 0 | 1 | 9 /50 | 0 | 0 | 0 | 0 | -1 /15 | 0 |
| x4 | 1596 2 /3 | 0 | 0 | 6 1 /2 | 1 | 0 | 0 | 0 | -3 1 /3 | 0 |
| x1 | 54 1 /5 | 1 | 0 | -11 /25 | 0 | 0 | 0 | 0 | 1 /5 | 0 |
| x6 | 6525 1 /3 | 0 | 0 | 30 3 /5 | 0 | 0 | 1 | 0 | -14 2 /3 | 0 |
| x5 | 3 4 /5 | 0 | 0 | 1 21 /25 | 0 | 1 | 0 | 0 | -2 1 /5 | 0 |
| x7 | 14 /15 | 0 | 0 | 9 /50 | 0 | 0 | 0 | 1 | -1 1 /15 | 0 |
| x9 | -14 /15 | 0 | 0 | -9 /50 | 0 | 0 | 0 | 0 | -14 /15 | 1 |
| F(X0) | -38403 1 /3 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -3 1 /3 | 0 |
| θ | — | — | -1 : ( -9 /50) = 5 5 /9 | — | — | — | — | -3 1 /3 : ( -14 /15) = 3 4 /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
