第3章 线性规划与单纯形法

线性规划问题的解空间是一个凸多边形区域，其最优解一定可以在顶点上找到，而单纯形法实质上就是在相邻顶点间进行迭代、逐步求得顶点上最优解的过程。就像一个登山者在一座单峰的山上寻找最高点，其只需要沿着山脊线不断向高处攀爬，就一定能够到达山顶。

人们在生产生活中，经常遇到这类问题：如何使用有限的资源（人力、物力、财力或者时间等）达到一定的目标（具体目标视活动的不同而不同），很多时候还可能要求以最好的效果来达成目标。例如，工厂在一定的原材料约束下进行生产计划，要求获得最大的利润；在交通运输中要安排路线以使货物运输成本最低等。类似问题在军事领域也非常普遍，作战中武器编配方案的选定就是典型的例子，不同类型的武器对一定目标的杀伤效果不同，要合理配备作战单位的武器装备，使其达到最好的作战效果。

对于这样一类“资源使用优化”问题，1939年，苏联数学家L.B.康托洛维奇出版了《生产组织与计划的数学方法》，首次对这类问题进行总结，提出了线性规划问题。1947年，美国学者G.B.丹捷格博士首次提出了现在被广泛使用的线性规划模型及其单纯形求解算法。在这之后，有关理论方法快速发展，在实际应用中日益广泛与深入，取得了巨大成效。特别在电子计算机普通应用之后，计算机已能处理规模庞大的线性规划问题，使得线性规划的适用领域更为广泛，应用范围从解决技术方面的最优化设计拓展到工业、农业、商业、交通运输业、军事、经济计划和管理决策等各领域。