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

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

Таблица 6.2

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

Проверка вырожденности опорного плана.

В соответствии с теоремой 6.2 проверяется вырожденность найденного плана. Если опорный план вырожденный, т.е.

, (6.13)

(где N – число заполненных клеток в таблице поставок) тогда вводится k фиктивных поставок:

, (6.14)

т.е. в любых k незаполненных клетках таблицы поставок вписывают нулевые значения проектным параметрам x_ij:

, (6.15)

где S – множество пар индексов (i, j) свободных переменных, соответствующих незаполненным клеткам.

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

, (6.16)

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

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

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

Потребители Поставщики	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

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

, (6.17)

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

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

. (6.18)

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

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

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

, (6.19)

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

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

, (6.20)

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

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