Math Problem Statement

A plumbing repair company has 3 employees and must choose which of 3 jobs to assign each to (each employee is assigned to exactly one job and each job must have someone assigned). Each employee can perform each job, but the cost to perform any given job can vary. The following table shows the cost for each employee to perform each job.

Employee A	Employee B	Employee C

Job 1 48 45 44 Job 2 43 35 45 Job 3 51 51 50 Solve this assignment problem in Excel to find the lowest cost solution and answer the following questions:

Which employee is assigned to job 1?

(Click to select)

Which employee is assigned to job 2?

(Click to select)

Which employee is assigned to job 3?

(Click to select)

What is the minimum cost to complete all three jobs?

Solution

This problem is a typical example of an assignment problem, which can be solved using the Hungarian method (or assignment algorithm) to minimize costs. In Excel, you can solve this by using Solver, an add-in that helps find the optimal solution for such linear programming problems.

Steps to solve the problem in Excel using Solver:

  1. Set up the cost matrix: Create a 3x3 matrix in Excel with the rows representing the jobs and the columns representing the employees. Populate the table as follows:

    ABC
    Job 1484544
    Job 2433545
    Job 3515150
  2. Define decision variables: Create a second matrix (3x3) next to the cost matrix that represents decision variables. For example, let’s use binary variables (0 or 1) to indicate whether an employee is assigned to a job or not:

    • If employee A is assigned to Job 1, the variable for that assignment is 1, otherwise it is 0. Do the same for all other employee-job combinations.
  3. Create constraints:

    • Ensure that each job is assigned to exactly one employee.
    • Ensure that each employee is assigned exactly one job.
  4. Objective function:

    • Create a formula to calculate the total cost based on the decision variables. The objective is to minimize this total cost.
  5. Use Solver:

    • Set the objective as the total cost (which needs to be minimized).
    • Set constraints to ensure each job is assigned to exactly one employee and each employee is assigned exactly one job.
    • Use the Solver function in Excel to solve for the optimal assignment.

Solver Configuration:

  • Objective: Minimize the total cost.
  • Changing variables: The binary decision variables (0 or 1) representing assignments.
  • Constraints:
    • Each row (job) must sum to 1 (i.e., each job gets exactly one employee).
    • Each column (employee) must sum to 1 (i.e., each employee is assigned to exactly one job).

Solution:

After running Solver, you will find the optimal assignment to minimize the cost:

  • Employee A is assigned to Job 3.
  • Employee B is assigned to Job 2.
  • Employee C is assigned to Job 1.

Minimum Cost:

The minimum cost to complete all three jobs is 124.


Would you like further details on how to set this up in Excel? Let me know if you have any questions!

Here are 5 questions to expand your understanding:

  1. What is the general structure of an assignment problem?
  2. How does the Hungarian method minimize costs?
  3. How can linear programming be applied to other real-world problems?
  4. What are the benefits of using Solver in Excel for optimization problems?
  5. How can you manually check if a given solution is optimal?

Tip: Always double-check Solver's constraints to ensure the problem is properly set up for minimizing or maximizing the desired outcome.

Ask a new question for Free

By Image

Drop file here or Click Here to upload

Math Problem Analysis

Mathematical Concepts

Linear Programming
Optimization
Assignment Problem

Formulas

Objective function: Minimize total cost
Constraints: Sum of assignments per job and employee = 1

Theorems

Hungarian Algorithm

Suitable Grade Level

University Level or Advanced High School (Grades 11-12)