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

Related Homework Solutions

Operations Research Problem Using Simplex
Homework Solution
$8.00
Mathematics
Simplex Method
Algebra
Operations Research
Microsoft Excel
Equations
Functions
Variables
Statements
Conditions
Graphs
Mathematics Questions
Homework Solution
$20.00
Mathematics
Operations
Research
Company
Restriction
Product
Machinery
Profit
Forecast
Operations Research Questions
Homework Solution
$60.00
Operations Research
Mathematics
Transportation Problem
Tables
Corner Rules
Simplex
Vogel's Approximation
Minimum Cost Technique
Interior Point Algorithm
Products
Constraints
Distances
Shortest Path
Graphs
Spanning Trees
Networks
Farm Management Case Study
Homework Solution
$45.00
Operations Research
Family History
Farms
Purchases
Business
Finance
Expenses
Models
Predictions
Optimal Values
Linear Programming Model
Estimates
Solutions
Operations Research Problem
Homework Solution
$8.00
Mathematics
Operations Research
Microsoft Excel
Equations
Functions
Variables
Statements
Conditions
Graphs
Integer Programming Question
Homework Solution
$8.00
Integer Programming
Mathematics
Computer Science
Operations Research
Products
Units
Operations
Costs
Profit
Dependent Variables
Functions
Statements
Get help from a qualified tutor
Live Chats