تکلیف با تیم های کارگری

نسخه های زیادی از مشکل انتساب وجود دارد که محدودیت های اضافی برای کارگران یا وظایف دارند. در مثال بعدی، شش کارگر به دو تیم تقسیم می شوند و هر تیم حداکثر می تواند دو وظیفه را انجام دهد.

بخش های زیر یک برنامه پایتون را ارائه می دهد که این مشکل را با استفاده از CP-SAT یا حل کننده MIP حل می کند. برای راه‌حلی با استفاده از حل‌کننده جریان حداقل هزینه، به بخش تکالیف با تیم‌ها مراجعه کنید.

راه حل CP-SAT

ابتدا، اجازه دهید نگاهی به راه حل CP-SAT برای مشکل بیندازیم.

کتابخانه ها را وارد کنید

کد زیر کتابخانه مورد نیاز را وارد می کند.

پایتون

from ortools.sat.python import cp_model

C++

#include <stdlib.h>

#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

جاوا

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

سی شارپ

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

داده ها را تعریف کنید

کد زیر داده های برنامه را ایجاد می کند.

پایتون

costs = [
    [90, 76, 75, 70],
    [35, 85, 55, 65],
    [125, 95, 90, 105],
    [45, 110, 95, 115],
    [60, 105, 80, 75],
    [45, 65, 110, 95],
]
num_workers = len(costs)
num_tasks = len(costs[0])

team1 = [0, 2, 4]
team2 = [1, 3, 5]
# Maximum total of tasks for any team
team_max = 2

C++

const std::vector<std::vector<int>> costs = {{
    {{90, 76, 75, 70}},
    {{35, 85, 55, 65}},
    {{125, 95, 90, 105}},
    {{45, 110, 95, 115}},
    {{60, 105, 80, 75}},
    {{45, 65, 110, 95}},
}};
const int num_workers = static_cast<int>(costs.size());
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = static_cast<int>(costs[0].size());
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);

const std::vector<int> team1 = {{0, 2, 4}};
const std::vector<int> team2 = {{1, 3, 5}};
// Maximum total of tasks for any team
const int team_max = 2;

جاوا

int[][] costs = {
    {90, 76, 75, 70},
    {35, 85, 55, 65},
    {125, 95, 90, 105},
    {45, 110, 95, 115},
    {60, 105, 80, 75},
    {45, 65, 110, 95},
};
final int numWorkers = costs.length;
final int numTasks = costs[0].length;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
final int[] allTasks = IntStream.range(0, numTasks).toArray();

final int[] team1 = {0, 2, 4};
final int[] team2 = {1, 3, 5};
// Maximum total of tasks for any team
final int teamMax = 2;

سی شارپ

int[,] costs = {
    { 90, 76, 75, 70 },   { 35, 85, 55, 65 },  { 125, 95, 90, 105 },
    { 45, 110, 95, 115 }, { 60, 105, 80, 75 }, { 45, 65, 110, 95 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

int[] team1 = { 0, 2, 4 };
int[] team2 = { 1, 3, 5 };
// Maximum total of tasks for any team
int teamMax = 2;

مدل را ایجاد کنید

کد زیر مدل را ایجاد می کند.

پایتون

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

جاوا

CpModel model = new CpModel();

سی شارپ

CpModel model = new CpModel();

متغیرها را ایجاد کنید

کد زیر آرایه ای از متغیرها را برای مشکل ایجاد می کند.

پایتون

x = {}
for worker in range(num_workers):
    for task in range(num_tasks):
        x[worker, task] = model.new_bool_var(f"x[{worker},{task}]")

C++

// x[i][j] is an array of Boolean variables. x[i][j] is true
// if worker i is assigned to task j.
std::vector<std::vector<BoolVar>> x(num_workers,
                                    std::vector<BoolVar>(num_tasks));
for (int worker : all_workers) {
  for (int task : all_tasks) {
    x[worker][task] = cp_model.NewBoolVar().WithName(
        absl::StrFormat("x[%d,%d]", worker, task));
  }
}

جاوا

Literal[][] x = new Literal[numWorkers][numTasks];
// Variables in a 1-dim array.
for (int worker : allWorkers) {
  for (int task : allTasks) {
    x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
  }
}

سی شارپ

BoolVar[,] x = new BoolVar[numWorkers, numTasks];
foreach (int worker in allWorkers)
{
    foreach (int task in allTasks)
    {
        x[worker, task] = model.NewBoolVar($"x[{worker},{task}]");
    }
}

برای هر جفت کارگر و وظیفه یک متغیر وجود دارد. توجه داشته باشید که کارگران 0 - 5 شماره گذاری می شوند، در حالی که وظایف 0 - 3 هستند، بر خلاف مثال اصلی ، که در آن همه گره ها باید به طور متفاوتی شماره گذاری می شدند، همانطور که توسط حل کننده جریان هزینه حداقل نیاز است.

محدودیت ها را اضافه کنید

کد زیر محدودیت هایی را برای برنامه ایجاد می کند.

پایتون

# Each worker is assigned to at most one task.
for worker in range(num_workers):
    model.add_at_most_one(x[worker, task] for task in range(num_tasks))

# Each task is assigned to exactly one worker.
for task in range(num_tasks):
    model.add_exactly_one(x[worker, task] for worker in range(num_workers))

# Each team takes at most two tasks.
team1_tasks = []
for worker in team1:
    for task in range(num_tasks):
        team1_tasks.append(x[worker, task])
model.add(sum(team1_tasks) <= team_max)

team2_tasks = []
for worker in team2:
    for task in range(num_tasks):
        team2_tasks.append(x[worker, task])
model.add(sum(team2_tasks) <= team_max)

C++

// Each worker is assigned to at most one task.
for (int worker : all_workers) {
  cp_model.AddAtMostOne(x[worker]);
}
// Each task is assigned to exactly one worker.
for (int task : all_tasks) {
  std::vector<BoolVar> tasks;
  for (int worker : all_workers) {
    tasks.push_back(x[worker][task]);
  }
  cp_model.AddExactlyOne(tasks);
}

// Each team takes at most two tasks.
LinearExpr team1_tasks;
for (int worker : team1) {
  for (int task : all_tasks) {
    team1_tasks += x[worker][task];
  }
}
cp_model.AddLessOrEqual(team1_tasks, team_max);

LinearExpr team2_tasks;
for (int worker : team2) {
  for (int task : all_tasks) {
    team2_tasks += x[worker][task];
  }
}
cp_model.AddLessOrEqual(team2_tasks, team_max);

جاوا

// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
  List<Literal> tasks = new ArrayList<>();
  for (int task : allTasks) {
    tasks.add(x[worker][task]);
  }
  model.addAtMostOne(tasks);
}

// Each task is assigned to exactly one worker.
for (int task : allTasks) {
  List<Literal> workers = new ArrayList<>();
  for (int worker : allWorkers) {
    workers.add(x[worker][task]);
  }
  model.addExactlyOne(workers);
}

// Each team takes at most two tasks.
LinearExprBuilder team1Tasks = LinearExpr.newBuilder();
for (int worker : team1) {
  for (int task : allTasks) {
    team1Tasks.add(x[worker][task]);
  }
}
model.addLessOrEqual(team1Tasks, teamMax);

LinearExprBuilder team2Tasks = LinearExpr.newBuilder();
for (int worker : team2) {
  for (int task : allTasks) {
    team2Tasks.add(x[worker][task]);
  }
}
model.addLessOrEqual(team2Tasks, teamMax);

سی شارپ

// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
    List<ILiteral> tasks = new List<ILiteral>();
    foreach (int task in allTasks)
    {
        tasks.Add(x[worker, task]);
    }
    model.AddAtMostOne(tasks);
}

// Each task is assigned to exactly one worker.
foreach (int task in allTasks)
{
    List<ILiteral> workers = new List<ILiteral>();
    foreach (int worker in allWorkers)
    {
        workers.Add(x[worker, task]);
    }
    model.AddExactlyOne(workers);
}

// Each team takes at most two tasks.
List<IntVar> team1Tasks = new List<IntVar>();
foreach (int worker in team1)
{
    foreach (int task in allTasks)
    {
        team1Tasks.Add(x[worker, task]);
    }
}
model.Add(LinearExpr.Sum(team1Tasks.ToArray()) <= teamMax);

List<IntVar> team2Tasks = new List<IntVar>();
foreach (int worker in team2)
{
    foreach (int task in allTasks)
    {
        team2Tasks.Add(x[worker, task]);
    }
}
model.Add(LinearExpr.Sum(team2Tasks.ToArray()) <= teamMax);

هدف را ایجاد کنید

کد زیر تابع هدف را ایجاد می کند.

پایتون

objective_terms = []
for worker in range(num_workers):
    for task in range(num_tasks):
        objective_terms.append(costs[worker][task] * x[worker, task])
model.minimize(sum(objective_terms))

C++

LinearExpr total_cost;
for (int worker : all_workers) {
  for (int task : all_tasks) {
    total_cost += x[worker][task] * costs[worker][task];
  }
}
cp_model.Minimize(total_cost);

جاوا

LinearExprBuilder obj = LinearExpr.newBuilder();
for (int worker : allWorkers) {
  for (int task : allTasks) {
    obj.addTerm(x[worker][task], costs[worker][task]);
  }
}
model.minimize(obj);

سی شارپ

LinearExprBuilder obj = LinearExpr.NewBuilder();
foreach (int worker in allWorkers)
{
    foreach (int task in allTasks)
    {
        obj.AddTerm(x[worker, task], costs[worker, task]);
    }
}
model.Minimize(obj);

مقدار تابع هدف کل هزینه تمام متغیرهایی است که توسط حل کننده مقدار 1 به آنها اختصاص داده شده است.

حل کننده را فراخوانی کنید

کد زیر حل کننده را فراخوانی می کند و نتایج را نمایش می دهد.

پایتون

solver = cp_model.CpSolver()
status = solver.solve(model)

C++

const CpSolverResponse response = Solve(cp_model.Build());

جاوا

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);

سی شارپ

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}");

نمایش نتایج

اکنون می توانیم راه حل را چاپ کنیم.

پایتون

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"Total cost = {solver.objective_value}\n")
    for worker in range(num_workers):
        for task in range(num_tasks):
            if solver.boolean_value(x[worker, task]):
                print(
                    f"Worker {worker} assigned to task {task}."
                    + f" Cost = {costs[worker][task]}"
                )
else:
    print("No solution found.")

C++

if (response.status() == CpSolverStatus::INFEASIBLE) {
  LOG(FATAL) << "No solution found.";
}
LOG(INFO) << "Total cost: " << response.objective_value();
LOG(INFO);
for (int worker : all_workers) {
  for (int task : all_tasks) {
    if (SolutionBooleanValue(response, x[worker][task])) {
      LOG(INFO) << "Worker " << worker << " assigned to task " << task
                << ".  Cost: " << costs[worker][task];
    }
  }
}

جاوا

// Check that the problem has a feasible solution.
if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
  System.out.println("Total cost: " + solver.objectiveValue() + "\n");
  for (int worker : allWorkers) {
    for (int task : allTasks) {
      if (solver.booleanValue(x[worker][task])) {
        System.out.println("Worker " + worker + " assigned to task " + task
            + ".  Cost: " + costs[worker][task]);
      }
    }
  }
} else {
  System.err.println("No solution found.");
}

سی شارپ

// Check that the problem has a feasible solution.
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
    Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n");
    foreach (int worker in allWorkers)
    {
        foreach (int task in allTasks)
        {
            if (solver.Value(x[worker, task]) > 0.5)
            {
                Console.WriteLine($"Worker {worker} assigned to task {task}. " +
                                  $"Cost: {costs[worker, task]}");
            }
        }
    }
}
else
{
    Console.WriteLine("No solution found.");
}

اینم خروجی برنامه

Total cost:  250
Worker 0 assigned to task 2. Cost = 75
Worker 1 assigned to task 0. Cost = 35
Worker 4 assigned to task 3. Cost = 75
Worker 5 assigned to task 1. Cost = 65
Time =  6  milliseconds

کل برنامه

در اینجا کل برنامه است.

پایتون

"""Solves a simple assignment problem."""
from ortools.sat.python import cp_model


def main() -> None:
    # Data
    costs = [
        [90, 76, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 105],
        [45, 110, 95, 115],
        [60, 105, 80, 75],
        [45, 65, 110, 95],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    team1 = [0, 2, 4]
    team2 = [1, 3, 5]
    # Maximum total of tasks for any team
    team_max = 2

    # Model
    model = cp_model.CpModel()

    # Variables
    x = {}
    for worker in range(num_workers):
        for task in range(num_tasks):
            x[worker, task] = model.new_bool_var(f"x[{worker},{task}]")

    # Constraints
    # Each worker is assigned to at most one task.
    for worker in range(num_workers):
        model.add_at_most_one(x[worker, task] for task in range(num_tasks))

    # Each task is assigned to exactly one worker.
    for task in range(num_tasks):
        model.add_exactly_one(x[worker, task] for worker in range(num_workers))

    # Each team takes at most two tasks.
    team1_tasks = []
    for worker in team1:
        for task in range(num_tasks):
            team1_tasks.append(x[worker, task])
    model.add(sum(team1_tasks) <= team_max)

    team2_tasks = []
    for worker in team2:
        for task in range(num_tasks):
            team2_tasks.append(x[worker, task])
    model.add(sum(team2_tasks) <= team_max)

    # Objective
    objective_terms = []
    for worker in range(num_workers):
        for task in range(num_tasks):
            objective_terms.append(costs[worker][task] * x[worker, task])
    model.minimize(sum(objective_terms))

    # Solve
    solver = cp_model.CpSolver()
    status = solver.solve(model)

    # Print solution.
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f"Total cost = {solver.objective_value}\n")
        for worker in range(num_workers):
            for task in range(num_tasks):
                if solver.boolean_value(x[worker, task]):
                    print(
                        f"Worker {worker} assigned to task {task}."
                        + f" Cost = {costs[worker][task]}"
                    )
    else:
        print("No solution found.")


if __name__ == "__main__":
    main()

C++

// Solve a simple assignment problem.
#include <stdlib.h>

#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

namespace operations_research {
namespace sat {

void AssignmentTeamsSat() {
  // Data
  const std::vector<std::vector<int>> costs = {{
      {{90, 76, 75, 70}},
      {{35, 85, 55, 65}},
      {{125, 95, 90, 105}},
      {{45, 110, 95, 115}},
      {{60, 105, 80, 75}},
      {{45, 65, 110, 95}},
  }};
  const int num_workers = static_cast<int>(costs.size());
  std::vector<int> all_workers(num_workers);
  std::iota(all_workers.begin(), all_workers.end(), 0);

  const int num_tasks = static_cast<int>(costs[0].size());
  std::vector<int> all_tasks(num_tasks);
  std::iota(all_tasks.begin(), all_tasks.end(), 0);

  const std::vector<int> team1 = {{0, 2, 4}};
  const std::vector<int> team2 = {{1, 3, 5}};
  // Maximum total of tasks for any team
  const int team_max = 2;

  // Model
  CpModelBuilder cp_model;

  // Variables
  // x[i][j] is an array of Boolean variables. x[i][j] is true
  // if worker i is assigned to task j.
  std::vector<std::vector<BoolVar>> x(num_workers,
                                      std::vector<BoolVar>(num_tasks));
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      x[worker][task] = cp_model.NewBoolVar().WithName(
          absl::StrFormat("x[%d,%d]", worker, task));
    }
  }

  // Constraints
  // Each worker is assigned to at most one task.
  for (int worker : all_workers) {
    cp_model.AddAtMostOne(x[worker]);
  }
  // Each task is assigned to exactly one worker.
  for (int task : all_tasks) {
    std::vector<BoolVar> tasks;
    for (int worker : all_workers) {
      tasks.push_back(x[worker][task]);
    }
    cp_model.AddExactlyOne(tasks);
  }

  // Each team takes at most two tasks.
  LinearExpr team1_tasks;
  for (int worker : team1) {
    for (int task : all_tasks) {
      team1_tasks += x[worker][task];
    }
  }
  cp_model.AddLessOrEqual(team1_tasks, team_max);

  LinearExpr team2_tasks;
  for (int worker : team2) {
    for (int task : all_tasks) {
      team2_tasks += x[worker][task];
    }
  }
  cp_model.AddLessOrEqual(team2_tasks, team_max);

  // Objective
  LinearExpr total_cost;
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      total_cost += x[worker][task] * costs[worker][task];
    }
  }
  cp_model.Minimize(total_cost);

  // Solve
  const CpSolverResponse response = Solve(cp_model.Build());

  // Print solution.
  if (response.status() == CpSolverStatus::INFEASIBLE) {
    LOG(FATAL) << "No solution found.";
  }
  LOG(INFO) << "Total cost: " << response.objective_value();
  LOG(INFO);
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      if (SolutionBooleanValue(response, x[worker][task])) {
        LOG(INFO) << "Worker " << worker << " assigned to task " << task
                  << ".  Cost: " << costs[worker][task];
      }
    }
  }
}
}  // namespace sat
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::sat::AssignmentTeamsSat();
  return EXIT_SUCCESS;
}

جاوا

// CP-SAT example that solves an assignment problem.
package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/** Assignment problem. */
public class AssignmentTeamsSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Data
    int[][] costs = {
        {90, 76, 75, 70},
        {35, 85, 55, 65},
        {125, 95, 90, 105},
        {45, 110, 95, 115},
        {60, 105, 80, 75},
        {45, 65, 110, 95},
    };
    final int numWorkers = costs.length;
    final int numTasks = costs[0].length;

    final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
    final int[] allTasks = IntStream.range(0, numTasks).toArray();

    final int[] team1 = {0, 2, 4};
    final int[] team2 = {1, 3, 5};
    // Maximum total of tasks for any team
    final int teamMax = 2;

    // Model
    CpModel model = new CpModel();

    // Variables
    Literal[][] x = new Literal[numWorkers][numTasks];
    // Variables in a 1-dim array.
    for (int worker : allWorkers) {
      for (int task : allTasks) {
        x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
      }
    }

    // Constraints
    // Each worker is assigned to at most one task.
    for (int worker : allWorkers) {
      List<Literal> tasks = new ArrayList<>();
      for (int task : allTasks) {
        tasks.add(x[worker][task]);
      }
      model.addAtMostOne(tasks);
    }

    // Each task is assigned to exactly one worker.
    for (int task : allTasks) {
      List<Literal> workers = new ArrayList<>();
      for (int worker : allWorkers) {
        workers.add(x[worker][task]);
      }
      model.addExactlyOne(workers);
    }

    // Each team takes at most two tasks.
    LinearExprBuilder team1Tasks = LinearExpr.newBuilder();
    for (int worker : team1) {
      for (int task : allTasks) {
        team1Tasks.add(x[worker][task]);
      }
    }
    model.addLessOrEqual(team1Tasks, teamMax);

    LinearExprBuilder team2Tasks = LinearExpr.newBuilder();
    for (int worker : team2) {
      for (int task : allTasks) {
        team2Tasks.add(x[worker][task]);
      }
    }
    model.addLessOrEqual(team2Tasks, teamMax);

    // Objective
    LinearExprBuilder obj = LinearExpr.newBuilder();
    for (int worker : allWorkers) {
      for (int task : allTasks) {
        obj.addTerm(x[worker][task], costs[worker][task]);
      }
    }
    model.minimize(obj);

    // Solve
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    // Print solution.
    // Check that the problem has a feasible solution.
    if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
      System.out.println("Total cost: " + solver.objectiveValue() + "\n");
      for (int worker : allWorkers) {
        for (int task : allTasks) {
          if (solver.booleanValue(x[worker][task])) {
            System.out.println("Worker " + worker + " assigned to task " + task
                + ".  Cost: " + costs[worker][task]);
          }
        }
      }
    } else {
      System.err.println("No solution found.");
    }
  }

  private AssignmentTeamsSat() {}
}

سی شارپ

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class AssignmentTeamsSat
{
    public static void Main(String[] args)
    {
        // Data.
        int[,] costs = {
            { 90, 76, 75, 70 },   { 35, 85, 55, 65 },  { 125, 95, 90, 105 },
            { 45, 110, 95, 115 }, { 60, 105, 80, 75 }, { 45, 65, 110, 95 },
        };
        int numWorkers = costs.GetLength(0);
        int numTasks = costs.GetLength(1);

        int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
        int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

        int[] team1 = { 0, 2, 4 };
        int[] team2 = { 1, 3, 5 };
        // Maximum total of tasks for any team
        int teamMax = 2;

        // Model.
        CpModel model = new CpModel();

        // Variables.
        BoolVar[,] x = new BoolVar[numWorkers, numTasks];
        foreach (int worker in allWorkers)
        {
            foreach (int task in allTasks)
            {
                x[worker, task] = model.NewBoolVar($"x[{worker},{task}]");
            }
        }

        // Constraints
        // Each worker is assigned to at most one task.
        foreach (int worker in allWorkers)
        {
            List<ILiteral> tasks = new List<ILiteral>();
            foreach (int task in allTasks)
            {
                tasks.Add(x[worker, task]);
            }
            model.AddAtMostOne(tasks);
        }

        // Each task is assigned to exactly one worker.
        foreach (int task in allTasks)
        {
            List<ILiteral> workers = new List<ILiteral>();
            foreach (int worker in allWorkers)
            {
                workers.Add(x[worker, task]);
            }
            model.AddExactlyOne(workers);
        }

        // Each team takes at most two tasks.
        List<IntVar> team1Tasks = new List<IntVar>();
        foreach (int worker in team1)
        {
            foreach (int task in allTasks)
            {
                team1Tasks.Add(x[worker, task]);
            }
        }
        model.Add(LinearExpr.Sum(team1Tasks.ToArray()) <= teamMax);

        List<IntVar> team2Tasks = new List<IntVar>();
        foreach (int worker in team2)
        {
            foreach (int task in allTasks)
            {
                team2Tasks.Add(x[worker, task]);
            }
        }
        model.Add(LinearExpr.Sum(team2Tasks.ToArray()) <= teamMax);

        // Objective
        LinearExprBuilder obj = LinearExpr.NewBuilder();
        foreach (int worker in allWorkers)
        {
            foreach (int task in allTasks)
            {
                obj.AddTerm(x[worker, task], costs[worker, task]);
            }
        }
        model.Minimize(obj);

        // Solve
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);
        Console.WriteLine($"Solve status: {status}");

        // Print solution.
        // Check that the problem has a feasible solution.
        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n");
            foreach (int worker in allWorkers)
            {
                foreach (int task in allTasks)
                {
                    if (solver.Value(x[worker, task]) > 0.5)
                    {
                        Console.WriteLine($"Worker {worker} assigned to task {task}. " +
                                          $"Cost: {costs[worker, task]}");
                    }
                }
            }
        }
        else
        {
            Console.WriteLine("No solution found.");
        }

        Console.WriteLine("Statistics");
        Console.WriteLine($"  - conflicts : {solver.NumConflicts()}");
        Console.WriteLine($"  - branches  : {solver.NumBranches()}");
        Console.WriteLine($"  - wall time : {solver.WallTime()}s");
    }
}

راه حل MIP

در مرحله بعد، ما یک راه حل برای این مشکل انتساب با استفاده از حل کننده MIP شرح می دهیم.

کتابخانه ها را وارد کنید

کد زیر کتابخانه مورد نیاز را وارد می کند.

پایتون

from ortools.linear_solver import pywraplp

C++

#include <cstdint>
#include <memory>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"

جاوا

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import java.util.stream.IntStream;

سی شارپ

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;

داده ها را تعریف کنید

کد زیر داده های برنامه را ایجاد می کند.

پایتون

costs = [
    [90, 76, 75, 70],
    [35, 85, 55, 65],
    [125, 95, 90, 105],
    [45, 110, 95, 115],
    [60, 105, 80, 75],
    [45, 65, 110, 95],
]
num_workers = len(costs)
num_tasks = len(costs[0])

team1 = [0, 2, 4]
team2 = [1, 3, 5]
# Maximum total of tasks for any team
team_max = 2

C++

const std::vector<std::vector<int64_t>> costs = {{
    {{90, 76, 75, 70}},
    {{35, 85, 55, 65}},
    {{125, 95, 90, 105}},
    {{45, 110, 95, 115}},
    {{60, 105, 80, 75}},
    {{45, 65, 110, 95}},
}};
const int num_workers = costs.size();
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = costs[0].size();
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);

const std::vector<int64_t> team1 = {{0, 2, 4}};
const std::vector<int64_t> team2 = {{1, 3, 5}};
// Maximum total of tasks for any team
const int team_max = 2;

جاوا

double[][] costs = {
    {90, 76, 75, 70},
    {35, 85, 55, 65},
    {125, 95, 90, 105},
    {45, 110, 95, 115},
    {60, 105, 80, 75},
    {45, 65, 110, 95},
};
int numWorkers = costs.length;
int numTasks = costs[0].length;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
final int[] allTasks = IntStream.range(0, numTasks).toArray();

final int[] team1 = {0, 2, 4};
final int[] team2 = {1, 3, 5};
// Maximum total of tasks for any team
final int teamMax = 2;

سی شارپ

int[,] costs = {
    { 90, 76, 75, 70 },   { 35, 85, 55, 65 },  { 125, 95, 90, 105 },
    { 45, 110, 95, 115 }, { 60, 105, 80, 75 }, { 45, 65, 110, 95 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

int[] team1 = { 0, 2, 4 };
int[] team2 = { 1, 3, 5 };
// Maximum total of tasks for any team
int teamMax = 2;

حل کننده را اعلام کنید

کد زیر حل کننده را ایجاد می کند.

پایتون

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
    return

C++

// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
  LOG(WARNING) << "SCIP solver unavailable.";
  return;
}

جاوا

// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
  System.out.println("Could not create solver SCIP");
  return;
}

سی شارپ

Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
    return;
}

متغیرها را ایجاد کنید

کد زیر آرایه ای از متغیرها را برای مشکل ایجاد می کند.

پایتون

# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
x = {}
for worker in range(num_workers):
    for task in range(num_tasks):
        x[worker, task] = solver.BoolVar(f"x[{worker},{task}]")

C++

// x[i][j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
std::vector<std::vector<const MPVariable*>> x(
    num_workers, std::vector<const MPVariable*>(num_tasks));
for (int worker : all_workers) {
  for (int task : all_tasks) {
    x[worker][task] =
        solver->MakeBoolVar(absl::StrFormat("x[%d,%d]", worker, task));
  }
}

جاوا

// x[i][j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
MPVariable[][] x = new MPVariable[numWorkers][numTasks];
for (int worker : allWorkers) {
  for (int task : allTasks) {
    x[worker][task] = solver.makeBoolVar("x[" + worker + "," + task + "]");
  }
}

سی شارپ

// x[i, j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
Variable[,] x = new Variable[numWorkers, numTasks];
foreach (int worker in allWorkers)
{
    foreach (int task in allTasks)
    {
        x[worker, task] = solver.MakeBoolVar($"x[{worker},{task}]");
    }
}

محدودیت ها را اضافه کنید

کد زیر محدودیت هایی را برای برنامه ایجاد می کند.

پایتون

# Each worker is assigned at most 1 task.
for worker in range(num_workers):
    solver.Add(solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1)

# Each task is assigned to exactly one worker.
for task in range(num_tasks):
    solver.Add(solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1)

# Each team takes at most two tasks.
team1_tasks = []
for worker in team1:
    for task in range(num_tasks):
        team1_tasks.append(x[worker, task])
solver.Add(solver.Sum(team1_tasks) <= team_max)

team2_tasks = []
for worker in team2:
    for task in range(num_tasks):
        team2_tasks.append(x[worker, task])
solver.Add(solver.Sum(team2_tasks) <= team_max)

C++

// Each worker is assigned to at most one task.
for (int worker : all_workers) {
  LinearExpr worker_sum;
  for (int task : all_tasks) {
    worker_sum += x[worker][task];
  }
  solver->MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int task : all_tasks) {
  LinearExpr task_sum;
  for (int worker : all_workers) {
    task_sum += x[worker][task];
  }
  solver->MakeRowConstraint(task_sum == 1.0);
}

// Each team takes at most two tasks.
LinearExpr team1_tasks;
for (int worker : team1) {
  for (int task : all_tasks) {
    team1_tasks += x[worker][task];
  }
}
solver->MakeRowConstraint(team1_tasks <= team_max);

LinearExpr team2_tasks;
for (int worker : team2) {
  for (int task : all_tasks) {
    team2_tasks += x[worker][task];
  }
}
solver->MakeRowConstraint(team2_tasks <= team_max);

جاوا

// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
  MPConstraint constraint = solver.makeConstraint(0, 1, "");
  for (int task : allTasks) {
    constraint.setCoefficient(x[worker][task], 1);
  }
}
// Each task is assigned to exactly one worker.
for (int task : allTasks) {
  MPConstraint constraint = solver.makeConstraint(1, 1, "");
  for (int worker : allWorkers) {
    constraint.setCoefficient(x[worker][task], 1);
  }
}

// Each team takes at most two tasks.
MPConstraint team1Tasks = solver.makeConstraint(0, teamMax, "");
for (int worker : team1) {
  for (int task : allTasks) {
    team1Tasks.setCoefficient(x[worker][task], 1);
  }
}

MPConstraint team2Tasks = solver.makeConstraint(0, teamMax, "");
for (int worker : team2) {
  for (int task : allTasks) {
    team2Tasks.setCoefficient(x[worker][task], 1);
  }
}

سی شارپ

// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
    Constraint constraint = solver.MakeConstraint(0, 1, "");
    foreach (int task in allTasks)
    {
        constraint.SetCoefficient(x[worker, task], 1);
    }
}
// Each task is assigned to exactly one worker.
foreach (int task in allTasks)
{
    Constraint constraint = solver.MakeConstraint(1, 1, "");
    foreach (int worker in allWorkers)
    {
        constraint.SetCoefficient(x[worker, task], 1);
    }
}

// Each team takes at most two tasks.
Constraint team1Tasks = solver.MakeConstraint(0, teamMax, "");
foreach (int worker in team1)
{
    foreach (int task in allTasks)
    {
        team1Tasks.SetCoefficient(x[worker, task], 1);
    }
}

Constraint team2Tasks = solver.MakeConstraint(0, teamMax, "");
foreach (int worker in team2)
{
    foreach (int task in allTasks)
    {
        team2Tasks.SetCoefficient(x[worker, task], 1);
    }
}

هدف را ایجاد کنید

کد زیر تابع هدف را ایجاد می کند.

پایتون

objective_terms = []
for worker in range(num_workers):
    for task in range(num_tasks):
        objective_terms.append(costs[worker][task] * x[worker, task])
solver.Minimize(solver.Sum(objective_terms))

C++

MPObjective* const objective = solver->MutableObjective();
for (int worker : all_workers) {
  for (int task : all_tasks) {
    objective->SetCoefficient(x[worker][task], costs[worker][task]);
  }
}
objective->SetMinimization();

جاوا

MPObjective objective = solver.objective();
for (int worker : allWorkers) {
  for (int task : allTasks) {
    objective.setCoefficient(x[worker][task], costs[worker][task]);
  }
}
objective.setMinimization();

سی شارپ

Objective objective = solver.Objective();
foreach (int worker in allWorkers)
{
    foreach (int task in allTasks)
    {
        objective.SetCoefficient(x[worker, task], costs[worker, task]);
    }
}
objective.SetMinimization();

حل کننده را فراخوانی کنید

کد زیر حل کننده را فراخوانی می کند و نتایج را نمایش می دهد.

پایتون

print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()

C++

const MPSolver::ResultStatus result_status = solver->Solve();

جاوا

MPSolver.ResultStatus resultStatus = solver.solve();

سی شارپ

Solver.ResultStatus resultStatus = solver.Solve();

نمایش نتایج

اکنون می توانیم راه حل را چاپ کنیم.

پایتون

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print(f"Total cost = {solver.Objective().Value()}\n")
    for worker in range(num_workers):
        for task in range(num_tasks):
            if x[worker, task].solution_value() > 0.5:
                print(
                    f"Worker {worker} assigned to task {task}."
                    + f" Cost = {costs[worker][task]}"
                )
else:
    print("No solution found.")
print(f"Time = {solver.WallTime()} ms")

C++

// Check that the problem has a feasible solution.
if (result_status != MPSolver::OPTIMAL &&
    result_status != MPSolver::FEASIBLE) {
  LOG(FATAL) << "No solution found.";
}
LOG(INFO) << "Total cost = " << objective->Value() << "\n\n";
for (int worker : all_workers) {
  for (int task : all_tasks) {
    // Test if x[i][j] is 0 or 1 (with tolerance for floating point
    // arithmetic).
    if (x[worker][task]->solution_value() > 0.5) {
      LOG(INFO) << "Worker " << worker << " assigned to task " << task
                << ".  Cost: " << costs[worker][task];
    }
  }
}

جاوا

// Check that the problem has a feasible solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL
    || resultStatus == MPSolver.ResultStatus.FEASIBLE) {
  System.out.println("Total cost: " + objective.value() + "\n");
  for (int worker : allWorkers) {
    for (int task : allTasks) {
      // Test if x[i][j] is 0 or 1 (with tolerance for floating point
      // arithmetic).
      if (x[worker][task].solutionValue() > 0.5) {
        System.out.println("Worker " + worker + " assigned to task " + task
            + ".  Cost: " + costs[worker][task]);
      }
    }
  }
} else {
  System.err.println("No solution found.");
}

سی شارپ

// Check that the problem has a feasible solution.
if (resultStatus == Solver.ResultStatus.OPTIMAL || resultStatus == Solver.ResultStatus.FEASIBLE)
{
    Console.WriteLine($"Total cost: {solver.Objective().Value()}\n");
    foreach (int worker in allWorkers)
    {
        foreach (int task in allTasks)
        {
            // Test if x[i, j] is 0 or 1 (with tolerance for floating point
            // arithmetic).
            if (x[worker, task].SolutionValue() > 0.5)
            {
                Console.WriteLine($"Worker {worker} assigned to task {task}. Cost: {costs[worker, task]}");
            }
        }
    }
}
else
{
    Console.WriteLine("No solution found.");
}

اینم خروجی برنامه

Minimum cost assignment:  250.0
Worker 0 assigned to task 2. Cost = 75
Worker 1 assigned to task 0. Cost = 35
Worker 4 assigned to task 3. Cost = 75
Worker 5 assigned to task 1. Cost = 65
Time =  6  milliseconds

کل برنامه

در اینجا کل برنامه است.

پایتون

"""MIP example that solves an assignment problem."""
from ortools.linear_solver import pywraplp


def main():
    # Data
    costs = [
        [90, 76, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 105],
        [45, 110, 95, 115],
        [60, 105, 80, 75],
        [45, 65, 110, 95],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    team1 = [0, 2, 4]
    team2 = [1, 3, 5]
    # Maximum total of tasks for any team
    team_max = 2

    # Solver
    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver("SCIP")
    if not solver:
        return

    # Variables
    # x[i, j] is an array of 0-1 variables, which will be 1
    # if worker i is assigned to task j.
    x = {}
    for worker in range(num_workers):
        for task in range(num_tasks):
            x[worker, task] = solver.BoolVar(f"x[{worker},{task}]")

    # Constraints
    # Each worker is assigned at most 1 task.
    for worker in range(num_workers):
        solver.Add(solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1)

    # Each task is assigned to exactly one worker.
    for task in range(num_tasks):
        solver.Add(solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1)

    # Each team takes at most two tasks.
    team1_tasks = []
    for worker in team1:
        for task in range(num_tasks):
            team1_tasks.append(x[worker, task])
    solver.Add(solver.Sum(team1_tasks) <= team_max)

    team2_tasks = []
    for worker in team2:
        for task in range(num_tasks):
            team2_tasks.append(x[worker, task])
    solver.Add(solver.Sum(team2_tasks) <= team_max)

    # Objective
    objective_terms = []
    for worker in range(num_workers):
        for task in range(num_tasks):
            objective_terms.append(costs[worker][task] * x[worker, task])
    solver.Minimize(solver.Sum(objective_terms))

    # Solve
    print(f"Solving with {solver.SolverVersion()}")
    status = solver.Solve()

    # Print solution.
    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
        print(f"Total cost = {solver.Objective().Value()}\n")
        for worker in range(num_workers):
            for task in range(num_tasks):
                if x[worker, task].solution_value() > 0.5:
                    print(
                        f"Worker {worker} assigned to task {task}."
                        + f" Cost = {costs[worker][task]}"
                    )
    else:
        print("No solution found.")
    print(f"Time = {solver.WallTime()} ms")


if __name__ == "__main__":
    main()

C++

// Solve a simple assignment problem.
#include <cstdint>
#include <memory>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void AssignmentTeamsMip() {
  // Data
  const std::vector<std::vector<int64_t>> costs = {{
      {{90, 76, 75, 70}},
      {{35, 85, 55, 65}},
      {{125, 95, 90, 105}},
      {{45, 110, 95, 115}},
      {{60, 105, 80, 75}},
      {{45, 65, 110, 95}},
  }};
  const int num_workers = costs.size();
  std::vector<int> all_workers(num_workers);
  std::iota(all_workers.begin(), all_workers.end(), 0);

  const int num_tasks = costs[0].size();
  std::vector<int> all_tasks(num_tasks);
  std::iota(all_tasks.begin(), all_tasks.end(), 0);

  const std::vector<int64_t> team1 = {{0, 2, 4}};
  const std::vector<int64_t> team2 = {{1, 3, 5}};
  // Maximum total of tasks for any team
  const int team_max = 2;

  // Solver
  // Create the mip solver with the SCIP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

  // Variables
  // x[i][j] is an array of 0-1 variables, which will be 1
  // if worker i is assigned to task j.
  std::vector<std::vector<const MPVariable*>> x(
      num_workers, std::vector<const MPVariable*>(num_tasks));
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      x[worker][task] =
          solver->MakeBoolVar(absl::StrFormat("x[%d,%d]", worker, task));
    }
  }

  // Constraints
  // Each worker is assigned to at most one task.
  for (int worker : all_workers) {
    LinearExpr worker_sum;
    for (int task : all_tasks) {
      worker_sum += x[worker][task];
    }
    solver->MakeRowConstraint(worker_sum <= 1.0);
  }
  // Each task is assigned to exactly one worker.
  for (int task : all_tasks) {
    LinearExpr task_sum;
    for (int worker : all_workers) {
      task_sum += x[worker][task];
    }
    solver->MakeRowConstraint(task_sum == 1.0);
  }

  // Each team takes at most two tasks.
  LinearExpr team1_tasks;
  for (int worker : team1) {
    for (int task : all_tasks) {
      team1_tasks += x[worker][task];
    }
  }
  solver->MakeRowConstraint(team1_tasks <= team_max);

  LinearExpr team2_tasks;
  for (int worker : team2) {
    for (int task : all_tasks) {
      team2_tasks += x[worker][task];
    }
  }
  solver->MakeRowConstraint(team2_tasks <= team_max);

  // Objective.
  MPObjective* const objective = solver->MutableObjective();
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      objective->SetCoefficient(x[worker][task], costs[worker][task]);
    }
  }
  objective->SetMinimization();

  // Solve
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Print solution.
  // Check that the problem has a feasible solution.
  if (result_status != MPSolver::OPTIMAL &&
      result_status != MPSolver::FEASIBLE) {
    LOG(FATAL) << "No solution found.";
  }
  LOG(INFO) << "Total cost = " << objective->Value() << "\n\n";
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      // Test if x[i][j] is 0 or 1 (with tolerance for floating point
      // arithmetic).
      if (x[worker][task]->solution_value() > 0.5) {
        LOG(INFO) << "Worker " << worker << " assigned to task " << task
                  << ".  Cost: " << costs[worker][task];
      }
    }
  }
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::AssignmentTeamsMip();
  return EXIT_SUCCESS;
}

جاوا

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import java.util.stream.IntStream;

/** MIP example that solves an assignment problem. */
public class AssignmentTeamsMip {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Data
    double[][] costs = {
        {90, 76, 75, 70},
        {35, 85, 55, 65},
        {125, 95, 90, 105},
        {45, 110, 95, 115},
        {60, 105, 80, 75},
        {45, 65, 110, 95},
    };
    int numWorkers = costs.length;
    int numTasks = costs[0].length;

    final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
    final int[] allTasks = IntStream.range(0, numTasks).toArray();

    final int[] team1 = {0, 2, 4};
    final int[] team2 = {1, 3, 5};
    // Maximum total of tasks for any team
    final int teamMax = 2;

    // Solver
    // Create the linear solver with the SCIP backend.
    MPSolver solver = MPSolver.createSolver("SCIP");
    if (solver == null) {
      System.out.println("Could not create solver SCIP");
      return;
    }

    // Variables
    // x[i][j] is an array of 0-1 variables, which will be 1
    // if worker i is assigned to task j.
    MPVariable[][] x = new MPVariable[numWorkers][numTasks];
    for (int worker : allWorkers) {
      for (int task : allTasks) {
        x[worker][task] = solver.makeBoolVar("x[" + worker + "," + task + "]");
      }
    }

    // Constraints
    // Each worker is assigned to at most one task.
    for (int worker : allWorkers) {
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      for (int task : allTasks) {
        constraint.setCoefficient(x[worker][task], 1);
      }
    }
    // Each task is assigned to exactly one worker.
    for (int task : allTasks) {
      MPConstraint constraint = solver.makeConstraint(1, 1, "");
      for (int worker : allWorkers) {
        constraint.setCoefficient(x[worker][task], 1);
      }
    }

    // Each team takes at most two tasks.
    MPConstraint team1Tasks = solver.makeConstraint(0, teamMax, "");
    for (int worker : team1) {
      for (int task : allTasks) {
        team1Tasks.setCoefficient(x[worker][task], 1);
      }
    }

    MPConstraint team2Tasks = solver.makeConstraint(0, teamMax, "");
    for (int worker : team2) {
      for (int task : allTasks) {
        team2Tasks.setCoefficient(x[worker][task], 1);
      }
    }

    // Objective
    MPObjective objective = solver.objective();
    for (int worker : allWorkers) {
      for (int task : allTasks) {
        objective.setCoefficient(x[worker][task], costs[worker][task]);
      }
    }
    objective.setMinimization();

    // Solve
    MPSolver.ResultStatus resultStatus = solver.solve();

    // Print solution.
    // Check that the problem has a feasible solution.
    if (resultStatus == MPSolver.ResultStatus.OPTIMAL
        || resultStatus == MPSolver.ResultStatus.FEASIBLE) {
      System.out.println("Total cost: " + objective.value() + "\n");
      for (int worker : allWorkers) {
        for (int task : allTasks) {
          // Test if x[i][j] is 0 or 1 (with tolerance for floating point
          // arithmetic).
          if (x[worker][task].solutionValue() > 0.5) {
            System.out.println("Worker " + worker + " assigned to task " + task
                + ".  Cost: " + costs[worker][task]);
          }
        }
      }
    } else {
      System.err.println("No solution found.");
    }
  }

  private AssignmentTeamsMip() {}
}

سی شارپ

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;

public class AssignmentTeamsMip
{
    static void Main()
    {
        // Data.
        int[,] costs = {
            { 90, 76, 75, 70 },   { 35, 85, 55, 65 },  { 125, 95, 90, 105 },
            { 45, 110, 95, 115 }, { 60, 105, 80, 75 }, { 45, 65, 110, 95 },
        };
        int numWorkers = costs.GetLength(0);
        int numTasks = costs.GetLength(1);

        int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
        int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

        int[] team1 = { 0, 2, 4 };
        int[] team2 = { 1, 3, 5 };
        // Maximum total of tasks for any team
        int teamMax = 2;

        // Solver.
        Solver solver = Solver.CreateSolver("SCIP");
        if (solver is null)
        {
            return;
        }

        // Variables.
        // x[i, j] is an array of 0-1 variables, which will be 1
        // if worker i is assigned to task j.
        Variable[,] x = new Variable[numWorkers, numTasks];
        foreach (int worker in allWorkers)
        {
            foreach (int task in allTasks)
            {
                x[worker, task] = solver.MakeBoolVar($"x[{worker},{task}]");
            }
        }

        // Constraints
        // Each worker is assigned to at most one task.
        foreach (int worker in allWorkers)
        {
            Constraint constraint = solver.MakeConstraint(0, 1, "");
            foreach (int task in allTasks)
            {
                constraint.SetCoefficient(x[worker, task], 1);
            }
        }
        // Each task is assigned to exactly one worker.
        foreach (int task in allTasks)
        {
            Constraint constraint = solver.MakeConstraint(1, 1, "");
            foreach (int worker in allWorkers)
            {
                constraint.SetCoefficient(x[worker, task], 1);
            }
        }

        // Each team takes at most two tasks.
        Constraint team1Tasks = solver.MakeConstraint(0, teamMax, "");
        foreach (int worker in team1)
        {
            foreach (int task in allTasks)
            {
                team1Tasks.SetCoefficient(x[worker, task], 1);
            }
        }

        Constraint team2Tasks = solver.MakeConstraint(0, teamMax, "");
        foreach (int worker in team2)
        {
            foreach (int task in allTasks)
            {
                team2Tasks.SetCoefficient(x[worker, task], 1);
            }
        }

        // Objective
        Objective objective = solver.Objective();
        foreach (int worker in allWorkers)
        {
            foreach (int task in allTasks)
            {
                objective.SetCoefficient(x[worker, task], costs[worker, task]);
            }
        }
        objective.SetMinimization();

        // Solve
        Solver.ResultStatus resultStatus = solver.Solve();

        // Print solution.
        // Check that the problem has a feasible solution.
        if (resultStatus == Solver.ResultStatus.OPTIMAL || resultStatus == Solver.ResultStatus.FEASIBLE)
        {
            Console.WriteLine($"Total cost: {solver.Objective().Value()}\n");
            foreach (int worker in allWorkers)
            {
                foreach (int task in allTasks)
                {
                    // Test if x[i, j] is 0 or 1 (with tolerance for floating point
                    // arithmetic).
                    if (x[worker, task].SolutionValue() > 0.5)
                    {
                        Console.WriteLine($"Worker {worker} assigned to task {task}. Cost: {costs[worker, task]}");
                    }
                }
            }
        }
        else
        {
            Console.WriteLine("No solution found.");
        }
    }
}