五、运输问题（10分）
求总运费最小的运输问题，某步运输图如下：
(1) 写出a, b ,c ,d ,e的值，并求出最优运输方案；
(2) A3到B1的单位运费满足什么条件时，表中运输方案为最优方案。
六、指派问题（10分）
分配甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间如下表，试确定总花费时间为最少的指派问题。
人 任务 甲 乙 丙 丁 戊 A 12 8 7 15 4 B 7 9 17 14 10 C 9 6 12 6 7 D 7 6 14 6 10 E 9 6 9 10 9 七、求下图所示容量网络中从vs～vt的最大流。其中每边上的数为(cij,fij)。
一、多项选择题（18分） 1、 线性规划模型有特点（ ）
A、 所有函数都是线性函数； B、 目标求最大；
6
C、 有等式或不等式约束； D、 变量非负。
2、 下面命题正确的是（ ）。
A、 线性规划的最优解是基本可行解； B、 基本可行解一定是基本解； C、 线性规划一定有可行解； D、 线性规划的最优值至多有一个。
3、 一个线性规划问题（P）与它的对偶问题（D）有关系（ ）。
A、（P）有可行解则（D）有最优解； B、（P）、（D）均有可行解则都有最优解； C、（P）可行（D）无解，则（P）无有限最优解； D、（P）（D）互为对偶。
4、 运输问题的基本可行解有特点（ ）。
A、 有m＋n－1个基变量； B、 有m+n个位势； C、 产销平衡； D、 不含闭回路。
5、 关于动态规划问题的下列命题中（ ）是错误的。
A、 动态规划分阶段顺序不同，则结果不同； B、 状态对决策有影响；
C、 在求解最短路径问题时，标号法与逆序法求解的思路是相同的； D、 动态规划的求解过程都可以用列表形式实现。
二、计算题
1、某公司下属的3个分厂A1、A2、A3生产质量相同的工艺品，要运输到B1、B2、B3、B4 ，4个销售点，分厂产量、销售点销量、单位物品的运费
数据如下：
求最优运输方案。 2、考虑下列线性规划：
7
最优单纯形表为：
（1）、写出此线性规划的最优解、最优基 B 和它的逆 B-1 ； （2）、求此线性规划的对偶问题的最优解；
（3）、试求 c2 在什么范围内，此线性规划的最优解不变； （4）、若 b1 = 20 变为 45，最优解及最优值是什么？
3、某公司决定投资60万元（以10万元为单位），以提高三种主要产品 A、B、C 的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下：
试确定如何安排对各种产品的投资数，可获得最大总期望利润？
maxz?2x1?x2?x3?一、有下面线性规划：?x1?x2?2x3?10s.t.? ?x1?x2?x3?20???xj?0,j?1.2.3要求：1、用单纯性发就解该线性规划问题； 2、写出该问题的对偶规划；
3、利用原问题的最优解和互补松弛性，直接秋池对偶问题的最优解； 4、利用原问题的最后一张单纯形表，直接秋池对偶问题最优解。
二、某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的
生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如下表所示。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总的运费最小。
8
产地 需地 A1 A2 A3 需求量
B1 2 1 3 3 B2 9 3 4 8 B3 10 4 2 4 B4 7 2 5 6 产量 9 5 7 三、已知下图表示7个城市间拟建一条连接各个城市的通讯线路，各边的权数表示两个城市之间的修建费用，求连接各城市通讯线路最修修建费用方案。
四、下图中vs表示仓库，vt表示商店，现要从仓库运10单位的物资到商店，应如何调运才能使运费最省（图中狐表示交通线，狐旁数字为（cij,bij）cij表示交通线上运输能力限制，bij表示单位运价。
9