筹学胡运权第五版课件.ppt

《筹学胡运权第五版课件.ppt》由会员分享，可在线阅读，更多相关《筹学胡运权第五版课件.ppt（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运 筹 学(Operations Research)一、古代朴素的运筹学思想一、古代朴素的运筹学思想例如：田忌赛马例如：田忌赛马二、运筹学的起源二、运筹学的起源国外国外英文原名英文原名 Operations Research 简称简称“O.R.”直译为：运用研究或作业研究直译为：运用研究或作业研究正式出现于正式出现于19381938年年7 7月英国一份关于防空作战系统运月英国一份关于防空作战系统运行的研究报告中行的研究报告中二战后运筹学的发展经历了三个阶段二战后运筹学的发展经历了三个阶段绪绪 论论国内国内19561956年成立第一个运筹学小组年成立第一个运筹学小组19571957年从年从“夫运

2、筹策帷幄之中，决胜于千里之外夫运筹策帷幄之中，决胜于千里之外”中中摘取摘取“运筹运筹”二字，将二字，将O.R.正式翻译为正式翻译为“运筹学运筹学”三、运筹学的定义三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供研究目的：对有限资源进行合理规划、使用，并提供 优化决策方案。优化决策方案。研究对象：复杂系统的组织和管理研究对象：复杂系统的组织和管理参考参考大英百科全书大英百科全书、辞海辞海、中国企业管理百科全书中国企业管理百科全书等。等。四、运筹学研究的基本特点四、运筹学研究的基本特点 系统的整体优化系统

3、的整体优化 多学科的配合多学科的配合 模型方法的应用模型方法的应用五、运筹学研究的基本步骤五、运筹学研究的基本步骤 分析与表述问题分析与表述问题 建立数学模型建立数学模型 对问题求解对问题求解 对模型和模型导出的解进行检验对模型和模型导出的解进行检验 建立对解的有效控制建立对解的有效控制 方案的实施方案的实施六、本课程的主要学习内容六、本课程的主要学习内容 第一章第一章 线性规划及单纯形法线性规划及单纯形法 第二章第二章 线性规划的对偶理论线性规划的对偶理论 第三章第三章 运输问题运输问题 第四章第四章 整数规划与分配问题整数规划与分配问题 第六章第六章 图与网络分析图与网络分析 第一章第一章

4、 线性规划及单纯形法线性规划及单纯形法Linear Programming and Simplex Methodxa此为无约束的极值问题此为无约束的极值问题1.1 一般线性规划问题的数学模型一般线性规划问题的数学模型1-1 1-1 问题的提出问题的提出例例1 1 用一块边长为用一块边长为a的正方形铁皮做一个无盖长方体容器，的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？应如何裁剪可使做成的容器的容积最大？解：如图设四个角上减去的小正方形边解：如图设四个角上减去的小正方形边长为长为x，则容器体积为：，则容器体积为：时，容积最大时，容积最大 例例2 2 常山机器厂生产常山机器

5、厂生产 I I、IIII 两型产品。这两型两型产品。这两型产品都分别要在产品都分别要在A A、B B、C C三种不同设备上加工。按三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：备的工时以及各种设备工时的限额如下表：如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？单位产品消耗设单位产品消耗设备工时备工时I IIIII设备工时限量设备工时限量（小时）（小时）设备设备A A设备设备B B设备设备C C2 24 40 02

6、 20 05 5121216161515单位利润（元）单位利润（元）2 23 3解：设计划期内两种产品的数量分别为解：设计划期内两种产品的数量分别为x1 1，x2 2，则总利润为：，则总利润为：maxz=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0，x2 0简记为：简记为：s.t.（约束于：）（约束于：）z=2 x1+3 x2在满足限制条件下求在满足限制条件下求z的最大值。的最大值。此为有约束极值问题此为有约束极值问题1-2 1-2 线性规划问题的数学模型线性规划问题的数学模型原型原型模型模型数学模型数学模型提炼提炼数学工具数学工具1 1、原型原型：现实世界

7、中人们关心、研究的实际对象。：现实世界中人们关心、研究的实际对象。模型模型：将某一部分信息简缩、提炼而构造的原型替代物。：将某一部分信息简缩、提炼而构造的原型替代物。数学模型数学模型：对现实世界的一个特定对象，为达到一定目的，：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设根据内在规律做出必要的简化假设,并运用适当数学工具得到并运用适当数学工具得到的一个数学结构。的一个数学结构。3 3、规划问题数学模型的三要素、规划问题数学模型的三要素（2 2）目标函数目标函数：问题要达到的目标要求，表示为决策变量的：问题要达到的目标要求，表示为决策变量的函数。用函数。用 z=f(x

8、1 1，x2 2，xn n)表示。表示。（1 1）决策变量决策变量：决策者为实现规划目标采取的方案、措施，：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用是问题中要确定的未知量。用x1 1，x2 2，xn n表示。表示。（3 3）约束条件约束条件：决策变量取值时受到的各种可用资源的限制，：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。表示为含决策变量的等式或不等式。2 2、规划问题、规划问题即求目标函数在若干约束条件下的最值。即求目标函数在若干约束条件下的最值。4 4、线性规划问题（、线性规划问题（Linear Programming）的数学模型）的

9、数学模型（2 2）一般形式一般形式：（1 1）条件条件：决策变量为可控的连续变量，目标函数和约束条：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为件都是线性的。简记为“L.P.”max(或或 min)z=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn （=，）b1 a21x1+a22x2+a2nxn （=，）b2 am1x1+am2x2+amnxn（=，）bm x1,x2,xn0（3 3）其他形式其他形式：连加形式连加形式向量形式向量形式其中 称为价值行向量价值行向量；决策列向量决策列向量系数列向量系数列向量右端列向量右端列向量矩阵形式矩阵形式其中 称

10、为价值行向量；称为价值行向量；决策列向量决策列向量右端列向量右端列向量约束矩阵或系数矩阵约束矩阵或系数矩阵1-3 1-3 线性规划问题的标准形式线性规划问题的标准形式1 1、标准形式、标准形式或或2 2、条件、条件目标函数求极大值目标函数求极大值约束条件全是等式（线性方程组）约束条件全是等式（线性方程组）决策变量全非负决策变量全非负右端常数全非负右端常数全非负3 3、标准化方法、标准化方法（1）若目标函数求极小值，即）若目标函数求极小值，即则令则令 转化为转化为（2 2）若约束条件为不等式，）若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），则依次引入松弛变量或剩余变量（统称

11、为松弛变量），转化为等式约束条件。转化为等式约束条件。注意注意：松弛变量在目标函数中系数全为：松弛变量在目标函数中系数全为0。约束为约束为不等式，减去松弛变量，化为等式约束条件；不等式，减去松弛变量，化为等式约束条件；约束为约束为不等式，加上松弛变量，化为等式约束条件。不等式，加上松弛变量，化为等式约束条件。多多退退少少补补例：例：max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0，x2 0 s.t.标准化标准化（3 3）若决策变量）若决策变量xj0，则令，则令（4 4）若决策变量）若决策变量xj取值无限制，则令取值无限制，则令（5 5）若约束等式的右

12、端常数）若约束等式的右端常数bi 0 0，则等式两边同时乘以，则等式两边同时乘以“-1-1”。其中其中（“一分为二一分为二”）例：例：将下列线性规划模型化为标准形式。将下列线性规划模型化为标准形式。则问题化为标准形式：则问题化为标准形式：并引入松弛变量并引入松弛变量x4,x5,1-4 1-4 线性规划问题的解线性规划问题的解已知线性规划的标准形式：已知线性规划的标准形式：或或1 1、求解线性规划问题求解线性规划问题：从满足（从满足（2）、（）、（3）的方程组中找出一个解使目标函）的方程组中找出一个解使目标函数（数（1）达到最大值。）达到最大值。2 2、可行解可行解：所有可行解的集合。所有可行解

13、的集合。可行域可行域：满足约束条件（满足约束条件（2）、（）、（3）的解。）的解。记做记做最优解最优解：使目标函数达到最大值的可行解。使目标函数达到最大值的可行解。（1 1）基基：设：设A A为线性规划问题约束条件的为线性规划问题约束条件的 m n 系数矩阵系数矩阵（m00，有如下结论：有如下结论：(1)(1)若对所有若对所有jm+1，有，有 j 0 0，则，则z（1）z（0），即，即z（0）为为最优函数值，最优函数值，X（0）为为唯一最优解唯一最优解；(2)(2)若对所有若对所有j m+1，有有 j 0，且，且存在某个非基变量的检验数存在某个非基变量的检验数 k=0，则将，则将Pk作为新的基

14、向量得出新的基可行解作为新的基向量得出新的基可行解X（1 1），满足，满足z（1）=z（0），故，故z（1）也也为最优函数值，从而为最优函数值，从而 X（1）也也为最优解，为最优解，X（0）、X（1）连线上所有点均为最优解，因此该线性规划连线上所有点均为最优解，因此该线性规划模型具有模型具有无穷多最优解无穷多最优解；(3)(3)若存在某个若存在某个 j 0 0，但对应的第，但对应的第j列系数全非正，即列系数全非正，即aij 0 0，则，则当当 +时，有时，有z（1）+，该线性规划模型具有该线性规划模型具有无界解无界解。1.4 1.4 单纯形法的计算步骤单纯形法的计算步骤1 1、前提：标准化的线

15、性规划问题的系数矩阵含有单位子矩阵。、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。不妨假设不妨假设A中前中前m列对应的子矩阵是单位列对应的子矩阵是单位矩阵，取其为基矩阵，取其为基B，得到初始基可行解，得到初始基可行解m+3行行n+4列列第第1行：价值行行：价值行 cj第第2行：变量行行：变量行 xj最后一最后一行：检验数行行：检验数行 j第第1列：基价值列列：基价值列 CB第第2列列：基变量列：基变量列 XB第第3列列：基解列：基解列 b最后一最后一列：列：比值比值列列 主体：系数矩阵主体：系数矩阵Amn2 2、单纯形表的结构、单纯形表的结构3 3、初始单纯形表：含初始基可行解的单纯形

16、表、初始单纯形表：含初始基可行解的单纯形表 最优单纯形表：含最优解的单纯形表最优单纯形表：含最优解的单纯形表4 4、单纯形法（、单纯形法（Simplex MethodSimplex Method）：）：利用单纯形表求解线性规划问题的方法。利用单纯形表求解线性规划问题的方法。5 5、单纯形法的计算步骤、单纯形法的计算步骤(1)(1)化化 L.P.问题为标准形式问题为标准形式,建立初始单纯形表；建立初始单纯形表；(3)(3)计算计算(4)(4)以以alk为主元素为主元素(简称主元，用简称主元，用 表示表示)，进行线性方程组，进行线性方程组 的的初等行变换，将主元列初等行变换，将主元列Pk化为单位向

17、量得到新的单纯形表，化为单位向量得到新的单纯形表，转入转入(2)(2)。（最大正检验数决定换入变量）（最大正检验数决定换入变量）（最小比值（最小比值决定换出变量决定换出变量）例：用单纯形法求解下列线性规划问题例：用单纯形法求解下列线性规划问题.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0，x2 0 s.t.解：先标准化解：先标准化Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 再列初始单纯形表：再列初始单纯形表：6-

18、32 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 1615 2 2 1 0 0 6 4 0 0 1 0 -0 5 0 0 1 3 2 3 0 0 0以以55为主元进为主元进行初等行变换行初等行变换Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 6 16 3 2 0 1 0 -2/5 3 4 0 0 1 0 4 0 1 0 0 1/5 -2 0 0 0 -3/5x1 1为换入变量为换入变量下面开始单纯形法迭代：下面开始单纯形法迭代：x5 5为换出变量为换出变量x2

19、2为换入变量为换入变量以以22为主元进为主元进行初等行变换行初等行变换x3 3为换出变量为换出变量主元化为主元化为1，主元列，主元列的其他元素化为的其他元素化为0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5此时得到唯一最优解此时得到唯一最优解X*=(3,3)T,Zmax=15=15。6、单纯形法中存在的问题、单纯形法中存在的问题（1 1）存在两个以上的最大正检验数。存在两个以上的最大正检验数。任取一个最大正检验数对应的变量作为换

20、入变量。任取一个最大正检验数对应的变量作为换入变量。（2 2）出现两个以上相同的最小值。出现两个以上相同的最小值。任取一个最小任取一个最小对应的变量作为换出变量。对应的变量作为换出变量。此时此时L.P.问题出现退化现象。问题出现退化现象。练习练习 用单纯形法求解下列线性规划问题用单纯形法求解下列线性规划问题解：先标准化解：先标准化 2 1 0 0 54 x3x400 x1 x2 x3 x4bxBcB 2 1 0 0cj 2415351 06201 0 0 x3x102 x1 x2 x3 x4bxBcB 2 1 0 0cj430141 01/3-1/21/61/3-1/33/412 0 0 -1

21、/12 -7/24 x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cj15/43/4011/4-1/810-1/125/24唯一最优解5-1 5-1 人工变量法（大人工变量法（大M法）法）1.5 单纯形法的进一步讨论例：用单纯形法求解下列线性规划问题。例：用单纯形法求解下列线性规划问题。解：先标准化为解：先标准化为系数矩阵系数矩阵但是但是A中没有单位矩阵，在中没有单位矩阵，在A中人为的增加两列中人为的增加两列此时对应的约束方程组为对应的约束方程组为：该问题新增加了两个变量：x4,x5（称为人工变量）（称为人工变量）A有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。有单位子矩

22、阵，选择这个单位矩阵作为基（称为人工基）。为使 必须保证在可行解中人工变量必须保证在可行解中人工变量x4=x5=0，故令故令x4，x5在目标函数中的系数为在目标函数中的系数为M（其中（其中M表示任意大的正数），表示任意大的正数），这种添加人工变量求解这种添加人工变量求解LP的方法称为的方法称为人工变量法人工变量法,计算过程中出现了计算过程中出现了M，这种方法也称为，这种方法也称为大大M法法。等价于于是，这个线性规划问题转化为：于是，这个线性规划问题转化为：以下可用单纯形法继续求解。以下可用单纯形法继续求解。Cj x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1-2 -3 0

23、-M -M34x4 x5-M -Mcj-zj-2+2M-3+3M-M03/1=34/2=21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj-zj-1/2+M/2 0 -M 0 3/2-3M/2-M-3241 0 -2 2 -1 0 1 1 -1 1x1 x221cj-zj 0 0 -1 1-M 1-M-2-3x50唯一最优解故 zmin=7注意：此时人工变量x4=x5=0说明：说明：若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工变量的人工变量 ，则该模，则该模型型无可行解无可行解。采用大采用大M法求解线性规划模型时，如果模型中法求解线性规划模型时

24、，如果模型中各个系数与各个系数与M的值非常接近或相差很大，若用手工计算的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混不会出现问题。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大淆，使得机器判断出错，从而使大M法失效。法失效。在这种情况下，可采用下面的两阶段法进行计算。在这种情况下，可采用下面的两阶段法进行计算。5-2 5-2 两阶段法两阶段法(将将L.P.问题分成两个阶段来考虑问题分成两个阶段来考虑)第一阶段第一阶段:判断原判断原L.P.L.P.问题是否存在可行解。问题是否存在可行解。给原给原L.P.L.P.问题加入人工变量，并构造仅含人

25、工变量的目标问题加入人工变量，并构造仅含人工变量的目标函数函数w（人工变量在人工变量在w中的系数一般取为中的系数一般取为1 1）并求）并求w的最小值；的最小值；然后用单纯形法求解。若求得然后用单纯形法求解。若求得wmin=0=0，则该问题有可行解，进，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。入第二阶段，否则该问题无可行解，结束。第二阶段：将第第二阶段：将第一一阶段得到的最终表去掉人工变量，并阶段得到的最终表去掉人工变量，并将目标函数还原为原将目标函数还原为原L.P.问题的目标函数（即修改最终表中问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续的

26、第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。用单纯形法求解。例：用两阶段法求解下列线性规划问题。例：用两阶段法求解下列线性规划问题。标准化引入人工变量z(1)(1)第一阶段，构造判断是否存在可行解的模型：第一阶段，构造判断是否存在可行解的模型：用单纯形法求解这个问题，先标准化为；用单纯形法求解这个问题，先标准化为；Cj x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1 0 0 0 -1 -134x4 x5-1 -1cj-zj 2 3-103/1=34/2=21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj-zj 1/2 0 -1

27、 0 -3/2-1 0241 0 -2 2 -1 0 1 1 -1 1x1 x221cj-zj 0 0 0 -1 -10 0 x50最优解本问题有可行解，进入第二阶段(2)(2)第二阶段第二阶段 先在第一阶段的最终单纯形表去掉人工变量，再还原原先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即目标函数，即 max z=-2=-2x1 1-3-3x2 2+0+0 x3 3，继续迭代：继续迭代：Cj x1x2x3XBbCB1 0 -2 0 1 1-2 -3 0 21x1 x2-2 -3cj-zj 0 0-1唯一最优解故 zmin=7注意：两阶段法中不再出现大M，但需要解两个线性规划问题，

28、要注意目标函数系数的变化。5-3 关于解的判别用最终单纯形表判断线性规划问题解的类型：用最终单纯形表判断线性规划问题解的类型：解的类型解的类型最终表的特征最终表的特征无可行解无可行解有非有非0 0的人工变量的人工变量有有可可行行解解唯一最优解唯一最优解无无非非0 0的人的人工变量，非基变量的检验工变量，非基变量的检验数全为负数数全为负数无穷多最优解无穷多最优解无非无非0 0的人工的人工变量，非基变量的检验变量，非基变量的检验数全非正，且有某个非基变量的检验数全非正，且有某个非基变量的检验数为数为0 0无界解无界解无非无非0 0的的人工变量，有某个非基变量人工变量，有某个非基变量的检验数为正数，

29、但该变量对应的系的检验数为正数，但该变量对应的系数全为非正数数全为非正数已知线性规划问题形如：已知线性规划问题形如：5-4 单纯形法计算的向量、矩阵描述引入松弛变量xs 记记X=(XB,XN,XS)T其中，其中，XS为松弛变量，在初始表中是基变量；为松弛变量，在初始表中是基变量；XB为为最终表中基变量；最终表中基变量；XN表示表示既不是初始表的基变量又不是最终表的基变量。既不是初始表的基变量又不是最终表的基变量。注意：注意：XS和和XB允许有公共变量。允许有公共变量。（2 2）A=(B,N,I)B,N,I分别为分别为XB、XN、XS在初始表中在初始表中对应对应的矩阵。的矩阵。则（则（1 1）C

30、=(CB,CN,0)CB,CN,0分别为分别为XB、XN、XS在目标函数中的系数。在目标函数中的系数。（3 3）A=(I,N,B-1)I,N,B-1分别为分别为XB、XN、XS在最终表中在最终表中对应对应的矩阵。的矩阵。约束方程组两端同时左乘B-1，则可得如下表达式：初始单纯形表初始单纯形表最终单纯形表最终单纯形表用单纯形表表示如下：用单纯形表表示如下：XS bB N IXB b I N B-1初始表初始表 X XB B X XN N X XS S cj-zj 0,0 N S=（-y1,-y2,-ym）=-YT 最终表最终表 X XB B X XN N X XS S cj-zj B N 0,0

31、 比较得：比较得：b=B-1b N=B-1N 或者或者 Pj=B-1Pj S=-CB B-1=-YT N=CN-CB B-1 N =CN-YT N或者或者 j=Cj-CBB-1 Pj其中其中B B-1-1为初始表中基变量在最终表对应的系数矩阵，为初始表中基变量在最终表对应的系数矩阵，B B为最终表中基变量在初始表对应的系数矩阵。为最终表中基变量在初始表对应的系数矩阵。例：用单纯形法求解下列线性规划问题.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x10，x2 0 s.t.解：先标准化Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5

32、0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 得到初始单纯形表：6-3 2 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5最终单纯形表：X4010X4010可以验证：三三要要素素决策变量决策变量约束条件约束条件目标函数目标函数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa标标准准化化图图解解法法、单单

33、纯纯形形法法单单纯纯形形法法不不处处理理令令xj=xj-xj xj 0 xj 0令令 xj=-xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-Z 0-M根据上表可以列出初始单纯形表根据上表可以列出初始单纯形表5-5 5-5 单纯形法小结单纯形法小结个数取值限制右端常数约束方向要求系数列初始表列初始表1.7 应用举例 一般而言，一个经济、管理问题要满足以下条一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：件，才能建立线性规划模型：.需要求解问题的目标能用数值指标来反映，需要求解

34、问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；且能用线性函数来描述目标的要求；.为达到这个目标存在多种方案；为达到这个目标存在多种方案；.要求达到的目标是在一定条件下实现的，这要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。些条件可用线性等式或不等式来描述。（一）、混合配料问题例：某糖果厂用原料例：某糖果厂用原料A A、B B、C C加工成三种不同牌号的糖果甲、乙、加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中各种原料的含量，原料成本，各种丙。已知各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价原料

35、的每月限制用量，三种牌号糖果的单位加工费用及售价如下表所示。问该厂每月生产这三种牌号糖果各多少千克，如下表所示。问该厂每月生产这三种牌号糖果各多少千克，能使该厂获利最大。请建立这个问题的线性规划模型。能使该厂获利最大。请建立这个问题的线性规划模型。甲甲乙乙丙丙原料成本（元原料成本（元/kg/kg）每月限制用每月限制用量（量（kgkg）A AB BC C6060202030305050 60602.002.001.501.501.001.00200020002500250012001200加工费（元加工费（元/kg/kg）0.500.500.400.400.300.30售价（元售价（元/kg/k

36、g）3.403.402.852.852.252.25解：用i=1,2,3表示原料A、B、C；用j=1,2,3表示糖果甲、乙、丙；设xij为生产第j种糖果使用的第i种原料的质量，则该问题的数学模型为：s.t.原料供应限制含量要求条件用单纯形法求得：即每月生产甲糖果 kg，乙糖果 kg，不生产丙糖果，可获得最大利润为5450元。（二）、投资项目组合问题例：兴安公司有一笔例：兴安公司有一笔3030万元的资金，考虑今后三年内用于下列万元的资金，考虑今后三年内用于下列项目的投资：项目的投资：1 1、三年内每年年初均可投资，每年获利为投资额的、三年内每年年初均可投资，每年获利为投资额的20%20%，其本，

37、其本利可一起用于下一年投资；利可一起用于下一年投资；2 2、只允许第一年初投入，于第二年末收回，本利合计为投资额、只允许第一年初投入，于第二年末收回，本利合计为投资额的的150%,150%,但此类投资限额不超过但此类投资限额不超过1515万元；万元；3 3、允许于第二年初投入，于第三年末收回，本利合计为投资额、允许于第二年初投入，于第三年末收回，本利合计为投资额的的160%160%，但限额投资，但限额投资2020万元；万元；4 4、允许于第三年初投入，年末收回，可获利、允许于第三年初投入，年末收回，可获利40%40%，但限额为，但限额为1010万元万元.试为该公司确立一个使第三年末本利和最大的投资组合方案，试为该公司确立一个使第三年末本利和最大的投资组合方案，请建立这个问题的线性规划模型。请建立这个问题的线性规划模型。解：用xij表示第i年初投放到第j个项目的资金数，则建立如下线性规划模型：1234一二三第第i年初年初投入第投入第j个项目个项目用单纯形法求得：1234一一166666.7133333.3二二0200000三三100000100000 第三年末本利和第三年末本利和=580000综上投资组合方案如下：综上投资组合方案如下：