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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

• Решение задачи многоцелевой оптимизации без применения ЭВМ
• Типовая таблица исходных данных
• Решение задачи графическим методом
• Построение кривой компромиссных решений
• Решение задачи многоцелевой оптимизации с использованием среды Microsoft Excel
• Вывод


I. Решение задачи многоцелевой оптимизации без применения ЭВМ

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

Таблица 1.1. Исходные данные

Характеристика производства	Располагаемый ресурс	Нормы расхода ресурсов
		Т1	Т2
Сырьё	4000	5	8
Электроэнергия	560	0,8	0,7
Объем реализации продукции	700	300
Показатели качества продукции	100	900
Кпред=100 000; 120 000; 150 000
Vпред=220 000; 250 000; 300 000

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

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

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

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

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

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

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

Решение задачи графическим методом

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

К_пред=100000; 120000; 150000.

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)=105000;

V=700x₁+300x₂=105000;

х₁=0 => х₂=350;

х₂=0 => х₁=150.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

V_пред=220000; 250000; 300000.

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)=45000;

К=100x₁+900x₂=45000;

х₁=0 => х₂=50;

х₂=0 => х₁=450.

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

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

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

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

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

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_пред=220000 решение задачи лежит в точке А₁ с координатами:

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

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

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

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

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

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

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

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

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

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

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

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

Построение кривой компромиссных решений

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

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 и найдем решение с помощью надстройки «Поиск решения». Результат представлен ниже:

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К=386829,3 - качество продукции.

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

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

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

К=359756,1 - качество продукции.

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

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

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

К=314634,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, ед. времени	660	667,69
Х2, ед. времени	40	36,92
V	474 000	478 462
Кпред	120 000
Х1, ед. времени	640	646,15
Х2, ед. времени	70	61,54
V	469 000	470 769
Кпред	150 000
Х1, ед. времени	610	613,85
Х2, ед. времени	100	98,46
V	457 000	459 231
Критерий оптимальности - качество продукции К
Vпред	220 000
Х1, ед. времени	140	136,59
Х2, ед. времени	420	414,63
К	392 000	386 829,3
Vпред	250 000
Х1, ед. времени	190	195,12
Х2, ед. времени	380	378,05
К	361 000	359 756,1
Vпред	300 000
Х1, ед. времени	290	292,68
Х2, ед. времени	320	317,07
К	317 000	314 634,1



Вывод

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

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

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

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

Размещено на Allbest.ru

...