文档介绍：关于线性规划与单纯形方法
*
第1页，讲稿共129张，创作于星期三
*
第一节线性规划问题及数学模型
一、实例
二、线性规划问题（LP问题）的共同特征
三、两变量线性规划问题的图解法
四、线性规划问题的标准型
五、标准型的紧缩形式
n－变量个数； m－约束行数； cj－价值系数；
bi－右端项或限额系数； aij－技术系数；
xj—决策变量
第11页，讲稿共129张，创作于星期三
*
练****题：是否为线性规划模型？
第12页，讲稿共129张，创作于星期三
*
— 半平面
作出LP问题的可行域
作出目标函数的等值线
移动等值线到可行域边界得到最优点

三、两变量线性规划问题的图解法
第13页，讲稿共129张，创作于星期三
*
4x1=16
4x2=12
x1+2x2=8
x1
x2
4
8
Q1 4
Q4 3
0
例3 （书P8）：
Q2(4,2)
Z=2x1+3x2
做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。
Q3
第14页，讲稿共129张，创作于星期三
*
目标函数z=ax1+bx2的值递增的方向与系数a、b有关
a>0, b>0
a<0, b>0
X1
X2
a<0, b<0
a>0, b<0
z=ax1+bx2
目标函数等值线：ax1+bx2=k
移项
x2=-a/bx1+k/b
目标函数等值线在纵轴上的截距为k/b
第15页，讲稿共129张，创作于星期三
*
例4
Z=36
第16页，讲稿共129张，创作于星期三
*
例用图解法求解线性规划问题
4x1=16
4x2=12
x1+2x2=8
x1
x2
4
8
Q1 4
Q4 3
0
Q2(4,2)
Z=2x1+4x2
当Z值由小变大时，将与Q2Q3重合
Q2Q3上任意一点都是最优解
有无穷多最优解（多重解）
Q3(2,3)
第17页，讲稿共129张，创作于星期三
*
例用图解法求解线性规划问题
可行域无界—无界解
（ “无有限最优解”或“最优解无界”）
约束条件过分宽松
x2
x1
x1-x2=1
B(2,1)
A(1,0)
-x1+2x2=0
0
可行域无解（不闭合）一定就会出现无界解吗？
第18页，讲稿共129张，创作于星期三
*
例用图解法求解线性规划问题
可行域无界—唯一最优解X*=(1,0)，对应于点A
x2
x1
x1-x2=1
B(2,1)
A(1,0)
-x1+2x2=0
0
第19页，讲稿共129张，创作于星期三
*
例用图解法求解线性规划问题
可行域无界—无穷多最优解对应于点B沿着OB向右上方发出的射线上的所有点
x2
x1
x1-x2=1
B(2,1)
A(1,0)
-x1+2x2=0
0
第20页，讲稿共129张，创作于星期三
*
例（书P11）：
无可行解（可行域为空）
x1
4x1=16
4x2=12
x1+2x2=8
x2
4
8
Q1 4
Q4 3
0
-2
-2x1+x2=4
无最优解
第21页，讲稿共129张，创作于星期三
*

能解决少量问题
揭示了线性规划问题的若干规律
解的类型
可行域类型
唯一最优解
无穷多最优解
最优解无界
（无有限最优解）
无解
（不存在可行域）
非空有界
无界
空集
规律1：
第22页，讲稿共129张，创作于星期三
*
规律2：
线性规划问题的可行域为凸集
线性规划问题凸集的顶点个数是有限的
最优解可在凸集的某顶点处达到
第23页，讲稿共129张，创作于星期三
*
小结：图解法的基本步骤：
1．在直角坐标系作出可行域S的区域（一般是一个凸多边形）
2．令目标函数值取一个已知的常数k，作等值线：c1x1+c2x2=k
3．对于max问题，让目标函数值k由小变大，即让等值线进行平移，若它与可行域S最后交于一个点（一般是S的一个顶点），则该点就是所求的最优点，若与S的一条边界重合，此时边界线上的点均是最优点
4．将最优点所在的两条边界线所代表的方程联立求解，即得最优解X*，把最优解X*带入目标函数，得最优值Z*=CX*
注意：若是求目标函数最小值，等值线向反方向移动
第24页，讲稿共129张，创作于星期三
*
四、线性规划问题的标准型

（1）目标函数：max
（2）约束条件：等式