Integer programming, system of linear inequalities. t 01 + t 11 + t 21 ≥ 4 t 02 + t 12 + t 22 ≥ 4 t 10 + t 11 + t 12 ≥ 4 t 10 + t 01 + t 22 ≥ 4 t 10 + t 02 + t 21 ≥ 4 t 20 + t 21 + t 22 ≥ 4 t 20 + t 01 + t 12 ≥ 4 t 20 + t 02 + t 11 ≥ 4There are 8 integer unknowns, t i j ≥ 0 , 0 ≤ i ≤ 2 , 0 ≤ j ≤ 2 , t 00 is missing. Every unknown is used in exacly 3 inequalitites. The problem is to find solution that minimizes sum of all t i j 3 × ∑ ≥ 8 × 4 ∑ ≥ 11I have got this solution t i j = [ 2 2 2 2 0 2 0 2 ] and I need hint to prove that it optimal. Sum of all unknowns is 12 here. Maybe linear programming method can be used?

Question

Integer programming, system of linear inequalities.      t      01    +      t      11    +      t      21    ≥  4      t      02    +      t      12    +      t      22    ≥  4      t      10    +      t      11    +      t      12    ≥  4      t      10    +      t      01    +      t      22    ≥  4      t      10    +      t      02    +      t      21    ≥  4      t      20    +      t      21    +      t      22    ≥  4      t      20    +      t      01    +      t      12    ≥  4      t      20    +      t      02    +      t      11    ≥  4There are 8 integer unknowns,       t          i      j        ≥  0  ,  0  ≤  i  ≤  2  ,  0  ≤  j  ≤  2  ,      t      00   is missing. Every unknown is used in exacly 3 inequalitites. The problem is to find solution that minimizes sum of all       t          i      j        3  ×  ∑  ≥  8  ×  4  ∑  ≥  11I have got this solution       t          i      j        =      [                                    2                          2                                      2                          2                          0                                      2                          0                          2                      ]   and I need hint to prove that it optimal. Sum of all unknowns is 12 here. Maybe linear programming method can be used?

Odin Jacobson · Accepted Answer

Let one of       t          i      j       be   2 (if there is   3, using same idea we can even prove that sum is   ≥  13) Let       t      02    =  2.If       t      01    =  0 then       t      10    +      t      22    ≥  4  and       t      11    +      t      21    ≥  4 and       t      12    +      t      20    ≥  4 so sum of all      t          i      j        ≥  2  +  0  +  4  +  4  +  4  =  14If       t      01    =  1 then       t      10    +      t      22    ≥  3 and       t      11    +      t      21    ≥  3 and       t      12    +      t      20    ≥  3 so sum of all      t          i      j        ≥  2  +  1  +  3  +  3  +  3  =  12If       t      01    =  2 then       t      10    +      t      11    +      t      12    ≥  4 and       t      20    +      t      21    +      t      22    ≥  4 so sum of all      t          i      j        ≥  2  +  2  +  4  +  4  =  12So for all cases we have sum of all       t          i      j        ≥  12

Integer programming, system of linear inequalities. t 01 </msub> + t

Answered question

Answer & Explanation

New Questions in Algebra I