[ Розвязання задач графічним методом методом потенціалів методом множників Лангранжа та симплекс-методом ] | 5 | 0 | -3/2 | 0 | 0 | 1/2 |
|
Вводимо в базис x2 замість x4 і перераховуємо таблицю:
xб | b | x1 | x2 | x3 | x4 | x5 | bi/xi |
x3 | 10 | 0 | 0 | 1 | -1/11 | 7/11 | — |
x2 | 2 | 0 | 1 | 0 | 2/11 | -3/11 | — |
x1 | 6 | 1 | 0 | 0 | 1/11 | 4/11 | — |
Δ | 8 | 0 | 0 | 0 | 3/11 | 1/11 |
|
В останньому рядку не залишилося від'ємних величин, тому стовбець b містить рішення вихідної задачі — максимум функції F:
x1 = 6
x2 = 2
Fmax = 8
Запишемо рішення двоїстої задачі з останнього рядка останньої симплекс-таблиці:
y1 = 0
y2 = 3/11
y3 = 1/11
F*min = 8
Відповідь:
Вихідна задача: Fmax = F(6; 2) = 8
Двоїста задача: F*min = F*(0; 3/11; 1/11) = 8
Завдання 3. Розв'язати методом потенціалів транспортну задачу
ai \ bj | 90 | 50 | 60 | 80 |
120 | 5 | 4 | 3 | 4 |
100 | 3 | 2 | 5 | 5 |
60 | 1 | 6 | 3 | 1 |
Рішення.
Підраховуємо загальні запаси постачальників: 120 + 100 + 60 = 280
Підраховуємо загальні потреби споживачів: 90 + 50 + 60 + 80 = 280
Дана модель закрита [5, с. 55], тому що загальні потреби споживачів дорівнюють загальним запасам постачальників.
Запишемо умову задачі у вигляді наступної таблиці:
| В1 | В2 | В3 | В4 | Запаси |
А1 | 5 | 4 | 3 | 4 | 120 |
А2 | 3 | 2 | 5 | 5 | 100 |
А3 | 1 | 6 | 3 | 1 | 60 |
Потреби | 90 | 50 | 60 | 80 |
|
Для визначення опорного плану транспортної задачі застосуємо спочатку метод мінімального елемента [5, с. 50]. Для цього будемо послідовно вибирати клітинки з мінімальним тарифом і робити спробу максимально задовольнити вимоги споживачів і постачальників.
Перший мінімальний елемент (1) знаходяться в клітинці А3В1, тому записуємо в неї запас постачальника А3 (60) і коректуємо колонки запасів та потреб:
| В1 | В2 | В3 | В4 | Запаси |
А1 |
|
|
|
| 120 |
А2 |
|
|
|
| 100 |
А3 | 60 | — | — | — | 0 |
Потреби | 30 | 50 | 60 | 80 |
|
Наступні мінімальні елементи (2 та 3) знаходяться в клітинках А2В2, А1В3 та А2В1, тому записуємо в них потреби споживачів В2 (50), В3 (60) та В1 (30) і коректуємо колонки запасів та потреб:
| В1 | В2 | В3 | В4 | Запаси |
А1 | — | — | 60 |
| 60 |
А2 | 30 | 50 | — |
| 20 |
А3 | 60 | — | — | — | 0 |
Потреби | 0 | 0 | 0 | 80 |
|
Залишилися вільні клітинки А1В4 та А2В4, тому записуємо в них запаси постачальників А1 (60) та А2 (20) і коректуємо колонки запасів та потреб:
| В1 | В2 | В3 | В4 | Запаси |
А1 | — | — | 60 | 60 | 0 |
А2 | 30 | 50 | — | 20 | 0 |
А3 | 60 | — | — | — | 0 |
Потреби | 0 | 0 | 0 | 0 |
|
Підрахуємо вартість перевезення для отриманого опорного плану:
60*3 + 60*4 + 30*3 + 50*2 + 20*5 + 60*1 = 770
Для визначення оптимальності отриманого опорного плану застосуємо метод потенціалів [5, с. 51]. Для цього задамо нульовий потенціал першому рядку, а решту потенціалів визначимо враховуючи отримані клітинки:
| В1 | В2 | В3 | В4 | потенц. |
А1 |
|
| 3 | 4 | 0 |
А2 | 3 | 2 |
| 5 | 1 |
А3 | 1 |
|
|
| 1 |
потенц. | 2 | 1 | 3 | 4 |
|
Визначаємо оцінки для вільних клітинок, знаходимо максимальну додатну оцінку (4) в клітинці А3В4 і позначаємо для неї цикл [5, с. 51]:
| В1 | В2 | В3 | В4 | потенц. |
А1 | -3 | -3 |
|
| 0 |
А2 | (+) |
| -1 | (-) | 1 |
А3 | (-) | -4 | 1 | 4(+) | 1 |
потенц. | 2 | 1 | 3 | 4 |
|
В вершинах циклу зі знаком (-) вибираємо мінімальне значення (20) у клітинці А2В4 опорного плану. Додаємо його до вершин циклу зі знаком (+) і віднімаємо його від вершин циклу зі знаком (-):
| В1 | В2 | В3 | В4 | Запаси |
А1 |
|
| 60 | 60 | 0 |
А2 | 50 | 50 |
|
| 0 |
А3 | 40 |
|
| 20 | 0 |
Потреби | 0 | 0 | 0 | 0 |
|
При цьому вартість перевезення для цього поліпшеного опорного плану:
60*3 + 60*4 + 50*3 + 50*2 + 40*1 + 20*1 = 730
Для визначення оптимальності поліпшеного опорного плану знову застосуємо метод потенціалів — задамо нульовий потенціал першому рядку, а решту потенціалів визначимо враховуючи отримані клітинки:
| В1 | В2 | В3 | В4 | потенц. |
А1 |
|
| 3 | 4 | 0 |
А2 | 3 | 2 |
|
| -1 |
А3 | 1 |
|
| 1 | -3 |
потенц. | 4 | 3 | 3 | 4 |
|
Визначаємо оцінки для вільних клітинок:
| В1 | В2 | В3 | В4 | потенц. | |||||||||||||||||||||||||||||||||||||||||||
А1
Оскільки всі отримані оцінки не більші нуля, то останній опорний план є оптимальним [5, с. 51]. Отримуємо оптимальний план перевезення:
Відповідь: Вартість оптимального плану транспортної задачі дорівнює 730. Завдання 4. Методом множників Лагранжа знайти умовні екстремуми функцій f = x12 + x1x2 + x22 - 3x1 - 6x2 за умови x1 + x2 = 3. Рішення. Перепишемо умову у вигляді c(x1, x2) = 0: x1 + x2 - 3 = 0 Тоді функція Лагранжа [5, с. 153]: L(x1, x2, λ) = f(x1, x2) + λ c(x1, x2) L(x1, x2, λ) = x12 + x1x2 + x22 - 3x1 - 6x2 + λ(x1 + x2 - 3) У точці екстремуму частинні похідні функції Лагранжа дорівнюють нулю [5, с. 154]: ∂L(x1, x2, λ) / ∂x1 = 2x1 + x2 - 3 + λ ∂L(x1, x2, λ) / ∂x2 = x1 + 2x2 - 6 + λ
Отримуємо наступну систему: 2x1 + x2 - 3 + λ = 0 x1 + 2x2 - 6 + λ = 0 x1 + x2 - 3 = 0 Віднімаємо друге рівняння системи від першого і визначаємо x2: x1 - x2 + 3 = 0 x2 = x1 + 3 Підставляємо отримане x2 в третє рівняння системи: x1 = 0 x2 = x1 + 3 = 3 Отже точка (0; 3) — умовний екстремум функції f, який дорівнює: f(0; 3) = 32 - 6*3 = -9 Розглянемо іншу довільну точку (3; 0), для якої виконується умова задачі. Значення функції для цієї точки: f(3; 0) = 32 - 3*3 = 0 Оскільки f(0; 3) < f(3; 0), то знайдений умовний екстремум — це умовний мінімум. Відповідь: Умовний мінімум функції f досягається в точці (0; 3) і дорівнює -9. Список використаної літератури 1. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навчально-методичний посібник для самостійного вивчення дисципліни. — К.: КНЕУ, 2001. — 248 с. 2. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы: Учебное пособие для студентов. — М.: Просвещение, 1991. — 176 с. 3. Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С. Математичне програмування (методичний посібник для студентів економічних спеціальностей). — Чернівці: Рута, 1998. — 168 с. 4. Наконечний С.І., Савіна С.С. Математичне програмування: Навчальний посібник. — К.: КНЕУ, 2003. — 452 с. 5. Попов Ю.Д., Тюптя В.І., Шевченко В.І. Методи оптимізації. — К.: КНУ, 2003. — 215 с. Будь ласка, не зберігайте тестовий текст. |