LinearFractionalOptimization

LinearFractionalOptimization[f,cons,vars]

求能最小化受线性约束条件 cons 限制的线性分式目标函数 f 的变量 vars 的值.

LinearFractionalOptimization[{α,β,γ,δ},{a,b}]

求能最小化受线性不等式约束条件 限制的线性分式函数 的向量 .

LinearFractionalOptimization[{α,β,γ,δ},{a,b},{aeq,beq}]

包括线性等式约束条件 .

LinearFractionalOptimization[{α,β,γ,δ},,{dom1,dom2,}]

置于域 domi 中,其中 domiIntegersReals.

LinearFractionalOptimization[,"prop"]

指定应返回解的 "prop" 属性.

更多信息和选项

  • 线性分式优化也称为线性分式规划(LFP)和混合整数分式线性规划(MILFP).
  • 线性分式优化是一个凸优化问题,可用实数、整数或复数变量高效地进行全局求解.
  • 线性分式优化求可解决原始问题的 »
  • 最小化
    受限于约束条件
    其中
  • 混合整数线性分式优化发现 求解这个问题:
  • 最小化
    受限于约束条件
    其中
  • 当目标函数取实数值时,LinearFractionalOptimization 在内部将 x in TemplateBox[{}, Complexes]^n 转换为实变量 (其中 ),进行问题求解.
  • 变量规范 vars 应该是一个列表,其中的元素以下列形式之一给出变量:
  • v名称为 和推断维度的变量
    vReals实数标量变量
    vIntegers整数标量变量
    vComplexes复标量变量
    v仅限于几何区域 的向量变量
    vVectors[n,dom] 中的向量变量
    vMatrices[{m,n},dom] 中的矩阵变量
  • 可用以下形式指定约束条件 cons
  • LessEqual标量不等式
    GreaterEqual标量不等式
    VectorLessEqual向量不等式
    VectorGreaterEqual向量不等式
    Equal向量或标量等式
    Element凸域或区域元素
  • 对于 LinearFractionalOptimization[f,cons,vars],可在约束条件中包括形式为 parval 的参数方程,以定义在 fcons 中使用的参数,其中 par 不在 vars 中,val 是数值或数值数组.
  • 原始最小化问题有相关的最大化问题,即拉格朗日对偶问题. 对偶最大值始终小于或等于原始最小值,因此它给出了下限. 对偶最大值点提供了有关原问题的信息,包括最小值对约束条件变化的敏感性.
  • 下面给出了线性分式优化的拉格朗日对偶问题: »
  • 最大化
    受限于约束条件
    其中
  • 对于线性分式优化,强对偶性始终成立,这意味着如果原始最小化问题的解存在,那么对偶最大化问题的解也存在,并且对偶最大值等于原始最小值.
  • 可能的解的属性 "prop" 包括:
  • "PrimalMinimizer"一个最小化目标函数的变量值列表
    "PrimalMinimizerRules"最小化 的变量值 vars={v1,}
    "PrimalMinimizerVector"最小化 的向量
    "PrimalMinimumValue"最小值
    "DualMaximizer"最大化 的向量
    "DualMaximumValue"对偶最大值
    "DualityGap"对偶值和原始最优值之间的差(由于强对偶性,差应为 0)
    "Slack"
  • 约束松弛向量
  • "ConstraintSensitivity"
    对约束条件扰动的敏感性
    "LinearFractionalObjectiveCoefficients" 的系数
    "LinearInequalityConstraints"
    线性不等式约束矩阵和向量
    "LinearEqualityConstraints"
    线性等式约束矩阵和向量
    {"prop1","prop2",} 解的几个属性
  • 对偶最大值 有关,关系式为 .
  • 可给出以下选项:
  • MaxIterationsAutomatic使用的最大迭代次数
    Method Automatic使用的方法
    PerformanceGoal$PerformanceGoal优化的目标
    Tolerance Automatic内部比较采用的容差
    WorkingPrecision Automatic内部计算使用的精度
  • 选项 Method->method 可用来指定使用的方法. 可用的方法包括:
  • Automatic自动选择方法
    "Simplex"单纯形法
    "RevisedSimplex"修正单纯形法
    "InteriorPoint"内点法(仅适用于机器精度)
    "CLP"COIN 库线性规划(仅适用于机器精度)
    "MOSEK"商业 MOSEK 线性优化求解器
    "Gurobi"商业 Gurobi 线性优化求解器
    "Xpress"商业 Xpress 线性优化求解器
  • 当设置为 WorkingPrecision->Automatic 时,精度是从输入参数的精度自动获取的,除非指定的方法仅适用于机器精度,在这种情况下使用机器精度.
  • 如果先验已知所寻求的解的分母的正负,那么在 ab 中放入规定分母正负的约束条件将加快 LinearFractionalOptimization 算出解的速度.

范例

打开所有单元关闭所有单元

基本范例  (3)

最小化受约束条件 限制的

在函数 在可行区域的绘图上显示最小点:

最小化受约束条件 限制的

以矩阵-向量格式指定输入:

用矩阵-向量格式求解:

最小化 ,约束为

使用等效的矩阵向量表示:

范围  (33)

基本用法  (17)

最小化受约束条件 限制的

最小化受约束条件 限制的

最小化受约束条件 限制的

VectorLessEqual 同时表示几个 LessEqual 不等式约束条件:

v<= 以紧凑格式输入向量不等式:

用标量不等式表示的等价格式:

VectorGreaterEqual 同时表示几个 GreaterEqual 不等式约束条件:

v>= 以紧凑格式输入向量不等式:

用标量不等式表示的等价格式:

Equal 同时表示几个等式约束条件:

用几个标量等式表示的等价格式:

同标量和向量不等式的组合指定约束条件:

最小化受约束条件 限制的 . 使用向量变量

用标量变量表示的等价格式:

用向量变量和向量不等式指定问题:

Indexed 指定向量变量的分量,如

用常参数方程指定目标函数和约束条件的系数:

用常参数方程指定几个约束条件的系数:

最小化受约束条件 限制的

需要的情况下用 Vectors[n] 指定向量变量的维度:

NonNegativeReals () 指定非负约束条件:

用向量不等式表示的等价格式:

NonPositiveReals () 指定非正约束条件:

用向量不等式表示的等价格式:

通过指定标量、向量和矩阵最小化受约束条件 限制的

用矩阵-向量格式求解:

用变量和不等式表示的等价格式:

求向量 ,以最小化受约束条件 限制的函数

最小值是无界的,因为可行区域内存在奇点:

整数变量  (4)

Integers 指定整数域约束条件:

Vectors[n,Integers] 指定向量变量的整数域约束条件:

NonNegativeIntegers () 指定非负整数域约束条件:

用向量不等式表示的等价形式:

NonPositiveIntegers () 指定非正整数域约束条件:

用向量不等式表示的等价形式:

复变量  (2)

Complexes 指定复变量:

Vectors[2,Complexes] 指定向量变量的复数域:

原始模型属性  (3)

最小化受约束条件 限制的

获取向量形式的原始最小点:

获取最小值:

用符号输入求解优化问题:

提取优化问题的矩阵-向量输入:

用矩阵-向量输入获取符号输入的结果:

求与最小化问题相关的松弛向量:

获取最小点和约束矩阵:

不等式约束条件 的松弛向量为满足 的向量

等式约束条件 的松弛向量为满足 的向量

等式的松弛向量 通常为零向量:

对偶模型属性  (3)

最小化受约束条件 限制的

对偶问题为最大化受约束条件 限制的

由于强对偶性,原始最小值和对偶最大值相同:

所以对偶间隙为零. 一般情况下,在最优值点

用从原始问题中提取的约束矩阵构建对偶问题:

提取目标向量和约束矩阵:

对偶问题是最大化受约束条件 限制的 . 使用 Inactive[Times] 来避免在等式约束中进行线程化:

用解的属性直接获取对偶最大值:

用解的属性直接获取对偶最大值点:

敏感性属性  (4)

"ConstraintSensitivity" 求由约束松弛造成的最优值的变化:

第一个向量是不等式敏感性,第二个是等式敏感性:

考虑新的约束条件 ,其中 为松弛向量. 新的近似最优值为:

与直接求解约束松弛后的问题相比较:

每种敏感性都与不等式或等式约束条件相关:

提取约束条件:

不等式约束条件及相关的敏感性:

等式约束条件及相关的敏感性:

约束松弛引起的最优值变化与灵敏度值成正比:

计算最小值和约束条件敏感性:

如果敏感性为零,放宽约束条件不会改变最优值:

如果敏感性为负,放宽约束条件将会使最优值减小:

如果敏感性为正,放宽约束条件将会使最优值增大:

"ConstraintSensitivity" 与问题的对偶最大值点相关:

不等式敏感性 满足 ,其中 为对偶不等式的最大值点:

等式敏感性 满足 ,其中 为对偶等式的最大值点:

选项  (8)

Method  (4)

MachinePrecision 情况下的默认方法是 "CLP"

任意或无限 WorkingPrecision 情况下的默认方法是 "Simplex"

所有方法都适用于 MachinePrecision 的输入:

"Simplex""RevisedSimplex" 可被用于任意精度和无限精度的输入:

不同的方法有不同的优势,这通常取决于问题及怎样进行优化:

"Simplex""RevisedSimplex" 适用于规模小且密集的问题:

"InteriorPoint""CLP" 适用于规模大且稀疏的问题:

如果问题的最优解集不是唯一的,不同的方法可能会给出不同的结果:

"InteriorPoint" 可能返回最优解集中间位置处的解:

"Simplex" 总是返回最优解集边角处的解:

Tolerance  (2)

Tolerance 的设置越小给出的结果越精确:

计算容差被设为非常小的值时求得的最小值,将其作为参考:

计算将 Tolerance 设为不同值时求得的解:

可视化误差随容差变化的情况:

Tolerance 的设置越小给出的答案越精确,但通常情况下要花费更多的时间进行计算:

小的容差将花费更多时间进行计算:

更严格的容差给出更精确的答案:

WorkingPrecision  (2)

精确输入给出精确输出:

MachinePrecision 获取非精确结果:

LinearFractionalOptimization 可使用更高的工作精度计算结果:

如果精度小于输入参数的精度,系统会发出一条消息:

应用  (16)

基本模型转换  (6)

最大化受约束条件 限制的 . 对目标函数取负求解最大化问题:

对原始最小值取负获取相应的最大值:

最小化受约束条件 限制的 . 令 ,并用 转换为线性函数:

也可用 来转换问题:

最小化受约束条件 限制的 . 由于 ,令 ,目标函数被转换为

最小化受约束条件 限制的 . 因为 ),通过令 ,目标函数被转换为

最小化受约束条件 限制的 ,其中 为非递减函数,因而可代之以最小化 . 对于两个问题,原始最小点 将保持不变. 考虑最小化受约束条件 限制的

通过将函数 应用于原始最小值即可获得真正的最小值:

最小化受约束条件 限制的

由于 ,在 的情况下求解问题:

最优解是两个解中最小的那一个:

运输问题  (1)

通过最小化成本和最大化利润,选择运输五种商品每次运送的件数. 每种商品运送一件的成本和利润是:

每件商品的重量和可运送的最大件数为:

卡车的最低运营成本为 $2000,总运输成本是:

如果卡车空着,那么卡车的最低利润为 $1000,因而总利润是:

卡车最多可以携带 8000 磅的货品. 所以对卡车的约束条件为:

通过最小化成本与利润的比率找到最佳货物运输组合:

计划生产  (1)

找到四种产品的组合,以最大限度地降低成本和最大化利润. 每个产品制造一件的成本和利润是:

为了制造每个产品,公司需要组合五种资源,它们是:

最大可用资源为:

资源和产品的约束条件为:

公司运营的最低成本为 $100. 总制造成本为:

出售产品所获总利润为:

通过最小化成本与利润的比率找到可制造的最大件数:

资源分配  (1)

公司需要满足城市高峰时期的电力需求,同时也要最大化利润并最大限度地降低成本,求此种情况下公司必须从三个发电厂向四个城市发送的电量. 从每个工厂向各个城市输送 100 万千瓦时电力的成本是:

每个电厂通过向每个城市出售 100 万千瓦时电力产生的利润是:

表示从电厂 输送到城市 的电量. 输送电力的总成本是 ,用 Inactive[Times] 构建表达式:

电力公司获得的总利润为 ,用 Inactive[Times] 构建表达式:

各个城市高峰时期的电力需求分别为 4.5、2、3、3 千万千瓦时:

电厂可分别提供最少 3.5、5 和 4 千万千瓦时的电力:

电厂只能为城市输送电力,不能从城市获取电力:

通过最小化成本与利润的比率,可以求出每个电厂输送到每个城市的最佳电量:

电力供应明细为:

混合问题  (1)

求最大限度地降低成本并最大化利润的情况下,制造最多含有 60% 的铅和 35% 的锡的新合金所需的旧合金的组合. 该铸造厂现有四种含锡和铅的旧合金:

为旧合金 的重量. 新合金由旧合金组合而成:

每磅旧合金的成本是:

生产新合金的成本是:

铸造厂以 $200 的价格出售新合金. 铸造厂获得的总利润是:

铸造厂必须生产至少 15 磅的最多含有 60% 的铅和 35% 的锡的新合金:

铸造厂只有 12、15、16 和 10 磅的四种合金:

通过最小化成本与利润的比率,可以找到旧合金的最佳组合:

投资问题  (2)

对最多 $250,000 的资金进行分配,用来购买两只股票和债券,使投资回报最大化,同时降低购买股票/债券的成本. 令 表示投资在两只股票上的资金,令 表示投资在债券上的资金:

投资于公用事业股票的金额不得超过 $40,000,并有 9% 的股息:

投资于债券的金额必须至少为 $70,000,并有 5% 的利息:

投资于两只股票的总金额必须至少是投资总额的一半:

电子股每年支付 4% 的股息. 总投资回报为:

投资成本为:

通过最小化成本与利润的比率,可以找到最佳投资金额:

投资总额和从投资中获得的年度红利为:

寻找能够在最大程度地降低成本的同时获得最大利润的最佳投资组合. 与每项投资相关的净现值和成本为:

为决策变量,如果选择了投资 . 目标是在最大程度地降低成本的同时最大化利润:

最多可用 $14,000 来进行投资:

求解最大化问题,获取最佳投资组合:

集合覆盖问题  (3)

求医院急诊室必须待命的医生的最佳组合,以便急诊室可以完成一系列手术. 每位医生只能完成一定数量的手术:

保持每个医生待命的费用为(每小时):

为决策变量,如果医生 待命则 . 目标是最大程度地降低成本,同时使急诊室中医生的总数最大化:

至少需要一名医生完成手术

给出待命医生的组合:

给出一个包含六个区的城市必须建立的最佳消防站数量,以使每个区 15 分钟之内至少有一个消防站. 在各区之间行驶所需的时间为:

在每个城市建立消防站的成本为(以百万美元计):

为决策变量,如果在城区 建消防站则 . 目标是建最大数量的消防站,同时最小化成本:

每个区 15 分钟内必须至少有一个消防局:

给出将要建消防局的地区:

总成本为:

求公司需要建立的最佳配送仓库的数量,以便为六个零售商店配送货物. 该公司选择了五个可能的地点. 每个仓库为每个商店配送货物的成本为:

每个仓库的建设成本为(以百万美元计):

为决策变量,如果要建造仓库 . 令 表示仓库 提供给商店 的商品份额. 总费用为:

该公司希望通过出租未使用的空间,从每个仓库获利 100 万美元:

每个商店必须收到所有货物:

只有建成的仓库可以将货物供应给商店:

找出应该建造哪五个仓库:

给出将建造的五个仓库:

供应零售商店的仓库是:

旅行商问题  (1)

找到一条推销员应选的穿过 个城市的路径,只访问每个城市一次,最小化行走的距离,同时最大程度地节省差旅成本. 生成位置:

为城市 和城市 之间的距离. 令 为决策变量,如果 ,则路径从城市 到城市

从一个城市到另一个城市的旅行预算是 15 美元. 如果两个城市相距 50 英里以内,则推销员支付 5 美元,否则统一支付 10 美元. 总共能节省:

目标是最小化距离,同时最大程度地节省成本:

推销员只能从一个城市到达,只能去往一个城市:

推销员不能到达一个城市并去往同一个城市:

推销员必须一次访问所有城市:

决策变量是一个二元变量,虚拟变量为

求使距离最小化的路径:

提取路径:

走过的距离为:

总共节省了:

属性和关系  (5)

LinearFractionalOptimization 给出目标函数的全局最小值:

Minimize 也可给出线性分式优化问题的全局精确结果:

NMinimize 可用来通过全局方法获取非精确结果:

FindMinimum 可用来通过局部方法获取非精确结果:

LinearOptimizationLinearFractionalOptimization 的特例:

可能存在的问题  (6)

可能无法满足用严格的不等式指定的约束条件:

给出的解是

空集或不可行问题的最小值被定义为

最小点为 Indeterminate

无界集或无界问题的最小值是

最小点为 Indeterminate

混合整数问题的对偶相关解属性可能不可用:

只能以机器精度求解混合整数问题

需使用向量不等式指定含有复数的约束条件:

只使用 GreaterEqualLessEqual 是不可行的:

Wolfram Research (2019),LinearFractionalOptimization,Wolfram 语言函数,https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html (更新于 2020 年).

文本

Wolfram Research (2019),LinearFractionalOptimization,Wolfram 语言函数,https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html (更新于 2020 年).

CMS

Wolfram 语言. 2019. "LinearFractionalOptimization." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2020. https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html.

APA

Wolfram 语言. (2019). LinearFractionalOptimization. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html 年

BibTeX

@misc{reference.wolfram_2024_linearfractionaloptimization, author="Wolfram Research", title="{LinearFractionalOptimization}", year="2020", howpublished="\url{https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_linearfractionaloptimization, organization={Wolfram Research}, title={LinearFractionalOptimization}, year={2020}, url={https://reference.wolfram.com/language/ref/LinearFractionalOptimization.html}, note=[Accessed: 21-November-2024 ]}