Linear Programming

Management Decisions

  • involves effective use of resources (machinery, labor, money, time, warehouse space, and raw materials) in order to:
    • Produce products - such as computers, automobiles, or clothing or
    • Provide services - such as package delivery, health services, or investment decisions
  • To solve problems of resource allocation one may use mathematical programming.

Linear Programming

  • the most common type of mathematical programming.
  • a particular type of mathematical model in which relationships involving the variables are linear.
  • uses a mathematical technique which determines the best or optimal decision .
  • Decision variables - mathematical symbols representing levels of activity of a firm.
  • Objective function – is the mathematical expression of the objective that the decision maker wants to achieve in a given linear programming decision situation, in terms of decision variables, that is to be maximized or minimized.
    • Commonly addressed in linear programming
    • Maximization of Profit or Revenue
    • Minimization of Losses or Cost
  • Constraints – is the linear mathematical expression of the relationships between the resource limitations and the resource requirements associated to the objective variables specified in a linear programming problem.
  • Parameters - numerical coefficients and constants used in the objective function and constraint equations

Types of Constraints

  • Capacity Constraints -These are limits because of space, equipment or manpower availability
  • Market Constraints - These are limits on how many products can be sold or used.
  • Availability Constraints - These are limits because of scarcity of raw materials, funds or other resources.
  • Quality or Blending Constraints - These are constraints that put limits on mixes of ingredient, usually defining the quality of output products.
  • Material Balance Constraints - These are constraints that define the output of some process as function of the inputs, often with a loss for scrap.

Linear Graphical Method

Graphical Method

  • Constraint - A limit on the availability of resources.
  • Extreme point - A corner of the feasible region
  • Feasible region - The area containing all the possible solutions to the problem, which are feasible, that is, those solutions which satisfy all the constraint in the problem.
  • Inequality - A mathematical expression indicating that minimum or maximum requirements must be met.
  • Infeasibility - The condition when there is no solution which satisfies all the constraints in a problem.
  • Iso-cost line - A line representing all possible combinations of problem variables which produce the same total cost
  • Iso-profit line - A line representing all possible combinations of products which will produce a given profit.
  • Non-negativity constraints - Constraints that restrict all variables to be zero or positive.
  • Redundancy - A constraint which does not affect the feasible region.
  • Structural Constraints - All constraints in a linear program besides the non-negativity constraints.

Simplex Method

  • Graphical solution - becomes impractical when there are three or more variables involved in the problem.
  • Simplex Method - is more appropriate method in solving complicated linear programming models.
  • Simplex method - is an iterative process.
  • Successive solutions are developed in a systematic way until the best solution is reached.
  • Artificial variable - A computational device used in linear programming to achieve an initial solution to the problem.
  • Augmentation - The process of adding slack and/or artificial variables to constraints to generate equations.
  • Cj column -. A column in the simplex tableau which contains the profit or cost per unit for the variable in the solution.
  • Cj-Zj row - The row containing the net benefit or loss occasioned by bringing one unit of a variable into the solution of a linear programming problem. Intersectional elements.
  • Elements which are common to both the optimum column and the rows representing variables in the solution.
  • Iterative process - A step-by-step process following a standard pattern.
  • Optimum column - That column in any solution to a maximizing problem which has the largest positive value in the Cj-Zj row or which has the largest negative value in a minimizing problem.
  • Pivoting - The process of going from one simplex tableau to the next.
  • Product-mix column - The column containing all the variables in a solution in the simplex tableau.
  • Quantity column - The column in a simplex tableau indicating the quantities of the variables that are in a solution.
  • Reduced costs -The entries of the Cj-Zj row