5. СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

5.1.Транспортные задачи

Впрактике задач линейного программирования очень часто встречаются транспортные задачи.

Характерная постановка: имеется m складов B , B , B ,...,Bm с запасами

b ,b ,...,bm , которые необходимо доставить потребителям D , D ,...,Dn с потребителями d , d ,...,dn . При этом возможна оценка эффективности перевоз-

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

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

цы, называемой матрицей перевозок (табл. 5.1).

						Таблица 5.1
		Матрица перевозок
Склад		Потребитель			Запасы на складе
	D	D	D
B	с	с		с		b
	x	x	x
B	с	с		с		b
	x	x	x
Потребности	d	d	d		d j bi
					j	i

Каждая строка матрицы соответствует пункту отправления (складу), каждый вектор-столбец соответствует пункту назначения (потребителю). Здесь bi ,i , m – запасы, d j , j , n – потребности, cij – стоимость перевозки

единицы продукции, xij – количество перевезенной продукции с i-го склада

j-ому потребителю. Продукция однородная, например, песок. Транспортная задача сбалансирована (или закрыта), т.е.

bi d j .
i	j

Для приведенной матрицы перевозок справедливы следующие соотношения:

110

общая стоимость перевозок

Q(x) c x c x c x c x c x c x min, (5.1) xij X

ограничения задачи

x x x b
x		x		x		b
x		x		d
X x		x		d
x		x		d
		, i , , j , ,
x	ij

-возможности складов

(5.2)

- потребности потребителей

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

трудно определить сколько получил 3-ий потребитель. Следовательно, при решении задачи симплекс-методом, где необходимо иметь систему независимых уравнений ограничений, одно из неравенств системы ограничений необходимо вычеркнуть, например последнее.

Условие xij означает, что не существует обратных перевозок от потребителей D j к складам Bi , при этом пропускная способность каналов пе-

ревозок не ограничена сверху.

В общем виде сбалансированная транспортная задача может быть представлена в виде

	m	n
	Q(x) cij xij min,
	i j		x X
	n		m	m
где X x : x E m n , x , xij bi , i , m, xij d j , j , n, bi
	j		i	i

(5.3)

d j .j

Кроме симплекс-метода ЛП для решения транспортной задачи (5.3) можно использовать специальные методы, например метод северо-западного угла и метод потенциалов. Эти методы позволяют скорее найти решение и представляют модификации симплекс-метода ЛП.

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

	m n
	Q(x) cij xij min,
	i j	x X
	n	m	m
X x : x E m n , x , xij bi , i		,...,m, xij d j , j , n, bi
	j	i	i

(5.4)

d j .j

111

сm , j

Если возможности складов превышают потребности, то постановка задачи имеет вид

	m	n
	Q(x) сij xij min,					(5.5)
	i j		x X
	n		m	m	n
X x : x E mn , x , xij bi , i , m, xij				d j , j , n, bi d j
	j		i	i	j

Постановка задач (5.4) и (5.5) носит название открытых (несбаланси-

рованных) транспортных задач.

Общих методов решения таких задач нет. Симплекс-метод же требует значительного объема вычислений.

Если для постановки (5.4) безразлично какие из потребителей недополучат продукцию, то ее легко свести к сбалансированной транспортной задаче. Для этого введем фиктивный склад (строку) с запасом (объемом), равным

n	m
недостатку продукции, т.е. небалансу bm d j bi . При этом стоимость
j	i

перевозок от этого склада ко всем потребителям принимается равной нулю, j ,...,n . Полученное решение xm , j соответствует количеству не-

дополученной продукции соответствующим потребителем.

Если для постановки (5.5) безразлично на каких складах останется продукция, то для перехода к сбалансированной задаче вводят фиктивного по-

m	n
требителя, с объемом потребностей dn bi d j . Стоимость перевозок
i	j

также равна нулю ci,n ,i , ,...,m.

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

Рассмотрим постановку задачи (5.4) (превышение спроса над предложением).

Пусть убыток, к которому приводит недополучение единицы продукции j-м потребителем оценивается штрафом rj .

Полагая, что стоимость перевозок с фиктивного склада (поставщика) j- му потребителю сm , j rj , получаем сбалансированную транспортную зада-

чу вида

m n
Q(x) cij xij min,		(5.6)
i j	x X

112

	n	m
X x : x E (m )n , xij , j , n,i , m , xij bi ,i , m , xij d j , j , n
	j	i

,

которую решаем либо методом потенциалов, либо северо-западного угла, либо симплекс-методом ЛП.

Для несбалансированной задачи (5.5) (превышение предложения над спросом) остатки на i-ом складе оцениваются штрафом сi,n ri . В этом слу-

чае имеем

	m n
	Q(x) cij xij min,
	i j	x X
		n	m
X x : x E m(n ) , xij ,i , m, j , n , xij bi ,i , m xij
		j	i

(5.7)

d j , j , n .

Значения штрафов в задачах (5.6) и (5.7) выбирают максимальными

или больше, чем стоимость перевозок cij	в исходной матрице перевозок
cm , j max cij ,ci,n max cij .		(5.8)
i, j	i, j

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

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

	m	n
	Q(x) cij xij min				(5.9)
	i j		x X
	n		m
X x : x E m n , xij bi ,i , m, xij d j , j , n, xij pij					,
	j		i

где pij - пропускная способность магистрали (i, j).

Эта задача может оказаться неразрешимой. Здесь применяются специальные методы решения таких задач (модификации метода потенциалов), которые либо находят решение, либо указывают на ее неразрешимость.

Принципиально меняется характер задачи, если за критерий оптимальности выбрано время доставки грузов. Задача оказывается нелинейной, вследствие нелинейности целевой функции.

Другой большой класс задач связан с перевозкой неоднородной продукции потребителям. В этом случае задача формулируется как многоиндексная. Например, трехиндексная

113

m n r
Q(x) cijk xijk min,		(5.10)
i j k	x X

n

xijk bik ,i , m, k , r

j

m

X xijk d jk , j , n, k , r

i

x , x E m n r .

Рассмотрим пример решения транспортной задачи в Mathcad и Matlab для матрицы перевозок, определяемой табл. 5.1 (рис. 5.1).

Ис ходные данные с баланс ированной задачи
c11 2	c12 6	c13 3	c21 5	c22 3	c23 1	b1 70	b2 30
d1 40	d2 55	d3 5

Q(x11 x12 x13 x21 x22 x23) c11 x11 c12 x12 c13 x13 c21 x21 c22 x22 c23 x23

x11 0 x12 0		x13 0	x21 0		x22 0	x23 0	- начальная точка п оис ка
Given
x11 x12 x13		b1	x11 x21		d1	x11 0	x21 0
x21 x22 x23		b2	x12 x22		d2	x12 0	x22 0
			x13 x23		d3	x13 0	x23 0

xx MinimizeQ( x11 x12 x13 x21 x22 x23)

T		25	5 0	30 0 )		Q xx xx xx xx xx xx							335
xx ( 40
							0	1	2	3	4	5
Решение задачи че рез матричные переменные
n 2		k 1		i 0 k		j 0 n				xi j	0
	2	6	3		70			40
cc				b		d		55
	5		1		30
		3
								5
		k	n	cc i jxi j
Q1(x)						2 x0 0	6 x0 1 5 x1 0					3 x0 2 3 x1 1 x1 2
	i 0		j 0

Рис. 5.1. Пример решения транспортной задачи в Mathcad и Matlab

114