Unit-7&8Lecture 52
Dynamic Programming (DP) Method:
Dynamic Programming is a widely used technique in power system studies. It is, in fact, a mathematical technique used for multistage decision problems; originally developed in 1950s. A multistage decision problem is a problem in which optimal decisions have to be made over some stages. The stages may be different times, different spaces, different levels, etc. The important point is that the output of each stage is the input to the next serial stage. The overall objective function is to be optimized over all stages. It is normally a function of the decision variables (xi) of all stages. The important fact is that one cannot start from optimizing the first stage; moving forward toward the final stage; as there may be some correlations between the stages, too. To make the problem clear, let us express a power system example. Suppose we are going to minimize the generation cost of a power system over a 24-h period. Some information is as follows
• There are four generation units available; each of which may be either off or on (so that various combinations are possible, such as, 1111, 1101, 1001, 0011,…).
• The unit efficiencies are different; so that if the system load is low and say, two units can meet the load, we should use the higher efficient units to supply the load.
• The load varies throughout the 24-h period; changing at each hour (stage). The multistage decision problem is, in fact, deciding on the units to be on at each stage so that the overall generation cost over the 24-h period is minimized. We note that if no other constraint was imposed, we should optimize our problem at each stage and sum it over all stages. In other words, 24 single stage optimization problems2 have to be solved to find the final solution. Suppose that the final solution looks like Fig. 2.5 in which the unit combinations are shown at each stage. As shown, unit 1 is on at hours 1 and 2, off at hour 3, and on again at hour 4. Now what happens if a constraint is imposed expressing the fact that if unit 1 is turned off, it cannot be turned on unless a 5-h period is elapsed.
Integer Programming Method:
In the algorithms discussed so far, each of the decision variables may take any real value. What happens if a decision variable is limited to take only an integer value? For instance, if the decision variable is the number of generation units, taking a real value is meaningless. The optimization algorithms developed for this class of problems are classified as IP methods. If all decision variables are of integer type, the problem is addressed as IP problem. If some decision variables are of integer type while some others are of non-integer type, the problem is known as mixed integer programming problem. Moreover, based on the nature of the original problem, both integer linear programming and integer nonlinear programming methods have been developed. As a result, in power system literature, some terms such as MILP have appeared. 2.3.2 Heuristic Algorithms Most mathematical based algorithms can guarantee reaching an optimal solution; while do not necessarily guarantee reaching a global optimum. Global optimality may be only reached, checked or guaranteed for simple cases. On the other hand, many practical optimization problems do not fall in strict forms and assumptions of mathematical based algorithms. Moreover, if the problem is highly complex, we may not readily be able to solve them, at all, through mathematical algorithms. Besides, finding global optimum is of interest, as finding a local one would be a major drawback. Heuristic algorithms are devised to tackle the above mentioned points. They, normally, can solve the combinatorial problems, sometimes very complex, yet in a reasonable time. However, they seek good solutions, without being able to guarantee the optimality, or even how close the solutions are to the optimal point.
Dept. of EEE, NIT-RaichurPage 1