。（4分）（6）求解上述线性规划问题的对偶问题的最优解。（6分）解：（1）首先，将问题化为标准型（4分）。加松弛变量x3，x4，得
其次，列出初始单纯形表，计算最优值（4分）。
由单纯形表一得最优解为x132Tz352（2分）（2）对偶问题为4分：mi
w＝9y1＋8y2st3y1＋5y2≥104y1＋2y2≥5y1y2≥0（3）用互补松弛地定理求出对偶问题的解为6分其中步骤4分，结果2分：先化为标准型，则有mi
w＝9y1＋8y2
fst3y1＋5y2y3104y1＋2y2y45y1y2，y3，y4≥0根据互补松弛定理有，x1y30x2y40x10x20则有：y3y40，带入对偶问题标准型则有3y1＋5y2104y1＋2y25则有：y1514y22514mi
W352四、（20分）在下面的运输问题中总需要量超过总供应量。假定对销地B1、B2和B3未满足需要量的单位罚款成本是3元吨、2元吨和1元吨。求最小运费和最优的运输方案。
运价（元吨）A1A2A3销量（吨）
B156375
B214220
B376550
产量（吨）108015
解答：虚设供应地A4，虚设地运价为惩罚成本，则有最优方案为3B10A13A20A32A4销量5（2）1B2【10】1【10】423B37（4）产量10801540
【60】6【15】33275
【10】62
（1）52320
【40】150
则有最优运输方案为X1210X2160X2210X2310X3115X4340最小运输费用为555。（步骤为15分，结果为5分）五、（10分）某工厂生产Ⅰ，Ⅱ两种产品。已知有关数据见下表。Ⅰ原材料kg设备hr利润元件218Ⅱ1210
拥有量
1110
公司在决策时需考虑以下问题：p1：根据市场信息，产品Ⅰ销售有下降趋势，故产品Ⅰ产量不大于产品Ⅱ产量
fp2：尽可能利用设备，但不能加班p3：应尽可能达到并超过利润56元为确定生产计划，试建立该问题的目标规划模型不需要求解
解：mi
Z＝p1d1＋＋p2（d2d2）p3d3（3分）2x1x2≤11（1分）－x1x2d1d10（1分）x12x2d2d210（1分）8x110x2d3d356（1分）x1x2didi≥0i123（1分）
有正负偏差变量、优先因子和mi
z即可得（2分）六、（10分）解：能联通12个部门的最短电话线路长实际为图形的最小支撑数的权值。
3①
4②21⑤4
⑨⑩
③5
④
1
⑦
⑥6
⑧3
⑾
⑿
2
4
最小支撑树为，权值为35（步骤为5分，结果为5分）
fr