优化模型及求解2

《优化模型及求解2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2021/9/17优化模型及求解整数规划问题的提出线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情形(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立小型中型大型现有量钢材1.535600时间2802

2、5040060000利润234线性规划模型(LP)模型求解3）模型中增加条件：x1,x2,x3均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.0032261）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与L

3、P最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。结果为小数，怎么办？某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制见下表。问每集装箱中两种货物各装多少箱，可使所获利润最大。货物／箱体积／米３重量／百斤利润／百元甲5220乙4510托运限制／集装箱2413设x1,x2分别为甲、乙两种货物的托运箱数。Maxz=20x1+10x2s.t.5x1+4x2242x1+5x213x1,x2

4、0，整数这是一个纯整数规划。去掉整数约束，解相应的线性规划，可得最优解X*=(4.8,0),z*=96.问题：是否可以把非整数的最优解通过化整得到整数规划的最优解？IP最优解为X*=(4,1),z*=90.图中画(+)号的点表示可行的整数解。凑整的(5，0)点不在可行域内，而C点又不合于整数条件。为了满足题中要求，表示目标函数的z的等值线必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。这样，z的等值线就由z=96变到z=90，它们的差值Δz=96-90=6表示利润的降低，这是由于变量的不可分性(装箱)所

5、引起的。背包问题有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。第i种物品每件重量为wi公斤，价值为vi元。每种物品各取多少件装入背包，使其中物品的总价值最高。设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为这个问题如果用线性规划求解，k个变量中将只有一个大于0，其余k-1个都等于0，而且这个大于0的变量一般情况下是非整数。这样的解显然是没有意义的。对求最优整数解的问题，有必要另行研究。称这样的问题为整数线性规划(integerlinearprogramming)，简称ILP。变量取整数的规划称为整数

6、规划。所有变量都取整数的规划称为纯整数规划；部分变量取整数的规划称为混合整数规划；所有变量都取0,1两个值的规划称为0-1规划；部分变量取0、1两个值的规划称为0-1混合规划。厂址选择问题在N个地点中选r个（N>r）建厂，在第i个地点建厂（i=1，2，…，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。相互排斥的约束条件例：工厂可用k种不同的工艺生产n种产品。每种产品的利润已知。在各种工艺条件下每种产品所消耗的资源是确定的，并且工厂的总资源有一定

7、的限制。问：应选择哪种工艺进行生产，每种产品各生产多少，能使总利润最高。符号设定：工艺：A1,A2,…,Ak;产品：B1,B2,…,Bn;单件Bi的利润为pi;在工艺Aj下单件Bi的资源消耗为cij,资源限制为Qj.决策变量：Bi的产量，记为xi.目标函数：总利润为在任一种工艺Aj下，资源限制可表示为为确定工艺，引入0-1变量选定某种工艺进行生产，以上的k个条件中只有被选中的某一个起作用，约束条件：这是一个混合0－1规划模型指派问题一般提法：某单位有n项任务可由n个人完成，但每人完成不同任务的效率不同，指派哪个人去完成哪项任务，可使

8、完成n项任务的效率最高。它是0－1型整数规划的特殊模型，也是供需平衡的运输问题的特例。指派问题的数学模型：设(cij)为n×n的效率矩阵，cij＞０决策变量xij=1，指派第i人去完成第j项任务0，不指派第i人去完成第j项任务集合覆盖