图解法和单纯形法求解线性规划问题

运筹学习题答案第一章（39页）1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。

（1）max 12z x x =+51x +102x £50 1x +2x ³1 2x £4 1x ，2x ³0 （2）min z=1x +1.52x 1x +32x ³3 1x +2x ³2 1x ，2x ³0 （3）max z=21x +22x 1x -2x ³-1 -0.51x +2x £2 1x ，2x ³0 （4）max z=1x +2x 1x -2x ³0 31x -2x £-3 1x ，2x ³0 解：（1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解（4）（图略）无可行解1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。

（1）min z=-31x +42x -23x +54x 41x -2x +23x -4x =-2 1x +2x +33x -4x £14 -21x +32x -3x +24x ³2 1x ，2x ，3x ³0，4x 无约束无约束（2）max kk z s p =11nmk ik ik i k z a x ===åå11(1,...,)mikk xi n =-=-=åik x ³0 (i=1(i=1……n; k=1,…,m) （1）解：设z=-z ¢,4x =5x -6x , 5x ,6x ³0 标准型：标准型：Max z ¢=31x -42x +23x -5(5x -6x )+07x +08x -M 9x -M 10x s. t . -41x +2x -23x +5x -6x +10x =2 1x +2x +33x -5x +6x +7x =14 -21x +32x -3x +25x -26x -8x +9x =2 1x ,2x ,3x ,5x ,6x ,7x ,8x ,9x ,10x ³0 初始单纯形表: j c ® 3 -4 2 -5 5 0 0 -M -M i qB C B Xb 1x 2x 3x 5x6x7x 8x9x10x-M 10x 2 -4 1 -2 1 -1 0 0 0 1 2 0 7x14 1 1 3 -1 1 1 0 0 0 14 -M 9x2 -2 [3] -1 2 -2 0 -1 1 0 2/3 -z ¢4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 -M 0 0 (2)解：加入人工变量1x ，2x ，3x ，…n x ，得：，得： Max s=(1/kp )1n i=å1m k =åik a ik x -M 1x -M 2x -…..-M n xs.t. 11mi ik k x x =+=å(i=1,2,3(i=1,2,3……,n) ik x ³0, i x ³0, (i=1,2,3(i=1,2,3……n; k=1,2….,m) M 是任意正整数是任意正整数 初始单纯形表：初始单纯形表： jc-M -M … -M 11k a p 12k a p… 1mk ap (1)n k a p 2n k a p …mnkapi qB C BXb 1x2x … n x11x12x … 1mx … 1n x2n x… nmx -M 1x1 1 0 … 0 1 1 … … 0 0 … 0 -M 2x 1 0 1 … 0 0 … … 0 0 … 0 … … … … … … … … … … … … … … … … -M n x 1 0 0 … 1 0 0 … 0 … 1 1 … 1 -s n M 0 0 … 0 11k a M p +12ka Mp + … 1mk a M p + (1)n k aM p +2n k a M p +…mnk a M p +1.3在下面的线性规划问题中找出满足约束条件的所有基解。

线性规划问题的两种求解⽅式线性规划问题的两种求解⽅式线性规划是运筹学中研究较早、发展较快、应⽤⼴泛、⽅法较成熟的⼀个重要分⽀，它是辅助⼈们进⾏科学管理的⼀种数学⽅法。

线性规划所研究的是：在⼀定条件下，合理安排⼈⼒物⼒等资源，使经济效果达到最好。

⼀般地，求线性⽬标函数在线性约束条件下的最⼤值或最⼩值的问题，统称为线性规划问题。

解决线性规划问题常⽤的⽅法是图解法和单纯性法，⽽图解法简单⽅便，但只适⽤于⼆维的线性规划问题，单纯性法的优点是可以适⽤于所有的线性规划问题，缺点是单纯形法中涉及⼤量不同的算法，为了针对不同的线性规划问题，计算量⼤，复杂繁琐。

在这个计算机⾼速发展的阶段，利⽤Excel建⽴电⼦表格模型，并利⽤它提供的“规划求解”⼯具，能轻松快捷地求解线性模型的解。

⽆论利⽤哪种⽅法进⾏求解线性规划问题，⾸先都需要对线性规划问题建⽴数学模型，确定⽬标函数和相应的约束条件，进⽽进⾏求解。

从实际问题中建⽴数学模型⼀般有以下三个步骤；1、根据所求⽬标的影响因素找到决策变量；2、由决策变量和所求⽬标的函数关系确定⽬标函数；3、由决策变量所受的限制条件确定决策变量所要满⾜的约束条件。

以下是分别利⽤单纯形法和Excel表格中的“规划求解”两种⽅法对例题进⾏求解的过程。

例题：某⼯⼚在计划期内要安排⽣产I、II两种产品，已知⽣产单位产品所需的设备台时分别为1台时、2台时，所需原材料A分别为4单位、0单位，所需原材料B分别为0单位、4单位，⼯⼚中设备运转最多台时为8台时，原材料A、B的总量分别为16单位、12单位。

每⽣产出I、II产品所获得的利润为2和3，问I、II两种产品的⽣产数量的哪种组合能使总利润最⼤？这是⼀个典型的产品组合问题，现将问题中的有关数据列表1-1如下：表1-1I II 限量设备 1 2 8台时原材料A 4 0 16单位原材料B 0 4 12单位所获利润 2 3⾸先对例题建⽴数学模型。

问题的决策变量有两个：产品I的⽣产数量和产品II的⽣产数量；⽬标是总利润最⼤；需满⾜的条件是：(1)两种产品使⽤设备的台时<= 台时限量值(2) ⽣产两种产品使⽤原材料A、B的数量<= 限量值(3)产品I、II的⽣产数量均>=0。

《运筹学》作业参考答案作业一一、是非题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

（√）2.线性规划问题的每一个基解对应可行解域的一个顶点。

（╳）3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。

（√）4.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。

（√）5.单纯形法计算中，如果不按最小比值规划选出基变量，则在下一个解中至少有一个基变量的值为负。

（√）6.线性规划问题的可行解如为最优解，则该可行解一定是基可行解。

（╳）7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。

（╳）8.对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为mnC个。

（╳）9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。

（√）10.求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。

（√）二、线性规划建模题：1.某公司一营业部每天需从A、B两仓库提货用于销售，需提取的商品有：甲商品不少于240件，乙商品不少于80台，丙商品不少于120吨。

已知：从A仓库每部汽车每天能运回营业部甲商品4件，乙商品2台，丙商品6吨，运费200元/每部；从B仓库每部汽车每天能运回营业部甲商品7件，乙商品2台，丙商品2吨，运费160元/每部。

问：为满足销售量需要，营业部每天应发往A、B两仓库各多少部汽车，并使总运费最少？解：设营业部每天应发往A、B两仓库各x1，x2部汽车,则有：12 121212min200160 47240 2280 621200(1,2)jW x xx xx xx xx j=++≥⎧⎪+≥⎪⎨+≥⎪⎪≥=⎩2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。

第一章 线性规划及单纯形法（作业）1.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

（1）Max z=2x 1+x 2St.⎪⎩⎪⎨⎧≥≤+≤+0,24261553212121x x x x x x 解：①图解法：由作图知，目标函数等值线越往右上移动，目标函数越大，故c 点为对应的最优解，最优解为直线⎩⎨⎧=+=+242615532121x x x x 的交点，解之得X=(15/4,3/4)T 。

Max z =33/4. ② 单纯形法：将上述问题化成标准形式有： Max z=2x 1+x 2+0x 3+0x 4St. ⎪⎩⎪⎨⎧≥≤++≤++0,,,242615535421421321x x x x x x x x x x其约束条件系数矩阵增广矩阵为：P 1 P 2 P 3 P 4⎥⎦⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵，构成一个基，对应变量向，x 3,x 4为基变量，令非基变量x 1,x 2为零，找到T 优解，代入目标函数得Max z=33/4.1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类。

（3）Min z=4x 1+x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 解：这种情况化为标准形式： Max z ＇=-4x 1-x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 添加人工变量y1,y2Max z ＇=-4x 1-x 2+0x 3+0x 4-My 1-My 2⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x(2) 两阶段法： Min ω=y 1+y 2St.⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x第二阶段，将表中y 1,y 2去掉，目标函数回归到Max z ＇=-4x 1-x 2+0x 3+0x 4第二章 线性规划的对偶理论与灵敏度分析（作业）2.7给出线性规划问题：Max z=2x 1+4x 2+x 3+x 4⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤+≤++)4,3,2,1(096628332143221421j x x x x x x x x x x x x j要求：（1）写出其对偶问题；（2）已知原问题最优解为X *=(2,2,4,0),试根据对偶理论，直接求出对偶问题的最优解。

1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。

⎪⎩⎪⎨⎧≤≤≤≤≤++=83105120106max 212121x x x x x x z2.将下述线性规划问题化成标准形式。

（1）⎪⎪⎩⎪⎪⎨⎧≥≥-++-≤+-+-=-+-+-+-=无约束4,03,2,12321422245243min 4321432143214321x x x x x x x x x x x x x x x x x x x x z解：令z z -='，''4'44x x x -=⎪⎪⎩⎪⎪⎨⎧≥=-+-++-=+-+-+=-+-+-+-+-=0,,,,,,232142222455243'max 65''4'43216''4'43215''4'4321''4'4321''4'4321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x z 3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。

⎪⎩⎪⎨⎧≥≤+≤++=0,825943510max 21212121x x x x x x x x z解：①图解法：②单纯形法：将原问题标准化：⎪⎩⎪⎨⎧≥=++=+++=0,,,825943510max 432142132121x x x x x x x x x x x x z C j10 5 0 0 θ 对应图解法中的点C B B b x 1 x 2 x 3 x 4 0 x 3 9 3 4 1 0 3 O 点 0x 48 [5] 2 0 1 8/5 σj 0 10 5 0 0 0 x 3 21/5 0 [14/5] 1 -3/5 3/2 C 点 10x 1 8/5 1 2/5 0 1/5 4 σj -16 0 1 0 -2 5 x 2 3/2 0 1 5/14 -3/14 B 点 10x 1 1 1 0 -1/7 2/7 σj35/2-5/14-25/14最优解为（1,3/2,0,0），最优值Z=35/2。

线性规划单纯形法(例题)《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》⎪⎩⎪⎨⎧≥=++=+++++=⎪⎩⎪⎨⎧≥≤+≤++=0,,,24261553).(002max ,,0,24261553).(2max 14.18432142132143214321212121x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。

分别用图解法和单纯形）】（页【为初始基变量，选择43,x x)1000(00)0010(01)2050(12)6030(24321=⨯+⨯-==⨯+⨯-==⨯+⨯-==⨯+⨯-=σσσσ为出基变量。

为进基变量，所以选择41x x3/1)6/122/10(00)0210(03/1)3/1240(10)1200(24321-=⨯+-⨯-==⨯+⨯-==⨯+⨯-==⨯+⨯-=σσσσ为出基变量。

为进基变量，所以选择32x x24/724/528/11012/112/124/1100021110120124321-=⨯+-⨯-=-=-⨯+⨯-==⨯+⨯-==⨯+⨯-=）（）（）（）（σσσσ4334341522max ,)43,415(),(2112=+⨯=+===x x z x x X TT 故有：所以，最优解为⎪⎪⎩⎪⎪⎨⎧≥=++=+=+++++=⎪⎪⎩⎪⎪⎨⎧≥≤+≤≤+=0,,,,18232424).(0002max ,,,0,182312212).(52max 24.185432152142315432154321212121x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。

1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。

２。

将下述线性规划问题化成标准形式。

（1)解:令,3。

分别用图解法和单纯形法求解下述线性规划问题,并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。

解:①图解法:单纯型法步骤：转化为标准线性规划问题;找到一个初始可行解,列出初始单纯型表；最优性检验，求cｊ－zj,若所有的值都小于0，则表中的解便是最优解,否则,找出最大的值的那一列，求出ｂi／aiｊ,选取最小的相对应的ｘij,作为换入基进行初等行变换,重复此步骤。

4.写出下列线性规划问题的对偶问题。

（1)（2)5。

给出线性规划问题要求:（１)写出其对偶问题；（2）已知原问题最优解为,试根据对偶理论，直接求出对偶问题的最优解。

解：(１)(２)因为,第四个约束取等号,根据互补松弛定理得:求得对偶问题的最优解为：，最优值min ｗ＝1６。

弱对偶性的推论：(１) 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界;反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界(２) 如原问题有可行解且目标函数值无界(具有无界解）,则其对偶问题无可行解;反之对偶问题有可行解且目标函数值无界,则其原问题无可行解。

注意：本点性质的逆不成立,当对偶问题无可行解时,其原问题或具有无界解或无可行解，反之亦然。

(3）若原问题有可行解而其对偶问题无可行解,则原问题目标函数值无界;反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。

强对偶性(或称对偶定理)若原问题及其对偶问题均具有可行解，则两者均具有最优解,且它们最优解的目标函数值相等。

互补松弛性在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式;反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。

影子价格资源的市场价格是其价值的客观体现,相对比较稳定,而它的影子价格则有赖于资源的利用情况,是未知数。

盐城师范学院运筹学期末论文题目: 用单纯形法解决线性规划问题**: **二级学院: 数学科学学院专业: 数学与应用数学班级: 111 班学号: ********成绩评定:前言线性规划问题是数学以及日常生活中最基本的问题之一，如何快速有效的解决线性规划问题是数学家也在努力研究的科目之一。

以前中学时我们解决线性规划问题一般采用的是图解法，即画出所给条件的可行域，找出目标函数的最优解。

这种方法的优点是直观性强，计算方便，但缺点是只适用于问题中有两个变量的情况。

下面我们介绍另外一种方法—单纯形法，来解决图解法不能解决的问题。

1 单纯形法1.1 单纯形法的基本思路利用求线性规划问题基本可行解的方法求解较大规模的问题是不可行的。

有选择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。

在线性规划的可行域中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数值接近最优值的另一个基本可行解。

由于基本可行解的个数有限，所以总可以通过有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。

1.2 单纯形法的基本步骤第1步求初始基可行解，列出初始单纯形表。

对非标准型的线性规划问题首先要化成标准形式。

由于总可以设法使约束方程的系数矩阵中包含一个单位矩阵（P1,P2，…，Pm），以此作为基求出问题的一个初始基可行解。

为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数值进行比较。

为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表（见表1—1）。

迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。

含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。

第2步：最优性检验如表中所有检验数c j−z j≤0，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。