整数规划与分配问题运筹学

整数规划与分配问题运筹学第一页，共九十一页，编辑于2023年，星期六第4章整数规划与分配问题2023/5/312第二页，共九十一页，编辑于2023年，星期六例4.1某服务部门各时段（每2小时为一时段）需要的服务员人数如下表，按规定，服务员连续工作8小时（即4个时段）为一班，现要求安排服务员的工作时间，使服务部门服务员总数最小。时段12345678服务员最少数目108911138534.1整数规划问题的数学模型2023/5/313第三页，共九十一页，编辑于2023年，星期六解：设在第j时段开始时上班的服务员人数为xj，由于第j时段开始时上班的服务员将在第(j+3)时段结束时下班，故决策变量只需考虑x1,x2,x3,x4,x5，此问题的数学模型为：2023/5/314第四页，共九十一页，编辑于2023年，星期六此类问题数学模型的一般形式为：求一组变量X1,X2,…,Xn，使2023/5/315第五页，共九十一页，编辑于2023年，星期六例4.2某单位有5个拟选择的投资项目，其所需投资额与期望收益如下表。由于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；B和D之间需选择也仅需选择一项；又由于C和D两项目密切相关，C的实施必须以D的实施为前提条件，该单位共筹集资金15万元，问应该选择哪些项目投资，使期望收益最大？项目所需投资额（万元）期望收益（万元）A610B48C27D46E592023/5/316第六页，共九十一页，编辑于2023年，星期六解：决策变量：设目标函数：期望收益最大约束条件：投资额限制条件6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件：x3

x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：2023/5/317第七页，共九十一页，编辑于2023年，星期六上面此例表明，利用0-1变量处理一类“可供选择条件”的问题非常简明方便。下面再进一步分别说明对0-1变量的应用。假定现有m种资源对可供选择的n个项目进行投资的数学模型为：求一组决策变量X1,X2,…,Xn，使 2023/5/318第八页，共九十一页，编辑于2023年，星期六根据变量取整数的情况,将整数规划分为：（1）纯整数规划，所有变量都取整数.（2）混合整数规划，一部分变量取整数,一部分变量取实数（3）0-1整数规划,所有变量均取0或1对决策变量只限于不能取负值的连续型数值，即可以是正分数或正小数。然而在许多经济管理的实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划(IntegerProgramming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(IntegerLinearProgramming)(简记为ILP)。2023/5/319第九页，共九十一页，编辑于2023年，星期六考虑纯整数问题：整数问题的松弛问题：第十页，共九十一页，编辑于2023年，星期六求解ILP问题方法的思考：“舍入取整”法：即先不考虑整数性约束，而去求解其相应的LP问题（称为松驰问题），然后将得到的非整数最优解用“舍入取整”的方法。这样能否得到整数最优解？但在处理个别实际问题时，如果允许目标函数值在某一误差范围内，有时也可采用“舍入取整”得到的整数可行解作为原问题整数最优解的近似。这样可节省求解的人力、物力和财力。2023/5/3111第十一页，共九十一页，编辑于2023年，星期六例4.3设整数规划问题如下首先不考虑整数约束，得到线性规划问题（松弛问题）。2023/5/3112第十二页，共九十一页，编辑于2023年，星期六用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。第十三页，共九十一页，编辑于2023年，星期六因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：割平面法和分支定界法，对于特别的0－1规划问题采用隐枚举法和匈牙利法。2023/5/3114第十四页，共九十一页，编辑于2023年，星期六在实际中经常会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。4.2分配问题与匈牙利法第十五页，共九十一页，编辑于2023年，星期六分配第i个人去完成第j项任务不分配第i个人去完成第j项任务例4.4有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间（h）如下表，应如何分配，使这四个人分别完成这四项任务总的时间为最小？2023/5/3116第十六页，共九十一页，编辑于2023年，星期六2023/5/3117第十七页，共九十一页，编辑于2023年，星期六分配问题的数学模型：设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第I个人去做第j件工作的的效率（时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？设决策变量1分配第i个人去做第j件工作

xij=0相反(I,j=1.2.…n)其数学模型为：第十八页，共九十一页，编辑于2023年，星期六4.2.2匈牙利法指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即（1）从（cij）的每行元素都减去该行的最小元素；（2）再从所得新系数矩阵的每列元素中减去该列的最小元素。2023/5/3119第十九页，共九十一页，编辑于2023年，星期六第二步：进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：（1）从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。然后划去◎所在列(行)的其它0元素，记作Ø；这表示这列所代表的任务已指派完，不必再考虑别人了。（2）给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Ø．（3）反复进行（1），（2）两步，直到尽可能多的0元素都被圈出和划掉为止。2023/5/3120第二十页，共九十一页，编辑于2023年，星期六（4）若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m<n,则转入下一步。第三步：作最少的直线覆盖所有0元素。（1）对没有◎的行打√号；（2）对已打√号的行中所有含Ø元素的列打√号；（3）再对打有√号的列中含◎元素的行打√号；2023/5/3121第二十一页，共九十一页，编辑于2023年，星期六（4）重复（2），（3）直到得不出新的打√号的行、列为止；（5）对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数l。l应等于m，若不相等，说明试指派过程有误，回到第二步（4），另行试指派；若l＝m<n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。第四步：变换矩阵(bij)以增加0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。2023/5/3122第二十二页，共九十一页，编辑于2023年，星期六例4.5任务人员ABCD甲215134乙1041415丙9141613丁78119第二十三页，共九十一页，编辑于2023年，星期六24972023/5/3124第二十四页，共九十一页，编辑于2023年，星期六422023/5/3125第二十五页，共九十一页，编辑于2023年，星期六◎Ø◎ØØ◎◎2023/5/3126第二十六页，共九十一页，编辑于2023年，星期六例4.7有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？任务人员ABCD甲67112乙4598丙31104丁5982第二十七页，共九十一页，编辑于2023年，星期六求解过程如下：第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ找到3个独立零元素但m=3<n=42023/5/3128第二十八页，共九十一页，编辑于2023年，星期六第三步，作最少的直线覆盖所有0元素：◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：2023/5/3129第二十九页，共九十一页，编辑于2023年，星期六000

0

00得到4个独立零元素，所以最优解矩阵为：◎◎◎ØØ√√√◎◎◎ØØ15◎◎◎ØØ◎2023/5/3130第三十页，共九十一页，编辑于2023年，星期六练习：115764戊69637丁86458丙9117129乙118957甲EDCBA费工作用人员第三十一页，共九十一页，编辑于2023年，星期六-1-22023/5/3132第三十二页，共九十一页，编辑于2023年，星期六◎Ø◎◎◎ØØ2023/5/3133第三十三页，共九十一页，编辑于2023年，星期六◎Ø◎◎◎ØØ√√√l=m=4<n=52023/5/3134第三十四页，共九十一页，编辑于2023年，星期六◎Ø◎◎◎ØØ2023/5/3135第三十五页，共九十一页，编辑于2023年，星期六◎Ø◎Ø◎Ø◎Ø√√√√√√√2023/5/3136第三十六页，共九十一页，编辑于2023年，星期六◎Ø◎Ø◎Ø◎Ø√√√√√√√l=m=4<n=52023/5/3137第三十七页，共九十一页，编辑于2023年，星期六◎Ø◎Ø◎Ø◎Ø√√√√√√√2023/5/3138第三十八页，共九十一页，编辑于2023年，星期六◎ØØ◎ØØ◎Ø◎Ø◎此问题有多个最优解282023/5/3139第三十九页，共九十一页，编辑于2023年，星期六◎ØØ◎ØØ◎Ø◎Ø◎2023/5/3140第四十页，共九十一页，编辑于2023年，星期六◎ØØ◎ØØ◎Ø◎Ø◎2023/5/3141第四十一页，共九十一页，编辑于2023年，星期六用匈牙利法求解下列指派问题，已知效率矩阵分别如下：2023/5/3142第四十二页，共九十一页，编辑于2023年，星期六4.2.3两点说明1.分配问题中如果人数和工作任务数不相等是的处理方法ⅠⅡⅢⅣ136262714433658464375524365762ⅠⅡⅢⅣⅤⅥ1362600271440033658004643700552430065762002023/5/3143第四十三页，共九十一页，编辑于2023年，星期六2．如果效率矩阵的数字是表示每人每天能完成的翻译成汉字的字数，问题就变成如何分配任务，使每天完成的任务量为大最，目标函数就变为：等价于：2023/5/3144第四十四页，共九十一页，编辑于2023年，星期六0－1整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，一般的解法为隐枚举法。例4.11求解下列0－1规划问题0－1整数规划与隐枚举法第四十五页，共九十一页，编辑于2023年，星期六解：对于0－1规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。x1.x2.x3约束条件满足条件Z值

(1)(2)(3)(4)是∨否×(0.0.0)

0000∨0(0.0.1)－1101∨5(0.1.0)

2414∨－2(1.0.0)

1110∨3(0.1.1)

15 ×(1.0.1)

0211∨8(1.1.0)

3×(1.1.1)

26×2023/5/3146第四十六页，共九十一页，编辑于2023年，星期六由上表可知，问题的最优解为X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1是一个可行解，为尽快找到最优解，可将3x1－2x2＋5x3≥5作为一个约束，凡是目标函数值小于5的组合不必讨论，如下表。x1.x2.x3约束条件满足条件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)

00000∨0(0.0.1)

5－1101∨5(0.1.0)-2×(0.1.1)

3×(1.0.0)

3×(1.0.1)

80211∨8(1.1.0)

1×(1.1.1)

4×2023/5/3147第四十七页，共九十一页，编辑于2023年，星期六例4.12求解下列0－1规划问题解：由于目标函数中变量x1,x2,

x4

的系数均为负数，可作如下变换：令x1

＝1－

x1′

,x2=1-x2′,x3=x3′,x4=1-x4′带入原题中，但需重新调整变量编号。令x3′=x1′,x4′=x2′得到下式。2023/5/3148第四十八页，共九十一页，编辑于2023年，星期六可以从(1.1.1.1)开始试算，x′(3)＝(1.1.0.1)最优解。∴x(3)＝(1.0.1.0)是原问题的最优解，Z*=－22023/5/3149第四十九页，共九十一页，编辑于2023年，星期六例4.13求解下列0－1规划问题令y1=x5,y2=x4,y3=x2,y4=x3,y5=x1

得到下式2023/5/3150第五十页，共九十一页，编辑于2023年，星期六y1.y2.y3.y4.y5约束条件满足条件Z值

(1)(2)是∨否×(0，0，0，0，0)

00×(1，0，0，0，0)

1-1×(0，1，0，0，0)

-11×(0，0，1，0，0)

-21×(0，0，0，1，0)

4-4∨8(0，0，0，0，1)

3-2×所以，

Y*=（0.0.0.1.0），原问题的最优解为：

X*

＝（0.0.1.0.0），Z*=82023/5/3151第五十一页，共九十一页，编辑于2023年，星期六（0，1，1，0，0）练习：用隐枚举法求解0—1规划问题第五十二页，共九十一页，编辑于2023年，星期六4.3.1基本思路4.3分枝定界法只解松弛问题1、在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程若松弛问题最优解中某个xk=bk不是整数，令bk为bk

的整数部分构造两个新的约束条件xkbk和xkbk+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题—定界过程设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况2023/5/3153第五十三页，共九十一页，编辑于2023年，星期六分枝问题解可能出现的情况情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或52023/5/3154第五十四页，共九十一页，编辑于2023年，星期六例4.8用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般线性规划问题记为（LP）第五十五页，共九十一页，编辑于2023年，星期六用图解法求（LP）的最优解，如图所示。x1x2⑴⑵33(18/11,40/11)⑶对于x1＝18/11≈1.64，取值x1≤1，x1≥2对于x2=40/11≈3.64，取值x2≤3，x2≥4先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。2023/5/3156第五十六页，共九十一页，编辑于2023年，星期六有下式：现在只要求出（LP1）和（LP2）的最优解即可。2023/5/3157第五十七页，共九十一页，编辑于2023年，星期六x1x2⑴⑵33(18/11,40/11)⑶先求（LP1）,如图所示。此时B在点取得最优解。x1＝1,x2=3,Z(1)＝－16找到整数解，问题已探明，此枝停止计算。11同理求（LP2）,如图所示。在C

点取得最优解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7∵Z2<Z1＝－16∴原问题有比（－16）更小的最优解，但x2不是整数，故利用3≥10/3≥4加入条件。BAC2023/5/3158第五十八页，共九十一页，编辑于2023年，星期六加入条件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最优解即可。2023/5/3159第五十九页，共九十一页，编辑于2023年，星期六x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如图所示。此时D在点取得最优解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整数，可继续分枝。即3≤x1≤2。D求（LP4），如图所示。无可行解，不再分枝。2023/5/3160第六十页，共九十一页，编辑于2023年，星期六在（LP3）的基础上继续分枝。加入条件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最优解即可。2023/5/3161第六十一页，共九十一页，编辑于2023年，星期六x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如图所示。此时E在点取得最优解。即x1＝2,x2=3,Z(5)＝－17找到整数解，问题已探明，此枝停止计算。E求（LP6），如图所示。此时F在点取得最优解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F如对Z(6)

继续分解，其最小值也不会低于－15.5，问题探明,剪枝。2023/5/3162第六十二页，共九十一页，编辑于2023年，星期六至此，原问题（IP）的最优解为：x1=2，x2=3,Z*=Z(5)

＝－17以上的求解过程可以用一个树形图表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP3x1=12/5,x2=3Z(3)

＝－17.4LP4无可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃2023/5/3163第六十三页，共九十一页，编辑于2023年，星期六练习：用分枝定界法求解整数规划问题（图解法）

第六十四页，共九十一页，编辑于2023年，星期六LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)

＝3LP6无可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)

＝61/14LP4无可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤2x1≥3＃＃2023/5/3165第六十五页，共九十一页，编辑于2023年，星期六LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=2/3,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9LP3x1=33/14,x2=2Z(3)

＝61/14LP4无可行解LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3＃＃＃＃2023/5/3166第六十六页，共九十一页，编辑于2023年，星期六3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例4.10用分枝定界法求解整数规划问题（单纯形法）

第六十七页，共九十一页，编辑于2023年，星期六

x1=13/4x2=5/2Z(0)=59/4≈14.75

选x2进行分枝，即增加两个约束，2≥x2≥3有下式：分别在(LP1)和(LP2)中引入松弛变量x5和x6

，将新加约束条件加入上表计算。即x2+x5=2,－x2+x6=－3

得下表:2023/5/3168第六十八页，共九十一页，编辑于2023年，星期六32000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2

-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2Z(1)=29/2=14.5继续分枝，加入约束

3≥x1≥4LP12023/5/3169第六十九页，共九十一页，编辑于2023年，星期六32000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3Z(2)=27/2=13.5∵Z(2)<Z(1)∴先不考虑分枝2023/5/3170第七十页，共九十一页，编辑于2023年，星期六接(LP1)继续分枝，加入约束4≤x1≤3，有下式：分别引入松弛变量x7和x8，然后进行计算。2023/5/3171第七十一页，共九十一页，编辑于2023年，星期六CB

XB

bx1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3

x1=3,x2=2Z(3)=13找到整数解，问题已探明，停止计算。LP32023/5/3172第七十二页，共九十一页，编辑于2023年，星期六CB

XB

bx1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1

x1=4,x2=1Z(4)=14找到整数解，问题已探明，停止计算。LP42023/5/3173第七十三页，共九十一页，编辑于2023年，星期六树形图如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)

＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)

＝13LP4x1=4,x2=1Z(4)

＝14x2≤2x2≥3x1≤3x1≥4＃＃＃2023/5/3174第七十四页，共九十一页，编辑于2023年，星期六练习：用分枝定界法求解整数规划问题（单纯形法）第七十五页，共九十一页，编辑于2023年，星期六cj-1-5000cBxBbx1x2x3x4x50x32-111000x4

30560100x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/115/110-1x1

18/11101/11-6/1100x526/1100-1/116/111-Z218/11006/1119/1102023/5/3176第七十六页，共九十一页，编辑于2023年，星期六LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP3x1=12/5,x2=3Z(3)

＝－17.4LP4无可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃2023/5/3177第七十七页，共九十一页，编辑于2023年，星期六4.4割平面法的基本思想费用减小方向若的分量不全是整数，则对增加一个割平面条件，将的可行区域割掉一块，恰好在被割掉的区域内，而原ILP问题的任何一个可行解（格点）都没有被割去.2023/5/3178第七十八页，共九十一页，编辑于2023年，星期六把增添了割平面条件的问题记为，用对偶单纯形法求解LP问题.若的最优解是整数向量，则是原ILP问题的最优解，计算结束；否则对问题在增加一个割平面条件，形成问题，…，如此继续下去，通过求解不断改进的松弛LP问题，知道得到最优整数解为止。2023/5/3179第七十九页，共九十一页，编辑于2023年，星期六例4.7用割平面法求解整数规划问题解：增加松弛变量x3和x4

，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/42023/5/3180第八十页，共九十一页，编辑于2023年，星期六此题的最优解为：X＊

(1,3/2)Z=3/2但不是整数最优解，引入割平面。以x2为源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:也即：2023/5/3181第八十一页，共九十一页，编辑于2023年，星期六将x3=6-3x1-2x2,x4=3x1-2x2,带入中，得到等价的割平面条件：x2≤1见下图。x1x2⑴⑵33第一个割平面2023/5/3182第八十二页，共九十一页，编辑于2023年，星期六Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010