Explore BrainMass

Explore BrainMass

    Linear Programming : Maximizing Subject to Constraints and Knapsack Algorithm Problem

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    1. Solve the following linear programming problem by the simplex method. At each iteration, identify B and B-1

    Maximize 3x1 + 2x2 + x3
    Subject to 3x1 - 3x2 + 2x3 ≤ 3
    - x1 + 2x2 + x3 ≤ 6
    x1, x2 ,x3 ≥ 0.

    2. Consider the following linear programming problem

    Maximize 2x1 + 2x2 + 4x3 + 5x5 + 3x6
    Subject to 3x1 + 6x2 + 3x3 +3x4 +3x5 + 4x6 ≤ 60
    x1, x2, x3, x4,x5, x6 ≥ 0

    This problem has one constraint in addition to the non negativity constraints, and is called knapsack problem. Find all the basic feasible solutions of the problem, and find an optimum by comparing these basic feasible solutions. Hence, prescribe a general rule to solve a knapsack problem of the type
    Maximize ∑cj xj,

    subject to ∑aj xj ≤ b , xj ≥ 0, for j=1,.....,n where b >0 , cj ≥ 0 , for all j, and aj >0
    ,for all j, based on the ratios cj/aj, j=1,....,n. Comment on how you would treat the case cj < 0 for any j, or cj > 0 and aj &#8804; 0 for any j.

    3. Consider the linear programming problem:
    Maximize cx
    subject to Ax=b, x &#8805; 0, where A is an m x n matrix of rank m. Suppose that an optimal solution with basis B is at hand. Further suppose that b is replaced by b + &#955;d where &#955; is a scalar and d is a fixed nonzero vector of dimension m. Give a condition such that the basis B will be optimal for all &#955; &#8805; 0

    © BrainMass Inc. brainmass.com December 24, 2021, 5:46 pm ad1c9bdddf


    Solution Summary

    Maximizing Subject to Constraints and a Knapsack Algorithm Problem are investigated. The solution is detailed and well presented.