List of Practical Experiments (Official Syllabus)

1. Solution of LPP by Graphical Method.
2. Solution of LPP by Simplex method.
3. Problem solving using Big-M method.
4. Problem solving using Two-Phase method.
5. Special cases in LPP (unbounded, alternative).
6. Problems based on Principle of Duality.
7. Problems based on Dual Simplex method.

Experiment 1 — Graphical Method

1. Problem

Maximise \(Z = 5x_1 + 4x_2\) subject to \(6x_1 + 4x_2 \le 24,\; x_1 + 2x_2 \le 6,\; -x_1 + x_2 \le 1,\; x_2 \le 2,\; x_1, x_2 \ge 0\).

2. Aim

To solve a two-variable LPP graphically by plotting the constraints and evaluating the objective at each vertex of the feasible region.

3. Formula

Applying it:

1. Plot each constraint line and shade the feasible polygon.
2. Identify the corner points (vertices).
3. Evaluate \(Z\) at each vertex; the largest value gives the optimum.

4. Calculation

Blank working table:

Vertex \((x_1, x_2)\)	\(Z = 5x_1 + 4x_2\)
(0, 0)
(4, 0)
(3, 1.5)
(2, 2)
(1, 2)
(0, 1)

The binding pair \(6x_1 + 4x_2 = 24\) and \(x_1 + 2x_2 = 6\) intersect at \((3, 1.5)\).

Vertex \((x_1, x_2)\)	\(Z = 5x_1 + 4x_2\)
(0, 0)	0
(4, 0)	20
(3, 1.5)	21 (max)
(2, 2)	18
(1, 2)	13
(0, 1)	4

5. Result

The optimum is \(x_1 = 3,\; x_2 = 1.5,\; Z_{\max} = 21\).

Experiment 2 — Simplex Method

1. Problem

Maximise \(Z = 3x_1 + 2x_2\) subject to \(x_1 + x_2 \le 4,\; x_1 + 3x_2 \le 6,\; x_1, x_2 \ge 0\).

2. Aim

To solve the LPP by the simplex method and verify the result graphically.

3. Formula

Applying it:

1. Add slacks \(s_1, s_2\); the initial BFS is \((x_1, x_2, s_1, s_2) = (0, 0, 4, 6)\).
2. Choose the entering variable (largest \(c_j - z_j\)) and the leaving variable (min ratio).
3. Pivot; repeat until all \(c_j - z_j \le 0\).

4. Calculation

Blank working table (iteration summary):

Iteration	Basis	\((x_1, x_2)\)	\(Z\)
Initial	\(s_1, s_2\)
1

Iteration	Basis	\((x_1, x_2)\)	\(Z\)
Initial	\(s_1, s_2\)	(0, 0)	0
1 (x₁ in, s₁ out)	\(x_1, s_2\)	(4, 0)	12

After one pivot all \(c_j - z_j \le 0\), so the optimum is reached.

Graphical check: vertices (0,0), (4,0), (3,1), (0,2) give \(Z = 0, 12, 11, 4\); max = 12 ✓.

5. Result

The optimum is \(x_1 = 4,\; x_2 = 0,\; Z_{\max} = 12\).

Experiment 3 — Big-M Method

1. Problem

Minimise \(Z = 7x_1 + 9x_2\) subject to \(3x_1 + 6x_2 \ge 18,\; 8x_1 + 4x_2 \ge 16,\; x_1, x_2 \ge 0\).

2. Aim

To solve a minimisation LPP with \(\ge\) constraints using surplus and artificial variables and the Big-M penalty.

3. Formula

Applying it:

1. Subtract surplus \(s_1, s_2\) and add artificials \(A_1, A_2\); penalise them with \(+M\).
2. Start with the artificials in the basis; apply the simplex rules for minimisation.
3. Drive both artificials out of the basis; the resulting BFS is optimal.

4. Calculation

Blank working table (corner-point evaluation):

Corner \((x_1, x_2)\)	Binding constraints	\(Z = 7x_1 + 9x_2\)
(6, 0)
(2/3, 8/3)
(0, 4)

At the optimum both constraints bind: \(3x_1 + 6x_2 = 18\) (i.e. \(x_1 + 2x_2 = 6\)) and \(8x_1 + 4x_2 = 16\) (i.e. \(2x_1 + x_2 = 4\)). Solving gives \(x_1 = 2/3,\; x_2 = 8/3\).

Corner \((x_1, x_2)\)	Binding constraints	\(Z = 7x_1 + 9x_2\)
(6, 0)	first only	42
(2/3, 8/3)	both	86/3 ≈ 28.67 (min)
(0, 4)	second only	36

\(Z = 7(2/3) + 9(8/3) = 14/3 + 72/3 = 86/3 \approx 28.67\).

5. Result

The optimum is \(x_1 = 2/3 \approx 0.667,\; x_2 = 8/3 \approx 2.667,\; Z_{\min} = 86/3 \approx 28.67\).

Experiment 4 — Two-Phase Method

1. Problem

Solve the LPP of Experiment 3 (Min \(Z = 7x_1 + 9x_2\) s.t. \(3x_1 + 6x_2 \ge 18,\; 8x_1 + 4x_2 \ge 16,\; x_1, x_2 \ge 0\)) by the Two-Phase method.

2. Aim

To solve the same problem in two phases (minimise the artificial sum, then optimise the original objective) and confirm it matches Big-M.

3. Formula

Applying it:

1. Phase 1: minimise \(W = A_1 + A_2\) subject to the constraints (surplus + artificial). Drive \(W\) to 0.
2. Phase 2: drop the artificials and optimise the original \(Z = 7x_1 + 9x_2\) from the Phase-1 BFS.
3. Check optimality: for a minimisation, \(c_j - z_j \ge 0\) for all non-basic variables.

4. Calculation

Blank working table:

Phase	Objective value	\((x_1, x_2)\)
End of Phase 1	\(W =\)
End of Phase 2	\(Z =\)

Phase	Objective value	\((x_1, x_2)\)
End of Phase 1	\(W = 0\)	(2/3, 8/3)
End of Phase 2	\(Z = 86/3 \approx 28.67\)	(2/3, 8/3)

Phase 1 ends with \(W = 0\) and a feasible BFS at \((2/3, 8/3)\); Phase 2 confirms optimality with \(c_j - z_j \ge 0\).

5. Result

\(x_1 = 2/3,\; x_2 = 8/3,\; Z_{\min} = 86/3 \approx 28.67\) — identical to the Big-M result, as expected.

Experiment 5 — Special Cases

1. Problem

(a) Show that Max \(Z = 3x_1 + 5x_2\) s.t. \(x_1 + x_2 \ge 2,\; x_1 - x_2 \le 1,\; x_1, x_2 \ge 0\) is unbounded. (b) Show that Max \(Z = 2x_1 + 4x_2\) s.t. \(x_1 + 2x_2 \le 5,\; x_1 + x_2 \le 4,\; x_1, x_2 \ge 0\) has alternative optima.

2. Aim

To recognise and interpret the special cases of an unbounded solution and of multiple (alternative) optima.

3. Formula

Applying it:

1. Unbounded: if at some iteration the entering column has all entries \(\le 0\), no leaving variable exists and \(Z \to \infty\).
2. Alternative optima: if at the optimum a non-basic variable has \(c_j - z_j = 0\), a second optimal vertex (and the whole edge joining it) is optimal.

4. Calculation

Blank working table (alternative-optima vertices):

Optimal vertex	\(Z = 2x_1 + 4x_2\)
(0, 2.5)
(3, 1)

(a) Taking \(x_1 = 0\), the constraints allow \(x_2 \to \infty\), so \(Z = 5x_2 \to \infty\): the problem is unbounded.

(b) Since \(2x_1 + 4x_2 = 2(x_1 + 2x_2) \le 10\), any point on \(x_1 + 2x_2 = 5\) inside the region attains \(Z = 10\):

Optimal vertex	\(Z = 2x_1 + 4x_2\)
(0, 2.5)	10
(3, 1)	10

5. Result

(a) The first LPP is unbounded (\(Z \to \infty\)). (b) The second has alternative optima: \((0, 2.5)\) and \((3, 1)\) both give \(Z = 10\), and every convex combination of them is also optimal.

Experiment 6 — Principle of Duality

1. Problem

For the primal Max \(Z = 4x_1 + 5x_2\) s.t. \(2x_1 + x_2 \le 8,\; x_1 + 2x_2 \le 10,\; x_1, x_2 \ge 0\), write the dual, solve the primal, and verify strong duality and complementary slackness.

2. Aim

To form the dual, obtain the shadow prices from the primal, and confirm \(Z^* = W^*\) and the complementary-slackness conditions.

3. Formula

Applying it:

1. Write the dual (one dual variable per primal constraint).
2. Solve the primal by simplex; read the shadow prices from the slack columns of the final tableau.
3. Check \(Z^* = W^*\) and complementary slackness.

4. Calculation

Blank working table:

Quantity	Value
Primal optimum \((x_1, x_2)\)
\(Z^*\)
Dual optimum \((y_1, y_2)\)
\(W^*\)

Both primal constraints bind at the optimum: \(2x_1 + x_2 = 8,\; x_1 + 2x_2 = 10 \Rightarrow x_1 = 2,\; x_2 = 4\), so \(Z^* = 4(2) + 5(4) = 28\). The dual constraints (both binding) give \(2y_1 + y_2 = 4,\; y_1 + 2y_2 = 5 \Rightarrow y_1 = 1,\; y_2 = 2\).

Quantity	Value
Primal optimum \((x_1, x_2)\)	(2, 4)
\(Z^*\)	28
Dual optimum \((y_1, y_2)\)	(1, 2)
\(W^*\)	8(1) + 10(2) = 28

Complementary slackness: both primal constraints are binding ⇒ \(y_1, y_2 > 0\); both primal variables are positive ⇒ both dual constraints bind (\(2(1)+2 = 4\) ✓, \(1 + 2(2) = 5\) ✓).

5. Result

\(Z^* = W^* = 28\) (strong duality holds), with shadow prices \(y_1 = 1,\; y_2 = 2\), and all complementary-slackness conditions are satisfied.

Experiment 7 — Dual Simplex Method

1. Problem

Minimise \(Z = 2x_1 + x_2\) subject to \(3x_1 + x_2 \ge 3,\; 4x_1 + 3x_2 \ge 6,\; x_1 + 2x_2 \le 3,\; x_1, x_2 \ge 0\).

2. Aim

To solve the LPP by the dual simplex method, starting from a dual-feasible but primal-infeasible tableau.

3. Formula

Applying it:

1. Convert \(\ge\) constraints to \(\le\) by multiplying by \(-1\), and Min to Max by negating \(Z\).
2. Add slacks; the starting tableau has \(c_j - z_j \le 0\) (dual feasible) but some \(b_i < 0\).
3. Leaving variable: most negative \(b_i\); entering variable: min ratio \(|(c_j - z_j)/a_{ij}|\) over negative \(a_{ij}\). Pivot and repeat until all \(b_i \ge 0\).

4. Calculation

Blank working table (initial tableau):

\(c_B\)	Basis	\(x_B\)	x₁ (−2)	x₂ (−1)	s₁	s₂	s₃
0	s₁		−3	−1	1	0	0
0	s₂		−4	−3	0	1	0
0	s₃		1	2	0	0	1
\(c_j - z_j\)

\(c_B\)	Basis	\(x_B\)	x₁ (−2)	x₂ (−1)	s₁	s₂	s₃
0	s₁	−3	−3	−1	1	0	0
0	s₂	−6	−4	−3	0	1	0
0	s₃	3	1	2	0	0	1
\(c_j - z_j\)			−2	−1	0	0	0

The tableau is dual feasible (all \(c_j - z_j \le 0\)) but primal infeasible (\(b < 0\)). Leaving: the most negative \(b = -6\) (row s₂). Ratios over its negative entries: x₁ \(= |{-2}/{-4}| = 0.5\), x₂ \(= |{-1}/{-3}| = 0.33\); the smaller is x₂, so x₂ enters (pivot \(-3\)). Continuing the iterations drives all \(b_i \ge 0\), giving \(x_1 = 3/5,\; x_2 = 6/5\).

5. Result

The optimum is \(x_1 = 3/5 = 0.6,\; x_2 = 6/5 = 1.2,\; Z_{\min} = 2(0.6) + 1.2 = 12/5 = 2.4\).

Lab Record Format (to be followed for every experiment)

1. 1. Problem — the LPP and the method to be used.
2. 2. Aim — what the experiment demonstrates.
3. 3. Formula — the standard or canonical form, then the numbered steps that apply it.
4. 4. Calculation — the filled tableau / vertex evaluation with the arithmetic.
5. 5. Result — the optimal solution and its interpretation (with verification where relevant).