第六章 随机规划
- 格式:doc
- 大小:289.50 KB
- 文档页数:8
第六章 随机规划第一节 问题的提出随机规划所研究的对象是含有随机因素的数学规划问题。
例如,我们熟悉的线性规划问题CX X f =)(min0≥=X bAX (6.1)如果其中的A ,b ,C 的元素中部分的或全部的是随机变量,则称其为随机线性规划问题。
在数学规划中引入随机性是很自然的事情。
在模型中的A ,b ,C 的元素常常代表价格、成本、需求量、资源数量、经济指标等参数。
由于各种不确定性因素的影响,这些参数经常出现波动。
例如,市场上对某种商品的需求量一般无法精确的预知,只能作出大致的预测,某种产品的生产成本往往受原材料价格、劳动生产率等各种因素的影响而经常变化,这些变化与波动,在许多场合可以用一定的概率分布去描述。
因此,在数学规划中引入随机变量,能够使模型更加符合实际情况,从而是的决策更加合理。
例1 某化工厂生产过程中需要A ,B 两种化学成分,现有甲、乙两种原材料可供选用。
其中原料甲中化学成分A 的单位含量为10/a ,B 的单位含量为3/a ;原料乙中化学成分A 的单位含量为10/1,B 的单位含量为3/1。
根据生产要求,化学成分A 的总含量不得少于10/7个单位,化学成分A 的总含量不得少于3/4个单位。
甲、乙两种原料的价格相同,问如何采购原料,使得即满足生产要求,又是的成本最低?显而易见,这个问题可以用线性规划模型来描述。
根据题意,设原料甲的采购数量为1x ,原料乙的采购数量为2x ,容易得到如下线性模型:21)(min x x X f +=,047212121≥≥≥+≥+x x x bx x ax (6.2)于是只要知道a 和b 的值,立即可以求得最优解。
但是,如果由于某种原因,原料甲中化学成分A 、B 的单位含量不稳定,其中T b a ),(=ξ是矩形}131,41{≤≤≤≤y x 内的均匀分布随机向量,则问题(7.2)就成为随机线性规划问题了。
由于引入了随机量,随机规划问题的分析与求解比普通数学规划问题要复杂大多。
产品设计⽅案随机机会约束规划2019-10-170引⾔近年来,伴随着科学技术的飞速发展,市场环境和消费者需求⽇益动态多变,企业之间的竞争愈加激烈,新产品开发成为企业在瞬息万变的市场环境中获取竞争优势的重要⼿段。
⽽产品设计⽅案的优选⼜是新产品开发成功的关键。
在产品设计⽅案的优选中,费⽤—效能(简称费效)分析是⽬前最常⽤的⼀类⽅法,其基本思路是综合费⽤和效能的各种指标,从费⽤和效能两⽅⾯综合评价各备选⽅案,得到费⽤和效能最佳配合的⽅案[1]。
传统的费效分析多使⽤费⽤效能⽐法[2-3],即分别计算出产品的费⽤值和效能值,再⽐较得出效能/费⽤⽐,然后根据决策准则进⾏⽅案优选。
由于⼤部分产品结构复杂,费⽤、效能的评估涉及因素众多,采⽤单⼀指标难以进⾏全⾯、准确的评价,很多学者提出对影响费⽤和效能的主要因素综合考虑,全⾯分析各因素对费⽤-效能的影响。
如熊云峰等[4]提出⼀种加权的多层次多⽬标灰关联综合评估⽅法,对船舶设备的费效进⾏综合评价,进⽽选择最佳的船舶设备⽅案。
赖佳栋等[5]建⽴了费效分析模糊综合评判法,⽤于电器设备购置决策;索中英[6]等建⽴了费效分析的模糊综合评判模型,⽤于飞机研制⽅案的决策;廖武等[7]应⽤数据包络分析⽅法对装备费效进⾏综合评价,为优化装备费⽤规模提供决策⽀持;陈佳[8]利⽤改进DEA⽅法⽤于油轮风险控制设计⽅案的费效分析。
这些⽅法都将产品费⽤和效能作为输出,根据费效⽐进⾏⽅案优选决策,追求⾼的费效⽐是其根本所在。
然⽽这些⽅法并没有对产品的费⽤、效能进⾏约束,使得最终⽅案会出现在满⾜⾼的费效⽐的前提下超出预算或产品⽆法达到预期效能的问题。
韩庆兰等[9]借鉴源⾃美国军⽅的以费⽤为独⽴变量(CostasIndependentVariable,CAIV)的武器装备采办费⽤管理技术,将产品的性能、⽣命周期费⽤及性能参数都作为输⼊,构建了基于CAIV的产品费效权衡模型,应⽤于混凝⼟泵车产品的设计⽅案优选,有效避免了费效分析中存在的弊端。
运筹学必考知识点总结在运筹学中,有一些必考的知识点是非常重要的。
这些知识点涵盖了运筹学的基本概念、方法和模型,对于考生来说,掌握这些知识点是至关重要的。
本文将对运筹学的一些必考知识点进行总结,帮助考生更好地备考。
1. 线性规划线性规划是运筹学中的重要方法之一,它通过建立数学模型来解决各种决策问题。
在线性规划中,目标是最大化或最小化一个线性函数,同时满足一系列线性约束条件。
考生需要掌握线性规划的基本理论,包括线性规划模型的建立、单纯形法和对偶理论等内容。
2. 整数规划整数规划是线性规划的扩展,它要求决策变量取整数值。
整数规划在实际应用中有着广泛的用途,因此对于考生来说,掌握整数规划的基本理论和解题方法是必不可少的。
3. 动态规划动态规划是一种用于求解多阶段决策问题的优化方法。
在动态规划中,问题被分解为多个子问题,并且这些子问题之间存在重叠。
考生需要了解动态规划的基本原理、状态转移方程的建立以及动态规划算法的实现。
4. 网络流问题网络流问题是运筹学中的一个重要领域,它涉及到图论和优化算法等多个方面的知识。
在网络流问题中,主要考察最大流、最小割、最短路等问题的求解方法。
5. 效用理论效用理论是运筹学中的一个重要分支,它研究人们在做出决策时的偏好和选择。
效用函数、期望效用、风险偏好等概念是考试中的热点内容。
6. 排队论排队论是研究排队系统的运作规律和性能指标的数学理论。
在排队论中,考生需要了解排队系统的稳定性条件、平衡方程、性能指标的计算方法等。
7. 多目标决策多目标决策是指在考虑多个目标时的决策问题。
在多目标决策中,往往需要考虑到多个目标之间的矛盾和权衡,因此考生需要掌握多目标规划的基本原理和解题方法。
8. 随机规划随机规划是考虑到不确定因素的决策问题。
在随机规划中,目标函数、约束条件等参数都是随机变量,因此需要考虑到风险和概率的因素。
以上是一些运筹学中的必考知识点,考生在备考过程中需要重点关注这些知识点。
随机优化与随机规划随机优化和随机规划是运筹学和数学领域中一类重要的优化问题求解方法。
它们通过引入随机变量来刻画问题中的不确定性信息,进而对问题进行求解和优化。
本文将介绍随机优化和随机规划的基本概念、方法以及应用领域。
一、随机优化的基本概念随机优化是指在优化问题中引入随机变量的方法,将确定性优化问题转化为随机优化问题,从而考虑问题中的不确定性因素。
随机优化的目标是在考虑不确定性条件下,寻找使得目标函数达到最优的解。
随机优化的基本步骤包括:建立模型、制定目标函数、确定约束条件、引入随机变量、建立随机优化模型、求解最优解。
其中,引入随机变量是随机优化的核心步骤,通过引入随机变量来刻画问题中的不确定性信息。
随机优化可以分为两类:随机线性规划和随机非线性规划。
随机线性规划是指目标函数和约束条件都是线性函数的优化问题;随机非线性规划是指目标函数和/或约束条件中存在非线性函数的优化问题。
二、随机规划的基本概念随机规划是指在规划问题中引入随机变量的方法,将确定性规划问题转化为随机规划问题,从而考虑问题中的不确定性因素。
随机规划的目标是在考虑不确定性条件下,制定合理的规划方案。
随机规划的基本步骤包括:建立模型、制定目标函数、确定约束条件、引入随机变量、建立随机规划模型、求解最优解。
与随机优化相似,引入随机变量也是随机规划的核心步骤。
随机规划可以分为两类:随机线性规划和随机非线性规划。
随机线性规划是指目标函数和约束条件都是线性函数的规划问题;随机非线性规划是指目标函数和/或约束条件中存在非线性函数的规划问题。
三、随机优化与随机规划的应用领域随机优化和随机规划在实际应用中具有广泛的应用领域,以下列举几个典型的应用领域:1. 金融风险管理:随机优化和随机规划可以应用于金融领域中的风险管理问题,通过引入随机变量来描述金融市场的不确定性,进而制定合理的投资组合方案和风险控制策略。
2. 生产调度问题:随机优化和随机规划可以应用于生产调度领域中的问题,通过引入随机变量来刻画生产过程中的各种不确定性因素,进而优化生产计划、资源调度和物流管理。
运筹学知识点总结一、线性规划线性规划是运筹学中最基础、最重要的一个分支。
它的基本形式可以表示为:Max cxs.t. Ax ≤ bx ≥ 0其中,c是一个n维的列向量,x是一个n维的列向量,A是一个m×n的矩阵,b是一个m维的列向量。
线性规划的目标是找到满足约束条件的x,使得目标函数cx取得最大值。
而当目标是最小化cx时,则是最小化问题。
线性规划问题有着很好的性质,它的最优解一定存在且一定在可行域边界上。
而且,很多非线性规划问题也可以通过线性化转化成线性规划问题,因此线性规划具有广泛的适用范围。
二、整数规划整数规划是线性规划的一个扩展,它在线性规划的基础上增加了对决策变量的整数取值限制。
这样的问题往往更加接近实际情况。
整数规划问题的一般形式可以表示为:Max cxs.t. Ax ≤ bx ∈ Zn整数规划问题的求解难度要比线性规划问题高很多。
因为整数规划问题是NP-hard问题,也就是说它没有多项式时间的算法可以解决。
但是对于特定结构的整数规划问题,可以设计专门的算法来求解。
比如分枝定界法、动态规划等。
整数规划问题在许多领域都有着广泛的应用,比如生产调度、设备配置、网络设计等。
三、动态规划动态规划是一种用来求解具有重叠子问题结构的最优化问题的方法。
它的核心思想是将原问题分解成一系列相互重叠的子问题,然后利用子问题的最优解来构造原问题的最优解。
动态规划问题的一般形式可以表示为:F(n) = max{F(n-1), F(n-2)+cn}其中,F(n)是问题的最优解,cn是问题的参数,n是问题的规模。
动态规划问题的求解是一个自底向上的过程,它依赖于子问题的最优解,然后通过递推关系来求解原问题的最优解。
动态规划在资源分配、路径优化、排程问题等方面有着广泛的应用。
四、决策分析决策分析是一种用来帮助人们做出最佳决策的方法。
它可以应用在各种风险决策、投资决策、生产决策等方面。
决策分析的一般形式可以表示为:Max E(u(x))其中,E(u(x))是对决策结果的期望效用,u(x)是决策结果的效用函数,x是决策变量。
潍坊市初中数学教学评一致教学分析九年级下册第6章事件的概率一、单元整体概述课标摘录1.通过实例,了解频数和频数分布的意义,能画频数直方图,能利用频数直方图解释数据中蕴含的信息;2.能解释统计结果,根据结果做出简单的判断和预测,并能进行交流;3.通过表格、折线图、趋势图等,感受随机现象的变化趋势;4.能通过列表、画树状图等方法列出简单随机事件所有可能的结果,以及指定事件发生的所有可能结果,了解事件的概率;5.知道通过大量的重复试验,可以用频率来估计概率.知识结构【教师的思考】1.小学1-3年级能根据给定的标准或者自己选定的标准,对事物进行分类,学会了调查、测量等收集数据的简单方法,并能用自己的方式(文字、图画、表格等)呈现整理数据的结果;4-6年级时会根据实际问题设计简单的调查表,认识了条形、折线、扇形统计图,会计算平均数,能列出简单的随机现象中所有可能发生的结果;七八年级学习了简单随机抽样、会画扇形统计图,会计算中位数、众数、加权平均数,方差。
小学知识较为直观,初中在小学的基础上加入了相关公式和运算分析。
2.高中将学习样本点、有限样本空间、古典概型、简单随机抽样等新知识,初中所学知识的是高中的前置。
3.学生对随机现象和概率有所了解,能说出简单事件的概率,但对于一些容易留下错误印象的问题(射击运动员射中靶和射不中的概率都是1/2)会判断错误,没有建立正确的概率直觉。
【对学生学习的期望】学生将会知道:(基本知识)1.随机事件、必然事件和不可能事件的概念;2.频数、频率、频数直方图的概念;3.各组的频数之和等于实验的次数,各组的频率之和等于1;4.概率的概念和计算公式;5.列表法和画树状图法的原理和步骤.学生将能够(基本技能)1.区分必然事件、不可能事件、随机事件;2.列出频数、频率分布表,画出频数直方图;3.用简单随机事件发生的概率的计算公式计算概率;4.能通过列表、画树状图列出简单随机事件的所有可能结果,以及指定事件的所有结果,求出简单随机事件的概率.学生将获得(基本活动经验)1.通过表格、趋势图等,感受随机现象的变化趋势;2.实验、数据收集、整理和分析的活动经验;3.简单随机事件概率的求法.学生将领悟(基本思想方法)数学建模、演绎推理二、单元学习目标1.通过具体事例,感受随机现象,认识随机事件、必然事件和不可能事件,理解频数、频率的概念,能利用频数直方图解释数据中蕴含的信息;2.通过表格、趋势图等,感受随机现象的变化趋势;3.通过实验、数据收集、整理和分析,体会概率的意义,了解频率和概率的关系,体会随机现象的特点;4.能通过列举法(包括列表、画树状图等方法)列举出简单事件的所有可能结果,以及指定事件的所有可能结果,计算一些简单事件的概率;5.通过参与试验、统计、推断等过程,丰富学生的数学活动经验,体会运用随机观念分析问题和解决问题的方法,发展学生的数据分析观念,形成坚持真理、修正错误、严谨求实的科学态度.三、单元评价任务设计任务一(针对目标1和2):以小组单位,组内成员互相举出生活中事件发生的例子,并按“一定发生”、“一定不发生”、“有可能发生”对举出的例子进行分类,交流分类结果;根据摸球活动试验结果,画出频数直方图,并能说出随机现象的变化趋势。
随机规划的逼近方法
骆建文
【期刊名称】《杭州电子工业学院学报》
【年(卷),期】1994(014)002
【摘要】本文将随机函数V(x,ω)引入随机规划问题·即Z(V(ω))■,对相应的最优化问题的稳定性作了一些探讨.得出了在一定条件下.只要Vn(ω)个分布收敛于v(ω),最优值Z(Vn(ω)就收敛于Z(v(ω)的结果,这个结论对于构造逼近算法,特别是如何估计逼近误差和改进逼近值提供了理论依据。
【总页数】6页(P27-32)
【作者】骆建文
【作者单位】无
【正文语种】中文
【中图分类】O221.5
【相关文献】
1.极大极小随机规划逼近最优值的收敛性 [J], 赵礼阳;霍永亮
2.极大极小随机规划逼近最优值的收敛性 [J], 赵礼阳;霍永亮;
3.二层随机规划逼近ε-最优解集的Hausdorff收敛性 [J], 周婉娜;霍永亮;胡之英
4.极大极小随机规划逼近问题最优解集和最优值的稳定性 [J], 霍永亮
5.一类极大极小随机规划逼近问题最优解集的上半收敛性 [J], 霍永亮
因版权原因,仅展示原文概要,查看原文内容请购买。
运筹学在应用统计学中的优化方法与实践运筹学是一门综合运用数学、统计学以及计算机科学等学科知识来进行优化决策的学科。
它在各个领域中都有广泛的应用,尤其在应用统计学中,它发挥着重要的作用。
本文将介绍运筹学在应用统计学中的一些优化方法与实践。
一、线性规划线性规划是运筹学中最常用的一种优化方法,它适用于很多实际问题的求解。
在应用统计学中,线性规划常常用于优化资源的分配和计划。
例如,在生产过程中,可以利用线性规划确定最优的产量和资源的分配比例,以实现成本的最小化和资源的最大化。
二、整数规划整数规划是线性规划的扩展,在应用统计学中也具有重要的应用价值。
与线性规划不同的是,整数规划的决策变量是整数,这使得它更适用于那些决策变量只能取离散值的问题。
在应用统计学中,整数规划常用于人员调度、货物运输等问题。
例如,在物流管理中,可以利用整数规划确定最优的配送路线和货物的装载方式,以提高运输效率和降低成本。
三、随机规划随机规划是一种将概率论和统计学方法与优化模型相结合的方法。
在应用统计学中,随机规划常用于处理不确定性和风险的问题。
例如,在金融风险管理中,可以利用随机规划模型对投资组合进行优化,以最大化收益并控制风险。
四、非线性规划非线性规划是一种将目标函数或约束条件中包含非线性函数的优化问题。
在应用统计学中,非线性规划常用于拟合曲线和参数估计等问题。
例如,在回归分析中,可以利用非线性规划对数据进行拟合,以找到最优的参数估计值。
五、模拟优化模拟优化是一种基于模拟方法的优化技术,它通过对问题进行多次模拟,寻找最优解。
在应用统计学中,模拟优化常用于处理复杂的优化问题。
例如,在供应链管理中,可以利用模拟优化对供应链网络进行优化,以最大化整体效益。
六、案例研究下面通过一个案例研究,进一步说明运筹学在应用统计学中的优化方法和实践。
假设一家电子公司需要决定在不同地区建立仓库的数量和位置,以满足不同地区的产品需求。
为了降低运输成本和提高产品的响应速度,公司希望在不同地区建立仓库,并确定每个仓库的容量和服务范围。
机械优化设计之数学模型及其实例机械优化设计是指在机械设计过程中,通过数学模型和方法来寻找最优解的一种设计方法。
数学模型的建立是机械优化设计的基础,它可以将机械设计问题转化为数学问题,从而可以应用数学方法进行求解。
本文将介绍机械优化设计中常用的数学模型及其实例。
一、机械优化设计的数学模型分类确定性模型是指在设计过程中,所有设计参数和目标函数的数值都是已知的,可以通过确定的数学方法进行求解。
典型的确定性模型包括线性规划、非线性规划、动态规划等。
随机模型是指在设计过程中,设计参数和目标函数中存在一些随机变量,其数值是不确定的。
对于随机模型的求解,通常需要引入概率论和统计学的方法。
典型的随机模型包括随机规划、可靠性设计、鲁棒设计等。
1.线性规划线性规划是一种常见的确定性优化方法,其数学模型可以表示为:min/max Z = c1x1 + c2x2 + … + cnxn(目标函数)s.t.:a11x1 + a12x2 + … + a1nxn ≤ b1a21x1 + a22x2 + … + a2nxn ≤ b2am1x1 + am2x2 + … + amnxn ≤ bmxi ≥ 0,i=1,2,…,n其中,x1,x2,…,xn为设计参数,c1,c2,…,cn为目标函数中的系数,a11,a12,…,amn为约束条件中的系数,b1,b2,…,bm为约束条件。
线性规划的求解方法主要有单纯形法、内点法等。
2.非线性规划非线性规划是一种常见的确定性优化方法,其数学模型可以表示为:min/max Z = f(x)(目标函数)s.t.:g1(x)≤0g2(x)≤0gm(x) ≤ 0h1(x)=0h2(x)=0hk(x) = 0其中,x为设计参数,f(x)为目标函数,g1(x),g2(x),…,gm(x)为不等式约束条件,h1(x),h2(x),…,hk(x)为等式约束条件。
非线性规划的求解方法主要有梯度法、牛顿法、拟牛顿法等。
第六章 随机规划第一节 问题的提出随机规划所研究的对象是含有随机因素的数学规划问题。
例如,我们熟悉的线性规划问题CX X f =)(min≥=X b AX (6.1) 如果其中的A ,b ,C 的元素中部分的或全部的是随机变量,则称其为随机线性规划问题。
在数学规划中引入随机性是很自然的事情。
在模型中的A ,b ,C 的元素常常代表价格、成本、需求量、资源数量、经济指标等参数。
由于各种不确定性因素的影响,这些参数经常出现波动。
例如,市场上对某种商品的需求量一般无法精确的预知,只能作出大致的预测,某种产品的生产成本往往受原材料价格、劳动生产率等各种因素的影响而经常变化,这些变化与波动,在许多场合可以用一定的概率分布去描述。
因此,在数学规划中引入随机变量,能够使模型更加符合实际情况,从而是的决策更加合理。
例1 某化工厂生产过程中需要A ,B 两种化学成分,现有甲、乙两种原材料可供选用。
其中原料甲中化学成分A 的单位含量为10/a ,B 的单位含量为3/a ;原料乙中化学成分A 的单位含量为10/1,B 的单位含量为3/1。
根据生产要求,化学成分A 的总含量不得少于10/7个单位,化学成分A 的总含量不得少于3/4个单位。
甲、乙两种原料的价格相同,问如何采购原料,使得即满足生产要求,又是的成本最低?显而易见,这个问题可以用线性规划模型来描述。
根据题意,设原料甲的采购数量为1x ,原料乙的采购数量为2x ,容易得到如下线性模型:21)(m in x x X f +=,047212121≥≥≥+≥+x x x bx x ax (6.2)于是只要知道a 和b 的值,立即可以求得最优解。
但是,如果由于某种原因,原料甲中化学成分A 、B 的单位含量不稳定,其中T b a ),(=ξ是矩形}131,41{≤≤≤≤y x 内的均匀分布随机向量,则问题(7.2)就成为随机线性规划问题了。
由于引入了随机量,随机规划问题的分析与求解比普通数学规划问题要复杂大多。
在处理随机规划问题时,人们最容易想到的方法也许是将模型中的随机变量用它们的期望值来代,从而得到确定性的数学规划模型,再去求解。
事实上,过去许多确定性数学规划正是这样建立起来的,但是应当指出,这种处理方法在实际问题中并不总可行的。
为了说明这一点,我们不妨用此方法试解例1中的问题。
容易求得T T b a E E )3/2,2/5(]),[()(==ξ, (6.3) 将此值代入问题(7.2),得到确定线性规划模型如下:21)(m in x x X f +=,0432725212121≥≥≥+≥+x x x x x x (6.4) 可以求得此问题的唯一最优解为T T x x X )11/32,11/18(),(*2*1*==, (6.5) 于是以此*X 作为原随机线性规划问题(7.2)的最优解。
可是,由于问题(7.2)中的T b a ),(是随机向量,我们自然希望知道,上述*X 是问题(7.2)的最优解这一事件的概率有多大?是问题(7.2)的可行解这一事件的概率有多大?然而,我们发现,4/1}3/2,2/5),{(}4,7),{(*2*1*2*1=≥≥=≥+≥+b a b a P x bx x ax b a P T T , (6.6)也即,*X 对问题(7.2)是可行解以0.75的概率是不可能的,只有0.25的可能性,这个解显然是不可用的。
这个例子说明,用上述方法处理随机规划问题时应当十分谨慎。
随机规划问题可以大致分为两种类型:被动型和主动型。
被动型即所谓“等待且看到(wait and see )”模型,即决策者等待着观察问题中随机变量的实现,然后适当地利用这些实现的信息作出决策,分布问题即属于此种类型。
主动型即所谓“这里且现在(here and now )”模型,决策者必须在没有机变量的实现的信息的情况下就作出决策,二阶段问题和机会约束规划均属于这种类型。
第二节 分布问题一、分布问题的提法例1 设某工厂生产几种产品,需要用m 种原料。
第j 种产品对第i 种原料的单位需要量为ij a ,第i 种原料的拥有量为i b ,第j 种产品的单位利润为j c ,试问如何安排各产品的生产量j x (),...,1n j =),以使的在现有条件下利润最大?容易列出这个问题的线性规划模型为∑==nj j j x c X f 1)(maxnj x m i b x a j i n j j ij,...,1,0,...,1,1=≥=≤∑= (6.7)进一步考虑后,发现上述模型中的系数ij a 总存在误差,故认为ij a 是服从正态分布的随机变量;而单位利润系数j c 亦可能随市场价格波动而变化,此外原料拥有量i b 也可能因运输、保管等原因而发生短缺。
于是,上述系数均可视为随机变量,记为)(w a ij ,j c )(w ,)(w b i ,Ω∈w (n j m i ,...,1;,...,1==)。
为了合理安排生产,显然希望知道,在各种可能的情况下,)(max X f 的值是什么,也即希望知道)(max X f 的分布如何,或者希望知道)(max X f 的数学期望是多少。
也就是说,对于每个样本Ω∈w 求解一个线性规划问题∑==nj j j x w c X f 1)()(maxnj x m i w b x w a j i n j j ij,...,1,0,...,1),()(1=≥==∑= , (6.8)然后再求)(max X f 的分布。
这就是本节将要讨论的分部问题。
一般地,所谓分布问题就是对于每个样本Ω∈w 求解一个线性规划问题X w C w )(min )(=ξ)()(≥=X w b X w A , (6.9) 并求)(w ξ的分布函数或其他概率特征。
上述问题中,)(w A 为随机矩阵,)(w b 和)(w c 分别随机向量。
显然为使上述分布问题在数学上有意义,首先要求)(w ξ必须是一个随机变量,即)(w ξ是概率空间),,(P P Ω上的Borel 可测函数。
对此有如下定理。
定理 1在上述分部问题中,最优目标函数值)(w ξ是一个随机变量,并且适当选择后可以找到该问题的一个最优解)(*w X 为随机向量。
随着w 的变化,问题(7.9)的最优目标函数值)(w ξ可能有限,也可能为无穷大。
如果)(w ξ取∞+活∞-的概率大于0,则)(w ξ的数学期望及其它概率特征均不存在,从而该问题在许多情况下将无实际意义。
因此,我们感兴趣的是:1))(:(=+∞<<-∞w w P ξ的情况,此时问题的最优值称为无缺陷的分布。
对于分部问题可以像对待普通线性规划那样按照参数规划的思路来讨论和求解,比如单纯形法、灵敏度分析等。
第三节 期望值模型在期望约束下,使得目标函数的期望值达到最优的数学规划称为期望值模型。
期望值模型是数学规划中常见的形式之一,如期望费用极小化,期望值模型极大化问题等等。
首先考虑报童问题。
报童需要每天提前到邮局定购报纸并确定所定购的报纸数量x 分,每份价格为c 元。
已经知道每份报纸的售价为a 元。
如果报童没有卖完当天的报纸,则回收中心以极低的价格b 元回收报纸。
假设每天报纸的需求量为ξ,若ξ>x ,则每天报纸的剩余量为ξ-x ,否则为0。
这样报童的受益为⎩⎨⎧>-+-≤-=ξξξξx b a x c b x x c a x f ,)()(,)(),( , (6.10) 在实际问题中,报童的需求量ξ通常是随机变量,从而导致效益函数),(ξx f 也是随机变量。
既然不能准确地预测出订购x 份报纸的实际收益,一个自然的方法就是考虑期望收益⎰⎰+∞-+-+-=xx d x c a d b a x c b x f E ξξφξξφξξ)()()(])()[()],([0, (6.11)其中E 表示期望值算子,)(ξφ表示需求量ξ的概率密度函数。
报童问题就是寻找最优的定购数量x 使期望收益)],([ξx f E 达到最大值,这是一个典型的期望值模型。
一、期望算子假设t 维随机向量ξ的概率密度函数为)(ξφ,则随机向量ξ的期望值定义为⎰=tR d E ξξξφξ)(][, (6.12) 通常也称其为均值设f 为定义在t R 上的实函数,则)(ξf 是一个随机变量,其期望值))((ξf E 可以通过下式来计算:⎰=tR d f f E ξξφξξ)()()]([, (6.13)期望值算子有如下的基本性质:若b a +=ξη,其中a 和b 是常数,则b aE E +=][][ξη, (6.14)更一般的情况,设n ξξξ,...,,21是n 个随机变量,且期望值][i E ξ(n i ,...,2,1=)存在,则有][...][][]...[2121n n E E E E ξξξξξξ+++=+++, (6.15)设n ξξξ,...,,21是n 个相互独立的随机变量,且期望值][i E ξ(n i ,...,2,1=)存在,则有][]...[].[]....[2121n n E E E E ξξξξξξ=, (6.16)二、期望值模型单目标期望值模型的一般形式为⎪⎪⎩⎪⎪⎨⎧===≤qk X h E pj X g E t s X f E k j ,...,2,1,0)],([,...,2,1,0)],([.)],([max ξξξ, (6.17) 其中X 是一个n 维决策向量,ξ是一个t 维随机向量,其概率密度函数为)(ξφ,),(ξX f 是目标函数,),(ξX g j 和),(ξX h k 是随机约束函数,p j ,...,2,1=,q k ,...,2,1=由于⎰=tR d X f X f E ξξφξξ)(),()],([ ⎰=t Rj j d X g X g E ξξφξξ)(),()],([,p j ,...,2,1=, (6.18) ⎰=t Rk k d X h X h E ξξφξξ)(),()],([,q k ,...,2,1= 一个可行解*X 是期望模型最优解,如果对于任意的可行解X ,有)],([)],([*ξξX f E X f E ≥成立。
第四节 机会约束规划作为第二种随机规划,机会约束规划(Chance Constrained Programming )主要是针对约束条件中含有随机变量,且必须在观察到随机变量的实现之前作出决策的情况。
考虑到所做的决策在不利情况发生时可能不满足约束条件,而采用一种原则:即允许所作决策在一定程度上不满足约束条件,但是该决策应使约束条件成立的概率不小于某一个置信水平α。
求解机会约束规划的传统方法是根据事先给定的置信水平,把机会约束规划化为各自的确定等价类,然后用传统的方法求解其等价的确定性模型。