## 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] [1]

A = [-1 1 0 2 1] and B = [1]

[ 0 6 1 0 3] [4]

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] [5]

A = [2 1 0 0 0] and B = [3]

[4 0 3 0 1] [6]

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

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse 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;...

This is only a preview of the solution. Please use the purchase button to see the entire solution