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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ ……………………………………………2

  1. Динамическое программирование
    1. Основные понятия …………………4
    2. Принципы динамического программирования. Функциональные уравнения Беллмана …………………….5
    3. Особенности задач динамического программирования……………….10
  2. Задача распределения ресурсов……………………12
    1. Общая постановка задачи ………………………….13
    2. Блок схема программы
    3. Структура алгоритма программы
    4. Результат работы программы
  3. Заключение
  4. Список используемой литературы
  5. Приложение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

Проблема распределения  ресурсов относится к разряду "вечных": ресурсы, в отличие от потребностей, всегда ограничены. Их, так или иначе, приходится распределять на различные  нужды постоянно и на всех уровнях. Примером таких задач является задача распределения ресурсов динамического программирования. Динамическое программирование является одним из наиболее эффективных методов решения подобных задач, чем и объясняется актуальность данной работы.

Целью данной работы является реализация на ЭВМ решения задачи оптимального распределения средств на расширение производства.

Задачи курсовой работы:

    1. Рассмотреть теоретические аспекты решения задач динамического программирования; рекуррентность природы задач данного типа; принципы оптимальности Беллмана.
    2. Разработка алгоритма. Блок - схемы. Структура алгоритма.
    3. Реализация на ЭВМ разработанного алгоритма на выбранном языке программирования.

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

Курсовая работа состоит  из двух частей:

    1. Теоретическая часть, где будут рассмотрены основные понятия и принципы динамического программирования, особенности задач динамического программирования, а также приведены примеры задач, относящихся к задачам такого типа.
    2. Практическая часть, в которой рассматривается общая постановка задачи распределения ресурсов, реализация на ЭВМ, примеры работы программы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1.1 Основные понятия

Динамическое программирование (иначе — динамическое планирование) — это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой. Многие экономические процессы расчленяются на шаги естественным образом. К таким процессам относятся процессы планирования и управления, развиваемые во времени. Естественным шагом в них может быть год, квартал, месяц, декада, неделя, день и т. д. Однако метод динамического программирования может использоваться при решении задач, где время вообще не фигурирует и разделение на шаги в таких задачах вводится искусственно. Поэтому «динамика» задач динамического программирования заключается в методе решения.

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

 

 

 

    1. Принципы динамического программирования. Функциональные уравнения Беллмана

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

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

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

Приведем  второй пример. Пусть прокладывается участок железнодорожного пути между  пунктами А и В. Различные варианты трассы требуют неодинаковых затрат, связанных с неоднородностью грунта, особенностями рельефа, естественными препятствиями и т. д. Требуется так провести дорогу из A в В, чтобы суммарные затраты были минимальны.

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

Таким образом, одним из условий применимости метода динамического программирования является возможность разбиения процесса оптимизации решения на ряд однотипных шагов (этапов), каждый из которых планируется  отдельно, но с учетом состояния  системы на начало этапа и последствий принятого решения. Однако, среди всех шагов существует один, который может планироваться без оглядки на будущее. Это последний шаг, поскольку за ним нет больше этапов. Он может быть изучен и спланирован сам по себе наилучшим. Отсюда получаем одну из специфических особенностей динамического программирования: всю вычислительную процедуру программирования целесообразно разворачивать от конца к началу. Раньше всех планируется последний N-й шаг, за ним (N–1)-й и т. д. Возникает вопрос, как найти оптимальное управление uN на N-м шаге, если оно определяется не только целью управления, но и состоянием системы на начало этого шага? Сделать это можно на основе предположений об ожидаемых исходах предшествующего, но еще не исследованного этапа, т. е. о значениях xN-1.

Для каждого возможного исхода хN-1 на (N – 1)-м этапе находим оптимальное управление на N-м этапе. Такой набор оптимальных управлений, зависящих от возможных исходов предыдущего этапа, называется условно-оптимальным решением (xN-1). Завершив анализ конечного этапа, рассматривают аналогичную задачу для предпоследнего этапа, требуя, чтобы функция цели достигала экстремального значения на двух последних этапах вместе. Это дает условно-оптимальное решение на предпоследнем этапе  
(xN-2) т.е. делаются всевозможные предположения о том, чем кончился предыдущий (N-2)-й шаг, и для каждого из предположений находится такое управление на (N–1)-м шаге, при котором эффект за последние два шага (из них последний уже оптимизирован) будет максимален. Тем самым мы найдем для каждого исхода (N–2)-го шага условно-оптимальное управление на (N–1)-м и условно-оптимальное значение функции цели на последних двух шагах. Проделав такой поиск условно-оптимальных управлений для каждого шага от конца к началу, найдем последовательность условно-оптимальных управлений (x0), (x1),…, (xN-1).

Условно-оптимальные  управления дают возможность найти  не условное, а просто оптимальное  управление на каждом шаге. В самом  деле, пусть начальное состояние x0 известно. Тогда, проделав процедуру движения от конца к началу, находим (х0). Так как начальное состояние x0 определяется однозначно, это оптимальное управление для первого шага. Вместе с тем находим экстремальное значение целевой функции относительно всего процесса. Зная оптимальное действие (с точки зрения всего процесса) для первого шага, выявим, к какому состоянию перейдет система в результате этого действия, т. е. найдем оптимальное состояние системы на начало второго этапа. Но для всех возможных состояний на начало второго этапа выявлены оптимальные управления. Таким образом, зная , установим оптимальное управление для второго этапа (x1) и т.д. Проделав обратное движение по условно-оптимальным управлениям от начала к концу, найдем просто оптимальные управления для всех этапов.

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

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

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

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

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

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

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

Дадим математическую формулировку принципа оптимальности. Для простоты будем считать, что  начальное x0 и конечное xT состояния системы заданы. Обозначим через z1(х0, u1) значение функции цели на первом этапе при начальном состоянии системы x0 и при управлении u1, через z2(х1,u2) – соответствующее значение функции цели только на втором этапе, ..., через 
zi(хi-1,ui) – на i-м этапе, ..., через zN(хN-1, uN) —на N-м этапе. Очевидно, что

Z = =  (1)

Надо найти  оптимальное управление u*= ( ; ;...; ), такое, что доставляет экстремум целевой функции (1) при ограничениях .

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

 

 

 

определения для подобных задач на последнем этапе, двух последних  и т. д.; 
– область определения исходной задачи. Обозначим через F1(xN-1), F2(xN-2), …, Fk(xN-k), …, FN(x0) соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т. д., на k последних и т. д., на всех N этапах.

Начинаем  с последнего этапа. Пусть хN-1 – возможные состояния системы на начало N-го этапа. Находим:

F1(xN-1) = zN(xN-1, uN). (2)

Для двух последних  этапов получаем

F2(xN-2) = (ZN-1(xN-2, uN-1) + F1(xN-1)). (3)

Аналогично:

F3(xN-3) = (ZN-2(xN-3, uN-2) + F2(xN-2)). (4)

………………………………………………….

Fk(xN-k) = (zN-k+1(xN-k, uN-k+1) + Fk-1(xN-k+1)). (5)

…………………………………………………..

FN(x0) = (z1(x0, u1) + FN-1(x1)). (6)

Выражение (6) представляет собой математическую запись принципа оптимальности. Выражение (5) – общая форма записи условно-оптимального значения функции цели для k оставшихся этапов. Выражения (2) – (6) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.

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

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

  • Рассматривается система, состояние которой на каждом шаге определяется вектором xt. Дальнейшее изменение ее состояния зависит только от данного состояния xt и не зависит от того, каким путем система пришла в это состояние. Такие процессы называются процессами без последействия.
  • На каждом шаге выбирается одно решение ut, под действием которого система переходит из предыдущего состояния xt-1 в новое хt. Это новое состояние является функцией состояния на начало интервала xt-1 и принятого в начале интервала решения ut, т. е. xt = xt(xt-1,ut).
  • Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
  • На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений .
  • Требуется найти такое допустимое управление ut для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.

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

Геометрическая  интерпретация задачи динамического  программирования состоит в следующем. Пусть n – размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой , начальное и конечное состояния системы – точками х0, , (рис. 1). Управление – это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X0 или XT, которой эти точки принадлежат.

Рисунок 1

Тогда допустимые управления переводят точки  из области Х0 в XT. Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х0 и оканчивающуюся в области ХT, для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.

    1. ЗАДАЧА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

2.1 Общая постановка задачи

  Рассмотрим применение метода динамического программирования на примере распределения средств между шестью объектами реконструкции предприятия горводоканала:

1. Центральная насосно-фильтровальная  станция;

2. Восточная насосно-фильтровальная  станция;

3. Водопроводная насосная станции  перекачки;

4. Центральная станция аэрации;

5. Восточная станция аэрации;

6. Загородная станция аэрации.

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

 

 

 

 

 

 

 

Таблица 1.1 Входные данные продуктивности объектов реконструкции

Порядковый номер объекта

Объем ресурсов, выданных на развитие объектов (тыс. грн.)

0

15

30

45

60

75

90

105

120

135

150

165

180

195

Продуктивность объектов  результате развития (тыс. м3)

1

2250

3300

3320

3330

3340

3350

3360

4400

4430

4440

4450

4460

4470

4490

2

1100

2200

3300

3350

4400

5500

7700

9900

11100

11440

11450

11500

11600

11610

3

3330

4450

4460

4470

5520

5530

5540

5550

5560

5570

5580

6600

6620

6630

4

1160

2260

3310

3360

3370

4410

4430

4440

4460

4480

5500

5510

5570

6610

5

8850

11230

22010

22090

33170

33750

44000

44010

55000

55050

55100

55200

55300

55400

6

445

547

669

881

993

1105

1117

1129

1141

1153

1165

1177

1189

2201


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

    1. Блок схема программы

Рисунок 1. Основная программа



          QtObj – количество объектов


          QtRes – количество ресурсов



effMatrix  - матрица                                        производительности объектов,


distVector – вектор выделенных              ресурсов



нет  да


 

 Шаг 1. Условная оптимизация


 

 

 


 Шаг 2. Безусловная оптимизация


 I = QtObj-1,0 формируем вектор результат



 


 

да нет


 

 

 

 

 

Рисунок 2. Ввод данных

                                                           distVector – вектор дистанций,               effMatrix = матрица производительности




 


      


 

да нет



 если все элементы матрицы введены


да  нет


если  вектор   производительности- не

отрицательный

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 3. Условная оптимизация,

формируем мартицу выхода (максимум функции  цели)


                                                               outMatrix – матрица максимума цели

                                            QtObj – количество объектов

                                           QtRes – количество ресурсов

                                                        Matrix – матрица производительности

                                                  distVect – вектор дистанций (вектор  ресурсов)








 нет да Если первое предприятие


 


 


 

 нет


 



 

 


Поиск максимума

 нет


 

 да maxItem = temp; outMatrix[i][j] = maxItem


    1. Структура алгоритма программы
      1. Ввод данных – класс DataDlg.

Переменные члены класса.

          //вектор для хранения объема  ресурсов

         std::vector<int> distVector;

 

   //матрица производительности объектов 

               int**  effMatrix;

 

          //функция  перевода строки в число

           int  StringToInt(CString);

 

          //функция  проверки корректности введенных  данных

            BOOL FillMatrix();

 

           //функция  очистки ресурсов, после закрытия  окна

            virtual BOOL DestroyWindow();

     

           //функция  инициализации диалога

              virtual BOOL OnInitDialog();

 

 

      1. Вычисление результатов – основной класс программы courseWorkDlg

Переменные члены  класса

struct Item

{

 int Value;  //значение производительности

   int MaxIndex;// максимальный индекс в векторе ресурсов

 

};

struct Result

{

int Facility;//предприятие

int  Recource;//выделенный ресурс

};

 

           Item ** outMatrix; //матрица максимума цели

             std::vector<Result> resVector; //вектор результатов

 

             void BuildOutMatrix(int **,std::vector<int>);//функция формирования матрицы цели     (условная оптимизация)

 

               afx_msg void OnBnClickedButton1();//обработчик нажатия на кнопку «Вычислить»,   который запускает процесс вычислений.

 

                virtual BOOL DestroyWindow();//очистка ресурсов программы

 

      1. Вывод результатов класс Report

Назначение данного класса – это вывод вектора результата в табличной форме.

 

2.4 Результаты работы программы

Начальный ввод данных

 

 

 

 

 

 

 

 

 

    1. Ввод данных о продуктивности объектов реконструкции
        1. Если не все поля заполнены

        1. Если введен неправильный символ

 

 

Корректный ввод данных

Показ результата

 

 

 

Пример 2.

      1. Ввод данных

Результат работы программы

 

 

 

 

Пример 3.

Начальный ввод данных

Ввод продуктивности объектов

 

 

 

Отчет

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение.

Листинг программы

DataDlg.cpp

int DataDlg::StringToInt(CString str)

{

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

return val;

}

 

// все поля заполнены ?

BOOL DataDlg::FillMatrix()

{

bool flag = true;

for (int i = 0; i < Cells.GetSize(); i ++){

for (int j = 0 ; j < Cells.GetAt(i)->Edits.GetSize(); j ++){

CString str;

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j);

 if (temp->m_hWnd != NULL){

temp->GetWindowText(str);

 if (str.IsEmpty()){

MessageBox(L"Нужно заполнить все поля", L"Ошибка", MB_ICONERROR | MB_OK);

Оптимальное распределение ресурсов методом динамического программирования 📙 Курсовая → 🆔 150221

Оптимальное распределение ресурсов методом динамического программирования 📙 Курсовая → 🆔 150221

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