Simplex Method for Determining Feasibility and Optimal Solutions in Linear Programming

Get The Answer

Consider the following two LPs (one is feasible and the other is infeasible). For each LP, use the Phase I simplex method to find an initial basic feasible solution. If the LP is feasible, starting from this BFS, use the standard simplex method to find the optimal solution. Show your work for both phases (or just Phase I if the problem is infeasible).

LP 1:

Minimize
4x1+x24x_1 + x_24x1​+x2​

Subject to:
3x1+x2=33x_1 + x_2 = 33x1​+x2​=3
4x1+3x2≥64x_1 + 3x_2 \geq 64x1​+3x2​≥6
x1+2x2≤4x_1 + 2x_2 \leq 4x1​+2x2​≤4
x1,x2≥0x_1, x_2 \geq 0x1​,x2​≥0

LP 2:

Maximize
2x1+3x22x_1 + 3x_22x1​+3x2​

Subject to:
x1+2x2≤2x_1 + 2x_2 \leq 2x1​+2x2​≤2
2x1+x2≥62x_1 + x_2 \geq 62x1​+x2​≥6
x1,x2≥0x_1, x_2 \geq 0x1​,x2​≥0

2. The Matrix Perspective

Problem 2: Tableau Canonicalization and Traversal

Given standard form LP:

Maximize cTxc^T xcTx
Subject to Ax=bAx = bAx=b, x≥0x \geq 0x≥0

(a) Derive matrix operations to obtain the canonical tableau (RREF).

• Write transformation matrix

• Provide formulas for:

  • updated RHS bˉ\bar{b}bˉ

  • updated non-basic columns Nˉ\bar{N}Nˉ

  • reduced costs cˉNT\bar{c}_N^TcˉNT​

(b) If reduced cost cˉj<0\bar{c}_j < 0cˉj​<0:

• Provide formulas for:

  • current corner point xBx_BxB​

  • edge direction ddd

Problem 3: Optimality and Unboundedness via Matrix Verification

(a) State necessary and sufficient conditions for optimality of basis BBB

(b) LP:

Maximize 3x1+2x23x_1 + 2x_23x1​+2x2​

Subject to:
2x1+x2≤102x_1 + x_2 \leq 102x1​+x2​≤10
x1+2x2≤8x_1 + 2x_2 \leq 8x1​+2x2​≤8
x1,x2≥0x_1, x_2 \geq 0x1​,x2​≥0

• Convert to standard form

• Basis: (x1,x2)(x_1, x_2)(x1​,x2​)

• Given:

B−1=13[2−1−12]B^{-1} = \frac{1}{3} \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}B−1=31​[2−1​−12​]

• Compute final tableau

• Verify primal & dual feasibility → optimality

(c) LP:

Maximize 2x1+x22x_1 + x_22x1​+x2​

Subject to:
x1−x2≤4x_1 - x_2 \leq 4x1​−x2​≤4
−x1+x2≤2-x_1 + x_2 \leq 2−x1​+x2​≤2
x1,x2≥0x_1, x_2 \geq 0x1​,x2​≥0

• Convert to standard form

• Basis: (x1,s2)(x_1, s_2)(x1​,s2​)

• Given:

B−1=[1011]B^{-1} = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}B−1=[11​01​]

• Compute tableau

• Verify LP is unbounded

3. The Dual Problem

Problem 4: The Dual Formulation

Write dual LPs for:

(a)

Maximize 2x1+3x2+4x3−x42x_1 + 3x_2 + 4x_3 - x_42x1​+3x2​+4x3​−x4​

Subject to:
−x1+2x2+3x3+2x4≤10-x_1 + 2x_2 + 3x_3 + 2x_4 \leq 10−x1​+2x2​+3x3​+2x4​≤10
3x1+x2−5x3≤203x_1 + x_2 - 5x_3 \leq 203x1​+x2​−5x3​≤20
−2x1−x2−2x4≥−12-2x_1 - x_2 - 2x_4 \geq -12−2x1​−x2​−2x4​≥−12
x1,x2,x3,x4≥0x_1, x_2, x_3, x_4 \geq 0x1​,x2​,x3​,x4​≥0

(b)

Maximize 2x1+4x2+5x32x_1 + 4x_2 + 5x_32x1​+4x2​+5x3​

Subject to:
3x1−5x2≤43x_1 - 5x_2 \leq 43x1​−5x2​≤4
x3+x4≤5x_3 + x_4 \leq 5x3​+x4​≤5
x4−x2≥3x_4 - x_2 \geq 3x4​−x2​≥3
x3≤2x_3 \leq 2x3​≤2
x4≥5x_4 \geq 5x4​≥5
x1,x2≤0x_1, x_2 \leq 0x1​,x2​≤0

Problem 5: Primal-Dual Relationship

For each:

• Formulate dual

• Determine feasibility/unboundedness of primal & dual

(a)

Minimize xxx

Subject to:
x≥1x \geq 1x≥1
x≤−1x \leq -1x≤−1
xxx free

(b)

Minimize x1−x2x_1 - x_2x1​−x2​

Subject to:
x1≥1x_1 \geq 1x1​≥1
x2≥1x_2 \geq 1x2​≥1
x1+x2≤1x_1 + x_2 \leq 1x1​+x2​≤1

Problem 6: Dual of an Inventory Model

Given multi-period inventory LP:

Minimize
∑cixi+∑hiIi\sum c_i x_i + \sum h_i I_i∑ci​xi​+∑hi​Ii​

Subject to:
Ii−1+xi−Ii=diI_{i-1} + x_i - I_i = d_iIi−1​+xi​−Ii​=di​
xi,Ii≥0x_i, I_i \geq 0xi​,Ii​≥0

(a) Write dual problem
(b) Provide economic interpretation

Problem 7: Dual Simplex Method

(a)

• Write dual of standard LP

• Define dual corner point

• Describe dual edges

(b) Given tableau:

Basisx1x2x3s1s2RHSz345000s1-1-2-310-5s2-2-1-101-6

• Perform dual simplex method

• Show:

  • dual corner point

  • direction

  • step length

(c) New constraint added:

x1+x2≤1.5x_1 + x_2 \leq 1.5x1​+x2​≤1.5

• Update tableau

• Apply dual simplex

• Find new optimum

4. Sensitivity Analysis

Problem 8: Sensitivity Analysis

Maximize x1+2x2x_1 + 2x_2x1​+2x2​

Subject to:
x1≤4x_1 \leq 4x1​≤4
x2≤6x_2 \leq 6x2​≤6
x1+x2≤8x_1 + x_2 \leq 8x1​+x2​≤8
x1,x2≥0x_1, x_2 \geq 0x1​,x2​≥0

(a) Plot feasible region
(b) Sensitivity analysis (coefficients & RHS)
(c) Explain shadow price

Problem 9: Sensitivity Analysis

(a) RHS perturbation → derive parametric solution
(b) Objective coefficient perturbation
(c) Solve LP using your solver
(d) Compute:

• shadow prices

• optimality ranges

5. Coding Problem

Problem 10: MATLAB Simplex Solver

Implement:

1. Constructor

2. Solver (Phase I & II)

3. Result display

Include:

• optimal solution

• tableau

• shadow prices

• reduced costs

• execution performance

Bonus

Problem 11 (Bonus)

• Implement Revised Simplex Method

• Compare with standard simplex:

Include:

• test cases

• performance analysis

• explanation of results