文档介绍：关于线性规划
第一页，本课件共有101页
*
决策变量：x1, ..., xn表示要寻求的方案，每一组值就是一个方案；
约束条件：线性等式或不等式
目标函数：Z=ƒ(x1 … xn) 线性式，求Z极大或极小
线性规划模型特点
第二页，本课件共有101页
*
一般式
min z=c1x1+ c2x2+…+cnxn
ai1x1+ ai2x2+…+ ainxn =bi ,i=1,…,p
ai1x1+ ai2x2+…+ ainxn bi , i=p+1,…,m
xj 0 , j=1,…,q
xj 符号无限制， j=q+1,…,n
.
目标函数
（LP）
第三页，本课件共有101页
*
比例性：决策变量变化引起目标的改变量与决策变量改变量成正比
可加性：每个决策变量对目标和约束的影响独立于其它变量
连续性：每个决策变量取连续值
确定性：线性规划中的参数aij , bi , ci为确定值
隐含的假设
第四页，本课件共有101页
*
矩阵形式说明：
A1 A2 ……… An
a11 a12 ……… a1n
A= a21 a22 ……… a2n
…………………
am1 am2 ………amn
x1
x= x2

xn
…
b1
b= b2

bm
…
c1
c= c2

cn
…
约束矩阵
决策向量
右端向量
价值向量
第五页，本课件共有101页
*
LP问题的规范型： LP问题的标准型：
LP问题的三种形式是等价的：
min z=cTx
Ax  b
x 0
.
min z=cTx
Ax=b
x 0
.
LP问题的规范型
LP问题的标准型
LP问题的一般型
第六页，本课件共有101页
*
LP问题的规范型
LP问题的一般型
第七页，本课件共有101页
*
LP问题的标准型
LP问题的一般型
第八页，本课件共有101页
*
例：将线性规划问题化成标准型：
第九页，本课件共有101页
*
解的概念：满足所有约束条件的一组x1, x2， …xn的值称作线性规划的可行解，所有可行解构成的集合称作可行域。使目标函数取得最大或最小值的可行解称为线性规划问题的最优解；对应的目标函数的取值称为最优值。求解线性规划问题就是求其最优解和相应的最优值。
图解法？对于只有两个变量的线性规划问题，可以用在平面上作图的方法求解，这种方法称为图解法。
特点：图解法简单、直观，便于初学者了解线性规划基本原理和几何意义。
§
第十页，本课件共有101页