运筹学习题(3)

CZ?Y*b

x4,x5为松弛变量，问题的约束

4. 已知下表为求解某线性规划问题的最终单纯形表，表中

条件为?形式。 x10 1 0 x2x31 0 0 x4x5x3 5/2 x1 5/2 cj?zj1/2 -1/2 -4 1/2 -1/6 -4 0 1/3 -2 (a)写出原线性规划问题 (b) 直接由表写出对偶问题的最优解。 答：（a）原线形规划问题如下：

maxz?6x1?2x2?10x3?x2?2x3?5?st.?3x1?x2?x3?10?x,x,x?0?123?

(b )对偶问题最优解为

5. 已知线性规划问题：

Y?(4,2)

maxz?5x1?3x2?6x3?x1?2x2?x3?18?2x?x?3x?16?123st.??x1?x2?x3?10?x1,x2?0,x3无约束 ?（a） 写出其对偶问题

（b） 已知原问题用两阶段法求解时得到的最终单纯形表如下 试写出其对偶问题的最优解。 5 3 6 －6 0 x10 x2 1 2 1 x3'x3'' 0 0 1 x4 1 0 0 x4 8 x5 1 14 －6 xs'' 4 0 1 0 0 0 －1 cj?zj0 －1 0 0 0 答： （a） 其对偶问题为

minw?18y1?16y2?10y3(1)?y1?2y2?y3?5?2y?y?y?3(2)?123st.?(3)?y1?3y2?y3?6??y1?0,y2,y3无约束

y第y（b） 设第（1）个约束条件的松弛变量为s1，（2）个约束条件的松弛变量为s2，

由原问题用两阶段法求得之最终单纯形表知

约束条件（1）~(3)有

ys1?0,ys2?1,y1?0，代入

?y1?2y2?y3?5??2y1?y2?y3?1?3?y?3y?y?623?1

(y,y,y)?(0,1,3)

解得：123

6.已知线性规划问题：

minz?2x1?x2?2x3??x1?x2?x3?4?st.??x1?x2?kx3?6?x?0,x?0,x无约束23?1

其最优解为

x1??5,x2?0,x3??1（a）求k的值；

（b）写出并求其对偶问题的最优解。 解：先写出其对偶问题如下：

maxw?4y1?6Y2

?y?y?2?12?y?y??1?12st.??y1?ky2?2??y1无约束,y2?0

由

z*?y*机互补松弛性质得

??y1?y2?2??4y1?6y2?12

解得y1?0,y2??2,代入求得k?1.

7.已知线性规划问题maxz?CX,AX?b,X?0,分别说明发生下列情况

时，其对偶问题的解的变化：

； (a)问题的第k个约束条件乘上常数?（??0）

(b)将第k个约束条件乘上常数?（??0）后加到第?个约束条件乘

上；

； (c)目标函数改变为maxz??CX（??0）

x1用3x1/(d)模型中全部

解：

代换。

?1Y?CBB?1,k?（a）对偶变量第个约束条件乘上常数?，即B的k列

1将为变化前的?，由此对偶问题变化后的解

1//(y1/,y2,...yk/,...ym)?(y1,y2,...yk,...ym);（b）与前类似，（c）（d）

?

bryr/?yr,yi/?yi(i?r);br??br

yi/??yi(i?1,...,m);

yi(i?1,...,m)不变。

8.已知线性规划问题：

max??cjxjj?1n?n??aijxj?bi(i?1,...,m)st.?j?1?x?0(j?1,...,n)?i

若（

***y1,y2,...,ym)为其对偶问题的最优解。又若原问题约束条件的，这时原问题的最优解变为（

//x1/,x2,...,xm)右端项变换为明

bibi/，试证

?j?1ncjx??bi/yi*/ji?1m

bi/解：原问题右端项变为后，其对偶问题为：

minz??bi/yii?1m

???aijyi?cj(j?1,...,n)st.?i?1?y?0(i?1,...,m)?im

必为上述问题的可行解。根据对

由于约束条件不变，（偶理论有：

***y1,y2,...,ym)?j?1ncjx??bi/yi*/ji?1m

9.已知线性规划问题：

maxz?x1?x2

??x1?x2?x3?2?st.??2x1?x2?x3?1?x,x,x?0?123

试应用对偶理论证明上述线性规划问题无最优解。

解：该问题存在可行解，如X?(0,0,0)；又上述问题的对偶问题为：

minw?2y1?y2??y1?2y2?1?y?y?1?2st.?1?y1?y2?0??y1,y2?0

解。

由第一个约束条件知对偶问题无可行解，由此可知其原问题无最优

10．已知线性规划问题：

maxz?x1?2x2?3x3?4x4?x1?2x2?2x3?3x4?20?st.?2x1?x2?3x3?2x4?20?x,x,x,x?0?1234

其对偶问题最优解为y1?1.2,y2?0.2,试根据对偶理论求出原问题的最优解。

*X?(0,0,4,4)解：写出对偶问题并根据互补松弛性质可求得原问题最优解为

2.11 已知某实际问题的线性规划模型为：

maxz??cjXjj?1n

若第i资源的影子价格为yi，

?naijXj?bi(i?1,2....m)???st:?j?1?Xj?0?(i?1,2....n???

（a） 若第一个约束条件两端乘以2，变为 约束条件的影子价格，求

?(2aj?1n1j)Xj?2bi ，

Y1 是对应这个新的

Y1与y1的关系；

x'?3x1 用 (x1'/3)替换模型中所有的x1，问影子价格yi是否变化？若x不可

（b） 令 11

x'能在最优基中出现，问1有否可能在最优基中出现；

（c） 如目标函数变为 解：（a）

maxz??2cjXjj?1n ，问影子价格有何变化？

yxx'Y1=1/2y1；

（b） 影子价格i不变，又1不在最优解中出现， 1也不可能在

y最优解中出现，（c）影子价格i也增大两倍。

2.12 下述线性规划问题

maxz?8x1?4x2?6x3?3x4?9x5?x1?2x2?3x3?3x4?3x5?180(资源1）?（资源2）?x1?2x2?3x3?3x4?3x5?270st.?（资源3）?x1?3x2?2x3?x4?3x5?180?x?0(j=1.2...5)?j

已知最优解中的基变量为

x3 x1 x5 且已知

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学习题(3)在线全文阅读。