如何优化多项目投标分配的低效MATLAB函数？

现有场景：c家企业竞标p个项目，需选中使客户总成本最低的中标方，且每家企业最多中标2个项目。以下是我编写的MATLAB代码，代码可运行但效率极低、耗时极长，请求优化：

function FINANCIAL_RESULTS
clear all; clc;
%This Matlab Program aims to select a large number of random combinations,
%filter those with more than two allocations per firm, and select the
%lowest price.

%number of companies
c = 7;

%number of projects
p = 9;

%max number of projects per company
lim = 2;

%upper and lower random limits
a = 1;
b = c;

%Results Matrix: each row represents the bidding price of one firm on all projects
Results = [382200,444050,725200,279250,750800,190200,528150,297700,297700;339040,393420,649520,243960,695760,157960,454550,259700,256980;388032,499002,721216,9999999,773184,204114,512148,293608,300934;385220,453130,737860,287480,9999999,188960,506690,274260,285670;351600,9999999,9999999,276150,722400,9999999,484150,266000,281400;404776,476444,722540,311634,778424,210776,521520,413130,442160;333400,403810,614720,232200,656140,165660,9999999,274180,274180];

Output = zeros(1,p+1);

n=1;
i=1;
for i = 1:10000000
    rndm = round(a + (b-a).*rand(1,p));
    %random checker with the criteria (max 2 allocations)
    Check = tabulate(rndm);
    if max(Check(:,2)) > lim
        continue
    end
    
    
    
    Output(n,1:end-1) = rndm;
    %Cumulative addition of random results
    for k = 1:p
        Output(n,end) = Output(n,end) + Results(rndm(k),k);
    end
    
    n = n+1;    
  
end

disp(Results);
[Min_pay,Indx] = min(Output(:,end));
disp(Output(Indx,:));

%You know the program is done when Handel plays
load handel
sound(y,Fs);
%Done !
end

优化方案 #

核心问题分析 #

原代码采用随机枚举碰运气的思路，不仅效率极低（要循环千万次），更关键的是无法保证找到全局最优解——最终得到的只是某次随机尝试里的次优结果，完全不符合"选总成本最低中标方"的核心需求。正确的解法是将问题转化为整数线性规划问题，直接精确求解全局最优。

具体优化实现 #

1. 数学建模

将问题转化为0-1整数规划：

• 决策变量：x(i,j)，当企业i中标项目j时取1，否则取0
• 目标函数：最小化总成本 min sum_{i=1到c} sum_{j=1到p} Results(i,j)*x(i,j)
• 约束条件：
  • 每个项目必须分配给一家企业：对每个项目j，sum_{i=1到c} x(i,j) = 1
  • 每家企业最多中标2个项目：对每个企业i，sum_{j=1到p} x(i,j) ≤ 2

2. 优化后代码

function FINANCIAL_RESULTS_OPTIMIZED
clear all; clc;

% 参数定义
c = 7;          % 企业数量
p = 9;          % 项目数量
max_projects_per_firm = 2;  % 每家企业最多中标项目数

% 投标价格矩阵：行=企业，列=项目
Results = [382200,444050,725200,279250,750800,190200,528150,297700,297700;
           339040,393420,649520,243960,695760,157960,454550,259700,256980;
           388032,499002,721216,9999999,773184,204114,512148,293608,300934;
           385220,453130,737860,287480,9999999,188960,506690,274260,285670;
           351600,9999999,9999999,276150,722400,9999999,484150,266000,281400;
           404776,476444,722540,311634,778424,210776,521520,413130,442160;
           333400,403810,614720,232200,656140,165660,9999999,274180,274180];

% 1. 构建整数线性规划的输入参数
% 目标函数系数：把Results矩阵展成一维向量
f = Results(:);
% 变量数量：c*p个0-1变量
num_vars = c * p;

% 2. 约束条件1：每个项目必须分配给一家企业（共p个约束）
A_eq1 = kron(eye(p), ones(1, c));
b_eq1 = ones(p, 1);

% 3. 约束条件2：每家企业最多中标max_projects_per_firm个项目（共c个约束）
A_ub2 = kron(ones(1, p), eye(c));
b_ub2 = max_projects_per_firm * ones(c, 1);

% 4. 变量类型：所有变量都是0-1整数
intcon = 1:num_vars;
lb = zeros(num_vars, 1);
ub = ones(num_vars, 1);

% 5. 调用intlinprog求解
options = optimoptions('intlinprog', 'Display', 'iter');
[x_opt, fval_opt, exitflag, output] = intlinprog(f, intcon, A_ub2, b_ub2, A_eq1, b_eq1, lb, ub, options);

% 6. 格式化输出结果
x_opt_matrix = reshape(x_opt, c, p);
disp('最优分配方案（行=企业，列=项目，1表示中标）：');
disp(x_opt_matrix);

disp(['最低总成本：', num2str(fval_opt)]);

% 输出每个企业中标的项目
disp('各企业中标项目列表：');
for i = 1:c
    projects = find(x_opt_matrix(i, :) == 1);
    if ~isempty(projects)
        fprintf('企业%d：项目%s\n', i, num2str(projects));
    else
        fprintf('企业%d：未中标任何项目\n', i);
    end
end

% 播放提示音
load handel
sound(y,Fs);
end

优化效果说明 #

• 效率：从千万次循环的随机枚举，变为线性规划求解，耗时从分钟级压缩到毫秒级
• 准确性：确保找到全局最优解，而不是随机碰出来的次优结果
• 可扩展性：当企业数c或项目数p增大时，依然能高效求解，原随机枚举法则会完全失效

内容的提问来源于stack exchange，提问作者ABD10