Pewien Algorytm

[Briker]

Czy mógłby mi ktoś pomóc? bo musze rozwiązać takie zadanie:

Podaj najbardziej efektywny algorytm rozwiązujący poniższy problem

 

Kopalnie A i B dostarczaja węgiel do miast C, D i E. Kopalnia A dostarcza dziennie 500 ton,

natomiast kopalnia B dostarcza dziennie 800 ton węgla. Miasta C, D i E zużywają odpowiednio

500, 400 i 400 ton węgla dziennie. Koszt transportu, w dziesiątkach złotych, jednej tony węgla

do poszczególnych miast podaje następująca tabelka:

 

-------------------

| z\do | C | D | E |

-------------------

| A | 8 | 5 | 5 |

-------------------

| B | 4 | 6 | 8 |

-------------------

 

Jak nalezy zorganizować transport węgla, aby koszt był możliwie najmniejszy?

[Contrast]

:blink:

Z kopalni B , 500 ton do C ,300 do D;

Z kopalni A, 100 ton Do D i 400 ton do E.

:blink:

 

Ale to jest statyczne rozwiązanie dla tych akurat danych....

 

Może to ma być ze zmieniającymi się dynamicznie danymi?

Edytowane 3 Czerwca 2005 przez Contrast

[kfgz]

W Excelu jest takie narzędzie jak Solver. Będzie idealnie pasowało do twojego zadania. Niestety w tej chwili nie pamiętam dokładnie jak ten wynalazek się obsługiwało :-(. Jedna rzecz jaką pamietam to to, że w opcjach należy wybrać model liniowy.

[civi]

Ja bym zastosował taki malutki bruteforce :) Wybierasz 2 miasta o najmniejszym zapotrzebowaniu i kopalnie o najmniejszej produkcji. Lecisz po wszystkich możliwych liczbach a i b takich że a i b jest mniejsze niż produkcja kopalni i teraz rozpatruje się przypadki następująco:

Kopalnia dostarcza a węgla pierwszemu miastu, b węgla drugiemu (produkcja-b-c) trzeciemu

Kopalnia druga dostarcza miastom tyle wegla ile nie dostarczyla pierwsza.

W ten sposób w sensownym czasie sprawdzi się wszystkie możliwości.