第三章 整数线性规划
本章, 我们介绍三种解决整数线性规划问题的软件:
第一种: MATLAB 中的optimization toolbox 中的若干程序;
第二种: LINDO 软件;
第二种: LINGO 软件.
1. MATLAB 程序说明
程序名: intprogram, L01p_e, L01p_ie, transdetobi, biprogram
intprogram 是利用分支定界法解决整数规划问题, 是全部的整数规划问题;
L01p_e 是利用枚举法解决0-1规划问题, 变量要求全部为0或者1;
L01p_ie 是利用隐枚举法解决0-1规划问题, 变量要求全部为0或者1;
Transdetobi 是枚举法和隐枚举法中利用到的将十进制数转化为二进制数的函数;
Biprogram 是MATLAB6.5以上版本中有的求解0-1规划的函数的程序.
intprogram 执行实例1：
12
121212max 2010s.t.5424
2513
,0, f x x x x x x x x =++≤+≤≥ 且为整数
在命令窗口的程序执行过程和结果如下:
>> c=[-20,-10]; %将最大转化为最小;
>> a=[5,4;2,5];
>> b=[24;13];
>> [x,f]=intprogram(c,a,b,[0;0],[inf;inf],[],0,0.0001) % c,a,b 之后[0;0] is the value of low bound;[inf;inf] is the value of up bound;[] is the initialization;0 is the number of the equation constraints; 0.0001 is the concise rate. x =
4.0000
1.0000
f =
-90
intprogram 执行实例2: 书中例题3.3.1
在命令窗口的程序执行过程和结果如下:
>> c=[-1,-1];
>> a=[-4,2;4,2;0,-2];
>> b=[-1;11;-1];
>> [x,f]=intprogram(c,a,b,[0;0],[inf;inf],[],0,0.0001)
x =
2 2
1 1
f =
-3
L01p_e 和L01p_ie 执行实例:
123
1231231223123max 325s.t.22
44
3
46
,,01
f x x x x x x x x x x x x x x x x =-++-≤++≤+≤+≤= － 或
在命令窗口的程序执行过程和结果如下:
>> c=[3,-2,5]; %将最大转化为最小;
>> a=[1,2,-1;1,4,1;1,1,0;0,4,1];
>> b=[2;4;3;6];
>> x1=L01p_e(c,a,b);x2=L01p_ie(c,a,b); %x1表示利用枚举法解决0-1规划问题，x2表示用隐% 枚举法解决问题, 结果是一样的
>> x1
x1 =
1
>> x2
x2 =
1
biprogram 执行实例: 1234
1234341324min ()9564s.t.63529
1
f x x x x x x x x x x x x x x x =---+++≤+≤+≤-+≤ － -
在命令窗口的程序执行过程和结果如下：
the program is with the binary linear programming
Please input the constraints number of the programming m=4
m =
4
Please input the variant number of the programming n=4
n =
4
Please input cost array of the objective function c(n)_T=[-9,-5,-6,-4]'
c =
-9
-5
-6
-4
Please input the coefficient matrix of the constraints A(m,n)=[6,3,5,2;0,0,1,1; -1,0,1,0;0,-1,0,1]
A =
6 3 5 2
0 0 1 1
-1 0 1 0
0 -1 0 1
Please input the resource array of the program b(m)_T=[9,1,0,0]'
b =
9
1
Optimization terminated successfully.
x =
1
1
简单线性规划问题的几种简单解法 依不拉音。司马义（吐鲁番市三堡中学，838009） “简单的线性规划问题”属于高中数学新课程必修5，进入了高考试题，并且保持了较大的考察比例，几乎是每年高考的必考内容，也是高中数学教学的一个难点。 简单的线性规划是指目标函数只含两个自变量的线性规划。简单线性规划问题的标准型为： 1112220(0)0(0),(),0(0) m m m A x B y C A x B y C m N z Ax By A x B y C +++≥≤??++≥≤?∈=+???++≥≤?约束条件 目标函数 ， 下面介绍简单线性规划问题的几种简单解法。 1. 图解法 第一步、画出约束条件表示的可行区域，这里有两种画可行 区域的方法。 ⑴代点法：直线Ax+By+C=0（c 不为0）的某侧任取一点，把 它的坐标代入不等式，若不等式成立，则不等式表示的区域在该点的那一侧；若不成立，则在另一侧。 ⑵B 判别法：若Ｂ＞0（＜０），则不等式Ax+By+C ＞0（＜０）
表示的区域在直线Ax+By+C＝0的上方；若Ｂ＞０（＜０），则不等式Ax+By+C＜０(＞0)表示的区域在直线Ax+By+C＝0的下方。（即若B与0的大小方向跟不等式的方向相同，则可行区域是边界线的上方；若B与0的大小方向与不等式的方向相反，则可信分区域是边界线的下方） 用上面的两种方法画出可行区域是很简单，所以这里不必举例说明。 第二步、在画出的可行区域内求最优解（使目标函数取最大值或最小值的点），这个可以用下面的两种办法解决。 ⑴y轴上的截距法：若b>0，直线y a b x z b =-+所经过可行域上的点使其y轴上的截距最大（最小）时，便是z取得最大值（最 小值）的点；若b<0，直线y a b x z b =-+所经过可行域上的点使其y 轴上的截距最大（最小）时，是z取得最小值（最小值）的点（提醒：截距不是距离，截距可以取正负）。 例1．设x,y满足约束条件 x y y x y +≤ ≤ ≥ ? ? ? ? ? 1 , , , 求z x y =+ 2的最大值、最 小值。 解：如图1作出可行域，因为y的系数1大于0，目标函数z x y =+ 2表示直线y x z =-+ 2在y轴上的截距，当直线过A（1，0） 时，截距值最大z max =?+= 2102，当直线过点O（0，0）时，截距
MATLAB 求解线性规划（含整数规划和0-1规划）问题 线性规划是数学规划中的一类最简单规划问题，常见的线性规划是一个有约束的，变量范围为有理数的线性规划。如： max 712z x y =+ 9430045200s.t 310300,0 x y x y x y x y +≤??+≤??+≤??≥? 对于这类线性规划问题，数学理论已经较为完善，可以有多种方法求解此类问题。但写这篇文章的目的并不是为了介绍数学理论，我们这里主要讲解如果利用工具求解这一类线性规划问题。 最著名，同时也是最强大的数学最优化软件是LINGO/LINDO 软件包，它能够求解多种的数学规划问题，同时还提供了多种的分析能力。但LINGO 软件并不容易上手，同时，应用LINGO 的场合一般是大规模的线性规划问题，小小的线性规划完全可以不使用它。一个更受科研人员欢迎的数学软件是MATLAB ，它以功能强大而称著，并有数学软件中的“航空母舰”之称。我们这里就是要学习使用MATLAB 软件求解线性规划（含整数规划和0-1规划）问题。 为了使得不熟悉MATLAB 的人员也能够使用MATLAB 进行线性规划问题求解，本文将对MATALB 中使用到的函数和过程以及结果进行详细的分析，最后会对每一个问题都给出一个可以完全“套用”的MATLAB 程序。 我们首先从上面的线性规划问题开始，为了便于表达，将上面的式子写成矩阵形式： max 712z x y =+ 9430045200s.t 310300,0x y x y ???????? ? ??≤? ? ? ???? ? ???????≥? 于是约束就表达为了一个Ax b ≤不等式。 求解MATLAB 线性规划时，最常用的函数是linprog 函数，下面来介绍一下这个函数的使用。 打开MATLAB 帮助文档（PS:帮助文档的内容是最全的，只要你的英文过了专业8级），可以看到linprog 函数求解的是具有如下标准形式的线性规划：
多目标线性规划的若干解法及MATLAB 实现 一．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ， 12(,,,)T r Z Z Z Z = . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx = 约束条件：0 Ax b x ≤?? ≥? （3） 二．MATLAB 优化工具箱常用函数[3] 在MA TLAB 软件中，有几个专门求解最优化问题的函数，如求线性规划问题的linprog 、求有约束非线性函数的fmincon 、求最大最小化问题的fminimax 、求多目标达到问题的fgoalattain 等,它们的调用形式分别为： ①.[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) f 为目标函数系数,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为x 的下 限和上限, fval 求解的x 所对应的值。 算法原理：单纯形法的改进方法投影法 ②.[x,fval ]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub ） fun 为目标函数的M 函数, x0为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束
●教学目标 （一）教学知识点 1.线性规划问题，线性规划的意义. 2.线性约束条件、线性目标函数、可行解、可行域、最优解等基本概念. 3.线性规划问题的图解方法. （二）能力训练要求 1.了解简单的线性规划问题. 2.了解线性规划的意义. 3.会用图解法解决简单的线性规划问题. （三）德育渗透目标 让学生树立数形结合思想. ●教学重点 用图解法解决简单的线性规划问题. ●教学难点 准确求得线性规划问题的最优解. ●教学方法 讲练结合法 教师可结合一些典型例题进行讲解，学生再通过练习来掌握用图解法解决一些较简单的线性规划问题. ●教具准备 多媒体课件（或幻灯片） 内容：课本P60图7—23 记作§7.4.2 A 过程：先分别作出x=1，x-4y+3=0，3x+5y-25=0三条直线，再找出不等式组所表示的平面区域（即三直线所围成的封闭区域）.再作直线l0:2x+y=0. 然后，作一组与直线的平行的直线： l:2x+y=t,t∈R （或平行移动直线l0），从而观察t值的变化. ●教学过程 Ⅰ.课题导入 上节课，咱们一起探讨了二元一次不等式表示平面区域，下面，我们再来探讨一下如何应用其解决一些问题. Ⅱ.讲授新课 首先，请同学们来看这样一个问题.
设z =2x +y ，式中变量x 、y 满足下列条件?? ???≥≤+-≤-1255334x y x y x 求z 的最大值和最小值. 分析：从变量x 、y 所满足的条件来看，变量x 、y 所满足的每个不等式都表示一个平面区域，不等式组则表示这些平面区域的公共区域. (打出投影片§7.4.2 A) ［师］（结合投影片或借助多媒体课件） 从图上可看出，点（0，0）不在以上公共区域内，当x =0，y =0时，z =2x +y =0. 点（0，0）在直线l 0：2x +y =0上. 作一组与直线l 0平行的直线（或平行移动直线l 0)l :2x +y =t ,t ∈R . 可知，当t 在l 0的右上方时，直线l 上的点（x ,y )满足2x +y ＞0, 即t ＞0. 而且，直线l 往右平移时，t 随之增大. （引导学生一起观察此规律） 在经过不等式组所表示的公共区域内的点且平行于l 的直线中，以经过点A （5，2）的直线l 2所对应的t 最大，以经过点B （1，1）的直线l 1所对应的t 最小. 所以：z m ax =2×5+2=12, z m in =2×1+3=3. 诸如上述问题中，不等式组是一组对变量x 、y 的约束条件，由于这组约束条件都是关于x 、y 的一次不等式，所以又可称其为线性约束条件.z =2x +y 是欲达到最大值或最小值所涉及的变量x 、y 的解析式，我们把它称为目标函数.由于z =2x +y 又是关于x 、y 的一次解析式，所以又可叫做线性目标函数. 另外注意：线性约束条件除了用一次不等式表示外，也可用一次方程表示. 一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.例如：我们刚才研究的就是求线性目标函数z =2x +y 在线性约束条件下的最大值和最小值的问题，即为线性规划问题. 那么，满足线性约束条件的解（x ,y )叫做可行解，由所有可行解组成的集合叫做可行域.在上述问题中，可行域就是阴影部分表示的三角形区域.其中可行解（5，2）和（1，1）分别使目标函数取得最大值和最小值，它们都叫做这个问题的最优解. Ⅲ.课堂练习 ［师］请同学们结合课本P 64练习1来掌握图解法解决简单的线性规划问题. （1）求z =2x +y 的最大值，使式中的x 、y 满足约束条件?? ???-≥≤+≤.1,1,y y x x y 解：不等式组表示的平面区域如图所示： 当x =0,y =0时，z =2x +y =0 点（0，0）在直线l 0:2x +y =0上. 作一组与直线l 0平行的直线 l :2x +y =t ,t ∈R . 可知，在经过不等式组所表示的公共区域内的点且平行于l 的直线中，以经过点A （2，-1）的直线所对应的t 最大 .
整数线性规划理论 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型整数线性规划。目前所流行的求解整数规划的方法，往 1.2 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.3 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21min x x z += 0,0,5422121≥≥=+x x x x 其最优实数解为：4 5min ,4 5,021===z x x 。LINGO1.lg4 LINGO11.lg4 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21m i n x x z += 0,0,6422121≥≥=+x x x x 其最优实数解为：2 3min ,23,021===z x x 。 若限制整数得：2min ,1,121===z x x 。LINGO2.lg4 LINGO21.lg4 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.4 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行
线性规划问题是高考的重点，而线性规划问题具有代数和几何的双重形式，多与函数、平面向量、数列、三角、概率、解析几何等问题交叉渗透，自然地融合在一起，使数学问题的解答变得更加新颖别致． 归纳起来常见的命题探究角度有： 1．求线性目标函数的最值． 2．求非线性目标函数的最值． 3．求线性规划中的参数． 4．线性规划的实际应用． 本节主要讲解线性规划的常见基础类题型． 【母题一】已知变量x ，y 满足约束条件???? ? x ＋y ≥3，x －y ≥－1， 2x －y ≤3，则目标函数z ＝2x ＋3y 的取值范围为( ) A ．[7，23] B ．[8，23] C ．[7，8] D ．[7，25] 求这类目标函数的最值常将函数z ＝ax ＋by 转化为直线的斜截式：y ＝－a b x ＋z b ，通过求 直线的截距z b 的最值，间接求出z 的最值． 【解析】画出不等式组???? ? x ＋y ≥3，x －y ≥－1， 2x －y ≤3， 表示的平面区域如图中阴影部分所示， 由目标函数z ＝2x ＋3y 得y ＝－23x ＋z 3，平移直线y ＝－2 3 x 知在点B 处目标函数取到最小值，解方程组 ????? x ＋y ＝3，2x －y ＝3，得????? x ＝2， y ＝1，所以B (2,1)，z min ＝2×2＋3×1＝7，在点A 处目标函数取到最大值，解方程组????? x －y ＝－1，2x －y ＝3，得????? x ＝4，y ＝5， 所以A (4,5)，z max ＝2×4＋3×5＝23． 【答案】A
【母题二】变量x ，y 满足???? ? x －4y ＋3≤0，3x ＋5y －25≤0， x ≥1， (1)设z ＝y 2x －1，求z 的最小值； (2)设z ＝x 2＋y 2，求z 的取值范围； (3)设z ＝x 2＋y 2＋6x －4y ＋13，求z 的取值范围． 点(x ，y )在不等式组表示的平面区域内，y 2x －1＝12·y －0 ??? ? x －12表示点(x ，y )和????12，0连线的斜率；x 2＋y 2表示点(x ，y )和原点距离的平方；x 2＋y 2＋6x －4y ＋13＝(x ＋3)2＋(y －2)2表示点(x ，y )和点(－3,2)的距离的平方． 【解析】(1)由约束条件???? ? x －4y ＋3≤0，3x ＋5y －25≤0， x ≥1， 作出(x ，y )的可行域如图所示． 由 ????? x ＝1，3x ＋5y －25＝0，解得A ????1，22 5． 由????? x ＝1， x －4y ＋3＝0，解得C (1,1)． 由? ???? x －4y ＋3＝0，3x ＋5y －25＝0，解得B (5,2)． ∵z ＝ y 2x －1 ＝y －0x －12 ×12 ∴z 的值即是可行域中的点与????12，0连线的斜率，观察图形可知z min ＝2－05－ 12×12＝29 ． (2)z ＝x 2＋y 2的几何意义是可行域上的点到原点O 的距离的平方． 结合图形可知，可行域上的点到原点的距离中， d min ＝|OC |＝2，d max ＝|OB |＝29． ∴2≤z ≤29． (3)z ＝x 2＋y 2＋6x －4y ＋13＝(x ＋3)2＋(y －2)2的几何意义是： 可行域上的点到点(－3,2)的距离的平方． 结合图形可知，可行域上的点到(－3,2)的距离中， d min ＝1－(－3)＝4， d max ＝(－3－5)2＋(2－2)2＝8 ∴16≤z ≤64．
整数线性规划 【数学模型】 m in T x f x st. A x b ?≤ A eq x b eq ?= lb x ub ≤≤ i x 取值为整数 其中f , x , b , beq , lb 和ub 为向量，A 和Aeq 为矩阵。 【函数】 intprog 【说明】 在Matlab 中无求解整数线性规划的现成函数，利用Matlab 的线性规划函数linprog 来编写整数线性规划函数，输入与输出与linprog 类似，采用分枝定界法来实现。 Matlab 主程序intprog 如下： function [x,fval,status] = intprog(f,A,B,I,Aeq,Beq,lb,ub,e) %整数规划求解函数 intprog() % 其中 f 为目标函数向量 % A 和B 为不等式约束 Aeq 与Beq 为等式约束 % I 为整数约束 % lb 与ub 分别为变量下界与上界 % x 为最优解，fval 为最优值 % 控制输入参数 if nargin < 9, e = 0.00001; if nargin < 8, ub = []; if nargin < 7, lb = []; if nargin < 6, Beq = []; if nargin < 5, Aeq = []; if nargin < 4, I = [1:length(f)]; end , end , end , end , end , end %求解整数规划对应的线性规划,判断是否有解 options = optimset('display','off'); [x0,fval0,exitflag] = linprog(f,A,B,Aeq,Beq,lb,ub,[],options); if exitflag < 0 disp('没有合适整数解'); x = x0; fval = fval0; status = exitflag; return ; else %采用分支定界法求解
第五章 非线性规划的概念和原理 非线性规划的理论是在线性规划的基础上发展起来的。1951年，库恩（H.W.Kuhn ）和塔克（A.W.Tucker ）等人提出了非线性规划的最优性条件，为它的发展奠定了基础。以后随着电子计算机的普遍使用，非线性规划的理论和方法有了很大的发展，其应用的领域也越来越广泛，特别是在军事，经济，管理，生产过程自动化，工程设计和产品优化设计等方面都有着重要的应用。 一般来说，解非线性规划问题要比求解线性规划问题困难得多，而且也不像线性规划那样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的适用范围。都有一定的局限性，到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人们进一步研究的课题。 5.1 非线性规划的实例及数学模型 [例题6.1] 投资问题： 假定国家的下一个五年计划内用于发展某种工业的总投资为b 亿元，可供选择兴建的项目共有几个。已知第j 个项目的投资为j a 亿元，可得收益为j c 亿元，问应如何进行投资，才能使盈利率（即单位投资可得到的收益）为最高？ 解：令决策变量为j x ，则j x 应满足条件() 10j j x x -= 同时j x 应满足约束条件 1 n j j j a x b =≤∑ 目标函数是要求盈利率()1121 ,,,n j j j n n j j j c x f x x x a x === ∑∑L 最大。 [例题6.2] 厂址选择问题： 设有n 个市场，第j 个市场位置为() ,j j p q ，它对某种货物的需要量为j b ()1,2,,j n =L 。 现计划建立m 个仓库，第i 个仓库的存储容量为i a ()1,2,,i m =L 。试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。 解：设第i 个仓库的位置为(),i i x y ()1,2,,i m =L ，第i 个仓库到第j 个市场的货物供应量为i j z ()1,2,,,1,2,,i m j n ==L L ，则第i 个仓库到第j 个市场的距离为
第三章 整数线性规划 本章, 我们介绍三种解决整数线性规划问题的软件: 第一种: MATLAB 中的optimization toolbox 中的若干程序; 第二种: LINDO 软件; 第二种: LINGO 软件. 1. MATLAB 程序说明 程序名: intprogram, L01p_e, L01p_ie, transdetobi, biprogram intprogram 是利用分支定界法解决整数规划问题, 是全部的整数规划问题; L01p_e 是利用枚举法解决0-1规划问题, 变量要求全部为0或者1; L01p_ie 是利用隐枚举法解决0-1规划问题, 变量要求全部为0或者1; Transdetobi 是枚举法和隐枚举法中利用到的将十进制数转化为二进制数的函数; Biprogram 是MATLAB6.5以上版本中有的求解0-1规划的函数的程序. intprogram 执行实例1： 12 121212max 2010s.t.5424 2513 ,0, f x x x x x x x x =++≤+≤≥ 且为整数 在命令窗口的程序执行过程和结果如下: >> c=[-20,-10]; %将最大转化为最小; >> a=[5,4;2,5]; >> b=[24;13]; >> [x,f]=intprogram(c,a,b,[0;0],[inf;inf],[],0,0.0001) % c,a,b 之后[0;0] is the value of low bound;[inf;inf] is the value of up bound;[] is the initialization;0 is the number of the equation constraints; 0.0001 is the concise rate. x = 4.0000 1.0000 f = -90 intprogram 执行实例2: 书中例题3.3.1 在命令窗口的程序执行过程和结果如下: >> c=[-1,-1]; >> a=[-4,2;4,2;0,-2]; >> b=[-1;11;-1];
探讨线性规划整数最优解的调整 对于高中的二元一次不等式（组）与平面区域这个知识点是不难的，不过对于解题的规范性学生还是要加强的。在这里就和大家探讨必修五课本当中的一道关于线性规划要求整数解的问题。 例1：某工厂用A ，B 两种配件生产甲，乙两种产品，每生产一件甲产品使用4个A 配件耗时1h ，每生产一件乙产品使用4个B 配件耗时2h ，该厂每天最多可以从配件厂获得16个A 配件和12个B 配件，按每天工作8h 计算，该厂所有可能的日生产安排是什么？若生产一件甲产品获利2万元，生产一件乙产品获利3万元，问哪种生产安排利润最大？ 分析：这是一道典型的线性规划的问题，首先可以设甲，乙两种产品分别为x,y 件，从而列出约束条件。在这道题目中，所设的是产品个数的问题，那就要注意x,y ∈N +。 解：设甲，乙两种产品分别为x,y 件，由题意可得： ???????????∈≥≥≤≤≤++ N y x,0y 0x 164y 164x 8 2y x 接着还要求解第二问，这就涉及到了目标函数，设利润为Z ，则Z=2x+3y 。 当目标函数刚好与可行域交于点M （4,2）时，能使获得的利润最大，Z max =14(万元) M(4,2)
此题中的点M 是刚好为整数点，而假设M 不是为整数点时，那又应该如何寻找其最优解？接下来再以必修五课本的一道为例题. 评析：对于此道类型的题目求出来的最优解恰好能符合条件，难度没那么大，但是有些题目对于最优解还要再进一步进行讨论。 例2：要将两种大小不同的钢板截成A ，B ，C 三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示： 问题1：今需要A ，B ，C 三种规格的成品分别15,18,27，用数学关系式和图形表示上述要求。 问题2：各截这两种干板多少张可得所需A ，B ，C 三种规格成品，且使所用钢板张数最少？ 分析：这种也是典型的线性规划的题目，问题1难度就是读懂题目，然后根据题意列出约束条件；而对于问题2即是求最优解，而此题的最优解也是要取整数，而这个整数最优解相对上一题就较难点。 解：设需截第一种钢板x 张，第二种钢板y 张，则 ?????????? ?∈≥≥≥+≥+≥++ N y x,0y 0x 27 3y x 182y x 15y 2x 则图形中的阴影部分的所有整数点就是可截的方法。接着还要求解问题 规格类型 钢板类型 A 规格 B 规格 C 规格 第一种钢板 2 1 1 第二种钢板 1 2 3
线性规划问题的解法比较与分析 【摘要】 总结了线性规划问题数学模型各种解法的优势和局限性，结合具体实例介绍一种适用性强，便于理解和记忆的新解法—新两阶段的解题思想和步骤，并通过初等行变换对单纯形法进行了进一步的改进。 关键词： 新两阶段法；换基迭代； 单纯形法； 初等行变换 1.问题的提出 线性规划问题的数学模型的一般表示形式为： 112211112211211222221122 12,max(min)(,)(,)(,),,0n n n n n n m m mn n m n z c x c x c x a x a x a x b a x a x a x b a x a x a x b x x x =++++++≤=≥??+++≤=≥??? ?+++≤=≥?≥? ? 由于有的线性规划问题目标函数求“最大值”，有的求“最小值”；约束条件中数量约束部分有的为“等式”约束，有的为“不等式”约束，故在解线性规划问题数学模型时，除图解法外，通常先规定线性规划问题的标准形式，然后给出标准形式的解法。在此我们规定，线性规划问题数学模型的标准形式为： 112211112211 21122222 1122 12,max ,,0n n n n n n m m mn n m n z c x c x c x a x a x a x b a x a x a x b a x a x a x b x x x =++++++=??+++=?? ? ?+++=?≥? ? 且：0(1,2, )i b i m ≥= 2.新两阶段法 以往，根据标准形式的不同形式的不同特点需要采用不同的解法。常用方法有：单纯形方法,大M 法，两阶段法及对偶单纯形方法等等。 在吕为的《线性规划数学模型的一种新解法》【1】 一文中，给出了适用性强，便于理解和记忆 的新解法——新两阶段法，下面我们结合例题介绍其解题方法和步骤： 例1：求解线性规划问题：
用“小范围搜索法”求“线性规划问题”的最优整数解 笔者对教科书中的全部7个线性规划的实际应用问题进行了研究和分类。其中1个问题（教科书第61页例3）的最优解不是整数解，最优解有且只有一个，最优解显然在边界折线的顶点处，此为第一类问题；有3个问题（教科书第64页练习第2题、第65页习题第3题，第66页研究课题与实习作业）的最优解为整数解，最优整数解有且只有一个，最优解整点显然在边界折线的顶点处，此为第二类问题；另有3个问题（教科书第63页例4、第65页习题第4题、第87页复习参考题七A组第16题）的最优解为整数解，最优整数解可能不止一个，最优解整点不在边界折线的顶点处，或虽在边界折线的顶点处但并不显然，此为第三类问题。第一、第二类问题的最优解可以通过解一个二元一次方程组直接得到，学生比较容易掌握。第三类问题的最优解不能通过解一个二元一次方程组直接得到，必须通过观察图形或计算检验去寻找，学生不容易掌握，学习困难比较大。 为了解决这类寻找最优整数解的困难，笔者采用“小范围搜索法”进行教学。该方法的优点在于，把在大范围同寻找最优整数解转化为在小范围内寻找最优整数解，而且在通过观察图形作出准确判断有困难的情况下，通过计算检验作出准确判断的工作量比较小。其步骤为（1）在边界折线顶点附近的小范围内搜索一个可行域内的年整点；（2）过该点作一条斜率为－（其中A，B分别为目标函数中变量x，y的系数）的直线，与可行域边界折线相交得到一个小范围的区域；（3）在这个小范围区域内继续搜索全部最优整数解。 用“小范围搜索法”成功解题的关键是分析，要把分析贯彻于解题的全过程，观察图形要分析，计算检验也要分析，通过分析充分发掘线性约束条件和线性目标函数的特殊性，使搜索范围缩到最小，计算的工作量减到最小。下面以教科书中的题目为例，说明“小范围搜索法”的运用。 例1教科书第65页习题题，题目略。 本题的线性约束条件 线性目标函数z=200x+150y，其中x，y分别为大房间与小房间的间数。作出可行域如图1。 （1）搜索一个可行域内邻近边界折线顶点的整点。 解方程组 得到点A（，），由于点A的坐标不是整数，故不是最优解。由于要使目标函数取最大值，因此要寻找可行域右上侧靠近边界或边界上的整点。与点A邻近的整点共有4个（2，8），（2，9），（3，8）与（3，9），显然点（2，8）是可行域内的整点，点（3，9）不是可行域内的整点。记点（a，b）处的目标函数的值为z（2，8），所以还应检验点（2，9）与（3，8）是否在可行域内。注意到目标函数z=200x+150y=150(x+y)+50x，而2+9=3+8，所以必有z （3，8）>z（2，9），所以应先检验点（3，8）是否在可行域内。观察与计算都表明该点在可行域内。记点（3，8）为B，B即为搜索到的可行域内邻近边界折线顶点的整点。 （2）作出可行域内的小范围搜索区域。 算出z（3，8）=1800，过B作直线200x+150y=18004x+3y=36.
第三章线性规划的解法 §3.1重点、难点提要 一、线性规划问题的图解法及几何意义 1．图解法。 线性规划问题采用在平面上作图的方法求解，这种方法称为图解法。图解法具有简单、直观、容易理解的特点，而且从几何的角度说明了线性规划方法的思路，所以，图解法还有助于了解一般线性规划问题的实质和求解的原理。 （1）图解法适用于求解只有两个或三个变量的线性规划问题，求解的具体步骤为： 1）在平面上建立直角坐标系； 2）图示约束条件，找出可行域。具体做法是画出所有约束方程(约束条件取等式)对应的直线，用原点判定直线的哪一边符合约束条件，从而找出所有约束条件都同时满足的公共平面区域，即得可行域。求出约束直线之间，以及约束直线与坐标轴的所有交点，即可行域的所有顶点； 3）图示目标函数直线。给定目标函数Z一个特定的值k，画出相应的目标函数等值线； 4）将目标函数直线沿其法线方向向可行域边界平移，直至与可行域边界第一次相切为止，这个切点就是最优点。具体地，当k值发生变化时，等值线将平行移动。对于目标函数最大化问题，找出目标函数值增加的方向(即坐标系纵轴值增大的方向)，等值线平行上移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最大值的最优解；对于目标函数最小化问题，找出目标函数值减少的方向(即坐标系纵轴值减少的方向)，等值线平行下移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最小值的最优解。 （2）线性规划问题的几种可能结果： 1）有唯一最优解； 2）有无穷多个最优解； 3）无最优解(无解或只有无界解)。 2．重要结论。 （1）线性规划的可行域为一个凸集，每一个可行解对应该凸集中的一个点； （2）每一个基可行解对应可行域的一个顶点。若可行解集非空，则必有顶点存在，从而，有可行解必有基可行解。 （3）一个基可行解对应约束方程组系数矩阵中一组线性无关的列向量，对
线性规划中的最优整数解 线性规划中的最优解，就是在线性约束条件下使目标函数取得最大值或最小值的可行 解，而求最优整数解，是同学们的棘手问题，下面以例题的形式讲讲如何求最优解。 例. 某人承揽了一项业务：需做文字标牌6个，绘画标牌5个。现有两种规格的原料， 甲种规格每张32m ，可做文字标牌1个、绘画标牌2个；乙种规格每张22m ，可做文字标 牌2个、绘画标牌1个，求两种规格的原料各用多少张才能使总的用料面积最小？最小用料 面积是多少？ 分析：将已知数据列成如下所示的表格： 解法一：设甲种规格的原料用x 张，乙种规格的原料用y 张，总的用料面积为z 2m ,则 z=3x+2y x+2y ≥6 2x+y ≥5 x ≥0 y ≥0 其可行域如图所示： 解方程组 x+2y=6 2x+y=5 得M 的坐标为47 (,)33
当直线z=3x+2y过点M 47 (,) 33 时z最小，此时 4726 32 333 z=?+?= 由题意可知，点M 47 (,) 33 不是最优解，因为此问题最优解(x,y)中x，y应都是非负 整数，所以目标函数z的最小值一定是大于26 3 的整数，且x，y都是非负整数。取z=9,得 3x+2y=9，其非负整数解是（1，3）和（3，0），但点（3，0）不在可行域内，舍去，所以 点（1，3）是最优解， min 9 z= 解法二：由解法一可知，点M 47 (,) 33 不是最优解，这时可求出可行域内左下侧靠近 边界的整点，依次为A（0，5），B（1，3），C（2，2），D（3，2），E（4，1），F（5，1），G（6，0），将这些点的坐标分别代入目标函数z=3x+2y，求出z的各对应值，经检验可知，在整点B（1，3）处z取得最小值9。 答：甲种规格的原料用1张，乙种规格的原料用3张时，总的用料面积最小，其最小用料面积为92 m。 对于线性规划中的最优整数解问题，当解方程组得到的解不是整数解时，可采用如下的方法： 1.调整优值法：先求“非整点最优解”及“最优值”，根据题意调整“最优值”，再求目标函数中的整数解，便可得出最优整数解。课本人教A版必修5第89页例6求最优整数解用的就是这种调整优值法。 2.代入验证法：在可行域内求出与“边界”（求得非整点最优解的两条直线）靠近的所有整点，代入目标函数，再进行比较就可得出最优整数解。
线性规划问题新解法 简单的线性规划问题是高中数学新课标教材的重点内容，也是近年高考命题的热点．线性规划问题的常规解法是“截距法”，即利用线性目标函数(0)z ax by b =+≠的几何意义：“z b 是直线a z y x b b =-+在y 轴上的截距”来求解．而对于有些线性规划问题．也可以运用新的视角探究其解法．现以近年高考题为例向同学们介绍，以拓广同学们的解题思路． 一、函数单调性法 例1 （高考福建卷）非负实数x y ，满足24030x y x y ?+-??+-?? ，，≤≤则3x y +的最大值是 ． 解析：在平面直角坐标系中作出不等式组表示的平面区域，如右图． 令3z x y =+，由图知，使目标函数3z x y =+取得最大值的 点一定在边界240x y +-=或30x y +-=上取得． 由24030x y x y +-=??+-=?，，解得12x y =??=? ，． （1）当01x ≤≤时，33(3)29z x y x x x =+=+-+=-+， 在[01]，上为减函数，0x =∴时，max 9z =； （2）当12x ≤≤时，33(24)512z x y x x x =+=+-+=-+， 在[1 2]，上也为减函数，1x =∴时，max 7z =； 综上知当0x =时，3z x y =+有最大值为9． 点评：本解法是将二元一次函数转化为一元一次函数，然后利用函数单调性求解的．既体现了函数与不等式的密切转化关系，也说明了线性规划问题的“返璞归真”． 二、待定系数法 例2 （高考浙江卷）设z x y =-式中变量x 和y 满足条件3020x y x y ?+-??-?? ，，≥≥则z 的最小值为（ ） Ａ．1 Ｂ．1- Ｃ．3 Ｄ．3- 解析：令()(2)()(2)z x y m x y n x y m n x m n y =-=++-=++-， 则121m n m n +=??-=-?，，解得1323m n ?=????=?? ，． 于是1212()(2)3013333 z x y x y x y =-=++-?+?=≥， 当且仅当320x y x y +=??-=? ，时，z 取最小值1．故选Ａ．
第一章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则2 1,x x 应满足 （目标函数）2134m ax x x z += (1) s.t.（约束条件）???????≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式 是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 b Ax x c x T ≤ that such min 其中c 和x 为n 维列向量，b 为m 维列向量，A 为n m ?矩阵。 例如线性规划 b Ax x c x T ≥ that such max 的Matlab 标准型为 b Ax x c x T -≤-- that such min
线性规划问题的求解 在数学中，线性规划 (Linear Programming，简称LP) 问题是目标函数和 约束条件都是线性的最优化问题。 线性规划是最优化问题中的重要领域之一。很多运筹学中的实际问题都可以 用线性规划来表述。线性规划的某些特殊情况，例如网络流、多商品流量等问题， 都被认为非常重要，并有大量对其算法的专门研究。很多其他种类的最优化问题 算法都可以分拆成线性规划子问题，然后求得解。在历史上，由线性规划引申出 的很多概念，启发了最优化理论的核心概念，诸如“对偶”、“分解”、“凸性” 的重要性及其一般化等。我们在以前的学习过程中曾经接触过最简单的线性规划 ——平面规划，但由于其是在平面上求解，形式较为简单，通过作图和平移目标 函数即可得到最优解。但是通过对平面规划的类比，我们可以得出求解线性规划 问题的一般方法——单纯形法。 几何上，线性约束条件的集合相当于一个凸包或凸集，叫做可行域。因为目 标函数亦是线性的，所以其极值点会自动成为最值点。线性目标函数亦暗示其最 优解只会出现在其可行域的边界点中。 在两种情况下线性规划问题没有最优解。其中一种是在约束条件相互矛盾的 情况下（例如x≥ 2 和x≤ 1），其可行域将会变成空集，问题没有解，因此 亦没有最优解。在这种情况下，该线性规划问题会被称之为“不可行”。 另一种情况是，约束条件的多面体可以在目标函数的方向无界（例如： max z=x + 3 x2 s.t. x1≥ 0, x2≥ 0, x1 + x2≥ 10），目标函数可以取得任意大1 的数值，所以没有最优解。 除了以上两种病态的情况以外（问题通常都会受到资源的限制，如上面的例 子），最优解永远都能够在多面体的顶点中取得。但最优解未必是唯一的：有可 能出现一组最优解，覆盖多面体的一条边、一个面、甚至是整个多面体（最后一 种情况会在目标函数只能等于0的情况下出现）。 在使用单纯形法求解线性规划问题之前，我们首先需要了解什么是标准 型，这是线性规划问题中最常用也最直观的形式。 标准型包括以下三个部分： 一个需要极大化的线性函数，例如:
目录 未找到目录项。 第一章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则21,x x 应满足 （目标函数）2134max x x z += (1) s.t.（约束条件）???????≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式 是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 b Ax x c x T ≤ that such min beq x Aeq =?