Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

Подождите немного. Документ загружается.

142 DUALITY

5.17 Consider the linear program

Minimize c

x = z

subject to Ax ≤ b

x ≥ 0,

where

A =



21−4

−1 −11

100



,b=



−1



,c=



−210



The ﬁnal tableau, where s

, s

, and s

are slacks, is

(−z) x

1 0 100024

0 0 −301422

0 1 000012

0 0 −110111

(a) What is an optimal solution x

∗

? What is an optimal solution π

∗

for the

dual? What is the optimal objective value z

∗

? What is the optimal basis

for the primal and what is its inverse?

(b) Suppose the right-hand side is changed to

b =(1, −1, 2)

. Does the current

basis remain feasible?

. Does the

current solution remain optimal?

5.18 Consider the linear program

Minimize a

x − b

y = z

subject to x − y = c

x ≤ 0

y ≤ 0,

where a, b, c are n-vectors.

(a) Exhibit a feasible solution.

(b) Since the problem is feasible, either there exists an optimal solution or there

exists a class of solutions with unbounded objective value. Find the dual

and using it, derive necessary and suﬃcient conditions on a and b for when

the primal has an optimal solution.

and complementary slackness to ﬁnd a basic optimal solution to the primal.

(d) Eliminate y from the LP (by substituting y = x − c) and re-derive your

conditions for a bounded optimum for the primal without referring to the

dual problem. (Hint: This should agree with your answer in (b).)

5.19 What is the dual linear program for

Minimize c

subject to Ay = x

y ≤ b.

5.6 PROBLEMS 143

5.20 What is the dual linear program for

Minimize c

subject to b

≤ Ax ≤ b

l ≤ x ≤ u,

where A is an m × n matrix. What would be the dual if we were maximizing

instead of minimizing?

5.21 Suppose that a linear program in standard form (5.5) has a ﬁnite optimal value.

Show that if the right-hand side is changed from b to some b



, the resulting linear

program is either infeasible or has a ﬁnite optimal value. Thus, by changing the

right-hand side b we cannot obtain an LP that is unbounded below.

5.22 In practical applications of linear programming, the scaling of coeﬃcients is

important for numerical reasons and for knowing how to interpret model results.

Consider a typical linear program and its associated dual:

Minimize c

x = z

subject to Ax ≥ b,

x ≥ 0.

Maximize b

y = v

subject to A

y ≤ c,

y ≥ 0.

What is the eﬀect of each of the actions (a), (b), (c), (d) below

(a) Multiplying a row of [Ab] by a factor γ;

(b) Multiplying the right-hand side b by a factor γ>0;





by a factor γ>0;

(d) Multiplying the objective row c by a factor γ (consider both positive and

negative γ)

upon

• the optimal objective value;

• the optimal choice of decision variables and their optimal activity levels;

• the optimal values of the dual variables.

This page intentionally left blank

CHAPTER 6

EQUIVALENT

FORMULATIONS

Real world problems tend to be “dirty,” that is, there is a certain softness—a lack of

precision—in their deﬁnition that often permits them to have two or more ways of

being expressed mathematically. These diﬀerent expressions may not be equivalent

in the mathematical sense that there is an exact one-to-one correspondence between

their solutions. However, from the point of view of a person looking for an answer,

either is an equally satisfactory statement of the practical problem to be solved. One

of these could turn out to be completely amenable to mathematical analysis and

solution while another could be computationally hopeless. Only through detailed

knowledge of the application and knowledge of what is intractable can one decide

which one of these two acceptable formulations is best to use. Linear programming

models have been successful because many large problems can be on the one hand

satisfactorily formulated by planners as linear programs and can be on the other

hand solved using computers.

6.1 RESTRICTED VARIABLES

Typically, the variables x

have a lower bound of 0. In practice, however, the

variables x

may have speciﬁed upper or lower bounds, or both. For example, x

≥

−10. In this case the user could deﬁne a new variable x



= x

+ 10 and substitute



−10 for x

into the equations and solve the resulting system as a “standard” LP.

If x

has both a ﬁnite upper and lower bound this simple substitution trick is not

suﬃcient to reduce the system to an equivalent standard form; an additional slack

variable and equation are needed.

145

146 EQUIVALENT FORMULATIONS

It would appear that having speciﬁed lower bounds increases the work required

by the user to set up the problem as a standard linear program. Fortunately, most

linear programming software makes it easy for the user to state the bounds. In

Chapter 3 we discussed special techniques for eﬃciently solving linear programs

whose variables have both upper and lower bounds.

6.2 UNRESTRICTED (FREE) VARIABLES

An interesting special case occurs when x

has neither a speciﬁed ﬁnite upper or

lower bound. This is called the unrestricted case. Except for possible numerical dif-

ﬁculties, we could eliminate any unrestricted variable by using one of the equations

that it is in with a nonzero coeﬃcient, to solve for it and substitute its expression

in terms of the other variables into the other equations. Another approach is to

replace each such variable x

by the diﬀerence of two nonnegative variables,

= x

− x

−

, where x

≥ 0,x

−

≥ 0.

The variable x

is called the positive part of x

and the variable x

−

is called the

negative part of x

. The variables x

and x

−

are deﬁned as follows:



if x

≥ 0

0ifx

< 0

−



0ifx

≥ 0

−x

if x

< 0

We shall show later that there exists an optimal solution for which either x

or x

−

= 0 or both equal zero.

Having no speciﬁed bounds appears to increase the work required by the user

to set up the problem as well as to increase the number of variables. Fortunately,

special techniques, such as those discussed in Chapter 3, not only allow the user

to specify the problem in a “user-friendly” way, but also in a way that does not

increase the size of the problem or the computational eﬀort required to specify and

solve such problems.

 Exercise 6.1 Suppose that you have an n-dimensional linear program with 1 ≤ k ≤ n

unrestricted variables. That is,

Minimize



j=1

= z

subject to



j=1

≥ b

for i =1,...,m.

Show that it is possible to modify the linear program to one that has all nonnegative

variables by replacing the unrestricted variables x

by restricted variables ¯x

≥ 0 and one

additional unrestricted variable x

n+1

6.3 ABSOLUTE VALUES 147

|x|



Figure 6-1: Absolute Value Function

 Exercise 6.2 Consider the problem Min x subject to x = 3. Since x is an unrestricted

variable, we replace it by x = u − v, where u ≥ 0, v ≥ 0 and we now have

Minimize −u + v = z

subject to u − v =3.

Assume that a basic feasible solution u and simplex multiplier π = −1 have been de-

termined. Checking for optimality, the v column prices out to zero. Hence the basic

feasible solution is optimal. However, due to slight round-oﬀ error, it apparently prices

out −0.0000000000001 and the software therefore chooses to introduce v as the incoming

variable. Discuss what happens next and what safeguards must be put into the simplex

algorithm software to prevent this from happening.

6.3 ABSOLUTE VALUES

An absolute value variable |x| is deﬁned as a function of x as follows:

|x| =



x if x ≥ 0,

−x if x<0.

The plot of the function is illustrated in Figure 6-1. When the absolute value

variables appear in a general system of equations, it is not possible to reformulate

the problem as a linear program. However, when such functions appear only as

terms in the objective function, it is sometimes possible to reformulate the model

as a linear program.

Consider the following problem, where the objective is to minimize the weighted

sum of absolute values subject to linear constraints, where the weights c

are non-

148 EQUIVALENT FORMULATIONS

negative.

Minimize



j=1

| = z, where c

≥ 0 for j =1,...,n,

subject to



j=1

= b

, for i =1,...,m.

(6.1)

We can replace in the equations each variable x

by the diﬀerence of its positive

and negative parts, that is,

= x

− x

−

, where x

≥ 0,x

−

≥ 0.

In the objective function, where the functions |x

| appear, |x

| can be replaced by

+ x

−

, the sum of the positive and negative parts, provided that x

−

= 0. This

results in the following modiﬁed problem:

Minimize



j=1

+ x

−

)=z

subject to



j=1

− x

−

)=b

for i =1,...,m,

≥ 0,x

−

≥ 0 for j =1,...,n,

−

= 0 for j =1,...,n.

(6.2)

The above problem is not a linear program because of relations x

−

in (6.2). However, if c

≥ 0 for all j, it can be shown (see Lemma 6.1) that even

if conditions x

−

= 0 in (6.2) are dropped, either x

or x

−

will be zero at an

optimum solution. Therefore, in the case c

≥ 0 for all j, the above problem reduces

to a linear program.

LEMMA 6.1 (Optimality Property) In the problem deﬁned by (6.2), if each

≥ 0, then there exists a ﬁnite optimum solution to

Minimize



j=1

+ x

−

)=z

subject to



j=1

− x

−

)=b

for i =1,...,m,

≥ 0,x

−

≥ 0 for j =1,...,n,

(6.3)

such that either x

or x

−

is zero provided there is a feasible solution.

Proof. Let ˆx

=(ˆx

, ˆx

,... , ˆx

)

and ˆx

−

=(ˆx

−

, ˆx

−

,... , ˆx

−

)

be a feasi-

ble solution to problem (6.3). For j =1,...,n deﬁne v

= min(ˆx

, ˆx

−

) and use

6.4 GOAL PROGRAMMING 149

these v

’s to deﬁne

¯x

=ˆx

− v

¯x

−

=ˆx

−

− v

(6.4)

The ¯x

,¯x

−

are clearly also a feasible solution to problem (6.3) with the additional

property that either ¯x

= 0 or ¯x

−

= 0. Therefore, they are also a feasible solution

to the problem deﬁned by (6.2). Furthermore, if each c

≥ 0, then

(¯x

+¯x

−

)=c

(ˆx

+ˆx

−

) − 2



j=1

≤ c

(ˆx

+ˆx

−

Thus, no matter what the solution, we can always ﬁnd an equal or better solution

with either the positive part or negative part of each x

equal to zero. This completes

the proof.

The lemma shows that if problem (6.1) has an optimum solution, then it can be

found by solving the linear program (6.3) and setting x

= x

− x

−

 Exercise 6.3 Assume in problem (6.1) that some c

< 0 and that feasible solutions

exist. Construct an example where the minimum z is ﬁnite. Show for such an example

that if we try to solve by means of (6.3) we will obtain a class of feasible solutions to (6.3)

where the minimum z of (6.3) tends to −∞.

 Exercise 6.4 Generalize Lemma 6.1 where (6.1) is replaced by

Minimize



j∈S

| +



j∈S

= z

subject to



j=1

= b

for i =1,...,m,

≥ 0 for j ∈S,

≥ 0 for j ∈S.

(6.5)

 Exercise 6.5 Extend the discussion in this section to list the conditions under which

the following problem can be formulated as a linear program.

Minimize



i=1





j=1



= z

subject to



j=1

= b

for i =1,...,m.

150 EQUIVALENT FORMULATIONS

6.4 GOAL PROGRAMMING

So far, all the linear programming examples have had a simple objective that could

be incorporated into a single objective function. In some practical situations there

may be no clear single objective to be minimized but rather several objectives that

we would like to minimize at the same time, which, in general, is nonsense because

the objectives are incompatible. Nevertheless, humans to do this all the time; and

there are a few situations where the objectives are not incompatible and it may

make sense to do so, as we shall see.

The technique, referred to as goal programming, endeavors to satisfy multiple

objectives simultaneously. As noted, this may not always be possible because the

various objectives may conﬂict with each other. One possibility is to give all the

objectives roughly equal priorities but to give diﬀerent weights measuring their

relative importance to one another and to add the diﬀerent objectives together.

 Exercise 6.6 Consider the product mix problem of Section 1.4.1. Assuming the same

production constraints, modify the objective function so that proﬁt from each of the desks

is 10, 20, 18, and 40 respectively. As before, the objective is to maximize proﬁt. However,

it may also be important to try to maximize the production of Desk 1, which sells at a

lower price than the other desks, in order to satisfy a community requirement of always

having some of the cheaper desks available. State the two objective functions that you

would want to consider in this case. Assign a relative weighting to these two objectives in

order to formulate a goal program and optimize the linear program associated with this

goal program.

Other possibilities are when weights are assigned to deviations from goals or

when the objectives have priorities associated with them. These are described in

the next two subsections.

WEIGHTED GOAL PROGRAMMING

In general, suppose that there are K objectives, z

,... ,z

, with respective goal

values g

,... ,g

.Inweighted goal programming, a composite objective function

is created of the form

z =



k=1

− z

where the function φ

is deﬁned by

(y)=



y if y ≥ 0,

y if y<0,

where α

≥ 0 is the penalty (or weight) of overshooting the goal, and β

≥ 0is

the penalty (or weight) of undershooting the goal. For example the objectives for a

manufacturing corporation may to be to maximize proﬁt while attempting to keep

the capital expenditures within a speciﬁed budget. Note that the budget restriction

6.4 GOAL PROGRAMMING 151

is not a rigid constraint since it need not be satisﬁed. In this case we call the right

hand side of the budget restriction a goal. Depending on how important it is to stay

within budget, we can attach a penalty cost to the violation of the budget goal.

The goal programming problem as deﬁned above falls under a class of problems

called separable nonlinear programming. When the constraints are linear, we can

easily convert the problem into a linear programming problem as long as the weights

and β

are nonnegative for all k =1,...,K. Deﬁne

− z

= u

− u

−

≥ 0,u

−

≥ 0,k=1,...,K.

Each φ

can then be replaced by the linear function

− z

)=α

+ β

−

together with the additional constraints u

≥ 0 and u

−

≥ 0. The resulting problem

is a linear program provided α

and β

are nonnegative for all k =1,...,K.

PRIORITY GOAL PROGRAMMING

In Priority Goal Programming the objectives fall into diﬀerent priority classes. We

assume that no two goals have equal priority. In this case we ﬁrst satisfy the

highest priority objectives and then if diﬀerent solutions tie for the optimum, the

tie is resolved by the next set of priorities, and so on.

We will describe two methods for solving such problems. The ﬁrst solves a

number of linear programs sequentially. First, order the objectives so that z

has

the highest priority, z

has the next highest priority, and so on. The objective of the

ﬁrst linear program is the linear form z

with highest priority. The resulting linear

program is solved. Nonbasic variables with reduced costs diﬀerent from zero are

dropped (this technique for identifying alternative optimal solutions was discussed in

Section 3.2.4) and the next priority objective form z

is made into the new objective

function. (Alternatively, we could optimize using z

and setting the upper and lower

bounds on the nonbasic variables with positive reduced costs to be 0.) After the new

linear program is solved, the process is continued until all the priorities have been

converted into objective forms. The process also terminates if a unique solution

is found. There is a technique that was discussed in Section 3.2.4 for ﬁnding out

whether or not an optimal solution is unique.

 Exercise 6.7 Another technique would be to make the ﬁrst objective z

a constraint

by setting the value of z

equal to its optimal value and then using the next priority

objective form z

as the new objective function. Discuss what numerical diﬃculties may be

encountered. Suggest a method that may possibly help in getting around such diﬃculties.

 Exercise 6.8 Solve, using the software, Exercise 6.6 by the method of Exercise 6.7.

Show that if the optimal value of z

is not correctly inputted into the second linear program

it can cause numerical diﬃculties if set too small. Graph the dual problem and identify

the corner solutions that are tied for minimum costs. Which corner solution was selected

and why?