Прикладні аспекти оптимізації

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

Справжнім початком математичного програмування в сучасному розумінні вважають праці радянського вченого Л. В. Канторовича. Наприкінці 30-х років у Ленінградському університеті ним уперше були сформульовані та досліджувались основні задачі, критерії оптимальності, економічна інтерпретація, методи розв'язання та геометрична інтерпретація результатів розв'язання задач лінійного програмування (1939 року Л. В. Канторович оприлюднив монографію «Математичні методи організації і планування виробництва»).

Канторович Леонід Віталійович (1912 - 1986) - радянський математик і економіст, піонер і один з творців лінійного програмування. Лауреат Нобелівської премії з економіки 1975 року «за внесок у теорію оптимального розподілу ресурсів» (єдиний радянський вчений, удостоєний Нобелівської премії з економіки).

В 1947 році американським вченим Дж. Данцигом був розроблений основний метод розв'язування задач лінійного програмування — симплексний метод, що вважається початком формування лінійного програмування як самостійного напрям-ку в математичному програмуванні.

Сам термін «лінійне програмування» був введений дещо пізніше, 1951 року, у працях того ж Дж. Данцига та Г. Кумпанса. Однак у своїй монографії Дж. Данциг зазначає, що Л. В. Канторовича слід визнати першим, хто виявив, що широке коло важливих виробничих задач може бути подане у чіткому математичному формулюванні, яке уможливлює підхід до таких задач з кількісного боку та розв'язання їх чисельними методами.

Джордж Бернард Данциг (1914-2005) американський математик, розробник симплексного алгоритму, застосовуваного в рішеннях завдань симплекс-методом.

Тьяллінг Чарльз Купманс (1910- 1985) американський економіст і математик, Нобелівської премії з економіки 1975 року «за внесок у теорію оптимального розподілу ресурсів» (разом з Л.В. Канторовичем)

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

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

Оптимізаційні задачі (ОЗ) вирішуються за допомогою оптимізаційних моделей (ОМ) методами математичного програмування.

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

Моделі усіх задач оптимізації складаються з наступних елементів:

1. Змінні - невідомі величини, які потрібно знайти при вирішенні задачі.

2. Обмеження - умови, яким повинні задовольняти змінні.

3. Критерій оптимальності - ключовий показник ефективності моделі, який залежить від змінних і є метою, ключовим показником ефективності моделі. Математичною  формою  критерію оптимальності  є цільова функція.

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

Кожна оптимізаційна модель послідовно проходить наступні основні етапи:

1. Постановка завдання.

2. Побудова (складання) математичної моделі.

3. Розв’язання задачі.

4. Аналіз одержаного рішення і коректування моделі у разі потреби.

5. Реалізація знайденого рішення на практиці.

Вивченням проблем, пов'язаних з вибором оптимальних рішень, займаються теорія дослідження операцій та теорія прийняття рішень.

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

Класифікація оптимізаційних моделей і методів.

1. За характером взаємозв'язку між змінними виділяють наступні моделі:

а) лінійні, коли функціональні зв'язки в системі обмежень і цільова функція - лінійні функції;

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

2. За характером зміни змінних

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

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

3. За обліком фактора часу

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

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

4. За наявністю інформації про змінні

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

б) стохастичні (в умовах невизначеності  або неповної визначеності, в умовах ризику - містять випадкові функції та величини.

5. За кількістю критеріїв ефективності:

а) однокритеріальні (прості) завдання, коли реальна ситуація дозволяє визначити єдину цільову функцію.

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

6. За видом цільової функції виділяють наступні методи:

а) лінійне програмування - цільова функція і функції в системі обмежень - лінійні функції;

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

в) нелінійне програмування - цільова функція і / або функції в системі обмежень - нелінійні функції;

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

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

е) стохастичне програмування - функції носять випадковий характер;

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

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

Найбільш опрацьованими є методи лінійного програмування.

1.2. Постановка та приклади задачі лінійного програмування (ЗЛП)

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

Задана система умов (обмежень) з n невідомих (змінних) х₁, х₂, …, х_n

та умова невід’ємності  змінних:

.

Необхідно знайти оптимальний розв’язок - значення змінних, які задовольняють вказаним умовам, тоді як цільова функція набуває екстремального (максимального чи мінімального) значення.

Задача про найкраще використання ресурсів

Класична постановка. Підприємство  випускає  n різних виробів. Для їх виробництва потрібні m різних видів ресурсів (сировини, допоміжних матеріалів, робочого часу і т.д.). Ці ресурси обмежені і складають в плановий період b₁, b₂, ..., b_m умовних одиниць. Відомі також технологічні коефіцієнти a_ij, які вказують, скільки одиниць i-го ресурсу потрібно для виробництва вироби j-го виду (i = 1, m, j = 1, n). Нехай вигода, одержувана підприємством при виробництві (реалізації) одиниці виробу j-го виду, дорівнює c_j. У плановому періоді всі показники b_i, a_ij і c_j передбачаються постійними.

 

Задача У господарстві є трактори Т-70С, ДТ-75М та МТЗ-80, що підлягають ремонту, на здійснення можуть бути витрачені 218000 грн. Вартість ремонту кожного з тракторів та змінний еталонний виробіток трактора кожної марки  наведені в табл. 1.3.

Таблиця 1.4

Вартість ремонту тракторів та їх виробіток

Показники	Марки тракторів
	Т-70С	ДТ-75М	МТЗ-80
Вартість ремонту трактора, грн.	17000	22000	26000
Змінний виробіток трактора, ум. ет. га	4,2	7	4,1

Скільки тракторів і яких саме слід відремонтувати, щоб забезпечити максимальний змінний виробіток в умовних еталонних гектарах, враховуючі, що гусеничних тракторів повинно бути не більше 80% від числа колісних, а тракторів ДТ-75М може бути відремонтовано не більше 4-х.

Математична модель:

Система змінних

Кількість тракторів, шт.

х₁ - Т-70С

х₂ - ДТ-75М

х₃ - МТЗ-80

Система обмежень

1. По фінансових ресурсах:         17000х₁+22000х₂+26000х₃≤218000

2. За кількістю колісних тракторів    х₁+х₂≤ 0,8х₃   або х₁+х₂-0,8х₃ ≤ 0

3. За кількістю тракторів ДТ-75М            х₂≤4

Критерій оптимальності - максимальний змінний виробіток в умовних еталонних гектарах

F=4,2х₁+ 7х₂+4,1х₃→ mах

Таблиця 1.5

Матриця економіко-математичної задачі оптимізації ремонту тракторів

 

Висновок: для забезпечення максимального змінного виробітку обсягом 48,5 ум. ет. га господарству необхідно відремонтувати максимально можливу кількість  тракторів ДТ-75М – 4 – та 5  тракторів МТЗ-80, трактори Т-70С ремонтувати недоречно.

 

Задача про суміші

    До групи задач про суміші відносять завдання з відшукання найбільш дешевого набору з певних вихідних матеріалів, що забезпечують отримання суміші із заданими властивостями. Іншими словами, одержувані суміші повинні мати у своєму складі n різних компонентів в певних кількостях, а самі компоненти є складовими частинами m вихідних матеріалів.

 

Задача 1.5 Щодня в ресторані фірмовий коктейль (місткість порції - 0,33 л) замовляють у середньому 600 відвідувачів. Відповідно до рецепта у складі коктейлю повинно бути:

• не менше 20 %, але й не більше 35 % спирту;

• не менше 2 % цукру;

• не більше 5 % домішок;

• не більше 76 % води;

• не менше 7 %, але й не більше 12 % соку.

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

Таблиця 1.8

Склад, запаси та вартість напоїв

Напій	Вміст,%				Щоденний запас, л	Вартість, гр. од./л
	Спирт	Вода	Цукор	Домішки
Горілка	40	57	1	2	50	30
Біле вино	18	67	9	6	184	20
Сік	-	88	8	4	46	10

Менеджер ресторану бажає  визначити такий склад коктейлю, щоб його вартість була мінімальною.

Математична модель:

Система змінних:

Кількість напою в складі коктейлю, л

х₁ - горілка

х₂ - вино

х₃ - сік

Система обмежень:

І. За загальним об’ємом коктейлю, л

1.місткість порції:     

х₁+х₂+х₃ = 0,33

ІІ. За щоденними запасами складових коктейлю, л

2. за запасами горілки               

600 х₁≤50

3. за запасами вина                    

600 х₂≤184

4. за запасами соку                   

600 х₃≤46

ІІІ. За вмістом речовин у коктейлі, л

5. спирту, не менше

0,4 х₁+0,18 х₂ ≥ 0,2*0,33      або    0,4 х₁+0,18 х₂≥ 0,066

6. спирту, не більше

0,4 х₁+0,18 х₂ ≤0,35*0,33      або    0,4 х₁+0,18 х₂≤0,116

7. цукру, не менше

0,01х₁+0,09х₂+0,08х₃ ≥ 0,02*0,33      або    0,01х₁+0,09х₂+0,08х₃≥ 0,007

8. домішок, не більше

0,02х₁+0,06х₂+0,04х₃≤0,05*0,33      або    0,02х₁+0,06х₂+0,04х₃≤0,017

9. води, не більше

0,57х₁+0,67х₂+0,88х₃≤0,76*0,33      або    0,57х₁+0,67х₂+0,88х₃≤0,251

10. соку, не менше                х₃ ≥ 0,07*0,33      або    х₃ ≥ 0,023

11. соку, не більше                 х₃≤0,12*0,33      або    х₃≤0,040

 

Критерій оптимальності – мінімальна вартість коктейлю, гр. од.

F=30х₁+ 20х₂+10х₃→ min

Таблиця 1.9

Матриця економіко-математичної задачі оптимізації складу коктейлю

 

Висновок: мінімальна вартість порції коктейлю 7,2 гр.од. досягається при додаванні до його складу 80 мл горілки, 220 мл білого вина та 20 мл соку.

 

 

Цілочисленне програмування

 Задача 1.6 Для роботи в новому офісі компанії Expert Service менеджер з персоналу набирає нових співробітників на повну ставку. Мінімальна потреба в співробітниках в різні дні тижня наведені в табл. 1.10.

Таблиця 1.10

Потреба в персоналі компанії Expert Service

Згідно угоди з профспілкою працівник, найнятий на повну ставку, повинен відпрацювати поспіль 5 днів, а потім мати поспіль 2 дні відпочинку.

Необхідно скласти оптимальний розклад роботи працівників, щоб потреба у найманому персоналі була мінімальною.

Математична модель:

Система змінних

Кількість співробітників, які починають роботу у:

 -  понеділок

 - вівторок

 - середу

 - четвер

 - п'ятницю

х₆ - четвер

х₇ - п'ятницю

 

Система обмежень

1.     Понеділок:                 х₁+х₄+х₅+х₆+х₇≥17

2.     Вівторок                    х₁+х₂+х₅+х₆+х₇≥13

3.     Середа                       х₁+х₂+х₃+х₆+х₇≥15

4.     Четвер                        х₁+х₂+х₃+х₄+х₇≥19

5.     П’ятниця                    х₁+х₂+х₃+х₄+х₅≥14

6.     Субота                       х₂+х₃+х₄+х₅+х₆ ≥16

7.     Неділя                         х₃+х₄+х₅+х₆+х₇≥11

х₁, х₂, х₃, х₄, х₅, х₆, х₇ – цілі числа

 

Критерій оптимальності – мінімальна кількість найманого персоналу, осіб

F=х₁+ х₂+х₃+х₄+х₅+х₆+х₇ → min

 

 

Таблиця 1.11

Матриця економіко-математичної задачі оптимізації розкладу роботи

Назва обмеження	Кількість робітників, що працюють з							Обмеження
	Пн.	Вт	Сер	Чт	Пт	Сб	Нд
	х1	х2	х3	х4	х5	х6	х7	Знак	Права частина
Потреба в персоналі, осіб:
1. у Пн.	1			1	1	1	1	≥	17
2. у Вт	1	1			1	1	1	≥	13
3. у Сер	1	1	1			1	1	≥	15
4. у Чт	1	1	1	1			1	≥	19
5.у Пт	1	1	1	1	1			≥	14
6.у Сб		1	1	1	1	1		≥	16
7. у Нд			1	1	1	1	1	≥	11
Кількість найманого персоналу, осіб	1	1	1	1	1	1	1	min	23

 

Висновок: згідно оптимального плану необхідно, щоб з понеділка починали працювати 2 співробітники, з вівторка та середи – по 3, в четвер - 7, починати з п’ятниці не має ні один з працівників, а з суботи та неділі виходять на роботу ще по 4 співробітники. При цьому кількість найманого персоналу складе 23 особи.

 

Задача про ранець

       В класичній постановці йдеться мандрівника, який зібрався у похід і повинен упакувати в ранець різні корисні предмети n найменувань, причому можуть знадобитися кілька однакових предметів. Маються m обмежень такого типу, як вага, обсяг, лінійні розміри і т.д. Нехай а_ij - i-я характеристика предмета j-го найменування (i = 1, m, j = 1, n), b_i - обмеження за вагою, обсягом і т.д., x_j - кількість предметів j-го найменування, запланована до навантаження в ранець (j = 1, n). Вважається, що відома корисність c_j одного предмета j.

Задача У склад місткістю 90 куб. м потрібно помістити три різних типи обладнання. Характеристика предметів дана в табл 1.12

Таблиця 1.12

Об'єм та вартість обладнання

Визначити, скільки обладнання кожного типу слід помістити на склад так, щоб загальна вартість складованого обладнання була максимальною.

Математична модель:

Система змінних

Кількість одиниць обладнання:

 -  типа 1

 - типа 2

 - типа 3

Система обмежень

1.     За місткістю складу, куб. м        24х₁+19х₂+16х₃≤90

 

2.     х₁, х₂, х₃ – цілі чила

Критерій оптимальності – максимальна вартість складованого обладнання, дол.

F=960х₁+ 500х₂+250х₃→ mах

 

 

Висновок: на склад слід помістити 3 одиниці обладнання типу 1 та одиницю типу 3, що забезпечить максимальну вартість обладнання в розмірі 3130 дол.

 

Задачі  з булевими (двоїчними, бінарними) змінними

До задач з булевими змінними належать завдання, змінні в яких можуть приймати тільки два значення: 0 або 1.

Задача Торгова компанія «Trade» має свої супермаркети в Києві, Харкові, Дніпропетровську, Донецьку, Запоріжжі, Полтаві та Сімферополі. У результаті помилок менеджменту економічне становище компанії стало погіршуватися, їй довелося взяти кредит у розмірі 65 млн. грн. і зрештою, щоб вчасно його погасити, терміново продавати деякі зі своїх супермаркетів. Засоби, які компанія могла б отримати від продажу супермаркетів у Києві, Харкові, Дніпропетровську, Донецьку, Запоріжжі, Полтаві та Сімферополі становлять відповідно 26; 24,5; 22,5; 18; 17; 16 і 15,5 млн. грн. При цьому продаж супермаркетів сполучена з необхідністю звільнення персоналу. Його чисельність супермаркетах становить відповідно 200, 190, 180, 170, 150, 130 і 110 осіб. На вимогу об'єднаної профспілки працівників торгівлі компанія повинна мінімізувати чисельність звільненого персоналу.

Побудуйте модель для знаходження оптимального рішення.

Математична модель:

Пронумеруємо міста відповідно до порядку їх перерахування.

Нехай х_i = 1, якщо супермаркет, розташований у місті, продається,

            х_i = 0 - в іншому випадку.

Система змінних:

Продаж супермаркету в місті

х₁ - Київ

х₂ - Харків

х₃ – Дніпропетровськ

х₄ - Донецьк

х₅ - Запоріжжя

х₆ - Полтава

х₇ - Сімферополь

Система обмежень:

1.     За обсягом потрібних коштів, млн. грн.

26х₁ + 24,5х₂ +22,5х₃ +18х₄ +17х₅ +16х₆ +15,5 х₇ ≥ 65

2. Умова булевості змінних:

1 варіант	2 варіант
х1, х2, х3, х4, х5, х6, х7 - бінарні	х1, х2, х3, х4, х5, х6, х7≥0
	х1, х2, х3, х4, х5, х6, х7≤1
	х1, х2, х3, х4, х5, х6, х7 – цілі числа

Критерій оптимальності - мінімальна чисельність звільненого персоналу

F=200х₁+190х₂+180х₃+170х₄+150х₅+130х₆+110х₇→ min

Висновок: найменша кількість звільнення персоналу (500 осіб) досягається шляхом продажу супермаркетів в Києві, Харкові та Сімферополі, при цьому обсяг виручених коштів складе 66 млн. грн.

Задача про доставку

Класична постановка. Фірма обслуговує деяку кількість клієнтів m. Кожен день вона доставляє своїм клієнтам товари на вантажних машинах (або залізницею, повітряним шляхом, на баржах і т.д.). Існує n допустимих маршрутів доставки, кожен з яких дозволяє обслужити певну множину клієнтів і вимагає використання в перебігу дня одного транспортного засобу. Кожен маршрут характеризується певними витратами с_j, які можуть відповідати його довжині, або вартості витраченого палива і т.д.

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

Задача  Фірма «Truck» обслуговує 5 клієнтів. Кожен день вона доставляє своїм клієнтам товари на вантажних машинах. Існує 3 допустимих маршруту доставки, кожен з яких дозволяє обслужити певну кількість клієнтів і вимагає використання протягом дня одного транспортного засобу. Кожен маршрут характеризується певними витратами (див. табл. 1.13).

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

Таблиця 1.13

Таблиця обслуговування клієнтів по маршрутах

Клієнти	Маршрути
	Маршрут 1	Маршрут 2	Маршрут 3
Клієнт 1	1		1
Клієнт 2	1
Клієнт 3	1		1
Клієнт 4		1
Клієнт 5		1	1
Витрати на маршрут, гр. од.	900	1000	800

Математична модель:

Приймаємо, що     x_і = 1, якщо маршрут і обраний;

                                 x_і = 0, в іншому випадку;

a_ij = 1, якщо i-й клієнт обслуговується за маршрутом j;

a_ij = 0, в іншому випадку

Система змінних:

х₁ - маршрут 1

х₂ - маршрут 2

х₃ – маршрут 3

Система обмежень:

1. По Клієнту 1                                         x₁+⋅x₃=1,

2. По Клієнту 2                                          x₁ =1

3. По Клієнту 3                                           x₁ +x₃=1

4. По Клієнту 4                                            x₂ =1

5. По Клієнту 5                                             x₂+x₃=1

Критерій оптимальності – мінімальні витрати на доставку, гр. од.

F=900x₁+1000x₂+800x₃→min

Висновок: найменші витрати на доставку в обсязі 1900 гр. од. передбачають використання маршрутів 1 і 2 та відмову від маршруту 3.

Транспортна задача та її модифікації

Класична постановка транспортної задачі. Потрібно скласти план перевезень однорідного вантажу в такий спосіб,щоб загальна вартість перевезень була мінімальною.

       Вихідна інформація:

a_i - кількість одиниць вантажу в i-му пункті відправлення (i = 1, m);

b_j - потреба в j-му пункті призначення (j = 1, n) в одиницях вантажу;

c_ij - вартість перевезення одиниці вантажу з i-го пункту в j-й.

x_ij - планова кількість одиниць вантажу для перевезення з i-го пункту в j-й.

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

Цільова функція має вигляд:

У випадку першої відкритої моделі ТЗ, коли загальна кількість одиниць вантажу пунктах відправлення більша за загальну потребу в пунктах призначення, повинні виконуватися умови:

У випадку другої відкритої моделі ТЗ, коли загальна кількість одиниць вантажу пунктах відправлення менша за загальну потребу в пунктах призначення, повинні виконуватися умови:

Задача  В групі господарств необхідно розширити площі посіву ярих культур.  Площі, що підлягають пересіву, складають 930, 600 та 700 га відповідно. Максимально можлива площа посіву гороху становить 730 га, вівсу – 400 га, проса – 190 га, ячменю – 580 га. Планові урожайності цих культур наведені в табл. 1.15.

Таблиця 1.15

Урожайність культур у різних господарствах

Господарства	Урожайність, ц/га
	горох	овес	просо	ячмінь
1	19	18	14	26
2	24	18	15	23
3	21	19	16	24

Необхідно скласти план розміщення ярих зернових культур, який забезпечив би максимальне виробництво зерна з урахуванням наступних умов:

а) перше господарство має запаси насіннєвого матеріалу, що дозволяє засіяти горох на площі 120 га, а ячмінь – на площі не більше 440 га;

б) запаси паливно-мастильних матеріалів у другому господарстві дозволять засіяти горох на площі не більше 550 га;

в) система сівозмін третього господарства не передбачає висівання вівса.

Математична модель:

Система змінних:

Площі окремих господарств під відповідними культурами:

x₁₁ – площа господарства 1 під горохом

x₁₂ - площа господарства 1 під вівсом

x₁₃ - площа господарства 1 під просом

 x₁₄ - площа господарства 1 під ячменем

х₃₄ - площа господарства 3 під ячменем

Система обмежень

1. Не всі відведені в господарствах площі мають бути зайняті	2. Вся можлива площа посіву ярих культур має бути пересіяна
x11 +x12 +x13 +x14≤930 x21 +x22 +x23 +x24≤600 x31 +x32 +x33 +x34≤700	x11 +x21 +x31 =730 x12 +x22 +x32 =400 x13 +x23 +x33 =190 x14 +x24 +x34 =580

3. По площі гороху в господарстві 1                   x₁₁=120

4. По площі ячменю в господарстві 1                   x₁₄≤440

5. По площі гороху в господарстві 2                   x₂₁≤550

3. По площі вівса в господарстві 3                        x₃₂=0

Критерій оптимальності - максимальний валовий збір ярих культур, ц

F = 19x₁₁ + 18x₁₂ +14x₁₃+ 26x₁₄ + 24x₂₁ + 18x₂₂ + 15x₂₃ + 23x₂₄ + 21x₃₁ + 19x₃₂ + 16x₃₃ + 24x₃₄ → mах

Висновок: оптимальний план передбачає розміщення на площах:

- господарства 1: 120 га посівів гороху, 370 га вівсу та 440 га ячменю, що забезпечить повну зайнятість відведених площ;

- господарства 2: 550 га посівів гороху та 30 га вівсу, при цьому 20 га площі залишаться незайнятими;

- господарства 3: 60 га посівів гороху, 190 га проса та 140 га ячменю, при цьому 310 га площі залишаться незайнятими.

Максимальний валовий збір зерна при цьому складе 41780 ц.

 

Аналіз чутливості оптимізаційних моделей

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

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

Аналіз чутливості оптимізаційних моделей  - це процес аналізу моделі після знаходження оптимального рішення.

Аналіз чутливості має дати відповіді на наступні питання:

♦ У яких межах можуть змінюватися параметри моделі так, щоб збереглося отримане рішення?

♦ Які обмеження пов'язані (тобто лімітують (стримують) цільову функцію), а які обмеження не впливають на рішення?

♦ Якщо змінити значення правих частин пов'язаних обмежень, то наскільки може змінитися значення цільової функції?

♦ Якщо значення якоїсь змінної рішення дорівнює нулю, то за яких умов вона може прийняти позитивне значення?

Аналіз  чутливості за звітами в MS Excel:

—  Звіт зі стійкості - вивчення впливу змін окремо взятих параметрів моделі на показники оптимального рішення

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

—  Звіт за результатами – вказує, які обмеження пов'язані і які непов'язані.

 Звіт зі стійкості, який є найкориснішим при аналізі чутливості оптимального плану. Він складається з двох частин:

1 – Комірки, що змінюються. Крім імені змінних і адрес комірок в ній присутні стовпчики:

Остаточне значення - це оптимальний план.

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

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

2 - Обмеження. Крім імені змінних і адрес комірок в ній присутні стовпчики:

Остаточне значення - значення лівої частини обмеження при оптимальному плані.

Тіньова ціна - зміна цільової функції при зміні дефіцитного ресурсу на 1 одиницю. Тіньова ціна недефіцитного ресурсу буде дорівнює 0.

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

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

 

НАЗАД                                         ГОЛОВНА