Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего образования

«Дальневосточный федеральный университет»

ШКОЛА ЕСТЕСТВЕННЫХ НАУК

Кафедра информационных систем управления

Омельяненко Михаил Владимирович

КУРСОВАЯ РАБОТА

РЕШЕНИЕ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОГО ПРОГРАММИРОВАНИЯ МЕТОД ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК

г. Владивосток 2016 г



Оглавление

Введение

1. Исследование предметной области

1.1 Линейное программирование

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

1.3 Многокритериальная оптимизация

2. Методы решения задачи многокритериальной оптимизации

2.1 Метод последовательных уступок

3. Реализация алгоритма

3.1 Описание алгоритма программы

3.2 Реализация в среде MatLab

3.3 Системные требования

3.4 Руководство пользователя

3.5 Тестирование алгоритма и решение тестового примера

Заключение

Список литературы

Приложение



Введение

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

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

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

Для достижения цели курсовой работы были поставлены следующие задачи:

· изучить метод последовательных уступок для решения многокритериальных ЗЛП;

· построить математическую модель для решения данным методом;

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

· выполнить решение задачи вручную и машинным способом;

· проанализировать полученные результаты и сделать вывод.



1. Исследование предметной области

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

1.1 Линейное программирование

Оптимизация в любой области науки, а также любой деятельности человека - её неотъемлемая часть. Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

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

1) рационального использования сырья и материалов, задачи оптимизации раскроя;

2) оптимизации производственной программы предприятий;

3) оптимального размещения и концентрации производства;

4) составления оптимального плана перевозок, работы транспорта;

5) управления производственными запасами и многие другие, принадлежащие сфере оптимального планирования

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

Основная задача линейного программирования выглядит следующим образом. Дана система из m линейных уравнений с n неизвестными:

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

и линейная функция от тех же переменных

которая называется целевой функцией (ЦФ).

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

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

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

1.3 Многокритериальная оптимизация

Задачи многокритериальной оптимизации возникают в тех случаях, когда имеется несколько целей, которые не могут быть отражены одним критерием. Лица, принимающие решения (ЛПР), нуждаются в необходимости оценки альтернативных решений с точки зрения нескольких критериев. Так, часто встречающееся выражение «достичь максимального эффекта при наименьших затратах» уже означает принятие решения при двух критериях. Оценка деятельности предприятий и планирования как системы принятия решений производится на основе более десятка критериев: выполнение плана производства по объему, по номенклатуре, плана реализации, прибыли по показателям рентабельности, производительности труда и т.д. Требуется найти точку области допустимых решений, которая минимизирует или максимизирует все эти критерии.

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

1. Разработка концепции оптимальности;

2. Доказательство существования решения, оптимального в соответствующем смысле;

3. Разработка методов нахождения оптимального решения.

Обозначим i-й частный критерий через fi (x), а область допустимых решений через Q. Учтем, что изменением знака функции всегда можно свести задачу минимизации к задаче максимизации, и наоборот, мы можем сформулировать кратко задачу векторной оптимизации следующим образом:

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

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

2. Методы решения задачи многокритериальной оптимизации

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

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

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

2.1 Метод последовательных уступок

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

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

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

Пример решения задачи

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

Уступка по первому критерию , а по второму .

Найти оптимальное решение задачи. Приступим к решению.

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

Оптимальный план такой:

Итак, мы максимизировали первую целевую функцию.

Далее переходим к решению задачи при ограничениях задачи, к которым добавлено новое ограничение . При: и получаем:

Выполним минимизацию функции F2 .

Оптимальный план:

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

Получаем следующие ограничения:

Найдем оптимальное решение для целевой функции F3. Полученный оптимальный план для F3:

Результат решения всей задачи таков:

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



3. Реализация алгоритма

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

3.1 Описание алгоритма программы

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

На вход программе подаются следующие значения:

· Количество переменных задачи;

· Количество ограничений задачи;

· Количество целевых функций;

· Вектор уступок;

· Матрица коэффициентов при переменных целевых функций;

· Вектор направлений ЦФ;

· Матрица коэффициентов при переменных ограничений;

· Вектор знаков ограничений;

· Вектор свободных коэффициентов ограничений.

На выходе, в качестве решения задачи получаем:

· Значения переменных оптимального решения;

· Значения ЦФ оптимального решения с учетом уступки;

· Окончательный ответ.

3.2 Реализация в среде MatLab

Алгоритм был реализован в виде консольного приложения. Ввод данных пользователем производится в командной строке среды. Программа реализована как скрипт.

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

· FN - количество переменных

· FM - количество ограничений

· FF - количество целевых функций

· US - вектор уступок для целевых функций

· AF - матрица коэффициентов целевых функций

· GF - вектор направлений целевых функций

· OG - матрица коэффициентов ограничений

· SO - вектор знаков при ограничениях

· OF - вектор свободных коэффициентов при ограничениях

Далее введенные данные приводятся к общему виду для обработки специальной функцией linprog.

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

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



3.3 Системные требования

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

· Среда MatLab (создание и отладка алгоритма выполнялись в версии R2014a)

· Процессор: Любой процессор Intel или AMD x86-64.

· Память на жестком диске: 2 ГБ для MATLAB

· Оперативная память: 2 Гб

· Видеоадаптер: не требуется специальных графических карт.

3.4 Руководство пользователя

Для работы с алгоритмом необходимо:

· Запустить среду MatLab

· Открыть файл kurs1.m

· Для запуска работы алгоритма необходимо нажать Run

· Программа начнет выполнение

· В командной строке вводятся данные задачи:

- Коэффициенты ЦФ (целевые функции вводятся в порядке убывания приоритета) - вводятся через пробел. В случае, если переменная отсутствует, вводится 0. По окончании ввода нажать Enter. На экране отобразится информация для дальнейшего ввода.

- Направление ЦФ (max или min). Далее Enter.

- Значение уступки для ЦФ (в процентах). Далее Enter.

- Коэффициенты при ограничениях. Вводятся через пробел. В случае, если в ограничении отсутствует переменная, вводится 0.

- Знак при ограничении (>=, <=, =). Далее Enter

- Свободный коэффициент при ограничении. Далее Enter.

· По окончании ввода программа выдаст решение.

3.5 Тестирование алгоритма и решение тестового примера

Протестируем работу алгоритма, решив задачу, рассмотренную в качестве примера в подпункте 2.1.1.

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

Рисунок 1 - Ввод условий задачи: целевых функций, уступок и ограничений

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

Рисунок 2 - Оптимальное решение задачи



Таким образом в результате работы программы были получены следующие результаты:

,

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



Заключение

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

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

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



Список литературы

1. Аттетков А.В. Методы оптимизации: Учеб. для вузов / Аттетков А.В., Галкин С.В., Зарубин В.С; под ред. В.С. Зарубина, А.П. Крищенко [2-е изд.]. - МГТУ им. Н.Э. Баумана, 2003. - 440с.

2. Землянухина Л.Н. Линейное программирование и смежные вопросы. Часть 4. Методические указания / Землянухина Л.Н., Зинченко А.Б., Сантылова Л.И. - Ростов-на-Дону: РГУ, 1998. - 36с.

3. Карманов В.Г. Математическое программирование: Учеб. пособие. / Карманов В.Г. [5-е изд.]. - М.: ФИЗМАТЛИТ, 2004. - 264с.

4. Лотов В.А. Многокритериальные задачи принятия решений: учебное пособие / В.А. Лотов, И.И. Поспелова - М.: МАКС Пресс, 2008. - 197с.

5. Пантелеев А.В. Методы оптимизации. Практический курс / А.В. Пантелеев, Т.А. Летова. - М.: Логос, 2011. - 110с.

6. Соболь И.М. Выбор оптимальных параметров в задачах со многими критериями / И.М. Соболь, Р.Б. Статников. - М.: Дрофа, 2006. - 176с.

7. Струченков В.И. Методы оптимизации / Струченков В.И. - М.: Экзамен, 2005. - 256с.

8. Таха, Хемди А. Введение в исследование операций / Таха, Хемди А.; пер. с англ. - М.: Издательский дом «Вильямс», 2001. - 912с.

9. Черноруцкий И.Г. Методы оптимизации и принятия решений / Черноруцкий И.Г. - СПб.: Лань, 2001. - 384с.

10. Штойер Р. Многокритериальная оптимизация / Штойер Р.: пер. с англ. - М.: Радио и связь, 1992. - 504с. - (Теория, вычисления и приложения).



Приложение

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

clear all

FN = input('Введите количество переменных: ');

FM = input('Введите количество ограничений: ');

FF = input('Введите количество ЦФ: ');

AF = [];%Массив ЦФ

GF = [];%Массив max/min

US = [];%Массив уступок

M = 'max';

for i=1:FF

if i==1

s = input('Введите коэффициенты при ЦФ: ','s');

AF = str2num(s);

s = input('Направление данной ЦФ: ','s');

if strcmp(s,'max')

GF = 1;

else

GF = 0;

end

s = input('Введите уступку для данной ЦФ, (%): ','s');

US = str2num(s);

else

s = input('Введите коэффициенты следующей ЦФ: ','s');

AF = [AF;str2num(s)];

s = input('Направление данной ЦФ: ','s');

if strcmp(s,'max')

GF = [GF;1];

else

GF = [GF;0];

end

if i~=FF

s = input('Введите уступку для данной ЦФ, (%): ','s');

US = [US;str2num(s)];

end

end

end

OG=[];%Массив ограничений

SO=[];%Знаки при ограничениях

OF=[];%Свободные коэффициенты ограничений

for i=1:FM

if i==1

s = input('Введите коэффициенты ограничения: ','s');

OG = str2num(s);

s = input('Введите знак ограничения: ','s');

if strcmp(s,'>=')

SO = 1;

else

SO = 0;

end

s = input('Введите свободный коэфф. ограничения: ','s');

OF = str2num(s);

else

s = input('Введите следующее ограничение: ','s');

OG = [OG;str2num(s)];

s = input('Введите знак ограничения: ','s');

if strcmp(s,'>=')

SO = [SO;1];

else

SO = [SO;0];

end

s = input('Введите свободный коэфф. ограничения: ','s');

OF = [OF;str2num(s)];

end

end

%Приведение к стандартному виду MatLab

for i=1:FF

if GF(i)==1

for j=1:FN

AF(i,j)=-AF(i,j);

end

end

end

for i=1:FM

if SO(i)==1

for j=1:FN

OG(i,j)=-OG(i,j);

end

OF(i)=-OF(i);

end

end

FS=[];%Массив решений

tAF = zeros(1,FN); %Текущая ЦФ

for i=1:FF

for j=1:FN

tAF(1,j)=AF(i,j);

end

lb = zeros(FN,1);

options=optimset('LargeScale', 'off','Simplex','on');

[x,fval]=linprog(tAF,OG,OF,[],[],lb,[],[],options);

if i==1

FS = abs(fval);

else

FS = [FS,abs(fval)];

end

if i~=FF

if GF(i)==1

OF = [OF;-(FS(i)-FS(i)*US(i)/100)];

else

OF = [OF;FS(i)+FS(i)*US(i)/100];

end

OG = [OG;tAF];

end

end

fprintf('РЕШЕНИЕ ЗАДАЧИ: \n');

for i=1:FF

fprintf('Решение F%d = %f\n', i,FS(i));

if i~=FF

fprintf('Уступка %d = %f\n', i,FS(i)*US(i)/100);

end

end

fprintf('\nОптимальное решение при\n');

for i=1:FN

fprintf('x%d = %f;\n',i,x(i));

end

fprintf('\n')

for i=1:FF

for j=1:FN

tAF(1,j)=AF(i,j);

end

fprintf('F%d = %f\n',i,abs(tAF*x));

end

Размещено на Allbest.ru

...