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