Пособие Методы оптимизации зоу

стемы (2.17) обращается в нуль, а остальные больше нуля, то величина t равна

минимальному положительному отношению х(i 0) / b(i

æ х(0) ö

t =min ç i ÷ > 0 .

ç b(0 )÷ è i ø

Новое пробное решение, таким образом, равно

é	(1)	(0)	(0)	(1)	=
ê	хi	= хi	-t bi	(i =1, 2,..., m), xm+1
ë

0) (i =1, 2,..., m), то есть

(2.20)

t,0,0,...,0ùúû (2.21)

Причем одна из первых m переменных равна нулю. Этому решения соответствует следующее значение линейного функционала (2.7):

z(1) =z(0) -Dz(1),

(2.22)

где Dz(1) определяется по (2.18).

Подытожим сказанное о симплексном методе. Он основывается на предварительном выборе базы и соответствующего ей исходного решения задачи. Исходное решение содержит m положительных переменных и n-m нулевых. Значения положительных переменных находятся путем решения балансовых уравнении.

Затем вводится m + 1-я переменная и проводится анализ приращения целевой функции. Если целевая функция уменьшается – новая программа лучше, увеличивается - хуже, равна нулю - одинакова.

В первом случае программа совершенствуется: в нее вводится новая переменная хm+1 и одновременно исключается переменная, для которой отношение

х(i 0) / b(i 0) минимальное положительное значение.

Новое улучшенное решение вновь пытаются усовершенствовать, вводя в

него последовательно m + 2-ю, m + 3-ю и т.д. переменные и повторяя описанные выше действия. После k = n-m повторений этих действий достигается оптимальная программа.

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

2.3. Примеры применения симплексного метода

Ниже приведено несколько простых числовых примеров применения алгоритма симплексного метода для решения задач программирования.

Задача 2.1. Найти оптимальную программу, соответствующую минимуму линейной целевой фикции

z =3х1 + 2х2 + х3 +4х4 ,

при выполнении следующих балансовых условий:

13

2х1 + х2 +3х3 + х4 =4; х1 + х2 +2х3 =3.

и обычных граничных условий (хi ³0).

Оптимальная программа содержит m=2 ненулевых переменных. Принимаем за исходное решение: х1 ¹0; х2 ¹0; х3 =0; х4 =0.

Из балансовых условий определяем переменные исходного решения:

2х1 + х2 =4;ü

ý

х1 + х2 =3, þ

то есть х1(0) =1; х(20) =2.

Исходному решению соответствует следующее значение целевой функции: z(0) =3 ×1+2 × 2 =7.

Попытаемся ввести в решение переменную х3 . Тогда балансовые условия примут вид:

2х1 + х2 +3х3 =4;ü

ý

х1 + х2 +2х3 =3.þ

Решение этой системы существует, если между столбцами коэффициентов системы имеется линейная зависимость, т.е. если существует ненулевое решение системы

2b1 + b2

=3;ü

ý

Решение этой системы: b(0)

=1; b(0)

b1 + b2 =2.þ

=1.

1

2

Определяем знак приращения целевой функции при введении в решение

переменной х3 :

si g n Dz =si g n êép3 -(p1b1(0 )+p2b(20 ))úù=

ë

û

si g n é1-(3 ×1+2 ×1)

ù =si g n (-4

)< 0.

ë

û

Введенная переменная х3

улучшает программу (уменьшает целевую функ-

цию). Определяем значение х3

(

0) ö

æ

х

æ

1

2

ö

(1 )

i

t =min ç

÷ = min ç

;

÷=1; х

=t =1.

(

ç

0 )÷

è

1 1

ø

3

è bi

ø

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

улучшенной программе:

х(1)

=х(0)

-t b(0) =1-1=0; х(1) =х(0) -t b(0) =2 -1=1;

1

1

1

2

2

2

х3(1 )=1; х(40 )=0; Dz(1 )= t êép3 -(p1b1(0 )+ p2b(20 ))úù=- 4;

ë

û

14

z(1) =z(0) + Dz =7 - 4 = 3.

Попытаемся ввести в решение переменную х4 :

х

+3х

+ х

=4;ü

b

+3b =1;

ü

b(21 )=- 2; b3(1 )=1.

2

3

4

ý

2

3

ý

х2 +2х3 + 0 =3;

þ

b2 +2b3 =0;þ

Определяем знак приращения целевой функции

si g n Dz =sig n êép4	-(p2b(21 )+p3b3(1 ))úù=1>0.
ë	û

Введение переменной х4 не улучшает программы. Таким образом, оптимальное решение имеет вид: х1 =0; х2 =1; х3 =1; х4 =0; zmin =3.

Задача 2.2. Целевая функция осталась та же, что и в задаче2.1, а балансовые условия немного изменились:

2х1 + х2 +3х3 + х4	=31; ü
х1 + х2 + 2х3	ý
	=20.þ

Найти оптимальную программу, соответствующую минимуму целевой функции. Принимаем за исходное решение: х1 ¹0; х2 ¹0; х3 =0; х4 =0.

Определяем параметры этого решения:

2х1 + х2 =31; ü

х(0)

=11;

х(0)

=9;

z(0)

=3 ×11+ 2 ×9 =51.

ý

1

2

х1 + х2 =20.þ

Попытаемся ввести в программу переменную х3 :

2х

+ х

+3х

=31;

ü

2b

+b

=3;ü

b1(0 )=1; b(20 )=1;

1

2

3

ý

1

2

ý

х1 + х2 +2х3 =20;þ

b1 +b2 =2;þ

g

3

=p b(0)

+p

2

b(0) =3 ×1 + 2 ×1=5; si g n Dz =si g n (р -g

3

)=si g n (-4 )< 0.

1

1

2

3

Переменная х3 улучшает программу. Определяем параметры улучшенного

решения:

(0)

æ

х

ö

æ

11

9 ö

(1 )

t =min ç

i

÷

= min ç

;

÷=1;

х

=t =9;

1

ç

(0 )÷

è

1 ø

3

è bi

ø

х1(1) =(х1(0) - tb1(0) )=(11-9 ×1)=2;

х(21) =0;

х(41) =0;

Dz(1) =t (р3 -g3 )=9(1-5)=- 36;

z(1) =z(0) + Dz(1) =51-36 =15.

Попытаемся ввести в программу переменную х4 :

2х

+3х

+ х

=31;ü

2b +3b

=1; ü

b1(1 )=2; b3(1 )=-1;

1

3

4

ý

1

3

ý

х1 + 2х3 + 0 =

20;þ

b1 +2b3 =0;þ

g

4

=p b(1)

+p b(1) =3 × 2 -1×1=5; si g n Dz =si g n (

р

4

-g

4

)=si g n (-1 ).

1

1

3

3

Переменная х4 также улучшает программу. Определяем параметры нового улучшенного решения:

15

æ

х

(1)

х

(1)

ö

æ

2

9

ö

(2 )

2

t =min ç

1

;

÷ >0;

t = min

ç

;

÷

>0; t =1;

х

=t =1;

b(1 )

ç b(1 )

÷

è

2

-1

ø

4

è

1

2

ø

х(2)

=0;

х(2)

=0;

х(2)

=х(1)

-t × b (1)

=9 -1×(-1

)=10;

Dz(2)

1

2

3

3

z(2)

3

= t (p4 -g4 )=1× 4(-5)=-1;

=z(1) + Dz(2) =15+(-1 )=14.

Все переменные исчерпаны. Оптимальная программа имеет вид:

х1 =0; х2 =0; х3 =10; х4 =1; zmin =14.

Задача 2.3. Она относится к случаю, когда балансовые условия даны в виде неравенств.

Найти оптимальную программу, соответствующую минимуму целевой функции

z =10x1 +17x2 +9x3 +24x4

при выполнении балансовых условий

5х1 + х2 +6х3 +11х4 ³14; 4х1 + х2 +5х3 +9х4 ³12

и обычных граничных условий (хi ³0).

Задачу линейного программирования с балансовыми условиями в виде неравенств всегда можно преобразовать в эквивалентную задачу с балансовыми условиями в виде равенств. Для этого введем вспомогательные переменные х5 ³0 и х6 ³0. Целевая функция и балансовые условия эквивалентной задачи можно записать в следующем виде:

z =10х1 +17х2 +9х3 +24х4 +0 × х5 +0 × х6;

5х1 + х2 +6х3 +11х4 + х5 +0 × х6 =14;ü

ý

4х1 + х2 +5х3 +9х4 +0 × х5 + х6 =12. þ

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

В оптимальной программе эквивалентной задачи содержится m = 2 ненулевых переменных. Принимаем за исходное решение

х1 ¹0; х2 ¹0; х3 = х4 =х5 = х6 =0 и определяем параметры этого решения:

5х	+ х		=14;ü	х1(0 )=2; х(20 )=4; z(0 )=10 × 2 +17 × 4 =88.
1		2	ý
4х1 + х2 =12;þ
Попытаемся ввести в программу переменную х3 :
5х1 + х2 +6х3				=14;ü	5b1 +b2 =6;ü	(0 )	=1;	(0 )	=1;
4х1 + х				ý	ý	b1		b2
			2 +5х3 =12;þ		4b1 + b2 =5; þ

16

g

3

=p b(0)

+p

2

b(0)

=10 ×1 +17 ×1=27;

si g n Dz =si g n (р

3

- g

3

)=

1

1

2

=sig n (9 - 27)=sig n (-18)<0.

Переменная х3

улучшает программу. Определяем параметры улучшенного

решения:

(0)

(0)

æ

х

х

ö

æ

2

4

ö

(1 )

(1 )

2

t =min ç

1

;

÷

= min ç

;

÷>0;

t =2; х

=0; х

=2;

ç b(0 )

b(0 ) ÷

è

1 1

ø

1

3

è

1

2

ø

х(21) =х(20) -t b(20) =4 -2 ×1=2; х(41) =х(51) = х(61) =0;

Dz(1) =t (p3 -g3 )=2 ×(9 -27)=- 36; z(1) =z(0) + Dz(1) =88+(-36)=52.

Попытаемся ввести в программу переменную х4 :
х2 +6х3 +11х4 =14;ü	b2 +6b3 =11;ü	(1 )	(1 )	=2;
ý	ý	b2	=-1; b3
х2 +5х3 + 9х4 =12;þ	b2 + 5b3 =9; þ

g4 =p2b(21) +p3b(31) =17 ×(-1 )+ 9 × 2 =1;

si g n Dz =si g n (р4 - g4 )=sig n (11-1)=sig n (10 )>0.

Переменная х4 ухудшает программу, и ее вводить нецелесообразно. Попытаемся ввести в программу переменную х5 :

х2	+6х3	+ х5	=14;ü		b2	+6b3	=1; ü	(2 )	(2 )	=1;
х2 +5х3 + 0 =12;				ý			ý	b2	=- 5; b3
				þ	b2 + 5b3 =0;þ

g

5

=p

2

b(2)

+p b(2)

=17 ×(-5

)+ 9 ×1=- 76;

2

3

3

si g n Dz =si g n (

р

5

- g

5

)=si g n é0 -

(-76)ù=si g n (76

)>0.

ë

û

Переменную х5 вводить также нецелесообразно. Попытаемся ввести в программу переменную х6 :

х2	+6х3 + 0			=14; ü			b2 +6b3 =0;ü	(3 )	(3 )	=-1;
х2					ý		ý	b2	=6; b3
	+5х3 + х6 =12;þ						b2 + 5b3 =1; þ
	g	6	=p	2	b(3) +p b(3) =17 × 6 + 9			×(-1 )=93;
					2	3	3

si g n Dz =si g n (р6 -g6 )= si g n (0 - 93)=si g n (-93)<0.

Переменная х6 улучшает программу. Определяем параметры улучшенного решения:

æ

х

(1)

х

(1)

ö

æ

2

2

ö

1

1

t =min ç

2

3

÷

;

= min ç

;

÷

>0;

t =

;

х6 =t =

;

(3 )

6

-1

3

3

ç

(3 ) ÷

è

ø

è b2

b3

ø

х(4 )=х(4 )= х(4 )			=х(4 )	= 0; х(4 )	=х(1 )	- t b(3 )	=2 -	1	×(-1 )=2	1	;
1	2	4	5	3	3	3	3			3

17

Dz(4 )= t (p6 -g6 )											=	1	×(0 -93)=- 31; z(4 )=z(1 )+ Dz(4 )=52 +(-31 =) 21.
											3
Переменные исчерпаны. Оптимальная программа эквивалентной задачи
равна: х =х		2	=х			4	=х	5	=0;					х		3	=2		1	;	х	6	=	1	;	z	min	=21.
1																		3					3
Оптимальная программа исходной задачи равна:
х =х	2	=х			4	=0;			х	3	=2				1	;	z	min			=21.
1														3
				1
Значение х6		=				из эквивалентной задачи показывает, на какую величину не ис-
			3

черпан лимит во втором балансовом условии исходной задачи. Значение правой

части второго балансового условия в точке оптимальной программы равно12 1 , а 3

лимит - 12.

3. Нелинейное программирование

Нелинейное программирование является наиболее общей и наиболее сложной по методам решения задач математического программирования. Как всякую задачу математического программирования, задачу нелинейного программирования можно сформулировать в виде целевой функции(1.1), балансовых условий (1.2) и граничных условий (1.3). Отличительная черта нелинейного программирования – то, что либо целевая функцияZ , либо балансовые условия Fj (х1, х2 ,..., хn ) являются нелинейными. При этом в зависимости от того являют-

ся ли Z и Fj непрерывными и дифференцируемыми, переменные хi принимают

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

Методы нелинейного программирования можно разделить на две группы: аналитические и шаговые. К первому типу относятся, например, метод неопределенных множителей Лагранжа и метод квадратичного программирования. Условный минимум целевой функции здесь определяется путем решения в общем случае системы нелинейных уравнений. В шаговых методах оптимизации процесс поиска минимума организован таким образом, что на каждом этапе поиска опре-

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

3.1. Геометрическая интерпретация задачи

При числе переменных n = 2 и n = 3 задачи нелинейного программирования можно решить геометрическим методом. Несмотря на ограниченную возмож-

18

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

В качестве примера рассмотрим задачу: определить оптимальные программы, соответствующие максимуму и минимуму целевой функции

z = x2 + y2	(3.1)
при наличии балансового условия
x2 + y2 -16х -8у +60 £ 0	(3.2)

и обычных граничных условий (x ³0, y ³0).

Уравнение, соответствующее равенству в балансовом условии(3.2), можно преобразовать к виду:

(х -8)2 + (у -4)2 =20, (3.3)

из которого следует, что оно в плоскости (х, у) соответствует окружности с цен-

тром в точке с координатами (х =8, у =4) и радиусом R1 =20 . Поэтому область

допустимых решений, определяемая балансовым (3.2) и граничными условиями, соответствует точкам усеченного круга (заштрихованная область на рис.3.1). При фиксированной степени достижения цели Z =Z0 целевая функция (3.1) в плоско-

сти (х, у) также является уравнением окружности с центром в начале координат и радиусом R 2 =Z0 . Различным степеням достижения цели соответствует се-

мейство целевых линий, являющихся концентрическими окружностями с центром в начале координат, причем увеличение значения целевой функции приводит к возрастанию радиуса соответствующей изоцелевой окружности (рис.3.1).

Как следует из взаимного расположения области допустимых решений и семейства изоцелевых линий на плоскости (х, у) (рис.3.1), существует такое ми-

нимальное значение целевой функции, при котором соответствующая изоцелевая линия имеет лишь одну точку пересечения с областью допустимых решений. Это значение целевой функции Z = 20, а соответствующая точка пересечения с областью допустимых решений (точка А) лежит на прямой, соединяющей центр изоцелевых окружностей с центром окружности, ограничивающей область допустимых решений. Координаты точки А (х =4, у =2) и значение целевой функцииZ = 20

являются оптимальной программой задачи(3.1), (3.2), которая соответствует минимальному значению целевой функции.

Существует также такое максимальное значение целевой функции(Z = 180, на рис.3.1), при котором соответствующая изоцелевая линия имеет лишь одну точку пересечения с областью допустимых решений(точка В). Координаты этой точки (х =12, у =8) и значение целевой функции(Z = 180) являются оптимальной

программой, соответствующей максимальному значению целевой функции в за-

даче (3.1), (3.2).

19

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

14	у
13
12
11						Z = 180
10
9				Z = 121
8
7		Z = 64
6													В
5
4	Z = 20
3
	Z = 9			А
2
1														х
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

Рис.3.1. Геометрическая интерпретация нелинейного программирования

3.2. Метод Лагранжа

Метод Лагранжа - один из возможных аналитических методов решения, задач нелинейного программирования, отличающийся простотой и наглядностью. Использование метода Лагранжа рассмотрим на примере общей задачи нелинейного программирования, но вначале примем, что балансовые условия заданы в виде равенств. Пусть требуется найти оптимальную программу, соответствующую минимуму целевой функции от n переменных

Z =F(х1, х2 ,..., хn )

(3.4)

в области допустимых решений, определяемой m балансовыми условиями

Fj (х1, х2,..., хn )=Сj ( j =1, 2,..., m)	(3.5)
и обычными граничными условиями
хi ³0, (i =1, 2,..., n ).	(3.6)

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

20

Из целевой функции (3.4) и балансовых условий (3.5) составим вспомогательную функцию, называемую функцией Лагранжа:

L (х1, х2 ,..., хn ; l1, l2 ,..., lm )=F(х1, х2 ,..., хn )-

m	ù	(3.7)
é
-å lj ëФ j (х1, х2,..., хm )-Cj û.
j=1
Функция Лагранжа есть функция	переменныхх1, х2,..., хn и множителей

l1, l2,..., lm . Первое слагаемое правой части есть целевая функция, минимум которой необходимо определить, а второе - взвешенная сумма балансовых условий. Весами этой суммы являются множители l1, l2,..., lm называемые неопределенными множителями Лагранжа.

Функция Лагранжа (3.7) обладает следующим замечательным свойством, имеющим практическое значение: если точка с координатами (х1, х2 ,..., хn ) находится в области допустимых решений, то выражение, стоящее под знаком суммы в формуле (3.7), в соответствии с (3.5) равно нулю. Тогда L =F(х1, х2,..., хn ) , сле-

довательно, в области допустимых решений функция Лагранжа имеет те же значения, что и целевая функцияZ. Из этого вытекает, что задача на определение условного экстремума функции(3.4) может быть заменена задачей отыскания обычного экстремума функции Лагранжа (3.7) от n +m переменных.

Необходимое условие существования экстремального значения функции Лагранжа - равенство нулю ее частных производных:

dL	=0 (i =1, 2,..., n ),	dL	=0 ( j =1, 2,..., m),	(3.8)
dxi		dlj

которые в соответствии с(3.7) могут быть преобразованы в следующие выражения:

dF

m

dФ

ü

=å lj

(i =1, 2,...,n ),

ï

dxi

dxi

(3.9)

j=1

ý

Ф

j

(х , х

2

,..., х

m

)-C

j

=0

( j =1, 2,...,m).ï

1

þ

Система (n +m) уравнений (3.9) относительно (n +m) неизвестных опреде-

ляет значения переменных (х1, х2 ,..., хn ) и значения неопределенных множителей Лагранжа l1, l2,..., lm , при которых функция Лагранжа(3.7) имеет экстремум. Поскольку найденные таким образом значения переменных(х1, х2 ,..., хn ) всегда находятся в области допустимых решений, ввиду выполнения балансовых условий, которыми являются последние (m) уравнения системы (3.9), то при этих

значениях будет иметь место и экстремум целевой функции задачи (3.4), (3.5). Условия (3.8) или эквивалентные им (3.9) являются лишь необходимыми

условиями существования экстремума функции (3.7). Для проверки достаточного условия необходимо вычислить дифференциал второго порядка от функции -Ла гранжа:

21

n n

é

d2F

m

d2Ф j

ù

d2L =å å

ê

-å lj

ú dxi dxk .

(3.10)

dx

dx

dx

i=1 k =1

êdx

i

k

j=1

i

ú

ë

k û

Достаточное условие существования минимума целевой функции задачи (3.4)-(3.5) состоит в том, чтобы дифференциал второго порядка функции Лагранжа (3.10) для значений переменных хi и значений неопределенных множителей

Лагранжа, найденных из уравнений (3.9), был положительным (d2L >0) для всех

значений dxi и dxk . Аналогично достаточным условием существования макси-

мума целевой функции задачи (3.4)-(3.5) является условие (d2L <0) для всех зна-

чений dxi и dxk .

Задача 3.1 Определить оптимальную программу, соответствующую минимуму целе-

вой функции

Z =х2	+ х2					+ х			2	+ х		2	,	(3.11)
1				2					3			4
при выполнении балансового условия								-С4
Ф =х х		2	х	3	х		4				=0			(3.12)
1

и обычных граничных условий (хi ³0, i =1, 2,3, 4). Функция Лагранжа задачи (3.11)-(3.12) имеет вид:

L =х12 + х22 + х32 + х42 -l(х1х2х3х4 -С4 ).

(3.13)

Необходимые условия существования экстремума функции Лагранжа в со-

ответствии с (3.9) можно выразить в виде системы уравнений:

2х -lх

2

х

3

х

4

=0, ü

1

ï

2х2 -lх1х3х4

=0, ï

2х3 -lх1х2х4 =0,

ï

(3.14)

ý

2х

4

-lх х

2

х

3

=0,

ï

1

ï

х х

х

3

х

4

-С4

=0,

ï

1

2

þ

из которой следует оптимальная программа задачи

х0	=х	0	=х0	=х	0	=С, l=	2	,	Z0	=4С2 .	(3.15)
1		2	3		4		С2		мин

Проверим достаточные условия существования минимума целевой функции в найденной точке решения, дифференциал второго порядка функции Лагранжа в соответствии с выражением (3.10) в точке экстремума равен:

d2L =2(х12 + х22 + х32 +х42 )-2(dx1dx2 +dx1dx3 +

(3.16)

+dx1dx4 +dx2dx3 +dx2dx4 +dx3dx4 ).

22