Многокритериальные задачи. Метод альтернативных решений

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

Необходимо разработать программное средство для поиска альтернативных решений для следующей задачи:

·        многокритериальная задача

входные данные: количество критериев и решений; весовые значения, заданные напрямую, степень важности критериев, интервалы превосходства, цена перехода значения в соседний класс.

выходные данные: матрица согласия; матрица несогласия; ядро бинарного отношения.

программный альтернативный решение многокритериальный

2. Краткие теоретические сведения

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

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

Как правило, между множествами возможных решений X и соответствующим множеством векторов Y можно установить взаимно однозначное соответствие, т.е. каждому возможному решению поставить в соответствие определенный возможный вектор, и обратно - каждому возможному вектору сопоставить определенное возможное решение. В таких случаях выбор во множестве решений с математической точки зрения равносилен выбору во множестве векторов и все определения и результаты можно формулировать как в терминах решений, так и в терминах векторов, причем при желании всегда можно без труда осуществить переход от одной формы изложения к другой.

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

Необходимо отметить, что формирование математической модели принятия решений (т.е. построение множества X и векторного критерия f ) нередко представляет собой сложный процесс, в котором тесно взаимодействуют специалисты двух сторон. А именно, представители конкретной области знаний, к которой относится исследуемая проблема, и специалисты по принятию решений (математики). С одной стороны, следует учесть все важнейшие черты и детали реальной задачи, а с другой, - построенная модель не должна оказаться чрезмерно сложной с тем, чтобы для ее исследования и решения можно было успешно применить разработанный к настоящему времени соответствующий математический аппарат. Именно поэтому этап построения математической модели в значительной степени зависит от опыта, интуиции и искусства исследователей обеих сторон. Его невозможно отождествить с простым формальным применением уже известных, хорошо описанных алгоритмов.

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

Рассмотрим два произвольных возможных решения  и . Для них имеет место один и только один из следующих трех случаев:

) справедливо соотношение  (ЛПР первое решение предпочитает второму),

) справедливо соотношение  (ЛПР второе решение предпочитает первому),

) не выполняется ни соотношение , ни соотношение  (ЛПР не может отдать предпочтение ни одному из указанных двух решений).

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

В первом из указанных выше случаев, т.е. при выполнении соотношения , говорят, что решение  доминирует решение .

Если же реализуется третий случай, то говорят, что решения  и не сравнимы по отношению предпочтения.

3. Реализация программного средства

Среда разработки: Visual Studio 2008 Язык программирования: C#

3.1 Проектирование

При проектировании программного средства будем использовать объектно-ориентированный подход. Список классов с кратким описанием:

1)      Program.cs - это главное окно, служит для ввода данных, запуска работы алгоритма поиска парето-оптимальных решений, содержит методы для решения поставленной задачи.

2)      Reader.cs - методы для загрузки данных из файла

3)      Writer.cs - методы для сохранения данных в файл

.2 Алгоритм поиска альтернативных решений

Шаг 1. Назначение весов. Назначаются положительные веса каждого из критериев  Шаг 2. Построение индекса согласия. Для каждой пары альтернатив j и k множество критериев  разбивается на три группы:

,,

Множество  включает те категории, по которым j-я альтернатива лучше k-й, множество , состоит из критериев, которым j-я альтернатива хуже k-й, а множество , состоит из тех критериев, по которым j-я и k-я альтернативы эквивалентны. Индекс согласия с тем , что альтернатива j лучше альтернативы k определяется следующим образом:

,

Где α - параметр, α

Шаг 3. Построение списка несогласия. Для каждой пары j и k индекс несогласия с тем, что альтернатива j лучше альтернативы k определяется по формуле:

Где интервал превосходства k-й альтернативы над j-й по i-му критерию определяет число последовательных переходов из класса в класс, которое необходимо осуществить для того, чтобы j-й вариант стал эквивалентен k-му по i-му критерию, умноженное на цену одного деления такого перехода. При этом требуется, чтобы величины  не превышали единицу

Шаг 4. Построение решающего правила. На основе чисел  и  , определяемы ЛПР, на множестве альтернатив строится следующее бинарное отношение: j-я альтернтива признается лучше альтернативы k, при условии того, что . Сразу можно заметить, что при  указанное бинарное отношение становится аналогом бинарного отношения Слейтера, поскольку в этом случае j-я альтернатива доминирует k-ю лишь тогда, когда , т.е.  для всех . При  могут возникнуть другие пары альтернатив, связанные введенным бинарным отношением.

После того как бинарное отношение построено, представляется множество взаимнонедоминирующих альтернатив, на котором построенное бинарное отношение обладает НМ-свойством. Далее ЛПР выбирает окончательное решение из этого множества. Таким образом данный метод позволяет сократить число анализируемых вариантов, облегчая тем самым выбор ЛПР.

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

public partial class Form1 : Form

{int countOfVariant;int countOfCriterion;double p;double q;double alfa;int max = 0;double Interval = 0;int count1 = 0;int count2 = 0;int row1;int col1;static int rows;static int cols;Double[,] tablesWeight;Double[,] tablesCriterionImportance;Double[,] tablesIntervalSuperiority;Double[,] TableOfAgreementIndex;Double[,] TableOfDisagreementIndex;String[,] TableofDecisiveRule;

// private Double[,] tablesCriterionImportance;double CriterionSumm = 0;Form1()

{();

}

// получение числа вариантов, числа критериев и параметра альфаvoid GetDate()

{= (int)numericUpDown1.Value;= (int)numericUpDown2.Value;= Convert.ToDouble(comboBox1.Text);

}

// создание и заполнение таблицы весов из формыvoid createTableOfWeightFromForm()

{= new double[rows, cols];(int i = 0; i < rows; i++)

{(int j = 0; j < cols; j++)

{[i, j] = Convert.ToDouble(dataGridView1.Rows[i].Cells[j].Value);

}

}

}

// создание и заполнение таблицы важности критериев, числа интервалов превосходства

//и стоимость перехода с уровня на уровень из формыvoid createTableOfCriterionImportanceFromForm()

{= new double[cols, 3];(int i = 0; i < cols; i++)

{[i, 0] = Convert.ToDouble(dataGridView5.Rows[i].Cells[0].Value);+= tablesCriterionImportance[i, 0];

//textBox1.AppendText(CriterionSumm.ToString());

}

}

//создание таблицы интервалов превосходства из формыvoid createTableOfIntervalSuperiorityFromForm()

{= new double[cols, (max + 1)];(int i = 0; i < cols; i++)

{(int j = 0; j < (max + 1); j++)[i, j] = Convert.ToDouble(dataGridView6.Rows[i].Cells[j].Value);

}

}

//создание таблицы весов на формеvoid CreateTableOfWeightOnForm(int row, int col)

{_row = row;_col = col;.ColumnCount = _col;.RowHeadersVisible = false;.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells;.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;.RowCount = _row;

}

// создание таблицы важности критериев на формеvoid CreateTableOfCriterionImportanceOnForm(int row)

{_row = row;_col = 3;.ColumnCount = _col;.RowHeadersVisible = false;.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells;.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;.RowCount = _row;

}

// создание таблицы ядра из формыvoid CreateTableofDecisiveRuleFromForm()

{= new string[rows, 1];(int i = 0; i < rows; i++)

}

}void button1_Click(object sender, EventArgs e)

{();= (int)countOfVariant;= (int)countOfCriterion;(rows, cols);(cols);

}

//добавление интервала превосходстваvoid IntervalSuperiority(int row)

{(int i = 0; i < cols; i++)

{(max < Convert.ToDouble(dataGridView5.Rows[i].Cells[1].Value))

{= Convert.ToInt16(dataGridView5.Rows[i].Cells[1].Value);

}

}_row = row;_col = (max + 1);.ColumnCount = _col;.RowHeadersVisible = false;.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells;.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;.RowCount = _row;

}

// получение матрицы индексов согласияvoid GetTableOfAgreementIndex(int row, int col)

{IPlus = 0;IMinus = 0;IZero = 0;_row = row;_col = col;.ColumnCount = _col;.RowHeadersVisible = false;.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells;.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;.RowCount = _row;= new double[rows, rows];(int i = 0; i < rows; i++)

{(int j = 0; j < rows; j++)

{(i == j)

{[i, j] = 0;

}

{= 0;= 0;= 0;(int k = 0; k < cols; k++)

{(Convert.ToDouble(dataGridView1.Rows[i].Cells[k].Value) > Convert.ToDouble(dataGridView1.Rows[j].Cells[k].Value))

{+= Convert.ToDouble(dataGridView5.Rows[k].Cells[0].Value);

}if (Convert.ToDouble(dataGridView1.Rows[i].Cells[k].Value) == Convert.ToDouble(dataGridView1.Rows[j].Cells[k].Value))

{+= Convert.ToDouble(dataGridView5.Rows[k].Cells[0].Value);

}

{+= Convert.ToDouble(dataGridView5.Rows[k].Cells[0].Value);

}

}[i, j] = (IPlus + alfa * IZero) / (CriterionSumm);

}.Rows[i].Cells[j].Value = TableOfAgreementIndex[i, j];

}

}

}

получение матрицы индексов несогласияvoid GetTableOfDisagreementIndex(int row, int col)

{[,] count;_row = row;_col = col;.ColumnCount = _col;.RowHeadersVisible = false;.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells;.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;.RowCount = _row;= new double[cols, 2];= new double[rows, rows];(int i = 0; i < rows; i++)

{(int j = 0; j < rows; j++)

{(i == j)

{[i, j] = 0;

}

{= 0;(int k = 0; k < cols; k++)

{[k, 0] = 0;[k, 1] = 0;= 0;= 0;(int m = 0; m < (Convert.ToInt32(dataGridView5.Rows[k].Cells[1].Value) + 1); m++)

{(Convert.ToDouble(dataGridView1.Rows[i].Cells[k].Value) > Convert.ToDouble(dataGridView6.Rows[k].Cells[m].Value))

{+= 1;

}

{= count1;

}(Convert.ToDouble(dataGridView1.Rows[j].Cells[k].Value) > Convert.ToDouble(dataGridView6.Rows[k].Cells[m].Value))

{+= 1;

}

{= count2;

}

/* textBox1.AppendText(" ");.AppendText(count1.ToString());.AppendText(" ");.AppendText(count2.ToString());

//textBox1.AppendText(" ");

//textBox1.AppendText(dataGridView1.Rows[i].Cells[k].Value.ToString());*/

}[k, 0] = count1;[k, 1] = count2;(count[k, 0] < count[k, 1])

{+= (count[k, 1] - count[k, 0]) * (Convert.ToDouble(dataGridView5.Rows[k].Cells[2].Value));

}

{= Interval;

}[i, j] = Interval/100;.AppendText(" ");.AppendText(Interval.ToString());

}

}.Rows[i].Cells[j].Value = TableOfDisagreementIndex[i, j];

}

}

}

получение параметров p и qvoid GetParametrsForDecisiveRule()

{= Convert.ToDouble(numericUpDown3.Value);= Convert.ToDouble(numericUpDown4.Value);

}

//построение решающего правилаvoid GetDecisiveRule(int row,int col)

{flag = false;count = 0;countOfq = 0;countOfp = 0;_row = row;_col = col;.ColumnCount = _col;.RowHeadersVisible = false;.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells;.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;.RowCount = _row;(int i = 0; i < rows; i++)

{= 0;= 0;= 0;(int j = 0; j < cols; j++)

{+= 1;(i != j)

{(Convert.ToInt32(dataGridView3.Rows[i].Cells[j].Value) < q)

{+= 1;(Convert.ToInt32(dataGridView2.Rows[i].Cells[j].Value) < p)

{+= 1;

{((count == cols) & (countOfp == 0))

{= true;

}

}

}

{((count == cols) & (countOfq == 0))

{= true;

}

}

}

}.Rows[i].Cells[0].Value = flag;

}

}void button2_Click(object sender, EventArgs e)

{();();(rows, rows);

}

void button3_Click(object sender, EventArgs e)

{(rows, rows);

}void закрытьToolStripMenuItem_Click(object sender, EventArgs e)

{();

}void button6_Click(object sender, EventArgs e)

{(cols);

}void button5_Click(object sender, EventArgs e)

{(rows, 1);();

}void button4_Click(object sender, EventArgs e)

{();

}

//загрузка таблицы весовvoid button8_Click(object sender, EventArgs e)

{FN;(openFileDialog1.ShowDialog() == DialogResult.OK)

{.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";= openFileDialog1.FileName;My = new Reader(FN);.ReadTable(out tablesWeight, out rows, out cols);= Convert.ToDouble(comboBox1.Text);(rows, cols);(int i = 0; i < rows; i++)

{(int j = 0; j < cols; j++)

{.Rows[i].Cells[j].Value = tablesWeight[i, j];

}

}

}

}

// сохранение таблицы весовvoid button7_Click(object sender, EventArgs e)

{FN;.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";(saveFileDialog1.ShowDialog() == DialogResult.OK)

{= saveFileDialog1.FileName;.WriteTable(FN, tablesWeight);

}

}

// загрузка таблицы критериев важностиvoid button9_Click(object sender, EventArgs e)

{FN;(openFileDialog1.ShowDialog() == DialogResult.OK)

{.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";= openFileDialog1.FileName;My = new Reader(FN);.ReadTable(out tablesCriterionImportance, out row1, out col1);= Convert.ToDouble(comboBox1.Text);(row1);(int i = 0; i < row1; i++)

{(int j = 0; j < col1; j++)

{.Rows[i].Cells[j].Value = tablesCriterionImportance[i, j];

}

}

}

}

// загрузка таблицы интервалов превосходстваvoid button11_Click(object sender, EventArgs e)

{FN;(openFileDialog1.ShowDialog() == DialogResult.OK)

{.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";= openFileDialog1.FileName;My = new Reader(FN);.ReadTable(out tablesIntervalSuperiority, out row1, out col1);= Convert.ToDouble(comboBox1.Text);(row1);(int i = 0; i < row1; i++)

{(int j = 0; j < col1; j++)

{.Rows[i].Cells[j].Value = tablesIntervalSuperiority[i, j];

}

}

}

}

//сохранение таблицы критериев важностиvoid button10_Click(object sender, EventArgs e)

{FN;.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";(saveFileDialog1.ShowDialog() == DialogResult.OK)

{= saveFileDialog1.FileName;.WriteTable(FN, tablesCriterionImportance);

}

}

// сохранение таблицы интервалов превосходстваvoid button12_Click(object sender, EventArgs e)

{FN;.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";(saveFileDialog1.ShowDialog() == DialogResult.OK)

{= saveFileDialog1.FileName;.WriteTable(FN, tablesIntervalSuperiority);

}

}

// сохранение матрицы индексов согласияvoid button13_Click(object sender, EventArgs e)

{FN;.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";(saveFileDialog1.ShowDialog() == DialogResult.OK)

}

}

//сохранение матрицы индексов несогласияvoid button14_Click(object sender, EventArgs e)

{FN;.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";(saveFileDialog1.ShowDialog() == DialogResult.OK)

{= saveFileDialog1.FileName;.WriteTable(FN, TableOfDisagreementIndex);

}

}

//сохранение ядраvoid button15_Click(object sender, EventArgs e)

{FN;.InitialDirectory = "G:\temp";.Filter = "diag files(*.diag)|*.abs|All files|*.*";(saveFileDialog1.ShowDialog() == DialogResult.OK)

{= saveFileDialog1.FileName;.WriteTableOfRule(FN, TableofDecisiveRule);

}

}

}Reader

{string fileName;string[] inputTxt;double[,] matrix;int row;int col;System.Globalization.NumberFormatInfo numberFormat;Reader(string Name)

{= Name;

}void ReadTable(out double[,] table, out int rows, out int cols)

{= new System.Globalization.NumberFormatInfo();.CurrencyDecimalSeparator = ".";[] output = File.ReadAllLines(fileName);[] aloneString = output[0].Split(new char[] { ' ' });

//double[,] temp = new double[output.Length, aloneString.Length];= new double[output.Length, aloneString.Length];= output.Length;= aloneString.Length;(int i = 0; i < aloneString.Length; i++)

{[0, i] = double.Parse(aloneString[i], numberFormat);

}(int i = 1; i < output.Length; i++)

{= output[i].Split(new char[] { ' ' });(int j = 0; j < aloneString.Length; j++)

{[i, j] = double.Parse(aloneString[j], numberFormat);

}

}

}

}Writer

{static string fileName;static string[] outputTxt;static double[,] matrix;static string[,] matrix1;static int row;static int col;static System.Globalization.NumberFormatInfo numberFormat;static void WriteTable(string nameFile, double[,] table)

{.fileName = nameFile;.matrix = table;(Writer.matrix != null)

{= matrix.GetLength(0);= matrix.GetLength(1);= new string[row];(int i = 0; i < row; i++)

{(int j = 0; j < col; j++)

{[i] += matrix[i, j].ToString();(j != (col - 1))[i] += " ";

}

}.WriteAllLines(nameFile, outputTxt);

}

}static void WriteTableOfRule(string nameFile, string[,] table)

{.fileName = nameFile;.matrix1 = table;(Writer.matrix1 != null)

{= matrix1.GetLength(0);= matrix1.GetLength(1);= new string[row];(int i = 0; i < row; i++)

{(int j = 0; j < col; j++)

{[i] += matrix1[i, j];(j != (col - 1))[i] += " ";

}

}.WriteAllLines(nameFile, outputTxt);

}

}

}

4. Пример работы программы

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

1)      Реализуем пример. Для этого воспользуемся уже заготовленными файлами с входными данными:

Рис

Найдем матрицу согласия:

Рис

Найдем матрицу индексов несогласия:

Рис

Найдем ядро бинарного отношения:

Рис

Выводы

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

Данное приложение может использоваться лишь как демонстрационно-обучающее по теме «Многокритериальные задачи. Метод альтернативных решений» дисциплины «Теория принятия решений».

Используемая литература

1. А.В Лотов, И.И. Поспелова Многокритериальные задачи принятия решения Учебное пособие.- М. : МАКС Пресс, 2008. - 197 с.

Используемые программные средства

Microsoft Visual Studio 2008