运筹学论文

姓名：张弛班级：经统1401学号：1409100138联系方式：15172323472运筹学中的线性规划问题摘要：线性规划是运筹学中研究较早、发展较快、方法较成熟一个重要分支，其应用极其广泛，其作用已为越来越多的人所重视，越来越多地渗透到农业生产、商业活动、军事行动和科学研究等各个方面。本文由以下四个部分组成：第一部分初步介绍了线性规划问题产生的历史背景、发展概况；第二部分介绍了线性规划问题的求解方法，包括图解法、单纯形法、大M法和两阶段法等方法；第三部分对图解法、单纯形法、大M法进行了举例说明；第四部分介绍了线性规划在经济中的实际应用。关键词：运筹学线性规划图解法单纯形法经济应用一、线性规划问题的产生与发展运筹学是用数学方法研究各种系统最优化问题的学科。其研究方法是应用数学语言来描述实际系统，建立相应的数学模型，并对模型进行研究和分析，据此求得模型的最优解；其目的是制定合理运用人力、物力和财力的最优方案；为决策者提供科学决策的依据；其研究对象是各种社会系统，可以是对新的系统进行优化设计，也可以是研究已有系统的最佳运营问题。因此，运筹学既是应用数学，也是管理科学，同时也是系统工程的基础之一。在生产生活、管理决策等各类经济活动中，我们经常遇到这样的问题：什么是最好的决策、最佳的方案？例如企业在生产条件不变的前提条件下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源使得成本最低；又如工厂在各原材料固定的情况下，如何最佳地使用原材料使得利润最大等。这类统筹规划问题用数学语言表达，先根据问题要达到的目标选取适当的变量，问题的目标通过用变量的函数形式表示，对问题的限制条件用有关变量的等式或不等式表达。当变量连续取值，且目标函数的约束条件均为线性时，这类模型为线性规划的模型。线性规划模型建模相对简单，有通用算法和计算机软件，是运筹学中应用最为广泛的一个分支。有些规划问题的目标函数是非线性的，但往往可以采用分段线性化等方法，转化为线性规划问题。线性规划问题的基本特点是：目标函数和所有约束条件都是线性的，所追求得是在满足约束条件的前提下，实现目标函数的最优化。线性规划已不仅仅是一种数学理论和方法，而且成了现代化管理的重要手段，是帮助管理者与经营者做出科学决策的一个有效的数学技术。二、求解线性规划问题的方法1、图解法（1）优缺点①图解法：图解法简单直观，求解线性规划问题时不需将数学模型化为标准型，可以直接在平面上作图，但此法只试用于二维问题，故有一定局限性。②用图解法求解，有助于了解线性规划问题求解的基本思想。它可以直接看出线性规划问题的几种情况：有唯一最优解有无穷多组最优解无可行解无有限最优解（即为无界解）（2）图解法的步骤①建立平面直角坐标系；②图示约束条件，找出可行域；③图示目标函数，即为一条直线；④将目标函数直线沿其法线在可行域内向可行域边界平移直至目标函数。2、单纯形法（1）单纯形法原理①基本思想：从可行域中的某个基本可行解开始到另一个基本可行解，直到目标函数达到最优。②理论基础：定理1若LP问题可行域存在，则可行域是个凸集。定理2LP问题的基可行解与可行域的顶点一一对应。定理3若LP问题存在最优解，则一定存在一个基可行解是最优解。（2）单纯形法的步骤及解法①找出初始基可行解，确定初始基可行解，建立初始单纯形表。②检验此基本可行解是否为最优解，即检验各非基变量𝑥𝑗检验数𝜎𝑗，若所有𝜎𝑗≤0（𝑗=𝑚+1，⋯，𝑛）则已经得到最优解，计算停止；否则转下一步。③在𝜎𝑗0（𝑗=𝑚+1，⋯，𝑛）中若有某个检验数𝜎𝑘对应的非基变量𝑥𝑘的系数列向量𝑃𝑘=（𝑎1𝑘，𝑎2𝑘，⋯，𝑎𝑛𝑘）T≤0，则此问题为无界解，停止计算；否则转下一步。④根据max(𝜎𝑗0)=𝜎𝑘，确定非基变量𝑥𝑘为换入变量；再根据𝜃法则θ=min(𝑏𝑖𝑎𝑖𝑘|𝑎𝑖𝑘0)=𝑏𝑙𝑎𝑙𝑘确定基变量𝑥𝑙为换出变量。⑤实施枢轴变量，即以𝑎𝑙𝑘为主元素进行枢轴运算（亦即进行矩阵的行变换），使𝑃𝑘变换为第1行的元素为1，其余的元素为0；并将𝑋𝐵列中的𝑥𝑙换为𝑥𝑘，从而得新的单纯性表；重复②~⑤，直到终止。3、两阶段法、大M法以及运用人工变量法求解非规范型的线性规划问题（1）两阶段法①原理：此方法是将加入人工变量后的线性规划问题分成两个阶段来求解。第一阶段：其目的是为原问题求初始基本可行解。为此，对于求极大化（或极小化）的线性规划问题，建立一个新的人工变量的目标函数——人工变量的系数均为−1（或+1），对新的问题：max𝑤=−𝑥𝑛+1−𝑥𝑛+2−⋯−𝑥𝑛+𝑚或min𝑤=𝑥𝑛+1+𝑥𝑛+2+⋯+𝑥𝑛+𝑚𝑠.𝑡.{𝑎11𝑥1+⋯+𝑎1𝑛𝑥𝑛+𝑥𝑛+1=𝑏1⋯𝑎𝑚1𝑥1+⋯+𝑎𝑛𝑚𝑥𝑛++𝑥𝑛+𝑚=𝑏𝑚𝑥1，⋯，𝑥𝑛≥0，𝑥𝑛+1，⋯，𝑥𝑛+𝑚≥0用单纯形法求解。若w=0.即所有的人工变量都换为非基变量，说明原问题已经得到了初始基本可行解；反之，若目标函数w的值为负（或为正），则人工变量中至少有一个为正，这表示原问题无可行解，应停止计算。第二阶段：将第一阶求得的基本可行解对原问题的目标函数进行优化，即将目标函数换成原目标函数，以第一阶段得到的最终单纯形表除去人工变量的列后作为第二阶段计算的初始表，继续用单纯形法以求得问题的最优解。②计算方法：单纯形法。（2）大M法①原理：人工变量在目标函数中的系数确定：若目标函数为maxz，则系数为−𝑀；否则为𝑀。②计算方法：单纯形法。三、线性规划问题举例例1分别用图解法和单纯形法求解下列线性规划问题，并指出单纯性法迭代的每一步相当于图形上的哪一个顶点。max𝑧=2𝑥1+𝑥2s.t.{3𝑥1+5𝑥2≤156𝑥1+2𝐱𝟐≤24𝑥1,𝑥2≥0①图解法图1图1中的阴影区域为可行域，可见目标函数𝑧=2𝑥1+𝑥2在点𝐴2处达到最大，求解方程组{3𝑥1+5𝑥2=156𝑥1+2𝑥2=24可知𝐴2的坐标为（154，34），所以𝑋∗=（154，34）T，𝑧∗=2×154+34=334②单纯形法max𝑧=2𝑥1+𝑥2+0𝑥3+0𝑥4𝑠.𝑡.{3𝑥1+5𝑥2+𝑥3=156𝑥1+2𝑥2+𝑥4=24𝑥1,𝑥2,𝑥3,𝑥4≥0由线性规划问题的标准型可列出初始单纯形表逐步迭代，计算结果如下表所示。表1𝑐𝑗2100𝜃𝑖𝐶𝐵𝑋𝐵b𝑥1𝑥2𝑥3𝑥400𝑥3𝑥415243[6]52100154𝑐𝑗−𝑧𝑗210002𝑥3𝑥13401[4]1/310—1/31/63/412𝑐𝑗−𝑧𝑗01/30—1/312𝑥2𝑥13/415/401101/4—1/12—1/85/24𝑐𝑗−𝑧𝑗00—1/12—7/24单纯形表的计算结果表明：𝑋∗=（154,34,0,0）𝑇，𝑧∗=2×154+34=334单纯性迭代的第一步得：𝑋（0）=（0,0,15,24）𝑇，表示图中原点（0,0）单纯性迭代的第二步得：𝑋（1）=（4,0,3,0）𝑇，表示图中𝐴1点单纯性迭代的第三步得：𝑋（2）=（154,34,0,0）𝑇，表示图中𝐴2点例二用大M法求解下列问题：min𝑧=𝑥1+𝑥2−3𝑥3𝑠.𝑡.{𝑥1−2𝑥2+𝑥3≤112𝑥1+𝑥2−4𝑥3≥3𝑥1−2𝑥3=1𝑥𝑗≥0，𝑗=1，⋯，3解引进松弛变量𝑥4、剩余变量𝑥5和人工变量𝑥6、𝑥7，解下列问题：min𝑧=𝑥1+𝑥2−3𝑥3+0𝑥4+0𝑥5+𝑀(𝑥6+𝑥7)𝑠.𝑡.{𝑥1−2𝑥2+𝑥3+𝑥4=112𝑥1+𝑥2−4𝑥3−𝑥5+𝑥6=3𝑥1−2𝑥3+𝑥7=1𝑥𝑗≥0，𝑗=1，2，⋯，7用单纯形法计算如下：表2—1𝑐𝑗11—300MM𝐶𝐵基b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥70𝑥411M𝑥63M𝑥711−21100021−40−110[1]0−20001𝑐𝑗−𝑧𝑗4M1−3M1−M−3+6M0M00由于𝜎1𝜎20，说明表中基可行解不是最优解，所以确定𝑥1为换入非基变量：以𝑥1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。𝜃=min(111，32，11)=1=11因此确定1为主元素（表2-1中以方括号[]括起），意味着将以非基变量𝑥1去置换基变量𝑥7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将𝑥1的系数列（1，2，1）𝑇变换成𝑥7（0，0，1）𝑇，变换之后重新计算检验数。变换结果见表2—2表2—2𝑐𝑗11—300MM𝐶𝐵基b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥70𝑥410M𝑥611𝑥110−23100−10[1]00−11−210−20001𝑐𝑗−𝑧𝑗M+101−M−10M03M−1由于𝜎2𝜎30，说明表中基可行解仍不是最优解，所以确定𝑥2为换入非基变量：以𝑥2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量𝑥2去置换基变量𝑥6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将𝑥2的系数列（−2，1，0）𝑇变换成𝑥6（0，1，0）𝑇，变换之后重新计算检验数。变换结果见表2—3表2—3𝑐𝑗11—300MM𝐶𝐵基b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥70𝑥4121𝑥211𝑥1100[3]1−22−50100−11−210−20001𝑐𝑗−𝑧𝑗200−101M−1M+1由于𝜎30，说明当前表中基可行解仍不是最优解，所以确定𝑥3为换入非基变量：又由于𝑥3的系数列的正分量只有3，所以确定3为主元素，意味着将以非基变量𝑥3去置换基变量𝑥4，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将𝑥3的系数列（3，0，−2）𝑇变换成𝑥4（1，0，0）𝑇，变换之后重新计算检验数。变换结果见表2—4表2—4𝑐𝑗11—300MM𝐶𝐵基b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7−3𝑥341𝑥211𝑥190011/3−2/32/3−5/30100−11−21002/3−4/34/3−7/3𝑐𝑗−𝑧𝑗−20001/31/3M−1/3M−2/3至此，无负的检验数且基变量中不含人工变量（即人工变量在基可行解中取0值），求得原问题的最优解：x1∗=9,x2∗=1,x3∗=4,最小目标函数值为-2。四、线性规划在经济中的应用随着经济社会的不断发展，企业面临着更加激烈的市场竞争。企业必须不断提高盈利水平、增强其获利能力，在生产、销售等一系列过程中发挥出自己的优势、提高企业效率、降低成本、形成企业的核心竞争力，才能在激烈的竞争中立于不败之地。利用线性规划问题我们可以解决很多问题。例如：在一定资源限定条件下，组织安排生产，获得最好的经济效益，使得产量最大，利润最大，效用最大；也可以在满足一定需求条件下，进行合理配置，使成本最小；还可以在任务确定后，进行统筹规划、合理安排、用最少的资源达到目标。以下为线性规划在经济中的应用举例：某企业有两个车间，各生产两种产品，生产这些产品所需的设备台数，人工工时及单位产品利润如表3所示表3生产计划列表车间产品设备人工利润/百元甲AB36233.5乙CD642276现在企业具有设备102台，人工工时46，计划部门将设备及人工进行如下分配：分给甲车间台时48，人工工时26；分给乙车间设备台时54，人工工时20.问计划部门如此进行分配是否合理？解设𝑥1、𝑥2分别为A、B两种产品的计划产量，𝑥3、𝑥4分别为C、D产品的计划产量。分别建立两个车间的生产组织的数学模型。甲车间的生产组织模型为：max𝑆1=3.5𝑥