Linear Programming : Maximizing Subject to Constraints and Knapsack Algorithm Problem
Not what you're looking for?
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 ≤ 0 for any j.
3. Consider the linear programming problem:
Maximize cx
subject to Ax=b, x ≥ 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 + λd where λ 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 λ ≥ 0
Purchase this Solution
Solution Summary
Maximizing Subject to Constraints and a Knapsack Algorithm Problem are investigated. The solution is detailed and well presented.
Purchase this Solution
Free BrainMass Quizzes
Graphs and Functions
This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Probability Quiz
Some questions on probability