1-1线性规划问题及其数学模型.

上页下页返回第一章线形规划本章学习重点线性规划是运筹学中比较成熟的一个分支，它具有成熟而有效的求解方法，可以借助于计算机进行求解，在军事、经济等领域中具有广泛的应用。学习本章，要掌握线性规划的数学模型（建模以及把不同形式的线性规划问题化为标准形式的方法）、求解方法。上页下页返回线性规划的地位与研究进程•作为一门科学的线性规划，最早可以追溯到20世纪30年代末，前苏联数学家康德洛维奇等人关于生产组织和运输问题研究所作的开拓性工作。1947年，美国数学家G.B.Dantzig以及美国空军的SCOOP研究小组提出了线性规划问题的一般性解法即单纯形法,奠定了线性规划的理论基础。50年代后，随着电子计算机的介入，线性规划的应用越来越普遍，在生产、管理、军事等方面发挥着重要的作用。•线性规划目前仍然还在发展，主要是：大型线性规划问题，线性规划解法研究等。线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式继续返回第一节线性规划问题及其数学模型上页下页返回•问题的提出•引例:生产计划问题甲乙资源限量设备原材料A原材料B1402048台时16kg12kg利润23上页下页返回产品甲产品乙如何安排生产使利润最大？上页下页返回什么是线性规划？在工业、农业、国防、建筑、交通运输、科研、商业等各种活动中，常常要求对资源进行统一分配、全面规划和合理调度，以便从各种可能安排方案中找出最优的计划或设计，用以指导生产。在这类问题中，一方面有期望达到最优要求的目标（例如希望产值最高或消耗最少），另一方面又要受到一定条件的限制（例如人力、物力、财力的限制），如何安排才能使成效最高，消耗既定资源取得的收益最大，或达到既定收益所消耗的资源最少。这可以借助线性规划（LinearProgramming，LP）来解决。上页下页返回线性规划研究的内容•在现有的资源条件下，如何充分利用资源，使任务或目标完成得最好（求极大化问题）。•在给定目标下，如何以最少的资源消耗，实现这个目标（求极小化问题）。上页下页返回x1x2是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。•第1步-确定决策变量•设——甲的产量——乙的产量x1x2上页下页返回MaxZ=x1+x2第2步--定义目标函数——利润z上页下页返回MaxZ=2x1+3x2第2步--定义目标函数上页下页返回对我们有何限制?上页下页返回第3步--表示约束条件x1+2x284x1164x212x1、x20甲乙资源限量设备原材料A原材料B1402048台时16kg12kg利润23上页下页返回该计划的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x2上页下页返回决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)•基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值上页下页返回线性规划问题的共同特征•一组决策变量X表示一个方案,一般X大于等于零。•约束条件是线性等式或不等式。•目标函数是线性的。求目标函数最大化或最小化上页下页返回例2(书)某厂生产甲乙两种产品，已知制成一吨产品甲需用资源A3吨，资源B4m3；制成一吨产品乙需用资源A2吨，资源B6m3，资源c7个单位。若一吨产品甲和乙的经济价值分别为7万元和5万元，三种资源的限制量分别为90吨、200m3和210个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高?上页下页返回建模步骤：•第一步：确定决策变量x1：生产产品甲的数量（吨）x2：生产产品乙的数量（吨）上述变量为由决策者决定的未知量，称为决策变量。上页下页返回•第二步：确定目标函数以Z表示生产甲和乙两种产品各为x1和x2（吨）时产生的经济价值，总经济价值最高的目标可表示为：maxz＝7x1十5x2这就是该问题的目标函数。上页下页返回•第三步：确定约束条件本例的约束条件为三种资源的限制用量。对各个限制条件逐一加以分析，写出反映其限制关系的表达式（等式或不等式），从而得到约束条件。资源A限制：3x1十2x2≤90资源B限制；4x1十6x2≤200资源C限制：7x2≤210此外，产量x1和x2不能为负，只能取正值非负条件：x1≥0，x2≥0上页下页返回经上述分析，可将该问题表示为：maxz＝7x1十5x23x1十2x2≤904x1十6x2≤2007x2≤210x1≥0，x2≥0这种数学表达方式，称为该问题的一种数学模型。上页下页返回例3：投资问题某单位有一批资金用于四个工程项目的投资，用于各工程项目时所得之净收益（投入资金的百分比）如下表所示：由于某种原因，决定用于项目A的投资不大于其它各项投资之和；而用于项目B和C的投资不小于项目D的投资。试确定使该单位收益最大的投资分配方案。工程项目ABCD收益（％）1510812上页下页返回第一步：确定变量x1、x2、x3、x4分别表示用于项目A、B、C、D的投资百分数。第二步：确定约束条件x1－x2－x3－x4≤0x2＋x3－x4≥0x1＋x2＋x3＋x4＝1xj≥0，j＝1，2,…,4上页下页返回第三步：确定目标函数maxz=0.15x1+0.1x2+0.08x3+0.12x4数学模型maxz=0.15x1+0.1x2+0.08x3+0.12x4x1－x2－x3－x4≤0x2＋x3－x4≥0x1＋x2＋x3＋x4＝1xj≥0，j＝1，2,…,4上页下页返回例4：营养问题某动物饲养场利用n种天然饲料来配制混合饲料使用，已知单位第j种天然饲料的价格为cj，它含有第i种营养成份的量为aij；根据动物生长的需要，要求具有m种营养成份，且第i种营养成份的含量不得低于bi。试确定在保证动物营养需要的条件下用最低的饲料配合法。上页下页返回•设xj为第j种天然饲料的使用量，则aijxj为第j种天然饲料含有第i种营养成分的数量。则：•考虑到非负约束和目标要求，其数学模型为：上页下页返回线性规划三要素线性规划(LinearProgramming，LP)有：•一组有待决策的变量（指模型中要求解的未知量）•一个线性的目标函数（指模型中要达到的目标的数学表达式）•一组线性的约束条件（指模型中的变量取值所需要满足的一切限制条件）上页下页返回线性规划模型的一般形式11221111221121122222112212(min)......(,)...(,)......................................................(,),,...,(,)0nnnnnnmmmnnmnMaxzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx上页下页返回线性规划问题的标准形式•标准形式为:0,...,0,...,,......................................................2121221122222121112121112211mnmnmnmmnnnnnnbbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax目标函数最大约束条件等式决策变量非负上页下页返回–简写为njxmibxaxcZjinjjijnjjj,...,2,10,...2,1max11其中：cj---------表示目标函数系数aij---------表示约束条件系数bi---------表示约束右端项上页下页返回–用向量表示),...cc,(cC,...2,10max212121n211b...bbba...aaPx...xxXnjxbxPCXZmmjjjjnjnijj其中：未知数向量上页下页返回–用矩阵表示0...000),...,,(.........................0max211111nmnmnPPPaaaaAXbAXCXZ决策变量向量-X价值向量-C资源向量0...000),...,,(.........................0max3211111bPPPaaaaAXbAXCXZmnmnA—系数矩阵C—价值向量b—资源向量X—决策变量向量上页下页返回一般线性规划问题的标准形化•线型规划问题的数学模型有各种不同的形式，为了便于讨论和求解，需要将线型规划问题的数学模型写成一个统一的格式，称为线型规划问题的标准型。•统一格式规定如下：1、目标函数取最大化2、所用约束条件用等式来表示3、所有决策变量取非负值4、每一约束条件的右端常数（资源限量）为非负值上页下页返回•minZ=CX等价于maxZ’=-CX•“”约束：加入非负松驰变量一般线性规划问题的标准形化例：目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20上页下页返回•minZ=CX等价于maxZ’=-CX•“”约束：加入非负松驰变量一般线性规划问题的标准形化0,,,,1241648200032max54321524132154321xxxxxxxxxxxxxxxxxz例：上页下页返回'',0kkkkkxxxxx令•“”约束：减去非负剩余变量；无约束321321321321321,0,7232732minxxxxxxxxxxxxxxxzMaxx6x7例：543xxxkx•可正可负（即无约束）；上页下页返回解：标准形为0,,,,,7)(232)(7)(00)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz上页下页返回非标准型转化举例0,,20040065300432..423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限原非标准型0,,,,,,2004006653004432..0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型上页下页返回复习思考题•1.什么是模型结构的三要素？•2.什么是线性规划模型？•3.LP模型中目标函数系数、约束条件系数、约束右端项的含义指的是什么？通常以什么符号表示？•4.LP模型的一般表示方法有几种形式？能否写出这些形式？上页下页返回将数学模型转化为标准形123123123123123min23+72326,0,zxxxxxxxxxxxxxxx无约束上页下页返回某企业生产两种产品，分别使用4种原料制成，4种原材料目前库存量分别为300，400，500和500吨，两种产品所需各种原材料数量见表。又知两种产品的单位利润分别为2800和3200元/吨，如何计划两种产品的产量，使利润达到最大。并将数学模型转化为标准形。两种产品所需的原材料数量原材料产品123411.41.31.41.421.