Расчет потенциалов.

Расчет потенциалов выполняют по загруженным клеткам таблицы поставок, для которых:

, (6.16)

где α_i, β_j – потенциал i -ой строки и j -ой колонки соответственно.

Для первой строки принимают α ₁=0, затем остальные потенциалы рассчитывают по загруженным клеткам в соответствии с выражением (6.14).

Результаты расчетов заносят в таблицу поставок.

Таблица 6.2

Таблица поставок

Потребители Поставщики	B1	B2	…	Bn	Запасы поставщиков	αi
A1	c11 x11	c12 x12	…	c1n x1n	a1	α1
A2	c21 x21	c22 x22	…	c2n x2n	a2	α2
			…
Am	cm1 xm1	cm2 xm2	…	cmn xmn	am	αm
Потребности потребителей	b1	b2	…	bn
βj	β1	β2	…	βn

 

5. Проверка плана на оптимальность.

Проверка опорного плана на оптимальность осуществляется по незагруженным клеткам. Если для всех незагруженных клеток выполняется условие:

, (6.17)

то найденный опорный план является оптимальным.

Оптимальное решение будет единственным, если для всех незагруженных клеток выполняется условие:

. (6.18)

Если для какой-либо незагруженной клетки условие (6.15) не выполняется, то опорный план не является оптимальным и переходят к следующему этапу.

 

6. Поиск «вершины максимальной неоптимальности» (ВМН).

По незагруженным клеткам, для которых условие (6.15) не выполняется, рассчитывают оценки:

, (6.19)

где – множество пар индексов (i, j), соответствующих незаполненным клеткам, для которых не выполняется условие оптимальности (6.15). Данные оценки характеризуют размер экономии транспортных издержек на 1 ед. перевозимого груза.

Среди полученных оценок находят наибольшую, т.е.:

, (6.20)

которая соответствует ВМН. Клетку, соответствующую ВМН, в таблице поставок помечают «+».