VONALOS PROGRAMOZÁSI PROBLÉMA (PPL)
Matematika
EGYÉB DOKUMENTUMOK
VONALOS PROGRAMOZÁSI PROBLÉMA (PPL)
A PPL alapvető formái, megoldások, osztályozás; a PPL gazdasági értelmezése.
A probléma matematikai programozás egy olyan vektorváltozó függvény optimális (maximális vagy minimum) meghatározását jelenti, amely teljesíti az 11511s1820l vesztegetési feltételeket (megszorítások, kapcsolatok), például egyenlőtlenségeket vagy egyenleteket, valamint a függvényváltozók nem negativitási feltételeit. Ha a matematikai programozási probléma megfogalmazásában beavatkozó összes funkció lineáris, akkor a feladatot meghívjuk a lineáris programozás problémája (PPL); különben hívják nemlineáris programozási probléma.
Alapforma - az, amely egyenlettípus-korlátokat tartalmaz.
- optimális z =
-egyenlőségi korlátozások:
- a negativitás feltételei:
A standard mátrix forma a következőképpen fejezhető ki:
ahol
- nak, nek hívják objektív funkció ( funkció gazdasági)
az X, illetve a C - vektor R n terét hívjuk meg tevékenységi tér
a vektort nevezzük erőforrás-vektor
az R m teret nevezzük erőforrástér.
Kanonikus formák
amely ellenőrzi a korlátozások rendszerét hívják a probléma megoldása (lehetséges megoldás);
- a korlátozások olyan megoldását hívják meg, amely igazolja a nem negativitás feltételeit ütemterv vagy megengedett megoldás;
- meghívják azt a programot, amelyhez a funkció kért végét végrehajtják optimális program.
Legyen a lineáris programozás problémája szabványos formában.
Lehetséges, hogy az egyenlőtlenségi korlátozásokat egyenlőségi korlátozások formájában hozzák meg azzal, hogy az egyik kifejezésben hozzáadják (vagy kivonják) az egyenlőtlenséget, amelyet változó ecart vagy kompenzációs változó.
Jelöljük az A mátrix oszlopvektorait,; akkor a korlátozások rendszere felírható:
Legyen B egy bázis a térben. Megjegyzés a B bázis egyik vektorához. Bármelyik megoldás megegyezik a B bázissal. A programhoz vezető B bázist ún. elfogadható alapon; ha ez nem program, akkor azt mondjuk, hogy B az lehetséges.
A gazdasági gyakorlatban tapasztalt lineáris programozási modellek
A lineáris programozással modellezett leggyakoribb gazdasági problémák közül a következőket mutatjuk be:
a) a gyártástervezési probléma
Egy vállalkozás válogatásban termel és m erőforrással rendelkezik. Szükséges a termelés megszervezése, ha a rendelkezésre álló erőforrások mennyisége, a konkrét fogyasztások és az egységnyi előnyök ismertek.
A PPL modell létrehozása során azonosítjuk a termelés szervezését a termelési tervvel.
Bármelyik: a rendelkezésre álló Ri erőforrások mennyisége
aij - az Ri források mennyisége, amely a fogyasztáshoz szükséges az Sj választékhoz
cj - a Sj választék által nyújtott előny.
Jelöljük xj - az Sj típusú választékok számát. Ezután a termelési tervet az oszlopvektor képviseli
Tehát a PPL a következőképpen állítható:
A koordináták meghatározása a feltételek szerint:
maximális előny elérése
b) a táplálkozás problémája
Az étrendnek tápanyagokat kell tartalmaznia az ételekben található mennyiségben
Legyen aij - az Aj élelmiszerben lévő anyagmennyiség,
cij-egységnyi élelmiszerköltség Aj.
Határozza meg a szükséges anyagmennyiség xj mennyiségét a szükséges anyagszint biztosításához, hogy az étrend teljes költsége minimális legyen.
A probléma matematikai modellje: tehát
c) Szállítási probléma
Ugyanezt a terméket újra el kell osztani az m -termelő központoktól (szállító) az n-értékesítési központokig (kedvezményezett), a szállító elérhetősége az, a kedvezményezett igénye Bj bj, az egységköltség a szállítótól a kedvezményezettnél Bj cij. A szállítás megszervezése azt jelenti, hogy meghatározzuk az egyes szállítóktól az egyes kedvezményezettekhez szállítandó termékmennyiségeket úgy, hogy a szállítás teljes költsége minimális legyen.
Megjegyezzük xij - azt a mennyiséget, amelyet a szállítótól a kedvezményezetthez szállítunk Bj.
Figyelembe véve, hogy a beszállítók rendelkezésére álló teljes összeg megegyezik a kedvezményezettek számára szükséges teljes összeggel, a probléma kiegyensúlyozottá válik, és a lineáris programozási modell:
min
d) A keverési probléma
N-nyersanyagok Mj keverékéből nyerünk terméket, az Mj alapanyag-egység aij egységnyi anyagot tartalmaz. A terméknek tartalmaznia kell legalább dh, anyagegységeket és legfeljebb dk, anyagegységeket, az alapanyagok egységköltsége Mj cj .
Határozza meg xj az Mj alapanyag mennyiségét, amelynek a termék részének kell lennie, hogy a költsége minimális legyen. A probléma PPL-ként megfogalmazott matematikai modellje:
,
,