运筹学复习题 - 考试题

《运筹学》复习题

一、填空题（1分×10=10分）

1．运筹学的主要研究对象是（组织系统的管理问题）。

2．运筹学的核心主要是运用（数学）方法研究各种系统的优化。 3．模型是一件实际事物或现实情况的代表或抽象。 4．通常对问题中变量值的限制称为（约束条件），它可以表示成一个等式或不等式的集合。 5．运筹学研究和解决问题的基础是（最优化技术），并强调系统整体优化功能。 6．运筹学用（系统）的观点研究（功能）之间的关系。

7．运筹学研究和解决问题的优势是应用各学科交叉的方法，具有典型综合应用特性。 8．运筹学的发展趋势是进一步依赖于计算机的应用和发展。 9．运筹学解决问题时首先要观察待决策问题所处的环境。 10．用运筹学分析与解决问题，是一个科学决策的过程。

11．运筹学的主要目的在于求得一个合理运用人力、物力和财力的最佳方案。

12．运筹学中所使用的模型是数学模型。用运筹学解决问题的核心是（建立数学模型），并对模型求解。

13．用运筹学解决问题时，要分析，定义待决策的问题。 14．运筹学的系统特征之一是用系统的观点研究功能关系。 15．数学模型中，“s.t.”表示约束。

16．建立数学模型时，需要回答的问题有性能的客观量度，可控制因素，不可控因素。 17．运筹学的主要研究对象是各种有组织系统的管理问题及经营活动。 18. 1940年8月，英国管理部门成立了一个跨学科的11人的运筹学小组，该小组简称为OR。 19．线性规划问题是求一个(线性目标函数),在一组(线性约束)条件下的极值问题。 20．图解法适用于含有两个变量的线性规划问题。

21．线性规划问题的可行解是指满足所有约束条件的解。 22．在线性规划问题的基本解中，所有的(非基变量)等于零。

23．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关

24．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。 25．线性规划问题有可行解，则必有基可行解。 26．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解的集合中进行搜索即可得到最优解。

27．满足非负条件的基本解称为基本可行解。 28．在将线性规划问题的一般形式转化为标准形式时，引入的松驰变量在目标函数中的系数为零。

29．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。 30．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。 31．线性规划问题可分为目标函数求极大值和极小_值两类。

32．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。

33．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解

34．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。

35．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。 36.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。

37.如果某个变量Xj为自由变量，则应引进两个非负变量Xj′ , Xj〞, 同时令

Xj＝Xj’－ Xj’’。

38.表达线性规划的简式中目标函数为max(min)Z=∑cijxij。 39. 线性规划的代数解法主要利用了代数消去法的原理，实现基可行解的转换，寻找最优解。 40．对于目标函数极大值型的线性规划问题，用单纯型法求解时，当基变量检验数(?j≤_0时)，当前解为最优解。

41．用大M法求目标函数为极大值的线性规划问题时，引入的人工变量在目标函数中的系数应为（－M）。

42．在单纯形迭代中，可以根据最终表中人工变量（不为零）判断线性规划问题无解。 43．当线性规划问题的系数矩阵中不存在现成的可行基时，一般可以加入人工变量构造可行基。

44．在单纯形迭代中，选出基变量时应遵循（最小比值θ法则）。 45．线性规划典性的特点是（初始基）为单位矩阵，（初始基变量）的目标函数系数为0。 46．对于目标函数求极大值线性规划问题，在[非基变量的检验数全部(?j≤_0时)]、（问题无界时），（问题无解时）的情况下，单纯形迭代应停止。

47．在单纯形迭代过程中，若有某个非基变量的?k>0，且对应的非基变量xk的系数列向量Pk_≤0_时，则此问题是无界的。

48．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的线性规划问题与之对应，反之亦然。

49．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的（目标函数）系数。 50．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式。 51．对偶问题的对偶问题是（原问题）。

52．若原问题可行，但目标函数无界，则对偶问题不可行。

53．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时，相应的目标函数值将增加3k 。 54．线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y﹡= CBB－1。

55．若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡= Y﹡b。 56．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX≤Yb。

57．若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡=Y*b。

58．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=Yb YA≥c Y≥0_。

59．影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。 60．线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为AT 。 61．在对偶单纯形法迭代中，若某bi<0，且所有的aij≥0(j=1，2，?n)，则原问题_无解。

62、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。 63、在线性规划的灵敏度分析中，我们主要用到的性质是（可行性），（正则性）。

64．在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。 65．如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应出基。

66．约束常数b的变化，不会引起解的正则性的变化。

67．在某线性规划问题中，已知某资源的影子价格为Y1，相应的约束常数b1，在灵敏度容

许变动范围内发生Δb1的变化，则新的最优解对应的最优目标函数值是Z*+yi△b (设原最优目标函数值为Z﹡)

68．若某约束常数bi的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用对偶单纯形法求解。

69．已知线性规划问题，最优基为B，目标系数为CB，若新增变量xt，目标系数为Ct，系数列向量为Pt，则当Ct≤CBB－1Pt时，Xt不能进入基底。

70．如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个（变量）。 71．若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加一行，一列。

72．线性规划灵敏度分析应在最优单纯形表的基础上，分析系数变化对最优解产生的影响 73．在某生产规划问题的线性规划模型中，变量Xj的目标系数Cj代表该变量所对应的产品的利润，则当某一非基变量的目标系数发生增大变化时，其有可能进入基底。

74．物资调运问题中，有m个供应地，Al，A2?，Am，Aj的供应量为ai(i=1，2?，m)，n个需求地B1，B2，?Bn，B的需求量为bj(j=1，2，?，n)，则供需平衡条件为 =

75．物资调运方案的最优性判别准则是：当全部检验数（非负）时，当前的方案一定是最优方案。

76．可以作为表上作业法的初始调运方案的填有数字的方格数应为m+n－1个(设问题中含有m个供应地和n个需求地)。

77．若调运方案中的某一空格的检验数为1，则在该空格的闭回路上调整单位运量而使运费增加1。

78．调运方案的调整是要在检验数出现（负值）的点为顶点所对应的闭回路内进行运量的调整。

79．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到_1条闭回路 80．在运输问题中，单位运价为Cij位势分别用Ui，Vj表示，则在基变量处有Cij ，Cij=Ui+Vj 。 81．供大于求的、供不应求的不平衡运输问题，分别是指 _＞ 的运输问题、 _＜ 的运输问题。

82．在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为（基变量）。 83．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。

84．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为X1≤1，X1≥2。 85．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P0无可行解。

86．在0 - 1整数规划中变量的取值可能是_0或1。

87．对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为n个。

88．分枝定界法和割平面法的基础都是用线性规划方法求解整数规划。 89．在用割平面法求解整数规划问题时，要求全部变量必须都为整数。

90．用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。

91．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法_。

92．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。 93．在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零元素_。 94.分枝定界法一般每次分枝数量为2个.

95．图的最基本要素是点、点与点之间构成的边

96．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。

97．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。

98．在图论中，图是反映研究对象之间特定关系的一种工具。 99．任一树中的边数必定是它的点数减1。

100．最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。 101．最小树的算法关键是把最近的未接_结点连接到那些已接结点上去。

102．求最短路问题的计算方法是从0≤Fij≤Cij开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。

二、选择题（1分×10=10分）

1． 图解法通常用于求解有（ ）个变量的线性规划问题。B A.1 B.2 C.4 D.5

2． 线性规划问题的最优解（ ）为可行解。 A A．一定 B． 不一定 C．一定不 D．无法判断

3． 关于图解法，下列结论最正确的是：D

A. 线性规划的可行域为凸集 B.线性规划的最优解 一定可在凸集的一个顶点达到 Ｃ.若线性规划的可行域有界，则一定有最优解 Ｄ.以上都正确

4． 线性规划的标准形有如下特征：C A. 决策变量不为零 B. 决策变量无符号限制 C. 决策变量全为非负 D. 以上都不对

5． 线性规划需满足的条件是：C A. 目标函数为线性 B. 约束条件为线性

C. 目标函数与约束条件均为线性 D. 都不对

6． 关于标准线性规划的特征，哪一项不正确：C A. 决策变量全≥0

B. 约束条件全为线性等式 C. 约束 条件右端常数无约束 D. 目标函数值求最大

7． 如果在线性规划标准型的每一个约束方程中各选一个变量，它在该方程中的系数为1，

在其它方程中系数为零，这个变量称为： A A. 基变量 B. 决策变量 C. 决策变量 D. 基本可行解

8．关于单纯形法的说法不正确的是：B

Ａ.只要人工变量取值大于零，目标函数就不可能实现最优 Ｂ.增加人工变量后目标函数表达式不变

Ｃ.所有线性规划问题化为标准形后都含有单位矩阵

Ｄ.检 验数中含M时，如果M的系数为负，则检验数为负

44．确定运输问题的初始调运方案的方法是： A A．沃格尔法 B．单纯形法 C．匈牙利法 D．闭回路法

45．一般来说，用沃格尔法与最小元素法求解初始调运方案时，目标函数的值：B A．一样优 B．前者的优 C．后者的优 D．不好说

46．运输问题的方案的确定最常用的方法是： A A．最小元素法 B．闭合回路法 C．表上作业法 D．以上都不是

47．运输问题的数学模型中包含（）个约束条件B A．m*n B．m+n C．m+n-1 D．m*n-1

48．人数大于事数的指派问题中，应该采取的措施是：B A．虚拟人 B．虚拟事 C．都可以 D．不需要

49．用EXCEL求解线性规划问题时，可变单元格是：B A．目标函数 B．决策变量 C．约束方程 D．都不是

50．关于运输问题的说法不正确的是：C A．它可用线性规划的单纯形表求解 B．它可用表上作业法求解

C．它的约束方程数等于基变量的数目 D．它一定有最优解

51．平衡运输模型的约束方程的特点包括：D A．约束左边所有的系数都是0或1

B．运输问题约 束方程左边的每一列中恰有两个系数是1，其他都是0 C．有m+n-1个独立约束条件，该问题的基变量有m+n-1个 D．以上都正确

52．平衡运输问题一定存在：B A．整数解 B．最优解 C．无穷多解 D．以上都不对

53．在n个产地、m个销地的产销平衡运输问题中，( )是错误的。D A .运输问题是线性规划问题

B .基变量的个数是数字 格的个数 C .空格有mn-n-m+1个

D .每一格在运输图中均有一闭合回路

54．典型的运输问题的平衡是指：C A .每个需求方物资的需要量一样 B .每个供应方物资 的供应量一样 C .总的需求量与总的供应量一样 D .需求方和供应方个数一样

55．有6 个产地4个销地的平衡运输问题模型具有特征:B A．有10个变量24个约束 B．有24个变量10个约束 C．有24个变量24约束

D．有9个基变量10个非基变量

56．运输问题中，m+n－1个变量构成一组基变量的充要条件是：B A．m+n－1个变量恰好构成一个闭回路 B．m+n－1个变量不包含任何闭回路

C．m+n－1个变量中部分变量构成 一个闭回路 D．m+n－1个变量对应的系数列向量线性相关

57．有m个产地n个销地的平衡运输问题模型具有特征: A A．有mn个变量m+n个约束 B．有m+n个变量mn个约束 C．有mn个变量m+n－1约束

D．有m+n－1个 基变量，mn－m－n－1个非基变量 58．用增加虚设产地或虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问题处理，该方法： A A．正确 B．错误

C．不一定 D．无法判断

59．建立运输问题的改进方案，在调整路线中调整量应为： A A．奇数格的最小运量 B．奇数格的最大运量 C．偶数格的最小运量 D．偶数格的最大运量 60．考虑某运输问题,设其总需求量为Q,总供应量为G,且Q

A．使诸供应点的供应总量减少G-Q B．使诸需求点的需求总量增加G-Q

C．虚设一个需求量为G-Q的需求点,且任一供应点到该虚设需求点的单位运费为充分大 D．虚设一个需求量为G-Q的需求点,且任一供应点到该虚设需求 点的单位运费为0

61．在解运输问题时,若已求得各个空格的改进路线和检验数，则选择调整格的原则是：C A．在所有空格中,挑选值最小的正检验数所在的空格作为调整格

B．在所有空格中,挑选绝对值最小的正检验数所在 的空格作为调整格 C．在所有空格中,挑选为正值且最大的检验数所在的空格作为调整格 D．在所有空格中,挑选绝对值最小的负检验数所在的空格作为调整格

62．当某供给地与某需求地之间不允许运输时，它对应的运价为：B A．零 B．无穷大 C．随便取 D．以上都不对

63．当运输问题是求利润最大化时，采取的措施是:B A．仍用最小元素法求初始调运方案 B．应用最大元素法 求初始调运方案 C．不可西北角法求初始调运方案 D．检验数都大于零时得到最优解

64．如果下表为一产销平衡运输问题的一组基可行解（左上角为运价），则x14的检验数为：B

A．8 B．7 C．4 D．5

65．网络计划发源于：D

A．德国 B．法国 C．日本 D．美国

66．关键路径法源于:B

A.惠普公司 B.杜邦公司 C.IBM公司 D.美国海军武器局

67．关于网络计划技术的说法不正确的是：B A．它需要分清哪项工作先作，哪项工作后做 B．它不是一种统筹方法

C．它的目的是缩短工期或降低成本 D．它需要找出关键工作

68．关键路线问题的关键工序是指:D A．最先开始的工序 B．最后结束的工序 C．最重要的工序

D．需要时间最长的工序

三、线性规划问题化为线性规划问题的标准形式（5分×2=10分）

1、 maxZ?4x?3x12

?x1?x2?10

? ?2x1?x2?2?x,x?0

?12

maxZ?4x1?3x2?0x3?0x4?Mx5 ?x1?x2?x3?10?

?2x1?x2?x4?x5?2 ?x,x?0,x,x,x?0345?12

2、 maxZ??x?2x12

?3x1?8x2?5

??x1?3x2?4

?x1?0 ??x2自由量

?

maxZ??x1?2x3?2x4?0x5?0x6?Mx7

?3x1?8x3?8x4?x5?5

??x1?3x3?3x4?x6?x7?4

?x1,x3,x4?0 ?? x5,x6,x7?0?

3、 maxZ?50x?30x12

?4x1?3x2?120

??2x1?x2?50

?x1?0 ?? x2?0?

maxZ?50x?30x?0x?0x1234

?4x1?3x2?x3?120

??2x1?x2?x4?50

?x1,x2?0 ?? x3,x4?0?

4、 minZ??3x?x?x123

?x1?2x2?x3?11

???4x1?x2?2x3?3

? ??2x1?x3?1? x1,x2,x3?0?

maxZ?3x1?x2?x3?0x4?0x5?Mx6?Mx7

?x1?2x2?x3?x4?11

???4x1?x2?2x3?x5?x6?3

??2x1?x3?x7?1 ??x1,x2,x3,x4,x5,x6,x7?0

?

四、根据实际问题，写出线性规划的数学模型（5分×2=10分）

1、设备配购问题

某农场要购买一批拖拉机以完成每年三季的工作量：春种330公顷，夏管130公顷，秋收470公顷。可供选择的拖拉机型号、单台投资额及工作能力如下表所示。

拖拉机型号 单台投资（元） 东方红 丰收 跃进 胜利 5000 4500 4400 5200 单台工作能力（公顷） 春种 30 29 32 31 夏管 17 14 16 18 秋收 41 43 42 44 问配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最小？

解：设购置东方红、丰收、跃进、胜利拖拉机的数量分别为x1,x2,x3,x4台，则可建立线性规划问题的数学模型：

minz?5000x1?4500x2?4400x3?5200x4?30x1?29x2?32x3?31x4?330?17x?14x?16x?18x?130?1234s.t.??41x1?43x2?42x3?44x4?470??x1,x2,x3,x4?0

2、物资调运问题

甲乙两煤矿供给A，B，C三个城市的用煤。各矿产量和各市需求如下表所示：

煤矿 日产量（吨） 城市 甲 200 A B 乙 250 C 各矿与各市之间的运输价格如下表示： 日需求量（吨） 100 150 200 城运价（元/吨） 市 A B C 煤矿 甲 9 7 10 乙 8 6.5 8 问应如何调运，才能既满足城市用煤需求，又使运输的总费用最少？

解：设煤矿甲供应城市A、B、C的煤分别为x11,x12,x13，煤矿乙供应城市A、B、C的煤分别为x21,x22,x23，则可建立线性规划问题数学模型：

minz?9x11?7x12?10x13?8x21?6.5x22?8x23?x11?x12?x13?200?x?x?x?25023?2122??x11?x21?100s.t.??x12?x22?150?x13?x23?200???xij?0(i?1,2;j?1,2,3)

3、食谱问题

某疗养院营养师要为某类病人拟订本周菜单。可供选择的蔬菜及其费用和所含营养成分的数量，以及这类病人每周所需各种养分的最低数量如下表所示：

养分 蔬菜 青豆 胡萝卜 花菜 卷心菜 甜菜 土豆 每周养分 最低需求量 铁 每份蔬菜所含养分数量（毫克） 0.45 10 0.45 28 1.05 50 0.4 0.5 0.5 25 22 75 415 9065 2550 75 15 235 17500 8 3 53 27 5 8 245 0.3 0.35 0.6 0.15 0.25 0.8 5.0 每份蔬菜 1.5 1.5 2.4 0.6 1.8 1.0 磷 维生素A（单位） 维生素C 烟酸 费用（元） 6.0 325 另外为了口味的需求，规定一周内所用的卷心菜不多于2份，其它蔬菜不多于4份。若病人每周需14份蔬菜，问选用每种蔬菜各多少份？

解：设该类病人每周需要青豆、胡萝卜、花菜、卷心菜、甜菜、土豆分别为份，则可建立线性规划问题数学模型：

minz?1.5x1?1.5x2?2.4x3?0.6x4?1.8x5?x6?0.45x1?0.45x2?1.05x3?0.4x4?0.5x5?0.5x6?6?10x?28x?50x?25x?22x?75x?325123456???415x1?9065x2?2550x3?75x4?15x5?235x6?17500 s.t.??8x1?3x2?53x3?27x4?5x5?8x6?245?0.3x1?0.35x2?0.6x3?0.15x4?0.25x5?0.8x6?5???x1,x2,x3,x4,x5,x6?0

4、下料问题

某钢筋车间要用一批长度为10米的钢筋下料制作长度为三米的钢筋90根和长度为四米的钢筋60根，问怎样下料最省？

解：首先将长度为10米的钢筋下料4米和3米的钢筋，一共有以下下料方式

B1 B2 B3 需要量 4米 2 1 0 60 3米 0 2 3 90 余料 2 0 0 设分别用B1，B2，B3方式下料x1,x2,x3根数，则可建立线性规划问题数学模型：

minz?x1?x2?x3?60?2x1?x2 ?s.t.?2x2?3x3?90?x,x,x?0?123

五、用单纯型方法求解简单的线性规划问题（10分×1=10分）

用单纯形法求解下述LP问题。

(1)maxz?10x1?5x2?3x1?4x2?9?s.t.?5x1?2x2?8?x,x?0?12解：

单纯形方法：引进松弛变量x3,x4，化成标准形：

maxz?10x1?5x2?9?3x1?4x2?x3 ?s.t.?5x1?2x2?x4?8?x,x,x,x?0?1234由于具有明显的可行基，以x3,x4为基变量的基是一个明显的可行基，上述LP标准形式所对应的单纯形表如下，用单纯形方法进行换基迭代：

基 解 x1? x2 x3 x4 比值 9/3=3 9 3 4 1 0 x3 8/5=1.6 2 0 1 ?x4 8 5 0 -10 -5 0 0 z 对应的基可行解为：x1?0,x2?0,x3?9,x4?8,z?0。不是最优基，x1为进基变量，

x4为出基变量，进行换基迭代：

基 解 x1 x2? x3 x4 比值 ?x3 21/5 0 14/5 1 -3/5 1.5. 8/5 1 2/5 0 1/5 4 x1 16 0 -1 0 2 z 对应的基可行解为：x1?1.6,x2?0,x3?4.2,x4?0,z?16。不是最优基，x2为进基

变量，x3为出基变量，进行换基迭代：

基 解 x1 x2 x3 1 0 0 x4 比值 x2 1.5 0 1 x1 1 z 17.5 0 单纯形表中所有检验数均非负。 5/14 -3/14 -1/7 2/7 5/14 25/14 最优解：x1?1,x2?1.5,x3?0,x4?0,maxz?17.5。

(2)maxz?2x1?x25x2?15??6x?2x?24 ?2s.t.?1?x1?x2?5??x1,x2?0解：

引进松弛变量x3,x4,x5，化成标准形：

(2)maxz?2x1?x25x2?x3?15??6x?2x?x?24 ?24s.t.?1?x5?5?x1?x2??x1,x2,x3,x4,x5?0由于具有明显的可行基，以x3,x4,x5为基变量的基是一个明显的可行基，上述LP标准

形式所对应的单纯形表如下，用单纯形方法进行换基迭代：

基 解 x1? x2 15 0 5 2 1 -1 x3 x4 x5 比值 1 0 0 0 0 1 0 0 0 0 1 0 — 24/6=4 5/1=5 x3 ?x4 24 6 x5 5 1 0 -2 z 对应的基可行解为：x1?0,x2?0,x3?15,x4?24,x5?5,z?0。不是最优基，x1为进基变量，x3为出基变量，进行换基迭代：

基 解 x1 x2? x3 x4 5 1/3 2/3 -1/3 1 0 0 0 0 1/6 1 0 0 x5 比值 0 0 15/5=3 4/（1/3）=12 1/（2/3）=1.5 x3 15 0 4 x1 ?x5 1 8 z -1/6 1 1/3 0 对应的基可行解为：x1?4,x2?0,x3?15,x4?0,x5?1,z?8。不是最优基，x2为进基变量，x5为出基变量，进行换基迭代：

基 解 x1 x2 x3 x4 0 1 0 0 0 0 1 0 1 0 0 0 5/4 1/4 x5 -1/2 比值 x3 15/2 x1 7/2 x2 3/2 z 8.5 -15/2 -1/4 3/2 1/4 1/2 单纯形表中所有检验数均非负。最优解：x1?3.5,x2?1.5,x3?7.5,x4?0,x5?0，

maxz?8.5。

六、写出线性规划的对偶问题的数学模型（5分×2=10分）

1、Max. Z = 2X1 + 3X2

St X1 ≤ 8

X2 ≤ 3 3X1 + 4X2 ≤ 2 X1 , X2 ≥ 0

Min. Z = 8Y1 + 2Y2 + 2Y3

St Y1 + 3Y3 ≥ 2

Y2+ 4Y3 ≥ 3 Y1 , Y2 , Y3 ≥ 0

2、Max. Z = 3X1 + 5X2

St 4X1 + X2 ≤ 8

2X1 + 4X2 ≤ 13 5X1 + 2X2 ≤ 16 3X1 + 2X2 ≤ 2 X1 , X2 ≥ 0

Min. Z = 8Y1 + 13Y2 + 16Y3 + 2Y4

St 4Y1 + 2Y2 + 5Y3 + 3Y4 ≥ 3

Y1 + 4Y2 + 2Y3 + 2Y4 ≥ 5 Y1 , Y2 , Y3 , Y4 ≥ 0

3、Min. Z = 12Y1 + 10Y2

St Y1 + 5Y2 ≥ 10

2Y1 + 6Y2 ≥ 9 3Y1 + 7Y2 ≥ 8 4Y1 + 8Y2 ≥ 7 5Y1 + 9Y2 ≥ 6 Y1 , Y2 ≥ 0

Max. Z = 10X1 + 9X2 + 8X3 + 7X4 + 6X5

St X1 + 2X2 + 3X3 + 4X4 + 5X5 ≤ 12

5X1 + 6X2 + 7X3 + 8X4 + 9X5 ≤ 10 X1 , X2 , X3 , X4 , X5 ≥ 0

4、Min. Z = 12Y1

St Y1 ≤ 10

2 Y1 ≤ 9 3 Y1 ≤ 8 4 Y1 ≤ 7 5 Y1 ≤ 6 Y1 ≥ 0

Max. Z = 10X1 + 9X2 + 8X3 + 7X4 + 6X5

St X1 + 2X2 + 3X3 + 4X4 + 5X5 ≤ 12

X1 , X2 , X3 , X4 , X5 ≤ 0

七、利用最小元素法（沃格尔法）求解产销平衡的运输问题，并用闭回路法（位势法）检验

是否是最优解。（10分×1=10分）

1、 利用最小元素法，求解产销平衡的运输问题，并用闭回路法检验是否是最优解，不要求

调整基解找更优的解。（10分×1=10分）

某公司经销甲产品。该公司下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往4个销售点。各销售点的每日销量为：B1为3吨，B2为6吨，B3为4吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。请利用最小元素法求解并用闭回路法检验和调整，确定公司在满足各销售点的需要量的前提下，使总运费为最少。 A1 A2 A3 销量 解： A1 A2 A3 销量 非基变量的检验数：

A1 A2 A3 销量

调整：

A1 A2 A3 销量

B1 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 产量 7 4 9 B1 3 3 B2 6 6 B3 4 1 5 B4 3 3 6 产量 7 4 9 B1 1 10 3 B2 2 1 6 B3 12 5 B4 -1 6 产量 7 4 9 B1 3 3 B2 6 6 B3 5 5 B4 2 1 3 6 产量 7 4 9

非基变量的检验数：

A1 A2 A3 销量 B1 0 9 3 B2 2 2 6 B3 1 12 5 B4 6 产量 7 4 9 检验数大于等于零，最优解。 最小费用85。

2、 利用沃格尔法求解产销平衡的运输问题，并用位势法检验是否是最优解。（10分×1=10

分）

某公司经销甲产品。该公司下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往4个销售点。各销售点的每日销量为：B1为3吨，B2为6吨，B3为4吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。请利用伏格尔法求解并用闭回路法检验和调整，确定公司在满足各销售点的需要量的前提下，使总运费为最少。 解： A1 A2 A3 销量 非基变量的检验数： A1 A2 A3 销量 B1 0 9 3 B2 2 2 6 B3 1 12 5 B4 6 产量 7 4 9 B1 3 3 B2 6 6 B3 5 5 B4 2 1 3 6 产量 7 4 9 检验数大于等于零，最优解。 最小费用85。

本文来源：https://www.bwwdw.com/article/wiut.html