0
$\begingroup$

This is a generalization of a subproblem from a past programming competition that I had trouble with.

Given input $6$ positive integers: $$r_1, r_2, r_3, x_1, x_2, x_3 \in \mathbb{Z^+}$$ Produce as output any $6$ non-negative integers: $$\theta_1, \theta_2, \theta_3, \theta_4, \theta_5, \theta_6$$ with a maximum sum, subject to the constraints: $$\theta_1x_1 + \theta_2x_1 + \theta_3x_2 + \theta_4x_2 + \theta_5x_3 + \theta_6x_3 \le r_1 \\ \theta_1x_2 + \theta_2x_3 + \theta_3x_1 + \theta_4x_3 + \theta_5x_1 + \theta_6x_2 \le r_2 \\ \theta_1x_3 + \theta_2x_2 + \theta_3x_3 + \theta_4x_1 + \theta_5x_2 + \theta_6x_1 \le r_3. $$

  • 1
    Isn't this just a [standard linear program](http://en.wikipedia.org/wiki/Linear_programming#Standard_form) of the form: minimize $\mathbf{1}^{T}\Theta$ subject to $X \Theta \le \mathbf{r}$ and $\Theta \ge \mathbf{0}$? (edit: why is `\mathbf` is so ugly in MathJax?)2012-08-17
  • 0
    As the xs are constant you can generalize it to that, but is there a way to take advantage of the fact that the xs repeat in all six permutations to give a simpler solution?2012-08-17
  • 0
    I've changed [tag:algebra] tag to [tag:algebra-precalculus], since we don't use algebra tag anymore, see [meta](http://meta.math.stackexchange.com/questions/473/the-use-of-the-algebra-tag/3081#3081) for details.2012-08-17
  • 0
    $r_1+r_2+r_3 \geq (x_1+x_2+x_3)(\theta_1+\theta_2+\theta_3+\theta_4+\theta_5+\theta_6)$2012-08-17
  • 0
    @AngelaRichardson: Information is lost. Your equation is implied by the triple equation, however the reverse is not true.2012-08-17

0 Answers 0