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 при.
0.47x1+0.47x2+0.47x3?18.5
0.47x1+0.27x2+0.47x3?17
0.27x1+0.47x2+0.27x3?14
0.47x1 + 0.47x2 + 0.47x3 + 1x4 + 0x5 + 0x6 = 18.5
0.47x1 + 0.27x2 + 0.47x3 + 0x4 + 1x5 + 0x6 = 17
0.27x1 + 0.47x2 + 0.27x3 + 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.47
0.47
0.47
1
0
0

x5
17
0.47
0.27
0.47
0
1
0

x6
14
0.27
0.47
0.27
0
0
1

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


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

x4
18.5
0.47
0.47
0.47
1
0
0
39.36

x5
17
0.47
0.27
0.47
0
1
0
62.96

x6
14
0.27
0.47
0.27
0
0
1
29.79

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
8.96
0.31
0
0.31
0
1
-0.57

x2
29.79
0.57
1
0.57
0
0
2.13

F(X1)
11378.72
-82.55
0
-82.55
0
0
812.77


Ітерація № 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
8.96
0.31
0
0.31
0
1
-0.57
28.45

x2
29.79
0.57
1
0.57
0
0
2.13
51.85

F(X2)
11378.72
-82.55
0
-82.55
0
0
812.77
0



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

x3
22.5
1
0
1
5
0
-5

x5
1.87
0
0
0
-1.57
1
1

x2
16.86
0
1
0
-2.87
0
5

F(X2)
13236.17
0
0
0
412.77
0
400


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

x3
22.5
1
0
1
5
0
-5

x5
1.87
0
0
0
-1.57
1
1

x2
16.86
0
1
0
-2.87
0
5

F(X3)
13236.17
0
0
0
412.77
0
400


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

x3
22.5
1
0
1
5
0
-5

x5
1.87
0
0
0
-1.57
1
1

x1
16861702127668
1
1000000000000
1
-2872340425530
0
4999999999998

F(X )
13236.17
0
0
0
412.77
0
400


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

x3
22.5
1
0
1
5
0
-5

x5
1.87
0
0
0
-1.57
1
1

x2
16.86
0
1
0
-2.87
0
5

F(X )
13236.17
0
0
0
412.77
0
400


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