1

Assume that intergers $m$ and $n$ satisfy $2|m|+3|n-1|\leq 7$. $m+n$ is maximum when $(m,n) = (3,?), (?,?)$ and its maximum value is $?$

given the above question the first thing i tried was calculating the intervals for each variable like this:

$2|m| \leq 7 \therefore m \in [-\frac{7}{2},\frac{7}{2}]$

$3|n-1| \leq 7 \therefore n \in [-\frac{4}{3},\frac{10}{3}]$

and since the exercise is telling me that the maximum is reached when $m=3$

$2|3|+3|n-1|\leq 7 \therefore 7 \geq 3|n-1| + 6 \therefore n \in [-\frac{1}{3},\frac{8}{3}]$

The next thing i want to do is make a graph but i got stuck in this part since i newbie in linear programming, any advice or material in this topic?

Carlos
  • 87
  • note: i mentioned the graph because of this video – Carlos May 16 '22 at 15:45
  • 1
    $m$ and $n$ are integers, hence there are only finitely many pairs $(m,n)$ satisfying the inequality, and you can easily list them all, starting from the intervalls you found. For each pair is then easy to compute $m+n$ and finally pick the maximum – Pomponazzo May 16 '22 at 16:11
  • I think drawing a coordinate grid could be illuminating. You should try that. – Arthur May 16 '22 at 16:13

2 Answers2

1

Assume that integers $m$ and $n$ satisfy $2|m|+3|n−1|≤7$. $m+n$ is maximum when $(m,n)=(3,?),(?,?)$ and its maximum value is $?$

We can turn the following problem into an LP model like such:

$$\max z = m+n$$ $$s.t.\quad 2m \le 7$$ $$2m \ge -7$$ $$3(n-1)\le7$$ $$3(n-1)\ge-7$$ $$m,n\in\Bbb Z$$

The linearly relaxed, feasible region of this model will look like so: enter image description here

Then, we can add in all the integer points that exist within the feasible region like so (which is the real feasible region of the above model):

enter image description here

Since we know $m=3$, we can isolate all the points where that is true: enter image description here

Which are the following points: $$\left(3,-1\right),\left(3,0\right),\left(3,1\right),\left(3,2\right),\left(3,3\right)$$

From here, since we’re looking for a point to satisfy the original $2||+3|−1|≤7 $ constraint, we can conclude that biggest, valid point that maximizes $z=m+n$ is the point $\left(3,1\right)$.

Miss Mae
  • 1,576
0

I have renamed your variables as $x$ and $y$ to match the linked Desmos plot.

Introduce (nonnegative) variables $u$ and $v$ to represent the absolute values. The resulting linear problem is to maximize $m+n$ subject to \begin{align} 2u+3v &\le 7 \\ u &\ge x \\ u &\ge -x \\ v &\ge y-1 \\ v &\ge -(y-1) \\ x &\in \mathbb{Z} \\ y &\in \mathbb{Z} \end{align} The two optimal solutions turn out to be $(x,y,u,v)=(3,1,3,1)$ and $(x,y,u,v)=(2,2,2,2)$. See https://www.desmos.com/calculator/x2w97ng3up

RobPratt
  • 45,619