**LINEAR PROGRAMMING**

A. Overview

A.1 An Optimisation Problem

A problem which seeks to maximize or minimize a function is called an optimisation problem. An optimisation problem may involve maximisation of profit, production etc or minimisation of cost, from available resources etc.

A.2 A Linear Programming Problem (LPP)

A linear programming problem deals with the optimisation (maximisationl minimisation) of a **linear function** of two variables (say *x* and *y*) known as objective function subject to the conditions that the variables are non—negative and satisfy a set of linear inequalities (called **linear constraints**). A linear programming problem is a special type of optimisation problem.

A.3 Objective Function

Linear function *Z=a⋅x+b⋅y*, where a and b are constants, which has to be maximized or minimized is called a linear objective function.

A.4 Decision Variables

In the objective function *Z=a⋅x+b⋅y*, *x* and *y* are called decision variables.

A.5 Constraints

The linear inequalities or restrictions on the variables of an LPP are called constraints. The conditions *x*≥0, *y*≥0 are called non—negative constraints.

A.6 Feasible Region

The common region determined by all the constraints including non—negative constraints *x*≥0, *y*≥0 of an LPP is called the feasible region for the problem.

A.7 Feasible Solutions

Points within and on the boundary of the feasible region for an LPP represent feasible solutions.

A.8 Infeasible Solutions

Any Point outside feasible region is called an infeasible solution.

A.9 Optimal (feasible) Solution

Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an optimal solution.

Following theorems are fundamental in solving LPPs.

A.10 Theorem 1

Let R be the feasible region (convex polygon) for an LPP and let *Z=a⋅x+b⋅y* be the objective function. When *Z* has an optimal value (maximum or minimum), where *x* and *y* are subject to constraints described by linear inequalities, this optimal value must occur at a comer point (vertex) of the feasible region.

Theorem 2

Let R be the feasible region for a LPP and let *Z=a⋅x+b⋅y* be the objective function. If R is bounded, then the objective function *Z* has both a maximum and a minimum value on R and each of these occur at a corner point of R.

If the feasible region R is **unbounded**, then a maximum or a minimum value of the objective function may or may not exist. However, if it exits, it must occur at a corner point of R.

A.11 Corner point method for solving a LPP

The method comprises of the following steps:

(1) Find the feasible region of the LPP and determine its corner points (vertices) either by inspection or by solving the two equations of the lines intersecting at that point.

(2) Evaluate the objective function *Z=a⋅x+b⋅y* at each corner point. Let *M* and *m*, respectively denote the largest and the smallest values of *Z*.

(3) (i) When the feasible region is __bounded__, *M* and *m* are, respectively, the maximum and minimum values of *Z*.

(ii) In case, the feasible region is __unbounded__.

(a) *M* is the maximum value of *Z*, if the open half plane determined by *a x+by>M* has no point in common with the feasible region. Otherwise,

*Z*has no maximum value.

(b) Similarly, *m* is the minimum of *Z*, if the open half plane determined by *a x+by has no point in common with the feasible region. Otherwise, Z has no minimum value.*

4

16

there are at most 5 packets of cereal available:

The feasible region is shaded on the attached graph paper.

The vertices of the feasible region are as follows:

Point A: (3, 1)

Point B: (4.5, 0)

Point C: (5, 0)

Point D: (0, 5)

The cost at each vertex is as follows:

Point A:

Point B:

Point C:

Point D:

To minimize the objective function select Point A. The minimum possible cost of $24 can be made if 3 packets of Cubi and 1 packets of Dino are sold.

A.12 Multiple optimal points

If two corner points of the feasible region are optimal solutions of the same type, i.e., both produce the same maximum or minimum, then any point on the line segment joining these two points is also an optimal solution of the same type.

B. **Solved Examples**

Ex1. To meet the requirements of a specialised diet a meal is prepared by mixing two types of cereal, Cubi and Dino. The mixture must contain *x* packets of Cubi cereal and *y* packets of Dino cereal. The meal requires at least 15 g of protein and at least 72 g of carbohydrates. Each packet of Cubi cereal contains 4 g of protein and 16 g of carbohydrates. Each packet of Dino cereal contains 3 g of protein and 24 g of carbohydrates. There are at most 5 packets of cereal available.

a) Write down the constraint inequalities.

b) If Cubi cereal costs $6 per packet and Dino cereal also costs $6 per packet, use the graph to determine how many packets of each cereal must be used so that the total cost for the mixture is a minimum.

c) Use the graph to determine how many packets of each cereal must be used so that the total cost for the mixture is a maximum (give all possibilities).

Solution:

a) Information of Ex1 can be displayed in a table and can be simplified as constraints.

a Cubi packet | a Dino packet | at least (g) | |

protein (g) | 4 | 3 | 15 |

carbohydrates (g) | 16 | 24 | 72 |

Constraints:

*x*+3

*y*≥15,

16

*x*+24

*y*≥72… (÷8) or 2

*x*+3

*y*≥6,

there are at most 5 packets of cereal available:

*x*+

*y*≤5.

The feasible region is shaded on the attached graph paper.

b) The objective function can be written as follows:

*P*=(profit per packet of Cubi)×(number of packets of Cubi)

+(profit per packet of Dino)×(number of packets of Dino)

*P*=6

*x*+6

*y*

The vertices of the feasible region are as follows:

Point B: (4.5, 0)

Point C: (5, 0)

Point D: (0, 5)

The cost at each vertex is as follows:

*P*=6(3)+6(1)=24

Point B:

*P*=6(4.5)+6(0)=27

Point C:

*P*=6(5)+6(0)=30

Point D:

*P*=6(0)+6(5)=30

To minimize the objective function select Point A. The minimum possible cost of $24 can be made if 3 packets of Cubi and 1 packets of Dino are sold.

c) To maximize the objective function select Point C, or Point D. The maximum possible cost of $30 can be made if either 5 packets of Cubi and 0 packets of Dino are sold, or 0 packets of Cubi and 5 packets of Dino are sold.

Follow this link for more examples.

👉 Linear Programming: How Can We Maximize and Minimize an Objective Function to the Constraints? 💎

*Embed the link of this post*