Assignment 1 :

- 1.
- Devise a linear program formulation for the ATM Cash Problem discussed in the class.
- 2.
- Show that the General, Canonical and Standard Formulations of Linear Programs are equivalent.
- 3.
- Show the equivalence of the Canonical Form to a polyhedron formed by the intersection of m halfspaces.
- 4.
- Prove that degenerate basic feasible solutions which are same in non-zero components correspond to the same vertex.
- 5.
- Show: If no adjacent BFS of a BFS
*B*has cost less than that of*B*then*B*is optimal. - 6.
- Supoose
*b*and_{1}*b*are two BFS's which are not adjacent to each other and_{2}*C*1 and*C*2 are the columns corresponding to the BFS's*b*and_{1}*b*then there exists another basis in ._{2} - 7.
- Prove that if
*e*is an edge of a polyhedron and , i.e ,then*z*,_{1}*z*belong to_{2}*e*. - 8.
- Resolve the assumption
*b*>=0 in the derivation of Simplex Method. - 9.
- Prove that Bland's Rule which is
Use lowest numbered column for basis change and use lowest numbered row for determining .

prevents cyclicity in the Simplex Method.

- 10.
- Design Linear Programs which demonstrate the relationship possible between primal & dual from the set of properties of bounded feasiblity, unbounded feasibility and infeasibility.
- 11.
- Analyze the worst case behaviour of the Simplex. This should include the time for pivoting also.