一、下表为某线性规划问题计算过程中的一个单纯形表，该线性规划问题的

目标函数为max z=28x1+x2+2x3 ，其中x4,x5,x6,为松驰变量， 解的目标函数值z=42。

（1）添满下表中的所有空格； 基 x1 x5 x3 Zj σj CB x1 1 0 0 x2 0 5/2 1 -1 x3 0 0 1 0 x4 0 6 3 0 x5 1/3 -14/3 0 x6 1 5 Z= 42 b

（2）请写出该线性规划问题的最优解，最优目标函数值，并说明解的类型。

二、已知运输问题的供需关系表与单位运价

(1) 以最小元素法确定初始基本可行解,并以闭回路法判别； 销地 产地 A1 A2 A3 销量

3 B1 3 1 7 6 B2 11 9 4 5 B3 3 2 10 6 B4 10 8 5 产量 7 4 9 (2) 求该运输问题的最优解,并以闭回路法判别； 销地 产地 A1 A2 A3 销量 3 B1 3 1 7 6 B2 11 9 4 5 B3 3 2 10 6 B4 10 8 5 产量 7 4 9

(3) 试写出上述运输问题的线性规划模型。

三．某电器公司经营的唱机和录音机均有车间A、B流水作业组装，数据见下表。

工时消耗 项目品种 销售利润 （台/时） （元/台） A B 唱机 2 1 250 录音机 1 3 150 总工时/月 180 200 要求按以下目标制订月生产计划： （1）每月利润不低于10000元； （2）每月销售唱机不少于80台； （3）不使A车间和B车间停工；

（4）B车间加班时间限制在20小时内； （5）每月销售录音机控制在100台； 试建立该问题的目标规划模型（无须计算）。

四、用标号算法,求 V1 至 V8 的最大流。

(提示：无需图上标注，但要写出每次找到的可增广链及可调整值)

V2

(9,6) V1

(8,4) V3 (8,5)

V4

(4,1)

(4,4) (3,3) V6 (11,3) (6,0) (9,5)

V7

V5

(10,2)

(4,2)

(5,4) (4,1)

(15,9)

V8

五、用求 V1 至 V6 的最短距离与最短路径。

V2 5

V1

4 V3

12

V5

18 10 V4

9 3

4

15

V6

六、某公司需要选择多个销售点，有9个场地可以选择，他们的年租金及所处区域位置见表。 销售点 1 2 3 4 5 6 7 8 9 年租金 6.2 7.0 8.8 8.6 5.5 6.3 9.0 10.2 11.8 （万元） 位置 城东 城东 城东 城西 城西 城西 城北 城北 城北 销售点满足以下条件：

(1)城北只能有一个销售点； (2)城西至少有一个销售点；

(3)如果选择了1号和6号销售点，则不得选择3号销售点； (4)2号和8号销售点至少有一个不选。 (5)每个城区至少有一个销售点。

问应当选择哪几个销售点，才能使年租金最低。（不计算）

七、试用用匈牙利法求解下列指派问题

A B C D

甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17