Решение задач многокритериальной оптимизации на эвм
Цель: научиться методам решения многокритериальных ЗЛП с помощью ЭВМ, используя метод последовательных уступок.
Во многих реальных экономических задачах критериев, которые оптимизируются, может быть несколько. Например, при производстве продукции максимизируется качество и минимизируется себестоимость, при взятии ссуды в банке максимизируется кредитный срок и минимизируется процентная ставка, при выборе места для строительства дома отдыха максимизируются экологические условия и минимизируется расстояние от населенного пункта и пр.
Существует несколько методов решения многокритериальных задач. Одним из наиболее эффективных является метод последовательных уступок, использование которого рассмотрим на примере.
ПРИМЕР 4.1.Математическая модель трехкритериальной задачи имеет вид:
Z1=2x1+ x2– 3x3→max;
Z2= x1+ 3x2– 2x3→min;
Z3= –x1+ 2x2+4x3→max;
x1+ 3x2+2x3≥1,
2x1–x2+x3≤16,
x1+ 2x2≤24,
x1, x2, x3 ≥0.
Решить задачу методом последовательных уступок, выбрав уступку по первому критерию 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, x3≥0 вновь нажимаем «Добавить», ставим курсор в левое поле и обводим ячейки В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. Решить методом последовательных уступок двухкритериальную задачу, представленную математической моделью:
Z1=x1–3x2→ max;
Z2=аx1–2x2→ min;
3x1+ 5x2≥2,
x1+x2≤11,
x1–x2≤ –1,
x1, x2 ≥0.
Уступка по первому критерию оптимизации d1=2.
Значение неизвестного параметра а взять равным номеру варианта.
Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.
Задание 4.2. Молочный комбинат, исследовав конъюнктуру местного рынка, решил выпускать новый вид йогурта, который был бы конкурентно способен. При этом необходимо разработать план организации производства для выпуска данного продукта. Основными затратами на разработку являются затраты на модернизацию оборудование х и затраты на научные исследования у. При исследовании установлено, что себестоимость единицы продукции при этом будет зависеть от затрат как F1(x, y) = 12 + ax + (31-а)y, а качество продукции как F2 = 6 + (31-а)x + аy. Ставится задача минимизировать себестоимость (цену) данного продукта и максимизировать качество выпускаемой продукции. Из двух целевых функций основной считается цена (себестоимость продукции). По фактору «цена» можно сделать уступку 3 денежные единицы. Решить задачу методом последовательных уступок и найти оптимальные значения факторов х и у, а также значения целевых функций, если на факторы наложены ограничения:
2х+у ≥8;
5х+ 4у ≤40;
0≤х ≤6; у≥0.
Значение неизвестного параметра а взять равным номеру варианта.
Отчет должен содержать математическую модель задачи, оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ, выводы, какие должны быть затраты на модернизацию оборудования и на научные исследования, какими при этом будет себестоимость и качество продукции.
Задание 4.3. Решить методом последовательных уступок двухкритериальную задачу, представленную математической моделью:
Z1=2x1+ x2– 5x3→ max;
Z2=3x1+ 2x2– 4x3→ min;
4x1+ 6x2+5x3≥2,
–2x1+x2–3x3≤27,
6x1+ 5x2≤75,
2x1+ 3x3≥3,
x1 ,x2 ,x3 ≥0.
Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.
Задание 4.4. Решить методом последовательных уступок трехкритериальную задачу, представленную математической моделью:
Z1= –x1+3 x2– 2x3→ min;
Z2=–3x1+ 2x2– x3→ max;
Z3=x1+ 2x2+4x3→ max;
3x1+ 2x2+ax3≥1,
x1+аx2+x3≤19,
аx1+ 3x2≤21,
x1 ,x2 ,x3 ≥0.
Значение неизвестного параметра а взять равным номеру варианта.
Уступки по первому и второму критерию оптимизации равны d1=6,d2=4.
Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.
Работа № 5