Динамическое программирование табличный метод

Билеты 15-32 / 27

1. Динамическое программирование. Рекуррентные соотношения. Табличный метод.

Многие задачи практического программирования являются задачами на перебор вариантов и выбор среди этих вариантов допустимого или наилучшего по тому или иному критерию. Однако рассмотреть все варианты, в силу чрезвычайно большого их количества, зачастую не представляется возможным. Для ряда задач, сходных по формулировке с проблемами, действительно требующими полного перебора вариантов, можно найти гораздо более эффективное решение. Чаще всего в таких случаях решение сводится к нахождению решений подзадач меньшей размерности, которые запоминаются в таблице и никогда более не пересчитываются, а подзадачи большей размерности используют эти уже найденные решения. Такой метод называется динамическим программированием, еще его называют табличным методом. В общей же форме под динамическим программированием понимают процесс пошагового решения задачи оптимизации, при котором на каждом шаге из множества допустимых решений выбирается одно, которое оптимизирует заданную целевую или критериальную функцию. Как правило, связь задач и подзадач формулируется в виде некоторого “принципа оптимальности” и выражается системой уравнений (рекуррентных соотношений). Основы теории динамического программирования были заложены Р. Беллманом (Беллман Ричард. Динамическое программирование). Заметим, что слово «программирование» в приведенном названии (dynamic programming), также как и в “линейном программировании” (linear programming) не означает составление программ для компьютера. Динамическое программирование — это способ решения сложных задач путем сведения их к более простым задачам того же типа. Такой подход впервые систематически применил американский математик Ричард Беллман при решении сложных многошаговых задач оптимизации. Его идея состояла в том, что оптимальная последовательность шагов оптимальна на любом участке. Например, пусть нужно перейти из пункта А в пункт Е через один из пунктов В, С или D (числами обозначена «стоимость» маршрута): Пусть уже известны оптимальные маршруты из пунктов В, С и D в пункт Е (они обозначены сплошными линиями) и их «стоимость». Тогда для нахождения оптимального маршрута из А в Е нужно выбрать вариант, который даст минимальную стоимость по сумме двух шагов. В данном случае это маршрут А-В-Е, стоимость которого равна 25. Как видим, такие задачи решаются «с конца».

1. Архитектура универсальной ЭВМ с последовательным выполнением команд. Функциональное назначение, физические принципы действия и организация основных блоков.

Основы учения об архитектуре вычислительных машин заложил выдающийся американский математик Джон фон Нейман. Использование двоичной системы для представления чисел имеет преимущества для технической реализации, удобство и простоту выполнения в ней арифметических и логических операций. В дальнейшем ЭВМ стали обрабатывать и нечисловые виды информации – текстовую, графическую, звуковую и другие, но двоичное кодирование данных по-прежнему составляет информационную основу любого современного компьютера. Еще одной поистине революционной идеей, значение которой трудно переоценить, является предложенный Нейманом принцип «хранимой программы”. Нейман первым догадался, что программа может также храниться в виде набора нулей и единиц, причем в той же самой памяти, что и обрабатываемые ею числа. Отсутствие принципиальной разницы между программой и данными дало возможность ЭВМ самой формировать для себя программу в соответствии с результатами вычислений. Фон Нейман не только выдвинул основополагающие принципы логического устройства ЭВМ, но и предложил ее структуру, которая воспроизводилась в течение первых двух поколений ЭВМ. Основными блоками по Нейману являются устройство управления (УУ) и арифметико-логическое устройство (АЛУ) (обычно объединяемые в центральный процессор), память, внешняя память, устройства ввода и вывода. Следует отметить, что внешняя память отличается от устройств ввода и вывода тем, что данные в нее заносятся в виде, удобном компьютеру, но недоступном для непосредственного восприятия человеком. Так, накопитель на магнитных дисках относится к внешней памяти, а клавиатура – устройство ввода, дисплей и печать – устройства вывода. Устройство управления и арифметико-логическое устройство в современных компьютерах объединены в один блок – процессор, являющийся преобразователем информации, поступающей из памяти и внешних устройств (сюда относятся выборка команд из памяти, кодирование и декодирование, выполнение различных, в том числе и арифметических, операций, согласование работы узлов компьютера). Более детально функции процессора будут обсуждаться ниже. Память (ЗУ) хранит информацию (данные) и программы. Запоминающее устройство у современных компьютеров «многоярусно” и включает оперативное запоминающее устройство (ОЗУ), хранящее ту информацию, с которой компьютер работает непосредственно в данное время (исполняемая программа, часть необходимых для нее данных, некоторые управляющие программы), и внешние запоминающие устройства (ВЗУ) гораздо большей емкости, чем ОЗУ. но с существенно более медленным доступом (и значительно меньшей стоимостью в расчете на 1 байт хранимой информации). На ОЗУ и ВЗУ классификация устройств памяти не заканчивается – определенные функции выполняют и СОЗУ (сверхоперативное запоминающее устройство), и ПЗУ (постоянное запоминающее устройство), и другие подвиды компьютерной памяти. В построенной по описанной схеме ЭВМ происходит последовательное считывание команд из памяти и их выполнение. Номер (адрес) очередной ячейки памяти. из которой будет извлечена следующая команда программы, указывается специальным устройством – счетчиком команд в УУ. Его наличие также является одним из характерных признаков рассматриваемой архитектуры. Разработанные фон Нейманом основы архитектуры вычислительных устройств оказались настолько фундаментальными, что получили в литературе название «фон-неймановской архитектуры”. Подавляющее большинство вычислительных машин на сегодняшний день – фон-неймановские машины. Исключение составляют лишь отдельные разновидности систем для параллельных вычислений, в которых отсутствует счетчик команд, не реализована классическая концепция переменной и имеются другие существенные принципиальные отличия от классической модели (примерами могут служить потоковая и редукционная вычислительные машины). По-видимому, значительное отклонение от фон-неймановской архитектуры произойдет в результате развития идеи машин пятого поколения, в основе обработки информации в которых лежат не вычисления, а логические выводы.

Для продолжения скачивания необходимо пройти капчу:

Источник

5.3 Метод динамического программирования

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

Условием применимости метода является аддитивность целевой функции, т.е. возможность представления функции от переменных в виде суммы функции, каждая из которых зависит только от одной переменной:

.

К числу задач динамического программирования относятся задачи: о замене и загрузке оборудования; оптимального распределения ресурсов по этапам планирования; оптимального управления запасами; оптимального распределения капиталовложений и многие другие.

Рассмотрим модель нелинейного программирования

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

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

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

,

где – варианты условий начала-го шага.

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

Уравнение Беллмана для шагов, начиная с предпоследнего до начала процесса, имеет вид:

,

где – варианты условий начала-го шага;

–функция Беллмана, найденная на предыдущем шаге.

При динамическом программировании многошаговый процесс проходят два раза:

1) от конца к началу – находят условные оптимальные решения на каждом шаге с учетом выигрыша на всех шагах, начиная с данного до конца;

2) от начала к концу – находят оптимальные шаговые решения на всех шагах.

5.4 Применение динамического программирования для решения задач о замене оборудования и эффективного использования

Задача эффективного использования ресурсов. Имеется некоторое количество ресурса , которое можно использовать различными способами. Пусть–количестворесурса,используемое -м способом,– доход от использования ресурса-м способом ().

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

Модель оптимального использования ресурса имеет вид:

(5.13)

(5.14)

. (5.15)

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

На последнем шаге определяется функция

.

Для всех остальных шагов используется рекуррентное соотношение

, ,

здесь – количество ресурса, оставшееся для распределения к началу-го шага.

.

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

Задача 5.3 Необходимо составить план вложений денежных средств в три отделения предприятия, исходя из общей суммы средств, которая равна 250 денежным единицам.

Известны функции прибыли f_i(x_i) по каждому отделению, где x_i — средства, вкладываемые в i-е отделение (таблица 5.1). Размеры вложений ограничены: для первого отделения суммой 250 ден. ед., для второго отделения – 100 ден. ед.; для третьего — 250 ден. ед.

Найти оптимальное распределение денежных средств по отделениям, соответствующее максимуму суммарной но трем отделениям прибыли.

Таблица 5.1 – Функции прибыли по трем отделениям

Источник