maxZ??(x1??x1??)?(x2??x2??)?x1??x1???x2??x2???x3?5??x1??x1???x4?4????????x1、x1、x2、x2、x3、x4?0

XB XB Cj-Zj XN N CN XN B－1N CN－CBB－1N XS B－1 XS I 0 b b 0 B CB XB I 0 b B－1b －CBB－1b XB λ －CBB－1 【例3-2 】在例3-1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。 （1）所装物品不变；

（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为

1.8x1?0.6x2?121.5x1?2x2?20

体积 （m3/每件） 0.0015 0.002 0.020 价值 (元/每件) 4 3 物品 丙 丁 约束 重量 （公斤/每件） 1.8 0.6 12 maxZ?4x1?3x21.2x1?0.8x2?10y1＋12y2（1）

2x1?2.5x2?25y1?20y2

i?1,2y1?y2?1xi?0,andinteger,yi?0或1

maxZ?4x1?3x21.2x1?0.8x2?10＋My21.8x1?0.6x2?12?My1(a)(b)(c)(d)（2）

2x1?2.5x2?25?My21.5x1?2x2?20?My1

y1?y2?1xi?0,andinteger,yi?0或1i?1,2【例3-3】试引入0－1变量将下列各题分别表达为一般线性约束条件 （1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20 （2）若x1≤5，则x2≥0，否则x2≤8 （3）x2取值0，1，3，5，7

?x?x?6?yM21?1?4x1?6x2?10?y2M??2x1?4x2?20?y3M?y?y2?y3?2(3?1)?1?yj?0或1，j?1,2,3??x1?5?yM??x1?5?(1?y)M?(2)?x2??yM

?x?8?(1?y)M?2?1?y?0或

?x?x?6?(1?y)M21?1?4x1?6x2?10?(1?y2)M??2x1?4x2?20?(1?y3)M?y?y2?y3?1?1?yj?0或1，j?1,2,3??x?y?3y?5y?7y21234?(3)?y1?y2?y3?y4?1

?y?0或1，j?1,2,3,4?j

【例3-4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产．已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表3－2所示，怎样安排产品的加工使总成本最小． 固定成本（元） 变动成本 最大加工数 （元／件） （件） 本企业加工 500 8 1500 外协加工Ⅰ 800 5 2000 外协加工Ⅱ 600 7 不限

minZ?(500y1?8x1)?(800y2?5x2)?(600y3?7x3)?xj??x1??x1?x?j?Myj?0j?1,2,3?x2?x3?4000?1500,x2?2000?0,yj?1或0，j?1,2,3

用分枝－隐枚举法求解下列BIP问题

minZ?x1?3x2?6x3?2x4?4x5?6x1?2x2?x3?7x4?x5?12??x1?4x2?5x3?x4?3x5?10??xj?0或1，j?1,2,3,4(3?11a)(3?11b)

解 （1）令x2=1－x'2及x5=1－x'5，代入模型后整理得

minZ?x1?3x2??6x3?2x4?4x5??7?6x?2x??x?7x?x??912345??x1?4x2??5x3?x4?3x5??3?x?0或1，j?1,2,3,4?j(3?11a)(3?11b)

minZ?x1?2x4?3x2??4x5??6x3?7?6x?7x?2x??x?－x?914253??x1?x4－4x2?－3x5??5x3?3?x?0或1，j?1,2,3,4?j(3?11a)(3?11b)

【例4-1】某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源、每件产品利润如表4－1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；假定市场需求无

限制。

现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：

（1）利润不少于3200元

（2）产品甲与产品乙的产量比例尽量不超过1.5 （3）提高产品丙的产量使之达到30件

（4）设备加工能力不足可以加班解决，能不加班最好不加班

（5）受到资金的限制，只能使用现有材料不能再购进（不能变化） 问企业如何安排生产计划才能到达经营目标。

minz?P1d1?P2d2?P3d3?P4(d4?d5)??????40x?30x?50x?d??d??320012311???x1－1.5x2?d2?d2?0????x3?d3?d3?30??? ?3x1?x2?2x3?d4?d4?200????2x1?2x2?4x3?d5?d5?200??4x1?5x2?x3?360?2x1?3x2?5x3?300????x1?0,x2?0,x3?0andinteger,dj、dj?0,j?1,2,?5??

【例4-2】某企业集团计划用1000万元对下属5个企业进行技术改造，各企业单位的投资额已知，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的4个因素，技术改造完成后预测单位投资收益率(（单位投资获得利润/单位投资额）×100％)如表4－2所示． 集团制定的目标是：

（1）希望完成总投资额又不超过预算1000万元； （2）总期望收益率达到总投资的30%； （3）投资风险尽可能最小；

（4）保证企业5的投资额占20%左右． 集团应如何作出投资决策． 企业1 企业2 企业3 企业4 企业5 单位投资额(万元) 12 10 15 13 20 单位投市场需求1 4.32 5 5.84 5.2 6.56 资收益市场需求2 3.52 3.04 5.08 4.2 6.24 率预测现有竞争对手 3.16 2.2 3.56 3.28 4.08 rij 替代品的威胁 2.24 3.12 2.6 2.2 3.24 期望(平均)收益率％ 3.31 3.34 4.27 3.72 5.03