线性规划模型

1、线性规划模型,y,2、找出问题中所有的限制或约束，写出未知变量的线性方程组或线性不等式组；,一、线性规划模型,1、找出待定的未知变量（又称为决策变量决策者自己可以控制的变量），并且用符号表示；,3、找出模型的目标函数：是以函数形式表示的决策者追求的目标写出未知变量的线性方程或线性不等式,（一）建立线性规划模型有三个基本步骤：,例 （配料问题）某铸造厂生产铸件，每件需要20千克铅，24千克铜和30千克铁。现有四种矿石可供选购，它们每10千克含有成分的质量（千克）和价格（元）如图。问：对每个铸件来说，每种矿石各应该选购多少，可以使总费用最少？试建立数学模型。,分析和建立模型,（1）确定决策变量：设

2、 为第i种矿石的选取的数量（单位10kg） ；,（3）确定约束条件：选定的四种矿石的数量应该满足铸件对三种成分的需求量，并且矿石数量应该是非负的，即,每件需要20千克铅，24千克铜和30千克铁,综合以上分析，得到配料问题的数学模型为：,受约束于,（二）线性规划模型的结构具有如下特性,（1）目标函数是决策变量 的线性函数；,（2）约束条件是决策变量 的线性等式或不等式；,具有以上结构特点的模型就是线性规划模型，记为LP（Linear Programming），具有以下一般形式：,（三）线性规划的标准模型,由于目标函数既可以是实现最大化，也可以是实现最小化，约束条件可以是等式，也可以是不等式，决策

3、变量为非负或不受限制，这么复杂的情况，一定会给模型的求解带来不便，为此引入标准形式,标准形式,（四）线性规划数学模型标准形式的特点,2、约束条件均为线性；,3、决策变量及方程右端非负。,线性规划数学模型标准形式可以有向量形式表示：,1、目标函数为最大化类型（有的书上为最小化）；,1、如果目标函数为最小化问题，则将目标函数两边乘以“-1”；,2、如果约束方程右端为负，在该方程两端同乘以 “-1”；,如果所建的模型不符合标准形式，则可以用适当方法化为标准形式，主要有：,3、如果约束为 “ ”，则可以增加一个变量 ，在左端加上 ，这种变量称为剩余变量；,4、如果约束为 “ ”，则可以增加一个变量 ，

4、在右 端加上 ，这种变量要求非负，在线性规划中均称为松驰变量；,5、如果某决策变量 无符号限制，则将每个 换成,例：将下列线性规划模型化为标准形式,化成标准形式为：,（一）基本概念：,1、可行解：所有满足约束条件 的解。,2、可行域：所有可行解组成的集合。,4、最优值：对应于最优解的目标函数值。,3、最优解：使得目标函数达到最优值的可行解。,二、线性规划问题的解及单纯形法（解法）,5、基：约束方程组 的系数矩阵为 阶的矩阵 则称A的任意一个 阶的非奇异子矩阵B为线性规划的一个基。,6、基向量：组成基B的列向量 称为 基向量。,7、基变量：基向量 对应的变量 称为基变量，基变量以外的变量称为非基

5、变量。,9、基可行解：满足非负条件 的基本解。,10、可行基：基可行解对应的基。,11、基本最优解：使目标函数达到最大值的基可行解。,12、最优基：基本最优解对应的基。,8、基本解：在 中，令非基变量全部为0，求出 的一个解X，称为基本解。,1、基本思想：首先找出一个基可行解，然后根据某种最优性准则判断该解是否为最优，如果最优，则结束；否则利用某种迭代规则寻找下一个基可行解，并且使下一个基可行解的目标函数值有所改变，反复多次，直到找出最优解，或判断出原问题无最优解。,（二）单纯形法,为了确定初始基可行解，需要先找出初始可行基。其方法是：观察约束方程组系数矩阵 ，若其中有子块为m阶单位矩阵 ，则

6、可将其选为初始可行基；否则，可采用所谓人工变量法寻找初始可行基。,（1）、确定初始基可行解并且计算相应的目标函数值,2、计算步骤（3步）,若 的前m列为单位阵（作为基），则约束方程 可化为,令非基变量 即得初始基可行解。,将方程组（1）代入目标函数,故对应于基可行解 的目标函数值 ，于是原线性规划模型等价于,此等价模型称为原线性规划的典式，其中 称为基本可行解 的检验数,（2）、根据检验数 进行最优性检验与解的判断。,定理：若线性规划的基可行解 对应的典式为（1）并且检验数为,、 当存在某个检验数 时，并且典式（1）中所有 时，线性规划无有限最优解。,则 、 当 时， 是线性规划的有限最优解；

7、,、 当存在检验数 且典式（1）中有些 ，这时采用迭代法实现基可行解的转移。,当初始基可行解 不是最优解，并且不能判别无有限最优解时，需要另找一个基可行解，并使相应目标函数值增大，（即要对原可行基换一个列向量）。为此需要确定进基变量和出基变量的规则。,（3） 通过换基迭代，实现基可行解的转移,出基变量的规则：,为了使得目标函数值增加得较快，进基变量 的取值使得目标函数值尽可能的大，出基变量取哪一个，通过 准则来确定。,准则,反复进行以上步骤，即可获得线性规划的最优解，或判断出该线性规划无有限最优解。,其中 对应的系数。 称为主元素（又称为中心元素），主元素所在行的基变量 ，就是要确定的出基变量

8、。,单纯形表：单纯形法的求解过程实际上是在一系列表格上进行的。从这些表格上可以得到基本可行解、检验数等信息。这些表格称为单纯形表。每个表相当于一个矩阵，每次迭代就是对矩阵进行初等行变换。,例：求解线性规划问题的最优解,解：（1）构造初始单纯单纯形表（第1、4、5列构成的矩阵可逆）所以可取,为初始基可行解。因目标函数 不是典式 ，故将 代入目标函数z，整理得 （典式） 其中，6为 的目标函数值，此时可以列出单纯形表（如图）。,（2）迭代求新的基可行解及其检验数,从上表格中可以看出，检验数 大于0，不满足最优性准则，须迭代求新解。取最大的检验数 对应的变量 为进基变量。它取代谁呢？再由 准则，用表

9、格最右侧元素分别与表格中 所在列的各元素去比，求最小值,最小值4对应表格中基变量为 ，故 为出基变量，元素 为中心元素。,开始迭代，将 所在列元素变为单位向量，检验数行也参加变换。同时将表格左侧列中基变量 换成 得表（把x3所在的元素化为1，然后再把其它行的元素化为零）,令 得第二个基可行解,表格的右下角说明，当前的目标值为 14，目标值增量为8，另外上面的表格中仍然有 仍然需要迭代求新解。,继续迭代,取 为进基变量，并且用上表格最右端列元素比上 所在列相应元素，计算,最小比值对应上表中基变量 所在的行，故 为出基变量 ，中心元素为 ，同上述方法可知 为进基变量，于是得到下面的表格,表格的右下

10、角说明，当前的目标值为 14.5，目标值增量为0.5，,下面利用LINGO软件求解,LINGO9.0,LINGO初始界面,LINGO程序,LINGO程序运行,变量数量,变量总数,非线性变量数,整数变量数,约束数量,约束总数,非线性约束个数,非零系数数量,总数,非线性项的系数个数,内存使用量,求解花费的时间,当前模型的类型,当前解的状态,当前解的目标函数值,求解器（求解程序）状态框,当前约束不满足的总量（不是不满足的约束的个数）实数时该值为0,到目前为止迭代次数,使用的特殊求解程序,扩展的求解器状态框（求解程序）状态框,到目前为止找到的可行解的最佳目标函数值,目标函数值的界,特殊求解程序当前运行

11、步数,有效步数,刷新本界面的时间间隔（秒）,目标函数值,求解迭代次数,决策变量,非基变量,基变量,给出最优的单纯形表中目标函数行变量对应的系数（即各个变量的检验数，基变量为0，非基变量对应的值表示当该非基变量增加一个单位时目标函数减少的量（对max型问题）,例1 加工奶制品的生产计划,问题：一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在甲类设备上用12小时加工成3公斤A1，或者在乙类设备上用8小时加工成4公斤A2。根据市场需求，生产的A1，A2全部能够售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并

12、且甲类设备每天至多能加工100公斤A1，乙类设备的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大？并且进一步讨论以下3个问题：,1）若有35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？ 2）若可以聘用临时工人增加劳动时间，付给临时工人的工资最多是每小时几元？ 3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？,问题分析：这个优化问题的目标是使每天的获利最大，要作的决策是生产计划，即每天用多少桶牛奶生产A1，用多少桶牛奶生产A2，决策受3个条件的限制：原料（牛奶）供应，劳动时间、甲类设备的加工能力。将决策变量、目标函数和约束条件用数学式子表

13、示出来，就得到相应的数学模型。,决策变量：设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2。,目标函数：设每天获利为z元，x1桶牛奶生产3x1公斤A1，获利24*3x1，x2桶牛奶生产4x2公斤A2，获利16*4x2，所以z=72*x1+64*x2。,约束条件： 原料供应 生产A1，A2的原料总量不得超过每天的供应，即x1+x2=50;,劳动时间 生产A1，A2的原料总加工时间不得超过每天正式工人总的劳动时间， 即 12*x1+8*x2=480；,设备能力 A1的产量不得超过甲类设备的加工能力， 即 3*x1=100；,非负约束 x1=0 x2=0 ；,数学模型：,给出最优的单纯形表中目标函数

14、行变量对应的系数（即各个变量的检验数，基变量为0，非基变量对应的值表示当该非基变量增加一个单位时目标函数减少的量（对max型问题）,约束条件的右段通常看作资源，一般称“资源”剩余为零的约束为紧约束（有效约束）；目标函数看作“效益”成为紧约束的资源一旦增加，“效益必然跟着增加”,LINDO6.1,LINDO程序,灵敏性分析吗,表示单纯形法在两次迭代后得到最优解,表示最优目标值为3360（在LINDO中目标函数所在的行总是被认为是第一行）,给出最优的单纯形表中目标函数行变量对应的系数（即各个变量的检验数，基变量为0，非基变量对应的值表示当该非基变量增加一个单位时目标函数减少的量（对max型问题）,

15、松弛或剩余（给出约束对应的松弛变量的值。第2、3行松弛变量为0，说明两个约束都是紧约束）,给出影子价格的值,表示用单纯形法进行了两次迭代,目标函数的系数和约束条件右端项在什么范围变化时，最优基保持不变,目标函数中系数变化的范围,最优基：基本最优解对应的基。,目标函数中变量当前的系数,目标函数的系数允许增加的幅度，最优基保持不变,目标函数的系数允许减少的幅度，最优基保持不变,约束条件中当前的右端项最优基保持不变,约束条件中当前的右端项允许变化的范围，最优基保持不变,约束条件中右端项允许增加的幅度最优基保持不变,约束条件中右端项允许减少的幅度，最优基保持不变,INFINITY表示正无穷大,问题：例

16、1给出的A1、A2两类奶制品的生产条件、利润，及工厂的资源限制全都不变。为了增加工厂的利润，开发了奶制品的深加工技术：用2个时间和3元加工费，可将1公斤A1加工成0.8公斤高级奶制品B1，也可以将1公斤A2加工成0.75公斤高级奶制品B2，每公斤B1能获利44元，每公斤B2能获利32元。试为该厂制订一个生产销售计划，使每天的净利润最大，并且讨论以下问题：,例2 奶制品的生产销售计划,1）：若投资30元可以增加供应1桶牛奶，投资3元可以增加1小时劳动时间，应否作这项投资？如每天投资150元，可以赚回多少？ 2）：每公斤高级奶制品B1、B2的获利经常有10%的波动，对制订的生产销售计划有无影响？若

17、每公斤B1的获利下降10%，计划应该变化吗？,教材P83例奶制品的生产销售计划程序,LINGO程序,LINDO程序,三、整数线性规划模型,变量取整数的线性规划称为整数线性规划，简称整数线性规划，记为IP。,整数规划分为纯整数线性规划，记为PILP； 混合整数规划，记为MILP,整数 规划的特殊情况是0-1规划，其变量只取0或者1,1、整数 规划模型及分枝定界法,由于整数 规划模型比线性规划模型增加了取整的条件，所以一种自然的想法是利用线性规划的方法求解整数规划模型。但如直接对线性规划问题最优解取整往往得不到整数 规划的最优解。因为对线性规划问题最优解取整以后，有时会破坏原问题的约束条件，但解却

18、不是最优解。下面介绍对于纯整数和混合整数规划都适用的分枝定界法,分枝定界法的一般步骤：,（1） 称原整数规划问题为A；不考虑整数条件，相应的线性规划问题为B；,（2） 解问题B，如问题B无可行解，则停止，原问题A也无可行解；,（3） 如求得问题B的最优解，检查它是否符合整数条件，如果满足整数条件，它就是问题A的最优解；如不满足整数条件，转下一步；,（5） 不考虑整数条件解这两个后继问题；,（6） 在现有并且还未分解出各后继问题的各可行解中，选择目标函数值为最优的问题，重新称该问题为B，转（3）。,首先不考虑整数的条件，求解线性规划，得最优解：,任意选择非整数解变量。如 ，由于 ，问题的解要求整

19、数，所以分出两个约束。 从而把原问题分成两个子问题：,对子问题S1、 S2，不考虑整数条件，得最优解,这两个仍然不满足整数的要求。所以继续对（S1）和（S2）分解。由于（S1）的最优值Z=349.000比，（S2）的最优值Z=341.390大，所以先对（S1）进行分解。由于 不满足整数要求，所以,所以添加条件 把（S1）分解成两个后继问题（S11）和（S12）。依次类推得到最优解或判断无最优解。,上述思想是分支定界的理论，但在利用数学软件求解时可以省去。,上述整数线性规划模型的LINGO程序,问题1. 如何下料最节省 ?,例 钢管下料,问题2. 客户增加需求：,节省的标准是什么？,由于采用不同

20、切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,合理切割模式的余料应小于客户需要钢管的最小尺寸,合理切割模式,钢管下料问题1：,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,2. 所用原料钢管总根数最少,两种标准,1. 原料钢管剩余总余量最小,xi 表示按第i 种模式切割的原料钢管根数(i=1,2,7),决策变量,目标1（总余量）,按模式2切割12根,按模式5切割15根，余料27米,最优解：x2=12, x5=15,其余为0； 最优值：27。,相应的LINGO程序,目标2（

21、总根数）,约束条件不变,最优解：x2=15, x5=5, x7=5, 其余为0； 最优值：25。,xi 为整数,相应的LINGO程序,钢管下料问题2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：5米10根；切割模式不超过3种。,现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。,决策变量,xi 表示按第i 种模式切割的原料钢管根数(i=1,2,3),r1i, r2i, r3i, r4i 表示第i 种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量,目标函数（总根数）,约束条件,模式合理：每根余料不超过3米,上述问题属

22、于整数非线性规划模型，模型求解比较困难，为此再引入适当的约束条件：,整数约束：xi ,r1i, r2i, r3i, r4i (i=1,2,3)为整数,增加约束，缩小可行域，便于求解,由于每根原料钢管长19米原料钢管总根数下界：,需求：4米50根，5米10根，6米20根，8米15根,特殊生产计划：对每根原料钢管 模式1：切割成50根4米钢管，需13根； 模式2：切割成10根5米和20根6米钢管，需10根； 模式3：切割成15根8米钢管，需8根。 原料钢管总根数上界：13+10+8=31,模式排列顺序可任定,LINGO程序,LINGO求解整数非线性规划模型,Local optimal soluti

23、on found at iteration: 12211 Objective value: 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000

24、R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000,模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根； 模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根； 模式3：每根原料钢管切割成2根8米钢管，共8根。 原料钢管总根数为28根。,板材规格2：长方形，3228cm，2万张。,例 易拉罐下料,板材规格1：正方形，边长24cm，5万张。,每周工作40小时，每只易拉罐利润0.10元，原料余料损失0.001

25、元 / cm2（不能装配的罐身、盖、底也是余料）,如何安排每周生产？,罐身高10cm，上盖、下底直径均5cm。,模式1: 正方形的边长24cm,问题分析,计算各种模式下的余料损失,上、下底直径d=5cm，罐身高h=10cm。,模式1 余料损失 242-10d2/4 - dh=222.6 cm2,问题分析,目标:易拉罐利润扣除原料余料损失后的净利润最大,约束：每周工作时间不超过40小时； 原料数量：规格1（模式1 3）5万张， 规格2（模式4）2万张； 罐身和底、盖的配套组装 。,注意：不能装配的罐身、上下底也是余料,决策变量,xi 按照第i 种模式的生产张数(i=1,2,3,4)； y1 一周生产的易拉罐个数； y2 不配套的罐身个数； y3 不配套的底、盖个数。,每只易拉罐利润0.10元，余料损失0.001元 / cm2,罐身面积dh=157.1 cm2 ，底盖面积d2/4=19.6 cm2,目标函数,约束条件,原料约束,约束条件,配套约束,虽然xi和y1，y2，y3应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理 。,将所有决策变量扩大10000倍（xi