ABSTRACT
This chapter discusses the shadow prices on a firm mathematical footing. The cost vector or resource vector changes, a new constraint is added, a new variable is added, etc. The method of sensitivity analysis is to start from the choice of basis that was optimal and proceed from there to the solution to the altered problem. The specifics of sensitivity analysis for typical problem changes are given below. Column generation takes the following form: Every time the algorithm returns from Step 3 to Step 2, it solves the new LP starting from the optimal basic solution of the previous LP. This can be viewed as sensitivity analysis when columns are added, or it can viewed as equivalent to the simplex method with a peculiar way of selecting the entering basic variable. The latter view proves that the column generation algorithm is valid, provided that the search procedure finds at least one favorable column if one exists.
