microbik.ru
1


Лабораторная работа № 2
Многокритериальные задачи линейного и нелинейного программирования
Цель работы
Исследование многокритериальных задач линейного и нелинейного программирования при различных компромиссных критериях [5].
Методические указания
Основная трудность принятия решений в условиях определен­ности связана с наличием нескольких критериев. В этом случае возникает необходимость в форми­ровании некоторого компромиссного векторного критерия.

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

Если все критерии измеряются в одной шкале, то компромиссный критерий можно записать в виде взвешенной суммы критериев:
, (2.1)
где – вес соответствующего критерия. В этом случае необходимо найти
. (2.2)
Если же критерии измеряются в различных шкалах, то необходимо привести их к единой шкале. Для этого критерий может быть сформирован в следующем виде:
, (2.3)
где и . В этом случае требуется минимизировать величину отклонения каждого критерия от его оптимального значения. При таком формировании обобщенного критерия можно добиться высоких показателей по одним критериям за счет ухудшения показателей по другим.

На некоторые частные критерии могут быть наложены ограничения
. (2.4)
Тогда исходная многокритериальная задача может быть преобразована к виду (2.1) или (2.3) с дополнением системы ограничением вида (2.4).

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

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

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


F(x)

x

F(x)

x


Рис. 2.1. Значения критериев F1 и F2

(Парето-оптимальное множество – одна точка)


Рис. 2.2. Значения критериев F1 и F2

(Парето-оптимальное множество – все возможные решения)
В случае, когда критерии зависят более, чем от одной переменной удобно изобразить множество значений критериев в координатах F1 и F2 (рис. 2.3). Если критерии F1 и F2 необходимо максимизировать, то Парето-оптимальным множеством является граница области допустимых значений, отмеченная на рис. 2.3 фигурной скобкой.



Рис. 2.3. Нахождение Парето-оптимального множества в координатах критериев F1 и F2
Порядок выполнения работы
1. Определить тип компромиссного критерия (2.1) или (2.3), который необходимо использовать для решения варианта задания.

2. Используя программное обеспечение решения задач линейного и нелинейного программирования, исследовать влияние весовых коэффициентов на оптимальное комп­ро­миссное решение.

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

Необходимо решить многокритериальную задачу.

Критерий 1. Максимизация прибыли.

Критерий 2. Максимизация количества комплектов. Комплект состоит из 18 костюмов первого вида, 15 костюмов второго вида и по 10 костюмов третьего и четвертого видов.
2. Три вида деталей можно производить на станках разных типов без переналадки.

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


Вид деталей

Производительность станков (деталей в час)

Себестоимость деталей

1 тип

2 тип

1

20

45

8

2

30

20

6

3

50

60

0,5


Фонд рабочего времени для станков составляет соответственно 12 и 8 часов.

Необходимо решить многокритериальную задачу.

Критерий 1. Максимизация количества комплектов. Комплект состоит из 16 деталей первого вида, 12 деталей второго вида и 24 детали третьего вида.

Критерий 2. Максимизация себестоимости.
3. Нефтеперерабатывающий завод получает 4 различных полуфа­бриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина пря­мой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А 2:3:5:2, бензин Б - 3:1:2:1 и бензин С - 2:2:1:3.

Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 12000 руб., 10000 руб., 15000 руб.

Необходимо решить многокритериальную задачу.

Критерий 1. Максимизация стоимости всей продукции.

Критерий 2. Минимизация остатков полуфабрикатов.
4. Полуфабрикаты поступают на предприятие в виде листов фанеры. Всего имеется две партии материала, причем первая партия содержит 400 листов, а вторая 250 листов фанеры. Из поступающих листов фанеры необходимо изготовить комплекты двух видов. Комплект первого вида включает 4 детали 1-го типа, 3 детали 2-го типа и 2 детали 3-го типа. Комплект второго вида включает 2 детали 1-го типа, 4 детали 2-го типа и 3 детали 3-го типа. Лист фанеры каждой партии может раскраиваться различными способами.

Количество деталей каждого типа, которое получается при рас­крое одного листа соответствующей партии по тому или иному спосо­бу раскроя, представлено в следующей таблице.

Стоимость одного листа первой партии составляет 1000 руб., а стоимость одного листа второй партии – 1200 руб. Цена комплекта первого вида составляет 150 руб., цена комплекта второго вида – 200 руб.


Детали

Способ раскроя

(1 п)


Детали

Способ раскроя

(2 п)




1

2

3




1

2

1

0

6

9

1

6

5

2

4

3

4

2

5

4

3

10

16

0

3

8

0


Необходимо решить многокритериальную задачу.

Критерий 1. Максимизация прибыли от продажи всех комплектов деталей.

Критерий 2. Максимизация количества комплектов первого вида.

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

Сырье. Для производства одной единицы первого продукта требуется одна единица сырья первого типа и семь единиц сырья второго типа. Для производства одной единицы второго продукта требуется три единицы сырья первого типа и пять единиц сырья второго типа.

Станки. Станок первого типа имеет ресурс мощности 3106, второго типа – 1106, третьего типа – 3105. При производстве первого продукта используется 0.5 единиц ресурса мощности станка первого типа, 0.2 единицы ресурса мощности станка второго типа и 0.025 единиц ресурса мощности станка третьего типа. При производстве второго продукта используется 2 единицы ресурса мощности станка первого типа, 0.5 единиц ресурса мощности станка второго типа и 0.1 единица ресурса мощности станка третьего типа.

Персонал. Бригада из одного квалифицированного рабочего и восьми неквалифированных рабочих может выпустить 1.5105 единиц первого продукта. Бригада из двух квалифицированных рабочих и 11-ти неквалифированных рабочих может выпустить 4104 единиц второго продукта.

Стоимость одной единицы сырья первого типа 1 руб., второго типа – 0.15 руб. Стоимость одного станка первого типа 8106 руб., станка второго типа – 7106 руб., станка третьего типа – 9106 руб. Амортизационные отчисления составляют 5 % от стоимости станка. Заработная плата квалифицированных рабочих 6.25103 руб., неквалифицированных – 4103 руб.

Цена первого продукта составляет 3.5 руб., второго – 12.5 руб.

Считается, что имеется неограниченное количество сырья. В наличии имеется 5 станков первого типа, 5 – второго типа, 3 ­– третьего типа. Максимальное число квалифицированных рабочих – 360, неквалифицированных – 2500. Платежеспособный спрос на первый продукт составляет 2.2107 руб., на второй продукт – 2.7107 руб.

Необходимо решить многокритериальную задачу.

Критерий 1. Максимизация стоимости продукции.

Критерий 2. Максимизация количества комплектов. Комплект состоит из 15 продуктов первого типа и 5 продуктов второго типа.
6. Четыре нефтеперерабатывающих завода с ежедневной производительностью 4, 6, 10 и 10 млн. тонн бензина снабжают пять бензохранилищ, ежедневная потребность которых составляет 7, 7, 7, 7 и 2 млн. тонн бензина соответственно. Стоимость транспортировки составляет 0.3 руб. за 1000 тонн на один км между заводами и хранилищами. Расстояние между заводами и хранилищами в км приведено в следующей таблице.


Заводы

Хранилища

Объем

1

2

3

4

5

1

160

300

170

100

160

4

2

300

270

260

90

230

6

3

130

40

220

30

100

10

4

30

100

50

40

240

10

Вместимость хранилища

7

7

7

7

2

30


Время (в часах), затрачиваемое на транспортировку бензина, приведено в следующей таблице.


Заводы

Хранилища

1

2

3

4

5

1

3

5

1

8

2

2

4

5

3

7

2

3

4

9

3

6

4

4

1

2

1

5

7


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

Критерий 1. Минимизация стоимости транспортировки бензина.

Критерий 2. Минимизация общего времени, затрачиваемого на транспортировку бензина из всех заводов во все хранилища.
7. 4 распределительных центра поставляют автомобили пяти дилерам. Автомобили от распределительных центров к дилерам перевозятся на трейлерах, и стоимость перевозки пропорциональна расстоянию между пунктами отправления и назначения и не зависят от степени загрузки трейлера. В таблице приведены расстояния между распределительными центрами и дилерами, а также соответствующие величины спроса и предложения, выраженные в количествах автомобилей. При полной загрузке трейлер вмещает 18 автомобилей. Транспортные расходы составляют 25 рублей за один км пути, пройденного трейлером.


Центры

Дилеры

Предложения

1

2

3

4

5

1

100

150

200

140

35

239

2

50

70

60

65

80

119

3

40

90

100

150

130

181

4

170

50

110

230

100

161

Спрос

111

131

259

98

101

700


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

Критерий 1. Максимизация общей загрузки трейлеров.

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


Пекарни

Транспортные издержки, руб./кг

Предложение

1-й магазин

2-й магазин

3-й магазин

4-й магазин

5-й магазин

A

0,9

1,7

2,9

2,8

0,8

200

B

1,3

2,1

2,7

1,6

2,9

300

C

2,0

3,0

2,4

0,7

2,6

200

D

1,1

1,9

3,0

0,6

0,2

200

Потребность магазинов

100

200

150

100

300

850 900


Время (в часах), затрачиваемое на транспортировку хлеба, приведено в следующей таблице.


Пекарни

Магазины

1

2

3

4

5

1

1,2

0,7

0,9

0,8

1,8

2

0,3

1,5

0,5

0,8

1,2

3

0,2

1,7

0,4

1,4

0,6

4

0,8

1,4

0,4

1,6

0,8


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

Критерий 1. Минимизация стоимости транспортировки.

Критерий 2. Минимизация общего времени, затрачиваемого на транспортировку хлеба из всех пекарней во все магазины.
9. 4 лесозаготовочных предприятия осуществляют поставки леса пяти деревообрабатывающим заводам. Лес перевозят на лесовозах, и стоимость перевозки пропорциональна расстоянию между пунктами отправления и назначения и не зависят от степени загрузки лесовоза. В таблице приведены расстояния между лесозаготовочными предприятиями и деревообрабатывающими заводами, а также соответствующие величины спроса и предложения, выраженные в куб. м. При полной загрузке лесовоз вмещает 16 куб. м. Транспортные расходы составляют 30 рублей за один км пути, пройденного лесовозом.


Лесозагот. предприятия

Деревообрабатывающие заводы

Предложения

1

2

3

4

5

1

160

300

170

100

160

700

2

300

270

260

90

230

650

3

130

40

220

30

100

700

4

30

100

50

40

240

520

Спрос

400

500

350

900

420

2570


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

Критерий 1. Максимизация общей загрузки лесовозов.

Критерий 2. Минимизация суммарной стоимости транспортировки леса.
10. 4 фермерских хозяйства осуществляют поставки зерна пяти мелькомбинатам. Зерно от фермерских хозяйств к мелькомбинатам перевозится на грузовых машинах вместимостью 2,5 тонны. Стоимость перевозки пропорциональна расстоянию между пунктами отправления и назначения и не зависит от степени загрузки машины. В таблице приведены расстояния в км между фермерскими хозяйствами и мелькомбинатами, а также соответствующие величины спроса и предложения, выраженные в тоннах. Транспортные расходы составляют 23 рубля за один км пути, пройденного одной грузовой машиной.


Фермерские

хозяйства


Мелькомбинаты

Предложения

1

2

3

4

5

1

80

170

290

280

80

22

2

130

210

170

160

290

13

3

200

250

240

70

240

17

4

110

190

300

60

20

18

Спрос

3

13

7

7

40

70


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

Критерий 1. Максимизация общей загрузки грузовиков.

Критерий 2. Минимизация суммарной стоимости транспортировки зерна.
11. Сотовая компания собирается строить новую базовую станцию в области, где имеется 10 населенных пунктов с координатами X и Y. Уровень сигнала от базовой станции уменьшается пропорционально квадрату расстояния до населенного пункта.


Населенный пункт

X

Y

Число жителей

1

10

15

52

2

3

6

104

3

5

25

30000

4

17

4

110

5

9

10

26

6

15

7

315

7

6

18

754

8

1

3

1267

9

12

8

1999

10

18

4

516


Расходы на установку базовой станции внутри населенных пунктов приведены в следующей таблице. Стоимость установки одной базовой станции вне населенных пунктов составляет 63 тыс. у.е.


Населенный пункт

Расходы на установку одной базовой станции, тыс. у.е.

1

10

2

7

3

14

4

17

5

9

6

15

7

6

8

10

9

12

10

18


Необходимо решить многокритериальную задачу.

Критерий 1. Минимизация взвешенной суммы квадратов расстояний до населенных пунктов с учетом числа жителей в каждом населенном пункте.

Критерий 2. Минимизация стоимости установки базовой станции.



№ варианта

1

2

3

4

5

6

7

8

9

10

11

Сложность задания (максимальное количество баллов)

12

10

10

12

12

11

11

11

11

11

12



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

2. Решение многокритериальных задач, когда критерии измеряются в одной шкале.

3. Решение многокритериальных задач, когда критерии измеряются в различных шкалах.

4. Определение Парето-оптимального множества решений.