Методы построения опорных решений

 

Метод северо-западного угла.

Начинаем заполнение с клетки (1,1) – С-З угол, либо удовлетворяя потребность, либо исчерпывая запасы в этом пункте. Затем переходим в следующий столбец или строку, что зависит от наличия потребности и запасов, идя как бы по диагонали таблицы заканчиваем заполнение в клетке (m,n), таким образом, будет получено опорное решение.

Метод минимального элемента

Среди всех клеток выбираем клетку с наименьшим тарифом C_ks и начинаем заполнение с этой клетки, либо удовлетворяя потребность, либо исчерпывая запасы (если таких клеток несколько, то заполняем все эти клетки). Затем переходим к заполнению клеток с большими по величине тарифами, пока полностью не исчерпаем запасы или не удовлетворим потребности.

Замечание: Если заполненных клеток оказалось меньше чем m+n-1, то к полученному набору дописывают в некоторых клетках «0», так чтобы общее количество заполненных клеток стало m+n-1.

Алгоритм решения транспортной задачи методом потенциалов.

1. Построить опорное решение транспортной задачи тремя описанными выше методами. Для каждого опорного решения найти значение целевой функции и остановится на том, для которого это значение минимально.

2. Найти потенциалы заполненных клеток.

3. Для незаполненных клеток проверить условие оптимальности. Если условие оптимальности выполняется, то полученное решение оптимально.

4. В противном случае выбирают клетку (k,s), для которой U_k+V_s>C_ks и строим цикл транспортной таблицы, приписывая клетке знак «+» и чередуя знаки во всех остальных клетках цикла.

5. Проводим пересчет таблицы по следующему правилу. Необходимо выбрать число r=min x_ij из цикла со знаком «-». В клетках цикла, помеченных знаком «+», это число прибавляем. В клетках цикла, помеченных знаком «-», это число отнимаем. Остальные клетки цикла не изменяем и ту клетку, в которой было найдено r, не заполняем.

6. Возвращаемся к пункту 2.

Пример:

Составим опорное решение методом С-З угла:

	B1	B2	B3	B4	Потребности
A1	270 1	140 4	100 7
A2			90 8
A3			10 4	110 8
Запасы

 

ƒ(α₁)=270+560+700+720+40+880=3170

Составим опорное решение методом минимального элемента

 

	B1	B2	B3	B4	Потребности
A1	270 1	20 4	110 7	110 3
A2			90 8
A3		120 2
Запасы

ƒ(α₂)=270+80+770+330+720+240=2410

Поскольку, пока минимальные затраты получились при α₂ начинаем реализацию метода потенциалов с этого опорного решения.

	B1	B2	B3	B4	Потребности	Ui
A1	270 1	+ -     - +   20 4	110 7	110 3
A2			90 8
A3		120 2				-2
Запасы
Vj

Условие оптимальности не выполняется в клетке (3;3). Производим пересчет.

 

	B1	B2	B3	B4	Потребности	Ui
A1	270 1	130 4		110 3
A2			90 8
A3		10 2	110 4			-2
Запасы
Vj