习 题 11 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。
⎪⎩⎪⎨⎧≥≥+≥++=0x x 42x 4x 66x 4x 3x 2x minz )a (21212121， ⎪⎩⎪⎨⎧≥≥+≤++=0x ,x 124x 3x 2x 2x 2x 3x maxz )b (21212121⎪⎩⎪⎨⎧≤≤≤≤≤++=8x 310x 512010x 6x x x maxz )c (212121 ⎪⎩⎪⎨⎧≥≤+-≥-+=0x ,x 23x 2x 2x 2x 6x 5x maxz )d (21212121 答案： (a)唯一解3*,)5.0,75.0(*==z X T); (b)无可行解;(c)唯一解16*,)6,10(*==z X T); (d)无界解）2 用单纯形法求解下列线性规划问题。
⎪⎩⎪⎨⎧≥≤+≤++=0x ,x 82x 5x 94x 3x 5x 10x maxz )a (21212121 ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=0x ,x 5x x 242x 6x 155x x 2x maxz )b (212121221 答案： (a)唯一解5.17*,)5.1,1(*==z X T )，对偶问题5.17*,)786.1,357.0(*==w Y T ; (b)唯一解5.8*,)5.1,5.3(*==z X T ），5.8*,)5.0,25.0,0(*==w Y T3 用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。
⎪⎪⎩⎪⎪⎨⎧≥≥-≥+-≥+++-=0x x x 0x 2x 2x 2x 6x x x 2x x 2x maxz )a (3,2,13231321321 ⎪⎩⎪⎨⎧≥≥+≥++++=0x ,x ,x 62x 3x 82x 4x xx 3x 2x minz )b (32121321321 答案：(a)无界解；(b)唯一解8*,)0,8.1,8.0(*==z X T)，对偶问题8*,)0,1(*==w Y T4已知线性规划问题的初始单纯形表（如表1-54所示）和用单纯形法迭代后得到的表（如表1-55所示）如下，试求括弧中未知数a ～l 的值。
表1-54 初始单纯形表表1-55基变量x 1列向量⎪⎪⎭⎫⎝⎛=0'1p ，所以g=1,h=0（2）初始表 ,,j p b 某步表j p B b B11,--有已知表查出⎪⎪⎭⎫⎝⎛=-12/102/11B,341612/102/141=⇒⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⇒⎪⎪⎭⎫ ⎝⎛=-f f f b B201112/102/10111=⇒⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛-⎪⎪⎭⎫ ⎝⎛⇒⎪⎪⎭⎫ ⎝⎛=-b b p B5,42312/102/1221==⇒⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⇒⎪⎪⎭⎫ ⎝⎛=-i c i c i p B2,21112/102/11131=-=⇒⎪⎪⎭⎫ ⎝⎛-=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⇒⎪⎪⎭⎫ ⎝⎛-=-e d e d p B （3）初始表主元行×（-主元检验数/主元）加到检验数行得下一步表的检验数行。
表1-54第一行系数×（-a/b ）+表1-54检验数行=表1-54检验数行即：0,21,2,712=-==+-=--l a k j a a故：0,23,5,3=-===l k j a 。
5某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A 、B 两道工序加工。
设A 工序可分别在设备A 1或A 2上完成，有B 1、B 2、B 3三种设备可用于完成B 工序。
已知产品Ⅰ可在A 、B 任何一种设备上加工；产品Ⅱ可在任何规格的A 设备上加工，但完成B 工序时，只能在B 1设备上加工；产品Ⅲ只能在A 2与B 2设备上加工。
加工单位产品所需工序时间及其他各项数据见下表1-56，试安排最优生产计划，使该厂获利最大。
6 一家糖果商店出售三种不同品牌的果仁糖，每个品牌含有不同比例的杏仁、核桃仁、胡桃仁。
为了维护商店的质量信誉，每个品牌中所含有的果仁的最大、最小比例是必须满足的，如下表1-57所示：表1-58列出了商店从供应商每周能够得到的每类果仁的最大数量和每磅的价格：商店希望确定每周购进杏仁、核桃仁、腰果仁、胡桃仁的数量，使周利润最大。
建立数学模型，帮助该商店管理人员解决果仁混合的问题。
7 写出下列线性规划问题的对偶问题。
⎪⎪⎩⎪⎪⎨⎧≥=+≤++≥++++=无约束321321321321321x 0,x ,x 53x 4x x 33x x 2x24x 3x x 4x 2x 2x minz )a ( ⎪⎪⎪⎩⎪⎪⎪⎨⎧+=<=≥+==<=≤=∑∑∑===)n ,,1n j (x )n n ,,1j (0x )m ,,1m i (b x a )m m ,,1i (b x a x c maxz )b (1j1j 1i n 1j j ij 1i n 1j j ij n1j jj 无约束 答案： （a ）⎪⎪⎩⎪⎪⎨⎧≥=++≤++≤++++=ω无约束321321321321321x 0,x ,x 43x 3y 4y 24y y 3y2y 2y y 5y 3y 2y max （b ）⎪⎪⎪⎩⎪⎪⎪⎨⎧+=<=≥+==+<=≥++=ω∑∑∑∑∑∑=+==+=+==)m ,,1i (v )n ,,1i (0u )n ,...,1n j (c v a u a )n n ,,1j (c v a u a v b u b min 1i1i 1j m 1i m1m i iij i ij 1j m 1i m 1m i i ij i ij m1m i ii m 1i i i 111111m m 无约束8 已知线性规划问题：⎪⎩⎪⎨⎧≥≤-+-≤++-+=0x x x 1x x 2x 2x x x x x maxz 32132132121，，试应用对偶理论证明上述线性规划问题最优解为无界。
答案：显然T(0,0,0)X =为该问题的可行解， 其对偶问题为：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥-≥+≥--+=0y y 0y y 1y y 12y y y y 2min 2121212121，ω显然第一个约束与变量非负要求矛盾，故对偶问题无可行解。
由无界性该问题最优解为无界。
9 已知线性规划问题：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤+≤+++++=)4,,1j (0x )4(9x x x )3(6x x x )2(6x 2x )1(8x 3x x x x 4x 2x maxz j 321432214214321 要求：（1）写出其对偶问题；（2）已知原问题最优解为X *=(2,2,4,0)T，试根据对偶理论求出对偶问题最优解。
答案： 对偶问题⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≥+≥++≥+++≥+++++=)4,,1j (0y (4)1y y (3)1y y (2)4y y y 3y (1)2y 2y y 9y y 66y 8y min j 314343214214321 ω 设对偶问题的最优解为),,,(*4*3*2*1*y y y y Y=将X *=(2,2,4,0)T代入原问题，约束（4）为严格不等式（即x *S1，x *S2，x *S3）0），由互补松弛性，y *4=0。
又因为x*1=2,x *2 =2,x *3 =4都大于0，由互补松弛性，对偶问题对应（1）--（3）约束为等式，（即y *S1= y *S2 =y *S3=0）故有⎪⎪⎩⎪⎪⎨⎧=+=++=+(3)1y (2)4y y 3y (1)22y y ****1*2*3321， 解得对偶问题的最优解为)0,1,5/3,5/4(*y Y =。
10 已知线性规划问题：⎪⎩⎪⎨⎧≥≤+-≤+++-=0x ,x ,x 42x x 6x x x x x 2x maxz 32121321321先用单纯形法求出最优解，再分析在下列条件单独变化的情况最优解的变化。
（1）目标函数变为321x 3x 2x m ax z ++=； （2）约束右端项由⎥⎦⎤⎢⎣⎡46变为⎥⎦⎤⎢⎣⎡43；（3）增添一个新的约束条件：22x x 31≥+-。
答案：该问题的最优解TX )10,0,0,0,6(*=，最优值1262*=⨯=z 对偶问题的最优解)2,1,3,0,2(*=Y ，最优值1226*=⨯=ω （1）目标函数中非基变量2x 的系数2c 由-1变为3 重新计算2x 的检验数2σ0131)02(3'22>=⎪⎪⎭⎫⎝⎛-=-=jB pC c σ最优解发生变化，将2x 的检验数12=σ，系数3c 2=代入最终表，用单纯形法求解之，见下表该问题的最优解TX )0,0,0,3/10,3/8(*=，最优值3463103382*=⨯+⨯=z 对偶问题的最优解)3/4,0,0,3/1,3/7(*=Y ,最优值346314376*=⨯+⨯=ω（2）037324331313132'1>⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎪⎭⎫ ⎝⎛-=-b B ，故最优基不变最优解为TX )0,0,0,3/7,3/2(*=，最优值325373322*=⨯+⨯=z （3）最优解TX )10,0,0,0,6(*=不满足新加的约束 将约束化为等式，选松弛变量作为基变量得-2x 2x x 631=+-将其添加到最终表得过渡表，然后将第一行乘-1加到第三行将基变量x 1的系数列向新的最优解T X )3/22,0,3/8,0,3/10(*=，最优值328332*=+⨯=z11 用分支定界法求解下列整数规划问题：(1) ⎪⎩⎪⎨⎧≥≤+≤++=，且为整数，0x x 369x 4x 357x 5x 3x 2x maxz 21212121 (2) ⎪⎩⎪⎨⎧≥≤+≤++=且为整数,0x ,x 305x 6x 165x 2x x x maxz 2121212112 用隐枚举法求解下列0-1规划问题：⎪⎪⎩⎪⎪⎨⎧==≥-+-≤++≤+++++--+=)5,,1j (10x 35x 3x 6x 11x 83x 4x -3x 7x 4x 2x x x x 3x 2x 5x 2x 3x maxz j 542154315432154321 或 x j =0 或1，j = 1，2，3，4，513 某航运公司承担六个港口城市A 、B 、C 、D 、E 、F 的四条固定航线的物资运输任务已知各条航线的起点、终点城市及每天航班数见表1-59。
假定各条航线使用相同型号的船只，又各城市之间的航程天数见表1-60。
又知每条船只每次装卸货物的时间各需1天，则该航运公司至少应配备多少条船,才能满足所有航线的运货需求? 建立模型并用软件求解。
