Вибрали генеральнeу строку, оскільки -10<0.
5/10>2/10, тому генеральна стовпчик береться по х1
Перерахуємо таблицю
x5 x2
x3 20 -1/2 11/2
х4 2 ½ -3/2
х1 5 -1/2 5/2
Lmin -5 ½ 1/2
Вибрали генеральний стовпчик, оскільки 1/2>0.
1/2>0, тому генеральна строка береться по х4
Перерахуємо таблицю
x4 x2
x3 22 1 4
х5 4 2 -3
х1 7 1 1
Lmin -7 -1 2
Вибрали генеральний стовпчик, оскільки 2>0.
7/1>22/4, тому генеральна строка береться по х3
Перерахуємо таблицю
x5 x3
x2 11/2 ¼ ¼
х4 41/2 11/4 ¾
х1 3/2 ¾ -1/4
Lmin -18 -3/2 -1/2
Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-18
a Lmax=18
x4=41/2
x2=11/2
x1=3/2
x3=x5=0
Задача З. Для заданої задачі лінійного програмування побудува¬ти двоїсту, розв'язати одну з пари двоїстих задач симплекс-методом і за її розв'язком знайти розв'язок двоїстої до неї:
Двоїста задача матиме вигляд
Розв’яжемо двоїсту задачу симплекс-методом
y1 y2 y3
y4 1 -1 1 -1
y5 3 3 1 2
Zmin 0 15 7 2
Вибрали генеральний стовпчик, оскільки 15>0.
3>0, тому генеральна строка береться по y5
Перерахуємо таблицю
y5 y2 y3
y4 2 1/3 4/3 -1/3
y1 1 1/3 1/3 2/3
Zmin -15 -5 2 -8
Вибрали генеральний стовпчик, оскільки 2>0.
6/4<3, тому генеральна строка береться по y4
Перерахуємо таблицю
y5 y4 y3
y2 3/2 ¼ ¾ -1/4
y1 ½ ¼ -1/4 ¾
Zmin -18 -11/2 -3/2 -15/2
Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто zmin=-18
a Zmax=18
y1=1/2
y2=3/2
y5=y4=y3=0
х1 х2 х3 х4 х5
у4 у5 у1 у2 у3
x1=3/2
x5=15/2
x2=11/2
x3=x4=0
L=18
Задача 4. Розв'язати методом потенціалів транспортну задачу:
Задача 5. Одним із методів відтинання розв'язати задачу цілочи¬слового програмування:
Розв’яжемо задачу симплекс-методом
x1 x2
x3 5 -1 1
x4 8 1 1
x5 -2 1 -2
Lmin 0 -2 3
Вибрали генеральну строку, оскільки -2<0.
-2<0, тому генеральний стовпчик береться по х2
Перерахуємо таблицю
x1 x5
x3 4 -1/2 ½
x4 7 3/2 ½
x2 1 -1/2 -1/2
Lmin -3 -1/2 3/2
Вибрали генеральний стовпчик, оскільки 3/2>0.
8<14, тому генеральна строка береться по х3
Перерахуємо таблицю
x1 x3
x5 8 -1 2
x4 3 2 -1
x2 5 -1 1
Lmin -15 1 -3
Вибрали генеральний стовпчик, оскільки 1>0.
2>0, тому генеральна строка береться по х4
Перерахуємо таблицю
x4 x3
x5 19/2 ½ 3/2
x1 3/2 ½ -1/2
x2 13/2 ½ ½
Lmin -33/2 -1/2 -5/2
Знайдене рішення оптимальне, але розв'язки мають бути цілими числами, тому використаємо алгоритм перший
x1=3/2-(1/2х4-1/2х3)
Побудуємо пряму відсікання
хвід=
х6=
Знайдемо оптимальне рішення, використовуючи пряму відсікання
Перерахуємо таблицю
x4 x3
x5 19/2 ½ 3/2
x1 3/2 ½ -1/2
x2 13/2 ½ ½
x6 -1/2 -1/2 -1/2
Lmin -33/2 -1/2 -5/2
