0-1整数线性规划
引入0-1变量的实际问题
更多的是站在数学建模的角度讨论
整数几何意义：当我们有了“0”和“1”的时候，其他整数就很容易被我们创造出来了，这个创造的方法在几何上叫平移
决策变量
x i = { 0 1 ⟺ x i ≤ 1 , x 1 ≥ 0 , x i ∈ Z ⟺ x i = 0 或 1 x_i=\left\{\begin{array}{c}0\\1\end{array}\right. \Longleftrightarrow x_i\le 1,x_1\ge 0,x_i\in Z \Longleftrightarrow x_i=0\text{或}1xi={01⟺xi≤1,x1≥0,xi∈Z⟺xi=0或1
注：如果变量x i x_ixi不是仅取值0或1，而是可取其他范围的非负整数，这时可利用二进制的计数法将它用若干个0-1变量来代替。相互排斥的计划
引入0-1变量x i x_ixi
x i = { 1 , 当 A i 点被选用 0 , 当 A i 点没被选用 , i = 1 , 2 , ⋯ , 7 x_i=\left\{\begin{array}{c}1,\text{当}A_i\text{点被选用}\\0,\text{当}A_i\text{点没被选用}\end{array}\right. ,~i=1,2,\cdots,7xi={1,当Ai点被选用0,当Ai点没被选用, i=1,2,⋯,7
注：难点往往是选择合适的决策变量，为什么要选择0-1变量目标函数
max z = c 1 x 1 + c 2 x 2 + ⋯ + c 7 x 7 = ∑ i = 1 7 c i x i \max z=c_1x_1+c_2x_2+\cdots+c_7x_7=\sum\limits_{i=1}^7c_ix_imaxz=c1x1+c2x2+⋯+c7x7=i=1∑7cixi
注：对于x i x_ixi来说选与不选用x i x_ixi来表示。如果选了A i , x i = 1 A_i,~x_i=1Ai, xi=1，此时利润为1 ⋅ c i 1\cdot c_i1⋅ci；如果没选A i , x i = 0 A_i,~x_i=0Ai, xi=0，此时利润为0 ⋅ c i 0\cdot c_i0⋅ci，但我们用整体视角去看上述两种情况时，不难发现，无论选择或不选择A i A_iAi，利润直接表示为x i c i x_ic_ixici即可约束方程
{ ∑ i = 1 7 b i x i ≤ B x 1 + x 2 + x 3 ≤ 2 x 4 + x 5 ≥ 1 x 6 + x 7 ≥ 1 x i = 0 或 1 \left\{\begin{array}{c} \sum\limits_{i=1}^7b_ix_i\le B\\ x_1+x_2+x_3\le 2\\ x_4+x_5\ge 1\\ x_6+x_7\ge 1\\ x_i=0~\text{或}~1 \end{array}\right.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧i=1∑7bixi≤Bx1+x2+x3≤2x4+x5≥1x6+x7≥1xi=0 或 1
注：方程2可以抽象为：在A 1 , A 2 , ⋯ , A n A_1,A_2,\cdots,A_nA1,A2,⋯,An中至多选M MM个⇒ \Rightarrow⇒x 1 + x 2 + ⋯ + x n ≤ M x_1+x_2+\cdots+x_n\le Mx1+x2+⋯+xn≤M
相互排斥的约束项
现公司需要运输货物，考虑使用集装箱，集装箱分甲乙两个型号，甲的容量为5 m 3 / 箱 5m^3/\text{箱}5m3/箱，乙的容量为4 m 3 / 箱 4m^3/\text{箱}4m3/箱，且甲乙两个型号只能车运，且车运限制为24 m 3 24m^324m3. 现有人提出了另一个方案，使用船运，在船运时，甲的容量可调整为7 m 3 / 箱 7m^3/\text{箱}7m3/箱，但乙的容量须调整为3 m 3 / 箱 3m^3/\text{箱}3m3/箱，船运上限为45 m 3 45m^345m3。另外，选择了车运就不能船运，反之亦然。
不妨设x 1 x_1x1个甲，x 2 x_2x2个乙，则有
车运： 5 x 1 + 4 x 2 ≤ 24 船运： 7 x 1 + 3 x 2 ≤ 45 \text{车运：}5x_1+4x_2\le 24\\ \text{船运：}7x_1+3x_2\le 45车运：5x1+4x2≤24船运：7x1+3x2≤45
注：车运和船运只能二选一，因此两个约束条件是互斥的，不能同时发生。如果写在同一个方程组中则是同时生效的。考虑引入0-1变量，但之后如何处理是难题引入0-1变量y yy，令
y = { 0 , 用车运 1 , 用船运 y=\left\{\begin{array}{c}0,\text{用车运}\\1,\text{用船运}\end{array}\right.y={0,用车运1,用船运约束方程（细品）
{ 5 x 1 + 4 x 2 ≤ 24 + y M 7 x 1 + 3 x 2 ≤ 45 + ( 1 − y ) M , M 是充分大的数 \left\{\begin{array}{c} 5x_1+4x_2\le 24+yM\\ 7x_1+3x_2\le 45+(1-y)M \end{array}\right. ,~M\text{是充分大的数}{5x1+4x2≤24+yM7x1+3x2≤45+(1−y)M, M是充分大的数
注：引入大M可以使部分约束失效注：如果有m mm个约束条件相互排斥，则引入m mm个0-1变量y i , i = 1 , ⋯ , m y_i,i=1,\cdots,myi,i=1,⋯,m和一个充分大的数M MM，并把原约束写成如下形式
{ a 11 x 1 + a 12 x 2 + ⋯ a 1 n x n ≤ b 1 + y 1 M a 21 x 1 + a 22 x 2 + ⋯ a 2 n x n ≤ b 2 + y 2 M ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ a m n x n ≤ b m + y 2 M y 1 + u 2 + ⋯ + y m = m − 1 \left\{\begin{array}{lcl} a_{11}x_1+a_{12}x_2+\cdots a_{1n}x_n&\le& b_1+y_1M\\ a_{21}x_1+a_{22}x_2+\cdots a_{2n}x_n&\le& b_2+y_2M\\ &\vdots&\\ a_{m1}x_1+a_{m2}x_2+\cdots a_{mn}x_n&\le& b_m+y_2M\\ y_1+u_2+\cdots+y_m&=&m-1 \end{array}\right.⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧a11x1+a12x2+⋯a1nxna21x1+a22x2+⋯a2nxnam1x1+am2x2+⋯amnxny1+u2+⋯+ym≤≤⋮≤=b1+y1Mb2+y2Mbm+y2Mm−1
注：对于y i ( i = 1 , ⋯ , m ) y_i(i=1,\cdots,m)yi(i=1,⋯,m)来说一定要求y 1 + y 2 + ⋯ + y m = m − 1 y_1+y_2+\cdots+y_m=m-1y1+y2+⋯+ym=m−1，且当y i = 0 y_i=0yi=0时，相应的约束才生效
关于固定费用的问题
某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定投资高的生产方式，每件产品的变动成本就降低；如选定投资低的生产方式，每件产品的变动成本可能增加。设有三种方式可供选择。令x j x_jxj表示第j jj种方式时的产量；c j c_jcj表示采用第j jj种方式时每件产品的变动成本；k j k_jkj表示采用第j jj种方式时的固定成本（j = 1 , 2 , 3 j=1,2,3j=1,2,3）
首先可以列出不同投资方式的成本
P j = { k j + c j x j , x j > 0 0 , x j = 0 , j = 1 , 2 , 3 P_j=\left\{\begin{array}{lcl}k_j+c_jx_j&,&x_j>0\\0&,&x_j=0\end{array}\right.,~j=1,2,3Pj={kj+cjxj0,,xj>0xj=0, j=1,2,3目标函数，使总投入最小。引入0-1变量y j y_jyj
y j = { 1 , 当采用第 j 种生产方式，即 x j > 0 0 , 当不采用第 j 种生产方式，即 x j = 0 y_j=\left\{\begin{array}{c}1,\text{当采用第}j\text{种生产方式，即}x_j>0\\0,\text{当不采用第}j\text{种生产方式，即}x_j=0\end{array}\right.yj={1,当采用第j种生产方式，即xj>00,当不采用第j种生产方式，即xj=0目标函数
min z = ( k 1 y 1 + c 1 x 1 ) + ( k 2 y 2 + c 2 x 2 ) + ( k 3 y 3 + c 3 x 3 ) \min z=(k_1y_1+c_1x_1)+(k_2y_2+c_2x_2)+(k_3y_3+c_3x_3)minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)约束方程
Cannot read property 'type' of undefined
注：若只允许采用一种投资方式，则需要满足y 1 + y 2 + y 3 = 3 − 1 y_1+y_2+y_3=3-1y1+y2+y3=3−1注：当y j = 1 y_j=1yj=1时，x j ≤ M x_j\le Mxj≤M，因此不对x j x_jxj产生约束；当y j = 0 y_j=0yj=0时，x j = 0 x_j=0xj=0，即不生产
隐枚举法
枚举法：n nn个变量需要穷举2 n 2^n2n次（上限）。隐枚举法（分支定界法也是一种隐枚举法）本质是对枚举法的一种优化（此外还有拉格朗日松弛法）
e.g. max z = 3 x 1 − 2 x 2 + 5 x 3 , s . t . { x 1 + 2 x 2 − x 3 ≤ 2 ① x 1 + 4 x 2 + x 3 ≤ 4 ② x 1 + x 2 ≤ 3 ③ 4 x 1 + x 3 ≤ 6 ④ x i = 0 或 1 \max z=3x_1-2x_2+5x_3 , ~s.t. \left\{\begin{array}{lc} x_1+2x_2-x_3\le 2 &\text{①}\\ x_1+4x_2+x_3\le 4 &\text{②}\\ x_1+x_2\le 3 &\text{③}\\ 4x_1+x_3\le 6 &\text{④}\\ x_i=0\text{或}1 \end{array}\right.maxz=3x1−2x2+5x3, s.t.⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧x1+2x2−x3≤2x1+4x2+x3≤4x1+x2≤34x1+x3≤6xi=0或1①②③④
不用化标准型，但对目标函数进行一些处理。保证是在求max z \max zmaxz的条件下对x i x_ixi前的系数按从小到大的顺序排序：max z = − 2 x 2 + 3 x 1 + 5 x 3 \max z=-2x_2+3x_1+5x_3maxz=−2x2+3x1+5x3
观察约束方程组，通过试探的方法随便找出一个可行解：x = ( 1 , 0 , 0 ) T x=(1,0,0)^Tx=(1,0,0)T
将2中试探出的可行解代入目标函数z zz后得出一个取值z 0 z_0z0，因为我们希望找到max z \max zmaxz，所以我们希望z ≥ z 0 z\ge z_0z≥z0，将此不等式作为一个新增约束：3 x 1 − 2 x 2 + 5 x 3 ≥ 5 ⑤ 3x_1-2x_2+5x_3\ge 5 ~~~~~\text{⑤}3x1−2x2+5x3≥5 ⑤
开始枚举和比较
注：对目标函数进行重排之后可以使目标函数求值非递减
指派问题
有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如图所示。问应指派何人去完成何工作，使所需总时间最少?
注：n个人干n件事，不重不漏，既没有人没事干，也不能有事没人干。给个人只干一件事，每件事都只被一个人处理
引入决策变量x i j x_{ij}xij
x i j = { 1 当指派第 i 人去完成第 j 项任务 0 当不指派第 i 人去完成第 j 项任务 x_{ij}=\left\{\begin{array}{ll}1&\text{当指派第}i\text{人去完成第}j\text{项任务}\\0&\text{当不指派第}i\text{人去完成第}j\text{项任务}\end{array}\right.xij={10当指派第i人去完成第j项任务当不指派第i人去完成第j项任务约束方程
x i j = { ∑ i x i j = 1 , j = 1 , 2 , 3 , 4 ∑ j x i j = 1 , i = 1 , 2 , 3 , 4 x i j = 1 或 0 x_{ij}=\left\{\begin{array}{ll} \sum\limits_{i}x_{ij}=1,&j=1,2,3,4\\ \sum\limits_{j}x_{ij}=1,&i=1,2,3,4\\ x_{ij}=1\text{ 或 }0 \end{array}\right.xij=⎩⎪⎪⎨⎪⎪⎧i∑xij=1,j∑xij=1,xij=1 或 0j=1,2,3,4i=1,2,3,4
注：从人的角度考虑，每个人至少干一件事，且每个人最多干一件事
{ 每个人至少干一件事 ⇒ x i 1 + x i 2 + x i 3 + x i 4 ≥ 1 每个人至多干一件事 ⇒ x i 1 + x i 2 + x i 3 + x i 4 ≤ 1 ⇒ x i 1 + x i 2 + x i 3 + x i 4 = 1 \left\{\begin{array}{c} \text{每个人至少干一件事}\Rightarrow x_{i1}+x_{i2}+x_{i3}+x_{i4}\ge 1\\ \text{每个人至多干一件事}\Rightarrow x_{i1}+x_{i2}+x_{i3}+x_{i4}\le 1 \end{array}\right. \Rightarrow x_{i1}+x_{i2}+x_{i3}+x_{i4}=1{每个人至少干一件事⇒xi1+xi2+xi3+xi4≥1每个人至多干一件事⇒xi1+xi2+xi3+xi4≤1⇒xi1+xi2+xi3+xi4=1
注：从事情的角度，每件事至少有一个人来做，且做每件事的人不超过一个人
x 1 j + x 2 j + x 3 j + x 4 j = 1 x_{1j}+x_{2j}+x_{3j}+x_{4j}=1x1j+x2j+x3j+x4j=1目标函数
min z = ∑ i ∑ j c i j x i j \min z=\sum\limits_i\sum\limits_j c_{ij}x_{ij}minz=i∑j∑cijxij
一般化模型：n个人干n件事情
min z = ∑ i ∑ j c i j x i j x i j = { ∑ i x i j = 1 , j = 1 , 2 , ⋯ , n ∑ j x i j = 1 , i = 1 , 2 , ⋯ , n x i j = 1 或 0 \begin{array}{c} \min z=\sum\limits_i\sum\limits_j c_{ij}x_{ij}\\ x_{ij}=\left\{\begin{array}{ll} \sum\limits_{i}x_{ij}=1,&j=1,2,\cdots,n\\ \sum\limits_{j}x_{ij}=1,&i=1,2,\cdots,n\\ x_{ij}=1\text{ 或 }0 \end{array}\right. \end{array}minz=i∑j∑cijxijxij=⎩⎪⎪⎨⎪⎪⎧i∑xij=1,j∑xij=1,xij=1 或 0j=1,2,⋯,ni=1,2,⋯,n
指派问题-匈牙利法
匈牙利法：可以认为是专门解决指派问题的算法
解矩阵：把可行解x i j x_{ij}xij写成矩阵形式
[ x 11 x 12 x 13 x 14 x 21 x 22 x 23 x 24 x 31 x 32 x 33 x 34 x 41 x 42 x 43 x 44 ] = = 比如 [ 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 ] \left[\begin{array}{cccc} x_{11}&x_{12}&x_{13}&x_{14}\\ x_{21}&x_{22}&x_{23}&x_{24}\\ x_{31}&x_{32}&x_{33}&x_{34}\\ x_{41}&x_{42}&x_{43}&x_{44} \end{array}\right] \overset{\text{比如}}{==} \left[\begin{array}{cccc} 0&1&0&0\\ 0&0&1&0\\ 1&0&0&0\\ 0&0&0&1 \end{array}\right]⎣⎢⎢⎡x11x21x31x41x12x22x32x42x13x23x33x43x14x24x34x44⎦⎥⎥⎤==比如⎣⎢⎢⎡0010100001000001⎦⎥⎥⎤
注：每一行每一列都只有一个1匈牙利法步骤
将题干中的工作矩阵写出来，并变换系数矩阵，使每行每列都出现0：每一行元素中减去该行最小元素，并在此基础上每列元素减去该列最小元素
C = [ 2 ‾ 15 13 4 10 4 ‾ 14 15 9 ‾ 14 16 13 7 ‾ 8 11 9 ] 2 4 9 7 → [ 0 13 11 2 6 0 ‾ 10 11 0 5 7 4 0 ‾ 1 4 ‾ 2 ‾ ] → [ 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 ] C= \left[\begin{array}{cccc} \underline{2}&15&13&4\\ 10&\underline{4}&14&15\\ \underline{9}&14&16&13\\ \underline{7}&8&11&9 \end{array}\right] \begin{array}{c} 2\\4\\9\\7 \end{array} \to \left[\begin{array}{cccc} 0&13&11&2\\ 6&\underline{0}&10&11\\ 0&5&7&4\\ \underline{0}&1&\underline{4}&\underline{2} \end{array}\right] \to \left[\begin{array}{cccc} 0&13&7&0\\ 6&0&6&9\\ 0&5&3&2\\ 0&1&0&0 \end{array}\right]C=⎣⎢⎢⎡2109715414813141611415139⎦⎥⎥⎤2497→⎣⎢⎢⎡06001305111107421142⎦⎥⎥⎤→⎣⎢⎢⎡06001305176300920⎦⎥⎥⎤
注：必须先变行，再变列，不能同时进行改变试指派：找出独立0元素
- 从只有一个0元素的行开始，给这个0元素加圈，记作⊚ \circledcirc⊚。这表示对这行所代表的人,只有一种任务可指派。然后划去⊚ \circledcirc⊚所在列的其他0元素，记作Φ \PhiΦ。这表示这列所代表的任务已指派完，不必再考虑别人了
- 给只有一个0元素列的0元素加圈，记作⊚ \circledcirc⊚；然后划去⊚ \circledcirc⊚所在行的其他0元素，记作Φ \PhiΦ
- 反复进行1、2两步，直到所有0元素都被圈出和划掉为止
- 若仍有没有划圈的0元素，且同行的0元素至少有两个（表示对这个人可以从两项任务中指派其一）。这可用不同的方案去试探。从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少的）。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止
- 若⊚ \circledcirc⊚元素的数目m mm等于矩阵的阶数n nn ，那么这指派问题的最优解已得到。若m ≤ n m\le nm≤n,则转入下一步
注：对于上矩阵，先给b 22 b_{22}b22加圈，然后给b 31 b_{31}b31加圈，划掉b 11 , b 41 b_{11},b_{41}b11,b41；给b 43 b_{43}b43加圈，划掉b 44 b_{44}b44，最后给b 14 b_{14}b14加圈
[ Φ 13 7 ⊚ 6 ⊚ 6 9 ⊚ 5 3 2 Φ 1 ⊚ Φ ] ⟹ 最优解 [ 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 ] ⟹ 最优值 min z = c 31 + c 22 + c 43 + c 14 = 28 \left[\begin{array}{cccc} \Phi&13&7&\circledcirc\\ 6&\circledcirc&6&9\\ \circledcirc&5&3&2\\ \Phi&1&\circledcirc&\Phi \end{array}\right] \begin{array}{c} &\overset{\text{最优解}}{\Longrightarrow} \left[\begin{array}{cccc} 0&0&0&1\\ 0&1&0&0\\ 1&0&0&0\\ 0&0&1&0 \end{array}\right]\\ &\overset{\text{最优值}}{\Longrightarrow} \min z=c_{31}+c_{22}+c_{43}+c_{14}=28 \end{array}⎣⎢⎢⎡Φ6⊚Φ13⊚51763⊚⊚92Φ⎦⎥⎥⎤⟹最优解⎣⎢⎢⎡0010010000011000⎦⎥⎥⎤⟹最优值minz=c31+c22+c43+c14=28打钩、直线覆盖：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素，以下矩阵为例
- 对没有⊚ \circledcirc⊚的行打√ √√号
- 对已打√ √√号的行中所有含Φ \PhiΦ元素的列打√ √√
- 再对打有√ √√的列中含⊚ \circledcirc⊚元素的行打√ √√
- 重复2、3直到得不出新的打√ √√的行列为止
- 对没有打√ √√的行画一条横线，有打√ √√的列画一条纵线，这就得到覆盖所有0元素的最少直线数
- 令直线数为l ll，若l < n l<nl<n，说明必须再变换当前的系数矩阵，才能找到n nn个独立的0元素，转至下一步；若l = n l=nl=n而m < n m<nm<n则回到上一步4，另行试探
找到没有覆盖的最小元素m i n minmin，没有覆盖的（打钩）行− m i n -min−min，覆盖的（打钩）列+ m i n +min+min，得到新系数矩阵，若得到n nn个独立的0元素，则已经得到最优解，否则回到上一步重复进行
对于max z \max zmaxz的问题max z = ∑ i ∑ j c i j x i j \max z=\sum\limits_i\sum\limits_jc_{ij}x_{ij}maxz=i∑j∑cijxij，需要转化为求min \minmin的情形。需要令b i j = M − c i j b_{ij}=M-c_{ij}bij=M−cij，其中M MM是足够大的数，如选c i j c_{ij}cij中最大元素为M MM即可，解得min z ′ = ∑ i ∑ j b i j x i j \min z'=\sum\limits_i\sum\limits_jb_{ij}x_{ij}minz′=i∑j∑bijxij的最优解就是原问题的最优解