Problema de Transporte

©2000-2001 Prof.ª Gladys Castillo 1

II. Programação Linear (PL)II. Programação Linear (PL)

Capítulo 7.1:

O problema de transporte (PT). Definição e apresentação sobre forma de rede. Formulação do caso equilibrado e não equilibrado.

Exemplos Propriedades fundamentais.


Problema de Transporte. Exemplo ProtótipoProblema de Transporte. Exemplo Protótipo

Um dos principais produtos da firma Lactosal é o leite.

Os pacotes de leites são empacotados em 3 fábricas e depois são distribuídos de camião para quatro armazéns

Conhecendo os custos de transporte, a procura prevista para cada armazém e as capacidades de produção de cada fábrica, pretende-se:

OPTIMIZAR O PROGRAMA DE DISTRIBUIÇÃO DIÁRIO DO LEITE.


Problema de Transporte. Exemplo ProtótipoProblema de Transporte. Exemplo Protótipo

Os dados dos custos de uma carga de leite para cada combinação fábrica-armazém e das ofertas(produção) e procuras, em cargas de camião/dia, são os seguintes:

24 cargas diárias de leite devem

ser produzidas e distribuídas

24 cargas diárias de leite devem

ser produzidas e distribuídas

Custo por carga de camião

Armazéns

Fábricas 1 2 3 4 Oferta

1 1 2 3 4 6

2 4 3 2 4 8

3 0 2 2 1 10

Procura 4 7 6 7


Minimizar z = x11 + 2 x12 + 3 x13 + 4 x14 + 4 x21 + 3 x22 + 2 x23 + 4 x24 + 2 x32 + 2 x33 + x34

sujeito a:

x11 + x12 + x13+ x14 = 6

x21 + x22 + x23+ x24 = 8

x31 + x32 + x33+ x34 = 10

x11 + x21 + x31 = 4 x12 + x22 + x32 = 7 x13 + x23 + x33 = 6 x14 + x24 + x34 = 7

xij 0 ( i=1,2,3; j=1,2,3,4 )

Minimizar z = x11 + 2 x12 + 3 x13 + 4 x14 + 4 x21 + 3 x22 + 2 x23 + 4 x24 + 2 x32 + 2 x33 + x34

sujeito a:

x11 + x12 + x13+ x14 = 6

x21 + x22 + x23+ x24 = 8

x31 + x32 + x33+ x34 = 10

x11 + x21 + x31 = 4 x12 + x22 + x32 = 7 x13 + x23 + x33 = 6 x14 + x24 + x34 = 7

xij 0 ( i=1,2,3; j=1,2,3,4 )

Formulação do Problema de Transporte.Formulação do Problema de Transporte.Exemplo Protótipo. Exemplo Protótipo. Custo por carga de

camião

Armazéns

1012203

7

4

4

4

4

4

1

1

7

3

2

2

6

2

3

3

Procura

82

61

OfertaFábricas

Custo por carga de camião

Armazéns

1012203

7

4

4

4

4

4

1

1

7

3

2

2

6

2

3

3

Procura

82

61

OfertaFábricas


x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34

A=A=

Matriz de Restrições do Problema de Matriz de Restrições do Problema de Transporte.Transporte.

Exemplo Protótipo.Exemplo Protótipo.A matriz das restrições do problema de transporte para

o exemplo protótipo apresenta a seguinte estrutura:


FábricasFábricas ArmazénsArmazéns

1111

2222

3333

1111

2222

3333

4444

c11

x11

c34

x34

Problema de Transporte sob a forma de Rede.Problema de Transporte sob a forma de Rede.Exemplo Protótipo.Exemplo Protótipo.


Cargas de leiteCargas de leiteCargas de leiteCargas de leite Unidades de um produtoUnidades de um produtoUnidades de um produtoUnidades de um produto

3 fábricas3 fábricas 3 fábricas3 fábricas m origensm origensm origensm origens

4 armazéns4 armazéns 4 armazéns4 armazéns n destinosn destinosn destinosn destinos

Produção da fábricaProdução da fábrica iProdução da fábricaProdução da fábrica i aaii oferta da origem oferta da origem ii aaii oferta da origem oferta da origem ii

Procura no armazém Procura no armazém jProcura no armazém Procura no armazém j bbjj procura no destinoprocura no destino j j bbjj procura no destinoprocura no destino j j

Custo de transporteCusto de transporte por carga da fábrica por carga da fábrica i

para o armazém para o armazém j

Custo de transporteCusto de transporte por carga da fábrica por carga da fábrica i


ccijij custo por unidade custo por unidade transportada da origem transportada da origem i i

para o destino para o destino jj

ccijij custo por unidade custo por unidade transportada da origem transportada da origem i i


Problema de Transporte.Problema de Transporte.Do Exemplo ao Modelo do PTDo Exemplo ao Modelo do PT


xxijij cargas a distribuir cargas a distribuir da fábrica da fábrica i


xxijij cargas a distribuir cargas a distribuir da fábrica da fábrica i


xxijij unidades a unidades a distribuirda origem distribuirda origem i i


xxijij unidades a unidades a distribuirda origem distribuirda origem i i


Determinar o plano o plano óptimo de distribuição óptimo de distribuição

diária do leite diária do leite das fábricas pelos

armazéns tendo como objectivo a a

minimização do custo minimização do custo totaltotal


diária do leite diária do leite das fábricas pelos

armazéns tendo como objectivo a a

minimização do custo minimização do custo totaltotal


desse produto desse produto das origens pelos destinos tendo como objectivo

a minimização do minimização do custo totalcusto total


desse produto desse produto das origens pelos destinos tendo como objectivo

a minimização do minimização do custo totalcusto total

Problema de Transporte.Problema de Transporte.Do Exemplo ao Modelo do PTDo Exemplo ao Modelo do PT


Oferta total = Procura totalOferta total = Procura total

Destino

Origem 1 2 … n1 2 … n Oferta

11

22......

mm

aa11

aa22

..

..

..

aamm

Procura bb1 1 bb2 2 … … bbnn aai i == bbjj

cc1111 cc1212 cc1n1n


ccm1m1 ccm2m2 ccmnmn

xx1111 xx1212xx1n1n

……

xx2121 xx2222xx2n2n

……

xxm1m1 xxm2m2xxmnmn

……

..

..

..

..

..

..

..

..

..

Um problema de transporte está equilibrado se a oferta total é igual à procura total, caso

contrário está não equilibrado.

Problema de Transporte. Caso Equilibrado.Problema de Transporte. Caso Equilibrado.


Oferta total = Procura totalOferta total = Procura total

Destino

Origem 1 2 3 4 1 2 3 4 Oferta

11

22

33

66

88

1010

Procura 44 77 6 6 77 2424 =24=24

11 22 44

44 33 44

xx11 11 xx12 12 xx1414

xx21 21 xx22 22 xx2424

33xx13 13

22xx23 23

00 22 11 xx31 31 xx32 32 xx3434

22xx33 33

Para o exemplo protótipo a oferta total é igual à procura total . Este problema está equilibrado.

Problema de Transporte.Caso equilibrado.Problema de Transporte.Caso equilibrado. Exemplo protótipo Exemplo protótipo


m

i

n

jijij xcz

1 1

n

jiij ax

1

0ijx

mi ,...,2,1 ,

nj ,...,2,1 ,

Minimizar

sujeito a:restrições de

oferta

nj ,...,2,1 ,

m

ijij bx

1

restrições de procura

mi ,...,2,1 ,

Problema de Transporte.Problema de Transporte.Formulação como problema de PL.Formulação como problema de PL.


OrigensOrigens DestinosDestinosc11

x11

cij xij

cmn

xmn

aa11

aaii

aamm

bb11

bbjj

bbnn

1111

iiii

mmmm

.

.

.

.

.

.

1111

jjjj

nnnn

.

.

.

.

.

.

Esta figura ilustra o problema de transporte sob a forma de rede representados por nodos e arcos.

Os nodos representam as origens e os destinos e os arcos representam os percursos das origens aos destinos

através dos quais o produto pode ser transportado.

Problema de transporte sob a forma de rede.Problema de transporte sob a forma de rede.


O problema de transporte apresenta uma estrutura especial evidenciada pela

disposição das restrições:

A matriz dos coeficientes das

restrições é apenas constituída por uns (1)

e zeros (0) . Cada

variável xij tem como

coeficientes apenas 2 uns : um na linha

associada à origem i e outro na linha relativa

ao destino j

A matriz dos coeficientes das

restrições é apenas constituída por uns (1)

e zeros (0) . Cada

variável xij tem como

coeficientes apenas 2 uns : um na linha

associada à origem i e outro na linha relativa

ao destino j

x11 x12 ... x1n x21 x22 ... x2n … xm1 xm2 ... xmn

A=A=.. . . . .

.. . . . .

restrições dos destinos

restrições das origens

Problema de Transporte.Problema de Transporte.Estrutura especial da matriz de restrições.Estrutura especial da matriz de restrições.


Destino

Origem 1 2 … n1 2 … n n+1n+1 Oferta

11

22......

mm

aa11

aa22

..

..

..

aamm

Procura bb1 1 bb2 2 … … bbnn aai i -- bbjj



ccm1m1 ccm2m2

ccmnmn

xx11 11 xx12 12 xx1n 1n … …

xx21 21 xx22 22 xx2n 2n … …

xxm1 m1 xxm2 m2 xxmn mn

… …

..

..

..

..

..

..

..

..

..

00

00

00

xx1 n+1 1 n+1

xx2 n+12 n+1

xxm n+1 m n+1

Adicionar destino fictício

Problema de Transporte.Problema de Transporte.Oferta total superior à procura totalOferta total superior à procura total


Oferta total superior à procura total.Oferta total superior à procura total.Exemplo 1: Plano de Produção.Exemplo 1: Plano de Produção.

Uma multinacional produz aviões comerciais para diversas companhias de aviação. A última etapa no processo de produção é a produção de motores seguido da sua instalação no avião.

Para cumprir os contratos estabelecidos deve ser determinado o plano óptimo de produção dos motores para os próximos quatro meses.


os custos em milhões de dólares


Os dados para o plano da produção para os quatro meses futuros são os seguintes:

Mês Instalaçõesprogramadas

Produção máxima

Custo unitário

de produção

Custo unitário de

armazenamento

1 10 25 1.08

2 15 35 1.11 0.015

3 25 30 1.10 0.015

4 20 10 1.13 0.015



Este problema pode ser reformulado como um problema de transporte, tomando como:

Origem i - produção de motores no mês i

(i =1,2,3,4)

Destino j - instalação de motores no mês j

(j=1,2,3,4)

xij - quantidades de motores produzidos no mês i a serem

instalados no mês j

xij = 0, se i>j (primeiro produzir, depois instalar)

cij - custo por unidade de produção e armazenamento

cij= M, se i>j, como não existe custo real associado com

estes dados, podem ser penalizados com um M arbitrariamente grande.


x11 + x12 + x13+ x14 25

x21 + x22 + x23+ x24 35x31 + x32 + x33+ x34 30

x41 + x42 + x43+ x44 10

Como estas restrições são de desigualdade é preciso introduzir variáveis de folga para converte-las em restrições de igualdade.

Isto significa que é preciso introduzir um destino fictício, em que as variáveis de folga representam a capacidade de produção não utilizada por cada mês .

Como estas restrições são de desigualdade é preciso introduzir variáveis de folga para converte-las em restrições de igualdade.

Isto significa que é preciso introduzir um destino fictício, em que as variáveis de folga representam a capacidade de produção não utilizada por cada mês .

Oferta total superior à procura total.Oferta total superior à procura total.Exemplo 1. Restrições de ofertas.Exemplo 1. Restrições de ofertas.

As restrições de oferta correspondem à produção de motores para cada mês i. Estas restrições são de desigualdade limitadas pela capacidade máxima de produção por mês.

0.0151.1030253

10

35

25

Produçãomáxima

1.13

1.11

1.08

Custo unitário

de produção

20

15

10

Instalaçõesprogramadas

0.0154

0.0152

1

Custo unitário de

armazenamento

Mês

0.0151.1030253

10

35

25

Produçãomáxima

1.13

1.11

1.08

Custo unitário

de produção

20

15

10


0.0154

0.0152

1

Custo unitário de

armazenamento

Mês


x11 + x21 + x31+ x32 = 10

x21 + x22 + x23+ x24 = 15x31 + x32 + x33+ x34 = 25

x41 + x42 + x43+ x44 = 20

Como é impossível produzir motores num mês determinado para serem instalados num mês anterior, todas as variáveis de decisão correspondentes

a i >j devem ser nulas. Para obter isto, é preciso penalizar os custos correspondentes a estas variáveis com um M arbitrariamente grande, tal

como no método do “big M”.

Como é impossível produzir motores num mês determinado para serem instalados num mês anterior, todas as variáveis de decisão correspondentes

a i >j devem ser nulas. Para obter isto, é preciso penalizar os custos correspondentes a estas variáveis com um M arbitrariamente grande, tal

como no método do “big M”.

Oferta total superior à procura total. Oferta total superior à procura total. Exemplo 1. Restrições de procuras.Exemplo 1. Restrições de procuras.

As restrições de procura correspondem ao plano de instalação para cada mês j. Estas restrições são de igualdade, correspondendo ao número de instalações requisitadas para cada mês.

0.0151.1030253

10

35

25

Produçãomáxima

1.13

1.11

1.08

Custo unitário

de produção

20

15

10


0.0154

0.0152

1

Custo unitário de

armazenamento

Mês

0.0151.1030253

10

35

25

Produçãomáxima

1.13

1.11

1.08

Custo unitário

de produção

20

15

10


0.0154

0.0152

1

Custo unitário de

armazenamento

Mês


3030

Destino

Origem 1 2 3 4 1 2 3 4 55 Oferta

11

22

33

44

2525

3535

3030

1010

Procura 10 10 1515 25 25 2020 3030

1.0801.080xx1111 xx1212 xx1414

xx2121 xx2222 xx2424

xx1515

xx2525

1.0951.095 1.1101.110 1.1251.125xx1313

MM 1.1101.110 1.1251.125 1.1401.140xx2323

MM MM 1.1001.100 1.1151.115xx3131 xx3232 xx3434 xx3535xx3333

MM MM MM 1.1301.130xx4141 xx4242 xx4444 xx4545xx4343

00

00

00

00

Este problema reformulado como problema de transporte apresenta o seguinte quadro:

Os custos são calculados tomando os dados dos custos

de produção e de armazenamento. Por exemplo

para a variável xx24 24 que

representa o número de motores produzidos no mês 22 a serem instalados no mês 4, 4,

o custo correspondente c24 = 1.11 + 0.015+0.015

=1.140

Os custos são calculados tomando os dados dos custos

de produção e de armazenamento. Por exemplo

para a variável xx24 24 que

representa o número de motores produzidos no mês 22 a serem instalados no mês 4, 4,

o custo correspondente c24 = 1.11 + 0.015+0.015

=1.140

Como a oferta total é superior à procura total foi adicionado um destino fictício com uma procura igual a: Oferta Total -Procura Total = 100 -70 = 30 u.

Oferta total superior à procura total.Oferta total superior à procura total.Exemplo 1. Quadro do problema de transporte.Exemplo 1. Quadro do problema de transporte.


Destino

Origem 1 2 … n 1 2 … n Oferta

11

22......

mm

m+1m+1

aa11

aa22

..

..

..

aamm

Procura bb1 1 bb2 2 … … bbnn

bbj j -- aaii



ccm1m1 ccm2m2

ccmnmn

xx11 11 xx12 12 xx1n 1n … …

xx21 21 xx22 22 xx2n 2n … …

xxm1 m1 xxm2 m2 xxmn mn … …

..

..

..

..

..

..

..

..

..

00 00 00

xxm+1,1 m+1,1 xxm+1,2 m+1,2 xxm+1,n m+1,n

… …

Origem fictícia

Problema de Transporte.Problema de Transporte.Oferta total inferior à procura totalOferta total inferior à procura total


Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2: distribuição de recursos de agua.Exemplo 2: distribuição de recursos de agua.

Uma empresa administra a distribuição de água duma região. Para isto é preciso canalizar a água de 3 rios que estão situados fora da região e distribui-la para 4 cidades.

Agora o gerente da empresa pretende distribuir toda a água disponível dos 3 rios para as 4 cidades, de forma a pelo menos satisfazer as necessidades essenciais de cada uma, minimizando o custo total.


Os dados dos custos e requerimentos para o plano de distribuição de água são os seguintes:

os custos por unidade de medida.

A cidade 3 tem uma fonte independente da água que satisfaz as suas necessidades mínimas

A cidade 3 tem uma fonte independente da água que satisfaz as suas necessidades mínimasO rio 3 não pode fornecer a cidade 4, o que significa nos termos do problema de transporte que este percurso é impossível. Neste caso é preciso penalizar este percurso com um M arbitrariamente grande.

O rio 3 não pode fornecer a cidade 4, o que significa nos termos do problema de transporte que este percurso é impossível. Neste caso é preciso penalizar este percurso com um M arbitrariamente grande.

A cidade 4 aceita toda a água que seja possível enviar além da sua necessidade mínima de 10 u.m.

A cidade 4 aceita toda a água que seja possível enviar além da sua necessidade mínima de 10 u.m.

Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2: distribuição de recursos de água.Exemplo 2: distribuição de recursos de água.

Cidade Rio

1 2 3 4 Fornece

1 16 13 22 17 50

2 14 13 19 15 60

3 19 20 23 - 50

Necessidades mínimas 30 70 0 10

Procura 50 70 30


Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2: distribuição de recursos de água.Exemplo 2: distribuição de recursos de água.

Este problema pode ser reformulado como um problema de transporte, tomando como:

Origem i – o rio i (i =1,2,3)

Destino j – a cidade j (j=1,2,3,4)

xij - quantidade de água a enviar do rio i para a cidade j

cij - custo unitário da distribuição da água do rio i para a cidade j


x11 + x12 + x13+ x14 = 50

x21 + x22 + x23+ x24 = 60x31 + x32 + x33+ x34 = 50

Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2. Restrições de ofertas.Exemplo 2. Restrições de ofertas.

As restrições de oferta correspondem às restrições dos rios (origens). Como deverá ser distribuída toda a água disponível dos 3 rios, estas 3 restrições são de igualdade, uma por cada rio.

1007030Necessidades mínimas

-

15

17

4

502320193

70

13

13

2

30

19

22

3

50

14

16

1

Procura

602

501

ForneceCidadeRio


-

15

17

4

502320193

70

13

13

2

30

19

22

3

50

14

16

1

Procura

602

501

ForneceCidadeRio


x11 + x21 + x31 50

Cidade 1Cidade 1: procura > necessidadeCidade 1Cidade 1: procura > necessidade

x11 + x21 + x31 30 limite inferiorlimite inferior

limite superiorlimite superior

Cidade 2Cidade 2: procura = necessidadeCidade 2Cidade 2: procura = necessidade

x12 + x22 + x32 = 70

x13+ x23 + x33 30


limite superiorlimite superior


x14 + x24 + x34 10 limite inferiorlimite inferior x14 + x24 + x34 60 limite superiorlimite superior

O limite superior para a cidade 4 pode ser calculado como a diferença entre a oferta total (50+ 60+50=160) e a soma das necessidades mínimas para as restantes

cidades (30+ 70 =100) 160 - 100 = 60160 - 100 = 60 unidades. (a quantidade máxima que pode receber a cidade 4

para além da necessidade mínima )

Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2. Restrições de procura.Exemplo 2. Restrições de procura.

As restrições de procura determinam a quantidade de água que deve ser fornecida a cada cidade, e têm limites superiores e inferiores (excepto a cidade 2, onde coincidem a procura com a necessidade mínima).


-

15

17

4

502320193

70

13

13

2

30

19

22

3

50

14

16

1

Procura

602

501

ForneceCidadeRio


-

15

17

4

502320193

70

13

13

2

30

19

22

3

50

14

16

1

Procura

602

501

ForneceCidadeRio


Cidades

Origem 1 2 1 2 3 4 3 4 Oferta

Rio 1Rio 1

Rio 2Rio 2

Rio 3Rio 3

Rio Rio FicticioFicticio

5050

6060

5050

5050

Procura 50 50 7070 30 30 6060

1616 1313 1717

1414 1313 1515

00 00 00

xx1111 xx1212xx1414

xx2121 xx2222xx2424

xx4141 xx4242 xx4444

2222xx1313

1919xx2323

1919 2020 MMxx3131 xx3232

xx3434

2323xx3333

00

xx4343

Como a oferta total é inferior à procura total foi adicionada uma origem fictícia com uma oferta igual a:

Procura Total -Oferta Total = 210 -160 = 50 unidades.

Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2. Quadro do problema de transporte. Exemplo 2. Quadro do problema de transporte.


Para satisfazer as necessidades mínimas de água é preciso re-analisar os dados para cada cidade de forma a garantir que o mínimo procurado não seja fornecido pelo rio fictício.

Cidade 3Cidade 3: Como não tem necessidade mínima, então não é preciso alterar nada.

Cidade 3Cidade 3: Como não tem necessidade mínima, então não é preciso alterar nada.

Cidade 4Cidade 4: procura > necessidade (60 > 10). Como o rio fictício fornece apenas 50 unidades, pelo menos fica garantido que as 10 unidades mínimas não podem ser obtidas deste rio. Não é preciso alterar nada.

Cidade 4Cidade 4: procura > necessidade (60 > 10). Como o rio fictício fornece apenas 50 unidades, pelo menos fica garantido que as 10 unidades mínimas não podem ser obtidas deste rio. Não é preciso alterar nada.

Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2. Análise do rio fictício.Exemplo 2. Análise do rio fictício.


-

15

17

4

502320193

70

13

13

2

30

19

22

3

50

14

16

1

Procura

602

501

ForneceCidadeRio


-

15

17

4

502320193

70

13

13

2

30

19

22

3

50

14

16

1

Procura

602

501

ForneceCidadeRio


Cidade 2Cidade 2: procura = necessidade Esta cidade não pode ser fornecida pelo rio fictício. Para isto é preciso penalizar com M o percurso que une o rio fictício com a cidade 2.

Cidade 2Cidade 2: procura = necessidade Esta cidade não pode ser fornecida pelo rio fictício. Para isto é preciso penalizar com M o percurso que une o rio fictício com a cidade 2.

Cidade 1Cidade 1: procura > necessidade

Esta cidade deve ser dividida em 2 destinos: um que verifica a necessidade mínima (onde o rio fictício fica penalizado) e o outro que corresponde à quantidade de água que pode ser tomada além do requerimento mínimo.

Cidade 1Cidade 1: procura > necessidade

Esta cidade deve ser dividida em 2 destinos: um que verifica a necessidade mínima (onde o rio fictício fica penalizado) e o outro que corresponde à quantidade de água que pode ser tomada além do requerimento mínimo.

Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2. Análise do rio fictício.Exemplo 2. Análise do rio fictício.


-

15

17

4

502320193

70

13

13

2

30

19

22

3

50

14

16

1

Procura

602

501

ForneceCidadeRio


-

15

17

4

502320193

70

13

13

2

30

19

22

3

50

14

16

1

Procura

602

501

ForneceCidadeRio


Cidades

Origem 1 1' ' 11'' '' 2 2 3 4 3 4 Oferta

Rio 1Rio 1

Rio 2Rio 2

Rio 3Rio 3

Rio Rio FicticioFicticio

5050

6060

5050

5050

Procura 3030 2020 7070 30 30 6060

1616 1313 1717

1414 1313 1515

00 MM 00

2222

1919

1919 2020 MM2323

00

1616

1414

MM

1919

O rio fictício está penalizado para a cidade 2

A cidade 1 foi dividida em duas para garantir as necessidades mínimas

de 30 unidades. O rio fictício está

penalizado para a cidade 1'.

Este é o quadro final dos custos para o problema de distribuição da água, formulado como problema de transporte:

Oferta total inferior à procura totalOferta total inferior à procura totalExemplo 2. Formulação como P.T.Exemplo 2. Formulação como P.T.


Problema de Transporte. Propriedades Problema de Transporte. Propriedades fundamentais(1).fundamentais(1).

Se um problema de transporte está equilibrado, i.e., a oferta total é igual à procura total, então tem sempre soluções admissíveis.

Se um problema de transporte não está equilibrado,i.e., a oferta total não é igual à procura total, então pode ser introduzida uma origem ou um destino fictício para converter as restrições de desigualdade em igualdade e poder obter assim um problema equilibrado.

O problema de transporte tem sempre óptimo finito.

Qualquer SBA do problema de transporte tem no máximo m+n-1 variáveis básicasDo total de m+n equações só m+n-1 são linearmente independentes, existindo sempre uma equação redundante, i.e., uma equação pode ser obtida como combinação linear das restantes.


1 1 0 … 0 0 0 1 1 … 0 0 0 0 1 … 0 0 ... 0 0 0 … 1 1

0 0 0 … 0 1

B=B=

Problema de Transporte. Propriedades Problema de Transporte. Propriedades fundamentais(2).fundamentais(2).

A base correspondente a qualquer SBA do problema de transporte é uma matriz triangular.

Se as quantidades das ofertas e procuras são valores inteiros, então qualquer SBA tem sempre valores inteiros.Como a matriz da base é uma matriz triangular composta por 0 e 1, a resolução do sistema conduz necessariamente a uma solução cujas variáveis assumem apenas valores inteiros, pois apenas exige adições e subtracções.


Como m=3 e n=4 e a característica de A, c(A)=m+n-1=6, qualquer base BB tem dimensão 6x6. Uma base pode ser obtida, por exemplo, tomando as colunas P11, P12, P22, P23,

P33, P34 e eliminando à restrição 4.

P11 P12 P13 P14P21P22P23P24P31P32P33P34

(1) 1 1 1 1 0 0 0 0 0 0 0 0

(2) 0 0 0 0 1 1 1 1 0 0 0 0

(3) 0 0 0 0 0 0 0 0 1 1 1 1

(4) 1 0 0 0 1 0 0 0 1 0 0 0

(5) 0 1 0 0 0 1 0 0 0 1 0 0

(6) 0 0 1 0 0 0 1 0 0 0 1 0

(7) 0 0 0 1 0 0 0 1 0 0 0 1

A=A=

P11 P12P22P23P33P34

(1) 1 1 0 0 0 0

(2) 0 0 1 1 0 0

(3) 0 0 0 0 1 1

(5) 0 1 1 0 0 0

(6) 0 0 0 1 1 0

(7) 0 0 0 0 0 1

B =B =

P11 P12P22P23P33P34

(1) 1 1 0 0 0 0

(5) 0 1 1 0 0 0

(2) 0 0 1 1 0 0

(6) 0 0 0 1 1 0

(3) 0 0 0 0 1 1

(7) 0 0 0 0 0 1

B =B =

Base e Solução Básica Admissível para o PT.Base e Solução Básica Admissível para o PT.Minimizar z = x11 + 2 x12 + 3 x13 + 4 x14 +

4 x21 + 3 x22 + 2 x23 + 4 x24 +2 x32 + 2 x33 + x34

sujeito a:

x11 + x12 + x13+ x14 = 6x21 + x22 + x23+ x24 = 8

x31 + x32 + x33+ x34 = 10x11 + x21 + x31 = 4

x12 + x22 + x32 = 7x13 + x23 + x33 = 6

x14 + x24 + x34 = 7

xij 0 ( i=1,2,3; j=1,2,3,4 )

Trocando as linhas obtém-se uma matriz BB

triangular


XB

x11 x12 x22

x23

x33

x34

6 7 86

107

====

Uma SBA do problema é: XX = (4, 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7)= (4, 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7)Uma SBA do problema é: XX = (4, 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7)= (4, 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7)

Como a matriz B é triangular a solução do sistema é imediata:

P11 P12P22P23P33P34

(1) 1 1 0 0 0 0

(5) 0 1 1 0 0 0

(2) 0 0 1 1 0 0

(6) 0 0 0 1 1 0

(3) 0 0 0 0 1 1

(7) 0 0 0 0 0 1

x34 =7x34 =7

x33 + x34 =10

x23 + x33 = 6

x33 =3x33 =3

x23 =3x23 =3

x22 + x23 = 8 x22 =5x22 =5

x12 + x22 = 7 x12 =2x12 =2

x11 + x12 = 6 x11 =4x11 =4

Uma Solução básica Admissível para o PT.Uma Solução básica Admissível para o PT.

Automotive

Problema de Transporte