Защищенная курсовая работа Парето (1063661), страница 2
Текст из файла (страница 2)
Очень частоподобной информации о структуре множества Парето уже бывает достаточно для решенияпрактических задач.Если множество Парето выпукло, то, увеличивая количество точек, которые определяютсяописанным способом, строим многогранник, аппроксимирующий это множество с любой степеньюточности. Однако практика дает примеры множеств Парето, которые не являются выпуклыми. Тогдазадача их аппроксимации резко усложняется. [6]Аксиомы, являющиеся основой принципа Парето1.
Аксиома исключения доминирующих решений: Для всякой пары допустимых решений , длякоторых имеет место соотношение, выполнено.2. Аксиома Парето: Для всех пар допустимых решений, для которых имеет место неравенство ,выполняется соотношение.3. Принцип Парето: наилучшее решение многокритериальной задачи всегда выбирается из Паретооптимального множества.5Алгоритм решения задачи1. Определить область допустимых действительных значений для функций (2) с ограничениями (1),получив диапазон констант:c помощь метода штрафных функций или перебора.2.
Разбить задачу на две задачи оптимизации путём сведения всех функций ограничениям.гдеточность,номер итерации и решить для различных3. Преобразуем задачу к решению с помощью метода штрафных функций:.,гдепараметр штрафа, значения которого убывают с каждой итерации, но т.к в нашемслучае надо решить несколько тысяч таких задач, то автоматизировать начальную точкуудовлетворяющую всем ограничением не удаётся, что приводит к фиктивному успеху нанекоторых итерациях. Поэтому решено было сравнивать решения с обычным перебором, чтопозволило получить достоверный результат, а главное более точный, благо мощные современныекомпьютеры не испытывают в этом сложности.[7]4. Найденные решения объединить в пары вида и построить их на одной плоскости:5.
Определить наилучшее решение с помощью сравнения его с идеальным решением к которомустремятся функции в одиночку, но не достигнут его в системе. Наилучшее решение будет наминимальном расстоянии от идеального.Результат вычислительного экспериментаКод программы приведён в приложении в конце курсовой работы. [8]Аналитическое решение задачиДля 5-и разбиений:6По результатам вычислений определилось две точки для каждой из задач оптимизации,которые отличаются друг от друга. Выбираем наилучшую точку для решения, которая записана впоследней строке.Для 5-и тысяч разбиений:По результатам видно, что две точки, выбранные в качестве наилучшего решения для каждойиз задач оптимизации, совпали, что подтверждает точность вычислений и служит единственнымправильным решением.Графическое представление множества ПаретоДля 5-и разбиений:Для 5-и тысяч разбиений:7В результате построилось множество Парето.
Видно две несовпадающие ломанные линии прималом количестве разбиений. В связи с этим построено более точное множество для 5-и тысячразбиений. При большем количестве разбиений видимых изменений не происходит , что не позволитих увидеть в курсовой работе.В итоге графики сходятся в одну кривую, что позволяет считать их одним целым длямножества Парето. В нашем случае, для минимизирования двух функций, мы теперь сможемпринять решения на кривой Парето.Сравнение результатов с точным решениемРешение получено с помощью подстановки всех значений до пятого знака после запятой.По результатам вычислений через Парето наилучшее решение равно с точностью до двухзнаков после запятой:Видно, что если округлить результаты до третьего знака, то решения совпадают, чтоподтверждает правильность проделанной работы.Выводы по работе1.
Большинство инженерных задач являются многокритериальными. Одним из возможныхспособов оптимизации этих задач является применение принципа Парето. Однако присложных зависимостях частных критерий применение принципа Парето затруднительно. Вэтом случае возможно применение численного метода.2.
При увеличении количества значений (разбиений) двух функции, а точнее, перебор большегоколичества констант , приведёт к сужению множества Парето и более плавным результатам.3. Рассмотрен пример оптимизации двух функций при решении программным способом и наэтой основе вычислено множество точек Парето. Определено наилучшее решения для задачичерез определение наименьшего расстояния до идеальной точки.8ПриложениеПрограмма написана на языке программирования С++ для вычисления значений точек,принадлежащих множеству Парето, и построения графика зависимости двух оптимизированныхфункций с помощью библиотеки OpenGL.[9]#include <stdio.h>#include <math.h>#include <GL/glut.h>using namespace std;//OpenGl, для рисования единичного отрезкаvoid draw_string_bitmap(void *font, const char* string)//Первая функцияdouble f1(double x, double y) {return (4*x*x)+(y*y);}//Вторая функцияdouble f2(double x, double y){return ((x+1)*(x+1))+((y-1)*(y-1));}//Вычисление и рисованиеvoid display(void) {//итерации,переменные,ограничения,точностьdouble x,y,C1,C2,min=1000,xmin,ymin,e=0.01;int n=0;//точное решение без Паретоfor (x=-1; x<1+e; x+=e)for (y=-1; y<1+e; y+=e)if ((f1(x,y)*f1(x,y)+f2(x,y)*f2(x,y))<min) {min=f1(x,y)*f1(x,y)+f2(x,y)*f2(x,y);xmin=x;ymin=y;printf(" %3.d (x1;x2)=(%5.5f %5.5f) (f1,f2)=(%5.5f %5.5f) \n", 1 + n++, xmin, ymin,f1(xmin, ymin), f2(xmin, ymin));}printf(" Exact Answer: (x1;x2)=(%5.5f %5.5f) (f1,f2)=(%5.5f %5.5f) \n",xmin,ymin,f1(xmin,ymin),f2(xmin,ymin));n = 0;//количество разбиенийconst int k=5;float x1[k],y1[k],c1[k],min1[k],x2[k],y2[k],c2[k],min2[k];//минимизация второй функции при закреплённой первойprintf("\n Solution: f1=const, f2=optimized\n");for (C1=0; C1<=5.0; C1+=5.0/(k-1)) {min=10;xmin=10;ymin=10;for (x=-1; x<1+e; x=x+e)for (y=-1; y<1+e; y=y+e)if ((f1(x,y)>=(C1-0.02)) && (f1(x,y)<=(C1+0.00001)) && (f2(x,y)<min)) {min=f2(x,y);xmin=x;ymin=y;}printf("\n %3.d (x1;x2)=(%5.2f %5.2f) (f1,f2)=(%5.2f%5.2f)",1+n++,x1[n]=xmin,y1[n]=ymin,c1[n]=C1,min1[n]=min);}//новая строкаprintf("\n\n Solution: f1=optimized, f2=const\n"); n=0;//минимизация первой функции при закреплённой второйfor (C2=0; C2<=2.0; C2+=2.0/(k-1)) {min=10;xmin=10;ymin=10;for (x=-1; x<1+e; x=x+e)for (y=-1; y<1+e; y=y+e)if ((f2(x,y)>=(C2-0.038)) && (f2(x,y)<=(C2+0.00001)) && (f1(x,y)<min)) {min=f1(x,y);xmin=x;ymin=y;}printf("\n %3.d (x1;x2)=(%5.2f %5.2f) (f1,f2)=(%5.2f%5.2f)",1+n++,x2[n]=xmin,y2[n]=ymin,min2[n]=min,c2[n]=C2);}//единичный отрезок по F2glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "0.0"); xx+=0.5;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "0.5"); xx+=0.5;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "1.0"); xx+=0.5;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "1.5"); xx+=0.5;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "2.0"); xx+=0.1;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "(F2)");//единичный отрезок по F1xx=-0.125, yy=-0.0275+1;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "1.0"); yy+=1;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "2.0"); yy+=1;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "3.0"); yy+=1;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "4.0"); yy+=1;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "5.0"); yy+=0.125;glRasterPos2f(xx, yy); draw_string_bitmap(GLUT_BITMAP_8_BY_13, "(F1)");glLineWidth(1);//рисование сеткиglBegin(GL_LINES);9for (float i =0; i <= 2.1; i += 0.1){glVertex2f(i, 0); glVertex2f(i, 5);}for (float i = 0; i <=5; i += 0.2){glVertex2f(0, i); glVertex2f(2, i);}glEnd();//построение кривыхglLineWidth(2);glBegin(GL_LINES);//F1-const/blueglColor3f(0, 0, 1);for (int i = 0; i < k-1; i++){glVertex2f(min1[i],c1[i]);glVertex2f(min1[i+1],c1[i+1]);}//F2-const/redglColor3f(1, 0, 0);for (int i = 0; i < k-1; i++){glVertex2f(c2[i],min2[i]);glVertex2f(c2[i+1],min2[i+1]);}double f10=0,f20=0,d1,d2;//идеальное решениеint i,imin=0,imin1=0,imin2=0;//поиск минимального расстояния при F1-const/bluemin=10;for (int i = 0; i < k-1; i++){d1=sqrt((c1[i]-f20)*(c1[i]-f20)+(min1[i]-f10)*(min1[i]-f10));if (d1<min) {min=d1, imin1=i;}}glColor3f(0, 1, 1);glVertex2f(f20, f10);glVertex2f(min1[imin1], c1[imin1]);//поиск минимального расстояния при F2-const/redmin=10;for (int i = 0; i < k-1; i++){d2=sqrt((c2[i]-f20)*(c2[i]-f20)+(min2[i]-f10)*(min2[i]-f10));if (d2<min) {min=d2, imin2=i;}}//построение идеальной точкиglVertex2f(f20, f10);glVertex2f(c2[imin2], min2[imin2]);glEnd();//подпись координат идеальной точкиprintf("\n\n Answer (f1=const): (x1;x2)=(%5.2f %5.2f) (f1,f2)=(%5.2f%5.2f)",x1[imin1],y1[imin1],c1[imin1],min1[imin1]);printf("\n\n Answer (f2=const): (x1;x2)=(%5.2f %5.2f) (f1,f2)=(%5.2f%5.2f)",x2[imin2],y2[imin2],min2[imin2],c2[imin2]);//сравнение минимальныхi=imin1; d1=sqrt((c1[i]-f20)*(c1[i]-f20)+(min1[i]-f10)*(min1[i]-f10));i=imin2; d2=sqrt((c2[i]-f20)*(c2[i]-f20)+(min2[i]-f10)*(min2[i]-f10));if (d1<=d2) printf("\n\n Best Answer: (x1;x2)=(%5.2f %5.2f) (f1,f2)=(%5.2f%5.2f)",x1[imin1],y1[imin1],c1[imin1],min1[imin1]);else printf("\n\n Best Answer: (x1;x2)=(%5.2f %5.2f) (f1,f2)=(%5.2f%5.2f)",x2[imin2],y2[imin2],min2[imin2],c2[imin2]);}//OpenGLvoid init(void)void reshape(int w, int h)void main(int argc, char** argv)Список используемой литературы1Корниенко В.
П., Методы оптимизации. 2007.Моисеев Н. Н., Методы оптимизации. 1978.3Штойер Р., Многокритериальная оптимизация. 1992.4Трифонов А.Г., Многокритериальная оптимизация. 2014.5Уайлд Д. Дж., Методы поиска экстремума. 1967.6Моисеев Н.Н., Математические задачи системного анализа. 1981.7Банди Б., Методы Оптимизации. Вводный курс. 1988.8Брюс Эккель, Философия C++., Введение в стандартный C++. 2004.9Бейкер М. П., Компьютерная графика и стандарт OpenGL.
2005.210.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
