《线性规划模型》PPT课件.ppt

《《线性规划模型》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《线性规划模型》PPT课件.ppt（143页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 线性规划模型线性规划模型 y 2 2、找出问题中所有的限制或约束，写出未知、找出问题中所有的限制或约束，写出未知变量的线性方程组或线性不等式组；变量的线性方程组或线性不等式组；一、线性规划模型一、线性规划模型 1 1、找出、找出待定的未知变量待定的未知变量（又称为（又称为决策变量决策变量决策者自己可以控制的变量），并且用符号表决策者自己可以控制的变量），并且用符号表示；示；3 3、找出模型的目标函数：是以函数形式表示、找出模型的目标函数：是以函数形式表示的决策者追求的目标写出未知变量的线性方程或的决策者追求的目标写出未知变量的线性方程或线性不等式线性不等式（一）建立线性规划模型有三个基本步骤

2、：（一）建立线性规划模型有三个基本步骤：例例 （配料问题配料问题）某铸造厂生产铸）某铸造厂生产铸件，每件需要件，每件需要2020千克铅，千克铅，2424千克铜和千克铜和3030千克铁。现有四种矿石可供选购，它们千克铁。现有四种矿石可供选购，它们每每1010千克含有成分千克含有成分的质量（千克）和价的质量（千克）和价格（元）如图。问：对每个铸件来说，格（元）如图。问：对每个铸件来说，每种矿石各应该选购多少，可以使每种矿石各应该选购多少，可以使总费总费用最少用最少？试建立数学模型。？试建立数学模型。分析和建立模型分析和建立模型 （1 1）确定决策变量：）确定决策变量：设设 为第为第i i种矿石的选

3、取的数量（单位种矿石的选取的数量（单位10kg10kg）；（2 2）确定目标函数）确定目标函数：目标应该是使得总费用最小，即目标应该是使得总费用最小，即达到最小；达到最小；（3 3）确定约束条件确定约束条件：选定的四种矿石的数量：选定的四种矿石的数量应该满足铸件对三种成分的需求量，并且矿石数应该满足铸件对三种成分的需求量，并且矿石数量应该是非负的，即量应该是非负的，即每件需要每件需要2020千克铅，千克铅，2424千克铜和千克铜和3030千克铁千克铁综合以上分析，得到配料问题的数学模型为：综合以上分析，得到配料问题的数学模型为：受约束于受约束于（二）线性规划模型的结构具有如下特性（二）线性规划

4、模型的结构具有如下特性 （1 1）目标函数是决策变量）目标函数是决策变量 的线性函数；的线性函数；（2 2）约束条件是决策变量）约束条件是决策变量 的线性等式或不等式；的线性等式或不等式；具有以上结构特点的模型就是线性规划模具有以上结构特点的模型就是线性规划模型，记为型，记为LPLP（Linear ProgrammingLinear Programming），具有以），具有以下一般形式：下一般形式：（三）线性规划的标准模型（三）线性规划的标准模型 由于目标函数既可以是实现最大化，由于目标函数既可以是实现最大化，也可以是实现最小化，约束条件可以是等也可以是实现最小化，约束条件可以是等式，也可以是

5、不等式，决策变量为非负或式，也可以是不等式，决策变量为非负或不受限制，这么复杂的情况，一定会给模不受限制，这么复杂的情况，一定会给模型的求解带来不便，为此引入标准形式型的求解带来不便，为此引入标准形式标准形式标准形式 （四）线性规划数学模型标准形式的特点（四）线性规划数学模型标准形式的特点 2 2、约束条件均为线性；、约束条件均为线性；3 3、决策变量及、决策变量及方程右端非负方程右端非负。线性规划数学模型标准形式可以有向量线性规划数学模型标准形式可以有向量形式表示：形式表示：1 1、目标函数为最大化类型（有的书上为、目标函数为最大化类型（有的书上为最小化）；最小化）；1 1、如果目标函数为最

6、小化问题，则将目、如果目标函数为最小化问题，则将目标函数两边乘以标函数两边乘以“-1”“-1”；2 2、如果约束方程右端为负，在该方程两端、如果约束方程右端为负，在该方程两端同乘以同乘以 “-1”“-1”；如果所建的模型不符合标准形式，则可以用如果所建的模型不符合标准形式，则可以用适当方法化为标准形式，主要有：适当方法化为标准形式，主要有：3 3、如果约束为、如果约束为 “”“”，则可以增加一，则可以增加一个变量个变量 ，在左端加上，在左端加上 ，这种变量，这种变量称为称为剩余变量剩余变量；4 4、如果约束为、如果约束为 “”“”，则可以增加一，则可以增加一个变量个变量 ，在右，在右 端加上端

7、加上 ，这种变量要求，这种变量要求非负，在线性规划中均称为非负，在线性规划中均称为松驰变量松驰变量；5 5、如果某决策变量、如果某决策变量 无符号限制，则将每无符号限制，则将每个个 换成换成 例：例：将下列线性规划模型化为标准形式将下列线性规划模型化为标准形式化成标准形式为：化成标准形式为：（一）基本概念：（一）基本概念：1 1、可行解可行解：所有满足约束条件：所有满足约束条件 的解。的解。2 2、可行域可行域：所有可行解组成的集合。：所有可行解组成的集合。4 4、最优值最优值：对应于最优解的目标函数值。：对应于最优解的目标函数值。3 3、最优解最优解：使得目标函数达到最优值的可：使得目标函数

8、达到最优值的可行解。行解。二、线性规划问题的解及单纯形法（解法）二、线性规划问题的解及单纯形法（解法）5 5、基基：约束方程组：约束方程组 的系数矩阵的系数矩阵为为 阶的矩阵阶的矩阵 则称则称A A的的任意一任意一个个 阶的非奇异阶的非奇异子矩阵子矩阵B B为线性规划的一为线性规划的一个个基基。6 6、基向量基向量：组成：组成基基B B的的列向量列向量 称为称为 基向量基向量。7 7、基变量基变量：基向量：基向量 对应对应的变量的变量 称为称为基变量基变量，基变量以外的变量称，基变量以外的变量称为为非基变量非基变量。9 9、基可行解基可行解：满足非负条件：满足非负条件 的基本解。的基本解。10

9、 10、可行基可行基：基可行解对应的基。：基可行解对应的基。11 11、基本最优解基本最优解：使目标函数达到最大值的基：使目标函数达到最大值的基可行解。可行解。12 12、最优基最优基：基本最优解对应的基。：基本最优解对应的基。8 8、基本解：基本解：在在 中，令中，令非基变量全非基变量全部为部为0 0，求出，求出 的一个解的一个解X X，称为，称为基本解基本解。1 1、基本思想基本思想：首先首先找出一个找出一个基可行基可行解解，然后然后根据根据某种最优性准则某种最优性准则判断该解是判断该解是否为最优，如果最优，则结束；否则利用否为最优，如果最优，则结束；否则利用某种迭代规则某种迭代规则寻找下

10、一个基可行解，并且寻找下一个基可行解，并且使下一个基可行解的使下一个基可行解的目标函数值有所改变目标函数值有所改变，反复多次，反复多次，直到找出最优解，或判断出原直到找出最优解，或判断出原问题无最优解问题无最优解。（二）单纯形法（二）单纯形法 为了确定为了确定初始初始基可行解基可行解，需要先找出初始可，需要先找出初始可行基。其方法是：观察约束方程组系数矩阵行基。其方法是：观察约束方程组系数矩阵 ，若其中有，若其中有子块为子块为m m阶单位矩阵阶单位矩阵 ，则可将其，则可将其选为初始可行基；否则，可采用所谓选为初始可行基；否则，可采用所谓人工变量法人工变量法寻找初始可行基寻找初始可行基。（1 1

11、）、确定）、确定初始初始基可行解并且计算相应的目基可行解并且计算相应的目标函数值标函数值2、计算步骤、计算步骤（3步）步）若若 的前的前m m列为单位阵（列为单位阵（作为基作为基），则），则约束方程约束方程 可化为可化为 为为基变量基变量，为为非基变量非基变量令令非基变量非基变量 即得即得初始初始基基可行解可行解。将方程组（将方程组（1 1）代入目标函数）代入目标函数 故对应于基可行解故对应于基可行解 的目标函数值的目标函数值 ，于是于是原线性规划模型等价于原线性规划模型等价于 此等价模型称为原线性规划的此等价模型称为原线性规划的典式典式，其中，其中 称为称为基本可行解基本可行解 的的检验数检

12、验数 （2 2）、根据检验数）、根据检验数 进行进行最优性检验与解的判断。最优性检验与解的判断。定理定理：若线性规划的基可行解：若线性规划的基可行解 对应的对应的典式为（典式为（1 1）并且检验数为）并且检验数为 、当存在某个检验数当存在某个检验数 时，并且典式（时，并且典式（1 1）中所有）中所有 时，时，线性规划无有限最优解线性规划无有限最优解。则则 、当当 时，时，是线性是线性规划的有限最优解；规划的有限最优解；、当存在检验数当存在检验数 且典式（且典式（1 1）中有些）中有些 ，这时采用迭代法，这时采用迭代法实现基可行解的转移。实现基可行解的转移。当初始基可行解当初始基可行解 不是最优

13、解，并且不能判不是最优解，并且不能判别无有限最优解时，需要另找一个别无有限最优解时，需要另找一个基可行解基可行解，并并使相应目标函数值增大使相应目标函数值增大，（即要对原可行基换一，（即要对原可行基换一个列向量）。为此需要确定个列向量）。为此需要确定进基变量进基变量和和出基变量出基变量的规则。的规则。（3 3）通过换基迭代，实现基可行解的转移通过换基迭代，实现基可行解的转移 进基变量的规则进基变量的规则：当某个当某个 时，增加时，增加 可以使得目标函可以使得目标函数值增加，故将数值增加，故将 作为进基变量。当有两个以上作为进基变量。当有两个以上的的 时，一般选择最大时，一般选择最大 对应的变量

14、对应的变量 为进基变量为进基变量 出基变量的规则：出基变量的规则：为了使得目标函数值增加得较快，进基变量为了使得目标函数值增加得较快，进基变量 的取值使得目标函数值尽可能的大，出基变量取哪的取值使得目标函数值尽可能的大，出基变量取哪一个，通过一个，通过 准则来确定。准则来确定。准则准则 反复进行以上步骤，即可获得线性规划反复进行以上步骤，即可获得线性规划的最优解，或判断出该线性规划无有限最优的最优解，或判断出该线性规划无有限最优解。解。其中其中 对应的对应的系系数数。称称为主元素为主元素（又称为（又称为中心元素中心元素），），主主元素所在行的基变量元素所在行的基变量 ，就是要确定的，就是要确定

15、的出出基变量基变量。单纯形表单纯形表：单纯形法的求解过：单纯形法的求解过程实际上是在程实际上是在一系列表格上进行的一系列表格上进行的。从这些表格上可以得到从这些表格上可以得到基本可行解基本可行解、检验数检验数等信息。这些表格称为等信息。这些表格称为单纯单纯形表形表。每个表相当于一个矩阵，每。每个表相当于一个矩阵，每次迭代就是对矩阵进行初等行变换。次迭代就是对矩阵进行初等行变换。例例：求解线性规划问题的最优解：求解线性规划问题的最优解 解：解：（1 1）构造初始单纯单纯形表（第）构造初始单纯单纯形表（第1 1、4 4、5 5列构成的矩阵可逆）所以可取列构成的矩阵可逆）所以可取为为初始初始基可行解

16、基可行解。因目标函数。因目标函数不是典式不是典式 ，故将，故将 代入目标函数代入目标函数z z，整理得，整理得 （典式典式）其中，其中，6 6为为 的目标函数值，此的目标函数值，此时可以列出单纯形表（如图）。时可以列出单纯形表（如图）。（2 2）迭代求新的基可行解及其检验数迭代求新的基可行解及其检验数 从上表格中可以看出，检验数从上表格中可以看出，检验数 大于大于0 0，不满足，不满足最优性准则最优性准则，须迭代求新解。取最，须迭代求新解。取最大的检验数大的检验数 对应的变量对应的变量 为为进基变量进基变量。它取代谁呢？它取代谁呢？再由再由 准则，用表格最右侧元素准则，用表格最右侧元素分别与表

17、格中分别与表格中 所在列的各元素去比，求最小所在列的各元素去比，求最小值值 最小值最小值4 4对应表格中基变量为对应表格中基变量为 ，故，故 为为出基变量出基变量，元素，元素 为为中心元素中心元素。开始迭代开始迭代，将，将 所在列元素变为单位向所在列元素变为单位向量，检验数行也参加变换。同时将表格左侧列量，检验数行也参加变换。同时将表格左侧列中基变量中基变量 换成换成 得表（把得表（把x3x3所在的元素所在的元素化为化为1 1，然后再把其它行的元素化为零），然后再把其它行的元素化为零）令令 得第二个得第二个基可行解基可行解 表格的右下角说明，当前的目标值为表格的右下角说明，当前的目标值为 14

18、 14，目标值增量为目标值增量为8 8，另外上面的表格中仍然有，另外上面的表格中仍然有 仍然需要迭代求新解。仍然需要迭代求新解。继续迭代继续迭代 取取 为进基变量，并且用上表格最右端列元为进基变量，并且用上表格最右端列元素比上素比上 所在列相应元素，计算所在列相应元素，计算 最小比值对应上表中基变量最小比值对应上表中基变量 所在的行，所在的行，故故 为为出基变量出基变量 ，中心元素为，中心元素为 ，同上，同上述方法可知述方法可知 为为进基变量进基变量，于是得到下面的表，于是得到下面的表格格表格的右下角说明，当前的目标值为表格的右下角说明，当前的目标值为 14.5 14.5，目标值增量为目标值增

19、量为0.50.5，表格表格3 3中检验数中检验数 ，故得最优解为，故得最优解为：最优值为：最优值为：14.5下面利用下面利用LINGOLINGO软件求解软件求解LINGO9.0LINGOLINGO初始界面初始界面LINGOLINGO程序程序LINGOLINGO程序运行程序运行变量数量变量数量变量总数变量总数非线性变量数非线性变量数整数变量数整数变量数约束数量约束数量约束总数约束总数非线性约束个非线性约束个数数非零系数数量非零系数数量总数总数非线性项的系数个数非线性项的系数个数内存使用量内存使用量求解花费的时间求解花费的时间当前模型的类型当前模型的类型当当前前解解的的状状态态当当前前解解的的目目

20、标标函函数数值值求解器（求解程序）求解器（求解程序）状态框状态框当前约当前约束不满束不满足的总足的总量（不量（不是不满是不满足的约足的约束的个束的个数）实数）实数时该数时该值为值为0到到目目前前为为止止迭迭代代次次数数使使用用的的特特殊殊求求解解程程序序扩展扩展的求的求解器解器状态状态框框（求（求解程解程序）序）状态状态框框到目到目前为前为止找止找到的到的可行可行解的解的最佳最佳目标目标函数函数值值目目标标函函数数值值的的界界特特殊殊求求解解程程序序当当前前运运行行步步数数有有效效步步数数刷新本刷新本界面的界面的时间间时间间隔（秒）隔（秒）目标函数值目标函数值求解迭代次求解迭代次数数决策变量决

21、策变量非基变量非基变量基变量基变量给出最优的单纯形表中目给出最优的单纯形表中目标函数行变量对应的系数标函数行变量对应的系数（即各个变量的检验数，（即各个变量的检验数，基变量为基变量为0，非基变量对应，非基变量对应的值表示当该非基变量增的值表示当该非基变量增加一个单位时目标函数减加一个单位时目标函数减少的量（对少的量（对max型问题）型问题）例例1 1 加工奶制品的生产计划加工奶制品的生产计划问题：问题：一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1A1，A2A2两种两种奶制品，奶制品，1 1桶牛奶可以在甲类设备上用桶牛奶可以在甲类设备上用1212小时加小时加工成工成3 3公斤公斤A1A1

22、，或者在乙类设备上用，或者在乙类设备上用8 8小时加工小时加工成成4 4公斤公斤A2A2。根据市场需求，生产的。根据市场需求，生产的A1A1，A2A2全部全部能够售出，且每公斤能够售出，且每公斤A1A1获利获利2424元，每公斤元，每公斤A2A2获获利利1616元。现在加工厂每天能得到元。现在加工厂每天能得到5050桶牛奶的供桶牛奶的供应，每天正式工人总的劳动时间为应，每天正式工人总的劳动时间为480480小时，并小时，并且甲类设备每天至多能加工且甲类设备每天至多能加工100100公斤公斤A1A1，乙类设，乙类设备的加工能力没有限制。备的加工能力没有限制。试为该厂制订一个生试为该厂制订一个生产

23、计划，使每天获利最大？产计划，使每天获利最大？并且进一步讨论以并且进一步讨论以下下3 3个问题：个问题：1 1）若有）若有3535元可以买到元可以买到1 1桶牛奶，应否作这桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？项投资？若投资，每天最多购买多少桶牛奶？2 2）若可以聘用临时工人增加劳动时间，付）若可以聘用临时工人增加劳动时间，付给临时工人的工资最多是每小时几元？给临时工人的工资最多是每小时几元？3 3）由于市场需求变化，每公斤）由于市场需求变化，每公斤A1A1的获利增的获利增加到加到3030元，应否改变生产计划？元，应否改变生产计划？问题分析：问题分析：这个优化问题的目标是使每

24、天的获这个优化问题的目标是使每天的获利最大，要作的决策是生产计划，即每天用多利最大，要作的决策是生产计划，即每天用多少桶牛奶生产少桶牛奶生产A1A1，用多少桶牛奶生产，用多少桶牛奶生产A2A2，决策，决策受受3 3个条件的限制：个条件的限制：原料（牛奶）供应，劳动时原料（牛奶）供应，劳动时间、甲类设备的加工能力间、甲类设备的加工能力。将决策变量、目标。将决策变量、目标函数和约束条件用数学式子表示出来，就得到函数和约束条件用数学式子表示出来，就得到相应的数学模型。相应的数学模型。决策变量：决策变量：设每天用设每天用x1x1桶牛奶生产桶牛奶生产A1A1，用，用x2x2桶牛奶生产桶牛奶生产A2A2。

25、目标函数：目标函数：设每天获利为设每天获利为z z元，元，x1x1桶牛奶生桶牛奶生产产3x13x1公斤公斤A1A1，获利，获利24*3x124*3x1，x2x2桶牛奶生产桶牛奶生产4x24x2公斤公斤A2A2，获利，获利16*4x216*4x2，所以，所以z=72*x1+64*x2z=72*x1+64*x2。约束条件：约束条件：原料供应原料供应 生产生产A1A1，A2A2的原料总量不得超过的原料总量不得超过每天的供应，即每天的供应，即x1+x2=50;x1+x2=50;劳动时间劳动时间 生产生产A1A1，A2A2的原料总加工时间的原料总加工时间不得超过每天正式工人总的劳动时间，不得超过每天正式

26、工人总的劳动时间，即即 12*x1+8*x2=480 12*x1+8*x2=480；设备能力设备能力 A1 A1的产量不得超过甲类设备的的产量不得超过甲类设备的加工能力，加工能力，即即 3*x1=100 3*x1=0 x2=0 x1=0 x2=0；数学模型：数学模型：给出最优的单纯形表中目标给出最优的单纯形表中目标函数行变量对应的系数（即函数行变量对应的系数（即各个变量的检验数，基变量各个变量的检验数，基变量为为0 0，非基变量对应的值表，非基变量对应的值表示当该非基变量增加一个单示当该非基变量增加一个单位时目标函数减少的量（对位时目标函数减少的量（对maxmax型问题型问题）约束条件的右段通

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

28、数行变量对应的系数（即各个变量的检验数，（即各个变量的检验数，基变量为基变量为0，非基变量对应，非基变量对应的值表示当该非基变量增的值表示当该非基变量增加一个单位时目标函数减加一个单位时目标函数减少的量（对少的量（对max型问题）型问题）松弛或剩余（给出约松弛或剩余（给出约束对应的松弛变量的束对应的松弛变量的值。第值。第2、3行松弛变行松弛变量为量为0，说明两个约束，说明两个约束都是紧约束）都是紧约束）给出影子价格的值给出影子价格的值表示用单纯形法进表示用单纯形法进行了两次迭代行了两次迭代目标函数的系数和目标函数的系数和约束条件右端项在约束条件右端项在什么范围变化时，什么范围变化时，最优基保持

29、不变最优基保持不变目标函数中系数目标函数中系数变化的范围变化的范围最优基最优基：基本最优解对应的基。：基本最优解对应的基。目标函数中变目标函数中变量当前的系数量当前的系数目标函数的系数允目标函数的系数允许增加的幅度，最许增加的幅度，最优基保持不变优基保持不变目标函数的系数允目标函数的系数允许减少的幅度，最许减少的幅度，最优基保持不变优基保持不变约束条件中当前的右约束条件中当前的右端项最优基保持不变端项最优基保持不变约束条件中当前的右约束条件中当前的右端项允许变化的范围，端项允许变化的范围，最优基保持不变最优基保持不变约束条件中右端项约束条件中右端项允许增加的幅度最允许增加的幅度最优基保持不变优

30、基保持不变约束条件中右端项约束条件中右端项允许减少的幅度，允许减少的幅度，最优基保持不变最优基保持不变INFINITY表示正表示正无穷大无穷大问题：问题：例例1 1给出的给出的A1A1、A2A2两类奶制品的生产条件、两类奶制品的生产条件、利润，及工厂的资源限制全都不变。为了增加利润，及工厂的资源限制全都不变。为了增加工厂的利润，开发了奶制品的深加工技术：用工厂的利润，开发了奶制品的深加工技术：用2 2个时间和个时间和3 3元加工费，可将元加工费，可将1 1公斤公斤A1A1加工成加工成0.80.8公公斤高级奶制品斤高级奶制品B1B1，也可以将，也可以将1 1公斤公斤A2A2加工成加工成0.750

31、.75公斤高级奶制品公斤高级奶制品B2B2，每公斤，每公斤B1B1能获利能获利4444元，每元，每公斤公斤B2B2能获利能获利3232元。试为该厂制订一个生产销元。试为该厂制订一个生产销售计划，使每天的净利润最大，并且讨论以下售计划，使每天的净利润最大，并且讨论以下问题：问题：例例2 2 奶制品的生产销售计划奶制品的生产销售计划1 1）：）：若投资若投资3030元可以增加供应元可以增加供应1 1桶牛奶，投资桶牛奶，投资3 3元可以增加元可以增加1 1小时劳动时间，应否作这项投资？小时劳动时间，应否作这项投资？如每天投资如每天投资150150元，可以赚回多少？元，可以赚回多少？2 2）：每公斤高

32、级奶制品：每公斤高级奶制品B1B1、B2B2的获利经常有的获利经常有10%10%的波动，对制订的生产销售计划有无影响？的波动，对制订的生产销售计划有无影响？若每公斤若每公斤B1B1的获利下降的获利下降10%10%，计划应该变化吗？，计划应该变化吗？教材教材P83P83例例奶制品的生产销售计划程序奶制品的生产销售计划程序LINGOLINGO程序程序LINDOLINDO程序程序三、整数线性规划模型三、整数线性规划模型 变量取整数的线性规划称为整数线性变量取整数的线性规划称为整数线性规划，简称规划，简称整数线性规划，记为整数线性规划，记为IP。整数规划分为整数规划分为纯整数线性规划纯整数线性规划，记

33、为，记为PILP；混合整数规划混合整数规划，记为，记为MILP整数整数规划的特殊情况是规划的特殊情况是0-1规划规划，其变，其变量只取量只取0或者或者11、整数、整数规划模型及规划模型及分枝定界法分枝定界法由于整数由于整数规划模型比线性规划模型增规划模型比线性规划模型增加了取整的条件，所以一种自然的想法是加了取整的条件，所以一种自然的想法是利用线性规划的方法求解整数规划模型。利用线性规划的方法求解整数规划模型。但如直接对线性规划问题最优解取整往往但如直接对线性规划问题最优解取整往往得不到整数得不到整数规划的最优解。因为对线性规规划的最优解。因为对线性规划问题最优解取整以后，有时会破坏原问划问题

34、最优解取整以后，有时会破坏原问题的约束条件，但解却不是最优解。下面题的约束条件，但解却不是最优解。下面介绍对于纯整数和混合整数规划都适用的介绍对于纯整数和混合整数规划都适用的分枝定界法分枝定界法分枝定界法分枝定界法的一般步骤：的一般步骤：（1）称原整数规划问题为称原整数规划问题为A；不考虑；不考虑整数条件，相应的线性规划问题为整数条件，相应的线性规划问题为B；（2）解问题解问题B，如问题，如问题B无可行解，则无可行解，则停止，原问题停止，原问题A也无可行解；也无可行解；（3）如求得问题如求得问题B的最优解，检查它的最优解，检查它是否符合整数条件，如果满足整数条件，是否符合整数条件，如果满足整数

35、条件，它就是问题它就是问题A的最优解；如不满足整数条的最优解；如不满足整数条件，转下一步；件，转下一步；（4）在问题在问题B的解中，任意选一不符的解中，任意选一不符合整数条件的变量合整数条件的变量，假设，假设的值为的值为，则，则作两个后继问题：作两个后继问题：它们是对问题它们是对问题B B的约束条件。的约束条件。（5）不考虑整数条件解这两个后继问不考虑整数条件解这两个后继问题；题；（6）在现有并且还未分解出各后继问在现有并且还未分解出各后继问题的各可行解中，选择目标函数值为最优题的各可行解中，选择目标函数值为最优的问题，重新称该问题为的问题，重新称该问题为B，转（，转（3）。）。例：设有整数规

36、划模型例：设有整数规划模型为整数为整数首先不考虑整数的条件，求解线性规首先不考虑整数的条件，求解线性规划，得最优解：划，得最优解：任意选择任意选择非整数解变量非整数解变量。如。如，由于，由于，问题的解要求整数，所以分出两个约束。，问题的解要求整数，所以分出两个约束。从而把原问题分成两个子问题：从而把原问题分成两个子问题：问题问题S1：为整数为整数问题问题S2为整数为整数对子问题对子问题S1、S2，不考虑整数条件，不考虑整数条件，得最优解得最优解这两个仍然不满足整数的要求。所以继这两个仍然不满足整数的要求。所以继续对（续对（S1）和（）和（S2）分解。由于（）分解。由于（S1）的）的最优值最优值

37、Z=349.000比比，（，（S2S2）的最优值）的最优值Z=341.390Z=341.390大，所以先对大，所以先对（S1）进行分解。）进行分解。由于由于不满足整数要求，所以不满足整数要求，所以所以添加条件所以添加条件把（把（S1）分解成两）分解成两个后继问题（个后继问题（S11）和（）和（S12）。依次类推得）。依次类推得到最优解或判断无最优解。到最优解或判断无最优解。上述思想是分支定界的理论，但在利用上述思想是分支定界的理论，但在利用数学软件求解时可以省去。数学软件求解时可以省去。上述整数线性上述整数线性规划模型的规划模型的LINGOLINGO程序程序问题问题1.1.如何下料最节省如何下

38、料最节省?例例 钢管下料钢管下料 问题问题2.2.客户增加需求：客户增加需求：原料钢管原料钢管:每根每根1919米米 4 4米米5050根根 6 6米米2020根根 8 8米米1515根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3 3种。如何下料最节省？种。如何下料最节省？5 5米米1010根根 按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。切割模式切割模式余料余料1 1米米 4米米1根根 6米米

39、1根根 8米米1根根余料余料3米米4米米1根根6米米1根根6米米1根根合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米8米米1根根8米米1根根合理切割模式合理切割模式模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1：为满足客户需要，按照哪些种合理模式，每种为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？模式切割多少根原料钢管，最为节省？2.2.所用原料钢管总根数最少所用原

40、料钢管总根数最少 两种标准两种标准1.1.原料钢管剩余总余量最小原料钢管剩余总余量最小x xi i 表示按第表示按第i i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i i=1,2,7)=1,2,7)决策变量决策变量 模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015目标目标1 1（总余量）（总余量）按模式按模式2 2切割切割1212根根,按模式按模式5 5切割切割1515根，余料根，余料2727米米 最优解：最优解：x x2 2=12,=12,x x5 5=15,=15,其余为其余为0

41、0；最优值：最优值：2727。约束条件约束条件整数约束：整数约束：x xi i 为整数为整数相应的相应的LINGO程序程序目标目标2 2（总根数）（总根数）约束条件不变约束条件不变 最优解：最优解：x x2 2=15,=15,x x5 5=5,=5,x x7 7=5,=5,其余为其余为0 0；最优值：最优值：2525。xi 为整数当余料没有用处时，通常以总根数最少为目标当余料没有用处时，通常以总根数最少为目标 按模式按模式2 2切割切割1515根，按模式根，按模式5 5切割切割5 5根，根，按模式按模式7 7切割切割5 5根，共根，共2525根，余料根，余料3535米米 虽余料增加虽余料增加8

42、 8米，但减少了米，但减少了2 2根根 与目标与目标1 1的结果的结果“共切割共切割2727根，余料根，余料2727米米”相相比比 相应的相应的LINGO程序程序钢管下料问题钢管下料问题2 2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5 5米米1010根；切割模式不超过根；切割模式不超过3 3种。种。现有现有4 4种需求：种需求：4 4米米5050根，根，5 5米米1010根，根，6 6米米2020根，根，8 8米米1515根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决策变量决策变量 x

43、xi i 表示按第表示按第i i 种模式切割的种模式切割的原料钢管根数原料钢管根数(i i=1,2,3)=1,2,3)r r1 1i i,r r2 2i i,r r3 3i i,r r4 4i i 表示第表示第i i 种切割模式下，种切割模式下，每根原每根原料钢管料钢管生产生产4 4米、米、5 5米、米、6 6米和米和8 8米长的钢管的数量米长的钢管的数量目标函数（目标函数（总根数）总根数）约束条件约束条件模式合理模式合理：每根余料不超过：每根余料不超过3 3米米 上述问题属于整数非线性规划模型，模型上述问题属于整数非线性规划模型，模型求解比较困难，为此再引入适当的约束条件：求解比较困难，为此

44、再引入适当的约束条件：整数约束：整数约束：x xi i,r,r1 1i i,r r2 2i i,r r3 3i i,r r4 4i i(i i=1,2,3)=1,2,3)为整数为整数增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解由于每根原料钢管长由于每根原料钢管长1919米米原料钢管总根数下界：原料钢管总根数下界：需求：需求：4 4米米5050根，根，5 5米米1010根，根，6 6米米2020根，根，8 8米米1515根根特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1 1：切割成：切割成5050根根4 4米钢管，需米钢管，需1313根；根；模式模式2 2：切

45、割成：切割成1010根根5 5米和米和2020根根6 6米钢管，需米钢管，需1010根；根；模式模式3 3：切割成：切割成1515根根8 8米钢管，需米钢管，需8 8根。根。原料钢管总根数上界：原料钢管总根数上界：13+10+8=31 13+10+8=31 模式排列顺序可任定模式排列顺序可任定 LINGOLINGO程序程序LINGOLINGO求解整数非线性规划模型求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.00000

46、0X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式模式1 1：每根原料钢管切割成：每根原料钢管切割成3 3根根4 4

47、米和米和1 1根根6 6米钢管，共米钢管，共1010根；根；模式模式2 2：每根原料钢管切割成：每根原料钢管切割成2 2根根4 4米、米、1 1根根5 5米和米和1 1根根6 6米钢管，米钢管，共共1010根；根；模式模式3 3：每根原料钢管切割成：每根原料钢管切割成2 2根根8 8米钢管，共米钢管，共8 8根。根。原料钢管总根数为原料钢管总根数为2828根。根。板材规格板材规格2 2：长方形，：长方形，3232 28cm28cm，2 2万张万张。例例易拉罐下料易拉罐下料模式模式1：1.5秒秒模式模式2：2秒秒模式模式3：1秒秒模式模式4：3秒秒板材规格板材规格1 1：正方形，边长：正方形，边

48、长24cm24cm，5 5万张万张。每周工作每周工作4040小时，每只易拉罐利润小时，每只易拉罐利润0.100.10元，原料余料损失元，原料余料损失0.0010.001元元/cm/cm2 2（不能装（不能装配的罐身、盖、底也是余料）配的罐身、盖、底也是余料）如何安排每周生产？如何安排每周生产？上盖上盖下底下底罐罐身身罐身高罐身高10cm10cm，上盖、下底直径均，上盖、下底直径均5cm5cm。模式模式1:1:正方形的边长正方形的边长24cm 24cm 问题分析问题分析计算各种模式下的余料损失计算各种模式下的余料损失 上、下底直径上、下底直径d d=5cm=5cm，罐身高，罐身高h h=10cm

49、=10cm。模式模式1 1 余料损失余料损失 24 242 2-10-10 d d2 2/4/4-dhdh=222.6=222.6 cmcm2 2罐身个数罐身个数底、盖底、盖个数个数余料损失余料损失（cm2）冲压时间冲压时间（秒（秒）模式模式1110222.61.5模式模式224183.32模式模式3016261.81模式模式445169.53问题分析问题分析目标目标:易拉罐利润扣除原料余料损失后的净利润最大易拉罐利润扣除原料余料损失后的净利润最大 约束约束：每周工作时间不超过每周工作时间不超过4040小时；小时；原料数量：规格原料数量：规格1 1（模式（模式1 31 3）5 5万张，万张，规

50、格规格2 2（模式（模式4 4）2 2万张；万张；罐身和底、盖的配套组装罐身和底、盖的配套组装 。注意：不能装配的罐身、上下底也是余料注意：不能装配的罐身、上下底也是余料决策变量决策变量 xi 按照第按照第i i 种模式的生产张数种模式的生产张数(i i=1,2,3,4)=1,2,3,4)；y1一周生产的易拉罐个数；一周生产的易拉罐个数；y2 不配套的罐身个数；不配套的罐身个数；y3 不配套的底、盖个数。不配套的底、盖个数。产量产量余料余料时间时间x1222.61.5x2183.32x3261.81x4169.53每只易拉罐利润每只易拉罐利润0.100.10元，余料损失元，余料损失0.0010