Scribd
Upload
3 views7 pages

Algebraic and Graphical Methods in LP

Chapter 2 discusses the algebraic and graphical methods for solving linear programming problems. The algebraic method involves converting inequalities to equalities, determining the number of variables and equations, solving the system, and checking feasibility, while the graphical method includes finding the feasible solution space and the optimum solution. Examples illustrate both methods for maximizing and minimizing objective functions under given constraints.

Uploaded by

mhmdrmdanslahslah3
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
3 views7 pages

Algebraic and Graphical Methods in LP

Chapter 2 discusses the algebraic and graphical methods for solving linear programming problems. The algebraic method involves converting inequalities to equalities, determining the number of variables and equations, solving the system, and checking feasibility, while the graphical method includes finding the feasible solution space and the optimum solution. Examples illustrate both methods for maximizing and minimizing objective functions under given constraints.

Uploaded by

mhmdrmdanslahslah3
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

Chapter 2 The Algebraic Method and Graphical Method

The algebraic method is from pure mathematical methods, which adopts


the method of algebraic compensation of the expected values of the
internal variables in the mathematical model according to the number of
possible ways of these values.
Summary, we carry out the following steps to solve any linear equation
using the algebraic method.
Step 1: convert all inequalities into equalities (including any variable
restricted constraints).
Step 2: calculate the numbers of variables 𝑛 and the number of
equations 𝑚.
Step 3: determine solution to all square system of equations. The
maximum number of systems of equation to be solved is:

n
n!
Cm =
m! (n − 𝑚)!
Step 4: check feasibility of each solution obtained in step 3 by using the
constraints of all other equations
We call the variables that we freeze to zero as non basic variables and
the variables for which we solve as basic variables.
 Example 1
Find the optimal solution for the following LP model using algebraic
method
𝑀𝑎𝑥 𝑍 = 3𝑋1 + 5𝑋2
Subject to
2𝑋1 + 3𝑋2 ≤ 30……(1)
5𝑋1 + 4𝑋2 ≤ 60……(2)
𝑋1 , 𝑋2 ≥ 𝟎……(3)
15
Solution
𝑀𝑎𝑥 𝑍 = 3𝑋1 + 5𝑋2 + 0𝑠1 + 0𝑠2
Subject to
2𝑋1 + 3𝑋2 + 𝑠1 = 30……(1)
5𝑋1 + 4𝑋2 + 𝑠2 = 60……(2)

n
n!
Cm = =6
m! (n − 𝑚)!

The Graphical Method


The graphical procedure includes two steps:
1) Determination of the feasible solution space.
2) Determination of the optimum solution from among all the feasible
points in the solution space.

16
 Example 2
Solve the following LP graphically
Maximize Z = 5 𝑋1 + 4 𝑋2
Constraints
6 𝑋1 + 4 𝑋2 < 24 (1)
𝑋1 + 2 𝑋2 < 6 (2)
− 𝑋1 + 𝑋2 < 1 (3)
𝑋2 < 2 (4)
𝑋1 , 𝑋2 > 0 (5)
Solution

17
How select feasible region
We now will shade the feasible region. To do that consider the
constraints one by one. To determine the region, it
1- represents the constraint choose any point which does not pass
through the line say (0,0).
2- Substitute it in the constraint.
3- Since this is true we conclude that (0,0) lies in the region represented
by this constraint.

18
 Example 3
Solve the following LP graphically
Minimize Z = 0. 3𝑋1 + 0. 9𝑋2
Constraints
𝑋1 + 𝑋2 ≥ 800 (1)
0. 21𝑋1 -0.3𝑋2 ≤ 0 (2)
0. 03𝑋1 -0.01𝑋2 ≥ 0 (3)
𝑋1 , 𝑋2 > 0 (4)

19
20
 Example 4
Solve the following LP graphically
Max. Z = 2𝑋1 +𝑋2
Constraints
X1 + X 2 ≤ 10 (1)
X1 ≤ 4 (2)
X 2 ≥ X1 or X 2 − X1 ≥ 0 (3)
X1 , X 2 ≥ 0 (4)

A linear programming problem is solved graphically if it contains only


two variables.
21

You might also like