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

第二章 对偶问题及灵敏度分析 四、确定初始调运方案应注意的问题 由于运输问题的基变量的个数为 m+n-1，基变量的个数为m+n-1意为着调运表中有数字的“格”的个数为m+n-1，但在有些情况下，可能出现基变量的个数小于m+n-1。例如： 3 4 4 3 9 (3) 10 2 B 8 4 6 (4) 1 (4) A Ⅲ Ⅱ Ⅰ 可见，这是按照西北角法确定的初始调运方案。为什么会出现只有三个数字“格” 的情况呢？这是由于在确定 x12时同时满足了行和列的需求，因而同时划去了行和列。 一般地，若出现这种情况，也只划去一行或者一列，最后用“0”填补某一格，作为数字格，也就是视为零运量发生。 第三节 最优解的判别与调运方案的改进 一、最优调运方案的判别 运输问题是否也有类似的检验数呢？ ㈠闭回路法 初始调运方案有m+n-1个基变量； 有m×n-(m+n-1)个非基变量。 1.什么是闭回路法呢？ 以非基变量所在的格（空格）为起点，以某些基变量所在的格为转折点，最终必将返回起点，所构成的一个路线称为闭回路。 闭回路是惟一的！每一个空格点都能构成一条闭回路！ 2.闭回路的作用是什么呢？ 找到闭回路以后，以空格点为始点，沿某一方向将所有奇数点的运价取正值；所有偶数点的运价取负值，其代数和为该空格点（非基变量）的检验数。 每一个空格点（非基变量）都有一个检验数，也必须确定每一个空格点（非基变量）的检验数！ 例如：用最小元素法确定的初始调运方案如下表，确定该方案的检验数。 6 5 6 3 销量 9 5 3 10 4 6 7 C 4 8 2 1 9 1 3 B 7 10 3 3 4 11 3 A 产量 Ⅳ Ⅲ Ⅱ Ⅰ 第五节 对偶单纯形法 重要概念：对偶单纯形法不是对对偶问题用单纯形法进行求解。 重要回忆： “ 可见，松弛变量检验数的反号正好对应对偶问题的一个基解。若B为最优基，则松弛变量检验数的反号为对偶问题的最优解 ” 重要过程：［在单纯形表迭代过程中］ 任一表——原问题的基可行解，对偶问题的基解 最终表——原问题的基可行解，对偶问题的基可行解 重要思想： 若始终保持其对偶问题是基可行解，让原问题从基解（非可行解）向基可行解迭代。 定义：若原问题的一个基解对应的检验数满足 则称此基解为原问题的正则解。 根据正则解的定义，重新构造单纯形表。 注意： ①构造原问题单纯形表，而不是对偶问题单纯形表； ②检验数必须小于等于零，常数项b不一定非负； ③迭代过程中，原问题是基本解，但对偶问题是可行的； ④迭代的目的，在检验数保持小于等于零的情况下，使常数项b≥０ 步骤： ①选定一个基Ｂ，若满足正则解的要求，得到初始单纯形表； ②若b≥０，则得到最优解，否则转入下一步； ③确定换出变量： ④确定换入变量： ⑤确定旋转元素（主元），迭代得到新的正则解，返回②。 例7 求解下列线性规划问题 分析：用单纯形法还是用对偶单纯形法求解？ 先看单纯形法的典式 若按正则解的要求，其模型为： 0 0 0 -1 -2 -3 0 -Z’ 0 0 1 0 1 0 1 0 0 -1 1 1 -1 0 -1 -1 -1 0 -6 -4 -3 X4 X5 X6 X6 X5 X4 X3 X2 X1 b XB 0 0 0 -1 -2 -3 0 0 0 -1 -2 -3 0 -Z’ 0 0 1 0 1 0 -1 1 1 1 0 0 1 -1 -2 1 -2 -1 6 -10 -9 X3 X5 X6 0 0 -1 0 -1 -2 6 -Z’ 0 0 1 0 1 0 1 0 0 -1 1 1 -1 0 -1 -1 -1 0 -6 -4 -3 X4 X5 X6 X6 X5 X4 X3 X2 X1 b XB 0 0 0 -1 -2 -3 -2 -3 0 -6 0 0 18 -Z’ -1 0 -1 -1 -1 0 1 0 0 -3 -1 -1 0 0 1 0 1 0 1 4 3 X4 X1 X2 X6 X5 X4 X3 X2 X1 b XB 则最终单纯形表为： …… 得到最优解为： 第六节 线性规划问题的灵敏度