Модели и методы многоцелевой оптимизации

Типовая таблица исходных данных.

1. Сведем исходные данные в типовую таблицу, характерную для данного класса задач:

Таблица 1.2. Типовая таблица исходных данных.

Характеристика производства.	Технология производства.	Лимит.
Т1.	Т2.
Норма вложений в ед. времени.
Объем.
Качество.
Ресурсы.
Сырьё.
Электроэнергия.	0,8.	0,7.

2. Введем обозначения искомых переменных.

х₁ — время выпуска продукции по технологии Т1, ед. времени;

х₂ — время выпуска продукции по технологии Т2, ед.времени.

Решение задачи графическим методом Этап 1. В качестве критерия оптимальности выступает объём выпуска продукции V. Качество К задано набором предельных значений (табл. 1.1.):

К_пред=100 000; 120 000; 150 000.

1. Составим математическую модель:

Ц.Ф.: V=700х₁+300х₂ max.

ОГР: 100х₁+900х₂? К_пред (1).

• 5х₁+8х₂? 4000 (2)
• 0,8х₁+0,7х₂? 560 (3)

ГРУ: х₁? 0, х₂? 0 (4).

• 2. Произведем решение задачи по стандартному алгоритму:
• 1) Решение без учета К_пред:
  • — построение области допустимых значений (ОДР):

Таблица 1.3. Расчет ОДР.

ОГР.	х1.	х2.
Кпред.	не учитывается.
5х1+8×2? 4000.	х2=0.	х1=0.
х1.	х2.
0,8×1+0,7×2? 560.	х2=0.	х1=0.
х1.	х2.
ГРУ.	х1? 0.	х2? 0.

Отобразим на плоскости неравенства (2)-(4). Полученный четырехугольник ОАВС является ОДР.

— построение линии уровня Ц.Ф.

Зададимся произвольными значениями Ц.Ф.:

V (x)=105 000;

V=700x₁+300x₂=105 000;

х₁=0 => х₂=350;

х₂=0 => х₁=150.

Построим линии уровня и найдем решение задачи (рис. 1.):

Решение задачи лежит в точке С с координатами:

х₁=700 ед. времени — время выпуска продукции по технологии Т1;

х₂=0 ед. времени — время выпуска продукции по технологии Т2;

V=700*700+300*0=490 000 ед. продукции — объём выпуска.

2) Решение с учетом К_пред:

Нанесем на полученный рисунок ещё 3 линии, соответствующие ограничению (1):

Таблица 1.4. Расчет ограничений по К_пред

ОГР.	Кпред.	х1.	х2.
100×1+900×2? Кпред.	100 000.	х2=0.	х1=0.
х1.	х2.
120 000.	х2=0.	х1=0.
х1.	х2.
150 000.	х2=0.	х1=0.
х1.	х2.

При К_пред=100 000 решение находится в точке С₁ с координатами:

х₁=660 ед. времени — время выпуска продукции по технологии Т1;

х₂=40 ед. времени — время выпуска продукции по технологии Т2;

V=700*660+300*40=474 000 ед. продукции — объём выпуска.

При К_пред=120 000 решение находится в точке С₂ с координатами:

х₁=640 ед. времени — время выпуска продукции по технологии Т1;

х₂=70 ед. времени — время выпуска продукции по технологии Т2;

V=700*640+300*70=469 000 ед. продукции — объём выпуска.

При К_пред=150 000 решение находится в точке С₃ с координатами:

х₁=610 ед. времени — время выпуска продукции по технологии Т1;

х₂=100 ед. времени — время выпуска продукции по технологии Т2;

V=700*610+300*100=457 000 ед. продукции — объём выпуска.

Вывод: без учета качества, объём производимой продукции получился наибольшим. При учете качества видно, что, чем выше качество выпускаемой продукции, тем меньше его объём. Таким образом, решение задачи соответствует реальным условиям производства.

Этап 2. В качестве критерия оптимальности выступает качество выпускаемой продукции К. Объём V задан набором предельных значений (табл. 1.1.):

V_пред=220 000; 250 000; 300 000.

1. Составим математическую модель:

Ц.Ф.: К=100х₁+900х₂ max.

ОГР: 700х₁+300х₂? V_пред (1).

• 5х₁+8х₂? 4000 (2)
• 0,8х₁+0,7х₂? 560 (3)

ГРУ: х₁? 0, х₂? 0 (4).

• 2. Произведем решение задачи по стандартному алгоритму:
• 1) Решение без учета V_пред:
  • — построение области допустимых значений (ОДР):

Таблица 1.5. Расчет ОДР.

ОГР.	х1.	х2.
Vпред.	не учитывается.
5х1+8×2? 4000.	х2=0.	х1=0.
х1.	х2.
0,8×1+0,7×2? 560.	х2=0.	х1=0.
х1.	х2.
ГРУ.	х1? 0.	х2? 0.

Отобразим на плоскости неравенства (2)-(4). Полученный четырехугольник ОАВС является ОДР.

— построение линии уровня Ц.Ф.

Зададимся произвольными значениями Ц.Ф.:

К (x)=45 000;

К=100x₁+900x₂=45 000;

х₁=0 => х₂=50;

х₂=0 => х₁=450.

Построим линии уровня и найдем решение задачи (рис. 2.):

Решение задачи лежит в точке, А с координатами:

х₁=0 ед. времени — время выпуска продукции по технологии Т1;

х₂=500 ед. времени — время выпуска продукции по технологии Т2;

К=100*0+900*500=450 000 — качество продукции.

2) Решение с учетом V_пред:

Нанесем на полученный рисунок ещё 3 линии, соответствующие ограничению (1):

Таблица 1.6. Расчет ограничений по V_пред

ОГР.	Vпред.	х1.	х2.
700×1+300×2? Vпред.	220 000.	х2=0.	х1=0.
х1.	х2.
250 000.	х2=0.	х1=0.
х1.	х2.
300 000.	х2=0.	х1=0.
х1.	х2.

При V_пред=220 000 решение задачи лежит в точке А₁ с координатами:

х₁=140 ед. времени — время выпуска продукции по технологии Т1;

х₂=420 ед. времени — время выпуска продукции по технологии Т2;

К=100*140+900*420=392 000 — качество продукции.

При V_пред=250 000 решение задачи лежит в точке А₂ с координатами:

х₁=190 ед. времени — время выпуска продукции по технологии Т1;

х₂=380 ед. времени — время выпуска продукции по технологии Т2;

К=100*190+900*380=361 000 — качество продукции.

При V_пред=300 000 решение задачи лежит в точке А₃ с координатами:

х₁=290 ед. времени — время выпуска продукции по технологии Т1;

х₂=320 ед. времени — время выпуска продукции по технологии Т2;

К=100*290+900*320=317 000 — качество продукции.

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

Построение кривой компромиссных решений По полученным данным построим график зависимости объёма производимой продукции от его качества — кривая альтернативных решений, оптимальных по Парето:

V.	220 000.	250 000.	300 000.	457 000.	469 000.	474 000.
K.	392 000.	361 000.	317 000.	150 000.	120 000.	100 000.

Рис. 3. Кривая компромиссных решений.

II. Решение задачи многоцелевой оптимизации с использованием среды microsoft excel.

Решим ту же задачу, но с использованием программной среды Microsoft Excel. Метод решения остался прежним.

На первом этапе предпочтение отдается объёму V как основной характеристике производства. Математическая модель при этом уже была сформулирована ранее:

Ц.Ф.: V=700х₁+300х₂ max.

ОГР: 100х₁+900х₂? К_пред (1).

• 5х₁+8х₂? 4000 (2)
• 0,8х₁+0,7х₂? 560 (3)

ГРУ: х₁? 0, х₂? 0 (4).

На втором этапе предпочтение отдается качеству К как основной характеристике производства. Математическая модель при этом также уже была сформулирована ранее:

Ц.Ф.: К=100х₁+900х₂ max.

ОГР: 700х₁+300х₂? V_пред (1).

• 5х₁+8х₂? 4000 (2)
• 0,8х₁+0,7х₂? 560 (3)

ГРУ: х₁? 0, х₂? 0 (4).

Запишем полученные математические модели в программе Microsoft Excel и найдем решение с помощью надстройки «Поиск решения». Результат представлен ниже:

оптимизация график вычисление кривая.

Таким образом, получен следующий результат:

На первом этапе:

При К_пред=100 000 решение находится в точке С₁ с координатами:

х₁=667,69 ед. времени — время выпуска продукции по технологии Т1;

х₂=36,92 ед. времени — время выпуска продукции по технологии Т2;

V=478 462 ед. продукции — объём выпуска.

При К_пред=120 000 решение находится в точке С₂ с координатами:

х₁=646,15 ед. времени — время выпуска продукции по технологии Т1;

х₂=61,54 ед. времени — время выпуска продукции по технологии Т2;

V=470 769 ед. продукции — объём выпуска.

При К_пред=150 000 решение находится в точке С₃ с координатами:

х₁=613,85 ед. времени — время выпуска продукции по технологии Т1;

х₂=98,46 ед. времени — время выпуска продукции по технологии Т2;

V=459 231 ед. продукции — объём выпуска.

На втором этапе:

При V_пред=220 000 решение задачи лежит в точке А₁ с координатами:

х₁=136,59 ед. времени — время выпуска продукции по технологии Т1;

х₂=414,63 ед. времени — время выпуска продукции по технологии Т2;

К=386 829,3 — качество продукции.

При V_пред=250 000 решение задачи лежит в точке А₂ с координатами:

х₁=195,12 ед. времени — время выпуска продукции по технологии Т1;

х₂=378,05 ед. времени — время выпуска продукции по технологии Т2;

К=359 756,1 — качество продукции.

При V_пред=300 000 решение задачи лежит в точке А₃ с координатами:

х₁=292,68 ед. времени — время выпуска продукции по технологии Т1;

х₂=317,07 ед. времени — время выпуска продукции по технологии Т2;

К=314 634,1 — качество продукции.

По полученным данным построим график зависимости объёма производимой продукции от его качества — кривая альтернативных решений, оптимальных по Парето:

V.	220 000.	250 000.	300 000.	459 231.	470 769.	478 462.
K.	386 829,3.	359 756,1.	314 634,1.	150 000.	120 000.	100 000.

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

Таблица 2.1. Сравнительный анализ решения задачи многоцелевой оптимизации графическим методом и в Microsoft Excel.

Параметр	Графический метод.	«Поиск решения».
Критерий оптимальности — объём производства V.
Кпред.	100 000.
Х1, ед. времени.		667,69.
Х2, ед. времени.		36,92.
V.	474 000.	478 462.
Кпред.	120 000.
Х1, ед. времени.		646,15.
Х2, ед. времени.		61,54.
V.	469 000.	470 769.
Кпред.	150 000.
Х1, ед. времени.		613,85.
Х2, ед. времени.		98,46.
V.	457 000.	459 231.
Критерий оптимальности — качество продукции К.
Vпред.	220 000.
Х1, ед. времени.		136,59.
Х2, ед. времени.		414,63.
К.	392 000.	386 829,3.
Vпред.	250 000.
Х1, ед. времени.		195,12.
Х2, ед. времени.		378,05.
К.	361 000.	359 756,1.
Vпред.	300 000.
Х1, ед. времени.		292,68.
Х2, ед. времени.		317,07.
К.	317 000.	314 634,1.

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

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

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

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