线性规划及单纯形法1.ppt

一、线性规划建模步骤： 1.分析实际问题，确定自变量（决策变量），这些 自变量应彼此独立，意义明确，可借助它们将实际 问题正确方便表达出来； 2.确定有关参数的数据，包括价值系数Cj、约束条件 右侧常数bi和约束条件中的系数aij； 3.认清决策者想要达到的主要目标，据此列出目标 函数自变量的线性函数），并决定是要极大化或极 小化； 4.分析并汇总问题的限制条件，将其与有关自变量 和参 数联系起来，并逐一表达成等式或不等式； 5.写出完整的线性规划数学模型，并检查与实际问 题是否一致。 例1： 胜利家具厂生产桌子和椅子两种家具，桌子售 价50元/个，椅子售价30元/个，生产桌子和椅子需要 木工和油漆工两种工种。生产一个桌子需要木工4小 时，油漆工2小时。生产一个椅子需要木工3小时， 油漆工1小时。该厂每月可用木工工时为120小时， 油漆工工时为50小时，问该厂如何组织生产才能使 每月的销售收入最大？ 桌子椅子资源限量 木工43120小时 油漆工2150小时 售价（元/个） 5030 1. 问题是求什么？决策变量是什么？ 问该厂 如何组织生产？生产桌子和椅子两种家具各多少？ X1生产桌子数量；X2生产椅子数量。 2. 目的是什么？目标函数是什么？ 使每月的销 售收入最大？ Z每月的销售收入，则Max Z50X1 30X2。 3. 满足什么？约束条件是什么？木工工时为120 小时： 4X13X2120；油漆工工时为50小时：2X1 X250；生产数量：X10；X20 模型为：求X1，X2 MaxZ50X130X2 s.t. 4X1+3X2120 2X1+X250 X10；X20 解： 例2：某车间有两台机床甲和乙，可用于加工三件工 件，假定这两台机床的可用台时数分别为700和800， 三种工件的数量分别为300，500 和 400，且已知用不 同机床加工单位数量的不同工件所需的台时数和加工 费用表，问怎样分配机床的加工任务，才能既满足加 工工件的要求又使总加工费用最低？ 机床 类型 单位工件所需加工台时单位工件的加工费用可用台 时数 工件1工件2工件3工件1工件2工件3 甲0.41.11.013910700 乙0.51.21.311128800 设在甲机床上加工工件1、2和3的数量分别为x1、x2 和x3，在乙机床上加工工件1、2和3的数量分别是x4、x5 和x6。有： 例3：某昼夜服务的公共交通系统每天各时间段 （ 每4小时为一个时间段）所需的值班人数如下表，这 些值班人员在某一时段开始上班后要连续工作8个小 时 （ 包括轮流用膳时间在内），问该公交系统至少 需多少名工作人员才能满足值班的需要。 班次时间段所需人数 16:0010:0060 210:0014:0070 314:0018:0060 418:0022:0050 522:002:0020 62:006:0030 设xi为第i个时段开始上班的人员数，由此可得数 学模型如下： （一） 混合配料问题 某糖果厂用原料A，B，C加工成三种 不同牌号的糖果甲、乙、丙。已知各种牌 号糖果中A，B，C含量，原产成本，各种 原料的每月限制用量，三种牌号糖果的单 位加费及售价如表1-17所示。问该厂每月 生产这三种牌号糖果各多少kg ,使其获利最 大。试建立这个问题的线性规划的数学模 型。 二、其他应用例子 表1-17 原料甲乙丙 原料成本 (元/kg) 每月限 制用量 (kg) A B C 60% 20% 3% 50%60 2.00 1.50 1.00 2000 2500 1200 加工费 (元/kg) 售价 (元/kg) 0.50 3.4 0.40 2.85 0.30 2.25 （二） 产品计划问题 某厂生产,三种产品,都分别经A,B 两道工序加工.设A工序可分别在设备A1或A2 上完成,有B1,B2,B3三种设备可用于完成B工序. 已知产品可在A,B任何一种设备上加工;产 品可在任何规格的A设备上加工,但完成B工 序时,只能在B1设备上加工;产品只能在A2与 B2设备上加工.加工单位产品所需工序时间及 其他各项数据见表1-18,试安排最优生产计划, 使该厂获利最大. 表1-18 设备 产品 设备有 效台时 设备加 费(元 /h) A1 A2 B1 B2 B3 5 7 6 4 7 10 9 8 12 11 6 000 10 000 4 000 7 000 4 000 0.05 0.03 0.06 0.11 0.05 原材料(元/件) 售价(元/件) 0.25 1.25 0.35 2.00 0.50 2.80 （三） 生产存贮问题 某厂签订了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