线性规划与单纯形法

1、1、 选择填空1. 2. 3. 4. 5. 6. 7. 8. 9. 10.2、 判断正误1. 2. 3. 4. 5. 6. 7. 8. 9. 10.3、 将下列问题化为标准型1.解 令，在约束1中引入非负的松弛变量，约束2两边同乘以-1。整理得： 即：2. Min Z=-x1+5x2-2x3s.t. x1 +x2 - x3 6 2x1 - x2 +3x3 5 x1 + x2 = 10 x1 0, x2 0, x3符号不限解 首先，令对变量x3进行处理，令x3 = x3- x4;再令x2 = - x2。然后对目标函数和约束条件进行标准化。 Max Z=x1+5x2+2x3-2x4s.t. x1

2、- x2 - x3+x4+x5 = 6 2x1 + x2 +3x3 - 3x4 -x6 = 5 x1 - x2 = 10 x1, x2, x3, x4, x5, x6 04、 用图解法求解下列线性规1. min Z= - x1+2x2s.t. x1 - x2 -2 x1 +2x2 6 x1, x2 0E-2 -1 0 1 2 3 4 5 6 7 8 x1x2 6 5 4 3 2 1 x1 - x2 -2x1 +2x2 6解 画图如下：根据上图，最优解为X*=（x1, x2）T =（6, 0）T，最优值为-6。2.Max Z= - x1+2x2s.t. x1 - x2 -2 x1 +2x2 6

3、x1, x2 0E-2 -1 0 1 2 3 4 5 6 7 8 x1x2 6 5 4 3 2 1 x1 - x2 -2x1 +2x2 6解 画图如下：根据上图，最优解为，最优值为。5、 用单纯形法求解下列线性规划1. Max Z=3x1+5x2s.t. x1 4 2x2 12 3x1 +2x2 18 x1, x2 0解 首先，标准化后线性规划如下：（1）Max Z=3x1+5x2+0x3+0x4+0x5s.t. x1 + x3 = 4 2x2 + x4 = 12 3x1 +2x2 + x5 = 18 x1, x2, x3, x4, x5, x6 0再用表格单纯形法求解如下：（一、按照第一个正

4、检验数对应非基变量进基的方法）CBXBcjb xj3 5 0 0 0x1 x2 x3 x4 x5j000x3 x4 x5412181 0 1 0 00 2 0 1 03 2 0 0 14/118/3-Z03 5 0 0 0 300x1 x4 x541261 0 1 0 00 2 0 1 00 2 -3 0 1 12/2 6/2-Z-12 0 5 -3 0 0305x1 x4 x24631 0 1 0 00 0 3 1 -10 1 -3/2 0 1/2 4/1 6/3-Z-27 0 0 9/2 0 -5/2305x1 x3 x22261 0 0 -1/3 1/30 0 1 1/3 -1/30 1

5、 0 1/2 0-Z-36 0 0 0 -3/2 -1（二、按照最大正检验数对应非基变量进基的方法）CBXBcjb xj3 5 0 0 0x1 x2 x3 x4 x5j000x3 x4 x5412181 0 1 0 00 2 0 1 03 2 0 0 112/218/2-Z03 5 0 0 0 050x3 x2 x54661 0 1 0 00 1 0 1/2 03 0 0 -1 1 4/1 6/3-Z-12 3 0 0 -5/2 0053x3 x2 x12620 0 1 1/3 -1/30 1 0 1/2 01 0 0 -1/3 1/3 -Z-36 0 0 -3 -3/2 -1因此，最优解为X

6、* =（2, 6, 2, 0, 0）T，最优值为Zmax=36。2. Max Z=2x1- x2+x3s.t. 3x1+x2+x3 60 x1-x2+2x3 10 x1 +x2-x3 20 x1, x2, x3 0解 首先，标准化后线性规划如下：（1）Max Z=2x1-x2+x3s.t. 3x1+x2+x3+x4 = 60 x1-x2+2x3+x5 = 10 x1 +x2-x3 +x6 = 20 x1, x2, x3, x4, x5, x6 0再用表格单纯形法求解如下：CBXBcjb xj2 -1 1 0 0 0x1 x2 x3 x4 x5 x6j000x4 x5 x66010203 1 1

7、 1 0 01 -1 2 0 1 01 1 -1 0 0 160/310/120/1-Z02 -1 1 0 0 0 020x4 x1 x63010100 4 -5 1 -3 01 -1 2 0 1 00 2 -3 0 -1 1 30/4 10/2-Z-200 1 -3 0 -2 002-1x4 x1 x2101550 0 1 1 -1 -21 0 1/2 0 1/2 1/20 1 -3/2 0 -1/2 1/2-Z-250 0 -3/2 0 -3/2 -1/2因此，最优解为X* =（15, 5, 0, 10, 0, 0）T，最优值为Zmax=25。6、 表格单纯形法计算题1. （2）初始线性规

8、划模型如下：Max Z=5x1+20x2+25x3s.t. 2x1+x2 40 2x2+x3 30 3x1 -1/2x3 15 x1, x2, x3 0（3）用单纯形法求出最优解及相应的最优值。解（按照最大检验数对应非基变量进基的方法）CBXBcjb xj5 20 25 0 0 0x1 x2 x3 x4 x5 x6j000x4 x5 x64030152 1 0 1 0 00 2 1 0 1 03 0 -1/2 0 0 130/1-Z05 20 25 0 0 0 0250x4 x3 x64030302 1 0 1 0 00 2 1 0 1 03 1 0 0 1/2 1 40/230/3-Z-75

9、05 -30 0 0 -25 00255x4 x3 x12030100 1/3 0 1 -1/3 -2/30 2 1 0 1 01 1/3 0 0 1/6 1/3-Z-8000 -95/3 0 0 -155/6 -5/37、 用大M法和两阶段法求解下列线性规划1. min Z= x1+2x2s.t. -x1 +2x2 2 x1 3 x1, x2 0解 标准化并引入人工变量x5后，线性规划模型如下：Max Z=-x1-2x2-Mx5s.t. -x1+2x2 -x3 +x5 = 2 x1 +x4 = 3x1, x2, x3, x4, x5 0用大M法求解如下：CBXBcjb xj-1 -2 0 0

10、 -M x1 x2 x3 x4 x5 j-M 0x5 x4 23-1 2 -1 0 1 1 0 0 1 0 2/2-Z2M-1-M -2+M -M 0 0 -2 0x2 x4 13-1/2 1 -1/2 0 1/2 1 0 0 1 0 -Z2 -2 0 -1 0 1-M从表中可以看出，最优解X* =（0, 1, 0, 3）T，最优值为Zmax=-2。因此，原问题最优解X* =（0, 1, 0, 3）T，最优值为Zmin=2。用两阶段法求解如下：第一阶段：标准化并引入人工变量x5，对人工变量进行优化线性规划模型如下：Max W=-x5s.t. -x1+2x2 -x3 +x5 = 2 x1 +x4

11、 = 3 x1, x2, x3, x4, x5 0CBXBcjb xj0 0 0 0 -1 x1 x2 x3 x4 x5 j-1 0x5 x4 23-1 2 -1 0 1 1 0 0 1 0 2/2-W2-1 2 -1 0 0 0 0x2 x4 13-1/2 1 -1/2 0 1/2 1 0 0 1 0 -Z0 0 0 0 0 -1由于人工变量x5=0，故可以划去该列，以x2， x4为基变量进行第二阶段的计算。第二阶段：Max Z=-x1-2x2s.t. -1/2x1+x2 -1/2x3 = 1 x1 +x4 = 3 x1, x2, x3, x4 0由于上表中所有非基变量的检验数小于等于0，因

12、此，原问题已经达到最优解，即X* =（0, 1, 0, 3）T，最优值为Zmin=2。2. Max Z=x1+2x2+3x3-x4s.t. x1+2x2+3x3 = 15 2x1+x2+5x3 = 20 x1 +2x2+x3+x4 = 10 x1, x2, x3, x4 0解 首先，标准化并引入人工变量x5, x6后,线性规划如下：（1）Max Z=x1+2x2+3x3-x4-Mx5-Mx6s.t. x1+2x2+3x3+x5 = 15 2x1+x2+5x3+x6 = 20 x1 +2x2+x3+x4 = 10 x1, x2, x3, x4 0用大M法求解如下：CBXBcjb xj1 2 3

13、-1 -M -Mx1 x2 x3 x4 x5 x6 j-M -M-1x5 x6x4 1520101 2 3 0 1 0 2 1 5 0 0 1 1 2 1 1 0 0 15/320/510/1-Z35M+102+3M 4+3M 4+8M 0 0 0 -M 3-1x5 x3x4 346-1/5 7/5 0 0 1 -3/5 2/5 1/5 1 0 0 1/5 3/5 9/5 0 1 0 -1/5 15/720/130/9-Z3M-62/5-M/5 0 0 0 16/5+7M/5 -4/5-8M/52 3-1x2 x3 x415/725/715/7-1/7 1 0 0 5/7 -3/7 3/7 0

14、 1 0 -1/7 2/7 6/7 0 0 1 -9/7 4/7 25/315/6-Z-90/76/7 0 0 0 231x2 x3 x15/25/25/20 1 0 1/6 1/2 -1/3 0 0 1 -1/2 1/2 0 1 0 0 7/6 -3/2 2/3 -Z-150 0 0 -1 -M-1 -M从表中可以看出，最优解X* =（5/2, 5/2, 5/2, 0, 0, 0）T，最优值为Zmax=15。用两阶段法求解如下： Min W=x5+x6CBXBcjb xj0 0 0 0 1 1x1 x2 x3 x4 x5 x6 j1 10x5 x6x4 1520101 2 3 0 1 0 2

15、 1 5 0 0 1 1 2 1 1 0 0 15/320/510/1-W-35 -3 -3 -8 0 0 0 1 00x5 x3x4 346-1/5 7/5 0 0 1 -3/5 2/5 1/5 1 0 0 1/5 3/5 9/5 0 1 0 -1/5 15/720/130/9-W-3 1/5 -7/5 0 0 0 8/5000x2 x3 x415/725/715/7-1/7 1 0 0 5/7 -3/7 3/7 0 1 0 -1/7 2/7 6/7 0 0 1 -9/7 4/7 25/315/6-W00 0 0 0 1 1从表中可以看出，第一阶段的最优解X* =（0, 15/7, 25/7

16、, 15/7, 0, 0）T，最优值为Wmin=0。转入第二阶段求解如下：CBXBcjb xj1 2 3 -1 x1 x2 x3 x4 j2 3-1x2 x3 x415/725/715/7-1/7 1 0 0 3/7 0 1 0 6/7 0 0 1 25/315/6-Z-90/76/7 0 0 0 2 31x2 x3 x15/25/25/20 1 0 1/6 0 0 1 -1/2 1 0 0 7/6 -Z-150 0 0 -1 s.t.3. Max Z=3x1- x2-x3 x1-2x2+x3 11 -4x1+x2+2x3 3 -2x1 +x3 = 1 x1, x2, x3 0解 首先，标准化

17、并引入人工变量x6, x7后,线性规划如下：Max Z=3x1-x2-x3-Mx6-Mx7 s.t. x1-2x2+x3 +x4 = 11 -4x1+x2+2x3 -x5+x6 = 3 -2x1 +x3+x7 = 1 x1, x2, x3, x4, x5, x6, x7 0用大M法求解如下：CBXBcjb xj3 -1 -1 0 0 -M -Mx1 x2 x3 x4 x5 x6 x7j0 -M-Mx4 x6 x711311 -2 1 1 0 0 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 1 3/1-Z4M3-6M M-1 3M-1 0 -M 0 0 0 -1-Mx4 x2 x7

18、1731-7 0 5 1 -2 2 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 117/53/21/1-Z3+M-1-2M 0 M+1 0 -1 1-M 00 -1-1x4 x2 x312113 0 0 1 -2 2 -50 1 0 0 -1 1 -2-2 0 1 0 0 0 1 12/3-Z2 1 0 0 0 -1 1-M -1-M3 -1-1x1 x2 x34191 0 0 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -20 0 1 2/3 -4/3 4/3 -7/3-Z-2 0 0 0 -1/3 -1/3 1/3-M 2/3-M从表中可以看出，最优解X* =

19、（4, 1,9, 0, 0, 0, 0）T，最优值为Zmax=2。用两阶段法求解如下： Min W=x6+x7CBXBcjb xj0 0 0 0 0 1 1x1 x2 x3 x4 x5 x6 x7j0 11x4 x6 x711311 -2 1 1 0 0 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 1 3/1-W-46 -1 -3 0 1 0 0 0 01x4 x2 x71731-7 0 5 1 -2 2 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 117/53/21/1-W-12 0 -1 0 0 1 00 00x4 x2 x312113 0 0 1 -2 2 -

20、50 1 0 0 -1 1 -2-2 0 1 0 0 0 1 -W0 0 0 0 0 0 1 1从表中可以看出，第一阶段的最优解X* =（0, 1, 1, 12, 0, 0, 0）T，最优值为Wmin=0。转入第二阶段求解如下：CBXBcjb xj3 -1 -1 0 0 x1 x2 x3 x4 x5 j0 -1-1x4 x2 x312113 0 0 1 -2 0 1 0 0 -1 -2 0 1 0 0 12/3-Z-41 0 0 0 -1 3 -1-1x1 x2 x34191 0 0 1/3 -2/30 1 0 0 -10 0 1 2/3 -4/3-Z-20 0 0 -1/3 -1/3从表中可

21、以看出，最优解X* =（4, 1,9, 0, 0, 0, 0）T，最优值为Zmax=2。8、 线性规划建模1. 某商店制定一种商品的712月进货与销售计划。由于商店仓库容量的限制，存货不能超过500件。6月底已存货100件，以后每月1日进货一次。假设各月份该种商品买进及销售单价如下表所示，问各月应进货、销售各多少，才能是总收入最多？试列出线性规划模型。月份7月8月9月10月11月12月买进单价元282425272323销售单价元292426282225解设7-12月份进货量分别为x11, x21, x31, x41, x51, x61; 销售量分别为x12, x22, x32, x42, x5

22、2, x62。则最大化目标函数可以表示为各个月的销售总收入与各个月进货总成本的差额。而约束条件包括两方面：月初库存量、月末库存量约束，库存要求介于0，500区间，因此，模型构造如下：Max Z =（29x12+24x22+26x32+28x42+22x52+25x62）-（28x11+24x21+25x31+27x41+23x51+23x61） s.t.x11 500-100 (或者400)100+x11-x12 0 (或者x12 100+ x11)x21 500-（100+x11-x12）100+x11-x12+x21-x22 0x31 500-（100+x11-x12+x21-x22）10

23、0+x11-x12+x21-x22+x31-x32 0x41 500-（100+x11-x12+x21-x22+x31-x32）100+x11-x12+x21-x22+x31-x32+x41-x42 0x51 500-（100+x11-x12+x21-x22+x31-x32+x41-x42）100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52 0x61 500-（100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52）100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52+x61-x62 0x11

24、, x21, x31, x41, x51, x61, x12, x22, x32, x42, x52, x62 03. 某厂生产A、B、C 三种产品，每种产品都要经过甲、乙两道工序。设该厂有两种规格的设备，甲1和甲2可以完成甲工序；有3种规格的设备乙1、乙2、乙3能完成乙工序。每种设备完成每个产品的加工工时、每小时的费用以及每件产品的原料费用和销售价格如表1.12所示，其中空缺位置表示该设备不能加工该种产品，要求安排最优生产计划，使该厂利润最大。工序设备产品设备有效台时设备加工费（元小时）ABC甲甲148050000.1甲2379110000.05乙乙106230000.08乙25056000

25、0.12乙363040000.07原料费（元件）0.30.50.8单价（元件）1.52.54甲1甲2乙1乙2乙3解：（1）决策变量：设A产品经过甲乙两道工序（5种规格）加工的产品数分别为；B产品经过甲乙两道工序（5种规格）加工的产品数分别为；C产品经过甲乙两道工序（5种规格）加工的产品数分别为；（2）目标函数：总利润收益工时成本C1材料成本C2收益A产品数×单价B产品数×单价C产品数×单价 C1+C2(3)工时约束： （4）工序流程约束：甲工序加工的产品数乙工序加工的产品数（A、B、C） 则线性规划模型为：9、 研究讨论题第1章 常见错误总结：（1）表格单纯形法简便易行，但却不习惯用。虽然思路十分明确，但还是不方便。单纯形表格可以求最优解，也可以进行敏感性分析。最优表中有许多有用的信