XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 27
Текст из файла (страница 27)
Ее пример при тп = 2 и и = 3 предста- Рис. л.1 влек на рис. 5.1. Итак, каждое переменное х! соответствует потоку вдоль ориентированной дуги, с; выражает затраты в расчете на единицу потока, а сама задача заключается в распределении мощностей источников по дугам таким образом, чтобы при минимальных затратах удовлетворить потребности стоков. Прежде чем переходить к рассмотрению конкретных примеров, сделаем несколько замечаний, относящихся к постановке классической транспортной задачи. Замечание 5.2. Затраты, связанные с производством единицы товара, как правило, не одинаковы для различных пунктов производства.
В случае необходимости учет этих затрат при постановке транспортных задач осуществляют путем их включения в коэффициенты с; . Замечание 5.3. Если в силу каких-либо причин 2-й пункт производства не доступен для 1'-го пункта потребления, то 195 1=1,т, 7=1,п х;, < 10, Таблица 5.4 194 а 3АдАчи тРАнспОРтнОГО типА либо переменное модели х; исключается из рассмотрения, либо величина с," принимается сколь угодно большой. Замечание 5.4. При постановке классической транспортной задачи предполагается выполнение условия (5.1), которое не является обременительным, так как всегда можно ввести фиктивный пункт производства или сбыта и скомпенсировать величину невязки Замечание 5.5, Иногда возникает необходимость в учете ограничений, связанных с пропускной способностью той или иной ориентированной дуги сети, при постановке транспортной задачи.
В простейшем случае зти ограничения имеют вид неравенств (5.7) Задачу исследования операций вида (5.1)-(5.4), (5.7) называют пзрокспортпной задачей с оераничениями по пропускной способкосгпи. Как правило, введение ограничений (5.7) в математическую модель классической транспортной задачи приводит лишь к незначительному увеличению объема вычислений при поиске оптимального решения. Но иногда зти ограничения оказываются настолько жесткими, что множество допусгпи.иых решений рассматриваемой задачи оказывается пустым. Замечание 5.6. При постановке классической транспортной задачи предполагают, что все пункты производства выпус.- кают одну и ту же продукцию, Но, как правило, каждое предприятие выпускает несколько видов товаров, и при разработке плана их перевозок необходимо учитывать всю номенклатуру. В настоящее время разработаны различные приемы преобразований этой задачи к классической транспортной задаче. 5. Ь Классическая трапспортнаи эвдача Пример 5,1, Пусть заводы автомобильной фирмы, расположенные в городах А~, Аз и Аз, выпускают соответственно 1000, 1500 и 1200 автомобилей в квартал, а спрос на готовую продукцию в центрах сбыта этой фирмы, расположенных в городах В~ и Вз, составляет 1900 и 1400 автомобилей в квартал соответственно.
Стоимость перевозки одного автомобиля от пункта производства до центра сбыта (в условных денежных единицах) представлена в табл. 5.3. Таблица 5.3 Необходимо разработать план перевозок автомобилей от пунктов их производства В~ Вз к центрам сбыта, обеспечивающий мини- А, 80 215 мальные транспортные затраты. А 100 108 Очевидно, что суммарный объем про- Аз 102 68 изводства (1000+ 1500+ 1200 = 3700 автомобилей в квартал) превышает спрос (1900+ 1400= 3300 автомобилей в квартал), и условие (5.1) не выполняется.
В этой ситуации можно ввести фиктивный пункт сбыта Вз, который „поглощает" избыток продукции. Фактически автомобили, произведенные на любом из заводов фирмы и предназначенные для фиктивного пункта сбыта Вз, представляют собой избыток производства и остаются на этом заводе. Поэтому стоимость перевозки одного такого автомобиля равна нулю и транспортная таблица рассматриваемой задачи имеет вид, указанный в табл.
5.4. Заметим, что можно назначить штраф за хранение автомобиля на складе завода. В этом случае стоимость перевозки 197 ц К Классическая чранспартнаа задача 196 л. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА одного автомобиля от места производства до фиктивного пункта сбыта Вз будет равна стоимости его хранения на складе завода-производителя. Пример 5,2. Предположим, что в условиях задачи, рассмотренной в примере 5.1, произошло изменение: завод, расположенный в городе Аз, производит не 1500 автомобилей в квартал, а всего лишь 1000 автомобилей.
Это опять приводит к нарушению условия (5.1), поскольку суммарный объем производства (3200 автомобилей в квартал) не равен суммарному спросу (3300 автомобилей в квартал). Таким образом, спрос в центрах сбыта автомобилей полностью удовлетворить не удастся. В рассматриваемой ситуации целесообразно так преобразовать транспортную задачу, чтобы недостаток автомобилей (ЗЗОΠ— 3200= 100 автомобилей в квартал) оптимально распределить между центрами сбыта фирмы. Можно ввести фиктивный завод А4, производящий в квартал 100 автомобилей, и считать, что стоимость перевозки одного такого автомобиля в любой центр сбыта равна нулю.
Транспортная таблица, соответствующая этому варианту действий, представлена в табл. 5.5. Таблица 5.5 Реально каждая единица недопоставленной в центры сбыта продукции приносит фирме явные и скрытые убытки (штрафы, недополученная прибыль, потеря престижа и т.д.). Поэтому транспортные расходы на единицу продукции фиктивного за- вода Ад целесообразно определять с учетом убытков фирмы, обусловленных недопоставками автомобилей в тот или иной центр сбыта. Пример 5.3. Рассмотрим задачу, которая на первый взгляд не имеет никакого отношения к классической транспортной задаче.
Некоторая фирма решила выделить часть производственных мощностей своего завода для производства сезонных изделии определенного вида в течение четырех месяцев. В течение первого месяца завод может произвести 50 изделий при спросе 100 иэделий, оговоренном в контракте оптовым покупателем. В течение второго, третьего и четвертого месяцев зти цифры соответственно составят 180 и 200, 280 и 180, 270 и 300. В течение каждого месяца спрос можно удовлетворить за счет: а) избытка изделий, произведенных в предыдущие месяцы и хранящихся на заводском складе для реализации в будущем; б) производства изделий в течение текущего месяца; в) избытка производства изделий в более поздние месяцы в счет невыполненных заказов. Затраты, связанные с производством одного изделия, составляют 4 условные денежные единицы.
Хранение одного изделия на заводском складе в течение одного месяца обходится фирме в 0,5 условной денежной единицы, а за недопоставку одного изделия оптовый покупатель штрафует изготовителя на 2 условные денежные единицы. Необходимо разработать план поставок готовой продукции оптовому покупателю, обеспечивающий минимальные затраты связанные с реализацией проекта выпуска сезонных иэделий определенного вида в течение четырех месяцев. Из табл. 5.6 следует, что рассматриваемая задача может быт ыть сформулирована в терминах классической транспортной задачи, если стоимость „перевозки" одного изделия из 1-го периода производства в З-й период потребления определяется Таблица 5.7 4, с;.
= 4+0,5(З вЂ” 1), 1 < ); 4+2(( — З), (> ъ Таблица б.б Производственная система Транспортная система Источник 1(пункт производ- ства) Сток з' (станция назначения или пункт сбыта) Мощность источника 1 (объ- ем поставок товара от Ьго пункта производства) Мощность стока з (объем по- ставок товара З'-й станции назначения) Стоимость перевозки едини- цы товара от 1-го источника к З-му стоку 198 Б. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА следующим образом (в условных денежных единицах): Здесь в случае г = З учтены затраты на производство, в случае ( < З' — затраты на производство и затраты на хранение, а в случае 1> ) — затраты на производство и затраты на оплату штрафа.
Период производства 1 (по- рядковый номер месяца) Период потребления у (поряд- ковый номер месяца реализа- ции готовой продукции) Объем производства за пе- риод 1 (количество изделий, произведенных в течение 1-го месяца) Реализация за период з (коли- чество изделий, полученных оптовым покупателем в Ззм месяце) Затраты, связанные с реали- зацией одного изделия в пе- риод потребления з, если оио изготовлено в период произ- водства 1 В соответствующей транспортной таблице (табл.
5.7) хц количество изделий, изготовленных на заводе в 1-м месяце и отправленных покупателю в счет З'-го месяца. аа Траиспортиаа задача с промеиуточимми пунктами 199 5,2, Транспортная задача с промежуточными пунктами Одно практически важное обобщение классической тпраисиоршиой задачи связано с учетом возможности доставки товара от 1-го исп1очиика к ~-му стпоку по маршруту, проходящему через некоторый оромежутпочный пуиктв (склад). Так, например, промежуточные пункты являются составной частью распределительной системы любой крупной компании, имеющей сеть универсальных магазинов во многих городах.