Розв'язок задачі дробово-лінійного програмування графічним методом
При розгляді теоретичної частини задачі дробово-лінійного програмування, а зокрема, при розгляді конкретної задачі такого типу, нами було анонсовано, що в подальшому дану задачу буде розв'язано з допомогою графічного методу та методу, який базується на зведенні задач з дробово-лінійною цільовою функцією до задачі лінійного програмування. Сьогодні розглянемо перший з них, але перш ніж приступити до розв'язку задачі, розглянемо алгоритм даного методу більш детально. Для цього, припустимо, що нам потрібно знайти максимальне (мінімальне) значення функції мети (де ):
при наступних обмеженнях:
Щоб знайти рішення задачі (1) — (3), спочатку, як і у випадку задачі лінійного програмування, знаходимо багатокутник рішень, який визначається обмеженнями (2) і (3). Припускаючи, що цей багатокутник не порожній, покладаємо значення функції (1) рівним деякому числу :
З отриманого виразу знайдемо значення змінної :
Тобто, в результаті, ми отримали рівняння прямої, яка проходить через початок системи координат. При деякому фіксованому значенні кутовий коефіцієнт
прямої також буде фіксованим і пряма займе певне положення. При зміні значень
пряма
буде повертатися навколо початку системи координат.
Далі, визначемо, як буде вести себе кутовий коефіцієнт при монотонному зростанні
. Для цього, знайдемо похідну від
по
:
Виходячи з того, що знаменник похідної завжди приймає дотнє значення, а чисельник від не залежить, то можна зробити висновок, що похідна має постійний знак і при збільшенні
кутовий коефіцієнт буде тільки зростати або спадати, а пряма буде повертатися в одну сторону. Якщо кутовий коефіцієнт прямої має додатнє значення, то пряма обертається проти годинникової стрілки, при від'ємному значенні
— за годинниковою стрілкою. Встановивши напрямок обертання, знаходимо вершину або вершини багатогранника, в яких функція приймає максимальне (мінімальне) значення, і таким чином знаходимо розв'язок задачі дробово-лінійного програмування. Відмітимо, що при цьому можливі наступні випадки:
- Область допустимих розв'язків обмежена — максимум і мінімум досягаються в її кутових точках.
- Область допустимих розв'язків необмежена, проте існують кутові точки, в яких цільова функція приймає максимальне і мінімальне значення.
- Область допустимих розв'язків необмежена, є один з екстремумів. Наприклад, мінімум досягається в одній з вершин області і існує так званий асимптотичний максимум.
- Область допустимих розв'язків необмежена. Максимум і мінімум є асимптотичним.
Випадок коли багатокутник розв'язків замкнутий
Випадок, коли багатокутник розв'язків необмежений (точка максимуму і точка мінімуму існує)
Випадок, коли багатокутник розв'язків необмежений (точки максимуму не існує)
Випадок коли багатокутник розв'язків необмежений і задача немає рішення (точки максимуму і точки мінімуму не існує)
Далі, на основі вище сказаного запишемо основні етапи, з яких складається графічний метод при розв'язку задач дробово-лінійного програмування, після чого перейдемо до рішення анонсованої задачі. Отже, процес знаходження рішення задачі (1) — (3) включає наступні етапи:
- В системі обмежень задачі замінюють знаки нерівностей на знаки рівностей і будують прямі, що визначаються цими рівностями.
- Знаходять півплощини, що визначаються кожною з нерівностей системи обмежень задачі.
- Знаходять багатокутник розв'язків задачі.
- Будують пряму (4), рівняння якої отримують шляхом покладання значенню цільової функції (1) рівним деякому постійному числу.
- Визначають точку максимуму (мінімуму) або встановлюють нерозв'язність задачі.
Розв'язок задачі дробово-лінійного програмування графічним методом — приклад:
Знайти мінімальне значення функції мети:
при наступних обмеженнях:
Щоб знайти рішення даної задачі графічно, на першому кроці будуємо багатокутник розв'язків. Як видно з малюнку нижче, ним являється трикутник . Значить, функція приймає мінімальне значення в одній з його вершин, а якщо бути більш точним, то виходячи з того, що оптимальне значення знаходиться шляхом обертання прмої, що описується рівнянням цільової функції, навколо початку системи координат, відразу можна зробимо висновок, що екстремальними точками будуть вершини
і
.
Багатокутник розв'язків задачі
Для визначити, яка з цих вершин буде точкою мінімум, а яка точкою максимум, скористаємось наведеними вище міркуваннями. Тобто, для функції мети задачі запишемо рівняння виду (4), та виразимо з нього змінну . В результаті отримаємо:
Після цього, знайшовши для отриманого кутового коефіцієнта похідну по
(
), бачимо, що вона при будь-якому
приймає додатнє значення, тобто із збільшенням значення
, кутовий коефіцієнт
також збільшується. Отже, пряму
необхідно обертати проти годинникової стрілки, і у вершині
значення функції мети буде найменшим, а у вершині
— найбільшим.
Знаходження точки в якій функція мети приймає свого мінімального значення
Відмітимо, що визначення точки мінімуму можна було б здійснити і дещо іншим, простішим, способом. Визначивши по малюнку екстремальні точки, та розв'язавши відповідні системи лінійних рівнянь отримаємо, так чи інакше необхідні, їх координати:
Далі, обчисливши значення функції мети в цих точках та порівнявши їх між собою, приходимо до висновку, що цільова функція приймає свого мінімального значення в точці :