|
Необходимо разработать программное средство для поиска альтернативных решений для следующей задачи:
· многокритериальная задача
входные данные: количество критериев и решений; весовые значения, заданные напрямую, степень важности критериев, интервалы превосходства, цена перехода значения в соседний класс.
выходные данные: матрица согласия; матрица несогласия; ядро бинарного отношения.
программный альтернативный решение
многокритериальный
2. Краткие теоретические сведения
Пусть задан набор числовых функций  , определенных на множестве возможных решений X. В зависимости от содержания задачи выбора эти функции именуют критериями оптимальности, критериями эффективности или целевыми функциями.
Указанные выше числовые функции образуют векторный критерий  , который принимает значения в пространстве m-мерных векторов  . Это пространство называют критериальным пространством или пространством оценок, а всякое значение  именуют векторной оценкой возможного решения x. Все возможные векторные оценки образуют множество возможных оценок (возможных или допустимых векторов)
Как правило, между множествами возможных решений X и соответствующим множеством векторов Y можно установить взаимно однозначное соответствие, т.е. каждому возможному решению поставить в соответствие определенный возможный вектор, и обратно – каждому возможному вектору сопоставить определенное возможное решение. В таких случаях выбор во множестве решений с математической точки зрения равносилен выбору во множестве векторов и все определения и результаты можно формулировать как в терминах решений, так и в терминах векторов, причем при желании всегда можно без труда осуществить переход от одной формы изложения к другой.
Задачу выбора, которая включает множество допустимых решений X и векторный критерий f, обычно называют многокритериальной задачей или задачей многокритериальной оптимизации.
Необходимо отметить, что формирование математической модели принятия решений (т.е. построение множества X
и векторного критерия f
) нередко представляет собой сложный процесс, в котором тесно взаимодействуют специалисты двух сторон. А именно, представители конкретной области знаний, к которой относится исследуемая проблема, и специалисты по принятию решений (математики). С одной стороны, следует учесть все важнейшие черты и детали реальной задачи, а с другой, – построенная модель не должна оказаться чрезмерно сложной с тем, чтобы для ее исследования и решения можно было успешно применить разработанный к настоящему времени соответствующий математический аппарат. Именно поэтому этап построения математической модели в значительной степени зависит от опыта, интуиции и искусства исследователей обеих сторон. Его невозможно отождествить с простым формальным применением уже известных, хорошо описанных алгоритмов.
Здесь следует еще добавить, что любая задача выбора (в том числе и многокритериальная) тесно связана с конкретным ЛПР
(лицо, принимающее решение). Уже на стадии формирования математической модели при построении множества возможных решений и векторного критерия дело не обходится без советов, рекомендаций и указаний ЛПР, тем более что векторный критерий как раз и служит. Принятие решения при многих критериях для выражения целей ЛПР. При этом ясно, что построить модель в точности соответствующую всем реальным обстоятельствам невозможно. Модель всегда является упрощением действительности. Важно добиться, чтобы она содержала те черты и детали, которые в наибольшей степени влияют на окончательный выбор наилучшего решения.
Рассмотрим два произвольных возможных решения  и  . Для них имеет место один и только один из следующих трех случаев:
1) справедливо соотношение  (ЛПР первое решение предпочитает второму),
2) справедливо соотношение  (ЛПР второе решение предпочитает первому),
3) не выполняется ни соотношение , ни соотношение (ЛПР не может отдать предпочтение ни одному из указанных двух решений).
Заметим, что четвертый случай, когда оба участвующих здесь соотношения и выполняются, невозможен благодаря асимметричности отношения предпочтения 
В первом из указанных выше случаев, т.е. при выполнении соотношения , говорят, что решение доминирует решение .
Если же реализуется третий случай, то говорят, что решения и не сравнимы по отношению предпочтения.
Среда разработки: VisualStudio2008 Язык программирования: C#
При проектировании программного средства будем использовать объектно-ориентированный подход. Список классов с кратким описанием:
1) Program.cs– это главное окно, служит для ввода данных, запуска работы алгоритма поиска парето-оптимальных решений, содержит методы для решения поставленной задачи.
2) Reader.cs– методы для загрузки данных из файла
3) Writer.cs– методы для сохранения данных в файл
Шаг 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.
Примерработыпрограммы
1) Реализуем пример. Для этого воспользуемся уже заготовленными файлами с входными данными:
Рис
Найдем матрицу согласия:
Рис
Найдем матрицу индексов несогласия:
Рис
Найдем ядро бинарного отношения:
Рис
В результате проделанной работы было разработано программное средство для поиска альтернативных вариантов решений для многокритериальных задач.
Данное приложение может использоваться лишь как демонстрационно-обучающее по теме «Многокритериальные задачи. Метод альтернативных решений» дисциплины «Теория принятия решений».
1. А.В Лотов, И.И. Поспелова Многокритериальные задачи принятия решения Учебное пособие.– М. : МАКС Пресс, 2008. – 197 с.
MicrosoftVisualStudio2008
|