Operations Management chap 5, 6, 7, 8, 11, 16

Overview of Integer Programming

1. Introduction to Integer Programming (IP)

• Integer programming is a mathematical optimization technique where some or all decision variables are constrained to be integers.

2. Topics Covered in Chapter 5

• Integer Programming (IP) Models

• Integer Programming Graphical Solution

• Computer Solution of Integer Programming Problems With Excel

• 0-1 Integer Programming Modeling Examples

Types of Integer Programming Models

1. Total Integer Model

• All decision variables must have integer solution values.

2. 0-1 Integer Model

• All decision variables required to take binary values, either 0 or 1.

3. Mixed Integer Model

• Some decision variables are required to have integer values, while others may take continuous values.

A Total Integer Model Example

1. Problem Statement

• 
  

• Scenario: The owner of a machine shop plans to expand by purchasing presses and lathes.

• 
  

• Profit Contribution:

  • Each press purchased increases profit by $100 daily.

  • Each lathe increases profit by $150 daily.

• 
  

• Constraints:

  • Budget: $40,000 for machine purchases.

  • Floor Space: 200 square feet available.

• 
  

• Machine Details:
  

  Machine Type	Required Floor Space (ft²)	Purchase Price ($)
  Press	15	8,000
  Lathe	30	4,000
  2. Model Construction

  1. Decision Variables

  • Let:

    • x_1 = number of presses

    • x_2 = number of lathes

  2. Objective Function

  • Maximize Z = 100x1 + 150x2

  3. Constraints

  • Budget constraint:
    8000x1 + 4000x2 \leq 40000

  • Space constraint:
    15x1 + 30x2 \leq 200

  • Non-negativity and integer constraints:
    x1, x2 \geq 0 and integer

  3. Model Summary

  • Maximize:
    Z = 100x1 + 150x2

  • Subject to:

    1. 8000x1 + 4000x2 \leq 40000

    2. 15x1 + 30x2 \leq 200

    3. x1, x2 \geq 0 and integer

  Integer Programming Graphical Solution

  1. Maximization IP Problem

  • Rounding non-integer solution values can lead to:

    • Infeasible solutions if rounded up.

    • Less than optimal solutions if rounded down.

  Example of Integer Programming Graphical Solution

  1. Problem Representation

  • Maximize:
    Z = 100x1 + 150x2

  • Subject to:

    1. 8000x1 + 4000x2 \leq 40000

    2. 15x1 + 30x2 \leq 200

    3. x1, x2 \geq 0 and integer

  • Optimal Solution:

    • In Linear Programming (LP), Z = 1055.56 with (2.22, 5.55)

    • In Integer Programming (IP), Z = 1000 with (1, 6)

  Computer Solution in LP

  1. Excel Setup for LP

  • Excel parameters include:

    • Profit per machine, resource constraints, total purchases.

    • Example output shows:

    • Presses: 2.22

    • Lathes: 5.56

    • Total Profit: $1055.56

  Branch and Bound Method

  1. Overview

  • A traditional approach to solving integer programming problems.

  • It involves partitioning feasible solutions into smaller subsets, evaluating until the best solution is found.

  • Known to be tedious and complex mathematically.

  Example of 0-1 Integer Model

  1. Problem Scenario

  • 
    

  • Community council is deciding on construction of recreation facilities under budget and land constraints.

  • 
    

  • Proposed facilities:
    

    Facility	Expected Usage (people/day)	Cost ($)	Land (acres)
    Swimming Pool	300	35,000	4
    Tennis Center	90	10,000	2
    Athletic Field	400	25,000	7
    2. Decision Variables for 0-1 Model

    • Let:

      • x_1 = Swimming Pool

      • x_2 = Tennis Center

      • x_3 = Athletic Field

      • x_4 = Gymnasium

    • Objective Function: Maximize
      Z = 300x1 + 90x2 + 400x3 + 150x4

    3. Constraints

    1. Budget constraint:
       35000x1 + 10000x2 + 25000x3 + 90000x4 \leq 120000

    2. Land use constraint:
       4x1 + 2x2 + 7x3 + 3x4 \leq 12

    3. One facility limit constraint:
       x1 + x2 \leq 1

    4. Decision variable constraints:
       x1, x2, x3, x4 = 0 ext{ or } 1

    4. Example Summary of 0-1 Model

    • Maximize Z:
      Z = 300x1 + 90x2 + 400x3 + 150x4

    • Subject to the constraints mentioned above.

    Mixed Integer Model Example

    1. Problem Statement

    • Nancy Smith's investment scenario involving condominiums, land, and municipal bonds with specific profits and costs.

    • Constraints include a total investment limit of $250,000 and limits on the number of each type of investment available.

    2. Model Construction

    1. Decision Variables

    • Let:

      • x_1 = condominiums

      • x_2 = acres of land

      • x_3 = bonds

    2. Objective Function

    • Maximize Z = 9000x1 + 1500x2 + 1000x_3

    3. Constraints

    • Budget:
      50000x1 + 12000x2 + 8000x_3 \leq 250000

    • Availability:
      x1 \leq 4 x2 \leq 15
      x_3 \leq 20

    • Decision variables constraints:
      x2 \geq 0 and x1, x_3 \geq 0 and integer

    4. Example Summary

    • Maximize Z:
      Z = 9000x1 + 1500x2 + 1000x_3

    • Subject to mentioned budget and availability constraints.