Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

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

Общая задача линейного дискретного целочисленного программирования имеет вид:
(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

Перейти к онлайн решению

Пример №2. Решить методом отсечений следующую целочисленную задачу ЛП:
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

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

Посмотреть все итерации

В полученном оптимальном плане присутствуют дробные числа. Определяем первое правильное отсечение.
По 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

Пример №3. Решить целочисленную задачу линейного программирования, используя метод Гомори: F(X) = 8x1 + 5x2
5x1 + 2x2≤20
x1 + x2≤6

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


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

План

Базис

B

x1

x2

x3

x4

0

x3

20

5

2

1

0


x4

6

1

1

0

1

Индексная строка

F(X0)

0

-8

-5

0

0

Посмотреть все итерации
Оптимальный план можно записать так:
x1 = 22/3, x2 = 31/3. F(X) = 8•22/3 + 5•31/3 = 38

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


План

Базис

B

x1

x2

x3

x4

x5

0

x1

22/3

1

0

1/3

-2/3

0


x2

31/3

0

1

-1/3

12/3

0


x5

-2/3

0

0

-1/3

-1/3

1

Индексная строка

F(X0)

38

0

0

1

3

0

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

B

x 1

x 2

x 3

x 4

x 5

22/3-(-2/31/3):-1/3

1-(0 • 1/3):-1/3

0-(0 • 1/3):-1/3

1/3-(-1/31/3):-1/3

-2/3-(-1/31/3):-1/3

0-(1 • 1/3):-1/3

31/3-(-2/3-1/3):-1/3

0-(0 • -1/3):-1/3

1-(0 • -1/3):-1/3

-1/3-(-1/3-1/3):-1/3

12/3-(-1/3-1/3):-1/3

0-(1 • -1/3):-1/3

-2/3 : -1/3

0 : -1/3

0 : -1/3

-1/3 : -1/3

-1/3 : -1/3

1 : -1/3

38-(-2/3 • 1):-1/3

0-(0 • 1):-1/3

0-(0 • 1):-1/3

1-(-1/3 • 1):-1/3

3-(-1/3 • 1):-1/3

0-(1 • 1):-1/3


План

Базис

B

x1

x2

x3

x4

x5

0

x1

2

1

0

0

-1

1


x2

4

0

1

0

2

-1


x3

2

0

0

[

1

-3

Индексная строка

F(X0)

36

0

0

[

2

3

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

Пример №4. Найти полностью целочисленное решение следующих задач, сопровождая (где это возможно) решение графической иллюстрацией. Предполагается, что все Xk≥0.

Пример №5. Решить целочисленную задачу линейного программирования, используя метод Гомори: F(X) = x1 + 2x2
4x1 + 3x2≤24
-x1 + x2≤3

Решение находим с помощью сервиса Метод Гомори (случай целочисленного решения).
Этап I. Решим прямую задачу линейного программирования симплекс-методом.
Определим максимальное значение целевой функции F(X) = x1 + 2x2 при следующих условиях-ограничений.
4x1 + 3x2≤24
-x1 + x2≤3

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
4x1 + 3x2 + 1x3 + 0x4 = 24
-1x1 + 1x2 + 0x3 + 1x4 = 3
Введем новую переменную x0 = x1 + 2x2.
Выразим базисные переменные <3, 4> через небазисные.
x0 = 0+x1+2x2
x3 = 24-4x1-3x2
x4 = 3+x1-x2

Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
x0 = 0+x1+2x2
x3 = 24-4x1-3x2
x4 = 3+x1-x2
В качестве новой переменной выбираем x2.

Вычислим значения D2 по всем уравнениям для этой переменной.
и из них выберем наименьшее:
min (24 : 3 , 3 : 1 ) = 3
Вместо переменной x4 в план войдет переменная x2.
Выразим переменную x2 через x4 и подставим во все выражения.
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 6+3x1-2x4
x3 = 15-7x1+3x4
x2 = 3+x1-x4

Полагая небазисные переменные x = (3, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-3, 0, 0, 2), x0 = 6
x0 = 6+3x1-2x4
x3 = 15-7x1+3x4
x2 = 3+x1-x4
В качестве новой переменной выбираем x1.
Вычислим значения D1 по всем уравнениям для этой переменной.
и из них выберем наименьшее:
min (15 : 7 , - ) = 21/7
Вместо переменной x3 в план войдет переменная x1.
Выразим переменную x1 через x3 и подставим во все выражения.

После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 123/7-3/7x3-5/7x4
x1 = 21/7-1/7x3+3/7x4
x2 = 51/7-1/7x3-4/7x4

Полагая небазисные переменные x = (1, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 3/7, 5/7), x0 = 123/7
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 123/7-3/7x3-5/7x4
x1 = 21/7-1/7x3+3/7x4
x2 = 51/7-1/7x3-4/7x4

Оптимальный план можно записать так:
x1 = 21/7, x2 = 51/7
F(X) = 1•21/7 + 2•51/7 = 123/7

Этап II. В полученном оптимальном плане присутствуют дробные числа. Применяем алгоритм отсечений Гомори.
По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 1/7, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4≤0
q1 = b1 - [b1] = 21/7 - 2 = 1/7
q11 = a11 - [a11] = 1 - 1 = 0
q12 = a12 - [a12] = 0 - 0 = 0
q13 = a13 - [a13] = 1/7 - 0 = 1/7
q14 = a14 - [a14] = -3/7 + 1 = 4/7

Дополнительное ограничение имеет вид:
1/7-1/7x3-4/7x4≤0
Преобразуем полученное неравенство в уравнение:
1/7-1/7x3-4/7x4 + x5 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.


План

Базис

B

x1

x2

x3

x4

x5

0

x1

21/7

1

0

1/7

-3/7

0


x2

51/7

0

1

1/7

4/7

0


x5

-1/7

0

0

-1/7

-4/7

1

Индексная строка

F(X0)

123/7

0

0

3/7

5/7

0

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

B

x1

x2

x3

x4

x5

21/7-(-1/7-3/7):-4/7

1-(0 • -3/7):-4/7

0-(0 • -3/7):-4/7

1/7-(-1/7-3/7):-4/7

-3/7-(-4/7-3/7):-4/7

0-(1 • -3/7):-4/7

51/7-(-1/74/7):-4/7

0-(0 • 4/7):-4/7

1-(0 • 4/7):-4/7

1/7-(-1/74/7):-4/7

4/7-(-4/74/7):-4/7

0-(1 • 4/7):-4/7

-1/7 : -4/7

0 : -4/7

0 : -4/7

-1/7 : -4/7

-4/7 : -4/7

1 : -4/7

123/7-(-1/75/7):-4/7

0-(0 • 5/7):-4/7

0-(0 • 5/7):-4/7

3/7-(-1/75/7):-4/7

5/7-(-4/75/7):-4/7

0-(1 • 5/7):-4/7


План

Базис

B

x1

x2

x3

x4

x5

0

x1

21/4

1

0

1/4

0

-3/4


x2

5

0

1

0

0

1


x4

1/4

0

0

1/4

1

-13/4

Индексная строка

F(X0)

121/4

0

0

1/4

0

11/4

В полученном оптимальном плане присутствуют дробные числа.
По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 1/4, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5≤0
q1 = b1 - [b1] = 21/4 - 2 = 1/4
q11 = a11 - [a11] = 1 - 1 = 0
q12 = a12 - [a12] = 0 - 0 = 0
q13 = a13 - [a13] = 1/4 - 0 = 1/4
q14 = a14 - [a14] = 0 - 0 = 0
q15 = a15 - [a15] = -3/4 + 1 = 1/4

Дополнительное ограничение имеет вид:
1/4-1/4x3-1/4x5≤0
Преобразуем полученное неравенство в уравнение:
1/4-1/4x3-1/4x5 + x6 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.


План

Базис

B

x1

x2

x3

x4

x5

x6

0

x1

21/4

1

0

1/4

0

-3/4

0


x2

5

0

1

0

0

1

0


x4

1/4

0

0

1/4

1

-13/4

0


x6

-1/4

0

0

-1/4

0

-1/4

1

Индексная строка

F(X0)

121/4

0

0

1/4

0

11/4

0

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

B

x1

x2

x3

x4

x5

x6

21/4-(-1/41/4):-1/4

1-(0 • 1/4):-1/4

0-(0 • 1/4):-1/4

1/4-(-1/41/4):-1/4

0-(0 • 1/4):-1/4

-3/4-(-1/41/4):-1/4

0-(1 • 1/4):-1/4

5-(-1/4 • 0):-1/4

0-(0 • 0):-1/4

1-(0 • 0):-1/4

0-(-1/4 • 0):-1/4

0-(0 • 0):-1/4

1-(-1/4 • 0):-1/4

0-(1 • 0):-1/4

1/4-(-1/41/4):-1/4

0-(0 • 1/4):-1/4

0-(0 • 1/4):-1/4

1/4-(-1/41/4):-1/4

1-(0 • 1/4):-1/4

-13/4-(-1/41/4):-1/4

0-(1 • 1/4):-1/4

-1/4 : -1/4

0 : -1/4

0 : -1/4

-1/4 : -1/4

0 : -1/4

-1/4 : -1/4

1 : -1/4

121/4-(-1/41/4):-1/4

0-(0 • 1/4):-1/4

0-(0 • 1/4):-1/4

1/4-(-1/41/4):-1/4

0-(0 • 1/4):-1/4

11/4-(-1/41/4):-1/4

0-(1 • 1/4):-1/4


План

Базис

B

x1

x2

x3

x4

x5

x6

0

x1

2

1

0

0

0

-1

1


x2

5

0

1

0

0

1

0


x4

0

0

0

0

1

-2

1


x3

1

0

0

1

0

1

-4

Индексная строка

F(X0)

12

0

0

0

0

1

1

Решение получилось целочисленным. Оптимальный план можно записать так:
x1 = 2, x2 = 5, x3 = 1, x4 = 0
F(X) = 12

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

Пример №6. Решить следующие частично целочисленные задачи, сопровождая (где это возможно) решение графической иллюстрацией. Предполагается, что все Xj≥0, XXi≥0 – целочисленное. Решениенаходим с помощью онлайн сервиса Метод Гомори.
Этап 1. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = x1+ x2при следующих условиях-ограничений.
2x1+ 11x2≤38
x1+ x2≤7
4x1- 5x2≤5
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
2x1+ 11x2+ 1x3+ 0x4+ 0x5= 38
1x1+ 1x2+ 0x3+ 1x4+ 0x5= 7
4x1-5x2+ 0x3+ 0x4+ 1x5= 5
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменныеравны 0, получим первый опорный план:
X1 = (0,0,38,7,5)

БазисBx1x2x3x4x5
x338211100
x4711010
x554-5001
F(X0)0-1-1000
Переходим к основному алгоритму симплекс-метода.

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

БазисBx1x2x3x4x5x6
x222/3011/9-2/900
x141/310-1/912/900
x51001-610
x6-2/300-1/9-7/901
F(X0)-7000-100


План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1/9).
БазисBx1x2x3x4x5x6
x222/3011/9-2/900
x141/310-1/912/900
x51001-610
x6-2/300-1/9-7/901
F(X)-7000-100
θ0 - -0 : (-1/9) = 0-1 : (-7/9) = 12/7 - -


Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
БазисBx1x2x3x4x5x6
x22010-101
x1510020-1
x5-5000-1319
x3600170-9
F(X0)-7000-100
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-13).
БазисBx1x2x3x4x5x6
x22010-101
x1510020-1
x5-5000-1319
x3600170-9
F(X)-7000-100
θ0 - - --1 : (-13) =1/13 - -

Посмотреть все итерации

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

Профессии будущего
РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса
Подробнее
Налоговый вычет на обучение
√ 120 тыс. руб. - максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя
Подробнее
Требуются авторы студенческих работ!
  • регулярный поток заказов;
  • стабильный доход
Подробнее
Курсовые на заказ