Методы оптимизации. Часть 2. Линейное программирование

Федеральное агентство по образованию

Томский государственный университет систем управления и радиоэлектроники

Ю.И. Параев

МЕТОДЫ ОПТИМИЗАЦИИ

(Часть 2. Линейное программирование)

Методические указания для проведения практических занятий для студентов направлений 230100 «Информатика и вычислительная техника»,

230400 «Информационные системы и технологии»

Томск

ТУСУР

2010

УДК 519.85 (076)

Параев Ю.И.

Методы оптимизации (Часть 2. Линейное программирование) – Методические указания для проведения практических занятий для студентов направления 230100 «Информатика и вычислительная техника». 2010. – 46 с.

©Параев Юрий Иванович, 2010

©Томский государственный университет систем управления и радиоэлектроники, 2010

Содержание
Тема 5. Линейное программирование.................................................................................	3
5.1. Постановка задачи...........................................................................................	3
5.2. Решение задач линейного программирования. Симплекс-метод..................	4
5.3. Выбор начального плана.................................................................................	8
5.4. Геометрическое решение задач линейного программирования..................	10
Тема 6. Транспортная задача .............................................................................................	13
6.1. Постановка задачи.........................................................................................	13
6.2. Структура решения........................................................................................	14
6.3. Выбор начального плана...............................................................................	15
6.4. Метод потенциалов.......................................................................................	17
Тема 7. Задача о назначениях.............................................................................................	21
7.1. Постановка задачи.........................................................................................	21
7.2. Решение задачи..............................................................................................	21
Задания для самостоятельной работы...............................................................................	26

ТЕМА 5. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

5.1. Постановка задачи Найти экстремум линейной функции

i 1

n
amixi	bm,
i 1
n
a1ixi	b1,
i 1
n
a2ixi	b2,	(5.4)
i 1
n
F(x) cixi		(5.1)
i 1
на линейном многообразии S, задаваемом условиями:
I. Все xi≥0, i=1,…,n.		(5.2)
II. Должны выполняться либо равенства
n
a1ixi	b1,
i 1
n
a2ixi	b2,	(5.3)
либо неравенства
n
amixi	bm.
i 1

Задача с ограничениями типа (5.3) называется основной. Замечания.

1.Ограничения (5.3) или (5.4)должны быть совместны.

2.Задача с ограничениями типа неравенств сводится к задаче с ограничениями типа равенств с помощью введения новых переменных

n

a1ixi xn 1 b1,

i 1
n
a2ixi xn 2 b2,	(5.5)
i 1

n

amixi xn m bm. i 1

Такой подход называется методом искусственного базиса.

3. Перечисленные соотношения удобно записать в матричной форме, если ввести в рассмотрение

вектор-строку СТ с1,с2,...,сn (Т – означает транспонирование),

векторы-столбцы

x1				b1
x x	2 ,	b b2
xn				bm
a11	a12		a1n
А a21	a22				a2n .
	an2
an1					ann
и матрицу
В результате вместо (5.1) получаем
F(x) cT x .					(5.6)
Вместо (5.2) и (5.3) –
	x 0,				(5.7)
	Ax b.				(5.8)
4. Предполагается, что rang A m n,				rang A,b rang A . Последнее есть
условие совместности системы уравнений (5.8).

5. Обычно предполагается, что b 0. Это можно всегда получить, умножая при необходимости уравнения (5.1) на – 1.

5.2. Решение задач линейного программирования. Симплекс-метод

Условия (5.7) и (5.8) задают линейное многообразие S, угловыми точками которого являются вектора x, у которых n-m координат обязательно равны 0, а m координат ≠0. Решением задачи, если оно существует, является одна из таких угловых точек. Такие точки еще называют планом решения.

Симплекс-метод решения задач линейного программирования состоит в последовательном переборе этих угловых точек. Для определенности будем искать минимум функции F(x).

Пусть x – некоторая угловая точка, которая взята в качестве начального приближения или начального плана. Вопрос о выборе начального приближения будет рассмотрен ниже. Эта точка удовлетворяет условиям (5.7) и (5.8).

Обозначим через I(x) набор индексов ненулевых координат вектора x и через O(x) набор индексов нулевых координат этого вектора. Множество I(x) сдержит m

чисел, а множество O(x) – n-m чисел. Очевидно, что I(x) O(x) {1,2,...,n}.
Введем новую угловую точку
x	x x ,		(5.9)
где θ(>0) – некоторое число, x – некоторый произвольный вектор. Вектор		x	должен

удовлетворять условиям (5.7) и (5.8). Подставляя (5.9) в (5.8), получаем, что вектор x должен удовлетворять уравнению

A x 0.

(5.10)

Обозначим через xI – вектор порядка m, составленный из элементов вектора х с

номерами из множества I(x), и через xO – вектор порядка n-m, составленный из эле-

ментов вектора х с номерами из множества О(x). Очевидно, что xO 0. Аналогично разделим строку сT на сTI и cOT . В результате вместо (5.6) получаем

			F(x) cTI				xI .			(5.11)
Аналогично разделим вектор	x		на векторы	x		I	и	x	O , и вектор x	на векторы xI и
xO .
При этом получается
x		I	xI xI ,		x		O xO.			(5.12)

Из последнего выражения следует необходимость условия xO 0.

Матрицу А можно записать в виде двух блоков AI , куда входят столбцы с номе-

рами из множества I(x) и AO , куда входят столбцы с номерами из множества O(x).

Блок AI имеет размерность m×m, блок AO – m×(n-m) соответственно. Тогда уравнение(5.10) можно переписать в виде

AI xI AO xO

0

или AI xI

AO xO.

(5.13)

Если блок AI невырожденный, то

x

I

A 1A x

P x .

(5.14)

I

O O

O

(P A 1A .) Элементы вектора

x назовем независимыми переменными, а вектора

I

O

O

xI – зависимыми. Подставляя (5.14) в (5.12), получаем

x

I

xI

P xO,

(5.15)

x

O xO.

(5.16)

Подставим последнее в (5.6). В результате получим

F(

x

) cT

x

I

cT

x

cT (x

I

P x

O

) cT x

O

I

O O

I

O

F(x) (cT cT P) x

F(x) T x ,

O

I

O

O

где

T

cOT cTI P.

(5.17)

Элементы строки T [ ,

2

,...,

n m

]

– называются коэффициентами замещения.

1

Учитывая,

что θ>0 и xO 0, получаем следующий результат. Если все

j 0,

то

F(

x

) F(x) и, следовательно,

вектор x дает минимальное значение функции F(x).

Та-

ким образом, решение задачи заканчивается. Если имеются j 0, то можно получить вектор x , для которого F(x) F(x). Для этого выберем наименьшее из j 0. Пусть это будет k k O x . Тогда положим xk 1, а все остальные xi 0 k,i O x . В

результате в векторе xO появляется k-ый элемент, равный . В этом случае вектор

(5.15) примет вид

xI xI pk ,

где pk – k-ый столбец матрицы Р. Вектор x должен удовлетворять условию (5.7), т.е.

должно выполняться

		xi pik 0, i I x .
Поскольку xi 0, i I x , то эти неравенства выполняются всегда, когда										pik 0. Поэто-
му рассматриваются неравенства, где			pik 0.				Параметр выбирается так, чтобы одно
из неравенств, например,	x	l xl plk	0 , а остальные					x	i xi pik 0, i I x \l. Таким
образом,
				xl			.			(5.18)
				plk
В результате получается,	что для вектора				x		набор индексов ненулевых координат

I x I x \l,k , нулевых координат – O x O x \k,l .

Далее процедура повторяется для вектора x . Вычисления продолжаются до тех пор, пока не окажется, что на каком-то этапе все коэффициенты замещения j 0, т.е.

получается окончательное решение.
Пример 5.1. Найти минимум функции
	F(x) x2 3x3 2x5,								(5.19)
при условиях
I. Все xi 0,i 1,...,6.
II. Должны выполняться уравнения
x1 3x2	x3			2x5			7,
2x2	4x3	x4						12,	(5.20)
4x2	3x3			8x5	x6			10.
В данном примере n=6,m=3. Матрица
	1	3	1	0	2	0
		2 4 1 0
	А 0					0
		4	3	0	8
	0					1

Решение. Начальное приближение выберем в виде

70

0

x.12

0

10

Видно, что этот вектор удовлетворяет уравнениям (5.20). Для проведения решения удобно составить таблицу (см. таблица 2.1).

Таблица 2.1. Первая итерация
		ci	x		x2	x3	x5		x x				x
1		0	7		3	1	2		7	10
2		1	0		1	0	0		0	0
3		3	0		0	1	0			3
4		0	12		2	4	0		12 4	0
5		2	0		0	0	1		0	0
6		0	10		4	3	8		10 3	1
			i		1	3	2		3
			F(x) 0							F(	x	) 9

В 1-й столбец заносятся коэффициенты сi согласно с (5.19), во 2-й – начальный план x.

Следующий шаг состоит в записи и решении уравнения (5.13). Из вида вектора x следует, что независимые переменные x2, x3, x5, зависимые x1, x4, x6. Поэтому уравнение (5.13) следует записать в виде

x1	3 x2		x3	2 x5
x4		2 x2	4 x3
x6		4 x2	3 x3	8 x5

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

1-го и 3,4,5-го столбцов. Получается, что 3 0. Это отмечается с помощью *. Поэто-

му полагается: x2 0, x3 1, x5 0. В 6-й столбец заносится вектор x x , кото-

рый равен сумме 2-го столбца и 4-го, умноженного на . Параметр выбирается как min 12/4,10/3 3. В 7-й столбец заносится окончательный план, т.е. 6-й столбец при

3. В нижней строке таблицы приведены значения F x и F x . Видно, что

F x F x .

Далее выполняется вторая итерация, результаты которой заносятся в таблицу 2.2.

Таблица 2.2. Вторая итерация
		ci	x		x2	x4	x5		x x				x
1		0	10		5 2	1 4	2		10 5 2			0
2		1	0		1	0	0			4
3		3	3		1 2 1 4 0				3 2	5
4		0	0		0	1	0		0	0
5		2	0		0	0	1		0	0
6		0	1		5 2	3 4 8			1 5 2	11
			i		1 2 3 4		2		4
			F x 9							F	x	11

Теперь независимые переменные x2, x4, x5 , зависимые x1, x3, x6 .

Уравнения(5.13) для них имеют вид

x1	x3		3 x2		2 x5
	4 x3			2 x2	x4
	3 x3	x6		4 x2	8 x5

Их решение заносится в 3,4,5-й столбцы таблицы 2.2. Вычисляя коэффициенты замещения, получаем, что 2 0. Поэтому полагаем: x2 1, x4 0, x5 0. В 6-й столбец заносится вектор x x.

Из требования, чтобы первый элемент равнялся 0, получаем 4. В 7-й столбец заносится окончательный план. В нижней строке таблицы приведены значения F x и

F	x	. Видно, что F			x	F x , т.е. план				x	лучше, чем план x.
Таблица 2.3. Третья итерация
				ci			x		x1		x4	x5		x x	x
1				0			0		1		0	0
2				1			4		2 5		110	4 5
3				3			5		1 5		3 10	2 5
4				0			0		0		1	0
5				2			0		0		0	1
6				0			11		1		1 2	10
							i		1 5		8 10	9
							F x 11

Теперь независимые переменные x1, x4, x5, зависимые x2, x3, x6 .

Уравнения(5.13) для них имеют вид

3 x2	x3		x1	2 x5
2 x2	4 x3			x4
4 x2	3 x3	x6		8 x5

Их решение заносится в 3,4,5-й столбцы таблицы 2.3. Вычисляя коэффициенты замещения, получаем, что все i 0. Следовательно, дальнейшее улучшение плана уже не-

возможно. Решением задачи является план, стоящий во 2-м столбце таблицы 2.3.

5.3. Выбор начального плана

Начальный план легко получить, если в матрице А можно выделить блок, состоящий из единичной матрицы. Тогда соответствующие элементы плана приравниваются к элементам вектора b . Так получен начальный план в примере 5.1. В общем случае для выбора начального плана вводятся новые переменные, которые добавляются также в функцию F x с очень большими коэффициентами. В результате после ряда применений симплекс-метода эти новые переменные будут исключены их плана, так как в функцию F x , которая минимизируется, они входят с большими коэффициентами. После этого получается начальный план для основного решения задачи.

Пример 5.2. Минимизировать функцию
F(x) x1 2x2 3x3 x4	(5.21)

при условиях

I. Все xi 0,i 1,...,4.
II. Должны выполняться уравнения
				x1		2x2		3x3					15,
				2x1		x2		5x3					20,					(5.22)
				x1		2x2		x3		x4			10.
В данном примере n=4, m=3. Введем новые переменные x5																и x6, и вставим их в функ-
цию F x и уравнения (5.22). В результате получим
			F(x) x1 2x2 3x3 x4 wx5 wx6,
и
			x1	2x2		3x3				x5							15,
			2x1	x2		5x3						x6					20,
			x1 2x2			x3			x4								10.
Здесь w – какое-то большое число. При этом матрица
							1	2	3	0	1	0
						А
							2 1 5			0 0 1 .
								2	1	1	0
							1					0
Отсюда легко получить начальный план. Он занесен во 2-й столбец таблицы 3.1
Таблица 3.1. Первая итерация
		ci	x			x1			x2		x3				x x					x
1		1	0			1			0			0					0	0
2		2	0			0			1			0					0	0
3		3	0			0			0			1						4
4		1	10			1			2			1			10			6
5		w	15			1			2			3			15 3			3
6		w	20			2			1		5				20 5			0
			i		2 3w 4 3w 4 8w										4
			F x x															F	x
			10 35w															6 3w
Теперь независимые переменные –							x1, x2, x3,				зависимые –						x4, x5, x6 .
Уравнения(5.13) для них имеют вид
				x4			x1			2 x2		x3
				x5			x1			2 x2		3 x3
				x6		2 x1				x2		5 x3

Их решение заносится в 3,4,5-й столбцы таблицы 3.1. В результате вычисления коэффициентов замещения, получаем, что наименьшим является коэффициент 3 4 8w.

Поэтому полагается: x1	x2 0, x3 1. В 6-й столбец заносится вектор x x.
Параметр выбирается	как min 10,15/3,20/5 4. В 7-й столбец заносится оконча-