2
$\begingroup$

Given a problem like the following:

A startup want to build talking washing machines spending the least possible. There are three ways of building them: manually, semi-automatically and automatically. The manual production demands 1 minute of qualified work, 40 minutes of non-qualified work and three minutes of assemblage. The work times are 4, 30 and 2 minutos for the semi-automatic method and 8, 20 and 4 minutos for the fully automatic method. A startup has a pool of 4500 minutes of qualified work, 36000 minutos of non-qualified work and 2700 minutos of assembly. The costs of the production are 70, 80 and 85 euros for the manual, semi-automatic and automatic methods.

There are constraints regarding the number of machines to be produced (999) and the capacity of the factory

I understand how to set up a linear program like this:

minimize $f(x) = 70x_1 + 80x_2 + 85x_3 \ s.t.$

$x_1 + x_2 + x_3 = 999$

$x_1 + 4x_2 + 8x_3 \leq 4500$

$40x_1 + 30x_2 + 20x_3 \leq 36000$

$3x_1 + 2x_2 + 4x_3 \leq 2700$

$x \geq 0$

However, I am confused on how to set up the constraints for a linear program when all you are given is a payout matrix for a 2 player zero sum game. Given the following matrix (row player payouts listed):

\begin{bmatrix} 1 & -1\\ -1 & 1 \end{bmatrix}

I can get to this setup for the row player:

minimize $z \ s.t.$

$x_1 - x_2 = a$

$-x_1 + x_2 = b$

$x_1 + x_2 = 1$

$x_1, x_2 \geq 0$

So $a$ and $b$ are what I'm confused about finding here. I'm wondering how to find these values given this type of input in a general sense, not just for this problem.

$\endgroup$
8
  • 1
    $\begingroup$ Just to check, do you understand the meaning of $z$ in my answer below? Does the LP make sense? $\endgroup$
    – Théophile
    Mar 1, 2017 at 5:47
  • $\begingroup$ Yes, it helped my understanding a lot. Although it turns out I actually need to maximize $z$ instead of minimize. To make this switch, I changed just changed the objective at the top from maximize to minimize. Will this be enough or am I missing something else? Thank you for your response by the way. $\endgroup$
    – UBears
    Mar 1, 2017 at 21:22
  • 1
    $\begingroup$ You're welcome! Note that you can't just switch from maximize to minimize. In that case, as written, $z$ would be unbounded. In the LP that I wrote below, $z$ represents an upper bound on the row player's winnings. The column player is trying to push down the upper bound as much as possible, effectively guaranteeing that the row player can never win more than some constant (the solution to the LP). If you want a maximization problem, write the transpose of the matrix. You would maximize $w$ according to similar constraints, but it would be a lower bound on the column player's winnings. $\endgroup$
    – Théophile
    Mar 1, 2017 at 21:56
  • 1
    $\begingroup$ In other words, maximize $w$ s.t. $$\begin{array}{c} y_1 &- &y_2 &\ge &w\\ -y_1 &+ &y_2 &\ge &w\\ y_1 &+ &y_2 &= &1\\ \end{array}$$ But note that the equations look similar to the original only because your payoff matrix is symmetrical! (i.e., the matrix is its own transpose.) $\endgroup$
    – Théophile
    Mar 1, 2017 at 21:58
  • $\begingroup$ So to bother you one more time, would the dual of this LP be maximize $-z$ s.t. $[x_1 - x_2 \leq z] [-x_1 + x_2 \leq z] [x_1 + x_2 = 1]$ (essentially what you had written in your initial answer) $\endgroup$
    – UBears
    Mar 2, 2017 at 2:05

1 Answer 1

Reset to default
1
$\begingroup$

Your setup is perhaps confusing because it's not clear what $a,b,z$ represent, and there's nothing relating them to each other or constraining them. As it stands, you could pick any feasible solution (e.g., $(x_1,x_2,a,b) = (1,0,1,-1)$), and then an arbitrarily low value for $z$. This shows that the problem is unbounded, and isn't doing what you want it to do.

Instead try:

$$\text{minimize } z \text{ s.t.}$$

$$\begin{array}{c} x_1 &- &x_2 &\le &z\\ -x_1 &+ &x_2 &\le &z\\ x_1 &+ &x_2 &= &1\\ \end{array}$$

$$x_1, x_2 \geq 0$$

Now take the instances of $z$ to the left-hand side.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .