运筹学单纯形算法课件

。：解：对于上述具有两个变量的线性规划问题，图1-2中的

OABCD部分描述了满足约束条件的区域；虚线为目标函数

Z=2x1+3x2的等值线。沿箭头方向移动目标函数的等值线，平移等值线直至与可行域OABCD相切或融合为一条直线，此时就得到最优解为B点，其坐标可通过解方程组得到：2x1+2x2=143x2=15解得：x1=2x2=5这就是本线性规划问题的最优解此时相应的目标函数的最大值为Z=2×2+3×5=191例1－6

用图解法求解线性规划问题maxZ=40x1+80x2s.t.x1+2x2

303x1+2x2

602x2

24x1

,x2

0解：如图1－3所示：求解最优解：BC线段B点

X(1)=

(6,12)；C点

X(2)=

(15,7.5)X=α

X(1)+(1-α)

X(2) (0

α

1)maxZ=1200即

x1

=6α

+(1-

α

)·15x2=12α+(1-

α

)·7.5整理得：x1

=15-9αx2

=7.5+4.5α

(0≤

α

≤

1)2例1－7maxZ=2x1+4x2s.t. 2x1+x2

8-2x1+

x2

2x1，x2

0解：由于可行域无界，作目标函数等值线，如图1－4中虚线所示，并用箭头标出其函数值增加的方向，由此可以看出，该问题无有限最优解。若目标函数由max

Z=2x1

+4x2改为min

Z=2

x1

+4

x2

,则可行解所在的范围虽然无界，但有最优解x1

=4，x2

=0

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

≤1)都在集合K中，即：αX1+(1-α)X2

∈K

(0≤α

≤1)则称K为凸集。从直观上讲，凸集无凹入部分，其内部没有洞。如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。凸组合：设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的连线上，而且反之亦然。顶点：假设K是凸集，X

∈K；X若不能用不同的两个点X1、X2∈K的线性组合表示为：X

=

αX1+(1-α)X2

，

(0<

α

<

1)则称X为凸集K的一个顶点（或称为极点）。顶点不位于凸集K中的任意不同两点的连线内。5定理1.1

若线性规划问题存在可行域，则其可行域：D

={X|AX=b,X

0}，是凸集。引理1.1

线性规划问题的可行解X为基本可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。定理1.2

线性规划问题的基本可行解对应于可行域的顶点。定理1.3

若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优解。定理1.4

若线性规划问题在k个顶点上达到最优解（k

2），则在这些顶点的凸组合上也达到最优解。6根据以上讨论得到如下的结论：7线性规划问题的所有可行解的集合一般是凸集，它可以是有界的，也可以是无界的区域；仅有有限个顶点。线性规划问题的每一个基本可行解对应于可行域的一个顶点。若线性规划问题有最优解，必定可在某顶点处取到。如果一个线性规划问题存在多个最优解，那么至少有两个相邻的顶点处是线性规划的最优解。虽然可行域的顶点个数是有限的(它们不超过Cnm

个)，采

用“枚举法”可以找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。但当m、n的数目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。第

三

节 单纯形算法8单纯形算法的基本思路是：根据问题的标准型，从可行域中某个基本可行解(顶点)开始，转换到另一个基本可行解(顶点)，并使得每次的转换，目标函数值均有所改善，最终达到最大值时就得到最优解。从线性规划解的性质定理可知，线性规划问题的可行域是凸多边形或凸多面体，而且如果一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。换言之，若某线性规划只有唯一的一个最优解，那么这个最优解所对应的点一定是可行域的一个顶点，若该线性规划有多个最优解，那么它一定可以在可行域的顶点中找到至少两个最优解。现在需要解决的问题是：(1)为了使目标函数逐步变优，应如何从可行域的一个顶点转移到可行域的另一个顶点？（2）目标函数何时达到最优值？判断标准是什么？1．确定初始基可行解对于标准型的线性规划问题(简写为LP)：或（1.9）这里A

=(aij)m

n

，秩A=m。9从中一般可以直接观察到存在一个初始可行基B=

(P1,P2,···,Pm

)（1.10）当线性规划的约束条件均为“”形式的不等式时，可以利用标准型的方法，在每个约束条件的左端加上一个松弛变量，其松弛变量的系数矩阵即为单位矩阵；对于约束条件为“”形式的不等式或等式时，若不存在单位矩阵，就采用构造人造基的办法，即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束，加上一个非负的人工变量。这样总可以找到一个单位矩阵，关于这个方法将在本章第四节10讨论。（1.10）式中的P1,P2,···,Pm称为基向量，其对应的变量称为基变量，模型中其它变量称为非基变量。在约束条件中把非基变量项移到等式的右边得：（1.11）令所有非基变量 ，得X=

(b1,b2,···,bm,0,···,0)又由于，故X满足约束条件，所以它是一个基可行解。式(1.11)就是基变量用非基变量表示的形式。T11令所有非基变量，得把式(1.12)代入目标函数得：式（1.14）就是目标函数用非基变量表示的形式。2．最优性检验假定已求得(LP)的一个基本可行解X(0)

，为叙述方便,不失一般性，假设：(1.12)（1.13）（1.14）12令，，于是再令，则得：（1.15），称为各非基变量在式（1.15）中，非基变量的系数（ ）的检验数。13定理1.5

最优解判别定理:若，有σj定理1.6

无穷多最优解判别定理:若为对应于基B的基本可行解，且对于一切，有σj

0，，则线性规划问题有无又存在某个非基变量的检验数穷多最优解。定理1.7

无有限最优解判别定理：

若

为对应于基

B的基本可行解，有一个 ，而对于有 ，则线性规划问题无有限最优解(也称为无最优解)。以上讨论的都是针对标准型的，即求目标函数极大化问题。当求目标函数极小化时，一种情况如前所述，将其化为标准型；另一种情况是将判别定理中的检验数σj

0改为即可。为对应于基B的基本可行解，且对于一切

0，则X（0）为线性规划问题的最优解。143.基变换15若上面所求的基可行解还不是最优解，下面我们将介绍，如何通过基(0)变换，求一个新的可行解？如何保证基变换后新的目标函数更优？若初始基可行解X

不是最优解及不能判别无界时，需要找一个新的基可行解，即进入迭代过程，具体做法是从原可行解基中用一个非基列向量换一个基列向量（换后当然要保证这些向量线性无关），得到一个新的基可行解基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就找到一个新的基可行解。3.基变换16（1）换入变量的确定由式(1.15)可知，当某些非基变量的检验数σj

>0时，如果xj增加，则目标函数值还可以增加。当有两个或两个以上σj

>0时，那么选哪个非基变量作为换入变量呢？为了使目标函数值增加的最快，我们一般选择σj

>0中的最大者，即：σj

=

max

{σl∣σl

>

0

}σj所对应的变量xj为换入变量(就是下一个基的基变量)。（2）换出变量的确定因为基变量个数总是为m，所以换入一个变量之后还必须换出一个变量。下面我们来考虑如何选择换出变量。确定换出变量的原则是保持解的可行性。这就是说，要使原基本可行解的某一个正分量xj变为0，同时保持其余分量均非负。具体实现是按“最小比例原则”进行，也称θ原则。若则选基变量xl为换出变量。17（3）旋转运算（迭代运算）在确定了换入变量xj与换出变量xl之后，要把xj和xl的位置对换，就是说，要把xj所对应的列向量pj变成单位向量。这时只需对系数矩阵的增广矩阵进行变换即可，称alj为旋转元。18单纯形表XB列中填入基变量，这里是x1，x2,…，xm；CB列中填入基变量的价值系数，这里是c1,c2,…,cm；它们是与基变量相对应的；b列中填入约束方程组右端的常数；cj行中填入基变量的价值系数c1,c2,…,cn；θi列的数字是在确定换入变量后，按θ规则计算后填入；最后一行称为检验数行，对应各非基变量xj的检验数是19cjc1…ck…cmcm+1…cj…cnθCBXBb*x1…xk…xmxm+1…xj…xnc1x1b1*1…0…0a1m+1…a1j…a1n………………………ClXlBl*0…1…0alm+1…alj…aln………………………cmxmbm*0…0…1amm+1…amj…amnC

-CB

B

AT

-10…0…0σm+1…σj…σn20表1—3初始单纯形表以表1—3中的元素alj(称为主元素或旋转元素)进行基变换：将第l行每个元素除以alj，再将第l行每个元素乘以–aij/alj

加到第i行(i=1,2,···,m,i≠l)，将第l行每个元素乘以–σj/alj

加到检验数行，对应的新的目标函数值即为：经过基变换之后，针对于新基B1的基本可行解为：21综合以上的讨论，单纯形算法的计算步骤可归结如下：22第一步：找出初始可行基，确定初始基本可行解，建立初始单纯形表；第二步：检查对应于非基变量的检验数σk

，k∈IN，(IN为非基变量指标集)，若所有σk≤0

，k∈IN

，则已得到最优解，停止计算，否则转入下一步；第三步：在所有σk>0，k∈IN

中，若有一个σj

对应的系数列向量aij

≤0，则此问题没有有限最优解，停止计算，否则转入下一步；第四步：根据max{σk∣σk>0，k∈IN

}=σj，确定xj

为换入变量(即为新基的基变量)，再根据：确定xl

为换出变量(即为新基的非基变量)，转下一步；第五步：以alj

为主元素进行基变换，转回第二步。23例1－8利用单纯形算法求解例1－1的线性规划问题。Max

Z=2x1+3x2+0·x3+0·x4+0·x53x2+x3=15244x1+x4=122x1+2x2＋x5=14x1，x2，x3，x4，x5≥0解：（1）由标准型得到初始单纯形表：cj23000θiXBbx1x2x3x4x5x3150[3]1005x41240010x514220017-Z023000(2) max{

1,

2}=3=

2，所以x2为换入变量。(3)

因为

1=2，

2=3都大于0，且p1,p2的坐标有正分量存在因为θ＝5与x3那一行相对应，所以x3为换出变量；故x2对应列与x3对应行的相交处的3为主元素；(4)以“3”为主元素进行旋转计算，进行行初等变换，得表1—5：表1—5cj23000θiXBbx1x2x3x4x5x25011/300x412400103x54[2]0-2/3012-Z-1520-10025重复以上步骤得表1—6。26表1—6目标函数的最大值为：Z*=19cj23000θiXBBx1x2x3x4x5x25011/300x44004/31-2x1210-1/301/2-Z-1900-1/30-1这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解：X*=(2,5,0,4,0)T例1－9利用单纯形算法求解线性规划问题。Max

Z=4x1+3x2+0·x3+0

·

x4+0

·

x5272x1+2x2+

x3=16005x1+2.5x2+x4=2500x1+x5

=400x1,x2,x3,x4,x5≥0解：（1）由标准型得到初始单纯形表1－7：表1—7cj43000θiXBbx1x2x3x4x5x3160022100800x4250052.5010500x5400[1]0001400-Z043000表1－828cj43000θiXBbx1x2x3x4x5x38000210-2400x45000[2.5]01-5200x140010001--Z-16000300-4表1－9cj43000θiXBbx1x2x3x4x5x3400001-0.8[2]200x22000100.4-2-x140010001400-Z-2200000-1.22表1－1029cj43000θiXBbx1x2x3x4x5x5200000.5-0.41x2600011-0.40-x120010-0.50.40-Z-260000-1-0.40这时，检验数全部小于等于0，即目标函数已达到最大，因此得到最优解：X=(200,600,0,0,200)T目标函数的最大值为：Z=2600例1－10利用单纯形算法求解线性规划问题。Max

Z=2x1+3x2+0·x3+0·x4+0·x5+0·x62x1+2x2+x3=1230x1+2x2+x4=84x1+x5=164x2+x6=12x1，x2，x3，x4，x5,x6≥0解：（1）由标准型得到初始单纯形表：表1—11cj230000θiXBbx1x2x3x4x5x6x3122210006x481201004x516400010x6120[4]00013-Z0230000表1—1231cj230000θiXBbx1x2x3x4x5x6x3620100-1/23x42[1]0010-1/22x5164000104x23010001/4-Z-920000-3/4表1—13cj230000θiXBbx1x2x3x4x5x6x32001-201/24x1210010-1/2x58000-41[2]4x23010001/412-Z-13000-201/4在求解过程中，有时会出现两个或更多的

相同的问题，这种情况出现时，我们称之为出现了退化问题。表1—13就出现了退化问题，在出现退化问题时，即有两个或更多的

相同时，在相同

对应的变量中选择下标最大的那个基变量为换出变量；同时如果出现有两个或更多的检验数σ大于零且相同时，在相同σ对应的变量中选择下标最小的那个基变量为进入变量，这样会避免出现“死循

环”的现象。表1—14cj230000θiXBbx1x2x3x4x5x6x30001-1-1/40x1410011/40x64000-21/21x220101/2-1/80-Z-14000-3/2-1/80这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解：X*=(4,2,0,0,0,4)目标函数的最大值为：

Z*=14T32第四节 单纯形算法的进一步讨论一、初始基本可行解的确定利用单纯形算法的一个根本前提是要有一个初始的基本可行解。这对于一些简单问题，利用观察或其它手段是容易得到的；但对于较复杂的问题，利用这种方法几乎是不可行的。这就引起了人们对求初始基本可行解的思考。以下我们分几种情形加以讨论。1．对于AX=b，若人们一下就可以从其中求得一个单位矩阵。这时取初始基B就是单位矩阵，对应的基变量为XB，非基变量为XN

。这时然后按单纯形算法计算步骤便可得到。这种情况包含了AX≤b的情形。332.

对于AX=b，并且不能够从中观测到一个单位矩阵。这时分别给每一个约束条件加入一个人工变量xn+1,…,xn+m

,得:由此可以得到一个m阶单位矩阵。以xn+1，…，xn+m为基变量，令非基变量x1，…，xn

为0，便可得到一个初始基本可行解X

(0)；X

(0)

=(0,

,0,b1

,

,bm

)T。因为人工变量是后加入到原约束方程组中的虚拟变量，我们要求将它们从基变量中逐渐替换掉。若经过基的变换，基变量中不再包含

有人工变量，这就表示原问题有解；若经过基变换，当所有的σj

0时，而在基中至少还有一个人工变量，这就意味着原问题无可行解。34二、人工变量法(大M法)35对于加入人工变量的线性规划问题的目标函数如

何处理？我们希望人工变量对目标函数取值不受影响。因此只有在迭代过程中，把人工变量从基变量中换出，让它成为非基变量。为此，就必须假定人工变量在目

标函数中的价值系数为(-M)(对于极大化目标)，M为充分大的正数。这样，对于要求实现目标函数最大化的

问题来讲，只要在基变量中还存在人工变量，目标函

数就不可能实现最大化。这就是大M法。以下举例加以说明。例1-11

试用大M法求解如下线性规划问题的最优解。解:在上述问题中加入松弛变量,剩余变量和人工变量得：这里M是一个充分大的正数，取基变量为x4,x6,x7,可得如下的表1—15。利用表1—15得初始单纯形表，单纯形算法得表1—16～表1—19。36表1—1537cj3-1-100-M-MXBbx1x2x3x4x5x6x7x4111-211000x63-4120-110x71-20[1]0001-Z03-1-100-M-M由于x4,x6,x7为基变量，因此它们对应的检验数行的检验数应为0，经变换得初始单纯形表1—16。初始单纯形表1—16cj3-1-100-M-MθXBbx1x2x3x4x5x6x7x4111-21100011x63-4120-1101.5x71-20[1]00011-Z4M3-6MM-13M-10-M00表1—1738cj3-1-100-M-MθXBbx1x2x3x4x5x6x7x4103-20100-1—x610[1]00-11-21x31-2010001—-ZM+11M-100-M01-3M表1—18cj3-1-100-M-MθXBbx1x2x3x4x5x6x7x412[3]001-22-54x210100-11-2—x31-2010001—-Z21000-11-M-1-M表1—1939cj3-1-100-M-MθXBbx1x2x3x4x5x6x7x141001/3-2/32/3-5/3x210100-11-2x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-M在表1—19中，所有的σj

0，故得到最优解：X*=

(4,1,9,0,0,0,0)T目标函数值Z′=2,原问题的最优目标值为:Z*=-2。三、两阶段法:这种方法是在约束条件中加入人工变量，将线性规划问题分为两阶段进行求解。第一阶段是先求出基本可行解(或判断出原线性规划问题无解)，第二阶段利用已求出的初始基本可行解来求最优解。具体由如下定理1.8给出。定理1.8

设原线性规划问题记成(LP)，由它而引入的新的线性规划问题记成(LP)*。分别表示如下：40则(LP)是可行1)

若(LP)*具有最优基本可行解的，而 即为(LP)的一个基可行解。2)

若(LP)*的最优基本可行解 则(LP)

必不可行。定理1.8的具体应用过程是：由(LP)*判断原线性规划问题是否存在基本可行解，利用单纯形算法，若得到W

=0，即所有人工变量为非基变量，这表示原问题已得到了一个基本可行解。于是只需要将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字，就得到了求解原问题的初始计算表，再进行第二阶段的求解。若第一阶段的最终计算表出现

W>0，这就表明原问题无可行解，应停止计算。各阶段的计算方法及步骤与前述单纯形法完全相同，下面用例子说明该方法的应用。41例1－12

试用两阶段法求解如下线性规划问题42解：先在以上问题的约束条件中加入松弛变量、剩余变量、人工变量，给出第一阶段的线性规划问题：以x4,x6,x7为基变量得如下初始表1—20。表1—20cj00000-1-1XBbx1x2x3x4x5x6x7x4111-211000x63-4120-110x71-2010001-W'000000-1-143初始单纯形表1—2144cj00000-1-1θXBbx1x2x3x4x5x6x7x4111-21100011x63-4120-1101.5x71-20[1]00011-W'4-6130-100表1—22cj00000-1-1θXBbx1x2x3x4x5x6x7x4103-20100-1—x610[1]00-11-21x31-2010001—-W'10100-10-3表1—23cj00000-1-1θXBbx1x2x3x4x5x6x7x4123001-22-5x210100-11-2x31-2010001-W'000000-1-1这里x6、x7

是人工变量。第一阶段我们已求得W

´=

0，最优解x5=0，x6=0，x7=0。因人工变量x6=x7=0，所以(0,1,1,12,0)T是原问题的基本可行解。于是可以开始

第二阶段的计算。将第一阶段的最终计算表1—23中的人工变量列取消，并将目标函数系数换成原问题的目标函数系

数，重新计算检验数行，可得如下第二阶段的初始单纯形表1—24；应用单纯形算法求解得最终表1—25。45表1—24cj3-1-100θXBbx1x2x3x4x5x412[3]001-24x210100-1—x31-20100—-Z'21000-1表1—25cj3-1-100θXBbx1x2x3x4x5x141001/3-2/3x210100-1x390012/3-4/3-Z'-2000-1/3-1/3表1—25中所有检验数

σj

0，所以

x1

=

4，x2

=

1

,

x3

=

9

是原线性规划问题的最优解。目标函数值：

Z*

=

246四、检验数的几种表示方法我们以

作

为标准型，以作为最优解的判别准则。还有其它形式，下面把几种检验数的表示方法及判别准则汇总于表1－26。表1－26标准型检验数σMax

Z=CTXAX=b,X≥0Min

Z=CTXAX=b,X≥0cj-zj≥0≤0zj-cj≤0≥0对于目标函数求极小值的问题采用上述任何一种处理方法，其单纯形法的步骤与求极大值的方法相同。这里提醒读者注意，在阅读其它有关线性规划的教科书时，一定要注意该书规定的标准型是目标函数求极大值还是求极小值，检验数是cj-zj还是zj-cj，不同的组合会使判别准则不同，但单纯形的计算步骤是不变的。47第五节 应用举例48线性规划的应用非常广泛，特别是在经济管理领域有大量的实际问题可以归纳为线性规划问题来研究，有些问题，它的背景不同，表现各异，但它们的数学模型却有着完全相同的形式。尽可能多地掌握一些典型模型不仅有助于深刻理解线性规划本身的理论，而且有利于灵活地处理千差万别的问题，提高解决实际问题的能力。下面举例说明线性规划在经济管理方面的应用。例1－13（投资问题）已知某集团有1,000,000元的资金可供投资，该集团有五个可49供选择的投资项目，其中各种资料如下：表1-27投资项目风险%红利%增长%信用度110510112681783187141041262245410710该集团的目标为：每年红利至少是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.04x5x1

+

x2+

x3

+

x4+

x5

=

1,000,0000.05x1

+

0.08x2

+

0.07x3

+

0.06x4+

0.1x5≥

80,0000.1x1

+

0.17x2

+

0.14x3

+

0.22x4+0.07x5≥140,000(11

x1

+

8x2

+

10x3

+

4x4+10x5)/5≥6xi

≥

0(i

=1,2,3,4,5)用单纯形法可计算出结果。50cj3-1-100-M-MθCBXBb*x1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-M表1—11在表1—11中，所有的σj

0，故得到最优解：X*

=

(4,

1,9,0,

0,0,0

)T目标函数值Z′=2,原问题的最优目标值为:Z*

=-2

。51例1－14（配料问题）某工厂要用三种原材料C、P、H

混合调出三种不同格的产品A、B、D。已知产品的规格要求、产品单价、每天能供应的原材料数量及原材料单价分别见表1-28、表1-29。问该厂应如何安排生产，使利润收入为最大？表1-28产品名称规 格

要

求单价(元/kg)A原材料C

不少于50%原材料P不超过25%50B原材料C

不少于25%原材料P不超过50%35D不

限25表1-29原材料名称每天最多供应量(kg)单价(元/kg)C10065P10025H6035521)

若(LP)*具有最优基本可行解则(LP)是可行的,而2)

若(LP)*的最优基本可行解则(LP)必不可行。定理5的具体应用过程是:(LP)*判断原线性规划问题是否存在基本可行解,利用单纯形算法,若得到W=0,即所有人工变量为非基变量,这表示原问题已得到了一个基本可行解.于是只需要将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字,就得到了求解原问题的初始计算表,再进行第二阶段的求解。若第一阶段的最终计算表出现W>0,这就表明原问题无可行解，应停止计算。53解：依条件有：又由于原料总限额已给定，加入到产品A、B、D的原材料C总量每天不超过100kg，P总量不超过100kg，H总量不超过60kg。由此有：AC

+

BC

+

DC

100AP

+

BP

+

DP

100AH

+

BH

+

DH

6054我们的目的是使利润最大，即产品价格减去原材料的价格为最大。目标函数：MaxZ=50(x1

+x2+x3)+35(x4+x5+x6)+25(x7+x8+x9)-65(x1+x4+x7)

－25(x2+x5+x8)–35(x3+x6+x9)=

-15x1

+

25x2

+

15x3

–30x4

+

10x5

+

0x6

–40x7

+0x8

–10x9约束条件：-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

≤

0x1

+x4

+x7

≤

100x2

+x5

+x8

≤

100x3

+x6

+x9

≤

60x1，······

，x9

≥

0上述数学模型，可用单纯形表计算，计算结果是：每天只生产产品A200kg

，分别需要用原料C

100

kg；P

50

kg

；H

50

kg

。总利润收入是Z=500元/天。55例1－15（连续投资问题）某部门在今后5年内考虑给下列项目投资，已知：

项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%；56项目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；xiD