Linear Optimization (Math 354, section 3), Fall 2023 (Rutgers, NB)

(Last Update: Dec. 23, 2023) http://sites.math.rutgers.edu/~zeilberg/math354_f23.html

Instructor: Dr. Doron Zeilberger (aka Dr. Z.) [Email: DrZlinear at gmail dot com (only for this class)]
Time: Mondays and Thursdays, Period 2, 10:20-11:40am
Place: TILLET HALL, ROOM 264 (Livingston Campus)
Textbook: "Elementary Linear Programming with Applications", second edition, by Bernard Kolman and Robert E. Beck, Elsevier [on-line]
Dr. Z.'s Office Hours: MTh 9:00-10:10am, TILLET 105
TA at Large: Mr. George Spahn (Email: gs828 at rutgers dot edu)
Mr. Spahn's On-Line Office Hours: Monday and Thursday, 12pm-1pm via Zoom
Mr. Mihail Tarigradschi's On-Line Office Hours: Tuesdays and Fridays, 12pm-1pm via Zoom
Homework grader: Ms. Kaylee Weatherspoon
CLASS POLICY (and instructions how to submit your homework)

Added Nov. 3, 2023: Everyone who didn't do well on Exam 1 is welcome to join the Second Chance Club for Exam 1

Added Nov. 28, 2023: Everyone who didn't do well on Exam 2 is welcome to join the Second Chance Club for Exam 2

Schedule and Homework

Thurs., Sept. 7:
Lecture 1: 0.2 ;
HW1 (due 9/13, 10:00 pm): Section 0.2: 1, 3, 5 ,7 .
Here is the "getting to know you" "quiz" and here are the beautiful solutions of student W. Ge.
Here is attendance quiz 1 and here are the Solutions to attendance quiz 1 .
Mon., Sept. 11:
Lecture 2: 0.3, 0.4, 0.5;
HW2 (due 9/20, 10:00pm): 0.3: 1, 3, 5 ,7 ; 0.4: 1, 3, 5; 0.5: 1, 3, 5, 19

Here is attendance quiz 2 and here are the Solutions to attendance quiz 2 .
Thurs., Sept. 14:
Lecture 3: 1.1;
HW3 (due 9/20, 10:00pm): 1.1: 1, 3, 5, 7, 9 ;
real quiz 1 (on Lecture 1) [during the first ten minutes of the class]
Here is attendance quiz 3 and here are the Solutions to attendance quiz 3 .
Here is Real quiz 1 and here are the Solutions to Real quiz 1 . average=6.59 (out of 8)
Mon., Sept. 18:
Lecture 4: 1.2;
HW4 (due 9/27, 10:00pm): 1.2: 5, 7, 9, 11, 13 .

Here is attendance quiz 4 and here are the Solutions to attendance quiz 4 .
Thurs., Sept. 21:
Lecture 5: 1.3
HW5 (due 9/27, 10:00pm): 1.3: 7, 8, 9, 10, 13 (only part (a)), 15 (only part (a))
real quiz 2 (on Lectures 2, 3) [during the first ten minutes of the class]

Here is attendance quiz 5 and here are the Solutions to attendance quiz 5 [ignore the "k" part]
Here is Real quiz 2 and here are the solutions to Real quiz 2 . average=4.4 (out of 8)
Mon., Sept. 25: Guest Lecturer: Soon-To-Be Dr. George Spahn
Lecture 6: 1.4
HW6 (due 10/4, 10:00pm): 1.4: 1, 3, 5, 7 .

Here is Intended attendance quiz 6 and here are the Solutions to the Intended attendance quiz 6 .
Thurs., Sept. 28:
Lecture 7: 1.5
HW7 (due 10/4, 10:00pm): 1.5: 1, 3, 5, 9 .
real quiz 3 (on Lectures 4, 5) [during the first ten minutes of the class]

Here is attendance quiz 7 and here are the Solutions to attendance quiz 7 .
Here is Real quiz 3 and here are the solutions to Real quiz 3 . average=7.24 (out of 8)
Mon., Oct. 2:
Lecture 8: 2.1 (part I) (pp. 104-112)
HW8 (due 10/11,10:00pm): 2.1: 1, 3, 5, 7, 9

Here is attendance quiz 8 and here are the Solutions to attendance quiz 8 .
Thurs., Oct. 5:
Lecture 9: 2.1 (part II) (pp. 113-118)
HW9 (due 10/11,10:00pm): 2.1: 11, 13, 15, 17, 19
real quiz 4 (on Lectures 6, 7) [during the first ten minutes of the class]

Here is attendance quiz 9 and here are the Solutions to attendance quiz 9 .
Here is Real quiz 4 and here are the solutions to Real quiz 4 using the geometrical approach of section 1.4 (sorry no picture) and solutions to Real quiz 4 using the algebraic approach of section 1.5 average=7.63 (out of 8)
Mon., Oct. 9:
Lecture 10: 2.3 (part I)
HW10 (due 10/18, 10:00pm): 2.3: 1(b), 2(b) 3(b)

Here is attendance quiz 10 and here are the Solutions to attendance quiz 10 .
Thurs., Oct. 12:
Lecture 11: 2.3 (part II)
HW11: HW (due 10/18, 10:00pm)
[The problems in the book are way too tedious to do by hand, hence this modified homework]
real quiz 5 (on Lectures 8, 9) [during the first ten minutes of the class]

Here is attendance quiz 11 and here are the Solutions to attendance quiz 11 .
Here is Real quiz 5 and here are the solutions to Real quiz 5 average=6.75 (out of 8)
Mon., Oct. 16: Special Lecture: How to Use Maple to Solve Linear Programming Problems (Bring your laptop!)
Attendace quiz: How to tell Maple to find the minimum of 2x+y, subject to x≥ 0 and y unconstrained.
Solution to Attendance quiz: simplex[minimize](-2*x+y,{x>=0}); [BTW, Maple returns nothing, since there is no solution]
HWmaple (due 10/25, 10:00pm, file name hwMapleFirstLast.pdf OR (better) hwMapleFirstLast.txt): Use the Maple command simplex[maximize] (or simplex[minimize]) to do problems 10-23 of section 2.1 and problems 20-23 of section 2.3. For the odd-numbered problems, check your answers with the back of the book. Also use the Maple command simplex[dual] to do problems 1-6 from section 3.1
Thurs., Oct. 19:
Lecture 12: 3.1
HW12 (due 10/25, 10:00pm): 3.1: 1, 3, 5, 7
real quiz 6 (on Lectures 10, 11) [during the first ten minutes of the class]

Here is attendance quiz 12 and here are the Solutions to attendance quiz 12 .
Here is Real quiz 6 and here are the solutions to Real quiz 6 average=5.55 (out of 8)
Mon., Oct. 23: Review
recording of optional review session
Thurs., Oct. 26: EXAM 1 (On Lectures 1-12) .
Here is Exam 1, and here are student Karen Pedri's perfect answers to Exam 1. average=81 (out of 100) (standard deviation: 21)
[Karen won a $25 amazon gift card for the best exam 1 award]
Mon., Oct. 30:
Lecture 13: 3.2 (part I)
HW13 (due 11/8, 10:00pm): 3.2: 1, 2, 3, 4, 5, 6, 7 and an extra problem

Here is attendance quiz 13 and here are the Solutions to attendance quiz 13 .
Thurs.,Nov. 2:
Lecture 14: 3.2 (part II)
HW14 (due 11/8,10:00pm): 3.2: 8,9,10,11

real quiz 7 (on Lecture 12) [during the first ten minutes of the class]

Here is Real quiz 7 and here are the solutions to Real quiz 7 average=5.8 (out of 8)
Here is attendance quiz 14 and here are the Solutions to attendance quiz 14 .
Mon., Nov. 6:
Lecture 15: 5.1 (part I)
HW15 (due 11/15, 10:00pm): 5.1: 2(a)(b) 3(a)(b) ,4(a)(b).

Here is attendance quiz 15 and here are the Solutions to attendance quiz 15 .
Thurs., Nov. 9:
Lecture 16: 5.1 (part II)
HW16 (due 11/15, 10:00pm): 5.1: 1,5,6,7
real quiz 8 (on Lectures 13,14) [during the first ten minutes of the class]

Here is Real quiz 8 and here are the solutions to Real quiz 8 average=5.34 (out of 8)
Here is attendance quiz 16 and here are the Solutions to attendance quiz 16 .
Mon., Nov. 13:
Lecture 17: 5.1 (part III)
HW17 (due 11/20, 10:00pm): 5.1: 8,9,10,12 .
Here are the answers to problems 8,10,12

Here is attendance quiz 17 and here are the Solutions to attendance quiz 17 .
Thurs., Nov. 16:
Lecture 18: 5.2 (part I)
HW18 (due 11/20, 10:00pm): 5.2: 1,2,3,4,5,6 (but only steps 1 and 2 of the algorithm)

real quiz 9 (on Lectures 15,16) [during the first ten minutes of the class]

Here is Real quiz 9 and here are the solutions to Real quiz 9 average=5.91 (out of 8)
Here is attendance quiz 18 and here are the Solutions to attendance quiz 18 .
Mon., Nov. 20:
Lecture 19: 5.2 (part II)
HW19 (due 11/26, 10:00pm ; deadline extended 12/6, 10:00pm ): 5.2: 1,2,3,4,5,6 (completely)

Here is attendance quiz 19 and here are the Solutions to attendance quiz 19 .
Tue., Nov. 21:
Review ;
real quiz 10 (on Lectures 17,18) [during the first ten minutes of the class] average=7.25 (out of 8)

Here is Real quiz 10 and here are the solutions to Real quiz 10
Mon., Nov. 27: EXAM 2 (On Lectures 1-19, with some emphasis on Lectures 13-19) . average=82.2 (out of 100)
Here is Exam 2, and here are student Tomas Spero's perfect answers to Exam 2, and student Seershika Kakuru's almost perfect answers to Exam 2
(with the solution to problem 7 corrected by Dr. Z. [Sheershika took the entering variable to be x₄₄ rather than x₃₄])
[Tomas and Seershika each won a $25 amazon gift card for the best exam 2 award.]
Thurs., Nov. 30:
Lecture 20: 5.3
HW20 (due 12/6, 10:00pm): 5.3: 1,2,3,4,5,6

Here is attendance quiz 20 and here are the Solutions to attendance quiz 20
Mon., Dec. 4:
Lecture 21: 5.4 (part I)
HW21 (due 12/10, 10:00pm): new due date: 12/14, 10:00pm): homework for Lecture 21 Answers to homework for Lecture 21

Here is attendance quiz 21 and here are the [ Solutions ]
[but the last sentence of p.1 should be "but the flow-out is simply the sum of the corresponding row, and the flow-in is simply the sum of the corresponding volumn]

[We will also use Chapter 7 (pp. 61-70) of the excellent book A Course in Combinatorics by J. H. van Lint and R. M. Wilson.]
Recommended reading: D.R. Fulkerson's Feb. 1966 American Monthly paper, that won the prestigious Lester R. Ford award for 1967.
(BTW, the award is named after L.R. Ford, Sr., the father of the Ford from Fulkerson-Ford).
(BTW, another paper, that also won the Lester R. Ford award, but for 1990, is this gem .)
Thurs., Dec. 7:
Lecture 22: 5.4(part II)
real quiz 11 (on Lecture 20) [Optional to people who took all the quizzes (I will drop the lowest quiz grade); Make up for those who missed at least one quiz] average=7.86 (out of 8)
Here is Real quiz 11 and here are the solutions to Real quiz 11 (thanks to Hudson Yan)
Here is attendance quiz 22 and here are the Solutions to attendance quiz 22
HW22 (due 12/10, 10:00pm; new due date: 12/14, 10:00pm): 5.4: 3,4,5,6,7. For 3,4,5,6 do not use the labeling algorithm (that is just distracting for humans), but instead use the "keep looking for augmenting paths" until you can't find any more. Also, for each of problems 3,4,5,6, show a minimal cut .
Mon., Dec. 11: Review . Here is the problem and solution of today's attendance quiz (thanks to Tomas Spero)
Sunday, Dec. 17 : 10:00am-1:00pm: Optional (but strongly recommended) for everyone but Mandatory for members of SCCI, members of SCCII, and of course, to members of both SCCI and SCCII)
recording [Unforunately, about half an hour were not recorded (I forgot to unpause it)]
Final Exam: Thurs., Dec. 21, 2023, 8:00-11:00am IN CLASSROOM (TIL 264)
Here is the Final exam and here are student Justin Tesvalles's almost perfect solutions.
[In two places his answers were replaced by a better version, (due to Alexnadra Maris). Also the answer for 14(c) is correct (namely 3), but the reason is wrong (it does not make sense to add the current flows of all the edges of this augmenting path, the extra net flow is 3 because that what you add to the first egde (coming out of the source, 1)]
[Justin won the "Best Final Exam award, an amazon gift card of $30. Quite a few people got 200, but his neat and clear presenataion was by far the best].

teaching evaluations

Doron Zeilberger's teaching page