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.
