Practice English Speaking&Listening with: Lec-19 Dynamic Programming - Continuous Variables

Normal
(0)
Difficulty: 0

In

this lecture we continue our discussion on dynamic programming. We continue to solve

examples where the decision variables take continuous values. In the previous example

we had a linear objective functions with nonlinear constrains and variables were continuous.

In this example we will have a nonlinear or a polynomial objective functions subject to

a linear inequality as a constraint.

The objective function is to minimize Z = X1 cube - 5X1 square + 8 X1 + X2 cube - 2X2 square

- 10X2 + 10 subject to X1 + X2 less than or equal to 4; X1 and X2 continuous and greater

than or equal to 0. As usual we define the stage, state, decision variable and criteria

of effectiveness. We have 2 variables here so we solve in 2 stages and each variable

represents a stage the state is the resource available for allocation the constrained X1

+ X2 less than or equal to 4 does not tell us what the resource is therefore we generally

define it as resource available for allocation. Decision variables of course, are the values

of the variables X1 and X2 and the criteria of effectiveness minimize the objective function

Z given by X1 cube - 5X1 square + 8X1 + X2 cube - 2X2 square - 10 X2 + 10.

We have 2 variables in this problem or in our approach. We are going to first solve

for variable X1 and then for variable X2 we may call it a kind of a forward recursion.

Alternately we can also re write the objective function such that the objective function

is X2 cube - 2X2 square - 10X2 + 10 + X1 cube - 5X1 square + 8X1. We will later see why

we decided to rewrite the objective function. Since we have rewritten the objective function

this way, it makes it easier for us to solve for variable X1, first and then for variable

X2. Then constant now is added along with the X2 terms and not along with the X1 terms

so as usual n = 1; 1 more stage to go F1 or S1, X1 is = X1 cube - 5X1 square + 8X1. F1

star of X1 is the best value of X1 that optimizes the function F1 X1 minimized, X1 cube - 5X1

square + 8X1 subject to the condition. 0 less than or equal to X1 less than or equal to

X1.,Differentiating with reference to X1 and setting it to 0, we get 3X1 square - 10 X1

+ 8 = 0 which would give us X1 = 2 or X1 = 4/3. Now we have 2 values of X1 which is X1 = 2

and X1 = 4/3. We also observe that when we solved for 3X1 square - 10X1 + 8 = 0, we can

easily solve for X1 by factorizing it. - 10 X1 can be written as - 6X1 - 4X1 from which

we would get X1 = 2 or X1 = 4/3.

Now in order to find out which one is the minimum, we now have to find out the second

derivative. Second derivative would be 6X1 - 10, now we substitute the 2 values that

we have got. That is X1 = 4/3 and X1 = 2. when we substitute X1 = 4/3 in 6 X1 - 10,

we get - 2 which indicates that 4/3 is a local maximum when X1 = 2. The value is + 2 indicating

2 is a minimum. Now if we go back to the function X1 cube - 5X1 square + 8X1 it is cubic in

X1. So we also have to find out in the range 0X1, 2, 4 the value of the function at the

end. Unlike a quadratic in a cubic we need to find out the value at the end. So when

we find the values at the extreme. At X1 = 0, the value of the function is 0 added X1 = 4.

It is 16. Now if we compare the value that X1 = 0 and X1 = 2 we observe that the minimum

actually happens at X1 star = 0. So the minimum happens at X1 star equals to 0 and F1 star

of X1 is = 0.

We also explain this using this figure. This is a kind of free hand diagram of the polynomial

that we have and we observe that the 2 values that we obtained our X1 = 2 here and X1 = 4/3.

X1 = 4/3 represents a local maximum. X1 = 2 represents local minimum. X1 = 0 is here and

X1 = 4 is farther. We also realize that for values less than 4/3, it is decreasing and

it is at 0 and X1 = 0. For values greater than 2, it will be increasing. So the minimum

happens to be at X1 = 0 with F1 star of X1 = 0.

Continuing with N = 2 and 2 more stages to go F2 or X2, S2 is = X2 cube - 2X2 square

- 10 X2 + 10 + F1 star of S2 - X2. Now F1 star of S2 - X2 comes because we assume that

there is an S2 resource available, out of which an X2 value of X2 is allocated to variable

X2 and the balance S2 - X2 has S1 for allocation to variable for X1. Now F2 star of S2 are

values of X2, minimizes X2 cube - 2X2 square - 10X2 + 10 + 0. The 0 comes because of F1

star of S2 - X2. We have all ready seen here that F1 star of S1 is 0 therefore F1 star

of S2 - X2 is also 0. Now in the range 0 less than or = X2 is less than or = 4. The 4 comes

from the inequality here.

4 is the amount of resource available at the beginning. So S2 takes value = 4. So X2 is

between 0 and 4 again. We have to differentiate with respect to variable X2 and we equate

it to 0. We get 3X2 square - 4X2 - 10 = 0 that comes from the first 3 terms. The terms

X2 cube - 2X2 square - 10X2 on differentiation will give 3X2 square - 4X2 - 10 = 0. Now this

is a quadratic equation we have to solve for X2, so we do not factorize it. So we use the

formula - B + or - root of B square - 4 ac/2a to get X2 is = 4 from + or - root of 136/6.

So we get 2 values. One is 4 + root 136/6 and the other is 4 - root 136/6. Now we do

not consider the negative value because X2 should be greater than or equal to 0. So we

consider only the positive value or the positive root and we have X2 is = 2.6103. Now we have

to find out whether this is a minimum and to do that, we further differentiate or we

find out the second derivative. Second derivative, on differentiating this would give us 6X2

- 4. 6X2 - 4 at 2.6103, there is a positive value of 11.66 and X2 is = 2.03. Therefore

the optimum S2 star is = 2.61 and F2 star of 4 or the objective function value is - 11.9446.

This we obtain by substituting 2.6103 in this expression X2 cube - 2X2 square - 10X2 + 10.

When we substitute X2 = 2.6103, we get the value of the function as - 11.9446. X1 star

is already 0, therefore the best values are X1 star is 0, X2 star is 2.6103 and F2 star

of 4 or the minimum value is - 11.9446. Now there are a couple of things we did in this

example. In this example we decided to choose that variable X1 first and then we chose variable

X2. If we look at the function carefully, normally in a backward recursive mode we would

have solved for variable X2 first and then at N = 2 we would have solved for X1 but then

here we did something. We rewrote the objective function or rearranged the terms. The X2 terms

were grouped together first and then the X1 terms were written so that we could optimize

X1 first. The reason was very simple. When we had the first derivative here we could

factorize it to get 2 or 4/3. If we had used X2 first we would be forced to use the quadratic

or the roots of the quadratic equation and we would have ended up getting decimals. So

wherever we observe that it is possible to attract a round values and good values we

can use that variable as a first variable to optimize, which is what we did here.

One should also understand that if we had worked out this problem in the normal way

by choosing variable X2 in the first stage or N = 1 and then choosing variable X1 at

N = 2, we would have got the same answer. The optimal solution in this problem is X1

star is = 0. X2 star is = 2.61 and the value - 11.9446. The other difference between the

earlier problem and this problem is we need to look at that in this problem. Our constraint

is an inequality. X1 + X2 is less than or equal to 0 whereas in the earlier problem,

the constraint was an equation. So whenever the constraint is in equation at N = 1, one

more stage to go. We did not optimize. We did not optimize or we did not differentiate

in the earlier problem. We substituted the value S1. Because of the equation all the

resource S1 will have to be utilized.

When we have an inequality, it is not necessary for us to use the entire research S1 that

is available. Here we have a research S1 that is available. It is not absolutely necessary

for us to use all the resource S1 available. We have an inequality. We differentiate or

we optimize at the first stage and then we got 2 values that happened in this example,

where X1 = 0 was the actual optimum.

Another important thing from this problem is because this function is cubic, as explained

in this figure it is not enough for us to restrict ourselves to minimum and maximum

found by the differentiation. It can happen as in this example the extreme or the end

is equal to 0 is actually the minimum, while the local minimum X1 equals to 2 gains the

higher value of the objective function. Now this is possible for higher order functions

whereas if it were a quadratic, it would have been enough because the quadratic would have

only one optimum moment. We have cubic and higher order functions, one need to look at

the value the functions take at the end or at the extremes. So these are the things that

we have learnt using this example. So in this example, we have tried to minimize the cubic

functions subject to inequality. The most important thing is when we have an inequality;

we do not substitute the value of the state variable. Instead we optimize at the first

stage or we optimize at N = 1, this is the most important thing that we learned from

this example. Let us continue our discussion with 1 more example.

This is shown here. The problem is to maximize 2X1 + 3X2 + X1 X2. Now, what is different

in this objective function compared to the previous function, last two examples are that,

we have a product form X1, X2 appearing in the objective function. Here in example 4,

when we first introduced continuous variables, we did have a product form in the constraint

but the difference here is, there is a separate X1 term. There is a separate X2 term, and

then there is X1 X2. Now with this kind of an objective function or with this type of

term, it may be difficult for us at the moment to identify the objective function and separate

it with respect to each stage. Now we will see how we will handle this kind of peculiarity.

As we go on with this example, we again have a constraint of the type X1 + X2 less than

or equal to 2 and X1, X2 greater than or equal to 0.

We once again define state, stage, decision variable and criteria of effectiveness. Again

we have 2 variables. So we solve it in 2 stages. So the 2 variables X1 and X2 give us the 2

stages. There are 2 stages and each stage corresponds to each variable. State once again

is defined in a very general way as resources available for allocation. We do not know what

this S2 represents. So we call it a resource and the amount or resource available for allocation

is state variable. The designation variables are the values of X1 and X2 which we are going

to find out the criteria of effectiveness or the objective function is to maximize Z.

Z is given by 2X1 + 3X2 + X1 X2. Once again in this example the product term X1, X2 is

present in the objective function making it difficult to separate the objective function

in terms of 2 separate functions of the variables.

Now to overcome this, what we do is we try to factorize the objective function in this

case. Now 2X1 + 3X2 + X1 X2, what we can do is we can add 6 and subtract a 6 from this.

So if we have 2X1 + 3X2 + X1 X2 + 6 - 6 and we take only these 3 terms and + 6 and we

realize that we can factorize it. After factorization we will get X1 + 3 into X2 + 2 - 6 or if we

expand this, X1 + 3 into X2 + 2 - 6. We would get X1 X2 2X1 + 3X2 + 6 - 6 which is S2X1

+ 3X2 + X1 X2 which is what our original objective function is. So we factorize this and we get

objective function which is in this form X1 + 3 into X2 + 2 - 6. We can always leave out

the consonant from any objective function. So we write the problem so as to maximize

X1 + 3 into X2 + 2 object of X1 + X2 less than or equal to 2X1 X2 greater than or equal

to 0. We have left out this - 6 therefore in the end, we have to add a + 6 to the objective

function. So at the moment we leave it out. Now this is a form with which we are quite

comfortable because we have 2 variables X1 X2. The constraint is of the form X1 + X2

less than R = 2. The objective function is clearly product of F2 terms S1 involving only

X1 and constraint and the other involving only X2 and constraint. So now we can nicely

do it the way we are comfortable with and we continue to solve this problem.

So when N = 1, one more stage to go, we try to optimize on the variable X2 first so we

have F1 or S1 is = X2 + 2. We take only this term. We take X2 + 2 terms. F1 star of S1

value of this function is to maximize X2 + 2, subject to the condition less than or equal

to X2 less than or equal to S1. We assume that a resource S1 available here for variable

X2 which means something is allocated to S1. The balance is available as S1, subject to

0 less than or equal to X2 less than or equal to S1. Now here again we optimize it and it

turns out that the optimum value is at X2 star has an upper limit of S1. So obviously,

the best value of S2 is going to be S1. Due to the presence of the inequality here, we

optimized it. We optimized this function subject to 0 less than or equal to S2 less than or

equal to S1. The maximum value is got at S2 star equal here and F1 star of S1 is = S1

+ 2. Now we go to the second stage N = 2, 2 more stages to go. F2 of 2, S1, 2 comes

from this so, 2X1 is X1 + 3 into F1 star of F2 - X1. 2 - X1 again comes because, out of

this available 2, there is an X1 greater than or equal to which is allocated to variable

X1, so 2 - X1 greater than or equal to 0 is now available as S1 or allocation for variable

X2.

Here again we are aware that S1 is greater than or equal to. Now this S1 is greater than

or equal to because if we go back here both X1 and X2 are = 0. So if we can give an allocation,

X1 greater than or equal to or less than or equal to 2, the balance S1 will have to be

greater than or = 2 is applicable here. Similarly 0 less than or equal to S1, less than or equal

to 2 is applicable here. This would mean F2 star of S1 is to maximize X1 + 3 into F1 star

of X2 - S1. We also know that F1 star of a given S1 is S1 + 2, so S1 star of S1 will

be 2 - S1 + 2 subject to 0 less than or equal to 2. So to maximize S1 + 3 into 4 - X1 subject

to 0, less than or equal to S1, less than or equal to 2, this on multiplication would

give us a - X1 square + X1 + 12. First derivative = 0.

We get X1 = 1/2. Now that comes because we have - 2X1 + 1 = 0 gives us S1 = 1/2 and the

second derivative will be - 2 indicating it is negative and also indicates the maximum.

So we are into maximizing, therefore X1 star = 1/2. Now if X1 star is = 1/2; S1 = 3/2 that

comes because X1 star is = 1/2. So we have used up 1/2 here. 3/2 is now available as

S1 for allocation of variable X2. We also know that S2 star is = S1, therefore 3/2,

which is available for allocation goes to variable X2, so X1 star is 1/2, X2 star is

3/2. The value of objective function at present is 49/4, i.e., the value of the function - X1

square + X1 + 12 at X1 = 1/2 is 49/4. But we also have to subtract a 6 because when

we factorize, the original objective function turned out to be X1 + 3 + X2 + 2 - (we left

out this) - (included only this). Therefore we have to include this - 6 here, so we subtract

a 6 from the Z to get 25/4 for the original problem.

Now the most important thing in this is when we have an objective function of this type,

where this is the first time we considered an objective function which has X1 terms,

X2 terms and a product, the presence of the product along with the X1 terms and the X2

terms makes it difficult. Therefore factorization came to our rescue. If the function is such

that we can factorize it, we can use it to our advantage and then convert the objective

function into this form where we can separate the X1 term and the X2 terms which in this

case turned out to be a product of S1 and a function of S2. If we had started with this,

then it would have become very difficult trying to optimize 2 variables in 1 stage or we end

up having to identify different types of state variables. So to avoid or overcome that difficulty

by factorizing and by bringing it into or at form, we can separately take out the X1

term as well as the X2 term and then we can separately optimize for each one of them.

So it is important when we have these kinds of objective functions. We should explore

possibilities.

We can convert them into the form S1 of X1, S2 of X2, so in this case it was the product

form. Also we need to understand that whenever we have an inequality coming in, we do not

substitute. We need to optimize. In this case we did optimize X2 + 2 subject to 0, less

than or equal to 0. We found out that, the value of X2 star was the available resource

but we did optimize to find out that the maximum value R is = S1. Couple of things that we

can learn from this example is that when we have an objective function, when we could

use factorization to convert into a form which is familiar and comfortable. We then have

an inequality. We need to optimize N = 1 stage. We continue our discussion in dynamic programming

through another example from which we would learn a few new things.

Now this problem is a typical manpower problem. So the problem is as follows. Man power requirements

for a company for the next 4 months are 90, 120, 80 and 100 respectively. They can employ

more than the requirement in any month, but if they do that, they incur a cost of under

utilization. Now this cost of underutilization is 10 times X, where X is the additional number

of employees over and above the minimum required and the minimum required in the first month

is 90. If they end up employing 95 people then because of the additional 5, they would

incur an under utilization cost of 10 into 5 which is 50. They cannot employ less than

the minimum required. So they can only employ 90 or more for the first month. They cannot

employ fewer than the requirement. Now there is also a cost of changeover given by Y square

where Y is the amount of decrease or increase over the employees. For example if they choose

to employ 95 employees for the first month instead of 90 and say 120, they employ in

the second month then there is a difference of 15 from 95 to 120. Remember 90 is the requirement

and if they employ 95 then from this 95 to 120, there is a change over cost and increase

cost which will be 15 square which is = 225 . If they choose to employ 100 here then there

is a decrease of 20 so, that would result again in a changeover cost so 20 square which

is = 400. So whether there is an increase or decrease, there is a change over cost given

by Y square where Y is the amount of decrease or the extent of decrease or increase of the

employees. Initially 100 employees are available so 100 employees are available here at the

beginning of the first month to find out the least cost solution to employees in the fair

month where we will now we look at.

We had defined decision variable and criterion of effectiveness now. There are 4 months,

so each month would act as a stage. We have 4 stages N = 1 to N = 4 which are represented

by the 4 months. State in this example, is the number of employees available in the month

or the number of employees who have been employed in the previous month. For example when we

look at the beginning of the first month now, 100 employees are available in the beginning

of the first month so that is the state variable. If we look at the beginning of the second

month then the number of people who were employed in the first month would now be available

at the beginning of the second month and therefore that would be the state variable. State variable

here is the number of employees available at the beginning of the month which is the

number of employees who were employed in the previous month. Decision variable is X1 to

X4 is the number of people to be employed in the current month or in the last month.

So we define X1 to X4 for 4 month, S1 to 4. Criterion of effectiveness or the objective

function as an example would be to minimize the sum of the change over cost and the underutilization

cost. There are 2 costs. There is a change over cost. There is an underutilization cost.

So we want to minimize the sum of these 2 costs as the minimum total cost. We use a

backward recursive approach.

So when N is = 1 more stage to go or 1 more month to go, we are effectively looking at

the 4th month, so because of the backward recursion we have 1 more month to go. We are

here. So we are looking at the fourth month, so we assume that we are at the end of the

3rd month. F1 or S1X4, S1 is a state variable which is the amount of people available at

the beginning of 4th month which is also the number of people employed in the 3rd month.

We will see that later. So the number of people available at the beginning of the 4th month

is X1. X4 is the decision variable which is a number of people who are going to be employed

in the 4th month. The requirement for the 4th month is 100, so number of people who

are going to be employed in the 4th month will have to be more than 100. So if it is

more than 100 then X4 - 100 is the excess number of employees who contributed to the

underutilization cost. So underutilization cost is 10 times X4 which 100. Now there is

a change over from X3 to X4 because X3 is the number of people in the month 3. X4 is

the number of people in the month 4. X3 - X4 is the change over so X3 is the same as S1.

A state variable is the same as the number of people employed in the 4th month. We have

S1 - X4, power the whole square. This is the change over cost.

This objective function is the sum of the underutilization cost and the change over

cost. So F1 star of S1 is the best value of X4 which is to minimize the sum of the underutilization

cost and the changes over cost to minimize 10 times X4 - 100 + S1 - X4 the whole square.

So subject to the condition, X4 is greater than or equal to 100. Company should employ

at least the minimum number or more and cannot employ less than 100 in this case. So once

again differentiating w.r.t 4 and equating to 0, we would get 10 - 2 times S1 - X4 will

be = 0, that comes with this expression. This would give us 10. This would give us - 2 times

S1 into X4 = 0 from which X4 star is = S1 - 5. Now we also have to find out the second

derivative and show that the second derivative is positive which would indicate a minimum,

which we would see from here. - 2 into - X4 would give us a + 2X4 which would give us

a minimum. So X4 star is = S1 - 5 in this case.

Now we also have 2 cases coming in here since X4 is greater than or equal to 100, we need

to have a couple of things. When S1 is greater than or equal to 105 then X4 star will become

S1 - 5. For example if S1 were 110, then the best value of X4 star would be 110 - 5. On

the other hand if S1 was 100, then S1 - 5 would give us 95 which is going to violate

X4, greater than or equal to 100. So in such a case, X4 star will take a value 100. X4

star will take values depending on what the value of S1 is, so if S1 is greater than or

equal to 105 then X4 star will be S1 - 5 and F1 star of S1 will be 10 times S1 - 105 +

25. This comes because when we substitute X4 = S1 - 5, becomes 10 into S1 - 5 - 100

which is 10 into S1 - 105. X4 is S1 - 5, S1 and S1 will cancel out each other and we will

get a 25. So when X4 star is = S1 - 5, F1 star of S1 is 10 times S1 - 105 + 25.

If S1 is less than 105, S1 - 5 will become less than 100 but then it will violate the

restrictions, so F4 star will take a value 100. So F4 star will take a value 100, if

S1 is less than 105. Substituting here, the under utilization cost becomes 0 and only

the change over cost will be there. F1 star of S1 will become S1 - 100 the whole square.

Now N= 2; 2 more stages to go, F2 of S2 X3 star. Now when we have 2 more stages to go,

we assume that we are at the beginning of month 3, and we have certain number of resources

available to us which is the number of people who worked in month 2. So, when we are here,

when have N =2; 2 more stages to go, and we have to make a decision for variable X3, assuming

that S2 people are available.

F2 of S2, X3= 10 times X3 - 80, 80 come as the minimum requirement for month 3 + S2 - X3,

the whole square represents the changeover. There is S2 that was available at the beginning,

X3 is employed + F1 star of X3, this comes in because the number that we employ this

month, X3 is now available at the beginning of the next month as X1 so the function is

10 into X3 - 80 + S2 - X3, whole square, + F1 star of X3. F2 star of S2 is to minimize

10 into 3 - 80 + S2 - X3, the whole square, + F1 star of X3, subject to the condition,

X3 greater than or equal to 80. Now you go back to the problem. We observe that the 4

requirements are 90, 120, 80 and 100. One look at these numbers is going to tell us

that for the second month it is not advisable for us to have more than 120 people at all

because if we have more than 120 people then we are going to unnecessarily have underutilization

cost and the change over cost is going to be more because the next month's requirement

is 80. One look at these numbers it would tell us that for the second one, we are going

to employ only 120 people. We use this information in this problem to simplify this problem further.

So we go back. In this problem, the maximum requirement is for the second month and having

an X2 star greater than 120 would only increase both the under utilization cost and the change

over costs further. We will have X2 star = 120 and S2 = 120. So we can comfortably substitute

S2 = 120 in this. Now we also have 2 functions for F1 star of X1. F1 star of S1 took 10 into

- 105 + 25 in a certain range and F1 star of S1, S1 - 100, the whole square in a different

range where S1 is less than 105. Now we have to substitute both these expressions here.

So we have 2 expressions for F2 star of S2. Now we understood that S2 is 120 because X2

star is 120. So we are going to substitute S2 = 120 and we are also going to substitute

the 2 expressions for F1 star of X3. F1 star of X3 is the same as F1 star of S1. So we

substitute both these expressions. So the first one will have one F2 star of S2, minimize

10 times X3 - 80 + 120 - X3 the whole square + 10 into X3 - 105 + 25. We have used the

first expression here, 10 into S1 - 105 + 25 but that is within the range greater than

or equal to S1, greater than or equal to 105. This implies X3 greater than or equal to 105.

X3 has to be less than or equal to 120 because that is the maximum. Therefore in the range

X3 between 105 and 120, we have this function which minimizes 10 times X3 - 80 + 120 - X3

the whole square + 10 times X3 - 105 + 25. On the other hand in the range X3 less than

105, let us go back. S1 is less than 105, F1 star of S1 is S1 - 100 the whole square.

S1 is the same as X3 in the range, X3 less than 105 or in the range of X3 between 80

and 105, 80 comes from the fact that minimum requirement is 80. Now in the range 80 to

105 that we have here, now the function becomes minimized. 10 into X3 - 80 + 120 - X3, the

whole square + X3 - 100 whole square. X3 - 100, the whole square comes from S1 - 100 the whole

square.

So we have written both these functions for F2 star S2 depending on the range of values

of X3. So if X3 is in this range, we have one function. X3 is in the other range. We

have another function, so we have to separately optimize both these functions and find out

what is the minimum value of X3. In order to do that we differentiate the first expression

with respect to X3 and we equate it to 0.

So this would give us a 10. This would give us 2 times 120 - X3 into -1. This would give

us another 10. So we get 10 - 2 times 120 - X3 + 10 = 0 from which X3 star is = 110.

Second derivative is positive because we have a + 2X3 term that would give us a + 2 which

is positive at X3 = 110 and then the value of X3 star is = 110 is indeed a minimum. We

also need to check that, the X3 for this function will be within the range 105 to 120 and it

happens if 110 is within the range and so we do not have to worry.

If X3 star had exceeded 120 or were less than or equal to 105, then we substitute as the

extreme points to find out which one is the minimum. Now in this case we found out that

the optimum value which is 110 is in the range and we comfortably use this 110 and substituting

we get F2 star of 120 = 475. We go back and substitute here we get 400, 0 50, another

25 so put together we get 475. So now we go to other expression we have to get the value

of X3 keeping in mind the range. This would give us a 10, this would give us - 2 times

120, - X3 and this would give another 2 times X3 - 100. So we get 10 - 2 times 120 - X3

+ 2 times X3 - 100 = 0 from which X3 star = 107.5. Second derivative is positive because

there is a 2X3 here and a 2X3 here so 4X3 will be + 4 and so it is positive. We need

to look at something else. The value is 107.5 but we know it is valued between 80 and 105.The

optimum exceeds the range. So we need to go back and substitute whether it is minimum

at 80 or whether it is minimum at 105. Because this function is quadratic and because at

107.5, it is a minimum, we observe that within this range the value at 105 will be smaller

than the value at 80 so X3 star is actually 105 in this case and not 107.5. So we will

take 105, X3 star will be 105. When we substitute F2 star of 120 is 487.5.

In this case the optimum value of X3 star is 110 which is the best value corresponding

to the lower of 475 and 487.5. So F2 star of 120 is 475, X3 star is = 110. Now we proceed

again at N = 3, 3 more stages to go mean that we are somewhere here. We are here at the

beginning of the second month and we have a state variable and a decision variable too

to make. So at N = 3 more stages to go, assuming F3 is a state variable and X2 is the decision

variable. 10 times X2 - 120, 120 is the minimum requirement, X2 is what we are going to employ

for month 2 + S3 - X2 the whole square. This represents the change over cost + F2 star

of X2. Now F3 star of X3 which is the best value of this function is given by an X2 such

that it minimizes 10 times X2 - 120 + X3 - S2 the whole square + F2 star of X2. F2 star

of X2 comes because whatever we have as X2 in this month is available as S2 in next month

will be available X2 in the beginning of next month, subject to the condition, the minimum

X2 greater than or equal to 120 is also satisfied.

Now we have already seen that because of these 4 values 90, 120, 80 and 100. We know it is

not advisable to have more than 120 in the second month and therefore we have already

seen that 2 star is = 120. So all we need to do here is to show or to take the value

F2 star is = 120 which we know in this case, X2 star is = 120. So we are not going to optimize

this and find out 120, we may do that.

Since we know that 120 is maximum and we have already used this in the earlier result, we

have X2 star is = 120 and F3 star of X3 will be S3 - 120, the whole square + 475. When

X2 star is = 120, the under utilization cost is not present. There is no under utilization

because we are not employing more people. Only the change over cost is there. So whatever

is available as state variable is X3, from that X3, we are going to bring it to 120,

S3 - 120 the whole square + F2 star of X2 has been found out to be 475, so we add this

475 to get F3 star of X3 = S3 - 120 the whole square + 475.

Now we go to the last one N = 4, 4 more stages to go, which means we are at the beginning

of the problem, which means we are at the beginning of month 1. The requirement during

this period is 90. People available at the beginning of the planning period are available

at the beginning of month 1, is 100, so we go back to N = 4.

F4 of 100X1, this 100 comes in because 100 is the amount of people available at the beginning

of the first month and X1 is the decision. X1 is the number of people that we are going

to employ in the first month. So F4 of 100, X1 is 10 times X1 - 90. 90 is the minimum

requirement for month 1, so if we end up employing more than X1 then there will more than 90.

There will be an X1 - 90 which will add to the under utilization. So there is going to

be a change over cost, 100 - X1, the whole square represents the change over cost + F3

star of X1 F3 star of X1 comes because this F3 star of X1 is available as X2 at the beginning

of the stage F = 3. X1 is going to go as S2.

Earlier we had defined F3 star of S3. Now this X1 is going to go as F3 so we write F3

star of X1. F4 star of 100 is the best value that this function can take for a given state

variable which has a value 100 and that would minimize this function, 10 times X1 - 90 +

100 - X1, the whole square + X1 - 120 the whole square + 475. X1 - 120 the whole square

+ 475 comes from the earlier statement, X3 - 120 the whole square + 475. So the whole

thing repeats again and most importantly subject to the condition, X1 less than greater than

or equal to 90. Now this 90 is the minimum requirement that we need to have for this.

Now once again differentiating with reference to X1 and equating it to 0, we get this expression.

It would give us a 10. This would give us 2 times 100 - X1 into - 1 and this would give

us 2 times X1 - 120. Constant does not yield anything. So we get 10 - 2 times 100 - X1

+ 2 times X1 - 120 equals to 0 from which X1 star is = 107.5. Second derivative would

be positive because this is a 4X1 terms this is a 2X1 term. So together we have 4X1. So

the second derivative will be 4 and it is positive and therefore 107.5 is the minimum.

Now it also satisfies the condition X1 greater than or equal to 90 and therefore we are comfortable

and it is also less than 120 which is one of the assumptions we had made. So it also

satisfies that and therefore does not give any trouble or any difficulty. We comfortably

assumed the value 107.5. This is within the range and F4 star of 100 on substitution would

give us 107.5 - 90 is 17.5 multiplied by 10 gives us 175. 100 - 107.5 is 7.5 square which

is 56.25, 107.5 - 120 is 12.5 square is 156.25 + 475 gives us 862.5 as the cost. Now the

optimum solution is X1 star is = 107.5 that we found out. Now X2 star is 120 which we

assumed in this problem. X3 Star is 110 that we found out. X4 star was 105 which we also

found out right at the beginning because when X3 star is 110. We go back here at N = 1 X3

star is 110. It implies that S1 is 110, if S1 is greater than 105, therefore X4 star

will be S1 - 5. It will become 105 and the value of the objective function is 862.5

But there are a few other things. We realize that X1 star is not an integer. It represents

number of people employed. In the problem if we go back to the original problem, it

does not explicitly state that the decision variables are integers therefore we ignored

it and solved it as a continuous variable. Due to the quadratic nature of the objective

function, we can actually evaluate X1 star = 107 and X1 star = 108 finds out actually.

They both gave the same value of the objective functions. We can actually choose either of

them. This problem was made much simpler by the fact that the maximum demand occurred

at the second period making X2 star = 120. This considerably decreases.

We have used this for our advantage while solving this problem. So a quick summary of

this problem had a quadratic kind of an objective. It also gave us situation where as in this

stage, the function F1 takes the common 2 different values depending on the range of

the variables. We have to carry it forward to the next stage and then we need to solve

that. We continue our discussion in the next class with more examples.

The Description of Lec-19 Dynamic Programming - Continuous Variables