7第七章习题及答案
- 格式:doc
- 大小:448.51 KB
- 文档页数:9
习题71.(1) 求最优生产计划.(2) 对目标函数系数c 1、c 4分别作灵敏度分析. (3) 对约束条件的常数项b 1、b 2分别作灵敏度分析.(4) 如果引进新产品F ,已知生产F1万件要用原材料甲、乙、丙分别为1、2、1公斤,问F 的利润多少时才有利于投产?如果每万件F 可得到利润12万元,问F 是否有利于投产? (5) 如果新增加煤耗不允许超过10吨的限制,而生产每万件A 、B 、C 、D 、E 产品分别需要煤3、2、1、2、1吨,问原最优方案是否需要改变?如果改变,应如何改变?解:设用54321,,,,x x x x x 分别表示计划生产产品A 、B 、C 、D 、E 的单位数量(万件)模型为:54321212010208max x x x x x f ++++=⎪⎪⎩⎪⎪⎨⎧≥≤++++≤+++≤+++0,,,,2122222423102..543215432154315321x x x x x x x x x x x x x x x x x x t s 标准形:54321212010208min x x x x x f f -----=-='⎪⎪⎩⎪⎪⎨⎧≥=+++++=++++=++++0,,,,,,,2122222423102..876543218543217543165321x x x x x x x x x x x x x x x x x x x x x x x x t s(1) 基B继续所以Tx )10,21,0,0,0(=,220=f即D 生产1/2万件,E 生产10万件,获得最大利润220万元. (2) 对c 1作灵敏度分析 记λλ+=+=811c c则186321101123220x x x x x x f λ-+++++-='(由最优基对应) 任以),,(B 若要原最优解不变,应满足条件:03≤-λ,3≤λ则1x 的价值系数1101≤≤c 时,最优解最优值不变. 对c 4作同样的灵敏度分析若要原最优解不变,应1200102023≤≤-⇒⎪⎪⎬⎫⎪⎪⎨⎧≤-≤+-≤+-λλλλ ,所以2104≤≤c ,最优值变为2220λ--.(3) 对b 1作灵敏度分析 设111110b b b b ∆+=∆+=最优基⎪⎪⎪⎭⎫ ⎝⎛==202312001),,(475a a a B ,则新的基解b B b B x B ∆+=--11所以⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛∆-∆+∆+=111212510b b b x B令0≥B x 得到2125-1≤∆≤b ,即2212151≤≤b 时,最优基不变。
对b 4作灵敏度分析可以得到25-2≥∆b ,即2431≥b 时,最优基不变。
(4) 设生产新产品F 9x 万件,每单位的利润为9c 万元9954321212010208min x c x x x x x f f ------=-='⎪⎪⎩⎪⎪⎨⎧≥=++++++=+++++=+++++0,,,,,,,,21222224223102..9876543218954321795431695321x x x x x x x x x x x x x x x x x x x x x x x x x x x x t s 原最优解Tx )0,25,0,10,21,0,0,0(=是该问题的一个可行解。
任取),,(475a a a B =为基,()()9100021201020811222211231111212101231100120021c C A B C B -------⎪⎪⎪⎭⎫⎝⎛⋅⎪⎪⎪⎭⎫ ⎝⎛-----=--=()1110010011239------c所以119>c 时,B 不是最优基,9x 可取非0值,从而安排生产F 有利。
129=c⎪⎪⎪⎭⎫⎝⎛-=⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛---==-2123112121123111919a B p 检验数为:1-C A B C B 变为Tx 3500032534000=即每万件F 可得利润12万元时,应生产D 为34万件,E 为325万件,F 为35万件。
(5) 新增约束条件1022354321≤++++x x x x x标准形54321212010208min x x x x x f f -----=-='⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=++++++=+++++=++++=++++0,,10223)1(2122222423102..919543218543217543165321x x x x x x x x x x x x x x x x x x x x x x x x t s ΛΛ 将(1)添入原最优基),,(475a a a B =对应的单纯形表),,,(9475*a a a a B =为对偶可行基对偶单纯形法所以最优解Tx 0140100000=,即改变为只生产E 为10万件。
3.求解下列线性规划问题的对偶问题:(2) 432132min x x x x f -+-= (3) 43214323min x x x x f +-+=⎪⎪⎩⎪⎪⎨⎧≥≥+≤--=++0,332432142..2131432421x x x x x x x x x x t s ⎪⎪⎩⎪⎪⎨⎧≤≥=----≥++≤++-无约束324143214324321,,0,0247325433432..x x x x x x x x x x x x x x x t s 解(1) 对偶问题:32132max y y y g ++=⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤-=-=+--≤+≤+0,0,3441331222..32121322131y y y y y y y y y y y t s 无约束(2) 对偶问题:321253max y y y g +-=⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≥-+-=-+=-+-≤+,,,0,04444373322232..32132132132131无约束y y y y y y y y y y y y y y t s3.判断下列说法是否正确,为什么?(1) 如果线性规划的原问题存在可行解,则其对偶问题也一定存在可行解. (2) 如果线性规划的对偶问题无可行解,则其原问题也一定无可行解.(3) 如果线性规划的原问题和对偶问题都具有可行解,则其原问题和对偶问题一定具有有限最优解.(4) 已知线性规划问题0,,max ≥≤=x b Ax cx f ,若x 是它的一个基解,y 是其对偶问题的基解,则恒有yb cx ≤.解:1. ×。
如原问题是无界解,则对偶问题无可行解。
P167 Th3。
2. ×。
(1)的逆否命题。
3. √。
P167 Thm44. ×。
原问题 对偶问题 若y x ,为可行解cx f =max yb g =min 则有b y x A y x c ≤≤⎩⎨⎧≥≤0..x b Ax t s ⎩⎨⎧≥≥0..y cyA t s 但若y x ,为基解,则不一定6.已知线性规划问题,23min 21x x f +=⎪⎪⎪⎨⎧≤-≤+≤+-3142342..212121x x x x x x t s(1) 写出它的对偶问题;(2) 应用对偶理论证明原问题和对偶问题都存在最优解.解:对偶问题3213144max y y y g ++=⎪⎩⎪⎨⎧≤≤-+≤++-0,,22233..321321321y y y y y y y y y t s(1) 原问题显然有可行解()Tx 21,0=对偶问题可行解()Ty 1,0,0=则由Thm4(P167)得 原问题和对偶问题都有最优解8.某文具用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。
该厂现有工人100人,每月白坯纸供应量为3万公斤。
已知工人的劳动生产率为:每人每月可生产原稿纸30捆,或生产日记本30打,或练习本30箱。
已知原材料消耗为:每捆原稿纸用白坯纸310公斤,每打日记本用白坯纸340公斤,每箱练习本用白坯纸380公斤。
又知每生产一捆原稿纸可获利润2元,生产一打日记本获利3元,生产一箱练习本获利1元,试确定:(1) 现有生产条件下获利最大的方案;(2) 如白坯纸的供应数量不变,当工人数不足时可招收临时工,临时工工资支出为每人每月40元,则该工厂要不要招收临时工,招收多少临时工合适?解:设每月生产原稿纸1x 捆,日记本2x 打,练习本3x 箱 标准形32132min x x x f ---='⎪⎩⎪⎨⎧≥=+++=+++0,,30000538034031030004..51321321x x x x x x x x x x t s ΛΛ 以()54a a B =为基的初始单纯形表变为对偶单纯形法所以最优解为(Tx 020001000=,最优值8000=f ,最优基)(12a a B =原问题的对偶问题的最优解()1,35=y 对偶问题2130000100min y y g +=⎪⎪⎩⎪⎪⎨⎧≥≥+≥+≥+0,,138030133403012310301..21212121y y y y y y y y t s 其最优解为()101,50=y ,则临时工的影子价格为50元/月>市场价40元/月 所以应招收临时工。
对b 1作灵敏度分析λ+=11b b⎪⎪⎭⎫ ⎝⎛-+=⎪⎪⎭⎫ ⎝⎛-+⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛--+⎪⎪⎭⎫ ⎝⎛==-λλλλλ10200040100010402000100001011010140200010001b B x B则要保持最优基不变,需要⎩⎨⎧≥-≥+01020000401000λλ,则20025≤≤-λ所以300751≤≤b 内最优基不变则招工的最大人数为200100300=-,10000)4050(20008000=-⨯+=f。