Пример решения методом Гомори

Задание. Решить целочисленную задачу линейного программирования, используя метод Гомори: 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

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

загрузка...