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

    Максимизировать z=r₁m₁+r₂m₂+…+r_nm_n.

    при условии, что

    w₁m₁+w₂m₂+…+w_nm_n

W,

    m₁,m₂,…,m_n

0 и целые.

    Три элемента модели динамического программирования определяются следующим образом:

1. Этап і ставится в соответствии предмету і-го наименования, і=1,2,…n.
2. Варианты решения на этапе і описываются количеством m_i предметов і-го наименования, подлежащих загрузке. Соответствующая прибыль равна r_im_i. Значение m_i заключено в пределах от 0 до [W/w_i], где [W/w_i] – целая часть числа W/w_i.
3. Состояние x_i на этапе і выражает суммарный вес предметов, решения о погрузке которых приняты на этапах і,і+1,...n. Это определение отражает тот факт, что ограничения по весу является единственным, которое связывает n этапов вместе.

    Пусть f_i(x_i)-максимальная суммарная прибыль от этапов і,і+1,...,n при заданном состоянии x_i. Проще всего рекуррентное уравнение определяется с помощью следующей двухшаговой процедуры.

    Шаг 1. Выразим f_i(x_i) как функцию f_i+1(x_i+1) в виде

    

    где f_n+1(x_n+1)=0.

    Шаг 2. Выразим x_i+1 как функцию x_i для гарантии того, что левая часть последнего уравнения является функцией лишь x_i. По определению x_i-x_i+1 представляет собой вес, загруженный на этапе і, т.е. x_i-x_i+1=w_im_i или x_i+1=x_i-w_im_i. Следовательно, рекуррентное уравнение приобретает следующий вид:

    

 

3. Практическая часть. Задача 

      Депутат некоторого округа баллотируется на следующий срок. Денежные средства на предвыборную кампанию составляют примерно 100000 руб. Хотя комитет по переизбранию хотел бы провести кампанию во всех пяти избирательных участках округа, ограниченность денежных средств, предписывает по-другому. Приведенная ниже таблица содержит данные о числе избирателей и денежных средств, необходимых для проведения успешной кампании по каждому избирательному участку. Каждый участок может либо использовать все предназначенные деньги, либо вовсе их не использовать. Как следует распределить денежные средства? 

 

      По  условию задачи максимальная сумма  денежных средств на предвыборную кампанию не должна превышать 100000 руб., т.е. M = 100000 руб. Тогда m – необходимые средства по каждому участку, а w – число избирателей.

      Построение экономико-математической модели:

• число шагов N в данной задаче следует принять равным количеству избирательных участков T, т.е. 5;
• фазовой переменной x является суммарная масса денежных средств на предвыборную кампанию после каждого шага управления. Ограничение: x_i ≤ M;
• управляющая переменная r может быть равна либо 0 (т.е. участок вовсе не использует предназначенные денежные средства), либо 1 (участок использует все предназначенные деньги);
• функция процесса x_i=f_i(x_i-1,r_i), определяющая закон изменения состояния системы, для данной задачи представляется формулой x_i = x_i-1 + r_i∙m_i. Она имеет следующий смысл: суммарная масса денежных средств на предвыборную кампанию x_i после шага с номером i равна суммарной массе денежных средств на предвыборную кампанию на предшествующем шаге x_i-1 плюс сумма денежных средств на текущем шаге, равная r_i∙m_i;
• частный экономический эффект представлен формулой z_i=r_i∙w_i, а целевая функция Z=z₁+z₂+z₃+z₄+z₅.

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

      В данном курсовом проекте все получаемые при решении задачи таблицы приведены  сразу окончательно заполненными.

      Предварительный этап. Данный этап проводится в естественном порядке для i=1,2,3,4,5, причем заполняются только первая строка вспомогательной таблицы и четыре левых столбца основной таблицы. Заполнение второй строки вспомогательной таблицы и оставшихся столбцов основной таблицы производится на этапе условной оптимизации. B₀(x₀) выражает максимальное значение сумм частных целевых функций на шагах от 1 до 5. Эта функция вычисляется с учетом функции B₁(x₁), которая является максимальным значением сумм частных целевых функций на шагах от 2 до 5 и т.д.

      i = 1. 
 

      Вспомогательная таблица соответствует начальному условию x₀=0 и имеет вид: 

      Таблица 3.1

Вспомогательная таблица на шаге 1 

 

      Заполнение  основной таблицы проводится обычным образом. Для заданного единственного допустимого значения x₀=0 выбираются все возможные значения управления r₁ и заносятся во второй столбец таблицы. При этом r₁ может принимать только значения 1 или 0. По формулам, приведенным выше, проводится расчет соответствующих значений переменных x₁ и z₁. Они заносятся в третий и четвертый столбцы. Получается основная таблица. 

      Таблица 3.2

Основная  таблица на шаге 1

 

      i = 2.

      На  втором шаге в первую строку вспомогательной  таблицы внесем все переменные x₁, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы: 

      Таблица 3.3

Вспомогательная таблица на шаге 2

 

      Для заполнения основной таблицы будем  последовательно выбирать все допустимые значения х₁, внесенные во вспомогательную таблицу, и проводить соответствующие расчеты:

      Таблица 3.4

Основная  таблица на шаге 2

 

      Аналогичные расчеты производятся на остальных  этапах решения.

      i = 3. 
 
 

      Таблица 3.5

Вспомогательная таблица на шаге 3

 
 
 

      Таблица 3.6

Основная  таблица на шаге 3