# 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

In [3]:

[ 1.2         2.20000001  0.79999999]
z:  13.7999999864


Picking $x_1 \leq 1$:

In [5]:

[ 1.          2.29999999  0.90000001]
z:  13.5999999665


Picking $x_1 \geq 2$:

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

In [11]:

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


Picking first branch:

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

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

% thus: \begin{align} \frac{1}{2}-\frac{3}{4}x-\frac{1}{4}s_1\leq 0\\ \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

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

% thus: \begin{align} \frac{1}{5}-\frac{2}{5}s_1-\frac{4}{5}s_2\leq 0\\ \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

% 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}

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:

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: