Www.swlearning.com



CHAPTER 2

An Introduction to

Linear Programming

21

KEY CONCEPTS

ILLUSTRATED ANSWERED

CONCEPT PROBLEMS PROBLEMS

Formulation 7,8 15,16

Minimization 2,5 9,10,15

Standard Form 1 14

Slack/Surplus Variables 1 16

Equal-to Constraints 3,5 14

Redundant Constraints 5,7 12,13

Extreme Points 2,5 11,16

Alternative Optimal Solutions 7 10,11,15

Infeasibility 4 14

Unbounded 4 11

Spreadsheet Example 2

REVIEW

1. A mathematical programming problem is one that seeks to maximize an objective function

subject to constraints. If both the objective function and the constraints are linear, the

problem is referred to as a linear programming problem.

2. Linear functions are functions in which each variable appears in a separate term raised to

the first power and is multiplied by a constant (which could be 0).

3. Linear constraints are linear functions that are restricted to be "less than or equal to", "equal to", or "greater than or equal to" a constant.

4. The maximization or minimization of some quantity is the objective in all linear

programming problems.

5. A feasible solution satisfies all the problem's constraints.

6. A linear program which is overconstrained so that no point satisfies all the constraints is

said to be infeasible. Changes to the objective function coefficients do not affect the

feasibility of the problem.

7. An optimal solution is a feasible solution that results in the largest possible objective

function value, z, when maximizing or smallest possible z when minimizing.

8. A graphical solution method can be used to solve a linear program with two variables.

9. If a linear program possesses an optimal solution, then an extreme point will be optimal.

10. If a constraint can be removed without affecting the shape of the feasible region, the

constraint is said to be redundant. If changes are anticipated to the linear programming

model, constraints which were redundant in the original formulation may not be redundant

in the revised formulation.

11. In the graphical method, if the objective function line is parallel to a boundary constraint in

the direction of optimization, there are alternative optimal solutions, with all points on this

line segment being optimal.

12. A feasible region may be unbounded and yet there may be optimal solutions. This is

common in minimization problems and is possible in maximization problems.

13. The feasible region for a two-variable linear programming problem can be: a) nonexistent,

b) a single point, c) a line, d) a polygon, or e) an unbounded area.

14. Any linear program either (a) is infeasible, (b) has a unique optimal solution or alternate

optimal solutions, or (c) has an objective function that can be increased without bound.

15. A linear program in which all the variables are non-negative and all the constraints are

equalities is said to be in standard form. Standard form is attained by adding slack

variables to "less than or equal to" constraints, and by subtracting surplus variables from

"greater than or equal to" constraints. They represent the difference between the left and

right sides of the constraints.

16. A nonbinding constraint is one in which there is positive slack or surplus when evaluated

at the optimal solution.

17. Slack and surplus variables have objective function coefficients equal to 0. If, however,

extra resources could be sold at a profit, or if there were a penalty for surplus resources,

the objective function coefficients would not be 0 and these variables would, in effect,

become new decision variables.

GRAPHICAL SOLUTION PROCEDURE

1. Graph the constraints and shade in the feasible region, considering the feasible side of

each constraint line.

2. Set the objective function equal to any arbitrary constant and graph it. If the line does not

lie in the feasible region, move it (maintaining its slope) into the feasible region.

3. Move the objective function line parallel to itself in the direction that increases its value

when maximizing (decreases its value when minimizing) until it touches the last point(s) of

the feasible region.

4. If the optimal extreme point falls on an axis (say, x2 axis), use the binding constraint

equation to solve for the unknown x* (in this case x2*, since x1* is zero). Otherwise, solve

the two equations (binding constraints) in two unknowns (x1* and x2*) that determine the

optimal extreme point.

5. Find z by substituting x1* and x2* in the objective function.

FLOW CHART OF

GRAPHICAL L.P. SOLUTION PROCEDURE

[pic]

ILLUSTRATED PROBLEMS

NOTE: Plotting an initial objective function line involves little more than reversing the objective coefficients for x1 and x2. Consider Problem 1 below. The objective line will cross the x1 axis at 4 (x2's coefficient) and the x2 axis at 3 (x1's coefficient). If the coefficients are too large (or small) for convenient graphing, scale them down (or up) in a consistent manner by dividing (or multiplying) both by, say, 10.

PROBLEM 1

Given the following linear program:

MAX z = 3x1 + 4x2

s.t. 2x1 + 3x2 < 24

3x1 + x2 < 21

x1 + x2 < 9

x1, x2 > 0

a) Solve the problem graphically.

b) Write the problem in standard form.

c) Given your answer to (a), what are the optimal values of the slack variables.

SOLUTION 1

a) (1) Graph the constraints. (See graph on next page.)

Constraint 1: When x1 = 0, then x2 = 8; when x2 = 0, then x1 = 12.

Connect (12,0) and (0,8). The "" side is above this line.

Constraint 2: When x2 = 0, then x1 = 3. But setting x1 to 0 will yield x2 = -12,

which is not on the graph. Thus, to get a second point on this line, set

x1 to any number larger than 3 and solve for x2: when x1 = 5, then

x2 = 8. Connect (3,0) and (5,8). The ">" side is to the right.

Constraint 3: When x1 = 0, then x2 = 4; when x2 = 0, then x1 = 4. Connect

(4,0) and (0,4). The ">" side is above this line.

Shade in the feasible region.

(2) Graph the objective function by setting the objective function equal to an arbitrary

constant (say 20) and graphing it. For 5x1 + 2x2 = 20, when x1 = 0, then x2 = 10;

when x2= 0, then x1 = 4. Connect (4,0) and (0,10).

(3) Move the objective function line in the direction which lowers its value until it

touches the last point of the feasible region, determined by the last two constraints.

(4) Solve these two equations in two unknowns. 4x1 - x2 = 12 and x1 + x2 = 4

Adding these two equations gives: 5x1 = 16 or x1 = 16/5. Substituting this into

x1 + x2 = 4 gives: x2 = 4/5.

(5) Solve for z = 5x1 + 2x2 = 5(16/5) + 2(4/5) = 88/5. Thus the optimal solution is

x1 = 16/5; x2 = 4/5; z = 88/5.

[pic]

b) (5,3) lies in the feasible region, but it is not an extreme point and can never be optimal.

c) Spreadsheet showing data and formulas

Steps in Using Excel Solver:

Step 1: Select the Tools pull-down Menu.

Step 2: Select the Solver option.

Step 3: When the Solver Parameters dialog box appears:

Enter C12 in the Set Target Cell box.

Select the Min option.

Enter B10:C10 in By Changing Cells box.

Choose Add.

Step 4: When Add Constraint dialog box appears:

Enter B15:B17 in Cell Reference box.

Select >=.

Enter D15:D17 in Constraint box.

Choose OK.

Step 5: When the Solver Parameters dialog box appears:

Choose Options.

Step 6: When the Solver Options dialog box appears:

Select Assume Linear Model.

Select Assume Non-Negative.

Choose OK.

Step 7: When Solver Parameters dialog box appears:

Choose Solve.

(continued)

Step 8: When Solver Results dialog box appears:

Select Keep Solver Solution.

Choose OK to produce optimal solution output.

PROBLEM 3

Given the following linear program:

MAX z = 4x1 + 5x2

s.t. x1 + 3x2 < 22

-x1 + x2 < 4

x2 < 6

2x1 - 5x2 < 0

x1, x2 > 0

NOTE: If a constraint’s righthand-side value is 0, the constraint line will pass through the origin (x1 = 0, x2 = 0). This is the case with the fourth constraint above.

a) Solve the problem by the graphical method.

b) What would be the optimal solution if the second constraint were -x1 + x2 = 4?

c) What would be the optimal solution if the first constraint were x1 + 3x2 > 22?

SOLUTION 3

a) (1) Graph the constraints.

Constraint 1: When x1 = 0, x2 = 22/3; when x2 = 0, then x1 = 22. Connect

(22,0) and (0,22/3). The "" side is to the right of this line.

Constraint 2: This is a horizontal line through x2 = 6. The ">" side is above this

line.

Constraint 3: This is a horizontal line through x2 = 15. The " ................
................

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

Google Online Preview   Download