Latest revision as of 10:10, 13 September 2013

ECE Ph.D. Qualifying Exam in "Automatic Control" (AC)

Question 3, August 2011, Part 2

Part 1,2,3,4,5

 $ \color{blue}\text{2. } \left( \text{20 pts} \right) \text{ Use the simplex method to solve the problem, } $

               maximize        x₁ + x₂

               $ \text{subject to } x_{1}-x_{2}\leq2 $
                                        $ x_{1}+x_{2}\leq6 $                                         

                                        $ x_{1},x_{2}\geq0. $

Theorem: 

A basic feasible solution is optimal if and only if the corresponding reduced cost coefficeints are all nonnegative.

Simplex Method:

1. Transform the given problem into standard form by introducing slack variables x₃ and x₄.

2. Form a canonical augmented matrix corresponding to an initial basic feasible solution.

3. Calculate the reduced cost coefficients corresponding to the nonbasic variables.

4. If $ r_{j}>\geq0 $ for all j, stop. -- the current basic feasible solution is optimal.

5. Select a q such that r_q < 0

6. If no y_iq > 0, stop. -- the problem is unbounded; else, calculate  $ p=argmin_{i}\left \{ y_{i0}/y_{iq}:y_{iq}>0 \right \} $. 

7. Update the canonical augmented matrix by pivoting about the (p,q) th element.

8. Go to step 3.

$ \color{blue}\text{Solution 1:} $

   min    − x₁ − x₂ 
   subject to    x₁ − x₂ + x₃ = 2 
                      x₁ + x₂ + x₄ = 6 

                      $ x_{1},x_{2},x_{3},x_{4}\geq 0 $

$ \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 1 & 1 & 0 & 1 & 6 \\ -1 & -1 & 0 & 0 & 0 \end{matrix} \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 0 & 2 & -1 & 1 & 4 \\ 0 & -2 & 1 & 0 & 2 \end{matrix} \Rightarrow \begin{matrix} 1 & 0 & \frac{1}{2} & \frac{1}{2} & 4\\ 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} $

$ \Rightarrow x_{1}=4, x_{2}=2, \text{the maximum value } x_{1}+x_{2}=6 $

$ \color{blue}\text{Solution 2:} $

Get standard form for simplex method   min    − x₁ − x₂

                                                           subject to    x₁ − x₂ + x₃ = 2

                                                                             x₁ + x₂ + x₄ = 6

                                                                             $ x_{i}\geq0, i=1,2,3,4 $

$ \begin{matrix} & x_{1} & x_{2} & x_{3} & x_{4} & b\\ & 1 & -1 & 1 & 0 & 2\\ & 1 & 1 & 0 & 1 & 6 \\ c^{T} & -1 & -1 & 0 & 0 & 0 \end{matrix} $      $ \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 1 & 1 & 0 & 1 & 6 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 0 & 2 & -1 & 1 & 4 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} \Rightarrow \begin{matrix} 1 & 0 & \frac{1}{2} & \frac{1}{2} & 4\\ 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} $

$ \therefore \text{the optimal solution to the original problem is } x^{*}= \begin{bmatrix} 4\\ 2 \end{bmatrix} $

The maximum value for   x₁ + x₂ is 6.

$ \color{blue}\text{Related Problem: Solve the following problem using simplex method} $

                      max  2x₁ + 3x₂

            subject to  $ 2x_{1}+x_{2}\leq4 $

                              $ x_{1}+x_{2}\leq3 $

                              $ x_{1},x_{2}\geq0. $

$ \color{blue}\text{Solution:} $

Transform to standard form:  min   − 2x₁ − 3x₂

                                       subject to   2x₁ + x₂ + x₃ = 4

                                                          x₁ + x₂ + x₄ = 3

                                                          $ x_{i}\geq0, i=1,2,3,4 $

              $ \begin{matrix} & x_{1} & x_{2} & x_{3} & x_{4} & b\\ & 2 & 1 & 1 & 0 & 4\\ & 1 & 1 & 0 & 1 & 3 \\ c^{T} & -2 & -3 & 0 & 0 & 0 \end{matrix} $

We have r₁ = − 2 < 0  and  r₂ = − 3 < 0.  We introduce a₂ into the new basis and pivot y₂₂, by calculating the ratios y_i0 / y_i2,y_i2 > 0.

               $ \begin{matrix} & x_{1} & x_{2} & x_{3} & x_{4} & b\\ & 2 & 1 & 1 & 0 & 4\\ & 1 & 1 & 0 & 1 & 3 \\ c^{T} & 1 & 0 & 0 & 3 & 9 \end{matrix} \Rightarrow \begin{matrix} & x_{1} & x_{2} & x_{3} & x_{4} & b\\ & 1 & 0 & 1 & -1 & 1\\ & 1 & 1 & 0 & 1 & 3 \\ c^{T} & 1 & 0 & 0 & 3 & 9 \end{matrix} $

All the reduced cost coefficients are positive, hence the optimal solution to the problem in standard form is

               $ x^{*}=\begin{bmatrix} 0 & 3 & 1 & 0 \end{bmatrix}^{T}. $

The optimal solution to the original problem is $ x^{*}=\begin{bmatrix} 0 & 3 \end{bmatrix}^{T}. $ and the optimal objective value is 9.

Automatic Control (AC)- Question 3, August 2011

Go to

• Part 1: solutions and discussions
• Part 2: solutions and discussions
• Part 3: solutions and discussions
• Part 4: solutions and discussions
• Part 5: solutions and discussions

Back to ECE Qualifying Exams (QE) page