Министерство общего и профессионального образования РФ
ТГТУ
Кафедра ИС
Курсовая работа по дисциплине
Теория оптимального управления ЭС
Выполнил: студент группы ИСЭ-32 Чернецов Д.Е.
Принял: д.т.н. профессор
Берзин Е.А.
Тверь
2000 год
Содержание
Введение
1. Общая постановка многокритериальной задачи линейного программирования.
1.1. Формальная постановка многокритериальной задачи линейного программирования.
1.2. Условие задачи
2. Решение многокритериальной задачи линейного программирования графическим методом
2.1. Формальное условие и сведение к ЗЛП
2.2. Графическое определениеp-множества
3. Определение Парето-оптимального множества с-методом
3.1. Удаление пассивных ограничений
3.2. Определениеp-множества с-методом
4. Определение альтернативных вариантов многокритериальной задачи
4.1. Метод гарантированного результата
4.2. Метод линейной свертки частных критериев
5. Составление сводной таблицы
Заключение
Список литературы
Введение
Лишь в редких случаях цели, которые лицо принимающее решение (ЛПР) стремится достичь в планируемой им операции, удается описать с помощью одного количественного показателя. Поэтому специалисты Системного анализа и Исследования операций считают целесообразным избегать термина «оптимизация», так как поиск оптимального решения х, доставляющего функции F(x) экстремальное значение, имеет вполне определенный смысл и давно входит в арсенал основных понятий математики. Многообразие целей ЛПР более адекватно может быть описано с помощью некоторой совокупности частных критериев (ч-критериев), характеризующих степень достижения частных целей. Противоречивый характер целей обуславливает, как правило, и противоречивость ч-критериев. С формальной точки зрения это приводит к тому, что свои экстремальные значения ч-критерии получают в различных точках ОДР Dx. Следовательно, ЛПР принимая решение х,всегда должно идти на компромисс, в разумных пределах допуская ухудшение значений одних ч-критериев во имя улучшения значений других. Именно этот этап творческой деятельности ЛПР наименее формализуем и требует привлечения предыдущего опыта, интуиции и даже искусства ЛПР, обладающего практическим опытом в соответствующей предметной области. Решение, принимаемое ЛПР с привлечением совокупности ч-критериев, будем называтькомпромиссным,рациональнымили просто решением ЛПР, избегая при этом термина «оптимальный», имеющего определенный и вполне точный смысл.
Основная идея обоснования и принятия решения ЛПР в условиях многокритериальности состоит впоследовательном сужении ОДР Dxдо минимальных размеров, что облегчает принятие окончательного решения ЛПР.Первым, наиболее существенным шагом в этом направлении будет являться сужение ОДР Dxдо некоторого подмножества DxpМDxна основании принципадоминирования.
1.Общая постановка многокритериальной задачи линейного программирования.
1.1.Формальная постановка многокритериальной задачи линейного программирования.
Формальная схема многокритериальной ЗЛП (МЗЛП) от обычной ЗЛП отличается наличием нескольких целевых функций:
гдеei– неотрицательные переменные (невязки, i = 1; m).
Знак max означает тот факт, чтожелательно увеличение каждой из линейных форм Lr(х),отражающей некоторую r-ю цель ЛРП.
Требование только максимизации не сужает общности задачи. Так, например, требованиеминимизации затрат некоторых ресурсовэквивалентно требованиюмаксимизации остаткаот изначально выделенных ресурсов. Наличие многих ч-критериев позволяет сделать модель (1) – (3) более адекватной изучаемой ситуации, однако выводит её из класса задач МП и требует разработки новых способов ее анализа. Начальный анализ МЗЛП состоит в удалении из области допустимых решений (ОДР) Dх явно худших, доминируемых решений х. Решение х, доминирует решение х (х, > х), если при х, хотя бы один ч-критерий имеет больше значение при равенстве остальных. Поэтому решение х может быть исключено из дальнейшего рассмотрения, как явно худшее, чем х,. Если решение х, не доминируется ни одним из решений хОDx, то его называютПаретто-оптимальным (p- оптимальным)илиэффективным решением (p- решением). Таким образом,p-решение - это неулучшаемое (недоминируемое) решение, и ясно, что решение ЛПР должно обладать этим свойством – другие решения нет смысла рассматривать.
Формальноеопределениеp-оптимальности решения х,записывается как требованиеоб отсутствиитакого решенияхОDx,при котором бы были выполненыусловия
и хотя бы одно из них – строго (со знаком >).
Иными словами, условия (4) выражаюттребование невозможности улучшения решения х,в пределах ОДР Dxни по одному ч-критерию без ухудшения хотя бы по одному из других.
1.2.Условие задачи
Даны целевые функции:
L1= -x1+ 2x2+ 2,
L2= x1+ x2+ 4,
L3= x1- 4x2+ 20,
и система ограничений:
x1+ x2Ј15,
5x1+ x2і1,
-x1+ x2Ј5,
x2Ј20,
"xjі0.
2. Решение многокритериальной задачи линейного программирования графическим методом.
2.1.Формальное условие и сведение к ЗЛП
Чтобы можно было проверить условие (4) (Lr(x)іLr(x’),"r) для некоторой произвольно взятой точких,, не прибегая к попарному сравнению с другими, условиеp-оптимальности (4)переформулируем в виде следующей задачилинейного программирования:
Смысл задачи линейного программирования нетрудно понять, если учесть, чтоdr– это приращение ч-критерия Lr, получаемое при смещении решениях,в точкух.Тогда, если после решения ЗЛП окажетсяDmax= 0, то это будет означать, что ни один из ч-критериев нельзя увеличить (Dmax= 0), если не допускать уменьшения любого из других ("drі0). Но это и есть условиеp-оптимальности х,. Если же при решении окажется, чтоDі0, то значит какой-то ч-критерий увеличил свое значениебез ухудшениязначений других("drі0), и значит х,ПDpx.
Теперь перейдем к решению нашей задачи:
L1= -x1+ 2x2+ 2,
L2= x1+ x2+ 4,
L3= x1- 4x2+ 20,
x1+ x2Ј15,
5x1+ x2і1,
-x1+ x2Ј5,
x2Ј20,
"xjі0.
Проверим некоторую точку х,= (5; 3) (эта точка принадлежит области Dx) на предметp-оптимальности:
Запишем ЗЛП в каноническом виде:
d1= x1- 2x2+ 1
Dxkd2= x1+ x2- 8
d3= -x1+ 4x2- 7
D= x1+ 3x2– 14,
e1= 15 - x1- x2
e2= 5x1+ x2– 1,
Dxe3= 5 + x1- x2
e4= 20 - x2
"xjі0.
и в форме с-таблицы:
|
Т1
|
х1 |
х2 |
1 |
e1 |
-1 |
-1 |
16 |
e2 |
5 |
1 |
-4 |
e3 |
1 |
-1 |
100 |
e4 |
0 |
-1 |
10 |
d1 |
1 |
-2 |
-4 |
d2 |
1 |
1 |
-12 |
d3 |
-1 |
1 |
-8 |
D |
1 |
4 |
-24 |
Применяя с-метод, после заменыd3«х2, получаем:
|
Т2
|
х1 |
d1 |
1 |
e1 |
-3/2 |
|
29/2 |
e2 |
11/2 |
-1/2 |
-1/2 |
e3 |
1/2 |
|
9/2 |
e4 |
-1/2 |
|
39/2 |
X2 |
1/2 |
-1/2 |
1/2 |
d2 |
3/2 |
-1/2 |
-15/2 |
d3 |
1 |
-2 |
-5 |
D |
5/2 |
-3/2 |
-25/2 |
Видим, что опорный план не получен, следовательно делаем еще одну замену:e1«х1:
|
Т3
|
e3 |
d1 |
1 |
x1 |
|
|
29/3
|
e2 |
|
|
316/6
|
e3 |
|
|
56/6
|
e4 |
|
|
88/6
|
x2 |
|
|
16/3
|
d2 |
|
|
7
|
d3 |
|
|
14/3
|
D |
-5/3 |
-2/3 |
70/6 |
В Т3получен опорный план. Так как при этомD>0, то, следовательно, система ч-критериев не противоречива и существует некоторая область, смещение в которую решения х,способно увеличить, по крайней мере, один ч-критерий без уменьшения значений остальных. Эта область и естьконусдоминирования - д – конусом Dxk(на рисунке выделен штриховкой). При R > n д-конус может выродиться в точку х, (вершина д-конуса). Получено целое множество оптимальных решений, извлекаемое из Т3: х0 = ( 29/3 ; 16/3 ). Таким образом, решение х, = ( 5; 3) не являетсяp-оптимальным, так как его удалось улучшить (Dmax>0). Помимо установления факта неэффективности решения х,, рассмотренный метод позволил определить ближайшее к немуp-оптимальное решение.
2 .2. Графическое определение p -множества
Сначала необходимо построить график.
Для построения графика необходимы следующие данные:
исходные данные:
L1= x1- 2x2+ 2,
L2= x1+ x2+ 4,
L3= -x1+ 4x2- 20,
в каноническом виде (после подстановки точки (5;3))
d1= x1- 2x2+ 1, (5 - 2*3 + 1= 1)
Dxkd2= x1+ x2- 8, (5 + 3 + 4 = 12)
d3= -x1+ 4x2- 7, (-5 + 4*3 - 20 = -13)
D= 2x1+ 4x2– 14,
Находим точки для построения прямых:
1)d1= x1- 2x2+ 1,
-x1+ 2x2Ј1 (1;1)
2)d2= x1+ x2- 8,
x1+ x2і8 (0;8)
3)d3= -x1+ 4x2- 7,
-x1 + 4x2і7 (1;2)
По полученным точкам строим график (рисунок 1). На рисунке штриховкой показан полученный д-конус. Переход к любой точке внутри конуса обеспечивает увеличение всех критериев. Точка (29/3; 16/3) являетсяp-оптимальным решением. Смещая точку х,внутрь д-конуса придем на границуe1. При этом д-конус выйдет из области допустимых решений (ОДР) Dx. Теперь полученная точка не сможет улучшить ни один ч-критерий без ухудшения других, значит онаp-оптимальная. Построив д-конус в любой точке стороныe1, убеждаемся, что каждая из точекp-оптимальна, значит вся сторонаe1составляетp-множество.
3.Определение Парето-оптимального множества
с-методом
3.1.Удаление пассивных ограничений
Перед построениемp-множества из системы ограничений должны быть удалены пассивные ограничения.Пассивнымбудем называть неравенство (п-неравенство), граница которого не является частью границ области Dx, за исключением, может быть, ее отдельной точки. Неравенства, образующие границы Dx, назовем активными (а-неравенства).
Чтобы грани не были включены в Dxp, не имея никакого отношения к Dxp, неравенствоe1должно быть удалено из исходной системы ограничений. Условием для исключения неравенстваeiі0 из системы являетсянесовместность(или вырожденность) данной системы неравенств при условииei= 0. Геометрически это означает, что границаei= 0 неравенстваeiі0не пересекаетсяс областью Dxили имеет одну общую точку. Если границаei= 0 имеет общую угловую точку с Dx(вырожденность), то с удалением п-неравенстваeiі0 эта точка не будет утеряна, так как она входит в границы других неравенств. Помимо заданных m неравенств проверке подлежат и n условий неотрицательности переменных, так как координатные плоскости (оси) также могут входить в границы Dx.
В качестве примечания можно отметить, что поскольку п-неравенства (пассивные неравенства) для любой точки xОDxбудут выполнены, то по мере выявления п-неравенств и введения их в базис они удаляются из с-таблицы.
Запишем систему неравенств Dxв форме с-таблицы:
|
Т1
|
х1 |
х2 |
1 |
bi/ais |
bi/ais |
e1 |
-1 |
-1 |
15 |
15 |
15 |
e2 |
5 |
1 |
-1 |
1/5 |
1 |
e3 |
1 |
-1 |
5 |
- |
5 |
e4 |
0 |
-1 |
20 |
- |
20 |
|
Т2
|
e1 |
x2 |
1 |
|
|
| |
Т2’
|
x1 |
e2 |
1 |
х1 |
-1 |
-1 |
15 |
|
|
| |
e1
|
4 |
-1 |
14 |
e2 |
-5 |
-4 |
74 |
|
|
| |
x2
|
-5 |
1 |
1 |
e3 |
-1 |
-2 |
20 |
|
|
| |
e3
|
2 |
-1 |
4 |
e4 |
0 |
-1 |
20 |
|
|
| |
e4
|
1 |
-1 |
19 |
