algorytm maksymalizacji - simplex?

"W fabryce jest n pracowników i n maszyn. Wydajności pracowników są różne na różnych maszynach i są znane. Wyznaczyć przydział pracowników do maszyn maksymalizujący sumaryczną wydajność"

musze napisac program ktory obliczy cos takiego, z samym stworzeniem aplikacji w C# nie bedzie problemu, jednak problem mam z wymysleniem algorytmu ktory potrafi to policzyc. jakies pomysly lub podpowiedzi ?

PS: pomysl z policzeniem wszystkich i wybraniu najwiekszego raczej nie wchodzi w gre :-D

czytałem już o metodzie simplex, ale jakoś nie do końca potrafię znaleźć powiązanie

tak w ogóle - witam wszystkich forumowiczów, to mój pierwszy temat tutaj :-)
a i jeśli dział nieodpowiedni to proszę o przeniesienie

ej... a gdzie warunki brzegowe, bez tego to banał?

W tak postawionym problemie masz macierz NxN w której komórka reprezentuje wydajność Ni tego pracownika na Nj maszynie gdzie i,j to indeksy kolumn/wierszy.

Algorytm:
1 Wyszukujesz aij = max(A), gdzie A to zbiór komórek.
2 Usuwasz wiersz i kolumnę o indeksach i,j.
3 Jeżeli macierz nie osiągnęła wielkości 0 to wracasz do 1.

Koziołek : twój sposób nie jest poprawny.

Kozik : wpisz "metoda węgierska" w google i wszystko stanie sie jasne.

Sposób Koziołka działa źle już dla n=2.
maszyny
| 5,1 5 |
pracownicy | |
| 5 0 |
Sposób Koziołka daje rozwiązanie pracownik 1 na maszynie 1, pracownik 2 na maszynie 2, wydajność 5,1. Pracownik 1 na maszynie 2, pracownik 2 na maszynie 1 daje wydajność 10.
Ale dla n=1 jest poprawny. ;-)

Mieliśmy takie coś na Dyskretnej, tyle że dla minimum i robiło się to tak:

• Wybierasz min z każdego wiersza macierzy i odejmujesz to min od każdego wyrazu w danym wierszu.

• Zaznaczasz sobie zera które powstały w macierzy i skreślasz je najmniejszą możliwą ilością okresek (tzn skreślasz cały wiersz/kolumnę gdzie to zero jest).

• Wybierasz minimum z całej macierzy z wyrazów nieskreslonych i
  a) jeśli liczba jest nieskreslona to odejmujesz od niej to minimum
  b) jeśli liczba jest skreslona to nie robisz nic
  c) jeśli liczba jest skreslona 2x to dodajesz do niej min
  Powtarzasz tą operację aż powstanie ci w macierzy taka ilość niezależnych zer, jaka była zadana.
  W miejscach gdzie masz te zera, w macierzy początkowej masz te liczby których szukałeś, tzn będziesz miał w każdym wierszu/kolumnie jedną liczbę i sumarycznie będziesz miał najmniejszą możliwą sumę tych liczb.
  (czyli najmniejszą "nieprzydatność").