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
В результаті отримаємо другий оптимальний план з іншим набором базисних змінних. В індексному рядку в 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.
