Linear Programming

Linear programming (LP) is a mathematical technique for finding the maximum or minimum value of a linear objective function of several variables, subject to linear constraints (equations or inequalities) and non-negativity conditions. It is used in production planning, resource allocation, diet and transportation problems.

Terminologies

• Decision variables: the unknowns ($x, y, z$) to be determined.
• Objective function: the linear function to be optimised, here $P = x + 2y + z$.
• Constraints: linear restrictions on the variables, here $x+y+2z\le 10$ and $2x+3y+z\le 12$.
• Non-negativity restrictions: $x,y,z\ge 0$.
• Feasible solution / feasible region: a solution satisfying all constraints / the set of all such solutions.
• Optimal solution: the feasible solution giving the best value of the objective function.
• Slack variable: a non-negative variable added to a "$\le$" constraint to turn it into an equation.
• Basic variables: the variables that are non-zero in a basic feasible solution (their columns form an identity matrix); non-basic variables are set to zero.

Solution by simplex method

Add slack variables $S_1, S_2\ge 0$:

$x+y+2z+S_1=10,\qquad 2x+3y+z+S_2=12,\qquad P-x-2y-z=0$

Initial table

Most negative $C_j-Z_j=-2$, so $y$ enters; minimum ratio $4$, so $S_2$ leaves (pivot $=3$).

Iteration 1 ($R_2\to R_2/3$, $R_1\to R_1-R_2$, objective row $\to$ row $+2R_2$)

The only negative entry is $-1/3$ under $z$, so $z$ enters. The minimum ratio is $18/5$, so $S_1$ leaves (pivot $=5/3$).

Iteration 2 ($R_1\to \tfrac35R_1$, $R_2\to R_2-\tfrac13R_1$, objective row $\to$ row $+\tfrac13R_1$)

All entries of the objective row are $\ge 0$, so the solution is optimal.

Result

$x=0,\quad y=\frac{14}{5},\quad z=\frac{18}{5},\quad P_{\max}=2\cdot\frac{14}{5}+\frac{18}{5}=\frac{46}{5}=9.2$

Check: $x+y+2z=\frac{14}{5}+\frac{36}{5}=10$ and $2x+3y+z=\frac{42}{5}+\frac{18}{5}=12$, so both constraints are satisfied (both resources fully used).