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.
Date11.10.2016
Size70.56 Kb.
#6




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
0

1

5

6




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.
Solve Problem 9.11 as a final value problem.
Solve the following problem by dynamic programming:
3


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


General nonlinear

problem


Cutting plane method

Branch-and-bound method




Cutting plane method

Branch-and-bound method

Balas method


All-integer

problem


Mixed-integer

problem


Generalized penalty function

method


Sequential linear integer

(discrete) programming

method


solve all integer and mixed-integer nonlinear programming problems. The various solu-

tion techniques of solving integer programming problems are summarized in Table 10.1.

All these techniques are discussed briefly in this chapter.


10.2


Integer Linear Programming
GRAPHICAL REPRESENTATION

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


(10.1)


The graphical solution of this problem, by ignoring the integer requirements, is shown in
Fig. 10.1. It can be seen that the solution is x 1 = 5 21, x 2 = 4 1

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


2 with a value of f = 34 21.






590


Integer Programming


Figure 10.1


Graphical solution of the problem stated in Eqs. (10.1).


by changing the constraint 3x 1 + 11x 2 _ 66 to 7x 1 + 11x 2 _ 88 in Eqs. (10.1). With

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.



Download 70.56 Kb.

Share with your friends:




The database is protected by copyright ©ru.originaldll.com 2024
send message

    Main page