Let A and B represent two linear inequalities:
A:a1x1+...+anxn≥k1
B:b1x1+...+bnxn≥k2
If A and B is unsatisfiable (does not have solution), does the following hold in general (the conjunction of two inequalities implies the summation of them )? If so, I am looking for a formal proof?
A∧B⟹A+B
𝑎1𝑥1+...+𝑎n𝑥n≥𝑘1∧𝑏1𝑥1+...𝑏n𝑥n≥𝑘2⟹𝑎1𝑥1+...+𝑎n𝑥n+𝑏1𝑥1+...𝑏n𝑥n≥𝑘1+𝑘2
and then I would like to generalize the above theorem to summation of several inequalities.
My attempt:
My intuition is that if A and B be unsatisfiable, there is a matrix of Farkas coefficient C such that the weighted sum of A + B would be zero, and leads to -1 > 0 contradiction. Since A and B are unsatisfiable, the conjunction would be false. Therefore ⊥⟹⊥
which is a correct statement.
My question is how to generalise this proof for a system of linear inequalities
A:⋀Σni=1aixi≤ki∧⋀Σni=1biyi≤li
and
B:⋀Σnj=1ajxj≤wj∧⋀Σnj=1bjyj≤zj
No comments:
Post a Comment