Page 16 - 6449

Використовуючи встановлені основні теоретичні положення теорії
лінійного програмування, можна запропонувати наступний спосіб

розв’язання ЗЛП: не використовуючи графік Z  const , зображається
графічно ОДР (приклад 1). В даному випадку ОДР – це шестикутник
APCDBQ. Оскільки розв’язок ЗЛП знаходиться лише на границі ОДР,
знайдемо координати вершин вказаного шестикутника і обчислимо в цих

точках значення функції Z, визначаємо при цьому Z max та Z min , що і
завершує розв’язок задачі. В даному випадку, виходячи з рис.1.5,
встановлюємо:
5 5
А( ; ); P(7,0);C(7,0); B(0,7);Q(0,5). Координати точки D знаходяться
6 6
шляхом розв’язку системи лінійних алгебраїчних рівнянь:
7х 1  9х 2  63 63  63 63 
  7х 1  9х 2  9х 1  7х 2  2х 1  2х 2  х 1  х 2 ;х 1  х 2   D  ; 
 9х 1  7х 2  63 16  16 16 
Підставляємо вказані координати в цільову функцію задачі,
наведеної в прикладі №1: Z  2,5; Z  5; Z  7; Z  14; Z  10, Z  11,8125.
A P C B Q D
Таким чином, Z  5 , 2 , Z  14 , і результат, одержаний методом
min max
повного перебору вершин співпадає з результатами, одержаними шляхом
використання графічного методу. Особливістю методу повного перебору
вершин є те, що його використання обмежується кількість обмежень та
невідомих ЗЛП. Зокрема, при великих значеннях n та m – відповідно
кількості невідомих та обмежень, кількість вершин ОДР дорівнює числу
комбінацій з n невідомих по m , тобто С . В такому випадку необхідно
m
n
m
розв’язати С систем лінійних алгебраїчних рівнянь, що робить вказаний
n
метод неефективним з обчислювальної точки зору, і він майже не
використовується при розв’язанні практичних задач.

1.3 Симплекс-метод розв’язку ЗЛП
Симплекс-метод, який в літературних джерелах зустрічається під
назвою “Метод послідовного покращення плану ”, був запропонований
Данцігом в 1947 р [9,13]. Цей метод є ітераційною процедурою, за
допомогою якої здійснюється перехід від одного допустимого базисного
розв’язку до іншого, який відповідає одній із наступних вершин ОДР,
причому значення цільової функції при цьому змінюється в потрібному
напрямку. За скінченну кількість кроків вдається або встановити
оптимальний розв’язок задачі, або ж встановити відсутність оптимального
розв’язку ЗЛП.
Симплексом називають найпростіший випуклий многогранник
даного числа вимірів n . При n  3 тривимірний симплекс – це тетраедр;
n  2 - трикутник; n  1 - відрізок; n  0 -точка.
Нехай необхідно знайти розв’язок задачі лінійного програмування
виду:

16