Математичне програмування
Размещено на /
Завдання 1
Побудувати математичну модель задачі.
Фірма, що спеціалізується на виробництві електроприладів, отримала замовлення на виготовлення 100 електроплит. Конструкторами запропоновано до випуску три моделі плит А, В і С за ціною відповідно 100, 60 та 50 грн.од. Норми витрат сировини для виготовлення однієї електроплити різних моделей та запас сировини на фірмі наведено в таблиці.
Сировина | Норми витрат сировини, грн.од. | Запас сировини, грн.од. | ||
А | В | С | ||
І | 10 | 4 | 5 | 700 |
ІІ | 3 | 2 | 1 | 400 |
Ціна, грн.од. | 100 | 60 | 50 |
Визначити оптимальні обсяги виробництва електроплит різних моделей, що максимізують дохід фірми.
Розв’язок
Складаємо математичну модель задачі. Позначимо через х1 кількість електроплит 1-ї моделі, що виготовляє фірма за деяким планом, а через х2 кількість електроплит 2-ї моделі та через та через х3 кількість виробів 3-ї моделі Тоді прибуток, отриманий фірмою від реалізації цих електроплит, складає
∫ = 100х1 + 60х2+ 50х3.
Витрати сировини на виготовлення такої кількості виробів складають відповідно:
А =10х1 + 4х2 + 5х3,
В =3х1 + 2х2 + 1х3,
Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:
10х1 + 4х2 + 5х3 ≤ 700
3х1 + 2х2 + 1х3 ≤ 400
Оскільки, кількість виробів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х1> 0, х2> 0, х3> 0.
Таким чином, приходимо до математичної моделі (задачі лінійного програмування):
Знайти х1 , х2, х3 такі, що функція∫ = 100х1 + 60х2 + 50х3 досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом. Введемо балансні змінні х4 ≥ 0, х5 ≥ 0. Їх величина поки що невідома, але така, що перетворює відповідну нерівність у точну рівність. Після цього, задача лінійного програмування набуде вигляду: ∫ = 100х1 + 60х2 + 50х3 → max при обмеженнях
де х1,...,х5>0
Оскільки завдання вирішується на максимум, то ведучий стовпець вибирають по максимальному негативному кількістю та індексного рядку. Всі перетворення проводять до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємо симплекс-таблицю:
Базис | x1 | х2 | x3 | x4 | x5 | b | |
I | II | III | IV | V | VI | VII | |
а | 0 | 10 | 4 | 5 | 1 | 0 | 700 |
б | 0 | 3 | 2 | 1 | 0 | 1 | 400 |
d | Індексний рядок, ∆i | 100 | 60 | 50 | 0 | 0 | 0 |
Складаємо перший план. Оскільки змінних х4,х5в цільовій функції немає, то їм відповідають коефіцієнти 0;
План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
1 | x4 | 700 | 10 | 4 | 5 | 1 | 0 | 70 |
x5 | 400 | 3 | 2 | 1 | 0 | 1 | 133.33 | |
Індексний рядок | F(X1) | 0 | -100 | -60 | -50 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
2 | x1 | 70 | 1 | 0.4 | 0.5 | 0.1 | 0 | 175 |
x5 | 190 | 0 | 0.8 | -0.5 | -0.3 | 1 | 237.5 | |
Індексний рядок | F(X2) | 7000 | 0 | -20 | 0 | 10 | 0 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
3 | x2 | 175 | 2.5 | 1 | 1.25 | 0.25 | 0 | 175 |
x5 | 50 | -2 | 0 | -1.5 | -0.5 | 1 | 237.5 | |
Індексний рядок | F(X3) | 10500 | 50 | 0 | 25 | 15 | 0 | 0 |
Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=0, х2=175, х3=0, х4=0, х5=50. Прибуток, при випуску продукції за цим планом, становить 10500 грн.
Дамо економічну трактову розв'язку: щоби досягнути максимально можливого, за умов задачі, прибутку (10500 грн.), необхідно виробів другої моделі випустити 175 од.
Завдання 2
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо максимальне значення цільової функції F(X) = x1+2x2 за таких умов-обмежень.
2x1+3x2≤6
2x1+4x2≤4
2x1+x2≥4
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
2x1 + 3x2 + 1x3 + 0x4 + 0x5 = 6
2x1 + 4x2 + 0x3 + 1x4 + 0x5 = 4
2x1 + 1x2 + 0x3 + 0x4-1x5 = 4
Введемо штучні змінні x.
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 6
2x1 + 4x2 + 0x3 + 1x4 + 0x5 + 0x6 = 4
2x1 + 1x2 + 0x3 + 0x4-1x5 + 1x6 = 4
Для постановки завдання на максимум цільову функцію запишемо так:
F(X) = x1+2x2 - Mx6 => max
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
З рівнянь висловлюємо штучні змінні:
x6 = 4-2x1-x2+x5
які підставимо в цільову функцію:
F(X) = x1 + 2x2 - M(4-2x1-x2+x5) => max
або
F(X) = (1+2M)x1+(2+1M)x2+(-1M)x5+(-4M) => max
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Вирішимо систему рівнянь відносно базисних змінних:
x3, x4, x6,
Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:
X1 = (0,0,6,4,0,4)
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
0 | x3 | 6 | 2 | 3 | 1 | 0 | 0 | 0 |
x4 | 4 | 2 | 4 | 0 | 1 | 0 | 0 | |
x6 | 4 | 2 | 1 | 0 | 0 | -1 | 1 | |
Індексний рядок | F(X0) | -4M | -1-2M | -2-1M | 0 | 0 | 1M | 0 |
Переходимо до основного алгоритму симплекс-методу.
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
1 | x3 | 6 | 2 | 3 | 1 | 0 | 0 | 0 | 3 |
x4 | 4 | 2 | 4 | 0 | 1 | 0 | 0 | 2 | |
x6 | 4 | 2 | 1 | 0 | 0 | -1 | 1 | 2 | |
Індексний рядок | F(X1) | -4M | -1-2M | -2-1M | 0 | 0 | 1M | 0 | 0 |
індексний рядок симплекс метод
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
2 | x3 | 2 | 0 | 2 | 1 | 0 | 1 | -1 | 1 |
x4 | 0 | 0 | 3 | 0 | 1 | 1 | -1 | 0 | |
x1 | 2 | 1 | 0.5 | 0 | 0 | -0.5 | 0.5 | 4 | |
Індексний рядок | F(X2) | 2 | 0 | -1.5 | 0 | 0 | -0.5 | 0.5+1M | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
3 | x3 | 2 | 0 | 0 | 1 | -0.6667 | 0.3333 | -0.3333 |
x2 | 0 | 0 | 1 | 0 | 0.3333 | 0.3333 | -0.3333 | |
x1 | 2 | 1 | 0 | 0 | -0.1667 | -0.6667 | 0.6667 | |
Індексний рядок | F(X3) | 2 | 0 | 0 | 0 | 0.5 | 0 | 1M |
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти.
Оптимальний план можна записати так:
x3 = 2
x2 = 0
x1 = 2
F(X) = 1*2 + 2*0 = 2
Складемо двоїсту задачу до прямої задачі.
2y1+2y2+2y3≥1
3y1+4y2+y3≥2
6y1+4y2+4y3 => min
y1 ≥ 0
y2 ≥ 0
y3 ≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.
Використовуючи останню ітерацію прямої задачі знайдемо, оптимальний план двоїстої задачі.
З першої теореми двоїстості випливає, що Y = C*A-1.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1 через алгебраїчні доповнення, отримаємо:
Як видно з останнього плану симплексного таблиці, зворотна матриця A-1 розташована в стовпцях додаткових змінних .
Тоді Y = C*A-1 =
Оптимальний план двоїстої задачі дорівнює:
y1 = 0
y2 = 0.5
y3 = 0
Z(Y) = 6*0+4*0.5+4*0 = 2
Завдання 3
Розв’язати транспортну задачу.
5 | 2 | 3 | 6 | 1 | 150 |
1 | 1 | 4 | 4 | 2 | 320 |
4 | 1 | 2 | 3 | 5 | 400 |
100 | 120 | 100 | 200 | 300 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача . Оскільки , то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:
У нашому випадку робиться це введенням фіктивного постачальника, оскільки . З уведенням фіктивного споживача транспортній таблиці додатково заявляється n робочих клітинок.
Ціни, додатковим клітинкам, щоб фіктивний стовбець був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
В1 | В2 | В3 | В4 | В5 | В6 | Запаси | |
А1 | 5 | 2 | 3 | 6 | 1 | 0 | 150 |
А2 | 1 | 1 | 4 | 4 | 2 | 0 | 320 |
А3 | 4 | 1 | 2 | 3 | 5 | 0 | 400 |
Потреби | 100 | 120 | 100 | 200 | 300 | 50 |
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ=5x11+2x12+3x13+6x14+1x15+0x16+1x21+1x22+4x23+4x24+2x25+0x26+4x31+1x32+2x33+3x34+ +5x35+0x36.
Загалом математична модель сформульованої задачі має вигляд:
minZ=5x11+2x12+3x13+6x14+1x15+0x16+1x21+1x22+4x23+4x24+2x25+0x26+4x31+1x32+2x33+3x34+ +5x35+0x36.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
Ai | Bj | ui | |||||
b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | b6=50 | ||
а1 = 150 |
5 100 |
2 [-] 50 |
3 | 6 |
1 [+] |
0 | u1 = 0 |
а2 = 320 | 1 |
1 [+] 70 |
4 100 |
4 [-] 150 |
2 | 0 | u2 = -1 |
а3 = 400 | 4 | 1 | 2 |
3 [+] 50 |
5 [-] 300 |
0 50 |
u3 = -2 |
vj | v1 = 5 | v2 = 2 | v3 = 5 | v4 = 5 | v5 = 7 | v6 = 2 |
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u1 + v2 = 2; 0 + v2 = 2; v2 = 2
u2 + v2 = 1; 2 + u2 = 1; u2 = -1
u2 + v3 = 4; -1 + v3 = 4; v3 = 5
u2 + v4 = 4; -1 + v4 = 4; v4 = 5
u3 + v4 = 3; 5 + u3 = 3; u3 = -2
u3 + v5 = 5; -2 + v5 = 5; v5 = 7
u3 + v6 = 0; -2 + v6 = 0; v6 = 2
Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(1;3): 0 + 5 > 3; ∆13 = 0 + 5 - 3 = 2
(1;5): 0 + 7 > 1; ∆15 = 0 + 7 - 1 = 6
(1;6): 0 + 2 > 0; ∆16 = 0 + 2 - 0 = 2
(2;1): -1 + 5 > 1; ∆21 = -1 + 5 - 1 = 3
(2;5): -1 + 7 > 2; ∆25 = -1 + 7 - 2 = 4
(2;6): -1 + 2 > 0; ∆26 = -1 + 2 - 0 = 1
(3;3): -2 + 5 > 2; ∆33 = -2 + 5 - 2 = 1
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (1;5): 1. Для цього в перспективну клітку (1;5) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 2) = 50. Додаємо 50 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 50 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Для цього у порожню клітинку (1;5) переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
Ai | Bj | ui | |||||
b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | b6=50 | ||
а1 = 150 |
5 [-] 100 |
2 |
3 | 6 |
1 [+] 50 |
0 | u1 = 0 |
а2 = 320 |
1 [+] |
1 120 |
4 100 |
4 [-] 100 |
2 | 0 | u2 = 5 |
а3 = 400 | 4 | 1 | 2 |
3 [+] 100 |
5 [-] 250 |
0 50 |
u3 = 4 |
vj | v1 = 5 | v2 = -4 | v3 = -1 | v4 = -1 | v5 = 1 | v6 = -4 |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(2;1): 5 + 5 > 1; ∆21 = 5 + 5 - 1 = 9
(2;5): 5 + 1 > 2; ∆25 = 5 + 1 - 2 = 4
(2;6): 5 + -4 > 0; ∆26 = 5 + -4 - 0 = 1
(3;1): 4 + 5 > 4; ∆31 = 4 + 5 - 4 = 5
(3;3): 4 + -1 > 2; ∆33 = 4 + -1 - 2 = 1
Вибираємо максимальну оцінку вільної клітини (2;1): 1
Для цього в перспективну клітку (2;1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 4) = 100. Додаємо 100 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 100 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Ai | Bj | ui | |||||
b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | b6=50 | ||
а1 = 150 |
5 [-] 0 |
2 |
3 | 6 |
1 [+] 150 |
0 | u1 = 0 |
а2 = 320 |
1 [+] 100 |
1 120 |
4 [-] 100 |
4 |
2 | 0 | u2 = -4 |
а3 = 400 | 4 | 1 |
2 [+] |
3 200 |
5 [-] 150 |
0 50 |
u3 = 4 |
vj | v1 = 5 | v2 = 5 | v3 = 8 | v4 = -1 | v5 = 1 | v6 = -4 |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(1;2): 0 + 5 > 2; ∆12 = 0 + 5 - 2 = 3
(1;3): 0 + 8 > 3; ∆13 = 0 + 8 - 3 = 5
(3;1): 4 + 5 > 4; ∆31 = 4 + 5 - 4 = 5
(3;2): 4 + 5 > 1; ∆32 = 4 + 5 - 1 = 8
(3;3): 4 + 8 > 2; ∆33 = 4 + 8 - 2 = 10
Вибираємо максимальну оцінку вільної клітини (3;3): 2
Для цього в перспективну клітку (3;3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 1) = 0. Додаємо 0 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 0 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
Ai | Bj | ui | |||||
b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | b6=50 | ||
а1 = 150 |
5 |
2 |
3 | 6 |
1 150 |
0 | u1 = 0 |
а2 = 320 |
1 100 |
1 120 |
4 [-] 100 |
4 |
2 [+] |
0 | u2 = 6 |
а3 = 400 | 4 | 1 |
2 [+] 0 |
3 200 |
5 [-] 150 |
0 50 |
u3 = 4 |
vj | v1 = -5 | v2 = -5 | v3 = -2 | v4 = -1 | v5 = 1 | v6 = -4 |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(2;4): 6 + -1 > 4; ∆24 = 6 + -1 - 4 = 1
(2;5): 6 + 1 > 2; ∆25 = 6 + 1 - 2 = 5
(2;6): 6 + -4 > 0; ∆26 = 6 + -4 - 0 = 2
Вибираємо максимальну оцінку вільної клітини (2;5): 2
Для цього в перспективну клітку (2;5) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 3) = 100. Додаємо 100 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 100 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
Ai | Bj | ui | |||||
b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | b6=50 | ||
а1 = 150 |
5 |
2 |
3 | 6 |
1 150 |
0 | u1 = 0 |
а2 = 320 |
1 100 |
1 [-] 120 |
4 |
4 |
2 [+] 100 |
0 | u2 = 1 |
а3 = 400 | 4 |
1 [+] |
2 100 |
3 200 |
5 [-] 50 |
0 50 |
u3 = 4 |
vj | v1 = 0 | v2 = 0 | v3 = -2 | v4 = -1 | v5 = 1 | v6 = -4 |
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij
(3;2): 4 + 0 > 1; ∆32 = 4 + 0 - 1 = 3
Вибираємо максимальну оцінку вільної клітини (3;2): 1
Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 5) = 50. Додаємо 50 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 50 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
Ai | Bj | ui | |||||
b1 = 100 | b2 = 120 | b3 = 100 | b4=200 | b5=300 | b6=50 | ||
а1 = 150 |
5 |
2 |
3 | 6 |
1 150 |
0 | u1 = 0 |
а2 = 320 |
1 100 |
1 70 |
4 |
4 |
2 150 |
0 | u2 = 1 |
а3 = 400 | 4 |
1 50 |
2 100 |
3 200 |
5 |
0 50 |
u3 = 4 |
vj | v1 = 0 | v2 = 0 | v3 = -2 | v4 = -1 | v5 = 1 | v6 = -4 |
Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Мінімальні витрати складуть:
F(x) = 1*150 + 1*100 + 1*70 + 2*150 + 1*50 + 2*100 + 3*200 + 0*50 = 1470
За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 1470 грн.
Завдання 4
Знайти графічним методом екстремуми функцій в області, визначеній нерівностями.
.
Розв’язок
Побудуємо область допустимих рішень, тобто вирішимо графічно систему нерівностей. Для цього побудуємо кожну пряму і визначимо півплощини, задані нерівностями (півплощини позначені штрихом).
Межі області
Цільова функція F(x) => max
Розглянемо цільову функцію завдання F = 4X1+5X2 => max.
Побудуємо пряму, що відповідає значенню функції F = 0: F = 4X1+5X2 = 0. Будемо рухати цю пряму паралельним чином. Оскільки нас цікавить максимальне рішення, тому рухався прямо до останнього торкання позначеної області. На графіку ця пряма позначена пунктирною лінією.
Рівний масштаб