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

Рассмотрим предложенную схему на конкретной задаче о распределении средств между предприятиями.

Формулировка задачи. Планируется деятельность четырех промышленных предприятий (системы) на очередной год. Начальные средства: S₀ = 5 у.е.

Размеры вложений в каждое предприятие кратны 1 у.е. средства Х, выделенные k-му предприятию (k=1÷4) приносят в конце года прибыль f_k (х). функции f_k заданы таблично.

Таблица 1.

Предположим, что (допущения модели)

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

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

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

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

Решение. Обозначим через х_k количество средств, выделенных k-ому предприятию. Суммарная прибыль равна

f_k(х_k) – целевая функция

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

х_k = 5

х_k ≥ 0, k=1÷4

Требуется найти переменные х₁, х₂, х₃, х₄, удовлетворяющие системе ограничений и обращающие в максимум целевую функцию.

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

Схема решения задачи методом динамического программирования имеет следующий вид: процесс распределения средств S₀ = 5 у.е. можно рассматривать как четырех шаговый, номер шага совпадает с номером предприятия, переменные х₁, х₂, х₃, х₄ – управления на I, II, III, IV – шагах. S_n - конечное состояние процесса распределения равно нулю, т.к. все средства должны быть вложены в производство; S_n = 0, согласно схеме:

5 S₁=5- х₁ S₂= S₁- х₂ S₃= S₂- х₃ S₄= S₃- х₄

Уравнения состояний в данной задаче имеют вид:

S_k = S_k-1 – x_k k= 1÷4,

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

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

Условный максимум целевой функции последнего шага

k=4, S₄ = 0 => (S₃) f₄ (x₄)

и далее по шагам

k=3, (S₂) {f₃ (x₃) + (S₃)}

k=2, (S₁) {f₂ (x₂) + (S₂)}

k=1, (S₀) {f₁ (x₁) + (S₁)}

Теперь требуется последовательно решить записанные уравнения (рекуррентные соотношения Беллмана), проводя условную оптимизацию каждого шага.

Шаг IV. Из таблицы следует, что f₄(х) прибыли четвертого предприятия монотонно возрастает, поэтому все средства, оставшиеся к четвертому шагу, следует вкладывать в четвертое предприятие. При этом для возможных значений S₃ = 0, 1, …, 5 получим:

(S₃) = f₄(S₃) и (S₃) = S₃

Шаг III. Делаем все предположения относительно остатка средств S₂ к третьему шагу (т.е. после выбора x₁ и x₂). S₂ может принимать значения от 0 до 5 (например, S₂ = 0, если все средства отданы первому и второму предприятиям, или S₂ = 5, если первое и второе предприятия не получили ничего, и т.д.) В зависимости от этого выбираем 0≤ х₃ ≤ S₂, находим

S₃ = S₂ – х₃ и сравниваем для разных х₃ и при фиксированном S₂ значения суммы f(x₃) + (S₃). Для каждого S₂ наибольшее из этих значений есть (S₂) условная оптимальная прибыль, полученная при оптимальном распределении средств S₂ между третьим и четвертым предприятиями.

Оптимизация дана в таблице при k=3. Для каждого значения S₂ (S₂) и (S₂) помещены в 5 и 6 графах.

Шаг II. Для всех возможных значений S₁ значения (S₁) и (S₁) помещаются в столбцы 8 и 9. В столбце 7 первое слагаемое берется из условий задачи (f₂(х₂)), а второе из столбца 5 при S₂ = S₁ - х₂.

Шаг I. Перед первым шагом S₀ = 5 – всегда, следовательно достаточно заполнить раздел таблицы при S₀ = 5. Рассмотрим подробно: если х₁ = 0, то S₁= 5, следовательно средства распределяются между всеми предприятиями, кроме первого. Оптимальное распределение прибыли между этими тремя предприятиями f₁(0) + (5) = 0+19=19. Если х₁ = 1, то S₂= 4. Суммарная прибыль при условии, что S₂= 4 и эти средства распределены оптимально, равна f₁(1) + (4) = 8+16=24. Аналогично при

х₁ = 2, S₂= 3, f₁(2) + (3) = 10+13=23

х₁ = 3, S₂= 2, f₁(3) + (2) = 11+10=21

х₁ = 4, S₂= 1, f₁(4) + (1) = 18+0=18

сравнивая полученные значения, находим максимум (5) = 24 – мах,

= (5) = 1.

Используя уравнение связей S_k = S_k-1 – х_k, находим = S₀ - 5-1=4. В девятом столбце таблицы ()) находим (4) = 2. Далее находим = - 4-2=2. По шестому столбцу определяем () = (. Аналогично, = - 1 => () = (1 1, т.е. (1. 2, 1, 1).

Максимум суммарной прибыли равен 24 у.е. при условии, ято первому предприятию выделено 1 у.е., второму – 2 у.е., третьему и четвертому по 1 у.е.

Замечание 1: на разобранной задаче видно, что метод динамического программирования безразличен к виду и способу задания функции: f_k(x) были заданы таблично, поэтому (S) и (S) принимали дискретные значения.

Решение иллюстрирует таблица 2.

Замечание 2: альтернативой методу динамического программирования для решения подобной задачи является метод перебора. Метод динамического программирования предпочтителен, т.к. на этапе условной оптимизации отбрасываются заведомо неэффективные варианты.

Замечание 3: достоинством метода является возможность анализа решения на чувствительность к изменению S₀ и n. Проведенные расчеты можно использовать для изменившихся начального состояния S₀ и числа шагов n. Например, пусть в задачах произошло уменьшение начальных средств на 1 у.е. Для S₀ = 4 достаточно в таблицу добавить расчеты для k=1 (и не рассматривать ее для пятой строки, где S_k-1 меняется от 0 до 5). В этом случае получаем = 21 у.е. при распределении

а) = 1

= 4-1=3; (3) = 1

= 3-1=2; (2) = 1 (1, 1, 1, 1)

= 2-1=1; (1) = = 1, или

б) = 1

= 4-1=3; (3) = 2

= 3-2=1; (1) = 0 (1, 1, 0, 1)

= 1-0=1; (1) = = 1

В результате найдены два оптимальных решения. Если начальные средства увеличились, например, на 1 у.е., S₀ = 6, а функции прибыли остались прежними, то в таблице достаточно добавить раздел S₀ = 6.

Таблица 3.

Получаем Z_max = 27,

= 1 = 6-1=5

= 1 = 5-1=4 (1, 1, 0, 4)

= 0 = 4-0=4

= 4

Если принято решение распределить средства S₀ = 5 между вторым и третьим предприятиями, то задача уже решена. В разделе k=2 таблицы находим

(5) = 19, при этом

= 1 = 5-1=4 (1, 0, 4)

= 0 = 4-0=4

= 4

Наконец, если увеличилось число предприятий (число шагов), то схему можно дополнить, присоединяя шаги с номером k=0, -1, …. и т.д., расширяя таблицу по горизонтали вправо.

Замечание 4: к недостаткам метода динамического программирования по-прежнему следует отнести возникновение технических трудностей при вычислениях в случае увеличения размерности.