Задача динамического программирования
Задача.Совет директоров фирмы рассматривает предложение по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме. Для модернизации предприятия совет директоров инвестирует средства в объеме 250 млн. р. с дискретностью 50 млн. р. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены в таблице:
| f1 | f2 | f3 | f4 | xi |
Первый этап: условная оптимизация.
1) k = 4.
Предположим, что все средства в количестве x4 = 250 отданы предприятию №4. В этом случае, максимальный доход, как это видно из таблицы, составит f4(u4) = 80, следовательно, F4(e4) = f4(u4)
| e3 | u4 | e4 = e3 - u4 | f4(u4) | F*4(e4) | u4(e4) |
2) k = 3.
Определяем оптимальную стратегию при распределении денежных средств между предприятиями №3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F3(e3) = max(x3<= e3)(f3(u3) + F4(e3-u3)).
| e2 | u3 | e3 = e2 - u3 | f3(u3) | F*3(e2) | F2(u3,e2) | F*3(e3) | u3(e3) |
3) k = 2.
Определяем оптимальную стратегию при распределении денежных средств между предприятиями №2, 3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F2(e2) = max(x2<= e2)(f2(u2) + F3(e2-u2)).
| e1 | u2 | e2 = e1 - u2 | f2(u2) | F*2(e1) | F1(u2,e1) | F*2(e2) | u2(e2) |
4) k = 1.
Определяем оптимальную стратегию при распределении денежных средств между предприятиями №1, 2, 3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F1(e1) = max(x1<= e1)(f1(u1) + F2(e1-u1))
| e0 | u1 | e1 = e0 - u1 | f1(u1) | F*1(e0) | F0(u1,e0) | F*1(e1) | u1(e1) |
Пояснение к построению таблиц:
Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими.
Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 4-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Второй этап: безусловная оптимизация.
Из таблицы 4-го шага имеем F*1(e0 = 250) = 115. То есть максимальный доход всей системы при количестве средств e0 = 250 равен 115.
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 250) = 100
Остаток средств составит:
e1 = e0 - u1
e1 = 250 - 100 = 150.
Из таблицы 3-го шага имеем F*2(e1 = 150) = 81. То есть максимальный доход всей системы при количестве средств e1 = 150 равен 81.
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 150) = 50.
При этом остаток средств составит:
e2 = e1 - u2
e2 = 150 - 50 = 100.
Из таблицы 2-го шага имеем F*3(e2 = 100) = 55. То есть максимальный доход всей системы при количестве средств e2 = 100 равен 55.
Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e2 = 100) = 50.
При этом остаток средств составит:
e3 = e2 - u3
e3 = 100 - 50 = 50
Последнему предприятию достается 50.
Ответ: Для модернизации предприятия совету директоров, чтобы обеспечить максимальный доход, равный 115 млн. рублей, следует распределить инвестиции в размере 250 млн. рублей следующим образом:
· первому предприятию выделить 100 млн. руб.;
· второму предприятию выделить 50 млн. руб.;
· третьему предприятию выделить 50 млн. руб.;
· четвертому предприятию выделить 50 млн. руб.
Транспортная задача
Задача.Фирма имеет три магазина розничной торговли, расположенные в разных районах города (А, В, С). Поставки продукции в эти магазины осуществляются с четырех складов (1,2,3,4). Найти оптимальные распределение поставок, при котором суммарные затраты на перевозку были бы минимальными.
Решение. Данные приведены в матрице ниже:
| Номер склада | Магазины | Запасы | ||
| А | В | С | ||
| Спрос |
Проверим закрытость ТЗ (транспортной задачи):
40+20+40=30+25+15+30=100
Общий спрос равен сумме всех запасов, следовательно, ТЗ закрытая.
Произведем первоначальное распределение первоначально методом северо-западного угла и затем методом минимального элемента, чтобы увидеть разницу, как быстрее получить оптимальный план поставок.
Распределяем методом северо-западного угла. Получаем матрицу:
| V1=2 | V2=5 | V3=8 | Запас | |
| U1=0 | 30 2 | 4 | 3 | |
| U2=0 | 10 2 | 15 5 | 2 | |
| U3=-4 | 4 | 5 1 | 10 4 | |
| U4=-3 | 5 | 3 | 30 5 | |
| Спрос |
Воспользуемся следующей формулой для проверки количества занятый ячеек:
n+m-1, где:
n – количество потребителей,
m - количество поставщиков.
Применим это формулу для нашей задачи: 3+4-1=6.Вводить дополнительных нули не надо.
По заполненным клеткам ищем транспортные издержки:
T=30*2+10*2+15*5+5*1+10*4+30*5=350.
Теперь считаем потенциалы по формуле (i- производитель, j- потребитель) :
Ui+Vj=Cij.
Предполагаем, что U1=0, тогда:
| U1+V1=2; U2+V1=2; U2+V2=5; | U3+V2=1; U3+V3=4 U4+V3=5. |
Для проверки оптимальности данного плана находим оценки по незаполненным клеткам, используя формулу:
∆ij=Ui+Vj-Cij.
| Применяем данную формулу: ∆12=0+5-4= 1; ∆13=0+8-3= 5; ∆23=0+8-2= 6; | ∆31=-4+2-4= -6; ∆41=-3+2-5= -6 ∆42=-3+5-3= -1. |
Условия оптимальности не выполняются.
Произведем распределение методом минимального элемента:
| V1=2 | V2=0 | V3=2 | Запас | |
| U1=0 | 30 2 | 4 | 3 | |
| U2=0 | 2 | 5 | 25 2 | |
| U3=1 | 4 | 15 1 | 4 | |
| U4=3 | 10 5 | 5 3 | 15 5 | |
| Спрос |
Рассчитываем транспортные издержки:
T=30*2+25*2+15*5+5*3+10*5+15==265.
Как мы может заметить, сразу издержки сократились. Возможно, найден оптимальный план поставок. Проверим это, найдя потенциалы и затем оценки.
Потенциалы находим и записываем в таблицу по вышеприведенной формуле.
Затем считаем оценки, получаем:
| ∆12=0+0-4= -4; ∆13=0+2-3= -1; ∆21=0+2-2= 0; | ∆22=0+0-5= -5; ∆31=1+2-4= -1; ∆33=1+2-4= -1. |
Как мы видим, оптимальный план поставок найден, все оценки или отрицательные или равны нулю.
Ответ: Фирма должна производить шесть перевозок следующим образом, для того, чтобы затраты на транспортировку товаров были минимальны в размере 265 ден. ед.:
1. от первого поставщика – 30 единиц продукции к первому потребителю,
2. второй поставщик 25 единиц к третьему,
3. третий поставщик 15 единиц второму потребителю,
4. четвертый поставщик производит три перевозки: 10 единиц первому потребителю, 5 единиц второму, и 15 единиц третьему потребителю.
Транспортная задача
Задача.Фирма имеет три магазина розничной торговли, расположенные в разных районах города (А, В, С). Поставки продукции в эти магазины осуществляются с четырех складов (1,2,3,4). Найти оптимальные распределение поставок, при котором суммарные затраты на перевозку были бы минимальными.
Решение. Данные приведены в матрице ниже:
| Номер склада | Магазины | Запасы | ||
| А | В | С | ||
| Спрос |
Проверим закрытость ТЗ (транспортной задачи):
40+20+40=30+25+15+30=100
Общий спрос равен сумме всех запасов, следовательно, ТЗ закрытая.
Произведем первоначальное распределение первоначально методом северо-западного угла и затем методом минимального элемента, чтобы увидеть разницу, как быстрее получить оптимальный план поставок.
Распределяем методом северо-западного угла. Получаем матрицу:
| V1=2 | V2=5 | V3=8 | Запас | |
| U1=0 | 30 2 | 4 | 3 | |
| U2=0 | 10 2 | 15 5 | 2 | |
| U3=-4 | 4 | 5 1 | 10 4 | |
| U4=-3 | 5 | 3 | 30 5 | |
| Спрос |
Воспользуемся следующей формулой для проверки количества занятый ячеек:
n+m-1, где:
n – количество потребителей,
m - количество поставщиков.
Применим это формулу для нашей задачи: 3+4-1=6.Вводить дополнительных нули не надо.
По заполненным клеткам ищем транспортные издержки:
T=30*2+10*2+15*5+5*1+10*4+30*5=350.
Теперь считаем потенциалы по формуле (i- производитель, j- потребитель) :
Ui+Vj=Cij.
Предполагаем, что U1=0, тогда:
| U1+V1=2; U2+V1=2; U2+V2=5; | U3+V2=1; U3+V3=4 U4+V3=5. |
Для проверки оптимальности данного плана находим оценки по незаполненным клеткам, используя формулу:
∆ij=Ui+Vj-Cij.
| Применяем данную формулу: ∆12=0+5-4= 1; ∆13=0+8-3= 5; ∆23=0+8-2= 6; | ∆31=-4+2-4= -6; ∆41=-3+2-5= -6 ∆42=-3+5-3= -1. |
Условия оптимальности не выполняются.
Произведем распределение методом минимального элемента:
| V1=2 | V2=0 | V3=2 | Запас | |
| U1=0 | 30 2 | 4 | 3 | |
| U2=0 | 2 | 5 | 25 2 | |
| U3=1 | 4 | 15 1 | 4 | |
| U4=3 | 10 5 | 5 3 | 15 5 | |
| Спрос |
Рассчитываем транспортные издержки:
T=30*2+25*2+15*5+5*3+10*5+15==265.
Как мы может заметить, сразу издержки сократились. Возможно, найден оптимальный план поставок. Проверим это, найдя потенциалы и затем оценки.
Потенциалы находим и записываем в таблицу по вышеприведенной формуле.
Затем считаем оценки, получаем:
| ∆12=0+0-4= -4; ∆13=0+2-3= -1; ∆21=0+2-2= 0; | ∆22=0+0-5= -5; ∆31=1+2-4= -1; ∆33=1+2-4= -1. |
Как мы видим, оптимальный план поставок найден, все оценки или отрицательные или равны нулю.
Ответ: Фирма должна производить шесть перевозок следующим образом, для того, чтобы затраты на транспортировку товаров были минимальны в размере 265 ден. ед.:
5. от первого поставщика – 30 единиц продукции к первому потребителю,
6. второй поставщик 25 единиц к третьему,
7. третий поставщик 15 единиц второму потребителю,
8. четвертый поставщик производит три перевозки: 10 единиц первому потребителю, 5 единиц второму, и 15 единиц третьему потребителю.