Завдання1
Для виготовленнявиробів №1 і №2 є 100 кг металу. На виготовлення виробу №1 витрачається 2 кгметалу, а на виріб №2 – 4 кг.
Скласти планвиробництва, що забезпечує одержання найбільшого прибутку від продажу виробів,якщо відпускна вартість одного виробу №1 становить 3 грн. од., а виробу №2 – 2грн. од., причому виробів №1 потрібно виготовити не більше 40 штук, а виробів№2 – 20 шт.Сировина Вироби Кількість сировини В1 В2 Метал 2 4 100 Вартість, грн. кг 3 2
Розв’язок
Складаємоматематичну модель задачі. Позначимо через х1 кількість виробу №1, щовиготовляє підприємство за деяким планом, а через х2 кількість виробу №2/>. Тоді прибуток, отриманий підприємством від реалізації цихвиробів, складає
?= 3х1+2х2.
Витратисировини на виготовлення такої кількості виробів складають відповідно:
CI=2х1+4х2,
Оскількизапаси сировини обмежені, то повинні виконуватись нерівності:
2х1+4х2?100
Окрім того,виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 – 20 шт., тобто повиннівиконуватись ще нерівності: х1?40,х2?20.
Такимчином, приходимо до математичної моделі:
Знайтих1, х2такі, що функція ? = 3х1+2х2досягає максимуму при системі обмежень:
/>
Розв'язуємозадачу лінійного програмування симплексним методом.
Дляпобудови першого опорного плану систему нерівностей приведемо до системирівнянь шляхом введення додаткових змінних.
2x1+ 4x2+ 1x3+ 0x4+ 0x5= 100
1x1+ 0x2+ 0x3+ 1x4+ 0x5= 40
0x1+ 1x2+ 0x3+ 0x4+ 1x5= 20
Матрицякоефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
/>
Базиснізмінні це змінні, які входять лише в одне рівняння системи обмежень і притому зодиничним коефіцієнтом.
Вирішимосистему рівнянь відносно базисних змінних:
x3,x4, x5
Вважаючи,що вільні змінні рівні 0, отримаємо перший опорний план:
X1= (0,0,100,40,20)
Оскількизавдання вирішується на максимум, то ведучий стовпець вибираємо помаксимальному негативному кількістю та індексного рядку. Всі перетворенняпроводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємосимплекс-таблицю:План Базис В x1 x2 x3 x4 x5 min 1 x3 100 2 4 1 50 x4 40
1 1
40 x5 20 1 1 Індексний рядок F(X1)
-3 -2
Оскільки,в індексному рядку знаходяться негативні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х1, оскільки значення коефіцієнта за модулем найбільше.План Базис В x1 x2 x3 x4 x5 min 2 x3 20
4 1 -2
5 x1 40 1 1 x5 20 1 1 20 Індексний рядок F(X2) 120
-2 3
Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х2.План Базис В x1 x2 x3 x4 x5 min 3 x2 5 1 0,25 -0,5 5 x1 40 1 1 x5 15 -0,25 0,5 1 20 Індексний рядок F(X3) 130 0,5 2
Оскількивсі оцінки >0, то знайдено оптимальний план, що забезпечуємаксимальний прибуток: х1=40, х2=5. Прибуток, при випуску продукції за цимпланом, становить 130 грн.
Завдання2
Записати двоїстузадачу до поставленої задачі лінійного програмування. Розв’язати одну із задачсимплексним методом і визначити оптимальний план іншої задачі.
/>
/>
Розв’язок
Розв’яжемозадачу лінійного програмування симплексним методом.
Визначимомінімальне значення цільової функції F(X) = x1+3x2принаступних умовах-обмежень.
9x1+10x2?45
5x1-x2?42
-x1+13x2?4
Для побудовипершого опорного плану систему нерівностей приведемо до системи рівнянь шляхомвведення додаткових змінних.
9x1+ 10x2-1x3+ 0x4+ 0x5= 45
5x1-1x2+ 0x3+ 1x4+ 0x5= 42
-1x1+ 13x2+ 0x3+ 0x4+ 1x5= 4
Введемоштучні змінні x.
9x1+ 10x2-1x3+ 0x4+ 0x5+ 1x6= 45
5x1-1x2+ 0x3+ 1x4+ 0x5+ 0x6= 42
-1x1+ 13x2 + 0x3 + 0x4 + 1x5 + 0x6 = 4
Дляпостановки задачі на мінімум цільову функцію запишемо так:
F(X)= x1+3x2+Mx6=>min
Вважаючи, щовільні змінні рівні 0, отримаємо перший опорний план:
X1= (0,0,0,42,4,45).План Базис В x1 x2 x3 x4 x5 х6 х6 45 9 10 -1 1 x4 42 5 -1 1 х5 4 -1 13 1 Індексний рядок F(X0)
Переходимодо основного алгоритму симплекс-методу.План Базис В x1 x2 x3 x4 x5 x6 min 1 х6 45 9 10 -1 1 5,5 x4 42 5 -1 1 х5 4 -1
13 1 0,3077 Індексний рядок F(X1)
Оскільки,в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х2, оскільки значення коефіцієнта за модулем найбільше.План Базис В x1 x2 x3 x4 x5 x6 min 2 х6 41,92
9,77 -1 -0,7692 1
4,29 x4 42,31 4,92 1 0,0769 8,59 х2 0,3077 -0,0769 1 0,0769 Індексний рядок F(X2)
Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х1.План Базис В x1 x2 x3 x4 x5 x6 min 3 х1 4,29 1 -0,1024 -0,0787 0,1024 x4 21,18 0,5039 1 0,4646 -0,5039 45,59 х2 0,6378 1 -0,0079
0,0709 0,0079
9 Індексний рядок F(X3)
Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х5.План Базис В x1 x2 x3 x4 x5 x6 4 х1 5 1 1,11 -0,1111 0,1111 x4 17 -6,56 0,5556 1 -0,5556 х5 9 14,11 -0,1111 1 0,1111 Індексний рядок F(X4)
Оптимальнийплан можна записати так:
x1 = 5
x4 = 17
x5 = 9
F(X) = 1*5 = 5
Складемо двоїстузадачу до поставленої задачі лінійного програмування.
9y1+5y2-y3?1
10y1-y2+13y3?3
45y1+42y2+4y3=> max
y1? 0
y2? 0
y3? 0
Рішення двоїстоїзадачі дає оптимальну систему оцінок ресурсів. Використовуючи останнюінтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теоремидвоїстості слідує, що Y = C*A-1.
Сформуємоматрицю A із компонентів векторів, які входять в оптимальний базис.
/>
Визначившиобернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
/>
Як видно ізостаннього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцяхдодаткових змінних.
Тоді Y = C*A-1 =/>
Запишемооптимальний план двоїстої задачі:
y1 = 0.11
y2 = 0
y3 = 0
Z(Y)= 45*0.11+42*0+4*0 = 5
Завдання3
Розв’язатитранспортну задачу.1 4 7 9 1 250 2 3 1 2 4 300 2 1 3 1 4 150 110 80 100 90 70
Розв’язок
Побудоваматематичної моделі. Нехай xij — кількістьпродукції, що перевозиться з і-го пункту виробництва до j-госпоживача />.Оскільки />,то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:
/>
/>
Унашому випадку робиться це введенням фіктивного постачальника, оскільки />. Зуведенням фіктивного споживача транспортній таблиці додатково заявляється nробочих клітинок.
Ціни, додатковимклітинкам, щоб фіктивний стовбець був нейтральним щодо оптимального виборупланових перевезень, призначаються усі рівні нулю.
Занесемовихідні дані у таблицю.
В1 В2 В3 В4 В5 В6 Запаси А1 1 4 7 9 1 250 А2 2 3 1 2 4 300 А3 2 1 3 1 4 150 Потреби 110 80 100 90 70 250
Забезпечившизакритість розв'язуваної задачі, розпочинаємо будувати математичну модель даноїзадачі:
/>
Економічний зміст записанихобмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можназаписати відносно замовників: вантаж, що може надходити до споживача відчотирьох баз, має повністю задовольняти його попит. Математично це записуєтьсятак:
/>
Загальнівитрати, пов’язані з транспортуванням продукції, визначаються як сума добутківобсягів перевезеної продукції на вартості транспортування од. продукції довідповідного замовника і за умовою задачі мають бути мінімальними. Томуформально це можна записати так:
minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34++4x35+0x36.
Загалом математична модельсформульованої задачі має вигляд:
minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34++4x35+0x36.
за умов:
/>
/>
Запишемо умовизадачі у вигляді транспортної таблиці та складемо її перший опорний план у ційтаблиці методом «північно-західного кута».
Ai
Bj
ui
b1 = 110
b2 = 80
b3 = 100
b4=90
b5=70
b6=250
а1 = 250
1
110
4
80
7
[-]60 9
1
[+]
u1 = 0
а2 = 300 2 3
1
[+]40
2
90
4
[-]70
100
u2 = -6
а3 = 150 2 1 3 1 4
150
u3 = -6
vj
v1 =1
v2 =4
v3 =7
v4 =8
v5 =10
v6 =6
В результатіотримано перший опорний план, який є допустимим, оскільки всі вантажі з базвивезені, потреба магазинів задоволена, а план відповідає системі обмеженьтранспортної задачі.
Підрахуємо числозайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є невиродженим.
Перевіримооптимальність опорного плану. Знайдемо потенціали ui,vi. по зайнятих клітинамтаблиці, в яких ui+ vi = cij,вважаючи, що u1 = 0:
u1=0,u2=-6, u3=-6, v1=1, v2=4, v3=7 v4=8,v5=10, v6=6. Ці значення потенціалів першого опорного планузаписуємо у транспортну таблицю.
Потім згідно залгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ? cij(дляпорожніх клітинок таблиці).
Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(1;5): 0 + 10 > 1
(1;6): 0 + 6 > 0
(3;4): -6 + 8 > 1
Тому від ньогонеобхідно перейти до другого плану, змінивши співвідношення заповнених іпорожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А1B5):1. Для цього в перспективну клітку (1;5) поставимо знак «+», а в інших вершинахбагатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідноперемістити продукцію в межах побудованого циклу. З вантажів хij що стоять вмінусових клітинах, вибираємо найменше, тобто у = min (1;3) = 60. Додаємо 60 дообсягів вантажів, що стоять в плюсових клітинах і віднімаємо 60 з хij, щостоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Для цього упорожню клітинку А1B5 переносимо менше з чисел хij, якірозміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємодо відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо відчисел, що розміщені в клітинках, позначених знаком «–».
Усі іншізаповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другутаблицю без змін. Кількість заповнених клітинок у новій таблиці також маєвідповідати умові невиродженості плану, тобто дорівнювати (n + m– 1).
Отже, другий опорний плантранспортної задачі матиме такий вигляд:
Ai
Bj
ui
b1 = 110
b2 = 80
b3 = 100
b4=90
b5=70
b6=250
а1 = 250
1
110
4
[-]80 7 9
1
[+]60
u1 = 0
а2 = 300 2 3
1
100
2
90
4
[-]10
[+]100
u2 = 3
а3 = 150 2
1
[+] 3 1 4
[-]150
u3 = 3
vj
v1 =1
v2 =4
v3 =-2
v4 =-1
v5 =1
v6 =-3
Перевіримооптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинамтаблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(2;1): 3 + 1 > 2
(2;2): 3 + 4 > 3
(3;1): 3 + 1 > 2
(3;2): 3 + 4 > 1
(3;4): 3 + -1 > 1
Вибираємомаксимальну оцінку вільної клітини (А3B2): 1
Для цього вперспективну клітку (А3B2) поставимо знак «+», а в інших вершинахбагатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А2B5)= 10. Додаємо 10 до обсягів вантажів, що стоять в плюсових клітинах івіднімаємо 10 з Хij, що стоять в мінусових клітинах. В результаті отримаємоновий опорний план.
Ai
Bj
ui
b1 = 110
b2 = 80
b3 = 100
b4=90
b5=70
b6=250
а1 = 250
1
110
4
[-]70 7 9
1
70
[+]
u1 = 0
а2 = 300 2 3
1
100
2
90 4
110
u2 = -3
а3 = 150 2
1
[+]10 3 1 4
[-]140
u3 = -3
vj
v1 =1
v2 =4
v3 =4
v4 =5
v5 =1
v6 =3
Перевіримооптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинамтаблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(1;6): 0 + 3 > 0
(3;4): -3 + 5 > 1
Вибираємомаксимальну оцінку вільної клітини (А1B6): 0
Для цього вперспективну клітку (А1B6) поставимо знак «+», а в інших вершинахбагатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А1B2)=70.Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 зХij, що стоять в мінусових клітинах.
В результатіотримаємо новий опорний план.
Ai
Bj
ui
b1 = 110
b2 = 80
b3 = 100
b4=90
b5=70
b6=250
а1 = 250
1
110 4 7 9
1
70
70
u1 = 0
а2 = 300 2 3
1
100
2
[-]90 4
[+]110
u2 = 0
а3 = 150 2
1
80 3
1
[+] 4
[-]70
u3 = 0
vj
v1 =1
v2 =1
v3 =1
v4 =2
v5 =1
v6 =0
Перевіримооптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинамтаблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(3;4): 0 + 2 > 1
Вибираємомаксимальну оцінку вільної клітини (А3B4): 1
Для цього в перспективнуклітку (А3B4) поставимо знак «+», а в інших вершинахбагатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А3B6)=70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо70 з Хij, що стоять в мінусових клітинах.
В результатіотримаємо новий опорний план.
Ai
Bj
ui
b1 = 110
b2 = 80
b3 = 100
b4=90
b5=70
b6=250
а1 = 250
1
110 4 7 9
1
70
70
u1 = 0
а2 = 300 2 3
1
100
2
20 4
180
u2 = 0
а3 = 150 2
1
80 3
1
70 4
u3 = -1
vj
v1 =1
v2 =2
v3 =1
v4 =2
v5 =1
v6 =0
Перевіримооптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемопотенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij,вважаючи, що u1 = 0.
математичниймодель симплекс екстремум
Перевіркаостаннього плану на оптимальність за допомогою методу потенціалів показує, щовін оптимальний.
Розрахуємозначення цільової функції відповідно до другого опорного плану задачі:
F(x)= 1*110 + 1*70 + 0*70 + 1*100 + 2*20 + 0*180 + 1*80 + 1*70 = 470
За оптимальнимпланом перевезень загальна вартість перевезень всієї продукції є найменшою істановить 470 грн.
Завдання4
Знайти графічнимметодом екстремуми функцій в області, визначеній нерівностями.
/>
/>
/>
/>
/>.
Розв’язок
Необхідно знайтимінімальне значення цільової функції F = 2X1+4X2 =>min, при системіобмежень:
x1+2x2?2(1)
2x1+2x2?10(2)
x1+x2=6 (3)
Побудуємообласть допустимих рішень, тобто вирішимо графічно систему нерівностей. Дляцього побудуємо кожну пряму і визначимо півплощини, задані нерівностями(півплощини позначені штрихом).
/>
Межі області
/>
Цільова функціяF(x) =>min
Розглянемоцільову функцію завдання F = 2X1+4X2 =>min.
Побудуємо пряму,що відповідає значенню функції F = 0: F = 2X1+4X2 = 0. Будемо рухати цю прямупаралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухався прямодо першого торкання позначеної області. На графіку ця пряма позначенапунктирною лінією.
/>
Рівний масштаб
/>
Областьдопустимих значень необмежена.