2.1 Визначення початкового опорного розв’язку.

Опорний план Т- задачі являє собою матрицю розміром m n, причому заповнені позиції матриці, відповідають базисним невідомим і їх число рівно r=m+n-1.

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

Метод північно- західного кута.

Будемо заповнювати транспортну таблицю (таблиця 2), починаючи з лівого верхнього («північно- західного») кута, рухаючись далі або по рядку праворуч, або по стовпцю вниз.

Таблиця 2

Постачальник	Споживачі					Запас
	В1	В2	В3	В4	В5
А1	100 0	7	4	1	4	100
А2	100 2	150 7	10	6	11	250
А3	8	50 5	100 3	50 2	2	200
А4	1	8	12	50 6	250 13	300
Потреба	200	200	100	100	250	850 = 850

Знайдемо загальну вартість складеного плану:

Z=100*10+100*2+150*7+50*5+100*3+50*2+50*16+250*13=6950(од.варт.)

Достоїнство методу: Метод північно- західного кута приводить до опорного розв’язку, причому одночасно з його знаходженням формується і повний базис цього опорного розв’язку (заповнені клітки- базисні клітки, незаповнені- вільні змінні).

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

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

Метод мінімального елемента

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

Таблиця 3

Постачальник	Споживачі					Запас
	В1	В2	В3	В4	В5
А1	10	7	4	100 1	4	100
А2	200 2	50 7	10	6	11	250
А3	8	5	3	2	200 2	200
А4	11	150 8	100 12	16	50 13	300
Потреба	200	200	100	100	250	850 = 850

Визначимо вартість отриманого плану перевезень

z= 100*1+ 200*2+ 50*7+ 200*2+ 150*8+ 100*12+ 50*13=4300(од. варт.).

Вартість плану перевезень значно менше, отже він ближче до оптимального.

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