План урока
Учебная дисциплина МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ЭКОНОМИКЕ
Тема урока Решение различных практических задач ДП с применением математических методов.
Цели урока
Развить навык решения задач динамического программирования.
Развитие качества ума, внимания, умений учебного труда студентов.
Воспитание дисциплинированности, целеустремленности студентов.
Оснащение урока конспект лекций, В.П.Агальцов «Математические методы в программировании».
Ход урока:
Организационный момент:
проверка отсутствующих, заполнение журнала.
Актуализация опорных знаний : ответы на контрольные вопросы
Какие задачи называются многошаговыми?
При помощи какого математического аппарата решаются многошаговые задачи?
Что такое оптимальное управление 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: формирование и усвоение содержания теоретического материала
Подпись преподавателя
1. Основные понятия
1.1. Модель динамического программирования
1.2. Принцип оптимальности. Уравнение Беллмана
2. Оптимальное распределение ресурсов
2.1 Постановка задачи
2.2 Двумерная модель распределения ресурсов
2.3 Дискретная динамическая модель оптимального распределения ресурсов
2.4 Учет последействия в задачах оптимального распределения ресурсов
Заключение
Список используемых источников
Приложение 1. Листинг программы для решения задачи оптимального распределения ресурсов с заданными параметрами. Результаты работы программы
Введение
На протяжении всей своей истории люди при необходимости принимать решения прибегали к сложным ритуалам. Они устраивали торжественные церемонии, приносили в жертву животных, гадали по звездам и следили за полетом птиц. Они полагались на народные приметы и старались следовать примитивным правилам, облегчающим им трудную задачу принятия решений. В настоящее время для принятия решения используют новый и, по-видимому, более научный «ритуал», основанный на применении электронно-вычислительной машины. Без современных технических средств человеческий ум, вероятно, не может учесть многочисленные и разнообразные факторы, с которыми сталкиваются при управлении предприятием, конструировании ракеты или регулировании движения транспорта. Существующие в настоящее время многочисленные математические методы оптимизации уже достаточно развиты, что позволяет эффективно использовать возможности цифровых и гибридных вычислительных машин. Одним из этих методов является математическое программирование, включающее в себя как частный случай динамическое программирование.
Большинство практических задач имеет несколько (а некоторые, возможно, даже бесконечное число) решений. Целью оптимизации является нахождение наилучшего решения среди многих потенциально возможных в соответствии с некоторым критерием эффективности или качества. Задача, допускающая лишь одно решение, не требует оптимизации. Оптимизация может быть осуществлена при помощи многих стратегий, начиная с весьма сложных аналитических и численных математических процедур и кончая разумным применением простой арифметики.
Динамическое программирование – метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные этапы (шаги). Такие операции называются многошаговыми.
Как раздел математического программирования, динамическое программирование (ДП) начало развиваться в 50-х годах XX в. благодаря работам Р. Беллмана и его сотрудников. Впервые этим методом решались задачи оптимального управления запасами, затем класс задач значительно расширился. Как практический метод оптимизации, метод динамического программирования стал возможен лишь при использовании современной вычислительной техники.
В основе метода динамического программирования лежит принцип оптимальности, сформулированный Беллманом. Этот принцип и идея включения конкретной задачи оптимизации в семейство аналогичных многошаговых задач приводят к рекуррентным соотношениям - функциональным уравнениям - относительно оптимального значения целевой функции. Их решение позволяет последовательно получить оптимальное управление для исходной задачи оптимизации.
1. Основные понятия
1.1 Модель динамического программирования
Дадим общее описание модели динамического программирования.
Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния
в конечное состояние . Предположим, что процесс управления системой можно разбить на п шагов. Пусть , ,…, - состояния системы после первого, второго,..., п -го шага. Схематически это показано на рис. 1.
Рисунок 1
Состояние
системы после k-го шага ( k = 1,2 …,n ) характеризуется параметрами , ,…, которые называются фазовыми координатами. Состояние можно изобразить точкой s-мерного пространства называемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий , ,…, , которые составляют управление системой
, где - управление на k
-м шаге, переводящее систему из состояния в состояние (рис. 1). Управление на k
-ом шаге заключается в выборе значений определенных управляющих переменных
.
Предполагаем впредь, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы
и управления на данном шаге (рис. 1). Такое свойство получило название отсутствия последействия. Обозначим эту зависимость в виде
, (1.1)
Равенства (1.1) получили название уравнений состояний. Функции
полагаем заданными.Варьируя управление U , получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z , зависящей от начального состояния системы
и от выбранного управления U : . (1.2)Показатель эффективности k-го шага процесса управления, который зависит от состояния
в начале этого шага и управления , выбранного на этом шаге, обозначим через рассматриваемой задаче пошаговой оптимизации целевая функция (1.2) должна быть аддитивной, т. е.
. (1.3)
Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z- мультипликативная функция, заданная в виде
, то можно рассмотреть функцию , которая является аддитивной.
Обычно условиями процесса на управление на каждом шаге
накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям называются допустимыми .Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлении
Метод динамического программирования позволяет с успехом решать многие экономические задачи (см., например, ). Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между предприятиями . Каждое из предприятий при вложении в него каких-то средств приносит доход, зависящий от , т. е. представляющий собой какую-то функцию Все функции заданы (разумеется, эти функции - неубывающие).
Спрашивается, как нужно распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?
Эта задача легко решается методом динамического программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие за второй - в и т. д.
Управляемая система S в данном случае - средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S - наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел при которой суммарный доход максимален:
Решим эту задачу сначала в общем, формульном виде, а потом - для конкретных числовых данных. Найдем для каждого шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш , а соответствующее ему условное оптимальное управление - средства, вкладываемые в предприятие, -
Начнем оптимизацию с последнего, шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие Поэтому условное оптимальное управление на -м шаге: отдать последнему предприятию все имеющиеся средства S, т. е.
а условный оптимальный выигрыш
Задаваясь целой гаммой значений S (располагая их достаточно тесно), мы для каждого значения S будем знать . Последний шаг оптимизирован.
Перейдем к предпоследнему, шагу. Пусть мы подошли к нему с запасом средств S. Обозначим условный оптимальный выигрыш на двух последних шагах: (который уже оптимизирован). Если мы выделим на шаге предприятию средства то на последний шаг останется Наш выигрыш на двух последних шагах будет равен
и нужно найти такое , при котором этот выигрыш максимален:
Знак означает, что берется максимальное значение по всем какие только возможны (вложить больше, чем S, мы не можем), от выражения, стоящего в фигурных скобках. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение при котором этот максимум достигается, - условное оптимальное управление на шаге.
и соответствующее ему условное оптимальное управление - то значение при котором этот максимум достигается.
Продолжая таким образом, дойдем, наконец, до предприятия Здесь нам не нужно будет варьировать значения S; мы точно знаем, что запас средств перед первым шагом равен К:
Итак, максимальный выигрыш (доход) от всех предприятий найден. Теперь остается только «прочесть рекомендации». То значение при котором достигается максимум (13.4), и есть оптимальное управление на 1-м шаге.
После того как мы вложим эти средства в 1-е предприятие, у нас их останется . «Читая» рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств: и т. д. до конца.
А теперь решим численный пример. Исходный запас средств (условных единиц), и требуется его оптимальным образом распределить между пятью предприятиями Для простоты предположим, что вкладываются только целые количества средств. Функции дохода заданы в таблице 13.1.
Таблица 13.1
В каждом столбце, начиная с какой-то суммы вложений, доходы перестают возрастать (реально это соответствует тому, что каждое предприятие способно «освоить» лишь ограниченное количество средств).
Произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств?, мы пробуем выделить на этот шаг то или другое количество средств, берем выигрыш на данном шаге по таблице 13.1, складываем с уже оптимизированным выигрышем на всех последующих шагах до конца (учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили) и находим то вложение, на котором эта сумма достигает максимума. Это вложение и есть условное оптимальное управление на данном шаге, а сам максимум - условный оптимальный выигрыш.
В таблице 13.2 даны результаты условной оптимизации по всем шагам. Таблица построена так: в первом столбце даются значения запаса средств S, с которым мы подходим к данному шагу. Далее таблица разделена на пять пар столбцов, соответственно номеру шага.
Таблица 13.2
В первом столбце каждой пары приводится значение условного оптимального управления, во втором - условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом - последнем - шаге вынужденное: выделяются все средства; на всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W за всю операцию - в данном случае он равен 5,6. В последних двух столбцах таблицы 13.2 заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно: . Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму - пять единиц, третьему - две, четвертому - ни одной, пятому - одну единицу. При этом распределении доход будет максимален и равен 5,6.
РЕФЕРАТ
Введение
Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми.
Начало развития динамического программирования относится к 50-м годам ХХ в. и связано с именем Ричарда Эрнеста Беллмана.
Если модели линейного программирования можно использовать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях, то модели динамического программирования применяются при решении задач значительно меньшего масштаба:
üпри разработке правил управления запасами;
üпри распределении инвестиционных ресурсов между альтернативными проектами;
üпри составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены и т.п.
1. Общая постановка задачи динамического программирования
динамический беллман уравнение программирование
Рассматривается управляемый процесс, например, процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования и т.п. В результате управления система (объект управления) S переводится из начального состояния s0 в состояние sn. Пусть, управление можно разбить на n шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управленческих решений.
Обозначим через Xk управленческое решение на k-м шаге (k=1, 2, …, n). Переменные Xk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Xk может быть числом, точкой в n-мерном пространстве или качественным признаком).
Пусть X=(X1, X2, …, Xn) - управление, переводящее систему S из состояния s0 в состояние sn. Обозначим через sk состояние системы (характеризуемое определенным набором параметров и конкретных их значений) после k-го шага управления. Причем состояние системы sk в конце k-го шага зависит только от предшествующего состояния sk-1 и управленческого решения на k-ом шаге Xk (т.е. не зависит напрямую от предшествующих состояний и управленческих решений). Данное требование называется «отсутствием последствия» и может быть выражено следующими уравнениями состояний:
Таким образом, получаем последовательность состояний s0, s1, …, sk-1, sk, …, sn-1, sn. Тогда n-шаговый управленческий процесс схематично можно изобразить следующим образом:
Пусть показатель эффективности k-го шага выражается некоторой функцией:
а эффективность всего рассматриваемого многошагового процесса следующей аддитивной функцией:
Тогда задача пошаговой оптимизации (задача динамического программирования) формулируется следующим образом: определить такое допустимое управление Х, переводящее систему S из состояния s0 в состояние sn, при котором целевая функция Z принимает наибольшее (наименьшее) значение.
Задача динамического программирования обладает следующими особенностями:
Задача оптимизации интерпретируется как n-шаговый процесс управления.
Целевая функция равна сумме целевых функций каждого шага.
Выбор управления на k-ом шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (отсутствие обратной связи).
Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления Xk («отсутствие последствия»).
На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние sk - от конечного числа параметров.
2. Принцип оптимальности и уравнения Беллмана
Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):
Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Р.Э. Беллманом были сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.
Рассмотрим общую задачу динамического программирования, приведенную выше. На каждом шаге кроме последнего для любого состояния системы sk-1 управленческое решение Xk необходимо выбирать «с оглядкой», так как этот выбор влияет на последующее состояние системы sk.
На последнем шаге исходя из состояния системы sn-1 управленческое решение Xn можно планировать локально-оптимально, т.е. исходя только из соображений этого шага.
Рассмотрим последний n-й шаг:
sn-1 - состояние системы к началу n-го шага;
sn - конечное состояние системы;
Xn - управление на n-ом шаге;
fn(sn-1, Xn) - целевая функция (выигрыш) n-го шага.
Согласно принципу оптимальности, Xn нужно выбирать таким образом, чтобы для любых состояний системы sn-1 получить оптимум целевой функции на этом шаге.
Обозначим через оптимум (для определенности примем максимум) целевой функции - показатель эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии sn-1, а на последнем шаге управление было оптимальным.
называют условным максимумом целевой функции на n-ом шаге, и определяют по следующей формуле:
Максимизация ведется по всем допустимым управлениям Xn.
Решение Xn, при котором достигается, также зависит от sn-1 и называется условным оптимальным решением на n-ом шаге. Обозначим его через.
Решив одномерную задачу локальной оптимизации по уравнению (5), определим для всех возможных состояний sn-1 две функции и.
Рассмотрим двухшаговую задачу: присоединим к n-му шагу (n-1) - й.
Для любых состояний sn-2, произвольных управленческих решений Xn-1 и оптимальном управлении на n-ом шаге значение целевой функции на двух последних шагах вычисляется по формуле:
Согласно принципу оптимальности Беллмана для любых sn-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (n-ом) шаге приводило бы к оптимуму целевой функции на двух последних шагах. Следовательно, необходимо отыскать оптимум выражения (6) по всем допустимым управленческим решениям Xn-1:
Называют условным максимумом целевой функции при оптимальном управлении на двух последних шагах. Необходимо отметить, что выражение в фигурных скобках в формуле (6), зависит только от sn-2 и Xn-1, так как sn-1 можно найти из уравнения состояний (1) при:
Соответствующее управление Xn-1 на (n-1) - ом шаге обозначается через и называют условным оптимальным управлением на (n-1) - ом.
Аналогично определяются условные оптимумы целевой функции при оптимальном управлении на (n-k+1) шагах, начиная с k-го до конца, при условии, что к началу k-го шага система находилась в состоянии sk-1:
Управление Xk на k-ом шаге, при котором достигается максимум по (8), обозначается и называется условным оптимальным управлением на k-ом шаге.
Уравнения (5) и (8) называют рекуррентными уравнения Беллмана (обратная схема). Процесс решения данных уравнений называют условной оптимизацией.
В результате условной оптимизации получаются две последовательности:
, …, - условные максимумы целевой функции на последнем, двух последних, …, на n шагах;
, …, - условные оптимальные управления на n-ом, (n-1) - ом, …, на 1-ом шагах.
Используя данные последовательности, можно найти решение задачи динамического программирования при данных n и s0:
В результате получаем оптимальное решение задачи динамического программирования: .
Аналогично рассуждая, можно выстроить и прямую схему условной оптимизации:
Оптимальное решение задачи в данном случае находится по следующей схеме:
Таким образом, построение модели динамического программирования и решение задачи на ее основе в общем виде можно представить в виде следующих этапов:
Выбирают способ деления процесса управления на шаги.
Определяют параметры состояния sk и переменные управления Xk на каждом шаге, записывают уравнения состояний.
3. Вводят целевые функции k-ого шага и суммарную целевую функцию, а также условные оптимумы и условное оптимальное управление на k-ом шаге ().
Записывают в соответствии с обратной или прямой схемой рекуррентные уравнения Беллмана и после выполнения условной оптимизации получают две последовательности: {} и {}.
Определяют оптимальное значение целевой функции и оптимальное решение.
3. Задача распределения ресурсов
Имеется определенное количество ресурсов s0, которое необходимо распределить между n хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц, квартал, полугодие, год и т.д.) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов xi (;) в деятельность каждого хозяйствующего субъекта кратны некоторой величине h. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств xi за рассматриваемый период приносит прибыль в размере fi(xi) (не зависит от вложения ресурсов в другие хозяйствующие субъекты).
Представим процесс распределения ресурсов между хозяйствующими субъектами как n-шаговый процесс управления (номер шага совпадает с условным номером хозяйствующего субъекта). Пусть sk () - параметр состояния, т.е. количество свободных средств после k-го шага для распределения между оставшимися (n - k) хозяйствующими субъектами. Тогда уравнения состояний можно записать в следующем виде:
Введем в рассмотрение функцию - условно оптимальная совокупная прибыль, полученная от k-го, (k+1) - го, …, n-го хозяйствующих субъектов, если между ними оптимальным образом распределялись ресурсы в объеме sk-1 (). Множество возможных управленческих решений относительно размера распределяемых ресурсов на k-ом шаге можно представить следующим образом: .
Тогда рекуррентные уравнения Р.Э. Беллмана (обратная схема) будут иметь вид:
Пример. Имеется определенное количество ресурсов s0=100, которое необходимо распределить между n=4 хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов xi (;) в деятельность каждого хозяйствующего субъекта кратны величине h=20 и заданы вектором Q. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств xi за рассматриваемый период приносит прибыль в размере fi(xi) () (не зависит от вложения ресурсов в другие хозяйствующие субъекты):
Необходимо определить, какой объем ресурсов нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
Решение. Составим рекуррентные уравнения Беллмана (обратную схему):
Определим условные максимумы в соответствии с (13), результаты расчетов представлены в таблице 1.
Таблица 1. Расчет условных оптимумов
sk-1xkskk=3k=2k=1123456789101112000000000000200200+20=20 22 200+22=22 2200+22=22 22020022+0=22 17+0=1714+0=14400400+33=33 42 200+42=42 4200+42=42 420202022+20=42 17+22=3914+22=3640021+0=2120+0=2026+0=26600600+46=46 55 200+55=55 59 20 0+59=59 590204022+33=5517+42=59 14+42=56402021+20=4120+22=4226+22=4860037+0=3732+0=3235+0=35800800+30=30 68 200+68=68 72 200+72=72 73 20206022+46=6817+55=7214+59=73 404021+33=5420+42=6426+42=68602037+20=5732+22=5435+22=5780067+0=6761+0=6152+0=5210001000+42=42 87 800+87=87 8700+87=87 870208022+30=5217+68=8514+72=86406021+46=6720+55=7526+59=85604037+33=7032+42=7435+42=77802067+20=87 61+22=8352+22=74100058+0=5872+0=7261+0=61По результатам условной оптимизации определим оптимальное распределение ресурсов:
Таким образом, оптимальное распределение ресурсов:
которое обеспечит наибольшую прибыль в размере 87 усл. ден. ед.
Ответ: оптимальное распределение ресурсов: , которое обеспечивает наибольшую прибыль в 87 усл. ден. ед.
Вывод
Динамическое программирование - это область математического программирования, включающая совокупность приемов и средств для нахождения оптимального решения, а также оптимизации каждого шага в системе и выработке стратегии управления, то есть процесс управления можно представить, как многошаговый процесс. Динамическое программирование, используя поэтапное планирование, позволяет не только упростить решение задачи, но и решить те из них, которым нельзя применить методы математического анализа. Упрощение решения достигается за счет значительного уменьшения количества исследуемых вариантов, так как вместо того, чтобы один раз решать сложную многовариантную задачу, метод поэтапного планирования предполагает многократное решение относительно простых задач. Планируя поэтапный процесс, исходят из интересов всего процесса в целом, т.е. при принятии решения на отдельном этапе всегда необходимо иметь в виду конечную цель. Однако динамическое программирование имеет и свои недостатки. В отличие от линейного программирования, в котором симплексный метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения. Недостаток динамического программирования заключается также в трудоемкости решения многомерных задач. Задача динамического программирования должна удовлетворять два условия. Первое условие обычно называют условием отсутствия последействия, а второе - условием аддитивности целевой функции задачи. На практике встречаются такие задачи планирования, в которых заметную роль играют случайные факторы, влияющие как на состояние системы, так и на выигрыш. Существует разница между детерминированной и стохастической задачами динамического программирования. В детерминированной задаче оптимальное управление является единственным и указывается заранее как жесткая программа действий. В стохастической задаче оптимальное управление является случайным и выбирается в ходе самого процесса в зависимости от случайно сложившейся ситуации. В детерминированной схеме, проходя процесс по этапам от конца к началу, тоже находится на каждом этапе целый ряд условных оптимальных управлений, но из всех этих управлений, в конечном счете осуществлялось только одно. В стохастической схеме это не так. Каждое из условных оптимальных управлений может оказаться фактически осуществленным, если предшествующий ход случайного процесса приведет систему в соответствующее состояние. Принцип оптимальности является основой поэтапного решения задач динамического программирования. Типичными представителями экономических задач динамического программирования являются так называемые задачи производства и хранения, задачи распределения капиталовложений, задачи календарного производственного планирования и другие. Задачи динамического программирования применяются в планировании деятельности предприятия с учетом изменения потребности в продукции во времени. В оптимальном распределении ресурсов между предприятиями в направлении или во времени. Описание характеристик динамического программирования и типов задач, которые могут быть сформулированы в его рамках, по необходимости должно быть очень общим и несколько неопределенным, так как существует необозримое множество различных задач, укладывающихся в схему динамического программирования. Только изучение большого числа примеров дает отчетливое понимание структуры динамического программирования.
Список литературы
- Экономико-математические модели и методы. Линейное программирование: Учебное пособие для студентов экономических специальностей / Составители: Смирнов Ю.Н., Шибанова Е.В., Набережные Челны: Изд-во КамПИ, 2004, 81 с.
- Исследование операций в экономике: Учебн. пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2000. - 407 с.
- Кузнецов А.В. и др. Высшая математика: Мат. программирование: Учеб./А.В. Кузнецов, В.А. Сакович, Н.И. Холод; Под общ. ред. А.В. Кузнецова. - Мн.: Высш. шк., 1994. - 286 с.: ил.
Репетиторство
Нужна помощь по изучению какой-либы темы?
Наши специалисты проконсультируют или окажут репетиторские услуги по интересующей вас тематике.
Отправь заявку
с указанием темы прямо сейчас, чтобы узнать о возможности получения консультации.
Такого рода задачи основаны на функции Беллмана и при решении используется метод обратной прогонки (см. Типовые задания). Также можно воспользоваться сервисом Процедура прямой прогонки .
Инструкция . Выберите количество предприятий и количество строк (количество вариантов эффективного вложения), нажмите Далее (см. Пример заполнения). Если доход и остатки предприятий задан в виде функций f(x) и g(x) , задача решается через этот калькулятор .
Пример №1 . Определите оптимальный план расширения производства трех предприятий, если известна их прибыль в год при отсутствии вложений и при инвестировании 1, 2, 3 или 4 млн. Определите, при каком инвестировании будет максимальный процент прироста прибыли.
| f1 | f2 | f3 | x i |
| 40 | 30 | 35 | 0 |
| 90 | 110 | 95 | 1 |
| 395 | 385 | 270 | 2 |
| 440 | 470 | 630 | 3 |
| 620 | 740 | 700 | 4 |
I этап. Условная оптимизация
.
1-ый шаг. k = 3.
| e 2 | u 3 | e 3 = e 2 - u 3 | f 3 (u 3) | F* 3 (e 3) | u 3 (e 3) |
| 1 | 0 | 1 | 35 | ||
| 1 | 0 | 95 | 95 | 1 | |
| 2 | 0 | 2 | 35 | ||
| 1 | 1 | 95 | |||
| 2 | 0 | 270 | 270 | 2 | |
| 3 | 0 | 3 | 35 | ||
| 1 | 2 | 95 | |||
| 2 | 1 | 270 | |||
| 3 | 0 | 630 | 630 | 3 | |
| 4 | 0 | 4 | 35 | ||
| 1 | 3 | 95 | |||
| 2 | 2 | 270 | |||
| 3 | 1 | 630 | |||
| 4 | 0 | 700 | 700 | 4 |
2-ый шаг. k = 2.
| e 1 | u 2 | e 2 = e 1 - u 2 | f 2 (u 2) | F* 2 (e 1) | F 1 (u 2 ,e 1) | F* 2 (e 2) | u 2 (e 2) |
| 1 | 0 | 1 | 30 | 95 | 125 | 125 | 0 |
| 1 | 0 | 110 | 0 | 110 | |||
| 2 | 0 | 2 | 30 | 270 | 300 | ||
| 1 | 1 | 110 | 95 | 205 | |||
| 2 | 0 | 385 | 0 | 385 | 385 | 2 | |
| 3 | 0 | 3 | 30 | 630 | 660 | 660 | 0 |
| 1 | 2 | 110 | 270 | 380 | |||
| 2 | 1 | 385 | 95 | 480 | |||
| 3 | 0 | 470 | 0 | 470 | |||
| 4 | 0 | 4 | 30 | 700 | 730 | ||
| 1 | 3 | 110 | 630 | 740 | 740 | 1 | |
| 2 | 2 | 385 | 270 | 655 | |||
| 3 | 1 | 470 | 95 | 565 | |||
| 4 | 0 | 740 | 0 | 740 |
3-ый шаг. k = 1.
| e 0 | u 1 | e 1 = e 0 - u 1 | f 1 (u 1) | F* 1 (e 0) | F 0 (u 1 ,e 0) | F* 1 (e 1) | u 1 (e 1) |
| 1 | 0 | 1 | 40 | 125 | 165 | 165 | 0 |
| 1 | 0 | 90 | 0 | 90 | |||
| 2 | 0 | 2 | 40 | 385 | 425 | 425 | 0 |
| 1 | 1 | 90 | 125 | 215 | |||
| 2 | 0 | 395 | 0 | 395 | |||
| 3 | 0 | 3 | 40 | 660 | 700 | 700 | 0 |
| 1 | 2 | 90 | 385 | 475 | |||
| 2 | 1 | 395 | 125 | 520 | |||
| 3 | 0 | 440 | 0 | 440 | |||
| 4 | 0 | 4 | 40 | 740 | 780 | 780 | 0 |
| 1 | 3 | 90 | 660 | 750 | |||
| 2 | 2 | 395 | 385 | 780 | |||
| 3 | 1 | 440 | 125 | 565 | |||
| 4 | 0 | 620 | 0 | 620 |
Примечание : Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация .
Из таблицы 3-го шага имеем F* 1 (e 0 = 4 млн.руб.) = 780 тыс.руб., то есть максимальная прибыль от инвестирования e 0 = 4 млн.руб. равна 780 тыс.руб.
Из этой же таблицы получаем, что первому предприятию следует выделить u* 1 (e 0 = 4 млн.руб.) = 0 млн.руб.
При этом остаток средств составит: e 1 = e 0 - u 1 , e 1 = 4 - 0 = 4 млн.руб.
Из таблицы 2-го шага имеем F* 2 (e 1 = 4 млн.руб.) = 740 тыс.руб., т.е. максимальная прибыль при e 1 = 4 млн.руб. равна 740 тыс.руб.
Из этой же таблицы получаем, что второму предприятию следует выделить u* 2 (e 1 = 4 млн.руб.) = 1 млн.руб.
При этом остаток средств составит: e 2 = e 1 - u 2 , e 2 = 4 - 1 = 3 млн.руб.
Последнему предприятию достается 3 млн.руб. Итак, инвестиции в размере 4 млн.руб. необходимо распределить следующим образом: первому предприятию ничего не выделять, второму предприятию выделить 1 млн.руб., третьему предприятию выделить 3 млн.руб., что обеспечит максимальную прибыль, равную 780 тыс.руб.
Пример №2 . Имеются 4 предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятии в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.