Оглавление
Оглавление. 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
Используемые программные средства. 291. Постановка задачи
математическаямодель парето оптимальность
Необходимо разработатьпрограммное средство для поиска парето-оптимальных решений для следующих видовзадач:
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;
}
}
}
}
}
И наконец получаем метод,возвращающий список парето-оптимальных решений:
publicList> 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)
{
}
//Двумерный случай/ графическое представление
privatevoid 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(objectsender, EventArgs e)
{
if (this.saveFileDialog1.ShowDialog() == DialogResult.OK)
{
if (y.Count == 0)
GetValuesFromGrid();
new File().WriteData(y, this.saveFileDialog1.FileName);
}
}
private void открытьToolStripMenuItem_Click(objectsender, 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