线性规划模型PPT课件.ppt

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

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

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

3、或不等式；具有以上结构特点的模型就是线性规划模型，记为LP（Linear Programming），具有以下一般形式：（三）线性规划的标准模型 由于目标函数既可以是实现最大化，也可以是实现最小化，约束条件可以是等式，也可以是不等式，决策变量为非负或不受限制，这么复杂的情况，一定会给模型的求解带来不便，为此引入标准形式标准形式 （四）线性规划数学模型标准形式的特点 2、约束条件均为线性；3、决策变量及方程右端非负。线性规划数学模型标准形式可以有向量形式表示：1、目标函数为最大化类型（有的书上为最小化）；1、如果目标函数为最小化问题，则将目标函数两边乘以“-1”；2、如果约束方程右端为负，在该方程

4、两端同乘以 “-1”；如果所建的模型不符合标准形式，则可以用适当方法化为标准形式，主要有：3 3、如果约束为、如果约束为 “”，则可以增加一，则可以增加一个变量个变量 ，在左端加上，在左端加上 ，这种变量，这种变量称为称为剩余变量剩余变量；4 4、如果约束为、如果约束为 “”，则可以增加一，则可以增加一个变量个变量 ，在右，在右 端加上端加上 ，这种变量要求，这种变量要求非负，在线性规划中均称为非负，在线性规划中均称为松驰变量松驰变量；5 5、如果某决策变量、如果某决策变量 无符号限制，则将每无符号限制，则将每个个 换成换成 例：将下列线性规划模型化为标准形式化成标准形式为：（一）基本概念：1

5、 1、可行解可行解：所有满足约束条件：所有满足约束条件 的解。的解。2、可行域：所有可行解组成的集合。4、最优值：对应于最优解的目标函数值。3、最优解：使得目标函数达到最优值的可行解。二、线性规划问题的解及单纯形法（解法）5 5、基基：约束方程组：约束方程组 的系数矩阵的系数矩阵为为 阶的矩阵阶的矩阵 则称则称A A的的任意一任意一个个 阶的非奇异阶的非奇异子矩阵子矩阵B B为线性规划的一为线性规划的一个个基基。6 6、基向量基向量：组成：组成基基B B的的列向量列向量 称为称为 基向量基向量。7 7、基变量基变量：基向量：基向量 对应对应的变量的变量 称为称为基变量基变量，基变量以外的变量称

6、，基变量以外的变量称为为非基变量非基变量。9 9、基可行解基可行解：满足非负条件：满足非负条件 的基本解。的基本解。10、可行基：基可行解对应的基。11、基本最优解：使目标函数达到最大值的基可行解。12、最优基：基本最优解对应的基。8 8、基本解：基本解：在在 中，令中，令非基变量全非基变量全部为部为0 0，求出，求出 的一个解的一个解X X，称为，称为基本解基本解。1、基本思想：首先找出一个基可行解，然后根据某种最优性准则判断该解是否为最优，如果最优，则结束；否则利用某种迭代规则寻找下一个基可行解，并且使下一个基可行解的目标函数值有所改变，反复多次，直到找出最优解，或判断出原问题无最优解。（

7、二）单纯形法 为了确定为了确定初始初始基可行解基可行解，需要先找出初始可，需要先找出初始可行基。其方法是：观察约束方程组系数矩阵行基。其方法是：观察约束方程组系数矩阵 ，若其中有，若其中有子块为子块为m m阶单位矩阵阶单位矩阵 ，则可将其，则可将其选为初始可行基；否则，可采用所谓选为初始可行基；否则，可采用所谓人工变量法人工变量法寻找初始可行基寻找初始可行基。（1）、确定初始基可行解并且计算相应的目标函数值2、计算步骤（3步）若若 的前的前m m列为单位阵（列为单位阵（作为基作为基），则），则约束方程约束方程 可化为可化为 为为基变量基变量，为为非基变量非基变量令令非基变量非基变量 即得即得初

8、始初始基基可行解可行解。将方程组（将方程组（1 1）代入目标函数）代入目标函数 故对应于基可行解故对应于基可行解 的目标函数值的目标函数值 ，于是于是原线性规划模型等价于原线性规划模型等价于 此等价模型称为原线性规划的此等价模型称为原线性规划的典式典式，其中，其中 称为称为基本可行解基本可行解 的的检验数检验数 （2 2）、根据检验数）、根据检验数 进行进行最优性检验与解的判断。最优性检验与解的判断。定理定理：若线性规划的基可行解：若线性规划的基可行解 对应的对应的典式为（典式为（1 1）并且检验数为）并且检验数为 、当存在某个检验数当存在某个检验数 时，并且典式（时，并且典式（1 1）中所有

9、）中所有 时，时，线性规划无有限最优解线性规划无有限最优解。则则 、当当 时，时，是线性是线性规划的有限最优解；规划的有限最优解；、当存在检验数当存在检验数 且典式（且典式（1 1）中有些）中有些 ，这时采用迭代法，这时采用迭代法实现基可行解的转移。实现基可行解的转移。当初始基可行解当初始基可行解 不是最优解，并且不能判不是最优解，并且不能判别无有限最优解时，需要另找一个别无有限最优解时，需要另找一个基可行解基可行解，并并使相应目标函数值增大使相应目标函数值增大，（即要对原可行基换一，（即要对原可行基换一个列向量）。为此需要确定个列向量）。为此需要确定进基变量进基变量和和出基变量出基变量的规则

10、。的规则。（3）通过换基迭代，实现基可行解的转移 进基变量的规则进基变量的规则：当某个当某个 时，增加时，增加 可以使得目标函可以使得目标函数值增加，故将数值增加，故将 作为进基变量。当有两个以上作为进基变量。当有两个以上的的 时，一般选择最大时，一般选择最大 对应的变量对应的变量 为进基变量为进基变量 出基变量的规则：为了使得目标函数值增加得较快，进基变量为了使得目标函数值增加得较快，进基变量 的取值使得目标函数值尽可能的大，出基变量取哪的取值使得目标函数值尽可能的大，出基变量取哪一个，通过一个，通过 准则来确定。准则来确定。准则准则 反复进行以上步骤，即可获得线性规划的最优解，或判断出该线

11、性规划无有限最优解。其中其中 对应的对应的系系数数。称称为主元素为主元素（又称为（又称为中心元素中心元素），），主主元素所在行的基变量元素所在行的基变量 ，就是要确定的，就是要确定的出出基变量基变量。单纯形表：单纯形法的求解过程实际上是在一系列表格上进行的。从这些表格上可以得到基本可行解、检验数等信息。这些表格称为单纯形表。每个表相当于一个矩阵，每次迭代就是对矩阵进行初等行变换。例：求解线性规划问题的最优解 解：（1）构造初始单纯单纯形表（第1、4、5列构成的矩阵可逆）所以可取为为初始初始基可行解基可行解。因目标函数。因目标函数不是典式不是典式 ，故将，故将 代入目标函数代入目标函数z z，整

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

13、 ，故，故 为为出基变量出基变量，元素，元素 为为中心元素中心元素。开始迭代开始迭代，将，将 所在列元素变为单位向所在列元素变为单位向量，检验数行也参加变换。同时将表格左侧列量，检验数行也参加变换。同时将表格左侧列中基变量中基变量 换成换成 得表（把得表（把x3x3所在的元素所在的元素化为化为1 1，然后再把其它行的元素化为零），然后再把其它行的元素化为零）令令 得第二个得第二个基可行解基可行解 表格的右下角说明，当前的目标值为表格的右下角说明，当前的目标值为 1414，目标值增量为目标值增量为8 8，另外上面的表格中仍然有，另外上面的表格中仍然有 仍然需要迭代求新解。仍然需要迭代求新解。继续

14、迭代 取取 为进基变量，并且用上表格最右端列元为进基变量，并且用上表格最右端列元素比上素比上 所在列相应元素，计算所在列相应元素，计算 最小比值对应上表中基变量最小比值对应上表中基变量 所在的行，所在的行，故故 为为出基变量出基变量 ，中心元素为，中心元素为 ，同上，同上述方法可知述方法可知 为为进基变量进基变量，于是得到下面的表，于是得到下面的表格格 表格的右下角说明，当前的目标值为 14.5，目标值增量为0.5，表格表格3 3中检验数中检验数 ，故得最优解为，故得最优解为：最优值为：最优值为：14.5下面利用LINGO软件求解LINGO9.0LINGO初始界面LINGO程序LINGO程序运

15、行变量数量变量总数非线性变量数整数变量数约束数量约束总数非线性约束个数非零系数数量总数非线性项的系数个数内存使用量求解花费的时间当前模型的类型当前解的状态当前解的目标函数值求解器（求解程序）状态框当前约束不满足的总量（不是不满足的约束的个数）实数时该值为0到目前为止迭代次数使用的特殊求解程序扩展的求解器状态框（求解程序）状态框到目前为止找到的可行解的最佳目标函数值目标函数值的界特殊求解程序当前运行步数有效步数刷新本界面的时间间隔（秒）目标函数值求解迭代次数决策变量非基变量基变量给出最优的单纯形表中目标函数行变量对应的系数（即各个变量的检验数，基变量为0，非基变量对应的值表示当该非基变量增加一个

16、单位时目标函数减少的量（对max型问题）例1 加工奶制品的生产计划问题：一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在甲类设备上用12小时加工成3公斤A1，或者在乙类设备上用8小时加工成4公斤A2。根据市场需求，生产的A1，A2全部能够售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天至多能加工100公斤A1，乙类设备的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大？并且进一步讨论以下3个问题：1）若有35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2

17、）若可以聘用临时工人增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？问题分析：这个优化问题的目标是使每天的获利最大，要作的决策是生产计划，即每天用多少桶牛奶生产A1，用多少桶牛奶生产A2，决策受3个条件的限制：原料（牛奶）供应，劳动时间、甲类设备的加工能力。将决策变量、目标函数和约束条件用数学式子表示出来，就得到相应的数学模型。决策变量：设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2。目标函数：设每天获利为z元，x1桶牛奶生产3x1公斤A1，获利24*3x1，x2桶牛奶生产4x2公斤A2，获利16*4x2，所以z=72*

18、x1+64*x2。约束条件：原料供应 生产A1，A2的原料总量不得超过每天的供应，即x1+x2=50;劳动时间 生产A1，A2的原料总加工时间不得超过每天正式工人总的劳动时间，即 12*x1+8*x2=480；设备能力 A1的产量不得超过甲类设备的加工能力，即 3*x1=0 x2=0；数学模型：给出最优的单纯形表中目标函数行变量对应的系数（即各个变量的检验数，基变量为0，非基变量对应的值表示当该非基变量增加一个单位时目标函数减少的量（对max型问题）约束条件的右段通常看作资源，一般称“资源”剩余为零的约束为紧约束（有效约束）；目标函数看作“效益”成为紧约束的资源一旦增加，“效益必然跟着增加”L

19、INDO6.1LINDO程序灵敏性分析吗表示单纯形法在两次迭代后得到最优解表示最优目标值为3360（在LINDO中目标函数所在的行总是被认为是第一行）给出最优的单纯形表中目标函数行变量对应的系数（即各个变量的检验数，基变量为0，非基变量对应的值表示当该非基变量增加一个单位时目标函数减少的量（对max型问题）松弛或剩余（给出约束对应的松弛变量的值。第2、3行松弛变量为0，说明两个约束都是紧约束）给出影子价格的值表示用单纯形法进行了两次迭代目标函数的系数和约束条件右端项在什么范围变化时，最优基保持不变目标函数中系数变化的范围最优基：基本最优解对应的基。2023/3/3073目标函数中变量当前的系数

20、目标函数的系数允许增加的幅度，最优基保持不变目标函数的系数允许减少的幅度，最优基保持不变约束条件中当前的右端项最优基保持不变约束条件中当前的右端项允许变化的范围，最优基保持不变约束条件中右端项允许增加的幅度最优基保持不变约束条件中右端项允许减少的幅度，最优基保持不变INFINITY表示正无穷大问题：例1给出的A1、A2两类奶制品的生产条件、利润，及工厂的资源限制全都不变。为了增加工厂的利润，开发了奶制品的深加工技术：用2个时间和3元加工费，可将1公斤A1加工成0.8公斤高级奶制品B1，也可以将1公斤A2加工成0.75公斤高级奶制品B2，每公斤B1能获利44元，每公斤B2能获利32元。试为该厂制

21、订一个生产销售计划，使每天的净利润最大，并且讨论以下问题：例2 奶制品的生产销售计划1）：若投资30元可以增加供应1桶牛奶，投资3元可以增加1小时劳动时间，应否作这项投资？如每天投资150元，可以赚回多少？2）：每公斤高级奶制品B1、B2的获利经常有10%的波动，对制订的生产销售计划有无影响？若每公斤B1的获利下降10%，计划应该变化吗？教材P83例奶制品的生产销售计划程序LINGO程序LINDO程序三、整数线性规划模型 变量取整数的线性规划称为整数线性规划，简称整数线性规划，记为IP。整数规划分为纯整数线性规划，记为PILP；混合整数规划，记为MILP 整数 规划的特殊情况是0-1规划，其变

22、量只取0或者1 1、整数 规划模型及分枝定界法 由于整数 规划模型比线性规划模型增加了取整的条件，所以一种自然的想法是利用线性规划的方法求解整数规划模型。但如直接对线性规划问题最优解取整往往得不到整数 规划的最优解。因为对线性规划问题最优解取整以后，有时会破坏原问题的约束条件，但解却不是最优解。下面介绍对于纯整数和混合整数规划都适用的分枝定界法分枝定界法的一般步骤：（1）称原整数规划问题为A；不考虑整数条件，相应的线性规划问题为B；（2）解问题B，如问题B无可行解，则停止，原问题A也无可行解；（3）如求得问题B的最优解，检查它是否符合整数条件，如果满足整数条件，它就是问题A的最优解；如不满足整

23、数条件，转下一步；（4）在问题在问题B的解中，任意选一不符的解中，任意选一不符合整数条件的变量合整数条件的变量，假设，假设的值为的值为，则，则作两个后继问题：作两个后继问题：它们是对问题它们是对问题B B的约束条件。的约束条件。（5）不考虑整数条件解这两个后继问题；（6）在现有并且还未分解出各后继问题的各可行解中，选择目标函数值为最优的问题，重新称该问题为B，转（3）。例：设有整数规划模型例：设有整数规划模型为整数为整数首先不考虑整数的条件，求解线性规首先不考虑整数的条件，求解线性规划，得最优解：划，得最优解：任意选择任意选择非整数解变量非整数解变量。如。如，由于，由于，问题的解要求整数，所以

24、分出两个约束。，问题的解要求整数，所以分出两个约束。从而把原问题分成两个子问题：从而把原问题分成两个子问题：问题问题S1：为整数为整数问题问题S2为整数为整数对子问题对子问题S1、S2，不考虑整数条件，不考虑整数条件，得最优解得最优解这两个仍然不满足整数的要求。所以继这两个仍然不满足整数的要求。所以继续对（续对（S1）和（）和（S2）分解。由于（）分解。由于（S1）的）的最优值最优值Z=349.000比比，（，（S2S2）的最优值）的最优值Z=341.390Z=341.390大，所以先对大，所以先对（S1）进行分解。）进行分解。由于由于不满足整数要求，所以不满足整数要求，所以所以添加条件所以添

25、加条件把（把（S1）分解成两）分解成两个后继问题（个后继问题（S11）和（）和（S12）。依次类推得）。依次类推得到最优解或判断无最优解。到最优解或判断无最优解。上述思想是分支定界的理论，但在利用数学软件求解时可以省去。上述整数线性规划模型的LINGO程序问题1.如何下料最节省?例 钢管下料 问题2.客户增加需求：原料钢管原料钢管:每根每根1919米米 4 4米米5050根根 6 6米米2020根根 8 8米米1515根根 客户需求客户需求节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？5 5米米1010根根 按照客户需要在一根原料钢

26、管上安排切割的一种组合。切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根余料余料3米米4米米1根根6米米1根根6米米1根根合理切割模式的余料应小于客户需要钢管的最小尺寸余料余料3米米8米米1根根8米米1根根合理切割模式模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题1：为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？2.所用原料钢管总根数最少 两种标准1.原料钢管剩余总余量最小xi 表示按第i 种模式切割的原料钢管根数(i=1

27、,2,7)决策变量 模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015目标目标1 1（总余量）（总余量）按模式2切割12根,按模式5切割15根，余料27米 最优解：x2=12,x5=15,其余为0；最优值：27。约束条件约束条件整数约束：整数约束：x xi i 为整数为整数相应的LINGO程序目标2（总根数）约束条件不变 最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。xi 为整数当余料没有用处时，通常以总根数最少为目标当余料没有用处时，通常以总根数最少为目标 按模式按模式2 2切

28、割切割1515根，按模式根，按模式5 5切割切割5 5根，根，按模式按模式7 7切割切割5 5根，共根，共2525根，余料根，余料3535米米 虽余料增加虽余料增加8 8米，但减少了米，但减少了2 2根根 与目标与目标1 1的结果的结果“共切割共切割2727根，余料根，余料2727米米”相相比比 相应的LINGO程序钢管下料问题2对大规模问题，用模型的约束条件界定合理模式增加一种需求：5米10根；切割模式不超过3种。现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。决策变量 xi 表示按第i 种模式切割的原料钢管根数(i=1,2,3)r1i,r2

29、i,r3i,r4i 表示第i 种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量目标函数（总根数）约束条件约束条件模式合理：每根余料不超过3米 上述问题属于整数非线性规划模型，模型求解比较困难，为此再引入适当的约束条件：整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数增加约束，缩小可行域，便于求解由于每根原料钢管长由于每根原料钢管长1919米米原料钢管总根数下界：原料钢管总根数下界：需求：4米50根，5米10根，6米20根，8米15根特殊生产计划：对每根原料钢管模式1：切割成50根4米钢管，需13根；模式2：切割成10根5米和20根6米钢管，需10根；模式

30、3：切割成15根8米钢管，需8根。原料钢管总根数上界：13+10+8=31 模式排列顺序可任定 LINGO程序LINGO求解整数非线性规划模型Local optimal solution found at iteration:12211 Objective value:28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.0

31、00000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 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：长方形

32、，32 28cm，2万张。例 易拉罐下料模式模式1：1.5秒秒模式模式2：2秒秒模式模式3：1秒秒模式模式4：3秒秒板材规格1：正方形，边长24cm，5万张。每周工作40小时，每只易拉罐利润0.10元，原料余料损失0.001元/cm2（不能装配的罐身、盖、底也是余料）如何安排每周生产？上盖上盖下底下底罐罐身身罐身高10cm，上盖、下底直径均5cm。模式1:正方形的边长24cm 问题分析计算各种模式下的余料损失 上、下底直径d=5cm，罐身高h=10cm。模式1 余料损失 242-10 d2/4-dh=222.6 cm2罐身个数罐身个数底、盖底、盖个数个数余料损失余料损失（cm2）冲压时间冲压时

33、间（秒（秒）模式模式1110222.61.5模式模式224183.32模式模式3016261.81模式模式445169.53问题分析目标:易拉罐利润扣除原料余料损失后的净利润最大 约束：每周工作时间不超过40小时；原料数量：规格1（模式1 3）5万张，规格2（模式4）2万张；罐身和底、盖的配套组装。注意：不能装配的罐身、上下底也是余料决策变量 xi 按照第i 种模式的生产张数(i=1,2,3,4)；y1 一周生产的易拉罐个数；y2 不配套的罐身个数；y3 不配套的底、盖个数。产量产量余料余料时间时间x1222.61.5x2183.32x3261.81x4169.53每只易拉罐利润0.10元，余

34、料损失0.001元/cm2罐身面积 dh=157.1 cm2，底盖面积 d2/4=19.6 cm2目标函数 约束条件 原料约束原料约束 时间约束时间约束 (4040小时小时)约束条件 配套约束 罐身罐身底、盖底、盖1102401645产量产量x1x2x3x4虽然xi和y1，y2，y3应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理。将所有决策变量扩大10000倍（xi 万张，yi 万件）警告信息：“数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别”模式2生产40125张，模式3生产3750张，模式4生产20000张，共产易拉罐160250个(罐身和底、盖无剩余

35、)，净利润为4298元 OBJECTIVE FUNCTION VALUE 1)0.4298337VARIABLE VALUE REDUCED COST Y1 16.025000 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X3 0.375000 0.000000 X4 2.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484 下料问题的建模 确定下料模式确定下料模式 构造优化模型构造优化模型 规格不太多，可枚举下料模式，建立整规格不太多，可枚举下料模式，建立整数线性规划模型，

36、否则要构造整数非线性规数线性规划模型，否则要构造整数非线性规划模型，求解困难，可用划模型，求解困难，可用缩小可行域缩小可行域的方法的方法进行化简，但要保证最优解的存在。进行化简，但要保证最优解的存在。一维问题（如钢管下料）一维问题（如钢管下料）二维问题（如易拉罐下料）二维问题（如易拉罐下料）具体问题具体分析（比较复杂具体问题具体分析（比较复杂 ）四、0-1规划 接力队的选拔接力队的选拔 问题：某班准备从问题：某班准备从5 5名游泳队员中名游泳队员中选择选择4 4人组成接力队，参加学校的人组成接力队，参加学校的4 4100100米混合泳接力比赛。米混合泳接力比赛。5 5名队员名队员4 4种泳姿的

37、百米成绩如表所示，种泳姿的百米成绩如表所示，1 1）问应）问应该如何选拔队员组成接力队？该如何选拔队员组成接力队？2 2）如果最近队员丁的蛙泳成绩有较大）如果最近队员丁的蛙泳成绩有较大退步，只有退步，只有 ；而队员戊经过艰苦训练；而队员戊经过艰苦训练自由泳成绩有所进步，达到自由泳成绩有所进步，达到 组成接力组成接力队的方案是否应该调整？队的方案是否应该调整？甲甲乙乙丙丙丁丁戊戊蝶蝶 泳泳仰仰 泳泳蛙蛙 泳泳自由泳自由泳引入引入0-10-1变量变量 ，若选择队员，若选择队员i i参加泳姿参加泳姿j j，记，记 ，否则记为，否则记为0 0。根据组成接力队。根据组成接力队的要求，的要求，应该满足两个

38、约束条件：应该满足两个约束条件：记甲乙丙丁戊分别为队员记甲乙丙丁戊分别为队员记蝶泳、仰泳、蛙泳、自由泳分别为泳姿记蝶泳、仰泳、蛙泳、自由泳分别为泳姿记队员记队员i的第的第j种泳姿的百米最好成绩为种泳姿的百米最好成绩为（秒）（秒）第一、每人最多只能入选第一、每人最多只能入选4 4种泳姿之种泳姿之一，即对于一，即对于 ，应有，应有 第二、每人泳姿必须有第二、每人泳姿必须有1 1人，而且只人，而且只能有一人入选，即对于能有一人入选，即对于 应有应有 当队员当队员i入选泳姿入选泳姿j时，时，表示该同学的成绩，表示该同学的成绩，否则否则于是接力队的总成绩为（目标函数）于是接力队的总成绩为（目标函数）上述

39、问题的01规划模型为：课堂作业：某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原材料钢管长度都是1850mm。现有一客户需要15根290mm、28根315mm、21根350mm和30根455mm的钢管，为了简化生产过程，规定所使用的切割模式的种类不能超过4种，使用频率最高的一种切割模式按照一根钢管价值的十分之一增加费用，使用频率次之的一种切割模式按照一根钢管价值的十分之二增加费用，依次类推，且每种切割模式下的切割次数不能太多（一根原料钢管最多生产5根产品），此外，为了减少余料浪费，每种切割模式下的余料浪费不能超过100m。为了使总费用最小，应如何下料？2023/3/30145