Stage építése a cél szintjének függvényében görbék és a meghatározott maximális pont - studopediya
A cél -, hogy megtalálja a sokszög AFEDCB pont, ahol a cél a Z = 2x1 + 3x2 maximális értéket.
Húzzon egy vonalat 2x1 + 3x2 = const (szint vonal) úgy, hogy metszi AFEDCB sokszög (például, Const = 10). Ez a vonal az ábra mutatja a szintet a szaggatott vonal.
Ha figyelembe vesszük az értékét egy lineáris célfüggvény Z a ponthalmaz (x1, x2), a szaggatott vonal tartozó szegmens, belsejében található a hatszög, akkor ezek mind egyenlő ugyanazt az értéket (Const = 10).
Irányának meghatározásához növekedése a funkciót. Ehhez megkonstruálunk vonalszintű egy nagyobb értéket. Ez lesz egy egyenes vonal építésével párhuzamosan, de ez a hely jobb. Tehát egy adott irányba a célfüggvény értékét növeli érdekünk, hogy mozgassa, amennyire csak lehetséges ebben az irányban.
Az eltolás lehet folytatni, amíg a mozgatható vonal metszi a sokszög megvalósítható megoldásokat. Az utolsó pozícióját a vonalat, amikor van egy közös pont a sokszög AFEDCB (C pont), a maximális érték a célfüggvény Z és elérte a ponton koordinátájú x1 = 4/3 ( »1,333), x2 = 10/3 (” 3,333) . Ahol Z = 38/3 ( »12,667).
Ezt a célt teljesen. A vezetett geometriai megfontolásokból kitűnik, hogy az egyetlen megoldás. Csináljunk néhány általánosítást adódó geometriai értelmezése a problémát.
Először. Megvalósítható régió - konvex sokszög (konvex Miért területén megvalósítható megoldásokat képviseli az üres halmaz pont fırészeljen Beam Ha igen, egy példa a rendszer korlátaira ??????).
Második. A maximális a célfüggvény eléri a tetején a sokszög megengedett megoldások
47. A optimalitási feltétele megoldására lineáris programozási feladatok
A lényege az elvet optimum egy erőfeszítés, hogy válasszon egy tervezési és gazdálkodási döntések. ahol - az összetevők, amelyek a legjobban figyelembe veszi annak lehetőségét, hogy a belső és külső feltételei termelési tevékenység az irányító alá.
A „legjobb” itt azt jelenti, kiválasztása bizonyos optimum kritérium, azaz a Egyes gazdasági mutatók lehetővé teszik, hogy összehasonlítsa a hatékonyságát különböző tervezési és irányítási döntések. Hagyományos kritériumoknak optimum „maximális profit”, „olcsó”, „maximális munkák (szolgáltatások)” és mások.
A „figyelembe venné a lehetőséget belső és külső feltételek gyártási tevékenység” azt jelenti, hogy a választott megoldások (viselkedés) ró számos feltétel, azaz a kiválasztás készül egy sor lehetséges (megengedett) a megoldások D; Ezen a területen is nevezik a domain a probléma meghatározásában.
Így, hogy ültessék át a gyakorlatba az elvet optimalitást tervezés és irányítás - ez azt jelenti, hogy megoldja a problémát a szélsőséges formájában
ahol - matematikai jelölés optimalitási kritériumként - a célfüggvény a probléma (modell) optimalizálás.
Korlátozott optimalizálási probléma (2.1), (2.2) általában írott formában:
megtalálni a maximális vagy minimális a függvény
Állapot (2,5) nem kötelező, de mindig érhető el, ha szükséges. Rendeltetése szerint adott egyik lehetséges korlátozás jelei ≤ = vagy ≥. Több kompakt jelölés:
A probléma (2.6) - (2.8) - az általános probléma optimális (matematika) programot, vagy - egy matematikai modell optimális programozási feladat alapján az építési (fejlődés) az elvei optimum, a következetesség és megfelelőségét.
Vektor (egy sor kontroll változók X j. J = 1, 2, n) nevezzük a lehetséges megoldást, vagy egy tervet optimális programozási probléma, ha a komponensek megfelelnek a megszorítások xj rendszer. És a terv (lehetséges megoldás), amely biztosítja a maximális vagy minimális az objektív f (x1. X2. Xn) nevezzük optimális tervet (optimális viselkedés, vagy egyszerűen csak a határozat) optimális programozás.
Így, a kiválasztás optimális kezelése a viselkedés egy adott munka helyzet lefolytatásával összefüggő rendszeres helyzetben, a megfelelőség és az optimális gazdasági és matematikai modellezése és megoldása az optimális programozás.
Oldja meg a problémát optimális programozás (az így kapott oldat optimalizálásához a gazdasági-matematikai modell) - ez azt jelenti:
- Először is, meg az optimális terv,
amely, figyelembe véve az értelmezését annak összetevőit, és meghatározza az optimális viselkedés ebben a helyzetben;
- másrészt, hogy megtalálja az optimális értéket (maximum vagy minimum) célfüggvényt. amely szintén egy gazdasági hatásainak értékelésekor a javasolt megoldások (magatartás).
Néha lehetetlen oldat előállítása optimalizálási modell: a terület megvalósítható megoldásokat lehet üres halmaz (a feladat ellentmondó) vagy célfüggvény korlátos a tartományban.
Az első eset összefügg a helytelen színre vagy gazdasági probléma (k) fejlett gazdasági és matematikai modell (EMM). Például, a meglévő források szintje nem lehet ismert, hogy még a minimális mennyiségű munkát, amelyek szerint egy etapban, mint az előírt minimum célkitűzéseket. Ha ebben a helyzetben, akkor is szükséges, hogy megoldást találjanak a problémára, meg kell építeni egy nem üres halmaza megvalósítható megoldások megszüntetésével egy vagy több korlátok, azaz Valójában elvével összhangban alternatív egyet.
A második eset általában azt jelenti, hogy az EMM célja helyesen és néhány jelentős korlátozások hiányzik belőle.
optimális programozási feladatot legáltalánosabb formája, aszerint csoportosítva, az alábbi feltételeknek.
1. A természet az változók közötti kapcsolat:
Abban az esetben, az (a) minden funkcionális kapcsolatokat a rendszer korlátai, és az objektív függvény - lineáris függvény, a jelenléte nem-linearitás legalább egyet az alábbi elemek vezet esetében (b).
2. a természet a változók változások:
Abban az esetben (a) értéke minden kontrollváltozó teljesen kitölti egy bizonyos domain a valós számok esetén (b) az összes, vagy legalább egy változó lehet, hogy csak egész értékeket.
3. Figyelembe véve az időtényező:
A probléma (a) modellezés és a döntéshozatal végeznek annak feltételezésével függetlenségét idő a modell elemeit egy ideig, hogy veszik a tervezés és menedzsment döntések. Abban az esetben, (b) az ilyen feltevés kellően indokolt nem lehet és kell figyelembe venni az időtényező.
1. A jelen tájékoztatás a változókat:
a) feladatok teljes bizonyossággal (determinisztikus);
b) feladatai körülmények között nem teljes információt
c) a feladatokat körülmények a bizonytalanság.
A problémák (b) az egyes elemek valószínűségi értékek, azonban ismeretes, vagy további statisztikai vizsgálatokat lehet megállapítani törvényei valószínűségi eloszlás. Abban az esetben, (b) föltételezni lehetséges eredményével véletlen elemeket, de nem lehet következtetést levonni a várható eredményt.
2. Az alternatívák számát az értékelési szempontok:
a) egy egyszerű, egy-kritérium probléma;
b) egy összetett, több kritérium feladatokat.
A probléma (a) gazdaságilag elfogadható, hogy az egyik optimum kritérium vagy képes különleges eljárásokat (például „súlyú prioritások”), hogy csökkentse a több kritériumon keresést egy kritérium; Példák multiobjective problémákat tárgyalják a 3. fejezetben.
A jellemzők kombinációja lehetővé teszi, hogy csoporthoz 1-5 (besorolt) az általános formája a problémát, és az optimális programozási technikák, mint például: 1a) a 2a) 3a) 4a) 5a) - célok és módszerek a lineáris programozás, 1b) a 2a) 3a) 4a) 5a) - célok és módszerek nemlineáris programozás, 1a), 2b) 3a) 4a) 5a) - problémák és módszerek egész szám (diszkrét) lineáris programozás, stb
Új lehetőségek széles gyakorlati alkalmazásának optimális programozási módszerek modern irodai berendezések. A széles körű szakemberek mindennapi gyakorlat segítségével alapvető eleme a pénzügyi és gazdasági számítások - Microsoft Excel (MS Excel), amely tartalmaz egy speciális funkció - Solver, amely lehetővé teszi a modellt, hogy végre egyenes, lineáris és diszkrét optimalizálás. optimalizálás technológia alkalmazásával Solver megoldásában bizonyos típusú problémák optimális programozási MS Excel környezetben tárgyalja részletesen, például az irodalomban.
48. alapvető meghatározások dualitás elmélet.
Minden egyes lineáris programozási feladat lehet társítani egy másik lineáris programozási feladat. Megoldásában egyikük automatikusan megoldódik egy másik probléma. Ilyen problémák nevezzük vzaimodvoystvennymi. Megmutatjuk, hogy ezt a problémát (fogjuk nevezni az eredeti) építeni kettős.
Tekintsük meg a problémát a szálak 3.8 A tervezett termelés.
Építünk a kettős feladatát alábbi szabályokat.
A változók száma a kettős probléma száma egyenlőtlenségek az eredeti.
Az együttható mátrix a kettős probléma átültetni az eredeti mátrix együtthatók.
Column szabad szempontjából az eredeti probléma egy sor együtthatóinak a célfüggvény a kettős. A célfüggvény maximalizálva van egy feladat, hogy egy másik minimalizálható.
A körülmények nem negativitás a változók felelnek meg az eredeti problémát, a kettős korlátok egyenlőtlenség célja a másik irányba. Ezzel szemben az egyenlőtlenségeket, a korlátozásokat az eredeti felel meg a nem-negatív feltételeket a kettős.
Figyeljük meg, hogy a feladat én oszlopsorok a mátrix problémák II. Ezért az együtthatók a változók a probléma yi II - rendre az együtthatókat az i-edik egyenlőtlenség probléma I.
Egyenlőtlenségek összekötve nyilak, konjugált.