Affordable Access

Teoremas de existencia de la programación lineal

Authors
Publisher
Publicacions de la Secció de Matemàtiques
Publication Date

Abstract

Pub . Mat . UAB N° 22 Nov . 1980 Actes VII JMHL TEOREMAS DE EXISTENCIA DE LA PROGRAMACION LINEAL J.P . Vilaplana Dpto . de Matemática Aplicada Universidad del País Vasco SUMMARY : One of the most important facts to solve a linear progra- mming model is that the solutions of the primal and dual must verify some conditions so that the solution may be optimum . In this paper, the Existence and Duality Theorems of t.he linear programming are proved, without using the Farkas-Minkows ki's Lemma . This provides a great simplification in the follo- wing theoretical development . o primal : (1 .a) (Min) z = c'x con las restricciones Sean el modelo de programación lineal bajo forma canónica (1 .b) Ax a b y (1 . c) x > 0 siendo x un vector colu=a con n componentes y A una matriz de for- mato m x n, y su dual : (2 .a) (Max) z' = b'u con las restricciones (2 . b) A'u < c y (2 . c) u > 0 siendo u el vector de las variables duales, un vector columna con m componentes . TEOREMA 1 .- Sí x* es una solución factible del primal y u* es una solución factible del dual, y se verifica : (3) c'x* = b'u* las soluciones x* y u* son las soluciones óptimas correspondientes . Si x* es una solución factible del primal, Ax* > b. La no- negatividad de u* nos permite escribir, pre-multiplicando por (u*)' : (4) (u*)'AX* > (u*)'b = b'u* Asimismo, puesto que A ' u* _ c, se tendrá que (u * ) ' A _ c ' , de donde, post-multiplicando por x* : (5) (u*)'Ax* < c'x* Luego, de (4) y (5), se deduce : (6) c'x* > b'u* Si x** es otra solución factible del primal, se tendrá análogamente : (7) c'x** > b'u* y, por la hipótesis (3), resultará : ' (8) c'x** > b'u* = c'x* y como en el primal se trata de una minimización, x* será la solución óptima del mismo . Un razonamiento análogo nos conduci- rá a : (9) b'u** = c'x*< b'u*

There are no comments yet on this publication. Be the first to share your thoughts.