a) You are given N tasks and M agents. Agent i can execute a fraction fij...

 

Transcribed Image Text:

a) You are given N tasks and M agents. Agent i can execute a fraction fij of task j in one hour. You have to assign tasks to agents to minimize the time T when all the jobs get completed. Formulate this as an LP. Prove that there exists an optimal solution with at most N+M pairs (i, j) such that agent i executes a non-zero amount of task j. For clarity, we use the following assumptions: - • An agent can perform multiple tasks, but not simultaneously. • Multiple agents can work on the same task at the same time, but an agent can only work one task at any given time T is the maximum of the times the agents finish their tasks. b) Reformulate the previous problem when the problem is to minimize the total cost incurred, assuming that agent i charges c; dollars per hour. Prove that there exists an optimal solution to your LP where there are at most N pairs (i, j) such that agent i executes task j. Does this offer any insight into easily computing an optimal solution without solving the LP? a) You are given N tasks and M agents. Agent i can execute a fraction fij of task j in one hour. You have to assign tasks to agents to minimize the time T when all the jobs get completed. Formulate this as an LP. Prove that there exists an optimal solution with at most N+M pairs (i, j) such that agent i executes a non-zero amount of task j. For clarity, we use the following assumptions: - • An agent can perform multiple tasks, but not simultaneously. • Multiple agents can work on the same task at the same time, but an agent can only work one task at any given time T is the maximum of the times the agents finish their tasks. b) Reformulate the previous problem when the problem is to minimize the total cost incurred, assuming that agent i charges c; dollars per hour. Prove that there exists an optimal solution to your LP where there are at most N pairs (i, j) such that agent i executes task j. Does this offer any insight into easily computing an optimal solution without solving the LP?

Answer rating: 100% (QA)

Recognize the issue The purpose of a linear programming issue is to figure out how to get the most o... View the full answer