Ahoj, omlouvám se, že ještě otravuju, navíc v sobotu večer, ale tohle už je vážně poslední úloha se kterou bych potřebovala poradit. V následujícím přiřazovacím problému mi optimální náklady vyšly 27 milionů, je to správně?
Podnik zakoupil 6 nových budov B1, ..., B6, do kterých chce rozmístit 6 svých pracovišť P1, ..., P6, do každé budovy jedno pracoviště. Náklady na adaptace budov pro jednotlivá pracoviště v milionech Kč jsou uvedeny v tabulce. Navrhněte takové rozmístění pracovišť, aby celkové náklady na tyto adaptace byly minimální.
P1
P2
P3
P4
P5
P6
B1
13
4
6
11
11
3
B2
5
6
5
12
3
4
B3
2
4
1
5
7
3
B4
3
5
10
12
11
4
B5
5
7
9
11
11
11
B6
11
11
7
10
4
10
Počet možností (budov), kam lze v optimálním řešení umístit pracoviště P1 je:
a)1b) 2c) více než 2
Počet možností (budov), kam lze v optimálním řešení umístit pracoviště P2 je:
a)1b) 2c) více než 2
Počet možností (budov), kam lze v optimálním řešení umístit pracoviště P3 je:
a)1b) 2c) více než 2
Počet možností (budov), kam lze v optimálním řešení umístit pracoviště P4 je:
a)1b) 2c) více než 2
Počet možností (budov), kam lze v optimálním řešení umístit pracoviště P5 je:a)1b) 2c) více než 2
Počet možností (budov), kam lze v optimálním řešení umístit pracoviště P6 je:
a)1b) 2c) více než 2
2x
Jo tak koukám, že ninus na tom zapracovala, tak to mne potěšilo, původně jsem myslela, že jen opět nakopírovala znovu požadavek na úlohu 
No, dělám to poprvé v životě, takže ne s úplnou zárukou. Když se na tu předupravenou matici od ninus poštve ta maďarská metoda z 2. odkazu od jirbara, vychází mi postupně takto upravené matice (v a < značí "pokryté" sloupce a řádky, závorky nalezené nezávislé nuly, sloupce oddělují středníky):
v; -; -; -; v; -
10; (0); 3; 4; 8; 0; <
2; 2; 2; 5; 0; 1;
1; 2; 0; (0); 6; 2; <
(0); 1; 7; 5; 8; 1;
0; 1; 4; 2; 6; 6;
7; 6; 3; 2; (0); 6;
minimum z nepokrytých je 1
v; v; -; -; v; v
11; (0); 3; 4; 9; 0;
2; 1; 1; 4; (0); 0;
2; 2; 0; (0); 7; 2; <
0; 0; 6; 4; 8; (0);
(0); 0; 3; 1; 6; 5;
7; 5; 2; 1; 0; 5;
minimum z nepokrytých je zase 1
11; (0); 2; 3; 9; 0
2; 1; (0); 3; 0; 0
3; 3; 0; (0); 8; 3
0; 0; 5; 3; 8; (0)
(0); 0; 2; 0; 6; 5
7; 5; 2; 0; (0); 5
nyní je 6 x nezávislá 0 ve všech řádcích a sloupcích, takže pokračovat redukcemi nelze (viz Königova věta), naznačený výběr je jedním z řešení. Když se s ním vrátím k původní zadané matici, dostanu minimum účelové funkce 4+5+5+4+5+4=27.
Maximální počty budov, kam lze umístit pracoviště v optimu, určitě nejsou větší, než počty nul ve sloupcích redukované matice, tedy 2 pro P1, 3 pro P2, 2 pro P3, 3 pro P4, 2 pro P5 a 3 pro P6. Potíž je teď v tom, jestli lze všechny výsledné 0 použít jako nezávislé - to musí říci někdo, kdo viděl detailní odvození a důkaz maďarské metody, mně se ho nikde najít nepodařilo. Pokud jo, jsou uvedené počty přímo odpověďmi na otázky. Pokud ne, nenapadá mne nic, než hledat možná další řešení (kombinace nezávislých nul) tak dlouho, dokud všechny 0 nepoužiji nebo všechny kombinace nevyčerpám. To už je mi líno, dávám do placu jen ty, které mi náhodou ještě vyšly:
11; (0); 2; 3; 9; 0
2; 1; 0; 3; (0); 0
3; 3; (0); 0; 8; 3
0; 0; 5; 3; 8; (0)
(0); 0; 2; 0; 6; 5
7; 5; 2; (0); 0; 5
11; 0; 2; 3; 9; (0)
2; 1; 0; 3; (0); 0
3; 3; (0); 0; 8; 3
(0); 0; 5; 3; 8; 0
0; (0); 2; 0; 6; 5
7; 5; 2; (0); 0; 5
jak na to koukám, stačí ověřit nuly na pozicích 2,6 4,2 a 5,4 a je to
0x
Zkusím to asi za hodinu, na to aplikovat tu Kuhnovu metodu, ale jestli je to špatně nebo správně, s tím se musíte poprat sami, nikdy jsem to před tím nedělala. Každopádně se mi nelíbí za někoho dělat domácí úkoly, já ráda pomůžu, když vídím nějakou snahu, že se někdo snaží něco dozvědět, udělat a někde se zasekne, ale něco opsat a někoho jen využívat, to se ježím.
K čemu to pak je, když se nic nenaučite? To je pak akorát zápočet za podvod, který se vám jednou vymstí. Navíc řada z vás za několik hodin práce, kdy se s tím člověk moří, neuzná ani za vhodné zaregovat, natož poděkovat. Líbí se mi proto přístup tady kolegy, který chce metodu a zkusit sám, proto to udělám, to chápu a tomu fandím.
Neneseme odpovědnost za správnost informací a za škodu vzniklou jejich využitím. Jednotlivé odpovědi vyjadřují názory jejich autorů a nemusí se shodovat s názorem provozovatele poradny Poradte.cz.
Používáním poradny vyjadřujete souhlas s personifikovanou reklamou, která pomáhá financovat tento server, děkujeme.