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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search

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

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

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

Պատմություն[խմբագրել | խմբագրել կոդը]

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

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

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

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

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

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

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

Խնդիրները[խմբագրել | խմբագրել կոդը]

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

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

,
.

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

,

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

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

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

Գծային ծրագրավորման երկակի խնդիրներ[խմբագրել | խմբագրել կոդը]

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

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

Ուղիղ խնդիր Երկակի խնդիր

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

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

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

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. 1,0 1,1 Աղբյուրը: Алтайская краевая универсальная научная библиотека им. В. Я. Шишкова (АКУНБ). Методы оптимизации: Учеб. пособие. Бразовская Н. В.; Алтайский государственный технический университет им. И. И. Ползунова, [Центр дистанц. обучения]. — Барнаул: Изд-во АлтГТУ, 2000. — 120 с. — ISBN 5-БНВ-МОр.9.00 — УДК/ББК 22.183.4 Б871.
  2. Дикин И. И. Итеративное решение задач линейного и квадратичного программирования // Докл. АН СССР. — 1967. — Т. 174. — № 4. — С. 747-748.
  3. Карманов, 1986, էջ 63
  4. Карманов, 1986, էջ 80
  5. Карманов, 1986, էջ 77
  6. Электронный учебник "Экономико-математические методы". Двойственность в линейном программировании

Գրականություն[խմբագրել | խմբագրել կոդը]

  • Абрамов Л. М., Капустин В.Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 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 с.
  • Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]