一、问答题

1、线性规划最优解的存在有哪几种情况？简述各种情况在单纯形法求解过程中的表现？

1(1)、在遇到退化的基可行解时、单纯形法求解出现循环时如何处理？

2、什么是影子价格？影子价格有什么作用？

3、什么是平衡运输问题？该类问题数学模型上有什么样的特征？

4、分支定界法包含两个重要概念，即“分支”和“定界”。试述这两个概念的基本含义！

5、什么是增广链？如何确定调整量？如何确定新的流？

6、试阐述具有不同等级目标规划求解的基本过程。

7、试述目标规划问题的解决思路。

8、在图论中什么是最小生成树，试述破圈法求最小生成树的方法。

9、图论中的图的涵义是什么？

10、在图论中什么是生成子图？

11、在图论中网络的含义是什么？ 

12、如何识别线性规划问题有多重最优解？

13、如何识别运输问题有多重最优解？

一、问答题

1、答：线性规划问题的最优解主要存在四种情况：

1）唯一最优解。判断条件：单纯形最终表中所有非基变量的检验数均小于零

2）多重最优解：判断条件：单纯形最终表中存在至少一个非基变量的检验数等于零。

3）无界解。判断条件：单纯形法迭代中某一变量的检验数大于零，同时它所在系数矩阵列中的所有元素均小于等于零

4）无可行解。判断条件：在辅助问题的最优解中，至少有一个人工变量大于零

2、答：把在一定条件下的最优生产方案中，某种资源增加或减少一个单位给总收益带来的改变量，称为此种资源在一定条件的影子价格。作用：a.能为经理的经营决策提供重要的指导（可举例说明）b.为重新分配一个组织内的资源提供依据。

3、答：平衡运输问题指的是总供给等于总需求的运输问题。其特点如下：

1）系数矩阵全部由0和1两种元素值组成，前m行每行有n个1，后n行每行有m个1。每列又且只有2个1，Pij向量的1分别在第i行和第m+j行。

2）共有m*n个决策变量，m+n个约束方程，基变量却只有m+n-1个。

3）任何一个平衡运输问题至少有一个最优解

4、答：“分支”：若xk不为整数，将对应的线性规划问题分别加入两个不等式，即和。“定界”：如果在分支过程中的某一步求得了一个可行整数解，它对应的目标函数值为z0 ,则把z0 作为一个界，以便提高计算效率。

5、答：设f={fij}是D中的一个可行流，若存在一条{vs-vt}链u，满足：1）对一切（i，j）∈u+,有fij2) 对一切（i，j）∈u-,有fij>0; 则称u是一条关于{vs-vt}的增广链

新的流为： 

6、答：首先求出目标规划的最优先级目标解，然后把已经求得的优先级的目标最优解作为下一优先级目标规划的约束条件来求解，以此类推，逐级求得所有优先级的目标最优解。

7、答：首先对于管理部门提出的每一个目标，由决策者确定一个具体的数量目标，并对每一个目标建立目标函数，然后寻求一个使目标函数和对应目标之间的偏差之和达到最小的解.

8、答：无圈的、最小的、连通的生成子图；在连通图中逢圈去掉最大的边。

9、答：具有表达对象之间特定关系的含义（如朋友关系，地点之间的通路关系）

10、答：在给定的无向图G(V,E)中，保留G中所有的点，而删掉G的部分边剩下（或保留）部分边所得到的图称为图G的生成子图。

11、答：在赋权有向图D（V,A）中指定了一个点（Vs），称为为发点,指定另一个点（Vt）为收点,其余的点为中间点，并把D中的每一条弧的赋权数Cij称之为弧（Vi,Vj）的容量,这样的赋权有向图D就称之为网络。

12、答：看在单纯形方法的最优解中是否存在非基变量的检验数为零的情况。如果存在，则存在最优解。

13、答：看在运输问题的最优方案是否存在非基变量的检验数为零。如果存在，则存在最优解。

二、判断下列说法的正确性（☆---对，¤---错）

 1、线性规划问题可行解X为基可行解的充分必要条件是X的正分量所对应的系数列向量是线性的。☆

 2、线性规划模型的每一个基可行解对应可行域的一个顶点。☆

 3、如线性规划问题的标准型为型，则当检验数时，相应的基可行解是最优解。☆

 4、若原问题第i个约束条件为严格的不等式，则第i个对偶变量的最优值yi*=0。☆

 5、根据弱对偶定理，当x,y分别是和的可行解，则。¤

 6、若线性规划问题的原问题无可行解，则其对偶问题无可行解。¤

 7、若序列{Vs , V1 , V2 ,……，Vn-1 , Vn }是从Vs到Vn的最短路，则序列{Vs , V1 , V2 ,……，Vn-1 }必定是Vs到Vn-1的最短路。☆

 8、表上作业法实质上是单纯形法在求解运输问题的一种简化方法。☆

 9、整数规划的目标函数值一般优于相应的线性规划问题的目标函数值。¤

10、目标规划问题中，当目标允许超额完成时（如利润、产值），则目标函数的表达式为。¤

10-1目标规划问题中，当要求不低于目标值（如利润、产值）时，则目标函数的表达式为☆

11、在对需要引入人工变量构成原线性规划辅助问题的单纯形法求得的最优解中，若人工变量不等于零，则说明原问题没有可行解。☆

12、如不按最小比值原则选取换出基变量，则在下一个解中至少有一个基变量的值为负值。☆

13、单纯法计算中，选取最大的正检验数б对应的变量作为换入变量 ，将使目标函数值得到最快的增长。¤

14、若X、X分别是某一线性规划问题的最优解，λ、λ为任意实数，则X=λX +λX也是该问题的最优解。¤

15、设，分别为标准形式为最大化的原问题与对偶问题的可行解， ，分别是其最优解，则恒有

≥≥。¤

16、已知是线性规划对偶问题的最优解，若〉0，说明在最优生产计划中第i种资源已完全耗尽。☆

16-1已知是线性规划对偶问题的最优解，若=0，说明在最优生产计划中第i种资源的消耗未超过界限值。

17、若线性规划问题中的，值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解。¤

18、按表上作业法(最小元素法或左上角法）给出的初始基可行解，从每个空格出发可以找出而且仅能找出唯一的闭回路。☆

18-1表上作业法(最小元素法或左上角法等）每次给出一个格点取值后，总是划去满足的一行或一列（若行与列同时满足则只划去其一），以保证所有填上数字（包括填上“0” ）的格点（基变量所在的点）不形成闭回路。

19、当所有产地的产量和销地的销量均为整数时，运输问题的最优解也为整数。☆

20、目标规划模型中，应同时包含绝对约束与目标约束。¤

21、指派问题效率矩阵的每一个元素都乘上同一个常数k将不影响最优指派方案。¤

22、若序列{Vs , V1 , V2 ,……，Vn-1 , Vn }是从Vs到Vn的最短路，则序列{ V2,……，Vn }必定是V2到Vn的最短路。

22-1若序列{Vs , V1 , V2 ,……，Vn-1 , Vn }是从Vs到Vn的最短路，则序列{ V1,……，Vn-1 }必定是V1到Vn-1的最短路。

三、算法题

1、已知线性规划问题：

其最优解为x1=-5,x2=0,x3=-1

1)写出并求其对偶问题的最优解；2）求k的值。

、

1、答：其对偶问题为： 

由z*=w* 可得

由对偶问题第三约束式得

解得

由互补松弛性可得，

并代入可得：

1、已知线性规划问题：

其最优解为x1=-5,x2=0,x3=-1

1)写出并求其对偶问题的最优解；2）求k的值。

、

1、答：其对偶问题为： 

由z*=w* 可得

由互补松弛性可得

解得

代入可得： 

2、设有LP问题：

其辅助问题的最优表的下半部分为：

2、答：首先写出两阶段法的辅助问题，计算出各个检验数，然后通过灵敏度分析判断出原问题无最优解。

3、在下面的运输问题中，假定B1、B2、B3的需求未被满足时，其单位惩罚成本分别是5、3和2，求最优解。

该问题的最小运费为595元。

4、求解下述最小支撑树问题： 

v1       4        v2       1        v3

        2                 3

1                 1      1

v8     4            v0     4        v4

5       5         2      4    5

v7         3      v6      2         v5

4、答：该问题的最小支撑树如下图所示。W（T）=13

v1                v2       1        v3

        2                 

1                 1      1

v8                  v0             v4

                2          

v7         3      v6      2         v5

5、设有线性规划问题及其最优单纯形表如下：

规划模型：               （1）

     St：3x+ 5x+ x       =15           （2）

        2x+  x+    x    =5            （3）

        2x+ 2x+        x=11           （4）

x、x、x、x、x≥0         

最终单纯形表：

5、答1：St：3x+ 5x+1·x      =15 +1·t=7          （2）

        2x+  x+        x   =5            （3）

        2x+ 2x+           x=11           （4）

由最终单纯形表：

5、答2：用对偶单纯形法继续计算可得新问题的最优解和最优值为：。过程如下：

由题目的模型可知：

6、求解如下运输问题的最优解：                                       

6、答：利用最小元素法或VOGEL法求出初始解；用位势法检验并求出最优解。该问题的最小运费为：Z=35。

7、下列表格为目标规划求解过程的单纯性表格，试指出下列表格（Ⅰ）、（Ⅱ）、（Ⅲ）优化到哪一级目标，接下去要优化优化哪一级目标？

表3B

8、用最小元素法求下表所表达的运输问题的初始基可行解，如何求得最优解?

其费用为：元 

9、求下图中v1到v8点得最短路

9、答：最短路长为25； 路径为：v1-v5-v2-v4-v8    

10、电力公司准备在甲（V1）、乙（V8）两地沿路架设一条电缆线，问如何架设使其电缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。

10、答：最短路径：v1-v3-v4-v6-v7- v8；路长：=2+2+1+2+1=8

11、已知某线性规划化问题的数学模型如下：

试写出该问题大M方法的数学求解模型（也叫大M法辅助模型），并指出在辅助模型中哪些变量可作为基变量？辅助问题的最优解在什么情况下可以得到原问题的最优解？

11B、已知某线性规划化问题的数学模型如下：

试写出该问题大M方法的数学求解模型（也叫大M法辅助模型），并指出在辅助模型中哪些变量可作为基变量？辅助问题的最优解在什么情况下可以得到原问题的最优解？

11B、答：（1）目标函数： max z=－2x1－3x2－Ma1－Ma2.

       约束条件：x1+x2－s1+a1=350，

                 x1－s2+a2=125，

                 2x1+x2+s3=600，

              x1，x2，s1，s2，s3，a1，a2≥0.

（2）答：s3，a1，a2，这三个变量可以做基变量；

（3）当辅助问题的最优解中的两个人工变量a1，a2，等于零的时候，可以作为原问题的最优解。

12、用最小元素法求下列运输作业表所表达的运输问题的初始基可行解：

     销地    

12、（1）答：x13 =4, x14=3, x21=3, x23=1, x32=6, x34=3,其余xij=0为非基变量；（2）答：用闭回路法或位势方程组法判断是否为最优解，若是结束，若不是，则进行优化变换：找出检验数为负数非基变量作为入基变量进行出入基变换，得出更优的解，然后再重复上述步骤，直至最优。

14、已知指派问题的效率矩阵如下，试用匈牙利法求出其最优指派方案。（10分）

14、答：1）

13、燃气公司准备在甲、乙两地沿路铺设一条管路，问如何铺设使其管路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）

答：最短路径v1       v3       v5        v4        v7，总长为21公里；每点的标号见下图：

14、某电力公司要沿道路为8个居民点架设输电网络，连接8个居民点的道路如下图所示，其中v1,v2,v3,v4,v5,v6,v7,v8表示8个居民点，图中的边表示8个居民点之间道路，边上的赋权数位这条道路的路长，单位为公里，请设计一个输电网络，连通这8个居民点，并使总的输电线长度最短。

14、答：总长：2+2+4+2+3+3+2=18公里

四、建模题

1、一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依法该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时支出40美元，音乐节目每小时费用为17.5美元。法律规定，正常情况下商业节目只能占广播时间的20，每小时至少安排5分钟的新闻节目。问每天的广播节目该如何安排？优先级如下：

p：满足法律规定的要求；

p：每天的纯收入最大。

试建立该问题的目标规划模型。

1、答：设x--商业；x--新闻；x--音乐

minz= p（d+d+ d）+pd

st：   x+x+x+d-d=12

            x+   d   =2.4 

x-    d  =1;    

250x- 40x-17.5x+ d+d=560  ;  

 x, x, x≥0; d , d ≥0) 

2、某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见下表：

1）装入卫星的总体积不超过V，总重量不超过W；

2）A1与A3中最多安装一件；

3）A2与 A4中至少安装一件；

4）A5 与A6或者都安上，或者都不安。

总的目的是使安装上的仪器在卫星上发挥最大的实验价值。

试建立这个问题的数学模型。

2、答：max=

s．t．    

         x + x1

            x+ x1

            x = x

            x=1 {安装A}； x=0 {不安装A}，j=1、2，…,6

3、某电动机厂生产A、B、C三种型号的电动机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时、8小时和10小时。生产线每月正常工作时间为200小时；三种型号的电动机销售后，每台可获利分别为500元，650元，和800元。每月销售量预计为12台、10台、6台。该厂的经营目标如下：

P1：利润指标定为每月1.6×104元；

P2：充分利用生产能力；

P3：加班时间不超过24小时；

P4：产量以预计的销量为标准；

为确定生产计划，试建立该问题的目标规划模型。

3、答：minz= pd+pd+pd+p（d+d+d+d+d+d）

st：{500x+650x+800x+d-d=1.6×10

          6x+  8x+ 10x+d-d=200 

d+ d- d  =24

x+    d-d    =12

x+     d-d     =10    (x, x, x≥0;

x+    d-d    =6;   d , d ≥0) }

4、某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总钻井费用为最小。若10个井位的代号为s,s…….s，相应的探井费用为c，c……...c，并且选择井位要满足下列条件：

1）或同时选择s和s，或选择s钻探；

2）选择了s或s，就不能选s；或反过来也一样；

3）在s，s，s，s中最多只能选两个；

试建立这个问题的整数规划模型。

4、答：

x=1， 选择钻探第Sj井位，x=0， 不选择钻探第Sj井位。

5、友谊农场有3万亩（每亩=666.66m2）农田，欲种玉米、大豆和小麦3种农作物。各种作物每亩需施化肥分别为0.12t、0.20t、0.15t，预计秋后玉米每亩可收获500kg，售价为0.24元/kg，大豆可收获200kg，售价为1.20元/kg，小麦每亩可收获300kg，售价为0.70元/kg。农场年初规划时考虑如下几个方面：

P1：年终收益不低于350万元；

P2：总产量不低于1.25万t；

P3：小麦产量以0.5万t为宜；

P4：大豆产量不少于0.2万t；

P5：玉米产量不超过0.6万t；

P6：农场能提供5000t化肥；若不够，可在市场上高价购买，但希望高价采购量越少越好。

试就该农场生产计划建立数学模型。（15分）

5、答：设种玉米亩，大豆亩，小麦亩，则该问题的数学模型：

s.t. 

6、某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见下表：

       题2表

2）A1与A3中至少安装一件；

    3）A2与 A4中至多安装一件；

4）A5 与A6或者都安上，或者都不安。

 总的目的是使安装上的仪器在卫星上发挥最大的实验价值。试建立这个问题的数学模型。

6、答：max=

s．t．    

            x + x1

                x+ x1

                x = x

                x=1 {安装A}； x=0 {不安装A}

8、某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总钻探费用最少。若10个井位的代号为S1，S2，…，S10，相应的钻费用为C1，C2，…，C10，并且井位选择方面要满足下列条件：

①或选择S1和S7，或选择钻探S8；、

②选择了S3或S4就不能选S5或反过来也一样；

③在S5、S6、S7、S8中最多只能选两个。

试建立这个问题的整数规划模型。（10分）

   1、某电动机厂生产A、B、C三种型号的电动机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时、8小时和10小时。生产线每月正常工作时间为200小时；三种型号的电动机销售后，每台可获利分别为500元，650元，和800元。每月销售量预计为12台、10台、6台。该厂的经营目标如下：

p：利润指标定为每月1.6×10元；

p：充分利用生产能力；

p ：加班时间不超过24小时；

p：产量以预计的销量为标准；

 为确定生产计划，试建立该问题的目标规划模型。

1、答：minz= pd+pd+pd+p（d+d+d+d+d+d）

st：{500x+650x+800x+d-d=1.6×10

          6x+  8x+ 10x+d-d=200 

d+ d- d  =24

x+    d-d    =12

x+     d-d     =10    (x, x, x≥0;

x+    d-d    =6;   d , d ≥0) }

复习题解

三

3、用最小元素法或VOGEL法求初始解，通过位势法进行检验并获得最优解。

该问题的最小运费为595元。

4、该问题的最小支撑树如下图所示。W（T）=13

v1                v2       1        v3

        2                 

1                 1      1

v8                  v0             v4

                2          

v7         3      v6      2         v5

三B、

1、用对偶单纯形法继续计算可得新问题的最优解和最优值为： 

2、利用最小元素法或VOGEL法求出初始解；用位势法检验并求出最优解。该问题的最小运费为：Z=35

3、

其对偶问题为： 

由z*=w* 可得

由互补松弛性可得

解得

代入可得： 

4、待答？

5、最短路长为25； 路径为：v1-v5-v2-v4-v8

3、用对偶单纯形法继续计算可得新问题的最优解和最优值为：。过程如下：

由题目的模型可知：

此表符合对偶单纯形法求解的条件，故利用对偶单纯形法计算如下：

四A、

1、1、minz= p（d+d+ d）+pd

st：   x+x+x+d-d=12

            x+   d   =2.4 

x-    d  =1;    

250x- 40x-17.5x+ d+d=560  ;  

 x, x, x≥0; d , d ≥0) 

2、答：max=

s．t．    

         x + x1

            x+ x1

            x = x

            x=1 {安装A}； x=0 {不安装A}，j=1、2，…,6

四B、

1、minz= pd+pd+pd+p（d+d+d+d+d+d）

st：{500x+650x+800x+d-d=1.6×10

          6x+  8x+ 10x+d-d=200 

d+ d- d  =24

x+    d-d    =12

x+     d-d     =10    (x, x, x≥0;

x+    d-d    =6;   d , d ≥0) }

2、

x=1， 选择钻探第Sj井位，x=0， 不选择钻探第Sj井位。下载本文