Math 340 Assignment/Quiz/Exam Info
Each week there will be either a quiz or an assignment (or a midterm), the
details of which will be on this page. There will be a total of 5 quizzes and 5
assignments throughout the semester (with more quizzes at the beginning and
more assignments towards the end).
- Quiz 1 - Friday Sept 15 (Solution)
- This quiz will cover things through Wednesday Sept 13:
- Linear programs in standard form (suggested problems: Chvátal
- Feasible/infeasible/unbounded linear programs (suggested problems:
Chvátal 1.3, 1.4)
- Solving 2-variable linear programs graphically (suggested problems:
try this for any of the 2-variable linear programs in the exercises of
Chvátal ch. 2 or Vanderbei ch. 2)
- Rewriting a linear program in standard form with slack variables
(suggested problems: try this for any of the linear programs in the
exercises of Chvátal ch. 2 or Vanderbei ch. 2)
- Quiz 2 - Friday Sept 22 (Solution)
- This quiz will cover things through Wednesday Sept 20:
- The simplex method (suggested problems with feasible initial
dictionaries: Exercises 2.1, 2.2 of Chvátal; also any of 2.1,
2.2, 2.8, 2.9 of Vanderbei you want to do).
- The two-phase simplex method for infeasible initial dictionaries
(suggested problems: Exercise 3.9 of Chvátal; also any of
2.3-2.7,2.10 of Vanderbei you want to do).
- (Feel free to use computer tools to help with the simplex method
computations - just remember, on the quiz you'll have to do it by
hand, and it will be designed to be reasonable to do by hand).
- Quiz 3 - Friday Oct 5 (Solution)
- This quiz will cover things through Wednesday Oct 3:
- The definition of the dual to an LP, and its relation to the primal.
(suggested problems: Chvátal 5.1-5.2, Vanderbei 5.1-5.4, 5.6)
- Midterm: in class on Friday October 20.
- A past exam for practice (and its
Solutions). We won't cover the
revised simplex method before the exam, so that sort of problem won't
be on our midterm.
- Problem 5 as stated also isn't something that could be on our
exam, because it involves duals to LPs with free variables /
equalities. Sorry I didn't notice that when I posted it! For a
problem that could be on our exam you could replace it with "prove
that either there exists a x≥0 such that
Ax≤0 and c·x>0, or
a y≥0 with
ATy≥c, but not both."
- Topics covered by the midterm are as follows.
- Linear programs (especially in standard form) and what it means
to be infeasible, unbounded, or to have an optimal solution.
(Chvátal Ch. 1 / Vanderbei Ch. 1)
- The simplex method, following the standard rule: dictionaries, how to
pivot for a feasible dictionary, and understanding uniqueness or
non-uniqueness of optimal solutions.
(Chvátal Ch. 2 / Vanderbei Ch. 2)
- The two-phase simplex method for initially infeasible dictionaries.
(Chvátal Ch. 3 / Vanderbei Ch. 2.3)
- Degeneracy, the possibility of cycling, and anti-cycling methods.
(Chvátal Ch. 3 / Vanderbei Ch. 3)
- Matrix formalism for linear programs and for dictionaries
(Beginnings of Chvátal Ch. 7 / Vanderbei Ch. 6)
- The dual to a standard form LP, weak and strong duality,
(Chvátal Ch. 5 / Vanderbei Ch. 5)
- Applications of duality: the theorem of the alternative,
complementary slackness, and the economic significance of dual
(Chvátal Ch. 5 / Vanderbei Ch. 5)
- Final Exam: December 5 at noon, location TBA.
For homework assignments, you may collaborate, but each person must write up
their solutions independently in their own words. Two or more people turning in
identical homework assignments are in violation of the UBC academic integrity
code and will be given a 0. Late homeworks may not be accepted.
At the end of the semester, your lowest quiz grade and lowest
homework grade will be dropped. This policy is intended to cover situations
where you may miss a quiz or assignment for whatever reason, without you
needing to come to me to ask for a concession. Beyond this, missed quizzes,
assignments, or midterms will be given a 0 by default - the only exceptions to
this are by instructor permission beforehand, or in the case of a medical
emergency notifying me within 48 hours and presenting a doctor's note. In such
cases there will be no make-up quiz or exams; your grade will be determined
from your other work throughout the term.