2 solve the following assignment problem of assigning four workers to four machines

• How it works
• Homework answers

Answer to Question #288489 in Management for sinte

1.      Solve the following assignment problem of assigning four workers to four machines:

-------------------------------------------------

                          Machine       1          2         3        4 

worker 1      1         4         6         3         

worker 2       9         7       10         9

worker 3      4         5       11         7         

worker 4       8         7         8         5

The answer to your question is provided in the image:

Need a fast expert's response?

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS !

Leave a comment

Ask your question, related questions.

• 1. 5. L&D management is a strategic activity that not only contributes to the overall HRD strategy
• 2. The process of risk analysis includes determining the severity or consequences and the probability f
• 3. L&D management is a strategic activity that not only contributes to the overall HRD strategy and
• 4. How does moderation support the assessment process
• 5. Discuss the three duties of the public relations practitioner, according to systems theory. Suppor
• 6. Systems theory enables us to understand the interdependence between the organisation and its enviro
• 7. Identify all possible stakeholders of Nulaid Eggs Company, according to the information in the case
• Programming
• Engineering

Who Can Help Me with My Assignment

There are three certainties in this world: Death, Taxes and Homework Assignments. No matter where you study, and no matter…

How to Finish Assignments When You Can’t

Crunch time is coming, deadlines need to be met, essays need to be submitted, and tests should be studied for.…

How to Effectively Study for a Math Test

Numbers and figures are an essential part of our world, necessary for almost everything we do every day. As important…

Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research

Chapter: 12th business maths and statistics : chapter 10 : operations research.

Solution of assignment problems (Hungarian Method)

First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.

Step :1 Choose the least element in each row and subtract it from all the elements of that row.

Step :2 Choose the least element in each column and subtract it from all the elements of that column. Step 2 has to be performed from the table obtained in step 1.

Step:3 Check whether there is atleast one zero in each row and each column and make an assignment as follows.

Step :4 If each row and each column contains exactly one assignment, then the solution is optimal.

Example 10.7

Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV.

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced. Now let us find the solution.

Step 1: Select a smallest element in each row and subtract this from all the elements in its row.

Look for atleast one zero in each row and each column.Otherwise go to step 2.

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.

Step 3 (Assignment):

Thus all the four assignments have been made. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost

Example 10.8

Consider the problem of assigning five jobs to five persons. The assignment costs are given as follows. Determine the optimum assignment schedule.

∴ The given assignment problem is balanced.

Now let us find the solution.

The cost matrix of the given assignment problem is

Column 3 contains no zero. Go to Step 2.

Thus all the five assignments have been made. The Optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ` 9

Example 10.9

Solve the following assignment problem.

Since the number of columns is less than the number of rows, given assignment problem is unbalanced one. To balance it , introduce a dummy column with all the entries zero. The revised assignment problem is

Here only 3 tasks can be assigned to 3 men.

Step 1: is not necessary, since each row contains zero entry. Go to Step 2.

Step 3 (Assignment) :

Since each row and each columncontains exactly one assignment,all the three men have been assigned a task. But task S is not assigned to any Man. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ₹ 35

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

• MapReduce Algorithm
• Linear Programming using Pyomo
• Networking and Professional Development for Machine Learning Careers in the USA
• Predicting Employee Churn in Python
• Airflow Operators

Solving Assignment Problem using Linear Programming in Python

Learn how to use Python PuLP to solve Assignment problems using Linear Programming.

In earlier articles, we have seen various applications of Linear programming such as transportation, transshipment problem, Cargo Loading problem, and shift-scheduling problem. Now In this tutorial, we will focus on another model that comes under the class of linear programming model known as the Assignment problem. Its objective function is similar to transportation problems. Here we minimize the objective function time or cost of manufacturing the products by allocating one job to one machine.

If we want to solve the maximization problem assignment problem then we subtract all the elements of the matrix from the highest element in the matrix or multiply the entire matrix by –1 and continue with the procedure. For solving the assignment problem, we use the Assignment technique or Hungarian method, or Flood’s technique.

The transportation problem is a special case of the linear programming model and the assignment problem is a special case of transportation problem, therefore it is also a special case of the linear programming problem.

In this tutorial, we are going to cover the following topics:

Assignment Problem

A problem that requires pairing two sets of items given a set of paired costs or profit in such a way that the total cost of the pairings is minimized or maximized. The assignment problem is a special case of linear programming.

For example, an operation manager needs to assign four jobs to four machines. The project manager needs to assign four projects to four staff members. Similarly, the marketing manager needs to assign the 4 salespersons to 4 territories. The manager’s goal is to minimize the total time or cost.

Problem Formulation

A manager has prepared a table that shows the cost of performing each of four jobs by each of four employees. The manager has stated his goal is to develop a set of job assignments that will minimize the total cost of getting all 4 jobs.  

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have two variable lists: workers and jobs. Let’s create them using  LpVariable.dicts()  class.  LpVariable.dicts()  used with Python’s list comprehension.  LpVariable.dicts()  will take the following four values:

• First, prefix name of what this variable represents.
• Second is the list of all the variables.
• Third is the lower bound on this variable.
• Fourth variable is the upper bound.
• Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are  LpContinuous  or  LpInteger .

Let’s first create a list route for the route between warehouse and project site and create the decision variables using LpVariable.dicts() the method.

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem  object. lpSum(vector)is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

Define the Constraints

Here, we are adding two types of constraints: Each job can be assigned to only one employee constraint and Each employee can be assigned to only one job. We have added the 2 constraints defined in the problem by adding them to the LpProblem  object.

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.

In this article, we have learned about Assignment problems, Problem Formulation, and implementation using the python PuLp library. We have solved the Assignment problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. You can also run other case studies on Cargo Loading problems , Staff scheduling problems . In upcoming articles, we will write more on different optimization problems such as transshipment problem, balanced diet problem. You can revise the basics of mathematical concepts in  this article  and learn about Linear Programming  in this article .

• Solving Blending Problem in Python using Gurobi
• Transshipment Problem in Python Using PuLP

You May Also Like

Working with Pandas Date and Time

Decision Tree Classification in Python

Support Vector Machine Classification in Scikit-learn

• Google OR-Tools
• Español – América Latina
• Português – Brasil
• Tiếng Việt

Solving an Assignment Problem

This section presents an example that shows how to solve an assignment problem using both the MIP solver and the CP-SAT solver.

In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). Note that there is one more worker than in the example in the Overview .

The costs of assigning workers to tasks are shown in the following table.

The problem is to assign each worker to at most one task, with no two workers performing the same task, while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

MIP solution

The following sections describe how to solve the problem using the MPSolver wrapper .

Import the libraries

The following code imports the required libraries.

Create the data

The following code creates the data for the problem.

The costs array corresponds to the table of costs for assigning workers to tasks, shown above.

Declare the MIP solver

The following code declares the MIP solver.

Create the variables

The following code creates binary integer variables for the problem.

Create the constraints

Create the objective function.

The following code creates the objective function for the problem.

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver

The following code invokes the solver.

Print the solution

The following code prints the solution to the problem.

Here is the output of the program.

Complete programs

Here are the complete programs for the MIP solution.

CP SAT solution

The following sections describe how to solve the problem using the CP-SAT solver.

Declare the model

The following code declares the CP-SAT model.

The following code sets up the data for the problem.

The following code creates the constraints for the problem.

Here are the complete programs for the CP-SAT solution.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2023-01-02 UTC.

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

• Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)
• Introduction to Exact Cover Problem and Algorithm X
• Greedy Approximate Algorithm for Set Cover Problem
• Job Assignment Problem using Branch And Bound
• Implementation of Exhaustive Search Algorithm for Set Packing
• Channel Assignment Problem
• Chocolate Distribution Problem | Set 2
• Transportation Problem | Set 1 (Introduction)
• OLA Interview Experience | Set 11 ( For Internship)
• Top 20 Greedy Algorithms Interview Questions
• Job Sequencing Problem - Loss Minimization
• Prim's Algorithm (Simple Implementation for Adjacency Matrix Representation)
• Data Structures and Algorithms | Set 21
• Adobe Interview Experience | Set 55 (On-Campus Full Time for MTS profile)
• Amazon Interview Experience | Set 211 (On-Campus for Internship)
• OYO Rooms Interview Experience | Set 3 (For SDE-II, Gurgaon)
• C# Program for Dijkstra's shortest path algorithm | Greedy Algo-7
• Algorithms | Dynamic Programming | Question 7
• Amazon Interview | Set 46 (On-campus for Internship)

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Do the same (as step 1) for all columns.
• Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
• Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Try it before moving to see the solution

Explanation for above simple example:

  An example that doesn’t lead to optimal value in first attempt: In the above example, the first check for optimality did give us solution. What if we the number covering lines is less than n.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity :   O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

In the next post, we will be discussing implementation of the above algorithm. The implementation requires more steps as we need to find minimum number of lines to cover all 0’s using a program. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY

Please Login to comment...

Similar reads.

• Mathematical

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Hungarian Method Examples

Now we will examine a few highly simplified illustrations of Hungarian Method for solving an assignment problem .

Later in the chapter, you will find more practical versions of assignment models like Crew assignment problem , Travelling salesman problem , etc.

Example-1, Example-2

Example 1: Hungarian Method

The Funny Toys Company has four men available for work on four separate jobs. Only one man can work on any one job. The cost of assigning each man to each job is given in the following table. The objective is to assign men to jobs in such a way that the total cost of assignment is minimum.

This is a minimization example of assignment problem . We will use the Hungarian Algorithm to solve this problem.

Identify the minimum element in each row and subtract it from every element of that row. The result is shown in the following table.

"A man has one hundred dollars and you leave him with two dollars, that's subtraction." -Mae West

On small screens, scroll horizontally to view full calculation

Identify the minimum element in each column and subtract it from every element of that column.

Make the assignments for the reduced matrix obtained from steps 1 and 2 in the following way:

• For every zero that becomes assigned, cross out (X) all other zeros in the same row and the same column.
• If for a row and a column, there are two or more zeros and one cannot be chosen by inspection, choose the cell arbitrarily for assignment.

An optimal assignment is found, if the number of assigned cells equals the number of rows (and columns). In case you have chosen a zero cell arbitrarily, there may be alternate optimal solutions. If no optimal solution is found, go to step 5.

Use Horizontal Scrollbar to View Full Table Calculation

Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix obtained from step 3 by adopting the following procedure:

• Mark all the rows that do not have assignments.
• Mark all the columns (not already marked) which have zeros in the marked rows.
• Mark all the rows (not already marked) that have assignments in marked columns.
• Repeat steps 5 (ii) and (iii) until no more rows or columns can be marked.
• Draw straight lines through all unmarked rows and marked columns.

You can also draw the minimum number of lines by inspection.

Select the smallest element (i.e., 1) from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment.

Now again make the assignments for the reduced matrix.

Final Table: Hungarian Method

Since the number of assignments is equal to the number of rows (& columns), this is the optimal solution.

The total cost of assignment = A1 + B4 + C2 + D3

Substituting values from original table: 20 + 17 + 17 + 24 = Rs. 78.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

Hungarian Method

The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term “Hungarian method” to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Let’s go through the steps of the Hungarian method with the help of a solved example.

Hungarian Method to Solve Assignment Problems

The Hungarian method is a simple way to solve assignment problems. Let us first discuss the assignment problems before moving on to learning the Hungarian method.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal amount of resources to the same number of activities. As a result, the overall cost of allocation is minimised or the total profit is maximised.

Because available resources such as workers, machines, and other resources have varying degrees of efficiency for executing different activities, and hence the cost, profit, or loss of conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to assign jobs to machines for the least amount of money possible (or maximum profit). Based on the notion that each machine can accomplish each task, but at variable levels of efficiency.

Hungarian Method Steps

Check to see if the number of rows and columns are equal; if they are, the assignment problem is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row. Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all the components in that column, ensuring that each column contains at least one zero.

Step 3 – Assign zeros

• Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.
• Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

• The present assignment is optimal if each row and column has exactly one encircled zero.
• The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).

(c) Highlight the rows that have assignments in indicated columns (if they haven’t previously been marked).

(d) Continue with (b) and (c) until no further marking is needed.

(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines, but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

Hungarian Method Example

Use the Hungarian method to solve the given assignment problem stated in the table. The entries in the matrix represent each man’s processing time in hours.

\(\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

With 5 jobs and 5 men, the stated problem is balanced.

\(\begin{array}{l}A = \begin{bmatrix}20 & 15 & 18 & 20 & 25 \\18 & 20 & 12 & 14 & 15 \\21 & 23 & 25 & 27 & 25 \\17 & 18 & 21 & 23 & 20 \\18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

Subtract the lowest cost element in each row from all of the elements in the given cost matrix’s row. Make sure that each row has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 5 & 10 \\6 & 8 & 0 & 2 & 3 \\0 & 2 & 4 & 6 & 4 \\0 & 1 & 4 & 6 & 3 \\2 & 2 & 0 & 3 & 4 \\\end{bmatrix}\end{array} \)

Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 3 & 7 \\6 & 8 & 0 & 0 & 0 \\0 & 2 & 4 & 4 & 1 \\0 & 1 & 4 & 4 & 0 \\2 & 2 & 0 & 1 & 1 \\\end{bmatrix}\end{array} \)

When the zeros are assigned, we get the following:

The present assignment is optimal because each row and column contain precisely one encircled zero.

Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.

Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.

Practice Question on Hungarian Method

Use the Hungarian method to solve the following assignment problem shown in table. The matrix entries represent the time it takes for each job to be processed by each machine in hours.

\(\begin{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} \)

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

The following is a quick overview of the Hungarian method: Step 1: Subtract the row minima. Step 2: Subtract the column minimums. Step 3: Use a limited number of lines to cover all zeros. Step 4: Add some more zeros to the equation.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

Related questions with answers

Five employees are available to perform four jobs. The lime it takes each person to perform each job is given in Table 50. Determine the assignment of employees to jobs that minimizes the total time required to perform the four jobs. TABLE 50:

Person Time (hours)   Job 1 Job 2 Job 3 Job 4 1 22 18 30 18 2 18 — 27 22 3 26 20 28 28 4 16 22 — 14 5 21 — 25 28 \begin{matrix} \text{Person} & \text{Time (hours)}\\ \text{ } & \text{Job 1} & \text{Job 2} & \text{Job 3} & \text{Job 4}\\ \text{1} & \text{22} & \text{18} & \text{30} & \text{18}\\ \text{2} & \text{18} & \text{—} & \text{27} & \text{22}\\ \text{3} & \text{26} & \text{20} & \text{28} & \text{28}\\ \text{4} & \text{16} & \text{22} & \text{—} & \text{14}\\ \text{5} & \text{21} & \text{—} & \text{25} & \text{28}\\ \end{matrix} Person   1 2 3 4 5 ​ Time (hours) Job 1 22 18 26 16 21 ​ Job 2 18 — 20 22 — ​ Job 3 30 27 28 — 25 ​ Job 4 18 22 28 14 28 ​

Four workers are available to perform jobs 1-4 Unfortunately, three workers can do only certain jobs worker 1, only job 1; worker 2, only jobs 1 and 2; worker 3, only job 2; worker 4, any job. Draw the network for the maximum-flow problem that can be used to determine whether all jobs can be assigned to a suitable worker.

Find a function f such that F=delf and evaluate integral C F.dr along the given curve C. F(x,y)=xy^2i+x^2yj, C; r(t)=<t+sin1/2pit, t+cos1/2pit>, 0<=t<=1

Five workers are available to perform four jobs. The time it takes each worker to perform each job is given in Table 65. The goal is to assign workers to jobs so as to minimize the total time required to perform the four jobs. Use the Hungarian method to solve the problem. TABLE 65:   Time (Hours) Worker Job 1 Job 2 Job 3 Job 4 1 10 15 10 15 2 12 8 20 16 3 12 9 12 18 4 6 12 15 18 5 16 12 8 12 \begin{matrix} \text{ } & \text{Time (Hours)}\\ \text{Worker} & \text{Job 1} & \text{Job 2} & \text{Job 3} & \text{Job 4}\\ \text{1} & \text{10} & \text{15} & \text{10} & \text{15}\\ \text{2} & \text{12} & \text{8} & \text{20} & \text{16}\\ \text{3} & \text{12} & \text{9} & \text{12} & \text{18}\\ \text{4} & \text{6} & \text{12} & \text{15} & \text{18}\\ \text{5} & \text{16} & \text{12} & \text{8} & \text{12}\\ \end{matrix}   Worker 1 2 3 4 5 ​ Time (Hours) Job 1 10 12 12 6 16 ​ Job 2 15 8 9 12 12 ​ Job 3 10 20 12 15 8 ​ Job 4 15 16 18 18 12 ​

We add a dummy job with associated times 0 for each employee to balance the assignment problem. We obtain the following table:

J 1 J 2 J 3 J 4 D W 1 10 15 10 15 0 W 2 12 8 20 16 0 W 3 12 9 12 18 0 W 4 6 12 15 18 0 W 5 16 12 8 12 0 \begin{array}{|c|c|c|c|c|c|}\hline &J1&J2&J3&J4&D\\\hline W1&10&15&10&15&0\\\hline W2&12&8&20&16&0\\\hline W3&12&9&12&18&0\\\hline W4&6&12&15&18&0\\\hline W5&16&12&8&12&0\\\hline \end{array} W 1 W 2 W 3 W 4 W 5 ​ J 1 10 12 12 6 16 ​ J 2 15 8 9 12 12 ​ J 3 10 20 12 15 8 ​ J 4 15 16 18 18 12 ​ D 0 0 0 0 0 ​ ​

The Hungarian method then gives us the assignment

J 1 J 2 J 3 J 4 D W 1 1 W 2 1 W 3 1 W 4 1 W 5 1 \begin{array}{|c|c|c|c|c|c|}\hline &J1&J2&J3&J4&D\\\hline W1&&&1&&\\\hline W2&&1&&&\\\hline W3&&&&&1\\\hline W4&1&&&&\\\hline W5&&&&1&\\\hline \end{array} W 1 W 2 W 3 W 4 W 5 ​ J 1 1 ​ J 2 1 ​ J 3 1 ​ J 4 1 ​ D 1 ​ ​

Create a free account to view solutions

Recommended textbook solutions.

Introduction to Operations Research

Operations Research: Applications and Algorithms

More related questions.

The following instruction is not included in the MIPS instruction set: rpt $t2, loop # if(R[rs]>0) R[rs]=R[rs]−1, PC=PC+4+BranchAddr. 1. If this instruction were to be implemented in the MIPS instruction set, what is the most appropriate instruction format? 2. What is the shortest sequence of MIPS instructions that performs the same operation?

A company must meet the following demands for a product: January, 30 units; February, 30 units; March, 20 units. Demand may be backlogged at a cost of $5/unit/month. All demand must be met by the end of March. Thus, if I unit of January demand is met during March, a backlogging cost of 5(2) =$10 is incurred. Monthly production capacity and unit production cost during each month are given in Table 66. A holding cost of $20/unit is assessed on the inventory at the end of each month. a. Formulate a balanced transportation problem that could be used to determine how to minimize the total cost (including backlogging, holding, and production costs) of meeting demand. b. Use Vogel’s method to find a basic feasible solution. c. Use the transportation simplex to determine how to meet each month’s demand. Make sure to give an interpretation of your optimal solution (for example, 20 units of month 2 demand is met from month 1 production). TABLE 66:

Month Production Capacity Unit Production Cost January 35 $400 February 30 $420 March 35 $410 \begin{matrix} \text{Month} & \text{Production Capacity} & \text{Unit Production Cost}\\ \text{January} & \text{35} & \text{\$400}\\ \text{February} & \text{30} & \text{\$420}\\ \text{March} & \text{35} & \text{\$410}\\ \end{matrix} Month January February March ​ Production Capacity 35 30 35 ​ Unit Production Cost $400 $420 $410 ​

Multiply. Write the product in simplest form.

1 4 5 × 5 12 1\frac { 4 } { 5 } \times \frac { 5 } { 12 } 1 5 4 ​ × 12 5 ​

Use the following terms in a separate sentence. demographic transition

In Problem, assume that before being shipped to Los Angeles or New York, all oil produced at the wells must be refined at either Galveston or Mobile. To refine 1,000 barrels of oil costs $12 at Mobile and$10 at Galveston. Assuming that both Mobile and Galveston have infinite refinery capacity, formulate a transshipment and balanced transportation model to minimize the daily cost of transporting and refining the oil requirements of Los Angeles and New York. Problem: Sunco Oil produces oil at two wells. Well 1 can produce as many as 150,000 barrels per day, and well 2 can produce as many as 200,000 barrels per day. It is possible to ship oil directly from the wells to Sunco’s customers in Los Angeles and New York. Alternatively, Sunco could transport oil to the ports of Mobile and Galveston and then ship it by tanker to New York or Los Angeles. Los Angeles requires 160,000 barrels per day, and New York requires 140,000 barrels per day. The costs of shipping 1,000 barrels between two points areshown in Table 61. Formulate a transshipment model (and equivalent transportation model) that could be used to minimize the transport costs in meeting the oil demands of Los Angeles and New York. Table 61:

From To ($)   Well 1 Well 2 Mobile Galveston N.Y. L.A. Well 1 0 — 10 13 25 28 Well 2 — 0 15 12 26 25 Mobile — — 0 6 16 17 Galveston — — 6 0 14 16 N.Y. — — — — 0 15 L.A. — — — — 15 0 \begin{matrix} \text{From} & \text{To (\$)}\\ \text{ } & \text{Well 1} & \text{Well 2} & \text{Mobile} & \text{Galveston} & \text{N.Y.} & \text{L.A.}\\ \text{Well 1} & \text{0} & \text{—} & \text{10} & \text{13} & \text{25} & \text{28}\\ \text{Well 2} & \text{—} & \text{0} & \text{15} & \text{12} & \text{26} & \text{25}\\ \text{Mobile} & \text{—} & \text{—} & \text{0} & \text{6} & \text{16} & \text{17}\\ \text{Galveston} & \text{—} & \text{—} & \text{6} & \text{0} & \text{14} & \text{16}\\ \text{N.Y.} & \text{—} & \text{—} & \text{—} & \text{—} & \text{0} & \text{15}\\ \text{L.A.} & \text{—} & \text{—} & \text{—} & \text{—} & \text{15} & \text{0}\\ \end{matrix} From   Well 1 Well 2 Mobile Galveston N.Y. L.A. ​ To ($) Well 1 0 — — — — — ​ Well 2 — 0 — — — — ​ Mobile 10 15 0 6 — — ​ Galveston 13 12 6 0 — — ​ N.Y. 25 26 16 14 0 15 ​ L.A. 28 25 17 16 15 0 ​

Note: Dashes indicate shipments that are not allowed.

Think back to a time when you negotiated with someone in a position of authority for something you strongly wanted. Briefly describe the tactics you used and look for similarities or differences between those and the tactics unions use with employers.

Credit card numbers typically have 16 digits, but not all of them are random. Discover cards begin with the digits 6011. If you know that the first four digits are 6011 and you also know the last four digits of a Discover card, what is the probability of randomly generating the other digits and getting all of them correct? Is this something to worry about?

Steelco manufactures three types of steel at different plants. The time required to manufacture 1 ton of steel (regardless of type) and the costs at each plant are shown in Table 8. Each week, 100 tons of each type of steel (1, 2, and 3) must be produced. Each plant is open 40 hours per week, a Formulate a balanced transportation problem to minimize the cost of meeting Steelco’s weekly requirements, b Suppose the time required to produce 1ton of steel depends on the type of steel as well as on the plant at which it is produced. Could a transportation problem still be formulated? TABLE 8:

  Cost ($)     Time (minutes) Plant Steel 1 Steel 2 Steel 3   1 60 40 28 20 2 50 30 30 16 3 43 20 20 15 \begin{matrix} \text{ } & \text{Cost (\$)} & \text{ } & \text{ } & \text{Time (minutes)}\\ \text{Plant} & \text{Steel 1} & \text{Steel 2} & \text{Steel 3} & \text{ }\\ \text{1} & \text{60} & \text{40} & \text{28} & \text{20}\\\text{2} & \text{50} & \text{30} & \text{30} & \text{16}\\ \text{3} & \text{43} & \text{20} & \text{20} & \text{15}\\ \end{matrix}   Plant 1 2 3 ​ Cost ($) Steel 1 60 50 43 ​   Steel 2 40 30 20 ​   Steel 3 28 30 20 ​ Time (minutes)   20 16 15 ​

  Time (minutes)     Plant Steel 1 Steel 2 Steel 3 1 15 12 15 2 15 15 20 3 10 10 15 \begin{matrix} \text{ } & \text{Time (minutes)} & \text{ } & \text{ }\\ \text{Plant} & \text{Steel 1} & \text{Steel 2} & \text{Steel 3}\\ \text{1} & \text{15} & \text{12} & \text{15}\\ \text{2} & \text{15} & \text{15} & \text{20}\\ \text{3} & \text{10} & \text{10} & \text{15}\\\end{matrix}   Plant 1 2 3 ​ Time (minutes) Steel 1 15 15 10 ​   Steel 2 12 15 10 ​   Steel 3 15 20 15 ​

Draw the tree structure that describes binary search on a list with 16 elements. What is the number of comparisons in the worst case?

Professor Jennings claims that only 35% of the students at Flora College work while attending school. Dean Renata thinks that the professor has underestimated the number of students with part-time or fulltime jobs. A random sample of 81 students shows that 39 have jobs. Do the data indicate that more than 35% of the students have jobs? (Use a 5% level of significance.)

Furnco manufactures tables and chairs. Each table and chair must be made entirely out of oak or entirely out of pine. A total of 150 board ft of oak and 210 board ft of pine are available A table requires either 17 board ft of oak or 30 board ft of pine, and a chair requires either 5 board ft of oak or 13 board ft of pine. Each table can be sold for $40 and each chair for$15. Formulate an LP that can be used to maximize revenue.

Televco produces TV picture tubes at three plants. Plant 1 can produce 50 tubes per week; plant 2, 100 tubes per week; and plant 3, 50 tubes per week. Tubes are shipped to three customers. The profit earned per tube depends on the site where the tube was produced and on the customer who purchases the tube (see Table 64). Customer 1 is willing to purchase as many as 80 tubes per week; customer 2, as many as 90; and customer 3, as many as 100. Televco wants to find a shipping and production plan that will maximize profits. a. Formulate a balanced transportation problem that can be used to maximize Televco’s profits b. Use the northwest corner method to find a bfs to the problem. c. Use the transportation simplex to find an optimal solution to the problem. TABLE 64:

From To ($)   Customer 1 Customer 2 Customer 3 Plant 1 75 60 69 Plant 2 79 73 68 Plant 3 85 76 70 \begin{matrix} \text{From} & \text{To (\$)}\\ \text{ } & \text{Customer 1} & \text{Customer 2} & \text{Customer 3}\\ \text{Plant 1} & \text{75} & \text{60} & \text{69}\\ \text{Plant 2} & \text{79} & \text{73} & \text{68}\\ \text{Plant 3} & \text{85} & \text{76} & \text{70}\\ \end{matrix} From   Plant 1 Plant 2 Plant 3 ​ To ($) Customer 1 75 79 85 ​ Customer 2 60 73 76 ​ Customer 3 69 68 70 ​

Farmer Jones bakes two types of cake (chocolate and vanilla) to supplement his income. Each chocolate cake can be sold for $1, and each vanilla cake can be sold for 50¢. Each chocolate cake requires 20 minutes of baking time and uses 4 eggs. Each vanilla cake requires 40 minutes of baking time and uses 1 egg. Eight hours of baking time and 30 eggs are available Formulate an LP to maximize Farmer Jones’s revenue, then graphically solve the LP (A fractional number of cakes is okay.)

Snapsolve any problem by taking a picture. Try it in the Numerade app?