Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
Общее в моделях то, что во всех случаях модель в определенном смысле заменяла сам исследуемый объект. Вместо исходного объекта (оригинала) использовалась его модель, модель являлась представлением объекта в некоторой форме, отличной от формы его реального существования. В любом случае модель строится с целью узнать про объект что-либо новое или сохранить об объекте информацию, которая может стать недоступной в будущем. Как правило, процесс изучения, связанный с использованием моделей и называемый моделированием не заканчивается созданием одной модели. Построив модель и получив с ее помощью, какие-либо результаты, соотносят их с реальностью, и если это соотношение дает неудовлетворительные результаты, то в построенную модель вносят коррективы или даже создают другую модель.Линейное программирование - это раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные.Нужно определить максимум линейной целевой функции (линейной формы): F(x)=?cjxj=c1x1 c2x2 … cnxn, j=(1,n), (1) при условиях: ? aijxj?bi , i=1,2,…,m (2)Задача имеет m n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям задачи как точным равенствам. Это столбец соответствующий минимально отрицательному (максимально положительному) элементу последней (индексной) строке: Если отрицательных элементов в индексной строке нет, то план оптимальный. В ключевом столбце выбираются положительные коэффициенты, если таких нет, то задача не имеет решений; Выбираем ключевую строку: Среди выбранных коэффициентов столбца, для которых абсолютная величина отношения соответствующего свободного члена к этому элементу минимальна.Для изготовления изделий двух видов склад может отпустить металла не более 150 кг, причем на изделие первого вида расходуется пять килограмм, а на изделие второго вида три килограмма.x1 - количество изделий первого вида. x2 - количество изделий второго вида. Приведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, превращающие неравенства в равенства. Составим симплекс - таблицу, соответствующую каноническому виду: Таблица 2 - Итерация 1 Построив первую таблицу, проверяем ее на оптимальность, то есть в последней строке таблицы ищем максимально отрицательный элемент, в нашем случае - это-8. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке.Если задача содержит несколько переменных и ограничений, то этот процесс очень громоздок. Во многие практические задачи входят десятки переменных и ограничений (иногда намного больше), и ясно, что неразумно решать эти задачи вручную.float m,tab[10][10],min=1000,c[10],tab1[10][10],x=1000; cout<<“Введите количество строк и столбцов”<<endl; {cout<<tab[i][j]<< ”“;}cout<<endl;} cout<<”F(x)=”<<tab[a-1][0]; {if (tab[j][stl]>0) c[j]=tab[j][0]/tab[j][stl]; {tab1[i][j]=tab[i][j]-(tab[i][stl]*tab[str][j]/tab[str][stl]);Введите [0][0] элемент таблицы Введите [0][1] элемент таблицы Введите [0][2] элемент таблицы Введите [0][3] элемент таблицы Введите [0][4] элемент таблицыДля нахождения оптимального решения можно пойти наиболее простым способом с точки зрения лица, которое непосредственно производит решение задачи. Для более быстрого решения задачи можно воспользоваться языками программирования, что приведет к более быстрому решению задачи.
План
Содержание
Введение
1. Теоретический материал
1.1 Математическая формулировка задачи линейного программирования
1.2 Решение задач линейного программирования симплекс-методом
2. Постановка задачи
3. Решение поставленной задачи
4. Алгоритм программы
5. Программа для общего случая
6. Результаты работы программы
Заключение
Список использованных источников
Введение
линейный программирование симплекс алгоритм
Математическое моделирование как инструмент познания завоевывает все новые и новые позиции в различных областях деятельности человека. Оно становится главенствующим направлением в проектировании и исследовании новых систем, анализе свойств существующих систем, выборе и обосновании оптимальных условий их функционирования и т.п.
Изучение математического моделирования открывает широкие возможности для осознания связи информатики с математикой и другими науками. Абстрактное моделирование с помощью компьютеров - вербальное, информационное, математическое - в наши дни стало одной из информационных технологий в познавательном плане исключительно мощной.
Общее в моделях то, что во всех случаях модель в определенном смысле заменяла сам исследуемый объект. Вместо исходного объекта (оригинала) использовалась его модель, модель являлась представлением объекта в некоторой форме, отличной от формы его реального существования.
Модель - это материальный или идеальный объект, который строится для изучения исходного объекта (оригинала) и который отражает наиболее важные качества и параметры оригинала.
Практически во всех науках о природе, живой и неживой, об обществе, построение и использование моделей является мощным орудием познания. Реальные объекты и процессы бывают столь многообразны и сложны, что лучшим способом изучения часто является построение модели, отражающей лишь какую - то часть реальности.
В любом случае модель строится с целью узнать про объект что-либо новое или сохранить об объекте информацию, которая может стать недоступной в будущем.
Как правило, процесс изучения, связанный с использованием моделей и называемый моделированием не заканчивается созданием одной модели. Построив модель и получив с ее помощью, какие-либо результаты, соотносят их с реальностью, и если это соотношение дает неудовлетворительные результаты, то в построенную модель вносят коррективы или даже создают другую модель. В случае достижения хорошего соответствия с реальностью выясняют границы применения модели. Это очень важный вопрос, он решается путем сравнения модели с оригиналом путем сравнения предсказаний, полученных с помощью компьютерной модели. Если это сравнение дает удовлетворительные результаты, то модель принимают на вооружение, если нет, приходится создавать другую модель.
Математическое моделирование относится к классу знакового моделирования, при этом модели могут создаваться из любых математических объектов, чисел, функций, уравнений, графиков, графов.
Практически во всех науках построение и использование моделей является мощным орудием познания.
В моделировании существует два пути: 1. Модель может быть похожей копией объекта, выполненной из другого материала и в другом масштабе, с отсутствием ряда деталей;
2. Модель может отражать реальность более абстрактно-словесным описанием, формализованным по каким-то правилам, соотношениям.
Все чаще компьютеры при математическом моделировании используются не только для численных расчетов, но и для аналитических преобразований.
Результат аналитического исследования часто выражен в столь сложной форме, что при взгляде на нее не складывается восприятие описываемого ею процесса. Эту формулу можно протабулировать, представить графически, проиллюстрировать в динамике, то есть проделать то, что называется визуализацией абстракции.
Вывод
Целью курсового проекта было решение задач линейного программирования симплекс-методом, составление алгоритма, составление программы по алгоритму и вывод результата на экран.
Для нахождения оптимального решения можно пойти наиболее простым способом с точки зрения лица, которое непосредственно производит решение задачи. Для более быстрого решения задачи можно воспользоваться языками программирования, что приведет к более быстрому решению задачи.
Он основан на пересчете коэффициентов в системе уравнений и целевой функции при перемене мест свободной и базисной переменных можно формализовать и свести к преобразованию симплекс-таблицы.
Симплекс-метод является вычислительной процедурой представленной в алгебраической форме. Он непосредственно применяется к общей задаче линейного программирования в стандартной форме.
В данном проекте был составлен оптимальный план выпуска продукции каждого вида, обеспечивающий максимальную прибыль.
Список литературы
1. Ашихмин В.Н. «Введение в математическое моделирование». Москва: Логос, 2005.
2. Банди Б. «Основы линейного программирования». Москва: Радио и связь, 1989.
