Scribd Logo
Upload

Welcome to Scribd!

  • 338 views

    Unbounded Solution

    Uploaded by

    Hunain Memon
    The document discusses unbounded solutions in linear programming problems (LPs) and the two-phase simplex method to solve LPs involving artificial variables. It states that an unbounded solution occurs when the objective function can be improved indefinitely without violating constraints. The two-phase simplex method first constructs an auxiliary problem in Phase I to find a feasible solution, then uses this in Phase II as the starting point for the original problem to find the optimum.

    Copyright:

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

    Unbounded Solution

    Uploaded by

    Hunain Memon
    338 views2 pages
    The document discusses unbounded solutions in linear programming problems (LPs) and the two-phase simplex method to solve LPs involving artificial variables. It states that an unbounded solution occurs when the objective function can be improved indefinitely without violating constraints. The two-phase simplex method first constructs an auxiliary problem in Phase I to find a feasible solution, then uses this in Phase II as the starting point for the original problem to find the optimum.

    Original Description:

    solution types

    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 discusses unbounded solutions in linear programming problems (LPs) and the two-phase simplex method to solve LPs involving artificial variables. It states that an unbounded solution occurs when the objective function can be improved indefinitely without violating constraints. The two-phase simplex method first constructs an auxiliary problem in Phase I to find a feasible solution, then uses this in Phase II as the starting point for the original problem to find the optimum.

    Copyright:

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

    Unbounded Solution

    Uploaded by

    Hunain Memon
    The document discusses unbounded solutions in linear programming problems (LPs) and the two-phase simplex method to solve LPs involving artificial variables. It states that an unbounded solution occurs when the objective function can be improved indefinitely without violating constraints. The two-phase simplex method first constructs an auxiliary problem in Phase I to find a feasible solution, then uses this in Phase II as the starting point for the original problem to find the optimum.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Unbounded Solution

    In some LP models, the values of the variables may be increased indefinitely without violating
    any of the constraints, meaning that the solution space is unbounded in at least one direction. As
    a result, the objective value may increase (maximization case) or decrease (minimization case)
    indefinitely. In this case, both the solution space and the optimum objective value are
    unbounded.
    Unboundedness points to the possibility that the model is poorly constructed. The most
    likely irregularities in such models are that one or more nonredundant constraints have not been
    accounted for, and the parameters (constants) of some constraints may not have been estimated
    correctly.
    The rule for recognizing unboundedness is that if at any iteration all the constraint
    coefficients of any non basic variable are zero or negative, then the solution space is unbounded
    in that direction. If, in addition, the. Objective coefficient of that variable is negative in the case
    of maximization or positive in the case of minimization, then the objective value is unbounded as
    well.

    Two-Phase Simplex Method


    The two-phase simplex method is another method to solve a given LPP involving some artificial
    variable. The solution is obtained in two phases.
    Phase I
    In this phase, we construct an auxiliary LPP leading to a final simplex table containing a basic
    feasible solution to the original problem.
    Step 1 Assign a cost -1 to each artificial variable and a cost 0 to all other variables and get a new
    Objective function z' = -AI -A2 -A3 .............where Ai are artificial variable.
    Step 2 Write down the auxiliary LPP in which the new objective function is to be maximized
    subject to the given set of constraints.
    Step 3 Solve the auxiliary LPP by simplex method until either of the following three cases arise:
    (i) Max z. < 0 and at least one artificial variable appears in the optimum basis at positive level.
    (ii) Max z* = 0 and at least one artificial variable appears in the optimum basis at zero level.
    (iii) Max z* = 0 and no artificial variable appears in the optimum basis.
    In case (i), given LPP does, not possess any feasible solution, whereas in case (ii) and (iii) we
    go to phase II.
    PhaseII
    Use the optimum basic feasible solution of phase I as a starting solution for the original LPP.
    Assign the actual costs to the variable in the objective function and a zero cost to every artificial
    variable in the basis at zero level. Delete the artificial variable column from the table which is
    eliminated from the basis in phase I. Apply simplex method to the modified simplex table
    obtained at the end of phase I till an optimum basic feasible is obtained or till there is an
    indication of unbounded solution.

    You might also like