O zasadzie dualności w programowaniu liniowym

• Autorzy: Antoni Smoluk

Warianty tytułu

On Dual Principle of Linear Programming

• Języki publikacji: PL

Abstrakty

W artykule podano zasadę dualności wraz z krótkim i elementarnym jej dowodem. Program liniowy jest trójką (p^*, A, q); szuka się maksimum funkcji f{x) = px przy ograniczeniach Ax ≤ q oraz x ≥ 0. Symbolem R(A, q) oznacza się zbiór rozwiązań dopuszczalnych {x є Rⁿ: Ax ≤ q, x ≥ 0}, natomiast v(p^* , A, q) jest wartością optymalną sup{px: x e R(A, q)}. Jeżeli program (p^* , -A, q) jest zadaniem prymarnym, to problem {-q^* , A^* ,-p) jest do niego dualny, gdzie gwiazdka jest sprzężeniem, czyli transpozycją macierzy. Zasada dualności. Jeżeli zbiory R(-A, q) i R(A^* , -p) nie są puste, to istnieje para decyzji optymalnych {u, w) є Rⁿ x (R^m)^* i ponadto pu = v(p , -A, q) = -v(-q^* ,A^*,-p) = qw. (abstrakt oryginalny)

EN

The article gives the dual principle of linear programming together with an elementary and short proof of it. Linear programme is defined as usual; it is an ordered triple (p ^*,A,q), where p^* is a linear functional from the space of baskets of goods Rⁿ into real line R, matrix A represents a technology - linear operator from Rⁿ into R^m, and vector q є R^m says about materials - resources we have in stock. We are seeking the maximum of the function f(x) = px under conditions Ax ≤ q and x ≥ 0. Let symbol R(A, q) denote the set {x є Rⁿ: Ax ≤ q, x ≥ 0} of all feasible solutions, while v(p^* , A, q) designates the optimal value sup {px: x є R(A, q)} of the programme (p^* , A, q). If a programme (p^* , -A, q) is primary, than the programme (-q^* , A^* , -p) is dual to it, where the asterisk means conjugations or simply the transposition of a matrix. Principle of duality. If primary and dual programmes are consistent, the sets of feasible solutions R(-A, q) and R(A^* , -p) are not empty, then there is a pair of optimal solutions (u, w) є Rⁿ x (R^m) and moreover pu = v(p^* ,-A,q) = -v{-q^* ,A^* ,-p) = qw, so we have equilibrium v(p^* , -A, q) + v(-q^* , A^* , -p) = 0. (original abstract)

Słowa kluczowe

PL

Programowanie liniowe; Zasada dualizmu w ekonomii

EN

Linear programming; Principle of duality in economics

• Czasopismo: Prace Naukowe Uniwersytetu Ekonomicznego we Wrocławiu. Ekonometria
• Rocznik: 2009
• Tom: 26
• Numer: nr 76 Zastosowanie matematyki w ekonomii
• Strony: 160--169

Twórcy

autor

Antoni Smoluk

• Uniwersytet Ekonomiczny we Wrocławiu

Bibliografia

• Czerwiński Z., Wstęp do teorii programowania liniowego z elementami algebry wyższej, PWN, Poznań 1961.
• Smoluk A., O perspektywie, dualności i equilibrium, „Przegląd Statystyczny” 2008, Tom 55, z. 2, s. 5-14.
• Yaglom I., Trakhtenbrot B., Ventsel E., Solodovnikov A., Nouvelles orientations des mathématiques, Editions Mir, Moscou 1975.