Linear programming with a matrix of decision variables [closed]

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Is it possible to use linear programming when the decision variables are not simply a vector? For example, say I have $n$ countries and $m$ different potential charities I can donate to. The benefits per dollar spent are different for each charity-country pair, and are stored in the $m\times n$ matrix $b$ (if the charity $i$ does not exist in country $j$ then $b_{ij} = 0$). Assume I have a budget of $B$, $x_{ij}$ denotes how much money I donate to charity $i$ in country $j$ and I want to maximize the benefit.

I can formulate this problem as:

$\max_{x} \sum_i \sum_j b_{ij} x_{ij}$

subject to $\sum_i\sum_j x_{ij} \leq B$

[Assume obviously that I will add other constraints along the way (certain amounts donated in each country, maximum donated to each different charity etc), I am just setting this up trivially to begin with to determine if it is doable.]

So rather than just setting up the simplex tableau with the vector $(x_1, x_2, ..., x_l)$ as the bottom row, I actually have an $m \times n$ matrix of decision variables. Is this solvable using linear programming? I am not interested in using a solver, I want to understand the basics of how a problem like this would be solved.

-

1
en.wikipedia.org/wiki/… – Federico Poloni May 9 2011 at 8:29
Paul, I'm afraid this question is outside the scope of MathOverflow. Federico Poloni has answered your question, but if you want a more elaborate explanation, I suggest you ask at math.stackexchange.com – S. Carnahan♦ May 10 2011 at 21:18
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 15, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9169601798057556, "perplexity_flag": "middle"}