Курсовик

Министерство образования Российской Федерации.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ

РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ

( ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ.)

Курсовая работа.

Тема: ”Двухкритериальные задачи ”

по дисциплине “Теории принятия решения ”.

Москва. 2003 г.

1.Задача.

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

1)выделение самого важного критерия, поиск оптимума по данному критерию и проверка оптимальности найденного решения с помощью метода уступки;

2)определение весовых коэффициентов критериев и нахождение с помощью них оптимума.

2.Исходные данные

Исходными данными в данной задаче являются:

1)Множество вариантов решений задачи, которые представлены в виде набора точек (х,у) на плоскости, расположенных в первом квадранте. Каждая координата данного решения представляет собой затраты по соответствующему критерию.

2)Определение самого важного критерия и уступка по нему (dx или dy).

3)Весовой коэффициент k в выражении kx+y, который показывает насколько критерий х важнее критерия у.

3.Метод решения и алгоритм, реализованный в программе.

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

Каждый критерий с разных сторон характеризует различные решения. Чаще всего заранее выделено направление улучшения каждого критерия, например его увеличение. Но одновременное увеличение всех критериев практически всегда невозможно из-за ограниченности какого-либо ресурса.

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

Рассмотрим двухкритериальные задачи (т. е. задач, в которых изначально или путем обоснованного упрощения осталось только два критерия).

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

Первый способ сведения двухкритериальной задачи к однокритериальной – это выделение самого важного критерия с последующим поиском оптимума по данному критерию. В нашем случае вы выбираем, какая координата самая важная – х или у. Далее мы ищем оптимум по этой координате (критерию). Оптимумом в нашей задаче является минимум затрат (точка с наименьшим значением соответствующей координаты). Когда такое решение найдено, идет проверка на его оптимальность. Для этого используется метод уступок. Состоит он в следующем. Относительно найденного оптимума делается уступка по соответствующему критерию (координате). Если в получившуюся область (х₀+dx) попадает одна или несколько точек из множества Парето, то выбирается точка с оптимальным вариантом по второму критерию (минимум). Однако выигрыш по второму критерию должен существенно превосходить уступку по первому, иначе выбор буде равнозначным исходному, а то и хуже.

Второй способ заключается во введении весовых коэффициентов по каждому критерию. В двухкритериальном случае достаточно ввести один из них, условно приняв, что второй равен единице. Мы получаем задачу поиска оптимума (минимума) для выражения kx+y, т.е. задачу с одним критерием.

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

Вначале работы программы вводится запрос к пользователю о варианте ввода координат точек – самостоятельно или случайно. После этого на экран выводятся все координаты исходных точек.

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

На последнем этапе требуется ввести коэффициент k, который показывает во сколько раз критерий х важнее критерия у (kх+у). После этого ведется поиск минимума суммы kx+y. На экран выводятся координаты найденной точки(решение). Помимо этого рисуется соответствующая линия уровня (kx+y=min).

4. Текст программы.

#include<bios.h>

#include<graphics.h>

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

#include<stdio.h>

int funci=0;

int col,mass=60;

#define e 0.00000001

void grafika(){

setcolor(6);

line(160,340,600,340);line(200,420,200,40);

outtextxy(590,348,"x"); outtextxy(208,45,"y");}

struct dannie{ double m[2],A[2],N[2];

float kust; int flag,fust;

} dis[100];

void vivod(int m)

{float a,b;

int rad=2; setcolor(col);

if(funci==0)

{a=200+mass*dis[m].A[0];

b=340-mass*dis[m].A[1];}

else {a=200+mass*dis[m].N[0];

b=340-mass*dis[m].N[1];}

setfillstyle(1,col); fillellipse(a,b,rad,rad);}

void main(){

int gdriver=DETECT,gmode;

initgraph(&gdriver,&gmode," ");

int lo,k,i,my,min; double minx,miny; float ust,kust;

cout<<"\n\nViberite vid vvoda(1_Manual. Other_Random.):";

cin>>i;

if(i==1)

{cout <<"\n\tVvedite dannie:\n";

for(lo=0;lo<80;lo++)

{if(!(cin>>dis[lo].A[0]>>dis[lo].A[1]))break;

cout<<"Tochka ь"<<lo+1<<": ";

cout<<"x"<<lo+1<<"="<<dis[lo].A[0]<<" y"<<lo+1<<"="<<dis[lo].A[1]<<"\n";}

} else {randomize();

cout <<"\n\t Sluchaino:\n";

for(lo=0;lo<80;lo++)

{dis[lo].A[0]=rand()%13; dis[lo].A[1]=rand()%13;}

}

for(i=0;i<lo;i++)

{if (dis[i].A[0]<e&&dis[i].A[1]<e)

{dis[i].A[0]=dis[i].A[0]*(-1);

dis[i].A[1]=dis[i].A[1]*(-1);}

else if(dis[i].A[1]<e)

{dis[i].A[1]=dis[i].A[1]*(-1);}

else if(dis[i].A[0]<e)

{dis[i].A[0]=dis[i].A[0]*(-1);}}

for(i=0;i<lo;i++)

for( k=i+1;k<lo;k++)

{if(dis[i].A[0]>dis[k].A[0])

{dis[i].m[0]=dis[i].A[0];dis[i].m[1]=dis[i].A[1];

dis[i].A[0]=dis[k].A[0];dis[i].A[1]=dis[k].A[1];

dis[k].A[0]=dis[i].m[0];dis[k].A[1]=dis[i].m[1];}

}

for(i=0;i<lo;i++)

for(k=i+1;k<lo;k++)

{if(dis[i].flag!=1)

if(dis[k].A[0]==dis[i].A[0])

{if(dis[k].A[1]>dis[i].A[1])

{dis[k].flag=1;}

else {dis[i].flag=1;}}

else

{if(dis[k].A[1]>=dis[i].A[1])

{dis[k].flag=1;}

}}

int uvel=0;

for(i=0;i<lo;i++)

{if(dis[i].flag==0)

{dis[uvel].N[0]=dis[i].A[0];dis[uvel].N[1]=dis[i].A[1];

cout<<"Pareto="<<dis[uvel].N[0]<<" "<<dis[uvel].N[1]<<"\n";

uvel++;}

}

cout<<"Naiti min(1-po X.2-po Y):";

scanf("%d",&min);

if(min==1)

{minx=dis[0].N[0];

cout<<uvel<<"\nTochka min po x="<<"["<<minx<<","<<dis[0].N[1]<<"]";}

else if(uvel==1)

{miny=dis[0].N[0];

cout<<"\nTochka min po y="<<"["<<miny<<","<<dis[0].N[1]<<"]";}

else{

miny=dis[uvel-1].N[1];

cout<<"\nTochka min po y="<<"["<<dis[uvel-1].N[0]<<","<<miny<<"]";

}

cout<<"\nVvedite interval ustupki:";

scanf("%f",&ust);

if(min==2)

{for(i=(uvel-1);i>=0;i--)

{if(dis[i].N[1]<=dis[uvel-1].N[1]+ust)

{my=i;}}

cout<<"\nMiny s ust ="<<ust<<"\ntochka: ["<<dis[my].N[0]<<","<<dis[my].N[1]<<"]";}

else {for(i=0;i<uvel;i++)

{if(dis[i].N[0]<=dis[0].N[0]+ust)

{my=i;}}

cout<<"\nMinx s ust ="<<ust<<"\ntochka: ["<<dis[my].N[0]<<","<<dis[my].N[1]<<"]";}

while(1){

grafika();

for(i=0;i<lo;i++)

{if(dis[i].flag==0)

{col=2; vivod(i);}

else {col=4;vivod(i);}}

switch(bioskey(0))

{case 0x4900:if(mass<200) mass+=3; cleardevice();break;

case 0x5100:if(mass>8) mass-=3;cleardevice();break;

case 0x11b :goto wq;}

}wq: my=0; cleardevice(); setcolor(5);

outtextxy(2,10," Vvedite koefficient vaznosti kx+y: "); gotoxy(1,3);

scanf("%f",&ust);

my=-1;kust=0; int rov;

for(i=0;i<uvel;i++)

{if(my==-1||kust>=ust*dis[i].N[0]+dis[i].N[1])

{my=i;rov=1;kust=(ust*dis[i].N[0]+dis[i].N[1]);}}

outtextxy(1,60,"To4ka s min kx+y:"); gotoxy(1,6);

cout<<"["<<dis[my].N[0]<<","<<dis[my].N[1]<<"]\n";

for(i=0;i<uvel;i++)

{cout<<"Pareto="<<dis[i].N[0]<<" "<<dis[i].N[1]<<"\n";}

double urov=(ust*dis[my].N[0]+dis[my].N[1]);

funci=1;

while(1){

grafika();

for(i=0;i<lo;i++)

{if(dis[i].flag==0)

{col=2;

for(k=0;k<uvel;k++)

vivod(k);}}

if(rov==1&&ust!=0)

{setcolor(3); line(200,340-urov*mass,200+(urov/ust)*mass,340);}

else{setcolor(3); line(200,340-urov*mass,600,340-(urov)*mass);}

switch(bioskey(0))

{case 0x4900:if(mass<200) mass+=3; cleardevice();break;

case 0x5100:if(mass>8) mass-=3;cleardevice();break;

case 0x11b :goto swq;}

}

swq:

}

5. Тестовая задача

Исходные данные:

Задали семь вариантов решения двухкритериальной задачи

1 – (0,6) 2 – (5,5)

3 – (4,3) 4 – (2,6)

5 – (7,1) 6 – (2,5)

7 – (6,4)

Получили множество Парето:

1 – (0,6) 3 – (4,3)

6 – (2,5) 5 – (7,1)

В первый раз важным критерием является критерий х. Оптимумом в этом случае является первое решение (0,6). Ввели уступку 3. Новое решение – (2,5).

y

x

Во второй раз важным выбрали критерий у. Точка оптимума в этом случае

– (7,1). Сделав уступку в 2 единицы, получим новый оптимум – (4,3).

Н а следующем этапе в качестве весового коэффициента выбрали число 2. Оптимумом по сумме kx+y будет первая точка (2*0+6=6). Нарисована соответствующая линия уровня.

y

x

Если вместо 2 взять 0.5 или 0.7, то получим соответственно оптимумы (7,1) -> 7*0.5+1=4.25 или (4,3) -> 4*0,7+3=5.8.

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