Dynamical system approach to solving linear programming problems and applications in economic modelling
A class of dynamycal systems on symplectic manifolds solving linear programming problems is described. The structure of orbit space is analyzed in the framework of the Marsden – Weinstein reduction scheme. Some examples having applications in modern macro-economical modelling are treated in deta...
Gespeichert in:
| Datum: | 2002 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут математики НАН України
2002
|
| Schriftenreihe: | Нелінійні коливання |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/174921 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Dynamical system approach to solving linear programming problems and applications in economic modelling / I.P. Tverdokhlib, O.A. Prykarpatsky // Нелінійні коливання. — 2002. — Т. 5, № 1. — С. 117-122. — Бібліогр.: 7 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-174921 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1749212021-01-30T01:27:16Z Dynamical system approach to solving linear programming problems and applications in economic modelling Tverdokhlib, I.P. Prykarpatsky, O.A. A class of dynamycal systems on symplectic manifolds solving linear programming problems is described. The structure of orbit space is analyzed in the framework of the Marsden – Weinstein reduction scheme. Some examples having applications in modern macro-economical modelling are treated in detail. Описано клас динамiчних систем на симплектичному многовидi, що розв’язують задачi лiнiйного програмування. Проведено аналiз простору орбiт з точки зору принципу редукцiї Марсдена i Вайнштейна. Детально розглянуто приклади застосувань у моделюваннi сучасних макроекономiчних процесiв. 2002 Article Dynamical system approach to solving linear programming problems and applications in economic modelling / I.P. Tverdokhlib, O.A. Prykarpatsky // Нелінійні коливання. — 2002. — Т. 5, № 1. — С. 117-122. — Бібліогр.: 7 назв. — англ. 1562-3076 http://dspace.nbuv.gov.ua/handle/123456789/174921 517 . 938 + 517 . 977 . 55 en Нелінійні коливання Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
A class of dynamycal systems on symplectic manifolds solving linear programming problems is described.
The structure of orbit space is analyzed in the framework of the Marsden – Weinstein reduction scheme.
Some examples having applications in modern macro-economical modelling are treated in detail. |
| format |
Article |
| author |
Tverdokhlib, I.P. Prykarpatsky, O.A. |
| spellingShingle |
Tverdokhlib, I.P. Prykarpatsky, O.A. Dynamical system approach to solving linear programming problems and applications in economic modelling Нелінійні коливання |
| author_facet |
Tverdokhlib, I.P. Prykarpatsky, O.A. |
| author_sort |
Tverdokhlib, I.P. |
| title |
Dynamical system approach to solving linear programming problems and applications in economic modelling |
| title_short |
Dynamical system approach to solving linear programming problems and applications in economic modelling |
| title_full |
Dynamical system approach to solving linear programming problems and applications in economic modelling |
| title_fullStr |
Dynamical system approach to solving linear programming problems and applications in economic modelling |
| title_full_unstemmed |
Dynamical system approach to solving linear programming problems and applications in economic modelling |
| title_sort |
dynamical system approach to solving linear programming problems and applications in economic modelling |
| publisher |
Інститут математики НАН України |
| publishDate |
2002 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/174921 |
| citation_txt |
Dynamical system approach to solving linear programming problems and applications in economic modelling / I.P. Tverdokhlib, O.A. Prykarpatsky // Нелінійні коливання. — 2002. — Т. 5, № 1. — С. 117-122. — Бібліогр.: 7 назв. — англ. |
| series |
Нелінійні коливання |
| work_keys_str_mv |
AT tverdokhlibip dynamicalsystemapproachtosolvinglinearprogrammingproblemsandapplicationsineconomicmodelling AT prykarpatskyoa dynamicalsystemapproachtosolvinglinearprogrammingproblemsandapplicationsineconomicmodelling |
| first_indexed |
2025-07-15T12:03:36Z |
| last_indexed |
2025-07-15T12:03:36Z |
| _version_ |
1837714392198676480 |
| fulltext |
UDC 517 . 938 + 517 . 977 . 55
DYNAMICAL SYSTEM APPROACH TO SOLVING LINEAR
PROGRAMMING PROBLEMS AND APPLICATIONS
IN ECONOMICS MODELLING
ПIДХIД ДО РОЗВ’ЯЗАННЯ ЗАДАЧ ЛIНIЙНОГО ПРОГРАМУВАННЯ
З ТОЧКИ ЗОРУ ДИНАМIЧНИХ СИСТЕМ
ТА ЗАСТОСУВАННЯ В МОДЕЛЮВАННI ЕКОНОМIЧНИХ ПРОЦЕСIВ
I. P. Tverdokhlib
I. Franko National University, L’viv, Ukraine
O. A. Prykarpats’ky
University of Koln, Germany
A class of dynamycal systems on symplectic manifolds solving linear programming problems is described.
The structure of orbit space is analyzed in the framework of the Marsden – Weinstein reduction scheme.
Some examples having applications in modern macro-economical modelling are treated in detail.
Описано клас динамiчних систем на симплектичному многовидi, що розв’язують задачi лiнiйно-
го програмування. Проведено аналiз простору орбiт з точки зору принципу редукцiї Марсдена
i Вайнштейна. Детально розглянуто приклади застосувань у моделюваннi сучасних макроеко-
номiчних процесiв.
1. Introduction. The methods of the theory of dynamical systems were effectively applied for
the first time in [1], where a new polynomial-time algorithm for linear programming was devised
and approved further by numerical experiments. Amongst very important problems of linear
programming we chose for studying here the one described below.
Let ai ∈ Rn, i = 1,m, be linearly independent constant vectors. Consider functions fi ∈
∈ D(R2n), fi(x, c) := 〈c, ai〉, i = 1,m, where u := (x, c) ∈ Rn×Rn is a given vector and 〈·, ·〉 is
the usual scalar product on Rn. It is assumed further that {fi, fj} = 0 for all i, j = 1,m, where
{·, ·} is a Poisson structure on R2n, to be specified in detail in what follows, related naturally with
some sympletic structure ω(2) ∈ Λ2(R2n) on R2n. Denote also by Yi : R2n → T (R2n), i = 1,m,
the corresponding Hamiltonian vector fields equal to {fi, u}, i = 1,m, commuting on R2n and
generating orbit spaces related with polyhedra arising here naturally via a construction specified
below.
Consider a polyhedron P ⊂ Rn which is described as
〈ai, x〉 = bi, xj ≥ 0, (1)
for i = 1,m, j = 1, n. Take now x ∈ Rn and denote the set {j ∈ [1, n] : xj = 0} by J(x). A
point x ∈ P is called an extreme point of P if the following implication holds:
{y ∈ Rn : 〈ai, y〉 = 0, i = 1,m} ∧ {yj = 0 : j ∈ J(x)} =⇒ y = 0. (2)
c© I. P. Tverdokhlib, O. A. Prykarpats’ky, 2002
ISSN 1562-3076. Нелiнiйнi коливання, 2002, т . 5, N◦ 1 117
118 I.P. TVERDOKHLIB, O.A. PRYKARPATS’KY
The set of extreme points will be denoted by E(P ). We shall also call a point x ∈ E(P ) simple
if the vectors
aj , j = 1,m, together with basis vectors ej , j ∈ J(x), (3)
form a basis in Rn. A polyhedron P defined by (2) and (3) is said to be simple if each of its
extreme points is simple. The following lemmas [2] are dealing with the critical set E(p).
Lemma 1. Given x ∈ P, where P is a simple compact polyhedron. Then there always exists
p ∈ E(p) such that J(x) ⊂ J(p).
Lemma 2. Let x, y ∈ M = Φ−1(P ), where Rn 3 x Φ−→ {1/2x2
j : j = 1, n} ∈ Rn, be such
that J(x) ⊂ J(y) and Φ(y) ∈ E(P ). Then the vectors D(x)ai, i = 1,m, and ej , j ∈ J(y), form
a basis in Rn, where D(x) = diag {xj : j = 1, n}.
Now the linear programming problem in the polyhedron P can be formulated as follows:
find x ∈ M such that
max
x∈M
gc(x) = gc(x) (4)
under the conditions
〈ai,Φ(x)〉 = bi, i = 1,m, (5)
where gc := 〈c,Φ(x)〉, x ∈ Rn. For its analysis, we shall apply methods of the Marsden –
Weinstein reduction theory [3].
2. Reduction algorithm and linear programming. Subject to the Poisson bracket {·, ·} on
R2n, conditions (1) can be considered evidently as constraints of first class [3, 4]. The latter, in
particular, means that there exists a reduced Poisson bracket {·, ·}r on the orbit space M̄c :=
:= R2n/Tm, Tm is a Lie group isomorphic to an Abelian Lie group generated by the mutually
commuting complete vector fields Yi : R2n → T (R2n), i = 1,m, defined before. With respect
to this Poisson bracket {·, ·}r on M̄c, one can consider the vector field K̄c : M̄c → T (M̄c)
generated by the Hamiltonian function Hc := 〈c, c〉/2 reduced on M̄c and study all of its
asymptotically stable limit points. The theorems following below make it possible to asso-
ciate these limit points with points x ∈ M solving the linear programming problem posed
above. Consider the distribution Dc : R2n → T (R2n) spanned by the Hamiltonian vector fields
Kj(u) = {Hj , u},
where u ∈ R2n and by definition,
Hj = 〈aj ,Φ(x)〉, j = 1,m,
which is evidently integrable on R2n. Its maximal integral submanifolds are naturally imbedded
into R2n and are usually called symplectic leaves of the bracket {·, ·} with respect to which we
can build the reduced manifold M c = R2n/Dc.
ISSN 1562-3076. Нелiнiйнi коливання, 2002, т . 5, N◦ 1
DYNAMICAL SYSTEM APPROACH TO SOLVING LINEAR PROGRAMMING PROBLEMS . . . 119
Construct now the second distribution Db : Rn → T (Rn) spanned by gradient vector fields
∇gj : Rn → T (Rn), gj(x) := 〈aj ,Φ(x)〉, j = 1,m. Then evidently the reduced space
M b := Rn/Db is diffeomorphic to M = Φ−1(P ) and one can define the reduction mapping
rb : Rn → M b.
Choose now the distribution Dc and let us denote by Ec the foliation induced by Dc on Rn. The
leaves of Ec are the intersections of R2n with leaves of Dc. One can prove that Ec is sufficiently
regular for the quotient space M c = R2n/Ec to be a manifold, which is satisfied for the case of
a compact simple polyhedron P ∈ Rn assumed before. Thereby one can define the canonical
projection rc : R2n → M c and apply the standard Marsden – Weinstein reduction algorithm
to find the reduced vector fields K̄c : M̄c → T (M̄c) and K̄b : M̄b → T (M̄b) on the reduced
manifolds M c and M b corresponding, respectively, to the vector fields Kb := ∇gc : Rn →
→ T (Rn) and Kc := {Hc, ·} : R2n → T (R2n).
Let now p ∈ E(p) be an extreme point of P . Since P is assumed to be simple, there always
exist vectors hj(p) ∈ Rn, j ∈ J(p), such that 〈ai, hj(p)〉 = 0, i = 1,m, and 〈ek, hj(p)〉 =
= δjk, k, j ∈ J(p). Then one says that a vector c ∈ Rn is in general position (relative to P ) if
〈c, hj(p)〉 6= 0 for all p ∈ E(p), j ∈ J(p).
Theorem 1. Let a vector c ∈ Rn be in general position. Then the set of stationary points of
the reduced vector fields K̄c : M̄c → T (M̄c) and K̄b : M̄b → T (M̄b) coincides with the set E(p).
A proof of this statement is easy and can be obtained from [2].
Theorem 2. Consider the following corresponding commutative diagrams
T ∗(R2n)
r∗c←− T ∗(M c)
↓ ↓
R2n rc→ M c
,
T (Rn)
rb∗→ T (M̄b)
↓ ↓
Rn rb→ M̄b
and the reduced symplectic structure ω(2)
c ∈ Λ2(M c) on M c and the reduced vector fields Kb :
M b → T (M b) and K̄c : M̄c → T (M̄c) related to them via the relations:
rb∗Kb = K̄b · rb, rc∗Kc = K̄c · rc, ω(2) = r∗c ω̄
(2)
c ,
whereKb := ∇gc : Rn → T (Rn), defining them uniquely, giving rise to the analytical criteria for
finding particular points x ∈ Rn solving the linear programming problem (4), (5) via the limiting
procedure,
lim
t→∞
rb(x(t;x0)) = x̄b, lim
t→∞
rc(x(t;x0)) = ūc, (6)
for all x0 ∈ Rn, together with evident conditions, K̄b(xb) = 0, K̄c(ūc) = 0.
ISSN 1562-3076. Нелiнiйнi коливання, 2002, т . 5, N◦ 1
120 I.P. TVERDOKHLIB, O.A. PRYKARPATS’KY
Here, by definition, rb(x) = xb ∈ M̄b, rc(x, c) = ūc ∈ M̄c, and the reduced vector field
K̄c : M̄c → T (M̄c) is defined simultaneously also by the relations
iKc
ω(2) = −dHc, iKcω
(2) = −dHc, (7)
where Hc := Hc|M̄c
. Moreover, M̄c ' M × Rn and the function ḡc := gc|M̄b
: M̄b → R serves
as a Liapunov function for the reduced vector field K̄b : M̄b → T (M̄b).
Thus, we obtained the effective analytical algorithm (6), (7) for solving linear programming
problems in a simple compact polyhedron P like (4), (5) based on its symmetry properties [5]
related with polyhedron constrains (1).
3. An application of the method of dynamical systems to modelling regional demand. Below
we shall discuss an example of an economics-mathematical model to which the method of
dynamical systems can be successfully applied. In [6] there was suggested the AIDS-model
of demand and described a technique of its application that based on dynamical statistical
data. Since one of the problems in modelling transition economical processes is a lack of true
statistical data for a long enough period of time, in [7] there was well grounded the follo-
wing priority demand model which is an extension of the known [6] AIDS-model: to find such
a symmetric matrix X : En → En, which would give
min
{~α;η}
(SpX + 〈
−→
b ,X
−→
b 〉) (8)
under the condition
−→w = −→α +X−→a + c~β (9)
and the constrains
〈−→a ,−→α 〉 + 〈−→a ,X−→a 〉/2 = k, −→e = (1, 1, . . . , 1)T ∈ En,
〈−→α ,−→e 〉 = 1, 〈
−→
β ,−→e 〉 = 0, X−→e = 0, (10)
where −→w ,
−→
b ,
−→
β and −→a ∈ En are some specified vectors; −→α ∈ En in an unknown vector,
c, k ∈ R1 are some constants; En is the n-dimensional Euclidean vector space with the usual
scalar product 〈·, ·〉; SpX is the trace of a matrix X : En → En and η ∈ En are intrinsic hidden
stabilization parameters.
Attempts to solve problem (8) – (10) making use of the usual simplex-method did not lead
to a success. That is why there was devised a special technique for mathematical analysis of
this problem basing on the Lagrangian multipliers method. With its help one could determine
a solution to problem (8) – (10) at a given vector
−→
β ∈ En. But a vector
−→
β ∈ En, as a rule,
is unknown in general, that is why in [7] it was suggested to seek it by means of solving an
additional linear programming problem. It allows to pose the additional optimization problem
(8) – (10) subject to vectors
−→
β ∈ En.
ISSN 1562-3076. Нелiнiйнi коливання, 2002, т . 5, N◦ 1
DYNAMICAL SYSTEM APPROACH TO SOLVING LINEAR PROGRAMMING PROBLEMS . . . 121
Let us consider a model which includes conditions (9), (10) and the functional
min
{~α;
−→
β ;η}
(SpX + 〈
−→
b ,X
−→
b 〉). (11)
Having used the Hilbert – Schmidt representation for a symmetric matrix X : En → En, one
gets the following expression:
X =
n−1∑
j=1
λj~ηj ⊗ ~ηj , (12)
where λj ∈ R1, j = 1, n− 1, are eigenvalues of the matrix X; ~ηj ∈ En, j = 1, n− 1, are the
corresponding eigenvectors, which are mutually orthonormal and orthogonal with the vector
−→e ∈ En,⊗ is the usual tensor product. Having substituted (12) info (9), (10), one can determi-
ne from that
λj =
〈−→w , ~ηj〉 − 〈−→α , ~ηj〉 − c〈
−→
β , ~ηj〉
〈~ηj ,−→a 〉
(13)
for j = 1, n− 1. Having taken then into account (12) and (13) the problem above reduces to
the equivalent one: to find a system of vectors ~ηj ∈ En, j = 1, n− 1, such that
minF (α;
−→
β ; η)
{~α;
−→
β ;η}
= min
{~α;
−→
β ;η}
n−1∑
j=1
{
〈−→w −−→α − c
−→
β , ~ηj〉
〈−→a , ~ηj〉
×
×
[
1 + 〈
−→
b , ~ηj〉2
]}
(14)
under the conditions
〈−→a ,−→α 〉 − c〈−→a ,
−→
β 〉 = k, k := 2k − 〈−→a ,−→w 〉,
〈~ηj , ~ηk〉 = δjk (j, k = 1, n− 1), 〈−→e ,−→α 〉 = 1, (15)
〈−→e ,
−→
β 〉 = 0, 〈~ηj ,−→e 〉 = 0 (j = 1, n− 1).
Having gone over from the model (11) and (8), (9) to the problem (14), (15), we have reali-
zed some justification of hidden parameters ~ηj ∈ En, j = 1, n− 1, specifying the wanted
matrix X : En → En. But the analysis of the optimization problem (14), (15) by means of
the Lagrangian multiplier method does not lead to a success.
Thereby we are forced to apply, for solving this problem, the dynamical system approach
described before. For it to be implemented, it is necessary to construct the corresponding phase
space Q and the constraint functions fi : Q → R1, i = 1,m. As a result of some analysis of this
problem, we found that
Q =
{
(−→α ,
−→
β ) ∈ R2n
}
×
{
(~a,~b) ∈ R2n
}
× T ∗(SO(n− 1)) (16)
ISSN 1562-3076. Нелiнiйнi коливання, 2002, т . 5, N◦ 1
122 I.P. TVERDOKHLIB, O.A. PRYKARPATS’KY
under the constraints
f1(x; a, b) := 〈−→a ,−→α 〉 − c〈−→a ,
−→
β 〉, f2(x; a, b) := 〈−→e ,−→α 〉,
f3(x; a, b) = 〈−→e ,
−→
β 〉,
where the elements (a, b) ∈ R2n, together with the space T ∗g (SO(n− 1)), g ∈ SO(n− 1), have
to be considered as complementary functions of the phase space subject to the Poisson bracket
{·, ·} defined on the whole symplectic space Q.
Concerning the phase space (16) we have also the following representation: ~ηj =
∑n−1
j=1 gij~ei,
where j = 1, n− 1 and the matrix g ∈ SO(n − 1) in accordance with conditions (15), which
should be substituted into expression (14). Now one can make use of the dynamical system
method to solve the nonlinear programming problem (14) following the scheme described in
Chapter 2.
Acknowledgements.The authors are grateful to participants of the research seminars at
Economics Dept. of the Franko National University of L’viv and Dept. of Applied Mathemati-
cs at the University of Mining and Metallurgy of Krakow. The results were presented at the
International Conference “Automatics” held in September 14’2000, L’viv, Ukraine.
1. Karmarkar N. A new polynomial-time algorithm for linear programming// Combinatorica. — 1984. — № 4.
— P. 373 – 395.
2. Faybusovich L. Simplex-method and groups generated by reflections// Acta Appl. Math. — 1990. — № 20.
— P. 231 – 245.
3. Abraham R., Marsden J. Foundations of mechanics. — New York: Addison Wesley, 1978.
4. Weinstein A. Local structure of Poisson manifolds // J. Different. Geom. — 1983. — № 18. — P. 523 – 557.
5. Prykarpatsky A., Mykytiuk K. Algebraic integrability of nonlinear dynamical systems on manifolds. —
Netherlands: Kluwer, 1998.
6. Deaton A.S., Muellbauer J. An almost ideal demand system // Amer. Econ. Rev. — 1980. — 70, № 3. —
P. 312 – 326.
7. Tverdokhlib I. P. Modelling of demand in a region with the transition economics [in Russian]: Candidate-
Degree Thesis (Economics). — L’viv, 1999.
Received 20.11.2000
ISSN 1562-3076. Нелiнiйнi коливання, 2002, т . 5, N◦ 1
|