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

Задача.Совет директоров фирмы рассматривает предложение по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме. Для модернизации предприятия совет директоров инвестирует средства в объеме 250 млн. р. с дискретностью 50 млн. р. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены в таблице:

f1	f2	f3	f4	xi

Первый этап: условная оптимизация.

1) k = 4.

Предположим, что все средства в количестве x₄ = 250 отданы предприятию №4. В этом случае, максимальный доход, как это видно из таблицы, составит f₄(u₄) = 80, следовательно, F₄(e₄) = f₄(u₄)

e3	u4	e4 = e3 - u4	f4(u4)	F*4(e4)	u4(e4)

 

2) k = 3.

Определяем оптимальную стратегию при распределении денежных средств между предприятиями №3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F₃(e₃) = max(x₃<= e₃)(f₃(u₃) + F₄(e₃-u₃)).

 

e2	u3	e3 = e2 - u3	f3(u3)	F*3(e2)	F2(u3,e2)	F*3(e3)	u3(e3)

 

3) k = 2.

Определяем оптимальную стратегию при распределении денежных средств между предприятиями №2, 3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F₂(e₂) = max(x₂<= e₂)(f₂(u₂) + F₃(e₂-u₂)).

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. При этом рекуррентное соотношение Беллмана имеет вид: F₁(e₁) = max(x₁<= e₁)(f₁(u₁) + F₂(e₁-u₁))

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*₁(e⁰ = 250) = 115. То есть максимальный доход всей системы при количестве средств e⁰ = 250 равен 115.

Из этой же таблицы получаем, что 1-му предприятию следует выделить u*₁(e⁰ = 250) = 100

Остаток средств составит:
e¹ = e⁰ - u¹
e¹ = 250 - 100 = 150.

Из таблицы 3-го шага имеем F*₂(e¹ = 150) = 81. То есть максимальный доход всей системы при количестве средств e¹ = 150 равен 81.

Из этой же таблицы получаем, что 2-му предприятию следует выделить u*₂(e¹ = 150) = 50.

При этом остаток средств составит:
e² = e¹ - u²
e² = 150 - 50 = 100.

Из таблицы 2-го шага имеем F*₃(e² = 100) = 55. То есть максимальный доход всей системы при количестве средств e² = 100 равен 55.

Из этой же таблицы получаем, что 3-му предприятию следует выделить u*₃(e² = 100) = 50.

При этом остаток средств составит:
e³ = e² - u³
e³ = 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 единиц третьему потребителю.