Симплекс-метод

Контрольная работа - Математика и статистика

Другие контрольные работы по предмету Математика и статистика

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



Введение

 

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

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

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

Симплекс - метод можно интерпретировать двумя способами:

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

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

 

 

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

 

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

 

Используя симплекс-метод решить ЗЛП:

 

 

При ограничениях:

 

 

Описание входной информации

Userform2 - форма для ввода целевой функции и ограничений

Описание выходной информации

1) Лист Каноническая таблица - лист, на котором содержится приведенная к каноническому виду таблица.

) Листы Симплекс таблица № n - лист, на котором содержится n-ая симплекс таблица.

) Лист Оптимальный план - лист, на котором содержится оптимальный план.

) MsgBox - встроенная функция VBA, которая выводит сообщение о том, что оптимальный план найден и значение функции.

 

1.2 Характеристика симплекс-метода

 

При решении задач линейного программирования наиболее распространены 2 способа - графический и симплекс-метод.

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

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

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

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

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

Выбор каждой последующей экстремальной (угловой) точки при использовании симплекс-метода определяется следующими двумя правилами:

). Каждая последующая угловая точка должна быть смежной с предыдущей. Этот переход осуществляется по границам (ребрам) пространства решений

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

 

1.3 Математическое описание алгоритма симплекс-метода

 

Математически алгоритм симплекс-метода можно представить в несколько шагов:

Шаг 1. Построить и заполнить исходную симплекс-таблицу (табл. 1).

 

Таблица 1. Исходная таблица

Базис……СВ………………

В столбце б

s