Изменение натурального объема, изделий
Р | Клетка, подвергнутая проверке + 1 | Заполненная клетка - 1 |
R | Заполненная клетка | Заполненная клетка |
- 1 | + 1 |
Стоимостные изменения, у.е. | ||
С | Ф | |
Р | Клетка, подвергнутая проверке | Заполненная клетка |
+ 5 | - 0 | |
R | Заполненная клетка | Заполненная клетка |
- 7 | + 0 |
Однако проверку пустых клеток необходимо завершить, поскольку могут существовать клетки, использование которых позволяет получить еще большую экономию.
Теперь построим ступенчатый путь для пустой клетки (Q, Ф). Необходимо учитывать, что для последующего осуществления балансировки движение можно осуществлять только через заполненные клетки.
В этом случае цикл из четырех шагов построить уже невозможно. Нам приходится выбирать более сложный маршрут.
В клетку (Q, Ф) поместим одно изделие. Строка Q и фиктивный столбец содержат только по одной заполненной клетке.
Предположим, что мы приняли решение двигаться из (Q, Ф) в (Q, В). Для того, чтобы сбалансировать строку Q,
из этой клетки вычтем одно изделие. Восстановить баланс для столбца В можно только с помощью клетки (R, В), следовательно, в нее необходимо добавить одно изделие. Балансировку строки R можно осуществить через клетки (R, А) и (R, С), но поскольку (R, А) - единственная заполненная клетка в столбце А, ее использовать нельзя. Если бы маршрут проходил через данную клетку, мы не могли бы сбалансировать столбец А. Объем перевозок в (R, С) уменьшается на одно изделие.
Оставшаяся часть маршрута очевидна. Восстановление баланса в столбце С производится увеличением перевозок в (Р, С) на одну единицу, а баланс строки Р достигается вычитанием одного изделия из (Р, Ф). Последний шаг позволяет также сбалансировать фиктивный столбец и замкнуть цикл.
Следует помнить, что построение замкнутого цикла внутри транспортной таблицы, который начинается и заканчивается в выбранной пустой точке, возможно только в том случае, если исходное распределение перевозок является базисным. Натуральные и стоимостные изменения, соответствующие построенному циклу, показаны в таблицах.
Чистый стоимостной эффект от размещения в пустой клетке (Q, Ф) составит + 8 у.е. за изделие. В случае заполнения данной пустой клетки общая стоимость транспортировки увеличится. Поэтому рассмотренные изменения вводить не следует.
В таблице показаны значения теневых цен.
Натуральные изменения, изделий | |||||||||||||||||||||||||||||
|
Стоимостные изменения, изделий
В | C | Ф | |||
Р | Пустая | Заполненная + 1 | Заполненная - 0 | ||
Q | Заполненная - 10 | ПУСТА | - | Проверяемая + 0 | |
_~_ | |||||
Я | |||||
R | Заполненная + 20 | Заполненная - 7 | ПУСТА | ||
Я |
2.17П Начальное распределение перевозок на оптимальность - метод ступенек | |||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||
Ключ: |
|
|||||||||||||||||||||||||||||||
Ключ: |
на оптимальность начального распределения перевозок | ||||||||||||||||||||||||||||||||||||||||||
|
Итеративная процедура нахождения оптимального распределения перевозок может быть представлена следующим образом:
1. Если транспортная таблица содержит более одной пустой клетки с отрицательным значением теневой цены, то выбирается та из них, которой соответствует наибольшее значение по абсолютной величине.
2. Построение для этой клетки ступенчатого цикла аналогично описанному выше.
3. Выявление клеток, количество перевозок в которых необходимо сократить, и определение величины этих сокращений таким образом, чтобы ни одно из значений перевозок не оказалось отрицательным. Максимальное количество изделий, соответствующее выбранной клетке, определяется минимумом из этих значений.
Перераспределение производится только для клеток, входящих в построенный цикл.
4. Нет никаких гарантий, что в полученном распределении нельзя предпринять никаких улучшений. Поэтому новое решение необходимо проверить на оптимальность с использованием метода МОДИ.
Утверждать, что найденная стоимость транспортировки является минимальной, можно только в том случае, если все теневые цены положительны или равны нулю.
Единственной клеткой с отрицательным значением теневой цены, равным - 2 у.е., является клетка (R, Ф). В эту клетку желательно разместить максимально возможное количество изделий.
Ниже приведен ступенчатый цикл для клетки (R, Ф), а также исходное распределение перевозок и единичные издержки.
2.20П Ступенчатый цикл для клетки (R, Ф)
С | Ф | |||
+ | 5 | - | 0 | |
Р | 2 | 7 | ||
- | 7 | + | 0 | |
R | 4 | ? |
Изменения, внесенные в транспортную таблицу, отражены в таблице.
2.21П Перераспределение перевозок | |||||||||||||||||||||||||||||||||||||||||||
|
Поставщ ик |
Транспортные издержки для магазинов, у.е. | Общий объем предложения | ||||||||
А | В | С | Ф | |||||||
Р | ,+ | 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 в розничный магазин С, увеличение стоимости составит 13 у.е., что гораздо выше, чем
стоимость самого маршрута, равная 8 у.е. Дополнительное увеличение стоимости появляется в связи с перебалансировкой распределения перевозок, при которой применяется ниже следующий ступенчатый цикл.
2.23П Ступенчатый цикл для (Q, С)
Натуральные изменения, изделий
Р Q R |
Пустая | Заполненная - 1 | Заполненная + 1 | ||
Заполненн - 1 | ая | Проверяемая - + 1 | Пустая | ||
Заполненная + 1 | Пустая | Заполненная - 1 |
Натуральные изменения, изделий | ||||||||||||||||||||||||
|
Изменение натурального объема, изделий | |||||||||||||||||
|
Изменение натурального объема, изделий | |||||||||||||||||
|
Если перевозка из некоторого пункта производства в некоторый пункт назначения по той или иной причине невозможна, то в алгоритме решения задачи данное ограничение можно учесть, присвоив соответствующей клетке достаточное большое значение стои-мости. Точное значение в данном случае неважно, однако оно должно быть больше, чем остальные значения стоимости, указанные в таблице.
Таким образом, алгоритм автоматически позволит избежать перевозок через данную клетку.
З а д а ч а 2.4
Ниже показано применение алгоритма решения транспортной задачи в решении проблем, связанных с недопустимостью прямых перевозок товаров из пунктов производства в пункты назначения. Рассматривается движение продукта во времени.
Пусть в нашем распоряжении имеется график перевозок сроком на 4 месяца, который необходимо выполнить. В таблице 2.27П приведены значения спроса на продукцию и значения производственных мощностей.
2.27П Значения спроса на продукцию и возможные объемы перевозок | |||||||||||||||
|
Стоимость перевозки единицы изделия, у.е. | Общее предложе ние |
|||||
Месяцы | ||||||
М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 |
Затем можно будет рассчитать значения всех компонент и и ?, следовательно, и теневые цены.
Реализацию алгоритма метода МОДИ мы начнем, используя пять заполненных клеток, соответствующих начальному распределению перевозок. Дополнительная нулевая перевозка будет введена только тогда, когда без нее продолжение алгоритма будет невозможно.
Обратимся к таблице.
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 |
Торго вый склад |
Розничный магазин | Общий объем предложения |
||||
М1 | М2 | М3 | Ф | |||
С1 | ^ | 4 3 |
(+6^ | 3 Ш | 6 | ui = 0 |
С2 | ^ | 2 Li | 1 Ll | та | 3 | U2 = - 1 |
С3 | 3 LL | 0й | ^ | о0 | 6 | U3 = 3 |
Общая потребн ость |
4 | 5 | 1 | 3 | 13 | |
V1 = - 1 | V2 = 4 | v3 = 3 | v4 = 0 |
Пусть выбрана клетка (С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 |
Торговый | Розничный магазин | Общий объем предложения |
|||||
склад | М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 ^і- |
Обратимся к данным таблицы.
Такие результаты далеко не всегда имеют место в случае вырожденного решения. В некоторых ситуациях при перераспределении перевозок определенное количество единиц продукта помещается в клетку с нулевой перевозкой, и тем самым данная клетка вводится в новое распределение перевозок. Это приводит к исчезновению врожденности решения.
Затем, для получения улучшенного распределения перевозок, применяются обычные алгоритмы.
Алгоритм решения транспортной задачи предполагает, что ее целевая функция стремится к минимуму. Однако, если некоторая проблема требует максимизации целевой функции, перед тем, как применять для решения этой задачи стандартный алгоритм, его следует несколько модифицировать.
Например, мы намерены осуществлять перевозки, максимизируя общий доход. В этом случае нам необходима информация об единичных доходах от транспортировки товаров между всеми пунктами производства и назначения.
Модификация заключается в умножении всех значений единичного дохода на (- 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.