Linear Programming: The Graphical solution

We provide here an example that demonstrates the algebraic development in the Graphical Solution. It is complementary to the geometric development in fig 8-3., 8-4., and 8-5 in pages 269, 270 and 272 respectively. In your solution you should consulidate these three figures into a single graph, which is complementary to the development here.

In yellow we introduce remarks that you need not reproduce.

Please also notice that many problems in chapter 8 are not word problems.  In these problems you are not asked to perform a set up, but only the solution procedure.  In this case you need not define the decision variables or the objective. 

Step 1. Set Up

1.1 Definition of Decision variables ( The three Ns—Name, Notation, uNit of measurement)

X_T- number of tables, unit of measurement = 1 table.

X_C- number of chairs, unit of measurement = 1 chair.

1.2. The objective:

Max P = 6X_T + 8X_C

Where P is a profit,  unit of measurement is 1 dollar of profit.

Notice that 6 represents the contribution to the objective (Profit) of a unit of X_T (one table).   (What is a unit is defined in 1.1 as the unit of measurement).

Similarly, 8 represents the contribution to the objective (Profit) of a unit of X_C (one chair).

1.2 S.t. (Subject to)

30X_T + 20X_C < 300 ( I )

5X_T + 10X_C <  110 ( II )

X_T > 0 ( III)

X_C > 0 ( IV)

Step 2. Boundaries of the constraints and their intercepts

I. Boundary of Const. I.

30X_T + 20X_C = 300

XT	XC
0	15
10	0

II. Boundary of Const. II.

5X_T + 10X_C = 110

XT	XC
0	11
22	0

III. Boundary of Const. III.

X_T = 0

XT	XC
0	0
0	3(arb)

!V. Boundary of Const. IV.

X_C = 0

XT	XC
0	0
5(arb)	0

(The selection of 3 and 5 are arbitrary)

Step 3. Plotting the boundary line of the constraint and determining the constraint’s valid side.

Constraint	Test Point	Result
I	(0,0)	T
II	(0,0)	T
III	(1,1)	T
IV	(1.1)	T

Step 4. Establishing the feasible set. The feasible set is the collection (loci) of all the points that satisfy every constraint.

Use English capital letters, to mark the corners of the feasible set, beginning with labeling the origin as O and following by A, B, C, etc. The order of marking is clock wise. If the origin is not in the feasible set, begin with A, B, C. Notice this stricter and more refined distinction was not made in fig. 8-3., in page 269. You are required to follow the stricter and more refined distinction. For this purpose change the corner notations in fig. 8-3. Also introduce the corner notations in fig. 8- 4. in page 270.

Step 5. Two arbitrary Objective Lines for finding Direction of Improvement and Objective's slope.

P₁ = 48= 6X_T + 8X_C

XT	XC
0	6
8	0

P₂ = 72= 6X_T + 8X_C

XT	XC
0	9
12	0

(The Choice of the 48 and 72 profit levels are arbitrary, as long as they make sense graphically, i.e., leading to profit lines that are on the same order of magnitude as the constraints.)

Step 6. Visually identifying the MAP (Most Attractive Point)

MAP is Point B.

Step 7. Algebraic and numerical determination of MAP.

Algebraic Declaration:

MAP is point B the intersection of the boundaries of constraints I and II.

30X_T + 20X_C = 300 ( I )

5X_T + 10X_C = 110 ( II )

Solving these two equation with two unknowns:

30X_T + 20X_C =300 ( I )

-2(5X_T + 10X_C = 110) ( II )

20X_T + 0X_C = 80

X_{T opt} = 80/20 = 4

Substituting the value of X_T into (I) we obtain,

30(4) + 20X_C = 300

20X_C = 300 – 30(4) = 300 –120 = 180

X_{C opt} = 180/20 = 9

Step 8. Finding the optimal value of the objective.

By substituting the optimal levels of X_T and X_C into the objective we obtain

Max P = 6(4)+ 8(9) = 96