精华内容
下载资源
问答
  • 文章目录机场出租车优化问题摘 要问题的重述问题的分析2.1问题一的分析2.2问题二的分析2.3问题三的分析2.4问题四的分析符号说明模型的建立与求解5.1 问题一模型的建立与求解5.2模型二的建立与求解5.3问题三5.4问题四...

    • 之前参加了一次全国大学生数学建模竞赛,没有用官方要求matlab,用的python,于是整理了下论文和代码如下。

    机场出租车优化问题

    摘 要

    • 本文针对机场的出租车优化问题进行了研究,建立了基于多属性的出租车司机接客决策树模型,通过基于Python的爬虫技术,获得了交通信息数据集,经过基于大数据的程序批量预处理后,作为验证集与其他不确定属性协同验证了模型的可行性,以此推广应用到出租车司机的收益问题上
    • 针对问题一,概括为建立出租车司机选择的决策模型。其主要思想是:首先宏观分析出租车司机决策模型的本质影响机理:收益值;然后列举出影响收益值的下一级因素:排队时间,放空时间,接客收益时间,继续向下分析出影响时间的多个属性:等车乘客数及其增量,排队车辆数,机场续车池分批效率,最高效空载距离,以及其他不确定因素。从底层属性到决策结果建立出三层决策树模型。(如:附录一\1.问题一)。
    • 针对问题二,概括为验证模型并分析可行性和多属性因子的问题。首先基于问题一决策树模型底层影响属性,判断出影响司机决策的主观因素需要用到的验证集:该时间段航班数据集和最高效空载距离集;然后通过Python爬虫技术,获得成都双流机场到港航班的数据集和成都出租车GPS定位的打车需求量和出租车分布的特征数据集;再通过Python进行数据集清洗预处理,得到某一时间段航班数量表和最高效空载距离,通过类比推理的思想,验证了百度地图热度图的参考价值,将百度地图热度图数据作为短距离运输最高效空载距离参考;最后通过Python进行决策树构建以及大数据运算,得出每天每个时间段的出租车司机决策结果。(如:附录一\2.问题二)
    • 针对问题三,概括为有约束条件的最优化问题。首先收集并处理选定机场的历史数据资料设计一个预方案大致判断设置的上车点个数的最小值和乘客分布,再基于排队论模型确定符合题目条件的多点纵列式排队服务系统,并且确定评价该系统的评价指标便于评价系统和模型的优化程度,接着进行对系统中乘客进行相关的概率计算和分析,再结合乘客等等待时间总费用和上车点及排队服务系统的建设和服务成本,以两者之和为最小为目标函数建立优化系统的费用决策模型。求解何时可取得最优数值,得出上车点为5个时总乘车效率最高。
    • 针对问题四,概括为需要改善之前建立的决策树模型的时间距离收益属性,有针对的提供补偿措施。求出问题一的决策树模型第二层的时间距离收益的拐点,找到即使比排队时早接客但是由于空载原因使收益仍然低于排队的时间或距离区间;再通过这个区间进行长途短途分类;然后结合实际情况得出优先方案。
    • 最后,本文对模型进行了误差分析,还对模型的优点和缺点进行了评价,分
      别在广度和深度上对模型进行了推广。

    关键词:多属性决策模型;多点纵列式排队;费用决策;大数据处理;
    Python爬虫

    问题的重述

    如今出租车已经成为了一个热门行业,而飞机是很多人出行的重要工具。因此送客去机场都是很多出租车司机都会面临的工作线路,而将乘客送入机场后,出租车司机将会面临两个选择:

    (A) 前往到达区排队等待载客返回市区。出租车必须到指定的“蓄车池”排队等候,依“先来后到”排队进场载客,等待时间长短取决于排队出租车和乘客的数量多少,需要付出一定的时间成本。

    (B) 直接放空返回市区拉客。出租车司机会付出空载费用和可能损失潜在的载客收益。

    请结合实际情况,建立数学模型研究下列问题:

    (1) 分析研究与出租车司机决策相关因素的影响机理,综合考虑机场乘客数量的变化规律和出租车司机的收益,建立出租车司机选择决策模型,并给出司机的选择策略。

    (2) 收集国内某一机场及其所在城市出租车的相关数据,给出该机场出租车司机的选择方案,并分析模型的合理性和对相关因素的依赖性。

    (3) 在某些时候,经常会出现出租车排队载客和乘客排队乘车的情况。某机场“乘车区”现有两条并行车道,管理部门应如何设置“上车点”,并合理安排出租车和乘客,在保证车辆和乘客安全的条件下,使得总的乘车效率最高。

    (4) 机场的出租车载客收益与载客的行驶里程有关,乘客的目的地有远有近,出租车司机不能选择乘客和拒载,但允许出租车多次往返载客。管理部门拟对某些短途载客再次返回的出租车给予一定的“优先权”,使得这些出租车的收益尽量均衡,试给出一个可行的“优先”安排方案。

    问题的分析

    2.1问题一的分析

    分析问题一,需要找出影响出租车司机决策的因素,从机场乘客数量变化规律和司机收益两方面确定司机的选择策略。

    首先从司机的角度比较排队等候载客和空载返回市区拉客两种选择所需要的时间的多少。再分两种情况比较两种选择的收益:第一种情况是排队时间大于空载时间即排队司机接到乘客前,若选择空载返回的司机的净利润大于0,则最后选择空载返回;第二种情况是排队时间小于空载时间,即排队司机的成本消耗较少,则最后选择排队等待载客返回市区。

    该司机排队等待到接到乘客时没有油费的亏损,盈亏均为0。如果需要排队的时间很短,若是之前选择放空,因为选择排队到拉到客的时间小于选择放空之后到拉到客的时间,而排队盈亏为0,放空有油费亏损,所以比较之下选择排队亏损的比放空少,选择接客;如果排队的时间太长,而若是之前选择放空,放空的车已经接到客了,而排队情况下还在排队没有接到客,放空情况下考虑油费成本后能有盈利,而排队盈利为0,则选择接客是不理想的决策,应该选择放空;如果排队时间很长,在排队的时间内若是放空已经有拉到客了,但是拉到客的利润不能弥补之前放空的损失,即此时放空有亏损,则选择放空是不理想的决策。

    2.2问题二的分析

    分析问题二,需要搜集数据来验证问题一所建立的模型,搜集的数据是问题一建立的模型的以及对模型影响较大的变量,比如某个飞机场在单位时间段里下飞机的乘客数量,已经在排队的人数和出租车,人和出租车分批疏散效率,附近打车需求量和出租车的供应数,载客数,不确定因素,并且还需要将数据带入模型验证模型的可行性以及相关因素的发生概率。

    2.3问题三的分析

    分析问题三,现拟定机场的乘车区域有两条行车道,需要保证车辆和乘客安全的条件下设置上车点。两条行车道的上车点设置分两种情况,第一种情况是两条道路都作为可载客的停车区,第二种情况是靠近上车点的一侧作为停车区,另一侧道路不作停车区。由于第一种情况极其容易造成交通堵塞和引发安全隐患,与题目中“保证车辆与乘客的安全”不符,因此不作考虑。上车点的确立是会产生建设成本,因此本文在乘客的等待时间应该尽可能小的前提下取上车点个数的最小值,该问题为有约束条件的多目标规划问题。

    首先以问题一、二中搜集到的关于机场的航班和客流量数据进行处理得出单位时间内平均出站人数,再设上车点的个数为变量并用式子表示出乘客等待的总时间和上车点的建设成本(即该上车点的总费用),然后建立两者最小的目标函数,其次,乘客由于天气、夜晚时间的敏感、排队的人数过多等种种原因不选择搭乘出租车,这时需要考虑乘客搭乘出租车的概率对乘客人数的影响,引入排队系统的组成部分的概率,再结合上车点的总费用作约束条件,求出总费用最低时的上车点的个数。

    2.4问题四的分析

    分析问题四,针对短途载客再次返回的出租车司机给予一定的“优先权”是所有司机的收益相对均衡。

    2.4.1 短途载客和长途载客的界定

    由于已知问题一的决策树模型第二层的时间距离收益的拐点,找到即使比排队时早接客但是由于空载原因使收益仍然低于排队的时间或距离区间;再通过这个区间进行长途短途分类;然后结合实际情况得出优先方案。

    短途载客的界定有两个条件:

    目的地距离机场不超过22公里;
    司机到达目的地后返回机场的时间不得超过1小时;
    长途载客的界定

    2.4.2 短途载客与长途载客的比较

    由于出租车司机的收益与行驶路程有关,行驶路程越大,司机收益相对越多。因此,绝大多数司机希望能长途载客。短途载客的司机虽然能够在较短时间内回到机场“蓄车池”继续等候载客,但是也是因此,这类司机等待的时间往往比送客时间长,也就是说,这类司机很容易面临“排队两个小时,但是送客十五分钟”的不利局面,而这类司机的收益也不容乐观。

    经常能够遇到长途载客的司机就不会面临上述短途载客司机的困境,他们的收益也相对较多。

    2.4.3 针对短途载客司机的相关策略

    一些地区规定:在乘客上车确认短途后,司机向管理人员报告,管理人员将记录了里程表数和车牌号的“插队条”发给司机,司机在将乘客送达目的地后,若选择继续返回机场接客,则凭借“插队条”直接进入上车点,几乎不用排队。

    模型假设与准备
    3.1模型的假设

    假设每辆出租车的性能相同。
    假设每个乘客进入上车点后不返回。
    假设每辆出租车从接客到起步的时间相同
    假设路面情况良好,司机行驶过程中无意外发生。
    假设每个上车点可以显示所有上车点有无使用的信息。
    假设相邻上车点的距离相等。
    3.2模型的准备

    排队论模型是解决工厂车间生产问题中一种常见的数学模型。通常来说,在一个排队系统中,包含一个或多个“服务设施”,同时也存在许多需要进入服务系统的“被服务者”。当被服务者进入服务系统后却不能立即得到服务时,便会出现排队现象。

    多点纵列式出租车排队服务系统属于面向乘客的带有多个服务台和一个公共队伍的排队系统。乘客到达排队系统后,排在队伍前端的乘客可以根据当前上车点的出租车服务状态分散到纵向排列的多个“服务台”获得服务。出租车则由内侧车道驶入港湾式上车点搭载乘客,服务结束后驶离上车点,然后由后面的出租车依次补位。

    符号说明

    在这里插入图片描述

    模型的建立与求解

    5.1 问题一模型的建立与求解

    5.1.1 问题一模型的建立
    5.1.1.1 出租车司机接客决策树模型第一层——判断结果层(Z)

    出租车司机将只会面临两种选择:

    前往到达区排队等待载客返回市区
    直接放空返回市区拉客
    这两种选择相互之间是独立的,两个选项之间只能二选一,于是构成第一层决策树,表示判断结果Z(A)或者Z(B)。

    5.1.1.2 出租车司机接客决策树模型第二层——收益值决策层

    基于现实实际情况,出租车司机首先会考虑自身的收益,于是我们基于出租车司机的收益情况,建立第二层决策树。即第二层决策树是模拟司机在决策时的收益预测。

    我们定义以时间为基准的收益为Wt,即收益跟时间有关,

    分析该司机排队等待到接到乘客时没有油费的亏损,盈亏均为0,即Wty= 0

    如果需要排队的时间很短,若是之前选择放空,因为选择排队到拉到客的时间小于选择放空之后到拉到客的时间,而排队盈亏为0, 即Wty = 0,放空有油费亏损,即Wtn < 0,所以比较之下选择排队亏损的比放空少,即Wty>Wtn,选择接客;

    如果排队的时间太长,若是之前选择放空,放空的车已经接到客了,而排队情况下还在排队没有接到客,放空情况下考虑油费成本后能有盈利,即Wtn>0,而排队盈利为0,即Wty = 0,即Wtn > Wty,则选择排队接客是不理想的决策,应该选择放空;如果排队时间很长,在排队的时间内若是放空已经有拉到客了,即Wty = 0,但是拉到客的利润不能弥补之前放空的损失,即此时放空有亏损Wtn < 0,Wtn < Wty,则选择放空是不理想的决策。

    决策层情况如下:

    A. Wty=0,Wtn<0

    B. Wty>0,Wtn<Wty

    C. Wty=0,Wtn>0

    5.1.1.3 出租车司机接客决策树模型第三层——收益影响层

    根据前面的叙述,导致收益决策层三种情况的因素是排队到接到客人的时间t1以及决定空载到载到人的时间t3。

    当t1>=t3,空载到载到客人比排队早,空载存在两种情况:

    A. 折合空载损失,一直到排队载到客人这段时间里面的收益为正;

    B.折合空载损失,一直到排队载到客人这段时间里面的收益为负;

    当t1<t3,排队到载到客人比空载早,排队存在一种情况:

    C.空载没载到人一直损失;

    5.1.1.4 出租车司机接客决策树模型第四层——时间影响层

    根据前面的叙述,t1和t3是收益影响因素;而仍然存在其他因素影响t1和t3。

    t1由两个大因素影响:

    车运完了人有:t1=Tc
    人运完了前面还有车需要等待:t1=Tp+C
    在这里插入图片描述

    5.2模型二的建立与求解

    Step1. 先基于问题一决策树模型底层影响属性,判断出影响司机决策的主观因素需要用到的验证集:该时间段航班数据集和最高效空载距离集;(数据集见数据文件包)

    Step2.然后通过Python爬虫技术,获得成都双流机场到港航班的数据集和成都出租车GPS定位的打车需求量和出租车分布的特征数据集;(Python代码见附录二,数据集见数据文件包)

    Step3.再通过Python进行数据集清洗预处理,得到某一时间段航班数量表和最高效空载距离,通过类比推理的思想,验证了百度地图热度图的参考价值,将百度地图热度图数据作为短距离运输最高效空载距离参考;

    Step4.最后通过Python进行决策树构建以及大数据运算,得出每天每个时间段的出租车司机决策结果。(计算过程见Python代码)

    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    5.3问题三

    问题三需求解使乘客的等待时间和上车点建设成本最少的上车点个数,使得总的乘车效率最高,这是一个有约束条件的最优化问题。

    首先,处理成都双流机场航班人次数据,求得一定单位时间内乘客出站搭乘出租车的人数将乘客等待的总时间产生的时间耗费和上车点的建设和服务的总费用作为两个决策变量,以两者之和最小作为目标函数,基于排队系统的状态概率稳定时建立关于排队系统的费用决策模型,编写程序求得建设上车点的最少个数及具体位置。
    在这里插入图片描述
    图 1 问题三的流程图

    按照惯性,大部分司机在进入乘车区时选择将车停在最近且有乘客的上车点的位置,但是这种情况最终就有极大可能性造成后面上车点长时间屋出租车停放的现象,从而使后面的部分上车点乘客等待时间过长的情况。因此,想要提高乘车效率,就要尽量避免上述情况。

    我们将设计一个预方案来预估结果: 假设第一个出租车在第一个上车点接人,从第一个出租车停在第一个上车点的那刻开始计时,即此时t=0,后面来的每一辆车都找到最近的且没有其他出租车停靠的上车点停车接客

    将上车点依次编号,分别为:①,②,③,④,⑤…
    为按顺序进入乘车区的批量出租车的编号 i=1…n

    下面列举了n=2,4,8时可以设置的上车点的最少数量以及乘客分布:

    表 1
    在这里插入图片描述
    表 2
    在这里插入图片描述
    表 3
    在这里插入图片描述
    可以得到的结论为:

    当n=2时,至少设置两个上车点,每个上车点乘客比例约为1:1;
    当n=4时,至少设置三个上车点,每个上车点乘客比例约为2:1:1;
    当n=8时,至少设置三个上车点,每个上车点乘客比例约为3:3:2;

    5.3.1多点纵列式的排队系统

    由前文的模型准备中可得出租车按多向纵列排队等待乘客,接到乘客后离开上车点,后方来车按顺序补位。由实际经验得出

    假设排队系统中有 个上车点,有 个乘客。设乘客平均到达率 ,单位上车点的平均服务率 ,即单个上车点单位时间内完成服务离开系统的乘客人数,所有上车点的总平均服务率 。 表示排队系统的服务强度, 为系统中乘客到达率与服务率之比。其中排队系统的服务率 可由以下公式计算得到:
    在这里插入图片描述
    显然,若 越大排队越拥挤。当 大于1时,系统将出现乘客排队的拥挤现象。

    5.3.2排队系统的评价指标

    系统评价指标是与乘客密切相关的排队长度 和乘客等待的总平均时间 。从机场和乘客的角度出发,都希望两者的取值越小越好。其中队列长 是指排队系统中正在等待的平均乘客数,队长 表示队列长 与正在接受司机接送服务的乘客数之和。乘客等待的总平均时间 是乘客从到开始排队到乘车离开的平均时间。

    5.3.3多点纵列式出租车排队系统

    多点纵列式排队系统是面向乘客的结合多个服务站点和出租车司机的排队系统。乘客按照各自的路线到达排队系统后,排在该队伍最前端的乘客优先接受服务,后面的乘客依次
    在这里插入图片描述
    图 2 出租车排队示意图

    我们可以将乘车区简化为矩形ABCD(如图)
    在这里插入图片描述
    图 3 简化乘车区间

    规定如下:

    1. EF为两条车道的分界线,AB边为安置上车点的一方,则ABFE区域为出租车司机停靠载客的区域,
    2. CDEF为行驶区域 行车方向由AD→BC
    3. A出安置第一个上车点,B出安置最后一个上车点

    5.3.4排队系统的相关概率和分析

    机场外的行车道不会无限长,排队系统在稳定工作状态时,系统中出租车乘客数为 概率如下:
    在这里插入图片描述
    结合排队系统中乘客排队的队长 与乘客等待的总平均时间 对系统进行分析得:
    在这里插入图片描述
    5.3.5优化系统的费用决策模型

    利用排队系统的费用决策模型对排队服务系统进行优化。假设乘客等待时间的总费用 ,上车点建设成本 ,其中 为每位乘客单位时间内的等待时间费用, 为单个上车点的建设费用和服务时间消费。因此需要满足两者之和最小才能使排队系统进一步优化,即:
    在这里插入图片描述
    其中, ,约束条件即:
    在这里插入图片描述
    5.3.6出租车排队服务系统及优化结果

    成都双流国际机场是国内八大区域枢纽机场之一,据2017年8月机场官网信息显示,机场共开通中国国内外209多个通航点,可保障旅客吞吐量5000万人次,自从2009年起,旅客吞吐量持续不断增长,并在2017年全年出入境客流突破500万人次,仅次于上海浦东、北京首都、广州白云国际机场。由此可知成都双流机场是一个大型的交通枢纽,它对外连接了国内外的许多航线,对内主要集结地铁、公交车、出租车、私家车、市区巴士和机场巴士的交通方式。出租车作为乘客离开机场的主要交通方式,出租车的上车点优化和排队服务系统的提高对疏散机场的客流和衔接城市与机场的交通具有重要意义。

    本文选取成都双流机场为例对上车点数量和多点纵列式排队服务系统,可以采用前文的费用决策模型对排队服务系统进行优化,得出最优个上车点。这里可以用问题一、二中收集并处理的双流国际机场的航班旅客数据,通过对其中规定单位时间内的平均搭乘出租车的乘客数和平均当前出站的总乘客的比值作为出租车排队系统中的乘客到达率 ,单位时间内系统中服务的乘客数即服务率 ,假设乘客等待时间总费用与上车点建设费用和服务时间消费法的比为 。成都双流机场航班乘客信息见附录,部分航班乘客信息如下表,将分为凌晨、白天、夜晚三部分进行数据展示,便于合理分析机场的客流和出租车与乘客的信息。

    表 4 凌晨时机场航班人次信息
    在这里插入图片描述
    表 5 白天机场航班人次信息
    在这里插入图片描述
    表 6 夜晚机场航班人次信息
    在这里插入图片描述
    由于时间和视线原因,大多数人认为凌晨和夜晚非飞机出行的最佳时刻。但是,根据附录中的整体信息比较和表1发现有较多乘客选择凌晨时间段的出行。根据表1中搭乘出租车的乘客数可计算出对应的乘客的到达率和系统服务率如下表。

    表 7乘客到达率与服务率
    在这里插入图片描述

    接下来用费用决策模型对成都双流国际机场的出租车上车点及排队服务系统进行优化,计算结果如下:
    表 8 费用决策模型计算过程
    在这里插入图片描述
    由上述计算结果可得,当 =5,满足原模型的约束条件,即此时乘客时间消费和上车点及系统的成本之和最小。这说明当设置5个出租车上车点时,可实现排队服务系统的成本和费用相对较小。

    5.4问题四

    问题四需要给出一个“优先安排”方案,使得对机场往返载客的出租车司机收益均衡。

    概括为需要改善之前建立的决策树模型的时间距离收益属性,有针对的提供补偿措施。首先将问题二的基于GPS定位的打车需求量和出租车分布的特征数据集进行目的地概率预测,表现形式以平面-气泡图转化为热度图呈现,得出地点概率预测列表,得出距离概率期望值;然后求出问题一的决策树模型第二层的时间距离收益的拐点,找到即使比排队时早接客但是由于空载原因使收益仍然低于排队的时间或距离区间;再通过这个区间进行长途短途分类;然后结合实际情况得出优先方案。

    假设打车乘客的目的地为短途的权重为w,长途为1-w,则司机接到短途乘客的概率为w

    模型的推广

    本文的优化模型除了适用于机场的出租车问题,还适用于客运站拉客等一系列接客问题。

    模型的改进

    本文主要通过提供出租车停靠方案来提高乘客的乘车效率,但影响乘车效率的因素还有很多,比如天气、时间等,还可以将更多因素考虑进去对模型进行改进。

    模型的优点

    问题一、二的模型能够将一系列大数据进行处理,从而得到可靠结果;问题三的模型将抽象问题具象化,使模型更易于理解。

    模型的缺点

    本文的模型对数据的依赖性很强,必须要保证数据本身的准确性。问题三的多点纵列式排队模型不适用于道路短的问题。

    6.模型的推广与改进

    6.1模型的推广

    本文的优化模型除了适用于机场的出租车问题,还适用于客运站拉客等一系列接客问题。

    6.2模型的改进

    本文主要通过提供出租车停靠方案来提高乘客的乘车效率,但影响乘车效率的因素还有很多,比如天气、时间等,还可以将更多因素考虑进去对模型进行改进。

    7.模型的优缺点

    7.1优点

    问题一、二的模型能够将一系列大数据进行处理,从而得到可靠结果;问题三的模型将抽象问题具象化,使模型更易于理解。

    7.2缺点

    1.本文的模型对数据的依赖性很强,必须要保证数据本身的准确性。问题三的多点纵列式排队模型不适用于道路短的问题。

    2.问题三的多点纵列式排队方式对区域的纵向距离要求较高,一般适用于机场等枢纽的纵向距离较大的的交通枢纽。

    参考文献

    [1]魏中华,王琳,邱实.基于排队论的枢纽内出租车上客区服务台优化[J].公路交通科技(应用技术版),2017,13(10):298-300.

    [2]黄岩,王光裕.虹桥机场T2航站楼出租车上客系统组织管理优化探讨[J].城市道桥与防洪,2014(12):7-9+35-36

    [3]林思睿. 机场出租车运力需求预测技术研究[D].电子科技大学,2018

    [4] 宗天禹,吴永晗,文磊,韩宇龙.基于排队论模型的RGV动态调度研究[J].科技资讯,2019,17(19):212+214.

    附录

    附录一\1.问题一
    在这里插入图片描述
    附录一\2.问题二
    在这里插入图片描述
    附录一\3.问题三
    在这里插入图片描述
    附录二 Python代码

    1. No1_solve_flight_time.py 统计exl中某时间段航班数量
    # !/usr/bin/env python
    # -*- coding:utf-8 -*-
    # author: haotian time:2019/9/14
    import numpy as np
    
    f = open("./data/CD_Flight190914A.csv", "rb")
    excel = open("./data/time_flight.csv", "w+")
    # position_exl = open("./data/position_exl.csv", "w+")
    schedule = np.loadtxt(f, dtype=str, delimiter=",", skiprows=1, usecols=(4,))  # 分隔符 空格
    Array = np.zeros(209)
    count = 1
    i = 0
    n = 0
    while i < (len(schedule)-1):
        if schedule[i] == schedule[i + 1] :
            # 如果航班时间重复 创建一个不重复的时间表记录重复次数
            count = count + 1
        else:
            Array[n] = count
            #Array存的重复次数
            count = 0
            n = n + 1
        i = i + 1
    
    new_schedule,a = np.unique(schedule,return_index=True)
    #去掉相同时间的数据
    
    # for i in range(len(position)):
    #     position_exl.write(str(position[i])+',\n')
    # position_exl.close()
    
    # position_exl = open(("./data/position_exl.csv", "w+"))
    # position = np.loadtxt(position_exl, dtype=float, delimiter=",", skiprows=0, usecols=(0,))
    # new_schedule = [len(position)*'']
    # n = 0
    # numbers = [ int(x) for x in position ]
    # for i in range(numbers):
    #     new_schedule[n] = schedule[i]
    #     n = n + 1
    excel.write("Schedule,PlaneNum"+'\n')
    for i in range(len(new_schedule)-1):
        excel.write(str(new_schedule[i])+","+str(Array[i])+",\n")
    
    excel.close()
    '''
    此时的数据time_flight.csv由于排序的原因导致时间的序列不一致,
    最终数据用excel降序排列并保存到schedule_PlaneNum.csv中
    '''
    
    1. No2_solve_t3.py 解决t3的问题
    #!/usr/bin/env python
    # -*- coding:utf-8 -*-
    # author: haotian time:2019/9/15
    import os  # 创建文件夹需要用
    import numpy as np
    f = open("./data/distribute_2016.08.08_510100_.csv", "rb")
    schedule = np.loadtxt(f, dtype=str, delimiter=",", skiprows=1)  # 分隔符 空格
    
    def exl_download(n, address):
        os.makedirs('./' + str(address) + '/', exist_ok=True)
        for a in range(n):
            print('No' + str(a) + 'exl is downloading')
            with open('./' + str(address) + '/' + str(a) + '.csv', 'w') as f1:
                for i in range(len(schedule)-1):
                    if(schedule[i][1]==str(a)):
                        for j in range(5):
                            print('Writing......')
                            schedule[i][j].encode("utf-8")
                            f1.write(schedule[i][j]+',')
                        f1.write('\n')
            f1.close()
            print('No' + str(a) + 'exl is downloaded')
    exl_download(24, 'distribute')
    
    1. No3_get_exl.py python爬虫获取url上的航班
    #!/usr/bin/env python
    # -*- coding:utf-8 -*-
    # author: haotian time:2019/9/15
    import pandas as pd
    def getTable(base_url,start=-1,end=1):
        for idx in range(start,end+1):
            for page in range(1,51):
                now_url=base_url %(idx,page)
                print(now_url)
                tb=pd.read_html(now_url)[0]
                tb.to_csv(r'flight_info.csv',mode='a',encoding='utf_8_sig',header=1,index=0)
                print(str(idx)+'页抓取完成')
    
    getTable('http://www.cdairport.com/flightInfor.aspx?t=4&attribute=A&time=%d&page=%d')
    
    
    1. No4_judge_model.py 验证模型
    # !/usr/bin/env python
    # -*- coding:utf-8 -*-
    # author: haotian time:2019/9/15
    
    import numpy as np
    
    f = open("./data/schedule_PlaneNum.csv", "rb")
    result = open("./data/judge_result.csv", "w")
    timedata = np.loadtxt(f, dtype=int, delimiter=",", skiprows=1, usecols=[12, 13])  # 分隔符 空格,
    
    def judger():
        for i in range(len(timedata)):
            t1 = timedata[i][0]
            t3 = timedata[i][1]
            if t1 <= t3:
                print(str(i) + ',t1 <= t3 ###### the result is 1')
                # 排队的先到,那么肯定要接
                result.write(str(i) + ',1,\n')
            if t1 > t3:
                # 放空的先到
                t4 = t1 - t3
                # t/min = 平均每分钟一公里
                Wt3 = -0.6*(t3/60)  # 油费
                Wt4 =(1.9-0.6) * (t4/60)
                Wt = Wt4 + Wt3
                if Wt >= 0:
                    print(str(i) + ",t1 > t3,Wt >= 0 ###### the result is 1")
                    result.write(str(i) + ',1,\n')
                else :
                    print(str(i) + ",t1 > t3,Wt < 0 ###### the result is 0")
                    result.write(str(i) + ',0,\n')
    judger()
    result.close()
    

    判断结果如下:(也就是问题二的决策图)

    0 1 1 0 2 0 3 1 4 1 5 0 6 0 7 1 8 1 9 0 10 1 11 0 12 0 13 0 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 0 23 0 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 0 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 0 61 1 62 0 63 0 64 1 65 0 66 1 67 1 68 1 69 1 70 1 71 1 72 0 73 1 74 0 75 1 76 1 77 1 78 1 79 1 80 1 81 1 82 1 83 1 84 1 85 0 86 1 87 1 88 1 89 1 90 1 91 0 92 1 93 1 94 0 95 1 96 1 97 0 98 1 99 1 100 1 101 1 102 1 103 1 104 1 105 0 106 1 107 1 108 1 109 1 110 1 111 0 112 1 113 1 114 1 115 1 116 1 117 1 118 1 119 1 120 0 121 1 122 1 123 0 124 1 125 1 126 1 127 1 128 1 129 0 130 1 131 1 132 1 133 0 134 1 135 0 136 1 137 1 138 1 139 1 140 1 141 0 142 1 143 1 144 1 145 1 146 1 147 1 148 0 149 1 150 1 151 1 152 1 153 1 154 1 155 1 156 1 157 1 158 1 159 1 160 1 161 1 162 1 163 1 164 1 165 1 166 1 167 1 168 1 169 1 170 0 171 1 172 1 173 1 174 1 175 1 176 1 177 0 178 1 179 0 180 1 181 1 182 1 183 1 184 1 185 1 186 1 187 1 188 1 189 1 190 1 191 0 192 1 193 1 194 0 195 1 196 1 197 0 198 1 199 1 200 1 201 1 202 1 203 0 204 1 205 1 206 1 207 0 208 0
    

    百度云代码数据资源下载

    下载链接
    在这里插入图片描述

    展开全文
  • 多目标优化问题的算法及其求解

    万次阅读 多人点赞 2018-09-06 17:32:58
    多目标优化问题的算法及其求解 一、多目标优化问题   多目标优化是在现实各个领域中都普遍存在的问题,每个目标不可能都同时达到最优,必须各有权重。但是,究竟要怎样分配这样的权重,这已经成为人们...

    多目标优化问题的算法及其求解

    一、多目标优化问题

      多目标优化是在现实各个领域中都普遍存在的问题,每个目标不可能都同时达到最优,必须各有权重。但是,究竟要怎样分配这样的权重,这已经成为人们研究的热点问题。同时,根据生物进化论发展起来的遗传算法,也得到了人们的关注。将这两者结合起来,能够利用遗传算法的全局搜索能力,避免传统的多目标优化方法在寻优过程中陷入局部最优解,可以使解个体保持多样性。所以,基于遗传算法的多目标寻优策略已经被应用于各个领域中。

    二、多目标优化的数学描述

      一般来讲,多目标优化问题是由多个目标函数与有关的一些等式以及不等式约束组成,从数学角度可以做如下描述:minf1(x1,x2,...,xn)min\qquad f_1(x_1,x_2,...,x_n)...............\qquad...\quad...\quad... minfr(x1,x2,...,xn)min\qquad f_r(x_1,x_2,...,x_n) maxfr+1(x1,x2,...,xn)\quad max\qquad f_{r+1}(x_1,x_2,...,x_n) ...............\qquad...\quad...\quad... maxfm(x1,x2,...,xn)\quad max\qquad f_m(x_1,x_2,...,x_n) s.t.gi(x)0,i=1,2,...,ps.t.\qquad g_i(x)\ge0,i=1,2,...,p hj(x)0,j=1,2,...,q\quad \quad \qquad h_j(x)\ge0,j=1,2,...,q (1)
      式中,函数fi(x),{i=1,2,3,...,m}f_i(x),\{i={1,2,3,...,m}\}称为目标函数;gi(x)g_i(x)hi(x)h_i(x)称为约束函数;x={x1,x2,...,xn}Tx=\{x_1,x_2,...,x_n\}^Tnn维的设计变量。X={xxRn,gi(x)0,hj(x)=0,i=1,2,...,p,j=1,2,...,q}X=\{x|x\in R^n,g_i(x)\ge0,h_j(x)=0,i=1,2,...,p,j=1,2,...,q\}称为上述公式的可行域
      在这个多目标优化问题中有m(m2)m(m\ge2)个目标函数(rr个极小化目标函数,(mr)(m-r)个极大化目标函数)和(p+q),p,q0(p+q),p,q\ge0个约束函数(其中有pp个不等式约束和qq个等式约束)。
      如果上述多目标优化问题公式(1)的目标函数全部是极小化目标函数,约束函数全都是不等式约束,则可以得到一个标准多目标优化模型minF(X)=[f1(x),f2(x),...,fm(x)]Tmin\qquad F(X)=[f_1(x),f_2(x),...,f_m(x)]^T s.t.gi(x)0,i=1,2,...,ps.t.\qquad g_i(x)\le0,i=1,2,...,p(2)
      设计变量x={x1,x2,...,xn}Tx=\{x_1,x_2,...,x_n\}^T是一组确定的向量,对应nn维欧氏设计变量空间RnR^n上的一点,而相应的目标函数f(x)f(x)则对应一个mm维的欧氏目标函数RmR^m空间的一点。也就是说,目标函数f(x)f(x)对应的是由n维设计变量空间到m维目标函数空间的一个映射:f:RnRmf:\qquad R^n\to R^m
      由此可知,设计变量、目标函数以及约束函数是构成多目标优化问题的三要素。
      设计变量x1,x2,...,xnx_1,x_2,...,x_n是在实际工程设计中可以人为指定控制的,并且能对工程系统的属性、性能产生影响的一组向量,不同取值的设计变量便意味着对应不同的工程系统设计方案,一组设计变量通常可以用向量x={x1,x2,...,xn}Tx=\{x_1,x_2,...,x_n\}^T表示,并把它称之为优化问题的一个
      目标函数可以看作是评价设计系统性能指标的数学表达式,在实际工程设计中,设计者(决策者)希望能同时使这些性能指标达到最优化。所有的目标函数f1(x),f2(x),...,fm(x)f_1(x),f_2(x),...,f_m(x)构成了多目标优化问题(2)的目标函数向量F(X)F(X)
      约束条件给出了设计变量需要满足的限制条件,用含有等式和不等式的约束函数来表示。满足所有约束函数(约束条件)的一组设计变量可以称之为一个***可行解***,优化问题中所有的可行解构成了整个优化问题的可行域。

    三、多目标优化的目标占优和Pareto占优

      在多目标优化算法的搜索中,普遍使用了占优(dominate)的概念。在这里将给出占优的概念以及相关术语的定义。

    定义1:帕累托占优(Pareto Dominate)和帕累托最优解(Pareto Optimal)

      考察两个决策向量a,bXa,b\in Xaa帕累托占优(Pareto Dominate)bb,记为a&gt;ba&gt;b,当且仅当:{i{1,2,...,n}fi(a)fi(b)}{j{1,2,...,n}fj(a)&lt;fj(b)}\{\forall i\in \{1,2,...,n \}f_i(a)\le f_i(b)\} \land\{\exists j\in \{1,2,...,n \}f_j(a)&lt;f_j(b)\}
      如果在整个参数空间内不存在任何决策向量帕累托占优某个决策向量,则称该决策向量既是帕累托最优解。所有帕累托最优解组成了帕累托最优解集合(Pareto Optimal Set)。

    定义2:绝对最优解、非劣解、帕累托前沿(Pareto Front)

       设S为多目标优化的可行域,f(x)f(x)为多目标优化的向量目标函数。
       若f(X)f(X)XSf(X^*)\le f(X)\qquad \forall X\in S,则ff^*称是多目标优化的***绝对最优解***。
      若f(X)f(X)XSf(X)\le f(X^-)\qquad \forall X\in S,则称XX^-是多目标优化问题的***非劣解***,即***Pareto最优解***。非劣解也成为有效解(Efficient Solution)、非支配解(Non-dominated Solution)、Pareto最优解(Pareto Optimal Solution)或Pareto解。
      多目标优化问题的非劣解一般不止一个,由所有非劣解构成的集合称为***非劣解集(Non-inferior Set)***。所有非劣解对应的目标函数构成了多目标优化问题的***非劣最优目标域***,也成为***Pareto前缘(Pareto Front)***,再不引起混淆的情况下也可以称为非劣解集。

    四、多目标优化问题的解

      在单目标优化问题中,通常最优解只有一个,而且能用比较简单和常用的数学方法求出其最优解。然而在多目标优化问题中,各个目标之间相互制约,可能使得一个目标性能的改善往往是以损失其它目标性能为代价,不可能存在一个使所有目标性能都达到最优的解,所以对于多目标优化问题,其解通常是一个非劣解的集合——Pareto解集。
      在存在多个Pareto最优解的情况下,如果没有关于问题的更多的信息,那么很难选择哪个解更可取,因此所有的Pareto最优解都可以被认为是同等重要的。由此可知,对于多目标优化问题,最重要的任务是找到尽可能多的关于该优化问题的Pareto最优解。因而,在多目标优化中主要完成以下两个任务:

    1)找到一组尽可能接近Pareto最优域的解。
    2)找到一组尽可能不同的解。

      第一个任务是在任何优化工作中都必须的做到的,收敛不到接近真正Pareto最优解集的解是不可取的,只有当一组解收敛到接近真正Pareto最优解,才能确保该组解近似最优的这一特性。
      除了要求优化问题的解要收敛到近似Pareto最优域,求得的解也必须均匀稀疏地分布在Pareto最优域上。一组在多个目标之间好的协议解是建立在一组多样解的基础之上。因为在多目标进化算法中,决策者一般需要处理两个空间——决策变量空间和目标空间,所以解(个体)之间的多样性可以分别在这两个空间定义。例如,若两个个体在决策变量空间中的欧拉距离大,那么就说这两个解在决策变量空间中互异;同理,若两个个体在目标空间中的欧拉距离大,则说它们在目标空间中互异。尽管对于大多数问题而言,在一个空间中的多样性通常意味着在另一个空间中的多样性,但是此结论并不是对所有的问题都是成立的。对于这样复杂的非线性优化问题,要找到在要求的空间中有好的多样性的一组解也是一项非常重要的任务。

    五、求解帕累托前沿解的方法

      目前求解帕累托前沿解的主要算法有基于数学的规划方法和基于遗传算法的两类方法。本文重点介绍目前使用较普遍的NSGA-II算法。
      多目标遗传算法是用来分析和解决多目标优化问题的一种进化算法,其核心就是协调各个目标函数之间的关系,找出使得各个目标函数都尽可能达到比较大的(或比较小的)函数值的最优解集。在众多多目标优化的遗传算法中,NSGA-II算法(带精英策略的非支配排序遗传算法(Elitist Non-Dominated Sorting Genetic Algorithm,NSGA-II),NSGA-II )是影响最大和应用范围最广的一种多目标遗传算法。在其出现以后,由于它简单有效以及比较明显的优越性,使得该算法已经成为多目标优化问题中的基本算法之一。该算法主要优点(改善内容)如下三点:

    1. 提出了快速非支配的排序算法,降低了计算非支配序的复杂度,使得优化算法的复杂度由原来的mN3mN^3降为mN2mN^2mm为目标函数的个数,NN为种群的大小)。
    2. 引入了精英策略,扩大了采样空间。将父代种群与其产生的子代种群组合在一起,共同通过竞争来产生下一代种群,这有利于是父代中的优良个体得以保持,保证那些优良的个体在进化过程中不被丢弃,从而提高优化结果的准确度。并且通过对种群所有个体分层存放,使得最佳个体不会丢失,能够迅速提高种群水平。
    3. 引入拥挤度和拥挤度比较算子,这不但克服了NSGA算法中需要人为指定共享参数ShareσShare_\sigma的缺陷,而且将拥挤度作为种群中个体之间的比较准则,使得准Pareto域中的种群个体能均匀扩展到整个Pareto域,从而保证了种群的多样性。
        NSGA-II算法流程图如下:
      这里写图片描述

    六、在供应链优化过程中的应用案例

      供应链系统优化问题的本质是:
    1)供应链可以理解为一个多实体集成的系统或网络,它同步一系列相互关联的实体业务流程;
    2)协同优化问题不是最大限度地提高单一实体的盈利能力,而是促进各种合作伙伴(包括供应商,制造商,零售商,分销商和第三方物流供应商)共同盈利能力;
    3)只有当所有实体都希望优化整个供应链的性能和盈利能力(协同优化),并且不将其个体偏好(个体优化)置于系统的优先级之外时,才能实现协同优化;
    4)供应链协同优化必须找到一种尽可能兼顾满足个体偏好,同时最大规模实现全局最优帕累托解的解决方案。
      假设如下供应链模型:
    这里写图片描述
    驱动数据集
    (i, j): Component-Supplier 组件 - 供应商
    (i, j, k): Component-Supplier-Plant 组件 - 供应商 - 工厂
    (k, l): Plant-Customer Zone 工厂 - 客户区
    数据集如下
    这里写图片描述
    约束函数设计如下
    这里写图片描述
    目标函数设计如下
    这里写图片描述
    模拟数据集如下
    这里写图片描述
    运行结果
    这里写图片描述
    这里写图片描述

    展开全文
  • 4.4二次优化问题 例子 二次锥规划 二次优化 当凸优化问题的目标函数是凸二次型并且约束函数为仿射函数时,问题为二次规划 二次约束二次规划 二次约束二次规划,即目标函数和不等式约束函数均为凸二次型。 ...

    4.4二次优化问题

    1. 例子
    2. 二次锥规划

    二次优化

    当凸优化问题的目标函数是凸二次型并且约束函数为仿射函数时,问题为二次规划

    minimize \, \, (1/2)x^TPx+q^Tx+r \\ subject \, \, to \, \, \begin{matrix} Gx\preceq h\\ Ax=b \end{matrix} \\ P \in S_+^n,G \in R^{m\times n},A \in R^{p\times n}

    二次约束二次规划

    minimize \, \, (1/2)x^TP_0x+q_0^Tx+r_0 \\ subject \, \, to \, \, \begin{matrix} (1/2)x^TP_ix+q_i^Tx+r_i\leq 0,i=1,2\cdots m,\\ Ax=b \end{matrix} \\ P_i \in S_+^n,i=0,1\cdots m,A \in R^{p\times n}

    二次约束二次规划,即目标函数和不等式约束函数均为凸二次型。

    这里记LP 为线性规划,QP为二次规划,QCQP为二次约束二次规划,可知LP \subseteq QP \subseteq QCQP

    当QCQP中的P_i=0,i=1,2\cdots m时,QCQP变为QP。

    当QP中的P_0=0时,QP变为LP。

    例子

    最小二乘

    minimize \,\begin{Vmatrix} Ax-b \end{Vmatrix}_2^2

    无约束的情况下,最小二乘问题是一个二次规划。

    解析解:是A 的伪逆。

    增加线性约束:l\leq x\leq u,也是一个二次规划问题。

    如果约束为:x_1\leq x_2\leq \cdots \leq x_n,对约束进行整理,整理成:x_{i+1}-x_i\geq 0,i=1,2\cdots n-1,也是线性约束,也是二次规划问题。

    关于随机费用的线性规划

    考虑线性规划:

    minimize \, \, \bar{c}^Tx+\gamma x^T\Sigma x=E(c^Tx+\gamma \, \mathbf{var}(c^Tx))\\ subject \, \, to \, \, \begin{matrix} Gx\preceq h\\ Ax=b \end{matrix} \\ P \in S_+^n,G \in R^{m\times n},A \in R^{p\times n}

    其中,c是随机向量,\bar{c}是c的均值,\Sigma是协方差,且\mathbf{var}(c^Tx)=E(c^Tx-E(c^Tx))^2=E(c^Tx-\bar{c}^Tx)^2=E(x^T(c^T-\bar{c}^T)^2x)

    根据协方差公式:cov(X,Y)=E((X-E(X))(Y-E(Y)))\Rightarrow cov(c,c)=E((c-\bar{c})(c-\bar{c})^T)

    \Rightarrow\mathbf{ var}(c^Tx)=x^T\Sigma x

    故问题:

    minimize \, \, \bar{c}^Tx+\gamma x^T\Sigma x=E(c^Tx+\gamma \, (x^T\Sigma x))\\ subject \, \, to \, \, \begin{matrix} Gx\preceq h\\ Ax=b \end{matrix} \\ P \in S_+^n,G \in R^{m\times n},A \in R^{p\times n}

    \gamma\geq 0,称为风险回避参,它越大,表示越在意费用方差,即越希望费用方差充分小。

    二阶锥规划

    二阶锥规划(SOCP):

    minimize \, \, f^Tx \\ subject \, \, to \, \, \begin{matrix} \begin{Vmatrix} A_ix+b_i \end{Vmatrix}_2\leq c_i^Tx+d_i\\ Fx=g \end{matrix} \\ x \in R^n,A_i \in R^{n_i\times n},F \in R^{p\times n}

    \begin{Vmatrix} A_ix+b_i \end{Vmatrix}_2\leq c_i^Tx+d_i这种形式的约束为二阶锥约束。因为(A_ix+b_i, c_i^Tx+d_i)\in二阶锥R^{(n_i+1)}中。

    c_i为0时,SOCP退化为QCQP。当n_i=0时,SOCP退化为LP问题。

    鲁棒线性规划

    minimize \, \, c^Tx\\ subject \, \, to \, \, a_i^Tx \leq b_i,i=1,2\cdots m

    其中参数a_i,b_i,c含有一些不确定性或变化。

    针对这种问题有两种解法(1)确定性模型(2)随机模型。

    简化起见,假设只有a_i有不确定性,其他都是确定的。

    (1)确定性模型

    已知a_i在给定的椭球中:a_i \in \varepsilon _i=\left \{ \bar{a_i}+P_iu|\begin{Vmatrix} u \end{Vmatrix}_2\leq 1 \right \},所以问题变成:

    minimize \, \, c^Tx\\ subject \, \, to \, \, a_i^Tx \leq b_i,\forall \, a_i \in \varepsilon _i,i=1,2\cdots m

    约束又可以表示成:sup\left \{ a_i^Tx|a_i \in \varepsilon _i \right \}\leq b_i

    sup\left \{ a_i^Tx|a_i \in \varepsilon _i \right \}=\bar{a_i}x+sup\left \{ u^TP_i^Tx|\begin{Vmatrix} u \end{Vmatrix}_2\leq 1 \right \}=\bar{a_i}x+\begin{Vmatrix} P_i^Tx \end{Vmatrix}_2

    所以上述约束变为\bar{a_i}x+\begin{Vmatrix} P_i^Tx \end{Vmatrix}_2\leq b_i

    问题变成:

    minimize \, \, c^Tx\\ subject \, \, to \, \, \bar{a_i}x+\begin{Vmatrix} P_i^Tx \end{Vmatrix}_2\leq b_i,i=1,2\cdots m

    (2)随机模型

    设参数a_i是独立搞死随机变量,均值为\bar{a_i},协方差为\Sigma _i,要求每一个约束a_i^Tx \leq b_i成立的概率超过\eta,且\eta \geq 0.5,即prob(a_i^Tx \leq b_i)\geq \eta

    u=a_i^Tx,均值\bar{a_i}^Tx,方差x^T\Phi _ix,因此

    prob(a_i^Tx \leq b_i)=prob(\frac{a_i^Tx-\bar{a_i}^Tx}{\begin{Vmatrix} \Sigma _i^{1/2}x \end{Vmatrix}_2}\leq \frac{b_i-\bar{a_i}^Tx}{\begin{Vmatrix} \Sigma _i^{1/2}x \end{Vmatrix}_2})

    所以

    prob(a_i^Tx\leq b_i)=\Phi (\frac{b_i-\bar{a_i}^Tx}{\begin{Vmatrix} \Sigma _i^{1/2}x \end{Vmatrix}_2})\Phi(x)= (\frac{1}{\sqrt{2\pi }})\int_{-\infty }^{x}e^{-t^2/2}dt

    所以:prob(a_i^Tx \leq b_i)\geq \eta可以写成:

    \frac{b_i-\bar{a_i}^Tx}{\begin{Vmatrix} \Sigma _i^{1/2}x \end{Vmatrix}_2}\geq \Phi ^{-1}(\eta)\Rightarrow \bar{a_i}^Tx+\begin{Vmatrix} \Sigma _i^{1/2}x \end{Vmatrix}_2\Phi ^{-1}(\eta)\leq b_i

    问题:

    minimize \, \, c^Tx\\ subject \, \, to \, \, prob(a_i^Tx \leq b_i)\geq \eta,i=1,2\cdots m

    变为:

    minimize \, \, c^Tx\\ subject \, \, to \, \, \bar{a_i}^Tx+\begin{Vmatrix} \Sigma _i^{1/2}x \end{Vmatrix}_2\Phi ^{-1}(\eta)\leq b_i,i=1,2\cdots m

     

     

     

    展开全文
  • 优化问题

    千次阅读 2017-10-15 17:14:58
    数学中最优化问题

    先转载几个链接,关于理论的介绍。


    作者:王业磊
    链接:https://www.zhihu.com/question/20343349/answer/17347657
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    数学中最优化问题的一般表述是求取x^{*}\in \chi,使f(x^{*} )=min\{f(x):x\in \chi \},其中x是n维向量,\chix的可行域,f\chi上的实值函数。
    凸优化问题是指\chi闭合的凸集f\chi上的凸函数的最优化问题,这两个条件任一不满足则该问题即为非凸的最优化问题。
    其中,\chi凸集是指对集合中的任意两点x_{1},x_{2}\in \chi,有tx_{1}+(1-t)x_{2}\in \chi,t\in[0,1],即任意两点的连线段都在集合内,直观上就是集合不会像下图那样有“凹下去”的部分。至于闭合的凸集,则涉及到闭集的定义,而闭集的定义又基于开集,比较抽象,不赘述,这里可以简单地认为闭合的凸集是指包含有所有边界点的凸集

    f凸函数是指对于定义域\chi中任意两点x_{1},x_{2}\in \chi,有f(t x_{1}+(1-t) x_{2}) \ge t f(x_{1})+(1-t)f( x_{2}),t\in[0,1]这里应该是小于等于号,作者注),直观上就是f向下凸出,如下图示意
    &amp;amp;amp;lt;img src=&quot;https://pic1.zhimg.com/50/3a05acd2b63840bd7f79333c647411f0_hd.jpg&quot; data-rawwidth=&quot;300&quot; data-rawheight=&quot;156&quot; class=&quot;content_image&quot; width=&quot;300&quot;&amp;amp;amp;gt;
    实际建模中判断一个最优化问题是不是凸优化问题一般看以下几点:
    • 目标函数f如果不是凸函数,则不是凸优化问题
    • 决策变量x中包含离散变量(0-1变量或整数变量),则不是凸优化问题
    • 约束条件写成g(x)\le0时,g如果不是凸函数,则不是凸优化问题
    之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解,这个特性使凸优化问题在一定意义上更易于解决,而一般的非凸最优化问题相比之下更难解决。
    资料来自维基,稍有删减改动。




    以上重要部分都已经标出,关键就是1)定义域是闭合的凸集  2)函数满足凸函数定义。
    其实在自己理解问题和听课时,直观理解更好。
    比如吴恩达教授提到的1/2*(y'-y)^2这个函数,课件中提到他是一个非凸函数。那么画下图来是底下这样的。
    可以看到这是个马鞍形的,并没有满足(下)凸函数条件,有可能出现两点连线的中值小于函数在该中间点的取值的情况。或者二维看不出来的话就转为一维度来看,切一条线初来,明显是上凸的,这种函数存在的最大问题,知乎回答也提及了,就是局部最优解有可能不是全局最优解。根据这种函数定义出来的损失函数(或者叫优化函数)会容易陷入局部最优解的问题,所以一般不采用这种函数。
    底下这个函数就很棒了。


    PS,记住底下这个公式,excel画曲面图必备。
    =$A2^2/2+B$1^2/2-2*$A2*B$1


    展开全文
  • 凸优化第四章凸优化问题 4.2凸优化

    千次阅读 2019-01-21 21:15:50
    则此优化问题是凸优化问题。 也可以写成 重要性质:凸优化问题的可行集也是凸集。 证明:可行集是满足不等式约束和等式约束的点的集合,首先不等式约束函数是凸函数,满足不等式约束的x,相当于是的0-下水平集...
  • 优化问题综述

    万次阅读 多人点赞 2017-03-19 18:58:47
    优化问题一般可分为两大类:无约束优化问题和约束优化问题,约束优化问题又可分为含等式约束优化问题和含不等式约束优化问题。 无约束优化问题 含等式约束的优化问题 含不等式约束的优化问题 2 求解策略 针对...
  • 要从优化问题开始,首先确定目标非常重要。目标是绩效的量化衡量。例如:最大化利润,最小化时间,最小化成本,最大化销售。 优化问题可分为两组 线性规划(LP):它也被称为线性优化,在这个问题中...
  • Lingo解决优化问题

    千次阅读 多人点赞 2018-08-30 17:15:02
    Lingo解决优化问题 前言 前面,我们已经对Lingo有了一定的了解,但是要想真正的熟悉Lingo在解决优化问题中的强大之处,还需要不断加强相关训练,本文主要是使用Lingo来解决优化问题,该文的主要目的有以下三点:...
  • 优化问题之子模问题

    千次阅读 2018-11-12 16:03:29
    优化问题之子模问题 什么是子模函数? 维基百科 核心:这涉及到一个边际效应递减,边际效应递减指的是当集合中元素较少或没有时加入一个元素会带来巨大的效益,当集合中已经有许多元素时,加入一个新的元素会带来的...
  • 把有约束最优化问题转化为无约束最优化问题之罚函数法 待补充
  • 最小二乘优化问题

    千次阅读 2019-04-10 22:44:25
    这里给大家介绍一下最小二乘优化问题,然后举例里程计校准odometry calibration加深印象。 问题描述 假设现有系统由nnn个观测函数描述 {fi(x)}i=1..n\lbrace f_{i}(x) \rbrace_{i=1..n}{fi​(x)}i=1..n​,其中xxx...
  • 仓内拣货路径优化问题

    千次阅读 多人点赞 2020-06-07 02:08:35
    详细分析了货格与货格间、货格与复核台间的距离计算;利用遗传算法解决了仓内拣货优化问题
  • 多目标优化问题概述

    万次阅读 2017-08-29 20:34:16
    关键词:条件约束,折中最优解(解并非唯一是与单目标优化问题的本质区别) 文字描述: D个决策变量参数; N个目标函数; m+n个约束条件。 数学描述:X(小写)为D维决策向量;y为目标向量;N为优化目标总数;...
  • 其中,显然线性规划问题是凸优化问题。 因为不等式约束函数和等式约束函数都是仿射函数,所以可行集是一个多面体。 所以也就是相等于在多面体中找一个使得最小,即找一个最大的。 例子 食谱问题 表示n种食物...
  • [最优化]不等式约束的优化问题求解

    万次阅读 2018-06-08 16:31:23
    不等式约束的优化问题求解 与前文讨论的只含等式约束的优化问题求解类似,含不等式约束的优化问题同样可以用拉格朗日乘子法进行求解 对于一般形式的优化问题: minimizef(x)subject&nbsp;toh(x)=0g(x)≤0...
  • MATLAB 求解最优化问题

    万次阅读 多人点赞 2017-08-17 20:49:03
    MATLAB 求解最优化问题 MATLAB 优化工具箱解线性规划 模型1 minz=cXs.t.AX≤b \text{min} \quad z=cX \\ s.t.\quad AX\leq b 命令:x=linprog(c,A,b)x=\text{linprog}(c,A,b) 模型2 minz=cXs.t.AX≤...
  • 优化问题简介

    万次阅读 2016-01-27 20:39:33
    题目:最优化问题简介  一年多学习以来,无论是前面学习压缩感知,还是这半年学习机器学习,一直离不开最优化,比如压缩感知的基追踪类重构算法,核心问题就是一个优化问题,而机器学习中的很多算法也需要最优化的...
  • 凸优化第四章凸优化问题 作业题

    千次阅读 2019-01-28 15:16:20
    标准形式凸优化问题 If an optimization problem is feasible, its optimal value satisfies 优化问题是可行的,表示问题至少有一个可行点,而可行解可以是,只是此时我们说问题无下界。 If the optimal ...
  • 优化问题的求解分类

    千次阅读 2019-02-09 10:10:19
    通常需要求解的最优化问题有如下几类: 无约束优化问题,可以写为: 有等式约束的优化问题,可以写为:   有不等式约束的优化问题,可以写为:额 对于第1类的优化问题,使用的方法为费马大定理(Fermat) ...
  • 更多专业的人工智能相关文章,微信搜索 : ...喜欢最优化问题的读者不妨先关注一下这个公众号,因为后面我们会用一个系列来讨论最优化问题。 今天我们简单的讨论一下,约束最优化问题中常常预见的几个名词关系,...
  • 优化问题及其分类

    万次阅读 多人点赞 2016-02-24 22:24:52
    归纳而言,最优化问题分为函数优化问题和组合优化问题两大类,其中函数优化的对象是一定区间的连续变量,而组合优化的对象则是解空间中的离散状态。 一、函数优化问题函数优化问题通常可描述为:令S S为R n R^n上...
  • 深度学习中的优化问题

    千次阅读 2018-04-28 11:07:37
    一、优化问题的挑战 绝大多数深度学习中的目标函数都很复杂。因此,很多优化问题并不存在显示解(解析解),而需要使用基于数值方法的优化算法找到近似解。这类优化算法一般通过不断迭代更新解的数值来找到近似...
  • 优化问题:基础定义

    千次阅读 2018-12-02 22:09:01
    优化问题 “一旦将一个实际问题表述为凸优化问题,大体上意味着相应问题已经得到彻底解决,这是非凸的优化问题所不具有的性质。”——《&amp;amp;lt;凸优化&amp;amp;gt;译者序》 1 什么是凸优化 什么是...
  • 优化问题,凸二次规划问题QP,凸函数

    万次阅读 多人点赞 2018-07-27 17:25:41
    约束优化问题 凸函数 凸优化问题 凸二次规划问题 约束优化问题 min&amp;nbsp;w&amp;nbsp;&amp;nbsp;f(w)min&amp;nbsp;w&amp;nbsp;&amp;nbsp;f(w) min_{ \ w} \ \ f(w) s.t.&...
  • 优化问题-线性优化(LP)

    万次阅读 2017-07-01 19:10:11
    这里最优化问题的讨论,主要指在给定某个确认的目标函数以及该函数的自变量的一些约束条件,求函数的最大或最小值的问题,通用的数学表达式: 目标函数 : f(x) f(x) 约束条件 : s.t.g(x)≤0,h(x)=0 s.t. g(x) \leq...
  • matlab改进的遗传算法求解路径优化问题

    千次阅读 多人点赞 2020-03-18 22:41:53
    遗传算法具有很强的全局搜索能力和较强的自适应性,适合解决连续变量函数优化问题和离散变量的优化组合问题。 二、问题描述 旅行商问题(TSP)是一个典型的优化组合问题,它需要求出旅行商从某一...
  • 优化问题综述(四)有约束最优化算法

    千次阅读 2018-09-04 14:27:42
    优化问题的三种情况 无约束条件:梯度下降法等(前面的文章已经有详细的描述) 等式约束条件:解决方法是消元法或者拉格朗日法。 不等式约束条件:一般用KKT(Karush Kuhn Tucker)条件对偶求解 等式约束条件...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 145,173
精华内容 58,069
关键字:

优化问题