运筹学作业-王程130404026(6)

(4) maxz??cjxjj?1n?n??aijxj?bi (i?1,?,m1?m)?j?1n??ax?b (i?m?1,m?2,?,m) s.t.??ijji11?j?1?xj?0 (j?1,?,n1?n)???xj无约束 (j?n1?1,?,n)解：对偶问题：minw?b1y1?b2y2??bmym?m??aijyi?cj (j?1,2,?,n1)?i?1?m s.t.??aijyi?cj (j?n1?1,n1?2,?,n)?i?1?yi?0 (i?1,?,m1)??yi无约束 (j?m1?1,?,m) 对偶的对偶问题：maxz??cjxjj?1n?n??aijxj?bi (i?1,?,m1?m)?j?1 n?? s.t.??aijxj?bi (i?m1?1,m1?2,?,m)?j?1?xj?0 (j?1,?,n1?n)???xj无约束 (j?n1?1,?,n)

2.2 判断下列说法是否正确，并说明为什么。

⑴如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错误。如果原问题是无界解，则对偶问题无可行解。

⑵如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：错误。如果对偶问题无可行解，也可能是因为原问题是无界解。

⑶在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； 答：错误。如果原问题是求极小，则结论相反。 ⑷任何线性规划问题具有唯一的对偶问题。 答：正确。

2.5 已知某求极大线性规划问题用单纯形法求解时的初始单纯形表及最终单纯

形表如表2-30所示，求表中各括号内未知数(a)～(l)的值。

cj → CB 基 b000x4x5x6cj-zj?3x11(a)232x211(c)22x31212?0x4100000x60010x50100(b)1520032x4x1x2cj-zj5/425/45/20100001(k)(d)(e)(f)(g)(l)000-1/43/4(h)-5/4-1/4(i)1/2(j)

解：l=1，k=0，a=2，c=3，h=-1/2，b=10，e=5/4，f=-1/2，d=1/4， g=-3/4，i=-1/4，j=-1/4. 2.6 给出线性规划问题

minz?2x1?3x2?5x3?6x4

?x1?2x2?3x3?x4?2?s.t.??2x1?x2?x3?3x4??3

?x?0 (j?1,?,4)?j⑴写出其对偶问题；⑵用图解法求解对偶问题；⑶利用⑵的结果及根据对偶问题性质写出原问题最优解。

解：⑴其对偶问题为：

minw?2y1?3y2?y1?2y2??2?2y?y??312?? s.t.?3y1?y2??5

?y?3y??62?1??y1?0,y2?0⑵图解法求解：

y2y18119 求得最优解为y1??,y2?,z*??

555（3）根据互补松弛型性质可以得到最优解X*?(7/5,0,1/5,0) 2.7 给出线性规划问题

maxz?3x1?2x2?5x3?x1?2x2?x3?500?3x ?2x?460?13 s.t.??x1?4x2 ?420?? x1,x2,x3?0⑴写出其对偶问题；⑵利用对偶问题性质证明原问题目标函数值z?1360 。 解：⑴其对偶问题为：

minw?500y1?460y2?420y3?y1?3y2?y3?3?2y ?4y?2?13s.t.??y1?2y2 ?5??y1,y2,y3?0

51 ⑵易得y1?0,y2?,y3? 是对偶问题的一个可行解，带入目标函数得

22w?1360 ，故原问题的目标函数值z?1360。

2.8 已知线性规划问题

maxz?x1?x2??x1?x2?x3?2 s.t.???2x1?x2?x3?1

?x,x,x?0?123试根据对偶问题性质证明上述线性规划问题目标函数值无界。

解：x1?2,x2?x3?0是原问题的一个可行解，原问题的对偶问题为： minw?2y1?y2??y1?2y2?1 (1)? y? y?1 (2) ?12 s.t.?? y1? y2?0 (3)?? y1,y2?0 (4)由于(1)和(4)是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。2.9 给出线性规划问题

maxz?2x1?4x2?x3?x4?x1?3x2 ?x4?8??2x1?x2 ?6 ?s.t.? x2?x3?x4?6?x?x?x ?923?1??xj?0 (j?1,?,4)

2，4，0),试根据对偶要求：⑴写出其对偶问题；⑵已知原问题最优解为X?(2，理论，直接求出对偶问题的最优解。

解：⑴其对偶问题为：

*minw?8y1?6y2?6y3?9y4?y1?2y2 ?y4?2??3y1?y2?y3?y4?1 s.t.? y?y?1?34? y?y?113???yj?0(j?1,?,4)*

2，4，0)，带入原问题，第4个约束不等式 ⑵已知原问题最优解为X?(2，成立，故y4?0。又由于x1,x2,x3大于0，上面对偶问题前3个约束取等号，故

43得到最优解：Y*=（，,1,0）。

552.10 已知线性规划问题A和B如下： 问题Amaxz??cjxj 影子价格j?1n

?n??a1jxj?b1 y1?j?1?n??a2jxj?b2 y2s.t.?j?1?n??a3jxj?b3 y3?j?1?x?0 (j=1,?,n)?j 问题Bmaxz??cjxj 影子价格j?1n

?n?1??5a1jxj?5b1 y?j?1?n11?2??a2jxj?b2 y5s.t.?j?15?n??(a3j?3a1j)xj?b3?3b1 y?3?j?1?x?0 (j?1,?,n)?j

试分别写出

?i同yi(i?1,2,3)间的关系式。 y?1?解：y11?2?5y2,y?3?y3?y1 . y1,y53（2） minz?5x1?2x2?4x3

2.11 用对偶单纯形法求解下列线性规划问题。

（）1 minz?4x1?12x2?18x3?x1 ?3x3?3? s.t.? 2x2?2x3?5?x,x,x?0?123解：⑴先将问题改写为：

?3x1?x2?2x3?4? s.t.?6x1?3x2?5x3?10

?x,x,x?0?123

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