单纯形替换法、步长加速法、Power法等适用于目标函数的导数不存在或导数过于复杂的情形.
最小二乘法是求解最小二乘问题的特定解法.
求解约束问题的基本方法有Z-容许方向法、梯度投影法、外点法(外部罚函数法)、内点法(内部罚函数法)、乘子法、线性化法、简约梯度法等.
Z-容许方向法：利用线性规划得到搜索方向
p，然
k
后再通过受限的直线搜索确定步长因子
t.
k
梯度投影法：利用对梯度投影的方式得到搜索方向
p，然后再通过受限的直线搜索确定步长因子k t.
k
外点法、内点法、乘子法：通过求解一系列的无约束问题解约束问题.而这一系列无约束问题的目标函数则是根据目标函数及约束函数，通过“惩罚”方式产生.
∶
单纯形法演算 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 无穷 0 4x 24 6 2 0 1 0 4 0 5x 5 1 1 0 0 1 5 j j z c -（检验数） 2 1 首先列出表格，先确定正检验数最大值所在列为主列，然后用b 除以主列上对应的同行数字。除出来所得值最小的那一行为主行，根据主行和主列可以确定主元（交点）。接着把主元化为1并把X4换成X1. ??? ??? ?≥=++=++=+++++=0,,524261550002max 5152 14213 25 4321x x x x x x x x x x x x x x x z ??????? ≥≤+≤+≤+=0 ,5 24261552max 21212122 1x x x x x x x x x z
j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5 1 1 0 0 1 j j z c - 2 1 这时进行初等行列变换，把主列换单位向量，主元为1。也就是X5所在行减去X1所在行。并且重新计算检验数。 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5-4 1-1=0 1-2/6 =4/6 0-1/6=-1/6 1 j j z c - 2-2*1-0*0-0*1=0 1-0*5-2*2/6-0*4/6=1/3 0-0*0-2*1/6-0*-1/6=-1/3 再次确定主元。为4/6。然后把X5换成X2。并且把主元化成1。
工程优化设计中单纯形法的基本原理 张云龙 （大连海洋大学土木工程学院辽宁大连116023) 摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。在此基础上进一步讨论单纯形法的推广，即大M法和两相法。 关键词：线性规划图解法单纯形法大M法 THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGN ZHANG Y un-long (Dalian Ocean University, College of Civil Engineering, Liaoning, Dalian 16023) Abstract: From the instance of the starting linear programming mathematical model of the basic principles of the graphic method, and then focus on the standard solution - simplex method. To promote further discussion on this basis, the simplex method, that is, the big M method and two-phase method. Key W ords: Linear programming；Graphic method；Simplex Method; Big M Method 1引言 在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。 虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。尤为重要的是，对于几乎所有规划问题的讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等错误！未找到引用源。。 因此，深刻理解线性规划问题及其标准解法——单纯形法，显得尤为关键。 2线性规划问题 2.1数学模型 线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。例如，美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？ 表1-1 工时及利润简表
利用修正单纯形法解线性规划问题一软件示意：
二代码说明： Dim A(1 To 3, 1 To 6) As Double '矩阵A Dim a1(1 To 3) As Double '矩阵A的第一列向量 Dim a2(1 To 3) As Double '矩阵A的第二列向量 Dim a3(1 To 3) As Double '矩阵A的第三列向量 Dim a4(1 To 3) As Double '矩阵A的第四列向量 Dim a5(1 To 3) As Double '矩阵A的第五列向量 Dim a6(1 To 3) As Double '矩阵A的第六列向量 Dim B_(1 To 3, 1 To 3) As Double '基矩阵B的逆矩阵 Dim XB(1 To 3) As Double '基本可行解 Dim b(1 To 3) As Double '右端向量b Dim C(1 To 6) As Double '检验数 Dim CB(1 To 3) As Double '基本可行解对应的检验数 Dim π(1 To 3) As Double '单纯形乘子矢量 Dim r(1 To 6) As Double '检验矢量r Dim r_min As Double '检验矢量最小值 Dim k_sign As Integer '检验矢量最小值对应的位置 Dim Y(1 To 3, 0 To 6) As Double '矩阵y Dim just_vector(1 To 3) As Double Dim liji_min As Double '用于判断离基变量所用值 Dim r_sign As Integer '用于记录离基变量对应的位置 Dim main_yuan As Double '用于存放主元 Dim Erk(1 To 3, 1 To 3) As Double Dim Exchange_B(1 To 3, 1 To 3) '在矩阵Erk与矩阵B_进行乘法运算时，作为矩阵B_的替换矩阵
2.2 单纯形法 考虑标准最大化线性规划问题的)15.1( max ∑=n j j j x c 1 ..t s ?????=≥=≤∑=n j x m i b x a j i n j j ij ,...,2,10,...,2,11 我们首先对它的第i 个约束条件引入松弛变量i s ,m i ,...,2,1=,并且以η表示目标函数值,则获得标准型)15.1(的等价线性规划,也称为标准型)15.1(的标准格式: max ∑==n j j j x c 1η ..t s ??? ????=≥=≥=-=∑=m i s n j x m i x a b s i j n j j ij i i ,...,2,1,0,...,2,1,0,...,2,1,1 )10.2( 从例1.2线性规划问题的求解过程中可以看到,随着迭代的继续,决策变量和松弛变量相互交织,成为一体,所以为了便于分析,令i i n s x =+m i ,...,2,1=,并引入以下标记: ),...,,,...,(),...,,,,...,,(1212121m n n n m n x x x x x s s s x x x ++= 那么,我们将)10.2(改写为: max ∑==n j j j x c 1η ..t s ?? ???++=≥=-=∑=+m n n n j x m i x a b x j n j j ij i i n ,...,1,,...,2,1,0,...,2,1,1 )11.2( 式)11.2(就是标准型线性规划问题)15.1(的标准格式或初始单纯形,显然若令0=j x ,n j ,...,2,1=,则有i i n b x =+,m i ,...,2,1=,则),...,,,0,...,0(210m b b b x =构成了标准型线性规划问题)15.1(的初始基可行解。随着搜索最优解过程的继续,单纯形迭代算法将从
第4章 单纯形法的计算方法单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代,直到目标函数实现最大值或最小值为止。 4.1 初始基可行解的确定 为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z = 从Pj ( j = 1 , 2 , ? , n)中一般能直接观察到存在一个初始可行基 （2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对 及 ( i = 1 , 2 , ? , m; j = 1 , 2 , ? , n)进行编号, 则可得下列方程组 显然得到一个m×m单位矩阵 以B 作为可行基。将上面方程组的每个等式移项得 令由上式得 又因 ≥0, 所以得到一个初始基可行解 （3）第三种情况：对所有约束条件是“ ≥”形式的不等式及等式约
束情况, 若不存在单位矩阵时, 就采用人造基方法。即对不等式约束减去一个非负的剩余变量后, 再加上一个非负的人工变量; 对于等式约束再加上一个非负的人工变量, 总能得到一个单位矩阵。 4.2 最优性检验和解的判别 对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况, 为此需要建立对解的判别准则。一般情况下, 经过迭代后可以得到： 将上代入目标函数，整理后得 令 于是 再令 则 (1) 最优解的判别定理 若为对应于基B的一个基可行解，且对于一切 且有则 为最优解。称为检验数。 (2) 无穷多最优解的判别定理 若为一个基可行解， 且对于一切 且有 又存在某个非基变量的检验数，则线性规划问题有无穷多最优解。 (3) 无界解判别定理 若为一个基可行解，有一个> 0 ,并且对i = 1 , 2 , ?, m,有≤0 , 那么该线性规划问题具有无界解(或称无最优解)。 4.3 基变换
三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.
解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量
多目标规划 multiple objectives programming 数学规划的一个分支。研究多于一个目标函数在给定区域上的最优化。又称多目标最优化。通常记为VMP。在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方面的研究。1896年法国经济学家V.帕雷托最早研究不可比较目标的优化问题，之后，J.冯·诺伊曼、H.W.库恩、A.W.塔克尔、A.M.日夫里翁等数学家做了深入的探讨，但是尚未有一个完全令人满意的定义。求解多目标规划的方法大体上有以下几种：一种是化多为少的方法，即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法等；另一种叫分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。对多目标的线性规划除以上方法外还可以适当修正单纯形法来求解；还有一种称为层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。 1947年，J.冯·诺伊曼和O.莫根施特恩从对策论的角度提出了有多个决策者在彼此有矛盾的情况下的多目标问题。1951年，T.C.库普曼斯从生产和分配的活动中提出多目标最优化问题，引入有效解的概念，并得到一些基本结果。同年，H.W.库恩和A.W.塔克尔从研究数学规划的角度提出向量极值问题，引入库恩-塔克尔有效解概念，并研究了它的必要和充分条件。1963年，L.A.扎德从控制论方面提出多指标最优化问题，也给出了一些基本结果。1968年，A.M.日夫里翁为了排除变态的有效解，引进了真有效解概念，并得到了有关的结果。自70年代以来，多目标规划的研究越来越受到人们的重视。至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。 化多为少 即把多目标规划问题归为单目标的数学规划（线性规划或非线性规划）问题进行求解，即所谓标量化的方法，这是基本的算法之一。 ①线性加权和法对于多目标规划问题（VMP），先选取向量 要求λi>0(i=1,2，…,m) 作各目标线性加权和
单纯形法步骤： 1. 给定初始点 )0(x 初始单纯形边长 a ， α ， 收缩系数 β ， 延伸系数 γ 以及精度要求 ε。 2. 作出初始单纯形图 3. 找出坏点 )(h x 、好点 )(e x 计算中心点 )1(+n x 及 反射点 )2(+n x 和各点上的目标函数值 4. 比较反射点和除了坏点上的函数值， 5. ⑴. 如果反射点上的函数值比好点差，但比坏点外的其他顶点函数值好，认为反射成功，将反射点代替坏点构成新的单纯形，转7 ⑵. 如果反射点上的函数比好点还要好，说明反射点很好，可以沿此方向作延伸尝试，如果延伸点上的函数值比好点还好，则将延伸点取代坏点，形成新单纯形，转7。反之，延伸点上函数值不如好点，说明延伸失败，但反射还是成功的，所以仍可用反射点代替坏点，然后转7 5. 如果反射点连坏点都不如，说明反射失败，那么作收缩，找出收缩点的函数值，并转 6.；如果反射点仅比坏点好，则将反射点取代坏点，然后收缩，转下一步6。 6. 如果收缩点上函数比坏点还差，说明收缩也失败，作缩小运算，形成缩小后的单纯形转7；反之（即收缩点上的函数值比坏点好），说明收缩成功，用收缩点代替坏点，形成新的单纯形转。转下一步7。 7. 检查是否满足精度要求 ()(1)max (()i n f x f x ε+-≤ 如满足，停止迭代，否则转3，继续迭代。 %三个考察点，最优，次差，最差 best = vx(: , 1) ; fbest = vf(1) ;
soso = vx(: , n) ; fsoso = vf(n) ; worst = vx(: , n+1) ; fworst = vf(n+1) ; center = sum(vx(: , 1:n) , 2) ./ n ; r = 2 * center - worst ;%反射点 fr = feval(fun , r) ; if fr < fbest %比最好的结果还好，说明方向正确，考察扩展点，以期望更多的下降 e = 2 * r - center ; %扩展点 fe = feval(fun , e) ; if fe < fr %在扩展点和反射点中选择较优者去替换最差点 vx(: , n+1) = e ; f(: , n+1) = fe ; else vx(: , n+1) = r ; vf(: , n+1) = fr ; end else if fr < fsoso %比次差结果好，能够改进 vx(: , n+1) = r ; vf(: , n+1) = fr ; else %比次差结果坏，当压缩点无法得到更优值的时候，考虑收缩 shrink = 0 ; if fr < fworst %由于r点更优所以向r点的方向找压缩点 c = ( r + center ) ./ 2 ; fc = feval(fun , c) ; if fc < fr %确定从r压缩向c可以改进 vx(: , n+1) = c ; vf(: , n+1) = fc ; else %否则的话，准备进行收缩
线性规划——单纯形法 设计文档 ——《通用优化模块》 编写人：徐天爽 编写时间：2010年06月完成 2010年06月整理
目录 第一部分功能概述 (1) 第二部分理论知识 (2) 2.1 线性规划标准型 (2) 2.2单纯形法 (4) 2.2.1修正单纯形法 (4) 2.2.2Bland规则 (7) 第三部分程序主要内容 (9) 第四部分程序测试 (10) 备注 (17) 参考文献 (18)
第一部分功能概述 单纯形法是线性规划算法的一种。由于若线性规划问题有最优解，则一定存在一个基本可行解是最优解，因此单纯形法是通过沿着可行集的边界，从一个顶点转移到改善当前目标函数值的相邻定点，以此来寻找最优解。 程序编写了加入Bland规则的修正单纯形法，只需用户给定设计变量个数、约束条件个数、约束条件系数，委托矩阵操作类MatrixOperation进行矩阵运算，即可实现线性规划问题的优化。
第二部分 理论知识 线性规划问题具备以下性质： 定理1 若线性规划问题的可行域X 非空，则X 是一个凸集。 定理2 线性规划问题的每一个基本可行解x 都对应于可行域X 的一个顶点。 定理3 若线性规划问题有最优解，则一定存在一个基本可行解是最优解。 定理4 若线性规划问题有最优解，则目标函数的最优值一定可以再可行域 X 的某个顶点上达到。 2.1 线性规划标准型 定义1 如果目标函数是设计变量的线性函数，且约束条件也是关于设计变量的线性等式或线性不等式，则相应的数学问题就称为一个线性规划问题。 单纯形法计算问题的最优值需要将原问题统一为标准形式。定义线性规划问题的标准形式为： 定义2 给定线性规划问题的标准型为 ()()1 1min .. 1,2,,01,2,,n j j j n ij j i j j z c x s t a x b i m x j n ==? =?? ? ==?? ?≥=?? ∑∑ (1) 其中()01,2, ,i b i m ≥=。即对目标函数一律求最小值；设计变量均非负；约束 条件除非负约束条件之外一律为等式约束；约束条件的右端项一律非负。 定义3 如果约束条件中含有不等式1n ij j i j a x b =≤∑且0i b ≥，则可引入一个新 的变量i x '，称为松弛变量；如果约束条件中含有不等式1 n ij j i j a x b =≥∑且0i b ≥，则 可引入一个新的变量i x ''，称为剩余变量。
修正单纯形法求解约束优化问题 姓名王铎 学号 2007021271 班级机械078 日期 2010/6/23
一．问题分析 求解约束优化问题中，假如目标函数和约束条件都是线性的，像这类约束函数和目标函数都是线性函数的优化问题称作线性规划问题。从实际问题中建立数学模型一般有以下三个步骤： 1.根据影响所要达到目的的因素找到决策变量； 2.由决策变量和所在大道目的之间的函数关系确定目标函数； 3.有决策变量所受的限制条件确定决策变量所要满足的约束条 件； 求解线性规划问题的基本方法是单纯形法，而本文研究的是修正单纯形法。1965 年由J.A.Nelder 等提出。是在基本单纯形优化法的基础上，引入了反射、扩展与收缩等操作规则，变固定步长推移单纯形为可变步长推移单纯形，在保证优化精度的条件下，加快了优化速度。是各种单纯形优化法在分析测试中应用最广的一种。 二．数学模型 1、线性规划问题的formalization 问题(1.1)称为线性规划问题： x= arg min_x c^T x s.t. Ax=b x>=0 (1.1) 其中x为n维列向量，A为m*n的矩阵，b和c分别为m,n维的常数向量。 任意一个线性不等式组约束下求解线性函数的最大最小值问题
都可以归结到问题(1.1)来。 比如 A(i,:) x <= b(i) <=> A(i,:) x + y(i) = b(i) y(i)>=0 (1.2) A(i,:) x >= b(i) <=> A(i,:) x - y(i) = b(i) y(i)>=0 (1.3) x <=> x=x'-x" x'>=0 x">=0 (1.4) 2、单纯形法 设m
单纯形法求解线性规划的步骤
单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive(); //判断目标行是否全部为非负数,最后一列不作考虑 这个函数用来判断是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列是否全部为负数或零 这个函数用来判断线性规划是否是无解的 bool Is_column_all_Positive(int col); //判断col列中是否全部为正(不包括目标行)
班级：优化1班授课老师：庞丽萍姓名：学号： 第二章 12.（1）用修正单纯形法求解下列LP问题: >>clear >>A=[121100;123010;215001]; [m,n]=size(A); b=[10;15;20]; r=[-1-2-31]; c=[-1-2-31]; bs=[3:3]; nbs=[1:4]; a1=A(:,3); T=A(:,bs); a2=inv(T)*a1; b=inv(T)*b; A=[eye(m),a2]; B=eye(m); xb=B\b; cb=c(bs); cn=c(nbs); con=1; M=zeros(1); while con M=M+1; t=cb/B; r=c-t*A; if all(r>=0) x(bs)=xb; x(nbs)=0; fx=cb*xb; disp(['当前解是最优解，minz=',num2str(fx)]) disp('对应的最优解为,x=') disp(x) break end rnbs=r(nbs); kk=find(rnbs==min(rnbs)); k=kk(1); Anbs=A(:,nbs); yik=B\Anbs(:,k); xb=B\b;%yi0 if all(yik<=0)
disp('此LP问题无有限的最优解，计算结束',x) disp(xb) break else i=find(yik>0); w=abs(xb(i,1)./yik(i,1)); l=find(w==min(w)); rr=min(l); yrrk=yik(rr,1); Abs=A(:,bs); D=Anbs(:,k); Anbs(:,k)=Abs(:,rr); Abs(:,rr)=D; F=bs(rr); bs(rr)=nbs(k); nbs(k)=F; AA=[Anbs,Abs]; EE=eye(m); EE(:,rr)=-yik./yrrk; Errk=EE; Errk(rr,rr)=1/yrrk; BB=Errk/B; B=inv(BB); cb=c(:,bs); xb=Errk*xb; x(bs)=xb; x(nbs)=0; fx=cb*xb; end if M>=1000 disp('此问题无有限最优解') break end end %结果 当前解是最优解，minz=-15 对应的最优解为,x= 2.5000 2.5000 2.50000
《运筹学》课程标准 一、课程概述 运筹学是数学的一门分支学科，也是管理科学的一个分支学科。它是一门应用性、综合性强的科学。它是实现管理现代化的有力工具，在生产管理、工程技术、军事作战、科学试验、财政经济以及社会科学中得到广泛应用。 运筹学通过建立数学模型或模拟模型运用数学方法对于要求解的问题得到合理的决策。二、课程目标 1．知道《运筹学》这门学科的性质、地位和独立价值。知道这门学科的研究范围、应用领域、研究方法、学科进展和未来方向。 2．理解这门学科的主要概念、基本原理和基本方法。 3．初步学会运用一些具体的方法与技术，如单纯形法、对偶单纯形法、修正单纯形法等解决线性规划问题。 三、课程内容和教学要求 这门学科的知识与技能要求分为知道、理解、掌握、学会四个层次。这四个层次的一般涵义表述如下： 知道———是指对这门学科的内涵与外延的认知。 理解———是指对这门学科涉及到的概念、原理的说明和解释。 掌握———是指课程涉及的方法的理论根据、适应范围、所需条件等的理性认识。 学会———是指能运用该课程的基本原理、基本方法分析、处理和解决实际问题。 教学内容和要求表中的“√”号表示对知识和方法的教学要求层次。 本标准中打“*”号的内容可作为自学，教师可根据实际情况确定要求或不布置要求。（一）绪论
（二）线性规划 （三）修正单纯形法 （四）对偶单纯形法
（五）线性规划的特殊类型及目标规划 （六）整数规划
（七）动态规划 （八）非线性规划 （九）库存论 （十）排队论
四、课程实施 （一）课时安排与教学建议 ?运筹学?是数学与应用数学、信息与计算科学的专业限选课，共54课时，具体课时安排如下： （二）教学组织形式与教学方法要求 1、教学班是主要的教学组织，班级授课制是目前教学的主要组织形式。 2．注意教学方法的灵活性，组织学生自我讨论、分析、提出问题教学、阅读指导等。。 3．充分发挥学生的主动性，运用启发式教学，引导学生自我进行方法的发现与总结。 五、教材编写与选用 《运筹学》教材要在课程标准的统一要求下，实行多样化。可以选用普通高校重点教材。也可以选用21世纪教材。 六、课程评价 1．这门学科的评价依据是本课程标准规定的课程目标、教学内容和要求。该门课程采用平时考核（80%）、和集中考试（20%）相结合的形式进行。
单纯形法 可按现代电子计算机标准程序求解线性规划模型的一般方法。分为代数形式 的单纯形法和表格形式的单纯形法。前者提供基本算法所依据的逻辑规则，适用 于在电子计算机上进行求解运算；后者将变量和数据列成表格，适用于笔算。两 者在数学上是等价的。单纯形法是由美国数学家G.B.丹齐克（1914～）于1947 年提出来的，它与苏联数学家Л.Β.坎托罗维奇（1912～）于1938年提出的 解乘数法相类似。 根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2， (x) 的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大n 值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所 确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目 的就是要找出最优解。 可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解； ③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止 目标函数的值无限增大（或向负的方向无限增大）。 要缩小对最优解的搜索范围，就必须认识最优解的一般性质，最优解如果存 在的话，则它必然处于可行区域的边界上。 任何一项约束条件的边界方程是用“＝”号来替换该约束条件中的“≤”或 “≥”号而得到的。每一个边界方程确定一个超平面。因此，可行区域的边界是 由那些满足一个或同时满足几个边界方程（即处在作为边界的一个或几个超平面 上）的可行解所组成，而且最优解必在其中。最优解不仅是在可行区域的边界上， 而且也在这个区域的一个隅角上。一个可行解，如果不处在由另两个可行解连接 起来的任何线段上，它就是一个角点可行解。如果连接两个角点可行解的线段处 在可行区域的边界上，这两个角点可行解就称为相邻的角点可行解。角点可行解 具有下列三个重要性质：①如果存在着一个最优解，那么它必定是角点可行解。 如果存在有多个最优解，那么至少有两个最优解必定是相邻的角点可行解。②只 存在有限个数的角点可行解。③如果一个角点可行解按目标函数值来衡量时比其 所有的相邻角点可行解更好一些，那它就比所有其他角点可行解都更好，也就是 最优解。
单纯形法（不可以解空集问题，无初始解） 一、单纯形法的基本思想 1、顶点的逐步转移 即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。 2．需要解决的问题： (1)为了使目标函数逐步变优，怎麽转移？ (2)目标函数何时达到最优——判断标准是什么？ （3）初始解的寻找 二、单纯形法原理（用代数方法求解LP） 第一步：引入非负的松弛变量（x3 x4 x5）和剩余变量（算完后剩余的资源） x3,x4,x5, 将该LP化为标准型 第二步：寻求初始可行基（单位阵对应的），确定基变量 第三步：写出初始基本可行解（很多之中找一个，必令原x为0）和相应的目标函数值 两个关键的基本表达式： ① 用非基变量表示基变量的表达式 ② 用非基变量表示目标函数的表达式 第四步：分析两个基本表达式，看看目标函数是否可以改善？ ① 分析用非基变量表示目标函数的表达式 非基变量前面的系数均为正数（必为负数才可以），所以任何一个非基变量进基都能使Z值增加 通常把非基变量前面的系数叫“检验数” ②选哪一个非基变量进基？ 排在最前面的负检验数对应的非基变量 ③确定出基变量 “最小比值原则”（或θ原则）见本 如果x2≤0，会出现什麽问题？ 最小比值原则会失效！ 基变换 新的基变量——x2, x3,x4；新的非基变量x1, x5； 写出用非基变量表示基变量的表达式： 可得新的基本可行解 X（1）=（0,3,2,16,0）T ⑤写出用非基变量表示目标函数的表达式: 检验数仍有正的 第五步：上述过程何时停止？ 当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正（0时表无穷解，负时表唯一解）时，当前的基本可行解就是最优解! 为什麽？ 分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！
单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive();其中row2为主元所在的行,col为主元所在的列,row1为要处理的行 void PrintAnswer();数不合法"< 第4章 单纯形法的计算方法 单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代, 直到目标函数实现最大值或最小值为止。 4.1 初始基可行解的确定 为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z =n j j j=1c x ∑ 1,1,2,...,0,1,2,...n ij j i j j a x b i m x j n =?==???≥=?∑ 从Pj ( j = 1 , 2 , ? , n )中一般能直接观察到存在一个初始可行基 121(,,...,)n B P P P 0 0?? ?0 1 0 ?== ? ?0 0 1?? （2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对 j x 及ij a ( i = 1 , 2 , ? , m ; j = 1 , 2 , ? , n )进行编号, 则可得下列方 程组 11,1111 22,1122,1112.........,,...,0 m m n n m m n n m m m m nn n n n x a x a x b x a x a x b x a x a x b x x x +++++++++=?? +++=?? ??+++=??≥? 显然得到一个m ×m 单位矩阵 运筹学实验报告 题目：用单纯形法求解线性规划问题 姓名顾文远 学号2012436034 年级专业12数电类2班 指导教师苏珂 2013年11月14日 一．实验目的 (2) 二．实验环境 (3) 三．实验内容 (4) 1.线性问题 (4) 2.函数调用形式： (4) 3.参数介绍： (4) 5.实验原理及步骤： (5) 四．函数代码及注释： (12) 五．数据测试： (16) 六、实际问题求解 (19) 掌握两阶段法求线性规划问题的最优解，并完成 matlab求解单纯形算法求线性规划问题的最优可行解的程序。加深对单纯形算法的理解，掌握matlab 的使用技巧. Matlab 7.1 系统：microsoft windows XP Professional CPU:Inter（R）Core（TM）2 Duo CPU E7500 @ 2.93GHz 3.24GB的内存 1.线性问题 用matlab程序两阶段法解下面形式的方程组的最优解： min f=c T*x s.t. A*x=b x>0 2.函数调用形式： [x,minf,flag,cpt]=dcxsf(A,b,c) 3.参数介绍： A为约束条件的系数矩阵。 b为约束条件的常数列向量。 c为目标函数的系数行向量。 4.函数输出介绍： X：为线性规划的解向量，当函数有可行解并且有最优值时输出最优解；当有可行解但无最优值或没有可行解时输出x[]。 minf：为目标函数的最优值，当函数有可行解并且有最优值时输出最优值； 当有可行解但没有最优值时minf=-inf，输出-1/0；当没有可行解 时输出minf=[]。 flag：为记录函数解的情况，当函数有可行解并且有最优值时，flag=1； 当函数有可行解但没有最优值时，flag=0；当函数没有可行解时， flag=-1. cpt：为单纯形表，当函数有可行解并且有最优值时输出最优解对应的单纯形 单纯形法的解题步骤 三、单纯形法的解题步骤 第一步：作单纯形表. （1）（1）把原线性规划问题化为标准形式； （2）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； （3）（3）目标函数非基化； （4）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即 ，则此时线性规划问题已取得最优解. (2) 若存在某个检验数是正数，即，而 所对应的列向量无正分量，则线性规划问题无最 优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. （1）找到最大正检验数，设为，并确定 （2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）. 表 6.8 x1 x2x3x4x5常数 x 3 x 4 x 51 0 1 0 0 1 2 0 1 0 0 （1）0 0 1 5 10 4 S′ 1 3 0 0 0 0 x 3 x 4 x2 1 0 1 0 0 （1）0 0 1 -2 0 1 0 0 1 5 2 4 S′ 1 0 0 0 -3 -12 x 3 x 1 x 20 0 1 -1 2 1 0 0 1 -2 0 1 0 0 1 3 2 4 S′0 0 0 -1 -1 -14 （3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 function [zyj,zyz,k]=ssssimplex(A,N) %A为初始单纯型表和书上的形式一样[m,n]=size(A); % 分别代表A的行数和列数%N为基本可行解的下标 k=0; %迭代次数%zyj为最优解 %zyz为最优值 flag=1; %定义一个逻辑变量 while flag k=k+1; if A(1,:)>=0 %已找到最优解 flag=0; zyj=zeros(1,n-1);%给每个变量赋初值0 for i=2:m zyj(N(i-1))=A(i,n);%给基变量赋新值 end zyz=-A(1,n);%给出最优解 else %判断问题是否不可解 for i=1:n-1 if A(1,i)<0&A(2:m,i)<=0 %问题不可解 disp('there is no answer'); flag=0; break; end end if flag %还不是最优表，进行转轴运算 temp=0; for i=1:n-1 if A(1,i)单纯形法的计算方法
单纯形法
单纯形法的解题步骤
单纯形法
相关主题
文本预览