Транспортна задача. Математичне формулювання і алгоритм вирішення

В аспекті вирішення задач лінійного програмування розглянемо математичне формулювання і алгоритм розв’язання транспортної задачі.

Змістовна постановка задачі: Однорідний продукт, зосереджений у m пунктах відправлення в кількостях а₁, а₂,... а_m одиниць відповідно, необхідно доставити в кожний із n пунктів призначення в кількості b₁, b₂,... b_n одиниць відповідно. Вартість (відстань) перевезення одиниці продукту з i-го пункту відправлення в j-й пункт призначення дорівнює с_ij і відома для кожного маршруту. Нехай x_ij - кількість продукту, перевезеного з і-ro пункту відправлення в j-й пункт призначення. Задача полягає у визначенні таких розмірів x_ij для всіх маршрутів, при яких сумарна вартість (відстань) перевезень була б мінімальною.

Математична модель задачі:

Позначимо:

с_ij - тарифи (вартість, час, відстань) перевезення одиниці вантажу з i-го пункту відправлення в j-й пункт призначення;

a_i - запаси вантажу в i-му пункті відправлення;

b_і — потреба у вантажі в j-му пункті призначення;

x_ij - кількість одиниць вантажу, перевезеного з і-го пункту відправлення в j-й пункт призначення.

Тоді математична модель транспортної задачі про планування перевезень має такий вигляд:

_{m n}

y=∑∑c_ijx_ij→min; (3.12)

^{i=1 j=1 x}_ij^ÎΩ

_{m ____}

Ω: f_j=∑x_ij=b_i, j=1,n; (3.13)

ⁱ⁼¹

_{n ____}

f_n+i=∑x_ij=a_i, i=1,m; (3.14)

^j=1 _{_______ _______}

x_ij≥0; i=1,m; j=1,m. (3.15)

Тут (3.12) - цільова функція, що визначає вартість перевезень усього вантажу. Саме екстремальне (мінімальне) значення цієї функції необхідно знайти в задачі. Причому значення змінних х_ij, при яких цільова функція досягає свого мінімуму, повинні належати області припустимих рішень Ω.

Вирази (3.13) - (3.14) визначають область припустимих рішень Ω. При цьому вираз (3.13) відбиває потреби у вантажі в пунктах призначення, вираз (3.14) визначає запаси вантажів у пунктах відправлення, а вираз (3.15) відокремлює негативну область значень х_ij, в яку дані змінні не можуть потрапляти за своїм фізичним змістом.

Вирази (3.13)-(3.15) називаються обмеженнями задачі лінійного програмування. Вирішення задачі (частковий набір значень змінних x_i) називається припустимим, якщо воно одночасно задовольняє всім і обмеженням задачі. Вирішення задачі називається оптимальним, якщо воно забезпечує оптимум (у даному випадку мінімум) функції цілі.

Вважатимемо, що функції y, f₁, f₂,...,f_n - неперервні лінійні функції, задані на невід'ємному ортанті евклідового простору Rⁿ. Дані функції мають місце, коли перевезений вантаж є рідиною, сипкою речовиною, дрібними заготівлями або дрібною неспакованою продукцією. Такий вантаж характеризується параметрами, що являють собою вагу, довжину (погонні метри), площу (квадратні метри), об'єм і т.п.

Якщо загальна потреба у вантажі в пунктах призначення дорівнює запасу вантажу в пунктах відправлення, тобто

_{m n}

∑a_i=∑b_j, (3.16)

^{i=1 j=1}

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

При вирішенні задач лінійного програмування використовують відповідні теореми.

Теорема 1.1. Для можливості розв'язання транспортної задачі необхідно і достатньо, щоб запаси вантажу в пунктах відправлення були рівні потребам у вантажі в пунктах призначення, тобто щоб виконувалася рівність (3.16).

У випадку перевищення запасу над потребою, тобто вводиться фіктивний (n+1)-й пункт призначення з потребою . При цьому відповідні тарифи вважаються рівними нулю:c_i,n+1=0 (i=1,m).Така задача буде вже транспортною задачею, для якої умова (3.13) виконується.

Аналогічно, якщо , вводиться фіктивний (m+1) -й пункт відправлення із запасом вантажу . При цьому відповідні тарифи вважаються рівними нулю: c_m+1,j=0 (j=1,n).Така задача буде вже транспортною задачею, для якої умова (3.16) виконується.

Далі будемо розглядати закриту модель транспортної задачі. Якщо ж модель конкретної задачі є відкритою, то, виходячи зі сказаного вище, її необхідно перетворити так, щоб виконувалася рівність (3.16).

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

Особливості вирішення закритої транспортної задачі:

Визначення 1.1. Усяке невід'ємне рішення систем лінійних рівнянь (3.13) і (3.14), що обумовлене матрицею X=[x_ij], i=1,m, j=1,n, називається планом транспортної задачі.

Визначення 1.2. План X^* =[x^*_ij], i=1,m, j=1,n, при якому функція (3.12) приймає своє мінімальне значення, називається оптимальним планом транспортної задачі.

Число змінних x_ij y транспортній задачі з m пунктами відправлення і n пунктами призначення дорівнює mn, а число рівнянь у системах (3.13) і (3.14) дорівнює m+n. Оскільки передбачається, що виконується умова (3.16), то число лінійно незалежних рівнянь дорівнює m+n-1. Отже, опорний план транспортної задачі може мати не більше m+n-1 відмінних від нуля невідомих.

Визначення 1.3. План X^* =[x^*_ij], i=1,m, j=1,n є опорним, якщо в ньому кількість відмінних від нуля компонентів у точності дорівнює m+n-1, а якщо менше - то ні.

Для визначення опорного плану існує декілька методів. Один з них - метод північно-західного кута, який буде розглянутий нижче.

Як і для всякої задачі лінійного програмування, оптимальним план транспортної задачі є також опорним планом. Для визначення оптимального плану транспортної задачі можна використовувати диференціальний алгоритм, симплекс-метод та інші універсальні методи. Однака через виняткову практичну важливість цієї задачі і специфіку її обмежень (кожна невідома входить лише в два рівняння систем (3.13) і (3.14), а коефіцієнти при невідомих дорівнюють одиниці) для визначення оптимального плану транспортної задачі розроблені спеціальні методи. Один з них - метод потенціалів - розглядається в даному курсі.

Звичайно вихідні дані транспортної задачі записують у вигляді табл.3.1.

Таблиця 3.1 - Вихідні дані транспортної завдання

Пункти відправлення	Запаси	Пункти призначення
		…	j	…	n
Потреби
b1	b2	…	b1	…	bn
	a1	c11 x11	c12 x12	…	c1j x1j	…	c1n x1n
	a2	c21 x21	c22 x22	…	c2j x2j	…	c2n x2n
…	…	…	…	…	…	…	…
i	ai	ci1 xi1	ci2 xi2	…	cij xij	…	cin xin
…	…	…	…	…	…	…	…
m	am	cm1 xm1	cm2 xm2	…	cmj xmj	…	cmn xmn

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

Сутність цього методу полягає в тому, що опорний план знаходять за m+n-1 кроками, на кожному з яких у таблиці транспортної задачі заповнюють одну клітку. Заповнення однієї клітки забезпечує задоволення потреби у вантажі одного з пунктів призначення (відповідно до того, в стовпці якого знаходиться клітка), або вивіз вантажу з одного з пунктів відправлення (відповідно до того, в рядку якого знаходиться клітка).

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

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

Після m+n-2 описаних вище кроків одержують задачу з одним пунктом відправлення і одним пунктом призначення. При цьому залишається вільною тільки одна клітка, а запаси пункту відправлення дорівнюватимуть потребам пункту призначення. Заповнення цієї клітки, тобто здійснення (m+n-1) -го кроку приводить до шуканого опорного плану.

Слід зауважити, що в процесі використання методу північно-західного кута може трапитися, що потреби у вантажі чергового пункту призначення рівні запасам чергового пункту відправлення. У цьому випадку з подальшого розгляду виключають або стовпець, або рядок, тобто тільки що-небудь одне. Таким чином, запаси відповідного пункту відправлення, або потребу відповідного пункт призначення вважають рівними нулю. Цей нуль записують у чергову клітку, яка заповнюється [61].

Зазначені вище умови гарантують одержання m+n-1 зайнятих кліток, у яких знаходяться компоненти опорного плану.

Опорний план перевезень повинен відповідати таким вимогам:

по-перше, кількість зайнятих маршрутів (кліток) повинна бути на одиницю менше суми числа постачальників т і числа споживачів п, тобто повинна дорівнювати значенню m+n-1;

по-друге, не повинно бути жодного зайнятого маршруту (клітки), що опинився б єдиним і в рядку, і в стовпці таблиці.

Визначення оптимального опорного плану транспортної задачі:

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

Теорема 1.2. Якщо для деякого опорного плану X^* =[x^*_ij], i=1,m, j=1,n транспортної задачі із заданими тарифами перевезень c_ij існують такі числа α_i(i=1,m) i β_j(j=1,n), що

β_i-α_j=c_ij при x_ij>0 (3.17)

і β_i-α_j≤c_ij при x_ij=0 (3.18)

для всіх i=1,m і j=1,n, то X^* =[x^*_ij] - оптимальний план.

Визначення 1.4. Числа α_i(i=1,m) i β_j(j=1,n) називаються потенціалами відповідно пунктів відправлення і пунктів призначення.

Теорема 1.2 дозволяє побудувати алгоритм знаходження рішення транспортної задачі. Він являє собою наступне. Нехай знайдений опорний план транспортної задачі. Для кожного з пунктів відправлення і призначення визначають потенціали α_i(i=1,m) i β_j(j=1,n) із системи рівнянь

β_i-α_j=c_ij. (3.19)

Оскільки число заповнених кліток дорівнює n+m-1, то система (3.19) із n+m невідомими містить n+m-1 рівнянь. Оскільки число невідомих перевищує на одиницю число рівнянь, одне з невідомих потрібно взяти рівним довільному числу, наприклад α₁=0, і знайти послідовно із системи (3.19) значення інших невідомих.

Після того, як усі потенціали знайдені, дія кожною з вільних кліток визначають числа α_ij=β_i-α_j-c_ij. Якщо серед чисел α_ij немає позитивних, то знайдений опорний план є оптимальним. Якщо ж для деякої вільної клітки α_ij>0, то опорний план, що перевіряється, не є оптимальним, і треба перейти до нового опорного плану. Для цього розглядають усі вільні клітки, для яких α_ij>0, і вибирають ту, для якої число α_ij максимальне. Обрану клітку необхідно заповнити.

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

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

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

При правильній побудові опорного плану для будь-якої вільної клітки можна побудувати тільки один цикл. Після того як для обраної вільної клітки він побудований, необхідно перейти до нового опорного плану. Для цього треба перемістити вантажі в межах кліток, що утворюють цикл. Переміщення роблять за такими правилами:

кожній з кліток, пов'язаних циклом з обраною вільною кліткою, і приписують знак "+" або "-", причому вільній клітці - знак плюс, а всім іншим кліткам - по черзі знаки мінус і плюс;

у вільну клітку переносять менше з чисел x_ij, що знаходяться в мінусових клітках, і одночасно це число додають до відповідних чисел, що знаходяться в "плюсових" клітках, і віднімають із чисел, що знаходяться в "мінусових" клітках. Клітка, що раніше була вільною, стає зайнятою, а "мінусова" клітка, в якій стояло мінімальне число x_ij, стає вільною.

У результаті зазначених вище переміщень вантажів у межах кліток, пов'язаних циклом з обраною вільною кліткою, визначають новий опорний план транспортної задачі. Число зайнятих кліток залишається рівним n+m-1. Якщо в зайнятих "мінусових" клітках циклу є два і більше однакових мінімальних чисел x_ij, то звільняють тільки одну з таких кліток, а інші залишають зайнятими з нульовими постачаннями.

Отриманий новий опорний план транспортної задачі перевіряють на оптимальність. Для цього визначають потенціали пунктів відправлення і призначення і знаходять числа α_ij=β_i-α_j-c_ij для всіх вільних кліток. Якщо серед цих чисел не буде позитивних, то це означає, що новий опорний план є оптимальним. Якщо ж є позитивні числа, то необхідно перейти до нового опорного плану. У результаті ітераційного плану кінцевого числа переходів одержують оптимальний план процесу.

Таким чином, процес вирішення транспортної задачі методом потенціалів включає такі етапи:

1-й етап. Знаходять опорний план.

2 й етап. Знаходять потенціали пунктів відправлення; і призначення.

3-й етап. Визначають числа α_ij для кожної вільної клітки. Якщо серед них немає позитивних, то отримано оптимальний план транспортної задачі, у противному разі переходять до нового опорного плану.

4-й етап. Вибирають серед позитивних чисел α_ij максимальне, будують для відповідної вільної клітки цикл перерахування і роблять зсув за циклом, одержуючи при цьому новий опорний план. Далі переходять до другого етапу.

Розглянемо приклад вирішення транспортної задачі методом потенціалів.

Приклад вирішення транспортної задачі методом потенціалів:

Приклад 1.1. Три заводи, що виготовляють бетонні конструкції, постачаються цементом з чотирьох складів. Попит заводів b_j відповідно дорівнює 280, 90 і 180 тис.т/міс. Пропускна здатність складів a_i, відповідно становить 200, 150, 80 і 120 тис.т/міс. Відстані перевезень (у км)

з і-го складу на j-й завод подані в матриці C=[c_ij]=

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

Вирішення

Позначимо через x_ij - кількість цементу, який щомісяця потрібно доставляти щомісяця на j-го завод з i-го складу. Тоді математична модель задачі має вигляд:

y=x₁₁+5x₁₂+3x₁₃+6x₂₁+8x₂₂+9x₂₃+2x₃₁+7x₃₂+4x₃₃+4x₄₁+x₄₂+11x₄₃→min; (3.20)

^xijÎΩ

Ω: x₁₁+x₂₁+x₃₁+x₄₁=280; (3.21)

x₁₂+x₂₂+x₃₂+x₄₂=90; (3.22)

x₁₃+x₂₃+x₃₃+x₄₃=180; (3.23)

x₁₁+x₁₂+x₁₃=200; (3.24)

x₂₁+x₂₂+x₂₃=150; (3.25)

x₃₁+x₃₂+x₃₃=80; (3.26)

x₄₁+x₄₂+x₄₃=120; (3.27)

x_ij³0. (3.28)

Тут (3.20) - цільова функція, (3.22) - (3.24) - обмеження задачі, що визначають місячні запаси цементу на складах, (3.25) - (3.27) – обмеження задачі, що визначають місячну потребу в цементі на заводах (3.28) - обмеження, що визначає неможливість негативних значень для постачань цементу на заводи.

1-й крок. 1-й етап. Використовуючи метод північно-західного кута, знайдемо опорне вирішення транспортної задачі (3.20)- (3.28).

Відповідно до цього методу заповнюємо таблицю, починаючи лівого верхнього квадрата. Порівнюємо запас вантажу в першому пункті відправлення (200 тис.т/міс.) із потребою першого пункту призначення (280 тис.т/міс.). Вибираємо меншу величину (200) і записуємо її в даний квадрат. Оскільки весь запас у першому пункті відправлення вичерпаний, то з подальшого розгляду виключаємо перший рядок і переходимо в сусідню клітку, що знаходиться нижче заповненої. У новій клітці для частини таблиці, що залишилася, повторюємо процедуру заповнення верхньої лівої клітки, але з урахуванням того, що потреба першого пункту призначення зменшилася на 200 тис.т/міс. і стала рівною 80 тис.т/міс. Тобто порівнюємо запас другого пункту відправлення (150 тис.т/міс.) з новою потребою першого пункту призначення (80 тис т/міс). Вибираємо меншу величину(80) і записуємо її в нову клітку Оскільки потреба у вантажі в першому пункті призначення повністю задоволена, то з подальшого розгляду виключаємо перший стовпець і переходимо в сусідню клітку, що знаходиться справа від тільки що заповненої. Для нової верхньої лівої клітки частини таблиці, що залишилася, повторюємо процедуру заповнення з урахуванням зміни запасу в другому пункті відправлення на 50 тис.т/міс. І так доти, поки не буде заповнено m+n-2 кліток.

Остання (m+n-2)-я клітка заповнюється механічно - у неї записується залишкова потреба останнього пункту призначення або залишковий запас останнього пункту відправлення. В умовах задачі це величина 120. Усі проміжні результати по знаходженню початкового опорного плану

Х₀ = відображені в табл. 3.2. Ці результати в таблиці виділені напівжирним шрифтом.

Для початкового опорного плану обчислюємо значення цільової функції (3.20):

y₀=1х200+6х80+8х70+7х20+4х60+11х120=2940 тис.т/міс.

Це значення буде використано на наступних кроках для контролю просування до оптимуму. Значення цільової функції повинно послідовно зменшуватися з кожним кроком.

Таблиця 3.2 - Проміжні результати по знаходженню початкового опорного плану

Пункт відправ-лення	Запас вантажу	Пункт призначення	Потенціал пункту відправлення ai
Потреба
					-5
			- 20	+ 60	-4
			+	- 120	-11
Потенціал пункту призначення bi

2-й етап. Знайдений опорний план перевіряємо на оптимальність. У зв'язку з там знаходимо потенціали пунктів відправлення і призначення із системи

b₁-a₁=1, b₂-a₂=8, b₃-a₃=4,

b₁-a₂=6, b₂-a₃=7, b₃-a₄=11.

що містить шість рівнянь із сімома невідомими. Вважаючи a₁=0, знаходимо b₁=1, a₂=-5, b₂=3, a₃=-4, b₃=0, a₃=-11. Записуємо знайдені потенціали в табл.3.2.

3-й етап. Для кожної вільної клітки обчислюємо числа α_ij=β_i-α_j-c_ij: α₁₂=-2, α₁₃=-3, α₂₃=-4, α₃₁=3, α₄₁=8, α₄₂=13.

Записуємо знайдені числа у відповідні вільні клітки табл.3.2 і вміщуємо їх у рамочки, щоб відрізняти їх від іншої інформації в таблиці Тому що серед чисел α_ij є позитивні, то опорний план Х₀ не є оптимальним.

4-й етап. Серед позитивних чисел α_ij вибираємо максимальне: α₄₂=13. Для відповідної вільної клітки будуємо цикл, а саму клітку позначаємо знаком «+». У табл.3.2 зайняті клітки, що складають цикл, виділені сірим фоном. Потім позначаємо знаками «-» і «+» по черзі інші клітки циклу, слідуючи уздовж ломаної лінії циклу.

Найменшим з чисел x_ij у «мінусових» клітках є x₃₂ (20). Дана клітка стає вільною, а інші клітки циклу змінюють свої значення в такий спосіб: Х₄₂=20, х₄₃=120-20=100, х₃₃=60+20=80.

У результаті зроблених перетворень одержуємо новий опорний план

X₁=

При такому опорному плані функція цілі (3.20) стає рівною 2680 тис.т/міс, що менше вихідного значення 2940 тис.т/міс.

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

2-й крок. Аналізуємо новий опорний план (табл.3.3) на оптимальність. Знову знаходимо потенціали пунктів відправлення і пунктів призначення, для чого складаємо таку систему рівнянь:

b₁-a₁=1, b₂-a₂=8, b₂-a₄=1,

b₁-a₂=6, b₃-a₃=4, b₃-a₄=11.

Вважаючи a₁=0, знаходимо b₁=1, a₂=-5, b₂=3,a₄=2, b₃=13, a₃=9. Для кожної вільної клітки обчислюємо числа α_ij: α₁₂=-2, α₁₃=10, α₂₃=9, α₃₁= -10,
α₃₂=-13, α₄₁=-5.

Тому що серед чисел α_ij є позитивні (α₁₃=10, α₂₃=9), то опорний план X₁
не є оптимальним.

Таблиця 3.3 - Новий опорний план

Пункт відправлення	Запас вантажу	Пункт призначення	Потенціал пункту відправлення ai
Потреба
		- 200		+
		+ 80	- 70		-5
			+ 20	- 100
Потенціал пункту призначення bi

Серед позитивних чисел α_ij вибираємо максимальне: α₁₃=10. Для відповідної вільної клітки будуємо цикл, а саму клітку позначає знаком «+». У табл.3.3 зайняті клітки, що складають цикл, виділені рим фоном. Потім позначаємо вузлові клітки циклу по черзі знаками «-» і «+».

Найменшим із чисел x_ij у «мінусових» клітках є х₂₃ (70). Дана клітка стає вільною, а інші клітки циклу змінюють свої значення в так спосіб: x₁₁=200-70=130, x₁₃=70, х₂₁=80+70=150, x₄₂=20+70=90, x₄₃=100-70=30.

У результаті виконаних перетворень одержуємо новий опори план

Х₂=

При такому опорному плані функція (3.20) стає рівною 1980 тис.т/міс, що значно менше попереднього значення 2680 тис.т/міс.

3-й крок. Аналізуємо новий опорний план (табл. 3.4) на оптимальність. Знову знаходимо потенціали пунктів відправлення і пунктів призначення, для чого складаємо наступну систему рівнянь:

b₁-a₁=1, b₁-a₂=6, b₂-a₄=1,

b₃-a₁=3, b₃-a₃=4, b₃-a₄=11.

Вважаючи a₁=0, знаходимо b₁=1, b₃=3, a₂=-5, b₃=4, a₃=0, a₄=-8, b₂=-7. Для кожної вільної клітки обчислюємо числа α_ij: α₁₂=-12, α₂₂=-10, α₂₃=-1, α₃₁=-1, α₃₂=-14, α₄₁=5. Оскільки серед чисел α_ij одне позитивне (α₄₁=5), то опорний план Х₂ не є оптимальним.

Таблиця 3.4 - Новий опорний план

Пункт відправ-лення	Запас вантажу	Пункт призначення	Потенціал пункту відправлення ai
Потреба
		- 130		+ 70
					-5
		+		- 30	-8
Потенціал пункту призначення bi		-7

Для відповідної вільної клітки (нижньої, лівої) будуємо цикл, а саму клітку позначаємо знаком «+». У табл.3.4 зайняті клітки, що складають цикл, виділені сірим фоном. Потім позначаємо вузлові клітки циклу по черзі знаками «-» і «+». Найменшим із чисел x_ij у «мінусових» клітках є х₄₃ (30). Дана клітка стає вільною, а інші клітки циклу змінюють свої значення в такий спосіб:
x₁₁ =130-30=100, х₁₃ =70+30=100, x₁₄=30.

У результаті зроблених перетворень одержуємо новий опорі план

Х₄=

При такому опорному плані функція (3.20) стає рівною 1830 тис.т/міс, що менше попереднього значення 1980 тис.т/міс.

4-й крок. Аналізуємо новий опорний план (табл.3.5) на оптимальність. Знову знаходимо потенціали пунктів відправлення і пунктів призначення, для чого складаємо наступну систему рівнянь:

b₁-a₁=1, b₁-a₂=6, b₁-a₄=4,

b₃-a₁=3, b₃-a₃=4, b₂-a₄=1.

Вважаючи a₁=0, знаходимо b₁=1, b₃=3, a₂=-5, a₃=-1, a₄= -3, b₂= -2. Для кожної вільної клітки обчислюємо числа α_ij: α₁₂=-7, α₂₂=-4, α₂₃=-1, α₃₁=0, α₃₂=-8, α₄₁=-5. Тому що серед чисел α_ij і немає строго позитивних, то опорний план Х₃
є оптимальним.

Таблиця 3.5 - Новий опорний план