用lingo求解0-1规划问题

用Lingo求解0-1规划问题的步骤与示例

一、0-1规划问题定义

0-1规划是整数规划的特殊形式，其决策变量仅能取0或1（即(x_i \in {0,1})），主要用于描述“是/否”“选/不选”“开/关”等逻辑关系，常见于指派问题、背包问题、生产计划安排等场景。

二、Lingo求解0-1规划的核心语法

Lingo中通过@bin()函数限制变量为0-1类型，其基本语法结构如下：

model:

! 目标函数（最大化/最小化）;

max = ... 或 min = ...;



! 约束条件（等式/不等式）;

constraint1;

constraint2;

...



! 变量定义（0-1约束）;

@bin(x1); @bin(x2); ... @bin(xn);

end

注：Lingo默认变量取值范围为非负实数（(x \geq 0)），@bin()函数用于强制变量取0或

三、典型示例演示

示例1：基础0-1规划问题

问题描述：

最大化目标函数 (z = 2x_1 + 5x_2 + 3x_3 + 4x_4)，约束条件为：

[

\begin{cases}

-4x_1 + x_2 + x_3 + x_4 \geq 0 \

-2x_1 + 4x_2 + 2x_3 + 4x_4 \geq 1 \

x_1 + x_2 - x_3 + x_4 \geq 1 \

x_1, x_2, x_3, x_4 \in {0,1}


\end{cases}

]

Lingo程序：

max = 2*x1 + 5*x2 + 3*x3 + 4*x4;

-4*x1 + x2 + x3 + x4 >= 0;

-2*x1 + 4*x2 + 2*x3 + 4*x4 >= 1;

x1 + x2 - x3 + x4 >= 1;

@bin(x1); @bin(x2); @bin(x3); @bin(x4);

说明：通过@bin()函数将(x_1)至(x_4)限制为0-1变量，直接求解满足约束的最大值。

示例2：指派问题（标准0-1规划）

问题描述：

某游泳队拟选4名运动员（A、B、C、D）组成4×100m混合泳接力队，每位运动员游不同姿势（自由泳、蛙泳、蝶泳、仰泳）的成绩如下表（单位：秒）。求每位运动员游1种姿势的方案，使总时间最小。

运动员 自由泳 蛙泳 蝶泳 仰泳

A 56 74 61

B 63 69 65

C 57 77 63

D 55 76 62

Lingo程序：

model:

sets:

athletes /A,B,C,D/;

strokes /Free, Breast, Fly, Back/;

link(athletes, strokes): time, assign;

endsets



data:

time = 56 74 61 63,

63 69 65 71,

57 77 63 67,

55 76 62 62;

enddata



! 目标：最小化总时间;

min = @sum(link: time * assign);



! 约束1：每位运动员只游1种姿势;

@for(athletes(i): @sum(strokes(j): assign(i,j)) = 1);



! 约束2：每种姿势只能由1位运动员游;

@for(strokes(j): @sum(athletes(i): assign(i,j)) = 1);



! 约束3：assign为0-1变量;

@for(link: @bin(assign));

end

说明：

使用集合（sets）定义运动员（athletes）和姿势（strokes），通过link集合关联两者；

数据段（data）输入成绩矩阵；

约束1确保每位运动员仅分配1种姿势，约束2确保每种姿势仅由1位运动员负责；

@bin(assign)强制assign变量为0-1（选或不选）。

四、注意事项

变量类型区分：

若变量为纯整数（非0-1），用@gin()函数（如(x \in \mathbb{Z}^+)）；

若变量为0-1，必须用@bin()函数。

默认值处理：

Lingo默认变量(x \geq 0)，若需允许负数，需用@free(x)函数（如(x \in \mathbb{R})）。

模型规模：

0-1规划的变量数量过多（如超过100个）时，求解时间会显著增加，需考虑模型简化或启发式算法。

通过上述步骤，可快速用Lingo求解0-1规划问题。关键是正确使用@bin()函数定义变量，并准确翻译实际问题的目标函数与约束条件。