А.В.Шатина МО 2012 версия 20.09.2013

51

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

x	x			2	extr
1
x			x				2				4;
	1
x		x			2				6;
	1
3x			x			2				6;
	1
x	0,				x			2			0 .
1

Решение. Множество допустимых точек этой задачи совпадает с

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 .
Поэтому 1 ;5 abs min з, 0;1 , fmin 4.	●

Рис 5.4

52

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

x	2x	2	extr
1

2x x				1;
1		2
x x	2		1;
1
x 2x		2		1;
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 .			●

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

Рис. 5.5

53

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

x		3	x		7	x		3	x	max
1		2	3		4	4		4	5

3x1 3x2 x3 x4 x5 4 ;

4x		x		4		x	12	;
	1					5
3x			x		2	x	6;
	1					5
x	0,					i 1,...,5.
i

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

3		3	1	1
A	4	0	0	1
	3	1	0	0

1

1

.

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

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

бодные x1, x2

. Получим:

Подставим эти значения

x3 x4 x5

x3

x1 x2 4		,
6 x1	x2	;
6 3x1	x2 .
, x4 , x5 в целевую функцию, тогда це-

левая функция примет вид:
~	x1		2x1	x2 .
f		, x2

С учетом условия

x	0,
i

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 .

54

му

Полученная задача совпадает с задачей в примере 1. Поэто-
3;3;4;0;0 absmax з , fmax 9 .	●

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

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

с двумя переменными (4)-(6) можно решить графически, учиты- ~ вая, что допустимое множество Dз этой задачи состоит из точек

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

требования целочисленности переменных x j .

Рис. 5.6

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

x1 3x2	extr
3x 4x		2	8;
1
x1 x2	5,5;

x1 0, x2 0, x1, x2 Z .

	55
Решение. На плоскости	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 .	●

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

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

методом:
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.

x1 x2	max ,
2x2	1,
x1 x2 3,
x1 2, x2		2,
2x1 x2		2 ,
x1 0, x2		0 .

5.4.

x1 x2 extr,

2x1 4x2 x3 x4 3,

4x1 3x2 x3 x4 x5 6 , x1 4x2 x3 x5 15 ,

x j 0, j 1,...,5.

56

5.5.

x1 2x2 x3 x4 extr,

10x2 x3 2x4 3x5 25,

x1 5x2 x3 x4 x5 10,

2x1 x2 x3 3x4 6 , x j 0, j 1,...,5.

5.6.

4x	2x	2	x x		4	min
1				3
3x1 2x2 x3 4x4 3 ,
x1 x2 4x3 2x4 2,
	x j 0,			j 1,...,4 .

,

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

		Таблица 5.1
Компоненты	Содержание компонентов в %
сплава
	сплав № 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 кг. Определить минимальную и максимальную возможную суммарную стоимость находящихся в контейнере комплектующих изделий.

57

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

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

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

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

40 изделий в смену.

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

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

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

форме имеет вид: f x

линейного программирования в общей

c1x1 cn xn extr

(з)

		n				b ,		i 1, ... ,l,
		a		x	j
		ij					i
		j 1
		n		b ,			i l 1, ... , m,
		a x	j
		ij				i
		j 1
		x j			0,		j 1, ... , n.
Здесь	aij , bi , c j	i 1, ... , m, j 1, ... , n							– заданные	величины,
x j j 1, ... , n – неизвестные переменные.
Задачей линейного программирования в канонической форме
называется следующая задача:
		c, x max;					Ax b,		x 0.	(зк)
Здесь	x x , ... , x Rn						–	неизвестная		переменная,
	1	n

58

c c	, ... , c Rn	и b b , ... ,b		Rm	– заданные векторы,
1	n	1	m

A aij i 1, ... ,m

j 1, ... ,n

столбцами a	j

...

... ...

...

a11am1

	a
		1 j
	...			,
		a
			mj

a1n

... –

a

mn

j 1, ...

заданная матрица размера

, n .

m n

со

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

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

c, x max;

Ax b,

x 0.

(зн)

Задачи линейного программирования в различных формах можно свести друг к другу путем введения дополнительных ко-

ординат, изменения матрицы A, изменения знака целевой функ-
ции	f x . Например, задача (зн) сводится к задаче (зк) путем вве-
дения дополнительных координат x xn 1,..., xn m		:
	c, x max; Ax Ix b, x 0, x 0	,
где I	– единичная матрица размера m m.

Более подробно рассмотрим задачу линейного программирования в канонической форме. Множество допустимых точек задачи (зк) имеет вид:

Dз	x R	n	Ax b, x 0
к

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

R n .

Определение. Точка d

крайней (угловой), если не t 0;1 таких, что d t d1

выпуклого множества D называется

существует точек	d1, d2 D и числа
1 t d2 .	▲

У многогранников крайними точками являются вершины. Поэтому, если существует экстремум линейной функции, то он достигается в крайней точке выпуклого многогранника. Число

	59
крайних точек множества	D , задаваемого в виде конечного числа

линейных равенств и неравенств, конечно. Таким образом, для решения задачи линейного программирования (если оно существует) достаточно перебрать значение целевой функции f x c, x во всех крайних точках множества D . Но нахождение всех этих крайних точек и перебор значений целевой функции в них – операция довольно трудоемкая.

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

дить к другой по направлению наибольшего возрастания функ-
ции	f x c, x .
	Определение. Задача (зк) называется невырожденной, если
любая крайняя точка множества Dз					к	содержит ровно m положи-
тельных координат.								▲
	Пусть x x1, ... , xm ,0, ... ,0 , xi				0, i 1, ... , m – крайняя точ-
ка в невырожденной задаче (зк). Вектор x							можно представить в
виде	x xb , xn ,		где	xb x1, ... , xm			–	базисный вектор,
xn 0, ... ,0 R		n m	– небазисный вектор. Аналогично, матрицу
A можно представить в виде A Ab , An , где								Ab – матрица, со-

стоящая из первых m столбцов матрицы A.

Столбцы матрицы Ab линейно независимы, т.е. матрица Ab является невырожденной. Действительно, допустим противное, что столбцы a1, ... , am линейно зависимы. Тогда существует

ненулевой

Значит	A
точка	xt

набор множителей 1, ... , m

0	для вектора 1, ... , m
x t Dз		при малых t как
	к

			m	i
	такой, что	i a			0 .
		i 1
	,0, ... ,0 R	n	. Поэтому

больших нуля, так и

меньших нуля. Это означает, что точка x не является крайней.

Получили противоречие.

60

Правило решения задач по симплекс-методу

1) Привести задачу к канонической форме.

i

1,

2)Найти

... , m, x Dз

крайнюю точку

к	.

x x	, ... , x	,0, ... ,0 , x	0,
1	m	i

3) Построить симплексную таблицу для начальной крайней точки. В таблице m 4 строки и n 4 столбца. В первом столбце,

начиная с 3-его по

m 2 -ое место находятся базисные векторы

1	, ... , a	m	,	соответствующие положительным	координатам
a
начальной				крайней точки x x1, ... , xm ,0, ... ,0 .	Во втором

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

В первой строке, начиная с 4-го столбца, располагаются элементы c1, ... , cn .

		Во		второй
	1	, ... , a			n	. Под
b, a
1	, ... , a		m	.
a
		а)			Так

строке, начиная с 3-его столбца – векторы ними – разложения этих векторов по базису

как	x xb , xn x1, ... , xm ,0, ... ,0 Dз	к	, то

1

xma

m

b . Это

означает,

что

разложением

Ax b x1a

1

m

является вектор

xb .

вектора b по базису a , ... , a

б) Предположим,

что векторы a j j 1, ... , n

имеют следу-

ющее разложение по базису a1, ... , am :

a

a

a

1 j

11

1m

m

a2 j

a

21

a

2m

a j ai xij

x1 j

xmj a j Ab x j ,

i 1

...

...

...

amj

am1

amm