1. Алгоритм табличного симплекс методу
Симплекс-метод - алгоритм розв'язання оптимізаційної задачі лінійного програмування шляхом перебору вершин опуклого багатогранника в багатовимірному просторі. Метод був розроблений американським математиком Джорджем Данцигом (George Dantzig) в 1947 році.
Алгоритм:
1) Перевіряємо базисні рішення на оптимальність. Переглядаємо знаки коефіцієнтів останнього рядка таблиці, виключаючи коефіцієнт при вільному члені. Наявність негативних коефіцієнтів в останньому рядку говорить про те, що рішення не оптимально.
2) Перевіряємо задачу на наявність рішення. Якщо над усіма негативними коефіцієнтами цільової функції немає жодного стовпця з непозитивно числами, то завдання не має рішення.
3) Вибираємо з небазисних змінних ту, яка здатна при введенні її в базис збільшити значення цільової функції, тобто змінну, що має найбільший негативний коефіцієнт в останньому рядку і відзначаємо її зірочкою «*» - дозволяє стовпець.
4) Визначаємо, яка з базисних змінних повинна бути виведена з базису. Для цього визначаємо мінімальне частка від ділення відповідних вільних членів і позитивних коефіцієнтів стовпця зазначеного зірочкою. Коефіцієнт який знаходиться на перетині роздільної рядка і розв'язного стовпця називається що дозволяє елементом (у таблиці його беруть в рамку).
5) що вводяться в базис змінну виражаємо через змінну, виведену з базису і інші небазисних змінні. Всі елементи роздільної рядка ділимо на дозволяє елемент. Далі висловлюємо всі інші змінні через нову базисну. Для цього ми повинні зробити рівними 0 всі інші елементи розв'язного стовпця таблиці 1, крім стоячого на перетині з роздільною рядком. Домножаем на необхідне число роздільну рядок таблиці 1 і прібавлеям до інших рядках.
2.Ідея методу штучного базису
Метод штучного базиса
Якщо після підготовки ЗЛП до спеціального виду на вирішення симплекс методом, над кожному рядку системи обмежень є базисна змінна (що входить у цю рядок з коефіцієнтом 1, а інші рядки з коефіцієнтом 0), то тут для вирішення цієї ЗЛП треба скористатися методом штучного базиса.
Суть методу досить проста:
1. До рядкам, у яких відсутня базисна змінна додається за однією штучної базисної переменной.
2. Нова завдання вирішується Симплекс-методом, причому всі штучні базисні перемінні мають стати вільними (вийти з базису) та його сума має дорівнювати нулю, у протилежному разі даної системи неможливо виділити припустимий базис.
Рассмотрим наступний пример:min(f)-?
1. У першому рівнянні немає базисних невідомих. Введём штучну базисну невідому Y1 і заповнимо першу симплекс-таблицу
Для здобуття права позбудеться штучної базисної невідомої нам доведеться вирішувати допоміжну задачу:
F=Y1>min
Выражая базисну невідому Y1 через вільні получаем:
F+4X1+X2=4 >min
|Б |X1 |X2 |X3 |X4 |Y1 |З | |Y1 |4 |1 |0 |0 |1 |4 | |X4 |11 |3 |-5 |-1 |0 |12 | |F |4 |1 |0 |0 |0 |4 |
Выбираем елемент в осередку (3;2) і робимо шаг.
|Б |X1 |X2 |X3 |X4 |Y1 |З | |X2 |4 |1 |0 |0 |1 |4 | |X4 |-1 |0 |-5 |-1 |-3 |0 | |F |0 |0 |0 |0 |-1 |0 |
min(f)=0, все коефіцієнти у вищій рядку менше, або рівні нулю, отже перейшли до нового природному базису. Нині можна вирішувати основну задачу.
3.Розв»язання ЗЛП Симплекс-методом за вихыдними даними Л.Р№1
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.
Визначимо максимальне значення цільової функції F(X) = 302x1+382x2+302x3 при.
00.42x1+0.42x2+0.42x3?18.5
0.42x1+0.22x2+0.42x3?17
0.22x1+0.42x2+0.22x3?14
0.42x1 + 0.42x2 + 0.42x3 + 1x4 + 0x5 + 0x6 = 18.5
0.42x1 + 0.22x2 + 0.42x3 + 0x4 + 1x5 + 0x6 = 17
0.22x1 + 0.42x2 + 0.22x3 + 0x4 + 0x5 + 1x6 = 14
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:

Вирішимо систему рівнянь відносно базисних змінних:
x4, x5, x6,
Вважаючи, що вільні змінні рівні 0, отримавши перший опорний план:X1 = (0,0,0,18.5,17,14)
Базис
В
x1
x2
x3
x4
x5
x6

x4
18.5
0.42
0.42
0.42
1
0
0

x5
17
0.42
0.22
0.42
0
1
0

x6
14
0.22
0.42
0.22
0
0
1

F(X0)
0
-302
-382
-302
0
0
0


Переходимо до основного алгоритму симплекс-методу.
Ітерація № 0.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В індексному рядку F (x) вибираємо максимальний по модулю елемент. В якості ведучого виберемо стовпець, відповідний змінної x2, так як це найбільший коефіцієнт за модулем.
Обчислимо значення Di по рядках як частка від ділення: bi / ai2
і з них виберемо найменше:
Отже, 3-й рядок є провідною.
Дозволяє елемент дорівнює (0.42) і знаходиться на перетині провідного стовпця і ведучою рядка.
Базис
В
x1
x2
x3
x4
x5
x6
min

x4
18.5
0.42
0.42
0.42
1
0
0
44.05

x5
17
0.42
0.22
0.42
0
1
0
77.27

x6
14
0.22
0.42
0.22
0
0
1
33.33

F(X1)
0
-302
-382
-302
0
0
0
0



Після перетворень отримуємо нову таблицю:
Базис
В
x1
x2
x3
x4
x5
x6

x4
4.5
0.2
0
0.2
1
0
-1

x5
9.67
0.3
0
0.3
0
1
-0.52

x2
33.33
0.52
1
0.52
0
0
2.38

F(X1)
12733.33
-101.9
0
-101.9
0
0
909.52


Ітерація № 1.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В індексному рядку F (x) вибираємо максимальний по модулю елемент. В якості ведучого виберемо стовпець, відповідний змінної x3, так як це найбільший коефіцієнт за модулем.
Обчислимо значення Di по рядках як частка від ділення: bi / ai3
і з них виберемо найменше:
Отже, 1-й рядок є провідною.
Дозволяє елемент дорівнює (0.2) і знаходиться на перетині провідного стовпця і ведучою рядка.
Базис
В
x1
x2
x3
x4
x5
x6
min

x4
4.5
0.2
0
0.2
1
0
-1
22.5

x5
9.67
0.3
0
0.3
0
1
-0.52
31.72

x2
33.33
0.52
1
0.52
0
0
2.38
63.64

F(X2)
12733.33
-101.9
0
-101.9
0
0
909.52
0



Після перетворень отримуємо нову таблицю:
Базис
В
x1
x2
x3
x4
x5
x6

x3
22.5
1
0
1
5
0
-5

x5
2.81
0
0
0
-1.52
1
1

x2
21.55
0
1
0
-2.62
0
5

F(X2)
15026.19
0
0
0
509.52
0
400


Кінець ітерацій: індексна рядок не містить негативних елементів - знайдений оптимальний план
Остаточний варіант симплекс-таблиці:
Базис
В
x1
x2
x3
x4
x5
x6

x3
22.5
1
0
1
5
0
-5

x5
2.81
0
0
0
-1.52
1
1

x2
21.55
0
1
0
-2.62
0
5

F(X3)
15026.19
0
0
0
509.52
0
400


Оптимальный план можно записать так:
x3 = 22.5
x5 = 2.81
x2 = 21.55
F(X) = 382*21.55 + 302*22.5 = 15026.19
Аналіз оптимальної симплекс-таблиці.
У оптимальний план увійшла додаткова змінна x5. Отже, при реалізації такого плану є недовикористані ресурси 2-го виду в кількості 2.81
В індексному рядку в 1-му стовпці нульове значення. У стовпці, що містить цей нуль, є хоча б один позитивний елемент. Отже, завдання має безліч оптимальних планів.
Покажемо це на прикладі. Вільну змінну, відповідну вказаною стовпцю, вносимо в базис (замість x2), виконавши відповідні етапи алгоритму.
Після перетворень отримуємо нову таблицю:
Базис
В
x1
x2
x3
x4
x5
x6

x3
22.5
1
0
1
5
0
-5

x5
2.81
0
0
0
-1.52
1
1

x1
5386904761908.2
1
250000000000
1
-654761904761.25
0
1249999999999.2

F(X )
15026.19
0
0
0
509.52
0
400


В результаті отримаємо другий оптимальний план з іншим набором базисних змінних.
В індексному рядку в 2-му стовпці нульове значення. У стовпці, що містить цей нуль, є хоча б один позитивний елемент. Отже, завдання має безліч оптимальних планів.
Покажемо це на прикладі. Вільну змінну, відповідну вказаною стовпцю, вносимо в базис (замість x1), виконавши відповідні етапи алгоритму.
Після перетворень отримуємо нову таблицю:
Базис
В
x1
x2
x3
x4
x5
x6

x3
22.5
1
0
1
5
0
-5

x5
2.81
0
0
0
-1.52
1
1

x2
21.55
0
1
0
-2.62
0
5

F(X )
15026.19
0
0
0
509.52
0
400


В результаті отримаємо другий оптимальний план з іншим набором базисних змінних.
Значення 0 у стовпці x3 означає, що використання x3 - вигідно.
Значення 509.52 в стовпці x4 означає, що тіньова ціна (двоїста оцінка) дорівнює 509.52.
Значення 400 в стовпці x6 означає, що тіньова ціна (двоїста оцінка) дорівнює 400.