运筹学(上篇)

2020年7月25日星期六运筹学西南交通大学交通运输与物流学院运筹学2020年7月25日星期六第2页上篇本篇内容主要是线性规划问题，学习线性规划要具有线性代数基础知识。本篇主要学习内容包括：（1）针对实际问题如何建立线性规划模型。（2）针对线性规划模型如何求解以及求解的方法有哪些。（3）针对线性规划模型的稳定性、适应性、可靠性等进行灵敏度分析。（4）线性规划模型特殊形式中的运输问题、指派问题、整数规划问题、0-1规划问题。（5）动态的线性规划问题即动态规划问题。下图给出了本书线性规划部分主要知识点之间的基本关联关系：运筹学2020年7月25日星期六第3页上篇否实际应用问题确定决策变量确定目标函数确定约束条件方程线性规划问题解的讨论单纯形法对偶单纯形法稳定性、适应性、健壮性题等灵敏度分析构建模型（线性规划）线性规划的标准型对偶问题求解方法是否适用所有的线性规划模型？运输问题指派问题整数规划0-1规划求解繁琐解不符合实际要求运筹学2020年7月25日星期六第4页第1章线性规划基础本章内容线性规划模型的特点及三种描述形式线性规划问题的提出及建立模型的步骤运筹学2020年7月25日星期六第5页第1章线性规划基础人们在生产活动实践中，往往会面临利用有限的资源去追求尽可能高的目标，或面临追求一定的目标而花费代价尽可能低的问题，对于这两个问题的的研究，构建了运筹学的重要组成部分——数学规划理论，而线性规划是发展较早、相对成熟、应用最为广泛的数学规划理论中的一个分支。线性规划是由美国数学家丹捷格（G.B.Dantzig）在1947年发表的成果，所解决的问题是美国空军军事规划时提出的，并提出了求解线性规划问题的单纯形法。而早在1939年，前苏联学者康托洛微奇在解决工业生产组织和计划问题时，已提出了类似线性规划问题的模型，并给出了“解乘数法”的求解方法，但当时并未引起人们的足够重视。问题进行了深入研究，最终线性规划形成了数学领域的一个重要分支，也成为运筹学的重要组成部分。运筹学2020年7月25日星期六第6页第1章线性规划基础1960年，康托洛微奇再次发表《最佳资源利用的经济计算》一书后，才受到国内外的一致重视，为此，康托洛微奇获得了诺贝尔奖。线性规划的提出很快受到经济学者的重视，如二战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans）很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划，其中阿罗、萨谬尔斯、西蒙、多夫曼和胡尔威茨等对线性规划问题进行了深入研究，最终线性规划形成了数学领域的一个重要分支，也成为运筹学的重要组成部分。线性规划的研究目的主要有两个：（1）研究利用有限的资源如何获取尽可能高的价值。（2）研究追求一定的目标如何使付出的代价尽可能少。为了明确线性规划这两个研究目的，本章主要学习什么是线性规划问题、如何构建线性规划问题的模型、线性规划模型有哪些特点以及线性规划模型的三种描述形式。运筹学2020年7月25日星期六第7页第1章线性规划基础§1.1线性规划问题的提出及建立模型的步骤一线性规划问题的提出下面是利用有限的资源如何获取价值最高的线性规划问题示例。某企业生产甲和乙两种产品，甲、乙两种产品需要在车间A和车间B加工，相关的资料如下表所示，那么该企业如何组织生产，才能使甲乙两种产品获得的总利润达到最大？为了解决上面的问题，首先要利用给出的资料对问题进行分析，在深入分析的基础上，用数学语言的形式将问题刻画和描述出来（把实际的问题用数学语言的形式描述出来就是建立数学模型的过程）。产品车间可用工时市场限制甲乙在A加工时数216114108无≤7在B加工时数单位产品利润运筹学2020年7月25日星期六第8页第1章线性规划基础问题分析：把上面的问题用逻辑图的形式进行分析，如下图所示。市场售卖市场售卖2工时/个企业车间有限工时资源车间A（可用工时≤10）车间B（可用工时≤8）1工时/个1工时/个1工时/个6元/个无数量限制4元/个数量≤7产品甲产品乙建立数学模型：通过分析，甲乙两种产品获得总利润最大取决于合理配置甲乙两种产品的生产数量，在此用未知数x1表示生产甲产品的数量，用未知数x2表示生产乙产品的数量，把设定的未知数x1、x2称为决策变量。运筹学2020年7月25日星期六第9页第1章线性规划基础甲乙两种产品获得的总利润表示为6x1+4x2，可用数学的表达式表示为z=6x1+4x2。为了表示获得总利润最大，用maximize缩写max来标识，即把上面的代数式写为maxz=6x1+4x2的形式。由高等数学中函数的定义可知，此式显然是一种函数式，x1、x2是自变量，z是因变量，即此式是追求目标z值最大的关于x1、x2的函数，我们把这个函数称为目标函数。现在从企业内部资源即车间可用工时的角度考虑：针对车间A，因为生产单位甲产品需要占用车间A的工时为2小时，那么生产x1个甲产品占用车间A的工时就为2x1小时；生产单位乙产品需要占用车间A的工时为1小时，那么生产x2个乙产品占用车间A的工时就为x2小时；车间A的可用工时为10个小时，所以生产x1个甲产品、x2个乙产品占用车间A的总共工时不能超过10小时，即有2x1+x2≤10。针对车间B进行同样的分析，可有代数式x1+x2≤8。现在从企业外部即市场限制的角度考虑：市场对甲产品无数量限制，市场对乙产品数量限制是不能多于7个，即有代数式x2≤7；另外，产品的产量不能为负数，也不能为小数，因此x1、x2必须是大于等于0的整数，即有x1,x2≥0且为整数。运筹学2020年7月25日星期六第10页第1章线性规划基础以上根据问题的约束条件产生的方程，称其为约束条件方程，将约束条件方程合在一起称为约束条件方程组，用subjectto的缩写s.t.来表示此类方程组。将上面所有的代数式合在一起，就是该问题的数学模型：为整数且21212212121,,0,78102..46xxxxxxxxxtsxxzmax此例是基于车间有限的工时资源以及市场对甲乙产品数量的限制，对甲乙两种产品的生产数量进行合理确定，从而获取最大的利润运筹学2020年7月25日星期六第11页第1章线性规划基础下面是追求一定的目标如何使付出的代价最少的线性规划问题示例。某公司要生产2000公斤由两种原材料A、B构成的混合物，已知原材料的购买价格分别是原材料A为6元/公斤、原材料B为5元/公斤，要求生产出的混合物必须满足以下规定：（1）混合物中包含原材料A至少25%。（2）混合物中包含原材料A不能多于65%。（3）混合物中包含原材料B至少30%。现在需要设计使成本最低的混合物配制方案。问题分析：把上面的问题用逻辑图的形式进行分析，如下图所示。≤65%≥25%≥30%市场购买市场购买6元/公斤5元/公斤原材料A原材料B目标2000公斤混合物运筹学2020年7月25日星期六第12页第1章线性规划基础建立数学模型：设定决策变量x1表示购买原材料A的数量，x2表示购买原材料B的数量，由此可知，购买原材料A、原材料B的总成本就为6x1+5x2，用代数式表示为z=6x1+5x2，为了表示总成本最低，用minimum的缩写min来标识，即目标函数写为minz=6x1+5x2。从配置混合物2000公斤的角度考虑：有约束条件方程x1+x2=2000。有约束条件方程x1/2000≥25%、x1/2000≤65%。有约束条件方程x2/2000≥30%；原材料A、B的数量不能为负数，因此x1、x2必须是大于等于0的数。0,%302000/%652000/%252000/2000..56212112121xxxxxxxtsxxzmin此例是追求配置2000公斤混合物的目标，通过购买原材料A、原材料B的合理数量，使付出的成本最少。运筹学2020年7月25日星期六第13页第1章线性规划基础二建立线性规划模型的步骤前面提到，把实际问题用数学语言的形式描述出来就是建立数学模型的过程，前面两个例题就是用数学函数、等式或不等式的形式把实际的问题抽象成数学描述。建立线性规划模型的一般步骤如下：第一步：确定决策变量用设定的未知数来表示线性规划问题中未知的量，把这个设定的未知数称为决策变量。确定合理的决策变量是成功建立数学模型的关键。第二步：确定目标函数线性规划问题都有特定的追求目标，把所要追求的目标用函数的形式描述出来，这个函数称为目标函数。由高等数学函数的定义可知，这个函数是以决策变量为自变量的函数。第三步：确定约束条件方程组给出的问题有若干个约束条件，把这些约束条件列成代数方程式，相应的代数方程式称为约束条件方程，这些约束条件方程组成的方程组称为约束条件方程组。另外，还要注意决策变量自身取值的约束。运筹学2020年7月25日星期六第14页第1章线性规划基础§1.2线性规划模型的特点及三种描述形式一线性规划模型的特点通过第1.1节的两个例题，基本可以看出线性规划问题的特点：1.每个问题都有一定的追求目标，追求的目标可以表示为变量（决策变量）的线性函数（所谓线性函数就是一次多项式形式的函数）。2.问题有若干个约束条件，这些约束条件可以用线性等式或线性不等式描述。3.在满足约束条件方程组的情况下，如果决策变量连续取值，问题就有无穷组解。求解的过程就是求出若干个可行的组解出来，在若干个可行的组解中，选出使目标函数值达到最大或最小的一组或多组解的最优方案，所以从选择方案的角度看，就是规划问题，但从使目标函数值达到最大或最小的角度看，又是优化问题。具有上述三个特征的问题称为线性规划问题。基于线性规划问题的三个特征，线性规划模型中所谓“线性”的主要含义是：（1）目标函数是线性的函数形式，有可能是求最大值，如追求利润最大，也有可能是求最小值，如追求成本最低。（2）约束条件方程组由线性等式或线性不等式组成，有≤、=、≥三种形式。运筹学2020年7月25日星期六第15页第1章线性规划基础特别提示:（1）若问题追求的目标只有一个，即线性规划模型的目标函数只有一个，称为单目标线性规划问题，如前面的两个例题；若问题追求的目标不止一个，即线性规划模型的目标函数至少有两个，称为多目标线性规划问题，多目标线性规划问题不作为本书的内容。（2）在线性规划模型中，目标函数和约束条件方程组中决策变量的系数都是确定的常数，同时约束条件方程右端也是确定的常数，把这类线性规划模型称为确定型线性规划问题，如前面的两个例题。但针对复杂的现实问题，构建的线性规划模型的目标函数或约束条件方程组中决策变量的系数可能是不确定的，或者约束条件方程右端不是确定的常数，这类线性规划模型就不是确定型线性规划问题，此类线性规划问题不作为本书的内容。（3）在建立同一个问题的线性规划模型时，由于决策变量的设置方法存在多样性，所以同一个问题的线性规划模型的形式也就不唯一。运筹学2020年7月25日星期六第16页第1章线性规划基础二线性规划模型的三种描述形式1.一般形式对具体的线性规划问题，将模型写成以下的一般形式：njxbxaxaxabxaxaxabxaxaxatsxcxcxczminmaxjmnmnmmnnnnnn,,2,1,0),(),(),(..)(2211222221211121211122112.简化形式为了方便讨论，有时将模型写成以下的简化形式：njxmibxatsxczminmaxjijnjijjnjj，，，，，,21,0,21),(..)(113.矩阵向量形式为了便于理论证明或数学上讨论方便，有时将模型写成以下的矩阵形式：),(;),(,,2,1;,2,1],[),,(0),(..)(212121mTnTijnbbbbxxxXnjmiaAcccCXbAXtsCXzminmax其中运筹学2020年7月25日星期六第17页第1章线性规划基础§1.3线性规划模型的构建方法示例针对复杂的实际问题