For $a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9$ are non-negative integer number and satisfied:
$\begin{align*} a_1+a_3-a_6=K_1\\ a_2+a_4-a_8=K_2\\ a_3+a_4+2a_5+a_6+a_8=K_3\\ a_4+a_5+a_6+a_8+a_9=K_4\\ a_3+a_5+a_6+a_7+a_8=K_5\\ a_1+a_2+a_3+a_4+a_7+a_9=K_6 \end{align*}$
- With $K_1,K_2,K_3,K_4,K_5,K_6,(K_i\in \mathbb{Z})$ are given and $-1000\le K_1,K_2,K_3\le 1000$ and $0\le K_4,K_4,K_6\le 1000$.
+Find maximize of $a_1+a_2+a_3+a_4+a_5+a_6+a_7+a_8+a_9$.
This is my try:
After a few transformations, I get: $a_6+a_7+a_8+a_9=\frac{K_4+K_5+K_6-(K_1+K_2+K_3)}{2}$.
So, now I just need compute the maximize of $a_1+a_2+a_3+a_4+a_5$. But i can't do it!
Best Answer
Since $a_1,a_2,\ldots,a_9$ are nonnegative inegers, it is necessary that $$0\leq K_3\leq \min\{K_1+K_2+2K_4,K_1+K_2+2K_5,K_1+2K_4,K_2+2K_5,K_4+K_5\}\,,$$ $$K_1+\min\{K_3,K_4,K_5\}\geq 0\,,$$ $$K_2+\min\{K_3,K_4,K_5\}\geq 0\,,$$ and $$K_1+K_2+\min\{K_3,K_4,K_5\}\geq 0\,.$$ We shall assume these inequalities implicitly throughout this answer. Because $$K_6=K_1+K_2-K_3+K_4+K_5\,,$$ we can ignore $K_6$ for the most part except that the constraints $0\leq K_6\leq 1000$ means $$0\leq K_1+K_2-K_3+K_4+K_5\leq 1000\,.$$ However, this is just another constraint on the parameters $K_1$, $K_2$, $K_3$, $K_4$, and $K_5$.
We have $$F:=\sum_{i=1}^9\,a_i\leq a_1+a_2+2a_3+2a_4+2a_5+a_6+a_7+a_8+a_9=K_1+K_2+K_4+K_5\,.$$ The equality holds if and only if $a_3=a_4=a_5=0$. This implies $$a_1-a_6=K_1\,,$$ $$a_2-a_8=K_2\,,$$ $$a_6+a_8=K_3\,,$$ $$a_6+a_8+a_9=K_4\,,$$ and $$a_6+a_7+a_8=K_5\,.$$ Thus, $a_9=K_4-K_3$, $a_8=K_3-a_6$, $a_7=K_5-K_3$, $a_2=K_2+K_3-a_6$ and $a_1=K_1+a_6$. This is possible iff $K_3\leq \min\{K_4,K_5\}$, where one solution is $$\begin{align}\big(a_1&,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9\big)\\&=\small\big(K_1+\min\{K_2+K_3,K_3\},K_2+K_3-\min\{K_2+K_3,K_3\},0,0,0,\min\{K_2+K_3,K_3\},K_5-K_3,K_3-\min\{K_2+K_3,K_3\},K_4-K_3\big)\,.\end{align}$$
Now we investigate the case $K_3>\min\{K_4,K_5\}$. Since we have $K_3\leq K_4+K_5$, there are three situations: $$K_4=\min\{K_3,K_4,K_5\}\text{ or }K_5=\min\{K_3,K_4,K_5\}\,.$$
Observe that $$F\leq a_1+a_2+a_3+2a_4+a_5+a_6+a_7+a_8+2a_9= K_1+K_2-K_3+2K_4+K_5$$ where the equality occurs iff $a_4=a_9=0$. If $K_4\leq K_5<K_3$, then we may take $a_4=a_7=a_9=0$, and get a solution $$\begin{align}\big(a_1&,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9\big)\\&=\small\big(K_1+K_4-K_5+\max\{0,-K_1-K_4+K_5\},K_2-K_3+K_4+K_5-\max\{0,-K_1-K_4+K_5\},K_5-K_4,0,K_3-K_5,\max\{0,-K_1-K_4+K_5\},0,-K_3+K_4+K_5-\max\{0,-K_1-K_4+K_5\},0\big)\,.\end{align}$$ If $K_4<K_3\leq K_5$, then we may take $a_4=a_5=a_9=0$, and get a solution $$\begin{align}\big(a_1&,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9\big)\\&=\small\big(K_1-K_3+K_4+\max\{0,-K_1+K_3-K_4\},0,K_2+K_4-\max\{0,-K_1+K_3-K_4\},K_3-K_4,0,0,\max\{0,-K_1+K_3-K_4\},K_5-K_3,K_4-\max\{0,-K_1+K_3-K_4\},0\big)\,.\end{align}$$
Next, observe that $$F\leq a_1+a_2+2a_3+a_4+a_5+a_6+2a_7+a_8+a_9= K_1+K_2-K_3+K_4+2K_5$$ where the equality occurs iff $a_3=a_7=0$. If $K_5=\min\{K_3,K_4,K_5\}$, then we may take $a_3=a_5=a_7=0$, and get a solution $$\begin{align}\big(a_1&,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9\big)\\&=\small\big(K_1+K_5-\max\{0,-K_2+K_3-K_5\},K_2-K_3+K_5+\max\{0,-K_2+K_3-K_5\},0,K_3-K_5,0,K_5-\max\{0,-K_2+K_3-K_5\},0,\max\{0,-K_2+K_3-K_5\},K_4-K_5\big)\,.\end{align}$$
In conclusion, the maximum value of $F$ is $$F_\text{max}=\left\{ \begin{array}{ll} K_1+K_2+K_4+K_5&\text{if }K_3=\min\{K_3,K_4,K_5\}\,,\\ K_1+K_2-K_3+2K_4+K_5&\text{if }K_4=\min\{K_3,K_4,K_5\}\,,\\ K_1+K_2-K_3+K_4+2K_5&\text{if }K_5=\min\{K_3,K_4,K_5\}\,. \end{array} \right.$$
Here, we are determining the minimum possible value of $F$. Note that $$F\geq a_1+a_2+a_3+a_4+a_7+a_9=K_1+K_2-K_3+K_4+K_5\,,$$ where the equality case happens when $a_5=a_6=a_8=0$. That is, $$a_1+a_3=K_1$$ $$a_2+a_4=K_2$$ $$a_3+a_4=K_3$$ $$a_4+a_9=K_4$$ and $$a_3+a_7=K_5$$ This requires $K_1\geq 0$, $K_2\geq 0$, and $K_3\leq \min\{K_1+K_2,K_1+K_4,K_2+K_5,K_4+K_5\}$. A solution is $$\begin{align}\big(a_1&,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9\big)\\&=\small\big(K_1-\min\{K_1,K_3,K_5\},K_2-K_3+\min\{K_1,K_3,K_5\},\min\{K_1,K_3,K_5\},K_3-\min\{K_1,K_3,K_5\},0,0,K_5-\min\{K_1,K_3,K_5\},0,K_4-K_3+\min\{K_1,K_3,K_5\}\big)\,.\end{align}$$ There are other cases to deal with but I am exhausted.