投资效益优化问题

应用数学系李晓彬应用数学系1、投资决策问题产生背景企业在某时期拥有一笔资金，如通过采用购买股票或国债的形式向外投资，如何选择投资项目，可获最大利润。应用数学系企业为提高产品质量或扩大生产，需对原有设备进行技术改造或新建一些项目工程。如何使有限资源充分被利用，以达到最大效益？注：这里的资－－指资金、材料、人力等各资源应用数学系2、投资决策问题数学模型假定某公司要对n个投资方案作出选择10jjx投资第个项目否则应用数学系设：n=可以投资项目的个数m=实施投资项目所需有关资源的种类数=各种资源的拥有量=实施第j项投资所需消耗的第i种资源的数量=实施第j项投资所能获得的收益(1,2,,)imibijajc应用数学系公司希望解决的问题，可表示为：11..1,2,,011,2,,njjjnijjijjMaxzcxstaxbimxjn或应用数学系3、问题的求解整数规划问题(IntegerLinearGrogramming)背包问题决策变量为0-1变量jx应用数学系物品项目食品氧气冰镐绳索帐篷照相器材通讯设备重量（kg）55261224重要系数201518148410重要系数4392.330.6722.5重量例、一登山队员允许携带的最大重量为25公斤，如何确定最优方案？应用数学系解决的问题可表示为：123456712345672015181484105526122425..011,2,,7iMaxzxxxxxxxxxxxxxxstxi或按物品重要系数与重量比值从大到小选取。只帐篷落选，最优携带物品总重24kg。123467510xxxxxxx应用数学系例、某公司有5个投资项目被列入投资计划，各项目需要的投资额和期望收益如下表。公司只有600万元可用于投资。项目12345投资额（万元）210300100130260期望收益（万元）1502106080180应用数学系由于技术上的原因，投资受到以下约束（1）项目1、2和3至少应有一项选中。（2）项目3、4只能选一项。（3）项目5选中的前提是项目1必须选中。问：如何确定一最优投资方案使得投资收益最大？应用数学系决策变量为0-1变量解决的问题可表示为：1234512345123345115021060801802103001001302606001..1011,2,,5iMaxzxxxxxxxxxxxxxstxxxxxi或10iix投资第个项目否则ix应用数学系项目12345投资额（万元）210300100130260期望收益（万元）1502106080180投资回报率0.7140.70.60.6150.692计算各方案的投资回报率：应用数学系由约束2，可选由约束3，可选由约束4和1，可选145111xxx项目12345投资回报率0.7140.70.60.6150.692230xx总投资额为：210+130+260=600万元总收益为：z=410万元应用数学系4、整数规划求解过程中存在的问题•解对应的LP问题，然后将其解舍入到最靠近的整数解。可行：LP的解较大，最优解对舍入误差不敏感。否则，可行性差或不可行。应用数学系•ILP的可行解大大少于LP的可行解，用枚举法求解ILP问题。可行：问题的变量个数、可行解集的格点数很少。应用数学系5、分枝定界法基本思路：根据某种策略将原问题的可行域分解为越来越小的子域，并检查每个子域内整数解的情况，直到找到最优的整数解或证明整数解不存在。应用数学系1、求解ILP问题的松弛问题，得一个整数解，则为所求最优解。2、求解ILP问题的松弛问题，得非整数解。则ILP的最优解不优于LP的最优解。3、求解过程中已得一个整数解，则最优整数解不劣于该整数解。三种情形应用数学系0z松弛问题的解值z最优整数解0izzzzz最优整数解满足关系iz目前已找到的整数解zz：下界：上界对最大化问题：对最小化问题：0izzzzz应用数学系分枝：从求解松弛问题开始，将线性规划问题的可行域分为小的子域。定界：分枝过程中找到的更好的整数解来不断修改问题的上界、下界。应用数学系例：求解下列ILP121212126217..5944Maxzxxxxstxxxx，为正整数原问题之松弛问题的可行域和最优解如图：应用数学系优先选择为分枝变量1x应用数学系分枝后可行域缩小应用数学系例、某公司有22亿资金可用来投资，现有6个投资项目可供选择，各项目需要的投资额和预计年收益如下（每项目投资一份或不投资）。问如何确定一最优投资方案使投资收益最大？项目123456投资额（亿元）526468年收益（亿元）0.50.40.60.50.91收益率0.10.20.10.1250.15.0.125应用数学系决策变量为0-1变量：解决的问题可表示为：1234561234560.50.40.60.50.952646822..011,2,,6iMaxzxxxxxxxxxxxxstxi或10iix投资第个项目否则ix应用数学系放宽约束条件，允许取正实数值，优先选择收益率最高的项目，得到两组最优解：ix1234561234561(,,,,,)(0,1,,1,1,1)32(,,,,,)(,1,0,1,1,1)5xxxxxxxxxxxx应用数学系增加约束：根据优先选取收益率高的项目的原则，允许其余变量取非负实数。对应年收益：10.40.60.50.913.0320.50.40.50.913.05i10x或（i=1,3）所以，实际最优解3.0应用数学系2.9应用数学系例、10个工件需在同一台机器上加工，要求在工件抵达后266小时内加工完毕，否则赔款，赔款金额正比于延误时间。具体情况如下表。由于机器故障，10个工件抵达后T小时才开始加工。问：如何安排加工次序，使得赔款最少？紧前工件应用数学系工件号12345678910加工时间20282545161260102030紧前工件387/1,2,684359赔款/小时121415101011128674731加工次序约束8265109应用数学系假设：机器加工下一工件时，准备时间忽略。加工顺序为第j次序加工完的工件共耗时赔款总额12310,,,,,ssssis1ijsitT1011max266,0iijssjiPtTw应用数学系赔款总额1011266,266iijssjiTPtTw1011266,max266,0iijssjiTPtTw应用数学系不妨设目标：求加工次序使P最小1011166,max100,0iijssjiTPtw12310,,,,,ssss应用数学系4731加工次序约束826910547311123144473max100,01,45,1002,(4560100)12603,(456025100)15450iijssisssssPtwjttwwPPjPPjPP元元应用数学系2342元2266元3182618266162211510元830元1550元1782元1420元2522元1590元1110元2782元2838元2662元3722元3666元3882元应用数学系4731加工次序约束82691055910891015910max100,03198iijssisssPtwPPPPPP元应用数学系4731最优加工次序8269105121010114710max100,0366631986364iijssjisssPtwPPPPPP元应用数学系选择对问题影响最大的变量首先分枝按目标函数的系数选择按非整数变量选择按人为给定的顺序选择6、提高分枝定界法的搜索效率应用数学系选择有利的分枝节点，减少搜索次数，尽快找到好的整数解.深探法广探法预估法