Scribd
Upload
30 views2 pages

Linear Programming Optimization Steps

The document provides steps for solving linear programming problems using the simplex method for both maximization and minimization problems. For maximization problems, the entering variable is chosen as the one with the highest non-negative cost (NC) value and the variable to exit is chosen using the least positive ratio test. For minimization problems, the entering variable is chosen as the one with the most negative NC value. In both cases, an optimal solution is reached when all entries in the NC row are non-positive. The document also includes an example problem on finding the optimal mixture of two ingredients to minimize total cost given various constraints.

Uploaded by

Cho Andrea
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
30 views2 pages

Linear Programming Optimization Steps

The document provides steps for solving linear programming problems using the simplex method for both maximization and minimization problems. For maximization problems, the entering variable is chosen as the one with the highest non-negative cost (NC) value and the variable to exit is chosen using the least positive ratio test. For minimization problems, the entering variable is chosen as the one with the most negative NC value. In both cases, an optimal solution is reached when all entries in the NC row are non-positive. The document also includes an example problem on finding the optimal mixture of two ingredients to minimize total cost given various constraints.

Uploaded by

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

Maximization: Summary of steps

1. Convert the constraints by :

Original Constraints Action Required Resulting Constraints


xc Add a slack variable x+ s=c
xc Multiply both sides by (-1) x + s=c
and add a slack variable
x=c Add an slack variable x+ s=c
2. Determine the entering variable by choosing the one with the highest NC value.
3. Least positive ratio will be chosen for the variable to exit.
4. If entries in NC row are negative or zero then an optimal solution has been reached.

Minimization: Summary of steps


1. Convert the constraints by :

Original Constraints Action Required Resulting Constraints


xc Add a surplus variable x+ r=c
xc Subtract a surplus and add xr +a=c
an artificial variable
x=c Add an artificial variable x+ a=c
2. Determine the entering variable by choosing the one with the most negative NC value.
3. Least positive ratio will be chosen for the variable to exit.
4. If entries in NC row are positive or zero then an optimal solution has been reached.

Illustrative example

A manufacturer of commercial chemicals has an order for a certain mixture consisting of


two ingredients, x and y which cost PhP4 and PhP5 per kilo, respectively. The following are
the specifications: a) The weight of the mixture must be 100 kilos, b) It cannot contain more
than 30 kilos of x, and c) It must contain at least 20 kilos of y. Find the mixture of the two
ingredients, which satisfies the customers requirement and still yield a minimum total cost
of raw materials.

Minimize: C=4 x +5 y

Subject to: x+ y=100

x 30

y 20

x , y 0

New LP model

Minimize: C=4 x +5 y +0 r 1 +0 r 2 +10 a1 +10 a2

Subject to: x+ y+ 0 r 1+ 0 r 2+ a1 +0 a2 =100

x+ 0 y+ r 1+ 0 r 2+ 0 a1 +0 a2 =30
0 x+ y+ 0 r 1r 2 +0 a1 +1 a2 =20

x , y , s 1 , s 2 , a1 ,a 2 0

Quantity 4 5 0 0 10 10 Ratio
Colum
Column x y r1 r2 a1 a2
n
10 a1 100 1 1 0 0 1 0
0 r1 30 1 0 1 0 0 0
10 a2 20 0 1 0 -1 0 1
Basic 10 20 0 -10 10 10 OC row
variables -6 -15 0 10 0 0 NC row

You might also like