13.2 Поиск минимума функции многих переменных

При нахождении минимума функции многих переменных функцию costf необходимо

построить таким образом, чтобы входными данными в нее были значения вектора

неизвестных x и параметра ind. Функция costf должна зависеть не от нескольких

неизвестных, а от одного массива (вектора) неизвестных.

В случае функции многих переменных структура функции сostf должна быть такой

function [f,g,ind]=costf(x,ind)

//f - функция от вектора неизвестных х, минимум которой ищется

f=gg(x);

// g - градиент функции f (вектор частной производной),

g=numdiff(gg,x);

endfunction

В качестве примера рассмотрим поиск минимума функции Розенброка

f x , y =1 0 0 y−x2 21−x 2 2 . График функции Розенброка представлен на рис. 13.2.

Рисунок 13.2. График функции Розенброка

Как известно функция Розеброка имеет минимум в точке (1,1) равный 0. В виду своей

специфики функция Розеброка является тестовой для алгоритмов минимизации. Найдем

минимум этой функции с помощью функции optim (листинг 13.2).

// Начальное приближение x0

x0=[-2;2]

//Функция Розенброка

function y=gg(x)

//Обратите внимание, здесь x - массив из двух неизвестных.

y=100*(x(2)-x(1)^2)^2+(1-x(1))^2;

endfunction

//Формирование функции cst, возвращающей функцию Розенброка и

//ее градиент.

function [f,g,ind]=cst(x,ind)

5

f=gg(x);

g=numdiff(gg,x);

endfunction

// Вызов функции optim

[f,xopt]=optim(cst,x0)

Листинг 13.3.

Ниже представлены результат поиска минимума функции Розенброка с помощью

функции optim.

x0 =

-2.

2.

xopt =

0.9999955

0.9999910

f =

2.010D-11

13.3 Решение задач линейного программирования

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

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

на примере задачи об оптимальном рационе.

Задача об оптимальном рационе. Имеется четыре вида продуктов питания: П1, П2,

П3, П4. Известна стоимость единицы каждого продукта c1 , c2 , c3 , c4 . Из этих продуктов

необходимо составить пищевой рацион, который должен содержать не менее b1 единиц

белков, не менее b2 единиц углеводов, не менее b3 единиц жиров. Причем известно, в

единице продукта П1 содержится a11 единиц белков, a12 единиц углеводов и a13

единиц жиров и т.д. (см. таблицу 13.1 ).

Таблица 13.1. Содержимое белков, углеводов и жиров в продуктах

Элемент белки углеводы жиры

П1 a11 a12 a11

П2 a21 a22 a23

П3 a31 a32 a33

П4 a41 a42 a43

Требуется составить пищевой рацион, чтобы обеспечить заданные условия при

минимальной стоимости.

Пусть x1 , x2 , x3 , x4 - количества продуктов П1, П2, П3, П4. Общая стоимость

рациона равна

L=c1 x 1c2 x2c3 x3c 4 x 4=Σ

i=1

4

c i xi (13.1)

Сформулируем ограничение на количество белков, углеводов и жиров в виде

неравенств. В одной единице продукта П1 содержится a11 единиц белков, в x1

единицах - a11 x1 , в x2 единицах продукта П2 содержится a21 x2 единиц белка и т.д.

6

Следовательно общее количество белков во всех четырех типов продукта равно Σ

j =1

4

a j1 x j

и должно быть не больше b1 . Получаем первое ограничение

a11 x1a21 x2a31 x3a41 x 4≤b1 (13.2)

Аналогичные ограничения для жиров и углеводов имеют вид:

a12 x1a22 x2a32 x3a42 x4≤b2 (13.3)

a13 x1a23 x2a33 x3a43 x 4≤b3 (13.4)

Принимаем во внимание, что x1 , x2 , x3 , x4 положительные значения, получим еще

четыре ограничения

x1≥0, x2≥0, x3≥0, x4≥0 (13.5)

Таким образом задачу о рациональном рационе можно сформулировать следующим

образом: найти значения переменных x1 , x2 , x3 , x4 , удовлетворяющие системе

ограничений (13.2) - (13.5) , при которых линейная функция (13.1) принимала бы

минимальное значение.

Задача об оптимальном рационе является задачей линейного программирования,

функция (13.1) называется функцией цели, а ограничения (13.2) - (13.5) системой

ограничений задачи линейного программирования.

В задачах линейного программирования функция цели функция цели L и система

ограничений являются линейными.

В общем случае задачу линейного программирования можно сформулировать

следующим образом. Найти такие значения x1 , x2 ,, xn , удовлетворяющие системе

ограничений (), при которых функция цели L (13.7) достигает своего минимального

(максимального) значения

Σj

=1

n

aij x j≤bi ,i=1,,m,

xi≥0

(13.6)

L=c1 x1c2 x2cn xn=Σ

i=1

n

ci xi (13.7)

Для решения задач линейного программирования в Scilab предназначена функция linpro

следующей структуры

[x,kl,f]=linpro(с,A,b[,ci,cs][,k][,x0])

Здесь с - массив (вектор-столбец) коэффициентов при неизвестных функции цели,

длина вектора n совпадает с количеством неизвестных x, A - матрица при неизвестных из

левой части системы ограничений, количество строк матрицы равно количеству ограничений

m, а количество столбцов совпадает с количеством неизвестных n, b - массив (вектор-

столбец) содержит свободные члены системы ограничений, длина вектора m, ci - массив

(вектор-столбец) размерностью n содержит нижнюю границу переменных ci j≤x j  , если

таковая отсутствует, указывают [], cs - массив (вектор-столбец) длиной n, содержит верхнюю

границу переменных cs j≥x j  , если таковая отсутствует, указывают [], k - целочисленная

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

в матрице они будут находиться в k первых строках, оставшиеся l строк займут неравенства,

7

то есть m=k+l, x0 - вектор-столбец начальных приближений длиной n.

Функция linpro возвращает массив неизвестных x, минимальное значение функции f

и массив множителей Лагранжа kl [].

Рассмотрим использование функции linpro на примере решения следующей задачи

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

ЗАДАЧА 13.2.

Найти такие значения переменных x1 , x2 , x3 , x4 при которых функция цели L

L=−x2−2 x3x 4

достигает своего минимального значения и удовлетворяются ограничения:

3 x1−x2≤2

x2−2 x3≤−1

4 x3−x4≤3

5 x1x4≥6

x1≥0, x2≥0, x3≥0, x4≥0

.

Обратите внимание, что в четвертом ограничении присутствует знак ≥. Для приведения

системы ограничений виду (13.6) необходимо четвертое уравнение умножить на -1. Решение

задачи 13.1 представлено на листинге 13.4.

c=[0;-1;-2;1];

A=[3 -1 0 0;0 1 -2 0; 0 0 4 -1; -5 0 0 -1];

b=[2;-1;3;-6];

ci=[0;0;0;0];

[x,kl,f]=linpro(p,A,b,ai,[])

Листинг 13.4.

Полученные значения представлены на листинге 13.5.

f=

2.

kl=

0.

0.

0.

0.

0.0909091

1.0909091

0.5454545

0.4545455

x=

1.

1.

1.

1

Листинг 13.5.

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

ЗАДАЧА 13.3.

Туристическая фирма заключила контракт с двумя турбазами на одном из

черноморских курортов, рассчитанных соответственно, на 200 и 150 человек.

8

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

походы в горы.

Составить маршрут движения туристов так, чтобы это обошлось возможно

дешевле, если дельфинарий принимает в день 70 организованных туристов,

ботанический сад _ 180,а в г оры в о дин д ень могут п ойти 110ч еловек .

Стоимость одного посещения выражается таблицей 13.2.

Таблица 13.2.

Турбаза Дельфинарий Ботанический

сад

Поход в горы

1 5 6 20

2 10 12 5

Для решения задачи введем следующие обозначения:

x1 _ число т уристов п ервой т урбазы ,п осещающих д ельфинарий ;

x2 _ число т уристов п ервой т урбазы ,п осещающих б отанический с ад ;

x3 _ число т уристов п ервой т урбазы ,о тправляющихся в п оход ;

x4 _ число т уристов в торой турбазы ,п осещающих д ельфинарий ;

x5 _ число т уристов в торой турбазы ,п осещающих б отанический с ад ;

x6 _ число т уристов в торой турбазы ,о тправляющихся в п оход .

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

: фирмы Z=5x1+6x2+20x3+10x4+12x5+5x6.

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

x1 + x4 ≤ 70;

x2 + x5 ≤ 180;

x3 + x6 ≤ 110;

x1 + x2 + x3 = 200;

x4 + x5 + x6 = 150.

Кроме того, количество туристов, участвующих в мероприятиях не может быть

отрицательным: x1≥0, x2≥0, x3≥0, x4≥0, x5≥0, x6≥0.

Решение задачи представлено в листинге 13.6. В массиве x будут хранится значения x1,

x2, x3, x4, x5 и x6. В матрице коэффициентов A, первые две строки отражают равенства

системы ограничений, поэтому включен параметр k=2. Вектор ci представляет нижнюю

границу неизвестных, то есть отражает тот факт, что они не могут быть меньше нуля. Если

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

содержать вектор неизвестных x, вторая _ множители Лагранжа kl, а третья _ минимальное

значение функции цели f.

Z=[5;6;20;10;12;5];

A=[1 1 1 0 0 0;

0 0 0 1 1 1;1 0 0 1 0 0;0 1 0 0 1 0;0 0 1 0 0 1];

b=[200;150;70;180;110];

ci=[0;0;0;0;0;0];

k=2;

[x,kl,f]=linpro(Z,A,b,ci,[],k);

Листинг 13.6.

Полученное в Scilab решение задачи представлено на листинге 13.7

9

f=

2120.

kl=

0.

0.

-20.

0.

-1.

0.

-6.

-11.

1.

0.

6.

x=

30.

170.

0.

40.

0.

110.

Листинг 13.7.

Авторы надеются, что разобрав примеры из этой главы, читатель сможет использовать

Scilab для решения своих оптимизационных задач.

Этой главой мы завершаем первое знакомство с пакетом и надеемся, что свободно

распространяемый пакет Scilab поможет читателю решать математические задачи,

возникающие в его практической деятельности.__