2014考研西安建筑科技大学-《816运筹学》强化精讲

《2014考研西安建筑科技大学-《816运筹学》强化精讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西安建筑科技大学《８１６运筹学》强化提高第１讲第一章线性规划（一）线性规划线性规划的一般形式：ｍａｘ（ｍｉｎ）Ｚ＝ｃ１ｘ１＋ｃ２ｘ２＋…＋ｃｎｘｎａ１１ｘ１＋ａ１２ｘ２＋…＋ａ１ｎｘｎ!（或，＝）ｂ１ａ２１ｘ１＋ａ２２ｘ２＋…＋ａ２ｎｘｎ!（或，＝）ｂ２ｓ．ｔ．……………ａｍ１ｘ１＋ａｍ２ｘ２＋…＋ａｍｎｘｎ!（或，＝）ｂｍ线性规划的向量形式：ｎｍａｘ（ｍｉｎ）Ｚ＝∑ｃｊｘｊｊ＝１ｎ∑ｐｊｘｊ!（或＝，）ｂｊ＝１ｓ．ｔ．{ｘｊ０（ｊ＝１，２，…，ｎ）线性规划的集合形式：ｎｍａｘ（ｍｉｎ）Ｚ＝∑ｃｊｘｊｊ＝１ｎ∑ａｉｊｘｊ!（或＝，）ｂｉ（ｉ＝１，２，…，ｍ）ｊ＝

2、１ｓ．ｔ．{ｘｊ０（ｊ＝１，２，…，ｎ）线性规划的矩阵形式：ｍａｘ（ｍｉｎ）Ｚ＝ＣＸＡＸ!（或＝，）ｂｓ．ｔ．{０Ｘ标准形式：目标函数最大化、约束条件为等式、决策变量均非负、右端项非负．决策变量为负值或自由变量：如果变量ｘｊ代表某产品当年计划数与上一年的计划数之差，显然ｘｊ的取值可能是正也可能为负。若ｘｊ≤０为负值，令ｘｉ＝－ｘ′ｉ（ｘ′ｊ０），使其变正；若ｘｊ为自由变量，令ｘｊ＝ｘ′ｊ－ｘ″ｊ，ｘ′ｊ０，ｘ″ｊ０，用两个非负变量之差来表示无符号限制的自由变量，ｘｊ的符号取决于ｘ′ｊ，ｘ″ｊ的大小。右端项为负值：—１—考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课程

3、电话：４００－６８８５－３６５右端项系数ｂｉ为负值时，即ｂｉ≤０，将等式约束两边同时乘以－１，得到－ａｉ１ｘ１－ａｉ２ｘ２－…－ａｉｎｘｎ＝－ｂｉＴ可行解满足所有约束条件的向量Ｘ＝（ｘ１，ｘ２，…，ｘｎ）可行域全部可行解的集合最优解使目标函数达到极值的可行解唯一最优解有唯一可行解使目标函数达到极值无穷多最优解有无穷多可行解使目标函数达到极值无界最优解存在可行解使目标函数值!Ｚ!≥Ｍ（Ｍ是任意大的正数）有界最优解存在可行解使目标函数值!Ｚ!≥Ｍ（Ｍ是任意大的正数）基矩阵Ｂ满秩系数矩阵Ａ（ｎ"ｍ）的任一个ｍｍ满秩子矩阵即由矩阵Ａ的任意ｍ列线性无!关的列向量构成的矩阵非基矩阵Ｎ即由矩阵Ａ去掉Ｂ

4、的ｍ列所余下的ｎ－ｍ列向量构成的矩阵Ｔ基向量基矩阵Ｂ的向量ｐｉ＝（ａ１ｉ，ａ２ｉ，…，ａｍｉ）ｉ＝１，２，…，ｍＴ非基向量非基矩阵Ｎ的向量ｐｊ＝（ａ１ｊ，ａ２ｊ，…，ａｍｊ）ｊ＝ｍ＋１，…ｎ－ｍＴ基变量与基向量ｐｉ对应的变量ｘｉｘＢ＝（ｘ１，ｘ２，…，ｘｍ）Ｔ非基变量与非基向量ｐｊ对应的变量ｘｊｘＮ＝（ｘｍ＋１，…，ｘｎ－ｍ）基本解在约束条件ＡＸ＝ｂ中不妨设基矩阵Ｂ是Ａ的前ｍ个列向量于是ＡＸ＝ｂ可改写为：－１Ｔ－１ＴＢｘＢ＋ＮｘＮ＝ｂ，然后令ｘＮ＝０，即可解得ｘＢ＝Ｂｂ，则Ｘ＝（ｘＢ，ｘＮ）＝（Ｂｂ，０），称为对应基矩阵Ｂ的基本解－１基本可行解若基本解中Ｂｂ≥０，则称其为对应Ｂ的基本可行

5、解凸集这样的点集合———其集合中任意两点的连线上的全部点都在该点集合内极点（顶点）凸集上不在两个不同点的连线上的点线性规划基本定理１线性规划所有可行解组成的集合Ｓ＝｛Ｘ｜ＡＸ＝ｂ，Ｘ≥０｝是凸集（另附凸集的定义）线性规划基本定理２Ｘ是线性规划问题的基本可行解的充要条件是Ｘ为凸集Ｓ＝｛Ｘ｜ＡＸ＝ｂ，Ｘ≥０｝的极点线性规划基本定理３给定线性规划问题，Ａ是秩为ｍ的ｍ×ｎ矩阵（ｉ）若线性规划问题存在可行解，则必存在基本可行解（ｉｉ）若线性规划问题存在有界最优解，则必存在有界最优基本可行解线性规划基本定理４线性规划一定在顶点达到最大值线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无界解、无

6、可行解。可行域为封闭有界区域时，可能存在唯一最优解，无穷多最优解两种情况；可行域为非封闭无界区域时，可能存在唯一最优解，无穷多最优解，无界解三种情况；可行域为空集时，没有可行解，原问题没有最优解。若线性规划存在最优解，则最优解或最优解之一肯定能够在可行域（凸集）的某个极点找到（所谓凸集是指集合中任何两点的连线上的点仍在集合中）。—２—西安建筑科技大学《８１６运筹学》强化提高例将ＬＰ模型转化为标准式ｍｉｎｚ＝３ｘ１＋５ｘ２－ｘ３－ｘ１＋ｘ２!９－２ｘ１＋ｘ２＋３ｘ３４ｓ．ｔ．３ｘ１＋２ｘ２－ｘ３－６ｘ１!０，ｘ２０，ｘ３无约束·单纯性法小结新加变建个数取值右端项等式或不

7、等式极大或极小量系数立模三个ｘｊ无型两个ｘｊ≥０ｘｊ≤０ｂｉ≥０ｂｉ＜０≤＝≥ｍａｘＺｍｉｎＺｘｓｘａ以上约束令ｘ＝约束图解ｊ加入令ｚ′条件加松求法、单纯ｘｊ′－ｘｊ″令ｘｊ′人工减去ｘｓ＝－Ｚ不处理不处理两端弛变不处理０－Ｍ解单纯形法ｘｊ′≥０＝－ｘｊ变量加入ｘａｍｉｎＺ＝同乘量ｘｓ形法ｘｊ″≥０ｘａ－ｍａｘＺ′以－１—３—考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课程电话：４００－６８８５－３６５第２讲第一章线性规划