Метод отсечений Гомори. Пример решения

Решение находим с помощью онлайн сервиса Метод Гомори.
Этап 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)

Базис

B

x1

x2

x3

x4

x5

x3

38

2

11

1

0

0

x4

7

1

1

0

1

0

x5

5

4

-5

0

0

1

F(X0)

0

-1

-1

0

0

0


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

Базис

B

x1

x2

x3

x4

x5

min

x3

38

2

11

1

0

0

35/11

x4

7

1

1

0

1

0

7

x5

5

4

-5

0

0

1

-

F(X1)

0

-1

-1

0

0

0

0


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

Базис

B

x1

x2

x3

x4

x5

x2

35/11

2/11

1

1/11

0

0

x4

36/11

9/11

0

-1/11

1

0

x5

223/11

410/11

0

5/11

0

1

F(X1)

35/11

-9/11

0

1/11

0

0


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

Базис

B

x1

x2

x3

x4

x5

min

x2

35/11

2/11

1

1/11

0

0

19

x4

36/11

9/11

0

-1/11

1

0

41/3

x5

223/11

410/11

0

5/11

0

1

429/54

F(X2)

35/11

-9/11

0

1/11

0

0

0


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

Базис

B

x1

x2

x3

x4

x5

x2

22/3

0

1

1/9

-2/9

0

x1

41/3

1

0

-1/9

12/9

0

x5

1

0

0

1

-6

1

F(X2)

7

0

0

0

1

0


 
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:

Базис

B

x1

x2

x3

x4

x5

x2

22/3

0

1

1/9

-2/9

0

x1

41/3

1

0

-1/9

12/9

0

x5

1

0

0

1

-6

1

F(X3)

7

0

0

0

1

0


 
Оптимальный план можно записать так:
x2 = 22/3
x1 = 41/3
x5 = 1
F(X) = 1•22/3 + 1•41/3 = 7
 
В полученном оптимальном плане присутствуют дробные числа.
По 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).

Базис

B

x1

x2

x3

x4

x5

x6

x2

22/3

0

1

1/9

-2/9

0

0

x1

41/3

1

0

-1/9

12/9

0

0

x5

1

0

0

1

-6

1

0

x6

-2/3

0

0

-1/9

-7/9

0

1

F(X0)

-7

0

0

0

-1

0

0


 
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1/9).

Базис

B

x1

x2

x3

x4

x5

x6

x2

22/3

0

1

1/9

-2/9

0

0

x1

41/3

1

0

-1/9

12/9

0

0

x5

1

0

0

1

-6

1

0

x6

-2/3

0

0

-1/9

-7/9

0

1

F(X)

-7

0

0

0

-1

0

0

θ

0

 -

 -

0 : (-1/9) = 0

-1 : (-7/9) = 12/7

 -

 -


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

Базис

B

x1

x2

x3

x4

x5

x6

x2

2

0

1

0

-1

0

1

x1

5

1

0

0

2

0

-1

x5

-5

0

0

0

-13

1

9

x3

6

0

0

1

7

0

-9

F(X0)

-7

0

0

0

-1

0

0


 
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-13).

Базис

B

x1

x2

x3

x4

x5

x6

x2

2

0

1

0

-1

0

1

x1

5

1

0

0

2

0

-1

x5

-5

0

0

0

-13

1

9

x3

6

0

0

1

7

0

-9

F(X)

-7

0

0

0

-1

0

0

θ

0

 -

 -

 -

-1 : (-13) = 1/13

 -

 -


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

Базис

B

x1

x2

x3

x4

x5

x6

x2

25/13

0

1

0

0

-1/13

4/13

x1

43/13

1

0

0

0

2/13

5/13

x4

5/13

0

0

0

1

-1/13

-9/13

x3

34/13

0

0

1

0

7/13

-42/13

F(X1)

-68/13

0

0

0

0

-1/13

-9/13


 
 
В полученном оптимальном плане присутствуют дробные числа.
По 5-у уравнению с переменной x, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 8/13, составляем дополнительное ограничение:
q5 - q51•x1 - q52•x2 - q53•x3 - q54•x4 - q55•x5 - q56•x6≤0
q5 = b5 - [b5] = -68/13 - -6 = -8/13
q51 = a51 - [a51] = 0 - 0 = 0
q52 = a52 - [a52] = 0 - 0 = 0
q53 = a53 - [a53] = 0 - 0 = 0
q54 = a54 - [a54] = 0 - 0 = 0
q55 = a55 - [a55] = -1/13 + 1 = 12/13
q56 = a56 - [a56] = -9/13 + 1 = 4/13
Дополнительное ограничение имеет вид:
-8/13-12/13x5-4/13x6≤0
Преобразуем полученное неравенство в уравнение:
-8/13-12/13x5-4/13x6 + x7 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x2

25/13

0

1

0

0

-1/13

4/13

0

x1

43/13

1

0

0

0

2/13

5/13

0

x4

5/13

0

0

0

1

-1/13

-9/13

0

x3

34/13

0

0

1

0

7/13

-42/13

0

x7

8/13

0

0

0

0

-12/13

-4/13

1

F(X0)

-68/13

0

0

0

0

-1/13

-9/13

0


 
В полученном оптимальном плане присутствуют дробные числа.
По 5-у уравнению с переменной x7, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 8/13, составляем дополнительное ограничение:
q5 - q51•x1 - q52•x2 - q53•x3 - q54•x4 - q55•x5 - q56•x6 - q57•x7≤0
q5 = b5 - [b5] = 8/13 - 0 = 8/13
q51 = a51 - [a51] = 0 - 0 = 0
q52 = a52 - [a52] = 0 - 0 = 0
q53 = a53 - [a53] = 0 - 0 = 0
q54 = a54 - [a54] = 0 - 0 = 0
q55 = a55 - [a55] = -12/13 + 1 = 1/13
q56 = a56 - [a56] = -4/13 + 1 = 9/13
q57 = a57 - [a57] = 1 - 1 = 0
Дополнительное ограничение имеет вид:
8/13-1/13x5-9/13x6≤0
Преобразуем полученное неравенство в уравнение:
8/13-1/13x5-9/13x6 + x8 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x2

25/13

0

1

0

0

-1/13

4/13

0

0

x1

43/13

1

0

0

0

2/13

5/13

0

0

x4

5/13

0

0

0

1

-1/13

-9/13

0

0

x3

34/13

0

0

1

0

7/13

-42/13

0

0

x7

8/13

0

0

0

0

-12/13

-4/13

1

0

x8

-8/13

0

0

0

0

-1/13

-9/13

0

1

F(X0)

-68/13

0

0

0

0

-1/13

-9/13

0

0


 
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-9/13).

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x2

25/13

0

1

0

0

-1/13

4/13

0

0

x1

43/13

1

0

0

0

2/13

5/13

0

0

x4

5/13

0

0

0

1

-1/13

-9/13

0

0

x3

34/13

0

0

1

0

7/13

-42/13

0

0

x7

8/13

0

0

0

0

-12/13

-4/13

1

0

x8

-8/13

0

0

0

0

-1/13

-9/13

0

1

F(X)

-68/13

0

0

0

0

-1/13

-9/13

0

0

θ

0

 -

 -

 -

 -

-1/13 : (-1/13) = 1

-9/13 : (-9/13) = 1

 -

 -


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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x2

21/9

0

1

0

0

-1/9

0

0

4/9

x1

38/9

1

0

0

0

1/9

0

0

5/9

x4

1

0

0

0

1

0

0

0

-1

x3

7

0

0

1

0

1

0

0

-6

x7

8/9

0

0

0

0

-8/9

0

1

-4/9

x6

8/9

0

0

0

0

1/9

1

0

-14/9

F(X0)

-6

0

0

0

0

0

0

0

-1


 
В полученном оптимальном плане присутствуют дробные числа.
По 2-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 8/9, составляем дополнительное ограничение:
q2 - q21•x1 - q22•x2 - q23•x3 - q24•x4 - q25•x5 - q26•x6 - q27•x7 - q28•x8≤0
q2 = b2 - [b2] = 38/9 - 3 = 8/9
q21 = a21 - [a21] = 1 - 1 = 0
q22 = a22 - [a22] = 0 - 0 = 0
q23 = a23 - [a23] = 0 - 0 = 0
q24 = a24 - [a24] = 0 - 0 = 0
q25 = a25 - [a25] = 1/9 - 0 = 1/9
q26 = a26 - [a26] = 0 - 0 = 0
q27 = a27 - [a27] = 0 - 0 = 0
q28 = a28 - [a28] = 5/9 - 0 = 5/9
Дополнительное ограничение имеет вид:
8/9-1/9x5-5/9x8≤0
Преобразуем полученное неравенство в уравнение:
8/9-1/9x5-5/9x8 + x9 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x2

21/9

0

1

0

0

-1/9

0

0

4/9

0

x1

38/9

1

0

0

0

1/9

0

0

5/9

0

x4

1

0

0

0

1

0

0

0

-1

0

x3

7

0

0

1

0

1

0

0

-6

0

x7

8/9

0

0

0

0

-8/9

0

1

-4/9

0

x6

8/9

0

0

0

0

1/9

1

0

-14/9

0

x9

-8/9

0

0

0

0

-1/9

0

0

-5/9

1

F(X0)

-6

0

0

0

0

0

0

0

-1

0


 
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1/9).

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x2

21/9

0

1

0

0

-1/9

0

0

4/9

0

x1

38/9

1

0

0

0

1/9

0

0

5/9

0

x4

1

0

0

0

1

0

0

0

-1

0

x3

7

0

0

1

0

1

0

0

-6

0

x7

8/9

0

0

0

0

-8/9

0

1

-4/9

0

x6

8/9

0

0

0

0

1/9

1

0

-14/9

0

x9

-8/9

0

0

0

0

-1/9

0

0

-5/9

1

F(X)

-6

0

0

0

0

0

0

0

-1

0

θ

0

 -

 -

 -

 -

0 : (-1/9) = 0

 -

 -

-1 : (-5/9) = 14/5

 -


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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x2

3

0

1

0

0

0

0

0

1

-1

x1

3

1

0

0

0

0

0

0

0

1

x4

1

0

0

0

1

0

0

0

-1

0

x3

-1

0

0

1

0

0

0

0

-11

9

x7

8

0

0

0

0

0

0

1

4

-8

x6

0

0

0

0

0

0

1

0

-2

1

x5

8

0

0

0

0

1

0

0

5

-9

F(X0)

-6

0

0

0

0

0

0

0

-1

0


 
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-11).

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x2

3

0

1

0

0

0

0

0

1

-1

x1

3

1

0

0

0

0

0

0

0

1

x4

1

0

0

0

1

0

0

0

-1

0

x3

-1

0

0

1

0

0

0

0

-11

9

x7

8

0

0

0

0

0

0

1

4

-8

x6

0

0

0

0

0

0

1

0

-2

1

x5

8

0

0

0

0

1

0

0

5

-9

F(X)

-6

0

0

0

0

0

0

0

-1

0

θ

0

 -

 -

 -

 -

 -

 -

 -

-1 : (-11) = 1/11

 -


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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x2

210/11

0

1

1/11

0

0

0

0

0

-2/11

x1

3

1

0

0

0

0

0

0

0

1

x4

11/11

0

0

-1/11

1

0

0

0

0

-9/11

x8

1/11

0

0

-1/11

0

0

0

0

1

-9/11

x7

77/11

0

0

4/11

0

0

0

1

0

-48/11

x6

2/11

0

0

-2/11

0

0

1

0

0

-7/11

x5

76/11

0

0

5/11

0

1

0

0

0

-410/11

F(X1)

-510/11

0

0

-1/11

0

0

0

0

0

-9/11


 
В полученном оптимальном плане присутствуют дробные числа.
По 1-у уравнению с переменной x2, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 10/11, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5 - q16•x6 - q17•x7 - q18•x8 - q19•x9≤0
q1 = b1 - [b1] = 210/11 - 2 = 10/11
q11 = a11 - [a11] = 0 - 0 = 0
q12 = a12 - [a12] = 1 - 1 = 0
q13 = a13 - [a13] = 1/11 - 0 = 1/11
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] = 0 - 0 = 0
q19 = a19 - [a19] = -2/11 + 1 = 9/11
Дополнительное ограничение имеет вид:
10/11-1/11x3-9/11x9≤0
Преобразуем полученное неравенство в уравнение:
10/11-1/11x3-9/11x9 + x10 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x2

210/11

0

1

1/11

0

0

0

0

0

-2/11

0

x1

3

1

0

0

0

0

0

0

0

1

0

x4

11/11

0

0

-1/11

1

0

0

0

0

-9/11

0

x8

1/11

0

0

-1/11

0

0

0

0

1

-9/11

0

x7

77/11

0

0

4/11

0

0

0

1

0

-48/11

0

x6

2/11

0

0

-2/11

0

0

1

0

0

-7/11

0

x5

76/11

0

0

5/11

0

1

0

0

0

-410/11

0

x10

-10/11

0

0

-1/11

0

0

0

0

0

-9/11

1

F(X0)

-510/11

0

0

-1/11

0

0

0

0

0

-9/11

0


 
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-9/11).

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x2

210/11

0

1

1/11

0

0

0

0

0

-2/11

0

x1

3

1

0

0

0

0

0

0

0

1

0

x4

11/11

0

0

-1/11

1

0

0

0

0

-9/11

0

x8

1/11

0

0

-1/11

0

0

0

0

1

-9/11

0

x7

77/11

0

0

4/11

0

0

0

1

0

-48/11

0

x6

2/11

0

0

-2/11

0

0

1

0

0

-7/11

0

x5

76/11

0

0

5/11

0

1

0

0

0

-410/11

0

x10

-10/11

0

0

-1/11

0

0

0

0

0

-9/11

1

F(X)

-510/11

0

0

-1/11

0

0

0

0

0

-9/11

0

θ

0

 -

 -

-1/11 : (-1/11) = 1

 -

 -

 -

 -

 -

-9/11 : (-9/11) = 1

 -


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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x2

31/9

0

1

1/9

0

0

0

0

0

0

-2/9

x1

18/9

1

0

-1/9

0

0

0

0

0

0

12/9

x4

2

0

0

0

1

0

0

0

0

0

-1

x8

1

0

0

0

0

0

0

0

1

0

-1

x7

128/9

0

0

8/9

0

0

0

1

0

0

-57/9

x6

8/9

0

0

-1/9

0

0

1

0

0

0

-7/9

x5

13

0

0

1

0

1

0

0

0

0

-6

x9

11/9

0

0

1/9

0

0

0

0

0

1

-12/9

F(X0)

-5

0

0

0

0

0

0

0

0

0

-1


 
В полученном оптимальном плане присутствуют дробные числа.
По 2-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 8/9, составляем дополнительное ограничение:
q2 - q21•x1 - q22•x2 - q23•x3 - q24•x4 - q25•x5 - q26•x6 - q27•x7 - q28•x8 - q29•x9 - q210•x10≤0
q2 = b2 - [b2] = 18/9 - 1 = 8/9
q21 = a21 - [a21] = 1 - 1 = 0
q22 = a22 - [a22] = 0 - 0 = 0
q23 = a23 - [a23] = -1/9 + 1 = 8/9
q24 = a24 - [a24] = 0 - 0 = 0
q25 = a25 - [a25] = 0 - 0 = 0
q26 = a26 - [a26] = 0 - 0 = 0
q27 = a27 - [a27] = 0 - 0 = 0
q28 = a28 - [a28] = 0 - 0 = 0
q29 = a29 - [a29] = 0 - 0 = 0
q210 = a210 - [a210] = 12/9 - 1 = 2/9
Дополнительное ограничение имеет вид:
8/9-8/9x3-2/9x10≤0
Преобразуем полученное неравенство в уравнение:
8/9-8/9x3-2/9x10 + x11 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x2

31/9

0

1

1/9

0

0

0

0

0

0

-2/9

0

x1

18/9

1

0

-1/9

0

0

0

0

0

0

12/9

0

x4

2

0

0

0

1

0

0

0

0

0

-1

0

x8

1

0

0

0

0

0

0

0

1

0

-1

0

x7

128/9

0

0

8/9

0

0

0

1

0

0

-57/9

0

x6

8/9

0

0

-1/9

0

0

1

0

0

0

-7/9

0

x5

13

0

0

1

0

1

0

0

0

0

-6

0

x9

11/9

0

0

1/9

0

0

0

0

0

1

-12/9

0

x11

-8/9

0

0

-8/9

0

0

0

0

0

0

-2/9

1

F(X0)

-5

0

0

0

0

0

0

0

0

0

-1

0


 
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-8/9).

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x2

31/9

0

1

1/9

0

0

0

0

0

0

-2/9

0

x1

18/9

1

0

-1/9

0

0

0

0

0

0

12/9

0

x4

2

0

0

0

1

0

0

0

0

0

-1

0

x8

1

0

0

0

0

0

0

0

1

0

-1

0

x7

128/9

0

0

8/9

0

0

0

1

0

0

-57/9

0

x6

8/9

0

0

-1/9

0

0

1

0

0

0

-7/9

0

x5

13

0

0

1

0

1

0

0

0

0

-6

0

x9

11/9

0

0

1/9

0

0

0

0

0

1

-12/9

0

x11

-8/9

0

0

-8/9

0

0

0

0

0

0

-2/9

1

F(X)

-5

0

0

0

0

0

0

0

0

0

-1

0

θ

0

 -

 -

0 : (-8/9) = 0

 -

 -

 -

 -

 -

 -

-1 : (-2/9) = 41/2

 -


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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x2

3

0

1

0

0

0

0

0

0

0

-1/4

1/8

x1

2

1

0

0

0

0

0

0

0

0

11/4

-1/8

x4

2

0

0

0

1

0

0

0

0

0

-1

0

x8

1

0

0

0

0

0

0

0

1

0

-1

0

x7

12

0

0

0

0

0

0

1

0

0

-6

1

x6

1

0

0

0

0

0

1

0

0

0

-3/4

-1/8

x5

12

0

0

0

0

1

0

0

0

0

-61/4

11/8

x9

1

0

0

0

0

0

0

0

0

1

-11/4

1/8

x3

1

0

0

1

0

0

0

0

0

0

1/4

-11/8

F(X0)

-5

0

0

0

0

0

0

0

0

0

-1

0

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

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

загрузка...