2线性规划.pptVIP

第一章 线性规划 线性规划的建模 线性规划的模型 线性规划的图解法 线性规划的标准化 线性规划的基本概念 线性规划的求解 线性规划 Linear programming 1、线性规划的建模一例（例1） 例1：在工厂计划期内要安排生产A、B两种产品，已知生产单位产品所需的设备台时及a、b两种原材料的消耗如下表。又该工厂每生产一件A产品可获利2元，每生产一件B产品可获例3元。问：如何安排计划使该工厂获利最大？ 2、线性规划模型 线性规划模型解析式标准形式 模型形式简记 线性规划模型矩阵标准形式 线性规划模型的结构 目标函数 ：max，min 约束条件：≥,=,≤ 变量符号：：≥0, unr, ≤0 线性规划的标准形式 目标函数：max 约束条件 ：= 变量符号 ：≥0 线性规划模型练习1 三种产品要经过三种不同的工序加工。各种产品每一件所需时间（分钟），每天各道工序的加工能力（每天多少分钟）和销售每一种产品的单位利润如下。试建立使总利润达到最大的线性规划模型。 线性规划模型练习2 某厂为进行生产需采购A、B两种原材料，单价分别为70元/公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少于80公斤，而A原材料不少于20公斤。问如何确定最好的采购方案（即花掉的资金最少并且购买的总量最大）？ 3、线性规划的图解 解决只有两个决策变量的线性规划问题 方法：在直角坐标系中画出所有约束方程的图象，从而得到可行域（满足所有约束方程的解的集合）；然后画出经过原点的目标函数图象的平行线——目标函数等值线；寻找经过可行域的使Z达到最大的目标函数等值线，该直线与可行域的交集即为最优解集。 图解法例1 max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 图解法例2 max z=2x1+3x2 s.t. x1+ 2x2≤8 4 x1 ≤16 4x2 ≤12 x1 ≥0, x2≥0 四种可能的解的情况 唯一最优解 无穷多最优解 无界解（无穷可行解，但无最优解） 无解（无可行解） 唯一最优解 max z=2x1+3x2 s.t. x1+ 2x2≤8 4 x1 ≤16 4x2 ≤12 x1 ≥0, x2≥0 线性规划的图解 无穷多最优解 无界解 无解 4、模型的标准化 一般形式： 模型的标准化 模型的标准化例题 将 例题答案 模型的标准化练习 练习答案 5、线性规划的基本概念 可行解与最优解 可行解：满足约束条件的解，记为X X=（x1，x2，…，xn）T 最优解：使目标函数值达到最优的可行解。 基矩阵 约束方程系数矩阵A的m×m子矩阵B，若B的行列式≠0，则称B为A的一个基（矩阵）。 基变量、基向量 基B对应的m个变量为基变量，其他n-m个变量为非基变量。假定 基解、基可行解 基解：令所有非基变量为0，根据约束方程求得的解（不包括非负约束）为对应基的基解。表示为 X=（x1，x2，… ，xm，0，… ，0）T 基可行解：满足非负约束的基解。 基的个数最多为 ，故基解的个数最多为 。 总结几个概念 基矩阵、非基矩阵 基变量、非基变量 基向量、非基向量 基解、可行解、基可行解、最优解 几种解的关系 可行域的性质 线性规划的可行域是凸集 线性规划的最优解在极点上 基解例2 max z=x1+3x2 D s.t. x1+ x2+x3 =6 B -x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x4≥0 x1=0 E O x2=0 A 基解课堂练习 max z=3x1+x2 s.t. 3x1+ 5x2+x3 =15 5x1+2x2 +x4=10 x1,x2,x3,x4≥0 试求其所有的基解,并判断哪些基解为基可行解. 练习答案 解题过程 A= 3 5 1 0 B1= 3 5 ∣B∣≠0为A的一个基 5 2 0 1