Смекни!
smekni.com

Линейное программирование (стр. 1 из 8)

Содержание

Содержание

1.Пояснительная записка

1.1.Введение

2.Теоретическая часть

2.1 Элементы теории матричных игр

2.2 Решение матричных игр в чистых стратегиях

2.3 Решение матричных игр в смешанных стратегиях путём сведения к задаче линейного программирования

3. Практическая часть

3.1 Построение математической модели задачи

3.2 Выбор метода решения и привидения задачи к каноническому виду

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

- Блок схема к поставленной задачи

- Программа к поставленной задачи (программный код)

3.4 Анализ результата решения поставленной задачи

4. Вывод курсового проектирования

Заключение

Список основных источников

1. Пояснительная записка курсового проектирования

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

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА 1.1 Математическое программирование.

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn ) ( bi , где gi - функция, описывающая ограничения, ( - один из следующих знаков ( , ( , ( , а bi - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ). Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные. Задачу линейного программирования можно сформулировать так . Найти max [pic] при условии : a11 x1 + a12 x2 + . . . + a1n xn ( b1 ; a21 x1 + a22 x2 + . . . + a2n xn ( b2 ; . . . . . . . . . . . . . . . . . . . . . . . . . . . . am1 x1 + am2 x2 + . . . + amn xn ( bm ; x1 ( 0, x2 ( 0, . . . , xn ( 0 . Эти ограничения называются условиями не отрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической. В матричной форме задачу линейного программирования, записывают следующим образом. Найти max cT x при условии A x ( b ; x ( 0 , где А - матрица ограничений размером (m(n), b(m(1) - вектор-столбец свободных членов, x(n ( 1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции. Решение х0 называется оптимальным, если для него выполняется условие сТ х0 ( сТ х , для всех х ( R(x). Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации. Для решения задач данного типа применяются методы:

1) графический;

2) табличный ( прямой, простой ) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

1.2 Табличный симплекс - метод Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны. Алгоритм решения сводится к следующему :

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

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

3. Формируется симплекс-таблица.

4. Рассчитываются симплекс- разности.

5. Принимается решение об окончании либо продолжении счёта.

6. При необходимости выполняются итерации.

7. На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана Гаусса или каким-нибудь другим способом.

1.3 Метод искусственного базиса. Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами, а в задачи минимизации с положительными. Таким образом, из исходной получается новая задача. Если в оптимальном решении задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.

1.4 Модифицированный симплекс-метод. В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы. В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m. В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс -разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана Гаусса. Особенности заключаются в наличии двух таблиц - основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных формул.

ПОСТАНОВКА ЗАДАЧИ:

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

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

Соответственно:

1. Первое с чего начинаем, это строим математическую модель задачи;

2. Выбираем метод решения задачи и приводим задачу к каноническому виду;

3. Решаем задачу путём сведения к задаче линейного программирования;

4. Затем строим блок схему к задачи с написанием программы на языке С++Builder 6.;

5. Дальнейшим этапом моей работы будет анализ результата решения выполненной мною задачи.

1.1 Введение

1 Математические методы

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

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

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

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

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

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

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

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

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

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

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

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

Существует следующая классификация абстрактных моделей:

Вербальные

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