2
$\begingroup$

Say I have three constants a, b and c (all > 0) and three variables x, y and z (all >= 0). I want to find values for x, y, z which maximise the lowest of the following:

ax - y - z -x + by - z -x -y + cz 

How can I find these values?

EDIT: just corrected expressions -- variables and constants were wrong way around

EDIT: x, y and z all must be >=0

1 Answers 1

1

If I understand, you are trying to solve a minimax (or rather, maximin) type problem. Formally, your statement is

$\max \min \{ax-y-z, -x+by-z, -x-y+cz\}$, and you have not listed any other constraints.

A standard trick is to reformulate this problem as a constrained maximization problem. We can do this by introducing an auxiliary variable $\gamma$,

$\max_{\gamma, x,y,z} \gamma$ subject to $ \gamma \leq f_i(x,y,z)$ for $i=1,2,3$

where $f_i(x,y,z)$ corresponds to each of the linear functions you stated.

This is nothing but a linear program now, which can be solved using your favorite method.

  • 0
    A good book is Dantiz and Thapa's "Linear Programming".2011-03-02