线性规划基本思路

基本思路：基于线性规划问题的标准形，先确定一初始基可行解X0,并由此开始在保证目标函数值不下降的情况下逐次施行从一个基可行解到另一个基可行解的转换。如此进行下去，直到取得最优解或判明问题无最优解为止。4）基本步骤:（1） 对一般线性规划问题标准化；（2） 确定一初始基可行解X0;（3） 若所有检验数ajV0（aj为的第］个分量），则X0是线性规划问题的最优解，停止计算；否则较4）（4） 若存在atv0所对应的系数列向量pt<O,则线性规划问题无最优解，停止计算；否则转（5）。（5）按最大检验数规则：jj0}jj0}kj确定进基变量xk和主列pk；再按最小比值规则:min{^^|a0} -i-

ia.ik a确定出基变量xl和主元alk。（6）以主元alk进行换基迭代得一新的基可行解xl,将xl记为x0返回到（3）。对偶关系对应表原问题（或对偶问题）对偶问题（或原问题）原问题（或对偶问题）对偶问题（或原问题）目标函数maxZ目标函数maxZ目标函数minW约束条件>0条件约束条件>0条件<0无限制m个变<量>n个约束约束条件右边常数项目标函数变量系数约束条件右边常数项目标函数变量系数目标函数变量系数约束条件右边常数项目标函数变量系数约束条件右边常数项表上作业法是单纯形法在求解运输问题时的一种简化方法，其本质是单纯形法。2）表上作业法的基本步骤：（1） 找一初始的调运方案（初始基可行解）；（必须满足：①产销平衡，②数字格（基变量）的个数为:产地数+销地数-1；常用最小元素法寻找）（2） 判断：计算表（产销平衡表）上空格（非基变量）的检验数，判断该方案是否为最优方案（最优解），若是最优方案，则停止计算;否则转（3）。（因运输问题为极小化问题，故最优性条件为：检验数a>0；常用位势法或闭合回路法计算检验数）（3） 调整：确定某个空格和某个数字格的转换，找出新的调运方案基可行解)转(2)常用闭合回路法进行调整(2)判断用位势法计算空格(非基变量)检验数：应用Cij=Ui+Vj计算数字格(基变量)的位势Ui、Vj，并令：U1=0；应用aij=Cij-(Ui+V计算空格非基变量)的检验数aij;若所有空格(非基变量)的检验数akl>0,则停止计算，输出最优方案；否则转(2。具体结果见下表3.6-5:(3)调整：(用闭合回路法)从某个检验数akl<0的空格(非基变量)出发；根据“遇见空格直行”的原则做闭合回路1;在闭合回路1的奇拐点中找出最小运量，记为a;将闭合回路L的每个奇拐点的运量都减去a,每个偶拐点的运量都加上a;得一新的调运方案；转⑵匈牙利算法1)适用范围：指派问题的标准型问题。指派问题的标准型问题必须满足以下3个条件：目标要求为极小化(min)；效益矩阵(目标系数矩阵)A=(aij)xn为方阵；A中所有元素均为非负常数(a>0,i,j=1,•凯n)基本步骤：效益矩阵的初始变换一一零元素的获取行变换：效益矩阵A0的每行减去该行的最小元素得新父攵益矩阵A1;列变换：对A1的每列减去该列的最小元素得新效益矩阵A2；（2） 最优性检验：用最少的直线覆盖A2所有的0元素，记其直线数为K,若k=n，则转（4）；否则转（3）。（3） 调整：在覆盖有直线的A2中，对线外的所有元素减去这些元素中的最小a；对线上交叉的元素加上a，得一新的效益矩阵，仍记为A2；转（2）。（4） 输出最优解：确定位于不同行不同列的0元素；将确定的位于不同行不同列的0元素对应的决策变量取1，其余决策变量取0，得最优解（方案）。三、分支定界法1、 适用范围：一般整数规划问题2、 基本思想：先求不含整数约束的规划问题（整数规划松弛问题）的最优解X。若X为整数解，则X*=X 为原整数规划问题的最优解。否则，若X中的xk=bk不是整数，则将原整数规划问题分别添加xk<[bk和