Математика / Контрольная работа: Розв`язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплек

Контрольная работа: Розв`язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплек

Вихідна задача: 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 -1 -1 0
А2 -3 -2 -1
А3 -6 -3 -3
потенц. 4 3 3 4

Оскільки всі отримані оцінки не більші нуля, то останній опорний план є оптимальним [5, с. 51]. Отримуємо оптимальний план перевезення:

Маршрут Кількість Вартість
??1 — В3 60 180
??1 — В­4 60 240
??2 — В­1 50 150
??2 — В­2 50 100
??3 — В­1 40 40
??3 — В­4 20 20
Всього 730

Відповідь:

Вартість оптимального плану транспортної задачі дорівнює 730.

Завдання 4. Методом множників Лагранжа знайти умовні екстремуми функцій

f = x1 2 + x1 x2 + x2 2 - 3x1 - 6x2 за умови x1 + x2 = 3.

Рішення.

Перепишемо умову у вигляді c(x1 , x2 ) = 0:

x1 + x2 - 3 = 0

Тоді функція Лагранжа [5, с. 153]:


К-во Просмотров: 238
Бесплатно скачать Контрольная работа: Розв`язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплек