Question about problem linear programming math modelingConsider points A(4.7,−4.1,−1.5),B(−0.4,−2.4,1.9),C(−0.3,−2.1,−6.5) and D(2.7,−3.6,4.0). How to discover if segment AB has intersection different of zero with the segment CD? Formulate this problem as a linear programming problem.

Question

hocelwsmjc · Accepted Answer

Step 1As I suggested above, it certainly seems to me that linear programming is a poor way to go about this. Nevertheless, this is an LP model that would accomplish this:                    minimize                    0                            subject to                    4.7                  t          1                −        0.4        (        1        −                  t          1                )        =        −        0.3                  t          2                +        2.7        (        1        −                  t          2                )                                  −        4.1                  t          1                −        2.4        (        1        −                  t          1                )        =        −        2.1                  t          2                −        3.6        (        1        −                  t          2                )                                  −        1.5                  t          1                +        1.9        (        1        −                  t          1                )        =        −        6.5                  t          2                +        4.0        (        1        −                  t          2                )                                  0        ≤                  t          1                ,                  t          2                ≤        1            This is a feasibility problem: there&#039;s no objective to minimize, so I put a dummy objective of 0, as is common practice. That doesn&#039;t make the problem trivial: the linear programming algorithm must still determine valid values of       t    1    ,      t    2   or conclude that the model is infeasible.      t    1   and       t    2   represent the relative location on each segment:On AB,       t    1    =  1 corresponds to A,       t    1    =  0 corresponds to B;On CD,       t    2    =  1 corresponds to C,       t    2    =  0 corresponds to D.So for instance, if the solution is       t    1    =      t    2    =  0.5, these segments intersect right at their midpoint.Step 2But this is like cracking open a peanut with a sledgehammer. Here&#039;s what I would do instead. First, solve the first two equations for       t    1   and       t    2  .1. Solve the first two equations for       t    1   and       t    2  2. If       t    1    ∉  [  0  ,  1  ] or       t    2    ∉  [  0  ,  1  ], STOP; there is no intersection.3. Check if the third equation is satisfied for this value of       t    1   and       t    2  . If it is, then this is your answer; if not, then there is no intersection.No need for a linear program at all; just a 2x2 linear system and a few checks. For general A,B,C,D, you&#039;ll need more checks to handle situations like collinearity. But in this case, you get   (  t  1  ,  t  2  )  =  (  0.4118  ,  −  0.3333  ) just like you would with the LP.

Answered question

Answer & Explanation

New Questions in Algebra II