7. Графічне розв`язання злп.
Графічним методом зазвичай вирішуються задачі лінійного програмування, що мають 2 змінні, тобто двовимірні. Алгоритм рішення задач двовимірного лінійного програмування графічним методом:
1. Будуємо область припустимих рішень функції F.
Для цьго в обмеженнях змінюємо знак нерівності на знаки рівняння і будуємо прямі. Далі визначаємо ті полуплощини, які відповідають обмеженням та отримуємо область припустимих значень, яка знаходиться на перетинанні всіх полуплощин.
2. Будуємо вектор нормальний.
Почаком вектору зазвичай обирається точка (0,0)
Кінцем виступають коефіцієнти при цільовій функції F.
3. Максимізуємо (мінімізуємо) цільову функцію F.
Будуємо до даного вектора нормального перпендикуляр та пересуваємо його у напрямку області допустимих значень, до перетинання з першою точною при мінімізації цільової функції (з останньою при максимізації). Отримана точка є оптимальним рішенням, в якому функція досягає свого максимуму (мінімуму). Знаходимо координати цієї точки та підставляємо їх в функцію F.
У разі застосування графічного методу можливі такі випадки:
1)Цільова функція набуває максимального значення в єдиній вершині А многокутника розв’язків (рис. 2.2). + 2)Максимального значення цільова функція досягає в будь-якій точці відрізка АВ (рис. 2.3). Тоді задача лінійного програмування має альтернативні оптимальні плани.
3) Задача лінійного програмування не має оптимальних планів (рис. 2.4 — цільова функція не обмежена згори; рис. 2.5 — система обмежень задачі несумісна).
4)Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв’язків (рис. 2.6 і 2.7).
8. Симплекс-таблиці.
Симплекс метод розв’язування ЗЛП доцільно використовувати при задач більше ніж з 2ма змінними. Процес розв’язання даним методом має інтеракційний характер, тобто при обчислюванні процесів (інтерацій) в переході від одного припустимого базисного рішення до іншого таким чином, що значення цільової функції при цьому безупинно зростають (для завдань максимізації).
Алгоритм:
Спочатку нашу умову ми повинні привести до загального вигляду ЗЛП, а саме:
L = (cx ) максимум/минимум
Ах ≤ b
І. Записуємо дану ЗЛП в нормальному стандартному вигляді.
L = 0 - (cx ) минимум
У = b – (сх)
ІІ. Будуємо симплекс-таблицю.
|
b |
x1 |
… |
xn |
|
0 |
c1 |
… |
cn |
y1 |
b1 |
a11 |
… |
a1n |
… |
… |
… |
… |
… |
ym |
bm |
am1 |
… |
amn |
Змінні у назвемо базовими змінними; змінні х – вільними змінними.
Суть симплекс-методу полягає у взаємозаміні базових змінних на для одержання спочатку допустимого, а потім і оптимального розв’язку задачі.
ІІІ. Шукаємо допустимий розв’язок.
ІV. Будуємо оптимальний розв’язок ЗЛП.
11.
L=(C1x)=C1X1+…+CnXn->max (1)
(2)
L’=(b1z)=b1z1+…+bmzm->min (3)
(4)
1)вільні члени обмежень (2) b1…bn є коеф. Нового критерію якості L*, а коеф. C1…Cn – критерії L вільними членами в обмеженнях (4)
2)Матрицею коеф. В нових обмежень є матриця А* , що одержана транспонуванням матриці А
3)В нових обмеженнях (4) знаки нерівностей протилежні знакам нерівностей (2)
4)максим. Критерію L змін. На мінімізацію критерію L*