Page 220 - 4685

ЛІНІЙНЕ ПРОГРАМУВАННЯ

Лінійне програмування – це математичний метод, призначений для
виявлення оптимального рішення з великої кількості можливих варіантів
рішення задачі, в якій умови дозволяють запис у вигляді лінійних
співвідношень. Лінійне програмування застосовується для вирішення
наступних типів задач: розподіл ресурсів, формування комбінації кормів,
складання портфеля інвестицій, вибір виробничої програми. Для постановки
задачі лінійного програмування необхідно ввести змінні величини, що
визначаються, виразити через ці змінні обмежуючі умови і цільову функцію.
Для вирішення задач лінійного програмування використовують симплекс-метод
або графічний метод (за наявності двох змінних у вирішуваній задачі).
Симплекс-метод (аналітичне вирішення задач лінійного програмування) –
це алгоритм формального перерахунку варіантів рішення задачі з послідовним
рухом до оптимального рішення. Кожен крок алгоритму розрахунків покращує
попереднє рішення.
Розглянемо алгоритм симплекс-методу на основі числового прикладу –
оптимізаційного завдання, що включає п'ять невідомих і три обмежуючі умови:
J= 1,2х(1)+ 1,4х(2) → min;
х(3)= 40х(1)+ 25х(2)+ 1000;
х(4)= 35х(1)+ 28х(2)+ 980;
х(5)= 25х(1)+ 35х (2)+ 875.
1-й етап рішення задачі. Початкове рішення задачі приймемо за умови,
що в ньому будуть нульовими перші дві змінні:
х(1)= 0; х(2)= 0; х (3) = 1000; х (4) = 980; х(5)= 875.
Це рішення задачі представимо у вигляді таблиці (симплекс-таблиці):
х(1) x(2) b
х(3) 40 25 1000
х(4) 35 28 980
х(5) 25 35 875
J 1,2 1,4 0
Ця таблиця в умовному вигляді повторює систему умов завдання.
2-й етап рішення задачі. Знаходимо "ключовий" стовпець за умовою max
c (i) (у нашому прикладі c (i) = 1,4).
3-й етап рішення задачі. Знаходимо "ключовий" рядок за умовою
( b ) j ( b ) j 875
min (у нашому прикладі min = ).
a , (i ) j a , (i ) j 35
4-й етап рішення задачі. "Повертаємо" таблицю довкола "ключового"
елемента:

216