PDF de programación - Qué Es La Programación Lineal

0066006006000000000000000000006000000008090000000000600000

lecciones populares

de matemáticas

LA PROGRAMACIÓN

QUÉ ES
LINEAL

A.S.Bársov

NOMNVYVJAPHBIE JIEKUNM MO MATEMATUKE

A. C. BAPCOB

UTO TAKOE JIMHEUHOE
NPOrTPAMMHPOBAHHUE

U3HATEJIBCTBO

«HAVKA»

LECCIONES POPULARES DE MATEMÁTICAS

A. S. BÁRSOV

QUÉ ES LA PROGRAMACIÓN

LINEAL

EDITORIAL MIR

MOSCÚ

Traducido del ruso por el Candidato a Doctor
en Ciencias Técnicas Bernardo del Río Salceda

Ha ucnaHckoM 5sA3bIKe

OQ Traducción al español. Editorial Mir. 1977

Impreso en la URSS. 1977

INDICE

Prefacio a la edición española

7

Prefacio

8

Introducción

9

Capitulo I.

Algunos conceptos y definiciones del álgebra lineal.
13

$ 1. Concepto de espacio m-dimensional.
24

$ 2. Hiperplanos y semiespacios.
26

$ 3. Poliedros convexos.

13

$ 4. Sistema de desigualdades lineales.

28

$ 5. Valor mayor y menor de la forma lineal en el poliedro.

33

$ 6. Transformaciones de desigualdades
en igualdades al resolver problemas

de programación lineal.

37

Capítulo II.

Resolución del problema general de la programación lineal

41

S 7. Transformaciones idénticas de un sistema

de ecuaciones algebraicas lineales.

41

$ 8. Método de cómputo de una solución

no negativa para un sistema
de ecuaciones algebraicas lineales.

56

$ 9. Resolución del problema de programación lineal.

64

$ 10. Sobre un problema de min-máx.

70

Capítulo III.

Resolución del problema de transporte

por el criterio de costos.

72
$ 11. Planteamiento del problema.

72

$ 12. Soluciones básicas del problema de
transporte por el criterio de costos.
74

$ 13, Elección Óptima.

78

$ 14. Invariabilidad de la sucesión de

selecciones, equivalentes a las transformaciones

de la matriz de los valores.

83

$ 15. Algoritmo del cálculo de la solución óptima.

85

Capítulo IV.

Resolución del problema de transporte

por el criterio del tiempo.

98

$ 16. Planteamiento y resolución del problema.

98

$ 17. Resolución de los problemas de transporte
tomando en cuenta el tiempo y el costo.
109

Bibliografía. 112

PREFACIO A LA EDICIÓN EN LENGUA ESPANOLA

AA

Con motivo de la decisión de publicar esta obra en lengua

española desearía dirigirme al lector con algunas palabras.

Hace ya cerca de veinte años que apareció este libro. En aquel
entonces la programación lineal
el proceso
de su desarrollo, estábamos apasionados con las cuestiones de su
teoría, aplicación y divulgación. En este pequeño libro
traté
de explicar los conceptos básicos de la asignatura y la esencia
de algunos de sus métodos de cómputo.

se encontraba en

El libro se agotó rápidamente, continuaron las investigaciones
sobre el tema; han aparecido muchas obras en las cuales, bajo
mi opinión, se explica mejor parte del material. A pesar de eso,
hace relativamente poco tiempo, este libro fue reeditado en Japón,
en la RDA, ha sido traducido a las lenguas de otros países.
Ahora la editorial “MIR” está preparando en lengua española
la edición de la serie completa de libros “Lecciones de divulgación
de matemáticas” en la que éste salió. La traducción de este libro
se ha hecho integramente por dicha edición. Observaremos que
desde
aquel tiempo las computadoras se han perfeccionado
muchísimo y por eso las referencias a los ejemplos de rapidez
de resolución de algunos problemas, así como las dimensiones
de éstos, deben ser interpretados por el lector como factores que
caracterizaron el periodo inicial de la aplicación de la programación
lineal. Actualmente las dimensiones de los problemas que se tratan
son mucho mayores y las velocidades de su resolución mucho más
altas. Las explicaciones que se dan sobre los conceptos y definiciones
fundamentales de la programación lineal y las bases de los métodos
de cálculo por el criterio de costo y de tiempo, pueden hoy
en día abrir al lector el camino a esta interesante asignatura
de la matemática moderna, a la programación lineal.

Estaré satisfecho de que el lector encuentre útil para sí este

pequeño libro y al mismo tiempo le expreso mi simpatía.

5 de mayo de 1976

A. S. Bársov

PREFACIO

el empleo de métodos

En este libro se examinan cuestiones de la teoría y de los
métodos de resolución de algunos problemas de programación
lineal. El está destinado a un amplio circulo de personas ocupadas
en
la organización
y la planificación de la industria.
los fundamentos

de la programación lineal.
Al hacerlo se presentan tan sólo los datos y demostraciones que
son necesarios para una exposición elemental de los métodos
de programación lineal.

matemáticos

Se estudian

en

El trabajo se realizó a base de las conferencias dadas por
que se dedicaban
las

el autor
a la resolución de problemas de programación lineal
máquinas computadoras electrónicas.

para personas

el año

1957

en

en

L. A. Lyusternik, miembro correspondiente de la A.C. de la
U.R.S.S., en el año 1959 revisó con atención el material de las
conferencias, dio una serie de valiosos consejos y contribuyó
a la edición del presente trabajo.

El autor agradece a los profesores A. A. Liapunov y N.S. Kra-
silnikov por su ayuda en la solución de las dificultades que
surgieron en el proceso de la preparación de este libro.

El autor está particularmente agradecido al redactor V. D, Ro-
senko por su minuciosa labor que sirvió considerablemente para
mejorar el libro.

A. S. Bársov

9

INTRODUCCIÓN

La tarea del desarrollo ulterior de las fuerzas productivas,
de la mejora de la planificación de la industria socialista y el
aumento de la efectividad económica de las inversiones básicas
en nuestro
país adquiere de año en año cada vez mayor
importancia.

de posibles

soluciones

La diversidad

y caminos
de desarrollo en la industria actual, las interrelaciones entre las
diferentes ramas de la economía nacional y otros problemas
económicos hacen que las tareas planteadas anteriormente sean
excepcionalmente difíciles.

técnicas

Para solucionar estos problemas, los métodos matemáticos
y en particular el método de programación lineal, así como los
medios técnicos modernos, las máquinas computadoras electrónicas
pueden prestar una ayuda sustancial.

La teoría de la programación lineal, que surgió hace dos
décadas, actualmente ha obtenido una amplia utilización práctica
particularmente en el terreno de la organización y planificación de
la industria.

Los primeros trabajos en este sentido fueron los de L. V. Kan-
torovich, miembro correspondiente de la A.C. de la U.R.S.S.*.
En esos trabajos se expusieron métodos matemáticos para resolver
problemas tales como el del aumento de la efectividad
del
transporte, el cálculo de los regímenes óptimos de producción,
la distribución racional de los materiales industriales, etc.

Posteriormente fueron creados métodos generales

de pro-
gramación lineal tales como, por ejemplo, el simplex, el combina-
torio y otros métodos que se emplean eficazmente en la solución
de diversos problemas para determinar el óptimo en la planifi-
cación. Dantzing, Charnes y una serie de cientificos soviéticos
y extranjeros se ocuparon de la elaboración de estos métodos.

La programación lineal abarca métodos de solución de problemas
de óptimo en los que hay muchas variables relacionadas entre
sí y subordinadas a unas determinadas condiciones de restricción.
El planteamiento de los problemas de programación lineal se puede
formular de la siguiente manera:

Tenemos cierta magnitud (por ejemplo el costo, el tiempo)

A. C. de la U.R.S.S. y laureado con el Premio Nobel.

*) L. V. Kantorovich hoy es miembro efectivo de la

10

que es función lineal de una serie de variables. A su vez, las
variables tienen que satisfacer a las restricciones expresadas en
forma de un sistema de desigualdades o igualdades lineales.

Hay que buscar aquellos valores no negativos de las variables
con los que la magnitud que sea su función adquiera el valor
menor (el mayor).

En calidad de ejemplo veamos el problema de transporte.

Este problema se puede formular de la forma siguiente:

De m puntos de partida dados, en cada uno de los cuales
hay a; unidades de cargamento, se deben llevar bj unidades
de la carga indicada a cada uno de los n puntos de llegada

(i=1,2,..., m;

j=1, 2, ..., 2).

Se exige planificar el transporte de tal modo que los gastos
sean mínimos. Designaremos con x;; la cantidad de carga trans-
portada del punto de partida i¡ al punto de llegada j. En tal
caso el contenido matemático del problema se reduce a encontrar
los valores no negativos de x,, que satisfagan las ecuaciones

n

m

Y, Xij = Aj,
j=1

y, Xiy =D),

y con los cuales el costo general del transporte

109

sea el menor. Aquí c,; es el costo de transporte de una unidad