Proof of Lemma 3, p. 208 — the exchange is extreme
ProvedMaxPressure.ReversedLeontief.single_processor_exchangeextreme-allocationmaximum-pressurep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reversed-leontief
Consider a reversed Leontief network satisfying the standing assumptions of §2, an extreme allocation , a processor and a possible activity . Let be the -th unit vector of , with for the idle Activity , and let
Then , and for every
This single-processor exchange gives the forward direction of Lemma 3: if some processor could switch to an activity of strictly higher pressure, would not maximize the pressure.
Formalization Note. is arbitrary (the page has ), a disclosed strengthening; when is idle, is the zero vector.
Preamble
import Mathlib import Definitions.Def_MaxPressure_ReversedLeontief_Network
Formal statement
namespace MaxPressure.ReversedLeontief
/-- Proof of Lemma 3, p. 208: in a reversed Leontief network, for an extreme allocation `a`,
a processor `k` and `o ∈ 𝒥(k)`, the allocation `ã = a − e_{j_k(a)} + e_o` (with `e_0 = 0`
for the idle Activity 0) is extreme, and `p(ã, z) = p(a, z) − p(j_k(a), z) + p(o, z)`. -/
theorem single_processor_exchange {I J K : ℕ} (N : Network I J K) (hN : N.Standing)
(hRL : IsReversedLeontief N) (a : Fin J → ℝ) (ha : a ∈ extremeAllocs N) (k : Fin K)
(o : Option (Fin J)) (ho : o ∈ procActs N k) :
a - unitVec (activityOf N a k) + unitVec o ∈ extremeAllocs N ∧
∀ z : Fin I → ℝ, pressure N (a - unitVec (activityOf N a k) + unitVec o) z =
pressure N a z - actPressure' N (activityOf N a k) z + actPressure' N o z := by sorry
end MaxPressure.ReversedLeontief
Source
Dai & Lin, Maximum pressure policies in stochastic processing networks, Oper. Res. 53(2) (2005), p. 208, §8, proof of Lemma 3 (forward direction)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.