In [2]:

# Introduction to Linear Programming

#### Question 1 - A

In [112]:

It is clear from the plot that the Maximization problem is unbounded and the solution to minimization problem is (0,4)

Matlab Linear Programming solution, which corresponds to infinity:

In [12]:

array([  5.99065774e+21,   2.62912198e+05])


#### Question 1 - B

Matlab Linear Programming solution:

In [8]:

array([  2.29759394e-08,   3.99999995e+00])


Which we solve by using the dual problem:

In [41]:

A=
[[1 1 2]
[2 1 4]
[5 2 1]]
A'=
[[1 2 5]
[1 1 2]
[2 4 1]]


Which corresponds to following problem: \begin{align} \text{Max } P(x; y) = 2x + 4y\\ \text{Subject to}:\\ x + 2y \leq 5\\ x + y \leq 2\\ x; y \geq 0\\ \end{align}

Writing down the augumented matrix:

In [53]:

x y s_1 s_2 P b
s_1 1 2 1 0 0 5
s_2 1 1 0 1 0 2
P -2 -4 0 0 1 0

3 rows × 6 columns

Which has following basic solution: %

choosing column $y$ as pivot column and row $s_2$ as pivot row we do the pivot operation:

In [54]:

x y s_1 s_2 P b
s_1 -1 0 1 -2 0 1
y 1 1 0 1 0 2
P 2 0 0 4 1 8

3 rows × 6 columns

This is matrix provides us with the solution: %

#### Question 2

In [16]:

Matlab Linear Programming solution:

In [17]:

In [18]:

x y s_1 s_2 s_3 P b
s_1 1 1 -1 0 0 0 2
s_2 1 1 0 1 0 0 8
s_3 2 1 0 0 1 0 10
P 20 10 0 0 0 1 0

4 rows × 7 columns

In [32]:

x y s_1 s_2 s_3 a_1 P b
s_1 1 1 -1 0 0 1 0 2
s_2 1 1 0 1 0 0 0 8
s_3 2 1 0 0 1 0 0 10
P -20 -10 0 0 0 1000 1 0

4 rows × 8 columns

In [33]:

x y s_1 s_2 s_3 a_1 P b
a_1 1 1 -1 0 0 1 0 2
s_2 1 1 0 1 0 0 0 8
s_3 2 1 0 0 1 0 0 10
P -1020 -1010 1000 0 0 0 1 -2000

4 rows × 8 columns

Here we write a simple function to do the pivot operation:

In [25]:

In [34]:

array([[    1,     1,    -1,     0,     0,     1,     0,     2],
[    1,     1,     0,     1,     0,     0,     0,     8],
[    2,     1,     0,     0,     1,     0,     0,    10],
[-1020, -1010,  1000,     0,     0,     0,     1, -2000]])


In [28]:

x y s_1 s_2 s_3 a_1 P b
x 1 1 -1 0 0 1 0 2
s_2 0 0 1 1 0 -1 0 6
s_3 0 -1 2 0 1 -2 0 6
P 0 10 -20 0 0 1020 1 40

4 rows × 8 columns

In [29]:

x y s_1 s_2 s_3 a_1 P b
x 1 0 0 0 0 0 0 5
s_2 0 0 0 1 -1 0 0 3
s_1 0 -1 2 0 1 -2 0 6
P 0 0 0 0 10 1000 1 100

4 rows × 8 columns

Since one of the constraint lines is parallel to objective function the whole line segment is optimal. The other end of the line is picked by Matlab solver.

#### Question 3 - A

In [193]:

\begin{align} \text{Max } P(x; y) =& 20x + 10y
\text{Subject to}:&
2x + 3y \geq& 30
2x + y \leq& 26
-2x + 5y \leq& 34
x; y \geq& 0
\end{align}

In [254]:

Matlab Linear Programming solution:

In [16]:

array([ 9.71445097,  6.57109806])


In [230]:

x y s_1 s_2 s_3 P b
s_1 2 3 -1 0 0 0 30
s_2 2 1 0 1 0 0 26
s_3 -2 5 0 0 1 0 34
P -20 -10 0 0 0 1 0

4 rows × 7 columns

This is not a valid basic solution

In [232]:

x y s_1 s_2 s_3 a_1 P b
s_1 2 3 -1 0 0 1 0 30
s_2 2 1 0 1 0 0 0 26
s_3 -2 5 0 0 1 0 0 34
P -20 -10 0 0 0 1000 1 0

4 rows × 8 columns

In [233]:

x y s_1 s_2 s_3 a_1 P b
a_1 2 3 -1 0 0 1 0 30
s_2 2 1 0 1 0 0 0 26
s_3 -2 5 0 0 1 0 0 34
P -2020 -3010 1000 0 0 0 1 -30000

4 rows × 8 columns

In [234]:

x y s_1 s_2 s_3 a_1 P b
a_1 3.2 0 -1 0 -0.6 1 0 9.6
s_2 2.4 0 0 1 -0.2 0 0 19.2
y -2.0 5 0 0 1.0 0 0 34.0
P -3224.0 0 1000 0 602.0 0 1 -9532.0

4 rows × 8 columns

In [235]:

x y s_1 s_2 s_3 a_1 P b
x 3.2 0 -1.000 0 -0.600 1.000 0 9.6
s_2 0.0 0 0.750 1 0.250 -0.750 0 12.0
y 0.0 5 -0.625 0 0.625 0.625 0 40.0
P 0.0 0 -7.500 0 -2.500 1007.500 1 140.0

4 rows × 8 columns

In [237]:

x y s_1 s_2 s_3 a_1 P b
x 3.2 0 0.00 1.333333 -2.666667e-01 0.00 0 25.6
s_1 0.0 0 0.75 1.000000 2.500000e-01 -0.75 0 12.0
y 0.0 5 0.00 0.833333 8.333333e-01 0.00 0 50.0
P 0.0 0 0.00 10.000000 1.132427e-13 1000.00 1 260.0

4 rows × 8 columns

#### Question 3 - B

Matlab Linear Programming solution:

In [17]:

array([ 3.,  8.])


This optimization problem is equal to:

In [257]:

x y s_1 s_2 s_3 P b
s_1 2 3 -1 0 0 0 30
s_2 2 1 0 1 0 0 26
s_3 -2 5 0 0 1 0 34
P 20 10 0 0 0 1 0

4 rows × 7 columns

In [261]:

x y s_1 s_2 s_3 a_1 P b
s_1 2 3 -1 0 0 1 0 30
s_2 2 1 0 1 0 0 0 26
s_3 -2 5 0 0 1 0 0 34
P 20 10 0 0 0 1000 1 0

4 rows × 8 columns

In [262]:

x y s_1 s_2 s_3 a_1 P b
a_1 2 3 -1 0 0 1 0 30
s_2 2 1 0 1 0 0 0 26
s_3 -2 5 0 0 1 0 0 34
P -1980 -2990 1000 0 0 0 1 -30000

4 rows × 8 columns

In [263]:

x y s_1 s_2 s_3 a_1 P b
a_1 3.2 0 -1 0 -0.6 1 0 9.6
s_2 2.4 0 0 1 -0.2 0 0 19.2
y -2.0 5 0 0 1.0 0 0 34.0
P -3176.0 0 1000 0 598.0 0 1 -9668.0

4 rows × 8 columns

In [265]:

x y s_1 s_2 s_3 a_1 P b
x 3.2 0 -1.000 0 -0.600 1.000 0 9.6
s_2 0.0 0 0.750 1 0.250 -0.750 0 12.0
y 0.0 5 -0.625 0 0.625 0.625 0 40.0
P 0.0 0 7.500 0 2.500 992.500 1 -140.0

4 rows × 8 columns

#### Question 4

In [311]:

Matlab Linear Programming solution:

In [18]:

array([  3.,  10.])


In [277]:

x y s_1 s_2 s_3 P b
s_1 2 1 1 0 0 0 16
s_2 1 0 0 1 0 0 6
s_3 0 1 0 0 1 0 10
P -1 -1 0 0 0 1 0

4 rows × 7 columns

We first pick column 1:

In [278]:

x y s_1 s_2 s_3 P b
s_1 0 1 1 -2 0 0 4
x 1 0 0 1 0 0 6
s_3 0 1 0 0 1 0 10
P 0 -1 0 1 0 1 6

4 rows × 7 columns

In [279]:

x y s_1 s_2 s_3 P b
y 0 1 1 -2 0 0 4
x 1 0 0 1 0 0 6
s_3 0 0 -1 2 1 0 6
P 0 0 1 -1 0 1 10

4 rows × 7 columns

In [280]:

x y s_1 s_2 s_3 P b
y 0 1 0 0 1 0 10
x 1 0 0 0 -1 0 3
s_2 0 0 -1 2 1 0 6
P 0 0 0 0 0 1 13

4 rows × 7 columns

In [284]:

x y s_1 s_2 s_3 P b
s_1 2 1 1 0 0 0 16
s_2 1 0 0 1 0 0 6
s_3 0 1 0 0 1 0 10
P -1 -1 0 0 0 1 0

4 rows × 7 columns

Now we pick column 2:

In [285]:

x y s_1 s_2 s_3 P b
s_1 2 0 1 0 -1 0 6
s_2 1 0 0 1 0 0 6
y 0 1 0 0 1 0 10
P -1 0 0 0 1 1 10

4 rows × 7 columns

In [286]:

x y s_1 s_2 s_3 P b
x 2 0 1 0 -1 0 6
s_2 0 0 -1 1 0 0 3
y 0 1 0 0 1 0 10
P 0 0 0 0 0 1 13

4 rows × 7 columns

Tags:

Categories:

Updated: