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

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

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

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

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

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

L₂ = x₁ + x₂ + 4,

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

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

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

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

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

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

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

¹ = x₁ - 2x₂ + 1,

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

² = x₁ + x₂ - 8,

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

³ = -x₁ + 4x₂ - 7,

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

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

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

с-методом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(8)

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

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

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

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

₁ D_x^, так как _max= 0.

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

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

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

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

(9)

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

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

¹ = х₁ - 2х₂ -  + 2,

² = х₁ + х₂ -  + 4,

³ = -х₁ + 4х₂ -  + 20,

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

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

₃ = x₁ - х₂ + 5,

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

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

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

L₁ = L₃ =  = 25/2

L₂ =  + ₂ = 25/2 + 13/2 = 19

L^ = 88/2 = 44

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

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

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

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

(9)

где

(10)

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

(11)

Коэффициенты веса обычно получаются путем опроса экспертов из соответствующей предметной области. Поскольку вектор  = (_r) – суть вектор-градиент ЦФ L^(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-го вида;

_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 – доля (процент налоговых отчислений от прибыли (выручки).

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

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

L_1max = 17

L_{2 max} = 19

L₃ = 5

L^= 41

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

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

Похожие работы

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

Скачать

20768

22

2

... = -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.Формальное условие и сведение к ЗЛП Чтобы можно было ...

Оптимизационные методы решения экономических задач

Скачать

23385

0

0

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

Линейное программирование

Скачать

63048

19

8

... 4 X1 + 2 X2 + 0 X3 + X4 = 19 0 X1 + 1 X2 + 1 X3 + X5 = 8 1 X1 + 2 X2 + 0 X3 + X6 = 24 Получили задачу: 4X1+2X2+X4 = 19 X2 + X3 +X5 = 8 X1+2X2 +X6 =24   3.3 Решаем задачу путем сведения к задаче линейного программирования: Xi≥0 ; 0-Z= -3X1- -7X2- -2X3 Приведем задачу к канонической форме. Задача ...

Теория принятия решений

Скачать

83422

1

0

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