42071

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

Лабораторная работа

Информатика, кибернетика и программирование

Средства X выделенные kому предприятию приносит в конце года прибыль . Функции заданы таблично: X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Определить какое количество средств нужно выделить каждому предприятию чтобы суммарная прибыль равная сумме прибылей полученных от каждого предприятия была наибольшей. Пусть количество средств выделенных kому предприятию. Уравнения на м шаге удовлетворяют условию: либо kому предприятию ничего не выделяем: либо не больше того что...

Русский

2013-10-27

610.5 KB

250 чел.

Лабораторная работа 4_2. Решение задачи о распределении ресурсов методом динамического программирования.

Цель работы – изучить возможности табличного процессора MS Excel для решения задачи распределения ограниченных ресурсов методом динамического программирования.

Краткие теоретические сведения

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

  1.  выбирают способ деления процесса управления на шаги;
  2.  определяют параметры состояния  и переменные управления Xk на каждом шаге;
  3.  записывают уравнения состояний;
  4.  вводят целевые функции k-ого шага и суммарную целевую функцию;
  5.  вводят в рассмотрение условные максимумы (минимумы)  и условное оптимальное управление на k-ом шаге: .
  6.  Записывают основные для вычислительной схемы ДП уравнения Беллмана для  и  по правилу:

, .

  1.  Решают последовательно уравнения Беллмана (условная оптимизация) и получают две последовательности функций  и .
  2.  После выполнения условной оптимизации получают оптимальное решение для конкретного состояния :

а)  и

б) по цепочке  оптимальное управление (решение) .

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

Условие задачи. Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства:   у.е. Размеры вложения в каждое предприятие  кратны 1 условной единице. Средства X,  выделенные k-ому предприятию (), приносит в конце года прибыль . Функции  заданы таблично:

X

f1(X)

f2(X)

f3(X)

f4(X)

1

8

6

3

4

2

10

9

4

6

3

11

11

7

8

4

12

13

11

13

5

18

15

18

16

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

Решение. Пусть  - количество средств, выделенных k-ому предприятию. Суммарная прибыль равна . Переменные X удовлетворяют ограничениям: . Требуется найти переменные, удовлетворяющие данным ограничениям и обращающие в максимум функцию Z. 

Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств  можно рассматривать как 4-шаговый, номер шага совпадает с номером предприятия; выбор переменных  – уравнения на 1, 2, 3, 4 шагах соответственно;  - конечное состояние процесса распределения – равно нулю, т.к. все средства должны быть вложены в производство, =0.

Уравнения состояний и схему распределения можно представить в виде:

   

Здесь  - параметр состояния – количество средств, оставшихся после k-ого шага, т.е. средства, которые остается распределить между оставшимися (4-k) предприятиями.

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

Уравнения Беллмана имеют вид:

  

Решение  уравнений осуществляется путем последовательной оптимизации каждого шага.

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

.

3 шаг. Делаем предположения относительно остатка средств  к 3-ему шагу:  может принимать значения  0,1,2,3,4,5 (=0, если все средства отданы 1-ому и 2-ому предприятиям и т.д.). В зависимости от этого выбираем  и сравниваем для разных  при фиксированных значениях  значения суммы . Для каждого  максимальное из этих значений есть  - условная оптимальная прибыль, полученная при оптимальном распределении средств  между 3-м и 4-м предприятиями. Полученные значения для приведены в таблице в графах 5 и 6 соответственно.

Sk-1

Xk

Sk

k=3

k=2

k=1

f3(X3)+

f2(X2)+

f1(X1)+

1

2

3

4

5

6

7

8

9

10

11

12

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

0

0+4=4

3+0=3

4

0

0+4=4

6+0=6

6

1

0+6=6

8+0=8

8

1

2

0

1

2

2

1

0

0+6=6

3+4=7

4+0=4

7

1

0+7=7

6+4=10

9+0=9

10

1

0+10=10

8+6=14

10+0=10

14

1

3

0

1

2

3

3

2

1

0

0+8=8

3+6=9

4+4=8

7+0=7

9

1

0+9=9

6+7=13

9+4=13

11+0=11

13

1

2

0+13=13

8+10=18

10+6=16

11+0=11

18

1

4

0

1

2

3

4

4

3

2

1

0

0+13=13

3+8=11

4+6=10

7+4=11

11+0=11

13

0

0+13=13

6+9=15

9+7=16

11+4=15

13+0=13

16

2

0+16=16

8+13=21

10+10=20

11+6=17

12+0=12

21

1

5

0

1

2

3

4

5

5

4

3

2

1

0

0+16=16

3+13=16

4+8=12

7+6=13

11+4=15

18+0=18

18

5

0+18=18

6+13=19

9+9=18

11+7=18

13+4=17

15+0=15

19

1

0+19=19

8+16=24

10+13=23

11+10=21

12+6=18

18+0=18

24

1

2 шаг. Условная оптимизация проведена в таблице при k=2. Для всех возможных значений  значения  и  находятся в столбцах 8 и 9 соответственно; первые слагаемые в столбце 7 – значения  взяты из условия, вторые слагаемые взяты из столбца 5 при .

1 шаг. Условная оптимизация проведена в таблице при k=1 для .

Если , то=5; прибыль, полученная от четырех предприятий при условии, что =5 средств между оставшимися тремя предприятиями будут распределены оптимально, равна.

Если , то=4; суммарная прибыль при условии, что =4 средств между оставшимися тремя предприятиями будут распределены оптимально, равна.

Аналогично, при ,  и ;

 при ,  и ;

 при ,  и ;

Сравнивая полученные значения, получим  при .

Вычисляя, получим , а по таблице в столбце 9 находим . Далее находим , а в столбце 6 . Наконец,  и . Оптимальное решение .

Ответ. Максимум суммарной прибыли равен 24 у.е. при условии, что 1-ому предприятию выделена 1 у.е.; 2-ому предприятию выделено 2 у.е.; 3-ому предприятию - 1 у.е.; 4-ому предприятию - 1 у.е.

Реализация задачи в MS Excel

  1.  Ввод исходных данных в таблицу показан на Рис.1.

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

2. Порядок заполнения ячеек таблицы:

1). В ячейку E15 введем формулу ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($C15;$B$3:$B$8);G$12+1) и скопируем формулу в диапазоне ячеек с E15 до E35.

2). В ячейку F15 введем формулу

ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($D15;$B$3:$B$8);5) и скопируем формулу в диапазон ячеек с F15 до F35.

3). В ячейку G15 введем формулу E15+F15 и скопируем формулу в диапазон: G15 - G35.

4). Находим максимальное значение для каждого состояния от 0 до 5, для этого в ячейку H15 введем формулу МАКС(G15); после ввода формулы в ячейку H16 необходимо изменить диапазон с G16 на G16:G17 и т.д. по всему столбику до ячейки H30 (Рис.2а).

3. Находим значение управления , которому соответствует максимальное значение функции , для этого в ячейку I15 введем формулу ИНДЕКС($C15:G15;ПОИСКПОЗ(H15;G15;0);1), скопируем формулу в ячейку I16 и увеличим диапазон, в результате в ячейке I16 получим: ИНДЕКС($C16:G17;ПОИСКПОЗ(H16;G16:G17;0);1). Далее скопируем формулу в ячейки I18, I21, I25, I30, постепенно увеличивая диапазон (Рис.2б)

Рис.2а. Вид рабочего листа с формулами, k=3.

Рис.2б (правая часть рабочего листа с формулами, k=3

В результате получим:

Рис.3. Результат выполнения первого шага (k=3).

4. Выделяем диапазон E15:I35, выполняем команду Копировать, устанавливаем курсор в ячейку J15 и выполняем команду Вставить.

5. Изменим формулу функции . В ячейки K15,K16,K18,K21,K25, K30 введем соответственно максимальные значения предыдущего шага, находящиеся в ячейках H15,H16,H18,H21,H25,H30. В остальные ячейки поместим значения, стоящие в этом же столбце и соответствующие предыдущим Sk.:

В ячейку K17 копируем значения ячейки К15;

в ячейки К19 и К20 – значения К16 и К17;

в К22:К24 – значения К18:К20;

в К26:К29 – значения К21:К24;

в К31:К35 – значения К25:К29;

В результате получим:

Рис.4. Результат выполнения второго шага (k=2).

6. Выделяем диапазон ячеек J15:N35, выполняем команду Копировать, устанавливаем курсор в ячейку O15, выполняем команду Вставить. В результате получаем заполненную таблицу с решением для k=1 (Рис.5)

7. Объясним полученные результаты: при . Вычисляя, получим , а по таблице в столбце 12 находим . Далее определяем , а из столбца 6 . Наконец,  и . Таким образом, оптимальное значение , а значение функции 24 у.е., что согласуется с данными, полученными вручную.

Рис.6. Результат выполнения третьего шага (k=1).

Контрольные упражнения. Варианты.

1. Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства  у.е. Размеры вложения в каждое предприятие  кратны 1 у.е. Средства X, выделенные k-ому предприятию (), приносит в конце года прибыль . Функции  заданы таблично:

X

f1(X)

f2(X)

f3(X)

f4(X)

1

2

10

21

0

2

9

11

25

20

3

10

13

29

25

4

12

14

39

30

5

20

18

49

40

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

2. Планируется деятельность трех промышленных предприятий на очередной год. Начальные средства:   у.е. Размеры вложения в каждое предприятие  кратны 1 у.е. Средства X, выделенные k-ому предприятию (), приносит в конце года прибыль . Функции  заданы таблично:

X

f1(X)

f2(X)

f3(X)

1

5

7

6

2

9

9

10

3

12

11

13

4

14

13

15

5

15

16

16

6

18

19

18

7

20

21

21

8

24

22

22

9

27

25

25

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


 

А также другие работы, которые могут Вас заинтересовать

34110. Понятие регрессии. Роль регрессии в развитии психоаналитической терапии 48 KB
  Понятие регрессии. Роль регрессии в развитии психоаналитической терапии. Процесс регрессии – как временный постоянный защитный топический ситуационный. Патологическая и нормальная регрессии их формирование в процессе развития и их значение в функционировании психического аппарата и формировании различных уровней психопатологии.
34111. Принцип психоаналитической нейтральности. Реакции аналитика на пациента: рациональные аффективные, комплиментарные, эмпатические, контрпереносные 48 KB
  Принцип психоаналитической нейтральности. В данной теме особое внимание следует уделить пониманию центрального базового значения психоаналитического понимания нейтральности. Слово НЕЙТРАЛЬНОСТЬ neutrlity и концепция ПСИХОАНАЛИТИЧЕСКОЙ НЕЙТРАЛЬНОСТИ были амбивалентными с самого момента рождения психоанализа. Приветствуемая одно время как настолько фундаментальная что принимается как данность к нейтральности тут же стали тихо относиться как мифу.
34112. Психоаналитическое понятие тревоги и ее типы 85.5 KB
  Тревога и процесс регрессии в психоаналитической ситуации. Тревога рассматривается как архаичный аффект оторвавшийся от первоначального смыслового контекста. Объективная тревога это тревога вызванная известной опасностью. Невротическая тревога вызвана неизвестной опасностью.
34113. Неспецифические аспекты психоаналитической терапии 77 KB
  В данной теме необходимо сформировать четкое представление о неспецифических формах взаимодействия аналитика и пациента. Данный раздел дает четкое представление о вспомогательных формах и методах во взаимодействии аналитика и пациента в рамках психоаналитической терапии. Если он будет это делать с неохотой аналитик может сказать что его интересуют факты. Пациента увязнувшего в неискренней похвале своих родителей можно спросить: Ваши родители действительно замечательные люди Расспрашивание для прояснения очевидности: Вместо того чтобы...
34114. Роль сновидений в психоаналитической терапии и техника работы с ними 73 KB
  Работа сновидения. Роль сновидения в работе психического аппарата. Развитие понимание сновидения и его роли в терапевтическом процессе от З. Классические подходы к пониманию сновидения его роль в общей структуре психики.
34115. Психоанализ и психоаналитическая терапия, основные принципы 67.5 KB
  Основные принципы классического психоанализа разработанного в наследие З. Основные отличия внешние – организационные и методологические основы клинического психоанализа психоаналитической терапии. Обратить особое внимание на основные принципы классического психоанализа разработанного З. Предлагаю обсудить вопрос который постоянно в той или иной форме возникает в ходе как профессиональных так и студенческих обсуждений отголоски этой дискуссии звучат и в раздающихся все чаще и чаще утверждениях о том что под брендом психоанализа скрывается...
34116. Показание и противопоказания психоаналитической терапии 62 KB
  Некоторые особенности российского пациента. Так же следует обратить особое внимание на особенности российского пациента и особенности построения терапии в зависимости от психологической конституции. Фрейд полагал что последние две силы связаны между собой и что существует некоторое соответствие внешней реальности и психологической предрасположенности самого пациента Тем самым предполагалось наличие патогенных компонентов в прошлом которые должны предопределять повышенную чувствительность по отношению к определенным обстоятельствам в...
34117. Сеттинг. Определение, взаимозависимость терапевтической задачи и сеттинга 46.5 KB
  Роль сеттинга в построение переходного пространства в рамках котрого происходит развертывание фантазий пациента и осуществляется работа с переносом и сопротивлением. Следует разобраться в ключевой роли сеттинга для формирования у пациента способности восприимать и продуцировать символическую организацию мира. Пациент лежит на кушетке или софе а психоаналитик сидит позади него оставаясь большей частью вне поля зрения пациента стараясь вмешиваться в процесс мышления пациента настолько мало насколько это возможно и не иначе как посредством...
34118. Структурные изменения, как основная цель психоанализа и психоаналитической терапии 62.5 KB
  Еще в 1894 году в работе “Невропсихозы защиты†он показывает что абсисивный симптом является компромиссом между неприемлемым сексуальным желанием защитой против удовлетворения этого желания и раскаянием или самонаказанием. Давайте попробуем понять фразу: Каждый симптом и каждая невротическая черта характера является компромиссным образованием И попробуенм в связи с этим ответить на два вопроса. Компромиссное образование является патологическим когда оно характеризуется любой комбинацией следующих черт: слишком большое ограничение...