Крок 3

3.1. Якщо невикресленим залишається рівно один рядок або один стовпчик, то закінчити обчислення.

3.2. Якщо залишається невикресленим тільки один рядок (стовпчик) із додатним обсягом виробництва (попитом), знайти базисні змінні в цьому рядку (стовпчику), використовуючи метод найменшої вартості.

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

3.4. В інших випадках обчислити нові значення штрафів для невикреслених рядків і стовпчиків і перейти до кроку 2(рядки та стовпчики з нульовими значеннями обсягу виробництва та попиту не слід використовувати при обчисленні цих штрафів).

Знайдемо ДБР задачі, умову якої наведено в наступній таблиці, за допомогою наближеного методу Фогеля.

Нижче наведено таблицю, що містить перший набір штрафів для рядків та стовпчиків. Оскільки рядок 3 має найбільший штраф (=3) та с31=2 є найменшим коефіцієнтом вартості, то змінній х31 приписуємо значення 5. Викреслюємо стовпчик 1.

    Штрафи рядків
             
       
             
       
             
     
     
Штрафи стовпчиків    

Наступна таблиця вміщує новий набір штрафів, одержаний після викреслювання стовпчика 1.

      Штрафи рядків
               
         
               
       
               
     
       
Штрафи стовпчиків ѕ      
                           

У цій таблиці другий рядок та третій стовпець мають найбільший штраф. Оберемо рядок 2. При цьому с23=1 є найменшим коефіцієнтом вартості в рядку. Змінній х23 приписуємо значення 10 і викреслюємо стовпчик 3.

      Штрафи рядків
               
       
               
     
               
     
       
Штрафи стовпчиків ѕ ѕ      

Рядок 1 є рядком з найбільшим штрафом. Елемент х14 є елементом з найменшою вартістю. Тому приписуємо йому значення 10. Обмеження виконується по рядку і по стовпчику, тобто викреслити можна або рядок, або стовпчик.

Викреслюємо стовпчик 4.

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

   
                   
    ѕ    
                   
    ѕ    
                   
    ѕ  
           
ѕ ѕ ѕ          
                 
    ѕ              

У результаті одержуємо такий базисний розв’язок:

         
   
         
   
         
   
 

Базисні змінні набувають значень: х12=0, х14=10, х22=10, х23=10, х31=5, х32=15. Сумарні витрати складають: 0*5+10*1+10*4+10*1+5*2+15*6=160.

 

5.5.3. Знаходження змінної, що вводиться до базису

Змінну, що вводиться до базису, знаходять, використовуючи умову оптимальності симплекс-методу.

Нехай ТЗЛП задано у векторній формі:

(5.10)

(5.11)

(5.12)

Вибір змінної, що вводиться до базису, залежить від значень компонент вектора відносних оцінок, який у "звичайному" модифікованому симплекс-методі визначається так:

(5.13)

де – вектор оцінок обмежень (двоїстих змінних).

Вектор визначається таким чином:

Тобто є розв’язком такої системи лінійних рівнянь:

Після транспонування одержимо:

(5.14)

Розглянемо тепер модифікований симплекс-метод, який застосуємо до ТЗЛП.

Подамо вектор оцінок обмежень (5.11) ЗЛП (5.10) – (5.12) у вигляді , де пiдвектор відповідає m першим обмеженням, пов’язаним з виробниками, а пiдвектор –n - останнім обмеженням, пов’язаним зі споживачами. Побудуємо для задачі (5.10) – (5.12) систему (5.14), записану за рівняннями:

= , (i, j , (5.15)

де – множина пар індексів базисних змінних.

З урахуванням структури векторів = із системи (5.15) одержуємо:

+ = ; (i, j . (5.16)

Система (5.16) має m+n змінних і m+n—1 рівнянь.

У системі обмежень ТЗЛП одне з обмежень "зайве ". Відкинути його – це означає надати відповідній йому двоїстій змінній довільного значення (найпростіше прирівняти до нуля). Оскільки зайвим можна вважати будь-яке з рівнянь, то значення "нуль" можна надати будь-якій зі змінних або . Нехай =0. Після цього система (5.16) перетворюється у систему з m+n—1 рівнянь із m+n—1 змінними.

Нехай , , , – розв’язок системи (5.16). Тоді, враховуючи (5.13), можемо визначити відносні оцінки небазисних змінних:

= + . (5.17)

Якщо всі Ј 0, то задане ДБР оптимальне, якщо >0, то треба переходити до наступного ДБР.

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

Побудуємо систему (5.16) за початковим ДБР задачі, одержаним методом північно-західного кута (див. табл. 5.3). Рівняння, пов’язані з базисними змінними, матимуть вигляд:

Поклавши = 0, одержимо значення потенціалів:

= 2, = 5, = –1, = 2, = 3, = –1.

Відповідно до (5.18) оцінки для небазисних змінних визначаються таким
чином:

Оскільки =max{ } за небазисними змінними , то змінна обирається як змінна, що вводиться до базису (табл. 5.4).

Таблиця 5.4

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

Рівняння + = , використовувані для знаходження потенціалів, мають настільки просту структуру, що насправді їх не треба записувати в явному вигляді. Звичайно набагато простіше визначати потенціали безпосередньо з транспортної таблиці, помітивши, що рядка i і стовпчика j в сумі дають , якщо на перетині рядка iта стовпчика jзнаходиться базисна змінна . Визначивши , можна обчислити для всіх небазисних змінних , додаючи рядка р до стовпчика qі потім віднімаючи величину , що стоїть на перетині рядка рта стовпчика q.

Далі величини будемо вказувати в південно-західному куті кожного небазисного елемента.

5.5.4. Знаходження змінної, що виводиться з базису (побудова циклу)

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

Для визначення мінімального відношення побудуємо замкнений цикл, який відповідає змінній, що вводиться ( на першiй iтерацiї). Призначення цього циклу – компенсувати зміну небазисної змінної з метою відновлення балансу за рядками та стовпчиками (цей цикл називають компенсаторним).

Цикл починається та закінчується обраною небазисною змінною. Він складається з послідовності горизонтальних та вертикальних (зв’язаних) відрізків, кінцями яких повинні бути базисні змінні (за винятком тих кінців, які стосуються змінної, що вводиться до базису). Це означає, що кожна клiтина, що стоїть у вершині (зламі) циклу, повинна містити базисну змінну. Табл. 5.5 ілюструє цикл, який відповідає ввідній змінній для початкового базисного розв’язку задачі з табл. 5.2. Цей цикл можна виразити за допомогою базисних змінних таким чином: . Несуттєво, у якому напрямі (за чи проти годинникової стрілки) проводиться обхід циклу. Відзначимо, що відповідно до наступної теореми 4 та її наслідкiв для кожного базисного розв’язку та відповідної небазисної змінної можна побудувати лише один цикл.

Теорема 4 (про єдиність циклу)

Сукупність векторів , (i,j)О R (R — деяка множина пар індексів) буде лінійно-залежною тоді і тільки тоді, коли з множини відповідних їм клітин транспортної задачі можна обрати частину, що утворює цикл.

Наслідок 1. Допустимий розв’язок транспортної задачі є базисним тоді, і тільки тоді, коли з клітин, що займає цей розв’язок, не можна утворити жодного циклу.

Наслідок 2. Якщо таблиця транспортної задачі містить базисний розв’язок задачі (5.1) — (5.3), то для кожної вільної клітини цієї таблиці можна утворити один і тільки один цикл, що містить цю клітину та деяку частину зайнятих клітин.

Нехай маємо деякий ДБР { } i нехай за змiнну, що вводиться у базис, обрано змiнну (їй вiдповiдає клiтина транспортної таблицi ). Згiдно з нас­лiдком 2 для небазисної змiнної завжди iснує компенсаторний цикл клiтин, що замикається на клiтинi , і при тому лише єдиний. При цьому змiннiй надається деяке значення D ³ 0.

Перемiщення по циклу будь-якого числа D не змiнить балансових рiвностей по рядках i стовпчиках таблицi. I при цьому для компенсацiї змiни колишньої небазисної змiнної деякi базиснi змiннi збiльшуються на D, а деякi — зменшуються
на D.

Позначимо знаком "+" ті клiтини циклу, які вiдповiдають базисним клiтинам, що збiльшуються на D, а знаком "–" – ті, що зменшуються на D. Множина пар iндексiв базисних змiнних вiдповiдно розбивається на три пiдмножини, що не перетинаються:

При довiльному виборi значення D деякi змiннi у новому розв’язку можуть стати вiд’ємними. Отже, щоб новий розв’язок залишався допустимим, має виконуватися така умова:

(5.19)