Metody_optimizatsii_Shatina_A_V

	91
æ	1	0	1	ö
ç	0	0	0	÷
D = ç				÷
ç	2	0	0	÷
è				ø.

Так как D ³ 0 , то третий план перевозок, полученный в пункте 5′

), является оптимальным. Найдем значение функционала (c, x) :

(c, x) = 1× 30 + 2 × 20 + 0 ×10 + 3×10 + 0 ×10 = 100.

Заметим, что в исходной задаче, задаваемой платежной мат-

рицей в виде таблицы 7.1, пункт отправления A3 отсутствовал, он был искусственно введен для сведения задачи к замкнутой моде-

ли. Тот факт, что в полученном плане перевозок x32 = 10 ¹ 0,

x33 = 10 ¹ 0 , означает, что пункты назначения B2 , B3 не будут полностью обслужены. Выпишем ответ для поставленной задачи.

ˆ	æ	0	20	0	ö		= 100
x = ç					÷, S	min
Ответ:	ç	30	0	10	÷		.
	è				ø

●

Пример 3. Решить транспортную задачу, заданную платежной матрицей (табл. 7.5).

Таблица 7.5

		b1 = 11	b2 = 2	b3 = 6	b4 = 7
a1	= 7	2	3	4	1
a2	= 8	3	4	2	5
a3	= 5	1	7	5	7
a4	= 6	5	2	8	2

Решение:

4	4
åai = åbj		= 26
1) В данной задаче i=1	j =1	, т.е. имеем замкнутую

модель	транспортной задачи.
2)	Методом северно-западного угла найдем начальный план
перевозок:
			b1 = 11		b2 = 2	b3 = 6	b4 = 7

						92
	a1 = 7	7
	a2 = 8	4				2			2
	a3 = 5								4	1
	a4 = 6									6
3) Построим матрицу					:
			C
		v1 = 2				v2 = 3			v3 = 1	v4 = 3
	u1 = 0	2				3			1	3
	u2 = 1	3				4			2	4
	u3 = 4	6				7			5	7
	u4 = −1	1				2			0	2

4) Найдем матрицу D = C - C :
æ	0	0	3	− 2	ö
ç	0	0	0	1	÷
ç					÷
D = ç	- 5	0	0	0	÷
ç					÷
ç	4	0	8	0	÷
è					ø.
Наименьший отрицательный			элемент матрицы			равен

31= −5 < 0.

5)Построим новый план перевозок, добавляя в предыдущий

план перевозок на место нулевого небазисного элемента x31 величину t > 0 :

		7
		4 − t			2		2 + t
		t					4 − t		1
t=4									6
¾¾®
	7
	0			2		6
	4							1
								6

93

Заметим, что здесь обратились в ноль два элемента x21 и x33

. Исключим из числа базисных компонент элемент x33 с большей стоимостью перевозки.

Перейдем к пункту 3′ ). 3′) Построим матрицу C :

	v1 = 2	v2 = 3	v3 = 1	v4 = 8
u1 = 0	2	3	1	8
u2 = 1	3	4	2	9
u3 = −1	1	2	0	7
u4 = −6	-4	-3	-5	2

4′) Найдем матрицу D = C - C :

æ	0	0	3	− 7	ö
ç	0	0	0	- 4	÷
ç					÷
D = ç	0	5	5	0	÷
ç					÷
ç	9	5	13	0	÷
è					ø

Наименьший отрицательный элемент матрицы равен

14 = −7 < 0 .

5′) Построим новый план перевозок, добавляя в предыдущий

план перевозок на место нулевого небазисного элемента x14 величину t > 0 :

	7 − t			t
	0	2	6
	4 + t			1− t
				6
	t=1
¾¾®
	6			1

		94
0	2	6
5
			6

3′′) Построим матрицу C :

		v1 = 2	v2 = 3			v3 = 1	v4 = 1
u1 = 0		2	3			1	1
u2	= 1	3	4			2	2
u3 = −1		1	2			0	0
u4	= 1	3	4			2	2

4′′) Найдем матрицу D = C - C :
æ	0	0	3	0	ö
ç	0	0	0	3	÷
ç					÷
D = ç	0	5	5	7	÷
ç					÷
ç	2	- 2	6	0	÷
è					ø

Наименьший отрицательный элемент матрицы равен

42 = −2 < 0.

5′′) Построим новый план перевозок, добавляя в предыду-

щий план перевозок на место нулевого небазисного элемента x42 величину t > 0 :

	6 − t			3
	0 + t	2 − t	6
	5
		t		4
	t=2
¾¾®
	4			3
	2		6
	5
		2		4

3′′′) Построим матрицу C :

95

		v1 = 2	v2 = 1	v3 = 1	v4 = 1
u1 = 0		2	1	1	1
u2	= 1	3	2	2	2
u3 = -1		1	0	0	0
u4	= 1	3	2	2	2

4¢¢¢) Найдем матрицу D = C -				:
			C
æ	0	2	3		0	ö
ç	0	2	0		3	÷
ç						÷	³ 0
D = ç	0	7	5		7	÷
ç						÷
ç	2	0	6		0	÷	.
è						ø

Так как D ³ 0 , то четвертый план перевозок, полученный в пункте 5′′), является оптимальным. Найдем значение функционала

(c, x) :

(c, x) = 2 × 4 + 3× 2 +1× 5 + 2 × 2 + 2 × 6 +1× 3 + 2 × 4 = 46.

	æ	4	0	0	3	ö
	ç	2	0	6	0	÷
ˆ	ç					÷	,	Smin = 46
x = ç		5	0	0	0	÷
	ç					÷
Ответ:	ç	0	2	0	4	÷		. ●
	è					ø

Пример 4. Решить транспортную задачу, заданную платежной матрицей (табл. 7.6), при дополнительном требовании полно-

го вывоза груза из пункта A2 .

Таблица 7.6

	b1 = 10	b2 = 20
a1 = 25	1	2
a2 = 15	3	4

Решение:

96
	2	2
1) Так как a1 + a2 = 40, b1 + b2 = 30	å ai > åbj
	, то i=1	j =1 . Для

приведения к замкнутой модели введем фиктивный пункт назна-

чения B3 с требуемой величиной ввоза b3 = 40 − 30 = 10. Так как в задаче имеется дополнительное требование полного удовлетво-

рения вывоза груза из пункта A2 , то положим c31 = 0, c32 = M , где M - достаточно большое положительное число. Получим замкнутую модель транспортной задачи со следующей платежной матрицей:

b1 = 10

b2 = 20

b3 = 10

a1 = 25

1

2

0

a2 = 15

3

4

M

2) Найдем начальный план перевозок методом «северо-за-

падного угла».

Первоначальный план перевозок:

b1 = 10

b2 = 20

b3 = 10

a1 = 25

10

15

a2 = 15

5

10

3) Построим матрицу

:

C

v1 = 1

v2 = 2

v3 = M − 2

u1 = 0

1

2

M − 2

u2 = 2

3

4

M

4) Найдем матрицу D = C -

:

C

æ

0

0

2 − M ö

D = ç

÷

ç

0

0

0

÷

как M

è

ø.

Так

-

достаточно

большое число, то

min

ij =

13 = 2 − M < 0

i, j

.

5) Построим новый план перевозок, добавляя в предыдущий

97

план перевозок на место нулевого небазисного элемента x13 величину t > 0 :

10	15 - t	5	t	10
	10
	5 + t 1510 - t

3′) Построим матрицу C :

v1 = 1

v2 = 2

v3 = 0

u1 = 0

1

2

0

u2 = 2

3

4

2

4′) Найдем матрицу D = C -

:

C

æ

0

0

0

ö

D = ç

÷

ç

0

0 M

- 2

÷

è

ø.

Так как D ³ 0 , то полученный в пункте 5) план перевозок являет-

ся оптимальным. При этом из пункта A2 весь груз будет вывезен,

а в пункте A1 останется 10 единиц груза. Найдем значение функ-

ционала (c, x) :

(c, x) = 1×10 + 2 × 5 + 0 ×10 + 4 ×15 = 80 .

ˆ

æ10

5

ö

S

= 80

x

= ç

÷,

min

Ответ:

ç

15

÷

. ●

è 0

ø

Задачи для самостоятельного решения.

Решить транспортные задачи с заданными платежными матрицами:

7.1.

		b1 = 2	b2 = 3	b3 = 4	b4 = 3
a1	= 3	1	2	3	4
a2	= 4	4	3	2	0

				98
	a3 = 5		0	2	2	1
7.2.
			b1 = 50	b2 = 100	b3 = 40	b4 = 110
	a1	= 85	2	3	1	2
	a2	= 90	5	2	4	1
	a3 = 125		4	2	3	5

7.3.

		b1 = 30	b2 = 30	b3 = 20
a1	= 20	1	2	3
a2	= 40	2	3	3

7.4.

		b1 = 130	b2 = 220	b3 = 60	b4 = 70
a1	= 120	1	7	9	5
a2 = 280		4	2	6	8
a3	= 160	3	8	1	2

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

значения B2 :

	b1 = 25	b2 = 15
a1 = 10	1	2
a2 = 20	3	4

Занятие 8. Простейшая задача классического вариационного исчисления.

Рассмотрим некоторое функциональное пространство X .

Пусть каждому элементу x = x(t) Î G Ì X поставлено в соответствие число I . Тогда говорят, что на множестве G X задан

функционал I( x) = I( x(×)) .

Линейное пространство X называется нормированным, если

99

на

X

определен функционал

×

: X ® R , называемый нормой и

удовлетворяющий условиям:

а)

x

³ 0 "x Î X , причем

x

= 0 Û x = 0;

б)

αx

=

α

×

x

"α Î R, "x Î X ;

в)

x1 + x2

£

x1

+

x2

"x1, x2 Î X .

Будем рассматривать следующие функциональные про-

странства:

1) C([t0 ;t1])

- пространство функций, непрерывных на отрез-

[t

;t

]

x(×)

0

=

max

x(t)

t

[t

,t

]

ке

0

с введенной в нем нормой

0

;

1

1

2)

C1([t

0

;t

])

- пространство функций, имеющих непрерыв-

1

ную производную на отрезке [t0 ;t1] с нормой

x(×)1 = max{ x(×)0, x(×)0} .

Определение. Простейшей задачей классического вариационного исчисления (КВИ) называется следующая экстремальная

задача в пространстве C1([t0 ;t1]) :

I( x(×)) =	t1		x(t0 ) = x0, x(t1) = x1
	ò
		L(t, x(t) , x(t))dt ® extr;
	t0		.	(з)

Здесь L = L(t, x, x) - функция трех переменных, называемая
интегрантом, отрезок [t0 ;t1] фиксирован и конечен, t0 < t1.						▲
Определение. Функции	x(×) ÎC1([t	0	;t	])	, удовлетворяющие
			1
краевым условиям x(t0 ) = x0 ,	x(t1 ) = x1, называются допустимы-
ми.						▲

0100090000030202000002008a01000000008a01000026060f000a03

574d464301000000000001005e860000000001000000e80200000000

0000e8020000010000006c00000000000000000000002c0000007100

00000000000000000000582300001221000020454d4600000100e802

100

00000e0000000200000000000000000000000000000080120000a81a

0000c800000021010000000000000000000000000000400d0300e868

0400160000000c000000180000000a00000010000000000000000000

000009000000100000005c080000d0070000250000000c0000000e00

0080120000000c000000010000005200000070010000010000009cffff

ff00000000000000000000000090010000000000cc074000125400690

06d006500730020004e0065007700200052006f006d0061006e000000

00000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000

0000000000000000d935093000000000040000000000ae3016360930

0000000047169001cc0002020603050405020304ff3a00e0417800c00

900000000000000ff01000000000000540069006d0065007300200000

0065007700200052006f006d0061006e000000333f00002c0c0000101

4000074481700387d086e000000005848170012b50230584817004c6

eaf30704817006476000800000000250000000c000000010000001800

00000c00000000000002540000005400000000000000000000002c00

00007100000001000000982287408d858740000000005a0000000100

00004c0000000400000000000000000000005a080000d00700005000

00002000ffff2d00000046000000280000001c0000004744494302000

000ffffffffffffffff5d080000d107000000000000460000001400000008

0000004744494303000000250000000c0000000e0000800e00000014

0000000000000010000000140000000400000003010800050000000b

0200000000050000000c02f0000101040000002e0118001c000000fb0

20200010000000000bc02000000cc0102022253797374656d0000000

03f3f3f3f0000000000000000000000003f3f3f3f3f00040000002d0100

0004000000020101001c000000fb02f4ff0000000000009001000000cc

0740001254696d6573204e657720526f6d616e0000000000000000000

000000000000000040000002d010100050000000902000000020d000

000320a0b00000001000400000000000001f00020000500040000002

d010000030000000000

Рис. 8.1

Определение. Говорят, что допустимая функция xˆ(×) достав-