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

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 28.09.2017
Размер файла 143,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

9

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

КОНТРОЛЬНАЯ РАБОТА № 4

по дисциплине "Автоматизированные информационно-управляющие системы"

г. Ноябрьск 2012

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

1. Сформулировать по заданному 24-хзначному числу математическую модель вида:

где все параметры модели должны быть определены на основе таблиц 3, 4, 5 приведенных в контрольной работе №1, а также из следующего условия:

Примечание. Если a1j = 1, то следует принять a1j = 2. (Это делается для уменьшения размера таблиц, получаемых при решении данной модели.)

2. Придумать оригинальную содержательную постановку задачи, которой соответствует модель из п.1.

Примечание. Данная задача относится к классу задач распределения ресурса.

3. Найти оптимальное решение модели, сформированной в п.1, используя метод динамического программирования.

4. Построить график зависимости оптимальной прибыли от величины распределяемого ресурса.

5. Требуется графически изобразить ациклическую сеть распределения ресурса, соответствующую модели из п.1.

Примечание. Константу в правой части ограничения модели следует заменить на

1. Формулировка модели.

Исходные данные:

а11

а12

а13

а14

c1

c2

c3

c4

b1

i

1

2

3

4

3

6

9

12

-

5

8

4

5

4

5

6

4

18

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

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

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

реанимационного отделения (1) необходимо будет потратить 5 млн рублей и в будущем получить 4 млн рублей прибыли от одного комплекта оборудования;

хирургического отделения (2) необходимо будет потратить 8 млн рублей и в будущем получить 5 млн рублей прибыли от одного комплекта оборудования;

диагностического отделения (3) необходимо будет потратить 4 млн рублей и в будущем получить 6 млн рублей прибыли от одного комплекта оборудования;

акушерского отделения (4) необходимо будет потратить 5 млн рублей и в будущем получить 4 млн рублей прибыли от одного комплекта оборудования;

Решение.

Запишем рекуррентное соотношение динамического программирования:

Допустим, что мы рассматриваем вложение средств только в производство 1:

Возьмем для рассмотрения последний объект

Составляем таблицу:

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

Таблица 3. Расчет оптимального вложения средств в производство 1 (с конца), n=1.

S

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

x4 (S)

0

0

0

0

0

1

1

1

1

1

2

2

2

2

2

3

3

3

3

f4 (S)

0

0

0

0

0

4

4

4

4

4

8

8

8

8

8

12

12

12

12

Возьмем для рассмотрения третий объект

Составляем таблицу:

Таблица 4.

Расчет оптимального вложения средств в производство 2 (с конца), n=2.

S

0

1

2

3

4

x3 (S)

f3 (S)

0

0

x

x

x

x

0

0

1

0

x

x

x

x

0

0

2

0

x

x

x

x

0

0

3

0

x

x

x

x

0

0

4

0

6

x

x

x

1

6

5

4

6

x

x

x

1

6

6

4

6

x

x

x

1

6

7

4

6

x

x

x

1

6

8

4

6

12

x

x

2

12

9

4

10

12

x

x

2

12

10

8

10

12

x

x

2

12

11

8

10

12

x

x

2

12

12

8

10

12

18

x

3

18

13

8

10

16

18

x

3

18

14

8

14

16

18

x

3

18

15

12

14

16

18

x

3

18

16

12

14

16

18

24

4

24

17

12

14

16

22

24

4

24

18

12

14

20

22

24

4

24

Возьмем для рассмотрения второй объект

Составляем таблицу:

Таблица 5.

Расчет оптимального вложения средств в производство 3 (с конца), n=3.

x S

0

1

2

x2 (S)

f2 (S)

0

0

x

x

0

0

1

0

x

x

0

0

2

0

x

x

0

0

3

0

x

x

0

0

4

6

x

x

0

6

5

6

x

x

0

6

6

6

x

x

0

6

7

6

x

x

0

6

8

12

5

x

0

12

9

12

5

x

0

12

10

12

5

x

0

12

11

12

5

x

0

12

12

18

11

x

0

18

13

18

11

x

0

18

14

18

11

x

0

18

15

18

11

x

0

18

16

24

17

10

0

24

17

24

17

10

0

24

18

24

17

10

0

24

Возьмем для рассмотрения первый объект

Составляем таблицу:

Таблица 6. Расчет оптимального вложения средств в производство 4 (с конца), n=4.

X S

0

1

2

3

0

0

x

x

x

0

0

1

0

x

x

x

0

0

2

0

x

x

x

0

0

3

0

x

x

x

0

0

4

6

x

x

x

0

6

5

6

4

x

x

0

6

6

6

4

x

x

0

6

7

6

4

x

x

0

6

8

12

4

x

x

0

12

9

12

10

x

x

0

12

10

12

10

8

x

0

12

11

12

10

8

x

0

12

12

18

10

8

x

0

18

13

18

16

8

x

0

18

14

18

16

14

x

0

18

15

18

16

14

12

0

18

16

24

16

14

12

0

24

17

24

22

14

12

0

24

18

24

22

20

12

0

24

Определяем оптимальное решение. При =18 в таблице 4 видно, что 4 млн рублей наиболее оптимально потратить на приобретение оборудования для диагностического отделения, то есть . Далее , , . Общая прибыль от приобретения будет равна 24 млн рублей.

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

Изображаем ациклическую сеть распределения ресурса:

Список литературы

1. Автоматизированное управление в технических системах. Исследование операций (детерменированные методы).

2. Учебное пособие "Автоматизированное управление в технических системах", автор Одиноков В.В., 2005 г.

Размещено на Allbest.ru


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.