For everybody, welcome back.

In this lesson,we are going to discuss ways of showing optimality.

As a warm up example,

consider the following situation.

Imagine a small chocolate factory that produces two types of chocolate,

milk chocolate and dark chocolate.

The price per box of milk chocolate is $10,

and the price per box of the dark chocolate is $30.

Okay. So, the estimated daily demands are

500 boxes of milk chocolate and 200 boxes of dark chocolate.

Unfortunately, the factory cannot fully

satisfy these daily demands because it can produce,

at most, 600 boxes per day.

So, on these given constraints,

the natural question is,

what is the optimum production plan?

To find it out,

they go to a consulting company,

and the consulting company claims that the optimum profit per day is $10,000.

So, the question is now,

how can the consulting company convince the factory that it is indeed optimal?

So, in general, such proof of optimality consists of two parts.

The first part is the so-called existential part.

In this case, we need to show that there exists a production plan,

achieving the value of $10,000.

All right.

And the other part is the so-called universal part.

We need to show that for all plans, the profits that they'll achieve is at most 10,000.

Let's start with the existential part.

So once again, for this,

we need to give the explicit production plan,

achieving $10,000 per day.

And for this, the consulting company suggests that the factory needs to

produce 400 boxes of milk chocolate per day and 200 boxes of dark chocolate per day.

First of all, we need to check whether all the constraints are satisfied,

and this is not difficult to do.

First of all, in the proposal plan,

the factory produces no more than 500 boxes of milk chocolate and

also no more than 200 boxes of dark chocolate,

and then total, no more than 600 boxes.

And indeed, the profit can also be easily computed.

This is 400 boxes of milk chocolate x $10 per

box + 200 boxes of dark chocolate x $30 per box of dark chocolate.

This gives exactly 10,000. So, we are done with the existential part.

Now we need to show the universal part,

mainly, we need to show that in any production, in any valid production plan,

mainly in any plan satisfying all the given constraints,

the profit is at most 10,000.

Okay, so for this, let's denote by M,

and these are number of boxes of milk and dark chocolate,

respectively, produced per day.

Then we are given the following constraints,

M should be at most 500, D should be at most 200, these are our estimated daily demands,

and M+D should be at most 600,

because the factory can not produce more than 600 boxes per day.

What we would like to show is that,

under these constraints, the profit is at most $10,000.

The profit is computed as 10 times M plus 30 times D. Okay.

So to prove this,

it is enough actually to compute the sum of the following two inequalities.

The first inequality is,

10M+10D is at most 6,000.

So it comes by multiplying this inequality M+D is at most, 600 by 10.

Then we do multiply it by 10,

we get 10M+10D is at most 6,000.

On the other hand, we can also get this inequality,

D is at most 200 and multiply it by 20,

then we'll get 20D is at most 4,000.

then if we compute the sum of these two inequalities, then

what we get is exactly what we want to get,

the sum, that the profit is at most 10,000.

Well, that was easy, right?

And it was actually clear from the very beginning that in this case,

the optimal production plan actually is to produce as

much dark chocolate as needed and only then to produce milk chocolate.

But the message of this short warm up video

was not about chocolate, but about optimality.

So once again, to show that some value alpha is optimal,

what we usually need to do is to show that,

first of all, this value is achievable, that is,

to provide some solutions that achieves the value alpha,

this is the existential statement.

And then we need to show the universal statement,

that all solutions achieve the value not greater than alpha.

So in this lesson we are going to

show several such examples of optimality, following the same pattern.