Учебное пособие 1053

В алгоритме построения базисного решения не задается способ выбора клетки (i, j) для заполнения. Мы предлагаем два наиболее распространенных метода заполнения клеток при построении начального базисного решения:

1.Метод северо-западного угла. (В этом случае для заполнения выбирается левая верхняя клетка.)

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

Пример 4.1. Имеется транспортная задача (рис. 4.3).

						Ai
	5	4	3	1	2	7
	3	6	2	4	3	8
	2	4	5	3	1	10
Bj	1	2	3	4	5	20
	8	10	7	11	9

Рис. 4.3 1. Используем при выборе клеток для заполнения метод северо-западного

угла (рис. 4.4).

7					7
					8	1
1	7
					10	7
	3	7
					20	9
		0	11	9
8	10	7	11	9
1	3	0

Рис. 4.4

Невычеркнутых элементов осталось 8, так как ранг матрицы равен 8, то есть матица размера 5×4. 5+4–1=8 (m+n–1).

Ñ(x) = 5 7 +3 1+6 7 + 4 3+5 7 +3 0 + 4 11+5 9 = 216 .

2.Метод минимального элемента (рис. 4.5).

			7		7
					8	1
		7	1
			1	9	10	1
8	10		2		20	12
8	10	7	11	9

24

3

Рис. 4.5

31

Ñ(x) = 7 1+1 4 +7 2 +1 3 +9 1+8 1+1 2 + 2 4 = 73.

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

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

Задание 1. Придумать пример транспортной задачи, при решении которой использование метода минимального элемента даст допустимое решение со значением целевой функции большим, чем при решении той же задачи с использованием метода северо-западного угла.

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

Замечание. При построении начального базисного решения на каждом Шаге вычеркивается либо строка, либо столбец, а на последнем Шаге остается не вычеркнутой и заполняется ровно одна клетка, таким образом общее количество заполненных клеток (m+n–1). Так как число базисных компонент в транспортной задаче равно (m+n–1), то можно предположить, что мы получили базисное решение.

4.3. Метод потенциалов

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

Основные этапы симплекс-метода:

Этап 1. Вычисление оценок. Проверка решения на оптимальность. Если решение оптимальное, то конец. Иначе переход к этапу 2.

Этап 2. Перестроение базисного решения. Переход к этапу 1. Рассмотрим подробно каждый из этапов применительно к транспортной

задаче.

Этап 1. Вычисление оценок и проверка решения на оптимальность

Наша задача ориентирована на min, поэтому нужно учесть критерий оптимальности ∆ij ≤ 0.

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

Переходим к вычислению оценок для транспортной задачи. Выпишем ограничения задачи двойственной к транспортной. Обозначим через Ui двойст-

32

венные переменные к первому блоку ограничений транспортной задачи и через Vj - ко второму блоку ограничений:

	n
Ui	∑xij = Ai , где i =		1,m		,
	j=1
Vj	m
	∑xij = Bj , где	j =1,n ,
	i=1
	xij ≥ 0.

∑cij xij → min .

Двойственное ограничение при переменной xij будет следующим:

xij	Ui +Vj ≤ Cij .

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

xij	áàç	Ui +V j = Cij ( x	ij баз	из матрицы Х).

Из этой системы найдем Ui , Vj .

Так как количество ограничений равно (m+n–1), а количество переменных равно (m+n), будем полагать, что всегда U1 = 0 и тогда

Ui = Cij −Vj ,

Vj = Cij −Ui .

Вычисляем для всех небазисных (i, j) оценки ∆ij по формуле

∆ij =Ui +V j −Cij .

Алгоритм выполнения этапа 1

Шаг 1. Для всех xij базисных записывается уравнение U i +V j = Ci. j .

Шаг 2. U1 = 0,

Шаг 3. Вычисление остальных потенциалов Ui , Vj по формулам:

Ui = Cij −Vj ,

Vj = Cij −Ui .

Шаг 4. Для всех (i, j) небазисных вычисляются оценки ∆ij :

∆ij =Ui +Vj −Cij .

Шаг 5. Если все ∆ij ≤ 0, то вычисляется

Ñ(x) = ∑cij xij .

Конец.

Иначе переход к Этапу 2.

33

Этап 2. Перестроение базисного решения

Пусть существует ∆i0 j0 > 0, как следует из теории симплекс-метода, если переменную xi0 j0 сделать базисной, то значение целевой функции уменьшится.

Посмотрим, как получить значение	xi j	=θ при отсутствии обычной
	0	0

симплекс-таблицы. Так как сумма элементов в каждой строке и в каждом столбце в матрице допустимого решения Х должна сохраняться, то если какойто элемент строки увеличивается, очевидно, что значение некоторого другого элемента в этой же стоке должно быть уменьшено, а некоторое значение в столбце, в котором значение элемента уменьшено, должно быть увеличено и так далее.

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

Эти элементы можно определить с помощью правила вычеркивания.

4.4. Правило вычеркивания

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

1.Все элементы вычеркнуты.

2.В каждой из невычеркнутых строк и столбцов содержатся не менее двух выделенных элементов.

Имеют место следующие утверждения.

Утверждение 1. Столбцы Pij , соответствующие вычеркнутым элемен-

там, линейно независимы.

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

Алгоритм перестроения базисного решения Шаг 1. Выбираем ∆i0 j0 > 0.

Шаг 2. Полагаем xi0 j0 =θ .

Шаг 3. К транспортной таблице, со всеми выделенными базисными xij и

добавленными к ним θ , применяется правило вычеркивания. Оставшиеся невычеркнутыми элементы образуют цикл.

Шаг 4. При движении по циклу от θ расставляются знаки минус и плюс поочередно.

Шаг 5. Полагаем θ = min xij− .

Шаг 6. Перестраивается базисное решение по формулам

34

xi0 j0 =θ ,

xij−нов = xij− −θ , xij+нов = xij+ +θ , xijнов = xij

для невычеркнутых элементов.

Шаг 7. Один из элементов, помеченный знаком минус, который после преобразования стал или был равным нулю, исключается из базиса.

Шаг 8. Переход к Этапу 1.

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

Утверждение 3. Если в транспортной задаче все Ai и Bj являются целыми числами,

то любое допустимое базисное решение также целое. Пример 4.2. Имеем транспортную задачу (рис. 4.6).

						Ai
	5	4	3	1	2	7
	3	6	2	4	3	8
	2	4	5	3	1	10
	1	2	3	4	5	20
Bj	8	10	7	11	9

Рис. 4.6

Матрица Х – начальное базисное решение, найденное с помощью произ-

вольного выбора xij	(рис. 4.7).
							Ai
					7(1)		7
							8	1
				7(2)		1(3)
							10	2
		8(4)				2(5)
							20	10	6
Bj			10(6)		4(7)	6(8)
		8	10	7	11	9
					4	8
				Рис. 4.7		6

35

Вычислим потенциалы:
U1+ V4	=1,	U3+ V5 = 1,	U1	= 0,	V1 = 3,
U2+ V3 = 2,		U4+ V2 = 2,	U2 = 1,		V2 = -1,
U2+ V5 = 3,		U4+ V4 = 4,	U3 = -1,		V3 = 1,
U3+ V1 = 2,		U4+ V5= 5,	U4 = 3,		V4 = 1,
					V5 = 2.

Занесем полученные результаты в таблицу (рис. 4.8)

	Vj	3	-1	1	1	2
	Ui
	0				7
	1			7		1
	-1	8				2
	3		10		4	6

Рис. 4.8

Для небазисных мест ∆ij =Ui +Vj −Cij (вычисление оценок и проверка на оптимальность), (рис. 4.9)

	Vj	3	-1	1	1	2
	Ui
	0	-2	-5	-2	7	0
	1	1	-6	7	6	1
	-1	8	-6	-5	-3	2
	3	5	10	1	4	6

Рис. 4.9

Для введения в базис выбираем клетку (4;1) так как ∆4;1 = 5 > 0 (решение неоптимальное) и поставим x4;1 =θ .

Определяем цикл, связывающий θ с базисными элементами, по правилу вычеркивания.

Расставим знаки при элементах цикла. θ = min xij− = 6 (рис. 4.10).

			7		(1)
		7		1	(5)
8-				2+
θ	10		4	6-

(2)(3) (4)

Рис. 4.10

36

Продолжаем перестраивать базисное решение (рис. 4.11 – 4.14).

	Vj	-2	-1	-4	1	-3
	Ui
	0	-7	-5	-7	7	-5
	6	1	-1	7	3	1-
	4	2-	-1	-5	2	8+
	3	6+	10	-4	4-	-5
			Рис. 4.11
				7	1-
			7	θ
		2-			8+
		6+	10	4-
			θ =1
			Рис. 4.12
	Vj	-2	-1	-1	1	-3
	Ui
	0	-7	-5	-4	7	-5
	3	-2	-4	7	1	-3
	4	1-	-1	-2	2	9
	3	7+	10	-1	3-	-5
			Рис. 4.13
				7
		1-	7	1
				θ	9
		7+	10	3-
			θ =1
			Рис. 4.14
			37

Новое базисное решение и новые оценки представлены на рис. 4.15.

	Vj	-2	-1	-1	1	-1
	Ui
	0	-7	-5	-4	7	-3
	3	-2	-4	7	1	-1
	2	-2	-3	-4	1	9
	3	8	10	-1	2	-3
			Рис. 4.15

Все оценки ∆ij < 0 , значит, решение оптимальное.

Вычисляем значение целевой функции:

C(x) = 7×1+1×4 + 7×2 +1×3 +9×1+8×1+1×2 + 2×4 = 73 .

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

Транспортная задача с запретами (в транспортной задаче запрещены некоторые маршруты перевозок)

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

Обозначим через Ji множество номеров потребителей, которые связаны коммуникациями с i-м поставщиком со стоимостью перевозок сij , а через I j –

множество номеров поставщиков, которые связаны коммуникациями с j-м потребителем со стоимостью перевозок сij , тогда математическая модель примет

вид

∑xij = Ai , i =1,m ,

j Ji

∑xij = Bj , j =1,n ,

i I j

xij ≥ 0,

∑∑xij ñij → min . i I j j Ji

Заметим, что в этом случае, даже при выполнении условия баланса, задача может оказаться несовместной.

Такая задача после некоторых преобразований сводится к обычной транспортной задаче.

Полагаем сij = М (М – большое число), где i I j и j Ji , полученная

задача решается методом потенциалов

Если в оптимальном решении xij > 0, там где сij = М , то исходная задача несовместна.

38

Если при всех сij = М все xij = 0, то найдено решение исходной задачи.

Несбалансированные транспортные задачи

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

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

Рассмотримm оба случаяn :

а) Пусть ∑Ai > ∑Bj , то есть предложение превышает спрос.

В этом случаеi=1 , очевидноj=1 , не вся продукция от поставщиков будет отправлена потребителям, поэтому математическая модель примет вид

	n
	∑xij ≤ Ai , i =	1,m		,
	j=1
	m
	∑xij = Bj , j =				,
			1,n
	i=1
	xij ≥ 0,
	m n
	∑∑xij ñij → min .
	i=1 j=1
m	n
б) Пусть ∑Ai < ∑B j , то есть спрос превышает предложение.
i=1	j=1

Математическая модель:

n

∑xij = Ai , i =1,m ,

j=1

m

∑xij ≤ Bj , j =1,n ,

i=1

xij ≥ 0,

m n

∑∑xij ñij → min . i=1 j=1

Рассмотрим способ сведения несбалансированных задач а) и б) к сбалансированным.

Для случая а) введём дополнительную переменную xi(n+1) – количество продукции, которая осталась на складе i-го поставщика, то есть не вывезенная к потребителям продукция. Получим

n

∑xij + xi(n+1) = Ai , j=1

m

∑xij = Bj , j =1,n ,

i=1

39

m	m		n
∑xi(n+1) = ∑Ai − ∑Bj = B(n+1)						,
i=1	i=1		j=1
	ci(n+1)		= 0
или
n+1
∑xij = Ai , i =				,
			1,m
j=1
m
∑xij ≤ Bj , j =					,
		1,(n +1)
i=1
m	n
∑∑xij ñij → min .
i=1	j=1

Таким образом, к таблице исходных данных надо добавить (n +1) -й столбец с целевыми коэффициентами, равными нулю, и

m

B(n+1) = ∑Ai i=1

n

− ∑Bj .

j=1

Для случая б) введём дополнительную переменную x(m+1) j – количество продукции, которое недодали j-му потребителю.

m
∑xij + x(m+1) j = Bj , j =										,
									1,n
i=1
	n
	∑xij = Ai , i =							,
						1,m
	j=1
n	n			m
∑x(m+1) j = ∑Bj − ∑Ai = A(m+1)											,
j=1	j=1			i=1
	c(m+1) j = 0
или
m+1
∑xij = Bj , j =					,
				1,n
i=1
n
∑xij = Ai , i =			1,(m +1)				,
j=1
m	n
∑∑xij ñij		→ min .
i=1	j=1

К таблице исходных данных добавляется (m +1) строка с целевыми ко-

	n	m
эффициентами, равными нулю, и	A(m+1) = ∑Bj − ∑Ai .
	j=1	i=1

Далее решается сбалансированная транспортная задача с помощью метода потенциалов. После решения добавленный столбец или строка отбрасываются.

40