d9e5a92d

Применение метода МОДИ для проверки

Проверка пустой клетки (R, Ф)


Изменение натурального объема, изделий

Р Клетка, подвергнутая проверке + 1 Заполненная клетка - 1
R Заполненная клетка Заполненная клетка
- 1 + 1

Проверка пустой клетки (R, Ф)


Стоимостные изменения, у.е.
С Ф
Р Клетка, подвергнутая проверке Заполненная клетка
+ 5 - 0
R Заполненная клетка Заполненная клетка
- 7 + 0

Стоимостные изменения от дополнения одного изделия в клетку (R, Ф) составили - 2 у.е. за одно изделие.
Размещение перевозок в клетке (R, Ф) дает возможность снизить издержки транспортировки, следовательно, начальное распределение перевозок оптимальным не является. Используя клетку (R, Ф) и указанный ступенчатый маршрут, можно найти более дешевое решение, позволяющее сэкономить 2 у.е. за каждую единицу изделия, перемещаемого в данную клетку.

Однако проверку пустых клеток необходимо завершить, поскольку могут существовать клетки, использование которых позволяет получить еще большую экономию.
Теперь построим ступенчатый путь для пустой клетки (Q, Ф). Необходимо учитывать, что для последующего осуществления балансировки движение можно осуществлять только через заполненные клетки.

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

В клетку (Q, Ф) поместим одно изделие. Строка Q и фиктивный столбец содержат только по одной заполненной клетке.

Предположим, что мы приняли решение двигаться из (Q, Ф) в (Q, В). Для того, чтобы сбалансировать строку Q,
из этой клетки вычтем одно изделие. Восстановить баланс для столбца В можно только с помощью клетки (R, В), следовательно, в нее необходимо добавить одно изделие. Балансировку строки R можно осуществить через клетки (R, А) и (R, С), но поскольку (R, А) - единственная заполненная клетка в столбце А, ее использовать нельзя. Если бы маршрут проходил через данную клетку, мы не могли бы сбалансировать столбец А. Объем перевозок в (R, С) уменьшается на одно изделие.

Оставшаяся часть маршрута очевидна. Восстановление баланса в столбце С производится увеличением перевозок в (Р, С) на одну единицу, а баланс строки Р достигается вычитанием одного изделия из (Р, Ф). Последний шаг позволяет также сбалансировать фиктивный столбец и замкнуть цикл.

Следует помнить, что построение замкнутого цикла внутри транспортной таблицы, который начинается и заканчивается в выбранной пустой точке, возможно только в том случае, если исходное распределение перевозок является базисным. Натуральные и стоимостные изменения, соответствующие построенному циклу, показаны в таблицах.
Чистый стоимостной эффект от размещения в пустой клетке (Q, Ф) составит + 8 у.е. за изделие. В случае заполнения данной пустой клетки общая стоимость транспортировки увеличится. Поэтому рассмотренные изменения вводить не следует.

В таблице показаны значения теневых цен.

Проверка пустой клетки (Q, Ф)


Натуральные изменения, изделий
В C ф
Р ПУСТАЯ Заполненная + 1 Заполненная - 1
Q Заполненная ПУСТА Проверяемая + 1
- 1
Я
Я
R Заполненная + 1 Заполненная - 1 Пустая

Проверка пустой клетки (Q, Ф)


Стоимостные изменения, изделий

В C Ф
Р Пустая Заполненная + 1 Заполненная - 0
Q Заполненная - 10 ПУСТА - Проверяемая + 0
_~_
Я
R Заполненная + 20 Заполненная - 7 ПУСТА
Я


2.17П Начальное распределение перевозок на оптимальность - метод ступенек
Постав- Транспортные издержки для магазинов, у.е. Общий объем
щик А В С Ф предложения
Р ? 10 20 2 ІА 7 La 9
Q 2 45 10 4
R 3 1 1 20 4 Ll 8
Общий
объем
3 5 6 7 21
спроса
Ключ:


В ней можно выделить компоненту и3, соответствующую строке, и компоненту v2, соответствующую столбцу.
Теневые цены для каждой пустой (небазисной) клетки можно найти из соотношения:
Sj = Cj - ( иi + Vj).
Эта теневая цена означает дополнительную стоимость транспортировки единицы изделия из пункта i в пункт j. Если все теневые цены положительны или равны нулю, то есть Sj 0, то полученное решение является оптимальным. В этом случае перемещение единицы изделия в пустую клетку, которой соответствует положительная теневая цена, увеличит стоимость транспортировки. Если теневая цена имеет нулевое значение, то общая стоимость транспортировки не изменится.
Обратимся вновь к начальному распределению перевозок, полученному методом минимальной стоимости. Проведем проверку данного распределения на оптимальность с помощью метода МОДИ.

Начальное распределение перевозок, полученое методом минимальной стоимости

Поставщик Транспортные издержки для магазинов, у.е. Общий объем предложения
А В С Ф
Р 10 20 5
2
7 0 9
Q 2 10
4 1
8 0 4
R 3 Li- 1 20 4 LI 0 8
Общий
объем
спроса
3 5 6 7 21
Ключ:
= 5 = u1 + v3 с14 = 0 = u1 + v4
С33 = 7 = U3 + V3
с31 = 1 = u3 + v1
С32 = 20 = U3 + V2 С22 = 10 = U2 + V2


для заполненной клетки (Р, С); для заполненной клетки (Р, Ф); для заполненной клетки (R, С); для заполненной клетки (R, A); для заполненной клетки (R, B); для заполненной клетки (Q, B).
Какой-либо из компонент присваивается некоторое значение, по которому из соответствующих уравнений рассчитываются значения остальных компонент. Положим, u1 = 0. Из этого следует, что v3 = 5, v4 = 0, v1 = - 1, v2 = 18, u3 = 2, u2 = - 8. Теперь, пользуясь соотношением Sj = Cj - (ui + v}-), мы можем найти значения теневых цен, соответствующих незаполненным клеткам.
Подставив найденные значения компонент ui и vj, получим следующие теневые цены:
s 11 = 10 - (0 - (-1)) = + 11 S12 = 20 - (0 + 18) = + 2 S21 = 2 - (- 8 - 1) = + 11
523 = 8 - (- 8 + 5) = + 11
524 = 0 - (- 8 + 0) = + 8
S34 = 0 - (2 + 0) = - 2
для пустой клетки (Р, А); для пустой клетки (Р, В); для пустой клетки (Q, А); для пустой клетки (Q, С); для пустой клетки (Q, Ф); для пустой клетки (R, Ф).
Эти значения заносятся в транспортную таблицу.
Теневые цены совпадают со значениями, найденными методом ступенек. Маршрут (R, Ф) имеет отрицательную теневую цену, следовательно, полученное решение является неоптимальным. Необходимо осуществить перераспределение перевозимых изделий с использованием указанной клетки и соответствующего ей ступенчатого цикла, что позволит снизит стоимость транспортировки.

Применение метода МОДИ для проверки


на оптимальность начального распределения перевозок
Постав
щик
Транспортные издержки для магазинов, у.е. Общий объем предложения
А В С Ф
Р (+И 10 20
(+8) L-I
2 Ш 7 Н 9 u1 0
Q СП 2 „ 10 45 - да да 4 и
і
00
R 1
3 -
20
1 -
4 Ш да 8 U3 2
Общий
объем
спроса
3 5 6 7 21
?і = - 1
II
00
J?
II
ил
о
и
^і-

ПОИСК ОПТИМАЛЬНОГО РЕШЕНИЯ


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

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

Утверждать, что найденная стоимость транспортировки является минимальной, можно только в том случае, если все теневые цены положительны или равны нулю.
Единственной клеткой с отрицательным значением теневой цены, равным - 2 у.е., является клетка (R, Ф). В эту клетку желательно разместить максимально возможное количество изделий.
Ниже приведен ступенчатый цикл для клетки (R, Ф), а также исходное распределение перевозок и единичные издержки.
2.20П Ступенчатый цикл для клетки (R, Ф)

С Ф
+ 5 - 0
Р 2 7
- 7 + 0
R 4 ?

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

Изменения, внесенные в транспортную таблицу, отражены в таблице.

2.21П Перераспределение перевозок
Постав
щик
Транспортные издержки для магазинов, у.е. Общий объем предложения
А В С Ф
Р - 10 - 20 2 + 4 5 7 - 4 0 9
Q - 2 4 10 - 8 - 0 4
R 3 1 1 20 4 - 4 7 0 + 4 0 8
Общий
объем
спроса
3 5 6 7 21
Данное решение по-прежнему является базисным, так как число заполненных клеток равно 6. Проверим данное решение на оптимальность с использованием метода МОДИ. Обратившись к заполненным клеткам (Р, С), (Р, Ф), (Q, В), (R, А), (R, В) и (R, Ф), получим:
с13 = 5 = u1 + ?3 Положим, и = 0, тогда ?3 = 5 с32 = 20 = u3 + ?2 u3 = 0
с22 = 10 = u2 + ?2 u2 = - 10
Таким образом, теневые цены, соответствующие пустым клеткам, будут равны:
Sj = Cij - (u + ?} )
s„ = 10 - (0 +1) = + 9 S12 = 20 - (0 + 20) = 0 S21 = 2 - (-10 + 1) = + 11
523 = 8 - (- 10 + 5) = + 13
524 = 0 - (- 10 + 0) = + 10 S33 = 7 - ( 0 + 5) = + 2
Поскольку ни одно из значений теневых цен не отрицательно, полученное решение является оптимальным. Минимальная стоимость равна:
101 + (4 х (-2)) = 93 у.е.
2.22П Применение метода МОДИ для проверки на оптимальность распределения перевозок
Поставщ
ик
Транспортные издержки для магазинов, у.е. Общий объем предложения
А В С Ф
Р ,+ 10 0 20 6 5 3 0 9 щ = 0
Q ш 45 10 8 0 4 К
II
1
о
R 3 1 1 20 7 4 0 8 и3 = 0
Общий
объем
спроса
3 5 6 7 21
?і = 1 ?2 = 20 J?
II
С/і
О
II

Решение.
- Шесть изделий перевозятся со склада Р в розничный магазин С, три изделия остаются на складе Р;
- четыре изделия перевозятся со склада Q в магазин В;
- со склада R перевозятся три изделия в магазин А, одно - в магазин В, а четыре изделия остаются на складе.
В случае если и повторное распределение перевозок не является оптимальным, процедуру перераспределения повторяют необходимое число раз.
Следует отметить, что минимальная стоимость была достигнута еще в исходном распределении перевозок, полученном методом Вогеля. Такая ситуация в задачах небольшой размерности бывает довольно часто.

Обычно метод Вогеля позволяет получить наилучшее начальное решение, однако нет никаких гарантий, что применение этого метода сразу обеспечивает получение оптимального решения. Следует также отметить, что распределение перевозок, полученное методом Вогеля, несколько отличается от распределения, найденного выше. Данная задача имеет альтернативное оптимальное решение:
- со склада Р одно изделие вывозится в магазин В, шесть - в магазин С, а два - остаются на складе;
- со склада Q четыре изделия вывозятся в магазин В;
- со склада R три изделия вывозятся в магазин А, а пять остаются на складе.
О существовании альтернативного оптимального решения говорит и нулевое значение теневой цены, соответствующей клетке (Р, В). Нулевые значения теневых цен всегда связаны с существованием альтернативных оптимальных распределений перевозок, которым соответствует одно значение общей стоимости транспортировки.

АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ


Итоговое распределение перевозок, а также значения теневых цен, соответствующие пустым клеткам, можно использовать при проведения анализа модели на чувствительность. Теневая цена показывает, на сколько увеличится общая стоимость, если в пустую клетку поместить одну единицу продукта. Если нам придется осуществить перевозку одного изделия с торгового склада Q в розничный магазин С, увеличение стоимости составит 13 у.е., что гораздо выше, чем
стоимость самого маршрута, равная 8 у.е. Дополнительное увеличение стоимости появляется в связи с перебалансировкой распределения перевозок, при которой применяется ниже следующий ступенчатый цикл.
2.23П Ступенчатый цикл для (Q, С)
Натуральные изменения, изделий

Р
Q
R
Пустая Заполненная - 1 Заполненная + 1
Заполненн - 1 ая Проверяемая - + 1 Пустая
Заполненная + 1 Пустая Заполненная - 1

2.24П Проверка пустой клетки (Q, Ф)

Натуральные изменения, изделий
В C Ф
Р
Q
R
Пустая Заполненная - 5 Заполненная + 0
Заполнены - 10 ая Проверяемая - + 8 Пустая
+8
Заполненная + 20 Пустая Заполненная - 0
Чистые изменения стоимости составят 13 у.е. за изделие. Максимальное количество изделий, которое можно перемещать внутри цикла, - это минимальное из значений, стоящих в клетках со знаком -, то есть (Р, С) = 5, (R, Ф) = 4 и (Q, В) = 4.
Следовательно, максимальное количество изделий, подлежащее перемещению, равно 4.
О нулевом значении теневой цены в клетке (Р, В) уже упоминалось. Ступенчатый цикл для данной пустой клетки имеет вид, указанный в таблице.
2.25П Ступенчатый цикл для (Р, В)
Изменение натурального объема, изделий
А С
Р Клетка, подвергнутая проверке Заполненная клетка
+ 1 1 _ - 1
R Заполненная клетка Заполненная клетка
- 1 + 1
2.26П Ступенчатый цикл для (Р, В)
Изменение натурального объема, изделий
А С
Р Клетка, подвергнутая проверке Заполненная клетка
+ 20 - 0
R Заполненная клетка Заполненная клетка
- 20 + 0
Можно поместить некоторое число изделий в клетку (Р, В), причем чистый стоимостной эффект будет равен нулю. Это означает, что существует альтернативное распределение перевозок, которое также позволяет получить минимальную стоимость в 93 у.е. Максимальное количество изделий, которое можно добавить в клетку (Р, В), -это минимум из значений, указанных в клетке со знаком - : (R, B) = 1 и (Р, Ф) = 3. Следовательно, только одно изделие можно, перемещая по циклу, поместить в клетку (Р, В).
Теневые цены можно использовать также в качестве индикаторов изменения стоимости транспортировки, соответствующей пустой клетке, которые оказывают воздействие на оптимальное распределение перевозок. Например, теневая цена пустой клетки (R, С) равна 2 у.е., а фактическая стоимость транспортировки - 7 у.е. за одно изделие. Следовательно, для того, чтобы использование данной клетки в распределении перевозок привело к снижению общей стоимости транспортировки, фактическую единичную стоимость, соответствующую этой клетке, необходимо снизить как минимум до (7 - 2) = 5 у.е.
Действие стоимостных изменений в заполненных клетках выявить гораздо сложнее. При снижении издержек увеличение числа изделий в данной клетке выгодно. Если же издержки, стоящие в заполненных клетках, возрастают, то при достижении ими определенного значения использование этой клетки является нежелательным, и необходимо осуществить переход к другому маршруту.
Рассмотрим заполненную клетку (Р, С). Соответствующая ей фактическая стоимость перевозок составляет 5 у.е. за изделие. Уменьшение этой стоимости не повлияет на объем перевозок, поскольку количество изделий, указанное в данной клетке, удовлетворяет всю потребность магазина С.
Если стоимость перевозки становится больше 5 у.е., то следует обратить внимание на ступенчатые циклы, в которых задействована клетка (Р, С). Эти циклы дают значения теневых цен: 13 у.е. для (Q, С) и 2 у.е. для (R, С). В обоих циклах клетка (Р, С) помечена знаком -, и любое увеличение стоимости на 5 у.е. повлечет за собой сужение теневых цен указанных пустых клеток. Изменение натурального объема перевозок будет иметь место в случае, если единичная стоимость транспортировки для клетки (Р, С) возрастет более, чем на 2 у.е. и превысит 8 у.е. При этом теневая цена клетки (R, C) станет отрицательной. В данной ситуации использование пустой клетки (R, С) окажется выгодным, что приведет к изменению объема перевозок для (Р, С).
Таким образом, для полученного оптимального распределения перевозок верхним пределом стоимости, соответствующей (Р, С), является значение 7 у.е., а нижним пределом - 0. Внутри указанного промежутка происходит изменение лишь общей стоимости транспортировки, тогда как в натуральном выражении распределение перевозок не меняется.

НЕДОПУСТИМЫЕ ПЕРЕВОЗКИ


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

Таким образом, алгоритм автоматически позволит избежать перевозок через данную клетку.
З а д а ч а 2.4
Ниже показано применение алгоритма решения транспортной задачи в решении проблем, связанных с недопустимостью прямых перевозок товаров из пунктов производства в пункты назначения. Рассматривается движение продукта во времени.

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

2.27П Значения спроса на продукцию и возможные объемы перевозок
Месяц Производственные мощности, изделий Спрос, изделий
1 300 300
2 350 275
3 325 400
4 375 300
К началу первого месяца имеется начальный запас изделий объемом 50 шт. Если спрос на изделия в течение месяца не удовлетворяется полностью, то прибыль от услуг по перевозке теряется. Издержки на перевозку составляют 100 у.е. за единицу изделия. Стоимость хранения запасов - 2 у.е. за единицу изделия. Каков оптимальный план перевозок?
Решение.
Данную ситуацию можно формализовать, используя транспортную табл. 2.28П, в которой строками является начальный запас и пополнение запаса за месяц, а столбцы отражают ежемесячный спрос на продукцию. Маршруты (клетки), в которых подразумевается удовлетворение спроса за текущий месяц в следующих месяцах, считаются недопустимыми. В таблице этим клеткам соответствуют клетки с символом х.
2.28П Данные плана перевозок для месяцев 1 - 4
Стоимость перевозки единицы изделия, у.е. Общее
предложе
ние
Месяцы
М1 М2 М3 М4
Запас М1 2 4 6 8 50
100 102 104 106 300
Произв
одство
М2 X 100 102 104 350
М3 X X 100 102 325
М4 X X X 100 375
Общая
потребность
300 275 400 300

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

ВЫРОЖДЕННОСТЬ


Решение называется вырожденным, если число перевозок в транспортной таблице меньше, чем (m + n - 1). Данную проблему можно разрешить, проставив в независимые клетки очень маленькие, по сути равные нулю, объемы перевозок. Число перевозок увеличивается таким образом до (m + n - 1).

Выявить клетки, которые следует использовать для этой цели, поможет алгоритм метода МОДИ проверки решения на оптимальность.
З а д а ч а 2.5
Три торговых склада (С1, С2 и С3) могут осуществлять поставки 6, 3 и 4 единиц продукта в три магазина (М1, M2, М3), спрос которых равен 4, 5 и 1 единицам соответственно. Значения единичной стоимости транспортировки указаны в приведенной ниже таблице.
2.29П Исходная информация

Торговый склад Стоимость перевозки единицы изделия, у. е. Общее
предложение
М1 М2 М3
С1 6 4 9 6
С2 5 3 2 3
С3 2 3 6 4
Общая потребность 4 5 1

Как следует распределить перевозки, чтобы общая стоимость транспортировки была минимальной?
Решение.
Общее предложение составляет 13 единиц, что превышает общую потребность в 10 единиц, поэтому в задачу вводится фиктивный магазин, потребность которого в продукции балансирует излишек предложения торговых складов. Чтобы найти начальное распределение перевозок, применим метод Вогеля.
Значение стоимости транспортировки составит 28 у.е. Для того, чтобы решение являлось базисным, оно
должно включать (3 + 4 - 1) = 6 переменных, тогда как в нашей задаче число перевозок равно лишь пяти.
Найденное решение является вырожденным. Поступая в соответствии с алгоритмом метода МОДИ, мы должны ввести нулевую перевозку, чтобы использовать в качестве заполненной одну из пустых клеток. Этот прием позволяет получить требуемое число перевозок, равное шести.

Затем можно будет рассчитать значения всех компонент и и ?, следовательно, и теневые цены.
Реализацию алгоритма метода МОДИ мы начнем, используя пять заполненных клеток, соответствующих начальному распределению перевозок. Дополнительная нулевая перевозка будет введена только тогда, когда без нее продолжение алгоритма будет невозможно.

Обратимся к таблице.
2.30П Начальное распределение перевозок, полученное методом Вогеля

Торговый
склад
Розничный магазин Общий
объем
Штрафная
стоимость
М1 М2 М3 Ф предлож
ения
1 2 3
С1 - 6 3 4 - 9 31 0 630 41 2 2
С2 - 5 2 3 12 2 - 0 320 2 1 2
С3 43 2 - 3 - 6 0 0 40 2 1 1
Общая
потребно
сть
4
0
5
0
1
0
3
0
13
1-й
штраф
1 101 2 0
2-й
штраф
92 0 2 0
3-й
штраф
- 0 2 0

Заполненные клетки используются для расчета соответствующих компонент по строкам и столбцам из соотношения: Cj = и, + Vj при условии, что и, = 0. Значения v2 , v4 , v3 , u2 , не испытывая никаких
затруднений, однако значения и3 и v1 рассчитать нельзя. Для этого необходимо иметь дополнительную заполненную клетку.

Применение метода МОДИ для проверки на оптимальность вырожденного решения


Торго
вый
склад
Розничный магазин Общий
объем
предложения
М1 М2 М3 Ф
С1 ^ 4
3
(+6^ 3 Ш 6 ui = 0
С2 ^ 2 Li 1 Ll та 3 U2 = - 1
С3 3 LL ^ о0 6 U3 = 3
Общая
потребн
ость
4 5 1 3 13
V1 = - 1 V2 = 4 v3 = 3 v4 = 0

Нулевую перевозку нужно поместить в пустую клетку столбца v1 или строки и3. Какая из этих клеток будет выбрана, значения не имеет.

Пусть выбрана клетка (С3, М3). Теперь можно завершить алгоритм и найти значения теневых цен для пустых клеток из соотношения Sj = Cj - (и, + Vj). Соответствующие величины приведены в таблице.

Как видно из таблицы, в двух клетках теневые цены принимают отрицательные значения. Следовательно, полученное распределение перевозок не является оптимальным, и необходимо осуществить их перераспределение, используя при этом клетки (С3, М2) или (С3, Ф). Начнем с клетки (С3, М2), поскольку ей соответствует большее по абсолютной величине значение теневой цены.

Ступенчатый цикл для клетки (С3, М2) можно представить в виде таблицы.
Чтобы определить число единиц, которое следует перемещать вдоль построенного цикла, обратимся к клеткам (С2, М2) и (С3, М3), помеченным знаком -, количество перевозок в которых равно 2 и 0
единицам.

М2 М3
С2 Заполненная клетка
2
Заполненная клетка +
1
С3 Клетка, подвергнутая проверке +
1
Нулевая перевозка
0

Это означает, что по циклу следует осуществлять перемещение нулевой перевозки таким образом, чтобы клетка (С3, М3) снова стала пустой, а клетку (С3, М2) предполагается использовать при распределении перевозок, поскольку в нее помещается нулевая перевозка.

Применение метода МОДИ для проверки на оптимальность


Торговый Розничный магазин Общий
объем
предложения
склад М1 М2 М3 Ф
С1 (+3) 6 3 4 3 3 Ы 6 u1 = 0
С2 2 Li 1 ы та 3 U2 = - 1
С3 4 Li ? ы та 4 u3 = - 1
Общая
потребно
сть
4 5 1 3 13
Vi = 3 V2 = 4 V3 = 3 о
II
^і-

Остальные перевозки остаются без изменений. При дальнейшей проверке данного распределения на оптимальность выясняется, что значения всех теневых цен положительны. Данное распределение перевозок оптимальное. Это предполагает, что начальное решение, включающее 5 переменных, также оптимально.

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

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

МАКСИМИЗАЦИЯ


Алгоритм решения транспортной задачи предполагает, что ее целевая функция стремится к минимуму. Однако, если некоторая проблема требует максимизации целевой функции, перед тем, как применять для решения этой задачи стандартный алгоритм, его следует несколько модифицировать.

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

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

СПИСОК используемой литературы


1 Гаджинский А. М. Основы логистики. М., 1996.
2 Гордон М. П. Проблемы комплексного управления товародвижением в материально-техническом снабжении. М.: НИИМС, 1993.
3 Житков В. А., Ким К. В. Методы оперативного планирования грузовых перевозок. М.: Транспорт, 1992.
4 Залманова М. Е. Логистика. Саратов, 1995.
5 Логистика - наука об управлении материальными потоками. М.: НИИМС, 1989.
6 Логистика - новая наука // Подъемно-транспортная техника и склады. 1989. 1.
7 Логистика. Учебное пособие / Под ред. А. Б. Аникина.

М.: Инфра-М, 1997.
8 Материально-техническое снабжение: Журнал. Раздел Логистика: теория и практика.

1990 - 1996 гг.
9 Монден Я. Тоета. Методы эффективного управления.

М.: Экономика, 1989.
10 Неруш Ю. М. Коммерческая логистика: Учеб. для студентов вузов, обучающихся по направлениям и спец. Менеджмент, Коммерция и Маркетинг.

М.: Банки и биржи: Юнити, 1997.
11 Новиков О. А., Уваров С. А. Коммерческая логистика. СПб., 1995.
12 Организация обеспечения фирм стран Западной Европы продукцией производственно-технического назначения. М.: ЦНИИТЭИМС, 1989.
13 Панаев Э. П. Некоторые проблемы предпринимательской логистики // Маркетинг. 1/1997.
14 Панаев Э. П. Особенности использования логистики в смешанной экономике // Маркетинг. 3/1997.
15 Подъемно-транспортная техника и склады: Журнал. Раздел Логистика.

1989 - 1995 гг.
16 Посредники в логистической системе США: Пер. с англ. М.: НИИМС, 1989.
17 Промышленная логистика. СПб., 1994.
18 Проценко О. Д, Белотелов Е. П., Кодуа Д. М. Оперативное регулирование поставок продукции производственно-технического назначения. М.: Экономика, 1995.
19 Пурлик В. М. Рынок инвестиционных товаров и логистика. М.: Междунар.

Ун-т Бизнеса и Упр., 1997.
20 Резер С. М. Управление транспортом за рубежом. М.: Наука, 1994.
21 Риск: Журнал. Раздел Логистика.

1991 - 1997 гг.
22 Родников А. Н. Логистика: Терминол. словарь. М.: Экономика, 1995.
23 Роль логистики в разработке хозяйственной стратегии: Пер. с англ. М.: НИИМС, 1989.
24 Рынок и логистика / Г. И. Андрющенко, А. И. Баскин, Е. П. Белотелов и др.; Под ред. М. П. Гордона.

Ассоц. логистики, Ин-т исслед. товародвижения и конъюнктуры оптового рынка. М.: Экономика, 1993.
25 Смехов А. А. Введение в логистику. М.: Транспорт, 1993.
26 Стратегический характер логистических связей поставщика и потребителя: Пер. с англ. М.: НИИМС, 1989.
27 Транспортная логистика. М., 1996.
28 Управленческие нововведения в США. М.: Наука, 1986.
29 Эддоус М., Стэнсфилд Р. Методы принятия решений. М.: Аудит, 1997.
30 Operations research proceedings 1991: DGOR: Papers of the 20-th ann. meeting / Ed. by W. Gaul et al. Berlin etc: Springer, 1992.



Содержание раздела