Новости Словари Конкурсы Бесплатные SMS Знакомства Подари звезду
В нашей
базе уже
59876
рефератов!
Логин

Пароль

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

Решение многокритериальной задачи линейного програмирования.
Решение многокритериальной задачи линейного програмирования
СодержаниеВведение1. Общая постановка многокритериальной задачи линейного программирования.1.1. Формальная постановка многокритериальной задачи линейного программирования.1.2. Условие задачи2. Решение многокритериальной задачи линейного программирования графическим методом2.1. Формальное условие и сведение к ЗЛП2.2. Графическое определение 2-множества3. Определение Парето-оптимального множества с-методом3.1. Удаление пассивных ограничений3.2. Определение 3-множества с-методом 4. Определение альтернативных вариантов многокритериальной задачи4.1. Метод гарантированного результата4.2. Метод линейной свертки частных критериев5. Составление сводной таблицыЗаключениеСписок литературыВведениеЛишь в редких случаях цели, которые лицо принимающее решение (ЛПР) стремится достичь в планируемой им операции, удается описать с помощью одного количественного показателя. Поэтому специалисты Системного анализа и Исследования операций считают целесообразным избегать термина «оптимизация», так как поиск оптимального решения х, доставляющего функции F(x) экстремальное значение, имеет вполне определенный смысл и давно входит в арсенал основных понятий математики. Многообразие целей ЛПР более адекватно может быть описано с помощью некоторой совокупности частных критериев (ч-критериев), характеризующих степень достижения частных целей. Противоречивый характер целей обуславливает, как правило, и противоречивость ч-критериев. С формальной точки зрения это приводит к тому, что свои экстремальные значения ч-критерии получают в различных точках ОДР Dx. Следовательно, ЛПР принимая решение х, всегда должно идти на компромисс, в разумных пределах допуская ухудшение значений одних ч-критериев во имя улучшения значений других. Именно этот этап творческой деятельности ЛПР наименее формализуем и требует привлечения предыдущего опыта, интуиции и даже искусства ЛПР, обладающего практическим опытом в соответствующей предметной области. Решение, принимаемое ЛПР с привлечением совокупности ч-критериев, будем называть компромиссным, рациональным или просто решением ЛПР, избегая при этом термина «оптимальный», имеющего определенный и вполне точный смысл.Основная идея обоснования и принятия решения ЛПР в условиях многокритериальности состоит в последовательном сужении ОДР Dx до минимальных размеров, что облегчает принятие окончательного решения ЛПР. Первым, наиболее существенным шагом в этом направлении будет являться сужение ОДР Dx до некоторого подмножества DxxDx на основании принципа доминирования.1.Общая постановка многокритериальной задачи линейного программирования.1.1.Формальная постановка многокритериальной задачи линейного программирования.Формальная схема многокритериальной ЗЛП (МЗЛП) от обычной ЗЛП отличается наличием нескольких целевых функций:где гi – неотрицательные переменные (невязки, i = 1; m).Знак max означает тот факт, что желательно увеличение каждой из линейных форм Lr(х), отражающей некоторую r-ю цель ЛРП.Требование только максимизации не сужает общности задачи. Так, например, требование минимизации затрат некоторых ресурсов эквивалентно требованию максимизации остатка от изначально выделенных ресурсов. Наличиемногих ч-критериев позволяет сделать модель (1) – (3) более адекватной изучаемой ситуации, однако выводит её из класса задач МП и требует разработки новых способов ее анализа. Начальный анализ МЗЛП состоит в удалении из области допустимых решений (ОДР) Dх явно худших, доминируемых решений х. Решение х, доминирует решение х (х, > х), если при х, хотя бы один ч-критерий имеет больше значение при равенстве остальных. Поэтому решение х может быть исключено из дальнейшего рассмотрения, как явно худшее, чем х,. Если решение х, не доминируется ни одним из решений хDx, то его называют Паретто-оптимальным (а - оптимальным) или эффективным решением ( - решением). Таким образом, .-решение - это неулучшаемое (недоминируемое) решение, и ясно, что решение ЛПР должно обладать этим свойством – другие решения нет смысла рассматривать.Формальное определение о-оптимальности решения х, записывается как требование об отсутствии такого решения х Dx, при котором бы были выполнены условияи хотя бы одно из них – строго (со знаком >).Иными словами, условия (4) выражают требование невозможности улучшения решения х, в пределах ОДР Dx ни по одному ч-критерию без ухудшения хотя бы по одному из других.1.2.Условие задачиДаны целевые функции:L1 = -x1 + 2x2 + 2,L2 = x1 + x2 + 4,L3 = x1 - 4x2 + 20,и система ограничений:x1 + x215,5x1 + x21,-x1 + x25,x220,xj0.2. Решение многокритериальной задачи линейного программирования графическим методом.2.1.Формальное условие и сведение к ЗЛПЧтобы можно было проверить условие (4) (Lr(x) ) Lr(x’),’r) для некоторой произвольно взятой точки х,, не прибегая к попарному сравнению с другими, условие ,-оптимальности (4) переформулируем в виде следующей задачи линейного программирования:Смысл задачи линейного программирования нетруднопонять, если учесть, что Сr – это приращение ч-критерия Lr, получаемое при смещении решения х, в точку х. Тогда, если после решения ЗЛП окажетсяmax = 0, то это будет означать, что ни один из ч-критериев нельзя увеличить ( max = 0), если не допускать уменьшения любого из других (r0). Но это и есть условие-оптимальности х,. Если же при решении окажется, что .0, то значит какой-то ч-критерий увеличил свое значение без ухудшения значений других(( r0), и значит х,DDx. Теперь перейдем к решению нашей задачи:L1 = -x1 + 2x2 + 2,L2 = x1 + x2 + 4,L3 = x1 - 4x2 + 20,x1 + x215,5x1 + x21,-x1 + x25,x220,xj0.Проверим некоторую точку х, = (5; 3) (эта точка принадлежит области Dx) на предмет )-оптимальности:Запишем ЗЛП в каноническом виде:1 = x1 - 2x2 + 1Dxk 2 = x1 + x2 - 83 = -x1 + 4x2 - 7= x1 + 3x2 – 14,1 = 15 - x1 - x22 = 5x1 + x2 – 1,Dx3 = 5 + x1 - x24 = 20 - x2xj0.и в форме с-таблицы:Т1 х1 х2 1?1 -1 -1 16?2 5 1 -4?3 1 -1 100?40 -1 10?1 1 -2 -4?2 1 1 -12?3 -1 1 -8? 1 4 -24Применяя с-метод, после замены П3х2, получаем:Т2 х1 ?1 1?1 -3/2 ? 29/2?2 11/2 -1/2 -1/2?3 1/2 ? 9/2?4 -1/2 ? 39/2X2 1/2 -1/2 1/2?2 3/2 -1/2 -15/2?3 1 -2 -5? 5/2 -3/2 -25/2Видим, что опорный план не получен, следовательно делаем еще одну замену: ?1 ? х1:Т3 ?3 ?1 1x1 29/3?2 316/6?3 56/6?4 88/6x2 16/3?2 7?3 14/3? -5/3 -2/3 70/6В Т3 получен опорный план. Так как при этом>0, то, следовательно, система ч-критериев не противоречива и существует некоторая облас
Умар.Ш. был тут !!!!!
 
давайте изгоним мат !!!
 
ДОБРОЙ НОЧИ ОТ Ъ
ЛОКИ ИНО
 
ДМК МЭ
 
где инфааа?