%run ../initscript.py
HTML("""
<div id="popup" style="padding-bottom:5px; display:none;">
    <div>Enter Password:</div>
    <input id="password" type="password"/>
    <button onclick="done()" style="border-radius: 12px;">Submit</button>
</div>
<button onclick="unlock()" style="border-radius: 12px;">Unclock</button>
<a href="#" onclick="code_toggle(this); return false;">show code</a>
""")

Enter Password:

Submit

Unclock show code

%run ./loadoptfuncs.py
%matplotlib inline
toggle()

show code

Introduction to Optimization

All optimization models have several common elements:

• 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.

• An objective function (objective, for short) to be optimized – minimized or maximized.

• Constraints that must be satisfied. They are usually physical, logical, or economic restrictions, depending on the nature of the problem.

  • In searching for the values of the decision variables that optimize the objective, only those values that satisfy all of the constraints are allowed.

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.

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.

Linear Programming

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.

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and/or linear inequality constraints.

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.

Problem Formulation

The LP problem formulation is illustrated through a product mix problem.

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.

For each model, it has required assembly, testing hours, cost, price and estimated maximal sales.

Business assumptions: - No computers are in inventory from the previous period (or no beginning inventory) - 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)

Business goal: the PC manufacturer wants to know - how many of each model it should produce - maximize its net profit

Business constraints: - resource constraints: available assembly and testing hours - market constraints: maximal sales

Algebraic Model

The PC manufacturer wants to

\begin{align*} \text{maximize} \quad \text{Profit} &= \text{Basic's unit margin} \times \text{Production of Basic} \\ & \qquad \qquad+ \text{XP's unit margin} \times \text{Production of XP} \end{align*}

subject to following constraints: \begin{align*} &\text{assembly hours:} & 5 \times \text{Production of Basic} + 6 \times \text{Production of XP} &\le 10000 \\ &\text{testing hours:} & \text{Production of Basic} + 2\times \text{Production of XP} &\le 3000 \\ &\text{maximal sales:} & \text{Production of Basic} &\le 600 \\ &\text{maximal sales:} & \text{Production of XP} &\le 1200 \\ \end{align*}

Intuitive constraints: \begin{align*} \text{Production of Basic} &\ge 0 \\ \text{Production of XP} &\ge 0 \\ \end{align*}

Graphical solution

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.

interact(prodmix_graph,
         zoom=widgets.Checkbox(value=False, description='Zoom In'));

We can modify objective coefficients in order to see how objective value changes in the feasible region.

interact(prodmix_obj,
         zoom=widgets.Checkbox(value=False, description='Zoom In', disabled=False),
         margin1=widgets.IntSlider(min=-30,max=150,step=10,value=80,description='Margin Basic:',
                                   style = {'description_width': 'initial'}),
         margin2=widgets.IntSlider(min=-30,max=150,step=10,value=129,description='Margin XP:',
                                  style = {'description_width': 'initial'}));

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.

Sensitivity Analysis

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

Variable Cells

Cell	Name	Final Value	Reduced Cost	Objective Coefficient	Allowable Increase	Allowable Decrease
$B$16	Number to produce Basic	560	0	80	27.5	80
$C$16	Number to produce XP	1200	33	129	1E+30	33

• Final Value: the optimal solution

• 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:

  • the number of XPs will stay at 1200 unless the profit margin for XPs decreases by at least $33

• Allowable Increase/Decrease: it indicates how much the objective coefficient could change before the optimal solution would change. For example:

  • if the selling price of Basics stays within a range from $220 to $327.5, the optimal product mix does not change at all.

Constraints

Cell	Name	Final Value	Shadow Price	Constraint R.H. Side	Allowable Increase	Allowable Decrease
$B$21	Labor availability for assembling Hours used	10000	16	10000	200	2800
$B$22	Labor availability for testing Hours used	2960	0	3000	1E+30	40

• Final Value: the value of the left side of the constraint at the optimal solution

• 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:

  • 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.

SAS proc optmodel

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.

To try SAS optimization package, we can log into SAS on Demand cloud service through following procedures

1. Go to the link and click “Not registered or cannot sign in?”

2. Click “Don’t have a SAS Profile?”

3. Register a SAS account and login

4. Select enrollment tab and click “+ enroll in a course”

5. The course code is available by clicking “show answer”

hide_answer()

show answer

The course code is: d66f5458-24ac-44b3-8733-13f3ec9f3822

Comparing to spreadsheet modeling, modeling language has a huge advantage because it can separate modeling and solution reporting from data management.

Datasets for a simple product mix problem

data ds_assemble;
    input type $ cost avail;
    datalines;
assemble 11 10000
;
run;

data ds_test;
    input type $ cost avail;
    datalines;
test 15 3000
;
run;

data ds_model;
    input model $ assemble test cost price max_sale;
    datalines;
Basic 5 1 150 300 600
XP 6 2 225 450 1200
;
run;

Datasets for a larger product mix problem

data ds_assemble;
    input type $ cost avail;
    datalines;
assemble 11 20000
;
run;

data ds_test;
    input type $ cost avail;
    datalines;
test1 19 5000
test2 17 6000
;
run;

data ds_model;
    input model $ assemble test1 test2 cost price max_sale;
    datalines;
Model1 4   1.5 2   150 350 1500
Model2 5   2   2.5 225 450 1250
Model3 5   2   2.5 225 460 1250
Model4 5   2   2.5 225 470 1250
Model5 5.5 2.5 3   250 500 1000
Model6 5.5 2.5 3   250 525 1000
Model7 5.5 2.5 3.5 250 530 1000
Model8 6   3   3.5 300 600 800
;
run;

The modeling code is quite general and can solve any product mix problem with given data structure.

proc optmodel;
/*read in data to set and arrays */
    set<str> ASSEMBLE_LINES;
    num assemble_cost{ASSEMBLE_LINES}, assemble_avail{ASSEMBLE_LINES};
    read data ds_assemble into ASSEMBLE_LINES=[type] assemble_cost=cost assemble_avail=avail;

    set<str> TEST_LINES;
    num test_cost{TEST_LINES}, test_avail{TEST_LINES};
    read data ds_test into TEST_LINES=[type] test_cost=cost test_avail=avail;

    set<str> LABORS = ASSEMBLE_LINES union TEST_LINES;

    set<str> MODELS;
    num price{MODELS}, hours{MODELS,LABORS} , cost{MODELS}, max_sale{MODELS};
    read data ds_model into MODELS=[model] {l in LABORS}<hours[model,l]=col(l)> cost price max_sale;

    num margin{m in MODELS, t in TEST_LINES}
        = price[m] - cost[m] - sum{a in ASSEMBLE_LINES} assemble_cost[a]*hours[m,a] - test_cost[t]*hours[m,t];

/* *********** * * * * * * *********** */
/* *********** build model *********** */
/* *********** * * * * * * *********** */

    var Produce{m in MODELS, t in TEST_LINES} >=0;
        /* production for each model in each testing line */

    impvar Production_of_Model{m in MODELS} = sum{t in TEST_LINES} Produce[m,t];
        /* implied variable: production for each model */

    con Maximal_Sales{m in MODELS}:
        Production_of_Model[m] <= max_sale[m];
        /* total production for each model in all testing lines */

    con Avail_Assemble{a in ASSEMBLE_LINES}:
        sum{m in MODELS} hours[m,a]*Production_of_Model[m] <= assemble_avail[a];

    con Avail_Test{t in TEST_LINES}:
        sum{m in MODELS} hours[m,t]*Produce[m,t] <= test_avail[t];

    max Profit=sum{m in MODELS, t in TEST_LINES} margin[m,t] * Produce[m,t];

    solve;

    create data solution from [t]=TEST_LINES {m in MODELS}<col(m)=Produce[m,t]>;
quit;