Examples and solution



Examples and solution

1- Ken and Larry, Inc., supplies its ice cream parlors with three flavors of ice cream: chocolate, vanilla, and banana. Due to extremely hot weather and a high demand for its products, the company has run short of its supply of ingredients: milk, sugar, and cream. Hence, they will not be able to fill all the orders received from their retail outlets, the ice cream parlors. Due to these circumstances, the company has decided to choose the amount of each flavor to produce that will maximize total profit, given the constraints on supply of the basic ingredients.

The chocolate, vanilla, and banana flavors generate, respectively, $1.00, $0.90, and $0.95 of profit per gallon sold. The company has only 200 gallons of milk, 150 pounds of sugar, and 60 gallons of cream left in its inventory.

Solution:

Let

C = gallons of chocolate ice cream produced,

V = gallons of vanilla ice cream produced,

B = gallons of banana ice cream produced.

Max Z = 1.00 C + 0.90 V + 0.95 B,

S.T

Milk: 0.45 C + 0.50 V + 0.40 B ≤ 200 gallons

Sugar: 0.50 C + 0.40 V + 0.40 B ≤ 150 pounds

Cream: 0.10 C + 0.15 V + 0.20 B ≤ 60 gallons

C ,V , B ≥ 0.

1- Comfortable Hands is a company which features a product line of winter gloves for the entire family — men, women, and children. They are trying to decide what mix of these three types of gloves to produce. Comfortable Hands’ manufacturing labor force is unionized. Each fulltime employee works a 40-hour week. In addition, by union contract, the number of full-time employees can never drop below 20. Nonunion, part-time workers can also be hired with the following union-imposed restrictions:

(1) each part-time worker works 20 hours per week, and

(2) there must be at least 2 full-time employees for each part-time employee.

All three types of gloves are made out of the same 100% genuine cowhide leather. Comfortable Hands has a long term contract with a supplier of the leather, and receives a 5,000 square feet shipment of the material each week. The material requirements and labor requirements, along with the gross profit per glove sold (not considering labor costs) is given in the following table.

Glove Material Required Labor Required Gross Profit

(square feet) (minutes) (per pair)

Men’s 2 30 $8

Women’s 1.5 45 $10

Children’s 1 40 $6

Each full-time employee earns $13 per hour, while each part-time employee earns $10 per hour. Management wishes to know what mix of each of the three types of gloves to produce per week, as well as how many full-time and how many part-time workers to employ. They would like to maximize their net profit — their gross profit from sales minus their labor costs.

Solution:

Letting

M = number of men’s gloves to produce per week,

W = number of women’s gloves to produce per week,

C = number of children’s gloves to produce per week,

F = number of full-time workers to employ, and

P = number of part-time workers to employ,

formulate a linear programming model for this problem, and put it into standard form (with only ≤ constraints).

Max Z= 8M + 10W + 6C – 13(40)F – 10(20)P,

S.T

2 M + 1.5 W + C ≤ 5000

30 M + 45 W + 40 C ≤ 40(60) F + 20(60) P

F ≥ 20 or –F ≤ -20

F ≥ 2P or –F + 2P ≤ 0

M , W , C , F , P ≥ 0.

2- (a) Put the following minimization problem in standard form (with only ≥ constraints):

Choose x1 and x2 to

Min Z= 3x1 + 2x2

S.T

2x1 + x2 ≥ 10

-3x1 + 2x2 ≤ −6

x1 + x2 ≥ 6

x1 , x2 ≥ 0.

Solution:

[Flipping the ≤ constraint to ≥]

You must note that the right hand side of any constraint MUST be positive not negative so to make it positive multiply the constraint with -1 to change the sign and change it to greater than (-3x1 + 2x2 ≤ −6

Must become 3x1 - 2x2 ≥ 6 after multiplying by -1)

Min 3x1 + 2x2

subject to

2x1 + x2 ≥ 10

3x1 - 2x2 ≥ 6

x1 + x2 ≥ 6

x1, x2 ≥ 0.

(b) After putting the problem in (a) in standard form, construct its dual.

Solution:

YOU MUST MAKE A MATRIX AND THE TRANSPOSE.

Max Z=10y1+ 6y2 + 6y3

S.T

2y1 + 3y2 + y3 ≤ 3

y1 - 2y2 + y3 ≤ 2

y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

6- A local restaurant makes three different kinds of burger. A classic cheeseburger uses one quarter pound of ground beef and slice of cheese. A turkey burger uses one quarter pound of ground turkey. A double cheese burger uses one-half of a pound of ground beef and one slice of cheese. In addition, each type of burger requires a bun. The restaurant can sell a classic cheese burger for $4.00, a turkey burger for $5.50, and a double (cheese) burgers for$8.00. Each day the restaurant has available 800 pounds of ground beef, 500 pounds of ground turkey, 2500 buns, and 2000 slices of cheese. The manager insists that the restaurant make at least 100 double cheese burgers every day. The restaurant wishes to know how many burgersof each type to produce in order to maximize profits subject to the constraints above.

Solution:

X1 = number of cheese burgers produced.

X2 = number of turkey burgers produced.

X3 = number of double burgers produced.

The problem is then: find values for x1, x2, and x3 to solve:

Max 4X1+5.5X2+8X3

S.T.

X2/4 ≤500

X1+ X3 ≤ 2000

X1/4+X3/2 ≤ 800

X1+X2+X3 ≤ 2500

X3≥100

X1, X2, X3 ≥ 0

Tutorial solutions

1. Joe's Garage specializes in oil changes and tune-ups. Profit per oil change is $7 and $15 per tune-up. Joe's has a fleet account customer, which guarantees at most 30 oil changes per week. Each oil change requires 20 minutes labor and $8 in supplies. A tune-up takes one hour and costs Joe's $15 in supplies. Mechanics are paid $10 per hour and Joe's currently employs two mechanics working 40 hours each per week. Every week Joe's orders $1,750 in supplies, and Joe's wishes to maximize profit.

a. Formulate the problem.

b. Solve the problem using simplex method.

The Solution

a.This is a linear programming question. A portion of an oil change or tune-up is not feasible.

X1 = Oil changes

X2 = Tune-ups

Maximize: 7X1 + 15X2

Subject to:

X1 ≤ 30 Fleet Account

20X1 + 60X2 ≤ 4800 Labor time

8X1 + 15X2 ≤ 1750 Materials

X1, X2 ≥0

Standard form

Z-7X1-15X2=0

X1+S1=30

20X1+60X2+S2=4800

8X1+15X2+S3=1750

X1,X2,S1,S2,S3 ≥ 0

|BASIC |X1 |X2 |S1 |S2 |S3 |RHS |

|S1 |1 |0 |0 |0 |0 |30 |

|S2 |20 |60 |0 |1 |0 |4800 |

|S3 |8 |15 |0 |0 |1 |1750 |

|Z |-7 |-15 |0 |0 |0 |0 |

Pivot row= 1/3 1 0 1/60 0 80

|BASIC |X1 |X2 |S1 |S2 |S3 |RHS |

|S1 |1 |0 |0 |0 |0 |30 |

|x2 |1/3 |1 |0 |1/60 |0 |80 |

|S3 |3 |0 |0 |-1/4 |1 |550 |

|Z |-2 |0 |0 |1/4 |0 |1200 |

Pivot row= 1 0 0 0 0 30

|BASIC |X1 |X2 |S1 |S2 |S3 |RHS |

|X1 |1 |0 |0 |0 |0 |30 |

|X2 |0 |1 |0 |1/60 |0 |70 |

|S3 |0 |0 |0 |0 |0 |460 |

|Z |0 |0 |0 |1/4 |0 |1260 |

The optimum solution :

X1=30, X2=70, S3= 460, Z=1260

3- A small petroleum company owns two refineries. Refinery 1 costs 20.000 $ per day to operate, and it can produce 400 barrels of high-grade oil, 300 barrels of medium-grade oil, and 200 barrels of low-grade oil each day. Refinery 2 is newer and more modern. It costs 25.000$ per day to operate, and it can produce 300 barrels of high-grade oil, 400 barrels of medium-grade oil, and 500 barrels of low-grade oil each day.

The company has orders totaling 25.000 barrels of high-grade oil, 27.000 barrels of medium-grade oil, and 30.000 barrels of low-grade oil. How many days should it run each refinery to minimize its cost and still refine enough oil to meet its order?

Solution:

X1: refinery 1

X2: refinery 2

Min Z = 20.000 X1+25.000X2

400 X1+300 X2 ≥ 25.000

300 X1+ 400 X2 ≥ 27.000

200X1+ 500 X2 ≥ 30.000

X1, X2 ≥ 0

To convert the Min to Max

400 300 25000

300 400 27000

200 500 30000

20000 25000 0

Make transpose for the above matrix

400 300 200 20000

300 400 500 25000

25000 27000 30000 0

Max Z= 25000Y1+27000Y2+ 30000Y3

400Y1+300Y2+200Y3 ≤ 20000

300Y1+400Y2+500Y3 ≤ 25000

Y1,Y2,Y3 ≥ 0

The standard form is:

Max Z-25000Y1-27000Y2- 30000Y3=0

400Y1+300Y2+200Y3+S1= 20000

300Y1+400Y2+500Y3+ S2= 25000

Y1,Y2,Y3, S1, S2 ≥ 0

|BASIC |Y1 |Y2 |Y3 |S1 |S2 |RHS |

|S1 |400 |300 |200 |1 |0 |20000 |

|S2 |300 |400 |500 |0 |1 |25000 |

|Z |-25000 |-27000 |-30000 |0 |0 |0 |

Pivot row= (0.6 0.8 1 0 0.002 50)

|BASIC |Y1 |Y2 |Y3 |S1 |S2 |RHS |

|S1 |280 |140 |0 |1 |-0.4 |10000 |

|Y3 |0.6 |0.8 |1 |0 |0.002 |50 |

|Z |-7000 |-3000 |0 |0 |60 |1500000 |

Pivot row= 1 0.5 0 0.0036 -0.0014 35.7

|BASIC |Y1 |Y2 |Y3 |S1 |S2 |RHS |

|Y1 |1 |0.5 |0 |0.0036 |-0.0014 |35.7 |

|Y3 |0 |0.3 |1 |-0.00216 |0.00284 |28.7 |

|Z |0 |500 |0 |25.2 |50.2 |1749900 |

4- Solve using simplex method

Max Z=2X1+X2-3X3+5X4

S.T

X1+2X2-2X3+4X4 ≤ 40

2X1-X2+X3+2X4 ≤ 8

4X1-2X2+X3-X4 ≤ 10

X1,X2,X3 ≥ 0

Solution:

The standard form is

Z-2X1-X2+3X3-5X4=0

X1+2X2-2X3+4X4 +S1’40

2X1-X2+X3+2X4 +S2’8

4X1-2X2+X3-X4 +S3 ’ 10

X1,X2,X3,S1,S2,S3 ≥ 0

|BASIC |X1 |X2 |X3 |X4 |S1 |

|S1 |1 |3 |1 |0 |2/3 |

|S2 |2 |2 |0 |1 |1 |

|Z |-3 |-5 |0 |0 |0 |

Pivot row= 1/3 1 1/3 0 2/3

|BASIC |Y1 |Y2 |S1 |S2 |RHS |

|Y2 |1/3 |1 |1/3 |0 |2/3 |

|S2 |4/3 |0 |-2/3 |1 |2/3 |

|Z |-4/3 |0 |5/3 |0 |10/3 |

Pivot row= 1 0 -1/2 3/4 1/2

|BASIC |Y1 |Y2 |S1 |S2 |RHS |

|Y2 |0 |1 |1/2 |-0.7/3 |½ |

|Y1 |1 |0 |-1/2 |3/4 |1/2 |

|Z |0 |0 |1 |1 |4 |

| | | |X1 |X2 | |

The optimum solution:

X1=1, X2=1, Z=4

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download