3对偶原理习题

更新时间:2023-11-25 23:08:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

习 题 三

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/jokt.html

Top