An excursion company is considering adding small boats to their fleet. The company has $200,000 to invest in this venture. At present there is an estimated maximum demand of 6,000 customers per season for these tours. The company does not wish to provide capacity in excess of the estimated maximum demand. The basic data are given below for the two types of available boats. The company will make an estimated seasonal profit of $4,000 for each boat of Type 1 and $7,000 for each boat of Type 2. How many boats of each type should the company use to maximize profit? Type 1Type 2capacity, {(customers) /  (season)}1,2002,000initial cost, {$ / (boat)}25,00080,00 ∙ Feasible continuations of decision variable values ( ) The value of the objective function in thousands of $
<image 1>
['4 boats of Type 1 and 1 boat of Type 2', '5 boats of Type 1 and 0 boats of Type 2', '3 boats of Type 1 and 2 boats of Type 2', '6 boats of Type 1 and 0 boats of Type 2']
The linear programming problem (illustrated in Figure 1) is: Maximize 4,000 x1 + 7,000 x2 Subject to 1,200 x1 + 2,000 x2 $\le $ 6,000 25,000 x1 + 80,000 x2 $\le $ 200,000 x1, x2 $\ge $ 0; x1 x2 are integers. Constraints in the original problem formulation should be transformed so that all coefficients are integers. This is done to facilitate solution of the integer programming problem. No transformation is required in this problem. If there were a constraint such as (3/4)x1 + (6/4)x2 $\le $ (48 / 10), both sides must be multiplied by 20 so that it becomes 15x1 + 30x2 $\le $ 96. To simplify notation, divide the first constraint by 100 and the objective function and second constraint by 1000 and construct the initial tableau (Tableau 1). Tableau 1ciBASISV1V2V3V4bi0x3122010600x4258001200 The final tableau in the Simplex solution is: Tableau 2ciBASISV1V2V3V4bifi04x1100.1739   0.04351.7390.7397x201   0.05430.02611.9560.956Solution (x0)00   0.3155   0.008720.65 Since the solution is non integer, add cutting planes to reduce the feasible region until an integer solution is obtained. The following steps will be used to develop new cutting planes (or constraints). 1. Add a new column to the final Simplex tableau. This is the fi0 column in Tableau 2. For each bi value associated with a basic variable determine an fi0 value, where fi0 is a nonnegative fraction greater than or equal to zero but less than one, which when subtracted from a given noninteger will convert to an integer (e.g. 0.739 subtracted from 1.739 will convert it to an integer; 0.25 subtracted from    6.75 will convert it to an integer). 2. The largest fio value will determine the row of the tableau to be used in constructing a cutting plane. In the above tableau f20 = 0.956 designates the second row to be used for this purpose since 0.956 > 0.739 (i.e. f20 > f10).When ties occur, an arbitrary choice among tied rows is made. For each aaj coefficient in this row determine an fij value, just as fi0 was determined for bi. x1x2x3x4biRow 201   0.05430.02611.956f2j values000.94570.02610.956Integer value01   101 The f2j values give a new constraint 0x1 + 0x2 + 0.9457x3 + 0.0261x4 $\ge $ 0.956. Adding a surplus variable x5 gives: 0x1 + 0x2 + 0.9457x 3 + 0.0261x4    x5 = 0.956. Tableau 3 ciBASISV1V2V3V4V5bi 4x1100.1739   0.043501.739 7x201   0.05430.026101.956 0x3000.94570.0261   10.956→ 3. The new constraint is added to the final Simplex tableau. The incoming variable is the one that will cause the smallest decrease in the objective function as indicated by the x0j values of the final Simplex tableau. An alternative rule (sometimes more efficient) is to select the incoming variable as that having the maximum quotient of x0j/aij for non basic variable j, where aij < 0. The incoming variable will be x4 with a  x04 of    0.0087. The outgoing variable, x5, is always that associated with the constraint just annexed (in this case, row 3). Apply the Simplex procedure to get the following tableau: Tableau 4ciBASISV1V2V3V4V5bifi04x1101.7500   1.6673.333.3327x201   1011.0000.0000x40036.2341   38.3142   0.333     x00000   0.008720.65 In the new solution X = (3.333, 1.000). Since x1 has the maximum fi0, it is used to determine the next cutting plane. Upon adding another column V6, and another constraint, the next tableau becomes: Tableau 5 ciBASISV1V2V3V4V5V6bi 4x1101.7500   1.66703.333 7x201   1.0101.000 0x40036.2341   38.3142036.628 0x600.75000.333   10.333→ ↑ Apply the Simplex procedure to obtain: Tableau 6ciBASISV1V2V3V4V5V6bi4x1105.500557x201   325.00300x400122.4410   114.9474.940x5002.2501   31.00x0j 00   219700   4120 Tableau 6 gives the optimum integer solution. X* = (5, 0).