# Modified Simplex Method of Goal Programming

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.

## Modified Simplex Method Example 1: Goal Programming

Minimize z = P1d1 + P2d4+ + 5P3d2 + 3P3d3 + P4d1+

subject to

x1 + x2 + d1 - d1+ = 80
x1 + d2 = 70
x2 + d3 = 45
d1+ + d4 - d4+ = 10

x1, x2, d1, d2, d3, d1+, d4, d4+ ≥ 0

Solution.

Substituting x1 = 0, x2 = 0, d1+ = 0 & d4+ = 0

Therefore, d1 = 80, d2 = 70, d3 = 45, d4 = 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 P1, P2, P3 and P4 are arranged in descending order.

Table 1

Use Horizontal Scrollbar to View Full Table Calculation

cj 0 0 P1 5P3 3P3 0 P4 P2
cB Basic variables
B
x1 x2 d1 d2 d3 d4 d1+ d4+ Solution values
b (=XB)
P1 d1 1 1 1 0 0 0 -1 0 80
5P3 d2 1 0 0 1 0 0 0 0 70
3P3 d3 0 1 0 0 1 0 0 0 45
0 d4 0 0 0 0 0 1 1 -1 10
zj-cj P4 0 0 0 0 0 0 -1 0 0
P3 5 3 0 0 0 0 0 0 485
P2 0 0 0 0 0 0 0 -1 0
P1 1 1 0 0 0 0 -1 0 80

Calculating values for the index row (zj – cj)

zj - cj = (Elements in cB Column) X (corresponding elements in xj columns) cj (Priority factors assigned to deviational variables)

Column x1
z1 - c1 = P1 X 1 + 5P3 X 1 + 3P3 X 0 + 0 X 0 0 = P1 + 5P3

Column x2
z2 - c2 = P1 X 1 + 5P3 X 0 + 3P3 X 1 + 0 X 0 0 = P1 + 3P3

Column d1
z3 - c3 = P1 X 1 + 5P3 X 0 + 3P3 X 0 + 0 X 0 P1 = 0

Column d2
z4 - c4 = P1 X 0 + 5P3 X 1 + 3P3 X 0 + 0 X 0 5P3 = 0

Column d3
z5 - c5 = P1 X 0 + 5P3 X 0 + 3P3 X 1 + 0 X 0 3P3 = 0

Column d4
z6 - c6 = P1 X 0 + 5P3 X 0 + 3P3 X 0 + 0 X 1 0 = 0

Column d1+
z7 - c7 = P1 X (-1) + 5P3 X 0 + 3P3 X 0 + 0 X 1 P4 = P1 P4

Column d4+
z8 - c8 = P1 X 0 + 5P3 X 0 + 3P3 X 0 + 0 X (-1) P2 = P2

Column XB
zB - cB = P1 X 80 + 5P3 X 70 + 3P3 X 45 + 0 X 10 = 80P1 + 485P3

Since, P1, P2, P3 and P4 are not commensurable, we list their coefficients separately in their rows in the simplex criterion (zj - cj) as shown in table 1.

Key column

The key column can be determined by selecting the largest positive element in zj - cj row at the highest priority goal level. In table 1, the largest positive element 1 in the P1 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 P3 row, therefore, column under x1 becomes the key column.

Key row

Minimum positive value = ( 80/1, 70/1) = 70
So d2 row is the key row.

Pivot element = 1
Therefore, d2 departs and x1 enters.

Table 2

cj 0 0 P1 5P3 3P3 0 P4 P2
cB Basic variables
B
x1 x2 d1 d2 d3 d4 d1+ d4+ Solution values
b (=XB)
P1 d1 0 1 1 -1 0 0 -1 0 10
0 x1 1 0 0 1 0 0 0 0 70
3P3 d3 0 1 0 0 1 0 0 0 45
0 d4 0 0 0 0 0 1 1 -1 10
zj-cj P4 0 0 0 0 0 0 -1 0 0
P3 0 3 0 -5 0 0 0 0 135
P2 0 0 0 0 0 0 0 -1 0
P1 0 1 0 -1 0 0 -1 0 10

Key column = x2 column
Minimum positive value = Min(10/1, 45/1) = 10
So d1 row is the key row.
d1 departs & x2 enters

Table 3

On small screens, scroll horizontally to view full calculation

cj 0 0 P1 5P3 3P3 0 P4 P2
cB Basic variables
B
x1 x2 d1 d2 d3 d4 d1+ d4+ Solution values
b (=XB)
0 x2 0 1 1 -1 0 0 -1 0 10
0 x1 1 0 0 1 0 0 0 0 70
3P3 d3 0 0 -1 1 1 0 1 0 35
0 d4 0 0 0 0 0 1 1 -1 10
zj-cj P4 0 0 0 0 0 0 -1 0 0
P3 0 0 -3 -2 0 0 3 0 105
P2 0 0 0 0 0 0 0 -1 0
P1 0 0 -1 0 0 0 0 0 10

Key column = d1+ column
Minimum positive value = Min(35/1, 10/1) = 10
d4 departs & d1+ enters

### Final Optimal Table: Modified Simplex Method

cj 0 0 P1 5P3 3P3 0 P4 P2
cB Basic variables
B
x1 x2 d1 d2 d3 d4 d1+ d4+ Solution values
b (=XB)
0 x2 0 1 1 -1 0 1 0 -1 20
0 x1 1 0 0 1 0 0 0 0 70
3P3 d3 0 0 -1 1 1 -1 0 1 25
P4 d1+ 0 0 0 0 0 1 1 -1 10
zj-cj P4 0 0 0 0 0 1 0 -1 10
P3 0 0 -3 -2 0 -3 0 3 75
P2 0 0 0 0 0 0 0 -1 0
P1 0 0 -1 0 0 0 0 0 0

In the above table, since all values in P1 and P2 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 P3 row. Since element 3 in P3 row is above the element 1 in the P2 row, therefore, the rule is that if there is a positive element at a lower priority level in zj-cj, 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 P4 row will not be considered.

The optimal solution is:

x1 = 70, x2 = 20, d1+ = 10, d3 = 25, d1 = 0, d2 = 0