Linear Optimization in Applications

5. Integer Programming Formulation

In many linear optimization problems, we require that the decision variables be integers. Strictly speaking, Example 1.1 in Chapter 1 is an integer programming problem, because the optimal number of pipes must be whole numbers. Example 1.1 , fortunately, has an optimal solution with decision variables in integers, and so we did not worry about the process of converting non integers to whole numbers. However, we do not face every problem as lucky as Example 1.1. In this chapter, we shall look into linear optimization problems which require optimal solutions to have integer values, and, furthermore, the problems which require the decision variables to have either the values of 0 or 1 (called zero-one variables). This chapter will only concentrate on the formulation of such models. The next chapter will discuss the method of solution for such problems. Now, let us see a number of examples on integer programming formulation. 5.1 An Integer Programming Example Example5.1 A company is planning to invest a maximum amount of $1,000,000 in purchasing vehicles to deliver goods to customers from a central store. Details of the three types of vehicles available for purchase are given below: Vehicle Type Capgaf city Price Average speed Annual rep也r cost $ (km/hr) ($/ye訂) 6 100,000 30 5.000 2 5 80,000 35 6,000 3 4 60,000 40 7,000 The total repair costs should not exceed $65,000 in a ye訂. No more than 12 vehicles are required. Determine the number of vehicles of each type to be purchased so that the rate of delivery can be optimized. 76 Linear Optimization in Applications $olution 5. 1 Let X1 = number of type 1 vehic1es X2 = number of type 2 vehic1es X3 = number of type 3 vehic1es Since the number of vehicles must be a whole number, therefore, X I，也 and X3 must be integers. Rate of delive可 is proportional to capacity, and rate of delivery is a1so proportional to average speed, ie. rate of delivery cx: capacity rate of delivery cx: average speed 人 rate of delivery cx: capacity x average speed In order to optimize the rate of delivery, our objective function is : Maximize Z = (6 X30)Xl + (5 x 35)X2 + (4 X40)X3 = 180Xl + 175x2 + 160x3 subject to: The capita1 constraint: 100,000Xl + 80,000X2 + 60，000X3 三 1 ，000，000 …(1) The repair cost constraint: 5,OOOXl + 6,000X2 + 7，000X3 三 65 ，000 The total number of vehic1es constraint: X} + X2 + X3 三 12 Therefore, the model can be summarized as follows: Max Z = 180x} + 175x2 + 160月 subject to (2) 一一一一…一一一 (3) 100,000x} + 80,OOOX2 + 60，000月三 1 ，000，000 一一…一一一一一一 (1) 5,000x} + 6,OOOX2 + 7，OOOX3 三 65 ，000 X} + X2 + X3 ~ 12 m…一…一一一一一一一 (2) …………………一 (3) 的teger Programming Formulation Xl , X2, X3 ~ 0 and are integers The solution for this model is: Rate of delivery = I.(capacity x speed) = 1955 Xl = 6 X2 = 5 X3 = 0 77 Note that if Xl and X2 were not constrained to be integers, the solution would be: Rate of delivery = I.(capacity x speed) = 2032.5 Xl = 4 X2 = 7.5 X3 = 0 5.2 Use of Zero-One Variables In the beginning of this chapter, we have come across the term "zero-one variables". Some decision variables of some linear programming problems can only take the value of either 1 or O. It is extremely powerful in the formulation of linear optimization models to use zero-one variable so that one can make a decision as yes or no by referring to whether the variable takes the value 1 or O. Readers will see how powerful and useful these zero-one integer decision variables are in the following examples. Example5.2 A product can be manufactured by five different plantlequipment. The set叫p costs (fixed costs), production costs (variables costs) per unit product processed, and the capacity of each plantlequipment per period are given as follows: 78 Linear Optimization 的 Applications Fixed set-up Variable Production Capacity per Plantlequipment cost ($) cost ($/unit) period (units) 5500 90 700 2 5000 85 650 3 4500 91 600 4 4200 93 550 5 3800 95 500 1500 units of the product is demanded for a given period. Determine the optimal combination of plantlequipment to be used. Solution 5.2 Let x1 = number of units produced by plant 1 X2 = number of units produced by plant 2 X3 = number of units produced...