第五章 线性规划 线性规划模型 线性规划的图解 单纯形法原理 单纯形法 单纯形表 单纯形的理论分析 人工变量法.

Presentation on theme: "第五章 线性规划 线性规划模型 线性规划的图解 单纯形法原理 单纯形法 单纯形表 单纯形的理论分析 人工变量法."— Presentation transcript:

1 第五章 线性规划 线性规划模型 线性规划的图解 单纯形法原理 单纯形法 单纯形表 单纯形的理论分析 人工变量法

2 §5.1 线性规划的数学模型 问：甲乙各生产多少，使企业利润最大？ 一、问题的提出 例1：生产计划问题： 设备 产品 A B C 利润
§5.1　线性规划的数学模型　 一、问题的提出 例1：生产计划问题： 设备 产品 A B C 利润 (元/公斤) 甲 3 5 9 70 乙 30 限制工时 540 450 720 问：甲乙各生产多少，使企业利润最大？

3 解:设产品甲、乙各生产x1 ， x2公斤 设总利润为Z，则： 资源约束 变量非负约束 设备 产品 A B C 利润 (元/公斤) 甲 3 5
9 70 乙 30 限制工时 540 450 720 解:设产品甲、乙各生产x1 ， x2公斤 设总利润为Z，则： 资源约束 变量非负约束

4 cj为价值系数 二、线性规划模型的一般特点 线性规划模型的一般形式： Max(Min) z=c1x1+c2x2+……+cnxn
1、决策变量：向量(x1… xn)T　　　　　　　　　 2、目标函数：Z=ƒ(x1 … xn)线性式，　　　　 3、约束条件：线性等式或不等式 行动方案 明确的目标要求，极大或极小 反映了客观限制条件。 cj为价值系数 线性规划模型的一般形式： Max(Min) z=c1x1+c2x2+……+cnxn   a11x1+a12x2+……+a1nxn≥(=或≤)b1 　　 　a21x1+a22x2+……+a2nxn≥(=或≤)b2 …… am1x1+am2x2+……+amnxn≥(=或≤)bm      xj(j=1,…,n) ≥(≤) 0，或者没有限制  约束方程 s.t. 变量约束

5 某厂生产A、B两种产品，都需用煤、金属材料、电力等资源，各产品对三种资源的消耗及可供利用的资源如表2示：
三、常用的线性规划模型 例2：资源合理利用问题： 某厂生产A、B两种产品，都需用煤、金属材料、电力等资源，各产品对三种资源的消耗及可供利用的资源如表2示： 表2： 　资源 产品 煤（吨） 金属材料 （公斤） 电力 （千瓦） 产品利润 （元/吨） A 6 80 50 6000 B 8 10 5000 资源供应量 540 4000 2000 问：应如何安排生产，使企业获利最大？

6 解：设产品A、B产量分别为变量x1 ， x2（吨），则：
　资源 产品 煤（吨） 金属材料 （公斤） 电力 （千瓦） 产品利润 （元/吨） A 6 80 50 6000 B 8 10 5000 资源供应量 540 4000 2000

7 例3、合理下料问题： 有一批长度为180厘米的钢管，需截成70、52和35厘米3种管料。它们的需求量分别不少于100、150和100根。问如何下料才能使钢管的消耗量为最少？ 先找出各种可能的下料方式：（再在各种可能的下料方案中去选择） 设在180厘米长的钢管上能下出u个70厘米管料，v个52厘米管料， w个35厘米，则满足约束条件： 70u+52v+35w≤180，其中，u，v，w只能是正整数。 　从最大尺寸管料下起：

8 各种可能的下料方案： I II III IV V VI VII VIII 70 2 1 52 3 35 5 合计 175 174 157 156 余料 6 23 24

9 min Z= 5x1 + 6x2＋23x3+5x4+24x5+6x6+23x7+5x8
解：设按第j种方案下料的原材料为xj根 min　Z= 5x1 + 6x2＋23x3+5x4+24x5+6x6+23x7+5x8 2x1 + x2 +x3+x4 　　　　 ≥100 2x2 +x x5+2x6+x ≥150 x1 　 +x3+3x x6+3x7+5x8≥100 xi  0 (i =1,…,8)，且为整数

10 问：如何安排运输，使运输费用最小？ 例4：运输问题 B1 B2 B3 B4 总产量 A1 1.5 2 0.3 3 100 A2 7 0.8
冶炼厂 矿山 B1 B2 B3 B4 总产量 A1 1.5 2 0.3 3 100 A2 7 0.8 1.4 80 A3 1.2 2.5 50 总需求量 70 30 230 问：如何安排运输，使运输费用最小？

11 解：设xij为第i个矿山运到第j个冶炼厂的矿石量
MinZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24 +1.2x31+0.3x32+2x33+2.5x34 (万元) x11+x12+x13+x14=100 x21+x22+x23+x24=80 x31+x32+x33+x34=50 x11+x21+x31=50 x12+x22+x32=70 x13+x23+x33=80 x14+x24+x34=30 xij≥0(i=1,2,3。　j=1,2,3,4) 第i个矿山的产量 第j个冶炼厂的需求量

12 例5：投资方案选择问题（0－1规划） 方案 序号 技改方案内容 决策 变量 投资（万元） 年收益(万元) 第一年 第二年 1
更新旧装置，提高炼油能力500桶/天 x1 200 100 2 建造新装置，提高炼油能力1000桶/天 x2 300 150 3 往新厂建输油管，提高炼油能力100桶/天 x3 50 4 往老厂建输油管，提高炼油能力50桶/天 x4 70 30 5 增加槽车运输能力，能提高出油20桶/天 x5 40 20

13 解：1）确定决策变量：方案的选择只有两种状态，选或不选，设xj（j=1,…,5）为第j方案的取舍，有：
又要求：方案1和2只能选择其中一种，不能兼而实现，并且，选择方案2，则方案3必须与2同时选择，或者都不选择。 现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。要求技改后，至少增加出油能力500桶/天，但又不得超过1100桶/天，确定该公司总经济效益最大的投资方案。 解：1）确定决策变量：方案的选择只有两种状态，选或不选，设xj（j=1,…,5）为第j方案的取舍，有： 2）目标函数： max Z=100x1+200x2+50x3+30x4+20x5

14 3) 约束条件：（投资总额约束（第一、二年），生产能力增加约束，方案制约约束，变量的取舍限制。
200x1+300x2+150x3+100x4+50x5≤650　（万元） 200x1+150x2+50x3+70x4+40x5≤460 500x1+1000x2+100x3+50x4+20x5≥500 500x1+1000x2+100x3+50x4+20x5≤1100 x1+x2≤1 -x2+x3=0 xj=1或0 (j=1,…5)

15 例6：人员分派问题数模（0－1规划） A B C D 甲 0.6 0.2 0.3 0.1 乙 0.7 0.4 丙 0.8 1.0 丁 0.5
工作 人员 A B C D 甲 0.6 0.2 0.3 0.1 乙 0.7 0.4 丙 0.8 1.0 丁 0.5 每项工作只能由一个人承担，每人做每项工作的工作效率如上表所示，现在怎样安排工作使总的效率最大。

16 解：设xij为第i个人做第j项工作，（xij=1或0）
Max Z＝0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x x31+x32+0.7x33+0.3x x41+0.7x42+0.5x43+0.4x44 x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x43=1　 x14+x24+x34+x44=1 xij=1或0　(i=1,….,4。　j=1,…,4） 每个人只做一项工作 每一项工作都有人做

17 线性规划建模小结 线性规划的共同点： 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件
    要解决的问题的目标可以用数值指标反映     对于要实现的目标有多种方案可选择 有影响决策的若干约束条件 线性规划建立模型步骤：   确定一组决策变量   确定目标函数   确定对决策变量的约束条件

18 作业：现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：
该企业计划用于此项广告宣传的经费预算是80万元，此外要求： 至少有200万人次妇女接触广告宣传； 电视广告费用不得超过50万元, 电视广告至少占用三个单元一般时间和两个单元黄金时间, 广播和报纸广告单元均不少于5个单元而不超过10个单元。 　　 试为该企业制定广告计划，使得广告所接触的未来顾客总数尽可能多，建立线性规划数学模型。 项目 电 视 广 播 报 纸 一般时间 黄金时间 每个广告单元的费用(元) 每个广告单元所接触的顾客数(万人) 每个广告单元所接触的女顾客数(万人) 4000 40 30 7000 90 3000 50 20 1500 10

19 §5.2 线性规划的图解法 一、图解法求最优解的步骤
§5.2　线性规划的图解法 一、图解法求最优解的步骤 对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。 思路：在直角坐标系中，描绘出约束条件和变量限制的公共区域，然后通过观察确定符合目标要求的变量的取值。  求解例1中的生产计划问题：

20 目标函数变形得： 目标函数等值线  可行解域 1、绘出约束方程的图形 2、确定可行解域 3、绘出目标函数图形 4、确定最优解及目标函数值
② ③ ① ④ x2 ④ Q8 Q4 目标函数变形得：  目标函数等值线 Q3 60  Q7 最优解 30   Q2(75,15)  ④ Q5 Q6     Q1 80 90 O 70 x1 ② ① 可行解域 ③

21 几个概念： 可行解：满足线性规划所有约束条件（含约束方程与变量约束）的点。 可行解域：所在可行解的集合。
最优解：使目标函数得到极值的可行解。最优解包括：唯一最优解和无穷多最优解。 等值线：具有相同目标函数值的直线。 法向量(梯度):由目标函数系数组成的与等值线垂直的向量。

22 Max Z=x1+2x2 x1+x2≤6 x1+2x2≤8 x2≤3 xi≥0(i=1,2) 二、二维线性规划问题解的形式 1、唯一最优解
2、无穷多个最优解 Max Z=x1+2x2 x1+x2≤6 x1+2x2≤8 x2≤3 　 xi≥0(i=1,2) 6 可行解域 4 Q3(2,3) 3 Q2(4,2) C(1,2) 目标函数的等值线 x1 6 8

23 3、有可行解但无最优解 max Z=x1+x2 -2x1+x2≤4 x1-x2≤2 x1,x2≥0　 可行解域 x2 (1,1) 4 -2 2 x1 -2

24 4、无可行解 Min　Z＝x1+2x2 s.t. x1+x2≤1 2x1+x2≥4 x1,x2≥0 可行域为空集，无可行解! x2 4 (1,2) 1 1 2 x1

25 可行解域凸多边形有若干个顶点，顶点的个数是有限的。
三、线性规划的几何意义 线性规划的可行解域为凸多边形（凸集）。 可行解域凸多边形有若干个顶点，顶点的个数是有限的。　 线性规划问题若存在最优解，则最优解必可在其可行域的某一顶点上得到。  O x1 x2 Q2(75,15) 60 ② ③ ④ ① 最优解 Q1 Q3 Q4 Q5 Q6 Q7 Q8

26 四、单纯形法原理　 　找可行解域顶点的计算方法，但不是计算所有的顶点，而是从凸集的一个顶点出发，沿着凸集的边缘逐个验算所遇到的顶点，直到找到目标函数为最优的顶点为止。如从O→ Q1→ Q2或从O→ Q4→ Q3 → Q2 。 x2 ④ Q8 Q4  Q3 60  Q7 最优解 Q2(75,15)  ④ Q5 Q6    O Q1 x1 ② ①

27 §1.3 单纯形法原理 §5.3 线性规划标准型和规范型 一、线性规划的标准型 1、一般形式： ①约束方程均为等式方程。
§1.3　单纯形法原理 §5.3　线性规划标准型和规范型 一、线性规划的标准型 ①约束方程均为等式方程。 ②右边常数bi为正数。 ③所有变量均为非负变量。 ④目标函数求max 1、一般形式：

28 或写成累加和形式： 标准型的一般形式

29 或写成矩阵形式： 其中：

30 2、化线性规划问题为标准型 (1) 约束条件为等式 ①约束方程为“≤“号，
　在方程式的左端“＋”一个变量（变量≥0，称为松驰变量），原不等式化为等式约束。 ②约束方程为“≥”号 　在方程式的左端“－”一个变量（变量≥0，称为剩余变量），原不等式化为等式约束。

31 （2）变量非负约束 若xk为无约束变量（即可≥0，也可≤0），引进两个变量xk’,xk”（均≥0），令xk=xk’－xk”。在规划模型中去掉xk这个变量。 （3）约束方程右边常数非负约束 在方程两边同时乘以（-1）使得约束方程右边常数变为非负

32 例1：把下面的线性规划模型化为标准型： 标准型为：

33 (2)在第一个约束不等式≤号左端加上松驰变量x6
例2：把下面的线性规划模型化为标准型： (1)　用x4－x5替换x3，其中x4，x5≥0 (2)在第一个约束不等式≤号左端加上松驰变量x6 (3)在第二个约束不等式左边减去松驰变量x7 (4)令D＝－Z,把求min Z化成max D 得到该问题的标准型为：

34 二、线性规划的规范型 1．基、基变量与非基变量 要用单纯形法求解线性规划数学模型，还需要把数学模型化成规范型。 设线性规划模型的标准型：
　　要用单纯形法求解线性规划数学模型，还需要把数学模型化成规范型。 1．基、基变量与非基变量 设线性规划模型的标准型： 基：设A是约束方程组的m×n维系数矩阵，B是矩阵A中m阶方阵（行列式的值不为0），则称B是线性规划问题的一个基。 基变量与非基变量：与基B对应的变量为基变量。其余变量为非基变量。

35 例1： 　　请列举出其中的三个基及对应的基变量与非基变量。 解：从约束系数矩阵可看出，该模型的基不超过 个。 对应的基变量为x3,x4,x5,非基变量为x1,x2。

36 对应的基变量为x1,x3,x4，非基变量为x2,x5。 对应的基变量为x1,x2,x3，非基变量为x4,x5。

37 2．基本解和基本可行解 基本解：对某一确定的基，令非基变量等于0，可求出m个约束方程的基变量的值，则这组解称为基本解。
　2．基本解和基本可行解 基本解：对某一确定的基，令非基变量等于0，可求出m个约束方程的基变量的值，则这组解称为基本解。 基本可行解：若基本解还满足决策变量非负要求，则这组基本解称为基本可行解（也称基可行解）。

38 对基B1来说，令非基变量 ，则可以得到一个基本解 因为 ，故 是基可行解。 对基B2来说，令非基变量 ，则可以得到一个基本解 因为 ，故 也是基可行解。

39 对基B3来说，令非基变量 ，则可以得到一个基本解 因为 ，故 不是基可行解。 对基B4来说，令非基变量 , 则可得基本解 因为 ，故 也不是基可行解。

40 3．基可行解与可行解域顶点的关系 X(1)对应原点O, X(2)对应顶点Q1, X(3) 对应Q7. X(4) 对应?  x2 ④ Q8
　3．基可行解与可行解域顶点的关系 x2 ④ Q8 Q4  Q3 60 X(1)对应原点O, X(2)对应顶点Q1, X(3) 对应Q7.  Q7 最优解 X(4) 对应? Q2(75,15)  ④ Q5 Q6    O Q1 x1 ② ①

41  非基变量 基变量 基本解X＝( x1,x2 x3,x4, x5)T 对应点 x1,x2 x3,x4, x5
O x2,x5 x1,x3, x4 (80,0,300,50,0)T Q1 x2,x4 x1,x3, x5 (90,0,270,0,-90)T Q5 x4,x5 x1,x2, x3 (75,15,180,0,0)T Q2 … x2 ④ Q8 Q4  Q3 60 ①  Q7 最优解 ② ③  Q2(75,15) Q5 Q6 x1    Q1 80 90 O ③ ② ①

42 定理1：线性规划的基本可行解对应于可行解域的顶 点。
定理1：线性规划的基本可行解对应于可行解域的顶 点。　 　　从定理1和单纯形的几何意义知，用单纯形法寻求最优解，就可从基本可行解（顶点）出发，在基本可行解（顶点）之间变换，如果L.P.有最优解，则最优解一定可在某一基本可行解（顶点）上得到。这个方法可用来求有任意多个变量的线性规划模型！ x2 ④ Q8 Q4  Q3 60 最优解  Q7 Q2(75,15)  ④ Q5 Q6    O Q1 x1 ② ① ③

43 4、线性规划的规范型 规范型条件： ①已是标准型； ②含单位基； ③目标函数用非基变量表示。 例1：
①已是标准型；　 ②含单位基；　 ③目标函数用非基变量表示。 例1： 得初始基本可行解：X(1）=(0,0,540,450,720) T,Z=0。 特点（1）基变量的值刚好是约束方程右边的常数； 　　（2）目标函数Z的值就是目标函数表达式中的常数。

44 可把模型化成以基变量系数矩阵为单位阵的规范型：
若取基变量x3,x4,x1,则基解及目标函数值？ 可把模型化成以基变量系数矩阵为单位阵的规范型： ， 得到基本可行解：

45 §5.4 单纯形法步骤 引例1：求解下列线性规划模型的最优解 ① ② ③ 解：1、确定初始基可行解 取B1＝（P3 P4 P5）＝I，
§5.4　单纯形法步骤 引例1：求解下列线性规划模型的最优解 ① ② ③ 解：1、确定初始基可行解 取B1＝（P3　P4　P5）＝I， 令非基变量x1,x2=0，得 X(1)＝（0,0,540,450,720）T， Z(1)＝0；（解的含义？） 从规范型出发

46 2、判定解是否最优 目标函数　Max Z＝0+70x1+30x2 检验数：用非基变量表达的目标函数中变量前的系数Rj（判别数或检验数）。 当x1从0↗或x2从0↗， Z从0↗，∴ X(1) 不是最优解 3、由一个基可行解→另一个基可行解。 　(1) 确定入基变量 可选Rj＞0的任一变量入基。（意义？）一般地，选择max{Rj}的变量入基，选x1从0↗，保持x2 =0   　(2)确定出基变量　

47 问题：确定入基变量x1增加的上界：从约束方程组怎样求解？
① ② ③ 在①②③中，继续令x2为非基变量，即x2 ＝0，求出当前每个基变量出基能使x1增大的上界值。即： x3=540－3x1≥0　　　 　x1≤180=540/3 x4=450－5x1≥ 　　　x1≤90=450/5 x5=720 －9x1 ≥ 　 x1≤80=720/9

48 x3=540－3x1≥0　　　 　x1≤180 x4=450－5x1≥ 　　　x1≤90 x5=720 －9x1 ≥ 　 x1≤80 θ＝min{180 ,90,80}= min{540/3 ,450/5,720/9}= 80, x5出基(变为0)，即x1的取值受第三种资源的约束。 θ规则：入基变量满足约束条件下取最大值。（大中取小） (3)　求出新的基可行解 新的基变量为x3,x4,x1，怎样求出新的基可行解？ 把模型变成以基变量的系数矩阵为单位阵的规范型。

49 本质：就是线性代数中的高斯消去法——方程组同解变形.
以基变量x3,x4,x5的系数矩阵为单位阵的规范型: 新的基变量为x3,x4,x1 （1）从出基变量x5所在的方程开始：方程两边同时除以入基变量x1的系数9，得： （2）方程①②中消去x1（入基变量）：方程③两边同时乘以某个数，加到方程①②上。 （3）目标函数中消去x1：从方程③中解出x1的值代入目标函数中： 本质：就是线性代数中的高斯消去法——方程组同解变形.

50 通过以上方程的变换，原线性规划模型等价于以下模型（得到当前基表示的规范型）：
1’、确定出新的基可行解 X(2)＝（80,0,300,50,0）T　， Z(2)＝5600； 对应图形上的Q1点。

51 2’、判定解是否最优 目标函数： ，R2=20/3, R5=-70/9 当x2从0↗，Z从5600↗，∴ X(2) 不是最优解. 3’、由一个基可行解→另一个基可行解。 (1)   确定入基变量 选择x2入基，即x2从0↗，x5 仍为0 从约束方程组求解x2的最大取值，从而确定出基变量。 同理：在①’②’③’中令x5=0，求出当前解下x2取值的上界。 ①’ ②’ ③’

52 x3=300－8x x2≤37.5 x4=50－10x2/3 x2≤15 x1=80―x2/ x2≤240 θ=min｛ 37.5，15 ，240｝＝15，x4出基 (2) 确定新基可行解： 新的基变量x3,x2,x1 把模型变成以基变量x3,x2,x1的系数矩阵为单位阵的规范型。

53 怎样把模型变成以基变量x3,x2,x1的系数矩阵为单位阵的规范型？
的系数变成1。 (2)用消元法消去方程①’③’中的x2。

54 由方程组变形得： X(3)＝（75,15,180,0,0）T， Z(3)＝5700；

55 2’’、判定解是否最优 目标函数　 非基变量的检验系数均为负数，故不能入基，否则使目标值劣化。 ——当前解为最优解。 X(3)＝（75，15，180，0，0）T　，Z(3)＝5700； 最优解判断标准： （1） 若全部检验数Rj ≤0，当前基本可行解为最优解。 （2） 若存在Rj ＞0，则当前解非最优，解可改进，寻求 更好的解。

56 小结：单纯形法求解线性规划的过程 1、  确定初始基可行解。 本题确定初始基为单位阵I，令单位阵对应的变量为基变量，可得到一个基本可行解。 规范型： AX＝b X≥0，b≥0 A中含有一单位阵。 2、最优化检验：用当前可行基的非基变量的检验数确定。 3、 从一个基本可行解到另一个基本可行解 　 ① 入基变量：由检验数确定。 　 ② 出基变量：由θ规则确定。

57 用单纯形法从另一条路径寻优？

58 §5.5 单纯形表 cj c1 c2 … cn CB XB x1 x2 … xn θ xi1 xi2 … xim －Z R1 R2 … Rn
§5.5　单纯形表 cj c c … cn CB XB x x … xn θ xi1 xi2 … xim －Z R1　 R2　 … Rn －Z0 目标函数行：常数Z0在右边。

59 主元 1、由规范型列出初始单纯形表： X(1)＝（0,0,540,450,720）T Z(1)＝0 cj 70 30 CB XB x1 x2
CB XB x1 x2 x3 x4 x5 θ 3 9 1 540 180 5 450 90 [9] 720 80 -Z 主元

60 主元 2、变换到下一单纯表（变成以新基为单位阵的规范型） 新的基变量：x3 ,x4,x1 cj 70 30 CB XB x1 x2 x3
CB XB x1 x2 x3 x4 x5 θ 8 1 -1/3 300 37.5 [10/3] -5/9 50 15 1/3 1/9 80 240 -Z 20/3 -70/9 -5600 思考：单纯形表有什么特点？ （1）基变量对应的约束方程中系数矩阵为单位矩阵。 （2）目标函数基变量的检验数为0。 （3）基可行解(？)不同，反映在原表中就是对应的基不同。 主元

61 Cj 70 30 CB x1 x2 x3 x4 x5 XB θ 表一 x3 3 9 1 540 180 x4 5 5 1 450 90 x5 9 9 3 1 720 80 -Z 70 30 x3 8 1 -1/3 300 37.5 表二 x4 10/3 1 -5/9 50 15 70 x1 1 1/3 1/9 80 240 -Z 20/3 -70/9 -5600 ?

62 3、重复以上过程直到得最优解： 思考：在单纯形表中，怎样判断LP问题已取得最优解？ 最优解判断标准： （1） 若全部检验数Rj ≤0，当前基本可行解为最优解。 （2） 若存在Rj ＞0，则当前解非最优，解可改进，寻求更好的解。

63 X*=(75,15,180, 0,0)T, Z=5700 cj 70 30 CB XB x1 x2 x3 x4 x5 b X3 3 9 1
CB XB x1 x2 x3 x4 x5 b  X3 3 9 1 540 180 X4 5 450 90 [9] 720 80 -Z 8 -1/3 300 37.5 [10/3] -5/9 50 15 1/3 1/9 240 20/3 -70/9 -5600 -12/5 3/10 -1/6 -1/10 1/6 75 -2 -20/3 -5700 X*=(75,15,180, 0,0)T, Z=5700

64 例1：求解下列线性规划模型： 解：化线性规划模型为规范型，并列出初始单纯形表： 按单纯法迭代，计算如下表，得最优解为: X=(1500,0,0,3500,0)T, Z=6000

65 Cj 4 1 5 CB XB x1 x2 x3 x4 x5 b θ x4 3 1 4 1 8000 2000 x5 2 1 4 4 1 3000 750 -Z 4 1 5 x4 1 1 -1 5000 5000 x3 1/2 1/4 1 1/4 750 1500 -Z 3/2 -1/4 -5/4 -3750 x4 -1/2 -2 1 -3/2 3500 x1 1 1/2 2 1/2 1500 -Z -1 -3 -2 -6000

66 例2： 用单纯形法求解下列线性规划数学模型　 选x1、x3、x6为基变量 　 目标函数用非基变量表示： 由 约束方程(1)(2)(3)解出 x3 = 6 - x2 + x4 - 2x5 x1 = 5 - 2x2 + 2x4 代入目标函数得： Min Z = x2 + 3x4 - 5x5 把LP化成求极大的规范型：

67 XB x1 x2 x3 x4 x5 x6 b  1 2 -2 5 － -1 6 3 8 8/3 -D 4 -3 11

68 3 2 X(3) = (0，5/2，3/2，0，1，0)T D(3) = 4，Z＝－4 XB x1 x2 x3 x4 x5 x6 b  1
-2 5 － x1 1 1 -1 2 6 3 x3 2 1 3 1 8 8/3 x6 -D 4 -3 5 11 1 2 -2 5 5/2 x1 x3 -1/3 1 -5/3 -2/3 2/3 － x5 2/3 1/3 1 1/3 8/3 4 -D 2/3 -14/3 -5/3 -7/3 x2 1/2 1 -1 5/2 x3 1/6 1 -2 -2/3 3/2 x5 -1/3 1 1 1/3 1 -D -1/3 -4 -5/3 -4 X(3) = (0，5/2，3/2，0，1，0)T D(3) = 4，Z＝－4

69 单纯形算法步骤 假设目标函数求极大MAX 1、从规范型出发，得出一个初始基可行解。按要求填入表中。
2、最优化检验：若还存在Rj>0，则当前解不是最优解。 3、解的改进： ①由检验数确定入基变量xp。(一般正系数大的变量先入基) ②确定出基变量: 确定L为出基行，则xL为换出变量。得到一个新的可行基。 4、用初等行变换方法把主元（aLp）变为1，把入基列（含其检验数）中除主元的其它元素消为零。转2.

70 讨论：单纯形表进行求解的特殊情况 （1）若最大检验数有两个或两个以上并且相等，应如何确定入基变量，理论上可任选一个非基变量入基，但在实际应用中，可采用以下法则： XB x1 x2 x3 x4 x5 b 1 2 3 9 1 540 180 60 5 450 90 720 80 240 -Z 70 　　依次选择X1和X2入基，分别计算出两组比值1和2，每组比值中分别选择最小值得80和60，两个最小值中选择最大值80，因此确定X1入基，此时目标函数值改变得最快(?)。

71 （2）原问题有解但无最优解(无界)的判断：某个Rj>0,但aij≤0(i=1,2,…m)。
例4：求解线性规划问题： 标准化 XB x1 x2 x3 x4 b 3 -2 1 2 -1 4 －Z －1 （2）原问题有解但无最优解(无界)的判断：某个Rj>0,但aij≤0(i=1,2,…m)。　　　

72 §5.6 单纯形的经济意义 一、最优决策变量的解 最优解是单纯形法的基本目标信息，在建模参数可靠的基础上，它提供最优决策方案 。
§5.6　单纯形的经济意义 一、最优决策变量的解 　　　最优解是单纯形法的基本目标信息，在建模参数可靠的基础上，它提供最优决策方案 。 二、松弛变量的解 　　单纯形表的每一个基本可行解，还包含有松弛变量的解，在最优决策条件下，松弛变量的解提供资源的剩余量。 如例2中： 最优解：X(3)＝（75，15，180，0，0）T　，Z(3)＝5700； X4 = 0， X5 = 0，表明资源B、C没有剩余，为企业的关键资源； X3 = 180，资源A还剩180个单位。 应设法提高关键资源的获得量。

73 三、检验数Rj(产品的相关价值系数)经济意义
当前方案下，非基变量Xj增加1个单位，使目标函数增大的量。 基本解：X(1)＝（0，0，540，450，720）T　，Z(1)＝0； Max Z＝70x1+30x2 基本解X(2)＝（80，0，300，50，0）T　 Z(2)＝5600； R2=20/3，而当前表中，入基变量x2可增加值为15，故当前表中x2入基，利润可增加100。

74 Cj 70 30 CB XB x1 x2 x3 x4 x5 θ x3 8 1 -1/3 300 37.5 x4 10/3 1 -5/9 50 15 70 x1 1 1/3 1/9 80 240 -Z 20/3 -70/9 -5600 从例1的第二个单纯形表来看，生产80个单位的x1，C资源全部用完，A、B资源分别剩余300和50。 生产1个单位的x2，分别需要A、B、C各9,5，3单位，由于资源总量的约束，只能少生产1/3单位的x1，所以少生产1/3单位的x1要损失的利润为： Z2＝0×8＋0×3/10+70×1/3=70/3， 故R2＝30－70/3＝20/3。

75 为了生产一单位的某产品将所需资源从原来的用途中抽出来而牺牲的利润为此种产品在此生产方案下的机会成本。（Zj为生产一单位xj产品所付出的成本。
　C2＝30，孤立地讲，生产1个单位的乙产品对市场的利润还是30，但在企业的资源约束下，在当前的生产方案下，要使x2=1，必然以少生产其它产品为代价，故在当前方案下增加1个单位的乙产品只能净得利润20/3。 为了生产一单位的某产品将所需资源从原来的用途中抽出来而牺牲的利润为此种产品在此生产方案下的机会成本。（Zj为生产一单位xj产品所付出的成本。 cj－zj表示生产1单位j产品对方案收益的增量。 　检验数Rj综合考虑了市场信息和规划方案改变对利润的影响。 　　一旦作出了生产安排，单位产品的利润增值（Rj）就可能变化， Rj能起到判别计划能否进一步改进的作用。

76 四、资源的影子（潜在）价格 1、定义： 　最优规划条件下，单位资源能够带来的目标函数增量。是反映资源最优利用的一种虚拟价格，也叫资源边际利润。 2、影子价格的计算 　　最优表中表示资源的松弛变量检验数的相反数。 Cj 3 4 CB XB x1 x2 x3 x4 x5 θ x3 1 -12/5 1 180 x2 1 3/10 -1/6 15 x1 1 -1/10 1/6 75 -Z -2 -20/3 -5700

77 X(3)＝（75，15，180，0，0）T　 根据影子价格的定义： 资源A的影子价格为0，资源B的影子价格为2，资源C的影子价格为20/3。 含义：在最优方案下，资源B增加1个单位，能使利润增加2个单位。资源C增加1个单位，能使利润增加20/3个单位。 资源A增加1个单位，不会使利润增加(A本身有剩余)。 　　资源影子价格的高低表明资源的重要性的大小，影子价格为0的资源是非关键资源，影子价格大于0的资源是关键资源。

78 3、影子价格的应用 ① 在企业内部：指出挖潜方向，影子价格高的资源潜力大，影子价格低的资源潜力小。 　问题：资源的影子价格是否是一定的？ 　　注意：随着资源可用量的不断增加，其影子价格会不断下降，当影子价格降为0时，再增加该资源的可用量,利润不会增加，此时该资源已成为非关键资源。 ②对企业外部来讲，影子价格是决定资源在市场上出售的标准： 　　当资源的市场价不低于其影子价格时，企业管理人员可以考虑出售，得到的利润与自己组织生产所得利润是一样的。 ③衡量资源的使用是否合理。 　　同一种资源在不同的地方和不同的时期，其影子价格不相同，影子价格高的说明使用合理，所以应建立动态影子价格体系，做到物尽其用。

79 §5.7 单纯形法理论分析 一、线性规划标准型的表达形式 Max Z=c1x1+ c2x2+…+cnxn
　a11x1+ a12x2+…+ a1nxn =b1 　a21x1+ a22x2+…+ a2nxn =b2 … … … … am1x1+ am2x2+…+ amnxn =bm 　xj 0(j=1,2,…,n)  ①约束方程均为等式方程。 ②所有变量均为非负变量。 ③右边常数bi为正数。 1、一般形式：

80 2、求和表达式

81 3、矩阵表达式 maxZ=CX AX=b X 0 A=(P1 P2 ……… Pn) a11 a12 ……… a1n
其中 A= a a22 ……… a2n ………………… am1 am2 ………amn maxZ=CX AX=b X 0 X1 X= X2 Xn … C=(c1 c2 …cn )

82 一、单纯形表（规范型）的一般表示 1、单纯形表的数学推导 LP的数学模型为： 不失一般性，设某一基变量为XB=(x1,x2,…xm)T，则对应此基下的约束方程组可表达为：

83 基变量的求和表达式： 把目标函数也表达成基变量和非基变量两部分的求和表达式： 把（1）式代入（2）式经整理得：

84 Zj＝∑基变量的价值系数×当前单纯形表中该变量前的系数
检验数Rj＝Cj－ Zj Zj＝∑基变量的价值系数×当前单纯形表中该变量前的系数 2、当前解的改进和最优解的确定 设检验数为： Rj＞0――解能改进的条件。 Rj≤0――最优解的确定条件。 　当存在若干个Rj＞0，一般选最大的数 实际上：可选使目标函数值Z变化最大的非基变量入基： 　　　　Z＝Z0＋Rjθ

85 ∵xp入基为正数，其它非基变量保持为零，
3、出基变量、主元素 ∵xp入基为正数，其它非基变量保持为零， 入基变量的上界值为： aip≥0，因为xp为非负的有限数，要求aip≥0 由θ规则为： 则xl行为换出行，主元为：

86 4、旋转运算 　　要得到下一单纯形表，即使入基列向量xp成为单位向量，其旋转运算方法： ①第l行（出基行）元素除以主元，使主元变为1。 ②入基列xp中除主元外的其它元素（包括检验数行）消为零。

87 例1：用公式验算引例第二个单纯形表（见表1）中目标函数的值与检验数。
CB XB x1 x2 x3 x4 x5 b  8 1 -1/3 300 37.5 [10/3] -5/9 50 15→ 70 1/3 1/9 80 240 -Z 20/3↑ -70/9 -5600 解：计算检验数： 其中ci为基变量的价值系数。 R2＝30－(0×8+ 0×10/3+ 70×1/3)=20/3 R5＝0－(0×(-1/3)+ 0×(-5/9)+ 70×1/9)＝－70/9 计算目标函数值： Z＝∑Cixi=70×80＝5600

88 二、单纯形表（规范型）的矩阵表示 max　Z=CX 　AX=b　（1） 　X≥0　　 对于线性规划模型的标准型： 　Z＝CBXB＋CNXN 　BXB＋NXN＝b (2) 设某个基可行解对应的基为B，LP模型又可表示为： 怎样得出该基对应下的单纯形表呢？ 对约束方程，两边同乘B－1得： IXB+B-1NXN=B-1b，解出：XB =B-1 b－B-1 NXN 代入目标函数，消去基变量，得： －Z＋0XB＋（CN－CBB－1N）XN＝－CBB－1b 单纯形表的矩阵表达式：

89 问题：与原模型相比， 1、基变量的系数向量如何变化？非基变量的呢？ 2、与原模型中的价值系数比较，基变量的检验数如何变化？非基变量的呢？ 3、与原模型相比，约束方程右边的常数如何变化？ 4、在当前基可行解下，目标函数值与B、CB及b的关系？

90 例1：用单纯形表的矩阵表达式计算引例中以x3,x4,x1为基变量的单纯形表。
(1)基变量的值： (2)非基变量的系数：

91 (3)非基变量的检验数： 用单纯形表的计算公式算出来的结果与用表格迭代的结果一致！ XB x1 x2 x3 x4 x5 b  8 1 -1/3 300 37.5 [10/3] -5/9 50 15→ 1/3 1/9 80 240 -Z 20/3↑ -70/9 -5600

92 例2：引例中，若知道最优基（以x3,x4,x1为基变量），最优基对应的单纯形表是否可一步求出？如何求？
XB x1 x2 x3 x4 x5 b  1 -12/5 180 3/10 -1/6 15 -1/10 1/6 75 -Z -2 -20/3 -5700

93 单纯形法基本步骤 (max型) 思考：求MIN型？ (1)、定初始基，初始基本可行解
(2)、对应于非基变量检验数Rj全≤0。 若是，停，得到最优解； 若否，转(3)。 (3)、若有Rp >0，全Pp ≤ 0，停，（Pp为入基列的系数向量） 没有有限最优解； 否则转(4) (4)、maxRj =Rp→Xp 入基变量 出基变量确定： XL为出基变量，aLp为主元。 (5)、以　　　　　为中心，换基迭代，得出新的基可行解。

94 XB x1 x2 x3 x4 x5 x6 b  1 2 -2 5 － -1 6 3 [3] 8 8/3 -D 4 -3 11 -Z -4 -5 -11

95 CB XB x1 x2 x3 x4 b c 1 1/5 2 5 d e a －Z -1 f g －Z0
练习：下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为：max Z=5x1+3x2,约束形式为≤，x3,x4为松弛变量，表中解代入目标函数后得Z＝10。 （1）求a－g 的值； （2）表中给出的解是否为最优解。 CB XB x1 x2 x3 x4 b c 1 1/5 2 5 d e a －Z -1 f g －Z0 答案：a=2,b=0,c=0,d=1,e=4/5,f=0,g=-5

96 §5.8 两阶段法与大M法 下面的线性规划模型，怎样得到一个初始基本可行解？ 标准化
一般说来，对于不是规范型的标准型，我们看不出哪组变量为基变量，可得基可行解。对于不是规范型的标准型，用单纯形法求解的办法就是添加人工变量，使标准型人为地变成规范型的形式。

97 人工变量法思想： 目的：使A中含单位基，得到模型（2）的一个基可行解，但此基可行解不是（1）的可行解。　 单纯形法是确定入基变量和出基变量的过程，(约束方程的等价变换过程)，只要人工变量全部出基，基变量中不含有人工变量，这时模型（2）的基可行解也是（1）的可行解。 如模型(2)的解： 人工变量是人为添加到原约束方程的虚拟变量，若人工变量不等于0，则不是原模型（1）的解。

98 一、两阶段法 第一阶段：不考虑原问题是否存在基可行解；给原LP模型加入人工变量，并构造仅含有人工变量的目标函数，实现极小化。
如xn+1,xn+2,…xn+m为加入的人工变量，则新的目标函数为： min W= xn+1＋xn+2＋…xn+m 然后用单纯形法求解上述模型，若得到W=0，这说明原问题存在基可行解，可以进入第二阶段计算。否则，原问题无可行解，应停止计算。 第二阶段也分2种情形——1)无人工变量作为基变量，直接进入第二阶段；2)有人工变量为0作为基变量，该行约束冗余，可以丢掉，在进入第二阶段.

99 第一阶段，构造新的目标函数：min w=x6
cj 1 XB x1 x2 x3 x4 x5 x6 b θ 1 x6 2 1 -1 1 6 3 2 x3 1 1 1 -1 4 4 -Z -2 -1 1 x1 1 1/2 -1/2 1/2 3 6 x3 1/2 1/2 1 1/2 -1 -1/2 1 2 -Z 1

100 第二阶段：换回原来的目标函数 max z=－10x1－8x2－7x3 cB cj -10 -8 -7 XB x1 x2 x3 x4 x5 b
教材例 cB cj -10 -8 -7 XB x1 x2 x3 x4 x5 b θ -10 x1 1 1/2 -1/2 3 6 -7 x3 1/2 1/2 1 1/2 -1 1 2 -Z 1/2 -3/2 -7 -10 x1 1 -1 -1 1 2 -8 x2 1 2 1 -2 2 -Z -1 -2 -6 36

101 解：第一阶段：希望人工变量等于零，故构造仅含人工变量的目标函数，并要求实现最小化。
把标准型化为规范型，如右边示： x6, x7为人工变量。 解：第一阶段：希望人工变量等于零，故构造仅含人工变量的目标函数，并要求实现最小化。 用单纯形法求解模型(2)，若人工变量x6，x7　能全部出基，变成非基变量，则W＝0，同时原问题也存在一个可行基，进入第二阶段的运算，否则原问题无可行解。

102 cj 1 1 CB XB x1 x2 x3 x4 x5 x6 x7 b θ 1 x6 1 1 -1 1 2 2 1 x7 -1 [1] -1 1 1 1 x5 1 1 3 3 -W -2 1 1 -3 1 x6 [2] -1 1 1 -1 1 1/2 x2 -1 1 -1 1 1 - x5 1 1 1 -1 2 2 -W -2 1 -1 2 -1 x1 1 -1/2 1/2 1/2 -1/2 1/2 x2 1 -1/2 -1/2 1/2 1/2 3/2 x5 1/2 1/2 1 -1/2 -1/2 3/2 -W 1 1

103 第二阶段：将第一阶段计算得到的最终表，去掉人工变量，将目标函数换回原问题的目标函数，并用非基变量表示目标函数。（此时原问题已变换成规范型）

104 5/2 -3/2 -1/2 -Z 3 3/2 1 1/2 x5 - x2 -2 [1/2] x1 θ b x4 x3 XB CB cj 4 -2 3 -Z 1 [1] -1 x5 - 2 x2 x4 6 2 1 -Z -1 x3 3 x2 -2 x4

105 例3.用两阶段单纯形法求解线性规划 解：标准形式为

106 在第一、三约束方程中加入人工变量x6、x7后，构造第一阶段问题
用单纯形法求解，得到第一阶段问题的计算表格

107 Cj 1 b CB XB x1 x2 x3 x4 x5 x6 x7 －4 2 3 －1 －2 [1] 4 10 1→ Rj －2↑ －6 －3 [5] 3→ 8 6 －5↑ －6/5 3/5 －2/5 －1/5 31/5 11/5

108 最优解为 最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解,即第二阶段问题为

109 用单纯形法计算得到下表 检验数λj≤0,j=1,2,…,5，最优解与最优值 Cj 3 2 －1 b CB XB x1 x2 x3 x4 x5
b CB XB x1 x2 x3 x4 x5 －6/5 [3/5] －2/5 1 －1/5 3/5 31/5→ 11/5 Rj 5↑ 5/3 2/3 13 31/3 19/3 －5 －25/3 检验数λj≤0,j=1,2,…,5，最优解与最优值

110 注：在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检验数，必须换成原问题的检验数，用代入法或消元法计算。
另外，即使第一阶段最优值w=0，只能说明原问题有可行解，第二阶段问题不一定有最优解，即原问题可能无界。 例4：用两阶段法求解下列线性规划。

111 加入松驰变量x3、x4化为标准型 第一阶段问题为

112 Rj≥0,得到第一阶段的最优解X=(2,0,0,0,2)T，最优目标值w=2≠0，x5仍在基变量中,从而原问题无可行解。
用单纯形法计算如表 Cj 1 b CB XB x1 x2 x3 x4 x5 [3] －2 －1 6→ 4 Rj  －1↑ 2 1/3 －7/3 －1/3 7/3 Rj≥0,得到第一阶段的最优解X=(2,0,0,0,2)T，最优目标值w=2≠0，x5仍在基变量中,从而原问题无可行解。 去掉冗余约束的例子参阅教材P148。

113 二、大M法： 　基本思想：对约束方程添加人工变量，化成规范型；设定人工变量在原目标函数中的系数为大M，（对于目标为min型）或－M（对于目标为max）,M假定为任意大的正数。 （1） （2） 　　人工变量不出基（＝0），阻碍项值趋近于很大，目标函数不可能实现极大(小)化。

114 cj -10 -8 -7 -M XB x1 x2 x3 x4 x5 x6 b θ -M x6 2 1 -1 1 6 3 -7 x3 1 1
-M XB x1 x2 x3 x4 x5 x6 b θ -M x6 2 1 -1 1 6 3 2 -7 x3 1 1 1 -1 4 4 -Z 2M-3 M-1 -M -7 6M+28 -10 x1 1 1/2 -1/2 1/2 3 6 -7 x3 1/2 1/2 1 1/2 -1 -1/2 1 2 -Z 1/2 -3/2 -7 1.5-M -10 x1 1 -1 -1 1 1 2 -8 x2 1 2 1 -2 -1 2 -Z -1 -2 -6 36

115 例6：用大M单纯形法求解下列线性规划 解：首先将数学模型化为标准形式

116 式中x4、x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入―Mx6―Mx7一项，得到大M单纯形法数学模型
再用前面介绍的单纯形法求解，见下表所示

117 Cj 3 2 －1 －M b CB XB x1 x2 x3 x4 x5 x6 x7 －M 0 －4 1 －2 [1] 4 10 1→ Rj 3－2M 2+M -1+2M↑ －6 －3 [5] 3→ 8 5－6M 5M↑ －6/5 [3/5] －2/5 －1/5 3/5 31/5→ 11/5 5↑ 5/3 2/3 13 31/3 19/3 λj －5 －25/3

118 因为λj≤0，j=1,2,…,5,并且x6，x7为非基变量，所以最优解
例7：用大M单纯形法求解下列线性规划

119 加入松驰变量x3、x4化为标准型 在第二个方程中加入人工变量x5，目标函数中加上Mx5一项，得到

120 用单纯形法计算如下表所示 Cj 5 －8 M b CB XB x1 x2 x3 x4 x5 [3] 1 －2 －1 6→ 4 Rj 5-M↑ －8+2M 1/3 －7/3 －1/3 2 -29/3+7/3M -5/3+1/3M 表中λj≥0，j=1，2，…，5，从而得到最优解X=(2，0，0，0，2)T，Z=10+2M。但最优解中含有人工变量 x5≠0说明这个解是伪最优解，是不可行的，因此原问题无可行解。

121 与例4中用两阶段方法的结果相同。 无可行解的判断 （1）大M法求解时，最优解中含有不为零的人工变量，原问题无可行解。 （2）两阶段法计算时，当第一阶段的最优值w≠0时，原问题无可行解。

122 §5.9　LP规划问题解的讨论 从最优单纯形表中判断解的性质（Max型） 1、唯一最优解 条件： ①Rj＜0　（非基变量的检验数小于0）

123 2、 无穷多个最优解 条件：当前基可行解是最优解，且还具有无穷多最优解，只需判断有两个基可行解为最优解就可以了。 ①RN≤0　 ③RN中至少有一个等于0，设RP＝0

124 Cj 1 2 CB XB x1 x2 x3 x4 x5 b’ θ 1 x1 1 2 -1 4 2 2 x2 1 -1 1 2 － x5 [1] -1 1 1 1 -Z -1 -8 x1 x2 x3 2 3 1 -Z -8 两个最优基本可行解，分别为： 最优解的一般表达式？

125 3、无界解 ②RN中存在大于0的检验数（对于max型），即可入基。 （表明当xp作为入基变量时，对xp的θ值取值无上限限制。）

126 4、无可行解 即　：首先不能化成规范型，用添加人工变量的方法，再用两阶段法或大M法做，如果人工变量不能出基，则无可行解。在单纯形表中即表现为： ②RN≤0　 ③基变量中含有人工变量（且不等于0，即④　） ④Xl>0。

127 线性规划的其他重要算法 单纯形算法——(1947年美国人G.B.Dantzig提出; 是近100年来最成功的10个算法之一。尽管如此，其复杂度是指数级的——有人举出实例，单纯形算法最坏情况下可能需要2n次转轴运算！) 椭球算法 Karmarkar方法 内点法(<n3)

128 用MATLAB解线性规划 ——优化工具箱中linprog 1、模型： 命令：x=linprog(c, A, b)
2、模型：min z=c’X 命令：x=linprog(c, A, b, Aeq, beq) 注意：若没有不等式： 存在，则令A=[ ]，b=[ ].

129 3、模型：min z=cX VLB≤X≤VUB 命令：[1] x=linprog(c, A, b, Aeq, beq,VLB, VUB) [2] x=linprog(c, A, b, Aeq, beq, VLB, VUB, X0 ) 注意：[1] 若没有等式约束: , 则令Aeq=[ ], beq=[ ]. [2]其中X0表示初始点 4、命令：[x,fval]=linprog(…) 返回最优解ｘ及ｘ处的目标函数值fval. 5、命令：[x,fval, flag]=linprog(…) 返回最优解ｘ及ｘ处的目标函数值fval以及有无解标志；

130 求解 例 任务分配问题： 某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？ 要求 车床类 型 单位工件所需加工台时数 可用台时数 单位工件的加工费用 工件1 工件2 工件3 甲 0.4 1.1 1.0 800 13 9 10 乙 0.5 1.2 1.3 900 11 12 8 设在甲车床上加工工件1、2、3的数量分别为x1, x2, x3, 在乙车床上加工工件1、2、3的数量分别为x4, x5, x6.

131 例3 引例1的解答 问题 改写为： ， S.t.

132 [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)
执行结果: x =[ 0.0000 ] fval = e+004 甲——600个工件2. 乙——400个工件1, 500个工件3. 最小加工费13800. 编写M文件xxgh3.m如下: f = [ ]; A = [ ]; b = [800; 900]; Aeq=[ ]; beq=[400;600;500]; vlb = zeros(6,1); vub=[]; [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)

133 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。
练习：某饲养场饲养肉用种鸡出售，设每只肉用种鸡每千克饲料营养要求：135~145g蛋白质、23~40g矿物质、100mg维生素。现有5种饲料可供选择，各种饲料每kg营养成分含量及单价如表示： 饲料 蛋白质(g)　 矿物质(g) 维生素（mg） 价格（元/kg） 1(玉米) 78 0.7 0.5 0.68 2（小麦） 114 0.6 1.0 0.72 3（米糠） 117 0.2 0.22 4（豆饼） 402 3.2 2 0.37 5（槐叶粉） 170 4.0 0.8 0.38 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。

134 作业 P ,5.2,5.3, 5.4, 5.7, 5.8, 5,9