Крок 3

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

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

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

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

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

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

						Штрафи рядків







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

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

Штрафи рядків

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

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

			Штрафи рядків







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

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

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

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

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

Базисні змінні набувають значень: х ₁₂=0, х ₁₄=10, х ₂₂=10, х ₂₃=10, х ₃₁=5, х ₃₂=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

	v ₁=2	v ₂=5	v ₃=2	v ₄=-1

u ₁=0
					-1	-1

u ₂=-1
	-2					-6

u ₃=3	Х ₃₁
Ю	+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)