山东理工大学管理学院
3.1 线性规划及其数学模型 3.1.2 线性规划数学模型
（4）隐含的假设

比例性：决策变量变化引起目标的改变量与决策变量 改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其 它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , ci为确定值
山东理工大学管理学院
简介
历史悠久
理论成熟

与其它传统数学学科相比较, 线 性规划算是非常“年轻”却非常 “实用”的一门应用数学。 根据八十年代的一项调查, 在美 国《财富》杂志(Fortune) 名列前五 百名的大公司中, 百分八十五均曾应 用线性规划的方法来协助公司的营 运。 由此可见线性规划应用面的宽 广与普及。
1 7 x1 1 x 1 2 x 1 3x 4 x x x x 4 21 22 23 24 3 9 2 x 3 3x 4 x3 1 x 3 xij 0 , i 1 , 2 , j3 ;
x1 1 x 2 1 x 3 13 26 2 x 3 x1 2 x 2 35 x1 3 x 2 3 x 3 x x x 6 24 34 14 i 1 , 2 , j3 ; xij 0 ,
第三章 线性规划
（Linear Programming）




LP问题的数学模型 LP问题的图解法 LP问题的标准型及其解的概念 单纯形法 对偶理论 灵敏度分析 运输问题
山东理工大学管理学院
3.1 线性规划及其数学模型

3.1.1 线性规划简介 3.1.2 线性规划的数学模型 小结
某工厂计划生产 A、B 两种产品，生产这两种产品需要煤、电力和劳动力三种 资源。已知该厂可利用的煤有 360t，电力有 200kw，劳动日有 300 个，生产每千克 产品的资源消耗量和能获得的利润如下表所列。问该厂应生产 A，B 两种产品各多 少千克才能使总利润最大？
资源 消耗量/kg 资 源 煤 电力 劳动日 利润/(百元/kg) 产 品 A x1 9 4 3 7 B x2 4 5 10 12 资源限制量
应用广泛
在1950和1960年代, 线性规划的内容愈变愈 丰富, 更有许多成功的实用案例, 所以愈来愈受世 人瞩目。到了1975年, 瑞典皇家科学院决定将当 年的诺贝尔经济奖颁发给前面提到的L. V. Kantorovich 和T. C.Koopmans 以表彰他们在 “资源最佳分配理论”的贡献。由于这项最佳分 配是藉由线性规划模式来达成, 所以线性规划便 成了万众瞩目的焦点。

作业
山东理工大学管理学院
3.1 线性规划及其数学模型 3.1.1 线性规划简介

运筹学中应用最广泛的方法之一 运筹学的最基本的方法之一，网络规划，整数规划， 目标规划和多目标规划都是以线性规划为基础的

解决稀缺资源最优分配的有效方法，使付出的费用最 小或获得的收益最大
山东理工大学管理学院
简介
G. B. Dantzig教授 山东理工大学管理学院
简介
历史悠久

理论成熟
线性规划的理论基础绝不是一夕生成。早在 1826年左右法国的大数学家傅立叶便研究过如何 解决一组联立线性不等式的问题。这以后还有不 少的数学家做过相关的研究工作。到了1939年, W.Karush 在芝加哥大学的硕士论文更提出在有 限维空间里满足不等式约束的函数其最优化的条 件(optimality conditions)。在同一年里, 苏联的L. V. Kantorovich 更提出一些很特殊的线性规划模 式来做简单的生产计划。他甚至还有一套简化的 方法来求解呢!不幸的是Kantorovich的工作始终 未为苏联之外的世界所知, 一直到了Dantzig 建立 起完整的线性规划理论之后数十年方为世人所知。
2
5 6 8
12
14 8
求：最低成本的原料混合方案 山东理工大学管理学院
3.1 线性规划及其数学模型
解：设每单位添加剂中原料i的用量为xi (i =1,2,3,4)， f 为
总成本。
min f= 2x1 + 5x2 +6x3+8x4
4x1 + 6x2 + x3+2x4 12
x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,…,4)

历史悠久
理论成熟
应用广泛
根据一般的说法, 线性规划问题是由G. B. Dantzig教授在1947年前后孕育出来的。那个时 候他担任美国空军的数学顾问, 负责发展一套 机械式的方法来做兵力调遣, 人员训练, 以及后 勤补给这些计划方案。由于这类问题牵涉很广 也很复杂, 所以Dantzig 博士先考虑最简单的线 性结构, 将有关的函数一律简化成线性形式来 处理。其结果便在1948 年以“线性结构的规划” (Programming in Linear Structure) 的标题发 表。 至于“线性规划”这个名称, 则是另一位 名家T. C. Koopmans 和Dantzig 两人于1948年 夏天在美国加州圣塔摩尼加(Santa Monica) 海 滩散步时拟定的。在1947到1949两年间, 线性规 划里的一些重要观念, 包括最有名的“单纯形 法” (Simplex method), 都陆续见诸于世。而且 从1947年开始,T. C. Koopmans 便明确指出线性 规划可以做为传统经济分析的利器。
山东理工大学管理学院
简介
历史悠久

理论成熟
应用广泛
四年之后(亦即1979年), 线性规划再次成了 报章杂志的头条新闻。这次是因为一位苏联数 学家L. G. Khachian, 他利用N. Z. Shor,D. B. Yudin, 以及A. S. Nemirovskii的“椭球 法”(ellipsoid method) 概念印证出线性规划问题 可在多项式时间内求得解答。从纯理论的观点 而言,Khachian 的“椭球法”在最恶劣的情况下 所需要的计算量要比“单纯形法”增长的缓慢。 所以有希望用之解决超大型的线性规划问题, 包 括全球资源的最佳分配在内。这也就是华尔街 日报(Wall Street Journal) 将“椭球法” 的发现 列为头条新闻的重要原因。不幸的是理论归于 理论, 在实际计算上, “椭球法”的一般表现反倒 不如传统的“单纯形法”来得有效。于是这方 面的学者专家重新构想是否能设计出一套解法 无论在理论上和实际计算上均能超越“单纯形 法” ? 这个问题的答案到了1984 年由一位美国电 话电报公司贝尔实验室的印度裔科学家N. Karmarkar 揭晓。他设计出一项“内点法” 来 解线性规划问题, 不但理论上较“单纯形法”为 优, 而且经由实际验证适合解决超大型的问题。 从此之后,“内点法”的研究蔚为一时风潮, 不断 有推陈出新的结果。
山东理工大学管理学院
3.1 线性规划及其数学模型 3.1.2 线性规划数学模型 例3：（下料问题）某工厂制造一种机床，每台 机床需A，B，C三种不同长度的轴各一根，其毛 坯长度：A为2.9m，B为2.1m，C为1.5m，它们用 同一种圆钢来下料，每根圆钢长为7.4m。要造 100台机床，问如何下料最好？试建立其数学模 型（不考虑下料截口损耗）。
山东理工大学管理学院
3.1 线性规划及其数学模型 3.1.2 线性规划数学模型 （1）线性规划模型特点

决策变量： x1， … ， xn 决策人要考虑和控制的因素且非负 约束条件：线性等式或不等式

目标函数：ƒ=ƒ(x1 … xn) 线性式，求ƒ最大或最小值。
山东理工大学管理学院
3.1 线性规划及其数学模型 3.1.2 线性规划数学模型
使得总利润 f=7x 1 +12x 2 取得最大值。
山东理工大学管理学院
3.1 线性规划及其数学模型
例2：原料混合方案
利用四种原料生产由维生素A、B、C组成的一种添加剂，详细数据 见下表：
维生素 原料 A B Ｃ 每单位成本
1
2 3 4 每单位添 加剂中维生 素最低含量
4
6 1 2
1
1 7 5
0
2 1 3
360t 200kw 300 个
山东理工大学管理学院
3.1 线性规划及其数学模型
解: 设产品A, B的产量分别为x1 ， x2 ，f 为总利润，则该问 题可归结为，求一组变量x1 ， x2满足下列条件：
9 x1 4 x 2 360 4 x 5 x 200 1 2 3 x1 10 x 2 300 x1 , x 2 0
（由收量关系）
山东理工大学管理学院
3.1 线性规划及其数学模型
解：由题意，将各种可能的下料方案排列如下表：
各种下料方案一览表
方 案 A B C 总用料 料 头 圆 钢
1 2根 1根 7.3 0.1
2 1 2 7.1 0.3
3 1 1 1 6.5 0.9
4 1
5 3
6 2 2 7.2 0.2
7 1 3 6.6 0.8
山东理工大学管理学院
14
3.1 线性规划及其数学模型 3.1.2 线性规划数学模型
（3）线性规划数学模型的简化形式
n
max(min)f c j x j
j 1
n aij x j (, )bi , i 1, 2 , , m j 1 x 0 , j 1,2 , , n j
甲 乙 丙 收量/t
A 5 1 7 3
B 12 9 4 6
C 3 2 10 5
D 11 7 5 6
发量/t 7 4 9 20
山东理工大学管理学院
3.1 线性规划及其数学模型