• Linear Programming/Optimization:
  • Minimize/maximize a linear function of \(n\) decision variables subject to \(m\) functional constraints (and \(n\) non-negativity constaints)
• The Canonical Form:
  • \(\text{max } Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n\)
  • subject to the constraints
  • \( \begin{array}{c c c c c c c c c} a_{11}x_1 & + & a_{12}x_2 & + & \cdots & + & a_{1n}x_n & \leq & b_1 \\ a_{21}x_1 & + & a_{22}x_2 & + & \cdots & + & a_{2n}x_n & \leq & b_2 \\ & & & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \cdots & + & a_{mn}x_n & \leq & b_m \\ \end{array} \)
  • and
  • \(x_1 \geq 0, x_2 \geq 0, \ldots, x_n \geq 0\)

• The Problem:
  • \( \begin{array}{l l l l l l} \text{max} & 3 x_1 & + & 5 x_2 \\ \text{s.t.} & 1 x_1 & & & \leq & 4 \\ & & & 2 x_2 & \leq & 12 \\ & x_1 & & & \geq & 0 \\ & & & x_2 & \geq & 0 \\ \end{array} \)
• What's Special?
  • Because of the nature of the functional constraints, the problem can be decomposed into two independent problems
    

• Fully Decomposable Problems:
  • Even for larger problems, the nature of the constraints sometimes makes it possible to solve smaller, independent problems
• "Partially Decomposable" Problems:
  • Other problems have stages that are coupled in particular ways

\( \begin{array}{r r r r r r r r r r r} \text{max} &c_{12}x_{12}&+c_{13}x_{13}&+c_{24}x_{24}&+c_{25}x_{25}& +c_{34}x_{34}&+c_{35}x_{35}&+c_{46}x_{46}&+c_{56}x_{56} \\ \text{s.t.} &+x_{12}&+x_{13}& & & & & & & = &1\\ &-x_{12}& &+x_{24}&+x_{25}& & & & & = & 0 \\ & &-x_{13}& & & +x_{34}&+x_{35}& & & = & 0 \\ & & &-x_{24}& & -x_{34}& &+x_{46}& & = & 0 \\ & & & &-x_{25}& &-x_{35}& &+x_{56}& = & 0 \\ & & & & & & &-x_{46}&-x_{56}& = & -1 \\ \end{array} \)

• The Idea:
  • Choose the minimum cost solution stage-by-stage
• The Shortcoming:
  • It isn't guaranteed to find the optimal answer to the complete problem because it sometimes better to "sacrifice" at an earlier stage to be "rewarded" later
• In This Example:
  • \(x_{1,2} = x_{2,6} = x_{6,9} = x_{9,10} = 1\) which has a cost of 13 and we could reduce the cost by using \(1 \rightarrow 4 \rightarrow 6\) (at a cost of 4) rather than \(1 \rightarrow 2 \rightarrow 6\) (at a cost of 6)

• The Idea:
  • Use brute force and evaluate the cost of all possible solutions
• The Shortcoming:
  • It often isn't computationally feasible
• In This Example:
  • There are only 18 possible solutions but in larger problems there are an enormous number of possible solutions

• The Idea:
  • Start with a small portion of the problem, find the optimal solution for it, then gradually enlarge the problem (finding the optimal solution to the larger problem using the optimal solution to the smaller problem)
• Notation:
  • \(x_n\) denotes the immediate "destination" for stage \(n\)
  • \(f_n(s, x_n)\) denotes the total cost of the best overall solution for the remaining stages, given that we are in state \(s\), ready to start stage \(n\), and selects \(x_n\) as the immediate "destination"
  • \(x^*_n\) denotes the value of \(x_n\) that minimizes \(f_n(s, x_n)\) given \(s\) and \(n\)
  • \(f^*_n(s)\) = \(f_n(s, x^*_n)\)

• The Idea:
  • Succesivley find \(f^*_4(s)\), \(f^*_3(s)\), \(f^*_2(s)\), and \(f^*_1(s)\)
• The Solution Using the New Notation:
  • \(1 \rightarrow x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow x_4\), where \(x_4 = 10\).

• One Stage to Go:
  • \(x^*_4\) must be 10, so:
  • \( \begin{array}{c c c} s & x^*_4 & f^*_4(s) \\ \hline 8 & 10 & 3 \\ 9 & 10 & 4 \\ \end{array} \)
• Two Stages to Go:
  • \(f_3(s, x_3) = c_{s, x_3} + f^*_4(x_3)\) so:
  • \begin{array}{c c c c c} s & f_3(s, 8) & f_3(s, 9) & x^*_3 & f^*_3(s) \\ \hline 5 & 1 + 3 & 4 + 4 & 8 & 4 \\ 6 & 6 + 3 & 3 + 4 & 9 & 7 \\ 7 & 3 + 3 & 3 + 4 & 8 & 6 \\ \end{array}

• Three Stages to Go:
  • \(f_2(s, x_2) = c_{s, x_2} + f^*_3(x_2)\) so:
  • \begin{array}{c c c c c c} s & f_2(s, 5) & f_2(s, 6) & f_2(s, 7) & x^*_2 & f^*_2(s) \\ \hline 2 & 7 + 4 & 4 + 7 & 6 + 6 & 5 \text{ or } 6& 11 \\ 3 & 3 + 4 & 2 + 7 & 4 + 6 & 5 & 7 \\ 4 & 4 + 4 & 1 + 7 & 5 + 6 & 5 \text{ or } 6& 8 \\ \end{array}
• Four Stages to Go:
  • \(f_1(s, x_1) = c_{s, x_1} + f^*_2(x_1)\) so:
  • \begin{array}{c c c c c} s & f_1(s, 2) & f_1(s, 3) & f_1(s, 4) & x^*_1 & f^*_1(s) \\ \hline 1 & 2 + 11 & 4 + 7 & 3 + 8 & 3 \text{ or } 4& 11 \\ \end{array}

• One Optimal Solution:
  • \(1 \rightarrow 3 \rightarrow 5 \rightarrow 8 \rightarrow 10\)
• Another Optimal Solution:
  • \(1 \rightarrow 4 \rightarrow 5 \rightarrow 8 \rightarrow 10\)
• A Third Optimal Solution:
  • \(1 \rightarrow 4 \rightarrow 6 \rightarrow 9 \rightarrow 10\)

• Division Into Stages:
  • The solution at each stage is often called a policy
• Each Stage Has States:
  • The possible conditions that the system might be in at that stage
• Policies Transform States:
  • The solution at each stage transform the current state into a state associated with the next stage
• Independence of Policies:
  • Given the current state, an optimal policy for the remaining stages is independent of the policy adopted in the previous stage and there is a recursive relationship that identifies the the optimal policy for each state at stage \(n\) given the optimal policy for each stage st stage \(n+1\)