Завдання 1
Побудувати математичну модель задачі.
Меблева фабрика виготовляє столи, стільці, тумби і книжкові шафи використовуючи дошки двох видів, причому фабрика має 500 м2дошок першого виду і 1000 м2дошок другого виду. Задані також трудові ресурси в кількості 800 людино-годин. У таблиці наведені нормативи витрат кожного виду ресурсів на виготовлення одного виду і прибуток від реалізації одиниці виробу.
РесурсиВитрати на один вирібЗапас сировини, м2СтолиСтільціТумбиКнижкові шафиДошки І виду, м251912500Дошки ІІ виду, м223411000Трудові ресурси, люд.год.32510800Прибуток від реалізації одного виробу, грн.од.1251510
Визначити асортимент, що максимізує прибуток.
Розвязок
Складаємо математичну модель задачі. Позначимо через х1кількість виробів 1-ї моделі, що виготовляє фірма за деяким планом, а через х2 кількість виробів 2-ї моделі та через та через х3і х4кількість виробів 3-ї і 4-ї моделі відповідно. Тоді прибуток, отриманий фабрикою від реалізації цих виробів, складає
∫ = 12х1+5х2 + 15х3+ 10х4.
Витрати сировини на виготовлення такої кількості виробів складають відповідно
А =5х1+1х2 + 9х3+ 12х4,
В =2х1+3х2 + 4х3+ 1х4,
С =3х1+2х2 + 5х3+ 10х4,
Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:
5х1+1х2 + 9х3+ 12х4≤ 500
2х1+3х2 + 4х3+ 1х4≤ 1000
3х1+2х2 + 5х3+ 10х4≤ 800
Оскільки, кількість виробів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х1> 0, х2> 0, х3> 0, х4> 0.
Таким чином, приходимо до математичної моделі (задачі лінійного програмування):
Знайти х1 , х2, х3 та х4 такі, що функція ∫ = 12х1+5х2 + 15х3+ 10х4 досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом. Введемо балансні змінні х5 ≥ 0, х6≥ 0, х7≥ 0. Їх величина поки що невідома, але така, що перетворює відповідну нерівність у точну рівність. Після цього, задача лінійного програмування набуде вигляду: ∫ = 12х1+5х2 + 15х3+ 10х4 → max при обмеженнях
де х1,...,х7>0
Оскільки завдання вирішується на максимум, то ведучий стовпець вибирають по максимальному негативному кількістю та індексного рядку. Всі перетворення проводять до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Переходимо до основного алгоритму симплекс-методу.
ПланБазисВx1x2x3x4x5x6x7min1x55005191210055.56x610002341010250x780032510001160Індексний рядокF(X1)0-12-5-15-100000
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х3, оскільки значення коефіцієнта за модулем найбільше.
ПланБазисВx1x2x3x4x5x6x7min2x355.560.560.1111.330.1100100x6777.78-0.222.560-4.33-0.44100x7522.220.221.4403.33-0.56012350Індексний рядокF(X2)833.33-3.67-3.330101.67000
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х1.
ПланБазисВx1x2x3x4x5x6x7min3x110010.21.82.40.200500x680002.60.4-3.8-0.410307.69x750001.4-0.42.8-0.601357.14Індексний рядокF(X3)12000-2.66.618.82.4000
Даний план, знову не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
ПланБазисВx1x2x3x4x5x6x7min4x138.46101.772.690.23-0.080500x2307.69010.15-1.46-0.150.380307.69x769.2300-0.624.85-0.38-0.541357.14Індексний рядокF(X4)2000007152100
Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=38.46, х2=307.69, х3=0, х4=0, х5=0, х6=0, х7=69.23. Прибуток, при випуску продукції за цим планом, становить 2000 грн.
Завдання 2
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розвязати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розвязок
Пряма задача лінійного програмування має вигляд:
При обмеженнях:
Оскільки, у прямій задачі лінійного програмування необхідно знайти мінімум функції, то приведемо першопочаткову умову до вигляду:
Для досягнення відповідного вигляду помножимо 3-ю нерівність на -1
0х1-11х2≥-11
В результаті отримаємо наступні матриці:
Для складання двоїстої задачі лінійного програмування знайдемо матриці А, В, СТ.
Відповідно, двоїста задача лінійного програмування матиме вигляд:
F(Y)= 14Y1+27Y2-11Y3 (max)
Обмеження:
8Y1+3Y2+0Y3≤5
-14Y1+2Y2-11Y3≤3
Y1≥0
Y2≥0
Y3≥0
Розвяжемо задачу лінійного програмування симплексним методом.
Визначимо мінімальне значення цільової функції F(X) = 5x1+3x2 при наступних умовах-обмежень.
8x1-14x2≥14
3x1+2x2≥27
x2≤11
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.
8x1-14x2-1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 14
3x1 + 2x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 = 27
0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 11
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = 5 x1 +3 x2 +M x6 +M x7 => min
Переходимо до основного алгоритму симплекс-методу.
ПланБазисВx1x2x3x4x5x6x7
min
1x6148-14-100101.75x727320-10019x51101001000Індексний рядокF(X1)41000001099995-1200003-100000-1000000000
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
математичний модель симплексний лінійний
ПланБазисВx1x2x3x4x5x6x7min2x11.751-1.75-0.13000.1300x721.7507.250.38-10-0.3813x511010010011Індексний рядокF(X2)2175008.750724988.2537499.38-1000000-137499.3800
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
ПланБазисВx1x2x3x4x5x6x7min3x1710-0.03-0.2400.030.240x23010.05-0.140-0.050.143x5800-0.050.1410.05-0.1411Індексний рядокF(X3)4400-0.02-1.620-99999.98-99998.380
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
Оптимальний план можна записати так:
x1 = 7
x2 = 3
x5 = 8
F(X) = 5*7 + 3*3 = 44
Визначаємо оптимальний план двоїстої задачі до поставленої задачі лінійного програмування.
F(Y)= 14Y1+27Y2-11Y3 (max)
Обмеження:
8Y1+3Y2+0Y3≤5
-14Y1+2Y2-11Y3≤3
Y1≥0
Y2≥0
Y3≥0
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
8x1 + 3x2 + 0x3 + 1x4 + 0x5 = 5
-14x1 + 2x2-11x3 + 0x4 + 1x5 = 3
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план
ПланБазисВx1x2x3x4x50x4583010x53-142-1101Індексний рядокF(X0)083-900
Перейдемо до основного алгоритму симплекс-метода.
ПланБазисВx1x2x3x4x5min1x45830101.67x53-142-11011.5Індексний рядокF(X1)0-14-2711000
ПланБазисВx1x2x3x4x5min2X40.529016.51-1.50.0172X21.5-71-5.500.50Индексная строкаF(X2)40.5-2030-137.5013.50
ПланБазисВx1x2x3x4x53x10.0172100.5690.0345-0.0517x21.6201-1.520.24140.1379Индексная строкаF(X3)4400-2273
ПланБазисВx1x2x3x4x54x30.03031.76010.0606-0.0909x21.672.67100.33330Индексная строкаF(X4)44.6738.67008.331
Оптимальний план можливо записати так:
x3 = 0.0303
x2 = 1.67
F(X) = 27*1.67 + -11*0.03 = 44.67
Завдання 3
Розвязати транспортну задачц.
141563001311225041223200100120907080
Розвязок
Побудова математичної моделі. Нехай xij кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача . Оскільки , то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби
У нашому випадку робиться це введенням фіктивного постачальника, оскільки . З уведенням фіктивного споживача в транспортній таблиці додатково заявляється n робочих клітинок (додатковий стовпчик).
Виникає проблема, які ціни присвоїти цим клітинкам, щоб фіктивний стовпчик був нейтральним щодо оптимального вибору планових перевезень. Нейтральність забезпечується тим, що всі ціни у фіктивних клітинках вибираються однаковими, а оскільки ці ціни при поставках не повинні впливати на значення цільової функції f, то їх беруть усі рівними нулю.
Занесемо вихідні дані у таблицю.
В1В2В3В4В5В6ЗапасиА1141560300А2131120250А3412230200Потреби100120907080290
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
&
