Автор работы: Пользователь скрыл имя, 14 Февраля 2012 в 18:57, реферат
Переход от административных к экономическим методам управления производством, развитие рыночных отношений, распространение договорных цен – все это нацеливает экономические службы на поиск наилучших хозяйственных решений, обеспечивающих максимум результатов или минимум затрат. Необходимость поиска таких решений обуславливается, прежде всего, существованием ограничений на факторы производства, в пределах которых предприятия (отдельные производители) постоянно функционируют.
Введение
1. Понятие математического программирования
2. Понятие линейного программирования. Виды задач линейного программирования
3. Понятие нелинейного программирования
4. Динамическое программирование
После того, как функция
Беллмана и соответствующие оптимальные
управления найдены для всех шагов
с n-го по первый, производится второй этап
решения задачи, который называется безусловной
оптимизацией.
В общем виде задача
динамического программирования формулируется
следующим образом: требуется определить
такое управление X*, переводящее
систему из начального состояния S0
в конечное состояние Sn, при котором
целевая функция F(S0,X*) принимает наибольшее
(наименьшее) значение.
Особенности математической
модели динамического программирования
заключаются в следующем:
задача оптимизации
формулируется как конечный многошаговый
процесс управления;
целевая функция
является аддитивной и равна сумме
целевых функций каждого шага;
выбор управления Xk
на каждом шаге зависит только от состояния
системы к этому шагу Sk-1 и не влияет на
предшествующие шаги (нет обратной связи);
состояние системы
Sk после каждого шага управления зависит
только от предшествующего состояния
системы Sk-1 и этого управляющего воздействия
Xk (отсутствие последействия) и может быть
записано в виде уравнения состояния:
на каждом шаге управление
Xk зависит от конечного числа управляющих
переменных, а состояние системы Sk зависит
от конечного числа переменных;
оптимальное управление
X* представляет собой вектор, определяемый
последовательностью
X*=(X*1, X*2, …, X*k, …, X*n),
число которых и определяет
количество шагов задачи.
Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как
Fn(S)=max{Wn(S,Xn)},
где максимум ищется
по всем возможным значениям Xn.
Дальнейшие вычисления
производятся согласно рекуррентному
соотношению, связывающему функцию
Беллмана на каждом шаге с этой же функцией,
но вычисленной на предыдущем шаге:
Fk(S)=max{Wk(S,Xk)+Fk+1(S'(S,
Этот максимум (или
минимум) определяется по всем возможным
для k и S значениям переменной управления
X.
Безусловная оптимизация.
После того, как функция Беллмана
и соответствующие оптимальные
управления найдены для всех шагов
с n-го по первый (на первом шаге k=1 состояние
системы равно ее начальному состоянию
S0), осуществляется второй этап решения
задачи. Находится оптимальное управление
на первом шаге X1, применение которого
приведет систему в состояние S1(S,x1*), зная
которое можно, пользуясь результатами
условной оптимизации, найти оптимальное
управление на втором шаге, и так далее
до последнего n-го шага.
Постановка задачи линейного программирования и двойственная задача линейного программирования.
Линейное программирование
является составной частью
Искусство математического
моделирования состоит в том,
чтобы учесть как можно больше
факторов по возможности
В большинстве
случаев первой степенью
Основные формы задачи ЛП.
Различают три
основные формы задач
Стандартная задача ЛП.
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
Каноническая задача ЛП.
Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
При изучении
задач ЛП сложилась
Исследование различных,
в том числе и экономических,
процессов обычно начинается с их
моделирования, т.е. отражения реального
процесса через математические соотношения.
При этом производится составление
уравнений или неравенств, связывающих
различные показатели (переменные)
исследуемого процесса, которые образуют
систему ограничений.
В этих соотношениях
выделяются такие переменные, меняя
которые, можно получить оптимальное
значение основного показателя данной
системы (прибыль, доход, затраты и
т.п.). Соответствующие методы, позволяющие
решать указанные задачи, объединяются
в общее название «математическое
программирование» или «
Математическое
Итак, математическое
программирование — это раздел высшей
математики, занимающийся решением задач,
связанных с нахождением
Методами математического
программирования решаются задачи распределения
ресурсов, планирования выпуска продукции,
ценообразования, транспортные задачи
и т.п.
Математическое
Составление математической модели экономической задачи включает следующие этапы: 1) выбор переменных задачи; 2) составление системы ограничений; 3) выбор целевой функции.
Переменными задачи называются величины x1, x2, х3,..., xn, которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора X=(x1, x2, x3,…., xn)
Система ограничений включает в себя систему уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий, например, положительности переменных и т.п.
Целевой функцией называют
функцию переменных задачи, которая
характеризует качество выполнения
задачи и экстремум которой требуется
найти.
Таким образом, общая
задача математического
Z(X) = f (x1, x2, x3,…., xn)max(min) (6.4.13)
и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений
(x1, x2, x3,…., xn ) =0, i=1,2,..,l
(x1, x2, x3,…., xn ) >(<) 0, i = l +1, l+2,…,m (6.4.15)
Если целевая функция (6.4.13)и система ограничений (6.4.14), (6.4.15) являются линейными, то задача математического программирования называется задачей линейного программирования,
В общем случае задача линейного программирования может быть записана в следующем виде:
Это позволяет найти
экстремум целевой функции
Допустимым решением (планом) задачи линейного программирования называется любой п-мерный вектор X=(x1, x2, x3,…., xn), удовлетворяющий системе ограничений и условиям неотрицательности.
Множество допустимых
решений (планов) задачи образует область
допустимых решений (ОДР). Оптимальным
решением (планом) задачи линейного
программирования называется такое
допустимое решение (план) задачи,
при котором целевая функция достигает
экстремума.
Так как в данном случае решается задача на экстремум, то возникает вопрос о возможности использования классических методов исследования на экстремум функции многих переменных. Первым шагом в этом направлении является использование необходимого условия экстремума функции, которое состоит в том, что частные производные функции многих переменных или равны нулю, или не существуют. В данном случае
i=1, 2,…,n .
Но если все сi = 0, то и Z = 0, т.е. экстремум функции не обнаруживается. Связано это с тем, что производную можно использовать для определения экстремума только во внутренних точках области решений, а в данном случае экстремум, как будет показано ниже, находится на границах области. Отсюда и возникает необходимость разработки специальных методов поиска экстремума.