чають дефіцитність ресурсів. p align="justify"> Обгрунтування ефективності оптимального плану
При підстановці оптимальних двоїстих оцінок в систему обмежень двоїстої задачі отримаємо:
-е обмеження двоїстої задачі виконується як рівність. Це означає, що 1-ий ресурс економічно вигідно використовувати, а його використання передбачено оптимальним планом прямої задачі (x1> 0)
* 0 + 1 * 5.33 + 4 * 0.67 = 8 = 8
-е обмеження двоїстої задачі виконується як рівність. Це означає, що 2-ий ресурс економічно вигідно використовувати, а його використання передбачено оптимальним планом прямої задачі (x2> 0)
* 0 + 1 * 5.33 + 1 * 0.67 = 6 = 6
Задача 12
Знайти такий варіант прикріплення постачальників до споживачів, при якому сума витрат на перевезення була б мінімальною.
В
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів
123Запасы114518025223003638120Потребности110350140
Перевіримо необхідна і достатня умова розв'язання задачі.
? a = 180 + 300 + 120 = 600
? b = 110 + 350 + 140 = 600
Занесемо вихідні дані у розподільну таблицю.
123Запасы114518025223003638120Потребности110350140
Етап I. Пошук першого опорного плану. p align="justify">. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі. br/>
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
. Підрахуємо число зайнятих клітин таблиці, їх 5, а має бути m + n - 1 = 5. Отже, опорний план є невироджених. p align="justify"> Значення цільової функції для цього опорного плану одно:
(x) = 1 * 110 + 5 * 70 + 2 * 300 + 3 * 50 + 8 * 70 = 1770
Етап II. Поліпшення опорного плану. p align="justify"> Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
v1 = 1v2 = 0v3 = 5u1 = 01 [110] 45 [70] u2 = 252 [300] 2u3 = 363 [50] 8 [70]
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi> cij
Вибираємо максимальну оцінку вільної клітини (2, 3): 2
Для цього в перспективну клітку (2, 3) поставимо знак В«+В», а в інших вершинах багатокутника чергуються знаки В«-В», В«+В», В«-В».
Цикл...
