РОЗРАХУНКОВЕ ЗАВДАННЯ 1. ТРАНСПОРТНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ

Короткі теоретичні відомості

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

Пусть в p пунктах отправления находятся соответственно a1 , a2 , …, a p

единиц однородного груза, который должен быть доставлен q						потребителям в
количествах b1 , b2 , …, bq единиц. Заданы стоимости cik				перевозок единицы гру-
за из	i го пункта отправления k му пункту потребления. Обозначим через
xik 0	(i 1,2,..., p; k 1,2,...q)		количество единиц груза,	перевозимого из i го
пункта отправления k му потребителю; тогда переменные xik						должны удовле-
				q
творять следующим ограничительным условиям: 1)				xik	ai	(i 1,2,..., p) ; 2)
				k 1
p
xik bk		(k 1,2,..., q) ; 3)	xik 0 . Суммарные затраты на		перевозки равны

i 1

L c11x11 c12 x12 ... cpq xpq . Классическая транспортная задача является сбалан-

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

p

ai

i 1

q

bk .

k 1

Требуется найти pq переменных xik , удовлетворяющих указанным усло-

виям и минимизирующих целевую функцию L . Решение такой задачи разбивается на два этапа:

1)определение исходного опорного решения;

2)построение последовательных итераций, т.е. приближение к оптимальному решению.

1. Определение исходного опорного решения.

Пусть мы имеем таблицу исходных данных задачи. Исходное решение будем строить по так называемому правилу “северо-западного угла”.

9

ai \ bk	b1		b2		…	bk			…	bq
		c		c				c			c1q
a1		11		12	…			1k	…
	x		x			x1k				x1q
	11		12
a2		c21		c22	…			c2k	…		c2q
	x21		x22			x2k				x2q
…	…		…		…	…			…	…
ai		ci1		ci 2	…			cik	…		ciq
	xi1		xi 2			xik				xiq
…	…		…		…	…			…	…
a p		c p1		c p 2	…			c pk	…		c pq
	x p1		x p 2			x pk				x pq

Заполним вышеуказанную таблицу, начиная с левого верхнего угла, двигаясь далее или по строке вправо, или по столбцу вниз. В клетку (1, 1) занесем меньшее из чисел a1 и b1 , т.е. x11 min{a1 ,b1} .

Если a1 b1 , то x11 b1 и первый столбец “закрыт”, т.е. потребности первого потребителя удовлетворены полностью. Двигаемся далее по первой строке, за-

писывая в соседнюю клетку (1, 2) меньшее из чисел	a1 b1 и b2 , т.е.
x12 min{a1 b1 ,b2 }.
Если же b2 a1 , то аналогично “закрывается” первая строка и далее пере-
ходим к заполнению соседней клетки (2, 1), куда заносим	x21 min{a2 ,b1 a1} .

Будем продолжать этот процесс до тех пор, пока на каком-то этапе не исчерпываются ресурсы a p и потребности bq .

Задача.

В двух пунктах отправления А и B находится соответственно 150 и 90 т горючего. В пункты 1, 2, 3 требуется доставить соответственно 60, 70 и 110 т горючего. Стоимости перевозки тонны горючего из пункта А в пункты 1, 2, 3 составляют соответственно 6, 10 и 4 ден. ед., а из пункта В – 12, 2 и 8 ден. ед. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей.

Решение.

Запишем исходные данные в таблицу.

		1		2		3
	ai \ bk	60		70		110
А	150		6		10		4
		60		70		20
В	90		12		2		8
						90
		10

Заполнение начнем с ячейки (1, 1): x11 min{150,60} 60 , первый столбец закрыт. Переходим к ячейке (1, 2): x12 min{150 60,70} 70 , второй столбец закрыт; далее, переходим к клетке (1, 3): x13 min{150 60 70,110} 20 . Так как в

третьем столбце оказался остаток, равный 90, то переходим к заполнению клетки (2, 3), куда заносим x23 min{90,90} 90 . Поскольку остатки по строке и

столбцу равны нулю, опорное исходное решение построено. Этому плану соответствуют затраты в количестве L 6 60 10 70 4 20 8 90 1860 ден. ед.

В правиле “северо-западного угла” не учитывается величина затрат cik , а

поэтому исходное опорное решение часто может быть далеким от оптимального.

Применяют также прием “минимального элемента”, в котором учитывается величина cik . В этом случае построение исходного опорного решения начи-

нают с клетки с наименьшей величиной cik , в данном примере – с клетки (2, 2),

где c22 2 . В эту клетку заносим x22 min{a2 ,b2 } min{90,70} 70 .
						1				2				3
				ai \ bk		60				70				110			Остаток
		А		150				6			10				4		60
					60									90
		В		90				12			2					8	20
										70				20
				Оста-		0				0				20
			ток
Остатки по строке и столбцу записываем в соответствующие клетки стро-
ки и столбца остатков. Столбец b2								закрыт. Теперь переходим к клетке (1, 3), так
как после		c22 2		наименьшим				является c13				4 .		В клетку				(1, 3)		заносим
x13 min{a1		b1 ,b3} min{150 60,110} 90 .								Затем		переходим					к клетке			(1, 1):
x11 min{a1 ,b1} min{150,60} 60 . Наконец,										переходим к клетке (2,								3), в которую
заносим x23 min{a2				b2 ,b3} min{90 70,110} 20 .
Применяя это правило, мы получили другой вариант исходного опорного
решения, при котором затраты							L 6 60 4 90 2 70 8 20 1020											ден.		ед., т.е.
сумма затрат ближе к оптимальному плану.

1. Построение последовательных итераций.

Получив исходное опорное решение, перейдем теперь к построению новых опорных решений, улучшающих друг друга: для этого применим метод потенциалов.

Итак, после построения исходного опорного решения все переменные разбиты на две группы: xkl базисные и x pq свободные; линейные функции сто-

имости перевозок выразятся через свободные переменные так: L pq x pq 0 .

pq

11

c /pq

Для нахождения коэффициентов pq при свободных переменных сопоставим каждому пункту отправления Ai некоторую величину ui (i 1,2,..., m) , которую назовем потенциалом пункта Ai , и каждому пункту назначения B j величину v j потенциал пункта B j . Свяжем эти величины равенством uk vl ckl , где ckl стоимость перевозки одной тонны груза из пункта Ak в пункт Bl . Доказывается, что совокупность уравнений uk vl ckl , составленных для всех базис-

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

u p vq c/pq , и назовем ее косвенной стоимостью (в отличие от данной стоимости c pq ). Тогда коэффициенты при свободных переменных в соотношении

L pq x pq 0 определяются с помощью равенства pq c pq c/pq .

pq

Если все величины pq неотрицательны, то исходное решение является оп-

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

Воспользуемся изложенными общими понятиями и продолжим решение нашей задачи. Мы получили исходное опорное решение (следуя правилу “ми-

нимального

элемента”):

x11 60 ,

x12 0 ,

x13 90 ,

x21

0 ,

x22 70 ,

x23 20 ,

L 1020 . Для нахождения потенциалов необходимо решить систему

u1 v1 c11 6 ,

u1 v3 c13 4 ,

u2 v2 c22 2 ,

u2 v3 c23 8 .

Значение одного из неизвестных зададим произвольно,

например u1

1.

Тогда v 5 ,

v

3

3

, u

2

5, v

2

3. Далее вычисляем косвенные стоимости c /

:

1

pq

c/

u v

2

2 ,

c/ u

2

v 10 .

12

1

21

1

Подсчитаем теперь разности pq c pq c/pq :

12

c c/ 10 ( 2) 12 ,

21

c

21

c/ 12 10 2 .

12

12

21

Следовательно,

выражение

L

через

свободные

переменные имеет

вид

L 1020 12x12 2x21 . Среди коэффициентов при переменных в правой части нет отрицательных. Значит, исходное опорное решение является оптимальным.

Решим теперь эту же задачу при условии, что исходное решение получено

по правилу “северо-западного

угла”,

т.е. x11 60 , x12 70 , x13 20 , x23

90 ,

L 1860 . Для нахождения потенциалов необходимо решить систему

u1 v1 c11 6 ,

u1 v2 c12 10 ,

u1 v3 c13 4 ,

u2 v3 c23 8 .

Полагая u1

1,

получим v1 5 , v2 9 ,

v3 3 , u2 5 . Вычисляем косвенные

стоимости c

/

:

c/

u

2

v 10 ,

c/

u

2

v

2

14 . Подсчитаем теперь разности

pq

21

1

22

pq c pq c/pq :

21 c21 c21/

12 10 2 ,

22 c22 c22/ 2 14 12 .

Следовательно,

выражение

L

через

свободные переменные имеет

вид

L 1860 2x21 12x22 . Среди коэффициентов при переменных в правой части есть отрицательный при x22 , следовательно, можно попытаться уменьшить L , уве-

12

личив x22 (сохранив нулевое значение x21 ). Положим x22 . Поскольку суммы значений неизвестных по строкам и столбцам должны оставаться неизменными, нужно произвести следующий балансовый пересчет:

		60	70	20
			.	90
Добавление		к x22 компенсируется вычитанием из x12 , а это в свою

очередь – прибавлением к x13 и т.д. до тех пор, пока мы не вернемся обратно к x22 . Обходя клетки по пунктирной ломаной линии, в одной из вершин которой находится свободная переменная x22 , а в остальных вершинах – базисные переменные (причем не обязательно все), мы получим так называемый цикл пересчета (ломаная называется циклом), отвечающий свободной клетке x22 . Как видно из таблицы, для неотрицательности переменных можно увеличить до70 , тогда получим второе опорное решение:

	60			0		90
	0			70		20
т.е. x11 60 , x12 0 , x13 90 , x21 0 ,			x22 70 , x23 20 .
Значение функции L для него составляет L 1860 12 70 1020 , т.е. получи-
ли оптимальное решение.
Таким образом, правила вычислений по методу потенциалов сводятся к
следующему.
1. Находят потенциалы uk и vl				всех пунктов отправления Ak и назначения
Bl .

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

3.Для выбранной в п.2 переменной находят соответствующий ей цикл пересчета и производят сдвиг по этому циклу. Этот сдвиг приводит к новому допустимому решению.

4.Вышеуказанные операции 1-3 повторяют до тех пор, пока не получат оптимальный базис, т.е. неотрицательные коэффициенты при свободных переменных в правой части линейной функции L .

13