12
Oct

How to Solve a Linear Programming Problem Using the Dual Simplex Method


Hello everyone this is Mirzaei from Cal poly
Pomona, and in this lesson we are going to learn, how to solve a linear programming problem
using the Dual Simplex method. Consider a linear programming problem as shown on the
screen. Suppose we are trying to solve this problem. We have the option of choosing two-phase
or big M to solve this problem. Another alternative to solve this problem would be using the Dual
Simplex method. In Dual Simplex method, we are trying to solve the dual of a problem
instead of the initial problem. Because, according to a theorem, we know that the value of a
primal problem and its dual programming its going to be the same at the optimal point,
and that’s why instead of solving the problem we have the option of solve it dual problem,
because both at the end converge to the same optimal solution. So, let’s look at the dual
programming of this primal problem. Before writing the dual programming of this initial
problem, we need to normalize this problem. We know that for a minimization problem the
normal condition is when all the constraints have>=. Therefore, to change this minimization
problem to a normal form I have to multiply the first three constraints by -1. If I multiply
the first three constraints by -1, and keep the last constraint as it is, I am able to
write the normalized form of this minimization problem. Now, that I have a normal minimization
problem, I am able to write the dual programming of this problem, which is a normal maximization
problem. I can start solving this problem using the Simplex method. Because all the
constraints are in form of=or=sign. So, these are the two important criteria
that we have to have for a problem before start solving it using the Dual Simplex method.
In this problem, since we have all the coefficients of the objective function positive for a minimization,
our objective function is in form of optimality. Also, we have one constraint that has a>=sign
here, and, therefore, both conditions are met to solve this problem using the Dual Simplex
method. The first thing that we need to do before starting the Dual Simplex method is
to standardize this problem. The first three constrains of this problem can be easily standardized
by adding slack variables. Because all the constraints are in form of

Tags: , , , , , , , , , , , , , , ,

75 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *