Page 22 - 4168

3 МЕТОДИЧНІ ВКАЗІВКИ
3.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.
Функція, яка підлягає мінімізації (максимізації), назива-
ється в математичному програмуванні цільовою функцією.
Наявність терміну „лінійне” в назві математичного мето-
ду означає те, що цільова функція і обмеження задачі знахо-
диться в лінійній залежності від змінних.
Графічний розв’язок задачі
Графічне розв’язання задачі лінійного програмування
можливе лише для задачі однієї, двох та трьох змінних. У ви-
падку однієї змінної задача розв’язується на прямій, для двох –
на площині, для трьох – у просторі.
Алгоритм розв’язку задачі:
1. На основі обмежень на площині (для двох змінних),
або у просторі (для трьох змінних) будується область допусти-
мих розв’язків (ОДР), всі точки якої задовольняють обмеження
моделі.
2. Вибираємо довільну точку ОДР і підставляємо її коор-
динати в цільову функцію. Визначаємо z 0. Будуємо на площині
лінію z 0, або для трьох змінних в просторі – площину z 0.
3. Визначаємо напрям покращення цільової функції у по-
рівнянні з z 0. Для цього вибираємо довільну точку ОДР по од-
ну сторону від лінії (площини) z 0, обчислюємо значення z 1 і
порівнюємо з z 0.
4. Переміщаємо паралельно лінію (площину) z 0 в сторону
оптимуму до межі ОДР. При цьому лінія оптимуму z max (z min)
може мати:

22