Дробово-лінійне програмування:

Розв’яжіть графічно задачу дробово-лінійного програмування:

за умов:

.

Розв’язання. Побудуємо на площині область допустимих розв’язків задачі. Маємо трикутник АВС.

Рис. 7.1

Цільова функція задачі являє собою пряму, що обертається навколо початку системи координат (на рис. 7.1 позначена пунктиром). Отже, залежно від напрямку обертання точками максимуму та мінімуму будуть А і С.

Скористаємося правилами визначення максимального та мінімального значень цільової функції. Перевіримо умову

,

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

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

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

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

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

- багатокутник розв’язків задачі необмежений, однак існують кутові точки, в яких досягаються максимальне та мінімальне значення цільової функції;

- багатокутник розв’язків задачі необмежений і досягається лише один із екстремумів;

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

Виконуючи зазначений порядок дій, маємо: С — точка максимуму, а точка А є точкою мінімуму цієї задачі. Знаходимо точку перетину відповідних прямих (точка максимуму чи мінімуму) і розв’язуємо систему рівнянь щодо цих прямих. Знаходимо x1 та x2, підставляємо в «Z»

5. У наведених далі задачах(Sensetive-аналіз):

а) побудуйте економіко-математичні моделі початкової й двоїстої задач;

б) приведіть задачі до канонічного виду й дайте економічне тлумачення основних й допоміжних змінних двох задач;

в) з наведеної останньої симплексної таблиці початкової задачі запишіть оптимальні плани і ;

г) визначте дефіцитні й недефіцитні ресурси, рентабельну та збиткову продукцію;

д) знайдіть межі зміни обсягів дефіцитних ресурсів, в котрих оцінка ресурсу залишається сталою (аналіз двоїстих оцінок на стійкість);

е) знайдіть межі зміни обсягів недефіцитних ресурсів;

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

ж) в якому випадку розширення асортименту випуску за рахунок введення нової продукції буде доцільним, чи недоцільним?

5.1. Підприємство виготовляє три види продукції а, в і с, використовуючи для цього три види ресурсів I, II, III. Норми витрат усіх ресурсів на одиницю продукції та запаси ресурсів наведено в табл.1

Таблиця 1

І II III

18 6 5

15 4 3

12 8 3

360 192 180

Відома ціна одиниці продукції кожного виду: А - 9 ум.од., В -10 ум. од. і С - 16 ум.од. Визначити план виробництва продукції, що забезпечує підприємству найбільший доход.

Остання симплекс-таблиця даної задачі має такий вигляд

Розв’язок: Математична модель прямої та двоїстої задач мають вигляд:

а) Z=

Де - обсяг виробництва j –го виду.

Де y i - оцінка одиниці і-го виду ресурсу.

б) основні змінні , , характеризують кількість продукції А, В, С, яку необхідно виготовляти. Додаткові змінні , , - характеризують залишки відповідних ресурсів І, ІІ, ІІІ.

в) =(0,8,20,0,0,96)

= (2/9, 5/3, 0)

г) відповідно до оптимального плану прямої задачі, необхідно виготовляти продукцію В і С у кількості відповідно 8 і 20 од, ці види продукції і будуть рентабельними. Випуск продукції а буде нерентабельним ( =0). І і ІІ ресурс використовуються повність, отже вони є дефіцитними, а ІІІ ресурс у процесі виробництва використовується неповністю і є недефіцитним.

д) Дефіцитними є ресурси І та ІІ.

Математична постановка:

Приріст запасу першого ресурсу позначимо через

Приріст запасу другого ресурсу позначимо через

е)

ж ) Дослідимо питання про доцільність введення нового n+1-го виду продукції. - витрати кожного виду ресурсу на виготовлення одиниці такої продукції.

- ціна її реалізації.

Обмеження, що описує витрати на виробництво нового виду продукції:

Рентабельною є продукція, для якої відповідне обмеження виконується як рівняння, а нерентабельною, якщо ліва частина нерівності(витрати ресурсів на виробництво одиниці продукції) перевищує праву (ціну реалізації одиниці продукції).

Розширення асортименту за рахунок нової продукції буде доцільним якщо витрати на виробництво продукції будуть менші, ніж ціна реалізації.

5.2 Підприємство виготовляє продукцію видів A, B, C для чого використовує три види ресурсів І, ІІ, ІІІ. Норми витрат усіх ресурсів на одиницю кожної продукції та обсяги ресурсів на підприємстві наведено в табл.. 1

Таблиця 1

Вид ресурсу	Норма витрат на одиницю продукції за видами			Запас ресурсу
	А	В	С
І II III	4 3 1	2 1 2	1 3 5	180 210 244

Відома ціна одиниці продукції кожного виду: А - 10 ум.од., В -14 ум.од. і С - 12 ум.од. Визначити план виробництва продукції, що забезпечує підприємству найбільший доход. Остання симплекс-таблиця, що містить оптимальний план задачі, має такий вигляд (табл.2)

Розв’язок: Математична модель прямої та двоїстої задач мають вигляд:

а) Z=

Де - обсяг виробництва j –го виду.

Де y i - оцінка одиниці і-го виду ресурсу.

б) основні змінні , , характеризують кількість продукції А, В, С, яку необхідно виготовляти. Додаткові змінні , , - характеризують залишки відповідних ресурсів І, ІІ, ІІІ.

в) =(0,82,16,0,80,0)

= (23/4, 0, 5/4)

г) відповідно до оптимального плану прямої задачі, необхідно виготовляти продукцію В і С у кількості відповідно 82 і 16 од, ці види продукції і будуть рентабельними. Випуск продукції А буде нерентабельним ( =0). І і ІІІ ресурси використовуються повність( = =0), отже вони є дефіцитними, а ІІІресурс у процесі виробництва використовується неповністю ( =80) і є недефіцитним.

д) Дефіцитними є ресурси І та ІІІ.

Математична постановка:

Приріст запасу першого ресурсу позначимо через

Приріст запасу третього ресурсу позначимо через

е)

ж ) Дослідимо питання про доцільність введення нового n+1-го виду продукції. - витрати кожного виду ресурсу на виготовлення одиниці такої продукції.

- ціна її реалізації.

Обмеження, що описує витрати на виробництво нового виду продукції:

Рентабельною є продукція, для якої відповідне обмеження виконується як рівняння, а нерентабельною, якщо ліва частина нерівності(витрати ресурсів на виробництво одиниці продукції) перевищує праву (ціну реалізації одиниці продукції).

Розширення асортименту за рахунок нової продукції буде доцільним якщо витрати на виробництво продукції будуть менші, ніж ціна реалізації.

Метод розв'язування задачі дрібно лінійного програмування у загальному вигляді.

Економічна і математична постановка задачі

Розв'язуючи економічні задачі, часто за критерій оптимальності беруть показники рентабельності, продуктивності праці тощо, які математично подаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так:

за умов

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

Алгоритм розв'язування задачі дробово-лінійного програму­вання передбачає зведення її до задачі лінійного програмування. Щоб виконати таке зведення, позначимо

зробимо заміну змінних

і запишемо економіко-математичну модель:

за умов

Дістали задачу лінійного програмування, яку можна розв'язати симплексним методом. Нехай оптимальний план

Оптимальні значення х0j знайдемо за формулою