文档介绍：线性规划与单纯形方法
*
第一页，共126页
第一节 线性规划问题及数学模型
一、实例
二、线性规划问题（LP问题）的共同特征
三、两变量线性规划问题的图解法
四、线性规划问题的标准型
五、标准型LP问题解的概念
六、可行解、基解和基可行解举例
*
第二页，共126页
一、实例
例1 生产计划问题(书P8)
Step 1:明确问题，设定决策变量
设I、II两种产品的产量分别为x1, x2 。
Step 2: 确定约束条件
产品
I
II
资源限量
设备
1
2
8台时
原料A
4
0
16公斤
原料B
0
4
12公斤
利润
2
3
问应如何安排生产
使该厂获利最多？
*
第三页，共126页
说明：OBJ 表示Objective;
. 表示Subject to
Step 3: 给出目标函数
Step 4: 整理数学模型
*
第四页，共126页
例2 下料问题
现要做100套钢架，、。，问如何下料，使用的原料最少（余料最少或根数最少）？
分析：
最简单的做法是：，，100套则浪费材料90米。关键是要设计套裁方案，不能有遗漏。
*
第五页，共126页
解：设 x1, x2 , x3, x4 , x5分别代表五种不同的原料用量方案。
3
1
0
x5
0
2
1
x4
2
2
0
x3
1
0
2
x2
0
3
0
1
x1
余料
合计
方案
余料最少的LP模型：
*
第六页，共126页
根数最少的LP模型：
料头最省
根数最少
＝
解1: x1=30, x2=10, x4=50; 料头Z=16, 根数90。可以做100套钢架，无圆钢剩余。
与解1相同
≥
解2: x1=100, x3=50; 料头Z=10, 根数150。可以做100套钢架, 。
与解1相同
*
第七页，共126页
LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：
（1）当资源给定时，要求完成的任务最多；
（2）当任务给定时，要求为完成任务所消耗的资源最少。
若上述问题的目标﹑约束都能表达成变量的线性关系，则这类优化问题称LP问题。
LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。
*
第八页，共126页
目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。
每一个问题变量都用一组决策变量（x1, x2, …, xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负且连续的。
存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。
结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。
二、线性规划问题（LP问题）的共同特征
*
第九页，共126页
Max(Min) Z=c1x1+c2x2+…+cnxn (1)
a11x1+a12x2+…+a1nxn ≤ ( =, ≥) b1
a21x1+a22x2+…+a2nxn ≤ ( =, ≥) b2
. …… (2)
am1x1+am2x2+…+amnxn ≤ ( =, ≥) bm
xj≥0, j=1,2, …，n (3)
(1)—目标函数；(2)约束条件；(3)决策变量非负
n－变量个数； m－约束行数； cj－价值系数；
bi－右端项或限额系数； aij－技术系数；
xj—决策变量
线性规划模型的一般形式为：
*
第十页，共126页