Purchase Solution

Linear Programming : Maximizing Subject to Constraints and Knapsack Algorithm Problem

Not what you're looking for?

Ask Custom Question

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
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
Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Probability Quiz

Some questions on probability

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.