Завдання1
Кондитерськафабрика для виробництва трьох видів карамелі А1, А2, А3використовує три види сировини: цукор-пісок, патоку і фруктове пюре. Нормивикористання сировини кожного виду на виробництво однієї тони карамелі подано втаблиці, відома також загальна кількість сировини кожного виду і прибуток відреалізації 1 тонни карамелі певного виду.Вид сировини Норми витрат сировини (т) на 1 т карамелі Об’єм сировини, т
А1
А2
А3 Цукор-пісок 0,8 0,5 0,6 1000 Патока 0,4 0,4 0,3 800 Фруктове пюре - 0,1 0,1 150 Прибуток від реалізації 1 т продукції (грн. од.) 21 23 25
Розв’язок
Складаємоматематичну модель задачі. Позначимо через х1 кількість карамелі1-го виду, що виготовляє підприємство за деяким планом, а через х2кількість карамелі 2-го виду та через х3 кількість карамелі 3-говиду. Тоді прибуток, отриманий підприємством від реалізації цих виробів,складає
∫= 21х1+23х2+25х3.
Витратисировини на виготовлення такої кількості виробів складають відповідно:
CI=0,8х1+0,5х2+0,6х3,
CIІ=0,4х1+0,4х2+0,3х3,
CIІІ=0х1+0,1х2+0,1х3.
Оскількизапаси сировини обмежені, то повинні виконуватись нерівності:
0,8х1+0,5х2+0,6х3≤1000
0,4х1+0,4х2+0,3х3≤800
0х1+0,1х2+0,1х3≤150.
Оскільки,кількість виробів є величина невід'ємна, то додатково повинні виконуватись щенерівності: х1> 0, х2> 0, х3>0.
Такимчином, приходимо до математичної моделі:
Знайтих1, х2, х3 такі, що функція ∫ = 21х1+23х2+25х3досягає максимуму при системі обмежень:
/>
Розв'язуємозадачу лінійного програмування симплексним методом.
Дляпобудови першого опорного плану систему нерівностей приведемо до системирівнянь шляхом введення додаткових змінних.
0,8x1+ 0,5x2 + 0,6x3 + 1x4 + 0x5 + 0x6= 1000
0,4x1+ 0,4x2 + 0,3x3 + 0x4 + 1x5 + 0x6= 800
0x1+ 0,1x2 + 0,1x3 + 0x4 + 0x5 + 1x6= 150
дех1,..., х6>0
Матрицякоефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
/>
Базиснізмінні це змінні, які входять лише в одне рівняння системи обмежень і притому зодиничним коефіцієнтом.
Вирішимосистему рівнянь відносно базисних змінних:
x4, x5, x6
Вважаючи,що вільні змінні рівні 0, отримаємо перший опорний план:
X1= (0,0,0,1000,800,150)
Оскількизавдання вирішується на максимум, то ведучий стовпець вибираємо помаксимальному негативному кількістю та індексного рядку. Всі перетворенняпроводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємосимплекс-таблицю:План Базис В
x1
x2
x3
x4
x5
x6 min 1
x4 1000 0.8 0.5 0.6 1 1666.67
x5 800 0.4 0.4 0.3 1 2666.67
x6 150 0.1
0.1 1
1500 Індексний рядок F(X1) -21 -23
-25
Оскільки,в індексному рядку знаходяться негативні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х3, оскільки значення коефіцієнта за модулем найбільше.План Базис В
x1
x2
x3
x4
x5
x6 min 2
x4 100
0.8 -0.1 1 -6
125
x5 350 0.4 0.1 1 -3 875
x3 1500 1 1 10 Індексний рядок F(X2) 37500
-21 2 250
Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х1.План Базис В
x1
x2
x3
x4
x5
x6 min 3
x1 125 1 -0.13 1.25 -7.5
x5 300 0.15 -0.5 1 2000
x3 1500
1 1 10
1500 Індексний рядок F(X3) 40125
-0.63 26.25 92.5
Оскільки,в індексному рядку знаходяться негативні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х2, оскільки значення коефіцієнта за модулем найбільше.План Базис В
x1
x2
x3
x4
x5
x6 min 4
x1 312.5 1 0.13 1.25 -6.25
x5 75 -0.15 -0.5 1 -1.5 2000
x2 1500 1 1 10 1500 Індексний рядок F(X4) 41062.5 0.63 26.25 98.75
Оскількивсі оцінки >0, то знайдено оптимальний план, що забезпечує максимальнийприбуток: х1=312.5, х2=1500. Прибуток, при випускупродукції за цим планом, становить 41062,5 грн.
Завдання2
Записати двоїстузадачу до поставленої задачі лінійного програмування. Розв’язати одну із задачсимплексним методом і визначити оптимальний план іншої задачі. Оптимальнірезультати перевірити графічно.
/>
/>
Розв’язок
Розв’яжемозадачу лінійного програмування симплексним методом.
Визначимомінімальне значення цільової функції F(X)=5x1+3x2 принаступних умовах-обмежень.
8x1-14x2≥14
3x1+2x2≥27
x2≤11
Для побудовипершого опорного плану систему нерівностей приведемо до системи рівнянь шляхомвведення додаткових змінних.
8x1-14x2-1x3+ 0x4 + 0x5 = 14
3x1+ 2x2 + 0x3-1x4 + 0x5 = 27
0x1+ 1x2 + 0x3 + 0x4 + 1x5 = 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)= 5x1+3x2+Mx6+Mx7 => min
Вважаючи, щовільні змінні рівні 0, отримаємо перший опорний план:
X1= (0,0,0,0,11,14,27)План Базис В
x1
x2
x3
x4
x5
х6
х7
х6 14 8 -14 -1 1
x7 27 3 2 -1 1
х5 11 1 1 Індексний рядок F(X0)
Переходимодо основного алгоритму симплекс-методу.План Базис В
x1
x2
x3
x4
x5
x6
х7 min 1
х6 14
8 -14 -1 1
1.75
x7 27 3 2 -1 1 9
х5 11 1 1 Індексний рядок F(X1)
Оскільки,в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х1, оскільки значення коефіцієнта за модулем найбільше.План Базис В
x1
x2
x3
x4
x5
x6
х7 min 2
х1 1.75 1 -1.75 -0.125 0.125
x7 21.75
7.25 0.375 -1 -0.375 1
3
х5 11 1 1 11 Індексний рядок F(X2)
Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х2.План Базис В
x1
x2
x3
x4
x5
x6
х7 3
х1 7 1 -0.0345 -0.2414 0.0345 0.2414
x2 3 1 0.0517 -0.1379 -0.0517 0.1379
х5 8 -0.0517 0.1379 1 0.0517 -0.1379 Індексний рядок F(X3)
Оптимальнийплан можна записати так:
x1 =7
x2 =3
x5 =8
F(X) = 5*7 + 3*3= 44
Складемо двоїстузадачу до поставленої задачі лінійного програмування.
8y1+3y2≤5
-14y1+2y2+y3≤3
14y1+27y2+11y3=> max
y1 ≥0
y2 ≥0
y3 ≤0
Рішення двоїстоїзадачі дає оптимальну систему оцінок ресурсів. Використовуючи останнюінтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теоремидвоїстості слідує, що Y = C*A-1.
Сформуємоматрицю A із компонентів векторів, які входять в оптимальний базис.
/>
Визначившиобернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
/>
Як видно ізостаннього плану симплексної таблиці, обернена матриця A-1 розміщенау стовбцях додаткових змінних.
Тоді Y = C*A-1= />
Запишемооптимальний план двоїстої задачі:
y1 =0.02
y2 =1.62
y3 =0
Z(Y) =14*0.02+27*1.62+11*0 = 44
Завдання3
Розв’язатитранспортну задачу.5 2 3 6 1 200 1 1 4 4 2 150 4 3 1 2 1 350 110 170 200 180 110
Розв’язок
Побудоваматематичної моделі. Нехай xij — кількістьпродукції, що перевозиться з і-го пункту виробництва до j-го споживача />. Оскільки />, то задачутреба закрити, тобто збалансувати (зрівняти) поставки й потреби:
/>
/>
/>У нашомувипадку робиться це введенням фіктивного постачальника, оскільки />. Зуведенням фіктивного постачальникав транспортній таблиці додатково заявляється n робочих клітинок.
Ціни додатковимклітинкам, щоб фіктивний рядок був нейтральним щодо оптимального виборупланових перевезень, призначаються усі рівні нулю.
Занесемовихідні дані у таблицю
В1
В2
В3
В4
В5 Запаси
А1 5 2 3 6 1 200
А2 1 1 4 4 2 150
А3 4 3 1 2 1 350
А4 70 Потреби 110 170 200 180 110
Забезпечившизакритість розв'язуваної задачі, розпочинаємо будувати математичну модель даноїзадачі:
/>
Економічний зміст записанихобмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можназаписати відносно замовників: вантаж, що може надходити до споживача відчотирьох баз, має повністю задовольняти його попит. Математично це записуєтьсятак:
/>
Загальнівитрати, пов’язані з транспортуванням продукції, визначаються як сума добутківобсягів перевезеної продукції на вартості транспортування од. продукції довідповідного замовника і за умовою задачі мають бути мінімальними. Томуформально це можна записати так:
minZ=5x11+2x12+3x13+6x14+1x15+1x21+1x22+4x23+4x24+2x25+4x31+3x32+1x33
+2x34++1x35+0x41+0x42+0x43+0x44+0x45.
Загалом математична модельсформульованої задачі має вигляд:
minZ=5x11+2x12+3x13+6x14+1x15+1x21+1x22+4x23+4x24+2x25+4x31+3x32+1x33
+2x34++1x35+0x41+0x42+0x43+0x44+0x45.
за умов:
/>/>
Запишемо умовизадачі у вигляді транспортної таблиці та складемо її перший опорний план у ційтаблиці методом «північно-західного кута».
Ai
Bj
ui
b1 = 110
b2 = 170
b3 = 200
b4=180
b5=110
а1 = 200
5
110
2
[-] 90 3 6
1
[+]
u1 = 0
а2 = 150 1
1
[+] 80
4
[-] 70 4 2
u2 = -1
а3 = 350 4 3
1
[+] 130
2
180
1
[-] 40
u3 = -4
а4 = 70
70
u4 = -5
vj
v1 = 5
v2 = 2
v3 = 5
v4 = 6
v5 = 5
В результатіотримано перший опорний план, який є допустимим, оскільки всі вантажі з базвивезені, потреба магазинів задоволена, а план відповідає системі обмеженьтранспортної задачі.
Підрахуємо числозайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є невиродженим.
Перевіримооптимальність опорного плану. Знайдемо потенціали ui,vi. по зайнятихклітинам таблиці, в яких ui+ vi = cij,вважаючи, що u1= 0:
u1=0,u2=-1, u3=-4, u4=-5, v1=5, v2=2,v3=5 v4=6, v5=5.
Ці значенняпотенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно залгоритмом методу потенціалів перевіряємо виконання другої умови оптимальностіui + vj ≤ cij (для порожніх клітиноктаблиці).
Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi> cij
(1;3): 0 + 5 > 3
(1;5): 0 + 5 > 1
(2;1): -1 + 5 > 1
(2;4): -1 + 6 > 4
(2;5): -1 + 5 > 2
(4;4): -5 + 6 > 0
Тому від ньогонеобхідно перейти до другого плану, змінивши співвідношення заповнених іпорожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А1B5):1. Для цього в перспективну клітку (1;5) поставимо знак «+», а в інших вершинахбагатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідноперемістити продукцію в межах побудованого циклу. З вантажів хij щостоять в мінусових клітинах, вибираємо найменше, тобто у = min (3;5) = 40.Додаємо 40 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 40 зхij, що стоять в мінусових клітинах. В результаті отримаємо новийопорний план.
Для цього упорожню клітинку А1B4 переносимо менше з чисел хij,які розміщені в клітинках зі знаком «–». Одночасно це саме число хijдодаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», тавіднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
Усі іншізаповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другутаблицю без змін. Кількість заповнених клітинок у новій таблиці також маєвідповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортноїзадачі матиме такий вигляд:
Ai
Bj
ui
b1 = 110
b2 = 170
b3 = 200
b4=180
b5=110
а1 = 200
5
110
2
[-] 50 3 6
1
[+] 40
u1 = 0
а2 = 150 1
1
[+] 120
4
[-] 30 4 2
u2 = -1
а3 = 350 4 3
1
[+] 170
2
[-] 180 1
u3 = -4
а4 = 70
[+]
[-] 70
u4 = -1
vj
v1 = 5
v2 = 2
v3 = 5
v4 = 6
v5 = 1
Перевіримо оптимальністьопорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинамтаблиці, в яких ui + vi = cij, вважаючи, що u1= 0.
Опорний план не єоптимальним, тому що існують оцінки вільних клітин для яких ui + vi> cij
(1;3): 0 + 5 > 3
(2;1): -1 + 5 > 1
(2;4): -1 + 6 > 4
(4;1): -1 + 5 > 0
(4;2): -1 + 2 > 0
(4;3): -1 + 5 > 0
(4;4): -1 + 6 > 0
Вибираємо максимальнуоцінку вільної клітини (А4B4): 0
Для цього в перспективнуклітку (А4B4) поставимо знак «+», а в інших вершинах багатокутникачергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А2B3)= 30. Додаємо 30 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо30 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новийопорний план.
Ai
Bj
ui
b1 = 110
b2 = 170
b3 = 200
b4=180
b5=110
а1 = 200
5
[-] 110
2
20 3 6
1
[+] 70
u1 = 0
а2 = 150 1
1
150 4 4 2
u2 = -1
а3 = 350 4 3
1
200
2
150 1
u3 = 1
а4 = 70
[+]
30
[-] 40
u4 = -1
vj
v1 = 5
v2 = 2
v3 = 0
v4 = 1
v5 = 1
Перевіримо оптимальністьопорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинамтаблиці, в яких ui + vi = cij, вважаючи, що u1= 0.
Опорний план не єоптимальним, тому що існують оцінки вільних клітин для яких ui + vi> cij
(2;1): -1 + 5 > 1
(3;1): 1 + 5 > 4
(3;5): 1 + 1 > 1
(4;1): -1 + 5 > 0
(4;2): -1 + 2 > 0
Вибираємо максимальнуоцінку вільної клітини (А4B1): 0
Для цього в перспективнуклітку (А4B1) поставимо знак «+», а в інших вершинах багатокутникачергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А4B5)=40. Додаємо 40 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо40 з Хij, що стоять в мінусових клітинах.
В результаті отримаємоновий опорний план.
Ai
Bj
ui
b1 = 110
b2 = 170
b3 = 200
b4=180
b5=110
а1 = 200
5
[-] 70
2
[+] 20 3 6
1
110
u1 = 0
а2 = 150
1
[+]
1
[-] 150 4 4 2
u2 = -1
а3 = 350 4 3
1
200
2
150 1
u3 = -3
а4 = 70
40
30
110
u4 = -5
vj
v1 = 5
v2 = 2
v3 = 4
v4 = 5
v5 = 1
Перевіримо оптимальністьопорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинамтаблиці, в яких ui + vi = cij, вважаючи, що u1= 0.
Опорний план не єоптимальним, тому що існують оцінки вільних клітин для яких ui + vi> cij
(1;3): 0 + 4 > 3
(2;1): -1 + 5 > 1
Вибираємо максимальнуоцінку вільної клітини (А2B1): 1
Для цього в перспективнуклітку (А2B1) поставимо знак «+», а в інших вершинах багатокутникачергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А1B1)=70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо70 з Хij, що стоять в мінусових клітинах.
В результаті отримаємоновий опорний план.
Ai
Bj
ui
b1 = 110
b2 = 170
b3 = 200
b4=180
b5=110
а1 = 200 5
2
90 3 6
1
110
u1 = 0
а2 = 150
1
70
1
80 4 4 2
u2 = -1
а3 = 350 4 3
1
200
2
150 1
u3 = 0
а4 = 70
40
30
110
u4 = -2
vj
v1 = 2
v2 = 2
v3 = 1
v4 = 2
v5 = 1
Перевіримо оптимальністьопорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціалиui, vi. по зайнятих клітинам таблиці, в яких ui+ vi = cij, вважаючи, що u1 = 0.
Перевірка останньогоплану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Розрахуємо значенняцільової функції відповідно до другого опорного плану задачі:
F(x)= 2*90 + 1*110 + 1*70 + 1*80 + 1*200 + 2*150 + 0*40 + 0*30 = 940
За оптимальним планомперевезень загальна вартість перевезень всієї продукції є найменшою і становить940 грн.
симплекснийприбуток транспортування витрати
Завдання4
Знайти графічнимметодом екстремуми функцій в області, визначеній нерівностями.
/>
/>
/>
/>
/>.
Розв’язок
Побудуємо областьдопустимих рішень, тобто вирішимо графічно систему нерівностей. Для цього побудуємокожну пряму і визначимо півплощини, задані нерівностями (півплощини позначені штрихом).
/>
Межі області
/>
Цільова функція F(x)=> min
Розглянемо цільовуфункцію завдання F = 3X1+6X2 => min.
Побудуємо пряму,що відповідає значенню функції F = 0: F = 3X1+6X2 = 0. Будемо рухати цю пряму паралельнимчином. Оскільки нас цікавить мінімальне рішення, тому рухався прямо до першого торканняпозначеної області. На графіку ця пряма позначена пунктирною лінією.
/>
Рівний масштаб
/>
Перетином півплощинибуде область, яка представляє собою багатокутник, координати точок якого задовольняютьумові нерівностей системи обмежень задачі.
Пряма F(x) = constперетинає область у точці C. Оскільки точка C отримана в результаті перетину прямих4 i 2, то її координати задовольняють рівнянням цих прямих:
x2=0
x1+2x2≥2
Вирішивши системурівнянь, одержимо: x1 = 2, x2 = 0
Звідки знайдемо мінімальнезначення цільової функції:
F(X) = 3*2 + 6*0= 6
Оскільки функціямети F(x) паралельна прямій 2, то на відрізку CA функція F (x) буде приймає однеі теж мінімальне значення.
Для визначення координатточки A вирішимо систему двох лінійних рівнянь:
x1+2x2≥2
x1=0
Вирішивши системурівнянь, одержимо: x1 = 0, x2 = 1
Звідки знайдемо мінімальнезначення цільової функції:
F(X) = 3*0 + 6*1= 6
/>