Simplex Algorithm

1. let v be ANY vertex on the feasible region
2. while neighbor $v_0$ has better value $v = v_0$

Vertex and Neighbors

• Every linear inequality defines a halfspace
• Every linear equality defines a hyperplane
• feasible region is specified by the intersection of those : convex polyhedron (볼록 다면체)
• each vertex = unique point which n hyperplanes meet
• neighbor ↔ n-1 hyperplanes in common that is: 1 dimentional line exists

Setting vertex to Origin

아무 점에서 시작하면 된다 → 원점에서 시작하면 깔끔 만약 원점이 vertex가 아니라면? → 좌표이동

현재 점을 u라 하고, u를 정의하는 초평면 $(H_1, …, H_n)$에 대해 임의의 점 $x = (x_1, …, x_n)$을 H에 대한 $y = (y_1, …, y_n)$으로 변환 즉 u가 원점이 되는 것이다

• 각 H가 $a_i \cdot x ≤ b_i$로 만들어졌다면 $y_i = b_i - a_i \cdot x$로 정의하면 된다.
• inequality: $y≥0$
• u is origin in y-space

Implementation of Simplex algorithm

1. Find an Initial Vertex (아직)
   1. if not origin, make it origin
2. Check if current vertex is optimal
   1. Origin is optimal ↔ all $c_j ≤0$ i.e. minimize problem
3. Find a neighbor of current vertex with better objective value
   1. 하나의 1차원 선 위에서 움직이는 것이다 그 선은 하나의 변수에 대해 정의되며, 이를 제외한 변수들에는 unique i.e. $\Sigma a_{ij}x_j ≤ b_i$ become tight except $x_j ≥0$
   2. since $\exist c_j >0$, increase $x_j$ until it hits some other constraint!