CHAPTER
8
Linear Programming Methods
for Optimum Design
Section 8.2 Definition of Standard Linear Programming Problem
8.1 _________________________________________________________________________________
Answer True or False.
1. A linear programming problem having maximization of a function cannot be transcribed
2. A surplus variable must be added to a “≤ type” constraint in the standard LP formulation.
3. A slack variable for an LP constraint can have a negative value. False
5. If a “≤ type” constraint is active, its slack variable must be positive. False
7. In the standard LP formulation, the resource limits are free in sign. False
9. Variables that are free in sign can be treated in any LP problem. True
11. All variables must be non-negative in the standard LP definition. True
8.2 _________________________________________________________________________________
Convert the following problem to the standard LP form:
Minimize = 51+ 42− 3
Subject to 1+ 22− 3≥1
21+2+3≥4
1,2≥0 ; 3 is unrestricted in sign.
Solution:
+− 3
− ; 1=1, 2=2, 3=3
+, 4=3
−, 5,6= surplus variables for the 1st and 2nd
8.3 _________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize =1+ 22
Subject to −1+ 32≤10
1+2≤6
1− 2≤2
1+ 32≤6
1,2≥0
Solution:
Arora, Introduction to Optimum Design, 4e
8-3
8.4 _________________________________________________________________________________
Convert the following problem to the standard LP form:
Minimize = 21−32
Subject to 1+2≤1
−21+2≥2
1,2≥0
Solution:
8.5 _________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize = 41+ 22
Subject to −21+2≤4
1+ 22≥2
1,2≥0
Solution:
8.6 _________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize =1+ 42
Subject to 1+ 22≤5
1+2= 4
1− 2≥3
1,2≥0
Solution:
Chapter 8 Linear Programming Methods for Optimum Design
8.7 _________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize =1+ 42
Subject to 1+ 22≤5
21+2= 4
1− 2≥1
1,2≥0
Solution:
8.8 _________________________________________________________________________________
Convert the following problem to the standard LP form:
Minimize = 91+ 22+ 33
Subject to −21− 2+ 33≤ −5
1−22+ 23≥ −2
1,2,3≥0
Solution:
Reversing the sign on the RHS of both constraints by multiplying both sides with
−
1, then introducing
8.9 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Minimize = 51+ 42− 3
Subject to 1+ 22− 3≥1
21+2+3≥4
1,2≥0 ; 3 is unrestricted in sign.
Solution:
+− 3
− ; 1=1, 2=2, 3=3
+, 4=3
−, 5,6= surplus variables for the 1st and 2nd
Arora, Introduction to Optimum Design, 4e
8-5
8.10 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize =−101−182
Subject to 1−32≤ −3
21+ 22≥5
1,2≥0
Solution:
8.11 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Minimize =201−62
Subject to 31− 2≥3
−41+ 32=−8
1,2≥0
Solution:
8.12 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize = 21+ 52−4.53+ 1.54
Subject to 51+ 32+ 1.53≤8
1.81−62+ 43+4≥3
−3.61+ 8.22+ 7.53+ 54=15
≥0; = 1 to 4
Solution:
5 = a slack variable for the 1st constraint; 6 = a surplus variable for the 2nd constraint.
Chapter 8 Linear Programming Methods for Optimum Design
8.13 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Minimize = 81−32+153
Subject to 51−1.82−3.63≥2
31+ 62+ 8.23≥5
1.51−42+ 7.53≥ −4.5
−2+ 53≥1.5
1,2≥0 ; 3 is unrestricted in sign.
Solution:
+− 3
− ; 1=1, 2=2, 3=3
+, 4=3
−; multiply by −1 on both sides of the 3rd
8.14 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize =101+ 62
Subject to 21+ 32≤90
41+ 22≤80
2≥15
51+2=25
1,2≥0
Solution:
Arora, Introduction to Optimum Design, 4e
8-7
8.15 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize =−21+ 42
Subject to 21+2≥3
21+102≤18
1,2≥0
Solution:
3 = a surplus variable for the 1st constraint, 4 = a slack variable for the 2nd constraint.
8.16 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize =1+ 42
Subject to 1+ 22≤5
21+2= 4
1− 2≥3
1≥0; 2 is unrestricted in sign.
Solution:
+− 2
− ; 1=1, 2=2
+, 3=2
−; 4 = a slack variable for the 1st constraint, and 5 = a
8.17 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Minimize = 31+ 22
Subject to 1− 2≥0
1+2≥2
1,2≥0
Solution:
Chapter 8 Linear Programming Methods for Optimum Design
Arora, Introduction to Optimum Design, 4e
8-8
8.18 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize = 31+ 22
Subject to 1− 2≥0
1+2≥2
21+2≤6
1,2≥0
Solution:
8.19 ________________________________________________________________________________
Convert the following problem to the standard LP form:
Maximize =1+ 22
Subject to 31+ 42≤12
1+ 32≥3
1≥0; 2 is unrestricted in sign.
Solution:
+− 2
− ; 1=1, 2=2
+, 3=2
−; 4 = a slack variable for the 1st constraint, and 5 = a
Chapter 8 Linear Programming Methods for Optimum Design
Section 8.3 Basic Concepts Related to LP Problems
Section 8.4 Calculation of Basic Solutions
8.20 ________________________________________________________________________________
Answer True or False.
1. In the standard LP definition, the number of constraint equations (i.e., rows in the matrix
2. In an LP problem, the number of “≤ type” constraints cannot be more than the number of
3. In an LP problem, the number of “≥ type” constraints cannot be more than the number of
7. A degenerate basic solution has exactly m variables with nonzero values, where m is the
9. A basic feasible solution must have m variables with positive values, where m is the number
11. The optimum point for an LP problem lies at a vertex of the feasible region. True
8.21 ________________________________________________________________________________
Find all the basic solutions for the following LP problem using the Gauss-Jordan elimination
method. Identify basic feasible solutions and show them on graph paper.
Maximize =1+ 42
Subject to 1+ 22≤5
21+2= 4
1− 2≥1
1,2≥0
Solution:
Standard LP form:
Table E8.21
1
2
3
4
f
1.
0
4
-3
-5
-16
infeasible
2.
2
0
3
1
-2
feasible
3.
1
2
0
-2
-9
infeasible
4.
5/3
2/3
2
0
-13/3
feasible
Chapter 8 Linear Programming Methods for Optimum Design
Arora, Introduction to Optimum Design, 4e
8-11
21+2= 4
1+ 22≤5
=−13/3
=−9
Chapter 8 Linear Programming Methods for Optimum Design
clear all
[x1,x2]=meshgrid(-1:0.05:5, -1:0.05:5);
f=–x1-4*x2;
cv1=[0:0.05:0.8];
const1=contour(x1,x2,g1,cv1,‘g’);
cv2=[0:0.01:0.02];
const1=contour(x1,x2,g1,cv2,‘k’);
cv3=[0:0.01:0.02];
contour(x1,x2,g3,cv8,‘k’);
cv9=[0:0.01:0.02]
contour(x1,x2,g4,cv9,‘k’);
fv=[-16 -9 -13/3 -2];
fs=contour(x1,x2,f,fv,‘r’);
8.22 ________________________________________________________________________________
Find all the basic solutions for the following LP problem using the Gauss-Jordan elimination
method. Identify basic feasible solutions and show them on graph paper.
Maximize =−101−182
Subject to 1−32≤ −3
21+ 22≥5
1,2≥0
Solution:
Standard LP form:
Table E8.22
1
2
3
4
f
1.
0
0
-3
-5
0
infeasible
2.
0
1
0
-3
18
infeasible
3.
0
2.5
4.5
0
45
feasible
4.
-3
0
0
-11
-30
infeasible
5.
2.5
0
-5.5
0
25
infeasible
6.
9/8
11/8
0
0
36
feasible
Figure E8.22
1−32≤ −3
=25
= 0
Chapter 8 Linear Programming Methods for Optimum Design
clear all
[x1,x2]=meshgrid(-1:0.05:3, -1:0.05:5);
f=10*x1+18*x2;
const1=contour(x1,x2,g1,cv1,‘g’);
cv2=[0:0.01:0.02];
const1=contour(x1,x2,g1,cv2,‘k’);
cv3=[0:0.07:0.85];
const3=contour(x1,x2,g2,cv3,‘g’);
8.23 ________________________________________________________________________________
Find all the basic solutions for the following LP problem using the Gauss-Jordan elimination
method. Identify basic feasible solutions and show them on graph paper.
Maximize =1+ 22
Subject to 31+ 42≤12
1+ 32≥3
1≥0, 2 is unrestricted in sign.
Solution:
Standard LP form:
8.24 ________________________________________________________________________________
Find all the basic solutions for the following LP problem using the Gauss-Jordan elimination
method. Identify basic feasible solutions and show them on graph paper.
Minimize =201−62
Subject to 31− 2≥3
−41+ 32=−8
1,2≥0
Solution:
Standard LP form:
Table E8.24
1
2
3
f
1.
0
-8/3
-1/3
16
infeasible
2.
2
0
3
40
feasible
3.
0.2
-2.4
0
18.4
infeasible
8.25 ________________________________________________________________________________
Find all the basic solutions for the following LP problem using the Gauss-Jordan elimination
method. Identify basic feasible solutions and show them on graph paper.
Maximize = 51−22
Subject to 21+2≤9
1−22≤2
−31+ 22≤3
1,2≥0
Solution:
Standard LP form:
Table E8.25
1
2
3
4
5
f
1.
0
0
9
2
3
0
feasible
2.
0
9
0
20
-15
18
infeasible
3.
0
-1
10
0
5
-2
infeasible
4.
0
1.5
7.5
5
0
3
feasible
5.
4.5
0
0
-2.5
16.5
-22.5
infeasible
6.
2
0
5
0
9
-10
feasible
7.
-1
0
11
3
0
5
infeasible
8.
4
1
0
0
13
-18
feasible
9.
15/7
33/7
0
65/7
0
-9/7
feasible
10.
-2.5
-2.25
16.25
0
0
8
infeasible
Chapter 8 Linear Programming Methods for Optimum Design
8.26 ________________________________________________________________________________
Find all the basic solutions for the following LP problem using the Gauss-Jordan elimination
method. Identify basic feasible solutions and show them on graph paper.
Maximize =1+ 42
Subject to 1+ 22≤5
1+2= 4
1− 2≥3
1,2≥0
Solution:
Standard LP form:
Table E8.26
1
2
3
4
f
1.
0
4
-3
-7
-16
infeasible
2.
4
0
1
1
-4
feasible
3.
3
1
0
-1
-7
infeasible
4.
3.5
0.5
0.5
0
-5.5
feasible
8.27 ________________________________________________________________________________
Find all the basic solutions for the following LP problem using the Gauss-Jordan elimination
method. Identify basic feasible solutions and show them on graph paper.
Minimize = 51+ 42− 3
Subject to 1+ 22− 3≥1
21+2+3≥4
1,3≥0, 2 is unrestricted in sign.
Solution:
Standard LP form:
Table E8.27
1
2
3
4
5
6
f
1.
0
0
0
0
-1
-4
0
infeasible
2.
0
0
0
-1
0
-5
1
infeasible
3.
0
0
0
4
-5
0
-4
infeasible
4.
0
0
-0.5
0
0
-3.5
2
infeasible
5.
0
0
-4
0
7
0
16
infeasible
6.
0
0
-5/3
7/3
0
0
13/3
infeasible
7.
0
0.5
0
0
0
-3.5
2
infeasible
8.
0
4
0
0
7
0
16
feasible
9.
0
5/3
0
7/3
0
0
13/3
feasible
10.
0
–
–
0
0
0
–
no solution
11.
1
0
0
0
0
-2
5
infeasible
12.
2
0
0
0
1
0
10
feasible
13.
5/3
0
0
2/3
0
0
23/3
feasible
14.
7/3
0
2/3
0
0
0
9
feasible
15.
7/3
-2/3
0
0
0
0
9
infeasible
Arora, Introduction to Optimum Design, 4e
8-20
8.28 ________________________________________________________________________________
Find all the basic solutions for the following LP problem using the Gauss-Jordan elimination
method. Identify basic feasible solutions and show them on graph paper.
Minimize = 91+ 22+ 33
Subject to −21− 2+ 33≤ −5
1−22+ 23≥ −2
1,2,3≥0
Solution:
Standard LP form:
Table E8.28
1
2
3
4
5
f
1.
0
0
0
-5
2
0
infeasible
2.
0
0
-5/3
0
-4/3
-15/3
infeasible
3.
0
0
-1
-2
0
-3
infeasible
4.
0
5
0
0
-8
10
infeasible
5.
0
1
0
-4
0
2
infeasible
6.
0
-1
-2
0
0
-8
infeasible
7.
2.5
0
0
0
4.5
22.5
feasible
8.
-2
0
0
-9
0
-18
infeasible
9.
4/7
0
-9/7
0
0
9/7
infeasible
10.
1.6
1.8
0
0
0
18
feasible