运筹学教学演示系统⑵.ppt

《运筹学教学演示系统⑵.ppt》由会员分享，可在线阅读，更多相关《运筹学教学演示系统⑵.ppt（91页珍藏版）》请在三一办公上搜索。

1、第二章 对偶问题及灵敏度分析,第一节 单纯形法的矩阵描述 矩阵描述的目的是将单纯形法用矩阵来加以解释及有助于对偶问题的分析。一、标准型规划问题的矩阵描述 设线性规划问题为：,所对应的单纯形表为：,关于检验数的再讨论！检验数的统一表示（不论是基变量还是非基变量）某一个变量检验数的表示方法,二、存在松弛变量模型的矩阵描述 设线性规划问题为：,引入松弛变量的模型为：,注意特别强调了松弛变量在模型矩阵描述中的作用！在下面的矩阵描述中，松弛变量独立表示，不归入非基变量。看下面的模型变化！,以此模型构造单纯形表如下：,此表的一个重要目的就是在于B-1所在的位置。,结合教材中，表1-3表1-5的约束方程的系

2、数矩阵，了解B-1的位置及作用。表1-3所对应的模型为：,第二节 对偶问题的提出 线性规划问题具有对偶性！什么是对偶性？任何一个求最大值的线性规划问题都有一个求最小值的线性规划问题与之相对应。一个叫“原始问题”，另一个称为它的“对偶问题”。原始问题和对偶问题所依据的数据资料是一致的！仍以前述模型为例说明对偶问题。,例1 某厂计划在下一个生产周期内生产甲、乙两种产品，这两种产品分别要经过两种设备加工，有关数据如下表，问应如何安排生产计划使总利润最大？其依据的数据资料及模型为：,现在从另一个角度讨论该问题 为什么能够获利呢？因为有资源：A80、B60 不生产甲、乙产品能否获利呢？把已有设备出租 租

3、金或设备使用费用如何收取？不低于自己创收、承租方可以接受 假设设备的每台时使用费分别为Y1、Y2 根据原始数据，用于加工一件产品的设备台时出租后的收益不应低于产品的利润，则得到另一组约束条件：,但是，承租方希望其设备台时的使用费越小越好，则必有：,则原问题的对偶问题为：,原问题,对偶问题,第三节 线性规划的对偶理论 一、对偶问题的定义 设原始线性规划问题为：,则称下列规划问题为原始问题的对偶问题。,注意：Y是行向量还是列向量；其分量的个数？,例2 写出下列规划问题的对偶问题。,注意：一个方程对应一个对偶变量！,原问题,对偶问题,二、非对称规划问题的对偶问题 若原始线性规划问题为：,关键在于将原

4、模型进行转变如下:,则其对偶问题为；,例3 写出下列规划问题的对偶问题,分析一个一般的线性规划问题？如何得到其对偶问题，又能够得到什么结论！,例4 写出下列规划问题的对偶问题,三、对偶问题的基本性质 这是基于对称型问题而言的 1.对称性：对偶问题的对偶问题是原问题 2.弱对偶性；若X(1)和Y(1)分别是可行解，则,结论表明：对偶问题的下界与原问题上界之间的关系,3.无界性：若原问题无界，则其对偶问题无可行解 注意：该问题的逆不存在！4.最优性：原问题和对偶问题都存在可行解，且目标函数值相等，该可行解分别是原问题和对偶问题的最优解。,综上所述，一对对偶问题必然是以下的三种情况：都存在最优解，且

5、最优的目标函数值相等 都无可行解 一个是无界，另一个无可行解 四、互补松弛条件 设X*和Y*分别是原问题和对偶问题的可行解，则它们分别是最优解的充分必要条件是：,注意：互补松弛条件的意义！,五、对偶问题的解 原问题单纯形表的检验数反号后，就是对偶问题的一个基解。证明：对于原问题,其标准型为：,设A中存在一个可行基B，则模型为：,则相应的对偶问题为：,原问题对应于可行基B的检验数可表示为：,代入对偶问题的约束条件，得到：,可见，松弛变量检验数的反号正好对应对偶问题的一个基解。若B为最优基，则,为对偶问题的最优解（松弛变量的检验数）。问题：如果存在人工变量，对偶问题的最优解如何得到？,例5 求下列

6、规划对偶问题的解,加入人工变量后，得到：,其初始和最终单纯形表如下：,讨论这样几个问题：原问题的最优解及最优的目标函数值,最优基及其基的逆矩阵是什么？,初始单纯形表与最终单纯形表的系数矩阵之间的联系,对偶问题的解如何从原问题单纯形表的检验数中得到,对偶问题的解,第四节 影子价格 对偶问题的解具有十分重要的经济意思，它反映了某种资源的影子价格。对偶问题的最优解为：,对偶问题解的经济意思在于其它条件不变的情况下，某种资源单位变化所引起的目标函数值的变化，它是该种资源实现最大利润时的一种价格估计，这种估价是针对具体企业具体产品而存在的一种特殊价格影子价格。,市场价格低于影子价格资源成本，买进 市场价

7、格高于影子价格资源成本，卖出 例6 某企业资源情况及生产计划安排见下表，讨论各资源的影子价格及其意义,最终单纯形表为：,分析这样几个问题：三种资源的影子价格 钢材：3/4 煤炭：0 台时：1/4 影子价格的意义 如增加煤炭这一资源其结果是什么？为什么？影子价格的应用 指导企业内部挖潜的方向：资源稀缺、资源剩余 新产品投产决策：机会成本新产品资源消耗量影子价格,第五节 对偶单纯形法 重要概念：对偶单纯形法不是对对偶问题用单纯形法进行求解。重要回忆：,“可见，松弛变量检验数的反号正好对应对偶问题的一个基解。若B为最优基，则松弛变量检验数的反号为对偶问题的最优解”重要过程：在单纯形表迭代过程中 任一

8、表原问题的基可行解，对偶问题的基解 最终表原问题的基可行解，对偶问题的基可行解 重要思想：若始终保持其对偶问题是基可行解，让原问题从基解（非可行解）向基可行解迭代。,定义：若原问题的一个基解对应的检验数满足,则称此基解为原问题的正则解。根据正则解的定义，重新构造单纯形表。注意：构造原问题单纯形表，而不是对偶问题单纯形表；检验数必须小于等于零，常数项b不一定非负；迭代过程中，原问题是基本解，但对偶问题是可行的；迭代的目的，在检验数保持小于等于零的情况下，使常数项b,步骤：选定一个基，若满足正则解的要求，得到初始单纯形表；若b，则得到最优解，否则转入下一步；确定换出变量：,确定换入变量：,确定旋转

9、元素（主元），迭代得到新的正则解，返回。,例7 求解下列线性规划问题,分析：用单纯形法还是用对偶单纯形法求解？先看单纯形法的典式,若按正则解的要求，其模型为：,则最终单纯形表为：,得到最优解为：,第六节 线性规划问题的灵敏度分析 一、灵敏度分析的基本概念和基本原理 灵敏度分析是指系数及常数项的变化对最优解的影响，有时也讨论新产品是否投产等生产计划问题。以标准线性规划问题为例：,则为最优基的条件是：,当某系数（常数）发生变化，若能继续满足可行性条件和正则性条件，则最优基不变；如果不满足某一个条件，可选择单纯形法或对偶单纯形法继续迭代。二、资源数量b变化的灵敏度分析 资源数量变化不影响正则性条件，

10、只影响可行性条件，因此若能继续保持,则，最优基不发生变化，但决策变量的取值一般会改变。,设原资源数量为：,现第r种资源发生变化，变化后资源的数量为：,资源变化后的可行性条件将变化为：,另外，资源数量在什么范围内变化，而最优基不变呢？,例7 分析下列线性规划问题(p31),则最终单纯形表为：,最优基的逆矩阵是什么？讨论第二种资源的变化范围,第一种资源有个单位的增量，最优解如何变化？,三、目标函数系数C变化的灵敏度分析 目标函数系数的变化不影响可行性条件，只影响正则性条件（检验数），正则性条件（检验数）可以表示为：,非基变量和基变量目标函数系数的变化对检验数的影响是不同的。1.非基变量目标函数系数

11、变化的分析,这里得到了两个方面的结论：一是非基变量系数发生变化后，检验数的变化情况，因此可判断是否对最优解产生影响；二是可确定最优解不变时，非基变量系数变化范围，即,2.基变量目标函数系数变化的分析,为保持原最优解，则：,仍以上例：,四、约束条件变化的灵敏度分析 1.增加新约束条件分析的方法 就是判断最优解能否满足新的约束条件。满足：仍为最优解（可能可行域减小）不满足：增加该约束条件，用对偶单纯形法迭代。2.原某个约束条件的改变 原某个约束条件的资源是否有剩余？有剩余，说明原某个约束条件为非严格等式 无剩余，严格等式 结合改变后的约束条件和原最优解进行分析。,例8 约束条件变化的灵敏度分析,无

12、穷多最优解 第一个方程为严格等式（资源用尽），第二个方程资源有剩余,第二个约束条件变化后，变成了严格等式，最优解不变（！？）。增加一个约束条件后，若不满足，则应增加约束方程继续迭代（可将原最优表写成模型，再增加方程）。,五、增加新决策变量的灵敏度分析 增加新变量指单纯形表增加一列。在单纯形表迭代中，可以认为该决策变量原先没有被换入基（不管按最大法则是否该入基）。不影响可行性条件，只影响正则性条件（该新决策变量的检验数）,入基后，应注意其技术系数向量的变化！,六、技术系数A变化的灵敏度分析 总体原则就是将技术系数变化的某决策变量作为新变量进行处理。例如（注意两个表所表示的模型等价）：,第三章 运

13、输问题,运输问题是一类特殊的线性规划问题，特殊就在于：特殊的结构、特殊的求解方法。第一节 运输问题的数学模型及特征 一、问题的提出 设某种物资共有m个产地，n个销地，供应与需求的数量及运价如下表所示，问如何制定调运方案，使总运费最低（吨公里、时间）？,二、运输问题数学模型的特征：1.约束方程系数矩阵,矩阵有m+n行，mn列；有1和0组成。,2.系数矩阵的秩,再从模型的结构上看，前m行之和等于后n行之和，因此存在多余方程。也就是说有效方程个数为 m+n-1。即基变量的个数为 m+n-1。约束条件系数矩阵的秩为：,第二节 运输问题的初始调运方案 运输问题可以采用特定的方法进行求解表上作业法，它也是

14、一种单纯形法。因而需要首先确定初始基可行解。运输问题中，初始基可行解可以称为初始调运方案。确定初始调运方案的方法主要有：西北角法 最小元素法 差值法,一、西北角法 西北角法的思想就是从表的左上角开始制定初始调运方案，并以最大满足为前提。,得到一初始调运方案，总运费为：S=135,二、最小元素法 最小元素法的思想就是选择最小运价，优先供应。一般情况下，采用最小元素法得到的初始调运方案将优于西北角法。,三、差值法（伏格尔法）最小元素法尽管能够得到一个较好的初始调运方案，但也存在缺陷：在选择某个最小运价优先供应的同时，可能给下一个供应方造成更大的运费损失。如：,黄色方案：S1=41+16+34+31

15、0=52 其它方案：S2=46+32+11+34=43 显然，最小元素法不是一种最好的方法！,差值法认为若不能以最小运价供应，将以次小运价供应。最小与次小有一个差值，差值越大，说明增加运费就越多。因此，必须保证差值大的（最小元素）优先供应！,差值法步骤：计算表中各行各列最小与次小运价的差值；选择最大差值所在的行或列，选最小元素充分供应 划去满足的行或列，得到剩余表；重复，直到调运完成。,四、确定初始调运方案应注意的问题 由于运输问题的基变量的个数为 m+n-1，基变量的个数为m+n-1意为着调运表中有数字的“格”的个数为m+n-1，但在有些情况下，可能出现基变量的个数小于m+n-1。例如：,可

16、见，这是按照西北角法确定的初始调运方案。为什么会出现只有三个数字“格”的情况呢？这是由于在确定 x12时同时满足了行和列的需求，因而同时划去了行和列。一般地，若出现这种情况，也只划去一行或者一列，最后用“0”填补某一格，作为数字格，也就是视为零运量发生。,第三节 最优解的判别与调运方案的改进 一、最优调运方案的判别 运输问题是否也有类似的检验数呢？闭回路法 初始调运方案有m+n-1个基变量；有mn-(m+n-1)个非基变量。1.什么是闭回路法呢？以非基变量所在的格（空格）为起点，以某些基变量所在的格为转折点，最终必将返回起点，所构成的一个路线称为闭回路。闭回路是惟一的！每一个空格点都能构成一条

17、闭回路！,2.闭回路的作用是什么呢？找到闭回路以后，以空格点为始点，沿某一方向将所有奇数点的运价取正值；所有偶数点的运价取负值，其代数和为该空格点（非基变量）的检验数。每一个空格点（非基变量）都有一个检验数，也必须确定每一个空格点（非基变量）的检验数！例如：用最小元素法确定的初始调运方案如下表，确定该方案的检验数。,X11的闭回路：X11，X13，X23，X21，X11X12的闭回路：X12，X14，X34，X32，X12X22的闭回路：X22，X23，X13，X14，X34，X32，X22显然，每条闭回路中只有一个非基变量！,非基变量检验数的确定：,可见，检验数有正有负，如何判别呢？3.检验

18、数的经济意义是什么呢？检验数就是在每条闭回路上调整单位运量而使运费发生变化的增减值。,如在X11的闭回路上，调整 3个单位的运量，则运费变化多少呢？X11 03 X13 41 X21 30 X23 14 调整量最大能取多少？偶数点的最小运量 费用变化多少？（因其余不变，只考虑闭回路）S0=03+43+12+31=17 S1=33+13+42+01=20 S=S1-S0=33-33+32-31=3(3-3+2-1)=31,4.调运方案最优性的判别准则 当所有的检验数非负时，当前的调运方案一定是最优方案。为什么检验数非负是最优方案？原因在于目标函数是min 存在一种特殊情况，尽管存在某个检验数小于

19、零，但该方案也是最优方案。为什么呢？无运量的调整！,位势法 设运输问题的线性规划模型如下：,设,是对应于m+n个约束条件的对偶变量，则：,m+n个约束方程中，基变量只有m+n-1个，同时m+n个方程线性相关。不妨在某个方程中增加一个人工变量，这样，m+n个方程就不线性相关。假设人工变量加入第一个方程！则，每一个决策变量的系数列向量可以用单位向量表示。,根据单纯形原理，基变量的检验数为零，则：,利用上面的关系，可得到对偶变量的解，从而再利用下式确定非基变量的检验数。,例如：下述模型中各检验数的计算结果为：,由于存在负检验数，还未得到最优解，需要加以迭代。现在来比较一下两种方法之间的联系，可见结论

20、与闭回路法完全一致。例如：,二、调运方案的调整 当存在某检验数为负时，应对该检验数所对应的决策变量（运量）进行调整。调整量的大小是闭回路中各偶数点的最小运量，调整只是针对于该闭回路进行。,-1,再计算检验数：,三、几个应注意的问题 无穷多最优解 在已经得到最优解的前提下，如果某检验数为零，也可进行运量的调整，得到另一方案，与原方案具有相同的目标函数值。退化问题 若基变量的个数少于m+n-1，则为退化的情况。问题在于如何补“0”呢？能否在任一空格（非基变量）的位置补“0”呢？重要提示：补“0”后，基变量自身不能出现闭回路！,第四节 特殊运输问题 特殊运输问题包括供需不平衡问题及转运问题，这类问题

21、都需要转化成供需平衡问题来解决。一、供大于求 产量大于销售量，因而多余的产品在生产地储存。各生产地的仓库就相当于一个需求点（只是需求点不在一个地方）。因此，虚设一个需求点。其需要量为多少？，其运价为多少？需要量为产销量之差；运价为零！,二、供小于求 产量小于需要量，因而生产不足。因此，虚设一个生产产家。其产量为多少？，其运价为多少？需要量为产销量之差；运价为零！三、转运问题 若运输过程中要经过转运，转运的类型有两种：中转站集中产地物资，运往销地。产地与销地都能够中转。,例如：现有某种物资，产地A1,A2的产量分别为10,2单位，销地A3,A4,A5的销量分别为3,1,8单位。A2,A4可作中转

22、站，另A6为纯中转站，运价如下表，试确定最优调运方案。在研究中转问题时，注意；确定中转量；纯中转站可认为其产量和销量都为最大中转量；作为中转的产销地，其产量或者销量可以加上本地的中转量；注意运价问题。,不加括号的数，如“2”表示实际发生的运输；加方括号的数，如“1”表示经过中转的运输；加园括号的数，如“(10)”表示没有发生的运输；,第五节 运输问题的图上作业法 运输其本身就是在线路（铁路、公路）上完成的，将线路用图来描述，这样的运输地图就称为“调运网络”。一、调运网络 如下调运网络表示了某种供需状态。,注意：数字的意义（运量、长度）调运网络也可以用表格反映出来。,二、制定初始流向图 流向的定

23、义：从一地（点）运往另一地（点）流向的画法：箭线、位置、流量 流向的原则：就近供应，在最短的线路上优先供应,三、初始流向图的简化 简化的原则：流向不经过（跨越）点,四、流向图的改进最优流向图的判别准则 改进是针对是否存在对流及迂回 不存在对流及迂回是最优流向图的充分必要条件。对流：在流向图中，如果两个相邻点之间存在方向相反的流向，称为对流。对流的调整方法：保留流量较大的一条，流量调整为两条流向的流量之差。,回路：每个点只经过一次 外圈流向：画在回路外侧的流向 内圈流向：画在回路内侧的流向 迂回：在流向图中，如果一条回路的外圈（或内圈）流向长度之和大于该回路长度的一半，称为迂回。迂回的调整方法：假设为外圈迂回，且外圈流向中的最小流量为，调整是针对该回路的。所有内圈流量加；无流向的线上，补上内圈流量；所有外圈流量减。,