[go: up one dir, main page]
Scribd
Upload
12 views29 pages

MPD445 - Lecture 02 - 252

The document provides an overview of Linear Programming (LP), a mathematical technique used for optimizing problems by maximizing or minimizing a linear function subject to constraints. It defines key concepts such as decision variables, objective functions, constraints, feasible solutions, and optimum solutions, and outlines the basic assumptions and properties of LP models. Additionally, it explains methods for solving LP problems, including graphical and simplex methods, and provides an example of formulating and solving an LP problem related to production planning.

Uploaded by

Mahmoud Essam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views29 pages

MPD445 - Lecture 02 - 252

The document provides an overview of Linear Programming (LP), a mathematical technique used for optimizing problems by maximizing or minimizing a linear function subject to constraints. It defines key concepts such as decision variables, objective functions, constraints, feasible solutions, and optimum solutions, and outlines the basic assumptions and properties of LP models. Additionally, it explains methods for solving LP problems, including graphical and simplex methods, and provides an example of formulating and solving an LP problem related to production planning.

Uploaded by

Mahmoud Essam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 29

MECHANICAL ENGINEERING

DEPARTMENT
4th year Production

MDP445
Computer in Planning,
Analysis and Control

Lecture: 2
Computer in Planning:
Linear Programming

Dr. Sayed Ali Zayan 2nd Term 2024/2025


Linear Programming (LP)
Linear programming is a mathematical technique for solving a
broad class of optimization problems. These problems require
maximizing or minimizing a linear function of n real variables
subject to m constraints. One can formulate and solve a large
number of real problems with linear programming. A partial list
includes
 Production planning and inventory control.
 Several varieties of blending problems including cattle feed
and steel making.
 Scheduling of personnel.
 Distribution and logistics problems.
 Assignment problems.
Linear Programming (LP): Definitions
 Decision Variables: In a LPP model, the decision variable means the variable
whose quantitative values are required be found, so as to minimize (or
maximize) the objective function.
 Objective Function: The decision maker wants to maximize a function such as
revenue/profit function, or minimize a function such as cost function, under
some restrictions. Function, which is maximized or minimized is termed as
objective function.
 Constraint: The restrictions, which are expressed in the form of an equation or
inequality (generally assigned with sign ≤ or ≥ are termed as constraints.
 Feasible Solution: A set of values of decision variables, which satisfies the
constraints set, contributes to the feasible solution. There may be many
feasible solutions for a LP problem and all obviously are not the best solution.
 Optimum Solution: An optimum solution of an LPP is that set of feasible
solution, which satisfies the maximization (or minimization) of the objective
function. In case of maximization problem, the objective function needs to be
maximized. However, in case of minimization problem, objective function is
minimized.
Linear Programming (LP)
There are following properties of LPP:
1. The relationship between variables and constraints is linear.
2. The model has an objective function.
3. The model has structural constraints.
4. The model has non-negativity constraint

Basic Assumptions of LPP


The following are some important assumptions made in formulating an LPP
model:
1. All the situations, such as resources, course of action, etc., are considered as
deterministic in nature.
2. The relationship between variables and resources is linear in nature.
3. The decision variables are continuous.
4. LPP is a static model, i.e. it is a single-stage decision problem.
Structure of Linear Programming Model
The objective function may be written as:

The linear programming problem may be solved by two methods:


1. Graphical Method
2. Simplex Method.
Linear Programming (LP):Graphical Method
Following steps are adopted to solve a two variable LPP through
graphical method:
Step 1: Formulate the problem in standard LPP form. It should have a
linear objective function of maximization (or minimization) type. There
may be as many linear constraints but decision variables should not
exceed two.
For example:
Linear Programming (LP):Graphical Method
Step 2: Treat each constraint as
a line equation by assuming ≥ or
≤ signs as equal to sign, Plot
them on a graph paper.
For example:
Constraint (1) X1 + X2 = 200

Step 3: Based on the original


sign (≥ or ≤) of the constraint,
mark the feasible region in
space.
Linear Programming (LP):Graphical Method
Step 4: Identify the corner points (or intersection of constraints,
represented by lines) of the feasible region. Also include the two
intersections on two axes by the feasible region. All these points
constitute a set of possible solution, as optimal solution always lies on
the corner points.

Figure: Objective
function values at
each extreme
point of the
feasible region
Linear Programming (LP):Graphical Method
Step 5: For the objective function, draw straight line, called as
isoprofit/isocost line. This may be done by equating the objective
function to a very small profit figure or a high cost figure depending
upon the nature of the objective function, i.e., maximization or
minimization respectively.
Linear Programming (LP):Graphical Method
Step 6: Draw parallel lines to the isoprofit
line in maximization problem: moving away
from the origin. Stop only when there is only
one point_ in the feasible region, which is
also on the isoprofit line.
For the minimization problem, draw parallel
lines to the isocost line and move towards
the origin. Stop when there is only, one
point in the feasible, region which is also on
the isocost line.
Step 7: This point represents optimal
solution. From the optimal solution point,
draw perpendicular lines on both axes (X
and Y axes). The point of intersection on the
axis will give the values of two variables
which give optimal solution.
Example:
A company is manufacturing two different types of products, A and B.
Each product has to be processed in 3 different departments casting,
machining and finally quality inspection. The capacity of the
departments is limited to 35, 32, and 24 hrs./week respectively. Product
A requires 7 hrs., in casting department, 8 hrs., in machining shop and 4
hrs. in inspection, whereas product B requires 5 hrs., 4 hrs., and 6 hrs.,
respectively in each shop. The profit contribution for a unit product of A
and B is $40 and $30 respectively.
A. Formulate the LP problem and solve the problem by graphical
method.
B. Solve the LPP by using QM software.
C. Create a spreadsheet model for this problem, write the different
formula, and solve it using Solver.
D. By using the coordinates of corner points for feasible solution area in
part (A), write the C++ program to find the optimal quantities of
product A and B and the total profit contribution.
Solution:
Processing time by product and department:

a) Formulation of problem:
1) Decision variables:
Let X1 = number of units from product A.
X2 = the number of units from product B.
2) Objective function:
The objective function, to be maximized:
Z = 40X1 + 30X2
Solution:
3) Constraints:
7X1 + 5X2 ≤ 35 (1)
8X1 + 4X2 ≤ 32 (2)
4X1 + 6X2 ≤ 24 (3)
Also, X1 ≥ 0 and X2 ≥0

Solve by graphical method:


For constraint (1):
Assume 7X1 + 5X2 = 35
if X1=0 then X2 = 35/5 = 7,
if X2 = 0 then X1 = 35/7=5.
Solution:
Constraint (2):
8X1 + 4X2 = 32, then
(X1, X2) = (4, 8)

Constraint (3):
Assume 4X1 + 6X2 = 24, then
(X1, X2) = (6,4)

The final graphical solution:


Solution:
The optimal solution by the corner points:

The optimal profit (maximum) is at point N; when (X1, X2) is (3, 2).
Hence, 3 units of A and 2 units of B should be manufactured.

The total profit contribution


The optimal profit contribution at N
Z= 40X1 + 30X2 = 40 x 3 + 30 x 2 =180
Solution:
b) By QM software:
From module menu select linear programming module, then click.
Solution:
Enter the data:
Solution:
Solution:
c) Solution by Excel solver:
First construct the Excel sheet:
Solution:
 The formula and Excel solver parameters:
Solution:

The results by solver:


From data menu click
on Solver:
Solution:
 After entering the parameters click Solve
Solution:
 Final result:
Solution:

d) The C++ program to find


the optimal solution and
the total profit:

Flow chart
Solution:
Solution:
Solution:
 The input and the final results screen:
END
Lecture
You can win, if you want

You might also like