Class Notes (809,264)
Canada (493,601)
York University (33,561)
Marketing (184)
MKTG 2030 (72)
Ben Kelly (12)

Lecture 1.pdf

21 Pages
Unlock Document

York University
MKTG 2030
Ben Kelly

OMIS2010 Lecture Notes Jessica Gahtan Page 2 of 21 OMIS2010 Lecture Notes Jessica Gahtan Lecture 1- January 8, 2013: Intro to Linear Programming - We need to realize that in business we will make decisions given a constrained environment and we want to make the best decision in light of limitations you have in a given situation (that is, you want to use your limited resources to do as well as possible) The Decision Process - Organizations have access to limited resources (time, space, etc.) which impacts the way that managers meet their objectives - Linear programming (LP) is one way that managers can determine the best way to allocate their scarce resources; it’s a systematic process to come up with the best course of action (it can also identify some other opportunities) LP Applications - Flexible, general structure - not limited to specific industry or area within business - Aviation, military, businesses, transportation, facility location problem Examples: a) Scheduling school buses to minimize total distance traveled(transportation) b) Allocating police patrol units to high crime areas in order to minimize response times to 911 calls c) Scheduling tellers at banks so that needs are met during each hour of the day while minimizing the total cost of labor Mathematical Program ming - A mathematical programming problem is one that seeks to optimize an objective function subject to constraints → want to optimize- achieve goal as much as possible Types of mathematical programming problems: Linear programming – focusing on these primarily – the structure of the problem seems restrictive BUT a lot of situations can be represented – get extra insights – advantages – foundation for exploring integer situations – have more power Integer Programming Non-linear Programming – when a problem isn’t linear Requirements of an LP Problem 1. LP problems seek to maximize or minimize some quantity (usually profit or cost) expressed as an objective function 2. The presence of restrictions, or constraints, limits the degree to which we can pursue the objectives – i.e. in deciding how many units of each product in a firm’s product line to manufacture is restricted by available labor and machinery • Can’t have unlimited profit because of restrictions like time, rules (i.e. labor law) wh ich hold us back from achieving more 3. A feasible solution satisfies all the problem’s constraints • Where the possible choices for decision variable are the different combinations that can work 4. An optimal solution is a feasible solution that results in the largest possible objective function value when maximizing (or smallest when minimizing) 5. A graphical solution method can be used to solve a linear program with two variables 6. If both the objective function and the constraints are linear, the problem is referred to as a linear programming problem 7. Linear functions are functions in which each variable appears in a separate term raised to the first power and is multiplied by a constant (which could be 0) • None of the variables can be squared or multiplied by each other – can be added to subtracted from one another 8. Linear constrains are linear functions are restricted to be ‘less than or equal to’, ‘equal to’, or ‘greater than or equal to’ • This is important- gives us something to test 9. Problem formulation or modeling is the process of translating a verbal statement into a mathematical problem Page 3 of 21 OMIS2010 Lecture Notes Jessica Gahtan • Going from the description to story/ math • While the math part is mechanical – the hard part is going from story to math- this part takes insight Linear Programming - Formulate the LP (Decision variables; objective function and constraints) - Solution Methods (Graphical; Corner points method; excel solver; [Simplex]) Guidelines for Model Formulation 1. Understand the problem thoroughly 2. Describe the objective 3. Describe each constraint 4. Define the decision variables 5. Write the objective in terms of the decision variables 6. Write the constraints in terms of the decision variables Example: LP Formulation The Stratton Company produces 2 basic types of plastic pipe. Three resources are crucia l to the output of pipe: extrusion hours, packaging hours, and a special additive to the plastic raw material. Below is the next week’s situation. Each unit of type1 yields $34, and each unit of type2 yields $40 Product Resource Type1 Type2 Resource Availability Extrusion 4hr 6hr 48hr Packaging 2hr 2hr 18hr Additive Mix 2lb 1lb 16lb Limit: Resource Availability Step  1:  Define  the  Objective   Maximize total profit Step  2:  Define  the  Decision  Variables     X 1 amount of type1 pipe to be produced and sold next week X 2 amount of type2 pipe to be produced and sold next week Step  3:  Write  the  mathematical  objective  function   Max: $34 ∗ 𝑥 ▯ $40 ∗ 𝑥 =▯𝑧 Step  4:  Formulate  the  Constraints   Extrusion: 4𝑥 ▯ 6𝑥 ≤▯  48 Packaging: 2𝑥 + 2𝑥 ≤  18 ▯ ▯ Additive mix: 2𝑥▯+ 𝑥 ≤▯  16 Inequalities: 1. Typically the constraining resources have upper or lower limits For example: For the Stratton Company, the total extrusion time must not exceed the 48 hours of capacity available, so we use the ≤ sign 2. Negative values for constraints 𝑥 ▯nd 𝑥 d▯ not make sense, so we add the non -negativity restrictions in the model: 𝑥 ▯ ≥  0 and 𝑥▯  ≥  0 (non negativity restrictions) 3. Other problems might have constraining resources requiring ≥,=,𝑜𝑟 ≤  restrictions LP in the Final Form Max 𝑧 = $34 ∗ 𝑥 ▯ $40 ∗ 𝑥 , ▯ubject to: Page 4 of 21 OMIS2010 Lecture Notes Jessica Gahtan 1. 4𝑥▯+ 6𝑥 ≤▯  48 (Extrusion constraint) 2. 2𝑥▯+ 2𝑥 ≤▯  18 (Packaging constraint) 3. 2𝑥 + 𝑥 ≤  16 (Additive mix constraint) ▯ ▯ 4. 𝑥▯,𝑥▯  ≥  0 (non-negativity constraints) ^ Equations are on the left side only, values of the constraint are on the right side only Graphical Solution Most linear programming problems are solved with a computer. However, insight into the meaning of the computer output, and linear programming concepts in general, ca n be gained by analyzing a simple two - variable problem graphically . Graphical Method of linear programming: A type of graphical analysis that involves 5 steps: 1. Plotting the constraints 2. Identifying the feasible region 3. Plotting an objective function line 4. Finding a visual solution 5. Finding the algebraic solution Step  1:  Plotting  the  constraint  equations – disregarding the inequality portion of the constraints (> or < ). Making each constraint an equality (=) transforms it into the equation for a straight line. Step  2:  Identifying  the  feasible  region   The feasible region is the area on the graph that contains the solutions that satisfy all the constraints simultaneously; to find it, first locate the feasible points for each constraint and then the area that satisfies all the constraints. - The feasible region for a two -variable LP problem can be nonexistent, a single point , a line, a polygon, or an unbounded area - Any linear problem falls into one of 3 categories: 1. Is infeasible 2. Has a unique optimal solution or alternate optimal solutions 3. Has an objective function that can b e increased without bound - A feasible region may be unbounded and yet there may be optimal solutions. This is common in minimization problems and is possible in maximization problems Graphical Solution Generally, the following 3 rules identify the feasible points for a given constraint: 1. For the = constraint, only the points on the line are feasible constraints 2. For the ≤ constraint, only the points on the line, and the points below or to the left of the line are feasible constraints 3. For the ≥ constraint, only the points on the line, and the points above or to the right of the line are feasible constraints Page 5 of 21 OMIS2010 Lecture Notes Jessica Gahtan Graphical Analysis - The Feasible Region a) b) c) d) e) Page 6 of 21 OMIS2010 Lecture Notes Jessica Gahtan Find the Optimal Solution We will demonstrate two approaches to find the optimal solutions: 1) Iso- Profit Line/ Level curve 2) Corner Points Iso-Profit Line/ Level curve- Solution Method Step  1:  Choose  a  possible  range  for  the  objective  function   𝑧 = $34𝑥 + $40𝑥 ▯ ▯ 204 = $34𝑥 +▯$40𝑥 ▯ Step  2:  Solve  for  the  axis  intercepts  of  the  function  and  plot  the  line - A series of dashed lines can be drawn parallel to this first line. - Each would have its own Z value: Lines above the first line would have higher Z values; Lines below it would have lower Z values. - Our goal is to maximize profits, so the best solution is a point on the iso-profit line farthest from the origin but still touching the feasible region Find Point C: I: 41 + 6x2=48 (extrusion) II: 21 +2x2= 18 (packaging) 2x1+4x 2 30 x1+2x 2 15 x1= 15 - 2x 2 I: 4 (15-2x 2+6x =248 60-8x 2 6x =28 60-2x 248 x1=15-2*6=3 Z= 34*3+40*6=$342 Graphical Solution - Corner Points Approach Now we want to find the solution that optimizes the objective function - Even though all the points in the feasible region represent possible solutions, we can limit our search to the corner points Corner point: A points that lies at the intersection of two (or possibly more) constraint lines on the boundary of the feasible re gion - No interior points in the feasible region need be considered because at least one corner point is better than any interior point The best approach is to plot the objective function on the graph of the feasible region for some arbitrary Z values Page 7 of 21 OMIS2010
More Less

Related notes for MKTG 2030

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.