《运-筹-学》

1、运 筹 学,“运筹学”课题组,本章内容重点,第一章 线性规划,第一章 线性规划 线性规划是运筹学的一个重要分枝 自1947年美国数学家丹捷格（G. B. Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟,第一章 线性规划 从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥重要作用 具有适应性强、应用广泛、计算技术比较简单的特点，是现代管理科学的重要基础和手段之一,线性规划问题主要解决以下两类问题： 任务确定后，如何统筹安排，做到应用尽量少的人力和物力资源来完成任务； 在一定量的人力、物力资源的条件下，如何安

2、排、使用他们，使完成的任务最多。,第 一 节 线性规划的数学模型,例11：（计划安排问题）某工厂在计划期内安排生产、两种产品，已知生产单位产品所占用的设备A、B的台时、原材料的消耗及两种产品每件可获利润见表所示：,问如何安排计划使该工厂获利最多？,解: 假设 x1、x2分别表示在计划期内生产 产品I、II的件数，因为设备A的有效台时是15，所以在确定产品I、II的产量时，可用不等式表示为： 3x2 15,同理，因设备B的限制，有不等式： 4x1 12 原材料的限制，有不等式： 2x1+2x2 14 若用Z表示利润，则该工厂的利润值： Z = 2x1 +3x2（元）,综上所述，该工厂的计划问题可

3、用如下 数学模型表示为： 目标函数： Max Z = 2x1 +3x2 约束条件：,例12 (成本问题)某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨，计划从A，B两处运回原油提炼； 已知两处的原油成分含量见表12 ；从A处采购的原油价格为每吨（包括运费）200元，B处采购的原油价格为每吨（包括运费）290元；,问：该炼油厂该如何从A，B两处采购原油，在满足供应合同的条件下，使购买成本最小。,产品来源,成分,表12,分析：很明显，该厂可以有多种不同的方案从A，B两处采购原油，但最优方案应是使购买成本最小的一个，即在满足供应合同单位的前提下，使成本最小的一个采购方案。

4、,解：设分别表示从A，B两处采购的原油量（单位：万吨），建立的数学模型为：,由以上两个例子，我们会发现此数学模型具有如下特点： 有一组非负的决策变量； 有一组约束条件：含有决策变量的线性不等式(或等式)组； 有一个含有决策变量的线性目标函数，按研究问题的不同，要求目标函数实现最大化或最小化。,我们把满足上述三个条件的数学模型称为线性规划的数学模型。 其一般形式如下：,在该数学模型中： 方程(1.1)称为目标函数； (1.2)称为约束条件； (1.3)称为变量的非负约束条件。,由以上所举的例子可知，线性规划问题可能有各种不同的形式： 目标函数有实现最大化也有实现最小化的；约束条件可以是“”形式、

5、“”形式的不等式，也可以是等式。决策变量有时有非负限制，有时没有。 这种多样性给讨论问题带来了不便。,二、线性规划问题的标准型,这里我们假设bi 0 ( i = 1,2,m)，否则两端同时乘以“1”。用矩阵向量描述就是：,其中：C = ( c1, c2, , cn )T，X = ( x1, x2, , xn )T，b = ( b1, b2, , bm ), A = ( P1, P2, , Pn )T，Pj = ( a1j , a2j , , amj )T，0 = ( 0, 0, , 0 )T , ( j = 1, 2, , n )T。,为了便于今后讨论，我们规定线性规划问题的标准型为：,实际上

6、，具体问题的线性规划数学模型是各式各样的，需要把它们化成标准型，并借助于标准型的求解方法进行求解。 以下就具体讨论如何把一般的线性规划模型化成标准型。,我们称 A 为约束方程组的系数矩阵( mn阶)；一般情况下 m n , （m , n 为正整数，分别表示约束条件的个数和决策变量的个数）， C 为价值向量，X 为决策向量； 通常aij , bi , cj ( i = 1, 2, , m ，j = 1, 2, , n ) 为已知常数。,T,1. 若要求目标函数实现最小化，即此时的目标函数是： min Z=C X， 这时只需要将目标函数的最小值变换为求目标函数的最大值，即 MinZ=Max (-Z

7、) 。 令Z= -Z，于是就得到： Max Z= - C X 。,2. 若约束方程组为不等式，分两种情况： 约束条件为“ ” ：在“ ”号的左边加入非负的松弛变量； 约束条件为“ ”：在“ ”号的左端减去一个非负的剩余变量。 相应的松弛变量或剩余变量在目标函数 的价值系数取值为0。,3. 若存在无非负要求的变量。 即有某一个变量 xj 取正值或负值都可以，这时为了满足标准型对变量的非负要求，可令 xj = xj- xj, 其中： xj、 xj 0 ，由于xj可能大于也可能小于xj，故 xj 可以为正也可以为负。,上述的标准型具有如下特点： （1）目标函数求最大值； （2）所求的变量都要求是非负

8、的； （3）所有的约束条件都是等式； （4）常数项非负。,例13 将例11的数学模型化为标准型。 解：引进3个新的非负变量x3，x4，x5使不等式变为等式，标准型为：,例14 试将如下线性规划问题化成标准型,解：令 x3 = x4 - x5 , x4 , x5 0 , (1)式左端加上非负松弛变量 x6 ； (2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准型：,第二节 线性规划问题的图解法 及几何意义,一、线性规划问题的解的概念 由前面讨论可知线性规划问题的标准型：,1. 可行解: 满足约束条件(1.7)，(1.8)的解 X = ( x1, x2, , xn) 称为

9、线性规划问题的可行解；所有可行解的集合称为可行解集或可行域。 2. 最优解: 满足约束条件及目标函数(1.6)的可行解称为线性规划问题的最优解。,T,3. 基: 假设 A 是约束方程组的系数矩阵，其秩数为 m ，B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0)，则称 B 是线性规划问题的一个基。这就是说，矩阵 B 是由 m 个线性无关的列向量组成。,T,不失一般性，可假设: 称 Pj ( j = 1,2,m )为基向量，与基向量 Pj 相对应的变量xj ( j = 1,2,m )称为基变量，否则称为非基变量。,T,约束方程组(1.7)的求解问题： 假设该方程组系数矩阵 A

10、的秩为 m，因 m n，所以它有无穷多个解。假设前 m 个变量的系数列向量是线性无关的，这时(1.7)式可改写为：,方程组(1.9)的一个基是B=(P1, P2, ,Pm), Pj=(a1j, ,amj), (j = 1,2, , m )，设 XB 是对应于这个基的基变量，即： XB = ( x1, x2, , xm ) 现若令(1.9)式中的非基变量xm+1= =xn=0，并用高斯消去法求出一个解X=(x1,x2, ,xm,0, , 0 ) ，这个解的非0分量的数目不大于方程的个数m，这时称X为基本解。,T,T,4. 基本可行解 : 满足非负条件(1.8)的基本解称为基本可行解。由此可见，基

11、本可行解的非0分量的数目不大于m，并且都是非负的。,5. 可行基: 对应于基本可行解的基称为可行基。由此可见，满足约束方程组(1.7)的基本解的数目至多是 Cnm 个。一般地讲，基本可行解的数目要小于基本解的数目，至多相等。,以上提到的几种解的概念，可用图14来表示：,对于简单的线性规划问题(只有两个决策变量的线性规划问题)，我们可以通过图解法对它进行求解。我们以例11具体给出求解的方法。,二、线性规划问题的图解法,例15 用图解法求解线性规划问题 max Z = 2x1 +3x2,解：图1-2中的OABCD部分描述了满足约束条件的区域； 虚线为目标函数Z=2x1+3x2的等值线。 沿箭头方向

12、移动目标函数的等值线，平移等值线直至与可行域OABCD相切或融合为一条直线，此时就得到最优解为B点。,B点坐标可通过解方程组得到： 2x1+2x2=14 3x2=15 解得：x1=2 x2=5 这就是本线性规划问题的最优解。 此时相应的目标函数的最大值为： Z=22+35=19,例16 用图解法求解线性规划问题 maxZ=40 x1+ 80 x2 s.t. x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0,解：如图13所示： 求解最优解：BC线段 B点 X(1)= (6,12)；C点 X(2)= (15,7.5) X= X(1)+(1-) X(2) (0 1) max

13、Z=1200 即 x1 =6 +(1- )15 x2=12+(1- )7.5 整理得：x1 =15-9 x2 =7.5+4.5 (0 1),例17 maxZ=2x1+ 4x2 s.t. 2x1+x2 8 -2 x1+ x2 2 x1，x2 0,解：作目标函数等值线，如图14中虚线所示， 该问题无有限最优解。 若目标函数由 max Z = 2x1 + 4x2 改为 min Z =2 x1 +4 x2 , 则可行解所在的范围虽然无界， 但有最优解 x1 = 4，x2 = 0 ，即 (4,0)点。,通过以上各题图解法所得结论可以看出： （1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域

14、可能是无界的； （2）若存在最优解，则一定在可行域的某顶点得到；,（3）若在两个顶点上同时得到最优解，则在这两点的连线内的任一点都是最优解。 （4）若可行域无界，则可能发生最优解无界的情况； （5）若可行域是空集，此时无最优解。 上述理论具有普遍意义，对于两个 以上变量的线性规划问题都是成立。,图解法虽然具有直观、简便等优点，但在变量多的情况下，即在多维的情况下，它就无能为力了。 因此，需要介绍一种代数方法单纯型法，为了以后介绍方便，需要研究一下线性规划问题解的基本定理。,三、基本定理 1. 凸集：假设K是n维欧氏空间的一个点集，若对于K中的任意两点X1、X2，其连线上的所有点X1+(1-)X

15、2，( 0 1)都在集合K中，即：X1+(1-)X2 K ( 0 1) 则称K为凸集。 从直观上讲，凸集无凹入部分，其内部没有洞，如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。,2. 凸组合：设X1，X2，Xk是n维欧氏空间En中的k个点，若存在1，2，k，且0 i 1，i = 1,2, , k， i = 1，使X = 1X1 + 2X2 + + kXk，则称X为由X1，X2，Xk所构成的凸组合。 按照定义，凡是由x，y的凸组合表示的点都在x，y的连线上，而且反之亦然。,3. 顶点： 假设K是凸集，X K；X若不能用不同的两个点X1、X2 K的线性组合表示为： X = X1+

16、(1-)X2 ， ( 0 1) 则称X为凸集K的一个顶点（或称为极点）。 顶点不位于凸集K中的任意不同两点的连线内。,定理1.1 若线性规划问题存在可行域，则其可行域： D = X | AX = b , X 0 ，是凸集。 引理1.1 线性规划问题的可行解X为基本可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。,定理1.2 线性规划问题的基本可行解对应于可行域的顶点。 定理1.3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优解。 定理1.4 若线性规划问题在k个顶点上达到最优解 （k2），则在这些顶点的凸组合上也达到最优解。,根据以上讨论得到如下的结论：

17、 （1）线性规划问题的所有可行解的集合一般是凸集，它可以是有界的，也可以是无界的区域；仅有有限个顶点。 (2) 线性规划问题的每一个基本可行解对应于可行域的一个顶点。若线性规划问题有最优解，必定可在某顶点处取到。,(3) 如果一个线性规划问题存在多个最优解，那么至少有两个相邻的顶点处是线性规划的最优解。,虽然可行域的顶点个数是有限的(不超过 个)，采用“枚举法”可以找出所有基本可行解，最终找到最优解。 但当m、n的数目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。,单纯形算法的基本思路： 根据问题的标准型，从可行域中某个基本可行

18、解(顶点)开始，转换到另一个基本可行解(顶点)，并使得每次的转换，目标函数值均有所改善，最终达到最大值时就得到最优解。,第 三 节 单纯形算法,现在需要解决的问题是： (1) 为了使目标函数逐步变优，应如何从可行域的一个顶点转移到可行域的另一个顶点？ （2）目标函数何时达到最优值？判断标准是什么？,1确定初始基可行解 对于标准型的线性规划问题(简写为 LP)：,或 这里 A = ( aij)mn ，秩A = m 。,（1.9）,从中一般可以直接观察到存在一个初始可行基 B = ( P1, P2, Pm ),（1.10）,当线性规划的约束条件均为“”形式的不等式时，可以利用标准型的方法，在每个约

19、束条件的左端加上一个松弛变量，其松弛变量的系数矩阵即为单位矩阵；,对于约束条件为“ ”形式的不等式时，若不存在单位矩阵，就采用构造人造基的办法，即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；,对于等式约束，加上一个非负的人工变量。 这样总可以找到一个单位矩阵，关于这个方法将在本章第四节讨论。,（1.10）式中的P1,P2, Pm称为基向量，其对应的变量称为基变量，模型中其它变量称为非基变量。在约束条件中把非基变量项移到等式的右边得：,（1.11）,令所有非基变量 得 X = ( b1,b2, , bm, 0, , 0 ) ， 故X满足约束条件，所以它是一个基可行解。 式(1

20、.11)就是基变量用非基变量表示的形式。,T,2最优性检验 假定已求得(LP)的一个基本可行解 X(0) ，为叙述方便, 不失一般性，假设：,令所有非基变量 得 把式(1.12)代入目标函数得： 式（1.14）就是目标函数用非基变量表示的形式。,(1.12),（1.14）,于是,令,再令 ， 则得： （1.15） 在式（1.15）中，非基变量的系数 ，称为各非基变量 （ ）的检验数。,定理1.5 最优解判别定理: 若 为对应于基 B 的基本可行解，且对于一切 ，有 j 0，则 X 为线性规划问题的最优解。,（0）,定理1.6 无穷多最优解判别定理:若 为对应于基 B 的基本可行解，且对于一切

21、有 j 0，又存在某个非基变量的检验数 ，则线性规划问题有无穷多最优解。,定理1.7 无有限最优解判别定理： 若 为对应于基 B 的基本可行解，有一个 ，而对于 有 ，则线性规划问题无有限最优解(也称为无最优解)。,以上讨论的都是针对标准型的，即求目标函数极大化问题。当求目标函数极小化时，一种情况如前所述，将其化为标准型；另一种情况是将判别定理中的检验数j 0改为 即可。,（1）换入变量的确定 由式(1.15) 知，当某些非基变量的检验数j 0时，如果xj 增加，则目标函数值还可以增加。当有两个或两个以上j 0时，为了使目标函数值增加最快，我们一般选择j 0中的最大者，即：j = max ll

22、 0 j所对应的变量xj 为换入变量。,（2）换出变量的确定 确定换出变量的原则是保持解的可行性。即要使原基本可行解的某一个正分量x j 变为0，同时保持其余分量均非负。具体实现是按“最小比例原则”进行，也称原则。 若 则选基变量xl为换出变量。,（3）旋转运算（迭代运算） 在确定了换入变量x j与换出变量x l之后，要把x j和x l的位置对换，就是说，要把x j 所对应的列向量p j变成单位向量。这时只需对系数矩阵的增广矩阵进行变换即可，称a l j为旋转元。,表13 初始单纯形表,以表13中的元素alj (称为主元素或旋转元素)进行基变换：将第l行每个元素除以 alj，再将第 l行每个元

23、素乘以 aij / alj 加到第 i 行( i = 1,2, ,m , i l )，将第 l 行每个元素乘以 j / alj 加到检验数行，对应的新的目标函数值即为：,经过基变换之后，针对于新基 B1 的基本可行解为：,单纯形算法的计算步骤可归结如下： 第一步：找出初始可行基，确定初始基本 可行解，建立初始单纯形表； 第二步：检查对应于非基变量的检验数 k ，kIN ，(IN为非基变量指标集)，若所有 k 0 ，kIN ，则已得到最优解，停止计算，否则转入下一步；,第三步：在所有k 0，kIN 中，若有一个j 对应的系数列向量 aij 0，则此问题没有有限最优解，停止计算，否则转入下一步；,

24、第四步：根据 max kk 0，kIN = j，确定 xj 为换入变量(即为新基的基变量)，再根据： 确定 xl 为换出变量(即为新基的非基变量)，转下一步； 第五步：以 alj 为主元素进行基变换，转回第二步。,例18 利用单纯形算法求解例11的线性规划问题。 Max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 4x1+x4=12 2x1+2x2x5=14 x1，x2，x3，x4，x50,解： （1）由标准型得到初始单纯形表：,(2) max1, 2=3=2，所以x2为换入变量。 (3) 因为1=2，2=3都大于0，且p1,p2的坐标有正分量存在 因为5与x3那一行

25、相对应，所以x3为换出变量； 故x2对应列与x3对应行的相交处的3为主元素；,(4) 以“3”为主元素进行旋转计算，进行行初等变换，得表15：,表15,重复以上步骤得表16。,表16,这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解： X*=(2,5,0,4,0) 目标函数的最大值为： Z*=19,T,例19 利用单纯形算法求解线性规划问题。 Max Z=4x1+3x2+0 x3+0 x4+0 x5 2x1+2x2+ x3=1600 5x1+2.5x2+x4=2500 x1+x5 =400 x1, x2, x3, x4, x50,解： （1）由标准型得到初始单纯形表17：,

26、表17,表18,表19,表110,这时，检验数全部小于等于0，即目标函数已达到最大，因此得到最优解： X=(200,600,0,0,200) 目标函数的最大值为： Z=2600,T,例110 利用单纯形算法求解线性规划问题。 MaxZ=2x1+3x2+0 x3+0 x4+0 x5+0 x6 2x1+2x2+x3=12 x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1，x2，x3，x4，x5, x60,解： （1）由标准型得到初始单纯形表：,表111,表112,表113,表113出现了“退化”问题， 同时如果出现有两个或更多的检验数大于零且相同时，在相同 对应的变量中选择下标

27、最小的那个基变量为进入变量，这样会避免出现“死循环”的现象。,表114,这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解： X*=(4,2,0,0,0,4) 目标函数的最大值为： Z*=14,T,利用单纯形算法的一个根本前提是要有一个初始的基本可行解。这就引起了人们对求初始基本可行解的思考。 以下我们分几种情形对该问题加以讨论。,第四节 单纯形算法的进一步讨论,1对于 AX = b，若人们一下就可以从其中求得一个单位矩阵。这时取初始基B 就是单位矩阵，对应的基变量为 XB，非基变量为 XN 。这时 然后按单纯形算法计算步骤便可得到。这种情况包含了 AX b 的情形。,2.

28、对于 AX = b，并且不能够从中观测到一个单位矩阵。这时分别给每一个约束条件加入一个人工变量 xn+1, , xn+m , 得:,(0),二、人工变量法(大M法) 对于加入人工变量的线性规划问题，我们希望人工变量对目标函数取值不受影响。因此只有在迭代过程中，把人工变量从基变量中换出，让它成为非基变量。,为此，就必须假定人工变量在目标函数中的价值系数为(-M)(对于极大化目标)，M为充分大的正数。这样，对于要求实现目标函数最大化的问题来讲，只要在基变量中还存在人工变量，目标函数就不可能实现最大化。这就是大M法。以下举例加以说明。,例1-11 试用大M法求解如下线性规划问题的最优解。,解:在上述

29、问题中加入松弛变量,剩余变量和人工变量得：,这里M是一个 充分大的正数,取基变量为 x4 , x6 , x7 , 可得如下的表115,表115,由于x4 , x6 , x7为基变量，因此它们对应的检验数行的检验数应为0，经变换得初始单纯形表。,表1-16,表119,继续用单纯形法求解，可得下表,在表119中，所有的 j 0， 故得到最优解： X* = ( 4, 1, 9, 0, 0, 0, 0 ) 目标函数值 Z= 2 , 原问题的最优目标值为: Z* = -2 。,T,三、 两阶段法: 这种方法是在约束条件中加入人工变量，将线性规划问题分为两阶段进行求解。 第一阶段是先求出基本可行解 (或判

30、断出原线性规划问题无解)， 第二阶段利用已求出的初始基本可行解来求最优解。具体由如下定理1.8给出。,定理1.8 设原线性规划问题记成(LP)，由它而引入的新的线性规划问题记成(LP)*。分别表示如下：,若(LP)*具有最优基本可行解 则(LP)是可行的， 而 即为(LP)的一个基可行解。,2) 若(LP)*的最优基本可行解 则(LP) 必不可行。,例112 试用两阶段法求解如下线性规划问题,解：先在以上问题的约束条件中加入松弛变量、剩余变量、人工变量，给出第一阶段的线性规划问题：,以x4 , x6 , x7 为基变量得如下初始表120,表120,x6、x7 是人工变量。第一阶段我们已求得 W

31、 = 0，最优解 x5 = 0，x6 = 0，x7 = 0。因人工变量 x6 = x7 = 0，所以( 0, 1, 1 ,12, 0 )T 是原问题的基本可行解。于是可以开始第二阶段的计算。,表125中所有检验数 j 0，所以 x1 = 4，x2 = 1 , x3 = 9 是原线性规划问题的最优解。 目标函数值： Z* = 2,表125,四、检验数的几种表示方法 我们以 作 为标准型，以作为最优解的判别准则。还有其它形式，下面把几种检验数的表示方法及判别准则汇总于表126。,表126,标准型,检验数,对于目标函数求极小值的问题采用上述任何一种处理方法，其单纯形法的步骤与求极大值的方法相同。,这

32、里提醒读者注意，在阅读其它有关线性规划的教科书时，一定要注意该书规定的标准型是目标函数求极大值还是求极小值，检验数是cj-zj还是zj-cj，不同的组合会使判别准则不同，但单纯形的计算步骤是不变的。,线性规划的应用非常广泛，特别是在经济管理领域有大量的实际问题可以归纳为线性规划问题来研究。尽可能多地掌握一些典型模型不仅有助于深刻理解线性规划本身的理论，而且有利于灵活地处理千差万别的问题。下面举例说明线性规划在经济管理方面的应用。,第五节 应用举例,例113（投资问题） 已知某集团有1,000,000元的资金可供投资，该集团有五个可供选择的投资项目，其中各种资料如下：,表1-27,该集团的目标为

33、：每年红利至少是80,000元，最低平均增长率14%，最低平均信用度为6，该集团应如何安排投资，使投资风险最小？,解: 设xi表示第 i项目的投资额 i =1,2,3,4,5， 目标是投资风险最小化， 因此目标函数为： min z = ( 0.1x1 + 0.06x2 +0.18x3 + 0.12x4+ 0.04x5 ),数学模型为： min z = 0.1x1 + 0.06x2 +0.18x3 + 0.12x4+ 0.04x5 x1 + x2 + x3 + x4+ x5 = 1,000,000 0.05 x1 + 0.08 x2 + 0.07 x3 + 0.06 x4+ 0.1 x5 80,

34、000 0.1x1 + 0.17 x2 + 0.14 x3 + 0.22 x4+0.07 x5140,000 (11 x1 + 8 x2 + 10 x3 + 4 x4+10 x5)/56 xi 0 ( i =1,2,3,4,5) 用单纯形法可计算出结果。,表111,在表111中，所有的 j 0， 故得到最优解： X* = ( 4, 1, 9, 0, 0, 0, 0 )T 目标函数值 Z= 2 , 原问题的最优目标值为: Z* = -2 。,例114（配料问题） 某工厂要用三种原材料 C、P、H 混合调出三种不同格的产品 A、B、D 。已知产品的规格要求、产品单价、每天能供应的原材料数量及原材料

35、单价分别见表1-28、表1-29。,问该厂应如何安排生产，使利润收入为最大？,表1-28,表1-29,1) 若(LP)*具有最优基本可行解,则(LP)是可行的,而,2) 若(LP)*的最优基本可行解,则(LP)必不可行。,解：依条件有：,又由于原料总限额已给定，加入到产品 A、B、D的原材料 C 总量每天不超过100kg ，P 总量不超过100kg，H 总量不超过60kg 。由此有： AC + BC + DC 100 AP + BP + DP 100 AH + BH + DH 60,我们的目的是使利润最大， 即产品价格减去原材料的价格为最大。 目标函数： MaxZ = 50(x1+x2+x3)

36、+35(x4+x5+x6) +25(x7+x8+x9)-65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3+ x6+x9) = -15x1 + 25x2 + 15x3 30 x4 + 10 x5 + 0 x6 40 x7 + 0 x8 10 x9,约束条件： -1/2 x1 + 1/2x2 + 1/2x3 0 -1/4x1 + 3/4x2 1/4x3 0 -3/4x4 + 1/4x5 + 1/4x6 0 -1/2x4 + 1/2x5 1/2x6 0 x1 + x4 + x7 100 x2 + x5 + x8 100 x3 + x6 + x9 60 x1， ，x9 0,上述数

37、学模型，可用单纯形表计算， 计算结果是： 每天只生产产品 A 200 kg ， 分别需要用原料 C 100 kg；P 50 kg ；H 50 kg 。 总利润收入是 Z = 500 元/天 。,例115（连续投资问题） 某部门在今后5年内考虑给下列项目投资，已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%； 项目B：第三年年初需要投资，到第五年年末能回收本利125%，但规定最大投资额不超过4万元；,项目C：第二年年初需要投资，到第五年年末能回收本利140%，但规定最大投资额不超过3万元； 项目D：五年内每年年初可购买公债，于当年年末归还，并加利息6%。,已知该部门现有资金10万， 问它应如何确定给这些项目每年的投资额，使到第五年年末拥有资金的本利总额为最大？,解：(1) 确定变量，设： xiA ：表示第 i 年年初给项目 A 的投资额 i = 1 , , 5； xiB ：表示第 i 年年初给项目 B 的投资额 i = 1 , , 5； xiC ：表示第 i 年年初给项目 C 的投资额 i = 1, , 5； xi