线性规划问题的数学模型

第一章线性规划及单纯型法•§1线性规划问题的数学模型•§2图解法•§3单纯形法原理•§4单纯形法计算步骤•§5单纯形法的进一步讨论•§7应用举例•习题课线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式§1线性规划问题的数学模型•问题的提出•例:生产计划问题III资源限量设备A设备B设备C24020512h16h15h利润23产品I产品2如何安排生产使利润最大？满足约束条件的决策变量的取值范围•基本概念可行域中使目标函数达到最优的决策变量的值问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。x1x2是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。•第1步-确定决策变量x1x2z•设——I的产量——II的产量——利润第2步--定义目标函数MaxZ=x1+x2MaxZ=2x1+3x2第2步--定义目标函数对我们有何限制?第3步–确定约束条件2x1+2x2124x1165x215x1、x20III资源限量设备A设备B设备C24020512h16h12h利润23该计划的数学模型目标函数MaxZ=2x1+3x2约束条件2x1+2x2124x1165x215x1、x20x1x2线性规划问题的共同特征•一组决策变量X表示一个方案,一般X大于等于零。•约束条件是线性等式或不等式。•目标函数是线性的。求目标函数最大化或最小化.线性规划模型的一般形式0,...,,),(......................................................),(...),(......)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax目标函数最大约束条件等式决策变量非负线性规划问题的标准形式•标准形式为:0,...,0,...,,......................................................2121221122222121112121112211mnmnmnmmnnnnnnbbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax–简写为njxmibxaxcZjinjjijnjjj,...,2,10,...2,1max11–用向量表示),...cc,(cC,...2,10max212121n211b...bbba...aaPx...xxXnjxbxPCXZmmjjjjnjnjjj其中：–用矩阵表示0...000),...,,(.........................0max211111nmnmnPPPaaaaAXbAXCXZ决策变量向量-X价值向量-C资源向量0...000),...,,(.........................0max3211111bPPPaaaaAXbAXCXZmnmnC—价值向量b—资源向量X—决策变量向量•minZ=CX等价于maxZ’=-CX•“”约束：加入非负松驰变量一般线性规划问题的标准形化例：目标函数MaxZ=2x1+3x2约束条件2x1+2x2124x1165x215x1、x20•minZ=CX等价于maxZ’=-CX•“”约束：加入非负松驰变量一般线性规划问题的标准形化0,,,,155164122200032max54321524132154321xxxxxxxxxxxxxxxxxz例：将下述线性规划模型化为标准形式取值无约束321321321321321,0,063234239232minxxxxxxxxxxxxxxxzz解：标准形为0,,,,,6)(3234)2(39)(2.00)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxtsxxxxxxz练习建立LP数学模型一、有两个煤厂A、B，每月分别供应三个居民区X、Y、Z。求运费最少的方案。距离AB需求量X10445Y5875Z61540供应量60100供需平衡线性规划模型举例(一)运输问题(二)布局问题(三)分派问题(四)生产计划问题(五)合理下料问题线性规划模型的条件•（1）要求解问题的目标函数能用数值指标来反映，且为线性函数；•（2）存在着多种方案；•（3）要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。(一)运输问题设某种物资有m个产地，A1，A2，…，Am；联合供应n个销地：B1，B2，…，Bn。各产地产量（单位：吨），各销地销量（单位：吨），各产地至各销地单位运价（单位：元／吨）如下表所示。应如何调运，才使总运费最少？表中：ai表示产地Ai的产量(i=1，2，…，m)；bj表示产地Bj的产量(j=1，2，…，n)；cij表示AiBj间的单位运价（元／吨）(i=1，2，…，m;j=1，2，…，n)；销地产地产量（吨）B1B2…BnA1A2┇Am销量（吨）C11C12…C1nC21C22…C2n┇┇…┇Cm1Cm2…Cmnb1b2…bna1a2┇am（二）布局问题•作物布局•在n块地上种植m种作物，已知各块土地•亩数、各种作物计划播种面积及各种作•物在各块的单产（每亩的产量）如表—（与运输问题相似），•问：如何合理安排种植计划，才使总产量最多。销地产地产量（吨）B1B2…BnA1A2┇Am销量（吨）C11C12…C1nC21C22…C2n┇┇…┇Cm1Cm2…Cmnb1b2…bna1a2┇am（二）布局问题n块土地每亩的产量m种农作物总产量最多(三）分派问题设有n件工作分派给n人去做，每人只做一件工作且每件工作只分派一人去做。设Ai完成Bj的工时为。问：应如何分派才使完成全部工作的总工时最少。nBBB,,,21nAAA,,,21njicij,,2,1,解：设为Bj分派给人Ai情况：Bj分派给Ai时，；不分派给Ai时，。那末这一问题的数学模型为：ijx1ijxnjicij,,2,1,0njixij,,2,1,求一组变量的值，使目标函数的值最小。nimjijijxcs11(完成全部工作的总工时最少）(三）分派问题(四）生产组织与计划问题(Ⅰ)生产的机器最多(Ⅱ)总的加工成本最低（Ⅲ）生产存储问题(四）生产组织与计划问题设某车间用机床生产由这n个不同零件构成的机器。如果每架机器需要各种零件的数目成比例;机床生产零件的效率(每日生产零件数)为。mAAA,,,21n,,,21nBBB,,,21iAjBijC(Ⅰ)生产的机器最多应如何分配机床负荷，才能使生产的机器最多?求一组变的值,njmixij,,2,1;,,2,1解：设为一天机床生产零件的时间（单位：日）这一问题的数学模型为：njmi,,2,1;,,2,1ijxiAjB的值最大。使目标函数11miijijxcs生产的机器台数(四）生产组织与计划问题(Ⅰ)生产的机器最多线性规划问题的共同特征•一组决策变量X表示一个方案,一般X大于等于零。•约束条件是线性等式或不等式。•目标函数是线性的。求目标函数最大化或最小化§1线性规划问题的数学模型