第一章 离散最优化算法

《第一章 离散最优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章线性规划　　线性规划是运筹学的重要分枝之一，诞生于第二次世界大战期间。战后得到了迅速发展。它的应用范围极为广泛。从农业上的作物轮作计划到大规模的军事行动计划；从港口间的船艇运行路线到物流的分配。研究者们把这些似乎无关的问题，统一个到同一个数学框架——线性规划。G．B．Dantzig给出简洁求解方法——单纯形方法（Dantzig，G．B，1963）　　实际上，上个世纪三十年代中期，前苏联的数学家康特洛维奇已在生产组织和计划中，提出了一些数学方法。其中就含线性规划模型，并给出了其求解线性规划的一个方法，称之为解乘数法，尽管解乘数法在理论上和应用上都没有单纯形算法好，

2、但他是首先用线性规划去解决实际生产问题的人之一。他在1939年的著作《生产组织与计划中的数学方法》中，讲述了九个应用问题。　　由于高速的电子计算机的出现，线性规划的应用越来越广泛。人们发现对某些特殊的线性规划实例[16]，单纯形算法的迭代步数随变量个数的增加而以指数的速度增长。因此，从理论上看，单纯形算法所能解的线性规划，其变量个数不能太多。由此引起了对线性规划的算法研究的重视，自上世纪七十年代中期开始，出现了一系列新的方法。但这些算法都比较复杂，而且在变量个数不是太多的情况下，其计算的平均速度未必比单纯形算法好，所以本书对这些新的算法省略了。59　　本章重点地介绍了

3、单纯形算法、修正的单纯形算法、对偶单纯形算法和原始——对偶算法。实际上只要掌握了单纯形算法及其原理，其它几个算法就容易理解了。本章最后提到了椭球算法，其目的是说明线性规划问题是有多项式时间算法的。　　本章的内容与线性代数有关，对代数不太熟悉的读者，可以先复习一下线性代数的基本知识。　　1．1线性规划的基本概念　　要回答什么是线性规划，先看几个线性规划的例子：　　例1．1．1(运输问题)设某种产品有m个产地：A1，A2，…，Am，其产量分别为a1，a2，…，am。该产品有n个需求地：B1，B2，…，Bn，其需求量分别为b1，b2，…，bn。已知从第i个产地Ai运单位产品

4、到第j个需求地Bj的费用为Cij元。如何对产品进行调配，使在满足供需要求的情况下，使总的运费最小？这里我们假定，即供需平衡。　　这一问题可化为下述数学模型：(1．1—1)(1．1—2)(1．1—3)xij≥0，i＝1，2，…，m，j＝1，2，…，n(1．1—4)　　其中xij表示自产地Ai运往需求地Bj的产品数量；式59(1．1—1)表示总的运费要求取最小值；式(1．1—2)表示从产地Ai运出去的数量等于Ai产地的产量；式(1．1—3)表示需求地Bj的需求量，等于运往Bj的数量；式(1．1—4)表示运送的数量非负。　　这个模型表示在满足供需关系式求(1．1—2)～(1

5、．1—4)条件下，求一组{xij}，使式(1．1—1)达到最小，这就是例1．1．1所要求的调运方案。　　例1．1．2(资源分配)某工厂现有m种资源，第i种资源的数量为bi，i＝1，2，…，m。用这m种资源可以生产n种产品。已知生产单位第j种产品需第i种资源的数量为aij，i＝1，2，…，m，j＝1，2，…，n。从中可获利cj元。问题是在现有资源的条件下，各种产品各生产多少才可能使总的利润最大？　　若用xj表示第j种产品生产的数量，那么上述问题可表示为(1．1—5)，i＝1，2，…，m(1．1—6)xj≥0，j＝1，2，…，n(1．1—7)　　上述两个例子，虽然问题不同

6、，但其数学模型的实质是相同的，都是在一组线性等式和（或）不等式约束下，求一个线性函数的极值（最大或最小值），这就是所谓的线性规划。　　从外形上看，线性规划可以是各种各样的，我们把下述的线性规划称为标准形式：59，i＝1，2，…，mxj≥0，j＝1，2，…，n　　我们称xj为变量，为目标函数，而＝bi和xj≥0，i＝1，2，…，m；j＝1，2，…，n为约束条件。　　任何一个线性规划问题都可以化为标准形式。比如，若某个约束条件为，则可以引进一个非负变量yi，用和yi≥0代替；同样，对，可用和yi≥0代之。我们称这样的yi为松弛变量。若线性规划中某个变量xj不要求非负，则可

7、做一个代换，用代入目标函数和约束条件中，并增加约束和。若目标函数为求最小，则改为求最大并把目标函数的系数变号，即求改为。　　为表述简单，通常我们用向量形式表示：maxCTX(LP)AX＝bX≥0　　其中C＝（c1，c2，…，cn）Ｔ，b＝（b1，b2，…，bm）T，　　A＝（P1，P2，…，Pn）且P＝（a1j，a2j，…，amj）T　　x≥0表示x的每一分量xj≥0，j＝1，2，…，n。59　　这c，bi和aij通常取自于实数域；但在实际中经常取自于有理数域或整数集。　　有时为方便，把线性规划也写成下述形式：maxCTXxj≥0，j＝1，2，…，n