《1-1线性规划概念与数学模型-wxp》由会员分享，可在线阅读，更多相关《1-1线性规划概念与数学模型-wxp（43页珍藏版）》请在金锄头文库上搜索。
1、第一章、第一章、 线性规划线性规划1 1、线性规划问题及其数学模型、线性规划问题及其数学模型2 2、线性规划的几何意义、线性规划的几何意义3 3、线性规划的求解单纯形法、线性规划的求解单纯形法一、线性规划问题：生产计划问题（例一、线性规划问题：生产计划问题（例1 1）甲乙设备128台时原材料A4016千克原材料B0412千克甲、乙产品每件获利分别为2、3元，如何安排获利最多？第一节、第一节、 线性规划问题及其数学模型线性规划问题及其数学模型如何制定生产计划，使两种产品总如何制定生产计划，使两种产品总 利润最大？利润最大？ 问题讨论何为生产计划？何为生产计划？总利润如何描述？总利润如何描述？还要
2、考虑什么因素？还要考虑什么因素？有什么需要注意的地方（技巧）？有什么需要注意的地方（技巧）？最终得到的数学模型是什么？最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）二、线性规划的定义和数学描述（模型）1 1定义：定义：对于求取一组变量对于求取一组变量x xj j(j (j =1,2,.,n)=1,2,.,n)， 使之既满足线性约束条件，又使具有线性表达使之既满足线性约束条件，又使具有线性表达 式的目标函数取得极大值或极小值的一类最优式的目标函数取得极大值或极小值的一类最优 化问题称为化问题称为线性规划问题线性规划问题，简称，简称线性规划线性规划。2.2. 线性规划模型的特点：线
3、性规划模型的特点： 用一组未知变量表示要求的方案，这组用一组未知变量表示要求的方案，这组 未知变量称为未知变量称为决策变量决策变量；存在一定的存在一定的限制条件限制条件，且为线性表达式，且为线性表达式 ；有一个有一个目标要求目标要求（最大化，当然也可以（最大化，当然也可以 是最小化），目标表示为未知变量的线是最小化），目标表示为未知变量的线 性表达式，称之为性表达式，称之为目标函数目标函数；对决策变量有对决策变量有非负要求非负要求。三三LPLP的数学描述的数学描述( (数学模型数学模型) )： 一般形式 二、二、 线性规划的图解法线性规划的图解法解的几何表示解的几何表示 1 1什么是图解法？什
4、么是图解法？线性规划的图解法就是用线性规划的图解法就是用几何作图几何作图的的方法方法分析并求出其最优解分析并求出其最优解的过程。的过程。求解的思路是：求解的思路是：先将约束条件加以图先将约束条件加以图解，求得满足所有约束条件的解的集合解，求得满足所有约束条件的解的集合（ 即可行域）即可行域），然后结合目标函数的要求从，然后结合目标函数的要求从 可行域中找出最优解。可行域中找出最优解。可行解：满足所有约束条件的解图解法举例图解法举例 实施图解法，以求出最优生产计划（最优解 ）例1 maxZ=2x1+3x2s.t.工时原材料由于线性规划模型中只有两个决策变量， 因此只需建立平面直角坐标系就可进行图
5、解 . 第一步：第一步：建立平面直角坐标系，标出坐标原坐标原 点点, 坐标轴的指向坐标轴的指向和单位长度单位长度。用x1轴表示产品甲的产量，用x2轴表示产 品乙的产量。 第二步：第二步：对约束条件加以图解。 第三步：第三步：画出目标函数等值线，结合目标 函数的要求求出最优解最优生产方案。约束条件的图解约束条件的图解: :每一个约束不等式在平面直角坐标系中都 代表一个半平面，只要先画出该半平面的边先画出该半平面的边 界界，然后确定是哪个半平面确定是哪个半平面。 ?以第一个约束条件（工时）x1+2 x2 8 为例说明约束条件的图解过程。怎么画边界怎么画边界怎么确定怎么确定半平面半平面如果全部的劳动
6、工时都用来生产甲 产品而不生 产乙产品，那么甲产品的最大可能产量为8吨，计 算过程为： x1+208 x18这个结果对应着下图中的点B(8,0),同样我们 可以找到B产品最大可能生产量对应的点A(0,4)。 连接A、B两点得到约束 x1+2 x2 8 所代表的半平面的边界:x1+2x2 8，即直线AB。12345678912345x1+2x2 = 8ABAB三个约束条件及非负条件三个约束条件及非负条件x x1 1,x ,x2 2 0 0所代表的公共部分所代表的公共部分 图中阴影区，就是满足所有约束条件和非负条件的点的图中阴影区，就是满足所有约束条件和非负条件的点的 集合，即集合，即可行域可行域
7、。在这个区域中的每一个点都对应着一个可。在这个区域中的每一个点都对应着一个可 行的生产方案。行的生产方案。 第二、三个约第二、三个约 束条件的边界束条件的边界 直线直线CDCD，EF: EF: 4x4x1 1=16,4x=16,4x2 2=12=1212345678912345EF 4x2 = 124x1=16ABCDx1+4x2 = 8令 Z=2x1+3x2=c,其中c c为任选的一个常数为任选的一个常数，在图中画出 直线 2x1+3x2=c,这条直线上的点即对应着一个可行的生产 方案，即使两种产品的总利润达到c。这样的直线有无数条，而且相互平行，称这样的直线 为目标函数等值线目标函数等值线
8、。只要只要画出两条目标函数等值线两条目标函数等值线，比如 令c0和c=6，就能看出目标函数值递增的方向目标函数值递增的方向，用箭头标出箭头标出这个方向。图中两条虚线 l1和l2就分别代表 目标函数等值线 2x1+3x2=0 和 2x1+3x2=6,箭头表示使两种产品的总利润递增的方向。12345678912345x1+2x2 = 8ABDC4x1=16l1l2l3FEBA4x1=12沿着箭头沿着箭头的方向平移平移目标函数等值线，使其达达 到可行域中的最远点到可行域中的最远点QQ2 2, QQ2 2点就是要求的最优 点，它对应的相应坐标 x1=4,x2=2 就是最有利 的产品组合，即生产甲产品4
9、件，乙产品2件能 使两种产品的总利润达到最大值 Zmax=24+32=14(元)，x x1 1=4,x=4,x2 2=2=2就是线性规 划模型的最优解最优解，Z Zmaxmax=14=14就是相应的目标函就是相应的目标函 数最优值数最优值尽管最优点的对应坐标可以直接从图中尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精给出，但是在大多数情况下，对实际问题精 确地看出一个解答是比较困难的。所以，通确地看出一个解答是比较困难的。所以，通 常总是常总是用解联立方程的方法求出最优解的精用解联立方程的方法求出最优解的精 确值。确值。比如比如QQ2 2点对应的坐标值我们可以通过求点
10、对应的坐标值我们可以通过求 解下面的联立方程，即求直线解下面的联立方程，即求直线ABAB和和CDCD的交的交点来求得。点来求得。直线直线AB: xAB: x1 1+2x+2x2 2=8=8直线直线CD: 4xCD: 4x1 1=16=160 1 2 3 4 5 6 7 8 9 x15 4 3 2 1x2（8，0）C=6（0，4）C=0s.t.Q2（4，2）一般线性规划解的几种不同情形：无穷多最优解（多重最优解）无界解无可行解0 1 2 3 4 5 6 7 8 9 x15 4 3 2 1x2-2 -14x1=124x1=16x1+2x2 = 8-2x1+x2 = 4二、二、 线性规划的标准型线性
11、规划的标准型1 1、LPLP标准型的概念标准型的概念（1 1）什么是）什么是LPLP的标准型？的标准型？标准格式！标准格式！（2 2）LPLP标准型的特点标准型的特点 目标函数约定是极大化目标函数约定是极大化Max(Max(或极小化或极小化Min);Min); 约束条件均用等式表示约束条件均用等式表示; ; 决策变量限于取非负值决策变量限于取非负值; ; 右端常数均为非负值右端常数均为非负值 ; ;2 2LPLP的数学描述的数学描述( (数学模型数学模型) )： （1）标准形式 （2 2）紧缩形式）紧缩形式（3）向量矩阵形式：其中：（4）矩阵形式其中 : 3 3、LPLP问题的标准化问题的标准
12、化 （为了问题的求解（为了问题的求解 ）MinZMinZ=CX=CXMaxZMaxZ=-CX=-CXZ=-ZZ=-Z（2 2） 约束条件的标准化约束条件的标准化2)确定基变量与非基变量； 例如，基变量( x3, x4, x5 )3)令非基变量取值为0； 令x1=x2=04)(基变量, 非基变量)构成基本解。(0,0,4,2,2) 然后按照基本解的定义： H(6,4,-6,0,0)T, C(3,1,0,3,0)T,B(2,2,0,0,2)T, D(2,0,2,4,0)T, F(-2,0,6,0,4)T, I(4,0,0,6,-2)T, E(0,-2,6,6,0)T, A(0,1,3,0,3)T,
13、 G(0,4,0,-8,6)T, O(0,0,4,2,2)T.对于上例,共有10个基本解求得的基本解和图解法对照，找出相应的点 。 为何红点和绿点是基本解却不是基本可行 解?12343210X2X1x1-x2=2-x1+2x2=2x1+x2=4Z=0Z=14IDBACHFEG结论：结论：(1) (1) 基本解基本解对应所有可行域边界及其延对应所有可行域边界及其延 长线、坐标轴之间的长线、坐标轴之间的交点交点；(2) (2) 基本可行解基本可行解对应可行域的对应可行域的顶点顶点。第一节 总 结LP定义，模型特点，图解法标准型概念及其作用标准型特点及四种形式标准化步骤n LP的提出与定义n LP数学描述可行解基解（基）基可行解（可行基）n LP问题的解课后作业:P44页1.1题的4个小题，1.3题的（1）题
