Algorithms for telecommunications: class #5

- Chapter 2 from "Routing, Flow, and Capacity Design of Communication and Computer Networks"
- Exercises for the lab

Laboratory on linear programming.

Solving this problem:

(1)\begin{align} \left\{ \begin{array}{rcl} H_f + H_s + H_{sOT} & = & 480 \\ B_f + B_s + B_{sOT} & = & 400 \\ P_f + P_s + P_{sOT} & = & 230 \\ \\ H_s + B_s + P_s & \leq & 420 \\ H_{sOT} + B_{sOT} + P_{sOT} & \leq & 250 \end{array} \right. \end{align}

(2)
\begin{array} {rclc} \textrm{Profit} & = & 8 H_f + 14 H_s + 11 H_{sOT} & +\\ & + & 4 B_f + 12 B_s + 7 B_{sOT} & + \\ & + & 4 P_f + 13 P_s + 9 P_{sOT}\\ \end{array}

My solution below (lp-solve), without elimination variables:

```
max: 8 H_f + 14 H_s + 11 H_sOT + 4 B_f + 12 B_s + 7 B_sOT + 4 P_f + 13 P_s + 9 P_sOT;
H_f + H_s + H_sOT = 480;
B_f + B_s + B_sOT = 400;
P_f + P_s + P_sOT = 230;
H_s + B_s + P_s <= 420;
H_sOT + B_sOT + P_sOT <= 250;
int H_f, H_s, H_sOT, B_f, B_s, B_sOT, P_f, P_s, P_sOT;
```

And the solution:

```
Value of objective function: 10910
Actual values of the variables:
H_f 440
H_s 0
H_sOT 40
B_f 0
B_s 400
B_sOT 0
P_f 0
P_s 20
P_sOT 210
```

Exercise from the pdf:

Minimize $2 x_{01} + 4 x_{04} + 3 x_{12} + x_{23} + x_{30} + 3 x_{43}$

Subject to:

(3)\begin{array} {rrrrrrrr} & x_{30} & - & x_{01} & - & x_{04} & = & -1 \\ & x_{01} & - & x_{12} & & & = & 0 \\ & x_{12} & - & x_{23} & & & = & 0 \\ & x_{23} & + & x_{43} & - & x_{30} & = & 1 \\ & x_{04} & - & x_{43} & & & = & 0 \\ \multicolumn{6}{r}{x_{01},\cdots,x_{43}} & \geq & 0 \end{array}

My solution:

```
min: 2 x01 + 4 x04 + 3 x12 + x23 + x30 + 3 x43;
x30 - x01 - x04 = -1;
x01 - x12 = 0;
x12 - x23 = 0;
x23 + x43 - x30 = 1;
x04 - x43 = 0;
bin x01, x04, x12, x23, x30, x43;
```

```
Value of objective function: 6
Actual values of the variables:
x01 1
x04 0
x12 1
x23 1
x30 0
x43 0
```

page revision: 7, last edited: 06 Nov 2009 16:20