Содержание

Введение

Лишь в редких случаях цели, которые лицо принимающее решение (ЛПР) стремится достичь в планируемой им операции, удается описать с помощью одного количественного показателя. Поэтому специалисты Системного анализа и Исследования операций считают целесообразным избегать термина «оптимизация», так как поиск оптимального решения х, доставляющего функции F(x) экстремальное значение, имеет вполне определенный смысл и давно входит в арсенал основных понятий математики. Многообразие целей ЛПР более адекватно может быть описано с помощью некоторой совокупности частных критериев (ч-критериев), характеризующих степень достижения частных целей. Противоречивый характер целей обуславливает, как правило, и противоречивость ч-критериев. С формальной точки зрения это приводит к тому, что свои экстремальные значения ч-критерии получают в различных точках ОДР D_x . Следовательно, ЛПР принимая решение х^, всегда должно идти на компромисс, в разумных пределах допуская ухудшение значений одних ч-критериев во имя улучшения значений других. Именно этот этап творческой деятельности ЛПР наименее формализуем и требует привлечения предыдущего опыта, интуиции и даже искусства ЛПР, обладающего практическим опытом в соответствующей предметной области. Решение, принимаемое ЛПР с привлечением совокупности ч-критериев, будем называть компромиссным , рациональным или просто решением ЛПР, избегая при этом термина «оптимальный», имеющего определенный и вполне точный смысл.

Основная идея обоснования и принятия решения ЛПР в условиях многокритериальности состоит в последовательном сужении ОДР D_x до минимальных размеров, что облегчает принятие окончательного решения ЛПР. Первым, наиболее существенным шагом в этом направлении будет являться сужение ОДР D_x до некоторого подмножества D_x ^p ÌD_x на основании принципа доминирования.

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

1.1.Формальная постановка многокритериальной задачи линейного программирования.

Формальная схема многокритериальной ЗЛП (МЗЛП) от обычной ЗЛП отличается наличием нескольких целевых функций:

Требование только максимизации не сужает общности задачи. Так, например, требование минимизации затрат некоторых ресурсов эквивалентно требованию максимизации остатка от изначально выделенных ресурсов. Наличие многих ч-критериев позволяет сделать модель (1) – (3) более адекватной изучаемой ситуации, однако выводит её из класса задач МП и требует разработки новых способов ее анализа. Начальный анализ МЗЛП состоит в удалении из области допустимых решений (ОДР) D_х явно худших, доминируемых решений х . Решение х^, доминирует решение х (х^, > х), если при х^, хотя бы один ч-критерий имеет больше значение при равенстве остальных. Поэтому решение х может быть исключено из дальнейшего рассмотрения, как явно худшее, чем х^, . Если решение х^, не доминируется ни одним из решений х ÎD_x , то его называют Паретто-оптимальным ( p - оптимальным) или эффективным решением ( p - решением) . Таким образом, p-решение - это неулучшаемое (недоминируемое) решение, и ясно, что решение ЛПР должно обладать этим свойством – другие решения нет смысла рассматривать.

Формальное определение p -оптимальности решения х^, записывается как требование об отсутствии такого решения х Î D_x , при котором бы были выполненыусловия

и хотя бы одно из них – строго (со знаком >).

Иными словами, условия (4) выражают требование невозможности улучшения решения х^, в пределах ОДР D_x ни по одному ч-критерию без ухудшения хотя бы по одному из других.

1.2.Условие задачи

Даны целевые функции:

L₁ = -x₁ + 2x₂ + 2,

L₂ = x₁ + x₂ + 4,

L₃ = x₁ - 4x₂ + 20,

и система ограничений:

x₁ + x₂ £ 15,

5x₁ + x₂ ³ 1,

-x₁ + x₂ £ 5,

x₂ £ 20,

"x_j ³ 0.

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

2.1.Формальное условие и сведение к ЗЛП

Чтобы можно было проверить условие (4) (L^r (x) ³L^r (x’),"r) для некоторой произвольно взятой точки х^, , не прибегая к попарному сравнению с другими, условие p-оптимальности (4) переформулируем в виде следующей задачи линейного программирования :

Смысл задачи линейного программирования нетрудно понять, если учесть, что d^r – это приращение ч-критерия L^r , получаемое при смещении решения х^, в точку х. Тогда, если после решения ЗЛП окажется D_max = 0, то это будет означать, что ни один из ч-критериев нельзя увеличить (D_max = 0), если не допускать уменьшения любого из других ("d^r ³ 0). Но это и есть условие p-оптимальности х^, . Если же при решении окажется, что D³ 0, то значит какой-то ч-критерий увеличил свое значение без ухудшения значений других ("d^r ³ 0), и значит х^, ÏD^p _x .

Теперь перейдем к решению нашей задачи:

L₁ = -x₁ + 2x₂ + 2,

L₂ = x₁ + x₂ + 4,

L₃ = x₁ - 4x₂ + 20,

x₁ + x₂ £ 15,

5x₁ + x₂ ³ 1,

-x₁ + x₂ £ 5,

x₂ £ 20,

"x_j ³ 0.

Проверим некоторую точку х^, = (5; 3) (эта точка принадлежит области Dx) на предмет p-оптимальности:

Запишем ЗЛП в каноническом виде:

d¹ = x₁ - 2x₂ + 1

D_x ^k d² = x₁ + x₂ - 8

d³ = -x₁ + 4x₂ - 7

D = x₁ + 3x₂ – 14,

e₁ = 15 - x₁ - x₂

e₂ = 5x₁ + x₂ – 1,

D_x e₃ = 5 + x₁ - x₂

e₄ = 20 - x₂

"x_j ³ 0.

и в форме с-таблицы:

Применяя с-метод, после замены d³ « х₂ , получаем:

Видим, что опорный план не получен, следовательно делаем еще одну замену: e₁ « х₁ :

В Т₃ получен опорный план. Так как при этом D>0, то, следовательно, система ч-критериев не противоречива и существует некоторая область, смещение в которую решения х^, способно увеличить, по крайней мере, один ч-критерий без уменьшения значений остальных. Эта область и есть конус доминирования - д – конусом D_x ^k (на рисунке выделен штриховкой). При R > n д-конус может выродиться в точку х^, (вершина д-конуса). Получено целое множество оптимальных решений, извлекаемое из Т₃ : х⁰ = ( 29/3 ; 16/3 ). Таким образом, решение х^, = ( 5; 3) не является p-оптимальным, так как его удалось улучшить (D_max >0). Помимо установления факта неэффективности решения х^, , рассмотренный метод позволил определить ближайшее к нему p-оптимальное решение.

2 .2. Графическое определение p -множества

Сначала необходимо построить график.

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

исходные данные:

L₁ = x₁ - 2x₂ + 2,

L₂ = x₁ + x₂ + 4,

L₃ = -x₁ + 4x₂ - 20,

в каноническом виде (после подстановки точки (5;3))

d¹ = x₁ - 2x₂ + 1, (5 - 2*3 + 1= 1)

D_x ^k d² = x₁ + x₂ - 8, (5 + 3 + 4 = 12)

d³ = -x₁ + 4x₂ - 7, (-5 + 4*3 - 20 = -13)

D = 2x₁ + 4x₂ – 14,

Находим точки для построения прямых:

1) d¹ = x₁ - 2x₂ + 1,

-x₁ + 2x₂ £ 1 (1;1)

2) d² = x₁ + x₂ - 8,

x₁ + x₂ ³8 (0;8)

3) d³ = -x₁ + 4x₂ - 7,

-x₁ + 4x₂ ³7 (1;2)

По полученным точкам строим график (рисунок 1). На рисунке штриховкой показан полученный д-конус. Переход к любой точке внутри конуса обеспечивает увеличение всех критериев. Точка (29/3; 16/3) является p-оптимальным решением. Смещая точку х^, внутрь д-конуса придем на границу e₁ . При этом д-конус выйдет из области допустимых решений (ОДР) D_x . Теперь полученная точка не сможет улучшить ни один ч-критерий без ухудшения других, значит она p-оптимальная. Построив д-конус в любой точке стороны e₁ , убеждаемся, что каждая из точек p-оптимальна, значит вся сторона e₁ составляет p-множество.

3.Определение Парето-оптимального множества

с-методом

3.1.Удаление пассивных ограничений

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

Чтобы грани не были включены в D_x ^p , не имея никакого отношения к D_x ^p , неравенство e₁ должно быть удалено из исходной системы ограничений. Условием для исключения неравенства e_i ³ 0 из системы является несовместность (или вырожденность) данной системы неравенств при условии e_i = 0. Геометрически это означает, что граница e_i = 0 неравенства e_i ³ 0 не пересекается с областью D_x или имеет одну общую точку. Если граница e_i = 0 имеет общую угловую точку с D_x (вырожденность), то с удалением п-неравенства e_i ³ 0 эта точка не будет утеряна, так как она входит в границы других неравенств. Помимо заданных m неравенств проверке подлежат и n условий неотрицательности переменных, так как координатные плоскости (оси) также могут входить в границы D_x .

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

Запишем систему неравенств D_x в форме с-таблицы:

ОП – получен, следовательно ОП – получен, следовательно

х₂ и e₁ – активные ограничения; x₁ и e₂ – активные ограничения;

из Т₂ получаем:

отсюда делаем вывод, что e₃ – активное ограничение;

из Т₃ получаем:

Опорный план не получен, следовательно e₄ – пассивное ограничение.

3.2 .Определение p -множества с-методом.

При подготовке решения для ЛПР интерес будет представлять информация обо всем множестве p-оптимальных (эффективных) решений D_x ^p . Графический метод позволяет сформулировать довольно простой подход к определению множества D_x ^p . Суть этого подхода в следующем. Решая усеченную задачу линейного программирования, устанавливаем факт существования д-конуса ( D_max > 0). Поскольку для линейных ЦФ конфигурация д-конуса не зависит от положения его вершины х^, , то, помещая ее на границу e_i области D_x , решаем усеченную ЗЛП с добавлением e_i , соответствующего i-му участку границ D_x . Вырождение д-конуса в точку х^, будет признаком p-оптимальности и всех других точек данной грани. С помощью с-метода указанная процедура легко проделывается для пространства любой размерности n. Неудобство указанного метода состоит в том, что потребуется на каждой грани ОДР D_x найти точку х^, (по числу граней D_x ) сформулировать и решить столько же ЗЛП размера R xn .

Существенно сократить объем вычислений можно путем выбора вершины д-конуса в фиксированной точке х^, = (1)_n и в нее же параллельно себе перенести грани, составляющие границы D_x

Приведенные к точке х^, = (1)_n приращения d^{- r} и невязки e_i запишутся в виде:

где черта сверху у d, e и D означает, что эти величины приведены к точке х^, = (1)_n .

По существу, (8) – ЗЛП размера (R+m)xn (D®max), аее решение позволит найти все грани, составляющие p-множество D_x ^p .

Составляем с-таблицу, не учитывая пассивные ограничения, т.е e₁ :

В начале решается усеченная ЗЛП (под чертой):

e₁ ÎD_x ^p , так как D_max = 0.

Данный метод построения множества D_x ^p обладает недостатком, связанным с разрушением области допустимых решений (ОДР) D_x при переносе ее граней в х^, . Действительно, вершины области D_x в преобразованной модели никак не отражены, а именно одна из них может составить p-множество в случае его совпадения с оптимальным решением. Такое совпадение возможно, если все ч-критерии достигают максимум на одной вершине. Физически это значит, что они слабопротиворечивы – угол при вершине д-конуса приближается к 180° (градиенты ч-критериев имеют практически совпадающие направления). Данный случай имеет место, если в p-множество не вошла ни одна из граней ОДР D_x . Следовательно, p-множество совпадает с оптимальным решением. Для определения p-множества решается обычная ЗЛП с одним из ч-критериев. Если при этом получено множество оптимальных решений, то решается ЗЛП с другим ч-критерием. Пересечение оптимальных решений и является p-множеством. Для ЛПР указание на то, что некоторая грань e_i = e_i ^p ÎD_x ^p p-оптимальна, является только обобщенной информацией.

4.Определение альтернативных вариантов многокритериальной задачи

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

4.1.Метод гарантированного результата

При любом произвольном решении х ÎD_x каждый из ч-критериев примет определенное значение и среди них найдется, по крайней мере, один, значение которого будет наименьшим :

Метод гарантированного результата (ГР) позволяет найти такое (гарантированное) решение, при котором значение «наименьшего» критерия станет максимальным. Таким образом, целевая функция (ЦФ) является некоторой сверткой ч-критериев (9), а МЗЛП сводится к задаче КВП (кусочно-выпуклого программирования) при ОДР D_x , заданной линейными ограничениями.

Исходные условия записываем в каноническом виде:

d¹ = х₁ - 2х₂ - j + 2,

d² = х₁ + х₂ - j + 4,

d³ = -х₁ + 4х₂ - j + 20,

e₁ = -х₁ - х₂ + 15,

e₂ = 5х₁ + х₂ - 1,

e₃ = x₁ - х₂ + 5,

потом в виде с-таблицы:

Вводя в базис переменную j (d¹ «j), получаем обычную ЗЛП при максимизации ЦФ j.

Решение ЗЛП приводит к конечной с-таблице Т₄ . Видно, что полученное гарантированное решение х p-оптимально, поскольку введение в базис любой свободной переменной (т.е. ее увеличение) приведет к снижению j - нижнего уровня ч-критериев ("с_j < 0). Из таблицы также видно, что решение х⁰ =(27/2; 3/2) находится на грани e₄ , при этом значения ч-критериев равны (находим по формуле L^r ( x^r ) = j + d ^r ):

L₁ = L₃ =j = 25/2

L₂ = j + d₂ = 25/2 + 13/2 = 19

L^S = 88/2 = 44

x° = ( 27/2; 3/2)

Если бы в строке j имелись нули, то это означало бы, что одну из соответствующих переменных можно ввести в базис (увеличить без снижения уровня j). Это могло бы привести и к увеличению приращения d^r для некоторого ч-критерия, находящегося в базисе.

4.2.Метод линейной свертки частных критериев

Линейная свертка ч-критериев получается как х сумма с некоторыми весовыми коэффициентами m_r :

где

Меняя порядок суммирования и вводя обозначения c_j и c₀ , окончательно получим:

Коэффициенты веса обычно получаются путем опроса экспертов из соответствующей предметной области. Поскольку вектор m = (m_r ) – суть вектор-градиент ЦФ L^m (x), то предполагается, что он указывает направление к экстремуму неизвестной функции полезности . Положительная сторона такого подхода – несложность, не всегда компенсирует его серьезный недостаток – потерю физического смысла линейной свертки разнородных ч-критериев. Это затрудняет интерпретацию результатов, поэтому полученное таким путем решение, следует рассматривать только как возможный (альтернативный) вариант решения ЛПР. Для его сравнительного анализа следует привлекать любые другие варианты и, конечно, значения ч-критериев, получаемые при этом. Иногда при получении свертки ч-критериев предварительно нормируются каким-нибудь способом.

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

На содержательном уровне данная МЗЛП состоит в необходимости принятия такого компромиссного решения (плана выпуска продукции) x^k ÎD_x , которое обеспечит, по возможности, наибольшую суммарную выручку L¹ (x) от реализации произведенной продукции; наименьший расход ресурсов i -го вида L^pl (x) (i = 1; m); минимальные налоговые отчисления от прибыли L^H (x) (или общей выручки).

Указанные цели носят противоречивый характер, и фактически мы имеем МЗЛП с m+2 –мя ч-критериями (m – количество видов потребляемых ресурсов). ОДР обусловлена ресурсными ограничениями и условиями неотрицательных переменных:

где a_ij – расход ресурса i-го вида для выпуска 1 единицы продукции j-го вида (j=1,n);

b_i – запас ресурса i-го вида;

e_i – остаток ресурса i-го вида при плане выпуска x = (x_j )_n . Ч-критерии однородны, если они могут быть сведены к единой мере измерения . В качестве такой меры можно взять денежный эквивалент. Тогда m+2 ч-критерия могут быть с помощью линейной свертки сведены к трем:

общая выручка (руб.):

общая экономия ресурсов (руб.):

налоговые отчисления (руб.):

где c_j – выручка от реализации 1 ед. продукции j-го вида (цена); s_i – стоимость (цена) 1 ед. ресурса i-го вида (i = 1;m); П_j – прибыль от реализации 1 ед. продукции j-го вида (j = 1;n); a_j – доля (процент налоговых отчислений от прибыли (выручки).

В заключение заметим, что коэффициенты m_r не обязательно должны удовлетворять условию (10),но обязательно должны быть положительными, если все ч-критерии максимизируются.

Перейдем к решению:

L_{1 max} = 17

L_{2 max} = 19

L₃ = 5

L^S = 41

5. Составление сводной таблицы.

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