Симплекс-метод
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
Введение
Математическое программирование - это область математики, разрабатывающая численные методы решения задач на экстремумах функций многих переменных с ограничениями на область изменения этих переменных.
Задачи математического программирования возникли из стремления к наиболее эффективному использованию имеющихся ресурсов. Такие задачи могут встречаться в разных отраслях, таких как экономика, техника, научные исследования. Например, в экономике часто возникали проблемы, связанные с извлечение максимальной прибыли из производства. Такие задача при текущем уровне развития экономики приобрели первостепенное значение. Сегодня нужно все свои шаги в производстве рассчитывать очень основательно, так как состояние экономики изменчиво. При этом нужно учитывать объем затрат на единицу продукции, прибыль полученную с этой единицы и состояние рынка на момент решения задачи. Среди множества возможных вариантов приходится отыскивать наилучший, при ограничениях, налагаемых на ресурсы и затраты.
Для решения этих трудностей в экономическую науку активно внедряется математическое программирование. Его применение существенно расширяет возможности традиционного экономического анализа, что позволяет ставить и решать качественно новые экономические проблемы. Одним из таких методов, позволяющих решать поставленные задачи по максимуму прибыли является симплекс - метод.
Симплекс - метод можно интерпретировать двумя способами:
) Экономически, в этом случае симплекс - метод позволяет решать вопросы о наиболее эффективном распределении средств. Выбрав начальный план действий и постепенно улучшая его достигается оптимальное решение. Каждому переходу по симплекс-методу соответствует переход от одной программы действий к другой, которая ближе к поставленной цели.
) Математически же симплекс-метод представляет собой тождественные алгебраические преобразования, дающие возможность от одной системы уравнений перейти к другой, эквивалентной ей системе. Достигнуть оптимального решения можно не выходя за пределы первых четырех алгебраических операций.
1. Теоретический раздел
.1 Постановка задачи
Используя симплекс-метод решить ЗЛП:
При ограничениях:
Описание входной информации
Userform2 - форма для ввода целевой функции и ограничений
Описание выходной информации
1) Лист Каноническая таблица - лист, на котором содержится приведенная к каноническому виду таблица.
) Листы Симплекс таблица № n - лист, на котором содержится n-ая симплекс таблица.
) Лист Оптимальный план - лист, на котором содержится оптимальный план.
) MsgBox - встроенная функция VBA, которая выводит сообщение о том, что оптимальный план найден и значение функции.
1.2 Характеристика симплекс-метода
При решении задач линейного программирования наиболее распространены 2 способа - графический и симплекс-метод.
Использование графического способа удобно только при решении задач ЛП с двумя переменными. При большем числе переменных необходимо применение алгебраического аппарата. Информация, которую можно получить с помощью симплекс-метода, не ограничивается лишь оптимальными значениями переменных. Симплекс-метод фактически позволяет дать экономическую интерпретацию полученного решения и провести анализ модели.
Процесс решения задачи линейного программирования носит итерационный характер: однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет получено оптимальное решение. Процедуры, реализуемые в рамках симплекс-метода, требуют применения вычислительных машин - мощного средства решения задач линейного программирования.
Симплекс-метод - это характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач.
При решении задачи ЛП симплекс-методом реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки (обычно начало координат), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
Для нахождения оптимального решения необходимо от одной угловой точки переходить к другой, то есть от исходного базисного решения к другому, при этом значение функции должно расти, если задача на максимум и убывать, если задача на минимум.
Выбор каждой последующей экстремальной (угловой) точки при использовании симплекс-метода определяется следующими двумя правилами:
). Каждая последующая угловая точка должна быть смежной с предыдущей. Этот переход осуществляется по границам (ребрам) пространства решений
). Обратный переход к предшествующей экстремальной точке не может производиться. Таким образом, отыскание оптимального решения начинается с некоторой допустимой угловой точки, и все переходы осуществляются только к смежным точкам, причем перед новым переходом каждая из полученных точек проверяется на оптимальность.
1.3 Математическое описание алгоритма симплекс-метода
Математически алгоритм симплекс-метода можно представить в несколько шагов:
Шаг 1. Построить и заполнить исходную симплекс-таблицу (табл. 1).
Таблица 1. Исходная таблица
Базис……СВ………………
В столбце б