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. (Version 1 Solutions and Version 2 Solutions)
- 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)
- Quiz 4 - Friday Oct 27 (Solution)
- This quiz will cover the revised simplex method. (suggested problems:
Chvátal 7.1-7.2; Vanderbei 6.1-6.3, minus the parts about dual
- Quiz 5 - Friday Nov 10 (Solution)
- This quiz will cover problems in general form, and the dual simplex
method. (Suggested problems: Chvátal 9.1, 9.2; Vanderbei 5.6
(via the dual simplex method)).
- Final Exam: December 5 at noon, Henry Angus building room
- The exam covers the entire contents of the course, so roughly
Chvátal chapters 1-5, 7, 9, and 10, plus the additional topics
discussed at the end (and of course minus the things not covered in
class, such as eta factorization in chapter 7).
- Old exams are available on the
department website. Unfortunately these don't have solutions;
however, if you try them I can check if what you're doing looks right,
and tell you whether or not a given problem would be reasonable for
this semester's final.
- Some practice problems for the
topics of the last week or so from the course, and Solutions. Questions 3 and 4
here are taken from past exams, and are a bit trickier than would be
reasonable on ours (past semesters have spent more time on matrix
games, I think).
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.