Решение многокритериальной задачи линейного програмирования
Министерство общего и профессионального образования РФ
ТГТУ
Кафедра ИС
Курсовая работа по дисциплине
Теория оптимального управления ЭС
Выполнил студент группы ИСЭ-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.Формальная постановка многокритериальной задачи линейного программирования.
Формальная схема многокритериальной ЗЛП (МЗЛП) от обычной ЗЛП отличается наличием нескольких целевых функций
(1)
где e
i – неотрицательные переменные (невязки, i = 1; m).
(3)
(2)
Знак max означает тот факт, что
желательно увеличение каждой из линейных форм
Lr
(х), отражающей некоторую r-ю цель ЛРП.
Требование только максимизации не сужает общности задачи. Так, например, требование минимизации затрат некоторых ресурсов эквивалентно требованию максимизации остатка от изначально выделенных ресурсов. Наличие многих ч-критериев позволяет сделать модель (1) – (3) более адекватной изучаемой ситуации, однако выводит её из класса задач МП и требует разработки новых способов ее анализа. Начальный анализ МЗЛП состоит в удалении из области допустимых решений (ОДР) Dх явно худших, доминируемых решений х. Решение х, доминирует решение х (х, > х), если при х, хотя бы один ч-критерий имеет больше значение при равенстве остальных. Поэтому решение х может быть исключено из дальнейшего рассмотрения, как явно худшее, чем х,. Если решение х, не доминируется ни одним из решений х Î Dx, то его называют Паретто-оптимальным (p — оптимальным) или эффективным решением (p — решением). Таким образом, p-решение — это неулучшаемое (недоминируемое) решение, и ясно, что решение ЛПР должно обладать этим свойством – другие решения нет смысла рассматривать.
Формальное определение p-оптимальности решения х, записывается как требование об отсутствии такого решения хÎ Dx, при котором бы были выполнены условия
(4)
и хотя бы одно из них – строго (со знаком >).
Иными словами, условия (4) выражают требование невозможности улучшения решения х, в пределах ОДР Dx ни по одному ч-критерию без ухудшения хотя бы по одному из других.
1.2.Условие задачи
Даны целевые функции
L1 = -x1 + 2×2 + 2,
L2 = x1 + x2 + 4,
L3 = x1 — 4×2 + 20,
и система ограничений
x1 + x2 £ 15,
5×1 + x2 ⊃3; 1,
-x1 + x2 £ 5,
x2 £ 20,
xj ⊃3; 0.
2. Решение многокритериальной задачи линейного программирования графическим методом.
2.1.Формальное условие и сведение к ЗЛП
Чтобы можно было проверить условие (4) (Lr(x) ⊃3; Lr(x’),»r) для некоторой произвольно взятой точки х,, не прибегая к попарному сравнению с другими, условие p-оптимальности (4) переформулируем в виде следующей задачи линейного программирования
(6)
(5)
(7)
Смысл задачи линейного программирования нетрудно понять, если учесть, что dr – это приращение ч-критерия Lr, получаемое при смещении решения х, в точку х. Тогда, если после решения ЗЛП окажется Dmax = 0, то это будет означать, что ни один из ч-критериев нельзя увеличить (Dmax = 0), если не допускать уменьшения любого из других (» dr ⊃3; 0). Но это и есть условие p-оптимальности х,. Если же при решении окажется, что D ⊃3; 0, то значит какой-то ч-критерий увеличил свое значение без ухудшения значений других (» dr ⊃3; 0), и значит х, Ï Dpx.
Теперь перейдем к решению нашей задачи
L1 = -x1 + 2×2 + 2,
L2 = x1 + x2 + 4,
L3 = x1 — 4×2 + 20,
x1 + x2 £ 15,
5×1 + x2 ⊃3; 1,
-x1 + x2 £ 5,
x2 £ 20,
«xj ⊃3; 0.
Проверим некоторую точку х, = (5; 3) (эта точка принадлежит области Dx) на предмет p-оптимальности
Запишем ЗЛП в каноническом виде
d1 = x1 — 2×2 + 1
Dxk d2 = x1 + x2 — 8
d3 = -x1 + 4×2 — 7
D = x1 + 3×2 – 14,
e1 = 15 — x1 — x2
e2 = 5×1 + x2 – 1,
Dx e3 = 5 + x1 — x2
e4 = 20 — x2
«xj ⊃3; 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 — 2×2 + 2,
L2 = x1 + x2 + 4,
L3 = -x1 + 4×2 — 20,
в каноническом виде (после подстановки точки (5;3))
d1 = x1 — 2×2 + 1, (5 — 2*3 + 1= 1)
Dxk d2 = x1 + x2 — 8, (5 + 3 + 4 = 12)
d3 = -x1 + 4×2 — 7, (-5 + 4*3 — 20 = -13)
D = 2×1 + 4×2 – 14,
Находим точки для построения прямых
1) d1 = x1 — 2×2 + 1,
-x1 + 2×2 £ 1 (1;1)
2) d2 = x1 + x2 — 8,
x1 + x2 ⊃3; 8 (0;8)
3) d3 = -x1 + 4×2 — 7,
-x1 + 4×2 ⊃3; 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 ⊃3; 0 из системы является несовместность (или вырожденность) данной системы неравенств при условии ei = 0. Геометрически это означает, что граница ei = 0 неравенства ei ⊃3; 0 не пересекается с областью Dx или имеет одну общую точку. Если граница ei = 0 имеет общую угловую точку с Dx (вырожденность), то с удалением п-неравенства ei ⊃3; 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
ОП – получен, следовательно ОП – получен, следовательно
х2 и e1 – активные ограничения; x1 и e2 – активные ограничения;
из Т2 получаем
Т3
e1
e3
1
x1
1
1/2
5
e2
-3
2
34
x2
-1/2
-1/2
10
e4
2
½
10
отсюда делаем вывод, что e3 – активное ограничение;
из Т3 получаем
Т4
e4
e3
1
x1
10
e2
19
x2
15/2
e1
-5
Опорный план не получен, следовательно e4 – пассивное ограничение.
3.2.Определение p-множества с-методом.
При подготовке решения для ЛПР интерес будет представлять информация обо всем множестве p-оптимальных (эффективных) решений Dxp. Графический метод позволяет сформулировать довольно простой подход к определению множества Dxp. Суть этого подхода в следующем. Решая усеченную задачу линейного программирования, устанавливаем факт существования д-конуса ( Dmax > 0). Поскольку для линейных ЦФ конфигурация д-конуса не зависит от положения его вершины х,, то, помещая ее на границу ei области Dx, решаем усеченную ЗЛП с добавлением ei, соответствующего i-му участку границ Dx. Вырождение д-конуса в точку х, будет признаком p-оптимальности и всех других точек данной грани. С помощью с-метода указанная процедура легко проделывается для пространства любой размерности n. Неудобство указанного метода состоит в том, что потребуется на каждой грани ОДР Dx найти точку х, (по числу граней Dx) сформулировать и решить столько же ЗЛП размера Rxn.
Существенно сократить объем вычислений можно путем выбора вершины д-конуса в фиксированной точке х, = (1)n и в нее же параллельно себе перенести грани, составляющие границы Dx
Приведенные к точке х, = (1)n приращения d-r и невязки ei запишутся в виде
(8)
где черта сверху у d, e и D означает, что эти величины приведены к точке х, = (1)n.
По существу, (8) – ЗЛП размера (R+m)xn (D®max), а ее решение позволит найти все грани, составляющие p-множество Dxp.
Составляем с-таблицу, не учитывая пассивные ограничения, т.е e1
Т1
х1
х2
1
e2
-1
-1
2
e3
5
1
-6
e4
1
-1
0
х1
1
0
-1
х2
0
1
-1
d1
1
-2
1
d2
1
1
-2
d3
-1
4
-3
D
1
3
-4
В начале решается усеченная ЗЛП (под чертой)
Т2
х1
d1
1
e1
-3/2
1/2
3/2
e2
11/2
-1/2
-11/2
e3
1/2
1/2
-1/2
х1
1
0
-1
х2
1/2
-1/2
-1/2
x2
1/2
-1/2
1/2
d2
3/2
-1/2
-3/2
d3
1
-2
-1
D
5/2
-3/2
-5/2
Т3
d3
d1
1
e1
-3/2
-5/2
0
e2
11/2
21/2
0
e3
1/2
3/2
0
х1
1
2
0
х2
1/2
1/2
0
x2
1/2
1/2
1
d2
3/2
5/2
0
x1
1
2
1
D
5/2
7/2
0
Т4
e1
d1
1
d3
0
x2
1
d2
0
x1
1
D
-5/3
-2/3
0
e1Î Dxp, так как Dmax = 0.
Данный метод построения множества Dxp обладает недостатком, связанным с разрушением области допустимых решений (ОДР) Dx при переносе ее граней в х,. Действительно, вершины области Dx в преобразованной модели никак не отражены, а именно одна из них может составить p-множество в случае его совпадения с оптимальным решением. Такое совпадение возможно, если все ч-критерии достигают максимум на одной вершине. Физически это значит, что они слабопротиворечивы – угол при вершине д-конуса приближается к 180° (градиенты ч-критериев имеют практически совпадающие направления). Данный случай имеет место, если в p-множество не вошла ни одна из граней ОДР Dx. Следовательно, p-множество совпадает с оптимальным решением. Для определения p-множества решается обычная ЗЛП с одним из ч-критериев. Если при этом получено множество оптимальных решений, то решается ЗЛП с другим ч-критерием. Пересечение оптимальных решений и является p-множеством. Для ЛПР указание на то, что некоторая грань ei = eip Î Dxp p-оптимальна, является только обобщенной информацией.
4.Определение альтернативных вариантов многокритериальной задачи
Наиболее естественным и разумным решением мк-задачи было бы органическое объединение всех ч-критериев в виде единой ЦФ. Иногда это удается сделать путем создания более общей модели, в которой ч-критерии являются аргументами более общей целевой функции, объединяющей в себе все частные цели операции. На практике этого редко удается достигнуть, что, собственно, и является основной причиной появления проблемы многокритериальности. Однако наиболее распространенный подход к решению проблемы пока остается все-таки один тем или иным путем свести решение мк-задачи к решению однокритериальной задачи. В основе подхода лежит предположение о существовании некой функции полезности, объединяющей в себе ч-критерии, но которую в явном виде, как правило, получить не удается. Получение наиболее обоснованной «свертки» ч-критериев является предметом исследований нового научного направления, возникшего в связи с проблемой многокритериальности — теории полезности. В данной работе будут рассмотрены некоторые подходы, позволяющие получить варианты решения мк-задач при тех или иных посылках и которые лицо принимающее решение (ЛПР) должно рассматривать как альтернативные при принятии окончательного решения и которые, конечно, должны удовлетворять необходимому условию- p-оптимальности.
4.1.Метод гарантированного результата
При любом произвольном решении х Î Dx каждый из ч-критериев примет определенное значение и среди них найдется, по крайней мере, один, значение которого будет наименьшим
(9)
Метод гарантированного результата (ГР) позволяет найти такое (гарантированное) решение, при котором значение «наименьшего» критерия станет максимальным. Таким образом, целевая функция (ЦФ) является некоторой сверткой ч-критериев (9), а МЗЛП сводится к задаче КВП (кусочно-выпуклого программирования) при ОДР Dx, заданной линейными ограничениями.
Исходные условия записываем в каноническом виде
d1 = х1 — 2х2 — j + 2,
d2 = х1 + х2 — j + 4,
d3 = -х1 + 4х2 — j + 20,
e1 = -х1 — х2 + 15,
e2 = 5х1 + х2 — 1,
e3 = x1 — х2 + 5,
потом в виде с-таблицы
Т1
х1
х2
j
1
e1
-1
-1
0
15
e2
5
1
0
-1
e3
1
-1
0
5
d1
1
-2
-1
2
d2
1
1
-1
4
d3
-1
4
-1
20
Вводя в базис переменную j (d1 « j), получаем обычную ЗЛП при максимизации ЦФ j.
Т2
х1
х2
d1
1
e1
-1
-1
0
15
e2
5
1
0
-1
e3
1
-1
0
5
j
1
-2
-1
2
d2
0
3
1
2
d3
-2
6
1
18
Т3
d3
x2
d1
1
bi/ais
e1
1/2
-4
-1/2
6
6/4
e2
-5/2
16
5/2
44
—
e3
-1/2
2
2
14
—
j
-1/2
1
-1/2
11
—
d2
0
3
-1
2
—
х1
-1/2
3
1/2
9
—
Т4
d3
e1
d1
1
x2
3/2
e2
68
e3
17
j
-3/8
-1/4
-5/8
25/2
d2
13/2
х1
27/2
Решение ЗЛП приводит к конечной с-таблице Т4. Видно, что полученное гарантированное решение х p-оптимально, поскольку введение в базис любой свободной переменной (т.е. ее увеличение) приведет к снижению j — нижнего уровня ч-критериев («сj < 0). Из таблицы также видно, что решение х0=(27/2; 3/2) находится на грани e4, при этом значения ч-критериев равны (находим по формуле Lr(xr) = j + dr)
L1 = L3 = j = 25/2
L2 = j + d2 = 25/2 + 13/2 = 19
LS = 88/2 = 44
x° = ( 27/2; 3/2)
Если бы в строке j имелись нули, то это означало бы, что одну из соответствующих переменных можно ввести в базис (увеличить без снижения уровня j). Это могло бы привести и к увеличению приращения dr для некоторого ч-критерия, находящегося в базисе.
4.2.Метод линейной свертки частных критериев
Линейная свертка ч-критериев получается как х сумма с некоторыми весовыми коэффициентами mr
(9)
где
(10)
Меняя порядок суммирования и вводя обозначения cj и c0, окончательно получим
(11)
Коэффициенты веса обычно получаются путем опроса экспертов из соответствующей предметной области. Поскольку вектор m = (mr) – суть вектор-градиент ЦФ Lm(x), то предполагается, что он указывает направление к экстремуму неизвестной функции полезности. Положительная сторона такого подхода – несложность, не всегда компенсирует его серьезный недостаток – потерю физического смысла линейной свертки разнородных ч-критериев. Это затрудняет интерпретацию результатов, поэтому полученное таким путем решение, следует рассматривать только как возможный (альтернативный) вариант решения ЛПР. Для его сравнительного анализа следует привлекать любые другие варианты и, конечно, значения ч-критериев, получаемые при этом. Иногда при получении свертки ч-критериев предварительно нормируются каким-нибудь способом.
Наиболее приемлемой линейная свертка ч-критериев может оказаться в том случае, когда ч-критерии однородны и имеют единый эквивалент, согласующий их наиболее естественным образом.
На содержательном уровне данная МЗЛП состоит в необходимости принятия такого компромиссного решения (плана выпуска продукции) xk Î Dx, которое обеспечит, по возможности, наибольшую суммарную выручку L1(x) от реализации произведенной продукции; наименьший расход ресурсов i-го вида Lpl (x) (i = 1; m); минимальные налоговые отчисления от прибыли LH(x) (или общей выручки).
Указанные цели носят противоречивый характер, и фактически мы имеем МЗЛП с m+2 –мя ч-критериями (m – количество видов потребляемых ресурсов). ОДР обусловлена ресурсными ограничениями и условиями неотрицательных переменных
где aij – расход ресурса i-го вида для выпуска 1 единицы продукции j-го вида (j=1,n);
bi – запас ресурса i-го вида;
ei – остаток ресурса i-го вида при плане выпуска x = (xj)n. Ч-критерии однородны, если они могут быть сведены к единой мере измерения. В качестве такой меры можно взять денежный эквивалент. Тогда m+2 ч-критерия могут быть с помощью линейной свертки сведены к трем
общая выручка (руб.)
общая экономия ресурсов (руб.)
налоговые отчисления (руб.)
где cj – выручка от реализации 1 ед. продукции j-го вида (цена); si – стоимость (цена) 1 ед. ресурса i-го вида (i = 1;m); Пj – прибыль от реализации 1 ед. продукции j-го вида (j = 1;n); aj – доля (процент налоговых отчислений от прибыли (выручки).
В заключение заметим, что коэффициенты mr не обязательно должны удовлетворять условию (10), но обязательно должны быть положительными, если все ч-критерии максимизируются.
Перейдем к решению
Т1
х1
х2
1
e1
-1
-1
15
e2
5
1
-1
e3
1
-1
5
L1
1
-2
2
L2
1
1
4
L3
-1
4
20
LS
1
3
26
Т2
e1
x2
1
x1
-1
-1
15
e2
-5
-4
74
e3
-1
-2
20
L1
-1
-1
17
L2
-1
0
19
L3
1
5
5
LS
-1
2
41
L1 max = 17
L2 max = 19
L3 = 5
LS = 41
Т3
e1
L1
1
x1
28/3
e2
154/3
e3
26/3
x2
17/3
L2
19
L3
-2/3
-5/3
100/3
LS
-5/3
-2/3
157/3
5. Составление сводной таблицы.
Окончательное решение сводится в таблицу, где записываются альтернативные варианты
Метод
х0
L1
L2
L3
LS
Метод гарантированного результата
(27/2 ; 3/2)
25/2
19
25/2
44
Метод свертки
(28/3;17/3)
0
19
33 1/3
52 1/3
Оптимизация L1
(15;0)
17
19
5
41
Оптимизация L2, L3
(28/3;17/3)
0
19
33 1/3
52 1/3
xÏDxp
(5;3)
1
12
-13
0
«