1、1运筹学与系统分析 复习资料一 单选题1 在产销平衡运输问题中，设产地为 m个，销地为 n个，那么解中非零变量的个数【 C 】A.等于( m+n-1) B.不能小于( m+n-1) C. 不能大于( m+n-1) D.不确定2 在单纯形表的终表中，若非基变量的检验数有 0，那么最优解【 B 】A.不存在 B.唯一 C. 无穷多 D.无穷大3.在 用 对 偶 单 纯 形 法 解 最 大 化 线 性 规 划 问 题 时 ， 每 次 迭 代 要 求 单 纯 形 表 中【 D 】A.b列 元 素 不 小 于 零 B.检 验 数 都 大 于 零C.检 验 数 都 不 小 于 零 D.检 验 数 都 不
2、大 于 零4 在 约 束 方 程 中 引 入 人 工 变 量 的 目 的 是 【 D 】A.体现变量的多样性 B.变不等式为等式 C.使目标函数为最优 D.形成一个单位矩阵5 若 运 输 问 题 已 求 得 最 优 解 ， 此 时 所 求 出 的 检 验 数 一 定 是 全 部 【 A 】A.大于或等于零 B.大于零 C.小于零 D.小于或等于零 6在线性规划模型中，没有非负约束的变量称为 【 C 】 A.多余变量 B.松弛变量 C.自由变量 D.人工变量 7 线性规划问题的最优解对应其可行域的【 B 】 A.内点 B.顶点 C.外点 D.几何点8 对 偶 问 题 的 对 偶 是 【 D 】A
3、.基本问题 B.解的问题 C.其它问题 D.原问题 9 原问题与对偶问题具有相同的最优【 B 】A.解 B.目标值 C.解结构 D.解的分量个数10 在对偶问题中，若原问题与对偶问题均具有可行解，则【 A 】A.两者均具有最优解，且它们最优解的目标函数值相等B.两者均具有最优解，原问题最优解的目标函数值小于对偶问题最优解的目标函数值C.若原问题有无界解，则对偶问题无最优解2D.若原问题有无穷多个最优解，则对偶问题只有唯一最优解11 表上作业法中初始方案均为【 A 】A.可行解 B.非可行解 C.待改进解 D.最优解12若原问题中 xi为自由变量，那么对偶问题中的第 i个约束一定为【 A 】A.
4、等式约束 B.“”型约束 C.“”约束 D.无法确定13线性规划一般模型中，自由变量可以代换为两个非负变量的【 B 】A.和 B.差 C.积 D.商 14建立运筹学模型的过程不包括的阶段是【 D 】A.观察环境 B.数据分析 C.模型设计 D.模型实施 15 使用人工变量法求解极大化线性规划问题时，当所有的检验数 0j，在基变量中仍含有非零的人工变量，表明该线性规划问题 【 D 】A.有唯一的最优解 B.有无穷多个最优解 C.为无界解 D.无可行解16 线性规划模型不包括的要素有【 D 】A.目标函数 B.约束条件 C.决策变量 D.状态变量二 填空题1 线性规划问题的可行解是指满足约束条件和
5、非负条件解 。2 若 线 形 规 划 问 题 存 在 可 行 解 ， 则 该 问 题 的 可 行 域 是 凸 集 。3 线 性 规 划 问 题 有 可 行 解 ， 则 必 有 。5 动 态 规 划 模 型 中 ， 各 阶 段 开 始 时 的 客 观 条 件 叫 做 状 态 。6 当 线 性 规 划 问 题 的 系 数 矩 阵 中 不 存 在 现 成 的 可 行 基 时 ， 一 般 可 以 加 入人 工 变 量 构 造 可 行 解 。7 在 大 M 法 中 ， M 表 示 人 工 变 量 一 个 绝 对 值 很 大 的 负 系 数 。8 线 形 规 划 问 题 的 标 准 形 式 是 ： 目 标
6、 函 授 是 求 是 确 定 的 ， 约 束 条 件 全为 线 性 等 式 ， 约 束 条 件 右 侧 常 数 项 全 为 非 负 值 。9 线性规划的右端常数项其对偶问题的 价 值 系 数 ；线性规划的第 i个约束条件其对偶问题 决 策 变 量 。310在一个基本可行解中，取正数值的变量称为 基 变 量 ；取零值的变量称为 非 基 变 量 。11在线性规划模型中，没有非负约束的变量称为 自 由 变 量 。12为求解需要量大于供应量的运输问题，可虚设一个供应点，该点的供应量等于 需 求 量 与 供 应 量 的 差 值 。13 线 性 规 划 问 题 可 分 为 目 标 函 数 求 极 大 值
7、和 极 小 值 两 类 。14 若线性规划为最大化问题，则对偶问题为 极 小 化 问 题 。15 用 运 筹 学 解 决 问 题 的 核 心 是 建 立 数 学 模 型 ， 并 对 数 学 模 型 求 解 。16 在 将 线 性 规 划 问 题 的 一 般 形 式 化 为 标 准 形 式 时 ， 引 入 的 松 弛 变 量 在 目 标 函 数中 的 系 数 为 零 。17 动 态 规 划 模 型 的 构 成 要 素 有 阶 段 、 状 态 、 决 策 和 策 略 、 状 态 转 移 和 目 标 函 数 。三计算题1用大 M法求解线性规划问题MinZ = 3X1 + X2+ X3s.t X12X
8、2 + X3 114X1+ X2 + 2X3 32X1X31X1 , X2,X3 0解：（1）将线性规划化为标准型。引入松弛变量 ，剩余变量 ，并令4x5x;Z得：123412354max =.,0xstxx约束方程系数矩阵 A为：1 -2 40-1 A4A中只有一个单位列向量，故对第二、第三个约束条件引入人工变量 ， 对6x7模型整理得： 123674123567max Z=4.0; ,.jxMxstx改造后的系数矩阵 A为：1 -2 04-1 0 A以 为初始基变量进行单纯形法求解如下表。467,x3 -1 -1 0 0 MBCX jcjxb1x23x45x67xj0 411 1 -2 1
9、 1 0 0 0 11/1M6x3 -4 1 2 0 -1 1 0 3/271 -2 0 1 0 0 0 1 1Z4M 3-6M -1+M -1+3M 0 -M 0 00 4x10 3 -2 0 1 0 0 -1 -M61 0 1 0 0 -1 1 -2 1-1 3x1 -2 0 1 0 0 0 1 -Z1+M 1 -1+M 0 0 -M 0 1-3M0 412 3 0 0 1 -2 2 -5 45-1 2x1 0 1 0 0 -1 1 -2 -1 31 -2 0 1 0 0 0 1 -Z2 1 0 0 0 -M 1-M -1-M3 1x4 1 0 0 1/3 -2/3 2/3 -5/3-1
10、21 0 1 0 0 -1 1 -2-1 3x9 0 0 1 2/3 -4/3 4/3 -7/3Z-2 0 0 0 -1/3 -1/3 1/3-M 2/3-M故，当 时，取得最优解。 。1234,x 2Z2用单纯形法求解下列线性规划,解出最优解。MaxZ = 3X1 + 4X2s.t X1 + X2 42X1+ 3X2 6X1 , X2 0解：将线性规划化成标准型，引入松弛变量 和 ：3x4123124max Z=.6,0xst系数矩阵 A为： ，以 和 为初始基变量计算，单纯性计算表1 033x4如下表。3 4 0 0BCX jcjxb1x2x3x4xj0 34 1 1 1 0 460 4x
11、6 2 3 0 1 2Z0 3 4 0 00 32 1/3 0 1 -1/3 64 2x2 2/3 1 0 1/3 3Z8 1/3 0 0 -4/30 31 0 -1/2 1 -1/23 1x3 1 3/2 0 1/2Z9 0 -1/2 0 -3/2故，当 时，线性规划取得最大值 。12,9Z3已知：运输问题的单价表。（1） 用最小元素法找出初始可行解；（2） 用位势法求出初始可行解相应的检验数；（3） 求最优方案。单位：万元单价 甲 乙 丙 供给量A 3 5 8 10B 7 4 6 20C 3 2 9 10需求量 5 25 5解：（1）用最小元素法求初始可行解。设供应地 A、B、C 到甲、乙
12、、丙三地的运价分别为 ；运量分别为 。由ijcijx于总的供给量为 40，需求量为 35，为供给量大于需求量的不平衡运输问题，增设一个假想需求地丁，需求量为 5，A、B、C 到给地的运价均为零。运价表变更为：单价 甲 乙 丙 丁（存储） 供给量7A 3 5 8 0 10B 7 4 6 0 20C 3 2 9 0 10需求量 5 25 5 5 40先不考虑丁地的需求，由表格可知 的运价最小，C 全部供应乙地，乙地32x需求还剩 15；依次找出最小运价，首先满足其需求，重复此过程，可以得出初始可行解，如下表所示：运量 甲 乙 丙 丁A 5 3 0 5 0 8 5 0B 0 7 15 4 5 6 0
13、 0C 0 3 10 2 0 9 0 0（2）用位势法求检验数。设 ；可知1,u1142232;4;6;uvuvuv代入，可解： ；计算如下表：12330; .0甲 乙 丙 丁 甲 乙 丙 丁A 3 0 1uA 3 4 6 0 0B 4 6 2B 3 4 6 0 0C 2 3C 1 2 4 -2 -21v3v43 4 6 0成本表 ijuv根据 计算如下表：()ijijijcuvij ijv甲 乙 丙 丁 甲 乙 丙 丁A 3 5 8 0 A 3 4 6 0B 7 4 6 0 B 3 4 6 0C 3 2 9 0 C 1 2 4 -28ij甲 乙 丙 丁A 0 1 2 0B 4 0 0 0C
14、2 0 5 2故，所有检验数均为非负值，得到最优解： 122325,;5;10xx最小运价 min3146Z4将下述线性规划模型化为标准型MinZ = X1X2+3 X3s.t X1X2 + X3 105X17X2 + 3X38X1X22X318X10, X20,X3 无符号限制解，引入松弛变量 ， ，剩余变量 ，两个非负变量 和 ，且4x65x3x。33x令 ，则线性规划的标准型为：Z12331234536123456ma =078.8,0xxstx5有四项工作要甲，乙，丙，丁四个人去完成，每一项工作只许一个人去完成，四项工作要四个不同的人去完成；问：应指派每个人完成哪一项工作，使得总的消耗
15、时间为最短？用匈牙利法求解。消耗时间 工作 1 工作 2 工作 3 工作 4甲 15 18 21 249乙 21 23 22 18丙 26 17 16 19丁 23 21 19 17解：（1）以各员工完成各项工作的时间构造矩阵一，如下：矩阵一 15 82 4316 7 9（2）对矩阵一进行行约减，即每一行数据减去本行数据中的最小数，得矩阵二。矩阵二 0 36 9541 2（3）检查矩阵二，若矩阵二各行各列均有“0” ，则跳过此步，否则进行列约减，即每一列数据减去本列数据中的最小数，得矩阵三。矩阵三 0 26 9341 （4） 画“盖 0”线。即画最少的线将矩阵三中的 0全部覆盖住0 26 93
16、41 （5） 数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步，若“盖0”线得数目小于矩阵得维数则进行数据转换，本题属于后一种情况，应进行转换，操作步骤如下：A、找出未被“盖0”线覆盖的数中的最小值 ，例中 2。B、将未被“盖0”线覆盖住的数减去 。C、将“盖0”线交叉点的数加上 。10可得矩阵四 0 26 1 54（6）重复步骤（4） 、 （5）直到“盖 0”线的数目等于矩阵的维数，计算过程如下。 0 26 1 54得到矩阵五 0 26 1 54（7）求最优解。对n维矩阵，找出不同行、不同列的n个“0” ，每个“0”的位置代表一对配置关系，具体步骤如下：A、先找只含有一个“0”的行（或列） ，将该行（或列）中的“0”打“” 。B、将带“”的“0”所在列（或行）中的“0”打“ ”。C、重复（1）步和（2）步至结束。若所有行列均含有多个“0” ，则从“0”的数目最少的行或列中任选一个“0”打“” 。0 26 111 2 2 010 0 0 541 0 0故，工作分配关系结果如下表。即甲完成工作 1，乙完成工作 4，丙完成工作2，丁完成工作 3。消耗时间 工作 1 工作 2 工作 3 工作 4甲 15乙 18丙 17丁 19
