0

I have the following linear program

MIN Z = 8x1 + 8x2 + 3x3 + 6x4 + 3x5 + 5x6 + 2x7 + x8 + 4x9
subject to
x1 + x2 = 50
-x1 + x3 + x4 + x6 = 0
-x2 - x3 + x7 - x8 + x9 = 0
-x4 + x5 - x7 = -20
-x5 - x6 + x7 + x8 - x9 = -30
x1 <= 12
x2 <= 5
x5 <= 5
x6 <= 9
x7 <= 16
x8 <= 6
x9 <=6

xi>=0

How to get incidence matrix? I tried many times but I don't get a final result.

user2350469
  • 103
  • 2
    Your question is unclear. An incidence matrix can refer to various combinatorial structures and especially to the incidence of lines with points (or edges with vertices). It doesn't make sense to ask how to calculate an incidence matrix given an arbitrary linear program. – hardmath May 12 '17 at 18:55

1 Answers1

0

The LP program you report is actually a minimum cost flow problem. It is defined on a capacited network with 5 nodes (the number of equations) and 9 arcs (the number of variables). The network has one source node (node 1) that supplies 50 units of some commodity and two sink nodes (nodes 4 and 5) requiring 20 and 30 units of commodity. To get the incidence matrix af the underlying network observe that each variable appears only in two equations meaning that is there is just an arc for every pair of nodes. This stated, getting the incidence matrix is straightforward: take a 5x9 matrix and fill it with the coefficients of the variables in the equations. For example the first row of such a matrix is $$1\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0$$

Marcello Sammarra
  • 385