ISE 3230

What is a basic variable?

It is a variable that is currently in the basis
- It has a non-zero value in the BFS

Where is a basic variable found while doing Simplex in the Tableau form?

The column forms part of the identity matrix, the value is found in RHS column

What is a non-basic variable?

It is a variable not in the bases (it is set to zero in the BFS)

Where is a non-basic variable found while doing Simplex in the Tableau form?

The column is not part of the identity matrix, its value is zero in the RHS

At the start, are slack variables basic or non-basic?

Slack variables are often basic

At the start, are decision variables basic or non-basic?

Slack variables are often non-basic

What is a feasible solution?

It is any solution satisfying all the constraints and x_i is greater than or equal to zero (non-negativity constraint)

Where is the feasible solution located while doing Simplex in the Tableau form?

Look at RHS, it is all values greater than or equal to zero

What is the basic feasible solution?

It is the feasible solution where all non-basic variables = 0

Where is the basic feasible solution located while doing Simplex in the Tableau form?

The Tableau’s RHS column shows current BFS values, the columns of basic variables form the identity matrix.

What does it mean to have an alternate solution?

Another BFS gives the same optimal value

How can you see that there is an Alternative Optimal Solution available while doing Simplex in the Tableau form?

There will be a zero coefficient in the objective row for a non-basic variable at optimality

How do you know you have an unbounded objective?

It is unbounded if the pivot column has no positive elements. This means that no leaving variable exists and the objective can increase indefinitely

What are the 2 conditions for having an Alternative Optimal Solution?

1. The Tableau is optimal

2. There exists at least one non-basic variable with zero as its coefficient in the objective row

Give me the steps for the Two-Phase Method (Phase 1)

Phase I – Find a feasible solution

1. Add artificial variables to constraints that cannot give a basic feasible solution.

2. Set Phase I objective: minimize the sum of artificial variables.

3. Build initial tableau with artificial variables as basic.

4. Make objective row canonical (eliminate basic variables from objective).

5. Run simplex until optimal:

   • If min w = 0 → feasible → go to Phase II

   • If min w > 0 → infeasible → stop

Give me the steps for the Two-Phase Method (Phase 2)

Phase II – Optimize original objective
6. Drop artificial variables (columns removed).
7. Restore original objective function.
8. Make objective row canonical (eliminate current basic variables from objective).
9. Run simplex until optimal (no negatives in max, no positives in min).

What is degeneracy in simplex?

Degeneracy occurs when a basic variable in the current BFS has value 0, meaning multiple BFSs correspond to the same corner of the feasible region.

How do you spot degeneracy in the Tableau while doing Simplex?

Look at the RHS (solution) column:

• If a basic variable’s value = 0, the BFS is degenerate.

• Often occurs during minimum ratio test when multiple rows tie.

How do you find B^-1in the Tableau form of Simplex?

B^-1 is always the matrix formed by the columns of the basic variables in the original constraint matrix, not the tableau.

What is the formula you need to know for filling in a partial Simplex Tableau?

Z-Row Entry = C_B * (that column in basic rows) - c_j

• Z-Row Entry - What is the value of z for the column you’re looking at?

• C_B - The costs of the basic variables, look at the basic variables in z-row

• Column - Find the column of interest and only pull the basic variables from it

• C_j - For the column of interest, find its value in the original objective function

What is b (lowercase) in the Simplex Tableau?

b is the original RHS vector of the constraints, before any Simplex row operations.

What is B^-1b?

B^-1b is the RHS column in the Simplex Tableau

What is a (lowercase) in the Simplex Tableau?

It is the column of coefficients of variable x_j in the original constraints

What information does B^-1a give?

This gives information about basic variables when the column variable changes

How do you solve a complementary slackness problem?

1. Convert the primal to the dual

2. Graph the dual and find its optimal value

3. Plug that optimal value into all the constraints for the dual form and see if equality holds.

4. If it does, then it is binding.

5. If the optimal values of the dual are greater than or equal to zero, our slack variables must be equal to 0 as well.

6. In the primal form, anything that is binding can remain. The rest can be crossed out. (Includes slack if the optimal values of the dual are greater than or equal to zero)

7. Then add together the constraints to get the optimal values for the primal.

What does the Weak Duality Theorem state?

For any feasible solution of a maximization primal and any feasible solution of its dual minimization, the primal objective ≤ dual objective

z_primal less than or equal to z_dual

The dual always provides an upper bound on the max problem

What does the Strong Duality Theorem state?

If both the primal and dual have optimal solutions, then the optimal objective values are equal:

z_primal equal to z_dual

What happens to the dual if the primal is unbounded?

The dual is infeasible

If one problem is infeasible, what can the other be?

The other problem is either infeasible or unbounded

When are primal and dual solutions optimal?

If both are feasible and their objective values are equal, then both are optimal.

How do you know a primal is unbounded from the Simplex Tableau?

You find an entering variable that improves the objective but its column has no positive entries. The no leaving variable means its unbounded.

How do you know when the primal is infeasible?

Phase 1 of the 2-phase method ends with a min w > 0

What is a shadow price?

A shadow price is the dual variable for a constraint and represents the value of one more unit of that resource

What does a shadow price y_i tell you economically?

How much the objective value increases per unit increase in resource i.

When is a shadow price positive?

When the corresponding constraint is binding

What is the shadow price if a constraint is nonbinding?

Zero - extra resource has no value

What does complementary slackness say about constraints for the economic interpretation?

Binding constraint - shadow price > 0

Nonbinding constraint - shadow price = 0

What are the reduced costs of basic variables at optimality?

Zero

In a maximization problem, what does a negative reduced cost mean?

Increasing the variable decreases the objective so it stays at zero

What is the economic meaning of reduced cost?

Profit of product - value of resources used to make it

What does the reduced cost tell you about changing c_j?

How much c_j should improve before the variable becomes positive

Where are the shadow prices located in the Simplex Tableau?

Shadow prices are in the z-row, under the slack variable columns

Where are the reduced costs located in the Simplex Tableau?

Reduced costs are the z-row coefficients under the decision variables

How can you tell if a constraint is binding from the Simplex Tableau? (Slack variable rule)

• Slack = 0 → constraint binding

• Slack > 0 → constraint nonbinding

Look at the RHS of the slack variable row

How can you tell if a constraint is binding from the Simplex Tableau? (Shadow price rule)

• Shadow price > 0 → constraint binding

• Shadow price = 0 → constraint nonbinding