运筹学胡运权第五版课件(第1章).ppt

运 筹 学(Operations Research)一、古代朴素的运筹学思想一、古代朴素的运筹学思想例如：田忌赛马例如：田忌赛马二、运筹学的起源二、运筹学的起源国外国外英文原名英文原名 Operations Research 简称简称“O.R.”直译为：运用研究或作业研究直译为：运用研究或作业研究正式出现于正式出现于19381938年年7 7月英国一份关于防空作战月英国一份关于防空作战系统运行的研究报告中系统运行的研究报告中绪绪 论论国内国内19561956年成立第一个运筹学小组年成立第一个运筹学小组19571957年从年从“夫运筹策帷幄之中，决胜于千里之外夫运筹策帷幄之中，决胜于千里之外”中中摘取摘取“运筹运筹”二字，将二字，将O.R.正式翻译为正式翻译为“运筹学运筹学”三、运筹学的定义三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供研究目的：对有限资源进行合理规划、使用，并提供 优化决策方案。优化决策方案。研究对象：复杂系统的组织和管理研究对象：复杂系统的组织和管理参考参考大英百科全书大英百科全书、辞海辞海、中国企业管理百科全书中国企业管理百科全书等。等。四、运筹学研究的基本特点四、运筹学研究的基本特点 系统的整体优化系统的整体优化 多学科的配合多学科的配合 模型方法的应用模型方法的应用五、运筹学研究的基本步骤五、运筹学研究的基本步骤 分析与表述问题分析与表述问题 建立数学模型建立数学模型 对问题求解对问题求解 对模型和模型导出的解进行检验对模型和模型导出的解进行检验 建立对解的有效控制建立对解的有效控制 方案的实施方案的实施第一章第一章 线性规划及单纯形法线性规划及单纯形法Linear Programming and Simplex Methodxa此为无约束的极值问题此为无约束的极值问题1.1 一般线性规划问题的数学模型一般线性规划问题的数学模型1-1 1-1 问题的提出问题的提出例例1 1 用一块边长为用一块边长为a的正方形铁皮做一个无盖长方体容器，的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？应如何裁剪可使做成的容器的容积最大？例例2 2 常山机器厂生产常山机器厂生产 I I、IIII 两型产品。这两型两型产品。这两型产品都分别要在产品都分别要在A A、B B、C C三种不同设备上加工。按三种不同设备上加工。按工艺规定，生产每件产品工艺规定，生产每件产品I I需占用各设备分别为需占用各设备分别为2h2h、4h4h、0h0h，生产每件产品，生产每件产品IIII需占用各设备分别为需占用各设备分别为2h2h、0h0h、5h5h。己知各设备计划期内用于生产这两种产品。己知各设备计划期内用于生产这两种产品的能力分别为的能力分别为12h12h、16h16h、15h15h，又知每生产一件产，又知每生产一件产品品I I企业能获利企业能获利2 2元利润，每生产一件产品元利润，每生产一件产品IIII企业能企业能获利获利3 3元利润，问该企业应安排生产两种产品各多元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。少件，使总的利润收入为最大。1-2 1-2 线性规划问题的数学模型线性规划问题的数学模型原型原型模型模型数学模型数学模型提炼提炼数学工具数学工具1 1、原型原型：现实世界中人们关心、研究的实际对象。：现实世界中人们关心、研究的实际对象。模型模型：将某一部分信息简缩、提炼而构造的原型替代物。：将某一部分信息简缩、提炼而构造的原型替代物。数学模型数学模型：对现实世界的一个特定对象，为达到一定目的，：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设根据内在规律做出必要的简化假设,并运用适当数学工具得到并运用适当数学工具得到的一个数学结构。的一个数学结构。3 3、规划问题数学模型的三要素、规划问题数学模型的三要素（2 2）目标函数目标函数：问题要达到的目标要求，表示为决策变量的：问题要达到的目标要求，表示为决策变量的函数。用函数。用 z=f(x1 1，x2 2，xn n)表示。表示。（1 1）决策变量决策变量：决策者为实现规划目标采取的方案、措施，：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用是问题中要确定的未知量。用x1 1，x2 2，xn n表示。表示。（3 3）约束条件约束条件：决策变量取值时受到的各种可用资源的限制，：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。表示为含决策变量的等式或不等式。2 2、规划问题、规划问题即求目标函数在若干约束条件下的最值。即求目标函数在若干约束条件下的最值。4 4、线性规划问题（、线性规划问题（Linear Programming）的数学模型）的数学模型（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）其他形式其他形式：连加形式连加形式1-3 1-3 线性规划问题的标准形式线性规划问题的标准形式1 1、标准形式、标准形式或或2 2、条件、条件目标函数求极大值目标函数求极大值约束条件全是等式（线性方程组）约束条件全是等式（线性方程组）决策变量全非负决策变量全非负右端常数全非负右端常数全非负3 3、标准化方法、标准化方法（1）若目标函数求极小值，即）若目标函数求极小值，即则令则令 转化为转化为（2 2）若约束条件为不等式，）若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。转化为等式约束条件。注意注意：松弛变量在目标函数中系数全为：松弛变量在目标函数中系数全为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）若约束等式的右端常数）若约束等式的右端常数bi 0 0，则，则其中其中（“一分为二一分为二”）等式两边同时乘以等式两边同时乘以“-1”。例例3：将下列线性规划模型化为标准形式。将下列线性规划模型化为标准形式。例例4：在下述线性规划问题中，列出全部基、基解、基：在下述线性规划问题中，列出全部基、基解、基可行解，并指出最优解。可行解，并指出最优解。解：系数矩阵为解：系数矩阵为若取基为若取基为 B=(P1,P2,P3),则基变量为则基变量为x1,x2,x3,非基变量为非基变量为x4,x5令令x4=x5=0，代入约束方程组，代入约束方程组解得解得x1=4,x2=3,x3=-2从而得到一个基解从而得到一个基解 X=(4,3,-2,0,0)T这个基解不是基可行解！这个基解不是基可行解！该该 L.P.共有共有8个基解。个基解。若取基为若取基为 B=(P3,P4,P5)=I3,则基变量为则基变量为x3,x4,x5,非基变量为非基变量为x1,x2令令x1=x2=0，代入约束方程组，代入约束方程组从而得到一个基解从而得到一个基解 X=(0,0,12,16,15)T这个基解是基可行解！这个基解是基可行解！（注意：选择单位矩阵为基可以较方便的求出一个基可行解。）（注意：选择单位矩阵为基可以较方便的求出一个基可行解。）同理可得其他基解同理可得其他基解.基基B基解基解是基是基可行可行解？解？目标目标函数函数值值x1x2x3x4x5P1P2P34 43 3-2-20 00 0否否1717P1P2P43 33 30 04 40 0是是1515P1P2P54 42 20 00 05 5是是1414P1P3P54 40 04 40 01515是是8 8P1P4P56 60 00 0-8-81515否否1212P2P3P40 03 36 616160 0是是9 9P2P4P50 06 60 01616-15-15否否1818P3P4P50 00 0121216161515是是0 0（最优基）（最优基）（最优解）（最优解）（最优目标函数值）（最优目标函数值）4 4、线性规划问题各种解之间的关系、线性规划问题各种解之间的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解最优解最优解1.2 1.2 图解法图解法1 1、适用范围：仅含两个决策变量的、适用范围：仅含两个决策变量的 L.P.2、步骤：、步骤：（1 1）作平面直角坐标系，标上刻度；）作平面直角坐标系，标上刻度；（2 2）作出约束方程所在直线，确定可行域；）作出约束方程所在直线，确定可行域；（3 3）作出一组目标函数的等值线，判定优化方向；）作出一组目标函数的等值线，判定优化方向；（4 4）沿优化方向移动，确定与可行域相切的点，确定）沿优化方向移动，确定与可行域相切的点，确定最优解，并计算最优目标函数值。最优解，并计算最优目标函数值。例：例：用图解法求解下列线性规划问题。用图解法求解下列线性规划问题。（1）max z=2x1+3x2 s.t.2x1+2x2 12 -4x1 16 -5x2 15 -x1 0,x2 0 x1x222468460 2x1+2x2=12 5x2=15 4x1=16 Z=6Z=0A(3,3)Zmax有有唯一最优解唯一最优解，当当 x1=x2=3 时，时，Zmax=15=15C(4,0)D(0,3)(0,0)B(4,2)顶点顶点基可行解基可行解A（3,3）（3,3,0,4,0）B（4,2）（4,2,0,0,5）C（4,0）（4,0,4,0,15）D（0,3）（0,3,6,16,0）O（0,0）（0,0,12,16,15）一一对应一一对应 （2 2）（3 3）无穷多最优解无穷多最优解无界解无界解x1x1x2 x2 x1x2 无可行解无可行解（4 4）3 3、线性规划问题解的类型、线性规划问题解的类型（1）唯一最优解：只有一个解为最优解）唯一最优解：只有一个解为最优解（2）无穷多最优解：有无穷多个解为最优解）无穷多最优解：有无穷多个解为最优解（3）无界解：目标函数的取值无界）无界解：目标函数的取值无界（4）无可行解：可行域为空集，即存在互相矛盾的约束条）无可行解：可行域为空集，即存在互相矛盾的约束条件。件。4 4、可行域的特征、可行域的特征（1 1）若）若L.P.的可行域不是空集，则可行域为凸集。的可行域不是空集，则可行域为凸集。（2 2）若）若L.P.有最优解，则一定可以在可行域的顶点上找到最有最优解，则一定可以在可行域的顶点上找到最优解。优解。（3 3）L.P.L.P.的顶点与基可行解一一对应。的顶点与基可行解一一对应。3-1 3-1 预备知识：凸集与顶点预备知识：凸集与顶点1.3 1.3 单纯形法单纯形法（Simplex Method）原理原理（1 1）凸集：对于集合）凸集：对于集合C C中任意两点连线段上的点，若全在中任意两点连线段上的点，若全在C C内，内，则称集合则称集合C C为凸集。为凸集。直观特征：图形从内部向外部凸出。直观特征：图形从内部向外部凸出。凸集凸集非凸集非凸集（2 2）顶点：凸集中不在任意两点的连线段内部的点。）顶点：凸集中不在任意两点的连线段内部的点。X1X4X3X5X2单纯形法的计算步骤：单纯形法的计算步骤：初始基可行解初始基可行解使目标函数值增大使目标函数值增大的新的基可行解的新的基可行解是否最优解？是否最优解？结束结束是是否否1.4 1.4 单纯形法的计算步骤单纯形法的计算步骤1 1、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。不妨假设不妨假设A中前中前m列对应的子矩阵是单位列对应的子矩阵是单位矩阵，取其为基矩阵，取其为基B，得到初始基可行解，得到初始基可行解m+3行行n+4列列第第1行：价值行行：价值行 cj第第2行：变量行行：变量行 xj最后一最后一行：检验数行行：检验数行 j第第1列：基价值列列：基价值列 CB第第2列列：基变量列：基变量列 XB第第3列列：基解列：基解列 b最后一最后一列：列：比值比值列列 主体：系数矩阵主体：系数矩阵Amn2 2、单纯形表的结构、单纯形表的结构例例5：用单纯形法求解下列线性规划问题：用单纯形法求解下列线性规划问题.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-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 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）存在两个以上的最大正检验数。存在两个以上的最大正检验数。任取一个最大正检验数对应的变量作为换入变量。任取一个最大正检验数对应的变量作为换入变量。（2 2）出现两个以上相同的最小值。出现两个以上相同的最小值。任取一个最小任取一个最小对应的变量作为换出变量。对应的变量作为换出变量。此时此时L.P.问题出现退化现象。问题出现退化现象。(1)(1)当所有当所有 j 0 0，表示有，表示有唯一最优解唯一最优解；(2)(2)当所有当所有 j 0，且，且存在某个非基变量的检验数存在某个非基变量的检验数 k=0，则该线，则该线性规划模型具有性规划模型具有无穷多最优解无穷多最优解；(3)(3)若存在某个若存在某个 j 0 0，但对应的第，但对应的第j列系数全非正，即列系数全非正，即aij 0 0，则，则线性规划模型具有线性规划模型具有无界解无界解。3-5 3-5 解的判别解的判别练习练习 用单纯形法求解下列线性规划问题用单纯形法求解下列线性规划问题解：先标准化解：先标准化 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/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 单纯形法的进一步讨论例例6：用单纯形法求解下列线性规划问题。：用单纯形法求解下列线性规划问题。说明：说明：若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工变量的人工变量 ，则该模，则该模型型无可行解无可行解。采用大采用大M法求解线性规划模型时，如果模型中法求解线性规划模型时，如果模型中各个系数与各个系数与M的值非常接近或相差很大，若用手工计算的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混不会出现问题。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大淆，使得机器判断出错，从而使大M法失效。法失效。在这种情况下，可采用下面的两阶段法进行计算。在这种情况下，可采用下面的两阶段法进行计算。5-2 5-2 两阶段法两阶段法(将将L.P.问题分成两个阶段来考虑问题分成两个阶段来考虑)第一阶段第一阶段:判断原判断原L.P.L.P.问题是否存在可行解。问题是否存在可行解。给原给原L.P.L.P.问题加入人工变量，并构造仅含人工变量的目标问题加入人工变量，并构造仅含人工变量的目标函数函数w（人工变量在人工变量在w中的系数一般取为中的系数一般取为1 1）并求）并求w的最小值；的最小值；然后用单纯形法求解。若求得然后用单纯形法求解。若求得wmin=0=0，则该问题有可行解，进，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。入第二阶段，否则该问题无可行解，结束。第二阶段：将第第二阶段：将第一一阶段得到的最终表去掉人工变量，并阶段得到的最终表去掉人工变量，并将目标函数还原为原将目标函数还原为原L.P.问题的目标函数（即修改最终表中问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。用单纯形法求解。例：用两阶段法求解下列线性规划问题。例：用两阶段法求解下列线性规划问题。标准化引入人工变量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 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，但需要解两个线性规划问题，要注意目标函数系数的变化。5-3 关于解的判别用最终单纯形表判断线性规划问题解的类型：用最终单纯形表判断线性规划问题解的类型：解的类型解的类型最终表的特征最终表的特征无可行解无可行解有非有非0 0的人工变量的人工变量有有可可行行解解唯一最优解唯一最优解无无非非0 0的人的人工变量，非基变量的检验工变量，非基变量的检验数全为负数数全为负数无穷多最优解无穷多最优解无非无非0 0的人工的人工变量，非基变量的检验变量，非基变量的检验数全非正，且有某个非基变量的检验数全非正，且有某个非基变量的检验数为数为0 0无界解无界解无非无非0 0的的人工变量，有某个非基变量人工变量，有某个非基变量的检验数为正数，但该变量对应的系的检验数为正数，但该变量对应的系数全为非正数数全为非正数例：用单纯形法求解下列线性规划问题.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x10，x2 0 s.t.解：先标准化5-4 单纯形法计算的向量、矩阵描述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-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标标准准化化图图解解法法、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj=xj-xj xj 0 xj 0令令 xj=-xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-Z 0-M根据上表可以列出初始单纯形表根据上表可以列出初始单纯形表5-5 5-5 单纯形法小结单纯形法小结个数取值限制右端常数约束方向要求系数列初始表列初始表1.7 应用举例 一般而言，一个经济、管理问题要满足以下条一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：件，才能建立线性规划模型：.需要求解问题的目标能用数值指标来反映，需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；且能用线性函数来描述目标的要求；.为达到这个目标存在多种方案；为达到这个目标存在多种方案；.要求达到的目标是在一定条件下实现的，这要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。些条件可用线性等式或不等式来描述。（一）、混合配料问题例：某糖果厂用原料例：某糖果厂用原料A A、B B、C C加工成三种不同牌号的糖果甲、乙、加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中各种原料的含量，原料成本，各种丙。已知各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价原料的每月限制用量，三种牌号糖果的单位加工费用及售价如下表所示。问该厂每月生产这三种牌号糖果各多少千克，如下表所示。问该厂每月生产这三种牌号糖果各多少千克，能使该厂获利最大。请建立这个问题的线性规划模型。能使该厂获利最大。请建立这个问题的线性规划模型。甲甲乙乙丙丙原料成本（元原料成本（元/kg/kg）每月限制用每月限制用量（量（kgkg）A AB BC C6060202030305050 60602.002.001.501.501.001.00200020002500250012001200加工费（元加工费（元/kg/kg）0.500.500.400.400.300.30售价（元售价（元/kg/kg）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%，其本，其本利可一起用于下一年投资；利可一起用于下一年投资；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综上投资组合方案如下：综上投资组合方案如下：