（精选）IE10_OR05 CH1 线性规划及单纯形法.ppt

第5讲目录，CH1线性规划和单纯形法1.1线性规划问题及其数学模型1.2线性规划问题的解法1.3线性规划的单纯形法1.3.1单纯形法的基本思想1.3.2初始基可行解的确定1.3.3最优性检验1.3.4基可行解的转换1.3.5单纯形法步骤1.4单纯形表1.5单纯形法应用的几个问题1.6线性规划建模实例。摘要：线性规划求解流程图(P35)，2，1.5单纯形法应用中的几个问题，1.5.1大M法的退化和2阶段单纯形法1.5.2退化，1.5.2退化。如果规则用于确定变化变量，有时会有两个以上的最小比率，因此一个或多个基础变量在下一次迭代中等于零，这将导致回归。当回归发生时，循环就发生了。1974年，Bland提出了一个简单的规则：(1)选择J0中下标最低的非基变量xk作为替代变量k=min (j | j0) (2)当有两个或更多个按规则计算的最小比率时，总是选择下标最低的替代变量。例如，线性规划建模被广泛使用：85%的财富500强公司在军事、工业、农业等领域。使用线性规划技术来帮助决策。企业决策包括生产计划、运输、财务、营销等。建模步骤：1。了解需要解决的问题，了解解决问题的目标和条件；2.定义决策变量(x1，x2，xn)，每组值代表一个方案；3.将目标函数写成决策变量的线性函数形式，以确定最大或最小目标；4.使用一组决策变量的等式或不等式来表示在解决问题的过程中必须遵循的约束条件。线性规划解决方案工具简介，首字母缩略词EXCELSOLVERLINDLINE近交互性和离散优化器。也就是“交互式线性和离散优化求解器”的首字母缩写.可以用来解决线性规划(线性规划)，整数规划(整数规划)和二次规划(QP -四次规划)问题。这个软件包是由美国芝加哥大学的LinusScharge教授在1980年左右开发的。它专门用于解决优化问题。经过不断的改进和扩展，LINDO公司成立，开展商业运营，并取得了巨大的成功。全球财富杂志500强企业中有一半以上使用该公司的产品，25强企业中有23家使用该产品。软件包有强大的功能和许多版本，但我们只使用演示版(试用版)。演示版本与正式版本基本相似，只是解决问题的规模有限，并且变量总数不超过30个，这在我们当前的使用过程中已经足够了。对于第一个LINDO，LINDO假设所有变量都是非负的，因此非负约束不需要输入到计算机中。LINDO也不区分变量中的大小写字符；约束条件中的=可以替换为，来求解一个简单的线性规划(LP)问题，它的Lindo程序是：例如，9，现在我们用Lindo软件来求解这个模型，点击工具栏中的图标，就会得到下面的运行状态窗口：添加Lindo求解器，10，结果如下所示，最优解，最优目标值，最优解的每个变量的值，双重价格， 影子价格：表示当非基变量增加一个单位而其他变量不变时(对于max-type问题)，目标函数的缩减量，松弛变量的值紧约束，简单行方法执行两次迭代，变量以字母开头，不区分大小写，变量名不能超过8个字符； 变量不能出现在约束条件的右端，并且右端只能是常数。变量和系数之间可以有空格，但绝对不能有运算符。任何操作符号，如()和逗号，等。林多不接受(评论声明除外)；模型中的表达式应该被转换，例如，(X 1)2 2X2 3Y不能出现，但应该写成3x22x3y1该模型假设所有变量都是非负的。命令“free”可以在模型的“end”语句之后使用，以取消变量的非负假设。它的用法是用变量名跟随“free”。在模型的“结束”语句之后，您可以使用命令“SUB”来设置变量的上限，使用命令“SLB”来设置变量的下限。林多以“！”开头开头是一个解释性声明，也标有“；”结束。使用Lindo软件的一些注意事项：12。例如，有一个制造车间，生产桌子、桌子和椅子。原材料、木匠和油漆工的数据如表1所示。表1。如果生产的桌子不超过5张，如何安排这三种产品的生产才能使收入最大化？桌子、桌子和椅子的产量分别用。建立了低压：型。lpoptimomfoundattepobjectivefunctionvalue 1)280.0000000 variablevaluereducedcostsi 2.000000.000000 x 2.00000005.000000 x 38.000000000000 RowslackorPlusdualPrices 2)24.0000000003)。00000010.0000004)。00000010.0000005)5.0000000.0000000，Lindo经过两次迭代获得了最优解。一条昼夜服务公交线路在每个时间段内所需的司机和乘务员人数如下：在每个时间段开始时设置司机和乘务员工作，连续工作8小时。询问如何为公交线路安排司机和乘务员以满足工作需要，同时至少提供司机和乘务员。一、人力资源配置问题，解决方案：让xi代表一班开始工作的司机和机组人员的数量，从而建立以下数学模型。目标函数：Minx1 x2 x3 x4 x5 x6约束：s t x1x 660x 1 x270x 2 x360x 3 x450x 4x 520x 5 X630x 1，x2，x3，x4，x5，X6 0，17，例2。一家中型百货公司，其对销售人员的需求进行了统计分析，如下表所示。为了保证销售人员的充分休息，销售人员每周工作五天，休息两天，并要求连续休息两天。我们应该如何安排销售人员的工作和休息，以满足工作的需要，并尽量减少销售人员的数量？解决方法：让Xi (I=1，2，7)代表从星期一到星期日开始休息的人数，因此我们建立了以下数学模型。目标函数：Minx1 x2 x3 x4 x5 x6 x7约束条件：s t x1 x2 x3 x4 x528 x2 X4 X5 x615x 3 X4 X5 X6 x724x 4 X5 X6 x7 x125x 5 X6 x7 x1 x219x 6 x7 x1 x3 X428x 1，x2，x3，X4，X5，X6，x70，19，例3。一家公司正面临外包合作或自我生产的问题。公司生产a、b、c三种产品，都需要经过铸造、机加工和装配三个车间。产品甲和乙的铸件可以外包、合作或自己生产，但产品丙必须由我厂铸造，以确保质量。数据显示在表格中。问：为了获得最大利润，公司生产多少件甲、乙、丙产品？在产品甲、乙的铸造中，我们公司应该铸造多少件，外包生产多少件？二、生产计划问题、解决方案：设X1、X2、X3为我公司三个工序分别加工的甲、乙、丙产品件数，X4、X5为我公司外包铸造后分别加工组装的甲、乙产品件数。问xi的利润：利润=销售价格-所有成本之和：产品A的自制利润=23-(3 2 3)=15产品A的铸造外包，剩余的自制利润=23-(5 2 3)=13产品B的自制利润=18-(5 1 2)=10产品B的铸造外包，剩余的自制利润=18-(6 1 2)=9产品C的利润=16-(4 3 2)=7获得基于以上分析，可以建立以下数学模型：目标函数：Max15x1 10 x2 7x3 13x4 9x5约束条件：5 x 1 10 x2 7 x380006 x 1 4x 28 x 3 6 x4 x 5120003 x 1 2 x 3 x 3 x 4 x 4 x 510000 x 1，x 2，x 3，x 4，x 5 0，22， 例4一家工厂需要制造100套钢架，每套钢架一个圆钢，长度分别为2.9米、2.1米和1.5米。众所周知，每种原材料的长度为7.4米。问：应该如何切断原材料，以尽量减少原材料的使用量？ 解决方案：可设计以下五种下料方案，如下表所示。设X1、X2、X3、X4和X5分别为上述五种方案下下料的原材料数量。所以我们建立了下面的数学模型。目标函数：Minx1 x2 x3 x4 x5约束条件：s t x12x 2 x41002 x32x 4 X51003 x1x22x 3 3x 5100 x 1，x2，x3，x4，X5 0，组切割和下料问题。使用“运筹学”软件计算并获得最佳下料方案：按方案1切割30块；根据方案2下料10件；根据计划4，将切割50块。即x1=30x2=10x3=0；x4=50X5=0；生产100套钢架只需要90种原材料。注意：建立这种类型的数学模型时，最好使用大于或等于约束的数字，而不是等于约束的数字。因为在应用某些下料方案时，有时可能会添加某种规格的圆钢，但这可能是最佳方案。如果我们用一个等于的符号，这个方案是不可行的。某部门有200万元资金，将考虑在未来五年投资以下项目。已知：项目甲：从第一年到第五年，每年年初投资，年末可收回原利润的110%；项目二：从第一年到第四年，投资可以在每年年初进行，利润可以在下一年年底收回125%，但每年最高投资金额不能超过30万元。项目三：第三年年初需要投资，第五年年底可收回利润140%，但最高投资不能超过80万元。项目D:第二年年初需要投资，第五年年底可收回利润155%，但最高投资不超过100万元。根据测算，每笔1万元投资的风险指数如下表所示：问：a)如何确定这些项目的年投资金额，以使第五年末资本的本息金额最大化？b)如何确定这些项目的年度投资金额，以便在第五年年底330万元的基础上，使其投资的总风险系数最小化？解决方案：1)确定决策变量：对于连续投资问题，让Xij(1=1 5，J=1 4)代表在一年的第一年开始时对A(j=1)，B(j=2)，C(j=3)，D(j=4)项目的投资额。通过这种方式，我们建立了以下决策变量：x11x 21 x 31x 41 x 51 bx 12 x 22x 32 x 42cx 33 dx 24，25，2)约束条件：第一年：a投资可以在年底收回，所以所有的资金都应该在第一年年初投资，所以x11x12=200第二年：投资只能在第二年年底收回，所以第二年年初有1.1x11的资金，所以x21x22x24=1.1x11第三年：年初资金为1.1x21.25x12，因此x31x 32 x33=1.1x 21.25 x12；第四年：年初资本为1.1x131 1.25x22，所以x41x42=1.1x131 1.25x22第五年：年初资本为1.1x141 1.25x32，所以x51=1.1x41 1.25x32；b、c和d的投资限制：xi230(i=1、2、3和4)，x3380，x241003)目标函数和模型：a)maxz=1.1x 151 1.25 x 421.4 x 33 1.55 x 24s . t . x11x 12=200 x21x 22 x 24=1.1x 11。x31 x32 x33=1.1x21 1.25x12x41 x42=1.1x31 1.25x22x51=1.1x41 1.25x32xi230(i=1、2、3、4)，x3380，x24100 xij0(i=1、2、3、4、5；J=1，2，3，4)，投资问题，26、b，b)变量集与问题a相同，目标函数为最小风险，问题a的约束条件中有minf=x11x 21 x31x 41 x513(x12x 22 x32x 42)4x 335.5 x24，加上“第五年末资本利润为330万元”的条件。那么模型如下：MINF=(x11x 21x 31 x41x 51)3(x12x 22 x32x 42)4x 335.5 x24s . t . x11x 12=200 x22x 24=1.1x 11；x31 x32 x33=1.1x21 1.25x12x41 x42=1.1x31 1.25x22x51=1.1x41 1.25x32xi230(i=1、2、3、4)，x3380，x241001.1 x51 1.25 x42 1.4 x33 1.55 x24330 xij0(I=1、2、3、4、5；J=1，2，3，4)，投资问题，27，课本例题：P40P42分批问题生产和储存问题，第1章线性规划和单纯形法(摘要)，1。线性规划的概念(1)形成决策变量的线性规划模型的目标函数：max(min)Z(决策变量的线性函数)约束条件：s t(满足包含决策变量的线性方程或不等式)，29，(2)一般形式：30，max=xns.t. a11x1a12x2.a1nxn=b1a21x1a22x2.a2nxn=B2am 1x 1 a2 x2.amnxn=bmxj0；j=1，2，nbi0；I=1，2，m，(3)标准形式，31，标准形式的线性规划具有以下四个特点：目标最大化；(2)约束是线性方程；(3)决策变量不是负的；正确的项目不是否定的。(4)剩余变量、松弛变量及其意义，32，2。与线性规划解相关的概念，(1)概念：凸集、可行解、可行域、最优解、最优值、基、基变量、基解、基可行解、可行基和最优基。(2)可行域、基本解、基本可行解和最优基之间的关系。(1)建立直角坐标系(2)说明约束条件和寻找可行解(3)说明代表目标函数的直线和目标函数值增加(或减少)的方向(4)寻找最优解(34)，(4)单纯形法，(1)理论基础定理1如果线性规划问题的可行域存在，那么可行域是凸集。定理2LP问题的基本可行解与可行域的顶点一一对应。定理3如果线性规划问题有一个最