In this video, I'll talk about how to deal with unrestricted-in-sign variables in the
simplex method and their application in the production smoothing scheduling problem.
In the previous videos, we talked about how to solve a linear programming problem when
it is converted into the standard form.
In this standard form, we want xj to be greater than or equal to 0.
If we have a variable x that is less than or equal to 0, we can define a variable y
which is equal to -x, and y should be greater than or equal to 0.
However, if we have a variable x that is urs, which means, it can take positive numbers,
negative numbers, or 0, then the problem is not in the standard form.
To deal with this situation, for each URS variable xi, we need to define two new nonnegative
variables xi+ and xi-.
xi+ denotes the positive deviation from 0, and xi- denotes the negative deviation from
0.
Then replace each xi with xi+ ? xi- and add the sign restrictions.
After that we can apply the simplex method to solve the modified problem formulation.
During the simplex iterations, the URS variable xi in every BFS must fall into one of the
following three cases.
Either the positive deviation is greater than 0, or the negative deviation is greater than
0, or they are both equal to 0.
We will not have the situation that the positive deviation and the negative deviation are both
greater than 0.
Now let me show you an example.
This is a maximization problem.
We have two variables, x1>=0, and x2 is urs.
For this problem, the feasible region is marked by the shaded area.
We can solve it graphically, and point D (3, 3) is the optimal solution, z*=15.
Let's try to solve it using the simplex method.
We need to introduce two slack variables, s1 and s2 and make these two equality constraints.
Then for urs variable x2, we introduce two variables x2+ and x2-.
Replace each x2 with x2+ minus x2-.
And add the sign restrictions.
This is the simplex tableau.
In this tableau, s1 and s2 are BVs.
And others are NBVs.
Let's set NBVs to 0 and solve for BVs. s1=9, s2=9, and z=0.
The entering variable will be x1, because it has the most negative coef in R0.
The ratio is the RHS divided by the coef of x1. 9/2 and 9/1.
R1 has the smallest ratio.
So it is the pivot row.
We need to change this to 1 and make it disappear from other rows using EROs.
This is the updated tableau.
x1 and s2 are BVs.
And others are NBVs.
Let's set NBVs to 0 and solve for BVs. x1=9/2, s2=9/2, and z=27/2.
The entering variable will be x2+, because it has the most negative coef in R0.
The ratios are 9 and 3.
So R2 is the pivot row because it has the smallest ratio.
We need to change this to 1 and make it disappear from other rows using EROs.
This is the updated tableau.
x1 and x2+ are BVs.
And others are NBVs.
Let's set NBVs to 0 and solve for BVs. x1=3, x2+=3, and z=15.
Now we don't have negative coefs in R0.
So this tableau is optimal.
The optimal solution is x1=3, x2=x2+?x2-=3-0=3, s1=s2=0, z*=15.
Also, this solution is the same as the one we got using the graphical method.
URS variables are useful in modeling the changes among different periods.
Let's see an example called production smoothing scheduling.
A company is scheduling their production for the next 3 months.
They already know the fixed demand for M1 through M3.
They are 200, 150, 400, respectively.
Four types of costs are involved for each product.
The manufacturing cost is $2000/product.
If they manufacture more products than the demand for that month, there will be a holding
cost at the end of each month, which is $500/product.
They want the production to go as smoothly as possible.
However, because the demand changes from month to month, and there is a holding cost, they
may need to increase or decrease production between one month the another.
If they increase production, they need to hire more people and train them to operate
the machines.
There will be an extra $4000 involved for each unit of increased production.
If they decrease production, they need to release some people and it may hurt the morale.
There will be an extra $3000 involved for each unit of decreased production.
300 products were manufactured and they were all sold before M1 started so there was no
inventory at the beginning.
The company wants to minimize the total cost during next 3 months.
For this type of problems, it is very important to define the appropriate decision variables.
We let pt be the number of products manufactured during Mt (t=1, 2, 3).
Let it be the inventory at the end of Mt. Let xt+ be the production increase from M(t-1)
to Mt. Let xt- be the production decrease from M(t-1) to Mt.
So, xt+ and xt- cannot both be positive.
The total cost is equal to the manufacturing cost + the holding cost + the increasing production
cost + the decreasing production cost.
For the constraints, we have these two sets of relations.
First, Mt's inventory is equal to M(t-1)'s inventory +Mt's production-Mt's demand.
We can create these three constraints using this relation.
Second, the production difference is equal to Mt's production - M(t-1)'s production,
which is also equal to production increase - production decrease.
We can create these three constraints using this relation.
This is a minimization problem.
We can take the opposite of the objective function and maximize -z.
We only have the equality constraints, so we need to use the big M method to solve the
problem.
The optimal solution is this one.
It means, we always manufacture 250 products each month.
We hold 50 at the end of M1, we hold 150 at the end of M2.
We are not increasing production between different months.
We decrease production by 50 from M0 to M1.
The total cost is $1.75 million.
Okay, that's how to deal with unrestricted-in-sign variables in the simplex method and their
application in the smoothing scheduling problem.
Thanks for watching.