Проверка небазисных клеток на соответствие их условию оптимальности.

Оптимальный план транспортной задачи должен отвечать критерию оптимальности, который выражается в том, соответствуют ли небазисные клетки матрицы условию, формулируемому следующим выражением:

. Если это условие для всех небазисных клеток выполняется, то план является оптимальным, а если нет, хотя бы для одной клетки, то план не оптимален. Иначе говоря, существует некоторый план с меньшим функционалом. Разность потенциалов может интерпретироваться как некоторая условная цена перевозки единицы продукции по маршруту, связывающему соответствующие станции «i» и «j». Если она ниже c_ij, значит, использование данного маршрута не улучшит план, а если c_ij ниже разности потенциалов, т. е. условие не выполняется, следовательно, существует план лучше рассчитанного, который необходимо отыскать.

3. Улучшение плана.

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

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

Улучшение плана осуществляется по одной из небазисных клеток, для которой условие оптимальности оказалось невыполненным. В нашем плане имеется четыре такие клетки. Выбираем одну из них, для которой условие оптимальности не выполняется в наибольшей степени.

 

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

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

Знаком «+» отмечаются те вершины цикла, в которых перевозки увеличиваются, а знаком «-» – те вершины, в которых они уменьшаются. Перенести какое-то количество единиц груза по циклу – это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах – уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется. При любом циклическом переносе, оставляющем перевозки неотрицательными, допустимый план остается допустимым. Стоимость же этого плана может меняться – увеличиваться или уменьшаться.

Цена цикла – увеличение стоимости перевозок при перемещении одной единицы груза по циклу. Цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла. Стоимости, стоящие в положительных вершинах, берутся со знаком «+», а в отрицательных – со знаком «–».

 

 

Основные классы задач, сводящиеся в транспортным.

Многопродуктовая транспортная модель.

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

К типов груза, для каждого типа груза заданы тарифы перевозок.

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

Чтобы свести многопродуктовую ТЗ к стандартной транспортной модели, будем рассматривать каждый пункт отправления A_i (i=1,2,..m), как К пунктов отправления A_i ^h , (h=1,2,..К), и каждый пункт назначения B_j (j=1,2,..n) как К пунктов назначения B_j ^h.

Верхний индекс h соответствует типу груза.

Получили m*К – пунктов отправления и n*К – пунктов назначения. Если между пунктами A_i ^h и B_j ^h

груз не перевозится, то этим перевозкам присваивается очень большая стоимость M.

Пример. Даны m =4 пункта отправления A_i (i=1,..4),

в которых содержится до К=3 типов груза, отправляемых в n=2 пункта назначения B_j (j=1,2)

Запасы: а₁ ¹=200, а₁ ³=150, а₂ ¹=75, а₂ ²=100, а₂ ³=50, а₃ ¹=50, а₃ ²=100, а₄ ¹=40, а₄ ²=30, а₄ ³=50.

ЗаявкиЖи₁ ¹=250б и₁ ²=130б и₁ ³=150б и₂ ¹=115б и₂ ²=100б и₂ ³=100

 

Транспортная модель с промежуточными пунктами.

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

1) Промежуточные пункты – только пункты отправления и назначения, т.е. груз можно перевозить через любой другой пункт отправления или назначения, пока груз не будет доставлен по назначению.

2) Промежуточными пунктами являются только дополнительные пункты.

3) Промежуточными пунктами являются как дополнительные пункты, так и пункты отправления и назначения.

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: