运筹学之线性规划引论

1、第一章第一章 线性规划引论线性规划引论1.1 线性规划问题及其数学模型线性规划问题及其数学模型1.2 线性规划问题的图解法线性规划问题的图解法1.3 线性规划问题的建模与应用举例线性规划问题的建模与应用举例1.1 线性规划问题及其数学模型线性规划问题及其数学模型(1) 线性规划问题线性规划问题例例1 1、生产组织与计划问题、生产组织与计划问题A, B A, B 各生产多少各生产多少, , 可获最大利润可获最大利润? ?可用资源可用资源煤煤劳动力劳动力仓库仓库A B1 23 20 2单位利润单位利润40 50306024解解: : 设产品设产品A, BA, B产量分别为变量产量分别为变量x x1

2、 1， x x2 2根据题意，两种产品的生产要受到可用资源的限制，根据题意，两种产品的生产要受到可用资源的限制，具体讲：具体讲：对于煤，两种产品生产消耗量不能超过对于煤，两种产品生产消耗量不能超过30，即：，即： x1 + 2x2 30对于劳动力，两种产品生产的占用量不能超过对于劳动力，两种产品生产的占用量不能超过60，即：，即： 3x1 + 2x2 60对于仓库，两种产品生产的占用量不能超过对于仓库，两种产品生产的占用量不能超过24，即：，即： 2x2 24另外，产品数不能为负，即：另外，产品数不能为负，即： x1，x2 0同时，我们有一个追求的目标同时，我们有一个追求的目标-最大利润，即：

3、最大利润，即： Max Z= 40 x1 +50 x2综合上述讨论，在生产资源的消耗以及利润与产品产量成综合上述讨论，在生产资源的消耗以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的数学模型：以建立如下的数学模型：Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件例例2 2 合理配料问题合理配料问题求：求：最低成本的原料混合方案最低成本的原料混合方案 原料原料 A B 每单位成本每单位成本 1 4 1 0

4、2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添每单位添加剂中维生加剂中维生 12 14 8 素最低含量素最低含量解：设每单位添加剂中原料解：设每单位添加剂中原料i i的用量为的用量为xj(j =1,2,3,4) 根据题意：混合配料后，根据题意：混合配料后， 每单位添加剂中每单位添加剂中A A的含量不得低于的含量不得低于1212，即，即 4x1 + 6x2 + x3+2x4 12 每单位添加剂中每单位添加剂中B B的含量不得低于的含量不得低于1414，即，即 x1 + x2 +7x3+5x4 14 每单位添加剂中每单位添加剂中C C的含量不得低于的含量不得低于8 8，即

5、，即 2x2 + x3+3x4 8 另外，原料使用量不能为负，即：另外，原料使用量不能为负，即： x1，x2 ， x3， x4， 0同时，我们有一个追求的目标同时，我们有一个追求的目标-成本最低，即：成本最低，即： Min Z= 2x1 + 5x2 +6x3+8x4综合上述讨论，在添加剂中各维生素的含量以及成本与原综合上述讨论，在添加剂中各维生素的含量以及成本与原料消耗量成线性关系的假设下，把目标函数和约束条件放料消耗量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的数学模型：在一起，可以建立如下的数学模型：目标函数目标函数约束条件约束条件Min Z= 2x1 + 5x2 +6

6、x3+8x44x1 + 6x2 + x3+2x4 12 x1 + x2 + 7x3+5x4 142x2 + x3 + 3x4 8 xj 0 (j =1,4)s.t 2.9m 2.9m钢筋架子钢筋架子100100个，每个需用个，每个需用 2.1m 2.1m 各各1 1，原料长，原料长7.4m7.4m 1.5m 1.5m求：如何下料，使得残余料头最少。求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；解：首先列出各种可能的下料方案； 计算出每个方案可得到的不同长度钢筋的数量及残余计算出每个方案可得到的不同长度钢筋的数量及残余料头长度；料头长度； 确定决策变量；确定决策变量； 根据下料

7、目标确定目标函数；根据下料目标确定目标函数； 根据不同长度钢筋的需要量确定约束方程。根据不同长度钢筋的需要量确定约束方程。例例3 3、合理下料问题、合理下料问题设按第设按第i i种方案下料的原材料为种方案下料的原材料为x xi i根根 8 ,7 ,6 ,5 ,4 ,3 ,2 , 1ix100 x4x3x2x0 x3xx0 x100 x0 xx2x3x0 xx2x0100 x0 x0 x0 x0 xxxx2. t . sxxxxxxxxZMini87654321876543218765432187654321为大于零的整数，为大于零的整数，组合方案组合方案 1 2 3 4 5 6 7 8 2.9

8、m 2 1 1 1 0 0 0 0 2.1m 0 2 1 0 3 2 1 0 1.5m 1 0 1 3 0 2 3 4 合合 计计 7.3m 7.1m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料料 长长 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 料料 头头 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m例例4 4、运输问题、运输问题 工工 厂厂 1 2 3 库存库存 仓仓 1 2 1 3 50 2 2 2 4 30 库库 3 3 4 2 10 需求需求 40 15 35运输运输单价单价求：求：运输费用最小

9、的运输方案运输费用最小的运输方案。解：设解：设x xijij为为i i 仓库运到仓库运到j j工厂的原棉数量工厂的原棉数量 其中：其中：i i 1 1，2 2，3 3 j j 1 1，2 2，3 3Min Z= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 + x12+ x13 50 x21 + x22+ x23 30 x31 + x32+ x33 10 x11 + x21+ x31 = 40 x12 + x22+ x32 = 15x13 + x23+ x33 = 35 xij 0s.t(2) 线性规划问题的特点线性规划问题的特点l

10、决策变量：决策变量： ( (x x1 1 x xn n) )T T 代表某一方案，代表某一方案， 决策者要考虑决策者要考虑和控制的因素非负；和控制的因素非负；l目标函数：目标函数：Z=Z=( (x x1 1 x xn n) ) 为线性函数，求为线性函数，求Z Z极大或极小极大或极小; ;l约束条件：可用线性等式或不等式表示约束条件：可用线性等式或不等式表示. .具备以上三个要素的问题就称为具备以上三个要素的问题就称为 线性规划问题线性规划问题。 0 x,x,xb,xaxaxab,xaxaxab,xaxaxat . sxcxcxcZMinMaxn21mnmn22m11m2nn22221211nn

11、1212111nn2211目标函数目标函数约束条件约束条件(3) 线性规划模型一般形式线性规划模型一般形式隐含的假设隐含的假设l比例性：决策变量变化引起目标的改变量与决策变量改比例性：决策变量变化引起目标的改变量与决策变量改变量成正比变量成正比l可加性：每个决策变量对目标和约束的影响独立于其它可加性：每个决策变量对目标和约束的影响独立于其它变量变量l连续性：每个决策变量取连续值连续性：每个决策变量取连续值l确定性：线性规划中的参数确定性：线性规划中的参数aij , bi , cj为确定值为确定值1.2 线性规划问题的图解法线性规划问题的图解法 20Xb,AXt . s1CXZMinMax 定义

12、定义1：满足约束：满足约束(2)的的X=(X1 Xn)T称为线性规划问题的称为线性规划问题的可行解可行解，全部可行解的集合称为，全部可行解的集合称为可行域可行域。定义定义2 2：满足：满足(1)(1)的可行解称为线性规划问题的的可行解称为线性规划问题的最优解最优解。例例1-1 Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0s.t解：解：(1)(1)、确定可行域、确定可行域 X1+2X2 30 3X1+2X2 60 2X2 24 X X1 1 0 0 X X2 2 0 02030100102030X2DABC2X2 24X1+2X2

13、 303X1+2X2 60X X1 1 0 0X X2 2 0 0可行域可行域(2)(2)、求最优解、求最优解最优解：最优解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C点：点： X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC最优解最优解Z=975可行解可行解Z=0等值线等值线解：解：(1)(1)、确定可行域与上例完全相同。、确定可行域与上例完全相同。 (2)(2)、求最优解、求最优解0203010102030DABC最优解最优解Z=1200最优解：最优解：BCBC线段线段0

14、x,0 x242x602x3x302xxt . s80 x40 xzMax21212212121例最优解：最优解：BCBC线段线段B B点：点：X X(1)(1)=(6,12) C=(6,12) C点：点：X X(2)(2)=(15,7.5)=(15,7.5)X=X= X X(1)(1)+(1-+(1- )X)X(2) (2) ( (0 0 1 1) ) Max Z=1200 Max Z=1200 X1 6 15 X2 12 7.5X= = +(1- )X1 =6 +(1- )15X2=12 +(1- )7.5X1 =15-9 X2 =7.5+4.5 (0 1)例例1-3、 Max Z=2X1

15、+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0s.tZ=08246X240X1-2X1+X2 22X1+X2 8X1 0X2 0可行域可行域无界无界无有限最优解无有限最优解无有限最优解无有限最优解可行域可行域无上界无上界例例1-4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0无可行域无可行域无可行解无可行解-1X2-1X10s.tX2 0X1 0-X1 -X2 101 2 3 4 5 6 7 8 1 2 3 4 5 6 有唯一最优解：有唯一最优解：x1 = 4 x2 = 2最优值最优值 Z = 14x2 x1(4 2) 0 x,0 x4124x382x2

16、82xx1122x2xt . s3x2xzMax1-22121212121例例01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1 0 x,0 x4124x362x282xx1122x2xt . s2xxzMax2-22121212121例例8z102x24x21 最优值：最优值：有无穷多最优解：有无穷多最优解：无界解无界解x1x2 0 x,0 x1xx22xxt . sxxzMax3-221212121例例x1x2 无可行解无可行解 0 x,0 x63x2x1xxt . s2x3xzMax4-221212121例例直观结论直观结论n若线性规划问题有解，则可行域是一个凸多边形若

17、线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；（或凸多面体）；n若线性规划问题有最优解，则若线性规划问题有最优解，则q唯一最优解对应于可行域的一个顶点；唯一最优解对应于可行域的一个顶点；q无穷多个最优解对应于可行域的一条边；无穷多个最优解对应于可行域的一条边；n若线性规划问题有可行解，但无有限最优解，则若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；可行域必然是无界的；n若线性规划问题无可行解，则可行域必为空集。若线性规划问题无可行解，则可行域必为空集。 1.3 线性规划问题的建模与应用举例线性规划问题的建模与应用举例数学规划的建模原则数学规划的建模原则 容易理解容易理

18、解。建立的模型不但要求建模者理解，还应当让。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。使得到的结论能够更好地应用于解决实际问题。 容易查找模型中的错误容易查找模型中的错误。这个原则的目的显然与。这个原则的目的显然与(1)相关。相关。常出现的错误有：书写错误、公式错误。常出现的错误有：书写错误、公式错误。 容易求解容易求解。对线性规划来说，容易求解问题主要是控制。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。问题的规模，包括

19、决策变量的个数和约束条件的个数。这条原则的实现往往会与这条原则的实现往往会与(1)发生矛盾，在实现时需要对发生矛盾，在实现时需要对两条原则进行统筹考虑。两条原则进行统筹考虑。建立线性规划模型的四个步骤建立线性规划模型的四个步骤设立决策变量；设立决策变量；明确约束条件并用决策变量的线性等式或不明确约束条件并用决策变量的线性等式或不等式表示；等式表示；用决策变量的线性函数表示目标，并确定是用决策变量的线性函数表示目标，并确定是求极大（求极大（Max）还是极小（）还是极小（Min）；）；根据决策变量的物理性质研究变量是否有非根据决策变量的物理性质研究变量是否有非负性。负性。例例 某昼夜服务的公交线路

20、每天各时间段内所需司机和乘务某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：人员数如下： 人力资源分配的问人力资源分配的问题题设司机和乘务人员分别在各时间段一开始时上班，并连续设司机和乘务人员分别在各时间段一开始时上班，并连续工作工作8h，问该公交线路怎样安排司机和乘务人员，既能满，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员足工作需要，又配备最少司机和乘务人员?解解：设：设 xi 表示第表示第i班次时开始上班的司机和乘务班次时开始上班的司机和乘务人员数人员数,这样我们建立如下的数学模型。这样我们建立如下的数学模型。目标函数：目标函数：Min z

21、=x1 + x2 + x3 + x4 + x5 + x6 约束条件：约束条件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0 ，整数，整数例例某工厂要做某工厂要做100套钢架，每套用长为套钢架，每套用长为2.9 m, 2.1m, 1.5m的的圆钢各一根。已知原料每根长圆钢各一根。已知原料每根长7.4 m，问：应如何下料，问：应如何下料，可使所用原料最省？可使所用原料最省？套裁下料问题套裁下料问题解解:考虑下列各种下料方案（按一种逻辑顺序给出）考虑下列各种下料方案

22、（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出把各种下料方案按剩余料头从小到大顺序列出假设假设 x1,x2,x3,x4,x5 分别为上面前分别为上面前 5 种方案下料的原材料根数。种方案下料的原材料根数。我们建立如下的数学模型。我们建立如下的数学模型。目标函数：目标函数： Min z=x1 + x2 + x3 + x4 + x5 约束条件：约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3+ 3x5 100 x1,x2,x3,x4,x5 0假设假设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上

23、面前分别为上面前 8种方案下料种方案下料的原材料根数。我们建立如下的数学模型。的原材料根数。我们建立如下的数学模型。目标函数：目标函数： Min z = 0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8 约束条件：约束条件： s.t. 2x1+x2+x3+x4 100 2x2+x3 +3x5+2x6+x7 100 x1 +x3+3x4 +2x6+3x7+4x8 100 x1,x2,x3,x4,x5,x6,x7,x8 0，整数，整数设按第设按第i i种方案下料的原材料为种方案下料的原材料为x xi i根根 8 ,7 ,6 ,5 ,4 ,3 ,2 , 1ix100

24、 x4x3x2x0 x3xx0 x100 x0 xx2x3x0 xx2x0100 x0 x0 x0 x0 xxxx2. t . sxxxxxxxxZMini87654321876543218765432187654321为大于零的整数，为大于零的整数，组合方案组合方案 1 2 3 4 5 6 7 8 2.9m 2 1 1 1 0 0 0 0 2.1m 0 2 1 0 3 2 1 0 1.5m 1 0 1 3 0 2 3 4 合合 计计 7.3m 7.1m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料料 长长 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m

25、 7.4m 料料 头头 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m例例:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配加工和装配 三个车间。甲、乙两种产品的铸件可以外包三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由丙三种产品各生产多少件？甲、乙两种产品的

26、铸造中，由本公司铸造和由外包协作各应多少件？本公司铸造和由外包协作各应多少件？生产计划的问题生产计划的问题解：解：设设 x1 ， x2 ， x3分别为三道工序都由本公司加工的甲、分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，乙、丙三种产品的件数，x4 ， x5分别为由外协铸造再由分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。本公司机加工和装配的甲、乙两种产品的件数。求求 xi 的利润的利润:利润利润 = 售价售价 - 各成本之和各成本之和可得到可得到 xi（i=1,2,3,4,5）的利润分别为的利润分别为15、10、7、13、9元。元。 这样我们建立如下数学模型：这样

27、我们建立如下数学模型： 目标函数目标函数: Max z=15x1+10 x2+7x3+13x4+9x5 约束条件：约束条件： s.t. 5x1+10 x2+7x3 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 0例例:某工厂要用三种原料某工厂要用三种原料1、2、3混合调配出三种不同规格的产混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？利润收入为最大？配料问题配料问题解：解：设设 xij 表示第表示第

28、 i 种（甲、乙、丙）产品中原料种（甲、乙、丙）产品中原料 j 的的含量。这样我们建立数学模型时，要考虑：含量。这样我们建立数学模型时，要考虑： 对于甲：对于甲： x11，x12，x13； 对于乙：对于乙： x21，x22，x23； 对于丙：对于丙： x31，x32，x33； 对于原料对于原料1： x11，x21，x31； 对于原料对于原料2： x12，x22，x32； 对于原料对于原料3： x13，x23，x33；目标函数：目标函数：利润最大，利润利润最大，利润 = 收入收入 - 原料支出原料支出 约束条件：约束条件：规格要求规格要求 4 个；供应量限制个；供应量限制 3 个。个。Max z

29、 = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （原材料（原材料1不少于不少于50%） -0.25x11+0.75x12 -0.25x13 0 （原材料（原材料2不超过不超过25%） 0.75x21-0.25x22 -0.25x23 0 （原材料（原材料1不少于不少于25%） -0.5 x21+0.5 x22 -0.5 x23 0 （原材料（原材料2不超过不超过50%） x11+x21+x31 100 (供应量限制）供应量限制） x12+x22+x32 100 (供应量限制）供应

30、量限制） x13+x23+x33 60 (供应量限制）供应量限制） xij0 ,i = 1,2,3; j = 1,2,3例：例：某部门现有资金某部门现有资金200万元，今后五年内考虑给以下的项目万元，今后五年内考虑给以下的项目投资。已知：项目投资。已知：项目A ：从第一年到第五年每年年初都可投：从第一年到第五年每年年初都可投资，当年末能收回本利资，当年末能收回本利110%；项目；项目B：从第一年到第四年：从第一年到第四年每年年初都可投资，次年末能收回本利每年年初都可投资，次年末能收回本利125%，但规定每年，但规定每年最大投资额不能超过最大投资额不能超过30万元；项目万元；项目C：需在第三年年

31、初投资，：需在第三年年初投资，第五年末能收回本利第五年末能收回本利140%，但规定最大投资额不能超过，但规定最大投资额不能超过80万元；项目万元；项目D：需在第二年年初投资，第五年末能收回本利：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过，但规定最大投资额不能超过100万元。万元。 据测定每万元每次投资的风险指数如下表：据测定每万元每次投资的风险指数如下表： 投资问题投资问题a）应如何确定这些项目的每年投资额，使得第五年）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五

32、年）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在年末拥有资金的本利在330万元的基础上使得其投资万元的基础上使得其投资总的风险系数为最小？总的风险系数为最小？问：问：解：解：1）确定决策变量：连续投资问题）确定决策变量：连续投资问题 设设 xij ( i = 1-5，j = 1、2、3、4)表示第表示第 i 年初投资于年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们项目的金额。这样我们建立如下建立如下决策变量决策变量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x242）约束条件：）约束

33、条件： 第一年：第一年：A当年末可收回投资，故第一年年初应把全部当年末可收回投资，故第一年年初应把全部资金投出去，于是：资金投出去，于是： x11+ x12 = 200 第二年：第二年：B次年末才可收回投资故第二年年初的资金为次年末才可收回投资故第二年年初的资金为1.1x11，于是：，于是： x21 + x22+ x24 = 1.1x11 第三年：第三年：年初的资金为年初的资金为1.1x21+1.25x12，于是，于是 ： x31 + x32+ x33 = 1.1x21+ 1.25x12 第四年：第四年：年初的资金为年初的资金为1.1x31+1.25x22，于是：，于是： x41 + x42

34、= 1.1x31+ 1.25x22 第五年：第五年：年初的资金为年初的资金为1.1x41+1.25x32，于是：，于是： x51 = 1.1x41+ 1.25x32 B、C、D的投资限制：的投资限制： xi2 30 ( i=1，2，3，4 )， x33 80，x24 100a) Max z=1.1x51+1.25x42+1.4x33+1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11 x31 + x32+ x33 = 1.1x21+ 1.25x12 x41 + x42 = 1.1x31+ 1.25x22 x51 = 1.1x41+ 1.25x

35、32 xi2 30 ( i =1、2、3、4 )， x33 80，x24 100 xij0(i=1,2,3,4,5；j=1,2,3,4）3）目标函数及模型：）目标函数及模型：b) Min f = （x11+x21+x31+x41+x51)+ 3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 200 x21 + x22+ x24 1.1x11 x31 + x32+ x33 1.1x21+ 1.25x12 x41 + x42 1.1x31+ 1.25x22 x51 1.1x41+ 1.25x32 xi2 30 ( i =1、2、3、4 )， x33 80，x

36、24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij0(i=1,2,3,4,5；j = 1,2,3,4）第一章作业第一章作业6 6、7 7、8 8、9 9、1010、1212中任选三题中任选三题补充例题n(20050415-1)(20050415-1)某厂生产一种产品，该产品在未来某厂生产一种产品，该产品在未来5 5个月的个月的需求量、每个月最大生产能力和单位生产成本如下表所示：需求量、每个月最大生产能力和单位生产成本如下表所示：n另外，每件产品每月的存储费用为另外，每件产品每月的存储费用为2 2元，假定元，假定1 1月初库存为月初库存为5 5件。件

37、。n管理层希望制定合理的月生产计划，既满足需求又使总生管理层希望制定合理的月生产计划，既满足需求又使总生产成本最低。试建立此问题的一般线性规划模型。产成本最低。试建立此问题的一般线性规划模型。月份月份12345需求量需求量dj1115222315生产成本生产成本cj876410最大生产能力最大生产能力kj3122301516解解：设第：设第j月生产量为月生产量为xj件，需求量为件，需求量为dj ，上月未交货量，上月未交货量(第第j月初库存月初库存)为为sj-1，本月未交货量本月未交货量(第第j+1月初库存月初库存)为为sj，单位单位生产成本为生产成本为cj ，单位存储费为，单位存储费为B和最大

38、生产能力为和最大生产能力为kj。 则第则第j月所发生的产品流转与费用如下图所示：月所发生的产品流转与费用如下图所示：生产量：生产量： xj生产成本：生产成本： cjxj可支配量：可支配量： xj+ sj-1需求量：需求量： dj未交货量：未交货量： sj上季度未交货量：上季度未交货量： sj-1保管费用：保管费用： Bsj-1本月费用：本月费用：cj xj+ Bsj-1供应约束供应约束xjkjxj0需求约束需求约束xj+sj-1dj均衡约束均衡约束sj=xj+sj-1-dj ；s0=5 ，s5=0 27210 x6x10 x13x16x66xxxx43xxx21xx6x210 x4x6x7x8

39、xz16x15x30 x22x31x0 x,x,x,x,x1566xxxxx2343xxxx2221xxx156xx115xt . s27210 x6x10 x13x16xzMin54321432132121154321543215432154321432132121154321n(20050315-数运数运) 某船厂接受某船厂接受7艘船的订货，要求第一、二、艘船的订货，要求第一、二、三、四季度末分别交货三、四季度末分别交货1、1、2、3艘，该厂每季度的生产艘，该厂每季度的生产能力为能力为2艘，预计每季度生产成本为艘，预计每季度生产成本为4、6、7、9，各季度，各季度多生产的船可存在仓库中，每

40、艘船每季度的保管费用为多生产的船可存在仓库中，每艘船每季度的保管费用为1.2。n试制定一个完成订货合同且总费用最低的生产计划。试制定一个完成订货合同且总费用最低的生产计划。n分析分析：设第：设第j季度生产量为季度生产量为xj艘，需求量为艘，需求量为dj ，上季度未交，上季度未交货量为货量为sj-1，本季度未交货量为本季度未交货量为sj，单位生产成本为单位生产成本为cj ，单，单位保管费和最大生产能力为位保管费和最大生产能力为B和和K。生产量：生产量： xj生产成本：生产成本： cjxj可支配量：可支配量： xj+ sj-1需求量：需求量： dj未交货量：未交货量： sj上季度未交货量：上季度未

41、交货量： sj-1保管费用：保管费用： Bsj-1本季度费用：本季度费用：cj xj+ Bsj-1供应约束供应约束xj=0,1,2需求约束需求约束xj+sj-1dj均衡约束均衡约束sj=xj+sj-1-dj ；s4=0 79x2x. 84x. 87.6x4xxx2xx1x2 . 19x7x6x4xz0,1,2x,x,x,x34xxxx22xxx11xx1xt . s79x2x. 84x. 87.6xzMin43213212114321432143213212114321n(20020110)某厂生产某厂生产、三种产品，产品三种产品，产品依次经依次经过设备过设备A、B加工，产品加工，产品依次经过设备依次经过设备A、C加工，产品加工，产品依次经过设备依次经过设备B、C加工，已知有关数据如下表所示，加工，已知有关数据如下表所示，问如何安排生产计划才能获利最大？试建立该问题的线性问如何安排生产计划才能获利最大？试建立该问题的线性规划模型。规划模型。产品产品机器生产率机器生产率(件件/小时小时)原料成本原料成本(元元)产品价格产品价格(元元)ABCI102015