|
Контрольная работа: Многокритериальные задачи. Метод альтернативных решенийКонтрольная работа: Многокритериальные задачи. Метод альтернативных решений1. Постановка задачиНеобходимо разработать программное средство для поиска альтернативных решений для следующей задачи: · многокритериальная задача входные данные: количество критериев и решений; весовые значения, заданные напрямую, степень важности критериев, интервалы превосходства, цена перехода значения в соседний класс. выходные данные: матрица согласия; матрица несогласия; ядро бинарного отношения. программный альтернативный решение многокритериальный 2. Краткие теоретические сведенияПусть задан набор числовых функций , определенных на множестве возможных решений X. В зависимости от содержания задачи выбора эти функции именуют критериями оптимальности, критериями эффективности или целевыми функциями. Указанные выше числовые функции образуют векторный критерий , который принимает значения в пространстве m-мерных векторов . Это пространство называют критериальным пространством или пространством оценок, а всякое значение именуют векторной оценкой возможного решения x. Все возможные векторные оценки образуют множество возможных оценок (возможных или допустимых векторов) Как правило, между множествами возможных решений X и соответствующим множеством векторов Y можно установить взаимно однозначное соответствие, т.е. каждому возможному решению поставить в соответствие определенный возможный вектор, и обратно – каждому возможному вектору сопоставить определенное возможное решение. В таких случаях выбор во множестве решений с математической точки зрения равносилен выбору во множестве векторов и все определения и результаты можно формулировать как в терминах решений, так и в терминах векторов, причем при желании всегда можно без труда осуществить переход от одной формы изложения к другой. Задачу выбора, которая включает множество допустимых решений X и векторный критерий f, обычно называют многокритериальной задачей или задачей многокритериальной оптимизации. Необходимо отметить, что формирование математической модели принятия решений (т.е. построение множества X и векторного критерия f ) нередко представляет собой сложный процесс, в котором тесно взаимодействуют специалисты двух сторон. А именно, представители конкретной области знаний, к которой относится исследуемая проблема, и специалисты по принятию решений (математики). С одной стороны, следует учесть все важнейшие черты и детали реальной задачи, а с другой, – построенная модель не должна оказаться чрезмерно сложной с тем, чтобы для ее исследования и решения можно было успешно применить разработанный к настоящему времени соответствующий математический аппарат. Именно поэтому этап построения математической модели в значительной степени зависит от опыта, интуиции и искусства исследователей обеих сторон. Его невозможно отождествить с простым формальным применением уже известных, хорошо описанных алгоритмов. Здесь следует еще добавить, что любая задача выбора (в том числе и многокритериальная) тесно связана с конкретным ЛПР(лицо, принимающее решение). Уже на стадии формирования математической модели при построении множества возможных решений и векторного критерия дело не обходится без советов, рекомендаций и указаний ЛПР, тем более что векторный критерий как раз и служит. Принятие решения при многих критериях для выражения целей ЛПР. При этом ясно, что построить модель в точности соответствующую всем реальным обстоятельствам невозможно. Модель всегда является упрощением действительности. Важно добиться, чтобы она содержала те черты и детали, которые в наибольшей степени влияют на окончательный выбор наилучшего решения. Рассмотрим два произвольных возможных решения и . Для них имеет место один и только один из следующих трех случаев: 1) справедливо соотношение (ЛПР первое решение предпочитает второму), 2) справедливо соотношение (ЛПР второе решение предпочитает первому), 3) не выполняется ни соотношение , ни соотношение (ЛПР не может отдать предпочтение ни одному из указанных двух решений). Заметим, что четвертый случай, когда оба участвующих здесь соотношения и выполняются, невозможен благодаря асимметричности отношения предпочтения В первом из указанных выше случаев, т.е. при выполнении соотношения , говорят, что решение доминирует решение . Если же реализуется третий случай, то говорят, что решения и не сравнимы по отношению предпочтения. 3. Реализация программного средства Среда разработки: Visual Studio 2008 Язык программирования: C# 3.1 ПроектированиеПри проектировании программного средства будем использовать объектно-ориентированный подход. Список классов с кратким описанием: 1) Program.cs – это главное окно, служит для ввода данных, запуска работы алгоритма поиска парето-оптимальных решений, содержит методы для решения поставленной задачи. 2) Reader.cs – методы для загрузки данных из файла 3) Writer.cs – методы для сохранения данных в файл 3.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 { private int countOfVariant; private int countOfCriterion; private double p; private double q; private double alfa; private int max = 0; private double Interval = 0; private int count1 = 0; private int count2 = 0; private int row1; private int col1; private static int rows; private static int cols; private Double[,] tablesWeight; private Double[,] tablesCriterionImportance; private Double[,] tablesIntervalSuperiority; private Double[,] TableOfAgreementIndex; private Double[,] TableOfDisagreementIndex; private String[,] TableofDecisiveRule; // private Double[,] tablesCriterionImportance; private double CriterionSumm = 0; public Form1() { InitializeComponent(); } // получение числа вариантов, числа критериев и параметра альфа private void GetDate() { countOfVariant = (int)numericUpDown1.Value; countOfCriterion = (int)numericUpDown2.Value; alfa = Convert.ToDouble(comboBox1.Text); } // создание и заполнение таблицы весов из формы private void createTableOfWeightFromForm() { tablesWeight = new double[rows, cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { tablesWeight[i, j] = Convert.ToDouble(dataGridView1.Rows[i].Cells[j].Value); } } } // создание и заполнение таблицы важности критериев, числа интервалов превосходства //и стоимость перехода с уровня на уровень из формы private void createTableOfCriterionImportanceFromForm() { tablesCriterionImportance = new double[cols, 3]; for (int i = 0; i < cols; i++) { tablesCriterionImportance[i, 0] = Convert.ToDouble(dataGridView5.Rows[i].Cells[0].Value); CriterionSumm += tablesCriterionImportance[i, 0]; //textBox1.AppendText(CriterionSumm.ToString()); } } //создание таблицы интервалов превосходства из формы private void createTableOfIntervalSuperiorityFromForm() { tablesIntervalSuperiority = new double[cols, (max + 1)]; for (int i = 0; i < cols; i++) { for (int j = 0; j < (max + 1); j++) tablesIntervalSuperiority[i, j] = Convert.ToDouble(dataGridView6.Rows[i].Cells[j].Value); } } //создание таблицы весов на форме private void CreateTableOfWeightOnForm(int row, int col) { int _row = row; int _col = col; dataGridView1.ColumnCount = _col; dataGridView1.RowHeadersVisible = false; dataGridView1.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells; dataGridView1.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells; dataGridView1.RowCount = _row; } // создание таблицы важности критериев на форме private void CreateTableOfCriterionImportanceOnForm(int row) { int _row = row; int _col = 3; dataGridView5.ColumnCount = _col; dataGridView5.RowHeadersVisible = false; dataGridView5.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells; dataGridView5.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells; dataGridView5.RowCount = _row; } // создание таблицы ядра из формы private void CreateTableofDecisiveRuleFromForm() { TableofDecisiveRule = new string[rows, 1]; for (int i = 0; i < rows; i++) { TableofDecisiveRule[i, 0] = dataGridView4.Rows[i].Cells[0].Value.ToString(); } } private void button1_Click(object sender, EventArgs e) { GetDate(); rows = (int)countOfVariant; cols = (int)countOfCriterion; CreateTableOfWeightOnForm(rows, cols); CreateTableOfCriterionImportanceOnForm(cols); } //добавление интервала превосходства private void IntervalSuperiority(int row) { for (int i = 0; i < cols; i++) { if (max < Convert.ToDouble(dataGridView5.Rows[i].Cells[1].Value)) { max = Convert.ToInt16(dataGridView5.Rows[i].Cells[1].Value); } } int _row = row; int _col = (max + 1); dataGridView6.ColumnCount = _col; dataGridView6.RowHeadersVisible = false; dataGridView6.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells; dataGridView6.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells; dataGridView6.RowCount = _row; } // получение матрицы индексов согласия private void GetTableOfAgreementIndex(int row, int col) { double IPlus = 0; double IMinus = 0; double IZero = 0; int _row = row; int _col = col; dataGridView2.ColumnCount = _col; dataGridView2.RowHeadersVisible = false; dataGridView2.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells; dataGridView2.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells; dataGridView2.RowCount = _row; TableOfAgreementIndex = new double[rows, rows]; for (int i = 0; i < rows; i++) { for (int j = 0; j < rows; j++) { if (i == j) { TableOfAgreementIndex[i, j] = 0; } else { IPlus = 0; IMinus = 0; IZero = 0; for(int k = 0; k < cols; k++) { if (Convert.ToDouble(dataGridView1.Rows[i].Cells[k].Value) > Convert.ToDouble(dataGridView1.Rows[j].Cells[k].Value)) { IPlus += Convert.ToDouble(dataGridView5.Rows[k].Cells[0].Value); } else if (Convert.ToDouble(dataGridView1.Rows[i].Cells[k].Value) == Convert.ToDouble(dataGridView1.Rows[j].Cells[k].Value)) { IZero += Convert.ToDouble(dataGridView5.Rows[k].Cells[0].Value); } else { IMinus += Convert.ToDouble(dataGridView5.Rows[k].Cells[0].Value); } } TableOfAgreementIndex[i, j] = (IPlus + alfa * IZero) / (CriterionSumm); } dataGridView2.Rows[i].Cells[j].Value = TableOfAgreementIndex[i, j]; } } } получение матрицы индексов несогласия private void GetTableOfDisagreementIndex(int row, int col) { Double[,] count; int _row = row; int _col = col; dataGridView3.ColumnCount = _col; dataGridView3.RowHeadersVisible = false; dataGridView3.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells; dataGridView3.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells; dataGridView3.RowCount = _row; count = new double[cols, 2]; TableOfDisagreementIndex = new double[rows, rows]; for (int i = 0; i < rows; i++) { for (int j = 0; j < rows; j++) { if (i == j) { TableOfDisagreementIndex[i, j] = 0; } else { Interval = 0; for (int k = 0; k < cols; k++) { count[k, 0] = 0; count[k, 1] = 0; count1 = 0; count2 = 0; for (int m = 0; m < (Convert.ToInt32(dataGridView5.Rows[k].Cells[1].Value) + 1); m++) { if (Convert.ToDouble(dataGridView1.Rows[i].Cells[k].Value) > Convert.ToDouble(dataGridView6.Rows[k].Cells[m].Value)) { count1 += 1; } else { count1 = count1; } if (Convert.ToDouble(dataGridView1.Rows[j].Cells[k].Value) > Convert.ToDouble(dataGridView6.Rows[k].Cells[m].Value)) { count2 += 1; } else { count2 = count2; } /* textBox1.AppendText(" "); textBox1.AppendText(count1.ToString()); textBox1.AppendText(" "); textBox1.AppendText(count2.ToString()); //textBox1.AppendText(" "); //textBox1.AppendText(dataGridView1.Rows[i].Cells[k].Value.ToString());*/ } count[k, 0] = count1; count[k, 1] = count2; if (count[k, 0] < count[k, 1]) { Interval += (count[k, 1] - count[k, 0]) * (Convert.ToDouble(dataGridView5.Rows[k].Cells[2].Value)); } else { Interval = Interval; } TableOfDisagreementIndex[i, j] = Interval/100; textBox1.AppendText(" "); textBox1.AppendText(Interval.ToString()); } } dataGridView3.Rows[i].Cells[j].Value = TableOfDisagreementIndex[i, j]; } } } получение параметров p и q private void GetParametrsForDecisiveRule() { p = Convert.ToDouble(numericUpDown3.Value); q = Convert.ToDouble(numericUpDown4.Value); } //построение решающего правила private void GetDecisiveRule(int row,int col) { bool flag = false; int count = 0; int countOfq = 0; int countOfp = 0; int _row = row; int _col = col; dataGridView4.ColumnCount = _col; dataGridView4.RowHeadersVisible = false; dataGridView4.AutoSizeRowsMode = DataGridViewAutoSizeRowsMode.AllCells; dataGridView4.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells; dataGridView4.RowCount = _row; for (int i = 0; i < rows; i++) { count = 0; countOfq = 0; countOfp = 0; for (int j = 0; j < cols; j++) { count += 1; if (i != j) { if (Convert.ToInt32(dataGridView3.Rows[i].Cells[j].Value) < q) { countOfq += 1; if (Convert.ToInt32(dataGridView2.Rows[i].Cells[j].Value) < p) { countOfp += 1; } else { if ((count == cols) & (countOfp == 0)) { flag = true; } } } else { if ((count == cols) & (countOfq == 0)) { flag = true; } } } } dataGridView4.Rows[i].Cells[0].Value = flag; } } private void button2_Click(object sender, EventArgs e) { createTableOfCriterionImportanceFromForm(); createTableOfWeightFromForm(); GetTableOfAgreementIndex(rows, rows); } private void button3_Click(object sender, EventArgs e) { GetTableOfDisagreementIndex(rows, rows); } private void закрытьToolStripMenuItem_Click(object sender, EventArgs e) { Close(); } private void button6_Click(object sender, EventArgs e) { IntervalSuperiority(cols); } private void button5_Click(object sender, EventArgs e) { GetDecisiveRule(rows, 1); CreateTableofDecisiveRuleFromForm(); } private void button4_Click(object sender, EventArgs e) { GetParametrsForDecisiveRule(); } //загрузка таблицы весов private void button8_Click(object sender, EventArgs e) { string FN; if (openFileDialog1.ShowDialog() == DialogResult.OK) { openFileDialog1.InitialDirectory = "G:\temp"; openFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; FN = openFileDialog1.FileName; Reader My = new Reader(FN); My.ReadTable(out tablesWeight, out rows, out cols); alfa = Convert.ToDouble(comboBox1.Text); CreateTableOfWeightOnForm(rows, cols); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { dataGridView1.Rows[i].Cells[j].Value = tablesWeight[i, j]; } } } } // сохранение таблицы весов private void button7_Click(object sender, EventArgs e) { string FN; saveFileDialog1.InitialDirectory = "G:\temp"; saveFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; if (saveFileDialog1.ShowDialog() == DialogResult.OK) { FN = saveFileDialog1.FileName; Writer.WriteTable(FN, tablesWeight); } } // загрузка таблицы критериев важности private void button9_Click(object sender, EventArgs e) { string FN; if (openFileDialog1.ShowDialog() == DialogResult.OK) { openFileDialog1.InitialDirectory = "G:\temp"; openFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; FN = openFileDialog1.FileName; Reader My = new Reader(FN); My.ReadTable(out tablesCriterionImportance, out row1, out col1); alfa = Convert.ToDouble(comboBox1.Text); CreateTableOfCriterionImportanceOnForm(row1); for (int i = 0; i < row1; i++) { for (int j = 0; j < col1; j++) { dataGridView5.Rows[i].Cells[j].Value = tablesCriterionImportance[i, j]; } } } } // загрузка таблицы интервалов превосходства private void button11_Click(object sender, EventArgs e) { string FN; if (openFileDialog1.ShowDialog() == DialogResult.OK) { openFileDialog1.InitialDirectory = "G:\temp"; openFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; FN = openFileDialog1.FileName; Reader My = new Reader(FN); My.ReadTable(out tablesIntervalSuperiority, out row1, out col1); alfa = Convert.ToDouble(comboBox1.Text); IntervalSuperiority(row1); for (int i = 0; i < row1; i++) { for (int j = 0; j < col1; j++) { dataGridView6.Rows[i].Cells[j].Value = tablesIntervalSuperiority[i, j]; } } } } //сохранение таблицы критериев важности private void button10_Click(object sender, EventArgs e) { string FN; saveFileDialog1.InitialDirectory = "G:\temp"; saveFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; if (saveFileDialog1.ShowDialog() == DialogResult.OK) { FN = saveFileDialog1.FileName; Writer.WriteTable(FN, tablesCriterionImportance); } } // сохранение таблицы интервалов превосходства private void button12_Click(object sender, EventArgs e) { string FN; saveFileDialog1.InitialDirectory = "G:\temp"; saveFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; if (saveFileDialog1.ShowDialog() == DialogResult.OK) { FN = saveFileDialog1.FileName; Writer.WriteTable(FN, tablesIntervalSuperiority); } } // сохранение матрицы индексов согласия private void button13_Click(object sender, EventArgs e) { string FN; saveFileDialog1.InitialDirectory = "G:\temp"; saveFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; if (saveFileDialog1.ShowDialog() == DialogResult.OK) { FN = saveFileDialog1.FileName; Writer.WriteTable(FN, TableOfAgreementIndex); } } //сохранение матрицы индексов несогласия private void button14_Click(object sender, EventArgs e) { string FN; saveFileDialog1.InitialDirectory = "G:\temp"; saveFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; if (saveFileDialog1.ShowDialog() == DialogResult.OK) { FN = saveFileDialog1.FileName; Writer.WriteTable(FN, TableOfDisagreementIndex); } } //сохранение ядра private void button15_Click(object sender, EventArgs e) { string FN; saveFileDialog1.InitialDirectory = "G:\temp"; saveFileDialog1.Filter = "diag files(*.diag)|*.abs|All files|*.*"; if (saveFileDialog1.ShowDialog() == DialogResult.OK) { FN = saveFileDialog1.FileName; Writer.WriteTableOfRule(FN, TableofDecisiveRule); } } } class Reader { private string fileName; private string[] inputTxt; private double[,] matrix; private int row; private int col; private System.Globalization.NumberFormatInfo numberFormat; public Reader(string Name) { fileName = Name; } public void ReadTable(out double[,] table, out int rows, out int cols) { numberFormat = new System.Globalization.NumberFormatInfo(); numberFormat.CurrencyDecimalSeparator = "."; string[] output = File.ReadAllLines(fileName); string[] aloneString = output[0].Split(new char[] { ' ' }); //double[,] temp = new double[output.Length, aloneString.Length]; table = new double[output.Length, aloneString.Length]; rows = output.Length; cols = aloneString.Length; for (int i = 0; i < aloneString.Length; i++) { table[0, i] = double.Parse(aloneString[i], numberFormat); } for (int i = 1; i < output.Length; i++) { aloneString = output[i].Split(new char[] { ' ' }); for (int j = 0; j < aloneString.Length; j++) { table[i, j] = double.Parse(aloneString[j], numberFormat); } } } } class Writer { private static string fileName; private static string[] outputTxt; private static double[,] matrix; private static string[,] matrix1; private static int row; private static int col; private static System.Globalization.NumberFormatInfo numberFormat; public static void WriteTable(string nameFile, double[,] table) { Writer.fileName = nameFile; Writer.matrix = table; if (Writer.matrix != null) { row = matrix.GetLength(0); col = matrix.GetLength(1); outputTxt = new string[row]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { outputTxt[i] += matrix[i, j].ToString(); if(j != (col - 1)) outputTxt[i] += " "; } } File.WriteAllLines(nameFile, outputTxt); } } public static void WriteTableOfRule(string nameFile, string[,] table) { Writer.fileName = nameFile; Writer.matrix1 = table; if (Writer.matrix1 != null) { row = matrix1.GetLength(0); col = matrix1.GetLength(1); outputTxt = new string[row]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { outputTxt[i] += matrix1[i, j]; if (j != (col - 1)) outputTxt[i] += " "; } } File.WriteAllLines(nameFile, outputTxt); } } } 4. Пример работы программы 4.1 Многокритериальная задача1) Реализуем пример. Для этого воспользуемся уже заготовленными файлами с входными данными: Рис Найдем матрицу согласия: Рис Найдем матрицу индексов несогласия: Рис Найдем ядро бинарного отношения: Рис Выводы В результате проделанной работы было разработано программное средство для поиска альтернативных вариантов решений для многокритериальных задач. Данное приложение может использоваться лишь как демонстрационно-обучающее по теме «Многокритериальные задачи. Метод альтернативных решений» дисциплины «Теория принятия решений». Используемая литература 1. А.В Лотов, И.И. Поспелова Многокритериальные задачи принятия решения Учебное пособие.– М. : МАКС Пресс, 2008. – 197 с. Используемые программные средстваMicrosoft Visual Studio 2008 |
НОВОСТИ |
ВХОД |
|
Рефераты бесплатно, реферат бесплатно, курсовые работы, реферат, доклады, рефераты, рефераты скачать, рефераты на тему, сочинения, курсовые, дипломы, научные работы и многое другое. |
||
При использовании материалов - ссылка на сайт обязательна. |