运筹学习题精选

1．在线性规划模型中，没有非负约束的变量称为……………………………………………………( C )

A．多余变量 B．松弛变量 C．自由变量 D．人工变量 2．约束条件为AXb,X0的线性规划问题的可行解集是………………………………………( B )

A． 补集 B．凸集 C．交集 D．凹集 3．线性规划问题若有最优解，则一定可以在可行域的（ C）上达到。

A．内点 B．外点 C．顶点 D．几何点 4． 线性规划标准型中bi（i=1，2，……m）必须是…………………………………………………( B)

A．正数 B．非负数 C．无约束 D．非零的 5． 线性规划问题的基本可行解X对应于可行域D的………………………………………………( D)

A．外点 B．所有点 C．内点 D．极点 6．基本可行解中的非零变量的个数小于约束条件数时，该问题可求得……………………………( B ) A．基本解 B．退化解 C．多重解 D．无解

7．满足线性规划问题全部约束条件的解称为…………………………………………………( C )

A．最优解 B．基本解 C．可行解 D．多重解 8．线性规划一般模型中，自由变量可以用两个非负变量的（B ）代换。

A．和 B．差 C．积 D．商 9．当满足最优检验，且检验数为零的变量的个数大于基变量的个数时，可求得………………………( A )

第 1 页 共 16 页

A．多重解 B．无解 C．正则解 D．退化解 10．若线性规划问题有最优解，则必定存在一个( D )是最优解。

A．无穷多解 B. 基解 C. 可行解 D. 基可行解 填空

计算 1． 某厂生产甲、乙、丙三种产品，已知有关数据如下表所示,求使该厂获利最大的生产计划。

2． 目标函数为max Z =28x4+x5+2x6，约束形式为“≤”，且x1，x2，x3为松弛变量，

表中的解代入目标函数中得Z=14，求出a~g的值，并判断是否最优解。 cj 0 0 0 28 1 2 x3 x5 x6 CB 基 b x1 x2 x4 2 x6 A 3 0 -14/3 0 1 1 0 x2 5 6 D 2 0 5/2 0 28 x4 0 0 E F 1 0 0 cjzj B C 0 0 -1 G

第 2 页 共 16 页

3． 某工厂生产A、B两种产品，已知生产A每公斤要用煤6吨、电4度、劳动力3个；生产B每公斤要用煤4吨、电5度、劳动力10个。又知每公斤A、B的利润分别为7万元和12万元。现在该工厂只有煤360吨、电200度、劳动力300个。问在这种情况下，各生产A、B多少公斤，才能获最大利润，请建立模型[仅建立模型，不求解]。

4． 已知单纯形表如下，其中x1,x2,x3表示三种产品的产量，x4,x5是松弛变量（目标函数为max Z）

（1）、写出此时生产方案，并判断是否最优生产方案。 （2）、该生产方案下每种产品的机会费用。 （3）、以此表为基础，请求出最优生产方案。

答：（1）生产方案是：不生产1、3两种产品，只生产第2种产

品100/3个单位，不是最优方案。

（2）30，45，15.

（3）最优生产方案：不生产第3种产品，1、2两种产品各生产20个单位，最大利润1700。

5．给出下面线性规划的标准形式，并用图解法求解

maxzx12x26xs.t.1x1x1,5x22x2x2x2015245

第 3 页 共 16 页

解：标准形式如右下：

maxzx12x26xs.t.1x1x1,L,5x2x32x2x4x2x5x5015245 最优解为：x1=2，x2=3 z*=8 资源2剩余6

6．某公司生产两种产品，其耗材获利情况如下表，问如何获利最大？ 产品1 产品2 资源量 原料1 0.4 0.5 20 原料2 0 0.2 6 原料3 0.6 0.3 21 获利 40 30 请你(1)建立线性规划模型，(2)并用单纯形法求解，(3)根据单纯形表最终结果分析，若产品1的

获利上升到56，最优解是否会变化？若同时产品2的获利下降到24，最优解是否会变化？ 解：（1）设产品1、2的产量分别为x1、x2，可得如下模型：

maxz40x130x20.4x1s.t.0.6x1x1 （2）单纯形表求解结果为： 0 0 12 1 A 0 1 0 0 B 4 1 0 3 C 10 0 6 0 D 甲 乙 丙 丁 ,0.5x20.2x20.3x2x2020621

x125,x220,资源2剩余2

通过代入参数到最终单纯形表，结合检验数可得： （3）若产品1的获利上升到56，最优解不会变化

若同时产品2的获利下降到24，最优解会变化

7．已知某线性规划问题的初始单纯形表和用单纯形迭代后得到的表如下，运用单纯形法的向量矩阵的方法求格中的未知数a,b,c,d,e,f,g,h,i,j,k,l。P47-1.8

xxxxx x1 x2 x3 x4 x5 35124

x1 f g 2 -1 1/2 0 x4 6 b c d 1 0 x5 4 h i 1 1/2 1 x5 1 -1 3 E 0 1

cz0 -7 j k l cjzj a -1 2 0 0 jj 第 4 页 共 16 页

解： 8．已知某线性规划问题用单纯形迭代时得到中间某两步的单纯形表如下表所示，试将表中空白处数字填上。P48-1.10

cj 3 5 4 0 0 0 CB 5 0 0 5 4 3 基 b x1 2/3 -4/3 5/3 -1/3 x2 1 0 0 0 x3 0 5 4 4 x4 1/3 -2/3 -2/3 -5/3 15/41 -6/41 -2/41 x5 0 1 0 0 8/41 5/41 -12/41 x6 0 0 1 0 -10/41 4/41 15/41 x2 8/3 x5 14/3 x6 29/3 cjzj x2 x3 x1 cjzj

证明

1． 证明若线性规划问题存在可行解，则问题的可行域必定是凸集。 2．

第二章 线性规划的对偶理论 选择

1．对偶问题的对偶是……………………………………………………………………( )

A．基本问题 B．解的问题 C．其它问题 D．原问题 正确答案为：4

2．若原问题是一标准型，则对偶问题的最优解值就等于原问题最优表中松弛变量的( )A．值 B．个数 C．机会费用 D．检验数 正确答案为：3

3．若原问题中xI为自由变量，那么对偶问题中的第i个约束一定为………………( )

第 5 页 共 16 页

A．等式约束 B．“≤”型约束 C．“≥”约束 D．无法确定 正确答案为：1

4．原问题的第i个约束方程是“=”型，则对偶问题的变量qi是…………………… ( )

A．多余变量 B．自由变量 C．松弛变量 D．非负变量 正确答案为：B 5． 若原问题求目标最小，则对偶问题的最优解值就等于原问题最优表中多余变量的……………( )

A．机会费用 B．个数 C．值 D．机会费用的相反数 正确答案为：D

6．原问题与对偶问题的最优（ ）相同。

A．解 B．目标值 C． 解结构 D．解的分量个数 正确答案为：B

填空

1．对偶理论中，如原问题具有无界解，则其对偶问题的解的情况为 。

2．对偶理论中，如原问题无可行解时，其对偶问题的解的情况为 。

3．对偶理论中，若线性规划问题的最优解中，对应某一约束条件的对偶变量值为非零，则该约束条件一定是严格的 (等式或不等式)，反之，如果约束条件取严格不等式，则其对应的对偶变量一定 (为零或不为零)。

计算

1. 写出该线性规划问题的对偶问题，求出原问题的最优

第 6 页 共 16 页

解。

对偶问题的最优解为（0，0，4，4），原问题的最优解为（6/5，1/5）

max z2x13x22x12x2122． 若某线性规划问题的标准模型为：4x1 16s.t. 5x215 x20x1, 形表为： 且按单纯形法求解的其最优单纯

cj 2 3 0 0 0 CB 2 基 b x1 1 0 0 0 x2 0 0 1 0 x3 1/2 -2 0 -1 x4 0 1 0 0 x5 -1/5 4/5 1/5 -1/5 x1 3 x4 4 0 x2 3 3 cjzj (1) 如果相应的目标系数c1,c2由2,3分别变为21和32，试运用灵敏度分析知识分析

1和2分别在什么范围变化，问题的最优解不变。

(2) 如果标准模型中的常数列由12,16,15分别变为121,162,153，试运用灵敏度分析

知识分析1和2和3分别在什么范围变化，问题的最优基不变。

(3) 如标准模型中增加了一个变量x6，且相应的目标系数c64,最初单纯形表中的

P6(2,4,5)T，试运用灵敏度分析的知识分析问题最优解的变化。

(4) 如在标准模型中增加了一个约束条件3x12x214，试运用灵敏度分析知识分析最优解

的变化。

(5) 若相应的目标系数c1,c2由2,3分别变为22和3，试运用参数线性规划的知识分析

最优解随参数变化情况，并画出目标函数最优值随参数变化图。

15，试运用参数线性规划的知(6) 如果标准模型中的常数列中第三个约束的常数由15变为识分析最优解随参数变化情况，并画出目标函数z()最优值随参数变化图。

第 7 页 共 16 页

max z2x1x25x36x42x1x3x483． 已知线性规划问题s.t.2x12x2x32x412x1,x2,x3,x40y14,y21

(1) 写出线性规划问题的对偶问题

(2) 运用对偶理论分析求解原线性规划问题的最优解。

若其对偶问题的最优解为

max z(c1t1)x1c2x2c3x30x40x54． 已知线性规划问题

a11x1a12x2a13x3x4b13t2s.t.a21x1a22x2a23x3x5b2t2x1,x2,x3,x4,x50x3 当t1t10时，求得

问题的最终单纯形表为：P78-2.11 x1 x2 x4 x5 x3 5/2 0 1/2 1 1.2 0 x1 5/2 1 -1/2 0 -1/6 1/3 cjzj 0 -4 0 -4 -2 (1) 确定a11,a12,a13,a21,a22,a23,c1,c2,c3,b1,b2的值。

(2) 当t20时,t1值在什么范围内变化，上述最优解不变。 (3) 当t10时,t2值在什么范围内变化，上述最优基不变。

证明.

1. 叙述并证明对偶问题的基本性质中的弱对偶性。 5． 试叙述并证明对偶问题的基本性质中的最优性。 6． 试叙述并证明对偶定理(强对偶性)。 第三章 运输问题 选择

1. 若运输问题已求得最优解，此时所求出的检验数一定是全部…………………………………( ) A．大于或等于零 B．大于零 C．小于零 D．小于或等于零 正确答案为：1 2． 运输问题中，m+n-1个变量构成基本可解的充要条件是它不含……………………………………( ) A．松弛变量 B．多余变量 C．闭回路 D．圈 正确答案为：C 填空 计算

1． 根据所给的表和一组解判断是否最优解，若不是，请求出最优解。

第 8 页 共 16 页

（x13, x14, x21, x22, x32, x34）=（5，2，3，1，5，4）

2. 求运输问题的最优解。

解：增加一个产地，最优解：A1 →B1，5；A1 →B2，15；A1 →B3，5；A1 →B4，15；A2 →B4，30；A3 →B3，30；虚产地 →B4，5

3．某部门有3个生产同类产品的工厂，生产的产品由4个销售点出售，各厂产量、各地销量和各厂到销售点的单位运价如下表，为使得总运费最小，请用西北角法求初始解，用表上作业法找出最优运输方案。

工厂 销售点 A1 A2 A3 销量 解：最后得结果如下 4 4 14 12 6 8 B1 4 2 8 8 B2 12 10 5 14 B3 4 3 11 12 B4 11 9 6 14 产量 16 10 22 48 即运输方案为：A1→B1运4，A1→B3运12，A2→B1运4，A2→B4运6，A3→B2运14，A3→B4运8 或 8 14 12 4 2 8 即运输方案为：A1→B3运12，A1→B4运4，A2→B1运8，A2→B4运2，A3→B2运14，A3

第 9 页 共 16 页

→B4运8

4．试分析发生下列情况时，运输问题的最优调动方案及总运价有何变化。 (1) 单位运价表第r行的每个cij都加上一个常数k。 (2) 单位运价表第p列的每个cij都加上一个常数k。P100-3.2

5．已知运输问题的产销平衡表，最优调运方案及单位运价表分别如下表所示：P101-3.3

产销平衡表及最优方案 销地 B1 B2 B3 B4 产量 产地 A1 A2 A3 销量 产地 0 5 5 销地 5 10 15 10 15 25 5 15 15 10 单位运价表 B1 B2 B3 B4 10 12 2 1 7 14 20 9 16 11 20 18 A1 A2 A3 试分析：(1) 从A2到B2的单位运价c22在什么范围变化时，上述最优调运方案不变； (2) 从从A2到B4的单位运价c24变为何值时，将有无限多最优调运方案。

6．已知运输问题的产销平衡表，某一调运方案及单位运价表分别如下表所示：P103-3.7

产销平衡表及某一调运方案 销地 B1 B2 B3 产量 产地 A1 A2 A3 销量 1 6 5 1 2 6 1 8 7 5 3 单位运价表 销地 B1 B2 B3 产地 A1 A2 A3 2 3 5 3 2 8 11 8 15 (1) 以调运方案对应的变量为基变量，列出该运输问题用单纯形表求解时的单纯形表。 (2) 在单纯形表上判断该调运方案是否最优，若否，用单纯形法继续迭代求出最优。 (3) 在最终单纯形表上判别c33在什么范围内变化，表中最优调运不变。

第 10 页 共 16 页

证明

第四章 整数规划与分配问题 选择

1．对max型整数规划，若最优非整数解对应的目标函数值为Zc，最优整数解对应的目标值为Zd，那么一定有……………………………………………………………………( )

A．Zc ∈Zd B．Zc =Zd C．Zc ≤Zd D． Zc ≥Zd 正确答案为：4 2． 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是………………………( ) A．非负的 B．大于零 C．无约束 D．非零常数 正确答案为：A 3．用割平面法求解整数规划时，构造的割平面只能切去………………………………( ) A．整数可行解 B．整数解最优解 C．非整数解 D．无法确定 正确答案为：C 4．只有一部分变量限制为整数的线性规划称为…………………………………………………………( ) A．混合整数规划 B．局部整数规划 C．部分整数规划 D．0—1规划 正确答案为：A 6. 若是否采用j项目的0-1变量为xj,那么J个项目中至多只能选择一个项目的约束方程为…( )

A.

xiJi1 B. xi1 C. xi1 D. xi1 正确答案为：C

iJiJiJ 填空

1. 整数规划的分配问题中，若效率矩阵的元素可分成0与非0两部分，则覆盖元素的最少直线数 不同行不同列的0元素的最大个数。[填大于，等于或小于] 计算

1． 有一份说明书，要分别译成英、日、德、俄四种文字（分别用E、J、G、R表示），由甲、乙、丙、

丁四人去完成。每个人完成任务所需时间见表所示。问怎样安排，才能使所用的时间最少？

2．指派4个工人完成四项工作，每人做各项工作所耗时间如下表：

工人 工作 甲 乙 丙 A 15 19 26 B 18 23 17 C 21 22 16 23 D 24 18 19 17

丁 19 21 问如何安排可使总耗时最少？（用匈牙利法求解） 解：匈牙利法求解如下 0 1 10 2 2 4 0 3 6 4 0 6 9 0 3 0 V V 第 11 页 共 16 页

0 0 10

V

1 V 2 3 0 2 6 3 0 5 10 0 4 0 V V V V

工作安排：甲——A、乙——D、丙——C、丁——B 或 甲——B、乙——A、丙——C、丁——B 最小耗时为70

3．已知某纯整数标准线性规划，运用割平面法求解，第一步得到该问题的最优单纯形表如下：

x3 CB 基 b x1 x2 x4 x2 5/2 x1 13/4 3 cjzj 2 0 1 0 1 0 0 1/2 -1/4 -1/4 -1/2 3/4 -5/4 试简要说明并写出运用割平面法继续求解的下一步所确定的Gomory约束不等式。

2． 试0－1变量将下列叙述成一般线性约束条件。

(1) x1x22或2x13x25

(2) 变量x只能取0,3,5或7中的一个。 (3) 变量x或等于0，或50。 证明 1．证明：如果从分配问题的效率矩阵的每一行元素分别减去一个常数，从每一列分别减去一个常数，得到一个新的效率矩阵，则以新效率矩阵的分配问题模型与原分配问题的最优解相等价。 第五章 目标规划 选择 填空 计算

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

p1：利润指标为1.6×104元/月； p2：充分利用生产能力； p3：加班时间不超过24小时； p4：产量以预计销量为标准。 为确定生产计划，请你为该问题建立目标规划模型（不求解）。 解：设生产A、B、C三种规格电视机各为x1,x2,x3，目标规划模型为

第 12 页 共 16 页

minP1d1P2d2P3d3P4d4d4d5d5d6d6500x1650x2800x3d1d11.61046x18x210x3d2d2200ddd24332x1d4d412s.t.xdd25510xdd6663xi0,i1,2,3dj,dj0,j1,2,3,4,5,61． 用图解法求解下面目标规划问题：

min zP1d1P2d2P3(5d33d4)P4d1x12x2d1d16x2xdd22291(1) s.t.x12x2d3d34 xdd2442x1,x2,di,di0

证明

第八章 动态规划 选择 填空 计算

1．某工厂自国外进口一部精密仪器，从制造厂至出口港有三个港口可选，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间运输成本如下图所示，用逆序解法求运费最低的路线。

第 13 页 共 16 页

解：逆序解法图示如下(粗线部分为可行路径)

运费最低为110，相应的路线可以为：

A→B2→C1→D1→E或者A→B3→C1→D1→E或者A→B3→C2→D2→E.

max z4x19x22x32．运用动态规划的方法求解：

2x1x2x310s.t x1,x2,x30

证明

第十一章 决策分析 选择 填空 计算

1. 某书店希望订购最新出版的图书出售，根据以往经验，新书的销售量可能为50,100,150或200

本，假定每本书的订购价为4元，销售价为6元，剩书处理价为每本2元，要求：(1) 建立条件收益矩阵；(2) 分别依据悲观主义、乐观主久及等可能性决策准则，决定该书店订购新书的数量；(3) 建立机会损失矩阵，并依据最小机会损失的决策准则决定订购数量；(4) 如果书店统计过去销售新书数量的规律如下图所示，求(a) 分别用EMV和EOL准则决定订购数量；(b) 假如书店负

第 14 页 共 16 页

责人能够确切掌握新书销售量的情况，试求EPPI和EVPI。 销售量 50 100 150 占的比率（%） 20 40 30 200 10

2． 某钟表公司计划通过它的销售网销售一种低价钟表，计划每块售价10元，生产这种钟表有三个

设计方案，方案I需一次投资10万元，以后生产一个的费用为5元；方案II需一次投资16万元，以后生产一个的费用为4元；方案III需一次投资25万元，以后生产一个的费用为3元；对该种钟表的需求量为未知，但估计有三种可能：E130000;E2120000;E3200000;要

求：(1) 建立这个问题的收益矩阵；(b) 分别用悲观主义、乐观主义和等可能性的决策准则来决定该公理公司应采用哪一个设计方案；(c) 建立机会损失矩阵，并用最小机会的决策准则决定采用哪一种设计方案。

证明

第十二章 博弈论 选择 填空

甲、乙两人游戏者在互不知道情况下，同时伸出一、二或三个指头，用k表示两人伸出指头总和，如果k为偶数，甲付给乙k元；k为奇数，乙付给甲k元，试列出对甲的赢得矩阵。 计算

1. 已知甲、乙二人零和博弈中对甲的赢得矩阵如下，求双方的最优策略与对策值。[需给出求解过程的相应准则说明，只有结果不作过程说明，不给分]

86282102032 8945 1753532142．求下列博弈中的纳什均衡解：

B A b1 b2 b3 a1 a2 a3

B A (2,0) (1,1) (4,2) (3,4) (1,3) (1,3) (1,3) (0,2) (3,0) b1 b2 b3 a1 a2 a3 (1,-2) (-2,1) (0,0) (-2,1) (1,-2) (0,0) (0,0) (0,1) (1,0)

3. 求下表所示博弈形式的混合策略解。[提示：运和混合策略的线性规划法求解。]

B b3 b1 b2 b4 A 第 15 页 共 16 页

a1 a2 a 1 3 0 4 2 4 8 3 3 7 2 7 3 证明

第九章 存贮论 选择 填空 计算 证明

第十章 排队论 选择 填空 计算 证明

第 16 页 共 16 页