Scribd Logo
Upload

Welcome to Scribd!

  • 88 views

    Assignment 2

    Uploaded by

    Rohith Duvasi
    This document contains exercises related to optimization and decision models. It includes: 1) A linear programming problem to minimize production and transportation costs for an electric motor company with multiple plants and customers. 2) Examples of finding the dual of linear programs using both the indirect and direct methods. 3) A proof that the definition of finding the dual of a linear program is symmetric. 4) Formulating 1-norm and infinity-norm regression problems as linear programs using graduate admissions data.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Assignment 2

    Uploaded by

    Rohith Duvasi
    88 views5 pages
    This document contains exercises related to optimization and decision models. It includes: 1) A linear programming problem to minimize production and transportation costs for an electric motor company with multiple plants and customers. 2) Examples of finding the dual of linear programs using both the indirect and direct methods. 3) A proof that the definition of finding the dual of a linear program is symmetric. 4) Formulating 1-norm and infinity-norm regression problems as linear programs using graduate admissions data.

    Original Title

    Assignment 2 (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains exercises related to optimization and decision models. It includes: 1) A linear programming problem to minimize production and transportation costs for an electric motor company with multiple plants and customers. 2) Examples of finding the dual of linear programs using both the indirect and direct methods. 3) A proof that the definition of finding the dual of a linear program is symmetric. 4) Formulating 1-norm and infinity-norm regression problems as linear programs using graduate admissions data.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    88 views5 pages

    Assignment 2

    Uploaded by

    Rohith Duvasi
    This document contains exercises related to optimization and decision models. It includes: 1) A linear programming problem to minimize production and transportation costs for an electric motor company with multiple plants and customers. 2) Examples of finding the dual of linear programs using both the indirect and direct methods. 3) A proof that the definition of finding the dual of a linear program is symmetric. 4) Formulating 1-norm and infinity-norm regression problems as linear programs using graduate admissions data.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 5

    MSc Business Analytics 2019/20

    Optimisation and Decision Models


    Wolfram Wiesemann

    Exercises 2

    (1) In-Class: Johnson Electric has three different plants, each of which produces electric motors
    for four different clients. The unit production costs and capacities for each plant are as follows.


    Plant Production costs Monthly capacity


    (£/motor) (# of motors)

    Aberdeen 17 800

    Birmingham 20 600

    Cardiff 24 700
    

    For the next months, the clients have submitted the following orders:


    Customer

    Onyx Inc. Treble Co. Hilton Appliances Dean Electric

    Demand 300 500 400 600


    

    The unit transportation costs (£/motor) to each of the clients is shown in the following table:


    Customer

    Plant Onyx Inc. Treble Co. Hilton Appliances Dean Electric

    Aberdeen 3 2 5 7

    Birmingham 6 4 8 3

    Cardiff 9 1 5 4
    

    Johnson Electric must decide how many motors to produce in each plant, as well as how much
    of each customer’s demand to supply from each plant, so as to minimise the overall costs (that
    is, the sum of production and transportation costs).


    (a) Construct a linear program that determines the production and distribution plans that
    minimise the overall costs.

    

    Hint: Introduce one decision variable for each plant-customer pair, such as AO for
    Aberdeen-Onyx or CT for Cardiff-Treble. The decision variable AO should determine
    how many motors Johnson Electric produces in Aberdeen that are to be shipped to
    Onyx Inc. You will then require constraints for the capacity of each plant as well as for
    the demand of each customer.

    (b) Solve the linear program using AMPL. What managerial actions would you recommend
    based on the optimal solution and the shadow price information?
    (2) In-Class: Dualising linear programs.

    (a) Using the “indirect method”, find the dual to the linear program:

    minimise 3 x1 + 5 x2 - x3
    subject to x1 + x3 = 4
    x2 - 2 x3 ≤ 2
    x1, x2 ≥ 0, x3 unrestricted

    (b) Using the “direct method”, find the dual to the linear program:

    maximise x1 - x3
    subject to x1 + x2 = 4
    x3 ≤ 2
    x1, x2 ≤ 0, x3 unrestricted
    (3) Homework: In class we have defi ned that the dual of the linear program

    

    maximise cTx

    subject to Ax ≤ b

    x ≥ 0

    

    is

    

    minimise bTy

    subject to ATy ≥ c

    y ≥ 0

    

    Show that this definition is symmetric, that is, the dual of the linear program

    

    minimise bTy

    subject to ATy ≥ c

    y ≥ 0

    

    is

    

    maximise cTx

    subject to Ax ≤ b

    x ≥ 0

    

    Hint: Bring the dual problem into the form of the primal problem (that is, change the
    objective into a maximisation and change the constraints), use the above definition to
    determine the dual of the resulting problem, and finally show that this dual is actually
    equivalent to the primal problem.
    (4) Homework: The Graduate Admissions dataset from Kaggle (https://www.kaggle.com/
    mohansacharya/graduate-admissions) has the independent variables

    

    GRE: GRE Scores (out of 340)

    TOEFL: TOEFL Scores (out of 120)

    Univ: University Rating (out of 5)

    SOP: Statement of Purpose Strength (out


    of 5)

    LOR: Letter of Recommendation Strength


    (out of 5)

    CGPA: Undergraduate GPA (out of 10)

    Res: Research Experience (either 0 or 1)

    

    as well as the dependent variable

    

    Chance: Chance of Admission (ranging from 0 to 1)

    (a) Formulate the 1-norm regression problem for this data set (with Chance as the dependent
    variable and GRE, TOEFL, …, Res as independent variables) as a linear program. You can
    “index” the data by writing “GRE”, “TOEFLi” etc. in your model.

    

    (Please also include an intercept in your regression problem!)

    (b) Construct an AMPL file that solves the 1-norm regression problem. To this end, you can use the
    Graduate_Admissions.dat file in the exercises folder (which only involves the first 100 records,
    to comply with the size limitations of the AMPL demo version) and import the data as follows:

    set NUM ordered; # candidate number

    param GRE {NUM}; # GRE Score


    param TOEFL {NUM}; # TOEFL Score
    param Univ {NUM}; # University Rating
    param SOP {NUM}; # Statement of Purpose Strength
    param LOR {NUM}; # Letter of Recommend. Strength
    param CGPA {NUM}; # Undergraduate GPA
    param Res {NUM}; # Research Experience
    param Chance {NUM}; # Chance of Admission

    data Graduate_Admissions.dat;

    In your model, you can access the i-th element of GRE via GRE[i]. Also, you can create

    variable vectors that are indexed by NUM (the candidate number) via

    var x {NUM};

    Similarly, the i-th component of x can be access via x[i]. You can sum over all elements of x via
    sum {i in NUM} x[i]

    Finally, you can create a set of constraints, one for each candidate NUM, via

    subject to constr {i in NUM}: ...

    You may want to consult the AMPL book (available online for free) for further information on

    sets and indexing.

    Solve the problem. Make sure you use CPLEX as a solver (“option solver ‘cplex’;”), as other 

    solvers have stricter size limitations in the demo version. What is your optimal objective value,

    and what are the regression coefficients?

    (c) Formulate the infinity-norm regression problem for this data set (again with Chance as the
    dependent variable and GRE, TOEFL, …, Res as independent variables — plus an intercept)
    as a linear program. You can “index” your data as in part (a). Justify why your model gives the
    correct solution (similar to our argumentation for the 1-norm problem in the lecture)!

    (d) Construct an AMPL file that solves the infinity-norm regression problem.

    Solve the problem. Make sure you use CPLEX as a solver (“option solver ‘cplex’;”).

    What is your optimal objective value, and what are the regression coefficients?

    You might also like