0:00

As we saw in the introduction, the three in an optimization model

are the decision variables, the objective function, and the constraints.

The key to the application of optimization is to be able to formulate

the problem as a mathematical model, this requires practice.

So in this video, we will follow a systematic

process to translate a decision problem in to a mathematical model.

We will focus on the transportation problem

that we describe in the introduction of this module.

In the transportation problem, we want to find the best way of moving units of

product from one set of suppliers to a set of customers.

The suppliers have limited capacity to meet the customer's demands.

There is a cost associated with moving one unit of product from a supplier

to a customer.

So, in terms of data there are three sets of values, capacity, demand, and

transportation costs.

The first step is to identify the decision variables.

In this problem there is only one set of decision variables,

the quantity to be shipped from each supplier to each customer.

Since there are five suppliers and four customers,

there are four times five, or 20 decision variables in this problem.

1:19

We then need to give each variable a unique name.

See the suppliers are labeled A to E and the customers are labeled 1 to 4,

we can create a name this is a combination of these two labels.

In this way, A1, A2, A3, and

A4 represent the quantities shipped from supplier A to customers 1, 2, 3, and 4.

The same is done for

the other suppliers, resulting in 20 unique names shown in this table.

The second step is to formulate the constraints,

this problem has two main sets of constraints.

One set of constraints to limit the total amount shipped from each supplier and

another set of constraints to make sure that the solution satisfies the demand.

2:08

Constraints are formulated as functions of the decision variables.

In this course we are going to focus on linear functions.

This means that constraints will be the sums of all differences of variables or

sums of differences of variables multiplied by constants.

Let's formulate the capacity constraints.

Since we want to limit the amount of units shipped from each supplier,

we calculate the total units shipped from each supplier.

The total quantities sent by Supplier A is the sum of all the quantities

sent from this location, that is A1+A2+A3+A4.

Since this amount should not exceed the capacity of the supplier,

then the constraint is that the sum of the shipments from Supplier A should be

less than or equal to 60.

The capacity constraints for the other suppliers are formulated in a similar way.

Now, let's formulate the demand constraints.

The total quantity that each customers receives is the sum of the units

shipped from a supplier.

For example, the total number of units received by customer is the sum of A1 + B1

+ C1 + D1 + E1.

This is the sum of the shipments to

customer 1 from all suppliers.

In order to satisfy customer A demand this sum should be greater than or equal to 75.

The same logic applies to the other three customers

to formulate their demand constraints.

There is one more thing that must be added that is

very common in these type of mathematical models.

In most problems, the only meaningful value for

the decision variables are positive.

In other words, negative values for the decision variables often have no meaning.

3:56

If you think about it, in all formulation of the transportation problem,

negative values for the decision variables have no meaning.

The only possible interpretation of a negative shipment would be

product that is returned to the supplier.

4:17

This means that we need to add bounds for

the decision variables to force it to be positive.

So we simply say that all the variables in the model are non-negative.

In these bounds are known as non-negativity constraints.

4:33

The third and final step consists of formulating the objective function.

This is the mathematical expression that evaluates the quality of the solution.

In optimization we want to find the best solution to our problem.

Where best means that the solution achieves the maximum or

the minimum value of the objective function.

For the transportation problem, best means a solution that minimizes

the total cost of supplying the product needed to satisfy all the demand.

5:12

We're going to focus on linear objective functions.

We have a table of costs, in which each entry

represents the cost of sending a unit of product from a supplier to a customer.

We also have decision variables that represent the number of units shipped from

each supplier to each customer.

Then, the objective function is the sum

of the product of each cost times its corresponding decision variable.

For example, the cost of shipping a unit of product from supplier A to customer 1,

is 3.

Since the decisions variable A1 represents all the units that are going to be sent

from supplier A to customer 1, then the cost of the quantity

sent from supplier A to customer 1 is 3 times A1.

All the other costs are calculated in that similar way.

The total cost is the sum of all these products.

The total cost function is linear

because it is the sum of variables that are multiplied by constant values.

6:45

By that I mean models with many decision variables and many constraints.

This is why, whenever possible, analysts use

only linear functions to formulate the constraints and the objective function.

I just want to mention one more thing before we go.

In our example we have bounds for

the decision variables and two types of general constraints.

A set of less than or equal constraints to model capacity and

a set of greater than or equal constraints to model demand.

7:16

It is also possible to use equality constraints in these models.

So remember, you can use linear functions to formulate constraints and

the objective.

And if you can represent all restrictions of the problem with equality or

inequality constraints, then you have linear programming model, for

which they are very efficient solution methods.