Share
Explore BrainMass

Linear Programming : Maximizing Subject to Constraints and Knapsack Algorithm Problem

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
n
Maximize ∑cj xj,
j=1

n
subject to ∑aj xj ≤ b , xj ≥ 0, for j=1,.....,n where b >0 , cj ≥ 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

Attachments

Solution Summary

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

$2.19