Задача о распределении средств между предприятиями.

Планируется деятельность N предприятий на очередной год. Начальные средства – So=M условных единиц. Средства x_k (k=1,2,…, N), выделенные каждому предприятию, в конце года приносят прибыль f_k(x_k). Функции f_k(x_k) заданы таблично.

Принято считать, что

1) прибыль f_k(x_k) не зависит от вложения средств в другие предприятия;

2) прибыль от каждого предприятия выражается в одних и тех же условных единицах;

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

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

Процесс можно рассматривать как N шаговый от состояния So=M, когда средства еще не распределены, до состояния S_N=0, когда все средства распределены полностью.

Переменные x_k удовлетворяют ограничениям:

Суммарная прибыль

Пример. Как распределить имеющиеся 6 миллионов рублей между проектами так, чтобы суммарная прибыль была максимальной?

Вложенная сумма (млн. руб.)	Проект 1	Проект 2	Проект 3
1	12	9	10
2	20	18	18
3	25	26	26
4	28	34	35
5	30	40	40
6	31	42	44

Решение.

В нашем примере N=3, M=6, всего четыре состояния системы: So, S₁, S₂, S₃. Построим граф состояний процесса распределения 6 млн.руб. среди трех проектов. Если точка имеет координаты (n;m), то это значит, что средства распределены между n предприятиями и осталось m условных единиц груза.

Нужно пройти от точки А(0,6), в которой все средства целы, до точки F₃(3,0), в которой все средства распределены между тремя проектами.

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

Рассмотрим состояние S₃=F₃(3,0) – конечное состояние, все средства распределены.

Рассмотрим состояние S₂ (двум проектам средства уже выделены, необходимо выделить средства третьему проекту):

1) Точка A₂(2,6) означает, что все средства целы, и, следовательно, все 6 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 44.

2) Точка B₂(2,5) означает, что осталось 5 млн. руб., и, следовательно, 5 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 40.

3) Точка C₂(2,4) означает, что осталось 4 млн. руб., и, следовательно, 4 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 35.

4) Точка D₂(2,3) означает, что осталось 3 млн. руб., и, следовательно, 3 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 26.

5) Точка E₂(2,2) означает, что осталось 2 млн. руб., и, следовательно, 2 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 18.

6) Точка G₂(2,1) означает, что осталось 1 млн. руб., и, следовательно, 1 млн. руб. нужно вложить в третий проект. Поэтому из таблицы из последнего столбца следует, что прибыль будет равна 10.

7) Точка F₂(2,0) означает, что осталось 0 млн. руб., и, следовательно, прибыль будет равна 0.

Нанесем на граф состояний условно оптимальные дуги переходов от состояния S₂ к состоянию S₃, указывая максимально возможную прибыль по третьему проекту возле соответствующих вершин.

Рассмотрим состояние S₁ (одному проекту средства уже выделены, необходимо выделить средства второму проекту):

1) Точка A₁(1,6) означает, что все средства целы, и, следовательно, во второй проект можно вложить

либо 0 млн. руб., что соответствует переходу из точки A₁(1,6) в точку A₂(2,6), при этом прибыль по второму предприятию равна нулю, а прибыль по третьему предприятию из таблицы равна 44 (она написана возле точки A₂(2,6))  0+44=44;

либо 1 млн. руб., что соответствует переходу из точки A₁(1,6) в точку B₂(2,5), при этом прибыль по второму предприятию, взятая из таблицы, равна 9, а прибыль по третьему предприятию равна 40 (она написана возле точки B₂(2,5))  9+40=49;

либо 2 млн. руб., что соответствует переходу из точки A₁(1,6) в точку C₂(2,4), при этом прибыль по второму предприятию, взятая из таблицы, равна 18, а прибыль по третьему предприятию равна 35 (она написана возле точки C₂(2,4))  18+35=53;

либо 3 млн. руб., что соответствует переходу из точки A₁(1,6) в точку D₂(2,3), при этом прибыль по второму предприятию, взятая из таблицы, равна 26, а прибыль по третьему предприятию равна 26 (она написана возле точки D₂(2,3))  26+26=52;

либо 4 млн. руб., что соответствует переходу из точки A₁(1,6) в точку E₂(2,2), при этом прибыль по второму предприятию, взятая из таблицы, равна 34, а прибыль по третьему предприятию равна 18 (она написана возле точки E₂(2,2))  34+18=52;

либо 5 млн. руб., что соответствует переходу из точки A₁(1,6) в точку G₂(2,1), при этом прибыль по второму предприятию, взятая из таблицы, равна 40, а прибыль по третьему предприятию равна 10 (она написана возле точки G₂(2,1))  40+10=50;

либо 6 млн. руб., что соответствует переходу из точки A₁(1,6) в точку F₂(2,0) при этом прибыль по второму предприятию, взятая из таблицы, равна 42, а прибыль по третьему предприятию равна 0 (она написана возле точки F₂(2,0))  42+0=42.

Итак:

0:  0+44=44

1:  9+40=49

2:  18+35=53*

3:  26+26=52

4: 34+18=52

5:  40+10=50

6:  42+0=42.

Выберем максимальную прибыль 53, отметим ее звездочкой *. Эта прибыль соответствует вложению 2 млн. руб. во второе предприятие. Следовательно, условно оптимальный переход из точки A₁(1,6) должен быть осуществлен в точку C₂(2,4), при этом максимальная прибыль, которую мы можем получить, равна 53. Отмечаем этот переход и возле вершины A₁(1,6) записываем число 53.

Рассуждаем аналогично для всех остальных вершин данного состояния.

2) Точка B₁(1,5) означает, что осталось 5 млн. руб., следовательно во второй проект можно вложить либо 0 (из точки B₁(1,5) в точку B₂(2,5)), либо 1 (из точки B₁(1,5) в точку C₂(2,4)), либо 2 (из точки B₁(1,5) в точку D₂(2,3)), либо 3 (из точки B₁(1,5) в точку E₂(2,2)), либо 4 (из точки B₁(1,5) в точку G₂(2,1)), либо 5 млн. руб.(из точки B₁(1,5) в точку F₂(2,0)). Поэтому из таблицы следует, что общая прибыль по второму и третьему проектам (по всем возможным вариантам) будет равна

0:  0+40=40

1:  9+35=44*

2: 18+26=44*

3:  26+18=44*

4:  34+10=44*

5:  40+0=40

Выберем максимальную прибыль 44. Эта прибыль соответствует вложению либо 1, либо 2, либо 3, либо 4 млн. руб. во второе предприятие. Получаем четыре условно оптимальных перехода. Нанесем на граф состояний условно оптимальные дуги переходов, указывая максимально возможную прибыль для точки B₁(1,5).

3) Точка C₁(1,4) означает, что осталось 4 млн. руб., и, следовательно, рассуждая аналогично предыдущему, получим

0: 0+35=35

1: 9+26=35

2: 18+18=36*

3: 26+10=36*

4: 34+0=34

Выберем максимальную прибыль 36. Эта прибыль соответствует вложению либо 2, либо 3 млн. руб. во второе предприятие.

4) Точка D₁(1,3) означает, что осталось 3 млн. руб.

0: 0+26=26

1: 9+18=27

2: 18+10=28*

3: 26+0=26.

Выберем максимальную прибыль 28. Эта прибыль соответствует вложению 2 млн. руб. во второе предприятие.

5) Точка E₁(1,2) означает, что осталось 2 млн. руб.

0: 0+18=18

1: 9+10=19*

2: 18+0=18.

Выберем максимальную прибыль 19. Эта прибыль соответствует вложению 1 млн. руб. во второе предприятие.

6) Точка G₁(1,1) означает, что осталось 1 млн. руб.

0: 0+10=10*

1: 9+0=9.

Выберем максимальную прибыль 10. Эта прибыль соответствует вложению 0 млн. руб. во второе предприятие.

7) Точка F₁(1,0) означает, что осталось 0 млн. руб., и, следовательно, прибыль будет равна 0.

Итак, нанесем на граф состояний условно оптимальные дуги переходов от состояния S₁ к состоянию S₂, указывая максимально возможную прибыль по второму и третьему проектам возле соответствующих вершин.

Рассмотрим начальное состояние S₀ = A(0,6) (необходимо выделить средства первому проекту):

Точка A(0,6) означает, что все средства целы, и, следовательно, в первый проект можно вложить либо 0 (из точки A(0,6) в точку A₁(1,6)), либо 1 (из точки A (0,6) в точку B₁(1,5)), либо 2 (из точки A(0,6) в точку C₁(1,4)), либо 3 (из точки A(0,6) в точку D₁(1,3)), либо 4 (из точки A(0,6) в точку E₁(1,2)), либо 5 (из точки A(0,6) в точку G₁(1,1)), либо 6 млн. руб. (из точки A(0,6) в точку F₁(1,0)). Поэтому из таблицы, используя первый столбец для первого проекта, следует, что общая прибыль по первому, второму и третьему проектам (по всем возможным вариантам) будет равна

0: 0+53=53

1: 12+44=56*

2: 20+36=56*

3: 25+28=53

4: 28+19=47

5: 30+10=40

6: 31+0=31.

Выберем максимальную прибыль 56. Эта прибыль соответствует вложению либо 1, либо 2 млн. руб. в первое предприятие – два возможных оптимальных перехода.

Заключительный этап построения оптимальной траектории: от начального состояния к конечному, идя по ранее построенным условно оптимальным дугам.

Оптимальные траектории:

1) A  B₁  C₂  F_3, X_опт=(1,1,4)

2) A  B₁  D₂  F_{3 ,} X_опт=(1,2,3)

3) A  B₁  E₂  F_3, X_опт=(1,3,2)

4) A  B₁  G₂  F_{3 ,} X_опт=(1,4,1)

5) A  C₁  E₂  F_3, X_опт=(2,2,2)

6) A  C₁  G₂  F_3, X_опт=(2,3,1)

Итак, оптимальная (максимальная) прибыль Z_max=Р_опт = 56.

Оптимальная схема вложения:

1. x₁ =ρ₁ = 1 млн. руб., x₂ =ρ₂ = 1 млн. руб, x₃ =ρ₃ = 4 млн. руб.

2. x₁ =ρ₁ = 1 млн. руб, x₂=ρ₂ = 2 млн. руб, x₃=ρ₃ = 3 млн. руб.

3. x₁ =ρ₁ = 1 млн. руб, x₂ =ρ₂ = 3 млн. руб, x₃ =ρ₃ = 2 млн. руб.

4. x₁ =ρ₁ = 1 млн. руб, x₂ =ρ₂ = 4 млн. руб, x₃ =ρ₃ = 1 млн. руб.

5. x₁ =ρ₁ = 2 млн. руб, x₂ =ρ₂ = 2 млн. руб, x₃ =ρ₃ = 2 млн. руб.

6. x₁ =ρ₁ = 2 млн. руб, x₂ =ρ₂ = 3 млн. руб, x₃ =ρ₃ = 1 млн. руб.