整数规划模型085课件.ppt

1、第三章第三章 整数规划整数规划第1页，共38页。3.1 整数规划简介n要求所有要求所有 x xj j 的解为整数，称为纯整数规划的解为整数，称为纯整数规划n要求部分要求部分 x xj j 的解为整数，称为混合整数规划的解为整数，称为混合整数规划n对应没有整数解要求的线性规划称之为松弛问题对应没有整数解要求的线性规划称之为松弛问题n整数规划的解是可数个的，最优解不一定发生在极点整数规划的解是可数个的，最优解不一定发生在极点n整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解njxmibxatsxcxfjnjijijnjjj,2,1,0,2,1,),(.)(max

2、(min)11且为整数第2页，共38页。3.2 整数规划问题及其数学模型1 1、生产计划问题、生产计划问题例例3.2.1 3.2.1 某工厂生产某工厂生产A1A1、A2A2两种产品，产品分别由两种产品，产品分别由B1B1、B2B2两种部件组装而成。每件产两种部件组装而成。每件产品所用部件数量和部件的产量限额以及产品利润如下表所示，应如何安排品所用部件数量和部件的产量限额以及产品利润如下表所示，应如何安排A1A1、A2A2的产量，该厂才能获得最大利润？的产量，该厂才能获得最大利润？部件产品B1B2利润（百元）A16115A24320最大产量2510解：设x1、x2分别表示产品A1、A2的产量，则

3、该问题的数学模型为且皆为整数,0,010325462015max21212121xxxxxxxxZ第3页，共38页。3.2 整数规划问题及其数学模型2 2、投资项目选择问题、投资项目选择问题例例3.2.2 3.2.2 某单位有某单位有5 5个拟选择的投资项目，其所需投资额与期望收益如下表所示。由于个拟选择的投资项目，其所需投资额与期望收益如下表所示。由于各项目之间有一定联系，各项目之间有一定联系，A A、C C、E E之间必须选择一项，且仅需选择一项；之间必须选择一项，且仅需选择一项；B B和和D D之间之间需选择且仅需选择一项；需选择且仅需选择一项；C C的实施必须以的实施必须以D D的实施

4、为前提条件。该单位共筹集资金的实施为前提条件。该单位共筹集资金1515万元，应选择哪些项目投资，使期望收益最大？万元，应选择哪些项目投资，使期望收益最大？项目所需投资额（万元）期望收益（万元）A6.010.0B4.08.0C2.07.0D4.06.0E5.09.0第4页，共38页。3.2 整数规划问题及其数学模型解：解：考虑到有的项目有可能被选中，也有可能不被选中，设决策变量考虑到有的项目有可能被选中，也有可能不被选中，设决策变量x xi i(i=1,2,3,4,5)(i=1,2,3,4,5)分分别表示项目别表示项目A A、B B、C C、D D、E E，且定义，且定义)5,4,3,2,1(1

5、0iiixi被选中项目不被选中项目由于A、C、E之间必须且仅需选择一项，故有x1+x3+x5=1与此类似，B、D之间有关系式x2+x4=1由C的实施必须以D的实施为前提，因此，若x4=0(即D不实施)，则x3=0(即C一定不实施）；若x4=1(即D实施），则x3=0或1(即C可实施，也可不实施），因此有x3x4,即x3-x40对所有项目投资总额的限制条件为6x1+4x2+2x3+4x4+5x515第5页，共38页。3.2 整数规划问题及其数学模型目标函数为期望收益最大，可表示为目标函数为期望收益最大，可表示为max Z=10 xmax Z=10 x1 1+8x+8x2 2+7x+7x3 3+6

6、x+6x4 4+9x+9x5 5因此，此问题的数学模型为因此，此问题的数学模型为)5,4,3,2,1(,101554246011967810max54321434253154321ixxxxxxxxxxxxxxxxxxZi或皆为此问题的所有决策变量只限取0或1，因此，称为0-10-1规划规划对实际问题建立数学模型，常可借助0-1变量，使含“非此即彼”的、相互排斥的决策变量和约束条件寓于同一模型之中。第6页，共38页。3.2 整数规划问题及其数学模型3 3、指派问题、指派问题例例3.2.3 3.2.3 现有现有A1A1、A2A2、A3A3、A4A4四人，每人都能完成工作四人，每人都能完成工作B1

7、B1、B2B2、B3B3、B4B4四项中的一项。四项中的一项。下表列出了他们完成各项工作所需的时间。如果每项工作需安排且仅需安排一人完下表列出了他们完成各项工作所需的时间。如果每项工作需安排且仅需安排一人完成。问如何安排四人可使完成四项任务所花费的总时间最少？成。问如何安排四人可使完成四项任务所花费的总时间最少？工作人B1B2B3B4A1314105A21041210A39141513A478119第7页，共38页。3.2 整数规划问题及其数学模型解：由于每项工作需安排一人且仅需一人去完成，所以，设解：由于每项工作需安排一人且仅需一人去完成，所以，设x xijij表示表示AiAi去做去做BjB

8、j工作工作（i,j=1,2,3,4i,j=1,2,3,4），且），且工作不被安排做当工作被安排做当BjAiBjAixij01则该问题的数学模型是)4,3,2,1,(,10111111119118713151491012410510143min443424144333231342322212413121114443424134333231242322211413121144434241343332312423222114131211jixBjxxxxxxxxxxxxxxxxAixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZji或工作只有一人去做表示只做一项工作表示第8页，共3

9、8页。3.3 分枝定界法3.3.1 3.3.1 思路与解题步骤思路与解题步骤n只解松弛问题只解松弛问题,通过分枝，通过分枝，逐步缩小目标函数的上逐步缩小目标函数的上下界之差下界之差1、在全部可行性域上解松弛问题、在全部可行性域上解松弛问题n若松弛问题最优解为整数解，则其也是整数规划的最优解若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程、分枝过程n若松弛问题最优解中某个若松弛问题最优解中某个 xk=bk 不是整数，令不是整数，令 bk 为为 bk 的整数部分的整数部分n构造两个新的约束条件构造两个新的约束条件 xk bk 和和 xk bk +1，分别加于原松弛问题，分别加于原松弛

10、问题，形成两个新的整数规划形成两个新的整数规划3、求解分枝的松弛问题、求解分枝的松弛问题 定界过程定界过程n设两个分枝的松弛问题分别为问题设两个分枝的松弛问题分别为问题 1 和问题和问题 2，它们的最优解有如，它们的最优解有如下情况下情况第9页，共38页。表3.3.1 分枝问题解可能出现的情况序序号号 问问题题 1 1 问问题题 2 2 说说 明明 1 无无可可行行解解 无无可可行行解解 整整数数规规划划无无可可行行解解 2 无无可可行行解解 整整数数解解 此此整整数数解解即即最最优优解解 3 无无可可行行解解 非非整整数数解解 对对问问题题 2 继继续续分分枝枝 4 整整数数解解 整整数数解

11、解 较较优优的的一一个个为为最最优优解解 5 整整数数解解，目目标标函函数数优优于于问问题题 2 非非整整数数解解 问问题题 1 的的解解即即最最优优解解 6 整整数数解解 非非整整数数解解，目目标标函函数数优优于于问问题题 1 问问题题 1 1 停停止止分分枝枝(剪剪枝枝)，其其整整数数解解为为界界，对对问问题题 2 继继续续分分枝枝 7 非非整整数数解解 非非整整数数解解 对对目目标标函函数数较较优优的的一一个个继继续续分分枝枝 情况情况 2,4,5:对该分枝，找到最优解对该分枝，找到最优解情况情况 3,7:在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6:问题问题 1 的

12、整数解作为界被保留，用于以后与问题的整数解作为界被保留，用于以后与问题 2 的后的后续分枝所得到的解进行比较，结论如情况续分枝所得到的解进行比较，结论如情况 4 或或 5第10页，共38页。3.3.2 分枝定界法举例例例3.3.13.3.1 且为整数 0,01 3 25462015max21212121xxxxxxxxZ解解 1.松弛问题的最优解为 x1=2.5,x2=2.5,Z=87.5 为上 界，令下界为Z=02.由 于x1=2.5不为整数，分别增加新的约束条件x1 2和 x1 3 得到两个分枝，它们的松弛问题如下：0,2 01 3 2546)1(2015max211212121xxxxx

13、xxxxZ问题 0,3 01 3 2546)2(2015max211212121xxxxxxxxxZ问题第11页，共38页。3.解问题（1）的松弛问题，问题（2）暂时记录下来.问题（问题（1 1）的松弛问题最优解为）的松弛问题最优解为 x1=2,x2=2.67,Z=83.3x1=2,x2=2.67,Z=83.3 由于由于x x2 2不为不为整数，对整数，对问题（问题（1 1）分别增加）分别增加新的约束条件新的约束条件x x2 2 2.2.x x2 2 3 3，分枝为两个分枝为两个子子问题，它们的松弛问题如下：问题，它们的松弛问题如下：0,32 01 3 2546)4(2015max212121

14、2121xxxxxxxxxxZ问题 0,2 201 3 2546)3(2015max2121212121xxxxxxxxxxZ问题第12页，共38页。4.解问题（3）的松弛问题，问题（4）暂时记录下来.问题（问题（3 3）的松弛问题最优解为）的松弛问题最优解为 x x1 1=2,=2,x x2 2=2,Z=70=2,Z=70 由于解为由于解为整数，整数，问题（问题（3 3）不再分枝，目标函数新的）不再分枝，目标函数新的下界为下界为Z Z=max0,70=70.=max0,70=70.5.5.对对记录下来的问题，记录下来的问题，依依“后进先出后进先出”的原则进行求解的原则进行求解.对对问题（问题

15、（4 4）进行求解，最优解为）进行求解，最优解为 x x1 1=1,=1,x x2 2=3,Z=75=3,Z=75 由于解为由于解为整数，整数，问题（问题（4 4）不再分枝，目标函数新的）不再分枝，目标函数新的下界为下界为Z Z=max70,75=75.=max70,75=75.X3=3X3=3X1 Z=75.对问题（2）进行分枝,增加新的约束条件 x2 1.x2 2，分枝为两个子问题，它们的松弛问题如下：0,1 301 3 2546)5(2015max2121212121xxxxxxxxxxZ问题 0,23 01 3 2546)6(2015max2121212121xxxxxxxxxxZ问题

16、第14页，共38页。7.7.对问题（5）进行求解，最优解为 x1=3.5,x2=1,Z=72.5 由于Z=72.5=4X3=6X10，则令yi=1-xi替换xi，于是yi在目标函数中的系数变为负，且yi也为0-1变量;(3)如果约束条件为“”，则可两边乘以-1，改为“”型(4)如果有k个等式约束，则可用以下(k+1)个“”约束代替。kjjkjniiijniiiijnijiijbxakjbxakjbxa11111),2,1(),2,1(第20页，共38页。3.4.2 隐枚举法基本思路：（1）首先令全部变量取0，如果此解可行，则为最优解，最优值为0，计算终止；否则，（2）有选择地指定某个变量为0或

17、1，并把它们固定下来（称为固定变量），其他变量为自由变量，将原问题分枝成两个子问题.对每个子问题，取自由变量均为0，继续分别检验；（3）对某个子问题，如果其有解，则停止分枝，返回；如果其目标函数值优于下界（初始设为-Inf)，则以其目标函数值为原问题的一个下界；否则不对界作修改。（4）如果无解，且取自由变量均为0时的目标函数值大于界，则继续步骤（2）进行分枝；否则，停止分枝，返回（5）以上分枝、定界的过程至所有子问题停止分枝，或没有自由变量为止（6）问题的最优解为最大下界值对应的可行解。（7）在第（2）步中，选择变量为固定变量的原则是：能使所有的约束到可行情况的总距离最小，所谓到可行情况的距离

18、，是指将约束变为可行情况，应在约束的左端所必须减少的数值第21页，共38页。例3.4.2用隐枚举法求解如下0-1规划问题)3,2,1(1073257324625624.161017max32132132132321jxxxxxxxxxxxxtsxxxZj或解：（1）令x1=1-y1,x2=1-y2,x3=1-y3,代入原问题，将其化为规范型)4()3()2()1()3,2,1(1033252324225024.)161017(max43max32132132132321jyyyyyyyyyyyytsyyySZj或第22页，共38页。例3.4.2(2)(2)目标函数值的下界设为目标函数值的下界设

19、为-Inf;-Inf;视视y y1 1,y,y2 2,y,y3 3均为自由变量，令均为自由变量，令(y(y1 1,y,y2 2,y,y3 3)=(0,0,0)=(0,0,0)，检，检验知，此解不可行；验知，此解不可行；(3)(3)选择固定变量：各变量到可行情况的距离如下表所示：选择固定变量：各变量到可行情况的距离如下表所示：(1)(2)(3)(4)总距离目标系数 固定变量Y1=100000-17Y2=101012-10Y3=100000-16 因此：以y3为固定变量，令y3=1,y3=0，将原问题分解为两个子问题)2,1(100255240524.101716max)1()1(21212122

20、13jyyyyyyyytsyySyj或问题)2,1(103252242504.1017max)0()2(2121212213jyyyyyyyytsyySyj或问题第23页，共38页。例3.4.2n检验问题检验问题(1)(1)：令自由变量：令自由变量(y1,y2)=(0,0)(y1,y2)=(0,0)，知其可行，连同固定变量，知其可行，连同固定变量y3=1y3=1，有变量有变量(y1,y2,y3)=(0,0,1)(y1,y2,y3)=(0,0,1)，目标函数值为，目标函数值为-16-16，优于当前下界，优于当前下界-Inf-Inf，因，因此，设下界为此，设下界为-16-16；返回。；返回。n检验

21、问题检验问题(2)(2)：令自由变量：令自由变量(y1,y2)=(0,0)(y1,y2)=(0,0)，知其不可行，目标函数值为，知其不可行，目标函数值为0 0，优于当，优于当前下界前下界-16-16，因此应继续分枝；，因此应继续分枝；n选择固定变量，其与可行情况的距离如下表：选择固定变量，其与可行情况的距离如下表：(1)(2)(3)(4)总距离目标系数 固定变量Y1=100000-17Y2=101012-10虽然，选择y1为固定变能使所有的约束到可行情况的总距离最小，但y1=1，y2=0 时，目标函数值为为17，小于当前下界，小于当前下界16。因此，选择y2为固定变量，令y2=0,1，将问题(

22、2)分解为两个子问题。第24页，共38页。例3.4.2)1(10150415.1710max)1()3(11112jyyyytsySyj或问题)1(10352425.17max)0()4(11112jyyyytsySyj或问题（7）检验问题(4)知，自由变量y1=0不可行，y1=1所得的目标函数值-17小于目标函数值的下界-16，故返回（8）检验问题(3)知，自由变量y1=0不可行，y1=1所得的目标函数值-27小于目标函数值的下界-16，故返回（9）总之，此问题的解为(0,0,1)，目标函数值为-16第25页，共38页。3.5 指派问题的解法例例3.5.1 3.5.1 有四个熟练工人，他们都

23、是多面手，有四项任务要他们完成。若有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表如表3.6.13.6.1，问如何分配任务使完成四项任务的总工时耗费最少？，问如何分配任务使完成四项任务的总工时耗费最少？1,0,2,1 1,2,1 1)0(,)(min1111ijniijnjijijninjijijxnjxnixcxcxf任任务务 工工时时ABCD人人员员人人员员甲甲109781乙乙58771丙丙54651丁丁23451任任务务1111第26页，共38页。3.5

24、.1 指派问题的数学模型模型中：xij 为第 i 个工人是否分配去做第 j 项任务；cij 为第 i 个工人为完成第 j 项任务时的工时消耗；cijnn 称为效率矩阵njijijixij,2,1,01项任务个工人未分配去做第当第项任务个工人分配去做第当第 指派指派问题是运输问题的特例问题是运输问题的特例 指派问题不但是整数规划，而且是指派问题不但是整数规划，而且是0 1规划规划 指派问题有指派问题有2n个约束条件，但有且只有个约束条件，但有且只有n个非零解，是高度退化个非零解，是高度退化的的第27页，共38页。3.5.2 匈牙利算法定理 1 如果从效率矩阵cijnn中任何一行各元素分别减去一个

25、常数 ui，从任何一列各元素分别减去一个常数 vj，所得新的效率矩阵bijnn的指派问题的最优解等价于原问题的最优解。证明：略定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。证明：略匈牙利算法的基本思路：根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 n 个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于n 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零第28页，共38页。匈牙利算法的步骤：例3.5.1第一步：变换效率矩阵，使每行每列至少有一个零第一步：变换效率矩阵，使每行

26、每列至少有一个零n行变换行变换：找出每行最小元素，从该行各元素中减去之：找出每行最小元素，从该行各元素中减去之n列变换列变换：找出每列最小元素，从该列各元素中减去之：找出每列最小元素，从该列各元素中减去之2210020112300023321012012230)1(023543)2(56)4(5778)5(8)7(910换变列换变行第二步：检查覆盖所有零元素的直线是否为第二步：检查覆盖所有零元素的直线是否为n n条条划线规则划线规则1 1、逐行检查，若该行只有一个未标记的零，对其加逐行检查，若该行只有一个未标记的零，对其加()()标记，将标记，将 ()标记元素同行同列上其它的零打上标记元素同行

27、同列上其它的零打上*标记。若该行有二个以上未标记的标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；零，暂不标记，转下一行检查，直到所有行检查完；第29页，共38页。匈牙利算法的步骤：例3.5.12、逐列检查，若该列只有一个未标记的零，对其加、逐列检查，若该列只有一个未标记的零，对其加()标记，将标记，将()标记元素标记元素同行同列上其它的零打上同行同列上其它的零打上*标记。若该列有二个以上未标记的零，暂不标记，标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；转下一列检查，直到所有列检查完；221*0*02)0(1123)0(*0)0(23

28、221*00201123)0(0023查检列逐查检行逐3、重复、重复1、2后，可能出现三种情况：后，可能出现三种情况：a.每行都有一个每行都有一个(0)，显然已找到最优解，令对应，显然已找到最优解，令对应(0)位置的位置的 xij=1；b.仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用为无法采用 1、2 中的方法继续标记。中的方法继续标记。打破僵局：令未标记零对应的同行同列上其它未标记零的个数为该零的打破僵局：令未标记零对应的同行同列上其它未标记零的个数为该零的指数，选指数最小的先标记指

29、数，选指数最小的先标记()；采用这种方法直至所有零都被标记，或；采用这种方法直至所有零都被标记，或出现出现 情况情况 a，或，或 情况情况 c。第30页，共38页。匈牙利算法的步骤：例3.5.1c.c.所有零都已标记，但标有所有零都已标记，但标有()()的零的个数少于的零的个数少于n ；开始开始划线过程划线过程：对没有标记对没有标记 ()()的行打的行打 对打对打 行上所有其它零元素对应的列打行上所有其它零元素对应的列打 再对打再对打 列上有列上有 ()()标记的零元素对应的行打标记的零元素对应的行打 重复重复IIII、III III，直至无法继续，直至无法继续I.I.对没有打对没有打 的行划

30、横线，对所有的行划横线，对所有打打 的列划垂线的列划垂线 221*0*02)0(1123)0(*0)0(23 划线后会出现两种情况：划线后会出现两种情况：(1)(1)标记标记()()的零少于的零少于n n个，但划有个，但划有 n n条直线，说明矩阵中已存在条直线，说明矩阵中已存在 n n 个不同个不同行不同列的零，但打破僵局时选择不合理，行不同列的零，但打破僵局时选择不合理，没能找到。回到没能找到。回到 b b 重新标记；重新标记；(2)(2)少于少于n n条直线，到第三步条直线，到第三步；第31页，共38页。匈牙利算法的步骤：例3.5.1第三步：进一步变换，第三步：进一步变换，增加新的零增加

31、新的零；在未划线的元素中找出值最小者，设其值为在未划线的元素中找出值最小者，设其值为 对未被直线覆盖的各元素减去对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用以上步骤实际上仍是利用定理 1 221*0*02)0(1123)0(*0)0(2311000202012000241 第四步：抹除所有标记，回到第二步，重新标记；第四步：抹除所有标记，回到第二步，重新标记；第32页，共38页。解优最列逐行逐记标11)0(*0)0(2*02*012)0(*0)0(24匈牙利算法的步骤

32、：例3.5.111000202012000241 答：最优分配方案为答：最优分配方案为 x13=x21=x34=x42=1，其余为，其余为0，即甲即甲C，乙，乙A，丙，丙D，丁，丁B，OBJ=20110002020120*0)0(24记记标标列列110*00202*012)0(*0)0(24局局僵僵破破打打221*0*02)0(1123)0(*0)0(23第33页，共38页。6 0 2 0 5 0 4 0 0 3 0 1 0 2 0 0 局局僵僵破破打打3.5.3 匈牙利匈牙利算法的适用条件n要求所有要求所有cij 0n若某些若某些 cij 0，则利用定理，则利用定理 1 进行变换，使所有进行

33、变换，使所有 cij 0n目标函数为目标函数为min型型n对于对于max型目标函数，将效率矩阵中所有型目标函数，将效率矩阵中所有 cij反号，则等效于求反号，则等效于求min型型问题；再利用定理问题；再利用定理 1 进行变换，使所有进行变换，使所有 cij 0，则可采用，则可采用匈牙利匈牙利算法算法 打破僵局时选择不当的结果：打破僵局时选择不当的结果：结果仅出现结果仅出现 3 个标记个标记()，但却划出，但却划出 4 条线，条线，说明什么？！说明什么？！6 0 2 *0 5 0 4 *0 0 3 0 1 *0 2 *0 )0(局局僵僵破破打打6 *0 2 *0 5 )0(4 *0 0 3 0

34、1 *0 2 *0 )0(局局僵僵破破打打6 *0 2 *0 5 )0(4 *0 *0 3 )0(1 *0 2 *0 )0(局局僵僵破破打打第34页，共38页。3.6 3.6 利用利用0-10-1变量处理变量处理“选择问题选择问题”n设设x xi i(i=1,2,n)(i=1,2,n)为为0-10-1变量变量,则则nx x1 1+x+x2 2+x+x3 3=1=1表示在表示在x x1 1,x,x2 2,x,x3 3中必须且只能选择一项中必须且只能选择一项nx x1 1+x+x2 2+x+xn n=k=k表示在表示在x x1 1,x,x2 2,x,xn n中必须且只能选择中必须且只能选择k k项

35、项nx x1 1+x+x2 2+x+xn n=k=k=k表示在表示在x x1 1,x,x2 2,x,xn n中至少选择中至少选择k k项项nX X1 1=x=x2 2表示表示x x1 1的成立以的成立以x x2 2的成立为先决条件的成立为先决条件第35页，共38页。3.6 3.6 利用利用0-10-1变量处理变量处理“选择问题选择问题”n例例3.6.1 3.6.1 试用试用0-10-1变量对下列各题分别表变量对下列各题分别表示成一般线性约束条件：示成一般线性约束条件：nx x1 1+x+x2 2=2=8=8n变量变量x x3 3只能取值只能取值0,5,9,120,5,9,12n若若x x2 2

36、=4,=0=0，否则，否则x x5 5=3=3n以下以下4 4个约束条件至少满足个约束条件至少满足2 2个个a.xa.x6 6+x+x7 7=2 b.x=2 b.x6 6=1 c.x=1 c.x7 7=5 d.x=3=3第36页，共38页。3.6 3.6 利用利用0-10-1变量处理变量处理“选择问题选择问题”n解：解：为任意大正数或 MyyMxxMyxx,10832)1(2.121213,2,1,1011295.23213213iyyyyyyyxi或225544(1)3.3(1)01,xyMxy Mxy MxyMyM 或为任意大正数671627367412342154.3201,1,2,3,

37、4ixxy Mxy Mxy Mxxy Myyyyyi 或第37页，共38页。线性规划有关的英文词汇nOperational/operations research 运筹学nLinear programming 线性规划 Feasible domain 可行域nConvex set 凸集 Basic feasible solutions 基础可行解nSimplex algorithm 单纯型法 Pivot 主元 Pivoting 主元变换nRevised,dual simplex algorithm 修正、对偶单纯型法nRelative cost 相对成本(机会成本)Shadow price 影子价格nSlack,Surplus,Artificial variable 松弛，剩余，人工变量nUnbounded,Infeasible,Degenerate solution 无界解,无可行解,退化解nDuality 对偶性 Primal,dual problem 原问题，对偶问题nComplementary slackness 互补松弛 Sensitivity analysis 灵敏度分析nTtransportation problem 运输问题nAssignment problem 任务分配(指派)问题nHungarian method 匈牙利算法第38页，共38页。