Home

Linear Programming

A linear programming problem may be defined as the problem of maximizing or minimizing a linear function subject to system of linear constraints. The constraints may be equalities or inequalities. The linear function is called the objective function , of the form $f (x, y) = a x + b y + c$ . The solution set of the system of inequalities is the set of possible or feasible solution , which are of the form $(x, y)$ .

If a linear programming problem can be optimized, an optimal value will occur at one of the vertices of the region representing the set of feasible solutions.

Math diagram

For example, the maximum or minimum value of $f (x, y) = a x + b y + c$ over the set of feasible solutions graphed occurs at point $A, B, C, D, E$ or $F$ .

When the graph of a system of inequalities forms a region that is closed, the region is said to be bounded. Sometimes a system of inequalities forms a region that is open. In this case, the region is called unbounded.

To solve a linear programming problem, follow these steps.

$•$ Graph the region corresponding to the solution of the system of constraints.

$•$ Find the coordinates of the vertices of the region formed.

$•$ Evaluate the objective function at each vertex to determine which $x$ - and $y$ -values, if any, maximize or minimize the function.

Example:

Find the minimum value and maximum value of the objective function $f (x, y) = 4 x + 5 y$ , subject to the following constraints.

${\begin{cases} x \geq 0 \\ y \geq 0 \\ x + y \leq 6 \end{cases}$

Solution

First graph the region corresponding to the solution of the system of constraints.

Math diagram

Now find the coordinates of the vertices of the region formed.

The vertices are $(0, 0)$ , $(0, 6)$ , and $(6, 0)$ .

Evaluate the objective function at each vertex.

At $(0, 0) : f (0, 0) = 4 (0) + 5 (0) = 0$ , Minimum value of $f (x, y)$

At $(0, 6) : f (0, 6) = 4 (0) + 5 (6) = 30$ , Maximum value of $f (x, y)$

At $(6, 0) : f (6, 0) = 4 (6) + 5 (0) = 24$

So, the maximum value of $f$ is $30$ when $x = 0$ and $y = 6$ . The minimum value of $f$ is $0$ when $x = 0$ and $y = 0$ .