SP23: BUSINESS ANALYTICS & MODELING: 20646, Fall 2022 Chapter 6 Assignment (Homework)   Consider the following optimization problem: MIN:      X1           +            X2           Subject to:          −4X1      +            4X2         ≤            1 −8X1      +            10X2      ≥            12 X1,          X2           ≥            0 (a) What is the optimal solution to this LP problem? (X1, X2) =       Incorrect: Your answer is incorrect

SP23: BUSINESS ANALYTICS & MODELING: 20646, Fall 2022

Chapter 6 Assignment (Homework)

 

Consider the following optimization problem:

MIN:      X1           +            X2          

Subject to:          −4X1      +            4X2         ≤            1

−8X1      +            10X2      ≥            12

X1,          X2           ≥            0

(a)

What is the optimal solution to this LP problem?

(X1, X2) =

 

 

 

Incorrect: Your answer is incorrect.

 

 

(b)

Now suppose that

X1

 and

X2

 must be integers. What is the optimal solution?

(X1, X2) =

 

 

 

Incorrect: Your answer is incorrect.

 

 

(c)

What general principle of integer programming is illustrated by this question?

The optimal integer solution to an ILP is not, in general, also a basic feasible solution to the continuous LP.

The optimal integer solution to an ILP is, in general, also an optimal solution to the continuous LP.   

The optimal objective function value of a minimization ILP is always smaller than that of the continuous solution.

The optimal objective function value of a minimization ILP is always higher than that of the continuous solution.

The optimal integer solution to an ILP cannot, in general, be obtained by rounding the continuous solution.

Correct: Your answer is correct.

Need Help? Read It

 

2.

[–/5 Points]

 

DETAILS

RAGSMDA9 6.E.009.

 

MY NOTES

 

ASK YOUR TEACHER

 

PRACTICE ANOTHER

Enrique Brava is responsible for upgrading the wireless network for his employer. He has identified seven possible locations to install new nodes for the network. Each node can provide service to different regions within his employer's corporate campus. The cost of installing each node and the regions that can be served by each node are summarized below.

Node 1: Regions 1, 2, 5; Cost $100

Node 2: Regions 3, 6, 7; Cost $900

Node 3: Regions 2, 3, 7, 9; Cost $750

Node 4: Regions 1, 3, 6, 10; Cost $1,350

Node 5: Regions 2, 4, 6, 8; Cost $1,000

Node 6: Regions 4, 5, 8, 10; Cost $500

Node 7: Regions 1, 5, 7, 8, 9; Cost $600

(a)

Formulate an ILP for this problem to minimize cost (in dollars) while providing coverage to every region. (Let Xi = 1 if node i is installed and 0 otherwise.)

MIN:     

 

Subject to:

Region 1              

 

Region 2              

 

Region 3              

 

Region 4              

 

Region 5              

 

Region 6              

 

Region 7              

 

Region 8              

 

Region 9              

 

Region 10           

 

Xi binary

(b)

Implement your model in a spreadsheet and solve it. What is the optimal solution?

(X1, X2, X3, X4, X5, X6, X7) =

 

 

 

 

Need Help? Read It

 

3.

[–/5 Points]

 

DETAILS

RAGSMDA9 6.E.011.

 

MY NOTES

 

ASK YOUR TEACHER

 

PRACTICE ANOTHER

Garden City Beach is a popular summer vacation destination for thousands of people. Each summer, the city hires temporary lifeguards to ensure the safety of the vacationing public. Garden City's lifeguards are assigned to work five consecutive days each week and then have two days off. However, the city's insurance company requires them to have at least the following number of lifeguards on duty each day of the week.

Minimum Number of Lifeguards Required Each Day

Sunday Monday               Tuesday               Wednesday        Thursday             Friday    Saturday

Lifeguards           19           18           16           16           16           15           20

The city manager would like to determine the minimum number of lifeguards that will have to be hired.

(a)

Formulate an ILP for this problem. (Let X1 be the number of lifeguards whose shift starts on Sunday, X2 be the number of lifeguards whose shift starts on Monday, …, and X7 be the number of lifeguards whose shift starts on Saturday.)

MIN:     

 

Subject to:

Sunday constraint           

 

Monday constraint         

 

Tuesday constraint         

 

Wednesday constraint 

 

Thursday constraint       

 

Friday constraint             

 

Saturday constraint        

 all Xi ≥ 0

all Xi must be integers

(b)

Implement your model in a spreadsheet and solve it. What is the optimal solution?

(X1, X2, X3, X4, X5, X6, X7) =

 

 

 

 

(c)

Several lifeguards have expressed a preference to be off on Saturdays and Sundays. What is the maximum number of lifeguards that can be off on the weekend without increasing the total number of life guards required?

 lifeguard(s)

Need Help? Read It

 

4.

[–/5 Points]

 

DETAILS

RAGSMDA9 6.E.018.

 

MY NOTES

 

ASK YOUR TEACHER

 

PRACTICE ANOTHER

Radford Castings can produce brake shoes on six different machines. The following table summarizes the manufacturing costs associated with producing the brake shoes on each machine along with the available capacity on each machine. If the company has received an order for 1,800 brake shoes, how should it schedule these machines?

Machine              Fixed Cost (in dollars)     Variable Cost (in dollars)               Capacity

1              1,000     21           450

2              950         23           550

3              875         25           800

4              850         24           350

5              800         20           550

6              700         26           750

(a)

Formulate an ILP model for this problem to minimize the total cost (in dollars). (Let Xi = the number of brake shoes produced by machine i. Let Yi = 1 if Xi > 0 and 0 otherwise. In your linking constraints, use the smallest possible value of Mi.)

MIN:     

 

Subject to:

total brake shoes produced       

 

linking constraint for Y1

 

linking constraint for Y2

 

linking constraint for Y3

 

linking constraint for Y4

 

linking constraint for Y5

 

linking constraint for Y6

 

Xi ≥ 0 and integer

Yi binary

(b)

Create a spreadsheet model for this problem and solve it. What is the optimal solution?

(X1, X2, X3, X4, X5, X6) =

 

 

 

 

Need Help? Read It Watch It

 

5.

[–/5 Points]

 

DETAILS

RAGSMDA9 6.E.020.

 

MY NOTES

 

ASK YOUR TEACHER

 

PRACTICE ANOTHER

A developer of video game software has seven proposals for new games. Unfortunately, the company cannot develop all the proposals because its budget for new projects is limited to $950,000 and it has only 20 programmers to assign to new projects. The financial requirements, returns, and the number of programmers required by each project are summarized in the following table. Projects 2 and 6 require specialized programming knowledge that only one of the programmers has. Both of these projects cannot be selected because the programmer with the necessary skills can be assigned to only one of the projects. (Note: All dollar amounts represent thousands.)

Project Programmers Required Capital Required               Estimated NPV

1              7              $250       $650

2              6              $175       $425

3              9              $300       $275

4              5              $150       $550

5              6              $145       $700

6              4              $160       $450

7              8              $325       $750

(a)

Formulate an ILP model for this problem to maximize NPV (in thousands of dollars). (Let Xi = 1 if project i is selected and 0 otherwise. In your projects 2 and 6 constraint, only use coefficients of 1 or −1.)

MAX:    

 

Subject to:

total programmers constraint    

 

budgetary constraint     

 

projects 2 and 6 constraint          

 

Xi binary

(b)

Create a spreadsheet model for this problem and solve it. What is the optimal solution?

(X1, X2, X3, X4, X5, X6, X7) =