FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 7: Integer Linear Programming

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 1

Essay

Review LaterAdd Note

Review Later

Consider a capital budgeting example with five projects from which to select.Let x_i = 1 if project i is selected,0 if not,for i = 1,… ,5.Write the appropriate constraint(s)for each condition.Conditions are independent. a.Choose no fewer than three projects. b.If project 3 is chosen,project 4 must be chosen. c.If project 1 is chosen,project 5 must not be chosen. d.Projects cost 100,200,150,75,and 300,respectively.The budget is 450. e.No more than two of projects 1,2,and 3 can be chosen.

Correct Answer

verified

Show Answer

Question 2

True/False

Review LaterAdd Note

Review Later

For the classic assignment problem,the optimal linear programming solution will consist of 0s and 1s.

Correct Answer

verified

Show Answer

Question 3

Essay

Review LaterAdd Note

Given the following all-integer linear program: ​ 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 solution is obtained by rounding fractions greater than or 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 part (c)is not optimal and that in fact the optimal integer is not obtained by any form of rounding.

The solution to the LP Relaxation of a maximization integer linear program provides a(n)

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

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: a.Research and development of a promising new product b.Plant expansion c.Modernization of its current facilities d.Investment in a valuable piece of nearby real estate ​ Monies not invested in these projects in a given year will NOT be available for the 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 millions of dollars. In addition,Kloos has decided to undertake exactly two of the projects.If plant expansion is selected,it will also modernize its current facilities. ​ Formulate and solve this problem as a binary programming problem.

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 below.​ ​ Develop a model whose solution would reveal which plants to build and the optimal shipping schedule.

In general,whenever rounding has a minimal impact on the objective function and constraints,most managers find it acceptable.

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

Rounded solutions to linear programs must be evaluated for

Solve the following problem graphically. ​ 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.

Let x₁,x₂,and x₃ be 0-1 variables whose values indicate whether the projects are not done (0) or are done (1) .Which of the following answers indicates that at least two of the projects must be done?

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

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

A business manager for a grain distributor is asked to decide how many containers of each of two grains to purchase to fill its 1,600-pound capacity warehouse.The table below summarizes the container size,availability,and expected profit per container upon distribution.​ ​ a.Formulate as a linear program with the decision variables representing the number of containers purchased of each grain.Solve for the optimal solution. b.What would be the optimal solution if you were not allowed to purchase fractional containers? c.There are three possible results from rounding an LP solution to obtain an integer solution: (1)The rounded optimal LP solution will be the optimal IP solution. (2)The rounded optimal LP solution gives a feasible,but not optimal IP solution. (3)The rounded optimal LP solution is an infeasible IP solution. ​ For this problem,(i)round down all fractions; (ii)round up all fractions; and (iii)round off (to the nearest integer)all fractions (Note: Two of these are equivalent.)Which result above (1,2,or 3)occurred under each rounding method?

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

Given the following all-integer linear programming problem: ​ Max 3x₁ + 10x₂ ​ s.t.2x₁ + x₂ < 5 x₁ + 6x₂ < 9 x₁ - x₂ > 2 x₁,x₂ > 0 and integer ​ a.Solve the problem graphically as a linear program. b.Show that there is only one integer point and that it is optimal. c.Suppose the third constraint was changed to x₁ - x₂ > 2.1.What is the new optimal solution to the LP? To the ILP?

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

In general,rounding large values of decision variables to the nearest integer value causes fewer problems than rounding small values.

The constraint x₁ + x₂ + x₃ + x₄ ≤ 2 means that two out of the first four projects must be selected.