Реалізація програми, що здатна розв"язувати симплекс-методом задачі лінійного програмування (ЗЛП)

Міністерство освіти і науки, молоді та спорту України Житомирський державний технологічний університет Кафедра ПЗОТ Звіт з курсової роботи на тему:

Реалізація програми що здатна розв’язувати симплекс-методом задачі лінійного програмування (ЗЛП) Житомир 2013

Тема: Реалізація програми, що здатна розв’язувати симплекс-методом задачі лінійного програмування (ЗЛП)

Хід роботи:

Теоретичні відомості

Якщо лінійна оптимізаційна задача містить три змінні, то графічний метод розв’язання стає неефективним, а при більшому числі змінних — взагалі неможливим. У цьому випадку необхідно застосувати алгебраїчний апарат. Універсальним алгебраїчним методом розв’язання задач лінійного програмування є так званий симплексний метод, запропонований у 1943 році американським вченим Дж. Данцигом.

Ідея цього методу полягає в здійсненні спрямованого перебору допустимих планів у такий спосіб, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який за значенням цільової функції був би хоча б не гіршим за попередній. Значення функціонала при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум).

Процес розв’язання задачі симплекс-методом має ітераційний характер: однотипні обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.

Отже, симплекс-метод — це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування.

Керівництво користувача

Інтерфейс програми має вигляд (Мал. 1)

Користувачу пропонується ввести кількість змінних та обмежень. Після цього користувач повинен ввести умову та натиснути на кнопку «Расчёт». (Мал. 2)

Мал. 1

Мал. 2

Керівництво програміста Даний програмний засіб реалізований на мові програмування С#.

симплекс ітераційний лінійний задача Лістинг основних фрагментів коду програми:

Функції програми, що виконують приведення до зручного вигляду для розв’язання ЗЛП:

public class Canonical

{

public static Simplex begin (Simplex obj)//приводим до канонического вида

{

if (!obj.Minimaze)//минимизируем функцию цели

{

for (int i = 1; i < obj. Variable — 1; i++)

obj.simplex_table[obj.Restrictions — 1, i] =

obj.simplex_table[obj.Restrictions — 1, i] * -1;

obj.isCanonical = true;

}

for (int i = 1; i < obj. Restrictions — 2; i++)//проверяем или все свободные члены больше 0

{

if (obj.simplex_table[i, obj. Variable — 2] < 0)

for (int j = 1; j < obj. Variable — 1; j++)

obj.simplex_table[i, j] = obj. simplex_table[i, j] * -1;

}

for (int i = 0; i < obj. Restrictions — 3; i++)//из неровностей делаем

уравнения

{

if (Simplex.znak[i] == «<=»)

{

Simplex.znak[i] = «=»;

double[,] mas = obj. simplex_table;

obj.Variable++;

obj.simplex_table = new double[obj.Restrictions, obj. Variable];

for (int j = 0; j < obj. Restrictions; j++)

for (int k = 0; k < obj. Variable — 3; k++)

obj.simplex_table[j, k] = mas[j, k];

for (int z = 1; z < obj. Restrictions — 2; z++)

obj.simplex_table[z, obj. Variable — 3] = 0;

obj.simplex_table[i + 1, obj. Variable — 3] = 1;

obj.simplex_table[0, obj. Variable — 3] = obj. simplex_table[0, obj. Variable — 4] + 1;

for (int j = obj. Variable — 2; j < obj. Variable; j++)

for (int k = 0; k < obj. Restrictions; k++)

obj.simplex_table[k, j] = mas[k, j — 1];

obj.isCanonical = true;

}

}

for (int i = 0; i < obj. Restrictions — 3; i++)

{

if (Simplex.znak[i] == «>=»)

{

Simplex.znak[i] = «=»;

double[,] mas = obj. simplex_table;

obj.Variable+=2;

obj.simplex_table = new double[obj.Restrictions, obj. Variable];

for (int j = 0; j < obj. Restrictions; j++)

for (int k = 0; k < obj. Variable — 3; k++)

obj.simplex_table[j, k] = mas[j, k];

for (int z = 1; z < obj. Restrictions — 2; z++)

obj.simplex_table[z, obj. Variable — 4] = 0;

obj.simplex_table[i + 1, obj. Variable — 4] = -1;

obj.simplex_table[0, obj. Variable — 4] = obj. simplex_table[0, obj. Variable — 5] + 1;

for (int z = 1; z < obj. Restrictions — 2; z++)

obj.simplex_table[z, obj. Variable — 3] = 0;

obj.simplex_table[i + 1, obj. Variable — 3] = 1;

obj.simplex_table[0, obj. Variable — 3] = obj. simplex_table[0, obj. Variable — 4] + 1;

obj.simplex_table[obj.Restrictions — 1, obj. Variable — 3] = 1000;

for (int j = obj. Variable — 2; j < obj. Variable; j++)

for (int k = 0; k < obj. Restrictions; k++)

obj.simplex_table[k, j] = mas[k, j — 2];

obj.isCanonical = true;

}

}

for (int i = 1; i < obj. Restrictions — 2; i++)

{

for (int j = 1; j < obj. Variable — 2; j++)

{

if (obj.simplex_table[i, j] == 1)

{

for (int k = 1; k < obj. Restrictions — 2; k++)

{

if (obj.simplex_table[k, j] == 0 && k ≠ i)

obj.simplex_table[i, 0] = obj. simplex_table[0, j];

}

}

}

}

for (int i = 1; i < obj. Restrictions — 2; i++)

{

if (obj.simplex_table[i, 0] == 0)

{

double[,] mas = obj. simplex_table;

obj.Variable++;

obj.simplex_table = new double[obj.Restrictions, obj. Variable];

for (int j = 0; j < obj. Restrictions; j++)

for (int k = 0; k < obj. Variable — 3; k++)

obj.simplex_table[j, k] = mas[j, k];

for (int z = 1; z < obj. Restrictions — 2; z++)

obj.simplex_table[z, obj. Variable — 3] = 0;

obj.simplex_table[i, obj. Variable — 3] = 1;

obj.simplex_table[0, obj. Variable — 3] = obj. simplex_table[0, obj. Variable — 4] + 1;

obj.simplex_table[i, 0] = obj. simplex_table[0, obj. Variable — 3];

for (int j = obj. Variable — 2; j < obj. Variable; j++)

for (int k = 0; k < obj. Restrictions; k++)

obj.simplex_table[k, j] = mas[k, j — 1];

obj.isCanonical = true;

}

}

for (int i = 1; i < obj. Restrictions — 2; i++)

{

for (int j = 1; j < obj. Variable — 2; j++)

{

if (obj.simplex_table[i, 0] == obj. simplex_table[0, j]) obj. simplex_table[i, obj. Variable — 1] = obj. simplex_table[obj.Restrictions — 1, j];

}

}

return obj;

}

}

Функція безпосереднього розв’язання задачі симплекс методом:

public class Decision

{

private Simplex obj;

public static Simplex start (Simplex s)//получает стартовую таюлицу

{

s=count_target (s);

return s;

}

public static Simplex end (Simplex s, out string info)//получает конечную таблицу

{

string str = string. Empty;

while (str == string. Empty)

{

s = evaluation (s, out str);

}

info = str;

return s;

}

private static Simplex evaluation (Simplex obj, out string str) //метод, который занимается онсовными подсчётами

{

int count = 0;

int max_col=0, min_row=0;

for (int i = 1; i < obj. Variable — 1; i++)

{

if (obj.simplex_table[obj.Restrictions — 2, i] <= 0) count++;

}

if (count == obj. Variable — 2) { str = «end»; return obj; } //определяет или уже есть решение

else

{

double max = obj. simplex_table[obj.Restrictions — 2, 1];

max_col = 1;

for (int i = 2; i < obj. Variable — 1; i++)//определяет решающий столбик

{

if (max < obj. simplex_table[obj.Restrictions — 2, i])

{

max = obj. simplex_table[obj.Restrictions — 2, i];

max_col = i;

}

}

count = 0;

for (int i = 1; i < obj. Restrictions — 2; i++)

{

if (obj.simplex_table[i, max_col] > 0) count++;

}

if (count == 0) { str = «Функция не ограниченая снизу»; return obj; } //определяет или функция не ограниченая снизу

else

{

double min=0;

for (int i = 1; i < obj. Restrictions — 2; i++) //определяет решающую строку

if (obj.simplex_table[i, max_col] > 0)

{

min = obj. simplex_table[i, obj. Variable — 2] / obj. simplex_table[i, max_col];

min_row = i;

break;

}

for (int i = 1; i < obj. Restrictions — 2; i++)

{

if (min > obj. simplex_table[i, obj. Variable — 2] / obj. simplex_table[i, max_col] && obj. simplex_table[i, max_col]>0)

{

min = obj. simplex_table[i, obj. Variable — 2] / obj. simplex_table[i, max_col];

min_row = i;

}

}

obj.simplex_table[min_row, 0] = obj. simplex_table[0, max_col]; //вводит новую переменную в базис

double elem = obj. simplex_table[min_row, max_col]; //делим решающую строку на решающий елемент

for (int i = 1; i < obj. Variable — 1; i++)

obj.simplex_table[min_row, i] = obj. simplex_table[min_row, i] / elem;

for (int i = 1; i < obj. Restrictions — 2; i++) //при помощи метода Гаусса убираем с остальных уравнений новую базисную переменную

{

if (i ≠ min_row)

{

double perem = (obj.simplex_table[i, max_col] /

obj.simplex_table[min_row, max_col]) * -1;

for (int j = 1; j < obj. Variable — 1; j++)

obj.simplex_table[i, j] = obj. simplex_table[i, j] +

obj.simplex_table[min_row, j] * perem;

}

}

for (int i = 1; i < obj. Restrictions — 2; i++)//записываем значения коефициентов у функции цели определенным базисным переменным

{

for (int j = 1; j < obj. Variable — 2; j++)

{

if (obj.simplex_table[i, 0] == obj. simplex_table[0, j]) obj. simplex_table[i, obj. Variable — 1] = obj. simplex_table[obj.Restrictions — 1, j];

}

}

obj = count_target (obj);

str = string. Empty;

return obj;

}

}

}

private static Simplex count_target (Simplex obj)//выщитывает функцию цели

{

int j, i;

for (i = 1; i < obj. Variable-1; i++)

{

obj.simplex_table[obj.Restrictions — 2, i] = 0;

for (j = 1; j < obj. Restrictions-2; j++)

{

obj.simplex_table[obj.Restrictions-2,i] += obj. simplex_table[j, i] * obj. simplex_table[j, obj. Variable-1];

}

obj.simplex_table[obj.Restrictions — 2, i] =

obj.simplex_table[obj.Restrictions — 2, i] ;

obj.simplex_table[obj.Restrictions-1, i];

}

return obj;

}

public static string print (Simplex obj)//формирут из симплекс таблицы строку, которую можна вывести на екран

{

string str = «rnt» ;

for (int i = 1; i < obj. Variable — 2; i++) str += «x» + obj. simplex_table[0, i] + «t» ;

str += «СЧrn» ;

for (int i = 1; i < obj. Restrictions — 1; i++)

{

for (int j = 0; j < obj. Variable — 1; j++)

{

str +=string.Format («{0:0.##}», obj. simplex_table[i, j]) + «t» ;

}

str += «rn» ;

}

return str;

}

public static string reasult (Simplex obj)//выводит итоговый результат в виде строки, который можна вывести на екран

{

double[] mas=new double[obj.Variable-2];

for (int i = 1; i < obj. Restrictions — 2; i++)

mas[Convert.ToInt32(obj.simplex_table[i, 0])] = obj. simplex_table[i,

obj.Variable — 2];

string str = «Результат: x*(«;

for (int i = 1; i < mas. Length; i++)

str += mas[i] + «,» ;

str += «)rnf (x)=» + obj. simplex_table[obj.Restrictions — 2, obj. Variable — 2];

return str;

}

}

}

public class Simplex

{

public bool isCanonical = false;

public int begin;

private static bool minimaze;

public bool Minimaze

{

get { return minimaze;}

}

public static string[] znak;

private static int variable; //количество переменных

private static int restrictions;//количество ограничений

public double[,] simplex_table;//симплекс таблица

public Simplex (int variabl, int restriction)//конструктор класса

{

restrictions = restriction+3;

variable = variabl+3;

simplex_table = new double[restrictions, variable];

znak = new string[restrictions — 3];

begin = variabl;

}

public int Variable//свойство, которое позволяет получить количество переменных

{

get { return variable; }

set { variable = value; }

}

public int Restrictions//свойство, которое позволяет получить количество ограничений

{

get { return restrictions; }

set { restrictions = value; }

}

public void initialization (List str)//формирует симплекс таблицу

{

string[] target = split (str[0], 0);

for (int j = 1; j < variable — 1; j++) simplex_table[restrictions — 1, j] = Convert. ToDouble (target[j — 1]);

for (int i = 1; i < str. Count; i++)

{

string[] mas = split (str[i], i);

for (int j = 1; j < variable-1; j++)

{

if (mas[j — 1] ≠ null)

{

simplex_table[i, j] = Convert. ToDouble (mas[j — 1]);

}

}

}

for (int i = 1; i < variable — 2; i++) simplex_table[0, i] = i;

for (int i = 1; i < restrictions — 2; i++)

{

for (int j = 1; j

{

if (simplex_table[i, j] == 1)

{

for (int k = 1; k < restrictions — 2; k++)

{

if (simplex_table[k, j] == 0 && k ≠ i) simplex_table[i, 0] = simplex_table[0, j];

}

}

}

}

for (int i = 1; i < restrictions — 2; i++)

{

for (int j = 1; j < variable — 2; j++)

{

if (simplex_table[i, 0] == simplex_table[0, j]) simplex_table[i, variable — 1] = simplex_table[restrictions — 1, j];

}

}

}

private static string[] split (string str, int number) //расбиваем целое уравнение на елементы

{

string[] mas=new string[variable];

for (int i = 0; i < str. Length; i++)

{

if (str[i] == '<' && str[i + 1] == '=')

{

znak[number — 1] = «<=»;

continue;

}

if (str[i] == '>' && str[i + 1] == '=')

{

znak[number — 1] = «>=»;

continue;

}

if (str[i] == 'x')

{

mas[Convert.ToInt32(str.Substring (i+1,1))-1] = «1» ;

i++;

continue;

}

if (str[i] == '-' || str[i] == '+')

{

if (str[i + 1] == '>')

{

if (str[i + 3] == 'i') minimaze = true;

else minimaze = false;

break;

}

if (str[i + 1] ≠ 'x')

{

int k = i + 1;

string s=string.Empty;

while (str[k] ≠ 'x')

{

s += str[k];

k++;

}

if (str[i] == '-') mas[Convert.ToInt32(str.Substring (k + 1, 1)) — 1] = «-» +s;

else mas[Convert.ToInt32(str.Substring (k + 1, 1)) — 1] = s;

i = k+1;

}

else

{

if (str[i]=='-') mas[Convert.ToInt32(str.Substring (i + 2, 1)) — 1] = «-1» ;

else mas[Convert.ToInt32(str.Substring (i + 2, 1)) — 1] = «1» ;

i=i+2;

}

continue;

}

if (str[i]=='=')

{

int k = i + 1;

while (k < str. Length)

{

mas[variable-3] += str[k];

k++;

}

break;

}

if (Convert.ToInt32(str.Substring (i, 1)) >= 0 &&

Convert.ToInt32(str.Substring (i, 1)) <= 9)

{

int k = i;

while (str[k] ≠ 'x')

{

mas[0] += str[k];

k++;

}

i = k + 1;

continue;

}

}

return mas;

}

}

}