课程

（P55）2.1、用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、

无穷多最优解、无界解还是无可行解。

（1）Max Z=x1+3x2 5x1+10x2<=50 x1+x2>=1 x2<=4 x1,x2>=0

解：图中的阴影部分为此线性规划问题的可行域，目标函数Z=x1+3x2，即x2=

z11—x1+是斜率为—的一族平行线，易知x1=3，x2=0为可行解，由线性规划

333的性质知，其最值在可行域的顶点取得，将直线x1+3x2=3沿法线方向逐渐向上

平移，直至A点，A点坐标为（2,4）

所以 max z =2+3×4=14 此线性规划问题有唯一最优解。

（P56）2.6、分别用单纯形法中的大M法和两阶段法求解下述线性规划问题，并

指出属哪一类解。 （1）Max z=2x1+3x2—5x3

x1+x2+x3=7 2x1—5x2+x3>=10 x1，x2，x3 >=0 解：大M法

在上述线性规划问题的约束条件中加上人工变量x4，x6，减去剩余变量x5，

得

Max z =2x1+3x2—5x3—Mx4+0x5—Mx6

x1 + x2 + x3 + x4 =7 2x1—5x2+x3—x5+x6=10 x1，x2，x3，x4，x5，x6 >=0

其中M是一个任意大的正数。据此可列出单纯形表： Cj 2 3 —5 —M 0 —M Θi CB —M —M XB x4 x6 Cj —Zj —M 2 x4 x1 Cj —Zj 3 2 x2 x1 Cj —Zj 4/7 45/7 2 5 b 7 10 x1 1 [2] x2 1 —5 x3 1 1 2M—5 1/2 1/2 M/2—6 1/7 6/7 —50/7 x4 1 0 0 1 0 0 2/7 5/7 —M—16/7 x5 0 —1 —M 1/2 —1/2 M/2+1 1/7 —1/7 —1/7 x6 0 1 0 —1/2 1/2 —3M/2—1 —1/7 1/7 —M+1/7 7 5 4/7 — 3M +2 3—4M 0 1 0 0 1 0 [7/2] —5/2 3M/2+8 1 0 0

由单纯形表的计算结果得：

最优解X =（

454454102，，0,0,0,0）T ，目标函数的最优值Z =2×+3×= 77777

两阶段法：

在上述线性规划问题的约束条件中加上人工变量x4，x6，减去剩余变量x5，得

第一阶段的数学模型 min w =x4+x6 x1+x2+x3+x4=7 2x—5x2+x3—x5+x6=10 x1，x2，x3，x4，x5，x6>=0 据此可列出单纯形表：

Cj 0 0 0 1 0 1 Θi CB 1 1 XB x4 x6 Cj —Zj b 7 10 x1 1 [2] —3 x2 1 —5 4 [7/2] —5/2 —7/2 1 0 0 x3 1 1 —2 1/2 1/2 —1/2 1/7 6/7 0 x4 1 0 0 1 0 0 2/7 5/7 1 x5 0 —1 1 1/2 —1/2 —1/2 1/7 —1/7 0 x6 0 1 0 —1/2 1/2 3/2 —1/7 1/7 1 7 5 4/7 — 1 0 x4 x1 Cj —Zj 2 5 0 1 0 0 0 x2 x1 Cj —Zj 4/7 45/7 0 1 0 454，，0,0,0,0）T ，目标函数的最优值W 77=0 454因人工变量x4=x6=0，所以（，，0,0,0,0）T 是原线性规划问题的基

77可行解。

于是可以进行第二阶段运算，将第一阶段的最终表中的人工变量取消，并填

入原问题的目标函数的系数，进行第二阶段的运算， Cj 2 3 —5 0 Θi CB XB b x1 x2 x3 x5 第一阶段求得的最优解X =（

3 2 x1 x2 4/7 45/7 0 1 1 0 1/7 6/7 1/7 —1/7 Cj —Zj 0 0 —50/7 —1/7 454，，0,0,0,0）T ，目77454102标函数的最优值Z =2×+3×=。

777

（P113）4.3 用表上作业法和伏格尔（Vogel）法求表4-44中给出的运输问题的

最优解和近似最忧解（表中数字M为任意大正数）。 销地 产地 甲 乙 丙 丁 戊 由表中计算可知，原线性规划问题的最优解X =（

产量 5 6 2 9 1 2 3 4 销量 10 2 1 8 4 20 10 20 6 4 5 8 7 3 6 9 30 10 7 2 10 6 4 5 4 解：产销不平衡的运输问题，所以增加一个假想销地巳，并令其运价为0，其销量为5+6+2+9—（4+4+6+2+4）=2，见表： 销地 产地 甲 乙 丙 丁 戊 巳 1 2 3 4 销量 10 2 1 8 4 20 10 20 6 4 5 8 7 3 9 30 10 7 10 6 4 5 0 0 0 0 产量 5 6 2 9 6 2 4 2 利用伏格尔求出初始解。 第一步：分别计算表中各行、各列的最小运费和次最小运费的差额，并填入该表

的最右列和最下行。

第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。 第三步：对未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，重复第一、第二，直到给出初始解为止。

最后利用位势法进行检验。

所有检验数都非负，故解为最优解。这时得到的总运费最少，为90.故该运输问

题有无穷多最优解。

P（127）5.2分别用图解法和单纯形法找出以下目标规划问题的满意解。

解：由约束条件作图

首先考虑P1优先因子的目标实现，在目标函数中要求实现

从图中可以看出：

当x1，x2在射线x1—10x2=50且x2>=0上取值，可以满足 =0 和 =0 。 再考虑P2优先因子的目标实现，在目标函数中要求实现 min ( 2 + ) 因 的权系数大于 的权系数，由图可知，D点为满意解，D点坐标为

（50,0）。

P（152）6.2 用分支定界法解

max z = x1+x2

951x1+ x2<=

14141—2x1+ x2<=

3x1，x2，>=0 x1，x2为整数

解： 在原线性规划问题约束条件中分别添加松弛变量x3，x4 ，化为标准型，

可得： max z = x1+x2

951x1+ x2+x3<=

14141—2x1+ x2+x4<=

3x1，x2，x3，x4>=0 x1，x2为整数

不考虑整数条件，用单纯形法求解，计算结果如表所示： Cj 1 1 0 0 Θi CB XB b x1 x2 x3 x4 0 0 x3 x4 Cj —Zj 1 0 x1 x4 51/14 160/21 51/14 1/3 [1] —2 3 1 0 9/14 1 2 9/14 [161] 1 0 0 1 2 0 1 0 0 1 51/14 — 51/9 160/3381 Cj —Zj 0 5/14 —1 0