Linear Programming - Fundamental Concepts: Canonical Forms, Feasible Regions, Basic Solutions...

  1. Home
  2. Homework Library
  3. Mathematics
  4. Operations Research
  5. Linear Programming - Fundamental Concepts: Canonical Forms, Feasible Regions, Basic Solutions...

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

$15.00

or $1 if you
register a new account!

Related Homework Solutions

Get help from a qualified tutor
Live Chats