Scribd Logo
Upload

Welcome to Scribd!

  • 922 views

    MMW s15 PDF

    Uploaded by

    Russel Cipres
    The document provides an overview of linear programming and the simplex method. It discusses how linear programming problems can be solved graphically or using the simplex method. The simplex method is an iterative technique that starts with a feasible solution and uses algebraic manipulation to improve the solution at each iteration until an optimal solution is found. The document provides definitions of key terms related to the simplex method and includes an example problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    MMW s15 PDF

    Uploaded by

    Russel Cipres
    922 views16 pages
    The document provides an overview of linear programming and the simplex method. It discusses how linear programming problems can be solved graphically or using the simplex method. The simplex method is an iterative technique that starts with a feasible solution and uses algebraic manipulation to improve the solution at each iteration until an optimal solution is found. The document provides definitions of key terms related to the simplex method and includes an example problem.

    Original Title

    MMW-s15.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides an overview of linear programming and the simplex method. It discusses how linear programming problems can be solved graphically or using the simplex method. The simplex method is an iterative technique that starts with a feasible solution and uses algebraic manipulation to improve the solution at each iteration until an optimal solution is found. The document provides definitions of key terms related to the simplex method and includes an example problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    922 views16 pages

    MMW s15 PDF

    Uploaded by

    Russel Cipres
    The document provides an overview of linear programming and the simplex method. It discusses how linear programming problems can be solved graphically or using the simplex method. The simplex method is an iterative technique that starts with a feasible solution and uses algebraic manipulation to improve the solution at each iteration until an optimal solution is found. The document provides definitions of key terms related to the simplex method and includes an example problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 16
    At a glance
    Powered by AI
    Linear programming is an optimization technique used to maximize or minimize objectives subject to constraints. It can be used to help plan efficient use of resources. The simplex method is an algorithm used to solve linear programming problems by iteratively moving to adjacent basic feasible solutions until an optimal solution is reached.

    Linear programming is an optimization technique that seeks to maximize or minimize linear objectives subject to linear equality and inequality constraints. It can be used in fields like business, economics and operations research to help with resource allocation and planning problems. The simplex method is an algorithm for solving linear programming problems.

    The simplex method is an iterative technique that starts with a feasible solution and uses algebraic manipulation at each step to improve the solution until an optimal solution is reached. It involves identifying a pivot column and row at each step to derive a new basic feasible solution until no further improvements are possible.

    Linear Programming (LP)

    Simplex Method

    Lecture Notes in Mathematics in the


    Modern World

    Session 15

    National University

    August 22, 2018

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Overview

    1 Linear Programming (LP)

    2 Simplex Method

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Today’s Learning Outcomes

    At the end of the day, the student must be able to:


    Solve LP Problems graphically. .
    Assessment
    Recitation
    Board work

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    QUIZ

    In a certain hospital, a nutritionist prepares a menu for patients on


    low-fat diets. The primary ingredients are chicken and rice. The
    meal must contain enough protein and iron to meet at least the
    DOH recommended daily allowance (RDA) for each nutrient. The
    RDA for protein is 60 grams and 30 milligrams. Each 4-ounce
    serving of chicken contains 60 grams of protein , 15 milligrams of
    iron, and 6 grams of fat. Each 1-cup serving of rice contains 12
    grams of protein, 9 milligrams of iron, and 3 grams of fat. How
    much chicken and rice should be included in the meal in order to
    minimize the amount of fat?

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Simplex Method

    Simplex Method is an iterative technique that begins with a


    feasible solution that is not optimal, but serves as a starting
    point.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Simplex Method

    Simplex Method is an iterative technique that begins with a


    feasible solution that is not optimal, but serves as a starting
    point.
    With the use of algebraic manipulation, the solution is
    improved until no further improvement is posible.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Simplex Method

    Simplex Method is an iterative technique that begins with a


    feasible solution that is not optimal, but serves as a starting
    point.
    With the use of algebraic manipulation, the solution is
    improved until no further improvement is posible.
    The simplex method requires that all constraints be expressed
    as equations.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Simplex Method

    Simplex Method is an iterative technique that begins with a


    feasible solution that is not optimal, but serves as a starting
    point.
    With the use of algebraic manipulation, the solution is
    improved until no further improvement is posible.
    The simplex method requires that all constraints be expressed
    as equations.
    All the inequalities shall be converted into equations or in the
    standard form of linear programming problem.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Standard LP Model

    A standard LP maximization model is of the form


    Maximize: P = a1 x1 + a2 x2 + · · · + an xn
    Subject to bi x1 + bi x2 + · · · + bi xn ≤ ci xi ≥ 0, 1 ≤ i ≤ m
    where ci > 0 for all i.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Steps in Solving Standard LP Maximization Model Using Simplex


    Method
    1 Set up an LP model of the Problem.
    2 Introduce the necessary Slack Variables.
    3 Establish the initial Tableau.
    4 Examine the simplex tableau for optimal solutions. If the basic
    feasible solution is maximal, the problem is solved. Otherwise,
    proceed to step 5.
    5 Compute a new simplex tableau: select the pivot column, find
    pivot row, and pivot about the pivot entry.
    6 Proceed to step 4.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Definition of Terms

    Slack Variables - variables added to constraints to convert


    them into equations.
    Iteration - is a simplex method which consists of steps (row
    operations) performed in moving one basic feasible solution to
    another.
    Simplex Tableau - is a table used to keep track of the
    calculations made when the simplex method is employed.
    Pivot Column - is the column in any solution to a
    maximization problem which has the lowest value in the last
    row.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Definition of Terms

    Intersectional Elements are elements common to both the


    pivot column and the rows representing variables in the
    solution.
    Pivot Row - is the row in the simplex tableau corresponding
    to the basic variable that will leave the solution. It is
    determined by the test ratio computed by dividing RHS by
    the intersectional elements.
    Pivot is the intersection of the pivot row and pivot column.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Initial Tableau to Simplex Tableau

    Identify the pivot column.


    Find the pivot row.
    Find the pivot.
    Identify the Leaving variable, entering variable, and
    intersectional elements (IE).
    Use the formula: RR = PR / P [RR - replacing row, PR -
    pivot row, P - pivot]
    Use the formula: R’R = P’R - (IE x RR) [R’R - remaining
    row, PR - previous row]
    Enter the results in Tableau 2.
    Tableau is optimal if there are no negative entries in the last
    row.

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Example

    A local boutique produced two designs of gowns A and B and has


    the following materials available: 18 m2 of cotton, 20 m2 of silk,
    and 5 m2 of wool. Design A requires the following: 3 m2 of cotton,
    2 m2 of silk, and 1 m2 of wool. Design B requires the following: 2
    m2 of cotton, 4 m2 of silk. If Design A sells for 1200 pesos and
    Design B for 1600 pesos, how many of each garment should the
    boutique produce to obtain maximum amount of money?

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    Exercise

    Maximize 13x + 6y
    Subject to x + 2y ≤ 8
    2x + y ≥ 8
    2x + 2y ≤ 16
    x ≥ 0, y ≥ 0

    Session 15 Lecture Notes in Mathematics in the Modern World


    Linear Programming (LP)
    Simplex Method

    REFERENCE

    Bazaraa, M., Jarvis, J., Sherali, H. (2010). Linear


    Programming and Network Flows (4th ed.). Wiley.
    Sirug, W. S. (2018). Mathematics in the Modern
    World. Mindshapers Co., Inc.

    Session 15 Lecture Notes in Mathematics in the Modern World

    You might also like