Could someone please explain how to solve such task by linear programming:
Let's say there is a starting point $A$ and two end points $B$ and $C$. $A$ is connected to $B$ and $C$ and the connections are weighted by different factors $a_i$.
Two objects $o_1$ and $o_2$ have to alternatively move to $B$ or $C$ starting at $A$. $o_1$ and $o_2$ have different cost factors $c_j$ per $a_i$, so that for example $c_1a_1 $$\neq$$c_2a_1$.
The goal is to determine which object should take which connection (with minimal costs) by linear programming.
Let $x_1^{AB}$ be a binary variable that equals $1$ if and only if $o_1$ goes from $A$ to $B$, $x_1^{AC}$ be a binary variable that equals $1$ if and only if $o_1$ goes from $A$ to $C$, $x_2^{AB}$ be a binary variable that equals $1$ if and only if $o_2$ goes from $A$ to $B$, and $x_2^{AC}$ be a binary variable that equals $1$ if and only if $o_2$ goes from $A$ to $C$.
You want to minimize $$ c_1a_{AB}x_1^{AB}+c_1a_{AC}x_1^{AC}+c_2a_{AB}x_2^{AB}+c_2a_{AC}x_2^{AC} $$ subject to $$ x_1^{AB}+x_1^{AC}=1\\ x_2^{AB}+x_2^{AC}=1\\ x_1^{AB},x_1^{AC},x_2^{AB},x_2^{AC}\in \{0,1\}\\ $$
You can simplify the problem to minimize $$ c_1a_{AB}x_1^{AB}+c_1a_{AC}(1-x_1^{AB})+c_2a_{AB}x_2^{AB}+c_2a_{AC}(1-x_2^{AB}) $$ subject to $$ x_1^{AB},x_2^{AB}\in \{0,1\}\\ $$ i.e., $$ \boxed{\min\limits_{x_1^{AB},x_2^{AB}\in \{0,1\}}(c_1a_{AB}-c_1a_{AC})x_1^{AB}+(c_2a_{AB}-c_2a_{AC})x_2^{AB} } $$
The answer is trivial:
if $c_1a_{AB}-c_1a_{AC}\le 0$, $x_1^{AB}=1$, and if $c_2a_{AB}-c_2a_{AC}\le 0$, $x_2^{AB}=1$.