Page 9 - 100

2 ОСНОВИ ЛІНІЙНОГО МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ

2.1 Формулювання задачі
Задача лінійного програмування формулюється наступним чином: по-
трібно знайти значення n змінних х і, які мінімізують (максимізують) функцію.
z=с 1x 1+с 2x 2+…+ с nx n
При m обмеженнях
а 11x 1+a 12x 2+…+a 1nx n≤b 1;
а 21x 1+a 22x 2+…+a 2nx n≤ b 2;
……………………...
а m1x 1+a m2x 2+…+a mnx n≤ b m;
і умова невід’ємності змінних
x 1≥0; x 2≥0; … ; x n≥0;
Функція, яка підлягає мінімізації (максимізації), називається в матема-
тичному програмуванні цільовою функцією.
Наявність терміну „лінійне” в назві математичного методу означає те,
що цільова функція і обмеження задачі знаходиться в лінійній залежності від
змінних.

2.2 Графічний розв’язок задачі
Графічне розв’язання задачі лінійного програмування можливе лише
для задачі однієї, двох та трьох змінних. У випадку однієї змінної задача
розв’язується на прямій, для двох – на площині, для трьох – у просторі.
Алгоритм розв’язку задачі:
1. На основі обмежень на площині (для двох змінних), або у просторі (для
трьох змінних) будується область допустимих розв’язків (ОДР), всі точки якої
задовольняють обмеження моделі.
2. Вибираємо довільну точку ОДР і підставляємо її координати в цільову фу-
нкцію. Визначаємо z 0. Будуємо на площині лінію z 0, або для трьох змінних в
просторі – площину z 0.
3. Визначаємо напрям покращення цільової функції у порівнянні з z 0. Для
цього вибираємо довільну точку ОДР по одну сторону від лінії (площини) z 0,
обчислюємо значення z 1 і порівнюємо з z 0.
4. Переміщаємо паралельно лінію (площину) z 0 в сторону оптимуму до межі
ОДР. При цьому лінія оптимуму z max (z min) може мати:
- одну спільну точку з ОДР, яка і буде оптимальною;
- відрізок спільних точок з ОДР, множина яких і буде розв’язком;
- необмежену кількість точок, якщо лінія (площина) z не виходить за межі
ОДР, скільки би її не пересували.

2.3 Аналіз моделей на чутливість
Після отримання оптимального розв’язку може бути проведений аналіз
чутливості отриманого розв’язку до зміни вихідних умов. Після отримання
розв’язку обмеження поділяються на активні, на перетині яких лежить точка
оптиму, та пасивні, які не є визначальними при розв’язку.

9