1. Young MBA Erica Cudahy may invest up to $1, 000.   She can invest her money in stocks and loans.  Each dollar invested in stocks yields 10 cent proit, and each dollar invested in a loan yields 5 cent proit.  At least 30% of all money invested must be in stocks, and at least $400 must be in loans.  Formulate an LP that can be used to maximize total proit earned from Erica’s investment. Then graphically solve the LP.

2.  Daisy drugs manufactures two drugs:  1 and 2.  The drugs are produced by blending two chemicals:  1 and 2.   By weight,  drug  1 must contain at least 65% chemical  1, and drug 2 must contain at least 55% chemical 1.  Drug  1 sells for $6 per ounce and drug 2 sells for $4 per ounce.  Chemicals 1 and 2 can be produced using either of two production processes. Running process 1 for an hour requires 3 oz of raw material and 2 hours skilled labor and yields 3 oz of each chemical.  Running process 2 for an hour requires 2 oz of raw material and 3 hours of skilled labor and yields 3 oz of chemical 1 and 1 oz of chemical 2.  A total of 120 hours of skilled labor and 100 oz of raw material

are available. Formulate an LP that can be used to maximize Daisy’s sales revenues.

3.  Consider the following Optimal Paper Recycling problem.

A company produces 5 types of paper products:

1   Newsprint.

2   Wall paper.

3    Coated paper.

4    Uncoated book paper.

5   Writing and related paper.

For each type,j, of paper, the demand, dj  is given in thousands of tons (see table be- low). The company meets the demand for its products in two ways.  It can manufacture new paper from fresh wood and it can also recycle old paper.  A certain percentage, mj , of the demand for paper type j must be satisied with paper produced from fresh wood, but the rest can come from recycling.  For example, all of the newsprint can come from recycled paper, but at least 47% of the wall paper must come from fresh wood.

When paper is recycled, there is some loss of material.  As a result, x tons of recycled paper produce fewer than x tons of new paper.  The actual amount, tj x, depends on the type of new paper being produced.  For example, 100 tons of old wall paper can be recycled into 85 tons of newsprint.

In the table below, the sj  column indicates the amount of old paper (in thousands of tons) of type j that is available for recycling.  Note that a given type of recycled paper can only be used to produce certain types of new paper. This information is given in the last column of the table.

j    dj              mj         sj            tj            Can be used to make

For ecological and economic reasons, the company wishes to use as little fresh wood as possible.  Formulate a linear program to solve the problem of producing enough of each product to meet the demand in such a way as to minimize the use of fresh wood.

Deine all variables, state clearly all assumptions, and briely justify each of the con- straints and the objective function.

4. A company produces two kinds of products.  A product of the irst type requires 1/4 hours of assembly labor, 1/8 hours of testing, and $1.20 worth of raw materials.  A product of the second type requires 1/3 hours of assembly, 1/3 hours of testing, and $0.90 worth of raw materials.  Given the current personnel of the company, there can be at most 90 hours of assembly labor and 80 hours of testing, each day.  Products of the irst and second type have a market value of $9 and $8, respectively.  You may assume demand for both products is unlimited.

(a)  Formulate a linear programming problem that can be used to maximize the daily proit of the company.

(b)  Consider the following modiications of the problem:

(1)  Suppose that up to 50 hours of overtime assembly labor can be scheduled, at a cost of $7 per hour.

(2)  Suppose that the raw material supplier provides a 10% discount if the daily bill is above $300.

For each of the two modiications, specify if it can be done with a linear program, or if it requires integer variables.   Speciically,  show how you would add these modiications to the formulation in both cases.  Please specify all new variables and all new constraints in your answer.

5. You are interested in solving a continuous knapsack problem like the one shown in discussion. In this one you have 4 diferent types of products you can put in your bag, each of which has a related value, weight and volume.  You also are required to carry a minimum of amount of water.  The optimization model is:

max 1x1 + 4x2 + 3x3 + 4x4

s.t. 3x1 + 2x2 + x3 + 2x4  三 100 (Volume of the bag)

(g) Does the optimal solution or optimal objective function change if you ind a bag with 50 units less of volume and the same weight capacity?

(h)  How does the optimal objective function change if we are allowed to carry 100 more units of weight?

6. You’re choosing decorations and candies for your house to make it a cool place for Halloween. You visited the Awazon webpage and made a detailed list of ive products and  a table  specifying the minimum  and  maximum  amount of each that you  can purchase, the cost of the product, its spookiness quality (decoration quality) and its sweetness quality (sugar level). The table is shown below:

You have set the following constraints:

. You can spend at most $200.

. Your house is required to have a minimum spookiness level of 60 and a minimum sweetness level of 70.

. You should buy at least two sets of lights but no more than three.  To make the decoration coherent, if you buy two sets of lights, the two of them should be of the same type, and if you buy three sets of lights then the three of them can not all be of the same type.

. If you buy three sets of lights then you won’t have space for the spiderwebs.

. You can assume that the amount of skittles and skull candies you buy can be be expressed by continuous variables.

. Of the total amount of candies you purchase, at most 70% of them can be of the same type.

. You had a family conversation and decided that each unit of spookiness gives the house 1.5 units of utility, each unit of sweetness gives a 1.0 unit of utility, and that you don’t care if you spend all the budget or not.

Write an MILP (Mixed Integer Linear Program) formulation that could solve the prob- lem of maximizing the total utility units while satisfying all the constraints above. Clearly deine any variables and parameters you use and explain the purpose of each constraint.

7. You are going to the racetrack to beton horses!  There are six horses available, and you may choose as many or as few as you wish to bet on. If you bet on a horse to win the race, your bet amount must be exactly $1.  Additionally, you have a heart condition, and the doctor has told you that you may not tolerate too much excitement.  The horses available to be bet on, their expected payofs for a $1 bet, and the excitement that comes with them, are as follows:

Additionally, you must obey the following rules:

(1) You may only bet on the Magniicent Miler if you bet on Pokey too.

(2) You may bet on either Zippity Doo Dah or the Grim Streaker, but not both. You are allowed to bet on neither of them.

(3) You must bet on at least two of the following three:  Pokey, The Grim Streaker, and Sir Kicks A Lot.

(4) You may not exceed your budget of $6:00.

(5)  Finally, your doctor has told you not to exceed an excitement threshold of 40.

You want to maximize your expected payof from bets you place on the horses, while still obeying the rules above. Formulate this as an integer programming problem. Be sure to deine clearly all the decision variables used.

8.  For each of the following statements, determine whether it is true or false.  Justify your answer by providing either a short proof or an example as appropriate.

(No explanation = no credit)

(a) If the dual of the linear problem (P) has an optimal solution, it is possible for (P) to be be unbounded.

(b) A linear program can be both infeasible and unbounded.

(c)  Suppose that linear programs (P1) and (P2) have identical objectives and identical sets of constraints but diferent right-hand-side values.  Then, it is possible that (P1) has an optimal solution and (P2) is unbounded.

(d) All linear programs have either no optimal solutions, exactly one optimal solution, or ininitely many optimal solutions.

(e)  Given a minimization integer linear program, the optimal objective function value of the integer solution will always be less than or equal to the optimal objective function value of the relaxed problem (that is, when the integer requirement is removed).

(f)  Suppose that the shadow price (optimal dual variable) associated with a certain constraint is 0.  Then, regardless of how much we increase the right hand side value of this constraint, the optimal objective function value remains unchanged.