Nelinearno programiranje

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу

U matematici, nelinearno programiranje (NLP) je proces rešavanja optimizacionog problema gde su neka od ograničenja ili objektivnih funkcija nelinearna. Optimizacioni problem je jedan od proračuna ektrema (maksimuma, minimuma ili stacionarnih tačaka) jedne objektivne funkcije nad setom nepoznatih realnih promenljivih, koji je uslovljen zadovoljavanjem sistema jednačina i nejednačina, kolektivno zvanih ograničenja. To je potpolje matematičke optimizacije koje se bavi problemima koji nisu linearni.

Primenjivost[уреди]

Tipični nekonveksni problem je problem optimizacije troškova prevoza selekcijom iz seta transportnih metoda, od kojih jedan ili više manifestuju efekte razmera, s različitim stepenima povezivanja i ograničenjima kapaciteta. Primer bi bio transport naftnih derivata s obzirom na izbor ili kombinaciju cevovoda, željezničkih tankera, cestovnih tankera, rečne barke ili priobalskog broda. Zbog ekonomije veličine šarže, troškovne funkcije mogu imati i diskontinuitete osim glatkih promena.

U eksperimentalnoj nauci neke se jednostavnih analiza podataka (poput uklapanja spektra sa zbirom pikova poznatog položaja i oblika, ali nepoznate magnitude) mogu se obaviti linearnim metodama, ali generalno su i ovi problemi nelinearni. Tipično postoji teorijski model ispitivanog sistema s promenjivim parametrima u njemu, i model eksperimenta ili eksperimenata, koji takođe može da ima nepoznate parametre. Potrebno je da se numerički pronađe najbolje uklapanje. U ovom slučaju se često zahteva izvesna mera preciznosti rezultata, kao i samo najbolje uklapanje.

Definicija[уреди]

Neka su n, m, i p pozitivni celi brojevi. Neka je X podskup skupa Rn, neka su f, gi, i hj funkcije realnih vrednosti na X za svako i u {1, …, m} i svako j u {1, …, p}, pri čemu je bar jedna od f, gi, i hj nelinearna.

Problem nelineare minimizacije je problem optimizacije oblika

Problem nelinearne maksimizacije je definisan na sličan način.

Mogući tipovi seta ograničenja[уреди]

Postoji nekoliko mogućnosti za prirodu skupa ograničenja, poznatog i pod nazivom izvodljivi skup ili izvodljiva regija. Neizvodljiv je problem za koji nijedan skup vrednosti za izabrane promenljive ne zadovoljava sva ograničenja. To jest, ograničenja su uzajamno kontradiktorna i ne postoji rešenje, te je izvodljivi skup je prazan skup. Izvodljiv je problem za koji postoji barem jedan niz vrednosti za skup izabranih promenljivih koji zadovoljava sva ograničenja. Neograničeni problem je izvodljiv problem za koji se ciljna funkcija može učiniti boljom od bilo koje date konačne vrednosti. Prema tome, ne postoji optimalno rešenje, jer uvek postoji izvodljivo rešenje koje daje bolju vrednost objektivne funkcije od bilo kojeg predloženog rešenja.

Metodi za rešavanje problema[уреди]

Ako je ciljna funkcija f linearna, a ograničeni prostor politop, problem je problem linearnog programiranja, koji se može rešiti korišćenjem poznatih tehnika linearnog programiranja, kao što je simpleks metoda.

Ako je ciljna funkcija konkavna (problem maksimizacije), ili konveksna (problem minimizacije), i skup ograničenja je konveksan, onda se program naziva konveksnim i opšte metode iz konveksne optimizacije mogu se koristiti u većini slučajeva.

Ako je ciljna funkcija kvadratna, a ograničenja linearna, koriste se tehnike kvadratnog programiranja.

Ako je ciljna funkcija odnos konkavne i konveksne funkcije (u slučaju maksimizacije), a ograničenja su konveksna, onda se problem može transformisati u problem konveksne optimizacije pomoću tehnika frakcijskog programiranja.

Dostupno je nekoliko metoda za rešavanje nekonveksnih problema. Jedan od pristupa je upotreba posebnih formulacija problema linearnog programiranja. Druga metoda uključuje upotrebu tehnika separacije i evaluacije, gde je program podeljen na podklase koje treba rešiti konveksnim (problem minimizacije) ili linearnim aproksimacijama, koje formiraju donju granicu sveukupnih troškova u podelama. S naknadnim podelama, u nekom trenutku će se dobiti stvarno rešenje, čiji je trošak jednak najboljoj donjoj granici dobivenoj za bilo koje od približnih rešenja. Ovo rešenje je optimalno, mada je moguće da nije jedinstveno. Algoritam se takođe može zaustaviti rano, sa sigurnošću da je najbolje moguće rešenje unutar tolerancije od najbolje pronađene tačke; takve tačke se nazivaju ε-optimalnim. Prekid na ε-optimalnim tačkama je obično neophodan da bi se osigurao konačni prekid. Ovo je posebno korisno za velike, teške probleme i probleme sa nepredvidivim troškovima ili vrednostima, gde se neizvesnost može proceniti odgovarajućom procenom pouzdanosti.

Pod pretpostavkama diferencijabilnosti i konstantnih kvalifikacija, Karuš–Kan–Takerovi uslovi (KKT) pružaju potrebne uslove da rešenje bude optimalno. Pod pretpostavkom konveksnosti, ovi uslovi su takođe dovoljni. Ako su neke funkcije nediferencirane, subdiferencijabilne verzije KKT uslova su dostupne.[1]

Primeri[уреди]

Dvodimenzioni primer[уреди]

Plavi region je izvodljivi region. Tangenta linije sa izvodivim regionom predstavlja rešenje. Ta linija je najboje ostvariva konturna linija (lokus sa datom vrednošću objektivne funkcije).

Jednostavni problem (prikazan na dijagramu) može se definisati pomoću ograničenja

x1 ≥ 0
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2

sa objektivnom funkcijom koju treba maksimizovati

f(x) = x1 + x2

gde je x = (x1, x2).

Trodimenzioni primer[уреди]

Tangenta gornje površine sa ograničenim prostorom u sredini predstavlja rešenje.

Još jedan jednostavan problem (pogledajte dijagram) može se definisati pomoću ograničenja

x12x22 + x32 ≤ 2
x12 + x22 + x32 ≤ 10

sa objektivnom funkcijom koju treba maksimizovati

f(x) = x1x2 + x2x3

gde je x = (x1, x2, x3).

Reference[уреди]

  1. ^ Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. стр. xii+454. ISBN 978-0691119151. MR 2199043. 

Literatura[уреди]

Spoljašnje veze[уреди]