运筹学复习.pptx

运筹学一般问题运筹学一般问题同一问题求解方法的选择同一问题求解方法的选择 运筹学课程中很多问题可以有多种求解方法，在平时运筹学课程中很多问题可以有多种求解方法，在平时练习、作业和测验、考试时，请遵循以下准则：练习、作业和测验、考试时，请遵循以下准则：(1)严格采用题目指定的方法解题；严格采用题目指定的方法解题；(2)当题目没有指定方法时，应采用通用的方法；当题目没有指定方法时，应采用通用的方法；(3)有些问题当具体问题的规模很小时，用眼看心算可有些问题当具体问题的规模很小时，用眼看心算可能就能就 可得出最优解，但对于规模大的同类问题时就不可得出最优解，但对于规模大的同类问题时就不可行了，可行了，所以不属于通用的方法。因此采用眼看心算所以不属于通用的方法。因此采用眼看心算的方法是不允许的。的方法是不允许的。1.线性规划问题的标准形式线性规划问题的标准形式如何化标准型1.min Z=CX 1.min Z=CX 等价于等价于等价于等价于max Z=-CX(max Z=-CX(令令令令 Z=-Z)Z=-Z)；2.“2.“”约束：加入非负松驰变量；约束：加入非负松驰变量；约束：加入非负松驰变量；约束：加入非负松驰变量；3.“3.“”约束：约束：约束：约束：减去非负松弛变量；减去非负松弛变量；减去非负松弛变量；减去非负松弛变量；4.决策变量无约束时：决策变量无约束时：5.若决策变量，则令。6.若某个约束方程的右端项，则在约束方程两端乘以（-1），不等号改变方向，然后再将不等式转化为等式（加减非负松弛变量）2.如何求线性规划问题的基本解？求线性规划问题的基本解的步骤如下：n把所有约束条件不等式转化成方程；n设约束方程组中包含m个方程和n个变量，则分别找出个方阵，计算每个方阵的行列式，判断其是否满秩；n对于所有满秩方阵，分别以各满秩方阵列元素作为约束条件系数的m个变量作为基变量，而其他变量作为非基变量；n将所有非基变量取0值，则得到包含m个方程和m个变量的方程组，求解该方程组得出各基变量的值。n将基变量和非基变量的值放在一起，就得到该满秩方阵对应的基本解。标准型为：标准型为：x1+2x2 8 4x1 16 4x2 12 x1，x20max z=2 x1+3 x2+0 x3+0 x4+0 x5 x1+2x2+x3 =8 4x1 x4 =16 4x2+x 5 =12 x1,x2,x3,x4,x5 0例例 max z=2 x1+3 x2基基为基为：基变量为：基变量为：x3，x4，x5，非基变量为非基变量为 x1，x2。令令非基变量非基变量 x1=0，x2=0，基变量基变量 x3=8，x4=16，x5=12X=(0,0,8,16,12)T为基解为基解，且为基可行解且为基可行解3.用单纯形表求解LP问题例、用单纯形表求解例、用单纯形表求解LPLP问题问题解：化标准型21000检验数单纯形表结构 单纯形表单纯形表24/65/1C例:求解线性规划问题4.大 M 法解:l加入松弛变量进行标准化加入松弛变量进行标准化,加入人工加入人工变量构造初始可行基变量构造初始可行基.l用单纯形法求解用单纯形法求解l求解结果出现检验数非正求解结果出现检验数非正若基变量中含非零的人工变量，则无可行解；否则，有最优解。5.原问题与对偶问题的对应关系原问题与对偶问题的对应关系 原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）约束系数矩阵A约束系数矩阵转置A 推论：(1)max问题(原问题)任一可行解的目标值为min问题(对偶问题)目标值的一个下界；min问题(对偶问题)任一可行解的目标值为max问题(原问题)目标值的一个上界。(2)（无界性）若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原问题(对偶问题)为无可行解，对偶问题(原问题)或为无界解，或为无可行解。(3)若原问题（对偶问题）有可行解而其对偶问题(原问题)无可行解，则原问题（对偶问题）目标函数值无界。7.互补松弛性互补松弛性 在线性规划问题的最优解中，如果对应在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则某一约束条件的对偶变量值为非零，则该约束条件是严格等式；反之如果约束该约束条件是严格等式；反之如果约束条件取严格不等式，则其对应的对偶变条件取严格不等式，则其对应的对偶变量一定为零。量一定为零。例.已知线性规划问题8.用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：使对偶问题基变量可行,换进9.表上作业法求解运输问题求一个初始基本可行解是判断基本可行解是否最优结束不是求使目标得到改善的基本可行解n最小元素法nVogel法n闭回路法n对偶变量法