5.2. Визначення вихідного опорного плану

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

Задача 5.2. Знайти методом північно-західного кута вихідний опорний план для транспортної задачі 1.3 (с. 10).

Рішення

Заповнимо таблицю постачань задачі 5.1 наступним чином. Дамо змін- ній максимально можливе значення або, іншими словами, максимально можливе постачання в клітину (1,1) – “північно-західний” кут цієї таблиці: . Після цього запас 1-го постачальника буде цілком реалізований, і перший рядок таблиці випадає з подальшого розгляду. В таблиці, що залишилася, знайдемо новий “північно-західний” кут – клітину (2,1) і запишемо в неї максимально можливе значення. Оскільки 1-й споживач вже отримав 40 одиниць товару, маємо . Після цього попит 1-го споживача вдоволений, і з розгляду випадає перший стовпець. У таблиці постачань знову знайдемо новий “північно-західний” кут – клітину (2,2) і запишемо в неї максимально можливе значення. Оскільки 2-й постачальник вже віддав 5 одиниць товару, одержуємо . Попит 2-го споживача вдоволений, і з розгляду випадає другий стовпець. Аналогічно, продовжуючи заповнення таблиці постачань крок за кроком, одержуємо,

, (табл. 5.2).

														Таблиця 5.2
	bj ai		45			35			55			65
40		4			1			2			5
		40
60		3			2			3			7
		5			35			20
90		4			4			5			2
								35			55
10		0			0			0			0
											10

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

Обчислимо для даного розподілу сумарні витрати на перевезення товару: .

Задача 5.3. Знайти методом подвійної переваги вихідний опорний план для транспортної задачі 1.3 (с. 10).

Рішення

У кожному рядку таблиці постачань (див. табл. 5.1) позначаємо знаком * клітини, для яких вартість перевезення одиниці товару є найменшою в рядку. У кожному стовпці цієї таблиці позначаємо знаком * клітини, для яких вартість перевезення одиниці товару є найменшою у стовпці. При цьому вартість перевезень одиниці товару фіктивного постачальника не враховується. В результаті в таблиці з’являються три типи клітин: позначені знаком **, знаком * і непо-значені. Спочатку максимально заповнюються клітини, позначені **, потім клітини, позначені *. Далі виконується добалансування таблиці, тобто заповнюються непозначені клітини так, щоб запаси всіх постачальників були реалізовані і попит всіх споживачів був задоволений.

У даному випадку спочатку запишемо у клітину (1,2), позначену **, максимально можливе значення: . Після цього попит 2-го споживача задоволений, і з розгляду випадає другий стовпець. Далі запишемо в клітину(3,4), позначену **, максимально можливе значення: . Після цього попит 4-го споживача вдоволений, і з розгляду випадає четвертий стовпець. В таблиці, що залишилася, заповнимо клітини, позначені знаком * –клітини (1,3) і (2,1): ,. Після цього перший рядок і перший стовпець випадають з подальшого розгляду. Зробимо добалансування третього стовпця таблиці:

, ,

.

														Таблиця 5.3
	bj ai		45			35			55			65
40		4			1		**	2		*	5
					35			5
60		3		*	2		*	3			7
		45						15
90		4			4			5			2		**
								25			65
10		0			0			0			0
								10

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

Обчислимо для цього розподілу сумарні витрати на перевезення товару:

.

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