运筹学绪论硕士课件

管理运筹学管理运筹学 汪贤裕汪贤裕 2009.081绪绪 论论一、什么是运筹学二、运筹学模型三、运筹学分析的主要步骤四、管理运筹学的教学组织2一、什么是运筹学一、什么是运筹学运筹学是对系统进行科学的定量分析，从而发现问题、解决问题的哲学方法论。运筹学研究“事”的内在规律，对“事”的内在规律进行形式化、定量化的描述，运筹学是管理科学中的最重要的组成部分。3二、运筹学模型二、运筹学模型1.运筹学研究的模型主要是抽象的数学模型。运筹学研究的模型主要是抽象的数学模型。其优点有：1.1建模的过程中，能对系统进行深入的了解和分析，1.2建模对系统的描述，可以找出和揭示出一些内在的联系和特征，1.3利用模型，可以对系统进行多种试验分析。42.运筹学模型的分类运筹学模型的分类：2.1数学规划模型，2.2图与网络模型，2.3对策论模型，2.4排队论模型，2.5决策论模型，2.6存贮论模型，2.7排序与统筹方法2.8计算机模拟技术。3.运筹学模型大多是优化模型运筹学模型大多是优化模型。5三、运筹学分析的主要步骤三、运筹学分析的主要步骤发现和定义待研究的问题，构造数学模型，寻找模型优化的结果，通过应用这些结果对系统进行分折和改善系统的运行。6真实真实系统系统数据数据准备准备系统分析系统分析问题描述问题描述模型建立模型建立与检验与检验模型术解模型术解与检验与检验结果分析结果分析与实施与实施7四、管理运筹学的教学组织教学大纲学分和学时数教材课件8投票博弈投票博弈例1：一个董事会有4位董事，其中董事长有3票，副董事长有2票，剩余2名董事各有1票，进行投票表决。表决的规则是：超过半数票，讨论的提案通过。问：1.副董事长的权力和1个董事的权力有多大的差异？2.若表决的规则是：超过2/3票，讨论的提案通过。副董事长的权力和1个董事的权力有多大的差异？9定义定义1.设投票博弈中，参加投票人的集合为N=1,2,n。N的一个子集S称为一个联盟联盟。定义定义2.设投票博弈中,若对某一个联盟S满足：（1）.投票人 i 在S中，（2）.S中的投票人一致同意，则提出的议案通过；且S i中的投票人一致同意，则提出的议案不能通过。则该联盟S称为投票人 i 的一个摆盟摆盟。10定义定义3.用i表示第i个投票人的摆盟数，则记 i=i/（1+2+n）i=1，2,n =(1 ,2 ,n)称为Banzhaf势指标。一般情况下，可用 Banzhaf 势指标来表示投票人的权力大小。11例1解：投票人集合：N=1，2，3，4。设Si为投票人i的摆盟，i =1,2,3,4。S 1：1,2、1,3、1,4、1,2,3、1,2,4、1,3,4S 2：2,1、2,3,4S 3：3,1、3,2,4S 4：4,1、4,2,3摆盟数摆盟数为：1=6,2=2,3=2,4=2.势指标势指标为：1=1/2,2=3=4=1/612例1(续)若表决的规则改为：达到或超过2/3时，提出的议案通过。解：投票人集合：N=1,2,3,4。设Si为投票人i的摆盟，i=1,2,3,4。S1：1,2,1,2,3,1,2,4,1,3,4,1,2,3,4S2：2,1、2,1,3、2,1,4S3：3,1,4S4：4,1,3摆盟数摆盟数为：1=5,2=3,3=1,4=1.势指标势指标为：1=5/10，2=3/10,3=4=1/1013方案序号董事长有3票副董事长有2票董事有1票董事有1票 方案1（达到半数）3/61/61/61/6方案2（达到2/3)5/103/101/101/1014例2 一个董事会由4位股东组成，每位股东依次拥有股份为：40%，30%，20%，10%。在董事会投票时，每位股东的票数与他所拥有的股份成正比。当投票规则为：（1）严格超过一半，提出的议案通过；（2）只要达到一半，提出的议案通过；（3）达到或超过2/3，提出的议案通过。试进行三种投票规则下，每位股东的权力比较分析。15解：设投票人集合为：N=1,2,3,4，每人依次拥有股份为：40%,30%,20%,10%.（1）每个投票人的摆盟分别为：S1:1,2,1,3,1,2,3,1,2,4,1,3,4;S2:2,1,2,3,4,2,1,4;S3:3,1,3,1,4,3,2,4;S4:4,2,3.摆盟数摆盟数分别为：1=5,2=3,3=3,4=1;势指标势指标分别为：1=5/12,2=3/12,3=3/12,4=1/1216（2）(此时只需要50%就可以通过）每个投票人的摆盟分别为：S1:1,2、1,3、1,4、1,2,4、1,3,4S2:2,1、2,3、2,3,4S3:3,1、3,2、3,2,4S4:4,1每个投票人的摆盟数摆盟数分别为：1=5,2=3,3=3,4=1势指标势指标分别为：1=5/12,2=3/12,3=3/12,4=1/12.17（3）（此时需66.67%就可以通过）每个投票人的摆盟分别为：S:1,2,1,2,3,1,2,4,1,3,4,1,2,3,4S:2,1,2,1,3,2,1,4S:3,1,4S:4,1,3每个投票人的摆盟数摆盟数分别为：=5,=3,=1,=1势指标势指标分别为：=5/10,=3/10,=1/10,=1/1018 方案 序号 股东1（40%股份）股东2（30%股份）股东3（20%股份）股东4（10%股份）方案1（超过半数）5/123/123/121/12方案2（达到半数）5/123/123/121/12 方案3（达到2/3）5/103/101/101/1019博弈承包基数的确定博弈承包基数的确定博弈的一方委托人-资产所有者，博弈的另一方代理人-生产经营者。双方对承包基数的确定发生冲突：（委托人要求数为：D，委托人要求D大。代理人自报数为：S，代理人要求S小.）20委托人提出基数确定三原则:1.委托人和代理人共同诵确定承包基数。最终合同基数C是委托人要求数D和代理人自报数S的加权平均：C=（1 W）D+W S W（0,1）合同基数C全部归委托人，即“基数全交”。不妨取:W=1/2.2.当期未的实际完成数AC时，超过部份的Q1将作为奖励归代理人；若AS时，将对代理人收取“少报罚金”。少报罚金的数量为（S-A）Q2。不妨取:Q2=60%.21承包基数确定范例表：代理人自报数的5种情况一二三四五(1)代理人的自报数：S60708090100(2)委托人的要求数：D6060606060(3)合同确定数:C=（D+S）/26065707580(4)代理人实行完成数:A8080808080(5)超基数奖励:（A-c）0.81612 8 4 0(6)少报罚金:（S-A)0.6（AS时）-12-600 0(7)代理人净收益=（5）+（6）4 6 8*4 022 结论：代理人以完成数作为自报数，即讲真话，可以得到最大净收益。下面我们分析在这种机制下，代理人的净收益：23代理人净收益图示分析：N(S)0 A S上述“讲真话”机制的充分条件为：Q2WQ10（上例中的数字是满足充分条件的）24第1章 线性规划与单纯形法线性规划是运筹学中应用最广泛的方法，世界500强最大的企业中，有85%的企使用过线性规划来解决管理中遇到的问题。线性规划在应用中用得最成功的是解决稀缺资源的最优分配问题。线性规划最常用于讨论利益（利润）的最大（max）和成本（支出）的最小（min）.25例：设有一根长为L果的铁丝，要围成一个矩形。问矩形的长和宽各为多少，使所围成的矩形面积最大？解：设围成矩形的长为x米，宽为y米。由矩形的特征有：xy=L/2，y=L/2x。问题等价求x满足：Max s=x y s.t.xy=L/2 0 xL/2,0yL/2（对该问题中学求觧：最大化二次函数：s=x (L/2x)这个简单的问题就是数学规划问题。数学规划问题有三个组成部分：数学规划问题有三个组成部分：1.决策变量（一般是多个决策变量）；2.含决策变量的目标函数；3.对决策变量的约束条件。261.1 线性规划的基本概念1.1.1 线性规划模型线性规划模型一、线性规划模型举例一、线性规划模型举例例1.1 生产计划问题 已知某家俱厂在计划期生产桌子和椅子，不考虑其它情况，只考虑劳动力情况如下。如何安排生产有最多的销售收入？单位产品用料桌子椅子可用资源木工4小时3小时120油漆工2小时1小时50单位产品售价50元/个30元/个27解：设生产桌子x个，生产椅子y个（决策变量为2个）.要达到销售收入最大：Max z=50 x30 y （目标函数）。工时要求：4x3y 120,2 xy 50.（约束条件）变量取值要求：x0,y0.（约束条件）。线性规划模型为：max z=50 x30 y s.t.4 x3 y 120 2 xy 50 x 0,y 0.28例1.2 营养配餐问题 要求配餐中至少应有热量3000kcal,蛋白质55g，钙300mg。问应怎样配餐成本最低？序号 食 品 名 称 热量（kcal）蛋白质 （g）钙（mg）价格（元)1猪 肉100050400142鸡 蛋8006020063大 米9002030034白 菜20010500229解：设每天配入猪肉 x1千克、鸡蛋 x2千克、大米 x3千克、白菜 x4千克。（决策变量）则配餐问题的线性规划模型如下：Min z=14x1 6x2 3x3 2x4 （目标函数)s.t.1000 x1800 x2900 x3200 x4 3000 50 x1 60 x2 20 x3 10 x4 55 400 x1 200 x2300 x3500 x4 800 x i 0 i=1,2,3,4.（s.t.后全是约束条件）30二、线性规划的一般形式二、线性规划的一般形式三要素三要素：1.有一组决策变量；2.有一个与决策变量有关的目标函数，并是决策变量的线性函数，需要解决max或min问题；3.有一组与决策变量有关的约束限制，用线性等式或线性不等式表示。31线性规划模型的一般形式32三、线性规划的隐含假定三、线性规划的隐含假定1.比例性假定；2.可加性假定；3.连续性假定；4.确定性假定。331.1.2 两变量线性规划的图解法两变量线性规划的图解法例：yMax z=50 x+30ys.t.4x+3y120 2x+y50 x 0,y0.max 10 0 10 x34图解法的步骤图解法的步骤1.画出直角坐标系。2.画出可行域，即满足约束条件的全部（x,y）点。3.对目标函数z给任意两个常数，画出两条目标函数等值线，确定目标出函数的方向。沿这一方向，平移目标函数等值线到可行域的边界，确定最优解。4.求解过最优解点的两个约束等式组成的线性方程组，求出最优解的数值。5.代最优解数值到目标出函数中，得出最优值。35例例1.31.3 Max z=1500 x1+2500 x2 s.t.3x1+2x2 65 (A)2x1+x2 40 (B)3x2 75 (C)x1,x2 0 (D,E)Max361.1.3 图解法的几点讨论一、概念概念1.可行解可行解满足全部约束条件的某一点；2.可行域可行域可行解的全体；3.最优解最优解使目标函数达到最优极值的可行解；4.最优值最优值最优解代入目标函数后的目标函数值。37二、最优解的个数二、最优解的个数1.唯一唯一最优解；2.有无穷无穷多个解；3.无解无解：（1）可行域为空集，（2）因目标函数值无界。38三、线性规划的基本定理三、线性规划的基本定理1.线性规划的可行域是凸集。2.线性规划可行域的极点与基本可行解一一对应。3.线性规划若有最优解，一定可以在可行域的极点达到。391.2 线性规划应用举列线性规划应用举列1.2.1调和问题调和问题例1.4.汽油组分的质量和成本数据 汽油产品的质量和价格数据求如何安排各种品牌汽油生产，使总利润最大？序号原 料辛烷值含硫量%成本（元/吨）可用量（吨/月）1直馏汽油621.560020002催化汽油780.890010003重整汽油900.21400500序号序号产品产品辛烷值辛烷值含硫量含硫量%销售价（元销售价（元/吨）吨）170#汽油汽油 70 1900280#汽油汽油 80 11200390#汽油汽油 90 0.6150040解：设第 j种产品对原料 i 使用为 xi,j 产品 j原料 i70#汽油（1）80#汽油（2）90#汽油 （3）原 料总用量1.直馏汽油x1,1x1,2x1,32.催化汽油x2,1x2,2x2,33.重整汽油x3,1x3,2x3,3产品总量41线性规划模型为：Max z=（900600)x1,1+(1200600)x1,2+(1500600)x1,3(900900)x2,1+(1200900)x2,2+(1500900)x2,3+(9001400)x3,1+(12001400)x3,2+(1500-1400)x3,3s.t.1.产品辛烷值应满足要求：(62x1,178x2,190 x3,1)70(x1,1x2,1x3,1)(62x1,278x2,290 x3,2)80 (x1,2x2,2x3,2)(62x1,378x2,390 x3,3)90(x1,3x2,3x3,3)422.产品含硫量应满足要求：(1.5%x1,10.8%x2,10.2%x3,1)/(x1,1x2,1x3,1)1%(1.5%x1,20.8%x2,20.2%x3,2)/(x1,2x2,2x3,2)1%(1.5%x1,30.8%x2,30.2%x3,3)/(x1,3+x2,3x3,3)0.6%3.原料可用量应满足要求：(x1,1x1,2x1,3)2000(x2,1x2,2x2,3)1000(x3,1x3,2x3,3)5004.生产中原料使用量的非负要求：x i,j0,i =1,2,3.j=1,2,3.43 1.2.2生产工艺优化问题生产工艺优化问题 例例1.5 佳丽化工厂生产洗衣粉和洗涤剂。生产原料可以从市场上以每千克5元的价格买到。处理1千克原料可生产0.5千克普通洗衣粉和0.3千克普通洗涤剂。普通洗衣粉和普通洗涤剂可分别以每千克8元和12元的价格在市场上出售。工厂设备每天最多可处理4吨原料，每加工1千克原料的成本为1元。为生产浓缩洗衣粉和高级洗涤剂，工厂还可继续对普通洗衣粉和普通洗涤剂进行精加工。处理1千克洗衣粉可得0.5千克浓缩洗衣粉，处理1千克普通洗涤剂可得0.25千克高级洗涤剂。加工示意图如下。浓缩洗衣粉的市场价格为每千克24元，高级洗涤剂的价格为每千克55元。每千克精加工产品的成本为3元。如果产品市场和原料供应设有限制，向该工厂如何生产能使其利润最大？44y千克原料0.3y千克洗涤剂0.5y千克洗衣粉x1千克普通洗衣粉x2千克浓缩洗衣粉x3千克普通洗涤剂x4千克高级洗涤剂8元/千克24元/千克12元/千克55元/千克原料5元/千克加工能力：4吨加工成本1元/千克成品率0.5产品成本：3元/千克成品率:0.25产品成本：3元/千克成品率：0.3成品率：0.545 解：设x1为普通洗衣粉的产量，x2为浓缩洗衣粉的产量，x3为普通洗涤剂的产量，x4为高级洗涤剂的产量，y为原料的供应量。工厂利润=8x1+12x3+24x2+55x43x23x4（5+1）y平衡关系：0.5y=x1+x2/0.5 0.3y=x3+x4/0.25加工能力：y=4000线性规划模型为：Max 8x1+21x2+12x3+52x46ys.t.0.5yx12x2=0 0.3yx34x4=0 y=046 1.2.3多周期动态生产计划问题多周期动态生产计划问题 例1.6 华津机器制造厂专门为拖拉机厂配套生产柴油机，今年头四个月收到的订单数量分别为3000台，4500台，3500台，5000台柴油机。该厂正常生主少每月可生立了3000台柴油机，利同加班还可生产1500台。正常生产的成本为每台5000元，加班生产还要追加成本1500元，库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低？47 解：设x i 为第i月正常生产的产品数，y i为第i月加班生产的产品数，z i为第i月月初产品的库存数。若令d i为第i月的需求，第一个月初的库存数为零，则模型的目标函数为：约束的一般形式为：Z 1=Z 5=048 1.2.4投资证券组合的选择投资证券组合的选择 例例1.7 某人有一笔50万元的资金可用于长期投资，可供选择的投资机会包含下列7种。不同的投资方式的具体参数见下表。投资者希望投资组合的平均年限不超过5年，平均期望收益率不低于13%，风险系数不超过4，收益的增长潜力不低于10%。问在满足上述要求的前提下，投资者该如何选择投资组合，使平均年收益率最高？49序号投资方式年收益率（%）投资期限（年）风险系数增长潜力（%）1国库券113102公司债券15103153房地产2568304股票2026205短期定期存款101156长期保值储蓄1252107现金存款3000要求 5 4 1050例例1.8生产计划安排问题生产计划安排问题益民食品厂用三种原料生产两种糖果。至少生产600千克高级奶糖，800千克水果糖。求在计划期应如何安排生产，使总利润最大。成分售价品种原科 A（奶粉）原料 B（可可粉）原料 C（糖）元/千克高级奶糖50%25%10%24.0水果糖15%15%60%15.0原料原料可供量（千克）成本（元/千克）A50020.00B75012.00C6258.0051解：变量假设：生产高级奶糖用原料A、B、C各为：x1,1，x2,1,x3,1生产水果糖用原料A、B、C各为：x1,2,x2,2,x3,2.利润函数为（略）原料A原料B原料C产品总量高级奶糖x1,1x2,1x3,1x1,1x2,1x3,1水果糖x1,2x2,2x3,2x1,2x2,2x3,2原料总量x1,1x1,2x2,1x2,2x3,1x3,252某昼夜服务的公交线路每天各时间段内所需司机数如下：某昼夜服务的公交线路每天各时间段内所需司机数如下：例例1.91.9人力资源分配的问题人力资源分配的问题设司机分别在各时间段一开始时上班，并连续工作设司机分别在各时间段一开始时上班，并连续工作8h8h，问该公交线路怎样安排司机，既能满足工作需要，问该公交线路怎样安排司机，既能满足工作需要，又配备最少司机又配备最少司机?53 解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘班次时开始上班的司机和乘务人员数务人员数,这样我们建立如下的数学模型。这样我们建立如下的数学模型。目标函数目标函数：Min Min Min Min x x x x1 1 1 1+x x x x2 2 2 2+x x x x3 3 3 3+x x x x4 4 4 4+x x x x5 5 5 5+x x x x6 6 6 6 约束条件约束条件：s.t.s.t.s.t.s.t.x x x x1 1 1 1+x x x x6 6 6 6 60 60 60 60 x x x x1 1 1 1+x x x x2 2 2 2 70 70 70 70 x x x x2 2 2 2+x x x x3 3 3 3 60 60 60 60 x x x x3 3 3 3+x x x x4 4 4 4 50 50 50 50 x x x x4 4 4 4+x x x x5 5 5 5 20 20 20 20 x x x x5 5 5 5+x x x x6 6 6 6 30 30 30 30 x x x x1 1 1 1,x x x x2 2 2 2,x x x x3 3 3 3,x x x x4 4 4 4,x x x x5 5 5 5,x x x x6 6 6 6 0 0 0 0 人力资源分配的问题人力资源分配的问题54 明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配 三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？例1.10 生产计划的问题（生产计划的问题（I I）55解：解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。生产计划的问题（生产计划的问题（I I）56 求 x i 的利润:利润=售价-各成本之和可得到 x i（i=1,2,3,4,51,2,3,4,5）的利润分别为1515、1010、7 7、1313、9 9元。这样我们建立如下数学模型：目标函数:Max 15x1+10 x2+7x3+13x4+9x5 约束条件：s.t.5x1+10 x2+7x3 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 0生产计划的问题（生产计划的问题（I)I)57 永久机械厂生产、三种产品，均要经过 A、B 两道工序加工。假设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。可在 A、B的任何规格的设备上加工；可在任意规格的A设备上加工，但对B工序,只能在B1设备上加工；只能在A2与B2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？例例1.111.11 生产计划的问题（生产计划的问题（IIII）58解：产品解：产品I I有有6 6种生产方式：种生产方式：A A1 1B B1 1,A,A1 1B B2 2,A,A1 1B B3 3,A,A2 2B B1 1.A.A2 2B B2 2.A.A2 2B B3 3,其生其生产量分别设为产量分别设为x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6;产品产品II有有2种生产方式：种生产方式：A1B1,A2B1其生产量分别设为其生产量分别设为x7,x8;产品产品III有有1种生产方式种生产方式,A2B2其生产量分别设为其生产量分别设为x9,利润=（销售单价-原料单价）产品件数之和 (每台时的设备费用设备实际使用的总台时数）之和。生产计划的问题（IIII）59生产计划的问题（II）这样对第这样对第I I种产品生产总量为：种产品生产总量为：x1+x2+x3+x4+x5+x6第第II种产品生产总量为：种产品生产总量为：x7+x8，第第III种产品生产总量为：种产品生产总量为：x9。设备设备A1用于生产：用于生产：x1,x2,x3,x7，其单位台时费为：，其单位台时费为：300/6000;设备设备A2用于生产：用于生产：x4,x5,x6,x8,x9，其单位台时费为：，其单位台时费为：321/10000;设备设备B1用于生产：用于生产：x1,x4,x7,x8，其单位台时费为：，其单位台时费为：50/4000;设备设备B2用于生产：用于生产：x2,x5,x9,，其单位台时费为：，其单位台时费为：783/7000;设备设备B3用于生产：用于生产：x3,x6。，其单位台时费为：。，其单位台时费为：200/4000;60我们建立如下的数学模型我们建立如下的数学模型:生产计划的问题（IIII）61 某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？例例1.121.12配料问题配料问题62配料问题配料问题 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学 模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；63目标函数：利润最大，利润=收入-原料支出 约束条件：规格要求 4 个；供应量限制 3 个。Max z z z z=-15=-15=-15=-15x x x x11111111+25+25+25+25x x x x12121212+15+15+15+15x x x x13131313-30-30-30-30 x x x x21212121+10+10+10+10 x x x x22222222-40-40-40-40 x x x x31313131-10-10-10-10 x x x x33333333 s.t.s.t.0.50.5x x1111-0.5-0.5x x1212-0.5-0.5x x1313 0 0（原材料1不少于50%）-0.25-0.25x x1111+0.75+0.75x x1212-0.25-0.25x x131300（原材料2不超过25%）0.75 0.75x x2121-0.25-0.25x x2222-0.25-0.25x x23230 0（原材料1不少于25%）-0.5-0.5 x x2121+0.5+0.5 x x2222-0.5-0.5 x x232300 原材料2不超过50%）x11+x21+x31 100 (供应量限制）x12+x22+x32 100 (供应量限制）x13+x23+x33 60 (供应量限制）xij0,i=1,2,3;j=1,2,364s.t.s.t.0.5 x11-0.5 x12-0.5 x13 0 （原材料1不少于50%）-0.25x11+0.75x12-0.25x13 0 （原材料2不超过25%）0.75x21-0.25x22-0.25x23 0 （原材料1不少于25%）-0.5 x21+0.5 x22-0.5 x23 0 （原材料2不超过50%）x11+x21+x31 100 (供应量限制）x12+x22+x32 100 (供应量限制）x13+x23+x33 60 (供应量限制）xij0,i=1,2,3;j=1,2,3配料问题配料问题65 某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。例例1.131.13投资问题投资问题66 据测定每万元每次投资的风险指数如下表：投资问题投资问题问问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第 五年年末拥有资金的本利在330万元的基础上使 得其投资总的风险系数为最小？67投资问题投资问题 解：解：1 1）确定决策变量：连续投资问题 设 xij(i=15，j=1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下决策变量：A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x2468 2 2 2 2）约束条件：）约束条件：）约束条件：）约束条件：第一年：第一年：A A当年末可收回投资，故第一年年初应把全部当年末可收回投资，故第一年年初应把全部资金投出去，于是：资金投出去，于是：x x1111+x x12 12=200=200 第二年：第二年：B B次年末才可收回投资故第二年年初的资金为次年末才可收回投资故第二年年初的资金为1.11.1x x1111，于是：，于是：x x21 21+x x2222+x x2424=1.1=1.1x x1111 第三年：第三年：年初的资金为年初的资金为1.11.1x x2121+1.25+1.25x x1212，于是，于是 ：x x31 31+x x3232+x x3333=1.1=1.1x x2121+1.25+1.25x x1212 第四年：第四年：年初的资金为年初的资金为1.11.1x x3131+1.25+1.25x x2222，于是：，于是：x x41 41+x x4242=1.1=1.1x x3131+1.25+1.25x x2222 第五年：第五年：年初的资金为年初的资金为1.11.1x x4141+1.25+1.25x x3232，于是：，于是：x x51 51=1.1=1.1x x4141+1.25+1.25x x3232 B B、C C、D D的投资限制：的投资限制：x xi i2 2 30(30(i i=1=1，2 2，3 3，4)4)，x x3333 80 80，x x2424 100 100投资问题投资问题69a)Max z=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200 x21+x22+x24=1.1x11 x31+x32+x33=1.1x21+1.25x12 x41+x42=1.1x31+1.25x22 x51=1.1x41+1.25x32 xi2 30(i=1、2、3、4)，x33 80，x24 100 xij0(i=1,2,3,4,5；j=1,2,3,4）3 3）目标函数及模型：）目标函数及模型：投资问题投资问题70b)b)MinMin f f=（x x1111+x x2121+x x3131+x x4141+x x5151)+)+3(3(x x1212+x x2222+x x3232+x x4242)+4)+4x x3333+5.5+5.5x x24 24 s.t.s.t.x x1111+x x12 12 200 200 x x21 21+x x2222+x x2424 1.1 1.1x x1111 x x31 31+x x3232+x x3333 1.1 1.1x x2121+1.25+1.25x x1212 x x41 41+x x4242 1.1 1.1x x3131+1.25+1.25x x2222 x x51 51 1.1 1.1x x4141+1.25+1.25x x3232 x xi i2 2 30(30(i i=1=1、2 2、3 3、4)4)，x x3333 80 80，x x2424 100 100 1.1 1.1x x51 51+1.25+1.25x x4242+1.4+1.4x x3333+1.55+1.55x x2424 330 330 x xijij0(0(i i=1,2,3,4,5=1,2,3,4,5；j j=1,2,3,4=1,2,3,4）投资问题投资问题711.3单纯形法单纯形法1.3.1线性规划的标准型线性规划的标准型72线性规划的标准型的矩阵表示：Max z=c X s.t.A X=b X 0其中：c=（c1,c2,c n）b=（b1,b2,b m）x=（x1,x2,x n）73任何线性规划都可以化为标准型表示：（1）目标函数（2）约束方程若b0，只须不等式两边同乘以1；是不等号，当“”时，可加上一个松驰变量，当“”时，减去一个剩余变量。（3）变量当x i 0；当x i 无符号要求时，令xi x”i=x i xi 0；x”i 0；741.3.2 一些基本概念一些基本概念前述概念1.可行解；可行解；2.可行域；可行域；3.最优解；最优解；4.最优值；最优值；新概念1.基基：A的一个满秩m维方阵。2.基变量基变量和和非基变量非基变量：基所对应的变量。3.基解基解：令非基变量为零，m个约束方程组的解。4.基可行解基可行解：满足非负条件的基解。5.可行基可行基：基可行解中基变量对应的基。6.最优基最优基：最优解中基变量对应的基。75线性规划的基本定理线性规划的基本定理1.线性规划的可行域是凸集。2.线性规划可行域的极点与基本可行解一一对应。3.线性规划若有最优解，一定可以在可行域的极点达到。761.3.3单纯形法单纯形法考察一个线性规划：Max z=50 x1+30 x2s.t.4x1+3x2120 2x1+x250 x10,x20.其标准型为：Max z=50 x1+30 x2+0 x3+0 x4 s.t.4 x1 +3 x2 +x3 =120 2 x1 +x2 +x4 =50 x1 0,x2 0,x3 0,x4 077在标准型中：基基变量非基变量基解基可行解可行基最优基 x 1,x 2 x 3,x 4（15,20,0,0）是是是 x 1,x 3 x 2,x 4（25,0,20,0）是是否 x 1,x 4 x 2,x 3（30,0,0,10）否否否 x 2,x 3 x 1,x 4（0,50,30,0）否否否 x 2,x 4 x 1,x 3（0,40,0,10）是是否 x 3,x 4 x 1,x 2（0,0,120,50）是是否78单纯形法的基本思路单纯形法的基本思路：1.确定一个初始可行基，转2。2.用非基变量表示目标函数，再用目标函数的系数作检验数。当通过检验，则得到最优解；若不能通过检验，则转3。3.换基迭代：确定出基变量和进基变量，得新的基变量和对应的可行基，转回2。79单纯形法具体计算过程：单纯形法具体计算过程：1.确定初始单纯形表。确定初始单纯形表。2.若全部检验数若全部检验数j j0出基：出基：x r 出基，出基，称称 为轴心元。以为轴心元。以 为中心，构造新单纯为中心，构造新单纯形表，并返回到形表，并返回到2。80三点说明：（1）整个运算在一个表格中，即单纯形表中计算。其本质是矩阵的行变换。（2）当找不出新的进基变量时，即原线性规划无可行解。（3）当最优解的基变量所对应的检验数为零时，原线性规划有无穷多解。具体过程见WinQSB软件。811.3.4.线性规划的具体计算线性规划的具体计算LINDO软件WinQSB软件82