运筹学单纯形法第部分.ppt

试比较：（1）（2）第31页,共40页，星期六，2024年，5月②（1）式目标要求改为极大化（或（2）式目标要求改为极小化）行不行？第二阶段：将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。问题讨论：①如何实施？需要重新建立初始单纯形表吗？第32页,共40页，星期六，2024年，5月实施中，在第一阶段最优表格中划去人工变量列，将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数)，继续迭代，直至求出最优解。②在大M法中，当人工变量出基后能否立即划去该人工变量所在的系数列？第33页,共40页，星期六，2024年，5月3、用表格单纯形法直接计算极小化线性规划时要修改哪些原则？（初始表？最优解判别？换入变量？换出变量？旋转运算？引入人工变量？）?最优性判别：所有检验数非负?换入变量的选择原则：（最小）负检验数所对应的变量进基，以保证目标函数值（较快）减小；?用大M法求解时，在目标函数中人工变量的前面添上一个很大的正系数M；第34页,共40页，星期六，2024年，5月六、迭代过程中可能出现的问题及处理方法1、为确定出基变量要计算比值，该比值=解答列元素/主元列元素。对于主元列的0元素或负元素是否也要计算比值？（此时解的可行性自然满足，不必计算；如果主元列元素全部为0元素或负元素，则最小比值失效，线性规划无“有限最优解”）第35页,共40页，星期六，2024年，5月2、现若干个相同的最小比值怎麽办？（说明出现了退化的基本可行解，即非0分量的个数小于约束方程的个数。按照“摄动原理”所得的规则，从相同比值对应的基变量中选下标最大的基变量作为换出变量可以避免出现“死循环”现象）3、选择进基变量时，同时有若干个正检验数，怎麽选？第36页,共40页，星期六，2024年，5月（最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基）课堂练习：直接按极小化问题求解下面的LP：第37页,共40页，星期六，2024年，5月CBXBcjxjb1200MX1X2X3X4X5M0X5X423-12-101100102/2_-Z-2M1+MM02-2M020X2X413-1/21-1/201/210010-Z-22010M-1?j第38页,共40页，星期六，2024年，5月由最优表得：最优解为X*=（0，1，0，3，0）T,相应的目标函数最优值为Zmin=2第39页,共40页，星期六，2024年，5月感谢大家观看第40页,共40页，星期六，2024年，5月关于运筹学单纯形法第部分先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；?线性规划限制条件都是“≥”或“=”类型的约束——第2页,共40页，星期六，2024年，5月等式约束左端引入人工变量的目的使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。（注意：用非基变量表示基变量的表达式）第3页,共40页，星期六，2024年，5月①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型的约束，怎麽办？构造“不完全的人造基”！讨论②为什麽初始可行基一定要选单位阵？b列正好就是基变量的取值，检验数行和b列交叉处元素也正好对应目标函数值，因此称b列为解答列第4页,共40页，星期六，2024年，5月（2）写出初始基本可行解——根据“用非基变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。2、建立判