第一章 线性规划 LINEAR PROGRAMMING
本章的主要内容
• 一般线性规划问题的数学模型 • 图解法 • 单纯形法原理 • 单纯形法的计算步骤 • 单纯形法的进一步讨论 • 数据包络分析
School of Management Harbin Institute of Technology 2
线性规划问题的数学模型
School of Management Harbin Institute of Technology 12
线性规划数学模型假设
（1）比例性 （2）可叠加性
（3）可分性
（4）确定性
School of Management Harbin Institute of Technology 13
线性规划问题的数学模型
• 标准形式的转换
–目标函数的转换 –无约束决策变量的转换 –约束方程的转换
• 松弛变量 • 剩余变量
–非正决策变量的转换
School of Management Harbin Institute of Technology 10
线性规划问题的数学模型
School of Management Harbin Institute of Technology 11
构建线性规划数学模型
例2：设有下面四个投资机会： 甲：在三年内，投资人应在每年年初投资，每年每元投 资可获利0.2元，每年取息后可重新将本息用于投资。 乙：在三年内，投资人应在第一年年初投资，每两年每 元投资可获利0.5元，两年后取息，取息后可重新将本息用 于投资。这种投资最多不得超过20,000元。 丙：在三年内，投资人应在第二年年初投资，两年后每 元投资可获利0.6元。这种投资最多不得超过15,000元。 丁：在三年内，投资人应在第三年年初投资，一年后每 元投资可获利0.4元。这种投资最多不得超过10,000元。 假定在这三年为一期的投资中，每期的开始有30,000元 资金可供使用，问：采取怎样的投资计划，才能在第三年 年底获得最大收益？
School of Management Harbin Institute of Technology 3
线性规划问题的数学模型
School of Management Harbin Institute of Technology 4
线性规划问题的数学模型
• 例子1.2 某企业计划生产甲，乙两种产品。这两 种产品需要在A，B，C三种不同的设备上进行 加工。按工艺需求，加工各种产品所需每种设 备的单位工时如下表所示，问如何安排生产计 划，使企业的总利润最大？
A 甲 乙 2 2 12 B 4 0 16 C 0 5 15 2 3
School of Management Harbin Institute of Technology 5
线性规划问题的数学模型
School of Management Harbin Institute of Technology 6
构建线性规划数学模型
例1：某工厂在生产过程中需要使用浓度为80% 的硫酸100 吨，而市面上只有浓度为30%，45% ，73%，85%，92%的硫酸出售， 每吨的价格
分别为400、700、1400、1900和2500元。 问：
采用怎样的购买方案，才能使所需总费用最小？
School of Management Harbin Institute of Technology 15
2
Ⅲ
Ⅳ
1Ⅴຫໍສະໝຸດ 22 7.1 0.3
1
1.5米
合 计 (米 ) 料 头 (米 )
3 7.4
0
1 7.3
0.1
2 7.2
0.2
3 6.6
0.8
School of Management Harbin Institute of Technology 17
构建线性规划数学模型
思考题：
目标函数是否可以选取为 min z'=x1+x2+x3+x4+x5 ，为什么？
School of Management Harbin Institute of Technology 16
构建线性规划数学模型
例3：合理下料问题：
要制作100套钢筋架子，每套含2.9米、2.1米、1.5米的 钢筋各一根。已知原料长7.4米，问：如何下料，使用料最 省？
长度
2.9米 2.1米
Ⅰ
1
Ⅱ
构建线性规划数学模型
（1）分析问题：确定决策内容、要实 现的目标以及所受到的限制条件。 （2）具体构造模型：选择合适的决策 变量、确定目标函数的表达式、约 束条件的表达式，分析各变量取值 的符号限制。
School of Management Harbin Institute of Technology 14
线性规划问题的数学模型
• 线性规划的数学模型由以下三个要素
–决策变量 decision variable –目标函数 objective function –约束条件 constrains
• 线性规划问题的辨别
–目标函数是多个决策变量的线性函数，取最 大值或最小值 –约束条件是一组多个决策变量的线性不等式 或等式
School of Management Harbin Institute of Technology 7
线性规划问题的数学模型
School of Management Harbin Institute of Technology 8
线性规划问题的数学模型
School of Management Harbin Institute of Technology 9
School of Management Harbin Institute of Technology 18
构建线性规划数学模型
例4：有A、B两种产品，都需要经过前、后两到化学反应过程。每种产品需 要的反应时间及其可供使用的总时间如表示。
每生产一个单位产品B的同时，会产生2个单位的副产品C，且不需 外加任何费用。副产品C的一部分可以出售盈利，其余的只能加以销毁。
线性规划问题的数学模型
• 规划问题
–生产和经营管理中经常提出如何合理安排， 使人力、物力等资源得到充分利用，获得最大 的效益，这就是规划问题
• 线性规划通常解决以下两类问题
–当任务和目标确定后，如何统筹兼顾，合理 安排，用最少的资源去完成确定的任务和目标 –在一定的资源限制下，如何组织安排生产获 得最好的经济效益