Динамическое программирование

Этап 4.

Этап 3.

Этап 2.

Этап 1.

 

 

y1=30	k1=5
y2=y1-2*k1=20	k2=3
y3=y2-4*k2=8	k3=4
y4=y3-k3=4	k4=3

 

соответственно  максимально количество баллов, которое  студент может набрать за отведенное время равно 39.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.  Пример задачи динамического программирования

                  Выбор состава оборудования технологической линии.

Есть технологическая  линия, то есть цепочка, последовательность операций.

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

1. Исходные данные для примера

i	1		2		3
j	1	2	1	2	1	2
	10	8	4	5	8	9
	12	8	4	6	9	9
	20	18	6	8	10	12

 

Стоимость сырья 

Расходы , связанные с использованием единицы оборудования j-го типа на i-ой операции

Производительности, соответственно, по выходу и входу и для  j-го типа оборудования, претендующего на i-ую операцию.

 

Решение:

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

N = 3 – число шагов.

 - Технологическая линия.

=  (0,0,0)

= (                   )

 

 – выбор оборудования для  i-ой операции.

U_i – область допустимых УВ на i-м шаге.

т.е.

W_i – оценка минимальной себестоимости, полученная в результате реализации i-го шага.

S – функция общего выигрыша  т. е. минимальная себестоимость .

 

                                                                                                                         (20)

 

                                - вектор – функция, описывающая переход системы из состояния в состояние   под действием УВ.

        

- вектор УВ на i-ом шаге, обеспечивающий переход системы из состояния x_i-1 в состояние x_{i ,} т.е. оптимальный выбор оборудования за N  шагов.

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

S₁( ) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления . Очевидно, что S = S₁( ), если = 0.

Запишем вектора допустимых значений

 

 

 

                                                                                                                                                Запишем вектора допустимых управляющих воздействий

 

 

 

 

Запишем вектор – функцию, описывающую переход системы из состояния                  в состояние   под действием УВ.

 

 

 

 

 

 

Запишем основное функциональное уравнение

 

                                                                                                                      (21)

 

1) Обратный проход

Для  i=3

 

 

       

                                                                                                                        (22)

                                                                                                                                        Учитывая то, что этот шаг у нас последний и следующей операции

уже не будет, а также то, что мы на обратном проходе, вместо функции

          возьмем стоимость сырья                    

при                                                                              =       

 

 

при                                                                              =                                                    

т. е.                                                         

 

Для   i=2

 

 

                                                                                                                        (23)       

 

 при                                                                                           =                                         

при                                                                                           = 

 

при                                                                                             =

 

при                                                                                            =

т. е.                         

 

Для i=1

 

 

 

 

 

при                                                                                         =   

 

при                                                                                       =

                                                                                                                          

 

 

при                                                                                         =

при                                                                                         ==

при                                                                                               =

при                                                                                                 =

при                                                                                                =

при                                                                                                   =

т. е.                                

 

2. Прямой проход

Учитывая то, что                                  и   = (0,0,0)  имеем

  i=1

 

                                       

 

                                             

 

  i=2

 

 

 

i=3                               

 

                                         

 

                                           

 

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

На  1-ую операцию назначим оборудование 2-го вида

На  2-ую операцию назначим оборудование 1-го вида

На  3-ью операцию назначим оборудование 2-го вида

Оценка минимальной  себестоимости составит 105,5.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

заключение

 

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

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

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

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

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

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

 

Список использованной литературы.

 

1. Абчук В. А. «Экономико-математические методы» -С.-П.: Союз, 1999.
2. Кузнецов Ю. Н. Математическое программирование. –М.: Наука,1976.
3. Вентцель Е. С. Исследование операций. –М.: Наука,1976.
4. Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.
5. Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,1971.
6. Вентцель Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,1988.
7. Карманов В. Т. Математическое программирование. –М.:Наука,1986.
8. Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.
9. Аоки М. Введение в методы оптимизации. –М.: Наука,1977.
10. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,1965.
11. Муну М. Математическое программирование. Теория алгоритмов. –М.: Наука,1990.