hvernig á að finna bestu lausnina í línulegri forritun


svara 1:

mynd 1: mörk línulegs forritunarvanda

mynd 2: lausn hagræðingaraðgerðar sem z = ax + með

Nú skaltu skoða lausnarreitinn, það er línuleg aðgerð, hafa einhverja halla háð breytum _a_ Og _b_ virkni

Nú munu Maxima og lágmörk í þessu plani innan marka vandamálsins falla mest á eitt af toppnum þess. Einhvern tíma er heil lína lausn þegar halla á lausnarplani hornrétt á markalínu


Nú hvað ef lausnaraðgerðin er ekki línuleg þar sem z = x ^ a + y ^ b eitthvað svoleiðis þá er lausnin ekki línuleg í þessu tilfelli optimam lausn getur verið til jafnvel innan markanna þá er önnur tæknileg tækni notuð sem mismunadreifi getur verið með tölulegum greiningu


— Athugasemd ef eitthvað mál er


svara 2:

Hugsaðu um það í samhengi við 2-dimensional vandamál og reyndu að teikna myndir. Línulegt misrétti deilir planinu í tvennt. A röð af línulegu ójöfnuði mun búa til poligon eða ómarkað svæði með stykki línuleg mörk á annarri hliðinni.

Svo hér að framan er lýst mögulegu setti. Þú getur einnig tjáð hlutlægu aðgerðina sem línu, þar sem hún er, ehhhh línuleg. Ef lp þitt er vel skilgreint er besta lausnin á þeim stað þegar línan sem svarar til hlutlægrar aðgerðar snertir poligonið fyrst. Það felur alltaf í sér hornpunkt.

Þegar þú skilur rúmfræðina sem lýst er hér að ofan, geturðu líklega skrifað niður formlega sönnun.


svara 3:

Að gefa innsæi skýringar.

Tökum aðeins eina sjálfstæða breytu (x). Hlutlæg aðgerð er línuleg, það er ax + b. Þessi aðgerð er lína og hún hefur hámarks- og lágmarksgildi át annað hvort í minnsta eða mesta gildi x.

Í tveimur víddarlénum verður aðgerðin ax + við + c sem kortast sem plan á 2D lén. Það er eins og þak á lokuðu svæði. Þakið (getur verið í hvaða átt sem er) getur haft hæsta og lægsta punktinn aðeins á mörkunum. Þess vegna eru ákjósanleg gildi á punktum á mörkunum. Jaðarpunkturinn þarf að vera við hornpunktinn. Þess vegna er ákjósanlegt gildi aðeins í hornpunkti.

Í fleiri en einni sjálfstæðri breytu er hlutafleiða með hverri breytu stuðull breytu í hlutlægri virkni. Svo að breyta aðeins einni breytu leiðir til þess að annaðhvort hlutlægt eykst einhæft eða lækkar með þeirri breytu. Ef hlutfallslegt virknigildi er á einhverjum innri stigum getum við fengið bæði hærra og lægra gildi með því að breyta aðeins þeirri breytu. Þess vegna getur innri punkturinn ekki haft ákjósanlegt gildi.

Þannig að ákjósanlegt gildi verður að vera á mörkunum. Þess vegna ætti það að vera í hornpunkti.


svara 4:

Fyrsta atriðið er að ekki er tryggt að lausnin liggi við hornpunktinn, hún gæti líka verið í jaðri. Nú eru stigasett af cx = z renniplan fyrir mismunandi gildi z.

Rúmfræði vandamálsins segir allt sem segja þarf. Hugsaðu um það út frá þessu sjónarhorni.

Ef þú fréttir af stigasettum í fyrsta skipti, lestu um hagræðingu fyrir ítarlega meðferð. Ég mæli með kúptri hagræðingu eftir Stephen Boyd.

Mynd tekin af internetinu með Google leit.


svara 5:

LPP er samsett sem annað hvort til að hámarka eða lágmarka hlutlæga virkni þína. Grafísk lausn á LPP felur almennt í sér tvær ákvarðunarbreytur í sömu röð x og y. Það fer eftir hlutlægri aðgerð sem reiknað er með mögulegu svæði þar sem besta lausnin liggur. Ef hlutlæg aðgerð hámarkar eða lágmarkar við hornpunktana er það sama talið ákjósanlegasta lausnin eftir því hvort um er að ræða hámörkunar- eða lágmörkunarvandamál.


svara 6:

Línuleg forritun hefur línulegar skorður sem eru ekkert nema planin samkvæmt rúmfræði.

Nú lítur skurðpunktur allra þessara línulegu skilyrða út eins og fjölliða.

Síðasti hluti.

Markmið aðgerð þín er einnig línuleg sem er aftur plan. Nú skaltu færa þetta plan samhliða fjölbrautinni þannig að hún yfirgefur fjölbrautina á einhverjum öfgapunkti eða safni öfgapunkta sem mynda brún á fjölbrautinni.

Hverjir eru útlimum marghyrninga? Hornpunktar. Og brún stig.

Allir þessir öfgafullu brúnpunktar með sama hlutlæga gildi hafa tvo endapunkta.

QED

Vísað til. Setning á gervifræði í kúptri hagræðingu.


svara 7:

Í grundvallaratriðum kemur það niður á þeirri einföldu staðreynd að línur (eins og í línulegri) eru beinar, þannig að aðeins þar sem línur fara yfir (hornpunktar) getur einn þáttur farið frá því að vera minni en annar í að vera stærri en annar. Sama gildir í mörgum víddum.

Sama á ekki við um ólínuleg eða stak vandamál, augljóslega.


svara 8: