Math 364 (Fall 2024): Lecture Notes and Videos on Principles of Optimization
|
Copyright: I (Bala Krishnamoorthy) hold the copyright
for all lecture scribes/notes, documents, and other
materials including videos posted on these course web
pages. These materials might not be used for commercial
purposes without my consent.
|
Scribes from
all lectures so far (as a single big file)
| Lec | Date | Topic(s) | Scribe | Video |
| 1 |
Aug 20 |
syllabus,
optimization in calculus, Dude's Thursday problem, the
system \(A\mathbf{x} = \mathbf{b}\), EROs, basic/non-basic
variables
|
Scb1
|
Vid1
|
| 2 |
Aug 22 |
parametric vector form, matrix multiplication, linear
independence, rank, inverse, general form of Gauss-Jordan
(GJ) method
|
Scb2
|
Vid2
|
| 3 |
Aug 27 |
GJ example, hints on Homework 1, LP formulation,
decision variables (d.v.'s), objective function,
constraints, sign restrictions
|
Scb3
|
Vid3
|
| 4 |
Aug 29 |
second formulation of Jones LP, assumptions of LP, graphical
solution in 2D, feasible region, optimal solution, convex
set
|
Scb4
|
Vid4
|
| 5 |
Sep 3 |
extreme point/vertex of LP, four cases of LP, alternative
optimal solutions, infeasible LP, unbounded LP, a full 2D
example
|
Scb5
|
Vid5
|
| 6 |
Sep 5 |
LP formulation problems: police staffing with shared shifts,
blending: average quality, inventory planning with storage
costs
|
Scb6
|
Vid6
|
| 7 |
Sep 10 |
inventory LP: unified flow balance constraints, computer
leasing problem, introduction to AMPL, model for Farmer
Jones LP
|
Scb7
|
Vid7
|
| 8 |
Sep 12 |
AMPL
session, Farmer Jones LP
using set of crops and # crops, inventory planning LP: all
balance constraints in one line
|
software
|
Vid8
|
| 9 |
Sep 17 |
LP standard form, slack/excess vars, basic solutions, basic
feasible solution (bfs), corner point \(\equiv\) bfs,
bfs of Farmer Jones LP
|
Scb9
|
Vid9
|
| 10 |
Sep 19 |
correspondence of bfs's and corner points, adjacent bfs, steps
of the simplex method for a max LP with \(\leq\) constraints
|
Scb10
|
Vid10
|
| 11 |
Sep 24 |
video lecture: simplex method for max LP, entering
and leaving variables, min-ratio test, pivoting, optimal
bfs, tableau simplex
|
Scb11
|
Vid11
|
| 12 |
Sep 26 |
Zoom lecture: simplex method for min-LP, describing
all alternative optima, unbounded LP, big-M simplex,
artificial variable
|
Scb12
|
Vid12
|
| 13 |
Oct 1 |
detect infeasible LP in big-M simplex, handling unrestricted
in sign (urs) vars: \(x_i \leftarrow x_i^+ - x_i^-\), for
\(x_i^+, x_i^- \geq 0\), full example
|
Scb13
|
Vid13
|
| 14 |
Oct 3 |
Hints for problems from Homework 6, review for
midterm exam: problems from the Practice midterm
|
Scb14
|
Vid14
|
| 15 |
Oct 8 |
midterm exam
|
| 16 |
Oct 10 |
more AMPL: Chukee toys LP;
sensitivity analysis in graphical LP, changing obj
fn coefficient of corn \((x_1)\) in Farmer Jones LP
|
Scb16
|
Vid16
|
| 17 |
Oct 15 |
changing coefficient of wheat in objective, changing rhs of
constraint \(b_i \rightarrow b_i + \Delta\), shadow price,
economic interpretation
|
Scb17
|
Vid17
|
| 18 |
Oct 17 |
tableau simplex in Matlab,
simplex method in matrix form, \(\mathbf{x}^T =
[\mathbf{x}_B^T~~\mathbf{x}_N^T ]\), optimal
\(\mathbf{x}_B = B^{-1}\mathbf{b}\), optimal \(z^* =
\mathbf{c}_B^T B^{-1}\mathbf{b}\)
|
Scb18
|
Vid18
|
| 19 |
Oct 22 |
optimal tableau from \(B\), sensitivity analysis in matrix
form: changing \(c_j\) of nonbasic \(x_j\), reduced cost,
changing \(c_j\) of basic \(x_j\)
|
Scb19
|
Vid19
|
| 20 |
Oct 24 |
\(b_i \rightarrow b_i + \Delta\), new \(\mathbf{x}_B =\) old
\(\mathbf{x}_B + \Delta [B^{-1}]_{\cdot i}\), shadow price,
changing \(c_j\) and \(A_{ij}\) for nonbasic (or new) \(x_j\)
simultaneously
|
Scb20
|
Vid20
|
| 21 |
Oct 29 |
hints for Hw 8, LP duality,
normal constraints/variables, dual of normal max LP,
primal-dual relations, motivation for the dual
|
Scb21
|
Vid21
|
| 22 |
Oct 31 |
economic interpretation of Farmer Jones and Gaseous
Chemicals LPs (Hw2), duality in matrix
form, weak and stroing duality
|
Scb22
|
Vid22
|
| 23 |
Nov 5 |
dual theorem: \(\mathbf{y}^T = \mathbf{c}_B^T B^{-1}\) is
optimal for (D), read off optimal
dual solution (Jones LP), shadow price\(_i =
y_i\), AMPL session
|
Scb23
|
Vid23
|
| 24 |
Nov 7 |
video lecture: complementary slackness conditions
(CSCs) as primal-dual optimality conditions, using CSCs to
solve LPs
|
Scb24
|
Vid24
|
| 25 |
Nov 12 |
on Project, AMPL
data from text file, integer programming (IP),
IP formulation: basketball starting line-up, if-then
constaints
|
Scb25
|
Vid25
|
| 26 |
Nov 14 |
fixed charge MIP, forcing
constraint, AMPL
session, general either-or constraint, OR vs XOR,
modeling more than two options
|
Scb26
|
Vid26
|
| 27 |
Nov 19 |
video lecture: more on Project, general if-then
statement, \(A \Rightarrow B ~\equiv~ \mbox{not} A
~\mbox{OR}~ B\), warehouse location MIP
|
Scb27
|
Vid27
|
| 28 |
Nov 21 |
video lecture: modeling general either-or and general
if-then statements using extra binary variables
|
Scb28
|
Vid28
|
| 29 |
Dec 3 |
problems from Homework 8, review
of practice final exam
|
Scb29
|
Vid29
|
| 30 |
Dec 5 |
more review
of practice
final exam
|
Scb30
|
Vid30
|
Last modified: Thu Apr 24 18:31:37 PDT 2025
|