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.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
DORUSAL OLMAYAN PROGRAMLAMA (DOP) PROGRAMMING(LP) L NEAR PROF. DR. VEDAT CEYHAN
Scope Appropriate for all problems that quantitatively define. Farm planning Transportation problems, Stock control Personal programming Diet problems Mixture problems Financial planning Investment plannimg ...........
Positive and Normative Analysis Positive analysis Current situation Regression analysis, input-output analysis etc. Normative analysis Ideal situation Linear programming
Components of linear programming 1. Objective function 2. Alternatives 3. Resources
Objectives Maximization cropping pattern that produce maximum income Minimization Input combination with minimum cost
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.)
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
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
Resource and marketing restriction Resource restriction Land, labor, capital, water, building, store etc. Marketing restriction Objective: Reaching maximum income or minmum cost combination
Assumptions of LP 1. Proportionality, (linearity) 2. Divisibility 3. Additivity 4. Certainty 5. Non-negativity
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
Solving LP model Graphical solution (two activities) Simplex algorithm (more than 2 activities) Hand (long time) Computer (quick)
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
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
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
Basic equation (maximization) 1. Production possibilities equation 2. Profit equation 3. Criteria equation
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?
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!!!!
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
Profit equation wheat gross income maize gross income Wheat quantity Maize quantity = + Z C B C M 0 b m
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
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
Crop combination for maximum income (Graphical solution) a Optimum region
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?
Land restriction: = 80000 0 5 . B M Labor restriction: 2 6 + = 750 B M 400 800 = B 150000 1.5M
Optimum region
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
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
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
Minimum cost combination Slope OB= Slope EMD ( A/ B) = (Pb/Pa) Slope OB = slope of iso product curve Slope EMD= slope of isocost curve
Objective function: Decision variable 1 Decision variable 2 = + 8 4 min Z A B Restrictions: + 50 A B 40 20 B A
Graphical presentation (minimization) Optimum region
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
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
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
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
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
Activities in LP 1. Reel activities 2. Slack 3. Transfer activities 4. Artificial activities
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.)
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.
Transfer activities Crop produced in farm; 1. for other activity requirement 2. Sale
Artificial activities Use for ensuring optimum solution in minimization problem. Software automatically put M values for activities
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
Maximum frontier 180 >= 6 X1 + 4 X2 + 12 X3 Slack 180 = 6 X1 + 4 X2 + 12 X3 + 1 X4
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
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
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
? 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.
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
