587 Return function, r i(X) r i(0) r i(1) r i(2) r i(3) 1 0 2 4 6 Thermal Station, I 2 0 1 5 6 3 0 3 5 6 10
Download 70.56 Kb.
|
- Navigate this page:
- Integer Programming INTRODUCTION
- 10.2 Integer Linear Programming GRAPHICAL REPRESENTATION
- Figure 10.2
Problems 587 Return function, R i(x) R i(0) R i(1) R i(2) R i(3) 1 0 2 4 6 Thermal Station, i 2
1 5
3 0 3 5 6 9.10 Find the investment policy for maximizing the total electric power generated. Solve the following LP problem by dynamic programming: Maximize f (x 1, x 2) = 10x 1 + 8x2 subject to 2x 1 + x 2 _ 25 3x 1 + 2x 2 _ 45 x 2 _ 10 x 1 _ 0, Verify your solution by solving it graphically. x 2 _ 0 9.11 9.12 9.13 A fertilizer company needs to supply 50 tons of fertilizer at the end of the first month, 70 tons at the end of second month, and 90 tons at the end of third month. The cost of producing x tons of fertilizer in any month is given by $(4500x + 20x 2). It can produce more fertilizer in any month and supply it in the next month. However, there is an inventory carrying cost of $400 per ton per month. Find the optimal level of production in each of the three periods and the total cost involved by solving it as an initial value problem.
Maximize d i _ 0 • i=1 di2 subject to di = x +1i Š x i, xi = 0 1, 2 . . . , 5,,, x3 = 5, x4 = 0 i = 1, 2 3, i = 1 2,
10 Integer Programming INTRODUCTION In all the optimization techniques considered so far, the design variables are assumed to be continuous, which can take any real value. In many situations it is entirely appropriate and possible to have fractional solutions. For example, it is possible to use a plate of thickness 2.60 mm in the construction of a boiler shell, 3.34 hours of labor time in a project, and 1.78 lb of nitrate to produce a fertilizer. Also, in many engineering systems, certain design variables can only have discrete values. For example, pipes carrying water in a heat exchanger may be available only in diameter increments of 81 in. However, there are practical problems in which the fractional values of the design variables are neither practical nor physically meaningful. For example, it is not possible to use 1.6 boilers in a thermal power station, 1.9 workers in a project, and 2.76 lathes in a machine shop. If an integer solution is desired, it is possible to use any of the techniques described in previous chapters and round off the optimum values of the design variables to the nearest integer values. However, in many cases, it is very difficult to round off the solution without violating any of the constraints. Frequently, the rounding of certain variables requires substantial changes in the values of some other variables to satisfy all the constraints. Further, the round-off solution may give a value of the objective function that is very far from the original optimum value. All these difficulties can be avoided if the optimization problem is posed and solved as an integer programming problem. When all the variables are constrained to take only integer values in an opti- mization problem, it is called an all-integer programming problem. When the vari- ables are restricted to take only discrete values, the problem is called a discrete programming problem. When some variables only are restricted to take integer (dis- crete) values, the optimization problem is called a mixed-integer (discrete) program- ming problem. When all the design variables of an optimization problem are allowed to take on values of either zero or 1, the problem is called a zero-one program- ming problem. Among the several techniques available for solving the all-integer and mixed-integer linear programming problems, the cutting plane algorithm of Gomory [10.7] and the branch-and-bound algorithm of Land and Doig [10.8] have been quite popular. Although the zero-one linear programming problems can be solved by the general cutting plane or the branch-and-bound algorithms, Balas [10.9] developed an efficient enumerative algorithm for solving those problems. Very little work has been done in the field of integer nonlinear programming. The generalized penalty function method and the sequential linear integer (discrete) programming method can be used to Engineering Optimization: Theory and Practice, Fourth Edition Singiresu S. Rao Copyright © 2009 by John Wiley & Sons, Inc. 10.1 588
10.2 Graphical Representation 589 Table 10.1 Integer Programming Methods Linear programming problems Nonlinear programming problems All-integer problem
Mixed-integer problem
Zero-one problem
Polynomial programming problem
problem
Cutting plane method Branch-and-bound method Cutting plane method Branch-and-bound method Balas method
problem
Mixed-integer problem
Generalized penalty function method
Sequential linear integer (discrete) programming method
tion techniques of solving integer programming problems are summarized in Table 10.1. All these techniques are discussed briefly in this chapter.
Consider the following integer programming problem: Maximize f (X) = 3x 1 + 4x2 subject to 3x 1 Š x 2 _ 12 3x 1 + 11x 2 _ 66 x 1 _ 0 x 2 _ 0 x 1 and x 2 are integers
Since this is a noninteger solution, we truncate the fractional parts and obtain the new solution as x 1 = 5, x 2 = 4, and f = 31. By comparing this solution with all other integer feasible solutions (shown by dots in Fig. 10.1), we find that this solution is optimum for the integer LP problem stated in Eqs. (10.1). It is to be noted that truncation of the fractional part of a LP problem will not always give the solution of the corresponding integer LP problem. This can be illustrated
this altered constraint, the feasible region and the solution of the LP problem, without considering the integer requirement, are shown in Fig. 10.2. The optimum solution of this problem is identical with that of the preceding problem: namely, x 1 = 5 21, Figure 10.2 Graphical solution with modified constraint. Directory: wp-content -> uploads -> sites sites -> Medical Radiography Program sites -> Background on the Haitian Earthquake sites -> Desk review yemen sites -> Safe Transitions for the Elderly Patient (step) sites -> District profile Haripur Introduction sites -> Germanie VanTrease and Tyler Tetzloff sites -> For more information sites -> To be completed by the cerf secretariat. Type of submission sites -> Sponsor Content Above the Clutter with Pete Krainik sites -> Bjarne Wollan Teigen Reformation Lectures Bethany Lutheran College and Seminary, Mankato, mn Download 70.56 Kb. Share with your friends:
|