ExtensoesŸ da Programac‚aoŸ Linearvalente/capt3_044.pdf · Cap· tulo 3 ExtensoesŸ da Programac‚aoŸ Linear 3.1 Programa‚caoŸ multiobjetivo Os modelos para tomada de decisoesŸ

Capıtulo 3

Extensoes da ProgramacaoLinear

3.1 Programacao multiobjetivo

Os modelos para tomada de decisoes discutidos ate o momento sao mo-noobjetivos, no sentido de que apenas uma funcao-objetivo, como custo totalde producao, faz parte da formulacao matematica do problema. Modelos paratomada de decisoes que envolvem mais do que uma funcao-objetivo, mais re-alistas do ponto de vista pratico, sao chamados de modelos multiobjetivos.

EXEMPLO 3.1 (Problema da Dieta Multiobjetivo) Considere o problema da dieta dis-cutido em detalhes no Capıtulo 2. A dieta deve atender a exigencias diarias mınimasde � diferentes nutrientes (vitaminas, proteınas, carboidratos, . . . ). Os nıveis mınimosde nutrientes sao representados por

�� ; supoe-se que cada alimento �possui �� unidades do nutriente

�por unidade do alimento � . Os custos unitarios dos� alimentos que compoem a dieta sao dados por �� , �� , . . . , �� , de tal maneira que se as

quantidades totais (nao-negativas) dos alimentos forem representadas por � � , � � , . . . ,� � , o custo total da dieta sera

� � � � � � �� ! � � � � � � �

Suponha que alem de minimizar o custo total, deseja-se minimizar a quantidadetotal de colesterol presente na dieta. Se " � representar a quantidade de colesterol porunidade do alimento � , entao a quantidade total de colesterol presente nos � alimentossera

� � � " � � �� " � � �#�$ � � " � � � �

O problema de programacao linear multiobjetivo associado e

70 � Capıtulo 3 Extensoes da Programacao Linear

��

minimizar � � � � � � � � � � � � � � � � � � �� " � � � � " � � � � � � " � � �sujeito a � � ��

� �� ...

......

...��

A dieta ideal seria aquela para a qual o custo total e o colesterol total fossem si-multaneamente mınimos. Entretanto, este tipo de solucao e raramente possıvel devidoa natureza conflitiva que os objetivos assumem. No problema da dieta, por exemplo, osalimentos mais baratos podem conter maior concentracao de colesterol; ao se tentar ob-ter uma dieta de baixo custo, incorre-se ao mesmo tempo numa dieta rica em colesterole vice-versa. �

De forma a discutir algumas abordagens simples para problemas como odiscutido no Exemplo 3.1, considere um problema de programacao linear mul-tiobjetivo generico na forma padrao:

(PMO)

minimizar �� ...��

sujeito a � � �� ! #"A formulacao (PMO) possui $ funcoes-objetivos, �� , �� . . . � ( $ �&% ), cada

uma delas caracterizada por um vetor linha �(' �*) �,+ �-%.��"("�"�� $ . Problemasmultiobjetivos geralmente nao possuem solucoes otimas no sentido usual, istoe, geralmente nao existe uma solucao factıvel �0/ ( � �1/ �2� �3�1/4�5 ) tal que '6 �7/98;: '

6 �<8 para todo ) ( ) �=+ �-%.�("�"�"�� $ ) e toda solucao � factıvel.

EXEMPLO 3.2 Uma empresa fabrica dois tipos de produtos, P1 e P2. Cada unidadedos produtos P1 e P2 demanda uma unidade de materia-prima; existem 400 unida-des de materia-prima disponıveis. Uma unidade de P1 consome 2 unidades de tempo(homens-hora); o produto P2 requer apenas uma unidade de tempo para ser produzidoe existem 500 unidades de tempo disponıveis. Os precos de venda de P1 e P2 sao $0.4e $0.3, respectivamente. A empresa esta interessada em maximizar sua receita e, aomesmo tempo, o numero de unidades produzidas do produto P1. O problema linearmultiobjetivo associado e, apos transformacao para minimizacao,

��

maximizar � � � � � > � �� ? � �� sujeito a � �� ;@ > �9� � � �� A@�B �9� �

��C�� D��

3.1 Programacao multiobjetivo � 71

A regiao factıvel do problema encontra-se ilustrada na Figura 3.1. Maximizandoisoladamente as funcoes objetivos, obtem-se o ponto � , correspondente a �� (� e� � � � ? �(� , como solucao otima para a funcao � � , e o ponto � , correspondente a �� B � e � �� , como solucao otima para a funcao � � . As solucoes otimas individuais saoobtidas em pontos diferentes da regiao factıvel, isto e, nao existe uma solucao factıvelque minimize simultaneamente ambas as funcoes. Em �� ,

� �� ? � � � �� 9� �e qualquer alternativa factıvel que aumente o valor de � � necessariamente diminui ovalor de � � . Do mesmo modo, em �� ,

� � � � � � � �9� � � � � � � � � B � �e qualquer tentativa de aumento do valor de � � implica na reducao de � � .

PSfrag replacements

�

�(�

�9�

�(�

�9�

? �(�

? �9�

> �9�

> �(�

B �9�

�9�

� �

� �

� �

� �

�

�

Figura 3.1: Interpretacao grafica do Exemplo 3.2.�

As abordagens mais simples para problemas multiobjetivos partem da for-mulacao (PMO) e obtem problemas monoobjetivos equivalentes.

Abordagem por ponderacao

Na abordagem por ponderacao exige-se a atribuicao de pesos – valoresescalares nao-negativos – aos objetivos. A ideia e que a importancia relativados objetivos seja estabelecida pelos pesos: pesos maiores para objetivos maisimportantes, pesos relativamente menores para objetivos menos importantes.


Denotando por �� , �D� , . . . , � � os $ pesos associados aos objetivos, obtem-se oproblema de programacao equivalente

(PW)

minimizar �� sujeito a � � �� #"

Observe que para cada conjunto de valores � ' �A) �5+ � % ��"("�"�� $ , (PW) e umproblema de programacao linear monoobjetivo, podendo ser resolvido pormeio do metodo Simplex. E necessario considerar apenas pesos satisfazendo

� ' � ��) � + � %.�("�"(" � $ ��' � �

� ' �=+ "

Dado que ' � � ' ��) � + � %.�("�"("�� $ , a funcao-objetivo de (PW) e equivalente a

�� 3�� D�9� � �� "O vetor de custos da funcao-objetivo de (PW) e uma combinacao linear nao-

negativa dos vetores � � , � � , . . . , � � , como ilustra a Figura 3.2 para o caso deapenas duas funcoes-objetivos.

PSfrag replacements

� �

� �

�� (� ��

� � � �

Figura 3.2: Vetor de custos equivalente.

Abordagem por restricao

Na abordagem por restricao para o problema (PMO), uma funcao-objetivode referencia, ' , por exemplo, e minimizada sujeito a que as demais $��&+funcoes-objetivos, �� ) , nao excedam valores pre-determinados �� ) .O problema assume a forma

(PE)

minimizar ' �� ' ��sujeito a � � ��

� �� : �� )-�� #"Obtem-se um problema de programacao linear monoobjetivo para cada ob-

jetivo de referencia selecionado e limites superiores � �� ) atribuıdos aos $�� +objetivos restantes.

3.1 Programacao multiobjetivo � 73

EXEMPLO 3.3 Considere o problema discutido no Exemplo 3.2:

��

maximizar � � � � � > � � � � � ? � �� sujeito a � �� ;@ > �(� � �� @�B �9� �

� � �� A��

A regiao factıvel do problema encontra-se ilustrada na Figura 3.2. Pela abordagempor ponderacao, obtem-se uma funcao-objetivo equivalente na forma

� � ��

com

� � � � �� > � � ? � � � �� ,� � ? � � � � � ��

O problema equivalente a ser resolvido seria

��

maximizar � � � �� ? � � � � �sujeito a � � � � �;@ > �(� � � �� A@�B �9� �

� � �� A��

Se � � � , obtem-se os coeficientes de � � , e a solucao otima para a maximizacao de� � , ponto � da Figura 3.1. Se � � � � , obtem-se os coeficientes de � � , e a solucao otima

para a maximizacao de � � , ponto � da Figura 3.1. Qual valor de � � levaria as solucoesmultiplas na aresta que liga os pontos � e � ? Para descobrir, basta obter coeficientesde � com inclinacao

� , a inclinacao de

� �� B �9� :�� ? � �

�

implica � � � B�� . Para B�� D@ , a solucao otima do problema e o ponto � . Para� � � B�� , obtem-se as solucoes multiplas contidas na aresta que liga � a � . Finalmente,

para � @�� B�� , obtem-se o ponto � .Considere agora a resolucao do mesmo problema pela abordagem por restricao.

Tomando o primeiro objetivo como referencia e impondo um limite inferior – o pro-blema e de maximizacao – igual a 150 para o segundo objetivo, obtem-se o problemaequivalente ��

maximizar � � � � � > � � � � � ? � �sujeito a � �� ;@ > �(� � �� @�B �9� �� B � �

� � �� A solucao otima deste problema, obtida graficamente, e �� B � e �� (� ,

correspondendo a � �� e � �� B � , contra 130 e 250, os valores otimos alcancadosquando as funcoes � � e � � sao maximizadas individualmente. �


3.2 Programacao por metas

Nos modelos de programacao por metas ou programacao alvo trabalha-secom metas ou alvos associadas as funcoes-objetivos do problema. Modelosdesse tipo sao frequentes principalmente no planejamento de atividades do se-tor publico. A ideia central e associar uma meta – algo tangıvel para a maioriadas pessoas – a cada funcao-objetivo e em seguida procurar minimizar os des-vios em relacao as metas previstas. A Figura 3.3 ilustra o mecanismo utilizado.Na programacao por metas, o tomador de decisoes fornece metas para os ob-jetivos e estabelece prioridades para a minimizacao de desvios em relacao asmetas. Os modelos de programacao por metas lineares sao facilmente imple-mentados atraves do metodo Simplex.

A Figura 3.3 ilustra o conceito de meta, de acordo com as seguintes conven-coes:

�' : meta para a funcao objetivo ' ;��'� : indica que ' ficou acima de

�' na quantidade

��' ��

'� : indica que ' ficou abaixo de

�' na quantidade

��' .

PSfrag replacements

'

'

'6 ��' �

� �' �

8�'

� �'

� �'

Figura 3.3: Conceito de meta.

Para garantir que��' e

� �' nao sejam simultaneamente positivos, introduz-

se a condicao adicional� �' �

��' �

para todo ) ( ) � + � %.�("�"(" � $ ). O objetivo geralna programacao por metas e minimizar os desvios em relacao as metas estipu-ladas. Para tornar a solucao do problema mais flexıvel, permite-se a definicaode (um inteiro positivo qualquer) funcoes de desvios �0� , �<� , . . . , �� , as quaisexpressam a ordem decrescente de prioridades na qual as funcoes de desviosserao minimizadas. Um problema generico de programacao por metas linear

3.2 Programacao por metas � 75

pode entao ser formulado como

6PPM 8

minlex � � � � � � �("�"�"(� � ��sujeito a

��

� ' � � � �� ' �� ' � � '��) �=+ � % ��"("�"��

��

� ' � � � ��' �

� �' �

�' ��) � + � %.�("�"(" � $

� �'� � � �'

� #� � �' ��' �

#��) � + �-%.�("�"�"�� '� � ��

'�! #� � �

' ��' �

��) � + � % ��"("�" � $��! #"Na formulacao (PPM), minlex e um acronimo para mınimo lexicografico,

a solucao do problema que obedece a seguinte regra: inicialmente a funcaode desvio � � , de mais alta prioridade, e minimizada sujeito as restricoes. Emseguida � � e minimizada sujeito as restricoes, e a que o valor otimo obtidopara � � nao seja alterado. Procede-se de maneira analoga ate o final da listade funcoes de desvios, minimizando-se uma funcao de desvio sujeito a que osvalores mınimos obtidos para funcoes anteriores sejam conservados.

Observe que as variaveis de decisao na formulacao (PPM) sao � ,� �

,� �

, � �e � � . Nos modelos de programacao por metas as restricoes originais do pro-blema sao manipuladas como metas prioritarias ( �9� � �� "("�"�� ); seus desviossao denotados por � �' e � �' e alguma funcao de desvio que dependa de � � e � �deve ser a primeira a ser minimizada.

EXEMPLO 3.4 Considere novamente o problema de planejamento da producao discu-tido no Exemplo 3.2, restrito a maximizacao da receita:

��

maximizar � � � � � > � � � � � ? � �sujeito a � �� ;@ > �(� � �� @�B �9� �

� � �� Suponha que uma meta � �� > � foi estabelecida para � � . Um modelo de programacao

por metas que reflete a natureza do problema seria��

minlex � �� "��sujeito a � �� > �9� � �� B �(� �� > � � � � � ? � � � " �� " � � � �> � �

� �� " � � �� " �� " � � " ��

A primeira funcao de desvio a ser minimizada e �� . Observe que se ovalor otimo de � � for zero ( " � � � " �� ) entao � �� @ > �9� e

� � � � �D@ B �(� , comorequerido. A segunda funcao de desvio e � � " �� , refletindo o desejo de se obter nomınimo 240 como valor para a funcao objetivo. Uma interpretacao grafica do problemae apresentada na Figura 3.4.


PSfrag replacements

0 250

400

400 600

500

800

�

� �

� �

��

� ��

" � �

" ��

"��

Figura 3.4: Solucao grafica do problema.

Os pontos viaveis do modelo de programacao por metas nos quais � �� coincidem com os pontos da regiao viavel do problema original. Em outras palavras,qualquer solucao viavel do problema original minimiza �� ( �� ). Em seguida,resolve-se ��

minimizar " ��sujeito a � � � � ��

�� > �(� � � �� B �9� �� > � �� ? � � � " �� " � � � > � �� " � � �� " �� " � � " ��

A solucao de mınimo desvio e encontrada no ponto � correspondente a � � � �9� e� � � ? �9� , no qual � �� ( � � � � � ) e � �� " �� .

Considere agora o problema alternativo (sem mencao explıcita das variaveis de des-vio, por brevidade) ��

minlex � �� "�� "�� sujeito a � �� > �9� � �� B �9� �� > � �� ? � � � " �� " � � � �> � �

� �� " �� " �� 4? �9� �Deseja-se produzir no mınimo 300 unidades do produto P2 e obter no mınimo $

240 de retorno, nesta ordem. A solucao grafica do problema alternativo encontra-serepresentada na Figura 3.5. Como no problema anterior, �� e minimizada em qualquersolucao factıvel do problema original. A minimizacao � � � "�� leva ao ponto � � � B �e � � � � , que tambem sera a solucao para a minimizacao de �� " �� , uma vez que omınimo de � � e atingido num unico ponto. A solucao apos as sucessivas minimizacoesdas funcoes de desvios e �� B � � � � � � � � �� " �� > � � " �� B � .

3.2 Programacao por metas � 77PSfrag replacements

0

"�� B �

250 300 400

400

600

500

800

A

� �

� �

��

��

" � �

"��

" ��" ��

"�� > �

Figura 3.5: Solucao grafica do problema alternativo.�

Programacao por metas via metodo Simplex

Os modelos de programacao por metas podem ser resolvidos de forma efi-ciente por meio de sucessivas aplicacoes do metodo Simplex, com uma mo-dificacao adequada na regra que rege a transformacao de uma variavel nao-basica em basica. O procedimento a ser utilizado e o seguinte:

1: Encontre uma solucao basica inicial factıvel; obtenha os custos relativos de� � � � � ��"�"("�� em relacao a solucao basica inicial; faca

� � + ;2: Se os custos relativos das variaveis nao-basicas de �� forem nao-negativos,

va para o passo 5; senao, va para o passo 3;

3: Se nas colunas de custos nao-basicos, todos os custos negativos de �� foremprecedidos por pelo menos um custo positivo de � ' �0) �=+ �-%.��"("�"��

� ��+ , vapara o passo 5. Caso contrario, va para o passo 4;

4: Escolha uma variavel com custo nao-basico negativo para ser transformadaem variavel basica; faca a atualizacao das variaveis basicas. Repita o pro-cedimento enquanto houver custos negativos nao precedidos por custospositivos. Em seguida, va para o passo 5;

5: O valor de � � nao pode continuar a ser reduzido: faca� � � � + . Se

� � pare; caso contrario, volte ao passo 2.

O procedimento acima e necessario para evitar que a reducao de uma funcaode desvios provoque o aumento de alguma funcao de desvio precedente, o que


ocorre se, numa coluna de custos relativos, acima de um custo relativo nega-tivo houver um custo relativo positivo. O procedimento e certas caracterısticasda resolucao de modelos de programacao por metas via metodo Simplex saoilustradas por meio de um exemplo.

EXEMPLO 3.5 Considere o modelo de programacao por metas discutido no Exemplo3.3: ��

minlex � �� " �� " �� sujeito a �� > �9� � � �� B �9� �� > � �� ? � � � " �� " � � � �> � �

�� " �� " �� 4? �9� �

A tabela inicial relativa ao metodo Simplex para programacao por metas e apresen-tada a seguir.

Tabela 3.1

� �� " � � " �� " �� " �� LD� 0 0 1 1 0 0 0 0 0 0 0� 0 0 0 0 0 0 0 0 0 1 0� 0 0 0 0 0 0 0 0 1 0 0

0 1 1�

0 0 0 1 0 0 0 4000 2 1 0

� 0 0 0 1 0 0 500

0 0.4 0.3 0 0�

0 0 0 1 0 2400 1 0 0 0 0

� 0 0 0 1 300

Nas tres primeiras linhas da Tabela 3.1 estao representadas as tres funcoes de des-vios do problema. As variaveis do problema foram organizadas de forma a evidenciaruma solucao basica viavel inicial: as variaveis de desvio para baixo das metas podemser tomadas como variaveis basicas e as restantes como nao-basicas. Observe que asrestricoes nao-lineares " �� "�� e �� sao naturalmente satisfeitas ao se ado-tar o metodo Simplex, uma vez que " �� e " �� ( � �� e � �� ) nao podem ser variaveis basicasao mesmo tempo: se uma e variavel basica (digamos " �� ), a outra e nao-basica( "�� ) e portanto " �� "�� .

O passo seguinte e obter os custos relativos das funcoes de desvios em relacao asolucao basica viavel inicial. Obtem-se entao a Tabela 3.2.

Tabela 3.2

� �� " � � " �� " �� " �� LD� 0 0 1 1 0 0 0 0 0 0 0� �

0 0 0 0 1 0 0 0 0� ? �(�� > � � � ? 0 0 1 0 0 0 0 0� �> �

0 1 1�

0 0 0 1 0 0 0 4000 � 2 1 0

� 0 0 0 1 0 0 500

0 0.4 0.3 0 0�

0 0 0 1 0 2400 1 0 0 0 0

� 0 0 0 1 300

3.2 Programacao por metas � 79

Constata-se que a solucao basica inicial e otima para � � , uma vez que os custosrelativos de � sao nao-negativos:

� �� > �(� � � �� B �9� � " �� > � � " �� ? �9� �� " � � � " �� ? �9� � � � � �> � �

Na base corrente, � � possui um custo relativo negativo. Se � � for transformada emvariavel basica, o valor de � � diminui sem alterar o valor de � � , pois o custo relativo de�� e nulo para � � . A determinacao da variavel basica que se transforma em nao-basicasegue a regra usual do metodo Simplex. Pelo criterio de primeira variavel a atingir ovalor nulo, a variavel � �� deve deixar a base. O elemento pivot encontra-se indicado naTabela 3.2. A nova solucao apos pivoteamento e apresentada na Tabela 3.3.

Tabela 3.3

� � � � � � �� " � � " �� " �� " �� LD� 0 0 1 1 0 0 0 0 0 0 0� 0 0.5 0

� � � B 0 1 0 0.5 0 0� B ��

0� � � 0 0 1 0 0 0.2 0 0

� -> �0 0 0.5

� 0.5 0 0 1

� � � B 0 0 1500 1 0.5 0

� � � B 0 0 0 0.5 0 0 2500 0 0.1 0 0.2

� 0 0

� � � 1 0 1400 0

� � � B 0 0.5 0�

0� � � B 0 1 50

De acordo com o procedimento adotado, a partir da nova solucao basica nao e maispossıvel diminuir � � sem aumentar � � , assim com nao e possıvel diminuir �� sem au-mentar � � : a base corrente e o mınimo lexicografico do problema, a solucao do problemade programacao por metas:

� �� B � � � �� " �� -> � � " �� B � �� " � � � " �� B � � � � � � �� B � � � �� > � �

�Os modelos de programacao por metas tornaram-se muito populares na

area de tomada de decisoes devido a sua flexibilidade, facilidade de imple-mentacao por intermedio do metodo Simplex, e pelo fato de serem sempreviaveis. Nos modelos de programacao por metas, as restricoes originais doproblema sao tratadas como metas prioritarias. O problema original possuiuma solucao viavel se e somente se uma funcao de desvios adequada represen-tando as restricoes puder assumir o valor zero. Os modelos de programacaopor metas sao sempre viaveis porque o objetivo e minimizar desvios, e estespodem assumir quaisquer valores.


3.3 Problemas de transporte

Em problemas de transporte lida-se com um conjunto de � pontos chama-dos de origens, cada um dos quais conectado a outros � pontos denominadosde destinos, como ilustra a Figura 4.1.

PSfrag replacements

++%%

��

� �

� �

� �

� �

��

� �

Figura 3.6: Representacao grafica do problema de transporte.

Os pontos de origem possuem producoes representadas por quantidadesnao-negativas � � , � � , . . . , � � , enquanto que os pontos de destino possuem de-mandas associadas as quantidades nao-negativas � � , � � , . . . , � � . O objetivo etransportar as producoes dos pontos de origem para os pontos de destino. Se-jam � ' � e � ' � o custo unitario de transporte e a quantidade total transportadaentre a origem ) e o destino � , respectivamente. O problema de transporte podeentao ser formulado matematicamente como

(PT)

minimizar ��

' � ��

� ' � � ' �

sujeito a

��

� ' � � � ' � ) � + � % ��"�"("��

' � �� ' � � � � � � � + � %.�("�"(" � �

�� ' � �! #� ) �=+ � % ��"("�"�� =+ �-%.�("�"�"��

"

Na formulacao (PT), representa o custo total de transporte entre origense destinos, o primeiro conjunto de � restricoes estabelece que a quantidadetotal transportada da origem ) para os � destinos deve ser igual a producao daorigem ) , e o segundo conjunto de � restricoes impoe que a quantidade totalrecebida pelo destino � oriunda das � origens deve ser igual a demanda do

3.3 Problemas de transporte � 81

destino � . Diz-se que um problema de transporte e balanceado se��

' � �� ' �

��

�� "Um problema de transporte balanceado sempre possui uma solucao viavel.

Para demonstrar essa afirmacao, considere a definicao de variaveis ( � �� )� ' � �

� ' �� ) � + � %.�("�"("�� + �-%.�("�"�"�� "

Neste caso, � ' � � quaisquer que sejam ) e � . Alem disso,��

� ' � ��

� � ' � �� '� ��

�� 'e ��

' � �� ' � �

��

' � �� ' ��

' � �� ' � � � �

indicando que o problema (PT) possui uma solucao viavel na forma definidaacima. Finalmente, o problema (PT) e limitado, pois � ' � :�� ' � � �� quais-quer que sejam ) e � . O problema possui uma solucao otima viavel, a qual podeser obtida por meio de uma versao especializada do metodo Simplex.

Forma Padrao de (PT)

O problema de transporte (PT) e um problema de programacao linear. Defato definindo as quantidades� �� ... ��

... � �3� � �D� �� (� � �(� � ��,�9� � ... ��... � �3� � �D�� ... ��

... � � � � ��,� � �� e possıvel representar o problema na forma padrao como

(PT–FP)

minimizar � ��sujeito a � � � � �� #�

sendo � uma matriz do tipo

� �

��

. . . �"�"("�"�"("�"("�"�"�"�"�"("� � ��

��

82 � Capıtulo 3 Extensoes da Programacao Linear�representa a matriz identidade de ordem � e

�e um vetor–linha de � compo-

nentes, todas iguais a + .EXEMPLO 3.6 Para exemplificar a estrutura da matriz � , considere o caso particular� �

e � � ? (duas origens e tres destinos). Explicitando as restricoes da formulacao(PT), obtem-se

� � � � � � � � � � � � � � ��

��

� � � � � � � ��

Definindo os vetores

� � � �� e� � � � � � � � � � � ��

resulta

� �

��

��

� �

sendo os elementos nao indicados explicitamente todos iguais a zero. �O problema de transporte (PT) possui � � variaveis (cada origem e ligada a

� destinos e existem � origens) e � � � restricoes ( � restricoes de origem e �

restricoes de destino). As matrizes � e�

possuem dimensoes6 � � �

8�� e6 � � �

8 � + , respectivamente. Ocorre que as linhas da matriz � sao linearmentedependentes. De fato, a soma das � primeiras linhas de � e igual a soma das �

ultimas, caracterizando a dependencia linear. Entretanto, dada a estrutura damatriz, quando qualquer linha de � e removida, as � � �� + linhas restantessao linearmente independentes. Suponha entao que uma linha qualquer de �foi removida, gerando uma nova matriz � . Neste caso e possıvel selecionar

� � � � + colunas linearmente independentes � e expressar � � � � + variaveis(basicas) em termos das � � �

6 � � � � + 8 variaveis (nao-basicas) restantes. Maisimportante ainda e o fato de que os valores das variaveis basicas podem serencontrados sem se recorrer a operacao de pivoteamento do metodo Simplex,como ilustra o exemplo a seguir.

EXEMPLO 3.7 Considere a matriz � e do Exemplo 3.6. Removendo a ultima linha de� , obtem-se a matriz>��

� ��

� �


Considere a matriz � formada pelas quatro primeiras colunas (linearmente inde-pendentes) de � :

� ��

� �

Para obter os valores das variaveis basicas, resolve-se

� � � � � �sendo

�o vetor

�sem sua ultima componente. Ao inves de calcular � � � � � � � , e

possıvel explorar a estrutura de � . Do sistema de equacoes acima,

� �� e � �� As demais variaveis sao obtidas por substituicao direta:

� � � � ��

��

�A solucao de � � � � � por substituicao direta e possıvel em decorrencia

da estrutura da matriz � . Qualquer matriz � formada por � � �� + colunaslinearmente independentes de � e triangular, no sentido de que operacoesde troca de colunas e/ou linhas permitem coloca-la na forma de uma matriztringular inferior.

EXEMPLO 3.8 A matriz � do Exemplo 3.7 pode ser triangularizada da seguinte forma:

1. Troque a primeira linha pela quarta:

� � ��

� ��

2. Troque a primeira coluna pela segunda:

� � ��

� ��

3. Troque a segunda coluna pela quarta:

� � ��

� �


4. Troque a terceira coluna pela quarta:

� � ��

� �

Observe que ao trocar colunas de � , troca-se variaveis; ao trocar linhas de � e ne-cessario tambem trocar as linhas de

�da mesma forma. Em relacao ao sistema original,

os novos vetores de variaveis basicas e de coeficientes seriam

� � ��

� e

� � ��

� �

A matriz � foi triangularizada: � � e uma matriz tringular inferior, pois acimada sua diagonal principal so existem zeros. A partir do sistema original obtem-se umsistema de equacoes equivalente na forma triangular,

� � � � � � � �o qual pode ser resolvido por substituicao direta:

� � � � � � � ��

��

��

Em termos dos vetores originais � � e�

, obtem-se

� � � � � ��

��

a mesma solucao antes da triangularizacao. �Na pratica nao e necessario obter a forma triangular da matriz formada

pelas colunas associadas as variaveis basicas.


Obtencao de uma solucao basica viavel inicial

Uma solucao basica viavel inicial para o problema de transporte pode serobtida por meio do procedimento conhecido como Regra do Noroeste. Paratanto utiliza-se uma representacao das restricoes de origem e destino comoindicada na tabela abaixo. Cada variavel ocupa uma celula da tabela.

� � � � � � �� ...

......

......� �3� � �D� ��

�� Observe que as somas das colunas devem ser iguais as producoes e as so-

mas das linhas devem ser iguais as demandas. A Regra do Noroeste consisteem explorar a estrutura do problema para obter uma solucao basica viavel ini-cial da seguinte forma:

1. Comecando no canto superior esquerdo (noroeste), faca � � � igual ao mıni-mo entre � � e � � ;

2. Se � � �3� �� , desloque-se para a celula da direita e faca � � � igual ao menorvalor entre �� e � � � � � � . Se � � � � � � , desloque-se para a celula abaixo,fazendo � �� igual ao menor valor entre � � e �� ;

3. Repita o procedimento ate que as somas das colunas e das linhas sejamiguais as producoes e demandas, respectivamente.

EXEMPLO 3.9 Considere um problema de transporte com os seguintes dados de en-trada: � � � ? � , �� , � � � � , � � � � ( � �!>

origens) e� � � � , � � � B � , � � � � ,� � �� , �� ( � � B destinos). A solucao inicial viavel obtida atraves da Regra do

Noroeste e indicada abaixo.

� � 30? � � ? � 80 � 10> � � 6010 50 20 80 20

Inicialmente, �� . Passa-se a celula �� e o maximo que e possıvel atribuir e� � � � � . Como a primeira restricao de producao foi atendida, passa-se para a celula� � � abaixo. Atribuindo � � � � ? � atende-se a segunda restricao de demanda; passa-sea celula � � � a direita. Atribuindo � � � � � , a terceira restricao de demanda e aten-dida; passa-se a celula � � � a direita. Com � � � �&? � a segunda restricao de producaoe atendida; passa-se a celula � � � abaixo. Atribuindo � � � � � , a terceira restricao deproducao e satisfeita; passa-se a celula � � � abaixo. Fazendo � � � � > � , atende-se a quartarestricao de demanda; passa-se a celula � � � a direira. Com � � � � � , a quarta restricao


de producao e a quinta restricao de demanda sao simultaneamente atendidas, o quecompleta o preenchimento da tabela.

Uma solucao basica viavel inicial foi obtida. Os valores das variaveis basicas sao

�� ? � � � � � � � � � � � � > � � � � � � � �As demais variaveis, nao-basicas, sao todas iguais a zero. Toda solucao basica viavel

do problema tratado exibira � � � � � � variaveis basicas (como acima) e � � � � � �� variaveis nao-basicas. �

Calculo dos custos relativos

A Regra do Noroeste permite obter uma solucao basica viavel inicial parao problema de transporte explorando a estrutura do problema. E necessarioagora determinar se a solucao obtida e otima, no sentido de minimizar o custototal de transporte e, caso contrario, promover uma mudanca de solucao basicaque produza uma diminuicao do custo. Especificamente, e preciso determinaros custos relativos das variaveis nao-basicas em relacao a solucao corrente: seestes forem todos nao-negativos, a solucao corrente e otima. Caso contrario,deve-se promover uma troca de variaveis: uma variavel nao-basica com custorelativo negativo torna-se basica, assumindo valor positivo. A variavel basicaque primeiro atingir o valor zero torna-se nao-basica.

Do estudo de programacao linear, sabe-se que o vetor de custos relativosnao-basicos e dado por �� para uma dada particao � �� ... �entre variaveis basicas e nao-basicas. Os vetores � � e � � sao os custos originaisdas variaveis basicas e nao-basicas, respectivamente. Convem lembrar que oscustos relativos das variaveis basicas sao todos iguais a zero. Fazendo �=�� , obtem-se � � � � � �� sendo � a solucao do sistema de equacoes

� � � � � "As componentes do vetor � sao precisamente as variaveis duais, tambem

chamadas de multiplicadores, associadas ao problema de transporte. Como� possui � � � linhas, existem � � � multiplicadores associados. Por con-veniencia, os multiplicadores sao denotados da seguinte forma:

� � � �0��1� "("�" � � ... � �� "�"(" � � "Observe que se � ' � e uma variavel basica, entao a coluna de � correspon-

dente possui elementos iguais a 1 nas linhas ) (entre as � primeiras linhas) e �(entre as � linhas restantes). Para cada variavel basica, uma equacao o tipo

� ' �� ' �


e obtida. Como toda solucao basica possui � � � ��+ variaveis basicas, existemsempre � � � � + equacoes e � � � incognitas (multiplicadores). Fazer ummultiplicador qualquer igual a zero equivale a remover a linha correspondenteda matriz � , o que nao foi feito ate agora por conveniencia. Os demais � � � � +multiplicadores podem entao ser determinados.

Calculados os multiplicadores, obtem-se os custos relativos das variaveisnao-basicas por meio de argumentos identicos: se � ' � e uma variavel nao-basica, entao a coluna correspondente de � possui elementos iguais a 1 naslinhas ) e � . Os custos relativos nao-basicos sao obtidos na forma

� � ' � � � � ' � � � ' � �� "Para facilitar o calculo dos multiplicadores, os custos de transporte do pro-

blema sao organizados numa tabela similar a utilizada para o caculo de solu-coes basicas:

�(� � �(� � �� 9� � �0�� 1�...

......

......

� �3� ��;� ��

EXEMPLO 3.10 Considere o problema tratado no Exemplo 3.9 e assuma que os custosunitarios de transporte sao como indicados na tabela abaixo.

�?

�> �

9 � � �

�>

� B 5 � � �?

2 � �? ? �>

� � �

� � � � � � � � � �

Os custos das variaveis basicas estao indicados com � . As seguintes equacoes saoentao formuladas:

� � � � � � ? �� > �� > �� B �� ? �� > ��

Embora qualquer multiplicador possa ser feito igual a zero, recomenda-se fazerigual a zero um dos que mais vezes aparecer nas equacoes. Fazendo, por exemplo,� � � � , obtem-se diretamente � � � B , � � � ? e � � � > . Em seguida, � � � � ?

, � ��

,� � � �

, � � �� e � � � �C>. Passa-se entao a calcular os custos relativos das variaveis

nao-basicas, indicadas na tabela abaixo.


? >�

��

��

� > B � B B

�

�

� ?

� ?

�?

�?

� > >

�C> � ? � � � Especificamente, a partir dos multiplicadores computados anteriormente,

� � � � � � � � � � � � � � � � � � � �� > �� B � > � �� B � B � � �� ? � > �4? �� ? � ? � �� ? � � � �� ? � � �� ? � > � > �4? �� ? � > � ? � �� > � � � �

�

Obtencao de uma nova solucao basica

Uma vez computados os custos relativos das variaveis nao-basicas, duassituacoes podem ocorrer. Se todos os custos nao-basicos sao nao-negativos, asolucao basica corrente e otima e o procedimento e encerrado. Caso contrario,seleciona-se uma variavel nao-basica com custo negativo para se tornar basica,determina-se qual variavel basica torna-se nao-basica e atualiza-se os valoresdas variaveis basicas. Este ultimo passo e realizado diretamente sobre a tabelacontendo a solucao basica corrente. Ao se atribuir um valor � � (inicialmentedesconhecido) a variavel nao-basica escolhida, os valores das variaveis basicasdevem sofrer variacoes positivas, negativas ou nulas para que a viabilidadeda solucao seja mantida. Determina-se o maior valor de � , correspondentea maxima variacao das variaveis basicas, que garante a nao-negatividade danova solucao basica. Para o valor de � encontrado, pelo menos uma variavelbasica deve atingir o valor zero, sendo entao declarada nao-basica.

EXEMPLO 3.11 Considere o problema tratado no Exemplo 3.10. Como o custo relativoda variavel nao-basica � � � e negativo, a solucao basica corrente nao e otima. O valorda funcao objetivo aumenta com a transformacao de � � � em variavel basica. Fazendo� � � �� , para que a nova solucao seja viavel (respeite as restricoes de producao edemanda), as demais variaveis basicas devem sofrer variacoes positivas, indicadas natabela abaixo por � � , negativas, indicadas por

��, ou nulas, indicadas com � .


�� ? �? �� ? � � � � � �� > � � � �� B � � � � �

O maior valor de�

que garante a nao-negatividade das variaveis e� � � . A

variavel � � � transforma-se em variavel basica com valor � � � � � e a variavel � � � ,assumindo valor nulo, transforma-se em variavel nao-basica. A nova solucao basica eindicada na tabela abaixo.

� � ? �? � B � � � � � � � � � � B � � � � �

O metodo prossegue com a atualizacao dos multiplicadores, dos custos relativosdas variaveis basicas e das solucoes basicas, ate que todos os custos relativos sejamnao-negativos, quando entao a solucao corrente e otima. �EXEMPLO 3.12 Um fabricante de produtos plasticos possui estoques de 1200 e 1000 cai-xas de fita adesiva em duas fabricas diferentes. O fabricante possui pedidos do produtode tres atacadistas distintos, nas quantidades de 1000, 700 e 500 caixas, respectivamente.Os custos unitarios de transporte (centavos/caixa) das fabricas para os atacadistas estaoindicados na tabela abaixo.

Fabrica Atacadista 1 Atacadista 2 Atacadista 21 14 13 112 13 13 12

A formulacao matematica do problema e a seguinte:��

minimizar � � > � � �� -? � � �#� � � � � -? � �� #� � � �sujeito a � � �� (� �

� �� 9�(� �� 9�(� �� (� �� B �(� �

sendo � � � � � � � �� ? � variaveis nao-negativas que indicam quantas caixas

devem ser despachadas da fabrica � para o atacadista�. Observe que o sistema e balan-

ceado: a soma dos estoques e igual a soma das demandas, 2200 caixas.A aplicacao da Regra do Noroeste gera a tabela abaixo, contendo uma solucao basica

viavel inicial.


1000 200 1200500 500 1000

1000 700 500

A solucao basica inicial e � � � � �9�9� , � � � � �(� , � � � � B �9� , � � � � B �9� (basicas),� � � � � �� (nao-basicas). A tabela de custos para o calculo dos multiplicadores eapresentada a seguir.

14 13 11 � �13 13 12 � ��

Com os custos das variaveis basicas, obtem-se

� � � � � � � � � � ->�� ? �� ? ��

Fazendo � � � � , � � � �?, � � � �?

, � � � , � � � � e � �

� � . Os custos relativos das

variaveis nao-basicas sao

� � � � � � � � � � � � � � �� -? � � � �� ? � -? � � � ��

A transformacao de �� ou � �� em variavel basica permite reduzir o custo de trans-porte. Escolhendo � � � e supondo que � � � assume o valor

�, obtem-se as variacoes indi-

cadas na tabela abaixo:

1000 � 200 � � �1200

500 � � 500 � � 10001000 700 500

A variavel � � � torna-se basica com o valor � � � � �9� ; a variavel � � � torna-se nao-basica. A nova solucao basica e indicada na tabela a seguir.

1000 200 1200700 300 1000

1000 700 500

Os multiplicadores sao atualizados:

� � � � � � � � � � ->�� ? ��

Fazendo � �� , � � � �

, � � � , � � ��? , � � �

. Os custos relativos atualizadossao

� � � � � � � � � � � � � � -? � �� -? � � � ? � � �


A transformacao de � �� em variavel basica permite reduzir ainda mais o custo totalde transporte. Supondo que � �� assume o valor

�, obtem-se as variacoes indicadas na

tabela abaixo:

1000 � � 200 � � 1200�700 � 300 � � 1000

1000 700 500

A variavel � �� torna-se basica com o valor � �� ? �9� ; a variavel � � � torna-se nao-basica. A nova solucao basica e indicada na tabela a seguir.

700 500 1200300 700 10001000 700 500

Atualiza-se mais uma vez os multiplicadores:

� �� >�� -? �� -? �

Fazendo � � � � , � � � ->, � � � �?

, � � � � , � � � � ?. Os custos relativos atualizados

sao:

� � � � � � � � � � � � � � -? � -> � � � � �� ? � ? � �

A transformacao de � � � em variavel basica permite uma reducao adicional do custototal de transporte. Supondo que � � � assume o valor

�, obtem-se as variacoes indicadas

na tabela abaixo:

700 � � �500 � 1200

300 � � 700 � � 10001000 700 500

A variavel � � � torna-se basica com o valor � � � �� 9� . Observe que duas variaveisbasicas, � � � e � � � , atingem o valor zero ao mesmo tempo. Uma delas deve ser declaradabasica e a outra nao-basica. Escolhe-se � � � para variavel basica com valor zero, o queleva a uma solucao basica degenerada. A nova solucao basica e indicada na tabela aseguir.

700 500 12001000 0 10001000 700 500

Atualiza-se mais uma vez os multiplicadores:

� �� -? �� -? �� -? �


Fazendo � � � � , � � � �?, � � � -?

, � � � � , � � � � . Os custos relativos atualizados

sao:

� � � � � � � � � � � � � � -> � -? � � � �� -? � � �

Como os custos das variaveis basicas sao todos nao-negativas, a solucao basica cor-rente e otima. A fabrica 1 deve enviar 700 caixas para o atacadista 2 e 500 caixas para oatacadista 3; a fabrica 2 deve enviar suas 1000 caixas para o atacadista 1. O custo totalde transporte e

� � � -> � � � � � �? � � � � � � � � � � -? � � �� -> � � �? � �9� � � B �9� � -? �(�9� � � � �� 9� ��B(B �(� � �? �9�(� � � �(� ��

Alguns casos especiais

Na aplicacao do metodo Simplex ao problema de transporte podem ocorreralgumas situacoes especiais, comentadas a seguir.

Solucoes degeneradas

Considere a tabela abaixo, que foi preenchida por meio da Regra do Noro-este com dados ligeiramente diferentes dos utilizados no Exemplo 3.9:

+ %� � � % � �

+ + % %� + �� % � %

A solucao basica obtida e degenerada, pois �� . Suponha que a variavelnao-basica �� deva ser transformada em basica. O procedimento a ser seguidoe o seguinte: substitua �� por �� ; posteriormente faz-se �� .Calcule as variacoes necessarias para manter a viabilidade da solucao, comona tabela abaixo.

+ � % � � �� % ��

+ + � � �� %� %�

+ �� % � %


Observe que � � � para que a viabilidade seja mantida. Fazendo � � ,obtem-se uma nova solucao basica degenerada, pois agora �� , como natabela abaixo.

+ %� �� % ��

+ + % % + �� % � %

O metodo prossegue com novos calculos de multiplicadores e custos relati-vos ate a convergencia para uma solucao basica otima.

Sistemas nao-balaceados

O sistema e balanceado se��

' � �� ' �

��

�� "

Podem surgir duas situacoes caso o sistema nao seja balanceado.

A soma das producoes e maior do que a soma das demandas. Neste casoacrescenta-se um destino artificial � ��+ ao problema, com custos de transportepara este destino iguais a zero e demanda

� � � � ��

' � �� ' �

��

�� "

O problema e resolvido normalmente. As demandas dos destinos sao aten-didas com o menor custo total de transporte e o excesso de producao do sis-tema e transportado para o destino artificial.

A soma das producoes e menor do que a soma das demandas. Neste casoacrescenta-se uma origem artificial � � + ao problema, com todos os custos detransporte desta origem iguais a zero e producao

� � � � ��

� � ��

' � �� ' "

O problema nao possui uma solucao viavel, mas e possıvel resolve-lo pormeio do procedimento proposto e obter a solucao de menor custo de trans-porte da producao existente. A diferenca e que as demandas dos destinos quereceberem unidades da origem artificial nao serao totalmente atendidas.


Rotas inexistentes

Pode acontecer de um ou mais pares origem-destino nao estarem servidospor rotas de transporte. Para resolver um problema de transporte com estacaracterıstica, associa-se a cada rota inexistente um custo unitario de transportemuito alto quando comparado aos custos das rotas existentes. A resolucaodo problema pelo metodo Simplex para transportes naturalmente evita rotas(criadas artificialmente) com custos unitarios altos e determina o transporte demınimo custo total pelas rotas existentes.

Rotas com pontos intermediarios

Problemas de transporte podem envolver a passagem de producoes porpontos intermediarios entre origens e destinos, como ilustra a Figura 3.7. Ob-serve que os pontos intermediarios nao possuem demandas associadas; asproducoes meramente passam por estes pontos a caminho dos pontos de des-tino.

PSfrag replacements++

%%

�

� �

� �

��

��

� �

Figura 3.7: Rotas com pontos intermediarios.

Para aplicar o metodo Simplex para transportes a problemas com pontosde transporte intermediarios, proceda da seguinte maneira: enumere todas aspossıveis rotas entre um dado par origem-destino; calcule o custo unitario decada rota origem-destino somando os custos unitarios dos trechos que com-poem a rota; determine a rota origem-destino de menor custo unitario de trans-porte; repita o procedimento para todos os pares origem-destino. Com issoobtem-se um problema equivalente com rotas diretas entre origens e destinos,ao qual o metodo Simplex para transportes pode ser aplicado.

O procedimento acima e viavel quanto o numero de rotas ligando origensdestinos e relativamente pequeno. Se este nao for o caso, uma alternativa eadotar a estrategia de modelagem e resolucao conhecida como programacaoem redes.

3.4 Problemas de Atribuicao � 95

3.4 Problemas de Atribuicao

Nos chamados problemas de atribuicao (assignment) deseja-se atribuir �

trabalhadores a � tarefas com as seguintes restricoes: a cada tarefa deve seratribuıdo um unico trabalhador (o que nao exclui a possibilidade de que ummesmo trabalhador seja atribuıdo a mais de uma tarefa) e cada trabalhadordeve ser atribuıdo a uma unica tarefa. A formulacao geral do problema e aseguinte:

(PA)

minimizar ��

' � ��

� ' � � ' �

sujeito a

��

' � �� ' � �=+ � � � + �-%.��"("�" � �

��

� ' � �=+ � ) �=+ �-%.��"("�"��

� ' � � ou � ' � � + ) � + � % ��"("�" � � � � � + � % ��"�"(" � ��

sendo que � ' � �5+ significa que o trabalhador ) e atribuıdo a tarefa � e � ' � � , caso contrario. O valor de representa o custo total da atribuicao dos �

trabalhadores as � tarefas; � ' � e o custo unitario de se alocar o trabalhador ) atarefa � .

A formulacao (PA) pode ser vista como um caso especial da formulacao(PT), problemas de transporte, nos quais as origens representam trabalhado-res, os destinos, tarefas, e as producoes e as demandas sao unitarias. O in-coveniente de tratar (PA) como um problema de transporte e a alta degene-rescencia das solucoes basicas do problema. De fato, (PA) possui �

� variaveis,%� restricoes e % �� + restricoes linearmente independentes, o mesmo numero

de variaveis basicas. Como apenas � variaveis assumem valor 1, existem sem-pre �� + variaveis basicas com valor 0, o que caracteriza solucoes basicas de-generadas. A aplicacao do metodo Simplex para problemas de transportes aoproblema (PA) tenderia a ser ineficiente.

Metodo Hungaro

O metodo hungaro, denominacao dada em homenagem aos pesquisado-res hungaros que o desenvolveram, explora eficientemente a estrutura do pro-blema de atribuicao. Como no problema de transporte, as restricoes do pro-blema sao representadas por uma tabela, como indicada abaixo.

� � � � � � �� ...

......

...� � � � � � ��


Observe que qualquer atribuicao viavel de trabalhadores a tarefas e tal quea soma de cada linha e a soma de cada coluna e igual a 1. Logo, nenhumalinha ou coluna pode ter mais do que uma variavel assumindo o valor 1. Umatabela similar e utilizada para representar os custos unitarios, por hipotese nao-negativos, do problema:

�(� � �(� � �� (� �� ...

......

...� � � � � � ��

Suponha que � ' � �*)-� � � + �-%.��"("�" � � , seja uma atribuicao factıvel do pro-blema. A soma total dos produtos celula-a-celula das duas tabelas anteriorescorrespondente o valor da funcao-objetivo (custo total da atribuicao) do pro-blema:

� �(� � � � ��4�(� � � � �� (� � � � � �� -��4� � � � � ��

...� � � � � � �4� � � � � �� "

Resolver o problema de atribuicao significa atribuir + a um conjunto de �

variaveis (dentre �� ) de tal forma que o valor de seja mınimo. Intuitivamente

as variaveis candidatas a assumirem valor + sao aquelas com menores custosunitarios. Em princıpio se poderia pensar em atribuir + as � variaveis com osmenores custos unitarios, mas geralmente essa atribuicao viola as restricoes doproblema. O metodo hungaro manipula os custos unitarios do problema deforma a obter uma atribuicao viavel de menor custo total. O metodo hungaropode ser justificado com base no metodo Simplex, mas uma abordagem maisdireta e utilizada nesta secao.

A abordagem adotada baseia-se na seguinte propriedade: a solucao otimade um problema de otimizacao nao se altera quando a funcao-objetivo e so-mada uma quantidade constante (positiva ou negativa), isto e, para um escalar� qualquer, as solucoes otimas dos problema de minimizar sujeito a restricoese minimizar � �� sujeito as mesmas restricoes sao identicas.

Assuma que �� ' ��)-� � � + � %.�("�"("�� e uma atribuicao otima viavel do pro-

blema (PA). Entao, para � ' qualquer e ) � + � %.�("�"("�� ,

� '6 � �' � �

� �' � �� ' �

8 � � ' �

pois se a solucao e viavel, � � ' � �� ' � � �� ' � �2+ para ) �2+ �-%.��"("�"�� . Da

mesma maneira, para�� qualquer e � �=+ �-%.�("�"�"�� ,

��6 � � � � � � � � � �� 8 � �

� "


Definindo � ' � �� ' � � � ' � ��"("�" � � ' � � e subtraindo

� '6 � �' � �

� �' � �� ' �

8�� ) �=+ �-%.�("�"�"��

do valor de , obtem-se uma nova funcao-objetivo, cujo valor difere do va-lor original por uma constante ( � � � � � � � � � �� ), que apresentapelo menos � novos custos unitarios nulos, e cujo valor mınimo tambem eatingido por meio da atribuicao � � ' �

� )-� � �2+ �-%.�("�"�"�� . Em seguida realiza-seuma operacao similar envolvendo as quantidades

�� 9�9� � � �� ("�"�"(� � � � � ,� � + �-%.�("�"�"�� . Mais uma vez mantem-se a otimalidade de � � ' �

�7)-� � � + � %.�("�"("��

e custos unitarios nulos adicionais sao criados.Variaveis com custos nulos sao potenciais candidatas a assumirem valor 1.

Se existir um numero suficiente de custos nulos para permitir que � variaveisassumam esse valor e ao mesmo tempo as restricoes sejam atendidas, entao oproblema de atribuicao tera sido resolvido.

Metodo hungaro – algoritmo

Considere a tabela original de custos unitarios:

�9� � �(� � �� (� �� -� � � � �� ...

......

...� � � � � � ��

1: Encontre o custo mınimo de cada linha e construa uma nova tabela sub-traindo os custos de cada linha da tabela original pelo seu custo mınimo;

2: De posse da nova tabela, encontre o custo mınimo de cada coluna e cons-trua uma nova tabela subtraindo os custos de cada coluna pelo seu customınimo;

3: Determine o menor numero de retas (horizontais e/ou verticais) necessariaspara cobrir todos os zeros da tabela corrente de custos. (Podem havervarias maneiras de cobrir os zeros com o mesmo numero mınimo de re-tas). Se exatamente � retas forem determinadas, entao uma atribuicao decusto mınimo podera ser obtida com base nos zeros cobertos pelas retas;o algoritmo termina. Se menos do que � retas forem determinadas, sigapara o passo 4;

4: Encontre o menor elemento nao-nulo, � , da tabela corrente de custos nao–coberto pelas retas determinadas no passo 3. Subtraia � de cada elementonao–coberto pelas retas, adicione � a cada elemento coberto por duas re-tas e volte ao passo 3.


Observe que as operacoes realizadas no passo 4 sao equivalentes a adicio-nar � a cada custo de uma linha coberta e subtrair � de cada custo de colunanao–coberta. Com isso, ao menos um novo custo torna-se zero, mantem-se anao–negatividade dos custos e a otimalidade da atribuicao. O passo 4 simples-mente executa essas operacoes com uma pequena economia de calculos.

EXEMPLO 3.13 Uma certa empresa possui 4 maquinas e 4 tarefas a serem executadas.Cada maquina deve ser atribuıda a uma unica tarefa; cada tarefa deve ser executadapor uma unica maquina. Os tempos de preparacao (setup) das maquinas, indicados natabela abaixo, variam com o tipo de tarefa a ser executada.

M/T 1 2 3 41

> B � �

2 � B

3� � ? �

4 > �

A empresa deseja obter a atribuicao de maquinas a tarefas que minimize o tempototal de setup.

Observe que neste problema os tempos de setup fazem o papel de custos unitarios.(O custo de setup seria proporcional ao tempo requerido.) Observe ainda que os meno-res tempos de setup das 4 tarefas sao fornecidos pelas maquinas 1, 1, 3 e 2, respectiva-mente, mas esta atribuicao nao e viavel – mesma maquina, duas tarefas.

O metodo hungaro sera aplicado ao problema. Determina-se inicialmente os temposmınimos de cada linha da tabela a seguir.

-> B � �

� B� � ? � > �

Os valores mınimos sao 5, 2, 3 e 2, respectivamente. Subtraindo cada linha do seurespectivo mınimo, obtem-se a tabela abaixo:

� � ? � � > ?> B � � > �

Os mınimos de cada coluna da nova tabela sao 0, 0, 0 e 2. Subtrair cada coluna danova tabela do seu respectivo mınimo resulta na tabela


10 0 3 00 10 4 14 5 0 40 2 4 6

Os zeros da tabela anterior sao cobertos por um mınimo de 3 retas horizontais e/ouverticais. Por conveniencia, em vez de tracar as retas, enfatizamos em negrito os ele-mentos das linhas e colunas correspondentes.

��

10 � 1� 5

�4�

2 � 6

Como um numero menor do que 4 retas foi obtido, executa-se o passo seguinte. Omenor valor nao-coberto por retas (que nao esta em negrito) e

� � (posicao (2,4)).

Subtraindo

de cada elemento nao-coberto pelas retas e adicionando

a cada elementocoberto por duas retas, chega-se a tabela a seguir.

11 0 4 00 9 4 04 4 0 30 1 4 5

Os zeros da tabela acima sao cobertos por um mınimo de 4 retas horizontais e/ouverticais, como na tabela abaixo, o que indica o termino do algoritmo. As variaveis queassumem valor 1 sao determinadas entre aquelas associadas a custos nulos.

��

��

� 4�

3�1 � 5

A analise da tabela final indica que a unica maneira da tarefa 2 ser executada e pormeio da maquina 1, isto e, � � � � �

. Com isso, � � � � � � . Da mesma forma, a tarefa 3 sopode ser executada pela maquina 3, � ��

, e a tarefa 4, pela maquina 2, � � � � � . Com

isso, �� . Finalmente, a tarefa 1 deve ser executada pela maquina 4, �� . As

demais variaveis sao iguais a zero. �EXEMPLO 3.14 O revezamento

>�� 9� medley envolve quatro nadadores diferentes, osquais nadam sucessivamente distancias de 100 m nos estilos costa, peito, borboleta e livre.O treinador da equipe possui seis nadadores que podem fazer parte do revezamento. Ostempos medios (em segundos) dos nadadores nos estilos individuais sao os seguintes:


Nadador Costa Peito Borboleta Livre1 65 73 63 572 67 70 65 583 68 72 69 554 67 75 70 595 71 69 75 576 69 71 66 59

Como o treinador deve atribuir nadadores a estilos de forma a minimizar a somados tempos obtidos pelos quatro nadadores no revezamento ?

Para resolver o problema pelo metodo hungaro sera necessario criar dois estilos adi-cionais, nos quais os 6 nadadores terao tempos medios iguais a zero. Resolve-se o pro-blema resultante e os nadadores designados para os estilos fictıcios ficam de fora dorevezamento.

A tabela inicial para a aplicacao do metodo e

65 73 63 57 0 067 70 65 58 0 068 72 69 55 0 067 75 70 59 0 071 69 75 57 0 069 71 66 59 0 0

Os valores mınimos das linhas sao todos iguais a zero. A tabela nao e alteradano passo 1 do algoritmo. Os valores mınimos das colunas sao 65, 69, 63, 55, 0 e 0.Subtraindo os elementos das colunas dessas quantidades obtem-se a tabela abaixo.

0 4 0 2 0 02 1 2 3 0 03 3 6 0 0 02 6 7 4 0 06 0 12 2 0 04 2 3 4 0 0

O menor numero de retas cobrindo os zeros da tabela resultante e 5. Uma alternativade cobertura com 5 retas e indicada na tabela a seguir. Em vez de retas, os elementosdas linhas e colunas cobertas estao enfatizados em negrito.

� � � � � �

2 1 2 3� �

� � � � � �

2 6 7 4� �

� � ��

4 2 3 4� �


Como um numero de retas menor do que 6 foi determinado, executa-se o proximopasso do algoritmo. O menor valor nao-coberto pelas retas e

(posicao (2,2)). Sub-

traindo

de cada elemento nao-coberto pelas retas e adicionando

a cada elementocoberto por duas retas, chega-se a tabela a seguir.

0 4 0 2 1 11 0 1 2 0 03 3 6 0 1 11 5 6 3 0 06 0 12 2 1 13 1 2 3 0 0

O menor numeros de retas cobrindo os zeros da tabela acima e novamente 5. Umaalternativa de cobertura com 5 retas e indicada na tabela abaixo.

� � � � � �

1�

1 2� �

� � � � � �

1 � 6 3� �

6�

12 2� �

3�

2 3� �

O menor valor nao-coberto pelas retas e

(em duas posicoes). Subtraindo

de cadaelemento nao-coberto pelas retas e adicionando

a cada elemento coberto por duas

retas, chega-se a tabela a seguir.

0 5 0 2 2 20 0 0 1 0 03 4 6 0 2 20 5 5 2 0 05 0 11 1 1 12 1 1 2 0 0

Agora sao necessarias 6 retas para cobrir os zeros da tabela. Uma alternativa decobertura com 6 retas e indicada na tabela abaixo.

� � � � � �

� � � � � �

3 � 6�

2 2� � � � � �

5�

11�

1 1� � � � � �


Na ultima tabela existe pelo menos uma atribuicao de nadadores a estilos que fazcom que o tempo total do revezamento seja mınimo. O nadador 5 deve nadar o estilo2, � � � � �

, implicando � � � � � � . O nadador 3 deve nadar o estilo 4, � �� . Se o

nadador 1 nadar o estilo 1, � � � � � , implicando � � �� , entao o estilo 3 deve ser

nadado pelo nadador 2, � � � � � . Os nadadores 4 e 6 nao participam do revezamento

pois devem nadar os estılos fictıcios 5 e 6.Existe outra solucao para o revezamento que fornece tempo total mınimo. O nada-

dor 1 nada o estilo 3, o nadador dois nada o estilo 1, e estilos 2 e 4 pelos nadadores 5 e3, como na solucao anterior. �

Documents

ExtensoesŸ da Programac‚aoŸ Linearvalente/capt3_044.pdf · Cap· tulo 3 ExtensoesŸ da Programac‚aoŸ Linear 3.1 Programa‚caoŸ multiobjetivo Os modelos para tomada de decisoesŸ