运筹学第2章习题

第2章对偶理论与灵敏度分析习题详解习题 2.1用改进单纯形法求解以下线性规划问题。 1 Max z6 玉-2*23 *3 2 jq -易 3 Xj 2 xx 4x3 4 万，x2, x3 0 2 min z2x1 x2 3 jq 易3 4 3 x2 6 万 2 x2 3 xi,x20 2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的计算表见表 2-1所示，试将空白处数字填上。 表2-1 Cj 3 5 4 0 0 0 Cb X- b 改 X 工5 5 8/3 2/3 1 0 1/3 0 0 0 14/3 -4/3 0 5 -2/3 1 0 0 工6 20/3 5/3 0 4 -2/3 0 1 c广Zj -1/3 0 4 -5/3 0 0 ..・・ X2 15/41 8/41 -10/41 -6/41 5/41 4/41 -2/41 -12/41 15/41 cj- zj 2.3写出下列线性规划问题的对偶问题。 1 min z 2 xr 2 x2 4 x3 2 m3 x25 x3 2 3 x1 x27 x3 3 x,4 x26 x3 5 万,x2, x3 0 2 max z 2x2 34 x4 -jq x2 - x3 -3 x4 5 6 M 7 x2 3 x3 -5 x4 8 12 M -9 x2 -9 x3 9 x4 20 x1x2 0;x3 0;x4无约束 3 min zEEc7 i-l J1 ri ji xijbj jl,...,n il 乂寸0 4 Max z Ve x. j j ji n 。内 々，il,....，YY\m ji bt, im（ 1,niy 2,...,m ji Xj 20,当 j l,77 弓无约束，当j〃l l,..., 2.4判断下列说法是否正确，并说明为什么. （1）如线性规划问题的原问题存在可行解，则其对偶问题也一定存在可行解。 （2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。 C3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题 一定有有限最优解。 2.5设线性规划问题（1）是 Max V c.x. ji 2获产场,il, 2..., m J1 Xj 0, j l,2....,n （2,是其对偶问题的最优解。 又设线性规划问题（2）是 n Max Z2 Z cjxj ji n E a..x. b； k. , iL 2..., m u J 11 ji Xj 0,y 1,2....,n 其中.是给定的常数，求证 m max z2 max zd zi 2.6已知线性规划问题 Max z cxxx c2x2 c3x3 Xj Q,j l,...,5 用单纯形法求解，得到最终单纯形表如表所示，要求 1 求 Qi，如，。13，％，。22，。23，K的值; 2求ct,c2,c3 的值。 表2-2 Xb b X] x3 X5 3/2 1 0 1 1/2 -1/2 2 1/2 1 0 -1 2 c. z. JJ -3 0 0 0 -4 2.7已知线性规划问题 Max z2 xr x2 5 x3 6 x4 s.t. 2 x3 x4 8 2 x{ 2 x2 x3 2x4 - 12 Xj 0, jl,...4 对偶变量乂，力，其对偶问题的最优解是24, 乂1,试应用对偶问题 的性质，求原问题的最优解。 2.8试用对偶单纯形法求解下列线性规划问题。 1 min z x2 2尤1 工2 24 7 x2 7 Xj, x2 0 2 min z3xt 2x2 3 4x4 2X] 4x2 5x3 x4 0 3,- x2 7x3-2x4 2 5 X] 2x2 x3 104 15 改,x2,天，x4 0 2.9现有线性规划问题 max z- 5 改 5 x213 x3 -Xj x2 3 x3 - 20 12 X] 4x210 x3 -90 , x2,＞0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什 么变化 1 约束条件1的右端常数由20变为30 2 约束条件2的右端常数由90变为70 3 目标函数中易的系数变为8 _ 「一1 4 西的系数向量变为 5 增加一个约束条件2羽3工25毛＜50 6 将约束条件2变为10也510退＜10 2.10已知某工厂计划生产1,11,111三种产品，各产品在ABC设备上加工，数据如 下表2-3所示， 表2-3 设备代号 I II III 每月设备 有效台时 A 8 2 10 300 B 10 5 8 400 C 2 13 10 420 单位产品利润 /千元 3 2 2.9 1 如何充分发挥设备能力，使生产盈利最大 2 如果为了增加产量，可借用其他工厂的设备B,每月可借用60台时, 租金为1.8万元，问借用设备是否合算 3 若另有两种新产品IV、V,其中IV为10台时，单位产品利润2.1千 元；新产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利 1.87千元。如A、B、C设备台时不增加，分别回答这两种新产品投产在经济上 是否戈|］算 4 对产品工艺重新进行设计，改进结构，改进后生产每件产品I,需要 设备A为9台时，设备B为12台时，设备C为4台时*,单位产品利润4.5千兀, 问这对原计划有何影响 2.11分析下列参数规划中当t变化时最优解的变化情况。 1 Max zz 3-6t、］2-2t x25-5t x3 t0 s.t. 2 x2 x3 -430 3 而 2 w - 460 尤i 4 x2 - 420 M，x3 -0 2 Max 72。工］12。x210-tx3 t0 s.t. x, x2 x3 -20 2 2 x2 x3 -30