1、从上面的图解过程可以看出并不难证明以下断言：（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时，它必定是若干个半平面的交集（除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。-3-（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”。上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维空间中，满足一线性等式=niiibxa1的点集被称为一个超平面，而满足一线性不等式=niiibxa1（或=niiibxa1）的点集被称为
2、一个半空间（其中）,（1naaL为一n维行向量，b为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域必为多胞形（为统一起见，空集也被视为多胞形）。在一般n维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。为此，我们将采用另一途径来定义它。定义定义 1 称n维空间中的区域R为一凸集，若Rxx21,及）1,0（，有Rxx+21）1（。定义定义 2 设R为n维空间中的一个凸集，R中的点x被称为R的一个极点，若不存在Rxx21、及）1,0（，使得21）1（
3、xxx+=。定义 1 说明凸集中任意两点的连线必在此凸集中；而定义 2 说明，若x是凸集R的一个极点，则x不能位于R中任意两点的连线上。不难证明，多胞形必为凸集。同样也不难证明，二维空间中可行域R的顶点均为R的极点（R也没有其它的极点）。1.5 求解线性规划的 Matlab 解法 单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的 Matlab解法。Matlab 中线性规划的标准型为 xcxT min s.t.=ubxlbbeqxAeqbAx 基本函数形式为 linprog（c,A,b），它的返回值是向量
4、x的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：x,fval=linprog（c,A,b,Aeq,beq,LB,UB,X0,OPTIONS）这里 fval 返回目标函数的值，LB 和 UB 分别是变量x的下界和上界，0 x是x的初始值，OPTIONS 是控制参数。例 2 求解下列线性规划问题 321532max xxxz+=s.t.7321=+xxx 1052321+xxx 123321+xxx 0,321xxx -4-解（i）编写 M 文件 c=2;3;-5;a=-2,5,-1;1,3,1;b=-10;12;aeq
5、=1,1,1;beq=7;x=linprog（-c,a,b,aeq,beq,zeros（3,1）value=c*x（ii）将M文件存盘，并命名为example1.m。（iii）在Matlab指令窗运行example1即可得所求结果。例3 求解线性规划问题 32132 minxxxz+=+0,62382432121321xxxxxxxx 解 编写Matlab程序如下：c=2;1;a=1,4,2;3,2,0;b=8;6;x,y=linprog（c,-a,-b,zeros（3,1）1.6 可以转化为线性规划的问题 很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如：例4 规划问题
6、为 bAxxxxn+t.s.|min21L 其中Tnxxx1L=，A和b为相应维数的矩阵和向量。要把上面的问题变换成线性规划问题，只要注意到事实：对任意的ix，存在0,iivu满足 iiivux=，iiivux+=|事实上，我们只要取2|iiixxu+=，2|iiixxv=就可以满足上面的条件。这样，记Tnuuu1L=，Tnvvv1L=，从而我们可以把上面的问题变成 =+niiivu1）（min 0,）（t.s.vubvuA 例 5|maxminiyxii 其中iiiyx=。对于这个问题，如果我们取|max0iyix=，这样，上面的问题就变换成 -5-0minx 0011,t.s.xyxxyx
7、nnL 此即我们通常的线性规划问题。2 运输问题（产销平衡）例 6 某商品有m个产地、n个销地，各产地的产量分别为maa,1L，各销地的需求量分别为nbb,1L。若该商品由i产地运到j销地的单位运价为ijc，问应该如何调运才能使总运费最省？解：引入变量ijx，其取值为由i产地运往j销地的该商品数量，数学模型为 =minjijijxc11min s.t.=0,2,1,1,11ijmijijnjiijxnjbxmiaxLL 显然是一个线性规划问题，当然可以用单纯形法求解。对产销平衡的运输问题，由于有以下关系式存在：=miinjnjmiijminjijjaxxb111111 其约束条件的系数矩阵相当
8、特殊，可用比较简单的计算方法，习惯上称为表上作业法（由康托洛维奇和希奇柯克两人独立地提出，简称康希表上作业法）。3 指派问题 3.1 指派问题的数学模型 例 7 拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费ijc单位时间，问应如何分配工作才能使工人花费的总时间最少？容易看出，要给出一个指派问题的实例，只需给出矩阵）（ijcC=，C被称为指派问题的系数矩阵。引入变量ijx，若分配i干j工作，则取1=ijx，否则取0=ijx。上述指派问题的数学模型为 =ninjijijxc11min s.t.=njijx11 -6-=niijx11 1 0或=ijx 上述指派问
9、题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为 0；可以用n,1L中的一个置换表示。问题中的变量只能取 0 或 1，从而是一个 0-1 规划问题。一般的 0-1 规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为1），其非负可行解的分量只能取 0 或 1，故约束10或=ijx可改写为0ijx而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中nm=，1=jiba。3.2 求解指派问题的匈牙利算法 由于指派问题的特殊性，又存在着由匈牙利数学家 Konig 提出的更为简便的解法匈牙利算法。算法主要依
10、据以下事实：如果系数矩阵）（ijcC=一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵）（ijbB=，则以C或B为系数矩阵的指派问题具有相同的最优指派。例 8 求解指派问题，其系数矩阵为 =16221917171822241819211722191516C 解 将第一行元素减去此行中的最小元素 15，同样，第二行元素减去 17，第三行元素减去 17，最后一行的元素减去 16，得 =06310157124074011B 再将第 3 列元素各减去 1，得 =*20531005711407301B 以2B为系数矩阵的指派问题有最优指派 43124321 由等价性，它也是例 7 的最优指派
11、。有时问题会稍复杂一些。例 9 求解系数矩阵C的指派问题 -7-=61071041066141512141217766698979712C 解：先作等价变换如下 2636040*08957510*00*0032202*056107104106614151214121776669897971246767 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但5=n，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：（1）对未选出 0 元素的行打；（2）对行中 0 元素所在列打；（3）对列中选中的 0 元素所在行打；重复（2）、（3）直到无法再打为止。可以证明，若用直线划没有打的
12、行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的 0 元素不变，而未覆盖元素中至少有一个已转变为 0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的 0 元素为止。例如，对例 5 变换后的矩阵再变换，第三行、第五行元素减去 2，第一列元素加上 2，得 04140400811353800003420207 现在已可看出，最优指派为5314254321。4 对偶理论与灵敏度分析 4.1 原始问题和对偶问题 考虑下列一对线性规划模型：xcTmax s.t.0,xbAx （P）和 y
13、bTmin s.t.0,ycyAT （D）-8-称（P）为原始问题，（D）为它的对偶问题。不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：（1）原始问题中的第j列系数与其对偶问题中的第j行的系数相同；（2）原始目标函数的各个系数行与其对偶问题右侧的各常数列相同；（3）原始问题右侧的各常数列与其对偶目标函数的各个系数行相同；（4）在这一对问题中，不等式方向和优化方向相反。考虑线性规划：0,s.t.min=xbAxxcT 把其中的等式约束变成不等式约束，可得 0,s.t.minxbbxAAxcT 它的对偶问题是 cyyAAyybbTTTT2121 s.t.max 其中1y和2y分别表示对应
14、于约束bAx 和bAx的对偶变量组。令21yyy=，则上式又可写成 cyAybTT s.t.max 原问题和对偶的对偶约束之间的关系：min max 无限制变量00 =000行约束=000行约束 无限制变量00 4.2 对偶问题的基本性质 1o 对称性：对偶问题的对偶是原问题。2o 弱对偶性：若x是原问题的可行解，y是对偶问题的可行解。则存在ybxcTT。3o 无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。4o 可行解是最优解时的性质：设x是原问题的可行解，y 是对偶问题的可行解，当ybxcTT=时，yx,是最优解。5o 对偶定理：若原问题有最优解，那么对偶问题也有最优
15、解；且目标函数值相同。6o 互补松弛性：若yx,分别是原问题和对偶问题的最优解，则 0）（,0）（=cyAxbxAyTTT 例 10 已知线性规划问题 5432132532minxxxxx+=s.t.43254321+xxxxx -9-33254321+xxxxx 5,2,1,0L=jxj 已知其对偶问题的最优解为5;53,54*2*1=zyy。试用对偶理论找出原问题的最优解。解 先写出它的对偶问题 2134maxyyz+=2221+yy 321 yy 53231+yy 221+yy 3321+yy 0,21yy 将*2*1,yy的值代入约束条件，得，为严格不等式；由互补松弛性得0*4*3*2
16、=xxx。因 0,*2*1yy；原问题的两个约束条件应取等式，故有 43*5*1=+xx 32*5*1=+xx 求解后得到1,1*5*1=xx；故原问题的最优解为 5;10001*=X。4.3 灵敏度分析 在以前讨论线性规划问题时，假定jiijcba,都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，jc值就会变化；ija往往是因工艺条件的改变而改变；ib是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。这里我们就不讨论了
17、。4.4 参数线性规划 参数线性规划是研究jiijcba,这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题。5 投资的收益和风险 5.1 问题提出 市场上有n种资产is（ni,2,1L=）可以选择，现用数额为M的相当大的资金作一个时期的投资。这n种资产在这一时期内购买is的平均收益率为ir，风险损失率为iq，投资越分散，总的风险越少，总体风险可用投资的is中最大的一个风险来度量。-10-购买is时要付交易费，（费率ip）
18、，当购买额不超过给定值iu时，交易费按购买iu计算。另外，假定同期银行存款利率是0r，既无交易费又无风险。（%50=r）已知4=n时相关数据如表 1。表 1 is ir（%）iq ip（%）iu（元）1s 28 2.5 1 103 2s 21 1.5 2 198 3s 23 5.5 4.5 52 4s 25 2.6 6.5 40 试给该公司设计一种投资组合方案，即用给定资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。5.2 符号规定和基本假设 符号规定：is：第i种投资项目，如股票，债券 iiiqpr,：分别为is的平均收益率，交易费率，风险损失率 iu：is
19、的交易定额 0r：同期银行利率 ix：投资项目is的资金 a：投资风险度 Q：总体收益 基本假设：1 投资数额M相当大，为了便于计算，假设1=M；2 投资越分散，总的风险越小；3 总体风险用投资项目is中最大的一个风险来度量；4 n种资产is之间是相互独立的；5 在投资的这一时期内，iiiqpr,，0r为定值，不受意外因素影响；6 净收益和总体风险只受iiiqpr,影响，不受其它因素干扰。5.3 模型的分析与建立 1 总体风险用所投资的is中最大的一个风险来衡量，即 ,2,1|maxnixqiiL=2购买is所付交易费是一个分段函数，即 交易费=iiiiiiiiuxupuxxp,而题目所给定的
20、定值iu（单位：元）相对总投资M很少，iiup更小，可以忽略不计，这样购买is的净收益为iiixpr）（。3 要使净收益尽可能大，总体风险尽可能小，这是一个多目标规划模型：-11-目标函数为 =maxmin）（max0iiniiiixqxpr 约束条件为 =+=nixMxpiniii,1,0,0）1（0L 4 模型简化 a）在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险aMxqii，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。模型一 固定风险水平，优化收益 =niiiixpr0）（max s.t.=+=niiiiiinixMxpaMxq0,1
21、,0,0,）1（L b）若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻求相应的投资组合。模型二 固定盈利水平，极小化风险 maxminiixq s.t.=+=niiiiniiiinixMxpkxpr00,1,0,0,）1（）（L c）投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益分别赋予权重s（10 s）和）1（s，s称为投资偏好系数。模型三 =niiiiiixprsxqs0）（）1（maxmin s.t.=+niiiinixMxp0,2,1,0,0,）1（L 5.4 模型一的求解 模型一为：Txxxxxf）,）（185.0,185.0,
22、19.0,27.0,05.0（min43210=-12-s.t.=+）4,1,0（0026.0055.0015.0025.01065.1045.102.101.1432143210Lixaxaxaxaxxxxxxi 由于a是任意给定的风险度，到底怎样没有一个准则，不同的投资者有不同的风险度。我们从0=a开始，以步长001.0=a进行循环搜索，编制程序如下：clc,clear a=0;hold on while a+=0 ,00,jjjjjjxxxckP当当 3,2,1=j.在构成目标函数时，为了统一在一个问题中讨论，现引入10变量jy，令=.00,0,1时种生产方式，即当不采用第时，种生产方式
23、，即当采用第jxjjxjjy （3）于是目标函数 ）（）（）（min333322221111xcykxcykxcykz+=（3）式这个规定可表为下述 3 个线性约束条件：3,2,1,=jMyxyjjj （4）其中是一个充分小的正常数，M是个充分大的正常数。（4）式说明，当0jx时jy必须为 1；当0=jx时只有jy为 0 时才有意义，所以（4）式完全可以代替（3）式。3.2 10型整数规划解法之一（过滤隐枚举法）解10型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为 0 或 1 的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的n2个组合。对于变
24、量个数n较大（例如100n），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对 -21-有些问题隐枚举法并不适用，所以有时穷举法还是必要的。下面举例说明一种解10型整数规划的隐枚举法。例 6 321523Maxxxxz+=+10,64344223213221321321或xxxxxxxxxxxxx 求解思路及改进措施：（i）先试探性求一个可行解，易看出）0,0,1（）,（321=xxx满足约束条件，故为一个可行解，且3=z。（ii）因为是求极大值问题
25、，故求最优解时，凡是目标值3z的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：（iii）改进过滤条件。（iv）由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值z大的组合，这样可提前抬高过滤门槛，以减少计算量。4 蒙特卡洛法（随机取样法）前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数
26、很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。例 7 已知非线性整数规划为：5432125242322212328 243Max xxxxxxxxxxz+=+=200520062800622400）5,1（9905433215432154321xxxxxxxxxxxxxxxxixiL 如果用显枚举法试探，共需计算10510）100（=个点，其计算量非常之大。然而应用蒙特卡洛去随机计算610个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？下面就分析随机取样采集610个点计算时，应用概率理
27、论来估计一下可信度。不失一般性，假定一个整数规划的最优点不是孤立的奇点。假设目标函数落在高值区的概率分别为 0.01，0.00001，则当计算610个点后，有-22-任一个点能落在高值区的概率分别为 多位）100（9999.099.011000000L，999954602.099999.011000000。解 （i）首先编写 M 文件 mente.m 定义目标函数 f 和约束向量函数 g，程序如下：function f,g=mengte（x）;f=x（1）2+x（2）2+3*x（3）2+4*x（4）2+2*x（5）-8*x（1）-2*x（2）-3*x（3）-.x（4）-2*x（5）;g=sum
28、（x）-400 x（1）+2*x（2）+2*x（3）+x（4）+6*x（5）-800 2*x（1）+x（2）+6*x（3）-200 x（3）+x（4）+5*x（5）-200;（ii）编写M文件mainint.m如下求问题的解：rand（state,sum（clock）;p0=0;tic for i=1:106 x=99*rand（5,1）;x1=floor（x）;x2=ceil（x）;f,g=mengte（x1）;if sum（g=0）=4 if p0=f x0=x1;p0=f;end end f,g=mengte（x2）;if sum（g=0）=4 if p0=f x0=x2;end end end x0,p0 toc 本题可以使用LINGO软件求得精确的全局最有解，程序如下：model:sets:row/1.4/:b;col/1.5/:c1,c2,x;link（row,col）:a;endsets data:c1=1,1,3,4,2;c2=-8,-
