```
OPTIMIZATION THEORY
++SIMPLEX METHOD

|
|
|\
| \
|  \
|   \
|-___\__
|     \ ---___________
|      \
+------------------------
/\
Polytope

B+W < 350
2B+W< 600
B+3W< 900

(1947 George Dantzig)
LP (Lin Prog) Solution always @ corner points on Boundary of Polytope
Algebraic Topology - polytope (Feasible region) = "SimpleX"

Simplex Method
1. Find a vertex in polytope & find value  @ this pt
2. Examine each edge attached to this vertex
3. Move alone edge w/ best improvement of criterion
4. Repeat 2-3

Graph Theory (1736 Leonhard Euler)
Nodes
a. Beginning - odd incident degree
b. End - odd incident degree
c. Intermediate Node - even incident degree
.--X--.
/ _/    \
|_/       |
X_________X
|\        |
\ \_      /
\_ \   _/
--X--

Min Cut-Max Flow Theorem
V* = Max steady state flow of s& t (source- sink)
c(P*,~P*) = capacity of minimum cut
-> V* = c(P*,~P*)
cut = node sets P & ~P,  P w/ source node, ~P w/ sink node
Capacity = c(P,~P) = sum of edges w/ one node in P and the other endpt in ~P

__
/  \
->|  |-
/  \__/ \
/    |\   \
/     ||    \
/      \|     \
__ /       __      \  __
/  \       /  \       /  \
|  | ----> |  |       |  |
\__/       \__/       \__/
\       |
\      |
\     \
\    __
\  /  \
->|  |
\__/

Gradient Method/Routing Networks
1. 1931 W. Gropius (SAR/OSR) Housing Block
P=alx/b
A=l(a+b)
I=3x/s
A/P = b(aI+3x) / alx
OSR = bsl/alx = bs/ax = sl/P
SAR -b/x = A/P -  b/x = sl/P = OSR

2. HILL CLIMB
Move in direction of steepest ascent/Gradient
Abraham wald- dynamic programming
3. Network routing (c.1950 R. Bellman)
Optimal value func - minimal cost tour city k to city N
optimal policy func j*(k) next city if at city k
4. Money allocation
principle of optimality

I3(X) = Max return of 3 investments w/ capital \$X
I3(X)=max(0.xc.X)[g3(xc)+I2(X-xc)]
g1(y)=return of investment 1 w/ \$y

``` Home