Реалізація програми, що здатна розв’язувати симплекс-методом задачі лінійного програмування (ЗЛП)
Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | украинский |
| Дата добавления | 18.09.2013 |
| Размер файла | 359,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Міністерство освіти і науки, молоді та спорту України
Житомирський державний технологічний університет
Кафедра ПЗОТ
Звіт з курсової роботи
на тему:
Реалізація програми що здатна розв'язувати симплекс-методом задачі лінійного програмування (ЗЛП)
Житомир 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 = "\r\n\t";
for (int i = 1; i < obj.Variable - 2; i++) str += "x" + obj.simplex_table[0, i] + "\t";
str += "СЧ\r\n";
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 += "\r\n";
}
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 += ")\r\nf(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<string> 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 <variable-2 ; 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;
}
}
}
Размещено на Allbest.ru
Подобные документы
Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.
контрольная работа [385,2 K], добавлен 04.06.2009Використання мови програмуванння Java при виконанні "задачі лінійного програмування": її лексична структура і типи даних. Методи розв’язання задачі. Особливості логічної структури програми, побудова її зручного інтерфейсу за допомогою симплекс методу.
курсовая работа [437,9 K], добавлен 24.01.2011Лінійне програмування як один з найбільш популярних апаратів математичної теорії оптимального управління рішень. Опис існуючих методів розв’язку задач лінійного програмування. Завдання, основні принципи, алгоритми і головна мета лінійного програмування.
курсовая работа [363,8 K], добавлен 03.12.2009Основні визначення дослідження операцій. Модель "затрати-випуск" В.В. Леонтьєва. Загальний вигляд задачі лінійного програмування. Розв'язання за допомогою симплекс-методу. Економічна інтерпретація основної та спряженої задач. Поліпшення плану перевезень.
учебное пособие [1,1 M], добавлен 27.12.2010Розв’язок багатокритеріальної задачі лінійного програмування з отриманням компромісного рішення (для задач з кількома функціями мети) за допомогою теоретико-ігрового підходу. Матриця мір неоптимальності та рядок функції мети. Модуль опису класу.
курсовая работа [588,8 K], добавлен 15.05.2011Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.
лекция [479,7 K], добавлен 10.10.2013Загальні відомості та геометричний зміст розв'язання задачі Коші. Використання методу Ейлера для розв'язання звичайних диференціальних рівнянь першого порядку. Розробка блок-схеми та реалізація алгоритму в середовищі програмування Borland Delphi 7.0.
курсовая работа [398,1 K], добавлен 14.10.2012Загальний вид двовимірного завдання лінійного програмування. Алгоритм рішення задач графічним методом. Максимізація (мінімізація) цільової функції. Послідовність рішення завдань лінійного програмування симплексом-методом. Принцип перетворення Гауса.
контрольная работа [149,8 K], добавлен 24.11.2010Теоретичні основи та приклади економічних задач лінійного програмування. Розробка математичної моделі задачі (запис цільової функції і системи обмежень) і програмного забезпечення її вирішення за допомогою "Пошуку рішень" в Excel симплекс-методом.
курсовая работа [993,9 K], добавлен 10.12.2010Використання графічного методу і симплекс-методу при вирішенні задач лінейного програмування. Сутність двоякого симплекс-методу і М-методу, приклади використання. Аналіз методу динамичного програмування. Специфіка вирішення матричної, антагоністичної гри.
контрольная работа [1,1 M], добавлен 02.07.2011
