Динамическое программирование распределение ресурсов. Решение различных практических задач динамического программирования: Оптимальное распределение ресурсов. Двумерная модель распределения ресурсов

План урока

Учебная дисциплина МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ЭКОНОМИКЕ

Тема урока Решение различных практических задач ДП с применением математических методов.

Цели урока

Развить навык решения задач динамического программирования.

Развитие качества ума, внимания, умений учебного труда студентов.

Воспитание дисциплинированности, целеустремленности студентов.

Оснащение урока конспект лекций, В.П.Агальцов «Математические методы в программировании».

Ход урока:

Организационный момент:

проверка отсутствующих, заполнение журнала.

Актуализация опорных знаний : ответы на контрольные вопросы

Какие задачи называются многошаговыми?

При помощи какого математического аппарата решаются многошаговые задачи?

Что такое оптимальное управление u*?

Каков алгоритм метода последовательных приближений в два круга?

Приведите примеры задач оптимального распределения ресурсов.

Изучение нового материала:

Классические задачи динамического программирования

• Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.

• Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.

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

• Задача о вычислении чисел Фибоначчи

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

• Задача о выборе траектории

• Задача последовательного принятия решения

• Задача об использовании рабочей силы

• Задача управления запасами

• Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

• Алгоритм Флойда - Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.

• Алгоритм Беллмана - Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

• Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

Пример: Оптимальное распределение ресурсов

Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так, чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны 8 млн. руб.)

u

Прибыль от внедрения

f4 (u )

f3 (u )

f2 (u )

f1 (u )

55

39

120

115

10 0

120

135

134

14 0

145

158

147

Решение:

Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) – ищем оптимальное решение задачи.

1 этап.

Распределяем капитал между четырьмя проектами и считаем получаемую прибыль L (i ), i = 8,16,24,32,40.

1 шаг : Денежные средства вкладываются в четвертый проект.

L (8)=55

L (16)=58

L (24)=90

L (32)=100

L (40)=140

2 шаг : Денежные средства вкладываются в четвертый и третий проекты.

u

Прибыль от внедрения

1 шаг

f3 (u )

55

39

10 0

120

14 0

145

3 шаг : Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.

u

Прибыль от внедрения

2 шаг

f 2(u )

94

108

120

135

135

175

158

175

134

214

147

2 этап:

На четвертом шаге выбираем максимальное из полученных значений прибыли L (40)=214.

И возвращаясь в обратном порядке от таблицы к таблице (от 4 шага к 1) выбираем такие значения доходов, при которых и получено значение 214.

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

1 проект – 0 млн. руб.

2 проект – 24 млн. руб.

3 проект – 8 млн. руб.

4 проект – 8 млн. руб.

Закрепление нового материала:

5. Подведение итогов урока: выводы, оценки, домашнее задание:

(2) п.5.1

Ср12: формирование и усвоение содержания теоретического материала

Подпись преподавателя

Инструкция . Выберите количество предприятий и количество строк (количество вариантов эффективного вложения), нажмите Далее (см. Пример заполнения). Если доход и остатки предприятий задан в виде функций f(x) и g(x) , задача решается через этот калькулятор .

Пример №1 . Определите оптимальный план расширения производства трех предприятий, если известна их прибыль в год при отсутствии вложений и при инвестировании 1, 2, 3 или 4 млн. Определите, при каком инвестировании будет максимальный процент прироста прибыли.

I этап. Условная оптимизация .
1-ый шаг. k = 3.

2-ый шаг. k = 2.

3-ый шаг. k = 1.

Пример №2 . Имеются 4 предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятии в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.

1. Основные понятия

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

1.2. Принцип оптимальности. Уравнение Беллмана

2. Оптимальное распределение ресурсов

2.1 Постановка задачи

2.2 Двумерная модель распределения ресурсов

2.3 Дискретная динамическая модель оптимального распределения ресурсов

2.4 Учет последействия в задачах оптимального распределения ресурсов

Заключение

Список используемых источников

Приложение 1. Листинг программы для решения задачи оптимального распределения ресурсов с заданными параметрами. Результаты работы программы

Введение

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

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

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

Как раздел математического программирования, динамическое программирование (ДП) начало развиваться в 50-х годах XX в. благодаря работам Р. Беллмана и его сотрудников. Впервые этим методом решались задачи оптимального управления запасами, затем класс задач значительно расширился. Как практический метод оптимизации, метод динамического программирования стал возможен лишь при использовании современной вычислительной техники.

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

1. Основные понятия

1.1 Модель динамического программирования

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

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

Рисунок 1

Состояние

Предполагаем впредь, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы

Равенства (1.1) получили название уравнений состояний. Функции

Варьируя управление U , получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z , зависящей от начального состояния системы

Показатель эффективности k-го шага процесса управления, который зависит от состояния

Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z- мультипликативная функция, заданная в виде

Обычно условиями процесса на управление на каждом шаге

Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлении

Динамическое программирование (ДП) – это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой.

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

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

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

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

В принятых обозначениях принцип оптимальности Беллмана можно записать в математической форме следующим образом

Равенство (3.1) называется основным функциональным уравнением динамического программирования. Для каждой конкретной задачи уравнение имеет особый вид.

Вычислительная процедура метода ДП распадается на два этапа: условную и безусловную оптимизацию.

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

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

3.1. Задача оптимального распределения ресурсов

Пусть на реконструкцию и модернизацию основного производства объединению выделяется некоторый объем материальных ресурсов Х . Имеется N предприятий, между которыми нужно распределить данный ресурс. Обозначим через
прибыль, которому приносит народному хозяйству выделениеj -му предприятию
единиц ресурса. Предполагается, что размер прибыли зависит как от выделенного количества ресурса, так и от предприятия. Причем прибыль, получаемая предприятиями измеряется в одних и тех же единицах и общая прибыль объединения состоит из прибылей отдельных предприятий. Необходимо найти оптимальный план распределения ресурсов между предприятиями, при котором общая прибыль объединения будет максимальной.

Поставленную задачу нужно рассмотреть как многошаговую.

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

Воспользуемся рекуррентным соотношением Беллмана (3.1), которое для данной задачи приводит к следующим функциональным уравнениям при
:

Здесь функция
определяет максимальную прибыль первого предприятия при выделении емуx единиц ресурса, функция
определяет максимальную прибыль первого и второго предприятий вместе при выделении имx единиц ресурса, функция
определяет максимальную прибыль первого, второго и третьего предприятий вместе при выделении имx единиц ресурса и т.д., и наконец, функция
определяет максимальную прибыль всех предприятий вместе при выделении имx единиц ресурса.

На этапе безусловной оптимизации определяется оптимальный план распределения ресурсов между предприятиями.

Пример 3.1.

Для увеличения объемов выпуска пользующейся повышенным спросом продукции четырем предприятиям производственного объединения выделены средства в размере 50 млн. руб. Каждому из предприятий может быть выделено: 0, 10, 20, 30, 40 или 50 млн. руб. При этом ежегодный прирост выпуска продукции каждым из предприятий
в зависимости от капиталовложений известен и приведен в табл. 3.1.

Таблица 3.1

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

Имеется определенное количество ресурсов s 0 , которое необходимо распределить между n хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц, квартал, полугодие, год и т.д.) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов x i (;) в деятельность каждого хозяйствующего субъекта кратны некоторой величине h. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств x i за рассматриваемый период приносит прибыль в размере f i (x i) (не зависит от вложения ресурсов в другие хозяйствующие субъекты).

Представим процесс распределения ресурсов между хозяйствующими субъектами как n-шаговый процесс управления (номер шага совпадает с условным номером хозяйствующего субъекта). Пусть s k () - параметр состояния, т.е. количество свободных средств после k-го шага для распределения между оставшимися (n - k) хозяйствующими субъектами. Тогда уравнения состояний можно записать в следующем виде:

Введем в рассмотрение функцию - условно оптимальная совокупная прибыль, полученная от k-го, (k+1) - го, …, n-го хозяйствующих субъектов, если между ними оптимальным образом распределялись ресурсы в объеме s k-1 (). Множество возможных управленческих решений относительно размера распределяемых ресурсов на k-ом шаге можно представить следующим образом: .

Тогда рекуррентные уравнения Р.Э. Беллмана (обратная схема) будут иметь вид:

Пример. Имеется определенное количество ресурсов s 0 =100, которое необходимо распределить между n=4 хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов x i (;) в деятельность каждого хозяйствующего субъекта кратны величине h=20 и заданы вектором Q. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств x i за рассматриваемый период приносит прибыль в размере f i (x i) () (не зависит от вложения ресурсов в другие хозяйствующие субъекты):

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

Решение. Составим рекуррентные уравнения Беллмана (обратную схему):

Определим условные максимумы в соответствии с (13), результаты расчетов представлены в таблице 1.

Таблица 1. Расчет условных оптимумов

По результатам условной оптимизации определим оптимальное распределение ресурсов:

Таким образом, оптимальное распределение ресурсов:

которое обеспечит наибольшую прибыль в размере 87 усл. ден. ед.

Ответ: оптимальное распределение ресурсов: , которое обеспечивает наибольшую прибыль в 87 усл. ден. ед.

Вывод

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