guia de estudio

ESTUDIS D’ECONOMIA I EMPRESA

INVESTIGACIÓ OPERATIVA
Mòdul 2

Guia d’estudi 2 – GES2

L’ALGORITME SíMPLEX



Presentació



Objectius específics



Coneixements previs



Conceptes fonamentals



Exercicis tipus



Fe d’errates del material propi: mòdul 2



Bibliografia

ESTUDIS D’ECONOMIA I EMPRESA
INVESTIGACIÓ OPERATIVA
Guia d’estudi 2Presentació
En aquesta GES ens introduirem en els principals conceptes associats a l’algoritme símplex, el
qual fou desenvolupat el darrer segle, al final de la dècada dels anys 40, per l’investigador
George Dantzig. No ens podem estar de mencionar que l’aparició d’aquesta eina representà una
autèntica revolució en l’anàlisi dels problemes de PL.
En relació a la nostra assignatura, cal destacar queaquest mòdul és molt important per al
desenvolupament del semestre atès que els conceptes que en formen part estan presents en la
resta dels mòduls de l'assignatura.

Objectius específics
Per aquest mòdul ens marquem com a objectiu assolir els conceptes i tècniques bàsiques de
l’algoritme símplex. Com a objectius específics del mòdul en destaquem:


Saber formular un problema PL en lesseves formes canònica, estàndard i ampliada.



Entendre el significat econòmic de les variables de decisió, les folgances i les variables
artificials.



Conèixer en profunditat l’algoritme símplex en la seva forma tabular, i les
relacions entre els elements de les taules símplex.



Classificar les variables d’un PL en variables bàsiques i no bàsiques, i obtenir el seus
valors deles taules símplex.



Saber identificar en una taula símplex els diferents tipus de solució que pot tenir un
problema (pròpia, impròpia, ...).

Coneixements Previs
Els coneixements previs a tenir presents són els associats al Mòdul 1 d’aquesta mateixa
assignatura. És important continuar treballant els exercicis del mòdul 1 de la miscel·lània de
problemes resolts referents a laformulació de models de PL.

Conceptes Fonamentals
El primer apartat d’aquest mòdul, anomenat L’algoritme Símplex, està dedicat a la "formulació
estàndard" o "forma estàndard" d'un problema PL. Com podreu observar les variables de
folgança (pàg. 10) hi juguen un paper clau. D'altra banda és bo habituar-se a la notació
matricial perquè ens serà de molta utilitat en el darrer mòdul de l’assignatura.El concepte més important del segon apartat és el concepte de vèrtex. El resultat clau és aquell
on s'expressa la relació entre vèrtex i òptim d’un PL. Ens referim al Teorema 2 de la pàgina 15.
El nostre interès no és aprendre a resoldre problemes mitjançant el mètode símplex
per matrius (apartat 3.1) i per això no hi esmerçarem gaire esforços. Malgrat això, no
perdrem de vista, però, lesfórmules que permeten resoldre un problema mitjançant l'algoritme
símplex matricial.
Allò que hem de considerar més important del mòdul radica en conèixer les tècniques
de resolució de problemes mitjançant l'algoritme símplex tabular (apartat 3.2). És un
Semestre set11 – feb12

2

ESTUDIS D’ECONOMIA I EMPRESA
INVESTIGACIÓ OPERATIVA
Guia d’estudi 2
apartat clau en el desenvolupament del’assignatura. En l’aplicació de l’algoritme símplex tabular
cal tenir molt clar com es tria l’element pivot i com es realitza una pivotació (pàg. 31 i 32). En
relació a la manera de fer una pivotació, veureu que, resumint, una iteració de l'algoritme
símplex tabular consisteix primer, en escollir adequadament un pivot; a continuació, convertir
l’element pivot en un 1 tot dividint la seva fila pelvalor del pivot; finalment, fer pivotacions o
operacions entre files a fi i a efecte de convertir en zeros la resta dels elements de la columna
(inclòs l’element Zi-Ci) del pivot. Aquesta manera de fer zeros és molt semblant a la manera de
fer zeros en el procés de resolució de sistemes d’equacions lineals pel mètode de Gauss. D’altra
banda, sempre cal tenir molt present que geomètricament...