最优化方法教案(1)

1、第一章最优化问题与数学预备知识最优化分支：线性规划，整数规划，几何规划，非线性规划，动 态规划。又称规划论。应用最优化方法解决问题时一般有以下几个特点：1. 实用性强2. 采用定量分析的科学手段3计算量大，必须借助于计算机4.理论涉及面广应用领域：工业，农业，交通运输，能源开发，经济方案，企业 管理，军事作战。§ 1.1最优化问题实例最优化问题：追求最优目标的数学问题。经典最优化理论：(1)无约束极值问题：opt f(Xi，X2， ,Xn)(min f(xX2， ,Xn)或 max f (xx?, , x.)其中，f (Xi，X2/ ,xn)是定义在n维空间上的可微函数。解法(求极值

2、点)：求驻点，即满足fx! (Xi, ,Xn) = 0fx2 (Xi, ,Xn) = 0fx： (Xi，Xn) = 0并验证这些驻点是否极值点。(2)约束极值问题：Opt f(Xi，X2， 凡)s.t.hj(Xi，X2，,Xn) = 0, j = 1,2,1(1 n)解法：采用Lagrange乘子法，即将问题转化为求 Lagrange函数L(X1,X2,Xn； 1,l,l) = f (X1,X2,Xn)、j=1jhj(X,Xn)的无约束极值问题近代最优化理论的实例：例1 (生产方案问题)设某工厂有3种资源B1，B2，Bs，数量各 为b1, b2, bs,要生产10种产品A1，A10。每生产一个

3、单位的Aj需要消耗Bi的量为aj，根据合同规定，产品Aj的量不少于dj，再 设Aj的单价为q。问如何安排生产方案，才能既完成合同，又使总收入最多？线性规划问题数学模型：设Aj的方案产量为Xj , z为总收入10目标函数：maxz = 7 CjXj j丄J- 10|瓦 aw 兰 bj = 1,2,3约束条件：'PXj 色 dj, j =1,2，,10线性规划问题通常采用单纯形法来求解。例2 工厂设址问题要在m个不同地点方案修建 m个规模不完 全相同的工厂，他们的生产能力分别是 aa2，am 为简便起见， 假设生产同一种产品，第i个工厂的建设费用fj =1,2，m。又 有n个零售商店销售这

4、种产品，对这种产品的需求量分别为 bb2，0，从第i个工厂运送一个单位产品到第j个零售商店的运 费为q。试决定应修建哪个工厂，使得既满足零售商店的需求，又使 建设工厂和运输的总费用最小。混合整数规划问题数学模型： 设第i个工厂运往第j个零售商店的产品数量为Xj i=1，m; j=1，n,且0,如果修建第i个工厂否那么mn目标函数：mi nz = Wf y + 送 c xi y iij ij<j二丿' Xij 岂 4%, i = 1, ,m2m苫 Xj > bj, j = 1,n约束条件：iy 0 或 1, i = 1, ,mXj 一 0, i = 1,m; j = 1, ,

5、n整数规划问题通常可用分枝定界法或割平面法来求解。例3 投资方案问题假设某一个生产部门在一段时间内可用于投资的总金额为a亿元，可供选择的工程总共有n个，分别记为1, 2,n。并且对第j个工程的投资总数为aj亿元，而收益额总数 为Cj亿元。问如何使用资金a亿元，才能使单位投资获得的收益最大。非线性规划问题11,对第j个工程投资数学模型：设Xj =0 否那么，“1,，nn7 CjXj_ p目标函数：maxz-迟 ajXjjm；nI瓦ajXj兰a约束条件：冃、Xj = 0 或 1, j = 1,n非线性规划问题的求解方法很多，是本课的重点。动态规划是解决“多阶段决策过程的最优化问题的一种方法，基于“

6、Bellman最优性原理，例如：资源分配问题，生产与存储问题例4 (多参数曲线拟合问题)热敏电阻R依赖于温度T的函数关系为X2R= x1eT x3 *其中，Xi,x2,X3是待定的参数，通过实验测得 T和R的15组数据列表如下，如何确定参数Xi,X2,X3 ？i12345678T/c5055606570758085R/也34.7828.6123.6519.6316.3713.7211.549.744i9101112131415T/c9095100105110115120R/Q8.2617.036.0055.1474.4273.823.307建立数学模型：测量点(Ti,Ri)与曲线R(T)对应的

7、点产生“偏差即15二S 八Rj -x£ X32i H得如下无约束最优化问题：15minf(x) = ：T RX,eT4X32通常采用最小二乘法。§ 1.2最优化问题的数学模型一、最优化问题的数学模型1.定义1：设向量，二包厂，amT,，»b2,，bmT.假设 aj 岂 bi i = 1,2,m，那么记或一：一；假设 a bj (i = 1,2，m)，那么记 < P 或 P a 。2.一般模型：opt f (x) = f (xx2，xn) (minf (x)或 maxf (x),(1)；Si(x)x 0, i =1,m(2)s.t. hj(x) = 0, j

8、=1,l其中，x = X1, X2，xnT ； f(x) , Si(x) , hj(x)是关于变量X1 , X2，,xn的实值连续函数， 般可假定它们具有一阶连续偏导数。3.向量模型：opt f (x) (minf(x) 或 maxf (x),(1)S(x) z 0, i = 1,m(2)s t“MX) = 0, j =1,l(3)其中，X =X1,X2，XnT , f x称为目标函数；Si x， hj x称为约束函数；满足约束条件2， 3的点称为容许解或容许点或可行解； 容许解的全体称为容许域或可行域，记为R；满足1的容许点称为最优点或最优解或极小大点，记 为x* ； f x 称为最优值；不

9、带约束的问题称为无约束问题，带约束的问题称为约束问题;假设目标函数f(x)，约束函数Si(x) , hj(x)都是线性函数，那么 称为线性规划；假设其中存在非线性函数，那么称为非线性规划；假设变量只取整数，称为整数规划；假设变量只取0， 1，称为0 1规划。注：因h(x) = 0 = h(x) 一 0，-h(x) 一 0，那么最优化问题一般可 写成"opt f (x)s.t. S(x) 0'一维问题 .n维问题'线性规划 非线性规划最优化问题的分类无约束问题最优化问题I静态规划'约束问题动态规划§ 1.3二维问题的图解法例 1. max z = 2x

10、3x2x1 2x2 岂 8s.t.4% - 16j Xi,X2 乏 0解：1.由全部约束条件作图，求出可行域 R:凸多边形OABC2. 作出一条目标函数的等值线：设 2x1 3x 6，作该直线即为一条目标函数的等值线，并确定在可行域内，这条等值线向哪个方 向平移可使z值增大。3. 平移目标函数等值线，做图求解最优点，再算出最优值。顶 点B4,2是最优点，即最优解X4 2t，最优值z =14。分析：线性规划问题解的几种情况1有唯一最优解上例；2有无穷多组最优解：目标函数改为 max z = 2x4x23无可行解：增加约束X2 -5，那么R八-。4无有限最优解无界解：例maxz二x< 化x-

11、 2x2 兰 4s.t.- x x2 乞 2.Xi,X2 A 0结论：1线性规划问题的可行域为凸集，特殊情况下为无界域 或空集。2线性规划问题假设有最优解，一定可在其可行域的顶点上 得到。例 2.min(石 -2)2 (x2 -1)2Xi x；-5X2 = 0s.t.% x2 - 5 - 0x1, x20解：目标函数等值线：(Xi-2)2 + (X2-1)2 = 1C为最优点x； - 5x2 = 0x2 - 5 = 0，得 x 二4iT定义2：在三维及三维以上的空间中，使目标函数取同一常数的点集x f x二r, r是常数，称为等值面§ 1.4预备知识一线性代数一、n维向量空间Rn1.

12、 向量的内积：设x二石毛，XnT, y二y丫2,，ynT，那么 内积为nxTy = X1 X22Xnyn 八 Xi yiim2. 向量的范数或长度或模：设Rn，假设实数x具有以下 性质：1|仪|亠0,当且仅当x = 0时| XI = 0 ；2卜x| = « NX，曽?丘 R ；3Ix+ y| 兰 |X| +|y|,wx,疔 Rn. 那么称|x|为Rn上的向量的范数，简记为|。规定了向量范数的线性空间Rn称为线性赋范空间，记为R n.3. 常见的向量范数丄f n向量的Lp范数：|x|p =?xi|，1兰p < 00V i =1丿三个重要的向量范数：|x|L, |x|2，I xL注

13、：假设无特殊说明，本书中的11指的是| XI2。4. x,y间的距离：x-y5. x与 y 正交：xTy = 0假设非零向量组x，xk的向量两两正交，称它们是正交向量组6.标准正交基：e，en是n个正交的单位向量，即 肌“1, IQ i * j二、特征值和特征向量定义：设A为n阶方阵，存在数-和非零向量x，使Ax = x，那么称 为矩阵A的特征值，非零向量x为矩阵A属于特征值 的特 征向量。三、正定矩阵定义：设A为n阶实对称方阵，假设对任意非零向量x，均有xT Ax 0，那么称xtAx为正定二次型，A为正定矩阵，记A 0。； 假设xT Ax 一 0，半正定二次型，A为半正定矩阵，记A - 0。

14、类似有负定半负定二次型，负定半负定矩阵的概念。性质：实对称方阵A为正定矩阵负=A的特征值均为正负=A的各阶顺序主子式均为正奇数阶为负，偶数阶为正实对称方阵A为半正定矩阵=A的特征值均非负=A的各阶顺序主子式均为非负(二) 数学分析梯度和海色(Hess©矩阵1.多元函数的可微性可微定义：设f ： D R" > R1 , x D，假设存在n维向 量I，对- p-0 Rn，总有f(X。 p)- f(X°)-|TpH(i)那么称函数f (x)在点Xo处可微。式(1)等价于f(Xo+ p) - f(Xo) = ITp+Oqp|)(2)其中，0(| p|)是I p|的高

15、阶无穷小。定理1：(可微的必要条件)假设函数f (X)在点Xo处可微，那么f (X) 在该点关于各个变量的偏导数存在，且Jf(X。)苛(X。)f (Xo) |T1 一 I ,-CX1CX2CXn 一2.梯度(1) 概念梯度：令'*77r-% 似2°Xn 一那么称灯f (X)为n元函数f(x)在X处的梯度(或记为gradf(x)。又称为f(x)关于x的一阶导数。注：式(2)等价于f(X。+ p) = f(X。)+ 灯 f (x°)T p + 0(| p| )(3)等值面：在三维和三维以上的空间中，使目标函数取同一数值的点集xf(x) = r,rw R称为等值面(曲面)

16、。方向导数：设f：R" > R1在点X。处可微，向量Rn，e 是p方向上的单位向量，那么极限lim fx。te - f x。t；。：p 。方向导数的几何解释：方向导数f(X0)表示函数f(x)在点X。处称为函数f(x)在点Xo处沿p方向的方向导数，记作'"x。)沿方向的p的变化率。函数的下降(上升)方向：设f :R1是连续函数，点X。 Rn， p = 0 Rn为一方向，假设存在0，对于一 t (Or )，都有f (Xo tp) f(X。)( f(Xo tp) f (Xo)那么称p方向是函数f (x)在点Xo处的下降(上升)方向；Wf(X。)-结论1：假设方向导

17、数丁 ：。，那么方向p是f(X)在点Xo处的cp讨(X。) c下降方向；假设方向导数 丁 。，那么方向p是f (X)在点Xo处的上cp升方向；2性质【性质1】：梯度可fX°为等值面fx= fx°在点X。处的切平面的法矢向量。【性质2】：梯度方向是函数具有最大变化率的方向。定理2：设f :Rn > R1在点X。处可微，那么方向导数八 fx°Te、fx° cost其中，e是p方向上的单位向量，二为梯度与p的夹角。结论2： 1 与梯度' fX。方向成锐角的方向是上升方向；与梯 度' fX。方向成钝角的方向是下降方向；2梯度方向是函数值上升

18、最快的方向，称为最速上升方向；负 梯度方向是函数值下降最快的方向，称为最速下降方向。3几种特殊函数的梯度公式1C = 0，C为常数；2bTx二b，其中b=虬鸟,，bn卩；3' xTx = 2x ；4假设Q是对称方阵，那么'xTQx二2Qx.例3.泰勒Taylor公式与Hesse矩阵性质1：设fx:Rn > R具有一阶连续偏导数，那么fx P二 fX ' f T p*其中，二x rp 0 八：1，即介于X与x p之间。性质2：设fx:Rn > R具有二阶连续偏导数，那么(* )f (x p)二 f (x) v f (x)T p 1 pU 2f ( )p2其中：

19、2f(x)1：2f(x)：2f(x)"2Xixr x2XiXn：2f (x)1：2f(x)：2f(x)1 x2 x1：X；* +X %：2f(x)：2f(x)：2f(x)_XjXiXnX2?Xn' 2 f (x)=为函数f x关于x的二阶导数，称为f x的海色HessH矩阵。结论1：当fx C2时,沁宀j1, ,n (即Xj；XjXjXj海色矩阵对称。注1：1设向量函数gx称为向量函数gx在点x处的导数梯度=gi(x),g2(x), ,gm(x)T 时,CXi云XiH1cXi|勺i(x) (x)gm(x)|牛%9*牛1勺i(x)勺2XWgm(x)臥Jg2xOg(x)gm(x)

20、'g(x)=2向量函数gx二9X, g2x,gmxT在点x°处可微是指所有分量都在点x0处可微。关于向量函数常见的梯度：(1) C = On, c Rn ；(2) (x)二 In , X Rn ；(3) (Ax) = At, a Rmn(4) 设(t)二 f (Xo tp)，其中 f :R1，: R R1 ,那么(t)八 f(X° tp)Tp ,二2f(Xo tp)p例:(三) 极小点的判定条件(求 min f(x)、 根本概念1点 X。的邻域：N(x。,)X x- X。， 0?2. 局部极小点：设f ：D Rn，R1.假设存在点x - D和数0，对-x N (x*

21、厂 D 都有 f (x) 一 f (x*)，那么称 x* 为 f (x) 在D上的(非严格)局部极小点；假设f(x)> f (x*)( xx*),那么称 x*为f(x)在D上的严格局部极小点。3. 全局极小点：设f : D Rn、R1.假设存在点x D，对于 - x D都有f (x) 一 f (x*)，那么称x*为f (x)在D上的(非严格) 全局极小点；假设f (x) a f (x*) ( x式x*)，那么称x*为f (x)在D上的 严格全局极小点。性质：全局极小点必是局部极小点；但局部极小点不一定是全局 极小点。类似有极大点的概念。因max f (x)二min- f (x)，本书主要

22、给 出极小问题。4. 驻点：设 f : D Rn > R1 可微，X： D，假设'f (x*) = 0， 那么称点x*为f(x)的驻点或临界点。二、极值的条件定理1 (一阶必要条件)设f ： D R R1具有一阶连续偏导 数，x*是D的内点，假设x*是f(x)的局部极小点，那么'、f (x*)二 0定理2(二阶必要条件)设f：D R R1具有二阶连续偏导 数，假设X是D的内点且为f x的局部极小点，贝X 2 fX 是半正定 的，即对一 p Rn恒有ph 2fx*p 一 0例定理3二阶充分条件设f : DR1具有二阶连续偏导数，* * a*x为D的内点，且' f x

23、 = 0，假设f x 正定，那么x为f x的 严格局部极小点。四凸函数与凸规划一、凸集1. 凸集的定义：一个n维向量空间的点集D中任意两点的连线 仍属于这个集合，即对一人公2，D，有：为1 - ： x2 D 0 - ： - 1那么称该点集D为凸集。2. 凸集的性质：1凸集的交集仍是凸集Die D2；2 数乘凸集仍是凸集= yy= ®x, D；3 凸集的和集仍是凸集D1 + D2=yy=x+ z,D? 特别规定，空集是凸集。3. 超平面：设。e Rn且式0,沪R，贝卩集合H = x|o Tx = b, x壬Rn称为Rn中的超平面，Q称为该超平面 的法向量，即H : a/ 72X2a.X

24、n二b ；是凸集半空间：集合 Tx启b,Rn称为Rn中的一个半空间。超球：x空r。4. 凸组合：设xX2，必为Rn中的|个点，假设存在aa2厂，qi且0乞q乞1,ai =1，使得idx = a1x1 a2x2- alxl那么称x为Xi，X2， ,X|的凸组合。假设aa2厂，a|均为正，那么称为严格凸组合。5. 顶点(或极点)：设D是凸集，D，假设x不能用D内不同 两点x1和x2的凸组合表示，即x » x1 (V : )x2 (0 1)，那么称 x为D的顶点。二、凸函数1.凸函数：设f : D Rn、R1， D是凸集，假设对- Xi* D 及-:0, 1，都有f (:咅(1 - ： )

25、x2) - ： f (xj (1 - ：)f (x2)那么称f (X)为凸集D上的凸函数；假设f (：为(1 - ： )x2) ： ： f (xj (1 - ：)f (x2) (01)那么称f(x)为凸集D上的严格凸函数。类似有凹函数的定义。2几何意义：函数图形上连接任意两点的线段处处都在函数图形 的上方。3性质性质1： f (x)为凸集D上的凸函数，k-0，那么kf (x)也为D上 的凸函数。性质2：两个凸函数的和仍是凸函数。(fi(x) f2(x)推论1 ：凸集D上有限个凸函数fi(x)的非负线性组合kj(X)kmfm(X), % 一 0仍为D上的凸函数。性质3：假设f(x)为凸集D上的凸

26、函数，那么对 R，f(x)的 水平集D二xf(x)，xD是凸集。性质4： f(x)为凸集D上的凹函数=-f(x)为凸集D上的凸 函数。4. 凸函数的充分必要条件定理1 (一阶条件)设f ：D Rn > R1可微，D是凸集，贝S(1) f (x)为凸函数u对一人公2，D，恒有f(X2)- f(xj ' f (xJT(X2-xJ(2) f (x)为严格凸函数u对 xi, x D , Xi= X2恒有f(X2)f (Xi) ' f (Xi)T(X2-Xi)定理2 (二阶条件)设f : D Rn > R1具有二阶连续偏导数， D为开凸集，那么(1) f (x)在D内为凸函数

27、=对-x D , ' 2f (x)是半正定的；(2) 假设' 2f (x)正定，那么f (x)在D内为严格凸函数。1特殊地，n元二次函数为f (x)二;2 xTQx bTx C ( Q为对称 矩阵)；假设Q正定，那么f(x)称为正定二次函数。性质：正定二次函数是严格凸函数。(因为I 2 f(X)二Q )5. 凸函数的极值定理3设f : D R R1为凸集D上的凸函数，贝S(1) f (x)的任一局部极小点x*为全局极小点；(2) 假设f(x)具有二阶连续偏导数，且存在x* D，使' f (x ) = 0，那么x为f (x)在D上的全局极小点；(3) 假设f(x)为严格凸

28、函数，且全局极小点存在，那么必唯一。特殊：对于正定二次函数f (x)二Qx x C，有' f (x)二Qx b，得唯一驻点X*二-Q_1b为唯一的全局极小点。6. 凸规划问题：非空凸集D上的凸函数的极小化问题。考虑凸规划问题：minf(x) , Rn(1)Si (x) - 0, i = 1, msthj (x) 7, j =1,1其中，S (x)为Rn上的凹函数，hj (x)为Rn上的线性函数, D =xSj(x)兰 0, hj(x) = 0,i =1,，m;j=1,，1为凸集， f : D Rn > R1为D上的凸函数。注：线性函数既可视为凸函数，又可视为凹函数。1二次规划:m

29、inf (x)xTQx bTx Cps.t. Cx 二 d其中，x Rn , Am n , Cl n, Q半正定或正定(五) 下降迭代算法1. 下降迭代算法的步骤(1) 选择一个初始点X。，令k： =0(2) 检验xk是否最优？假设是，那么停止迭代；假设不是，那么(3) 确定一个下降方向Pk :存在0，对- t (0厂)，使得f Xk tPkf Xk(4) 从点xk出发，沿方向Pk进行直线搜索(一维搜索)，即求 步长tk使f Xk tk Pk - min f Xk tPk(5) 计算 XkXk tk Pk，令 k： =k+1，转(2)2. 直线搜索及其性质(1) 简记Z 二 ls(x, p)f

30、 x t0 p = min f x tPz 二 x t。p表示从点X出发，沿方向P进行直线搜索，得到极小点z。(2) 定理：设目标函数f(x)具有一阶连续偏导数，假设Z 二 ls(x, P)，贝S' f(z)T p = 0证明：(反正法)设f (Z) Tp = 0，贝y1) ' f (z)T p 0，此时- p是点z的下降方向；2) ' f (z)T p “ 0，此时P是点z的下降方向；与 z = ls(x, p)矛盾。3收敛速度定义1 :设序列3讣是线性赋范空间Rn,|中的点列，X： Rn，假设回& - x卜0那么称序列Xk收敛于X*，记为pm Xk二X*。定

31、义 2 :设向量函数 f(x)二fi(x), f2(x), fm(x)卩，x，D Rn，假设当 x-x° ，0 时，总有 f(x)- f(x°) > 0，那么称 f (x)在点Xo连续；假设f (x)在D内每一点都连续，那么称f (X)在D内 连续。特别地，m=1时，f(x)为数量函数，那么|f(x) - f(Xo)|=|f(X)- f(Xo)定义3：设序列 Xk收敛于x*，假设存在与K无关的数C 1)和 :e 0)，使得当K从某个KoC 0)开始，都有& 1 一 X* £ : Xk - x* ：那么称序列Xk收敛的阶为，或Xk为阶收敛。当:=1，且

32、0舟11时，称线性收敛或一阶收敛；当-2时，称二阶收敛；当12时，称超线性收敛。4.计算终止准那么计算终止准那么根据相继两次迭代的结果a. 根据相继两次迭代的绝对误差(不常用)Xk 1Xkf (Xk 1)- f (Xk)2b. 根据相继两次迭代的相对误差f (Xk+1)-f (Xk)阅+13，f (Xk)+ 1c. 根据目标函数梯度的模足够小IFfXk|；1, 2 ；3, ；4, ；5为给定的足够小的正数。以上准那么统称为Himmelblau计算终止准那么，简称H终止准那么第二章线性规划§ 2.1数学模型一、线性规划的标准型1. 繁写形式：min z 二 c1x1 c2x2cn xn

33、s.t.a11x1 a12x2 a?i X + a?2 X2 +am1 X1am2 X2amXn 二 bi a2nXn 二 b2amnXn - bmXi*, Xn - 0其中，0 -0, i =1,2, ,m 否那么，等式两端同乘以“ -1 。n2. 缩写形式：min Z八CjXjjm；najX厂 bj 二 1,2, ,ms.t.冃N 启 0 , j = 1,2,，n3. 向量形式：min z二CTXn/ PjXj =bs.t.冃0其中，C =C1,C2/,CnT，X =X1,X2,XnT，"0,鸟,"，Pj _ a1 j , a2j ,4.矩阵形式：minz二CTXAX

34、= bs.t.X 工 0其中，_aii 兀九11 . 1I a2ia22a2n I rA=一： :打Pi, P2,Pn1 1.am1am2amnA :约束条件的m n系数矩阵，m 0 , n 0，一般地，m ： n ； b :限定向量，一般地，0 - 0, i,2, m ;C :价值向量；X :决策向量，X - 0 ；通常A，b，C为，X未知。二、任一模型化为标准型1. 极大化目标函数：max z= CTX令z-z，那么问题转化为min z二-CTX2. 约束条件为不等式假设约束为“空型，那么“左端+松弛变量二右端松弛变量- 0如：aiiXi - a：2X2a.岂b，引入松弛变量x.* - 0

35、，化为a 2X2ainXn Xn 厂 b假设约束为“ -型，那么“左端-剩余变量二右端剩余变量0如：aiiXi'ai2Xa.-bj，引入剩余变量x.*- 0，化为aMi 02X2 - aMn - Xn ibi3. 假设存在无非负要求的变量xk 称为自由变量令Xk = Xk - Xk，其中Xk - 0 , Xk - 0，代入目标函数及约束条件即可。4. 某变量Xj有上、下界假设 Xj - Uj，即 Xj - Uj _ 0，令 x厂 Xj _ u，有 Xj 一 0。用 Xj Uj 代替Xj即可。假设 x tj，即 tj - Xj - 0，令 Xj = tj - Xj，有 Xj - 0。用

36、t- Xj 代替Xj即可。例：§ 22线性规划解的性质、根本概念标准型(LP):minz = CTX (1)A = b 2stX>0 3可行解容许解：满足约束2、3的解。最优解：满足1的容许解。基：设Am n的秩为m，假设B是A中的m m阶可逆矩阵，称B是线性规划问题LP的一个基。基向量：基B中的一列Pi即为一个基向量。共m个非基向量：基B之外的一列Pj即为一个非基向量。共n-m个基变量：与基向量Pi相应的变量K。共m个非基变量：与非基向量 Pj相应的变量Xj。共n-m个根本解：令所有非基变量为0,求出的满足约束2的解。根本容许解：满足约束3的根本解。最优根本容许解：满足约束1

37、的根本容许解。退化的根本解：假设根本解中有基变量为 0的根本解。退化的根本容许解：退化的最优根本容许解：、线性规划问题的根本定理定理 1 假设线性规划问题存在容许域，那么其容许域是凸集。定理 2 线性规划问题的根本容许解对应于容许域的顶点。定理 3 假设线性规划问题存在有限最优解，那么其目标函数最优值 一定可以在容许域的顶点到达。§ 2.3单纯形法一、单纯形法原理单纯形法的根本思路：根据问题的标准型，沉着许域的一个根本 容许解一个顶点开始，转移到另一个根本容许解顶点 ，并且 使目标函数值逐步下降；当目标函数到达最小值时，问题就得到了最 优解。二、单纯形法的步骤以“大 M法为例数学描述

38、例大 M 法：min z = 4x+ 3x? + 8X3Xi X3 - 2s.t.- x2 2x3 - 5Xj HO (j= 1,2,3)1. 构造初始容许基初始容许基是一个m m单位矩阵，它相应的根本解是容许的。1o引入附加变量，把数学模型化为标准型。2o假设约束条件中附加变量系数为“ -1，或原约束即为等式，那么 一般须引入人工变量。3o目标函数中，附加变量系数为 0,而人工变量系数为 M 很 大的正数。人工变量系数为大M :只要人工变量0,使前后约束条件不等 价，但由于目标函数的修改，同时也使所求的目标函数最小值是一个 很大的数，也是对“篡改约束条件的一种惩罚，因此， M叫做罚因子，大M

39、法也叫做罚函数法。假设对极大化问题，目标函数中人工变量系数为(-M) 得到如下标准型：nmin z=CjXjj=iX1ai ,m 1 Xm 1ainXn - bis.t.X2 + a2,mXm岀 + + a?.%.= b2Xm am,m 1Xm 1amnXn _ bmXj -0 (j 72,n)其中，Xj(i=1,2,i,m)表示基变量；Xj(j = mT厂，n)表示非基变 量。2. 求出一个根本容许解1o用非基变量表示基变量和目标函数。用非基变量表示基变量，即有nXi 二 b - ' aijXj (i 二 1,m)j =m 1用非基变量表示目标函数，即nmnZ 八 CkXk = 7 CjXi .' CjXjk=1i =1j=m 1mnm=?Cibi + W (Cj _ W ci aij )Xji =1j 1i=1nn=Z° 、(Cj _ Zj)Xj = Z° vjXjj=m*j=m 北其中，zo八.ch ,而二5 - Zj称为非基变量Xj的检验数。上式i丄中，规定各基变量的检验数为 0。mZj = 'ciaij 二 ciai jc2a2jcmamji丄aij ,cm二g, ,cjPj假设干次迭代=g，cBm Pj 二 CB pj其中，Cb是基变量的价值系数，随基的