Студопедия
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Динамического программирования .

Читайте также:
  1. I. Языки программирования
  2. Lt;variant>язык программирования высокого уровня
  3. Lt;variant>Языки программирования высокого уровня
  4. Алгоритмизация и основы программирования: А5
  5. Базовые конструкции структурного программирования
  6. Введение в психологию программирования
  7. Выбор языка и среды программирования
  8. Задача целочисленного программирования
  9. Запуск интегрированной среды программирования Турбо Паскаль

В 1803—1804 гг. была проведена реформа народного образова­ния. Россия испытывала

острую потребность в грамотных чиновниках, дипломатах, инженерах и т.д.

Усложнялось государственное управ­ление, росли промышленность и торговля,

появились пароходы и железная дорога, а образованных людей было крайне мало.

Поэто­му основная цель реформы была в том, чтобы дать возможность получить

образование сво­бодным людям из низших сословий, а затем привлечь их к

государственной службе. Все учебные заведения делились на четыре

ступени, вводилась преемственность между ними. Страна была разделена на учебные

округа, во главе которых стоял местный университет, обязанный обеспечивать

учебными программа­ми и кадрами свои училища и гимназии. Были открыты 5 новых

университетов и два привиле­гированных учебных заведения для дворян —

Царскосельский и Демидовский лицеи. Для университетов предусматривалась

автономия, были выделены большие средства для созда­ния низших звеньев

образовательной систе­мы. Но к 1816- 1817 гг. политика царизма в области

просвещения также претерпела зна­чительные изменения и оказалась в общем русле

нарастания консервативных тенденций. Проявлениями «нового курса» стали усиление

цензуры, преобразование Министерства про­свещения в Министерство народного

просве­щения и духовных дел (1817 г.), назначение министром обер-прокурора

синода князя А.Н. Голицына, гонения на университеты как центры вольнодумства и

ликвидация универ­ситетской автономии. Усилилась сословность образования: в

гимназии принимали только дворян, а мещан - только в приходские учили­ща.

 

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Основные понятия и постановка задачи

динамического программирования.

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

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

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

Оптимизационная задача математического программирования

W = f(X) → max (min) при ограничениях Φ(Х) ≤ В

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

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

Мультипликативная – это функция одного аргумента f(m), удовлетворяющая условию f(mn) = f(m)∙ f(n) для любой пары m и n. Позволяют представить зависимую переменную в виде произведения факторных переменных, обращающего его в нуль при отсутствии действия хотя бы одного фактора.

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

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

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

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

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

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

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

Динамическое программирование основывается на важных принципах оптимальности и вложения.

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

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

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

Метод динамического программирования обладает следующими положительными качествами:

- метод ДП дает возможность решать задачи, которые раньше не исследовались из-за отсутствия соответствующего математического аппарата (например, конечномерные экстремальные задачи с дискретной структурой);

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

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

Однако динамическое программирование имеет и свои недостатки. В отличие от линейного программирования, в котором симплексный метод является универсальным, в динамическом программировании такого метода не существует, который был бы пригоден для решения всех задач. Алгоритмы, используемые в рамках динамического программирования, объединены лишь общей идеей, но в каждом конкретном случае должны формироваться применительно к условиям конкретной задачи.




Дата добавления: 2014-12-15; просмотров: 179 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2025 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав