книги / Математические методы принятия решений

Поскольку эффективное множество Е неизвестно в явном ви­ де, то нельзя непосредственно решить эту задачу. Для большинства задач МКЛП множество Е не является выпуклым.

Один из способов решения поставленной задачи базируется на использовании таблицы выигрышей (табл. 5.12). Строки табли­ цы выигрышей представляют собой критериальные векторы, по­ лученные в результате максимизации отдельных критериев. В том случае, когда оптимум не единственный, необходимо принять спе­ циальные меры, чтобы все критериальные векторы, стоящие в стро­ ках, были недоминируемыми. Величины z*, стоящие на главной диагонали, образуют вектор максимальных значений критериев на множестве эффективных точек. Минимальное значение в j -м столбце таблицы выигрышей —это некоторая оценка минимально­ го значения j-ro критерия на множестве Е. Если минимальное по столбцу значение находится в строке, в которой стоит доми­ нируемый критериальный вектор, то оно может оказаться меньше искомого минимума на множестве Е. Если строка, содержащая минимальное значение, является недоминируемым критериальным вектором, то минимальное значение либо определяет минималь­ ное значение критерия на множестве Е, либо является его оценкой сверху. В целом, этот подход не всегда приводит к оптимальному решению.

Для определения минимального на множестве эффективных то­ чек значения г-го критерия можно использовать симплекс-метод. Поочередно лексикографически максимизируя каждый из критери­ ев, строим таблицу выигрышей. Пусть zmi —минимальное значение критерия, находящееся в г-м столбце таблицы выигрышей. Доба­ вим в условия-ограничения задачи еще одно ограничение с}х ^ zmi.

Начнем счет с граничной точки, соответствующей zmj. Исследуем грань с]х = zmi нового (после дополнительного ограничения) мно­ жества допустимых точек с целью найти такую граничную точку, из шторой исходит эффективное ребро с убывающим значением г-го критерия. Если такого ребра нет, то текущее значение zmi и есть минимальное значение г-го критерия на Е; процесс окончен. Ес­ ли такое ребро существует, то производим замещение переменной вдоль этого ребра методом Жордана и переходим в крайнюю точку на другом его конце, где значение г-го критерия равно z ^ . Вво­ дим дополнительное ограничение с\х ^ z ^ и повторяем процеду­ ру. Алгоритм заканчивает работу в точке минимума г-го критерия на множестве эффективных точек.

§ 5.16. Параметризация целевой функции

Рассмотрим алгоритм метода взвешенных сумм на примере па­ раметризации целевой функции для задачи ЛП с одним критерием. Аналогичная задача рассматривалась в § 5.2.

Исходная задача имеет вид

max {cj a: = z}, x e D .

Задан вектор сг е Мп, который определяет изменения координат це­ левой функции; вводится параметризованный (суммарный) гради­ ент целевой функции с+ e R":

с+ = с1 + Рс2,

где Р е [0, Ртах]- Отсюда находится последовательность парамет­ рически оптимальных граничных точек (и ребер) при изменении Р от 0 до Ртах.

Точка х 6 D называется параметрически оптимальной, если она максимизирует величину (с+)Тх, х е D, для некоторого значения

Р е [0, Рта*]- При использовании метода взвешенных сумм вводится выпук­

лая комбинация векторов

ХеЛ

итогда с+ = Xjci + Х2С2.

В табл. 5.15 имеем с у —z y > 0, сц — z y < О, т. е. J = 0 , следо­ вательно, процесс завершен.

Получили следующие подмножества множества Л, относящи­ еся к различным параметрически оптимальным крайним точкам и ребрам:

Лх>= { х е л |х 1б [ | , 1 ] д 2б[0, у ]} ,

ЛдЗ = |х е Л h 6

Задача 2. С помощью метода взвешенных сумм провести анализ задачи МКЛП:

(табл. 5.16). После решения задачи ЛП мы получим начальную па­ раметрически оптимальную точку х 1 = (0,4) (см. рис. 5.20).

Переводим переменную х\ в базис и переходим при использо­ вании метода Жордана в точку х 2 = (2,4) (табл. 5.17).

Таблица 5.17

Вторая итерация

Для определения подмножества Ах 2 аналогично получим си­ стему

—5Х1 + ЗХ2 ^ 0,

X4 = (3/8,5/8,0). Подмножество Лх2 изображено на рис. 5.22. Далее переходим в точку х 3 = (10/3, 10/3) (табл. 5.18).

Таблица 5.18

Последняя итерация