Различные технико-экономические и экономические задачи менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования. В книге [1] приведен обширный перечень публикаций, посвященный многочисленным применениям линейного программирования в металлургии, угольной, химической, нефтяной, бумажной и прочих отраслях промышленности, в проблемах транспорта и связи, планирования производства, конструирования и хранения продукции, сельском хозяйстве, в научных исследованиях, в том числе экономических, и даже при регулировании уличного движения.
В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.
|
|
Например, может идти речь о перевозке песка - сырья для производства кирпичей. В Москву песок обычно доставляется самым дешевым транспортом - водным. Поэтому в качестве складов можно рассматривать порты, а в качестве запасов - их суточную пропускную способность. Потребителями являются кирпичные заводы, а их потребности определяются суточным производством (в соответствии с имеющимися заказами). Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным правилам, на которых не имеет смысла останавливаться. Поэтому затраты на доставку товара с определенного склада тому или иному потребителю можно считать известными.
Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 3. В ней, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада i, i = 1,2,3, потребителю j, j = 1,2,3,4. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется 50+70 =120 единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.
|
|
Таблица 3.
Исходные данные к транспортной задаче.
Потреби-тель 1 | Потреби-тель 2 | Потреби-тель 3 | Потреби-тель 4 | Запасы на складах | |
Склад 1 | |||||
Склад 2 | |||||
Склад 3 | |||||
Потреб-ности |
Надо спланировать перевозки, т.е. выбрать объемы Хij поставок товара со склада i потребителю j, где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:
X 11 + Х 12 + Х 13 + Х 14 = 60,
X 21 + Х 22 + Х 23 + Х 24 = 80,
X 31 + Х 32 + Х 33 + Х 34 = 60.
Во-вторых, известны потребности клиентов:
X 11 + Х 21 + Х 31 = 50,
X 12 + Х 22 + Х 32 = 40,
X 13 + Х 23 + Х 33 = 70,
X 14 + Х 24 + Х 34 = 40.
Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений.
Целевая функция - издержки по перевозке, которые необходимо минимизировать:
F = 2 X 11 + 5 Х 12 + 4 Х 13 + 5 Х 14 + X 21 + 2 Х 22 + Х 23 + 4 Х 24 +
+ +3 X 31 + Х 32 + 5 Х 33 + 2 Х 34 → min.
Кроме обсуждаемой, рассматриваются также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.
Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта.