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

教学要求教学要求1).了解一般线性规划问题的数学模型。了解一般线性规划问题的数学模型。2)掌握图解法。掌握图解法。3)理解单纯形法原理。理解单纯形法原理。4)掌握单纯形法的计算步骤。掌握单纯形法的计算步骤。5)对单纯形法的进一步讨论。对单纯形法的进一步讨论。6)了解单纯形法的矩阵描述。了解单纯形法的矩阵描述。教学重点与难点教学重点与难点重点重点:1、单纯形方法中初始可行基的确定方法、基可行解的、单纯形方法中初始可行基的确定方法、基可行解的转换和最优性检验；转换和最优性检验；2、运用单纯形表求解线性规划问题。、运用单纯形表求解线性规划问题。难点难点:最优性检验、基的变换。最优性检验、基的变换。第第1章章 线性规划线性规划教学要求第1章 线性规划11 1、线性规划问题的数学建模、线性规划问题的数学建模、线性规划问题的数学建模、线性规划问题的数学建模2 2、LPLP的数学模型及的数学模型及的数学模型及的数学模型及准型化准型化 3、线性规划解的概念线性规划解的概念-基基,基解基解,基可行解基可行解,4、线性规划的图解法线性规划的图解法5、单纯形法原理单纯形法原理(1)线性规划问题的可行解集线性规划问题的可行解集(即可行域即可行域)是凸集是凸集.(2)(线性规划几何理论基本定理线性规划几何理论基本定理)若若X是一可行解是一可行解,则则X是是C的一个顶点的充分必要条件是的一个顶点的充分必要条件是X为线性规为线性规 划的基本可划的基本可行解行解.(3)若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值达到最优值.(即即LP有最优解有最优解,一定存在一个基可行解是最优解一定存在一个基可行解是最优解)(4)若目标函数在若目标函数在k个点处达到最优值个点处达到最优值(k2),世隔绝则在这些点的任意凸世隔绝则在这些点的任意凸组合上也达到最优值组合上也达到最优值.第第1章章 线性规划线性规划1、线性规划问题的数学建模第1章 线性规划26 6、单纯形法单纯形法将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。阶单位矩阵作为初始可行基，建立初始单纯形表。计计算算各各非非基基变变量量xj的的检检验验数数 j=Cj-CBPj，若若所所有有 j0，则则问问题题已已得得到最优解，停止计算，否则转入下步。到最优解，停止计算，否则转入下步。在在大大于于0的的检检验验数数中中，若若某某个个 k所所对对应应的的系系数数列列向向量量Pk0,则则此此问问题题是无界解，停止计算，否则转入下步。是无界解，停止计算，否则转入下步。根根据据max j j0=k原原则则，确确定定xk为为换换入入变变量量(进进基基变变量量)，再再按按 规规则则计计算算：=minbi/aik|aik0=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*;在最终表中在最终表中在最终表中在最终表中,与初始单纯形表里的单位阵对应的矩与初始单纯形表里的单位阵对应的矩与初始单纯形表里的单位阵对应的矩与初始单纯形表里的单位阵对应的矩阵即为最优基的逆阵即为最优基的逆阵即为最优基的逆阵即为最优基的逆(B*)(B*)-1-1.第第1章章 线性规划线性规划8、单纯形中确定最优基及其逆的方法第1章 线性规划5第第2章章 对偶理论对偶理论 教学要求教学要求1)理解原问题与对偶问题。会写对偶问题。理解原问题与对偶问题。会写对偶问题。2)了解对偶问题的基本性质。了解对偶问题的基本性质。3)掌握对偶单纯形法。掌握对偶单纯形法。4)掌握灵敏度分析。掌握灵敏度分析。5)了解影子价格。解释经济意义。了解影子价格。解释经济意义。教学重点与难点教学重点与难点重点重点:线性规划的对偶理论和基本性质；线性规划的对偶理论和基本性质；对偶单纯形法的对偶单纯形法的计算方法；计算方法；灵敏度分析。灵敏度分析。难点难点:对偶理论及基本性质；对偶单纯形法；灵敏度分析对偶理论及基本性质；对偶单纯形法；灵敏度分析第2章 对偶理论 教学要求61、对称形式的对偶关系、对称形式的对偶关系第第2章章 对偶理论对偶理论（D）（L）上、下上、下”交换，交换，“左、右左、右”换位，换位，不等式变号，不等式变号，“极大极大”变变“极小极小 一般形式的对偶问题按照原始一般形式的对偶问题按照原始一般形式的对偶问题按照原始一般形式的对偶问题按照原始-对偶表直接写出对偶表直接写出对偶表直接写出对偶表直接写出 1、对称形式的对偶关系第2章 对偶理论（D）（L）上、下72 2、对偶问题的基本性质（对偶定理）、对偶问题的基本性质（对偶定理）、对偶问题的基本性质（对偶定理）、对偶问题的基本性质（对偶定理）对称性定理对称性定理对称性定理对称性定理对偶问题的对偶是原问题对偶问题的对偶是原问题对偶问题的对偶是原问题对偶问题的对偶是原问题。弱对偶定理弱对偶定理弱对偶定理弱对偶定理若一对对称形式的对偶线性规划若一对对称形式的对偶线性规划若一对对称形式的对偶线性规划若一对对称形式的对偶线性规划 注注:由该定理可以得到由该定理可以得到关于关于关于关于“界界界界”的结果的结果的结果的结果无界性定理无界性定理无界性定理无界性定理最优性准则定理最优性准则定理最优性准则定理最优性准则定理强对偶定理强对偶定理强对偶定理强对偶定理 若原始问题和对偶问题两者均可行，则两者均有最若原始问题和对偶问题两者均可行，则两者均有最若原始问题和对偶问题两者均可行，则两者均有最若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。优解，且此时目标函数值相同。优解，且此时目标函数值相同。优解，且此时目标函数值相同。互补松弛性互补松弛性定理定理定理定理 第第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个数字。个数字。最优性检验：计算各非基变量的检验数，当最优性检验：计算各非基变量的检验数，当 ij 0最优。最优。方案调整与改进：确定进基变量和离基变量，找出新方案调整与改进：确定进基变量和离基变量，找出新的基可行解。的基可行解。第第3章章 运输问题表上作业法求解步骤：第3章 运输问题14确定初始方案确定初始方案(1)最小元素法最小元素法“就近运给就近运给”，从单位运价表中最小运价开始确定供销关系，从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量逐次挑选最小元素，安排运量minai,bj。(2)最大差额法最大差额法(Vogel法法)不能按最小运费就近供应，就考虑次小运费。不能按最小运费就近供应，就考虑次小运费。各行各行(各列各列)的最小运费与次小运费之差称为行差的最小运费与次小运费之差称为行差(列差列差)。差额越大，说明不能按最小运费调运时，运费增加最多。差额越大，说明不能按最小运费调运时，运费增加最多。对最大差额处就采用最小运费调运。对最大差额处就采用最小运费调运。第第3章章 运输问题确定初始方案第3章 运输问题15最优性检验最优性检验判别方法是计算非基变量的检验数判别方法是计算非基变量的检验数：ij=cij CBPij=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章章 运输问题最优性检验第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个数个数所有分枝末梢的所有分枝末梢的Z值，则得最优解。否则，值，则得最优解。否则，取取Z值值最大的非整数解，继续分解，最大的非整数解，继续分解，Go to 3第4章 整数线性规划分枝定界法步骤24第第4章章 整数线性规划整数线性规划割平面方法割平面方法(Gomory)(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章章 网络分析网络分析 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v22058910网络最短路问题-表格实现第6章 网络分析 v1 1 329第第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第6章 网络分析vjv1v2v3v4v5v6初始值T(vj30网络最大流问题网络最大流问题1.最大流问题的数学模型：最大流问题的数学模型：2.可行流定义可行流定义第第6章章 网络分析网络分析网络最大流问题第6章 网络分析31网络最大流问题网络最大流问题2.割的定义割的定义 割是指将容量网络中的发点和收点分割开割是指将容量网络中的发点和收点分割开,并使并使和流中断的一组弧的集合和流中断的一组弧的集合.第第6章章 网络分析网络分析,),(S(S,)jiji=uuuu网络割的容量网络割的容量最小割最小割 所有割集中容量最小的一个割集所有割集中容量最小的一个割集.网络最大流问题第6章 网络分析,),(S(S,)32网络最大流问题网络最大流问题3.增广链定义增广链定义第第6章章 网络分析网络分析是指满足以下条件的是指满足以下条件的st的一条链的一条链:在这条链上在这条链上 所有指向为所有指向为st的弧为非饱合弧的弧为非饱合弧(f0).增广链的作用增广链的作用(1)可调整可行流的流量可调整可行流的流量,使流量增大使流量增大.调整原则调整原则(2)若在一个有可行流的网络图中不存在增广链若在一个有可行流的网络图中不存在增广链,则说则说明流量不能再调整明流量不能再调整,于是当前流为最大流于是当前流为最大流.即即(3)是否存在增广链是判断最大流的标志是否存在增广链是判断最大流的标志网络最大流问题第6章 网络分析是指满足以下条件的st的一条33网络最大流问题网络最大流问题3.FordFulkerson算法步骤算法步骤 第第6章章 网络分析网络分析为网络分配初始流为网络分配初始流fij标在图中弧旁的标在图中弧旁的()内或为已知；内或为已知；寻寻求求增增广广链链（标标号号原原则则）。若若不不存存在在，则则已已最最优优,算算法法结结束；否则转下步；束；否则转下步；在在增增广广链链上上调调整整流流量量（调调整整原原则则），产产生生新新的的可可行行流流，转转步步。网络最大流问题第6章 网络分析为网络分配初始流fij标在图34网络最小费用流问题网络最小费用流问题算法一般步骤算法一般步骤第一步第一步 从零流开始从零流开始.f0为可行流为可行流,也是相应的流量为也是相应的流量为0时费时费用最小的用最小的;第二步第二步 对可行流构造加权网络对可行流构造加权网络W(fk).构造原则构造原则.第三步第三步 在加权网络在加权网络W(fk)中寻找费用最小的增广链中寻找费用最小的增广链,也即也即求从求从s到到t的最短路的最短路,并将该增广链上流量调整至允许的最并将该增广链上流量调整至允许的最大值大值,得到一个新的流量更大的可行流得到一个新的流量更大的可行流,转第二步转第二步;若在若在此网络图中不存在这样的增广链此网络图中不存在这样的增广链,则当前流即为要寻找的则当前流即为要寻找的最小费用最大流最小费用最大流,算法结束算法结束.第第6章章 网络分析网络分析网络最小费用流问题第6章 网络分析35网络最小费用流问题网络最小费用流问题构造加权网络构造加权网络W(fk)构造原则构造原则.对对0fijcij的弧的弧,当其为正向弧时当其为正向弧时,通过单位流量的费用为通过单位流量的费用为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)最优策略的任何一部分子策略，也是相应初始状态的最优策略的任何一部分子策略，也是相应初始状态的最优策略。最优策略。(2)每个最优策略只能由最优子策略构成。每个最优策略只能由最优子策略构成。第第8章章 动态规划动态规划1.动态规划最优性原理第8章 动态规划382.动态规划四大要素、一个方程动态规划四大要素、一个方程四大要素、一个方程：四大要素、一个方程：状态变量及其可能集合状态变量及其可能集合决策变量及其允许集合决策变量及其允许集合状态转移方程状态转移方程阶段效应阶段效应动态规划基本方程：动态规划基本方程：第第8章章 动态规划动态规划2.动态规划四大要素、一个方程四大要素、一个方程：第8章 393.动态规划典型问题动态规划典型问题 (1)最短路最短路问题问题 (2)资源分配问题资源分配问题 资源的多元分配资源的多元分配 资源的多段分配资源的多段分配 (3)设备更新问题设备更新问题 (4)生产库存问题生产库存问题 第第8章章 动态规划动态规划3.动态规划典型问题第8章 动态规划40第第9章章 库存论库存论教学要求教学要求1)、掌握经济订购批量存贮模型。基本的、掌握经济订购批量存贮模型。基本的EOQ模型、一般的模型、一般的EOQ模型、允许缺货的模型、允许缺货的EOQ模型、生产需一定周期，不模型、生产需一定周期，不允许缺货的允许缺货的EOQ模型。模型。2)、掌握具有约束条件的存贮模型。、掌握具有约束条件的存贮模型。3)、掌握具有价格折扣优惠的存贮模型。、掌握具有价格折扣优惠的存贮模型。4)、掌握动态的存贮模型。动态的存贮模型建立和求解。、掌握动态的存贮模型。动态的存贮模型建立和求解。教学重点与难点教学重点与难点重点重点:确定性存储模型及其求解方法确定性存储模型及其求解方法 难点难点:确定性和随机性存储模型的求解。确定性和随机性存储模型的求解。第9章 库存论教学要求41(1)每次订货周期每次订货周期T,订货量订货量Q（每次生产（每次生产,固定装配固定装配费）；费）；(2)最佳存储量最佳存储量S0(3)每次订货固定费每次订货固定费C1（每次生产（每次生产,固定装配费）；固定装配费）；(4)单位货物单位时间存储费单位货物单位时间存储费C2;(5)缺货费用为缺货费用为C3；(6)需求速度需求速度 r是（单位时间的需求量）是（单位时间的需求量）第第9章章 库存论库存论(1)每次订货周期T,订货量Q（每次生产,固定装配费）；42模型一模型一（不允许缺货，生产需要时间很短）（不允许缺货，生产需要时间很短）最佳存储量最佳存储量模型二模型二（不允许缺货，生产需一定时间）（不允许缺货，生产需一定时间）最佳存储量最佳存储量 模型三模型三（允许缺货，生产需时间很短）（允许缺货，生产需时间很短）最佳存储量最佳存储量 模型四模型四（允许缺货，生产需一定时间）（允许缺货，生产需一定时间）模型一（不允许缺货，生产需要时间很短）最佳存储量模型二（不允43