Lesson 5: Optimization via Linear Programming

Linear programming is an optimization technique used to allocate scarce resources to maximize an objective (such as profit) or minimize an objective (such as cost). The problem must be modeled using linear equations and inequalities.

Core Components of an LP Model

• Decision Variables: Unknown values ($x_1, x_2, \dots$) that represent the quantities to be determined to solve the optimization problem.
• Objective Function: A linear equation that defines the primary goal to be maximized or minimized.
• Structural Constraints: A set of linear inequalities that define the limits, resource caps, or performance requirements of the system.
• Non-Negativity Restrictions: Mathematical constraints ensuring that decision variables cannot take on negative values ($x_i \ge 0$).

For linear programming models with two decision variables, the optimal solution can be found by graphing the system of inequalities on a two-dimensional plane.

Step-by-Step Graphical Process

1. Graph the Boundary Lines: Convert each constraint inequality into a linear equation and plot its line on the coordinate plane.
2. Identify the Feasible Region: Use test points (such as the origin $(0,0)$) to determine which side of each line satisfies the inequality constraint. The intersection of all satisfying regions forms the feasible region.
3. Locate the Corner Points (Vertices): Find the exact coordinates of the intersection points that form the boundaries of the feasible region.
4. Evaluate the Objective Function: Calculate the value of the objective function at each corner point. According to fundamental LP theory, if an optimal solution exists, it must occur at one of these vertices.

         x2 ^
            |       \ Line 1
            |----\   \
            |     \   \
            | Feasible \
            |  Region   \
            |___________ \______>
            0           Corner Points occur at vertices