The Big M Method – In Linear Programming

iamnasirene

4 years ago

Lecture 6

You receive your objective function, and your list of constraints, some of which are inequalities and some equalities i.e. greater than and less than and equal to.

$$\text{Minimise/Maximise } z = ax_1+bx_2+cx_3$$ $$ x_i \ge 0, i = 1,2,3…$$

Remember to:

Linear programme must be in standard form i.e.
- Maximise not minimise (signs)
- Equality constraints (unique slack variables)
- RHS >=0 (signs)

Issue Arises When…:

When there is no initial basic feasible solution (bfs) present you have to consider that you cannot just go ahead with the Simplex procedure, hence the Big M Method.

Introducing Artificial Variables

For those equations with no BFS Variable
- add in new artificial variables
In the objective function
- remove the artificial variables multiplied by the Big M
This allows an initial BFS solution i.e. a canonical system to start the simplex procedure…

$$ ax_1 +bx_2+cx_3 – Mx_6 – Mx_7$$ $$+x_4 \text{ Inequality slack correcting variables }$$ $$-x_5 \text{ Inequality slack correcting variables }$$ $$+x_6 \text{ BFS Big M Variables positive here }$$ $$+x_7 \text{ BFS Big M Variable positive here}$$ $$x_i\ge0 \text{ for } i=1,2,3,4,5,6,7$$

I give you a readily available BFS!!

Utilise the Simplex Method Now

Go ahead, it’s an iterative process so keep it neat – draw up the tables, keep track of your signs…

Basically,

Objective function coefficient less Basis co-efficient matrix multiplied by variant coefficient matrix, added altogether for final answer.

Choose largest resulting Deviation row.

Minimum RHS / Matrix of variable with largest deviation row.

Keep at it until ALL the answers result in zeros or negatives to insert into Objective Function. The objective function does not take negatives, so the answer will be the variables which look like :

$$\matrix{1,0,0- 0,1,0- 0,0,1}$$

Easy peasy.

Be Aware: Pivot Table

You cannot take negatives or zero into consideration in the pivot table, when finding the minimum ratio on the RHS.