Алгоритм Гомори для частично целочисленной задачи линейного программирования

В частично целочисленных задачах требование целочисленности накладывается не на все переменные, а на одну или некоторые из них.
Пусть дана следующая задача:
max {F(x)=∑cixi|∑ajixi{≤=≥}bj, j = 1,m, xi≥0 для всех i = 1,n}, (1)

целочисленной должна быть только переменная xk.
Таблица 1- симплекс-таблица для задачи ЛП
базисные переменные Свободные члены Небазисные переменные
w1 w2 ... wn
v1 β1 α11 α12 ... α1n
v2 β2 α21 α22 ... α2n
. . . . . .
vm βm αm1 αm2 ... αmn
F β c1 c2 ... cn

В результате решения задачи с отброшенным условием целочисленности получена оптимальная симплекс-таблица (табл. 1) и переменной xk соответствует строка базисной переменной vk этой таблицы. Эта строка порождает равенство
∑αkiwi+vkk. (2)

Выделим в βk целую и дробную часть и преобразуем (2) к виду
vk-[βk]={βk}-∑αkiwi (3)

Если значение vk = βk оказалось дробным, то можно сказать, что интервал [βk]<vk<[βk ]+1 не содержит допустимых целочисленных компонентов решения. Тогда для целочисленной переменной vk должно выполняться одно из двух неравенств: либо vk≤[βk], либо vk≥ [βk ] + 1. Левая часть выражения (3) должна быть целой.
Рассмотрим условия, при которых правая часть (3) будет принимать целое значение.
Если vk≤[βk ], то из (3) для αki≥ 0 следует, что
k}-∑αkiwi≤0 или ∑αkiwi≥{βk} (4)

Если vk≥[βk] + 1, то vk - [βk ] ≥ 1, и из (3) для αki≤0 следует, что
k}-∑αkiwi≥1 или ∑αkiwi≤{βk} -1 (5)

Умножим обе части неравенства (5) на
, тогда
(6)
Так как соотношения (4) и (6) не могут выполняться одновременно, их можно объединить в одно ограничение вида
(7)

где I+ – множество значений i, для которых αki > 0 ; I- – множество значений i , для которых αki< 0.

Пример №1. Решить задачу частично целочисленного линейного программирования.
Считать, что базисные переменные в оптимальной симплекс-таблице (до поиска целочисленного решения) должны быть целочисленными. По этой же таблице указать решение двойственной задачи; проверить ответ с помощью базисного вектора С0.

Решим задачу частично целочисленного линейного программирования симплексным методом, с использованием калькулятора. Определим максимальное значение целевой функции F(X) = 7x1 + 9x2 при следующих условиях-ограничений.
- x1 + 3x2 + x3=6
7x1 + x2 + x4=35
Для построения первого опорного плана в системе уравнений уже имеются базисные переменные.
-1x1 + 3x2 + 1x3 + 0x4 = 6
7x1 + 1x2 + 0x3 + 1x4 = 35
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =
-1310
7101

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x3, x4
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,6,35)
Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4
x3 6 -1 3 1 0
x4 35 7 1 0 1
F(X0) 0 -7 -9 0 0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (6 : 3 , 35 : 1 ) = 2
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 min
x3 6 -1 3 1 0 2
x4 35 7 1 0 1 35
F(X1) 0 -7 -9 0 0 0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=3
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4
6 : 3 -1 : 3 3 : 3 1 : 3 0 : 3
35-(6 • 1):3 7-(-1 • 1):3 1-(3 • 1):3 0-(1 • 1):3 1-(0 • 1):3
0-(6 • -9):3 -7-(-1 • -9):3 -9-(3 • -9):3 0-(1 • -9):3 0-(0 • -9):3


Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4
x2 2 -1/3 1 1/3 0
x4 33 22/3 0 -1/3 1
F(X1) 18 -10 0 3 0

Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (- , 33 : 71/3 ) = 41/2
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (71/3) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 min
x2 2 -1/3 1 1/3 0 -
x4 33 71/3 0 -1/3 1 41/2
F(X2) 18 -10 0 3 0 0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=71/3
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4
2-(33 • -1/3):71/3 -1/3-(71/3-1/3):71/3 1-(0 • -1/3):71/3 1/3-(-1/3-1/3):71/3 0-(1 • -1/3):71/3
33 : 71/3 71/3 : 71/3 0 : 71/3 -1/3 : 71/3 1 : 71/3
18-(33 • -10):71/3 -10-(71/3 • -10):71/3 0-(0 • -10):71/3 3-(-1/3 • -10):71/3 0-(1 • -10):71/3


Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4
x2 7/2 0 1 7/22 1/22
x1 9/2 1 0 -1/22 3/22
F(X2) 63 0 0 28/11 15/11

1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4
x2 7/2 0 1 7/22 1/22
x1 9/2 1 0 -1/22 3/22
F(X3) 63 0 0 28/11 15/11

Оптимальный план можно записать так:
x2 = 31/2
x1 = 41/2
F(X) = 9•31/2 + 7•41/2 = 63
Метод Гомори.
В полученном оптимальном плане переменная x2 имеет дробную часть числа. Дополнительное ограничение составляем по строке, соответствующей переменной x2.

После преобразования, умножения его на (-1) и введения дополнительной переменной х5 получим дополнительное ограничение в виде
-7/22x3-1/22x4+x5 = -1/2
Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F(x) = -F(X).

Базис B x1 x2 x3 x4 x5
x2 7/2 0 1 7/22 1/22 0
x1 9/2 1 0 -1/22 3/22 0
x5 -1/2 0 0 -7/22 -1/22 1
F(X0) -63 0 0 -28/11 -15/11 0

1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 3-ая строка, а переменную x5 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-7/22).

Базис B x1 x2 x3 x4 x5
x2 31/2 0 1 7/22 1/22 0
x1 41/2 1 0 -1/22 3/22 0
x5 -1/2 0 0 -7/22 -1/22 1
F(X0) -63 0 0 -26/11 -14/11 0
θ - - -26/11 : (-7/22) = 8 -14/11 : (-1/22) = 30 -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5
x2 3 0 1 0 0 1
x1 32/7 1 0 0 1/7 -1/7
x3 11/7 0 0 1 1/7 -22/7
F(X0) -59 0 0 0 -1 -8

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5
31/2-(-1/27/22):-7/22 0-(0 • 7/22):-7/22 1-(0 • 7/22):-7/22 7/22-(-7/227/22):-7/22 1/22-(-1/227/22):-7/22 0-(1 • 7/22):-7/22
41/2-(-1/2-1/22):-7/22 1-(0 • -1/22):-7/22 0-(0 • -1/22):-7/22 -1/22-(-7/22-1/22):-7/22 3/22-(-1/22-1/22):-7/22 0-(1 • -1/22):-7/22
-1/2 : -7/22 0 : -7/22 0 : -7/22 -7/22 : -7/22 -1/22 : -7/22 1 : -7/22
-63-(-1/2 • -26/11):-7/22 0-(0 • -26/11):-7/22 0-(0 • (-2)6/11):-7/22 -26/11-(-7/22 • -26/11):-7/22 -14/11-(-1/22 • -26/11):-7/22 0-(1 • -26/11):-7/22

Оптимальный целочисленный план можно записать так:
x2 = 3
x1 = 44/7
x3 = 14/7
F(X) = 59

Перейти к онлайн решению своей задачи

Пример №2.
Определим минимальное значение целевой функции F(X) = 6x1 + 8x2 + x3 + 2x4 при следующих условиях-ограничений.
x1 + 2x2 - x3≥3
2x1 + x2 + x3 + x4≥4
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус.
1x1 + 2x2-1x3 + 0x4-1x5 + 0x6 = 3
2x1 + 1x2 + 1x3 + 1x4 + 0x5-1x6 = 4
Умножим все строки на (-1) и будем искать первоначальный опорный план.
-1x1-2x2 + 1x3 + 0x4 + 1x5 + 0x6 = -3
-2x1-1x2-1x3-1x4 + 0x5 + 1x6 = -4
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =
-1-21010
-2-1-1-101

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,-3,-4)
Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4 x5 x6
x5 -3 -1 -2 1 0 1 0
x6 -4 -2 -1 -1 -1 0 1
F(X0) 0 6 8 1 2 0 0

1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 2-ая строка, а переменную x6 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Базис B x1 x2 x3 x4 x5 x6
x5 -3 -1 -2 1 0 1 0
x6 -4 -2 -1 -1 -1 0 1
F(X0) 0 6 8 1 2 0 0
θ 6 : (-2) = -3 8 : (-1) = -8 1 : (-1) = -1 2 : (-1) = -2 - -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6
x5 -3 -1 -2 1 0 1 0
x4 4 2 1 1 1 0 -1
F(X0) -8 2 6 -1 0 0 2

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6
-3-(-4 • 0):-1 -1-(-2 • 0):-1 -2-(-1 • 0):-1 1-(-1 • 0):-1 0-(-1 • 0):-1 1-(0 • 0):-1 0-(1 • 0):-1
-4 : -1 -2 : -1 -1 : -1 -1 : -1 -1 : -1 0 : -1 1 : -1
0-(-4 • 2):-1 6-(-2 • 2):-1 8-(-1 • 2):-1 1-(-1 • 2):-1 2-(-1 • 2):-1 0-(0 • 2):-1 0-(1 • 2):-1

1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 1-ая строка, а переменную x5 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2).

Базис B x1 x2 x3 x4 x5 x6
x5 -3 -1 -2 1 0 1 0
x4 4 2 1 1 1 0 -1
F(X0) -8 2 6 -1 0 0 2
θ 2 : (-1) = -2 6 : (-2) = -3 - - - -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6
x2 3/2 1/2 1 -1/2 0 -1/2 0
x4 5/2 3/2 0 3/2 1 1/2 -1
F(X1) -17 -1 0 2 0 3 2

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6
-3 : -2 -1 : -2 -2 : -2 1 : -2 0 : -2 1 : -2 0 : -2
4-(-3 • 1):-2 2-(-1 • 1):-2 1-(-2 • 1):-2 1-(1 • 1):-2 1-(0 • 1):-2 0-(1 • 1):-2 -1-(0 • 1):-2
-8-(-3 • 6):-2 2-(-1 • 6):-2 6-(-2 • 6):-2 -1-(1 • 6):-2 0-(0 • 6):-2 0-(1 • 6):-2 2-(0 • 6):-2

В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (11/2 : 1/2 , 21/2 : 11/2 ) = 12/3
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (11/2) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 x5 x6 min
x2 11/2 1/2 1 -1/2 0 -1/2 0 3
x4 21/2 11/2 0 11/2 1 1/2 -1 12/3
F(X1) -17 -1 0 2 0 3 2 0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=11/2
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (11/2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6
11/2-(21/21/2):11/2 1/2-(11/21/2):11/2 1-(0 • 1/2):11/2 -1/2-(11/21/2):11/2 0-(1 • 1/2):11/2 -1/2-(1/21/2):11/2 0-(-1 • 1/2):11/2
21/2 : 11/2 11/2 : 11/2 0 : 11/2 11/2 : 11/2 1 : 11/2 1/2 : 11/2 -1 : 11/2
-17-(21/2 • -1):11/2 -1-(11/2 • -1):11/2 0-(0 • -1):11/2 2-(11/2 • -1):11/2 0-(1 • -1):11/2 3-(1/2 • -1):11/2 2-(-1 • -1):11/2


Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4 x5 x6
x2 2/3 0 1 -1 -1/3 -2/3 1/3
x1 5/3 1 0 1 2/3 1/3 -2/3
F(X1) -46/3 0 0 3 2/3 10/3 4/3

1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4 x5 x6
x2 2/3 0 1 -1 -1/3 -2/3 1/3
x1 5/3 1 0 1 2/3 1/3 -2/3
F(X2) -46/3 0 0 3 2/3 10/3 4/3

Оптимальный план можно записать так:
x2 = 2/3
x1 = 12/3
F(X) = 8•2/3 + 6•12/3 = 151/3
Метод Гомори.
В полученном оптимальном плане переменная x1 имеет дробную часть числа. Дополнительное ограничение составляем по строке, соответствующей переменной x1.

После преобразования, умножения его на (-1) и введения дополнительной переменной х7 получим дополнительное ограничение в виде
-x3-2/3x4-1/3x5-11/3x6+x7 = -2/3

Базис B x1 x2 x3 x4 x5 x6 x7
x2 2/3 0 1 -1 -1/3 -2/3 1/3 0
x1 5/3 1 0 1 2/3 1/3 -2/3 0
x7 -2/3 0 0 -1 -2/3 -1/3 -4/3 1
F(X0) -46/3 0 0 3 2/3 10/3 4/3 0

1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 3-ая строка, а переменную x7 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 6-му столбцу, т.е. переменную x6 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-11/3).

Базис B x1 x2 x3 x4 x5 x6 x7
x2 2/3 0 1 -1 -1/3 -2/3 1/3 0
x1 12/3 1 0 1 2/3 1/3 -2/3 0
x7 -2/3 0 0 -1 -2/3 -1/3 -11/3 1
F(X0) -151/3 0 0 3 2/3 31/3 11/3 0
θ - - 3 : (-1) = -3 2/3 : (-2/3) = -1 31/3 : (-1/3) = -10 11/3 : (-11/3) = -1 -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6 x7
x2 1/2 0 1 -5/4 -1/2 -3/4 0 1/4
x1 2 1 0 3/2 1 1/2 0 -1/2
x6 1/2 0 0 3/4 1/2 1/4 1 -3/4
F(X0) -16 0 0 2 0 3 0 1

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6 x 7
2/3-(-2/31/3):-11/3 0-(0 • 1/3):-11/3 1-(0 • 1/3):-11/3 -1-(-1 • 1/3):-11/3 -1/3-(-2/31/3):-11/3 -2/3-(-1/31/3):-11/3 1/3-(-11/31/3):-11/3 0-(1 • 1/3):-11/3
12/3-(-2/3-2/3):-11/3 1-(0 • -2/3):-11/3 0-(0 • -2/3):-11/3 1-(-1 • -2/3):-11/3 2/3-(-2/3-2/3):-11/3 1/3-(-1/3-2/3):-11/3 -2/3-(-11/3-2/3):-11/3 0-(1 • -2/3):-11/3
-2/3 : -11/3 0 : -11/3 0 : -11/3 -1 : -11/3 -2/3 : -11/3 -1/3 : -11/3 -11/3 : -11/3 1 : -11/3
-151/3-(-2/3 • 11/3):-11/3 0-(0 • 11/3):-11/3 0-(0 • 11/3):-11/3 3-(-1 • 11/3):-11/3 2/3-(-2/3 • 11/3):-11/3 31/3-(-1/3 • 11/3):-11/3 11/3-(-11/3 • 11/3):-11/3 0-(1 • 11/3):-11/3

Оптимальный целочисленный план можно записать так:
x2 = 1/2
x1 = 2
x6 = 1/2
F(X) = 16
Открыть диалог Discus Помощь в решении контрольных