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

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

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

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

Рассмотрим пример транспортной задачи, исходные данные к которой представлены в Табл. 8.3.

В этой таблице, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада I, I=1,2,3, потребителю J, J=1,2,3,4. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется 50+70=120 единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в Табл. 8.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.

Таблица 8.3

Исходные данные к транспортной задаче

	Потреби-тель 1	Потреби-тель 2	Потреби-тель 3	Потреби-тель 4	Запасы на складах
Склад 1	2	5	5	5	60
Склад 2	1	2	1	4	80
Склад 3	3	1	5	2	60
Потреб-ности	50	40	70	40	200

Надо спланировать перевозки, т. е. выбрать объемы Xij поставок товара со склада I потребителю J, где I=1,2,3; J=1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:

X11 + X12 + X13 + X14 = 60,

X21 + X22 + X23 + X24 = 80,

X31 + X32 + X33 + X34 = 60,

Во-вторых, известны потребности клиентов:

X11 + X21 + X31 = 50,

X12 + X22 + X32 = 40,

X13 + X23 + X33 = 70,

X14 + X24 + X34 = 40,

Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений.

Целевая функция - издержки по перевозке, которые необходимо минимизировать: 2X11 + 5X12 + 4X13 + 5X14 + X21 + 2X22 + X23 + 4X24 + 3X31 + X32 + 5X33 + 2X34 ð Min.

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

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

< Предыдущая		Следующая >