Formulating an Optimization Problem
The key to the application of optimization is to be able to formulate the problem as a mathematical model.
Step 1: Identify 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.
Label or name the decision variables. In this example, A1, A2, A3, A4, B1, B2, B3, and so on. A$ represents the quantity shipped from supplier A to customer 4.
Step 2: Formulate the constraints. Constraints are formulated as functions of the decision variables.
In this example, there are 3 sets of constraints:
B1+B2+B3+B4 <= 50
C1+C2+C3+C4 <= 70
D1+D2+D3+D4 <= 40
E1+E2+E3+E4 <= 20
A2+B2+C2+D2+E2 >= 25
A3+B3+C3+D3+E3 >= 35
A4+B4+C4+D4+E4 >= 65
Step 3: Formulating 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.
In this example, the objective function is the sum of the product of each cost times its corresponding decision variable.
Step 1: Identify 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.
Label or name the decision variables. In this example, A1, A2, A3, A4, B1, B2, B3, and so on. A$ represents the quantity shipped from supplier A to customer 4.
Step 2: Formulate the constraints. Constraints are formulated as functions of the decision variables.
In this example, there are 3 sets of constraints:
- Limit the total amount shipped from each supplier based on their capacities:
B1+B2+B3+B4 <= 50
C1+C2+C3+C4 <= 70
D1+D2+D3+D4 <= 40
E1+E2+E3+E4 <= 20
- Make sure that the solution satisfies the demand:
A2+B2+C2+D2+E2 >= 25
A3+B3+C3+D3+E3 >= 35
A4+B4+C4+D4+E4 >= 65
- Non-negativity constraints
Step 3: Formulating 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.
In this example, the objective function is the sum of the product of each cost times its corresponding decision variable.
The above function will give us the total cost of transportation for our example.
