1. Run the Dijkstra method to find the shortest paths to every node from A! What will be the shortest path to B?

The shortest path to B in backward direction: B – C – F – G – E – A.

2. Run the modified Dijkstra method to find the widest path among the shortest ones to each node from A (the black numbers are the distances, and the red ones are the widths). What is the best path to D?

The shortest path to D in backward direction: D – B – A.

3. Solve the following linear programming problems with graphic tools.

a) Max{x-y: y >= 0; 2x-y >= 0; x+y<=9}

b) Max{-x+y: y >= 0; 2x-y >= 0; x+y<=9}

The optimal solution for a) will be on the left node of the triangle: x=9,y=0, with objective function value 9.

The optimal solution for b) will be on the top node of the triangle: x=3,y=6, with objective function value 3.

4. What is the dual of the following linear programming problems:

a) The problems of the previous example

b) Min{2x+3y: x+y+z >= 2; 2x-y >= 3; x+y-z<=4}

c) Min{3x+2y: 2x+y = 2; 3x-2y = 3; x-2y=4 x>=0; y>=0}

a) a) Max{x-y: y >= 0; 2x-y >= 0; x+y<=9}

Max{x-y: -y <=0; -2x+y <= 0; x+y<=9}

The dual will be:

Min{9x3: -2x2 + x3 = 1; -x1+x2+x3=-1; x1>=0; x2>=0; x3>=0}

b) The same way as in the previous part of the example:

The dual will be:

Min{9x3: -2x2 + x3 = -1; -x1+x2+x3=1; x1>=0; x2>=0; x3>=0}

b) Min{2x+3y: x+y+z >= 2; 2x-y >= 3; x+y-z<=4} <=> -Max{-2x-3y: x+y+z >= 2; 2x-y >= 3; x+y-z<=4} <=> -Max{-2x-3y: -x-y-z <= -2; -2x+y <= -3; x+y-z<=4}

The dual will be -Min{-2x-3y+4z: -x-2y+z=-2; -x+y+z=-3; -x-z=0; x>=0; y>=0; z>=0 }

That is Max{2x+3y-4z: -x-2y+z=-2; -x+y+z=-3; -x-z=0; x>=0; y>=0; z>=0 }

c) Observe that it is in the form of the dual LP in the theorem, so its dual will be in the form of the original primal one:so the dual of Min{3x+2y: 2x+y = 2; 3x-2y = 3; x-2y=4 x>=0; y>=0}

Is Max{2x+3y+4z: 2x+3y+z<=3; x-2y-2z<=2}.

5. Write down the linear/integer programming formulation of the following problems:

a) The knypsack problem with limit 103, objects 21-46, 38-12, 53-26, 49-38, 25-25

max{46x1+12x2+26x3+38x4+25x5}

With the conditions:

For all i xi>=0, xi<=1 and xi integer

21x1+38x2+53x3+49x4+25x5 <=103

b) The network flow problem of this graph:

We label the edges with the red numbers:

max{x7+x8+x9}

With the conditions:

For all i xi>=0,

x1-x7=0

x2+x4+x5-x8=0

x3-x4-x6=0

-x5+x6-x9=0

x1<=3

x2<=3

x3<=3

x4<=4

x5<=4

x6<=4

x7<=5

x8<=5

x9<=5

c) The minimum assignment (this means a perfect matching with minimum total value) problem of this graph:

We label the edges from left to right.

min{5x1+4x2+3x3+7x4+x5+5x6+2x7}

With the conditions:

For all i xi>=0, xi<=1 and xi integer

x1+x2=1

x3+x4+x5=1

x6+x7=1

x1+x3=1

x2+x4+x6=1

x5+x7=1