avangard-pressa.ru

Задача динамического программирования - Программирование

Задача.

Совет директоров фирмы рассматривает предложение по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме. Для модернизации предприятия совет директоров инвестирует средства в объеме 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 единиц третьему потребителю.