Linear Programming in Quantitative Problem-solving

Linear Programming (LP) is a powerful tool for solving quantitative problems, providing solutions for a wide range of scenarios such as farm planning, stock control, and financial planning. This method involves defining objectives, alternatives, and resources to maximize income or minimize costs efficiently. LP components include objective functions, alternatives, and resources, with analysis focusing on both current and ideal situations. The process requires input-output coefficients and considerations for resource and marketing constraints. Assumptions like proportionality and certainty guide the application of LP in real-world problem-solving.

• Linear Programming
• Quantitative Problems
• Optimization
• Resource Constraint
• Problem-solving

barreda_e Follow

Uploaded on Sep 20, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. DORUSAL OLMAYAN PROGRAMLAMA (DOP) PROGRAMMING(LP) L NEAR PROF. DR. VEDAT CEYHAN

2. Scope Appropriate for all problems that quantitatively define. Farm planning Transportation problems, Stock control Personal programming Diet problems Mixture problems Financial planning Investment plannimg ...........

3. Positive and Normative Analysis Positive analysis Current situation Regression analysis, input-output analysis etc. Normative analysis Ideal situation Linear programming

4. Components of linear programming 1. Objective function 2. Alternatives 3. Resources

5. Objectives Maximization cropping pattern that produce maximum income Minimization Input combination with minimum cost

6. Alternatives All activities having different input-output coefficient 1. Production activities (wheat, dairy etc.) 2. Sales activities 3. Buying activities 4. Renting activities (labor, land, credit etc.)

7. Input-Output Coefficient Output production from one unit input Output / Input Input: all things used for production. Attention!! Please select the unit (hectare, kg, hours) and use throughout the programming

8. Example 1 Wheat Input-output coefficient Production (kg/da) production Input requirements (input requirements for 1 ton wheat)* activity Land (da) Fertilizer (kg) Land Fertilizer 1 1 2 1/0.2 2/0.2 200 =5 = 10 2 1 4 1/0.3 4/0.3 300 =3.33 =13.3 3 1 6 1/0.36 6/0.36 360 = 2.77 = 16.66

9. Resource and marketing restriction Resource restriction Land, labor, capital, water, building, store etc. Marketing restriction Objective: Reaching maximum income or minmum cost combination

10. Assumptions of LP 1. Proportionality, (linearity) 2. Divisibility 3. Additivity 4. Certainty 5. Non-negativity

11. Formulation of LP problem Problem statement Defining objective(maximization/minimization) Defining restrictions Defining decision variables (activities) Writing objective function equation Writing restriction equations Mathematical presentation of problems

12. Solving LP model Graphical solution (two activities) Simplex algorithm (more than 2 activities) Hand (long time) Computer (quick)

13. Concepts of LP (1) Optimum solution Solution that ensure the all restrictions Optimum region Region show the optimum solution Slack (S) unused resource Unnecessary restrictions Restriction does not affect the optimum solution

14. Concepts of LP (2) Infeasible solution Situation is presence of no solution ensured the all restriction Reasons: 1) High expectation, 2) Large number of restriction

15. Concept of LP (3) Unbounded solution The situation of increasing objective function till infinite or vice versa. Reasons: 1) Inappropriate formulation of the problem, 2) Inharmonious with real world

16. Basic equation (maximization) 1. Production possibilities equation 2. Profit equation 3. Criteria equation

17. Example Land= 200 hectare Capital= enough Activities= Wheat and maize Yield= Wheat 400 kg/da Maize 800 kg/da Gross income= Wheat 0.2 TL/kg Maize 0.15 TL/kg Question: For maximum gross income how much land allocated to wheat and maize?

18. Production possibilities equation 1 1 + = 200 B M 400 800 1 1 = 200 B M 400 800 = 80000 0 5 . B M Girdi kt katsay lar n n 1 kg r n i in hesapland na dikkat ediniz!!!!

19. Production possibility equation Marginal substitution ratio For 1 kg more wheat, we sacrifice 0.5 kg wheat = 80000 0 . 5 B M B = MRS m b M B = 80000 B M M

20. Profit equation wheat gross income maize gross income Wheat quantity Maize quantity = + Z C B C M 0 b m

21. B = + 80000 C C ( M ) Z C 0 b m b M Criteria equation Criteria equation= if sign is + , increasing maize production increase the gross income Criteria equation= if sign is - , increasing maize production decrease the gross income

22. Crop combination for maximum income Slope PPC = Slope IRC ( B/ M) = (Cm/Cb) Slope PPC = Marginal rate of substitution (MRS) Slope IRC = slope of iso-revenue curve

23. Crop combination for maximum income (Graphical solution) a Optimum region

24. More than 1 restrictions Example Land= 200 decare Labor= 750 hours Capital= Enough Activities= Wheat and Maize Yield= Wheat 400 kg/da Maize 800 kg/da Gross income= Wheat 0.2 TL/kg Maize 0.15 TL/kg Labor requirements: Wheat 2 hours/da Maize 6 hors /da letmenin br t gelirini maksimum yapan retim bile imi nedir?

25. Land restriction: = 80000 0 5 . B M Labor restriction: 2 6 + = 750 B M 400 800 = B 150000 1.5M

26. Optimum region

27. B = 80 000 0.5 M B=150 000 1.5 M Optimum combination 45 ton wheat ve 70 ton maize Gross income of optimum combination 19500 TL Gross income (land allocated completely wheat) 16000 TL Gross income (land allocated completely maize) 15000 TL

28. Mathematical presentation Objective function 0.2 B + 0.15 M Maximum Subject to 1 1 land + = 200 B M 400 800 labor 2 6 + = 750 B M 400 800 B ve M >= 0 non-negativity

30. Minimum cost combination (Minimization) Example Medicine production Active matter: Avatec and Biotin Prices: Avatec 8 TL/g Biotin 4 TL/g Restrictions: 1) total mixture will be larger than 50 g. 2) Avatec will be at least 20 g in mixture 3) Biotin will be maximum 40 g. Objective: finding minimum cost combination

31. Minimum cost combination Slope OB= Slope EMD ( A/ B) = (Pb/Pa) Slope OB = slope of iso product curve Slope EMD= slope of isocost curve

32. Objective function: Decision variable 1 Decision variable 2 = + 8 4 min Z A B Restrictions: + 50 A B 40 20 B A

33. Graphical presentation (minimization) Optimum region

34. SMPLEX ALGROTIMH In initial matrix, all activities level area zero , all resource avaliable and gross income zero. Activities are included into initial matrix one by one until reaching optimum solution. Data requirements (i) Net prices and gross income of all decision variable, (ii) Quantity of resource, (iii) input-output coefficient of activities

35. Example Land: 15 dekar, Labor: 48 hours Working capital: 500 TL Ectivities: maize (x1), soy beans (X2) and oat (X3) Kar maksimum yapan retim bile imi ? Gross production value (TL/decare) 112,5 75 55 Variable cost (TL/decare) 52,5 30 25 Labor Capital (TL/decare) 54 36 27 (hours/decare) 6 6 2 Maize Soy bean Oat

36. Resource restriction and production possibilities Maize Soy bean Oat LAnd (decare) (15) 1 1 1 Labor (hours) (48) 6 6 2 Working capital (TL) (500) 54 36 27 1x1 + 1x2 + 1x3 6x1 + 6x2 + 2x3 54x1 + 36x2 + 27x3 500 1x1 + 1x2 + 1x3 + S1 6x1 + 6x2 + 2x3 + S2 54x1 + 36x2 + 27x3 + S3 15 48 15 48 500

37. Objective function 60 X1 + 45 X2 + 30 X3 Maximum Subject to 1x1 + 1x2 + 1x3 6x1 + 6x2 + 2x3 54x1 + 36x2 + 27x3 500 15 48 Disposal slack 1x1 + 1x2 + 1x3 + S1 6x1 + 6x2 + 2x3 + S2 54x1 + 36x2 + 27x3 + S3 15 48 500

38. Initial matrix Disposal resource Activities gross income and Resource activities or ? Land Labor Capital Maize Soy Oat ?? bean X2 45 S1 0 S2 0 S3 0 X1 60 X3 30 Quantity (B) Name 1 2 3.1 3.2 3.3 4.1 4.2 4.3 5 Initial plan(Plan 0) 0 0 0 ?? ?? ?? S1 S2 S3 15 48 500 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 6 54 0 -60 1 6 1 2 15 8 9.3 36 0 -45 27 0 -30

39. Activities in LP 1. Reel activities 2. Slack 3. Transfer activities 4. Artificial activities

40. Reel Activities 1. All activities having different input-output coefficient 1. Production activities (wheat, dairy etc.) 2. Sales activities 3. Buying activities 4. Renting activities (labor, land, credit etc.)

41. Slacks Reflects the disposal resources In objective function, take the value of zero. Take the value of zero or positive values. Use for transforming inequality to equality.

42. Transfer activities Crop produced in farm; 1. for other activity requirement 2. Sale

43. Artificial activities Use for ensuring optimum solution in minimization problem. Software automatically put M values for activities

44. Restrictions Resource and input (land, labor, capital, building etc.) External factors (government programs, legislation) Farm preference (marketing restriction, lacking of information etc.) Cropping rotation and risk factor

45. Maximum frontier 180 >= 6 X1 + 4 X2 + 12 X3 Slack 180 = 6 X1 + 4 X2 + 12 X3 + 1 X4

46. Minimum frontier Fodder crops will be more than 30 tones. Slack (pay attention to negative sign) 30 <= 2 X1 + 3 X2 + 2 X 3 30 = 2 X1 + 3 X2 + 2 X 3 1 X4

47. Frontier in equation forms Widely used. (Orchards etc.) Example Fodder crops in 300 decares of farmland. Maize (X1), Rotation (maize+maize+oat+pasture) (X2) Soy bean (X3) 300 = 1 X1 + 4 X2 + 1 X 3

48. Meaning of input-output coefficient Positive (+) reflects the required resource quantity for increasing quantity of activity by one unit. Negative (-) reflects the increase in resource

49. ? Negative sign 1 hour labor hiring, quantity of labor increase by one hour ?1?2 Arazi 200 1 0 g c 80 7 -1 X1: Maize ve X2: labor hiring Positive coefficient (1) = If maize increase by 1 decare, total farmland decrease by 1 decare. (7) = If maize increase by 1 decare, labor quantity decrease by 7 hours.

50. Programming models example Production, harvest and sale activity Production and sale activity together with transfer activity Intermediate crops and renting activities Separating harvesting activity Crop rotation Combining crop rotation and sales activities

Load More ...