Метод потенціалів для знаходження оптимального розв’язку транспортної задачі

Метод потенціалів є особливим випадком симплекс-методу, що враховує особливості транспортної задачі. Метод потенціалів ґрунтується на наступній теоремі.

Теорема про потенціали.

Якщо для деякого опорного плану , транспортної задачі існують такі числа що при , при для всіх , то — оптимальний план транспортної задачі.

Величини та називаються потенціалами пунктів постачання та пунктів споживання відповідно.

Алгоритм методу потенціалів включає наступні кроки.

1. Розраховуємо значення потенціалів рядків та стовпців та , розв’язуючи систему рівнянь , що складені для заповнених клітинок транспортної задачі. Число заповнених клітинок дорівнює , а система має невідомих, тому для визначеності приймаємо та послідовно з рівнянь знаходимо інші значення та .

2. Для кожної з вільних клітинок розраховуємо значення . Якщо , то план оптимальний. В іншому випадку обираємо максимальне значення та заповнюємо відповідну клітинку, змінюючи об’єми поставок в інших заповнених клітинках, що пов’язані з нею циклом.

а). Побудова циклу.

Цикл будується у вигляді ламаної лінії в таблиці транспортної задачі, вершини якого розташовані в заповнених клітинках таблиці, а ланки ламаної — вздовж рядків та стовпчиків, причому в кожній вершині циклу зустрічається рівно дві ланки — одна з них проходить вздовж стовпчика, а інша — вздовж рядка. Точки самоперетину ламаної не є вершинами. Однією з вершин циклу є обрана незаповнена клітинка.

б). Переміщення перевезень в межах клітинок, пов’язаних з вільною циклом.

Починаючи з вільної клітинки, якій приписується знак +, іншим почергово, просуваючись за циклом, приписуємо знаки — та +.

В вільну клітинку переносимо найменше з чисел , що знаходиться в мінусових клітинках. Це число додається до клітинок зі знаком + та віднімається від клітинок зі знаком — . В результаті вільна клітинка стає заповненою, а заповнена з мінімальним значенням та +-ом — вільною. Баланс перевезень не змінюється, оскільки в кожному стовпчику та рядку додається і віднімається одне й те ж значення.

Перехід до кроку 1.

Нижче наведені приклади можливих конфіґурацій циклів в транспортній таблиці.

Приклад.

На трьох пунктах зберігання наявні наступні запаси: a1=100, a2=150, a3=50. Потреби чотирьох пунктів споживання становлять b1=75, b2=80, b3=60, b4=85. Вартості перевезень одиниці продукції задані матрицею С . Прямою перевіркою впевнюємося, що задача закритого типу, оскільки сумарні потреби рівні сумарним запасам. Застосуємо на першому кроці для знаходження початкового опорного розв’язку метод північно-західного кута.

  B1 B2 B3 B4 Зап.
A1  
A2
A3  
Потр.

Розраховуємо значення потенціалів рядків та стовпчиків, використовуючи для цього заповнені клітинки таблиці та присвоюємо значення потенціалу .

 
 
-5
-10  

Після цього розраховуємо потенціали незаповнених клітинок і будуємо цикл. Оскільки серед потенціалів незаповнених клітинок є додатні, то знайдений опорний розв’язок не оптимальний — клітинка з найбільшим позитивним значенням потенціалу обирається як вершина циклу, а всі інші клітинки — вершини циклу повинні бути заповненими.

         
  - +  
       
-5   + -  
       
-10        
    -12   -13   -20  

Здійснюємо переміщення перевезення 25 в межах циклу та переходимо до нової транспортної таблиці з повторенням розрахунків.

         
0 -   +  
      -7     -1
2 +   -  
         
-3        
    -5   -13   -20  

Процес побудови циклу повторюємо, так як оптимального розв’язку ще не досягнуто.

         
0 -     +
       
-5 +     -
        -7  
-10        
    -12   -13   -17  

В процесі переходу від однієї таблички до іншої зберігається опорність знайденого перевезення, та зменшується його сумарна вартість, тобто йде процес наближення до оптимуму. Переходимо до наступної таблиці.

         
       
         
-5        
        -7   -6
-4        
    -6   -7   -21  

Оскільки серед потенціалів незаповнених клітинок немає ні одного додатнього, то знайдений план перевезень є оптимальним. Сумарна вартість перевезень для нього становитиме

.

Наши рекомендации