Экономико математические методы и модели 3 (стр. 5 из 5)

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

2. Найти оптимальное распределение средств, обеспечивающее максимальный прирост выпуска продукции.

PЕШЕHИЕ.

1. Системой S в данном случае является предприятие из 4-х цехов, в которое вложена сумма 100.000 ед. Состояния и управления системы Sоднозначно взаимосвязаны – это способы распределения суммы между цехами. Для осуществления инвариантного погружения задачи будем считать, что вместо суммы 100.000 ед. вкладывается сумма y: 0≤у≤100.000. Состояния системы искусственно разобьем на этапы: начальный (нулевой), первый, второй и третий этапы соответственно означают, что сумма y распределяется между четырьмя цехами, тремя цехами, двумя цехами и вся сумма yвыделяется одному цеху. Нумерацию этапов удобнее проводить в обратном порядке: третий этап – m = 1,второй этап – m = 2, первый этап – m = 3, нулевой этап – m = 4. Тогда функция Беллмана, имеющая смысл максимальной прибыли при распределении суммы y между m цехами, запишется в виде:

Если при m = 1 … k–1 функция B(y, m) уже построена, то функциональное уравнение Беллмана для данной задачи принимает вид:

Пpи m= 1 дополнительно имеем:

2. При m= 1 функция Беллмана уже построена, т.е.

y	20	40	60	80	100
B(y, 1)	9	17	29	38	47

При m= 2 уравнение из функционального уравнения Беллмана имеет вид:

Так как функции

и заданы таблично, то для определения максимума функции при каждом y составляем таблицу значений этой функции:

xy	0	20	40	60	80	100	B(y, 2)
20	0 + 9	11 + 0	11	20
40	0 + 17	11 + 9	34 + 0	34	40
60	0 + 29	11 + 17	34 + 9	46 + 0	46	60
80	0 + 38	11 + 29	34 + 17	46 + 9	53 + 0	55	60
100	0 + 47	11 + 38	34 + 29	46 + 17	53 + 9	75 + 0	75	100

Подчеркнутые значения являются максимальными в строке, т.е. являются значениями функции Беллмана B(y, 2). Они выписаны в предпоследнем столбце. В последний столбец выписаны значения x, при которых достигается максимум функции

Эти значения обозначены и их можно считать управлениями. Смысл – средства, выделяемые второму цеху, при оптимальном распределении суммы y между двумя цехами.

Аналогично, при m = 3

Составляем таблицу значений функции

xy	0	20	40	60	80	100	B(y, 3)
20	0 + 11	13 + 0	13	20
40	0 + 34	13 + 11	28 + 0	34	0
60	0 + 46	13 + 34	28 + 11	37 + 0	47	20
80	0 + 55	13 + 46	28 + 34	37 + 11	49 + 0	62	40
100	0 + 75	13 + 55	28 + 46	37 + 34	49 + 11	61 + 0	75	0

Как и выше

– сумма средств, выделяемых третьему цеху, при оптимальном распределении суммы y между тремя цехами.

При m = 4

Составляем таблицу значений функции

xy	0	20	40	60	80	100	B(y, 4)
20	0 + 13	12 + 0	13	0
40	0 + 34	12 + 13	35 + 0	35	40
60	0 + 47	12 + 34	35 + 13	40 + 0	48	40
80	0 + 62	12 + 47	35 + 34	40 + 13	54 + 0	69	40
100	0 + 75	12 + 62	35 + 47	40 + 34	54 + 13	73 + 0	82	40

В двух последних столбцах этой таблицы получены значения функции Беллмана B(y, 4) и соответствующие им управления

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

y
0	0	0	0	0	0	0	0	0
20	20	9	20	11	20	13	0	13
40	40	17		34	0	34	40	35
60	60	29	60	46		47	40	48
80	80	38	60	55	40	62	40	69
100	100	47	100	75	0	75		82

С помощью таблицы функции Беллмана для данной задачи можно произвести распределение любой суммы у от 0 до 100 между k цехами 1 ≤ k ≤ 4. В клетке

стоит максимальная прибыль от этого распределения, а в клетке стоит сумма, выделяемая k-му цеху. Распределим сумму 100 между 4-мя цехами. По клетке максимально возможная прибыль равна 82. 4-му цеху следует выделить 40 тыс. $. На первые три цеха остается 60 тыс. $. По клетке 3-му цеху выделяется 20 тыс. $. На первые два цеха остается 40 тыс. $. По клетке 2-му цеху выделяется 40 тыс. $. Тогда 1-му цеху средства не выделяются.