15:50 Динамическое программирование | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице 8.2.
Решение получаем с помощью калькулятора. I этап. Условная оптимизация. 1-ый шаг. k = 3. Предположим, что все партии в количестве x3 = 5 отданы рынку №3. В этом случае, максимальный доход, как это видно из таблицы, составит f3(u3) = 76, следовательно, F3(e3) = f3(u3)
2-ый шаг. k = 2. Определяем оптимальную стратегию при распределении партий между рынками №2, 3. При этом рекуррентное соотношение Беллмана имеет вид: F2(e2) = max(x2 ≤ e2)(f2(u2) + F3(e2-u2))
3-ый шаг. k = 1. Определяем оптимальную стратегию при распределении партий товаров между рынками №1, 2, 3. При этом рекуррентное соотношение Беллмана имеет вид: F1(e1) = max(x1 ≤ e1)(f1(u1) + F2(e1-u1))
Столбцы 1 (партии), 2 (рынок) и 3 (остаток партий) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют). В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7. Этап II. Безусловная оптимизация. Из таблицы 3-го шага имеем F*1(e0 = 5) = 127. То есть максимальный доход всей системы при количестве партий e0 = 5 равен 127. Из этой же таблицы получаем, что первому рынку следует выделить u*1(e0 = 5) = 1 (одну партию). При этом остаток партий товаров составит: e1 = e0 - u1 e1 = 5 - 1 = 4 Из таблицы 2-го шага имеем F*2(e1 = 4) = 94. То есть максимальный доход всей системы при количестве средств e1 = 4 равен 94. Из этой же таблицы получаем, что второму рынку следует выделить u*2(e1 = 4) = 3. При этом остаток партий товаров составит: e2 = e1 - u2 e2 = 4 - 3 = 1 Последнему рынку достается одна партия. Итак, партии товаров в размере 5 необходимо распределить следующим образом: 1-му рынку выделить одну партию, 2-му рынку выделить 3 партии, 3-му рынку выделить одну партию. Что обеспечит максимальный доход, равный 127. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Всего комментариев: 0 | |