Linear programming, del 2 Flashcards
Vad är reduced cost?
Reduced cost shows how much a variables coefficient must change for the variable to become positive in the optimal solution.
When is the reduced cost 0?
If the variable has positive value. fel??? Vid minimering är den negativ, eller????
What can a feasible region for a LP problem be?
Non existent
A single point –> alla begränsningar möts i en enda punkt
A line –> lösningsmängden ligger längs en linje
A polygon –> en sluten och begränsad mängd
An unbounded area –> oändligt i någon riktning
Three categories of LP:
- Is infeasible
- Has a unique optimal solution OR alternate optimal solutions
- Has an objective function that can be increased without bound (begränsning)
Steps leading to Simplex method:
Formulate problem as LP
Put in standard form
Put in tableau form
Execute simplex method
När är a set of equations I tableu-form?
If högerledet (RHS) is non-negative and there is basic variable
What is a basic variable?
A basic variable is a variable whose coefficient in the equation is +1 and whose coefficient in all other equations of the problem is 0.
When do we have to do if the constraint is missing a basic variable?
If the constraint is a equalitie and has no basic variable, an artificial variable must be added. (a1)
Uträkning för new values i LP:
If KeyRow = Old n / KeyElement
If not KeyRow = Old n - KeyRow * KeyColumn / KeyElement
Uträkning för zj:
Cb * x1 + Cb * x1
Uträkning för bredvid b:
Old n / KeyColumn på samma rad
4 special cases:
- Infeasibility
- Unboundedness
- Alternative Optimal Solution
- Degeneracy
Describe infeasibility
Infeasibility is detected in the simplex method when an artificial variable remains positive in the final tableau
Describe unboundedness
A linear program has an unbounded solution if all entries in an entering column are non-positive
Describe alternative optimal solution
A linear program has alternate optimal solutions if the final tableau has a cj – zj value equal to 0 for a non-basic variable.
