ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
Зафиксируем продолжительность цикла Т, не принимая во внимание колеблемость значений спроса и времени поставки заказа. Значение Т следует округлить до соответствующей величины. Система управления запасами должна быть построена таким образом, чтобы ею можно было легко управлять, поэтому совершенно нежелательно, чтобы лицу, осуществляющему управление запасами, приходилось проводить проверку запасов с неудобными для него интервалами времени.
Критерием выбора размера заказа должна служить цель создания системы управления запасами. Как и в предыдущем случае, исследуем данную проблему с точки зрения минимального уровня обслуживания и минимальной стоимости.
М о д е л ь I: Достижение минимального уровня обслуживания
Для определения фиксированного интервала повторного заказа, не учитывая каких-либо изменений значений спроса или времени поставки, найдем интервал повторного заказа, в котором достигается минимальное значение общей переменной стоимости подачи заказа и хранения запасов:
Общая переменная стоимость за год = Годовая стоимость подачи заказа + Годовые издержки хранения.
Если интервал повторного заказа равен Т лет, число подаваемых за год запасов составит 1/Т. Размер каждого заказа равен q, где D = q /T, следовательно, q = DT.
Если не учитывать размер резервного запаса, то средний уровень запаса составит q/2 = DT/2. Таким образом, общая переменная стоимость за год определяется по следующей формуле:
ТС = Со (1/Т) + Сн (DT/2) (у.е. в год).
После того, как значение Т найдено, производится его корректировка в соответствие с наиболее удобным интервалом проверки наличия запасов. Если, например, расчеты показали бы, что Т = 4,2 дня, найденное значение было бы скорректировано на интервал проверки запасов, равный одной неделе.
Теперь мы должны найти уровень запасов, который будет определять размер подаваемого заказа. Например, можно принять решение, что размер заказа на момент его подачи должен быть выбран таким образом, чтобы уровень запаса увеличился до 100 единиц продукции при условии, что поставка заказа осуществляется незамедлительно.
Следовательно, если уровень запасов равен 35, то размер заказа будет равен 65, если же уровень запасов равен 43, размер заказа составит 57 единиц продукции.
З а д а ч а 1.9 Предположим, что для некоторого вида продукции уровень обслуживания совпадает с размером одной нехватки продукции при условии, что цикл повторного заказа составляет 4 рабочие недели. Предположим также, что год состоит из 50 рабочих недель. Зафиксируем время поставки заказа на уровне двух недель.
Спрос на данную продукцию в неделю аппроксимируется нормальным распределением, среднее значение которого равно 300 единицам продукции в неделю, а стандартное отклонение - 50 единиц продукции в неделю.
Решение
Число циклов запаса в течение года составит: 50/4 = 12,5. Вероятность нехватки запаса в течение цикла определяется как 1/12,5 = 0,08.
Следовательно, уровень обслуживания, которого необходимо достичь, равен 0,92.
Переменный спрос, который нужно учесть в процессе решения, - это спрос, предъявляемый с момента принятия решения о подаче заказа до момента получения новой партии повторного заказа, то есть спрос, возникающий в течение всего цикла повторного заказа, а также спрос в течение поставки как было в уровневой модели повторного заказа. Предположим, что распределение спроса в течение 6 недель (продолжительность цикла - 4 недели плюс время поставки заказа - 2 недели) является нормальным и имеет среднее значение: 6 Ф 300 = 1800
единиц продукции и стандартное отклонение V6 X 502 = 122,5 единиц продукции. Соответствующий график распределения спроса - см. рис.
3П.
Размер заказа выбирается таким образом, чтобы уровень запасов возрос до величины М; которая, в свою очередь, выбирается так, чтобы вероятность удовлетворения спроса в продолжении цикла запаса составляла 92 %. Мпредставляет собой z стандартных отклонений от среднего, где
M -1800 z = .
122,5
Следовательно, из таблицы для стандартного нормального распределения находим, что при P(z) (M - 1800/122,5) = 0,08; z =
1,405.
Следовательно,
М = 1800 + (1,405 Ф 122,5) = 1972,1.
Итак, во время каждой проверки наличия запасов, проводимой один раз в 4 недели, будет сделан новый заказ, размер которого позволит обеспечить уровень обслуживания, равный 92 % или в среднем одну нехватку запасов в год.
М о д е л ь II: Достижение минимальной стоимости
Алгоритм, который применялся в модели I, можно использовать также и для определения наиболее приемлемой продолжительности цикла повторного заказа. Уровень запасов М, при котором достигается минимум общей переменной стоимости за год, можно определить по аналогии с методом определения размера необходимого резервного запаса.
Используя данные задачи 8, определим фиксированный интервал повторного заказа.
D = 475 телевизоров в среднем за год;
С0 = 50 у.е. за заказ;
Ch = 0,15 ^ 250 у.е. = 37,50 у.е. за телевизор в год;
С = 250 у.е. за телевизор;
Съ = 20 у.е. за телевизор;
L = 3 дня.
Продолжительность рабочего года - 300 дней.
Оптимальный интервал повторного заказа определяется следующим образом:
0,07 года.
2Q , T 2 х 50 ChD ’ \ 475 х 37,5
Оптимальный интервал повторного заказа составляет: 0,07 Ф 300 = 21 рабочий день. Предположим, что
рабочий год, продолжительностью в 300 дней состоит из 6-дневных рабочих недель, тогда наиболее приемлемым для подачи повторных заказов будет интервал, равный 4 неделям. Размер заказа, определяемый каждый раз в момент его подачи, должен быть таким, чтобы уровень запасов возрос до величины М при условии незамедлительного получения заказа, где М минимизирует издержки хранения резервного запаса и стоимость нехватки запасов за год. Размер резервного запаса определяется как:
В = (М - среднее значение спроса в течение поставки и цикла повторного заказа).
Цикл повторного заказа составляет 4 Ф 6 рабочих дней, а время поставки - 3 рабочих дня. Поэтому необходимо учитывать спрос, возникающий в течение 27 рабочих дней.
Нам известно, что годовой спрос равен 475 телевизорам за 300 рабочих дней, поэтому среднее значение спроса за 27 дней составит: (475/300) ^ 27 = 42,75 телевизорам. Резервный запас равен М - 42,75, а издержки его хранения за год - (М- 42,75) ^ 37,5 у.е. в год. Ожидаемые издержки, связанные с отсутствием запаса в течение года, зависят от колеблемости спроса в течение исследуемых 27 дней.
К сожалению, невозможно произвести расчеты ввиду недостатка информации, имеющейся в распоряжении. Необходимо сгенерировать соответствующее распределение и проверить его надежность, собрав дополнительные данные.
ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
При разработке оптимального плана перевозок существенно упрощает процесс построения исходной модели использование специально алгоритмов. Ниже рассматриваются примеры таких алгоритмов, созданных для решения транспортной задачи и задачи о назначениях.
В обоих случаях проблема распределения перевозок связана с продуктами, которые в соответствии с определенной целью перевозятся из пунктов производства в пункты потребления. Целью часто является минимизация общей стоимости транспортировки. Пусть, например, некоторой компании принадлежат три завода и пять пунктов распределения продукции, находящиеся в одном регионе.
Администрация компании должна организовать перевозку конечной продукции с заводов в пункты распределения с минимальной стоимостью. В этой ситуации наиболее подходящими могли бы стать методы решения транспортной задачи.
Частным случаем транспортной задачи является задача о назначениях. Предполагается, что из каждого пункта производства в каждый пункт потребления перевозится только один товар.
В процессе решения этой и подобных проблем можно использовать алгоритм решения задачи о назначении.
На практике зачастую размерность таких задач значительна, что требует применения для их решения пакетов прикладных программ.
РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Данная проблема связана с распределением товаров между поставщиками (находящимися в пунктах производства) и потребителями (находящимися в пунктах назначения) таким образом, чтобы общая стоимость этого распределения была минимальной. Эта задача может быть решена либо с помощью методов линейного программирования, либо специального алгоритма решения транспортной задачи.
З а д а ч а 2.1. Компания с ограниченной ответственностью осуществляет производство прохладительных напитков на двух заводах - А и В. Поставкой бутылок на каждый из заводов занимаются две фирмы P и Q. На ноябрь заводу требуется 5000 бутылок, а заводу В - 3500 бутылок.
Фирма Р может поставить максимум 7500 бутылок, а фирма Q - 4000 бутылок.
2.1 П Стоимость перевозки бутылок, показатели спроса и предложения
| Поставщик | Стоимость перевозки одной бутылки на завод, пенсов | Максимальный объем поставки | |
| А | В | ||
| Р | 4 | 4 | 7500 |
| Q | 3 | 2 | 4000 |
| СПРОС НА БУТЫЛ КИ |
5000 | 3500 |
Решение
Пусть фирма Р поставляет х бутылок для завода А и у бутылок для завода В. Фирма Q поставляет а бутылок заводу а и b бутылок заводу В. Целевая функция с учетом приведенных в таблице затрат на перевозку будет иметь вид:
С = 4х + 4y + 3a + 2b.
Выразим ограничения через переменные:
Данная задача не удовлетворяет предпосылкам транспортной задачи, но может быть преобразована в транспортную.
х + у 7500, a + b 4000, a + х = 5000, y + b = 3500.
Решая задачу с помощью прикладной программы для ЭВМ, получаем следующий результат.
х = 4500.0000, а = 500.0000, b = 3500.0000.
Значение целевой функции (оптимальное) 26500.0000.
Анализ ограничений и теневые цены:
Огр: х + у 7500
4500.0000 = 7500.0000 == 0.00000
Огр: a + b 4000
4000.0000 = 4000.0000 == 0.000000
Огр: a + х = 5000
5000.0000 = 5000.0000 == -4.000000
Огр: у + b = 3500
3500.0000 = 3500.0000 == -3.000000.
Данная задача после некоторого преобразования может быть решена графически. Однако встречаются относительно более сложные задачи, при решении которых применение методов линейного программирования является более обоснованным.
За дача 2.2. Некоторый продукт производится на двух заводах и распределяется между двумя
пользователями. Их потребности на ближайшие два месяца приведены в таблице:
2.2П Потребности на ближайшие два месяца
| Пользователь | Потребность | |
| август | сентябрь | |
| 1 | 420 | 550 |
| 2 | 350 | 480 |
2.3П Стоимость транспортировки продукта с заводов потребителям
|
||||||||||
| Стоимость производства единицы продукта и объем производства по плану за два месяца приведены в таблицах. |
| 2.4П Объем производства по плану за два месяца | |||||||
|
500
2.5П Стоимость производства единицы продукта за два месяца
| Завод | Объем производства | |
| август | сентябрь | |
| 1 | 3,0 | 3,6 |
| 2 | 3,2 | 2,9 |
| Решение Сформулируем задачу как задачу линейного программирования. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| cla |
1 в августе;
c2a
zla
zls
z2a
z2s
- количество продукта, поступившего на склад завода
2 в августе;
- количество продукта, произведенного заводом 1 в августе;
- количество продукта, произведенного заводом 1 в сентябре;
- количество продукта, произведенного заводом 2 в августе;
- количество продукта, произведенного заводом 2 в сентябре.
Целевая функция будет иметь вид:
С = zlpla Ф 10 + z2p1a Ф 12 + zlpls Ф 10 + z2p1s Ф 12 +
+ z1p2a Ф 13 + z2p2a Ф 6 + z1p2s Ф 13 + z2p2s Ф 5 + zla Ф 3 + + z2a Ф 3.2 + zls Ф 3.6 + z2s Ф 2.9 + cla Ф 0.5 + c2a Ф 0.6. Ее значение необходимо минимизировать.
Введем следующие ограничения.
zlpla + z2p1a = 420 zlpls + z2p1s = 550 z1p2a + z2p2a = 350
z1p2s + z2p2s = 480 zla 500 zls 600 z2a 300 z2s 500
cla = zla - zlpla - z1p2a c2a = z2a - z2pla - z2p2a zls = zlpls - zlp2s - cla z2s = z2pls + z2p2s - c2a
С помощью прикладной программы для ЭВМ получаем следующее решение:
Отчет о решении задачи линейной оптимизации
Замечание
| Переменная | Значение |
| zlpla | 420.0000 |
| zlp2a | 50.000000 |
| z2pla | 0.00000 |
| z2p2a | 300.0000 |
| zlpls | 550.0000 |
| zlp2s | 0.00000 |
| z2pls | 0.00000 |
| z2p2s | 480.0000 |
| cla | 30.000000 |
| c2a | 0.00000 |
| zla | 500.0000 |
| zls | 520.0000 |
| z2a | 300.0000 |
| z2s | 480.0000 |
Огр: zlpla + z2p1a = 420
420.0000 = 420.0000 == -l3.l00000
Огр: zlpls + z2pls = 550
550.0000 = 550.0000 == -l3.600000
350.0000 = 350.0000 == -l6.l00000
Огр:zlp2a + z2p2a = 350 Огр: zlp2s + z2p2s = 480
480.0000 = 480.0000 == -7.900000
Огр: zla 500
500.0000 = 500.0000 == 0.l000000
520.0000 = 600.0000 == 0.00000
Огр: zls 600 Огр: z2a 300
300.0000 = 300.0000 == 6.900000
Огр: z2s 500
480.0000 = 500.0000 == 0.00000
Огр:cla = zla - zlpla - zlp2a
30.000000 = 30.000000 == 3.100000
Огр: c2a = z2a - z2p1a - z2p2a
0.00000 = 0.00000 == 10.100000
Огр: z1s = z1p1s + z1p2s - c1a
520.0000 = 520.0000 == -3.600000
Огр: z2s = z2p1s + z2p2s - c2a
480.0000 = 480.0000 == -2.900000
Итоговая таблица оптимального плана производства и транспортировки выглядит следующим образом.
| 2.6П Оптимальный плана производства и транспортировки | ||||||||||||||||||||||||||||||
|
АЛГОРИТМЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
Выше приведено решения задач с помощью методов линейного программирования. Возможно также использовать алгоритм решения транспортной задачи. Применение этого алгоритма требует, чтобы задача удовлетворяла определенным требованиям:
1) должна быть известна стоимость перевозки единицы продукта из каждого пункта производства в пункт назначения;
2) запас продуктов в каждом пункте производства должен быть известен;
3) потребности в продуктах в каждом пункте производства должны быть известны;
4) общее предложение должно быть равно общему спросу, то есть задача должна быть транспортной.
Задача 1 не являлась транспортной как раз по тому, что не удовлетворяла предпосылке 4). Тем не менее,
можно ввести фиктивный завод, потребность которого определяется разностью между общим предложением и общим спросом. Потребность фиктивного завода по данным задачи 2.1 составила бы (11 500 8500) = 3000 бутылок. Любые продукты, которые подлежат распределению в фиктивный пункт назначения, на деле не вывозятся из пункта производства. В случае, если общее предложение меньше общего спроса, поступают аналогичным образом, то есть в модель вводится фиктивный поставщик, максимальный объем поставок которого равен величине неудовлетворенного спроса.
Количество товаров, вывозимых из фиктивного пункта производства, характеризует величину недостающих поставок.
Алгоритм решения транспортной задачи состоит из четырех этапов:
Этап 1. Представление данных в форме стандартной таблицы и поиск любого допустимого распределения перевозок. Допустимым называется такое распределение перевозок, которое позволяет удовлетворить весь спрос в пунктах назначения и вывезти весь запас продуктов из пунктов производства.
Этап 2. Проверка полученного распределения перевозок на оптимальность.
Этап 3. Если полученное распределение перевозок не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.
Этап 4. Повторная проверка оптимальности полученного распределения перевозок.
Данный итеративный процесс повторяется до тех пор, пока не будет получено оптимальное решение.
ПОИСК НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ ПЕРЕВОЗОК
Начальное распределение перевозок может быть получено с помощью любого метода, позволяющего найти допустимое решение задачи. Однако при систематическом решении таких задач можно разработать методы, позволяющие получать более выгодные начальные решения.
Остановимся на двух методах нахождения начального распределения перевозок - методе минимальной стоимости и методе Вогеля.
З а д а ч а 2.3. Три торговых склада - P, Q и R - могут поставлять некоторое изделие в количестве 9, 4 и 8 единиц соответственно.
Величины спроса трех магазинов розничной торговли, находящихся в пунктах А, В и С, на это изделие равны 3, 5 и 6 единицам соответственно. Какова минимальная стоимость транспортировки изделий от поставщиков к потребителям?
Единичные издержки транспортировки приведены в таблице.
2.7П Издержки транспортировки, объемы потребностей и предложения
| Поставщик | Транспортные издержки для магазинов, у.е. | Общий объем предложения | ||
| А | В | С | ||
| Р | 10 | 20 | 5 | 9 |
| Q | 2 | 10 | 8 | 4 |
| R | 1 | 20 | 7 | 8 |
| Общий объем спроса | 3 | 5 | 6 |
В нашем распоряжении имеется информация об издержках, предложении изделий и потребностей в них, но общее предложение превышает общий спрос. Общее количество изделий, которое могут поставить все склады, равно 21, однако розничным магазинам необходимо только 14 изделий. Следовательно, необходимо ввести фиктивный розничный магазин, потребность которого будет равна 7 изделиям, определяющим избыток предложения.
Фактически эти 7 изделий не будут вывезены с торговых складов, поэтому предполагается, что издержки транспортировки для них будут равны нулю.
2.8П Сбалансированная транспортная таблица
| Поставщик | Транспортные издержки для магазинов, у.е. | Общий объем предложения | |||
| А | В | С | Ф | ||
| Р | 10 | 20 | 5 | 0 | 9 |
| Q | 2 | 10 | 8 | 0 | 4 |
| R | 1 | 20 | 7 | 0 | 8 |
| Общий объем спроса |
3 | 5 | 6 | 7 |
М е т о д 1. Метод минимальной стоимости
1. В клетку с минимальной единичной стоимостью записывают наибольшее возможное количество продукта.
2. Производится корректировка оставшихся объемов предложения и потребностей.
3. Выбирается следующая клетка с наименьшей стоимостью, в которую помещается наибольшее возможное количество продукта, и так далее до тех пор, пока спрос и предложение не станут равными нулю.
4. Если наименьшее значение стоимости соответствует более чем одной клетке таблицы, выбор осуществляется случайным образом.
НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПЕРЕВОЗОК, ПОЛУЧЕННОЕ МЕТОДОМ МИНИМАЛЬНОЙ СТОИМОСТИ
|
|||||||||||||||||||||||||||||||||||||
| Ключ: |
Ключ:
Если значение стоимости положительное, то привлечение пустой клетки увеличит общую стоимость, а это невыгодно. Если же значение стоимости отрицательное, то использование пустой клетки, напротив, снижает общую стоимость транспортировки. Последнее означает, что полученное распределение перевозок является неоптимальным, и при использовании данной незаполненной клетки можно получить лучшее решение задачи.
Какая из пустых клеток будет выбрана в начале процедуры, значения не имеет. Выберем клетку (Р, А). Добавим в нее одну единицу изделия. Теперь полученное распределение является несбалансированным. Розничный магазин А получает 4 единицы изделия, в то время как его потребность - 3. Торговый склад Р является поставщиком 10 изделий, тогда как максимальный объем его предложения равен 9. Необходимо произвести корректировку столбца А и строки Р. Для восстановления баланса в столбце А необходимо вычесть одно изделие из ступеньки (R, А). Эта мера корректирует столбец А, но нарушает баланс строки R, уменьшая соответствующее предложение с 8 до 7 единиц.
Можно осуществить перебалансировку строки Р вычитанием одного изделия либо из клетки (Р, Ф), либо из клетки (Р, С). Если мы выберем клетку (Р, Ф), то в фиктивном столбце нет больше заполненных клеток, которые можно было бы использовать в дальнейшей корректировке этого столбца, следовательно, данный выбор неприемлем. Корректировку можно осуществлять только с помощью тех клеток, которые уже заполнены на настоящий момент. Поэтому мы должны выбрать клетку (Р, С). Из (Р, С) вычитаем одно изделие. Это корректирует баланс по строке Р, но нарушает его по столбцу С. На данном этапе проблема несбалансированности связана со строкой R и столбцом С. Их можно скорректировать одновременно, добавив одно изделие в (R, C). Схематично процесс заполнения пустой клетки (Р, А) и восстановления баланса распределения перевозок показан в таблице.
Денежный эффект от перемещения одного изделия в клетку (Р, А) рассчитывается следующим образом:
+ 1 х стоимость (Р, А) - 1 х стоимость (R, A) + 1 х х стоимость (R, С) - 1 х стоимость (Р, С) = + 11 за изделие.
2.12П Проверка пустой клетки (Р, А)
| Изменение натурального объема, изделий | ||
| А | С | |
| Р | Клетка, подвергнутая проверке + 1 | Заполненная клетка - 1 |
| R | Заполненная клетка | Заполненная клетка |
| - 1 | + 1 |
Возвращаемся к исходному распределению перевозок и проводим последовательную проверку остальных пустых клеток. Выберем клетку (R, Ф), а для иллюстрации натуральных и стоимостных изменений, связанных с перемещением одной единицы изделия в клетку (R, Ф), используем ступеньки (Р, Ф), (Р, С) и (R, С).
