内容发布更新时间 : 2024/11/19 8:30:54星期一 下面是文章的全部内容请认真阅读。

1 用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。

minz?2x1?3x2 s.t.?4x1?6x2?6??4x1?2x2?4 ?x,x?0?12解：图解过程见下图 x2 2 4x1?2x2?4 1 0 1 2 x1 4x1?6x2?6*TT*有：X??(1.5,0)?(1??)(0.75,0.5) Z?3 该问题有无穷多最优解。 2 将下列线性规划问题化为标准形式，并列出初始单纯形表。 （10分） minz?3x1?x2?2x3 ?2x1?3x2?4x3?12?4x?x?2x?8?123 ?3x?x?3x?5123???x1?0,x2无约束,x3?0??x2???2x3? 解：原问题标准化为：maxz???3x1?x2??3x2???4x3??x4?12s.t.?2x1?3x2?4x?x??x???2x??x5?x6?8?1223???x2???3x3??x7?5?3x1?x2??,x2??,x3?,x4,x5,x6,x7?0?x1,x2s.t.其初始单纯形表为： Cj 0 0 0 Xj x4 x6 x7 cj-zj 12 8 5 -3 x1 2 4 3 -3 -1 x/2 3 1 -1 -1 1 x//2 -3 -1 1 1 -2 x/3 4 -2 -3 -2 0 x4 1 0 0 0 0 x5 0 -1 0 0 0 x6 0 1 0 0 0 x7 0 0 1 0 3 已知某线性规划问题用单纯形法迭代时得到中间某两步的单纯形表如表所示，试将表中空白处数字填上。 （10分） 3 5 4 0 0 0 5 0 x2 x5 8/3 14/3 x1 2/3 -4/3 x2 1 0 x3 0 5 x4 1/3 -2/3 x5 0 1 x6 0 0 （第 1 页）

0 x6 cj-zj ┇ x2 x3 x1 cj-zj 29/3 5/3 -1/3 0 0 1 0 0 0 1 0 0 0 4 4 ┇ 0 1 0 0 -2/3 -5/3 15/41 -6/41 -2/41 -45/41 0 0 8/41 5/41 -12/41 -24/41 1 0 -10/41 4/41 15/41 -11/41 5 4 3 50/41 62/41 89/41 4 已知线性规划问题：maxz?x1?x2 s.t.??x1?x2?x3?2???2x1?x2?x3?1 ?x,x,x?0?123试应用对偶理论证明上述线性规划问题最优解为无界。 （10分） 解：原问题的对偶问题为：minw?2y1?y2 s.t.????????y1?2y2?1y1?y2?1y1?y2?0y1,y2?0 由约束条件 ?y1?2y2?1 可知，其对偶问题无解；又因X?(0,0,0)T是原问题的可行解。由对偶定理可知原线性规划问题最优解为无界。 5 东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生产能力分别为120、160、100万t。公司同3个城市签订了下年度的供货合同：城市1-110万t，城市2-150万t，城市3-70万t，但城市3表示愿购买剩余的全部煤炭。另有城市4虽未签订合同，但也表示只要公司有剩余煤炭，愿全部收购。已知从各矿至4个城市的煤炭单位运价见表。将此问题归结为运输问题，列出相应的产销平衡表与单位运价表。 （10分） 单位运价表 单位：元/t 城市 1 2 3 4 煤矿 吉祥 8 平安 5 双福 6 解：该问题的运输问题产销平衡表与单位运价表为 城市 1 2 煤矿 吉祥 平安 双福 虚设矿山 8 5 6 M 7 2 4 M 7 2 4 3 5 1 3 M 3/ 5 1 3 0 5 1 3 4/ 2 3 5 0 2 3 5 产量 120 160 100 50 销量 110 150 70 50 50 6 已知下列五名运动员各种姿势的游泳成绩(各为50m，单位：s)如表所示。试问如何从中选拔一个4×50m混合泳的接力队，使预期的比赛成绩为最好。 （10分） 赵 钱 张 王 周 仰泳 37.7 32.9 38.8 37.0 35.4 蛙泳 43.4 33.1 42.2 34.7 41.8 33.3 28.5 38.9 30.4 33.6 蝶泳 29.2 26.4 29.6 28.5 31.1 自由泳 解：原问题用匈牙利算法求解为： （第 2 页）

32.938.837.035.4??4.805.94.12.5??10.309.11.68.7?33.142.234.741.8????28.538.930.433.6? 变换后：C1??4.8010.41.95.1? ???26.429.628.531.1?2.803.22.14.7???0000?000???00??3.204.32.50.9??2.303.42.50??8.707.507.1??7.806.606.2?????再变换为：C2??3.208.80.33.5? 再变换：C3??2.307.90.32.6? ????1.201.60.53.10.300.50.52.2??????00??01.60??02.500.90???2.003.12.50??00001??7.506.306.2??00010?????*再变换为：C4??2.007.60.32.6? ∴X??01000? Z*=127.8 ????000.20.52.210000???????02.801.20.3???00100??7 分别用破圈法和避圈法求下图的最小部分树。 （10分） ?37.7?43.4?C??33.3??29.2??05 2 3 2 2 2 1 3 3 5 5 2 3 2 2 2 1 3 3 5 5 2 3 2 v2 9 v1 8 v3 5 8 7 （第 3 页）

2 2 3 2 4 2 解：用破圈法求最小部分树为：W（Tmin）=18 注意有多重解 2 2 3 2 4 2 用避圈法求最小部分树为：W（Tmin）=18 2 1 2 3 3 5 2 2 3 2 v5 7 3 4 10 v6 4 2 8 用标号法求下图中v1至各点的最短路。 （10分） 1 2 v4 3 v7 解：标号过程如图所示： v2 （9,v1） 1 7 v5 （10,v2） 9 （0,v1） v1 8 （8,v1） v3 5 2 3 4 10 （13,v5） v7 8 （11,v2） v4 3 7 （14,v4） v6 由图可得：v1→v2 L=9 v1→v3 L=8 v1→v2→v4 L=11 v1→v2→v5 L=10 v1→v2→v4→v6 L=14 v1→v2→v5→v7 L=13 9 现有8名青工，要分配给3个采矿队，每队限最多分5名，每个采矿队增加不同青工后产量增加如下表，如何分配才能使产量增加最大？试建立其动态规划求解模型。 （10分） 增加青工数 采矿队 0 1 2 3 4 5 第一采矿队 0 16 25 30 32 33 0 10 14 16 17 17.5 第二采矿队 0 12 17 21 22 22.5 第三采矿队 解：根据题意，原问题用动态规划求解模型为： （1）按作业班组分为3阶段，K=（1，2，3，4），k=4为终了阶段； （2）xk：第k阶段初拥有待分配新工人数； 有：X1={8}，X2={8,7,6,5,4,3}，X3={5,4,3,2,1,0}，X={0}。 （3）uk：第k阶段分配给第k作业班组的新工人数； 有：U1={0,1,2,3,4,5}，U2={0,1,2,…,x2}( x2?5)；U2={ x2-5,…,5}( x2>5)，U3={x3}。 （4）状态转移方程：xk?1?xk?uk； （5）阶段指标：见表，如：d2(3,2)?14 ；d3(2,1)?12； （6）递推方程：fk(xk)?max?dk(xk,uk)?fk?1(xk?1)? uk?Uk（7）边界条件：f4(x4)?0。 10 某书店希望订购最新出版的图书出售。根据以往经验，新书的销售量可能为50、100、150或200本。假定每本书的订购价为4元，销售价为6元，剩书处理价为每本2元。分别依据悲观主义、乐观主义、等可能性、最小机会损失决策准则决定该书店应订购新书的数量。（10分） 解：（1）根据题意该问题的益损值表为： αi Sj 50 100 0 -100 -200 100 100 200 100 0 150 100 200 300 200 200 50 100 150 200 （2）悲观准则：maxmindijjj????400 ∴?*??100,200,300,400乐观准则：maxmax?d??max?ij100 200 300 400 ?max???100 ∴?*??1 100,0,?100,?2004 （第 4 页）

??dij??j?等可能准则：max?100,150,150,100??150 ∴?*??2或?3 ??max?n?????0100200300??1000100200?? 最小机会损失准则：损失矩阵为：D????2001000100???3002001000?????mi?dij则 minmax? ∴?*??2或?3 n30,020,020,030?0?200j （第 5 页）