知识卡片

普通读书笔记卡 · 3690

法卡斯引理给不可行证书

理解等级:高级

对线性不等式组Mv≤g,法卡斯引理断言恰有一者成立:存在可行v;或存在非负w使wᵀM=0且wᵀg。

后一组乘子把所有左端消为零、右端压成负数。若可行 v 与该 w 同时存在,由 Mv≤g 和 w≥0 可得 wᵀMv≤wᵀg,但左侧 wᵀMv=(wᵀM)v=0,右侧却小于 0,产生 0<0 型矛盾。因此 w 构成任何人都能直接核验的不可行证书。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第29章 线性规划 · 查看原书依据

      Lemma 29.3 (Farkas’s lemma) Given M ∈ ℝ(m+1)×n and g ∈ ℝm+1, exactly one of the following statements is true: There exists v ∈ ℝn such that Mv ≤ g, There exists w ∈ ℝm+1 such that w ≥ 0, wTM = 0 (an n-vector of all zeros), and wTg < 0.

    参考来源

    - 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[35000,40000))。 - 结论依据:引理29.3 在 `OEBPS/chapter029.xhtml` 的两条列表项直接写出互斥条件;这里的 M 有 m+1 行。该引理的证明留给问题29-4,卡片记录引理陈述及不可行证书的直接推论。 - 公式核读:恰有其一成立:∃v∈ℝⁿ,Mv≤g;或 ∃w∈ℝᵐ⁺¹,w≥0、wᵀM=0、wᵀg<0。后一条件与前一条件不能同时成立,因为 0=wᵀMv≤wᵀg<0 矛盾。 - 原始内容:Lemma 29.3 (Farkas’s lemma) Given M ∈ ℝ ( m +1)× n and g ∈ ℝ m +1 , exactly one of the following statements is true: There exists v ∈ ℝ n such that Mv ≤ g , There exists w ∈ ℝ m +1 such that w ≥ 0, w T M = 0 (an n -vector of all zeros), and w T g < 0.