agbus 435 lec9 f04

Integer Programming: 

Integer Programming Chapter 9: Hillier and Hillier

Agenda: 

Agenda Motivating Case Study: TBA Airlines Discuss Integer Programming Problems Case Study: California Manufacturing Company Wyndor Case Revisited Variation of Wyndor’s Problem

Motivating Case Study: TBA Airlines: 

Motivating Case Study: TBA Airlines TBA Airlines is a small regional company that uses small planes for short flights. The company is considering expanding its operations. TBA has two choices: Buy more small planes (SP) and continue with short flights Buy only large planes (LP) and only expand into larger markets with longer flights Expand by purchasing some small and some large planes

TBA Airlines Cont.: 

TBA Airlines Cont. Question: How many large and small planes should be purchased to maximize total net annual profit?

Case Study: TBA Airlines: 

Case Study: TBA Airlines

Mathematical Model for TBA: 

Mathematical Model for TBA

Graphical Method for Linear Programming: 

Graphical Method for Linear Programming

Divisibility Assumption of LP: 

Divisibility Assumption of LP This assumption says that the decision variables in a LP model are allowed to have any values that satisfy the functional and nonnegativity constraints. This implies that the decision variables are not restricted to integer values. Note: Implicitly in TBA’s problem, it cannot purchase a fraction of a plane which implies this assumption is not met.

New Mathematical Model for TBA: 

New Mathematical Model for TBA

The Graphical Solution Method For Integer Programming: 

The Graphical Solution Method For Integer Programming Step 1: Graph the feasible region Step 2: Determine the slope of the objective function line Step 3: Moving the objective function line through this feasible region in the direction of improving values of the objective function. Step 4: Stop at the last instant the the objective function line passes through an integer point that lies within this feasible region. This integer point is the optimal solution.

Graphical Method for Integer Programming: 

Graphical Method for Integer Programming

Types of Integer Programming Problems: 

Types of Integer Programming Problems Pure Integer Programming (PIP) These problems are those where all the decision variables must be integers. Mixed Integer Programming (MIP) These problems only require some of the variables to have integer values.

Types of Integer Programming Problems Cont.: 

Types of Integer Programming Problems Cont. Binary Integer Programming (BIP) These problems are those where all the decision variables restricted to integer values are further restricted to be binary variables. A binary variable are variables whose only possible values are 0 and 1. BIP problems can be separated into either pure BIP problems or mixed BIP problems.

Applications of Binary Variables: 

Applications of Binary Variables Binary variables only allow two choices This makes them suited for problems that are characterized by variables that can take on only two possibilities. Examples: Do a project or not do a project? To hire or not to hire? To build or not to build? To Sell or not to sell?

Case Study: California Manufacturing Company (CMC): 

Case Study: California Manufacturing Company (CMC) The California Manufacturing Company is a company with factories and warehouses throughout California. It is currently considering whether to build a new factory in Los Angeles and/or San Francisco. Management is also considering building one new warehouse where a new factory has been recently built. Should the CMC build factories and/or warehouses in Los Angeles and/or San Francisco?

Case Study: CMC Cont.: 

Case Study: CMC Cont.

Case Study: CMC Cont.: 

Case Study: CMC Cont. FLA, FSF, WLA,WSF are all binary variables which take on the value of 1 if the specific item is done and zero if it is not done. We also need to make sure that at most one warehouse is built and it is built where a factory is built.

Mathematical Model for CMC: 

Mathematical Model for CMC

Wyndor Case Revisited: 

Wyndor Case Revisited Two new products have been developed: An 8-foot glass door A 4x6 foot glass window Wyndor has three production plants Production of the door utilizes Plants 1 and 3 Production of the window utilizes Plants 2 and 3 Objective is to find the optimal mix of these two new products.

Wyndor Case Revisited Cont.: 

Wyndor Case Revisited Cont.

Wyndor Case Revisited Cont.: 

Wyndor Case Revisited Cont.

Changing Wyndor to Account for Setup Costs: 

Changing Wyndor to Account for Setup Costs Suppose that two changes are made to the original Wyndor problem: If Wyndor chooses to produce doors, it must pay a one time set-up cost of $700, while if Wyndor produces windows it must pay a set-up cost of $1,300. We want to restrict the doors and windows to be integer values.

Graphical Solution to Original Wyndor Problem: 

Graphical Solution to Original Wyndor Problem

Feasible Solutions for Wyndor with Setup Costs: 

Feasible Solutions for Wyndor with Setup Costs

Wyndor’s Mathematical Model With Set-Up Costs: 

Wyndor’s Mathematical Model With Set-Up Costs

Changing Wyndor to Account for Mutually Exclusive Products: 

Changing Wyndor to Account for Mutually Exclusive Products Suppose Wyndor decides that it only wants to produce doors or windows rather than both. This implies that either doors have to be zero or windows have to be zero.

Wyndor’s Mathematical Model With Mutually Exclusive Products: 

Wyndor’s Mathematical Model With Mutually Exclusive Products

Changing Wyndor to Account for Either-Or Constraints: 

Changing Wyndor to Account for Either-Or Constraints Suppose the company is trying to decide whether to build a new up-to-date plant that will be used to replace plant 3. This implies that Wyndor wants to examine the profitably of using plant 4 versus plant 3.

Wyndor’s Data with Either/Or Constraint: 

Wyndor’s Data with Either/Or Constraint

Graphical Solution with Plant 3 or Plant 4: 

Graphical Solution with Plant 3 or Plant 4

Wyndor’s Mathematical Model With Either/Or Constraint: 

Wyndor’s Mathematical Model With Either/Or Constraint

The Challenges of Rounding: 

The Challenges of Rounding It may be tempting to round a solution from a non-integer problem, rather than modeling for the integer value. There are three main issues that can arise: Rounded Solution may not be feasible. Rounded solution may not be close to optimal. There can be many rounded solutions