Перевірка вирожденність опорного плану.
Відповідно до теореми 6.2 перевіряється вирожденність знайденого плану. Якщо опорний план вироджений, тобто
(Де N - число заповнених клітин в таблиці поставок) тоді вводиться k фіктивних поставок:
тобто в будь-яких k незаповнених клітинках таблиці поставок вписують нульові значення проектним параметрам xij:
де S - безліч пар індексів (i. j) вільних змінних, відповідних незаповненим клітинам.
Розрахунок потенціалів виконують по завантажених клітин таблиці поставок, для яких:
де # 945; i. # 946; j - потенціал i -ої рядки і j -ої колонки відповідно.
Для першого рядка приймають # 945; 1 = 0, потім інші потенціали розраховують по завантажених клітин відповідно до вираження (6.14).
Результати розрахунків заносять в таблицю поставок.
Перевірка опорного плану на оптимальність здійснюється по незавантажені клітинам. Якщо для всіх незавантажених клітин виконується умова:
то знайдений опорний план є оптимальним.
Оптимальне рішення буде єдиним, якщо для всіх незавантажених клітин виконується умова:
Якщо для будь-якої незавантаженої клітини умова (6.15) не виконується, то опорний план не є оптимальним і переходять до наступного етапу.
6. Пошук «вершини максимальної неоптимальности» (ВМН).
За незавантажені клітинам, для яких умова (6.15) не виконується, розраховують оцінки:
де - безліч пар індексів (i. j), відповідних незаповненим клітинам, для яких не виконується умова оптимальності (6.15). Дані оцінки характеризують розмір економії транспортних витрат на 1 од. вантажу, що перевозиться.
Серед отриманих оцінок знаходять найбільшу, тобто .:
яка відповідає ВМН. Клітку, відповідну ВМН, в таблиці поставок позначають «+».
Генерація сторінки за: 0.007 сек.