Проверка сбалансированности запасов и потребностей.

В соответствии с теоремой 6.1 проверяется условие сбалансированности запасов поставщиков и потребностей потребителей.

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

2. Разработка исходного опорного плана методом «минимальной стоимости».

В таблице поставок отыскивается клетка с минимальной стоимостью перевозок:

.

При этом из двух клеток с одинаковой стоимостью перевозок предпочтение отдается клетке, через которую осуществляется больший объем перевозок. Данная клетка заполняется минимальным значением от возможного объема поставок и объема потребностей. В результате либо будут удовлетворены потребности, либо исчерпаны запасы.

Если удовлетворены потребности, то остальные клетки данного столбца вычеркиваются и в последующих распределениях не участвуют.

Если исчерпаны запасы поставщика, то зачеркиваются остальные клетки соответствующей строки, и они не участвуют в последующих распределениях.

Затем из всех незаполненных (незагруженных) клеток находится очередная клетка с минимальной стоимостью, итерации повторяются.

После того, как будет найден опорный план, по нему вычисляют значение целевой функции F(x).

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

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

,

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

,

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

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

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

 

 

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

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

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

Таблица 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.19)

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

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

,

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

Построение контура перераспределения поставок.

Контур перераспределения поставок составляют по следующим правилам:

7.1. Контур представляет собой многоугольник с вершинами в загруженных клетках, за исключением клетки ВМН, и ребрами, пролегающими вдоль строк и колонок таблицы поставок. В каждой строке (колонке) должны быть только по две вершины.

7.2. Вершины контура последовательно поочередно подразделяют на загружаемые «+» и разгружаемые «–», начиная с ВМН.

Построенный контур в соответствии с вышеперечисленными правилами может принимать, к примеру, следующие формы: