Методи вирішення завдань.
Завдання лінійного програмування, яка є окремим випадком задачі оптимізації записується в такий спосіб: 
(7.10)
Дана система з n лінійних нерівностей з n невідомими і лінійна функція F. Потрібно знайти рішення системи x1, x2, x3 ... xn, що задовольняє ГРУ, при якому функція F приймає max значення.
Завдання лінійного програмування можна вирішити аналітичним шляхом і графічним методом. Другий метод - наочний, але придатний лише для n = 2 (тобто де число змінних = 2).
приклад
Відомо, що рівняння прямої має вигляд: a1x1 + a2x2 = b. Побудуємо пряму 2x1 + x2 = 2. Перепишемо це рівняння у вигляді: 
При такій формі запису в знаменнику показані відрізки, які відтинає пряма на осях координат (Рис. 7.2). Якщо від вихідного рівняння перейти до нерівності 2x1 + x2≤2, то графічно рішення цієї нерівності показано на рис. 7.3, тобто рішенням лінійного нерівності з двома змінними є напівплощина. На рис. 7.3 частина площині, яка не задовольняє нерівності розташована вище прямої, заштрихована. Координати всіх точок, що належать не заштрихованої частини площини, мають такі значення х1 і х2, які задовольняють заданому нерівності. Ця напівплощина є областю допустимих рішень (ОДР).
Розглянемо систему нерівностей: 
Для зручності запишемо її в наступному вигляді: 
Графічне рішення цієї системи показано на рис. 7.4
Рішенням цієї системи є координати всіх точок, що належать ОДР, тобто многоугольнику ABCDO.
Оскільки в ОДР незліченна безліч точок, значить, розглянута система має безліч допустимих рішень.
Якщо ми хочемо знайти оптимальне рішення, то ми повинні прийняти цільову функцію. Нехай ми хочемо, щоб рішення було оптимальним в сенсі максимізації цільової функції F = x1 + x2 → max
Ця залежність на рис. 7.5 представлена у формі рівняння прямої з кутовим коефіцієнтом x2 = F-x1, з якого видно, що tga = -1. При цьому кут a = 135 °, а величина F дорівнює відрізку, який відсікається прямою на осі ординат. Якщо пряму переміщати паралельно самій собі в напрямку, зазначеному стрілками, то величина F буде зростати. Сумісний тепер ОДР, зображену на рис. 7.4, з лінією цільової функції F, побудованої на рис. 7.5, отримаємо рис. 7.6.
Оскільки потрібно знайти оптимальне рішення, при якому цільова функція F = x1 + x2 → max, тобто прагне до максимуму, будемо переміщувати графік цільової функції в напрямку збільшення F. Очевидно, що оптимальним рішенням будуть координати точки С, рівні х1 * і х2 *. При цьому F = F *.
На підставі розглянутого можна зробити висновок: оптимальним рішенням є координати вершин ОДР.
На цьому базується аналітичний метод розв'язання задач лінійного програмування, який полягає в наступному:
- Знайти вершини ОРД, як точки перетину обмежень.
- Визначити послідовно значення цільової функції в вершинах.
- Вершина, в якій ЦФ набуває оптимальне (максимальне або мінімальне) значення, є оптимальною вершиною.
- Координати цієї вершини і є шуканими оптимальними значеннями змінних.
Основні положення симплекс-методу
Для аналітичного рішення задач лінійного програмування розроблено спеціальний алгоритм спрямованого перебору вершин ОРД (області допустимих рішень). Цей алгоритм забезпечує перехід від однієї вершини до іншої в такому напрямку, при якому значення цільової функції від вершини до вершини поліпшується. В геометрії є таке поняття, як "симплекс". Симплексом тел в К-вимірному просторі називається сукупність (К + 1) його вершин. Так, для площини при К = 2 симплексом будуть 3 вершини трикутника. При К = 3 - 4 вершини четирехгранніка і т.д. З урахуванням цього поняття аналітичний метод розв'язання задач лінійного програмування називається симплекс-метод. Обчислення, що забезпечують визначення значення ЦФ і змінних в одній вершині називаються итерацией.
назад зміст вперед
