MMP_5

Перв. пр	А2	B1		А4
			B2				А2
Посмотрим прямую L: 3x1 4x2		12 (см. рис.2).				B1	B2
			А1		А3		А1
	x2
№
Справ.	3		L
	0			4	x1

	.	дата	Рис. 2
			1<2 < 3 
	защищены	Под
	Для того чтобы определить,		какая полуплоскость удовлетворяет
		и.п

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

L, и подставить ее координаты

в

неравенство. Если

неравенство

будет

F

=

права

1



Все ду№бл.

2

выполняться,

то

данная точка

является

допустимым

решением,Fи

=



полуплоскость, содержащая точку, удовлетворяет неравенству. Как правило,

. .

Россия

№

Инв



в качестве «пробной» берут точку O 0; 0 .



Подставимни.мАСКОН.,

x2

0 в заданное неравенство:

3 0 4 0 12. Получим

ЗАО

x1

Вза

истинное утверждение. Следовательно, заданному неравенству соответствует

нижняя

полуплоскость

(заштрихованная на

рис.

2),

содержащая

точку

O 0; 0 .

-2007

дата

)с1989 ПолуплоскостиодП . и

,

описываемые

неравенствами

(19)

– выпуклые

(

Изм. Лист

№докум.

Подп. Дата

множества. LTИх пересечение – область допустимых Ррешенийаз ЗЛП, которая

одл.

аб.

-3D

Пров.

является также выпуклым множеством.

Т.контр.

КОМПАС

п

Инв

Утв.

№.

Это множество называют также многоугольником решений. Он может

Н.контр.

быть точкой, отрезком, лучом, ограниченным или неограниченным

КОМПАС-3D LT V9 (некоммерческая версия)

многоугольником. (Случай вырождения, когда система ограничений (19) –

пустое множество и ЗЛП не имеет решения, исключается).

20

Ввиду неравенств x1 0 и x2 0 многоугольник решений всегда находится в первом квадранте координатной плоскости Ox1x2 .

Для нахождения экстремума целевой функции F воспользуемся вектором набла - градиентом F:

		F		F			c1, c2 .
	grad F		,
		x		x
					2
		1

Он показывает направление наискорейшего изменения целевой

функции F.
Прямая c1x1 c2 x2	называется линией уровня функции F.	Иными
словами на множестве	всех точек x1, x2 линии уровня функции	F она

сохраняет постоянное значение .

Алгоритм решения ЗЛП геометрическим методом.

1.Строится многоугольник решений.

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

3.Первая точка встречи линии уровня с многоугольником решений определяет минимум целевой функции.

4.Последняя точка встречи линии уровня с многоугольником решений определяет максимум целевой функции.

5.Если линия уровня параллельна одной из сторон многоугольника решений, то экстремум достигается во всех точках этой стороны A2 A3 . ЗЛП в

этом случае имеет бесконечное множество решений.

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

21

Пример 1. Экономико-математическая модель задачи о планировании

производства.

x1

Построим многоугольник решений. С этой целью запишем уравнения

границ полуплоскостей из (17) в виде

x1

x2 1

L

x1 x2 42

42 42

1

2x2 48

x

x

1

L2

x1

или

1

2

x

4x

2

72

48

24

1

x1

x2 1

L

72

18

3

«Пробная» точка

O 0; 0

удовлетворяет всем неравенствам из (17) и

потому многоугольник решений OA1 A2 A3 A4

расположен в нижних

полуплоскостях, порожденных прямыми L1 ,

L2

и L3 как показано на рис. 3

Построим вектор набла 25, 34 . Последней точкой встречи линии



x2

A1

уровня

с

многоугольником

решений

будет

точка

A

(см.

рис.3)

с

3

9

A2

координатами: x1 36,

x2 6, являющимися решениями системы уравнений

x1 x2 42

L1

L2

x

2x

2

48

L

1

2

Подставив координаты точки A3

в целевую функцию, найдем

L1

Fmax

25 36 34 6 1104

2

1

L3

A3

x2

0

3

42

L1





24

L2





18 A1



A2

A3

L3

0

A4

x1

42 48

72

Рис. 3

22

Пример 2. Экономико-математическая модель задачи о диете.

Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей из (17) в виде

x1

x2

1

L

x1 3x2 6

1

6

2

3x

x

9

или

x1

x2

1

L

2

1

2

x

8x

2

8

3

9

1

x1

x2

1

L

3

8

1

O 0; 0

«Пробная» точка

удовлетворяет всем неравенствам из (17) и

потому многоугольник

решений A1 A2 A3 A4 A5 A6

расположен в

верхних

полуплоскостях, порожденных прямыми L1 , L2 и L3

как показано на рис. 4

Построим

вектор

набла

8,16 .

Первой

точкой

встречи линии

уровня с многоугольником решений будет точка

A3

(см. рис. 4) с

координатами:

x1 2,625 ,

x2 1,125 ,

являющимися решениями

системы

уравнений:

		x1 3x2 6					L1
		3x		x	2	9	L
			1				2
	Подставив координаты точки A3					в целевую функцию, найдем
		fmin 8 2,625 16 1,125 39
	x2					
		A1				
							
	9	A2					
								
		L2
	2	L1
	1	L3	A3
							A4	A5	A6
	0
			3				6	8	x1
						Рис. 4

					23

A3	L3
	A4

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

С увеличением числа неизвестных геометрический метод решения ЗЛП становится затруднительным при трех переменных и невозможным при большем числе переменных.

Поэтому был разработан универсальный метод решения ЗЛП –

симплекс-метод, позволяющий решать ЗЛП в канонической форме.

Изложим суть симплекс-метода на примере задач с 5 неизвестными.

Пусть ЗЛП приведена к виду

F c0 c1x1 c2 x2						max		(20)
при ограничениях:
x3 p p1x1 p2 x2
		0
x4		q	q1x1 q2 x2 ,					(21)
x		0
		r	r x		r x		2
	5	0	1	1	2

где p0 0, q0 0, r0 0 ,

x1 0, x2 0, x3 0, x4 0, x5 0

(22)

Про систему ограничений (21) говорят, что она имеет допустимый вид,

если одни неизвестные ( x3 , x4 , x5 ) выражаются через остальные ( x1, x2 ),

причем	свободные	члены		этих	выражений	неотрицательны
( p0 0, q0 0, r0 0 ).
Неизвестные x3 , x4		и x5	называются базисными, а неизвестные x1, x2 –
свободными.
Возможны два принципиальных случая:
1 Все коэффициенты при свободных неизвестных в выражении для F
неположительны: c1 0		и	c2 0 .	Тогда	для всякого	неотрицательного

решения системы уравнений (21) имеем c1x1 0 и c2 x2 0 , а потому

24

F c0 c1x1 c2 x2 c0	или max F c0 .
Следовательно, базисное решение	x1 0, x2 0, x3 p0 , x4 q0 , x5 r0

является оптимальными, т. е. задача решена.

2 Имеется свободное неизвестное, коэффициент при котором в выражении для F положителен, а все коэффициенты при этом неизвестном в

уравнениях (21) – неотрицательны.

Для определенности положим c1 0, p1 0, q1 0, r1 0. Исходя из базисного решения, станем наращивать значение x1 , не меняя x2 0 . Тогда значения базисных неизвестных будут оставаться неотрицательными:

x3 p0 p1x1 p0 0 x4 q0 q1x1 q0 0 , x5 r0 r1x1 r0 0

а значение F c0 c1x1 будет неограниченно возрастать, т.е. max F и задача решения не имеет.

Решения ЗЛП редуцируются к одному из случаев 1 или 2 путем перехода к новому базису, в котором целевая функция не уменьшит своего значения для базисного решения, а новая система ограничений должна иметь допустимый вид. Преобразование базиса и перестройку целевой функции и системы ограничений называют шагом в решении ЗЛП. Таким образом,

сделав нужное число шагов, решают ЗЛП (20) – (22).

Применим симплекс-метод к первой задаче.

I. Основная задача в примере 1 имеет вид

F 25x1 34x2 max

25

x1	x2 42
x1	2x2		48
x	4x		72
1		2
	0,		x2 0
x1

Сначала приведем ее неизвестные x3 0 , x4 0 и x5

x1x1x1

к каноническому виду, вводя балансовые

0 :

x2 x3 42

2x2	x4	48	(23)
4x2	x5	72

xi 0,	i 1, 5	(24)
Теперь приведем (23) к допустимому виду – неизвестные x3 ,			x4 и x5
выразим через x1 и x2 , при этом свободные		члены в правых	частях
полученных уравнений неотрицательны:

x3x4x5

42 x1	x2
48 x1	2x2	(25)
72 x1	4x2

Здесь x3 , x4 и x5 – базисные неизвестные, а x1

и x2 – свободные

неизвестные.

Шаг 1: положим в (25) x1 0

и x2 0, тогда x3 42 ,

x4 48, x5 72 .

Получим неотрицательное решение 0, 0, 42, 48, 72

системы уравнений (25).

Его называют базисным решением. Для него F 0.

Шаг 2: положим в (25) x2 0, а x1

начнем наращивать так, чтобы x3 ,

x4 и x5 оставались неотрицательными, т. е.

x3 42 x1 0,

x4 48 x1 0,

x5 72 x1 0 .

Решая

эти

неравенства,

найдем

наименьшее

значение

x1 min 42; 48; 72 42 . Тогда x3

0 .

Объявив

x2

и

x3

свободными

неизвестными, приведем (25) к допустимому виду:

26

x	42 x		x
1		2			3
x4	6 x2 x3				(26)
x	30 3x		2	x
5					3

Получим неотрицательное решение 42, 0, 0, 6, 30 системы уравнений (26). Для него

F 25x1 34x2 25 42 x2 x3 34x2 1050 9x2 25x3 (27)

примет значение F 1050 .

Сделаем выводы.

Во-первых, значение F по сравнению с 1-ым шагом увеличилось.

Во-вторых, в (27) коэффициент при x3 отрицательный и для дальнейшего увеличения значения F надо положить x3 0 и наращивать x2 .

Шаг 3: положим в (26) x3 0 ,

а x2 начнем наращивать так, чтобы x1 ,

x4 и x5 оставались неотрицательными, т. е.

x1 42 x2 0,

x4 6 x2 0,

x5 30 3x2 0 .

30

Откуда находим наименьшее значение x2 min

42; 6;

6 .

Тогда

3

x4 0. Объявив

x3

и x4

свободными неизвестными, приведем

(27) к

допустимому виду:

x

36 2x

x

4

1

3

x2

6 x3 x4

(28)

x

12 2x

3x

4

5

3

Получили неотрицательное решение 36, 6, 0, 0,12

системы уравнений

(28). Для него

F 1050 9 6 x3 x4 25x3

1104 16x3 9x4

(29)

примет значение F 1104 .

Сделаем выводы.

27

Во-первых, значение F по сравнению со 2-ым шагом увеличилось.

Во-вторых, в (29) оба коэффициента при свободных неизвестных отрицательны и дальнейшее увеличение значения F невозможно:

Fmax 1104

при x3 x4 0 . Задача решена. Учитывая экономический смысл неизвестных, приходим к выводу: предприятие получит наибольшую

прибыль 1104 единиц при изготовлении 36 единиц товара T1 и 6 единиц товара T2 , при этом остатки ресурсов S1 и S2 равны нулю ( x3 x4 0 ), а

остаток ресурса S3 равен 12 единицам.

Если решается ЗЛП, в которой требуется найти минимум целевой

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

принципиальных случаев:

1 Все коэффициенты при свободных неизвестных в выражении для F

неотрицательны:	c1 0	и	c2 0 .	Тогда	базисное	решение
x1 0, x2 0, x3 p0 , x4 q0 , x5 r0			является решением задачи.
2 Имеется	свободное	неизвестное,		коэффициент при		котором в

выражении для F (20) отрицателен, а все коэффициенты при этом неизвестном в уравнениях (21) – неотрицательны. Тогда задача решения не имеет.

Применим симплекс-метод ко второй задаче, Основная задача в

примере 2 имеет вид

f 8x1 16x2 min

x1 3x2 6
		9
3x1 x2
	8x2	8
x1
x	0,	x	2	0
1

28

Сначала приведем ее к каноническому виду, вводя балансовые неизвестные x3 0 , x4 0 и x5 0 :

x	3x		x	6
1		2	3
3x1 x2			x4	9		(30)
x	8x	2	x	8
1			5
	xi 0,		i 1, 5			(31)

Приведем ограничения (30) к допустимому виду. Как показано выше, в

качестве базисных неизвестных следует выбирать такие неизвестные, каждая из которых входит только в одно из уравнений системы ограничений (31),

при этом нет таких уравнений системы, в которые не входит ни одна из этих неизвестных, и каждая базисная неизвестная имеет тот же знак, что и свободный член.

Нетрудно видеть, что x3 , x4 и x5 не могут быть базисными неизвестными. Действительно,

x3x4x5

6 x1	3x2
9 3x1 x2		(32)
8 x1	8x2

и знаки x3 , x4	и x5	противоположны знакам свободных членов.
Для выделения базисных неизвестных из системы ограничений (30)
необходима ее перестройка.
Полагая в	(32)			x1 0 (или		x2 0) найдем из условий
неотрицательности x3 , x4			и x5 :
x3 6 3x2 0,		x4 9 x2 0,				x5 8 8x2 0 .

наибольшее значение x2 max 2; 9;1 9 . Тогда x4 0 и систему (32)

запишем в виде

29