I've been having trouble getting started with this problem.

Suppose $x_1,x_2,x_3$ are integers $\geq 0$, satisfying $$21.7x_1-18.2x_2-19.4x_3=5.3$$

Then show $$7x_1+8x_2+6x_3=3+10z_1$$.

(*edit*)where $x_1,x_2,x_3,z_1$ are all integers $\geq 0$

This is from Joel Franklin's Methods of Mathematical Economics page 131.

my attempt: I multiplied the constraint by 10 to get $217x_1-182x_2-194x_3=53$. I found my first basic optimal solution with $x_1=53/217$. This left me with Gomory cut with

$\frac{35}{217} x_2+ \frac{23}{217} x_3 - z_1= \frac{53}{217}$ (where the inverse of inverse of basis matrix was 1/217, and I had to take the positive complements of -182/217 and -194/217 for $x_2,x_3$) as an added constraint.

I am not sure what to do next. Any help would be appreciated. Thanks.

  • $\begingroup$ What is $z_1$ here? $\endgroup$ – Kieran Cooney Oct 28 '13 at 5:06
  • $\begingroup$ @JosebYosebYi: When you multiplied by $10$, shouldn't you have $217$? $\endgroup$ – Amzoti Oct 28 '13 at 5:08
  • $\begingroup$ @Amzoti you're correct I changed it. $\endgroup$ – Joseb Yoseb Yi Oct 28 '13 at 5:15
  • 1
    $\begingroup$ I think you need to explain Gomory cut and what you mean by $z_1$. $\endgroup$ – Amzoti Oct 28 '13 at 5:15
  • $\begingroup$ @KieranCooney It's part of a new constraint -- I think the idea is that since we are considering only integer solutions, the sum of the fractional parts of $x_2$ and $x_3$ should be equal to the sum of an integer ($z_1$) and the fractional part 53/217. $\endgroup$ – Joseb Yoseb Yi Oct 28 '13 at 5:18

Multiply the first equation by $10$ as you already did and from this subtract the second equation you need to show. Simplify and rearrange to express $z_1$ in terms of $x_1,x_2,x_3$ and constants. It is easy to show that $z_1$ is a sum of products of integers, and hence itself an integer. The part $z_1\ge 0$ follows from the second equation.

  • $\begingroup$ do you mind clarifying what you mean by "subtract the second equation you need to show". Thanks for the help. $\endgroup$ – Joseb Yoseb Yi Oct 28 '13 at 19:22
  • $\begingroup$ i was dumb haha thanks! figured it out $\endgroup$ – Joseb Yoseb Yi Oct 28 '13 at 21:29

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.