Ситникова, ИВ. Линейная алгебра. Практикум

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

13. Транспортная задача линейного программирования

Транспортная задача является одной из задач линейного

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

В этом случае определяют такой план перевозок, при котором их стоимость

будет минимальной.

Пусть однородный груз сосредоточен у m поставщиков в объемах

а	, а		,...а	груз необходимо поставить n потребителям в объемах
1	2		m . Данный
b ,b		,...b		c	(i 1,2,...m, j 1,2,...n)	- стоимости перевозок единицы
1	2		n . Известны	ij

груза от каждого i-ого поставщика каждому j–му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны.

Обозначим через

хij 0

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

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

следующим ограничительным условиям: 1)

n
xij	ai (i 1,2,...m);
j 1

m
2) xij	bj ( j 1,2,...n); 3)
i 1

x	0.
ij

Суммарные затраты на перевозки равны

		n	m
Z c11x11 c12 x12 ...cnm xmn cij xij . Следовательно, требуется				найти
		i 1	j 1
переменные	xij , которые	удовлетворяют указанным условиям и		мини-
мизируют целевую функцию		Z.

51

Исходные данные записывают в таблице вида:

b	j

a	i

a1

a	2

…

a	m

b
	1
c
	11
c	21
…
c	m1

b
		2
c
	12
c		22
…
c	m 2

…

…

…

…

…

bn

c1n

c2n

…

c	mn

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

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

Решение задачи разбивается на два этапа:

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

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

оптимальному решению.

Для построения базисного решения применяют один из двух методов:

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

достаточно близкое к оптимальному. Метод состоит из ряда однотипных

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

соответственно, исключается из рассмотрения один поставщик или потре-

битель. Построение базисного решения начинают с клетки с наименьшей

стоимостью	ij		. Далее заполняется очередная клетка, соответствующая
	min c
следующему min cij		. Если на каком-либо шаге (кроме последнего) из таблицы

поставок одновременно выпадает и строка, и столбец, то в любую пустую

52

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

клеток равно			m n 1.
		Для проверки оптимальности базисного решения и построения новых
решений, улучшающих друг друга, применяют метод потенциалов.
		Если допустимое решение транспортной задачи является оптимальным, то
существуют			потенциалы (числа) поставщиков ui ,i 1, 2,..., m и потребителей
v	j	, j 1, 2,..., n	, удовлетворяющие условиям:

u		i	v		j	c
						ij
u	i	v		j		c
						ij

при

при

х	0
ij
х	0
ij

(*) (**)

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

неизвестных находят однозначно.

Неравенства (**) используют для проверки

оптимальности опорного

решения. Неравенства представляют в виде

ij

u

i

v

j

c

0

при хij 0.

ij

Числа

ij называют оценками для свободных клеток таблицы транспортной

задачи.

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

Алгоритм решения транспортной задачи:

1)Проверить закрытость транспортной задачи. В случае необходимости ввести фиктивного поставщика или потребителя.

2)Найти первоначальное базисное решение.

3)Рассчитать стоимость затрат.

53

4)	Найти потенциалы, решая систему уравнений	u	i	v	j	c	для заполненных
						ij
	клеток таблицы.
5)	Вычислить оценки для всех незаполненных клеток таблицы по формулам

	ij	u	i	v	j

cij

.

6)а) Если все оценки неположительны, то найденное решение является оптимальным и задача решена.

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

угловых точках цикла ставят знаки «+» и «-», начиная со знака «+» в

клетке с наибольшей положительной оценкой. Осуществляют сдвиг

(перераспределение груза) по циклу на величину	z min x	ij	, которая

равна наименьшей из поставок в клетках цикла, отмеченных знаком «-».

Клетка, с которой начинают сдвиг, остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляются базисные нули, чтобы число занятых клеток осталось равным m n 1.

7) Перейти к пункту 3 данного алгоритма.

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

Упражнения 13

13.1. На двух складах А и В находится по 90 т горючего. Перевозка одной тонны горючего со склада А в пункты 1, 2, 3 соответственно стоит 1, 3 и 5 у.е.,

а перевозка одной тонны со склада В в те же пункты – соответственно 2, 5 и 4

54

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

13.2. В резерве трех железнодорожных станций А, В и С находится,

соответственно, 60, 80 и 100 вагонов. Составить оптимальный план перегона этих вагонов к четырем пунктам перевозки хлеба, если пункту №1 необходимо 40 вагонов, №2 – 60 вагонов, №3 – 80 вагонов и №4 – 60 вагонов. Стоимость перегона одного вагона со станции А в указанные пункты, соответственно,

равны 1, 2, 3, 4 у.е., со станции В – 4, 3, 2,0 у.е. и со станции С – 0, 2, 2, 1 у.е.

13.3. Завод имеет три цеха А, В, С и четыре склада №1, 2, 3 и 4. Цех А производит 30 тыс. штук изделий, цех В – 40 тыс. шт., цех С – 20 тыс. шт. Пропускная способность складов за то же время характеризуется следующими показателями: склад №1 - 20 тыс. шт., склад №2 – 30 тыс. шт., склад №3 – 30

тыс. шт., склад № 4 – 10 тыс. шт. Стоимость перевозки 1 тыс. шт. изделий из цеха А в склады 1, 2, 3 и 4 соответственно равны 2, 3, 2 и 4 у.е.; из цеха В -3, 2,

5, 1 у.е., а из цеха С – 4, 3, 2 и 6 у.е. Составить такой план перевозок изделий, при котором расходы на перевозку 90 тыс. шт. изделий были бы наименьшими.

13.4. Решить транспортные задачи, исходные данные которых заданы таблицей:

а)

b	j

a	i

200

300

500

200	200	300	400
4	3	2	1
2	3	5	6
6	7	9	12

55

б)

b	j

a	i

100

200

400

200

100	200	200	300
1	3	4	1
5	2	2	7
4	4	3	6
7	2	5	3

Домашнее задание №13

1.В двух пунктах отправления А и В находятся, соответственно, 150 и 90

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

2.На трех складах А, В, С находится сортовое зерно, соответственно, 10, 15, 25 т, которое надо доставить в четыре пункта: пункту №1 – 5 т, №2 – 10 т, №3 – 20 т, №4 – 15. Стоимости перевозки одной тонны со склада А в указанные пункты соответственно равны 8, 3, 5, 2 у.е.; со склада В - 4, 1, 6, 7

у.е. и со склада С – 1, 9, 4, 3 у.е. Составить оптимальный план перевозки зерна

вчетыре пункта, минимизирующий стоимость перевозок.

3.Решить транспортную задачу, исходные данные которой заданы таблицей:

b	j
ai		200	400	400	800
200		1	6	9	3
400		3	2	2	4
600		4	5	4	7
200		1	4	3	9

56

Приложения Приложение А. Задания домашней контрольной 1

А. 1. Даны матрицы А, В и Е (Е - единичная матрица). Найти матрицу С,

удовлетворяющую равенству:

		2	1	1			0	2	1
											. C AB 2A 4E .
1.	A	0	4	2		, B	2	5	3
		3	5	1			8	12	2

2.

		1	1
	A	0	2
		5	3

2
4
0

,

	2	1
B	4	2
	0	5

2

.

C

AB

3A

4E

.

3.

4.

	1
A	2
	3
	1
A	3
	1

2 4 6

2 02

3 1 2

,	B
0
4		,
1

	1			1
	1			- 2
		2		1
			3	1
	B		2	1
			0	1

0
3	.
- 3

2

.

C AB 4A

C AB 4A

2E .

2E .

		3	1	1				0	1	1
5.	A	2	1	2		,	B	1	2	1	.
		1	2	5				2 0		2

C

AB

A

5E

.

6.

2		0
A	1	3
	0	2

1

,

	1	1
B	2	1
	1	0

1

1

. C AB 2A 2E .

7.

	0	1
A 1		2
	0	1

2
0
1

,

1		2	4
B	1	3	4	.
	1	2	1

C

AB

2A

4E

.

	1 2			0		3		1	0
											. C AB 3A E .
8.	A	3	0	4		, B	2 1		2
		1	2	1			0	1	1

57

9.

	3	1
A	2	1
	1	2

,

	1	1
B	2	1
	1	0

		продолжение приложения А. 1
1
1		. C AB 5A E .
1

10.

		0	1	2
	A	1	4	2
		2	1	3

,

		1	3
	B	2	1
		1	3

1
5
0

.

C

AB

3A

5E

.

		2	1	1			2	1	3
											.C AB 2A 4E .
11.	A	0	4	2		, B	4	2	1
		3	5	1			0	5	2

12.

13.

		1	1
	A	0	2
		5	3
		1	2
	A	3	0
		1	2

2
4		,
0
0
4	,
1

	0	2
B	2	5
	8	12

		1	1
	B	1	- 2
		2	1

	1
	3	.
	2
	0
	3	.
	- 3

C

C

AB

AB

3A

4A

4E

2E .

.

		1	2	3
14.	A	2	4	1		,
		3	6	2

	3	1
B	2	1
	0	1

2

. C AB 4A 2E .

15.

16.

	3	1	1						1
A	2	1	2			,	B		2
	1	2	5						1
2		0	1					0
A	1	3	2	,			B	1
	0	2	1					2

11 0

1 2 0

	1
	1			. C
	1
1
			C
1		.
2

AB A

AB 2A

5E .

2E .

	0		1	2		3		1	0
17.			2						2		C AB 2A 4E .
	A 1			0		, B	2	1		.
		0	1	1			0	1	1

58

продолжение приложения А. 1

18.

19.

20.

	1
A	3
	1
	3
A	2
	1
	0
A 1
	2

2 02

11

12

23

1 41

	0					1
	4
		,		B 1
	1						1
						1
		B				2
	,
						1
	2							1
				B				2
	2		,
	3							1

23 2

3 13

11 0

1 5 0

4
			C AB 3A
4	.
1
		C AB 5A
.
1
1			. C AB 3A
1

E .

E .

5E

.

1.

А. 2. Дана матрица А.

AA	1	E		.
	3		2		4
							. 2.	A
A 2			1		2
	2		1		3

Найти матрицу, обратную данной. Проверить,

1	2	3				1	3 1				3	3
2	2	1		. 3.					. 4.
					A	1	1 2			A	3	3
2	1	2				2	1 2				1	2

что

1
2	.
1

5.

2		3
A	1	3
	5	4

1

. 6.

		2	1
	A	4	1
		5	3

2

. 7.

	2	1
A	2	1
	3	2

	3
	2
	5

. 8.

2		2	1
A	2	1	3
	1	2	2

		2	2	1
9.	A	2	1	2		.10.
		1	2	3

	4		5
	A	3	1
		5	1

3
2
2

	2		1	1			0		1	2
.11.						. 12.		1 4
	A	0	4	2			A			2
		3	5	1				2	1	3

	1		3 1				1 2				0			2			0 1					3		1	0
13.						. 14.							15.		1		3
	A	2	1	5			A	3		0	4 .			A				2	. 16.			A	2	1	2
		1	3	0				1		2					0		2 1						0	1	1
											1
	1		1	2			3 1				1					2	1	3					1	1	1
17.						. 18.				1			. 19. A								. 20.			1
	A	0	2	4			A		2		2					4	2	1				A	2		1	.
		5	3	0					1 2		5					0	5 2						1	0	1

59

А. 3. Дана система линейных уравнений. Решить ее: а) методом обратной матрицы; б) по формулам Крамера; в) методом Гаусса.

	1.
	4.

2х 2х			х	12
1		2	3
3х х		3х		21	;
1	2		3
х 3х		2х		9
1	2		3

-2 х1 5х 2 6х 3 8

х1 7х 2 5х 3 9

4х	1	2х	2	х	3	12

;

2.

5.

	x	1	2x				2	x			3	8
	2x					3x					3x
					1					2				3
				4x					5x
3x			1					2					3

		2x		1	3x		2	x	3
				1 x 2			5x 3
	4x
		x		2x			4x
			1			2			3

5 10

4 6 ; 9

;

	3x		2x					x				5
		1					2				3
3.		x 2				x3				0					;
	x1
			x				5x					3
	4x	1				2					3
	3х				1	5х				2	6х				3
6.			2х1			3х 2					5х 3
			х		4х					х				1
				1					2				3

5 8

;

	4x					7x							3x							10
				1							2						3
7.			2x1							9x 2						x 3					8
		x								6x						3x					3
							1							2						3
			5x					1		8x				2		x		3			7
10.										3x						2x					9	;
		2x				1							2						3
			x						2x						3x						1
					1							2						3

;

		3x		1	2x			2		5x			3		6						3х		1	9х			2		8х			3			5
8.					3x 2					4x 3				20				;	9.		2х1			5х 2					5х 3						4	;
	2x1
			x1		2x 2					3x 3				6							2х1			х 2				х 3			4
				х		х				3х					0							2x		3x					x					1
					1				2					3									1					2			3
11.			3х				2х					2х					1		12.			x	x			4x					0					;
						1					2					3
																						1			2					3
				х		х				5х					2							4x		5x					3x						1
									2					3														2					3
					1																		1

13.

16.

19.

3x			2x					x				5
		1				2			3
	x	3x				2x						2				;
				2						3
	1
			2x					4x						7
5x						2						3
		1
x		2x		2		3x			3			1
	1
			3x					x				7			;
2x						2			3
		1
			x			2x						0
4x				2						3
		1
4x			x		2		3x				3		1
		1
			2x					4x						8		;
3x							2						3
		1
	2x		2x					4x						0
							2						3
		1

14.

17.

20.

x				4x			2		2x				3		5
			1
	4x					x			3x						3				;
							2					3
				1
	2x					3x					4x						1
									2						3
				1
3x						x	2		4x			3			2
				1														;
		x			2x				3x								7
							2					3
			1
						3x				2x						8
	5x								2					3
					1
2x1 x2 3x3 1
x 2x								2		5x				3		9 .
				1
4x 3x										2	2x					3	4
						1

15.

18.

2x			4x				2	3x					3		2
		1
	x	x			2x						0					;
				2					3
	1
			2x					x						5
	3x						2				3
		1
3x			3x			2		2x				3			4
	1
	2x		x				3x						1
					2					3
		1
	x	2x					5x						1
					2					3
	1

;

А. 4. Найти общее решение системы линейных уравнений методом Гаусса.

	3x x			2	8x 2x	4	x 0			x1 x2 3x3 2x4 3x5 4
		1			3			5
1.			2x2 3x3 7x4 2x5 0 ;						2			2x2		4x3 x4 3x5 6 ;
	2x1									2x1
		11x2 12x3 34x4 5x5 0										3x2		5x3 2x4 3x5 6
	x1									3x1
	x 5x			2	2x 16x		4	3x 0		2x	1	2x	2	8x	3	3x	4	9x	5	14
	1				3			5

60