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 = P₁d₁⁻ + P₂d₄⁺ + 5P₃d₂⁻ + 3P₃d₃⁻ + P₄d₁⁺

subject to

x₁ + x₂ + d₁⁻ - d₁⁺ = 80
x₁ + d₂⁻ = 70
x₂ + d₃⁻ = 45
d₁⁺ + d₄⁻ - d₄⁺ = 10

x₁, x₂, d₁⁻, d₂⁻, d₃⁻, d₁⁺, d₄⁻, d₄⁺ ≥ 0

Solution.

Substituting x₁ = 0, x₂ = 0, d₁⁺ = 0 & d₄⁺ = 0

Therefore, d₁⁻ = 80, d₂⁻ = 70, d₃⁻ = 45, d₄⁻ = 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₁, P₂, P₃ and P₄ are arranged in descending order.

Table 1

Use Horizontal Scrollbar to View Full Table Calculation

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₁
z₁ - c₁ = P₁ X 1 + 5P₃ X 1 + 3P₃ X 0 + 0 X 0 0 = P₁ + 5P₃

Column x₂
z₂ - c₂ = P₁ X 1 + 5P₃ X 0 + 3P₃ X 1 + 0 X 0 0 = P₁ + 3P₃

Column d₁⁻
z₃ - c₃ = P₁ X 1 + 5P₃ X 0 + 3P₃ X 0 + 0 X 0 P₁ = 0

Column d₂⁻
z₄ - c₄ = P₁ X 0 + 5P₃ X 1 + 3P₃ X 0 + 0 X 0 5P₃ = 0

Column d₃⁻
z₅ - c₅ = P₁ X 0 + 5P₃ X 0 + 3P₃ X 1 + 0 X 0 3P₃ = 0

Column d₄⁻
z₆ - c₆ = P₁ X 0 + 5P₃ X 0 + 3P₃ X 0 + 0 X 1 0 = 0

Column d₁⁺
z₇ - c₇ = P₁ X (-1) + 5P₃ X 0 + 3P₃ X 0 + 0 X 1 P₄ = P₁ P₄

Column d₄⁺
z₈ - c₈ = P₁ X 0 + 5P₃ X 0 + 3P₃ X 0 + 0 X (-1) P₂ = P₂

Column X_B
z_B - c_B = P₁ X 80 + 5P₃ X 70 + 3P₃ X 45 + 0 X 10 = 80P₁ + 485P₃

Since, P₁, P₂, P₃ and P₄ 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₁ 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₃ row, therefore, column under x₁ becomes the key column.

Key row

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

Pivot element = 1
Therefore, d₂⁻ departs and x₁ enters.

Table 2

Key column = x₂ column
Minimum positive value = Min(10/1, 45/1) = 10
So d₁⁻ row is the key row.
d₁⁻ departs & x₂ enters

Table 3

On small screens, scroll horizontally to view full calculation

Key column = d₁+ column
Minimum positive value = Min(35/1, 10/1) = 10
d₄⁻ departs & d₁+ enters

Final Optimal Table: Modified Simplex Method

In the above table, since all values in P₁ and P₂ 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₃ row. Since element 3 in P₃ row is above the element 1 in the P₂ 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₄ row will not be considered.

The optimal solution is:

x₁ = 70, x₂ = 20, d₁⁺ = 10, d₃⁻ = 25, d₁⁻ = 0, d₂⁻ = 0