Метод отсечения. Алгоритм Гомори

Общая задача линейного дискретного целочисленного программирования имеет вид:
(4.1)
(4.2)
xj ≥ 0 , j = 1,..,n (4.3)
xj– целые,  j = 1,..,n (4.4)
Задача (4.1) – (4.4)  называется полностью целочисленной задачей линейного программирования, т.к. на все переменные положено условие целочисленности (ограничение 4.4). Когда это условие относится лишь к некоторым переменным, задача называется частично целочисленной.
Пусть дана задача полностью целочисленного линейного программирования (4.1) – (4.4). Алгоритм метода отсечений состоит из следующих этапов:
1) решается ЗЛП (4.1) – (4.3) с отброшенными условием целочисленности (4.4); если она не разрешима, то задача (4.1) –(4.4) тоже решения не имеет;
2) если условие целочисленности выполняется по всем переменным, то найденное решение есть решение задачи (4.1) –(4.4);
3) иначе строится дополнительное отсекающее ограничение, включается в систему ограничений (4.2) – (4.3) и на этап 1.
Для решения полностью целочисленной задачи ЛП Гомори предложено делать каждый раз на этапе 3 дополнительное ограничение для нецелой переменной с наибольшей дробной частью.
Предположим, что задача с отброшенным условием целочисленности решена. Рассмотрим i-ю строку оптимальной симплексной таблицы, которой соответствует нецелое решение β i базисной переменной xi Пусть R – множество индексов j, которые соответствуют небазисным переменным. Тогда переменная xi может быть выражена через небазисные переменные xj:
 β i – нецелое.                     (4.5)
Обозначим наибольшую целую часть числа a, его не превосходящую, через [a], ( a≥[a]), а дробную положительную часть – через {a} Очевидно a = [a] + {a}. Например, если  a=4,7 то [a] = 4, {a} = 0,7,  если a =-8,6, то [a] = -9, {a} = 0,4.
Выразим базисную переменную xi в (4.5) в виде суммы целой и дробной частей.

.(4.6)
Выражение в левых круглых скобках (4.6) целое число, и чтобы xj было целым, необходимо, чтобы выражение в правых круглых скобках (4.6) тоже было целым. Когда выражение будет целым? Так как 0 ≤ {βi}≤1, а  то Li будет целым числом, если   т.е.
(4.7)
Соотношение (4.7) определяет правильное отсечение Гомори.
Задача (4.1) – (4.4) не будет иметь полностью целочисленного решения, если встретится в симплекс-таблице уравнение такое, что βi дробное число, а αij –целые.

Пример решения методом Гомори.
Решить задачу ЛП max: Z = 3 x1 + x 2
при ограничениях: 3x1 – 2x2 ≤3
-5 x1 – 4x 2 ≤ -10;
2 x1 + x 2 ≤ 5;
x1, x 2 ≥ 0
x1, x 2 – целые.
Без учета целочисленности оптимальной симплекс-таблицей будет следующая табл. 4.1.

Рис. - Геометрическая интерпретация отсечения Гомори
Решим прямую задачу линейного программирования симплексным методом, с использованием калькулятора.
Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).
Определим максимальное значение целевой функции F(X) = 3x1 + x2 при следующих условиях-ограничений.
3x1 - 2x2≤3
5x1 + 4x2≥10
2x1 + x2≤5
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
3x1-2x2 + 1x3 + 0x4 + 0x5 = 3
5x1 + 4x2 + 0x3-1x4 + 0x5 = 10
2x1 + 1x2 + 0x3 + 0x4 + 1x5 = 5
Введем искусственные переменные x.
3x1-2x2 + 1x3 + 0x4 + 0x5 + 0x6 = 3
5x1 + 4x2 + 0x3-1x4 + 0x5 + 1x6= 10
2x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6= 5
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 3x1+x2 - Mx6 => max
Из уравнений выражаем искусственные переменные:
x6 = 10-5x1-4x2+x4
которые подставим в целевую функцию:
F(X) = (3+5M)x1+(1+4M)x2+(-1M)x4+(-10M) => max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных:
x3, x6, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,3,0,5,10)

План Базис B x1 x2 x3 x4 x5 x6
0 x3 3 3 -2 1 0 0 0
x6 10 5 4 0 -1 0 1
x5 5 2 1 0 0 1 0
Индексная строка F(X0) -10M -3-5M -1-4M 0 1M 0 0

Переходим к основному алгоритму симплекс-метода.

План Базис B x1 x2 x3 x4 x5 x6 min
1 x3 3 3 -2 1 0 0 0 1
x6 10 5 4 0 -1 0 1 2
x5 5 2 1 0 0 1 0 21/2
Индексная строка F(X1) -10M -3-5M -1-4M 0 1M 0 0 0


Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее:
min (3 : 3 , 10 : 5 , 5 : 2 ) = 1
Следовательно, 1-ая строка является ведущей.

План Базис B x1 x2 x3 x4 x5 x6 min
2 x1 1 1 -2 /3 1 /3 0 0 0 -
x6 5 0 71/3 -12/3 -1 0 1 15 /22
x5 3 0 21/3 -2 /3 0 1 0 12/7
Индексная строка F(X2) 3-5M 0 -3-71/3M 1+12/3M 1M 0 0 0


Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления:
и из них выберем наименьшее:
min (- , 5 : 71/3 , 3 : 21/3 ) = 15/22
Следовательно, 2-ая строка является ведущей.

План Базис B x1 x2 x3 x4 x5 x6 min
3 x1 15/11 1 0 2 /11 -1 /11 0 1 /11 -
x2 15 /22 0 1 -5 /22 -3 /22 0 3 /22 -
x5 19/22 0 0 -3 /22 7 /22 1 -7 /22 43/7
Индексная строка F(X3) 51/22 0 0 7 /22 -9 /22 0 9 /22+1M 0


Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления:
и из них выберем наименьшее:
min (- , - , 19/22 : 7/22 ) = 43/7
Следовательно, 3-ая строка является ведущей.
Конец итераций: найден оптимальный план
Окончательный вариант симплекс-таблицы:

План Базис B x1 x2 x3 x4 x5 x6
4 x1 16/7 1 0 1 /7 0 2 /7 0
x2 12/7 0 1 -2 /7 0 3 /7 0
x4 43/7 0 0 -3 /7 1 31/7 -1
Индексная строка F(X4) 66/7 0 0 1 /7 0 12/7 1M


Оптимальный план можно записать так:
x1 = 16/7
x2 = 12/7
x4 = 43/7
F(X) = 3•16/7 + 1•12/7 = 66/7
В полученном оптимальном плане присутствуют дробные числа.
По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 6/7, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5 - q16•x6≤0
q1 = b1 - [b1] = 16/7 - 1 = 6/7
q11 = a11 - [a11] = 1 - 1 = 0
q12 = a12 - [a12] = 0 - 0 = 0
q13 = a13 - [a13] = 1/7 - 0 = 1/7
q14 = a14 - [a14] = 0 - 0 = 0
q15 = a15 - [a15] = 2/7 - 0 = 2/7
q16 = a16 - [a16] = 0 - 0 = 0
Дополнительное ограничение имеет вид:
6/7-1/7x3-2/7x5≤0
Преобразуем полученное неравенство в уравнение:
6/7-1/7x3-2/7x5+ x7 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

План Базис B x1 x2 x3 x4 x5 x6 x7
0 x1 16/7 1 0 1 /7 0 2 /7 0 0
x2 12/7 0 1 -2 /7 0 3 /7 0 0
x4 43/7 0 0 -3 /7 1 31/7 -1 0
x7 -6 /7 0 0 -1 /7 0 -2 /7 0 1
Индексная строка F(X0) -10M -3-5M -1-4M 0 1M 0 0 0


План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 4-ая строка, а переменную x7 следует вывести из базиса.
В строку θ заносим следующие величины:
[ - ; - ;1/7:-1/7; - ;12/7:-2/7; - ; - ;] = [ - ; -;-1; - ;-41/2; - ; - ;]
Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный -1/7.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6 x 7
16/7-(-6/71/7):-1/7 1-(0 • 1/7):-1/7 0-(0 • 1/7):-1/7 1 /7-(-1/71/7):-1/7 0-(0 • 1/7):-1/7 2 /7-(-2/71/7):-1/7 0-(0 • 1/7):-1/7 0-(1 • 1/7):-1/7
12/7-(-6/7-2/7):-1/7 0-(0 • -2/7):-1/7 1-(0 • -2/7):-1/7 -2 /7-(-1/7-2/7):-1/7 0-(0 • -2/7):-1/7 3 /7-(-2/7-2/7):-1/7 0-(0 • -2/7):-1/7 0-(1 • -2/7):-1/7
43/7-(-6/7-3/7):-1/7 0-(0 • -3/7):-1/7 0-(0 • -3/7):-1/7 -3 /7-(-1/7-3/7):-1/7 1-(0 • -3/7):-1/7 31/7-(-2/7-3/7):-1/7 -1-(0 • -3/7):-1/7 0-(1 • -3/7):-1/7
-6 /7 : -1/7 0 : -1/7 0 : -1/7 -1 /7 : -1/7 0 : -1/7 -2 /7 : -1/7 0 : -1/7 1 : -1/7
66/7-(-6/71/7):-1/7 0-(0 • 1/7):-1/7 0-(0 • 1/7):-1/7 1 /7-(-1/71/7):-1/7 0-(0 • 1/7):-1/7 12/7-(-2/71/7):-1/7 10000-(0 • 1/7):-1/7 0-(1 • 1/7):-1/7


План Базис B x1 x2 x3 x4 x5 x6 x7
0 x1 1 1 0 0 0 0 0 1
x2 3 0 1 0 0 1 0 -2
x4 7 0 0 0 1 4 -1 -3
x3 6 0 0 1 0 2 0 -7
Индексная строка F(X0) -10M -3-5M -1-4M 0 1M 0 0 0


Решение получилось целочисленным. Нет необходимости применять метод Гомори.
Оптимальный целочисленный план можно записать так:
x1 = 1
x2 = 3
x4 = 7
x3 = 6
F(X) = 6

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

Пример. Решить методом отсечений следующую целочисленную задачу ЛП:
7x1 + 9x2 → max
- x1 + 3x2≤6
7x1 + x2≤35
- x1 + 3x2≤6
1 ≥ x2
1, x2 - целые

Записываем задачу L0(исходная задача без учета требования целочисленности):
7x1 + 9x2 → max
- x1 + 3x2≤6
7x1 + x2≤35
- x1 + 3x2≤6

Решаем задачу L0 симплекс-методом.
Определим максимальное значение целевой функции F(X) = 7x1 + 9x2 при следующих условиях-ограничений.
- x1 + 3x2≤6
7x1 + x2≤35
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4.
-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

В полученном оптимальном плане присутствуют дробные числа. Определяем первое правильное отсечение.
По 1-у уравнению с переменной x2, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 1/2, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4≤0
q1 = b1 - [b1] = 31/2 - 3 = 1/2
q11 = a11 - [a11] = 0 - 0 = 0
q12 = a12 - [a12] = 1 - 1 = 0
q13 = a13 - [a13] = 7/22 - 0 = 7/22
q14 = a14 - [a14] = 1/22 - 0 = 1/22
Дополнительное ограничение имеет вид:
1/2-7/22x3-1/22x4 ≤ 0
Преобразуем полученное неравенство в уравнение:
1/2-7/22x3-1/22x4 + x5 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование 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 • -26/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

В полученном оптимальном плане присутствуют дробные числа.
По 2-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 4/7, составляем дополнительное ограничение:
q2 - q21•x1 - q22•x2 - q23•x3 - q24•x4 - q25•x5≤0
q2 = b2 - [b2] = 44/7 - 4 = 4/7
q21 = a21 - [a21] = 1 - 1 = 0
q22 = a22 - [a22] = 0 - 0 = 0
q23 = a23 - [a23] = 0 - 0 = 0
q24 = a24 - [a24] = 1/7 - 0 = 1/7
q25 = a25 - [a25] = -1/7 + 1 = 6/7
Дополнительное ограничение имеет вид:
4/7-1/7x4-6/7x5 ≤ 0
Преобразуем полученное неравенство в уравнение:
4/7-1/7x4-6/7x5 + x6 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

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

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

Базис B x1 x2 x3 x4 x5 x6
x2 3 0 1 0 0 1 0
x1 44/7 1 0 0 1/7 -1/7 0
x3 14/7 0 0 1 1/7 -31/7 0
x6 -4/7 0 0 0 -1/7 -6/7 1
F(X0) -59 0 0 0 -1 -8 0
θ - - - -1 : (-1/7) = 7 -8 : (-6/7) = 91/3 -

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

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

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

B x 1 x 2 x 3 x 4 x 5 x 6
3-(-4/7 • 0):-1/7 0-(0 • 0):-1/7 1-(0 • 0):-1/7 0-(0 • 0):-1/7 0-(-1/7 • 0):-1/7 1-(-6/7 • 0):-1/7 0-(1 • 0):-1/7
44/7-(-4/71/7):-1/7 1-(0 • 1/7):-1/7 0-(0 • 1/7):-1/7 0-(0 • 1/7):-1/7 1/7-(-1/71/7):-1/7 -1/7-(-6/71/7):-1/7 0-(1 • 1/7):-1/7
14/7-(-4/71/7):-1/7 0-(0 • 1/7):-1/7 0-(0 • 1/7):-1/7 1-(0 • 1/7):-1/7 1/7-(-1/71/7):-1/7 -31/7-(-6/71/7):-1/7 0-(1 • 1/7):-1/7
-4/7 : -1/7 0 : -1/7 0 : -1/7 0 : -1/7 -1/7 : -1/7 -6/7 : -1/7 1 : -1/7
-59-(-4/7 • -1):-1/7 0-(0 • -1):-1/7 0-(0 • -1):-1/7 0-(0 • -1):-1/7 -1-(-1/7 • -1):-1/7 -8-(-6/7 • -1):-1/7 0-(1 • -1):-1/7

Решение получилось целочисленным. Нет необходимости применять метод Гомори.
Оптимальный целочисленный план можно записать так:
x2 = 3
x1 = 4
x3 = 1
x4 = 4
F(X) = 55
загрузка...