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 21

True/False

Review LaterAdd Note

Review Later

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

Correct Answer

verified

Show Answer

Question 22

Essay

Review LaterAdd Note

Review Later

Solve the following problem graphically. $\begin{array} { l l } \text { Max } & 5 x + 6 y \\\text { s.t. } & 17 x + 8 y \leq 136 \\& 3 x + 4 y \leq 36 \\& x , y \geq 0 \text { and 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.

Correct Answer

verified

a.The feasible region is those integer v...

View Answer

Show Answer

Question 23

Essay

Review LaterAdd Note

Given the following all-integer linear program: Max $15 x _ { 1 } + 2 x _ { 2 }$ s. t. $7 x _ { 1 } + x _ { 2 } \leq 23$ $3 x _ { 1 } - x _ { 2 } \leq 5$ $x _ { 1 } , x _ { 2 } \geq 0$ and integer a. Solve the problem as an LP, ignoring the integer constraints. b. What solution is obtained by rounding up fractions greater than or equal to 1/2? Is this the optimal integer solution? c. What solution is obtained by rounding down all fractions? Is this the optimal integer solution? Explain. d. Show that the optimal objective function value for the ILP is lower than that for the optimal LP. e. Why is the optimal objective function value for the ILP problem always less than or equal to the corresponding LP's optimal objective function value? When would they be equal? Comment on the MILP's optimal objective function compared to the corresponding LP & ILP.

Kloos Industries has projected the availability of capital over each of the next three years to be $850,000,$1,000,000,and $1,200,000,respectively.It is considering four options for the disposition of the capital: (1)Research and development of a promising new product (2)Plant expansion (3)Modernization of its current facilities (4)Investment in a valuable piece of nearby real estate Monies not invested in these projects in a given year will NOT be available for following year's investment in the projects.The expected benefits three years hence from each of the four projects and the yearly capital outlays of the four options are summarized in the table below in $1,000,000's. In addition,Kloos has decided to undertake exactly two of the projects,and if plant expansion is selected,it will also modernize its current facilities. $\begin{array} { l c c c c } & { \text { Capital Outlays } } &&& \text { Projected } \\\text { Options } & \text { Year 1 } & \text { Year 2 } & \text { Year 3 } & \text { B enefits } \\\hline \text { New Product R\&D } & .35 & .55 & .75 & 5.2 \\\text { Plant Expansion } & .50 & .50 & 0 & 3.6 \\\text { Modernization } & .35 & .40 & .45 & 3.2 \\\text { Real Estate } & .50 & 0 & 0 & 2.8\end{array}$ Formulate and solve this problem as a binary programming problem.

The classic assignment problem can be modeled as a 0-1 integer program.

The product design and market share optimization problem presented in the textbook is formulated as a 0-1 integer linear programming model.

Most practical applications of integer linear programming involve only 0 - 1 integer variables.

Rounded solutions to linear programs must be evaluated for

Why are 0 - 1 variables sometimes called logical variables?

Hansen Controls has been awarded a contract for a large number of control panels.To meet this demand,it will use its existing plants in San Diego and Houston,and consider new plants in Tulsa,St.Louis,and Portland.Finished control panels are to be shipped to Seattle,Denver,and Kansas City.Pertinent information is given in the table. $\begin{array} { l | c | c c c | c } & &{ \text { Shipping Cost to Destination: } } & \\{ \text { Sources } } & \begin{array} { c } \text { Construction } \\\text { Cost }\end{array} & \text { Seattle } & \text { Denver } & \begin{array} { c } \text { Kansas } \\\text { City }\end{array} & \text { Capacity } \\\hline \text { San Diego } & \cdots & 5 & 7 & 8 & 2,500 \\\text { Houston } & \cdots & 10 & 8 & 6 & 2,500 \\\text { Tulsa } & 350,000 & 9 & 4 & 3 & 10,000 \\\text { St. Louis } & 200,000 & 12 & 6 & 2 & 10,000 \\\text { Portland } & 480,000 & 4 & 10 & 11 & 10,000 \\\hline & \text { Demand } & 3,000 & 8,000 & 9,000 &\end{array}$ Develop a model whose solution would reveal which plants to build and the optimal shipping schedule.

Integer linear programs are harder to solve than linear programs.

Modeling a fixed cost problem as an integer linear program requires

Some linear programming problems have a special structure that guarantees the variables will have integer values.

Solve the following problem graphically. $\begin{array} { l l } \text { Min } & 6 x + 11 y \\\text { s.t. } & 9 x + 3 y \geq 27 \\& 7 x + 6 y \geq 42 \\& 4 x + 8 y \geq 32 \\& x , y \geq 0 \text { and integer }\end{array}$ a.Graph the constraints for this problem. Indicate all feasible solutions. b.Find the optimal solution to the LP Relaxation. Round up to find a feasible integer solution. Is this solution optimal? c.Find the optimal solution.

Generally,the optimal solution to an integer linear program is less sensitive to the constraint coefficients than is a linear program.

A multiple choice constraint involves selecting k out of n alternatives,where k  2.

Solve the following problem graphically. $\begin{array} { l l } \operatorname { Max } & x + 2 y \\\text { s.t. } & 6 x + 8 y \leq 48 \\& 7 x + 5 y \geq 35 \\& x , y \geq 0 \text { and } 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.

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

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.

Give a verbal interpretation of each of these constraints in the context of a capital budgeting problem. a.x₁  x₂  0 b.x₁  x₂ = 0 c.x₁ + x₂ + x₃  2