Scribd
Upload
5 views4 pages

Linear Programming Examples and Solutions

This document provides 3 examples of using the artificial variable method to find an initial basic feasible solution (BFS0) for linear programs (LPs) that may not have an initial feasible solution. It introduces the artificial variable technique, which involves adding an artificial variable to make the starting solution feasible. It then works through each example step-by-step, showing how to set up the artificial LP and find the BFS0. The key point is that finding a feasible solution to the artificial LP with the artificial variable equal to zero corresponds to a feasible solution for the original LP.

Uploaded by

Ali A Daraghmeh
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
5 views4 pages

Linear Programming Examples and Solutions

This document provides 3 examples of using the artificial variable method to find an initial basic feasible solution (BFS0) for linear programs (LPs) that may not have an initial feasible solution. It introduces the artificial variable technique, which involves adding an artificial variable to make the starting solution feasible. It then works through each example step-by-step, showing how to set up the artificial LP and find the BFS0. The key point is that finding a feasible solution to the artificial LP with the artificial variable equal to zero corresponds to a feasible solution for the original LP.

Uploaded by

Ali A Daraghmeh
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

Example 1:

Max Z=3x1+2x2+4x3
x1+2x2+5x3 ≤ 20 (1)
-3x1 + 4x2 ≤ 10 (2)
x1,x2,x3 ≥ 0
Standard form
Max Z=3x1+2x2+4x3
x1+2x2+5x3+s1 = 20 (1)
-3x1 + 4x2 + s2 = 10 (2)
x1,x2,x3,s1,s2 ≥ 0
Finding BFS0:
Set the original variables to zero
BFS0=(0,0,0,20,10)
Basic variables: s1, s2
Remark: Z=c.x=[Link]+[Link]=[Link] (since xN=0)
Example 2 :
Max Z = x1 + 3 x2
x1 + 2 x2  2 (1)
- x1 + 2 x2  4 (2)
x1 , x2  0
Standard form:
Max Z = x1 + 3 x2
x1 + 2 x2 +s1 = 2 (1)
- x1 + 2 x2 - s2= 4 (2)
x1 , x2 ,s1,s2  0
Finding BFS0:
Setting the original variables to zero
BFS0=(0,0,2,-4) (infeasible solution!!!)
The Artificial Linear Program
(LPA): Min ZA = a2
x1 + 2 x2 +s1 = 2 (1)
- x1+2 x2-s2+a2=4 (2)
x1 , x2 ,s1,s2,a2  0
By setting x1=x2=0, we get: s1=2,s2=0,a2=4
BFS0=(0,0,2,0,4)
Adding artificial variables solves the starting
solution issue. However, a feasible solution of
(LPA) is also feasible for the original LP if and
only if all the artificial variables are equal to
zero. In other words, finding a feasible solution
for the original LP turns out to finding a feasible
solution of LPA but with a2=0.
Example 3:
Max Z=3x1+2x2+4x3
x1+2x2+5x3 ≤ 20 (1)
-3x1 + 4x2 ≥ 10 (2)
x1,x2,x3 ≥ 0
Artificial LP
Min ZA=a2 (or equivalently Max ZA=-a2)
x1+2x2+5x3+s1 = 20 (1)
-3x1 + 4x2 - s2 + a2 = 10 (2)
x1,x2,x3,s1,s2,a2 ≥ 0
BFS0=(0,0,0,20,0,10)

You might also like