Deck 3: Applications of Linear and Integer Programming Models

Question 1

Nimble Automotive uses linear programming to produce a monthly production schedule for their manufacturing plant.Although the number of cars built is obviously an integer, the fractional part of a non-integer decision variable could be considered "work in progress" at the end of the month.

Answer 1

True

Question 2

The objective function coefficient for X₁ is currently $18 and for X₂ is $29, and the ranges of optimality for these coefficients are between $15 and $20 and between $25 and $35, respectively.If the objective function coefficients for X₁ and X₂ decline by $2 each, since both coefficients are still within their ranges of optimality, the optimal solution is guaranteed to remain the same.

Answer 2

False

Question 3

A linear programming model has a constraint that reflects a budget restriction of $100,000.The range of feasibility for this amount, reflected on the sensitivity report, is $85,000 to $325,000.Thus if the budget restriction is changed to $90,000, the optimal solution will not change.

Answer 3

False

Question 4

If at most 3 of 7 projects are to be performed, this can be modeled by X₁ + X₂ + X₃ + X₄ + X₅ + X₆ + X₇ $\le$ 3, where X₁, X₂, X₃, X₄, X₅, X₆, and X₇ are all restricted to be non-negative, have an upper bound of 1, and be integer-valued.

Question 5

The optimal solution to a supply chain management model can be found by solving the standalone separate components of the process.

Question 6

Relaxing the integer restrictions to an integer linear model produces an optimal solution of X₁ = 23 and X₂ = 15.This must also be the optimal solution to the integer linear model.

Question 7

The optimal solution value of an integer linear programming problem with a minimization objective function may not be __________ the optimal solution value if integer requirements are ignored.

A)the same as
B)less than
C)greater than
D)a rounded form of

Question 8

Which of the following is true when using summation variables?

A)The number of constraints will stay the same as in a formulation without the use of summation variables.
B)The number of variables will stay the same as in a formulation without the use of summation variables.
C)There are typically fewer non-zero input coefficients on the left side of the constraints.
D)Percentage constraints cannot be formulated without the use of summation variables.

Question 9

Hong Securities has $300,000 to invest in four stocks and three bonds.X₁, X₂, X₃, and X₄ denote the amounts invested in each of the stocks, and Y₁, Y₂, and Y₃ equal the amounts invested in each of the three bonds.Which of the following shows that at least 40% of the investment in stocks must be in stock 1?

A)X₁ $\ge$ 120,000
B)X₁ - .4X₂ -.4X₃ - .4X₄ $\ge$ 0
C).6X₁ - .4X₂ - .4X₃ - .4X₄ $\ge$ 0
D)X₁ $\ge$ .4(X₂ + X₃ + X₄ + Y₁ + Y₂ + Y₃)

Question 10

A maximization integer linear model is solved by first relaxing the integer restrictions, giving an optimal solution to the resulting linear model of X₁ = 6, X₂ = 11.The shadow price for the first constraint is $9, and the range of feasibility has a maximum increase of 20 and a maximum decrease of 5.Then for the integer model, X₁ = 6, X₂ = 11 is the optimal solution.If there is an increase of 3 units of the first resource, the optimal value of the objective function will increase by $27.

Question 11

The shadow price for a constraint that expresses that the availability of wood is 3000 board-feet is $0.50, and the range of feasibility is between 2800 and 4000 board-feet.Which of the following is not correct?

A)All 3000 board-feet of wood will be used.
B)If only 2900 board-feet of wood are available, the optimal objective function value will be reduced by $50.
C)If only 2900 board-feet of wood are available, the optimal solution will not change.
D)If 6000 board-feet of wood are available, the objective function value will increase by at least $500.

Question 12

It takes two pounds of steel and three pounds of copper to make a particular product.If there are 100 pounds of steel and 100 pounds of cooper available, one constraint will be 2X₁ + 3X₂ $\le$ 200.

Question 13

Joe Chan is modeling the installation of smoke alarms.The constraint Y₁ - Y₂ $\ge$ 0 uses the binary variables Y₁ for upstairs installation and Y₂ for downstairs installation.The constraint implies that if the first installation is performed, the second must also be performed.

Question 14

If project 1 is performed then project 2 will not be performed.This can be modeled by the constraint X₁ - X₂ $\le$ 1, where X₁ and X₂ are binary variables.

Question 15

In problem 2, let A = the total amount invested in stocks and B = the total amount invested in bonds.To state that at least 40% of the investment in stocks must be in stock 1, two constraints in the model would be:

A)X₁ - .4A $\ge$ 0, X₂ + X₃ + X₄ - A = 0
B)X₁ - .4A $\ge$ 0, X₁ + X₂ + X₃ + X₄ - A = 0
C)X₁ - .4A - .4B $\ge$ 0, A + B = 300,000
D)X₁ - .4A - .4B $\le$ 0, A + B = 300,000

Question 16

In a fixed charge integer linear model where there are variable profits of $45 and $80 for producing products 1 and 2, and a fixed charge of $1000 if any of product 2 is produced, the objective function can be modeled by MAX 45X₁ + 80X₂ - 1000Y₂, where Y₂ is a binary variable.

Question 17

The optimal solution obtained to a maximization integer linear programming model, where the integer requirements are at first ignored, provides a lower bound for the optimal objective function value of the integer model.

Question 18

One approach for solving an integer linear programming problem is simply to enumerate all feasible points and select the one yielding the "best" value for the objective function.However, the number of feasible integer points is usually so large, even for small problems, that this approach is inefficient for solving most models even with a computer.

Question 19

A management science professional with extensive modeling experience will focus on management concerns and need not spend much time questioning accountants and front line workers.

Question 20

You are currently paying $12 per hour for labor, and labor costs are included in the calculation of the objective function coefficients of a maximization problem.The shadow price for labor printed on the sensitivity analysis report is $8.It would be economically beneficial to you if you could secure extra labor for $15 per hour.

Question 21

Nike may build a factory at Millville (Y₁) or it may not.It may also build a regional warehouse at the same site (W₁).But Nike will not build a warehouse without also building a factory.So, its choices are: (1) neither factory nor warehouse; (2) factory only; or (3) factory and warehouse.The appropriate linear constraint to express this is:

A)Y₁ - W₁ $\le$ 1
B)Y₁ + W₁ $\le$ 1
C)Y₁ + W₁ $\le$ 0
D)Y₁ - W₁ $\ge$ 0

Question 22

Nike will build a factory at Millville or Greenfield, but not both.Alternatively, Nike may choose to build at neither location.The appropriate linear constraint to express this restriction using binary variables Y₁ and Y₂ is:

A)Y₁ - Y₂ $\le$ 1
B)Y₁ + Y₂ $\le$ 1
C)Y₁ + Y₂ = 1
D)Y₁ - Y₂ $\le$ 0

Question 23

Billyboy Toys' toy balls, bats, and gloves net profits, excluding fixed costs, of $7, $8, and $13 respectively.The products require 2, 3, and 5 production hours each.Using current facilities, 1600 production hours are available for the production of these products each month.If Billyboy also leases a second, smaller production facility for $3000 per month, this will increase the availability of production hours for these products by 800.This situation can be modeled using a mixed integer model that includes the following:

A)An objective function of: MAX 7X₁ + 8X₂ + 13X₃ Constraints including: 2X₁ + 3X₂ + 5X₃ $\le$ 2400
Variable constraints including X₁, X₂, X₃ $\ge$ 0
B)An objective function of: MAX 7X₁ + 8X₂ + 13X₃ - 3000Y₁ Constraints including: 2X₁ + 3X₂ + 5X₃ - 800Y₁ $\le$ 2400
Variable constraints including X₁, X₂, X₃= 0, Y₁ = 0 or 1
C)An objective function of: MAX 7X₁ + 8X₂ + 13X₃ - 3000Y₁ Constraints including: 2X₁ + 3X₂ + 5X₃ + 800Y₁ $\le$ 1600
Variable constraints including X₁, X₂, X₃ $\ge$ 0, Y₁ = 0 or 1
D)An objective function of: MAX 7X₁ + 8X₂ + 13X₃ - 3000Y₁

Question 24

What is the difference in the interpretation of reduced cost for an unbounded variable versus a bounded variable?

Question 25

XLB Sports has 30 franchises (teams).Although most of the teams make an annual profit, some teams report losses.An owner of a team that loses money can still make a profit when he sells the franchise since equity increases have been greater than reported losses.XLB has requested a model to determine which, if any, franchises should be eliminated.The costs associated with team elimination include the buyout of the owner, paying off existing contracts such as ballpark leases, and anticipated legal costs.The objective function is the overall profit of XLB.Because all teams must play on the same day, the number of teams must be an even number.Some teams may lose money at home but help other teams by drawing well in road games. Which of the following is true?

A)Teams reporting a loss should be eliminated.
B)You should use binary variables in a mixed integer model.
C)The problem can be solved by solving 30 team integer linear programming models.
D)The problem cannot be modeled.

Question 26

Explain the Excel formula SUMIF(F5:F12,"Daily",B5:B12).

Question 27

Review the Excel spreadsheet below. Based on the information in the spreadsheet, we can conclude:

A)There may be alternate optimal solutions.
B)The range of feasibility for Hours Used Electrical is unlimited.
C)For every extra unit of Hours Used Gas, the objective function value will increase by 80.
D)The range of optimality for House Inspections is 25 to 29.

Question 28

The availability of seats for ballgames at Oliver Field is $\begin{array} { l r r r } \text { Bleachers } & 4000 \text { seats } & A _ { 1 } & \\\text { General Admission } & 10,000 \text { seats } & A _ { 2 } \\\text { Grandstand } & 10,000 \text { seats } & A _ { 3 } \\\text { Luxury Boxes } & 1000 \text { seats } &A _ { 4 } &\end{array}$
A1 through A₄ represent the attendance in the different seating options at prices X₁, X₂, X₃, and X₄. Better seats must cost at least $1 more than the next lower category. If the team charges $1 per seat, the demand will be 25,000. For each $1 increase in ticket price, the demand drops by 1000. The team owner has set up an integer programming model to maximize revenue (not necessarily to sell out).
What prices should be charged? Is this a linear programming model?

Question 29

Why use summation variables, which make the linear programming model larger? The model can be completed without summation variables.

Question 30

You have formulated a problem with three constraints: (1) 2X₁ + 3X₂ + 4X₃ $\le$ 300; (2) X₁ + X₂ $\ge$ 40; (3) X₁ + X₂ + X₃ = 100.Which of the following states that at least 2 of these 3 constraints must hold? (M = a large value)

A)2X₁ + 3X₂ + 4X₃ - MY₁ $\le$ 300
X₁ + X₂ - MY₂ $\ge$ 40
X₁ + X₂ + X₃ - MY₃ = 100
Y₁ + Y₂ + Y₃ $\ge$ 2
B)2X₁ + 3X₂ + 4X₃ - MY₁ $\le$ 300
X₁ + X₂ - MY₂ $\ge$ 40
X₁ + X₂ + X₃ + MY₃ $\ge$ 100
Y₁ + Y₂ + Y₃ $\ge$ 2
C)2X₁ + 3X₂ + 4X₃ - MY₁ $\le$ 300
X₁ + X₂ + MY₂ $\ge$ 40
X₁ + X₂ + X₃ - MY₃ $\le$ 100
X₁ + X₂ + X₃ + MY₃ $\ge$ 100
Y₁ + Y₂ + Y₃ $\le$ 1
D)2X₁ + 3X₂ + 4X₃ - MY₁ $\le$ 300
X₁ + X₂ – MY₂ $\ge$ 40
X₁ + X₂ + X₃ – MY₃ $\le$ 100
Y₁ + Y₂ + Y₃ $\le$ 1

Question 31

Nike must build a factory at either Millville or Greenfield, but not both.The appropriate linear constraint to express this restriction using binary variables Y₁ and Y₂ is:

A)Y₁ - Y₂ $\le$ 1
B)Y₁ + Y₂ $\le$ 1
C)Y₁ + Y₂ = 1
D)Y₁ - Y₂ $\le$ 0

Question 32

Review this Excel spreadsheet: Based on the figures in the spreadsheet, we can conclude:

A)Atlantic Lighting is included in the optimal result.
B)Atlantic Lighting would be included in the optimal result if its objective coefficient were 20.333.
C)The range of optimality for Bedrock Insurance is 19.57 to 20.5.
D)The range of feasibility for the total expected return is 6980 to 7880.

Question 33

What is the initial step in the process of building linear models?

A)Define the constraints.
B)Graph the problem.
C)Determine decision variables.
D)Make sure a feasible solution exists.

Question 34

Marc Leaser, who has a PhD from MIT, has created a process model using first and second order differential equations.He correctly points out that your linear programming model of the same process makes significant simplifying assumptions which make the linear solution suboptimal.What is your reply to management?

Question 35

Two constraints in a model with binary variables Y₁, Y₂, Y₃ representing whether or not project 1, 2, or 3 will be performed are: Y₁ - Y₂ $\le$ 0 and Y₁ - Y₃ $\le$ 0.Taken together, what can be inferred from these constraints?

A)Projects 2 and 3 cannot both be performed.
B)Projects 2 and 3 must be performed if project 1 is performed.
C)Projects 2 and 3 may be performed is project is performed.
D)Project 1 must be performed.

Question 36

Silver's Gym offers Kickboxing I, Kickboxing II, and Kickboxing III, and Ms.DeVore insists on teaching all three classes.Otherwise, the gym will offer no kickboxing classes.How would you model this constraint?

A)X₁ + X₂ + X₃ = 0
B)X₁ + X₂ + X₃ = 3
C)X₁ + X₂ + X₃ $\le$ 0
D)X₁ - X₂ = 0 and X₁ - X₃ = 0

Question 37

What is wrong with this model? $\begin{aligned}\operatorname { MAX } X _ { 1 } + X _ { 2 } - X _ { 3 } & \\\operatorname { ST~X } _ { 1 } & \leq 10 \\X _ { 2 } & \leq 10 \\X _ { 3 } \leq 10 & \\X _ { 1 } - X _ { 2 } & \geq 5 \\X _ { 1 } , X _ { 2 } , X _ { 3 } \geq 0 &\end{aligned}$

Question 38

What is Data Envelopment Analysis?

A)A linear programming based approach to determine the relative efficiency of entities with similar goals and objectives.
B)A decision support system that envelops the entire manufacturing and shipping process into an integrated system.
C)An integer linear programming technique involving solving a series of linear programming models and using the solutions as bounds on the integer solution.
D)A form of sensitivity analysis that allows the simultaneous changing of multiple decision variable values.

Question 39

Adding a constraint increases the time needed to solve a linear programming model.Why then might adding a summation variable actually improve model efficiency?

Question 40

Caspian Seafoods has recently purchased a very large property for possible expansion of its business.On this property, Caspian may construct a large plant (X₁) or a small plant (X₂).In addition, if, and only if, it constructs either plant, it may or may not choose to build a warehouse (X₃) as well.That is, no plant also means no warehouse.Caspian has other expansion opportunities as well, and is using binary (0 - 1) programming for evaluation.Write a linear constraint (or constraints) that adequately and appropriately reflects the stated conditions on X₁, X₂, and X₃ under binary programming.

Question 41

Eastern Engineering Company is trying to decide which of 6 projects to perform during the next quarter.The net present value, the estimated cost, and the number of engineers and staff personnel required for each project are given in the following table. $\begin{array}{ccccc}\text { Project } & \text { Net Present} & \text { Cost } & \text { Engineers } & \text { Staff }\\ &\text { Value } & \left(\$ 1000^{\prime} s\right) & \text { Required } & \text { Required }\\&(\$ 1000^{\prime} \mathrm{s})\\1 & 100 & 35 & 5 & 2 \\2 & 145 & 65 & 8 & 3 \\3 & 200 & 95 & 11 & 2 \\4 & 250 & 180 & 4 & 2 \\5 & 500 & 250 & 16 & 7 \\6 & 695 & 475 & 19 & 11\end{array}$
Eastern has a $550,000 budget and 30 engineers and 15 staff available.Which projects should Eastern perform during the quarter?

Question 42

Suppose in problem 4, Clancy's Casino pays a wage differential depending on the hours worked.In particular, between midnight and 0700, it pays dealers $16 per hour, between 0700 and 1900 $10 per hour, and between 1900 and midnight $12 per hour.Modify your formulation to problem 4, and determine the minimum cost shift schedule for Clancy's.

Question 43

X₁ is limited to 40% of the total, as modeled by the constraint .6X₁ - .4X₂ - .4X₃ $\le$ 0.Rewrite this as two constraints using a summation variable.

Question 44

For the Eastern Engineering problem in question 7, suppose the budget is increased to $600,000 and that the additional engineers or additional staff (but not both) can be hired so that only one of the engineer or staff limitations must hold (i.e.at least one of the two constraints holds).Also, if project 2 is performed, project 5 will not be performed, at least two of projects 1, 2, and 3 should be performed, and if project 3 is performed, project 4 should be performed.Which projects should Eastern undertake under these conditions?

Question 45

Clancy's Casino, in Muledeer, Nevada, is open 24 hours a day, seven days a week.Along with all the other attractions and diversion, Clancy's operates a variety of gaming tables.Dealers at these tables are interchangeable.The casino has the following daily requirements for dealers: $\begin{array} { c c } \text { Time } & \text { Minimum \# of dealers } \\0100 - 0500 & 7 \\0500 - 0900 & 4 \\0900 - 1300 & 9 \\1300 - 1700 & 12 \\1700 - 2100 & 15 \\2100 - 0100 & 17\end{array}$
A dealer may start work at the beginning of any one of the six shifts and, having begun, works eight consecutive hours.Find the employee schedule that minimizes the total number of dealers required, meeting the minimum level of each shift's requirements.

Question 46

Kings Department Store has 625 rubies, 800 diamonds, and 700 emeralds from which they will make bracelets and necklaces that they have advertised in their Christmas brochure.Each of the rubies is approximately the same size and shape as the diamonds and the emeralds.Kings will net a profit of $250 on each bracelet, which is made with 2 rubies, 3 diamonds, and 4 emeralds, and $500 on each necklace, which includes 5 rubies, 7 diamonds, and 3 emeralds.How many of each should Kings make to maximize its profit?

Question 47

Heavenly Casket Company is trying to choose sites for the production of its "mail order" caskets.It is considering plants in Chicago, Dallas, and Atlanta.Finished caskets will then be sent to their two distribution sites in Trenton and Tacoma, which take orders over the internet.Heavenly expects demand of 4000 caskets per year in Trenton and 2500 in Tacoma.The table below gives annual plant capacity, fixed yearly operating expenses, unit production costs, and unit transportation costs between possible plant locations and the distribution sites: $\begin{array}{cccccc}\text { Site } & \text { Capacity } & \begin{array}{c}\text { Fixed } \\\text { Annual } \\\text { Operating } \\\text { Costs }\end{array} & \begin{array}{c}\text { Production } \\\text { Cost Per } \\\text { Unit }\end{array} & \begin{array}{c}\text { Shipping } \\\text { to Trenton }\end{array} & \begin{array}{c}\text { Shipping } \\\text { to Tacoma }\end{array} \\\text { Chicago } & 3500 & \$ 40,000 & \$ 200 & 75 & 50 \\\text { Dallas } & 3200 & \$ 42,000 & \$ 160 & 95 & 70 \\\text { At lanta } & 3700 & \$ 45,000 & \$ 170 & 82 & 98\end{array}$
Which plants should be operational, and what should the production quantities and shipping pattern be to minimize Heavenly's annual expenses?

Question 48

The optimal linear programming solution to the Kings Department Store problem in problem 1 is 131.58 bracelets and 57.89 necklaces.
A.Characterize the (i) rounded off solution; and (ii) the rounded down solution.
B.The shadow price associated with emeralds in the linear programming solution is $13.16, and the upper limit of the range of feasibility for emeralds is 1066.67.A gem buyer at Kings reasoned that since the purchase of emeralds is an included cost, he should be willing to pay up to $13.16 above Kings' current cost for emeralds.When he found a seller who would sell him 100 additional emeralds at $13.00 over the original cost, he purchased them, figuring it would add 100($13.16 - $13.00) = $16 to company profits.He said, "Hey, $16 is $16." Why might he be looking for another job?

Question 49

Wisconsin State University is planning to advertise its new degree program in Professional Business in several media--television commercials on the local cable station, advertisements in the local community college newspaper, and manning a booth at the county fair.Preliminary estimates are that each television spot will reach 1000 potential students, each newspaper ad will reach 100 potential students, and each day at the county fair will reach 500 potential students.There is a $7500 advertising budget, and the university has negotiated a rate of $825 per ad on the cable station, $85 per ad in the newspaper, and $1150 for a booth at the 3-day county fair.What should be its advertising strategy?

Question 50

Why use hidden cells in an Excel spreadsheet representation of a linear programming model?

Question 51

The Data Envelopment Analysis model gives the following equation: $\frac {\text { Relative Output Value }} { \text {Relative Input Value } }$ = $\frac{5 Y_{1}}{2 X_{1}}\frac{+7 Y_{2}+9 X_{2}}{+4X_{4}+3 X_{3}}$
Create a linear programming model for this DEA problem by converting this equation to a linear objective function and two linear constraints.

Question 52

Appalachian Coal Company must mine a minimum of 30 tons of coal weekly.It can mine at any of four sites.Relevant data concerning fixed weekly operation costs of the sites, variable mining costs per ton of coal, and estimated maximum weekly output of coal at each site are given in the following table.Formulate a mixed integer programming model and solve for the mining strategy that will minimize total weekly costs. $\begin{array}{lccc}\text { Site } & \text { Weekly Operating } & \text { Mining Costs Per } & \text { Maximum Weekly } \\ &\text { Costs }\left(\$ 1000^{\prime} s\right) & \text { Ton }\left(\$ 1000^{\prime} s\right) & \text { Output (Tons) }\\\mathrm{A} & \$ 5 & \$ 12 & 10 \\\mathrm{~B} & \$ 6 & \$ 8 & 20 \\\mathrm{C} & \$ 2 & \$ 14 & 25 \\\mathrm{D} & \$ 7 & \$ 6 & 15\end{array}$

Question 53

An assembly line has 4 stations.All laborers are trained to operate all stations.The union contract limits laborers to a 40 hour work week with no overtime.The company is contracted to produce 320 units per week, with a profit of $1000 per unit.Each unit must proceed through all 4 stations in order.However, there is sufficient work in progress inventory to keep all stations busy at all times.Station information is detailed in the following table: $\begin{array}{lcc}\text { Station } & \text { Time Required Per } & \text { cost to Build the } \\& \text { Unit in minutes } & \text { Station }\\1 & 15 & \$ 5000 \\2 & 20 & \$ 8000 \\3 & 30 & \$ 4000 \\4 & 20 & \$ 10,000\end{array}$ How many stations of each type does the assembly line require to meet demand?