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
{
for (int j = 0; 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
{
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
{
for (int j = 0; 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
{
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
{
if (max
{
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
{
for (int j = 0; j
{
if (i == j)
{
TableOfAgreementIndex[i, j] = 0;
}
else
{
IPlus = 0;
IMinus = 0;
IZero = 0;
for(int k = 0; 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
{
for (int j = 0; j
{
if (i == j)
{
TableOfDisagreementIndex[i, j] = 0;
}
else
{
Interval = 0;
for (int k = 0; k
{
count[k, 0] = 0;
count[k, 1] = 0;
count1 = 0;
count2 = 0;
for (int m = 0; 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]
{
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
{
count = 0;
countOfq = 0;
countOfp = 0;
for (int j = 0; j
{
count += 1;
if (i != j)
{
if (Convert.ToInt32(dataGridView3.Rows[i].Cells[j].Value)
{
countOfq += 1;
if (Convert.ToInt32(dataGridView2.Rows[i].Cells[j].Value)
{
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
{
for (int j = 0; 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
{
for (int j = 0; 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
{
for (int j = 0; 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 intcols)
{
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
{
table[0, i] = double.Parse(aloneString[i], numberFormat);
}
for (int i = 1; i
{
aloneString = output[i].Split(new char[] { ' ' });
for (int j = 0; 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
{
for (int j = 0; 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
{
for (int j = 0; 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