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 &#8804; 3
- x1 + 2x2 + x3 &#8804; 6
x1, x2 ,x3 &#8805; 0.

2. Consider the following linear programming problem

Maximize 2x1 + 2x2 + 4x3 + 5x5 + 3x6
Subject to 3x1 + 6x2 + 3x3 +3x4 +3x5 + 4x6 &#8804; 60
x1, x2, x3, x4,x5, x6 &#8805; 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
n
Maximize &#8721;cj xj,
j=1

n
subject to &#8721;aj xj &#8804; b , xj &#8805; 0, for j=1,.....,n where b >0 , cj &#8805; 0 , for all j, and aj >0
j=1
,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