Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Решение задач линейного программирования симплекс-методом

Название: Решение задач линейного программирования симплекс-методом
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 16:28:20 11 февраля 2011 Похожие работы
Просмотров: 9956 Комментариев: 20 Оценило: 5 человек Средний балл: 4.2 Оценка: неизвестно     Скачать

Содержание

Введение

1. Теоретический материал

1.1 Математическая формулировка задачи линейного программирования

1.2 Решение задач линейного программирования симплекс-методом

2. Постановка задачи

3. Решение поставленной задачи

4. Алгоритм программы

5. Программа для общего случая

6. Результаты работы программы

Заключение

Список использованных источников


Введение

линейный программирование симплекс алгоритм

Математическое моделирование как инструмент познания завоевывает все новые и новые позиции в различных областях деятельности человека. Оно становится главенствующим направлением в проектировании и исследовании новых систем, анализе свойств существующих систем, выборе и обосновании оптимальных условий их функционирования и т.п.

Изучение математического моделирования открывает широкие возможности для осознания связи информатики с математикой и другими науками. Абстрактное моделирование с помощью компьютеров – вербальное, информационное, математическое – в наши дни стало одной из информационных технологий в познавательном плане исключительно мощной.

Общее в моделях то, что во всех случаях модель в определённом смысле заменяла сам исследуемый объект. Вместо исходного объекта (оригинала) использовалась его модель, модель являлась представлением объекта в некоторой форме, отличной от формы его реального существования.

Модель – это материальный или идеальный объект, который строится для изучения исходного объекта (оригинала) и который отражает наиболее важные качества и параметры оригинала.

Практически во всех науках о природе, живой и неживой, об обществе, построение и использование моделей является мощным орудием познания. Реальные объекты и процессы бывают столь многообразны и сложны, что лучшим способом изучения часто является построение модели, отражающей лишь какую – то часть реальности.

В любом случае модель строится с целью узнать про объект что-либо новое или сохранить об объекте информацию, которая может стать недоступной в будущем.

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

Математическое моделирование относится к классу знакового моделирования, при этом модели могут создаваться из любых математических объектов, чисел, функций, уравнений, графиков, графов.

Практически во всех науках построение и использование моделей является мощным орудием познания.

В моделировании существует два пути:

1. Модель может быть похожей копией объекта, выполненной из другого материала и в другом масштабе, с отсутствием ряда деталей;

2. Модель может отражать реальность более абстрактно-словесным описанием, формализованным по каким-то правилам, соотношениям.

Всё чаще компьютеры при математическом моделировании используются не только для численных расчётов, но и для аналитических преобразований.

Результат аналитического исследования часто выражен в столь сложной форме, что при взгляде на неё не складывается восприятие описываемого ею процесса. Эту формулу можно протабулировать, представить графически, проиллюстрировать в динамике, то есть проделать то, что называется визуализацией абстракции.

1. Теоретический материал

Линейное программирование – это раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования. Специальные методы учитывают особенности и модели задач, ее целевой функции и системы ограничений.

Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда – необходимость разработки новых методов.

1.1 Математическая формулировка задачи линейного программирования

Нужно определить максимум линейной целевой функции (линейной формы):

F(x)=∑cj xj =c1 x1 +c2 x2 +…+cn xn , j=(1,n), (1)

при условиях:

∑ aij xj ≤bi , i=1,2,…,m (2)

Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах (а также в функции f ).Такую задачу называют «основной» или «стандартной» в линейном программировании.

1.2 Решение задач линейного программирования симплекс-методом

Задача ЛП в общем виде может быть записана так:

(c, x) − max

Ax = b,

где c =(c1 ,c2 ,...,cn )T – мерный вектор-столбец коэффициентов; x =(x1 ,x2,...,xn)T – мерный вектор-столбец неизвестных; A =(aij ),m × n – матрица коэффициентов; B =(b1 ,b2 ,...,bm ) – вектор-столбец коэффициентов.

В этом случае мы имеем дело с неотрицательными решениями системы уравнений.

Любая задача линейного программирования с помощью элементарных преобразований может быть приведена к каноническому виду.

F(x)=c1 x1 +c2 x2 +...+cn xn ->max(min)

a11 x1 +a12 x2 +...+a1n xn n +1 = b1

a21 x1 +a22 x2 +...+a2n xn n +2 = b2 (3)

. ......................

am1 x1 +am2 x2 +...+amn xn n +т = bm

xi ≥0 (i=1..n),

где F(x) – целевая функция; х12 ,…,хn – базисные переменные; остальные переменные называются свободными.

Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям задачи как точным равенствам.

Таблица 1 – Система ограничений и целевая функция

Базисные переменные Свободные члены X 1 X 2 X n X n+1 X n+2 Xn+m
X n+1 b1 a 11 a 12 a 1n 1 0 0
X n+2 b2 a 21 a 22 a 2n 0 1 0
X n+m b m a m1 a m2 a mn 0 0 1
F(x) 0 -c1 -c2 -cn 0 0 0

Рассмотрим алгоритм перехода к следующим симплекс-таблицам:

1. Выбираем ключевой столбец. Это столбец соответствующий минимально отрицательному (максимально положительному) элементу последней (индексной) строке:

Если отрицательных элементов в индексной строке нет, то план оптимальный.

2. В ключевом столбце выбираются положительные коэффициенты, если таких нет, то задача не имеет решений;

3. Выбираем ключевую строку:

Среди выбранных коэффициентов столбца, для которых абсолютная величина отношения соответствующего свободного члена к этому элементу минимальна.

Ключевой элемент – это элемент, стоящий на пересечении ключевого столбца и ключевой строки;

4. Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;

5. В новой таблице:

5.1 Все элементы ключевой строки делятся на ключевой элемент.

5.2 Все элементы ключевого столба равны нулю, за исключением ключевого элемента.

5.3 Столбец, у которого в ключевой строке имеется ноль, в новой таблице будет таким же.

5.4 Строка, у которой в ключевом столбце имеется ноль, в новой таблице будет такой же.

5.5 В остальные клетки записывается результат преобразования элементов старой таблицы.

6. Переход к шагу 1.

Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.


2. Постановка задачи

Для изготовления изделий двух видов склад может отпустить металла не более 150 кг, причем на изделие первого вида расходуется пять килограмм, а на изделие второго вида три килограмма. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий первого вида требуется изготовить не более 20 штук, а изделий второго вида не более 25 штук, причем одно изделие первого вида стоит 7 руб., а изделие второго вида стоит 8 руб.


3. Решение поставленной задачи

x1 – количество изделий первого вида.

x2 – количество изделий второго вида.

F(x) – целевая функция.

5x1 + 3x2 =150

x1 £20

x2 £25

x1, x2≥0

F(x) = 7x1 +8x2 ®max

Приведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, превращающие неравенства в равенства. Переменные x3, x4, x5 входят в уравнение с коэффициентом единица и только один раз:

5x1 + 3x2 +x3 =150

x1 +x4 =20

x2 +x5 =25

x1, x2, x3, x4, x5≥0

F(x)= 7x1 +8x2 +x3 +x4 +x5

x3, x4, x5 – базисные переменные; x1, x2 – свободные переменные.

Составим симплекс – таблицу, соответствующую каноническому виду:

Таблица2 – Итерация 1

Базис Свободные чл. X1 X2 X3 X4 X 5
X 3 150 5 3 1 0 0
X 4 20 1 0 0 1 0
X 5 25 0 1 0 0 1
F(x) 0 -7 -8 0 0 0

Построив первую таблицу, проверяем ее на оптимальность, то есть в последней строке таблицы ищем максимально отрицательный элемент, в нашем случае – это -8. Из этого следует, что столбец х2 становится ключевым. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке. Из полученных делений выбираем минимальное, у нас это будет 25. То есть строка, в которой получилось минимальное частное, будет являться ключевой (строка х5). А элемент, стоящий на пересечении ключевого столбца и ключевой строки будет являться ключевым элементом, в нашей задаче это будет 1.

Строим новую таблицу, следуя алгоритму, приведенному выше.

Таблица 3 – Итерация 2

Базис Свободные X1 X2 X3 X4 X5
X3 75 5 0 1 0 -3
X4 20 1 0 0 1 0
X2 25 0 1 0 0 1
F(x) 200 -7 0 0 0 8

Таблицу 3 проверяем на оптимальность таким же способом, что и изначальную таблицу. Находим ключевой элемент в таблице 3, и затем заново пересчитываем новую таблицу.

Таблица 4 – Итерация 3

Базис Свободные X1 X2 X3 X4 X5
X1 15 1 0 0,2 0 -0,6
X4 5 0 0 -0,2 1 0,6
X2 25 0 1 0 0 1
F(x) 305 0 0 1,4 0 3,8

В нашем случае таблица 4 стала окончательным решением, так как в последней строке нет отрицательных чисел, из этого следует, что мы нашли оптимальный способ решение поставленной задачи.

X1 =15; X2 =25; Fmax =305.

Для достижения максимальной прибыли, равной 305 руб., необходимо производить 15 изделий первого вида и 25 изделий второго вида в день.


4. Алгоритм программы

Блок-схема симплекс-метода

Вычислительная процедура симплекс-метода является итерационным процессом. Если задача содержит несколько переменных и ограничений, то этот процесс очень громоздок. Во многие практические задачи входят десятки переменных и ограничений (иногда намного больше), и ясно, что неразумно решать эти задачи вручную. Симплекс-метод – это метод для электронно-вычислительных машин. Не случайно развитие теории линейного программирования совпало по времени с развитием электронно-вычислительных машин. Без них теория имела бы весьма узкую область приложений.


5. Программа для общего случая

#include ”stdafx.h”

#include ”iostream”

#include “locale”

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{ int a,b,d,stl,str,baz[10],f,g=0,i,j,l=0,q=0,z=0,y=0,xx,z1[10];

float m,tab[10][10],min=1000,c[10],tab1[10][10],x=1000;

setlocale(LC_ALL, ”russian”);

cout<<“Введитеколичествострокистолбцов”<<endl;

cin>>a>>b;

//заполнение начальной матрицы

for (i=0;i<a;i++)

{

for (j=0;j<b;j++)

{cout<<”Введите [”<<i<<”][”<<j<<“] элементтаблицы”<<endl;

cin>>tab[i][j];

}}

cout<<”перваяитерация”<<endl;

for (i=0;i<a;i++)

{

for (j=0;j<b;j++){cout<<tab[i][j]<<" ";}cout<<endl;}

//проверка на оптимальность

k:

l=0;

for (i=0;i<b;i++){

if (tab[a-1][i]<0) {l=l+1;}}

if (l==0){

for (j=1;j<b-a+1;j++){

int kol=0,nol=0,ind;

for (i=0;i<a-1;i++){

if (tab[i][j]==1) {kol++;ind=i;}

else nol++;

}

if ((kol==1) && (a-nol==2))

cout<<”x=”<<j<<”=”<<tab[ind][0]<<endl;

}cout<<”Решениеоптимально”<<endl;

for (i=0;i<a;i++)

{ for (j=0;j<b;j++)

{cout<<tab[i][j]<< ” “;}cout<<endl;}

cout<<”F(x)=”<<tab[a-1][0];

return 0;}

x=1000;

//поискключевогостолбца

for (i=1;i<b;i++)

{ if (tab[a-1][i]<=x)

{x=tab[a-1][i];

stl=i;

}}

//поискключевойстроки

for (j=0;j<a-1;j++)

{ if (tab[j][stl]>0)

c[j]=tab[j][0]/tab[j][stl];

else

c[j]=1000;}

cout<<endl;

cout<<”Массив для нахождения ключевой строки”<<endl;

for (j=0;j<a-1;j++){

cout<<c[j]<< “ “;

}

cout<<endl;

for (i=0;i<(a-1);i++)

if (c[i]<min){

min=c[i];

str=i;

}

cout<<endl;

cout<<”Kлючевойстолбециключеваястрока”<<endl;

cout<<stl<<” ”<<str<<” “<<endl;

cout<<endl;

cout<<“Ключевойэлемент:”<<tab[str][stl]<<endl;

cout<<endl;

//пересчетновойтаблицы

for (i=0;i<a;i++)

{ for (j=0;j<b;j++)

{tab1[i][j]=tab[i][j]-(tab[i][stl]*tab[str][j]/tab[str][stl]);

tab1[i][stl]=0;

tab1[str][stl]=1;

tab1[str][j]=tab[str][j]/tab[str][stl];

}}

//переприсвоенние матриц и вывод их на экран

for (i=0;i<a;i++)

{ for (j=0;j<b;j++)

{ tab[i][j]=tab1[i][j];

}}

goto k;

return 0;

}

6. Результаты работы программы

Введите количество строк и столбцов

4

6

Введите [0][0] элемент таблицы

150

Введите [0][1] элемент таблицы

5

Введите [0][2] элемент таблицы

3

Введите [0][3] элемент таблицы

1

Введите [0][4] элемент таблицы

0

Введите [0][5] элемент таблицы

0

Введите [1][0] элемент таблицы

20

Введите [1][0] элемент таблицы

1

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

1

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

25

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

1

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

1

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

-7

Введите [1][0] элемент таблицы

-8

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

0

Введите [1][0] элемент таблицы

0

Первая итерация

150 5 3 1 0 0

20 1 0 0 1 0

25 0 1 0 0 1

0 -7 -8 0 0 0

Массив для нахождения ключевой строки

50 1000 25

Ключевой столбец и ключевая строка

2 2

Ключевой элемент:1

Массив для нахождения ключевой строки

15 20 1000

Ключевой столбец и ключевая строка

1 0

Ключевой элемент:5

Решение оптимально!

х1=15

х2=25

F(x)=305

15 1 0 0.2 0 -0.6

5 0 0 -0.2 1 0.6

25 0 1 0 0 1

305 0 0 1.4 0 3.8

Заключение

Целью курсового проекта было решение задач линейного программирования симплекс-методом, составление алгоритма, составление программы по алгоритму и вывод результата на экран.

Для нахождения оптимального решения можно пойти наиболее простым способом с точки зрения лица, которое непосредственно производит решение задачи. Для более быстрого решения задачи можно воспользоваться языками программирования, что приведет к более быстрому решению задачи.

Он основан на пересчёте коэффициентов в системе уравнений и целевой функции при перемене мест свободной и базисной переменных можно формализовать и свести к преобразованию симплекс-таблицы.

Симплекс-метод является вычислительной процедурой представленной в алгебраической форме. Он непосредственно применяется к общей задаче линейного программирования в стандартной форме.

В данном проекте был составлен оптимальный план выпуска продукции каждого вида, обеспечивающий максимальную прибыль.

Список использованных источников

1. Ашихмин В.Н. «Введение в математическое моделирование». Москва: Логос, 2005.

2. Банди Б. «Основы линейного программирования». Москва: Радио и связь, 1989.

3. Большакова И.В. «Линейное программирование». Минск: БНТУ, 2004.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита04:14:13 03 ноября 2021
.
.04:14:11 03 ноября 2021
.
.04:14:09 03 ноября 2021
.
.04:14:08 03 ноября 2021
.
.04:14:08 03 ноября 2021

Смотреть все комментарии (20)
Работы, похожие на Курсовая работа: Решение задач линейного программирования симплекс-методом

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(287698)
Комментарии (4159)
Copyright © 2005-2021 HEKIMA.RU [email protected] реклама на сайте