数学建模讲义7省名师优质课赛课获奖课件市赛课一等奖课件.ppt

主讲人主讲人:穆学文穆学文西安电子科技大学数学系西安电子科技大学数学系Email:数学建模讲义数学建模讲义第1页数学建模专题讲座数学建模专题讲座最优化模型最优化模型 -线性整数规划线性整数规划 第2页线性整数规划线性整数规划1、建模引例。、建模引例。2、线性整数规划模型、线性整数规划模型3 3、线性整数规划主要算法。、线性整数规划主要算法。4、0-1规划选讲规划选讲第3页 1、建模引例、建模引例例例1:1:某某厂厂拟拟用用火火车车装装运运甲甲、乙乙两两种种货货物物集集装装箱箱，每每箱箱体体积积、重重量量、可可赢赢利利润润以以及及装装运运所所受受限限制制以下：以下：货物集装箱货物集装箱 体积体积(米米3 3)重量重量(百斤百斤)利润利润(百元百元)甲甲 5 2 20 5 2 20 乙乙 4 5 10 4 5 10 托运限制托运限制 24 24 13 13 问问两两种种货货物物各各装装运运多多少少箱箱，可可使使取取得得利利润润最最大大？第4页 设甲、乙两种货物装运箱数分别为设甲、乙两种货物装运箱数分别为x x1 1和和x x2 2。显然，。显然，x x1 1、x x2 2都要求为整数都要求为整数,于是可建立整数规划模型以下：于是可建立整数规划模型以下：Max z Max z20 x20 x1 1+10 x+10 x2 2 (1)(1)5x 5x1 1+4x+4x2 224 (2)24 (2)2x 2x1 1+5x+5x2 213 (3)13 (3)x x1 1,x,x2 20 (4)0 (4)x x1 1,x,x2 2为整数为整数 (5)(5)第5页 是是不不是是可可经经过过把把不不考考虑虑整整数数要要求求求求得得最最优优解解经过经过“化整化整”得到满足整数要求最优解呢？得到满足整数要求最优解呢？它和线性规划问题区分在于条件它和线性规划问题区分在于条件(5)(5)。此此例例可可解解得得x x1 1=4.8,x=4.8,x2 2=0=0，凑凑整整为为x x1 1=5,x=5,x2 2=0=0，这这就就破破坏坏了了条条件件(2)(2)，因因而而不不是是可可行行解解；如如截截断断小小数数变变为为x x1 1=4,x=4,x2 2=0=0，这这当当然然满满足足全全部部约约束束条条件件，但但不不是是最最 优优 解解，因因 为为 对对 x x1 1=4,x=4,x2 2=0=0有有 z z 8080，而而 对对x x1 1=4,x=4,x2 2=1=1（也也是是可可行行解解）有有z z9090。所所以以要要专专门门研研究整数规划解法。究整数规划解法。第6页整数规划是一类要求变量取整数值整数规划是一类要求变量取整数值数学数学规规划，可分成线性和非线性两类。划，可分成线性和非线性两类。依依据据变变量量取取值值性性质质，又又能能够够分分为为全全整整数数规规划，混合整数规划，划，混合整数规划，0-1整数规划等。整数规划等。整整数数规规划划是是数数学学规规划划中中一一个个较较弱弱分分支支，当当前前只只能能解解中中等等规规模模线线性性整整数数规规划划问问题题，而而非线性整数规划问题，还没有好方法。非线性整数规划问题，还没有好方法。整数规划介绍整数规划介绍第7页整数规划整数规划(IP)普通数学模型普通数学模型:Max(min)Z=cjxjs.t.aijxj bi(i=1,2,m)xj 0 且部分或全部是整数且部分或全部是整数2.线性整数规划模型线性整数规划模型第8页解法概述解法概述当人们开始接触整数规划问题时，常会有以当人们开始接触整数规划问题时，常会有以下两种初始想法：下两种初始想法：因为可行方案数目有限，所以经过一一比较后，因为可行方案数目有限，所以经过一一比较后，因为可行方案数目有限，所以经过一一比较后，因为可行方案数目有限，所以经过一一比较后，总能求出最好方案，比如，背包问题充其量有总能求出最好方案，比如，背包问题充其量有总能求出最好方案，比如，背包问题充其量有总能求出最好方案，比如，背包问题充其量有2 2n-1n-1种方式；连线问题充其量有种方式；连线问题充其量有种方式；连线问题充其量有种方式；连线问题充其量有n n!种方式；实际上这种种方式；实际上这种种方式；实际上这种种方式；实际上这种方法是不可行。构想计算机每秒能比较方法是不可行。构想计算机每秒能比较方法是不可行。构想计算机每秒能比较方法是不可行。构想计算机每秒能比较10000001000000个个个个方式，那么要比较完方式，那么要比较完方式，那么要比较完方式，那么要比较完2020!（大于（大于（大于（大于2*102*101818）种方式，大）种方式，大）种方式，大）种方式，大约需要约需要约需要约需要800800年。比较完年。比较完年。比较完年。比较完2 26060种方式，大约需要种方式，大约需要种方式，大约需要种方式，大约需要360360世纪。世纪。世纪。世纪。第9页先放弃变量整数性要求，解一个线性规划问先放弃变量整数性要求，解一个线性规划问先放弃变量整数性要求，解一个线性规划问先放弃变量整数性要求，解一个线性规划问题，然后用题，然后用题，然后用题，然后用“四舍五入四舍五入四舍五入四舍五入”法取整数解，这种方法取整数解，这种方法取整数解，这种方法取整数解，这种方法，只有在变量取值很大时，才有成功可能性，法，只有在变量取值很大时，才有成功可能性，法，只有在变量取值很大时，才有成功可能性，法，只有在变量取值很大时，才有成功可能性，而当变量取值较小时，尤其是而当变量取值较小时，尤其是而当变量取值较小时，尤其是而当变量取值较小时，尤其是0-10-1规划时，往规划时，往规划时，往规划时，往往不能成功往不能成功往不能成功往不能成功。例例例例2 2 求以下问题：求以下问题：求以下问题：求以下问题：Max Z=3x Max Z=3x1 1+13x+13x2 2 s.t.2x s.t.2x1 1+9x+9x2 2 40 40 11x 11x1 1-8x-8x2 2 82 82 x x1 1,x,x2 2 0,0,且取整数值且取整数值且取整数值且取整数值第10页O 1 2 3 4 5 6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)AD可行域可行域可行域可行域OABDOABD内整数点，放弃整数要求后，最优解内整数点，放弃整数要求后，最优解内整数点，放弃整数要求后，最优解内整数点，放弃整数要求后，最优解B(9.2,2.4)ZB(9.2,2.4)Z0 0=58.8=58.8，而原整数规划最优解，而原整数规划最优解，而原整数规划最优解，而原整数规划最优解I(2,4)I(2,4)Z Z0 0=58=58，实际上，实际上，实际上，实际上B B附近四个整点附近四个整点附近四个整点附近四个整点(9,2)(10,2)(9,3)(10,3)(9,2)(10,2)(9,3)(10,3)都不是原规划最优解都不是原规划最优解都不是原规划最优解都不是原规划最优解。第11页3 线性整数规划解法线性整数规划解法枚举法枚举法 仅仅对极小规模问题有效仅仅对极小规模问题有效分支定界法分支定界法 应用比较广泛，对中小规模问题应用比较广泛，对中小规模问题割平面法割平面法 应用比较广泛，对中小规模问题应用比较广泛，对中小规模问题第12页 分分枝枝定定界界法法是是2020世世纪纪6060年年代代由由Land-DoigLand-Doig和和DakinDakin等等人人提提出出。这这种种方方法法既既可可用用于于纯纯整整数数规规划划问问题题，也也可可用用于于混混合合整整数数规规划划问问题题，而而且且便便于于用用计计算算机机求求解解，所所以以很很快快成成为为解解整整数数规规划划最最主要方法。主要方法。3.1 分枝定界法分枝定界法第13页 分枝定界法步骤分枝定界法步骤 原问题松驰问题：任何整数规划（原问题松驰问题：任何整数规划（原问题松驰问题：任何整数规划（原问题松驰问题：任何整数规划（IPIP），凡放弃），凡放弃），凡放弃），凡放弃一些约束条件（如整数要求）后，所得到问题（一些约束条件（如整数要求）后，所得到问题（一些约束条件（如整数要求）后，所得到问题（一些约束条件（如整数要求）后，所得到问题（P P）都称为（都称为（都称为（都称为（IPIP）松驰问题。普通求解对应松驰问题，可）松驰问题。普通求解对应松驰问题，可）松驰问题。普通求解对应松驰问题，可）松驰问题。普通求解对应松驰问题，可能会出现下面几个情况：能会出现下面几个情况：能会出现下面几个情况：能会出现下面几个情况：若所得最优解各分量恰好是整数，则这个解也是原若所得最优解各分量恰好是整数，则这个解也是原若所得最优解各分量恰好是整数，则这个解也是原若所得最优解各分量恰好是整数，则这个解也是原整数规划最优解，计算结束整数规划最优解，计算结束整数规划最优解，计算结束整数规划最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行若松驰问题无可行解，则原整数规划问题也无可行若松驰问题无可行解，则原整数规划问题也无可行若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。解，计算结束。解，计算结束。解，计算结束。若松驰问题有最优解，但其各分量不全是整数，则若松驰问题有最优解，但其各分量不全是整数，则若松驰问题有最优解，但其各分量不全是整数，则若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划最优解，转下一步。这个解不是原整数规划最优解，转下一步。这个解不是原整数规划最优解，转下一步。这个解不是原整数规划最优解，转下一步。第14页从不满足整数条件基变量中任选从不满足整数条件基变量中任选从不满足整数条件基变量中任选从不满足整数条件基变量中任选 一个一个一个一个x xl l进进进进行分枝，它必须满足行分枝，它必须满足行分枝，它必须满足行分枝，它必须满足x xl l x xl l 或或或或x xl l x xl l +1+1中中中中一个，把这两个约束条件加进原问题中，形一个，把这两个约束条件加进原问题中，形一个，把这两个约束条件加进原问题中，形一个，把这两个约束条件加进原问题中，形成两个互不相容子问题（两分法）。成两个互不相容子问题（两分法）。成两个互不相容子问题（两分法）。成两个互不相容子问题（两分法）。定界：把满足整数条件各分枝最优目标函定界：把满足整数条件各分枝最优目标函定界：把满足整数条件各分枝最优目标函定界：把满足整数条件各分枝最优目标函数值作为上（下）界，用它来判断分枝是保数值作为上（下）界，用它来判断分枝是保数值作为上（下）界，用它来判断分枝是保数值作为上（下）界，用它来判断分枝是保留还是剪枝。留还是剪枝。留还是剪枝。留还是剪枝。剪枝：把那些子问题最优值与界值比较，剪枝：把那些子问题最优值与界值比较，剪枝：把那些子问题最优值与界值比较，剪枝：把那些子问题最优值与界值比较，凡不优或不能更优分枝全剪掉，直到每个分凡不优或不能更优分枝全剪掉，直到每个分凡不优或不能更优分枝全剪掉，直到每个分凡不优或不能更优分枝全剪掉，直到每个分枝都查清为止。枝都查清为止。枝都查清为止。枝都查清为止。第15页例例3 求解问题求解问题 Max z=40 x1+90 x2 9x1+7x2 56 7x1+20 x270 x1,x20,整数整数R0:z0=356 x1=4.81 x2=1.82R1:z1=349 x1=4.00 x2=2.10R2:z2=341 x1=5.00 x2=1.57R12:z12=327x1=1.42x2=3.00 x23R11:z11=340 x1=4.00 x2=2.00R21:z21=308x1=5.44x2=1.00R22:无可无可行解行解x1 4x1 1x15x12问题问题R0为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x270 x1,x20问题问题R2为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 5 x1,x2 0问题问题R1为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x1,x20 x2 2问题问题R11为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 2 x1,x20问题问题R12为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 3 x1,x2 0第16页 割平面法基础依然是用解线性规划方法去解整数规割平面法基础依然是用解线性规划方法去解整数规划问题。首先不考虑变量为整数这一条件，但增加线性划问题。首先不考虑变量为整数这一条件，但增加线性约束条件（几何术语，称为约束条件（几何术语，称为割平面割平面），使得原可行解域），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解。切除结果使整数解可能成为顶点何整数可行解。切除结果使整数解可能成为顶点 分枝定解法是对原问题可行解域进行了切割，切分枝定解法是对原问题可行解域进行了切割，切割方法是对取非整数解相邻整数作附加约束，约束方割方法是对取非整数解相邻整数作附加约束，约束方程简单，但子问题因为分枝增多而成指数增加。程简单，但子问题因为分枝增多而成指数增加。关键：关键：怎样找到割平面约束方程怎样找到割平面约束方程，使切割后最终得到，使切割后最终得到这么可行解域，它一个整数坐标顶点恰好是问题最优这么可行解域，它一个整数坐标顶点恰好是问题最优解。解。3.2 割平面法割平面法第17页割平面法步骤：割平面法步骤：（1）去掉整数约束，用单纯形法求解。若最优）去掉整数约束，用单纯形法求解。若最优解是整数，停顿计算，不然转第（解是整数，停顿计算，不然转第（2）步。）步。（2）寻求附加条件（割平面方程），其方法后述。）寻求附加条件（割平面方程），其方法后述。（3）将割平面方程标准化后加到约束方程组中求）将割平面方程标准化后加到约束方程组中求解，如所得最优解仍为非整数，则转到第（解，如所得最优解仍为非整数，则转到第（2）步继）步继续进行，直到找到最优整数解为止。续进行，直到找到最优整数解为止。第18页 决议变量仅取为决议变量仅取为0或或1整数规划问题。整数规划问题。xi 是是0-1变量表示：变量表示：xi 1，xi 0 4 0-1 规划规划 把上约束加到约束方程组中就和普通整数规划把上约束加到约束方程组中就和普通整数规划约束条件一致了。故约束条件一致了。故0-1型整数可用普通求整数规划型整数可用普通求整数规划方法求解，但方法求解，但0-1型整数规划是整数规划特殊情型整数规划是整数规划特殊情形，所以，有特殊解法。形，所以，有特殊解法。4.1 隐枚举法隐枚举法第19页 【例【例4】某厂拟在】某厂拟在A、B、C、D、E五个城市中建立五个城市中建立若干个产品经销联营点，各处设点都需资金、人力、设若干个产品经销联营点，各处设点都需资金、人力、设备等，需求量以及能提供利润各处不一样，有些点也可备等，需求量以及能提供利润各处不一样，有些点也可能赔本，但却能取得贷款和人力等。设数据已知（在下能赔本，但却能取得贷款和人力等。设数据已知（在下面建模中给出），为使总收益最大，问厂方应作出何种面建模中给出），为使总收益最大，问厂方应作出何种最优选点决议？最优选点决议？上述各城市是否被选，可用决议变量上述各城市是否被选，可用决议变量xi表示，表示，xi=1表示被选，不然表示被选，不然xi=0，依据已知数据可建数模以下，依据已知数据可建数模以下:第20页解题分析：解题分析：仅从目标函数看，为使总收益最大，应取仅从目标函数看，为使总收益最大，应取x1=x2=x3=1，x4=x5=0即选即选A、B、C三城建联营点三城建联营点 不不选选D、E，这时总收益为，这时总收益为Z=17.8（十万元）；但从约（十万元）；但从约束条件来看，这个决议不可行。假如哪个城市都不设束条件来看，这个决议不可行。假如哪个城市都不设点，即点，即xj=0(j=1,2,3,4,5)，从约束条件看都满足，但，从约束条件看都满足，但Z=0，这显然不是一个最优决议，终究应选那些城市，这显然不是一个最优决议，终究应选那些城市建点呢建点呢?每个城市都有可能入选和不入选，即每个城市都有可能入选和不入选，即xj取值有取值有0和和1两种状态；有两种状态；有5个变量，这么个变量，这么0，1组合就有组合就有25=32个。把个。把每种组合列出，代入约束条件检验是否可行，可行解代每种组合列出，代入约束条件检验是否可行，可行解代入目标函数比较大小得出最优解入目标函数比较大小得出最优解-枚举法，繁琐枚举法，繁琐!第21页 实际不需要列出全部可行组合。实际不需要列出全部可行组合。兴趣兴趣-使使目标函数最优目标函数最优变量可行变量可行组合组合。1.按目标函数值从优到劣（本例，从大到小），次序按目标函数值从优到劣（本例，从大到小），次序列出变量组合；列出变量组合；过滤性条件过滤性条件2.逐一检验变量组合可行性，最先满足全部约束条件逐一检验变量组合可行性，最先满足全部约束条件变量组合就是最优解；变量组合就是最优解；3.而劣于最优解组合即使可行，也不用列出和检验；而劣于最优解组合即使可行，也不用列出和检验；4.相当于把枚举法得出全部非优组合隐去不算了，相当于把枚举法得出全部非优组合隐去不算了，故称为隐枚举法。故称为隐枚举法。第22页隐枚举法解题步骤：隐枚举法解题步骤：（1）变换目标函数和约束条件）变换目标函数和约束条件 价值系数价值系数cj前符号统一前符号统一 在目标函数在目标函数 求求极大极大时，统一带时，统一带负号负号；求极小值时，；求极小值时，统一带正号。在不满足上述要求时，用统一带正号。在不满足上述要求时，用 代代入目标函数。入目标函数。本例求极大值，本例求极大值，x1,x2,x3前符号不满足，用前符号不满足，用代入目标函数和约束条件；代入目标函数和约束条件；按按 值从小到大排列决议变量项值从小到大排列决议变量项本例变换结果以下：本例变换结果以下：第23页 本例变换结果以下：本例变换结果以下：（2）用目标函数值探索法求最优解）用目标函数值探索法求最优解 由公式由公式 ，当，当 时，时，Z=Z0=17.8为上限。为上限。假如假如 这个组合又满足全部约束条件，则它这个组合又满足全部约束条件，则它为最优解为最优解;不然，不然，按劣于按劣于Z0组合解方向组合解方向探索可行解。探索可行解。按按 由小到大逐项计算组合解由小到大逐项计算组合解 值及其对应值及其对应Z值，代入约束条件检验可行性，如全部满足，即为最优值，代入约束条件检验可行性，如全部满足，即为最优解。解。最大值最大值第24页目标探索法计算过程示于下表：目标探索法计算过程示于下表：Z值值组合解组合解是否满足约束是否满足约束是否可是否可行解行解x5x4017.800000否否1.516.310000否否2.015.801000否否3.514.311000否否3.814.000100否否4.513.300010否否5.312.510100是是 最优解为：最优解为：x1=1,x2=0,x3=1,x4=0,x5=1,即在即在A,C,E三三个城市设联营点，可获最大收益个城市设联营点，可获最大收益12.5（十万元）。（十万元）。第25页4.2 4.2 分配问题和匈牙利法分配问题和匈牙利法Assignment Problem 有有n项项任任务务，恰恰好好n个个人人负负担担，第第i 人人完完成成第第j 项项任任务务花花费费(时时间间或或费费用用等等)为为cij，怎怎样样分分配配使使总总花花费最省？费最省？第第j项工作由一项工作由一个人做个人做第第i人做一项工人做一项工作作分配第分配第i人做第人做第j项工作项工作不分配第不分配第i人做第人做第j项工作项工作第26页 【例【例5】有四项任务需分配给甲、乙、丙、丁四有四项任务需分配给甲、乙、丙、丁四个人去做，这四个人都能负担上述四项任务，但完成个人去做，这四个人都能负担上述四项任务，但完成各项任务所需时间以下表所表示。问应怎样分配任务各项任务所需时间以下表所表示。问应怎样分配任务可使完成任务总工时最少？可使完成任务总工时最少？任务人员ABCD甲917167乙1271416丙8171417丁79119问题分析：引入决议变量问题分析：引入决议变量xij,第27页分配问题是分配问题是0-1规划问题。规划问题。因每个人仅能负担一项任务，每项任务也只能分因每个人仅能负担一项任务，每项任务也只能分配给一个人，所以上述问题线性规划模型为：配给一个人，所以上述问题线性规划模型为：满足该约束条件可行满足该约束条件可行解可写成矩阵形式解可写成矩阵形式分配问题是线性规划，又是运输问题。分配问题是线性规划，又是运输问题。第28页匈牙利算法步骤：匈牙利算法步骤：（1）变换系数矩阵，使其每行每列都出现）变换系数矩阵，使其每行每列都出现0元素。首元素。首先每行减去该行最小数，再每列减去该列最小数。先每行减去该行最小数，再每列减去该列最小数。-7-7-8-7-4(cij)(2)进行试分配，寻求最优解。进行试分配，寻求最优解。经第（经第（1）步变换后，系数矩阵每行每列都已经有）步变换后，系数矩阵每行每列都已经有了了0元素，但需找出元素，但需找出n个独立个独立0元素，为此，按以下步元素，为此，按以下步骤进行。骤进行。第29页 从只有一个从只有一个0元素行（列）元素行（列）0元素开始，给这个元素开始，给这个0元元素加圈，即作素加圈，即作，这表示对这行所代表人，这表示对这行所代表人，只有一个任，只有一个任务可分配。然后划去务可分配。然后划去所在列（行）其它所在列（行）其它0元素元素 ，记作，记作，这表示这列所代表任务已分配完，无须再考虑他人，这表示这列所代表任务已分配完，无须再考虑他人了。了。给只有一个给只有一个0元素列元素列(行行)元素加圈，记作元素加圈，记作；然后；然后划去划去所在行其它所在行其它0元素，即作元素，即作。重复进行重复进行、两步，直到全部两步，直到全部0元素都被圈出元素都被圈出或划掉为止。转第或划掉为止。转第步。步。若仍有没有圈出或划掉若仍有没有圈出或划掉0元素，且同行（列）元素，且同行（列）0元元素最少有素最少有2个，则找出个，则找出0元素闭回路，任选一个元素闭回路，任选一个0元素加元素加圈，破闭回路，直到全部圈，破闭回路，直到全部0元素都已圈出和划掉为止。元素都已圈出和划掉为止。第30页 若若元素数目等于矩阵阶数，那末，这分配问题元素数目等于矩阵阶数，那末，这分配问题最优解已经得到，不然转第（最优解已经得到，不然转第（3）步。）步。（3）作最少直线覆盖全部）作最少直线覆盖全部0元素，已确定该系数矩阵元素，已确定该系数矩阵能找到最多独立能找到最多独立0元素。为此按以下步骤进行：元素。为此按以下步骤进行：对没有对没有行打行打号；号；对已打对已打行中全部行中全部0元素所对应列打元素所对应列打号；号；再对打有再对打有列中列中元素所对应行打元素所对应行打号；号；重复重复、，直到得不出新打，直到得不出新打号行、列为止。号行、列为止。对没有打对没有打号行画一横线，有打号行画一横线，有打号列画一纵线，号列画一纵线，这就得到覆盖全部这就得到覆盖全部0元素最少直线数。元素最少直线数。第31页 （4）在未被直线覆盖部分中找出最小元素，然在未被直线覆盖部分中找出最小元素，然后在打后在打行各元素中都减去这最小元素，而在打行各元素中都减去这最小元素，而在打列列各元素都加上这最小元素。这么得到新系数矩阵各元素都加上这最小元素。这么得到新系数矩阵（它最优解和原问题相同）。（它最优解和原问题相同）。【例【例5】第32页4.3 4.3 背包问题背包问题背包问题背包问题(Knapsack Problem)(Knapsack Problem)和贪心算法和贪心算法和贪心算法和贪心算法 一个旅行者一个旅行者一个旅行者一个旅行者,为了准备旅行必须用具为了准备旅行必须用具为了准备旅行必须用具为了准备旅行必须用具,要要要要在背包内装一些最有用东西在背包内装一些最有用东西在背包内装一些最有用东西在背包内装一些最有用东西,但有个限制但有个限制但有个限制但有个限制,最最最最多只能装多只能装多只能装多只能装b b千克物品千克物品千克物品千克物品,而每件物品只能整个而每件物品只能整个而每件物品只能整个而每件物品只能整个携带携带携带携带,这么旅行者给每件物品要求了一个这么旅行者给每件物品要求了一个这么旅行者给每件物品要求了一个这么旅行者给每件物品要求了一个“价价价价值值值值”以表示其有用程度以表示其有用程度以表示其有用程度以表示其有用程度,假如共有假如共有假如共有假如共有n n件物品件物品件物品件物品,第第第第j j件物品件物品件物品件物品a aj j千克千克千克千克,其价值为其价值为其价值为其价值为c cj j.问题变成问题变成问题变成问题变成:在携在携在携在携带物品总重量不超出带物品总重量不超出带物品总重量不超出带物品总重量不超出b b千克条件下千克条件下千克条件下千克条件下,携带哪携带哪携带哪携带哪些物品些物品些物品些物品,可使总价值最大可使总价值最大可使总价值最大可使总价值最大第33页解：解：假如令假如令假如令假如令x xj j=1=1表示携带物品表示携带物品表示携带物品表示携带物品j j，x xj j=0=0表示不携带表示不携带表示不携带表示不携带 物品物品物品物品j j，则问题表示成，则问题表示成，则问题表示成，则问题表示成0-10-1规划规划规划规划:Max Z=Max Z=c cj jx xj j s.t.s.t.aaj jx xj j b b x xj j=0 =0 或或或或1 1第34页