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

 

Міністерство освіти і науки, молоді та спорту України

Житомирський державний технологічний університет

Кафедра ПЗОТ










Звіт з курсової роботи

на тему:

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













Житомир 2013


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


Хід роботи:

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

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

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

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

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

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

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

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


Мал. 1


Мал. 2


Керівництво програміста

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

симплекс ітераційний лінійний задача


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


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


public class Canonical

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

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

{(int i = 1; i < obj.Variable - 1; i++).simplex_table[obj.Restrictions - 1, i] =

obj.simplex_table[obj.Restrictions - 1, i] * -1;.isCanonical = true;

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

{(obj.simplex_table[i, obj.Variable - 2] < 0)(int j = 1; j < obj.Variable - 1; j++).simplex_table[i, j] = obj.simplex_table[i, j] * -1;

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

уравнения

{(Simplex.znak[i] == "<=")

{.znak[i] = "=";[,] mas = obj.simplex_table;.Variable++;.simplex_table = new double[obj.Restrictions, obj.Variable];(int j = 0; j < obj.Restrictions; j++)(int k = 0; k < obj.Variable - 3; k++).simplex_table[j, k] = mas[j, k];(int z = 1; z < obj.Restrictions - 2; z++).simplex_table[z, obj.Variable - 3] = 0;.simplex_table[i + 1, obj.Variable - 3] = 1;.simplex_table[0, obj.Variable - 3] = obj.simplex_table[0, obj.Variable - 4] + 1;(int j = obj.Variable - 2; j < obj.Variable; j++)(int k = 0; k < obj.Restrictions; k++).simplex_table[k, j] = mas[k, j - 1];.isCanonical = true;

}

}(int i = 0; i < obj.Restrictions - 3; i++)

{(Simplex.znak[i] == ">=")

{.znak[i] = "=";[,] mas = obj.simplex_table;.Variable+=2;.simplex_table = new double[obj.Restrictions, obj.Variable];(int j = 0; j < obj.Restrictions; j++)(int k = 0; k < obj.Variable - 3; k++).simplex_table[j, k] = mas[j, k];(int z = 1; z < obj.Restrictions - 2; z++).simplex_table[z, obj.Variable - 4] = 0;.simplex_table[i + 1, obj.Variable - 4] = -1;.simplex_table[0, obj.Variable - 4] = obj.simplex_table[0, obj.Variable - 5] + 1;(int z = 1; z < obj.Restrictions - 2; z++).simplex_table[z, obj.Variable - 3] = 0;.simplex_table[i + 1, obj.Variable - 3] = 1;.simplex_table[0, obj.Variable - 3] = obj.simplex_table[0, obj.Variable - 4] + 1;.simplex_table[obj.Restrictions - 1, obj.Variable - 3] = 1000;(int j = obj.Variable - 2; j < obj.Variable; j++)(int k = 0; k < obj.Restrictions; k++).simplex_table[k, j] = mas[k, j - 2];.isCanonical = true;

}

}(int i = 1; i < obj.Restrictions - 2; i++)

{(int j = 1; j < obj.Variable - 2; j++)

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

{(int k = 1; k < obj.Restrictions - 2; k++)

{(obj.simplex_table[k, j] == 0 && k != i).simplex_table[i, 0] = obj.simplex_table[0, j];

}

}

}

}(int i = 1; i < obj.Restrictions - 2; i++)

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

{[,] mas = obj.simplex_table;.Variable++;.simplex_table = new double[obj.Restrictions, obj.Variable];(int j = 0; j < obj.Restrictions; j++)(int k = 0; k < obj.Variable - 3; k++).simplex_table[j, k] = mas[j, k];(int z = 1; z < obj.Restrictions - 2; z++).simplex_table[z, obj.Variable - 3] = 0;.simplex_table[i, obj.Variable - 3] = 1;.simplex_table[0, obj.Variable - 3] = obj.simplex_table[0, obj.Variable - 4] + 1;.simplex_table[i, 0] = obj.simplex_table[0, obj.Variable - 3];(int j = obj.Variable - 2; j < obj.Variable; j++)(int k = 0; k < obj.Restrictions; k++).simplex_table[k, j] = mas[k, j - 1];.isCanonical = true;

}

}(int i = 1; i < obj.Restrictions - 2; i++)

{(int j = 1; j < obj.Variable - 2; j++)

{(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;

}

}

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

public class Decision

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

{=count_target(s);s;

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

{str = string.Empty;(str == string.Empty)

{= evaluation(s, out str);

}= str;s;

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

{count = 0;max_col=0, min_row=0;(int i = 1; i < obj.Variable - 1; i++)

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

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

{max = obj.simplex_table[obj.Restrictions - 2, 1];_col = 1;(int i = 2; i < obj.Variable - 1; i++)//определяет решающий столбик

{(max < obj.simplex_table[obj.Restrictions - 2, i])

{= obj.simplex_table[obj.Restrictions - 2, i];_col = i;

}

}= 0;(int i = 1; i < obj.Restrictions - 2; i++)

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

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

else

{min=0;(int i = 1; i < obj.Restrictions - 2; i++) //определяет решающую строку(obj.simplex_table[i, max_col] > 0)

{= obj.simplex_table[i, obj.Variable - 2] / obj.simplex_table[i, max_col];_row = i;;

}(int i = 1; i < obj.Restrictions - 2; i++)

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

{= obj.simplex_table[i, obj.Variable - 2] / obj.simplex_table[i, max_col];_row = i;

}

}.simplex_table[min_row, 0] = obj.simplex_table[0, max_col]; //вводит новую переменную в базисelem = obj.simplex_table[min_row, max_col];//делим решающую строку на решающий елемент(int i = 1; i < obj.Variable - 1; i++).simplex_table[min_row, i] = obj.simplex_table[min_row, i] / elem;

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

{(i != min_row)

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

obj.simplex_table[min_row, max_col]) * -1;(int j = 1; j < obj.Variable - 1; j++).simplex_table[i, j] = obj.simplex_table[i, j] +

obj.simplex_table[min_row, j] * perem;

}

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

{(int j = 1; j < obj.Variable - 2; j++)

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

}

}= count_target(obj);= string.Empty;obj;

}

}

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

{j,i;(i = 1; i < obj.Variable-1; i++)

{.simplex_table[obj.Restrictions - 2, i] = 0;(j = 1; j < obj.Restrictions-2; j++)

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

}.simplex_table[obj.Restrictions - 2, i] =

obj.simplex_table[obj.Restrictions - 2, i] -

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

}obj;

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

{str = "\r\n\t";(int i = 1; i < obj.Variable - 2; i++) str += "x" + obj.simplex_table[0, i] + "\t";+= "СЧ\r\n";(int i = 1; i < obj.Restrictions - 1; i++)

{(int j = 0; j < obj.Variable - 1; j++)

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

}+= "\r\n";

}str;

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

{[] mas=new double[obj.Variable-2];(int i = 1; i < obj.Restrictions - 2; i++)[Convert.ToInt32(obj.simplex_table[i, 0])] = obj.simplex_table[i, .Variable - 2];str = "Результат: x*(";(int i = 1; i < mas.Length; i++)+= mas[i] + ",";+= ")\r\nf(x)=" + obj.simplex_table[obj.Restrictions - 2, obj.Variable - 2];str;

}

}

}class Simplex

{bool isCanonical = false;int begin;static bool minimaze;bool Minimaze

{{ return minimaze;}

}static string[] znak;static int variable; //количество переменныхstatic int restrictions;//количество ограниченийdouble[,] simplex_table;//симплекс таблицаSimplex(int variabl,int restriction)//конструктор класса

{= restriction+3;= variabl+3;_table = new double[restrictions, variable];= new string[restrictions - 3];= variabl;

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

{{ return variable; }{ variable = value; }

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

{{ return restrictions; }{ restrictions = value; }

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

{[] target = split(str[0],0);(int j = 1; j < variable - 1; j++) simplex_table[restrictions - 1, j] = Convert.ToDouble(target[j - 1]);(int i = 1; i < str.Count; i++)

{[] mas = split(str[i],i);(int j = 1; j < variable-1; j++)

{(mas[j - 1] != null)

{_table[i, j] = Convert.ToDouble(mas[j - 1]);

}

}

}(int i = 1; i < variable - 2; i++) simplex_table[0, i] = i;(int i = 1; i < restrictions - 2; i++)

{(int j = 1; j <variable-2 ; j++)

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

{(int k = 1; k < restrictions - 2; k++)

{(simplex_table[k, j] == 0 && k != i) simplex_table[i, 0] = simplex_table[0, j];

}

}

}

}(int i = 1; i < restrictions - 2; i++)

{(int j = 1; j < variable - 2; j++)

{(simplex_table[i, 0] == simplex_table[0, j]) simplex_table[i, variable - 1] = simplex_table[restrictions - 1, j];

}

}

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

{[] mas=new string[variable];(int i = 0; i < str.Length; i++)

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

{[number - 1] = "<=";;

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

{[number - 1] = ">=";;

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

{[Convert.ToInt32(str.Substring(i+1,1))-1] = "1";++;;

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

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

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

}(str[i + 1] != 'x')

{k = i + 1;s=string.Empty;(str[k] != 'x')

{+= str[k];++;

}(str[i] == '-') mas[Convert.ToInt32(str.Substring(k + 1, 1)) - 1] = "-"+s;mas[Convert.ToInt32(str.Substring(k + 1, 1)) - 1] = s;= k+1;

}

{(str[i]=='-') mas[Convert.ToInt32(str.Substring(i + 2, 1)) - 1] = "-1";mas[Convert.ToInt32(str.Substring(i + 2, 1)) - 1] = "1";=i+2;

};

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

{k = i + 1;(k < str.Length)

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

};

}(Convert.ToInt32(str.Substring(i, 1)) >= 0 && .ToInt32(str.Substring(i, 1)) <= 9)

{k = i;(str[k] != 'x')

{[0] += str[k];++;

}= k + 1;;

}

}mas;

}

}

}


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

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ