• 3.1 Проектування
  • 3.2 Алгоритм пошуку парето-оптимальних рішень
  • 3.3 Лістінгпрограммногокода
  • 4.1 Багатокритерійна завдання
  • 4.2 двухкрітеріальний завдання
  • 3. Аналітичне завдання критеріїв


  • Дата конвертації26.03.2017
    Розмір26.49 Kb.
    Типконтрольна робота

    Скачати 26.49 Kb.

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


    Зміст

    Зміст. 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. Реалізація програмного засобу.

    Середовище розробки: VisualStudio 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 ();

    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с.


    Програмні засоби

    MicrosoftVisualStudio 2010