Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Chapter 2 (Graphic Resolution)

    Uploaded by

    chedli ben amara

    Copyright:

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

    Chapter 2 (Graphic Resolution)

    Uploaded by

    chedli ben amara
    2 views14 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    2 views14 pages

    Chapter 2 (Graphic Resolution)

    Uploaded by

    chedli ben amara

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 14

    Linear programming

    Chapter 2: Graphical resolution

    Fedia Daami Remadi Asma Ben Yaghlane Riahi Roua Ben Ammar

    Tunis Business School


    Any linear problem, having 2 decision variables, can be solved by
    the graphical method:

    • Make a representation on an orthonormal coordinate system (i, j)


    of the lines representing the constraints.

    • Determine the feasible region which satisfies all the different


    constraints.

    • Represent the line of the objective function allowing the search


    for the optimum in the field of possibilities.
    Graphical region describing all feasible solutions to a linear programming
    problem:
    • In 2-space: Polygon: each edge represents a constraint.

    Example
    2x1 + x2 ≤ 4

    In an LP environment, restrict to
    Quadrant I since x1, x2 ≥ 0
    Graphic Method Example:
    Step 1: Plot Boundary Conditions
    max 5x1 + 4x2
    subject to:
    x1 – 3x2 ≤ 3
    2x1 + 3x2 ≤ 12
    -2x1 + 7x2 ≤ 21
    x1,x2 ≥ 0

    4
    Graphic Method Example:
    Step 2: Determine Feasibility

    max 5x1 + 4x2


    subject to:
    x1 – 3x2 ≤ 3 B
    2x1 + 3x2 ≤ 12 A
    -2x1 + 7x2 ≤ 21
    x1,x2 ≥ 0
    Based only on this, C
    where might the optimal
    solution be?
    O D 5
    Graphic Method Example:
    Step 3: Plot Objective = c
    max 5x1 + 4x2 X1=-4/5X2
    (0,0)(-4/5,1)
    subject to:
    x1 – 3x2 ≤ 3
    2x1 + 3x2 ≤ 12
    -2x1 + 7x2 ≤ 21
    x1,x2 ≥ 0

    6
    Graphic Method Example:
    Step 4: Find Parallel Tangent

    max 5x1 + 4x2


    subject to:
    x1 – 3x2 ≤ 3
    B
    2x1 + 3x2 ≤ 12
    A
    -2x1 + 7x2 ≤ 21
    x1,x2 ≥ 0
    C
    Optimal solution:
    x1=5, x2=2/3, z=83/3 O D 7
    Graphic Method Example:
    Using the Corner point
    A(0; 3) ZA=12
    max 5x1 + 4x2 B(1; 10/3) ZB=55/3
    C(2/3; 5) ZC= 83/3
    subject to: D(3, 0) ZD= 15
    x1 – 3x2 ≤ 3 O(0, 0) Zo=0
    B
    2x1 + 3x2 ≤ 12
    A
    -2x1 + 7x2 ≤ 21
    x1,x2 ≥ 0
    C
    Optimal solution:
    X1*=xc1=5, X2*xc2=2/3, Z*=zc=83/3

    O D 8
    Special Cases
    Infeasibility: model has no feasible point

    Unboundness: objective can become infinitely large


    (max), or infinitely small (min).

    Alternate solution (multiple optimal solution): more


    than one point optimizes the objective function
    Special Cases
    Infeasibility

    No point, simultaneously,
    lies both above line 1 and

    2
    below lines 2 and 3
    .

    3 1
    Special Cases
    Unboundness
    the Ma
    Ob x im
    jec ize
    tiv
    eF
    Th un
    cti
    ef on
    e
    reg asib
    ion le
    Special Cases: Alternate solution
    (multiple optimal solution)
    For multiple optimal solutions to exist, the OF must be parallel to one of
    the constraints

    •Any weighted average of optimal


    solutions is also an optimal solution.

    12
    Minimization Problem
    Minimize 0.60X1 + 0.50X2
    Subject to
    20X1 + 50X2 ≥ 100
    25X1 + 25X2 ≥ 100
    50X1 + 10X2 ≥ 100
    X1 , X 2 ≥ 0

    13
    1
    C3
    X1*= 1.5
    0 X2*= 2.5
    Feasible Z*=$ 2.15.
    Region
    C2

    C1

    2 4 5 14

    You might also like