chapitre 3 Flashcards
What can we do when a primal tableau is not feasible ?
creation of an auxiliary LP whose solution provides a feasible solution to the initial problem, Once a feasible solution is found, we can apply the phase II of the simplex algorithm
Construction of the Auxiliary Problem
we add x0 to the answer b to make it >0
The objective function is Max z′ = −x0 ⇐⇒ −Min z′ = x0
Characteristics of The Auxiliary Problem
It always has a feasible solution
It always has an optimal solution
We can use the Phase II of the simplex algorithm to solve the auxiliary problem
The initial problem has at least one feasible solution if and only if the optimal value of the auxiliary problem is zero
If the optimal value of the auxiliary problem is zero, then it is easy to get a feasible tableau for the initial problem
If we have determined a feasible solution to the initial problem after solving the auxiliary problem, then we can apply the Phase II of the simplex algorithm to solve the initial problem
end of phase I
As soon as x0 exits the basis, then z′ = 0
As z′ = 0, this tableau is optimal for the objective funtion z′
We get an initial feasible tableau for the initial problem by
removing the columns x0 and z′ and the last row
what are reduced costs, what when they are negative ?
The last row of the tableau contains the reduced costs −γN , negative reduced costs
indicates that it may be possible to find a better solution ! because − γr < 0, any increase of the non-basic variable xr will cause an increase in z.
Solution of an unbounded tableau
It means that the optimal solution is to have xr as large as possible–> no finite optimum
(xr → +∞) to maximize the objective function
bland’s rule
When several candidates may enter or exit a basis, always choose the variable xr with the smallest index, case of same ratio : the smallest exiting basis is selected
