管理数量方法与分析-第五章：线性规划介绍

1、线性规划问题的数学模型2、使用线性规划的基本技巧3、运输问题目录线性规划是运筹学的规划论的一个重要分支。从20世纪30年代末开始，就有人从运输等问题开始研究。规划论要解决的问题是在给定条件下，按某一衡量指标来寻找安排的最优方案，可将之表示为函数在约束条件下的极值问题；当约束方程和目标函数都是线性，就属于线性规划问题。5.1线性规划问题的数学模型线性规划问题的数学模型的一般形式112211112211211222221122maxmin,,..,0,1,2,,nnnnnnmmmnnmizcxcxcxaxaxaxbaxaxaxbstaxaxaxbxin目标函数ObjectiveFunction约束条件Constraintcondition决策变量费用系数例5.1运输问题设有两个砖厂A1，A2，其产量分别为23万块、27万块。将这些砖供给三个建筑工地B1，B2，B3使用，其需求量分别为17万块，18万块，15万块。砖厂A1到工地B1，B2，B3的单位运价分别为50,60,70（元/万块），砖厂A2到工地B1，B2，B3的单位运价分别为60,110,160（元/万块）。考虑如何安排调运，可使总运费最省？A1B1A2B2B3解：设变量xij（i=1,2；j=1,2,3）表示由砖厂Ai将砖运到建筑工地Bj的数量（万块），可表示以下方程组：11121321222311211222132302327171815ijxxxxxxxxxxxxx111213212223min50607060110160Sxxxxxx约束条件Constraintcondition例5.2指派问题将三项任务Bj指派给三位工作人员Ai完成，而且要求将每项任务仅指派给一位工作人员完成，每位工作人员仅完成一项工作任务。工作人员A1完成工作B1，B2，B3的时间为1,4,6（天），工作人员A2完成工作B1，B2，B3的时间为2,5,8（天），工作人员A3完成工作B1，B2，B3的时间为3,7,9（天）。考虑如何指派，可使完成全部工作任务的总工作时间最少？A1B1A2B2B3A3解：设变量xij=1工作任务Bj指派给工作人员Ai，而xij=0不将工作任务Bj指派给工作人员Ai，可表示以下方程组：1112132122233132331121311222321323331=0111111ijxxxxxxxxxxxxxxxxxxx111213212223313233min46258379Sxxxxxxxxx约束条件Constraintcondition例5.3配套问题用三台机床A1，A2，A3分别在单位时间加工两种不同的零件B1，B2。其中，机床A1加工零件B1，B2的效率为50,60（件）；机床A2加工零件B1，B2的效率为30,90（件）；机床A3加工零件B1，B2的效率为20,80（件）。若某产品仅由一个B1与一个B2配套而成。考虑如何安排生产任务，可在单位时间内生产成套产品最多？A1B1A2B2A3解：设变量tij表示机床Ai产出零件Bj所用时间，可表示以下方程组：1112212231321121311222320111503020609080ijttttttttttttt112131122232max503020max609080StttSttt或约束条件Constraintcondition5.2使用线性规划的基本技巧针对生产能力的合理分配问题，使用效率比法；针对原料的有限库存，合理安排两种产品的产量使生产效益最大，使用图解法；针对物资调运问题，使用表上作业法；针对指派问题或旅行商问题，使用匈牙利法。5.2.1效率比法例5.1解：1212125010601230490122038012BBBBBB21212160650590153058020205BBBBBB所用A1加工B1效率最高，A3加工B2效率最高，A2用时间t加工B1和1-t加工B3，可使配套产品最多故列方程50+30t=90（1-t）+80，可得t=1故最多套数为50+30=805.2.2图解法引例某蛋糕商店生产甲、乙两种款式蛋糕，每件产品的利润，所消耗的材料、工时及材料限额与工时限额如下表所示，请问如何安排生产，使每天获得利润最大？甲乙限额面粉(斤/件)2324鸡蛋(个/件)3226利润(元/件)43(榴莲味)(草莓味)表1产品的消耗和收益解：这是一个生产计划问题，可使用如下数学模型进行描述。假设每天生产甲、乙两款蛋糕为x1件和x2件，每天利润为z，则12max43zxx1212122324..32260,0xxstxxxx可画出如下图形x10481216x24812163x1+2x2=262x1+3x2=24因此，可得出每天最多生产甲、乙两款蛋糕分别为6件4件，此时最大利润为36元。联立方程，可得121223243226xxxx1264xx(1)图解法5.3运输问题针对物资调运，使用表上作业法针对物资调运，还可以使用图上作业法针对车辆运输的调度问题，可以使用图上作业法针对指派问题或旅行商问题，使用匈牙利法例5.9由甲乙丙三人完成A,B,C三项任务，必须每个人只完成一项任务，假如三人完成三项任务所需要的经费如下ABC甲251522乙312019丙352417如何指派甲乙丙完成A,B,C三项任务，可使经费最少？匈牙利法的关键步骤：第一步：先将费用矩阵的每一行元素减去该行最小元素，再将每一列元素减去该列最小元素；1122331510190170251522100700731201912102103524171870870rcrcrc第二步：找在不同行，不同列的0元素，加*；**0721087第三步：在有“0*”的行列上，过“0*”画横线/竖线，有n个0*就画n条横竖线，且直线必须经过，再没有横竖线经过的非0元素中找到最小且没有被划过的最小元素，没被划过的元素均减到该元素，划过的元素均加上该元素；**0721087min2,1,8,71008100760第四步：重做第二步，即可得到最佳指派方案。***0810760100010001ABC甲乙丙甲完成A，乙完成B，丙完成C，可使费用最少，最少费用为：25+20+17=62