{
"metadata": {
"name": "",
"signature": "sha256:4cf11f099b505217c212be98a9c66635c10ab815dc28142018fcaae70660de9b"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 6,
"metadata": {},
"source": [
"The latest version of this IPython notebook is available at [http://github.com/jckantor/ESTM60203](http://github.com/jckantor/ESTM60203) for noncommercial use under terms of the [Creative Commons Attribution Noncommericial ShareAlike License (CC BY-NC-SA 4.0)](http://creativecommons.org/licenses/by-nc-sa/4.0/)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"J.C. Kantor (Kantor.1@nd.edu)"
]
},
{
"cell_type": "heading",
"level": 1,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Case Study - Landhills Winery"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This notebook demonstrates the use of linear programming to analyze the case study\n",
"\n",
">Owen Hall and Kenneth Ko. \"Landhills Winery: Developing an Optimal Blending Plan,\" 3 pages, HBS Case W14167-PDF-ENG, published May 21, 2014.\n",
"\n",
"The notebook uses MathProg/GLPK to represent the model and calculate solutions."
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Initializations"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%matplotlib inline\n",
"from pylab import *\n",
"\n",
"from IPython.core.display import HTML\n",
"HTML(open(\"styles/custom.css\", \"r\").read())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
""
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%script glpsol -m /dev/stdin -o /dev/stdout -y display.txt --out output\n",
"\n",
"set GRAPES;\n",
"set WINES;\n",
" \n",
"param gAcid{GRAPES};\n",
"param gSugr{GRAPES};\n",
"param gAlch{GRAPES};\n",
"param gQnty{GRAPES};\n",
"param gCost{GRAPES}; \n",
"\n",
"param wAcid{WINES};\n",
"param wSugr{WINES};\n",
"param wAlch{WINES};\n",
"param wPric{WINES};\n",
" \n",
"var x{WINES,GRAPES}, integer >= 0;\n",
"var wProd{WINES} >= 0;\n",
"var gCons{GRAPES} >= 0;\n",
"\n",
"maximize Profit : \n",
" sum{w in WINES} wPric[w]*wProd[w] - sum{g in GRAPES} gCost[g]*gCons[g];\n",
"\n",
"# balances\n",
"subject to grapes {g in GRAPES} : \n",
" sum{w in WINES} x[w,g] == gCons[g];\n",
"subject to wines {w in WINES} : \n",
" sum{g in GRAPES} x[w,g] == wProd[w];\n",
"\n",
"# bound on grapes\n",
"subject to capacity {g in GRAPES} : \n",
" gCons[g] <= gQnty[g];\n",
"\n",
"# acidity\n",
"subject to acidity {w in WINES} : \n",
" sum{g in GRAPES} x[w,g]*gAcid[g] <= wProd[w]*wAcid[w];\n",
"\n",
"# sugar\n",
"subject to sugar {w in WINES} : \n",
" sum{g in GRAPES} x[w,g]*gSugr[g] <= wProd[w]*wSugr[w];\n",
"\n",
"# Varietal content\n",
"subject to v1 {w in {'wSB11','wSL10','wSL11','wCabS'}} : \n",
" sum {g in {'gSB11','gSL10','gSL11'}} x[w,g] >= 0.75*wProd[w];\n",
"\n",
"subject to v2 {w in {'wMerl'}} : \n",
" sum {g in {'gMerl'}} x[w,g] >= 0.75*wProd[w];\n",
"\n",
"# alchohol content\n",
"subject to a1 {w in WINES} : \n",
" sum{g in GRAPES} x[w,g]*gAlch[g] >= 10.0*wProd[w];\n",
"subject to a2 {w in WINES} : \n",
" sum{g in GRAPES} x[w,g]*gAlch[g] <= 15.0*wProd[w];\n",
"\n",
"# vintage\n",
"subject to vn1 : \n",
" x['wSB11','gSB11'] >= 0.95*wProd['wSB11'];\n",
"subject to vn2 : \n",
" x['wSL10','gSL10'] >= 0.95*wProd['wSL10'];\n",
"subject to vn3 : \n",
" x['wSL11','gSL11'] >= 0.95*wProd['wSL11'];\n",
"\n",
"solve;\n",
"\n",
"printf \"Profit = %9.2f\\n\\n\", Profit;\n",
"for {w in WINES} {\n",
" printf \"%6s \", w;\n",
" printf \"%8.1f \", wProd[w];\n",
" for {g in GRAPES} printf \"%8.1f \", x[w,g];\n",
" printf \"\\n\";\n",
"}\n",
"\n",
"data;\n",
" \n",
"param : GRAPES : gAcid, gSugr, gAlch, gQnty, gCost :=\n",
" gSB11 0.35 0.12 13.5 50000 2.35\n",
" gSL10 0.75 0.25 15.3 60000 2.60\n",
" gSL11 0.55 0.30 11.5 30000 2.10\n",
" gMerl 0.25 0.08 15.7 200000 1.55;\n",
" \n",
"param : WINES : wAcid, wSugr, wPric :=\n",
" wSB11 0.7 0.2 9.00\n",
" wSL10 0.7 0.2 9.00\n",
" wSL11 0.7 0.2 9.00\n",
" wCabS 0.7 0.3 5.50\n",
" wMerl 0.3 1.0 2.95;\n",
"end;\n"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print(open('display.txt').read())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Profit = 809905.50\n",
"\n",
" wSB11 52631.0 50000.0 0.0 0.0 2631.0 \n",
" wSL10 0.0 0.0 0.0 0.0 0.0 \n",
" wSL11 0.0 0.0 0.0 0.0 0.0 \n",
" wCabS 93061.0 0.0 60000.0 9796.0 23265.0 \n",
" wMerl 121224.0 0.0 0.0 20204.0 101020.0 \n",
"\n"
]
}
],
"prompt_number": 126
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print output"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"GLPSOL: GLPK LP/MIP Solver, v4.52\n",
"Parameter(s) specified in the command line:\n",
" -m /dev/stdin -o /dev/stdout -y display.txt\n",
"Reading model section from /dev/stdin...\n",
"Reading data section from /dev/stdin...\n",
"73 lines were read\n",
"Generating Profit...\n",
"Generating grapes...\n",
"Generating wines...\n",
"Generating capacity...\n",
"Generating acidity...\n",
"Generating sugar...\n",
"Generating v1...\n",
"Generating v2...\n",
"Generating a1...\n",
"Generating a2...\n",
"Generating vn1...\n",
"Generating vn2...\n",
"Generating vn3...\n",
"Model has been successfully generated\n",
"GLPK Integer Optimizer, v4.52\n",
"42 rows, 29 columns, 186 non-zeros\n",
"20 integer variables, none of which are binary\n",
"Preprocessing...\n",
"37 rows, 25 columns, 169 non-zeros\n",
"20 integer variables, none of which are binary\n",
"Scaling...\n",
" A: min|aij| = 8.000e-02 max|aij| = 1.570e+01 ratio = 1.962e+02\n",
"GM: min|aij| = 4.751e-01 max|aij| = 2.105e+00 ratio = 4.430e+00\n",
"EQ: min|aij| = 2.257e-01 max|aij| = 1.000e+00 ratio = 4.430e+00\n",
"2N: min|aij| = 1.562e-01 max|aij| = 1.500e+00 ratio = 9.600e+00\n",
"Constructing initial basis...\n",
"Size of triangular part is 37\n",
"Solving LP relaxation...\n",
"GLPK Simplex Optimizer, v4.52\n",
"37 rows, 25 columns, 169 non-zeros\n",
"* 0: obj = 0.000000000e+00 infeas = 0.000e+00 (0)\n",
"* 14: obj = 8.099113856e+05 infeas = 0.000e+00 (0)\n",
"OPTIMAL LP SOLUTION FOUND\n",
"Integer optimization begins...\n",
"+ 14: mip = not found yet <= +inf (1; 0)\n",
"+ 63921: mip = not found yet <= 8.099075263e+05 (15571; 0)\n",
"+ 89096: mip = not found yet <= 8.099075263e+05 (21702; 0)\n",
"+106858: mip = not found yet <= 8.099075263e+05 (26028; 0)\n",
"+121867: mip = not found yet <= 8.099075263e+05 (29681; 0)\n",
"+135030: mip = not found yet <= 8.099075263e+05 (32887; 0)\n",
"+147134: mip = not found yet <= 8.099075263e+05 (35835; 0)\n",
"+157857: mip = not found yet <= 8.099075263e+05 (38447; 0)\n",
"+167910: mip = not found yet <= 8.099075263e+05 (40893; 0)\n",
"+177522: mip = not found yet <= 8.099075263e+05 (43230; 0)\n",
"+186554: mip = not found yet <= 8.099075263e+05 (45426; 0)\n",
"+194800: mip = not found yet <= 8.099075263e+05 (47428; 0)\n",
"Time used: 60.0 secs. Memory used: 20.6 Mb.\n",
"+202782: mip = not found yet <= 8.099075263e+05 (49361; 0)\n",
"+205452: >>>>> 8.099055000e+05 <= 8.099058632e+05 < 0.1% (50008; 1)\n",
"+205453: mip = 8.099055000e+05 <= tree is empty 0.0% (0; 100017)\n",
"INTEGER OPTIMAL SOLUTION FOUND\n",
"Time used: 61.7 secs\n",
"Memory used: 20.8 Mb (21850447 bytes)\n",
"Model has been successfully processed\n",
"Writing MIP solution to `/dev/stdout'...\n",
"Problem: stdin\n",
"Rows: 42\n",
"Columns: 29 (20 integer, 0 binary)\n",
"Non-zeros: 186\n",
"Status: INTEGER OPTIMAL\n",
"Objective: Profit = 809905.5 (MAXimum)\n",
"\n",
" No. Row name Activity Lower bound Upper bound\n",
"------ ------------ ------------- ------------- -------------\n",
" 1 Profit 809906 \n",
" 2 grapes[gSB11]\n",
" 0 -0 = \n",
" 3 grapes[gSL10]\n",
" 0 -0 = \n",
" 4 grapes[gSL11]\n",
" 0 -0 = \n",
" 5 grapes[gMerl]\n",
" 0 -0 = \n",
" 6 wines[wSB11] 0 -0 = \n",
" 7 wines[wSL10] 0 -0 = \n",
" 8 wines[wSL11] 0 -0 = \n",
" 9 wines[wCabS] 0 -0 = \n",
" 10 wines[wMerl] 0 -0 = \n",
" 11 capacity[gSB11]\n",
" 50000 50000 \n",
" 12 capacity[gSL10]\n",
" 60000 60000 \n",
" 13 capacity[gSL11]\n",
" 30000 30000 \n",
" 14 capacity[gMerl]\n",
" 126916 200000 \n",
" 15 acidity[wSB11]\n",
" -18683.9 -0 \n",
" 16 acidity[wSL10]\n",
" 0 -0 \n",
" 17 acidity[wSL11]\n",
" 0 -0 \n",
" 18 acidity[wCabS]\n",
" -8938.65 -0 \n",
" 19 acidity[wMerl]\n",
" 0 -0 \n",
" 20 sugar[wSB11] -4315.72 -0 \n",
" 21 sugar[wSL10] 0 -0 \n",
" 22 sugar[wSL11] 0 -0 \n",
" 23 sugar[wCabS] -8118.3 -0 \n",
" 24 sugar[wMerl] -107081 -0 \n",
" 25 v1[wSB11] 10526.8 -0 \n",
" 26 v1[wSL10] 0 -0 \n",
" 27 v1[wSL11] 0 -0 \n",
" 28 v1[wCabS] 0.25 -0 \n",
" 29 v2[wMerl] 10102 -0 \n",
" 30 a1[wSB11] 189997 -0 \n",
" 31 a1[wSL10] 0 -0 \n",
" 32 a1[wSL11] 0 -0 \n",
" 33 a1[wCabS] 465304 -0 \n",
" 34 a1[wMerl] 606120 -0 \n",
" 35 a2[wSB11] -73158.3 -0 \n",
" 36 a2[wSL10] 0 -0 \n",
" 37 a2[wSL11] 0 -0 \n",
" 38 a2[wCabS] -0.5 -0 \n",
" 39 a2[wMerl] 0 -0 \n",
" 40 vn1 0.55 -0 \n",
" 41 vn2 0 -0 \n",
" 42 vn3 0 -0 \n",
"\n",
" No. Column name Activity Lower bound Upper bound\n",
"------ ------------ ------------- ------------- -------------\n",
" 1 x[wSB11,gSB11]\n",
" * 50000 0 \n",
" 2 x[wSL10,gSB11]\n",
" * 0 0 \n",
" 3 x[wSL11,gSB11]\n",
" * 0 0 \n",
" 4 x[wCabS,gSB11]\n",
" * 0 0 \n",
" 5 x[wMerl,gSB11]\n",
" * 0 0 \n",
" 6 x[wSB11,gSL10]\n",
" * 0 0 \n",
" 7 x[wSL10,gSL10]\n",
" * 0 0 \n",
" 8 x[wSL11,gSL10]\n",
" * 0 0 \n",
" 9 x[wCabS,gSL10]\n",
" * 60000 0 \n",
" 10 x[wMerl,gSL10]\n",
" * 0 0 \n",
" 11 x[wSB11,gSL11]\n",
" * 0 0 \n",
" 12 x[wSL10,gSL11]\n",
" * 0 0 \n",
" 13 x[wSL11,gSL11]\n",
" * 0 0 \n",
" 14 x[wCabS,gSL11]\n",
" * 9796 0 \n",
" 15 x[wMerl,gSL11]\n",
" * 20204 0 \n",
" 16 x[wSB11,gMerl]\n",
" * 2631 0 \n",
" 17 x[wSL10,gMerl]\n",
" * 0 0 \n",
" 18 x[wSL11,gMerl]\n",
" * 0 0 \n",
" 19 x[wCabS,gMerl]\n",
" * 23265 0 \n",
" 20 x[wMerl,gMerl]\n",
" * 101020 0 \n",
" 21 wProd[wSB11] 52631 0 \n",
" 22 wProd[wSL10] 0 0 \n",
" 23 wProd[wSL11] 0 0 \n",
" 24 wProd[wCabS] 93061 0 \n",
" 25 wProd[wMerl] 121224 0 \n",
" 26 gCons[gSB11] 50000 0 \n",
" 27 gCons[gSL10] 60000 0 \n",
" 28 gCons[gSL11] 30000 0 \n",
" 29 gCons[gMerl] 126916 0 \n",
"\n",
"Integer feasibility conditions:\n",
"\n",
"KKT.PE: max.abs.err = 0.00e+00 on row 0\n",
" max.rel.err = 0.00e+00 on row 0\n",
" High quality\n",
"\n",
"KKT.PB: max.abs.err = 0.00e+00 on row 0\n",
" max.rel.err = 0.00e+00 on row 0\n",
" High quality\n",
"\n",
"End of output\n",
"\n"
]
}
],
"prompt_number": 127
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%script glpsol -m /dev/stdin -o /dev/stdout -y display.txt --out output\n",
"\n",
"set VARIETALS := {'SB2011','SLO2010','SLO2011'};\n",
"set NONVARIETALS := {'Cab','Merlot'};\n",
"set CABERNETs := {'SB2011','SLO2010','SLO2011','Cab'};\n",
"\n",
"\n",
"param price{WINES};\n",
"\n",
"param acidity{GRAPES};\n",
"param sugar{GRAPES};\n",
"param alcohol{GRAPES};\n",
"param quantity{GRAPES};\n",
"param cost{GRAPES}; \n",
" \n",
"var x{WINES,GRAPES} >= 0;\n",
"var wine{WINES} >= 0;\n",
"var grape{GRAPES} >= 0;\n",
"\n",
"maximize PROFIT: sum{w in WINES} wine[w]*price[w] - sum{g in GRAPES} grape[g]*cost[g];\n",
"\n",
"subject to g_cons{g in GRAPES}: sum{w in WINES} x[w,g] = grape[g];\n",
"subject to w_prod{w in WINES}: sum{g in GRAPES} x[w,g] = wine[w];\n",
" \n",
"subject to acid{w in WINES}\n",
"\n",
"subject to qty{g in GRAPES}: sum{w in WINES} x[w,g] <= quantity[g];\n",
"\n",
"solve;\n",
"\n",
"data;\n",
"\n",
"param : WINES : price :=\n",
" V1 9.00\n",
" V2 9.00\n",
" V3 9.00\n",
" NV 5.50\n",
" M 2.95;\n",
"\n",
"param : GRAPES : acidity, sugar, alcohol, quantity, cost :=\n",
" G1 0.35 0.12 13.5 50000 2.35\n",
" G2 0.75 0.25 15.3 60000 2.60\n",
" G3 0.55 0.30 11.5 30000 2.10\n",
" G4 0.25 0.08 15.7 200000 1.55;\n",
" \n",
"end;\n"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 91
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Looking at the model output"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print output"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"GLPSOL: GLPK LP/MIP Solver, v4.52\n",
"Parameter(s) specified in the command line:\n",
" -m /dev/stdin -o /dev/stdout -y display.txt\n",
"Reading model section from /dev/stdin...\n",
"Reading data section from /dev/stdin...\n",
"41 lines were read\n",
"Generating PROFIT...\n",
"Generating g_cons...\n",
"Generating w_prod...\n",
"Generating qty...\n",
"Model has been successfully generated\n",
"GLPK Simplex Optimizer, v4.52\n",
"14 rows, 29 columns, 78 non-zeros\n",
"Preprocessing...\n",
"4 rows, 20 columns, 20 non-zeros\n",
"Scaling...\n",
" A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00\n",
"Problem data seem to be well scaled\n",
"Constructing initial basis...\n",
"Size of triangular part is 4\n",
"* 0: obj = 0.000000000e+00 infeas = 0.000e+00 (0)\n",
"* 4: obj = 2.413500000e+06 infeas = 0.000e+00 (0)\n",
"OPTIMAL LP SOLUTION FOUND\n",
"Time used: 0.0 secs\n",
"Memory used: 0.1 Mb (142786 bytes)\n",
"Model has been successfully processed\n",
"Writing basic solution to `/dev/stdout'...\n",
"Problem: stdin\n",
"Rows: 14\n",
"Columns: 29\n",
"Non-zeros: 78\n",
"Status: OPTIMAL\n",
"Objective: PROFIT = 2413500 (MAXimum)\n",
"\n",
" No. Row name St Activity Lower bound Upper bound Marginal\n",
"------ ------------ -- ------------- ------------- ------------- -------------\n",
" 1 PROFIT B 2.4135e+06 \n",
" 2 g_cons[G1] NS 0 -0 = 2.35 \n",
" 3 g_cons[G2] NS 0 -0 = 2.6 \n",
" 4 g_cons[G3] NS 0 -0 = 2.1 \n",
" 5 g_cons[G4] NS 0 -0 = 1.55 \n",
" 6 w_prod[V1] NS 0 -0 = -9 \n",
" 7 w_prod[V2] NS 0 -0 = -9 \n",
" 8 w_prod[V3] NS 0 -0 = -9 \n",
" 9 w_prod[NV] NS 0 -0 = -5.5 \n",
" 10 w_prod[M] NS 0 -0 = -2.95 \n",
" 11 qty[G1] NU 50000 50000 6.65 \n",
" 12 qty[G2] NU 60000 60000 6.4 \n",
" 13 qty[G3] NU 30000 30000 6.9 \n",
" 14 qty[G4] NU 200000 200000 7.45 \n",
"\n",
" No. Column name St Activity Lower bound Upper bound Marginal\n",
"------ ------------ -- ------------- ------------- ------------- -------------\n",
" 1 x[V1,G1] B 50000 0 \n",
" 2 x[V2,G1] NL 0 0 < eps\n",
" 3 x[V3,G1] NL 0 0 < eps\n",
" 4 x[NV,G1] NL 0 0 -3.5 \n",
" 5 x[M,G1] NL 0 0 -6.05 \n",
" 6 x[V1,G2] B 60000 0 \n",
" 7 x[V2,G2] NL 0 0 < eps\n",
" 8 x[V3,G2] NL 0 0 < eps\n",
" 9 x[NV,G2] NL 0 0 -3.5 \n",
" 10 x[M,G2] NL 0 0 -6.05 \n",
" 11 x[V1,G3] B 30000 0 \n",
" 12 x[V2,G3] NL 0 0 < eps\n",
" 13 x[V3,G3] NL 0 0 < eps\n",
" 14 x[NV,G3] NL 0 0 -3.5 \n",
" 15 x[M,G3] NL 0 0 -6.05 \n",
" 16 x[V1,G4] B 200000 0 \n",
" 17 x[V2,G4] NL 0 0 < eps\n",
" 18 x[V3,G4] NL 0 0 < eps\n",
" 19 x[NV,G4] NL 0 0 -3.5 \n",
" 20 x[M,G4] NL 0 0 -6.05 \n",
" 21 wine[V1] B 340000 0 \n",
" 22 wine[V2] B 0 0 \n",
" 23 wine[V3] B 0 0 \n",
" 24 wine[NV] B 0 0 \n",
" 25 wine[M] B 0 0 \n",
" 26 grape[G1] B 50000 0 \n",
" 27 grape[G2] B 60000 0 \n",
" 28 grape[G3] B 30000 0 \n",
" 29 grape[G4] B 200000 0 \n",
"\n",
"Karush-Kuhn-Tucker optimality conditions:\n",
"\n",
"KKT.PE: max.abs.err = 0.00e+00 on row 0\n",
" max.rel.err = 0.00e+00 on row 0\n",
" High quality\n",
"\n",
"KKT.PB: max.abs.err = 0.00e+00 on row 0\n",
" max.rel.err = 0.00e+00 on row 0\n",
" High quality\n",
"\n",
"KKT.DE: max.abs.err = 0.00e+00 on column 0\n",
" max.rel.err = 0.00e+00 on column 0\n",
" High quality\n",
"\n",
"KKT.DB: max.abs.err = 0.00e+00 on row 0\n",
" max.rel.err = 0.00e+00 on row 0\n",
" High quality\n",
"\n",
"End of output\n",
"\n"
]
}
],
"prompt_number": 55
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}