კომპიუტერულ მეცნიერებათა დეპარტამენტის სამეცნიერო სემინარი

2012 წლის 22 მარტს, 11 საათზე კომპიუტერულ მეცნიერებათა დეპარტამენტში ჩატარდება სამეცნიერო სემინარი თემაზე:
“წრფივ პროგრამირებაში ზოგიერთიი მათემატიკური და პროგრამული მიდგომის შესახებ’’
მომხსენებელი: პროფ. კობა გელაშვილი
მისამართი: თსუ  XI კორპუსი, აუდიტორია 204


მოკლე ანოტაცია
პრობლემის აქტუალობა.  წრფივი პროგრამირების ამოცანა (შემდეგში LP) არის ერთ-ერთი ყველაზე გამორჩეული მათემატიკური ამოცანა როგორც თეორიული, ასევე გამოყენებითი და კომერციული თვალსაზრისით, რადგან მაღალი მოთხოვნილების გამო, პროგრამული პროდუქტების ბაზარზე ძალიან პოპულარულია LP –ს ამოცანების ამოსახსნელი კომერციული პაკეტები.
LP გამოიყენება რესურსების განაწილების, წარმოების დაგეგმვის, საინვესტიციო პორტფელების შედგენის, სამხედრო სტრატეგიების განსაზღვრის მიზნით და ა.შ.. ითვლება, რომ ეკონომიკაში მისი გამოყენების შემდეგ დანახარჯები შემცირდა დაახლოებით 20%-ით, რამაც მათემატიკური მეთოდების გამოყენებაში დაარწმუნა ისეთი მეწარმეებიც და მენეჯერებიც, რომლებიც მიჩვეული იყვნენ მხოლოდ გამოცდილებასა და ინტუიციაზე დაყრდნობას.
თეორიულ კომპიუტერულ მეცნიერებაში LP წარმოადგენს ალგორითმების აგების ერთ-ერთ ძირითად საშუალებას. გარდა იმისა, რომ მრავალი ამოცანა მთელრიცხვა პროგრამირებიდან, გრაფთა თეორიიდან და ა.შ. უშუალოდ წრფივი პროგრამირების მეთოდებზე დაყრდნობით იხსნება, მთელი რიგი გამოთვლითი ამოცანებისთვის ეფექტური ალგორითმის არსებობა მტკიცდება LP –ის საშუალებებით.
ამჟამად ბევრად დიდი მოცულობის წრფივი პროგრამირების ამოცანების ამოხსნა შეიძლება, ვიდრე რამდენიმე ათეული წლის წინ. ამას აქვს ორი მიზეზი: მუდმივად იზრდება კომპიუტერების სიმძლავრე და ინტენსიურად ვითარდება LP –ის ალგორითმების თეორია. ითვლება, რომ ალგორითმებთან დაკავშირებული თეორიული პროგრესი ბევრად მნიშვნელოვანია, ვიდრე კომპიუტერების სიმძლავრის ზრდა (დეტალურად იხ. Jiˇrí Matoušek, Bernd Gärtner. Understanding and Using Linear Programming, Springer-Verlag Berlin Heidelberg 2007).
კვლევის სფეროში არსებული მდგომარეობა. LP –ში დღეისათვის მხოლოდ სიმპლექს ალგორითმი და შიგა წერტილის მეთოდები არის რეალიზებული ეფექტური პროგრამული პროდუქტების სახით. გარკვეული დიაპაზონის (მოცულობის მიხედვით)  LP–ს ამოცანებისთვის საუკეთესოდ ითვლება სიმპლექს ალგორითმი, გარკვეული დიაპაზონისთვის (ძირითადად ძალიან დიდი ზომის ამოცანები) ლიდერობს შიგა წერტილის მეთოდები. ამ ალგორითმების საუკეთესო რეალიზაციებს, რომლებიც კომერციულ პროდუქტებს წარმოადგენენ, შეუძლიათ ათეულ ათასობით შეზღუდვის და იგივე რიგის ცვლადების შემცველი ამოცანების ამოხსნა რეალურ დროში. LP –ს უაღრესად დიდი პრაქტიკული მნიშვნელობის გამო, კომერციული პროგრამული რეალიზაციები ბევრად უკეთესია ვიდრე უფასოდ (free) ხელმისაწვდომი (დეტალურად იხ. Steven S. Skiena. The Algorithm Desigh Manual. Springer 1998).
არსებობს ნაკლებად წარმატებული რამდენიმე სხვა რიცხვითი ალგორითმი. მათ ნაწილს ახლა აქვს მხოლოდ ისტორიული ინტერესი, ხოლო ზოგიერთი შეიცავს საინტერესო იდეებს შემდეგი განვითარების პერსპექტივით.
არსებული მიდგომებიდან, მოხსენება შეეხება: სიმპლექსს, გრადიენტულ მეთოდს, დაჯახების მეთოდს, შიგა წერტილის მეთოდს, ბრაუნისა და ფონ ნეიმანის მიდგომას.
მათემატიკური მეთოდებიდან, რომლებსაც შესაძლოა გარკვეული პერსპექტივა გაუჩნდეს ოპტიმიზაციის მეთოდების შერჩევისა და განვითარების, აგრეთვე
 კვალიფიციური დაპროგრამების შემთხვევვაში, აღნიშნულ იქნება საჯარიმო ფუნქციების მეთოდი. მოკლედ იქნება აღწერილი გამოსაქვეყნებლად გადაცემული ერთი პუბლიკაციის შინაარსი.
პროგრამული მეთოდებიდან რომლებიც გარკვეულ კომფორტს ქმნიან ახალი მეთოდების რეალიზაციის თვალსაზრისით, შეგვიძლია აღვნიშნოთ STL ბიბლიოთეკის საშუალებები.