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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Եթե  և  վեկտորները համապատասխանաբար ուղիղ և երկակի խնդիրների լուծումներն են,ապա տեղի ունի հետևյալ հավասարությունը՝

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

Ծանոթագրություններ

Գրականություն 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

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

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