1. “Fresh and tasty” bakers make cakes and pastries.

On a Sunday morning they have to make

‘plum cake” and “fruit pastries”. They have 59 units of flour and they use 5 units of flour per
cake and 4 units per pastry. They also have 46 units of time in the oven that day and each
cake requires 4 units in the oven and each pastry requires 3 units of time in the oven. They
sell each cake for Rs 32 and each pastry for Rs 25. How many cakes and pastries they should
make to maximize their sale?

SOLUTION:

We first create a mathematical model and then solve the model to find out the number of
cakes and pastries the baker should make.
The baker has to decide the number of cakes and pastries to make. Let us define X as the
number of cakes made and Y as the number of pastries made.

Since they sell a cake for Rs 32 and a pastry for Rs 25, their revenue (if they can sell all the
cakes and pastries made) is Rs 32X + 25Y. Since they wish to maximize the revenue, they
want X and Y to

The mathematical model is to determine X and Y to

Maximize 32X+25Y
Subject to
5X+4Y59

4X+3Y46

X,Y0.

TERMINOLOGY

In the model we used variable names X and Y to denote the number of cakes and pastries
made. These are the variables that represent the decisions in the problem. They are called
decision variables.

The purpose of the model is to find out the values of the decision variables such that the
function 32X + 25Y is as large as possible. In other words, the objective is to find out X and
Y that maximizes 32X + 25Y (or makes it as large as possible). The function 32X + 25Y is
called the objective function because it represents the objective of the model which is to
maximize it.

The conditions or limitations that restrict the values that the decision variables can take are
called the constraints. We have two constraints that are5X+4Y59and4X+3Y 46.

There is an additional condition that the decision variables should be non negative. These are
called non negativity restriction so the decision variables. These are the conditions X ,Y 0.

LINEAR PROGRAMMING MODEL

Our modeling process was carried out in the following steps:

 1. Identify the decision variables.
2. Write the objective function (as a function of one or more decision variables). The
objective either maximizes or minimizes the function.
3. Write the constraints (the left hand side is a function of one or more decision variables
and the right hand side is usually a known constant). The sign of the inequality that
relates the left hand side (LHS) and the right hand side (RHS) is usually a ≤, ≥ or =.
4. Write the non negativity restrictions on the decision variables

We followed steps 1 to 4 in our formulation. We also observe that we have modeled the
objective function as a linear function of the decision variables. Both the constraints are linear
inequalities. Our model is a Linear Programming (LP) model because both the objective
function and the constraints are linear functions of the decision variables.

ASSUMPTIONS IN LINEAR PROGRAMMING(LP)

1. Additivity–the total revenue is the sum of there venues generated by the sale of cakes
and pastries.
2. Proportionality (or multiplicity): If each cake fetches revenue of Rs 32, X cakes fetch
a revenue of 32X.
3. Divisibility– If each cake fetches revenue of Rs 32, making half a cake is allowed and
it fetches revenue of 16.
4. Deterministic–All the values and coefficients are known in advance with certainty.

USUAL NOTATION

Since we had two decision variables, we can use X and Y to represent them. If we have a
large bakery that makes 40 products (say), we would be at a loss to define notation for these.
It is therefore customary to use X1to Xn if we have n products. We therefore use X1and X2 to
represent the decision variables in our case. Sometimes Xij and Xijk are used to represent the
decision variables depending on the situation.

Our final LP model for the baker’s problem is

Maximize32X1+25X2
Subject to
5X 1 +4X259
4X1+3X2 46
X1,X20.
SOLUTION–GRAPHICAL METHOD

Let us try to solve the baker’s LP problem given below:

Maximize 32X1+25X2
Subject to
5X 1 +4X259
4X1+3X2 46
X1,X20.

The shaded region shows the set of points that satisfy both the inequalities. The shaded
portion represents the feasible region where every point in the feasible region satisfies all the
constraints including the non-negativity restrictions). A point (or solution) is a feasible
solution if it satisfies all the constraints. Examples of feasible solutions are (0, 0), (8, 4), (11,
0), (0, 14.75) etc. (An important issue arises here. We have defined X2 as the number of
pastries to be made. Can X2 take a value 14.75? Can we make a fractional number of
pastries? Should X2 be an integer?
At present we have assumed X1 and X2 to be continuous variables and we have not placed an
explicit integer restriction on X1 and X2. We therefore do not restrict them to be integers.
Restricting them to be integers leads us to a different class of problems called Integer
programming problems and we will learn about them later.

As far as LP is concerned, we assume that all variables are continuous and can take fractional
values. We worry about the implementation aspects after we solve the LP).

Since very feasible solution satisfies all the constraints (including the non negativity) we can
implement all of the solutions (From now on, if we say that a solution satisfies all the
constraints, we include the non negativity restrictions as well). We obviously want the final
solution to be implementable and therefore it has to be feasible. It is the feasible solution that
has the highest value of 32X1 + 25X2(the objective function).
 1
6

1
2

(0,14.75)
Z=368. 8

(7,6)
Z=3
4

(0,0) Z=0 4 8 (11.5,0) 12 Z=36 16

Let us evaluate the objective function value for the feasible solutions. Let Z denote the value
of the objective function for the feasible solutions. shows the values.

Feasible solutions

No. Solution Objective

function
1 (0,0) 0
2 (8,4) 356
3 (11,0) 352
4 (0,14.75) 368.75

Among the four solutions we would choose (0, 14.75) because it has the highest value of the
objective function. We also wish to find out if we can have a solution with higher value of the
objective function.

Let us consider the solution (0,15). This has an objective function value of 375 but violates
The constraint 5X 1 +4X259.We do not consider this solution because it is in feasible and
Violates a constraint.

Letusconsiderthesolution(16,-6).Thissatisfiesboththeconstraints5X 1 +4X259and 4X1+3X246.

It has an objective function value of 362. It is not considered because it violates the non
negativity restriction.

We therefore know that the best solution is a feasible solution with the best possible
(highest) value of the objective function.

Let us consider the solution (8, 4). This solution is feasible because it is inside the feasible
region. The objective function value is 356. We can fix X1 = 8 and increase X2 by moving to
the right of this point till we reach the point (8,4.666) to get an objective function value of
372.67. We can fix X2 = 4 and increase X1 by moving above this point till we reach the point
(8.5, 4) to get an objective function value of 372.
We could generalize and say that for every point inside the feasible region, it is possible to
move to the right (left) or move above (below) depending on the nature of the objective
function (maximize or minimize) or the sign of the coefficients (positive or negative) and
obtain a point on the boundary of the feasible region with a better value of the objective
function.

We can also generalize that the best solution is a point that lies on the boundary of the
feasible region.

Let us consider the point (8, 4.666)with an objective function valueof372.67. This point lies
ontheline4X1+3X2=46.Theslopeofthislineis0.75.Theslopeoftheobjectivefunction
line is 25/32 = 0.78. Since the slope of the objective line is higher we can increase X 2 to get
pointsthatsatisfy4X1+3X2=46and5X 1 +4X259. This can increase X2to 6 and bring down X1to 7
to get the point (7,6) with an objective function value of 374. Here 5X1 + 3X2
becomesequalto59.IncreasingX2furtherandretaining4X1+3X2=46wouldviolate
5X 1 +4X259.The best solution is (7,6) with Z=374.
 The best solution is called the optimal solution or optimum solution and is a corner point
solution in the feasible region.

Therefore it is enough if we determine the corner points and compute the objective function
at

Corner point solutions

No. Solution Objective

function
1 (0,0) 0
2 (0,14.75) 368.75
3 (11.5,0) 368
4 (7,6) 374

The best among the corner point solutions is (7,6) with Z = 374. This is the optimum solution.

Another way to get to the optimal solution is to draw iso revenue lines. The objective
function is 32X1+ 25X2. Draw a line 32X1+ 25X2= 200 and 32X1+ 25X2= 300. The second
line shows that every point in the feasible region as well as in the line 32X1 + 25X2 = 300 has
an objective function value of 300.Since we want to get a feasible point that maximizes
32X1+ 25X2, we draw revenue lines by increasing the value (draw lines parallel to 32X1 +
25X2 = 300) till it just touches the last point in the feasible region. This will be a corner point
(if the slope of the objective function is different from the slopes of the constraints). In our
example it is the corner point (7, 6) with Z* = 374. (We use Z* to denote the objective
function value at the optimum).
STEPSINTHEGRAPHICAL METHOD

1. Draw the constraints and obtain the feasible region.

2. Identify the corner points of the feasible region.
3. Evaluatetheobjectivefunctionatthecornerpointsandidentifytheoptimumsolution.
The reader should note that the graphical method works extremely well when we have two
decision variables. When the number of decision variables increases, it becomes difficult to
use the graphical method to get the optimum solution. We use the Simplex algorithm to solve
LP problems with more than 2 variables. Several solvers are available and the most popular
among them is the solver available as an add on to Microsoft excel.

2. Maximization 10 X1 + 9 X2

Subject to

3 X1 + 3 X2 ≤ 21

4 X1 + 3 X2 ≤ 24

X1 , X2 ≥ 0
Sol:

No. Solution Objective

function
1 (0,0) 0
2 (6,0) 60
3 (0,7) 63
4 (3,4) 66

Graphical Method (Maximization)

(0,8) 4x1 + 3x2 = 24

( 0, 7)
Z = 63

( 3, 4 ) Z= 66
(Feasible Region)
3x1 + 3 x2 = 21
( 0, 0 ) Z= 0 ( 6, 0) Z= 60 (7,0)

Objective Function Lines touch last at ( 3, 4)

Note: For every Z value represents a straight Line ( 3, 4) is the Optimum Solution

Evaluate corner points

Four corner points

For (0,0) the objective function value Z = 0

For (6,0) the objective function value Z = 60

For (0,7) the objective function value Z = 63

For (3,4) the objective function value Z = 66 Optimum solution

3. Minimize 7 X1 + 5 X2

Subject to

X1 + X2 ≥ 4

5 X1 + 2X2 ≥ 10

X1 , X2 ≥ 0
Sol:

No. Solution Objective

function
1 (0,0) 0
2 (0,5) 25
3 (0,4) 28
4 (2/3,10/3) 21.33

Graphical Method (Minimize)

X2

( 0 , 5)

(0,4)
( 2/3 , 10/3)
(Feasible Region)

( 0, 0) (2,0 ) (4, 0) X1
Feasible region has 3 corner points, the first corner point is given here which is (4, 0), the o

ther corner point is (0, 5). For (4, 0) we evaluate the objective function and the objective
function value is given as Z = 28.

The next corner point is (0, 5) which is here and when we evaluate the objective function
7X1+5X2 we get Z = 25, (7 x 0)+(5 x 5) = 25.

We now look at the third corner point which is (2/3, 10/3), now this (2/3, 10/3) can be found in
the graph, if we draw this graph to scale and we draw the graph correctly as we have attempted
to do, now you realize that this point has an X coordinate of 2/3 and has a Y coordinate of 10/3.

This point is (2/3, 10/3), for objective function value we substitute:

7 (2/3) + 10(5/3) which is (50/3),

(14/3)+(50/)3 is (64/3)

Now we have (64/3) which is Z= 21.33 for the other corner point which is (2/3, 10/3).

Therefore, the optimum solution to this minimization problem is that corner point which has the
smallest value of the objective function and out of these 3 we realize that the point (2/3,10/3)
with (64/3) has the smallest value and therefore, is the optimum solution. This point is the
optimum solution with value (64/3), like we did for the maximization problem we can also draw
what are called is objective function lines, where we fix 7X1+5X2 to a constant.

The last feasible point is given by (2/3, 10/3), which is the optimum solution to the
minimization problem. This is how we solve we solve minimization problems using the
graphical method. Now, the only difference between the maximization and the minimization is
many times it will happen that in a minimization problem, the feasible region will not be
bounded as in this case. Even though, we have shown a certain portion of the feasible region one
would realize that a point here, a point here is also feasible and a feasible region is not bounded
or it is not a closed region whereas, in a maximization problem many times we would get a
feasible region, that is a closed region. That is one of the things that we need to understand, the
other most important thing where the reason for which we evaluate only the corner points is that
we have shown that every point inside the region, there will be a corner point which will have a
better value of the objective function. Now, that is happened due to what is called the convexity
property of the feasible region, if we take two points in the feasible region and join them by a
line, we will realize that all the points in the line will lie in the feasible region. And because this
feasible region is convex, we can easily show that for every point inside the feasible region there
is always a point on the boundary, there is always a point on the boundary and then there is
always a corner point which has a better value of the objective function. These are the basic
ideas and principles that we use to solve the linear programming problem using the graphical
method. While the graphical method is simple and easily understandable we are limited by the
fact that we can only represent two variables in the graphical method the X1 and X2.

4. For Maximize 10X1 + 9X2 Subject to X1 - X2 ≤ 5 , 4X1 ≤ 24 ; X1 , X2 ≥ 0

Sol:

No. Solution Objective

function
1 (0,0) 0
2 (5,0) 50
3 (6,0) 60
4 (6,1 ) 69
``

Unbounded

X2 ( Feasible region ) 4X1 = 24

(6,1)

Objective Function Line

(0 , 0) ( 5, 0 ) (6 , 0) X1
X1 – X2 =5

5. For Maximize 10X1 + 9X2 Subject to X1 + X2 ≤ 5; 4X1 ≥ 24 ; X1 , X2 ≥ 0

Sol:

No. Solution Objective

function
1 (0,0) 0
2 (5,0) 50
3 (0,5) 45
4 (6,0) 60

``` Infeasibility
UnboudednessgrasrsEzdvxdgsdg

(0, 5)

X2 4X1 = 24

Vjjgfvjg fjgjgfjfgjjbdfhfdh

X1 + X2 =5 ( Feasible Region)

( Feasible Region )

(0 , 0) ( 5, 0 ) (6 , 0) X1

There is no region that satisfies both the constraints. This LP is infeasible.

 6. Solve the LP
Maximize 7 X1 + 5X 2
Subject to
X1 − 2 X 2  12

2 X1  8

X1 , X 2  0

Sol:
No. Solution Objective
function
1 (0,0) 0
2 (4,0) 28
3 (12,0) ----
4 (4,4) 48

LPs formulated from practical situations should not be unbounded. Usually when
an LP problem terminates with an unbounded solution, we should check the sign
of the coefficients in the constraints. If the problem is formulated out of a practical
situation, it is likely that during the formulation the sign of one of the coefficients
has been typed wrongly.

If we correct the first constraint to X1 + 2X2 ≤ 12 then we get the solution for the
problem we get Z= 48.
16

12

4 (4,0) 8 12 16
(0,0 Z=0
Z=28 (12,0)
7. Solve the LP - Maximize 7 X1 + 5X 2
Subject to 2 X1 + 2 X 2  8
X1 + X 2  5

X1 , X 2  0

We observe that the second constraint is violated when the solver terminated the solution of
the problem. This situation is called infeasibility. The given LP is infeasible.

The graph corresponding to the constraints is shown. From the graph it is observed that there
is no feasible region.

LPs formulated from existing situations should not be infeasible. Usually when an LP
problem terminates with infeasibility, we should check the sign of the inequalities in the
constraints. If the problem is formulated out of a practical situation, it is likely that during the
formulation the sign of one of the inequalities has been typed wrongly.

Changing the second constraint to X1 + X 2  5 we get the optimal solution X1 = 4 with Z =

28.

If we observe that the sign of the inequalities are correct and there is no mistake during the
entry, it is likely that some values in the RHS have been overstated or understated. If we
change the RHS of the first constraint to 18, the optimum solution is X1 = 9 with Z = 63.
 8

2 4 6 8
Figure 1.3 – Graph for the constraints in Illustration 1.10

If we are convinced that there is no change in the sign of the inequalities and in the RHS
values, it finally means that we are trying to formulate a situation that cannot be implemented
or achieved.

Based on the above examples we generalize that

Every LP problem results either in an optimum solution or is unbounded or is infeasible.

INSTALLING THE SOLVER INTO MICROSOFT EXCEL

The following steps help us in installing the solver into Microsoft excel screen:

1. Go to the Windows icon, the top leftmost icon in MS Excel

2. Click on excel options
3. Go to add in (on the left side of the new screen)
4. Choose solver add in and click on the GO button
5. It will install the solver.
6. If you click on Data from the main excel page, you can see the solver icon on the right
hand side.
7. Now you are ready to solve LPs using this solver.