Фирма, в состав которой входит три предприятия, принимает решение о комплексной реконструкции этих предприятий. В следующей таблице указаны 4 возможных решения по каждому предприятию, затраты ci на реализацию таких решений и чистая прибыль Ri как результат принятого решения (в млн. руб.)
1-е предприятие 2-е предприятие 3-е предприятие
с1 R1 c2 R2 c3 R3
Оставляем в прежнем виде 0 0 0 0 0 0
Малая механизация 2 9 1 3 7 9
Частичная модернизация 7 14 5 16 12 13
Полная реконструкция 14 28 12 23 22 47
Требуется, используя метод динамического программирования, составить план реконструкции предприятий, обеспечивающий максимальную прибыль, при условии, что фирма может вложить в реконструкцию предприятий не более 31 млн. руб.
Решение
В нашей задаче имеется три этапа, на каждом из которых мы должны принять решение о реконструкции первого, второго и третьего предприятия соответственно. Состояние системы xi на каждом этапе i, i=1,2,3, описывается наличием неизрасходованных денежных средств. Поскольку с самого начала у нас имеется 31 млн. рублей, и мы должны расходовать целое число миллионов, можно считать, что на каждом шаге количество неизрасходованных денег есть целое число от 0 до 31.
Выпишем функцию F3x3. Если к моменту принятия решения о реконструкции третьего предприятия известно, сколько осталось денег, то оптимальное решение очень простое – мы проводим самую дорогую реконструкцию, какая нам доступна. Результат оформим в виде таблицы.
x3
0 – 6 7 – 11 12 – 21 22 – 31
u*
1 2 3 4
F3x3
0 9 13 47
Теперь рассмотрим второе предприятие и вычислим функцию F2x2.
Пусть сначала x2=0. Тогда имеется единственная возможность u*=1, F2=0.
Если 1≤x2<5 , то имеется два доступных проекта по второму предприятию: проекты №1 и №2. При этом на реконструкцию третьего предприятия остается денег ≤5, поэтому прибыль последующих этапов равна 0. Имеем:
u=1 → f2x2+F3x3=0+0=0
u=2 → f2x2+F3x3=3+0=3
Максимум из этих выражений достигается во 2-ой строке, следовательно, u*=2, F2x2=3.
Если x2=5, 6, имеется три возможности:
u=1 →x3=5,6 → f2x2+F3x3=0+0=0
u=2 → x3=4,5→f2x2+F3x3=3+0=3
u=3 → x3=0,1→f2x2+F3x3=16+0=16
Максимум из этих трех выражений достигается в третьей строке, следовательно, u*=3, F2x2=16
. Если x2=7, то имеются следующие три возможности:
u=1 →x3=7 → f2x2+F3x3=0+9=9
u=2 → x3=6→f2x2+F3x3=3+0=3
u=3 → x3=2→f2x2+F3x3=16+0=16
Максимум из этих трех выражений достигается в третьей строке, следовательно, u*=3, F2x2=16.
Если x2=8, 9, 10, 11 то имеются следующие три возможности:
u=1 →x3=8,9,10,11 → f2x2+F3x3=0+9=9
u=2 → x3=7,8,9,10→f2x2+F3x3=3+9=12
u=3 → x3=3,4,5,6→f2x2+F3x3=16+0=16
Максимум достигается в третьей строке, следовательно, u*=3, F2x2=16.
Если x2=12, то все четыре проекта реконструкции становятся доступными:
u=1 →x3=12 → f2x2+F3x3=0+13=13
u=2 → x3=11→f2x2+F3x3=3+9=12
u=3 → x3=7→f2x2+F3x3=16+9=25
u=4→ x3=0→f2x2+F3x3=23+0=23
Максимум достигается в третьей строке, следовательно, u*=3, F2x2=25. Если x2=13, 14, 15, 16, то все четыре проекта реконструкции становятся доступными:
u=1 →x3=13, 14,15, 16→ f2x2+F3x3=0+13=13
u=2 → x3=12,13,14,15→f2x2+F3x3=3+13=16
u=3 → x3=8,9,10,11→f2x2+F3x3=16+9=25
u=4→ x3=1,2,3,4→f2x2+F3x3=23+0=23
Максимум достигается в третьей строке, следовательно, u*=3, F2x2=25. Если x2=17, 18, то имеем:
u=1 →x3=17, 18 → f2x2+F3x3=0+13=13
u=2 → x3=16, 17→f2x2+F3x3=3+13=16
u=3 → x3=12, 13→f2x2+F3x3=16+13=29
u=4 → x3=5, 6→f2x2+F3x3=23+0=23
Максимум достигается в третьей строке, следовательно, u*=3, F2x2=29
Задать вопрос
на новый заказ в Автор24.
