Читайте также:
|
Математическое программирование – это математическая дисциплина, в которой изучают теорию и методы задач о нахождении экстремальных (максимальных и минимальных) значений функций действительных переменных на множествах, определяемых ограничениями в виде линейных и нелинейных числовых неравенств.
Простейшие из задач математического программирования – это задачи безусловной оптимизации. В задачах безусловной оптимизации необходимо отыскать локальный экстремум (максимум или минимум) некоторой действительной функции F, которая называется целевой:
F (x1, x2, …, xn) → max (min). Искомое решение x задачи – это n-мерный вектор с действительными компонентами xi (i = 1, 2, …, n): x = (x1, x2, …, xn).
Если локальный экстремум не является глобальным, то после его нахождения поиск других локальных экстремумов продолжается: при этом на последующих этапах для итерационных процессов отыскания экстремумов выбирают другие начальные точки. Глобальный экстремум (как максимальный, так и минимальный) ищется путём сравнения локальных экстремальных значений.
Метод градиентного спуска – простейший из методов отыскания безусловного экстремума функций многих переменных. Требуется найти минимальное значение дифференцируемой функции n переменных: F (x) ≡ F (x1, x2, …, xn) → min. Проблема решается итерационным методом (методом последовательных приближений).
В общем случае задачи математического программирования, помимо целевой функции F, принимающей действительные значения, содержат ряд ограничений в форме равенств и неравенств. Неравенства – ограничения, определяющие допустимое множество, задаются с помощью действительных функций gi (i = 1, 2, …, m) (левых частей неравенств-ограничений) и hj (j = 1, 2, …, k) (левых частей равенств-ограничений).
В простейшей (канонической) форме задача линейного программирования (ЛП) записывается следующим образом. Необходимо найти минимум целевой функции F(x):
F(x) = Σ
при условии неотрицательности переменных xj xj ≥ 0, j = 1, 2, …, n и дополнительных равенствах-ограничениях вида. Здесь вектор x = (x1, x2, …, xn) – искомое решение задачи оптимизации.
Задачи линейного программирования алгоритм требует решения
систем уравнений, а это число велико даже при небольших значениях числа n и стремительно возрастает при его увеличении. Между тем многие практические задачи линейного программирования содержат сотни переменных. Потому потребовался более рациональный метод решения задач ЛП. Один из наиболее распространённых в настоящее время методов решения задач ЛП – это так называемый симплекс-метод.
Симплекс-метод – универсальный метод решения задач линейного программирования. Это итерационный метод, то есть оптимальное решение ищется с помощью последовательных приближений.
Постановка задачи. Пусть предприятие производит три вида продукции: G1, G2, G3. От продажи единицы продукции вида G1предприятие получает прибыль в размере c1 = 1 у.е., от продажи единицы продукции вида G2 – в размере c2 = 2 у.е., а от продажи продукции вида G3 – в размере c3 = 3 у.е.
Для выпуска продукции предприятие располагает тремя видами ресурсов: R1, R2 и R3 в количестве, заданном вектором ограничений b = (b1, b2, b3) = (800, 600, 1000). Объемы затрат ресурсов на производство продукции представлены технологической матрицей A =║ai j║ (i = 1, 2, 3; j = 1, 2, 3), которая в данном случае является квадратной. Требуется определить план производства, максимизирующий прибыль предприятия от производства продукции с учетом указанных ограничений.
Алгоритм симплекс-метода решения задачи линейного программирования.
1. Задачу необходимо привести к каноническому виду.
2. Заполнить симплекс-таблицу.
3. Определить разрешающий столбец.
4. Определить разрешающую строку.
5. Найти разрешающий элемент.
6. Разделить все элементы разрешающей строки на разрешающий элемент.
7. Обнулить все элементы разрешающего столбца, за исключением разрешающего элемента.
8. Записать результат итерации.
9. В том случае, когда в последней строке симплекс-таблицы имеются отрицательные элементы, необходимо повторить пункты 3–8.
10. Если же в последней строке симплекс-таблицы отрицательные элементы не найдутся, то необходимо закончить итерационный процесс и записать результат последней из итераций в качестве окончательного.
11. Выполнить содержательный анализ полученного результата.
Дата добавления: 2015-07-16; просмотров: 176 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Понятие математической модели. | | | Транспортная задача |