*Faculdade de Engenharia - Campus de GuaratinguetPesquisa Operacional

Livro: Introduo Pesquisa OperacionalCaptulo 2 - Programao Linear

Fernando Marins fmarins@feg.unesp.brDepartamento de Produo

Sumrio

*

Modelagem e limitaes da Programao Linear.

Resoluo Grfica.

Forma padro de um modelo de Programao Linear.

Definies e Teoremas.

Forma cannica de um sistema de equaes lineares.

Mtodo Simplex. Exerccios

*

Programao Linear: Preocupao em encontrar a melhor soluo para problemas associados com modelos lineares.

Modelo de Programao Linear: Maximizao (ou minimizao) de uma funo objetivo linear com relao as variveis de deciso do modelo.Respeitando-se as limitaes (restries) do problema expressas por um sistema de equaes e inequaes associadas com as variveis de deciso do modelo.Programao Linear

Modelagem em Programao Linear*Razes para o uso da Programao Linear:

Grande variedade de situaes podem ser aproximadas por modelos lineares.

Existncia de tcnicas (algoritmos) eficientes para a soluo de modelos lineares.

Possibilidade de realizao de anlise de sensibilidade nos dados do modelo.

Estgio de desenvolvimento da tecnologia computacional.

Modelagem em Programao Linear*Passos bsicos na obteno de modelos de PL:

Identificar as variveis de deciso, represent-las em simbologia algbrica.

Identificar as restries do problema, express-las como equaes ou inequaes lineares em termos das variveis de deciso.

Identificar o objetivo de interesse no problema, represent-lo como funo linear em termos das variveis de deciso, que dever ser maximizada ou minimizada.

Modelagem em Programao Linear*Construo de modelos no uma cincia, mas uma arte, podendo ser melhorada com a prtica.

Exemplos a serem trabalhados:

Determinao do mix de produoSeleo de mdia para propagandaUm problema de treinamentoUma indstria qumicaUma oficina mecnicaDimensionamento de equipes de inspeo

Modelagem em Programao Linear

*Determinao do mix de produo

Uma companhia deseja programar a produo de um utenslio de cozinha que requer o uso de dois tipos de recursos mo-de-obra e material. A companhia est considerando a fabricao de trs modelos e o seu departamento de engenharia forneceu os dados a seguir:O suprimento de material de 200 kg por dia. A disponibilidade diria de mo-de-obra 150 horas. Formule um modelo de Programao Linear para determinar a produo diria de cada um dos modelos de modo a maximizar o lucro total da companhia.

ModeloABCMo-de-obra(horas por unidade)736Material(kg por unidade)445Lucro($ por unidade)423

Modelagem em Programao Linear*Formulao do modelo

Identificao das variveis de deciso:XA produo diria do modelo AXB produo diria do modelo BXC produo diria do modelo CIdentificao das restries:Identificao do objetivo: maximizao do lucro totalLucro Total = L = 4XA + 2XB +3XCMax L = 4XA + 2XB +3XC

Modelagem em Programao Linear

*ModeloEncontrar nmeros XA, XB, XC tais que:

Max L= 4XA + 2XB +3XC

Sujeito as restries: 7XA + 3XB +6XC 150 4XA + 4XB +5XC 200XA 0, XB 0, XC 0

Modelagem em Programao Linear

*Seleo de mdia para propaganda

Uma companhia de propaganda deseja planejar uma campanha em 03 diferentes meios: TV, rdio e revistas. Pretende-se alcanar o maior nmero de clientes possvel. Um estudo de mercado resultou em:0bs: valores vlidos para cada veiculao da propaganda.

TV horrioTV horrioRdioRevistasnormalnobreCusto40.00075.00030.00015.000ClientesAtingidos400.000900.000500.000200.000MulheresAtingidas300.000400.000200.000100.000

Modelagem em Programao Linear

* A companhia no quer gastar mais de $ 800.000 e, adicionalmente, deseja:(1) Que no mnimo 2 milhes de mulheres sejam atingidas;(2) Gastar no mximo $ 500.000 com TV;(3) Que no mnimo 03 veiculaes ocorram no horrio normal TV;(4) Que no mnimo 02 veiculaes ocorram no horrio nobre TV;(5) Que o n. de veiculaes no rdio e revistas fiquem entre 05 e 10, para cada meio de divulgao. Formular um modelo de PL que trate este problema, determinando o n. de veiculaes a serem feitas em cada meio de comunicao, de modo a atingir o mximo possvel de clientes.

Modelagem em Programao Linear

*Resoluo do exemplo seleo de mdia para propagandaVariveis de deciso:X1 = n. de exposies em horrio normal na tv.X2 = n. de exposies em horrio nobre na tv.X3 = n. de exposies feitas utilizando rdioX4 = n. de exposies feitas utilizando revistas.Funo-objetivo:Maximizar n. de clientes atingidosMax Z = 400.000X1 + 900.000X2 + 500.000X3 + 200.000X4

Modelagem em Programao Linear

*Restries:Oramento:40.000X1 + 75.000X2 + 30.000X3 + 15.000X4 800.000Mulheres atingidas:300.000X1 + 400.000X2 + 200.000X3 + 100.000X4 2.000.000Gasto com TV40.000X1 + 75.000X2 500.000N. de veiculaes em TV, rdio e revistas X1 3, X2 2, 5 X3 10, 5 X4 10No-negatividadeX1, X2, X3, X4 0.

Modelagem em Programao Linear

*Um problema de treinamento

Uma empresa de mquinas ferramentas tem um programa de treinamento para operadores de mquinas. Alguns operadores j treinados podem trabalhar como instrutores neste programa ficando responsveis por 10 trainees cada. A empresa pretende aproveitar apenas 07 trainees de cada turma de 10.

Estes operadores treinados tambm so necessrios na linha de fabricao, e sabe-se que sero necessrios para os prximos meses: 100 operadores em janeiro, 150 em fevereiro, 200 em maro, e 250 em abril. Atualmente h 130 operadores treinados disponveis na empresa.

Modelagem em Programao Linear

*Encontrar um modelo de PL que fornea um programa de treinamento de custo mnimo e satisfaa os requisitos da empresa em termos de n. de operadores treinados disponveis a cada ms.

Observao: acordo firmado com o sindicato probe demisses de operadores treinados no perodo. Os custos associados a cada situao so:

Trainees ...........................................................................$ 400.Operador treinado trabalhando ........................................$ 700.Operador treinado ocioso..................................................$ 500.

Modelagem em Programao Linear

*Variveis de deciso:X6 = operadores ociosos em maroX5 = operadores trabalhando como instrutores em maroX4 = operadores ociosos em fevereiroX3 = operadores trabalhando como instrutores em fevereiroX2 = operadores ociosos em janeiroResoluo do exemplo: Um problema de treinamento

Observe que a cada ms um operador treinado est: operando mquina, trabalhando como instrutor, ou est ocioso. Alm disto, o n. de operadores treinados trabalhando nas mquinas fixo e conhecido: 100 em janeiro, 150 em fevereiro, 200 em maro e 250 em abril.X1 = operadores trabalhando como instrutores em janeiro

Modelagem em Programao Linear

*Funo-objetivo:Min C = 400(10X1 + 10X3 + 10X5) + 700(X1 + X3 + X5) + + 500(X2 + X4 + X6) + 700(100 + 150 + 200)

Min C = 4700X1 +500X2 + 4700X3 +500X4 +4700X5 +500X6 + 315.000

Custo total = custo trainees + custo instrutores + custo ociosos + custo operadores trabalhando em mquinas.

Modelagem em Programao Linear

*Restries: X1, X2, X3, X4, X5, X6 0 (no-negatividade) Abril: 250 = 130 + 7X1 + 7X3 + 7X5 7X1 + 7X3 + 7X5 = 120.operadores treinados no incio do ms = operadores nas mquinas + instrutores + operadores ociosos.Equao de balano mensal: Janeiro: 130 = 100 + X1 + X2 X1 + X2 = 30 Fevereiro: 130 + 7X1 = 150 + X3 + X4 7X1 - X3 - X4 = 20 Maro: 130 + 7X1 + 7X3 = 200 + X5 + X6 7X1 + 7X3 - X5 - X6 = 70

Modelagem em Programao Linear

*Uma indstria qumica

Dois produtos, A e B, so feitos a partir de duas operaes qumicas. Cada unidade do produto A requer 02 horas da operao 1 e 03 horas da operao 2. Cada unidade do produto B requer 03 horas da operao 1 e 04 horas da operao 2. O tempo total disponvel para a realizao da operao 1 de 16 horas, e o tempo total para a operao 2 de 24 horas.

A produo do produto B resulta, tambm, num subproduto C sem custos adicionais. Sabe-se que parte do produto C pode ser vendido com lucro, mas o restante deve ser destrudo. Previses mostram que no mximo 05 unidades do produto C sero vendidas, e sabe-se que cada unidade do produto B fabricada gera 02 unidades do produto C.

Modelagem em Programao Linear

*Sabe-se que:

Produto A gera um lucro de $ 4 por unidade.Produto B gera um lucro de $ 10 por unidade.Produto C gera um lucro de $ 3 por unidade se for vendido.Produto C gera um custo de $ 2 por unidade se for destrudoDeterminar um modelo de PL para tratar este problema, e encontrar quanto produzir de cada produto, de modo a maximizar o lucro da indstria qumica.

Modelagem em Programao Linear

*Observe que o lucro da venda do produto A uma funo linear, mas com respeito ao produto C isto no ocorre.Resoluo do exemplo: Uma indstria qumica - produto A

Modelagem em Programao Linear

*2 X1 + 3 X2 16 (disponibilidade de tempo para operao 1)3 X1 + 4 X2 24 (disponibilidade de tempo para operao 2)X3 + X4 = 2 X2 (produo do produto C a partir do produto B)X3 5 (previso de produto C que pode ser vendido)X1, X2, X3, X4 0 (no-negatividade)Restries:Artifcio: considerar as variveis de deciso como sendoX1 = quantidade produto A produzidaX2 = quantidade produto B produzidaX3 = quantidade produto C vendidaX4 = quantidade produto C destrudaFuno-objetivo:Max Z = 4 X1 + 10 X2 + 3 X3 2 X4

Modelagem em Programao Linear

*Oficina mecnica

Uma oficina mecnica tem 01 furadeira vertical e 05 fresas, que so usadas para a produo de conjuntos formados de 2 partes. Sabe-se qual a produtividade de cada mquina na fabricao destas partes do conjunto:Obs: tempo para produzir as partes dado em minutos.

FuradeiraFresaParte 10320Parte 20515

Modelagem em Programao Linear

*O encarregado pela oficina deseja manter uma carga balanceada nas mquinas de modo que nenhuma delas seja usada mais que 30 minutos por dia que qualquer outra, sendo o carregamento de fresamento dividido igualmente entre as 05 fresas.

Achar um modelo de PL para dividir o tempo de trabalho entre as mquinas de modo a obter o mximo de conjuntos completos ao final de um dia, num total de 08 horas de trabalho.

Modelagem em Programao Linear

*Restries:3X1 + 5X2 480 (minutos por dia disponveis para a furadeira)

(20X1 + 15X2)/5 = 4X1 + 3X2 480 (minutos por dia disponveis para cada fresa)

Resoluo do exemplo: Oficina mecnicaVariveis de deciso:X1 = nmero de partes 1 produzidas por diaX2 = nmero de partes 2 produzidas por dia

Modelagem em Programao Linear

*Observe que esta ltima restrio no linear, mas equivalente a duas equaes lineares que podem substitu-la:

X1 - 2X2 30 e -X1 + 2X2 30

X1, X2 0 (no-negatividade).

|(4X1 + 3X2) - (3X1 + 5X2)| = |X1 -2X2| 30 (Balanceamento de carga entre as mquinas)

Modelagem em Programao Linear

*maximizao do nmero de conjuntos completos por diaMax Z = min (X1, X2)

Observe que esta funo no linear, mas pode ser linearizada utilizando-se uma nova varivel, da forma:

Seja Y = min (X1, X2), Y 0, naturalmente tem-se duas novas restries

Dadas por: Y X1 e Y X2.

A funo-objetivo linear fica sendo: Max Z = YFuno-objetivo:

Modelagem em Programao Linear

*Problema de dimensionamento de equipes de inspeo

Uma companhia deseja determinar quantos inspetores alocar uma dada tarefa do controle da qualidade. As informaes disponveis so:

H 08 inspetores do nvel 1 que podem checar as peas a uma taxa de 25 peas por hora, com uma acuracidade de 98%, sendo o custo de cada inspetor deste nvel $4 por hora;

H 10 inspetores do nvel 2 que podem checar as peas a uma taxa de 15 peas por hora, com uma acuracidade de 95%, sendo o custo de cada inspetor deste nvel $3 por hora.

Modelagem em Programao Linear

*A companhia deseja que no mnimo 1800 peas sejam inspecionadas por dia (= 08 horas).

Sabe-se, ainda, que cada erro cometido por inspetores no controle da qualidade das peas acarreta um prejuzo companhia de $2 por pea mal inspecionada.

Formular um modelo de PL para possibilitar a designao tima do n. de inspetores de cada nvel de modo a otimizar o custo da inspeo diria da companhia.

Modelagem em Programao Linear

*Funo objetivo:

Minimizar C = custo total dirio de inspeo ($/dia)onde : custo total = custo do salrio dos inspetores + custo dos erros

Min C = 8 *[(4X1 + 3X2) + 2 * (25*0,02X1 + 15*0,05X2)] Min C = 40X1 + 36X2Resoluo do exemplo: Dimensionamento de equipes de inspeoVariveis de deciso:Xi = n. de inspetores do nvel i (= 1, 2) alocados inspeo.

Modelagem em Programao Linear

*Quanto ao n. de inspetores disponveis:X1 8 (inspetores do nvel 1)X2 10 (inspetores do nvel 2)2. Quanto ao n. de peas inspecionadas por dia:8 * (25X1 + 15X2) 1800 5X1 + 3X2 453. Restries implcitas de no negatividade:X1 0X2 0. Restries:

Resoluo grfica de modelos de PL*Aplicvel para modelos com 02 variveis de deciso

til para a ilustrao de alguns conceitos bsicos utilizados na resoluo de modelos de maior porte.Etapas a serem seguidas na resoluo grfica

1 Passo: identificar a regio vivel do modelo, isto , quais so os pares (X1, X2) que satisfazem a todas as restries.

2 Passo: achar a melhor soluo vivel, denominada Soluo tima e denotada por (X1*, X2*), que leva ao valor timo da funo-objetivo Z*.

Resoluo grfica de modelos de PL

*Problema de mix de Produo

Fabricao de dois modelos de brinquedos: B1 e B2. Lucros unitrios/dzia: $8 para B1 e $5 para B2 Recursos disponveis:1000 kg de plstico especial.40 horas para produo semanal.

Requisitos do Departamento de Marketing: Produo total no pode exceder 700 dzias; A quantidade de dzias de B1 no pode exceder em 350 a quantidade de dzias de B2.

Dados tcnicos: B1 requer 2 kg de plstico e 3 minutos por dzia. B2 requer 1 kg de plstico e 4 minutos por dzia.

Resoluo grfica de modelos de PL

*A Gerncia est procurando um programa de produo que aumente o lucro da Companhia.

Resoluo grfica de modelos de PL

*Variveis de deciso:X2: produo semanal de B2 (em dzias).X1: produo semanal de B1 (em dzias).Funo Objetivo: Maximizar o Lucro semanal

Resoluo grfica de modelos de PL

*Max 8X1 + 5X2 (Lucro semanal)

sujeito a:2X1 + 1X2 1000 (Plstico - Kg)3X1 + 4X2 2400 (Tempo de produo - minutos) X1 + X2 700 (Produo total) X1 - X2 350 (mix) Xj 0, j = 1,2 (No negatividade)

Resoluo grfica de modelos de PL*Conceitos importantes:Os pontos (X1, X2) que satisfazem todas as restries do modelo formam a Regio Vivel.Esses pontos so chamados de Solues Viveis.

Usando a resoluo grfica pode-se representar todos as restries (semi-planos), a funo objetivo (reta) e os trs tipos de pontos viveis.

Resoluo grfica de modelos de PL

*1 Passo:

Traar eixos cartesianos, associando a cada um deles uma varivel de deciso.

No exemplo de fabricao de brinquedos: X1 para o eixo das abscissas e X2 para o eixo das ordenadas.

As restries de no-negatividade, X1 0 e X2 0, implicam que os pares (X1, X2) viveis esto no 1 quadrante dos eixos considerados.

Resoluo grfica de modelos de PL

*2 Passo:

Observar que a funo-objetivo, ao se fixar um valor para Z, representa uma reta. Alteraes neste valor de Z gera uma famlia de retas paralelas.

No exemplo dos brinquedos: considere a reta obtida fazendo Z= 2000, isto , a reta dada por 8X1 + 5X2 = 2000. Percebe-se que ao se traar retas paralelas no sentido de ficar mais afastado da origem (0, 0), o valor de Z aumenta. De fato pode-se verificar que a reta paralela, que contm algum ponto da regio vivel, no caso o ponto timo X* = (320, 360), e est mais afastada da origem, corresponde a um valor timo da funo objetivo Z* = 4360.

Resoluo grfica de modelos de PL

*Representando as condies de no negatividade X2X1

Resoluo grfica de modelos de PL*Pesquisa Operacional - UNESP / Campus de GuaratinguetObservar que no exemplo dos brinquedos, as restries correspondem a semi-planos associados, respectivamente, s retas suportes dadas por:

2X1 + 1X2 = 1000 3X1 + 4X2 = 2400 X1 + X2 = 700 X1 - X2 = 350 Xj 0, j = 1,2

Notar que cada reta suporte define dois semi-planos no espao (X1, X2).Para identificar qual destes semi-planos de interesse no caso, ou seja, contm os pontos que satisfazem a desigualdade da restrio, basta testar algum ponto esquerda ou direita (acima ou abaixo) da reta suporte da desigualdade. Um ponto que torna isto fcil a origem (0, 0), mas poderia ser qualquer outro.

Resoluo grfica de modelos de PL

*1000500VivelX2InvivelTempo de produo3X1+4X2 2400Restrio da produo total X1+X2 700 (redundante)500700X1700

Resoluo grfica de modelos de PL

*1000VivelX2InvivelTempo de Produo3X1+4X2 2400 Restrio da produo total: X1+X2 700 (redundante)500Restrio do mix da produo:X1-X2 350Restrio do plstico2X1+X2 1000X1700

Resoluo grfica de modelos de PL*1000500VivelX2Invivel500700X1700H trs tipos de pontos viveis.Pontos interiores. Pontos na fronteira. Pontos extremos.

Resoluo grfica de modelos de PL

*A busca por uma Soluo tima:Comear com algum valor de lucro arbitrrio, Por exemplo $2000...Depois aumentar o lucro, se possvel......e continuar at que seja invivel6007001000500X2X1X* = (320, 360) com Z* = 4.360

*Pontos extremos e Solues timasSe o problema de Programao Linear tem uma Soluo tima, um ponto extremo Soluo tima.

Resoluo grfica de modelos de PL

Resoluo grfica de modelos de PL

*Visualizao de situaes possveis X2

Resoluo grfica de modelos de PL

*Solues timas MltiplasQuando a funo objetivo paralela a alguma restrio.Todos os pontos do segmento de reta sero Solues timas.X* = X*1 + (1 - )X*2, com 0 1

Resoluo grfica de modelos de PL

*Mltiplas Solues timas 1 Segmento de Reta timoX1X*

Resoluo grfica de modelos de PL

*O conjunto vivel vazio. H restries incompatveis.Problema invivel

Forma padro de modelo de PL

*

Um modelo de PL com m restries e n variveis est na forma padro se possuir as caractersticas abaixo:

A funo-objetivo de minimizao ou maximizao;

Todas as restries esto na forma de igualdade;

Todas as variveis so no-negativas;

As constantes de cada restrio so no-negativas.

Forma padro de modelo de PL

*Modelo na forma padro:

Minimizar (ou maximizar) Z = C1 X1 + C2 X2 + ... + Cn Xn

Sujeito a:

*Notao matricial para um modelo na forma padro:

Minimizar (ou maximizar) Z = C X

Sujeito a: Onde: A (m x n) matriz de coeficientes tecnolgicos

X (n x 1) vetor das variveis de deciso

b (m x 1) vetor de demandas C (1 x n) vetor de custos (lucros) Forma padro de modelo de PL

*Reduo de um modelo geral para a forma padro

O Mtodo Simplex exige que o modelo esteja na forma padro.

Tratando com restries na forma de inequaes:

Estas restries so transformadas em equaes atravs da introduo de novas variveis (no-negativas), chamadas de variveis de folga.Forma padro de modelo de PL

Forma padro de modelo de PL

*Tratando com variveis no-positivas:

Suponha que num determinado modelo h uma varivel X1 0.

Basta substitu-la no modelo por uma nova varivel no-negativa X1 0, dada por X1 = X1.

Forma padro de modelo de PL

*Exemplo:

Considere o problema de dimensionamento de equipes de inspeo: X1 8 X1 + X3 = 8, X3 0 uma varivel de folga.X2 10 X2 + X4 = 10, X4 0 uma varivel de folga.5 X1 + 3 X2 45 5 X1 + 3 X2 X5 = 45, X5 0 uma varivel de folga.

Forma padro de modelo de PL

*Interpretao das variveis de folga no exemplo:X3 = nmero de inspetores do nvel 1 no utilizados.X4 = nmero de inspetores do nvel 2 no utilizados.X5 = nmero (extra) de peas inspecionadas por dia, acima da quantidade mnima (1800) especificada pela empresa

Variveis de folga fornecem informaes teis sobre o problema.

Forma padro de modelo de PL*Tratando com variveis livres (irrestritas em sinal):

Em algumas situaes exige-se o uso de variveis que podem assumir tanto valores positivos, nulos, e negativos. Estas variveis so chamadas de livres (free) ou irrestritas em sinal.

Exemplo: Modelo de Planejamento Macroeconmico

Uma das Variveis de Deciso a Taxa de Inflao que pode assumir qualquer valor positivo, nulo ou negativo (neste caso conhecida como Deflao).

Tratando com variveis livres (irrestritas em sinal):

*Estas variveis devem ser eliminadas do modelo na forma padro. H, pelo menos, duas maneiras de se fazer isto:

1. Por substituio utilizando uma das restries do modelo, j na forma padro (igualdade), procura-se expressar a varivel livre como funo das demais variveis (no negativas) do modelo. A seguir eliminar a varivel livre do modelo substituindo-a pela funo escolhida na etapa anterior. A equao utilizada para expressar a varivel livre como funo das demais variveis tambm ser eliminada do modelo.

2. Por transformao Suponha que a varivel livre S. Basta substituir em todas as restries, e na funo objetivo, a varivel S por S = S S, com S 0 e S 0 sendo duas novas variveis (auxiliares) no modelo.

Forma padro de modelo de PL

Exemplo Completo

Obtenha a forma padro do modelo abaixo:

Maximizar Z = X1 2X2 + 3X3

Sujeito a: *

Forma padro de modelo de PL

*

1. Introduzir variveis de folga nas restries (1) e (2):

X1 + X2 + X3 + X4 = 7 (1) com X4 0.X1 X2 + X3 X5 = 2 (2) com X5 0.

2. Multiplicar a restrio (3) por ( 1) para eliminar b3 = 5 < 0:3X1 + X2 + 2X3 = 5 (3)

3. Substituir X2 0 por X2 0 atravs de X2 = X2:Max Z = X1+ 2 X2 + 3 X3

Sujeito a:

Forma padro de modelo de PL

*4. Eliminar X3:

4.1. Substituio ou 4.2. Transformao

Max Z = -2X1 + 5X2 - 3X4 + 21 ou Max Z = X1 + 2X2 + 3X3 - 3X3

s. a: s. a:

UsandoDe (1): X3 = 7 X1 + X2 X4 ou X3 = X3 X3

Definies e Teoremas em PL

*Ponto central na resoluo de modelos de PL a soluo de sistemas de equaes lineares.

Apresenta-se a seguir o Mtodo de Eliminao de Gauss Jordan.

Considere o sistema de equaes abaixo:

(S1)

(n variveis >> n equaes)

Definies e Teoremas em PL

*Conjunto soluo de (S1) a coleo de todos os valores de (X1, X2, X3, X4, X5) que satisfazem as equaes (1) e (2) conjuntamente.

Dois sistemas so equivalentes se possuem o mesmo conjunto soluo.

Sistemas equivalentes podem ser obtidos por meio de operaes elementares sobre as linhas do sistema:

1. Multiplicar (dividir) qualquer equao por um n.

2. Adicionar qualquer equao uma Combinao Linear das demais equaes.

Forma Cannica

*Um sistema (S2) equivalente a (S1) pode ser obtido multiplicando-se a equao (1) por 1 e adicionando-se o resultado equao (2):

(S2)

Um sistema (S3) equivalente a (S1) pode ser obtido multiplicando-se equao (4) por 2 e adicionando-se o resultado equao (3):

(S3)

(S3) denominado uma forma cannica do sistema original (S1).

Forma Cannica

*Considere uma forma cannica de um sistema de equaes lineares: (como (S3) anteriormente obtido)

Uma varivel dita ser varivel bsica para uma dada equao do sistema se ela possuir coeficiente 1 nesta equao e coeficientes nulos nas demais equaes do sistema.

Exemplo: em (S3) X1 e X2 so variveis bsicas

Variveis que no satisfazem a condio acima so chamadas de variveis no-bsicas.

Exemplo: em (S3) X3, X4, X5 so variveis no-bsicas.

Soluo Bsica*A soluo de um sistema na forma cannica, obtida fazendo-se as variveis no-bsicas iguais a zero, chamada de uma soluo bsica (SB). N mximo de solues bsicas =

Exemplo: Em (S3) fazendo-se X3 = X4 = X5 = 0 X1 = 6 e X2 = 2 formam uma soluo bsica.

N de solues bsicas = = 10

Uma Soluo Bsica Vivel (SBV) de um sistema uma soluo bsica onde todas as variveis assumem valores no-negativos.

Exemplo: a soluo bsica do exemplo anterior uma SBV.

Pivoteamento

*Operaes de Pivoteamento so as operaes elementares aplicadas um sistema para transformar uma dada varivel em varivel bsica. So usadas pelo mtodo de eliminao de Gauss Jordan. Deve-se identificar o elemento Piv que deve ser transformado em 1 e os demais elementos da sua coluna que devem ser transformados em 0.

Para obter uma forma cannica de um sistema basta aplicar uma sequncia de operaes de pivoteamento (mtodo de Gauss Jordan) de modo se conseguir uma varivel bsica associada com cada equao.

Mtodo de Eliminao de Gauss Jordan

*Artifcio para a realizao de operaes de pivoteamento:

Considere o sistema (S) abaixo:

(S) Achar (S) uma forma cannica de (S) de modo que X1 seja a varivel bsica associada com a equao (1), e X3 seja a varivel bsica associada com a equao (2).

Mtodo de Eliminao de Gauss Jordan

*VB X1 X2 X3 b Operaes Elementares Feitas

X1 2 -2 6 4 (1) - Piv em azul

X3 -1 4 -1 2 (2)(S)

Soluo bsica (no vivel): X1 = 4 (Varivel bsica)X3 = 2 (Varivel bsica) X2 = 0 (Varivel no bsica) X1 1 -11/2 0 -4 (1) = (1) - 3*(2)

X3 0 3/2 1 2 (2) = (2)/2 Equao do Piv

Teoremas em PL

*Teorema 1

Dado um modelo j na forma padro, as solues bsicas viveis do sistema de equaes, correspondente s restries do modelo, esto associadas a pontos extremos do conjunto de solues viveis do modelo original.

Teorema 2

Se um modelo de Programao Linear possui Soluo tima ento pelo menos um ponto extremo, do conjunto de solues viveis do modelo original, corresponde a uma Soluo tima.

Comentrios Gerais

*Procedimento simplista para resolver um modelo de PL

Gerar todas as possveis solues bsicas viveis.

Determinar qual das solues bsicas viveis corresponde ao melhor valor da funo-objetivo.

Problemas:1. N de solues bsicas viveis pode ser excessivo.

2. Modelo pode apresentar soluo ilimitada ou ainda ser invivel.

Observe que problemas de mdio porte, que aparecem na prtica, costumam envolver centenas de variveis (valor de n) e milhares de restries (valor de m).

Comentrios Gerais

*Linhas de Pesquisa

Algoritmos de pontos interiores e suas derivaes.Implementaes de algoritmos para processamento em paralelo.Linguagens de modelagem: ajudar no desenvolvimento e aplicao de modelos de Pesquisa Operacional.

Exemplos:

AMPL - Modeling Language for Mathematical Programming - R. Fourer, D. M. Gay, and B. W. Kerningham, 1993.

GAMS - General Algebraic Modeling System - J. Bisschop and A. Meeraus, 1982.

Whats best - The ABC of Optimization - S. L. Savage, 1992.

Mtodo Simplex

*Procedimento iterativo que resolve qualquer modelo de PL num nmero finito de iteraes. Indica a ocorrncia de mltiplas Solues timas, soluo ilimitada, e problema invivel.

Etapas de aplicao do Mtodo Simplex

Considere um modelo de PL que esteja na forma padro, e uma Soluo Bsica Vivel inicial.

O Mtodo Simplex consiste basicamente da aplicao sucessiva de duas etapas:

Etapa A: Identificao de uma Soluo tima.

Etapa B: Melhoria de uma Soluo Bsica Vivel.

Mtodo Simplex *Etapa A: Identificao de uma Soluo tima.

Verificar se a Soluo Bsica Vivel atual satisfaz o critrio de otimalidade do algoritmo:Se o critrio for satisfeito termina a aplicao do mtodo;Caso contrrio deve-se aplicar a etapa B.

Etapa B: Melhoria de uma Soluo Bsica Vivel.Procurar obter uma Soluo Bsica Vivel melhor que a atual:Determinao da varivel no-bsica que deve entrar;Determinao da varivel bsica que ser substituda;Obteno da nova Soluo Bsica Vivel - atravs de operaes de pivoteamento.

Mtodo Simplex - Minimizao

*Desenvolvimento do Mtodo Simplex

Seja um modelo de PL (minimizao) colocado na forma padro:Min Z = C1 X1 + C2 X2 + ... + Cn Xn

s. a:

*Considere o sistema (S) abaixo:

s. a:

Obter, aplicando o mtodo de eliminao de Gauss-Jordan, o sistema equivalente (S) = uma forma cannica de (S) onde:

X1 seja a varivel bsica referente a equao (1),X2 seja a varivel bsica referente a equao (2),...Xm seja a varivel bsica referente a equao (m),Z seja a varivel bsica referente a equao (m+1). Mtodo Simplex - Minimizao

Mtodo Simplex - Minimizao

*O sistema (S), que uma forma cannica de (S), foi obtido pelas operaes de pivoteamento aplicadas s variveis X1, X2, ..., Xm, e Z, dado por:

Mtodo Simplex - Minimizao

*Em (S) :

so respectivamente os novos coeficientes das variveis nas equaes de (S), as novas constantes nestas mesmas equaes, e os novos coeficientes das variveis na funo objetivo (expresso (I)), obtidos pelas operaes de pivoteamento no sistema (S).

(2) Os coeficientes so denominados coeficientes de custo relativo (ou reduzido) das variveis no-bsicas da soluo atual.

(3) H uma Soluo Bsica Vivel explcita em (S), onde:

Variveis bsicas:

Variveis no-bsicas:

Valor da funo objetivo:

Mtodo Simplex - Minimizao*Visualizao da etapa A do Mtodo Simplex:

Teste de otimalidade da Soluo Bsica Vivel atual.Min Z = 4X1 + X2 + X3

s. a:

(S):

Mtodo Simplex - Minimizao * Aplicando o mtodo de eliminao de Gauss Jordan para obter uma forma cannica (S) associando X3 como varivel bsica para a equao (1), X1 para a equao (2) e Z para a equao (3), tem-se:

(S):

Soluo bsica vivel atual Variveis bsicas: X1 = 1/2, X3 = 3/2Variveis no-bsicas: X2 = 0Funo objetivo: Z = Z0 = 7/2

Mtodo Simplex - Minimizao*De (I):Z = 7/2 13/4 X2

Anlise de otimalidade da Soluo Bsica Vivel (SBV) atual:

X2 = 0 varivel no bsicaSe X2 se tornar VB o valor de X2Se X2 o valor de Z o que desejvel pois a funo objetivo de minimizao

Concluso: A SBV atual no tima e X2 deve se tornar VB numa prxima SBV melhor que a atual.Assim X2 deve Entrar. Ir a etapa (B).

Mtodo Simplex - Minimizao*Etapa (A) do Mtodo Simplex

Questo: Como verificar se a Soluo Bsica Vivel explicitada em (S) tima para o modelo em estudo?

Resposta: Considere a expresso (I) em (S), dada por:

Mtodo Simplex - Minimizao*Analisando (I) h duas possibilidades:

Se no h ento a soluo atual tima. No haver a aplicao da etapa (B). Fim da aplicao do Mtodo Simplex.

Se h a soluo atual no tima. Uma varivel no-bsica XS, associada com um coeficiente de custo relativo negativo, deve ser transformada em varivel bsica numa prxima soluo bsica vivel . Esta nova Soluo Bsica Vivel ter um valor para a funo objetivo melhor (no caso do modelo de minimizao, menor) que o valor da funo objetivo atual Z0. Aplicar a etapa (B).

Mtodo Simplex - Minimizao

*Visualizao da etapa B do Mtodo Simplex (PL de Minimizao):

Seja uma Soluo Bsica Vivel disponvel dada por,X1 = 5, X2 = 6, X3 = X4 = 0, Z = 4, Associada ao sistema (S) abaixo:

(S):Aplicando a etapa (A) tem-se:

Como

Desta maneira X3 deve Entrar e seu valor dever aumentar. Observe-se que X4 no deve Entrar pois piorar o valor da F. O.

Mtodo Simplex (minimizao)

*Problema: At quanto aumentar o valor de X3?

Anlise: como X4= 0 (permanece varivel no-bsica), tem-se:

De (1): X1 = 5 2X3 ou seja se De (2): X2 = 6 2X3 ou seja se

Sabe-se que X1 0 X3 5/2

Sabe-se que X2 0 X3 6/2

Portanto X3 substituir X1 no conjunto das variveis bsicas da nova Soluo Bsica Vivel dada por:

X3 = 5/2, X2 = 1, X1 = X4 = 0, Z = 4 - 4X3 = -6

Mtodo Simplex - Minimizao

*Etapa (B) do Mtodo Simplex

Hiptese:

H um coeficiente de custo relativo deve-se achar uma nova Soluo Bsica Vivel onde XS seja varivel bsica.

Problema: Qual das atuais variveis bsicas ser substituda por XS na prxima Soluo Bsica Vivel?

Mtodo Simplex - Minimizao*Soluo:

Sejam i,s os coeficientes de XS nas equaes do sistema de restries, onde i = 1, ..., m.

Procurar a equao r do sistema de restries onde ocorra:

A varivel bsica da Soluo Bsica Vivel atual associada com a equao r acima ser substituda por XS.

Mtodo Simplex - Minimizao

*Artifcio para aplicar as etapas (A) e (B) do Mtodo Simplex.

Considere o exemplo de minimizao usado na visualizao da etapa (B), j colocado numa forma cannica:

Mtodo Simplex - Minimizao

* VB X1 X2 X3 X4 b X1 1 0 2 3 5 X2 0 1 2 -2 6No h, assim a soluo atual tima.Z* = - 6 -Z 0 0 -4 5 -4 X3 1/2 0 1 3/2 5/2 X2 -1 1 0 -5 1 -Z 2 0 0 11 6Operacionalizao da aplicao das etapas (A) e (B):(5/2) menor quociente X1 sai(6/2) X3 entra

Mtodo Simplex - Maximizao

*Modelo de Programao Linear com funo objetivo de maximizao.

Etapa (A):Soluo bsica vivel atual ser tima Etapa (B):A varivel XS que entra ter > 0, para possibilitar uma melhoria (aumento) no valor da funo objetivo associado com a Soluo Bsica Vivel atual.

Importante: as operaes de pivoteamento no se alteram.

Mtodo Simplex (maximizao)

*Exemplo de modelo de maximizao resolvido pelo Mtodo Simplex. Modelo original Modelo na forma padro Max Z = 3X1 + 5X2 Max Z = 3X1 + 5X2

s. a: s. a:

Mtodo Simplex *VB X1 X2 X3 X4 X5 b X3 1 0 1 0 0 4X4 0 1 0 1 0 6X5 3 2 0 0 1 18 -Z 3 5 0 0 0 0X3 1 0 1 0 0 4X2 0 1 0 1 0 6X5 3 0 0 -2 1 6 -Z 3 0 0 -5 0 -30X3* 0 0 1 2/3 -1/3 2X2* 0 1 0 1 0 6X1* 1 0 0 -2/3 1/3 2 -Z* 0 0 0 -3 -1 -36Soluo timaX*1 = 2, X*2 = 6, X*3 = 2, X*4 = X*5 = 0, Z* = 36Entra X2, Sai X4Entra X1, Sai X5

Mtodo Simplex

*Comentrios Gerais

Considere um modelo de Programao Linear na forma padro que seja de minimizao.

(1) Ocorrncia de Empate na Entrada:

Escolher para entrar a varivel no-bsica Xs associada ao menor valor de coeficiente de custo relativo < 0. (Regra de entrada de Dantzig)

Mtodo Simplex*(2) Identificao de Soluo Ilimitada:

Pode ser feita a identificao de soluo ilimitada durante a aplicao da etapa (B).

Se houver alguma varivel no-bsica Xs para entrar que tenha coeficientes 0, em todas as equaes i (= 1,..., m) do sistema de restries.

Mtodo Simplex

*Exemplo de Modelo com Soluo Ilimitada: Seja a Soluo Bsica Vivel abaixo, associada a forma cannica (S):X1 = 5, X2 = 6, X3 = X4 = 0, Z = 4

(S):

Observar que = 4 < 0 X3 deve entrar. Quem vai sair?De (1): X1 = 5 + 2X3 quando X3 X1 , X2 e ZDe (2): X2 = 6 + 2X3Assim o modelo apresenta soluo ilimitada com Z .

Mtodo Simplex

*(3) Interpretao geomtrica do Mtodo Simplex:

Em cada iterao do Mtodo Simplex (Etapa (A) + Etapa (B)) h um deslocamento de uma Soluo Bsica Vivel para outra que apresenta um valor para a funo objetivo melhor.

Em termos da resoluo grfica: numa iterao h a locomoo de um ponto extremo para outro ponto extremo adjacente na regio vivel do modelo em questo.

Mtodo Simplex

*Exemplo:Modelo originalMin Z = 3X1 5X2

s. a:

Mtodo Simplex

*s. a:s. a:Exemplo:Modelo original Modelo na forma padroMin Z = 3X1 5X2 Min Z = 3X1 5X2

Mtodo Simplex

*VB X1 X2 X3 X4 X5 bX3 1 0 1 0 0 4X4 0 1 0 1 0 6 X5 3 2 0 0 1 18-Z -3 -5 0 0 0 0X3 1 0 1 0 0 4X2 0 1 0 1 0 6X5 3 0 0 -2 1 6-Z -3 0 0 5 0 30X3* 0 0 1 2/3 -1/3 2X2* 0 1 0 1 0 6 X1* 1 0 0 -2/3 1/3 2-Z* 0 0 0 3 1 36Soluo bsica vivel tima: X1* = 2, X2* = 6, X3* = 2, X4* = X5* = 0, Z* = 36Resoluo do exemplo para interpretao geomtrica do Mtodo Simplex: Quadro 1: Entra X2 Sai X4Quadro 2: Entra X1 Sai X5Quadro 3 (timo)

Mtodo Simplex

*Quadro 2:X1 = X4 = 0, Z = -30, X2 = 6, X3 = 4, X5 = 6.Quadro 3:X4 *= X5* = 0, Z* = -36, X1* = 2, X2* = 6, X3* = 2.Quadro 1:X1 = X2 = 0,Z = 0, X3 = 4, X4 = 6, X5 = 18. X1Visualizao das iteraes

Mtodo Simplex

*(4) Identificao de Solues timas Mltiplas: Considere que h uma Soluo Bsica Vivel tima para um modelo de minimizao, ou seja, tem-se Z* = Z* e todos 0 para toda varivel no-bsica X s .A identificao da ocorrncia de Solues timas mltiplas feita, no Quadro timo, quando h alguma varivel no-bsica Xj com = 0.Assim ao se escolher Xj para entrar no conjunto das variveis bsicas, no se alterar o valor timo Z* da funo objetivo.Desta maneira, pode-se obter uma nova Soluo Bsica Vivel tima na qual Xj ser uma varivel bsica. Fica caracterizada assim a existncia de mltiplas Solues timas.

Mtodo Simplex

*Exemplo: Modelo original Modelo na forma padro Min Z = X1 2X2 Min Z = X1 2X2 S. a: S. a: A seguir apresenta-se:A resoluo grfica do modelo original.A resoluo do modelo na forma padro pelo Mtodo Simplex.Uma visualizao das iteraes desenvolvidas pelo Mtodo Simplex sobre a regio vivel do modelo original.

Mtodo Simplex

*Resoluo grfica do exemplo com mltiplas Solues timas Observao: XA* , XB* so solues bsicas viveis timas, Z* = 9 o valor timo da funo objetivo, a expresso geral da Soluo tima : X* = XA* + (1 ) XB* com 0 1.(3,0)X114Z = - 6Z* = - 9= XB*

Mtodo Simplex

*VB X1 X2 X3 X4 X5 bX3 1 0 1 0 0 3X4 0 1 0 1 0 4 X5 1 2 0 0 1 9-Z -1 -2 0 0 0 0Soluo tima geral:X* = XA* + (1 - ) XB*, com 0 1, e Z* = - 9X3 1 0 1 0 0 3X2 0 1 0 1 0 4X5 1 0 0 -2 1 1-Z -1 0 0 2 0 8X3* 0 0 1 2 -1 2 X2* 0 1 0 1 0 4 X1* 1 2 0 -2 1 1 -Z* 0 0 0 0 1 9X4* 0 0 1/2 1 -1/2 1 X2* 0 1 -1/2 0 1/2 3 X1* 1 0 1 0 0 3 -Z* 0 0 0 0 1 9Resoluo do modelo na forma padro Quadro 1: Entra X2 e Sai X4Quadro 2: Entra X1 e Sai X5Quadro 3: timo (XA*)Quadro 4timo (XB*)

Mtodo Simplex

*Visualizao das iteraes do Mtodo Simplex Quadro 2:X1 = X4 = 0,X2 = 4, X3 = 3,X5 = 1, Z = -8 Quadro 3:X4* = X5* = 0,X1* = 1, X2* = 4,X3* = 2, Z* = -9Quadro 4:X3* = X5* = 0,X1* = 3, X2* = 3,X4* = 1, Z* = -9 Quadro 1:X1 = X2= 0, X3 = 3, X4 = 4, X5 = 9, Z = 0 XAXBX*X1X2(0,0)X* = XA* + (1 -) XB*, onde 0 1 o caso, em termos de resoluo grfica, de um segmento de reta timo.

Mtodo Simplex

*Observao importante: Se no Quadro 3, na coluna da varivel X4 no houvesse algum coeficiente , no se poderia efetuar o pivoteamento;

Ento este o caso, em termos da resoluo grfica, que a Soluo tima uma semi-reta, da forma X* = XA* com 1 .

*Considere um modelo de Programao Linear que esteja na forma padro

Se todas as restries do modelo original (ainda no colocado na forma padro) forem desigualdades do tipo , tem-se uma forma cannica inicial (ou seja, uma Soluo Bsica Vivel inicial) evidente, onde as variveis bsicas sero as variveis de folga introduzidas para a reduo das desigualdades para equaes equivalentes.

Se alguma restrio do modelo original for uma igualdade =, ou ainda desigualdade do tipo , a condio acima no ocorrer e no haver uma Soluo Bsica Vivel inicial explcita.

Quando no h uma Soluo Bsica Vivel inicial deve-se utilizar algum procedimento de inicializao para o Mtodo Simplex.Procedimentos de inicializao para o Mtodo Simplex

Procedimentos de inicializao para o Mtodo Simplex

*(1) Mtodo das Duas Fases.

Fase 1: (a) Construo e resoluo de um modelo artificial (b) Anlise da Soluo tima do modelo artificial

Fase 2: Resoluo do modelo original utilizando como soluo inicial a Soluo tima do modelo artificial.(2) Mtodo do Big M . Introduz variveis artificiais, nas equaes do sistema de restries (exatamente como o mtodo das duas fases), e na funo objetivo original com coeficientes penalizantes adequados, isto , M >>0 para minimizao e M

Procedimentos de inicializao para o Mtodo Simplex

*Desenvolvimento do Mtodo das Duas FasesConsidere que o modelo de Programao Linear na forma padro abaixo no apresenta uma Soluo Bsica Vivel inicial, isto , no h uma forma cannica evidente.Modelo original (na forma padro)Min Z = C1 X1 + C2 X2 + ... + Cn Xn

s.a:

Procedimentos de inicializao para o Mtodo Simplex *Fase 1: Construo e resoluo de um modelo artificialO modelo artificial, a partir das equaes do sistema de restries do modelo original ser: com Y1, Y2, ..., Ym sendo as variveis artificiais no negativas.Min W = Y1 + Y2 + .... + Ym

s. a:

A F. O. artificial sempre ser de Minimizao, qualquer que seja o Modelo Original.

Procedimentos de inicializao para o Mtodo Simplex

*Observe que o modelo artificial est na forma padro com Soluo Bsica Vivel inicial:X1 = X2 = ... = Xn = 0 (variveis no-bsicas)Y1 = b1, Y2 = b2, ..., Ym = bm (variveis bsicas)W = b1 + b2 + ... + bm.

Analisando o valor timo da funo objetivo W* do modelo artificial pode-se concluir:

Caso 1: Se W* 0 h pelo menos uma varivel bsica artificial Yj com valor 0.

Nesta situao conclui-se que o sistema de restries do modelo original depende destas variveis artificiais no nulas para ser satisfeito. Assim o Modelo Original invivel. No h a fase 2.

Procedimentos de inicializao para o Mtodo Simplex

*Caso 2: se W* = 0 Y1* = Y2* = ... = Ym* = 0.

Conclui-se que o sistema de restries do Modelo Original pode ser satisfeito apenas com as variveis Xi.

Desta forma o Modelo Original vivel.

Subcaso 2.1: se todas as variveis artificiais so no-bsicas na Soluo tima do modelo artificial.

Basta eliminar todas as variveis artificiais, substituir a funo objetivo artificial pela original, e iniciar a fase 2.

Procedimentos de inicializao para o Mtodo Simplex

*Subcaso 2.2: se alguma varivel artificial permanece como varivel bsica na Soluo tima do modelo artificial. Observe que estas variveis devem ser nulas, pois W* = 0. Deve-se, atravs de operaes de pivoteamento, substituir estas variveis artificiais bsicas por variveis originais, eliminar todas as variveis artificiais no bsicas, substituir a funo objetivo artificial pela original, e iniciar a fase 2.

Se no possvel substituir alguma varivel artificial bsica por uma varivel original (pela inexistncia de elemento pivot), basta eliminar a equao associada com a varivel artificial em questo (a equao uma combinao linear das demais equaes do modelo original).

*Visualizao das iteraes Modelo Min Z = -3X1 - 5X2

s. a:

Exemplo de aplicao do Mtodo das Duas Fases

Procedimentos de inicializao para o Mtodo Simplex *Exemplo de aplicao do Mtodo das Duas Fases

Modelo Modelo na forma padro Min Z = -3X1 - 5X2 Min Z = -3X1 - 5X2

s. a: s. a:

Procedimentos de inicializao para o Mtodo Simplex

*Fase 1: construo do Modelo Artificial

Min W = Y1s. a: X1 + X3 = 4 X2 +X4 = 63X1 + 2X2 X5 + Y1 = 18Xi 0, i = 1,5; Yi 0

Soluo bsica vivel inicial para o Modelo Artificial:

X1 = X2 = X5 = 0 (variveis no-bsicas)X3 = 4, X4 = 6, Y1 = 18 (variveis bsicas)W = 18

*Exemplo de aplicao do Mtodo das Duas Fases VB X1 X2 X3 X4 X5 Y1 b X3 1 0 1 0 0 0 4 Adequar a X4 0 1 0 1 0 0 6 funo Y1 3 2 0 0 -1 1 18 objetivo -W 0 0 0 0 0 1 0Fase 1: Anlise da Soluo tima do Modelo ArtificialW* = 0Caso 2.1: Modelo Original vivel. No h variveis bsicas artificiais. Eliminar variveis artificiais, substituir funo objetivo artificial pela original. Iniciar fase 2. X3 1 0 1 0 0 0 4 X4 0 1 0 1 0 0 6 Quadro 1 Y1 3 2 0 0 -1 1 18 -W -3 -2 0 0 1 0 -18Fase 1: Resoluo do Modelo Artificial X1 1 0 1 0 0 0 4 X4 0 1 0 1 0 0 6 Quadro 2 Y1 0 2 -3 0 -1 1 6 -W 0 -2 3 0 0 1 -6 X1 1 0 1 0 0 0 4 X4 0 0 3/2 1 1/2 -1/2 3 Quadro 3 X2 0 1 -3/2 0 -1/2 1/2 3 -W* 0 0 0 0 0 1 0Transformar em Zeros os coeficientes das variveis artificiais na F. O.

*VB X1 X2 X3 X4 X5 b X1 1 0 1 0 0 4 Adequar a X4 0 0 3/2 1 1/2 3 funo X2 0 1 -3/2 0 -1/2 3 objetivo -Z -3 -5 0 0 0 0Exemplo de aplicao do Mtodo das Duas Fases Soluo tima (nica) do Modelo Original:X1* = 4, X2* = 6, X5* = 6, X3* = X4* = 0, Z* = -42 Fase 2: Resoluo do Modelo Original X1 1 0 1 0 0 4 X4 0 0 3/2 1 1/2 3 Quadro 3 X2 0 1 -3/2 0 -1/2 3 -Z 0 0 -9/2 0 -5/2 27X1* 1 0 0 0 0 4X5* 0 0 3 2 1 6 Quadro 4X2* 0 1 0 1 0 6 (timo)-Z* 0 0 3 5 0 42

Coeficientes de variveis bsicas na F. O. devem ser Zero

Visualizao da Iteraes do Mtodo das Duas Fases

*

SIM

Exerccios: Resolver graficamente e pelo Simplex*Min Z = X1 + 2 X2

X1 + X2 3s. a: 2X1 + X2 2X1, X2 0(R: Invivel)

Max Z = 6X1 + 10 X2

3X1 + 5X2 15s. a:5X1 + 2X2 10X1, X2 0R: h mais de uma soluo tima (Segmento de reta timo)

Exerccios*3.Max Z = 2X1 + 2X2

X1 - X2 -1s. a: - X1 + X2 2X1, X2 0(R: Soluo ilimitada)

4.Max Z = X1 + X2

X1 + 4X2 4s. a: 3X1 + X2 = 1X1, X2 0Comentrio: Fica a Varivel Artificial na soluo tima do Problema Artificial como Varivel Bsica, ela sai por pivoteamento.

Exerccios*5.Max Z = X1 + X2

2X1 + 3X2 = 5s. a: - 6X1 - 9X2 = - 15X1 X2 0 Comentrio: 1a. equao X1, X2 0 combinao linear das demais.

6.Max Z = - 4X1 + X2

3X1 + X2 3s. a: X1 - X2 - 14X1 X2 - 4 X1, X2 0R: H mais de uma soluo tima (Semi-reta tima)

Exerccios7. Max Z = 3X1 5X2 s.a: -3X1 + 5X2 0 X1 2X2 -2 Xi 0, i = 1,2R: H mais de uma soluo tima (Semi-reta tima)

******************************************************************************************