第四部分线性规划模型

1、第四部分线性规划模型14.1 线性规划问题 在20世纪30年代未，苏联数学家康托洛维奇首先提出了线性规划模型，并于1947年由美国人丹捷格提出了线性规划的单纯形算法，较好地解决了线性规划的求解问题，从而奠定了线性规划作为一个学科的基石。 随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能够迅速地求解，为线性规划在经济等各领域的广泛应用创造了有利的条件。 1 线性规划的研究对象(1) 在现有的资源条件下，研究如何合理地计 划、安排，可使某一目标 达到最大化；(2) 在任务确定后，研究如何合理地计划、排， 用最低限度的人、财等资源, 去实现任务。说明：线性规划中研究的问题要求目

2、标函数与约束 条件函数均是线性的，或者说或以转化为线性的。2 线性规划建模型的过程(1) 理解需要解决的问题, 明确模型条件 以及要达到的目标；(2) 针对问题定义一组决策变量, 用 x =(x1, x2, , xn)T 表示某一方案。 这组决策变量的值就代表一个具体方案, 通常这些变量的取值是非负的;(3) 用决策变量的线性函数形式表示出所要寻找求的目标,称为目标函数。按问题的不同,要求目标函数在满足约束条件下实现最大化或最小化；(4) 用一组含有决策变量的等式或不等式来表示在解决问题的过程中所必须遵循的约束条件。满足以上条件(2)、(3)、(4) 的数学模 型称为线性规划的数学模型, 一般

3、形式为：max(min) z = c1x1+c2x2+cnxn约束条件：a11x1+ a12 x2+ +a1n xn (=, ) b1 ;a21x1+ a22 x2+ +a2n xn (=, ) b2 ; am1x1+ am2 x2+ +amn xn(=, ) bm. z = c1x1+c2x2+cnxn 称为目标函数, 其中cj ( j =1, 2, n ) 称为价值系数, c = (c1, c2 , cn)T, 称为价值向量, xj ( j =1, 2, , n)为求解的变量。由系数组成的矩阵：称为约束矩阵； 列向量 b = (b1,b2, ,bn )T : 为右端向量；条件 xj 0 (

4、j=1,2, ,n ) : 非负约束；一个向量x = (x1,x2, ,xn )T满足约束条件, 称为可行解或可行点，全部可行点的集合称为可行区域, 记为D。 使得目标函数值最大化或最小化的可行解称为该 线性规划的最优解，此目标函数值称为最优目标函数值，简称最优值。4.2.1 线性规划问题的标准形式线性规划问题： 在一组线性的等式或不等式的约束之下，求一个线性函数的最大值或最小值的问题，其标准形式为：简写为用矩阵形式表示为4.2.2 线性规划问题解的概念 设 A是约束方程组 m n 维的系数矩阵, 其秩为 m, B 是矩阵 A 中mm 阶非奇异子阵(即| B |0 ), 则称 B 是线性规划问

5、题的一个基。一般地，设 称 aj 是基向量，它是一个线性无关的向量组，与基向量 aj 对应的变量 xj 称为基变量，其余变量称为非基变量。基向量基变量非基向量非基变量若约束方程组 (2) 中的系数矩阵的秩为 m, 由 m=18MON) XMON+XTHU+XFRI+XSAT+XSUN=16TUE) XMON+XTUE+XFRI+XSAT+XSUN=15WED) XMON+XTUE+XWED+XSAT+XSUN=16THU) XMON+XTUE+XWED+XTHU+XSUN=19FRI) XMON+XTUE+XWED+XTHU+XFRI=14SAT) XTUE+XWED+XTHU+XSUN+XS

6、AT=12END例5 某个中型百货商场对售货人员的需求量经过统计分析后，得到如表1.2所示数据。为了保证销售人员的充分休息，售货人员每周工作五天，并连续休息两天。问应该如何安排售货人员的作息时间，既能满足需要，又使配备的售货人员的数量最少？时 间所需售货人员数量时 间所需售货人员数量星期日星期一星期二星期三28152425星期四星期五星期六193128表1.2解：由于每个售货员都要工作五天，休z = x1+x2+ +x7 (10)息两天，因此只要计算出连续休息两天的售货员的人数，也就确定了售货员的总人数。 设周一开始休息的人数为 x1, 周二开始休息人数为 x2, , 周日开始休息的人数为 x

7、7, 则由于除了在周六和周日休息的人员 x1+x2+x3 + x4+x5 28之外其余的售货员均应该工作，因此，同理，有x2 + x3+ x4 +x5+x6 15x3+ x4+x5+ x6+x7 24x4 + x5+x6 + x7+x1 25x5+x6+x7 + x1+x2 19x6+x7 + x1+x2+x3 31x7 +x1+x2+x3+x4 28 xi 0，i=1,2, ,7.用 Lindo 软件计算可得： x1=12, x2=0, x3= 11, x4=5, x5= 0, x6 = 8, x7=0每周的至少需要配备 36 个售货员，并如下安排休息人数：星期一、二： 12 人；星期三、四

8、： 11 人；星期五： 5 人;星期六、日： 8 人。MIN 100 XMON+100 XTUE+100 XWED+ 100 XTHU+100 XFRI+100 XSAT+100 XSUNSUBJECT TOSUN) XWED+XTHU+XFRI+XSAT+XSUN=24MON) XMON+XTHU+XFRI+XSAT+XSUN=25TUE) XMON+XTUE+XFRI+XSAT+XSUN=19WED) XMON+XTUE+XWED+XSAT+XSUN=31THU) XMON+XTUE+XWED+XTHU+XSUN=28FRI) XMON+XTUE+XWED+XTHU+XFRI=28SAT)

9、 XTUE+XWED+XTHU+XSUN+XSAT=15END例6 制造某种产品需要A、B、C三种配件，其规格与数量如表1.3示。各类配件都用5.5米长的同一种圆钢生产。若计划生产100套产品，最少需要多少根圆钢？配件类型规格长度(米)每件产品所需配件数量ABC3.12.11.2124表1.3解：确定每根圆钢截成A、B、C三种配截法一根圆钢所截各类配件数量产品需要数量类型12345A(3.1)B(2.1)C(1.2)1100 010210 02124100200400 余料j(米)0.3 0 0.1 1 0.7件的具 体下料方式，即确定余料长度 j1.2米的各种下料方式：问题转化为： 采用上述

10、五种截法，需要多少根圆钢才能生产100件产品，且使总下料根数最少？min z= x1+x2 + x3+ x4 +x5s.t.解: 设按第 j 种截法下料 xj ( j =1,2,3,4,5)根, 则有x1+x2 100 x1 +2x3+x4 200 2x2+ x3+2x4+4x5 400 x1, x2, x3, x4, x5 0用 Lindo 软件计算可得： x*（0, 100, 100, 0, 25)T, z*=225.具体下料方式为：截法2、3： 100根；截法5： 25根； 需要用某种原料下 m 种零件 A1, A2, Am 的毛坯材料。根据既省材料又易于现场操作的原则，在一根原材料上已

11、经设计出 m 种不同的小料方式，其中第 j 种方式可下得 Ai 零件 aij 个。若 Ai 零件的需要量为 bi, 则应该如何下料，才能使既满足需要又使所用的原材料最少？一般(一维)下料问题：解：设按第 j 种截法下料 xj( j =1,2,n)根,所用原材料总数为 z 件, 则配料问题要用n种原料 A1, A2, , Am 配制成具有 m种成份 B1, B2, , Bm 的某种产品，规定每一单位的产品所含Bi成分的数量不低于bi( i=1,2,m)。 原料 Aj 的单价为cj, 现有数量为 dj, 而每一单位Aj原料所含Bi成分的数量为aij (i =1,2,m, j =1,2,n). 若要

12、求酿成的产品的产品数量不低于t, 则应该如何配料, 才能使既满足需要又使总成本 最少？设所取原料Aj 的数量为xj , 原料总成本为 z, 则配成品的总量为所含Bi成分的数量则有则问题的线性规划(LP)模型为：例7 某化工厂要用三种原料I, II,III 混合配制三种不同规格的产品A,B,C。各产品的规格、单价如表1.4所示，各原料的单价及每天最大供应量如表1.5所示，则该厂应该如何安排生产才能使利润本最大？产品规格 单价(元/千克)A原料I不少于 50% 50 原料II不超过 25%B原料I不少于 25% 35 原料II不超过 50% C 不限 25 产品最大供应量(千克/天) 单价(元/千

13、克)I 100 50II 100 25III 60 35解:1.确定决策变量设用 xij 表示第 i 种产品的日产量(千克)中所含第 j 种原料的数量, 具体关系如下: jiI II IIIABCx11 x12 x13x21 x22 x23x31 x23 x332.确定约束条件: (1) 规格约束：整理，得： (2) 资源约束：3.目标函数(1) 产品的总产值：产品 A 的产值：产品 B 的产值：产品 C 的产值：(2) 产品的总成本：产品 A 的成本：产品 B 的成本：产品 C 的成本：因此，目标函数为：因此，问题的LP模型为：用 Lindo 软件计算可得：x11=100, x12=50, x13=50, x21= x22=x23 =x31= x32x33 0 每天只生产 A 产品 200 千克，分别用 I 原料 100千克和 II、III 原