Реферати українською » Экономико-математическое моделирование » Багатокритеріальні задачі. Паретовскіе рішення


Реферат Багатокритеріальні задачі. Паретовскіе рішення

>Оглавление

>Оглавление. 1

1. Постановка завдання. 2

2. Стислі теоретичні відомості. 3

3. Реалізація програмного кошти. 7

3.1 Проектування. 7

3.2 Алгоритм пошукупарето-оптимальних рішень. 7

3.3Листинг програмного коду. 10

4. Приклад роботи програми.. 24

4.1Многокритериальная завдання. 24

4.2Двухкритериальная завдання. 25

3.Аналитическое завдання критеріїв. 27

Висновки.. 28

Використовувана література. 29

Використовувані програмні кошти. 29

1. Постановка завдання

математична модельпарето оптимальність

Необхідно розробити програмне засіб на допомогу пошукупарето-оптимальних рішень до таких видів завдань:

1) багатокритерійну завдання

вхідні дані: кількість критеріїв і рішень; вагові значення, задані безпосередньо, або упараметрическом вигляді.

вихідних даних: рішення, що входять до безліч Парето; номерипарето-оптимальних рішень з багатьох вихідних рішень

2)двухкритериальная завдання

вхідні дані: кількість критеріїв і рішень; вагові значення, задані безпосередньо, або упараметрическом вигляді.

вихідних даних: рішення, що входять до безліч Парето; номерипарето-оптимальних рішень з багатьох вихідних рішень; графічне уявленняпарето-оптимальних рішень.


2. Стислі теоретичні відомості

Нехай заданий набір числових функцій , певних на безліч імовірних рішень X. Залежно від змісту завдання вибору цих функцій називають критеріями оптимальності, критеріями ефективності чи цільовими функціями.

Зазначені вище числові функції утворюють векторний критерій , котра приймає значення просторіm-мерних векторів . Це простір називаютькритериальним простором чи простором оцінок, а всяке значення називають векторної оцінкою можливого рішення x. Усі можливі векторні оцінки утворюють безліч можливих оцінок (можливих чи допустимих векторів)

Зазвичай, між множинами можливих рішень X і відповідатиме безліччю векторів Y можна встановити взаємно однозначне відповідність, тобто. кожному можливого рішенню експортувати відповідність певний можливий вектор, і навпаки – кожному можливого вектору зіставити певне можливе рішення. У разі вибір в багатьох рішень з математичної погляду рівнозначний вибору в багатьох векторів і всі ухвали і результати можна формулювати як і термінах рішень, і у термінах векторів, причому за бажання можна легко перейти від однієї форми викладу в іншу.

Завдання вибору, що включає безліч допустимих рішень X і векторний критерійf, зазвичай називаютьмногокритериальной завданням чи завданняммногокритериальной оптимізації.

Слід зазначити, формування математичну модель прийняття рішень (тобто. побудова безлічі X і векторного критерію >f ) нерідко є складного процесу, у якому тісно взаємодіють фахівці обох сторін. Як-от, представники конкретної області знань, до якої належить досліджувана проблема, і з прийняттю рішень (математики). З одного боку, треба врахувати все найважливіші риси і деталі реальної завдання, з другого, – побудована модель має виявитися надмірно складної про те, щоб на її дослідження та рішення можна було успішно застосувати розроблений на сьогодні відповідний математичний апарат. Саме тому етап побудови математичну модель значною мірою залежить від досвіду, інтуїції і надзвичайно мистецтва дослідників обох сторін. Його неможливо ототожнити з простим формальним застосуванням вже, добре описаних алгоритмів.

Тут треба ще додати, будь-яка завдання вибору (зокрема і багатокритерійну) міцно пов'язана з конкретною >ЛПР(обличчя, яка набирає рішення). Уже формування математичну модель при побудові безлічі можливих прийняття рішень та векторного критерію справа не обходиться без рад, рекомендацій та вказівокЛПР, тим більше векторний критерій таки служить. Прийняття рішення за багатьох критеріях висловлення цілейЛПР. У цьому ясно, що модель з точністю відповідну всім реальним обставинам неможливо. Модель завжди є спрощенням дійсності. Важливо домогтися, щоб він містила ті риси і деталі, які у найбільшою мірою впливають на остаточний вибір найкращого рішення.

Розглянемо два довільних можливих рішення і . Їх має місце сам і лише з наступних трьох випадків:

1) справедливо співвідношення (>ЛПР перше рішення воліє другому),

2) справедливо співвідношення (>ЛПР друге рішення воліє першому),

3) не виконується ні співвідношення , ні співвідношення (>ЛПР неспроможна віддавати перевагу жодному із зазначених двох рішень).

Зауважимо, що четвертий випадок, коли обидва що беруть участь тут співвідношення і виконуються, неможливий завдяки асиметричності відносини переваги

У першому із зазначених вище випадків, тобто. і під час співвідношення , кажуть, що ухвалено рішення домінує рішення .

Якщо ж реалізується третій випадок, то кажуть, що рішення і можна порівняти стосовно переваги.

Аксіома Парето.

Всім пар допустимих рішень , котрим має місце нерівність , виконується співвідношення

Рішення називається оптимальним по Парето (>парето-оптимальним), а то й існує такого можливого рішення , котрій має місце нерівність . Усіпарето-оптимальние рішення утворюють безліч Парето, позначуване

>Парето-оптимальное рішення – це таке дозволене рішення, яка може бути поліпшено (збільшено) з жодного з наявних критеріїв без погіршення (зменшення) за якимось хоча б жодного іншого критерію.

Інакше висловлюючись, воліючи одномупарето-оптимальному рішенню іншепарето-оптимальное рішення,ЛПР(лицо, яка набирає рішення) змушене на певного компромісу, погоджуючись певну втрату хоча би за одному критерію (одержуючи, зрозуміло, певний виграш, по крайнього заходу, з якоїсь іншої критерію). Через це безліч Парето нерідко називають безліччю компромісів.

Поняття оптимальності по Парето відіграє в математичної економіці. Саме в області часто замістьпарето-оптимальности використовують найменування ефективне рішення і безліч ефективного розв'язання. Тим самим було,парето-оптимальность і ефективність у математичної економіці нерідко виявляються синонімами.


3. Реалізація програмного кошти.

Середовище розробки:Visual Studio 2010

Мова програмування: З#

3.1 Проектування

Під час проектування програмного кошти використовуватимемообъектно-ориентированний підхід.

Список класів з коротким описом:

1)MainView.cs – це головне вікно, служить для введення даних, і запуску роботи алгоритму пошукупарето-оптимальних рішень.

2)SolutionsView.cs – це немовбито вікно, яке містить знайденіпарето-оптимальние рішення, представлені у табличній формі

3)GraphView.cs – вікно, де буде відображатись графічне уявлення безлічі Парето длядвухкритериальних завдань

4)Pareto.cs – це основний клас. Містить 2 алгоритму пошуку безлічі Парето.

5)Graph.cs – клас, у якому методи для побудови графіків (у разі використовуватимемо сторонню бібліотекуZedGgraph.dll)

6)File.cs –методи задля збереження і завантаження даних у/ізфайл(а).

3.2 Алгоритм пошукупарето-оптимальних рішень

 

Крок 1. ПокластиP(Y) =Y , і =1, j = 2 . Тим самим було утворюється зване поточне безлічпарето-оптимальних векторів, яке на початку роботи алгоритму збігаються з безліччю Y , тож під кінець становитиме дані безлічпарето-оптимальних векторів. Алгоритм влаштований в такий спосіб, що дані безлічпарето-оптимальних векторів виходить з Y послідовним видаленням явнонеоптимальних векторів.

Крок 2. Перевірити виконання нерівності . Якщо він виявилося істинним, то можливість перейти доШагу 3. Інакше можливість перейти доШагу 5.

Крок 3. Видалити з поточного безлічі векторівP(Y) вектор , оскільки вона єпарето-оптимальним. Потім можливість перейти доШагу 4.

Крок 4. Перевірити виконання нерівності j < N . Якщо він має місце, то покласти j = j +1 і повернутися доШагу 2. Інакше – можливість перейти доШагу 7.

Крок 5. Перевірити справедливість нерівності . У разі, як його є справжнім, можливість перейти доШагу 6. Інакше – повернутися доШагу 4.

Крок 6. Видалити з поточного безлічі векторівP(Y) вектор перейти доШагу 7.

Крок 7. Перевірити виконання нерівності і < N -1. Що стосується істинності цього нерівності слід послідовно покласти і = і +1 , та був j = і +1. Після цього потрібні повернутися доШагу 2. Інакше (тобто. коли) обчислення закінчити. На той час безлічпарето-оптимальних векторів побудовано повністю.

Спочатку реалізуємо допоміжні методи:

//поелементное порівняння вектораv1 з векторомv2

privatevoidCompare(List<int>v1,List<int>v2)

 {

 >more = 0;

 >less = 0;

 >equal = 0;

 >for (>int і = 0; і <v1.Count; і++)

 {

 >if (>v1[i] >v2[i])

 >more++;

 >elseif (>v1[i] <v2[i])less++;

 >elseequal++;

 }

 }

 // повертає істину якщоv1 >=v2

 privateboolMoreOrEqual()

 {

 >if (>more >= 0 &&less == 0)

 >returntrue;

 >elsereturnfalse;

 }

Далі напишеморекурсивную процедуру видаленнядоминируемих рішень, спираючись на алгоритм, описане вище:

// y – список рішень

 publicvoidDeleteDominated(List<List<int>> y)

 {

 >foreach (>List<int>yi in y)

 {

 >foreach (>List<int>gj in y)

 {

 >if (!>Equals(gj,yi))

 {

 >Compare(gj,yi);

 >if (>MoreOrEqual())

 {

 >y.Remove(yi);

 >DeleteDominated(y);

 >return;

 }

 >Compare(yi,gj);

 >if (>MoreOrEqual())

 {

 >y.Remove(gj);

 >DeleteDominated(y);

 >return;

 }

 }

 }

 }

 

 }

І, насамкінець отримуємо метод,возвращающий списокпарето-оптимальних рішень:

 publicList<List<int>>GetParetoList(List<List<int>> y)

 {

 >DeleteDominated(y);

 >return y;

 }

3.3Листинг програмного коду

publicclassGraph

 {

 publicZedGraphControlDisplayGrahpics(Panelpanel,int[] x,int[] y,int[]pareto_x,int[]pareto_y)

 {

 >var control = newZedGraphControl();

 >control.Width =panel.Width;

 >control.Height =panel.Height;

 >GraphPanemyPane =control.GraphPane;

 //Set thetitle andaxislabels

 >myPane.Title.IsVisible =false;

 //>myPane.Title.Text =title;

 >myPane.XAxis.Title.IsVisible =false;

 >myPane.YAxis.Title.IsVisible =false;

 >myPane.YAxis.Scale.MaxAuto =true;

 >myPane.Legend.IsVisible =false;

 >PointPairListlist1 = newPointPairList();

 >for (>int і = 0; і <x.Length; і++)

 >list1.Add(x[i],y[i]);

 >LineItemcurve1 =myPane.AddCurve("label",list1,Color.Black,SymbolType.Circle);

 >curve1.Symbol.Fill = newFill(Color.Black);

 >curve1.Symbol.Size = 7;

 >curve1.Line.IsVisible =false;

 >PointPairListlist2 = newPointPairList();

 >for (>int і = 0; і <pareto_x.Length; і++)

 >list2.Add(pareto_x[i],pareto_y[i]);

 >LineItemcurve2 =myPane.AddCurve("label",list2,Color.Red,SymbolType.Circle);

 >curve2.Symbol.Fill = newFill(Color.Red);

 >curve2.Symbol.Size = 7;

 >curve2.Line.IsVisible =false;

 //Fill theaxisbackgroundwith acolorgradient

 >myPane.Chart.Fill = newFill(Color.White,Color.FromArgb(255, 255, 166),45.0F);

 >control.AxisChange();

 //expand therange of the Yaxisslightly toaccommodate thelabels

 >myPane.YAxis.Scale.Max +=myPane.YAxis.Scale.MajorStep;

 >return control;

 }

 }

publicclassFile

 {

 privateStreamWriterwriter;

 privateStreamReaderreader;

 publicvoidWriteData(List<List<int>> y,stringfileName)

 {

 >writer = newStreamWriter(newFileStream(fileName,FileMode.Create,FileAccess.Write));

 >writer.WriteLine(y.Count.ToString()+ " " +y[0].Count.ToString());

 >for (>int і = 0; і <y.Count; і++)

 {

 >for (>int j = 0; j <y[i].Count; j++)

 {

 >writer.Write(y[i][j].ToString() + " ");

 }

 >writer.WriteLine();

 }

 >writer.Close();

 }

 publicList<List<int>>ReadData(stringfileName)

 {

 >List<List<int>> y = newList<List<int>>();

 >intn,m;

 

 >reader = newStreamReader(newFileStream(fileName,FileMode.Open,FileAccess.Read));

 >while (!>reader.EndOfStream)

 {

 >char[]separator = { ' ' };

 >string[]vals =reader.ReadLine().Split(separator,StringSplitOptions.RemoveEmptyEntries);

 n =Convert.ToInt32(vals[0]);

 >m =Convert.ToInt32(vals[1]);

 >for (>int і = 0; і < n; і++)

 {

 >List<int> list = newList<int>();

 >vals =reader.ReadLine().Split(separator,StringSplitOptions.RemoveEmptyEntries);

 >for (>int j = 0; j <m; j++)

 {

 >list.Add(Convert.ToInt32(vals[j]));

 }

 >y.Add(list);

 }

 }

 >reader.Close();

 >return y;

 }

 }

publicpartialclassSolutionsView :Form

 {

 publicSolutionsView(List<List<int>> list)

 {

 >InitializeComponent();

 >int n =list[0].Count;

 >intm =list.Count;

 >dataGridView2.ColumnCount = n;

 >dataGridView2.RowCount =m;

 >for (>int і = 0; і <m; і++)

 {

 >for (>int j = 0; j < n; j++)

 >dataGridView2[j,i].Value =list[i][j];

 }

 }

 }

publicpartialclassGraphView :Form

 {

 publicGraphView()

 {

 >InitializeComponent();

 }

 publicPanelGetPanel()

 {

 >returnpanel1;

 }

 }

publicpartialclassMainView :Form

 {

 privateint n,m,krit,comp,var;

 privateList<List<int>> y;

 privateList<int>paretoSet;

 privateList<int>paretoSet2;

 

 privateParetopareto;

 

 publicMainView()

 {

 >InitializeComponent();

 >InitComboboxes(2, 20, 1);

 y = newList<List<int>>();

 >paretoSet = newList<int>();

 >dataGridView1.AllowUserToAddRows =false;

 >dgA.AllowUserToAddRows =false;

 >dgK.AllowUserToAddRows =false;

 >dgX.AllowUserToAddRows =false;

 }

 privatevoidInitComboboxes(intminimum,intmaximum,intstep)

 {

 >for (>int і =minimum; і <maximum;i+=step)

 {

 >comboBox1.Items.Add(i);

 >comboBox2.Items.Add(i);

 >comboBox3.Items.Add(i);

 >comboBox4.Items.Add(i);

 >comboBox5.Items.Add(i);

 }

 }

 privatevoidbutton1_Click(objectsender,EventArgs e)

 {

 n =Convert.ToInt32(comboBox1.Text);

 >m =Convert.ToInt32(comboBox2.Text);

 >dataGridView1.ColumnCount = n;

 >dataGridView1.RowCount =m;

 >for (>int і = 0; і < n; і++)

 >dataGridView1.Columns[i].Name = ">k" + (>i+1).ToString();

 }

 privatevoidGetValuesFromGrid()

 {

 y = newList<List<int>>();

 >if (>tabControl1.SelectedIndex == 0)

 {

 >for (>int і = 0; і <m; і++)

 {

 >var list = newList<int>();

 >for (>int j = 0; j < n; j++)

 >list.Add(Convert.ToInt32(dataGridView1[j,i].Value.ToString()));

 >y.Add(list);

 }

 }

 >elseif (>tabControl1.SelectedIndex == 1)

 {

 >for (>int і = 0; і <var; і++)

 {

 >var list = newList<int>();

 >for (>int j = 0; j <krit; j++)

 {

 >intsum = 0;

 >for (>intk = 0;k <comp;k++)

 {

 >intai =Convert.ToInt32(dgA[k,j].Value.ToString());

 >intki =Convert.ToInt32(dgK[k,j].Value.ToString());

 >intxi =Convert.ToInt32(dgX[k,i].Value.ToString());

 >sum +=ai *Convert.ToInt32(Math.Pow((double)xi, (>double)k));

 }

 >list.Add(sum);

 }

 >y.Add(list);

 }

 }

 }

 

 

 privatevoidbutton2_Click(objectsender,EventArgs e)

 {

 >textBox1.Text = "";

 >paretoSet = newList<int>();

 >if (>y.Count == 0)

 >GetValuesFromGrid();

 

 >pareto = newPareto();

 >paretoSet =pareto.GetPareto(y);

 >paretoSet2 =pareto.GetPareto2(y);

 >WriteList("метод1: ",>paretoSet);

 >WriteList("метод2: ",paretoSet2);

 >SolutionsViewsolView = newSolutionsView(pareto.GetParetoList(y));

 >solView.Show();

 >if (>krit == 2 ||n==2)

 >DrawGraph();

 }

 privatevoidWriteList(stringtext,List<int>set)

 {

 >textBox1.Text +=text;

 >foreach (>intval inset)

 >textBox1.Text += (>val+1).ToString() + "; ";

 }

 privatevoidInitGrid()

 {

 >krit =Convert.ToInt32(comboBox3.Text);

 >var =Convert.ToInt32(comboBox4.Text);

 >comp =Convert.ToInt32(comboBox5.Text);

 >dgA.ColumnCount =comp;

 >dgK.ColumnCount =comp;

 >dgX.ColumnCount =comp;

 >dgA.RowCount =krit;

 >dgK.RowCount =krit;

 >dgX.RowCount =var;

 }

 privatevoidbutton3_Click(objectsender,EventArgs e)

 {

 >InitGrid();

 >for (>intq = 0;q <comp;q++)

 {

 >dgK.Columns[q].Name = (>q +1).ToString();

 >dgA.Columns[q].Name = (>q +1).ToString();

 >dgX.Columns[q].Name = (>q +1).ToString();

 }

 }

 privatevoiddataGridView1_CellFormatting(objectsender,DataGridViewCellFormattingEventArgs e)

 {

 }

 //Двумерний випадок/ графічне уявлення

 privatevoidDrawGraph()

 {

 >GraphViewform2 = newGraphView();

 >form2.Show();

 >GetValuesFromGrid();

 >intcnt;

 >if (>m == 0)

 >cnt =var;

 >elsecnt =m;

 >int[] x_ = newint[cnt -paretoSet.Count];

 >int[] y_ = newint[cnt -paretoSet.Count];

 >for (>int і = 0; і <cnt -paretoSet.Count; і++)

 {

 >x_[i] =y[pareto.deleted[i]][0];

 >y_[i] =y[pareto.deleted[i]][1];

 }

 >cnt =paretoSet.Count;

 >int[]pareto_x = newint[cnt];

 >int[]pareto_y = newint[cnt];

 >for (>int і = 0; і <cnt; і++)

 {

 >pareto_x[i] =y[paretoSet[i]][0];

 >pareto_y[i] =y[paretoSet[i]][1];

 }

 >panel1 =form2.GetPanel();

 >var control = newGraph().DisplayGrahpics(panel1,x_,y_,pareto_x,pareto_y);

 >panel1.Controls.Clear();

 >panel1.Controls.Add(control);

 >panel1.Invalidate();

 }

 //Randomvalues

 privatevoidbutton2_Click_1(objectsender,EventArgs e)

 {

 >Randomrandom = newRandom();

 

 >if (>tabControl1.SelectedIndex == 0)

 {

 >for (>int і = 0; і <m; і++)

 {

 >for (>int j = 0; j < n; j++)

 {

 >dataGridView1[j,i].Value =random.Next(20);

 }

 }

 }

 >elseif (>tabControl1.SelectedIndex == 1)

 {

 >for (>int і = 0; і <comp; і++)

 {

 >for (>int j = 0; j <krit; j++)

 {

 >dgA[i,j].Value =random.Next(5);

 >dgK[i,j].Value =random.Next(5);

 }

 >for (>intq = 0;q <var;q++)

 {

 >dgX[i,q].Value =random.Next(5);

 }

 }

 }

 }

 privatevoidсохранитьКакToolStripMenuItem_Click(objectsender,EventArgs e)

 {

 >if (>this.saveFileDialog1.ShowDialog() ==DialogResult.OK)

 {

 >if (>y.Count == 0)

 >GetValuesFromGrid();

 newFile().WriteData(y,this.saveFileDialog1.FileName);

 }

 }

 privatevoidоткритьToolStripMenuItem_Click(objectsender,EventArgs e)

 {

 >if (>this.openFileDialog1.ShowDialog() ==DialogResult.OK)

 {

 y = newFile().ReadData(this.openFileDialog1.FileName);

 >FillGridFromList(y);

 }

 }

 privatevoidFillGridFromList(List<List<int>> list)

 {

 n =list[0].Count;

 >m =list.Count;

 >dataGridView1.ColumnCount = n;

 >dataGridView1.RowCount =m;

 >comboBox1.Text =n.ToString();

 >comboBox2.Text =m.ToString();

 

 >for (>int і = 0; і <m; і++)

 {

 >for (>int j = 0; j < n; j++)

 >dataGridView1[j,i].Value =list[i][j];

 

 }

 }

 }

}


4. Приклад роботи програми

4.1Многокритериальная завдання

1) Реалізуємо приклад, описаний в посібнику №1 зі списку використаної літератури. І тому скористаємося вже заготовленим файломпример1.txt:

2) Знайдемопарето-оптимальние рішення:


4.2Двухкритериальная завдання

1) Продемонструємо роботу програми длядвухкритериальной завдання. Нехай кількість рішень дорівнюватиме 11.

 

2) Результат роботи програми:


Червоним кольором виділенопарето-оптимальние рішення. Чорним –доминируемие рішення.


3.Аналитическое завдання критеріїв

Нехай кількість критеріїв 6

Кількість рішень 16

>Весовие значення перебуватимуть за такою формулою:

, деp – число критеріїв, n – кількість компонент рішення, a,k, x – задаються в таблиці:

У результаті дістаємо списокпарето-оптимальних рішень, які з трьох векторів:


Висновки

Через війну зробленого було розроблено програмне засіб на допомогу пошукупарето-оптимальних рішень длямногокритериальних завдань.

Дане додаток можна використовувати лише якдемонстрационно-обучающее на тему «>Многокритериальние завдання. Безліч Парето» дисципліни «Теорія прийняття рішень». Це з тим, що неможливо формалізувати математичну модель векторних оцінок. Кожна завдання пошуку оптимальних рішень вимагає власного підходу.


Використовувана література

1. В.Д.Ногин. Прийняття рішень під час багатьох критеріях.Учебнометодическое

посібник.– СПб. Видавництво «>ЮТАС», 2007. – 104 з.

2.Парето-оптимальние рішеннямногокритериальних завдань.Подинвоский В.В.,Ногин В.Д. –М. Головна редакція фізико-математичній літератури, 1982. –256с.

Використовувані програмні кошти

MicrosoftVisual Studio 2010


Схожі реферати:

Навігація