Examples of Linear-Programming Problems

In this section, we discuss two additional formulation examples. These examples are more sophisticated than the product-mix problem. Click on the titles below to view these examples (which are in the pdf format).

Example 1: The Production-Planning Problem

Example 2: The Investment Problem

For additional formulation examples, browse Section 3.4 of the text.

We now briefly discuss how to use the LINDO software.

Suppose you wish to solve the product-mix problem. Launch the LINDO package. We will use XR and XE to denote the decision variables. In the current window, enter:

MAX  5 XR + 7 XE
ST
  3 XR + 4 XE < 650
  2 XR + 3 XE < 500
END

Note that

In LINDO, the minute you use a variable in your model, it exists. You don't have to do anything other than enter it in a formula.
LINDO interprets the "<" symbol as less-than-or-equal-to rather than strictly-less-than.
The objective function should not contain any constant. For example, MAX 3 X1 + 4 is not allowed.
All variables must appear on the left-hand side of the constraints, while numerical values must appear on the right-hand side of the constraints.
All variables are assumed to be nonnegative. Therefore, do not enter the nonnegativity constraints.

Now, click "Solve" on the menu bar and then select "Solve". Click on "No" in the "Do Range (Sensitivity) Analysis?" dialog box. The solution will be displayed in a separate "Reports Window". The output is:

 LP OPTIMUM FOUND AT STEP      2

        OBJECTIVE FUNCTION VALUE

        1)      1137.500

  VARIABLE        VALUE          REDUCED COST
        XR         0.000000          0.250000
        XE       162.500000          0.000000


       ROW   SLACK OR SURPLUS     DUAL PRICES
        2)         0.000000          1.750000
        3)        12.500000          0.000000

 NO. ITERATIONS=       2

Thus, the optimal solution for the problem is: x_r = 0 and x_e = 162.5, with a corresponding optimal objective-function value of 1137.5. Interpretation of the remaining information in the output will be discussed in a later section.

For more-detailed instructions on using LINDO, click "Help". Appendix 4.1, p. 169, in the text also provides a discussion.

As another example, the investment problem can be entered as:

MAX  2 X4 + S5
ST
  X1 + S1 = 100
  S1- 0.5 X1 - X2 - S2 = 0
  2 X1 + S2 - 0.5 X2 - X3 - S3 = 0
  2 X2 + S3 - 0.5 X3 - X4 - S4 = 0
  2 X3 + S4 - 0.5 X4 - S5 = 0
END

This yields the output:

 LP OPTIMUM FOUND AT STEP      6

        OBJECTIVE FUNCTION VALUE

        1)      208.1301

  VARIABLE        VALUE          REDUCED COST
        X4       104.065041          0.000000
        S5         0.000000          0.138211
        X1        27.642277          0.000000
        S1        72.357727          0.000000
        X2        58.536587          0.000000
        S2         0.000000          0.520325
        X3        26.016260          0.000000
        S3         0.000000          0.130081
        S4         0.000000          0.292683


       ROW   SLACK OR SURPLUS     DUAL PRICES
        2)         0.000000          2.081301
        3)         0.000000         -2.081301
        4)         0.000000         -1.560976
        5)         0.000000         -1.430894
        6)         0.000000         -1.138211

 NO. ITERATIONS=       6

It is interesting to note that the optimal objective-function value 208.1301 is approximately 17% higher than 177.7778, which is the corresponding value for the naive strategy of investing 66.6667 dollars on Monday. Moreover, an inspection of the listed values for the decision variables shows that the optimal strategy prescribes an initial investment of $27.6423 on Monday; and that this initial investment paves the way for three "perfectly-coupled" investment cycles that begin on Tuesday, Wednesday, and Thursday, respectively. A little bit of reflection should convince you that this strategy is, in fact, quite intuitive.

The product-mix problem and the investment problem can also be solved using Excel with the Premium Solver add-in. (The Premium Solver can be installed from the course CD.) Section 3.6 (pp. 67-72) in the text explains how to use the Solver. For a quick start, click on the following titles to view/download the Excel setups for these two problems: The Product-Mix Problem, The Investment Problem.

Assignment No. 1

Chapter 3: 3.4-13, 3.4-15, 3.4-16, 3.4-18, and 3.6-4.

Provide a brief explanation for each of your formulations.

For part (c) of 3.4-13, use Excel's Solver add-in. For part (b) of 3.4-15, 3.4-16, and 3.4-18, use LINDO.