# 02-Integer-Linear-Programming

In [1]:

Found version: 2013a at /Applications/MATLAB_R2013a.app/bin/matlab

< M A T L A B (R) >
R2013a (8.1.0.604) 64-bit (maci64)
February 15, 2013

To get started, type one of these: helpwin, helpdesk, or demo.
For product information, visit www.mathworks.com.

>>


# Introduction to Optimization

### Homework 2

#### Question 1

\begin{align} \text{Max } 4x_1 + 3x_2+3x_3\\ \text{Subject to}:\\ 4x_1+2x_2+x_3\leq 10 \\ 3x_1+4x_2+2x_3\leq 14 \\ 2x_1+x_2+3x_3\leq 7 \\ x_1,x_2,x_3\geq 0\\ x_1,x_2,x_3 \in Z \end{align}

In [3]:

[ 1.2         2.20000001  0.79999999]
z:  13.7999999864


Picking $x_1 \leq 1$:

\begin{align} \text{Max } 4x_1 + 3x_2+3x_3\\ \text{Subject to}:\\ 4x_1+2x_2+x_3\leq 10 \\ 3x_1+4x_2+2x_3\leq 14 \\ 2x_1+x_2+3x_3\leq 7 \\ x_1 \leq 1 \\ x_1,x_2,x_3\geq 0\\ x_1,x_2,x_3 \in Z \end{align}

In [5]:

[ 1.          2.29999999  0.90000001]
z:  13.5999999665


Picking $x_1 \geq 2$:

\begin{align} \text{Max } 4x_1 + 3x_2+3x_3\\ \text{Subject to}:\\ 4x_1+2x_2+x_3\leq 10 \\ 3x_1+4x_2+2x_3\leq 14 \\ 2x_1+x_2+3x_3\leq 7 \\ x_1 \geq 2 \\ x_1,x_2,x_3\geq 0\\ x_1,x_2,x_3 \in Z \end{align}

In [7]:

[ 2.          0.59999998  0.80000001]
z:  12.1999999723


Therefore Picking $x_1 \leq 1$ yields higher objective function.

In [8]:

Picking $x_2 \leq 2$:

\begin{align} \text{Max } 4x_1 + 3x_2+3x_3
\text{Subject to}:
4x_1+2x_2+x_3\leq 10
3x_1+4x_2+2x_3\leq 14
2x_1+x_2+3x_3\leq 7
x_2 \leq 2
x_1 \leq 1
x_1,x_2,x_3\geq 0
x_1,x_2,x_3 \in Z \end{align}

In [9]:

[ 1.  2.  1.]
z:  13.0000000002


Picking $x_2 \geq 3$:

\begin{align} \text{Max } 4x_1 + 3x_2+3x_3\\ \text{Subject to}:\\ 4x_1+2x_2+x_3\leq 10 \\ 3x_1+4x_2+2x_3\leq 14 \\ 2x_1+x_2+3x_3\leq 7 \\ x_2 \geq 3 \\ x_1 \leq 1 \\ x_1,x_2,x_3\geq 0\\ x_1,x_2,x_3 \in Z \end{align}

In [11]:

[ -3.80282472e-11   3.00000000e+00   1.00000000e+00]
z:  12.0000000027


Picking first branch:

\begin{align} \text{Max } 4x_1 + 3x_2+3x_3\\ \text{Subject to}:\\ 4x_1+2x_2+x_3\leq 10 \\ 3x_1+4x_2+2x_3\leq 14 \\ 2x_1+x_2+3x_3\leq 7 \\ x_2 \leq 2 \\ x_1 \leq 1 \\ x_1,x_2,x_3\geq 0\\ x_1,x_2,x_3 \in Z \end{align}

#### Question 2

In [13]:

Linear Programming
100 loops, best of 3: 10.2 ms per loop
x_1: 1.2
x_2: 2.2
x_3: 0.8
Integer Linear Programming
100 loops, best of 3: 14.7 ms per loop
x_1: 1.0
x_2: 2.0
x_3: 1.0


#### Question 3

\begin{align} \text{Min } x - y\\ \text{Subject to}:\\ 3x+4y \leq 6 \\ x-y \leq 1 \\ x,y \geq 0\\ x,y \in Z \end{align}

In [15]:

In [16]:

[ -6.37783160e-11   1.50000000e+00]
z:  -1.50000000011


In [17]:

x y s_1 s_2 P b
s_1 3 4 1 0 0 6
s_2 1 -1 0 1 0 1
P 1 -1 0 0 1 0

3 rows × 6 columns

\begin{align} y&=\frac{3}{2}-\frac{3}{4}x-\frac{1}{4}s_1=1.5\\ &=(1+\frac{1}{2})-(0+\frac{3}{4}x)-(0+\frac{1}{4}s_1)\\ &=(1)+(\frac{1}{2}-\frac{3}{4}x-\frac{1}{4}s_1)\\ \end{align} thus: \begin{align} \frac{1}{2}-\frac{3}{4}x-\frac{1}{4}s_1\leq 0\\ \end{align}

\begin{align} \text{Min } x - y\\ \text{Subject to}:\\ 3x+4y+s_1 = 6 \\ x-y \leq 1 \\ -\frac{3}{4}x-\frac{1}{4}s_1\leq -\frac{1}{2}\\ x,y \geq 0\\ x,y \in Z \end{align}

In [19]:

In [20]:

[  2.95855784e-10   1.00000000e+00   2.00000000e+00]
z:  -0.999999999679


In [22]:

x y s_1 s_2 t P b
s_1 3.00 4 1.00 0 0 0 6.0
s_2 1.00 -1 0.00 1 0 0 1.0
t_1 -0.75 0 -0.25 0 1 0 -0.5
P -1.00 1 0.00 0 0 1 0.0

4 rows × 7 columns

#### Question 4

\begin{align} \text{Max } 4x_1+3x_2+x_3\\ \text{Subject to}:\\ 4x_1+2x_2+x_3 \leq 10 \\ 3x_1+4x_2+2x_3 \leq 14 \\ 2x_1+x_2+3x_3 \leq 7 \\ x_i \geq 0\\ x_i \in Z \end{align}

In [23]:

Question 4:
MAXIMIZE
4*x_1 + 3*x_2 + 1*x_3 + 0
SUBJECT TO
_C1: 4 x_1 + 2 x_2 + x_3 <= 10

_C2: 3 x_1 + 4 x_2 + 2 x_3 <= 14

_C3: 2 x_1 + x_2 + 3 x_3 <= 7

VARIABLES
0 <= x_1 Integer
0 <= x_2 Integer
0 <= x_3 Integer

x_1: 2.0
x_2: 1.0
x_3: 0.0

11.0


In [26]:

In [43]:

[  1.20000000e+00   2.60000000e+00   1.71098691e-11]
z:  -12.6


In [31]:

x_1 x_2 x_3 s_1 s_2 s_3 P b
s_1 1 0 0.0 0.4 -0.2 0.0 0 1.2
s_2 0 1 0.5 -0.3 0.4 0.0 0 2.6
s_3 0 0 1.0 -0.2 0.0 0.4 0 0.8
P 0 0 0.5 0.7 0.4 0.0 1 12.6

4 rows × 8 columns

\begin{align} x_1&=-\frac{56}{10}-2x_2-\frac{6}{10}s_2+\frac{4}{10}s_3\\ &=-5\frac{3}{5}-2x_2-\frac{3}{5}s_2+\frac{2}{5}s_3\\ &=1 +1 + \{\frac{1}{5}-\frac{2}{5}s_1-\frac{4}{5}s_2\}\\ \end{align} thus: \begin{align} \frac{1}{5}-\frac{2}{5}s_1-\frac{4}{5}s_2\leq 0\\ \end{align}

\begin{align} \text{Max } 4x_1+3x_2+x_3\\ \text{Subject to}:\\ 4x_1+2x_2+x_3 +s_1= 10 \\ 3x_1+4x_2+2x_3+s_2 = 14 \\ 2x_1+x_2+3x_3 \leq 7 \\ -\frac{2}{5}s_1-\frac{4}{5}s_2\leq -\frac{1}{5}\\ x_i \geq 0\\ x_i \in Z \end{align}

In [162]:

[[ 3.    4.    2.    0.  ]
[ 2.    1.    3.    0.  ]
[-1.    0.    0.    0.  ]
[ 0.   -1.    0.    0.  ]
[ 0.    0.   -1.    0.  ]
[ 0.    0.    0.   -1.  ]
[ 0.   -0.5  -0.25 -0.25]]
[ 14.    7.    0.    0.    0.    0.   -0.5]
[  1.20000000e+00   2.60000000e+00   2.77191248e-09   1.82848225e-09]
z:  -12.5999999939


In [160]:

x_1 x_2 x_3 s_1 s_2 s_3 t_1 P b
s_1 4 2.0 1.00 1.00 0 0 0 0 10.0
s_2 3 4.0 2.00 0.00 1 0 0 0 14.0
s_3 2 1.0 3.00 0.00 0 1 0 0 7.0
t_1 0 -0.5 -0.25 -0.25 0 0 1 0 -0.5
P -4 -3.0 -1.00 0.00 0 0 0 1 0.0

5 rows × 9 columns

\begin{align} x_2&=\frac{7}{2}-\frac{3}{4}x_1-\frac{1}{2}x_3-\frac{1}{4}s_2=1.2\\ &=(3+\frac{1}{2})-(0+\frac{3}{4}x_1)-(0+\frac{1}{2}x_3)-(0+\frac{1}{4}s_2)\\ &=(3)+(\frac{1}{2}-\frac{3}{4}x_1-\frac{1}{2}x_3-\frac{1}{4}s_2)\\\\ \end{align} thus: \begin{align} \frac{1}{2}-\frac{3}{4}x_1-\frac{1}{2}x_3-\frac{1}{4}s_2 \leq 0 \end{align}

\begin{align} \text{Max } 4x_1+3x_2+x_3\\ \text{Subject to}:\\ 4x_1+2x_2+x_3 \leq 10 \\ 3x_1+4x_2+2x_3 \leq 14 \\ 2x_1+x_2+3x_3 \leq 7 \\ -\frac{1}{2}x_2-\frac{1}{4}x_3-\frac{1}{4}s_1\leq -\frac{1}{2}\\ -\frac{3}{4}x_1-\frac{1}{2}x_3-\frac{1}{4}s_2 \leq -\frac{1}{2}\\ x_i \geq 0\\ x_i \in Z \end{align}

In [1]:

[[ 2.    1.    3.    0.    0.  ]
[-1.    0.    0.    0.    0.  ]
[ 0.   -1.    0.    0.    0.  ]
[ 0.    0.   -1.    0.    0.  ]
[ 0.    0.    0.   -1.    0.  ]
[ 0.    0.    0.    0.   -1.  ]
[ 0.   -0.5  -0.25 -0.25  0.  ]
[-0.75  0.   -0.5   0.   -0.25]]
[ 7.   0.   0.   0.   0.  -0.5 -0.5]


#### Question 5

Decision variables:

\begin{align} \text{Max: } \sum_1^6 r_i p_i\\ \text{Subject to:}\\ \sum_1^6 c_{1i} p_i \leq 250\\ \sum_1^6 c_{2i} p_i \leq 75\\ \sum_1^6 c_{3i} p_i \leq 50\\ \sum_1^6 c_{4i} p_i \leq 50\\ \sum_1^6 c_{5i} p_i \leq 50\\ \end{align}

Where $r_i$ represents revenue for project $i$,$c_{ki}$ represents costs for project $i$ at year $k$ and $p_i=0/1$ represents whether project $i$ is selected.

In [5]:

[ 1.  0.  0.  1.  1.  0.]
z:  486.0


Tags:

Categories:

Updated: