Модификации транспортной задачи

1) Недопустимые перевозки.

В ряде случаев поставки по некоторым каналам оказываются недопустимыми. Это, например, могут быть условия технологии (предприятии, производящее продукцию на экспорт не может потреблять сырье низкого качества), отсутствие у потребителя подходящей взлетно-посадочной полосы для приема воздушных транспортных средств и пр. Следовательно, в исходной задаче набор переменных xij не является полным, их количество меньше произведения m*n. Для решения этой проблемы некоторые клетки шахматной таблицы при счете нужно исключить из числа используемых. Для этого в эти «запретные» клетки нужно задать очень большие удельные транспортные (превышающие самые большие значения параметров сij). Точное значение в данном случае неважно, однако, оно должно быть больше, чем остальные значения стоимости, указанные в таблице. Если исходная задача разрешима, то в ходе реализации метода потенциалов несуществующие переменные xij уйдут из числа базисных. Если же все-таки окажется, что в оптимальный базис попала хотя бы одна из запретных клеток, и значение соответствующей переменной положительно, то это будет означать, что исходная задача была неразрешимой.

Пример: Исходная транспортная таблица задачи с запретами, составленная методом наименьшего элемента, приведена в таблице.

Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=252	B5=177
Распределение перевозок
A1=227	40	5	42	66	20
	200			27
A2=152	70	15	31	25	40
		50	27	75
A3=225	50	40	40	10	52
			225
A4=175	14	25	52	52	21
100				75

В силу некоторых обстоятельств поставки по каналу А1-В2 невозможны.

Для решения этой задачи поставим в соответствующую клетку транспортной таблицы вместо реальной стоимости перевозки ∞ (сколь угодно большое число, большее любого наперед заданного числа). Решаем эта задачу методом потенциалов.

2) Максимизация прибыли (дохода)

Проблемой также может быть не минимизация суммарных транспортных затрат, а максимизация прибыли от выполнения перевозок – в качестве параметров сij в этом случае будет удельная (в расчете на единицу перевозимого продукта) прибыль из каждого пункта производства в каждый пункт потребления. Для того, чтобы перейти к стандартной постановке на минимум значения целевой функции и не изменять алгоритм решения, в этом случае достаточно поменять знаки коэффициентов целевой функции на противоположные.

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

3) Задача с ограничениями типа «=» Еще один пример, приводящий к нестандартной шахматной таблице – наличие среди ограничений (2) или (3) строгих равенств, т.е. требования вывоза из некоторых пунктов всех наличных запасов товара или доставки в пункты потребления заданного объема продукции.

Фактически этот пример сводится к случаю недопустимых перевозок – отсутствие дополнительной переменной, т.е. возможности поставки в фиктивный пункт потребления из этих пунктов производства. В этом случае, в число «запретных» включаются соответствующие клетки последнего столбца или стоки шахматной таблицы. Либо удается обойтись без них, либо они временно «открываются», но затраты на поставки в фиктивный пункт поставки или потребления ставятся не нулевыми, а очень большими.

Пример. Исходная транспортная таблица задачи имеет вид:

Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=252	B5=177
Распределение перевозок
A1=237!!! Да-да!	40	5	42	66	20
	150
A2=152	70	15	31	25	40
A3=225	50	40	40	10	52
A4=175	14	25	52	52	21

Первый поставщик должен поставить второму потребителю ровно 150 ед продукции.

Решая эту задачу, получаем: сумма запасов равна 237+152+225+175=789

Сумма потребностей: 100+200+50+252+177=779 Следовательно, вводим фиктивного потребителя с потребностью В6=10, но тариф принимаем равным бесконечности.

4) Задача с обязательными поставками В качестве примера решения такой задачи рассмотрим исходные данные, приведенные в таблице.

Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=250	B5=150
Распределение перевозок
A1=200	40	15	22	66	20
A2=150	7	25	52	25	40
A3=225	55	40	40	52	52
A4=175	55	25	52	14	33

Пусть, в силу определенных обстоятельств (например, госзаказ), третий поставщик А3, несмотря на фактические затраты, обязан поставить четвертому потребителю В4 не менее 100 единиц продукции. Исключим эту обязательную поставку из транспортной таблицы (см. таблицу 2.5.7).

Таблица 2.5.7

Транспортная таблица с исключенными обязательными поставками
Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=150	B5=150
Распределение перевозок
A1=200	40	15	22	66	20
A2=150	7	25	52	25	40
A3=125	55	40	40	52	52
A4=175	55	25	52	14	33

Затем решается обычная транспортная задача, но при определении суммарных затрат на перевозки необходимо учесть и затраты на обязательные поставки: 100×52=5200.

5) Задача с ограниченной пропускной способностью

Если, например, по маршруту AiBj можно поставить не более q единиц груза, то Ai-ая строка матрицы разбивается на две строки – Ai1 и Ai2. В первом столбце спрос принимается равным Ai 1= Ai -q, во втором – Ai 2=q. Несмотря на то, что фактические затраты сij в обоих строках одинаковы и равны исходным, в строке Ai1 вместо истинного тарифа сij ставится искусственно завышенный тариф ∞ (клетка блокируется). Затем задача решается обычным способом.

Пример. Пусть в силу некоторых обстоятельств по каналу А3-В4, несмотря на низкую стоимость перевозок, можно поставить не более 125 единиц продукции.

Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=250	B5=150
Распределение перевозок
A1=200
A2=150
A3=225
A4=175

Тогда представим поставщика А3 в виде двух поставщиков – А31 и А32, находящихся в одном и том же месте. Производственные мощности этих поставщиков соответственно 100 (ограничение на поставку) и 125 единиц. Естественно, что затраты на перевозки и них останутся такими же, как и у А3, однако, для выполнения поставленного ограничения у поставщика А31 по каналу А31-В4 поставим запрет ∞.

Исходная транспортная таблица задачи с ограниченной пропускной способностью, подготовленная к решению
Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=250	B5=175
Распределение перевозок
A1=225
A2=150
A31=100				∞
A32=125
A4=175

Таким образом, получается обычная задача с запретами. Результаты решения этой задачи приведены в таблице.

Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=250	B5=150
Распределение перевозок
A1=200
A2=150
A31=100				∞
A32=125
A4=175

Как видно из таблицы, третий поставщик будет поставлять четвертому потребителю не более 125 единиц продукции, а оставшиеся 100 ед. он поставит потребителю А1.

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

Необходимо распределить работников по видам работ или же распределить отдельные виды работ по работникам или по предприятиям, которые могут их выполнить. Пусть ai – суммарный за рассматриваемый период фонд рабочего времени i-го работника, sij – время, требующееся работнику i для выполнения единицы работы j (изделия вида j); bj – суммарный объем работ j-го вида, который необходимо выполнить (количество изделий вида j, которое необходимо произвести). Требуется распределить фонд рабочего времени каждого работника по выполняемым им видам работ так, чтобы минимизировать суммарное рабочее время, требующееся для выполнения всех работ.

Математическая постановка такой задачи полностью идентична стандартной транспортной задаче типа (1 – 4). Также идентична ей будет и постановка задачи для решения проблемы распределения по «подрядчикам» разных работ (bj – объем работ j-го вида, ai – суммарный объем работ i-го вида, который может выполнить i-й подрядчик, сij – плата за выполнение единицы работы вида j, которую берет подрядчик i) таким образом, чтобы минимизировать суммарную стоимость выполнения всех работ.

Решить самостоятельно:

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

Таблица 13.22. Значения спроса и производственных мощностей
Месяц	Производственные мощности, изделий	Спрос, изделий
1	300	300
2	350	275
3	325	400
4	375	300

К началу первого месяца имеется начальный запас изделий объемом 50 шт. Изделия можно производить как для удовлетворения текущего спроса, так и создания запаса для удовлетворения спроса в последующие месяцы. Если спрос на изделия в течение месяца не удовлетворяется полностью, то прибыль от продажи теряется. Издержки производства составляют 100 ф. ст. за единицу изделия. Стоимость хранения запасов равна 2 ф. ст. за единицу изделия. Каков оптимальный план производства?

Решение:

Данную ситуацию можно формализовать, используя транспортную таблицу, в которой строками являются начальный запас и объемы производства изделий в месяц, а столбцы отражают ежемесячный спрос на продукцию. Маршруты (клетки), в которых подразумевается удовлетворение спроса за текущий месяц в следующих месяцах, считаются недопустимыми. В табл. 13.23 этим клеткам соответствуют бесконечные значения стоимости.

Таблица 13.23. Данные производственного плана для месяцев 1—4
	Стоимость единицы изделия, ф. ст. Месяцы	Общее предложение
Ml	М2	МЗ	М4
Запас	Ml		4	6	8	50
Производство	Ml	100	102	104	106	300
М2		100	100	104	350
МЗ				102	325
М4				100	375
Общая потребность	300	275	400	300

Решение этой транспортной задачи производится с помощью обычного алгоритма, позволяющего минимизировать стоимость выполнения производственного графика

Пример 2. Имеется 4 поставщика и 5 потребителей однородной продукции. Каждый поставщик может поставлять свою продукцию любому из потребителей. Затраты на перевозку единицы продукции от каждого поставщика к каждому потребителю, а также запасы продукции и потребности потребителей представлены в таблице. Необходимо так распределить перевозки, чтобы суммарные затраты были минимальными при условии, что третий поставщик поставит продукцию второму потребителю в количестве 100 ед.

Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=252	B5=177
Распределение перевозок
A1=237	40	5	42	66	20
A2=152	70	15	31	25	40
	100
A3=225	50	40	40	10	52
A4=175	14	25	52	52	21

Пример 3. Три торговых склада (X, Y и Z) могут осуществлять поставки 6, 3 и 4 единиц продукта в три магазина (L, М и N), спрос которых равен 4, 5 и 1 единицам соответственно. Значения единичной стоимости транспортировки указаны в приведенной ниже таблице.

Таблица 13.24. Исходная информация
Торговый склад	Магазин ф. ст./ед.	Общее предложение
L	М	N
X Y Z	6 5 2	4 3 3	9 2 6	6 3 4
Общая потребность	4	5	1

Как следует распределить перевозки, чтобы общая стоимость транспортировки была минимальной?

Пример 4. Имеется 4 поставщика однородной и 5 потребителей этой продукции. Каждый поставщик может поставлять свою продукцию любому из потребителей. Затраты на перевозку единицы продукции от каждого поставщика к каждому потребителю, а также запасы продукции и потребности потребителей представлены в таблице. Необходимо так распределить перевозки, чтобы суммарные затраты были минимальными при условии, что по каналу А3-В5, несмотря на низкую стоимость перевозок, можно поставить не более 100 единиц продукции.

Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=252	B5=177
Распределение перевозок
A1=237	40	5	42	66	20
A2=152	70	15	31	25	40
A3=225	50	40	40	10	52
A4=175	14	25	52	52	21

Дата добавления: 2015-10-13