Q: Question about problem linear programming math modeling Consider 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.

A: As 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:
\begin{array}{ll}
\text{minimize} & 0 \\ \text{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 \leq t_1, t_2 \leq 1
\end{array} 
This is a feasibility problem: there's no objective to minimize, so I put a dummy objective of $0$, as is common practice. That doesn'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.
But this is like cracking open a peanut with a sledgehammer. Here's what I would do instead. First, solve the first two equations for $t_1$ and $t_2$. 


*

*Solve the first two equations for $t_1$ and $t_2$.

*If $t_1\not\in[0,1]$ or $t_2\not\in[0,1]$, STOP; there is no intersection.

*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'll need more checks to handle situations like collinearity. But in this case, you get $(t1,t2)=(0.4118,-0.3333)$ just like you would with the LP.
