Scribd
Upload
6 views2 pages

Big-M Method for Linear Programming

The document outlines the application of the penalty (Big-M) method to solve a linear programming (LP) problem, detailing the introduction of slack, surplus, and artificial variables to convert the problem into standard form. It provides a step-by-step iterative process to find an optimal solution, including calculations of basic feasible solutions and adjustments to the basis through row operations. The final result indicates that an optimal solution has been reached with all cj - zj values being non-negative.

Uploaded by

Melengfe Oliver
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views2 pages

Big-M Method for Linear Programming

The document outlines the application of the penalty (Big-M) method to solve a linear programming (LP) problem, detailing the introduction of slack, surplus, and artificial variables to convert the problem into standard form. It provides a step-by-step iterative process to find an optimal solution, including calculations of basic feasible solutions and adjustments to the basis through row operations. The final result indicates that an optimal solution has been reached with all cj - zj values being non-negative.

Uploaded by

Melengfe Oliver
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Example 1

Use penalty (Big-M) method to solve the following LP problem.

subject to the constraints

Solution
Adding slack variable, s1; surplus variable, s2 and artificial variables, A1 and A2 in the constraints of the given LP
problem, the standard form of the LP problem becomes.

subject to the constraints

An initial basic feasible solution: s1 = 12, A1 = 10, A2 = 10 and Min Z = 10M + 10M = 20M is obtained by
putting x1 = x2 = s2 = 0. It may be noted that the columns that correspond to the current basic variables and form
the basis (identity matrix) are s1 (slack variable), A1 and A2 (both artificial variables). The initial basic feasible
solution is given in the table below.
Initial table
Cj 5 3 0 0 M M Min Ratio
Cb Base
0 12 2 4 1 0 0 0 12/2 = 6
M 10 2 2 0 0 1 0 10/2 = 5
M 10 5 2 0 –1 0 1 10/5 = 2 →
Zj 20M 7M 4M 0 –M M M
Cj – Zj 5 – 7M 3 – 4M 0 M 0 0
↑
Since the value c1 – z1= 5 – 7M is the smallest value, therefore variable x1 is chosen to enter into the basis
(solution mix). To decide a current basic variable to leave the basis, calculate minimum ratio as shown above.

In the 1st Iteration, Introduce variable x1 into the basis and remove A2 from the basis by applying the following
row operations.

The improved basic feasible solution is shown below.

Cj 5 3 0 0 M Min Ratio
Cb Base
0 8 0 16/5 1 2/5 0 8/(16/5) = 5/2 →

\M 6 0 6/5 0 2/5 1 6/(6/5) = 5


5 2 1 2/5 0 – 1/5 0 2/(2/5) = 5
Zj 10 + 5 (6M/5) + 2 0 (2M/5) – 1 M
6M
Cj – Zj 0
(– 6M/5) + 0 (– 2M/5) + 1 0
1
↑
nd
In the 2 Iteration, Since the value of c2 – z2 above is the largest negative value, variable x2 is chosen to replace
basic variable s1 in the basis. Thus, to get an improved basic feasible solution, apply, the following row
operations:

1
The new solution is shown below

Cj 5 3 0 0 M Min
Cb Base Ratio
3 5/2 0 1 5/16 1/8 0 40
M 3 0 0 -3/8 1/4 1 12
5 1 1 0 -1/8 – 1/4 0
Zj 25/2 + 3M 5 3 – 3M/ 8 + 5/16M/4 – 7/8 M
Cj – Zj 0 0 03M/8 – 5/16 -M/4+7/8 0
↑
In the 3rd Iteration, Since c4 – z4 < 0 (negative) in s2-column, the current solution is not optimal. Thus, non-basic
variable s2 is chosen to replace artificial variable A1 in the basis. To get an improved basic feasible solution,
apply the following row operations:
R2 (new) → R2 (old) × 4 (key element);
R1 (new) → R1 (old) – (1/8) R2 (new)
R3 (new) → R3 (old) + (1/4) R2 (new).
The improved basic feasible solution is shown below
Cj 5 3 0 0
Cb Base
3 1 0 1 1/2 0
0 12 0 0 – 3/2 1
5 4 1 0 – 1/2 0
Zj 23 5 5 –1 0
Cj – Zj 0 0 1 0
In the table above, all cj – zj ≥ 0. Thus, an optimal solution is arrived at with the value of variables as:
.

Example 2
Use penalty (Big-M) method to solve the following LP problem

subject to the constraints

You might also like