optymalizacja, minimalna suma wybranych elementów macierzy

kubanowy88 · Post autor: **kubanowy88** » 18 wrz 2015, o 22:33

Dzień dobry,

mam pewien problem z rozwiązaniem następującego zagadnienia, które niejako sam sobie zadałem. Mamy pewną macierz kwadratową o wymiarach \(\displaystyle{ n}\) na \(\displaystyle{ n}\), w której znajdują się różne naturalne liczby. Celem jest dobór \(\displaystyle{ n}\) liczb, w taki sposób, aby ich suma była jak najmniejsza. Drugi warunek jest taki, że należy wybrać z każdego wiersza tej macierzy dokładnie jedną liczbę i z każdej kolumny należy również wybrać tylko jedną liczbę. Oczywiście nie jest poprawne rozwiązanie doboru \(\displaystyle{ n}\) najmniejszych liczb z całej macierzy, bo może się zdarzyć, że leżą one wszystkie lub część z nich w tym samym wierszu lub tej samej kolumnie. W związku z tym pytam, w jaki sposób rozwiązać to zagadnienie ręcznie na kartce papieru, ewentualnie jakiego programu do optymalizacji można by użyć i jakich instrukcji/pętli użyć po zdefiniowaniu tej macierzy.

Pozdrawiam,
Michał

kropka+ · Post autor: **kropka+** » 19 wrz 2015, o 02:14

Można to potraktować jako zagadnienie transportowe. Macierz to jednostkowe koszty transportu od \(\displaystyle{ i}\)-tego dostawcy do \(\displaystyle{ j}\)-tego odbiorcy. Mamy \(\displaystyle{ n}\) dostawców, każdy ma \(\displaystyle{ 1}\) sztukę produktu i \(\displaystyle{ n}\) odbiorców, każdy chce \(\displaystyle{ 1}\) sztukę. Minimalizujemy łączny koszt transportu. Można to policzyć ręcznie, lub w Excelu za pomocą Solvera.

Medea 2 · Post autor: **Medea 2** » 19 wrz 2015, o 10:37

Czym takie rozwiązanie różni się od siłowego, w którym przeszukujemy wszystkie możliwe kombinacje? Ich jest trochę dużo, bo \(\displaystyle{ n!}\), więc już dla \(\displaystyle{ n = 5}\) bałabym się liczyć to ręcznie.

kubanowy88 · Post autor: **kubanowy88** » 19 wrz 2015, o 11:43

Odnośnie dodatku Solver, czy mogłabyś troszkę przybliżyć, w jaki sposób zdefiniować dane do wpisania w okienku Solver - parametry? (np. mamy macierz o wymiarach \(\displaystyle{ 4}\)x\(\displaystyle{ 4}\) w komórkach \(\displaystyle{ b2}\):\(\displaystyle{ e5}\)).
Odnośnie metody "siłowej", czy w takim zagadnieniu trzeba ręcznie przeszukać wszystkie możliwe rozwiązania czy może istnieje jakiś algorytm, za pomocą którego można już na początku odrzucić część rozwiązań?

kropka+ · Post autor: **kropka+** » 19 wrz 2015, o 11:58

Medea 2 pisze:Czym takie rozwiązanie różni się od siłowego, w którym przeszukujemy wszystkie możliwe kombinacje?

Tym, że wykonamy znacznie mniej operacji.