(四)可化为线性规划的问题

问题一

汽车厂月度生产计划一汽车厂生产小、中、大三种类型的汽车,各种类型的汽车对钢材以及劳动时间的需求如下表.试制订月生产计划,使该工厂的利润最大.小型车中型车大型车现有量钢材1.535600劳动时间28025040060000利润234分析小型车中型车大型车现有量钢材1.535600劳动时间28025040060000利润234从收益率来看,比较中型车和大型车得出结论,生产大型车不经济.因此,若允许车辆数量为实数,则不生产大型车.但是现在车辆为整数,因此模型为1模型的建立记月生产的小、中、大型车的数量分别为x1,x2,x3,模型为这是个整数线性规划问题,有三个决策变量,要用软件来求ILP.但是本题比较特殊,我们可以发现2LP图解法我们先得到实数型的最优解为（64.5,167.7),利润的最大值为632.3.（64.5,167.7)•但是,遗憾的是,这个解不是整数解,因此不合要求.解决方法:(1)由于解的数字都比较大,我们可以简单地舍去小数,即取(64,167),此时利润为629,可以接受.同时定界.(2)在最优解附近试探:(64,168);(65,167);(66,167),(65,166,1)等等.利润分别为632,631,后两个不满足约束.由于最大利润为632,故最优解为(64,168).3进一步讨论由于各种原因(比如,工艺),若生产某种汽车,则至少生产80辆,问生产计划有何改变?分析:要么xi=0,要么xi≥80,组合起来,共有八种情形:方法一:

让它们分别与模型(*)一起来求解新的LP,逐一得到它们的最优解.其中(1)不用解;(7),(8)无解;(2)的解为(214.3,0,0),z=428.5;(3)的解为(0,200,0),z=600;;(4)的解为(0,0,120),z=480;(5)的最优解为(80,150.4,0),z=611.2;工时为紧约束;(6)的最优解为(80,0,94),z=536;工时为紧约束;结论:此时最优解为(80,150.4,0),利润为611.2（64.5,167.7)•(75,97.5)∙可行域方法二引入0-1变量的作用是当yi=0时,必有xi=0.本例中,方法三从数学上讲,不过,这个式子对变量而言,出现了非线性函数,因此就变成了非线性规划问题,其求解往往比较困难,即使用软件求解(如:LINGO,Matlab),也往往依赖于初值的选择.评注:若能用线性规划处理,则尽量不要用非线性规划.例2原油的采购与加工问题某公司用两种原油(A和B)混合加工成两种汽油(甲和乙).甲乙两种汽油含原油A的最低比例分别是50%和60%,每吨售价分别为4800元和5600元.该公司现有原油A和B的库存量分别为500吨和1000吨,还可以从市场上买到不超过1500吨的原油A.原油A的市场价为:购买量不超过500吨时的单价为10000元/吨;购买量超过500吨但不超过1000吨时,超过500吨的部分8000元/吨;购买量超过1000吨时,超过1000吨的部分6000元/吨.该公司应如何安排原油的采购和加工?模型的建立设购买原油Ax吨,生产汽油甲所用的原油A和B分别为x11和x21吨;乙的分别为x12和x22吨.公司销售生产的汽油收入为P千元,纯收入为R千元.则购买原油A的成本为于是模型为其中模型求解方法一由于c(x)为分段函数,且在每一段内都是线性函数,因此我们可以通过求解三个线性规划问题,最后比较即可得到模型的最优解.方法二处理分段函数c(x)方法三引入0-1变量yi以yi=1分别表示以三种价格购买原油,等价于模型为混合线性规划.方法四处理分段线性函数的一般方法500100015001200090005000这个分段函数在三个区间内分别是线性函数,区间的分段点为0,500,1000,1500.当x落在某个区间时我们可以取做区间两个端点的线性组合来解决.500100015001200090005000取分点b1=0,b2=500,b3=1000,b4=1500.取分点的比例z1,z2,z3,z4.当x落在区间[b1,b2]时,取x=b1z1+b2z2,z1+z2=1;当x落在区间[b2,b3]时,取x=b2z2+b3z3,z2+z3=1;当x落在区间[b3,b4]时,取x=b3z3+b4z4,z3+z4=1;由于c(x)是x的线性函数,自然也是zi的线性函数.为了表示x落在某个区间,我们还要引入表示这个属性的变量:0-1变量yi.关系式yi中有只有一个为1.投资的收益与风险问题(98年A题)市场上有n种资产（如股票、债券、……）Si（i=1,2,…,n）供投资者选择，某公司有数额为M的一笔相当大的资金可用于作一个时期的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买Si的平均收益率为ri，并预测出购买Si的的风险损失率为qi。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的Si中最大的一个风险来度量。购买Si要付交易费，费率为pi，并且当购买额不超过给定值ui时，交易费按购买ui计算（不买当然无须付费）。另外，假定同期银行存款利率是r0，且既无交易费又无风险。（r0=5%）1)已知n=4时的相关数据如下：Siri(%)qi(%)pi(%)ui(元)S1282.51103S2211.52198S3235.54.552S4252.66.540试给该公司设计一种投资组合方案，即用给定的资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总风险尽可能小。2)试就一般情况对以上问题进行讨论，并利用以下数据进行计算。Siri(%)qi(%)pi(%)ui(元)S19.6422.1181S218.5543.2407S349.4606.0428S423.9421.5549S58.11.27.6270Siri(%)qi(%)pi(%)ui(元)S614393.4