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

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

Содержание

Введение

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

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

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F(x)=∑cjxj=c1x1+c2x2+…+cnxn, j=(1,n),                                                       (1)

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

∑ aijxj≤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)=c1x1+c2x2+...+cnxn ->max(min)

a11x1+a12x2+...+a1nxn +х n +1 = b1

a21x1+a22x2+...+a2nxn+х n +2 = b2                                                                     (3)

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

am1x1+am2x2+...+amnxn+х n +т = bm

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

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

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

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

Страницы: 1, 2, 3, 4