Question

Problem 7-15 CHB, Inc., is a bank holding company that is evaluating the potential for expanding into a 13-county region in the southwestern part of the state. State law permits establishing branches in any county that is adjacent to a county in which a PPB (principal place of business) is located. The following map shows the 13-county region, with the population of each county indicated. 195.000 87.000 96.000 117,000 52.000 57.000 233.000 88,000 11 95.000 106,000 10 76,000 13 175,000 323,000

Answer 1

a)

It can formulated as LP model as follows:

Let Xi = 1 if PPB is established at county i, otherwise Xi = 0

Yi = 1, if a branch can be established in county i, otherwise Yi = 0

Max 195000Y1+96000Y2+87000Y3+52000Y4+233000Y5+57000Y6+117000Y7+88000Y8+106000Y9+76000Y10+95000Y11+323000Y12+175000Y13

s.t.

X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13 <= 1

X1+X2+X3-Y1 >= 0

X2+X3+X4+X6+X7-Y2 >= 0

X1+X2+X3+X4+X5-Y3 >= 0

X2+X3+X4+X5+X6+X8-Y4 >= 0

X3+X4+X5+X8+X9+X10-Y5 >= 0

X2+X4+X6+X7+X8+X11-Y6 >= 0

X2+X6+X7+X11-Y7 >= 0

X4+X5+X6+X8+X9+X11-Y8 >= 0

X5+X8+X9+X10+X11+X12-Y9 >= 0

X5+X9+X10+X12-Y10 >= 0

X6+X7+X8+X9+X11+X12+X13-Y11 >= 0

X9+X10+X11+X12+X13-Y12 >= 0

X11+X12+X13-Y13 >= 0

Xi, Yi = {0,1}

Solution using LINGO is following:

Lingo 17.0 - Solution Report - Lingo1 File Edit Solver Window Help DBH8 %0 29 Be OKO 2323 2/ Solution Report - Lingo1 Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Elapsed runtime seconds: 961000.0 961000.0 0.000000 14 0.58 Model Class: PILP Total variables: Nonlinear variables: Integer variables: Total constraints: Nonlinear constraints: Lindo Model - Lingo1 Max 195000Y1+96000Y2+87000Y3+5200044 +233000Y5+57000Y6+117000Y7+88000Y8 +106000Y9+76000Y10+95000211 +32300012+175000913 s.t. X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+x13 <= 1 X1+X2+X3-Yl >= 0 X2+X3+X4+X6+X7-Y2 >= 0 X1+X2+X3+X4+X5-Y3 >= 0 X2+X3+X4+X5+X6+X8-94 >= 0 X3+X4+X5+X8+X9+X10-Y5 >= 0 X2+X4+X6+X7+X8+Xll-Y6 >= 0 X2+X6+X7+X11-77 >= 0 X4+X5+X6+X8+X9+X11-Y8 >= 0 X5+X8+X9+X10+X11+x12-19 >= 0 X5+X9+X10+X12-410 >= 0 X6+X7+X8+X9+X11+x12+X13-Yll >= 0 X9+X10+X11+X12+X13-Y12 >= 0 X11+x12+x13-Y13 >= 0 END INT XI INT X2 INT X3 INT X4 INT X5 INT X6 INT X7 INT X8 INT X9 INT X10 INT X11 INT X12 INT X13 INT YI INT Y2 INT Y3 INT Y4 INT Y5 INT Y6 Total nonzeros: Nonlinear nonzeros: Variable Value 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 Y9 Y10 Reduced Cost -195000.0 -96000.00 -87000.00 -52000.00 -233000.0 -57000.00 -117000.0 -88000.00 -106000.0 - 76000.00 -95000.00 -323000.0 -175000.0 0.000000 0.000000 0.000000 CAP NUM Yli W For Help, press F1 L n 58, Col10 10:15 am

Variable Value 0.000000 0.000000 ооооо ооооооо ооооо оооооо оооо во Y10 Ұ11 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 Reduced Cost -195000.0 –96000.00 –87000.00 –52000.00 -233000.0 -57000.00 -117000.0 –88000.00 -106000.0 -76000.00 —95000.00 -323000.0 -175000.0 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 X9 х10 X11 X12 Х13

The optimal solution has a principal place of business in County 11

b)

In this case, only the following constraint will change

X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13 <= 2

Rest of the model remains same.

Max 195000Y1+96000Y2+87000Y3+52000Y4+233000Y5+57000Y6+117000Y7
+88000Y8+106000Y9+76000Y10+95000Y11+323000Y12+175000Y13
s.t.
X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13 <= 2
X1+X2+X3-Y1 >= 0
X2+X3+X4+X6+X7-Y2 >= 0
X1+X2+X3+X4+X5-Y3 >= 0
X2+X3+X4+X5+X6+X8-Y4 >= 0
X3+X4+X5+X8+X9+X10-Y5 >= 0
X2+X4+X6+X7+X8+X11-Y6 >= 0
X2+X6+X7+X11-Y7 >= 0
X4+X5+X6+X8+X9+X11-Y8 >= 0
X5+X8+X9+X10+X11+X12-Y9 >= 0
X5+X9+X10+X12-Y10 >= 0
X6+X7+X8+X9+X11+X12+X13-Y11 >= 0
X9+X10+X11+X12+X13-Y12 >= 0
X11+X12+X13-Y13 >= 0
END
INT X1
INT X2
INT X3
INT X4
INT X5
INT X6
INT X7
INT X8
INT X9
INT X10
INT X11
INT X12
INT X13
INT Y1
INT Y2
INT Y3
INT Y4
INT Y5
INT Y6
INT Y7
INT Y8
INT Y9
INT Y10
INT Y11
INT Y12
INT Y13

Solution using LINGO is following:

Lingo 17.0 - Lindo Model - Lingo1 Eile Edit Solver Window Help Do x Lindo Model - Lingo1 Max 195000Y1+9600042+87000Y3+5200074 +233000Y5+57000Y6+117000Y7+88000Y8 +106000Y9+76000Y10+95000Yll+323000Y12 +175000913 Solution Report - Lingo1 Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Elapsed runtime seconds : 1624000. 1624000. 0.000000 s.t. 8 0.49 Model Class : PILP Total variables: Nonlinear variables: Integer variables: Total constraints: Nonlinear constraints: Total nonzeros: Nonlinear nonzeros: X1+x2+x3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13 <= 2 X1+X2+X3-Yl >= 0 X2+X3+X4+X6+X7-Y2 >= 0 X1+X2+X3+X4+X5-Y3 >= 0 X2+X3+X4+X5+X6+X8-Y4 >= 0 X3+X4+X5+X8+X9+X10-Y5 >= 0 X2+X4+X6+X7+X8+X11-Y6 >= 0 X2+X6+X7+X11-17 >= 0 X4+X5+X6+X8+X9+X11-Y8 >= 0 X5+X8+X9+X10+X11+X12-49 >= 0 X5+X9+X10+X12-410 >= 0 X6+X7+X8+X9+X11+x12+X13-yil >= 0 X9+X10+X11+X12+X13-Y12 >= 0 X11+x12x13-Y13 >= 0 END INT XI INT X2 INT X3 INT X4 INT X5 INT X6 INT X7 INT X8 INT X9 INT X10 INT X11 INT X12 INT X13 INT YI INT Y2 INT Y3 INT Y4 Variable HWEWNO CO WN Value 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 1.000000 Reduced Cost -195000.0 -96000.00 -87000.00 -52000.00 -233000.0 -57000.00 -117000.0 -88000.00 -106000.0 - 76000.00 -95000.00 -323000.0 -175000.0 0.000000 0.000000 0.000000 For Help, press F1 NUM MOD Ln 9, Col 17 2:30 pm

Variable www四www Y10 Y11 Value 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 X10 X11 X12 ZX13

X3 = 1

X11 = 1

ANSWER: Counties 3 and 11

c)

In the optimal solutions as determined in part a and b, county 5 is not selected for establishing PPB. Therefore, establishing a PPB in county 5 is not an optimal decision.