资源描述：
《运筹学第1章线性规划和单纯形法复习试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第1章线性规划及单纯形法(LinearProgrammingandSimplexMethod)§1一般线性规划问题及其数学模型§2图解法§3单纯形法原理§5单纯形法的进一步讨论§7线性规划应用§4单纯形法的计算步骤§6数据包络分析为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。例一、有一正方形铁皮，如何截取x使容积为最大？xa此为无约束极值问题（一）、问题的提出§1一般线性规划问题及其数学模型设备产品ABCD利润(元)Ⅰ21402Ⅱ22043有效台时1281612例二、已知资料如表所示，问如何安排
2、生产才能使利润最大？或如何考虑利润大，产品好销。模型maxZ=2x1+3x2x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此为带约束的极值问题问题中总有未知的变量，需要我们去解决。要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性的。反之，就是非线性的规划问题。（二）、数学模型1、目标函数：约束条件：①②③2、线性规划数学模型的一般形式也可以记为如下形式：目标函数：约
3、束条件：如将上例用表格表示如下：设变量产品j设备i有效台时利润向量形式：矩阵形式：3、线性规划的标准形式①②③一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意多个变量、但需将一般形式变成标准形式4、线性规划问题的解（一）求解方法1、解的概念⑴可行解：满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。⑵最优解：使目标函数①达到最大值的可行解。⑶基：B是矩阵A中m×m阶非奇异子矩阵（∣B∣≠0），则B是一个基。则称Pj(j=12……m)为基向量。∴Xj为基变量，否则为非基变量。（二）线性规划问题的解⑷基本解：满足条件②，但不满足条件③由基B
4、决定的解.最多为个。⑸基本可行解：满足非负约束条件的基本解，简称基可行解。⑹可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解例题基可行解说明maxZ=70X1+120X2P1P2P3P4P59X1+4X2+X3=360941004X1+5X2+x4=200A=450103X1+10X2+x5=300310001Xj≥0j=1,2,…,5这里m=3,n=5。Cmn=10基（p3,p4,p5），令非基变量x1,x2=0，则基变量x3=360,x4=200,x5=300,可行解基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=－250,x5=
5、－600.非可行解基（p2,p3,p4），令非基变量x1,x5=0，则基变量x2=30,x3=240,x4=50,可行解.例一、⑴⑵⑶⑷§2图解法012345678123456⑴⑵⑶⑷作图∴最优解：x1=4，x2=2有唯一最优解，Z=14x2x1(42)⑴⑵⑶⑷例二、例三、⑴⑵⑶无穷多最优解⑴⑵无界解x1x1x2x2⑴⑵x1x2无可行解例四、图解法的解题思路和几何上直观得到的一些结论对于求解一般的线性规划有什么启示?§3单纯形法原理(1)(2)几个1引理标准形线性规划问题的可行解X=(x1,x2,···,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的.定
6、理2标准形线性规划的基本可行解X对应可行域(凸集)的顶点(极点).证明:(1)若X不是基本可行解→X不是可行域的顶点.不失一般性,假设X的前m个分量正,故有由引理知P1,P2,···,Pm线性相关,即存在一组不全为零的数δi(i=1,2,…,m),使得δ1P1+δ2P2+···+δmPm=0(2)(1)于是有:(x1±μ•δ1)P1+(x2±μ•δ2)P2+···+(xm±μ•δm)Pm=b(3)其中μ的选取使得对所有xi±μ•δi≥0(i=1,2,…,m).由(3)式可知:X(1)=(x1+μ•δ1,x2+μ•δ2,…,xm+μ•δm,0,…,0)TX(2)=(x1-μ•δ1
7、,x2-μ•δ2,…,xm-μ•δm,0,…,0)T是线性规划的可行解,即为可行域中的点,但是点是X(1)和X(2)的凸组合,所以不是极点(顶点).(2)若X不是可行域的顶点→X不是基本可行解.如果X不是可行域内的点,即X不是可行解,当然X不是基本可行解.不妨设X是一个可行解,X=(x1,x2,…,xr,0,…,0)T且,但不是可行域的顶点.由于可行域是凸集,所以存在两个不同的点Y和Z,使得X=aY+(1-a)Z,其中0
