Практика 6. МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ

Содержание
Теоретические положения.
Упражнение 1. Найти частную ЦФ (ЧЦФ) для первого города, если известно, что он хочет построить завод на трассе р11-р12 как можно ближе.
Контрольные вопросы.
Упражнение 2. Два города решили построить завод на трассе р11-р12. Найти ЧЦФ и глобальные (ГЦФ)  для различных случаев.
Контрольные вопросы.
Упражнение 3. Три города р1, р2, р3 решили также на трассе р11-р12 построить завод р по переработке отходов. Определить ЧЦФ и  общее  минимальное расстояние (поиск ГЦФ). Укажите зону решений в случае компромисса (все заводы решили построить завод на одинаковом расстоянии).
Контрольные вопросы.
Упражнение 4. Три города р1, р2, р3 решили в плоскости треугольника, образованного их расположением,  построить завод р по переработке отходов. Определить местоположение завода таким, чтобы сумма расстояний от городов до него была минимальной. Указать зоны Парето при противоречивых условиях.
Контрольные вопросы.


Теоретические положения.
Задача называется многокритериальной, когда общий критерий (на маx/мin) отыскивается по сумме частных критериев, которые могут быть противоречивы (например, один критерий на максимум, другой - на минимум).
Формализация задачи:
F(Х) = {f1(X) -min;
            f2(X) -max; }-min,
где X - вектор переменных параметров, f1, f2 - частные целевая функция (ЦФ), а F - глобальная ЦФ поставленной задачи.

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



Упражнение 1.
Два города р1 и р2 (рис.1) решили построить завод (р) по переработке отходов. Возможны разные варианты: первый и второй города стремятся построить завод р как можно ближе, чтобы общее расстояние (s3=s1+s2) до завода было минимальным, второй город имеет приоритет, на одинаковом расстоянии (s1=s2), или первый город стремиться построить завод как можно дальше, второй город - как можно ближе и т.д. Решим сначала для первого случая - определим частную цель для первого города, или тоже самое: найти наикратчайшее расстояние от точки р1  до прямой р11-р12.

grd.mac
: p1=40.,0. p2=210.,0. p11=10.,25. p12=275.,130.   $ города, дорога
otrezok : p101=p11 p102=p12     $ изображение дороги
okr: p100=p1 s100=4.0          $ положение первого города
okr: p100=p2        $  положение второго города
:s91=1000.  $ начальное значения эталона заведомо большее число
s1=$sqrt((x1-x11)*(x1-x11)+(y1-y11)*(y1-y11)) $ длина от р1 до р11
p91=x11, s1+10.  $ нач. точка графика 1-й ЧЦФ
grc: s=0.0                             $ обращение к циклу

grc.mac   $ исполнительная МК - перебора, выбора min и т.д.
s > 1.0001 ? exit    $ условие выхода
p=(1.-s)*p11 +s*p12     $ перебор положений завода
otrezok : p101=p1 p102=p   $ перебор отрезков от 1-го города до трассы
s1=$sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y))   $  - расстояния |p1-p|
otrezok: p101=p91 p102=x, s1+10.  $ график  расстояния от p1 до р
p91=p102    $ переводим конец отрезка в начало
s1 < s91 ? s91=s1         $ сравниваем и выбираем мin (в s91)
n51=s91*10000.                        $ перевод s91 в целое
$ n51 <> (подставить значение n51) ? exit  $ выход при s91 равном min
grc: s=s+0.01                         $ рекурсия - вызов МК самой себя
 

Примечание. После запуска МК (grd) получим рисунок 6.1 и мin расстояние s3 в s91. Чтобы определить точку р - положение завода требуется: запомнить s91,   в МК grc.mac поставить условие: при достижении минимума (s91) выйти, для чего число (s91) перевести сначала в целое, с учетом знаков после точки (строчка: n51=s91*10000.), а потом поставить само условие: n51 <> 343165 ? exit. Убрав знак комментария $, вновь запустить grd. мас Получим рисунок 6.2, а в оперативной памяти искомую точку р.
 

Рис. 6.1

Рис. 6.2
Графическая интерпретация задачи упр.1. 
 Контрольные вопросы.
В каком регистре лежит минимум расстояния от города до завода?
Что означает командная строка: s1 < s91 ? s91=s1 ?
Что означает командная строка: n50 <> 214036 ? exit ?
Как определить положение завода при минимуме s1?

Упражнение 2. Смоделировать и решить слеующие задачи (данные в упр.1):
1) 1-й город стремится построить завод р как можно ближе (s1-> min).
2) 2-й город стремится построить завод ближе (s2-> min) (в s92)
3) Решили, чтоб (s3=s1+s2) было минимальным (s3-> min) (в s93)
4) Второй город имеет приоритет 2 (s4=s1+2.*s2) (s4-> min) (мin в s94)
5) Города хотят построить завод на одинаковом расстоянии (s1=s2)
6) 1-й город стремиться построить завод как можно дальше (s1-> max), 2-й город - ближе (s2-> min).

grd.mac
: p1=30.,0. p2=210.,0. p11=0.,25. p12=275.,130.    $ города, дорога
otrezok : p101=p11 p102=p12     $ изображение дороги
: s91=1000. s92=1000. s93=2000. s94=5000. s95=1000.
s1=$sqrt((x1-x11)*(x1-x11)+(y1-y11)*(y1-y11))  $   расстояние р1-р11
s2=$sqrt((x2-x11)*(x2-x11)+(y2-y11)*(y2-y11))  $   расстояние р2-р11
p91=x11,s1+10.  $ начальная точка графика 1-й ЧЦФ
p92=x11,s2+10.     $ - 2-ЧЦФ +10. (масштабирование)
p93=x11,(s1+s2)-100.   $- для суммарной ЦФ
p94=x11,(s1+2.0*s2)-250.         $ начальная точка для 3-го графика
p95=x11,$sqrt((s1-s2)*(s1-s2))   $ нач. т. для графика компромисса
grc: s=0.0                             $ обращение к циклу

grc.mac
s > 1.0001 ? exit    $ условие выхода
p=(1.-s)*p11 +s*p12     $ перебор положений завода
$ решаем задачe с 1-й ЧЦФ
otrezok : p101=p1 p102=p   $ перебор отрезков от 1-го города до трассы
s1=$sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y))   $  - расстояния |p1-p|
otrezok: p101=p91 p102=x,s1+10.   $ график  расстояния от p1 до р
p91=p102    $ переводим конец отрезка в начало
s1 < s91 ? s91=s1         $ сравниваем и выбираем мin (в s91)
n51=s91*10000.                        $ перевод в целое
$ n51 <> (подставить n51 мin)  ? exit  $ выход при s1 минимальное
 

 

 
Графическая интерпретация первого условия.

$ решаем задачи с 2-й ЧЦФ (зависимости s2 от 2-го города до завода)
otrezok: p101=p2 p102=p   $ перебор отрезками от 2-го города до завода
s2=$sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y)) $  - расстояния  |p2-p|
otrezok: p101=p92 p102=x,s2+10. $ график расстояния s2 от p2 до р
p92=p102    $  конец в начало
s2 <s92 ? s92=s2   $ сравниваем и выбираем мин (s92
n52=s92*10000.                        $ перевод в целое
$ n52 <> (подставить n52 мin)  ? exit  $ выход при s2 минимальное
ская интерпретация первого условия.
 


 
ЦФ второго условия.

$ решаем задачу суммы s1+s2 ЦФ стремящейся к минимуму
s3=s1+s2   $  вычесление суммы расстояний
otrezok: p101=p93 p102=x,s3-100. $  график  s3(p)
p93=p102          $  конец в начало
s3 < s93 ? s93=s3                   $ выбираем мin суммы в s93
n53=s93*10000.                       $ перевод в целое
$ n53 <> (подставить n53 мin)  ? exit  $ выход при s3 минимальное
 

 
ЦФ третьего условия.

$ решаем задачу с приоритетом 2-го города
s4=s1+2.*s2
otrezok: p101=p94 p102=x,s4-250.   $ строим график ЦФ
p94=p102
s4 < s94 ? s94=s4                    $ сравниваем - минимум в s94
n54=s94*10000.                        $ перевод в целое
$ n54 <> (подставить n54 мin)  ? exit  $ выход при s4 минимальное
 

 
ЦФ четвертого условия.

$ решаем задачу на компромисс s1=s2 или s1-s2 -> min (s5)
$ чтобы (s1-s2) была положительной берем в квадрате и корень:
s5=$sqrt((s1-s2)*(s1-s2))           $ смотри строчку выше
s5 < s95 ? s95=s5                        $ минимум в s95
otrezok: p101=p95  p102=x,s5    $ строим график ЦФ
p95=p102                              $ конец в начало
n55=s95*10000.                       $ перевод в целое
$ n55 <> (подставить n55 мin)  ? exit  $ выход при s5 минимальное
 

 
ЦФ пятого условия.

$ 1-й город стремиться построить завод как можно дальше (s1-> max),
$ 2-й город - ближе (s2-> min)
s1=$sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y))   $  - расстояния |p1-p|
s2=$sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y)) $  - расстояния  |p2-p|
s6=2.5*s2-s1
s6 < s96 ? s96=s6
otrezok: p101=p96 p102=x,s6  $ график ЦФ
p96=p102
n56=s96*10000.                       $ перевод в целое
$ n56 <> (подставить n56 мin)  ? exit  $ выход при s5 минимальное
grc: s=s+0.05                         $ рекурсия - вызов МК самой себя
 

 
ЦФ шестого условия. На втором рисунке решение иайдено в зоне Парето р2*-р1*.
 
 

 
ЦФ всех шести условий. Справа показано построение ЦФ для 3-го условия в зоне Парето 



 Контрольные вопросы
1. Покажите область Парето для того или иного случая. Между какими точками (или в точке) она лежит?
2. Что нужно сделать, чтобы вычисления проходили в зоне Парето?
3. Что означает командная строка s5=$sqrt((s1-s2)*(s1-s2))?
4. Что вычисяют переменные: s1, s2, s3, s4, s5, s6?
5. В каких регистрах лежат s1, s2, s3, s4, s5, s6 минимальные?

Упражнение 3. Три города р1, р2, р3 решили также на трассе р11-р12 построить завод р по переработке отходов. Определить ЧЦФ и  общее  минимальное расстояние (поиск ГЦФ). Укажите зону решений в случае компромисса (все заводы решили построить завод на одинаковом расстоянии).

 Данные в МК grd3g.mac. Определим частные ЦФ и  общее  минимальное расстояние (поиск глобальной ЦФ) с помощью МК:  grс3g.mac.

grd3g.mac
$ print$on
: p1=30.,0. p2=210.,0.  p3=100.,-40.
: p11=0.,25. p12=275.,130.    $ дорога
otrezok : p101=p11 p102=p12     $ изображение дороги
okr: p100=p11 s100=2.
okr: p100=p12
okr: p100=p1 s100=3.
okr: p100=p2 s100=3.
: s91=1000. s92=1000. s93=2000. s94=5000.
s1=$sqrt((x1-x11)*(x1-x11)+(y1-y11)*(y1-y11))  $   расстояние р1-р11
s2=$sqrt((x2-x11)*(x2-x11)+(y2-y11)*(y2-y11))  $   расстояние р2-р11
s3=$sqrt((x3-x11)*(x3-x11)+(y3-y11)*(y3-y11))  $   расстояние р2-р11
p91=x11,s1+10.  $ начальная точка графика 1-й ЧЦФ
p92=x11,s2+10.     $ - 2-ЧЦФ +10. (масштабирование)
p93=x11,s3+10.         $ - для 3-й ЧЦФ
p94=x11,(s1+2.*s2+s3)-250.          $ начальная точка для 4-го графика
grc3g: s=0.0                             $ обращение к циклу

grc3g.mac
s > 1.0001 ? exit    $ условие выхода
p=(1.-s)*p11 +s*p12      $ перебор положений завода

$ решаем задачу с 1-й ЧЦФ
otrezok : p101=p1 p102=p   $ перебор отрезков от 1-го города до трассы
s1=$sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y))   $  - расстояния |p1-p|
otrezok: p101=p91 p102=x,s1+10.   $ график  расстояния от p1 до р
p91=p102    $ переводим конец отрезка в начало
s1 < s91 ? s91=s1         $ сравниваем и выбираем мin (в s91)
n51=s91*10000.                        $ перевод в целое
$ n51 <> 343383   ? exit   $ выход при s1 минимальное

$ решаем задачи с 2-й ЧЦФ (зависимости s2 от 2-го города до завода)
otrezok: p101=p2 p102=p   $ перебор отрезками от 2-го города до завода
s2=$sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y)) $  - расстояния  |p2-p|
otrezok: p101=p92 p102=x,s2+10. $ график расстояния s2 от p2 до р
p92=p102    $  конец в начало
s2 <s92 ? s92=s2   $ сравниваем и выбираем мин (s92
n52=s92*10000.                        $ перевод в целое
$ n52 <> 983469  ? exit   $ выход при s2 минимальное

$ решаем задачи с 3-й ЧЦФ (зависимости s3 3-го города до завода)
otrezok: p101=p3 p102=p   $ перебор отрезками от 2-го города до завода
s3=$sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y)) $  - расстояния  |p2-p|
otrezok: p101=p93 p102=x,s3+10.  $ график расстояния s3 от p3 до р
p93=p102    $  конец в начало
s3 < s93 ? s93=s3   $ сравниваем и выбираем мин (s93
n53=s93*10000.                        $ перевод в целое
$ n53 <> 964527  ? exit   $ выход при s3 минимальное

$ решаем задачу суммы s1+2.*s2+s3 ЦФ стремящейся к минимуму (2-й город имеет еще и преоритет
s11=s1+2.*s2+s3   $  вычесление суммы расстояний
otrezok: p101=p94 p102=x,s11-300. $  график  s11(p)
p94=p102          $  конец в начало
s11 < s94 ? s94=s11                   $ выбираем мin суммы в s94
n54=s94*10000.                       $ перевод в целое
$ n54 <> 4512447  ? exit   $ выход при s11 минимальное
grc3g: s=s+0.05
МК
 



Контрольные вопросы
1. Где находится область Парето при поиске ГЦФ?
2. Укажите зону (или точку) копромиссных решений.
3. В какой регистре определяется минимум ГЦФ?
4. Всегда ли может быть найдено единственое решение при компромиссе (все расстояния от городов до завода равны) в данной задаче?
5. В какой переменной идет расчет ГЦФ?



 
 
Упражнение  4. Три города р1, р2, р3 решили в плоскости треугольника, образованного их расположением  построить завод р по переработке отходов. Определить местоположение завода таким, чтобы сумма расстояний от городов до него быа минимальной. Определите зоны Парето при противоречивых условиях. 
 
 

Решение. Данные в МК t3gor0.maс. Возможны разные ситуации. Определим частные ЦФ и  общее  минимальное расстояние (поиск глобальной ЦФ) в одном файле:
t3gor0.maс
: p1=150.,160. p2=20.,20. p3=285.,20.
otrezok: p101=p1 p102=p2
otrezok: p101=p2 p102=p3
otrezok: p101=p3 p102=p1
t3gor1: s=0. s11=0. s99=1000. p99=p1
$ соединяем вершины треугольника с найденной точкой
otrezok: p101=p1 p102=p
otrezok: p101=p2 p102=p
otrezok: p101=p3 p102=p

t3gor1.mac
s11  > 1.001 ? exit
p13=(1.-s11)*p1 + s11*p3
p12=(1.-s11)*p1 + s11*p2
t3gor2: s=0.
$ n50 < 369721 ? exit
t3gor1: s11=s11+0.1

t3gor2.mac
s > 1.001 ? exit
p=(1.-s)*p13+s*p12
okr: p100=p s100=3.0
s1=$sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y))
s2=$sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y))
s3=$sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y))
s4=s1+s2+s3
s4 < s99 ? s99=s4
n50=s99*1000.
$ n50 < 369721 ? exit
otrezok: p101=p99 p102=x,s4/2. $  график ЦФ
p99=p102
t3gor2: s=s+0.1
 

 
График ЦФ и искомая точка р. 



Контрольные вопросы
1. Где находится область Парето при поиске ГЦФ?
2. В какой системе координат изображена ГЦФ?
3. В какой регистре определяется минимум ГЦФ?
4. Сколько циклов имеет задача?
5. В какой переменной идет расчет ГЦФ?