Схема методу потенціалiв

Попереднiми мiркуваннями обґрунтована послiдовнiсть крокiв методу потенціалів розв’язання транспортних задач.

Крок 0. Побудова початкового ДБР.

Побудувати початковий ДБР { } задачi (методом пiвнiчно-захiдного кута, методом мінімальної вартостi й т. ін.).

Нехай — множина пар iндексiв базисних змiнних початкового ДБР.

Крок 1. Обчислення вiдносних оцiнок небазисних змiнних.

За множиною побудувати систему рiвнянь:

+ = ; (i, j .

Знайти розв’язок { } i=1, …, m, { } j=1, …, n такої системи з точнiстю до доданка. Обчислити вiдноснi оцiнки :

= + , (i, j )Ï .

Крок 2. Перевiрка умови оптимальностi.

Якщо £ 0 для всiх (i, j)Ï , то припинити обчислення, поточне ДБР є розв’язком початкової задачi.

Крок 3. Вибiр небазисної змiнної, що вводиться у множину базисних

Обрати пару таку, що > 0 Þ змiнну ввести в базис.

Крок 4. Вибiр базисної змiнної, що виводиться з множини базисних.

Для змiнної побудувати компенсаторний цикл. Видiлити множини i . Обрати

Крок 5. Перехiд до нового ДБР.

Визначити новий ДБР за допомогою спiввiдношень:

Побудувати нову множину пар iндексiв базисних змiнних:

Покласти i перейти до кроку 1.

Продовжимо розв’язання задачi, початковий ДБР якої наведено в табл. 5.5.

Таблиця 5.5

  v1=2 v2=5 v3=2 v4=-1  
Ь          
u1=0    
-     Е -1   -1    
           
u2=-1    
  -2     -   Е -6    
           
u3=3 Ю х31  
  +3 Е     -      
  5 Э  

З табл. 5.5 бачимо, що, якщо значення (змінної, що вводиться до базису) збільшується на одиницю, для збереження допустимості розв’язку значення базисних змінних, що стоять на зламах -циклу, необхідно скоректувати таким чином: зменшити на одиницю, збільшити на одиницю, зменшити на одиницю, збільшити на одиницю і, нарешті, зменшити на одиницю. Цей процес позначений знаками Е та “–”у відповідних клітинах табл. 5.4. Введені зміни не порушують обмежень на обсяги виробництва та попит.

Змінна, що виводиться з базису, обирається зі змінних, що знаходяться на зламах циклу, значення яких зменшуються при збільшенні . Вони розташовуються в табл. 5.5 у клітинах, помічених знаком “–”. З табл. 5.5 випливає, що , , – базисні змінні, які зменшуються зі зростанням . Змінною, що виводиться з базису, стає та, що має найменше значення, оскільки саме вона раніше за всіх досягне нуля, і будь-яке подальше зменшення робить її від’ємною. У цьому прикладі = 5, = 20, = 10,

Таким чином, за змінну, що вилучається, обирається змінна ; тоді значення буде дорівнювати 5, а змінні, що знаходяться на зламах циклу (базисні), відповідним чином коректуються (тобто кожна з них збільшується або зменшується на 5 одиниць залежно від знака Еабо ”–”). Новий розв’язок наведено у табл. 5.6.

Таблиця 5.6

   
     
                 
   
   
                 
   
 
                 
 

Цей розв’язок має таку вартість:

z1

Одержана вартість є відмінною від z0 на 185 — 170 = 15 од. вартості, тобто на величину, приписану змінній = 5 і помножену на = 3.

Оптимальність нового базисного розв’язку з табл. 5.6 перевіряють обчисленням нових потенціалів та оцінок небазисних змінних (табл. 5.7). Небазисна змінна , що має максимальну додатну оцінку = 2, вводиться до складу базисних.

Таблиця 5.7

  v1=-1 v2=5 v3=2 v4=-1  
           
u1=0      
  -3       -1   -1    
           
u2=-1   15  
  -5     ѕ   Е -6    
           
u3=3 x32
      +2 Е   ѕ      
  25 Э 10 Я  

Замкнений цикл, що відповідає , , показує, що з базису повинна бути вилучена змінна

У табл. 5.8 наведено новий базисний розв’язок з вартістю .

Таблиця 5.8

  v1=1 v2=5 v3=2 v4=1  
           
u1=0     х14
  -1     - -1   +1 Е Ь
           
u2=-1    
  -3           -6    
           
u3=1  
        Е -2     -  
  10 Я  

Оскільки , то розв’язок не оптимальний. Для змінної , що вводиться до базису, побудуємо компенсаторний цикл: . З компенсаторного циклу бачимо, що з базису може бути вилучена або змінна , або змінна (оскільки ); зупинимося на останній. У результаті одержимо розв’язок, наведений у табл. 5.9.

Таблиця 5.9

  v1=1 v2=5 v3=2 v4=0  
           
u1=0    
  -1       -1        
           
u2=-1    
  -3           -5    
           
u3=1    
          -2   -1    
   

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

Оптимальний план перевезень наведено в табл. 5.10.


Таблиця 5.10