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

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

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

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

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

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

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

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

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

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

## Խնդիրները
***Ընդհանուր (ստանդարտ) ԳԾ խնդիր*** կոչվում է գծային նպատակային ֆունկցիայի մինիմումի արժեքի որոշումը
:
: f(x)=\sum_{j=1}^n c_jx_j=c_1x_1+c_2x_2+\ldots+c_nx_n
իսկ անհավասարությունների տեսքով սահմանափակումները կոչվում են **Գծային ծրագրավորման հիմնական խնդիր**
: \sum_{j=1}^n a_{ij}x_j\geqslant b_i\quad (i=1,\;2,\;\ldots,\;m),
: x_j\geqslant 0\quad (j=1,\;2,\;\ldots,\;n).

Գծային ծրագրավորման խնդիրը կոչվում է **կանոնական տեսքի**, եթե հիմնական խնդրում անհավասարությունները գրված են հավասարությունների տեսքով։
: \sum_{j=1}^n a_{ij}x_j = b_i\quad (i=1,\;2,\;\ldots,\;m),

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

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

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

## Գծային ծրագրավորման երկակի խնդիրներ
Յուրաքանչյուր հետևյալ տեսքի ԳԾ խնդիր

\sum_{j=1}^n a_{ij} x_j \leq c_i, i=1,m; 
x_j \geq 0, j=1,n; 
F(x) = \sum_{j=1}^n b_j x_j \to \max 

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

Եթե x և y վեկտորները ուղիղ և երկակի խնդիրների թույլատրելի լուծումներն են, ապա F(x)\leq 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 Л. В. Канторовиче и линейном программировании»
* Սահիկաշար գծային ծրագրավորման վերաբերյալ
* Барсов А. С. «Что такое линейное программирование », Гостехиздат, 1959.
* 

Կատեգորիա:Գծային ծրագրավորում
Կատեգորիա:Երկրաչափական ալգորիթմներ