 # 1) Construct the canonical forms of the following linear programs. ...

## Question

1) Construct the canonical forms of the following linear programs.
(a) max { 3x + 2y } subject to:
2x - y ≤ 6;
2x + y ≤ 10;
x, y ≥ 0.
(b) max { x + y } subject to:
-2x + y ≤ 0;
x - 2y ≤ 0,
x + y ≤ 9;
x, y ≥ 0.
(c) min { 2x₁ - x₂ + 3x₃ } subject to:
x₁ - x₂ + 4x₃ ≤ 8;
2x₁ + 2x₂ - 5x₃ = 4;
x₁       + x₃ ≥ 6; x₁, x₃ ≥ 0, x₂ ≤ 0.
(d) max { x₁ + 2x₂ } subject to:
4x₁ - 2x₂ + 3x₃ ≤ 13;
5x₁ - 2x₂       ≥ 10;
x₁,x₂ ≥ 0.

2) Consider the system of equations Ax = B where
[ 2 3 1 0 0]             
A = [-1 1 0 2 1] and B = 
[ 0 6 1 0 3]             
Determine which of the following are basic solutions to the system.
(a) (1, 0,-1, 1, 0). (b) (0, 2,-5, 0, 1). (c) (0, 0, 1, 0, 1).

3) Suppose the canonical form of a linear program is given by the constraint matrix A and right-hand-side vector B:
[3 0 1 1 0]             
A = [2 1 0 0 0] and B = 
[4 0 3 0 1]             
Determine (and justify) which of the following solutions is
(i) a feasible solution to the linear programming problem.
(ii) an extreme point of the feasible region.
(iii) a basic solution.
(iv) a basic feasible solution.
For each basic feasible solution, list the basic variables.
(a) (0, 3, 0, 5, 6).
(b) (0, 3, 5, 0,-9).
(c) (3/2, 0, 0, 1/2, 0).
(d) (1/2, 1, 1, 0, 2).
(e) (1, 1, 1/2, 3/2, 1/2).

4) Consider the linear program
max { c'x + c"y }, subject to: x - y ≤ 2; 2x - y ≥ -4; x, y ≥ 0.
(a) Identify every extreme point of the feasible region.
(b) Identify every extreme direction of the feasible region.
(c) Characterize the set of values (c', c") for which there is a finite optimal solution.
(d) Characterize the set of values (c', c") for which there is an unbounded solution.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

1) Explanation: canonical form needs equations with non-negative variables and initial basis, so every inequality should be equalized, every arbitrary variable should be expressed as a difference of other 2 non-negative variables (x = x’ – x”). Eventually artificial basic variables should be introduced, if simplex-method with artificial basis(M-method) will be used.
(a) max {3x + 2y + 0u + 0v}
2x – y + u      = 6;
2x + y +       v = 10;...

By purchasing this solution you'll be able to access the following files:
Solution.docx.

\$10.50
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Operations Research Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.