运筹学方法总结.docx

线性规划1.问题背景：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题2.求解方法： a.单纯形法：适用的问题：约束条件全部为≤，右边常数全部为非负，对目标函数的系数没有要求。min z=3x1-2x2s.t. x1+2x2≤12 2x1+ x2≤18 x1,x2≥0求解步骤：STEP 0 将线性规划问题标准化STEP 1 是否有明显的初始基础可行解，如果有，转STEP 3，否则，转STEP 2。STEP 2 构造辅助问题，用两阶段法求解辅助问题。如果辅助问题最优解的目标函数值大于0，原问题无可行解，算法终止。否则转STEP 3。STEP 3 写出单纯形表，将基变量在约束条件中的系数消为单位矩阵，将基变量在目标函数中的系数消为0。转STEP 4。STEP 4 如果所有非基变量的检验数全为负数或0，则已获得最优解，算法终止。否则， 选择检验数为正数并且绝对值最大的非基变量为进基变量。转STEP 5。STEP 5 如果进基变量在约束条件中的系数全为负数或0，目标函数无界，算法终止。否则根据右边常数和正的系数的最小比值，确定离基变量。转STEP 6。STEP 6 进基变量列和离基变量行交叉的元素称为主元。对单纯形表进行行变换，将主元变为1，将主元所在列的其他元素变为0。转STEP 4。b.对偶单纯形法：适用的问题:约束条件中至少有一个是≥，相应的右边常数为非负，目标函数系数全部为非负。min z=3x1+2x2s.t. x1+2x2≥12 2x1+ x2≤18 x1,x2≥0求解步骤：步骤1 确定原问题（L）的初始基B，使所有检验数 ，即是对偶可行解，建立初始单纯形表。步骤2 检查基变量的取值，若≥0，则已得最优解，计算停；否则求确定单纯形表第L行对应的基变量为旋出变量。 步骤3 若所有,则原问题无可行解，计算停；否则，计算确定对应的为旋入变量。 步骤4 以为主元作（L，K）旋转变换，得新的单纯形表，转步骤2。可以证明，按上述方法进行迭代，所得解始终是对偶可行解。运输问题1.问题背景：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。2.求解方法:a. 表上作业法:方法描述：表上作业法是一种求解运输问题的特殊的方法，其实质是单纯形法，它针对运输问题变量多,结构独特的情况，大大简化了计算过程的求解方法求解步骤：找出初始基本可行解2. 求各非基变量的检验数，即在表上计算除了上述的m+n-1个数字格以外的空格的检验数判别是否达到最优解,如已是最优解，则停止计算,否则转到下一步。在运输问题中都存在最优解。3. 确定入基变量与出基变量，找出新的基本可行解。在表上用闭回路法调整。4. 重复2、3直至得到最优解。目标规划问题背景：目标规划（Goal programming） 目标规划是线性规划的一种特殊应用，能够处理单个主目标与多个目标并存，以及多个主目标与多个次目标并存的问题。求解方法：约束法：方法描述：在多个目标函数中选择一个主要目标作为 基本思想： 基本思想 目标函数，其它目标处理为适当的约束。 目标函数，其它目标处理为适当的约束。求解步骤：min f1 ( x) ~ ? ( P)?s.t. g i ( x) ≥ 0, i = 1,2, L, m ? f j ( x) ≤ f j ( x ( 0 ) ), j = 2,3, L, p 第一步： （1）对 j = 1,2, L, p，min f j ( x) (VPj )? ?s.t. x ∈ S，求解单目标问题第二步：选择整数r1，确定0 jt，f j0的r个不同阀值第三步：对 t = 0,1,L, r ? 1 ，分别求解问题：min f k ( x) ? ( Pt j )?s.t. g i ( x) ≥ 0, i = 1,2, L, m ? f j ( x) ? f jt j ≤ 0, j = 1, L, k ? 1, k + 1,L, p ?) 各目标函数 f ( j ≠ k ) 可对应不同的 t (t = 0,1,L, r ? 1（共 有 r p ?1 个约束问题）。求解后可得到(VP)的一有 效解集合，是(VP)有效解集合