《运筹学》复习参考资料知识点及习题_高等教育-试题.pdf

《《运筹学》复习参考资料知识点及习题_高等教育-试题.pdf》由会员分享，可在线阅读，更多相关《《运筹学》复习参考资料知识点及习题_高等教育-试题.pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一部分 线性规划问题的求解 一、两个变量的线性规划问题的图解法：概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。图解法：图解法采用直角坐标求解：x1横轴；x2竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题：（只要求下面这些有唯一最优解的类型）例 1：某厂生产甲、乙两种产品，这两种产品均需在 A、B、C 三种不同的设备上加工，每种产品在不同设备上加工所需的

2、工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：A B C 利润（万元）甲 乙 3 5 9 9 5 3 70 30 有效总工时 540 450 720 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？（此题也可用“单纯形法”或化“对偶问题”用大 M 法求解）设 备 消 耗 产 品 解：设 x1、x2为生产甲、乙产品的数量。max z=70 x1+30 x2 s.t.072039450555409321212121xxxxxxxx，可行解域为oabcd0，最优解为 b 点。由方程组 72039450552121xxxx

3、解出x1=75，x2=15 X*=21xx=（75，15）T max z=Z*=70 75+30 15=5700 、可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例

4、用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形例 2：用图解法求解 max z=6x1+4x2 s.t.0781022122121xxxxxxx，解：可行解域为oabcd0，最优解为 b 点。由方程组 81022121xxxx 解出x1=2，x2=6 X*=21xx=（2，6）T max z=6 2+4 6=36 、可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例

5、某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形例 3：用图解法求解 min z=3x1+x2 s.t.08212523421212121xxxxxxxx，解：可行解域为bcdefb，最优解为 b 点。由方程组12524211xxx 解出 x1=4

6、，x2=54 X*=21xx=（4，54）T min z=3 4+54=1151 、可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为

7、点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入 3；3、根据L规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入 3，直至最优解。具体做法（可化归标准型的情况）：设已知 max z=c1x1+c2x2+cnxn s.t.njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn，.210.221122222121

8、11212111 对第 i 个方程加入松弛变量 xn+i，i=1，2，m，得到 njxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn，.210.2211222222121111212111 列表计算，格式、算法如下：可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件

9、限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形CB XB b c1 c2 cn+m L x1 x2 xn+m cn+1 xn+1 b1 a11 a12 a1 n+m c n+2 xn+2 b2 a21 a22 a2 n+m .cn+m xn+m bn am1 am2 am n+m z1 z2 zn+m 1 2 n+m 注：zj=cn+1 a1j+cn+2 a2j+cn+m amj=miij

10、inac1，（j=1，2，n+m）j=cjzj,当j 0 时，当前解最优。注：由 maxj确定所对应的行的变量为“入基变量”；由L=0minikikiiaab确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为 1，此列其余元素变为 0。例 1：用单纯形法求解（本题即是本资料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解）max z=70 x1+30 x2 s.t.072039450555409321212121xxxxxxxx，解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z=70 x1+30 x2+0 x3+0 x4+0 x5 可行解的

11、全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形s

12、.t.5,.,2,1,0720394505554093521421321jxxxxxxxxxxj 列表计算如下：CB XB b 70 30 0 0 0 L x1 x2 x3 x4 x5 0 x3 540 3 9 1 0 0 540/3 =180 0 x4 450 5 5 0 1 0 450/5 =90 0 x5 720（9）3 0 0 1 720/9 =80 0 0 0 0 0 70 30 0 0 0 0 x3 300 0 8 1 0-1/3 300/8 =37.5 0 x4 50 0（10/3）0 1 -5/9 50/10/3 =15 70 x1 80 1 1/3 0 0 1/9 80/1/

13、3 =240 70 70/3 0 0 70/9 0 20/3 0 0 70/9 0 x3 180 0 0 1 12/5 1 30 x2 15 0 1 0 3/10-1/6 70 x1 75 1 0 0-1/10 1/6 5700 70 30 0 2 20/3 0 0 0-2 20/3 X*=（75，15，180，0，0）T max z=70 75+3015=5700 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两

14、种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形例 2：用单纯形法求解 max z=7x1+12x2 s.t.0300103200543604921212121xxxxxxxx，解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z=7x1+12x2+0 x3

15、+0 x4+0 x5 s.t.5,.,2,1,03001032005436049521421321jxxxxxxxxxxj 列表计算如下：可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最

16、优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形 CB XB b 7 12 0 0 0 L x1 x2 x3 x4 x5 0 x3 360 9 4 1 0 0 360/4=90 0 x4 200 4 5 0 1 0 200/5=40 0 x5 300 3（10）0 0 1 300/10=30 0 0 0 0 0 7 12 0 0 0 0 x3 240 78/10 0 1 0-2/5 240/78/10=2400/78 0 x4 50（5/2）0 0 1-1/2 50/5/2=20 12 x2 30

17、3/10 1 0 0 1/10 30/3/10=100 18/5 12 0 0 6/5 17/5 0 0 0 6/5 0 x3 84 0 0 1 78/25 29/25 7 x1 20 1 0 0 2/5-1/5 12 x2 24 0 1 0 3/25 4/28 428 7 12 0 34/25 11/35 0 0 0 34/25 11/35 X*=（20，24，84，0，0）T max z=7 20+1224=428 三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：若为“”，则加松弛变量，使方程成为“”；若为“”，则减松弛变量，使方程成为“”。我们在前面标准型中是规定目标函数求极

18、大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例

19、用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形由目标函数 min z=njjjxc1变成等价的目标函数 max（z）=njjjxc1)(令z=z/，min z=max z/2、等式约束大 M 法：通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为M，M 是很大的正数，从原理上理解又称为“惩罚系数”。（课本 P29）类型一：目标函数仍为 max z，约束条件组与。例 1：max z=3x1+5x2 s.t.018231224212121xxxxxx，解：加入松弛变量 x3，x4，得到等效的标准模型：max z=3x1+5x2 s.t.4,3,2

20、,1,018231224214231jxxxxxxxj 其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量 x5，得到：max z=3x1+5x2Mx5 s.t.5,.,2,1,0182312245214231jxxxxxxxxj 单纯形表求解过程如下：可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三

21、种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形CB XB b 3 5 0 0 M L x1 x2 x3 x4 x5 0 x3 4（1）0 1 0 0 4/1=4 0 x4 12 0 2 0 1 0 M x5 18 3 2 0 0 1 18/3=6 3M 2M 0 0 M 3M3 52M 0 0 0 3 x1 4 1 0 1 0 0 0 x4 12 0 2 0 1 0 1

22、2/2=6 M x5 6 0（2）3 0 1 6/2=3 3 2M 33M 0 M 0 5 33M 0 0 3 x1 4 1 0 1 0 0 4/1=4 0 x4 6 0 0（3）1 1 6/3=2 5 x2 3 0 1 3/2 0 1/2 3/(2/3)=9/2 3 5 9/2 0 5/2 0 0 9/2 0 M5/2 3 0 5 x1 2 1 0 0 1/3 1/3 x3 2 0 0 1 1/3 1/3 x2 6 0 1 0 1/2 0 36 3 5 0 3/2 1 0 0 0 3/2 M1 X*=（2，6，2，0）T 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直

23、角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形max z=3 2+56=36 类型二：目标函数 min z，约

24、束条件组与。例 2：用单纯形法求解 min z=4x1+3x2 s.t.012231642212121xxxxxx，解：减去松弛变量 x3，x4，并化为等效的标准模型：max z/=4x13x2 s.t.4,3,2,1,012231642421321jxxxxxxxj 增加人工变量 x5、x6，得到：max z/=4x13x2Mx5Mx6 s.t 6,.,2,1,01223164264215321jxxxxxxxxxj 单纯形表求解过程如下：可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定

25、它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形 CB XB b 4 0 0 M M L x1 x2 x3 x4 x5 x6 M x5 16 2（4）1 0 1 0 16/4=4 M x6 12

26、3 2 0 1 0 1 12/2=6 5M 6M M M M M 5M4 6M3 M M 0 0 3 x2 4 1/2 1 1/4 0 1/4 0 4/1/2=8 M x6 4（2）0 1/2 1 1/2 1 4/2=2 2M3/2 3 3/4M/2 M M/23/4 M 2M5/2 0 M/23/4 M 3/43M/2 0 3 x2 3 0 1 3/8 1/4 3/8 1/4 4 x1 2 1 0 1/4 1/2 1/4 1/2 17 4 3 1/8 5/4 1/8 5/4 0 0 1/8 5/4 M1/8 M5/4 X*=（2，3，0，0）T min z=max z/=（17）=17 可行

27、解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯

28、形四、对偶问题的解法：什么是对偶问题？1、在资源一定的条件下，作出最大的贡献；2、完成给定的工作，所消耗的资源最少。引例（与本资料P2例1“图解法”、P7例1“单纯形法”同）：某工厂生产甲、乙两种产品，这些产品均需在 A、B、C 三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：A B C 利润（万元）甲 乙 3 5 9 9 5 3 70 30 有效总工时 540 450 720 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？解：原问题 设 x1、x2为生产甲、乙产品的数

29、量。max z=70 x1+30 x2 s.t.072039450555409321212121xxxxxxxx，将这个原问题化为它的对偶问题 设 备 消 耗 产 品 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为

30、生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形设 y1、y2、y2分别为设备 A、B、C 单位工时数的加工费。min w=540y1+450y2+720y3 s.t.32103035970953321321，iyyyyyyyi 用大 M 法，先化为等效的标准模型：max w/=540y1450y2720y3 s.t.5,.,2,1,0303597095353214321jyyyyyyyyyj 增加人工变量 y6、y7，得到：max z/=540y1450y2720y3

31、My6My7 s.t 5,.,2,1,030359709537532164321jyyyyyyyyyyyj 大 M 法单纯形表求解过程如下：可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为

32、最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形 CB XB b 540 450 720 0 0 M M L y1 y2 y3 y4 y5 y6 y7 M y6 70 3 5 9 1 0 1 0 70/3 M y7 30（9）5 3 0 1 0 1 30/9=10/3 12M 10M 12M M M M M 12M540 10M450 12M720 M M 0 0 M y6 60 0 10/3（8）1 1/3 1 1/3 60/8=2.5 540 y1 10/3 1 5/9 1/3 0 1/9 0

33、 1/9 10/3/1/3=10 -300+10/3M-8M180 M M/3+60 M M/360 0-150+10/3M 8M-540 M M/360 0 M/3+60 720 y3 15/2 0 5/12 1 1/8 1/24 1/8 1/24 15/2/5/12=18 540 y1 5/6 1（5/12）0 1/24 1/8 1/24 1/8 5/6/5/12=2 540 572 720 135/2 475/12 135/2 75/2 0 125 0 135/2 475/12 135/2 M 75/2 M 720 450 y3 20/3 1 0 1 1/6 1/6 1/6 1/6 y2

34、 2 12/5 1 0 1/10 3/10 1/10 3/10 5700 360 450 720 75 15 75 15 180 0 0 75 15 75M 15M 该对偶问题的最优解是 y*=（0，2，320，0，0）T 最优目标函数值 min w=（5700）=5700 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润

35、以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形五、运输规划问题：运输规划问题的特殊解法“表上作业法”解题步骤：1、找出初始调运方案。即在(mn)产销平衡表上给出 m+n-1个数字格。（最小元素法）2、（对空格）求检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（闭回路法）3、对方案进行改善，找出新的调运方案。（根据检验结果选择入基变量，用表

36、上闭回路法调整即迭代计算，得新的基本可行解）4、重复 2、3，再检验、再迭代，直到求得最优调运方案。类型一：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）引例：某钢铁公司有三个铁矿和四个炼铁厂，铁矿的年产矿石量分别为 100万吨、80 万吨和 50 万吨，炼铁厂年需矿石量分别为 50 万吨、70 万吨、80 万吨和 30 万吨，这三个铁矿与四个炼铁厂的距离如下：B1 B2 B3 B4 A1 A2 A3 15 20 3 30 70 8 14 20 12 3 20 15 问：该公司应如何组织运输，既满足各炼铁厂需要，又使总的运输费用为最小（按吨.公里计）？解：用“表上作业法”求解。先用最

37、低费用法（最小元素法）求此问题的初始基础可行解：炼 铁 距 离 铁 矿 厂 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程

38、组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形 B1 B2 B3 B4 产量 Si A1 15 20 67 3 30 65 100 20 80 A2 70 8 14 44 20 80 30 20 30 A3 12 53 3 20 33 25 10 50 50 销量 dj 50 70 80 30 230 230 初始方案：Z=1520+380+7030+820+2030+350=3550（吨.公里）对的初始可行解进行迭代（表上闭回路法），求最优解：销 地 费 用 产 地 20 80 B1 B3 A1 B2 20 30 30 B1 B3 A2 B2 50 A3

39、可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的

40、单纯形 B1 B2 B3 B4 产量 Si A1 15 20 14 3 30 12 100 20 80 A2 70 53 8 14 9 20 80 50 30 A3 12 3 20 20 25 10 50 30 20 销量 dj 50 70 80 30 230 230 用表上闭回路法调整后，从上表可看出，所有检验数0，已得最优解。最优方案：Z=1520+380+850+2030+1230+320=1960（吨.公里）解法分析：如何求检验数并由此确定入基变量？有数字的空格称为“基格”、打的空格称为“空格”，标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点，出发点算0故为偶点。找出所有空格的闭回

41、路后计算它们的检验数偶点奇点ijijijcc，必须ij0，才得到最优解。否则，应选所有中正的最大者对应的变量xj为入基变量进行迭代（调整）。检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。重复以上两步，再检验、再调整，直到求得最优运输方案。类型二：供求不平衡的运输规划问题 销 地 费 用 产 地 20 80 B1 B3 A1 50 30 B2 B4 A2 30 20 B1 B2 A3 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值

42、线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形若njjmiids11，则是供大于求（供过于求）问题，可设一虚销地Bn+1，令ci,n+1=0，dn+1=njjmiids11，转化为产销平衡

43、问题。若njjmiids11，则是供小于求（供不应求）问题，可设一虚产地Am+1，令cm+1,j=0，sm+1=miinjjsd11，转化为产销平衡问题。（，2，m；，2，n）六、工作指派问题：工作指派问题的数学模型假定有 n 项工作需要完成，恰好有 n 个人每人可去完成其中一项工作，效果要好。工作指派问题的特殊解法“匈牙利法”（考！）解题步骤：1、使系数矩阵（效率矩阵）各行、各列出现零元素。作法：行约简系数矩阵各行元素减去所在行的最小元素，列约简再从所得矩阵的各列减去所在列最小元素。2、试求最优解。如能找出 n 个位于不同行不同列的零元素，令对应的xij=1，其余xij=0，得最优解，结束；

44、否则下一步。作法：由独立 0 元素的行（列）开始，独立 0 元素处画（）标记，在有（）的行列中划去（也可打*）其它 0 元素；再在剩余的 0 元素中重复此做法，直至不能标记（）为止。3、作能覆盖所有 0 元素的最少数直线集合。作法：对没有（）的行打号；对已打号的行中所有 0 元素的所在列打号；再对打有号的列中 0 元素的所在行打号；重复、直到得不出新的打号的行(列)为止；对没有打号的行画一横线，对打号的列画一纵线，这就得到覆盖所有 0 元素的最少直线数。未被直线覆盖的最小元素为cij,在未被直线覆盖处减去cij,在直线交叉处加上cij。4、重复 2、3，直到求得最优解。类型一：求极小值的匈牙利

45、法：（重点掌握这种基本问题）可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程

46、组解出二标准型线性规划问题的单纯形例 1：有甲、乙、丙、丁四个人，要派去完成 A、B、C、D 四项工作，他们完成的工时如下表：A B C D 甲 乙 丙 丁 6 12 13 4 10 3 12 14 7 14 13 16 8 8 12 10 试问：应如何分配任务可使总工时为最少？解：用“匈牙利法”求解。已知条件可用系数矩阵（效率矩阵）表示为：（cij）=10128816131471412310413126 24009670119070982 20009270115070582 2)0(00927)0(115)0(7)0(582*使总工时为最少的分配任务方案为：甲D，乙B，丙A，丁C 此时总工时

47、数 W=4+3+7+12=26 例 2：求效率矩阵 列约简 任 务 工 时 人 行约简 标号 甲 乙 丙 丁 A B C D 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为生产甲乙产品的数量可行解域为最优解为点由方

48、程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形54325645778587910的最优解。解：54325645778587910 3210120122301023 2210020112300023 221002)0(1123)0(0)0(23*所画（）0 元素少于 n，未得到最优解，需要继续变换矩阵（求能覆盖所有 0 元素的最少数直线集合）：221002)0(1123)0(0)0(23*未被直线覆盖的最小元素为cij=1,在未被直线覆盖处减去 1,在直线交叉处加上 1。1100020201200024 110

49、00202012)0(0)0(24*）（）（得最优解：0010100000010100 类型二：求极大值的匈牙利法：min z=max（z）标号 列约简 行约简 标号 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不同的设备上加工每种产品在不同设备上加工所需的工时不同这些产品销售后所能得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示备设耗消产品甲或化对偶问题用大法求解解设为

50、生产甲乙产品的数量可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出例用图解法求解解可行解域为最优解为点由方程组解出二标准型线性规划问题的单纯形（cij）（Mcij）=（bij），（cij）中最大的元素为 M max z=jijijixc=jijijixcM)(=jijijixcM)(jijijixc 第一部分到此结束 可行解的全体称为可行解域定义达到目标的可行解为最优解图解法图解法采用直角坐标求解横轴竖轴将约束条件取等号用直线绘出确定可行解域绘出目标函数的图形等值线确定它向最优解的移动方向注求极大值沿价值系数向量的正型例某厂生产甲乙两种产品这两种产品均需在三种不