| КОНТРОЛЬНА РОБОТА
з дисципліни
„Математичне програмування”
Завдання 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 грошову одиницю. Потрібно скласти виробничий план, який максимізує дохід підприємства.
Математична модель прямої задачі:
за умов
Математична модель двоїстої задачі:
Економічна інтерпретація двоїстої задачі
: двоїсті змінні у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.
|
