апасами 45 одиниць направимо транзитом через 9 вершину, всього запасів стало 75 одиниць, направимо їх транзитом через 7 вершину в 4 вершину, потреби якої складають 40 одиниць, що залишилися 35 одиниць направимо в 2 вершину і задовольнимо її потреби. p> З 3 вершини з запасами 30 одиниць направимо транзитом через 7 вершину у 1 вершину, потреби якої задовольнимо.
В результаті проведених операцій всі запаси вивезені, потреби всіх споживачів задоволені. p> У результаті проведених операцій всі запаси вивезені, потреби всіх споживачів задоволені. Число базисних ребер тут дорівнює 11, число вершин 13. p> Отже, отриманий план є опорним, так як задовольняє всім вимогам опорного плану. Значення функції, яке відповідає побудованому планом одно
.
Перевірку плану на оптимальність здійснимо за допомогою методу потенціалів. p> Однією з вершин (наприклад, 1) задамо довільне значення потенціалу О± 1 = 0. Запишемо його біля вершини 1. p> Потім, рухаючись по базисним ребрах, обчислюємо потенціали інших вершин. p>;
;;
;;
;
;;
В
Після обчислення потенціалів знаходимо оцінки для небазисних ребер: (1,2), (2,4), (2,7), (3,7), (7,12), (7,8), (10,12), (4,6). Вони визначаються за формулою і рівні відповідно:
;;
;;.
В В
Є три позитивні оцінки, значить побудований опорний план не оптимальний. p> Найбільша оцінка. Ребро (7,8), оголошуємо дозволяючими, направляємо роздільну стрілку (Поки порожню) від вершини з меншим потенціалом до вершини з великим потенціалом, тобто від 7-й вершини до 8-й (на рис. 2 роздільна стрілка намічена пунктиром). У результаті отримуємо цикл перерахунку, замикається на ребрі (7,8). Цикл перерахунку на рис.2 намічений суцільною лінією.
В
Рис.3. перерахунок перевезень по потенциалам
У другому рядку виписуємо ребра, що належать циклу перерахунку. У першому рядку, над ребрами за допомогою стрілок вкажемо напрямок перевезень, а в третьому рядку - обсяг перевезеного вантажу. У четвертому рядку отриманої конструкції запишемо, якщо напрямок перевезення збігається з роздільною стрілкою і, в іншому випадку.
В
Змінюємо розподіл поставок. Визначаємо величину коригування плану. Оскільки перевезення х 8,10 , х 11,9 направлені проти роздільної стрілки, величина покладається меншою з них
Включаємо в базис ребро (7,8), а обсяг перевезення вважаємо рівним величині коригування Ребро (7,9) виключаємо з базису.
Після перерахунку отримаємо значення функції:
В
Задача № 5
Задача про призначення
Нижче наведені таблиці, в клітинах яких проставлені елементи матриці ефективностей задачі про розбірливою нареченій. Вирішити задачу методом потенціалів та угорським методом.
44
31
13
11
41
10
17
38
25
35
20
26
8
17
14
38
36
12
37
38
49
38
22
10
13
28
21
48
43
44
29
26
12
37
22
39
46
26
20
44
49
22
49
19
2
20
30
45
16
45
27
5
21
30
...
