Xreferat.com » Рефераты по информатике и программированию » Модель распределения ресурсов

Модель распределения ресурсов

Содержание


Введение

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

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

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

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

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

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

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

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

Заключение

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

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

Введение


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

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

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

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

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

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


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


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

Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния Модель распределения ресурсов в конечное состояние Модель распределения ресурсов. Предположим, что процесс управления системой можно разбить на п шагов. Пусть Модель распределения ресурсов, Модель распределения ресурсов,…, Модель распределения ресурсов— состояния системы после первого, второго,..., п-го шага. Схематически это показано на рис. 1.


Модель распределения ресурсов

Рисунок 3


Состояние Модель распределения ресурсов системы после 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— мультипликативная функция, заданная в виде Модель распределения ресурсов, то можно рассмотреть функцию Модель распределения ресурсов, которая является аддитивной.

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

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

Для единообразия формулировок (но не вычислительных процедур!) в дальнейшем мы будем говорить только о задаче максимизации, имея в виду, что если необходимо минимизировать Z, то, заменив Z на Z' = —Z перейдем к максимизации Z'.

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

Если переменные управления Модель распределения ресурсов принимают дискретные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В зависимости от числа параметров состояний (s) и числа управляющих переменных на каждом шаге (r) различают одномерные и многомерные модели ДП. Число шагов в задаче может быть либо конечным, либо бесконечным.

Динамическое программирование применяется при оптимизации как детерминированных, так и стохастических процессов.

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


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


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

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

Модель распределения ресурсов

Рисунок 3


С точки зрения интересов оптимизации только каждого ближайшего шага — выбора кратчайшего пути из данной точки в соседнюю — следует двигаться по маршруту, проходящему через точки Модель распределения ресурсов. Длина этого маршрута равна 34. Такой путь из A в B не является кратчайшим. Например, маршрут, проходящий через точки Модель распределения ресурсов, имеет меньшую длину, равную 25. Решив эту задачу, можно убедиться, что второй путь также не является оптимальным.

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

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

Использование этого принципа гарантирует, что управление, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения процесса в целом.

Так, если система в начале k-го шага находится в состоянии Модель распределения ресурсов, и мы выбираем произвольное управление Модель распределения ресурсов, то система придет в новое состояние Модель распределения ресурсов, и дальнейшие управления Модель распределения ресурсов должны выбираться оптимальными относительно состояния Модель распределения ресурсов. Последнее означает, что при этих управлениях максимизируется показатель эффективности на последующих до конца процесса шагах k+1,...,n, т. е. величина Модель распределения ресурсов. Показатель, характеризующий суммарную эффективность от данного k-го до последнего п-го шага, будем обозначать через Модель распределения ресурсов, т.е. Модель распределения ресурсов. Задача оптимизации процесса, начиная с k-го до последнего n-го шага (рис. 3), похожа на исходную при начальном состоянии системы Модель распределения ресурсов, управлении Модель распределения ресурсов и показателе эффективности Модель распределения ресурсов [аналогично (1.2)]. Выбрав оптимальное управление Модель распределения ресурсов на оставшихся п—k+l шагах, получим величину Модель распределения ресурсов, которая зависит только от Модель распределения ресурсов, т. е.


Модель распределения ресурсов. (1.4)


Назовем величину Модель распределения ресурсов условным максимумом. Если теперь мы выберем на k-м шаге некоторое произвольное управление Модель распределения ресурсов, то система придет в состояние Модель распределения ресурсов. Согласно принципу оптимальности, какое бы Модель распределения ресурсов мы ни выбрали, на последующих шагах управление Модель распределения ресурсов должно выбираться так, чтобы показатель эффективности Модель распределения ресурсов достигал максимального значения, равного Модель распределения ресурсов. Остается выбрать управление Модель распределения ресурсов. Его нельзя выбирать из условия локальной максимизации показателя эффективности на данном k-м шаге, лишь бы получить Модель распределения ресурсов. Такой подход был бы недальновидным, поскольку от выбора Модель распределения ресурсов зависит новое состояние Модель распределения ресурсов, а от последнего—максимально возможная эффективность, которая может быть достигнута в дальнейшем, т. е. величина Модель распределения ресурсов. Поэтому необходимо выбирать управление Модель распределения ресурсов так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)-го) приводило бы к общему максимуму показателя эффективности на п—k+l шагах, начиная с k-го до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:


Модель распределения ресурсов, (1.5)


получившего название основного функционального уравнения ДП, или уравнения Беллмана. Схематически соотношение (1.5) иллюстрируется на рис. 3.


Модель распределения ресурсов

Рисунок 3


Из уравнения (1.5) может быть получена функция Модель распределения ресурсов, если известна функция Модель распределения ресурсов; аналогично можно получить Модель распределения ресурсов, если найдена Модель распределения ресурсов и т. д., пока не будет определена величина Модель распределения ресурсов, представляющая по определению максимальное значение показателя эффективности процесса в целом: Модель распределения ресурсов.

Соотношения (1.5) для определения последовательности функций Модель распределения ресурсов через Модель распределения ресурсов Модель распределения ресурсовполучили название основных рекуррентных уравнений Беллмана.

Решая уравнение (1.5) для определения условного максимума показателя эффективности за n—k+l шагов, начиная с k-го, мы определяем соответствующее оптимальное управление Модель распределения ресурсов, при котором этот максимум достигается. Это управление также зависит от Модель распределения ресурсов. Будем обозначать такое управление через Модель распределения ресурсови называть условным оптимальным управлением на k-м шаге.

Основное значение уравнения (1.5), в котором реализована идея динамического программирования, заключается в том, что решение исходной задачи определения - максимума функции (1.2) n переменных Модель распределения ресурсов, Модель распределения ресурсов,…, Модель распределения ресурсов сводится к решению последовательности n задач, задаваемых соотношениями (1.5), каждое из которых является задачей максимизации функции одной переменной Модель распределения ресурсов. Эти задачи оказываются взаимосвязанными, так как в соотношении (1.5) при определении Модель распределения ресурсов учитывается найденная при решении предыдущей задачи функция Модель распределения ресурсов.

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


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


Класс задач, рассматриваемый в данной главе, имеет многочисленные практические приложения.

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

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

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


Задача 1. Имеется начальное количество средств Модель распределения ресурсовМодель распределения ресурсов, которое необходимо распределить в течение n лет между s предприятиями. Средства Модель распределения ресурсов, выделенные в k-м году i-му предприятию, приносят доход в размере Модель распределения ресурсов и к концу года возвращаются в количествеМодель распределения ресурсов. В последующем распределении доход может либо участвовать (частично или полностью), либо не участвовать.

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

Следовательно, в качестве показателя эффективности процесса распределения ресурсов за n лет принимается суммарный доход, полученный от s предприятий:


Модель распределения ресурсов. (2.1)


Количество ресурсов в начале k-го года будем характеризовать величиной Модель распределения ресурсов (параметр состояния). Управление на k-м шаге состоит в выборе переменных Модель распределения ресурсов, обозначающих ресурсы, выделяемые в k-м году i-му предприятию.

Если предположить, что доход в дальнейшем распределении не участвует, то уравнение состояния процесса имеет вид


Модель распределения ресурсов (2.2)


Если же некоторая часть дохода участвует в дальнейшем распределении в каком-нибудь году, то к правой части равенства (2.2) прибавляется соответствующая величина.

Требуется определить ns неотрицательных переменных Модель распределения ресурсов, удовлетворяющих условиям (2.2) и максимизирующих функцию (2.1).

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


Модель распределения ресурсов (2.3)


При

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: