线性规划及单纯形法.ppt

一、线性规划建模步骤：,分析实际问题，确定自变量（决策变量），这些自变量应彼此独立，意义明确，可借助它们将实际问题正确方便表达出来；确定有关参数的数据，包括价值系数Cj、约束条件右侧常数bi和约束条件中的系数aij；认清决策者想要达到的主要目标，据此列出目标函数自变量的线性函数），并决定是要极大化或极小化；分析并汇总问题的限制条件，将其与有关自变量和参数联系起来，并逐一表达成等式或不等式；写出完整的线性规划数学模型，并检查与实际问题是否一致。,例1：胜利家具厂生产桌子和椅子两种家具，桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时，问该厂如何组织生产才能使每月的销售收入最大？,1.问题是求什么？决策变量是什么？问该厂如何组织生产？生产桌子和椅子两种家具各多少？X1生产桌子数量；X2生产椅子数量。2.目的是什么？目标函数是什么？使每月的销售收入最大？Z每月的销售收入，则MaxZ50X130X2。3.满足什么？约束条件是什么？木工工时为120小时：4X13X2120；油漆工工时为50小时：2X1X250；生产数量：X10；X20模型为：求X1，X2MaxZ50X130X2s.t.4X1+3X21202X1+X250X10；X20,解：,例2：某车间有两台机床甲和乙，可用于加工三件工件，假定这两台机床的可用台时数分别为700和800，三种工件的数量分别为300，500和400，且已知用不同机床加工单位数量的不同工件所需的台时数和加工费用表，问怎样分配机床的加工任务，才能既满足加工工件的要求又使总加工费用最低？,设在甲机床上加工工件1、2和3的数量分别为x1、x2和x3，在乙机床上加工工件1、2和3的数量分别是x4、x5和x6。有：,例3：某昼夜服务的公共交通系统每天各时间段（每4小时为一个时间段）所需的值班人数如下表，这些值班人员在某一时段开始上班后要连续工作8个小时（包括轮流用膳时间在内），问该公交系统至少需多少名工作人员才能满足值班的需要。,设xi为第i个时段开始上班的人员数，由此可得数学模型如下：,（一）混合配料问题某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A，B，C含量，原产成本，各种原料的每月限制用量，三种牌号糖果的单位加费及售价如表1-17所示。问该厂每月生产这三种牌号糖果各多少kg,使其获利最大。试建立这个问题的线性规划的数学模型。,二、其他应用例子,表1-17,（二）产品计划问题某厂生产,三种产品,都分别经A,B两道工序加工.设A工序可分别在设备A1或A2上完成,有B1,B2,B3三种设备可用于完成B工序.已知产品可在A,B任何一种设备上加工;产品可在任何规格的A设备上加工,但完成B工序时,只能在B1设备上加工;产品只能在A2与B2设备上加工.加工单位产品所需工序时间及其他各项数据见表1-18,试安排最优生产计划,使该厂获利最大.,表1-18,（三）生产存贮问题某厂签订了5种产品(i=1,2,5)上半年的交货合同.已知各产品在第j月(j=1,6)的合同交货量Dij,该月售价Sij,成本价Cij及生产1件时所需工时aij.该厂第j月的正常生产工时为tj,但必要时可加班生产,第j月允许的最多另班工时不超过tj,并且加班时间内生产出来的产品每件成本增另额外费用cij元.若生产出来的产品当月不交货,每件库存1个月交存贮费pj.试为该厂设计一个保证完成合同交货,又使上半年预期盈利总额为最大的生产计划安排.,（四）动态投资问题宏银公司为某建设项目从2003年起的4年中每年初分别提供以下数额贷款:2003年100万元,2004年150万元,2005年120万元,2006年110万元.以上贷款资金均需于2002年底前筹集齐.但为了充分发挥这笔资金的作用,在满足每年贷款额情况下,可将多余资金分别用于下列投资项目:,(1)于2003年初购买A种债券,期限2年,到期后本息合计为投资额的140%,但限购90万元.(2)于2003年初购买B种债券,期限2年,到期后本息合计为投资额的1