Всероссийский заочный финансово-экономический институт Кафедра экономико-математический методов и моделей Тема: Решение многокритериальных задач линейного программирования методом последовательных уступок в Excel Работу выполнила:студентка 3-го курса спец. Финансы и кредит Сущевская Лилия С. Руководитель:к.т.н., доц.Уродовских Виктор Николаевич

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

метод последова- тельных уступок Наиболее эффективным методом решения много- критериальных задач является метод последова- тельных уступок. Он применяется, когда частные критерии (Ц.Ф.) могут быть упорядочены в порядке убывающей важности. Предположим, что все критерии максимизируются и пронумерованы в порядке убывания их важности. Находим максимальное значение Z 1, первого по важности критерия в области допустимых решений, решив задачу Затем исходя из практических соображений и принятой точности, назначается допустимое отклонение (экономически оправданная уступка) критерия Z 1 и отыскивается максимальное значение второго критерия Z 2 при условии, что значение первого должно отклоняться от максимального не более чем на величину допустимой уступки.

Далее решается задача Затем снова назначается величина уступки по второму критерию, которая вместе с первой использу- ется при нахождении условного экстремума третьего частного критерия, и т.д. В конце, выявляется экстремальное значение последнего по важности критерия Z m при условии, что значение каждого из первых m-1 частных критериев отличается от экстремального не более чем на величину допустимой уступки. Полученное на последнем этапе решение считается оптимальным. Недостаток – метод не всегда дает эффективное решение.

ПРИМЕР 1. Найти оптимальное решение для трехкритериальной задачи:

Оптимальное решение найти методом последовательных уступок, выбрав уступку по первому критерию 1 = 4, а по второму 2 = 5. Алгоритм решения задачи Алгоритм решения задачи. 1. Вначале решаем однокритериальную задачу с первой целевой функцией. В ячейку С1 записываем «Переменные», а в ячейку А3 - «значение». В соседние три ячейки В3, С3 и D3 вводим произвольные числа для переменных (Х1, Х2, Х3), например, единицы. В дальнейшем эти числа будут оптимизироваться.

2. В следующей строке задаем целевые функции. В А4 вводим подпись «Целевые», а в В4 формулу «= 2*B3 + C3 - 3*D3» задаем первую целе- вую функцию. Аналогично в ячейку С4 вводим вторую целевую функцию «= B3+3*C3-2*D3», и в ячейку третью D4 – третью «= - B3+2*C3+4*D3 ».

3. В следующую строку вводим левые части ограничений. Для этого в А5 вводим подпись «Ограничения», в В5 формулу «=B3+3*C3+2*D3», в С5 формулу «=2*B3- C3+D3» и в D5 формулу «=B3+2*C3».

4. Вызываем надстройку «Поиск решения» (Solver). После открытия окна «Поиск решения» в поле «Установить целевую ячейку» ставим курсор и делаем ссылку на ячейку В4, щелкая по ней мышью. Поскольку целевая функция максимизируется, то нужно убедиться в том, что флажок стоит напротив надписи «Равной: максимальному значению».

Затем ставим курсор в поле «Изменяя ячейки» и выделяем блок ячеек В3, С3 и D3 с переменными. В поле появиться $B$3:$D$3. В поле «Ограничения» нажатием кнопки «Добавить» поочередно вводятся ссылки на ограничения – ячейку В5, в центральном окне определяем знак и в правом «Ограничения» набираем правую часть ограничения – число 1. Аналогично вводим «С5» « » и «16». Вновь нажимаем «Добавить», вводим «D5» «» и «24». Для ввода дополнительных ограничений (условия неотрицательности) нажимаем «Добавить», ставим курсор в левое поле и обводим ячейки В3, С3 и D3 (результат $B$3:$D$3) в среднем окне ставим « » и в правом число 0.

Для запуска вычислений нажимаем кнопку «Выполнить».

В открывшемся диалоговом окне «Результаты поиска решения» выбираем «Сохранить найденное решение» (Keep Solver Solution) и подтверждаем «ОК». В ячейках В3, С3 и D3 находятся оптимальные значения переменных: 11,2; 6,4 и 0. В ячейки В4 – значение целевой функции 28,8.

5. После этого оптимизируется вторая целевая функция. При этом первую Ц.Ф., в соответствии с методом последовательных уступок можно ухудшить на величину не более, чем 1= 4. С учетом этого значение в ячейке В4 (где хранится первая целевая функция) может быть не меньшее, чем 28,8 – 4 = 24,8. Далее вызываем надстройку «Поиск решения», в ней все данные остались прежними. Меняем ссылку на целевую функцию. Ставим курсор в поле «Установить целевую ячейку» и щелкаем по ячейке С4, в которой находится ссылка на вторую целевую функцию. Поскольку вторая целевая функция миними- зируется, то ставим флажок напротив надписи «Равной минимальному значению».

В поле «Ограничения» нажимаем кнопку «Добавить» и вводим дополнительное ограничение, связанное с уступкой по первому критерию. В появившемся окне «Добавление ограничения» в трех окнах (слева на право) вводим данные «В4», «», «24,8».

В результате решения – переменные равны 10,2; 4,4; 0. Вторая целевая функция равна 23,4 (ячейка С4). Первая равна своему минимальному значению 24,8 (ячейка В4).

6. На третьем этапе делаем уступку по второму крите- рию, равную 2 = 5. Поскольку вторая функция минимизируется, то ее значение не должно превышать 23,4 + 5 = 28,4. Вызываем надстройку «Поиск решения» и меняем ссылку на целевую функцию. Для этого ставим курсор в поле «Установить целевую ячейку» и щелкаем по ячейке D4, содержащую третью целевую функцию. Поскольку третья Ц.Ф. максимизируется, то ставим флажок в поле напротив надписи «Равной максималь- ному значению». В поле «Ограничения» и нажимаем кнопку «Добавить» вводим дополнительное ограничение с учетом уступки по второму критерию. В окне «Добавление ограничения» вводим данные «С4», «», «28,4».

В поле «Ограничения» нажимаем кнопки «Добавить» вводим дополнительное ограничение с учетом уступки по второму критерию. В окне «Добавление ограничения» вводим данные «С4», «», «28,4».

В результате расчета найдены: X 1 = 10,76; X 2 = 6,62; X 3 = 1,11. Целевые функции равны: max Z 1 = 24,8 ; min Z 2 = 28,4 и max Z 3 = 28,4, при удовлетворении всех ограничений