Исследование операций и методы оптимизации

исходит

запоминание

значений

аргументов в

качестве

текущего решения,

= .

min

Пример 5.8 ·······················

·······················

Рассмотрим пример решения задачи о диете (см. гл. 3) методом Монте-

Карло.

В таблице 5.3 представлены сведения о продуктах и о содержании в них

минералов: фосфора и калия.

Таблица 5.3 – Информация о продуктах

Содержание

Содержание

Минерал

в 1 курином яйце, мг

в 1 яблоке, мг

Фосфор

96

16,5

Калий

70

412,5

Суточная потребность человека в фо форе

составляет 2 000 мг,

в калии –

2 500 мг. Стоимость одного куриного яйца

составляет 4,5 руб. яблока – 20 руб.

Таким образом, модель имеет вид (

– количество

яиц,

– количество

яблок). Ограничения:

x

x ≥

+

≥

+

x

1

2

≥

x ≥

x

Целевая функция:

1

x +

2

x →

f (x

x ) =

1

2

На рисунке 5.20 представлено решение данной задачи, полученное в Ex

1

2

1

2

могут при

cel помощью надстройки «Поиск решения», без учета того, что

имать только

ое значение. Для удовлетворения суточной потреб

ности в фосфорецелочисленкалии нужно

съедать в день 20,386 яблок и 2,6 яиц. Стои-

мость набора составит 143,76 руб.

Если мы

полученные значения в большую сторону, то получим:

21 куриное яйцоокруглим3 яблока. Стоимость набора составит:

+

=

.

Данное решение не является оптимальным.

172

							Рис.		расчета
		Теперь для получения решения будем использовать метод Монте-Карло.
		макрос, который будет							случайны вел чины количества
яицНапишемяблок, проверять ограничениегенерироватьнаходить решение с минимальной стои-
мостью. Пусть максимальное число яиц равно 36, яблок – 120. Т гда величины
x , x		будут	генерироваться					из	интервалов (0;36) и	(0;120) соответственно.
Текст макроса:
1	2	Sub CalcLinear()
		fmin
		For i = 100000To 10000000
		1					36)
		x2 = Round(Rnd()					1 0)
		((96 *			+ 16.5 * x2)			>= 2000) And ((70 * x1 + 412.5 * x2) >= 2500) Then
		= 4.5 * x1			+ 20 * x2
		If (f <			Then
		fmin =fmin)
		1		1
		x2min = x2
		End If	B			1
		Next
				8") = x2min					16.5 * x2min
				0		96
				11") = 70			* x1min + 412.5 * x2min
		Range("C9")				= fmin
		End Sub				решение		представлено на		5.21. Таким образом,
		Полученное
в день нужно съедать 24									яйца и 2 яблока.рисункеПр этом потребление фос-
фора		калия составит 2куриных337 2 505 мг соответственно, что удовлетворяет
ограничениям. Стоимость набора составит 148 руб.

	Рис. 5.21 – Решение	программирования
·······································································
	·····························································
	Контрольные вопросы по главе 5
1.	·····························································
	Какие задачи называются задачами целочисленного программирова-
2.	ния?
	Какие существуют методы решения задачи целочисленного програм-
3.	мирования?
	Каким образом задача целочисленного программирования решается
4	графически?
	В чем суть метода Гомори?
5	Опишите алгоритм метода Гомори.
6	В чем суть метода ветвей и	ветвейграниц? границ.
7	Опишите алгоритм
8	Сформулируйте задачуметоданазначениях.
9.	задачи о коммивояжере?

10. В чем суть метода Монте-Карло?

6 Нелинейное

.

Задачи с ограничениямипрограммированиевиде равенств

Рассмотрим общую задачу оптимизации с ограничениями – равенства-

ми [1]:

(

) →

(6.1)

Функции

и

i

(

)

=

=

(6.2)

( )

i ( )

предполагаются непрерывными и дифференциру-

емыми.

6.1 Метод замены переменных

может быть решена как задача

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

безу ловной оптимизации, путем исключения

из целевой функции (6.1)

не

переменных

помощью заданных равенств (6.2). Наличие ограни-

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

задачи

до

(

−

)

. Для решения задачи безусловной минимизации можно

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

·······················

·······················

f

x

= x2

Пример 6.1

Решить задачу:

(

)

+ x

→

Решение:

=1

x

− x

=

+

подставим1

в

2

f

(

x

)

=

(

+ x

2(+)x →

2 )

2

f

′

(

x

)

=

(

+ x

+ x = x = x = −

2 )

2

1

2

····················································· ··················

Пусть имеется

ограничений равенств, причем

< .

=

, то -

дача оптимизации сводится к решению системы уравнений (6.2)Еслиоптимизация здесь не нужна.

Таким

экстремальная точка функции

(

)

ищется лишь по тем

образом,которые удовлетворяют независимой системе (6.2) при

<

,

значениямт. . в некоторой части

пространства

(

).

Пусть первые

…

, относительно которых мы хотим

разрешить систему (6.2),переменныхт. . вектор

1 можно представить в виде:

Решаем систему (6.2):

x

y

x

u

y = Ψ

(u)

u R

−

m+1

≡

1

x =

y

y =

1 ≡

1

u =

xm

ym

xn

un−m

u

и подставляем

в целевую функцию

=

=

Ψ

. Получим

функцию

( −

) переменных

1,…,

−

, на которую не наложено никаких

ограничений, . . получим задачу оп имизации без

граничений.

Для идентификации точки экстремума целевой функции можно исполь-

зовать один из известных методов.

( )

(

)

(

( )

)

Метод замены переменных (МЗП) применим лишь в случаях, когда урав-

ения ограничения можно разрешить относительно некоторого конкретного

набора незави имых переменных. При наличии большого

числа ограничений

МЗП становится весьма трудоемкой процедурой. Кроме того, возможны ситуа

ции, когда уравнение не удается разрешить относительно переменной, напри-

мер:

2

2 +

−1

(

) =

+

В этом случае целесообразно использовать метод множителей Лагранжа.

6.2 Метод множителей Лагранжа

необ-

С помощью метода множителей Лагранжа (ММЛ) устанавл

ход ое

позволяющее идентифицировать точки

иваютзадаче

условие,ограничениями – равенствами. При этом задачаэкстремумаограничения-

оптимизациипреобразуется в эквивалентную задачу безуслов

й оптимизации, в которой

фигурируют некоторые неизвестные параметры –

множители Лагранжа [1].

Рассмотрим задачу оптимизации:

f (x

… x

) →

h(x … x ) =

1

1

n

n

В соответствии с ММЛ эта задача преобразуется в задачу оптимизации

без ограничений.

L(x

λ) = f (x) + λh

(x) →

– множитель Лагранжа,

Функция

(

λ)

– функция Лагра жа. λ =

на знак которого н

каких требований не накладывается.

1

Проиллюстрируем ММЛ на конкретном примере.

·······················

Пример 6.2

·······················

Решить задачу:

h(x)

x + x −

=

=

Соответствующая задача оптимизации без ограничений записывается

1

2

+

в следующем виде:

( ) =

L(x λ) = x2

+ x + λ(

x + x

− ) →

Решение:

x

1

2

1

2

1

1

∂

1

= x + λ = → x*

= −λ

∂L

∂L

*

λ

∂x

=

x2 + λ = → x2

= −

ми-

Для того чтобы провер2ить, соответствует ли стационарная точка

нимуму,

вычислим матрицу

Гессе

функции

(

λ), рассматриваемой

как

функция

:

HL

(x λ) =

которая оказывается положительно определенной.

Это означает, что

( λ) – выпуклая функция .

Следовательно, координаты

x

= −λ,−

определяют точку глобального

минимума. Оптимальное значение λ

находится путем подстановки значений

и в уравнение ограничений

x

*

=

λ

+ x

−

, откуда:

1

2

λ + λ = − → λ* = −

Таким

образом,

минимум

достигается

при

x* =

и x* =

и

f * = min f

x

.

1

2

(

)

=

x

x λ

является седловой точкой функции Лагранжа

λ),

еслиλ.

Точка

(

)

(

1

2

функцию

Лагранжа рассматривать как функцию трех переменных

·······································································

ММЛ можно распространить на

лучай, когда задача оптимизации имеет

несколько ограничений – равенств.

Рассмотрим

общую задачу:

f (x

… x

)→

i

1

1

n

n

(

…

) =

=

Функция Лагранжа принимает следующий вид:

где λ … λ

– множит

(

λ) = ( )+ m

λ

i

i

( )

∑

i=1

Лагранжа, т. е. неизвестные параметры, значения ко-

торых1 необходимо определить.

Далее находят частные производные:

∂L

∂L

и рассматривают систему (

∂x

=

=

) неизвестными x

λ :

j

∂λ

i

+

)

уравнений с (

+

∂L

∂f

x

m

∂h

x

(

(

)

j =

n → xL =

=

) +

∑λi

i

=

∂xj

∂xj

∂xj

i=1

∂L

= h (x

,…,x

) = 0 i =1,m →

L = 0.

λ

∂λ

i

1

n

Это

бходимое условие экстремума функции Лагранжа.

есть

неоi

ции

Решение

расширенной системы определяет

точку функ

. Затем реализуется процедура проверки на минимумстационарнуюли максимум, ко-

торая проводится на основе вычисления элементов матрицы Гессе функции

,

рассматриваемой как функция .

) уравнений с ( +

Для некоторых задач расширенная система ( +

)

накоеизвестными может не иметь решений, и ММЛ окажется неприемлемым. Одна практике такие задачи встречаются редко.

	178
6.3 Решение обратной задачи с помощью
метода множителей Лагранжа		двух
Рассмотрим случай мультипликативн й зависимости для

аргументов (рис. 6.1): выручка (r) равна произведению цены ( p)функцииколичества
товара (c):	r = p c.

		Рис.					показателей
цены	Исходные данные: r = 50, p =10, c = 5. Необходимо определить значения
	количества (наиболее близкие к исходным), которые обеспечат величи-
ну выручки, равную 100.
	Определение приращений аргументов можно представить в виде задачи
нелинейного программирования с квадратичной целевой функцией:
			f	(∆x) = ∆x2		+ ∆x → min;
		(x			1		2
				+ ∆x )(x + ∆x			) = y + ∆y.
	Для случая определения цены и количества необходимо найти решение
задачи:			1	1	2	2
				∆p2 + ∆c2 → min;
			(10 + ∆p)(5			+ ∆c) =100.
	В соответствии с методом множителей Лагранжа задача преобразуется
в задачу оптимизации без ограничений:
где		L	(x,λ) = f (x)− λh(x)→ min,
	L(x,λ) – функция Лагранжа;
	λ = const	– множитель Лагранжа, на знак которого никаких требований не
накладывается.
	Запишем задачу в виде задачи оптимизации без ограничений:
		∆p2 + ∆c2	− λ (10		+ ∆p)(5 + ∆c)−100 → min.

Частные производные: ∂L

∂∆p

= ∆

− λ(

+ ∆

)

Для получения окончательного решения необходимо решить систему

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

− λ(

+ ∆ )

∂L

= ∆

∂∆

− λ(5 + ∆c) = 0;

∆p

Получим: λ =

2∆c

− λ 10

+ ∆p

)

= 0;

∆

=

∆

=

(

(

+ ∆p)(

+ ∆c)

−

=

·······················

Пример 6.3

·······················

Решим также задачу

∆p2 + ∆c2

→

с помощью метода замены переменных

−

(

∆p =

100

+ ∆p)(

+ ∆c) =

Задача заключается

100

+ ∆ 2

2

нахождении минимума одномерной функции. Ис-

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

принадлежит интервалу

f

(∆c) =

5

+ ∆c

−

+ ∆c

→

от 0 до 5 (шаг равен 0,1). Результаты представлены в таблице 6.1.

Таблица 6.1 – Решение задачи с помощью равномерного поиска

5

0

0,1

…

3,1

3,2

3,3

…

4,9

∆

100

92,321

15,112

15,059

15,085

24,02

25

(

)

значение функции д

остигается

при

.

Отсюда

Наименьшее

∆

=

∆

∆p =

100

−

=

·······································································+ ∆

	·····························································
	Контрольные вопросы по главе 6
1	·····························································
	й вид имеет задача нелинейного программирования?
2	ое требование предъявляется к целевой функции?
3.	Какие существуют методы решения задачи нелинейного программи-
4	рования?	замены переменных?
5	В чем суть метода множ телей Лагранжа?
6	формируется функция Лагранжа?
7	ие параметры являются неизвестными в функции Лагранжа?
8		седловая точка функции Лагранжа?
9.	Как определяется минимум функции Лагранжа?
10.	Назовите необходимое условие экстремума функции Лагранжа.