Завдання 1
Цех випускає валиі втулки. На виробництво одного вала робочий витрачає 3 год., однієї втулки – 2год. Від реалізації одного вала підприємство одержує прибуток 80 грн., а відреалізації однієї втулки – 60 грн. Цех має випустити не менше 100 валів і неменше 200 втулок. Скільки валів і скільки втулок має випустити цех, щободержати найбільший прибуток, якщо фонд робочого часу робітників становить 900людино-годин?Ресурс Вироби Фонд робочого часу Вали Втулки Робітник, год. од. 3 2 900 Вартість, грн. од. 80 60
Розв’язок
Складаємоматематичну модель задачі. Позначимо через х1 кількість валів, що виготовляєпідприємство за деяким планом, а через х2 кількість втулок. Тоді прибуток,отриманий підприємством від реалізації цих виробів, складає
∫= 80х1+60х2.
Витратиресурсів на виготовлення такої кількості виробів складають відповідно:
CI=3х1+2х2,
Оскількизапаси ресурсів обмежені, то повинні виконуватись нерівності:
3х1+2х2≤900
Окрім того, валівпотрібно виготовити не менше 100 штук, а втулок – 200 шт., тобто повинні виконуватисьще нерівності: х1≥ 100,х2≥200.
Такимчином, приходимо до математичної моделі:
Знайтих1, х2 такі, що функція ∫ = 80х1+60х2 досягає максимуму при системіобмежень:
/>
Розв’язуємозадачу лінійного програмування симплексним методом.
Дляпобудови першого опорного плану систему нерівностей приведемо до системирівнянь шляхом введення додаткових змінних. Оскільки маємо змішаніумови-обмеження, то введемо штучні змінні x.
3×1+ 2×2 + 1×3 + 0x4 + 0x5 + 0x6 + 0x7 = 900
1×1+ 0x2 + 0x3-1×4 + 0x5 + 1×6 + 0x7 = 100
0x1+ 1×2 + 0x3 + 0x4-1×5 + 0x6 + 1×7 = 200
Дляпостановки задачі на максимум цільову функцію запишемо так:
F(X)= 80 x1 +60 x2 — M x6 — M x7 => max
Отриманийбазис називається штучним, а метод рішення називається методом штучного базису.
Причомуштучні змінні не мають стосунку до змісту поставленого завдання, проте вонидозволяють побудувати початкову точку, а процес оптимізації змушує ці змінніприймати нульові значення і забезпечити допустимість оптимального рішення.
Зметою формулювання задачі для вирішення її в табличній формі скористаємосявиразами з системи рівнянь для штучних змінних:
x6= 100-x1 +x4
x7= 200-x2 +x5
якіпідставимо в цільову функцію:
F(X)= 80×1 + 60×2 — M(100-x1 +x4 ) — M(200-x2 +x5 ) => max
або
F(X)= (80+1M)x1 +(60+1M)x2 +(-1M)x4 +(-1M)x5 +(-300M) => max
Матрицякоефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:3 2 1 1 -1 1 1 -1 1
Базиснізмінні це змінні, які входять лише в одне рівняння системи обмежень і притому зодиничним коефіцієнтом.
Вирішимосистему рівнянь відносно базисних змінних:
x3, x6, x7
Вважаючи,що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,900,0,0,100,200)
Оскількизавдання вирішується на максимум, то ведучий стовпець вибираємо помаксимальному негативному кількістю та індексного рядку. Всі перетворенняпроводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємосимплекс-таблицю:План Базис В x1 x2 x3 x4 x5 x6 x7 min 1 x3 900 3 2 1 300 x6 100 1 -1 1 100 x7 200 1 -1 1 Індексний рядок F(X1) -30000000 -100080 -100060 100000
Оскільки,в індексному рядку знаходяться негативні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х1, оскільки значення коефіцієнта за модулем найбільше.План Базис В x1 x2 x3 x4 x5 x6 x7 min 2 x3 600 2 2 3 -3 300 x1 100 1 -1 1 x7 200 1 1 1 200 Індексний рядок F(X2) -19992000 -100060 -80 100080
Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х2.План Базис В x1 x2 x3 x4 x5 x6 x7 min 3 x3 200 1 3 2 -3 -2 66,67 x1 100 1 -1 1 x2 200 1 -1 1 Індексний рядок F(X3) 20000 -80 -60 100080 100060
Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х4.План Базис В x1 x2 x3 x4 x5 x6 x7 min 4 x4 66,67 0,33 1 0,67 -1 -0,67 100 x1 166,67 1 0,33 0,67 -0,67 250 x2 200 1 -1 1 Індексний рядок F(X4) 25333,33 26,67 -6,67 100000 100006,67
Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х5.План Базис В x1 x2 x3 x4 x5 x6 x7 min 5 x5 100 0,5 1,5 1 -1,5 -1 100 x1 100 1 -1 1 250 x2 300 1 0,5 1,5 -1,5 Індексний рядок F(X5) 26000 30 10 99990 100000
Оскількивсі оцінки >0, то знайдено оптимальний план, що забезпечує максимальнийприбуток: х1=100, х2=300. Прибуток, при випуску продукції за цим планом, становить26000 грн.
/>
Завдання 2
Записати двоїстузадачу до поставленої задачі лінійного програмування. Розв’язати одну із задачсимплексним методом і визначити оптимальний план іншої задачі. Оптимальнірезультати перевірити графічно.
/>
/>
Розв’язок
Розв’яжемозадачу лінійного програмування симплексним методом.
Визначимомінімальне значення цільової функції F(X) = 3×1+x2 принаступних умовах-обмежень.
x1+2×2≤6
-5×1+4×2≤2
7×1+5×2≥35
Для побудовипершого опорного плану систему нерівностей приведемо до системи рівнянь шляхомвведення додаткових змінних.
1×1+ 2×2+ 1×3+ 0x4+ 0x5= 6
-5×1+ 4×2+ 0x3+ 1×4+ 0x5= 2
7×1+ 5×2+ 0x3+ 0x4-1×5= 35
Введемоштучні змінні x.
1×1+ 2×2+ 1×3+ 0x4+ 0x5+ 0x6= 6
-5×1+ 4×2+ 0x3+ 1×4+ 0x5+ 0x6= 2
7×1+ 5×2+ 0x3+ 0x4-1×5+ 1×6= 35
Дляпостановки задачі на мінімум цільову функцію запишемо так:
F(X)= 3×1+x2- Mx6=> max
Вважаючи, щовільні змінні рівні 0, отримаємо перший опорний план:
X1= (0,0,6,2,0,35)План Базис В x1 x2 x3 x4 x5 х6 х3 6 1 2 1 x4 2 -5 4 1 х6 35 7 5 -1 1 Індексний рядок F(X0)
Переходимодо основного алгоритму симплекс-методу.План Базис В x1 x2 x3 x4 x5 x6 min 1 х3 6 1 2 1 6 x4 2 -5 4 1 х6 35 7 5 -1 1 5 Індексний рядок F(X1)
Оскільки,в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х1, оскільки значення коефіцієнта за модулем найбільше.План Базис В x1 x2 x3 x4 x5 x6 min 2 х3 1 1,29 1 0,1429 -0,1429 7 x4 27 7,57 1 -0,7143 0,7143 х1 5 1 0,7143 -0,1429 0,1429 Індексний рядок F(X2)
Оскільки,в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х5, оскільки значення коефіцієнта за модулем найбільше.План Базис В x1 x2 x3 x4 x5 x6 3 х5 7 9 7 1 -1 x4 32 14 5 1 х1 6 1 2 1 Індексний рядок F(X3)
Оптимальнийплан можна записати так:
x5 = 7
x4 = 32
x1 = 6
F(X) = 3*6 = 18
Складемо двоїстузадачу до поставленої задачі лінійного програмування.
y1+5y2+7y3≥3
2y1-4y2+5y3≥1
6y1-2y2+35y3=> min
y1≥ 0
y2≤ 0
y3≤ 0
двоїстийсимплексний задача лінійний програмування
Рішення двоїстоїзадачі дає оптимальну систему оцінок ресурсів. Використовуючи останнюінтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теоремидвоїстості слідує, що Y = C*A-1. Сформуємо матрицю A із компонентів векторів,які входять в оптимальний базис.
/>
Визначившиобернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
/>
Як видно ізостаннього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцяхдодаткових змінних.
Тоді Y = C*A-1 =/>
Запишемооптимальний план двоїстої задачі:
y1= 3
y2= 0
y3= 0
Z(Y)= 6*3+-2*0+35*0 = 18
Завдання 3
Розв’язатитранспортну задачу.2 4 5 8 6 180 7 3 6 4 5 300 8 5 6 5 3 230 110 140 220 190 120
Розв’язок
Побудоваматематичної моделі. Нехай xij — кількість продукції, що перевозиться з і-гопункту виробництва до j-го споживача />. Оскільки />, то задачу требазакрити, тобто збалансувати (зрівняти) поставки й потреби:
/>
/>
/>У нашомувипадку робиться це введенням фіктивного постачальника, оскільки
/>
Зуведенням фіктивного постачальникав транспортній таблиці додатково заявляється n робочих клітинок.
Ціни, додатковимклітинкам, щоб фіктивний рядок був нейтральним щодо оптимального виборупланових перевезень, призначаються усі рівні нулю.
Занесемовихідні дані у таблицю. В1 В2 В3 В4 В5 Запаси А1 2 4 5 8 6 180 А2 7 3 6 4 5 300 А3 8 5 6 5 3 230 А4 70 Потреби 110 140 220 190 120
Забезпечившизакритість розв’язуваної задачі, розпочинаємо будувати математичну модель даноїзадачі:
/>
Економічний зміст записанихобмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можназаписати відносно замовників: вантаж, що може надходити до споживача відчотирьох баз, має повністю задовольняти його попит. Математично це записуєтьсятак:
/>
Загальнівитрати, пов’язані з транспортуванням продукції, визначаються як сума добутківобсягів перевезеної продукції на вартості транспортування од. продукції довідповідного замовника і за умовою задачі мають бути мінімальними. Томуформально це можна записати так:
minZ=2×11+4×12+5×13+86×14+6×15+7×21+3×22+6×23+4×24+5×25+8×31+5×32+6×33+5×34++3×35+0x41+0x42+0x43+0x44+0x45.
Загалом математична модельсформульованої задачі має вигляд:
minZ=2×11+4×12+5×13+86×14+6×15+7×21+3×22+6×23+4×24+5×25+8×31+5×32+6×33+5×34++3×35+0x41+0x42+0x43+0x44+0x45.
за умов:
/>
/>
Запишемо умовизадачі у вигляді транспортної таблиці та складемо її перший опорний план у ційтаблиці методом «північно-західного кута».Ai Bj ui b1 = 110 b2 = 140 b3 = 220 b4=190 b5=120 а1 = 180
2
110
4
70 5 8 6 u1 = 0 а2 = 300 7
3
70
6
[-] 220
4
[+] 10 5 u2 = -1 а3 = 230 8 5 6
5
[-] 180
3
[+] 50 u3 = 0 а4 = 70
[+]
[-] 70 u4 = -3 vj v1 = 2 v2 = 4 v3 = 7 v4 = 5 v5 = 3
В результатіотримано перший опорний план, який є допустимим, оскільки всі вантажі з базвивезені, потреба магазинів задоволена, а план відповідає системі обмеженьтранспортної задачі.
Підрахуємо числозайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є невиродженим.
Перевіримооптимальність опорного плану. Знайдемо потенціали ui,vi. по зайнятих клітинамтаблиці, в яких ui+ vi = cij,вважаючи, що u1 = 0
u1=0, u2=-1, u3=0,u4=-3, v1=2, v2=4, v3=7 v4=5, v5=3
Ці значенняпотенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно залгоритмом методу потенціалів перевіряємо виконання другої умови оптимальностіui + vj ≤ cij (для порожніх клітинок таблиці).
Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(1;3): 0 + 7 > 5
(3;3): 0 + 7 > 6
(4;2): -3 + 4 > 0
(4;3): -3 + 7 > 0
(4;4): -3 + 5 > 0
Тому від ньогонеобхідно перейти до другого плану, змінивши співвідношення заповнених іпорожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А4B3):0. Для цього в перспективну клітку (4;3) поставимо знак «+», а в інших вершинахбагатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідноперемістити продукцію в межах побудованого циклу.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (4;5) = 70.
Додаємо 70 дообсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з хij, щостоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Для цього упорожню клітинку А4B3 переносимо менше з чисел хij, які розміщені в клітинкахзі знаком «–».
Одночасно цесаме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком«+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
Усі іншізаповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другутаблицю без змін.
Кількістьзаповнених клітинок у новій таблиці також має відповідати умові невиродженостіплану, тобто дорівнювати (n + m – 1).
Отже, другий опорний плантранспортної задачі матиме такий виглядAi Bj ui b1 = 110 b2 = 140 b3 = 220 b4=190 b5=120 а1 = 180
2
110
4
[-] 70
5
[+] 8 6 u1 = 0 а2 = 300 7
3
[+] 70
6
[-] 150
4
80 5 u2 = -1 а3 = 230 8 5 6
5
110
3
120 u3 = 0 а4 = 70
70 u4 = -7 vj v1 = 2 v2 = 4 v3 = 7 v4 = 5 v5 = 3
Перевіримооптимальність опорного плану.Знайдемо потенціали ui, vi. по зайнятих клітинамтаблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(1;3): 0 + 7 > 5
(3;3): 0 + 7 > 6
Вибираємомаксимальну оцінку вільної клітини (А1B3): 5
Для цього вперспективну клітку (А1B3) поставимо знак «+», а в інших вершинах багатокутникачергуються знаки «-», «+», «-».
Цикл наведено втаблиці.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А1B2) = 70.
Додаємо 70 дообсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij, щостоять в мінусових клітинах.
В результатіотримаємо новий опорний план.Ai Bj ui b1 = 110 b2 = 140 b3 = 220 b4=190 b5=120 а1 = 180
2
110 4
5
70 8 6 u1 = 0 а2 = 300 7
3
140
6
[-] 80
4
[+] 80 5 u2 = 1 а3 = 230 8 5
6
[+]
5
[-] 110
3
120 u3 = 2 а4 = 70
70 u4 = -5 vj v1 = 2 v2 = 2 v3 = 5 v4 = 3 v5 = 1
Перевіримо оптимальністьопорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, вяких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(3;3): 2 + 5 > 6
Вибираємомаксимальну оцінку вільної клітини (А3B3): 6
Для цього вперспективну клітку (А3B3) поставимо знак «+», а в інших вершинах багатокутникачергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А2B3) =80.Додаємо 80 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 80 зХij, що стоять в мінусових клітинах.
В результатіотримаємо новий опорний план.Ai Bj ui b1 = 110 b2 = 140 b3 = 220 b4=190 b5=120 а1 = 180
2
110 4
5
70 8 6 u1 = 0 а2 = 300 7
3
140 6
4
160 5 u2 = 0 а3 = 230 8 5
6
80
5
30
3
120 u3 = 1 а4 = 70
70 u4 = -5 vj v1 = 2 v2 = 3 v3 = 5 v4 = 4 v5 = 2
Перевіримооптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемопотенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij,вважаючи, що u1 = 0.
Перевіркаостаннього плану на оптимальність за допомогою методу потенціалів показує, щовін оптимальний.
Розрахуємозначення цільової функції відповідно до другого опорного плану задачі
F(x)= 2*110 + 5*70 + 3*140 + 4*160 + 6*80 + 5*30 + 3*120 + 0*70 = 2620
За оптимальнимпланом перевезень загальна вартість перевезень всієї продукції є найменшою істановить 2620 грн.
Завдання 4
Знайти графічнимметодом екстремуми функцій в області, визначеній нерівностями.
/>
/>
/>
/>
/>.
Розв’язок
Побудуємообласть допустимих рішень, тобто вирішимо графічно систему нерівностей. Дляцього побудуємо кожну пряму і визначимо півплощини, задані нерівностями(півплощини позначені штрихом).
/>
Межі області
/>
Цільова функціяF(x) => min
Розглянемоцільову функцію завдання F = 9X1+8X2 => min.
Побудуємо пряму,що відповідає значенню функції F = 0: F = 9X1+8X2 = 0. Будемо рухати цю прямупаралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухався прямодо першого торкання позначеної області. На графіку ця пряма позначенапунктирною лінією.
/>
Рівний масштаб
/>
Перетиномпівплощини буде область, яка представляє собою багатокутник, координати точокякого задовольняють умові нерівностей системи обмежень задачі.
Пряма F(x) =const перетинає область у точці A. Оскільки точка A отримана в результатіперетину прямих 1 i 5, то її координати задовольняють рівнянням цих прямих:
x1+x2≥1
x1=0
Вирішившисистему рівнянь, одержимо
x1 = 0, x2 = 1
Звідки знайдемомінімальне значення цільової функції
F(X) = 9*0 + 8*1= 8