运筹学复习题(第一章)线性规划及单纯型法

运筹学复习题(第一章)第一章线性规划及单纯型法1．试述线性规划数学模型的结构及各要素的特征。2．什么是线性规划问题的标准形式，如何将一个非标准型的线性规划问题转化为标准形式。3．试述线性规划问题的可行解、基本解、基可行解、最优解的概念以及上述解之间的相互关系。4．用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。(a)2146minxxz0,5.14312212121xxxxxx(b)2184maxxxz0,81022212121xxxxxx(c)2123maxxxz0,4221212121xxxxxx(d)2143maxxxz0,05264223212122121xxxxxxxxx5.将下列线性规划问题变换成标准型，并列出初始单纯型表。(a)32122minxxxz无约束321321321,0,064xxxxxxxxx解：将此线性规划问题变换成标准型：令''3'33'11;'xxxxxzz，在约束条件中分别添加松弛变量、剩余变量和人工变量得：54''3'32'10222'maxxMxxxxxz0,,,,,6454''3'32'15''3'32'14''3'32'1xxxxxxxxxxxxxxxx列出初始单纯型表如下：jc→21-22-M0BC基b'1x2x'3x''3x4x5x-M4x4[1]11-11005x611-1101jjzc2+M1+MM-22-M00(b)432132maxxxxxz无约束42314313214321,0,0,12285327xxxxxxxxxxxxxx解：令,,''4'442'2xxxxx化为标准型为8765''4'43'210032maxMxxMxxxxxxxz8,...,1012228532787''4'43163'215''4'43'21jxxxxxxxxxxxxxxxxxj表略。6．单纯型法求解下列线性规划问题，并指出问题的解属于哪一类：(a)2153maxxxz0,18231224212121xxxxxx(b)3212maxxxxz0,,20102603321321321321xxxxxxxxxxxx答案：(a)最优解x1x2x3x4x5x320011/3-1/3x260101/20x12100-1/31/3cj-zj000-3/2-1答案：(b)最优解x1x2x3x4x5x6x4100011-1-2x115101/201/21/2x2501-3/20-1/21/2cj-zj00-3/20-3/2-1/2