Завдання 2
Запісаті двоїсту задачу до поставленої Задачі лінійного програмування. Розв'язати одну Із завдань симплексним методом и візначіті оптимальний план іншої Задачі. Оптімальні результати перевіріті графічно.
розв'язок
Розв'яжемо задачу лінійного програмування симплексним методом.
Візначімо мінімальне Значення цільової функції F (X) = 4x1 +2 x2 при Наступний Умова-обмежень.
x1-x2 ≤ 4
x1 +3 x2 ≤ 6
x1 +2 x2 ≥ 2
Для Побудова Першого опорного плану систему нерівностей пріведемо до системи рівнянь шляхом Введення Додатковий змінніх.
Оскількі маємо змішані Умова-обмеження, то введемо штучні змінні x.
1x1-1x2 + 1x3 + 0x4 + 0x5 = 4
1x1 + 3x2 + 0x3 + 1x4 + 0x5 = 6
1x1 + 2x2 + 0x3 + 0x4-1x5 = 2
Для постановки Задачі на мінімум цільову функцію запішемо так:
F (X) = 4x1 +2 x2 - Mx6 => max
Вважаючі, Що Вільні змінні рівні 0, отрімаємо Перший опорний план:
План
Базис
В
x1
x2
x3
x4
x5
х6
0
х3
4
1
-1
1
0
0
0
x4
6
1
3
0
1
0
0
х6
2
1
2
0
0
-1
1
Індексній рядок
F (X0)
0
0
0
0
0
0
0
Переходімо до основного алгоритму симплекс-методу.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
1
x3
4
1
-1
1
0
0
0
0
x4
6
1
3
0
1
0
0
2
x6
2
1
2
0
0
-1
1
1
Індексній рядок
F (X1)
0
0
0
0
0
0
0
0
Оскількі, в індексному рядку знаходяться негатівні коефіцієнті, поточний опорний план неоптимальним, тому Будуємо новий план. У ЯКОСТІ ведучого віберемо елемент у стовбці х2, оскількі Значення коефіцієнта за модулем найбільше.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
2
x3
5
1.5
0
1
0
-0.5
0.5
3.33
х4
3
-0.5
0
0
1
1.5
-1.5
0
x2
1
0.5
1
0
0
-0.5
0.5
2
Індексній рядок
F (X2)
0
0
0
0
0
0
0
0
Сейчас план, кож не оптимальний, тому Будуємо Знову нову симплексного таблиці. У ЯКОСТІ ведучого віберемо елемент у стовбці х2.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
3
x3
2
0
-3
1
0
1
-1
2
X4
4
0
1
0
1
1
-1
4
X1
2
1
2
0
0
-1
1
0
Індексній рядок
F (X3)
0
0
0
0
0
0
0
0
План
Базис
В
x1
x2
x3
x4
x5
x6
min
4
х5
2
0
|
