Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Yes that's it -- but I'm afraid I don't now how to solve linear programs -- please could you explain? –  user7694 Mar 2 '11 at 13:39
    
Sorry, but I think "how to solve linear programs" is really beyond the scope of this board. I can only suggest finding a book (Convex Optimization by Boyd is good) or starting with wiki (en.wikipedia.org/wiki/Linear_programming). If you know how to use MATLAB, there are built in solvers (linprog). –  1yen Mar 2 '11 at 13:52
    
Okay, I'll read up. Thanks for the answer! –  user7694 Mar 2 '11 at 13:52
    
A good book is Dantiz and Thapa's "Linear Programming". –  Dilawar Mar 2 '11 at 14:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.