线性代数与线性规划
学分: 6
线性代数是在 18 世纪初莱布尼兹、克拉默和高斯所采用的线性方程组解法的基础上发展起来的。凯莱在 19 世纪中期发展了矩阵代数理论，皮亚诺在 19 世纪末期定义了向量空间概念，从而为线性变换和向量空间理论在 20 世纪初期的诞生奠定了基础。线性代数不仅是理论数学和应用数学的基础，而且应用于从量子理论到谷歌搜索算法的广泛领域。本课程将详述向量空间理论在向量、几何学和线性代数领域的应用，尤其是在特征向量、特征多项式、内积及对角化方面的应用。
如果线性代数理论起源于线性方程组的解法，则线性规划理论起源于线性不等式组的解法尝试。后者促使人们基于表达为不等式的形式的约束条件优化线性函数概念。线性规划理论在二战期间由苏联数学家坎托罗维奇为制定生产规划而提出的，美国数学家丹茨格为解答复杂军事规划问题也提出了该理论，而库普曼斯将其应用于航运问题。该理论随后在二战后工业繁荣时代得以快速发展。
用于解答线性规划问题的第一个完整算法，即单纯形法，由丹茨格于 1947 年公布；同年，冯·诺依曼提出了对偶理论。1975 年，坎托罗维奇和库普曼斯因其贡献共同获得诺贝尔经济学奖；而丹茨格提出的单纯形法荣膺 20 世纪，继蒙特卡罗法之后，第二大最重要算法。
线性规划是一个极其有效的现代方法，可以应用在广泛的领域，不仅包括商业和经济学领域，而且还包括工程、交通、电信和规划等领域。在本课程结课时，学生应能够：
• 理解并运用线性代数和矩阵的基本概念，包括线性变换、特征向量、特征多项式
• 理解内积理论的基本概念，并运用该理论解答正交性和/或可对角性问题
• 解释线性规划的基本方法（图解法和单纯形法）
• 为各种管理问题构建多个线性规划模型，运用线性规划方法解答这些问题并解释计算得出的答案
• 解释何为单纯形法、何时无法用于解答某问题及如何解决这一情况
• 提出、证明并运用对偶理论的答案并做出相应解释
• 解释单纯形和线性规划的计算复杂性
Linear Algebra and Linear Programming 线性代数与线性规划
Credits: 6
Linear algebra grew out of the development of techniques at the start of the 18th century by Leibniz, Cramer and Gauss to solve systems of linear equations. Cayley developed matrix algebra in the middle of the 19th century, and Peano made the definition of a vector space at the end of the 19th century, resulting in a theory of linear transformations and vector spaces in the early 20th century. Linear algebra is not only fundamental to both pure and applied mathematics, but also has applications ranging from quantum theory to Google search algorithms. This module develops the theory of vector spaces introduced in Vectors, Geometry & Linear Algebra, covering eigenvectors, characteristic polynomials, inner products, and diagonalization. If linear algebra grew out of the solution of systems of linear equations, then linear programming grew out of attempts to solve systems of linear inequalities, allowing one to optimise linear functions subject to constraints expressed as inequalities. The theory was developed independently at the time of World War II by the Soviet mathematician Kantorovich, for production planning, and by Dantzig, to solve complex military planning problems. Koopmans applied it to shipping problems and the technique enjoyed rapid development in the postwar industrial boom.
The first complete algorithm to solve linear programming problems, called the simplex method, was published by Dantzig in 1947 and in the same year, von Neumann established the theory of duality. In 1975, Kantorovich and Koopmans shared the Nobel Prize in Economics for their work and Dantzig’s simplex method has been voted the second most important algorithm of the 20th century after the Monte Carlo method. Linear programming is a modern and immensely powerful technique that has numerous applications, not only in business and economics, but also in engineering, transportation, telecommunications, and planning.
By the end of this module, students should be able to:
• understand and use the basic concepts of linear algebra and matrices, including linear transformations, eigenvectors and the characteristic polynomial understand the basic theory of inner products and apply it to questions of orthogonality and/or diagonalizability
• explain the basic techniques of linear programming (graphical method and simplex method)
• construct linear programming models of a variety of managerial> problems and interpret the results obtained by applying the linear programming techniques to these problems
• explain why and when the simplex method fails to provide a solution and how to resolve such a situation
• present, prove and use the results of duality theory and interpret them
• explain the computational complexity of SIMPLEX and LP
