Range of optimality The range of valuesover which an ...

.n

Problems

18-21

GLOSSARY

Range of optimality The range of values over which an objective function coefficient may vary without causing any change in the optimal solution (i.e., the values of all the vari ables will remain the same, but the value of the objective function may change).

Dual price The improvement in value of the optimal solution per unit increase in a con straint's right-hand-side value.

Range of feasibiSity The range of values over which a Z?,- may vary without causing the

current basic solution to become infeasible. The values of the variables in the solution will

change, but the same variables will remain basic. The dual prices for constraints do not change within these ranges.

Dual problem A linearprogramming problemrelated to the primal problem. Solution of the dual also provides the solution to the primal.

Primal problem The original formulation of a linear programming problem.

Canonical form for a maximization problem A maximization problem with all lessthan-or-equal-to constraints and nonnegativity requirements for the decision variables.

Canonical form for a minimization problem A minimization problem with all greaterthan-or-equal-to constraints and nonnegativity requirements for the decision variables.

Dual variable The variable in a dual linear programming problem. Its optimal value pro vides the dual price for the associated primal resource.

PROBLEMS

SELF

1. Consider the following linear programming problem.

Max

s.t.

5xj + 6x2 + 4xj

3X| + 4^2 + 2^3 < 120 x, + 2^2 + a:3 < 50 X, + 2^2 + 3JC3 > 30 X|,X2,X3 ^ 0

The optimal simplex tableau is

Basic

^3 Si

?2 ^3

5

6

4

0

00

00

4 ? ?0

-2

7

1

80

^3

4

0

2 - 1- -]

3

0

30

JCl

5

1

0

0

1

-2 0

20

9 - ^7

5

8

4

1

2

0 220

0 -2 0 -] -2 0

18-22

SELFf

SELF

Chapter 18 Simplex-Based Sensitivity Analysis and Duality

a. Compute the range of optimality for Cj. b. Compute the range of optimality for Cjc. Compute the range of optimality for .

1. For the HighTech problem, we found the range of optimality for g,, the profit contribu tion per unit of the Deskpro. The final simplex tableau is given in Section 18.1. Find the following: a. The range of optimality for C2. b. The range of optimality for c. The range of optimality for d. Suppose the per-unit profit contribution of the Portable (cj) dropped to $35. How would the optimal solution change? What is the new value for total profit?

3. Refer to the problem formulation and optimal simplex tableau given in Problem 1. a. Find the dual price for the first constraint. Find the dual price for the second constraint. Find the dual price for the third constraint. Suppose the right-hand side of the first constraint is increased from 120 to 125. Find the new optimal solution and its value. Suppose the right-hand side of the first constraint is decreased from 120 to 110. Find the new optimal solution and its value.

4. Refer again to the problem formulation and optimal simplex tableau given in Problem 1. a. Find the range of feasibility for Zj, . b. Find the range of feasibility for b^. c. Find the range of feasibility for 63.

5. For the HighTech problem, we found the range of feasibility for ft,, the assembly time available (see Section 18.1). a. Find the range of feasibility for b. Find the range of feasibility for b-^. c. How much will HighTech's profit increase if there is a 20-square-foot increase in the amount of warehouse space available (63)?

6. Recall the Par, Inc., problem introduced in Chapter 2. The linear program for this prob

lem is

Max

s.t.

lOx, -t-

VlO^l + 1x2 < 630

y2x, +

600

Ix, -t-

708

Vio^l -1- V4X2 ^ 135

^1 , > 0

Cutting and dyeing time Sewing time Finishing time Inspection and packaging time

where

X| = number of standard bags produced X2 = number of deluxe bags produced

'"?f!

Problems

The final simplex tableau is

18-23

Basis

X, ^2 10 9

Si . ,52^'

? ^4

0

0

0

0

X2

90 1

0 00

X,

10 1 0

?S4

0 00

9-

10 9 00

0 1 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download