Поиск оптимального решения

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

Гл. 13. Транспортная задача и задача о назначениях _____ 475

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

2. Построение для этой клетки ступенчатого цикла аналогично описанному выше.

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

А. Нет никаких гарантий, что в полученном распределении нельзя предпринять никаких улучшений. Поэтому новое решение необходимо проверить на опти­мальность с использованием метода МОДИ. Утверждать, что найденная стои­мость транспортировки является минимальной, можно только в том случае, если все теневые цены положительны или равны нулю.

Продолжение примера 13.4. Единственной клеткой с отрицательным значением теневой цены, равным - 2 ф. ст., является клетка (R, фиктивный). В эту клетку желательно разместить максимально возможное количество изделий.

Ниже приведен ступенчатый цикл для клетки (R, фиктивный), которая имеет значение теневой цены, равное - 2 ф. ст., а также исходное распределение перевозок и единичные издержки.

Таблица 13.15. Ступенчатый цикл для (R, фиктивный)

С Фиктивный

+ 5 2
7 4	+ 0

Знак "+" означает увеличение количества перевозимых изделий в данной клетке; знак "-" — уменьшение соответствующего количества изделий.

Клетки со знаком "-" — это клетки (R, фиктивный) и (R.C), объем перево­зок в которых равен 7 и 4 изделиям соответственно. Минимальным значением для клеток, отмеченных знаком "-", является 4, что означает, что внутри цикла можно осуществлять перемещение четырех изделий, добавляя их в клетки со знаком "+" и вычитая из клеток со знаком "-". Общая экономия стоимости транспортировки составит в данном случае (2 х 4) = 8 ф. ст. Изменения, внесенные в транспортную таблицу, отражены в табл. 13.16.

Ч. 4. Моделирование в бизнесе

	Таблица	13.16.	Перераспределение перевовок
Торговый склад	Розничный магазин	Общее предло­жение
А	В	С	фиктивный
Р Q R
				2 + 4	7 -	-4
								4-
:	J			4-	-4	0+4
Общая потребность

Данное решение по-прежнему является базисным, так как число заполненных клеток равно 6. Проверим данное решение на оптимальность с использованием метода МОДИ. Обратившись к заполненным клеткам (Р,С), (Р, фиктивный), (Q,B), (R,A), (R,B) и (R,-фиктивный), получим:

v3 =	5;
v4 =	0;
u3 =	0;
V, =	1;
v2 =

= 5 = 0 = 0 = 1 = 20 = 10

с13 с14.с34 с31 с32 с22

^{= U}1 ^{+ v}3 Положим и₍ = 0, тогда - и, + v₄ = u₃ + v₄ = u₃

1u3 +v2 U2 +v2

+ V

u₂ = -10. Таким образом, теневые цены соответствующие пустым клеткам, будут равны:

Si2 S21 ^s23 S24 S33

= 10 = 20 = 2 = 8 = 0 = 7

- (u, + v.); -(0+1) = -(0+20) = -(-10+1) =

- (-10 + 5) =

- (-10 + 0) =

- (0 + 5) =

+ 9 0; +11 +13 +10 + 2

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

Минимальная стоимость равна:

101 + (4 х (- 2)) = 93 ф. ст.

Гл. 13. Транспортная задача и задача о назначениях

Таблица 13.17. Проверка распределения перевозок на оптимальность с использованием метода МОДИ

I Торговый		Розничный магазин		Обцее "]
I склад	А	В	С	Фиктивный	предложение 1
	G	,0	©	Li,	.		9 и, = 0
Р R	г	i
				i 1 8			4 iii = -10
£	$		©	©
				1-ч ©		8 1и = 0
:
Общая потребность
	V, = 1	v, = 20	v,= 5	v< = 0

три

Решение. • Шесть изделий перевозятся со склада Р в розничный магазин С,

изделия остаются на складе Р.

• Четыре изделия перевозятся со склада Q в магазин В.

• Со склада R перевозятся три изделия в магазин А, одно —в магазин В, а четыре изделия остаются на складе.

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

Следует отметить, что минимальная стоимость была достигнута еще в исходном распределении перевозок, полученном методом Вогеля. Такая ситуация в задачах небольшой размерности бывает довольно часто. Обычно метод Вогеля позволяет получить наилучшее начальное решение, однако нет никаких гаршггий, что примене­ние этого метода сразу обеспечивает получение оптимального решения. Следует также отметить, что распределение перевозок, полученное методом Вогеля, несколько отличается от распределения, найденного выше (см. пример 13.2). Данная задача имеет альтернативное оптимальное решение:

• Со склада Р одно изделие вывозятся в магазин В, шесть — в магазин С, а два — остаются на складе;

• Со склада Q четыре изделия вывозится в магазин В;

• Со склада R три изделия вывозятся в магазин А, а пять остаются на складе.
О существовании альтернативного оптимального решения говорит и нулевое

значение теневой цены, соответствующей клетке (Р,В). Нулевые значения теневых

Ч. 4. Моделирование в бизнесе

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