西安建筑科技大学-《816运筹学》-重难点解析讲义

《西安建筑科技大学-《816运筹学》-重难点解析讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西安建筑科技大学《８１６运筹学》重难点解析?第１讲第一章线性规划线性规划ｎ（１）（２）定理一设ＥＲ，若Ｅ中任意两点ｘ，ｘ的连线仍属于Ｅ，即（１）（２）ｘ∈Ｅ，ｘ∈Ｅ（１）（２）ｘ＝ａｘ＋（１－ａ）ｘ∈Ｅ，（０!ａ!１）则称Ｅ为凸集定理二若对于凸集Ｅ中的点ｘ，不存在Ｅ中两个相异的点使下式（１）（２）成立：ｘ＝ａｘ＋（１－ａ）ｘ，（０＜ａ＜１）则称ｘ为Ｅ的极点或顶点。定理三线性规划问题的可行解集ｎ（即可行域）Ｄ＝{Ｘ∑Ｐｊｘｊ＝ｂ，ｘｊ≥０}是凸集。ｊ＝１定理四线性规划几何理论基本定理ｎ若Ｄ＝{Ｘ∑Ｐｊｘｊ＝ｂ

2、，ｘｊ０}ｊ＝１则Ｘ是Ｄ的一个顶点的充分必要条件是Ｘ为线性规划的基本可行解。定理四若目标函数在ｋ个点处达到最优值（ｋ≥２），则在这些顶点的凸组合上也达到最优值。定理五若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。引理：可行域非空有界就肯定有最优解ＬＰ问题的各种解１．可行解：满足约束条件和非负条件的决策变量的一组取值。２．最优解：使目标函数达到最优值的可行解。３．基本解：设ＡＸ＝ｂ是含ｎ个决策变量、ｍ个约束条件的ＬＰ的约束方程组，Ｂ是ＬＰ问题的一个基，若令不—１—考试点（ｗｗｗ．

3、ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课程电话：４００６８８５３６５与Ｂ的列相应的ｎ－ｍ个分量（非基变量）都等于零，所得的方程组的解称为方程组ＡＸ＝ｂ关于基Ｂ的基本解，简称为ＬＰ的基本解。４．基本可行解（对应的基为可行基）：满足非负条件的基本解。５．基本最优解（对应的基为最优基）：使目标函数达到最优值的基本可行解。掌握各种解的关系解的情况线性规划线性规划的一般形式：—２—西安建筑科技大学《８１６运筹学》重难点解析ｍａｘ（ｍｉｎ）ｚ＝ｃ１ｘ１＋ｃ２ｘ２＋…＋ｃｎｘｎａ１１ｘ１＋ａ１２ｘ２＋…＋ａ１ｎｘｎ!（

4、或，＝）ｂ１ａ２１ｘ１＋ａ２２ｘ２＋…＋ａ２ｎｘｎ!（或，＝）ｂ２ｓ．ｔ．……………ａｍ１ｘ１＋ａｍ２ｘ２＋…＋ａｍｎｘｎ!（或，＝）ｂｍ线性规划的集合形式：ｎＭａｘ（Ｍｉｎ）Ｚ＝∑ｃｊｘｊｊ＝１ｎ∑ａｉｊｘｊ!（或＝，）ｂｉ（ｉ＝１，２，…，ｍ）ｓ．ｔ．{ｊ＝１ｘｊ０（ｊ＝１，２，…，ｎ）线性规划的向量形式：ｎＭａｘ（Ｍｉｎ）Ｚ＝∑ｃｊｘｊｊ＝１ｎ∑ｐｊｘｊ!（或＝，）ｂｓ．ｔ．{ｊ＝１ｘｊ０（ｊ＝１，２，…，ｎ）线性规划的矩阵形式：Ｍａｘ（Ｍｉｎ）Ｚ＝ＣＸＡＸ!（或＝，）ｂｓ．ｔ

5、．{Ｘ０标准形式有四个特点：（１）目标最大化；（２）约束为等式；（３）决策变量均非负；（４）右端项非负。—３—考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课程电话：４００６８８５３６５线性规划模型化为标准形式Ｘｊ≥０不变Ｘｊ≤０令Ｘｊ＝－Ｘｊ，则Ｘｊ≥０变量Ｘｊ≤０取值无约束令Ｘｊ＝－Ｘｊ，则Ｘｊ≥０ｂｉ≥０不变右端项ｂｉ＜０约束式两端同乘以”－１”约ａｉ１ｘ１＋…＋ａｉｎｘｎ＝ｂｉ不变束条件形式ａｉ１ｘ１＋…＋ａｉｎｘｎ≤ｂｉａｉ１ｘ１＋…＋ａｉｎｘｎ＋ｘｓｉ＝ｂｉａｉ１ｘ１＋…＋ａｉ

6、ｎｘｎ≥ｂｉａｉ１ｘ１＋…＋ａｉｎｘｎ－ｘｒｉ＝ｂｉｍａｘｚ＝ｃ１ｘ１＋…＋ｃｎｘｎ不变目标函数令ｚ＝－ｚ，化为求ｍａｘｚ＝－ｃ１ｘ１ｍｉｎｚ＝ｃ１ｘ１＋…＋ｃｎｘｎ－…－ｃｎｘｎｂｉｂｌθ＝ｍｉｎ｛ａ＞０｝＝（ｉ＝１，２，…，ｍ）单纯形法解题步骤：ａｉｋａｉｋｌｋ１．使ＬＰ模型右端项非负、约束符取“＝”、目标函数ｍａｘ（即标准化），并设法在约束系数中构造一个单位矩阵，令其为初始基，该基必为可行基，右端项即为基可行解。２．求检验数．若所有检验数均不大于０，找到最优解，计算结束；若存在大于０的检验数，找出最大

7、者σｋ，对应的变量ｘｋ为入基变量。３．若ａｌｋ均不大于０，则解无界，计算结束，否则找出最小比值：ｂｉｂｌθ＝ｍｉｎ{ａａｉｋ＞０}＝ａ（ｉ＝１，２，…，ｍ）ｉｋｌｋ对应的变量ｘｌ为出基变量。４．用入基变量替换出基变量，并通过行初等变换将基变成单位矩阵，右端项即为基可行解，转第２步。５．１大Ｍ法△没有单位矩阵，不符合构造初始基的条件，需加入人工变量。△人工变量最终必须等于０才能保持原问题性质不变。为保证人工变量为０，在目标函数中令其系数为（－Ｍ）（求最小值问题中，人工变量系数取Ｍ）—４—西安建筑科技大学《８１６运

8、筹学》重难点解析△Ｍ为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。△如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。５．２两阶段法第一阶段：构造目标函数只含人工变量的线性规划问题，求解后判断原线性规划问题是否有基本可行解若有，则进行第二阶段；第二阶段：将第一阶段的最终单纯形表所对