第1章线性规划及单纯形法.ppt

1、Operations Research(OR)夫运筹于帷幄之中，夫运筹于帷幄之中，决胜于千里之外决胜于千里之外运筹：军事用语，排兵布阵运筹：军事用语，排兵布阵Operation:军事行动军事行动 规划、调度规划、调度历史背景：战争历史背景：战争|运筹学运筹学主要研究经济活动与军事主要研究经济活动与军事活动中能用数量来表达有关运用、活动中能用数量来表达有关运用、筹划与管理方面的问题。它根据筹划与管理方面的问题。它根据问题地要求，通过数学的分析与问题地要求，通过数学的分析与运算，作出综合防治性的合理安运算，作出综合防治性的合理安排，以达到较经济较有效地使用排，以达到较经济较有效地使用人力物力。人力

2、物力。|运筹学运筹学是应用分析、试验、量化是应用分析、试验、量化的方法对经济管理系统中人力、的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，为决策者提供有依据的最优方案，以实现最有效的管理。以实现最有效的管理。|起源：古代战争、娱乐、建设起源：古代战争、娱乐、建设|学科产生：第二次世界大战学科产生：第二次世界大战|问题：合理利用稀缺战争资源问题：合理利用稀缺战争资源保护自己、消灭敌人保护自己、消灭敌人|扩展：战后用于民用事业扩展：战后用于民用事业|成型：各个分支成熟成型：各个分支成熟|成熟：计算机、信息技术结合成熟：计算机、

3、信息技术结合|发展：学科结合、渗透发展：学科结合、渗透 应用广度和深度、方法和算应用广度和深度、方法和算法的完善法的完善 确定目标，明确约束确定目标，明确约束 抓主要矛盾、舍次要矛盾抓主要矛盾、舍次要矛盾 选择模型、设定变量选择模型、设定变量 描述约束和目标、确定参数描述约束和目标、确定参数 选择求解方法、求解工具选择求解方法、求解工具 检验解，灵敏度分析检验解，灵敏度分析 谁、什么时间、如何。谁、什么时间、如何。提出问题提出问题建立模型建立模型优化求解优化求解检验分析检验分析方案实施方案实施|规划理论规划理论 线性规划线性规划 非线性规划非线性规划 运输问题运输问题 整数规划整数规划 动态规

4、划动态规划 目标规划目标规划|图与网络理论图与网络理论|排队论排队论|存储论存储论|决策论决策论|对策论对策论|冲突分析冲突分析|搜索论搜索论|可靠性理论可靠性理论|计划协调技术计划协调技术|图解协调技术图解协调技术课程内容：课程内容：线性规划及单纯形法线性规划及单纯形法线性规划的对偶理论线性规划的对偶理论运输问题运输问题 整数规划整数规划 目标规划目标规划考核办法：考核办法：总评平时成绩总评平时成绩10%+实验实验成绩成绩20+期末考试期末考试70%一般线性规划问题的数学模一般线性规划问题的数学模型型图解法图解法单纯形法原理单纯形法原理单纯形法的计算步骤单纯形法的计算步骤应用举例应用举例 线

5、性规划与单纯形法线性规划与单纯形法 第一章第一章|问题的提出问题的提出|线性规划的概念和模型线性规划的概念和模型|线性规划的标准型线性规划的标准型|线性规划的解线性规划的解一般线性规划问题的一般线性规划问题的 数学模型数学模型第一节第一节 例例 某工厂生产某工厂生产A、B、C三种产品，三种产品，每吨利润分别为每吨利润分别为2千元，千元，3千元，千元，3千元；千元；生产单位产品所需的工时及原材料如下生产单位产品所需的工时及原材料如下表所示。若供应的原材料每天不超过表所示。若供应的原材料每天不超过9t，所能利用的劳动力日总工时为所能利用的劳动力日总工时为3个单位，个单位，问如何制定日生产计划，使三

6、种产品总问如何制定日生产计划，使三种产品总利润最大？利润最大？产产品品生产每吨生产每吨产品所需产品所需资源资源资资 源源 A B C 工工 时时 材材 料料 1 1 1 1 4 7问题：工时和材料的日可供量已知问题：工时和材料的日可供量已知 求使利润最大的生产方案求使利润最大的生产方案解：产品解：产品A，B，C的日生产量：的日生产量：x1，x2，x3每日工时每日工时=x1+x2+x3 每日消耗材料量每日消耗材料量=x1+4x2+7x3每天可得利润（以千元为单位）每天可得利润（以千元为单位）Z=2x1+3x2+3x3利润最大利润最大工时约束工时约束材料约束材料约束非负约束非负约束 321332m

7、axxxxZ0,0,09743.321321321xxxxxxxxxtsMax：maximize，“最大化最大化”定义：定义：对于求取一组变量对于求取一组变量xj(j=1,2,.,n)，使之既满足线使之既满足线性约束条件，又使具有线性的性约束条件，又使具有线性的目标函数取得极值的一类最优目标函数取得极值的一类最优化问题称为化问题称为线性规划问题线性规划问题。max（或或min）nnxcxcxcZ2211自由,00,),(),(),(.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats一般形式：一般形式：max（或或min）自由

8、,00,),(),(),(.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxatsnnxcxcxcZ2211目标函数目标函数约束条件约束条件非负约束非负约束称为称为决策变量决策变量),2,1(njxj称为称为价值系数价值系数或或目标函数系数目标函数系数),2,1(njcj称为称为资源常数资源常数或或约束右端常数约束右端常数),2,1(mibi称为称为技术系数技术系数或或约束系数约束系数(1,2,1,2,)ija im jn紧缩形式：紧缩形式：max（或或min）njjjxcZ1njxbxatsjnjijij,2,10),(.1i=

9、1,2,.,m 矩阵形式：矩阵形式：max（或或min）称为称为决策变量向量决策变量向量 称为称为价值系数向量价值系数向量或或目标函数系数向量目标函数系数向量 称为称为资源常数向量资源常数向量或或约束右端常数向量约束右端常数向量 称为称为技术系数技术系数或或约束系数矩阵约束系数矩阵 CXZ0XbAXts),(.nxxxX21),(21ncccCmnmmnnaaaaaaaaaA212222111211mbbbb21线性规划模型特点：线性规划模型特点：用一组未知变量（决策变量）表示用一组未知变量（决策变量）表示要求的方案。通常，根据决策变量要求的方案。通常，根据决策变量所代表的事物的特点可以对变量

10、的所代表的事物的特点可以对变量的取值加以约束，例如非负约束。取值加以约束，例如非负约束。存在一定的限制条件，通常称为约存在一定的限制条件，通常称为约束条件，这些约束条件可以用一组束条件，这些约束条件可以用一组线性等式或者线性不等式来表示。线性等式或者线性不等式来表示。有一个目标要求，并且可以表示为有一个目标要求，并且可以表示为决策变量的线性函数，称为目标函决策变量的线性函数，称为目标函数，按所研究问题的不同，要求目数，按所研究问题的不同，要求目标函数实现最大化或者最小化。标函数实现最大化或者最小化。标准型的主要特征：标准型的主要特征：目标最大；目标最大；约束等式；约束等式；变量非负；变量非负；

11、右端非负。右端非负。nnxcxcxcZ2211max0,.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxat s标准型的紧缩形式：标准型的紧缩形式：njjjxcZ1maxnjxmibxatsjnjijij,2,10,2,1.1标准型的矩阵形式：标准型的矩阵形式：CXZ max0.XbAXts标准型的向量形式：标准型的向量形式：njjjxcZ1maxnjxbxptsjnjjj,2,10.1其中：其中：mjjjjaaap21标标准准化化把一般的把一般的LP化成标准型的过程化成标准型的过程称为称为线性规划问题的标准化线性规划问题的标准

12、化 方法：方法：1 目标标准化目标标准化 min Z=-max(-Z)2 化约束为等式化约束为等式 加松弛变量、减剩余变量加松弛变量、减剩余变量 3 变量非负化变量非负化 做变换做变换 或或 4 右端非负右端非负jjxxjjjxxx 0 jx0jx标标准准化化标准化举例：标准化举例：32132minxxxZ符号不受限制321321321321,0,1382310.xxxxxxxxxxxxts1233max23Zxxxx1233412335123312334510328.31,0 xxxxxxxxxxs txxxxx xxxxx可行解：可行解：满足所有约束条件的解满足所有约束条件的解.可行域：可

13、行域：即可行解的集合即可行解的集合.满足所有约束条件满足所有约束条件的解的集合，称为可行域的解的集合，称为可行域.最优解：最优解：使得目标函数达到最优的可行解使得目标函数达到最优的可行解.最优值：最优值：最优解对应的目标函数值最优解对应的目标函数值.CXZ max0.XbAXts先研究先研究AX=b设设 系数矩阵系数矩阵A是是mn矩阵，秩为矩阵，秩为m，B是是A中中mm阶阶非奇异子矩阵非奇异子矩阵（即（即|B|0），），则称则称B是线性规划问题是线性规划问题的一个的一个基基。B 是由是由m个线性独立的列向量组成个线性独立的列向量组成),(21mrrrpppB),2,1(mjxrj基向量基向量

14、基变量基变量非基变量非基变量：其余变量其余变量AX=BXB+NXN=b令令 非基变量非基变量XN=0 得得BXB=b和特解和特解XB=B-1b,结合结合XN=0 得得称为对应于称为对应于B的的基解基解.基解个数基解个数=基的个数基的个数Cnm基可行解基可行解:满足变量非负约束的基解满足变量非负约束的基解.XB0 XN=0 可行基可行基：对应于基可行解的基：对应于基可行解的基.NBTnXXxxxX),(21A=（B|N）12(,.,0,.,0)TmXx xx例例 在下述线性规划问题中在下述线性规划问题中,列出全部列出全部基、基解、基可行解和指出最优解基、基解、基可行解和指出最优解12314252

15、212416.5150(1,.,5)jxxxxxstxxxj12max23Zxx用作图的方法确定可行域，判用作图的方法确定可行域，判断目标函数的大小，达到求断目标函数的大小，达到求解的目的解的目的优点优点:直观性强直观性强,计算方便计算方便适用对象：适用对象：仅有两个变量的仅有两个变量的LP问题问题 步骤：步骤：建立平面坐标系建立平面坐标系,将约束条件将约束条件在图上表示在图上表示.|确立满足约束条件的解的范确立满足约束条件的解的范围围.作目标函数等值线作目标函数等值线平移目标函数等值线平移目标函数等值线确定最优解确定最优解例例1 用图解法求解下面的线性规用图解法求解下面的线性规划问题：划问题

16、：2152maxxxZ0,02224.21212121xxxxxxxxts2x1+5x2=10-x1+2x2=2 2x1+5x2=0 x1+x2=4 0 1 2 3 4 x1x2 G4321FEHABCDI x1-x2=2 例例2 用图解法求解下面的线性规用图解法求解下面的线性规划问题：划问题：2122maxxxZ0,02224.21212121xxxxxxxxts-x1+2x2=2 x1-x2=2 x1+x2=4 0 1 2 3 4 x1x2 G4321FEHABCDI例例3 用图解法求解下面的线性用图解法求解下面的线性规划问题：规划问题：212minxxZ0,0302.21121xxxxx

17、tsx1+2x2=4 x1+2x2=6 0 1 2 3 4 x1 x1=3X2321-x1+2x2=0例例4 用图解法求解下面的线性用图解法求解下面的线性规划问题：规划问题：212minxxZ0,0302.21121xxxxxts0 1 2 3 4 x1 x1=3X2321-x1+2x2=0例例5 用图解法求解下面的线性规用图解法求解下面的线性规划问题：划问题：212maxxxZ0,0302.21121xxxxxtsx1+2x2=4 x1+2x2=6 0 1 2 3 4 x1 x1=3X2321-x1+2x2=0例例6 用图解法求解下面的线性用图解法求解下面的线性规划问题：规划问题：212ma

18、xxxZx1+x2=1 0 1 2 3 4 x1 X2321-x1+2x2=40,0142.212121xxxxxxts 可行域可行域 最优解最优解 空集空集 无最优解无最优解 有界集有界集 唯一最优解唯一最优解 无界集无界集无穷多个最优解无穷多个最优解没有有限最优解没有有限最优解|LP的解的情况有的解的情况有:唯一最优解唯一最优解,无穷多个最优解无穷多个最优解,无界解无界解,无可无可行解行解.|若若LP的可行域存在的可行域存在,则可行域则可行域是一个凸集是一个凸集.|若若LP的最优解存在的最优解存在,则最优解则最优解或最优解之一定能够在可行或最优解之一定能够在可行域的某个顶点达到域的某个顶点

19、达到.|求解思路求解思路?图解法的启示图解法的启示|先找出凸集的任一顶点先找出凸集的任一顶点,计算计算在顶点处的目标函数值在顶点处的目标函数值.比较比较周围相邻的目标函数值是否比周围相邻的目标函数值是否比这个值更优这个值更优,如果为否如果为否,则该顶则该顶点就是最优解的点或最优解的点就是最优解的点或最优解的点之一点之一,否则转到比这个点的否则转到比这个点的目标函数值更优的另一顶点目标函数值更优的另一顶点,重复上述过程重复上述过程,一直找出使目一直找出使目标函数值最优的顶点为止标函数值最优的顶点为止.求一个初始基本可行解求一个初始基本可行解 是是 判断基本可行解是否最优判断基本可行解是否最优 结

20、结 束束 不是不是 求使目标得到改善的基本可行解求使目标得到改善的基本可行解 是否存在？是否存在？如何得到？如何得到？是否唯一？是否唯一？如何判断？如何判断？如何改善？如何改善？如何判断没有有限最优解？如何判断没有有限最优解？|3-1 预备知识预备知识|凸集凸集 如果集合如果集合C中任意两中任意两点点 X1,X2,其连线上的所有点也都其连线上的所有点也都是集合是集合C中的点中的点,称称C为为凸集凸集.|顶点顶点 凸集凸集C中满足下述条中满足下述条件的点称为件的点称为顶点顶点:如果如果C中不存在中不存在任何两个不同的点任何两个不同的点X1,X2,使使X成成为这两个点连线上的一个点为这两个点连线上

21、的一个点.|3-2 几个基本定理几个基本定理|定理定理1若线性规划问题存在可行若线性规划问题存在可行解解,则问题的可行域是凸集则问题的可行域是凸集.|引理引理 线性规划问题的可行解线性规划问题的可行解 X=(x x1 1,x,x2 2,x xn n)T T为基可行解的充为基可行解的充要条件是要条件是 X 的正分量所对应的系的正分量所对应的系数列向量是线性无关的数列向量是线性无关的.z 定理定理2 线性规划问题的基可行线性规划问题的基可行解解X对应线性规划问题可行域对应线性规划问题可行域(凸集凸集)的顶点的顶点.|定理定理3 若线性规划问题有最优若线性规划问题有最优解解,一定存在一个基可行解是最

22、优一定存在一个基可行解是最优解解.njjjxcZ1maxnjxbpxtsjnjjj,2,10.1mnnjjnjjjxxcZ110max0,.212211222222121111212111mnmmnnmnmmnnnnnnxxxbxxaxaxabxxaxaxabxxaxaxatsmnnjjnjjjxxcZ110max0,.212211222222121111212111mnmmnnmnmmnnnnnnxxxbxxaxaxabxxaxaxabxxaxaxats100010001),(21mnnnpppBTmbbbX),0,0,0(21基基基可行解基可行解bxPmiii10mnmjmmmnjmnjm

23、njmmbaaabaaabaaabpppppp,1,2,2,21,21,1,11,1121100010001)(TmxxxX)0,0,(0001()2设初始基可行解为设初始基可行解为则有则有其系数矩阵的增广矩阵为其系数矩阵的增广矩阵为bPPaxPaPPaPjmiiijimiiijjmiiijj1011)()0(0)(0miiijjPaP1TmjmjaxaxX)0,0,(0101)1(则找到满足则找到满足 的另一个点的另一个点则则bxPmjjj100ijiax.)(0)(00|min)1(000是一个新的基可行解则则令Xliliaxaxaaxijiljlijijii)1(X要使要使 是一个基可行

24、解是一个基可行解,应对所有应对所有 存在存在且这些等式中至少有一个等号成立且这些等式中至少有一个等号成立.mi,.,1检检验验数数记记分分别别代代入入目目标标函函数数得得和和j j)()()(111010)1(10)0()1()0(miijijjjmiijijmiijijmiimiiacczcaccxccaxcZxcZXXiii将将基基可可行行解解(1)当所有的当所有的 j 0时时,当前基可行解当前基可行解 为最优解为最优解.0(2)当所有的当所有的 j 0,又对某个非基变量又对某个非基变量xj 有有cj-zj=0,且可找到且可找到 ,则则有无穷多个最优解有无穷多个最优解.(3)如果存在某个如

25、果存在某个 j 0,又又Pj 向量的所向量的所有分量有分量aij 0,则存在无界解则存在无界解.第一步第一步:求出线性规划的初始基求出线性规划的初始基可行解可行解,列出初始单纯形表列出初始单纯形表.初始单纯形表初始单纯形表第二步第二步:进行最优性检验进行最优性检验如果表中所有检验数如果表中所有检验数 j，则表中的基可行解就是问题的最优解则表中的基可行解就是问题的最优解计算到此结束否则转下一步计算到此结束否则转下一步第三步第三步:从一个基可行解转换到另从一个基可行解转换到另一个目标函数值更大的基可行解一个目标函数值更大的基可行解列出新的单纯形表列出新的单纯形表 (1)确定确定进基变量进基变量 若

26、若 j 0，则可选则可选xj进基进基,当有一当有一个以上检验数大于零时个以上检验数大于零时,一般从中一般从中找出最大一个找出最大一个 k其对应的变量作为其对应的变量作为xk进基变量进基变量.max|0kjjj (2)确定确定出基变量出基变量 lklikikiabaab0min即即xl出基出基,目标改善目标改善.元素元素alk决定了从一个基本可行解决定了从一个基本可行解到另一个可行解的转移去向到另一个可行解的转移去向,取名取名主主元素元素.换基过程中若换基过程中若不存在不存在,则则Z，没有有限最优解没有有限最优解.(3)用进基变量用进基变量xk替换出基变量替换出基变量 ，得，得到一个新的基本可行

27、解，并相应到一个新的基本可行解，并相应地可以画出一个新的单纯形表地可以画出一个新的单纯形表 第四步：重复第二，第三步一直到第四步：重复第二，第三步一直到计算终止计算终止|进基变量的选取进基变量的选取 若有不止一若有不止一个变量可以进基时个变量可以进基时,只取一个只取一个|最小比值最小比值 若有不止一个最若有不止一个最小比值时，只能选取其中之一小比值时，只能选取其中之一行对应的基变量出基行对应的基变量出基|最优解是否唯一最优解是否唯一 最优表中最优表中非基变量检验数等于零时非基变量检验数等于零时,可可能最优解不唯一能最优解不唯一.练练 用单纯形法求解下面的线性用单纯形法求解下面的线性规划问题：规

28、划问题：12max52Zxx12121123216515.4,0 xxxxstxx x|人工变量法人工变量法 当规划模型化为标准型后当规划模型化为标准型后,当其当其约束条件的系数矩阵中不存在单位约束条件的系数矩阵中不存在单位矩阵时矩阵时,须再添加新的变量须再添加新的变量,使其含有使其含有单位矩阵单位矩阵,此时的新加变量为此时的新加变量为人工变人工变量量,这种化为标准型的方法称为这种化为标准型的方法称为人工人工变量法变量法.|两阶段法两阶段法 第一阶段第一阶段:求解一个目标函数仅含有人工求解一个目标函数仅含有人工变量变量,且为最小化的线性规划问题且为最小化的线性规划问题,其有两种可能结果其有两种

29、可能结果:(1)目标函数最优值为目标函数最优值为0,则去掉人则去掉人工变量转入第二阶段工变量转入第二阶段;(2)目标函数最优值不为目标函数最优值不为0,则原问则原问题无可行解题无可行解,停止计算停止计算.|两阶段法两阶段法 第二阶段第二阶段:去掉第一阶段中的人工变量去掉第一阶段中的人工变量,将第一阶段得到的最优解作为初将第一阶段得到的最优解作为初始基可行解始基可行解,利用单纯形法继续进利用单纯形法继续进行迭代行迭代,直到终止直到终止.求一个初始基本可行解求一个初始基本可行解 是是 判断基本可行解是否最优判断基本可行解是否最优 结结 束束 不是不是 求使目标得到改善的基本可行解求使目标得到改善的

30、基本可行解 是否存在？是否存在？如何得到？如何得到？是否唯一？是否唯一？如何判断？如何判断？如何改善？如何改善？如何判断没有有限最优解？如何判断没有有限最优解？CXZ max0.XbAXts)(),(2121222211211NBpppaaaaaaaaaAnmnmmnnNBTnXXxxxX),(21)(NBCCCbNXBXXXNBAXNBNB)(NNBNXBbBNXbBX111)(CXZ max0.XbAXtsNNBNXBbBNXbBX111)(NNBBNBNBXCXCXXCCCXZ)(NBNBNNNBXNBCCbBCXCNXBbBC)()(1111NBCCBNN1NNBXbBCZ1NNBNX

31、BbBNXbBX111)(NNBBNBNBXCXCXXCCCXZ)(NBNBNNNBXNBCCbBCXCNXBbBC)()(1111NBCCBNN1NNBXbBCZ11BCB01BBBBBXBCXCXAcbZ)(CB XB cjCBCN xj b XBTXNTCBTXBB-1b B-1BB-1N-CB B-1b CB-CB B-1B CN-CB B-1N单纯形表的矩阵形式单纯形表的矩阵形式线性规划建模步骤线性规划建模步骤:设立决策变量；设立决策变量；明确约束条件并用变量的线性等式明确约束条件并用变量的线性等式或不等式表示；或不等式表示；用变量的线性函数表示目标，并确用变量的线性函数表示目标，并

32、确定是求极小还是极大；定是求极小还是极大；根据变量的物理性质研究变量是否根据变量的物理性质研究变量是否有非负性有非负性.1 1人力资源分配的问题人力资源分配的问题 例例1.1.某昼夜服务的公交线路每天各时间段内所需司机和乘某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：务人员数如下：设司机和乘务人员分别在各时间段开始时上班，并连续工设司机和乘务人员分别在各时间段开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员满足工作需要，又配备最少司机和乘务人员?分析：不同上班班次时段的分

33、析：不同上班班次时段的司机和乘务人员数司机和乘务人员数 结束时段结束时段开工时段开工时段1234566;00-10:0010:00-14:0014:00-18:0018:00-22:0022:00-2:002:00-6:0016:00-10:00 x1x1210:00-14:00 x2x2314:00-18:00 x3x3418:00-22:00 x4x4522:00-2:00 x5x562:00-6:00 x6x6每时段需要的每时段需要的总人数总人数607060502030.6,2,10302050607060.655443322161654321jxxxxxxxxxxxxxtsxxxxxx

34、minZj且为整数 解：设解：设 xi 表示第表示第i班次时班次时开始上班的司机和乘务开始上班的司机和乘务人员数人员数,这样我们建立如这样我们建立如下的数学模型下的数学模型:例例2.某企业生产甲、乙、丙三种产品，某企业生产甲、乙、丙三种产品，每一产品均须经过每一产品均须经过A、B两道工序两道工序。A工序有两种设备可完成，工序有两种设备可完成，B工序有三种设备可完工序有三种设备可完成，除甲产品和乙产品的成，除甲产品和乙产品的A工序可随意安排外，其余只能在要工序可随意安排外，其余只能在要求的设备上完成。加工单位产品所需工序时间及其他各项数据求的设备上完成。加工单位产品所需工序时间及其他各项数据的费

35、用有关资料见下表。试制订利润最大的产品加工方案。的费用有关资料见下表。试制订利润最大的产品加工方案。设备设备产品甲产品甲产品乙产品乙产品丙产品丙费用费用/有效台时有效台时A15 x110 x6300/6000A27 x29 x712 x8321/10000B16 x38 (x6+x7)250/4000B24 x411 x8783/7000B37 x5200/4000原料单价原料单价(元元/件件)0.250.350.5销售单价销售单价(元元/件件)1.252.002.82 生产计划问题生产计划问题解：用8个单下标变量分别表示3种产品在相应工序中的生产量，如表所示。在约束条件中需考虑 x1+x2=

36、x3+x4+x5线性规划模型的目标函数为（利润=收入-成本-加工费）：max z=(1.25-0.25)(x1+x2)+(2-0.35)(x6+x7)+(2.8-0.5)x8-0.05(5x1+10 x6)+0.0321(7x2+9x7+12x8)+0.0625(6x3+8x6+8x7)+0.111857(4x4+11x8)+0.057x5即:max z=0.75x1+0.7753x2+0.65x6+0.8611x7+0.6844x8-0.375x3-0.4474x4-0.35x5销售收入-原料成本加工费设备产品甲产品乙产品丙费用/有效台时A15 x110 x6300/6000A27 x29

37、x712 x8321/10000B16 x38 (x6+x7)250/4000B24 x411 x8783/7000B37 x5200/4000原料单价(元/件)0.250.350.5销售单价(元/件)1.252.002.8设备产品甲产品乙产品丙费用/有效台时A15 x110 x6300/6000A27 x29 x712 x8321/10000B16 x38 (x6+x7)250/4000B24 x411 x8783/7000B37 x5200/4000原料单价(元/件)0.250.350.5销售单价(元/件)1.252.002.8解：用解：用8个单下标变量分别表示个单下标变量分别表示3种产品

38、在相应工序中的生产种产品在相应工序中的生产量，如表所示。量，如表所示。在约束条件中需考虑在约束条件中需考虑 x1+x2=x3+x4+x5线性规划模型的目标函数为（利润线性规划模型的目标函数为（利润=收入收入-成本成本-加工费）：加工费）：max z=(1.25-0.25)(x1+x2)+(2-0.35)(x6+x7)+(2.8-0.5)x8-0.05(5x1+10 x6)+0.0321(7x2+9x7+12x8)+0.0625(6x3+8x6+8x7)+0.111857(4x4+11x8)+0.057x5即即:max z=0.75x1+0.7753x2+0.65x6+0.8611x7+0.68

39、44x8-0.375x3-0.4474x4-0.35x5销售收入销售收入-原料成本原料成本加工费加工费该问题线性规划模型为：该问题线性规划模型为：8,2,10)(04000770001144000886100012976000105.35.04474.0375.06844.08611.065.07753.075.0max543215847638726154387621jxxxxxxxxxxxxxxxxxtsxxxxxxxxZj量相等产品甲两道工序上的数有效台时约有效台时约束束例例3.现要做现要做100套钢架，每套用长为套钢架，每套用长为2.9m,2.1m和和1.5m的圆钢各一的圆钢各一根。已知

40、原料长根。已知原料长7.4m，问应如何下料使所用料最省？，问应如何下料使所用料最省？3 套裁套裁下料问题下料问题解：设案方案 i下料的原料根数为xi,根据上表的方案,可建立如下线性规划模型：方案 下料数(根)长度(m)123456782.9120101002.1002211301.531203104合计7.47.37.27.16.66.56.36残料00.10.20.30.80.91.11.4.8,2,1010043231003221002.)(8653217654364218765432181ixxxxxxxxxxxxxxxxtsxxxxxxxxxminZijj且为整数最小化总的下料根数.8

41、,2,1010043231003221002.)(4.11.19.08.03.02.01.0086532176543642187654321ixxxxxxxxxxxxxxxxtsxxxxxxxxminZi且为整数最小化总残料试比较模型产品名称产品名称规格要求规格要求单价单价(元元/kg)甲甲原材料原材料1不少于不少于50%,原材料原材料2不超过不超过25%50乙乙原材料原材料1不少于不少于25%,原材料原材料2不超过不超过50%35丙丙不限不限25 例例4某工厂要用三种原料某工厂要用三种原料1、2、3混合调配出三种不同规格的混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排

42、生产产品甲、乙、丙，数据如下表。问：该厂应如何安排生产,使利使利润为最大？润为最大？原材料名称原材料名称每天最多供应量每天最多供应量单价单价(元元/kg)11006521002536035 解：设解：设 xij 表示第表示第 i 种（种（i=1(甲甲)、i=2(乙乙)、i=3(丙丙)）产品中）产品中原料原料 j 的含量。（注意：正确定义决策变量。）的含量。（注意：正确定义决策变量。）这样我们建立数学模型时，要考虑：这样我们建立数学模型时，要考虑：对于甲：对于甲：x11，x12，x13；产品甲的产量为；产品甲的产量为 x11+x12+x13 对于乙：对于乙：x21，x22，x23；产品乙的产量为

43、；产品乙的产量为 x21+x22+x23 对于丙：对于丙：x31，x32，x33；产品丙的产量为；产品丙的产量为 x31+x32+x33 对于原料对于原料1：x11，x21，x31；原料；原料1的需求量为的需求量为 x11+x21+x31 对于原料对于原料2：x12，x22，x32；原料；原料2的需求量为的需求量为 x12+x22+x32 对于原料对于原料3：x13，x23，x33；原料；原料3的需求量为的需求量为 x13+x23+x33 目标函数：目标函数：利润最大，利润利润最大，利润=收入收入-原料支出原料支出 约束条件：约束条件：规格要求规格要求 4 个个 供应量限制供应量限制 3 个个

44、利润利润=总收入总收入-总成本总成本=甲乙丙三种产品的销售单价甲乙丙三种产品的销售单价*产品数量产品数量-甲乙丙使用的原料单价甲乙丙使用的原料单价*原料数原料数量量目标函数目标函数max z=50(x11+x12+x13)+35(x21+x22+x23)+25(x31+x32+x33)-65(x11+x21+x31)-25(x12+x22+x32)-35(x13+x23+x33)=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 产品名称产品名称单价单价(元元/kg)原材料名称原材料名称单价单价(元元/kg)甲甲50165乙乙35225丙丙25335

45、约束条件：约束条件：从第从第1个表中有，产品规格要求：个表中有，产品规格要求：x110.5(x11+x12+x13)x120.25(x11+x12+x13)x210.25(x21+x22+x23)x220.5(x21+x22+x23)产品名称产品名称规格要求规格要求单价单价(元元/kg)甲甲原材料原材料1不少于不少于50%,原材料原材料2不超过不超过25%50乙乙原材料原材料1不少于不少于25%,原材料原材料2不超过不超过50%35丙丙不限不限25约束条件：约束条件：从第从第2个表中个表中,生产甲乙丙的原材料的需求不生产甲乙丙的原材料的需求不能超过原材料的供应限额，故有能超过原材料的供应限额，

46、故有 (x11+x21+x31)100 (x12+x22+x32)100 (x13+x23+x33)60原材料名称原材料名称每天最多供应量每天最多供应量单价单价(元元/kg)11006521002536035通过整理，得到以下模型通过整理，得到以下模型.3,2,1;3,2,1,0)3(60)2(100)1(100%)502(05.05.05.0%)201(025.025.075.0%)252(025.075.025.0%)501(05.05.05.0.1040103015251533231332221231211132222123222113121113121133312221131211ji

47、xxxxxxxxxxxxxxxxxxxtsxxxxxxxminZij的供应限制原材料的供应限制原材料的供应限制原材料不少于产品乙原材料不少于产品乙原材料不少于产品甲原材料不少于产品甲原材料例例4 兴安公司有一笔兴安公司有一笔30万元的资金万元的资金,考虑今后三年内用于下列考虑今后三年内用于下列项目的投资项目的投资:(1)三年内的每年年初均可投资三年内的每年年初均可投资,每年获利为投资额的每年获利为投资额的20%,其本其本利可一起用于下一年投资利可一起用于下一年投资;(2)只允许第一年初投入只允许第一年初投入,于第二年末收回于第二年末收回,本利合计为投资额的本利合计为投资额的150%,但此类投资限额不超过但此类投资限额不超过15万元万元;(3)允许于第二年初投入允许于第二年初投入,于第三年末收回于第三年末收回,本利合计为投资额的本利合计为投资额的160%,但限额投资但限额投资20万元万元;(4)允许于第三年初投入允许于第三年初投入,年末收回年末收回,可获利可获利40%,但限额为但限额为10万万元元;试为该公司确定一个使得第三年末本利和为最大的投试为该公司确定一个使得第三年末本利和为最大的投资组合方案资组合方案.5 连续投资问题连续投资问题