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

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

2、第第1章章 线性规划线性规划准型化准型化 3 线性规划解的概念线性规划解的概念-基基,基解基解,基可行解基可行解,4 线性规划的图解法线性规划的图解法5 单纯形法原理单纯形法原理(1)线性规划问题的可行解集线性规划问题的可行解集(即可行域即可行域)是凸集是凸集.(2)(线性规划几何理论基本定理线性规划几何理论基本定理)若若X是一可行解是一可行解,则则X是是C的一个顶点的充分必要条件是的一个顶点的充分必要条件是X为线性规为线性规 划的基本可划的基本可行解行解.(3)若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上

3、达到最优值达到最优值.(即即LP有最优解有最优解,一定存在一个基可行解是最优解一定存在一个基可行解是最优解)(4)若目标函数在若目标函数在k个点处达到最优值个点处达到最优值(k2),世隔绝则在这些点的任意凸组世隔绝则在这些点的任意凸组合上也达到最优值合上也达到最优值.第第1章章 线性规划线性规划单纯形法单纯形法将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量计算各非基变量xj的检验数的检验数 j=Cj-CBPj，若所有，若所有 j0，则问题已得，则问题已得到最

4、优解，停止计算，否则转入下步。到最优解，停止计算，否则转入下步。在大于在大于0的检验数中，若某个的检验数中，若某个 k所对应的系数列向量所对应的系数列向量Pk0,则此问则此问题是无界解，停止计算，否则转入下步。题是无界解，停止计算，否则转入下步。根据根据max j j0=k原则，确定原则，确定xk为换入变量为换入变量(进基变量进基变量)，再按，再按 规则计算：规则计算：=minbi/aik|aik0=bl/aik 确定确定xBl为换出变量。建立新为换出变量。建立新的单纯形表，此时基变量中的单纯形表，此时基变量中xk取代了取代了xBl的位置。的位置。以以aik为主元素进行迭代，把为主元素进行迭代

5、，把xk所对应的列向量变为单所对应的列向量变为单位列向量，即位列向量，即aik变为变为1，同列中其它元素为，同列中其它元素为0，转第，转第 步。步。第第1章章 线性规划线性规划 LP无解的条件无解的条件;LP有无界解的条件有无界解的条件;LP有无穷解的条件有无穷解的条件;LP有惟一解的条件有惟一解的条件;LP有退化解的条件有退化解的条件.第第1章章 线性规划线性规划第第1章章 线性规划线性规划第第2章章 对偶理论对偶理论 教学要求教学要求1)理解原问题与对偶问题。会写对偶问题。理解原问题与对偶问题。会写对偶问题。2)了解对偶问题的基本性质。了解对偶问题的基本性质。3)掌握对偶单纯形法。掌握对偶

6、单纯形法。4)掌握灵敏度分析。掌握灵敏度分析。5)了解影子价格。解释经济意义。了解影子价格。解释经济意义。教学重点与难点教学重点与难点重点重点:线性规划的对偶理论和基本性质；线性规划的对偶理论和基本性质；对偶单纯形法的对偶单纯形法的计算方法；计算方法；灵敏度分析。灵敏度分析。难点难点:对偶理论及基本性质；对偶单纯形法；灵敏度分析对偶理论及基本性质；对偶单纯形法；灵敏度分析第第2章章 对偶理论对偶理论0.minYCYAtsYbW（D）0.maxXbAXtsCXZ（L）上、下上、下”交换，交换，“左、右左、右”换位，换位，不等式变号，不等式变号，“极大极大”变变“极小极小。注注:由该定理可以得到由

7、该定理可以得到 互补松弛性互补松弛性第第2章章 对偶理论对偶理论bYXC（b列保列保0）（检验数行（检验数行0）第第2章章 对偶理论对偶理论第第2章章 对偶理论对偶理论否否初始正则解初始正则解()检查可行检查可行是则停止是则停止得最优解得最优解选出基变量选出基变量检查检查是否无可是否无可行解行解是则停止是则停止否否无最优解无最优解选入基变量选入基变量进行旋转变换进行旋转变换灵敏度分析灵敏度分析 价值系数价值系数C发生变化的情况发生变化的情况 右端常数右端常数b发生变化发生变化 系数阵系数阵A的元素发生变化的元素发生变化 (1)增加增加1个新变量个新变量;(2)增加增加1个约束条件个约束条件.第

8、第2章章 对偶理论对偶理论第第3章章 运输问题 教学要求教学要求1)理解运输问题的典例和数学模型。理解运输问题的典例和数学模型。2)掌握表上作业法。掌握表上作业法。3)掌握产销不平衡的运输问题及其处理方法。掌握产销不平衡的运输问题及其处理方法。教学重点与难点教学重点与难点重点重点:运输问题的表上作业法；产销不平衡问题的转化。运输问题的表上作业法；产销不平衡问题的转化。难点难点:表上作业法；产销不平衡问题的求解方法。表上作业法；产销不平衡问题的求解方法。运输问题的三种类型运输问题的三种类型 产销平衡产销平衡第第3章章 运输问题11mnijijab 1111min,1,2,.,1,2,.,0mni

9、jijijnijijmijjiijZc xxaimxbjnx 表上作业法求解步骤：表上作业法求解步骤：找出初始方案（初始基可行解）：在找出初始方案（初始基可行解）：在m n维产销平衡维产销平衡表上给出表上给出m+n-1个数字。个数字。最优性检验：计算各非基变量的检验数，当最优性检验：计算各非基变量的检验数，当 ij 0最优。最优。方案调整与改进：确定进基变量和离基变量，找出新方案调整与改进：确定进基变量和离基变量，找出新的基可行解。的基可行解。第第3章章 运输问题 确定初始方案确定初始方案(1)最小元素法最小元素法“就近运给就近运给”，从单位运价表中最小运价开始确定供销关系，从单位运价表中最小

10、运价开始确定供销关系，逐次挑选最小元素，安排运量逐次挑选最小元素，安排运量minai,bj。(2)最大差额法最大差额法(Vogel法法)不能按最小运费就近供应，就考虑次小运费。不能按最小运费就近供应，就考虑次小运费。各行各行(各列各列)的最小运费与次小运费之差称为行差的最小运费与次小运费之差称为行差(列差列差)。差差额越大，说明不能按最小运费调运时，运费增加最多。额越大，说明不能按最小运费调运时，运费增加最多。对最大差额处就采用最小运费调运。对最大差额处就采用最小运费调运。第第3章章 运输问题 最优性检验最优性检验 判别方法是计算非基变量的检验数判别方法是计算非基变量的检验数：ij=cij C

11、BPij=cij CBB-1Pij 运输问题的目标函数要求为最小，即当运输问题的目标函数要求为最小，即当 ij 0视为最优。视为最优。位势法位势法计算检验数计算检验数 ij=cij CBPij=cij CBB-1Pij ij=cij(ui+vj)ui代表产地代表产地Ai的位势量，的位势量，vj代表销地代表销地Bj的位势量。的位势量。基变量的检验数为基变量的检验数为0，即，即 ij=cij ui vj=0，并令并令u1=0，计算各行各列的位势量。，计算各行各列的位势量。第第3章章 运输问题 方案改进（闭回路调整法）方案改进（闭回路调整法）(1)确定进基变量确定进基变量 检查非基变量检查非基变量x

12、ij的检验数的检验数 ij，按，按 min ij|ij 0=lk 确定确定xlk进基。进基。(2)确定离基变量确定离基变量 非基变量非基变量xlk进基之后，要求它的运量增加量按照它所在行和列的进基之后，要求它的运量增加量按照它所在行和列的运量保持运量保持。保持产销平衡的方法是。保持产销平衡的方法是。以进基变量以进基变量xlk所在格为始点和终点，其余顶点均为基所在格为始点和终点，其余顶点均为基变量的封闭回路。变量的封闭回路。：从进基变量：从进基变量xlk所在格开始，用水平或垂直线向前所在格开始，用水平或垂直线向前划，每碰到一个基变量格转划，每碰到一个基变量格转90，继续前进，直到返回始点。，继续

13、前进，直到返回始点。始点是偶点，依次奇偶相间标注；偶点标始点是偶点，依次奇偶相间标注；偶点标“+”，表示运，表示运量增加量；奇点标量增加量；奇点标“-”，表示运量减少量。，表示运量减少量。最大可调整的运量，为奇点运量的最小值。最大可调整的运量，为奇点运量的最小值。奇点运量的最小值所在格的基变量离基。奇点运量的最小值所在格的基变量离基。第第3章章 运输问题 产销不平衡的运输问题产销不平衡的运输问题 产大于销：产大于销：虚设一个销地虚设一个销地 Bk(多于物资在产地存储多于物资在产地存储)，其运价为，其运价为0，销量销量(存储量存储量)为产销量之差为产销量之差 bk=ai-bj。产小于销：产小于销

14、：虚设一个产地虚设一个产地 Al(不足物资的脱销量不足物资的脱销量)，其运价为，其运价为0，产，产量量(脱销量脱销量)为销产量之差为销产量之差 ak=bj-ai。带存储费或缺货费的产销不平衡运输问题带存储费或缺货费的产销不平衡运输问题第第3章章 运输问题第第4章章 整数线性规划整数线性规划 教学要求教学要求1)了解整数规划的特点及应用。会建立整数规划模型。了解整数规划的特点及应用。会建立整数规划模型。2)学会分配问题与匈牙利法。学会分配问题与匈牙利法。3)理解并掌握分枝定界法。理解并掌握分枝定界法。4)理解割平面法。了解割平面法求解整数规划思想与方法。理解割平面法。了解割平面法求解整数规划思想

15、与方法。教学重点与难点教学重点与难点重点重点:解整数规划问题的分枝定界法和割平面法；分配问题解整数规划问题的分枝定界法和割平面法；分配问题的数学模型及其解法。的数学模型及其解法。难点难点:分枝定界法和割平面法；分配问题的解法。分枝定界法和割平面法；分配问题的解法。整数规划建模问题整数规划建模问题 经典分配经典分配(指派指派)问题问题第第4章章 整数线性规划整数线性规划分配问题的数学模型分配问题的数学模型 设决策变量为：设决策变量为：0 1否则项工作员工分配做第第jixijn1in1jijijc=z max)min(or xn ,1,2,=j 1xn1iijs.t.n ,1,2,=j 1xn1i

16、ijn,1,=jn;,1,2,=i 1,0 xij或 匈牙利方法步骤匈牙利方法步骤第一步：成本矩阵的每一行及每一列减去该行或列的最小数，第一步：成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个使每行每列至少有一个0；第二步：画直线覆盖全部第二步：画直线覆盖全部0元素。元素。覆盖原则覆盖原则 如果直线条数如果直线条数=n（此时矩阵每行都有一个打（）的（此时矩阵每行都有一个打（）的0，并且所有打（）的并且所有打（）的0必在不同行不同列）必在不同行不同列）,只要令对应打（）只要令对应打（）0元素的元素的xij=1即为最优解，算法结束。即为最优解，算法结束。如果直线条数如果直线条数

17、n（此时打（）的（此时打（）的0个数个数所有分枝末梢的所有分枝末梢的Z值，则得最优解。否则，值，则得最优解。否则，取取Z值值最大的非整数解，继续分解，最大的非整数解，继续分解，Go to 3第第4章章 整数线性规划整数线性规划 割平面方法割平面方法(Gomory)(Gomory)掌握确定掌握确定Gomory约束的方法的方法通常取非整数解变量中分数部分最大的一个基变量所在的通常取非整数解变量中分数部分最大的一个基变量所在的方程来求方程来求G-约束约束选选：1351213777xxx拆：拆：15356151777xxxx356150777xx取取:356156777xxx 变变:135156(0)

18、(1)1777xxx 移：移：第第6章章 网络分析网络分析 教学要求教学要求1)理解图的基本概念与模型。会建立图的模型。理解图的基本概念与模型。会建立图的模型。2)了解树图和图的最小部分树。掌握树图的性质。了解树图和图的最小部分树。掌握树图的性质。3)掌握最短路问题。掌握最短路问题。4)掌握网络的最大流。掌握网络的最大流。5)掌握最小费用最大流问题。掌握最小费用最大流问题。教学重点与难点教学重点与难点重点重点:最小支撑树问题；最短路问题最大流问题。最小支撑树问题；最短路问题最大流问题。难点难点:最短路与最大流问题的求解方法。最短路与最大流问题的求解方法。第第6章章 网络分析网络分析 树图定义与

19、性质树图定义与性质(1)定义定义:一个连通的无圈图则称为树，一个林的每个连通子一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。图都是一个树。(2)定理定理 以下关于树的六种不同描述是等价的：以下关于树的六种不同描述是等价的：无圈连通图。无圈连通图。无圈，无圈，q=p-1(p点数点数;q边数边数)。连通，连通，q=p-1。无圈，但若任意增加一条边，则可得到一个且仅一个圈。无圈，但若任意增加一条边，则可得到一个且仅一个圈。连通，但若任意舍弃一条边，图便不连通。连通，但若任意舍弃一条边，图便不连通。每一对顶点之间有一条且仅有一条链。每一对顶点之间有一条且仅有一条链。网络最小部分树问题网络最

20、小部分树问题(1)破圈法破圈法(2)生长法生长法(避圈法避圈法)第第6章章 网络分析网络分析 网络最短路问题网络最短路问题-表格实现表格实现第第6章章 网络分析网络分析 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v22058910第第6章章 网络分析网络分析vjv1v2v3v4v5v6初始值初始值T(vj)0第一次第一次P()+lij0+2 0+6 0+0+0+T()26第二次第二次P()+lij2+3 2+82+92+T()51011第三次第三次P()+lij5+55+35+T()108第四次第四次P()+lij8+8+1T()109网络最大流问题网络最大流问题1.最大流

21、问题的数学模型：最大流问题的数学模型：可行流定义可行流定义第第6章章 网络分析网络分析max0,.0jiijjjijijffisffis tstfitfc 网络最大流问题网络最大流问题2.割的定义割的定义 割是指将容量网络中的发点和收点分割开割是指将容量网络中的发点和收点分割开,并使并使和流中断的一组弧的集合和流中断的一组弧的集合.第第6章章 网络分析网络分析,),(S(S,)jijiuuuuS),(),(),(SSijjifSScuu网络割的容量网络割的容量最小割最小割 所有割集中容量最小的一个割集所有割集中容量最小的一个割集.),(*SScS 网络最大流问题网络最大流问题3.增广链定义增广

22、链定义第第6章章 网络分析网络分析是指满足以下条件的是指满足以下条件的st的一条链的一条链:在这条链上在这条链上 所有指向为所有指向为st的弧为非饱合弧的弧为非饱合弧(f0).增广链的作用增广链的作用(1)可调整可行流的流量可调整可行流的流量,使流量增大使流量增大.调整原则调整原则(2)若在一个有可行流的网络图中不存在增广链若在一个有可行流的网络图中不存在增广链,则说则说明流量不能再调整明流量不能再调整,于是当前流为最大流于是当前流为最大流.即即(3)是否存在增广链是判断最大流的标志是否存在增广链是判断最大流的标志网络最大流问题网络最大流问题3.FordFulkerson算法算法步骤步骤 第第

23、6章章 网络分析网络分析为网络分配初始流为网络分配初始流fij标在图中弧旁的标在图中弧旁的()内或为已知；内或为已知；寻求增广链（寻求增广链（标号原则标号原则）。若不存在，则已最优）。若不存在，则已最优,算法结算法结束；否则转下步；束；否则转下步；在增广链上调整流量（在增广链上调整流量（调整原则调整原则），产生新的可行流，转），产生新的可行流，转步步。网络最小费用流问题网络最小费用流问题算法一般步骤算法一般步骤 第一步第一步 从零流开始从零流开始.f0为可行流为可行流,也是相应的流量为也是相应的流量为0时费时费用最小的用最小的;第二步第二步 对可行流构造加权网络对可行流构造加权网络W(fk).

24、构造原则构造原则.第三步第三步 在加权网络在加权网络W(fk)中寻找费用最小的增广链中寻找费用最小的增广链,也即求也即求从从s到到t的最短路的最短路,并将该增广链上流量调整至允许的最大并将该增广链上流量调整至允许的最大值值,得到一个新的流量更大的可行流得到一个新的流量更大的可行流,转第二步转第二步;若在此网若在此网络图中不存在这样的增广链络图中不存在这样的增广链,则当前流即为要寻找的最小则当前流即为要寻找的最小费用最大流费用最大流,算法结束算法结束.第第6章章 网络分析网络分析 网络最小费用流问题网络最小费用流问题构造加权网络构造加权网络W(fk)构造原则构造原则.对对0fijcij的弧的弧,

25、当其为正向弧时当其为正向弧时,通过单位流量的费用为通过单位流量的费用为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.

26、第第6章章 网络分析网络分析第第8章章 动态规划动态规划 教学要求教学要求1)理解多阶段的决策问题。理解多阶段的决策问题。2)掌握最优化原理与动态规划的数学模型。掌握最优化原理与动态规划的数学模型。3)掌握确定性动态规划模型的求解。掌握确定性动态规划模型的求解。4)了解一般数学规划模型的动态规划解法。了解一般数学规划模型的动态规划解法。教学重点与难点教学重点与难点重点重点:最优化原理与动态规划的数学模型；离散确定性动态最优化原理与动态规划的数学模型；离散确定性动态规划模型的求解。规划模型的求解。难点难点:最优化原理与动态规划的思想方法。最优化原理与动态规划的思想方法。1.动态规划最优性原理动态

27、规划最优性原理 “最优策略具有的基本性质是：无论初始状态和初始最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策如何，对于前面决策所造成的某一状态而言，下余的决策序列必构成最优策略决策序列必构成最优策略”。最优性原理的含意最优性原理的含意 (1)最优策略的任何一部分子策略，也是相应初始状态的最最优策略的任何一部分子策略，也是相应初始状态的最优策略。优策略。(2)每个最优策略只能由最优子策略构成。每个最优策略只能由最优子策略构成。第第8章章 动态规划动态规划2.动态规划四大要素、一个方程动态规划四大要素、一个方程四大要素、一个方程：四大要素、一个方

28、程：状态变量及其可能集合状态变量及其可能集合决策变量及其允许集合决策变量及其允许集合状态转移方程状态转移方程阶段效应阶段效应动态规划基本方程：动态规划基本方程：1()(,)(,)kkkkkkkkkkufxopt rxufTxu 第第8章章 动态规划动态规划3.动态规划典型问题动态规划典型问题 (1)最短路问题最短路问题 (2)资源分配问题资源分配问题 资源的多元分配资源的多元分配 资源的多段分配资源的多段分配 (3)设备更新问题设备更新问题 (4)生产库存问题生产库存问题 第第8章章 动态规划动态规划第第9章章 库存论库存论 教学要求教学要求1)、掌握经济订购批量存贮模型。基本的、掌握经济订购

29、批量存贮模型。基本的EOQ模型、一般的模型、一般的EOQ模型、允许缺货的模型、允许缺货的EOQ模型、生产需一定周期，不模型、生产需一定周期，不允许缺货的允许缺货的EOQ模型。模型。2)、掌握具有约束条件的存贮模型。、掌握具有约束条件的存贮模型。3)、掌握具有价格折扣优惠的存贮模型。、掌握具有价格折扣优惠的存贮模型。4)、掌握动态的存贮模型。动态的存贮模型建立和求解。、掌握动态的存贮模型。动态的存贮模型建立和求解。教学重点与难点教学重点与难点重点重点:确定性存储模型及其求解方法确定性存储模型及其求解方法 难点难点:确定性和随机性存储模型的求解。确定性和随机性存储模型的求解。(1)每次订货周期每次

30、订货周期T,订货量订货量Q（每次生产（每次生产,固定装配固定装配费）；费）；(2)最佳存储量最佳存储量S0(3)每次订货固定费每次订货固定费C1（每次生产（每次生产,固定装配费）；固定装配费）；(4)单位货物单位时间存储费单位货物单位时间存储费C2;(5)缺货费用为缺货费用为C3；(6)需求速度需求速度 r是（单位时间的需求量）是（单位时间的需求量）第第9章章 库存论库存论模型一模型一（不允许缺货，生产需要时间很短）（不允许缺货，生产需要时间很短）11002222,CC RTQC RC最佳存储量最佳存储量00QS 模型二模型二（不允许缺货，生产需一定时间）（不允许缺货，生产需一定时间）11002222,CC RppTQC RpRCpR最佳存储量最佳存储量 012()2SpR tC RpRCp模型三模型三（允许缺货，生产需时间很短）（允许缺货，生产需时间很短）23231100232322,CCCCCC RTQC RCCC最佳存储量最佳存储量 3102232CC RSCCC 2310232CCCptC RCpR 23100232CCC RpQRtCCpR 模型四模型四（允许缺货，生产需一定时间）（允许缺货，生产需一定时间）