Green-sell.info

Новые технологии
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Многокритериальная оптимизация примеры решения задач

РЕШЕНИЕ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ НА ЭВМ

Цель: научиться методам решения многокритериальных ЗЛП с помощью ЭВМ, используя метод последовательных уступок.

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

Существует несколько методов решения многокритериальных задач. Одним из наиболее эффективных является метод последовательных уступок, использование которого рассмотрим на примере.

ПРИМЕР 4.1.Математическая модель трехкритериальной задачи имеет вид:

Решить задачу методом последовательных уступок, выбрав уступку по первому критерию d1=4, а по второму d2=5.

Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные x1, x2, x3. Для этого в ячейку А1 вводим подпись «Переменные», а соседние три ячейки В1, С1 и D1 вводим значения переменных. Это могут быть произвольные числа, например единицы, далее они будут оптимизироваться. Во второй строке задаем целевые функции. В А2 вводим подпись «Целевые», а в В2 формулой «=2*B1+C1–3*D1» задаем первую целевую функцию 2x1+ x2–3x3. Аналогично в С2 и D2 вводим вторую и третью целевую функцию, вводя в С2 «=B1+3*C1–2*D1», а в D2 «= –B1+2*C1+4*D1». В третью строку вводим левые части ограничений. Для этого вводим в А3 подпись «Ограничения», в В3 формулу «=B1+3*C1+2*D1», в С3 формулу «=2*B1–C1+D1» и в D3 формулу «=B1+2*C1».

Предварительные действия завершены. Вызываем надстройку «Поиск решения» в меню «Сервис». На первом этапе оптимизируем первую целевую функцию.

После открытия окна «Поиск решения» в поле «Установить целевую» ставим курсор и делаем ссылку на ячейку В2, щелкая по ней мышью. В окне появится $B$2. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Равной максимальному значению». После ставим курсор в поле «Изменяя ячейки» и обводим ячейки с переменными В1, С1 и D1, выделяя ячейки с переменными. В поле появится $B$1:$D$1. В нижней части окна находится поле «Ограничения». Для того чтобы ввести ограничения, нажимают кнопку «Добавить», откроется окно «Добавление ограничения». В левом поле «Ссылка на ячейку» вводят ссылку на левую часть первого ограничения – ячейку В3, в центральном окне определяем знак ≥ и в правом «Ограничения» набираем правую часть ограничения – число 1. Нажимаем «ОК», видим, что ограничение появилось в окне. Нажимаем вновь «Добавить», вводим «С3» «≤» и «16». Вновь нажимаем «Добавить», вводим «D3» «≤» и «24». Для ввода дополнительных ограничений x1, x2, x30 вновь нажимаем «Добавить», ставим курсор в левое поле и обводим ячейки В1, С1 и D1 (результат $B$1:$D$1) в среднем окне ставим «≥» и в правом число 0. Результат на рис.4.1.

Рисунок 4.1 Окно «Поиск решения» первого этапа

Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат (рис. 4.2): в ячейках В1, С1 и D1 значения переменных x1, x2, x3, соответствующие оптимальному решению: 11,2; 6,4 и 0. В ячейки В2 – значение целевой функции 28,8.

Рисунок 4.2 Решение первого этапа примера 4.1

На втором этапе оптимизируется вторая целевая функция. При этом первую, в соответствие с методом последовательных уступок, можно ухудшить на величину не более чем d1=4. По этой причине, на втором шаге, значения в ячейке В2 (где хранится первая целевая функция, которая максимизируется) может быть не меньшее, чем 28,8–4=24,8. Вызываем надстройку «Сервис/Поиск решения», видим, что все прежние данные остались введенными. Меняем ссылку на целевую функцию. Ставим курсор в поле «Установить целевую» и щелкаем по ячейке С2, в которой находится ссылка на вторую целевую функцию. Так как вторая целевая функция минимизируется, то ставим флажок в поле напротив надписи «Равной минимальному значению». Вводим дополнительное ограничение, связанное с уступкой по первому критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить». В появившемся окне «Добавление ограничения» в трех окнах (слева направо) вводим данные «В2», «≥», «24,8». Результат на рис.4.3.

Рисунок 4.3 Окно «Поиск решения» второго этапа

Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат (рис. 4.4): переменные x1, x2, x3равны 10,2; 4,4; 0. Вторая целевая функция равна 23,4 (ячейка В2). Первая равна своему минимальному значению 24,8 (ячейка С2).

Рисунок 4.4 Решение второго этапа примера 4.1

На третьем этапе делаем уступку по второму критерию. Величина уступки равна d2=5. Так, как вторая функция минимизируется, то ее значение не должно превышать 23,4+5=28,4. Вызываем надстройку «Сервис/Поиск решения». Меняем ссылку на целевую функцию. Ставим курсор в поле «Установить целевую» и щелкаем по ячейке D2, в которой находится ссылка на третью целевую функцию. Так как третья целевая максимизируется, то ставим флажок в поле напротив надписи «Равной максимальному значению». Вводим дополнительное ограничение, связанное с уступкой по второму критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить». В появившемся окне «Добавление ограничения» вводим данные «С2», «≤», «28,4». Результат на рис.4.5.

Рисунок 4.5 Окно «Поиск решения» третьего этапа

Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат (рис. 4.6): переменные x1, x2, x3равны 10,76; 6,62; 1,11. Целевые функции равны, соответственно, 24,8; 28,4 и 6,93. Это окончательный ответ. Все дополнительные условия соблюдены.

Рисунок 4.6 Окончательное решение примера 4.1

Задание 4.1. Решить методом последовательных уступок двухкритериальную задачу, представленную математической моделью:

Уступка по первому критерию оптимизации d1=2.

Значение неизвестного параметра а взять равным номеру варианта.

Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.

Задание 4.2. Молочный комбинат, исследовав конъюнктуру местного рынка, решил выпускать новый вид йогурта, который был бы конкурентно способен. При этом необходимо разработать план организации производства для выпуска данного продукта. Основными затратами на разработку являются затраты на модернизацию оборудование х и затраты на научные исследования у. При исследовании установлено, что себестоимость единицы продукции при этом будет зависеть от затрат как F1(x, y) = 12 + ax + (31а)y, а качество продукции как F2 = 6 + (31а)x + аy. Ставится задача минимизировать себестоимость (цену) данного продукта и максимизировать качество выпускаемой продукции. Из двух целевых функций основной считается цена (себестоимость продукции). По фактору «цена» можно сделать уступку 3 денежные единицы. Решить задачу методом последовательных уступок и найти оптимальные значения факторов х и у, а также значения целевых функций, если на факторы наложены ограничения:

Значение неизвестного параметра а взять равным номеру варианта.

Отчет должен содержать математическую модель задачи, оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ, выводы, какие должны быть затраты на модернизацию оборудования и на научные исследования, какими при этом будет себестоимость и качество продукции.

Задание 4.3. Решить методом последовательных уступок двухкритериальную задачу, представленную математической моделью:

Уступка по первому критерию оптимизации d1 равна номеру варианта а.

Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.

Задание 4.4. Решить методом последовательных уступок трехкритериальную задачу, представленную математической моделью:

Значение неизвестного параметра а взять равным номеру варианта.

Уступки по первому и второму критерию оптимизации равны d1=6,d2=4.

Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.

Задачи многокритериальной оптимизации

В практической деятельности часто встречаются задачи, заключающиеся в поиске лучшего (оптимального) решения при наличии различных несводимых друг к другу критериев оптимальности. Например, принятие решения о строительстве дороги в объезд города должно учитывать такие факторы, как выигрыш города в целом по соображениям экологии, проигрыш отдельных предприятий и фирм, например, из-за уменьшения проезжающих через город потенциальных покупателей и многие другие. Если такого рода задачи решаются методами математического программирования, то говорят о задачах многокритериальной оптимизации. Эти задачи могут носить как линейный, так и нелинейный характер. Поскольку методы решения таких задач излагаются ниже на примере линейных многокритериальных оптимизационных задач, это объясняет рассмотрение этой темы в данной главе учебного пособия.

Читать еще:  Оптимизация сетевых моделей по ресурсам

Задачи многокритериальной оптимизации возникают в тех случаях, когда имеется несколько целей, которые не могут быть отражены одним критерием (например, стоимость и надежность). Требуется найти точку области допустимых решений, которая минимизирует или максимизирует все такие критерии. Если в подобного рода задачах речь идет не о разнородных критериях некоторой системы, а о сопоставлении однородных критериев разных ее подсистем (например, отрасли, группы населения и т.п.), то эти задачи называются задачами векторной оптимизации.

Обозначим 1-й частный критерий через , где — допустимое решение, а область допустимых решений — через Q. Если учесть, что изменением знака функции всегда можно свести задачу минимизации к задаче максимизации, то кратко задачу многокритериальной оптимизации можно сформулировать следующим образом:

(3.28)

(3.29)

Некоторые частные критерии могут противоречить друг другу, другие действуют в одном направлении, третьи — индифферентны, безразличны друг к другу. Поэтому процесс решения многокритериальных задач неизбежно связан с экспертными оценками как самих критериев, так и взаимоотношений между ними. Известен ряд методов решения задач многокритериальной оптимизации:

  • — оптимизация одного признанного наиболее важным критерия, остальные критерии при этом играют роль дополнительных ограничений;
  • — упорядочение заданного множества критериев и последовательная оптимизация по каждому из них (этот подход рассмотрен ниже на примере метода последовательных уступок;
  • — сведение многих критериев к одному введением экспертных весовых коэффициентов для каждого из критериев таким образом, что более важный критерий получает более высокий вес.

Возвращаясь к задаче многокритериальной оптимизации в общей постановке (3.28), (3.29), отмстим, что в идеальном случае можно вести поиск такого решения, которое принадлежит пересечению множеств оптимальных решений всех однокритериальных задач. Однако такое пересечение обычно оказывается пустым множеством, поэтому приходится рассматривать так называемое переговорное множество эффективных решений (оптимальных по Парето). Критерий оптимальности итальянского экономиста В. Парето применяется при решении таких задач, когда оптимизация означает улучшение одних показателей при условии, чтобы другие не ухудшались.

Определение 3.1. Векторназывается эффективным (оптимальным по Парето) решением задачи (3.28), (3.29), если не существует такого вектора , что

(3.30)

причем хотя бы для одного значения i имеет место строгое неравенство.

Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности (т.е. улучшить хотя бы один из них, не ухудшая остальных), принято называть областью Парето, или областью компромиссов, а принадлежащие ей решения — эффективными, или оптимальными по Парето.

В общем случае эффективные решения не эквивалентны друг другу, так что про два оптимальных по Парето решения нельзя сказать, какое из них лучше. Поэтому при решении многокритериальных задач необходимо дополнительное изучение эффективных решений. Для этого можно было бы сформулировать некоторый критерий и оптимизировать его на множестве эффективных решений. Однако при этом возникают значительные трудности в связи с тем, что, как правило, область компромиссов не является выпуклой, и полученная задача в общем случае будет задачей невыпуклого программирования. Обычный подход заключается в стремлении «свернуть» частные критерии в один обобщенный скалярный критерий, оптимизация которого приводит к оптимальному решению задачи в целом. Формулировка подходящего обобщенного критерия в зависимости от конкретных условий как раз и является основным вопросом, который изучается в многокритериальной оптимизации.

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

Рассмотрим один из таких методов решения многокритериальных задач — метод последовательных уступок.

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

Затем, исходя из практических соображений и принятой точности, назначается величина допустимого отклонения 8, > 0 (экономически оправданной уступки) критерия Z, и находится максимальное значение второго критерия Z’2 при условии, что значение первого критерия не должно отклоняться от своего максимального значения более чем на величину допустимой уступки, т.е. решается задача:

Снова назначается величина уступки δ2 > 0 по второму критерию, которая вместе с первой уступкой используется для нахождения условного максимума третьего частого критерия:

Аналогичные процедуры повторяются до тех пор, пока не будет выявлено максимальное значение последнего по важности критерия Zm при условии, что значение каждого из первых т — 1 частных критериев отличается от соответствующего условного максимума не более чем на величину допустимой уступки по данному критерию. Полученное на последнем этапе решение считается оптимальным. Следует заметить, что этот метод не всегда приводит к эффективному решению.

Пример 3.7. Решение задачи многокритериальной оптимизации методом последовательных уступок.

Решение. Пусть задача трехкритериальной оптимизации имеет вид

(3.31)

(3.32)

(3.33)

(3.34)

Заметим, что так как коэффициенты при одних и тех же переменных в данных частных критериях имеют разные знаки, то в заданной области допустимых решений невозможно одновременно улучшить все частные критерии, т.е. в рассматриваемом случае область компромиссов (область Парето) совпадает с областью допустимых решений (3.34).

Для определенности будем считать, что допустимые уступки по первым двум критериям заданы: δ1 = 3; δ3 = 5/3.

Максимизируем функцию Z3 в области допустимых решений, т.е. решаем одну критериальную задачу (3.31), (3.34). Это несложно сделать рассмотренным в главе 2 графическим методом решения задач линейного программирования (рис. 3.3).

Рис. 3.3

Максимум функции Z1 при условиях (3.34) достигается в точке А области Q с координатами (1; 4), так что в данном случае

Переходим к максимизации функции Z, при условиях (3.34) и дополнительном ограничении, позволяющем учесть, что по критерию Z, нельзя уступать более чем на δ1. Так как в нашем примере , то дополнительное ограничение будет иметь вид

(3.35)

Задачу (3.32), (3.34), (3.35) также решаем графически (рис. 3.4).

Получаем, что максимум функции Z2 при условиях (3.34), (3.35) достигается в точке В части Q, области Q, так что

Теперь уступаем по критерию Z2 на величину уступки 52= 5/3 и получаем второе дополнительное ограничение:

(3.36)

Максимизируем функцию Z3 при условиях (3.34), (3.35) и (3.36). Решение этой задачи представлено на рис 3.5.

Рис. 3.4

Рис. 3.5

Таким образом, получаем оптимальное решение рассматриваемой трехкритериальной задачи (точка С на рис. 3.5):

Соответствующие значения частных критериев при этом составляют:

Z1 = 4; Z2 = 7; Z3 = -7.

Задачи многокритериальной оптимизации

В практической деятельности часто встречаются задачи, заключающиеся в поиске лучшего (оптимального) решения при наличии различных несводимых друг к другу критериев оптимальности. Например, принятие решения о строительстве дороги в объезд города должно учитывать такие факторы, как выигрыш города в целом по соображениям экологии, проигрыш отдельных предприятий и фирм, например, из-за уменьшения проезжающих через город потенциальных покупателей и многие другие. Если такого рода задачи решаются методами математического программирования, то говорят о задачах многокритериальной оптимизации. Эти задачи могут носить как линейный, так и нелинейный характер. Поскольку методы решения таких задач излагаются ниже на примере линейных многокритериальных оптимизационных задач, это объясняет рассмотрение этой темы в данной главе учебного пособия.

Задачи многокритериальной оптимизации возникают в тех случаях, когда имеется несколько целей, которые не могут быть отражены одним критерием (например, стоимость и надежность). Требуется найти точку области допустимых решений, которая минимизирует или максимизирует все такие критерии. Если в подобного рода задачах речь идет не о разнородных критериях некоторой системы, а о сопоставлении однородных критериев разных ее подсистем (например, отрасли, группы населения и т.п.), то эти задачи называются задачами векторной оптимизации.

Обозначим 1-й частный критерий через , где — допустимое решение, а область допустимых решений — через Q. Если учесть, что изменением знака функции всегда можно свести задачу минимизации к задаче максимизации, то кратко задачу многокритериальной оптимизации можно сформулировать следующим образом:

(3.28)

(3.29)

Некоторые частные критерии могут противоречить друг другу, другие действуют в одном направлении, третьи — индифферентны, безразличны друг к другу. Поэтому процесс решения многокритериальных задач неизбежно связан с экспертными оценками как самих критериев, так и взаимоотношений между ними. Известен ряд методов решения задач многокритериальной оптимизации:

  • — оптимизация одного признанного наиболее важным критерия, остальные критерии при этом играют роль дополнительных ограничений;
  • — упорядочение заданного множества критериев и последовательная оптимизация по каждому из них (этот подход рассмотрен ниже на примере метода последовательных уступок;
  • — сведение многих критериев к одному введением экспертных весовых коэффициентов для каждого из критериев таким образом, что более важный критерий получает более высокий вес.
Читать еще:  Операционная система linux какую выбрать

Возвращаясь к задаче многокритериальной оптимизации в общей постановке (3.28), (3.29), отмстим, что в идеальном случае можно вести поиск такого решения, которое принадлежит пересечению множеств оптимальных решений всех однокритериальных задач. Однако такое пересечение обычно оказывается пустым множеством, поэтому приходится рассматривать так называемое переговорное множество эффективных решений (оптимальных по Парето). Критерий оптимальности итальянского экономиста В. Парето применяется при решении таких задач, когда оптимизация означает улучшение одних показателей при условии, чтобы другие не ухудшались.

Определение 3.1. Векторназывается эффективным (оптимальным по Парето) решением задачи (3.28), (3.29), если не существует такого вектора , что

(3.30)

причем хотя бы для одного значения i имеет место строгое неравенство.

Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности (т.е. улучшить хотя бы один из них, не ухудшая остальных), принято называть областью Парето, или областью компромиссов, а принадлежащие ей решения — эффективными, или оптимальными по Парето.

В общем случае эффективные решения не эквивалентны друг другу, так что про два оптимальных по Парето решения нельзя сказать, какое из них лучше. Поэтому при решении многокритериальных задач необходимо дополнительное изучение эффективных решений. Для этого можно было бы сформулировать некоторый критерий и оптимизировать его на множестве эффективных решений. Однако при этом возникают значительные трудности в связи с тем, что, как правило, область компромиссов не является выпуклой, и полученная задача в общем случае будет задачей невыпуклого программирования. Обычный подход заключается в стремлении «свернуть» частные критерии в один обобщенный скалярный критерий, оптимизация которого приводит к оптимальному решению задачи в целом. Формулировка подходящего обобщенного критерия в зависимости от конкретных условий как раз и является основным вопросом, который изучается в многокритериальной оптимизации.

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

Рассмотрим один из таких методов решения многокритериальных задач — метод последовательных уступок.

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

Затем, исходя из практических соображений и принятой точности, назначается величина допустимого отклонения 8, > 0 (экономически оправданной уступки) критерия Z, и находится максимальное значение второго критерия Z’2 при условии, что значение первого критерия не должно отклоняться от своего максимального значения более чем на величину допустимой уступки, т.е. решается задача:

Снова назначается величина уступки δ2 > 0 по второму критерию, которая вместе с первой уступкой используется для нахождения условного максимума третьего частого критерия:

Аналогичные процедуры повторяются до тех пор, пока не будет выявлено максимальное значение последнего по важности критерия Zm при условии, что значение каждого из первых т — 1 частных критериев отличается от соответствующего условного максимума не более чем на величину допустимой уступки по данному критерию. Полученное на последнем этапе решение считается оптимальным. Следует заметить, что этот метод не всегда приводит к эффективному решению.

Пример 3.7. Решение задачи многокритериальной оптимизации методом последовательных уступок.

Решение. Пусть задача трехкритериальной оптимизации имеет вид

(3.31)

(3.32)

(3.33)

(3.34)

Заметим, что так как коэффициенты при одних и тех же переменных в данных частных критериях имеют разные знаки, то в заданной области допустимых решений невозможно одновременно улучшить все частные критерии, т.е. в рассматриваемом случае область компромиссов (область Парето) совпадает с областью допустимых решений (3.34).

Для определенности будем считать, что допустимые уступки по первым двум критериям заданы: δ1 = 3; δ3 = 5/3.

Максимизируем функцию Z3 в области допустимых решений, т.е. решаем одну критериальную задачу (3.31), (3.34). Это несложно сделать рассмотренным в главе 2 графическим методом решения задач линейного программирования (рис. 3.3).

Рис. 3.3

Максимум функции Z1 при условиях (3.34) достигается в точке А области Q с координатами (1; 4), так что в данном случае

Переходим к максимизации функции Z, при условиях (3.34) и дополнительном ограничении, позволяющем учесть, что по критерию Z, нельзя уступать более чем на δ1. Так как в нашем примере , то дополнительное ограничение будет иметь вид

(3.35)

Задачу (3.32), (3.34), (3.35) также решаем графически (рис. 3.4).

Получаем, что максимум функции Z2 при условиях (3.34), (3.35) достигается в точке В части Q, области Q, так что

Теперь уступаем по критерию Z2 на величину уступки 52= 5/3 и получаем второе дополнительное ограничение:

(3.36)

Максимизируем функцию Z3 при условиях (3.34), (3.35) и (3.36). Решение этой задачи представлено на рис 3.5.

Рис. 3.4

Рис. 3.5

Таким образом, получаем оптимальное решение рассматриваемой трехкритериальной задачи (точка С на рис. 3.5):

Соответствующие значения частных критериев при этом составляют:

Z1 = 4; Z2 = 7; Z3 = -7.

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

На предприятии необходимо выполнить последовательно 6 видов работ (R1÷R6). 6 сотрудников предприятия (S1÷S6) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения. Составить экономико-математическую модель задачи и решить задачу с помощью венгерского алгоритма.

Составляем экономико-математическую модель задачи

1. Форматируем задачу в виде транспортной таблицы

2. Выполним приведение матрицы

3. Произведем назначение каждого сотрудника на один из видов работ:

4. Решение не оптимально, невозможно назначить всех сотрудников на выполнение работ.

5. Делаем дальнейшее преобразование матрицы

Минимальное число, через которое не проходит ни одна линия 0,5.

6. Составляем новую матрицу

7. Производим новые назначения

9. Решение

Оптимально и единственно.

Время, затрачиваемое на выполнение всех работ, составит 7+3+1+5,5+2+0,7=19,2 часов.

Пример решения задачи методом множителей Лагранжа

Потребитель имеет финансовые средства в объёме 360 условных денежных единиц, которые он готов потратить на приобретение двух видов продукции А1 и А2. При известных ценах за единицу каждого вида продукций Р1=3 усл.ден.ед. и Р2=4усл.ден.ед. (соответственно) найти такое количество продукций видов А1 и А2, которые может приобрести потребитель, максимизируя свою полезность U(x1;x2)=x1 4/5 *x2 1/5 , где х1 – количество продукта вида А1, х2 – количество продукта вида А2. При этом потребитель должен использовать финансовые средства в полном объёме.

Составляем экономико-математическую модель задачи:

Составляем функцию Лагранжа:

Находим частные производные от функции Лагранжа по трём переменным:

Составляем систему уравнений, приравняв производные нулю:

Для решения системы уравнений преобразуем два первых равенства:

Разделив первое равенство на второе, и выполнив алгебраические преобразования, получаем:

Выразив х1 = (16/3)*х2, из третьего уравнения получаем х2 = 96 и х1 =18.

В итоге решением этой системы уравнений является:

х1 = 96; х2 = 18; λ = -1.4 и значение функции полезности U(x1,x2) = 68.6

Найдём значение функции полезности в любой другой точке, удовлетворяющей ограничениям ЭММ задачи.

Возьмём точку (120; 0). Значение U(120; 0) = 0.

Значит, в точке (96; 18) функция полезности достигает своего максимума .Т.о., чтобы максимизировать свою функцию полезности потребитель должен приобрести продукции вида А1 — 96 усл.ед. и продукции вида А2 — 18 усл.ед.

Организация выпускает 3 вида продукции видов Р1, Р2, Р3. В производстве используется 4 вида основного сырья А1, А2 , А3, А4. В таблице даны: запасы сырья, затраты каждого вида сырья (усл.ед) на производство 1 усл.ед. каждого вида продукции, цены и себестоимость 1 усл.ед. каждого вида продукции. По одному из видов продукции были проведены маркетинговые исследования на предмет определения спроса на данный вид продукции (минимальный объём выпуска). Найти оптимальные объёмы выпуска каждого вида продукции, что бы прибыль и объём выпуска продукции были бы максимальны, а себестоимость каждого вида продукции – минимальна.

9 Многокритериальные задачи

Постановка задачи линейного программирования. Математическая модель задачи. Примеры задач линейного программирования. Графический метод решения задачи. Симплекс– метод решения задачи линейного программирования. Анализ решения задачи линейного программирования.

Читать еще:  Однокритериальная и многокритериальная оптимизация

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

Каждая из сравниваемых альтернатив характеризуются некоторыми показателями. Часть этих показателей выступает в качестве критериев при отборе альтернативы из множества других. Так, при оценке технического изделия основными критериями оценки служат его технические характеристики, а также такие качества, как надежность, эргономичность, внешний вид. При выборе кандидата на должность важнейшими критериями оценки являются квалификация, образование, эрудиция, возраст, коммуникабельность и т.п. В экономических задачах основными критериями служат экономическая эффективность и стоимость, при этом каждый из этих критериев, в свою очередь, может быть подразделен на более частные критерии. Считается, что

n показатели-критерии являются одноименными для всех альтернатив и их количество у всех альтернатив одинаковое;

n другие показатели альтернатив либо одинаковы, либо несущественны в данной задаче.

Если альтернативы оцениваются по m критериям, где m > 1, то такая задача принятия решений называется многокритериальной.

Критерий называется позитивным, если необходимо стремиться к его увеличению, и негативным, если необходимо стремиться к его уменьшению. В конкретных задачах принятия решений характер критерия устанавливается по содержательным соображениям. Преобразование негативного критерия в позитивный (и наоборот) можно осуществить заменой знака. При рассмотрении многокритериальных задач в общем виде, если не оговорено противное, предполагается, что все имеющиеся критерии являются позитивными. В многокритериальной задаче с позитивными критериями цель— получение альтернативы, имеющей как можно более высокие оценки по каждому критерию.

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

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

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

Предположим, что при оценке альтернатив использовались два критерия: стоимость (К1) и надежность (К2). Значения критериев для трех альтернатив представлены в таблице.

Очевидно, что альтернатива 3 является наиболее предпочтительной, так как она не хуже остальных альтернатив по всем критериям.

Альтернатива ai является доминирующей по отношению к альтернативе ak, если по всем критериям оценки альтернативы ai не хуже, чем альтернативы ak, а хотя бы по одному критерию оценка ai лучше. При этом альтернатива ak называется доминируемой. Из определения следует, что альтернатива 3 из приведенного выше примера является доминирующей по отношению к альтернативе 1 и альтернативе 2. Это можно увидеть из рис. 1, где альтернатива 3 занимает самое правое и верхнее положение по отношению к другим альтернативам.

Рассмотрим теперь альтернативы 1 и 2. Из рис. 1 также следует, что альтернативы 1 и 2 не находятся в отношении доминирования. Действительно, по стоимости предпочтительнее альтернатива 1, а по надежности — альтернатива 2. Эти альтернативы являются несравнимыми по отношению предпочтения между векторными оценками, так как их невозможно сравнить непосредственно на основе критериальных оценок. Множество несравнимых альтернатив образуют область эффективных решений и называется множеством Парето, а альтернативы, образующие это множество Парето-оптимальными. Если вернуться к примеру, то оставшиеся альтернативы 1 и 2 принадлежат множеству Парето.

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

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

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

Второй подход. Производится сужение множества Парето-оптимальных альтернатив (в идеале — до одной) с помощью некоторых формализованных процедур, что облегчает окончательный выбор альтернативы для лица, принимающего решение. Отметим, что такое сужение может быть произведено только при наличии дополнительной информации о критериях или о свойствах оптимального решения.

Рассмотрим некоторые простейшие способы сужения Парето-оптимального множества, акцентируя при этом внимание на необходимой дополнительной информации.

1. Указание нижних границ критериев. Набор оценок нижних границ по каждому критерию представляет собой дополнительную информацию. При указании нижних границ критериев оптимальной может считаться только такая Парето-оптимальная альтернатива, для которой оценка по каждому из критериев не ниже назначенной оценки. Это приводит к сужению Парето-оптимального множества.

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

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

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

С помощью метода субоптимизации задача многокритериальной оптимизации превращается в задачу скалярной оптимизации на суженном допустимом множестве. Выделение одного из критериев, а также указание нижних границ для остальных критериев основано на дополнительной информации, получаемой от принимающего решение. Следовательно, окончательное решение здесь также имеет субъективный характер.

3. Лексикографическая оптимизация. Этот метод основан на упорядочении критериев по их относительной важности. После этого процедуру нахождения оптимального решения проводят следующим образом. На первом шаге отбирают исходы, которые имеют максимальную оценку по важнейшему критерию. Если такой исход единственный, То его и считают оптимальным. Если же таких исходов несколько, То среди них отбирают те, которые имеют максимальную оценку по следующему за важнейшим критерию и т. д. В результате такой процедуры всегда остается (по крайней мере, в случае конечного множества исходов) единственный исход — он и будет оптимальным.

Термин «лексикографический» отражает аналогию между этим методом и методом упорядочивания слов в словаре. При лексикографическом подходе требуется ранжирование показателей по важности, а значения показателей располагаются на шкале порядка. После того как важнейший показатель выбран, может быть определена альтернатива, имеющая наивысшее значение по этому показателю. Если такая альтернатива одна, то ее выбирают и процедура заканчивается. Если по определенному показателю имеется несколько альтернатив с одним и тем же наивысшим значением, то они сравниваются по второму по важности показателю. Процесс продолжается таким образом до тех пор, пока не будет выявлена единственная альтернатива, или пока не будут проверены все показа-ели.

Основными недостатками метода лексикографической оптимизации являются следующие.

n При практическом применении данного метода возникают трудности в установлении полной упорядоченности критериев по их относительной важности.

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

Проиллюстрируем рассмотренные в этом пункте методы нахождения оптимального решения в многокритериальных ЗПР на следующем примере.

Пример. Выбор места работы. Предположим, что Вам предстоит выбрать место работы из девяти вариантов, представленных в табл. 5.1. В качестве основных критериев взяты: зарплата 3, длительность отпуска Д, время поездки на работу В. Так как критерий В имеет характер потерь, оценки по этому критерию берутся со знаком «минус». Какой вариант является оптимальным?

Ссылка на основную публикацию
Adblock
detector