Курсовая работа

Ввод поддтверждается нажатием клавишиEnter. В конечном итоге возможны 2 варианта. Программа:

1.Выдастрешение «Текущее решение оптимально «-оптимальныйплан,» Значение целевой функции равно «- значениецелевойфункции.

2.Либо, если оно не существует, уведомит пользователя об этом «Не существует решения!"Заключение

В завершении проделанной работы подведём итоги. Во-первых, в ходе работы были рассмотрены различные постановки задач линейного программирования и симплекс-метод как универсальный и широко применяемый метод решения этих задач. Во-вторых, была построена математическая модель конкретной задачи. В-третьих, удалось достигнуть цели — реализовать построенную модель с помощью симплекс-метода.В-четвёртых, благодаря чёткому алгоритму симплекс-метода, на языке С++ была написана программа, реализующая этот алгоритм. Однако стоит отметить, что, несмотря на универсальность симплекс-метода у него есть явный недостаток: он является алгоритмом с экспоненциальной сложностью. Поэтому при решении задач большой размерности имеет смысл сравнить работу симплекс-метода с работой алгоритма с полиномиальной сложностью.

ЛИТЕРАТУРА

1.Акулич, И. Л. Математическое программирование в примерах и задачах / И. Л. Акулич. — М.: Высшая школа, 1986. -319 с.

2.Ашманов, С. А. Линейное программирование/С.А. Ашманов.

М.: Наука. Главная редакция физико-математической литературы, 1981.-340 с.

3.Банди, Б. Основы линейного программирования / Б. Банди; пер. с англ. -М.: Радио и связь, 1989. — 176 с.

4.Барсов, А. С. Что такое линейное программирование/А.С. Барсов.

М.: Государственное издательство физико-математической литературы, 1959. 104 с.

5.Березнев, В.А. О полиномиальной сложности одной модификации симплекс метода//Журнал вычислительной математики и математической физики.М., 2004, с.

12 441 260.URL:

http://www.mathnet.ru/links/6d1a17414de2d8a5cbfb7fb80fb085c8/zvmmf810.pdf (дата обращения 01.

03.2012)

6. Васильев, Ф. П. Линейное программирование / Ф. П. Васильев, А. Ю. Иваницкий.

М.:изд-во «Факториал Пресс», 2003.-352 с.

7.Вентцель, Е. С. Исследование операций/ Е. С. Вентцель. — М: Советское радио, 1972.-552 с.

8.Волков, И. К. Исследование операций/ И. К. Волков, Загоруйко Е.А.-М: Издательство МГТУ имени Н. Э. Баумана, 2000. — 436с.

9.Гасс, С. Линейное программирование/ С. Гасс — М.:Физматлит, 1961.-304 с.

10.Глебов, Н. И. Методы оптимизации: учеб.

пособие/ Н. И. Глебов, Ю. А. Кочетов, А. В. Плясунов.

Новосибирск: Новосибирский государственный университет, 2000. -105 с.

11.Зайченко, Ю. П. Исследование операций. Сборник задач/ Ю. П. Зайченко, С. А. Шумилова.

Киев: Вища школа. Изд-во при Киев.

ун-те, 1984.-224 с.

12. Зенкевич, Н. А. Материалы к установочной лекции. Вопрос № 33. Симплекс-метод решения задачи линейного программированияURL:

http://www.apmath.spbu.ru/ru/education/final/question33.pdf (дата обращения 15.

03.2012)

13. Зенкевич, Н. А. Практикум по исследованию операций: учеб.

пособие/Н. А. Зенкевич, Е. А. Губар.

СПб.: Санкт-Петербургский государственный университет, 2007. — 170 с. 14. Калихман, И.

Л. Сборник задач по математическому программированию/ И. Л. М. Калихман-М: Высш. школа, 1975. -270 с.

15. Карманов, В. Г. Математическое программирование: Учеб.

пособие. — 5-е изд., стереотип. — М.: Физматлит, 2004. -264 с.

16. Кремер, Н. Ш. Исследование операций в экономике: Учеб.

пособие для вузов /Н.Ш. Кремер, БА. Путко, И. М. Тришин, М. Н. Фридман; Под ред. проф. Н. Ш. Кремера. — М.: ЮНИТИ, 2005. — 407 с.

17.Лунгу, К. Н. Линейное программирование: руководство к решению задач/ К. Н Лунгу — М.: Физматлит, 2005. — 128 с.

18.Палий, И. А. Линейное программирование / И. А. Палий. — М.: Эксмо, 2008. -256 с.

19.Романовский, И. В. Алгоритмы решения экстремальных задач/ И. В. Романовский — М.: Наука, 1977.-352 с.

20. Саати, Т. Л. Математические методы исследования операций/ Т. Л. Саати.

М.:Воениздат. 1963._420 с.

21.Хемди А. Таха, Введение в исследование операций/А. Таха

Хемди — 7-е изд. — М.: «Вильямс», 2007. -903 c.

22.Шилдт, Г. Полный справочник по

С++./Герберт Шилдт; пер. с англ.

М.:Издательский дом «Вильямс», 2009.-800 с.

23.Matthias KalleDalheimer .A Comparison of Qt and Java;перевод: Andi Peredri. URL:

http://citforum.ru/programming/application/java_qt.shtml (датаобращения 19.

03.2012)ПРИЛОЖЕНИЕИсходный код:#include using namespace std;double temp, tmp;int col, str, r, u, i, j;class simplex{int n_of_var, n_of_res;int *sol;double **p;public:simplex ();~simplex ();bool optimal ();void leading_element ();};simplex:simplex ()//конструктор (инициализируем все переменные){cout<<" Ведите количество переменных" <>n_of_var;cout<<" Ведите количество ограничений" <>n_of_res;p=new double*[n_of_res+1]; sol=new int[n_of_res]; //здесь хранятся номера базисных элементовfor (i=0;i<(n_of_res+1);i++){p[i]=new double[n_of_var+n_of_res+1]; }p[0][0]=1;cout<<" Введите целевую функцию" <<(n_of_var+1);j++){cin>>temp;p[0][j]=-temp;}for (j=n_of_var+1;j<(n_of_var+n_of_res+1);j++){p[0][j]=0;}cout<<" Введите матрицу ограничений" <<(n_of_res+1);i++){for (j=1;j<(n_of_var+1);j++){cin>>p[i][j]; }for (j=(n_of_var+1);j<(n_of_var+n_of_res+1);j++){p[i][j]=0;}p[i][(n_of_var)+i]=1;}cout<<" ведите вектор правой части" <<(n_of_res+1);i++){cin>>p[i][0]; }};bool simplex: optimal ()//проверка плана на оптимальность, поиск ведущего столбца и строки{temp=0;for (j=1;j<(n_of_var+n_of_res+1);j++)//ведущийстолбец{if ((p[0][j]<0)&&(p[0][j]<<" Текущеерешениеоптимально" <n_of_res){cout<<" x" <<<" = «<

<<<" x" <<" = «<<0<<<» Значение целевой функции равно «<

<0) {temp=p[i][0]/p[i][col]; str=i;}};for (i=n_of_res;i>0;i—){if ((p[i][col]>0)&&((p[i][0]/p[i][col])<=temp)){temp=p[i][0]/p[i][col];str=i;}}if (str==0){cout<<" Решения не существует!" <<(n_of_var+n_of_res+1);j++)//делимведущуюстроку{ p[str][j]/=tmp;}for (i=0;i<(n_of_res+1);i++)//остальныестрокипреобразуем{if (i==str) continue;temp=p[i][col]; for (j=0;j<(n_of_var+n_of_res+1);j++){p[i][j]=p[i][j]-temp*p[str][j];}}for (i=0;i<(n_of_res+1);i++)//остальные строки преобразуем{for (j=0;j<(n_of_var+n_of_res+1);j++){}}for (i=0;i<=(n_of_var)) sol[i]=col+n_of_res;else sol[i]=col-n_of_var;}}}simplex:~simplex (){for (i=0;i