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.

Â