XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 28
Текст из файла (страница 28)
Такая компания обычно имеет зональные оптовые базы (источникн), снабжающие товарами более мелкие региональные склады (промежуточные пункты), откуда эти товары поступают в розничную торговую сеть (стоки). При этом товар для каждого фиксированного стока в общем случае может быть доставлен не иэ любого источника и по маршрутам, не обязательно проходящим через все промежуточные пункты. Кроме того, промежуточные пункты могут обладать вполне определенной спецификой. Так, например, при транспортировке товара от источника к стоку по маршруту, проходящему через склад, часть товара может быть использована для создания неприкосновенного запаса на складе. Таблица 5.8 78 о -1 ю Рис. 5.2 200 а ЗАДАЧИ ТРАНСПОРТНОГО ТИНА Задачу выбора плана перевозок товаров от источников к стокам с учетом промежуточных пунктов, обеспечивающего минимальные транспортные затраты и потребности стоков, в исследовании операций называют пэрансзторпз44ой задачет1 с ззромежпзтаочмыми пизскпэами.
Для приобретения практических навыков в построении математических моделей таких задач обратимся к следующему примеру. Пример 5.4. Торговая фирма имеет восемь складов, на которых сосредоточены все имеющиеся в наличии запасы товара. Перед началом рекламной компании решено перераспределить часть запасов товара между складами в соответствии с прогнозами сбыта в районах их размещения. Требуется разработать план перевозок товара между складами, который позволит при минимальных транспортных затратах создать на каждом складе необходимый запас товара. На рис. 5.2 представлена схема размещения складов, на которой указаны: а) номера складов (цифры 1 — 8 в круге); б) избыток товара на складе (если он есть), который должен быть перераспределен в системе складов (он указан под кругом с номером склада неотрицательным числом в единицах измерения товара); в) недостаток товара на складе (если он есть), который должен быть устранен за счет его поставок с других складов системы (он указан под кругом с номером склада отрицательным числом и выражен в единицах измерения товара); г) возможность перевозки товара со склада г на склад 1 (ориентированная дуга от круга с номером 1 к кругу с номером у); 5.2.
Транспортная задача с промежуточными пунктами 201 д) затраты, связанные с перевозкой единицы товара со склада1 на склад 1' (величина с;, над соответствующей ориентированной дугой, выраженная в условных денежных единицах). На рис. 5.2 видно, что суммарный избыток товара, имеющийся на складах системы с номерами 1 и 4, равен суммарному недостатку товара, имеющемуся на складах с номерами 3, 6 и 8 этой же системы. Перераспределение товара может происходить через склады с номерами 2, 4-7, которые в рассматриваемой задаче и являются промежуточными пунктами.
Источником является лишь склад с номером 1, на котором имеется избыток товара и с которого товар можно только вывозить, а стоками являются склады с номерами 3 и 8, на которых есть недостаток товара, и на эти склады товары можно только завозить. Заметим также, что между складами с номерами 4 и 5 возможны перевозки в обоих направлениях, но в общем случае с4ь ~ сь4 (например, наличие одностороннего движения по кратчайшему маршруту). На рис. 5.2 фактически представлена сегпь рассматриваемой транспортной задачи с промежуточными пунктами.
Формальное описание этой сети удобно представить в виде табл. 5.8, аналогичной табл. 5.2. о.З. Транспортнаа задача с промемуточными пунктами 203 202 о. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА В табл. 5.8 каждому узлу селю (складу) соответствует одна строка и каждой ориентированной дуге сети соответствует одно переменное моделн х;, представляющее собой количество товара (в единицах его измерения), которое должно быть отправлено с т-го склада на у-й склад. Каждому переменному модели х;- соответствует один столбец, в котором стоит 1 в г-й строке, -1 в у'-й строке и с; в последней строке. В табл.
5.8 на пересечении 1-й строки и последнего столбца находится число, равное избытку (если оно неотрицательное) или недостатку (если оно отрицательное) товара на е'-м складе (в единицах измерения товара). Перейдем к построению транспортной таблицы (табл. 5.9) для рассматриваемой транспортной задачи с промежуточными пунктами с целью доказательства возможности преобразования этой задачи к классической транспортной задаче.
Таблица 5.9 На первом этапе в табл. 5.8 нужно выделить строку для каждого истпочнина и указать его моецность (избыток товара на складе). В данном примере источником является только склад с номером 1, мощность которого В1 = 10. В табл. 5.9 этому складу соответствует первый пункт производства с объемом поставок, равным 10. На втором этапе в табл. 5.8 нужно выделить столбец для каждого стока и указать его мощность (недостаток товара на складе). В данном примере стоками являются третий и восьмой склады. Поэтому Рз = 3 и Ре — — 8, что в табл.
5.9 соответствует значениям спроса для пунктов потребления 3 и 8. На третьем этапе нужно сделать следующее. 1. В табл. 5.9 выделить строку и столбец для каждого промежуточного пункта. В данном случае промежуточными пунктами являются склады с номерами 2, 4 — 7, которые в табл. 5.9 фигурируют как пункты производства и пункты потребления.
2. Для каждого и-го промежуточного пункта определить величину чнсупоео запаса товара Ть, равного объему избытка со знаком плюс либо объему недостатка со знаком минус. В данном случае Тз — — О, Т4 — — 2, Ть —— О, Те = — 1, Ту = 0 (см. табл. 5.8). 3. Определить суммарный объем избытка В на всех складах системы, используя последний столбец табл. 5.8. Суммарный объем избытка В представляет собой общий объем перевозок (в единицах измерения товара). В данном случае В = 10+ 2 = 12. 4. Считать, что маршрут транспортировки всего суммарного объема избытка товара может проходить через любой промежуточный пункт. Это означает, что любой склад с номером й, рассматриваемый как промежуточный пункт, может принять весь суммарный объем избытка товара и мощность „его стока" равна В, т.е.
Рь = В. Таким образом, в данном случае Рг = Рд —— Рь = Ре = Ру — — 12, в табл. 5.9 эти значения фигурируют как спрос. 5. Для каждого й-го промежуточного пункта определить „мощность его источника" Вь, т.е, объем товара, который может быть вывезен со склада с номером й. Так как на складе с номером й величина чистого запаса товара равна 204 Б.
ЗАДА ЧИ ТРАНСПОРТНОГО ТИПА Тз, а максимально возможный объем поставок определяется величиной В, то Вь = В + Та. В данном случае Вз = 12+ 0 = 12, 54= 12+2= 14, Яя = 12+0= 12, Во =12 — 1=11, Ят =12+0=12. В табл. 5.9 эти значения фигурируют как поставки. На ч е т в е р т о м з т а п е необходимо для каждого к-го промежуточного пункта ввести переменное хоь при соо = О. В данном случае Й Е (2, 4, 5, 6, 7), а интерпретировать переменное хоо можно как объем товара, который оседает на складе с номером /с. При построении транспортной таблицы (см. табл.
5.9) введена величина В, имеющая смысл „буферного запаса" в каждом промежуточном пункте. Для каждого Й-го промежуточного пункта величина В входит как в Вю так и в Вю Поэтому сумма спроса равна сумме поставок. Значение Вл должно быть настолько велико, чтобы оно могло соответствовать любому количеству товара, приходящему через к-й промежуточный пункт при любом допуспньном решении исходной задачи. Поэтому значение В принимают равным суммарному объему избытка товара в системе. В этом случае значение разности ( — хан) представляет собой объем товара (в единицах его измерения), перевезенного через и-й промежуточный пункт, так как  — максимально возможный объем поставок товара на склад с номером й, а хьо — объем товара, осевшего на этом складе.
В табл. 5.9 заполнены лишь те клетки, которые содержат переменные х;„соответствующие ориентированным дугам сети, а также переменные хьь, соответствующие промежуточным пунктам. Именно в этом и заключается отличие табл. 5.9 от табл. 5.1 (транспортной таблицы). Следует отметить, что в табл. 5.8 заданы восемь ограничений и десять переменных, а в транспортной таблице (см. табл. 5.9) заданы уже тринадцать ограничений (по строкам и столбцам) и пятнадцать переменных. Увеличение размерности на пять единиц объясняется наличием пяти промежуточных пунктов.
аа Транспортнан задача с промежуточнымн пуннтамн 205 Нетрудно убедиться в том, что в табл. 5.9 строка, соответствующая первому складу (источник), и столбцы, соответствующие третьему и восьмому складам (стоки), задают те же ограничения, что и соответствующие строки в табл. 5.8. Обратимся теперь к и-му складу, являющемуся промежуточным пунктом, т.е. (с Е (2, 4, 5, 6, 7), Пусть 1* — множество номеров складов, на которые товар может быть доставлен с Й-го склада, а 7- — множество номеров складов, с которых товар может быть доставлен на й-й склад. Тогда ограничение для й-го склада, заданное в табл. 5.8, имеет вид ~> хлй — ~~> хра = Ты (5.8) уеу где То — величина чистого запаса товара, введенная на третьем этапе построения транспортной табл. 5.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
