运筹学作业题

1、1已知某线性规划问题的初始单纯形表和用单纯形表法迭代后得到的表1，试求括号中未知数 a-l 的数值。项目x1x2x3x4x5x46(b)(c)(d)10x51-13( e)01cj-z j(a)-1200x1 (f)(g)2-11/20x5 4(h)(i)11/21cj-z j0-7(j)(k)(l)解：（1）X5是基变量，检验数 l=0（2）x1是基变量，则， g=1， h=0（3）x4行乘以 1/2 得到迭代后的 x1行 所以， f=6*1/2=3, b=2 ， c=4， d=-2（4）x4行乘以 1/2 加到 x5 行上，得到迭代后的 x5行 所以， c*1/2+3=i ，i=5 ，d*

2、1/2+e=1, e=2（5）迭代前为初始单纯形表，价值系数为初始表检验数 所以， x2 价值系数为 -1， x3 价值系数为 2，x4 价值系数为 0 则， -7=-1- （ 2a-0*i ），所以 a=3 j=2- （ -a ）=5； k=0- （1/2*a+1/2*0 ）=-3/2 即， a=3， b=2， c=4， d=-2 ，e=2, f=3, g=1, h=0, i=5, j=5, k= -3/2, l=02. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯 形表如下表 2 所示。求表中括号中未知数的值cj322000CB基bx1x2x3x4x5x60x4（b）

3、1111000x515（a）120100x6202（c）1001cj-z j3220000x45/400(d)（l）-1/4-1/43x125/410(e)03/4（i）2x25/201(f)0（h）1/2cj-z j0（k）（g）0-5/4（j）解：初始单纯形表中的单位矩阵，在最终单纯形表中变化为B-1l1414l1414b5/4(1) B 1 0 34ib B 1b 0 34 i 15 25/ 40h120h12205/2在最终表中， x4 是基变量，所以 l =1 所以， b=10， i=-1/4 ， h=-1/21141410(2) p1B 1p103414a1则 a=2012 12

4、2 01 143) p2 B 1p2 0 340 1214 114 1124 c00 则 c=31以此类推其它未知数取值。即， a=2 b=10 c=3 d=1/4 e=5/4 -1/4 k=0 l=1f=-1/2 g=-3/4 h= -1/2 i= -1/4 j=3. 给出线性规划问题max z2x1 4x2x3x4x13x2x482x1x26st.x2x3x46x1x2x39xj0(j1,.,4)要求：（1）写出其对偶问题；（2）已知原问题最优解为 X*=（2,2,4,0） ，试根据对偶理论直接写出对偶问题的最优解。解：（1）其对偶问题为min w8y1 6y2 6y39y4y12y2y4

5、23y1y2y3y44st.y3y41y1y31yj 0(j 1,.,4)（2）根据对偶理论知， x12,x22,x34 均绝对大于零，所以其变量对应的对偶问题的约束条件取严格等式。原问题与对偶问题同时取得最优解，且目标函数值相等。则可得：min w 8y1 6y2 6y3 9y4y12y2y42y1453y1y2y3y44 解得，y235st.y3y41y318y16y26y39y42x1 4x2 x3 x4y404. 某厂生产A/B/C 三种产品，其所需劳动力、材料等相关数据见下表。要求：（1）确定获利最大的产品生产计划； （2）产品 A 的利润在什么范围内变动时，上述最优计 划不变；（3

6、）如果设计一种新产品 D，单件劳动力消耗为 8单位，材料消耗为 2 单位，每件可获利 3 元，问该产品是否值得生产 （ 4）如果劳动力数量不增， 材料不足时可从市场购买， 没单位元。问该厂要不要购进原材料扩大生产，以购进多少为宜。产品ABC可用量（单位）消耗定额资源劳动力63545材料34530产品利润（元 / 件）314解：（1）设 A/B/C 三种产品的产量分别为 x1，x2， x3，写出最优生产计划数学模型。maxz 3x1 x2 4x36x1 3x2 5x3 45st. 6x1 3x2 5x3 45xj 0,j 1,2,3标准化后，列单纯形表计算。cj31400CB基bx1x2x3x4

7、x50x445635100x53034（5）01cj - z j314000x415(3)-101-14x363/54/5101/5cj - z j3/5-11/500-4/53x151-1/301/3-1/34x33011-1/52/5cj - z j0-20-1/5-3/5所有检验数均小于等于零，所以当前解为最优解。x1 5 x2 0 x3 3（2）假设产品 A 的利润变动量为时，上述最优计划不变。 则体现在最终单纯形表上为：cj3+1400CB基bx1x2x3x4x53+x151-1/301/3-1/34x33011-1/52/5cj - z j0/3-20- /3-1/5/3-3/5抱

8、持最优计划不变，则需要当前解仍为最优解。即检验数行均小于等于零。2031390 解得 3355530351224所以355即在上述范围内最优计划不变。3）设计新产品，相当于增加一列111p6B p6p，则有2456 c6 3 4214555b 发生了变化，设变化情况为因为检验数大于零，所以此产品值得生产。110530 b，则 bb B 1 b 5 3313232555因为决策为扩大生产，即保持生产品种（基变量）不变，所以得到：4）劳动力数量不增，材料不足可购买，相当于资源拥有量533250得到 0 150因为利润3z 3x1 x2 4x53 ，可知 z 值随着增长而增长。当取最大值z 值同时取的最大值。因此以购进15 单位为宜。15 时，5、 三个城市每年需分别供应电力 320，250，350 个单位，由 A、B 两个电站提供，它们 的最大可供电量分别为 400，450 个单位，单位费用如表所示。由于需求大于供给，决定城 市 1 的供应量可减少 030 个单位，城市 2 的供应量不变，城市 3 的供应量不能少于 270 单 位。试求总费用最低的分配方案。 （将可供电量用完。 ）电站城市城