ЛАБОРАТОРНА РОБОТА № 2
по мат.программірованію
«Графічний і симплексний методи вирішення ОЗЛП»
Для виготовлення 2-х різних виробів А і В використовується 3 види сировини. На виробництво одиниці виробу А потрібно затратити сировини 1-го виду а1 кг, сировини 2-го виду - а2 кг, сировини 3-го виду - а3 кг. На виробництво одиниці вироби У потрібно затратити сировини 1-го виду в1 кг, сировини 2-го виду - в2 кг, сировини 3-го виду - в3 кг. Виробництво забезпечене сировиною 1-го виду в кількості Р1 кг, сировиною 2-го виду в кількості Р2 кг, сировиною 3-го виду в кількості Р3 кг. Прибуток від реалізації одиниці готового виробу А становить ден.ед., а вироби В - ден.ед.
№ | а1 | а2 | а3 | в1 | в2 | в3 | Р1 | Р2 | Р3 |
|
|
8 | 11 | 7 | 8 | 10 | 5 | 6 | 425 | 450 | 550 | 2 | 4 |
Математична модель задачі
Позначимо кількість виробленої продукції 1-го виду через х1, 2-го виду - х2. Тоді лінійна функція набуде вигляду: Z (х1, х2) = 2 * х1 +4 * х2.
Це є ціна виробленої продукції. Наше рішення має забезпечити максимальне значення цієї функції.
Умова накладає на величини х1 і х2 обмеження такого вигляду:
Побудована лінійна функція називається функцією мети і спільно системою обмежень утворює математичну модель розглянутої економічної задачі.
Графічне рішення задачі
Побудуємо багатокутник рішень. Для цього в системі координат х1Ох2 на площині зобразимо граничні прямі
х1 | 0 | 68,75 |
х2 | 91,66 | 0 |
х1 | 0 | 64,28 |
х2 | 90 | 0 |
х1 | 0 | 38,63 |
х2 | 42,5 | 0 |
Взявши яку-небудь точку, наприклад, початок координат, встановимо, яку полуплоскость визначає відповідне нерівність. Багатокутником рішень даної задачі є трикутник АОВ. Для побудови прямої 2 * х1 +4 * х2 = 0 будуємо радіус-вектор N = (2, 4) = 2.5 * (2, 4) = (5, 10) і через точку 0 проводимо пряму, перпендикулярну йому. Побудовану пряму Z = 0 переміщаємо паралельно самій собі в напрямку вектора N. Опорної по відношенню до багатокутника рішень ця пряма стає в точці А (0; 42,5), де функція Z приймає максимальне значення.
Оптимальний план завдання: х1 = 0; х2 = 42,5.
Підставляючи значення х1 і х2 в лінійну функцію, отримуємо Zmax = 2 * 0 +4 * 42.5 = 170 у.о.
Таким чином, для того щоб отримати максимальний прибуток у розмірі 170 у.о., необхідно запланувати виробництво 42,5 од. продукції В.
Рішення завдання симплексним методом
Запишемо систему у векторній формі
х1 * А1 + х2 * А2 + х3 * А3 + х4 * А4 + х5 * А5 = Ао, де
Складаємо симплексних таблицю.
i | Базис | Сбаз | Ао | С1 = 2 | С2 = 4 | С3 = 0 | С4 = 0 | С5 = 0 | С.О. |
А1 | А2 | А3 | А4 | А5 | |||||
1 | А3 | 0 | 425 | 11 | 10 | 1 | 0 | 0 | 42,5 |
2 | А4 | 0 | 450 | 7 | 5 | 0 | 1 |
0 | 90 | ||||||||
3 | А5 | 0 | 550 | 8 | 6 | 0 | 0 | 1 | 91,66667 |
m +1 | Zj-Cj | 0 | -2 | -4 | 0 | 0 | 0 |
Серед отриманих оцінок є дві негативні: Z 1 - C 1 =- 2 <0 і Z 2 - C 2 =- 4 <0. Це означає, що початковий опорний план не є оптимальним і його можна поліпшити, включивши в базис вектор, якому відповідає максимальне по модулю негативне число в m +1 рядку. Дозволяє вектор-стовпець А2. Дозволяє елемент знаходимо за мінімальним симплексному відношенню. Дозволяє елемент - число 10.
Склав другу симплексних таблицю.
i | Базис | Сбаз | Ао | С1 = 2 | С2 = 4 | С3 = 0 | С4 = 0 | С5 = 0 |
А1 | А2 | А3 | А4 | А5 | ||||
1 | А2 | 4 | 42,5 | 1,1 | 1 | 0,1 | 0 | 0 |
2 | А4 | 0 | 237,5 | 1,5 | 0 | -0,5 | 1 | 0 |
3 | А5 | 0 | 295 | 1,4 | 0 | -0,6 | 0 | 1 |
m +1 | Zj-Cj | 170 | 2,4 | 0 | 0,4 | 0 | 0 |
Переглянувши m +1 рядок, переконуємося, що опорний план - оптимальний.
Оптимальний план передбачає виготовлення 42,5 ед.ізделія В і не передбачає виготовлення виробів А. Виготовлення виробів А привело б до зменшення прибутку на 2,4 у.о. Сировина 1-го виду використовується повністю. Невикористаними залишається 450-237,5 = 212,5 тонн 2-го виду та 550-295 = 255 тонн 3-го виду сировини. Максимальний прибуток становить 170 у.о.
Рішення завдання на комп'ютері
Виконаємо такі дії:
- У клітинку А1 вводимо формулу для цільової функції = 2 * х1 +4 * х2
- У осередок А3 вводимо формулу для обмеження: = 11 * с1 +10 * с2.
- У клітинку А4 вводимо формулу для обмеження: = 7 * с1 +5 * с2.
- У осередок А3 вводимо формулу для обмеження: = 8 * с1 +6 * с2.
- У клітинку С1: С2 вводимо початкові значення змінних (0:0).
- Виконаємо команду Сервіс> Пошук рішення.
Отже, план випуску продукції, що включає виготовлення виробів 42,5 В є оптимальним. При цьому плані випуску виробів повністю використовується сировина 1-го виду і залишається невикористаним 450-237,5 = 212,5 тонн 2-го виду та 550-295 = 255 тонн 3-го виду сировини, а вартість виробленої продукції дорівнює 170 у. е.
ЛАБОРАТОРНА РОБОТА № 3
по мат.программірованію
«Транспортна задача»
Є 3 пункту поставки однорідного вантажу А1, А2, А3 та 5 пунктів В1, В2, В3, В4, В5 споживання цього вантажу. На пунктах А1-А3 знаходиться вантаж відповідно в кількості а1-а3 тонн. До пунктів В1-В5 потрібно доставити відповідно в1-В5 тонн вантажу. Вартості перевезень 1 тонни вантажу між пунктами постачання та пунктами споживання наведені в матриці D. Знайти такий план закріплення споживачів за постачальниками однорідного вантажу, щоб загальні витрати з перевезень були мінімальними.
Пункти поставки | Пункти споживання | Запаси | ||||
В1 | В2 | В3 | В4 | В5 | ||
А1 | 12 | 10 | 15 | 12 | 13 | 350 |
А2 | 16 | 14 | 17 | 10 | 8 | 150 |
А3 | 15 | 10 | 13 | 14 | 15 | 280 |
Потребн. | 100 | 120 | 200 | 160 | 200 |
Математична модель задачі
Математична модель транспортної задачі полягає в знаходженні такого неотрицательного рішення системи лінійних рівнянь
при яких цільова функція
F = 12 * x11 +10 * x12 +15 * x13 +12 * x14 +13 * x15 +16 * x21 +14 * x22 +17 * x23 +10 * x24 +8 * x25 +15 * x31 +10 * x32 + 13 * x33 +14 * x34 +15 * x35
приймає мінімальне значення.
Опорний план знайдемо методом північно-західного кута.
Пункти поставки | Пункти споживання | Запаси | ||||
В1 | В2 | В3 | В4 | В5 | ||
А1 | 350 | |||||
А2 | 150 | |||||
А3 | 280 | |||||
Потребн. | 100 | 120 | 200 | 160 | 200 |
Для перевірки плану на оптимальність необхідно побудувати систему потенціалів. Для побудови системи потенціалів використовуємо умова Ui + Vj = Cij
Пункти поставки | Пункти споживання | Запаси | |||||
В1 | В2 | В3 | В4 | В5 | |||
Потенціали | V1 = | V2 = | V3 = | V4 = | V5 = | ||
А1 | U1 = | 350 | |||||
А2 | U2 = | 150 | |||||
А3 | U3 = | 280 | |||||
Потребн. | 100 | 120 | 200 | 160 | 200 |
Пункти поставки | Пункти споживання | Запаси | |||||
В1 | В2 | В3 | В4 | В5 | |||
Потенціали | V1 = | V2 = | V3 = | V4 = | V5 = | ||
А1 | U1 = | 350 | |||||
А2 | U2 = | 150 | |||||
А3 | U3 = | 280 | |||||
Потребн. | 100 | 120 | 200 | 160 | 200 |
Пункти поставки | Пункти споживання | Запаси | |||||
В1 | В2 | В3 | В4 | В5 | |||
Потенціали | V1 = |