Formulation of linear programming problems ( L PP

Formulation of Linear Programming Problems (LPP)

Formulating an LPP involves translating a word problem into mathematical inequalities or equalities. Key components include:

1. Decision Variables
2. Objective Function
3. Constraints
4. Non-Negativity Constraints

a. Decision Variables

These are variables (e.g., x, y) representing the quantities to be determined.

b. Objective Function

This is a linear function used to find the minimum or maximum value. It's in the form:

$$f(x, y) = ax + by$$

where a and b are constants.

c. Constraints

These are linear inequalities defining limitations. They arise from limited resources, obligations, or physical laws. Inequality signs used are ≤, ≥, <, and >.

Common words representing inequality symbols:

Word	Inequality Symbol
Greatest value, maximum value, at most, not more than	≤
Lowest value, minimum value, at least, not less than	≥

d. Non-Negativity Constraints

These are inequalities x ≥ 0 and y ≥ 0. Decision variables cannot be negative (e.g., you can't have negative quantities of items or resources).

Examples

Example 1: Food mixture problem

A cook wants to mix two types of food, $F_1$ and $F_2$, to create a mixture containing at least 8 units of vitamin A and 11 units of vitamin B. $F_1$ costs Tsh 600/kg and contains 3 units/kg of vitamin A and 5 units/kg of vitamin B. $F_2$ costs Tsh 800/kg and contains 4 units/kg of vitamin A and 2 units/kg of vitamin B. Formulate an LPP to minimize the cost.

Vitamin Content	Food $F_1$ (units/kg)	Food $F_2$ (units/kg)	Minimum Requirement
Vitamin A	3	4	8
Vitamin B	5	2	11
Cost (Tsh/kg)	600	800

Solution:

1. Decision Variables: Let x be the kg of $F_1$ and y be the kg of $F_2$.
2. Constraints:
   • Vitamin A: $3x + 4y \ge 8$
   • Vitamin B: $5x + 2y \ge 11$
3. Objective Function (Minimize Cost): $f(x, y) = 600x + 800y$
4. Non-Negativity Constraints: $x \ge 0, \quad y \ge 0$

The LPP is:

Minimize: $f(x, y) = 600x + 800y$

Subject to:

$$\begin{cases} 3x + 4y \ge 8 \\ 5x + 2y \ge 11 \\ x \ge 0 \\ y \ge 0 \end{cases}$$

Example 2: Furniture company problem

A furniture company produces tables and chairs. Each table takes 4 hours of carpentry and 2 hours of painting. Each chair takes 3 hours of carpentry and 1 hour of painting. 240 hours of carpentry and 100 hours of painting time are available. Each table yields a profit of Tsh 70,000 and each chair yields a profit of Tsh 50,000. Formulate an LPP to maximize profit.

Department	Tables	Chairs	Available Hours
Carpentry	4	3	240
Painting	2	1	100
Profit (Tsh)	70,000	50,000

Solution:

1. Decision Variables: Let x be the number of tables and y be the number of chairs.
2. Constraints:
   • Carpentry: $4x + 3y \le 240$
   • Painting: $2x + y \le 100$
3. Objective Function (Maximize Profit): $P(x, y) = 70000x + 50000y$
4. Non-Negativity Constraints: $x \ge 0, \quad y \ge 0$

The LPP is:

Maximize: $P(x, y) = 70000x + 50000y$

Subject to:

$$\begin{cases} 4x + 3y \le 240 \\ 2x + y \le 100 \\ x \ge 0 \\ y \ge 0 \end{cases}$$