3对偶原理习题

习 题 三 3 1 试建立下述 LP 问题的对偶关系表 并写出其对偶问题 1 max z 4x1 3x2 6x3 s t 123 123 123 123 360 22340 226 0 0 0 xxx xxx xxx xxx 2 min w 60 x1 10 x2 20 x3 s t 123 123 123 123 32 1 21 0 0 0 xxx xxx xxx xxx 3 min w 5x1 3x2 s t 123 123 123 123 242 21 33 0 0 0 xxx xxx xxx xxx 4 max z 4x1 3x2 6x3 s t 123 123 123 2410 25315 0 0 0 xxx xxx xxx 3 2 试写出下述 LP 问题的对偶问题 1 1 1 1 题 2 1 5 题 3 2 4 5 题 4 2 4 7 题 5 min w 2x1 2x2 4x3 s t 123 123 123 23 2352 373 465 0 0 xxx xxx xxx xx 6 min w 2x1 3x2 6x3 x4 s t 1234 1234 1234 124 344721 273818 2534 0 0 0 xxxx xxxx xxxx xxx 3 3 试证明 LP 问题 P2 是 D2 的对偶 P2 是 D2 的对偶 3 4 试写出下述 LP 问题的对偶问题 1 min w CTX s t 0 AXb Xa 2 min z 11 mn ijij ij c x s t 1 1 1 2 1 2 0 n iji j m ijj i ij xa im xbjn x 3 max z 1 n jj j c x s t 1 1 1 2 1 2 0 1 2 n ijji j n ijji j j a xb ir a xb irrm xjsn 3 5 已知 LP 问题 min z 5x1 6x2 3x3 s t 123 123 123 123 123 12 23 123 55350 20 76930 7 241510 6545 1020 0 0 0 xxx xxx xxx xxx xxx xx xx xxx 试通过求解其对偶问题来确定该 LP 问题的最优解 3 6 已知 LP 问题 max z x1 2x2 s t 12 12 12 2 1 0 0 xx xx xx 1 试证明它与其对偶问题均无可行解 2 试构造一个 LP 问题 使其本身及其对偶问题均无可行解 3 7 已知 两个 LP 问题 max z1 1 n jj j c x s t 1 1 2 0 1 2 n ijji j j a xb im xjn max z2 1 n jj j c x 1 1 2 0 1 2 n ijjii j j a xbk im xjn 其中 均为已知常数 ij a i b i k 设 分别为 的最优值 i 1 2 m 为 的对偶问题的最优解 求证 1 z 2 z i y 21 1 m ii i zzk y 3 8 不用单纯形法 利用对偶性质和其它简便方法求解下述 LP 问题 1 max w 4x1 3x2 6x3 s t 123 123 123 3330 22340 0 0 0 xxx xxx xxx 2 max z x1 x2 x3 13 123 123 4 23 0 0 0 xx xxx xxx 3 9 已知 LP 问题 max z 6x1 8x2 s t 12 12 12 5220 210 0 0 xx xx xx 1 写出它的对偶问题 2 用图解发求解原始 对偶问题 识别两个问题的所有极点解 3 用单纯形法求解原始问题 在每个单纯形表中 识别此问题的基本可行解及对偶问题的互补基本解 指出它们相应于图解法中哪个极点 4 按表 3 8 的格式 列出该问题的全部互补基本解 5 用对偶单纯形法求解对偶问题 并将结果与 3 中结果进行对比 6 该问题是否满足互补松弛性 为什么 3 10 用对偶单纯形法求解下述 LP 问题 1 min z x1 x2 s t 12 1 12 12 24 5 36 0 0 xx x xx xx 2 min z 3x1 2x2 x3 s t 123 13 23 123 6 4 3 0 0 0 xxx xx xx xxx 3 2 4 4 题 3 11 某厂拟生产甲 乙 丙三种产品 都需要在 A B 两种设备上加工 有关数据如下表所示 单耗 台时 件 产品 设备 甲 乙 丙 设备有效台时 A B 1 2 1 2 1 2 400 500 产值 千元 件 3 2 1 1 如何充分发挥设备能力 使产品总产值最大 2 若为了提高产量 以每台时 350 元租金租用外厂 A 设备 问是否合算 3 12 用对偶单纯形法求解下述 LP 问题 1 max z 3x1 2x2 x3 s t 123 23 23 123 4 28 2 0 xxx xx xx x x x 2 max z 2x1 x2 2x3 s t 123 13 23 123 6 26 20 0 xxx xx xx x x x 3 max z 5x1 8x2