We think that the best way to explain the **simplex method** of **goal programming** is through an example.

Here, we proceed directly to the consideration of a numerical example.

Minimize z = P_{1}d_{1}^{−} + P_{2}d_{4}^{+} + 5P_{3}d_{2}^{−} + 3P_{3}d_{3}^{−} + P_{4}d_{1}^{+}

subject to

x_{1} + x_{2} + d_{1}^{−} - d_{1}^{+} = 80

x_{1} + d_{2}^{−} = 70

x_{2} + d_{3}^{−} = 45

d_{1}^{+} + d_{4}^{−} - d_{4}^{+} = 10

x_{1}, x_{2}, d_{1}^{−},
d_{2}^{−}, d_{3}^{−},
d_{1}^{+}, d_{4}^{−},
d_{4}^{+} ≥ 0

Solution.

Substituting x_{1} = 0, x_{2} = 0, d_{1}^{+} = 0 & d_{4}^{+} = 0

Therefore, d_{1}^{− } = 80, d_{2}^{− } = 70,
d_{3}^{− } = 45, d_{4}^{−} = 10

The first four rows of table 1 are set up in the same way as
for the Simplex Method. The next four rows stand for priority goal levels.
The goal levels P_{1}, P_{2}, P_{3} and P_{4} are arranged in descending order.

Table 1

c_{j} |
0 | 0 | P_{1} |
5P_{3} |
3P_{3} |
0 | P_{4} |
P_{2} |
||
---|---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
d_{1}^{−} |
d_{2}^{−} |
d_{3}^{−} |
d_{4}^{−} |
d_{1}^{+} |
d_{4}^{+} |
Solution values b (=X _{B}) |

P_{1} |
d_{1}^{−} |
1 | 1 | 1 | 0 | 0 | 0 | -1 | 0 | 80 |

5P_{3} |
d_{2}^{−} |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 70 |

3P_{3} |
d_{3}^{−} |
0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 45 |

0 | d_{4}^{−} |
0 | 0 | 0 | 0 | 0 | 1 | 1 | -1 | 10 |

z_{j}-c_{j} |
P_{4} |
0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 |

P_{3} |
5 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 485 | |

P_{2} |
0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | |

P_{1} |
1 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 80 |

Calculating
values for the index row (z_{j }– c_{j})

z_{j} - c_{j} = (Elements in cB Column) X (corresponding
elements in x_{j} columns) c_{j} (Priority factors
assigned to deviational variables)

Column x_{1
}z_{1} - c_{1} = P_{1 }X 1 + 5P_{3 }X
1 + 3P_{3 }X 0 + 0_{ }X 0 0 = P_{1} + 5P_{3}

Column x_{2
}z_{2 }- c_{2} = P_{1 }X 1 + 5P_{3 }X
0 + 3P_{3 }X 1 + 0 X 0 0 = P_{1} + 3P_{3}

Column d_{1}^{−
}z_{3} - c_{3} = P_{1 }X 1 + 5P_{3 }X
0 + 3P_{3} X 0 + 0 X 0 P_{1} = 0

Column d_{2}^{−
}z_{4} - c_{4} = P_{1} X 0 + 5P_{3} X 1 + 3P_{3} X 0 + 0 X 0 5P_{3} = 0

Column d_{3}^{−
}z_{5 }- c_{5} = P_{1} X 0 + 5P_{3} X 0 + 3P_{3} X 1 + 0 X 0 3P_{3} = 0

Column d_{4}^{−
}z_{6} - c_{6} = P_{1} X 0 + 5P_{3} X 0 + 3P_{3} X 0 + 0 X 1 0 = 0

Column d_{1}^{+
}z_{7} - c_{7} = P_{1} X (-1) + 5P_{3} X 0 + 3P_{3} X 0 + 0 X 1 P_{4} = P_{1} P_{4}

Column d_{4}^{+
}z_{8} - c_{8} = P_{1} X 0 + 5P_{3} X 0 + 3P_{3} X 0 + 0 X (-1) P_{2} = P_{2}

Column X_{B
}z_{B} - c_{B} = P_{1} X 80 + 5P_{3} X 70 + 3P_{3} X 45 + 0 X 10 = 80P_{1} + 485P_{3}

Since, P_{1}, P_{2}, P_{3} and P_{4} are not commensurable, we list their coefficients separately in their
rows in the simplex criterion (z_{j} - c_{j}) as shown
in table 1.

Key column

The key column can be determined by selecting the largest positive
element in z_{j} - c_{j} row at the highest priority
goal level. In table 1, the largest positive element 1 in the P_{1} row occurs at two places. In order to break this tie, check the next
lower priority goal levels. Since the largest positive element is 5
in P_{3} row, therefore, column under x_{1} becomes
the key column.

Key row

Minimum positive value = ( 80/1, 70/1) = 70

So d_{2}^{−} row is the
key row.

Pivot element = 1

Therefore, d_{2}^{−} departs and x_{1} enters.

Table 2

c_{j} |
0 | 0 | P_{1} |
5P_{3} |
3P_{3} |
0 | P_{4} |
P_{2} |
||
---|---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
d_{1}^{−} |
d_{2}^{−} |
d_{3}^{−} |
d_{4}^{−} |
d_{1}^{+} |
d_{4}^{+} |
Solution values b (=X _{B}) |

P_{1} |
d_{1}^{−} |
0 | 1 | 1 | -1 | 0 | 0 | -1 | 0 | 10 |

0 | x_{1} |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 70 |

3P_{3} |
d_{3}^{−} |
0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 45 |

0 | d_{4}^{−} |
0 | 0 | 0 | 0 | 0 | 1 | 1 | -1 | 10 |

z_{j}-c_{j} |
P_{4} |
0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 |

P_{3} |
0 | 3 | 0 | -5 | 0 | 0 | 0 | 0 | 135 | |

P_{2} |
0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | |

P_{1} |
0 | 1 | 0 | -1 | 0 | 0 | -1 | 0 | 10 |

Key column = x_{2} column

Minimum positive value = Min(10/1, 45/1) = 10

So d_{1}^{−} row is the
key row.

d_{1}^{−} departs &
x_{2} enters

Table 3

c_{j} |
0 | 0 | P_{1} |
5P_{3} |
3P_{3} |
0 | P_{4} |
P_{2} |
||
---|---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
d_{1}^{−} |
d_{2}^{−} |
d_{3}^{−} |
d_{4}^{−} |
d_{1}^{+} |
d_{4}^{+} |
Solution values b (=X _{B}) |

0 | x_{2} |
0 | 1 | 1 | -1 | 0 | 0 | -1 | 0 | 10 |

0 | x_{1} |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 70 |

3P_{3} |
d_{3}^{−} |
0 | 0 | -1 | 1 | 1 | 0 | 1 | 0 | 35 |

0 | d_{4}^{−} |
0 | 0 | 0 | 0 | 0 | 1 | 1 | -1 | 10 |

z_{j}-c_{j} |
P_{4} |
0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 |

P_{3} |
0 | 0 | -3 | -2 | 0 | 0 | 3 | 0 | 105 | |

P_{2} |
0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | |

P_{1} |
0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | 10 |

Key column = d_{1}+ column

Minimum positive value = Min(35/1, 10/1) = 10

d_{4}^{−} departs &
d_{1}+ enters

c_{j} |
0 | 0 | P_{1} |
5P_{3} |
3P_{3} |
0 | P_{4} |
P_{2} |
||
---|---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
d_{1}^{−} |
d_{2}^{−} |
d_{3}^{−} |
d_{4}^{−} |
d_{1}^{+} |
d_{4}^{+} |
Solution values b (=X _{B}) |

0 | x_{2} |
0 | 1 | 1 | -1 | 0 | 1 | 0 | -1 | 20 |

0 | x_{1} |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 70 |

3P_{3} |
d_{3}^{−} |
0 | 0 | -1 | 1 | 1 | -1 | 0 | 1 | 25 |

P_{4} |
d_{1}^{+} |
0 | 0 | 0 | 0 | 0 | 1 | 1 | -1 | 10 |

z_{j}-c_{j} |
P_{4} |
0 | 0 | 0 | 0 | 0 | 1 | 0 | -1 | 10 |

P_{3} |
0 | 0 | -3 | -2 | 0 | -3 | 0 | 3 | 75 | |

P_{2} |
0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | |

P_{1} |
0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |

In the above table, since all values in P_{1} and P_{2} row are either zero or negative, the first goal and the second goal
are completely achieved. The third goal is not completely attained,
because there is a positive value, i.e., 3 in the P_{3} row.
Since element 3 in P_{3} row is above the element 1 in the
P_{2} row, therefore, the rule is that if there is a positive
element at a lower priority level in z_{j}-c_{j}, the
variable in that column cannot be introduced into the solution, as long
as there is a negative element at a higher priority level. Likewise,
the positive element 1 in the P_{4} row will not be considered.

The **optimal solution** is:

x_{1} = 70, x_{2} = 20, d_{1}^{+} =
10, d_{3}^{− } = 25,
d_{1}^{− } = 0, d_{2}^{− } = 0