PHP - Trudne obliczenie matematyczne

Question

Opis projektu

Projekt oblicza ile żywności koń powinien mieć ten opiera się na ogromnej liczby zmiennych. Użytkownik wprowadza informacje o każdym koniu i preferowanych kanałach. Każda karma ma wiele rodzajów witamin i składników odżywczych.

1 koń wykorzystuje wiele rodzajów pasz.

Co mamy

Mamy wartości min i max dla każdego składnika odżywczego, że specyficzne potrzeby konia.

Mamy zawartość dla jednego lub więcej różnych rodzajów paszy, może to być około 20-30 różnych składników odżywczych i witamin na paszę. Mamy również cenę i chcemy tego użyć, aby zaoszczędzić pieniądze.

(Obliczanie jest tylko dla jednego konia w czasie)

przykładu

używamy, B i C stanowią składniki odżywcze.

koń wymaga: (A, B, C) min (30,7,9) MAX (35,9,17)

Kanał 1 zawiera: (a, b, c) wartości (16,2 , 3)
Feed 2 zawiera: (A, B, C) WARTOŚCI (0,4,9)

Rozwiązaniem roboczym będzie 2 * Feed1 i 1 * Feed2.

Problem

Chcę system obliczyć idealną równowagę w oparciu o wartości max/min dla każdego składnika odżywczego i nadal utrzymać ceny na możliwie najniższym poziomie.

rozwiązanie

Gdybym najpierw obliczyć najwyższą możliwą kwotę dla każdego kanału, będzie to możliwe losowo aż wydaje się działać roboczych. A następnie użytkownik będzie mógł zmienić kwoty, jeśli nie jest doskonały.

<?php 
function randomizerLoop(){ 
    foreach($feeds as $feed){ 
     $max['A'] = floor($horse_max['A']/$feed['A']); 
     $max['B'] = floor($horse_max['B']/$feed['B']); 
     $max['C'] = floor($horse_max['C']/$feed['C']); 
     $maxRand = MIN($max['A'], $max['B'], $max['C']); 

     $amounts[$feed['id']] = rand(0, $maxRand); 
    } 

    return $amounts; 
} 
?> 

Ten kod będzie próbował, aż uzyska równowagę roboczą, zamiast korzystać z kilku fajnych obliczeń, aby znaleźć saldo za pierwszym razem.

Po prostu potrzebuję pomysłu, jak go rozwiązać bez numeru rand().

Więcej informacji

Każdy użytkownik będzie mógł dodać nieskończoną liczbę koni, ale będzie w stanie obliczyć za jednego konia w czasie (na razie).

Możliwe będzie również dodawanie nieskończonej liczby kanałów (zdefiniowanych przez użytkownika), a każdy kanał może mieć 20-30 zmiennych. W zależności od rozwiązania prawdopodobnie wymagałoby to limitu źródeł dla każdego automatycznego obliczenia.

Będzie wiele kombinacji, jeśli użyjemy 20 różnych kanałów, 20-30 zmiennych dla każdego kanału, a także wtedy, gdy zdefiniujemy ilość w int zamiast samych wartości logicznych.

Answer 1

Co chcesz zrobić, to wypróbować każdą kombinację każdego kanału. Załóżmy, że istnieje 5 rodzajów kanałów. Już wiesz, jak obliczyć maksimum każdego rodzaju pliku danych. Więc zakładam, że masz coś takiego:

$feeds_cost = array of costs for each feed 
$feeds_ingredient_A = array of how much ingredient A each feed has 
$feeds_ingredient_B = array of how much ingredient B each feed has 
$feeds_ingredient_C = array of how much ingredient C each feed has 
$feeds_max = array of maximum quantity of each feed allowed 

Teraz, po 5 typów, chcesz spróbować ilości {0,0,0,0,0}, {0,0,0,0, 1}, {0,0,0,0,2} ... {$ feeds_max [0], $ feeds_max [1], $ feeds_max [2], $ feeds_max [3], $ feeds_max [4]}. Dla każdego zestawu ilościowego należy: 1. Upewnić się, że ilość spełnia minimalne wymagania. 2. Jeśli spełnia minimalne wymagania, oblicz koszt.

W tym momencie masz koszt za każdą ilość, która spełnia minimalne wymagania, ale nie przekracza maksymalnego wymagania. Nie musisz przechowywać ich wszystkich. Utrzymaj dwie zmienne: $ best_quantities (tablica zliczeń każdego kanału) i $ best_cost. Jeśli ilość ma niższy koszt przy spełnianiu wymagań, zastępujesz $ best_quantities i $ best_cost.

Wszystko jest trywialne, z wyjątkiem przechodzenia przez wszystkie ilości. To nie jest naprawdę trudne. Utrzymujesz indeks, który zwiększasz. Początkowo wynosi zero, ale przechodzi do najwyższego indeksu (4, jeśli masz 5 plików danych). Funkcja przyrost wynosi:

function increment_counts($feeds_max, $quantities, $index) 
{ 
    if($index>sizeof($quantities)) return null; 
    $quantities[$index]++; 
    if($quantities[$index] > $feeds_max[$index]) 
    { 
     $quantities[$index]=0; 
     return increment_counts($feeds_max, $quantities, $index+1); 
    } 
    return $quantities; 
} 

Zakładając, że mam wpisane, że prawidłowo przy mojej głowie, będzie liczyć przez ilościach. Nadal wywołujesz go, zwiększając indeks 0 i zastępując bieżącą ilość wartością zwracaną. Kiedy zwróci wartość null, skończysz.

Jestem pewien, że popełniłem co najmniej jedno niedopatrzenie, ale w ten sposób rozwiązałem ten problem.

Answer 2

To jest problem linear programming.

 MIN  MAX 
A 30  35 
B 7  9 
C 9  17 

      A B C 
Feed1  16 2 3 
Feed2  0 4 9 

Niech jedzenie zawiera x liczbę feed1 i y number of feed2. Zgodnie z pytaniem:

30<16*x+0*y<35 
=> 30<16x<35 

korzystanie ceil() podzielić 30 przez 16, które dadzą Ux (który jest 2). Potem masz 3 < 4y < 5, podobnie użyj ceil(), a otrzymasz y = 1.

teraz myśleć w kategoriach projekcji,

Dla dużej liczby kanałów trudno będzie obliczyć tylu równań.

Należy stosowanie matryc do simplification.The martix do równania podane powyżej są następujące: -

A * B = C 
|16 0| | x | | 30 | 
|2 4| | y | = | 7 | 
|3 9|   | 9 | 

teraz użyć Lapack::pseudoInverse() obliczyć odwrotność macierzy A i mnoży C. Następnie wystarczy zrównać wartość x i y w macierzy B na odpowiedź i wykorzystanie ceil().

Answer 3

Skupię się na wartościach MIN w celu zminimalizowania kosztów.W każdym razie, cały sens sugerowanego podejścia polega na spełnieniu pewnych celów, które mogą być tak zmienne, jak jest to wymagane (na przykład: wymuszanie składników odżywczych E & G, aby uzyskać co najmniej połowę wartości między MIN & MAX).

Podstawowa struktura składa się z trzech pętli: głównej przechodzącej przez wszystkie składniki odżywcze; i dwóch wewnętrznych, próbujących wszystkich możliwych kombinacji pomiędzy kanałami.

NUTRIENT A 
Trying feed1 until reaching minimum (because feed2 is zero). 
Best so far: 2*feed1=32A. 

NUTRIENT B 
Starting from 2*feed1=4B, +feed2 reaches minimum. 
Best so far: 2*feed1+feed2=8B. 

NUTRIENT C 
Starting from 2*feed1+feed2=15C which is fine already. 
Best so far: 2*feed1+feed2=15C. 

Bardziej zaawansowana wersja tego podejścia będzie wracając do sprawdzenia (na przykład w przypadku, gdy docelowy został osiągnięty od pierwszej chwili, jak to, co dzieje się z odżywczym C) czy lepszym rozwiązaniem byłoby możliwe. W każdym razie złożoność takiej implementacji i liczba kombinacji byłyby znacznie wyższe.

Uważam, że jest to dość elastyczne i precyzyjne podejście. Implementacja algorytmu dla wersji podstawowej nie jest zbyt trudna (ale ani zbyt prosta, dlatego nie napisałem jej tutaj) i powinna zapewniać dość dobrą dokładność i szybkość. Po przetestowaniu go i zorientowaniu się w jego działaniu możesz zacząć myśleć o jego dalszej poprawie (np. Poprzez ponowne przeanalizowanie określonego przypadku lub uwzględnienie celów innych niż MIN).