FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 11: Integer Linear Programming

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 31

Multiple Choice

Review LaterAdd Note

Review Later

To perform sensitivity analysis involving an integer linear program,it is recommended to

A) use the dual prices very cautiously.
B) make multiple computer runs.
C) use the same approach as you would for a linear program.
D) use LP relaxation.

Correct Answer

verified

Show Answer

Question 32

Essay

Review LaterAdd Note

Review Later

Grush Consulting has five projects to consider.Each will require time in the next two quarters according to the table below. ​ $\begin{array} { c c c c } \text { Project } & \text { Time in first quarter } & \text { Time in second quarter } & \text { Revenue } \\\hline \text { A } & 5 & 8 & 12000 \\\text { B } & 3 & 12 & 10000 \\\text { C } & 7 & 5 & 15000 \\\text { D } & 2 & 3 & 5000 \\\text { E } & 15 & 1 & 20000\end{array}$ Revenue from each project is also shown.Develop a model whose solution would maximize revenue,meet the time budget of 25 in the first quarter and 20 in the second quarter,and not do both projects C and D.

Correct Answer

verified

Let A = 1 if project A is selected,0 oth...

View Answer

Show Answer

Question 33

True/False

Review LaterAdd Note

The constraint x₁ − x₂ = 0 implies that if project 1 is selected,project 2 cannot be.

Let x₁ and x₂ be 0 - 1 variables whose values indicate whether projects 1 and 2 are not done or are done.Which answer below indicates that project 2 can be done only if project 1 is done?

Given the following all-integer linear program: ​ Max $3 x _ { 1 } + 2 x _ { 2 }$ s.t. $\begin{array} { l l } \text { M.t. } & 3 x _ { 1 } + 2 x _ { 2 } \\ & 3 x _ { 1 } + x _ { 2 } \leq 9 \\ & x _ { 1 } + 3 x _ { 2 } \leq 7 \\ & - x _ { 1 } + x _ { 2 } \leq 1 \\ & x _ { 1 } , x _ { 2 } \geq 0 \text { and integer } \end{array}$ a.​Solve the problem as a linear program ignoring the integer constraints.Show that the optimal solution to the linear program gives fractional values for both x₁ and x₂. b.​What is the solution obtained by rounding fractions greater than of equal to 1/2 to the next larger number? Show that this solution is not a feasible solution. c.What is the solution obtained by rounding down all fractions? Is it feasible? d.​ ​ Enumerate all points in the linear programming feasible region in which both x₁ and x₂ are integers,and show that the feasible solution obtained in (c)is not optimal and that in fact the optimal integer is not obtained by any form of rounding.

List and explain four types of constraints involving 0-1 integer variables only.

Which of the following applications modeled in the textbook is an example of a fixed cost problem?​

​Assuming W₁,W₂ and W₃ are 0 -1 integer variables,the constraint W₁ + W₂ + W₃ < 1 is often called a

If a problem has only less-than-or-equal-to constraints with positive coefficients for the variables,rounding down will always provide a feasible integer solution.

Simplon Manufacturing must decide on the processes to use to produce 1650 units.If machine 1 is used,its production will be between 300 and 1500 units.Machine 2 and/or machine 3 can be used only if machine 1's production is at least 1000 units.Machine 4 can be used with no restrictions. ​ $\begin{array} { c c c c c } \text { Machine } & \begin{array} { c } \text { Fixed } \\\text { cost }\end{array} & \begin{array} { c } \text { Variable } \\\text { cost }\end{array} & \begin{array} { c } \text { Minimum } \\\text { Production }\end{array} & \begin{array} { c } \text { Maximum } \\\text { Production }\end{array} \\\hline 1 & 500 & 2.00 & 300 & 1500 \\2 & 800 & 0.50 & 500 & 1200 \\3 & 200 & 3.00 & 100 & 800 \\4 & 50 & 5.00 & \text { any } & \text { any }\end{array}$ (HINT: Use an additional 0 - 1 variable to indicate when machines 2 and 3 can be used. )

Rounding the solution of an LP Relaxation to the nearest integer values provides

The 0-1 variables in the fixed cost models correspond to

Why are 0 - 1 variables sometimes called logical variables?

Solve the following problem graphically. ​ $\begin{array} { l l } \text { Max } & X + 2 Y \\\text { s.t. } & 6 X + 8 Y \leq 48 \\& 7 X + 5 Y \geq 35 \\& X , Y \geq 0 \\& Y \text { is integer }\end{array}$ a.Graph the constraints for this problem.Indicate all feasible solutions. b.Find the optimal solution to the LP Relaxation.Round down to find a feasible integer solution.Is this solution optimal? c.Find the optimal solution.

​The use of integer variables creates additional restrictions but provides additional flexibility.Explain.

If the LP relaxation of an integer program has a feasible solution,then the integer program has a feasible solution.

In a model involving fixed costs,the 0 - 1 variable guarantees that the capacity is not available unless the cost has been incurred.

Slack and surplus variables are not useful in integer linear programs.

Rounded solutions to linear programs must be evaluated for

The LP Relaxation contains the objective function and constraints of the IP problem,but drops all integer restrictions.