Открытая транспортная задача

Глава 5. Транспортная задача

Цели

В данной главе рассматривается задача транспортировки продук­та, который в определенных количествах предлагается различны­ми производителями. Известны потребности нескольких потреби­телей в этом продукте. Требуется определить, от каких производи­телей и в каких объемах должны получать продукт потребители. Поставки должны осуществляться таким образом, чтобы совокуп­ные издержки на транспортировку продукта были минимальными.

После того как вы выполните задания, предлагаемые в этой гла­ве, вы будете уметь составлять и использовать для экономическо­го анализа:

• замкнутую и открытую транспортные задачи;

• транспортную задачу с запретами;

• транспортную задачу с фиксированными перевозками;

• транспортную задачу с ограничениями на пропускную спо­собность;

• транспортную задачу с фиксированными доплатами;

• транспортную таблицу.

Модели

Обозначения:

а_i — величина предложения продукта в пункте i (i = 1,..., n);

b_j — величина спроса на продукт в пункте j (j = 1,..., т);

c_ij — затраты на транспортировку единицы продукта из пункта i в пункт j;

x_ij — количество продукта, перевозимого из пункта i в пункт j.

Модель транспортной задачи:

Здесь (1) — целевая функция (минимум затрат на транспортиров­ку продукта);

(2) — ограничения по величине предложения в каждом пунк­те производства;

(3) — ограничения по величине спроса в каждом пункте по­требления;

(4) — условия неотрицательности объемов перевозок.

1. Замкнутая транспортная задача. Общее предложение равно общему спросу:

Это необходимое и достаточное условие существования допу­стимого плана задачи (1)—(4).

Открытая транспортная задача.

а) — излишек продукта

Способ сведения к замкнутой задаче. Пусть b_{m +1} — величина избытка продукции, т.е. - штраф за еди­ницу продукта, не реализованного в пункте i; у_i — количество про­дукта, не реализованного в пункте i.

Замкнутая транспортная задача имеет вид

б) — дефицит продукта.

Способ сведения к замкнутой задаче. Пусть а_{n +1} — величина дефицита продукции, т.е. - штраф за еди­ницу продукта, недопоставленного в пункт j; у_j — количество про­дукта, недопоставленного в пункту.

Замкнутая транспортная задача имеет вид

3. Транспортная задача с запретами. Пусть Е — множество пар индексов (ij), таких, что из пункта i в пункт j допускается транс­портировка продукта. Между любыми другими двумя пунктами транспортировка не допускается.

Пусть М— большое число, например

Тогда

В оптимальном плане { } транспортной задачи при ограничениях (2)—(4) x_ij = 0, если (i,j) Ï Е.

4. Транспортная задача с фиксированными перевозками. Если объем перевозок между пунктами i и j задан, то в задаче (1)—(4) вводится дополнительное ограничение: x_ij = v_ij, где v_ij — заданный объемперевозок.

5. Транспортная задача с ограничениями на пропускную способ­ность. Если объем перевозок из пункта i в пункт j ограничен ве­личиной w_ij, то в задаче (1)—(4) вводится дополнительное огра­ничение: x_ij £ w_ij.

6. Транспортная задача с фиксированными доплатами. Предпо­ложим, что в открытой транспортной задаче имеет место дефицит продукта и для его устранения в пунктах i = п + 1,..., k воз­можно создание новых мощностей d_i.

Пусть переменные z_i = 1, если в пункте i (i = п + 1,..., k) вво­дятся мощности d_i и z_i = 0, если в пункте i мощности не вводят­ся. Издержки на ввод мощностей d, в пункте i (i = n + 1,..., k)составляют и_i.

С учетом возможности создания новых мощностей транспорт­ная задача может быть записана в следующем виде:

Здесь (5) — целевая функция (минимум затрат на транспортиров­ку и ввод мощностей);

(6) — ограничения по величине предложения в каждом су­ществующем пункте производства;

(7) — ограничения по величине предложения в каждом но­вом пункте производства;

(8) — ограничения по величине спроса в каждом пункте по­требления;

(9) — условия неотрицательности объемов перевозок.

Помимо непрерывных переменных x_ij в модель включены бу­левы переменные z_i,. Задача (5)—(9) является задачей линейного программирования со «смешанными» переменными.

Все приведенные модели описывают транспортную задачу в виде задачи линейного программирования. В такой форме она может быть решена стандартными средствами линейного програм­мирования, например симплекс-методом.

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

Большинство специальных алгоритмов решения транспортной задачи использует исходную информацию в форме транспортной таблицы:

Оптимальный план перевозок имеет вид