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

Министерство образования и науки Российской Федерации

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

«Пермский национальный исследовательский политехнический университет»

Лысьвенский филиал

 

Факультет высшего профессионального образования

кафедра Естественнонаучных дисциплин

 

 

 

 

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

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

по теме: «Об аналитическом применении метода идеальной точки для решения многоцелевой задачи линейного программирования»

 

 

 

 

Выполнил 

Студент группы Вивт - 08:      Торощина Н.В.

 

Проверил

преподаватель:         Мухаметьянов  И.Т.

 

 

 

 

 

Лысьва, 2012

 

Содержание

 

Введение 3

1 Общая постановка многоцелевой задачи линейного программирования 5

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

3 ЕЩЕ ОДИН АНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ МНОГОЦЕЛЕВОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ …………………...16

Заключение 25

Список использованных источников 26

 

 

Введение

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

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

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

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

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

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

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

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

Исходя из цели работы, можно поставить следующие задачи:

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

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

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

Курсовая работа состоит из введения, 3 частей, трех рисунков, заключения и списка использованной литературы.

 

 

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

 

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

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

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

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

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

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

• целевые функции:

…

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

• требование неотрицательности переменных:

xj ≥ 0,

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

 

 

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

 

 

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

 
                         

Многоцелевая задача линейного программирования  тогда примет вид:

  

       

Требуется найти такое решение, , которое будет наиболее близким к экстремумам всех целевых функций.

Предположим, что  X ограниченное замкнутое множество, тогда все задачи имеют решения.  Полученную точку назовем идеальной, так как ни по одному критерию нельзя получить большее значение.  Идеальной точкой для множества X будет точка a=(a1, a2,…, am), в которой Обычно точка a не принадлежит множеству Х. Введем, понятие расстояния  между двумя точками r(a,b) в пространстве Rm:

                           

При s=1 получаем

При s=2  имеем, обычное евклидово расстояние

И наконец, при s=Ґ получим равномерную метрику

Теперь решение многокритериальной задачи можно свести  к решению обычной однокритериальной задачи оптимизации

                                                        (1)

Введем некоторые понятия. Идеальная точка является эффективным решением, которое нельзя улучшить по какому-либо из критериев, не ухудшив при этом значения других критериев. Множество эффективных решений называется множеством Парето и обозначается  P(D). Очевидно, множество Парето является подмножеством множества допустимых решений, которое, в свою очередь принадлежит n-мерному векторному пространству, т.е. P(D)   D  En.   

 

Связь между решениями задачи (1) и эффективными точками устанавливает следующее утверждение.

Утверждение1. Для всякого sО[1,Ґ),  любое решение задачи (1) является эффективной точкой, то есть множество оптимальных решений задачи (1), вложено во множество Парето.

Утверждение 2. Если множество  F выпукло, то множество оптимальных решений задачи (1) состоит из одной точки, и эта точка из множества Парето.

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

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

Для этого производятся следующие действия. Строится область допустимых решений - рисунок 1, ее отражение - рисунок 2. Находится ближайшая к «точке утопии» грань отражения области допустимых решений. Из уравнения грани выписывается уравнение координат точек грани в общем виде, составляется уравнение расстояния между «точкой утопии» и точками грани. Далее это расстояние минимизируется. На минимальном расстоянии от «точки утопии»  находится искомая идеальная точка - рисунок 3.

 

 

 

 

 

 

Рисунок 1 - Определение области допустимых решений

 

Рисунок 2. Определение отображения области допустимых решений

Рисунок 3 - Определение «точки утопии» и «идеальной точки»

«Идеальная точка» имеет координаты I(4,7; 4,8).

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

При метрике s=2 необходимо решить задачу следующего вида: . Здесь - это точка, в которой все целевые функции достигают своего истинного условного экстремума , а ее можно найти, решив исходную задачу для каждой целевой функции в отдельности.

      Аналитически, метод идеальной точки также предполагает последовательное выполнение ряда шагов. Рассмотрим на примере простой задачи. Сначала составим математическую модель. Используем метрику s=2.

Аналитически нужно решить задачу для каждой целевой функции отдельно.

Помножим 1-e неравенство на -1. Введем дополнительные переменные X3, X4, X5, X6.  
F(X)=2X1+1X2 (max) 
Ограничения:

-1X1	-	1X2	+X3	=	-1
4X1	+	8X2	+X4	=	32
1X1	+	1X2	+X5	=	4
1X1	-	2X2	+X6	=	3

 

Составим симплекс таблицу:

Базисные  переменные	Свободные  члены	X1	X2
X3	-1	-1	-1
X4	32	4	8
X5	4	1	1
X6	3	1	-2
F	0	-2	-1

 

Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член (-1). Ведущая строка - X3. В строке X3 так же найдем максимальный по модулю отрицательный свободный член (-1). Столбец X1- ведущий.

Пересчитаем таблицу

Базисные  переменные	Свободные  члены	X3	X2
X1	1	-1	1
X4	28	4	4
X5	3	1	0
X6	2	1	-3
F	2	-2	1