Introduction to

Operations Research
LEC. 4
Dr. Esmat Mohamed Abdel Moniem El sayed

Misr University for science & Technology

Faculty Of Information Technology

Department of Information Systems

1
Chapter 1- Linear Programming: Model Formulation and
Graphical Solution
Chapter Topics

• Model Formulation

• A Maximization Model Example

• Graphical Solutions of Linear Programming Models

• A Minimization Model Example

• Irregular Types of Linear Programming Models

• Characteristics of Linear Programming Problems

Dr. Esmat Mohamed Abdel Moniem El sayed 2

 Linear Programming - An Overview

• Objectives of business firms frequently include maximizing profit or

minimizing costs.

• Linear programming is an analysis technique in which linear algebraic

relationships represent a firm’s decisions given a business objective
and resource constraints.

• Steps in application:
1- Identify problem as solvable by linear programming.
2- Formulate a mathematical model of the unstructured problem.
3- Solve the model.

Chapter 2 - Linear Programming: Model Formulation and Graphical Solution 3

 Model Components and Formulation

• Decision variables: mathematical symbols representing

levels of activity of a firm.
• Objective function: a linear mathematical relationship
describing an objective of the firm, in terms of decision
variables, that is maximized or minimized
• Constraints: restrictions placed on the firm by the
operating environment stated in linear relationships of the
decision variables.
• Parameters: numerical coefficients and constants used in
the objective function and constraint equations.

Dr. Esmat Mohamed Abdel Moniem El sayed 4

 A Maximization Model Example (1 of 2)

Problem Definition

• Product mix problem - Beaver Creek Pottery Company

• How many bowls and mugs should be produced to
maximize profits given labor and materials constraints?
• Product resource requirements and unit profit:
Resource Requirements
Product Labor Clay Profit
(hr/unit) (lb/unit) ($/unit)
Bowl 1 4 40
Mug 2 3 50

Chapter 2 - Linear Programming: Model Formulation and Graphical Solution 5

 A Maximization Model Example (2 of 2)
Resource availability:
40 hours of labor per day
120 pounds of clay
Descision Variables:
x1=number of bowls to produce/day
x2= number of mugs to produce/day
Objective function
maximize Z = $40x1 + 50x2
where Z= profit per day
Resource Constraints:
1x1 + 2x2  40 hours of labor
4x1 + 3x2  120 pounds of clay
Non-negativity Constraints:
x10; x2  0
Complete Linear Programming Model:
maximize Z=$40x1 + 50x2
subject to
1x1 + 2x2  40
4x2 + 3x2  120
x1, x2  0

Chapter 2 - Linear Programming: Model Formulation and Graphical Solution 6

 Feasible/Infeasible Solutions
• A feasible solution does not violate any of the constraints:
Example x1= 5 bowls
x2= 10 mugs
Z = $40 x1 + 50x2= $700
Labor constraint check:
1(5) + 2(10) = 25 < 40 hours, within constraint
Clay constraint check:
4(5) + 3(10) = 70 < 120 pounds, within constraint

• An infeasible solution violates at least one of the constraints:

Example x1 = 10 bowls
x2 = 20 mugs
Z = $1400
Labor constraint check:
1(10) + 2(20) = 50 > 40 hours, violates constraint
Chapter 2 - Linear Programming: Model Formulation and Graphical Solution 7
 Graphical Solution of Linear Programming Models

• Graphical solution is limited to linear programming models

containing only two decision variables. (Can be used with
three variables but only with great difficulty.)

• Graphical methods provide visualization of how a solution

for a linear programming problem is obtained.

Dr. Esmat Mohamed Abdel Moniem El sayed 8

 Graphical Solution of a Maximization Model (1 of 12)
Coordinate Axes

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x 2  0

Figure 2.1 Coordinates for graphical analysis

Dr. Esmat Mohamed Abdel Moniem El sayed 9
 Graphical Solution of a Maximization Model (2 of 12)
Labor Constraint

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x 2  0

Figure 2.2 Graph of the labor constraint line

Dr. Esmat Mohamed Abdel Moniem El sayed 10
 Graphical Solution of a Maximization Model (3 of 12)
Labor Constraint Area

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x 1, x2  0

Figure 2.3 The labor constraint area

Dr. Esmat Mohamed Abdel Moniem El sayed 11

 Graphical Solution of a Maximization Model (4 of 12)
Clay Constraint Area

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x2 0

Figure 2.4 The constraint area for clay

Dr. Esmat Mohamed Abdel Moniem El sayed 12

 Graphical Solution of a Maximization Model (5 of 12)
Both Constraints

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x 2  0

Figure 2.5 Graph of both model Constraints

Dr. Esmat Mohamed Abdel Moniem El sayed 13

 Graphical Solution of a Maximization Model (6 of 12)
Feasible Solution Area

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x2  0

Figure 2.6 The feasible solution area constraints

Chapter 2 - Linear Programming: Model Formulation and Graphical Solution 14

 Graphical Solution of a Maximization Model (7 of 12)
Objective Function = $800

Z= $800 = $40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x 2  0

Figure 2.7 Objective function line for Z = $800

Dr. Esmat Mohamed Abdel Moniem El sayed 15

 Graphical Solution of a Maximization Model (8 of 12)
Alternative Objective Functions

Z=$800, $1200, $1600 = $40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x 2  0

Figure 2.8
Alternative objective function lines for profits, Z, of $800, $1,200, and $1,600
Dr. Esmat Mohamed Abdel Moniem El sayed 16
 Graphical Solution of a Maximization Model (9 of 12)
Optimal Solution

Z= $800 =$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x 2  0

Figure 2.9 Identification of optimal solution point

Dr. Esmat Mohamed Abdel Moniem El sayed 17

 Graphical Solution of a Maximization Model (10 of 12)
Optimal Solution Coordinates

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x2  0

Figure 2.10 Optimal solution coordinates

Chapter 2 - Linear Programming: Model Formulation and Graphical Solution 18

 Graphical Solution of a Maximization Model (11 of 12)
Corner Point Solutions

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x 2  0

Figure 2.11 Solutions at all corner points

Dr. Esmat Mohamed Abdel Moniem El sayed 19
 Graphical Solution of a Maximization Model (12 of 12)
Optimal Solution for New Objective Function

maximize Z=$40x1 + 50x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x 2  0

Figure 2.12 The optimal solution with Z = 70x1 1 20x2

Dr. Esmat Mohamed Abdel Moniem El sayed 20

 Slack Variables

• Standard form requires that all constraints be in the form of

equations.

• A slack variable is added to a  constraint to convert it to

an equation (=).

• A slack variable represents unused resources.

• A slack variable contributes nothing to the objective

function value.

Dr. Esmat Mohamed Abdel Moniem El sayed 21

 Complete Linear Programming Model in Standard Form

maximize Z=$40x1 + 50x2 + 0s1 + 0s2

subject to
1x1 + 2x2 + s1 = 40
4x2 + 3x2 + s2 = 120
x1,x2,s1,s2 = 0
where x1 = number of bowls
x2 = number of mugs
s1, s2 are slack variables

Figure 2.13 Solutions at points A, B, and C with slack

Dr. Esmat Mohamed Abdel Moniem El sayed 22

 A Minimization Model Example (1 of 7)
Problem Definition
• Two brands of fertilizer available - Super-gro, Crop-quick.
• Field requires at least 16 pounds of nitrogen and 24 pounds of phosphate.
• Super-gro costs $6 per bag, Crop-quick $3 per bag.
• Problem : How much of each brand to purchase to minimize total cost of
fertilizer given following data ?

Chemical Contribution

Nitrogen Phosphate
Brand (lb/bag) (lb/bag)

Super-gro 2 4

Crop-quick 4 3

Dr. Esmat Mohamed Abdel Moniem El sayed 23

 A Minimization Model Example (2 of 7)
Model Construction
Decision varables
x1 = bags of Super-gro
x2 = bags of Crop-quick
The objective function:
minimize Z = $6x1 + 3x2
where $6x1 = cost of bags of Super-gro
3x2 = cost of bags of Crop-quick
Model constraints:
2x1 + 4x2  16 lb (nitrogen constraint)
4x1 + 3x2  24 lb (phosphate constraint)
x1, x2  0 (nonnegativity constraint)

Chapter 2 - Linear Programming: Model Formulation and Graphical Solution 24

 A Minimization Model Example( 3 of 7)
Complete Model Formulation and Constraint Graph

Complete model formulation:

minimize Z = $6x1 + 3x2
subject to
2x1 + 4x2  16 lb of nitrogen
4x1 + 3x2  24 lb of phosphate
x1, x 2  0

Figure 2.4 Constraint lines for fertilizer model

Dr. Esmat Mohamed Abdel Moniem El sayed 25
 A Minimization Model Example( 4 of 7)
Feasible Solution Area

minimize Z = $6x1 + 3x2

subject to
2x1 + 4x2  16 lb of nitrogen
4x1 + 3x2  24 lb of phosphate
x1, x2  0

Figure 2.15 Feasible solution area

Dr. Esmat Mohamed Abdel Moniem El sayed 26

 A Minimization Model Example (5 of 7)
Optimal Solution Point

minimize Z = $6x1 + 3x2

subject to
2x1 + 4x2  16 lb of nitrogen
4x1 + 3x2  24 lb of phosphate
x1, x2  0

Figure 2.16 The optimal solution point

Dr. Esmat Mohamed Abdel Moniem El sayed 27

 A Minimization Model Example (6 of 7)
Surplus Variables

• A surplus variable is subtracted from a  constraint to convert it to an

equation (=).

• A surplus variable represents an excess above a constraint requirement

level.

• Surplus variables contribute nothing to the calculated value of the

objective function.

• Subtracting slack variables in the farmer problem constraints:

2x1 + 4x2 - s1 = 16 (nitrogen)
4x1 + 3x2 - s2 = 24 (phosphate)

Dr. Esmat Mohamed Abdel Moniem El sayed 28

 A Minimization Model Example (7 of 7)
Graphical Solutions

minimize Z = $6x1 + 3x2 + 0s1 + 0s2

subject to
2x1 + 4x2 - s1 = 16
4x1 + 3x2 - s2 = 24
x1, x2, s1, s2 = 0

Figure 2.17 Graph of the fertilizer example

Dr. Esmat Mohamed Abdel Moniem El sayed 29

 Irregular Types of Linear Programming Problems

• The general rules do not apply for some linear

programming models.

• Special types of problems include those with:

1. Multiple optimal solutions
2. Infeasibile solutions
3. Unbounded solutions

Dr. Esmat Mohamed Abdel Moniem El sayed 30

 Multiple Optimal Solutions

Objective function is parallel to a

constraint line:

maximize Z=$40x1 + 30x2

subject to
1x1 + 2x2  40 hours of labor
4x2 + 3x2  120 pounds of clay
x1, x2  0
where x1 = number of bowls
x2 = number of mugs

Figure 2.18
Graph of the Beaver Creek Pottery Company example with multiple optimal solutions

Dr. Esmat Mohamed Abdel Moniem El sayed 31

 An Infeasible Problem

Every possible solution violates

at least one constraint:

maximize Z = 5x1 + 3x2

subject to
4x1 + 2x2  8
x1  4
x2  6
x1, x2  0

Figure 2.19 Graph of an infeasible problem

Dr. Esmat Mohamed Abdel Moniem El sayed 32

 An Unbounded Problem

Value of objective function

increases indefinetly:

maximize Z = 4x1 + 2x2

subject to
x1  4
x2  2
x1, x2  0

Figure 2.20 An unbounded problem

Dr. Esmat Mohamed Abdel Moniem El sayed 33
 Characteristics of Linear Programming Problems

• A linear programming problem requires a decision - a choice amongst

alternative courses of action.
• The decision is represented in the model by decision variables.
• The problem encompasses a goal, expressed as an objective function,
that the decision maker wants to achieve.
• Constraints exist that limit the extent of achievment of the objective.
• The objective and constraints must be definable by linear mathematical
functional relationships.

Chapter 2 - Linear Programming: Model Formulation and Graphical Solution 34

 Properties of Linear Programming Models

• Proportionality - The rate of change (slope) of the

objective function and constraint equations is constant.
• Additivity - Terms in the objective function and constraint
equations must be additive.
• Divisability -Decision variables can take on any fractional
value and are therefore continuous as opposed to integer
in nature.
• Certainty - Values of all the model parameters are assumed
to be known with certainty (non-probabilistic).

Dr. Esmat Mohamed Abdel Moniem El sayed 35

 Example Problem No. 1 (1 of 2)
Problem Statement

- Hot dog mixture in 1000-pound batches.

- Two ingredients, chicken ($3/lb) and beef ($5/lb),
- Recipe requirements:
at least 500 pounds of chicken
at least 200 pounds of beef.
- Ratio of chicken to beef must be at least 2 to 1.
- Determine optimal mixture of ingredients that will minimize costs.

Dr. Esmat Mohamed Abdel Moniem El sayed 36

 Example Problem No. 1 (2 of 2)
Solution

Step 1: Identify decision variables.

x1 = lb of chicken
x2 = lb of beef

Step 2: Formulate the objective function.

minimize Z = $3x1 + 5x2
where Z = cost per 1,000-lb batch
$3x1 = cost of chicken
5x2 = cost of beef

Dr. Esmat Mohamed Abdel Moniem El sayed 37

 Example Problem No.1 (3 of 3)
Solution (continued)
Step 3: Establish Model Constraints
x1 + x2 = 1,000 lb
x1  500 lb of chicken
x2  200 lb of beef
x1/x2  2/1 or x1 - 2x2  0
x1,x2  0
The model: minimize Z = $3x1 + 5x2
subject to
x1 + x2 = 1,000 lb
x1  50
x2  200
x1 - 2x2  0
x1,x2  0

Dr. Esmat Mohamed Abdel Moniem El sayed 38

 Example Problem No.2 (1 of 3)

Solve the following model graphically:

maximize Z = 4x1 + 5x2
subject to
x1 + 2x2  10
6x1 + 6x2  36
x1  4
x1,x2  0
Step 1: Plot the constraint s as equations:

Figure 2.21 The constraint equations

Dr. Esmat Mohamed Abdel Moniem El sayed 39

 Example Problem No.2 (2 of 3)

maximize Z = 4x1 + 5x2

subject to
x1 + 2x2  1
6x1 + 6x2  36
x1  4
x1,x2  0
Step 2: Determine the feasible
solution area:

Figure 2.22 The feasible solution space and extreme points

Dr. Esmat Mohamed Abdel Moniem El sayed 40

 Example Problem No.2 (3 of 3)

maximize Z = 4x1 + 5x2

subject to
x1 + 2x2  10
6x1 + 6x2  36
x1  4
x1,x2  0
Steps 3 and 4:
Determine the solution points
and optimal solution.

Figure 2.23 Optimal solution point

Dr. Esmat Mohamed Abdel Moniem El sayed 41