Задача ЭМММ

     Задача 29

     Решить  симплексным методом, контролируя  вычисления

     2х₃ ≤ 4,

     -х₁ – х₂ ≤ -4,

     х₁ – х₂ + 2х₃ ≤ 0,

     -х₁ – х₂ ≤ -2,

     х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0,

     -2х₁ – х₂ + 10х₃ → max. 

     Решение

     Составим  исходную систему уравнений:

     y₁ = -2х₃ + 4,

     y₂ = х₁ + х₂ – 4,

     y₃ = -х₁ + х₂ – 2х₃,

     y₄ = х₁ + х₂ – 2.

     Z = -2х₁ – х₂ + 10х₃ → max.

     Двойственная  задача:

     υ₁ = -u₂ + u₃ – u₄ + 2,

     υ₂ = -u₂ – u₃ – u₄ + 1,

     υ₃ = 2u₁ + 2u₃ – 10.

     ω = 4u₁ – 4u₂ – 2u₄ → min

     Составим  симплекс-таблицу задачи

0	-х1, v1	-х2, v2	-х3, v3	ω = 1
y1, u1	0	0	2	4
y2, u2	-1	-1	0	-4
y3, u3	1	-1	2	0
y4, u4	-1	-1	0	-2
Z = 1	2	1	-10	0

 

     Начальное прямое и двойственное решения:

     Х = (0, 0, 0), Y = (4, -4, 0, -2), z = 0,

     V = (2, 1, -10), U = (0, 0, 0, 0), ω = 0.

     Разрешающая строка – четвертая, в последнем столбце содержится отрицательный элемент.

     Выбираем  разрешающим второй столбец.

     Разрешающий элемент: α₄₂ = -1.

     В результате преобразований получим  следующую таблицу:

1	-х1, v1	-у4, u4	-х3, v3	ω = 1
y1, u1	0	0	2	4
y2, u2	0	-1	0	-2
y3, u3	2	-1	2	2
x2, v2	1	-1	0	2
Z = 1	1	1	-10	-2

 

     Новые решения прямой и двойственной задачи:

     Х = (0, 2, 0), Y = (4, -2, 2, 0), z = -2,

     V = (1, 0, -10), U = (0, 0, 0, 1), ω = -2.

     Проверка  решения:

     

Прямого 4 = -2*0 + 4 -2 = 0 + 2 - 4 2 = -0 + 2 – 2*0 0 = 0 + 2 – 2

Двойственного 1 = -0 + 0 – 1 + 2 0 = -0 – 0 –  1 + 1 -10 = 2*0 + 2*0 – 10

 

     В качестве разрешающих выбираем второй столбец, вторую строку.

     В результате преобразований получим  следующую таблицу:

2	-х1, v1	-у2, u2	-х3, v3	ω = 1
y1, u1	0	0	2	4
y4, u4	0	-1	0	2
y3, u3	2	-1	2	4
x2, v2	1	-1	0	4
Z = 1	1	1	-10	-4

 

     Новые решения прямой и двойственной задачи:

     Х = (0, 4, 0), Y = (4, 0, 4, 2), z = -4,

     V = (1, 0, -10), U = (0, 1, 0, 0), ω = -4.

     Проверка  решения:

     

Прямого 4 = -2*0 + 4 0 = 0 + 4 - 4 4 = -0 + 4 – 2*0 2 = 0 + 4 – 2

Двойственного 1 = -1 + 0 – 0 + 2 0 = -1 – 0 – 0 + 1 -10 = 2*0 + 2*0 – 10

 

     Так как z-строка содержит отрицательный элемент, то полученное решение не является оптимальным, его можно улучшить.

     В качестве разрешающих выбираем первую строку, третий столбец.

3	-х1, v1	-у2, u2	-х3, v3	ω = 1
y1, u1	0	0	½	2
y4, u4	0	-1	0	2
y3, u3	2	-1	-1	0
x2, v2	1	-1	0	4
Z = 1	1	1	5	16

 

     Новые решения прямой и двойственной задачи:

     Х = (0, 4, 2), Y = (0, 0, 0, 2), z = 16,

     V = (1, 0, 0), U = (5, 1, 0, 0), ω = 16.

     Прямое  и двойственное решение оптимальны (нет отрицательных элементов). Проверим их.

     Проверка  решения:

     

Прямого 0 = -2*2 + 4 0 = 0 + 4 - 4 0 = -0 + 4 – 2*2 2 = 0 + 4 – 2

Двойственного 1 = -1 + 0 – 0 + 2 0 = -1 – 0 – 0 + 1 0 = 2*5 + 2*0 – 10

 

     Ответ: Х^* = (0, 4, 2), U^* = (5, 1, 0, 0), z = ω = 16.