Business And Financial Mathematics-linear Programming

Linear Programming Sub Topics I. General form of linear programming II. Graph Method III Simplex Method IV Application in business V. Problems I General form of linear programming Definition of linear programming Linear programming consists of method for solving optimization problems in which the object function f is a linear function . In linear programming, we discuss how to find the value of control variables to optimize the object function. a General form General form of linear programming consist object function(object function) and feasible area which are described by a function and linear equations. b. Example Object function: Z = 250 X + 200Y (To maximize) Feasible area is restricted by a system of linear inequalities as follows: 3X + 2Y ≤ 700 X + Y ≤ 300 X ≥0 Y ≥0 II Graph Method Steps • The problems is described by a mathematical model consists of object function and feasible area(system of linear inequalities) • Based on the system of linear inequalities , make a graph of the feasible area. • Based on the object function , make a investigation line. Z=250X+200Y or 200Y=-250X+Z Y=-250/200 X+ Z/200 Or Y=-5/4 X+ Z/200 28

•

Move the investigation line until it reach the first point the feasible area. The point is called optimal solution.

Refer to the above problem: Object function: Z = 250 X + 200Y (To maximize) Feasible area is restricted by system of inequalities as follows: 3X + 2Y ≤ 700 X + Y ≤ 300 X ≥0 Y ≥0 The Graph

The first point reached is (100,200). The solution is X=100 dan Y=200. III Simplex Method Simplex method solves linear programming with two or more than two variables. a.Steps 1. 2. 3.

Make a mathematical model. Inequalities have to modified become equations using slack variables. Described it in a table or a matrix. Determine a pivot element ( intersection between pivot row and pivot column) .

29

4. 5. 6.

pivot column is column whose last element is the most negative. Then, pivot can be found as follows: (a) Find ratio of last element and element at pivot column. (b) The row whose ratio least positive is pivot row. Transformation at every row : (a) Every element at pivot row divided by pivot element. (b) Others rows must be subtracted or added by pivot row so the element of pivot column is zero. Repeat step (3) and (4) if the last row remains negative value. If the last row doesn’t have negative value, then the solution can be seen as follows: a) Check every row b) The value of last element is solution variabel(column) whose element is one and zero at others rows.

b. Example Use simplex method to solve the following problem. Object function: Z = 50 X + 80Y (To maximize) Feasible area is restricted by a system of inequalities as follows: X + 2Y ≤ 320 3 X + 4 Y ≤ 840 X ≥0 Y ≥0 Steps : Step 1 X + 2Y ≤ 320 3 X + 4 Y ≤ 840 Z = 50 X + 80Y

→ → →

X + 2 Y + r = 320 3 X + 4 Y +s = 840 -50 X - 80 Y +Z = 0

Step 2 X 1 3 -50

Y 2 4 -80

R 1 0 0

S 0 1 0

Z 0 0 1

Step 3 Pivot column is column 2. Pivot row is row 1 Pivot element is row 1 dan column 2

30

320 840 0

Ratio 320/2=160 840/4=210 0/-80

Step 4 Notation of row transformation as follows: R1 ↔R1/2 means that new row 1 = old row 1 divided by two. R2 ↔R2-2R1 new means row 2 = old row 2 minus 2 old row 1 R3 ↔R3 +40R1 new means row 3 = old row 3 plus 40 old row 1. The result: X ½ 1 -10

Y 1 0 0

R ½ -2 40

S 0 1 0

Z 0 0 1

Ratio 160 200 12800

Step 5 (Repeat step (3) and (4) because the last row remains negative number. Step 3 Pivot column is column 1 X Y R S Z Ratio ½ 1 ½ 0 0 160 160/(1/2)=320 1 0 -2 1 0 200 200/1=200 -10 0 40 0 1 12800 12800/-10 Pivot row is row 2 Pivot element is row 2 and column 1 Step 4 Notation of row transformation as follows: R1 ↔R1 – R2/2 R2 ↔R2 R3 ↔R3 +10R2 The results: X Y R S 0 1 3/2 -1/2 1 0 -2 1 0 0 20 0

Z 0 0 1

Step 6 Solution : Y=60 X=200 Z=14800

31

60 200 14800

IV Application in business Problem An agricultural businessman has a land with the area 100 dam2 (are). He will cultivate the land with plant A, B, and C. Seed cost per dam2 are: A=40$, B=20$, and C=30$ respectively. The maximum fund available for the seeds is 3200$. He also need labors for: A=1 man-day, B=2 man-days, C=1 man-days. There is 160 mandays available. Profit per dam2 are : A=100$, B=300$, and C=200$ respectively. Find the area for plant A, B, and C respectively to maximize the profit? Answer Object function: Z = 100 X1 + 300X2+ 200X3 (To maximize) Feasible area is restricted by a system of inequalities as follows: X1 + X2+ X3 ≤ 100 40 X1 + 20 X2+ 30 X3 ≤ 3200 X1 + 2 X2+ X3 ≤160 X1 ≥0 X2 ≥0 X3 ≥0 Steps: Step 1 X1 + X2+ X3 ≤ 100 40 X1 + 20 X2+ 30 X3 ≤ 3200 X1 + 2 X2+ X3 ≤160 Z = 100 X1 + 300X2+ 200X3 Step 2 X1 1 40 1 -100

X2 1 20 2 -300

X3 1 30 1 -200

r 1 0 0 0

→ → → →

X1 + X2+ X3 40 X1 + 20 X2+ 30 X3 X1 + 2 X2+ X3 -100 X1 - 300X2- 200X3 S 0 1 0 0

t 0 0 1 0

32

Z 0 0 0 1

+ r = 100 + s = 3200 + t =160 + Z =0

100 3200 160 0

Ratio 100 160 80 0

Step 3 Pivot column is column 2. Pivot row is row 3 Pivot element is row 3 dan column 2 Step 4 Notation of row transformation as follows: R1 ↔R1 - R3/2 R2 ↔R2-10R3 R3 ↔R3/2 R4 ↔R4 +150R3 The result: r S X1 X2 X3 ½ 0 ½ 1 0 30 0 20 0 1 ½ 1 ½ 0 0 50 0 -50 0 0

t -1/2 -10 1/2 150

Z 0 0 0 1

20 1600 80 24000

Step 5 (Repeat step (3) and (4) because the last row remains negative number. Step 3 Pivot column is column 3 r S T Z X1 X2 X3 ½ 0 ½ 1 0 -1/2 0 20 30 0 20 0 1 -10 0 1600 ½ 1 ½ 0 0 1/2 0 80 50 0 -50 0 0 150 1 24000 Pivot row is row 1 Pivot element is row 1 dan column 3 Step 4 Notation of row transformation as follows: R1 ↔2R1 R2 ↔R2-40R1 R3 ↔R3-R1 R4 ↔R4 +100R1 The result: r S X1 X2 X3 1 0 1 2 0 10 0 0 -40 1 0 1 0 -1 0 100 0 0 100 0

t -1 10 1 100

33

Z 0 0 0 1

40 800 60 26000

Ratio 40 80 160 -480

Step 6 Solution : X3 =40 S =800 X2=60 U =26000

V Problems Problem 1 A home industry produce two kinds of cake those are Cake I and cake II in a day Cake I need 0.3 kg of wheat (terigu) and 0.1 kg of sugar per unit. Cake II need 0.2 kg of wheat (terigu) and 0.1 kg of sugar per unit. In a day, 140 kg wheat and 60 kg sugar are available. Profit per unit of Cake I and cake II are Rp. 900 and Rp. 800 respectively. Find number of Cake I and cake II should be made respectively to maximize the profit? Problem 2 A factory produces three kinds of toys those are toy A, B, and C. The maximum production of the toys is 200 units. Cost per unit of product A, B, and C is $24, $40, and $30 respectively. The maximum budget of $3500 is available. Product A need 1 man-day, product B need 2 man-days, and product C need 2 man-days. 160 man-days are available. Profit per unit of product A=$14, B=$20, C=$16. Find number of product A, B, and C should be made respectively to maximize the profit?

34

Suppose: M=gradient of investigation line P = gradient of line I: 3X+2Y=700 2Y=-3X+700 Y=-3/2X +700/2 Q= gradient of line II: X+Y=300 Y=-X+300 When, P<MP and M>Q, then the solution is A Refer to the example above: M=-5/4 P = -3/2 =-6/4 Q= -1=-4/4 So, P<MP and M>Q The optimal solution is A or X=0, Y=300 If Profit per unit of Cake I and cake II are Rp. 350 and Rp. 200 respectively. Find number of Cake I and cake II should be made respectively to maximize the profit? Z=350X+200Y. M=-350/200=-7/4 So, M

35

Simplex Method For Mathematical Model with ≥ and ≤ A factory produces two kinds of bags those are bag A and B. In making bags we need cutting and assembling. A bag A need 1 hour cutting and 3 hours assembling. A bag B need 2 hour cutting and 4 hours assembling. Time available for cutting maximum is 32 hours and for assembling maximum is 84 hours and minimum 48 hours. Profit per unit of bag A=$50,and B=$80. Find number of bag A and B should be made respectively to maximize the profit? X= number of bag A, Y= number of bag B, P = profit(untung) X+ 2Y ≤32 (cutting) 3X+4Y≤84 (assembling) 3X+4Y≥48 (assembling) p=50X+80Y X+ 2Y +r=32 3X+4Y+s=84 3X+4Y-t=48 -50X-80Y+p=0 X 1 3 3 -50

Y 2 4 4 -80

R 1 0 0 0

S 0 1 0 0

T 0 0 -1 0

P 0 0 0 1

32 84 48 0

In simplex method, every matrix has a basic solution. In can be seen using step (6) above. Example: Basic solution of the matrix above is: r=32,s=84,t=-48, p=0 . If all solutions are non negative, the matrix is called feasible. When, there is a negative value in basic solution, we need to do a further matrix operation as follows: 1.Find a row whose solution is negative (This is a key row) 2.Find a column whose at least two non zero. This a key column. 3. Modify the matrix to make all element in the key column is zero except element in the key row is 1. Look at the example above: key row = row 3, key column = column 2 Do operation: R1 ↔R1-R3/2 , R2 ↔R2-R3, R3 ↔ R3/4, R4 ↔R4+20R3

X -1/2 0 ¾ 10

Y 0 0 1 0

R 1 0 0 0

S 0 1 0 0

T ½ 1 -1/4 -20

36

P 0 0 0 1

8 36 12 960

Ratio 16 36 -48 -48

Basic solution: r=8,s=36,y=12,p=960 , Already feasible Next process is row operation process (step 3 and 4) of simplex method. Pivot Column =column 5, pivot row=row 1 Next: R1 ↔2R1 , R2 ↔R2-2R1, R3 ↔ R3+R1/2, R4 ↔R4+40R1 The result: X Y R S T P Ratio -1 0 2 0 1 0 16 -16 1 0 -2 1 0 0 20 20 ½ 1 ½ 0 0 0 16 32 -10 0 40 0 0 1 1280 -128 Pívot Column =column 1, pivot row=row 2 Next:( step 3 and 4) of simplex method) R1 ↔R1+R2 , R2 ↔R2, R3 ↔ R3-R2/2, R4 ↔R4+10R2 The result: X y R S T P 0 0 0 1 1 0 36 1 0 -2 1 0 0 20 0 1 -1/2 -1/2 0 0 6 0 0 20 10 0 1 1480 Solution : t=36, x=20, y=6, P=1480 Application of Simplex Method To Minimize Object Function Let Z is an object function. Minimizing Z means maximizing –Z (negative of Z). Example: A factory produces three kinds of product those are product I, II and III. In making products we need cutting and finishing. A product I needs 2 hours cutting and 1 hour finishing. A product II needs 1 hour cutting and 1 hour finishing. A product III needs 1 hour cutting and 2 hours finishing. Total time for cutting at least 600 hours and Total time for finishing maximum 800 hours. Cost per unit of product I=$30, II=$30 and III=$10. Find number of product I, II and III should be made respectively to minimize the cost? Let x=number of product I, y=number of product II, Z=number of product III and C=Cost 2X+ Y+ Z ≥ 600 X+ Y+2Z ≤ 800 30X+30Y+10Z=C or 30X+30Y+10Z+(-C)=0

37

2X+ Y+ Z -r = 600 X+ Y+2Z +s = 800 30X+30Y+10Z+p=0 where p=-C X Y Z r S P 2 1 1 -1 0 0 600 1 1 2 0 1 0 800 30 30 10 0 0 1 0 Basic solution r=-600 s=800 (not feasible) Key element is row 1 and column 2 Matrix operation : R1 ↔R1, R2 ↔R2-R1, R3 ↔R3-30R1. X Y Z r S P Ratio 2 1 1 -1 0 0 600 600/2=300 -1 0 1 1 1 0 200 200/(-1)=-200 -30 0 -20 30 0 1 -1800 Basic solution y=600 s=200 (already feasible) Pivot element is column 1, row 1 Matrix operation : R1 ↔R1/2, R2 ↔R2+R1/2, R3 ↔R3+15R1. X Y Z R S P Ratio 1 ½ ½ -1/2 0 0 300 600 1000/3=333 1/3 0 ½ 3/2 1/2 1 0 500 0 15 -5 15 0 1 -9000 Basic solution X=300 s=500 (feasible) Pivot element is column 3, row 2 Matrix operation : R1 ↔R1-R2/3, R2 ↔(2/3)R2, R3 ↔R3+(10/3)R2. X 1 0 0

Y 1/6 1/3 50/3

Z 0 1 0

R -2/3 1/2 50/3

S -1/3 2/3 10/3

P 0 0 1

400/3 1000/3 -22000/3

Solution: X=400/3, Z=1000/3, P=-22000/3 or –p=22000/3 or C=22000/3

38