Գծային ծրագրավորում

Գծային ծրագրավորում, կիրառական մաթեմատիկայի ճյուղ, որը զբաղվում է մաթեմատիկական մեթոդների և օպտիմալացման խնդիրների ալգորիթմերի մշակմամբ $n$-չափանի էվկլիդյան վեկտորական տարածության մեջ, որը սահմանափակված է գծային անհավասարումներով և հավասարումներով։

Գծային ծրագրավորումը (ԳԾ) ուռուցիկ ծրագրավորման մասնավոր դեպք է, որն էլ իր հերթին հանդիսանում է մաթեմատիկական ծրագրավորման մասնավոր դեպք։ Միաժամանակ այն հանդիսանում է ամբողջաթիվ ծրագրավորման և ոչ գծային ծրագրավորման մի շարք մեթոդների ստեղծման հիմք։ Ընդհանրացված գծային ծրագրավորում է համարվում նաև կոտորակա-գծային ծրագրավորումը։

Գծային ծրագրավորման մի շարք հատկություններ կարելի է մեկնաբանել նաև որպես բազմանկյան (բազմանիստ) հատկություններ, երկրաչափորեն ձևակերպել և ապացուցել։

Պատմություն

Տնտեսագիտության մեջ մաթեմատիկական հետազոտությունները կատարվել են դեռ 19-րդ դարում։ Մաթեմատիկական անալիզում արտադրության ընդլայնման կազմակերպումը իրականացվում էր երկրաչափական առնչությունների միջոցով՝ օգտագործելով դիֆերենցիալհաշիվների մեթոդը։ Դա հնարավորություն էր տալիս կազմել ամբողջական պատկերացում խնդիրների մասին։

Տնտեսության զարգացումը պահանջում էր քանական ցուցանիշներ, և 1920 թվականին ստեղծվեց միջոլորտային հաշվեկշիռ (ՄՈՀ)։ Այն ծառայում էր մաթեմատիկական մոդելների ստեղծման և ուսումնասիրության համար։ ՄՈՀ-ի ուսումնասիրությունները 1924-1925 թվականներին էականորեն ազդեցին ԽՍՀՄ տնտեսագետ և վիճակագիր Վ․ Վ․ Լեոնտևի աշխատանքի վրա։ Նա մշակել է արտադրության և դրա բաշխման միջճյուղային մոդելներ։

1939 թվականին Լ․ Վ․ Կանտորովիչը հրատարակեց «Արտադրության կազմակերպման և պլանավորման մաթեմատիկական մեթոդները» աշխատությունը, որտեղ ձևակերպված էին սահմանափակումներով էքստրեմումի խնդիրների նոր դաս և դրանց լուծման արդյունավետ մեթոդները՝ այդ ձևով հիմք հիմք դնելով գծային ծրագրավորման հիմունքներին։

Այսպիսի մեթոդների ուսումնասիրությունը հանգեցրեց գծային ծրագրավորման նոր ճյուղի ստեղծմանը և նոր էջ բացեց տնտեսա-մաթեմատիկական մեթոդների զարգացման մեջ։

1949 ամերիկացի մաթեմատիկոս Ջորջ Դանցիգը մշակեց գծային ծրագրավորման խնդիրների լուծման արդյունավետ մեթոդ՝ սիմպլեքս-մեթոդ։

«Ծրագրավորում» տերմինը այս դեպքում պետք է հասկանալ որպես «պլանավորում»։ Այն շարունակվել է ուսումնասիրվել 1940-ական թվականների ընթացքում Ջորջ Դանցիգի՝ գծային ծրագրավորման հիմնադիրներից մեկի կողմից, դեռ այն ժամանակ, երբ համակարգիչները չէին օգտագործվում գծային խնդիրների լուծման համար։

Ներքին կետերի մասին առաջինը հիշատակել է Ի․ Ի․ Դիկինը 1967 թվականին։

Խնդիրները

Ընդհանուր (ստանդարտ) ԳԾ խնդիր կոչվում է գծային նպատակային ֆունկցիայի մինիմումի արժեքի որոշումը Կաղապար:Sfn:

$f(x)=\sum _{j=1}^n{c}_j{x}_j=c_1{x}_1+c_2{x}_2+\dots +c_n{x}_n$

իսկ անհավասարությունների տեսքով սահմանափակումները կոչվում են Գծային ծրագրավորման հիմնական խնդիր

$\sum _{j=1}^n{a}_{ij}{x}_j⩾b_i(i=1,2,\dots ,m)$,

$x_j⩾0(j=1,2,\dots ,n)$.

Գծային ծրագրավորման խնդիրը կոչվում է կանոնական տեսքի, եթե հիմնական խնդրում անհավասարությունները գրված են հավասարությունների տեսքովԿաղապար:Sfn։

$\sum _{j=1}^n{a}_{ij}{x}_j=b_i(i=1,2,\dots ,m)$,

Հիմնական խնդիրը կարելի է բերել կանոնական տեսքի նոր փոփոխականների ավելացման միջոցով։

Գծային ծրագրավորման ընդհանուր տեսքի խնդիրները կարող են բերվել համարժեքորեն կանոնական և ընդհանուր տեսքի անհավասարությունները հավասարություններով փոխարինելով և հակառակըԿաղապար:Sfn։

Խնդրում մաքսիմումի արժեքի որոշումը կարելի է հեշտորեն գտնել փոխելով $c$ գործակիցների նշանները։

Գծային ծրագրավորման երկակի խնդիրներ

Յուրաքանչյուր հետևյալ տեսքի ԳԾ խնդիր

$\sum _{j=1}^n{a}_{ij}{x}_j\le c_i,i=1,m;$ $x_j\ge 0,j=1,n;$ $F(x)=\sum _{j=1}^n{b}_j{x}_j\to \max$

կարելի է համապասխանեցնել մեկ ուրիշ ԳԾ խնդրի հետ,որը կոչվում է երկակի խնդիր։ Ուղիղ և երկակի խնդիրների կապը այն է, որ գտնելով մեկի լուծումը՝ ուղղակիորեն կարելի է գտնել նաև մյուսինը։ Երկակի և ուղիղ խնդիրների կապը հետևյալն է՝

Ուղիղ խնդիր	Երկակի խնդիր
$\sum _{j=1}^n{a}_{ij}{x}_j\le c_i,i=1,m$	$y_i\ge 0,i=1,m$
$x_j\ge 0,j=1,n$	$\sum _{i=1}^m{a}_{ij}{y}_i\ge b_j,j=1,n$
$F(x)=\sum _{j=1}^n{b}_j{x}_j\to \max$	$T(y)=\sum _{i=1}^m{c}_i{y}_i\to \min$

Եթե $x$ և $y$ վեկտորները ուղիղ և երկակի խնդիրների թույլատրելի լուծումներն են, ապա $F(x)\le T(y)$, ընդ որում հավասարությունը հաստատվում է միայն և միայն այն դեպքում, երբ $x$ և $y$ վեկտորները օպտիմալ լուծումներ են։ Եթե խնդիրներից որևէ մեկի նպատակային ֆունկցիան սահմանափակ չէ (ուղիղ խնդրի դեպքում վերևից,երկակիի դեպքում՝ ներքևից), ապա մյուս խնդրի թույլատրելի արժեքների տիրույթը դատարկ է։

Եթե $x^{*}$ և $y^{*}$ վեկտորները համապատասխանաբար ուղիղ և երկակի խնդիրների լուծումներն են,ապա տեղի ունի հետևյալ հավասարությունը՝

$x_j^{*}(\sum _{i=1}^m{a}_{ij}{y}_i^{*}-b_j)=0,j=1,n;$

$y_i^{*}(\sum _{j=1}^n{a}_{ij}{x}_j^{*}-c_i)=0,i=1,m.$

Երկակի խնդրի այս հատկությունը թույլ են տալիս կրճատել լուծման համար պահանջվող ժամանակը, եթե ստիպված ենք լինում լուծել շատ փոփոխականներով խնդիրներ։ Այդ դեպքում, լուծելով երկակի խնդիրը և գտնելով նրա հենային պլանը, կարող ենք գտնել դրան համապատասխան ուղիղ խնդրի հենային պլանը, հետևաբար նաև լուծել խնդրի լուծումը։

Գրականություն

• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Կաղապար:Книга
• Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Արտաքին հղումներ

• Linear Program Solver (LiPS) — Անվճար օպտիմիզացման փաթեթ գծային և ամբողջաթիվ ծրագրավորման խնդիրների համար
• Вершик А. М. «O Л. В. Канторовиче и линейном программировании»
• Սահիկաշար գծային ծրագրավորման վերաբերյալ
• Барсов А. С. «Что такое линейное программирование Կաղապար:Webarchive», Гостехиздат, 1959.
• Կաղապար:Книга