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

Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.

На автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:

• прикрепление потребителей ресурса к производителям;

• привязка пунктов отправления к пунктам назначения;

• взаимная привязка грузопотоков прямого и обратного направлений;

• отдельные задачи оптимальной загрузки промышленного оборудования;

• оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Цели

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

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

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

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

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

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

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

Модели

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения.

Имеются m пунктов отправления груза А₁, А₂, ..., А_m и объемы отправления по каждому пункту a₁, a₂, ..., a_m.

Известна потребность в грузах b₁, b₂,...,b_n по каждому из n пунктов назначения B₁, B₂,..., B_n.

Задана также матрица стоимостей с_ij, (i=1,...,m, j=1,...,n) доставки груза из пункта i в пункт j.

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

В общем виде исходные данные представлены в табл. 1.

Таблица 1

Исходные данные

Потреби-тели Постав- щики	B1	B2	…	Bn	Запасы (объемы отправления)
A1	С11 X11	С12 X12	…	С1n X1n	a1
A2	С21 X21	С22 X22		С2n X2n	a2
	…	…	…	…	…
Am	Сm1 Xm1	Сm2 Xm2		Сmn Xmn	am
Потребность	b1	b2		bn

Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой.

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

, где i=1,…,m

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

, где j=1,…,n

Из экономических соображений должно выполняться также условие неотрицательности переменных:

i=1,…,m; j=1,…,n

Перевозки необходимо осуществить с минимальными транспортными издержками. Следовательно, целевая функция примет вид:

Таким образом, математическая формализация простейшей транспортной задачи закрытого типа имеет следующий вид:

где i=1,2,…,m; j=1,2,…,n

В этой модели вместо матрицы стоимостей перевозок могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (11), уравнение баланса является обязательным условием решения закрытой транспортной задачи, поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если

• потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

• запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.

1. Общая модель транспортной задачи:

(11)

, где i=1,2,…,m (12)

, где j=1,2,…,n (13)

где i=1,2,…,m; j=1,2,…,n (14)

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

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

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

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

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

Это необходимое и достаточное условие существования допустимого плана значения.

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

   1. – излишек продукта.

Способ сведения к замкнутой задаче. Пусть b_n+1 – величина избытка продукции, то есть ; c_i,n+1 – штраф за единицу продукта, не реализованного в пункте i; y_i – количество продукта, не реализованного в пункте i.

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

, где i=1,2,…,m

, где j=1,2,…,n

i=1,2,…,m; j=1,2,…,n

2. – дефицит продукта.

Способ сведения к замкнутой задаче. Пусть a_m+1 – величина дефицита продукции, то есть ; c_m+1,j – штраф за единицу продукта, недопоставленного в пункт j; y_j – количество продукта, не реализованного в пункте j.

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

, где i=1,…,m

, где j=1,…,n

i=1,…,m; j=1,…,n

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

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

М=max(c_ij ) max , i=1,…,m; j=1,…,n.

Т

, если (i,j)  Е,

, если (i,j)  E.

огда

В оптимальном плане транспортной задачи при ограничениях (12)–(1

4) x_ij=0, если (i,j)  E.

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

6. Транспортная задача с ограничениями на пропускную способность. Если объем перевозок из пункта i в пункт j ограничен величиной w_ij, то в задаче (11)–(14) вводится дополнительное ограничение: x_ij  w_ij.

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

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

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

(15)

, где i=1,…,m (16)

, где i=m+1, ..., k (17)

, где j=1,…,n (18)

где i=1,…,k; j=1,…,n (19)

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

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

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

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

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

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

Транспортным задачам присущи следующие особенности:

• распределению подлежат однородные ресурсы;

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

• все переменные выражаются в одинаковых единицах измерения;

• во всех уравнениях коэффициенты при неизвестных равны единице;

• каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

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

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

Рассмотрим, как это можно сделать в среде электронных таблиц Microsoft Excel на примере следующей задачи