Число свободных клеток с нулевыми перевозками

(m–1)(n–1) = 3*4 = 12,

Так что найденный план – опорный.

Заполненные клетки будем называть базисными, а пустые – свободными.

Является ли найденный план оптимальным? Скорее всего, нет, так как при его составлении стоимости перевозок никак не учитывались. Стоимость плана определится как сумма произведений перевозок, стоящих в базисных клетках, на стоимость перевозки.

2.6.3. Нахождение оптимального решения

Улучшить план перевозок можно, произведя в нем "циклическую перестановку".

Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на ± 90°.

Условимся отмечать знаком "+" те вершины цикла, в которых перевозки увеличиваются и знаком "–" – те вершины, в которых они уменьшаются. Цикл с отмеченными вершинами называется означенным (табл. 7). В цикле знаки вершин должны чередоваться.

Таблица 7

ПО	ПН				Запас a_i
ПО	В ₁	В ₂	. . .	В _n	Запас a_i
А ₁	c₁₁	c₁₁	. . .	c_1n	a₁
А ₂	c₂₁ ₊	c₂₂ _–	. . .	c_2n	a₂
. . .	. . .	. . .	. . .	. . .
А_m	c_m1 _–	c_m2 ₊	. . .	c_mn	a_m
Заявки b_j	b₁	b₂	. . .	b_n	å b_j = å a_i

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

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

Цена цикла g – это увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, т.е. стоимости в положительных вершинах берутся со знаком "+", стоимости в отрицательных вершинах – со знаком "–".Например, для цикла, выделенного в табл. 7, цена определится так:

g = С₂₁ – С_m₁ + С_m₂ – С₂₂. (2.41)

При перемещении единицы груза по циклу стоимость перевозок изменяется на g . Если перевозим k единиц груза, то стоимость изменяется на k g. Для улучшения плана имеет смысл перемещать перевозки по тем циклам, цена которых отрицательна, значит, стоимость всего плана будет уменьшаться на k g.

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

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

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

Сделаем замечание относительно вырожденного случая.

Вырожденный случай – случай, когда в ноль обращается больше, чем k переменных. Применительно к транспортной таблице это будет выражаться в том, что будет заполнено меньше чем ( m + n – 1) клеток.

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

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

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

2.6.4. Транспортная задача с неправильным балансом

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

å a_i ¹ å b _j . (2.42)

Нарушение баланса возможно в двух направлениях:

1. Сумма запасов превышает сумму заявок

å a_i ³ å b _j . (2.43)

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

Задача может быть сведена к транспортной задаче с правильным балансом, если ввести в рассмотрение некий "фиктивный" пункт назначения В_ф, условно приписав ему заявку, равную избытку запасов над заявками:

b_ф = å a_i – å b _j . (2.44)

Тогда задача сводится к задаче с правильным балансом

Стоимости перевозок из всех пунктов отправления A в этот "фиктивный" пункт назначения B_ф полагают равными нулю. Поэтому для любого пункта отправления стоимость C _i _ф = 0.

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

При этом нужно иметь в виду, что все перевозки x_iф, стоящие в правом столбце, фактически никуда не отправляются, а остаются на пунктах отправления A.

2. Сумма заявок превышает сумму запасов

å a_i £ å b _j . (2.45)

В этом случае задача называется транспортной задачей с избытком заявок.

Для решения задачи можно тем или другим способом "срезать" заявки и снова получить транспортную задачу с правильным балансом. Если нас совершенно не интересует, насколько "справедливо" удовлетворяются заявки, а важно только "подешевле развезти" имеющиеся запасы (все равно, куда), то можно ввести в рассмотрение фиктивный пункт отправления A_ф, условно приписав ему недостающий запас, равный

a _ф = å b _j – å a_i (2.46)

Стоимости перевозок из этого "фиктивного" пункта отправления A_ф во все пункты назначения полагают равными нулю. Поэтому для любого пункта назначения стоимость C_ф _j = 0.

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

k = å a_i / å b _j , (2.47)

Тогда получим транспортную задачу с правильным балансом.

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

Дата добавления: 2019-02-12; просмотров: 251; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 456 Следующая ⇒

Мы поможем в написании ваших работ!