Obyektiv funksiya- bəzi optimallaşdırma məsələsini həll etmək üçün optimallaşdırmaya (minimizasiya və ya maksimumlaşdırma) məruz qalan bir neçə dəyişənin real və ya tam funksiyası. Riyazi proqramlaşdırmada, əməliyyatların tədqiqatında, xətti proqramlaşdırmada, nəzəriyyədə istifadə olunan termin statistik həllər və riyaziyyatın digər sahələri, ilk növbədə tətbiqi xarakter daşıyır, baxmayaraq ki, optimallaşdırmanın məqsədi həm də riyazi problemin özünün həlli ola bilər. Bundan başqa məqsəd funksiyası Optimallaşdırma məsələsində bərabərliklər və ya bərabərsizliklər sistemi şəklində dəyişənlər üçün məhdudiyyətlər təyin oluna bilər. IN ümumi hal hədəf funksiyasının arqumentləri ixtiyari çoxluqlarda göstərilə bilər.
Nümunələr
Hamar funksiyalar və tənliklər sistemləri
İstənilən tənliklər sisteminin həlli məsələsi
( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \sol\((\begin(matris)F_(1)(x_(1),x_(2),\ldots,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots,x_(M))=0\end(matris) )\sağ.)
məqsəd funksiyasını minimuma endirmək problemi kimi formalaşdırmaq olar
S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots,x_(M))\qquad (1))
Əgər funksiyalar hamardırsa, o zaman minimumlaşdırma problemi gradient metodlarından istifadə etməklə həll edilə bilər.
İstənilən hamar məqsəd funksiyası üçün bütün dəyişənlərə münasibətdə qismən törəmələri 0-a bərabərləşdirmək olar (\displaystyle 0). Məqsəd funksiyasının optimalı belə tənliklər sisteminin həlli yollarından biri olacaqdır. (1) (\displaystyle (1)) funksiyası vəziyyətində bu metodun tənliklər sistemi olacaqdır. ən kiçik kvadratlar(MNC). Orijinal sistemin hər bir həlli ən kiçik kvadratlar sisteminin həllidir. Əgər ilkin sistem uyğunsuzdursa, onda həmişə həlli olan ən kiçik kvadratlar sistemi ilkin sistemin təxmini həllini əldə etməyə imkan verir. Ən kiçik kvadratlar sistemindəki tənliklərin sayı naməlumların sayı ilə üst-üstə düşür ki, bu da bəzən birgə ilkin sistemlərin həllini asanlaşdırır.
Xətti proqramlaşdırma
Başqalarına məşhur nümunə Məqsəd funksiyası xətti proqramlaşdırma məsələlərində yaranan xətti funksiyadır. Kvadrat məqsəd funksiyasından fərqli olaraq, xətti funksiyanın optimallaşdırılması yalnız xətti bərabərliklər və ya bərabərsizliklər sistemi şəklində məhdudiyyətlər olduqda mümkündür.
Kombinatorial optimallaşdırma
Kombinator məqsəd funksiyasının tipik nümunəsi səyyar satıcı probleminin məqsəd funksiyasıdır. Bu funksiya qrafikdə Hamilton dövrünün uzunluğuna bərabərdir. O, qrafikin n − 1 (\displaystyle n-1) təpələrinin dəyişdirmə çoxluğunda müəyyən edilir və qrafikin kənarlarının uzunluqları matrisi ilə müəyyən edilir. Bu cür problemlərin dəqiq həlli çox vaxt variantları sadalamaqdan keçir.
Fəsil 1. Əsas xətti proqramlaşdırma məsələsinin ifadəsi
Xətti proqramlaşdırma
Xətti proqramlaşdırma riyazi proqramlaşdırmanın ekstremal məsələlərin həlli üsullarını öyrənən bir sahəsidir. xətti asılılıq dəyişənlər və xətti test arasında. Bu cür problemlər insan fəaliyyətinin müxtəlif sahələrində geniş tətbiq tapır. Bu tip problemlərin sistemli şəkildə öyrənilməsi 1939-1940-cı illərdə başladı. L.V-nin əsərlərində. Kantoroviç.
Xətti proqramlaşdırmanın riyazi məsələlərinə bu və ya digər formada məhdud resurslardan optimal istifadə məsələləri kimi şərh edilən konkret istehsal və iqtisadi vəziyyətlərin tədqiqi daxildir.
Xətti proqramlaşdırma metodlarından istifadə etməklə həll olunan məsələlərin diapazonu kifayət qədər genişdir.Bunlar, məsələn:
istehsalın planlaşdırılmasında resurslardan optimal istifadə problemi;
qarışıq problemi (məhsulun tərkibinin planlaşdırılması);
optimal birləşmənin tapılması problemi müxtəlif növlər anbarlarda saxlama üçün məhsullar (inventarların idarə edilməsi və ya);
nəqliyyat vəzifələri (müəssisənin yerləşməsinin təhlili, malların hərəkəti).
Xətti proqramlaşdırma riyazi proqramlaşdırmanın ən inkişaf etmiş və geniş istifadə olunan bölməsidir (əlavə olaraq bura daxildir: tam, dinamik, qeyri-xətti, parametrik proqramlaşdırma). Bu aşağıdakı kimi izah olunur:
çoxlu sayda iqtisadi məsələlərin riyazi modelləri tələb olunan dəyişənlərə görə xətti olur;
Bu tip problem hazırda ən çox öyrənilmişdir. Onun üçün nəzərdə tutulmuşdur xüsusi üsullar, köməyi ilə bu problemlərin həll edildiyi və müvafiq kompüter proqramları;
bir çox xətti proqramlaşdırma problemləri həll edilərək geniş tətbiq tapmışdır;
İlkin tərtibatda xətti olmayan bəzi məsələlər, bir sıra əlavə məhdudiyyətlər və fərziyyələrdən sonra xətti ola bilər və ya xətti proqramlaşdırma üsulları ilə həll oluna biləcək formada azaldıla bilər.
İstənilən xətti proqramlaşdırma probleminin iqtisadi və riyazi modelinə aşağıdakılar daxildir: məqsəd funksiyası, optimal dəyər hansını (maksimum və ya minimum) tapmaq lazımdır; sistem şəklində məhdudiyyətlər xətti tənliklər və ya bərabərsizliklər; dəyişənlərin mənfi olmaması tələbi.
IN ümumi görünüş model aşağıdakı kimi yazılır:
məqsəd funksiyası
(1.1) məhdudiyyətlərlə
(1.2) mənfi olmayan tələblər
(1.3) harada x j– dəyişənlər (naməlum);
- xətti proqramlaşdırma məsələsinin əmsalları.
Problem (1.2) və (1.3) məhdudiyyətlərə tabe olan (1.1) funksiyasının optimal qiymətini tapmaqdır.
Məhdudiyyətlər sistemi (1.2) məsələnin funksional məhdudiyyətləri, (1.3) isə birbaşa olanlar adlanır.
(1.2) və (1.3) məhdudiyyətləri ödəyən vektor xətti proqramlaşdırma məsələsinin qəbul edilən həlli (planı) adlanır. (1.1) funksiyasının maksimum (minimum) dəyərinə çatdığı plan optimal adlanır.
1.2. Xətti proqramlaşdırma məsələlərinin həlli üçün Simpleks metodu
Simpleks metodu ilk dəfə 1947-ci ildə Amerika riyaziyyatçısı C.Dansiq tərəfindən məsələlərin həlli üçün işlənib hazırlanmış və istifadə edilmişdir.
İki ölçülü xətti proqramlaşdırma məsələləri qrafik şəkildə həll edilir. N=3 halı üçün nəzərdən keçirə bilərik üç ölçülü məkan və məqsəd funksiyası çoxhərlinin təpələrindən birində optimal qiymətə çatacaqdır.
Standart formada verilmiş LP probleminin yol verilən həlli (qəbul edilən plan) məhdudiyyətləri təmin edən sıralı nömrələr toplusudur (x1, x2, ..., xn); n ölçülü fəzada bir nöqtədir.
İcazə verilən həllər toplusu LP probleminin məqbul həllər bölgəsini (ADS) təşkil edir. ODR qabarıq çoxbucaqlıdır (çoxbucaqlı).
Ümumiyyətlə, məsələ N-naməlumları əhatə etdikdə deyə bilərik ki, məhdudlaşdırıcı şərtlər sistemi ilə müəyyən edilən mümkün həllər bölgəsi n ölçülü fəzada qabarıq çoxbucaqlı ilə təmsil olunur və məqsəd funksiyasının optimal qiyməti əldə edilir. bir və ya daha çox təpədə.
Əsas həll, bütün sərbəst dəyişənlərin sıfıra bərabər olduğu bir həlldir.
Dəstək həlli əsas mənfi olmayan həlldir. Dəstək həlli qeyri-degenerasiya və degenerasiya ola bilər. İstinad məhlulu, sıfırdan fərqli koordinatlarının sayı sistemin dərəcəsinə bərabərdirsə, qeyri-degenerativ adlanır, əks halda degenerativdir.
Məqsəd funksiyasının ifrat dəyərinə çatdığı icazə verilən həll optimal adlanır və işarələnir 
.
Dəyişənlərin sayı 3-dən çox olduqda bu məsələləri qrafik şəkildə həll etmək çox çətindir. Xətti proqramlaşdırma məsələlərinin həllinin universal üsulu var, simpleks metodu adlanır.
Simpleks metodu LP problemlərinin həlli üçün universal bir üsuldur, bir həll ilə başlayan və ən yaxşı variantın axtarışında optimal qiymətə çatana qədər mümkün həllər bölgəsinin künc nöqtələri boyunca hərəkət edən iterativ bir prosesdir.
İstənilən xətti proqramlaşdırma problemini həll etmək üçün istifadə edilə bilər.
Simpleks metodu, əldə edilən həllin ardıcıl təkmilləşdirilməsi ideyasına əsaslanır.
Simpleks metodunun həndəsi mənası məhdud polihedronun bir təpəsindən qonşuya ardıcıl keçiddir, burada məqsəd funksiyası optimal həll tapılana qədər ən yaxşı (və ya ən azı ən pis deyil) dəyəri alır - təpənin olduğu təpə. optimal dəyər məqsədin əldə edilmiş funksiyasıdır (əgər problemin yekun optimalı varsa).
Beləliklə, kanonik formaya endirilmiş məhdudiyyətlər sisteminə (bütün funksional məhdudiyyətlər bərabərlik formasına malikdir) malik olmaqla, onlar bu sistemin hər hansı əsas həllini tapır, yalnız onu mümkün qədər sadə tapmağa diqqət yetirirlər. Tapılan ilk əsas həllin mümkün olduğu ortaya çıxarsa, optimallıq yoxlanılır. Əgər optimal deyilsə, o zaman başqa, mütləq məqbul olan əsas həll yoluna keçid edilir. Simpleks metodu zəmanət verir ki, bu yeni həll ilə məqsəd funksiyası, əgər optimala çatmazsa, ona yaxınlaşacaq (və ya heç olmasa ondan uzaqlaşmayacaq). Eyni şey, optimal olan həll tapılana qədər yeni mümkün əsas həll yolu ilə edilir.
Simpleks metodunun tətbiqi prosesi onun üç əsas elementinin həyata keçirilməsini əhatə edir:
problemin hər hansı ilkin mümkün əsas həllinin müəyyən edilməsi üsulu;
ən yaxşı (daha doğrusu, daha pis deyil) həllinə keçid qaydası;
tapılan həllin optimallığının yoxlanılması meyarı.
Simpleks metodu bir sıra mərhələləri əhatə edir və aydın alqoritm (ardıcıl əməliyyatların yerinə yetirilməsi üçün aydın təlimat) şəklində tərtib edilə bilər. Bu, onu kompüterdə uğurla proqramlaşdırmağa və həyata keçirməyə imkan verir. Az sayda dəyişənlər və məhdudiyyətlər olan problemlər simpleks metodundan istifadə etməklə əl ilə həll edilə bilər.
6.1.Giriş
Optimallaşdırma. 1-ci hissə
Optimallaşdırma üsulları seçim etməyə imkan verir ən yaxşı variant hamıdan dizaynlar mümkün variantlar. IN son illər bu üsullar verilmişdir böyük diqqət, və nəticədə kompüterdən istifadə edərək optimal dizayn variantını tapmağa imkan verən bir sıra yüksək səmərəli alqoritmlər hazırlanmışdır. Bu fəsildə optimallaşdırma nəzəriyyəsinin əsasları təsvir olunur, optimal həllər üçün alqoritmlərin qurulmasının əsas prinsipləri araşdırılır, ən məşhur alqoritmlər təsvir edilir, onların üstünlükləri və çatışmazlıqları təhlil edilir.
6.2.Optimallaşdırma nəzəriyyəsinin əsasları
Ədəbiyyatda “optimallaşdırma” termini dəqiq bir həll əldə etməyə imkan verən bir proses və ya əməliyyatlar ardıcıllığını ifadə edir. Optimallaşdırmanın son məqsədi ən yaxşı və ya “optimal” həlli tapmaq olsa da, adətən məlum həlləri təkmilləşdirməkdənsə, təkmilləşdirməklə kifayətlənmək lazımdır. Buna görə də, optimallaşdırma daha çox əldə edilə bilməyən mükəmməllik arzusu kimi başa düşülür.
n naməlumlu m tənlikləri ilə təsvir edilən bəzi ixtiyari sistemi nəzərə alsaq, üç əsas problem tipini ayırd edə bilərik. Əgər m=n olarsa, məsələ cəbri adlanır. Bu problemin adətən bir həlli var. Əgər m>n olarsa, onda problem artıq müəyyən edilmişdir və bir qayda olaraq, həlli yoxdur. Nəhayət, m
Optimallaşdırma məsələlərini müzakirə etməyə başlamazdan əvvəl bir sıra tərifləri təqdim edirik.
Dizayn parametrləri
Bu termin həll olunan dizayn problemini tam və birmənalı müəyyən edən müstəqil dəyişən parametrləri ifadə edir. Dizayn parametrləri optimallaşdırma zamanı dəyərləri hesablanan naməlum kəmiyyətlərdir. Sistemin kəmiyyətcə təsvirinə xidmət edən hər hansı əsas və ya törəmə kəmiyyətlər dizayn parametrləri kimi çıxış edə bilər. Bəli, ola bilər naməlum dəyərlər uzunluq, kütlə, vaxt, temperatur. Dizayn parametrlərinin sayı verilmiş dizayn probleminin mürəkkəblik dərəcəsini xarakterizə edir. Adətən dizayn parametrlərinin sayı n ilə, dizayn parametrlərinin özləri isə müvafiq indekslərlə x ilə işarələnir. Beləliklə, bu problemin n dizayn parametrləri ilə işarələnəcəkdir
X1, x2, x3,...,xn.
Obyektiv funksiya
Bu, mühəndisin dəyərini maksimum və ya minimum etməyə çalışdığı bir ifadədir. Məqsəd funksiyası iki alternativ həlli kəmiyyətcə müqayisə etməyə imkan verir. Riyazi nöqteyi-nəzərdən məqsəd funksiyası bəzi (n+1) ölçülü səthi təsvir edir. Onun dəyəri dizayn parametrləri ilə müəyyən edilir
M=M(x 1, x 2,...,x n).
Mühəndislik təcrübəsində tez-tez rast gəlinən obyektiv funksiyaların nümunələri qiymət, çəki, güc, ölçülər, səmərəlilikdir. Yalnız bir dizayn parametri varsa, məqsəd funksiyası müstəvidə əyri ilə təmsil oluna bilər (şək. 6.1). Əgər iki dizayn parametri varsa, onda məqsəd funksiyası üçölçülü fəzada səth kimi təsvir olunacaq (şək. 6.2). Üç və ya daha çox dizayn parametrləri ilə, məqsəd funksiyası ilə müəyyən edilmiş səthlər hipersəthlər adlanır və təsvir edilə bilməz.
adi yollarla evlənmək. Məqsəd funksiyasının səthinin topoloji xassələri optimallaşdırma prosesində böyük rol oynayır, çünki ən səmərəli alqoritmin seçimi onlardan asılıdır.
Məqsəd funksiyası bəzi hallarda ən gözlənilməz formaları ala bilər. Məsələn, onu ifadə etmək həmişə mümkün olmur
Şəkil 1. Birölçülü məqsəd funksiyası.
Şəkil 6.2 İkiölçülü məqsəd funksiyası.
qapalı riyazi forma, digər hallarda ola bilər
hissə-hissə hamar funksiyanı təmsil edir. Məqsəd funksiyasını müəyyən etmək üçün bəzən texniki məlumat cədvəli (məsələn, su buxarının vəziyyəti cədvəli) və ya təcrübə tələb oluna bilər. Bəzi hallarda dizayn parametrləri yalnız tam qiymətləri qəbul edir. Məsələn, dişlərin sayı ola bilər dişli ötürücü və ya flanşdakı boltlar sayı. Bəzən dizayn parametrlərinin yalnız iki mənası var - bəli və ya yox. Məhsulu alan alıcının yaşadığı məmnunluq, etibarlılıq, estetika kimi keyfiyyət parametrləri optimallaşdırma prosesində nəzərə almaq çətindir, çünki onları kəmiyyətcə xarakterizə etmək demək olar ki, mümkün deyil. Bununla belə, məqsəd funksiyası hansı formada təqdim olunursa, o, dizayn parametrlərinin birmənalı funksiyası olmalıdır.
Bir sıra optimallaşdırma problemləri birdən çox məqsəd funksiyasının tətbiqini tələb edir. Bəzən onlardan biri digəri ilə uyğun gəlmir. Buna misal olaraq, eyni zamanda maksimum güc, minimum çəki və minimum xərc tələb olunan təyyarə dizaynını göstərmək olar. Belə hallarda konstruktor prioritetlər sistemini təqdim etməli və hər bir məqsəd funksiyasına müəyyən ölçüsüz çarpan təyin etməlidir. Nəticədə, optimallaşdırma prosesi zamanı bir mürəkkəb məqsəd funksiyasından istifadə etməyə imkan verən “kompromis funksiyası” meydana çıxır.
Minimum və maksimum tapmaq
Bəzi optimallaşdırma alqoritmləri maksimumu, digərləri isə minimumu tapmaq üçün nəzərdə tutulmuşdur. Bununla belə, həll olunan ekstremum məsələsinin növündən asılı olmayaraq, eyni alqoritmdən istifadə edə bilərsiniz, çünki minimumlaşdırma məsələsi məqsəd funksiyasının işarəsini tərsinə çevirməklə asanlıqla maksimum axtarış məsələsinə çevrilə bilər. Bu texnika Şəkil 6.3-də təsvir edilmişdir.
Dizayn sahəsi
Bu, bütün n dizayn parametrləri ilə müəyyən edilən ərazinin adıdır. Dizayn sahəsi göründüyü qədər böyük deyil, çünki adətən bir sıra ilə məhdudlaşır
problemin fiziki mahiyyəti ilə bağlı şərtlər. Məhdudiyyətlər o qədər güclü ola bilər ki, problemin heç biri olmayacaq
Şəkil.6.3.Məqsəd funksiyasının işarəsinin əksinə dəyişdirilməsi
maksimum tapşırıq minimum vəzifəyə çevrilir.
qənaətbəxş həll. Məhdudiyyətlər iki qrupa bölünür: məhdudiyyətlər - bərabərlik və məhdudiyyətlər - bərabərsizlik.
Məhdudiyyətlər - Bərabərliklər
Məhdudiyyətlər - bərabərliklər - həll yolu taparkən nəzərə alınmalı olan dizayn parametrləri arasındakı asılılıqlardır. Onlar təbiət qanunlarını, iqtisadiyyatı, qanunları, üstünlük təşkil edən zövqləri və mövcudluğu əks etdirir zəruri materiallar. Məhdudiyyətlərin sayı - bərabərliklər istənilən ola bilər. Onlar oxşayır
C 1 (x 1 , x 2 ,...,x n)=0,
C 2 (x 1, x 2,...,x n)=0,
..................
C j (x 1 , x 2 ,...,x n)=0.
Əgər bu əlaqələrdən hər hansı biri dizayn parametrlərindən birinə münasibətdə həll edilə bilərsə, bu, bu parametrin optimallaşdırma prosesindən xaric edilməsinə imkan verir. Bu, dizayn məkanının ölçülərinin sayını azaldır və problemin həllini asanlaşdırır.
Məhdudiyyətlər - bərabərsizliklər
Bu, bərabərsizliklərlə ifadə olunan xüsusi bir məhdudiyyət növüdür. Ümumiyyətlə, onlardan istədiyiniz qədər ola bilər və hamısının forması var
z 1 r 1 (x 1 , x 2 ,...,x n) Z 1
z 2 r 2 (x 1 , x 2 ,...,x n) Z 2
.......................
z k r k (x 1 , x 2 ,...,x n) Z k
Qeyd etmək lazımdır ki, çox vaxt məhdudiyyətlər səbəbindən məqsəd funksiyasının optimal dəyəri onun səthinin sıfır gradientə malik olduğu yerdə deyil. Çox vaxt ən yaxşı həll dizayn məkanının sərhədlərindən birinə uyğun gəlir.
Yerli optimal
Bu, dizayn məkanında məqsəd funksiyasının olduğu nöqtənin adıdır ən yüksək dəyər bilavasitə yaxınlığındakı bütün digər nöqtələrdəki dəyərləri ilə müqayisədə.
Şəkil 6.4. İxtiyari məqsəd funksiyası bir neçə ola bilər
yerli optimal.
Şəkildə. Şəkil 6.4-də iki yerli optima malik olan birölçülü məqsəd funksiyası göstərilir. Çox vaxt dizayn məkanı çoxlu yerli optimalları ehtiva edir və problemin optimal həlli üçün birincisini səhv salmamağa diqqət yetirilməlidir.
Qlobal optimal
Qlobal optimal bütün dizayn sahəsi üçün optimal həlldir. Bu, yerli optima uyğun gələn bütün digər həllərdən daha yaxşıdır və dizaynerin axtardığı budur. Mümkündür ki, bir neçə bərabər qlobal optima yerləşir müxtəlif hissələr dizayn sahəsi. Optimallaşdırma probleminin necə qoyulması ən yaxşı nümunə ilə göstərilmişdir.
Misal 6.1
Tutaq ki, qablaşdırılmamış lifin daşınması üçün nəzərdə tutulmuş həcmi 1 m olan düzbucaqlı bir qab dizayn etməlisiniz. Bu cür qabların istehsalına mümkün qədər az material sərf edilməsi arzu edilir (sabit divar qalınlığını nəzərə alsaq, bu, səth sahəsinin minimal olması deməkdir), çünki daha ucuz olacaqdır. Konteynerin yük maşını ilə rahat şəkildə götürülməsi üçün onun eni ən azı 1,5 m olmalıdır.
Bu problemi optimallaşdırma alqoritmini tətbiq etmək üçün əlverişli formada tərtib edək.
Dizayn parametrləri: x 1, x 2, x 3.
Məqsəd funksiyası (kiçildilməli olan) konteynerin yan səthinin sahəsidir:
A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.
Məhdudiyyət - bərabərlik:
Həcmi = x 1 x 2 x 3 = 1m3.
Məhdudiyyət - bərabərsizlik:
Xətti proqramlaşdırma problemləri
Xətti proqramlaşdırma (LP) riyazi proqramlaşdırmanın qollarından biridir - ekstremal (optimallaşdırma) məsələləri öyrənən və onların həlli üsullarını işləyib hazırlayan bir fəndir.
Optimallaşdırma problemi məqsəd funksiyasının optimal (yəni maksimum və ya minimum) dəyərini tapmaqdan ibarət riyazi problemdir və dəyişənlərin dəyərləri müəyyən məqbul dəyərlər diapazonuna (APV) aid olmalıdır.
Ümumiyyətlə, riyazi proqramlaşdırmanın ekstremal probleminin tərtibi ən böyük və ya ən aşağı dəyər funksiyası çağırılır hədəf funksiyası, şərtlərdə (məhdudiyyətlər) burada və funksiyalar verilir və sabit qiymətlər verilir. Bu halda, bərabərlik və bərabərsizliklər şəklində məhdudiyyətlər yol verilən həllərin (ADS) çoxluğunu (sahəsini) müəyyənləşdirir və adlanır. dizayn parametrləri.
Funksiyaların növündən asılı olaraq riyazi proqramlaşdırma məsələləri bir sıra siniflərə (xətti, qeyri-xətti, qabarıq, tam, stoxastik, dinamik proqramlaşdırma və s.) bölünür.
IN ümumi görünüş LP problemi aşağıdakı formaya malikdir:
, (5.1)
, , (5.2)
, 
, (5.3)
burada , , sabit qiymətlər verilir.
(5.1) funksiyası məqsəd funksiyası adlanır; sistemlər (5.2), (5.3) – məhdudiyyətlər sistemi; şərt (5.4) – layihə parametrlərinin mənfi olmama şərti.
(5.2), (5.3) və (5.4) məhdudiyyətlərini təmin edən dizayn parametrləri toplusu adlanır. məqbul həll və ya plan.
Optimal həll və ya optimal plan LP problemi məqsəd funksiyasının (5.1) optimal (maksimum və ya minimum) qiymətini qəbul etdiyi məqbul həll adlanır.
Standart tapşırıq LP (5.2) və (5.4) şərtində məqsəd funksiyasının (5.1) maksimum (minimum) qiymətinin tapılması məsələsidir, burada , , yəni. olanlar. yalnız bərabərsizliklər şəklində məhdudiyyətlər (5.2) və bütün dizayn parametrləri qeyri-mənfilik şərtini ödəyir və bərabərlik şəklində şərtlər yoxdur:
,
, , (5.5)
.
Kanonik (əsas) vəzifə LP (5.3) və (5.4) şərtində məqsəd funksiyasının (5.1) maksimum (minimum) qiymətinin tapılması məsələsidir, burada , , yəni. olanlar. yalnız bərabərliklər şəklində məhdudiyyətlər (5.3) və bütün dizayn parametrləri qeyri-mənfilik şərtini ödəyir və bərabərsizliklər şəklində heç bir şərt yoxdur:
,
.
Kanonik LP problemi matris və vektor formasında da yazıla bilər.
Kanonik LP probleminin matris forması aşağıdakı formaya malikdir:
Kanonik LP probleminin vektor forması.
Gəlin müstəvidə xətti bərabərsizliklər sisteminin mümkün həllər toplusunu quraq və məqsəd funksiyasının minimum qiymətini həndəsi şəkildə tapaq.
X 1 x 2 koordinat sistemində düz xətlər qururuq
Sistem tərəfindən müəyyən edilmiş yarım müstəviləri tapırıq. Sistemin bərabərsizlikləri müvafiq yarımmüstəvidə istənilən nöqtə üçün ödənildiyi üçün onları hər hansı bir nöqtə üçün yoxlamaq kifayətdir. (0;0) nöqtəsindən istifadə edirik. Onun koordinatlarını sistemin birinci bərabərsizliyinə əvəz edək. Çünki , onda bərabərsizlik (0;0) nöqtəsini ehtiva etməyən yarımmüstəvi müəyyən edir. Qalan yarım təyyarələri də eyni şəkildə müəyyənləşdiririk. Yaranan yarım təyyarələrin ümumi hissəsi kimi mümkün həllər dəstini tapırıq - bu kölgəli sahədir.
Bir vektor və ona perpendikulyar sıfır səviyyəli xətt qururuq.
Düz xətti (5) vektor istiqamətində hərəkət etdikdə, bölgənin maksimum nöqtəsinin düz xəttin (3) və düz xəttin (2) kəsişməsinin A nöqtəsində olacağını görürük. Tənliklər sisteminin həllini tapırıq:
Bu o deməkdir ki, biz (13;11) nöqtəni aldıq və.
Düz xətti (5) vektor istiqamətində hərəkət etdikdə, bölgənin minimum nöqtəsinin (1) düz xəttin (4) kəsişməsinin B nöqtəsində olacağını görürük. Tənliklər sisteminin həllini tapırıq:
Bu o deməkdir ki, biz (6;6) nöqtəsini aldıq və.
2. Mebel şirkəti kombinə edilmiş şkaflar və kompüter masaları istehsal edir. Onların istehsalı xammalın (yüksək keyfiyyətli lövhələr, fitinqlər) mövcudluğu və onları emal edən maşınların işləmə müddəti ilə məhdudlaşır. Hər bir kabinet üçün 5 m2 lövhələr, bir masa üçün - 2 m2 lazımdır. Fitinqlər bir şkaf üçün 10 dollar, bir masa üçün isə 8 dollardır. Şirkət öz təchizatçılarından ayda 600 m2-ə qədər lövhə və 2000 ABŞ dolları dəyərində aksessuarlar ala bilər. Hər bir kabinetə 7 saat maşın işləməsi, masaya isə 3 saat lazımdır. Ayda cəmi 840 maşın iş saatı istifadə edilə bilər.
Bir kabinet 100 dollar qazanc gətirirsə və hər bir masa 50 dollar gəlir gətirirsə, mənfəəti artırmaq üçün şirkət ayda neçə kombinasiya şkafı və kompüter masası istehsal etməlidir?
- 1. Yaratmaq riyazi model problemi və onu simpleks üsulu ilə həll edin.
- 2. İkili məsələnin riyazi modelini yaradın, orijinalın həllinə əsasən onun həllini yazın.
- 3. İstifadə olunan resursların qıtlıq dərəcəsini müəyyən edin və optimal planın rentabelliyini əsaslandırın.
- 4. Hər bir resurs növünün istifadəsindən asılı olaraq istehsal məhsulunun daha da artırılması imkanlarını araşdırın.
- 5. Əgər bir rəfin istehsalı 1 m 2 lövhə və ləvazimatların dəyəri 5 ABŞ dolları dəyərindədirsə və 0,25 saat maşın istismarına və satışdan əldə edilən gəlirə sərf etmək lazımdırsa, yeni növ məhsulun - kitab rəflərinin tətbiqinin məqsədəuyğunluğunu qiymətləndirin. bir rəf 20 dollardır.
- 1. Bu məsələ üçün riyazi model quraq:
X 1 ilə şkafların istehsalının həcmini, x 2 ilə isə masaların istehsalının həcmini işarə edək. Məhdudiyyətlər sistemi və məqsəd funksiyası yaradaq:
Problemi simpleks üsulu ilə həll edirik. Bunu kanonik formada yazaq:
Tapşırıq məlumatlarını cədvəl şəklində yazaq:
Cədvəl 1
Çünki İndi bütün deltalar sıfırdan böyükdür, onda f məqsəd funksiyasının dəyərinin daha da artırılması mümkün deyil və biz optimal plan əldə etmişik.
Giriş
Bəşəriyyətin inkişafının hazırkı mərhələsi onunla seçilir ki, enerji əsri informatika əsri ilə əvəz olunur. İnsan fəaliyyətinin bütün sahələrinə yeni texnologiyaların intensiv tətbiqi müşahidə olunur. İnformasiya cəmiyyətinə keçidin real problemi var ki, bunun üçün təhsilin inkişafı prioritet məsələyə çevrilməlidir. Cəmiyyətdə biliyin strukturu da dəyişir. üçün getdikcə əhəmiyyətlidir praktik həyat fərdin yaradıcı inkişafına töhfə verən fundamental biliklərə yiyələnmək. Qazanılan biliklərin konstruktivliyi və onu məqsədə uyğun şəkildə qurmaq bacarığı da mühüm əhəmiyyət kəsb edir. Bilik əsasında yeniləri formalaşır informasiya resursları cəmiyyət. Yeni biliklərin formalaşması və mənimsənilməsi sistemli yanaşmanın ciddi metodologiyasına əsaslanmalıdır ki, onun daxilində model yanaşması xüsusi yer tutur. Model yanaşmasının imkanları həm istifadə olunan formal modellər baxımından, həm də modelləşdirmə metodlarının həyata keçirilməsi üsulları baxımından son dərəcə müxtəlifdir. Fiziki modelləşdirmə kifayət qədər sadə sistemlər üçün etibarlı nəticələr əldə etməyə imkan verir.
Hal-hazırda, modelləşdirmə metodlarının bu və ya digər dərəcədə istifadə olunmayacağı insan fəaliyyəti sahəsini adlandırmaq mümkün deyil. Bu xüsusilə idarəetmə sahəsində doğrudur müxtəlif sistemlər, burada əsas proseslər alınan məlumat əsasında qərarların qəbul edilməsidir.
1. Problemin ifadəsi
minimum məqsəd funksiyası
Tapşırığın 16-cı variantına uyğun olaraq həll poliqonu ilə müəyyən edilmiş məhdudiyyətlər sistemi üçün məqsəd funksiyasının minimumunun tapılması məsələsini həll edin. Həlli çoxbucaqlı Şəkil 1-də göstərilmişdir:
Şəkil 1 - Problemin həlli çoxbucaqlı
Məhdudiyyətlər sistemi və problemin məqsəd funksiyası aşağıda təqdim olunur:
Problemi aşağıdakı üsullardan istifadə edərək həll etmək lazımdır:
LP məsələlərinin həlli üçün qrafik üsul;
LP məsələlərinin həlli üçün cəbri üsul;
LP məsələlərinin həlli üçün Simpleks metodu;
LP problemlərinin məqbul həllini tapmaq üsulu;
İkili LP probleminin həlli;
Tam LP məsələlərinin həlli üçün budaq və bağlı metod;
Tam ədədli LP məsələlərinin həlli üçün Gomori üsulu;
Boolean LP problemlərinin həlli üçün Balazs metodu.
Həll nəticələrini müqayisə edin müxtəlif üsullar işdən müvafiq nəticələr çıxarmaq.
2. Xətti proqramlaşdırma məsələsinin qrafik həlli
Xətti proqramlaşdırma məsələlərinin həlli üçün qrafik üsul naməlumların sayı üçdən çox olmadığı hallarda istifadə olunur. Məhlulların xassələrinin keyfiyyətcə tədqiqi üçün əlverişlidir və digər üsullarla (cəbri, budaqlı və hədsiz və s.) birlikdə istifadə olunur. Metodun ideyası xətti bərabərsizliklər sisteminin qrafik həllinə əsaslanır.
düyü. 2 LP məsələsinin qrafik həlli
Minimum nöqtə
A1 və A2 iki nöqtəsindən keçən xəttin tənliyi:
AB: (0;1); (3;3)
VS: (3;3); (4;1)
CD: (4;1); (3;0)
EA: (1;0); (0;1)
CF: (0;1); (5;2)
məhdudiyyətlərlə:
Cəbri simpleks üsulu ilə xətti proqramlaşdırma məsələsinin həlli
Məsələnin həlli üçün cəbri metodun tətbiqi LP məsələsinin təsvirinin ümumiləşdirilməsini tələb edir. Bərabərsizliklər şəklində göstərilən ilkin məhdudiyyətlər sistemi, məhdudiyyətlər bərabərlik şəklində göstərildikdə standart qeydə çevrilir. Məhdudiyyət sisteminin transformasiyası standart görünüş aşağıdakı addımları əhatə edir:
Bərabərsizlikləri elə çevirin ki, solda dəyişənlər və sərbəst şərtlər, sağda isə 0 olsun, yəni. üçün sol tərəf sıfırdan böyük və ya bərabər idi;
Sayı məhdudiyyətlər sistemindəki bərabərsizliklərin sayına bərabər olan əlavə dəyişənlər təqdim etmək;
Əlavə edilmiş dəyişənlərin qeyri-mənfiliyinə əlavə məhdudiyyətlər tətbiq etməklə bərabərsizlik işarələrini ciddi bərabərlik işarələri ilə əvəz edin.
Cəbri metoddan istifadə edərək LP məsələsini həll edərkən bir şərt əlavə olunur: məqsəd funksiyası minimuma meyl etməlidir. Əgər bu şərt qane olunmursa, məqsəd funksiyasını müvafiq olaraq çevirmək (-1-ə vurmaq) və minimumlaşdırma məsələsini həll etmək lazımdır. Həlli tapıldıqdan sonra dəyişənlərin dəyərlərini orijinal funksiyaya əvəz edin və onun dəyərini hesablayın.
Cəbri metoddan istifadə edərək problemin həlli bütün əsas dəyişənlərin qiymətləri mənfi olmayan və məqsəd funksiyası tənliyində sərbəst dəyişənlərin əmsalları da mənfi olduqda optimal hesab olunur. Bu şərtlər yerinə yetirilmədikdə, yuxarıda göstərilən məhdudiyyətlərin yerinə yetirilməsinə nail olmaq üçün bəzi dəyişənləri digərləri ilə ifadə edən (sərbəst və əsas dəyişənlərin dəyişdirilməsi) bərabərsizliklər sistemini çevirmək lazımdır. Bütün sərbəst dəyişənlərin dəyəri sıfıra bərabər hesab olunur.
Xətti proqramlaşdırma məsələlərinin həlli üçün cəbri üsul ən çox istifadə olunanlardan biridir təsirli üsullar kiçik miqyaslı məsələləri əl ilə həll edərkən, çünki çoxlu sayda arifmetik hesablamalar tələb etmir. Bu metodun maşın tətbiqi, məsələn, simpleks metodundan daha mürəkkəbdir, çünki Cəbri metoddan istifadə edərək həll alqoritmi müəyyən dərəcədə evristikdir və həllin effektivliyi əsasən şəxsi təcrübədən asılıdır.
Pulsuz dəyişənlər
St zolaqlı - əlavə dəsti
Mənfi olmayan şərtlər yerinə yetirilir, buna görə də optimal həll yolu tapıldı.
3. Simpleks cədvəlindən istifadə etməklə xətti proqramlaşdırma məsələsinin həlli
Həlli: Simpleks cədvəlindən istifadə edərək problemi həll etmək üçün standart formaya gətirək.
Sistemin bütün tənliklərini aşağıdakı formaya endirək:
Simpleks cədvəli qururuq:
Cədvəlin hər bir xanasının yuxarı küncündə tənliklər sistemindən əmsalları daxil edirik;
F sətirində maksimum müsbət elementi seçirik, istisna olmaqla, bu ümumi sütun olacaq;
Ümumi elementi tapmaq üçün bütün müsbət olanlar üçün əlaqə qururuq. 3/3; 9/1;- x3 sətirində minimum nisbət. Buna görə də - ümumi sətir və =3 - ümumi element.
=1/=1/3 tapırıq. Biz onu ümumi elementin yerləşdiyi hüceyrənin aşağı küncünə gətiririk;
Ümumi xəttin bütün boş aşağı künclərində xananın yuxarı küncündəki dəyərin hasilini aşağıdakılarla daxil edirik;
Ümumi xəttin yuxarı künclərini seçin;
Ümumi sütunun bütün aşağı künclərində yuxarı küncdəki dəyərin məhsulunu - ilə daxil edirik və nəticədə alınan dəyərləri seçirik;
Cədvəlin qalan xanaları müvafiq seçilmiş elementlərin məhsulu kimi doldurulur;
Sonra ümumi sütun və sətir elementlərinin hüceyrələrinin təyinatlarının dəyişdirildiyi yeni bir cədvəl qururuq (x2 və x3);
Əvvəllər aşağı küncdə olan dəyərlər əvvəlki ümumi sətir və sütunun yuxarı küncünə yazılır;
Əvvəlki cədvəldə bu xanaların yuxarı və aşağı künclərinin qiymətlərinin cəmi qalan xanaların yuxarı küncündə yazılır.
4. Xətti proqramlaşdırma məsələsinin məqbul həllini tapmaq yolu ilə həlli
Xətti cəbri tənliklər sistemi verilsin:
Hər şeyin olduğunu güman edə bilərik, əks halda müvafiq tənliyi -1-ə vururuq.
Köməkçi dəyişənləri təqdim edirik:
Biz həmçinin köməkçi funksiyanı təqdim edirik
Biz məhdudiyyətlər (2) və şərtlər altında sistemi minimuma endirəcəyik.
İCAZƏ VERİLƏN HƏLLİN TAPILMASI QAYDASI: Sistem (1) üçün məqbul həll tapmaq üçün (2) məhdudiyyətlər altında (3) formanı minimuma endiririk, xj-i sərbəst naməlumlar kimi götürürük və xj-i əsas götürürük.
Simpleks metodundan istifadə edərək problemi həll edərkən iki hal yarana bilər:
min f=0, onda bütün i sıfıra bərabər olmalıdır. Və nəticədə xj qiymətləri sistem (1) üçün məqbul bir həll təşkil edəcəkdir.
min f>0, yəni. orijinal sistemin mümkün həlli yoxdur.
Mənbə sistemi:
Əvvəlki mövzudan məsələnin şərtindən istifadə olunur.
Əlavə dəyişənləri təqdim edək:
İlkin məsələnin məqbul həlli tapıldı: x1 = 3, x2 = 3, F = -12. Əldə edilmiş mümkün həllə əsaslanaraq, biz simpleks üsulundan istifadə edərək orijinal məsələnin optimal həllini tapacağıq. Bunun üçün yuxarıda əldə edilmiş cədvəldən köməkçi məsələnin hədəf funksiyası olan cərgə və cərgəni çıxararaq yeni simpleks cədvəli quracağıq:
Qurulmuş simpleks cədvəlini təhlil etdikdə görürük ki, ilkin məsələnin optimal həlli artıq tapılıb (məqsəd funksiyasına uyğun gələn cərgədəki elementlər mənfidir). Beləliklə, köməkçi məsələnin həlli zamanı tapılan mümkün həll orijinal problemin optimal həlli ilə üst-üstə düşür:
6. İkili xətti proqramlaşdırma məsələsi
Məhdudiyyətlərin orijinal sistemi və problemin məqsəd funksiyası aşağıdakı şəkildə göstərilmişdir.
məhdudiyyətlərlə:
Həll yolu: Məhdudiyyətlər sistemini standart formaya gətirək:
Bununla ikili problem aşağıdakı formada olacaq:
İkili məsələnin həlli sadə simpleks üsulu ilə yerinə yetiriləcəkdir.
Məqsəd funksiyasını elə çevirək ki, minimumlaşdırma məsələsi həll olunsun və məhdudiyyətlər sistemini simpleks üsulu ilə həll etmək üçün standart formada yazaq.
y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)
y7 = 5 - (-3y1 - y2 + y3 + y4)
Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??dəq
İkili LP problemini həll etmək üçün ilkin simpleks cədvəlini quraq.
Simpleks metodunun ikinci mərhələsi
Belə ki, simpleks metodunun üçüncü pilləsində aşağıdakı nəticələrlə minimumlaşdırma məsələsinin optimal həlli tapılmışdır: y2 = -7 /8, y1 = -11/8, Ф = 12. Qiymətini tapmaq üçün. ikili məsələnin məqsəd funksiyası üçün əsas və sərbəst dəyişənlərin tapılmış qiymətlərini maksimumlaşdırma funksiyasına əvəz edirik:
Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
Birbaşa və ikili məsələlərin məqsəd funksiyasının qiyməti üst-üstə düşdüyündən birbaşa məsələnin həlli tapılır və 12-yə bərabər olur.
Fmin = Фmax = -12
7. Budaq-bağlama metodundan istifadə etməklə tam ədədli xətti proqramlaşdırma məsələsinin həlli
İlkin məsələni elə çevirək ki, şərti üsullardan istifadə etməklə həll edildikdə tam ədəd şərti ödənilməsin.
Tam ədədli proqramlaşdırma məsələsinin həllərinin ilkin poliqonu.
Məhlulların çevrilmiş çoxbucaqlıları üçün qururuq yeni sistem məhdudiyyətlər.
Məhdudiyyətlər sistemini cəbri üsulla həll ediləcək bərabərliklər şəklində yazaq.
Həlli nəticəsində problemin optimal planı tapıldı: x1 = 9/4, x2 = 5/2, F = -41/4. Bu həll məsələdə qoyulmuş tam ədəd şərtinə cavab vermir. Orijinal həll çoxbucaqlısını ondan 3-cü sahəni çıxmaqla iki sahəyə ayıraq Dəyişdirilmiş problem həlli poliqonu Həll çoxbucaqlısının yaranan sahələri üçün yeni məhdudiyyətlər sistemləri yaradaq. Sol sahə dördbucaqlıdır (trapesiya). Həll poliqonunun sol bölgəsi üçün məhdudiyyətlər sistemi aşağıda təqdim olunur. Sol sahə üçün məhdudiyyət sistemi Sağ sahə C nöqtəsini təmsil edir. Doğru qərar bölgəsi üçün məhdudiyyətlər sistemi aşağıda təqdim olunur. Yeni məhdudiyyət sistemləri bir-birindən asılı olmayaraq həll edilməli olan iki köməkçi problemi təmsil edir. Həll çoxbucağının sol bölgəsi üçün tam ədəd proqramlaşdırma məsələsini həll edək. Həlli nəticəsində məsələnin optimal planı tapıldı: x1 = 3, x2 = 3, F = -12. Bu plan problemdəki dəyişənlərin tam ədəd olması şərtini ödəyir və orijinal tam ədədli xətti proqramlaşdırma məsələsi üçün optimal istinad planı kimi qəbul edilə bilər. Düzgün həll bölgəsi üçün həll etməyin mənası yoxdur. Aşağıdakı şəkildə ağac şəklində tam ədəd xətti proqramlaşdırma məsələsinin həllinin gedişatı göstərilir. Qomori metodundan istifadə etməklə tam ədədli xətti proqramlaşdırma məsələsinin həllinin gedişatı. Bir çox praktik tətbiqlərdə xətti bərabərsizliklər sisteminin və xətti formanın verildiyi tam ədədli proqramlaşdırma problemi böyük maraq doğurur. F məqsəd funksiyasını minimuma endirən (1) sisteminin tam həllini tapmaq tələb olunur və bütün əmsallar tam ədədlərdir. Tam ədədli proqramlaşdırma məsələsinin həlli üsullarından biri Qomori tərəfindən təklif edilmişdir. Metodun ideyası davamlı xətti proqramlaşdırma metodlarından, xüsusən də simplex metodundan istifadə etməkdir. 1) Simpleks metodundan istifadə etməklə (1), (2) məsələnin həlli müəyyən edilir, bunun üçün tam ədəd həlli tələbi çıxarılır; əgər həll tam ədəd olarsa, onda tam ədədli məsələnin istənilən həlli də tapılacaq; 2) Əks halda, əgər hansısa koordinat tam ədəd deyilsə, problemin nəticədə həlli tam ədəd həllinin mövcudluğu üçün yoxlanılır (icazə verilən çoxbucaqlıda tam ədədlərin olması): kəsrli sərbəst termini olan hər hansı bir cərgədə bütün digər əmsallar tam ədədlər olarsa, onda icazə verilən çoxbucaqlıda tam ədədlər və ya nöqtələr yoxdur və tam ədədli proqramlaşdırma məsələsinin həlli yoxdur; Əks halda, tam ədədli proqramlaşdırma məsələsinin həlli üçün perspektivsiz olan icazə verilən çoxbucaqlının bir hissəsini kəsən əlavə xətti məhdudiyyət tətbiq edilir; 3) Əlavə xətti məhdudiyyət qurmaq üçün kəsr sərbəst termini olan l-ci cərgəni seçin və əlavə məhdudiyyəti yazın. burada və əmsalların müvafiq olaraq kəsr hissələridir və sərbəstdir üzv. Məhdudiyyətə (3) köməkçi dəyişən daxil edək: Məhdudiyyətə (4) daxil olan əmsalları təyin edək: burada və müvafiq olaraq və üçün aşağıdan ən yaxın tam ədədlərdir. Gomori sübut etdi ki, sonlu sayda oxşar addımlar həlli tam və deməli, arzu olunan olan xətti proqramlaşdırma probleminə gətirib çıxarır. Həlli: Gəlin xətti məhdudiyyətlər sistemini və məqsəd funksiyasını kanonik formaya gətirək: Tam ədəd şərtini müvəqqəti olaraq ləğv edərək xətti məhdudiyyətlər sisteminin optimal həllini müəyyən edək. Bunun üçün simplex metodundan istifadə edirik. Aşağıda, ardıcıl olaraq cədvəllərdə problemin orijinal həlli təqdim olunur və problemin optimal həllini əldə etmək üçün orijinal cədvəlin çevrilmələri verilir: Balazs metodundan istifadə etməklə Boolean LP məsələlərinin həlli. Aşağıdakı qaydaları nəzərə alaraq, Boolean dəyişənləri ilə tam ədəd xətti proqramlaşdırma məsələsi üçün öz versiyanızı yaradın: problem ən azı 5 dəyişəndən, ən azı 4 məhdudiyyətdən istifadə edir, məhdudiyyətlərin əmsalları və məqsəd funksiyası ixtiyari olaraq seçilir, lakin belə məhdudiyyətlər sisteminin uyğun olması üsulu. Vəzifə Balazs alqoritmindən istifadə edərək LCLP-ni Boolean dəyişənləri ilə həll etmək və hərtərəfli axtarış metodundan istifadə edərək problemin həlli ilə əlaqədar hesablamaların mürəkkəbliyinin azaldılmasını müəyyən etməkdir. Məhdudiyyətlərin icrası F dəyəri Filtrləmə məhdudiyyəti: Hesablama səylərinin azaldılmasının təyini Tam axtarış metodundan istifadə etməklə problemin həlli 6*25=192 hesablanmış ifadədir. Məsələnin Balazs üsulu ilə həlli 3*6+(25-3)=47 hesablanmış ifadədir. Tam axtarış metodundan istifadə edərək problemin həlli ilə əlaqədar hesablamaların mürəkkəbliyində ümumi azalma: Nəticə Yeni informasiya texnologiyalarını tətbiq edən informasiya sistemlərinin layihələndirilməsi prosesi daim təkmilləşdirilir. Sistem mühəndislərinin diqqəti getdikcə mürəkkəb sistemlərə yönəlib, fiziki modellərdən istifadəni çətinləşdirir və riyazi modellərin və sistemlərin maşın simulyasiyasının əhəmiyyətini artırır. Maşın simulyasiyası mürəkkəb sistemlərin öyrənilməsi və layihələndirilməsi üçün effektiv vasitəyə çevrilmişdir. Riyazi modellərin aktuallığı onların çevikliyi, real proseslərə adekvatlığı və müasir fərdi kompüterlər əsasında həyata keçirilməsinin aşağı qiyməti sayəsində davamlı olaraq artır. İstifadəçiyə, yəni kompüter texnologiyasından istifadə edərək sistemlərin modelləşdirilməsi üzrə mütəxəssisə getdikcə daha çox imkanlar verilir. Modelləşdirmədən istifadə xüsusilə avtomatlaşdırılmış sistemlərin layihələndirilməsinin ilkin mərhələlərində, səhv qərarların dəyərinin ən əhəmiyyətli olduğu hallarda təsirli olur. Müasir hesablama vasitələri sistemlərin öyrənilməsində istifadə olunan modellərin mürəkkəbliyini əhəmiyyətli dərəcədə artırmağa imkan verdi, real sistemlərdə baş verən amillərin bütün müxtəlifliyini nəzərə alan birləşmiş, analitik və simulyasiya modellərini qurmaq mümkün oldu, yəni. , öyrənilən hadisələrə daha adekvat olan modellərdən istifadə. Ədəbiyyat: 1. Lyaşchenko I.N. Xətti və qeyri-xətti proqramlaşdırma / İ.N.Lyaşenko, E.A.Karaqodova, N.V.Çernikova, N.Z.Şor. - K.: “Ali məktəb”, 1975, 372 s. 2. Əyani və qiyabi təhsil formalarının “Kompüter sistemləri və şəbəkələri” ixtisasının tələbələri üçün “Tətbiqi riyaziyyat” fənni üzrə kurs layihəsini tamamlamaq üçün təlimatlar / Tərtib edənlər: I.A. Balakireva, A.V. Skatkov - Sevastopol: SevNTU Nəşriyyat , 2003. - 15 s. 3. “Tətbiqi riyaziyyat” fənninin öyrənilməsi üçün təlimatlar, “Qlobal axtarış və birölçülü minimuma endirmə üsulları” bölməsi / Komp. A.V.Skatkov, I.A.Balakireva, L.A.Litvinova - Sevastopol: SevGTU nəşriyyatı, 2000. - 31 s. 4. Əyani və qiyabi təhsil üçün “Kompüter sistemləri və şəbəkələri” ixtisasının tələbələri üçün “Tətbiqi riyaziyyat” fənninin tədrisi üçün təlimatlar / Tərtib edənlər: İ.A.Balakireva, A.V.Skatkov - Sevastopol. : SevNTU nəşriyyatı, 2000. - 13 s. 5. Akuliç İ.L. Nümunələr və məsələlərdə riyazi proqramlaşdırma: 6. Dərslik iqtisadiyyat tələbələri üçün müavinət. mütəxəssis. universitetlər.-M.: Ali. məktəb, 1986.- 319 s., xəstə. 7. Andronov S.A. Optimal dizayn üsulları: Mühazirələrin mətni / SPbSUAP. Sankt-Peterburq, 2001. 169 s.: ill. Simpleks üsulu ilə xətti proqramlaşdırma məsələlərinin həlli alqoritmi. Xətti proqramlaşdırma məsələsinin riyazi modelinin qurulması. Excel-də xətti proqramlaşdırma məsələsinin həlli. Mənfəət və optimal istehsal planının tapılması. kurs işi, 21/03/2012 əlavə edildi Qrafik problemin həlli. Riyazi modelin tərtib edilməsi. Məqsəd funksiyasının maksimum qiymətinin müəyyən edilməsi. Kanonik xətti proqramlaşdırma məsələsinin süni əsası ilə simpleks üsulu ilə həlli. Həllin optimallığının yoxlanılması. test, 04/05/2016 əlavə edildi Xətti proqramlaşdırmanın nəzəri əsasları. Xətti proqramlaşdırma məsələləri, həlli üsulları. Optimal həllin təhlili. Tək indeksli xətti proqramlaşdırma məsələsinin həlli. Problemin ifadəsi və məlumatların daxil edilməsi. Modelin qurulması və həll mərhələləri. kurs işi, 12/09/2008 əlavə edildi Riyazi modelin qurulması. Simpleks cədvəlindən istifadə etməklə, simpleks üsulu ilə birbaşa xətti proqramlaşdırma məsələsinin həlli metodunun seçilməsi, əsaslandırılması və təsviri. İkili məsələnin formalaşdırılması və həlli. Modelin həssaslıq təhlili. kurs işi, 31/10/2014 əlavə edildi Müəssisə üçün maksimum mənfəət əldə etmək üçün riyazi modelin qurulması, məsələnin qrafik həlli. SOLVER əlavəsindən istifadə edərək problemin həlli. Resurs ehtiyatlarında dəyişikliklərin təhlili. Məqsəd funksiyasının əmsallarının dəyişdirilməsi hədlərinin müəyyən edilməsi. kurs işi, 12/17/2014 əlavə edildi Riyazi proqramlaşdırma. Xətti proqramlaşdırma. Xətti proqramlaşdırma problemləri. Xətti proqramlaşdırma məsələlərinin həlli üçün qrafik üsul. Xətti proqramlaşdırma probleminin iqtisadi formalaşdırılması. Riyazi modelin qurulması. kurs işi, 10/13/2008 əlavə edildi Xətti proqramlaşdırma məsələsinin qrafik üsulla həlli, MS Excel proqramında yoxlanılması. Proqramda məsələnin həllinin daxili strukturunun təhlili. İstehsal planının optimallaşdırılması. Simpleks metodundan istifadə etməklə məsələnin həlli. Çoxkanallı növbə sistemi. test, 05/02/2012 əlavə edildi Simpleks metodundan istifadə etməklə xətti proqramlaşdırma məsələsinin həlli: məsələnin ifadəsi, iqtisadi-riyazi modelin qurulması. Potensial metoddan istifadə etməklə nəqliyyat probleminin həlli: ilkin istinad planının qurulması, onun optimal qiymətinin müəyyən edilməsi. test, 04/11/2012 əlavə edildi Qeyri-xətti proqramlaşdırma probleminin ifadəsi. Stasionar nöqtələrin və onların növünün təyini. Səviyyə xətlərinin qurulması, məqsəd funksiyasının üçölçülü qrafiki və məhdudiyyətlər. Problemin qrafik və analitik həlli. İstifadəçi təlimatı və alqoritm diaqramı. kurs işi, 12/17/2012 əlavə edildi Xətti proqramlaşdırma məsələsinin həllinin təhlili. Simpleks cədvəllərindən istifadə edərək Simpleks metodu. Kompüterdə LP problemlərinin modelləşdirilməsi və həlli. Problemin optimal həllinin iqtisadi şərhi. Nəqliyyat probleminin riyazi formalaşdırılması. Üçüncü sıranı 5-ə bərabər olan əsas elementə bölün, yeni cədvəlin üçüncü sırasını alırıq. Əsas sütunlar vahid sütunlarına uyğundur. Digər cədvəl dəyərlərinin hesablanması: “BP – Əsas Plan”: ; "x1": "x5": İndeks sətirinin dəyərləri mənfi deyil, ona görə də optimal həlli əldə edirik: , ; Cavab: istehsal olunmuş məhsulların satışından maksimum 160/3 ədədə bərabər mənfəət yalnız 80/9 ədəd həcmində ikinci növ məhsul istehsalı ilə təmin edilir. Qeyri-xətti proqramlaşdırma məsələsi verilmişdir. Qrafik-analitik üsulla məqsəd funksiyasının maksimum və minimumunu tapın. Laqranj funksiyasını tərtib edin və ekstremum nöqtələrində minimum (maksimum) üçün kifayət qədər şərtlərin ödənildiyini göstərin. Çünki şifrənin sonuncu rəqəmi 8-dir, onda A=2; B=5. Çünki şifrənin sondan əvvəlki rəqəmi 1-dir, onda siz 1 nömrəli tapşırığı seçməlisiniz. Həll: 1) Bərabərsizliklər sistemi ilə müəyyən edilmiş sahəni çəkək. Bu sahə təpə koordinatları olan ABC üçbucağıdır: A(0; 2); B(4; 6) və C(16/3; 14/3). Məqsəd funksiyasının səviyyələri mərkəzi (2; 5) nöqtəsində olan dairələrdir. Radiusların kvadratları məqsəd funksiyasının dəyərləri olacaqdır. Sonra rəqəm göstərir ki, məqsəd funksiyasının minimum dəyəri H nöqtəsində, maksimuma - ya A nöqtəsində, ya da C nöqtəsində əldə edilir. Məqsəd funksiyasının A nöqtəsindəki qiyməti: ; C nöqtəsində məqsəd funksiyasının qiyməti: ; Bu o deməkdir ki, funksiyanın maksimum qiyməti A(0; 2) nöqtəsində əldə edilir və 13-ə bərabərdir. H nöqtəsinin koordinatlarını tapaq. Bunu etmək üçün sistemi nəzərdən keçirin: Tənliyin unikal həlli varsa, xətt dairəyə tangensdir. Diskriminant 0 olarsa, kvadrat tənliyin unikal həlli var. 2) Minimum həlli tapmaq üçün Laqranj funksiyasını tərtib edək: At x 1
=2.5;
x 2
=4.5
alırıq: Sistemin həlli var, yəni. ekstremum üçün kifayət qədər şərait təmin edilir. Maksimum həlli tapmaq üçün Laqranj funksiyasını tərtib edək: Ekstremum üçün kifayət qədər şərtlər: At x 1
=0;
x 2
=2
alırıq: Sistemin də bir həlli var, yəni. ekstremum üçün kifayət qədər şərait təmin edilir. Cavab: məqsəd funksiyasının minimumu o zaman əldə edilir məbləğində iki müəssisəyə vəsait ayrılıb d vahidlər. İlk müəssisəni bir il müddətinə ayırarkən x vəsait vahidləri gəlir təmin edir k 1
x vahidlər və ikinci müəssisəyə ayrıldıqda y vəsait vahidləri, gəlir təmin edir k 1
y vahidlər. Birinci müəssisə üzrə ilin sonuna vəsait qalığı bərabərdir nx, və ikinci üçün mənim. Ümumi gəlirin ən çox olması üçün bütün vəsaitləri 4 il ərzində necə bölüşdürmək olar? Problemi dinamik proqramlaşdırma metodundan istifadə edərək həll edin. i=8, k=1. A=2200; k 1 =6; k 2 =1; n=0,2; m=0,5. Həll: Bütün 4 il müddətini hər biri bir ilə bərabər olan 4 mərhələyə bölürük. Birinci ildən başlayaraq mərhələləri nömrələyək. K-ci mərhələdə A və B müəssisələrinə müvafiq olaraq ayrılmış vəsaitlər X k və Y k olsun. Onda X k + Y k = a k cəmi k – həmin mərhələdə istifadə olunmuş vəsaitin ümumi məbləği və əvvəlki mərhələdən qalan k – 1. birinci mərhələdə bütün ayrılmış vəsaitlər istifadə olunur və a 1 = 2200 vahid . k – həmin mərhələdə X k və Y k vahidlərinin ayrılması ilə əldə ediləcək gəlir 6X k + 1Y k olacaqdır. k – həmin mərhələdən başlayaraq son mərhələlərdə alınan maksimum gəlir f k (a k) vahidi olsun. Optimallıq prinsipini ifadə edən funksional Bellman tənliyini yazaq: ilkin vəziyyət və ilkin həll nə olursa olsun, sonrakı həll ilkin vəziyyət nəticəsində alınan vəziyyətə görə optimal olmalıdır: Hər bir mərhələ üçün X k dəyərini və dəyəri seçməlisiniz Yk=ak- Xk. Bunu nəzərə alaraq, gəliri IX mərhələdə tapacağıq: Bellman funksional tənliyi belə olacaq: Sonuncudan başlayaraq bütün mərhələləri nəzərdən keçirək. (xətti funksiyanın maksimumu seqmentin sonunda x 4 = a 4-də əldə edildiyi üçün);
Oxşar sənədlər
;
; 
;
; 
.
.
Tapşırıq № 2
ó
ó 
Sonra 
; ; 
- funksiyanın minimum qiyməti.
ó 
ó 
ó 
; ; məqsəd funksiyasının maksimumuna çatır 
; .
Tapşırıq №3
