运筹学期末复习.docx

《运筹学期末复习.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学期末复习Lecture1绪论Lecture2图解法生产问题maxst.productionconstraints线性规划(linearprogramming,LP)·基本概念：o建模过程：理解问题、定义决策变量、定义目标函数、写出约束条件、求解o可行解、最优解、最优目标函数值o图解法：可行域、凸集、等值线·线性规划标准型·矩阵形式：maxcTxst.Ax=b,x≥0·标准型的转化：min转化为max、松弛量/剩余量（slack/surplus）、右端项变号、决策变量替换·求解LP：有最优解（必为顶点）、无界解

2、、无可行解图解法·可行域一定是凸集（可行域内任意两点的连线仍然在可行域内）·线性规划基本定理（针对标准型）：线性规划若有最优解,一定有最优解在顶点上。·图解法的敏感性分析o目标函数系数影响等值线的斜率o右端项影响可行域边界的截距Lecture3单纯形法·单纯形法的思路：从可行域的某一个顶点开始，判断此顶点是否是最优解，如不是，则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否为最优解，直到找到一个顶点为最优解，或者能判断出LP无最优解为止。·基本概念：o基本可行解：可行域的顶点o初始基本可行解：找到的第一个可行域顶点o基：m×n系

3、数矩阵A的m阶可逆子矩阵B，由m个线性无关的列向量组成o基向量：基B的一列，每一个基矩阵对应m个基向量o基变量：基向量系数对应的决策变量o如果找到一个基矩阵，令这个基矩阵的非基变量为零，然后求解这个基矩阵对应的基变量，即得到一个基本解，但是基本解可能存在负数，所以不一定是基本可行解·单纯形法的步骤oStep1初始可行基单位基矩阵，列向量前后顺序无关紧要如果找不到可以构造：加入人工变量，可行解中人工变量必须为零，有两种方法——大M法和两阶段法1）大M法：另人工变量在目标函数中的系数为-M，这里M为惩罚因子2）两阶段法：第一阶段解目标函数为人工变量之

4、和的最小值，如果最优值大于0，说明原规划不存在可行解，如果为0，则得到一个基本可行解，进入第二阶段，即以下步骤。oStep2最优性检验检验数σj：把所有的基变量用非基变量表示，然后得到目标函数中各决策变量的系数即为检验数。如果所有检验数非正,该基解是最优解，否则进入Step3。oStep3基变换1）入基变量：σj≥0的xj，如果有多个，一般选取σj最大的那个2）出基变量：把已确定的入基变量在各约束方程中的正的系数除所在约束方程的右端项，把其中最小比值所在约束方程中的原基变量确定为出基变量。注意：只考虑正的系数；如果出现多个最小变动比值，也有不同法

5、则3）旋转元：入基变量所在列×出基变量所在行的元素oStep4初等行变换把旋转元系数定为1，然后进行初等行变换得到新的单位基矩阵，重复Step2和Step3，直到所有的检验数非正，或者判断出存在无界解·四种结果o唯一最优解：非基变量的检验数都非正o无界解：检验数为正的入基变量对应的系数非正，找不到出基变量o无解：第一阶段就挂了o无穷多最优解：存在非基变量的检验数为0·退化问题o寻找出基变量时，存在多个最小比值，导致下一次迭代出现退化，某个基变量为0，再次迭代时得不到改进o出现退化时一般还是有解的，只是单纯形法的效率降低，但是有时候会出现死循环o解

6、决办法：Bland’srule（总是选下标最小的作为入基/出基变量）Lecture4敏感性分析目标函数系数的变动·问题：目标函数系数在什么范围内变动时，最优解不变？·百分百法则：o确定各目标函数系数的上下界o计算各系数的允许增加量和允许减少量o计算允许增加（减少）百分比o如果所有的百分比加起来不超过100%，则最优解不变o如果超过100%，那么无法确定最优解是否改变，只能重新计算o百分百法则既适用于目标函数系数的变动（最优解不变），也适用于约束条件右端项的变动（影子价格不变），但是不适用于两者同时变化的情况右端项的变动·影子价格：约束条件右端项增

7、加一个单位而使最优目标函数值增加的数量·当某约束条件中的松弛变量（或剩余变量）不为零时，这个约束条件的影子价格为零Lecture5运输问题·选课问题·运输问题Ø源(sources)与汇(destinations)[决策变量]Ø源：供应地，仅向汇供应Ø汇：需求地，仅从源得到供应Ø费用[目标函数]Ø运输费用是确定的，且与运输量成正比Ø总运输费用最小Ø能力[约束条件]Ø源的供应能力（供应量）Ø汇的接收能力（需求量）Ø供求情况Ø供求平衡Ø供大于求Ø供不应求见ExcelLecture5.xlsLecture6线性规划应用最小费用流：例子：见7-Distri

8、butionUnlimited-1.xls最小费用流解的性质：1）无可行流的两个独立原因：ØA）网络中没有足够的弧容量，使得供应点的流质