一、一般线性规划问题的数学模型

1、第一章 线性规划及单纯形法1、 一般线性规划问题的数学模型问题的提出 在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。任何资源，如劳动力、原材料、设备或资金等都是有限的。因此，必须进行合理的配置，寻求最佳的利用方式。 由此可以把有限资源的合理配置归纳为两类问题：一类是如何合理地使用有限的资源，使生产经营的效益达到最大；另一类是在生产或经营的任务确定的条件下如何合理地组织生产，安排经营活动，使所消耗的资源数最少。这是最常见的两类规划问题。 与规划问题有关的数学模型由两部分组成：一部分是约束条件，反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务，另一

2、部分是目标函数，反映生产经营在有限资源条件下希望达到的生产或经营的目标。 例1 常山机器厂生产甲、乙两种产品。这两种产品都要分别在A、B、C三种不同设备上加工。按工艺材料规定，生产每件产品甲需占用各设备分别为2小时、4小时、0小时，生产每件产品乙需占用各设备分别为2小时、0小时、5小时。已知各设备计划期内用于生产这两种产品的能力分别为12小时、16小时、15小时，又知每生产一件甲产品企业能获得2元利润，每生产一件乙产品企业能获得3元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大？解：为更加直观理解题意，把上述问题转化为如下表格甲产品乙产品资源限量A设备2212B设备4016C设

3、备0515利润23假定用x1和x2分别表示甲、乙两种产品在计划期内的产量。因设备A在计划期内的可用时间为12小时，不允许超过，于是有2x1+2x212。对设备B、C也可列出类似的不等式：4x116，5x215。企业的目标实在各种设备能力允许的条件下，使总的利润收入z=2x1+3x2为最大。所以可归结为：约束于s.t.使 z=2x1+3x2max 这是一个将生产安排问题抽象为在满足一组约束条件的限制下，寻求变量xl和x2的决策值，使目标函数达到最大值的数学规划问题。常写成如下数学表达式max z=2x1+3x2s.t.例2：某养鸡场每天需要的混合饲料的批量是100千克，这些饲料必须包含：（1）

4、至少0.8%但不超过1.2%的钙；（2） 至少15%的蛋白质；（3） 最多5%的粗纤维假定主要的配料包括骨粉、谷物和大豆粉，这些配料的营养成分及每千克成本汇总如下表，问如何配置可使总成本最小。骨粉谷物大豆粉钙0.180.010.02蛋白质0.030.090.25粗纤维0.000.020.02每千克成本（元）25.803.607.50解：设是100千克混合饲料中所用的骨粉、谷物和大豆粉的含量，于是数学模型为：s.t. 例3：某公司有一笔30万元的资金，考虑今后3年内用于下列项目的投资：（1） 三年内每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资。（2） 只允许第一年年初

5、投入，于第二年末收回，本利合计为投资额的150%，但此类投资限额不超过15万元。（3） 允许于第二年年初投入，于第三年末收回，本利合计为投资额的160%，但投资限额20万元。（4） 允许于第三年年初投入，年末收回，可获利40%，但投资限额10万元。试为该公司确定一个使第三年末本利和为最大的投资组合方案。【解】 为便于理解，投资方式见图用xij表示第i年初投放到j项目的资金数第一年年初 投资方式 x11+x12=30第二年年初，可投资金额 1.2x11，投资方式x21+x23，满足x21+x23=1.2x11第三年年初，可投资金额 1.2x21+1.5x12，投资方式x31+x34，满足x31+

6、x34=1.2x21+1.5x12第三年年底可回收资金 1.2 x31+1.4x34+1.6 x23线性规划模型为 max z=1.2 x31+1.4x34+1.6 x23 s.t. 求解得：x11=16.67 x12=13.33 x21=0 x23=20 x31=10 x34=10第三年末本利合计为58万元1-2 线性规划问题的数学模型规划问题的数学模型包含三个组成要素：(1) 决策变量，指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量；(2) 目标函数，指问题要达到的目的要求，表示为决策变量的函数；(3) 约束条件，指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的

7、等式或不等式。如果在规划问题的数学模型中，决策变量为可控的连续变量，目标函数和约束条件都是线性的，这类模型称作为线性规划问题的数学模型一般线性规划问题的数学模型可表示为以下几种形式：max(或min) z=c1x1+c2x2+cnxns.t. 以上模型的简写形式为： max(或min) z= s.t. 用向量形式表达时，上述模型可写为： max(或min) z=CX s.t. 式中： C=(c1,c2,cn); X= Pj= b=用矩阵形式来表示可写为： max(或min) z=CX s.t. A=A称为约束方程组变量的系数矩阵，或简称约束变量的系数矩阵。13线性规划问题的标准形式由于目标函数

8、和约束条件内容和形式上的差别，线性规划问题可以有多种多样。为了便于讨论，规定线性规划问题的标准形式如下： max z=CX s.t. 标准形式的线性规划模型中，1、目标函数为求极大值(有些书上规定是求极小值)，2、约束条件为等式，3、约束条件右端常数项b全为非负值，4、变量X的取值为非负。对不符合标准形式(或称非标准形式)的线性规划问题，可分别通过下列方法化为标准形式:1目标函数为求极小值即min z=CX 等价于max(-z)2约束条件为不等式。当约束条件为“”时，如30x1+20x2160，可添加松弛变量x30，使成等式30x1+20x2+x3=160当约束条件为“”时，如3x1+15x2

9、5，可添加剩余变量x40，使成等式3x1+15x2-x4=5松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超用的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。3. 常数项bj<0，两边乘负号 4. 变量取值无约束的变量。这时可令x=x1-x2, 其中x1，x2 0代入变量xj0。可令xj= -xj，显然xj 0。【例4】 将下述线性规划模型化为标准形式 min z=x1+2x2+3x3 s.t. 2x1+x2+x39 -3x1+x2+2x34 3x1-2x2-3x3= -6 x10, x20, x3取值无约束解：令 z= -z, x1= -x1 x

10、3-x3”=x3 (x3,x3” 0,) 将问题转化为： max z= x1-2x2-3 x3+3 x3”+0x4+0x5 s.t. 2x1 +x2 +x3 - x3” +x4 =9 3 x1 +x2 +2x3 -2 x3” - x5 = 4 3 x1 +2x2 +3x3 -3 x3” =6 x1， x2，x3,x3” 0l4线性规划问题的解线性规划问题max z=CX s.t. 求解线性规划问题，就是从满足约束条件的方程组中找出一个解，使目标函数达到最大值。可行解 满足上述约束条件的解。全部可行解的集合称为可行域。最优解 使目标函数达到最大值的可行解称为最优解。基 设A为约束方程组AX=b的

11、m×n阶系数矩阵，(设n>m)，其秩为m。B是矩阵A中的一个m×m阶的满秩子矩阵，称B是线性规划问题的一个基。不失一般性，设B= = (P1,.,Pm)B中的每一个列向量Pj (j1，,m)称为基向量，与基向量Pj对应的变量xj称为基变量。线性规划中除基变量以外的其它变量称为非基变量。基 解 在约束方程组，令所有非基变量xm+1=xm+2=.=xn=0又因为0,m个约束方程有唯一解XB(x1,x2,.xm) ,将这个解加上非基变量取0的值有x(x1,x2,.xm,0,0)称X为线性规划问题的基解。基可行解 满足变量非负约束条件的基解称为基可行解。可行基 对应于基可行解

12、的基称为可行基。例5：在线性规划模型 max z=3x1+4x2s.t. 化成标准形得： max z=3x1+4x2s.t. 其中P1= P2= P3= P4= P5=列向量共有个组合，易验证，除（P1，P3，P4）外，其余任取3列均线性无关，可以组成9个基。若取B1=（P3,P4,P5）=， 则x3,x4,x5为基变量，x1,x2为非基变量，令x1=x2=0,得：x3=6, x4=8, x5=6，对应的基解为X(1)=(0,0,6,8,6)T0 所以是基可行解，B1是可行基。若取B2=（P2,P4,P5）=则x2,x4,x5为基变量，x1,x3为非基变量。相应的基解为X(2)=(0,6,0,-4,-6)T上述基解中存在负值，此时X(2)不是基可行解，B2也非可行基。其他基所对应的基解，可以类似求出。见列表列向量组合是否基向量基变量非基变量对于的基解是否基可行解是否可行基函数值是否最优解P1P2P3是x1,x2,x3x4,x5(2,3,1,0,0)是是18P1P2P4是x1,x2,x4x3,x5(3,3,0,-1,0)否否P1P2P5是x1,x2,x5x3,x4(4,2,0,0,2)是是20是P1P3P4否P1P3P5是