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

c24 u2 v4 5,

c31 u3 v1 3,

c34 u3 v4 8.

Решение этой системы уравнений равно

u1 1, u2 3,u3 0,v1 3,v2 2,v3 5,v4 8.

На основании этих данных составляем таблицу коэффициентов замещения.

	ui \vj											3																								2																									5																										8																											1	1
	1																																																															c					u v																					c						u v
																																																													12 1																				2						14 1																					4			=
С																																																																																																																7 10
			3											c			21			u2 v1																		c		22 u2 v2
																																																																																																																	4	6
	0																																				c32 u3 v2																										c33 u3 v3

Получается, что все коэффициенты замещения неотрицательны. Поэтому план (6.15) дает окончательное решение задачи.

ТЕМА 7. ЗАДАЧА О НАЗНАЧЕНИЯХ

7.1. Постановка задачи

Задача о назначениях является частным случаем транспортной задачи, когда число складов и число магазинов одинаково и равно n. На каждом складе имеется только одна единица товара и каждому магазину требуется также только одна единица товара. Предполагается, что известны сij – стоимости перевозки единицы товара из i-го

склада в j-й магазин. Из этих стоимостей можно составить матрицу

c11	c12	c1n
c	c	c	(7.1)
C 21	22	2n .
	cm2
cm1		cmn

Пусть xij − количество единиц товара, перевозимых из i-го склада в j-й магазин. Можно составить матрицу

x11	x12		x1n
x	x	x		(7.2)
X 21	22		2n ,
	xm2
xm1			xmn

которая определяет план перевозок. В результате получаем, что величина сij xij есть

цена перевозки из i-го склада в j-й магазин. Суммируя по всем i и j, получаем общую цену всех перевозок

		n n
	F(C, X) cijxij.		(7.3)
		i 1i 1
Особенностью данной задачи является то, что
1. Все xij 0 или 1.
n
2. xkj 1,	k 1,2,...,n,
j 1
	n
	xik 1,	k 1,2,...,n.
	i 1

Эти условия означают, что в плане Х в каждой строке и в каждом столбце должна стоять одна и только одна 1.

Задача о назначениях состоит в выборе такого плана Х, при котором общая цена всех перевозок F(C,X) минимальна. Если в исходной задаче нужно максимизировать целевую функцию, то можно просто стоимостную матрицу С умножить на –1 и затем перейти к задаче минимизации целевой функции.

7.2. Решение задачи

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

шение задачи сводится к преобразованию матрицы С к виду, когда все сij 0 и в каж-

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

Таким образом, строится следующий алгоритм решения.

Шаг 1. (Подготовительный). Если исходная задача требует нахождения максимума функции F(C, X), все элементы матрицы С умножаются на –1. Далее. Из всех элементов каждого столбца вычитается минимальный элемент. Из всех элементов каждой строки вычитается минимальный элемент. В результате получается, что все сij 0 .

Шаг 2. В матрице С выделяются значимые нули. Эта процедура состоит в следующем. Выделяется какой-то нулевой элемент. Лучше начинать с нулей, которые единственные в какой-то строке и каком-то столбце. Вычеркиваются строка и столбец, на пересечении которых стоит этот элемент. В оставшейся части выделяется какой-то новый нулевой элемент, и вычеркиваются строка и столбец, на пересечении которых стоит этого элемента. И т.д. Если значимых нулей окажется n, то задача решена. Иначе переход к следующему шагу.

Шаг 3. Отмечаются строки, где нет значимых нулей.

Шаг 4. Отмечаются столбцы, где в выделенных строках есть неотмеченные нули. Если таких нулей нет, то переход к шагу 6, иначе к шагу 5.

Шаг 5.Отмечаются строки, где в отмеченных столбцах имеются значимые нули. Переход к шагу 4.

Шаг 6. В матрице С вычеркиваются отмеченные столбцы и неотмеченные строки. В оставшейся части не должно быть нулевых элементов.

Шаг 7. В оставшейся части находится минимальный элемент и это число вычитается из всех невычеркнутых столбцов уже всей матрицы С. В результате в матрице С появятся отрицательные элементы. Они появятся в каких-то вычеркнутых строках. Прибавляем к элементам этих строк указанное число, чтобы в С не было отрицательных элементов. Окончательно получим новую матрицу С, у которой все сij 0 . Затем

переход к шагу 2.

Пример 7.1. Пусть исходная матрица
		9	6	5	8
С		4	8	6	2		.	(7.4)
		6	7	9	4
		2	7	3	1
Нужно построить план
x11			x12	x13			x14
X x21			x22	x23 x24 ,
			x32	x33			x34
x31
x41			x42	x43			x44

при котором общая цена всех перевозок

4 4

F(C, X) cijxij

i 1i 1

минимальна.

Решение

Шаг 1. Из всех элементов каждого столбца матрицы С. вычитается минимальный элемент столбца

		7	0	2	7
	С	2	2	3	1	.
		4	1	6	3
		0	1	0	0

Из всех элементов 2-й и 3-й строк вычитается минимальный элемент

		7	0	2	7
	С	1	1	2	0	.
		3	0	5	2
		0	1	0	0

В результате получается, что все сij 0 .

Шаг 2. В матрице С выделяются значимые нули.

		7		0	2	7
		1		1	2			.
С						0
		3		0	5	2
				1	0	0
		0

Они отмечаются чертой сверху. Эта матрица имеет 3 значимых нуля, поскольку элементс33 5.

Шаг 3. Отмечаются строки, где нет значимых нулей.

	7			0	2	7
	1			1	2
						0
С	3			0	5	2		.
				1	0	0
		0

Шаг 4. Отмечаются столбцы, где в выделенных строках есть неотмеченные ну-

ли.

	7			0		2	7
	1			1		2
							0
С	3			0		5	2		.
				1		0	0
		0

Шаг 5. Отмечаются строки, где в отмеченных столбцах имеются отмеченные

нули

	7			0		2	7
	1			1		2
							0
С	3			0		5	2		.		(7.5)
				1		0	0
		0

Переход к шагу 4.

Шаг 6. Отмечаются столбцы, где в выделенных строках есть неотмеченные нули. Таких больше нет. Переход к шагу 6.

Шаг 7. В матрице С вычеркиваются отмеченные столбцы и неотмеченные стро-

ки

7		2	7
С		5	.
3			2

Воставшейся части не должно быть нулевых элементов.

Шаг 8. В оставшейся части находится минимальный элемент. В данном случае это с13=2. Это число вычитается из всех не вычеркнутых столбцов уже всей матрицы С

(см. (7.7)).

		5	0	0	5
	С	1	1	0	2	.
		1	0	3	0
		2	1	2	2

Прибавляем к элементам 2-й и 4-й строк число 2. Окончательно получим новую матрицу

		5	0	0	5
	С	1	3	2	0	,	(7.6)
		1	0	3	0
		0	3	0	0

у которой все сij 0 . Затем переходим к шагу 2.

Шаг 9. В матрице (7.6) выделяются значимые нули

5 0 0 5

С 1 3 2 0 . 1 0 3 0

0 3 0 0

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

		0	0	1	0
	Х	0	0	0	1	.
		0	1	0	0
		1	0	0	0

Если вернуться к исходной матрице (7.4), то в ней можно отметить перевозки из плана Х

9 6 5 8

С 4 8 6 2 . 6 7 9 4

2 7 3 1

Минимальная цена перевозок равна 16. Если перевозки планировать из принципа минимального тарифа (см. п.6.3.3), то цена перевозок будет равна

F c44 c21 c13 c32 17.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Вариант 1

1. Решить геометрически и симплекс-методом задачи линейного программирования а) F x 3x1 2x2 min

x1 5x2 3x3 28

2x1 x2 3x3 26 5x1 6x2 4x3 48 x1 0,x2 0,x3 0.

б) F x x1 2x2 min

3x2 5x3 3x4 3

5x1 5x2 4x3 2x4 40 x1 0,x2 0,x3 0,x4 0.

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

ai	\	bj	18	40	51	20
	35		25	16	71	19
	45		41	13	27	15
	20		18	54	75	17
	15		12	21	35	10
ai	\	bj	18	40	51	20	30
	35		25	16	71	19	8
	45		41	13	27	15	9
	20		18	54	75	17	7
	15		12	21	35	10	11
	21		17	20	9	7	31

3. Решить задачи о назначениях для следующих матриц стоимостей:

2	5	8	8
4	1	11	3
5	6	4	12
8	8	9	9
2	8	3	1	4
11	2	18	7	5
1	1	1	14	5
6	7	8	9	10
5	4	3	2	1

Вариант 2

1. Решить геометрически и симплекс-методом задачи линейного программирования а) F x 3x1 2x2 min

2x1 3x2 x3 5

x2 5x3 33

x1 0,x2 0,x3 0.

б) F x x1 x2 min

5x1 2x2 3x3 x4 16

x1 3x2 2x3 6x4 10

x1 0,x2 0,x3 0,x4 0.

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

ai	\	bj	18	40	51	20
	35		25	16	71	19
	45		41	13	27	15
	20		18	54	75	17
	15		12	21	35	10
ai	\	bj	18	40	51	20	30
	35		25	16	71	19	8
	45		41	13	27	15	9
	20		18	54	75	17	7
	15		12	21	5	10	11
	21		17	20	9	7	31

3. Решить задачи о назначениях для следующих матрицу стоимостей:

8	5	8	8
4	1	11	3
5	6	4	12
8	8	11	9
2	8	3	1	4
11	2	18	7	5
1	11	1	14	5
6	7	8	9	10
5	4	3	2	1

Вариант 3

1. Решить геометрически и симплекс-методом задачи линейного программирования а) F x 3x1 2x2 min

7x2 x3 28

6x1 x2 2x3 16

5x1 6x2 7x3 18

x1 0,x2 0,x3 0.

б) F x x1 2x2 min

7x1 6x2 5x3 4x4 28

x1 6x2 40

x1 0,x2 0,x3 0,x4 0.

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

ai	\	bj	18	40	51	20
	35		12	16	19	19
	45		41	13	17	15
	20		18	54	75	17
	15		12	21	35	10
ai	\	bj	18	40	51	20	30
	35		25	16	71	19	8
	45		43	13	27	15	9
	20		18	54	75	17	7
	15		12	21	35	10	11
	21		17	20	9	7	31

3. Решить задачи о назначениях для следующих матрицу стоимостей:

7	5	8	8
14	1	11	3
5	6	4	12
8	18	9	9
2	8	3	1	4
11	2	18	7	5
1	11	1	14	5
6	7	8	9	10
5	14	3	2	1

Вариант 4

1. Решить геометрически и симплекс-методом задачи линейного программирования а) F x x1 2x2 min

4x1 7x2 4x3 5 3x2 4x3 43

6x1 7x2 6x3 95 x1 0,x2 0,x3 0.

б) F x x1 2x2 min

6x1 6x2 5x3 4x4 42 x1 7x2 43

x1 0,x2 0,x3 0,x4 0.

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

ai	\	bj	18	40	51	20
	35		25	16	71	19
	45		41	13	27	15
	20		18	54	75	17
	15		12	21	35	10
ai	\	bj	18	40	51	20	30
	35		25	16	41	19	8
	45		41	13	27	15	9
	20		18	54	75	17	7
	15		16	21	35	10	11
	21		17	20	9	17	31

3. Решить задачи о назначениях для следующих матрицу стоимостей:

21	9	8	8
4	19	11	3
5	6	4	12
8	8	9	19
2	8	3	1	4
11	2	18	7	5
21	1	1	14	5
6	7	8	8	10
5	4	3	2	1