А.И. Орлов       
Основы теории принятия решениий       
Учебное пособие. Москва, 2002.

5. Методы решения задач линейного программирования
    

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

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

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

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

Табл. 5. Исходные данные к транспортной задаче.

Потреби-тель 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

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

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

X11 + Х12 + Х13 + Х14 = 60 ,

X21 + Х22 + Х23 + Х24 = 80 ,

X31 + Х32 + Х33 + Х34 = 60 .

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

X11 + Х21 + Х31 = 50 ,

X12 + Х22 + Х32 = 40 ,

X13 + Х23 + Х33 = 70 ,

X14 + Х24 + Х34 = 40 .

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

Целевая функция - издержки по перевозке, которые необходимо минимизировать:

F = 2X11 + 5Х12 + 4Х13 + 5Х14 + X21 + 2Х22 + Х23 + 4Х24 + +3X31 + Х32 + 5Х33 + 2Х34 → min .

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

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

Предыдущая страница | Оглавление | Следующая страница