运用单纯形表求解线性规划问题难点课件

教学要求1).了解一般线性规划问题的数学模型。2)．掌握图解法。3)．理解单纯形法原理。4)．掌握单纯形法的计算步骤。5)．对单纯形法的进一步讨论。6)．了解单纯形法的矩阵描述。教学重点与难点重点:1、单纯形方法中初始可行基的确定方法、基可行解的转换和最优性检验；2、运用单纯形表求解线性规划问题。难点:最优性检验、基的变换。第1章线性规划教学要求第1章线性规划11、线性规划问题的数学建模2、LP的数学模型及准型化

3、线性规划解的概念----基,基解,基可行解,…

4、线性规划的图解法5、单纯形法原理(1)线性规划问题的可行解集(即可行域)是凸集.(2)(线性规划几何理论基本定理)若X是一可行解,则X是C的一个顶点的充分必要条件是X为线性规划的基本可行解.(3)若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值.(即LP有最优解,一定存在一个基可行解是最优解)(4)若目标函数在k个点处达到最优值(k≥2),世隔绝则在这些点的任意凸组合上也达到最优值.第1章线性规划1、线性规划问题的数学建模第1章线性规划26、单纯形法①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数

j=Cj-CBPj，若所有

j≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个

k所对应的系数列向量Pk≤0,则此问题是无界解，停止计算，否则转入下步。⑤根据max{

j｜

j＞0}=

k原则，确定xk为换入变量(进基变量)，再按

规则计算：

=min{bi/aik|aik＞0}=bl/aik确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第③步。

第1章线性规划6、单纯形法第1章线性规划37、LP解在单纯形中的讨论LP无解的条件;LP有无界解的条件;LP有无穷解的条件;LP有惟一解的条件;LP有退化解的条件.第1章线性规划7、LP解在单纯形中的讨论第1章线性规划48、单纯形中确定最优基及其逆的方法在初始单纯形表中,与最终表里的单位阵对应的矩阵即为最优基B*;在最终表中,与初始单纯形表里的单位阵对应的矩阵即为最优基的逆(B*)-1.第1章线性规划8、单纯形中确定最优基及其逆的方法第1章线性规划5第2章对偶理论教学要求1)．理解原问题与对偶问题。会写对偶问题。2)．了解对偶问题的基本性质。3)．掌握对偶单纯形法。4)．掌握灵敏度分析。5)．了解影子价格。解释经济意义。教学重点与难点重点:线性规划的对偶理论和基本性质；对偶单纯形法的计算方法；灵敏度分析。难点:对偶理论及基本性质；对偶单纯形法；灵敏度分析第2章对偶理论教学要求61、对称形式的对偶关系第2章对偶理论（D）（L）

上、下”交换，“左、右”换位，不等式变号，“极大”变“极小一般形式的对偶问题按照原始-对偶表直接写出1、对称形式的对偶关系第2章对偶理论（D）（L）上、下72、对偶问题的基本性质（对偶定理）对称性定理——对偶问题的对偶是原问题。弱对偶定理——若一对对称形式的对偶线性规划

注:由该定理可以得到关于“界”的结果无界性定理最优性准则定理强对偶定理若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。互补松弛性定理

第2章对偶理论2、对偶问题的基本性质（对偶定理）第2章对偶理论83、对偶单纯形法对偶单纯形法思想在保持原始可行的前提下（b列保≥0）通过逐步迭代实现对偶可行（检验数行≤0）对偶单纯形法步骤第2章对偶理论3、对偶单纯形法第2章对偶理论9第2章对偶理论否初始正则解(对偶可行)检查可行是则停止得最优解选出基变量检查是否无可行解是则停止否无最优解选入基变量进行旋转变换第2章对偶理论否初始正则解(对偶可行)检查可行是则停止得104、灵敏度分析价值系数C发生变化的情况右端常数b发生变化系数阵A的元素发生变化

(1)增加1个新变量;(2)增加1个约束条件.第2章对偶理论4、灵敏度分析第2章对偶理论11第3章运输问题教学要求1)理解运输问题的典例和数学模型。2)掌握表上作业法。3)掌握产销不平衡的运输问题及其处理方法。教学重点与难点重点:运输问题的表上作业法；产销不平衡问题的转化。难点:表上作业法；产销不平衡问题的求解方法。第3章运输问题教学要求12运输问题的三种类型产销平衡第3章运输问题运输问题的三种类型第3章运输问题13表上作业法求解步骤：找出初始方案（初始基可行解）：在m

n维产销平衡表上给出m+n-1个数字。

最优性检验：计算各非基变量的检验数，当

ij0最优。方案调整与改进：确定进基变量和离基变量，找出新的基可行解。第3章运输问题表上作业法求解步骤：第3章运输问题14确定初始方案(1)最小元素法“就近运给”，从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量min{ai,bj}。(2)最大差额法(Vogel法)不能按最小运费就近供应，就考虑次小运费。各行(各列)的最小运费与次小运费之差称为行差(列差)。差额越大，说明不能按最小运费调运时，运费增加最多。对最大差额处就采用最小运费调运。第3章运输问题确定初始方案第3章运输问题15最优性检验判别方法是计算非基变量的检验数：

ij=cij–CBPij’=cij–CBB-1Pij运输问题的目标函数要求为最小，即当

ij0视为最优。位势法计算检验数

ij=cij–CBPij’=cij–CBB-1Pij

ij=cij–(ui+vj)ui代表产地Ai的位势量，vj代表销地Bj的位势量。基变量的检验数为0，即

ij=cij–ui–vj=0，并令u1=0，计算各行各列的位势量。第3章运输问题最优性检验第3章运输问题16方案改进（闭回路调整法）(1)确定进基变量检查非基变量xij的检验数

ij，按min{

ij|

ij<0}=

lk确定xlk进基。(2)确定离基变量非基变量xlk进基之后，要求它的运量增加量按照它所在行和列的运量保持产销平衡。保持产销平衡的方法是闭回路法。闭回路法：以进基变量xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。闭回路的画法：从进基变量xlk所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90º，继续前进，直到返回始点。奇偶点：始点是偶点，依次奇偶相间标注；偶点标“+”，表示运量增加量；奇点标“-”，表示运量减少量。调整量：最大可调整的运量，为奇点运量的最小值。奇点运量的最小值所在格的基变量离基。第3章运输问题方案改进（闭回路调整法）第3章运输问题17产销不平衡的运输问题产大于销：虚设一个销地Bk(多于物资在产地存储)，其运价为0，销量(存储量)为产销量之差bk=

ai-bj。产小于销：虚设一个产地Al(不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差ak=

bj

-

ai

。带存储费或缺货费的产销不平衡运输问题第3章运输问题产销不平衡的运输问题第3章运输问题18第4章整数线性规划教学要求1)了解整数规划的特点及应用。会建立整数规划模型。2)学会分配问题与匈牙利法。3)理解并掌握分枝定界法。4)理解割平面法。了解割平面法求解整数规划思想与方法。教学重点与难点重点:解整数规划问题的分枝定界法和割平面法；分配问题的数学模型及其解法。难点:分枝定界法和割平面法；分配问题的解法。第4章整数线性规划教学要求19整数规划建模问题经典分配(指派)问题第4章整数线性规划分配问题的数学模型

设决策变量为：s.t.整数规划建模问题第4章整数线性规划分配问题的数学模型设20匈牙利方法步骤第一步：成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个0；第二步：画直线覆盖全部0元素。覆盖原则如果直线条数=n（此时矩阵每行都有一个打（）的0，并且所有打（）的0必在不同行不同列）,只要令对应打（）0元素的xij=1即为最优解，算法结束。如果直线条数<n（此时打（）的0个数<n），转下一步；第三步：进行成本矩阵变换。变换原则得到一个新的成本矩阵，转第二步。直到矩阵的每一行都有一个打（）的0元素为止第4章整数线性规划匈牙利方法步骤第4章整数线性规划21匈牙利方法步骤覆盖原则1、从第一行开始，若该行只有一个0元素，就对这个0打上（），对打（）的0元素所在列画一条直线；若该行没有或有两个以上0（已划去的不计在内），则转下一行，依次进行到最后一行；2、从第一列开始，与行做法类似，依次进行到最后一列；3、重复以上两个步骤。若还有未被划去的0,且未被划去的0之间存在闭回路。这时可沿着闭回路的走向，对每个间隔的0打（），然后对打（）的0，或所在的行，或所在的列，画一条直线。变换原则1、从矩阵未被直线覆盖的数字中找出一个最小的数k；2、对矩阵的每行，当该行有直线覆盖时，令ui=0，无直线覆盖的令ui=k；3、对矩阵有直线覆盖的列，令vj=-k，对无直线覆盖的令vj=0；4、从原矩阵的每个元素cij中分别减去ui和vj，得到一个新矩阵。第4章整数线性规划匈牙利方法步骤第4章整数线性规划22第4章整数线性规划一般指派问题的转化(1)最大化分配问题(2)人数和工作数不等的分配问题(3)一个人可做几项工作的分配问题(4)某项工作一定不能由某人做的分配问题第4章整数线性规划一般指派问题的转化(1)最大化分配问题23第4章整数线性规划分枝定界法步骤(1)不考虑整数约束，解相应LP问题(即松弛问题)(2)检查是否符合整数要求，是，则得最优解，算法结束。否则，转下步(3)分枝:任取一个非整数变量xi=bi，构造两个新的约束条件：xi

≤[bi],xi

≥[bi]+1,分别加入到上一个LP问题，形成两个新的分枝问题。(4)定界:不考虑整数要求，解分枝问题。若整数解的Z值>所有分枝末梢的Z值，则得最优解。否则，取Z值最大的非整数解，继续分解，Goto3第4章整数线性规划分枝定界法步骤24第4章整数线性规划割平面方法(Gomory)

掌握确定Gomory约束的方法通常取非整数解变量中分数部分最大的一个基变量所在的方程来求G-约束选：拆：取:变:移：第4章整数线性规划割平面方法(Gomory)通常取非整数解25第6章网络分析教学要求1)．理解图的基本概念与模型。会建立图的模型。2)．了解树图和图的最小部分树。掌握树图的性质。3)．掌握最短路问题。4)．掌握网络的最大流。5)．掌握最小费用最大流问题。教学重点与难点重点:最小支撑树问题；最短路问题最大流问题。难点:最短路与最大流问题的求解方法。第6章网络分析教学要求26第6章网络分析树图定义与性质(1)定义:一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。(2)定理以下关于树的六种不同描述是等价的：①无圈连通图。②无圈，q=p-1(p点数;q边数)。③连通，q=p-1。④无圈，但若任意增加一条边，则可得到一个且仅一个圈。⑤连通，但若任意舍弃一条边，图便不连通。⑥每一对顶点之间有一条且仅有一条链。第6章网络分析树图定义与性质27网络最小部分树问题(1)破圈法(2)生长法(避圈法)第6章网络分析网络最小部分树问题第6章网络分析28网络最短路问题----表格实现第6章网络分析v1139538362v6v5v3v4v22058910网络最短路问题----表格实现第6章网络分析v11329第6章网络分析vjv1v2v3v4v5v6初始值T(vj

)0∞∞∞∞∞第一次P()+lij0+20+60+∞0+∞0+∞T()26∞∞∞第二次P()+lij2+32+82+92+∞T()51011∞第三次P()+lij5+55+35+∞T()108∞第四次P()+lij8+∞8+1T()109第6章网络分析vjv1v2v3v4v5v6初始值T(vj30网络最大流问题最大流问题的数学模型：

可行流定义第6章网络分析网络最大流问题第6章网络分析31网络最大流问题2.割的定义

割是指将容量网络中的发点和收点分割开,并使和流中断的一组弧的集合.第6章网络分析},),({S(S,)jijiÎ=uuuu网络割的容量最小割

所有割集中容量最小的一个割集.网络最大流问题第6章网络分析},),({S(S,)32网络最大流问题3.增广链定义第6章网络分析是指满足以下条件的s→t的一条链:在这条链上所有指向为s→t的弧为非饱合弧(f<c);所有指向为t→s的弧有非零流弧(f>0).增广链的作用可调整可行流的流量,使流量增大.调整原则若在一个有可行流的网络图中不存在增广链,则说明流量不能再调整,于是当前流为最大流.即是否存在增广链是判断最大流的标志网络最大流问题第6章网络分析是指满足以下条件的s→t的一条33网络最大流问题3.Ford－Fulkerson算法步骤

第6章网络分析①为网络分配初始流fij标在图中弧旁的()内或为已知；②寻求增广链（标号原则）。若不存在，则已最优,算法结束；否则转下步；③在增广链上调整流量（调整原则），产生新的可行流，转步②。网络最大流问题第6章网络分析①为网络分配初始流fij标在图34网络最小费用流问题算法一般步骤第一步从零流开始.f0为可行流,也是相应的流量为0时费用最小的;第二步对可行流构造加权网络W(fk).构造原则.第三步在加权网络W(fk)中寻找费用最小的增广链,也即求从s到t的最短路,并将该增广链上流量调整至允许的最大值,得到一个新的流量更大的可行流,转第二步;若在此网络图中不存在这样的增广链,则当前流即为要寻找的最小费用最大流,算法结束.第6章网络分析网络最小费用流问题第6章网络分析35网络最小费用流问题构造加权网络W(fk)构造原则.对0<fij<cij的弧,当其为正向弧时,通过单位流量的费用为bij,为反向弧时,相应的费用为-bij.即在i和j点间分别画出弧(i,j)和(j,i),其权数分别为bij和-bij;对fij=cij的弧(i,j),因该弧流量已饱和,在增广链中只能作为反向弧,故在W(fk)中只画出弧(j,i),其权数为-bij;对fij=0的弧(i,j),在增广链中只能为正向弧,故在W(fk)中只画出弧(i,j),其权数为bij.第6章网络分析网络最小费用流问题第6章网络分析36第8章动态规划教学要求1)理解多阶段的决策问题。2)掌握最优化原理与动态规划的数学模型。3)掌握确定性动态规划模型的求解。4)了解一般数学规划模型的动态规划解法。教学重点与难点重点:最优化原理与动态规划的数学模型；离散确定性动态规划模型的求解。

难点:最优化原理与动态规划的思想方法。

第8章动态规划教学要求371.动态规划最优性原理

“最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策序列必构成最优策略”。最优性原理的含意

(1)最优策略的任何一部分子策略，也是相应初始状态的最优