Задача №3

На складах зосереджені запаси продукції у кількості 90, 400, 110 тон відповідно. Споживачіповинні одержати цю продукцію у кількості 140, 300, 160 тон відповідно. Знайти такий варіант закріплення постачальників до споживачів, при якому сума витрат на перевезення була б мінімальною.

Витрати на перевезення однієї тони продукції задано матрицею .

Перевіримо, чи є дана задача закритою.

тон;

тон.

.

Отже, дана транспортна задача є закритою.

Знайдемо вихідний опорний розв’язок методом мінімального тарифу.

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

		140	300	160
	90	2 90	5	2
	400	4	1 300	5 100
	110	3 50	6	8 60

.

Вартість перевезень при вихідному опорному розв’язку складає (грн.).

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

Для вільних клітин знайдемо посередні вартості

Занесемо результати обчислень до таблиці. Знайдемо різниці між тарифами та посередніми вартостями

Оскільки серед є від’ємне значення, то знайдений розв’язок не є оптимальним і його необхідно покращити. Перейдемо до нового базису за допомогою циклу перерахунку. Для цього представимо функцію у вигляді

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

Одержуємо новий план, який представлений у таблиці.

.

Перевіримо новий план на оптимальність. Для цього повторимо повний цикл розрахунків.

	2 90 -Р	5 3	2 7 +Р
	4 0	1 300	5 100
	3 50 +Р	6 4	8 60 -Р

		140	300	160
	90	2 30	5	2 60
	400	4	1 300	5 100
	110	3 100	6	8

Представимо функцію у вигляді

Перейдемо до нового базису

	2 30 -Р	5 -2	2 60 +Р
	4 5+Р	1 300	5 100 -Р
	3 110	6 -1	8 3

		140	300	160
	90	2	5	2 90
	400	4 30	1 300	5 70
	110	3 110	6	8

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