LP问题的对偶问题习题集

习 题 三

3.1 试建立下述LP问题的对偶关系表，并写出其对偶问题： （1）max z=4x1+3x2+6x3

s.t.

?3x1?x2?x3?60?2x?2x?3x?40?123 ?2x?2x?x?623?1??x1?0,x2?0,x3?0?3x1?x2?x3?2?x?x?x??1?123 ?x?2x?x?123?1??x1?0,x2?0,x3?0?2x1?x2?4x3?2?x?x?2x?1?123 ?3x?x?x?3?123??x1?0,x2?0,x3?0?x1?2x2?4x3?10??2x1?5x2?3x3?15 ?x?0,x?0,x?023?1（2）min w=60x1+10x2+20x3

s.t.

（3）min w=5x1-3x2

s.t.

（4）max z=4x1+3x2+6x3

s.t.

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.

?2x1?3x2?5x3?2?3x?x?7x?3?123 ?x?4x?6x?523?1??x2?0,x3?0?3x1?4x2?4x3?7x4?21?2x?7x?3x?8x?18?1234 ??x1?2x2?5x3?3x4?4??x1?0,x2?0,x4?0(6) min w=2x1+3x2+6x3+x4

s.t.

3.3 试证明LP问题（P2）是（D2）的对偶，（P2）是（D2）的对偶。 3.4 试写出下述LP问题的对偶问题： （1）min w=CTX s.t.

?AX?b ??X?a(?0)(2) min z=

??cxi?1j?1mnijij

s.t.

?n??xij?ai,i?1,2,...m?j?1?m??xij?bj,j?1,2,...n ?i?1?xij?0???(3) max z=

?cxjj?1nj

s.t.

?n??aijxj?bi,i?1,2,...,r?j?1?n??aijxj?bi,i?r?1,r?2,...,m ?j?1?x?0,j?1,2,...,s(?n)?j??3.5 已知LP问题： min z= 5x1+6x2+3x3

s.t.

?5x1?5x2?3x3?50?x?x?x?20?123?7x1?6x2?9x3?30??x1?x2?x3?7 ?2x?4x?15x?1023?1?6x1?5x2?45??x2?10x3?20?x?0,x?0,x?023?1试通过求解其对偶问题来确定该LP问题的最优解。 3.6 已知LP问题： max z= x1+2x2

?x1?x2?2?s.t.??x1?x2?1 ?x?0,x?02?1（1）试证明它与其对偶问题均无可行解。

（2）试构造一个LP问题，使其本身及其对偶问题均无可行解。 3.7 已知（Ⅰ）（Ⅱ）两个LP问题： （Ⅰ）max z1=

?cxjj?1nj

s.t.

?n??aijxj?bi,i?1,2,...,m ?j?1?x?0,j?1,2,...,n?j（Ⅱ）max z2=

?cxjj?1nj

?n??aijxj?bi?ki,i?1,2,...,m ?j?1?x?0,j?1,2,...,n?j其中aij，bi ，ki均为已知常数。

设z1，z2分别为（Ⅰ），（Ⅱ）的最优值，yi（i=1,2,…,m）为（Ⅰ）的对偶问题的最优解，求证：

???z?z??kiyi

?2?1i?1m3.8 不用单纯形法，利用对偶性质和其它简便方法求解下述LP问题： (1) max w=4x1+3x2+6x3

s.t.

?3x1?x2?3x3?30??2x1?2x2?3x3?40 ?x?0,x?0,x?023?1(2) max z=x1-x2+x3

?x3?4?x1? ?x1?x2?2x3?3?x?0,x?0,x?023?13.9 已知LP问题：max z= 6x1+8x2

?5x1?2x2?20?s.t.?x1?2x2?10 ?x?0,x?02?1(1)写出它的对偶问题。

(2)用图解发求解原始、对偶问题。识别两个问题的所有极点解。

(3)用单纯形法求解原始问题。在每个单纯形表中，识别此问题的基本可行解及对偶问题的互补基本解。指出它们相应于图解法中哪个极点。

(4)按表3-8的格式，列出该问题的全部互补基本解。

(5)用对偶单纯形法求解对偶问题，并将结果与（3）中结果进行对比。 (6)该问题是否满足互补松弛性？为什么？

3.10用对偶单纯形法求解下述LP问题: (1)min z= x1+x2

s.t.

?x1?2x2?4?x?5?1 ??3x1?x2?6??x1?0,x2?0?x1?x2?x3?6?x?x3?4?1 ?x2?x3?3???x1?0,x2?0,x3?0(2) min z= 3x1+2x2+x3

s.t.

(3) 2.4(4)题

3.11 某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示：

产品 单耗（台时/件） 设备有效台时 设备 甲 乙 丙 A B 产值（千元/件） 1 2 1 2 1 2 3 2 1 400 500 （1） 如何充分发挥设备能力，使产品总产值最大？

（2） 若为了提高产量，以每台时350元租金租用外厂A设备，问是否合算？ 3.12 用对偶单纯形法求解下述LP问题: （1）max z= 3x1-2x2-x3

s.t.

?x1?x2?x3?4?x2?2x3?8? ?x?x?223???x1,x2,x3?0?x1?x2?x3?6??2x?x3?6?1 ?2x?x?023???x1,x2,x3?0(2) max z= 2x1-x2+2x3

s.t.

(3) max z= 5x1-8x2-x3+4x4-11x5

?2x1?9x2?7x3?2x4?11x5?5?x?6x?6x?2x?9x?3?12345s.t.? ?x1?7x2?8x3?3x4?12x5?4??x1,x2,x3,x4,x5?03.13 用交替单纯形法求解3.12题。

本文来源：https://www.bwwdw.com/article/6c2t.html