ЗАГАЛЬНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА ДЕЯКІ З МЕТОДІВ ЇЇ РОЗВ’ЯЗУВАННЯ (2) Задача 2.2. На ринок поставляється картопля з трьох фермерських господарств за цінами відповідно 80, 75 та 65 коп. за 1 кг. На завантаження 1 т картоплі в господарствах відповідно витрачається по 1, 6 та 5 хвилин. Замовлено 12 т картоплі, і для своєчасної доставки необхідно, щоб на її завантаження витрачалося не більше сорока хвилин. Потрібно визначити, з яких фермерських господарств і в якій кількості необхідно доставляти картоплю, щоб загальна вартість закупівлі була мінімальною, якщо фермери можуть виділити для продажу відповідно 10, 8 та 6 т картоплі. Побудова економіко-математичної моделі. Позначимо: х1 — кількість картоплі, що буде закуплена у першому господарстві (т); х2, х3 — кількість картоплі, закупленої відповідно у другого та третього фермерів (т). Поставка потрібної кількості картоплі описується рівністю: , наступне обмеження описує витрати часу на завантаження продукції: обмеження щодо можливостей поставок продукції з кожного господарства:
Вартість продукції, що закуповується, визначається як сума добутків ціни на відповідні її обсяги. Ціни 1 т картоплі відповідно дорівнюють 800, 750 та 650 грн в даних трьох фермерських господарствах. Отже, цільову функцію можна записати так: . Економіко-математична модель задачі має вигляд:
за умов:
Задача 2.5.(Транспортна) Фермерське господарство спеціалізується на вирощуванні озимої пшениці і має три ділянки землі площею S1 = 40 га, S2 = 90 га, S3 = 55 га. Враховуючи наявну кількість посівного матеріалу, є можливість засіяти всю площу озимою пшеницею трьох сортів. Кількість пшениці сорту «Миронівська-808» забезпечить посів на 80 га,«Безоста-1» — 60 га та «Одеська — 51» — 45 га. Урожайність сорту «Миронівська-808» на даних ділянках становить відповідно 41 ц/га, 40 ц/га, 46 ц/га. Аналогічно для сорту «Безоста-1» маємо: 38 ц/га, 41 ц/га, 45 ц/га, а для «Одеської-51» — 30 ц/га, 28 ц/га, 40 ц/га. Необхідно розподілити посівний матеріал за земельними ділянками так, щоб отримати максимальний урожай (валовий збір) озимої пшениці. Побудова економіко-математичної моделі. Позначимо через хij площу (га) і-ої земельної ділянки, що буде засіяна j-м сортом озимої пшениці (домовимося, що сорти «Миронівська-808», «Безоста-1», «Одеська-51» відповідатимуть номерам 1, 2, 3), (і = 1, 2, 3), (j = 1, 2, 3). Тоді використання земельних угідь описуватиме така система обмежень: ; ; . Використання посівного матеріалу формально можна описати так: ; ; . Валовий збір зерна розраховується як сума добутків урожайностей відповідних сортів пшениці на їх посівні площі, тобто:
Отже, економіко-математична модель задачі загалом буде мати вигляд:
за умов:
. 2.5(1) Розглянемо геометричну інтерпретацію задачі лінійного програмування на прикладі. Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га. Техніко-економічні показники вирощування цих культур маємо у табл. 2.3: Таблиця 2.3 ПОКАЗНИКИ ВИРОЩУВАННЯ СІЛЬСЬКОГОСПОДАРСЬКИХ КУЛЬТУР Показник (із розрахунку на 1 га) Озима пшениця Цукрові буряки Наявний ресурс
Затрати праці, людино-днів 5 25 270
Затрати праці механізаторів, людино-днів 2 8 80
Урожайність, тонн 3,5 40 —
Прибуток, тис. грн 0,7 1 —
Критерієм оптимальності є максимізація прибутку. Запишемо економіко-математичну модель структури виробництва озимої пшениці та цукрових буряків, ввівши такі позначення: х1 — шукана площа посіву озимої пшениці, га; х2 — шукана площа посіву цукрових буряків, га. Задача лінійного програмування має такий вигляд: max Z = 0,7x1 + x2 (2.10) за умов: x1 + x2 ? 20; (2.11) 5 x1 + 25 x2 ? 270; (2.12) 2 x1 + 8 x2 ? 80; (2.13) x2 ? 5; (2.14) x1 ? 0, x2 ? 0. (2.15) Геометричну інтерпретацію задачі зображено на рис. 2.2. Рис. 2.2. Область допустимих розв’язків задачі Область допустимих розв’язків цієї задачі дістаємо так. Кожне обмеження, наприклад x1 + x2 ? 20, задає півплощину з граничною прямою x1 + x2 = 20. Будуємо її і визначаємо півплощину, яка описується нерівністю x1 + x2 ? 20. З цією метою в нерівність x1 + x2 ? 20 підставляємо координати характерної точки, скажімо, x1 = 0 і x2 = 0. Переконуємося, що ця точка належить півплощині x1 + x2 ? 20. Цей факт на рис. 2.2 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають нерівностям (2.11)—(2.15). У результаті перетину цих півплощин утворюється область допустимих розв’язків задачі (на рис. 2.2 — чотирикутник ABCD). Цільова функція Z = 0,7 x1 + x2 являє собою сім’ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z = 0, то маємо 0,7 x1 + x2 = 0. Ця пряма проходить через початок системи координат. Коли Z = 3,5, то маємо пряму 0,7 x1 + x2 = 3,5. Задача 2.6. Розв’язати графічним методом задачу лінійного програмування
. Розв’язання. Маємо n = 7 — кількість змінних, m = 5 — кількість обмежень. Виберемо як вільні змінні х1 та х2 і виразимо через них всі інші базисні змінні. З першого рівняння маємо: (2.19.2) З третього рівняння: , (2.19.3) а з четвертого: . (2.19.4) Підставляючи (2.19.2) в друге рівняння системи і (2.19.4) в останнє, розв’язуємо їх відносно х4 та х7. Отримаємо: ; . Далі за алгоритмом беремо х1 = 0 та х2 = 0 — координатні осі; інші обмежуючі прямі знаходимо, узявши х3 = 0, х4 = 0, х5 = 0, х6 = 0, х7 = 0. Багатокутник допустимих розв’язків зображено на рис. 2.12. Рис. 2.12 Знайдемо вигляд функціонала, вираженого через х1 та х2. Для цього знайдені щойно вирази для х3, х4, х5, х6 та х7 через вільні змінні х1 і х2 підставимо у функціонал і, звівши подібні члени, отримаємо: . Відкидаючи вільний член, маємо: . Будуємо вектор (–5, –2), перпендикулярно до нього — пряму F(. Рухаючи пряму F( в напрямку, протилежному (необхідно знайти мінімальне значення функції F), отримаємо точку мінімуму — А (рис. 2.13). Рис. 2.13 У точці А перетинаються дві обмежуючі прямі: х6 = 0 та х7 = 0. Отже, для відшукання її координат необхідно розв’язати систему рівнянь:
Розв’язком системи є х1*= 8,5; х2*= 5. Підставивши ці значення у відповідні вирази, знайдемо оптимальні значення базисних змінних: Х3*= 0,5; х4*= 16,5; х5*= 17,5; х6*= 0; х7*= 0. Підстановкою значень х1* та х2* в лінійну функцію F отримуємо значення цільової функції: Задача 2.7. Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає два види збірних книжкових полиць — А та В. Полиці обох видів виготовляють на верстатах 1 та 2. Тривалість обробки деталей однієї полиці кожної моделі подано в табл. (2.4). Таблиця 2.4 ТРИВАЛІСТЬ ВИГОТОВЛЕННЯ КНИЖКОВИХ ПОЛИЦЬ Верстат Тривалість обробки полиці моделі, хв. Ресурс робочого часу верстатів, год. на тиждень
А В
1 30 15 40
2 12 26 36
Прибуток фірми від реалізації однієї полиці моделі А дорівнює 50 у. о., а моделі В — 30 у. о. Вивчення ринку збуту показало, що тижневий попит на книжкові полиці моделі А ніколи не перевищує попиту на модель В більш як на 30 одиниць, а продаж полиць моделі В не перевищує 80 одиниць на тиждень. Необхідно визначити обсяги виробництва книжкових полиць цих двох моделей, що максимізують прибуток фірми. Для цього слід побудувати економіко-математичну модель поставленої задачі та розв’язати її графічно. Побудова математичної моделі. Змінними в моделі є тижневі обсяги виробництва книжкових полиць моделей А та В. Нехай х1 — кількість полиць моделі А, виготовлених фірмою за тиждень, а х2 — кількість полиць моделі В. Цільова функція задачі — максимум прибутку фірми від реалізації продукції. Математично вона подається так: . Обмеження задачі враховують тривалість роботи верстатів 1 та 2 для виготовлення продукції та попит на полиці різних моделей. Обмеження на тривалість роботи верстатів 1 та 2 мають вид: для верстата 1: 30х1 + 15х х2 ? 2400 (хв); для верстата 2: 12 х1 + 26 х2 ? 2160 (хв). Обмеження на попит записуються так: х1 – х2 ? 30 та х2 ? 80. Загалом економіко-математичну модель цієї задачі можна записати так: max Z = 50 х1 + 30 х2 (2.20) за умов:
Ця економіко-математична модель є моделлю задачі лінійного програмування, що містить лише дві змінні, і тому може бути розв’язана графічно. Розв’язання. Перший крок згідно з графічним методом полягає в геометричному зображенні допустимих планів задачі, тобто у визначенні такої області, де водночас виконуються всі обмеження моделі. Замінимо знаки нерівностей на знаки строгих рівностей і побудуємо графіки відповідних прямих (рис. 2.14). Кожна з побудованих прямих поділяє площину системи координат на дві півплощини. Координати точок однієї з півплощин задовольняють розглядувану нерівність, а іншої — ні. Щоб визначити необхідну півплощину (на рис. 2.14 її напрям позначено стрілкою), потрібно взяти будь-яку точку і перевірити, чи задовольняють її координати зазначене обмеження. Якщо задовольняють, то півплощина, в якій міститься вибрана точка, є геометричним зображенням нерівності. Інакше таким зображенням є інша півплощина.
Рис. 2.14 Умова невід’ємності змінних х1 ? 0, х2 ? 0 обмежує область допустимих планів задачі першим квадрантом системи координат. Переріз усіх півплощин визначає область допустимих планів задачі — шестикутник OABCDE. Координати будь-якої його точки задовольняють систему обмежень задачі та умову невід’ємності змінних. Тому поставлену задачу буде розв’язано, якщо ми зможемо відшукати таку точку багатокутника OABCDE, в якій цільова функція Z набирає найбільшого значення. Для цього побудуємо вектор , координатами якого є коефіцієнти при змінних у цільовій функції задачі. Вектор завжди виходить із початку координат і напрямлений до точки з координатами (х1 = с1; х2 = с2). У нашій задачі вектор . Він задає напрям збільшення значень цільової функції Z, а вектор, протилежний йому, — напрям їх зменшення. Побудуємо лінію, що відповідає, наприклад, значенню Z = 0. Це буде пряма 50 х1 + 30 х2 = 0, яка перпендикулярна до вектора і проходить через початок координат. Оскільки в даному прикладі необхідно визначити найбільше значення цільової функції, то пересуватимемо пряму 50 х1 + 30 х2 = 0 паралельно самій собі згідно з напрямом вектора доти, доки не визначимо вершину багатокутника, яка відповідає оптимальному плану задачі. Із рис. 2.14 видно, що останньою спільною точкою прямої цільової функції та багатокутника OABCDE є точка С. Координати цієї точки є оптимальним планом задачі, тобто такими обсягами виробництва книжкових полиць видів А та В, що забезпечують максимум прибутку від їх реалізації за даних умов. Координати точки С є розв’язком системи рівнянь (2.17) і (2.18):
звідси маємо: х1 = 50; х2 = 60. Отже, Х* = (50; 60); Мах. Z = 50*50 + 30*60 = 4300 Це означає, що коли фірма щотижня виготовлятиме 50 збірних книжкових полиць моделі А та 60 — моделі В, то вона отримає максимальний прибуток — 4300 у. о. Це потребуватиме повного використання тижневих ресурсів робочого часу верстатів 1 та 2. Задача 2.8. Симплексний метод розв’язування задач лінійного програмування Продукція чотирьох видів А, В, С і D проходить послідовну обробку на двох верстатах. Тривалість обробки одиниці продукції кожного виду наведена в табл. 2.8.Таблиця 2.8 Верстат Тривалість обробки одиниці продукції
А В С D
1 2 3 4 2
2 3 2 1 2
Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-години становить 10 грн для верстата 1 і 15 грн — для верстата 2. Тривалість використання верстатів обмежена: для верстата 1 вона становить 450 машино-годин, а для верстата 2 — 380 машино-годин. Ціна одиниці продукції видів А, В, С і D дорівнює відповідно 73, 70, 55 та 45 грн. Визначити оптимальний план виробництва продукції всіх чотирьох видів, який максимізує загальний прибуток. Побудова економіко-математичної моделі. Нехай хj — план виробництва продукції j-го виду, де j може набувати значень від 1 до 4. Умовами задачі будуть обмеження на тривалість використання верстатів для виробництва продукції всіх видів: для верстата 1 (маш.год.); для верстата 2 (маш.-год.). Цільовою функцією задачі є загальний прибуток від реалізації готової продукції, який розраховується як різниця між ціною та собівартістю виготовлення продукції кожного виду: . Отже, математична модель цієї задачі має такий вигляд:
за умов:
Розв’язання. Розв’яжемо задачу симплекс-методом згідно з розглянутим алгоритмом. 1. Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні х5 та х6:
Ці додаткові змінні за економічним змістом означають недовикористаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:
Канонічну систему обмежень задачі запишемо у векторній формі:
де
Оскільки вектори та одиничні та лінійно незалежні, то саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі х5 та х6, що відповідають одиничним базисним векторам, називають базисними, а решту — вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:
Згідно з визначеними векторна форма запису системи обмежень цієї задачі матиме вигляд: . Оскільки додатні коефіцієнти х5 та х6 відповідають лінійно незалежним векторам, то за означенням
є опорним планом задачі і для цього початкового плану . 2. Складемо симплексну таблицю для першого опорного плану задачі. Базис Сбаз План 8 10 0 – 5 0 0
х1 х2 х3 х4 х5 х6
х5 0 450 2 3 4 2 1 0 150
х6 0 380 3 2 1 2 0 1 190
Zj – сj ? 0 0 –8 –10 0 5 0 0
Елементи останнього рядка симплекс-таблиці є оцінками ?j, за допомогою яких опорний план перевіряють на оптимальність. Їх визначають так: ; ; ; ; ; . У стовпчику «План» оцінкового рядка записують значення цільової функції Z, якого вона набуває для визначеного опорного плану: . 3. Після обчислення всіх оцінок опорний план перевіряють на оптимальність. Для цього продивляються елементи оцінкового рядка. Якщо всі (для задачі на max) або (для задачі на min), то визначений опорний план є оптимальним. Якщо ж в оцінковому рядку є хоча б одна оцінка, що не задовольняє умову оптимальності (від’ємна в задачі на max або додатна в задачі на min), то опорний план є неоптимальним і його можна поліпшити. У цій задачі в оцінковому рядку дві оцінки та від’ємні, тобто не задовольняють умову оптимальності, і тому перший визначений опорний план є неоптимальним. За алгоритмом симплекс-методу необхідно від нього перейти до іншого опорного плану задачі. 4. Перехід від одного опорного плану до іншого здійснюють зміною базису, тобто через виключення з поточного базису якоїсь змінної та включення замість неї нової з числа вільних змінних. Для введення до нового базису вибираємо змінну х2, оскільки їй відповідає найбільша за абсолютною величиною оцінка з-поміж тих, які не задовольняють умову оптимальності (|–10|>|–8|). Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х2» знаходимо відношення і вибираємо найменше значення. Згідно з даними симплексної таблиці маємо, що , і тому з базису виключаємо змінну х5, а число а12 = 3 — розв’язувальний елемент. Дальший перехід до нового опорного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана—Гаусса. Друга симплексна таблиця має такий вигляд: Базис Сбаз План 8 10 0 – 5 0 0
х1 х2 х3 х4 х5 х6
х2 10 150 2/3 1 4/3 2/3 1/3 0 225
х6 0 80 5/3 0 -5/3 2/3 –2/3 1 48
Zj – сj ? 0 1500 -4/3 0 40/3 35/3 10/3 0
У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «Сбаз», а решту елементів нової таблиці розраховують за розглянутими нижче правилами: 1. Кожний елемент розв’язувального (напрямного) рядка необхідно поділити на розв’язувальний елемент і отримані числа записати у відповідний рядок нової симплексної таблиці. 2. Розв’язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв’язувального елемента. 3. Якщо в напрямному рядку є нульовий елемент, то від повідний стовпчик переписують у нову симплексну таблицю без змін. 4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін. Усі інші елементи наступної симплексної таблиці розраховують за правилом прямокутника. Щоб визначити будь-який елемент нової таблиці за цим правилом, необхідно в попередній симплексній таблиці скласти умовний прямокутник, вершини якого утворюються такими числами: 1 — розв’язувальний елемент (число 1); 2 — число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати; 3 та 4 — елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника. Необхідний елемент нової симплекс-таблиці визначають за такою формулою: . Наприклад, визначимо елемент , який розміщується в новій таблиці в другому рядку стовпчика «х4». Складемо умовний прямокутник:
Тоді . Це значення записуємо в стовпчик «х4» у другому рядку другої симплексної таблиці. Аналогічно розраховують усі елементи нової симплексної таблиці, у тому числі й елементи стовпчика «План» та оцінкового рядка. Наявність двох способів зображення визначення оцінок опорного плану (за правилом прямокутника та за відповідною формулою) дає змогу контролювати правильність арифметичних обчислень на кожному кроці симплекс-методу. Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності Zj – сj ? 0 для другого опорного плану. Цей план також неоптимальний, оскільки . Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці: Базис Сбаз План 8 10 0 – 5 0 0
х1 х2 х3 х4 х5 х6
х2 10 118 0 1 2 2/5 3/5 –2/5
х1 8 48 1 0 –1 2/5 –2/5 3/5
Zj – сj ? 0 1564 0 0 12 61/5 14/5 4/5
В оцінковому рядку третьої симплексної таблиці немає від’ємних чисел, тобто всі і задовольняють умову оптимальності. Це означає, що знайдено оптимальний план задачі:
або Х* = (48; 118; 0; 0; 0; 0); . Отже, план виробництва продукції, що передбачає випуск 48 одиниць продукції А та 118 одиниць продукції В, є оптимальним. Він уможливлює отримання найбільшого прибутку за заданих умов (1564 грн). При цьому час роботи верстатів використовується повністю (х5 = х6 = 0). Наведені вище три симплексні таблиці можна об’єднати в одну та послідовно записувати в ній всі ітерації. Задача 2.13. (Метод штучного базису). Продукція фабрики випускається у вигляді паперових рулонів стандартної ширини — 2 м. За спеціальним замовленням споживачів фабрика постачає також рулони інших розмірів, розрізуючи стандартні. Замовлення Потрібна ширина рулона, м Кількість замовлених рулонів
1 0,8 150
2 1,0 200
3 1,2 300
Типові замовлення на рулони нестандартних розмірів наведено в табл. 2.9. Необхідно визначити оптимальний варіант розкрою стандартних рулонів, за якого спеціальні замовлення, що надходять, задовольняють повністю з мінімальними відходами паперу. Розв’язання. Аби виконати спеціальні замовлення, які надійшли, розглянемо п’ять можливих варіантів розрізування стандартних рулонів, що можуть використовуватися в різних комбінаціях. Варіанти розкрою наведено в табл. 2.10. МОЖЛИВІ ВАРІАНТИ РОЗРІЗУВАННЯ СТАНДАРТНИХ РУЛОНІВ ПАПЕРУ Потрібна ширина рулона, м Кількість нестандартних рулонів за варіантами
1 2 3 4 5
0,8 2 1 1 0 0
1,0 0 0 1 2 0
1,2 0 1 0 0 1
Обсяг відходів, м 0,4 0 0,2 0 0,8
Нехай xj — кількість стандартних рулонів паперу, які буде розрізано j-способом, . Обмеження задачі пов’язані з обов’язковою вимогою повного забезпечення необхідної кількості нестандартних рулонів за спеціальними замовленнями. Якщо брати до уваги всі подані в таблиці способи розкрою, то дістанемо такі умови (обмеження) даної задачі: 1. Щодо кількості рулонів шириною 0,8 м: 2х1 + х2 + х3 = 150. 2. Щодо кількості рулонів шириною 1 м: х3 + 2х4 = 200. 3. Стосовно кількості рулонів шириною 1,2 м: х2 + х5 = 300. Цільова функція задачі — це мінімальні загальні втрати паперу під час розрізування стандартних рулонів на рулони нестандартної ширини. Математично вона має такий вигляд: . Математична модель задачі загалом записується так:
за умов:
Для розв’язування цієї задачі застосуємо алгоритм симплекс-методу. Оскільки задачу сформульовано в канонічній формі, запишемо її відразу у векторній формі:
де
У системі векторів маємо лише один одиничний вектор . Тому в перше та друге обмеження введемо штучні змінні х6 та х7. Розширена задача матиме вигляд:
за умов:
Процес розв’язання задачі симплекс-методом подано у вигляді таблиці: Базис Сбаз План 0,4 0 0,2 0 0,8 М M
х1 х2 х3 х4 х5 х6 х7
х6 M 150 2 1 1 0 0 1 0
х7 M 200 0 0 1 2 0 0 1
х5 0,8 300 0 1 0 0 1 0 0
Zj – сj ( 0 240 –0,4 0,8 –0,2 0 0 0 0
350 M 2 M M 2 M 2 M 0 0 0
х6 M 150 2 1 1 0 0 1
х4 0 100 0 0 1/2 1 0 0
х5 0,8 300 0 1 0 0 1 0
Zj – сj ( 0 240 –0,4 0,8 –0,2 0 0 0
150 M 2 M M M 0 0 0
х1 0,4 75 1 1/2 1/2 0 0
х4 0 100 0 0 1/2 1 0
х5 0,8 300 0 1 0 0 1
Zj – сj ( 0 270 0 1 0 0 0
х2 0 150 2 1 1 0 0
х4 0 100 0 0 1/2 1 0
х5 0,8 150 –2 0 –1 0 1
Zj – сj ( 0 120 –2 0 –1 0 0
Згідно з останньою симплексною таблицею запишемо оптимальний план задачі: Х* = (0; 150; 0; 100; 150), min Z = 120. Визначений оптимальний план передбачає: щоб у повному обсязі виконати спеціальні замовлення, які надходять на паперову фабрику, необхідно розрізати 150 стандартних рулонів другим способом, 100 рулонів — четвертим і 150 — п’ятим. За такого оптимального варіанта розкрою обсяг відходів паперу буде найменшим і становитиме 120 м. ТЕОРІЯ ДВОЇСТОСТІ ТА ДВОЇСТІ ОЦІНКИ У ЛІНІЙНОМУ ПРОГРАМУВАННІ (3) Задача 3.1 До даної задачі лінійного програмування записати двоїсту. max F = –5x1 + 2x2;
Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то вони мусять мати знак «». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо: max F = –5x1 + 2x2;
Тепер за відповідними правилами складемо двоїсту задачу: ;
Задача 3.2 До заданої задачі лінійного програмування записати двоїсту.
Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція F мінімізується і в системі обмежень є нерівності, то вони мають бути виду «». Тому друге обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:
Двоїста задача:
Оскільки перше обмеження початкової задачі є рівнянням, то відповідна йому змінна двоїстої задачі y1 може набувати як додатного, так і від’ємного значення. Задача 3.3 До заданої задачі лінійного програмування записати двоїсту задачу. Розв’язати одну з них симплекс-методом та визначити оптимальний план другої задачі, використовуючи співвідношення першої теореми двоїстості. max Z = – 5x1 + 2x2;
Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то їх слід звести до виду «». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо: max Z = – 5x1 + 2x2;
Тепер за відповідними правилами складемо двоїсту задачу: min F = – y1 + 5y2;
Оскільки записані задачі симетричні, то будь-яку з них можна розв’язати симплекс-методом. Наприклад, визначимо спочатку оптимальний план прямої задачі. Для цього застосуємо алгоритм симплекс-методу. 1. max Z = – 5x1 + 2x2 + 0x3 + 0x4;
2. Векторна форма запису системи обмежень має вигляд: , де , , , , . У системі векторів для утворення початкового одиничного базису відсутній один вектор. Тому введемо штучну змінну в перше обмеження. 3. Розширена задача лінійного програмування буде такою: max Z = – 5x1 + 2x2 + 0x3 + 0x4 – Мx5;
У цій задачі х4 та х5 — базисні змінні, а х1, х2, х3 — вільні. Нехай х1 = х2 = х3 = 0, тоді х4 = 5; х5 = 1. Перший опорний план задачі: X0 = (0; 0; 0; 5; 1), Z0 = – M. 4. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці: Базис Сбаз План –5 2 0 0 – М (
x1 x2 x3 x4 x5
( x5x4 –М0 15 12 13 – 10 01 10 15/3
Zj – cj ( 0 0–М 5–М –2–М 0М 00 00
x2( x4 20 12 1–1 10 –13 01 1–3 –2/3
Zj – cj ( 0 2 7 0 – 2 0 2М
x2x3 20 5/32/3 2/3–1/3 10 01 1/31/3 0–1
Zj – cj ( 0 10/3 19/3 0 0 2/3 0М
З останньої симплекс-таблиці запишемо оптимальний план прямої задачі: Х* = (0; 5/3; 2/3; 0), Zmax = 10/3. Згідно зі співвідношенням двоїстості за першою теоремою можна висновувати, що оптимальний план двоїстої задачі існує і min F = max Z = 10/3. Компоненти вектора Y* (оптимальний план двоїстої задачі) визначимо за формулою: , де та міститься в стовпчику «Cбаз» останньої симплекс-таблиці; . Матриця D– 1 також міститься в останній симплекс-таблиці у стовпчиках змінних «x5» та «x4», які утворювали початковий базис. Отже, , min F = – 1 ( 0 + 5 ( 2/3 = 10/3. Застосувавши для розв’язування прямої задачі симплекс-метод, ми знайшли її оптимальний план, а потім визначили оптимальний розв’язок двоїстої задачі за допомогою співвідношень першої теореми двоїстості. Задача 3.4 До заданої задачі лінійного програмування записати двоїсту задачу. Розв’язавши двоїсту задачу графічно, визначити оптимальний план прямої задачі. min Z = x1 + 2x2 + 2x3;
Розв’язання. За відповідними правилами побудуємо двоїсту задачу: mах F = y1 + 4y2;
Зауважимо, що задачі несиметричні, і тому змінна у1, що відповідає першому рівнянню в системі обмежень прямої задачі, може мати будь-який знак, а змінна у2 — лише невід’ємна. Двоїста задача має дві змінні, а отже, її можна розв’язати графічно (рис. 3.2). Рис. 3.2 Найбільшого значення цільова функція двоїстої задачі F досягає в точці В багатокутника ABCD. Її координати визначимо розв’язанням системи рівнянь:
Отже, Y* = (– 2/3; 4/3); mах F = 1 ( (– 2/3) + 4 ( 4/3 = 14/3. Оптимальний план прямої задачі визначимо за допомогою співвідношень другої теореми двоїстості. Підставимо Y* у систему обмежень двоїстої задачі і з’ясуємо, як виконуються обмеження цієї задачі:
Оскільки перше обмеження для оптимального плану двоїстої задачі виконується як строга нерівність, то висновуємо, що перша змінна прямої задачі дорівнюватиме нулю х1 = 0 (перша частина другої теореми двоїстості). Тепер проаналізуємо оптимальний план двоїстої задачі. Оскільки друга компонента плану у2 = 4/3 додатна, то друге обмеження прямої задачі для Х* виконуватиметься як строге рівняння (друга частина другої теореми двоїстості). Об’єднуючи здобуту інформацію, можна записати систему обмежень прямої задачі як систему двох рівнянь, в якій х1 = 0, та визначити решту змінних:
тобто Х* = (0; 5/3; 2/3), min Z = 1 ( 0 + 2 ( 5/3 + 2 ( 2/3 = 14/3. Умова min Z = max F = 14/3 виконується, і тому Х* = (0; 5/3; 2/3); Y* = (– 2/3; 4/3) є оптимальними планами відповідно прямої та двоїстої задач. Задача 3.5 Визначити, чи є оптимальними такі плани сформульованої задачі лінійного програмування: min Z = 12x1 – 4x2 + 2x3;
а) Х = (8/7; 3/7; 0); б) Х = (0; 1/5; 8/5); в) Х = (1/3; 0; 1/3). Розв’язання. Принцип розв’язування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розв’язок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій будуть однаковими за величиною, то припущення правильне. Протилежне можна висновувати в таких випадках: 1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі. 2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі. 3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює значенню функції Z, тобто не виконується умова першої теореми двоїстості. Запишемо двоїсту задачу до прямої задачі лінійного програмування: max F = y1 + 2y2;
Перевіримо запропоновані плани на оптимальність. 1. Х = (8/7; 3/7; 0). Підставимо його в систему обмежень прямої задачі:
Обидва обмеження виконуються, і тому Х = (8/7; 3/7; 0) є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = 12 ( 8/7 – 4 ( 3/7 + 2 ( 0 = 12. Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x1 = 8/7 > 0; x2 = 3/7 > 0, то згідно з другою частиною другої теореми двоїстості можна записати перше та друге обмеження як рівняння і визначити у1 та у2:
Підставимо ці значення в третє обмеження системи двоїстої задачі: ; . Для визначених значень у1 = 4; у2 = 4 це обмеження не виконується, і тому відповідний план у = (4; 4) є недопустимим планом двоїстої задачі. Внаслідок цього наше допущення, що Х = (8/7; 3/7; 0) є оптимальним планом прямої задачі, виявилося помилковим. 2. Х = (0; 1/5; 8/5). Підставимо цей план у систему обмежень прямої задачі:
План допустимий, і для нього Z = 12 ( 0 – 4 ( 1/5 + 2 ( 8/5 = 12/5. Визначимо відповідний план двоїстої задачі. Оскільки компоненти x2 та x3 додатні, то друге і третє обмеження двоїстої задачі можна записати як рівняння:
Перевіримо, чи виконується перше обмеження двоїстої задачі для визначених значень у1 та у2: 2 ( 8/5 + 2/5 = 18/5 < 12. Отже, перше обмеження виконується, і тому у = (8/5; 2/5) є допустимим планом двоїстої задачі. Для нього F = 8/5 + 2 ( 2/5 = 12/5 = Z. З огляду на викладене можна висновувати, що Y* = (8/5; 2/5) є оптимальним планом двоїстої задачі, а X* = (0; 1/5; 8/5) — оптимальним планом прямої задачі. Наше припущення відносно запропонованого плану виявилося правильним. 3. Х = (1/3; 0; 1/3). Для цього плану обмеження прямої задачі виконуються так:
Оскільки Х = (1/3; 0; 1/3) є недопустимим планом, то він не може бути також оптимальним планом прямої задачі. Отже, перевірка запропонованих планів на оптимальність дала такі результати: а) ні; б) так, Х* = (0; 1/5; 8/5), min Z = 12/5; в) ні. АНАЛІЗ ЛІНІЙНИХ МОДЕЛЕЙ ЕКОНОМІЧНИХ ЗАДАЧ Задача 4.1 Деяке підприємство виробляє чотири види продукції А, В, С, і D, використовуючи для цього три види ресурсів 1, 2 і 3. Норми витрат ресурсів на виробництво одиниці кожного виду продукції (в умовних одиницях) наведено в табл. 4.1. Таблиця 4.1 Норми витрат ресурсів на виробництво продукції, ум. од. Ресурс Норма витрат ресурсу на одиницю продукції виду Запас ресурсу
А В С D
1 2 5 2 4 250
2 1 6 2 4 280
3 3 2 1 1 80
Відомі також ціни реалізації одиниці продукції кожного виду: для продукції А — 2 ум. од., для продукції В і D — по 4 ум. од., для продукції С — 3 ум. од. Необхідно визначити оптимальний план виробництва продукції кожного виду за умов обмеженості запасів ресурсів, який дав би змогу підприємству отримати найбільшу виручку від реалізації продукції. Розв’язання. Математичні моделі прямої (4.7) та двоїстої (4.8) задач мають такий вигляд: (4.7) де хj — обсяг виробництва продукції j-го виду ; (4.8) де yi — оцінка одиниці і-го виду ресурсу . Симплексна таблиця, що відповідає оптимальному плану сформульованої вище задачі має вигляд: Базис Сбаз План 2 4 3 4 0 0 0
х1 х2 х3 х4 х5 х6 х7
х4 4 45 –2 1/2 0 1 1/2 0 –1
х6 0 30 –1 1 0 0 –1 1 0
х3 3 35 5 3/2 1 0 –1/2 0 2
Zj – cj ( 0 285 5 5/2 0 0 1/2 0 2
Задача 4.2 Фірма виготовляє продукцію трьох видів: А, В і С. Потрібний певний час для обробки одиниці кожного виду продукції на різному обладнанні (табл. 4.2). Таблиця 4.2 Тривалість обробки продукції, год Тип обладнання Тривалість обробки одиниці продукції виду Тривалість роботи обладнання на місяць
А В С
І 1 2 4 360
ІІ 2 4 2 520
ІІІ 1 1 2 220
Ціна одиниці продукції видів А, В і С дорівнює 90 дол., 110 дол. та 150 дол. відповідно. Визначити, яку продукцію і в якому обсязі слід виготовляти, щоб фірма отримувала найбільший дохід. Розв’язавши цю задачу симплекс-методом, отримаємо таку останню симплексну таблицю: Базис Сбаз План 90 110 150 0 0 0
х1 х2 х3 х4 х5 х6
х4 0 100 0 0 3 1 –1/2 0
х2 110 40 0 1 –1 0 1/2 –1
х1 90 180 1 0 3 0 –1/2 2
Fj – cj ( 0 20 600 0 0 10 0 10 70
Керівництво фірми цікавить відповідь на таке запитання: «Чи зміниться оптимальний план виробництва продукції і якщо зміниться, то яким буде новий оптимальний план у кожній з наведених нижче ситуацій?» 1. Фірма може збільшити тривалість роботи обладнання типів 2 та 3 відповідно на 100 і 80 год на місяць, орендуючи для цього додаткове обладнання, але орендна плата становитиме 5000 дол. Чи вигідно це? Якщо вигідно, то яким має бути новий оптимальний план виробництва продукції? 2. Фінансовий відділ фірми вважає, що загострення конкуренції на ринку збуту може призвести до зниження ціни на продукцію В на 25 дол. Як це позначиться на оптимальному плані виробництва продукції фірми? 3. Відділ досліджень і розробок фірми пропонує виготовляти дешевшу модифікацію продукції С. Тривалість обробки одиниці цієї нової продукції на обладнанні типів 1, 2 та 3 становить відповідно 4, 3 і 1 год. Орієнтовна ціна одиниці нової продукції дорівнює 120 дол. Керівництво фірми цікавить, чи буде за таких умов виробництво нової продукції вигідним. 4. Споживач продукції виду А за певних обставин порушив попередню домовленість і відмовився прийняти більш як 100 од. продукції. Визначити, як слід змінити план виробництва своєї продукції, щоб уникнути втрат, пов’язаних із надвиробництвом цього виду продукції. Розв’язання. Із наведеної в умові задачі симплекс-таблиці маємо: Х* = (180; 40; 0; 100; 0; 0), max F = 20600, Y* = (0; 10; 70). Оптимальним планом виробництва продукції на фірмі є випуск 180 од. продукції виду А та 40 од. продукції виду В. Виготовлення продукції виду С не передбачається. При цьому фірма отримає максимальну виручку обсягом 20600 дол. на місяць. 1. Збільшення тривалості роботи обладнання дасть змогу збільшити випуск продукції, тобто змінити оптимальний план і дохід фірми. Оскільки (b1 = 0, (b2 = 100, (b3 = 80, то новий оптимальний план визначається так: . Новий план допустимий (всі хj ( 0), і тому оптимальні значення двоїстих оцінок зберігаються: Y* = (0; 10; 70). Приріст доходу фірми в результаті зміни оптимального плану виробництва продукції розраховується так: max (Z = (b1y1 + (b2y2 + (b3y3 = 100 10 + 80 70 = 6600 дол. Оскільки дохід фірми від додаткового використання обладнання груп 2 і 3 перевищує витрати на його оренду (6600 > 5000), то природно, що така тактика фірми буде вигідною. При цьому оптимальним планом виробництва стане випуск 290од. продукції виду А і 10 од. продукції виду В. Невикористаний час роботи обладнання типу І зменшиться до 50 год на місяць, а дохід фірми за відрахуванням витрат на оренду обладнання дорівнюватиме 20600 + (6600 – 5000) = 22200 дол. на місяць. 2. Зниження ціни одиниці продукції В на (c2 (–25 дол.) стосується всього оцінкового рядка симплекс-таблиці, оскільки х2 є базисною змінною. Нові Fj – cj матимуть такі значення: F3 – c3 = 10 – 1(c2 = 10 + 25 = 35; F5 – c5 = 10 + 1/2(c2 = 10 – 12,5 = –2,5; F6 – c6 = 70 – 1(c2 = 70 + 25 = 95. Якби всі здобуті оцінки задовольняли умову Zj – Cj ( 0, то це означало б, що попри зниження ціни план виробництва продукції на фірмі не зміниться. Але оцінка F5 – c5 не задовольняє умову оптимальності задачі на максимум, і тому можна висновувати, що істотне зниження ціни одиниці продукції виду В порушує визначений раніше оптимальний план виробництва продукції, оскільки випуск цієї продукції стає для фірми невигідним, нерентабельним. Новий оптимальний план визначається у процесі подальшого розв’язання задачі симплекс-методом: Базис Сбаз План 90 85 150 0 0 0
х1 х2 х3 х4 х5 х6
х4 0 100 0 0 3 1 –1/2 0
х2 85 40 0 1 –1 0 1/2 –1
х1 90 180 1 0 3 0 –1/2 2
Fj – cj ( 0 19 600 0 0 35 0 –2,5 95
х4 0 140 0 1 2 1 0 –1
х5 0 80 0 2 –2 0 1 –2
х1 90 220 1 1 2 0 0 1
Fj – cj ( 0 19 800 0 5 30 0 0 90
Отже, у розглянутій ситуації зниження ціни одиниці продукції виду В на 25 дол. різко змінить структуру та обсяги виробництва продукції на фірмі. Вигідним стане випуск лише продукції виду А обсягом 220 од.: при цьому можливий час роботи обладнання типів 1 та 2 використовуватиметься не повністю. Усе це призведе до зменшення виручки фірми до 19 800 дол. на місяць. 3. Обсяг виробництва нової продукції в оптимальному плані позначимо через х7. Тоді математична модель прямої задачі матиме такий вигляд:
У математичній моделі двоїстої задачі змінній х7 відповідатиме таке обмеження: . Оцінимо рентабельність виробництва нової продукції за допомогою двоїстих оцінок: 4 · 0 + 3 · 10 + 1 · 70 = 100, що є меншим за 120. Отже, загальна вартість усіх ресурсів, що витрачаються на випуск одиниці нової продукції, не перевищує орієнтовної ціни цієї продукції, і тому її виробництво для фірми є вигідним, рентабельним. Завдяки цьому визначений раніше оптимальний план виробництва продукції можна поліпшити за рахунок уведення в нього х7. Для цього за допомогою оберненої матриці необхідно визначити елементи стовпчика «х7» останньої симплекс-таблиці:
Результати однієї ітерації симплекс-методу, що приводить до нового оптимального плану задачі, наведено нижче. Базис Сбаз План 90 110 150 0 0 0 120 (
х1 х2 х3 х4 х5 х6 х7
х4 0 100 0 0 3 1 –1/2 0 5/2 40
х2 110 40 0 1 –1 0 1/2 –1 1/2 80
х1 90 180 1 0 3 0 –1/2 2 1/2 360
Fj – cj ( 0 20 600 0 0 10 0 10 70 –20
х7 120 40 0 0 6/5 2/5 –1/5 0 1
х2 110 20 0 1 –8/5 –1/5 3/5 –1 0
х1 90 160 1 0 12/5 –1/5 –2/5 2 0
Fj – cj ( 0 21 400 0 0 34 8 6 70 0
Отже, оптимальним планом є Х* = (160; 20; 0; 0; 0; 0; 40), а max Z = 21 400. Керівництво фірми має підтримати пропозицію відділу досліджень та розробок і налагодити виробництво нової продукції, яка є рентабельною. Виготовляючи її обсягом 40 од., а також продукцію видів А та В обсягом 160 і 20 од. відповідно, фірма зможе збільшити обсяг виручки до 21400 дол. на місяць згідно з новим оптимальним планом виробництва продукції. 4. Четверта запропонована ситуація математично пов’язана із введенням в умову задачі додаткового обмеження, що може привести до таких наслідків: а) нове обмеження для визначеного оптимального плану виконується. Тоді воно є надлишковим, зайвим і його включення до моделі не змінює визначеного плану; б) нове обмеження для визначеного оптимального плану не виконується, і тоді за допомогою двоїстого симплекс-методу необхідно знайти новий оптимальний план. За умовою задачі додатковим є обмеження х1 < 100. Але воно суперечить оптимальному обсягу продукції виду А, що дорівнює 180 од. Тому необхідно приєднати це додаткове обмеження до симплекс-таблиці та продовжити розв’язання задачі, але вже за допомогою двоїстого симплекс-методу. Для цього спочатку зведемо додаткове обмеження до канонічного вигляду: х1 + х7 = 100. Оскільки в оптимальному плані змінна х1 є базисною, то її необхідно записати через небазисні невідомі. Це робиться так. У симплекс-таблиці, яку наведено в умові задачі, рядок змінної «х1» подається рівнянням: 1 · х1 + 0 · х2 + 3 · х3 + 0 · х4 – 1/2 · х5 + 2 · х6 = 180. З нього запишемо вираз для х1: х1 = 180 – 3х3 + 1/2х5 – 2х6. Підставивши цей вираз в додаткове обмеження, отримаємо: 180 – 3х3 + 1/2х5 – 2х6 + х7 = 100 або – 3х3 + 1/2х5 – 2х6 + х7 = – 80. Базис Сбаз План 90 110 150 0 0 0 0
х1 х2 х3 х4 х5 х6 х7
х4 0 100 0 0 3 1 –1/2 0 0
х2 110 40 0 1 –1 0 1/2 –1 0
х1 90 180 1 0 3 0 –1/2 2 0
х7 0 – 80 0 0 –3 0 1/2 –2 1
Fj – cj ( 0 20 600 0 0 10 0 10 70 0
х4 0 20 0 0 0 1 0 –2 1
х2 110 200/3 0 1 0 0 1/3 –1/3 –1/3
х1 90 100 1 0 0 0 0 0 1
х3 150 80/3 0 0 1 0 –1/6 2/3 –1/3
Fj – cj ( 0 61 000/3 0 0 0 0 35/3 190/3 10/3
У такому вигляді додаткове обмеження допишемо в симплекс-таблицю. Застосування двоїстого симплекс-методу приведе до нового оптимального плану задачі. В останній таблиці маємо: Х* = (100; 200/3; 80/3; 20; 0;0), а max Z = 61000/3 ( 20333. Проаналізуємо цей план. Прийнявши до уваги ситуацію, що склалася, керівництво фірми змушене змінити структуру виробництва продукції. Тепер з урахуванням вимог споживача фірма виготовлятиме 100 од. продукції виду А, 200/3 од. продукції виду В і 80/3 од. продукції виду С. У результаті такого плану випуску продукції виручка фірми дещо зменшиться (до 20333 дол. на місяць). ТРАНСПОРТНА ЗАДАЧА Компанія контролює три фабрики А1, А2, А3, здатні виготовляти відповідно 150, 60 та 80 тис. од. продукції щотижня. Вона уклала договір із чотирма замовниками В1, В2, В3, В4, яким потрібно щотижня доставляти відповідно 110, 40, 60 та 80 тис. од. продукції. Вартість транспортування 1000 од. продукції замовникам з кожної фабрики наведена в табл. 5.10. Фабрика Вартість транспортування 1000 од. продукції замовнику
В1 В2 В3 В4
А1 4 4 2 5
А2 5 3 1 2
А3 2 1 4 2
ВИЗНАЧИТИ ОПТИМАЛЬНИЙ ПЛАН ПЕРЕВЕЗЕНЬ ПРОДУКЦІЇ ВІД КОЖНОЇ ФАБРИКИ ДО ЗАМОВНИКІВ, ЩО МІНІМІЗУЄ ЗАГАЛЬНУ ВАРТІСТЬ ТРАНСПОРТНИХ ПОСЛУГ. Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-ї фабрики до j-го замовника . Оскільки транспортна задача за умовою є збалансованою, закритою то математична модель задачі матиме вигляд:
ЕКОНОМІЧНИЙ ЗМІСТ ЗАПИСАНИХ ОБМЕЖЕНЬ ПОЛЯГАЄ В ТОМУ, ЩО ВСЯ ВИРОБЛЕНА НА ФАБРИКАХ ПРОДУКЦІЯ МАЄ ВИВОЗИТИСЯ ДО ЗАМОВНИКІВ ПОВНІСТЮ. АНАЛОГІЧНІ ОБМЕЖЕННЯ МОЖНА ЗАПИСАТИ ВІДНОСНО ЗАМОВНИКІВ: ПРОДУКЦІЯ, ЩО МОЖЕ НАДХОДИТИ ДО СПОЖИВАЧА ВІД ТРЬОХ ФАБРИК, МАЄ ПОВНІСТЮ ЗАДОВОЛЬНЯТИ ЙОГО ПОПИТ. МАТЕМАТИЧНО ЦЕ ЗАПИСУЄТЬСЯ ТАК:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування 1000 од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так: min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + 2x31 + + x32 +4x33 +2x34. ЗАГАЛОМ МАТЕМАТИЧНА МОДЕЛЬ СФОРМУЛЬОВАНОЇ ЗАДАЧІ МАЄ ВИГЛЯД: min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + 2x31 + x32 ++ 4x33 +2x34 ЗА УМОВ:
Методи побудови опорного планц транспортної задачі. Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. Спочатку, не враховуючи вартості перевезень, завжди задовольняють потреби першого споживача В1, використовуючи запаси першого постачальника А1. У нашому прикладі (табл. 5.2) потреби споживача В1 становлять = 110, а запаси постачальника — = 150 одиниць (тобто із запасів першого постачальника можна повністю задовольнити потреби першого споживача), тому в клітинку А1В1 записуємо менше із значень , , тобто 110. Тепер потреби першого споживача повністю задоволені, і переходимо до задоволення потреб наступного (другого) споживача В2. Обсяг його потреб = 50. Після задоволення потреб першого споживача залишок запасів першого постачальника становить 150 –– 110 = 40. Отже, від першого виробника другому споживачеві можна перевезти лише 40 одиниць продукції, тому в клітину А1В2 записуємо число 40. Після цього, оскільки запаси першого постачальника повністю вичерпані, переходимо до використання запасів наступного постачальника А2. Його запаси = 60, а незадоволені потреби другого споживача 50 – 40 = 10, тому в клітинку А2В2 записуємо число 10, і другий споживач у такий спосіб також повністю отримав необхідну кількість продукції. Переходимо до задоволення потреб наступного споживача В3. У результаті часткового використання запасів другого постачальника його залишок продукції становить 60 – 10 = 50. Отже, від другого виробника до третього споживача можна перевезти 50 одиниць продукції. Клітинка А2В3 міститиме зазначене число 50, і цим запаси постачальника А2 будуть повністю вичерпані. Переходимо до розподілу запасів останнього (третього) постачальника А3. Залишились незадоволеними потреби третього споживача в обсязі 60 –50 = 10. Для їх задоволення скористаємося запасами постачальника А3. У клітинку А3В3 записуємо число 10, і потреби споживача В3 також повністю задоволені. Переходимо до останнього споживача В4 з потребами b4 = 80, які повністю задовольняються за рахунок залишку запасів третього постачальника: 90 – 10 = 80. Таблиця 5.2 Постачальники Запаси Споживачі
B1 B2 B3 B4
Потреби
b1 = 110 b2 = 50 b3 = 60 b4 = 80
А1 а1 = 150 4 110 4 40 2 5
А2 а2 = 60 5 3 10 1 50 2
А3 а3 = 90 2 1 4 10 2 80
ОТЖЕ, В ТАБЛИЦІ 5.2 У ЗАПОВНЕНИХ КЛІТИНКАХ ЗНАХОДЯТЬСЯ ЧИСЛА, ЩО ОЗНАЧАЮТЬ МОЖЛИВИЙ ПЛАН ПЕРЕВЕЗЕНЬ ПРОДУКЦІЇ. СУМА ЧИСЕЛ (ПЕРЕВЕЗЕНЬ) ПО РЯДКАХ ДОРІВНЮЄ ОБСЯГАМ ЗАПАСІВ ПОСТАЧАЛЬНИКІВ, А СУМА ЧИСЕЛ ПО СТОВПЦЯХ — ОБСЯГАМ ПОТРЕБ ВІДПОВІДНИХ СПОЖИВАЧІВ. Визначимо загальну вартість перевезень згідно з початковим опорним планом. Від першого постачальника до першого споживача необхідно перевезти 110 одиниць продукції за ціною 4 ум. од. (ціна записана в правому верхньому куті кожної клітини), отже, це коштуватиме 110*4=440ум. од. Крім того, необхідно перевезти від першого постачальника 40 одиниць продукції до другого споживача за ціною 4 ум. од. і т. д. У такий спосіб визначимо загальну вартість усіх перевезень: (ум. од.).Записуємо оптимальний план, за допомогою матриці: Ідея методу мінімальної вартості полягає в тому, що на кожному кроці заповнюють клітинку таблиці, яка має найменшу вартість перевезення одиниці продукції. Такі дії повторюють доти, доки не буде розподілено всю продукцію між постачальниками та споживачами. Складемо за допомогою цього методу план розглянутої задачі (табл. 5.3). Найменшу вартість мають перевезення, які здійснюються від А2 до В3 та від А3 до В2 (ціна перевезення одиниці продукції — 1 ум. од.). Заповнимо будь-яку з них, наприклад, А2В3. Оскільки постачальник має 60 одиниць продукції, а споживач потребує саме такої її кількості, то в клітину А2В3 ставимо значення 60. У такий спосіб запаси другого постачальника повністю вичерпані, а потреби третього споживача повністю задоволені. Також мінімальною є вартість перевезень від третього постачальника до другого споживача, тому заповнимо також клітину А3В2. З клітинок таблиці, що залишились незаповненими, вибираємо наступне мінімальне значення вартості перевезень, яке дорівнює 2 ум. од. — для клітин А1В3, А2В4, А3В1 та А3В4. Заповнення клітин А2В4 та А1В3 неможливе, оскільки постачальник А2 вже повністю вичерпав власний обсяг запасів, задовольняючи потреби споживача В3, а споживач В3 повністю задовольнив свої потреби. Отже, можна заповнити тільки клітину А3В1 чи А3В4. Заповнимо А3В1. Обсяг запасів а3 = 90, причому 50 одиниць продукції вже надано другому споживачеві. Отже, маємо залишок 90 – 50 = 40, а потреби b1 = 110, тому від третього постачальника до першого споживача плануємо перевезти 40 одиниць продукції. Тепер у клітину А3В4 не можна записати будь-який обсяг постачання, оскільки запаси третього постачальника вже повністю вичерпані. Знову вибираємо найменшу вартість для клітин таблиці, що залишилися пустими, і продовжуємо процес доти, поки всі запаси не будуть розподілені, а потреби — задоволені. Таблиця 5.3 bj ai b1 = 110 b2 = 50 b3 = 60 b4 = 80
а1 = 150 4 70 4 2 5 80
а2 = 60 5 3 1 60 2
а3 = 90 2 40 1 50 4 2
В результаті таких міркувань отримали початковий опорний план, загальна вартість перевезень для якого становить: (ум. од.). Значення цільової функції менше за попередній варіант, значить цей план ближчий до оптимального. МЕТОД ПОДВІЙНОЇ ПЕРЕВАГИ. ЯКЩО РОЗМІРНІСТЬ ЗАДАЧІ ДОСИТЬ ВЕЛИКА, ТО ПЕРЕБІР ЗА МЕТОДОМ МІНІМАЛЬНОЇ ВАРТОСТІ УСКЛАДНЮЄТЬСЯ. В ТАКОМУ РАЗІ СПРОСТИТИ ПОШУК КЛІТИН З НАЙМЕНШИМИ ВАРТОСТЯМИ МОЖНА, ЗАСТОСОВУЮЧИ МЕТОД ПОДВІЙНОЇ ПЕРЕВАГИ. ЗГІДНО З ПРОЦЕДУРОЮ ЦЬОГО МЕТОДУ ПЕРЕД ПОЧАТКОМ ЗАПОВНЕННЯ ТАБЛИЦІ НЕОБХІДНО ПОЗНАЧИТИ БУДЬ-ЯКИМИ СИМВОЛАМИ КЛІТИНКИ, ЯКІ МІСТЯТЬ НАЙМЕНШУ ВАРТІСТЬ У РЯДКАХ, А ПОТІМ — У СТОВПЧИКАХ. ТАБЛИЦЮ ПОЧИНАЮТЬ ЗАПОВНЮВАТИ З КЛІТИНОК, ПОЗНАЧЕНИХ ДВІЧІ (ЯКІ МІСТЯТЬ ВАРТОСТІ, ЩО Є МІНІМАЛЬНИМИ І В РЯДКУ, І В СТОВПЧИКУ). ДАЛІ ЗАПОВНЮЮТЬ КЛІТИНКИ, ПОЗНАЧЕНІ ОДИН РАЗ (ЩО МІСТЯТЬ МІНІМАЛЬНІ ВАРТОСТІ АБО В РЯДКУ, АБО В СТОВПЧИКУ), А ВЖЕ ПОТІМ — ЗА МЕТОДОМ МІНІМАЛЬНОЇ ВАРТОСТІ. Таблиця 5.4 bj ai b1 = 110 b2 = 50 b3 = 60 b4 = 80
а1 = 150 4 110 4 V 2 5 40
а2 = 60 5 3 VV 1 60 V 2
а3 = 90 V 2 VV 1 50 4 V 2 40
(ум. од.). ЗАСТОСУВАННЯ ДЛЯ ПОБУДОВИ ОПОРНОГО ПЛАНУ ДАНОГО МЕТОДУ УМОЖЛИВЛЮЄ ОТРИМАННЯ НАЙМЕНШОГО У ЗІСТАВЛЕННІ З РОЗГЛЯНУТИМИ ВИЩЕ ЗНАЧЕННЯ ЦІЛЬОВОЇ ФУНКЦІЇ. ОТЖЕ, ТАКИЙ ПЛАН Є НАЙБЛИЖЧИМ ДО ОПТИМАЛЬНОГО. ДРОБОВО-ЛІНІЙНЕ ПРОГРАМУВАННЯ: Розв’яжіть графічно задачу дробово-лінійного програмування:
за умов:
. Розв’язання. Побудуємо на площині область допустимих розв’язків задачі. Маємо трикутник АВС.
Рис. 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 знайдемо за формулою
Графічний метод У разі, коли задача дробово-лінійного програмування містить лише дві змінні, для її розв’язування зручно скористатися графічним методом. Нехай маємо таку задачу: (7.4) за умов: (7.5) , (7.6) Спочатку, як і для звичайної задачі лінійного програмування будуємо геометричне місце точок системи нерівностей (7.5), що визначає деякий багатокутник допустимих розв’язків. Допустимо, що , і цільова функція набуває деякого значення: . Після елементарних перетворень дістанемо:
або . (7.7) Останнє рівняння описує пряму, що обертається навколо початку системи координат залежно від зміни значень х1 та х2. Розглянемо кутовий коефіцієнт нахилу прямої (7.7), що виражає цільову функцію: . (7.8) Отже, кутовий коефіцієнт являє собою функцію від Z. Для визначення умов зростання (спадання) функції (7.8) дослідимо зміну знака її похідної: (7.9) Використовуючи формулу (7.9), можна встановити правила пошуку максимального (мінімального) значення цільової функції: 1.) якщо , то функція (7.8) є зростаючою, і за збільшення значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (7.7) також збільшується. Тобто у разі, якщо , для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку проти годинникової стрілки; 2.)якщо , то функція (7.8) є спадною і за збільшення значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (7.7) буде зменшуватись. Тому у разі, якщо , для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку за годинниковою стрілкою. При розв’язуванні задачі дробово-лінійного програмування графічним методом можливі такі випадки: -багатокутник розв’язків задачі обмежений і максимальне та мінімальне значення досягаються у його кутових точках; -багатокутник розв’язків задачі необмежений, однак існують кутові точки, в яких досягаються максимальне та мінімальне значення цільової функції; -багатокутник розв’язків задачі необмежений і досягається лише один із екстремумів; -багатокутник розв’язків задачі необмежений, точки екстремумів визначити неможливо. Розв’язування зведенням до задачі лінійного програмування Нехай потрібно розв’язати задачу (7.1)—(7.3). Позначимо і введемо заміну змінних . Тоді цільова функція (7.1) матиме вигляд: Отримали цільову функцію, що виражена лінійною залежністю. Оскільки , то звідси маємо: . Підставимо виражені через нові змінні значення в систему обмежень (7.2):
Крім того, з початкової умови Умова (7.3) стосовно невід’ємності змінних набуває вигляду: . Виконані перетворення приводять до такої моделі задачі:
Отримали звичайну задачу лінійного програмування, яку можна розв’язувати симплексним методом. Допустимо, що оптимальний розв’язок останньої задачі існує і позначається: . Оптимальні значення початкової задачі (7.1)—(7.3) визначають за формулою: . Задачі нелінійного програмування. Задача№1 Знайти мінімальне і максимальне значення функції:
за умов:
. Розв’язання. Область допустимих розв’язків утворює чотирикутник АВСD (рис. 8.1).
Геометрично цільова функція являє собою коло з центром у точці М (2; 2), квадрат радіуса якого . Це означає, що її значення буде збільшуватися (зменшуватися) зі збільшенням (зменшенням) радіуса кола. Проведемо з точки М кола різних радіусів. Функція Z має два локальних максимуми: точки В (0; 6) і С (8; 0). Обчислимо значення функціонала в цих точках: , . Оскільки , то точка С (8; 0) є точкою глобального максимуму. Очевидно, що найменший радіус , тоді: . Тобто точка М є точкою мінімуму, оскільки їй відповідає найменше можливе значення цільової функції. Зазначимо, що в даному разі точка, яка відповідає оптимальному плану задачі (мінімальному значенню функціонала), знаходиться всередині багатокутника допустимих розв’язків, що в задачах лінійного програмування неможливо. Задача№2 Знайти мінімальне значення функції:
за умов:
. Розв’язування. У даному прикладі множина допустимих розв’язків складається з двох окремих частин, необмежених зверху (рис. 8.2). Цільова функція аналогічно попередньому випадку є колом з центром у точці М (4; 4). Функція Z має два локальних мінімуми: в точці А (), і в точці В ().
Значення функціонала в цих точках однакове і дорівнює: . Отже, маємо два альтернативні оптимальні плани. Задача №3 Акціонерне товариство з обмеженою відповідальністю виділило 1200 га ріллі під основні сільськогосподарські культури — озиму пшеницю і цукрові буряки. У табл. 8.1 маємо техніко-економічні показники вирощування цих культур: Таблиця 8.1 Показник Озима пшениця х1, сотні га Цукрові буряки х2, сотні га
Урожайність, т/га 4 35
Ціна, грн/т 800 300
Собівартість, грн/т
Необхідно знайти оптимальні площі посіву озимої пшениці та цукрових буряків. Нехай: х1 — площа ріллі під озимою пшеницею, сотні га; х2 — площа ріллі під цукровими буряками, сотні га. Звернемо увагу на те, що собівартість тонни пшениці та цукрових буряків залежить від відповідної площі посіву. Запишемо економіко-математичну модель цієї задачі. Критерієм оптимальності візьмемо максимізацію чистого доходу:
за умов:
Запишемо функцію Лагранжа:
Візьмемо частинні похідні і прирівняємо їх до нуля:
З цієї системи рівнянь визначаємо координати сідлових точок. З першого та другого рівняння знаходимо (1 і, прирівнюючи вирази, маємо: (8.10) або, скоротивши на 100 обидві частини і розкривши дужки, отримаємо:
(8.11) Із останнього рівняння системи маємо: . Підставимо вираз для у рівність (8.11). Отримаємо:
або
Отже, ;
. (553 га); (178 га). Відповідно дістаємо: га); га). Тобто отримали дві сідлові точки:
Перевіримо за допомогою достатньої умови існування екстремуму спочатку сідлову точку . Матриця Гессе має такий вигляд: . За вищезазначеним правилом визначаємо головні мінори, починаючи з 2-го порядку (): , . Отже, головні мінори утворюють знакозмінний ряд та, починаючи з головного мінору 2-го порядку, наступний мінор визначається знаком , тобто є точкою максимуму. Обчислимо значення цільової функції в цій точці:
Аналогічні обчислення для точки показують, що вона не є екстремальною. Отже, цільова функція набуде максимального значення, якщо озима пшениця вирощуватиметься на площі 647 га, а цукрові буряки — на площі 553 га. Задача№4 Визначити вид квадратичної форми:
Матриця С має вигляд: . Запишемо характеристичне рівняння . Звідси маємо: . Коренями отриманого квадратного рівняння є: , тоді . Отже, квадратична форма за теоремою 8.5 є напіввід’ємною. Задача№5 Підприємство виробляє два види продукції (А і В) і використовує на виробництво три види ресурсів: І, ІІ, ІІІ. Витрати ресурсів на виробництво одиниці кожного виду продукції подано в табл. 8.2. Таблиця 8.2 Вид ресурсу Вид продукції Загальний обсяг ресурсу
А В
І 1 3 30
ІІ 1 1 15
ІІІ 5 2 60
Ціна реалізації одиниці продукції виду А становить 20 ум. од., проте прибуток залежить від витрат на виробництво, які пропорційні квадрату кількості виготовленої продукції. Аналогічно визначається прибуток для продукції виду В, ціна реалізації якої дорівнює 18 ум. од. Розв’язання. Позначимо через х1 кількість продукції виду А, х2 — кількість продукції виду В, тоді загальний прибуток матиме вигляд: . Математична модель задачі має вигляд: ,
. Розв’яжемо задачу методом Франка Вульфа. І ітерація Вибираємо точку, що належить множині допустимих планів задачі. Розглянемо, наприклад, точку . Визначимо градієнт цільової функції: . В точці обчислюємо значення градієнта: . Використовуючи розраховане значення градієнта, записуємо і вводимо нову цільову функцію: . Маємо таку задачу лінійного програмування:
. Розв’язуючи цю задачу симплексним методом, знаходимо її оптимальний план: . Знайдемо новий допустимий план задачі, використовуючи формулу для визначення координат наступної точки. Визначаємо координати точки Х1: , ,
Знайдемо крок такий, за якого досягається максимальне значення цільової функції. Для цього підставимо розраховані значення для х1, х2, які виражені через , у цільову функцію :
Отримали функцію, що залежить від . Знайдемо значення , за якого функція досягає максимуму, тобто коли її похідна дорівнює нулю: Оскільки , то беремо . Тоді наступна точка Х1 має координати: . Для знайденої точки обчислюємо значення цільової функції: . ІІ ітерація Узявши точку , обчислюємо значення градієнта в ній:
Використовуючи розраховане значення градієнта, вводимо нову цільову функцію: . Отримуємо таку задачу лінійного програмування:
. Розв’язавши її симплексним методом, отримуємо оптимальний план: . За формулою визначаємо координати наступної точки наближення. Визначаємо координати точки Х2: , Знайдемо такий крок ?2, за якого досягається максимальне значення цільової функції:
Матимемо . Обчислимо координати наступної точки Х2:
Для знайденої точки значення цільової функції дорівнює: . Продовжуючи процес у аналогічний спосіб, на ІІІ ітерації визначаємо точку і переконуємося, що значення цільової функції знову зростає: . На IV ітерації розраховуються координати точки , для якої . V ітерація Узявши точку , обчислюємо значення градієнта в ній: . Використовуючи значення цього вектора (градієнта), вводимо нову цільову функцію: і маємо таку задачу лінійного програмування: ,
. Розв’язавши цю задачу, отримаємо значення оптимального плану , тобто повертаємося до попереднього значення. Отже, точку з координатами вважаємо оптимальним планом, оскільки маємо нульовий градієнт функції, тобто цей план поліпшити вже не можна. 12. Розв’язати графічним методом наступну задачу дробово-лінійного програмування:
