Scribd Logo
Upload

Welcome to Scribd!

  • 11 views

    Or1 HW

    Uploaded by

    Throwaway Two
    Operations research hw

    Copyright:

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

    Or1 HW

    Uploaded by

    Throwaway Two
    11 views9 pages
    Operations research hw

    Original Title

    OR1 HW

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Operations research hw

    Copyright:

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

    Or1 HW

    Uploaded by

    Throwaway Two
    Operations research hw

    Copyright:

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

    Problem 2

    Classify each of the following according to whether it: has a unique optimal solution, has multiple optimal
    solutions, is infeasible, or is unbounded.

    Maximize z = x1 + x2
    S.t. x1 + x2 ≤ 4
    x1 - x2 ≥ 5
    x1,x2 ≥ 0
    Infeasible

    Maximize z = 4x1 + x2
    S.t. 8x1 + 2x2 ≤ 16
    5x1 + 2x2 ≤ 12
    x1,x2 ≥ 0
    Feasible (multiple solution)

    Maximize z = -x1 + 3x2


    S.t. x1 - x2 ≤ 4
    x1 + 2x2 ≥ 4
    x1,x2 ≥ 0
    Unbounded

    Maximize z = 3x​1​ + x​2


    S.t. 2x1 + x2 ≤ 6
    x1 + 3x2 ≤ 9
    x1,x2 ≥ 0
    Feasible (unique solution)
    Problem 3
    Maximize z = x1 - x2

    S.t. x1 + x2 ≤ 6
    x1 - x2 ≥ 0
    x1 - x2 ≥ 3
    x1,x2 ≥ 0

    Optimal solution is found in extreme point (6,0) where z = 6. Constraints that are binding here are
    x1 + x2 ≤ 6 and x1 - x2 ≥ 3.

    Maximize z = x1
    S.t. -x1 + x2 ≤ 2
    x1 + x2 ≤ 8
    -x1 + x2 ≥ -4
    x1,x2 ≥ 0

    Optimal solution is found in (6,2) where z = 6. Constraints that are binding here are x1+ x2 ≤ 8
    - x1+ x2 ≥ -4.
    Problem 5
    For the following LPs, show how the basic feasible solutions to the LP in standard form correspond to the
    extreme points of the feasible region.
    Max z = = 3 x1 + 5 x2
    Subject to
    2x1 + x2 ≤ 100
    x1 + x2 ≤ 80
    x1 ≤ 40
    x1 ≥ 0
    x2 ≥ 0

    Standard form of given LP


    Max z = 3 x1 + 5 x2
    Subject to
    2x1 + x2 +s1 = 100
    x1 + x2 +s2 = 80
    x1 +s3 = 40
    x1, x2, s1, s2, s3 ≥ 0

    NBV BV x1 x2 s1 s2 s3 BFS Z Corner


    Point

    x1, x2 s1, s2, s3 0 0 100 80 40 Yes 0 E

    x1, s1 x2, s2, s3 0 100 0 -20 40 No - -

    x1, s2 x2, s1, s3 0 80 20 0 40 Yes 400 A


    x1, s3 x2, s1, s2 - - - -- - - Not -
    feasible

    x2, s1 x1, s2, s3 50 0 0 30 -10 No - -

    x2, s2 x1, s1, s3 80 0 -60 0 -40 No - -

    x2, s3 x1, s1, s2 40 0 20 40 0 Yes 120 D

    s1, s2 x1, x2, s3 20 60 0 0 20 Yes 360 B

    s1, s3 x1, x2, s2 40 20 0 0 0 Yes 220 C

    s2, s3 x1, x2, s1 40 40 -20 0 0 No - -

    Problem 6
    Convert the following LP into one in standard form.
    Maximize z = 3x1 + 5x2 -x3
    Subject to
    x1 + 2x2 + 4x3 ≤ -4
    -5x1 -3x2 +x3 ≥ 15
    x2 ≤ 0
    x3 ≥ 0

    Solution:
    Slack variable for constraint 1 is s1
    Surplus variable for constraint 2 is s2
    Convert x2 to nonnegative by introducing variable y2 where x2 = -y2
    Convert URS x1 to nonnegative by introducing variables w1 and y1 where x1 = y1-w1

    Standard Form of the LP


    Maximize z = 3y1 - 3w1 - 5y2 -x3
    Subject to
    y1- w1 - 2y2 + 4x3 + s1 = -4
    -5y1 +5w1 +3y2 +x3 - s2 = 15
    x3, y1, y2, w1,s1, s2 ≥ 0
    Exercise B
    Problem 4
    The following is part of a simplex tableau. Determine the departing variable if the entering variable is (a)
    x5, (b) x3, (c) x7.
    Problem 7

    BV NBV

    z 42 x1 0

    x3 10 x2 0

    u -34 w 0

    v 22
    Problem 8
    #1

    Max z = 2x1 + 3x2 -x3


    S.t.
    x1 + 2x2 -x3 ≤ 6
    x1 - 3x2 - 3x3 ≤ 10
    x1, x2, x3 ≥ 0

    Solution:
    Slack variable for constraint 1 is s1
    Slack variable for constraint 2 is s2

    Standard Form of the LP


    Max z - 2x1 - 3x2 + x3 = 0
    S.t.
    x1 + 2x2 -x3 + s1 = 6
    x1 - 3x2 - 3x3 + s2 = 10
    x1, x2, x3, s1, s2 ≥ 0
    N = 5, m = 2
    N-m = 3 NBVs
    Let x1,x2, x3 = 0
    S1 = 6, S2 = 10
    #2

    Max z = x1 + 2x2 + x3 + x4
    S.t.
    2x1 + x2 + 3x3 + x4 ≤ 8
    2x1 + 3x2 + 4x4 ≤ 12
    3x1 + x2 + 2x3 ≤ 18
    x1, x2, x3, x4 ≥ 0

    Solution:
    Slack variable for constraint 1 is s1
    Slack variable for constraint 2 is s2
    Slack variable for constraint 3 is s3

    Standard Form of the LP


    Max z - x1 - 2x2 - x3 - x4 = 0
    S.t.
    2x1 + x2 + 3x3 + x4 + s1 = 8
    2x1 + 3x2 + 4x4 + s2 = 12
    3x1 + x2 + 2x3 + s3 = 18
    x1, x2, x3, x4, s1, s2, s3 ≥ 0
    N = 7, m = 3
    N-m = 4 NBVs
    Let x1,x2, x3, x4 = 0
    s1 = 8, s2 = 12, s3 = 18

    You might also like