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

Зміст

Зміст. 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

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

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, i = 1, j = 2. Тим самим утворюється так зване поточне безліч Парето-оптимальних векторів, яке на початку роботи алгоритму збігається з безліччю Y, а в кінці складе шукане безліч Парето-оптимальних векторів. Алгоритм влаштований таким чином, що шукане безліч Парето-оптимальних векторів виходить з Y послідовним видаленням свідомо неоптимальних векторів.

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

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

Крок 4. Перевірити виконання нерівності j

Крок 5. Перевірити справедливість нерівності. У тому випадку, коли воно є істинним, перейти до Кроку 6. В іншому випадку - повернутися до Кроку 4.

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

Крок 7. Перевірити виконання нерівності i

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

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

private void Compare (List v1, List v2)

{

more = 0;

less = 0;

equal = 0;

for (int i = 0; i

{

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

more + +;

else if (v1 [i]

else equal + +;

}

}

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

private bool MoreOrEqual ()

{

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

return true;

else return false;

}

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

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

public void DeleteDominated (List > y)

{

foreach (List yi in y)

{

foreach (List 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;

}

}

}

}

}

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

public List > GetParetoList (List > y)

{

DeleteDominated (y);

return y;

}

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

public class Graph

{

public ZedGraphControl DisplayGrahpics (Panel panel, int [] x, int [] y, int [] pareto_x, int [] pareto_y)

{

var control = new ZedGraphControl ();

control.Width = panel.Width;

control.Height = panel.Height;

GraphPane myPane = control.GraphPane;

// Set the title and axis labels

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;

PointPairList list1 = new PointPairList ();

for (int i = 0; i

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

LineItem curve1 = myPane.AddCurve ("label", list1, Color.Black, SymbolType.Circle);

curve1.Symbol.Fill = new Fill (Color.Black);

curve1.Symbol.Size = 7;

curve1.Line.IsVisible = false;

PointPairList list2 = new PointPairList ();

for (int i = 0; i

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

LineItem curve2 = myPane.AddCurve ("label", list2, Color.Red, SymbolType.Circle);

curve2.Symbol.Fill = new Fill (Color.Red);

curve2.Symbol.Size = 7;

curve2.Line.IsVisible = false;

// Fill the axis background with a color gradient

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

control.AxisChange ();

// expand the range of the Y axis slightly to accommodate the labels

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

return control;

}

}

public class File

{

private StreamWriter writer;

private StreamReader reader;

public void WriteData (List > y, string fileName)

{

writer = new StreamWriter (new FileStream (fileName, FileMode.Create, FileAccess.Write));

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

for (int i = 0; i

{

for (int j = 0; j

{

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

}

writer.WriteLine ();

}

writer.Close ();

}

public List > ReadData (string fileName)

{

List > y = new List > ();

int n, m;

reader = new StreamReader (new FileStream (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 i = 0; i

{

List list = new List ();

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

for (int j = 0; j

{

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

}

y.Add (list);

}

}

reader.Close ();

return y;

}

}

public partial class SolutionsView: Form

{

public SolutionsView (List > list)

{

InitializeComponent ();

int n = list [0]. Count;

int m = list.Count;

dataGridView2.ColumnCount = n;

dataGridView2.RowCount = m;

for (int i = 0; i

{

for (int j = 0; j

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

}

}

}

public partial class GraphView: Form

{

public GraphView ()

{

InitializeComponent ();

}

public Panel GetPanel ()

{

return panel1;

}

}

public partial class MainView: Form

{

private int n, m, krit, comp, var;

private List > y;

private List paretoSet;

private List paretoSet2;

private Pareto pareto;

public MainView ()

{

InitializeComponent ();

InitComboboxes (2, 20, 1);

y = new List > ();

paretoSet = new List ();

dataGridView1.AllowUserToAddRows = false;

dgA.AllowUserToAddRows = false;

dgK.AllowUserToAddRows = false;

dgX.AllowUserToAddRows = false;

}

private void InitComboboxes (int minimum, int maximum, int step)

{

for (int i = minimum; i

{

comboBox1.Items.Add (i);

comboBox2.Items.Add (i);

comboBox3.Items.Add (i);

comboBox4.Items.Add (i);

comboBox5.Items.Add (i);

}

}

private void button1_Click (object sender, EventArgs e)

{

n = Convert.ToInt32 (comboBox1.Text);

m = Convert.ToInt32 (comboBox2.Text);

dataGridView1.ColumnCount = n;

dataGridView1.RowCount = m;

for (int i = 0; i

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

}

private void GetValuesFromGrid ()

{

y = new List > ();

if (tabControl1.SelectedIndex == 0)

{

for (int i = 0; i

{

var list = new List ();

<...p> for (int j = 0; j

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

y.Add (list);

}

}

else if (tabControl1.SelectedIndex == 1)

{

for (int i = 0; i

{

var list = new List ();

for (int j = 0; j

{

int sum = 0;

for (int k = 0; k

{

int ai = Convert.ToInt32 (dgA [k, j]. Value.ToString ());

int ki = Convert.ToInt32 (dgK [k, j]. Value.ToString ());

int xi = Convert.ToInt32 (dgX [k, i]. Value.ToString ());

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

}

list.Add (sum);

}

y.Add (list);

}

}

}

private void button2_Click (object sender, EventArgs e)

{

textBox1.Text = "";

paretoSet = new List ();

if (y.Count == 0)

GetValuesFromGrid ();

pareto = new Pareto ();

paretoSet = pareto.GetPareto (y);

paretoSet2 = pareto.GetPareto2 (y);

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

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

SolutionsView solView = new SolutionsView (pareto.GetParetoList (y));

solView.Show ();

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

DrawGraph ();

}

private void WriteList (string text, List set)

{

textBox1.Text + = text;

foreach (int val in set)

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

}

private void InitGrid ()

{

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;

}

private void button3_Click (object sender, EventArgs e)

{

InitGrid ();

for (int q = 0; q

{

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

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

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

}

}

private void dataGridView1_CellFormatting (object sender, DataGridViewCellFormattingEventArgs e)

{

}

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

private void DrawGraph ()

{

GraphView form2 = new GraphView ();

form2.Show ();

GetValuesFromGrid ();

int cnt;

if (m == 0)

cnt = var;

else cnt = m;

int [] x_ = new int [cnt - paretoSet.Count];

int [] y_ = new int [cnt - paretoSet.Count];

for (int i = 0; i

{

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

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

}

cnt = paretoSet.Count;

int [] pareto_x = new int [cnt];

int [] pareto_y = new int [cnt];

for (int i = 0; i

{

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

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

}

panel1 = form2.GetPanel ();

var control = new Graph (). DisplayGrahpics (panel1, x_, y_, pareto_x, pareto_y);

panel1.Controls.Clear ();

panel1.Controls.Add (control);

panel1.Invalidate ();

}

// Random values ​​

private void button2_Click_1 (object sender, EventArgs e)

{

Random random = new Random ();

if (tabControl1.SelectedIndex == 0)

{

for (int i = 0; i

{

for (int j = 0; j

{

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

}

}

}

else if (tabControl1.SelectedIndex == 1)

{

for (int i = 0; i

{

for (int j = 0; j

{

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

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

}

for (int q = 0; q

{

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

}

}

}

}

private void сохранітьКакToolStripMenuItem_Click (object sender, EventArgs e)

{

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

{

if (y.Count == 0)

GetValuesFromGrid ();

new File (). WriteData (y, this.saveFileDialog1.FileName);

}

}

private void откритьToolStripMenuItem_Click (object sender, EventArgs e)

{

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

{

y = new File (). ReadData (this.openFileDialog1.FileName);

FillGridFromList (y);

}

}

private void FillGridFromList (List > list)

{

n = list [0]. Count;

m = list.Count;

dataGridView1.ColumnCount = n;

dataGridView1.RowCount = m;

comboBox1.Text = n.ToString ();

comboBox2.Text = m.ToString ();

for (int i = 0; i

{

for (int j = 0; 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с.

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

Microsoft Visual Studio 2010