清华大学运筹学4整数规划

1、第第五五章章 整数规划整数规划第一节第一节 整数规划数学模型及解的特点整数规划数学模型及解的特点第二节第二节 割平面法割平面法第四节第四节 0-1型整数规划型整数规划第五节第五节 指派问题指派问题1/68第一节第一节 整数规划整数规划模型及模型及解的特点解的特点一一、整数规划模型一般形式整数规划模型一般形式2/683/68 Max z=CX s.t. AX 或或=或或 b X0， b0 C=(c1, c2, , cn ) X=(x1, x2, , xn )T 有些或全部有些或全部xj取整数取整数 b=(b1, b2, , bm )T a11 a12 a1n A= = a21 a22 a2n .

2、 . . . . . . . . mn am1 am2 amn 4/68若对决策变量不提整数要求，则上述规划问题称若对决策变量不提整数要求，则上述规划问题称为该为该整数规划问题的松弛整数规划问题的松弛问题问题。若松弛。若松弛问题是线问题是线性规划问题，则该性规划问题，则该整数规划整数规划问题叫做问题叫做整数线性规整数线性规划划。整数线性规划有如下几种类型：整数线性规划有如下几种类型：1. 纯整数线性规划纯整数线性规划全部决策变量须取整数，全部决策变量须取整数，亦称亦称全整数规划全整数规划。 2. 混合混合整数线性规划整数线性规划部分决策变量须部分决策变量须取取整整数。数。3. 0-1型型整数线

3、性规划整数线性规划决策变量只取决策变量只取0或或1的的整数线性规划。整数线性规划。 5/68二、二、 整数规划之整数规划之例例例例1某商场拟用集装箱托运两种货物，每箱体某商场拟用集装箱托运两种货物，每箱体积、重量、可获利润以及所受限制如下表。积、重量、可获利润以及所受限制如下表。问：两种货物各托运多少，利润最大？问：两种货物各托运多少，利润最大？ 货物货物体积体积立方米立方米/箱箱重量重量百斤百斤/箱箱利润利润千元千元/箱箱服装服装5220玩具玩具4510托运限制托运限制24136/68用用x1和和x2将表示服装和玩具的托运箱数，则该问将表示服装和玩具的托运箱数，则该问题可表示如下：题可表示如

4、下： Max z=20 x1+10 x2 (1) s.t. 5x1 +4x2 24 (2) 2x1+5x2 13 (3) x1，x20， (4) x1，x2取整数取整数 (5)7/68例例2某地区要建水电站，有某地区要建水电站，有15处可行，可用资处可行，可用资金总额为金总额为B。各处所需投资和预期收益分别为。各处所需投资和预期收益分别为aj和和cj (j=1, 3, , 15)。要求是：要求是：若在第一处建，第二处也要建；若在第一处建，第二处也要建；但是，第二但是，第二处建处建；第一处不一定建；第一处不一定建；第三和第四处至少有一处必须建；第三和第四处至少有一处必须建；第五、六和第七处建两个

5、。第五、六和第七处建两个。问问：如何在这：如何在这15处布置水电站，才能预期最大收处布置水电站，才能预期最大收益？益？8/68n9/68例例3现有现有A1和和A2生产某产品，在生产某产品，在B1、B2 、B3和和B4销售。因供不应求，计划再建一厂。新厂有方销售。因供不应求，计划再建一厂。新厂有方案案A3和和A4，建成后年生产费用分别为，建成后年生产费用分别为1200和和1500万元。从产地到销地运费见下表。问哪一方案使万元。从产地到销地运费见下表。问哪一方案使新厂建成后年运费与生产费用总和最少？新厂建成后年运费与生产费用总和最少？ B1B2B3B4产能（千吨产能（千吨/年）年）A1293440

6、0A28357600A37612200A44525200需求量需求量（千吨（千吨/年）年） 350400 30015010/68n11/68三、解的特点三、解的特点 整数线性规划整数线性规划的解一定是松弛问题的解的解一定是松弛问题的解，可行域是松弛问题可行域的子集。可行域是松弛问题可行域的子集。 目标函数值不会超过松弛问题目标函数值。目标函数值不会超过松弛问题目标函数值。 反过来，反过来，不一定成立不一定成立。 不能不能将松弛问题的解四舍五入当作将松弛问题的解四舍五入当作整数线性整数线性规划的解。规划的解。 xj=1或或0， j=1, 3, , 15 12/68现在看托运问题：现在看托运问题：

7、 Max z=20 x1+10 x2 s.t. 5x1 +4x2 24 2x1+5x2 13 x1，x20， x1，x2取整数取整数先用图解法解先用图解法解松驰问题松驰问题，得得13/684x1x23225x1+4x2=24z=20 x1+10 x2=96z=15oA(4.8, 0)2x1+5x2 =136z=90(4, 1)z=1014/68最优解最优解是是(x1, x2)=(4.8, 0) Max z=96再看整数规划问题再看整数规划问题，若若取取x1=5，x2=0，破坏了约束条件，破坏了约束条件5x1 +4x224若取若取x1=4，x2=0 ， z=20 x1+10 x2=80，实际上实

8、际上，(x1, x2)=(4, 1)也是可行解，也是可行解，z=90可见，将松弛问题的解四舍五入不能求得整数线可见，将松弛问题的解四舍五入不能求得整数线性规划的解。性规划的解。第二节第二节 解整数规划的割平面法解整数规划的割平面法 就是在解松驰问题过程就是在解松驰问题过程中中逐一去掉非整数逐一去掉非整数解域，寻找整数解的方法，也就是解域，寻找整数解的方法，也就是“切割切割”可可行域平面。切割的办法是增加约束条件。行域平面。切割的办法是增加约束条件。15/68He (born 7 May 1929 in Brooklyn) is an applied mathematician. He work

9、ed at IBM as a researcher and later as an executive and his research led to the creation of new areas of applied mathematics. After his career in the corporate world, he became the president of the Alfred P. Sloan Foundation, where he oversaw programs dedicated to broadening public understanding in

10、three key areas: the economic importance of science and research; the effects of globalization on the United States; and the role of technology in education. 16/68Ralph Edward Gomory 17/68例例1 Max z=x1+x2 s.t. -x1 +x2 1 3x1+x2 4 x1，x20， x1，x2取整数取整数先用图解法解先用图解法解松驰问题松驰问题，得得18/68x1x2211-x1+x2=1z=x1+x2=2.

11、5o4/33x1+x2 =4A(3/4, 7/4)C(1, 1)R19/68最优解最优解是是(x1, x2)=(3/4, 7/4) Max z=10/4整数整数点点C不是顶点不是顶点，所以目标函数就向非整数点所以目标函数就向非整数点A呼啸而去，若将呼啸而去，若将C改成顶点，就可能拦截目标改成顶点，就可能拦截目标函数函数。20/68x1x2211-x1+x2=1o4/33x1+x2 =4C(1, 1)整数点整数点C已已经改成顶点，但还经改成顶点，但还拦不住目标函数。拦不住目标函数。DAR 21/68x1x2211-x1+x2=1o4/33x1+x2 =4C(1, 1)再切一次，整数顶点再切一次，

12、整数顶点C拦住了拦住了目标函数。目标函数。DBAR 22/68如何构造用来切割平面的直线呢？如何构造用来切割平面的直线呢？在松弛问题约束条件中添加松弛变量：在松弛问题约束条件中添加松弛变量： -x1 +x2 +x3 =1 3x1+x2 +x4 = 4 x1，x20， 然后，列出初始单纯形表：然后，列出初始单纯形表：23/68cj1100icBxBB-1bx1x2x3x40 x31-1110-0 x4431014/3z1100j0 x37/304/311/37/41x14/311/301/34z02/30-1/3j24/68cj1100icBxBB-1bx1x2x3x41x27/4013/41/

13、41x13/410-1/41/4z10/400-1/2-1/2j从中可得到从中可得到 x1 -x3/4+x4/4 =3/4 x2+3x3/4 +x4/4 =7/4将其中的系数和常数项均分解成整数和非整数两将其中的系数和常数项均分解成整数和非整数两部分：部分：25/68可得到可得到 x1 -x3 = 3/4-(3x3/4+x4/4) x2 1 =3/4- (3x3/4 +x4/4)从从 -x1 +x2 +x3 =1 3x1+x2 +x4 = 4可知，可知，x1和和x2若是非负整数，若是非负整数， x3和和x4也是非负整也是非负整数。所以，根据数。所以，根据 x1 -x3 = 3/4-(3x3/4

14、+x4/4) x2 1 =3/4- (3x3/4 +x4/4)左边判断，左边判断，3/4- (3x3/4 +x4/4)应当是整数，应当是整数，26/68而而 (3x3/4 +x4/4)是正数，一定要比是正数，一定要比3/4大，两者之大，两者之差才可能是整数，即，必须有差才可能是整数，即，必须有3x3/4 +x4/43/4，-3x3 -x4-3，添加松弛变量添加松弛变量x5后得到：后得到： -3x3 -x4+x5= -3，叫做，叫做切割方程，将其添加到最终单纯形表中，得切割方程，将其添加到最终单纯形表中，得cj11000icBxBB-1bx1x2x3x4x51x27/4013/41/401x13

15、/410-1/41/400 x5-300-3-11z-1/2/-3-1/2/-1-j/alj27/68最终单纯形表最终单纯形表已经得到整数线性规划已经得到整数线性规划最优解。最优解。(x1, x2, x3, x4)=(1, 1, 1, 0)，Max z=2。cj11000icBxBB-1bx1x2x3x4x51x2101001/41x111001/3-1/120 x310011/3-1/3z2000-1/3-1/6j/alj28/68n29/68n30/68例例2用用Gomory切割法求解如下问题。切割法求解如下问题。Max z=3x1-x2 s.t. 3x1 -2x2 3 5x1+4x2 1

16、0 2x1+ x2 5，x1，x2为非负为非负整数整数。先解松驰问题先解松驰问题 Max z=3x1-x2+0 x3+0 x4-Mx5+0 x6 s.t. 3x1 -2x2+x3 =3 5x1+4x2 -x4 +x5 =10 2x1+ x2 +x6 =5 x1，x2031/68cj3-100-M0icBxBB-1bx1x2x3x4x5x60 x333-210003/3-Mx510540-11010/50 x652100015/2z5M+34M-10-M00初始初始单纯形表单纯形表3x111-2/31/3000-Mx55022/3-5/3-11015/220 x6307/3-2/30019/7z

17、022M/3 -5M/3 -M0032/683x116/11102/11-1/11-0-1x215/2201-5/22-3/22-0-0 x631/2200-3/227/22-131/7z00-17/222/11-0cj3-100-M0icBxBB-1bx1x2x3x4x5x63x113/7101/70-2/7-1x29/701-2/70-3/70 x431/700-3/71-22/7z30/700-5/70-3/733/68构造切割方程，构造切割方程，13/7、9/7和和31/7中真分数最大的中真分数最大的是是13/7，对应最终单纯形表中第一行，对应最终单纯形表中第一行，所以，所以，选选取取

18、 x1 + x3/7 + 2x6/7=13/7 x1 -1 =6/7- x3/7 - 2x6/7 -x3/7-2x6/7 -6/7添入松弛变量添入松弛变量x7 得得 -x3/7-2x6/7 +x7 = -6/7将其添入上面的最终单纯形表，得将其添入上面的最终单纯形表，得34/683x113/7101/702/70-1x29/701-2/703/700 x431/700-3/7122/700 x7-6/700-1/70-2/71z00503/2cj3-10000icBxBB-1bx1x2x3x4x6x73x11100001-1x2001-1/2003/20 x4-500-210110 x6300

19、1/201-7/2001/400-35/68cj3-10000icBxBB-1bx1x2x3x4x6x73x11100001-1x25/4010-1/40-5/40 x35/2001-1/20-11/20 x67/40001/41-3/4z7/4000-1/40-17/4构造切割方程：构造切割方程：5/4、5/2和和7/4真分数最大的是真分数最大的是7/4，对应最终单纯形表第四行，所以，选取，对应最终单纯形表第四行，所以，选取 x4/4+x5-3x7/4=7/4，即，即x5 -x7-1= 3/4 -x4/4-x7/4，3/4 -x4/4-x7/40，添入松弛变量，添入松弛变量x8 得得-x4/

20、4-x7/4 +x8 = -3/4，添入上面最终单纯形表，得，添入上面最终单纯形表，得36/68cj3-100000icBxBB-1bx1x2x3x4x6x7x83x111000010-1x25/4010-1/40-5/400 x35/2001-1/20-11/200 x67/40001/41-3/400 x8-3/4000-1/40-1/410001017037/68cj3-100000icBxBB-1bx1x2x3x4x6x7x83x111000010-1x2201000-1-10 x3400100-5-20 x6100001-110 x43000101-4100000-4-1X*=(x1

21、, x2, x3, x4, x6, x7, x8)=(1, 2, 4, 3, 1, 0, 0)38/68为了说明切割方程的几何意义，回头看：为了说明切割方程的几何意义，回头看： x1 -1 =6/7- x3/7 - 2x6/7和和x5 -x7-1= 3/4 -x4/4-x7/4，另外另外，从松驰问题标准形式约束条件知从松驰问题标准形式约束条件知 3x1 -2x2+x3 =3 5x1+4x2 -x4 +x5 =10 2x1+ x2 +x6 =5 即即 x3=3-3x1 +2x2 x5=10-5x1-4x2 +x4 x6 =5-2x1-x2将其代入切割方程，并考虑到将其代入切割方程，并考虑到6/7

22、- x3/7 - 2x6/7 0， 3/4 -x4/4-x7/4 0 ，39/68得到：得到： x1 -1 0和和x1 +x23这就是这就是用用x1和和x2表示的切割方程。表示的切割方程。下面下面，逐次分割松弛问题的可行域逐次分割松弛问题的可行域，逐步求得整逐步求得整数解。数解。40/68x1x2211o23x1-2x2 =3A(13/7, 9/7)R2.52.52x1+x2 =55x1+4x2 =10z=3x1-x2 =30/7未切割时的松弛问题未切割时的松弛问题41/68x1x2211o23x1-2x2 =3B(1, 5/4)R2.52.52x1+x2 =55x1+4x2 =10z=3x1

23、-x2 =7/4用用x1=1切割切割x1=1A(13/7, 9/7)42/68x1x2211o23x1-2x2 =3C(1, 2)R”2.52.5x1+x2 =35x1+4x2 =10z=3x1-x2 =1用用x1+x2=3切割切割x1=132x1+x2 =5B(1, 5/4)A(13/7, 9/7)第四节第四节 0-1整数规划整数规划43/68一、一、0-1变量及其应用变量及其应用1. 互斥的约束条件互斥的约束条件前面托运问题，体积限制条件是前面托运问题，体积限制条件是 5x1+4x224现假设托运有陆运和水运两种方式，水运时体现假设托运有陆运和水运两种方式，水运时体积限制条件是积限制条件是

24、 7x1+3x2 45 为了将这两个互斥的限制条件一块考虑，借为了将这两个互斥的限制条件一块考虑，借用一个用一个0-1变量变量y，令，令 y=0，陆运，陆运 y=1，水运，水运44/68这样一来，上述两个互斥约束条件都可以写入这样一来，上述两个互斥约束条件都可以写入模型：模型： 5x1+4x224+yM 7x1+3x245+(1-y)MM是足够大的整数。是足够大的整数。y=0，陆运，陆运，7x1+3x245+M不起作用；不起作用；y=1，水运，水运，5x1+4x224+M。 y在目标函数中在目标函数中的系数为的系数为0。45/6846/68二、二、0-1型整数线性规划解法型整数线性规划解法 若

25、有若有n个个0-1型决策变量，就会有型决策变量，就会有2n个取值个取值情况。问题的解就在这情况。问题的解就在这2n种情况之中。若种情况之中。若n=10，则有，则有1024种情况，手算工作量可观。种情况，手算工作量可观。 如果能很快发现这如果能很快发现这2n种种情况情况之中不符合要之中不符合要求者，就可以节省计算时间。求者，就可以节省计算时间。 我们就遵循这个思路寻找解题办法。我们就遵循这个思路寻找解题办法。47/68例例1求解求解0-1型整数线性规划型整数线性规划Max z=3x1-2x2+5x3s.t. x1+2x2-x3 2 (a) x1+4x2+x34 (b) x1+x2 3 (c) 4

26、x2+x3 6 (d) x1, x2, x3=1,048/6849/68 x1, x2, x3za b c d过滤条件过滤条件0 0 00 z00 0 15 z50 1 0-2无须检查无须检查0 1 13无须检查无须检查1 0 03无须检查无须检查1 0 18 z81 1 01无须检查无须检查1 1 16无须检查无须检查X* =(x1, x2, x3)T= (1, 0, 1)T，Max z=8计算工作量还需减少。计算工作量还需减少。例例2求解求解0-1型整数线性规划型整数线性规划Min z=3x1+7x2-x3+x4s.t. 2x1-x2+ x3 -x41 x1 -x2+6x3+4x48 5x

27、1+3x2 +x45 x1, x2, x3, x4=1,0求目标函数最大的问题按价值系数由小到大重求目标函数最大的问题按价值系数由小到大重新排列；求最小问题，反过来，这样，可减少新排列；求最小问题，反过来，这样，可减少计算量。计算量。50/68本例可如下重新排列本例可如下重新排列Min z=7x2+3x1+x4-x3s.t. -x2 +2x1 -x4 + x31 -x2 + x1+4x4 +6x38 3x2 +5x1+x4 5 x2, x1, x4, x3 =1,051/68第五节第五节 指派问题指派问题52/68一、指派问题标准形式及数学模型一、指派问题标准形式及数学模型标准形式指派问题标准

28、形式指派问题定义：定义：已知已知n种资源用于种资源用于n种用途的代价种用途的代价分别分别为为cij(i, j=1, 2, , n)，如何在代价最小且每一种用途，如何在代价最小且每一种用途只用一种资源条件下分派这些资源？或者在只用一种资源条件下分派这些资源？或者在cij是收益时，如何是收益时，如何分派这些分派这些资源，才能取得最大资源，才能取得最大收益？收益？一般用一般用C表示指派问题的系数矩阵表示指派问题的系数矩阵(cij)。令。令xij令令为为nn个个0-1型变量，型变量， xij=1表示为第表示为第j种用途指种用途指派第派第i种资源，种资源， xij=0表示未为表示未为第第j种用途指派第种

29、用途指派第i种种资源。资源。53/6854/68例例1某公司最近在五处中标，有五人可派。某公司最近在五处中标，有五人可派。他们的经验、语言、习惯、能力、社会交往和他们的经验、语言、习惯、能力、社会交往和个人喜好等，使其在不同地方和不同工程上付个人喜好等，使其在不同地方和不同工程上付出的代价如下表。问：如何为他们分派地点，出的代价如下表。问：如何为他们分派地点，公司才代价最小？公司才代价最小？55/68阿联酋阿联酋新加坡新加坡香港香港关岛关岛苏丹苏丹王聪王聪4871512张猛张猛79171410李志李志691287孙爽孙爽6714610何立何立691210656/68二、匈牙利解法二、匈牙利解法

30、上述的枚举法可以解指派问题上述的枚举法可以解指派问题，但匈牙利法更但匈牙利法更好好。该法利用了。该法利用了C中独立零元素的性质。中独立零元素的性质。若从若从C中某行或某列各元素减去或在其上加上某中某行或某列各元素减去或在其上加上某常数常数，得到得到的新矩阵对应的指派问题与原矩阵的新矩阵对应的指派问题与原矩阵对应者同解，即对应者同解，即X =(xij)相同。相同。该法一般步骤该法一般步骤：Step1变换变换C，先各行分别减去本行最小元素；，先各行分别减去本行最小元素；再各列分别再各列分别减去减去本列最小本列最小元素元素；使每行、每列；使每行、每列至少有一个零，但不出现小于零者。然后，至少有一个零

31、，但不出现小于零者。然后，Step2在新在新C中确定独立零，个数若为中确定独立零，个数若为n，则已经，则已经得到最优解。若少于得到最优解。若少于n，则划直线覆盖零，并，则划直线覆盖零，并57/68找出最少条数覆盖所有独立零的直线全体。然找出最少条数覆盖所有独立零的直线全体。然后转后转step3。对于对于C非非负的指派问题，若从中找出负的指派问题，若从中找出n个处于个处于不同行、不同列的零，总代价一定为零，最优不同行、不同列的零，总代价一定为零，最优。若某行（列）有多个零，选定一个后，不能。若某行（列）有多个零，选定一个后，不能再选别的。所以，所谓再选别的。所以，所谓n个零，一定应是独立个零，一

32、定应是独立的。如果独立零个数少于的。如果独立零个数少于n，找出最少条数覆找出最少条数覆盖所有独立零的直线全体盖所有独立零的直线全体。Step3继续变换继续变换C，然后，回到，然后，回到step2。以下举例说明这三个步骤。以下举例说明这三个步骤。58/68例例2派项目经理求最小代价问题。派项目经理求最小代价问题。 4 8 7 15 12 7 9 17 14 10 C = 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6Step1 变换变换C，先各行分别减去本行最小元素先各行分别减去本行最小元素；再各列分别减去本列最小；再各列分别减去本列最小元素：元素：59/68 0 4 3

33、11 8 0 2 10 7 3 C 0 3 6 2 1 0 1 8 0 4 0 3 6 4 0 0 3 0 11 8 0 1 7 7 3 0 2 3 2 1 = C 0 0 5 0 4 0 2 3 4 0C每行每列都已有零。每行每列都已有零。60/68 3 11 8 1 7 7 3 C = 2 3 2 1 5 4 2 3 4 只有四个独立只有四个独立零，故须找能覆盖所有零零，故须找能覆盖所有零数目最少数目最少的直线的直线。 3 11 8 1 7 7 3 C = 2 3 2 1 5 4 2 3 4 61/6800000000 3 11 8 1 7 7 3 C = 2 3 2 1 5 4 为了为了在未覆盖在未覆盖 2 3 4 行列中出现零行列中出现零，从中找出最小元素，从中找出最小元素1，从第二、三行减去。，从第二、三行减去。 3 11 8 -1 0 6 6 2 C = -1 1 2 1 0 5 4 2 3 4 62/680000000由于第一列出现负数，该列再加由于第一列出现负数，该列再加1： 1 3 0 11 8 0 0 6 6 2 C 0 1 2 1 0 =C“ 1 0 5 0 4 1 2 3 4 0 回到回到step2 1 3 11 8 6 6 2 C“ = 1 2 1 1 5 4 1 2 3 4 63/6800