16. Геометрична інтерпретація задачі лінійного програмування, графічний метод розв’язання задач лінійного програмування з двома змінними.

Розглянемо задачу лінійного програмування у формі стандартної задачі – з обмеженнями у вигляді нерівностей. З метою наочності розглянемо простіший випадок з двома невідомими змінними.

Z = 10 x1 + 20 x2 ; Z → max;

х1 + 3,5 х2 ≤ 350;

2 х1 + 0,5 х2 ≤240;

х1 + х2 ≤150;

х1 + х2 ≤110;

10 х1 + 20 х2 ≤1400;

х1 ≤0;

х2 ≤0.

Нерівність – обмеження графічно відображається півплощіною, а границя – граничною прямою, рівняння якої утворюється перетворенням нерівності на рівняння.

x1 + 3,5x2 = 350 ;

x1 = 0, x2 = 0

x2 = 350 / 3,5 = 100 ; x1 = 350.

Щоб з’ясувати, яка напівплощіна задовольняє нерівності, перевіримо, наприклад, чи включає точку (0,0) 0 + 3,5 × 0 £ 350 напівплощіна нижче граничної прямої – нерівність виконується – напівплощіна нижче границі.

Таким же чином перевіримо та побудуємо інші нерівності:

2x1 + 0,5x2 = 240 ;

x1 = 0, x2 = 240 / 0,5 = 480 ;

x2 = 0, x1 = 240 / 2 = 120 ;

x1 + x2 = 150;

x1 = 0; x2 = 150;

x2 = 0, x1 = 150;

x1 + x2 = 110;

x1 = 0; x2 = 110;

x2 = 0, x1 = 110;

10x1 + 20x2 = 1400;

x1 = 0, x2 = 1400 / 20 = 70;

x2 = 0, x1 = 1400 / 10 = 140;

але точка (0,0) 10 × 0 + 20 × 0 = 0 ≤ 1400 не відповідає нерівності, тому нам потрібна півплощіна вище граничної прямої.

Таким чином отриманий многокутник розв’язків.

З метою знаходження максимуму цільової функції

Z = 10 x1 + 20 x2 побудуємо лінію рівня цільової функції, поклавши Z = 0 ,

10 x1 + 20 x2 = 10;

x1 = 0, x2 = 40;

x2 = 0; x1 = 80;

зростання цільової функції позначає паралельне зміщення самій собі догори, доки остання крапка не вийде на границю многокутника розв’язків.

Ця точка відповідає перетину прямих

х1 + 3,5 х2 = 350; - l1 ( × ) C (70; 80)

х1 + х2 = 250; - l3

х1 = 70, х2 = 80,

Zmax (x) = 10 × x1 + 20 × x2 = 10 × 70 + 20 × 80 = 23000 грн.

Якщо було б потрібно знайти мінімальне значення цільової функції, так лінію рівня потрібно зміщувати униз, доки остання крапка вийде на границю многокутника розв’язків – це l5 , усі крапки якої є розв’язком задачі – нескінченна множина рішень.

У розглянутому випадку многокутник розв’язків не тільки опуклий, а ще і є замкненим. Можливі варіанти опуклого многокутника розв’язків, який є необмеженим.

У першому випадку можливо знайти максимальне значення цільової функції, а у другому випадку – мінімальне значення.

17. Симплексний метод.

Перша праця по лінійному програмуванню була надрукована Канторовичем у 1939 році, але лише після відкриття Данцігом у 1949 році симплекс-метода розв'язання задачі лінійного програмування до цього класу задач виникла зацікавленість. Симплекс-метод дає аналітичний розв’язок лінійної задачі математичного програмування.

Симплексний метод розв’язання задачі лінійного програмування ґрунтується на переході від одного опорного плану до іншого таким чином, що кожного разу значення цільової функції зростає (за умов, що задача має оптимальний план, та кожний з опорних планів не є надмірним). Під опорним планом мають на увазі невід’ємний базисний розв’язок задачі лінійного програмування. Нагадаємо – базисний план (розв’язок) – рішення системи обмежень. у якому усі вільні змінні дорівнюють нулеві, тобто геометрично базисний план відповідає одній з вершин або граней многокутника розв’язків.

Стереометрично ідея методу полягає у тому, що:

• знаходять будь-яку вершину багатогранника розв’язків;

• рухаються вздовж того з ребер, по якому функція зменшується (збільшується) до іншої вершини багатогранника розв’язків;

• як потрапляють у вершину, з якої у всі боки функція зростає (спадає), так знаходять мінімум (максимум).

• якщо вектор розв’язків задовольняє усім обмеженням, так він має назву плану;

• якщо план відповідає вершині багатогранника розв’язків (усі вільні змінні дорівнюють нулеві), так він має назву опорного плану;

• якщо опорний план відповідає екстремальному значенню цільової функції, так він має назву оптимального плану.

• Якщо форма мінімізується (максимізується) і у рідку цільової функції відсутні додатні числа (від’ємні числа), за винятком стовпчика опорний розв’язок (b1), так опорний план є оптимальним.

Коефіцієнти рядка цільової функції інтерпретують як приріст цільової функції при збільшенні вільної невідомої на одиницю. Приріст додатній, якщо коефіцієнт від’ємний, і навпаки від’ємний, якщо коефіцієнт додатній.

Послідовність використання симплекс-методу:

1. звести задачу лінійного програмування до задачі мінімізації у канонічній формі (обмеження-рівняння; bі ≤0);

2. поділити змінні на базисні та вільні і отримати базисне припустиме рішення (базисні змінні невід’ємні; вільні змінні дорівнюють нулеві);

3. знайти вираз базисних змінних та цільової функції через вільні змінні;

4. за знаком коефіцієнтів при невідомих (сj ≤ 0) у цільовій функції з’ясувати, чи є рішення оптимальне

5. Z = с0 + с1х1 + с2х2 + . . . + сnхn ; (cj ≤ 0 – мінімізація); або яку вільну змінну можливо підвищити від нуля та перевести у базис і відповідно, яку базисну змінну перевести у вільні змінні;

6. знайти мінімальне додатне співвідношення “bi” вільних членів рівнянь-обмежень до коефіцієнтів “aij” при новій вільній змінній, тобто з’ясувати, яку базисну змінну необхідно перевести у вільні змінні;

7. перетворити умови-обмеження та цільову функцію у вираз в залежності від нових вільних змінних.