• Author / Uploaded
• David Cruz Mateo

Citation preview

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

FACULTAD DE INGENIERÍA

APUNTES

PROGRAMACION LINEAL

ING.BENITO MARIN PINILLOS. NOVIEMBRE DE 1980.

GP R 0 L 0 G 0.-

APUNTES DE PROGRAMACION LINEAL (II SENIERIA DE SISTEMAS)

Los apuntes que aqui se presentan tienen el objeto de proporcionar al alumna del Curse Ingenieria de Sistemas, material de referencia y con sulta. Incluyen casi la totalidad de los temas de la materia perc es necesario que elalumno realice trabajos de investigaci6n para complementarlos, ademas de resolver ejercicios variados sabre cada tema y consultar la bibliografia seleccionada.

No se pretende que este sea un trabajo concluido, pues se espera realizar nuevas correciones, para €sto las sugerencias de alumnos y

fAt:ULTAD

n:

::iuJ..,;::;ll!~

prof~

sores son de gran irnportancia.

M. EN C. BENITO MARIN PINILLOS NOV /1980.

M. EN C. BENITO MARIN PINILLOS.

Noviembre de 1980.

'

3

INVESTIGACION DE OPERACIONES I

CONTENt DO CAP. I Antecedentes CAP. II Matrices Ecuaciones Lineales Simult6neas CAP. ttl Programaci6n Lineal Caroctertsticas qye debe tener un problema para poder ser ,....,etto por Progromaci6n Lineal Terminologta en Progromaci6n Lineal Rutina del M.!!todo Simplex M~todo del Pivote Compl icaciones M~todo de las dos Fases CAP. IV Problema de Tronsporte Degeneraci6n en el problema de transporte Problema de Asignaci6n Procedim iento Sistemc:lti co

ANTECEDENTES 10 34 Es por todos conocido el rapido desarrollo que

47

tado durante el presente siglo,

58 68 78 '12

organizaciones humanas.

97 121

han

experime~

el tamano y la complejidad de las -

Por ejemplo el tamano de las empresas mo--

dernas implica que las decisiones administrativas pueden tener un efecto sabre grandes cantidades de capital y

nas.

gran nUmero de perso--

Los errores pueden ser tremendamente costosos y una sola deci

si6n equivocada puede requerir anos pdra rectificarse.

150 174 176 180

El cambia revolucionario sufrido por las organizaciones huma nas

ha traido consigo la divisiOn del

trabajo y la segmentaci6n de-

las responsabilidades administrativas en estas organizaciones.

CAP. V Tearta Dual Metodologia del M.!!todo Simplex Dual Uso de matrices en Progromaci6n Lineal Programaci6n de enteros An61 isis Post-Dptimo

-

Es-

191 201

te crecimiento ha traido consigo la tendencia por parte de los mu--

211

chos componentes de una organizaci6n a crecer dentro de

218 220

lativamente autOnomo teniendo cada uno de ellos sus propias metas ,-

un plan re-

perdiendo por lo tanto la visiOn de como sus actividades y objeti--

CAP. VI lmplementacirn en Computadoros CAP. VII Teorta de Redes Ruta m6s coria Mtnimo 6rbol de expansi6n Pert Sistema de redes con activioodes en el nodo

Ap~ndice

vos se comparan con los de la organizaci6n.

Lo que es buena para

un componente frecuentemente es perjudicial para el otro.

229

246 257

que en una empresa por ejemplo, Producci6n.-

-

r::s asi -

existen las siguientes tendencias:

Pocas lineas de productos y grandes corridas -

262 281

de producci6n Ventas.-

(grandes inventarios).

Abundantes y variados inventarios.

Finanzas.-

Minimizar inventarios.

Personal.-

Producir inventarios solamente durante los pe- riodos flojos

(mantener producci6n constante).

4

GCu31 es en realidad la mejor politica para la organizaci6nT Es aqui donde entra en acci6n la investigaci6n de operaciones. La investigaci6n de operaciones siempre toma el punta de vista general de la organizaci6n e timas,

intenta llegar a soluciones 6p-

teristicas asociadas con ella mensionales

esto es la mejor soluci6n para la organizaci6n.

estudios de grupo

(pesos, etc.) pero a veces son adi--

(probabilidad de destruir un blanco durante un ataque-

aereo).

Esta solu-

ciOn no siempre es la Optima para sus componentes por separado. La investigaci6n de operaciones envuelve

La medida de efectividad generalmente tiene unidades carac-

Los origenes de la investigaci6n de operaciones datan de -hace muchos aDos cuando se empez6 el intento de usar un

acercamie~

to cientifico en la administraci6n de las organizaciones.

Estos -

Esto es --

origenes sin embargo fueron aislados y faltos de coordinaci6n, no-

debido al aspecto tan general que toma la misma y al hecho de que-

fue sino hasta la segunda guerra mundial cuando la complejidad de-

ser1a

las operaciones militares hizo surgir lo que hoy se conoce por in-

i.e.

agrupa

a toda clase de expertos en sus estudios.

imposible que un especialista en investigaci6n de operacio--

nes supiese todo lo relative a cada aspecto y es por esto que el especialista requiere de los demas expertos a quienes

e1

coordina.

Otro de los aspectos que favoreci6 el desarrollo de la in-vestigaci6n de operaciones es el hecho de que el ritmo de la

empr~

vestigaci6n de operaciones.

A causa de la guerra hubo la necesi--

dad de distribuir de manera eficiente materiales escasos a las dis tintas operaciones militares y dentro de estas a las actividades que los campanian.

Para el efecto se reuni6 un gran nUmero de -

sa moderna es tal que las decisiones se requieren mas rdpidamente-

cientificos para que realizaran una investigaci6n de las operacio-

que nunca; el posponer la acci6n puede poner en una decidida venta

nes militares.

ja a un cornpetidor.

Debido al §xito logrado en el aspecto militar, la industria

No es sorprer1der1te que el aumento en la Jificultad de tornar las decisiones haya requerido de esfuerzos para dar a esta actividad una base mas objetiva y rutinaria.

La investigaci6n de opera-

se fue

los militares. lJna

Desde el punto de vista de la investigaci6n de operacionesuna decisiOn es una recomendcici6n de que se lleve a cabo un cursoQ11ien toma la deci- -

Los invcstigadores descubrie- -

ron que la industria sufria de los misrnos problemas b§sicos que --

cior1PS forma parte de este esfuerzo.

de acci6n particular que afecta al sistema.

interesando en este campo.

vez

inici~rlas

las t§cnicas de la investigaci6n de

oper~

ciones atrajeron la atenci6n de numerosos investigadores los cua-les lograrorl desarrollar las mismas a grandes pasos.

Las t§cnicas

desarrolladas contribuyeron a empujar la r§pida carrera que lleva-

si6n intenta que el sistema sea mds ''efectivo'' para alcanzar las -

la investigaci6n de operaciones,

metas de la organizaci6n.

las t§cnicas hubieren alcanzado un grado de desarrollo extraordina rio.

de aqui que para 1950 muchas de -

5

Simulaci6n.

En la misma €poca en que se perfeccionaban las t€cnicas de-

Teoria de inventarios.

la investigaci6n de operaciones t~~hi;n se lograron grandes avan--

En la actualidad existen dos organizaciones en Estados Unices en el disefto de computadoras, lo que facilit6 la utilizaci6n dos que agrupan gente interesada en la investigaci6n de operacio-de las mismas debido a la gran cantidad de computaci6n requerida nes. por la investigaci6n de operaciones.

The Operations Research Society of America que edita la re-

Aunque no existe una definiciOn correcta para la investigaci6n

de operaciones podemos decir que la

~~-

se aplica a

iuue~ti~aeiBn

ae

vista Operations Research.

o~-­

problemas que conciernen a la conducci6n y

coo~

dinaci6n de operaciones o actividades dentro de una organizaci6n.

The Institute of ManageMent Science que edita la revista -Management Science. Metodolclgia.-

La investigaci6n de operaciones se aplica extensamente en el campo de los negocios, el militar, la industria, el gobierno, hospitales,

comunicaciones,

transporte etc.

El m€todo de an§lisis empleado esto es,

Aunque no existe una secuencia tija de pasos a seguir en un -

estudio de investigaci6n de operaciones, podemos analizar los pa-sos dentro de un problema tipico.

es el del m€todo cientifico,

la investigaci6n de operaciones introduce el razonamiento

a) Formulaci6n del problema. surgen de una manera vaga,

En la practica los problemas-

raz6n par la cual es necesario estudiar

cientifico creative dentro de las propiedades fundamentales de las

el sistema bajo consideraci6n y definir exactamente el problema,

operaciones.

indicando claramente cuales son los objetivos,

La programaci6n lineal ha sido usada con €xito en problemas

y que es

lo que se puede hacer;

las restricciones

interrelaciones existentes, alter-

de asignaci6n de personal, mezclado de rnateriales, distribuci6n y-

nativas posibles,

transportaci6n, asi como politicas de inversiOn.

laci6n es crucial, pues es imposible obtener buenos resultados -

La programaci6n din§mica ha tenido exito en la planeaci6n de gastos de propaganda,

distribuci6n del esfuerzo de ventas y

pl~

neaci6n de la producci6n.

-

limitaci6n del tiempo, etc.

partiendo de un mal planteamiento.

Se ve que la formu-

De aqui que en cuanto surjan -

nuevas aspectos durante el nesarrollo del estudio, la formulaci6ndebe ser revisada para ver si no ha cambiado.

Los fen6menos de espera se han aplicado a problemas de con-

Aqui se debe tener cuidado ya que aunque dijimos que el - -

gestionamiento de tr§fico, reparaci6n de rnaquinaria, planeaci6n de

objetivo principal era la soluci6n Optima para toda la organiza- -

tr§fico aereo y diseno de presas.

ci6n,

Otras de las -~~r:~~ de la investigaci6n de operaciones son: Teoria de juegos.

existen cases en que el problema afecta a una sola secci6n y

al incluir todas las demas cornplica terriblemente el problema.

6

b) Construcci6n del modele matern3tico (muchas veces es este el paso mas sencillo). problema de manera tal,

~•te

~aoe

consiste en la reforrnulaci6n del

que sea conveniente para analizarlo.

En -

este paso representamos matern§ticamente el sistema bajo estudio. Un modele rnatem§tico es una representaci6n idealizada

expr~

Per ejemplo en prograrnaci6n lineal podemos representar las-

x1'

cuyo valor se va a deterrninar,

como -----

'xn.

x2, . . .

rentes alternativas con suficiente exactitud como para poder reali zar una buena decisiOn. Cuando existe mas de una funci6n objetiva, estas deberan -transformarse y combinarse en una sola funci6n objetiva compuesta. El coste del estudio y el retraso deben tambi~n ser considerados.

sada en terrninos de simbolos rnatem§ticos.

n variables de decisiOn,

Un buen rnodelo es aquel que predice los efectos de las dife

c) Obtener una Soluci6n del Modelo.-

Aqui debernos aclarar-

que aunque existen modelos matematicos que conducen a

una soluci6n

Optima dicha soluci6n es s6lo Optima con respecto al modele emple~

La medida compuesta de efectividad (llamada funci6n objetido y es posible que esta soluci6n no sea la mejor posible para elva)

(ganancia)

se expresa entonces como una

funci6n matem3tica problema real.

De aqui que si el modele esta bien formulado la so

como: luci6n obtenida debera ser una buena aproximaci6n a P= Sx

1

L

3x

2

+ 7x

3

la soluci6n

+ .... + 2xn del problema real.

Las restricciones a las variables de decisiOn tarnbien se -Muchas veces la soluci6n obtenida se emplea como datos para expresan rnatematicamente

Jx

1

+

Bx

7

+

-

3x

n

~

100. fur•JJtUldi' rtueVdiJJente el problema y asi mediante una serie de ciclos

El modele matematico quedaria en este caso como escoger los se obtiene una mejor soluci6n. valores de las variables de decisiOn tales que maximicen la funci6n d) objetiva,

Probar el Modele y su Soluci6n.-

No importa cuan bueno-

siempre y cuando se cumplan las restricciones. parezca nuestro,modelo siempre

se debe probar.

El primer paso es-

El modele matematico ayuda a revelar relaciones importantes checar errores obvios de causa y efecto,

o detalles pasados per alto.

senalando de esta forma cualquier data adicio-Prueba Retrospectiva.-

nal que pudiera ser de irnportancia para el estudio. Debe tenerse en cuenta que el modele matematico es una abs-

Cuando es aplicable,

consiste en mi

rar la historia de la campania y encontrar que hubiese pasado de haberse aplicado este modele.

Este metoda puede mostrar fallas en

tracci6n de la realidad y como tal no puede incluir hasta el mas el modele y asi modificarlo. minima detalle,

lo

Una gran desventaja de este metoda

cual complicaria innecesariarnente el problema. consiste en que utiliza los mismos datos con ayuda de los cuales -

Per otro lade el excluir efectos colaterales que estan fuerternente se desarrollO el modele.

Otra falla es que las condiciones pueden

correlacionados con la decisiOn por efectuarse afecta grandementeel resultado.

haber cambiado y que los datos diciones futuras.

pasados

ya no representen las con-

7

Otra prueba es decir que no se aplique el modele hasta dentro de seis meses y observar que hubiese pasado en este lapso de haberse aplicado el modelo. e) Establecer gontrol Sabre la SoluciOn.sOlo cuando

~l

Este paso se usa

modele desarrollado se va a usar repetidamente

bido a que las condiciones (datos)

de-

pueden estar variando constan--

temente. Este paso puede envolver el descubrir los parametres criticos (aquellos cuyo cambio puede afectar significativarnente la solu ciOn).

Esto se efectlia mediante el analisis de sensibilidad. Una vez descubiertos los parametres criticos se puede esta-

blecer un metodo estadistico para detectar cambios significativosen los mismos. Cuando se descubre un cambio en un parametro critico, es ne cesario ajustar la soluci6n al nuevo valor. f)

Implementaci6n.-

El grupo de investigadores debe parti-

cipar activamente en esta fase,

con objeto de supervisar que la --

soluci6n obtenida sea convertida con exactitud en un procedimiento operative. Los pasos a

seguir son: 1) Se comunica a la administraci6n ciOn obtenida.

la solu-

2) Tanto la administraci6n como los investigadores comparten la responsabilidad de poner esta soluci6n en operaci6n.

3) Adiestramiento del personal involucrado enla soluci6n.

4)

Retroalimentaci6n.

9

mos con la misrna letra perc rninllscula, seguida de des sufijos, el-

II.- MATRICES

primero de los cuales representa el renglon al que el elemento corresponde, mientras que el segundo indica la columna. Es as1 que los elementos de la matriz A ser&n a ..

per

~J

Definicion II-1.-

eje~

plo: Una matriz es un arreglo rectangular de nUmeros escalares. Denominaremos por m

ro de columnas de una matriz. Una matriz con m una matriz

a13

el nUrnero de renglones y por n el nUme

=

mxn.

A=

Una matriz n x n se dice que es de arden n.

Tenemos entonces que:

A=

l:

2

6

5

12

es una rnatriz 3 x 4 y

'0

21

a22

a· m1

a· m2

J

0

0

0

0

0

0

0

0

0

0

0.

:'"l 2n

a•mn

_j

A=[aii}

='aijll

=11 a ij

II

m xn

Debe notarse que la letra particular que aparece como sub-indice es indiferente, es la posiciOn lo que es irnportanteo Con las anteriores convenciones aij

II a ijll

~ :l

es una matriz 3 x 2

["

a12

Algunos autores utilizan 8

a33 = 12

a24 = 14;

sigue:

renglones y n columnas, se conoce como --

7

8;

En terminos generales podernos representar una rnatriz como -

akl

es una matriz.

es un escalar

y

Notese que mientras los elementos a ij

pueden no ser iguales,

se considera que las matrices

y -

II aijll

y

llaklll son identicas o Una rnatriz no posee ninglln valor numerico (a diferencia de su de-•

terminante).

A los nUmeros que integran el arreglo rectangular, se 1~ d~ nomina "elementos de la matriz".

7,

2,

5, 8,

6, 12, 1, 14, 3,

mientras que 4, 8,

7,

Es asi que los nllmeros 4,

3, 1,-

son los elementos de la matriz A,

5, 3, 9, son los elementos de la matriz B.

Las matrices las denominaremos con letras mayUsculas.

Sin embargo es conveniente realizar ciertas manipulaciones con los arreglos de nllmeros; es asi que

se han desarrollado reglas que

pe~

miten realizar operaciones con matrices, las cuales son analogas a las operaciones aritmeticaso Definicion II-2

Los elementos correspondientes de la matriz los denominareSean:

10

A= dos matrices.

y s6lo

I aijll

y

I ill

B =

Se dice que A y B son "iguales", esto es A

=

Para "surnar" dos matrices A y B

B sl

si todos y cada uno de los elementos correspondientes son Es decir A y B tienen exactarnente los mismos componentes

iguales. (a ..

bij

l]

mero de hileras y de columnas entre si),

ambas matrices tengan el mismo nUmero de renglones,

A + B Ejemplo.

asi como el

II-3

de elementos DefiniciOn.

\all

••

0

0

att

}

don de t

II

ai i

= min

lo cual puede quedar-

II

\ m,

es el conjunto n

1.

c( -~,

=

II a i

+

j

bi j

I

II-2 4

l:

mismo nUrnero de columnas entre si.

La diagonal principal de una matriz

nu

solamente es necesario su

mar los elementos correspondientes de ambas,

De lo anterior es clara que para que A = B es necesario que

DefiniciOn.

deben tener el mismo

~ue

representado en la siguiente forma:

y de j).

para todos los valores de i

II-6

DefiniciOn.

bi

-3

+

DefiniciOn.

II-7

~

-1 1) 7

-4

2

3

~

10 -4

La resta de dos matrices A y B podemos

II-4

interpretarla como -

la suma de la matriz A con la matriz C donde C = kB = (-1) Una matriz diagonal es una rnatriz cuadrada de arden n,

B.

en Asi pues tenemos:

la cual los elementos que no pertenecen a

la diagonal principal --

II-5

Ejemplo.

Asi pues:

ka i j

II I

a12

k

....

aln

k

k

a22

k

....

a2n

k

k

a

k

••

a

k

all

k

a21

a

1

5

0

8

-

bijll

2

ml

m2

0

mn

j

[ -1 3

7

lJ

~2

2

3

63

0

9

~

=

c:

20

315

c

45

3J 10

=

~-4

-1 0

-6

12

7

-2

-1

el elemento cij

5 -1]

en el rengl6n

i

y la columna

de la matriz resultante de multiplicar A por B, es necesario -

multiplicar cada elemento del reng6n rrespondiente de la columna

4

-4

II-8 (Multiplicacion)

Para encontrar 0

II-1

[:

7

Definicion.

don de A puede tener cualquier disposici6n de sus elementos. Ejemplo.

II-cl

3 4 -j [

efectUa multiplicando cada uno de los elementos de la matriz por k.

I

-

lumnas entre sl.

La operaciOn de multiplicar una matriz par un nUmero k se

=

II aij

B =

nuevamente A y B deben de tener el mismo nGmero de renglones y co-

Definicion.

kA

B = A + C = A + ( -1)

A -

son cera.

j

de A por el elemento co- -

de B y sumar estos productos;

obser-

11

vamos que la multiplicaciOn de dos matrices esta definida si y s6lo si el nUmero de columnas de A es igual al nUmero de renglones de B,

Se llama matriz cero o nula a aquella matriz de cualquier arden cuyos elementos son todos ''cero''; Se representa por:

~

(n6tese que el nUmero de renglones de A y de columnas de B -

puede ser cualquiera.) En general si:

II a ij II

y

mxn

II bijJI nxr

su producto sera:

~

C= AB = L a. llk=l lk

. EJem~.

AB=

b

. k]

II-4

I

=

mxr

II

Ejercicio II-1 C .. l]

II

1

3

0

2

1

-2

2

2

1

3

-2

= 11 0

4

Ejemplo.

A

{ l~ l[Jl-:Jt~[J B=

1

523

C= 5

0

A=D p01"'1Ue a

4

o AB=

344

D= 1

412 5

C 0

2~

10

BA=

c2

14

1~

t- c

5. -

porque b ij

t-

X

4.

c

X

3

es una matriz 4

=

II-1

II-9

00~30

ci j

B es una matriz 3

7.- k B

8.- A + D

3 B

21

:1F

1

es

4.- A es una matriz de arden 3.

no esta definida.

La divisiOn entre matrices no esta definida.

500

7 E 0 6

723

6.- E es una matriz diagonal.

b.- La multiplicacion BAde las matrices del ejemplo II-4 -

6

= d11 = 3 ; a12 = d12 = 4 ; a13 = d13 = 4 11

La diagonal principal de B

lo esta.

Definicion.

5

3.- La diagonal principal de A es

BA

En la mayor1a de los cases en que A B esta definida,B A no-

Nota.

2

etc.

II-5

t )'{ ~

7

7

1.-

2.- B

t-

.. . 0

1320

-2

es decir: AB

.. . 0

5436

4

6

La operaci6n de multiplicaci6n de matrices no es conmutativa,

..... ] ..... 0

Sean: mxr

~" 'j~ ]~' 2

0 0

f

12

9

21

6

15

3

9

6

[: ~ 8

12

4

]

~

3' 6'

f 5'

2'

31 q

12

no est a definida.

A + B

[ :I

- E =

9.- A

A - Cn

est

BF

a

1

10.- BC=

Dada la matriz

la matriz AT, obtenida de A intercambian-

4

do las hileras par las columnas en A,

0

ta de A.

2

rengl6n i

definida.

en el rengl6n j

04

43

79

24

29

4

431

Si

AT =

II

aij

y la columna co 1 u mn a

i

11

se llama la matriz

el elemento a_ij

j

transpue~

que aparece en el --

de AT es el elemento a .. Jl

que aparece -

de A .

Ejemplo II-6

40

1.:_j

no esta definida.

11.- CB=

A,

7

37

34

9

32

23

30

9

24

21

25

1

41

48

47

3]

[

'" ~

3

0

J[ A"':::

1

2

0

6l 7

2

4

1

3

3

2

1

Para obtener la transpuesta de una matriz,no es necesarioque esta sea cuadrada. Propiedades de la matriz transpuesta:

Vemos que B C 1

C B

A B

Las matrices satisfacen las siguientes leyes: 1.-

2.-

CA =

¢

A

BT AT

)T

= AT

A + B )T

+

BT

Definicion II-11

A

La rnatriz adjunta es aquella 3.-A+¢

los menores de la transpuesta de la matriz cuadrada dada.

4.- A - A

¢

5.- A + B

B + A

6.- A

B + C

A + B

c

8.-

A + B

+ c

=

Se escribe A

A C + B C A +

B + C)

(AB) C

leyes que se satisfacen siempre y cuando las operaciones propues-tas est&n bien definidas. Definicion II-10

r

Ejemplo II-7

AB + AC

7.-

9.- A (BC)

matriz cuadrada formada por -

A

1J ~

A

3

0

1

2

4

2

A~

~3-~

=

1

0

4

0

1

2

13

- I~

~I +I~ ~I + I~ -~I -I~ ~I - I~ -~, +I~ ~I

-I~ ~I Ar =

I -I~ -~,

+I~ -~, Definicion

I) a11

[" ] -2

Ar = -8

4

12

-10

=

3)

a11

2) A12 =G12

x2

0 0

•••••

•

0

0

••••

( 2)

.... 0. ( 3)

...... ......

tras rectas en zona no factible) son:

( 1)

Vemos que la regiOn

,.

(600,300) y (800,0)

cuenta con un nllmero infinite de --

puntas los cuales son soluciones a nuestro problema; el problema -

( 1)

de programaci6n lineal entonces es el de seleccionar de entre este

(4)

numero

( 5)

el cual como puede apreciarse representa un problema en el plano -

infinito de puntos, aquel

0

aquellos puntos (x~, x~)

que maximicen la funci6n objetiva Z

x

+ 2x . 2

1

La funci6n z~ x + 2x es una familia de rectas con un pa2 1 rametro (Z), esto es, la funci6n representa una familia de rectas-

(x 1 , x 2 ), lo cual nos permite representarlo graficamente. El primer paso en el metoda

~

(0, 600),

grafico es el de representar -

todos aquellos valores que son permitidos per las restricciones.

-

paralelas ( dependiente -1/2) tales que el valor de Z aumenta a medida que la recta se aleja del origen.

El sistema de desigualdades lineales que constituye las restriccio nes resulta en el conjunto convexo de puntas dado por el poligonoOABCD.

Cualquier punto (x, y) dentro de este pol1gono (region 0()

satisface el sistema de desigualdades (I).

Al poligono OABCD

' .-1-., ""' ~~"-


necesariamente es la que mas incrementa el valor de Z, debido a que las restricciones pueden impedir que su valor aumente tanto como

cuando dicha funci6n se encuentra en la forma:

z= c;_

x1 +

c;

x2

+ ... + c~

con variables con coeficientes menores, como puede apreciarse en el

(I)

xn

siguiente ejemplo:

Justificaci6n. CI

j

significa el coeficiente actual de la variable xj

en -

Ejemplo III-9.-

z

la funci6n objetiva. Es importante el recordar siempre que

X

e

es la variable nu-

la en la soluci6n basica factible actual que va a tamar un valor -

sera aquella variable no b3sica en Z que cuente con el rna

Esto es debido a que si c~

al incrementar xe, el valor de

z

= max Cj >

0,

parece incrementarse mas rapida--

mente que incrementando cualquier otra variable. El motive de introducir x

8

cuando menos existe un coeficiente

+

x1

~

x

~

2

= x

a la base es debido a que si

Cj

que sea positive en la ecua

cion (I), entonces es posible (suponiendo que todas las bi> 0) el

x

2

100 y sin embargo no es la variable que mas

1

incrementa el valor de Z. Paso 3.Determine la variable basica (xs) que dejara la base.

yor coeficiente entre aquellos con signa positive, estando Z en la forma indicada en (I).

1

8

La regla de selecci6n para xe tambien puede ser expresada 8

3x

Aqui se selecciona x

no nulo en la siguiente iteraci6n.

x

para

llegar a 1a soluci6n Optima.

que satisfaga la condici6n:

asi:

arbitr~

La

selecci6n de la variable de salida se determina, en general, per la seleccion de la variable de entrada (xe) junto con las restricciones.

Se escogera como

X

s

a aquella variable basica cuyo valor-

45

Del sistema de ecuaciones (II) vemos que el limite superior

se hara negative primero cuando el valor de la variable basica en-

para el valor que podra tamar xe en la ecuacion (j) sera:

trante (x ) se incrementa. e

~~

Justificaci5n. Debe quedar claro que xs es aquella variable no nula (basi-

Algebra1camente podemos interpretar el paso 3 como sigue:

¢=

a

b.

¢

min

( i )] i= 1, .. , n

si a! 1e

>

0

i

es decir, si cuando menos una a! 1e

actual de Z.

coeficiente actual de xe en la ecuaci6n

I

ie

incrernentar el valor de x

e

es positiva, no sera posible

indefinidamente, porque cuando

termino constante actual en la ecuaci6n ( i)

l

Dado que

= valor

0

sea

sea: Zl 0

0

2

co~--

=

z

p

que

¢2

rrespondiente a

L

)253

'100, nva(3)ant.(3)

'c¢:::

dnt

(2)

nuestra nueva soluci6n b§sica seril:

min

bilsica

variable no b§sicJ

la extrema derecha.

Marquese con un circulo el elemento aPe ejemplo ya

Q)

-

y

v~riable

se colocan en la columna a

nvu(O)=c.wt(O) +2 ant. (2) 600 nva(1)=allt.(1)

de donde P=2

(a

22

en nuestro-

y J.a variable co-

la segundct ecuaci6n es x

4

par lo que X

s

"3

600

x1

x2

300

x4

0

x5 =1200

=

z

= 600

x4). Paso 5.Paso

4.-

En

una

nueva

y p6ngase

tabla,

c§.mbiese x

la ecuaci6n i=P

4

par x

2

Revise la ecuaci6n

{0) para ver si

existe cllgGn coeficien

en la coLumd v.b. tc nc:gativo.

Vemos que C

(ecuaci6n correspondiente a -

1

-1 por lo tdnto nuestrJ so-

luci6n aGn no es Optima y se rcquiere otra x

8

)

iteraci6n.

En

dividida entre ape (es decir entre el coeficiente nuestra situientc iteruci6n x

de nuestro primer pivote)

en la nueva tabla.

En nuestro obtendremos la tabla:

caso ape =

por lo que obtendremos:

e

=x

1

y

x

s

x

5

con la que

52

v. b.

No.Ec.

z

x2

xi

v.b.

Po

x5

x4

x3

Ec.No.

7

h

xi

x3

x4

x5

0

no b.§.sicas

bdsicas

¢

I i/3 iOOO nva(O)=ant(O)+i/3 ant(3)

z

0

i

x3

i

0

0

0

i

x2

2

0

0

i

0

i

0

300 nva(2)

ant(2)

xi

3

0

i

0

0

f4n

i/3

400 nvu(3)

i/3 ant(3)

2/3

0

0

0

z

0

i

-2

5

0

0

0

0

..

1

0

i

0

i

0

0

l[

2

0

0

CD

0

1

0

3

3

xs

3

0

i

2

0

0

i

8

4

z

200 nva(i)=ant(i)-i/3 ant(3)

4/3 1/3

X

~

4

x5

X

(0) no

tiene ya

X

~jercicio

v.b.

t:c . ;~ o.

variable no b§sica

b.3sica

'"

xi

x2

x3

x4

xs

Po

0

z

0

1

-7

0

0

5

0

i5

X~

300

x'~

0

x3

1

0

i

0

i

0

0

4

200

x2

2

0

0

1

0

i

0

3 00

iOOO

x5

3

0

@

0

0

-2

i

2

X

Sea el problcmd de M0ximizar Z

llrogrdmaci6n

2x

i

+

Sx

lineal

siguiente:

X

v.b. ~ L!

x

7

+2x

2

e

x1

s

x5

I I

= '+

x3

b§sicas

xi

= 0

x4

0

x5

z

2

=iS

Ec.No.

z

z

x1

x2

x3

x4

xs

Po

0

i

0

0

0

i

2

19

i

0

0

0

i

2

-i

2

no

b.§sicas

Z'''

19

x''i =

2

~

-

X

2

3

x2

I

2

0

0

i

' '

0

1

0

3

x•';

0

-2

1

2

x•'•

2:

x1

j

x2 4

no

7

sujeto u:

X

tasicds

X~

Ifl-1.-

x1

¢

400

=

x2

x4

s

x'[

x•'3• z,·,

xi

x4

ningGn coeficiente negativo-

nuestra soluci6n sera Optima: variable

00

X}

('

como nuestra ecuaci6n

4

x3

xi

3

0

1

0

b,l:sicas

x''4

= 0

I xt'

= 0

2

3

=

x2 Utilice el m~todo del pivote para

encontrar la soluci6n Optima.

COMPLICACIONES.E~

muchas ocaciones nos encontramos

con que al

nuestro modelo rnatemdtico este aparece con algunas respecto al

modelo general

que

hemos analizado

constuir

-·-

variaciones con

hasta

el momento.

53

A continuaci6n veremos mente encontradas y implique que no te,

cuales son las variaciones mas comUn

las trataremos

individualmente,

se pueden presentar varias de

en cuyo caso se aplican en forma

sin que ello -

ellas simult§neamen-

sucesiva los metodos que

se

-

describir§n para solucionar estas variaciones. Las

variaciones mas

to que el ajuste al m€todo simplex en este caso sera: Se escogera como variable entrante (x ) a aquella variable no b§sica que ?isminuira m§s r.§.pidamente el valor de Z cuandoeesta variable adquiere un valor -positive. La variable de salida (x ) se escoger.§. en la misma forma que antes. Laprueba de optim.:1lid.J.d con.sistirS. c~ rcvisar si el valor de Z puede aU.n ser dismi-nuido al incrementar el valor de una variable no b§sica (estando la funciOn objeti va s6lo en funciOn de i§stas variables). b) Supongamos que tenernos: Z = f (x , x , ... , x ) 1 2 0 que nos representa nucstru. funciOn objetivu. lu cual deseamos minimizar. Si recor-damos que: f = -(-f) y que si f ~ (-f) tendremos que: min f = - [max (-f) J por lo que al minimizar una funci6n objetiva sujeta a una serie de restricciones es completamente equivalente a maximizar el negative de 1.:1 funciOn sujeta a las -mismas restricciones, con la salvedad de que el minima valor de Z buscado sera --igual al negativo del rn.3.ximo valor de Z encontrado.

comunes son:

1.

Minimizaci6n.

2.

Desigualdad con sentido

3.

Constantes negativas

4.

Igualdades.

5.

Variables no restringidas en signa.

6.

Empate para entrar como variable b§sica.

7.

Empate para dejar la base.

f

=T

invertido.

(bi