Algorithms for telecommunications: class #5

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
Unclear, need to ask the teachers, since most is obviously derived works.