(Python)Gurobi求解多目标指派问题

问题描述:

工厂需要把 N 份工作分配给 N 个工人,每份工作只能由一个工人做,且每个工人也只能做一份工作。假设工人 i i i 处理工作 j j j 需要的时间是 T i j T_{ij} Tij​ ,创造的利润是 C i j C_{ij} Cij​,那么需要如何安排才能使总耗时最小且总利润最大?

代码:

import gurobipy as gp
from gurobipy import GRB
import numpy as np

N = 10  # Set the number of workers and jobs
np.random.seed(1234)  # To generate the same data each time

# Generate the time and cost data using the dict
# An index i corresponds to a worker
# An index j corresponds to a job
T = {(i, j): np.random.randint(0, 100) for i in range(N) for j in range(N)}
C = {(i, j): np.random.randint(0, 100) for i in range(N) for j in range(N)}

# Establish the model
m = gp.Model('Assignment_problem_with_multiple_objectives')

# Add decision variables
x = m.addVars(T.keys(), vtype=GRB.BINARY, name='x')

# Add constraints
m.addConstrs((x.sum(i, '*') == 1 for i in range(N)), 'Constraint_of_worker')
m.addConstrs((x.sum('*', j) == 1 for j in range(N)), 'Constraint_of_job')

m.setObjectiveN(x.prod(T), index=0, priority=1, abstol=0, reltol=0, name='minimize_time')
m.setObjectiveN(-x.prod(C), index=1, priority=2, abstol=100, reltol=0, name='maximize_profit')

# Solve the model
m.optimize()

# Display the results
print('*' * 60)
for i in T.keys():
    if x[i].x > 0.9:
        print("The job %d is allocated to the worker %d" % (i[1]+1, i[0]+1))

print("\nThe objective function values are:")
print('Obj1: the total time is: {}'.format(m.ObjNVal))
m.setParam(GRB.Param.ObjNumber, 1)
print('Obj2: the total profit is: {}'.format(-m.ObjNVal))

控制台输出结果:

Using license file C:\Users\86158\gurobi.lic
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 20 rows, 100 columns and 200 nonzeros
Model fingerprint: 0x65ad441f
Variable types: 0 continuous, 100 integer (100 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+02]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]

---------------------------------------------------------------------------
Multi-objectives: starting optimization with 2 objectives ... 
---------------------------------------------------------------------------

Multi-objectives: applying initial presolve ...
---------------------------------------------------------------------------

Presolve time: 0.02s
Presolved: 20 rows and 100 columns
---------------------------------------------------------------------------

Multi-objectives: optimize objective 1 (maximize_profit) ...
---------------------------------------------------------------------------

Found heuristic solution: objective -424.0000000
Presolve time: 0.00s
Presolved: 20 rows, 100 columns, 200 nonzeros
Variable types: 0 continuous, 100 integer (100 binary)

Root relaxation: objective -8.630000e+02, 18 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    -863.0000000 -863.00000  0.00%     -    0s

Explored 0 nodes (18 simplex iterations) in 0.02 seconds
Thread count was 8 (of 8 available processors)

Solution count 2: -863 -424 
No other solutions better than -863

Optimal solution found (tolerance 1.00e-04)
Best objective -8.630000000000e+02, best bound -8.630000000000e+02, gap 0.0000%
---------------------------------------------------------------------------

Multi-objectives: optimize objective 2 (minimize_time) ...
---------------------------------------------------------------------------


Loaded user MIP start with objective 687

Presolve time: 0.00s
Presolved: 21 rows, 100 columns, 288 nonzeros
Variable types: 0 continuous, 100 integer (100 binary)

Root relaxation: objective 3.596170e+02, 30 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  359.61702    0   12  687.00000  359.61702  47.7%     -    0s
H    0     0                     396.0000000  359.61702  9.19%     -    0s
H    0     0                     373.0000000  359.61702  3.59%     -    0s

Cutting planes:
  Gomory: 1

Explored 1 nodes (30 simplex iterations) in 0.02 seconds
Thread count was 8 (of 8 available processors)

Solution count 3: 373 396 687 

Optimal solution found (tolerance 1.00e-04)
Best objective 3.730000000000e+02, best bound 3.730000000000e+02, gap 0.0000%

---------------------------------------------------------------------------
Multi-objectives: solved in 0.03 seconds, solution count 4

************************************************************
The job 8 is allocated to the worker 1
The job 10 is allocated to the worker 2
The job 9 is allocated to the worker 3
The job 3 is allocated to the worker 4
The job 2 is allocated to the worker 5
The job 4 is allocated to the worker 6
The job 5 is allocated to the worker 7
The job 7 is allocated to the worker 8
The job 1 is allocated to the worker 9
The job 6 is allocated to the worker 10

The objective function values are:
Obj1: the total time is: 373.0
Obj2: the total profit is: 768.0

Process finished with exit code 0

上一篇:Objective-C 之父去世,他推动了苹果软件生态的发展


下一篇:闲聊Objective-C中的weak