线性规划

出版时间：2009-2  出版社：清华大学出版社  作者：卢开澄,卢华明  页数：322  

前言

　　电子计算机的出现是20世纪的大事，它改变了我们这个世界的面貌。可以毫不夸张地说，它的影响遍及所有角落，几乎无处不感觉到它的存在。数学更不例外。严格地说，电子计算机本身就是近代数学的辉煌成就。将计算机与数学割裂开来，既不合理也不可能。组合学也就是在计算机科学蓬勃发展的刺激下而崛起的，从而成为近若干年来最活跃的数学分支。它研究的问题有的可追溯到Euler和Hamiltan等18世纪的数学家，但它成为新的分支还是近若干年的事。它从与计算机科学相结合中获得了广阔的发展空间，从而也为计算机科学奠定了理论基础。　　什么是计算机科学呢？有的学者将它定义为研究算法的一门学科。研究算法无疑是计算机科学的重要领域，也是本丛书的核心内容，贯穿始终。组合学家在20世纪70年代初建立的算法复杂性“NP理论”，至今仍然令无数计算机科学工作者与数学工作者为之折腰。　　计算机科学里的组合学内容十分广泛。本丛书涉及组合分析、图论、组合算法、近代密码学、组合优化、编码理论及算法复杂性等7部分。　　组合分析是算法的理论基础。组合分析之与组合算法犹如数学分析之与计算数学，众所周知，前者是后者的理论根基。　　图论原本是组合数学这个“家族”的主要成员，只因它已成长壮大，故自立门户独立出去。　　算法复杂性的NP理论是近三十年的一大成就。研究表明对于一类叫做NPC类的困难问题，至今都没找到有效算法，但它们难度相当，只要其中任何一个找到多项式解法，则全体都获得解决；或证明它们根本不存在有效办法。不论是前者还是后者都还看不见露到海平面上的桅杆塔，它吸引了众多的有志之士。密码学是其中十分引人人胜的分支。如若设计好的密码，对它的破译等价于某一NPC类困难问题，无疑这样的密码将是牢不可破的。　　在计算机网络深入普及的信息时代，信息本身就是时间，就是财富。信息的传输通过的是脆弱的公共信道，信息储存于“不设防”的计算机系统中，如何保护信息的安全使之不被窃取及不至于被篡改或破坏，已成为当今被普遍关注的重大问题。密码是有效而且可行的办法。在计算机网络的刺激下，近代密码学便在算法复杂性理论的基础上建立起来了。密码作为一种技术，自从人类有了战争，不久便有了它。但作为一门学科则是近二十多年的事。甚至于它已成为其他学科的基础。密码也从此走出“军营”，进入百姓家。

内容概要

　　全书共9章，分单纯形法和几个专题两部分。　　第一部分单纯形法，包括数学模型、单纯形法、改善的单纯形法、单纯形法的补充、对偶原理与对偶单纯形共5章。第二部分几个专题，包括运输问题及其他、内点法简介、目标规划、整数规划共4章。　　第一部分是基本内容；第二部分供各取所需选择内容，概括了线性规划的各个方面，算例丰富是其特点。本书可作为计算机系、数学系、经济管理学院本科生及研究生的教材。

书籍目录

第一部分 单纯形法第1章 数学模型31.1 引言31.2 问题的提出41.3 标准形式与矩阵表示81.4 几何解释9习题一12第2章 单纯形法152.1 凸集152.1.1 凸集概念152.1.2 可行解域与极方向概念162.2 凸多面体172.3 松弛变量182.3.1 松弛变量概念182.3.2 松弛变量的几何意义192.4 单纯形法的理论基础212.4.1 极值点的特性212.4.2 矩阵求逆222.4.3 可行解域无界的情况232.4.4 退化型举例252.5 单纯形法基础262.5.1 基本公式262.5.2 退出基的确定与进入基的选择272.5.3 举例292.6 单纯形法（续）312.6.1 基本定理312.6.2 退化型概念322.6.3 单纯形法步骤332.6.4 举例342.7 单纯形表格40习题二49第3章 改善的单纯形法523.1 数学准备523.2 改善的单纯形法543.2.1 改善的单纯形法的步骤543.2.2 举例553.3 改善的单纯形法表格603.3.1 表格的介绍603.3.2 复杂性分析63习题三64第4章 单纯形法的补充664.1 二阶段法664.2 大M法744.3 变量有上下界约束问题794.3.1 下界不为零的情况794.3.2 有上界的约束794.4 退化情形874.4.1 退化形问题874.4.2 出现循环举例与防止循环的Bland准则884.5 灵敏度分析904.5.1 C有变化914.5.2 右端项改变934.5.3 aij改变944.5.4 A的列向量改变954.5.5 A的行向量改变964.5.6 增加新变量984.5.7 增加新约束条件994.5.8 应用举例1014.5.9 参数规划1024.6 分解原理1044.6.1 分解算法1054.6.2 说明举例1064.7 无界域问题的分解算法1164.7.1 分解原理1164.7.2 说明举例116习题四121第5章 对偶原理与对偶单纯形法1265.1 对偶问题1265.1.1 对偶问题定义1265.1.2 对偶问题的意义1275.1.3 互为对偶1285.1.4 Ax=b的情形1295.1.5 其他类型1305.2 对偶性质1325.2.1 弱对偶性质1325.2.2 强对偶性质1335.2.3 min问题的对偶解法1335.3 影子价格1385.4 对偶单纯形法1405.4.1 基本公式1405.4.2 对偶单纯形法1415.4.3 举例1425.5 原偶单纯形法1465.5.1 问题的引入1465.5.2 原偶单纯形法之一1475.5.3 原偶单纯形法之二..1 48习题五149第二部分 几个专题*第6章 运输问题及其他1556.1 运输问题的数学模型1556.1.1 问题的提出1556.1.2 运输问题的特殊性1566.2 矩阵A的性质1576.3 运输问题的求解过程1586.3.1 求初始可行解的西北角法1586.3.2 最小元素法1606.3.3 图上作业法1616.4 ci-zi的计算，进入基的确定1626.5 退出基的确定1636.6 举例1656.7 任务安排问题1716.7.1 任务安排与运输问题1716.7.2 求解举例1726.8 任务安排的匈牙利算法1746.8.1 代价矩阵1746.8.2 Konig定理1766.8.3 标志数法1766.8.4 匈牙利算法1796.8.5 匹配算法1836.9 任务安排的分支定界法1846.1 0一般的任务安排问题1866.1 1运输网络1896.1 1.1 网络流1896.1 1.2 割切1906.1 1.3 Ford-Fulkerson定理1916.1 1.4 标号法1936.1 1.5 Edmonds-Karp修正算法1946.1 1.6 Dinic算法196习题六198第7章 内点法简介2007.1 Klee与Minty举例2007.2 数学准备2027.2.1 Lagrange乘数法2027.2.2 Kuhn-Tucker条件2037.2.3 垂直投影矩阵2047.2.4 最速下降法2057.2.5 牛顿法介绍2057.2.6 罚函数概念2067.2.7 中心路径2077.3 路径跟踪法2077.3.1 原偶对称型2077.3.2 KKT方程组及牛顿法2097.3.3 μ的确定，步长的确定2107.3.4 初始值和结束准则2117.3.5 算法步骤2117.3.6 收敛性的讨论2127.3.7 KKT方程组的重要归约2147.4 梯度法与仿射变换215第8章 目标规划2188.1 问题的提出2188.2 目标规划的几何解释2218.3 目标规划的单纯形表格2268.4 目标序列化方法2298.5 目标规划的灵敏度分析2348.6 应用举例245习题八248第9章 整数规划2529.1 问题的提出2529.2 整数规划的几何意义2569.3 0-1规划和DFS搜索法2589.3.1 穷举法2589.3.2 DFS搜索法2599.4 0-1规划的DFS搜索法2629.4.1 搜索策略2629.4.2 举例264*9.5 替代约束2679.5.1 Geoffrion替代约束2679.5.2 举例2699.6 分支定界法2759.6.1 对称型流动推销员问题2759.6.2 非对称型流动推销员问题2769.7 整数规划的分支定界解法2789.8 分支定界法在解混合规划上的应用2889.9 背包问题的分支定界解法2929.10 整数规划的割平面法2979.10.1 Gomory割平面方程2979.10.2 举例2989.11 割平面的选择3049.12　Martin割平面法3079.13 全整数割平面法3129.13.1 全整数单纯形表格3129.13.2 举例3149.14 混合规划的割平面法319习题九321