### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# OM 300- Linear Programming (Optimization) Notes OM 300

UA

GPA 3.2

### View Full Document

## 291

## 2

## Popular in Operations Management

## Popular in Department

This 34 page Class Notes was uploaded by Samantha on Sunday March 8, 2015. The Class Notes belongs to OM 300 at University of Alabama - Tuscaloosa taught by William Petty in Winter2015. Since its upload, it has received 291 views.

## Reviews for OM 300- Linear Programming (Optimization) Notes

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 03/08/15

M 300 Introduction to Operations Management Supplement Optimization Bill Petty REE31332 THE UNIVERSITY 0F ALABAMA Optimization A constrained optimization problem is a mathematical model that maximizes or minimizes some quantity While satisfying a set of constraints 0 Maj or elements of an optimization problem gtgt DeQision v ri gtgt Obiective gtgt Constraints THE UNIVERSITY 0F ALABAMA Elements 0 Decision Variables Values that must be chosen in order to define a solution to the problem In uence the objective function in some way Consume or supply some resource THE UNIVERSITY 0F ALABAMA Elements 0 Objective Function Value of a solution Measures relative quality of different solutions Benchmark 0 Constraints Inequalities or equalities Associated with some limited resource Determine whether a specific solution is feasible R39ght39hand S39de defines the amount of resource available or needed to satisfy the constraint gtgt THE UNIVERSITY 0F ALABAMA Example Sldneyv111e Desk Mfg 0 Product MiX Problem 0 Produces two types of desk 0 Using three types of wood in every desk measured in board feet bf Type Profitdesk Amount Used Amount Rolltop 115 Wood Rolltop Regular Available Regular 90 Pine 10 20 200 Cedar 4 16 128 Maple 15 10 220 THE UNIVERSITY 0F ALABAMA Example cont 0 Decision problem How many of each type of desk should Sidneyville make in order to maximize profit using only the wood that is currently available 0 What are the decision variables how many of each type ofdesk o What is the objective function max profit 0 What are the constraints using available materialsBill of materials ex amount of wood THE UNIVERSITY 0F ALABAMA Example cont 0 Decision variables gtgt x1 of rolltop desks to produce gtgt x2 of regular desks to produce 0 Objective function Total profit 115x1 9ch2 THE UNIVERSITY 0F ALABAMA Example Constraints 0 Limited wood available Amount used is less than or equal to the amount available Pine 10x120x2 lt 200 Righthand Cedar 4x16x2 lt 128 S1des Maple 15x 10x2 lt 220 o Nonnegative production gtgt X1 gt0 X2gtO KHEKMK Example LP Formulation maximize 1 15x1 90x2 subject to 10x1 20x2 S 200 4X116X2 S 128 15x110x2 S 220 961962 20 o This is an example of a linear program THE UNIVERSITY 0F ALABAMA Feasibility O A feasible solution is a set of decision variable values that satisfy all of the constraints 0 The feasible region is the set of all feasible solutions 0 extreme points are the corners of the feasible region 10 THE UNIVERSITY 0F ALABAMA Graphical Example x2 number of regular desks 20 15 10 A l o Sidneyville Mfg example 15x1 1Ox2 220 extreme point 10x1 20x2 2 200 feasible region x 4x116x2 128 x1x2 2 0 x1 number of 5 rolltop desks 10 15 20 25 3O 11 THE UNIVERSITY 0F ALABAMA Optimality 0 An Optimal solution is a feasible solution that achieves the best possible objective function value Within the feasible region No other feasible solution has a better objective value There may be multiple optimal solutions In an LP at least one of the extreme points is an optimal solution Graphical method Simplex method Excel Solver 12 THE UNIVERSITY 0F ALABAMA Graphical Solution Method x2 number of regular desks A o Sidneyville Mfg example 20 15x1 10x2 220 x2 8 x2 7 x112 10 720 962 4 x2 O 5 17 i 10x1 20x2 2 200 gt 0 xvxz 0 17 4x116x2 128 gt b f 5 1o 15 20 25 30 x1 Hum er 0 rolltop desks 13 THE UNIVERSITY 0F ALABAMA Computerized Method o Simplex Method invented by George Dantzig in 1947 0 We Will use Excel spreadsheet with Solver addin o Other more robust computer software is available to solve large LPs Spreadsheet addins Standalone optimization modeling and solution programs OPL and CPLEX ILOG 14 Excel Spreadsheet THE UNIVERSITY 0F ALABAMA V Egil tlit Type a question for help 7 E x MECI eee tt Excell Siidne wttllle Eile Edit emur merit anmt Innis eam induw eat 23 eueeleem eeelmnvle E itmlm v1 El QQIIVJReplywithghengeem fg rial 139 IE vl B E I 34 T53 F5 r A e t D IE I F e H3 11 Sidneyvitlllle Mtamutactu rt 39 3 Decision Variates Reltlttepe Regutar e Ojective x2 Vatue 5 Quantity 12 4 e Pre theetk t t 5 90 LHS RHS e Constraints Feet per Feet per Feet Feet g eelk Desk Used ye Avaitltalblte tn Pine 10 20 I 200 H Cedar 4 1 1 m Maple 15 10 e 220 113 Reade Emmi lectures gm 353 PM Mfitmee I Sidinaewililfre 2 C6CSD6D5 C10C5D10D5 15 REE31M Using Excel Solver o If you are using 2007or 2010 Go to Data and then Solver if not in your system Click on Office Button Excel OptionsAdd insGo check Solver click on OK and Solver will be added to your Data Tool Bar 0 If a MAC you will need to download Solver as an outside program 0 Sample 17 THE UNIVERSITY 0F ALABAMA Using ExcelSolver 0 Set objective ObjECtiVE fUIlCtiOIl o changing cells decision variables a Constraints Left hand side Type of constraint Right hand side 0 Solver Options Assume Linear Assume Nonnegative 18 THE UNIVERSITY 0F ALABAMA Using ExcelSolver cont Aelil Type a queetien for help v a x Milaneseft Excel Si39 lmlewi39lle Eile Edit Em Insert Fgrmat Innis gala mm Help 23 euetea 3E lee39lnvnv E vELEll L E E El 21 I quotH Rep y with ghangeem f Hriial rule 7 B I g g E I 3 l 53 33 F5 v at A e 11 S td neyvilllle Manufactu rintj 511 39 T 1 1 3 lm EI F le HT Solve Button Options if Se ver Parameters 3 Decieinm Variallee Roltltops Regullars Ojective 4 X 1 X 2 Va ue Ti Utan tiity 12 4 Pr e wtestk 1 39 a Constrat Signage Emarut F ag I V 39E39i lai39le lie3 mess 1quot 1H 311 le I I 41 it lm A II 1 311 311 4 312 1131 112 113 H I Ir EmMRepmti f Ewanav L e lAQt Sh pEE139 a A 3733 quot Pm Heard lettures MiicmmeenmerShineMlle EJ IWLE 355 PM 19 THE UNIVERSITY 0F 1JAJ3RAUAI Using ExcelSolver cont Assume Linear and NonNegative A l l TEX HiCI E l lExee Sinjllmewil e file Edit ew lme t Fgmmat ladle Ham in ew Help Type a question for help Eeeueeleewe eaveemlm vi El l f i eplywithghengeem fgl t l lll v E 139 E 3931 T63 413 i F5 r T A B D E I F l e HT S d neyville M an ufact u r 39 Decision Va ria es Rlll tepe Reg uxllare Ojective Value quantiity Pr39 WDeelk 115 90 E IIEIII and RH S Feet LHS Pt per Feet elk Used Tye Avaiuxabe e 200 1 220 fl e MERE 432 PM Reade eUMre5 IMiiemeu t I Sienewil le 20 THE UNIVERSITY 0F ALABAMA Using ExcelSolver cont Aelel Type a question fer help 7 E x E Micreee Exeell Si lmewillle Bile eilit eelr lemma Imba eaia winder Help g lgl lvl 3 iH lm quot39 I E E E IE 5 I WREplywith ghangesm 3 Elhr e vlll v E I g E 3 53 493 F5 v 5 A e C D E F e HT IE YVHIE Manufactu rm 5151 T v 3quot T 1 S d 3 Decision Varia ee Relll tepe R eguxllar e Ojective 4 x 1 x2 Value uenltiity 12 4 a Pr39 WDeelk 1 15 90 LHS RHS e Constrair Remus 5 mquot E er Feet Feet 9 lmma m n w L TyEi e 200 z 1 at 220 13 2 z M LIJJ Reade H Starlj e eUlM1re5 IMiiemeun t Fewer I ltlt game 459PM Sid naewililie 21 THE UNIVERSITY 0F ALABAMA Special Problems Multiple optimal solutions Infeasible problem Empty feasible region no feasible solutions May have a missing or incorrect constraint Unbounded solution There is no finite optimal solution May have incorrect objective function May have a missing or incorrect constraint 22 THE UNIVERSITY 0F ALABAMA Tips for Spreadsheet Optimization 0 Keep it organized and structured 0 Use descriptive labels 0 Use notes where appropriate 0 Pay attention to the Solver options For example Assume NonNegative 0 Design the spreadsheet so that the decision variables are used directly in the objective function target cell 0 Print Screen 0 Formatting 23 Some Useful Excel Functions THE UNIVERSITY 0F ALABAMA SUMA1C1 A1B1C1 A1 131 C1 A1 A1A2A3 A3 SUMPRODUCTA12B2C3ZD4 A1C3 B1D3 A2C4 82D4 A2 B2 C3 D3 C4 D4 24 THE UNIVERSITY 0F ALABAMA Transportation Problem Statem 39 0 Objective minimize total cost of shipping product from each of the sources to each of the destinations 0 Subject to the following requirements Total amount shipped out of a source outbound cannot exceed its supply Total amount shipped to a destination inbound must equal its demand requirement Negative shipments returns are not allowed 25 THE UNIVERSITY 0F Example Midwest Flour ALABAMA 0 Grain is delivered by truck from farms for storage in grain elevators located in Kansas City Omaha and Des Moines 0 Grain is transported by train from grain elevators to our mills located in Chicago St Louis and Cincinnati 0 Supply and demand are measured in tons Elevator Annual Supply Mill Annual Demand Kansas City 170 Chicago 200 Omaha 250 St Louis 100 Des Moines 200 Cincinnati 300 Total 620 Total 600 26 Example cont THE UNIVERSITY 0F ALABAMA 0 Shipping costs gtgt per ton From originelevator to destinationmill Flour Mill Grain Elevator Chicago St Louis Cincinnati Kansas City 6 8 10 Omaha 7 1 1 1 1 Des Moines 4 5 12 27 THE UNIVERSITY 0F ALABAMA Solvmg the TP usmg ExcelSolve Wereeuft Excell Midwest eur 7 7 i if 7 7777777 7 g Eile Edit 39g39iew lneert Fgrrnai leeIE gate indew Help Type a question for help v El 3 D g evemvwveiv l m e v BEBE Q e Hg El FEE 9e W eep wmh ehangesm 1 Ariel v M v I g E E 31 I T63 43913 D i E1 v e 5UMFHUULJEHE51ET 13E15 A e e D E F e H ll fl Midwest Flun39 Ttel Est sumproductC13E15C5 E7 Shipments T tel 39x ineinneti iii Supply 1 0 0 100 0 100 V Firm Keneee ity Elevetn39e mehe Dee Mines Ttel In sumC5E5 Demand 112 Shipping Bets 113 Keneee ity iiiizlmehe 1 1 1 1 15 Dee Mines 1 5 lim h tl 4 Sheet Sheet 1 I ll manav 23 gie hapeev a a D C Al Reedy H tartquot e em H SCME Ill Mi dwestFlnmr le 311 393 the 1123 pm 2 8 sumE5E7 THE UNIVERSITY 0F ALABAMA TP with ExcelSolver Elwinme 4 e 3 file Edit meant Fgrmat Ianl5 grate indme Help Type a question for help 7 E X Deneeeeeteenezeiieue v Q E E E 9 H39 Reply with Ell ll lgEEM 1 Ariel vlll vl I g F i156 SlUllilllF lRUlDlLJE39l E5clET lEclE lEu e D 39 Midwest Fleur T39tel Bust l D UU 3 EA IJIZIII 39 T T v Flel H l lil A e Shipments T Mills Ttel Chiceg StLuis Iincinneti ut Frm KensesBity39 I Elevetlrs mahe 100 Des Mines 100 100 Ii i T39tel In Supply lt 1 lt 25 Demand Sinleer Parameters game a minimize Shipping Cats m m r aremam mahe Des Minei alelslellelelellmlelelelel l l Iil Ed I H h hieetl 5 Sheet f Sheet f mamav is Amushapesv a a ElQE Read HSftarltll DIME llMicrese Mi dlwmll nulr 29 THE UNIVERSITY 0F ALABAMA An Optimal Solution i Mi cmSu ExEe Mi iwegtflpulr39 M le Edit mart Iml gain induw LIEIp Typea question forhelp v E X gawngplgvpvwwnvgzMHE v El QQIIYJReplyw thghangesm fghriial vlll v Q E 3393 1 313413 1 EW Y r EJUMHRUHDUCWE5IETC HBE H5 A E G I E F IGI HI I M iidwest leuw Ttal Cst1 Shipments T Miflllls TtalJ Chicag StLwiis Ei ciinln tii Owt Supply 4 1 4 25 4 0 1 N U Frm Kansasmty Elevatm Omaha Des MJ iinpes Ttall In Dema nd 1 SUWEII Regu tS 7 39 Shipping Casts Chicag SthiEl f zummmmw Kansas iw 395 a F Oman ha 7 1 1 r 15 Des Mines 4 5 m m ap 1 5 IE Im IM I It H w M IE4 Ir M f ElseBE f leEH f Emaw 22 Inmmhapesv a III All 5 3E 3quotquot mead H Starlj ma n Miicmm tpnmer Midasavast mr E W 3 353 11quot 30 THE UNIVERSITY 0F ALABAMA Another Optimal Solution E Mi l l ExEel Mi lwestflmmr le Edit mm mart Inma Qam in uw LIEIp Typea question forhelp v a x ED uplgv pv l gzv i v1 E E El I TJReplywnth QhangEEm 1 Ariiali v13 v I H E 3 5 113413 v i5 WMW WWCUWCEIEKCWEZE H E A B G I E F IGI HI u j M iidwest Flluw Ttal est 1 Shipments To Mille TtalJ Chicag StLwiis Eitmciimnatil Out Supply 4 1 4 25 4 100 U 70 0 100 100 Frm Kansasmty Elevators Omaha Des Ml iintes Ttall In Dema n d 1 Shipping Casts Chjiicag StlLI mmfppz mmmw Kansas ity 6 Omaha T 11 15 Des M1 i1ni3985 4 5 i i i i i i L i 1 E l 1 E E Ijei Ir M f HIEEli f leeta E 1 Enzawv R l utn hapea39 a III All 12 315E Iiquotquotquotii 39 E E E1 R aadyr Slartl 0M3 Miicmm tpnmerl Midwest nm ltlt E E3 241PM 31 THE UNIVERSITY 0F ALABAMA Another Example Elevator Annual Supply Mill Annual Demand Kansas City 170 Chicago 200 Omaha 250 St Louis 150 Des Moines 200 Cincinnati 250 Total 620 Total 600 Flour Mill Eitjtlgr Chicago St Louis Cincinnati Kansas City 7 8 10 Omaha 6 1 1 1 1 Des Moines 5 4 12 32 Cost of the Greedy Solution THE UNIVERSITY 0F ALABAMA From To Amount Rate Cost DesMoines StLouis 150 4 600 DesMoines Chicago 50 5 250 Omaha Chicago 150 6 900 KansasCity Cincinnati 170 10 1700 Omaha Cincinnati 80 1 1 880 Total 4330 Cost 33 THE UNIVERSITY 0F ALABAMA An Optimal Solution i Mi cmSu ExEe Mi iwegtflpulr39 M le Edit mart Iml gain induw LIEIp Typea question forhelp v E X gawngplgvpvwwnvgzMHE v El QQIIYJReplyw thghangesm fghriial vlll v Q E 3393 1 313413 1 EW Y r EJUMHRUHDUCWE5IETC HBE H5 A E G I E F IGI HI I M iidwest leuw Ttal Cst1 Shipments T Miflllls TtalJ Chicag StLwiis Ei ciinln tii Owt Supply 4 1 4 25 4 0 a 170 150 u an 39 1510 Frm Kansasmty Elevatm Omaha Des MJ iinpes Ttall In Dema nd 15 SHINEr Regu ts 39 Shipping Casts Chicag StLI f mmwmw Kansas ity Y Oman ha 6 1 1 r 15 Des Mines 5 4 at W w 1 5 IE Im IM I It H w M IE4 Ir H K Exarplel yJE lill l39f quot1 2mm Ire Inmhapw a D All 2 3157 39 mead H Starlj ma n Miicmm tpnmer Midasavast mr 53 W 33114 PM 34 THE UNIVERSITY 0F ALABAMA Benefit of Optimization 0 Example 1 Total cost of greedy solution 4830 Total cost of optimal solution 4730 Benefit 100 2 0 Example 2 Total cost of greedy solution 4330 Total cost of optimal solution 4330 Benefit 0 0 Sometimes the greedy heuristic is lucky 35

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.