Реализация

Для решения задачи методом уступок, пользователю необходимо сформировать начальные значения. При нажатии элемента главного меню «Новая задача» формируется поле ввода начальных значений: количество целевых функций, количество ограничений, количество переменных. Программа формирует поля для ввода коэффициентов целевой функции и ограничений. После ввода коэффициентов и нажатия кнопки «ОК», программа сформирует данные на главной форме. При нажатии второго элемента главного меню «Решить задачу» программа предложит выбрать наиболее значимый критерий и коэффициент уступки. В результате будет получено решение задачи по первому выбранному критерию и сформировано дополнительное ограничение для следующего критерия по значимости. Программа заканчивает свою работу, когда будет выбран последний критерий. Результатом будет диалоговое окно о полученном решении или сообщение о невозможности решения. Каждый этап работы программы отображается в нижнем меню главной формы программы. Пункт меню «Новая задача» позволяет сбросить условия текущей задачи для ввода новой. Пункт “О программе” выводит информацию о программе, авторе и руководителе курсового проекта.

Код программы:

См. Приложение 1.

Пример работы:

Решить задачу методом последовательных уступок:

1. Нажимаем элемент главного меню «Новая задача» и вводим количество целевых функций, ограничений и переменных

Рисунок 1. Создание новой задачи

2. Вводим коэффициенты целевых функций и ограничений

Рисунок 2. Ввод коэффициентов новой задачи

3. Формируем задачу

Рисунок 3. Сформированная задача

4. Нажимаем элемент главного меню «Решить задачу» и делаем уступку по выбранному критерию:

Рисунок 4. Выбор наиболее важного критерия и коэффициента уступки

5. Решаем задачу по второму критерию с дополнительным ограничением:

Рисунок 5. Выбор второго по важности критерия

6. Получаем подтверждение решения

Рисунок 6. Вывод результата

Список литературы

1. Вентцель Е.С. «Исследование операций», Высшая школа, 2001 г.

2. Таха Х. «Введение в исследование операций», Вильямс, 2005 г.

3. Сакович В.А. «Исследование операций», Высшая школа, 1984 г.

4. Комплект электронных учебно-методических материалов НГТУ на тему «Метод уступок», http://edu.nstu.ru/courses/mo_tpr/files/5.5.html

5. Шикин Е.В., Шикина Г.Е. «Исследование операций», Проспект, 2006 г.

Приложение

Приложение 1

Код программы:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace WindowsFormsApplication1

{

public partial class Main: Form

{

public Main()

{

InitializeComponent();

this.StartPosition = FormStartPosition.CenterScreen;

Data.check = 0;

}

private void новаяЗадачаToolStripMenuItem_Click(object sender, EventArgs e)

{

if (Data.check!= 0)

{ Controls.Remove(Data.pan); }

Data.check++;

Panel pan = new Panel();

pan.Location = new Point(0,24);

pan.Height = this.Height - 24 - log.Height;

pan.Width = this.Width;

Data.pan = pan;

Controls.Add(pan);

log.Text = "";

log.AppendText("Создание новой задачи...\r \n");

Data.Ind = true;

NewData fr2 = new NewData();

fr2.StartPosition = FormStartPosition.CenterScreen;

fr2.ShowDialog();

Data.V = new Double[Data.n];

log.AppendText("Количество ЦФ - " + Data.n + "\r \n");

log.AppendText("Количество ограничей - " + Data.m + "\r \n");

log.AppendText("Количество переменных - " + Data.p + "\r \n");

EnterData fr3 = new EnterData();

fr3.StartPosition = FormStartPosition.CenterScreen;

fr3.ShowDialog();

if (Data.closed == false)

{

log.AppendText("Формирование задачи...\r \n");

Vivod();

решитьЗадачуToolStripMenuItem.Enabled = true;

}

else { log.Text = ""; }

}

private void решитьЗадачуToolStripMenuItem_Click(object sender, EventArgs e)

{

int k;

Data.V = new Double[Data.n];

int test = 0;

log.AppendText("Решение задачи...\r \n");

for (int it = 0; it <= Data.n - 1; it++)

{

test++;

Data.test = test;

Transfer fr4 = new Transfer();

fr4.StartPosition = FormStartPosition.CenterScreen;

fr4.ShowDialog();

k = Data.krit;

Presimplex(k);

minG(k);

if (Data.valid == 1)

{ solutionF(k); }

else

{

log.AppendText("Завершено\r \n");

MessageBox.Show("Решение задачи невозможно");

решитьЗадачуToolStripMenuItem.Enabled = false;

return;

}

if (Data.valid == 0)

{

log.AppendText("Завершено\r \n");

MessageBox.Show("Решение задачи невозможно");

решитьЗадачуToolStripMenuItem.Enabled = false;

return;

}

for (int j = 1; j <= Data.p + Data.m; j++)

{

for (int i = 0; i <= Data.m - 1; i++)

{

if (Data.des[k, i] == j) { Data.per[k, j-1] = Data.f[i]; }

}

}

Data.V[k] = Data.F[Data.m + Data.p];

if ((Data.V[k]==Double.NaN)||(Data.V[k]==Double.PositiveInfinity)||(Data.V[k]==Double.NegativeInfinity))

{

log.AppendText("Завершено\r \n");

MessageBox.Show("Решение задачи невозможно");

решитьЗадачуToolStripMenuItem.Enabled = false;

return;

}

log.AppendText("Решение задачи по " + (k + 1) + " критерию завершено: F" + (k + 1) + "= " + Edit(Data.V[k]) + "\r \n");

for (int j = 0; j <= Data.p - 1; j++)

{

if ((Data.per[k, j] < 0.001) && (Data.per[k, j] > -0.001))

{ Data.per[k, j] = 0; }

log.AppendText("X"+(j+1) + "= " + Edit(Data.per[k, j]) + " ");

}

log.AppendText("\r\n");

if (test!= Data.n)

{

Data.V[k] = ((Math.Round(Data.V[k] * 100)) * (100 - Data.ku)) / 10000;

log.AppendText("Решением задачи после уступки на " + Data.ku + "% " + "будет F" + (k + 1) + "= " + Edit(Data.V[k]) + "\r \n");

//Формирование нового ограничения

Data.m++;

int n = Data.n;

int m = Data.m;

int p = Data.p;

string s;

string f;

for (int j = 0; j <= p - 1; j++)

{

Data.g[m - 1, j] = Data.o[k, j];

}

s = "";

if (Data.mm[k] == 1)

{

Data.zn[m - 1] = -1;

s = "≥";

}

if (Data.mm[k] == 0)

{

Data.zn[m - 1] = 1;

s = "≤";

}

Data.f[m - 1] = Data.V[k];

Data.f1[m - 1] = Data.V[k];

if (Data.V[k] == 0) { Data.V[k] = 0.0001; }

f = Convert.ToString(Data.f[m - 1]);

//Вывод нового ограничения

GroupBox of = new GroupBox();

of.Location = new Point(15, n * 25 + 80 + 25 * (m - 1));

of.TabIndex = (m - 1);

of.FlatStyle = FlatStyle.Flat;

of.Width = 70 + 70 * p;

of.Height = 30;

Label label = new Label();

label.Font = new Font("Times New Roman", 10);

label.TextAlign = ContentAlignment.MiddleCenter;

label.AutoSize = false;

label.Location = new Point(15, 85 + 25 * (m - 1));

label.Height = 20;

label.Width = 40 + 70 * p;

for (int j = 0; j <= p - 1; j++)

{

if (j!= (p - 1))

{ label.Text = label.Text + (Data.g[(m - 1), j]).ToString() + " " + "X" + (j + 1).ToString() + "+ "; }

else

{ label.Text = label.Text + (Data.g[(m - 1), j]).ToString() + " " + "X" + (j + 1).ToString() + " " + s + " " + f; }

}

label.Location = new Point((of.Width / 2) - (label.Width / 2), 8);

of.Controls.Add(label);

Data.pan.Controls.Add(of);

log.AppendText("Вводим в задачу дополнительное ограничение: \r\n" + label.Text + "\r\n");

// Определение размеров формы

this.Height = 80 + 180 + 30 * (n + m + 1);

this.Width = 300 + 60 * p;

Data.pan.Height = this.Height - 24 - log.Height;

log.Location = new Point(0, 80 + 30 * (n + m + 1));

log.Width = 290 + 60 * p;

log.Height = 150;

}

if (test == Data.n)

{

MessageBox.Show("Решение получено");

}

}

log.AppendText("Завершено\r \n");

решитьЗадачуToolStripMenuItem.Enabled = false;

}

private void выходToolStripMenuItem_Click(object sender, EventArgs e)

{

this.Close();

}

public void console()

{

log.Enabled = true;

int n = Data.n; int m = Data.m; int p = Data.p;

log.AppendText(" " + "\n");

for (int i = 0; i <= m - 1; i++)

{

for (int j = 0; j <= Data.d - 1; j++)

{

log.AppendText(Data.sim[i, j] + " ");

}

log.AppendText(Data.f[i] + "\n");

}

log.AppendText("\n");

if (Data.level == 1)

{

//Прописываем Q

for (int j = 0; j <= Data.d; j++)

{

log.AppendText(Data.Q[j] + " ");

}

log.AppendText("\n");

//Прописываем G

for (int j = 0; j <= Data.d; j++)

{

log.AppendText(Data.G[j] + " ");

}

log.AppendText("\n");

}

if (Data.level == 2)

{

//Прописываем F

for (int j = 0; j <= Data.d; j++)

{

log.AppendText(Data.F[j] + " ");

}

log.AppendText("\n");

}

}

public void Presimplex(int k)

{

//Реализация симплекс метода

//Шаг 0. Определение переменных и массивов

int n = Data.n;

int m = Data.m;

int p = Data.p;

Data.level = 1;

Data.s = new Double[m, m];

Data.r = new Double[m, m];

Data.b = new int[m];

Data.des = new int[n,m];

Data.per = new Double[n, p + m];

Data.G = new Double[m + m + p + 1];

Data.Q = new Double[m + m + p + 1];

Data.sim = new Double[m, m + m + p];

Data.d = m + m + p;

int d = Data.d;

// Шаг 1. Проверка правой части

for (int i = 0; i <= m - 1; i++)

{

Data.f[i] = Data.f1[i];

if (Data.f[i] == 0)

{ Data.f[i] = 0.001; }

if (Data.f[i] < 0)

{

Data.f[i] = Data.f[i] * (-1);

Data.zn[i] = Data.zn[i] * (-1);

for (int j = 0; j <= p - 1; j++)

{

Data.g[i, j] = Data.g[i, j] * (-1);

}

}

}

//Шаг 2. Избавляемся от неравенств

for (int i = 0; i <= m - 1; i++)

{

if (Data.zn[i] == 1)

{ Data.s[i,i] = 1; }

if (Data.zn[i] == -1)

{ Data.s[i,i] = -1; }

}

//Шаг 3. Поиск базовых переменных

for (int i = 0; i <= m - 1; i++)

{

if (Data.zn[i] == 0)

{ Data.r[i, i] = 1; }

if ((Data.zn[i] == -1)&&(Data.s[i, i] == -1))

{ Data.r[i, i] = 1; }

}

//Шаг 4. Формируем вспомогательную ЦФ и ЦФ

//Формирование симплекс-таблицы

for (int i = 0; i <= m - 1; i++)

{

for (int j = 0; j <= m + m + p - 1; j++)

{

if (j <= p - 1)

{ Data.sim[i, j] = Data.g[i, j]; }

if ((j > p - 1) && (j <= p + m - 1))

{ Data.sim[i, j] = Data.s[i, j-p]; }

if ((j > p + m - 1) && (j <= p + m + m -1))

{ Data.sim[i, j] = Data.r[i, j - p - m]; }

}

}

for (int i = 0; i <= m - 1; i++)

{

for (int j = 0; j <= m + m + p; j++)

{

if (j <= p - 1)

{ Data.G[j] = Data.G[j] + Data.sim[i, j] * Data.r[i,i]; }

if ((j > p - 1) && (j <= p + m - 1)&&(j-p==i))

{ Data.G[j] = Data.G[j] + Data.sim[i, i+p] * Data.r[i, i]; }

if (j == m + m + p)

{ Data.G[j] = Data.G[j] + Data.f[i] * Data.r[i, i]; }

}

}

for (int j = 0; j <= p-1; j++)

{

{ Data.Q[j] = Data.Q[j] - Data.o[k,j]; }

}

//console();

}

public void minG(int k)

{

int n = Data.n;

int m = Data.m;

int p = Data.p;

Data.d = m + m + p;

int d = Data.d;

for (int it = 0; it <= 50; it++)

{

int test = 0;

for (int j = 0; j <= d - 1; j++)

{

if ((Data.G[j] < 0.0001) && (Data.G[j] > -0.0001))

{ Data.G[j] = 0; }

if (Data.G[j] > 0) { test++; }

}

if ((Data.G[d] < 0.0001) && (Data.G[d] > -0.0001))

{ Data.G[d] = 0; }

if ((test == 0)&&(Data.G[d]!=0)) { Data.valid = 0; return; }

if (test == 0) { Data.valid = 1; return; }

//Шаг 5. Минимизация вспомогательной функции

//Ведущий столбец

int Vcol = 0; double temp = -1000;

for (int j = 0; j <= d - 1; j++)

{

if (Data.G[j] > temp)

{ temp = Data.G[j]; Vcol = j; }

}

//Ведущая строка

temp = 1000; int Vstr = 0;

double otn = -1000;

for (int i = 0; i <= m - 1; i++)

{

otn = ((Data.f[i]) / (Data.sim[i, Vcol]));

if ((otn < temp) && (otn >= 0))

{ temp = otn; Vstr = i; }

}

Data.des[k,Vstr] = Vcol+1;

//Новая ведущаю строка

double vk = Data.sim[Vstr, Vcol];

for (int j = 0; j <= d; j++)

{

if (j!= d)

Data.sim[Vstr, j] = Data.sim[Vstr, j] / vk;

else

Data.f[Vstr] = Data.f[Vstr] / vk;

}

//Новые строки

for (int i = 0; i <= m - 1; i++)

{

double Simcol = Data.sim[i, Vcol];

for (int j = 0; j <= d; j++)

{

if ((i!= Vstr) && (j <= d - 1))

{ Data.sim[i, j] = Data.sim[i, j] - Simcol * Data.sim[Vstr, j]; }

if ((i!= Vstr) && (j == d))

{ Data.f[i] = Data.f[i] - Simcol * Data.f[Vstr]; }

}

}

double Gcol = Data.G[Vcol];

double Qcol = Data.Q[Vcol];

for (int j = 0; j <= d; j++)

{

if (j <= d - 1)

{

Data.G[j] = Data.G[j] - Gcol * Data.sim[Vstr, j];

Data.Q[j] = Data.Q[j] - Qcol * Data.sim[Vstr, j];

}

if (j == m + m + p)

{

Data.G[j] = Data.G[j] - Gcol * Data.f[Vstr];

Data.Q[j] = Data.Q[j] - Qcol * Data.f[Vstr];

}

}

Data.valid = 0;

//console();

}

}

public void solutionF(int k)

{

int n = Data.n;

int m = Data.m;

int p = Data.p;

Data.d = m + p;

int d = Data.d;

Data.F = new Double[m + p + 1];

Data.level = 2;

//Формирование симплекс-таблицы

for (int j = 0; j <= d; j++)

{

if (j!= d)

{ Data.F[j] = Data.Q[j]; }

else

{ Data.F[j] = Data.Q[m + d]; }

}

for (int it = 0; it <= 50; it++)

{

if (Data.mm[k] == 0) //Min

{

int test = 0;

for (int j = 0; j <= d - 1; j++)

{

if ((Data.F[j] < 0.0001) && (Data.F[j] > -0.0001))

{ Data.F[j] = 0; }

if (Data.F[j] > 0) { test++; }

}

if (test == 0) { Data.valid = 1; return; }

}

if (Data.mm[k] == 1) //Max

{

int test = 0;

for (int j = 0; j <= d - 1; j++)

{

if ((Data.F[j] < 0.0001) && (Data.F[j] > -0.0001))

{ Data.F[j] = 0; }

if (Data.F[j] < 0) { test++; }

}

if (test == 0) { Data.valid = 1; return; }

}

//Шаг 5. Минимизация/Максимизация ЦФ

int Vcol = 0; double temp = 0;

if (Data.mm[k] == 0) //Min

{

//Ведущий столбец

for (int j = 0; j <= d - 1; j++)

{

if (Data.F[j] >= temp)

{ temp = Data.F[j]; Vcol = j; }

}

}

else //Max

{

//Ведущий столбец

temp = 1000;

for (int j = 0; j <= d - 1; j++)

{

if (Data.F[j] <= temp)

{ temp = Data.F[j]; Vcol = j; }

}

}

//Ведущая строка

temp = 1000; int Vstr = 0;

double otn = -1000;

for (int i = 0; i <= m - 1; i++)

{

otn = ((Data.f[i]) / (Data.sim[i, Vcol]));

if ((otn <= temp) && (otn >= 0))

{ temp = otn; Vstr = i; }

}

Data.des[k,Vstr] = Vcol+1;

//Новая ведущаю строка

double vk = Data.sim[Vstr, Vcol];

for (int j = 0; j <= d; j++)

{

if (j!= d)

Data.sim[Vstr, j] = Data.sim[Vstr, j] / vk;

else

Data.f[Vstr] = Data.f[Vstr] / vk;

}

//Новые строки

for (int i = 0; i <= m - 1; i++)

{

double Simcol = Data.sim[i, Vcol];

for (int j = 0; j <= d; j++)

{

if ((i!= Vstr) && (j <= d - 1))

{ Data.sim[i, j] = Data.sim[i, j] - Simcol * Data.sim[Vstr, j]; }

if ((i!= Vstr) && (j == d))

{ Data.f[i] = Data.f[i] - Simcol * Data.f[Vstr]; }

}

}

double Fcol = Data.F[Vcol];

for (int j = 0; j <= d; j++)

{

if (j <= d - 1)

{

Data.F[j] = Data.F[j] - Fcol * Data.sim[Vstr, j];

}

if (j == d)

{

Data.F[j] = Data.F[j] - Fcol * Data.f[Vstr];

}

}

Data.valid = 0;

//console();

}

}

private double Edit(double n)

{

return ((Math.Round(n * 100)) / 100);

}

public void Vivod()

{

int n = Data.n;

int m = Data.m;

int p = Data.p;

// Определение размеров формы

this.Height = 80 + 180 + 30 * (n+m + 1);

this.Width = 300 + 60 * p;

log.Location = new Point(0, 80 + 30 * (n+m + 1));

log.Width = 290 + 60 * p;

log.Height = 150;

Data.pan.Height = this.Height - 24 - log.Height;

Data.pan.Width = this.Width;

//Вывод на главную форму ЦФ и огр.

Label title1 = new Label();

title1.Location = new Point(20, 40);

title1.Font = new Font("Times New Roman", 12);

title1.Width = 330;

title1.Height = 20;

title1.Text = "Целевые функции:";

Data.pan.Controls.Add(title1);

for (int i = 0; i <= n - 1; i++)

{

GroupBox of = new GroupBox();

of.Location = new Point(15, 55 + 25 * i);

of.TabIndex = i;

of.FlatStyle = FlatStyle.Flat;

of.Width = 70+70 * p;

of.Height = 30;

Label label = new Label();

label.Font = new Font("Times New Roman", 10);

label.TextAlign = ContentAlignment.MiddleCenter;

label.AutoSize = false;

label.Location = new Point(15, 55 + 25 * i);

label.Height = 20;

label.Width = 40+70*p;

label.Text = "F" + (i + 1) + " = ";

for (int j = 0; j <= p - 1; j++)

{

if (j!= (p-1))

{ label.Text = label.Text + (Data.o[i, j]).ToString() + " " + "X" + (j + 1).ToString() + "+ "; }

else

{ label.Text = label.Text + (Data.o[i, j]).ToString() + " " + "X" + (j + 1).ToString() + " —> " + Data.ofmm[i].Text; }

}

label.Location = new Point((of.Width / 2) - (label.Width / 2), 8);

of.Controls.Add(label);

Data.pan.Controls.Add(of);

}

Label title2 = new Label();

title2.Location = new Point(20, n * 25+65);

title2.Font = new Font("Times New Roman", 12);

title2.Width = 330;

title2.Height = 20;

title2.Text = "Ограничения:";

Data.pan.Controls.Add(title2);

for (int i = 0; i <= m - 1; i++)

{

GroupBox of = new GroupBox();

of.Location = new Point(15, n*25+80 + 25 * i);

of.TabIndex = i;

of.FlatStyle = FlatStyle.Flat;

of.Width = 70 + 70 * p;

of.Height = 30;

Label label = new Label();

label.Font = new Font("Times New Roman", 10);

label.TextAlign = ContentAlignment.MiddleCenter;

label.AutoSize = false;

label.Location = new Point(15, 55 + 25 * i);

label.Height = 20;

label.Width = 40 + 70 * p;

for (int j = 0; j <= p - 1; j++)

{

if (j!= (p - 1))

{ label.Text = label.Text + (Data.g[i, j]).ToString() + " " + "X" + (j + 1).ToString() + "+ "; }

else

{ label.Text = label.Text + (Data.g[i, j]).ToString() + " " + "X" + (j + 1).ToString() + " " + Data.limzn[i].Text + " " + Data.limequ[i].Text; }

}

label.Location = new Point((of.Width / 2) - (label.Width / 2), 8);

of.Controls.Add(label);

Data.pan.Controls.Add(of);

}

}

private void оПрограммеToolStripMenuItem_Click(object sender, EventArgs e)

{

MessageBox.Show("Курсовая работа 'Метод уступок'\r\nАвтор: Корнев Н.С.\r\nГруппа: C-8327\r\nРуководитель КП: Брязига С.П.");

}

}

}