Цикл перерахунку

Цикл транспортної таблиці – це замкнена ламана, що задовольняє умовам:

1. ламана починається і закінчується у вільній клітинці, в якій не виконана умова оптимальності,[1]

2. ланки ламаної повертають[2] тільки під прямим кутом,

3. поворот може бути тільки у базисній клітинці

Приклади циклів

Перерахунок по циклу:

1. вільній клітині циклу присвоюють знак “+”;

2. при повороті знаки чергуються;

3. серед клітин зі знаком “–” обирають найменше значення поставки ;

4. з поставок в клітинах зі знаком “–” віднімають , а до поставок в клітинах зі знаком “+” додають .

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

Намалюємо цикл перерахунку для приклада 12.

aі	bj
	^5	300–^1	+^2	^3
	^6	^3	^7	200^1
	^4	^5	300^3	200^2
	230^2	120+^4	350–^6	^8

З клітинок зі знаком мінус віднімаємо найменше число , а в клітинки зі знаком плюс його додаємо:

aі	bj
	^5	^1	300^2	^3
	^6	^3	^7	200^1
	^4	^5	300^3	200^2
	230^2	420^4	50^6	^8

Отриманий план перевіряємо на оптимальність за методом потенціалів.

aі	bj
		^5	^1	300^2	^3
		^6	^3	^7	200^1
		^4	^5	300^3	200^2
		230^2	420^4	50^6	^8

Звідки для знайдемо , , , , , , .

Умови оптимальності виконані, план оптимальний.

Обчислимо вартість перевезення.

Відповідь: , .

[1] Якщо таких клітинок декілька, обирають з найбільшою різницею.

[2] Напрямок ланок неважливий.

Дата добавления: 2014-12-25