Cohen Chemicals, Inc. Minimization problemExample of the Simplex Method - Two-Phase

Problem Data

We want to Minimize the following problem:

Objective Function
Z = 2500X1 + 3000X2
Subject to the following constraints
  • X1 + 0X2 30
  • 0X1 + X2 20
  • X1 + X2 60

X1, X2 ≥ 0

Description
Cohen Chemicals, Inc. Minimization problemCohen Chemicals, Inc., produces two types of photo-developing fluids. The first, a black-and-white picture chemical, costs Cohen $2,500 per ton to produce. The second, a color photo chemical, costs $3,000 per ton. Based on an analysis of current inventory levels and outstanding orders, Cohen’s production manager has specified that at least 30 tons of the black-and-white chemical and at least 20 tons of the color chemical must be produced during the next month. In addition, the manager notes that an existing inventory of a highly perishable raw material needed in both chemicals must be used within 30 days. To avoid wasting the expensive raw material, Cohen must produce a total of at least 60 tons of the photo chemicals in the next month. Solve this problem using the two-phase method.

Solution

To solve the problem, the iterations of the simplex method will be performed until the optimal solution is found.

Next, the problem will be adapted to the standard linear programming model, adding the slack, excess and/or artificial variables in each of the constraints and converting the inequalities into equalities:

  • Constraint 1: It has sign “” (greatest equal), therefore the excess variable S1 will be subtracted and the artificial variable A1 will be added. In the initial matrix, A1 will be in the base.
  • Constraint 2: It has sign “” (greatest equal), therefore the excess variable S2 will be subtracted and the artificial variable A2 will be added. In the initial matrix, A2 will be in the base.
  • Constraint 3: It has sign “” (greatest equal), therefore the excess variable S3 will be subtracted and the artificial variable A3 will be added. In the initial matrix, A3 will be in the base.

Since the problem has artificial variables, the two-phase method will be used. In the first phase, the objective function will be modified to minimize the sum of the artificial variables.

Now we will show the problem in the standard form. We will place the coefficient 0 (zero) where appropriate to create our initial matrix:

Objective Function:

Minimize Z = 0X1 + 0X2 + 0S1 + 0S2 + 0S3 + A1 + A2 + A3

Subject to:

  • X1 + 0X2 - S1 + 0S2 + 0S3 + A1 + 0A2 + 0A3 = 30
  • 0X1 + X2 + 0S1 - S2 + 0S3 + 0A1 + A2 + 0A3 = 20
  • X1 + X2 + 0S1 + 0S2 - S3 + 0A1 + 0A2 + A3 = 60

Initial Matrix Phase One

We will use the coefficients of the equations to elaborate our first table:

Table 1Cj00000111
CbBaseX1X2S1S2S3A1A2A3R
1A110-10010030
1A2010-1001020
1A31100-100160
Z22-1-1-1000110

a) Reduced Cost Vector Calculation (Z):

The values recorded in row Z were obtained as follows:

  • Z1 = (Cb,1×X1,1) + (Cb,2×X1,2) + (Cb,3×X1,3) - Cj,1 = (1×1) + (1×0) + (1×1) - (0) = 2
  • Z2 = (Cb,1×X2,1) + (Cb,2×X2,2) + (Cb,3×X2,3) - Cj,2 = (1×0) + (1×1) + (1×1) - (0) = 2
  • Z3 = (Cb,1×S1,1) + (Cb,2×S1,2) + (Cb,3×S1,3) - Cj,3 = (1×-1) + (1×0) + (1×0) - (0) = -1
  • Z4 = (Cb,1×S2,1) + (Cb,2×S2,2) + (Cb,3×S2,3) - Cj,4 = (1×0) + (1×-1) + (1×0) - (0) = -1
  • Z5 = (Cb,1×S3,1) + (Cb,2×S3,2) + (Cb,3×S3,3) - Cj,5 = (1×0) + (1×0) + (1×-1) - (0) = -1
  • Z6 = (Cb,1×A1,1) + (Cb,2×A1,2) + (Cb,3×A1,3) - Cj,6 = (1×1) + (1×0) + (1×0) - (1) = 0
  • Z7 = (Cb,1×A2,1) + (Cb,2×A2,2) + (Cb,3×A2,3) - Cj,7 = (1×0) + (1×1) + (1×0) - (1) = 0
  • Z8 = (Cb,1×A3,1) + (Cb,2×A3,2) + (Cb,3×A3,3) - Cj,8 = (1×0) + (1×0) + (1×1) - (1) = 0
  • Z9 = (Cb,1×R1) + (Cb,2×R2) + (Cb,3×R3) = (1×30) + (1×20) + (1×60) = 110

b) Optimality Condition (Incoming Variable):

In the reduced cost vector (Z) we have positive values, so we must select the highest value for the pivot column (minimization).

In the vector Z (excluding the last value), we have the following numbers: [2, 2, -1, -1, -1, 0, 0, 0]. The highest value is = 2 which corresponds to the X1 variable. This variable will enter the base and its values in the table will form our pivot column.

d) Feasibility Condition (Outgoing Variable):

The feasibility condition will be verified by dividing the values of column R by the pivot column X1. To process the division, the denominator must be strictly positive (If it's negative or zero, it'll display N/A = Not applicable). The lowest value will define the variable that will exit from the base:

  • Row A1 → R1 / X1,1 = 30 / 1 = 30 (The Lowest Value)
  • Row A2 → R2 / X1,2 = 20 / 0 = NA
  • Row A3 → R3 / X1,3 = 60 / 1 = 60

The lowest value corresponds to the A1 row. This variable will come from the base. The pivot element corresponds to the value that crosses the X1 column and the A1 row = 1.

Enter the variable X1 and the variable A1 leaves the base. The pivot element is 1

Learn with step-by-step explanations

At PM Calculators we strive to help you overcome those tricky subjects in an easier way.

Membership

With access to our membership you will have access to 13 applications to learn projects, linear programming, statistics, among others.

What calculators are included?

  • Critical Path PERT and CPM

  • Linear Programming Methods

  • Normal Distribution

  • Break-even and more