运筹学ABC-2线性规划建模课.

线性规划在经济管理中的应用——线性规划建模应用1：生产计划问题问题1试列出下述产品规划问题的线性规划模型：某工厂生产A、B、C三种产品，每吨利润分别为2000元、3000元、1000元；生产单位产品所需的工时及原材料如表所示。若供应的原材料每天不超过3吨，所能利用的劳动力日总工时是固定的，问如何制定日生产计划，使三种产品总利润最大？生产每吨产品所需资源产品ABC劳动力所需工时占总工时比例1/31/31/3所需原材料（吨）1/34/37/3解：第一步——确定决策变量1x为产品A的日产量2x为产品B的日产量3x为产品C的日产量第二步——明确约束条件劳动力的约束条件为：1313131321xxx原材料的约束条件为：3373431321xxx第三步——明确目标总利润为：32132xxxZ32132maxxxxZ0,,33734311313131..321321321xxxxxxxxxts此产品规划问题的线性规划模型为：•问题2某工厂在计划期内要安排生产I、II两种产品。已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示。该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问I、II两种产品的产量各为多少时，使该工厂获取最大利润？产品I产品II设备128台时原材料A4016kg原材料B0412kg约束条件x1＋2x2≤84x1≤164x2≤12x1，x2≥0该生产计划问题可用数学模型表示为：目标函数maxz＝2x1＋3x2•问题3•某制造企业有A、B、C、D四种主要产品，所有产品均需四道工序生产：第一阶段是冲压，第二阶段是成型，第三阶段是装配，第四阶段是喷漆。根据工艺要求及成本核算，单位产品所需的加工时间、利润以及可供使用的总工时如下表所示。这四种产品每天要各生产多少件才能使获得的利润最大？请就这一问题，以利润最大为目标，建立求解的线性规划模型。工序每件产品加工时间每天加工能力（分钟）ABCD冲压1111480成型48252400装配42552000喷漆64843000单位利润（元）96118解答：maxZ=9x1+6x2+11x3+8x4约束条件：x1+x2+x3+x4≤4804x1+8x2+2x3+5x4≤24004x1+2x2+5x3+5x4≤20006x1+4x2+8x3+4x4≤3000x1≥0，x2≥0，x3≥0，x4≥0应用2：配料问题某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价(元/公斤)115978276假设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，才能使新产品的原材料成本最小。•问题1解：设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4公斤，根据条件，可建立相应的线性规划模型如下：这是一个典型的成本最小化的问题。这个线性规划问题的最优解是：x1=26.58，x2=31.57，x3=41.84，x4=0（公斤）最低成本为：z=9549.87（元）minz=115x1+97x2+82x3+76x4s.t.0.0321x1+0.0453x2+0.0219x3+0.0176x4≥3.200.0204x1+0.0112x2+0.0357x3+0.0433x4≥2.100.0582x1+0.0306x2+0.0427x3+0.0273x4≥4.30x1+x2+x3+x4=100x1,x2,x3,x4≥0•问题2某养猪场的猪每天至少需要700g蛋白质，30g矿物质，100mg维生素。现有五种饲料可选，每种饲料每kg营养成分含量及单价如表所示。要求确定既满足动物生长应用需要，又使费用最省的选用饲料方案。饲料蛋白质（g）矿物质（g）维生素（mg）价格（元/kg）1234532161810.50.220.50.51.00.220.80.20.70.40.30.8设xi为第i种饲料的数量（公斤），则Minz=0.2x1+0.7x2+0.4x3+0.3x4+0.8x5St.3x1+2x2+1X3+6X4+18X5=7001x1+0.5x2+0.2X3+2X4+0.5X5=300.5x1+1x2+0.2X3+2X4+0.8X5=100应用3：背包及配送问题一个物料箱最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：物品1物品2物品3重量（公斤/件）104120价值（元/件）177235问：要在物料箱中装入这三种物品各多少件，使箱中的物品价值最高？问题1：物料装箱这个问题的最优解是：x1=1(件),x2=0(件),x3=2(件),最高价值为：z=87（元）解：设装入物品1，物品2和物品3各为x1，x2，x3件，由于物品的件数必须是整数，因此物料箱问题的线性规划模型是一个整数规划问题：Maxz=17x1+41x2+35x3s.t10x1+41x2+20x3=50xi≥0(i=1,2,3)且为整数问题2设某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地的单位物资运价如下表所示。运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）103020问如何安排运输计划，从而使总运费最小？设xij为从供应地Ai运往需求地Bj的物资数量（i=1,2；j=1,2,3），z为总运费，则总运费最小的线性规划模型为：minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35(1)x21+x22+x23=25(2)x11+x21=10(3)x12+x22=30(4)x13+x23=20(5)xij≥0以上约束条件（1）、（2）称为供应地约束，（3）、（4）、（5）称为需求地约束。这个问题的最优解为：x11=0，x12=30，x13=5（吨）；x21=10,x22=0,x23=15（吨）最小运费为：z=275元。应用4：优化下料问题问题1线材优化现要做100套钢架，每套用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。方案下料数长度IIIIIIIVV2.92.11.510321221213合计料头7.407.30.17.20.27.10.36.60.8为了得到100套钢架，需要混合使用各种下料方案。设第i种方案下料的原材料根数为xi，（i＝1，2，3，4，5）得数学模型为：minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5x1+2x2+x4＝100x2+2x3+2x4+x5＝1003x1+x2+2x3+3x5＝100xi≥0(i=1,2,3,4,5)且为整数问题2板材优化要将两种大小不同规格的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：规格类型第一种钢板第二种钢板A规格B规格C规格212131今需要A,B,C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。解：设需截第一种钢板x张，第一种钢板y张，则2x+y≥15,x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*目标函数为minz=x+y应用5：值班调度问题问题1某个中型的百货商场对售货人员的需求经过统计分析如下表所示，为了保证销售人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既能满足工作需要，又使配备的售货人员的人数最少？问题2某医院护士值班班次、每班工作时间及各班所需护士数如下表所示。每班护士值班开始时向病房报到，试决定：若护士上班后连续工作8h，该医院最少需多少名护士，以满足轮班需要？解：在本例中，每一时段上班的工作人员，既包括本时段开始上班的人，又包括上一个时段开始上班的人。因此，设xi为第i个时段开始上班的人员数，得到数学模型为：Minz=x1+x2+x3+x4+x5+x6x6+x1=60X1+x2=70X2+x3=60x3+x4=50X4+x5=20X5+x6=30Xj=0,j=1,2,…6应用6：投资组合问题问题1宏银公司承诺为某建设项目从2003年起的4年中每年初分别提供以下数额贷款：2003年—100万，2004年—150万，2005年—120万，2006年—110万元。以上贷款资金均需于2002年底前筹集齐。但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目（1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元；（2）于2003年初购买B种债券，期限2年，到期后本息合计为投资额的125%，且限购90万元；（3）于2004年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元；（4）于每年初将任意数额的资金存放于银行，年息4%，于每年底取出。问宏银公司应如何运用好这笔筹集到的资金，使2002年底需筹集到的资金数额最少？解：设x为2002年底宏银公司需筹集到的资金额，y1，y2，y3为分别与2003、2004、2005年初存放到银行的资金数，WA、wB、WC、为分别购买A、B、C债券的数额（单位均为万元），则可列出minz=xx-y1-WA-WB=1001.04y1-y2-WC=1501.04y2+1.25wB-y3=1201.04y3+1.40wA+1.30wC=110X=0,yi=0(i=1,2,3)wj=0(j=A,B,C)