Транспортная задача

шагу соответствует разбиение переменных на основные (базисные) и неосновные (свободные).

Число r основных переменных транспортной задачи равно рангу системы линейных уравнений (максимальному числу линейно независимых уравнений в системе ограничений).

Теорема 2. Ранг r системы уравнений (1),(2) при условии (8) равен 5

 

 

 

 

 

2.2. Открытая модель транспортной задачи

Определение 6.

Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие (8), называется открытой.

Для открытой модели может быть два случая:

1. суммарные запасы превышают суммарные потребности ;
2. суммарные потребности превышают суммарные запасы .

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

Найти минимальное значение линейной функции

 при ограничениях

,    i = 1,2,3, ... m ;                          (случай  а)

,    j = 1,2,3, ..., n;

,    i = 1,2,3, ...n;                           (случай б)

,   j = 1,2,3, ..., n;

   i = 1,2,3, ... m; j = 1,2,3, ..., n).

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель , потребности которого 

 = .

В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик запасы которого

= .

Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.

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

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

 

Пример 1.

Пусть заводы автомобильной фирмы, расположенные в городах А1,А2 и А3, выпускают соответственно 1000, 1500 и 1200 автомобилей в квартал, а спрос на готовую продукцию в центрах сбыта этой фирмы, расположенных в городах В1,В2 и В3, составляет 1900 и 1400 автомобилей в квартал соответственно. Стоимость перевозки одного автомобиля от пункта производства до центра сбыта (в условных денежных единицах) представлена в табл. 2. Необходимо разработать план перевозок автомобилей от пунктов их производства к центрам сбыта, обеспечивающий минимальные транспортные затраты.

Таблица 2.

	В1	В2
А1	80	215
А2	100	108
А3	102	68

 

Очевидно, что суммарный объем производства (1000 + 1500 + 1200 = 3700 автомобилей в квартал) превышает спрос (1900+ 1400= 3300 автомобилей в квартал), и условие (8) не выполняется. В этой ситуации можно ввести фиктивный пункт сбыта В3, который „поглощает" избыток продукции. Фактически автомобили, произведенные на любом из заводов фирмы и предназначенные для фиктивного пункта сбыта В3, представляют собой избыток производства и остаются на этом заводе. Поэтому стоимость перевозки одного такого автомобиля равна нулю и транспортная таблица рассматриваемой задачи имеет вид, указанный в табл. 3.

 

Таблица 3.

	В1	В2	В2	Поставки
А1 А2 А3
Спрос

 

Заметим, что можно назначить штраф за хранение автомобиля на складе завода. В этом случае стоимость перевозки одного автомобиля от места производства до фиктивного пункта сбыта В3 будет равна стоимости его хранения на складе завода-производителя.

 

3. Транспортная задача с промежуточными  пунктами

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

 
Определение 7.

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

 

Для приобретения практических навыков в построении математических моделей таких задач обратимся к следующему примеру.

 

 

 

Пример 2.

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

    а) склады в виде узлов сети с номерами от 1 до 8;

    б) избыток  товара на складе, который должен  быть перераспределен в системе  складов (указан в квадратных  скобках рядом с узлом сети  положительным числом и выражен  в единицах измерения товара);

    в) недостаток  товара на складе, который должен  быть устранен за счет его  поставок с других складов  системы (указан в квадратных  скобках рядом с узлом сети  отрицательным числом);

    г) возможность  перевозки товара со склада  на склад (ориентированная дуга от круга с номером к кругу с номером ;

    д) затраты, связанные с перевозкой единицы товара со склада на складвеличина cij рядом с соответствующей ориентированной дугой, выраженная в денежных единицах).

 

 

 

На рис. 2 видно, что суммарный избыток товара, имеющийся на складах системы с номерами 1 и 4, равен суммарному недостатку товара, имеющемуся на складах с номерами 3, 6 и 8 той же системы. Перераспределение товара может происходить через склады с номерами 2, 4-7, которые в рассматриваемой задаче и являются промежуточными или транзитными пунктами. Истинным пунктом отправления является лишь склад с номером 1, на котором имеется избыток товара и с которого товар можно только вывозить, а истинными пунктами назначения являются склады с номерами 3 и 8, на которых есть недостаток товара, и на эти склады товары можно только завозить. Заметим также, что между складами с номерами 4 и 5 возможны перевозки в обоих направлениях, но в общем случае ¹ (например, наличие одностороннего движения по кратчайшему маршруту).

 
Таким образом, на рисунке 2 фактически представлена сеть рассматриваемой транспортной задачи с промежуточными пунктами. Формальное описание этой сети удобно представить в виде следующей таблицы 4:

 

 

 

 

 

 

 

 

 Таблица 4:

Номер склада	Объемы перевозок						Избыток (+) или недостаток (-) товара
1 2 3 4 5 6 7 8	-1	1   -1 -1   -1	-1 1     1     1        -1               -1	-1 1       1            -1	1 -1	1 -1	10 0 -3 2 0 -1 0 -8

 

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

Далее построю транспортную таблицу для рассматриваемой транспортной задачи с промежуточными пунктами. Параллельно с построением найду доказательство возможности преобразования этой задачи к классической транспортной задаче.

Таблица 5.

Пункт произ-водства	Пункт потребления							По-став-ки
	2	3	4	5	6	7	8
1 2 4 5 6 7								12 14 12 11 12
Спрос		3		12		12	8

 

На первом этапе в таблице 4 нужно выделить строку для каждого источника и указать его «мощность» (избыток товара на складе). В данном примере источником является только склад с номером 1, мощность которого  = 10. В таблице 5 этому складу будет соответствовать первый пункт производства с объемом поставок, равным 10.

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

На третьем этапе нужно сделать следующее.

1. В таблице 5 выделить строку и столбец  для каждого промежуточного пункта. В данном случае промежуточными пунктами являются склады с номерами 2, 4, 5, 6 и 7, которые в таблице 5 фигурируют как пункты производства и пункты потребления.

2. Для каждого  -го промежуточного пункта определить величину чистого запаса товара, равного объему избытка со знаком плюс либо объему недостатка со знаком минус. В данном случае:

.

3. Определить суммарный объем  избытка  на всех складах системы, используя последний столбец таблицы 4. Суммарный объем избытка представляет собой общий объем перевозок (в единицах измерения товара). В данном случае

4. Считать, что  маршрут транспортировки всего  суммарного объема избытка товара может проходить через любой промежуточный пункт. Это означает, что любой склад с номером , рассматриваемый как промежуточный пункт, может принять весь суммарный объем избытка товара и мощность его стока равна . Таким образом, в данном случае =12, в таблице 5 эти значения фигурируют как спрос.

5. Для каждого -того промежуточного пункта определить мощность его источника , то есть объем товара, который может быть вывезен со склада с номером . Так как на складе с номером величина чистого запаса товара равна , а максимально возможный объем поставок определяется величиной , то . В данном примере

.

В таблице 5 эти значения фигурируют как поставки.

На четвертом этапе необходимо для каждого -го промежуточного пункта ввести переменную  . В данном случае . Интерпретировать переменную  можно как объем товара, который оседает на складе с номером.

При построении транспортной таблицы ранее нами была введена величина , имеющая смысл динамического запаса или буфера в каждом промежуточном пункте. Для каждого -го промежуточного пункта величина  входит как в . Поэтому сумма запроса равна сумме поставок.

Значение  должно быть настолько велико, чтобы оно могло соответствовать любому количеству товара, приходящему через -ый промежуточный пункт при любом допустимом решении исходной задачи. Поэтому значение  принимают равным суммарному объему избытка товара в системе.