Consider a Linear Programming problem in dictionary form, max { f π + ∑ j ∈ D ( π ) d j π x j | ∀ i ∈ B ( π ) b i π + ∑ j ∈ D ( π ) G i j π x j ≥ 0 , ∀ j ∈ D ( π ) x j ≥ 0 } ,where indices π uniquely define the coefficients of each basic inequality system.Now assume that the problem is both primal and dual infeasible. Primal infeasibility implies that there always exists a "primal-infeasible" basis α with some r ∈ B ( α ) having b r α &lt; 0 and ∀ j ∈ D ( α ) G r j α ≤ 0, while dual infeasibility implies that there exists a (possibly different) "dual-infeasible" basis β with some s ∈ D ( β ) having d s β &gt; 0 and ∀ i ∈ B ( β ) G i s β ≥ 0.It is easy to construct doubly infeasible problems where both of the above properties appear together at some of its bases, that is, where α = β. But is that true for all doubly infeasible problems? By a case by case analysis, I was able to prove that a counterexample to the existence of such doubly infeasible bases would have at least | D ( π ) | ≥ 3 and | B ( π ) | ≥ 3.Does a doubly infeasible problem always have bases that are simultaneously primal-infeasible and dual-infeasible? Alternatively, is there a doubly infeasible problem such that the above two properties do only appear at different bases?

Question

Consider a Linear Programming problem in dictionary form,  max        {        f    π    +            ∑          j      ∈      D      (      π      )                d    j    π        x    j             |       ∀     i    ∈    B  (  π  )               b    i    π    +            ∑          j      ∈      D      (      π      )                G          i      j        π        x    j    ≥  0  ,           ∀     j    ∈    D  (  π  )            x    j    ≥  0        }    ,where indices   π uniquely define the coefficients of each basic inequality system.Now assume that the problem is both primal and dual infeasible. Primal infeasibility implies that there always exists a &quot;primal-infeasible&quot; basis α with some   r    ∈    B  (  α  ) having           b    r    α    &amp;lt;  0 and   ∀     j    ∈    D  (  α  )            G          r      j        α    ≤  0, while dual infeasibility implies that there exists a (possibly different) &quot;dual-infeasible&quot; basis   β with some   s    ∈    D  (  β  ) having           d    s    β    &amp;gt;  0 and   ∀     i    ∈    B  (  β  )            G          i      s        β    ≥  0.It is easy to construct doubly infeasible problems where both of the above properties appear together at some of its bases, that is, where   α  =  β. But is that true for all doubly infeasible problems? By a case by case analysis, I was able to prove that a counterexample to the existence of such doubly infeasible bases would have at least   |  D  (  π  )  |  ≥  3 and   |  B  (  π  )  |  ≥  3.Does a doubly infeasible problem always have bases that are simultaneously primal-infeasible and dual-infeasible? Alternatively, is there a doubly infeasible problem such that the above two properties do only appear at different bases?

pyphekam · Accepted Answer

The answer is Yes. A doubly infeasible problem does always have some basis that is both primal infeasible and dual infeasible.

Consider a Linear Programming problem in dictionary form, <mo movablelimits="true" form="prefix"

Answered question

Answer & Explanation

New Questions in Algebra I