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

Subject Mathematics Operations Research

## 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

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 \$8.00
Mathematics
Simplex Method
Algebra
Operations Research
Microsoft Excel
Equations
Functions
Variables
Statements
Conditions
Graphs
Mathematics Questions \$20.00
Mathematics
Operations
Research
Company
Restriction
Product
Machinery
Profit
Forecast
Operations Research Questions \$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 \$45.00
Operations Research
Family History
Farms
Purchases
Finance
Expenses
Models
Predictions
Optimal Values
Linear Programming Model
Estimates
Solutions
Operations Research Problem \$8.00
Mathematics
Operations Research
Microsoft Excel
Equations
Functions
Variables
Statements
Conditions
Graphs
Integer Programming Question \$8.00
Integer Programming
Mathematics
Computer Science
Operations Research
Products
Units
Operations
Costs
Profit
Dependent Variables
Functions
Statements
Live Chats