Question

Problem 6-29 (Algorithmic) The north-south highway system passing through Albany, New York, can accommodate the capacities shown. If the constant is "1" it must be entered in the box. If your answer is zero enter "0". For negative values enter "minus" sign (-). Flow capacity: 4.000 vehicles per hour 6 Entering Albany (north) Leaving Albany (south) Max s.t.

Answer 1

LP model is following:

Max 1x61

s.t.

Node 1: 1x12 + 1x13 + 1x14 - 1x61 = 0

Node 2: 1x24 + 1x25 - 1x12 - 1x42 = 0

Node 3: 1x34 + 1x36 - 1x13 - 1x43 = 0

Node 4: 1x42 + 1x43 + 1x45 + 1x46 - 1x14 - 1x24 - 1x34 - 1x54 = 0

Node 5: 1x54 + 1x56 - 1x25 - 1x45 = 0

Node 6: 1x61 - 1x36 - 1x46 - 1x56 = 0

x12 <= 1

x13 <= 3

x14 <= 1

x24 <= 1

x25 <= 3

x34 <= 2

x36 <= 1

x42 <= 1

x43 <= 2

x45 <= 1

x46 <= 1

x54 <= 1

x56 <= 4

xij >= 0

LP model is solved using LINGO as follows:

Lingo 17.0 - Solution Report - Lingo1 File Edit Solver Window Help Lindo Model - Lingo1 Max lx61 Solution Report - Lingo1 Global optimal solution found. Objective value: Infeasibilities: Total solver iterations: Elapsed runtime seconds: 5.000000 0.000000 s.t. 1.68 Model Class : 1x12 + 1x13 + 1x14 - lx6l = 0 1x24 + 1x25 - 1x12 - 1x42 = 0 1x34 + 1x36 - lx13 - 1x43 = 0 1x42 + 1x43 + 1x45 + 1x 46 - 1x14 - 1x24 - 1x34 - lx54 = 0 1x54 + 1x56 - 1x25 - lx45 = 0 1x61 - lx36 - lx46 - lx56 = 0 xl2 <= 1 x13 <= 3 x14 <= 1 Total variables: Nonlinear variables: Integer variables: Total constraints: Nonlinear constraints: β η Total nonzeros: Nonlinear nonzeros: Β ο Ν ↑↑↑↑↑↑↑↑↑↑ ω η Variable Οι in Value 5.000000 1.000000 3.000000 1.000000 0.000000 2.000000 1.000000 2.000000 1.000000 0.000000 1.000000 1.000000 0.000000 3.000000 Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 o un won X56 SIN! Slack or Surplus 5.000000 0.000000 Dual Price 1.000000 -1.000000 For Help, press F1 NUM L n 1, Col1 9:38 am

Objective function value = 5   (the flow is in thousands)

Therefore, the highway system cannot accommodate a north-south flow of 6,000 vehicles per hour

No

Maximum flow of vehicles per hour = 5000