Розв’язок задачі дробово-лінійного програмування графічним методом

При розгляді теоретичної частини задачі дробово-лінійного програмування, а зокрема, при розгляді конкретної задачі такого типу, нами було анонсовано, що в подальшому дану задачу буде розв’язано з допомогою графічного методу та методу, який базується на зведенні задач з дробово-лінійною цільовою функцією до задачі лінійного програмування. Сьогодні розглянемо перший з них, але перш ніж приступити до розв’язку задачі, розглянемо алгоритм даного методу більш детально. Для цього, припустимо, що нам потрібно знайти максимальне (мінімальне) значення функції мети (де ):

при наступних обмеженнях:

Щоб знайти рішення задачі (1) – (3), спочатку, як і у випадку задачі лінійного програмування, знаходимо багатокутник рішень, який визначається обмеженнями (2) і (3). Припускаючи, що цей багатокутник не порожній, покладаємо значення функції (1) рівним деякому числу :

З отриманого виразу знайдемо значення змінної :

Тобто, в результаті, ми отримали рівняння прямої, яка проходить через початок системи координат. При деякому фіксованому значенні  кутовий коефіцієнт прямої також буде фіксованим і пряма займе певне положення. При зміні значень  пряма буде повертатися навколо початку системи координат.

Далі, визначемо, як буде вести себе кутовий коефіцієнт  при монотонному зростанні . Для цього, знайдемо похідну від  по :

Виходячи з того, що знаменник похідної завжди приймає дотнє значення, а чисельник від  не залежить, то можна зробити висновок, що похідна має постійний знак і при збільшенні  кутовий коефіцієнт буде тільки зростати або спадати, а пряма буде повертатися в одну сторону. Якщо кутовий коефіцієнт прямої має додатнє значення, то пряма обертається проти годинникової стрілки, при від’ємному значенні  – за годинниковою стрілкою. Встановивши напрямок обертання, знаходимо вершину або вершини багатогранника, в яких функція приймає максимальне (мінімальне) значення, і таким чином знаходимо розв’язок задачі дробово-лінійного програмування. Відмітимо, що при цьому можливі наступні випадки:

1. Область допустимих розв’язків обмежена – максимум і мінімум досягаються в її кутових точках.

   

Випадок коли багатокутник розв’язків замкнутий

2. Область допустимих розв’язків необмежена, проте існують кутові точки, в яких цільова функція приймає максимальне і мінімальне значення.



Випадок, коли багатокутник розв’язків необмежений (точка максимуму і точка мінімуму існує)

3. Область допустимих розв’язків необмежена, є один з екстремумів. Наприклад, мінімум досягається в одній з вершин області і існує так званий асимптотичний максимум.



Випадок, коли багатокутник розв’язків необмежений (точки максимуму не існує)

4. Область допустимих розв’язків необмежена. Максимум і мінімум є асимптотичним.

   

Випадок коли багатокутник розв’язків необмежений і задача немає рішення (точки максимуму і точки мінімуму не існує)

Далі, на основі вище сказаного запишемо основні етапи, з яких складається графічний метод при розв’язку задач дробово-лінійного програмування, після чого перейдемо до рішення анонсованої задачі. Отже, процес знаходження рішення задачі (1) – (3) включає наступні етапи:

1. В системі обмежень задачі замінюють знаки нерівностей на знаки рівностей і будують прямі, що визначаються цими рівностями.
2. Знаходять півплощини, що визначаються кожною з нерівностей системи обмежень задачі.
3. Знаходять багатокутник розв’язків задачі.
4. Будують пряму (4), рівняння якої отримують шляхом покладання значенню цільової функції (1) рівним деякому постійному числу.
5. Визначають точку максимуму (мінімуму) або встановлюють нерозв’язність задачі.

Розв’язок задачі дробово-лінійного програмування графічним методом – приклад:

Знайти мінімальне значення функції мети:

при наступних обмеженнях:

Щоб знайти рішення даної задачі графічно, на першому кроці будуємо багатокутник розв’язків. Як видно з малюнку нижче, ним являється трикутник . Значить, функція приймає мінімальне значення в одній з його вершин, а якщо бути більш точним, то виходячи з того, що оптимальне значення знаходиться шляхом обертання прмої, що описується рівнянням цільової функції, навколо початку системи координат, відразу можна зробимо висновок, що екстремальними точками будуть вершини і .

Багатокутник розв’язків задачі

Для визначити, яка з цих вершин буде точкою мінімум, а яка точкою максимум, скористаємось наведеними вище міркуваннями. Тобто, для функції мети задачі запишемо рівняння виду (4), та виразимо з нього змінну . В результаті отримаємо:

Після цього, знайшовши  для отриманого кутового коефіцієнта  похідну по  (), бачимо, що вона при будь-якому  приймає додатнє значення, тобто із збільшенням значення , кутовий коефіцієнт  також збільшується. Отже, пряму  необхідно обертати проти годинникової стрілки, і у вершині  значення функції мети буде найменшим, а у вершині  – найбільшим.

Знаходження точки в якій функція мети приймає свого мінімального значення

Відмітимо, що визначення точки мінімуму можна було б здійснити і дещо іншим, простішим, способом. Визначивши по малюнку екстремальні точки, та розв’язавши відповідні системи лінійних рівнянь отримаємо, так чи інакше необхідні, їх координати:

Далі, обчисливши значення функції мети в цих точках та порівнявши їх між собою, приходимо до висновку, що цільова функція приймає свого мінімального значення в точці :

Блок-схема алгоритму знаходження розв’язку задачі дробово-лінійного програмування графічним методом