Faaliyetler İş Araştırma ve İktisat Introduction to Linear Programming 5 Chapter 7 Introduction to Linear Programming ~t-----~binear Programming Problem .'. ~- . ~- - ~ . - .. '. ". :-'. '". -- .-,.' ••.. ..c._ . .•• ,._ • Problem Formulation • A Maximization Pro"bI~,~m;;--- • Graphical Solution Procedure • Extreme Points and the Optimal Solution • Computei' Solutions ' . • A Minimization Problem • Special Cases ~ __ . Cl2006 Thomson South,We5tem. All Rights Reserved. Slide 1 Linear Programming (LP) Problem • U both the objective function and the constraints are linear, the problem is referred to as a linear programining·problem. • Linear functions are functions in which each variable appears in a separa~ term raised to the first power and is multiplied by a c_onstant (which CQuld ,be 0) . • Linear constraints are· lin. eadurictions lhat"aie restricted to be -less than or equal to·, -equal to", or "greater than or equal to" a constant . "'. , , " '," , , ' " " ~uid~Ji,n~s-.fqr}'4od~1 fqrm~l?,qon '_ • Und. erstand the problem thoroughly. • DesCribe the objective . . • Describe each constraint. • :Define the deciSion variableS. • Write the objective in terms of the decision variables. • Write the constraints in terms of the d ecision variables. ~ Thomson South-Western. All Rights Reserved. Slide 5 Linear Programming (LP) Pro blem • The maximization or minlmiz.ation of some quantity. is the objective in all linear programming problems. • All LP problems have constraints that limit the degr;;,;:;e'--il­ to which the ~tive can be pursued .. • A feasible solution satisfies all the problem's constrai.n1s. • An opti~al solution is a feasible solution that results in the largest possible objective function value when max~zing (~smallesLwhen minimizing). ~ A graphical solution method can be used. to solve a 3::: .=~4' llnea~.progr;am with two variables. 0 2006 Thomson ~Wl"$tem. AU Rights Reservl."d . : &oblem 'Formulation • Probleii·do~lation or modeling is the process of ··rranslating.a.vero.. •. slatement of a problem into a mathein~6CaI statement. . .... . , ":"- ':~'.:~:.:~'.:;-;:.~-~_.\_.""_ '00 " "'-. '\ '. ,. LP.F~tf}~tion·o ".'" r----:-:-----, Max Xl 5. 6 ' 2x 1 +3x l .s. 19 Xl + xl.s. 8 0 2006 Thomson 5ouIIrI-W~tem. All ~~rved. Slide 2 . .... Slide 6 1 . , Example 1: Graphical Solution • Constraint #1 Graphed x, , 6 5 4 3 , 5 , (6.0) / • " x, C 2006 Thomson South-Wesl~rn. All Righn ~rved . . Slidr7 Example 1: Graphita' J SO'iulian '" • Constraint #3 Graphed x, /(0. 8) -, 6 5 , 3 1 - , / -3 , • Feasible Solution Region. x, , 6 5 , 3 2 "'- "~ "'-"'-"'-"' - "' - "' .. '" ~ ~ ~ ~ ~ ~ ~ ," .-:'::': ":~~:~:'r:-:--:";' :.:~:~:.-.: . , ', , "' ~ ~ ~ ~ ~ ~ ~ ~ , ., :~~ . :.:~ : ~~ };~;;~~:r~:.~~~f~.j\. :~; :1;:~· ,-- . ... \ ., .,. ,." .:: :~+- . :'-.<. . ":';. "./.: :).,>::'\. '. : ~' .. ;"' ;" .- ;" - . " C-------------~--->--~---x, 1 ...2 -----3 7 " '" 2006 Thomson South-Western. AU Rights Reserved. Slide 11 Exam",l: Graphkal Solution • Constraint #2(;uphed x, , (0.6",, ) 6 5 3 / -. ---- 2 (9 '/2. 0) / , 3 , • " Example 1: Graphical Solution • CODlbined-O...arr';nt Graph x, • 7 6 5 4 3 , EXa......., 1: Graphical Solution • Objective ~ Line x, • 7 6 5 , 3 Objective Function 5I, + 7x 1 -35 (7.0) / x, '-----------------'--"---------- x, . . , • 10 Cl2006 1l>omson~tem. AU Rights ~rv~. Stid~ 8 .' i - ' -. : ',. " -' . . '~' . :~:'/~ Slide 12 2 . .. : .: '. .... ~~ .. ... ~ ~ - ... -~. .' .' :';-':~" .:: --::';:': :.~ ~;~ ~!.:~:; :" \, - '-, . j '-; -,.\ ~ , -' -' .' . Example 1: Graphical Solution • Optimal Solution 8 7 6 5 / Ogjecti"e Flloction 57 1 +77 1 -46 / Optimal Solutiop (Xl =5, 72 = 3) 3 .•........••.••... ""'''"'''~ i 2 '---_-'---'----'------ x, 8 9 10 .-L . (;I 2006 ThoDUon South-Weslem. All Rights RHervrd. Slidtll , " Slack and Surplus Variables • A linear program in which all the variables are non­ negati'.{e and all the constraints are equalities is said to be· in sta'ndard form. • Standard form is attained by adding slack variables to "less than or equal to· constraints, and by subtracting surplus variables frQU,_ -greater than or equal to· constraints .. • Slack and surPlus vari~bles represent th~'diffe~ence between the left and' righ~ sides of the constramts. • Slack-and'-surplllS varia.bl~ ~v!?objective :~(;m- coeffi~e~~~~a~_·tOq.;- -_·'·,'·. _ ..... ,_'- .. ;. ":_ .. '" " - ... " . .... ExtremePoinls . and the OptinralSolution' • The. comers or vertices of the feasible region are referred . to as.the extrem'e POints. • An optimal Solution-to an LP problem can be found at . an extreme point of the feasible_ region. • When lOOking for the optimal sblution.. you do not have ~ evaluate all feasible solution points. • You have to consider only the extreme points of the feasible region, ..J2 ~ Thomson South-Weslem. All Rights ~rd. Sijdt 17 Summary of the Graphical Solution Procedure for Maximization Problems • Prepar~gr.JIIJbof .the feasible solutions fOT each of the constram .ts.. • DeteTriUne Ihrfeasjble region tha~ sa~fies all the ~----t cons train 15 .siIIIultaneously " • Draw an obpdive function line. • Move -j:m"aIl!!ltCJbjective function lines toward larger objective fud:tion values without entire1y leaving the feasible ~egila _ • Any leasiblrsdation-on the objective function line.-- :-=~~ .. _. ~--+ .with th~ larpstvalue is an optimal solution~ •.... .... ,. __ . , " C .' '.E_ple 1: Standard Form ': : <~~~ -":~1-:'77i~OSl:t-~+ 'Os] -' :: \. ~ ~!L~~~ }: ,~-~';.~~-.+ ~ + ~ ,~.~::~~. ~:~~~~?~~~~~~ ;~~< . :~ - si :: '~'> ': . -? > - -~ -.:-' -- ·~;i, ·~,~,S2'~ ~ 0 '-.,' ~,- ' , .. " , . . '.' •. '~- ---.!' .-;. " "'" - --. -, " ?;~\,-... - . , , :,,: ;-:: ~' . ~- ~/./~",-' .~ :. 7 ·0 6 3 2 o 0) 6 ]9 ~ . '0 ® SotAlo'Mil II .. AlI~~. SIKlt 14 " .-. - Slide 18 '"- . ; 3 - ~. Computer Solutions • Computer programs designed to solve LP problems are now widely available. • Most large LP problems can be solved with jusla few minutes of computer time. • SmaU LP problems usuaUy require only a few seconds. • Unezrryrogrammmg solvers are now part of many spreadsheet packages, such as MicroSoft Excel. 0 2006 ThOlJUon South-W~tem.· AD Righ~ Reserv~. Example 1: Spreadsheet Solution • Pa'iti'J.Sp",.dsheetSt,o"nng Problem Data LHS Coefficients Slid~ 19 .: .. : Slide" 21" -, .:.; ...c: :: .: • ..;: .•. . . . :;.<~.iIlItPl~J:·Spreadshe~t .S9Iu tion ·. , •. lti.~w.~~~on .~(Computer Output .W{~·fiom·the previous slide that . : Ob)ectJve Function Value ""46 .Decision Variable #1 (Xl) '" 5 Decision Variable 112 (x:J '" 3 Slack in Constraint #1 Slack in Constraint #2 _ Slack in Constraint #3 1(=6-5) .::. _ _ 0 (= 19 - 19) ~ O(~8-8) C 2006 ThotTl5On South-wes~m. AJ1..Rjzhts Reserved. Slid~ 23 interpretation of Computer Output • In this chapter we-will discuss the following output: • objective function value • values of the decision variables • reduced costs • slack/ surplus • In the next chapter we will discuss how an optimal solution is affected by a change in: • a coeffidenLolthe..o.bject::hreJ:unction • the~ht-hand side value of a constraint Example 1: Spreadsheet-So]ution • PartialSpreadshretShowing:Solution C i D Or;!..:!I al DedSion Vllriallie Vaflk18 xt .' . X2~. ~, ..,., ...... . . . _; • The reduced cbst for a decision 'v'~bl~ w~se value is o in the optimaJ.solution is the.amo:UOt.the variable's objective function coefficient would have· to improve (increase for rnaximizSitive value. . • The reduced cost for a decision variable with a positive value is O . 4:12006 Thomson .5oud.-We;tern. Ali Righl5 ~rved. slid(>~l--- 4 ' < '. ' ... .' " .. ..... · .... -. c· . .. -~ .--.-' -:- -~, - c' . /,. -,-, ' ;, ' .' ... ~.-;;.:-!;; ,.", .- '.: ;-" '.; .... ::;.";;' .=-''';',.:'';'..;. ~ , ... :: I • • ' , . " . '~ , Example 1: Spreadsheet Solution • Reduced Costs Thomson South-Western. All Rights ~rved. Slide 25 Example 2: Graphical Solution • Graph the Constraints Constraint 1: When Xl'" 0, then X 2 = 2; whenx 2 · ... 0, . 'theri X~ :S: 5, Corniect (5,0)' and' (0,2), The '-:>" side is a hove this line. Constraint 2: When .1'2 - 0, then Xl = '3. But seltmg Xl to ° will yieJd Xl "" -12, which is not-on the graph. Thus, to ge) a'·second.P9int on thls line; set Xl to any nim'tber larger than 3 and sOlve fOT i2~ when Xl "" 5, then -12 "" 8. Connect (3,0) and (5~8), The ">­ side is to·the, iignf: 'Constraint 3 ~' . }vpen ~l',"" .o,,_th, eI1 x 2 ~ 4; \'f~.e~x2- "1; 0, thenxf ~ 4; _ Connect (4,0) and (OA) .. The w>n side is above-t¥s·liI:le . . .:. :'. .. Example 2: ·G.raplUcal&,ll\tipl) . • Grapfl the Objective Function _ Set. the objective fwlction equal to an arbitrary constant (say 20) and graph it For 5x) + 2:r2 '" 20, when It: 0, thenx 2 =-10; when x 2 =·0, then x) =- 4. Connect (4,0) and (0,10). • Move the Objective Function Line Toward Optimality Move it in the direction wtrich lowers its Y'Clue (down), since we are minimizing.. until it touches the __ lasf pOint of the feasible region,. determined by the last two constraints. - ~ Thomson South-Western. All Rights Reserved. Slide 29 Examplr2: A Minimization Problem • LP Formulatiial ' . '.' - .,:, Min 5x l + 2x2 s.L 2:rl -+ 5x 1 .:: 10 4.1:) - x 2 ,:: 12 Xl + x,,:: 4 ·.:ExaDiigii2:2: Graphical Solution Slide 26 ,-- - , . Feasible Region' ' ,. j. .. ; ",,', . , x, .:- ." .•...... ....:---.•. _ .. , '. '.' '.' -" -. ":--::" '.- -:=- C-- _~~_'.: ., ., " .j' -j ' •• "",,""'''' .; "1'.- .. ;' - -: " .- , - ' ,;- .: · .. ~±;~,,\..:.i -Graphical Solution • .Obj~~ j:~Graphed Min z- = '5x, + 2x2 , x, C 2006 ThoIn$()n SQ"5'D" m. All Rig~ed. Slide 30 5 Example 2: Graph.ical Solution • Solve fOT the Extreme Point at the Intersection of the Two Binding Constraints 4x'-)'2=12 X 1 +)'2= 4 Adding these two equations gives: 5r, = 16 or Xl = 16/5, Substituting this into Xl +)'2 = 4 gives: )'2 "' 4/5 Cl2006 Thormon South-We-stem, Au Righ~ Reserved Slid~ 31 . , ' " ,E~a_m'ple 2: Graph.ical Solution · :'OP~\l~SOlu1i6n opilirull: :x~' ~:"j6i5 , .1'2 ~ 4/~ x, 02006 Thomson South-Western, S lid~ 35 • Solve for lhe Optimal Value of the Objective Function Solve for z = 5~'I +- 2z2 to" 5(16/5) + 2(4/5) = 88/5, Thus the optimotisolution is Xl =16/5; )'2 - 4/5; z = 88/5 Cl2006 Thomson SousJ.-Wetom'\ All Rights R"~!""r:d . 5lid~ 32 Example 2: Spreadshee't: Sofution • Partial Spreadsheet. Showing Problem-Data ' . - " -' .< " , - - ' -'-' '.. '.' '.' --.-.:.- - ,' . " . " .'''.'. > , Example 2: 'Spieaasnee.tS6Iutiorr' • Partial Spreadsheet Showing Solution· . Ditcision Variables 'I X1 Dec.Var.Value 320 MinimiZild C:.! ~,:-:,'vG Function Constraints I :"'''TIount Used #'I I 104 #2 I 12 18 #3 ! 4 J 5lide~ J---' 02006 Thomson SoaIIt-Weslem. All Righ~ Rts('rved. 6 Feasible Region i • The feasible region for a two-variable LP problem can be none,:,istent, a single point, a tine, a polygon, or an unbounded area. --- • Any linear program falls in one of three categories: • is infeasible • has a unique optimal solution or alternate optimal solutionS • has an objective function that can be increased without bound - -1---....-A-feasjDJeregionmay~bounded and yet there m~~ ." . be optimal ~lutions. This is common in minimization . I -?:". > . :'0" - "."-",- ",."'.> ~ " .' ~ ... : .... .... . '. ' . . ;;."j,~~.~.:;. <~ :,. ; .t .. ~;(~/\~ '~,; ~<~, ,- i· ... i'..·-('.~ : - '.- : C' -='~''';'~~: -: :'- -,-. ,. -.{ >( '.j -; :1 ".,.'." .-., .. pi"l:?blems and is possibl~ in maximization problems. . . . - 02006 Thomson South-Wesltm. All Right!> Rt~rJed. Example: Infeasible Problem • Solve graphicaUy for the optimal solution: o Max 2xl -f 6x 2 s.L 4xl + 3x 1 ~ 12 2x 1 + ~2 ~ 8 , . ..... , Exalllpk: Unbounded" Pro.blein· • Solve graphically- for the optimal sOlution: s.l Xl + . X 2 ~ 5 3Xt+X2~8 Q 2006·· Thomson So\lth-Weslem. All Rights Rl5erved. Slidt 37 Slide 39 . ] Slide 41 Special Cases • Altema!5vtOptimal50lutions In the graphi"cal method, if the objective function line is parallel IDa boundary constraint in the direction oL optimiza~ihere ar. e altemate oEtimal solutions, with all ~ on this line s. egment being optimal. • lnfeasib~ A linear pt1IBII4lm which is overconstrained so that no point satisfirsall the constraints is said to be infeasible. • Unbound~ . (See examJ*on upcoming slide.) -- .. . 't. - ." _ . C 2006 ThoinSon s..IIo-Wtsttm. A;U Right!> ~rvtd. Slidt38 '- Ex.....,le: irtfeasible Problem • There_ ar:eo oo .Jlliirlts tha~ satisfy both constraints, hence , this pi1:>blem_no ieasible region, and n~,-optimal 'solu.tion~ ~. '. ':' i _ • . ' . • . " ... ,.... ... .~ ::~ ~~~--- " " . :- ~ , .'~"::- -. .-,,:,} . / . .... ' . . ':' ,~ ":'.: "~:\ -;:.j<:~ ,::~;;~---=~::~:. '- "::. -:'.' - . ·.·.Exa;njile: lfnbollllded Problem . .... The fea~bie rep... is unbOlU"Ided and·the objective function-line ~ be'moved parallel to itself without bou.nd so 'that ZGICI be increased infinitely . . .' : .. 02006 Thomson Sou~rn. All Righ~ed. Slide 42 7