ch 12: linear optimization models

notes from ch 12 slides/ lecture videos

optimization problems:

• can be used to support and improve managerial decision making

• maximize or minimize some function, called objection function, and have a set of restrictions known as constraints

• can be linear or nonlinear

typical applications:

• a manufacturer want to develop a production schedule and an inventory policy that will satisfy demand in future periods and at the same time minimize the total production and inventory costs. in this case, the constraint is demand and objective function is to minimize the total production and inventory costs

• a financial analyst would like to establish an investment portfolio from a variety of stock and bond investment alternatives that maximizes the return on investment. in this case, the the objective function is to maximize return and constraint is subjective

• a marketing manager wants to determine how best to allocate a fixed advertising budget among alternatives advertising media such as web, radio, television, newspaper, and magazine that maximizes advertising effectiveness.,

• a company had warehouses in a number of locations. given specific customer demands, the company would like to determine how much each warehouse should ship to each customer so that total transportation costs are minimized

linear optimization models are also known as? why?

linear programs. its called linear program because the objective functions are linear. meaning that the power of x, independent variable, and y is 1. the power of variables for constraints is also 1.

linear programming:

• a problem-solving approach developed to help managers make better decisions

• numerous applications in todays competitive business environment

  • GE capital uses linear programming to help determine optimal lease structering

  • marathon oil company uses linear programming for gasoline blending and to evaluate the economies of a new terminal or pipeline

problem formulation or modeling:

process of translating the verbal statement of a problem into a mathematical statement (or model)

general guidelines for problem formulation?

1. understand the problem thoroughly

2. describe the objective

3. describe each constraint

4. define the decision variables

5. write the objective in terms of the decision variables

6. write the constraints in terms of the decision variables

example of constraints:

• number of hours of cutting and dyeing time used must be less than. two hours of cutting and dyeing time available

• number of hours of sewing time used must be less than or equal to the number of sewing time available

• number of hours finishing time must be less than or equal to the number of hours finishing time available

• number of hours of inspections and packaging time used must be less than or equal to the number of hours of inspection and packaging time available

non-negativity constraints:

based on the fact that the number of services/products produced cannot be negative

mathematical model:

a set of mathematical relationships

its a linear programming model (or linear program) when?

the objective function and all constraint functions are linear functions of decision variables

linear function:

mathematical function in which each variable appears in a separate term and is raised to the first power

to find the optimal solution to the problem modeled as a linear program:

• the optimal solution must have the highest objective function value

• the optimal solution must be a feasible solution — a setting of the decision variables that satisfies all of the constraints of the problem

• search over the feasible region — a set of all the possible solutions

• find the solution that gives the best objective function value

feasible solution:

a setting of the decision variable that satisfies all of the constraints of the problem

feasible solution:

a set of all the possible solutions

extreme points:

found where constraints intersect on the boundary of the feasible region

to solve a linear optimization problem:

only have to search the extreme points of the feasible region to find the optimal solution

solving linear programs with excel solver:

• the first step is to construct the relevant what-if model

• a what-if model for optimization allows the user to try different values of the decision variables and see:

  • whether the trial solution is feasible

  • the value of the objective function for that trial solution

• convey the excel solver the structure of the linear optimization model

binding constraint:

one that holds as an equality at the optimal solution

slack value

for each less-than-or-equal-to constraint indicates the difference betweenn the left-hand and right-hand values for a constraint

by adding a non-negative slack variable:

we can make the constraint equality

alternative optimal solutions:

• where the optimal objective function contour line coincides with one of the binding constraint lines on the boundary of the feasible region

• in these solutions, more than one solution provides the optimal value for the objective function

infeasibility:

• means no solution to the linear programming problem

  • no points satisfy all the constraints and the non-negativity conditions simultaneously

• graphically, a feasible region does not exist

• infeasibility occurs because:

  • managements expectations are too high

  • too many restrictions have been placed on the problem

an infeasible problem when solved with excel solver:

• will return a message indicating that no feasible solution exists — indicating no solution to the linear programming problem will satisfy all constraints

• careful inspection is necessary to identify why the problem is feasible

• one of the approaches is to drop one or more constraints and re-solve the problem

• if we find an optimal solution for this revised problem, then the constraint(s) that ar omitted with the others, are causing the problem to be infeasible

unbounded:

• the situation is which the value of the solution

  • may be made infinitely large — for a maximization linear programming

  • may be made infinitely small — for a minimization linear programming

  • without violating any of the constraints

solving an unbounded problem using excel solver:

returns a message “objective cell values do not converge”

in linear programming models of real problems:

the occurrence of an unbounded solution means that the problem has been improperly formulated

general linear programming notation advantage & disadvantage

advantage: formulating a mathematical model for a problem that involves a large number of decision variables is much easier

disadvantage: not being able to easily identify what the decision variables actually represent in the mathematical model

classical sensitivity analysis:

• based on the assumption that only one piece of input data has changed

• it is assumed that all other parameters remain as stated in the original problem

when interested in what would happen if two or more pieces of input data are changed simultaneously:

the easiest way to examine the effect of simultaneous changes is to make the changes and rerun the model

sensitivity analysis:

the study of how the changes in the input parameters of an optimization model affect the optimal solution

sensitivity analysis helps in answering the questions:

• how will a change in a coefficient of the objective function affect the optimal solution?

• how will a change in the right-hand-side value for a constraint affect the optimal solution?

shadow price:

shadow price for a constraint is the change in the optimal objective function value if the right-hand side of the constraint is increased by one

the sign of a shadow price depends on:

whether the problem is a maximization or minimization type and the type of constraint under consideration

when observing the shadow prices, the following general principle holds:

• making a binding constraint more restrictive (tightening the constraint) degrades or leaves unchanged the optimal objective function

• making a binding constraint less restrictive (relaxing or loosening the constraint) improves or leaves unchanged the optimal objective function

the allowable increase and the allowable decrease are:

the allowable changes in the right-hand side for which the current shadow price remain valid

constraints section:

• first column — gives the cell location of the left-hand side of the constraint

• second column — constraint name

• third column — value of the left-hand side of the constraint of optimality

• fourth column — gives the shadow price for each constraint