WikiDer > Бөлшек бағдарламалау - Википедия

Жылы математикалық оңтайландыру, бөлшек бағдарламалау жалпылау болып табылады сызықтық-бөлшектік бағдарламалау. The мақсаттық функция бөлшек бағдарламада - бұл жалпы сызықтық емес екі функцияның қатынасы. Оңтайландырылатын коэффициент көбінесе жүйенің қандай-да бір тиімділігін сипаттайды.

Анықтама

Келіңіздер ${ displaystyle f, g, h_ {j}, j = 1, ldots, m}$ болуы нақты бағаланатын функциялар жиынтықта анықталған ${ displaystyle mathbf {S} _ {0} subset mathbb {R} ^ {n}}$. Келіңіздер ${ displaystyle mathbf {S} = {{ boldsymbol {x}} in mathbf {S} _ {0}: h_ {j} ({ boldsymbol {x}}) leq 0, j = 1 , ldots, m }}$. The сызықтық емес бағдарлама

${ displaystyle { underset {{ boldsymbol {x}} in mathbf {S}} { text {maximize}}} quad { frac {f ({ boldsymbol {x}})} {g ( { boldsymbol {x}})}},}$

қайда ${ displaystyle g ({ boldsymbol {x}})> 0}$ қосулы ${ displaystyle mathbf {S}}$, бөлшек программа деп аталады.

Шұңқырлы бөлшек бағдарламалар

Ондағы бөлшек бағдарлама f теріс емес және ойыс, ж оң және дөңес, және S Бұл дөңес жиынтық а деп аталады ойыс бөлшек бағдарлама. Егер ж аффинді, f белгісімен шектелудің қажеті жоқ. Сызықтық бөлшек программа - бұл барлық функциялар болатын вогнуты бөлшек бағдарламаның ерекше жағдайы ${ displaystyle f, g, h_ {j}, j = 1, ldots, m}$ аффинді.

Қасиеттері

Функция ${ displaystyle q ({ boldsymbol {x}}) = f ({ boldsymbol {x}}) / g ({ boldsymbol {x}})}$ жарты ауданды құрайды квазиконкав қосулы S. Егер f және ж дифференциалданған болып табылады q болып табылады псевдоконкав. Сызықтық бөлшек бағдарламада мақсат функциясы болып табылады жалған.

Ойыс бағдарламаға айналу

Трансформация бойынша ${ displaystyle { boldsymbol {y}} = { frac { boldsymbol {x}} {g ({ boldsymbol {x}})}}; t = { frac {1} {g ({ boldsymbol { х}})}}}$, кез-келген вогнуты фракциялық бағдарламаны эквивалентті-параметрге айналдыруға болады ойыс бағдарламасы ^[1]

${ displaystyle { begin {aligned} { underset {{ frac { boldsymbol {y}} {t}} in mathbf {S} _ {0}} { text {maximize}}} quad & tf солға ({ frac { boldsymbol {y}} {t}} right) { text {subject to}} quad & tg left ({ frac { boldsymbol {y}} {t}} right) leq 1, & t geq 0. end {aligned}}}$

Егер ж аффинді, бірінші шектеу өзгерді ${ displaystyle tg ({ frac { boldsymbol {y}} {t}}) = 1}$ және бұл болжам f теріс емес болуы мүмкін.

Дуальность

Эквивалентті вогнуты бағдарламаның лагранждық дуалы болып табылады

${ displaystyle { begin {aligned} { underset { boldsymbol {u}} { text {minimize}}} quad & { underset {{ boldsymbol {x}} in mathbf {S} _ { 0}} { operatorname {sup}}} { frac {f ({ boldsymbol {x}}) - { boldsymbol {u}} ^ {T} { boldsymbol {h}} ({ boldsymbol {x) }})} {g ({ boldsymbol {x}})}} { text {subject}} quad & u_ {i} geq 0, quad i = 1, dots, m. end {тураланған}}}$

Ескертулер

Әдебиеттер тізімі

• Авриэль, Мордахай; Диверт, Уолтер Э .; Шайбл, Зигфрид; Цанг, Израиль (1988). Жалпы ойыс. Пленум баспасөз қызметі.
• Шейбл, Зигфрид (1983). «Бөлшектік бағдарламалау». Zeitschrift für Operations Research. 27: 39–54. дои:10.1007 / bf01916898.