Jack Ulern University Maximization Exercise - Simplex MethodExample of the Simplex Method - Two-Phase

Problem Data

We want to Maximize the following problem:

Objective Function
Z = 2X1 + X2
Subject to the following constraints
  • X1 + X2 ≤ 10
  • X1 - X2 ≤ 0
  • X1 + 0X2 ≤ 4

X1, X2 ≥ 0

Description
Jack Ulern University Maximization Exercise - Simplex MethodJack is an inspiring freshman at Ulern University. He realized that "all work and no play makes Jack a dull boy. As a result, Jack wants to apportion his available time of about 10 hours a day between work and play. He estimates that play is twice as much fun as work. He also wants to study at least as much as he plays. However, Jack realizes that if he is going to get all his homework assignments done, he cannot play more than 4 hours a day. How should Jack allocate his time to maximize his pleasure from both work and play? Solve the problem with the Simplex 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 “≤” (least equal), therefore the slack variable S1. This variable will be placed at the base in the initial matrix.
  • Constraint 2: It has sign “≤” (least equal), therefore the slack variable S2. This variable will be placed at the base in the initial matrix.
  • Constraint 3: It has sign “≤” (least equal), therefore the slack variable S3. This variable will be placed at the base in the initial matrix.

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:

Maximize Z = 2X1 + X2 + 0S1 + 0S2 + 0S3

Subject to:

  • X1 + X2 + S1 + 0S2 + 0S3 = 10
  • X1 - X2 + 0S1 + S2 + 0S3 = 0
  • X1 + 0X2 + 0S1 + 0S2 + S3 = 4

Initial Matrix

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

Table 1Cj21000
CbBaseX1X2S1S2S3R
0S11110010
0S21-10100
0S3100014
Z-2-10000

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 = (0×1) + (0×1) + (0×1) - (2) = -2
  • Z2 = (Cb,1×X2,1) + (Cb,2×X2,2) + (Cb,3×X2,3) - Cj,2 = (0×1) + (0×-1) + (0×0) - (1) = -1
  • Z3 = (Cb,1×S1,1) + (Cb,2×S1,2) + (Cb,3×S1,3) - Cj,3 = (0×1) + (0×0) + (0×0) - (0) = 0
  • Z4 = (Cb,1×S2,1) + (Cb,2×S2,2) + (Cb,3×S2,3) - Cj,4 = (0×0) + (0×1) + (0×0) - (0) = 0
  • Z5 = (Cb,1×S3,1) + (Cb,2×S3,2) + (Cb,3×S3,3) - Cj,5 = (0×0) + (0×0) + (0×1) - (0) = 0
  • Z6 = (Cb,1×R1) + (Cb,2×R2) + (Cb,3×R3) = (0×10) + (0×0) + (0×4) = 0

b) Optimality Condition (Incoming Variable):

In the reduced cost vector (Z) we have negative values, so we must select the most negative for the pivot column (maximization).

In the vector Z (excluding the last value), we have the following numbers: [-2, -1, 0, 0, 0]. The most negative 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 S1 → R1 / X1,1 = 10 / 1 = 10
  • Row S2 → R2 / X1,2 = 0 / 1 = 0 (The Lowest Value)
  • Row S3 → R3 / X1,3 = 4 / 1 = 4

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

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

See list of examples of the subject

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

Purchase our monthly subscription from

$10USD

Learn more and save with semi-annual, annual and lifetime plans.

Get Access
Any doubts? Contact us