Mathematical ProgrammingComponents of Math-ProgExamplesMajor Classes of Mathematical ProgrammingSlide 5Linear Programming - Standard FormSlide 7PowerPoint PresentationLP expressionsSlide 10Linear Programming – Conversion to Standard FormSlide 12Slide 13Slide 14Slide 15Slide 16ExampleSolutionSlide 19Slide 20exercisesMathematical Programming•Mathematical Programming considers the problem of allocating limited resources among competing activities.•These resources could be people, capital, equipment, and competing activities might be products or services, investments, marketing media, or transportation routes.•The objective of mathematical programming is to select the best or optimal solution from the set of solutions that satisfy all of the restriction on resources, called feasible solutions.Components of Math-Prog•Decision Variables,–Those factors that are controlled by decision maker. Example: How many products, No of people, Amount of money allocated•Objective function–A performance measure such as Maximizing profit, Minimizing cost, Minimizing delivery time•Constraints–Restrictions that limit availability and manner that resources can be used to achieve the objective. Example: Limitation on labor, Time available to process a procedure.Examples•An Operation Manger whishes to determine the most profitable mix of products or services that meets restrictions on labor, material and equipment while meeting forecasted demands.•A call center manager needs to decide how many technicians must be scheduled during each shift so that the forecasted call volume during the day can be met.•A marketing manager must decide how to allocate the advertising budget to different media depending on cost, effectiveness and mix constraints.•A transportation manager wishes to determine the shortest routes for its delivery vehicle while serving all of its customers.Major Classes of Mathematical Programming•Continuous Linear Programming (LP)–Values are real numbers–Makes 4 assumptions: Linearity, Divisibility, Certainty, and non negativity. •Discrete (Integer Programming)–Assumes that the decision parameters must take on integer values.•Non linear programming (NLP)–Assumes that the relationship in the objective function and/or constraint may be nonlinearMajor Classes of Mathematical Programming•Combinatorial Optimization: Many optimization problems that occur in network design are associated with a combinatorial structure, typically a graph. This often imposes theconstraint that the variables are 0-1 valued, i.e, can only take 2 possible values (0 or 1). Then we often speak about combinatorial optimization.Linear Programming - Standard Form0,...,0,00,...,0,0................212122112222212111212111111111mnmnmnmmnnnnnnbbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcxcZMaximize (Minimize):Subject to:Linear Programming - Standard Form0,...,0,00,...,0,0................212122112222212111212111111111mnmnmnmmnnnnnnbbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcxcZMaximize (Minimize):Subject to:ObjectiveFunctionConstraint SetNon-negativeVariablesConstraintNon-negativeRight-hand sideConstants•Thus, a linear programming problem (or linear program, for short; abbreviated LP) looks like this for minimization:–minZ = c1x1 + c2x2 + . . . + cnxn–subject toa11x1 + a12x2 + . . . + a1nxn = b1a21x1 + a22x2 + . . . + a2nxn = b2 ...am1x1 + am2x2 + . . . + amnxn = bmx1 >= 0...xn >= 0LP expressions•An important restriction is that we only allow linear expressions, both in the objective function and in the constraints. •A linear expression (in terms of the xi variables) can only be one of the following:–a constant–a variable xi multiplied by a constant (such as cixi )–sum of expressions that belong to either the above typesLP expressions•(Examples: c1x1 + c2x2 + . . . + cnxn, or 3x4 − 2).•No other types of expressions are allowed. In particular, no product of variables, no logical case separation, etc.Linear Programming – Conversion to Standard FormInequality constraints: slack or surplus variables101088211211xxxxxxs.t.=>s.t.=>x2 – slack variablex2 – surplus variableLinear Programming - Standard Form00bxbAxcxZMaximize (Minimize):Subject to:Linear Programming - Standard Form00bxbAxcxZMaximize (Minimize):Subject to:mnmmnnaaaaaaaaa...........212222111211Ambbb.21bmxxx.21x]...[21 nccccwhere,Linear Programming – Conversion to Standard FormUnrestricted variables: replace with 2 non-negative variables24343112212minedunrestrictis,0.s.t2minxxxZxxxxxxxZset,=>Linear Programming – Conversion to Standard FormExample:edunrestrict02,052327..32min31321321321321xxxxxxxxxxxxtsxxxZLinear Programming – Conversion to Standard Form0,,,,,522327..332min765421542175421654215421xxxxxxxxxxxxxxxxxxxxtsxxxxZExample:Example•Convert the following LP into standard form:–minZ = 5x − 6y; subject to–2x − 3y >= 6–x − y <= 4–x >= 3Solution•Set y = x2 − x3 for the free (unbounded) variable y, using the fact that any number can be expressed as the difference of two nonnegative numbers. •Furthermore, introduce a slack variable in each inequality.Solution•the first constraint 2x − 3y >= 6 will be transformed as follows.–Let us use x1 instead of x, for uniform notation.–The variable y will be replaced by x2 − x3, where x2, x3 >= 0. Then we get–2x1− 3(x2 − x3) − x4 = 6.•After transforming the other inequalities, too, and also substituting the old variables in the objective function with the new ones, we get the entire standard form:–minZ = 5x1 − 6x2 + 6x3; subject to–2x1 − 3x2 + 3x3 − x4 = 6–x1 − x2 + x3 + x5 = 4–x1 − x6 = 3–x1, x2, x3, x4, x5, x6 >=
View Full Document
Unlocking...