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

261 чел.

Лабораторная работа 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

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


 

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

28616. Подпрограмма 21.26 KB
  Функции Другой вид подпрограммыфункцияоформляется аналогично процедуре. Отличительные особенности функции: она имеет только один результат выполнения но может иметь несколько входных параметров; результат обозначается именем функции и передаётся в основную программу. Функция оформляется в следующем виде: Function имя функции формальные параметры: тип: тип значения функции; Var . Вызов функции можно делать непосредственно внутри выражения.
28617. В программе на языке FPC 12.55 KB
  Если локальное и глобальное имя совпадают то в подпрограмме локальное имя блокирует глобальное. Формат доступа к глобальному имени: имя программы . глобальное имя .
28618. Процедурные типы 15.45 KB
  Для объявления процедурного типа используется заголовок процедуры функции в котором опускается ее имя например: type Prod = Procedure a b c: Real; var d: Real; Proc2 = Procedure var a b ; РгосЗ = Procedure; Func1 = Function: String; Func2 = Function var s: String: Real; Как видно из приведенных примеров существует два процедурных типа: типпроцедура и типфункция. Вычисление и печать значений этих функций реализуются в процедуре PRINTFUNC которой в качестве параметров передаются номер позиции N на экране куда будет...
28619. Процедуры с ближним и дальним адресом вызова 21.13 KB
  Возможность создавать опережающее описание для процедур позволяет решить следующую проблему: предположим в некоторой программе Вы используете две процедуры с именами Proc1 и Proc2 причем процедура Proc1 использует вложенную процедуру Proc2 а процедура Proc2 в свою очередь использует процедуру Proc1. Поскольку Вы не можете использовать не объявленную ранее процедуру то у Вас возникает проблема связанная с необходимостью развязать зацикленные друг на друга процедуры Proc1 и Proc2. Использование директивы Forward при объявлении процедуры...
28620. Описание и вызов процедур и функций 18.23 KB
  Формат описания процедуры имеет вид: procedure имя процедуры формальные параметры; раздел описаний процедуры begin исполняемая часть процедуры end; Формат описания функции: function имя функции формальные параметры:тип результата; раздел описаний функции begin исполняемая часть функции end; Формальные параметры в заголовке процедур и функций записываются в виде: var имя праметра: имя типа и отделяются друг от друга точкой с запятой. Вызов функции в Турбо Паскаль может производиться аналогичным способом кроме того имеется возможность...
28623. Работа со строками Delphi 26.31 KB
  С помощью операции конкатенации одна строка присоединяется к другой:var S S1 S2: String;begin S:=S1S2;end; Результирующая строка S будет суммой двух слагаемых строк. Длина строки то есть количество символов в строке возвращается встроенной функцией function LengthS: String: Integer; Delphi работает со строками типа String в котором длина строки записывается в начале строки перед первым символом. То есть если:S:='Строка типа String';то S[1] символ 'С' S[2] символ 'т' последний символ в строке S[LengthS] равный 'g'....
28624. Оператор цикла for 14.7 KB
  Прежде всего это оператор цикла с параметром for. Такой тип цикла обычно применяют в тех случаях когда количество возможных повторов известно заранее. Он имеет 2 варианта написания: один для цикла с приращением и другой для цикла с уменьшением: for параметр := выражение 1 to выражение 2 do тело цикла ; for параметр := выражение 1 downto выражение 2 do тело цикла ; В первом случае с использованием цикла forto при каждом проходе цикла называемом итерацией значение параметра увеличивается на 1 а во втором fordownto...