Побудова математичної моделі задачі лінійного програмування КОНТРОЛЬНА РОБОТА з дисципліни „Математичне програмування” Завдання 1 1) Побудувати математичну модель задачі лінійного програмування. 2) Звести дану задачу до канонічного вигляду. Діва вироби В1 і В2 обробляються послідовно на трьох верстатах. Кожний виріб типу В1 потребує 1 год. для обробки на першому верстаті, 2 год. – на ІІ-му і А год. – на третьому. Кожний виріб В2 потребує для обробки 2 год, А год. і 3 год. відповідно на І-му, ІІ-му і ІІІ-му верстатах. Час роботи на першому верстаті не повинен перевищувати 10N год., на ІІ-му – 15N год., на ІІІ-му – 50 год. Скласти план виробництва при максимальному прибутку, якщо відомо, що продаж одного виробу типу В1 приносить прибуток 5 грн., а типу В2 – 3 грн. Примітка : А= , тобто А= . Розв’язання. Типи верстатів Затрати часу, год Час роботи, год В1 В2 І в 1 2 60 ІІ в 2 А 90 ІІІ в А 3 50 Прибуток, грн 5 3 1) Математична модель задачі. Позначимо кількість виробів В1 і В2 відповідно х1 та х2 . Цільова функція (величина прибутку), яку потрібно максимізувати Спеціальні обмеження задачі визначаються обмеженнями часу роботи верстатів і нормативами часу обробки виробів на верстатах. При обсягу випуску виробів В1 і В2 відповідно х1 та х2 і заданих нормативах часу обробки час роботи першого верстату дорівнює час роботи другого верстату час роботи третього верстату Спеціальні обмеження є наступними: Загальні обмеження задачі витікають з природи економічних змінних і полягають у тому, що вони не можуть мати від’ємні значення, тобто Отже маємо математичну модель задачі: за умов Словесно задача формулюється таким чином: знайти значення змінних х1 та х2 , які задовольняють заданій системі обмежень і доставляють максимальне значення цільовій функції Z. 2) У канонічній формі задачі лінійного програмування спеціальні обмеження подаються рівностями. Перехід до канонічної форми здійснюється шляхом введення додаткових (фіктивних) змінних, які перетворюють нерівності на рівності. В даному випадку до першого обмеження вводиться змінна х3 , до другого – х4, до третього – х5. Додаткові змінні вводяться зі знаками „+”, оскільки обмеження мають тип „ ”. Математична модель задачі у канонічній формі: за умов Завдання 2 Розв’язати задачу лінійного програмування графічним методом за умов Розв’язання. В декартовій системі координат х1 Ох2 будуємо прямі, які визначаються нерівностями системи обмежень. Це прямі ; ; . Кожна пряма ділить площину х1 Ох2 на дві половини, в одній з яких виконується відповідна нерівність системи обмежень, а в іншій не виконується. Півплощини, в яких виконуються нерівності системи обмежень позначені штриховою біля прямих. Переріз цих півплощин являє собою область припустимих планів задачі. Це – чотирикутник ОАВС. Цільова функція визначає сімейство паралельних прямих ліній з різними значеннями параметра z . При z=0 маємо пряму , що проходить через початок координат. Збільшенню значення параметра z відповідає переміщення прямої цільової функції у напрямку, позначеному вектором n+ . Безпосередньо з креслення видно, що максимальному значенню параметра z (максимуму цільової функції при заданих обмеженнях) відповідає точка припустимої області, яка є вершиною В чотирикутника ОАВС (це остання точка припустимої області, яка належить прямій цільової функції z при її переміщенні у напрямку збільшення параметра z ). Координати (х1 , х2 ) цієї точки є шуканим оптимальним планом задачі. З креслення визначаємо: . Отже, оптимальним планом даної задачі є , цільова функція при цьому набуває максимального значення . Завдання 3 Розв’язати систему лінійних рівнянь методом повного виключення змінних з використанням розрахункових таблиць. Будуємо розрахункову таблицю і обираємо за ведучий елемент а21 =1 (у таблиці виділений): х1 х2 х3 B 3 -2 2 -3 1 4 -1 0 4 -1 4 6 Перераховуючи елементи таблиці, виключаємо з першого і третього рівнянь (перший і третій рядки таблиці) змінну х1 , отримуємо х1 х2 х3 B 0 -14 5 -3 1 4 -1 0 0 -17 8 6 Обираємо за ведучий елемент а12 =-14 (у таблиці виділений) і, виконавши перерахунок, виключаємо змінну х2 з другого і третього рівнянь. Отримуємо таблицю х1 х2 х3 B 0 1 -5/14 3/14 1 0 3/7 -6/7 0 0 27/14 135/14 Обираємо за ведучий елемент а33 =-27/14 (у таблиці виділений) і, виконавши перерахунок, виключаємо змінну х3 з першого і другого рівнянь. Отримуємо таблицю х1 х2 х3 B 0 1 0 2 1 0 0 -3 0 0 1 5 З останньої таблиці, яка відповідає системі рівнянь з повністю виключеними змінними, знаходимо розв’язок системи рівнянь: Завдання 4 1) Розв’язати симплекс-методом задачу лінійного програмування, яка представлена у Завданні 2. 2) Побудувати двоїсту задачу до заданої задачі лінійного програмування. 3) Знайти розв’язок двоїстої задачі та дати економічну інтерпретацію отриманого розв’язку. Розв’язання. 1) Задача лінійного програмування: а) Зводимо задачу до канонічної форми введенням додаткових змінних х3 та х4 . б) Дана задача має початковий опорний план (0;0;6;6;), при якому цільова функція дорівнює нулю. У даному опорному плані базисними є додаткові змінні х3 та х4 , а змінні х1 та х2 є вільними. в) Запишемо цільову функцію у вигляді, виразивши її через небазисні змінні, г) Будуємо симплекс-таблицю, в яку заносимо початковий опорний план: Базисні змінні х1 х2 х3 х4 B Базисний розв’язок Х3 -1 3 1 0 6 (0;0;6;6) Х4 3 -1 0 1 6 Z -1 -1 0 0 0 Даний опорний план не є оптимальним, оскільки рядок цільової функції містить від’ємні значення (коефіцієнти при змінних). Перехід до нового опорного плану, виконуємо шляхом заміни змінної х3 на змінну х2 . Вибір змінних для заміни базиса обумовлюється тим, що у записі змінної х3 через небазисні змінні (х1 та х2 ) коефіцієнт при змінній х2 має найбільше негативне значення (-3). Отже, ведучим елементом обираємо а12 =3 (у таблиці виділений). В результаті перехунку таблиці, отримуємо другу таблицю: Базисні змінні х1 х2 х3 х4 B Базисний розв’язок Х2 1 0 2 (0;2;0;8) Х4 0 1 8 Z 0 0 2 Отриманий опорний план не є оптимальним, оскільки рядок цільової функції містить від’ємне значення (а31 = ). Для переходу до нового базису і, відповідно нового опорного плану, обираємо ведучим елементом а21 = (він лежить у стовпчику, де знаходиться негативний коефіцієнт у виразі цільової функції, і є позитивним). В результаті перехунку, отримуємо наступну таблицю: Базисні змінні х1 х2 х3 х4 B Базисний розв’язок Х2 0 1 3 (3;3;0;0) Х1 1 0 3 Z 0 0 6 Отриманий опорний план є оптимальним, оскільки у рядку цільової функції містять ся тільки позитивні значення. Отже, оптимальний план є , цільова функція при цьому набуває максимального значення . 2)Двоїста задача лінійного програмування формулюється відносно двоїстих змінних у1 , у2 і утворюється шляхом транспонування матриці коефіцієнтів обмежень, взаємної заміни коефіцієнтів цільової функції і вільних членів системи обмежень і зміни типу нерівностей (>= на <= і навпаки), а також зміни критерія оптимізація цільової функції на протилежний (максимізація на мінімізацію і навпаки). Двоїста задача: 2)Розв’язання двоїстої задачі виконуємо за допомогою процесора електронних таблиць MS Excel. Створюємо робочий лист з математичною моделлю задачі, який наведено на малюнку: Розв’язання здійснюється за допомогою надбудови Поиск решения. Вікно пошуку розв’язку, налаштоване для даної задачі показане на малюнку: Розв’язок задачі (оптимальний план двоїстої задачі) міститься у комірках В2 (змінна у1 ), С2 (змінна у2 ): у1 = 0,5; у2 := 0,5 Вікно MS Excel з розв’язком задачі: Економічна інтерпретація задачі. Будемо розглядати пряму задачу як задачу про оптимальне використання обмежених ресурсів. Підприємство виготовляє два види продукції П1 і П2 у кількостях х1 та х2 відповідно, використовуючи два види ресурсів Р1 та Р2, запаси яких обмежені і становлять 6 одиниць кожного; нормативи витрат ресурсів на одиницю продукції задані таблицею П1 П2 Р1 -1 3 Р2 3 -1 Ціна реалізації одиниці кожного продукту становить 1 грошову одиницю. Потрібно скласти виробничий план, який максимізує дохід підприємства. Математична модель прямої задачі: за умов Математична модель двоїстої задачі: Економічна інтерпретація двоїстої задачі : двоїсті змінні у1 та у2 – це ціни ресурсів Р1 та Р2 відповідно, і, таким чином, задача полягає у визначенні таких цін використовуваних ресурсів, при яких загальна вартість їх буде мінімальною. Отриманий оптимальний план двоїстої задачі показує, що оптимальною ціною ресурсів Р1 та Р2 є у1 =0,5 та у2 = 0,5 грошових одиниць. Обидва ресурси використовуються повністю і є дефіцитними (оскільки їх двоїсті оцінки більші нуля у1 >0, у2 > 0). Обидва види продукції є рентабельними (оскільки х1 >0 і х2 > 0). Двоїсті оцінки у1 =0,5 та у2 = 0,5 показують, що величина доходу підприємства (значення цільової функції прямої задачі) збільшиться на 0,5 при збільшенні величини на одиницю величини запасу кожного з ресурсів. Список використаної літератури 1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высш.шк., 1986. 2. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч.–метод. посіб. для самост. вивч. дисц. – К.: КНЕУ, 2001. 3. Кабак Л.Ф., Суворовский А.А. Математическое программирование. – К.: ИМКВО, 1992. 4. Калихман И.А. Сборник задач по математическому программированию. – М.: Высш.шк., 1975. 5. Савчук М.В. Лінійне програмування: Навч. посібник. – К.: ІПК ДСЗУ, 2006.