Customer Tolerances, p. 882 — a ratio of linear functions is uniformly increasing or decreasing along a line avoiding the zeros of its denominator
ProvedCuttingStock63.Fractional.ratio_monotone_on_lineLet and consider the ratio of two linear functions restricted to the line through in direction ,
Let be an interval on which the denominator does not vanish. Then:
- is strictly increasing on , or strictly decreasing on , or constant on ;
- the derivative changes along only by a positive factor: for all ,
In particular has the same sign at every point of .
This is what lets the simplex method be used for a ratio objective: along an edge the objective cannot first improve and then deteriorate, so the local test at a vertex decides the whole edge.
Formalization Note The page says the derivative "will have the same value " at every point of the line; this is false when the denominator is not constant along the line (the derivative of is ). The statement formalizes the correct version, which is what "uniformly increasing or decreasing" and the simplex argument need: the derivative times the squared denominator is constant. The page's "rational function" is the ratio of two linear functions of p. 881, Derman's published fracObj. The page speaks of a whole line; the statement is for any interval (the whole line being ), which is the stronger form used along a segment of the feasible set.
import Mathlib import Definitions.Def_DermanSeqDecisions_LinProg_LinearFractional
namespace CuttingStock63.Fractional
open DermanSeqDecisions.LinProg
theorem ratio_monotone_on_line {n : ℕ} (c d x v : Fin n → ℝ) (I : Set ℝ)
(hI : IsPreconnected I) (hden : ∀ τ ∈ I, ∑ i, d i * (x + τ • v) i ≠ 0) :
(StrictMonoOn (fun τ : ℝ => fracObj c d (x + τ • v)) I ∨
StrictAntiOn (fun τ : ℝ => fracObj c d (x + τ • v)) I ∨
∀ τ ∈ I, ∀ τ' ∈ I, fracObj c d (x + τ • v) = fracObj c d (x + τ' • v)) ∧
∀ τ ∈ I, ∀ τ' ∈ I,
deriv (fun s : ℝ => fracObj c d (x + s • v)) τ * (∑ i, d i * (x + τ • v) i) ^ 2 =
deriv (fun s : ℝ => fracObj c d (x + s • v)) τ' * (∑ i, d i * (x + τ' • v) i) ^ 2 := by sorry
end CuttingStock63.Fractional
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.