From: "R.G. Vickson" Subject: Re: Simultanious Equations with Mutliple solutions and Less Eq's than Date: Mon, 27 Sep 1999 16:37:25 -0400 Newsgroups: sci.math Keywords: Hitchcock-Koopmans transportation problem robjames@my-deja.com wrote: > HI, > > Problem: > I have an unknown 4x4 'grid' of integer values. > What I do have is the column and row sums. This a classical 4x4 Hitchcock-Koopmans transportation problem. Think of it this way: you have 4 plants (the rows) and 4 warehouses (the columns). If x_{ij} is the amount shipped from plant i to warehouse j, the ith row sum is the amount shipped out of plant i while the j th column sum is the amount shipped into warehouse j. Presumably, you have specified these in advance (assuming sum(r_i) = sum)c_j)). It is a fact about such systems that if the r_i and c_j are all integers, then any so-called BASIC solution has integer-values x_{ij} values. In this case, a basic solution in which 2n-1 variables are solved for as functions of the remaining n^2-(2n-1) variables, then all the latter are set to zero (n=4 in your proboem) Consult any introductory textbook on Operations Research or Linear Programming to learn more about such problems. (The classical problem is to determine a shipping pattern--the x_{ij}--so as to minimize some total cost function of the form \sum_i \sum_j c_{ij} x_{ij} with specified cost matrix c_{ij}.) > > > My plan was to turn this into a simultanious equation problem my lining > up the rows into 8 equations of 16 unknowns. > > This will of course mean that there are mutliple solutions based on the > 8 (4 row + 4 column) equation values. I want these solutions! > e.g > > a b c d r1 > e f g h r2 > i j k l r3 > m n o p r4 > -- -- -- -- > c1 c2 c3 c4 > > becomes > > 1a + 1b + 1c + 1d + 0e +0f +og +... 0p = r1 > 1a + 0b +0c +0d + 1e + 0f.... = c1 > > What methods can I use to generate the solutions ? > > Rob J. > > Sent via Deja.com http://www.deja.com/ > Before you buy.