Pesquisa Operacional

O MTODO SIMPLEX 4 O Mtodo Simplex uma metodologia que envolve uma seqncia de clculos repetitivos por meio dos quais possvel chegar soluo de um problema de programao linear. Essa seqncia de clculos recebe o nome de algoritmo. Esse mtodo, caminha pelos vrtices da regio vivel at encontrar uma soluo que no possua solues vizinhas melhores que ela. Esta a soluo tima. A soluo tima pode no existir em dois casos quando no h nenhuma soluo vivel para o problema, devido a restries incompatveis ou quando no h mximo (ou mnimo), isto , uma ou mais variveis podem tender a infinito e as restries continuarem sendo satisfeitas, o que fornece um valor sem limites para a funo objetivo. 2.1 Exemplo de um Problema O modelo de programao linear pode ser resolvido por um mtodo de soluo de sistema de equaes lineares. O processo que ser apresentado no exemplo a seguir, retirado de ANDRADE (2000), bastante intuitivo e tem por finalidade apresentar a metodologia utilizada pelo mtodo Simplex. a) Formulao do problema Uma marcenaria deseja estabelecer uma programao diria de produo. Atualmente, a oficina faz apenas dois produtos mesa e armrio, ambos de um s modelo. Para efeito de simplificao, vamos considerar que a marcenaria tem limitaes em somente dois recursos madeira e mo-de-obra, cujas disponibilidades dirias so mostradas na tabela a seguir. O processo de produo tal que, para fazer uma mesa a fbrica gasta 2 m2 de madeira e 2 H.h de mo-de-obra. Para fazer um armrio, a fbrica gasta 3 m2 de madeira e 1 H.h de mo de obra. Alm disso, o fabricante sabe que cada mesa d uma margem de contribuio para o lucro de 4 e cada armrio de 1. O problema encontrar o programa de produo que maximiza a margem de contribuio total para o lucro. b) Montagem do modelo As variveis de deciso envolvidas no problema so x1 quantidade a produzir de mesas x2 quantidade a produzir de armrios A funo objetivo Lucro z 4 x1 x2 Ao se introduzir o conceito de folga de recurso, a inequao pode ser escrita como Utilizao de