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

Классическая постановка транспортной задачи по критерию стоимости

Имеется т пунктов отправления А1; А2, ..., Ат, на которых сосредоточены запасы однородного груза в известных количествах аь а2, ..., ат. Имеются также п пунктов потребления Вь В2,..., Вп, подавшие заявки на доставку этих грузов в объемах Ьь Ь2, ..., Ьп. Предполагается, что общее количество грузов на пунктах отправления равно суммарной заявке на доставку грузов. Известны цены с,-,- доставки одной единицы груза из каждого пункта отправления А, в каждый пункт прибытия В,. Требуется составить такой план перевозок грузов, чтобы общая стоимость всех заявленных перевозок была наименьшей.

Построим математическую модель задачи. Пусть — объем доставки грузов из А, в Bj по плану (предполагается, что все х1} > 0). Тогда общие плановые затраты на перевозку определяются суммой

Ограничения задачи формализуются исходя из условия замкнутости задачи — суммарный объем вывезенного груза равен объему доставленного груза:

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

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

Требуется получить план перевозок (т.е. определить все элементы матрицы X* = |х*|), минимизирующий затраты на его реализацию, т.е.

Соотношения (14.15)—(14.18) представляют собой математическую модель замкнутой транспортной задачи (ТЗ) по критерию стоимости. По форме построенная модель (14.15)—(14.18) —это модель линейного программирования. Следовательно, для решения транспортной задачи применимы методы линейного программирования. Вместе с тем можно заметить, что данная модель представляет собой частный случай ОЗЛП (видно, что в ограничениях (14.16) и (14.17) все неизвестные имеют коэффициент, равный единице). Это обстоятельство позволило разработать специальные, более простые методы и приемы решения транспортных задач, некоторые из которых будут здесь рассмотрены. Кроме того, благодаря условию (14.15) ТЗ всегда имеет решение.

Следует заметить, что к моделям такого типа сводится множество встречающихся на практике распределительных задач, например задача о назначениях на должности, задача о закреплении оборудования и т.п. Название же «транспортная задача» применяют к моделям вида (14.15)—(14.18) в силу исторических причин.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >