business case 3
rosni
BinaryLinearOptimizationAnalysis.htm.zipimscc34599479a8a84f22b9904c3e83ad8ac4/U10R/C72R/Binary Linear Optimization Analysis.htm
Binary Linear Optimization Analysis
When we perform a linear optimization analysis, if the value of decision variables can only be either 0 or 1, we call this analysis a binary linear optimization analysis. A binary linear optimization analysis consists of four major steps: (1) identify the objective variable and decision variables; (2) create the objective function; (3) find out the constraints; (4) specify the decision variables to be binary. I use an example to show everyone how we use this technique in a logistics analysis process.
Example:
An online shopping website plans to build distribution centers to serve customers from 20 counties as shown in the picture below. Each distribution center should serve customers either from the county OR from the adjacent counties. What is the minimum number of distribution centers needed to cover all 20 counties?
To simply the analysis, we give each county an id number. For instance, 1 represents Ashtabula county; 2 represents Lake county, etc.
(1) Identify the objective variable and decision variables
Objective variable: Total number of distribution centers needed to serve these 20 counties. We use N to denote this number.
Decision variables: To calculate the objective variable, we need to count how many counties have distribution centers. There are two possibilities in each county: It either has a distribution center OR not has one. Let
: the
number of distribution center in a county;
i: the id number
of each county, i
{1, 2, 3,
�., 20}
Thus, �= 1 if there
is a distribution center in a county; otherwise,
�= 0 for
that county. For instance, in Ashtabula county (county id i = 1),
�= 1 if
Ashtabula county has a distribution center;
�= 0 if
Ashtabula county does not have a distribution center. InLake county (county id i = 2),
�= 1 if
Lake county has a distribution center;
�= 0 if
Lake county does not have a distribution center, etc.
(2) Create the objective function
N =
Our objective is to minimize N
(3) Find out the constraints
The constraint in this case is that each distribution center must serve customers either from the county OR from the adjacent counties. Because we don�t know which counties would have the distribution centers yet, we should build the constraint for each county. For instance, for Ashtabula county, it is adjacent to Lake county, Geauga county, and Trumbull county, as shown in the map on page 1. No matter where the distribution center is finally built among these counties, there must be at least one that serves Ashtabula county. Thus, the constraint for Ashtabula county is
≥ 1
We should establish such a constraint for each county. For instance, for Lake county, it is adjacent to Ashtabula county, Cuyahoga county, and Geauga county. Thus, the constraint for Lake county is
≥ 1
For some counties that are adjacent to several other counties, the constraint could be stricter. For instance, for Geauga county, it is adjacent to 6 counties (Ashtabula, Lake, Cuyahoga, Summit, Portage, and Trumbull), we have
≥ 1
In other words, no matter where the distribution centers are finally built, there must be at least one that serves the Geauga county.
Using Solver
(1) Open the source data file �Binary in Logistic Management.xlsx�
In the data set, we first build a 20 by 20 matrix to indicate the counties locations in a mathematical way. We mark 1 if two counties share a border (i.e., adjacent geographically). We mark 0 if two counties do not share a border.
(2) Objective and Decision variables
We use cells from C32 to V32 to contain the decision variables. If there is a distribution center in a county, the value for the decision variable will be 1; otherwise, it will be 0.
We use cell D29 to contain the objective variable (i.e., the total number of distribution centers needed). In D29, we type in
=SUM(C32:V32)
Our goal is to minimize the value in cell D29.
(3) Set up constraints
In cell B35, we type in
=SUMPRODUCT($C$32:$V$32,C6:V6)
Note:
=SUMPRODUCT($C$32:$V$32,C6:V6) equals to =$C$32*C6 + $D$32*D6 + $E$32*E6 + � + $V$32*V6
We use this function (i.e., =SUMPRODUCT($C$32:$V$32,C6:V6)) to see if there is at least one distribution center serving the Ashtabula county.
We then drag the autofill button of B35 to the rest of counties
(4) Set up Solver as shown below. See step (5) of how to set up the constraints.
(5) How to set up the constraints
Click Add next to the �Subject to the Constraints� box
In the left hand box, select cellsfrom B35 to B54. In the dropdown list in the middle, choose >=, and type in 1 in the right hand box, and click OK to add the first constraint.
Click Add next to the �Subject to the Constraints� box again.
In the left hand box, select cellsfrom C32 to V32. In the dropdown list in the middle, choose bin, and then the value in the right hand box will change to binary automatically. Click OK to confirm. By doing so, we specify the decision variables can get either a 0 or a 1 as the value.
(6) After clicking the Solve button, choose �Keep Solver Solution�, and click OK.
From the analysis result, we find that the distribution centers should be built in Ashland county, Stark county, and Geauga county. By doing so, we need a minimum of 3 distribution centers to serve all 20 counties.
As you can see in this example, the binary analysis is a very useful technique for logistic optimization, location based service, and supply chain management. Please keep this tutorial for your advanced analytics courses such as Project Management.
