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

18

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ć?

canisrufus
źródło
4
Mmmm Bardzo fajne gówno z benzenem, toluenem i O2F2. Mam nadzieję, że nigdy nie spotkałem ich w restauracji ...
Deer Hunter
3
@Deer Hunter: Mam nadzieję, że nigdy nie przyjdę w odległości mniejszej niż 10 mil od tego miejsca uprawy ...
Michael Borgwardt
6
FOOF !
Bobson,
2
Ten problem staje się jeszcze bardziej interesujący, jeśli trzeba wziąć pod uwagę aktualną cenę jabłek i pomarańczy.
Ingo
2
„grzyby” -> jak w chmurach o tym samym kształcie?
Maciej

Odpowiedzi:

27

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
9
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
4

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,
1
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