\n",
"\n",
"show code\n",
"\"\"\")"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
" show code\n",
" "
],
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%run ./loadoptfuncs.py\n",
"%matplotlib inline\n",
"toggle()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Introduction to Optimization\n",
"\n",
"All optimization models have several common elements:\n",
"\n",
"- **Decision variables** the variable whose values the decision maker is allowed to choose. The values of these variables determine such outputs as total cost, revenue, and profit.\n",
"\n",
"- An **objective function** (**objective**, for short) to be optimized – minimized or maximized. \n",
"\n",
"- **Constraints** that must be satisfied. They are usually physical, logical, or economic restrictions, depending on the nature of the problem. \n",
" * In searching for the values of the decision variables that optimize the objective, only those values that satisfy all of the constraints are allowed.\n",
" \n",
"To **optimize** means that you must systematically choose the values of the decision variables that make the objective as large (for maximization) or small (for minimization) as possible and cause all of the constraints to be satisfied.\n",
"\n",
"Any set of values of the decision variables that satisfies all of the constraints is called a **feasible solution**. The set of all feasible solutions is called the **feasible region**."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Linear Programming"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As one of the fundamental prescriptive analysis method, **linear programming (LP)** is used in all types of organizations, often on a daily basis, to solve a wide variety of problems such as advertising, distribution, investment, production, refinery operations, and transportation analysis.\n",
"\n",
"More formally, linear programming is a technique for the optimization of a **linear** objective function, subject to **linear equality and/or linear inequality** constraints.\n",
"\n",
"The main important feature of LP model is the presence of linearity in the problem. Some model may not be strictly linear, but can be made linear by applying appropriate mathematical transformations. Still some applications are not at all linear, but can be effectively approximated by linear models. LP models can be effectively solved by algorithms such as simplex, dual simplex and interior method. The ease with which LP models can usually be solved makes an attractive means of dealing with otherwise intractable nonlinear models."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problem Formulation\n",
"\n",
"The LP problem formulation is illustrated through a product mix problem. \n",
"\n",
"A PC manufacturer assembles and then tests two models of computers, Basic and XP. There are at most 10,000 assembly hours at the cost of $11 available and 3000 testing hours at the cost of $15 available.\n",
"\n",
"For each model, it has required assembly, testing hours, cost, price and estimated maximal sales.\n",
"\n",
"\n",
"Business assumptions:\n",
"- No computers are in inventory from the previous period (or no beginning inventory)\n",
"- Because these models are going to be changed after this month, the company doesn't want to hold any inventory after this period (no ending inventory)\n",
"\n",
"Business goal: the PC manufacturer wants to know\n",
"- how many of each model it should produce\n",
"- maximize its net profit\n",
"\n",
"Business constraints:\n",
"- resource constraints: available assembly and testing hours\n",
"- market constraints: maximal sales"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Algebraic Model"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The PC manufacturer wants to \n",
"\n",
"\\begin{align*}\n",
"\\text{maximize} \\quad \\text{Profit} &= \\text{Basic's unit margin} \\times \\text{Production of Basic} \\\\\n",
"& \\qquad \\qquad+ \\text{XP's unit margin} \\times \\text{Production of XP}\n",
"\\end{align*}\n",
"\n",
"subject to following constraints:\n",
"\\begin{align*}\n",
"&\\text{assembly hours:} & 5 \\times \\text{Production of Basic} + 6 \\times \\text{Production of XP} &\\le 10000 \\\\\n",
"&\\text{testing hours:} & \\text{Production of Basic} + 2\\times \\text{Production of XP} &\\le 3000 \\\\\n",
"&\\text{maximal sales:} & \\text{Production of Basic} &\\le 600 \\\\\n",
"&\\text{maximal sales:} & \\text{Production of XP} &\\le 1200 \\\\\n",
"\\end{align*}\n",
"\n",
"Intuitive constraints:\n",
"\\begin{align*}\n",
"\\text{Production of Basic} &\\ge 0 \\\\\n",
"\\text{Production of XP} &\\ge 0 \\\\\n",
"\\end{align*}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Graphical solution\n",
"\n",
"When there are only two decision variables in an LP model, as there are in this product mix problem, we can demonstrate the problem graphically."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "fa071b4328ef4c24a5b30b154d26edc2",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"interactive(children=(Checkbox(value=False, description='Zoom In'), Output()), _dom_classes=('widget-interact'…"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"interact(prodmix_graph,\n",
" zoom=widgets.Checkbox(value=False, description='Zoom In'));"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can modify objective coefficients in order to see how objective value changes in the feasible region."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"scrolled": false
},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "4071122f192843f0a91d6346163972c6",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"interactive(children=(Checkbox(value=False, description='Zoom In'), IntSlider(value=80, description='Margin Ba…"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"interact(prodmix_obj,\n",
" zoom=widgets.Checkbox(value=False, description='Zoom In', disabled=False),\n",
" margin1=widgets.IntSlider(min=-30,max=150,step=10,value=80,description='Margin Basic:',\n",
" style = {'description_width': 'initial'}),\n",
" margin2=widgets.IntSlider(min=-30,max=150,step=10,value=129,description='Margin XP:',\n",
" style = {'description_width': 'initial'}));"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Because of this geometry, the optimal solution is always a corner point of the polygon. The simplex method for LP works so well because it can search through the finite number of corner points extremely efficiently and recognize when it has found the best corner point. This simple insight, plus its effective implementation in software package, has saved companies many millions of dollars."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sensitivity Analysis\n",
"\n",
"In real LP applications, solving a model is simply the beginning of the analysis. It is always crucial to perform a sensitivity analysis to see how (or if) the optimal solution changes as one or more inputs vary. The sensitivity report from excel shows\n",
"\n",
"**Variable Cells**\n",
"\n",
"| Cell | Name | Final Value | Reduced Cost | Objective Coefficient | Allowable Increase | Allowable Decrease |\n",
"| ----------- | ---- | ----- | ------- | ----------- | --------- | -------- |\n",
"|$B$16 | Number to produce Basic | 560 | 0\t| 80 | 27.5 | 80 |\n",
"|$C$16 | Number to produce XP\t | 1200 | 33\t| 129 | 1E+30 |\t33 |\n",
"\n",
"- Final Value: the optimal solution\n",
"\n",
"- Reduced Cost: it is relevant only if the final value is equal to either 0 or its upper bound. It indicates how much the objective coefficient of a decision variable (which is currently 0 or at its upper bound) must change before that variable changes. For example:\n",
" - the number of XPs will stay at 1200 unless the profit margin for XPs decreases by at least $33\n",
"\n",
"- Allowable Increase/Decrease: it indicates how much the objective coefficient could change before the optimal solution would change. For example:\n",
" - if the selling price of Basics stays within a range from $220 to $327.5, the optimal product mix does not change at all.\n",
"\n",
"**Constraints**\n",
"\n",
"| Cell | Name | Final Value | Shadow Price | Constraint R.H. Side | Allowable Increase | Allowable Decrease |\n",
"| ----------- | ---- | ----- | ------- | ----------- | --------- | -------- |\n",
"|$B$21 | Labor availability for assembling Hours used | 10000 | 16\t| 10000 | 200 | 2800 |\n",
"|$B$22 | Labor availability for testing Hours used\t | 2960 | 0\t| 3000 | 1E+30 |\t40 |\n",
"\n",
"- Final Value: the value of the left side of the constraint at the optimal solution\n",
"\n",
"- Shadow Price: it indicates the change in the optimal value of the objective when the right side of some constraint changes by one unit. For example:\n",
"\n",
" - If the right side of this constraint increases by one hour, from 10000 to 10001, the optimal value of the objective will increase by $16."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## SAS `proc optmodel`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In practice, users do not need to interact with solver directly. SAS, as well as many other software package, offers modeling language that allows the user to formulate the problem in algebraic model.\n",
"\n",
"To try SAS optimization package, we can log into `SAS on Demand` cloud service through following procedures\n",
"\n",
"1. Go to the [link](https://odamid.oda.sas.com/) and click \"Not registered or cannot sign in?\"\n",
"\n",
"2. Click \"Don't have a SAS Profile?\"\n",
"\n",
"3. Register a SAS account and login\n",
"\n",
"4. Select enrollment tab and click \"+ enroll in a course\"\n",
"\n",
"5. The course code is available by clicking \"show answer\""
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
" show answer\n",
" "
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hide_answer()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The course code is: **d66f5458-24ac-44b3-8733-13f3ec9f3822**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Comparing to spreadsheet modeling, modeling language has a huge advantage because it can separate modeling and solution reporting from data management.\n",
"\n",
"**Datasets for a simple product mix problem**\n",
"\n",
"```sas\n",
"data ds_assemble;\n",
"\tinput type $ cost avail;\n",
"\tdatalines;\n",
"assemble 11 10000\n",
";\n",
"run;\n",
"\n",
"data ds_test;\n",
"\tinput type $ cost avail;\n",
"\tdatalines;\n",
"test 15 3000\n",
";\n",
"run;\n",
"\n",
"data ds_model;\n",
"\tinput model $ assemble test cost price max_sale;\n",
"\tdatalines;\n",
"Basic 5 1 150 300 600\n",
"XP 6 2 225 450 1200\n",
";\n",
"run;\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Datasets for a larger product mix problem**\n",
"\n",
"```sas\n",
"data ds_assemble;\n",
"\tinput type $ cost avail;\n",
"\tdatalines;\n",
"assemble 11 20000\n",
";\n",
"run;\n",
"\n",
"data ds_test;\n",
"\tinput type $ cost avail;\n",
"\tdatalines;\n",
"test1 19 5000\n",
"test2 17 6000\n",
";\n",
"run;\n",
"\n",
"data ds_model;\n",
"\tinput model $ assemble test1 test2 cost price max_sale;\n",
"\tdatalines;\n",
"Model1 4 1.5 2 150 350 1500\n",
"Model2 5 2 2.5 225 450 1250\n",
"Model3 5 2 2.5 225 460 1250\n",
"Model4 5 2 2.5 225 470 1250\n",
"Model5 5.5 2.5 3 250 500 1000\n",
"Model6 5.5 2.5 3 250 525 1000\n",
"Model7 5.5 2.5 3.5 250 530 1000\n",
"Model8 6 3 3.5 300 600 800\n",
";\n",
"run;\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The modeling code is quite general and can solve any product mix problem with given data structure.\n",
"\n",
"```sas\n",
"proc optmodel;\n",
"/*read in data to set and arrays */\n",
"\tset ASSEMBLE_LINES;\n",
"\tnum assemble_cost{ASSEMBLE_LINES}, assemble_avail{ASSEMBLE_LINES};\n",
"\tread data ds_assemble into ASSEMBLE_LINES=[type] assemble_cost=cost assemble_avail=avail;\n",
"\t\n",
"\tset TEST_LINES;\n",
"\tnum test_cost{TEST_LINES}, test_avail{TEST_LINES};\n",
"\tread data ds_test into TEST_LINES=[type] test_cost=cost test_avail=avail;\n",
"\t\n",
"\tset LABORS = ASSEMBLE_LINES union TEST_LINES;\n",
"\t\n",
"\tset MODELS;\n",
"\tnum price{MODELS}, hours{MODELS,LABORS} , cost{MODELS}, max_sale{MODELS};\n",
"\tread data ds_model into MODELS=[model] {l in LABORS} cost price max_sale;\n",
"\t\n",
"\tnum margin{m in MODELS, t in TEST_LINES} \n",
"\t\t= price[m] - cost[m] - sum{a in ASSEMBLE_LINES} assemble_cost[a]*hours[m,a] - test_cost[t]*hours[m,t];\n",
"\n",
"/* *********** * * * * * * *********** */\t\n",
"/* *********** build model *********** */\n",
"/* *********** * * * * * * *********** */\n",
"\n",
"\tvar Produce{m in MODELS, t in TEST_LINES} >=0; \n",
"\t\t/* production for each model in each testing line */\n",
"\t\t\n",
"\timpvar Production_of_Model{m in MODELS} = sum{t in TEST_LINES} Produce[m,t];\n",
" /* implied variable: production for each model */\n",
"\n",
"\tcon Maximal_Sales{m in MODELS}:\n",
"\t\tProduction_of_Model[m] <= max_sale[m];\n",
"\t\t/* total production for each model in all testing lines */\n",
"\n",
"\tcon Avail_Assemble{a in ASSEMBLE_LINES}:\n",
"\t\tsum{m in MODELS} hours[m,a]*Production_of_Model[m] <= assemble_avail[a];\n",
"\t\t\n",
"\tcon Avail_Test{t in TEST_LINES}:\n",
"\t\tsum{m in MODELS} hours[m,t]*Produce[m,t] <= test_avail[t];\n",
"\t\t\t\n",
"\tmax Profit=sum{m in MODELS, t in TEST_LINES} margin[m,t] * Produce[m,t];\n",
"\n",
"\tsolve;\n",
"\t\n",
"\tcreate data solution from [t]=TEST_LINES {m in MODELS}