Визначення оптимального плану транспортної задачі - студопедія
Найбільш поширеним є метод потенціалів.
Теорема. Якщо для деякого опорного плану X * = [x * ij] транспортної задачі існують числа і такі, що при xij> 0 і при xij = 0 для всіх і, то Х * - оптимальний план.
Числа і називаються потенціалами, відповідно, пунктів відправлення і пунктів призначення.
Ця теорема дозволяє побудувати алгоритм вирішення транспортної задачі:
1. Знаходять опорний план транспортної задачі одним з розглянутих вище методів.
2. Обчислюють потенціали пунктів відправлення і пунктів призначення, використовуючи співвідношення:
де Cij - тарифи, які стоять в заповнених клітинах таблиці умов транспортної задачі.
В результаті отримують систему лінійних рівнянь, що складаються з (m + n-1) рівнянь з (m + n) - невідомими, тобто система буде невизначеною.
Для її вирішення однієї з змінних надають довільне значення і послідовно знаходять інші невідомі (наприклад, вважають # 945; 1 = 0)
3. Для всіх вільних клітин знаходять числа # 945; ij з умови:
Якщо серед чисел # 945; ij немає позитивних, тобто все # 945; ij ≤0, то знайдений опорний план є оптимальним.
Якщо для деякої вільної клітини # 945; ij> 0, то план можна поліпшити.
4. Побудова поліпшеного плану:
З усіх чисел # 945; ij> 0вибірают максимальне і клітку, яка відповідає цьому числу, необхідно заповнити. Це можна зробити за допомогою циклічного контуру (циклу)
Якщо ламана, що утворює цикл, перетинається, то точка самопересеченія вершиною не є (рис. Б)
Якщо опорний план побудований правильно, то для будь-якої вільної клітини можна побудувати тільки один циклічний контур.
Для переходу до нового опорного плану, після побудови циклічного контуру, необхідно здійснити переміщення вантажів в межах клітин, пов'язаних циклічним контуром, тобто здійснити зрушення по циклу перерахунку
Його ведуть за такими правилами:
1. Кожній клітці, що входить в циклічний контур, привласнюють певний знак, причому, вільній клітці знак «+», а іншим по черзі «-», «+».
2. У вільну клітину переносять менше з чисел хij. що стоять в «-» клітинах. Це ж число додають до чисел, що стоять в «плюсових» клітинах і вичитують з чисел, що стоять «мінусових» клітках. В результаті обрана вільна клітина стане зайнятої, а «мінусова» клітина, в якій стояло мінімальне з чисел хij, - вільною.
При зсуві по циклу перерахунку, число зайнятих клітин має залишитися незмінним, рівним (m + n-1).
Якщо в «мінусових» клітках є два або більше однакових числа хij. то звільняють одну клітку, а хтось вважає умовно зайнятими з нульовими перевезеннями.
При побудові опорного плану або в процесі виконання завдання може бути отриманий вироджений план. Щоб уникнути в цьому випадку зациклення. необхідно привести план до невироджені, для чого вільні клітини (бажано з мінімальними тарифами перевезень) заповнюють як завгодно малими перевезеннями, тобто в цих клітинах ставлять, наприклад, число Е = 0,001 і вважають клітини умовно зайнятими. При визначенні вартості перевезень і в оптимальному плані приймають Е = 0.
3. Покращений план знову перевіряють на оптимальність, тобто переходять до пункту 2.