《参数规划.ppt》由会员分享，可在线阅读，更多相关《参数规划.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第二节第二节 参参 数数 规规 划划 什麽是参数规划？什麽是参数规划？灵敏度分析的扩展灵敏度分析的扩展 两类单参数线性规划问题的求解两类单参数线性规划问题的求解约束方程右端常数项含有参数约束方程右端常数项含有参数价值系数含有参数价值系数含有参数 数学模型数学模型求解要求求解要求由于由于改变参数改变参数的值的值，将引起，将引起全体价值系数全体价值系数的变化，因此的变化，因此应应对一切实值对一切实值，求出求出所对应所对应的的最优解族最优解族和相应的和相应的目标函数最优值。目标函数最优值。1 1价价价价值值值值系系系系数数数数含含含含有有有有参参参参数数数数其中其中,C=(c,C=(c1 1，c
2、c2 2，c cn n）是给定的是给定的价值向价值向价值向价值向量量量量，是给定的是给定的变化向量变化向量变化向量变化向量，是未知的实值参数。是未知的实值参数。步骤步骤 对对的某个固定值的某个固定值（通常（通常取取=0=0）应应用单纯形法解出相应的线性规划。设用单纯形法解出相应的线性规划。设B B为为=0=0时的最优基，则时的最优基，则非基变量对非基变量对应的检验数应的检验数j j=c=cj j-C-CB BB B-1-1P Pj j ；令令从零开始从零开始变化到某一实数值变化到某一实数值，不妨仍用不妨仍用表示，则表示，则x xj j所对应的检所对应的检验数验数 令令令令确定参数规划得到确定参
3、数规划得到最优解最优解时，时，的范围的范围及相应的及相应的最优解族最优解族。相应的目标函数值相应的目标函数值 例例1-7 求解求解 解：解：解：解：这是价值系数含有单参数的线性规划问题。这是价值系数含有单参数的线性规划问题。这是价值系数含有单参数的线性规划问题。这是价值系数含有单参数的线性规划问题。令令令令=0=0，解解相相应应的的LP得得最最优优单单纯纯形形表表为为表表1，当当从从0变变化化到到某某一一实实值值时时，为为计计算算新新的的检检验验数数，在在原原单单纯纯形形表表上上增增加加“变变化化向向量量行行”和和“新新检检验验数数行行”得到得到扩充表扩充表扩充表扩充表为表为表2（称之为（称之
4、为基准表基准表基准表基准表）。）。CB XB cj xj b 2 3 1 0 0 x1 x2 x3 x4 x5 2 3 x1 x2 1 2 1 0 -1 4 -1 0 1 2 -1 1 -Z -8 0 0 -3 -5 -1 例例1-7表表1例例1-7 表表2 扩充表扩充表（基准表）（基准表）CB XB cj xj b 1 -1 1 0 0 2 3 1 0 0 x1 x2 x3 x4 x5 1-1 2 3 x1 x2 1 2 1 0 -1 4 -1 0 1 2 -1 1 -Z -8 0 0 -3 -5 -1 1 0 0 4 -5 2 表中表中,的计算公式与的计算公式与 的相同的相同,只需将只需将
5、cj 用用 代替，代替，CB用用 代替代替.由由 =可得：可得：=1-1*（-1）+（-1）*2=1+3=4=0-1*4+（-1）*（-1）=-5=0-1*（-1）+（-1）*1=2 由基准表得由基准表得 基本可行解基本可行解X（0）=（1,2,0,0,0）T 相应的目标函数值相应的目标函数值Z()=Z+=8-计算非基变量的检验数计算非基变量的检验数计算非基变量的检验数计算非基变量的检验数 令令 ()0，则则X（0）即即为为最最优优解解，解解相相应应的的不等式组以确定参数规划得最优解时不等式组以确定参数规划得最优解时的范围的范围:：3/43/4 -1-1 1/21/2 解此不等式组得解此不等式
6、组得 -11/2结果表明结果表明结果表明结果表明：当当当当 在实值区间在实值区间在实值区间在实值区间-1-1，1/21/2中变动时中变动时中变动时中变动时 参数规划的最优解是：参数规划的最优解是：X（0）=（1，2，0，0，0）T相应的目标函数最优值为相应的目标函数最优值为 Z()=8-当当变化超出上述范围时变化超出上述范围时,如如1/2时时，应应在在基基准准表表基基础础上上继继续续进进行行换换基基迭迭代代，变变量量x5进进基基，用用最最小小比比值值原原则则确确定定变变量量x2出出基基，迭代过程见例迭代过程见例1-7表表2，结果见表，结果见表3。例例1-7 表表2 扩充表扩充表（基准表）（基准
7、表）CB XB cj xj b 1 -1 1 0 0 2 3 1 0 0 x1 x2 x3 x4 x5 1-1 2 3 x1 x2 1 2 1 0 -1 4 -1 0 1 2 -1 1 -Z -8 0 0 -3 -5 -1 1 0 0 4 -5 2 -例例1-7表表3 CB XB cj xj b 1 -1 1 0 0 2 3 1 0 0 x1 x2 x3 x4 x5 1 0 2 0 x1 x5 3 2 1 1 1 3 0 0 1 2 -1 1 -Z -6 0 1 -1 -6 0 -3 0 -2 0 -3 0 1/21/2 -2-21/21/2 因此，因此，当当1/2，)时，该参数规划有时，该参
8、数规划有最优解最优解 X*=（3，0，0，0，2）T相应的目标函数最优值为相应的目标函数最优值为 Z（）=Z+=6+3 当当-1时时 以以x4作为进基变量作为进基变量，用，用原则确定原则确定x1为为换出变量换出变量，迭代结果见例，迭代结果见例1-7表表4。其中，检验数行的计算如下其中，检验数行的计算如下：-1-1 所以所以,当当(-，-1)时时,该参数规划有最优解该参数规划有最优解 X*=（0，9/4，0，1/4，0）T，相应的目标函数最优值为相应的目标函数最优值为 Z()=Z+=27/4 9/4。例例1-7表表4 CB XB cj xj b 1 -1 1 0 0 2 3 1 0 0 x1 x
9、2 x3 x4 x5 0 -1 0 3 x4 x2 1/4 9/4 1/4 0 -1/4 1 -1/4 1/4 1 7/4 0 3/4 -Z -27/4 5/4 0 -17/4 0 -9/4 9/4 5/4 0 11/4 0 3/4 综上，当综上，当取遍一切实值时，取遍一切实值时，与与Z的关系可的关系可以由下图表示：以由下图表示：9-7-5-3-1-1 0 1/2 1 Z（）斜率斜率=-9/4 斜率斜率=3(-1,9)(1,9)斜率斜率=-1 该参数规划的该参数规划的 最优解族：最优解族：相应的相应的 目标函数最优值：目标函数最优值：-1 -1 例例例例1-71-7表表表表4 4 例例例例1-
10、71-7表表表表3 1/23 1/2 求解过程总结图求解过程总结图 扩充表（基准表）扩充表（基准表）-11/2X5进基，进基，x2出基出基X4进基，进基，x1出基出基 1/2为给定的变化向量，为给定的变化向量，其中其中:b=(bb=(b1 1，b b2 2，b bm m)T T为给定的右端系数向量为给定的右端系数向量，2约约束束方方程程右右端端常常数数项项含含有有参参数数是未知的实值参数是未知的实值参数。当改变当改变 的取值时，约束方程的右端系的取值时，约束方程的右端系数将同时发生变化，因此，数将同时发生变化，因此，应对一切实应对一切实值值 求出所对应的最优解族和相应的最求出所对应的最优解族和
11、相应的最优目标函数值优目标函数值步骤步骤从从0 0变到某一实值变到某一实值(不妨仍用不妨仍用表示表示)，X XB B随之变成随之变成:对对的某个固定值的某个固定值,通常取通常取=0=0，设，设B B是是最优基最优基,则相应的最优解为则相应的最优解为 X XB B=B=B-1-1b b，X XN N=,X=,X=（X XB B，X XN N）T T 的变化不影响检验数，故最优单纯形的变化不影响检验数，故最优单纯形表中，所有检验数仍然保持非正，因此，只表中，所有检验数仍然保持非正，因此，只要要 则，则，基基B B仍然保持为最优基。仍然保持为最优基。讨讨 论论 的变化会影响什麽？的变化会影响什麽？（
12、会影响检验数吗？会影响解答列吗？）（会影响检验数吗？会影响解答列吗？）根据根据 确定参数确定参数的变化范围的变化范围计算出当计算出当B B保持为最优基时保持为最优基时相应的最优解。相应的最优解。然后由式然后由式例例1-8 求解求解 本例中，右端系数变化向量本例中，右端系数变化向量本例中，右端系数变化向量本例中，右端系数变化向量 =(1,-1)=(1,-1)T T 令令=0，求解相应的线性规划求解相应的线性规划，得最优单纯形表见例得最优单纯形表见例1-8表表1：CB XB cj xj b 2 3 1 0 0 x1 x2 x3 x4 x5 2 3 x1 x2 1 2 1 0 -1 4 -1 0 1
13、 2 -1 1 -Z -8 0 0 -3 -5 -1例例1-8表表1 当参数当参数从从0变到某一实值时，变到某一实值时，约束方程右端常数同时发生变约束方程右端常数同时发生变化化在例在例1-8表表1基础上增加一列变化向量得基础上增加一列变化向量得扩充表扩充表 例例1-8表表2（基准表基准表）：其中其中 列数字列数字?CB XB cj b xj 2 3 1 0 0 x1 x2 x3 x4 x5 2 3 x1 x2 1 2 5 -2 1 0 -1 4 -1 0 1 2 -1 1 -Z -8 0 0 -3 -5 -1 -4 例例1-8表表2 扩充表扩充表（基准表基准表）令令 以确定以确定的变化范围：的
14、变化范围：由由 ,只要只要-1/5，1，原来的原来的基变量保持不变基变量保持不变，仍为，仍为x1,x2；但但 最优解的取值随最优解的取值随的变化有所变化的变化有所变化 新的最优解为；新的最优解为；X*=(1+5,2-2,0,0,0）T 相应的目标函数值为：相应的目标函数值为：若参数若参数的变化超出了上述范围的变化超出了上述范围,原始问题原始问题的可行性被破坏的可行性被破坏,但但仍保持对偶可行性仍保持对偶可行性 为什麽？为什麽？用用对偶单纯形法对偶单纯形法继续进行换基迭代，继续进行换基迭代，以确定新的最优解以确定新的最优解 情况一情况一 1,解答列中第二个分量解答列中第二个分量 2-23时时，解
15、答列中第一个分量小于零，解答列中第一个分量小于零，故可考虑故可考虑x1出基出基。但此时但此时主元行（第一行）全部为非负元素主元行（第一行）全部为非负元素，最小比值原则失效。最小比值原则失效。第一个约束条件表现为矛盾方程！第一个约束条件表现为矛盾方程！为什麽？为什麽？因此因此原问题不可行，原问题不可行，也就也就不存在最优解。不存在最优解。类似地，可以考虑类似地，可以考虑情况二情况二，即即-1/5时时的情况的情况 整个求解过程图示整个求解过程图示 扩充表（基准表）扩充表（基准表）扩充表（基准表）扩充表（基准表）-1/51-1/51 11-1/5 3 3-1-1x2出基出基,x4进基进基x1出基出基,x5进基进基综上综上:该问题的该问题的最优解为最优解为:相应的相应的目标函数最优值为目标函数最优值为:-1 -1/5 0 1 2 3 Z*=12 Z*=7.2 与与Z的关系示意图的关系示意图 无解无解无解无解1、两类单参数线性规划的求解思路是什、两类单参数线性规划的求解思路是什麽？麽？思考题思考题（1）