Linear Programming Problems Formulation

Steps in formulating a linear programming problem.

1. Read the problem several times and assess what is known and what is to be determined.
2. Identify the unknown quantities and assign variables to them, be careful about the units.
3. Determine the objective function; it involves the quantity to be maximized or minimized.
4. Translate the constraints into linear inequalities. Constraints are limitations or restrictions to the problem; for each constraint the units must be the same.
5. Graph the constraints and find the feasible solution.
6. Find the corner points of the feasible solution. These are points of intersection of the graph.
7. Evaluate the objective function. The highest value of the objective function has to be maximized or smallest value to be minimized.

Example

In a big organization, decisions about distribution in order to realize maximum profit or reduce costs of production are done by use of linear programming.

Limitations/constraints are translated by linear inequalities.

Greatest value or least value will be expressed as a function (called the objective function).

Drawing of linear inequalities

Example 01

Draw and show the half plane represented by $8x + 2y \geq 16$

Solution

For $8x + 2y \geq 16$; draw $8x + 2y = 16$

For x-intercept, $y = 0$

$8x = 16$

$x = 2$

For y-intercept, $x = 0$

$2y = 16$

$y = 8$

Using (0, 0) as a test point

$8(0) + 2(0) \geq 16$

$0 \geq 16$ (False)

Example 02

Determine the solution set of the simultaneous inequalities

$x + y \geq 3$

$x - 2y \leq 9$

Solution

$x + y \geq 3$ draw $x + y = 3$ (full line)

$x + y = 3$

At x-intercept $y = 0$ at y-intercept $x = 0$

$x = 3$ $y = 3$

For $x - 2y \leq 9$, $x - 2y = 9$

At x-intercept $y = 0$ at y-intercept, $x = 0$

$x = 9$ $-2y = 9$

$y = -4.5$

Using (0, 0) as a test point

$x + y \geq 3$: $0 + 0 \geq 3$, $0 \geq 3$ (F)

$x - 2y \leq 9$: $0 - (2)(0) \leq 9$, $0 \leq 9$ (T)

• The clear part is the solution set
• The solution set is called the feasible region

Example

Find the maximum and minimum value of $c = 4x + 3y + 38$ subjected to

$x + y \geq 5$

$0 \leq y \leq 6$

$0 \leq x \leq 5$

$x \geq 0, y \geq 0$

Solution

For $x + y \geq 5$

$x + y = 5$

When $x = 0, y = 5$

$y = 0, x = 5$

For $0 \leq y \leq 6$

$y = 0$ and $y = 6$

Line $y = 6$

For $0 \leq x \leq 5$

$x = 0$ and $x = 5$

Line $x = 5$

Test points: $x \geq 0$, shade left of $x = 0$; $y \geq 0$, shade above the x-axis

Corner points	C = 4x + 3y + 38
A (5, 0)	4(5) + 3(0) + 38 = 58
B (5, 6)	4(5) + 3(6) + 38 = 76
C (0, 6)	4(0) + 3(6) + 38 = 56
D (0, 5)	4(0) + 3(5) + 38 = 53

Therefore, the maximum value of $c = 76$ and occurs at (5, 6).

The minimum value of $c = 53$ and occurs at (0, 5).

Example

Find the maximum and minimum values of the given functions and the value of x and y where they occur.

(i) $Z = 4x + 3y$

Subject to

$x + 2y \leq 10$

$3x + y \leq 5$

$x \geq 0, y \geq 0$

(ii) $P = 134x + 20y$

Subject to

$x + y \leq 160$

$10 \leq x \leq 60$

$0 \leq y \leq 120$

(iii) $T = 4x + 7y$

Subject to

$x + y \leq 18$

$5 \leq x \leq 10$

$3 \leq y \leq 10$

$x \geq 0, y \geq 0$

(iv) $P = 2x + 4y$

Subject to

$2x + 3y \geq 3$

$-5x + 4y \leq 0$

$3x + 4y \leq 18$

$x \geq 0, y \geq 0$