Use Dynamic Programming to maximise a nonlinear objective function

 0 Using dynamic programming, Maximise $$z = x_1(1-x_2)x_3$$ subject to $$x_1 - x_2 + x_3 \le 1$$ $$x_1, x_2, x_3 \ge 0$$ Here's the outline of my solution 1. How is it? Let $$y_2=1-x_2$$. Also let's change the other x's to y's. Then we have Maximise $$z = y_1y_2y_3$$ subject to $$y_1 + y_2 + y_3 \le 2$$ $$y_1, \color{red}{y_2,} y_3 \ge 0$$ $$y_2 \le 1$$ We can deduce that $$y_2 \ge 0$$, but do we need to? In this case I guess not, but in general? If we solve this problem by dynamic programming, then we get the same answer as in Wolfram. Here's the outline of my solution 2. How is it? Stage 3: Max $$x_3$$ $$f_3^{op}(s_3) = \max_{0 \le x_3 \le s_3} {x_3}$$ Stage 2: Min $$x_2$$ $$f_2^{op}(s_2) = \min_{0 \le x_2 \le s_2} {(1-x_2) f_3^{op}(s_2+x_2)}$$ Stage 1: Max $$x_1$$ $$f_1^{op}(s_1) = \max_{0 \le x_1 \le s_1} {(x_1) f_2^{op}(s_1 - x_1)}$$ where $$s_1 = 1$$ After we solve $$x_1^{op} = 2/3$$ we get $$x_2^{op} = s_2 = s_1 - x_1 = 1 - 2/3 = 1/3$$ $$x_3^{op} = s_2 + x_2 = 1/3 + 1/3 = 2/3$$ I think we have to minimise $$x_2$$ and maximise everything else because the $$x_2$$ part we want to maximise is $$1-x_2$$, which would be done by minimising $$x_2$$. Is that right? Why should we still have $$x_2 \color{red}{\le s_2}$$? My solution (whose answer agrees with Wolfram) seems to rely on $$x_2^{*} = s_2$$. I was thinking that the negative coefficient of $$x_2$$ in the constraint removes that. If not, what is the role of the negative coefficient of $$x_2$$ (in the constraint, not objective function)? Just the $$s_2 \color{red}{+} x_2$$? asked 22 Apr '16, 06:38 BCLC 8●3●13 accept rate: 0%
Be the first one to answer this question!
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: