Контрольная работа: Розв`язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплек

Перепишемо ЗЛП, помноживши першу нерівність на -1:

F = x₁ + x₂ → max

-x₁ + x₂ ≤ 6

3x₁ + 4x₂ ≤ 26

2x₁ - x₂ ≤ 10

x₁ ≥ 0, x₂ ≥ 0

Двоїста задача записується у вигляді:

F^* = 6y₁ + 26y₂ + 10y₃ → min

-1y₁ + 3y₂ + 2y₃ ≥ 1

1y₁ + 4y₂ - 1y₃ ≥ 1

y₁ ≥ 0, y₂ ≥ 0, y₃ ≥ 0

Зведемовихіднузадачудоканонічноїформи [5, с. 14]. Для цього добавимо невід'ємні величини x₃ , x₄ , x₅ , щоб нерівності перетворити в рівняння:

F - x₁ - x₂ → max

-x₁ + x₂ + x₃ = 6

3x₁ + 4x₂ + x₄ = 26

2x₁ - x₂ + x₅ = 10

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0, x₅ ≥ 0

Розв'яжемо дану задачу симплекс-методом [5, с. 18]. Заповнюємо симплекс-таблицю початковими значеннями, вибираємо стовпець (x₁ ) з першим від'ємним значенням (-1) в останньому рядку, вибираємо рядок (x₅ ) з найменшим значенням b_i /x_i (5) і виділяємо розв'язувальний елемент (2):

xб	b	x1	x2	x3	x4	x5	bi /xi
x3	6	-1	1	1	0	0	—
x4	26	3	4	0	1	0	26/3
x5	10	2	-1	0	0	1	5 (min)
Δ	0	-1	-1	0	0	0

Вводимо в базис x₁ замість x₅ і перераховуємо таблицю. Вибираємо стовпець (x₂ ) з єдиним від'ємним значенням (-3/2) в останньому рядку, вибираємо рядок (x₄ ) з найменшим значенням b_i /x_i (2) і виділяємо розв'язувальний елемент (11/2):

xб	b	x1	x2	x3	x4	x5	bi /xi
x3	11	0	1/2	1	0	1/2	22
x4	11	0	11/2	0	1	-3/2	2 (min)
x1	5	1	-1/2	0	0	1/2	—
Δ	5	0	-3/2	0	0	1/2

Вводимо в базис x₂ замість x₄ і перераховуємо таблицю:

xб	b	x1	x2	x3	x4	x5	bi /xi
x3	10	0	0	1	-1/11	7/11	—
x2	2	0	1	0	2/11	-3/11	—
x1	6	1	0	0	1/11	4/11	—
Δ	8	0	0	0	3/11	1/11

В останньому рядку не залишилося від'ємних величин, тому стовбець b містить рішення вихідної задачі — максимум функції F:

x₁ = 6

x₂ = 2

F_max = 8

Запишемо рішення двоїстої задачі з останнього рядка останньої симплекс-таблиці:

y₁ = 0

y₂ = 3/11

y₃ = 1/11

F^* _min = 8