Реалізація програми, що здатна розв’язувати симплекс-методом задачі лінійного програмування (ЗЛП)
Міністерство
освіти і науки, молоді та спорту України
Житомирський
державний технологічний університет
Кафедра
ПЗОТ
Звіт
з курсової
роботи
на
тему:
Реалізація
програми що здатна розв’язувати симплекс-методом задачі лінійного програмування
(ЗЛП)
Житомир
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) //метод,
который
занимается
онсовными
подсчётами
{(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;
}
}
}