Автор работы: Пользователь скрыл имя, 14 Февраля 2012 в 18:57, реферат
Переход от административных к экономическим методам управления производством, развитие рыночных отношений, распространение договорных цен – все это нацеливает экономические службы на поиск наилучших хозяйственных решений, обеспечивающих максимум результатов или минимум затрат. Необходимость поиска таких решений обуславливается, прежде всего, существованием ограничений на факторы производства, в пределах которых предприятия (отдельные производители) постоянно функционируют.
Введение
1. Понятие математического программирования
2. Понятие линейного программирования. Виды задач линейного программирования
3. Понятие нелинейного программирования
4. Динамическое программирование
План:
Введение
1.
Понятие математического
программирования
2.
Понятие линейного
программирования. Виды
задач линейного
программирования
3.
Понятие нелинейного
программирования
4.
Динамическое программирование
Введение
Переход от административных
к экономическим методам
Известно, что определенный
вид продукции можно
Как лучше организовать
производство, по каким ценам выгодно
производить продукцию, как лучше
всего использовать производственные
ресурсы, которые высвобождаются и
т.п.?
На все эти вопросы
позволяет получить ответ математическое
программирование, являющееся действенным
инструментом принятия решений.
Математическое
В общем виде математическая
постановка экстремальной задачи состоит
в определении наибольшего или
наименьшего значения целевой функции
f(x1, х2,.........., xn) при условиях gi(x1, х2,..........,
xn) ≤ bi, где f и gi — заданные функции, a bi
— некоторые действительные числа.
В зависимости от
свойств функций f и gi математическое
программирование можно рассматривать
как ряд самостоятельных дисциплин, занимающихся
изучением и разработкой методов решения
определенных классов задач.
Прежде всего задачи
математического программирования делятся
на задачи линейного и нелинейного программирования.
При этом если все функции f и gi линейные,
то соответствующая задача является задачей
линейного программирования. Если же хотя
бы одна из указанных функций нелинейная,
то соответствующая задача является задачей
нелинейного программирования. Наиболее
изученным разделом математического программирования
является линейное программирование.
Для решения задач линейного программирования
разработан целый ряд эффективных методов,
алгоритмов и программ. Среди задач нелинейного
программирования наиболее глубоко изучены
задачи выпуклого программирования. Это
задачи, в результате решения которых
определяется минимум выпуклой (или максимум
вогнутой) функции, заданной на выпуклом
замкнутом множестве.
В свою очередь, среди
задач выпуклого
В задачах целочисленного программирования неизвестные могут принимать только целочисленные значения.
Задача, процесс нахождения
решения которой является многоэтапным,
относится к задаче динамического
программирования.
1.
Понятие математического
программирования
Математическое
Наличие ограничений
делает задачи математического
Для решения задач
математического
Математическое
В зависимости от
свойств целевой функции и
функции ограничений все задачи
математического программирования делятся
на три основных класса:
задачи
линейного программирования,
задачи
нелинейного программирования;
задачи
динамического
Если целевая функция
и функции ограничений –
2.
Понятие линейного
программирования. Виды
задач линейного
программирования
Линейное программирование
(ЛП) – один из первых и наиболее
подробно изученных разделов математического
программирования. Именно линейное программирование
явилось тем разделом, с которого
и начала развиваться сама дисциплина
"математическое программирование".
Термин "программирование" в названии
дисциплины ничего общего с термином "программирование
(т.е. составление программы) для ЭВМ"
не имеет, т.к. дисциплина "линейное
программирование" возникла еще до
того времени, когда ЭВМ стали широко применяться
для решения математических, инженерных,
экономических и др. задач.
Термин "линейное
программирование" возник в результате
неточного перевода английского "linear
programming". Одно из значений слова "programming"
- составление планов, планирование. Следовательно,
правильным переводом английского "linear
programming" было бы не "линейное программирование",
а "линейное планирование", что более
точно отражает содержание дисциплины.
Однако, термины линейное программирование,
нелинейное программирование, математическое
программирование и т.д. в нашей литературе
стали общепринятыми и поэтому будут сохранены.
Итак, линейное программирование
возникло после второй мировой войны
и стало быстро развиваться, привлекая
внимание математиков, экономистов
и инженеров благодаря
Можно сказать, что
линейное программирование применимо
для решения математических моделей
тех процессов и систем, в основу которых
может быть положена гипотеза линейного
представления реального мира.
Линейное программирование
применяется при решении
Задача линейного
программирования (ЛП), как уже ясно
из сказанного выше, состоит в нахождении
минимума (или максимума) линейной функции
при линейных ограничениях.
Существует несколько
методов решения задач ЛП. В
данной работе будут рассмотрены
некоторые из них, в частности:
Графический метод
решения задачи ЛП;
Симплексный метод;
Решение задачи ЛП средствами
табличного процессора Excel;
3.
Понятие нелинейного
программирования
В большинстве инженерных
задач построение математической модели
не удается свести к задаче линейного
программирования.
Математические модели
в задачах проектирования реальных
объектов или технологических процессов
должны отражать реальные протекающие
в них физические и, как правило,
нелинейные процессы. Переменные этих
объектов или процессов связанны
между собой физическими
В данной работе будет
рассматриваться такой метод
решения задач НП, как метод
множителей Лагранжа.
Метод множителей Лагранжа
позволяет отыскивать максимум (или
минимум) функции при ограничениях-
4. Динамическое программирование
Динамическое программирование
представляет собой математические
аппарат, позволяющий быстро находить
оптимальное решение в случаях,
когда анализируемая ситуация не
содержит факторов неопределенности,
но имеется большое количество вариантов
поведения, приносящих различные результаты,
среди которых необходимо выбрать
наилучший. Динамическое программирование
подходит к решению некоторого класса
задач путем разложения на части,
небольшие и менее сложные
задачи. В принципе, задачи такого рода
могут быть решены путем перебора
всех возможных вариантов и выбора
среди них наилучшего, однако часто
такой перебор весьма затруднен.
В этих случаях процесс принятия
оптимального решения может быть
разбит на шаги (этапы) и исследован
с помощью метода динамического
программирования.
Решение задач методами
динамического программирования проводится
на основе сформулированного Р.Э.
Таким образом, планирование
каждого шага должно проводится с учетом
общей выгоды, получаемой по завершении
всего процесса, что и позволяет оптимизировать
конечный результат по выбранному критерию.
Вместе с тем
динамическое программирование не является
универсальным методом решения.
Практически каждая задача, решаемая
этим методом, характеризуется своими
особенностями и требует
Динамическое программирование
применяется для решения таких
задач, как: распределение дефицитных
капитальных вложений между новыми
направлениями их использования; разработка
правил управления спросом и запасами;
составление календарных планов
текущего и капитального ремонтов оборудования
и его замены; поиск кратчайших
расстояний на транспортной сети и
т.д.
Пусть процесс оптимизации
разбит на n шагов. На каждом шаге необходимо
определить два типа переменных –
переменную состояния S и переменную
управления X. Переменная S определяет,
в каких состояниях может оказаться
система на данном k-м шаге. В зависимости
от S на этом шаге можно применить
некоторые управления, которые характеризуются
переменной X. Применение управления X
на k-м шаге приносит некоторый результат
Wk(S,Xk) и переводит систему в некоторое
новое состояние S'(S,Xk). Для каждого возможного
состояния на k-м шаге среди всех возможных
управлений выбирается оптимальное управление
X*k такое, чтобы результат, который достигается
за шаги с k-го по n-й, оказался оптимальным.
Числовая характеристика этого результата
называется функцией Беллмана Fk(S) и зависит
от номера шага k и состояния системы S.
Все решения задачи
разбиваются на два этапа. На первом
этапе, который называют условной оптимизацией,
отыскиваются функция Беллмана и
оптимальные управления для всех
возможных состояний на каждом шаге,
начиная с последнего.