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

ВСТУП

 

 

Моделювання в наукових дослідженнях стало застосовуватися  ще в глибокій старовині і поступово  захоплювало все нові області наукових знань: технічне конструювання, будівництво і архітектура, астрономію, фізику, хімію, біологію і, нарешті, суспільні науки. Великі успіхи і визнання практично у всіх галузях сучасної науки принесло методу моделювання ХХ ст. Однак методологія моделювання довгий час розвивалася незалежно окремими науками. Була відсутня єдина система понять, єдина термінологія. Лише поступово стала усвідомлюватись роль моделювання як універсального методу наукового пізнання. Термін "модель" широко використовується в різних сферах людської діяльності і має безліч смислових значень. Розглянемо тільки такі "моделі", які є інструментами отримання знань. Модель - це такий матеріальний об'єкт, який в процесі дослідження заміщає об'єкт-оригінал так, що його безпосереднє вивчення дає нові знання про об'єкт-оригінал.

Під моделюванням розуміється процес побудови, вивчення та застосування моделей. Воно тісно пов'язане з такими категоріями, як абстракція, аналогія, гіпотеза та ін. Процес моделювання обов'язково включає й побудову абстракцій за аналогією, і конструювання наукових гіпотез. Головна особливість моделювання в тому, що це метод опосередкованого пізнання з допомогою об'єктів-заступників. Модель виступає як своєрідний інструмент пізнання, який дослідник ставить між собою і об'єктом і за допомогою якого вивчає об'єкт що його цікавить. Саме ця особливість методу моделювання визначає специфічні форми використання абстракцій, аналогів, гіпотез, інших категорій і методів пізнання.

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

Моделювання - циклічний процес. Це означає, що за першим з чотирьох етапів циклів може послідувати другий, третій і т.д. При цьому знання про досліджуваний об'єкт розширюються і уточнюються, а вихідна модель постійно вдосконалюється. Недоліки, виявлені після першого циклу моделювання, обумовлені малим знанням об'єкта і помилками в побудові моделі, можна виправити в наступних циклах. У методології моделювання, таким чином, закладені великі можливості саморозвитку.

 

1 ТЕОРЕТИЧНА ЧАСТИНА

 

 

1.1 Економічна і математична постановка задачі дробово–лінійного програмування.

 

 

Розв’язуючи економічні задачі, часто  як критерії оптимальності беруть рівень рентабельності, продуктивність праці тощо. Ці показники математично виражаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так (розглянемо задачу визначення оптимальних обсягів виробництва продукції): позначимо через прибуток від реалізації одиниці -го виду продукції, тоді загальний прибуток можна виразити формулою: ; якщо — витрати на виробництво одиниці -го виду продукції, то — загальні витрати на виробництво. У разі максимізації рівня рентабельності виробництва цільова функція має вигляд:

 

                                           

                                                 (1.1.1)

 

за умов виконання обмежень щодо використання ресурсів:

 

;                                                         (1.1.2)

 

.                                                                   (1.1.3)

 

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

Очевидно, що задача (1.1.1)—(1.1.3) відрізняється від звичайної задачі лінійного програмування лише цільовою функцією, що дає змогу застосовувати для її розв’язування за певного модифікування вже відомі методи розв’язання задач лінійного програмування.

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

 

 

 

 

1.2 Геометрична інтерпретація задачі дробово-лінійного програмування.

 

 

У разі, коли задача дробово-лінійного  програмування містить лише дві змінні, для її розв’язування зручно скористатися графічним методом.

Нехай маємо таку задачу:

 

                                                                 (1.2.1)

 

за умов:

                                                                   (1.2.2)

 

,                                                               (1.2.3)

 

Спочатку, як і для  звичайної задачі лінійного програмування  будуємо геометричне місце точок системи нерівностей (1.2.2), що визначає деякий багатокутник допустимих розв’язків.

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

.

Після елементарних перетворень  дістанемо:

 

 

або

 

                            

.                                                            (1.2.4)

 

Останнє рівняння описує пряму, що обертається навколо початку системи координат залежно від зміни значень х₁ та х₂.

Розглянемо кутовий  коефіцієнт нахилу прямої (1.2.4), що виражає цільову функцію:

 

    .                                                                (1.2.5)

 

Отже, кутовий коефіцієнт являє собою функцію від Z. Для  визначення умов зростання (спадання) функції (1.2.5) дослідимо зміну знака її похідної:

 

                       (1.2.6)

 

Використовуючи  формулу (1.2.6), можна встановити правила пошуку максимального (мінімального) значення цільової функції:

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

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

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

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

за умов:

.

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

Рис. 1.2.1

 

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

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

,

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

Виконуючи зазначений порядок  дій, маємо: С — точка максимуму, а точка А є точкою мінімуму цієї задачі.

 

1.3 Розв’язування дробово-лінійної задачі зведенням до задачі лінійного програмування.

Нехай потрібно розв’язати задачу (1.3.1)—(1.3.3). Позначимо

і введемо заміну змінних  . Тоді цільова функція (1.3.1) матиме вигляд:

.

Отримали  цільову функцію, що виражена лінійною залежністю.

Оскільки  , то звідси маємо: . Підставимо виражені через нові змінні значення в систему обмежень (1.3.2):

крім того, з початкової умови

.

Умова (1.3.3) стосовно невід’ємності змінних набуває вигляду:

.

Виконані перетворення приводять до такої моделі задачі:

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

Допустимо, що оптимальний  розв’язок останньої задачі існує  і позначається:      .

Оптимальні значення початкової задачі (1.3.1)—(1.3.3) визначають за формулою: .

 

Приклад 1.3.1. Сільськогосподарське акціонерне товариство з обмеженою відповідальністю, яке розміщене у Лісостепу України, бажає оптимізувати структуру виробництва. Критерієм оптимальності вибрали максимізацію рівня рентабельності як відношення прибутку до собівартості. У табл. 1.3.1. маємо дані про види діяльності, якими керівництво товариства передбачає займатися.

Таблиця 1.3.1.

Техніко-економічні показники головних  
напрямів виробництва

Показник	Напрям виробництва
	озима   пшениця	цукрові   буряки	корови   (продуктивність, кг)				кормові культури	ресурс
			5000	4500	4000	3500
Урожайність, т/га	4	35	—	—	—	—	6	—
Собівартість, грн/т	600	250	600	700	800	900	200	—
Ціна, грн/т	800	300	1000	1000	1000	1000	—	—
Вихід кормів, т кор. од./га	4,8	2,0	—	—	—	—	6	—
Затрати трудових ресурсів, людино-днів/га (гол.)	4	25	6	6	6	6	3	26 000
Затрати механізованої праці, людино-днів/га (гол.)	2	8	3	3	3	3	2	11 000
Частка корів	—	—	0,1	0,2	0,3	0,4	—	—
Потреба у кормах, т кор. од./гол.	—	—	5	4,7	4,4	4,1	—	—

 

Акціонерне товариство має 2500 га ріллі. Для виготовлення кормів передбачається використовувати 20 % урожаю озимої пшениці та 30 % — цукрових буряків.

Знайти оптимальну структуру  виробництва.

Розв’язання. Введемо позначення:

х₁ — площа посіву озимої пшениці, га;

х₂ — площа посіву цукрових буряків, га;

х₃ — площа посіву кормових культур, га;

х₄ — кількість корів продуктивністю 5000 кг/рік;

х₅ — кількість корів продуктивністю 4500 кг/рік;

х₆ — кількість корів продуктивністю 4000 кг/рік;

х₇ — кількість корів продуктивністю 3500 кг/рік.

Запишемо критерій оптимальності:

за умов дотримання таких  обмежень:

1. Обмеження щодо використання  ресурсів:

а) використання ріллі:

;

б) використання живої  праці:

;

в) використання механізованої  праці:

.

2. Обмеження стосовно  дотримання сівозмін:

а) посівна площа кормових культур має бути більшою або дорівнювати площі під озимою пшеницею:

;

б) посівна площа озимої пшениці має бути більша або дорівнювати площі під цукровими буряками:

.

3. Структура корів  за продуктивністю:

а) балансове рівняння щодо поголів’я корів:

,

де — загальне поголів’я корів;

б) частка корів продуктивністю 5000 кг/рік:

;

в) частка корів продуктивністю 4500 кг/рік:

;

г) частка корів продуктивністю 4000 кг/рік:

;

д) частка корів продуктивністю 3500 кг/рік:

.

4. Забезпеченість корів  кормами:

Невід’ємність змінних:

( ).

Щоб знайти розв’язок за цією моделлю, необхідно зробити відповідну заміну змінних. Нехай:

і .

Тоді маємо таку лінійну  економіко-математичну модель:

за умов:

1.  ;

;

.

2.

3.