运筹学7卷答案

课程名称:运筹学一（10分）解：则标准形式为：设对偶变量分别为y1，y2，y3，则对偶规划为：二（15分）解：首先变成最小化指派问题。B=(7-Cij)5×53分列减1分行减2分列减1分行减2分指派5分所以2分指派5分即甲—5，乙—4，丙—2，丁—1，戊—3，最大生产能力为7+6+5+5+5+5=282分三（20分）解：此问题可分为三个阶段，分别在地区A、B、C设销售点，k=1,2,3；决策变量uk：表示在地区k可设置的销售点数；状态变量sk：表示k阶段出可在第k到第c个地区设置销售点的个数；状态转移方程：sk+1=sk-uk表示：4分因为此问题为离散确定性多阶段决策，所以可用图表示。图形：8分000000000012121212101201012001032110103211017141722273147222020171717121212000171614016302504323244017141722273147222020171717121212000171614016302504323244此问题求总利润最大，相当于求状态s1到状态s4的最长路，采用逆序法标号标号：6分则最长路径为：4—2—1—0，最长路为47。即地区A设2个销售点，地区B设1个销售点，地区C设1个销售点。结果：2分四（15分）解：由最小元素法得初始运输方案如下表所示：（初始解5分，检验数4分）甲乙丙产量uiA48856056（-4）（4）B1624168212（0）4141C816247741661（16）销量7210241Vj4124因为σ14＜0，所以该方案不是最优方案。进行调整：（新方案3分，检验数2分）甲乙丙产量uiA488560（4）56（8）B1624168216（0）4141C81624778725（16）销量7210241Vj080因为，所以该方案是最优方案。总运费为2744。（1分）五（20分）解：（1）首先写出线性规划问题的标准形式（2分）Cj→23100θCBXBbx1x2x3x4x50x45111105/10x54-1[2]0014/2δj23100（2分）0x43[3/2]011-1/223x22-1/21001/2—δj5/2000-3/2（3分）2x12102/32/3-1/33x23011/31/31/3δj00-4/3-7/3-1/3（2分）此时，原问题得到最优解为X*=(2，3，0，0，0)T，maxZ＝13（1分）（2）当右边向量b变为(3,7)T时，（5分）代入最终单纯型表继续迭代：Cj→23100CBXBbx1x2x3x4x52x1-1/3102/32/3[-1/3[3x210/3011/31/31/3δj00-4/3-7/3-1/3（2分）0x51-30-2-213x2311110δj-10-2-30（2分）所以X*=（0，3，0，0，1）T，Z*=9（1分）六（20分）解：（1）用Dijkstra算法求顶点v1到顶点v7的最短路，标号见下表：由图知v1到v7的最短路长为12，路径为V1→V2→V5→V7（2分）VV24343101354278V1V31V4V5V6V7（4，4）5（7，4）（10，10）（3，3）（12，12）（8，8）（6分）（2）求最大流：增广链流量调整量V1→V4→V6→V74V1→V2→V3→V5→V73V1→V2→V5→V71（4分）V1→V3→V6→V73V1→V4→V3→V6→V71V1→V4→V3→V5→V71V1→V4→V3→V6→V5→V71所以最大流量为：4+3+1+3+1+1+1=14（1分）最大流量图为：VV2(4,4)(3,3)(4,3)(3,3)(10,7)(1,1)(3,3)(5,