The Harrison Electric Company, located in Chicago’s Old Town area, produces two products popular with home renovators: old-fashioned chandeliers and ceiling fans. Both the chandeliers and the fans require a two-step production process involving wiring and assembly. It takes about 2 hours to wire each chandelier and 3 hours to wire each ceiling fan. Final assembly of the chandeliers and fans requires 6 and 5 hours, respectively. The production capability is such that only 12 hours of wiring time and 30 hours of assembly time are available. If each chandelier produced nets the firm $7 and each fan nets $6, Harrison’s production mix decision can be formulated using LP as follows:

where

With only two variables and two constraints, Harrison’s production planner, Wes Wallace, employed the graphical LP approach (see Figure 10.1) to generate the optimal solution of $X_1=3.75$ chandeliers and $X_2=1.5$ ceiling fans during the production cycle. Recognizing that the company could not produce and sell a fraction of a product, Wes decided that he was dealing with an integer programming problem.

It seemed to Wes that the simplest approach was to round off the optimal fractional solutions for $X_1$ and $X_2$ to integer values of $X_1=4$ chandeliers and $X_2=2$ ceiling fans. Unfortunately, rounding can produce two problems. First, the new integer solution may not be in the feasible region and thus is not a practical answer. This is the case if we round to $X_1=4, X_2=2$. Second, even if we round off to a feasible solution, such as $X_1=4, X_2=1$, it may not be the optimal feasible integer solution.

Listing all feasible solutions and selecting the one with the best objective function value is called the enumeration method. Obviously, this can be quite tedious for even small problems, and it is virtually impossible for large problems, as the number of feasible integer solutions is extremely large.

Table 10.1 lists the entire set of integer-valued solutions to the Harrison Electric problem. By inspecting the right-hand column, we see that the optimal integer solution is

Table 10.1 Integer solutions to the Harrison Electric Company Problem

Note that this integer restriction results in a lower profit level than the original optimal LP solution. As a matter of fact, an integer programming solution can never produce a greater profit than the LP solution to the same problem; usually, it means a lesser value.

QM for Windows and Excel spreadsheets are capable of handling integer programming problems such as the Harrison Electric case. Program 10.1A illustrates the data input to QM for Windows, and Program 10.1B provides the results.

To use QM for Windows, select the Integer & Mixed Integer Programming Results module. Specify the number of constraints and the number of variables. Program 10.1A provides the input screen, with data entered for the Harrison Electric example. The last row of the table allows you to classify each variable according to the type of variable (Integer, Real, or 0/1). Once all variables have been correctly specified, click Solve, and you will see the output as shown in Program 10.1B.

Solver in Excel 2016 can also be used to solve this problem, as shown in Program 10.2. The Solver parameters and selections are shown, and the key formulas are displayed. To specify that the variables must be integers, a special constraint is entered in Solver. After opening the Solver Parameters window, select Add, just as you would do to enter other constraints. When the Change Constraint window opens, enter the range containing the solution values, as shown in Program 10.2. Then click the tab to open the drop-down menu and then change the type of constraint to int, for integer. Click OK to return to the Solver Parameters window. Then enter the other constraints, specify the parameters and selections, and click Solve. The solution is shown to be 5 chandeliers and 0 fans, for a profit of $35.

Although the Harrison Electric example was a pure integer problem, there are many situations in which some of the variables are restricted to integers and others are not. The following is an example of such a mixed-integer programming problem.

Bagwell Chemical Company, in Jackson, Mississippi, produces two industrial chemicals. The first product, xyline, must be produced in 50-pound bags; the second, hexall, is sold by the pound in dry bulk and hence can be produced in any quantity. Both xyline and hexall are composed of three ingredients—A, B, and C—as follows:

Bagwell sells 50-pound bags of xyline for $85 and hexall in any weight for $1.50 per pound.

If we let $\text{X}=\text{number}$ of 50-pound bags of xyline produced and $Y=\text{number}$ of pounds of hexall (in dry bulk) mixed, Bagwell’s problem can be described with mixed-integer programming:

Note that Y represents the bulk weight of hexall and is not required to be integer valued.

Using QM For Windows And Excel to Solve Bagwell’s Integer Programming Model

The solution to Bagwell’s problem is to produce 44 bags of xyline and 20 pounds of hexall, yielding a profit of $3,770. (The optimal linear solution, by the way, is to produce 44.444 bags of xyline and 0 pounds of hexall, yielding a profit of $3,777.78.) This is first illustrated in Program 10.3, which uses the Integer & Mixed Integer Programming Results module in QM for Windows. Note that variable X is identified as Integer, while Y is Real in Program 10.3.

Figure 10.3 Full Alternative Text

In Program 10.4, we use Excel to provide an alternative solution method.

Figure 10.4 Full Alternative Text

Solver Parameter Inputs and Selections	Key Formulas
Set Objective: D5	Copy D5 to D8:D10
By Changing cells: B4:C4
To: Max
Subject to the Constraints:
D8:D10 <= F8:F10
B4 = integer
Solving Method: Simplex LP
☑ Make Variables Non-Negative