({{, (RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization])[f,cons, vars] 
finds values of variables vars that minimize the linear fractional objective f subject to linear constraints cons.}, {, (RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization])[{α,β,γ,δ},{a,b}]
finds a vector x that minimizes the linear fractional function (α.x+β)/(γ.x+δ) subject to the linear inequality constraints a.x+b⪰0. }, {, (RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization])[{α,β,γ,δ},{a,b},{(Subscript[a, eq]),(Subscript[b, eq])}]
includes the linear equality constraints (Subscript[a, eq]).x+(Subscript[b, eq])==0.}, {, (RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization])[…,"prop"]
specifies what solution property "prop" should be returned.}})

OpenersNotesSection(Spacer1)Details and Options

Linear fractional optimization is also known as linear fractional programming (LFP).

Linear fractional optimization is a convex optimization problem that can be solved globally and efficiently.

Linear fractional optimization finds x that solves the primal problem: »

The constraints cons can be specified by:

With (RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization])[f,cons,vars], parameter equations of the form par==val, where par is not in vars and val is numerical or an array with numerical values, may be included in the constraints to define parameters used in f or cons.

The primal minimization problem has a related maximization problem that is the Lagrangian dual problem. The dual maximum value is always less than or equal to the primal minimum value, so it provides a lower bound. The dual maximizer provides information about the primal problem, including sensitivity of the minimum value to changes in the constraints.

The Lagrangian dual problem for linear fractional optimization is given by:  »

For linear fractional optimization, strong duality always holds, meaning that if there is a solution to the primal minimization problem, then there is a solution to the dual maximization problem, and the dual maximum value is equal to the primal minimum value.

The possible solution properties "prop" include:

The dual maximum value ζ is related to λ and ν through ζγ+aᵀ.λ+(Subscript[a, eq])ᵀ.ν == α.

The following options may be given:

The option (RefLink[Method, paclet:ref/Method])->method may be used to specify the method to use. Available methods include:

With (RefLink[WorkingPrecision, paclet:ref/WorkingPrecision])->(RefLink[Automatic, paclet:ref/Automatic]), the precision is taken automatically from the precision of the input arguments unless a method is specified that only works with machine precision, in which case machine precision is used.

If it is a priori known that the solution sought is where either the denominator is positive or negative, then including a constraint in a and b equivalent to positivity or negativity of the denominator will allow (RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization]) to compute the solution more quickly.

OpenersPrimaryExamplesSection(Spacer1)Examples  (56)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Minimize (x+ y)/(1+3x+2 y) subject to the constraints x+y≥2, x≥0, y≥0:

res=LinearFractionalOptimization[(x+y)/(1+3x+2y),{x+y≥2,x≥0,y≥0},{x,y}]

Show the minimizer on a plot of the function (x+ y)/(1+3x+2 y) over the feasible region:

obj=(x+y)/(1+3x+2y);
Show[Plot3D[obj,{x,y}∈ImplicitRegion[(x+y≥2&&x≥0&&y≥0),{x,y}], ],Graphics3D[{Blue, PointSize[0.05],Point[{x,y,obj}/.res]}]]

Minimize (5x-3y+2)/(4x+y+5) subject to x+2y≤4,x+3y≥6,x≥0,y≥0:

LinearFractionalOptimization[(5x-3y+2)/(4x+y+5),{x+2y≤4,x+3y≥6,x≥0,y≥0},{x,y}]

Specify the input in matrix-vector form:

{α,β,γ,δ}={{5,-3},2,{4,1},5};
{a,b}={{{-1,-2},{1,3},{1,0},{0,1}},{4,-6,0,0}};

Solve using matrix-vector form:

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

OpenersExampleSection1(Spacer1)Scope  (27)

OpenersExampleSubsection0(Spacer1)Basic Uses  (17)

Minimize (x+y-5)/ ( 3x +2y+15) subject to the constraints 3x+4y≥ 12 and y≥2:

LinearFractionalOptimization[(x+y-5)/(3x+2y+15),{3x+4y≥12,x≥2},{x,y}]

Minimize (x+y-5)/ ( 3x +2y+15) subject to the constraints 3x+4y==12 and y≥2:

LinearFractionalOptimization[(x+y-5)/(3x+2y+15),{3x+4y==7,x≥2},{x,y}]

Minimize -(x+y+5)/(3x+2y+15) subject to 3x+y≤6,3x+4y=-2 and bounds -1≤x≤1,-2≤y≤4:

LinearFractionalOptimization[-(x+y+5)/(3x+2y+15),{3x+y≤6,3x+4y==-2,-1≤x≤1,-2≤y≤4},{x,y}]

Use (RefLink[VectorLessEqual, paclet:ref/VectorLessEqual]) to express several (RefLink[LessEqual, paclet:ref/LessEqual]) inequality constraints at once:

LinearFractionalOptimization[(2+x+2y)/(1+50x+50y),VectorLessEqual[{{3x+4y,5x-6y},{-2,-20}}],{x,y}]

Use (Key0[esc]) v<= (Key0[esc]) to enter the vector inequality in a compact form:

LinearFractionalOptimization[(2+x+2y)/(1+50x+50y),{{3x+4y},{5x-6y}}\[VectorLessEqual]{-2,-20},{x,y}]

An equivalent form using scalar inequalities:

LinearFractionalOptimization[(2+x+2y)/(1+50x+50y),{3x+4y≤-2,5x-6y≤-20},{x,y}]

Use (RefLink[VectorGreaterEqual, paclet:ref/VectorGreaterEqual]) to express several (RefLink[GreaterEqual, paclet:ref/GreaterEqual]) inequality constraints at once:

LinearFractionalOptimization[(x+y-5)/(3x+2y+15),VectorGreaterEqual[{{3x+4y,x},{12,2}}],{x,y}]

Use (Key0[esc]) v>=(Key0[esc]) to enter the vector inequality in a compact form:

LinearFractionalOptimization[(x+y-5)/(3x+2y+15),{3x+4y,x}\[VectorGreaterEqual]{12,2},{x,y}]

An equivalent form using scalar inequalities:

LinearFractionalOptimization[(x+y-5)/(3x+2y+15),{3x+4y≥12,x≥2},{x,y}]

Use (RefLink[Equal, paclet:ref/Equal]) to express several equality constraints at once:

LinearFractionalOptimization[(x-y)/(1+x+y),{x+y,x-y}=={1/2,1},{x,y}]

An equivalent form using several scalar equalities:

LinearFractionalOptimization[(x-y)/(1+x+y),{x+y==1/2,x-y==1},{x,y}]

Specify constraints using a combination of scalar and vector inequalities:

LinearFractionalOptimization[-(x+y+5)/(3x+2y+15),{3x+y≤6,3x+4y≤12,{-1,-2}\[VectorLessEqual]{x,y}\[VectorLessEqual]{1,4}},{x,y}]

Minimize (x+y-5)/(3x+2y+15) subject to 3x+4y≥12,x≥2. Use vector variable v={x,y}:

LinearFractionalOptimization[({1,1}.v-5)/({3,2}.v+15),{{3,4}.v≥12,{1,0}.v≥2},v]

An equivalent form using scalar variables:

LinearFractionalOptimization[(x+y-5)/(3x+2y+15),{3x+4y≥12,x≥2},{x,y}]

Use vector variables and vector inequalities to specify the problem:

LinearFractionalOptimization[({1,1}.v-5)/({3,2}.v+15),{{3,4},{1,0}}.v\[VectorGreaterEqual]{12,2},v]

Use (RefLink[Indexed, paclet:ref/Indexed]) to access components of a vector variable, e.g. (IndexedDefault[v, 1]):

LinearFractionalOptimization[({1,1}.v-5)/({3,2}.v+15),{{3,4}.v≥12,Indexed[v,1]≥2},v]

Use parameter equations to specify the coefficients of the objective and constraints:

parameterEqns={α=={1,1},γ=={3,2},a1=={3,4},a2=={1,0}};
constraints={a1.{x,y}≥12,a2.{x,y}≥2};

LinearFractionalOptimization[(α.{x,y}-5)/(γ.{x,y}+15),{parameterEqns,constraints},{x,y}]

Use parameter equations to specify coefficients of several constraints:

parameterEqns={α=={1,1},γ=={3,2},a=={{3,4},{1,0}},b=={12,2}};

LinearFractionalOptimization[(α.{x,y}-5)/(γ.{x,y}+15),{parameterEqns,a.{x,y}\[VectorGreaterEqual]b},{x,y}]

Minimize ((∑_(j=1)^2)(Subscript[x, i])-5)/(3(Subscript[x, 1])+2(Subscript[x, 2])+(∑_(j=1)^3)(Subscript[y, i])) subject to a.x\[VectorGreaterEqual]b,y\[VectorGreaterEqual]1, y∈(ℝ^3):

parameterEqns={γ=={3,2},a=={{3,4},{1,0}},b=={12,2}};

LinearFractionalOptimization[(Total[x]-5)/(γ.x+Total[y]),{parameterEqns,a.x\[VectorGreaterEqual]b,y\[VectorGreaterEqual]1},{x,y}]

Use (RefLink[Vectors, paclet:ref/Vectors])[n] to specify the dimension of vector variables when needed:

LinearFractionalOptimization[(Total[x]-5)/(γ.x+Total[y]),{parameterEqns,a.x\[VectorGreaterEqual]b,y\[VectorGreaterEqual]1},{x,y∈Vectors[3]}]

Specify non-negative constraints using (RefLink[NonNegativeReals, paclet:ref/NonNegativeReals]) ((NonNegativeReals)):

LinearFractionalOptimization[({5,-3}.v+2)/({4,1}.v+5),{{-1,-2},{1,3}}.v\[VectorGreaterEqual]{-4,6},v∈Vectors[2,NonNegativeReals]]

An equivalent form using vector inequalities:

LinearFractionalOptimization[({5,-3}.v+2)/({4,1}.v+5),{{{-1,-2},{1,3}}.v\[VectorGreaterEqual]{-4,6},v\[VectorGreaterEqual]0},v]

Specify non-positive constraints using (RefLink[NonPositiveReals, paclet:ref/NonPositiveReals]) ((NonPositiveReals)):

LinearFractionalOptimization[({-5,3}.v+2)/({-4,-1}.v+5),{{1,2},{-1,-3}}.v\[VectorGreaterEqual]{-4,6},v∈Vectors[2,NonPositiveReals]]

An equivalent form using vector inequalities:

LinearFractionalOptimization[({-5,3}.v+2)/({-4,-1}.v+5),{{{1,2},{-1,-3}}.v\[VectorGreaterEqual]{-4,6},v\[VectorLessEqual]0},v]

Minimize (α.x+β)/(γ.x+δ) subject to a.x+b\[VectorGreaterEqual]0,(Subscript[a, eq])+(Subscript[b, eq])\[VectorGreaterEqual]0 by specifying the scalars, vectors and matrices:

{α,β,γ,δ}={{1,1},-5,{3,2},15};
{a,b}={{{3,4}},{-12}};
{aeq,beq}={{{1,0}},{0}};

Solve using the matrix-vector form:

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

The equivalent form using variables and inequalities:

constraints={Thread[a.{x,y}+b≥{0}], Thread[aeq.{x,y}+beq=={0}]}

LinearFractionalOptimization[(α.{x,y}+β)/(γ.{x,y}+δ),constraints,{x,y}]

Try to find a vector (x,y) that minimizes the function (3+x+ 2 y)/(1- 5x-5 y) subject to the constraints 3x+4y≤ 7,5x-6y≤ 20, -7x+8y≥27, x≥-3:

res=LinearFractionalOptimization[(3+x+2y)/(1-5x-5y),{3x+4y≤7,5x-6y≤20,-7x+8y≥27,x≥-3},{x,y},{"PrimalMinimumValue","PrimalMinimizerRules"}]

The minimum value is unbounded because there is a singularity across the feasible region:

Plot3D[(3+x+2y)/(1-5x-5y),{x,y}∈]

OpenersExampleSubsection1(Spacer1)Primal Model Properties  (3)

Minimize -(x+y+5)/(3x+2y+15) subject to 3x+y≤6,3x+4y≤12,-1≤x≤1,-2≤y≤4:

LinearFractionalOptimization[-(x+y+5)/(3x+2y+15),{3x+y≤6,3x+4y≤12,-1≤x≤1,-2≤y≤4},{x,y}]

Get the primal minimizer as a vector:

LinearFractionalOptimization[-(x+y+5)/(3x+2y+15),{3x+y≤6,3x+4y≤12,-1≤x≤1,-2≤y≤4},{x,y},"PrimalMinimizer"]

Get the minimal value:

LinearFractionalOptimization[-(x+y+5)/(3x+2y+15),{3x+y≤6,3x+4y≤12,-1≤x≤1,-2≤y≤4},{x,y},"PrimalMinimumValue"]

Solve an optimization problem using symbolic inputs:

obj=(x+y-5)/(3x+2y+15);
cons={3x+4y≥12,x==0};

LinearFractionalOptimization[obj,cons,{x,y}]

Extract the matrix-vector inputs of the optimization problem:

{{α,β,γ,δ},{a,b},{(Subscript[a, eq]),(Subscript[b, eq])}}=LinearFractionalOptimization[obj,cons,
{x,y},{"LinearFractionalObjectiveCoefficients","LinearInequalityConstraints","LinearEqualityConstraints"}];

Recover the symbolic input result using the matrix-vector inputs:

LinearFractionalOptimization[{α,β,γ,δ},{a,b},{(Subscript[a, eq]),(Subscript[b, eq])}]

Find the slack associated with a minimization problem:

obj=-(x+y+5)/(3x+2y+15);cons={3x+y≤6,3x+4y==-2,-1≤x≤1,-2≤y≤4};

{(Subscript[s, ineq]),(Subscript[s, eq])}=LinearFractionalOptimization[obj,cons,{x,y},"Slack"]

Get the primal minimizer and the constraint matrices:

{(SuperStar[x]),{a,b},{(Subscript[a, eq]),(Subscript[b, eq])}}=LinearFractionalOptimization[obj,cons,{x,y},];

The slack for inequality constraints a.(SuperStar[x])+b\[VectorGreaterEqual]0 is a vector (Subscript[s, ineq]) such that a.(SuperStar[x])+b-(Subscript[s, ineq])==0:

Norm[a.(SuperStar[x])+b-(Subscript[s, ineq])]==0

The slack for the equality constraints a.(SuperStar[x])+b==0 is a vector (Subscript[s, eq]) such that a.(SuperStar[x])+b-(Subscript[s, eq])==0:

Norm[(Subscript[a, eq]).(SuperStar[x])+(Subscript[b, eq])-(Subscript[s, eq])]==0

The equality slack (Subscript[s, eq]) is typically a zero vector:

(Subscript[s, eq])

OpenersExampleSubsection2(Spacer1)Dual Model Properties  (3)

Minimize (α.x+β)/(γ.x+δ) subject to a.x+b\[VectorGreaterEqual]0 and (Subscript[a, eq]).x+(Subscript[b, eq])==0:

{α,β,γ,δ}={{-1,-1},-5,{3,2},15};
{a,b}={{{-3,-1},{-1,0},{0,-1}},{6,1,1}};
{(Subscript[a, eq]),(Subscript[b, eq])}={{{3,4}},{2}};
xv = Table[Indexed[x,i],{i,2}];

psol=LinearFractionalOptimization[(α.xv+β)/(γ.xv+δ),{a.xv+b\[VectorGreaterEqual]0,(Subscript[a, eq]).xv+(Subscript[b, eq])\[VectorGreaterEqual]0},xv]

The dual problem is to maximize ζ subject to  δ ζ+b.λ+(Subscript[b, eq]).ν≤β,ζ γ+aᵀ.λ+(Subscript[a, eq])ᵀ.ν==α,λ\[VectorGreaterEqual]0:

{λv,νv}={Table[Indexed[λ,i],{i,3}],Table[Indexed[ν,i],{i,1}]};

dsol=LinearOptimization[-ζ,{δ ζ+b.λv+(Subscript[b, eq]).νv≤β,ζ γ+a\[Transpose].λv+(Subscript[a, eq])\[Transpose].νv==α,
λv\[VectorGreaterEqual]0},Join[{ζ},λv,νv]]

The primal minimum value and the dual maximum value coincide because of strong duality:

{(α.xv+β)/(γ.xv+δ)/.psol,ζ/.dsol}

The duality gap of zero. In general, (α.(SuperStar[x])+β)/(γ.(SuperStar[x])+δ)≤-b.(SuperStar[λ])-(Subscript[b, eq]).(SuperStar[ν]) at optimal points:

LinearFractionalOptimization[(α.xv+β)/(γ.xv+δ),{a.xv+b\[VectorGreaterEqual]0,(Subscript[a, eq]).xv+(Subscript[b, eq])\[VectorGreaterEqual]0},xv,"DualityGap"]

Construct the dual problem using constraint matrices extracted from the primal problem:

obj=-(x+y+5)/(3x+2y+15);
constraints={3x+y≤6,3x+4y==-2,x≤1,y≤1};

LinearFractionalOptimization[obj,constraints,{x,y}]

Extract the objective vectors and constraint matrices:

{{α,β,γ,δ},{a,b},{(Subscript[a, eq]),(Subscript[b, eq])}}=LinearFractionalOptimization[obj,constraints,{x,y},{"LinearFractionalObjectiveCoefficients","LinearInequalityConstraints","LinearEqualityConstraints"}];

The dual problem is to maximize ζ subject to  δ ζ+b.λ+(Subscript[b, eq]).ν≤β,ζ γ+aᵀ.λ+(Subscript[a, eq])ᵀ.ν==α,λ\[VectorGreaterEqual]0:

LinearOptimization[-ζ,{δ ζ+b.λ+(Subscript[b, eq]).ν≤β,ζ γ+a\[Transpose].λ+(Subscript[a, eq])\[Transpose].ν==α,λ\[VectorGreaterEqual]0},{ζ,λ,ν}]

Get the dual maximum value directly using solution properties:

obj=-(x+y+5)/(3x+2y+15);cons={3x+y≤6,3x+4y==-2,x≤1,y≤1};

LinearFractionalOptimization[obj,cons,{x,y},"DualMaximumValue"]

Get the dual maximizer directly using solution properties:

LinearFractionalOptimization[obj,cons,{x,y},"DualMaximizer"]

OpenersExampleSubsection3(Spacer1)Sensitivity Properties  (4)

Use "ConstraintSensitivity" to find the change in optimal value due to constraint relaxations:

{α,β,γ,δ}={{1,1},-5,{3,2},15};
{a,b}={{{-3,4},{1,0},{0,-1}},{12.,0.,0.}};
(SuperStar[p])=LinearFractionalOptimization[{α,β,γ,δ},{a,b},"PrimalMinimumValue"]

The first vector is inequality sensitivity and the second is equality sensitivity:

s = LinearFractionalOptimization[{α,β,γ,δ},{a,b},"ConstraintSensitivity"]

Consider new constraints a.x+b+δb\[VectorGreaterEqual]0 where δb is the relaxation. The approximate new optimal value is:

δb={0.01,0.01,0.01};
(SuperStar[p])+δb.s[[1]]

Compare directly by solving the relaxed problem:

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

Each sensitivity is associated with inequality or equality constraints:

obj=(-5+x+y)/(15+3x+2y+z);
constraints={3x-4y≤1/2,x≥0,x+y+z==10,x-z==40};

{(Subscript[s, λ]),(Subscript[s, ν])}=LinearFractionalOptimization[obj,constraints,{x,y,z},"ConstraintSensitivity"]

Extract the constraints:

{{a,b},{(Subscript[a, eq]),(Subscript[b, eq])}}=LinearFractionalOptimization[obj,constraints,{x,y,z},{"LinearInequalityConstraints","LinearEqualityConstraints"}];

The inequality constraints and their associated sensitivity:

Table[{a[[i]].{x,y,z}+b[[i]]≥0,(Subscript[s, λ])[[i]]},{i,2}]

The equality constraints and their associated sensitivity:

Table[{(Subscript[a, eq])[[i]].{x,y,z}+(Subscript[b, eq])[[i]]==0,(Subscript[s, ν])[[i]]},{i,2}]

The change in optimal value due to constraint relaxation is proportional to the sensitivity value:

{α,β,γ,δ}={{1,1,0},-5,{3,2,1},15};
{a,b}={{{-3,4,0},{1,0,0}},{1/2,0}};
{(Subscript[a, eq]),(Subscript[b, eq])}={{{1,1,1},{1,0,-1}},{-10,-40}};

Compute the minimal value and constraint sensitivity:

{(SuperStar[p]),{(Subscript[s, λ]),(Subscript[s, ν])}}=LinearFractionalOptimization[{α,β,γ,δ},{a,b},{(Subscript[a, eq]),(Subscript[b, eq])}, {"PrimalMinimumValue","ConstraintSensitivity"}]

A zero sensitivity will not change the optimal value if the constraint is relaxed:

(Subscript[s, λ])[[2]]

(SuperStar[p])==LinearFractionalOptimization[{α,β,γ,δ},{a,b+{0,1}},{(Subscript[a, eq]),(Subscript[b, eq])},"PrimalMinimumValue"]

A negative sensitivity will decrease the optimal value:

(Subscript[s, λ])[[1]]

(SuperStar[p])>LinearFractionalOptimization[{α,β,γ,δ},{a,b+{1,0}},{(Subscript[a, eq]),(Subscript[b, eq])},"PrimalMinimumValue"]

A positive sensitivity will increase the optimal value:

(Subscript[s, ν])[[1]]

(SuperStar[p])<LinearFractionalOptimization[{α,β,γ,δ},{a,b},{(Subscript[a, eq]),(Subscript[b, eq])+{1,0}},"PrimalMinimumValue"]

The "ConstraintSensitivity" is related to the dual maximizer of the problem:

obj=(-5+x+y)/(15+3x+2y+z);
constraints={3x-4y≤1/2,x≥0,x+y+z==10,x-z==40};

{{(Subscript[s, λ]),(Subscript[s, ν])},{ζ,(SuperStar[λ]),(SuperStar[ν])}}=LinearFractionalOptimization[
obj,constraints,{x,y,z},{"ConstraintSensitivity","DualMaximizer"}]

The inequality sensitivity (Subscript[s, λ])==((∂(SuperStar[p]))/(∂b)) satisfies (Subscript[s, λ])==-(SuperStar[λ])/(γ.(SuperStar[x])+δ), where (SuperStar[λ]) is the dual inequality maximizer:

{(SuperStar[x]),(SuperStar[y]),(SuperStar[z])}=LinearFractionalOptimization[obj,constraints,{x,y,z},"PrimalMinimizer"];

(Subscript[s, λ])==-(SuperStar[λ])/(15+3(SuperStar[x])+2(SuperStar[y])+(SuperStar[z]))

The equality sensitivity (Subscript[s, ν])==((∂(SuperStar[p]))/(∂(Subscript[b, eq]))) satisfies (Subscript[s, ν])==-(SuperStar[ν])/(γ.(SuperStar[x])+δ), where (SuperStar[ν]) is the dual equality maximizer:

(Subscript[s, ν])==-(SuperStar[ν])/(15+3(SuperStar[x])+2(SuperStar[y])+(SuperStar[z]))

OpenersExampleSection2(Spacer1)Options  (8)

OpenersExampleSubsection4(Spacer1)Method  (4)

The default method for (RefLink[MachinePrecision, paclet:ref/MachinePrecision]) is "CLP":

obj=-(x+y+5)/(3x+2y+15);
cons={3x+y≤6,3x+4y≤12,-1≤x≤1,-2≤y≤4};

LinearFractionalOptimization[obj,N[cons],{x,y},Method->Automatic]

LinearFractionalOptimization[obj,N[cons],{x,y},Method->"CLP"]

The default method for arbitrary or infinite (RefLink[WorkingPrecision, paclet:ref/WorkingPrecision]) is "Simplex":

LinearFractionalOptimization[obj,cons,{x,y},Method->Automatic]

LinearFractionalOptimization[obj,cons,{x,y},Method->"Simplex"]

All methods work for (RefLink[MachinePrecision, paclet:ref/MachinePrecision]) input:

obj=-(x+y+5)/(3x+2y+15);
cons={3x+y≤6,3x+4y≤12,-1≤x≤1,-2≤y≤4};

Table[LinearFractionalOptimization[obj,N[cons],{x,y},Method-> met],{met,{"Simplex","RevisedSimplex","InteriorPoint","CLP"}}]

"Simplex" and "RevisedSimplex" can be used for arbitrary- and infinite-precision inputs:

Table[LinearFractionalOptimization[obj,N[cons,20],{x,y},Method-> met],{met,{"Simplex","RevisedSimplex"}}]

Different methods have different strengths, which is typically problem and implementation dependent:

a=SparseArray[{Band[{1,1}]->1.,Band[{1,2}]-> 2.},{500,300}];

"Simplex" and "RevisedSimplex" are good for small dense problems:

Timing[LinearFractionalOptimization[Total[x]/(1+Total[x]),
{a.x\[VectorGreaterEqual]-1,x\[VectorGreaterEqual]0},x,Method->"Simplex"];]

"InteriorPoint" and "CLP" are good for large sparse problems:

Timing[LinearFractionalOptimization[Total[x]/(1+Total[x]),
{a.x\[VectorGreaterEqual]-1,x\[VectorGreaterEqual]0},x,Method->"InteriorPoint"];]

Timing[LinearFractionalOptimization[Total[x]/(1+Total[x]),
{a.x\[VectorGreaterEqual]-1,x\[VectorGreaterEqual]0},x,Method->"CLP"];]

Different methods may give different results for problems where the optimal solution set is not unique:

ContourPlot[-(x+y)/(1+x+y),{x,y}∈ImplicitRegion[x+y≤1&&x≥0&&y≥0,{x,y}],ContourLabels->True,ImageSize->Small]

"InteriorPoint" may return a solution in the middle of the optimal solution set:

LinearFractionalOptimization[-(x+y)/(1+x+y),{x+y≤1,x≥0,y≥0},{x,y},Method->"InteriorPoint"]

"Simplex" always returns a solution at a corner of the optimal solution set:

LinearFractionalOptimization[-(x+y)/(1+x+y),{x+y≤1,x≥0,y≥0},{x,y},Method->"Simplex"]

OpenersExampleSubsection5(Spacer1)Tolerance  (2)

A smaller (RefLink[Tolerance, paclet:ref/Tolerance]) setting gives a more precise result:

n=2000; m=1000;
a=SparseArray[{Band[{1,1}]->1,Band[{1,2}]-> 2},{m,n}];
b=Range[m];

Compute minimum value with very small tolerance to serve as reference:

(Subscript[p, ref])=LinearFractionalOptimization[Total[x]/(1+Total[x]),{a.x\[VectorGreaterEqual]b,x\[VectorGreaterEqual]0},x,"PrimalMinimumValue", Method->"InteriorPoint",Tolerance-> 10^-12]

Compute the solution using different (RefLink[Tolerance, paclet:ref/Tolerance]) settings:

err=Table[{tol,Abs[(Subscript[p, ref])-LinearFractionalOptimization[
,Tolerance->tol]]},{tol,10.^-Range[7]}]

Visualize the change in error with respect to tolerance:

ListLogLogPlot[err, PlotRange->All,Joined->True,PlotMarkers->Automatic]

A smaller (RefLink[Tolerance, paclet:ref/Tolerance]) setting gives a more precise answer, but typically takes longer to compute:

n=2000; m=1000;
a=SparseArray[{Band[{1,1}]->1.,Band[{1,2}]-> 2.},{m,n}];
b=Range[m];

A smaller tolerance takes longer:

Timing[ptight=LinearFractionalOptimization[Total[x]/(n+Total[x]),{a.x\[VectorGreaterEqual]b,x\[VectorGreaterEqual]0},x,"PrimalMinimumValue",Tolerance-> (10^(-12)),Method->"InteriorPoint"];]

Timing[ploose=LinearFractionalOptimization[Total[x]/(n+Total[x]),{a.x\[VectorGreaterEqual]b,x\[VectorGreaterEqual]0},x,"PrimalMinimumValue",Tolerance-> (10^(-1)),Method->"InteriorPoint"];]

The tighter tolerance gives a more precise answer:

{ptight,ploose}

OpenersExampleSubsection6(Spacer1)WorkingPrecision  (2)

Exact input gives exact output:

LinearFractionalOptimization[((Subscript[x, 1])+(Subscript[x, 2])-5)/(3(Subscript[x, 1])+2(Subscript[x, 2])+15),{3(Subscript[x, 1])+4(Subscript[x, 2])≥12,(Subscript[x, 1])≥2},{(Subscript[x, 1]),(Subscript[x, 2])}]

Use (RefLink[MachinePrecision, paclet:ref/MachinePrecision]) to get an inexact result:

LinearFractionalOptimization[((Subscript[x, 1])+(Subscript[x, 2])-5)/(3(Subscript[x, 1])+2(Subscript[x, 2])+15),{3(Subscript[x, 1])+4(Subscript[x, 2])≥12,(Subscript[x, 1])≥2},{(Subscript[x, 1]),(Subscript[x, 2])}, WorkingPrecision-> MachinePrecision]

(RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization]) can compute results using a higher working precision:

LinearFractionalOptimization[((Subscript[x, 1])+(Subscript[x, 2])-5)/(3(Subscript[x, 1])+2(Subscript[x, 2])+15),{3(Subscript[x, 1])+4(Subscript[x, 2])≥12,(Subscript[x, 1])≥2},{(Subscript[x, 1]),(Subscript[x, 2])}, WorkingPrecision-> 30]

If the precision is less than the precision of the input arguments, a message is issued:

LinearFractionalOptimization[((Subscript[x, 1])+(Subscript[x, 2])-5.0)/(3(Subscript[x, 1])+2(Subscript[x, 2])+15),{3(Subscript[x, 1])+4(Subscript[x, 2])≥12,(Subscript[x, 1])≥2},{(Subscript[x, 1]),(Subscript[x, 2])}, WorkingPrecision-> 30]

OpenersExampleSection3(Spacer1)Applications  (11)

OpenersExampleSubsection7(Spacer1)Basic Modeling Transformations  (6)

Maximize (5-(Subscript[x, 1])-(Subscript[x, 2]))/(5+3(Subscript[x, 1])+2(Subscript[x, 2])) subject to 3(Subscript[x, 1])+2(Subscript[x, 2])≥1,(Subscript[x, 1])≤1. Solve a maximization problem by negating the objective function:

LinearFractionalOptimization[-(5-(Subscript[x, 1])-(Subscript[x, 2]))/(5+3(Subscript[x, 1])+2(Subscript[x, 2])),{3(Subscript[x, 1])+2(Subscript[x, 2])≥1,(Subscript[x, 1])≤ 1},{(Subscript[x, 1]),(Subscript[x, 2])}]

Negate the primal minimal value to get the corresponding maximum value:

-LinearFractionalOptimization[-(5-(Subscript[x, 1])-(Subscript[x, 2]))/(5+3(Subscript[x, 1])+2(Subscript[x, 2])),{3(Subscript[x, 1])+2(Subscript[x, 2])≥1,(Subscript[x, 1])≤ 1},{(Subscript[x, 1]),(Subscript[x, 2])}, "PrimalMinimumValue"]

Minimize |x+y|/(1+x+3y) subject to 2x-y≤1,x≥ 0,y≥0. Let x+y=t, and convert|t| into a linear function using |t|=(SuperPlus[t])+(SuperMinus[t]), t=(SuperPlus[t])-(SuperMinus[t]), (SuperPlus[t])≥0,(SuperMinus[t])≥0:

LinearFractionalOptimization[(tp+tm)/(1+x+3y),{2x-y≥1,x≥0,y≥0,x+y==tp-tm,tp≥0,tm≥0},{x,y,tp,tm}]

The problem can also be converted using t=|x+y|, -t≤x+y≤t:

LinearFractionalOptimization[t/(1+x+3y),{2x-y≥1,x≥0,y≥0,-t≤x+y≤t},{x,y,t}]

Minimize ||{x,2y}(Subscript[||, 1])/(1+x+3y) subject to 2x-y≥1,x≥ 0,y≥0. Since ||{x,2y}(Subscript[||, 1])=|x|+|2y|, letting (Subscript[s, 1])=|x|, (Subscript[s, 2])=|2y|, -(Subscript[s, 1])≤x≤(Subscript[s, 2]), -(Subscript[s, 2])≤2y≤(Subscript[s, 2]), the objective is transformed to ((Subscript[s, 1])+(Subscript[s, 2]))/(1+x+3y):

LinearFractionalOptimization[(s1+s2)/(1+x+3y),{2x-y≥1,x≥0,y≥0,-s1≤x≤s1,-s2≤2y≤s2},{x,y,s1,s2}]

Minimize ||{x,2y}(Subscript[||, ∞])/(1+x+3y) subject to 2x-y≥1,x≥ 0,y≥0. Since ||{x,2y}(Subscript[||, ∞])=Max(|x|,|2y|), using s=||{x,2y}(Subscript[||, ∞]), -s≤x≤s, -s≤2y≤s, the objective is transformed to s/(1+x+3y):

LinearFractionalOptimization[s/(1+x+3y),{2x-y≥1,x≥0,y≥0,-s≤x≤s,-s≤2y≤s},{x,y,s}]

Minimize f((β+α.x)/(δ+γ.x)) subject to a.x⪯b, where f is a nondecreasing function, by instead minimizing (β+α.x)/(δ+γ.x). The primal minimizer (SuperStar[x]) will remain same for both problems. Consider minimizing f(x,y)=((((x+y)/(1+x+3y)))^2) subject to 2x-y≤1,x≥ 0,y≥0, x+y≥0:

g=(x+y)/(1+x+3y);
f=Function[{s},s^2];

{minval,(Subscript[X, min])}=LinearFractionalOptimization[g,{2x-y≥1,x≥0,y≥0,x+y≥0},{x,y},{"PrimalMinimumValue","PrimalMinimizerRules"}]

The true minimum value can be obtained by applying the function f to the primal minimum value:

f[minval]

Minimize f(z)=√z, z=(x+y)/(1+x+3y), z≥0, subject to 2x+y≥1,-2≤y≤2:

g=(x+y)/(1+x+3y);
f=Function[{s},Sqrt[s]];

Since z≥0, solve the problem with x+y≥0,x+3y≥0 and x+y≤ 0,x+3y≤0:

res1=LinearFractionalOptimization[(x+y)/(1+x+3y),{2x+y≥1,x+y≥0,1+x+3y≥0, -2≤y≤2},{x,y},{"PrimalMinimumValue","PrimalMinimizerRules"}]

res2=LinearFractionalOptimization[(x+y)/(1+x+3y),{2x+y≥1,x+y≤0,1+x+3y≤0,-2≤y≤2},{x,y},{"PrimalMinimumValue","PrimalMinimizerRules"}]

The optimal solution is the transformed minimum of the two solutions:

First@MinimalBy[{res1,res2},f[First[#]]&]

OpenersExampleSubsection8(Spacer1)Transportation Problem  (1)

Choose a number of units to transport for five goods by minimizing cost and maximizing profit. The cost and profit of transporting one unit of each good are:

costPerUnit = {100,100,100,100,100};
profitPerUnit={115,108,130,120,110};

The weight of each unit of goods and the maximum units available for transport are:

weightPerUnit={100,100,110,200,115};
maxUnits={30,20,20,30,20};

The minimum operating cost of running the truck is $2000 for the trip. The total transportation cost is:

cost=2000+costPerUnit.x;

The truck makes a minimum profit of $1000 if it rides empty. The total profit is:

profit=1000+profitPerUnit.x;

The truck can carry a maximum of 8000 lbs. The constraints on the truck are:

wtConstraint=weightPerUnit.x\[VectorLessEqual]8000;
goodsConstraints=0\[VectorLessEqual]x\[VectorLessEqual]maxUnits;

The optimal mix of goods to transport if found by minimizing the ratio of cost to profit:

res = LinearFractionalOptimization[cost/profit,{wtConstraint,goodsConstraints},x∈Vectors[5]]

TableForm[{x/.res}, TableHeadings->{{"Units"},Array[(Subscript[x, #])&,5]}]

OpenersExampleSubsection9(Spacer1)Production Planning  (1)

Find the mix of four products to manufacture that minimize cost and maximize profit. The cost and profit of manufacturing one unit of each product are:

costPerUnit={8,5,5,8};
profitPerUnit={10,10,10,10};

To manufacture each product, the company needs a combination of five resources, given by:

resourcesNeeded={{5,1,0,4},{3,3,10,3},{7,2,5,5},{0,5,8,0},{10,20,0,0}};
GraphicsRow[, ImageSize->450]

The maximum resources available are:

maxResources={20,20,20,50,50};

The constraints on the resources and products are:

resourceConstraint=resourcesNeeded.x\[VectorLessEqual]maxResources;
productConstraints=x\[VectorGreaterEqual]0;

The company has a minimum operating cost of $100. The total manufacturing cost is:

totalCost=100+costPerUnit.x;

The total profit made by selling the products is:

totalProfit=profitPerUnit.x;

To find out the maximum units to manufacture, minimize the ratio of cost to profit:

res=LinearFractionalOptimization[totalCost/totalProfit,{resourceConstraint,productConstraints},x]

OpenersExampleSubsection10(Spacer1)Resource Allocation  (1)

Find the amount of electricity a company must send from its three power plants to four cities so as to maximize profit and minimize cost while meeting the cities' peak demands. The cost of transporting the 1 million kWh of electricity from each plant to the various cities is:

cost={{8,6,10,9},{9,12,13,7},{14,9,16,5}};
GraphicsRow[&/@Range[3]]

The profit that each power plant generates by selling 1 million kWh to each city is:

profit={{5,4,4,3},{6,2,3,4},{10,5,6,2}};
GraphicsRow[&/@Range[3]]

Let (Subscript[x, i,j]) represent the amount of electricity sent by plant (Subscript[p, i]) to city (Subscript[c, j]). The total cost of transporting electricity is (∑_(i=1))(∑_(j=1))(Subscript[cost, ij])(Subscript[x, ij]) and constructed using (RefLink[Inactive, paclet:ref/Inactive])[(RefLink[Times, paclet:ref/Times])]:

totalCost= Total[cost*x,2];

The total profit made by the power company is (∑_(i=1))(∑_(j=1))(Subscript[p, ij])(Subscript[x, ij]) and constructed using (RefLink[Inactive, paclet:ref/Inactive])[(RefLink[Times, paclet:ref/Times])]:

totalProfit=Total[profit*x,2];

The cities have a peak demand of 45, 20, 30, 30 million kWh, respectively:

peakDemand=Total[x]\[VectorLessEqual]{45,20,30,30};

The power plants can supply a minimum of 35, 50 and 40 million kWh of electricity, respectively:

minSupply=Total[x,{2}]\[VectorGreaterEqual]{35,50,40};

The plants can only give and not receive power from the cities:

negativePowerConstraint = x\[VectorGreaterEqual]0;

The optimal amount of electricity to send each city by each plant can be found by minimizing the ratio of cost to profit:

res=LinearFractionalOptimization[totalCost/totalProfit,{peakDemand,minSupply,negativePowerConstraint},x∈Matrices[{3,4}]]

The breakdown of electricity supplied is:

TableForm[(x/.res) , TableHeadings->{{"Plant 1", "Plant 2","Plant 3"},{"City 1","City 2","City 3","City 4"}}]

OpenersExampleSubsection11(Spacer1)Blending Problems  (1)

Find the mix of old alloys needed to make a new alloy containing at most 60% lead and at most 35% tin while minimizing cost and maximizing profit. The foundry has four existing old alloys containing tin and lead:

tinAvailable={0.6,0.4,0.2,0.3};
leadAvailable={0.4,0.6,0.8,0.7};
GraphicsRow[&/@Range[2], ImageSize->400]

Let (Subscript[w, i]) be the weight of the old alloy i. The new alloy is produced by a combination of the old alloys:

newAlloy=Total[w];

The cost to acquire one pound of each of the four alloys is:

costPerPound={240,180,160,210};

The cost to produce the new alloy is:

totalCost=costPerPound.w;

The foundry sells the new alloy for $200. The total profit that the foundry makes is:

totalProfit=200 newAlloy;

The foundry must produce at least 15 lbs of the new alloy containing at most 60% lead and 35% tin:

wtConstraint=newAlloy≥15;
leadConstraint=0.6newAlloy≤leadAvailable.w;
tinConstraint=0.35newAlloy≤tinAvailable.w;

The foundry has access to only 12, 15, 16 and 10 lbs of the four old alloys respectively:

resourceConstraint={VectorLessEqual[{w,{12,15,16,10}}],
VectorGreaterEqual[{w,0}]};

The optimal mix of the old alloys to use can be found by minimizing the ratio of cost to profit:

res=LinearFractionalOptimization[totalCost/totalProfit,{wtConstraint,tinConstraint,leadConstraint,resourceConstraint},w]

TableForm[{w/.res}, TableHeadings->{{"lbs (x)"},{"(Subscript[a, 1])","(Subscript[a, 2])","(Subscript[a, 3])","(Subscript[a, 4])"}}]

OpenersExampleSubsection12(Spacer1)Investment Problems  (1)

Find the allocation of a maximum of $250,000 of capital to purchase two stocks and a bond such that the return on investment is maximized while reducing the cost of purchasing the stocks/bond. Let (Subscript[x, 1]),(Subscript[x, 2]) be the amount to invest in the two stocks and let (Subscript[x, 3]) be the amount to invest in the bond:

capitalConstraint=(Subscript[x, 1])+(Subscript[x, 2])+(Subscript[x, 3])≤250000;

The amount invested in the utilities stock cannot be more than $40,000 and pay a 9% dividend:

utilityStockConstraint=0≤(Subscript[x, 1])≤40000;

The amount invested in the bond must be at least $70,000 and pay 5% interest:

bondConstraint=(Subscript[x, 3])≥70000;

The total amount invested in the two stocks must be at least half the total amount invested:

investmentConstraint=(Subscript[x, 1])+(Subscript[x, 2])≥((Subscript[x, 1])+(Subscript[x, 2])+(Subscript[x, 3]))/2;

The electronics stock pays a 4% dividend annually. The total return on investment is:

totalProfit=(0.09(Subscript[x, 1])+0.04(Subscript[x, 2])+0.05(Subscript[x, 3]));

The cost associated with the investment is:

totalCost=((Subscript[x, 1])+(Subscript[x, 2])+(Subscript[x, 3]));

The optimal amount to be invested can be found by minimizing the ratio of cost to profit:

res = LinearFractionalOptimization[totalCost/totalProfit,{capitalConstraint,utilityStockConstraint,bondConstraint,investmentConstraint}, {(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}]

The total amount invested and the annual dividends received from the investments are:

{totalCost,totalProfit}/.res

OpenersExampleSection4(Spacer1)Properties & Relations  (5)

(RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization]) gives the global minimum of the objective function:

res=LinearFractionalOptimization[(1+x+y)/(1-3x-5y),{3x-3y≥1,x≥1,y≥1},{x,y}]

Show[Plot3D[(1+x+y)/(1-3x-5y),{x,y}∈ImplicitRegion[3x-3y≥1&&x≥1&&y≥1,{x,y}]],Graphics3D[{PointSize[0.05],Point[{x,y,(1+x+y)/(1-3x-5y)}/.res]}]]

(RefLink[Minimize, paclet:ref/Minimize]) also gives global exact results for linear fractional optimization problems:

Minimize[{(1+x+y)/(1-3x-5y),{3x-3y≥1,x≥1,y≥1}},{x,y}]

(RefLink[NMinimize, paclet:ref/NMinimize]) can be used to obtain inexact results using global methods:

NMinimize[{(1+x+y)/(1-3x-5y),{3x-3y≥1,x≥1,y≥1}},{x,y}]

(RefLink[FindMinimum, paclet:ref/FindMinimum]) can be used to obtain inexact results using local methods:

FindMinimum[{(1+x+y)/(1-3x-5y),{3x-3y≥1,x≥1,y≥1}},{x,y}]

(RefLink[LinearOptimization, paclet:ref/LinearOptimization]) is a special case of (RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization]):

LinearFractionalOptimization[(1+x+y),{3x-3y≥1,x≥1,y≥1},{x,y}]

LinearOptimization[(1+x+y),{3x-3y≥1,x≥1,y≥1},{x,y}]

OpenersExampleSection5(Spacer1)Possible Issues  (3)

Constraints specified using strict inequalities may not be satisfied:

res=LinearFractionalOptimization[(x+y)/(1+3x+2y),{x+y>2,x>0,y>0},{x,y}]

The solution given is inf {(x+y)/(1+3x+2y)|x+ y>2,x>0,y>0}:

{x+y>2,x>0,y>0}/.res

The minimum value of an empty set or infeasible problem is defined to be ∞:

LinearFractionalOptimization[x/(x+1),{x≤0,x≥1},x,"PrimalMinimumValue"]

The minimizer is (RefLink[Indeterminate, paclet:ref/Indeterminate]):

LinearFractionalOptimization[x/(x+1),{x≤0,x≥1},x]

The minimum value for an unbounded set or unbounded problem is -∞:

LinearFractionalOptimization[(1+x+2y)/(1+x+y),x+y≤0,{x,y},"PrimalMinimumValue"]

The minimizer is (RefLink[Indeterminate, paclet:ref/Indeterminate]):

LinearFractionalOptimization[(1+x+2y)/(1+x+y),x+y≤0,{x,y}]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[LinearOptimization, paclet:ref/LinearOptimization])  ▪  (RefLink[QuadraticOptimization, paclet:ref/QuadraticOptimization])  ▪  (RefLink[FindMinimum, paclet:ref/FindMinimum])  ▪  (RefLink[NMinimize, paclet:ref/NMinimize])  ▪  (RefLink[Minimize, paclet:ref/Minimize])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Optimization, paclet:guide/Optimization])}, {▪(RefLinkPlain[Convex Optimization, paclet:guide/ConvexOptimization])}})}})