1、第一章线性规划理论及应用线性规划 Linear Programming（ LP）1n 引 言n 解决有限资源在有竞争的使用方向中如何进行最佳分配。n 线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自 1947年旦茨基（ G. B. Dantzig） 提出了一般线性规划问题求解的方法 单纯形法（ simplex method） 之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界 500家最大的企业中，有 85%的企业都曾使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。线性规划 Linear Progr
2、amming（ LP）2n 本章中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解方法。n 线性规划问题是什么样的一类问题呢？线性规划 Linear Programming（ LP）3线性规划 Linear Programming（ LP）1.线性规划模型 Linear Programming Model或 Linear Optimization Model用线性规划方法解决实际问题的第一步是建立能够完整描述和反映实际问题的线性规划模型。4线性规划 Linear Programming（ LP）通常建立 LP模型有以下几个步骤：1. 确定决策变量： 决策变量是模型要确
3、定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。2. 确定目标函数： 目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化（ max） 或最小化（ min）。3. 确定约束方程： 一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述。4. 变量取值限制： 一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即 Xj0， 但也存在例外。5线性规划 Linear Programming（ LP）n 例 1
4、某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下，试拟订使总收入最大的生产计划方案。资 源 单 耗 产 品资 源 甲 乙 资 源限量煤电油9 44 53 10 360200300单 位 产 品价格 7 126n 线性规划模型三要素：1.决策变量：需决策的量，即待求的未知数；2.目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；3.约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。7n 在本例中 决策变量：甲、乙产品的计划产量，记为 x1,x2； 目标函数：总收入，记为 z, 则z=7x1+12x2， 为体现对其追求极大化，在 z的前面冠以极大号 Max； 约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为8s.t. 9x1 + 4x2 3604x1 +5x2 2003x1 +10x2 300x1 ， x2 09线性规划模型的一个基本特点：目标和约束均为变量的 线性 表达式如果模型中出现如x12+2lnx2-1/x3的非线性表达式，则不属于线性规划。10
