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

Գծային ծրագրավորում, կիրառական մաթեմատիկայի ճյուղ, որը զբաղվում է մաթեմատիկական մեթոդների և օպտիմալացման խնդիրների ալգորիթմերի մշակմամբ 
  
    
      
        n
      
    
    {\displaystyle n}
  -չափանի էվկլիդյան վեկտորական տարածության մեջ, որը սահմանափակված է գծային անհավասարումներով և հավասարումներով։
Գծային ծրագրավորումը (ԳԾ) ուռուցիկ ծրագրավորման մասնավոր դեպք է, որն էլ իր հերթին հանդիսանում է մաթեմատիկական ծրագրավորման մասնավոր դեպք։ Միաժամանակ այն հանդիսանում է ամբողջաթիվ ծրագրավորման և ոչ գծային ծրագրավորման մի շարք մեթոդների ստեղծման հիմք։ Ընդհանրացված գծային ծրագրավորում է համարվում նաև կոտորակա-գծային ծրագրավորումը։
Գծային ծրագրավորման մի շարք հատկություններ կարելի է մեկնաբանել նաև որպես բազմանկյան (բազմանիստ) հատկություններ, երկրաչափորեն ձևակերպել և ապացուցել։


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


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

  
    
      
        f
        (
        x
        )
        =
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          c
          
            j
          
        
        
          x
          
            j
          
        
        =
        
          c
          
            1
          
        
        
          x
          
            1
          
        
        +
        
          c
          
            2
          
        
        
          x
          
            2
          
        
        +
        …
        +
        
          c
          
            n
          
        
        
          x
          
            n
          
        
      
    
    {\displaystyle f(x)=\sum _{j=1}^{n}c_{j}x_{j}=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}}
  իսկ անհավասարությունների տեսքով սահմանափակումները կոչվում են Գծային ծրագրավորման հիմնական խնդիր

  
    
      
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          a
          
            i
            j
          
        
        
          x
          
            j
          
        
        ⩾
        
          b
          
            i
          
        
        
        (
        i
        =
        1
        ,
        
        2
        ,
        
        …
        ,
        
        m
        )
      
    
    {\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\geqslant b_{i}\quad (i=1,\;2,\;\ldots ,\;m)}
  ,

  
    
      
        
          x
          
            j
          
        
        ⩾
        0
        
        (
        j
        =
        1
        ,
        
        2
        ,
        
        …
        ,
        
        n
        )
      
    
    {\displaystyle x_{j}\geqslant 0\quad (j=1,\;2,\;\ldots ,\;n)}
  .Գծային ծրագրավորման խնդիրը կոչվում է կանոնական տեսքի, եթե հիմնական խնդրում անհավասարությունները գրված են հավասարությունների տեսքով։

  
    
      
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          a
          
            i
            j
          
        
        
          x
          
            j
          
        
        =
        
          b
          
            i
          
        
        
        (
        i
        =
        1
        ,
        
        2
        ,
        
        …
        ,
        
        m
        )
      
    
    {\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}=b_{i}\quad (i=1,\;2,\;\ldots ,\;m)}
  ,Հիմնական խնդիրը կարելի է բերել կանոնական տեսքի նոր փոփոխականների ավելացման միջոցով։
Գծային ծրագրավորման ընդհանուր տեսքի խնդիրները կարող են բերվել համարժեքորեն կանոնական և ընդհանուր տեսքի անհավասարությունները հավասարություններով փոխարինելով և հակառակը։
Խնդրում մաքսիմումի արժեքի որոշումը կարելի է հեշտորեն գտնել փոխելով 
  
    
      
        c
      
    
    {\displaystyle c}
   գործակիցների նշանները։


== Գծային ծրագրավորման երկակի խնդիրներ ==
Յուրաքանչյուր հետևյալ տեսքի ԳԾ խնդիր
  
    
      
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          a
          
            i
            j
          
        
        
          x
          
            j
          
        
        ≤
        
          c
          
            i
          
        
        ,
        i
        =
        1
        ,
        m
        ;
      
    
    {\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leq c_{i},i=1,m;}
  

  
    
      
        
          x
          
            j
          
        
        ≥
        0
        ,
        j
        =
        1
        ,
        n
        ;
      
    
    {\displaystyle x_{j}\geq 0,j=1,n;}
  

  
    
      
        F
        (
        x
        )
        =
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          b
          
            j
          
        
        
          x
          
            j
          
        
        →
        max
      
    
    {\displaystyle F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max }
  
կարելի է համապասխանեցնել մեկ ուրիշ ԳԾ խնդրի հետ,որը կոչվում է երկակի խնդիր։ Ուղիղ և երկակի խնդիրների կապը այն է, որ գտնելով մեկի լուծումը՝ ուղղակիորեն կարելի է գտնել նաև մյուսինը։ Երկակի և ուղիղ խնդիրների կապը հետևյալն է՝

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

  
    
      
        
          x
          
            j
          
          
            ∗
          
        
        (
        
          ∑
          
            i
            =
            1
          
          
            m
          
        
        
          a
          
            i
            j
          
        
        
          y
          
            i
          
          
            ∗
          
        
        −
        
          b
          
            j
          
        
        )
        =
        0
        ,
        j
        =
        1
        ,
        n
        ;
      
    
    {\displaystyle x_{j}^{*}(\sum _{i=1}^{m}a_{ij}y_{i}^{*}-b_{j})=0,j=1,n;}
  

  
    
      
        
          y
          
            i
          
          
            ∗
          
        
        (
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          a
          
            i
            j
          
        
        
          x
          
            j
          
          
            ∗
          
        
        −
        
          c
          
            i
          
        
        )
        =
        0
        ,
        i
        =
        1
        ,
        m
        .
      
    
    {\displaystyle y_{i}^{*}(\sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,i=1,m.}
  
Երկակի խնդրի այս հատկությունը թույլ են տալիս կրճատել լուծման համար պահանջվող ժամանակը, եթե ստիպված ենք լինում լուծել շատ փոփոխականներով խնդիրներ։ Այդ դեպքում, լուծելով երկակի խնդիրը և գտնելով նրա հենային պլանը, կարող ենք գտնել դրան համապատասխան ուղիղ խնդրի հենային պլանը, հետևաբար նաև լուծել խնդրի լուծումը։


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


== Գրականություն ==
Абрамов Л. М., Капустин В.Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 1981. — 328 с.
Акоф Р., Сасиени М. Основы исследования операций. — Пер.с англ. В.Я.Алтаева. под ред. И.А.Ушакова. — М.: Мир, 1971. — 551 с.
Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9
Астафьев Н.Н. Бесконечные системы линейных неравенств в математическом программировании. — М.: Наука, 1991. — 134 с.
Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. — М.: Наука, 1991. — 446 с.
Гасс С. Линейное программирование. — М.: Физико-математическая литература, 1961. — 300 с.
Давыдов Э.Г. Исследование операций. — М.: Высшая школа, 1990. — 382 с.
Дегтярёв Ю.И. Исследование операций. — Учебник для вузов. — М.: Высшая школа, 1986. — 320 с.
Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. — М.: Наука, 1966. — 348 с.
Карманов В. Г. Математическое программирование. — 3-е издание. — М.: Наука, 1986. — 288 с.
Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. — Минск.: Вышейшая школа, 1994. — 286 с.
Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4
Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. — М.: Наука, 1969. — 424 с.
Данциг Джордж Бернард «Воспоминания о начале линейного программирования»


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