Jaka to jest klasa problemu i jaka matematyka muszę wiedzieć, aby go rozwiązać?

Uprawa grzybów wymaga dość precyzyjnego składu chemicznego substratu (inaczej pożywki). Udawajmy, że uprawiamy gówna i że jest to wymagany skład ich podłoża:

Nitrogen | Benzene | Toluene | Dioxygen Diflouride
5%       | 5%      | 10%     | 80%

Chcemy stworzyć odpowiednie podłoże z materiałów, które mamy pod ręką, o których znamy skład chemiczny.

Material | Nitrogen | Benzene | Toluene | Dioxygen Diflouride
apples   | 5%       | 0%      | 5%      | 90%
oranges  | 20%      | 20%     | 50%     | 10%
Etc...

Jak to obliczyć? Przypomina mi to rozwiązywanie matryc w szkole średniej. Czy można to zrobić za pomocą matryc? Jak nazywa się ten problem? Co muszę wiedzieć, aby to rozwiązać?

algorithms computer-science

— canisrufus
źródło

Mmmm Bardzo fajne gówno z benzenem, toluenem i O2F2. Mam nadzieję, że nigdy nie spotkałem ich w restauracji ...

— Deer Hunter

@Deer Hunter: Mam nadzieję, że nigdy nie przyjdę w odległości mniejszej niż 10 mil od tego miejsca uprawy ...

— Michael Borgwardt

FOOF !

— Bobson,

Ten problem staje się jeszcze bardziej interesujący, jeśli trzeba wziąć pod uwagę aktualną cenę jabłek i pomarańczy.

— Ingo

„grzyby” -> jak w chmurach o tym samym kształcie?

— Maciej

Odpowiedzi:

Nazywa się to programowaniem liniowym . To jest NP-trudny do ograniczenia całkowitych ale istnieją sposoby radzenia sobie z tym, patrz Jeff Ericksona notatki na ten temat. Najpopularniejszą metodą jest algorytm Simplex .

Zasadniczo znajdujesz wierzchołki kształtów utworzone geometrycznie przez równania liniowe reprezentujące twoje wiązania. Idziesz dalej, aż znajdziesz optymalny. W tym przypadku stosunek potrzebnych składników podłoża.

— Inżynier świata
źródło

Programowanie liniowe nie jest tak naprawdę trudne do NP, można je rozwiązać w czasie wielomianowym. Staje się trudny tylko wtedy, gdy dodasz ograniczenia integralności (np. Nie chcesz 3,7 jabłek, ale musi to być liczba całkowita).

— Falk Hüffner,

Naprawiono ten problem

— inżynier świata z

Edycja: to nie działa, patrz komentarze

Ponieważ nie ma tutaj nierówności i minimalizacji kosztów, tak naprawdę nie potrzebujesz programowania liniowego, możesz po prostu rozwiązać go jako układ równań liniowych . Np. Jabłka + pomarańcze = 1, 0,05 * jabłka + 0,20 * pomarańcze = 0,05 itd.

— Falk Hüffner
źródło

Dopóki rozwiązania systemowe nie dają ułamków ujemnych (np. Mieszają w -22% jabłek i + 122% pomarańczy, aby uzyskać 100% ...) Rzeczywiście, układ równań liniowych daje niektórych kandydatów (rozwiązania wewnętrzne?) ale wtedy należy również sprawdzić przypadki krawędzi.

— rwong

Racja, zapomniałem o tym.

— Falk Hüffner,

Formulacja LP działałaby dobrze, ponieważ mogłaby obejmować ograniczenie, że wszystkie ilości są dodatnie.

— kevin cline

Zmiany polegają na tym, że minimalizacja kosztów w stosunku do ceny jabłek / pomarańczy byłaby kolejnym krokiem w rozwoju tego programu.

— Ingo

@ Ingo Tak, masz rację; Nie zadawałem sobie tak daleko, kiedy zadałem to pytanie. To będzie drugi krok.

— canisrufus