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$$


  1. 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?

  2. 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's gravatar image

BCLC
8312
accept rate: 0%

edited 24 Apr '16, 10:05

Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×190
×79
×9

Asked: 22 Apr '16, 06:38

Seen: 619 times

Last updated: 24 Apr '16, 10:05

OR-Exchange! Your site for questions, answers, and announcements about operations research.