1. **Linear Programming (LP)** is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. 2. **Simplex Method** is an algorithm to solve LP problems. It moves from one vertex (corner point) of the feasible region to another, improving the objective function at each step until the optimum is reached. 3. **Two Phase Method** is used when the LP problem does not have an obvious initial feasible solution. Phase 1 finds a feasible solution by minimizing the sum of artificial variables. Phase 2 solves the original problem starting from that feasible solution. 4. **Duality in Linear Programming** states that every LP problem (called the primal) has a corresponding dual problem. The solution to the dual provides bounds on the solution to the primal, and under certain conditions, both have the same optimal value. 5. **Transportation Problem** is a special type of LP that deals with finding the least cost way to transport goods from several suppliers to several consumers while satisfying supply and demand constraints. 6. **Assignment Problem** is a special case of the transportation problem where the goal is to assign tasks to agents at minimum cost or maximum efficiency, with each agent assigned exactly one task. --- ### Example Problems **Simplex Method Example:** Maximize $$Z = 3x_1 + 2x_2$$ subject to $$x_1 + x_2 \leq 4$$ $$x_1 \leq 2$$ $$x_2 \leq 3$$ $$x_1, x_2 \geq 0$$ **Two Phase Method Example:** Minimize $$Z = x_1 + x_2$$ subject to $$x_1 + x_2 = 1$$ $$x_1 - x_2 \geq 1$$ $$x_1, x_2 \geq 0$$ **Duality Example:** Primal: Maximize $$Z = 2x_1 + 3x_2$$ subject to $$x_1 + 2x_2 \leq 6$$ $$3x_1 + 2x_2 \leq 12$$ $$x_1, x_2 \geq 0$$ Dual: Minimize $$W = 6y_1 + 12y_2$$ subject to $$y_1 + 3y_2 \geq 2$$ $$2y_1 + 2y_2 \geq 3$$ $$y_1, y_2 \geq 0$$ **Transportation Problem Example:** Minimize cost of shipping from 2 factories to 3 warehouses with given supply, demand, and cost matrix. **Assignment Problem Example:** Assign 3 jobs to 3 workers minimizing total cost given a cost matrix.