Engineering Optimization: Theory and Practice, Fourth Edition

160 Linear Programming I: Simplex Method

(u)The optimum solution of an LP problem cannot contain slack variables in the basis.

(v)If the infeasibility form has a nonzero value at the end of phase I, it indicates an

unbounded solution to the LP problem.

(w)The solution of an LP problem can be a local optimum.

(x)In a standard LP problem, all the cost coefficients will be positive.

(y)In a standard LP problem, all the right-hand-side constants will be positive.

(z)In a LP problem, the number of inequality constraints cannot exceed the number of

variables.

(aa)A basic feasible solution cannot have zero value for any of the variables.

Problems

3.1 State the following LP problem in standard form:

Maximizef= − 2 x 1 −x 2 + 5 x 3

subject to

x 1 − 2 x 2 +x 3 ≤ 8

3 x 1 − 2 x 2 ≥ − 18

2 x 1 +x 2 − 2 x 3 ≤ − 4

3.2 State the following LP problem in standard form:

Maximizef=x 1 − 8 x 2

subject to

3 x 1 + 2 x 2 ≥ 6

9 x 1 + 7 x 2 ≤ 108

2 x 1 − 5 x 2 ≥ − 35

x 1 , x 2 unrestricted in sign

3.3 Solve the following system of equations using pivot operations:

6 x 1 − 2 x 2 + 3 x 3 = 11

4 x 1 + 7 x 2 +x 3 = 21

5 x 1 + 8 x 2 + 9 x 3 = 48

3.4 It is proposed to build a reservoir of capacityx 1 to better control the supply of water to

an irrigation district [3.15, 3.17]. The inflow to the reservoir is expected to be 4. 5 × 106

acre-ft during the wet (rainy) season and 1. 1 × 106 acre-ft during the dry (summer)

season. Between the reservoir and the irrigation district, one stream(A)adds water to

and another stream(B)carries water away from the main stream, as shown in Fig. 3.16.

StreamAadds 1. 2 × 106 and 0. 3 × 106 acre-ft of water during the wet and dry seasons,

respectively. StreamBtakes away 0. 5 × 106 and 0. 2 × 106 acre-ft of water during the