Management Decision Tools

Seminar 3: Applications of Linear Programming

Imron Rosyadi

Today’s Mission

We’ll explore how Linear Programming (LP) helps make critical decisions in different areas of a business.

• Marketing: How to design a cost-effective survey.
• Finance: How to invest millions for maximum return.
• Operations: How to schedule a workforce to meet production goals.

Today, we move from the “how” of LP to the “why.” We’ll see that the same structured thinking—defining variables, an objective, and constraints—can be applied to solve very different kinds of business puzzles.

Marketing Application: MSI Research

The Scenario: Market Survey Inc. (MSI) needs to conduct 1000 door-to-door interviews for a new product. They want to do it as cheaply as possible, but they have a lot of rules to follow.

The Puzzle: How do you plan the interviews to meet all the requirements at the minimum cost? This is a classic resource allocation problem perfect for LP.

Think of this like planning a big event on a tight budget. You have to invite specific groups of people (the constraints) and want to spend as little as possible (the objective).

MSI: Breaking Down the Problem

First, let’s identify the core components of our LP model.

1. Decisions (Variables) We need to decide how many interviews to conduct in each category.

• \(DC\): Daytime, with Children
• \(EC\): Evening, with Children
• \(DNC\): Daytime, No Children
• \(ENC\): Evening, No Children

2. Objective (The Goal) Minimize the total survey cost.

Interview Type	Cost
Daytime, with Children	$20
Evening, with Children	$25
Daytime, No Children	$18
Evening, No Children	$20

Minimize Cost: 20DC + 25EC + 18DNC + 20ENC

MSI: The Rules (Constraints)

These are the rules MSI must follow, translated into math.

Rule in Plain English	Mathematical Constraint
1. Conduct exactly 1000 interviews in total.	\(DC+EC+DNC+ENC = 1000\)
2. At least 400 households with children.	\(DC+EC \geq 400\)
3. At least 400 households without children.	\(DNC+ENC \geq 400\)
4. Evening interviews must be \(\geq\) daytime.	\(EC+ENC \geq DC+DNC\)
5. \(\geq 40\%\) of “with children” interviews in evening.	\(EC \geq 0.4(DC+EC)\)
6. \(\geq 60\%\) of “no children” interviews in evening.	\(ENC \geq 0.6(DNC+ENC)\)

Each rule becomes a line in our LP model. Notice how we rearrange some constraints (like #4, #5, #6) to have all the variables on one side (-DC + EC - DNC + ENC >= 0) before putting them into a solver.

MSI: The Optimal Solution

After running this model through a solver, we get the cheapest plan.

Optimal Interview Plan:

Variable	Description	Number of Interviews
DC	Daytime, with Children	240
EC	Evening, with Children	160
DNC	Daytime, No Children	240
ENC	Evening, No Children	360

Minimum Total Cost: $20,320

You can verify the cost with this simple calculator:

Financial Application: Winslow Portfolio

The Scenario: Winslow Savings has $20 million to invest over the next 4 months. They want to maximize their interest earnings.

The Puzzle: How should they allocate their money each month between different investment options to get the highest return, while making sure they have enough cash for a big project later? This is a multi-period planning problem.

Think of this like a 4-level video game. In each level (month), you invest resources. Your earnings from one level carry over to the next. You need a strategy to maximize your score (interest) while making sure you have enough power-ups ($10M) for the final boss fight (the building venture).

Winslow: Variables and Objective

This model is dynamic, so our variables need to track investments in each month i (where i=1, 2, 3, 4).

• \(G_i\): New investment in Government bonds in month i. (2% return over 2 months)
• \(C_i\): New investment in Construction loans in month i. (6% return over 3 months)
• \(L_i\): Liquid funds invested locally in month i. (0.75% return per month)

Objective: Maximize Total Interest \[ \text{Max } 0.02(G_1+...+G_4) + 0.06(C_1+...+C_4) + 0.0075(L_1+...+L_4) \]

Winslow: Cash Flow Constraints

This is the tricky part. The money available to invest each month depends on what investments from previous months have matured.

• Month 1: Start with $20M.

\(G_1 + C_1 + L_1 = 20,000,000\)

• Month 2: Money available is the cash (\(L_1\)) from Month 1 plus its interest.

\(G_2 + C_2 + L_2 = 1.0075 L_1\)

• Month 3: Money comes from bonds from Month 1 (\(G_1\)) and cash from Month 2 (\(L_2\)) maturing.

\(G_3 + C_3 + L_3 = 1.02 G_1 + 1.0075 L_2\)

• Month 4: Money from loans from M1 (\(C_1\)), bonds from M2 (\(G_2\)), and cash from M3 (\(L_3\)).

\(G_4 + C_4 + L_4 = 1.06 C_1 + 1.02 G_2 + 1.0075 L_3\)

Winslow: Other Constraints & Solution

There are a few more critical rules to follow.

Constraint	Explanation
\(1.06C_2 + 1.02G_3 + 1.0075L_4 \ge 10,000,000\)	Must have 10M cash available at start of Month 5.
\(G_1+G_2 \le 8,000,000\), etc.	Total Gov’t bonds held at any time must not exceed 8M.
\(C_1+C_2+C_3 \le 8,000,000\), etc.	Total Const. loans held at any time must not exceed 8M.

The Optimal Solution: The solver provides a detailed month-by-month investment plan that results in a maximum interest of $1,429,214.

The full solution table is complex, but the key takeaway is that LP can map out this entire 4-month strategy, balancing risk (investment limits) and reward (interest) to meet all of the bank’s goals perfectly.

Operations Application: NWC Workforce

The Scenario: National Wing Company (NWC) has a contract to produce a specific number of airplane wings each month for three months. They need to manage their workforce to meet these targets.

The Puzzle: How can NWC hire, train, and assign workers each month to meet the production schedule at the minimum possible payroll cost?

This is like managing a sports team for a championship run. You have veterans (producers), rookies (apprentices), and prospects (recruits). Some veterans need to step back from playing to coach (trainers). You need to find the right mix each month to win all your games (meet production targets) while staying under the salary cap (minimizing cost).

NWC: The Workforce Flow

A key part of this problem is understanding how the workforce changes over time. A new recruit isn’t immediately productive.

graph TD
    subgraph Month 1 - April
        R1(Recruits)
        T1(Trainers)
    end
    subgraph Month 2 - May
        A2(Apprentices)
        R2(Recruits)
        T2(Trainers)
    end
    subgraph Month 3 - June
        A3(Apprentices)
        QW3(Qualified Workers)
    end
  
    R1 -- 1 month training --> A2
    A2 -- 1 month experience --> QW3
    T1 -- Train --> R1
    T2 -- Train --> R2

• A Recruit needs one month of training to become an Apprentice.
• An Apprentice needs one more month to become a fully Qualified Worker.

NWC: Variables and Objective

Let’s define our decision variables and goal for April (i=1), May (i=2), and June (i=3).

• \(P_i\): Number of Producers in month i
• \(T_i\): Number of Trainers in month i
• \(A_i\): Number of Apprentices in month i
• \(R_i\): Number of Recruits in month i

Objective: Minimize Total Wage Cost \[ \text{Min } 3000P_1 + 3300T_1 + ... + 3000P_3 + 2600A_3 \]

NWC: Key Constraints

This model links months together.

• Production Targets: The number of wings produced each month must meet the contract. \(0.6P_1 + 0.3T_1 + 0.05R_1 \ge 20\) (April’s production)

• Workforce Balance: The number of qualified workers flows from one month to the next. \(P_2 + T_2 = P_1 + T_1\) (Qualified workers don’t disappear) \(A_2 = R_1\) (April’s recruits become May’s apprentices)

• Training Capacity: Each trainer can handle two recruits. \(2T_1 \ge R_1\)

• Boundary Conditions: Start with 100 workers, end with at least 140. \(P_1 + T_1 = 100\) \(P_3 + A_3 \ge 140\)

NWC: The Optimal Workforce Plan

The LP solver gives NWC a detailed, cost-effective staffing plan for the entire quarter.

Optimal Plan Summary:

Employee Type	April	May	June
Producers	100	80	100
Trainers	0	20	0
Apprentices	0	0	40
Recruits	0	40	0

Minimum Total Wage Cost: $1,098,000

Insight: The model shows it’s cheapest to start with everyone producing. Then, in May, some producers switch to being trainers to hire and train 40 new recruits, who become apprentices in June, helping to meet the final production targets and the goal of having 140 workers by July.