Metody_optimizatsii_Shatina_A_V

51
′	,c2 ) = e перпендикулярен пря-
мых. Вектор–градиент f ( x) = (c1
мым (7) и указывает направление возрастания функции f ( x) .

Если перемешать параллельно самой себе произвольную прямую

(7), проходящую через допустимое множество Dз , в направлении e до тех пор, пока эта прямая будет иметь хотя бы одну общую

точку с множеством Dз , то в своем крайнем положении указанная прямая пройдет через точку множества Dз , в которой функ-

ция f ( x) принимает максимальное на Dз значение. Если перемещать произвольную прямую (6) в противоположном направлении до тех пор, пока эта прямая будет иметь хотя бы одну общую точ-

ку с множеством Dз , то получим точку, в которой f ( x) принимает минимальное значение на множестве Dз .

Заметим, что в случае, когда Dз		представляет собой неогра-
ниченное множество	на плоскости Ox1x2 , возможно,		что
fmax = +∞ ( fmin = −∞) .	Если прямая	(7) параллельна одной	из

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

Рис. 5.1

52

Рис. 5.2

Пример 1. Решить задачу линейного программирования:

2x1 + x2 ® max

- x1 + x2 £ 4; x1 + x2 £ 6; 3x1 - x2 £ 6;

x1 ³ 0, x2 ³ 0.

Решение. Изобразим на плоскости Ox1x2 допустимое множество

Dз данной задачи. Оно представляет собой многоугольник OABCD с вершинами в точках O(0;0), A(0;4), B(1;5) , C(3;3), D(2;0)

(рис. 5.3). Построим одну из линий уровня целевой функции f ( x) 2x1 + x2 = c . Вектор-градиент e = (2;1) указывает направление

возрастания функции f ( x) . Совершая параллельный перенос линии уровня вдоль направления e, находим ее крайнее положение.

В своем крайнем положении прямая 2x1 + x2 = c проходит через

точку C(3;3)	многоугольника	Dз . Откуда следует, что
(3;3) Î absmax з,	fmax = f (3;3) = 9.	●

53

Рис. 5.3

Пример 2. Решить задачу линейного программирования:

x1 - x2 ® extr

- x1 + x2 £ 4; x1 + x2 £ 6; 3x1 - x2 £ 6;

x1 ³ 0, x2 ³ 0.

Решение. Множество допустимых точек этой задачи совпадает с Dз в примере 1 (см. рис. 5.3). Изобразим линию уровня

x1 - x2 = c . Вектор e = (1;-1) указывает направление возрастания целевой функции (рис. 5.4). Совершая параллельный перенос линии уровня вдоль направления e, получим, что максимальное значение целевая функция достигает в точке D . Поэтому

(2;0) Î abs max з, fmax = f (2;0) = 2 .

Перемещая линию уровня параллельно самой себе в противоположном направлении, получим, что в своем крайнем положении она содержит отрезок AB . Любая точка отрезка AB предста- вима в виде: xα = α (0;4) + (1- α )(1;5) = (1- α;5 - α ), α Î[0;1] .

54
Поэтому (1- α;5 - α ) Î abs min з, α Î[0;1], fmin = -4.	●

Рис 5.4 Пример 3. Решить задачу линейного программирования:

x1 + 2x2 ® extr

- 2x1 + x2 £1; x1 + x2 ³ 1; x1 - 2x2 £ 1;

x1 ³ 0, x2 ³ 0.

Решение. Допустимое множество Dз данной задачи представляет собой неограниченное многоугольное множество (рис. 5.5). Функция f ( x) = x1 + 2x2 возрастает в направлении e = (1;2) . При

параллельном переносе прямой x1 + 2x2 = c в направлении e функция f неограниченно возрастает. Поэтому fmax = +¥ . При параллельном переносе прямой x1 + 2x2 = c в противоположном направлении крайней точкой пересечения этой прямой с Dз яв-

ляется точка (1;0) . Следовательно, (1;0) Î abs min з, fmin = 1 .

●

55

Графический метод используется также для задач линейного программирования в общей постановке, если отсутствует ограничение (2), а число свободных переменных системы (1) не больше двух.

Рис. 5.5 Пример 4. Решить задачу линейного программирования:

x	+ 3 x		- 7 x	4	+ 3 x ® max
1	2	3	4		4	5
- 3x1 + 3x2 + x3 + x4 - x5 = 4;
	4x1 + x4 + x5 = 12 ;
	3x1 - x2 + x5 = 6;
	xi	³ 0,			i = 1,...,5.

Решение. Матрица системы ограничений имеет вид:

æ- 3		3	1	1	-1ö
ç	4	0	0	1	1	÷
A = ç						÷
ç	3	-1	0	0	1	÷
è						ø .

Ранг этой матрицы равен 3. Число свободных переменных равно 5-3=2. Выберем в качестве базисного минора мир, образованный последними тремя столбцами матрицы A и разрешим систему

допустимое множество Dз

56

ограничений-равенств относительно базисных переменных x3, x4, x5 . Т.е. выразим базисные переменные x3, x4 , x5 через сво-

бодные x1, x2 . Получим:

x3 = x1 - x2 + 4, x4 = 6 - x1 - x2 ; x5 = 6 - 3x1 + x2 .

Подставим эти значения x3, x4 , x5 в целевую функцию, тогда целевая функция примет вид:

~		( x1, x2 ) = 2x1 + x2 .
f
С учетом условия		xi ³ 0,	i = 1,...,5, получим следующую
задачу:
~	( x1, x2 ) = 2x1 + x2 → extr
f
		x1 ³ 0,	x2 ³ 0,

x3 = x1 - x2 + 4 ³ 0 , x4 = 6 - x1 - x2 ³ 0; x5 = 6 - 3x1 + x2 ³ 0 .

Полученная задача совпадает с задачей в примере 1. Поэтому

(3;3;4;0;0) Î absmax з , fmax = 9 . ●

Во многих случаях на допустимое множество задачи линейного программирования (1)–(3) накладывается дополнительное требо-

вание целочисленности переменных x j . Если этому требованию должны удовлетворять все переменные, то получаем полностью целочисленную задачу линейного программирования. Полностью целочисленную задачу линейного программирования с двумя переменными (4)-(6) можно решить графически, учитывая, что

этой задачи состоит из точек целочис-

ленной координатной сетки, принадлежащих множеству Dз задачи линейного программирования без дополнительного требования

57

Рис. 5.6

Пример 5. Найти решение целочисленной задачи линейного программирования:

x1 - 3x2 ® extr

- 3x1 + 4x2 £ 8; x1 + x2 £ 5,5;

x1 ³ 0, x2 ³ 0, x1, x2 Î Z .

Решение. На плоскости Ox1x2 построим допустимое множество рассматриваемой задачи без требования целочисленности

переменных x1, x2 . Получим многоугольник OABC (рис. 5.6). Отметим внутри этого многоугольника точки с целочисленными координатами. Совокупность этих точек представляет собой до-

пустимое множество Dз полностью целочисленной задачи. Перемещая линию уровня x1 - 3x2 = c в направлении e = (1;-3) возрастания функции f ( x) , находим крайнее положение этой линии, в котором она еще имеет непустое пересечение с множеством Dз .

Получаем точку (5;0) . Следовательно (5;0) Î abs max з, fmax = 5 . Перемещая линию уровня в направлении, противоположном век-

тору e = (1;-3) ,	получим решение задачи	на минимум:
(2;3) Î abs min з,	fmin = -7 .	●

58

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

Решить задачи линейного программирования графическим

методом:
5.1.		5.2.
x1 - 2x2 ® min ,			- x1 - 3x2 ® min ,
2x1 + x2 £ 3,			2x1 + x2 £ 2,
- x1 + x2 £ 0,			x1 - x2 ³ 0,
x1 - x2 £ 1,			x1 - x2 £ 1,
x1 ³ 0, x2 ³ 0.			x1 ³ 0, x2 ³ 0.
5.3.		5.4.
x1 + x2 ® max ,			- x1 + x2 ® extr ,
2x2 ³ 1,		2x1 - 4x2 - x3 + x4 = -3,
x1 + x2 £ 3,		4x1 - 3x2 - x3 + x4 + x5 = 6 ,
x1 £ 2, x2 £ 2	,	x + 4x		2	+ x		3	+ x	5	= 15	,
2x1 + x2 ³ 2,		1
		x j ³ 0,	j = 1,...,5			.
x1 ³ 0, x2 ³ 0.
5.5.		5.6.
x1 + 2x2 + x3 - x4 ® extr ,		4x1 - 2x2 - x3 + x4 ® min ,
10x2 + x3 + 2x4 + 3x5 = 25,		3x1 + 2x2 - x3 + 4x4 = 3,
- x1 + 5x2 + x3 + x4 + x5 = 10,		x1 - x2 + 4x3 - 2x4 = 2,
2x1 - x2 + x3 - 3x4 = 6 ,			x j		³ 0,			j = 1,...,4 .

xj ³ 0, j = 1,...,5.

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

Таблица 5.1

	59
Компоненты сплава	Содержание компонентов в %
	сплав № 1	сплав № 2
Медь	10	10
Олово	10	30
Цинк	80	60
Стоимость 1 кг	4	6

Получаемый сплав должен содержать не более 2 кг меди, не менее 3 кг олова, а содержание цинка может составлять от 7,2 до 12,8 кг.

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

5.8.В контейнер упакованы комплектующие изделия трех типов. Стоимость и вес одного изделия составляют 400 тыс. руб. и 12 кг для первого типа, 500 тыс. руб. и 16 кг для второго типа, 600 тыс. руб. и 15 кг для третьего типа. Общий вес комплектующих равен 326 кг. Определить минимальную и максимальную возможную суммарную стоимость находящихся в контейнере комплектующих изделий.

5.9.Детский сад планирует приобрести на сумму 220$ наборы конфет. Наборы одного типа стоят 5$ ( в каждой коробке 50 конфет), наборы второго типа стоят 18$ ( в каждой коробке 190 конфет), наборы третьего типа стоят 15$ ( в каждой коробке 160 конфет). Сколько коробок каждого типа должен купить детский сад, чтобы общее число купленных конфет было максимально?

5.10.В цехе площадью 74 м2 необходимо установить станки, на приобретение которых отпущено 42 тыс. руб. Существует два типа станков. Станок первого типа стоимостью 6 тыс. руб., требу-

ющий 12 м2 производственных площадей, обеспечивает изготовление 70 изделий в смену. Аналогичные характеристики станка

второго типа составляют соответственно 4 тыс. руб., 6 м2 , 40 изделий в смену.

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

60

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

Постановка задачи линейного программирования в общей форме имеет вид:

f ( x) = c1x1 + ××× + cn xn ® extr

(з)

n

åaij x j = bi ,

i = 1, ... ,l,

j=1

n

åaij x j £ bi ,

i = l +1, ... , m,

j=1

x j ³ 0,

j = 1, ... , n.

Здесь

aij , bi ,c j (i = 1, ... , m, j = 1, ... , n)

– заданные

величины,

x j ( j = 1, ... , n)

– неизвестные переменные.

Задачей линейного программирования в канонической форме

называется следующая задача:

x ³ 0.

(c, x) ® max;

Ax = b,

(з )

x = ( x , ... , x

) Î Rn

к

Здесь

n

–

неизвестная

переменная,

1

c = (c , ... ,c

n

) Î Rn

и

b = (b , ... ,b

) Î Rm

– заданные

векторы,

1

...

1

m

A = (a

)i=1, ... ,m

æ a11

a1n

ö

= ç ... ... ...

÷

ij

ç

÷

j=1, ... ,n

ç

...

÷

èam1

amn

ø

–

заданная

матрица

размера

æ

ö

a j

ç a1 j

÷

j = 1, ... , n

= ç ...

÷,

m × n со столбцами

ç

÷

èamj

ø

.

Задачей линейного программирования в нормальной форме

называется следующая задача:

x ³ 0.

(c, x) ® max;

Ax £ b,

(з )

н

Задачи линейного программирования в различных формах

можно

свести

друг

к другу

путем введения

дополнительных