物流运筹学课件3

1、郭淑红郭淑红guoshuhong_1307455345313074553453n例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。n全部决策变量的取值都为整数，则称为全整数规划(All IP)n仅要求部分决策变量的取值为整数，则称为混合整数规划(Mixed IP)n要求决策变量只取0或1值，则称0-1规划(0-1 Programming) 整数线性规划数学模型的一般形式：且部分或全部为整数或 n)1.2(j 0)2 . 1( )min(max11jnjijijnjjjxmibxaxcZZ人员安排规划某服务部门各时段某服务部门各时段( (每每2 2小时为一时

2、段小时为一时段) )需要的服务人数如表：需要的服务人数如表：解：设第j 时段开始时上班的服务员人数为xj 第 j 时段来上班的服务员将在第j+3 时段结束时下班，故决策变量有x1,x2,x3,x4,x5 。 二、二、0-10-1规划规划)2 , 1(01iyi若不建工厂若建工厂 )2 , 1(1 , 0)4 , 3 , 2 , 1,(0200200600400150300400350.15001200min244434241134333231242322211413121144342414433323134232221241312111414121iyjixyxxxxyxxxxxxxxxxxx

3、xxxxxxxxxxxxxxxxtsyyxcziijijijij混合整数规划问题混合整数规划问题且为整数0,13651914max21212121xxxxxxxxZ首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。0,13651914max21212121xxxxxxxxZx x1 1x x2 23 33 3(3/2,10/3)(3/2,10/3)5x1 +7 x2 =352x1 + x2 =9x1x2123125344)972,913(分支定界法分支定界法 LandDoig和和Dakin于于60年代提出年代提出一种隐枚举法,用来解纯整数规划及混合整数规划纯整数规划及混合整数规划. 整

4、数规划的可行域是相应的线性规划松弛问题可行域的子集；因此，松弛问题最优解是整数规划最优解的一个界 （对于max，为上界；对于min，为下界）。 分析整数规划问题A对应的松弛问题B的最优解（对于max）：说明：该方法可计算机求解；在部分可行解中求解，计算量小于枚举法；对于大问题，计算量仍较大。例例取整数2121212121,0,35759256maxxxxxxxxxxxZ 第二步，定界过程。 这个解不满足整数约束，因此不是原整数规划的最优解。 因为这个问题是求最大化问题，前面说过整数规划是在线性规划的基础上增加了整数约束，现在不考虑整数约束求得这个解，其目标函值 Z是原整数规划目标函数的上界，记

5、 。由于 必然满足整数约束，其目标函数值为0，确定为现有下界，记 。 第三步，分枝过程，将不满足整数约束的变量x1进行分枝，构造两个新的约束条件：这样就把相应的线性规划的可行域分成两个部分5 x2 1 2 5 3 4 x1 1 2 3 4 2x1 + x2 =9 5x1 +7x2 =35 17(3,2 )99121 623,2,3277L PxxZ：120 1753,2,3 2999L PxxZ：122 4,1,29LPxxZ：1233,2,2 8L PxxZ：124442,3 ,3 155L PxxZ：125462 ,3,2 977L PxxZ：6L P：无 可 行 解1272 ,3 ,2

6、7L PxxZ：128221,4 ,2 855L PxxZ：x13x1 4x22x2 3x12x1 3x23x2 409532下界：上界：297232下界：上界：295431下界：上界：297629下界：上界：2929下界：上界： 且且全全为为整整数数0,4 30 652 5min211212121xxxxxxxxxZ 0,4 30 652 5min211212121xxxxxxxxxZLPLPIPIPx x1 1x x2 23 3(18/11,40/11)(18/11,40/11)2 21 11 12 23 3x x1 118/11, 18/11, x x2 2 =40/11 =40/11Z

7、=Z=218/11(218/11(19.8)19.8)即即Z Z 也是也是IPIP最小值的下限。最小值的下限。对于对于x x1 118/111.6418/111.64，取值取值x x1 1 1 1， x x1 1 2 2对于对于x x2 2 =40/11 3.64 =40/11 3.64，取，取值值x x2 2 3 3 ，x x2 2 4 4先将（先将（LPLP）划分为（）划分为（LP1LP1）和）和（LP2LP2）, ,取取x1 1, x1 2x1 1, x1 2且为整数0,1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ且为整数0,2 4 30 652 )

8、2(5min2111212121xxxxxxxxIPxxZx1x233(18/11,40/11)11BAC同理求同理求LP2,LP2,如图所示。在如图所示。在C C 点点取得最优解。即取得最优解。即: :x x1 12, 2, x x2 2 =10/3, =10/3, Z Z(2)(2)56/356/318.7 18.7 ZZ(2)(2) Z Z(1)(1)16 16 原问题有比原问题有比1616更小的最优更小的最优解，但解，但 x2 x2 不是整数，故继续不是整数，故继续分支。分支。且为整数0,3 2 4 30 652 )21(5min21211212121xxxxxxxxxIPxxZ且为整

9、数0,4 2 4 30 652 )22(5min21211212121xxxxxxxxxIPxxZ分别求出分别求出LP21LP21和和LP22LP22的最优解的最优解x1x233(18/11,40/11)11BACD先求先求LP21,LP21,如图所示。此时如图所示。此时D D 在在点取得最优解。点取得最优解。即即 x x1 112/52.4, x12/52.4, x2 2 =3, =3, Z Z(21)(21)-87/5-17.4 Z-87/5-17.4 Z(211) 如对如对LP212继续分解，其最小继续分解，其最小值也不会低于值也不会低于15.5 ，问题探，问题探明明,剪枝。剪枝。LP1

10、x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22无可无可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13 且且均均取取整整数数,0,255.22108.02.134max21212121xxxxxxxxZ)(0,255 . 22108 . 02 . 134max021212121LPxxxxxxstxxZ 1010108 . 02 . 121

11、 xx255 . 2221 xx松弛问题松弛问题LPLP0 0的最优解的最优解X X=(3.57,7.14),Z=(3.57,7.14),Z0 0=35.7=35.7x1x2oABC得到两个线性规划及增加约束4311xx10 x2oABC 0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255 . 22108 . 02 . 1:234max211212121xxxxxxxLPxxZLP2:X=(4,6.5),Z2=35.510 x1x2oABCLP1LP2134LP21:X=

12、(4.33,6),Z21=35.33 0,64255 . 22108 . 02 . 1:2134max2121212121xxxxxxxxLPxxZ，不可行，得到线性规划，显然及进行分枝，增加约束选择目标值最大的分枝7762222xxxLP6不可行72x 0,74255 . 22108 . 02 . 1:2234max2121212121xxxxxxxxLPxxZ，10 x1x2oACLP134可可行行域域是是一一条条线线段段即即，, 40,464255 . 22108 . 02 . 1:21134max121121212121 xxxxxxxxxxLPxxZ：及，得线性规划及进行分枝，增加约

13、束，选择由于212211542111121LPLPxxLPZZ6 0,65255 . 22108 . 02 . 1:21234max2121212121xxxxxxxxLPxxZ，LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22无可行解无可行解x

14、27课后练习：课后练习：12121212 max 85 1.56. .2 6,0,zxxxxstxxx x且为整数12341231241234 m ax 8500 2 3 12. 2 6, , ,0zxxxxxxxstxxxx x x x 计算步骤举例求解整数规划模型：化标准型：）分析：分析：第一步第一步，如果原问题的系数有小数，将其化为整数。如第一个约束化为122312xx。(15/4, 3/2)X 37.5z松弛问题的最优解，非整数规划的可行解。1x1341333884xxx134133(0)(0)(3)884xxx1343133488xxx 343130488xx在最终单纯形表中选择分数

15、部分最大的基变量列出该行约束：将所有系数分成整数与一个正的分数之和：将分数部分移至右端：分析右边的分数项，其取值小于1，即得到了Gomory约束：引入0-1变量的实际问题0-1型整数规划的解法 如果线性规划中的所有决策变量的取如果线性规划中的所有决策变量的取值只能取值只能取0 0、1 1，则这类线性规划问题是，则这类线性规划问题是一种特殊的整数规划问题称之为一种特殊的整数规划问题称之为0-10-1规划规划，把只能取，把只能取0 0或或1 1值的变量称为值的变量称为0-10-1变量。变量。0-10-1变量是一种逻辑变量。变量是一种逻辑变量。 n, 2 , 1j ,A0A1xm, 2 , 1i,b

16、),(xa. t . sxc)x( fmax(min)jn1jijijn1jjj不不成成立立时时当当条条件件成成立立时时当当条条件件其其数学模型数学模型如下：如下：本节先介绍引入本节先介绍引入0-1变量的变量的实际问题实际问题： 投资场所（项目）的选定投资场所（项目）的选定相互排斥的约束条件相互排斥的约束条件关于固定费用的问题关于固定费用的问题 然后，再研究然后，再研究0-1规划问题的一般解法规划问题的一般解法-隐枚举法隐枚举法。7 , 2 , 1iA, 0A, 1xiii 点点没没有有被被选选用用当当点点被被选选用用当当令令 10 x1xx1xx)85(2xxxBxbxczmaxi76543

17、2171iii71iii约约束束条条件件目目标标函函数数：（1 1）两个约束条件中只有一个起作用）两个约束条件中只有一个起作用 当采用车运方式当采用车运方式当采用船运方式当采用船运方式, 0, 1y例：例：利用利用0 0 1 1变量将下题表示成一般线性约束条件变量将下题表示成一般线性约束条件x x 1 1+x +x 2 2 2 2 或或 2 2x x 1 1+3x +3x 2 2 5 ; 5 ; 为为非非常常大大的的正正数数）（或或MyyyyMyxxMyxxa10,1)1(532)1(2)(2121221121解：解： 为为非非常常大大的的正正数数）（或或MyyyyMyxxMyxxa10,1)

18、1(532)1(2)(2121221121 10,1753)(321321321或或yyyyyyyyyxb变量变量 x x 只能取值只能取值0 0、3 3、5 5 或或 7 7 中的一个中的一个 ; ; 10,17530321, 032103210或或或或yyyyyyyyyyyyx例：例：利用利用0 0 1 1变量将下题表示成一般线性约束条件变量将下题表示成一般线性约束条件 10,1753)(321321321或或yyyyyyyyyxb50(1)( )00 1()xyMxMycxyM 或或非非常常大大的的正正变量变量x x 或等于或等于 0 0，或，或 50 ;50 ;例：例：利用利用0 0

19、1 1变量将下题表示成一般线性约束条件变量将下题表示成一般线性约束条件50(1)( )00 1()xyMxMycxyM 或或非非常常大大的的正正1121122212122 (1)1 (1)2 (1)( )4 (1)1,01xyMxyMxyMdxyMyyMy y （ 非非常常大大的的正正）或或若若 x x1 1 2 2，则，则 x x2 2 1 1，否则，否则x x2 2 4 ; 4 ;例：例：利用利用0 0 1 1变量将下题表示成一般线性约束条件变量将下题表示成一般线性约束条件1121122212122 (1)1 (1)2 (1)( )4 (1)1,01xyMxyMxyMdxyMyyMy y

20、（ 非非常常大大的的正正）或或 非非常常大大的的正正数数）（或或MyyyyyyyyMyxxMyxMyxMyxxe10,2)1 (6)1 (2)1 (2)1 (5)(432143214433321121以下四个约束条件中至少满足两个以下四个约束条件中至少满足两个x x1 1+x+x2 2 5 5， x x1 1 2 2， x x3 3 2 2， x x3 3+x+x4 4 6 6 非非常常大大的的正正数数）（或或MyyyyyyyyMyxxMyxMyxMyxxe10,2)1 (6)1 (2)1 (2)1 (5)(432143214433321121例：例：利用利用0 0 1 1变量将下题表示成一般

21、线性约束条件变量将下题表示成一般线性约束条件项目投资选择项目投资选择有有600万元投资万元投资5个项目，收益如表，求利润最大的方案？个项目，收益如表，求利润最大的方案？ 互斥约束问题互斥约束问题 例如关于煤资源的限制，其约束条件为： 企业也可以考虑采用天然气进行加热处理： 这两个条件是互相排斥的。引入01变量y，令 互斥问题可由下述的条件来代替，其中M是充分大的数。 租赁生产问题),.,2 , 1(01njjjxj不投资对项目投资对项目投资问题可以表示为：投资问题可以表示为： ）（或或者者nxxxxxxxxBxatsxczjnjjjnjjj, 2 , 1j1021.max765431211隐枚

22、举法的步骤：隐枚举法的步骤： 1.找出任意一可行解，目标函数值为找出任意一可行解，目标函数值为Z0 2. 原问题求最大值时，则增加一个约束原问题求最大值时，则增加一个约束1 1220(*)nnc xc xc xZ当求最小值时，上式改为小于等于约束当求最小值时，上式改为小于等于约束 3. 列出所有可能解，对每个可能解先检验式（列出所有可能解，对每个可能解先检验式（*），若满足再），若满足再检验其它约束，若不满足式（检验其它约束，若不满足式（*），则认为不可行，若所有约束），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值都满足，则认为此解是可行解，求出目标值 4. 目标函数值最大（

23、最小）的解就是最优解目标函数值最大（最小）的解就是最优解 【例例】用隐枚举法求解下面问题用隐枚举法求解下面问题 4 , 3 , 2 , 11010542324653103245326max43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或【解解】（1）不难看出，当所有变量等于）不难看出，当所有变量等于0或或1的任意组合时，的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。还能通过观察得到从约束条件中去掉。还能通过观察得到X0(1，0，0，1)是一是一个可行解，目标值个

24、可行解，目标值Z0=11是该问题的下界是该问题的下界,增加下面约束增加下面约束1153264321xxxx)9 . 3()9 . 3()9 . 3()9 . 3(4 , 3 , 2 , 110105423246531153265326max43214321432143214321dcbajxxxxxxxxxxxxxxxxxxxxxZj，或(2) 列出变量取值列出变量取值0和和1的组合，共的组合，共2416个，分别代入约束条件个，分别代入约束条件判断是否可行。首先判断式（判断是否可行。首先判断式（3.9a）是否满足，如果满足，接下）是否满足，如果满足，接下来判断其它约束，否则认为不可行。来判断其

25、它约束，否则认为不可行。 (3) 由表知，由表知，该该问题的最优解：问题的最优解：X（1，0，1，1），最优值），最优值Z14 选择不同的初始可行解，计算量会不一样。一般地，选择不同的初始可行解，计算量会不一样。一般地，当目标函数求最大值时，首先考虑目标函数系数最大当目标函数求最大值时，首先考虑目标函数系数最大的变量等于的变量等于1。当目标函数求最小值时，先考虑目标。当目标函数求最小值时，先考虑目标函数系数最大的变量等于函数系数最大的变量等于0。 解：(1)观察一个可行解x1 = 1 x2 = x3 = 0 此时，z = 3 (2) (2)增加一个过滤条件增加一个过滤条件 3x3x1 1-2x

26、-2x2 2+5x+5x3 33 3 * * 最优解：最优解：x x1 1* * = 1 x = 1 x2 2* * = 0 x = 0 x3 3* * = 1 = 1 此时，此时，z z* * = 8 = 8例： 用穷举法解0-1整数规划1 , 0,322228232243max32132132321321321xxxxxxxxxxxxxxxxxS321xxx最优解为最优值为S=3., 0, 0, 1321xxx解：对于这个问题，很容易建立一个数学模型的，解：对于这个问题，很容易建立一个数学模型的， 引入引入0-1变量变量 ， 当当 =1时，表示分配第时，表示分配第i个人完成第个人完成第j项

27、任务项任务 当当 =0时，表示不分配第时，表示不分配第i个人完成第个人完成第j项任务项任务 一项任务只由一个人完成，有如下约束一项任务只由一个人完成，有如下约束 一人只能完成一项任务，有如下约束一人只能完成一项任务，有如下约束 设设 工作人做不分配第工作人做分配第jijixij01数学模型如下：数学模型如下：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为： 1111444342413433323124232221

28、14131211xxxxxxxxxxxxxxxx 111144342414433323134232221241312111xxxxxxxxxxxxxxxx：4 ,3,2, 110 jixij、，或或指派问题的数学模型:nBBB21nAAA21nnnnnnccccccccc212222111211要求每个工人有一项工作,每项工作只有一个工人来作.如何安排使总的效益最好., 2 , 1, .0,1njijixjixijij项工作个人不去做第表示第项工作个人去做第表示分配第设10., 2 , 11., 2 , 11min1111或ijniijnjijninjijijxnjxnixxcS二、指派问题的

29、解法匈牙利法匈牙利法(1955年W.W.Kuhn求解分配问题,使用了匈牙利数学家Kuhn的两个定理,故称匈牙利解法. .)()(,配问题的最优解相同配问题的最优解与原分目标函数系数矩阵的分为则以矩阵的最小元素后得到的新列该行各元素分别减去列中某一行是在系数矩阵是分配问题目标函数的设BAbBaAnnijnnij 若方阵中的一部分元素为零,一部分非零,则覆盖方阵内所有零元素的最小直线数,等于方阵内位于不同行不同列的零元素的最多个数。根据定理1,2设计出分配问题的一般解法:第一步:将效率矩阵A的每一行各减去该行的最小元素,再从新矩阵中的各列减去该列的最小元素,得矩阵B;第二步:从有零元素最少的行(列

30、)开始,圈出零元素后划去同行(列)的其他零元素.若被圈出的零元素恰好布满B的不同行不同列,则将这些零元素改为1,其余元素改为0,得最优分配矩阵.否则转第三步;分配问题的一般解法详解: 对没有被圈出零的打”; 对有的行上所有有零元素的列打; 再对打的列上有被圈出零的行打;第三步:根据定理2作出覆盖零元素的最小直线集: 重复 ,直到得不出新打的行,列为止; 对没有打的行画横虚线;对所有打的列画纵虚线,这就是覆盖所有零元素的最小直线集,转第四步;第四步:在没有被覆盖的元素中找出最小元素,对没有画直线的行上各元素都减去这个最小元素;对画有直线的列上各元素都加上这个最小元素,这样得到的矩阵如果不同行不同

31、列上都有被圈出的零,则可将其换为1,其余元素换为0,最优分配方案求出,否则转第三步.例： 某配送中心有 四项配送任务,分配给 四辆汽车 去完成,每辆汽车完成各项配送任务的时间如下表,问如何分配任务使总的用时最少.4321,AAAA4321,BBBB4321AAAA4321BBBB解:取出效率矩阵进行运算.9118713161491514410413152A794224在B中找出位于不同行,不同列的四个零元素,作法如下:24104750111006211130B00102350960607130 先从零元素最少的行(列)开始,选取一个零元素将其圈起来,同时将零元素所在行,列的其余零元素划去; 如

32、果恰有四个被圈起来的零元素,处于不同行不同列,则将这些零改为1,其余元素改为0,得到最优分配方案.00102350960607130B00000100000100101000B最优分配方案是: .,34132241ABABABAB最优值(即总用时)是minS=4+4+9+11=28.9118713161491514410413152A注意:对于 来说不是最优方案,但对整体来说达到最优,这就是运筹学思想.4B例：工厂有 五个独立车间,该厂计划生产五种产品 ,由于产品性质和各车间设备不同,每个车间生产各种产品消耗的资金(万元)不同,如下表.问如何安排生产任务,使总的耗资最少.54321,AAAAA

33、54321,BBBBB54321AAAAA54321BBBBB解:610710410661415121412177666989797124676726360400895751000003220205263604008957510000032202052636040089575100000322020500414040081135380000342020722 , 6 , 3 , 6 , 5 , 7 , 5 ,10min),(),(),(),(),(5534134221BABABABABA).(3266767min万元S4347511576469637964589117129118957 713

34、2036304520142405263402-1 -2 5032015304310140305242402 50320153043101403052424022 2）试指派（找独立）试指派（找独立0 0元素）元素） 独立独立0 0元素的个数元素的个数l l4545，故画直线调整矩阵。，故画直线调整矩阵。 5032015304310140305242402选择直线外的最小元素选择直线外的最小元素为为1；直线外元素减；直线外元素减1，直线交点元素加直线交点元素加1，其，其他保持不变。他保持不变。 5033004203310240306231301l =m=4 n=5选择直线外最小元素为选择直线外最小元素为1，直线外元素减直线外元素减1，直线交点，直线交点元素加元素加1，其他保持不变，其他保持不变，得到新的系数矩阵。得到新的系数矩阵。 6044003202300230206130300总费用为总费用为=5+7+6+6+4=28=5+7+6+6+4=28注：此问题有多个最优解注：此问题有多个最优解 6044003202300230206130300总费用为总费用为=7+9+4+3+5=28=7+9+4+3+5=28 6044003202300230206130300总费用为总费用为=8+9+4+3+4=28=8