Решение задач оптимизации с применением пакетов прикладных программ

Рабочая среда MATLAB. Запуск MATLAB 6.x приводит к открытию рабочей среды.

Рабочая среда содержит следующие элементы:

· меню;

· панель инструментов с кнопками и раскрывающимся списком;

· окно с вкладками Launch Pad и Workspace, из которого можно получить простой доступ к различным модулям Toolbox и к содержимому рабочей среды;

· окно с вкладками Command History и Current Directory, предназначенное для просмотра и повторного вызова ранее ввденных команд, а также для установки текущего каталога;

· командное окно;

· строку состояния.

Все команды следует набирать в командной строке. Для того чтобы MATLAB выполнила команду или вычислила выражение, набор любой команды или выражения должен заканчиваться нажатием на кнопку <Enter>.

Арифметические вычисления. Встроенные математические функции MATLAB позволят находить значения различных выражений. MATLAB предоставляет возможность управления форматом вывода результата. Команды для вычисления выражений имеют вид, свойственный всем языкам программирования высокого уровня [14].

Использование переменных. В MATLAB предусмотрена возможность работы с переменными. При этом нет необходимости задавать тип вводимой переменной.

В MATLAB команды можно завершать точкой с запятой. При этом операция будет выполнена, но результат выполнения не будет выводиться на экран.

Сохранение рабочей среды. Один из способов сохранения значений всех переменных - это использование в меню File пункта Save Workspace As. По умолчанию предлагается сохранить файл в подкаталоге work основного каталога MATLAB. MATLAB сохранит результаты работы в файле с расширением *.mat. Теперь можно закрыть MATLAB одним из следующих способов:

· выбрать в меню File пункт Exit MATLAB;

· нажать клавиши <Ctrl>+<Q>;

· набрать команду Exit в командной строке и нажать <Enter>;

· нажать на кнопку с крестиком в правом верхнем углу окна программы

MATLAB.

Для восстановления значений переменных следует открыть созданный файл при помощи подпункта Open меню File. Теперь все перменные, определенные в прошлом сеансе, стали доступными. Их можно использовать в следующем сеансе.

Сохранение и восстановление переменных рабочей среды можно выполнить и из командной строки. Для этого служат команды save и load. В конце сеанса работы с MATLAB надо выполнить команду

>>save session_1

В начале следующего сеанса работы для считывания переменных следует ввести коианду

>>load session_1

Подробную информацию о командах save и load можно получить, набрав в командной строке help save или help load. Переменные в файлах с расширением *.mat хранятся в двоичном виде.

В MATLAB имеется возможность записывать исполняемые команды и результаты в текстовый файл, который потом можно легко прочитать или распечатать из текстового редактора. Для начала ведения журнала служит команда diary.В качестве аргумента команды diary следует задать имя файла, в котором будет храниться журнал работы.

>> diary session_1.txt

При остановке записи сеанса работы, наберите

>> diary off

Рабочее пространство. Рабочее пространство - это область памяти, доступная из командной строки MATLAB. Две команды, who и whos, показывают текущее содержание рабочего пространства. Команда who выдает краткий список, а команда whos размер и используемую память.

Действие над векторами. В MATLAB выделяется две существенно различающиеся группы действий над векторами: векторные действия - такие, которые предусмотрены векторным исчислением в математике, и действия по преобразованию элементов векторов.

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

Ввод матриц. При вводе матриц необходимо соблюдать основные условия:

· отделять элементы строки пробелами или запятыми;

· использовать точку с запятой для обозначения окончания каждой строки, заключать весь список элементов квадратными скобками [];

· при обращении к элементам массива использовать круглые скобки ();

Матрицы в MATLAB можно вводить несколькими способами:

· вводить полный список элементов;

· загружать матрицы из внешних файлов;

· генерировать матрицы, используя встроенные функции;

· создавать матрицы с помощью ваших собственных функций в М - файлах.

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

Объединение. Объединение - это процесс соединения маленьких матриц для создания больших. Пара квадратных скобок - это оператор объединения.

Удаление строк и столбцов. Удалять строки столбцы матрицы можно, используя пару пустых квадратных скобок.

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

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

MATLAB предоставляет набор команд высокого уровня, которые используются для построения графиков. Это такие команды как plot, title, axis, text, hist, contour и ряд других. Команды высокоуровневой графики автоматически устанавливают свойства графических объектов и обеспечивают воспроизведение графики в нужных системах координат, палитре цветов и т.д.

MATLAB показывает графические объекты в специальных графических окнах, имеющих в заголовке слово Figure (фигура, изображение).

Для отображения нескольких графиков на одном рисунке существует два способа. Первым способом является использование команды hold on, которая замораживает текущий график, так что последующие кривые помещаются на этот же график [15]. Команда hold off приводит к тому, что любой последующий вызов команды plot создает новый рисунок на этом же листе, т.е. предыдущий график стирается. Того же самого результата можно добиться, используя функции plot с последовательностью аргументов: переменная x, первая функция, переменная x, вторая функция и т.д.

У такого способа есть еще одно преимущество: разные графики автоматически строятся разным цветом.

Если все же нужно одновременно визуализировать результаты, выводя каждый график отдельно, то это можно сделать также двумя способами. Первым способом является построение их в разных графических окнах. Для создания нового графического окна применяется команда figure.

Вторым решением показа нескольких графиков без конфликта диапазонов осей координат является использование функции subplot.

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

Функция fplot. Функция fplot предоставляет альтернативную возможность изображения функций по сравнению с вычислением вектора y по x и последующим изображением этой кривой с помощью функции plot. Этой функции необходимо передавать строку, описывающую требуемую функцию в виде f(x), может содержать любые допустимые в MATLAB операции и/или функции. Функция fplot имеет еще два дополнительных аргумента. Один из них - это строка, описывающая тип и цвет линии, а вторая - точность. По умолчанию точность равна, и она определяет, на какое количество точек делить интервал, чтобы погрешность от линейной интерполяции не превосходила этой заданной точности.

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

Визуализация постановки задачи в MATLAB решается применением приложения Notebook и назначением именам функций достаточно ясных имен (идентификаторов). А визуализация результатов вычислений достигается применением обширных средств графики, в том числе анимационной, а также использованием (там, где это нужно) средств символьной математики.

Новая версия MATLAB избавилась от некоторой примитивности графиков, которая была присуща первым версиям этой системы. Теперь новые графические средства Handle Graphics (дескрипторная или описательная графика) позволяют создавать полноценные объекты графики высокого разрешения, как геометрического, так и цветового. Возможности этой графики поддерживаются объектно-ориентированным программированием, средства которого также имеются в языке программирования системы MATLAB.

Реализуются, причем с повышенной скоростью, построения графиков практически всех известных в науке и технике типов. Широко практикуется функциональная закраска сложных поверхностей, в том числе с интерполяцией по цвету. Возможен учет всевозможных световых эффектов -- вплоть до бликов на поверхности сложных фигур при освещении их различными источниками света и с учетом свойств материалов отражающих поверхностей. Применение дескрипторной графики позволяет создавать и типовые элементы пользовательского интерфейса -- кнопки, меню, информационные и инструментальные панели и т. д., то есть реализовать элементы визуально-ориентированного программирования [16].

Графики выводятся отдельно от текстов в отдельных окнах. На одном графике можно представить множество кривых, отличающихся цветом (при цветном дисплее) и отличительными символами (кружками, крестиками, прямоугольниками и т. д.). Графики можно выводить в одно или в несколько окон. Наконец, в статьях и книгах формата Notebook, реализованных при совместной работе системы MATLAB с популярным текстовым процессором Microsoft Word 95/97/2000, графики могут располагаться вместе с текстом, формулами и результатами вычислений (числами, векторами и матрицами, таблицами и т. д.). В этом случае степень визуализации оказывается особенно высокой, поскольку документы класса Notebook по существу являются превосходно оформленными электронными книгами с действующими (вычисляемыми) примерами. Особенно привлекательной выглядит возможность построения трехмерных поверхностей и фигур. Если в MATLAB 4 рендеринг трехмерных фигур осуществлялся только при помощи фирменного механизма painters, а в MATLAB 5 был добавлен программный рендеринг при помощи Z-буфера, то в MATLAB б основным является индустриальный стандарт Open GL. Он может поддерживаться аппаратно графическими ускорителями. Система автоматически подбирает наиболее оптимальный механизм рендеринга. По сравнению с системой Mathcad построение трехмерных фигур средствами MATLAB происходит почти на порядок быстрее. Кроме того, при построении таких графиков используется достаточно совершенный алгоритм удаления невидимых линий, что наряду с большими размерами графиков и возможностью интерполяции по цвету делает построенные трехмерные поверхности и фигуры весьма эстетичными и наглядными. Фигуры могут быть прозрачными. Уже в ранних версиях была введена эффектная возможность быстрого вращения графиков в любом направлении. В MATLAB 5.3.1 и 6 она улучшена - теперь вращать в пространстве можно даже плоскость с двумерными графиками.

Трехмерные графики функций. Для отображения функции двух переменных следует:

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

2. Вычислить функцию в узлах сетки и записать полученные значения в матрицу.

3. Использовать одну из графических функций MATLAB.

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

Сетка генерируется при помощи команды meshgrid, вызываемой с двумя аргументами. Аргументами являются векторы, элементы которых соответствуют сетке на прямоугольной области построения функции. Можно использовать один аргумент, если область построения функции - квадрат. Для вычисления функции следует использовать поэлементные операции.

Для построения каркасной поверхности, используется функция mesh, вызываемая с тремя аргументами. Цвет линий поверхности соответствует значениям функции. MATLAB рисует только видимую часть поверхности. При помощи команды hidden off можно сделать каркасную поверхность “прозрачной”, добавив скрытую часть. Команда hidden on убирает невидимую часть поверхности, возвращая графику прежний вид [17].

Функция surf строит каркасную поверхность графика функции и заливает каждую клетку поверхности определенным цветом, зависящим от значения функции в точках, соответствующих углам клетки.

В пределах каждой клетки цвет постоянный. Команда shading flat позволяет убрать каркасные линии. Для получения поверхности, плавно залитой цветом, зависящим от значений функции, предназначена команда shading interp.

При помощи shading faceted можно вернуть к виду каркасной поверхности, залитой цветом. В MATLAB определена команда colorbar, которая выводит рядом с графиком столбик, устанавливающий соответствие между цветом и значением функции.

Команды meshc или surfc позволяют получить более точное представление о поведении функции. Эти команды строят каркасную поверхность и размещают на плоскости xy линии уровня функции.

MATLAB позволяет построить поверхность, состоящую из линий уровня, при помощи функции contour3. Эту функцию можно использовать так же, как и описанные выше функции mesh, surf, meshc и surf с тремя аргументами.

При этом число линий уровня выбирается автоматически. Имеется возможность задать четвертым аргументом в contour3 либо число линий уровня, либо вектор, элементы которого равны значениям функции, отображаемым в виде линий уровня. Задание вектора удобно, когда требуется исследовать поведение функции в некоторой области ее значений (срез функции).

Оформление графика. Простым, но эффективным способом изменения цветового оформления графика является установка цветовой палитры при помощи функции colormap. Для восстановления первоначального значения палитры следует применить команду colormap('default').

Построение освещенной поверхности. Для построения освещенной поверхности применяется функция .

При использовании удобно задавать цветовые палитры: , , , , в которых интенсивность цвета изменяется линейно. Для получения плавно изменяющихся оттенков следует использовать shading interp

Объединение графиков. Для объединения графиков предназначена команда hold on, которую можно задать перед построением следующего графика.

М-файлы. Файлы, которые содержат коды языка MATLAB, называются М-файлами. Процедура создания М-файла включает две операции:

· создание М-файла с использованием текстового редактора

· вызов М-файла из командной строки или из другого М-файла

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

Типы М-файлов. Существует два типа М-файлов: М-сценарии и М-функции со следующими характеристиками (Таблица 1):

Таблица 1. Характеристики М-сценария и М-функции

М-сценарий	М-функция
Не допускает входных и выходных аргументов	Допускает водные и выходные аргументы
Оперирует с данными из рабочей области	По умолчанию внутренние переменные являются локальными по отношению к функции
Предназначен для автоматизации последовательности шагов, которые нужно выполнять много раз	Предназначена для расширения возможностей языка MATLAB (библиотеки функции, пакеты прикладных программ)

Структура М-файла. М-файл, оформленный в виде функции, состоит из следующих компонентов:

· строки определения функции

· первой строки комментария

· комментария

· тела функции

Структура этой функции содержит компоненты, которые являются общими для любых функций системы MATLAB:

· строку определения функции - задает имя, количество и порядок следования водных и выходных аргументов;

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

Она выводится на экран с помощью команд lookfor или help<имя каталога>;

· комментарий - выводится на экран вместе с первой строкой при использовании команды help<имя функции>;

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

Типы переменных. Локальные и глобальные переменные. Использование переменных в М-файле ничем не отличается от использования переменных в командной строке, а именно:

· переменные не требуют объявления; прежде чем переменной присвоить значение, необходимо убедиться, что всем переменным в правой части присвоены значения;

· любая операция присваивания создает переменную, если это необходимо, или изменяет значение существующей переменной;

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

Обычно каждая М-функция, задаваемая в виде М-файла, имеет собственные локальные переменные, которые отличны от переменных других функций и переменных рабочей области. Если несколько функций и рабочая область объявляют некоторую переменную глобальной, то все они используют единственную копию этой переменной. Любое присваивание этой переменной распространяется на все функции, где она объявлена глобальной.

Для того чтобы переменная рабочей области была глобальной, необходимо объявить ее как глобальную из командной строки; в каждой функции использовать команду global перед первым появлением переменной, рекомендуется указывать команду global в начале М-файла [15].

Создание М-файлов. М-файлы являются обычными текстовыми файлами, которые создаются с помощью текстового редактора. Для операционной среды персонального компьютера система MATLAB поддерживает специальный встроенный редактор/отладчик, хотя можно использовать и любой другой текстовый редактор с ASCII-кодами [18].

Открыть редактор можно двумя способами:

· из меню File выбрать опцию New, а затем M-File;

· использовать команду редактирования edit<имя файла>.

М-сценарии. Сценарии являются самым простым типом М-файла - у них нет входных и выходных аргументов. Они полезны для выполнения автоматизации последовательности MATLAB-команд вычисления, которые должны были бы многократно вводиться из командной строки.

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

М-функции. Функции являются М-файлами, которые допускают наличие входных и выходных данных аргументов. Они работают с переменными в пределах собственной рабочей области, отличной от рабочей области системы MATLAB.

Структура М-функции. М-функция включает следующие компоненты:

· строки определения функции;

· первой строки комментария;

· собственно комментария;

· тела функции;

· строчных комментариев.

Имена М-функций. Имя файла, содержащего М-функцию, составляется из имени функции и расширения ''.m''.

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

Выполнение М-функций. М-функцию можно вызвать из командной строки системы MATLAB или из других М-файлов, обязательно указав все необходимые атрибуты - входные аргументы в круглых скобках, выходные аргументы в квадратных скобках.

Для вывода сообщений об ошибках используется оператор error(`Message').

Средства программирования в MATLAB. Многие математические системы создавались исходя из предположения, что пользователь будет решать свои задачи, практически не занимаясь программированием. Однако с самого начала было ясно, что подобный путь имеет недостатки и, вообще говоря, порочен. Ведь многие задачи нуждаются в развитых средствах программирования, которые упрощают запись алгоритмов задач и порой открывают новые методы создания алгоритмов. С одной стороны, MATLAB содержит огромное число операторов и функций, которые решают множество практических задач, для чего ранее приходилось готовить достаточно сложные программы. К примеру, это функции обращения или транспонирования матриц, вычисления значений производной или интеграла и т. д. Число таких функций с учетом пакетов расширения системы уже достигает многих тысяч и непрерывно увеличивается. Но, с другой стороны, система MATLAB с момента своего создания создавалась как мощный математико-ориентированный язык программирования высокого уровня. И многие рассматривали это как важное достоинство системы, свидетельствующее о возможности ее применения для решения новых, наиболее сложных математических задач [19].

Система MATLAB имеет входной язык, напоминающий Бейсик (с примесью Фортрана и Паскаля). Запись программ в системе традиционна и потому привычна для большинства пользователей компьютеров. К тому же система дает возможность редактировать программы с помощью любого привычного для пользователя текстового редактора. Имеет она и собственный редактор с отладчиком. Язык системы MATLAB в части программирования математических вычислений намного богаче любого универсального языка программирования высокого уровня. Он реализует почти все известные средства программирования, в том числе объектно-ориентированное и (средствами Simulink) визуальное программирование. Это дает опытным программистам необъятные возможности для самовыражения.

Управление потоками. MATLAB имеет пять видов структур управления потоками [20]:

· оператор if

· оператор switch

· циклы for

· циклы while

· оператор break

Операторы цикла for, while. Самое простое использование for осуществляется следующим образом:

for count = start:step:final

команды MATLAB

end

Здесь count - пременная цикла, start - ее начальное значение, final - конечное значение, а step - шаг, на который увеличивается count при каждом следующем заходе в цикл. Цикл заканчивается, как только значение count становится больше final. Переменная цикла может принимать не только целые, но и вещественные значения любого знака.

Использование оператора for.

for i=1:m

for j=1:n

H(i, j) = 1/(i+j-1);

end

end

H

По данному набору команд создается и выводится на экран матрица Гилберта размерности mЧn. Точка с запятой, которая завешает внутренний оператор, предотвращает вывод на экран ненужных промежуточных результатов, в то время как последний оператор H выводит на экран окончательный результат.

Цикл While. В общем виде цикл while записывается в виде

while <условие>

<операторы>

end

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

Использование оператора while

n=0;

while 2^n<a

n=n+1;

end

n

Условный оператор if. В общем виде простой оператор if используется следующим образом:

if <условие>

<операторы>

end

<операторы> будут выполняться, только если <условие> истинно. Возможно также множественное ветвление, что демонстрируется приведенным далее примером.

Использование оператора if

If n<0

parity=0;

elseif mod(n, 2)==0

parity=2;

else

parity=1;

end

parity

Оператор переключения switch…case. При необходимости построить конструкцию ветвления с более чем двумя логическими условиями удобнее использовать не вложенные операторы if, а оператор переключения switch…case. Этот оператор имеет следующую структуру:

switch <выражение>

case <значение 1>

операторы

case <значение 2>

операторы

…

otherwise

операторы

end

Условия (операторы отношения). В MATLAB используются следующие операторы отношения:

< меньше чем

> больше чем

<= меньше или равно

>= больше или равно

== равно

~= не равно

Отметим, что знак = используется в операторах присваивания, в то время как знак == используется в операторах отношения.

Когда эти операторы применяются к скалярам, то результатом является тоже скаляр 1 или 0 в зависимости от того, является ли результат истиной или ложью. Когда операторы отношения применяются к матрицам одинакового размера, результатом является матрица того же размера, у которой в качестве элементов стоят 0 или 1, в зависимости от соотношения между соответствующими элементами исходных матриц. Операторы while и if интерпретирует отношение между матрицами как истинное в том случае, если результирующая матрица не имеет нулевых элементов [16].

2. Решение задач оптимизации с применением пакетов прикладных программ

2.1 Решение задач оптимизации с применением MS Excel

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

Структура производственных моделей. Производственная математическая модель предназначена для формирования оптимального производственного плана или технологических операций при ограниченных временных, материальных, трудовых и производственных ресурсах [21]. Критерием оптимальности является получение максимума прибыли или минимума издержек. Само планирование состоит обычно в определении количества выпускаемой продукции или составляющих в пределах заданного ассортимента. Чтобы создать математическую модель производственной фирмы, надо определить следующие параметры:

* константы нормативных затрат материалов, труда и финансов;

* переменные решения;

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

* запас ресурсов или продукции;

* параметры спроса на продукцию.

Оптимизация модели производственного плана состоит в поиске максимума (для прибыли) или минимума (для затрат) целевой функции при ограничении на спрос и ресурсы [22]. При оптимизации раскроя листовых материалов возникают важные для технологов вопросы минимизации отходов. При составлении смесей часто требуется выполнить ограничение сверху и снизу концентрации составляющих компонент.

Математическое программирование занимается исследованием детерминированных и одноцелевых задач. Слово "программирование" в данном случае означает "планирование". К математическому программированию относится [23]:

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

2. Нелинейное программирование: целевая функция и ограничения могут быть нелинейными функциями.

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

4. Динамическое программирование: для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом.

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

Математическая модель любой задачи линейного программирования включает в себя:

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

- искомые переменные величины, например, количество запланированной к выпуску продукции по всему ассортименту;

- максимум или минимум целевой функции, например, запланированной прибыли;

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

- требование неотрицательности переменных (если не предусмотрено иное).

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

Рисунок 13. Схема моделирования

При решении "стандартной" задачи в линейном программировании нужно определить максимум линейной целевой функции

при условиях

Здесь целевая функция формируется как скалярное произведение двух векторов. Один из них -- вектор искомых переменных . Компонентами другого вектора являются целевые коэффициенты . Условия задачи можно сформулировать так: "Расход не должен превышать имеющиеся ресурсы ". Вектор расхода есть сумма произведений матрицы нормированных коэффициентов на вектор искомых переменных .

Основной аналитический метод решения задач линейного программирования -- это симплексный метод. Он сводится к вычислительной процедуре, основанной на принципе последовательного улучшения решений -- перехода от одной базисной точки к другой, для которой значение целевой функции больше. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов. Геометрическая интерпретация метода состоит в последовательном движении по вершинам симплекса (n-мерного тетраэдра). Симплекс-метод послужил исходным пунктом для разработки целого семейства алгоритмов решения как линейных, так и нелинейных выпуклых задач оптимизации.

Алгоритмы такого рода лежат в основе инструмента Поиск решения (Solver) в табличном процессоре MS Excel. Следовательно, решение многих экономических оптимизационных (линейных и нелинейных) задач можно существенно облегчить с помощью данного инструмента.

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

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

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

Обычными задачами, решаемыми с помощью надстройки Поиск решения, являются [24]:

- Ассортимент продукции. Максимизация выпуска товаров при ограничениях на сырье (или другие ресурсы) для производства изделий.

- Штатное расписание. Составление штатного расписания для достижения наилучших результатов при наименьших расходах.

- Планирование перевозок. Минимизация затрат на транспортировку.

- Составление смеси. Получение заданного качества смеси при наименьших расходах.

- Оптимальный раскрой материалов (ограничения -- количество деталей различной формы и размеров).

- Оптимизация финансовых показателей (например максимизация доходов за счет оптимизации средств на разные инвестиционные проекты).

Задачи, которые лучше всего решаются данным средством, имеют три свойства:

- имеется единственная максимизируемая или минимизируемая цель (доход, ресурсы и т.д.);

- имеются ограничения, выражающиеся, как правило, в виде неравенств (например, объем используемого сырья не может превышать объем имеющегося сырья на складе, или время работы станка за сутки не должно быть больше 24 часов минус время на обслуживание);

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

Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями:

- количество неизвестных - 200;

- количество формульных ограничений на неизвестные - 100;

- количество предельных условий ) на неизвестные - 400.

Ограничения в задачах. Под ограничениями понимаются соотношения типа А1>=В1, А1=А2, А3>=0, А1= целое.

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

Часто ограничения записываются сразу для групп ячеек, например: А1:А10<=В1:В10 или А1:Е1>0.

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

В одних случаях ограничения просты и очевидны, например ограничение на количество сырья. Другие типы ограничений менее очевидны и могут быть указаны неверно или, хуже того, могут оказаться пропущенными. Вот некоторые примеры ограничений такого типа:

1. в модели с несколькими периодами времени величина материального ресурса на начало следующего периода должна равняться величине этого ресурса на конец предыдущего периода;

2. в модели поставок величина запаса на начало периода плюс количество полученного должна равняться величине запаса на конец периода плюс количество отправленного;

3. многие величины в модели по своему физическому смыслу не могут быть отрицательными, например количество полученных единиц товара (это кажется естественным, однако, если не указать данные ограничения, Поиск решения вполне может предложить отрицательные значения в качестве обеспечивающих получение оптимального результата).

Рассмотрим применение инструмента Поиск решения на примере следующей экономической задачи.

Задача 1. Составление производственного плана.

Фабрика выпускает сумки: женские, мужские, дорожные. Данные о материалах, используемых для производства сумок и месячный запас сырья на складе приведены в таблице 2.

Таблица 2. Данные о материалах

Материалы	Нормы расхода	Месячный запас материалов
	Сумка женская	Сумка мужская	Сумка дорожная	Сумка спортивная
Кожа (м2)	0,5				75
Кожзаменитель (м2)		0,3	1,5	1,0	150
Подкладочная ткань (м2)	0,6	0,4	1,7	1,5	300
Нитки (м)	20	10	30	25	8000
Фурнитура-молния (шт.)	4	5	3	6	1500
Фурнитура-пряжки (шт.)	2	2	2	2	800
Фурнитура разная (шт.)	2	2	4	6	1000

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

· сумка женская -- 150 шт. при оптовой цене 3000 руб.;

· сумка мужская -- 70 шт. при оптовой цене 700 руб.;

· сумка дорожная -- 50 шт. при оптовой цене 2000 руб.;

· сумка спортивная -- 30 шт. при оптовой цене 1200 руб.

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

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

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

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

Ментальная карта должна проиллюстрировать основную формулу математической модели (рисунок 14):

Рисунок 15. Основная формула математической модели

Ментальную карту выполним в виде столбцов со списками данных (рисунок 16):

Рисунок 16. Представление исходных данных

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

В третьем столбце представлена матрица нормативных коэффициентов - удельных затрат материалов на каждый вид сумки. Индексы определяют один из четырех видов продукции и один из семи видов ресурсов.

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

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

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

Оптимальному решению задачи отвечает максимальное значение целевой функции при следующих условиях и ограничениях (таблица 3):

Таблица 3. Тестовая таблица

Выражение	Знак отношения	Ресурс	Примечание
		150	Выполнение договорных поставок	сумки женские
		70		сумки мужские
		50		сумки дорожные
		30		сумки спортивные
	Целые		Доли сумок не выпускаются
		75	Ограничение на расход материалов	кожа
		150		кожзаменитель
		300		подкладочная ткань
		8000		нитки
		1500		фурнитура-молнии
		800		фурнитура-пряжки
		1000		фурнитура-разная

Лишь после того, как мы разобрались в условиях задачи, можно приступить к формированию таблицы в MS Excel (рисунок 17). Заполним ячейки исходными данными. Искомые переменные (количество сумок каждого вида) поместим в ячейки строки 12. В ячейку F3 вставим формулу и протянем ее до ячейки F10. Целевая функция помещается в ячейке F10. Это выручка, т.е. стоимость всех произведенных сумок.

Рисунок 17. Вставка формул в таблицу MS Excel

Отформатированная таблица представлена на рисунке 18. В ячейки для искомых переменных В12:Е12 можно вставлять, вообще говоря, любые числа. Программа выполнит подбор их числовых значений в соответствии с условиями задачи. Однако чаще всего в качестве начальных значений вводят 0 (как на рисунке 18) или 1 (как на рисунке 19).

Рисунок 18. Сформированная таблица MS Excel

После вставки формул по команде Данные - Поиск решения вызовем диалог и заполним поля, как показано на рисунке 2.5. Адреса ячеек нужно не набирать вручную, а показывать мышью. Вызывать поля ограничений для записи нужно кнопкой "Добавить". На рисунке показано, что введены ограничения на целостность искомых переменных, на превышение выпуска продукции над обязательными поставками и на не превышение расхода материалов над запасами их на складе. Не отрицательность переменных учитывается в диалоге автоматически.

Рисунок 19. Заполнение диалога "Параметры поиска решения"

После выполнения команды "Найти решение" будет выдан результат расчета: значения искомых переменных и соответствующий расход материалов (рисунок 20):

Рисунок 20. Результаты поиска решения

Таким образом, мы нашли, что максимально возможная выручка может составить 677500 руб. Для этого сверх договорных поставок мы должны изготовить 35 мужских сумок и 9 дорожных сумок. При этом на складе останется около 10% запаса материалов, кроме кожи и кожзаменителя, которые будут израсходованы полностью. Для сохранения результата нужно нажать кнопку "Сохранить сценарий", в диалоге дать имя сценарию "Сумки_1".

Оптимизация математической модели фактически закончена. Но теперь нужно перейти обратно от модели к реальной ситуации, т.е. принять управленческое решение. А что будет, если не удастся реализовать сумки, изготовленные сверх потребности? Ясно, что выручка будет равна только сумме, перечисленной от покупателей по договорным обязательствам. Тогда, может быть, и не изготавливать излишнюю продукцию? А сколько при этом останется материалов на складе? Руководитель предприятия на основе данного анализа должен иметь возможность принять решение о создании запасов, как буферных (запас материалов для компенсации задержек в поставках), так и гарантийных (запас продукции для удовлетворения ожидаемого спроса).

Вернемся в диалоговое окно "Поиск решения". Изменим запись, приравняв в окне ограничений искомое количество продукции поставкам по договорам (рисунок 21):

Рисунок 21. Решение для обязательных поставок

Полученное решение оптимально -- оно отвечает максимуму целевой функции и удовлетворяет заданным ограничениям. Сохраним второй сценарий под именем "Сумки_2".

А теперь подготовим графические материалы для отчета по составлению производственного плана. Представим остатки материалов на складе в конце следующего месяца для двух вариантов плана: для максимальной выручки и только для обязательных поставок.

По команде на ленте "Данные" - Анализ "что если" - Диспетчер сценариев -- Отчет получим отчет по сценариям. Отредактируем отчет вручную по примеру, приведенному на рисунке 22:

Рисунок 22. Отредактированный отчет по двум сценариям остатков материалов

Задача 2. Цех алкидных красок с производительностью 450 тонн продукта в месяц способен производить три разновидности красок: белой, синей и красной. Согласно договорам цех должен изготовить 40 тонн белой, 60 тонн синей и 80 тонн красной красок за месяц. Избыток краски сверх этого количества поступает в свободную продажу. В качестве сырья для изготовления красок используются четыре мастики в различных соотношениях. Цех располагает следующими запасами мастики: первой -- 100 тонн, второй -- 150 тонн, третьей -- 120 тонн и четвертой -- 180 тонн. Данные о расходе мастики на производство одной тонны каждой разновидности краски сведены в таблицу 4.

Таблица 4. Данные о расходе мастики

Краски	Расход мастики на 1 тонну краски, т
	Мастика 1	Мастика 2	Мастика 3	Мастика 4
Белая	0,3	0,2	0,4	0,4
Синяя	0,2	0,1	0,3	0,6
Красная	0,2	0,5	0,2	0,3

Требуется найти оптимальное (в смысле максимизации прибыли) количество каждого вида изготавливаемых красок при условии, что стоимости красок равны: белой - 13500 руб. , синей -- 11300 руб. и красной 8200 руб. за тонну.

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

Решение. Таблица Excel формируется для этой задачи стандартным образом (рисунок 23):

Рисунок 23. Формирование таблицы данных

Неизвестные переменные помещаем в ячейки H3:H5, а целевую функцию - в ячейку G6. Ограничения вводим из условия задачи (рисунок 24):

Рисунок 24. Параметры поиска решений

Сохраним сценарий этого решения под именем "Краски_450". Далее во втором ограничении поставим знак "=" и сохраним сценарий под именем "Краски_180". По команде Данные - Анализ "что если" - Диспетчер сценариев - Отчеты - Структура выведем на лист отчет сценариев. Отредактированный отчет выглядит следующим образом (рисунок 25):

Рисунок 25. Отчет сценариев

Из отчета следует, что договорные поставки загружают мощности предприятия лишь на 40% и дают лишь 56,38% возможной выручки. При этом остаются невостребованными со склада запасы мастики, хранение которой также требует существенных расходов. По данным отчета построим гистограммы расхода мастики для двух вариантов производственного плана (рисунок 26):

Рисунок 26. Гистограмма расхода мастики

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

На примере рассмотренных экономических задач была продемонстрирована автоматизация их решения при помощи инструмента Поиск решения табличного процессора MS Excel.

2.2 Решение задач оптимизации с применением MATLAB

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

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

методы исследования функций классического анализа;

методы, основанные на использовании неопределенных множителей Лагранжа;

вариационное исчисление;

динамическое программирование;

принцип максимума;

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

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

В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.

Минимизация унимодальной функции одной переменной. Функция одного переменного называется унимодальной на отрезке , если имеется единственное значение такое, что [25], [26]:

· -минимум на ;

· строго убывает при ;

· строго возрастает при .

Для отыскания минимума унимодальной функции используется функция fminbnd. Алгоритм, реализованный ею, представляет собой комбинацию метода золотого сечения и обратной параболической интерполяции [27]. В простейшем варианте вызова кроме указателя на минимизируемую функцию fun задаются начало и конец интервала поиска: x=fminbnd(fun, a, b).

Пример 1. Использование функции fminbnd для поиска минимума функции humps (переводится как «горб»), входящей в ядро MATLAB. Данная функция задается формулой

Для построения ее графика следует выполнить команду

>>fplot (@humps, [0, 3])

Из рисунка 27 следует, что минимум функции humps существует на отрезке [0.5, 1].

Для нахождения минимума функции нужно выполнить команду

>> fminbnd (@humps, 0.5, 1)

ans =

0.63701067459059

Для одновременного нахождения минимума функции и значения функции в точке минимума следует использовать следующий синтаксис вызова функции fminbnd:

>> [x, y]= fminbnd(@humps, 0.5, 1)

x =

0.63701067459059

y =

11.25275412656431

Рисунок 27. График функции humps

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

[xmin, val, flag, output] = fminbnd (@humps, 0.5, 1)

где output - объект, содержащий полную информацию о процессе нахождения минимума функции. В частности, поле output.iterations содержит количество совершенных итераций. Для вывода на экран числа итераций выполнения функции fminbnd необходимо использовать следующий синтаксис обращения к данной функции:

>>[xmin, val, flag, output] = fminbnd (@humps, 0.5, 1)

x =

0.63701067459059

y =

11.25275412656431

flag =

1

output =

iterations: 7

funcCount: 8

algorithm: 'golden section search, parabolic interpolation'

message: [1x112 char]

Пример 2. График функции представлен на рисунке 28. На каждом из интервалов и эта функция унимодальна. Для нахождения ее минимумов на указанных интервалах и построения графика с выделением точек минимума составлена программа prog1.m:

function prog1

xx=-2:0.1:3; yy=fun(xx);

plot (xx, yy,'k-')

hold on; grid;

xlabel('x'); ylabel('y');

[x,f] = fminbnd(@fun,-2,0)

line(x,f, 'Marker', '.', 'MarkerSize', 20);

[x,f] = fminbnd(@fun,0,3)

line(x,f,'Marker', '.', 'MarkerSize', 20);

function y=fun(x)

y=3*x.^4-4*x.^3-12*x.^2;

Запуск этой программы выдает следующие результаты:

x=

-1.0000

f=

-5.0000

x=

2.0000

f=

-32.0000

Рисунок 28. Поиск минимума унимодальной функции

Многомерная безусловная минимизация. Задач поиска минимума вещественной функции векторного аргумента называется безусловной, если на ее аргумент не наложено никаких ограничений. В противном случае, когда вектор x должен удовлетворять каким-то уравнениям и/или неравенствам, говорят об условной минимизации [28].

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

Функция fminsearch. Для поиска минимума функции нескольких переменных применяется функция fminsearch:

fminsearch (hFunction, x0)

где hFunction - дескриптор функции нескольких переменных, для которой ищется минимум, x0 - вектор аргументов функции, с которого начинается поиск минимума.

В функции fminsearch используется так называемый алгоритм симплексного поиска, идея которого заключается в следующем. В окрестности стартовой точки n-мерного пространства строится симплекс - (n+1) точка в общем положении (никакие 3 точки не лежат на одной прямой, никакие 4 не лежат в одной плоскости и т. д.). Целевая функция измеряется в этих точках и та точка, в которой значение функции максимально, отбрасывается, а вместо нее в симплекс по определенным правилам вставляется другая точка. Процесс завершается, когда диаметр симплекса становится меньше заданного порога. Целевая функция может быть негладкой и даже разрывной [29]. Использование данной функции продемонстрировано в следующем примере.

Пример 3. Найти минимум функции

>> f2 = inline ('x(1)^2+x(2)^2', 'x')

f2 =

Inline function:

f2(x) = x(1)^2+x(2)^2

>> xmin = fminsearch(f2, [1 1])

xmin =

1.0e-004 *

-0.21023529262365 0.25484564932795

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

[xmin, val, flag, output] = fminsearch(hFun, x0)

где output - объект, содержащий полную информацию о процессе нахождения минимума функции. В частности, поле output.iterations содержит количество совершенных итераций. Для вывода на экран числа итераций выполнения функции fminsearch необходимо использовать следующий синтаксис обращения к данной функции:

>> [xmin, val, flag, output] = fminsearch(f2, [1 1])

xmin =

1.0e-004 *

-0.21023529262365 0.25484564932795

val =

1.0915e-009

flag =

1

output =

iterations: 38

funcCount: 69

algorithm: 'Nelder-Mead simplex direct search'

message: [1x196 char]

Замечание. Для функции нескольких переменных еще важнее, чем для рассмотренных ранее функций одной переменной, постараться априорно оценить количество и приблизительное нахождение локальных минимумов. Здесь могут существенно помочь трехмерные графики, способы построения которых были рассмотрены в параграфе 1.3 данной работы.

Банан Розенброка. Графически он представляет собой овраг с очень крутыми склонами, дно которого при «взгляде сверху» имеет форму параболы (рисунок 29) и плавно спускается к точке минимума x=[1;1], которой z=0. Ее линии уровня представляют собой изогнутые овалы (отсюда «банан»).

function f = Rosenbrock(x)

f=5*(x(2)-x(1)^2)^2+(1-x(1))^2

Рисунок 29. Минимизация функции Розенброка

Для поиска минимума и построения линий уровня функции Розенброка была написана программа prog2.m (см. Приложение 2).

Найденный минимум:

x=

1.0000

1.0000

f=

1.8161e-009

Функция fminunc. В том случае, когда функция fun(x) является достаточно гладкой, для поиска ее минимума можно воспользоваться функцией fminunc. Идея поиска минимума с помощью производных принадлежит Коши и заключается в следующем: градиент функции fun(x) в любой точке x есть вектор g, направленный в сторону наибольшего локального увеличения функции fun(x). Следовательно, для достижения минимума надо двигаться в направлении наискорейшего спуска - g. В более развитом варианте этого алгоритма используются также вторые производные, которые образуют так называемую матрицу Гессе (гессиан) H. При помощи формулы Тейлора строится локальная квадратичная аппроксимация целевой функции в окрестности текущей точки :

.

Минимум выражения в правой части (если он существует) достигается при векторе смещения , который удовлетворяет системе уравнений . Такой способ выбора направления называется методом Ньютона [30]. Иногда на вектор смещения накладывается ограничение при специально подобранном - в этом случае говорят о методе доверительного интервала.