Difference between revisions of "OR-Tools/C2/Linear-Programming-with-two-index-variables/English"
Nancyvarkey (Talk | contribs) |
Nancyvarkey (Talk | contribs) |
||
Line 331: | Line 331: | ||
|Here is an assignment for you. | |Here is an assignment for you. | ||
− | + | * Here we have 2 plants and 2 sites. Transportation cost is given in the table. | |
− | + | * Hint: Formulate this problem as explained in the previous example. | |
− | + | * Please solve it using '''Karmarkar function''' and verify. | |
− | + | * The optimal value should be 520 and | |
− | + | * The optimal solution should have x1,2=60, x2,1= 100 , and all others have zero. | |
|- | |- | ||
Line 348: | Line 348: | ||
In this tutorial, we have learnt: | In this tutorial, we have learnt: | ||
− | + | * About variables with two indices. | |
− | + | * Example of '''LP''' with two-index variables and its input parameters. | |
− | + | * We have also learnt to apply '''Karmarkar function''' to solve '''Linear Transportation problem''' in '''Scilab'''. | |
|- | |- | ||
Line 363: | Line 363: | ||
'''FOSSEE''' stands for Free and Open Source Software for Education. | '''FOSSEE''' stands for Free and Open Source Software for Education. | ||
− | |||
− | + | This project promotes the use of free and open source software tools. | |
+ | |||
+ | |||
+ | For more details, please visit: http://fossee.in/ | ||
|- | |- | ||
|Slide 21 | |Slide 21 | ||
About the Spoken Tutorial Project | About the Spoken Tutorial Project | ||
− | |||
− | |||
| | | | ||
The video at this link summarises the Spoken Tutorial project. | The video at this link summarises the Spoken Tutorial project. | ||
Please download and watch it. | Please download and watch it. | ||
+ | |||
|- | |- | ||
|Slide 22 | |Slide 22 |
Latest revision as of 06:16, 30 May 2015
Time | Narration |
Slide 1
Welcome |
Welcome to the spoken tutorial on solving Linear Programming problems with two-index variables in Scilab. |
Slide 2
Objective |
In this tutorial, we will learn how to:
|
Slide 3
Prerequisites |
In order to understand this tutorial:
|
Slide 4
Terminology |
In this tutorial, we will refer to:
|
Slide 5
What is two-index variable? |
|
Slide 6
What is Transportation Problem? |
To understand the transportation problem, we consider the following network as an example.
This network has three supply nodes - plant P1, plant P2 and plant P3, two demand nodes - site S1 and site S2.
Similarly, goods from P2 to S1 and S2 with transporting cost c2,1 and c2,2. Goods from P3 to S1 and S2 with transporting cost c3,1 and c3,2, respectively.
|
Slide 7
Transportation Problem Example |
|
Slide 8
Transportation Problem Example |
Point to the table.
|
Slide 9
Decision Variable |
|
Slide 10
Formulation |
Formulation of this problem is:
* Objective function: Minimize 3 x1,1 plus 2x1,2 plus x2,1 plus 5x2,2 plus 5x3,1 plus 4x3,2. * Constraints: Since plant-1 can not supply more than its capacity, therefore we have x1,1 plus x1,2 is less than or equal to forty five Similary for plant-2, we have x2,1 plus x2,2 is less than or equal to sixty Similary for plant-3, we have x3,1 plus x3,2 is less than or equal to thirty five * Demand at the site-1 must be met, therefore we have x1,1 plus x2,1 plus x3,1 is greater than or equal (>=) to fifty. It is equivalent to minus x1,1 minus x2,1 minus x3,1 is less than or equal (<=)to minus fifty(-50). Both constraints are equivalent to each other. We multiplied with -1 to make inequality constraints in 'less than or equal to' form for Karmarkar function. Similarly at site-2, we have x1,2 plus x2,2 plus x3,2 is greater than or equal to (>=) sixty. It is equivalent to minus x1,2 minus x2,2 minus x32 is less than or equal (<=) to minus sixty(-60).
* xi,j is greater than or equal to zero (This is because transported quantity can not be negative). i is 1, 2, 3 because we have 3 supply nodes in this example. And j is 1, 2 because we have two demand nodes. |
Slide 11
Karmarkar Function in Scilab |
|
Slide 12
Karmarkar Function in Scilab |
Minimize c transpose X. subject to AeqX is equal to beq which means constraints have equality sign. AX less than or equal to b which means constraints with greater than or equal to sign must be by multiplied by -1. lb less than or equal to X less than or equal to ub. Where, lb stands for lower bounds and ub stands for upper bounds on the variables. c transpose, Aeq, beq, A, b, lb and ub are the known parameters. x is the vector of decision variables. |
Slide 13
Input Parameters |
Coming back to our example.
The coefficient vector of objective function is c transpose 3 2 1 5 5 4. This vector size will change according to the example.In our example, it contains 6 numbers. |
Slide 14
Input Parameters |
The coefficient matrix of constraints is capital A . In the first row, we have 1 1 and rest of the values are zero. This is because in our 1st constraint only variables x1,1 and x1,2 are present, and rest of the variables have zero coefficient. Row 2 is 0 0 1 1 0 0 because 2nd constraint has variables x2,1 and x2,2. And Row 3 is 0 0 0 0 1 1 because 3rd constraint has variables x3,1 and x3,2. In fourth row, we have -1 0 -1 0 -1 0. This because in our 4th constraint only variables are x1,1, x2,1 and x3,1 are present. 5th row is 0 -1 0 -1 0 -1 because 5th constraint has variables x1,2, x2,2 and x3,2. |
Slide 15
Input Parameters |
|
Slide 16
Steps to download the required code |
I have a working example with me. I will open my file opt.sce in the Scilab console.
|
c = [3;2;1;5;5;4]; |
In the formulation of TP, c is the coefficient vector of the objective function. |
A = [ 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 -1 0 -1 0 -1 0 0 -1 0 -1 0 -1 ]; |
Capital A is the coefficient matrix of constraints. |
b=[45;60;35;-50;-60]; |
b is the vector of right hand side of constraints. |
lb=[0;0;0;0;0;0]; |
lb is the vector of the lower bound of the variables. |
ub =[]; |
Upper bound is empty vector because we do not require it in this example. |
[xopt,fopt,exitflag,iter,yopt]= karmarkar([],[],c,[],[],[],[],[],A,b,lb,ub) |
Now we can call the Karmarkar function to solve TP. Each parameter in this function is explained in the spoken tutorial mentioned earlier. In TP, four parameters c, A, b, lb and ub will always be present, and rest will be empty. |
disp(xopt,'Optimal solution') |
This line will display xopt value, which is the optimal solution of TP. |
disp(fopt, 'Optimal value') |
This line will display fopt value, which is the optimal value of TP. |
Now, click on the Execute button. After that, go back to Scilab console to see the results. | |
Optimal-solution
0.0000691 44.999793 50.000138 0.0002763 0.0000691 15. |
The optimal solution and optimal value are given.
First value is x1,1, second value is x1,2, third value is x2,1, fourth value is x2,2, fifth value is x3,1 and sixth value is x3,2. Note x1,1 can be taken as zero since the decimal value after zero, is floating point error. x1,2 can be rounded upto forty five. x2,1 can be rounded to fifty. x2,2 and x3,1 can be rounded to zero. |
Optimal-value
200.00166 |
Optimal value is two hundred only as decimal places are only floating point errors. |
Slide 17
Result |
In our example, red edges denote the non zero variables in the optimal solution.
In the optimal solution, we can transport, 45 tons from plant-1 to site-2 with transportation cost 2 per ton, 50 tons from plant-2 to site-1 with transportation cost 1 per ton, 15 tons from plant-3 to site-2 with transportation cost 4 per ton. Other values of x are zero. So we do not transport goods on those paths. Thus, the minimum transportation cost to transport the goods is two hundred. |
Slide 18
Assignment |
Here is an assignment for you.
|
Slide 19
Summary |
This brings us to the end of this tutorial. Let us summarise.
In this tutorial, we have learnt:
|
Slide 20
FOSSEE |
OR Tools series is created by the FOSSEE Project, IIT Bombay. FOSSEE stands for Free and Open Source Software for Education.
|
Slide 21
About the Spoken Tutorial Project |
The video at this link summarises the Spoken Tutorial project. Please download and watch it. |
Slide 22
Spoken Tutorial Workshops |
The Spoken Tutorial Project Team conducts workshops and gives certificates on passing online tests. For more details, please write to us. |
Slide 23
Acknowledgements |
Spoken Tutorial Project is funded by NMEICT, MHRD, Government of India. More information on this Mission is available at http://spoken-tutorial.org /NMEICT-Intro
|
The script is created by Suraj Trivedi and this is Rahul Joshi from FOSSEE Project, IIT Bombay.
Thank you for joining. |