1
$\begingroup$

how to find the minimum value of the given expression $ax+by+cz$ if the constraints are $x,y,z$ are non negative integers that satisfy $x+2y+3z=d$, where $a,b,c,d$ all are positive integers and known beforehand. Or if I substitute one variable from the equation the question can be also asked as How to find minimum non negative value of $Ax+By+C$ given that $x,y$ are non negative integers and A,B are integers?

$\endgroup$
  • $\begingroup$ Likely the constraint should be $x+2y+3z=d$ rather than $x+2y+3x=d$. It would also help to put the given expression in the question itself, rather than just the title. $\endgroup$ – Michael Dec 7 '17 at 17:42
  • $\begingroup$ @Michael edited $\endgroup$ – Ashish Ranjan Dec 7 '17 at 17:43
  • $\begingroup$ What if you remove $x$ from the problem? Can you rewrite in a simpler form without $x$? $\endgroup$ – Michael Dec 7 '17 at 17:46
  • $\begingroup$ @Michael that would be I guess How to find minimum non negative value of $Ax+By+C$ given that x,y are non negative integers and A,B are integers. $\endgroup$ – Ashish Ranjan Dec 7 '17 at 17:57
  • $\begingroup$ I do not follow your above comment. I expected you to substitute $x=d-2y-3z$ everywhere you see an ``$x$'' in the objective function, while carefully considering how the constraint $x \geq 0$ is transformed when you remove the $x$. You can reduce it to minimizing a function $h(y,z)$ subject to constraints on $(y, z)$. $\endgroup$ – Michael Dec 8 '17 at 1:10
1
$\begingroup$

Note that $$ \left\{ \matrix{ ax + by + cz = u \hfill \cr x + 2y + 3z = d \hfill \cr} \right. $$ represents a line in 3D.

You want to find the minimum value of $u$ for which the line contains non-negative integer points.

A vector ($\bf t$) parallel to the line is given by the cross product of the vectors normal to the planes

$$ {\bf t} = \left( {3b - 2c,\;c - 3a,\,\,2a - b} \right) $$

and we can write the parametric equation of the line as $$ \left\{ \matrix{ x = d - 2{{u - ad} \over {b - 2a}} + \left( {3b - 2c} \right)s \hfill \cr y = {{u - ad} \over {b - 2a}} + \left( {c - 3a} \right)s \hfill \cr z = \left( {2a - b} \right)s \hfill \cr} \right. $$ i.e. $$ \left\{ \matrix{ s = {n \over {2a - b}}\quad \left| {\,n \in \mathbb N} \right. \hfill \cr x = d + 2{{u - ad + \left( {3b - 2c} \right)n} \over {2a - b}} \hfill \cr y = {{ - u + ad + \left( {c - 3a} \right)n} \over {2a - b}} \hfill \cr z = n \hfill \cr} \right. $$

Since $a,b,c,d$ are positive integers, and assuming $0<2a-b$ $$ \left\{ \matrix{ \left( {2a - b} \right)x = \left( {2a - b} \right)d + 2\left( {u - ad} \right) + 2\left( {3b - 2c} \right)n \hfill \cr \left( {2a - b} \right)y = - \left( {u - ad} \right) + \left( {c - 3a} \right)n \hfill \cr z = n \hfill \cr} \right. $$

That means that, first of all, $u$ and $n$ must satisfy the congruence relations $$ \left\{ \matrix{ v = u - ad \hfill \cr \left( {2a - b} \right)d + 2v + 2\left( {3b - 2c} \right)n \equiv 0\quad \bmod \left( {2a - b} \right) \hfill \cr - v + \left( {c - 3a} \right)n \equiv 0\quad \bmod \left( {2a - b} \right) \hfill \cr z = n \hfill \cr} \right. $$ which upon some simplifications leads to $$ \left\{ \matrix{ \left( {2c - 3a} \right)n \equiv 0\quad \bmod \left( {2a - b} \right) \hfill \cr v = u - ad \equiv \left( {c - 3a} \right)n \equiv 3cn\quad \bmod \left( {2a - b} \right) \hfill \cr z = n \hfill \cr} \right. $$ Once the solutions to these are found, it will be the case to check them against the original equations to properly take into account the signs, and verify that $x$ and $y$ are positive, and choose the minimum $u$ for that.

Example, in the case $a=b=c=d=1$, the congruences give $$ \left\{ \matrix{ - n \equiv 0\quad \bmod \left( 1 \right) \hfill \cr v = u - 1 \equiv - 2n \equiv 3n\quad \bmod \left( 1 \right) \hfill \cr z = n \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ 0 \le z = n \in Z \hfill \cr u \in Z \hfill \cr} \right. $$ and substituting back $$ \left\{ \matrix{ x = 2u + 2n - 1 \hfill \cr y = 1 - u - 2n \hfill \cr z = n \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ 0 \le x + y = u \hfill \cr u \le 1 - 2n \hfill \cr 0 \le n \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ u_{\,\min } = 1 \hfill \cr n = 0 \hfill \cr x = 1,\;y = 0,z = 0 \hfill \cr} \right. $$

The other approach that you suggested is also viable $$ \eqalign{ & \left\{ \matrix{ ax + by + cz = u \hfill \cr x + 2y + 3z = d \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ 0 \le x = d - 2y - 3z \hfill \cr \left( {2a - b} \right)y + \left( {3a - c} \right)z + \left( {ad - u} \right) = 0 \hfill \cr} \right.\quad \Rightarrow \cr & \Rightarrow \quad \left\{ \matrix{ 0 \le x = d - 2y - 3z \hfill \cr Ay + Bz + C = 0 \hfill \cr} \right. \cr} $$

For the resolution of the 2D diophantine equation in the 2nd line, please refer to this related post.
The solutions to it shall then respect the inequality in the 1st line.

From the cited post you get that your problem is, in general, related to:
- the Modular Inverse operation;
- the Popoviciu's Theorem;
- the Frobenius Coin Exchange problem.
and that, for some particular values of $a,b,c,d$, although non-negative, you might even have no solution, for whichever value of $u$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.