Sadržaj:
Definicija - Što znači Simplex metoda?
Jednostavna metoda, u matematičkoj optimizaciji, dobro je poznat algoritam koji se koristi za linearno programiranje. Prema časopisu Computing in Science & Engineering, ova se metoda smatra jednim od prvih 10 algoritama nastalih u dvadesetom stoljeću.
Jednostavna metoda predstavlja organiziranu strategiju za procjenu izvedivih vrhova regije. To pomaže utvrditi optimalnu vrijednost ciljane funkcije.
George Dantzig razvio je simplex metodu 1946. godine.
Metoda je poznata i kao simplex algoritam.
Tehopedia objašnjava Simplex metodu
Jednostavna metoda koristi se za iskorjenjivanje problema u linearnom programiranju. Ispituje susedne vrhove izvedivog skupa kako bi se osiguralo da se u svakoj novoj vrhovi, ciljna funkcija povećava ili na nju ne utječe. Općenito, simpleks metoda je izuzetno moćna, koja obično ima najviše 2m do 3m iteracije (ovdje m označava raspon ograničenja jednakosti) i konvergira se u predviđeno vrijeme polinoma za specifične raspodjele slučajnih ulaza.
Jednostavna metoda koristi sustavnu strategiju za generiranje i testiranje kandidatnih rješenja na linearni program. Pri svakoj iteraciji bira varijablu koja može napraviti najveću izmjenu prema minimalnom rješenju. Ta varijabla tada zamjenjuje jedan od njegovih covariara, što je najdrastičnije ograničava, premještajući simpleks metodu u drugi dio skupa rješenja i prema konačnom rješenju.
Nadalje, simpleks metoda može procijeniti ne postoji li rješenje zapravo. Može se primijetiti da je algoritam pohlepan jer se odlučuje za najbolju opciju pri svakoj iteraciji, bez potrebe za informacijama s ranije ili naredne iteracije.
Ponekad se glavna struktura podataka primjena jednostavnom metodom naziva rječnik. Rječnici sadrže prikaz skupa jednadžbi koji su pravilno podešeni na postojeću osnovu. Rječnici se mogu koristiti za intuitivno razumijevanje zašto sve varijable ulaze i ostavljaju osnovu.
