Решение оптимизационных задач

	
function obj = phi(x)
	obj = x^4+3*x^3-13*x^2-6*x+26;
endfunction
[x, obj, info, iter]= sqp(-3, @phi)
% Результаты решения
x =-3.8407
obj =-95.089
info = 101
iter = 5		

Пример 10.2. Найти минимум функции Розенброка В классическом определении функции Розенброка N = 100 (N > 0, достаточно большое число), авторы используют N=20. (Прим. редактора.) $$f(x,y)=N(y-x^{2})^{2}+(1-x^{2})^{2}$$

На рис. 10.1 изображен график функции: $$\phi(x)=x^4 + 3x^3 - 13x^2- 6x + 26$$

Построим график функции Розенброка для $$N = 20$$ (см. листинг 10.2). График полученной поверхности приведён на рис. 10.2.

	
[x y]= meshgrid(-2:0.1:2, 2:-0.1:-2);
z =20*(y-x.^2).^2+(1-x).^2;
surf(x, y, z);

Как известно, функция Розенброка имеет минимум в точке (1,1) равный 0. В виду своей специфики функция Розенброка является тестовой для алгоритмов минимизации. Найдём минимум этой функции с помощью функции $$sqp$$ (см. листинг 10.3).

При решении задач на экстремум функций многих переменных следует учитывать особенности синтаксиса при определении оптимизируемой функции. Аргументом функции многих переменных (в нашем случае — её имя $$r$$) является массив $$x$$, первая переменная имеет имя $$x(1)$$, вторая $$x(2)$$ и т. д. Если имя аргумента функции многих переменных будет другим — допустим m, то изменятся и имена переменных: $$m(1), m(2), m(3)$$ и т.д.

	
function y=r(x)
	y=20*(x(2)-x(1)^2)^2+(1-x(1))^2;
endfunction
x0 = [0; 0];
[x, obj, info, iter]= sqp(x0, @r)
% Результаты вычислений
x =
	1.00000
	1.00000
obj = 7.1675e-13
info = 101
iter = 14

(рис 10.2) График функции Розенброка

Как и следовало ожидать, функция $$sqp$$ нашла минимум в точке (1,1), само значение 0 найдено достаточно точно ($$7.2*10^{-13} $$). Значение info = 101 говорит о корректном решении задачи, для нахождения минимального значения функции Розенброка потребовалось 14 итераций.

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

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

Пример 10.3. Найти максимум и минимум функции ([1])

$$F=(x-3)^{2}-(y-4)^{2}$$ при ограничениях: $$\left\{ \begin{matrix} 3x+2y\ge 7\\ 10x-y\le 8\\ -18x+4y\le 12\\ x\ge 0\\y\ge 0 \end{matrix} \right.$$.

В функции $$sqp$$ все ограничения должны быть вида $$\ge 0$$. Поэтому второе и третье ограничение умножим на -1, и перенесём всё в левую часть неравенств. В результате этих несложных преобразований система ограничений примет вид:

$$g(x)=\left\{ \begin{matrix} 3x+2y-7\ge 0\\ -10x+y+8\ge 0\\ 18x-4y+12\ge 0\\ x\ge 0\\y\ge 0 \end{matrix} \right.$$

Последовательно рассмотрим задачу на минимум (листинг 10.4) и максимум (листинг 10.5).

	
% В задаче на минимум функция, в которой хранится F(x) будет такой
function y=f(x)
	y=(x(1)-3)^2+(x(2)-4)^2;
endfunction
% Вектор-функцию ограничений g(x) можно записать так:
function r = g(x)
	r=[3*x(1)+3*x(2)-7; -10*x(1)+x(2)+8;18*x(1)-4*x(2)+12;x(1);x(2)];
endfunction
% Вычисляем с помощью функции sqp
x0 = [0; 0]; [x, obj, info, iter]= sqp(x0, @f, [ ], @g)
minimum=f(x)
% Результаты
x =
	1.2178
	4.1782
obj = 3.2079
info = 101
iter = 5
mininum =3.2079

Минимум 3.2079 достигается в точке (1.2178, 4.1782), значение info = 101 говорит о корректном решении задачи, для нахождения минимального значения потребовалось всего 5 итераций.

Теперь рассмотрим решение задачи на максимум. Функция $$sqp$$ может искать только минимум. Поэтому вспомним, как задача на максимум сводится к задаче на минимум: $$max f (x) = - min f (-x)$$. Это учтено в листинге 10.5.

	
function y=f(x)
	y=(x(1)-3)^2+(x(2)-4)^2;
endfunction
% Определяем функцию, для которой минимум будет максимумом функции f
function y=f1(x)
y= -f(-x);
endfunction
function r = g(x)
	r=[3*x(1)+2*x(2)-7; -10*x(1)+x(2)+8;18*x(1)-4*x(2)+12;x(1);x(2)];
endfunction
x0 = [0; 0]; [x, obj, info, iter]= sqp(x0, @f1, [ ], @g)
maximum=f(x)
% Результаты работы программы
x =
	2.0000
	12.0000
obj = -281.00
info = 101
iter = 3
maximum = 65.000

Максимум достигается в точке (2,12), его величина равна 65.

Пример 10.4. План производства изделий трёх типов составляет 120 деталей ($$x_1$$ — количество изделий первого вида, $$x_2$$ — количество изделий второго вида, $$x_3$$ — количество изделий третьего вида). Изделия можно изготовить тремя способами. При первом технологическом способе производят изделия первого типа и затраты составляют $$4x_{1}+x_{1}^{2}$$. Второй технологический способ предназначен для производства изделий второго типа и затраты составляют $$8x_{2}+x_{2}^{2}$$. Третий способ позволяет производить изделия третьего типа и затраты в нём можно рассчитать по формуле $$x_{3}^{2}$$. Определить, сколько изделий каждого типа надо изготовить, чтобы затраты были минимальными [1].

Сформулируем эту задачу, как задачу оптимизации. Найти минимум функции $$f(x_{1,}x_{2})=4x_{1}+x_{1}^{2}+8x_{2}+x_{2}^{2}+x_{3}^{2}$$ при следующих ограничениях $$x_{1}+x_{2}+x_{3}=120,x_{1}\ge 0,x_{2}\ge 0,x_{3}\ge 0$$

	
% Оптимизируемая функция f
function y=f(x)
	y=4-x(1)+x(1)*x(1)+8*x(2)+x(2)*x(2)+x(3)*x(3);
endfunction
% Функция ограничения g(x) = 0
function z=g(x)
	z=x(1)+x(2)+x(3)-120;
endfunction
% Функция ограничения f(x) =0
function u= fi(x)
	fi =[x(1); x(2); x(3)];
endfunction
x0 = [0; 0; 0]; [x, obj, info, iter]= sqp(x0, @f, @g)
% Результаты решения
x =
	40.000
	38.000
	42.000
obj = 5272.0
info = 101
iter = 8

Минимальные затраты составят 5272 денежных единицы, при этом будет произведено 40 изделий первого вида, 38 — второго и 42 — третьего. Для решения задачи было проведено 8 итераций.

Пример 10.5. Найти максимум функции $$f=-x_{1}^{2}-x_{2}^{2}$$ при ограничениях $$(x_{1}-7)^{2}+(x_{2}-7)^{2}\le 18, x_{1}\ge 0, x_{2}\ge 0$$.

В этой задаче необходимо свести задачу на максимум к задаче на минимум, а также путём умножения на -1 заменить знак в неравенстве. Текст программы-решения задачи в Octave представлен в листинге 10.7. Функция достигает своего максимального значения -32 в точке (4, 4).

	
function y=f(x)
	y=-x(1)*x(1)*x(2)*x(2);
endfunction
function y=f1(x)
	y= -f(-x);
endfunction
function u= fi(x)
	u=[-(x(1)-7)^2-(x(2)-7)^2+18;x(1); x(2)];
endfunction
x0 = [0; 0]; [xopt, obj, info, iter]= sqp(x0, @f1, [ ], @fi)
f(xopt)
% Результаты решения
xopt =
	4.0000
	4.0000
obj =32.000
info =101
iter =8
ans =-32.000

Следующим классом оптимизационных задач, рассматриваемых в этой главе, будут задачи линейного программирования (ЗЛП).

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

Элемент	белки	углеводы	жиры
П1	$$a_11$$	$$a_12$$	$$a_11$$
П2	$$a_21$$	$$a_22$$	$$a_23$$
П3	$$a_31$$	$$a_32$$	$$a_33$$
П4	$$a_41$$	$$a_42$$	$$a_43$$

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

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

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

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

Задача об оптимальном рационе. Имеется четыре вида продуктов питания: $$П1, П2, П3, П4$$. Известна стоимость единицы каждого продукта $$c_{1},c_{2},c_{3},c_{4}$$. Из этих продуктов необходимо составить пищевой рацион, который должен содержать не более$$b_{1}$$ единиц белков, не более $$b_{2}$$ единиц углеводов, не более $$b_{3}$$ единиц жиров. Причём известно, в единице продукта П1 содержится $$a_{11}$$ единиц белков, $$a_{12}$$ единиц углеводов и $$a_{13}$$ единиц жиров и т.д. (см. таблицу 10.1).

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

Пусть $$x_{1},x_{2},x_{3},x_{4}$$— количества продуктов $$П1, П2, П3, П4$$. Общая стоимость рациона равна

$$L=c_{1}x_{1}+c_{2}x_{2}+c_{3}x_{3}+c_{4}x_{4}=\sum _{i=1}^{4}c_{i}x_{i}$$

Сформулируем ограничение на количество белков, углеводов и жиров в виде неравенств. В одной единице продукта $$П1$$ содержится $$a_{11}$$ единиц белков, в $$x_{1}$$ единицах — $$a_{11}x_{1}$$, в $$x_{2}$$ единицах продукта $$П2$$ содержится $$a_{21}x_{2}$$ единиц белка и т.д. Следовательно общее количество белков во всех четырёх типов продукта равно $$\sum _{j=1}^{4}a_{j1}x_{j}$$ и должно быть не больше $$b_{1}$$. Получаем первое ограничение

$$a_{11}x_{1}+a_{21}x_{2}+a_{31}x_{3}+a_{41}x_{4}\le b_{1}$$

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

$$a_{12}x_{1}+a_{22}x_{2}+a_{32}x_{3}+a_{42}x_{4}\le b_{2}\\ a_{13}x_{1}+a_{23}x_{2}+a_{33}x_{3}+a_{43}x_{4}\le b_{3}$$

Принимаем во внимание, что $$x_{1},x_{2},x_{3},x_{4}$$ положительные значения, получим ещё четыре ограничения

$$x_{1}\ge 0,\ x_{2}\ge 0,\ x_{3}\ge 0,\ x_{4}\ge 0$$

Таким образом задачу о оптимальном рационе можно сформулировать следующим образом: найти значения переменных $$x_{1},x_{2},x_{3},x_{4}$$ удовлетворяющие системе ограничений (10.2) — (10.4), при которых линейная функция (10.1) принимала бы минимальное значение.

Задача об оптимальном рационе является задачей линейного программирования, функция (10.1) называется функцией цели, а ограничения (10.2) — (10.4) системой ограничений задачи линейного программирования.

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

В общем случае задачу линейного программирования можно сформулировать следующим образом. Найти такие положительные значения $$x_{1},x_{2},\ldots,x_{n}$$, при которых функция цели $$L$$ (10.5) достигает своего минимального значения и удовлетворяет системе линейных ограничений (10.6).

$$L=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}=\sum _{i=1}^{n}c_{i}x_{i}$$ $$\sum _{j=1}^{n}a_{\mathit{ij}}x_{j}\le b_{i},\quad i=1,2,\ldots m.$$

Если в задачу линейного программирования добавляется ограничение целочисленности значений $$x$$, то мы получаем задачу целочисленного программирования.

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

Найти такие положительные значения $$x_{1},x_{2},\ldots,x_{n}$$, при которых функция цели L (10.5) достигает своего минимального (максимального) значения и удовлетворяет системе линейных ограничений. Система ограничений может быть представлена неравенствами (10.7) или (10.8). При этом значения $$x$$ могут быть, как вещественными, так и целочисленными, как положительными, так и отрицательными.

$$\sum _{j=1}^{n}a_{\mathit{ij}}x_{j}\le b_{i}, \quad i=1,2,\ldots,m$$ $$\sum _{j=1}^{n}a_{\mathit{ij}}x_{j}\ge b_{i}, \quad i=1,2,\ldots,m$$

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

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

Для решения задач линейного программирования в Octave существует функция $$[xopt, fmin, status, extra] = glpk(c, a, b, lb, ub, ctype, vartype, sense, param)$$

Здесь:

$$c$$ — вектор-столбец, включающий в себя коэффициенты при неизвестных функции цели, размерность вектора c равна количеству неизвестных $$n$$ в задаче линейного программирования;

$$a$$ — матрица при неизвестных из левой части системы ограничений, количество строк матрицы равно количеству ограничений $$m$$, а количество столбцов совпадает с количеством неизвестных $$n$$;

$$b$$ — вектор-столбец содержит свободные члены системы ограничений, размерность вектора равна количеству ограничений $$m$$.

$$lb$$ — вектор-столбец размерности $$n$$, содержащий верхнюю систему ограничений $$(x > lb)$$, по умолчанию $$lb$$ — вектор столбец, состоящий из нулей;

$$ub$$ — вектор-столбец размерности $$n$$, содержащий нижнюю систему ограничений $$(x < ub)$$, по умолчанию верхняя система ограничений отсутствует, подразумевается, что все значения вектора $$ub$$ равны +\infty;

$$ctype$$ — массив символов размерности $$n$$, определяющий тип ограничения (например, (10.7) или (10.8)), элементы этого век-тора могут принимать одно из следующих значений:

$$"F"$$ — ограничение будет проигнорировано,

$$"U"$$ — ограничение с верхней границей $$((A(i,:)*x <= b(i))$$,

$$"S"$$ — ограничение в виде равенства $$((A(i,:)*x = b(i))$$,

$$"L"$$ — ограничение с верхней границей $$((A(i,:)*x >= b(i))$$,

$$"D"$$ — двойное ограничение $$((A(i,:)*x <= b(i)$$ и $$(A(i,:)*x>= b(i))$$;

$$vartype$$ — массив символов размерности $$n$$, который определяет тип переменной $$x_i$$ "C" — вещественная переменная, "I" —целочисленная переменная;

$$sense$$ — значение, определяющее тип задачи оптимизации:

1 — задача минимизации,

-1 — задача максимизации;

$$param$$ — структура, определяющая параметры оптимизационных алгоритмов, при обращении к функции glpk.

Во многих случаях достаточно значений структуры param по умолчанию, в этом случае последний параметр в функции $$glpk$$ можно не указывать. Подробное описание структуры $$param$$ выходит за рамки книги, в случае необходимости его использования авторы рекомендуют обратиться ко встроенной справке Octave.

Функция $$glpk$$ возвращает следующие значения:

$$xopt$$ — массив значений $$x$$, при котором функция цели $$L$$ принимает оптимальное значение;

$$fmin$$ — оптимальное значение функции цели;

$$status$$ — переменная, определяющая как решена задача оптимизация, при $$status = 180$$, решение найдено и задача оптимизации решена полностью Если $$status\not =180$$, то полученному решению доверять нельзя, подробнее о значениях переменной $$status$$ в этом случае можно прочитать в справке. ;

$$extra$$ — структура, включающая следующие поля:

$$lambda$$ — множители Лагранжа;

$$time$$ — время в секундах, затраченное на решение задачи;

$$mem$$ — память в байтах, которая была использована, при решении задачи (значение недоступно, если была использована библиотека линейного программирования GLPK 4.15 В последней на момент написания книги версии Octave использовалась библиотека GLPK версии 4.38. и выше).

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

Пример 10.6. Найти такие значения переменных $$x_{1},x_{2},x_{3},x_{4}$$ при которых функция цели $$L=-x_{2}-2x_{3}+4x_{4}$$ достигает своего минимального значения и удовлетворяются ограничения:

$$\left\{\begin{aligned} 3x_{1}-x_{2}\le 2\\ x_{2}-2x_{3}\le -1\\ 4x_{3}-x_{4}\le 3\\ 5x_{1}+x_{4}\ge 6\\ x_{1}\ge 0,\ x_{2}\ge0,\ x_{3}\ge 0,\ x_{4}\ge 0. \end{aligned}\right.$$

Сформируем параметры функции $$gplk$$

$$c=\begin{pmatrix}0\\-1\\-2\\4\end{pmatrix}$$ — коэффициенты при неизвестных функции цели,

$$a=\begin{pmatrix}3-100\\01-20\\004-1\\5001\end{pmatrix}$$ — матрица системы ограничений,

$$b=\begin{pmatrix}2\\-1\\3\\6\end{pmatrix}$$ –– свободные члены системы ограничений,

$$ctype ="UUUL"$$— массив, определяющий тип ограничения Первые три ограничения типа "меньше", четвёртое — типа "больше" ,

$$vartype ="CCCC"$$— массив, определяющий тип переменной, в данном случае все переменные вещественные,

$$sense = 1$$ –– задача на минимум.

Текст программы решения задачи приведён в листинге 10.8.

	
c = [0; -1; -2; 4]; a =[3 -1 0 0; 0 1 -2 0; 0 0 4 -1;5 0 0 1];
b = [2; -1; 3; 6];
ctype="UUUL"; vartype= "CCCC"; sense =1;
[xmin, fmin, status] =glpk(c, a, b, [0; 0; 0; 0], [], ctype, vartype, sense)
% Результаты решения
xmin =
	1.00000
	1.00000
	1.00000
	1.00000
fmin = 1.00000
status = 180

Минимальное значение $$L = 1$$ достигается при $$x=\begin{pmatrix}1\\1\\1\\1\end{pmatrix}$$. Значение переменной $$status$$ равно 180, что свидетельствует о корректном решении задачи линейного программирования.

Пример 10.7. Найти такие значения переменных $$x_{1},x_{2},x_{3}$$ при которых функция цели $$L=-5+x_{1}-x_{2}-3x_{3}$$ достигает своего минимального значения и удовлетворяются ограничения:

$$\left\{ \begin{aligned} x_{1}+x_{2}\ge 2\\ x_{1}-x_{2}\le 0\\ x_{1}+x_{3}\ge 2\\ x_{1}+x_{2}-x_{3}\le 3\\ x_{1}\ge 0,\ x_{2}\ge 0,\ x_{3}\ge 0. \end{aligned} \right.$$

Сформируем параметры функции $$gplk$$:

$$c=\begin{pmatrix}1\\-1\\-3\end{pmatrix}$$ — коэффициенты при неизвестных функции цели,

$$a=\begin{pmatrix}110\\1-10\\101\\11-1\end{pmatrix}$$ — матрица системы ограничений (три переменных и четыре ограничения),

$$b=\begin{pmatrix}2\\0\\2\\3\end{pmatrix}$$ — свободные члены системы ограничений,

$$ctype ="LULU"$$— массив символов, определяющий тип ограничения Первое и третье ограничения типа "больше", второе четвёртое — типа "меньше". ,

$$vartype ="CCC"$$— массив, определяющий тип переменной, в данном случае все переменные вещественные,

$$sense = -1$$ –– задача на максимум.

Текст программы решения задачи приведён в листинге 10.9.

	
c =[1; -1; -3]; a =[1 1 0; 1 -1 0; 1 0 1; 1 1 -1]; b = [2; 0; 2; 3];
ctype="LULU"; vartype= "CCC"; sense =-1;
[xmax, fmax, status]= glpk(c, a, b, [ ], [ ], ctype, vartype, sense)
% Результаты решения
xmax =
	1.66667
	1.66667
	0.33333
fmax = -1.0000
status = 180

Минимальное значение Авторы обращают внимание читателей в Octave $$fmin$$ было равно -1, а потом к нему необходимо было прибавить -5 $$L = -6$$ достигается при $$x=\begin{pmatrix}1.66667\\1.66667\\0.33333\end{pmatrix}$$

Значение переменной $$status$$ равно 180, что свидетельствует о корректном решении задачи линейного программирования.

Решим задачу 10.7, как задачу целочисленного программирования (см. листинг 10.10)

	
c =[1; -1; -3]; a =[1 1 0; 1 -1 0; 1 0 1; 1 1 -1]; b = [2; 0; 2; 3];
ctype="LULU"; vartype= "III"; sense =-1;
[xmax, fmax, status]= glpk(c, a, b, [ ], [ ], ctype, vartype, sense)
% Результаты решения
xmin =
	2
	2
	1
fmin = -3
status = 171	

Значение $$status = 171$$ свидетельствует о корректном решении задачи целочисленного программирования, значение $$L = -8$$ достигается при $$x=\begin{pmatrix}2\\2\\1\end{pmatrix}$$

Пример 10.8. Туристическая фирма заключила контракт с двумя турбазами на одном из черноморских курортов, рассчитанных соответственно на 195 и 165 человек. Туристам для посещения предлагается дельфинарий в городе, ботанический сад и походы в горы.

Стоимость одного посещения

Турбаза	Дельфинарий	Ботанический сад	Поход в горы
1	5	9	20
2	10	12	24

Составить маршрут движения туристов так, чтобы это обошлось возможно дешевле, если дельфинарий принимает в день 90 организованных туристов, ботанический сад — 170, а в горы в один день могут пойти 105 человек.

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

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

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

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

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

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

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

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

Составим функцию цели, заключающуюся в минимизации стоимости мероприятий фирмы: Z = 5x1 + 9x2 + 20x3 + 10x4 + 12x5 + 24x6.

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

$$\left\{ \begin{aligned} x1 + x4 \leq 90;\\ x2 + x5 \leq 170;\\ x3 + x6 \leq 105;\\ x1 + x2 + x3 = 195;\\ x4 + x5 + x6 = 165. \end{aligned} \right.$$

Количество туристов, участвующих в мероприятиях не может быть отрицательным: $$x1\geq 0,x2\geq 0,x3 \geq 0,x4\geq 0,x5\geq 0,x6\geq 0$$.

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

В массиве x будут хранится значения x1, x2, x3, x4, x5 и x6.

Сформируем параметры функции $$gplk$$:

$$c=\begin{pmatrix}15\\9\\20\\10\\12\\24\end{pmatrix}$$ — коэффициенты при неизвестных функции цели,

$$a=\begin{pmatrix}100100\\010010\\001001\\111000\\000111\end{pmatrix}$$ –– матрица системы ограничений шесть переменных и пять ограничений,

$$b=\begin{pmatrix}90\\170\\105\\195\\165\end{pmatrix}$$ — свободные члены системы ограничений,

$$ctype ="UUUSS"$$— массив, определяющий тип ограничения Первые три ограничения типа "меньше", четвёртое и пятое — типа "равно". ,

$$vartype ="IIIIII"$$— массив, определяющий тип переменной, в данном случае все переменные целые (задача целочисленного программирования),

$$sense=1$$ — задача на минимум.

Решение задачи представлено в листинге 10.11.

	
c = [5; 9; 20; 10; 12; 24];
a =[1 0 0 1 0 0;0 1 0 0 1 0;0 0 1 0 0 1;1 1 1 0 0 0;0 0 0 1 1 1];
b = [90; 170; 105; 195; 165];
ctype="UUUSS"; vartype= "IIIIII"; sense =1;
[xmin, fmin, status]= glpk(c, a, b, [ ], [], ctype, vartype, sense)
% Результаты решения
xmin =
	90
	5
	100
	0
	165
	0
fmin = 4475
status = 171	

Значение переменной $$status$$ = 171 свидетельствует о корректном решении задачи целочисленного программирования.

В результате получилось следующее решение: 90 туристов первой турбазы посетят дельфинарий, 5 туристов первой турбазы и все 165 второй турбазы поедут в ботанический сад, 100 туристов первой турбазы отправятся в поход. Стоимость мероприятия составит 4475.

Данные к задаче 10.9

Тип оборудования	Затраты времени на обработку одного изделия вида (станко-ч)			Общий фонд времени работы оборудования (ч)
	А	Б	В
Фрезерное	2	4	5	120
Токарное	1	8	6	280
Сварочное	7	4	5	240
Шлифовальное	4	6	7	360
Прибыль (тыс. грн)	10	14	12

Пример 10.9. Для изготовления трёх видов изделий (А, Б, В) используется токарное, фрезерное, шлифовальное и сварочное оборудование. Затраты времени на обработку одного изделия каждого типа представлены в таблице 10.3. Общий фонд рабочего времени каждого вида оборудования и прибыль от реализации изделий каждого типа представлены этой же таблице. Составить план выпуска изделий для достижения максимальной прибыли [1].

Пусть $$x_1$$ — количество изделий вида А, $$x_2$$ — количество изделий вида Б, $$x_3$$ — вида В.

Прибыль от реализации всех изделий составляет

$$L=10x_{1}+14x_{2}+12x_{3}$$

Общий фонд рабочего времени фрезерного оборудования составляет $$2x_{1}+4x_{2}+5x_{3}$$. Эта величина не должна превышать 120 часов.

$$2x_{1}+4x_{2}+5x_{3}\le 120$$

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

$$\left\{\begin{matrix}x_{1}+8x_{2}+6x_{3}\le 280\\7x_{1}+4x_{2}+5x_{3}<240\\4x_{1}+6x_{2}+7x_{3}\le 360\end{matrix}\right.$$

Таким образом получаем следующую задачу линейного программирования.

Найти такие положительные значения $$x_1,x_2,x_3$$ при которых функция цели $$L$$ (10.9) достигает максимального значения и выполняются ограничения (10.10)–(10.11).

Теперь решим эту задачу в Octave с помощью функции $$gplk$$.

Сформируем параметры функции $$gplk$$:

$$c=\begin{pmatrix}10\\14\\12\end{pmatrix}$$ — коэффициенты при неизвестных функции цели,

$$a=\begin{pmatrix}245\\186\\745\\467\end{pmatrix}$$ — матрица системы ограничений (три переменных и четыре ограничений),

$$b=\begin{pmatrix}120\\280\\240\\360\end{pmatrix}$$ –– свободные члены системы ограничений,

$$ctype ="UUUU"$$— массив, определяющий тип ограничения Все четыре ограничения типа "меньше". ,

$$vartype ="III"$$— массив, определяющий тип переменной, в данном случае все переменные целые,

$$sense = -1$$ — задача на максимум.

Решение задачи в Octave представлено в листинге 10.12

	
c = [10; 14; 12]; a =[2 4 5; 1 8 6; 7 4 5; 4 6 7]; b = [ 1 2 0; 2 8 0; 2 4 0; 3 6 0];
ctype="UUUU"; vartype= "III"; sense =-1;
[xmax, fmax, status] =glpk(c, a, b, [0;0;0], [], ctype, vartype, sense)
% Результаты решения
xmax =
	24
	18
	0
fmax = 492
status = 171

Таким образом для получения максимальной прибыли ($$fmax =492$$) необходимо произвести 24 единицы изделия типа А и 18 единиц изделия типа Б. Значение параметра $$status = 171$$ говорит о корректности решения задачи линейного программирования.

Пример 10.10. Для изготовления четырёх видов изделий используется токарное, фрезерное, сверлильное, расточное шлифовального оборудование, а также комплектующие изделия. Сборка изделий требует сборочно-наладочных работ. В таблице 10.4 представлены: нормы затрат ресурсов на изготовление различных изделий, наличие каждого из ресурсов, прибыль от реализации одного изделия, ограничения на выпуск изделий второго и третьего типа [1]. Сформировать план выпуска продукции для достижения максимальной прибыли.

Нормы затрат ресурсов к примеру 10.10

Ресурсы	Нормы затрат на одно изделие				Общий объём ресурсов
Производительность оборудования (человеко-ч)
токарного	550		620		64270
фрезерного	40	30	20	20	4800
сверлильного	86	110	150	52	22360
расточного	160	92	158	128	26240
шлифовального		158	30	50	7900
Комплектующие изделия (шт.)	3	4	3	3	520
Сборочно-наладочные работы (человеко-ч)	4.5	4.5	4.5	4.5	720
Прибыль от реализации одного изделия (тыс. руб.)	315	278	573	370
Выпуск
минимальный		40
максимальный			120

Пусть $$x_1$$ — количество изделий первого вида, $$x_2$$ — количество изделий второго вида,$$x_3$$ и $$x_4$$ — количество изделий третьего и четвёртого вида соответственно. Тогда прибыль от реализации всех изделий вычисляется по формуле

$$L=315x_{1}+278x_{2}+573x_{3}+370x_{4}$$

Ограничения на фонд рабочего времени формируют следующие ограничения

$$\left\{ \begin{aligned} 550x_{1}+620x_{3}\le 64270\\ 30x_{1}+30x_{2}+20x_{3}+20x_{4}\le 4800\\ 86x_{1}+110x_{2}+150x_{3}+52x_{4}\le 22360\\ 160x_{1}+92x_{2}+158x_{3}+128x_{4}\le 26240\\ 158x_{2}+30x_{3}+50x_{4}\le 7900 \end{aligned} \right.$$

Ограничение на возможное использование комплектующих изделий

$$3x_{1}+4x_{2}+3x_{3}+3x_{4}\le 520$$

Ограничение на выполнение сборочно-наладочных работ

$$4.5x_{1}+4.5x_{2}+4.5x_{3}+4.5x_{4}\le 720$$

Ограничения на возможный выпуск изделий каждого вида

$$x2\ge 40,\ x3\le 120,\ x1\ge 0,\ x3\ge 0,\ x4\ge 0$$

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

Найти значения $$x_{1},x_{2},x_{3}$$ и $$x_{4}$$ при которых функция цели $$L$$ (10.12) достигает своего максимального значения и выполняются ограничения (10.13)–(10.16).

Рассматриваемая задача из широко известной книги [1] была интересна авторам в связи с тем, что ещё 25 лет назад для решения задач подобной сложности использовали большие ЭВМ и специализированные пакеты решения оптимизационных задач. На подготовку данные и решение её затрачивался не один час. Мы же попробуем решить её в Octave и посмотрим сколько времени у нас на это уйдёт.

Сформируем параметры функции $$gplk$$:

$$c=\begin{pmatrix}315\\278\\573\\370\end{pmatrix}$$ — коэффициенты при неизвестных функции цели,

$$a=\begin{pmatrix} 55006200\\ 40302020\\ 8611015052\\ 16092158128\\ 01583050\\ 3433\\ 4.54.54.54.5\\ 0100\\ 0010\\ 1000\\ 871 0010\\ 872 0001 873 \end{pmatrix}$$ — матрица системы ограничений (четыре переменных и двенадцать ограничений),

$$b=\begin{pmatrix}64270\\4800\\22360\\26240\\7900\\520\\720\\40\\120\\0\\0\\0\end{pmatrix}$$ — свободные члены системы ограничений,

$$ctype ="UUUUUUULULLL"$$— массив символов, определяющий тип ограничения Первые три ограничения типа "меньше", четвёртое и пятое — типа "равно". ,

$$vartype ="IIII"$$— массив, определяющий тип переменной, в данном случае все переменные целые (задача целочисленного программирования),

$$sense = -1$$ — задача на максимум.

Программа решения задачи в Octave представлена в листинге 10.13.

	
c = [315; 278; 573; 370];
a =[550 0 620 0; 40 30 20 20; 86 110 150 52; 160 92 158 128; 0 158
	30 50; 3 4 3 3; 4.5 4.5 4.5 4.5; 0 1 0 0; 0 0 1 0; 1 0 0 0; 0 0
	1 0; 0 0 0 1];
b = [64270; 4800; 22360; 26240; 7900; 520; 720; 40; 120; 0; 0; 0];
ctype="UUUUUUULULLL"; vartype= "IIII"; sense =-1;
[xmax, fmax, status]= glpk(c, a, b, [ ], [ ], ctype, vartype, sense)
% Результаты решения
[xmax, fmax, status]= glpk(c, a, b, [ ], [ ], ctype, vartype, sense)
xmax =
	65
	40
	46
	4
fmax = 59433
status = 171	

Для получения максимальной прибыли ($$fmax = 492$$) необходимо произвести 65 единиц изделий первого типа, 40 — второго, 46 — третьего - и 4 — четвёртого. Значение параметра $$status = 171$$ говорит о корректности решения задачи линейного программирования.

Для написания программы и решения довольно сложной задачи в Octave понадобилось буквально пару минут.

Подобным образом можно решать всевозможные задачи линейного программирования. Кроме Octave, для решения задач линейного программирования авторы использовали электронные таблицы OpenOffice.org Calc, MS Office Excel, математические программы MathCad, Matlab, Maple, Mathematica, Scilab. На наш взгляд, именно Octave, обладает самой гибкой и мощной функцией $$gplk$$ для решения задач линейного программирования из всех свободных и проприетарных программ.

Рассмотренных двух функций ($$gplk$$ и $$sqp$$) достаточно для решения очень многих оптимизационных задач. Если читателю встретятся оптимизационные задачи, которые невозможно решить с помощью $$gplk$$ и $$sqp$$, то авторы рекомендуют ему обратиться к пакету расширений Minimization для GNU .