DR.

IBRAHIM SABRY Lecturer 2

Verbal Language (L.P)

Faculty of Engineering
Linear Programming: An Overview

 Objectives of business decisions frequently involve

of Mechanical Engineering

maximizing profit or minimizing costs.

 Steps in application:
1. Identify problem as solvable by linear
programming.
2. Formulate a mathematical model of the
unstructured problem.
Benha University
M 1481 , Department

3. Solve the model.

4. Implementation

Dr. Ibrahim Sabry

 INTRODUCTION

 Mathematical programming is used to find the best or optimal

Faculty of Engineering
of Mechanical Engineering

solution to a problem that requires a decision or set of

decisions about how best to use a set of limited resources to
achieve a state goal of objectives.

 Steps involved in mathematical programming

 Conversion of stated problem into a mathematical model

Benha University
M 1481 , Department

 Exploration of different solutions of the problem.

 Finding out the most suitable or optimum solution.

 Linear programming requires that all the mathematical

functions in the model be linear functions.

Dr. Ibrahim Sabry

 Model Components
 Decision variables - mathematical symbols representing levels of activity
Faculty of Engineering

of a firm.
of Mechanical Engineering

 Objective function - a linear mathematical relationship describing an

objective of the firm, in terms of decision variables - this function is to be
maximized or minimized.
 Constraints – requirements or 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
Benha University
M 1481 , Department

function and constraints.

Linear Programming Model is composed of the same components

Dr. Ibrahim Sabry
 Benha University Faculty of Engineering
M 1481 , Department of Mechanical Engineering

Dr. Ibrahim Sabry

Faculty of Engineering
Summary of Model Formulation Steps
of Mechanical Engineering

Step 1
Clearly define the decision
variables

Step 2
Construct the objective
function
Benha University
M 1481 , Department

Step 3 Formulate the constraints

Dr. Ibrahim Sabry

 PROPERTIES OF LP MODELS
Faculty of Engineering
of Mechanical Engineering

Seek to minimize or maximize

Include “constraints” or limitations

Benha University
M 1481 , Department

There must be alternatives available

All equations are linear

Dr. Ibrahim Sabry

 THE LINEAR PROGRAMMING MODEL (1)
Let: X1, X2, X3, ………, Xn = decision variables
Faculty of Engineering
of Mechanical Engineering

Z = Objective function or linear function

Requirement: Maximization of the linear function Z.

Z = c1X1 + c2X2 + c3X3 + ………+ cnXn …..Eq (1)

subject to the following constraints:
Benha University
M 1481 , Department

…..Eq (2)

Dr. Ibrahim Sabry

 THE LINEAR PROGRAMMING MODEL (2)
 The linear programming model can be written in more efficient notation as:
Faculty of Engineering
of Mechanical Engineering

…..Eq (3)
Benha University
M 1481 , Department

The decision variables, xI, x2, ..., xn, represent levels of n competing
activities.
Dr. Ibrahim Sabry
 Benha University Faculty of Engineering
M 1481 , Department of Mechanical Engineering
 A factory manufactures two products A and B. To manufacture one unit
Faculty of Engineering

of A, 1.5 machine hours and 2.5 labour hours are required. To

of Mechanical Engineering

manufacture product B, 2.5 machine hours and 1.5 labour hours are
required. In a month, 300 machine hours and 240 labour hours are
available. Profit per unit for A is Rs. 50 and for B is Rs. 40. Formulate
as LPP.
Benha University
M 1481 , Department

There will be two constraints. One for machine hours availability and
for labour hours availability. Decision variables

Dr. Ibrahim Sabry

Faculty of Engineering

X1 = Number of units of A manufactured per month.

of Mechanical Engineering

X2 = Number of units of B manufactured per month.

The objective function:

Max Z = 50x1+ 40x2

Constraints
For machine hours
Benha University
M 1481 , Department

1.5x1+ 2.5x2 ≤ 300

For labour hours
2.5x1+ 1.5x2 ≤ 240
Non negativity
x1, x2 ≥0

Dr. Ibrahim Sabry

 A company produces three products A, B, C. For manufacturing
Faculty of Engineering

three raw materials P, Q and R are used. Profit per unit

of Mechanical Engineering

A - Rs. 5, B - Rs. 3, C - Rs. 4

Resource requirements/unit
Benha University
M 1481 , Department

Maximum raw material availability:

P - 80 units; Q - 100 units; R - 150 units. Formulate LPP.

Dr. Ibrahim Sabry

 Decision variables:
Faculty of Engineering

x1 = Number of units of A
of Mechanical Engineering

x2 = Number of units of B
x3 = Number of units of C

Objective Function
Since Profit per unit is given, objective function is maximisation
Max Z = 5x1+ 3x2 + 4x3
Constraints:
Benha University
M 1481 , Department

For P:
0x1+ 20x2 + 30x3 ≤ 80
For Q:
20x1+ 30x2 + 20x3 ≤ 100
For R:
50x1+ 0x2 + 40x3 ≤ 150 X1, X2, X3 ≥ 0
Dr. Ibrahim Sabry
 A firm produces three products. These products are processed
Faculty of Engineering
of Mechanical Engineering

on three different machines.

The time required to manufacture one unit of each of the three
products and the daily capacity of the three machines are given
in the table below:
Benha University
M 1481 , Department

Dr. Ibrahim Sabry

 Decision variables:
Faculty of Engineering

x1 = Number of units of M1
of Mechanical Engineering

x2 = Number of units of M2
x3 = Number of units of M3

Z = 4x1+ 3x2 + 6x3

Constraints:

2x1+ 3x2 + 2x3 ≤ 440

Benha University
M 1481 , Department

4x1+ 0x2 + 3x3 ≤ 470

2x1+ 5x2 + 0x3 ≤ 430

Dr. Ibrahim Sabry

 A manager at an oil company wants to find optimal mix of two blending
Faculty of Engineering

processes. Formulate LPP.

of Mechanical Engineering

Process 1 (P1) = Rs. 4, 000

Profit per operation:
Process 2 (P2) = Rs. 5, 000
Benha University
M 1481 , Department

Grade A = 500 units

Maximum availability of crude oil:
Grade B = 400 units

Minimum Demand for Gasoline:

X = 300 units
Y = 200 units

Dr. Ibrahim Sabry

 Solution:
Faculty of Engineering
of Mechanical Engineering

Decision Variables:
x1 = No. of operations of P1
x2 = No. of operations of P2
Objective Function:
Max. Z = 4000 x1 + 5000 x2
Subjective to constraints:
6x1+ 5x2 ≤ 500
4x1+ 6x2 ≤ 400
Benha University
M 1481 , Department

6x1+ 5x2 ≥300

9x1+ 5x2 ≥200
x1, x2 ≥ 0

Dr. Ibrahim Sabry

 Vitamins B1 and B2 are found in two foods F1 and F2. 1 unit of F1 contains 3
Faculty of Engineering

units of B1 and 4 units of B2. 1 unit of F2 contains 5 units of B1 and 3 units

of Mechanical Engineering

of B2 respectively.
Minimum daily prescribed consumption of B1 & B2 is 50 and 60 units
respectively. Cost per unit of F1 & F2 is Rs. 6 & Rs. 3 respectively.
Formulate as LPP

Vitamins FOOD Minimum

consumption
Benha University

F1 F2
M 1481 , Department

B1 3 5 50

B2 4 3 60

Dr. Ibrahim Sabry

 Decision Variables:
Faculty of Engineering

x1 = No. of units of B1 per day.

of Mechanical Engineering

x2 = No. of units of B2 per day.

Objective function:
Min. Z = 6 x1 + 3 x2

Subject to constraints:
Benha University
M 1481 , Department

3x1+ 5x2 ≥ 50 (for N1)

4x1+ 3x2 ≥ 60 (for N2)
x1, x2 ≥ 0

Dr. Ibrahim Sabry

 A farmer has 200 acres of land. He produces three products X, Y & Z.
Faculty of Engineering

Average yield per acre for X,Y & Z is 4000, 6000 and 2000 kg.
of Mechanical Engineering

Selling price of X, Y & Z is Rs. 2, 1.5 & 4 per kg respectively. Each product
needs fertilizers.
Cost of fertilizer is Rs. 1 per kg. Per acre need for fertilizer for X, Y & Z is
200, 200 & 100 kg respectively. Labour requirements for X, Y & Z is 10, 12 &
10 man hours per acre. Cost of labour is Rs. 40 per man hour. Maximum
availability of labour is 20, 000 man hours.
Benha University
M 1481 , Department

Formulate as LPP to maximise profit

Dr. Ibrahim Sabry

 The production/yield of three products X, Y & Z is given as per acre.
Faculty of Engineering

Hence,
of Mechanical Engineering

x1 = No. of acres allocated to X

x2 = No. of acres allocated to Y
x3 = No. of acres allocated to Z

Objective Function:
Profit = Revenue - Cost
Profit = Revenue - (Fertiliser Cost + Labour Cost)

Objective function
Benha University
M 1481 , Department

Max. = 7400 x1 + 8320 x2 + 7500 x3

Subject to constraints:
x1 + x2 + x3 = 200 (Total Land)
10 x1 + 12 x2 + 10 x3 ≤ 20, 000 (Max Man hours)
x1, x2, x3 ≥ 0

Dr. Ibrahim Sabry