найдено оптимальне рішення, яке мінімізує функціонал. Якщо ці числа непозитивні, досягнутий максимум функціоналу. За наявності чисел різних знаків включаємо в план вільну клітину, в якій коштує найбільше за модулем від'ємне число для мінімуму і позитивне - для максимуму.
5. У негативній полуцепі того циклу, який відповідає обраній клітці, відшукуємо найменшу перевезення та робимо зрушення по циклу на це число. Знаходимо новий допустимий план. p> 6. Відчуваємо цей план на оптимальність, тобто для кожної вільної клітини будуємо цикл перерахунку і обчислюємо алгебраїчну суму тарифів. При неоптимальности плану знову включаємо вільну клітину в план і робимо зрушення за відповідним циклом. Так продовжуємо до тих пір, поки план не буде оптимальним.
Для ручного рахунку більш зручний метод потенціалів. Однак на розподільному методі засновані деякі інші способи вирішення завдань, що і викликає необхідність його вивчення. [5]
9. Метод потенціалів
Рішення транспортної задачі будь-яким способом проводиться на макеті. Макет для застосування методу потенціалів має наступний вид.
В
Основна частина макета виділена подвійними лініями. Вона містить k Г— l клітин. Кожна клітина в цій частині позначається символом ( i , j ). Наприклад, клітина, що стоїть в другому рядку і першому стовпці, буде позначена (2, 1). Макет містить в собі матрицю тарифів. Призначення рядка v j і шпальти u i буде з'ясовано надалі.
Перш ніж приступити до викладу методу, розглянемо деякі попередні поняття.
Довільну сукупність клітин в макеті називають набором. Ланцюгом називається послідовний набір клітин, в якому кожні дві сусідні клітини розташовані в одному ряду (рядку, стовпці), причому ніякі три клітини в одному ряду не розташовуються.
Приклад ланцюга наведено в табл.2.
В
Прямі, що з'єднують взяті клітини, перетнулися, але так як клітку в перетині ми не беремо, правило ланцюга не порушується.
Якщо остання клітина ланцюга розташована в одному ряду з першої, то така замкнута ланцюг називається циклом. Деякі різновиди циклів показані в табл.3. br/>В
Теорема. Нехай в макеті (або матриці) з k рядків і l стовпців довільно відзначено k + l клітин, причому k + l ВЈ kl . У цьому випадку завжди можна побудувати цикл, вершини якого лежать у зазначених клітинах (може бути не в усіх).
Зауваження. Числа k і l цілі, і для них не завжди буде виконано нерівність k + l ВЈ kl . Якщо одне з цих чисел - одиниця, це нерівність не виконується. Наприклад, при k = 3, l = 1 маємо 3 + 1> 3.1. Однак при k = 2 і l = 2 буде 2 +2 = 2.2, а при k і l , одночасно великих двох, нерівність завжди виконується....
