Handout: (Side 1) Lindo Outputs; (Side 2) Duality

IFSM 300 – Class 12

March 6, 2002

Preliminaries

Handout: (Side 1) Lindo Outputs; (Side 2) Duality.
Class Web site reminder:

Download the Windows trial version of LINDO 6.1 from Their helps, which include an example, are good.

Homework 3 (in assignment 11): due Monday, March 11.
Assignment 12: read chapter 11.

Chapter 9 Example: Ancient Enterprises (Situation 9.1, Page 380)

Part 1 – The LP Model

Complete notes below. Summary here.

Develop the LP model (pages 380- 381).
Prepare the model to be input to Lindo.
Obtain the Lindo output.
Review the optimum values of the objective function and decision variables.
Interpret the corresponding values of slack and surplus variables.

Ancient Enterprises, Part 2 – Lindo Output

Complete notes below. Summary here.

Review the full Lindo report.
Review a “reference card” that summarizes concisely the meanings of different types of information in the Lindo report.
Discuss the four main information types. Give examples.
Reduced cost.
Dual price.
Objective coefficient range.
Righthand side range.

Ancient Enterprises, Part 3 – Primal-Dual Relationships

Complete notes below. Summary here.
What is a primal and what is a dual? Why are they interesting?
Preparing to write the dual – “canonical form.”
Rules for writing down the dual LP by inspection.
Connections between the primal and the dual.
Solving a dual from the primal solution, and vice versa.

Illustrating the meaning of a negative dual price.

Millionaire Q1

The reduced cost of a decision variable shows the change in that variable’s objective-function coefficient required to:

Change the solution.
Improve the optimal objective-function value by one unit.
Remove that variable from the solution.
Bring that variable into the solution. (!!)

Millionaire Q2

The dual price is also called the:

Batman price.
Shadow price. (!!)
Green Hornet price.
Superman price.

Millionaire Q3

The dual price of a constraint tells us how much the objective function changes (after resolving the LP) if we:

Decrease the right-hand side by a small amount.
Decrease the right-hand side by one unit.
Increase the right-hand side by a small amount.
Increase the right-hand side by one unit.(!!)

Millionaire Q4

The word “basis” in the LP output report refers to:

The decision variables.
The decision variables with positive values in the solution.
The decision, slack, and surplus variables with positive values in the solution. (!!)
All decision, slack, and surplus variables.

Millionaire Q5

The objective-coefficient-range report shows both the increase and the decrease in a decision variable’s objective-function coefficient that:

Does not change the dual price.
Does not change the value of any variable in the solution. (!!)
Does not change the reduced cost.
Does not change the value of the objective function in the solution.

Millionaire Q6

The righthand-side range report shows both the increase and the decrease in a constraint’s righthand-side value that:

Does not change the constraint.
Does not change the value of any variable in the solution.
Does not change the value of this constraint’s dual price. (!!)
Does not change the price of bread.

Millionaire Q7

The standard form (“canonical form” in the book) into which a minimization LP would be expressed in order to write its dual LP by our groundrules requires:

All nonnegative variables.
All equality constraints.
All  constraints.
All  constraints. (!!)

Millionaire Q8

If a MAX primal has an = constraint, we can convert it to the  needed to write the dual LP by means of:

Multiplying by –1.
Substituting  for =.
Substituting  and  for =. (!!)
Dividing by –1.

Millionaire Q9

To write a dual LP starting with a MIN primal, we do NOT:

Convert nonnegative variables into nonpositive variables. (!!)
Interchange objective-function coefficients and righthand-side parameters.
Convert from MIN to MAX.
Interchange column coefficients and row coefficients in the constraints.

Millionaire Q10

Comparing a primal LP with its dual, this element is the same in each:

Values of the decision variables.
Value of the objective function. (!!)
Dual prices.
Values of slack and surplus variables.

Millionaire Q11

Primal dual prices appear in the dual LP as:

Decision-variable values. (!!)
Dual prices.
Values of slack and surplus variables.
Dual primal prices.

Millionaire Q12

The primal-dual relationship in the principle of complementary slackness is:

Positive indicates zero.
Zero indicates positive.
Slack or surplus variable associated with decision variable.
All of the above. (!!)

Notes: Ancient Enterprises

Part 1 – The LP Model

The Problem. See pages 380-381.This is the problem statement:

Ancient Enterprises specializes in refurbishing and sale of antique clocks and stoves. Each refurbished clock can be sold for an estimated average profit of $20 and each stove for $40. A clock requires three labor hours and one hour of machine time for restoration, while a stove needs five labor hours and five hours of machine time for restoration. In addition, 25 pounds of a particular cast iron are needed to refurbish a typical antique stove. There are an estimated 1,000 machine hours and 1,800 labor hours available per month with current facilities. Also, management will provide funds sufficient to purchase a maximum 3,750 pounds of cast iron per month. It is possible to start the restoration in one month and complete the project in a subsequent time period. The company wants to refurbish the number of clocks and stoves that will maximize total monthly profit.

The LP Model. Going through the customary steps, we develop the LP model as follows:

Objective: maximize profit (last sentence of the problem statement).

Decision Variables:

x1 – number of clocks to refurbish

x2 – number of stoves to refurbish.

Objective Function: The unit-value coefficients are the profit in

One clock -- $20

One stove -- $40.

Thus the objective function Z may be written

Z = 20 x1 + 40 x2profit ($).

Constraints:

1,800 labor hours available. Unit labor hours are 3 per clock and 5 per stove.

3 x1 + 5 x2 1,800labor (hours).

1,000 machine hours available. Unit machine hours are 1 per clock and 5 per stove.

x1 + 5 x2 1,000machine (hours).

maximum 3,750 pounds of cast iron. Unit amounts of cast iron are 0 per clock and 25 per stove.

25 x2 3,750cast iron (pounds).

Nonnegative variables. A reminder:

(x1, x2 0).

To summarize, the LP model is

MAX Z = 20 x1 + 40 x2

subject to

3 x1 + 5 x2 1,800

x1 + 5 x2 1,000

25 x2 3,750

(x1, x2 0).

Lindo Version. We prepare this to enter into Lindo by (1) removing Z = , (2) writing subject to as ST, (3) using symbols on the regular keyboard to write the inequalities, (4)

deleting commas in numbers, and (5) deleting the nonnegative-variable reminder. Also, I prefer to space around each element. And we need not bother with lowering the subscripts. That produces the input

MAX 20 x1 + 40 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1000

25 x2 <= 3750

The resulting full output, including the range (sensitivity) analysis, is:

LP OPTIMUM FOUND AT STEP 2

OBJECTIVE FUNCTION VALUE

1) 12800.00

VARIABLE VALUE REDUCED COST

X1 400.000000 0.000000

X2 120.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 6.000000

3) 0.000000 2.000000

4) 750.000000 0.000000

NO. ITERATIONS= 2

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

X1 20.000000 4.000000 12.000000

X2 40.000000 60.000000 6.666667

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE

RHS INCREASE DECREASE

2 1800.000000 1200.000000 300.000000

3 1000.000000 100.000000 399.999969

4 3750.000000 INFINITY 750.000000

Solution. The solution is displayed in the top left: Z* = $12,800, x1* = 400 clocks, x2* = 120 stoves.

Immediately under that data, we see the values of slack and surplus variables in the solution. By inspection of the model, we know that all three constraints have slack variables (+ s) because all three inequalities are .

The report shows that the slack variables for labor hours and machine hours are 0 (rows 2 and 3 in Lindo since the objective function is row 1). This tells us that these two constraints are binding – that is, they actively restrain the decision variables from further increases.

The slack variable for cast iron, on the other hand, has a positive value, 750. Thus we know it is not binding. The amount of cast iron used -- 25 x2 = (25)(120) = 3,000 pounds – is less than the upper limit of 3,750 by the slack amount 750. The limit on cast iron, therefore, is not preventing the decision variables (actually, the one variable x2) from increasing more.

Notes: Ancient Enterprises

Part 2 – Lindo Output

Full Lindo Report. You obtain a full report from Lindo by asking for the range (sensitivity) analysis. We’ve already gone over the optimal values of the decision variables and the corresponding values of the slack/surplus variables (all +s slack variables in these  constraints). Now we consider the remaining data: reduced cost, dual prices, objective coefficient ranges, and righthand side ranges.

Degeneracy. Recall from class 11 that if m is the number of constraints, a clean (nondegenerate) solution has m positive variables (including slack and surplus variables), while the other variables are zero. If the number of positive variables in the solution is less than m, the solution is said to be degenerate, which tells us that the computer output may need special interpretation.

Reference Card. Here is a reference card to summarize what those Lindo-report numbers tell us. Next we’ll consider examples of each type of information:

Recap of LINDO Outputs

Reduced Cost  OBJ coefficient to bring variable into

solution

(degen:  shown is minimum)

Dual Price  OBJ when  RHS = +1

(+ dual price means OBJ better, - means

worse)

OBJ Coefficient Range increase/decrease that does NOT

change ANY x*or s* (basis)

(degen: ’s shown are

minimum)

RHS Range increase/decrease that does NOT

change THIS constraint’s dual price

(degen: some ranges will be 0,

giving no information)

Note If you have a degenerate solution, you can explore sensitivities by recomputing with altered inputs.

Reduced Cost. The reduced cost associated with a decision variable is the amount by which the coefficient of that variable in the objective function would have to change for the variable to be brought into the solution – that is, to have a positive value in the optimal solution. Thus, when the variable is in the optimal solution already, its reduced cost is zero.

The foregoing applies to a nondegenerate solution. With a degenerate solution, the reduced cost shows the least amount of change that might be necessary – it could be more.

For example, in the report above we see that the variables x1 and x2 already are in the solution and therefore have reduced costs of zero:

MAX 20 x1 + 40 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 12800.00

VARIABLE VALUE REDUCED COST

X1 400.000000 0.000000

X2 120.000000 0.000000

Let’s look at another case -- created by revising the coefficient of x1 in the objective function -- where x2 is out of the solution:

MAX 25 x1 + 40 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 15000.00

VARIABLE VALUE REDUCED COST

X1 600.000000 0.000000

X2 0.000000 1.666667

Since the reduced cost of x2, not in the solution now, is 1.66…, we know that at least this amount must be added to the coefficient of x2 in the objective function to bring x2 back into the solution. So let’s increase the x2 coefficient 40 by say 2, making it 42:

MAX 25 x1 + 42 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 15040.00

VARIABLE VALUE REDUCED COST

X1 400.000000 0.000000

X2 120.000000 0.000000

As expected, that returned x2 to the solution.

Dual Price. The dual price is called a shadow price in the book. Recall our original example:

MAX 20 x1 + 40 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 12800.00

VARIABLE VALUE REDUCED COST

X1 400.000000 0.000000

X2 120.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 6.000000

3) 0.000000 2.000000

4) 750.000000 0.000000

The 6.000000 for the constraint on line 2 (labor limit) means that an increase of one unit in the righthand side (1,800 to 1,801 labor hours) would result, after resolving, in an improvement of $6.00 in the objective function:

MAX 20 x1 + 40 x2

3 x1+ 5 x2 <= 1801

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 12806.00

VARIABLE VALUE REDUCED COST

X1 400.500000 0.000000

X2 119.900002 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 6.000000

3) 0.000000 2.000000

4) 752.500000 0.000000

If we instead reduce the righthand side by one unit, the objective function becomes $6.00 worse:

MAX 20 x1 + 40 x2

3 x1+ 5 x2 <= 1799

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 12794.00

VARIABLE VALUE REDUCED COST

X1 399.500000 0.000000

X2 120.099998 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 6.000000

3) 0.000000 2.000000

4) 747.500000 0.000000

Note well that a positive value for a dual price indicates that the objective function improves by the amount of the dual price. Conversely, a negative dual price indicates the amount by which the objective function becomes worse.

If the model entails minimization, therefore, a positive dual price shows the amount by which a one-unit increase in the righthand side causes the objective function to become smaller (which is improvement when we minimize).

Objective Coefficient Range. A full Lindo report mentions the word “basis.” This term basis has a particular meaning in linear algebra (the algebra of vectors and matrices). For us, it’s fine to think of a basis as the set of variables (including the slack and surplus variables) with positive values in a solution. As noted previously, if a solution is nondegenerate, and if there are m constraints, the number of variables in the basis is m. Other variables will have value zero.

The objective coefficient range is the amount of increase or decrease that could take place in a variable’s coefficient in the objective function without changing the optimal solution (not change values of anyvariables in the basis). With a degenerate solution, as was true of the reduced cost, this data shows us the least amount of change. Note well: In this situation, the “solution” that stays the samerefers to values of the positive variables in the optimum solution, not to the value of the objective function, which changes

For instance, for our original Ancient Enterprises model, the Lindo report shows:

MAX 20 x1 + 40 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 12800.00

VARIABLE VALUE REDUCED COST

X1 400.000000 0.000000

X2 120.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 6.000000

3) 0.000000 2.000000

4) 750.000000 0.000000

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

X1 20.000000 4.000000 12.000000

When we revise the coefficient 20 of x1 to something inside the range (between 20 + 4 and 20 – 12), say to 23, we see that the new optimum solution keeps the same variable values but, of course, has a different value of the objective function:

MAX 23 x1 + 40 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 14000.00

VARIABLE VALUE REDUCED COST

X1 400.000000 0.000000

X2 120.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 7.500000

3) 0.000000 0.500000

4) 750.000000 0.000000

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

X1 23.000000 1.000000 15.000000

Should we instead revise the coefficient to 25, thereby falling outside the range, then the basis in the optimum solution changes:

MAX 25 x1 + 40 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1000

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 15000.00

VARIABLE VALUE REDUCED COST

X1 600.000000 0.000000

X2 0.000000 1.666667

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 8.333333

3) 400.000000 0.000000

4) 3750.000000 0.000000

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

X1 25.000000 INFINITY 0.999999

Righthand Side Range. The right-hand side range is the amount of increase or decrease that could take place in a constraint’s righthand side without changing its corresponding dual price. In a degenerate solution, some of these ranges will appear as zero, giving us no information.

To illustrate, in the report on the original model, we observe that the range of the righthand side of the machine constraint 1000 is between 1000 + 100 and 1000 – 400, and that the dual price of that constraint is $2.00. If we revise the righthand side within the range, say to 1050, the new solution retains the same dual price of $2.00. But if we revise the righthand side outside the range, say to 1150, the dual price then changes – to zero in this case:

MAX 20 x1 + 40 x2

3 x1+ 5 x2 <= 1800

x1 + 5 x2 <= 1150

25 x2 <= 3750

OBJECTIVE FUNCTION VALUE

1) 13000.00

VARIABLE VALUE REDUCED COST

X1 350.000000 0.000000

X2 150.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 6.666667

3) 50.000000 0.000000

4) 0.000000 0.266667

Notes: Ancient Enterprises

Part 3 – Primal-Dual Relationships

Overview. Every LP model has an associated LP model called the dual. The dual LP is something like a mirror image of the original, called the primal.

The dual is helpful in research on solution methods. The main reason we’re interested, however, is that sometimes the dual has substantially fewer constraints and therefore may be faster to solve in practice. Another reason to be interested is that duality is a famous aspect of LP models

Canonical Form. There are various ways to go from an LP model we have in hand (the primal) to its dual. We’ll stick with the way in the book.

Recall that to understand slack and surplus variables, we created a standard form of the original LP (the equation form). The same idea applies to duality, except now the standard form is different. In the book, this particular standard form is called canonical form:

For a MAX LP, all constraints must be .

For a MIN LP , all constraints must be .

In cases where the original LP is not already in canonical form, the first step toward working with the dual is to revise any nonconforming constraints. The methods are these:

Converting  into  , or  into  : Multiply by –1.

Example:(1)5 x1 + 7 x2 10

(1)x (-1)-5 x1 – 7 x2 -10

Converting = into  , or converting = into  : Create simultaneous inequalities (one  and one ). Then convert the one not in the correct direction.

Example:(1) 5 x1 + 7 x2 = 10

(1a) 5 x1 + 7 x2 10

(1b) 5 x1 + 7 x2 10

(1a) 5 x1 + 7 x2 10

(1b) x (-1)-5 x1 - 7 x2  -10

Writing the Dual LP.Once the primal (original) LP model is in canonical (standard) form for the purpose of writing its dual, you then may specify the dual by inspection.

The rules to do this are simple: switch MAX to MIN or MIN to MAX, reverse the direction of inequalities, interchange the righthand-side and objective-function coefficients, and interchange the column and row constraint coefficients (on the lefthand sides of the constraints). In reference style, these rules, again, are:

MAX  MIN



OBJ  RHS

COLUMNS  ROWS

To illustrate, if we begin with our regular Ancient Enterprises LP, then we can immediately write down its dual LP (using the symbol u for a dual LP decision variable):