Simpleks üsulu ilə məsələlərin həlli alqoritmi. Problemin həlli nümunəsi. LLP həlli üçün Simpleks metodu. Element çevrilməsinin həlli
Xətti proqramlaşdırma məsələlərinin həlli üçün Simpleks metodu
1. Giriş. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 səhifə
2. Xətti proqramlaşdırma məsələlərinin həlli üçün sadə üsul. . . 4-10 səhifə
3. Xətti proqramlaşdırma məsələlərinin həlli üçün simpleks metodunun alqoritmi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 səhifə
4. Simpleks üsulu ilə məsələnin həllinə nümunə. . . . . . . . . . . . . . . . . . 11-15 səhifə
5. Nəticə. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16 səhifə
6. İstifadə olunan istinadların siyahısı. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 səhifə
1. Giriş
İş xətti proqramlaşdırma məsələsinin həlli üçün ən ümumi üsula (simpleks metodu) həsr edilmişdir. Simpleks metodu xətti proqramlaşdırmada klassik və ən inkişaf etmiş metoddur. Bu, ya məhdud sayda addımda tapmağa imkan verir optimal həll, ya da optimal həllin olmadığını müəyyən edin.
Məsələnin həlli üçün bir alqoritm tərtib edilmiş və nümunə ilə təsvir edilmişdir.
1. Optimal istinad həllinin tapılması üsulunu göstərin
2. Bir istinad həllindən digərinə keçid üsulunu göstərin, bu zaman məqsəd funksiyasının dəyəri optimala yaxın olacaqdır, yəni. istinad həllini təkmilləşdirməyin yolunu göstərir
3. Optimal həlldə dəstək həllərinin axtarışını dərhal dayandırmağa və ya optimal həllin olmaması haqqında nəticə çıxarmağa imkan verən meyarlar təyin edin.
2. Xətti proqramlaşdırma məsələlərinin həlli üçün sadə üsul I
Xətti proqramlaşdırma məsələlərinin həlli üçün simpleks metodu (simpleks metodu) həllərin ardıcıl təkmilləşdirilməsi prinsipinə əsaslanan hesablama prosedurudur - bir baza nöqtəsindən digərinə keçid, bunun üçün məqsəd funksiyasının dəyəri daha böyükdür (bu əməliyyatlar simpleks cədvəli).
Bu üsul xətti proqramlaşdırma məsələsinin istinad həllərinin məqsədyönlü sadalanması üsuludur. Bu, məhdud sayda addımlarla ya optimal həlli tapmağa, ya da optimal həllin olmadığını müəyyən etməyə imkan verir. Sübut edilmişdir ki, əgər optimal həll mövcuddursa, o, mütləq məhdud sayda addımlardan sonra tapılacaqdır ("velosiped sürmə" fenomeninin mümkün olduğu, yəni. eyni mövqe).
Simpleks metodu xətti proqramlaşdırmada əsasdır. Məsələnin həlli şərtlər çoxhərlisinin təpələrindən birini nəzərdən keçirməklə başlayır. Əgər tədqiq olunan təpə maksimuma (minimum) uyğun gəlmirsə, onlar qonşuya keçir, problemi maksimuma həll edərkən məqsəd funksiyasının dəyərini artırır və minimuma həll edərkən onu azaldırlar. Beləliklə, bir təpədən digərinə keçmək məqsəd funksiyasının dəyərini yaxşılaşdırır. Polihedronun təpələrinin sayı məhdud olduğundan, sonlu sayda addımda onun tapılması təmin edilir. optimal dəyər ya da problemin həll olunmaz olduğunun müəyyən edilməsi.
Bu üsul universaldır, kanonik formada istənilən xətti proqramlaşdırma məsələsinə tətbiq olunur. Buradakı məhdudiyyətlər sistemi naməlumların sayının tənliklərin sayından çox olduğu xətti tənliklər sistemidir. Sistemin rütbəsi r olarsa, qalan naməlumlar baxımından ifadə etdiyimiz r naməlumları seçə bilərik. Dəqiqlik üçün ilk ardıcıl naməlum X1, X2, ..., Xr seçildiyini fərz edirik. Onda tənliklər sistemimizi belə yazmaq olar
İstənilən ardıcıl sistem, məsələn, Qauss metodundan istifadə etməklə bu formaya endirilə bilər. Düzdür, onu qalan ilk r naməlumlar baxımından ifadə etmək həmişə mümkün olmur (bunu qeydin müəyyənliyi üçün etdik). Bununla belə, belə r bilinməyənlər mütləq mövcud olacaqdır. Bu naməlumlar (dəyişənlər) əsas adlanır, qalanları sərbəstdir.
Sərbəst dəyişənlərə müəyyən dəyərlər təyin etməklə və əsasların qiymətlərini hesablamaqla (sərbəst olanlar baxımından ifadə olunur) biz məhdudiyyətlər sistemimiz üçün müxtəlif həllər əldə edəcəyik. Beləliklə, hər hansı bir həll əldə edilə bilər. Sərbəst dəyişənlərin sıfıra bərabər olduğu halda əldə edilən xüsusi həllərlə maraqlanacağıq. Bu cür həllər əsas adlanır; verilmiş məhdudiyyətlər sisteminin müxtəlif əsas növləri olduğu qədər onların sayı çoxdur. Dəyişənlərin dəyərləri mənfi deyilsə, əsas həll yol verilən əsas həll və ya dəstək həlli adlanır. X1, X2, ..., Xr dəyişənləri əsas götürülərsə, b1, şərti ilə həll (b1, b2,..., br, 0, ..., 0) istinad olacaq. b2,... , br ≥ 0.
Simpleks metodu simpleks metodunun əsas teoremi adlanan teoremə əsaslanır. Xətti proqramlaşdırma məsələsinin kanonik formada optimal planları arasında onun məhdudiyyətlər sisteminə istinad həlli mütləqdir. Problemin optimal planı unikaldırsa, o, hansısa istinad həlli ilə üst-üstə düşür. Məhdudiyyətlər sisteminə sonlu sayda müxtəlif dəstəkləyici həllər var. Buna görə də, problemin kanonik formada həllini istinad həlləri vasitəsilə axtarmaq və onların arasından F dəyərinin ən böyük olanını seçməklə axtarmaq olar. Lakin, birincisi, bütün istinad həlləri məlum deyil və onları tapmaq lazımdır, ikincisi, real problemlərdə bu həllər çoxdur və birbaşa axtarış demək olar ki, mümkün deyil. Simpleks metodu dəstək həllərinin istiqamətləndirilmiş sadalanması üçün müəyyən bir prosedurdur. Simpleks metodunun müəyyən bir alqoritmindən istifadə edərək əvvəlcədən tapılmış müəyyən istinad həllinə əsaslanaraq, F məqsəd funksiyasının dəyərinin köhnədən az olmayan yeni bir istinad həllini hesablayırıq. Bir sıra addımlardan sonra biz optimal plan olan istinad həllinə gəlirik.
Beləliklə, simpleks metodu həm birinci (ilkin) əsas həlli taparkən, həm də digər əsas həllərə keçərkən müəyyən bir sıra təqdim edir.
Simpleks üsulu ilə məsələnin həllinin həyata keçirilməsi blok-sxemdə aydın şəkildə göstərilmişdir (şək. 1).
Beləliklə, simpleks metodunun tətbiqi iki mərhələyə bölünür: məhdudiyyətlər sisteminə yol verilən əsas həllin tapılması və ya onun uyğunsuzluğu faktının müəyyən edilməsi; optimal həll yolunun tapılması. Bundan əlavə, hər bir mərhələ bu və ya digər əsas həllə uyğun gələn bir neçə addımı əhatə edə bilər. Lakin əsas həllərin sayı həmişə məhdud olduğundan, simplex metodunun addımlarının sayı da məhduddur.
Simpleks metodunun verilmiş diaqramı onun alqoritmik mahiyyətini (ardıcıl əməliyyatların yerinə yetirilməsinə dair aydın göstərişin xarakterini) aydın şəkildə ifadə edir ki, bu da bu metodu 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.
Onun hesablama tərəfini təsvir edək. Simpleks üsulu ilə hesablamalar xətti proqramlaşdırma məsələsinin kanonik formada qısaldılmış təsviri olan simpleks cədvəlləri şəklində təşkil edilir. Simpleks cədvəlini tərtib etməzdən əvvəl problem transformasiya edilməli, məhdudiyyətlər sistemi məqbul əsas formaya gətirilməli, onun köməyi ilə əsas dəyişənlər məqsəd funksiyasından xaric edilməlidir. Bu ilkin transformasiyalar məsələsini aşağıda nəzərdən keçirəcəyik. İndi onların artıq tamamlandığını və tapşırığın formasına sahib olduğunu güman edəcəyik:
Burada qeydin müəyyənliyi üçün nəzərdə tutulur ki, X1, X2, ..., Xr dəyişənləri əsas dəyişənlər kimi götürülə bilər və b1, b2,..., br ≥ 0 (uyğun əsas həll istinad bir).
Problem bəyanatında bütün bərabərliklərdə simpleks cədvəlini tərtib etmək üçün dəyişənləri ehtiva edən terminlər sol tərəfə köçürülür, sərbəst olanlar sağda qalır, yəni. məsələ bərabərlik sistemi şəklində yazılır:
Qeyd. Əsas dəyişənlərin adları burada yalnız aydınlıq üçün götürülüb və faktiki cədvəldə fərqli görünə bilər.
Simpleks cədvəli ilə işləmə qaydası. Birinci simpleks cədvəli transformasiyaya məruz qalır, onun mahiyyəti yeni istinad həllinə keçiddir.
Növbəti cədvələ keçmək üçün alqoritm aşağıdakı kimidir:
cədvəlin axırıncı sətri (indeksi) nəzərdən keçirilir və bu sətrin əmsalları arasından (sərbəst terminlər sütunu istisna olmaqla) max tapılarkən ən kiçik mənfi ədəd, min axtararkən isə ən böyük müsbət ədəd seçilir. Əgər heç biri yoxdursa, onda orijinal əsas həll optimaldır və bu cədvəl sonuncudur;
sonuncu sətirdə seçilmiş mənfi (müsbət) əmsala uyğun gələn cədvəl sütunu - əsas sütuna baxılır və bu sütunda müsbət əmsallar seçilir. Əgər onlar yoxdursa, o zaman məqsəd funksiyası dəyişənlərin icazə verilən dəyərləri diapazonunda qeyri-məhduddur və problemin həlli yoxdur;
Sütunun seçilmiş əmsalları arasında müvafiq sərbəst terminin (sərbəst şərtlər sütununda yerləşir) bu elementə nisbətinin mütləq dəyərinin minimal olduğu biri seçilir. Bu əmsal həlledici əmsalı adlanır və onun yerləşdiyi xətt açardır;
Xətti proqramlaşdırma məsələsini həll etmək lazımdır.
Məqsəd funksiyası:
2x 1 +5x 2 +3x 3 +8x 4 →dəq
Məhdudiyyət şərtləri:
3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1
Məhdudiyyətlər sistemini kanonik formaya gətirək, bunun üçün əlavə dəyişənlər əlavə etməklə bərabərsizliklərdən bərabərliyə keçmək lazımdır.
Problemimiz minimumlaşdırma problemi olduğu üçün onu maksimum axtarış probleminə çevirməliyik. Bunun üçün məqsəd funksiyasının əmsallarının işarələrini əks olanlara dəyişirik. Birinci bərabərsizliyin elementlərini dəyişmədən yazırıq, əlavə x 5 dəyişəni əlavə edirik və “≤” işarəsini “=” olaraq dəyişirik. İkinci və üçüncü bərabərsizliklər “≥” işarələrinə malik olduğundan onların əmsallarının işarələrini əksinə dəyişmək və onlara müvafiq olaraq əlavə x 6 və x 7 dəyişənləri daxil etmək lazımdır. Nəticədə, ekvivalent bir problem alırıq:
3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1
İlkin simpleks cədvəlinin formalaşmasına davam edirik. Məqsəd funksiyasının əks işarəli əmsalları cədvəlin F sətirinə daxil edilir.
Pulsuz üzv |
|||||
F | |||||
X5 | |||||
X6 | |||||
X7 |
Tərtib etdiyimiz cədvəldə sərbəst terminlər sütununda mənfi elementlər var, onların arasında modulda maksimumu tapırıq - bu elementdir: -6, aparıcı sıranı təyin edir - X6. Bu sətirdə modulda maksimum mənfi elementi də tapırıq: -10 o, aparıcı sütun olacaq X3 sütununda yerləşir. Aparıcı sətirdəki dəyişən bazadan, aparıcı sütuna uyğun dəyişən isə bazaya daxil edilir. Simpleks cədvəlini yenidən hesablayaq:
X1 | X2 | X6 | X4 | Pulsuz üzv | |
F | 0.8 | 8.9 | 0.3 | 6.5 | -1.8 |
X5 | 4.6 | 0.8 | -0.4 | 3 | 14.4 |
X3 | 0.4 | -1.3 | -0.1 | 0.5 | 0.6 |
X7 | -2.6 | -8.3 | -0.1 | 0.5 | -0.4 |
Tərtib etdiyimiz cədvəldə sərbəst terminlər sütununda mənfi elementlər var, onların arasında modulda maksimumu tapırıq - bu elementdir: -0,4, aparıcı sıranı təyin edir - X7. Bu sətirdə modulda maksimum mənfi elementi də tapırıq: -8.3 o, aparıcı sütun olacaq X2 sütununda yerləşir. Aparıcı sətirdəki dəyişən bazadan, aparıcı sütuna uyğun dəyişən isə bazaya daxil edilir. Simpleks cədvəlini yenidən hesablayaq:
X1 | X7 | X6 | X4 | Pulsuz üzv | |
F | -1.988 | 1.072 | 0.193 | 7.036 | -2.229 |
X5 | 4.349 | 0.096 | -0.41 | 3.048 | 14.361 |
X3 | 0.807 | -0.157 | -0.084 | 0.422 | 0.663 |
X2 | 0.313 | -0.12 | 0.012 | -0.06 | 0.048 |
Sərbəst şərtlər sütununda mənfi elementlər olmadığı üçün yol verilən həll tapılmışdır.F sətirində mənfi elementlər var, bu isə nəticədə alınan həllin optimal olmadığını bildirir. Gəlin aparıcı sütunu təyin edək. Bunu etmək üçün F sətirində maksimum modulu olan mənfi elementi tapacağıq - bu -1.988 Aparıcı sətir sərbəst terminin aparıcı sütunun müvafiq elementinə nisbətinin minimal olduğu biri olacaq. Aparıcı sıra X2, aparıcı element isə: 0,313.
X2 | X7 | X6 | X4 | Pulsuz üzv | |
F | 6.351 | 0.31 | 0.269 | 6.655 | -1.924 |
X5 | -13.895 | 1.763 | -0.577 | 3.882 | 13.694 |
X3 | -2.578 | 0.152 | -0.115 | 0.577 | 0.539 |
X1 | 3.195 | -0.383 | 0.038 | -0.192 | 0.153 |
F sətirində mənfi elementlər olmadığına görə
optimal həll yolu tapıldı. İlkin tapşırıq minimumu tapmaq olduğundan, optimal həll əks işarə ilə alınan F sətirinin sərbəst müddəti olacaqdır. F=1,924
dəyişən dəyərləri bərabərdir: x 3 =0,539, x 1 =0,153. x 2 və x 4 dəyişənləri bazaya daxil edilmir, ona görə də x 2 =0 x 4 =0.
Xətti proqramlaşdırma məhdud resurslardan istifadəni optimallaşdırmaq üçün nəzərdə tutulmuş riyazi modelləşdirmə texnikasıdır. LP hərbi sahədə, sənayedə, kənd təsərrüfatında, nəqliyyat sənayesində, iqtisadiyyatda, səhiyyə sistemində və hətta sosial elmlərdə uğurla istifadə olunur. Bu metodun geniş tətbiqi bu metodu həyata keçirən yüksək səmərəli kompüter alqoritmləri ilə də dəstəklənir. Tam, qeyri-xətti və stoxastik proqramlaşdırma daxil olmaqla, digər, daha mürəkkəb modellər və əməliyyat tədqiqatı (OR) problemləri üçün optimallaşdırma alqoritmləri xətti proqramlaşdırma alqoritmlərinə əsaslanır.
Optimallaşdırma problemi məqsəd funksiyasının optimal (maksimum və ya minimum) qiymətinin tapılmasından ibarət iqtisadi və riyazi problemdir və dəyişənlərin qiymətləri müəyyən məqbul dəyərlər diapazonuna aid olmalıdır.
Ən ümumi formada xətti proqramlaşdırma məsələsi riyazi olaraq aşağıdakı kimi yazılır:
Harada X = (x 1 , x 2 , ... , x n ) ; W– dəyişənlərin icazə verilən dəyərlərinin diapazonu x 1 , x 2 , ... , x n ;f(X)- məqsəd funksiyası.
Optimallaşdırma problemini həll etmək üçün onun optimal həllini tapmaq kifayətdir, yəni. bunu göstərir istənilən vaxt.
Optimallaşdırma probleminin optimal həlli yoxdursa, həll olunmazdır. Xüsusilə, məqsəd funksiyası varsa, maksimumlaşdırma problemi həll edilməyəcəkdir f(X) icazə verilən dəstdə yuxarıdan məhdudlaşdırılmır W.
Optimallaşdırma məsələlərinin həlli üsulları həm məqsəd funksiyasının növündən asılıdır f(X), və icazə verilən çoxluğun strukturundan W. Əgər məsələdə hədəf funksiya funksiyadırsa n dəyişənlər, sonra həll üsulları riyazi proqramlaşdırma metodları adlanır.
Xətti proqramlaşdırma məsələlərinin xarakterik xüsusiyyətləri aşağıdakılardır:
optimallıq indeksi f(X) həll elementlərinin xətti funksiyasıdır X = (x 1 , x 2 , ... , x n ) ;
mümkün həllər üçün qoyulan məhdudlaşdırıcı şərtlər xətti bərabərliklər və ya bərabərsizliklər formasını alır.
Xətti proqramlaşdırma problemi Riyazi modeli aşağıdakı formada olan əməliyyat tədqiqatı problemi adlanır:
(2) (3) (4) (5)
Bu halda problemin yol verilən həllər toplusunu təyin edən xətti tənliklər (3) və bərabərsizliklər (4), (5) sistemi W, çağırdı məhdudiyyətlər sistemi xətti proqramlaşdırma problemləri və xətti funksiya f(X)çağırdı hədəf funksiyası və ya optimallıq meyarı .
Etibarlı həll ədədlər toplusudur ( plan ) X = (x 1 , x 2 , ... , x n ) , problemin məhdudiyyətlərini ödəmək. Optimal həll – bu, məqsəd funksiyasının maksimum (minimum) qiymətini aldığı plandır.
Xətti proqramlaşdırma məsələsinin riyazi modeli aşağıdakı formaya malikdirsə:
sonra problemin təqdim edildiyini söyləyirlər kanonik forma .
İstənilən xətti proqramlaşdırma problemi kanonik formada xətti proqramlaşdırma məsələsinə çevrilə bilər. Bunun üçün ümumi halda maksimumlaşdırma problemini minimuma endirməyi bacarmaq lazımdır; bərabərsizlik məhdudiyyətlərindən bərabərlik məhdudiyyətlərinə keçin və qeyri-mənfilik şərtinə tabe olmayan dəyişənləri əvəz edin. Müəyyən bir funksiyanı maksimuma çatdırmaq əks işarə ilə götürülmüş eyni funksiyanı minimuma endirməyə bərabərdir və əksinə.
Xətti proqramlaşdırma məsələsinin kanonik formaya gətirilməsi qaydası aşağıdakı kimidir:
əgər ilkin məsələdə xətti funksiyanın maksimumunu təyin etmək lazımdırsa, onda siz işarəni dəyişməli və bu funksiyanın minimumunu axtarmalısınız;
məhdudiyyətlərin sağ tərəfi mənfi olarsa, bu məhdudiyyət -1-ə vurulmalıdır;
məhdudiyyətlər arasında bərabərsizliklər varsa, onda əlavə qeyri-mənfi dəyişənlər daxil edilməklə onlar bərabərliyə çevrilir;
bəzi dəyişən varsa x j işarə məhdudiyyəti yoxdur, onda (məqsəd funksiyasında və bütün məhdudiyyətlərdə) iki yeni qeyri-mənfi dəyişən arasındakı fərqlə əvəz olunur: x 3 = x 3 + -x 3 - , Harada x 3 + , x 3 - ≥ 0 .
Misal 1. Xətti proqramlaşdırma probleminin kanonik formaya endirilməsi:
min L = 2x 1 + x 2 -x 3 ; 2x 2 -x 3 ≤ 5; x 1 + x 2 -x 3 ≥ -1; 2x 1 -x 2 ≤ -3; x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.
Məhdudiyyətlər sisteminin hər bir tənliyinə səviyyə dəyişənlərini daxil edək x 4 , x 5 , x 6 . Sistem bərabərliklər şəklində yazılacaq və məhdudiyyətlər sisteminin birinci və üçüncü tənliklərində dəyişənlər x 4 , x 6 sol tərəfə “+” işarəsi ilə, ikinci tənliyə isə dəyişən daxil edilir x 5 "-" işarəsi ilə daxil edilir.
2x 2 -x 3 + x 4 = 5; x 1 + x 2 -x 3 -x 5 = -1; 2x 1 -x 2 + x 6 = -3; x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.
Kanonik formada sərbəst şərtlər müsbət olmalıdır; bunun üçün son iki tənliyi -1-ə vurun:
2x 2 -x 3 + x 4 = 5; -x 1 -x 2 + x 3 + x 5 = 1; -2x 1 + x 2 -x 6 = 3.
Xətti proqramlaşdırma məsələlərinin həlli üçün Simpleks metodu.
Simpleks metod alqoritmi məhdud sayda mümkün əsas həlləri nəzərə alaraq optimal həlli tapır. Simpleks metod alqoritmi həmişə bəzi mümkün əsas həll yolu ilə başlayır və sonra məqsəd funksiyasının dəyərini “yaxşılaşdıran” başqa mümkün əsas həlli tapmağa çalışır. Bu, yalnız hər hansı sıfır (əsas olmayan) dəyişənin artması məqsəd funksiyasının dəyərinin yaxşılaşmasına səbəb olduqda mümkündür. Lakin qeyri-əsas dəyişənin müsbət olması üçün cari əsas dəyişənlərdən biri sıfıra təyin olunmalıdır, yəni. əsas olmayana çevirmək. Bu, yeni həllin tam olaraq ehtiva etməsi üçün lazımdır məsas dəyişənlər. Simpleks metodunun terminologiyasına uyğun olaraq seçilmiş sıfır dəyişən çağırılır giriş (əsas üçün) və silinəcək əsas dəyişəndir istisna olunur (əsasdan).
Simpleks metodunda giriş və istisna dəyişənlərinin seçilməsi üçün iki qayda çağıraq optimallıq şərti Və yolverilməlilik şərti . Gəlin bu qaydaları formalaşdıraq və həmçinin simpleks metodunu həyata keçirərkən yerinə yetirilən hərəkətlərin ardıcıllığını nəzərdən keçirək.
Optimallıq vəziyyəti. Maksimallaşdırma (minimizasiya) məsələsindəki giriş dəyişəni qeyri-əsas dəyişəndir və ən böyük mənfi (müsbət) əmsala malikdir. hədəf-xətt. Əgər daxil hədəf-sətirdə bir neçə belə əmsal var, onda daxil edilmiş dəyişənin seçimi özbaşına aparılır. Optimal həll o zaman əldə edilir hədəf-xətti, qeyri-əsas dəyişənlər üçün bütün əmsallar mənfi (müsbət olmayan) olacaq.
Qəbul olunma şərti. Həm maksimumlaşdırma, həm də minimumlaşdırma məsələlərində məhdudiyyətin sağ tərəfinin dəyərinin aparıcı sütunun müsbət əmsalına nisbətinin minimal olduğu əsas dəyişən xaric edilmiş kimi seçilir. Bu xassə ilə bir neçə əsas dəyişən varsa, xaric edilən dəyişənin seçimi ixtiyaridir.
Simpleks cədvəllərindən istifadə edərək maksimumun tapılmasına dair xətti proqramlaşdırma məsələsinin həlli alqoritmini təqdim edək.
F = с 1 x 1 +с 2 x 2 +…+с n x n max
x 1 0, x 2 0,…, x n 0.
1-ci addım. Əlavə dəyişənlər təqdim edirik və nəticədə tənliklər sistemini və xətti funksiyanı genişləndirilmiş sistem şəklində yazırıq.
F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.
2-ci addım.İlkin simpleks cədvəlini tərtib edirik.
Dəyişənlər |
Əsas və əlavə dəyişənlər |
pulsuz üzvlər (həll) |
Təxmini münasibət |
|||||||
3-cü addım. Biz optimallıq meyarının yerinə yetirilməsini - sonuncu sətirdə mənfi əmsalların olmasını yoxlayırıq. Əgər onlar yoxdursa, onda həll optimaldır və F * =c o, əsas dəyişənlər müvafiq əmsallara bərabərdir b j, qeyri-əsas dəyişənlər sıfıra bərabərdir, yəni X * =(b 1,b 2,…, b m, 0,…, 0).
4-cü addım. Əgər optimallıq meyarına cavab verilmirsə, onda sonuncu (təxmin edilən) sətirdəki ən böyük mütləq mənfi əmsalı s həlledici sütunu müəyyən edir.
Qətnamə xəttini müəyyən etmək üçün qiymətləndirmə əmsallarını hesablayırıq və cədvəlin son sütununu doldurun.
i-ci sıranın təxmini nisbəti
əgər b i və a varsa müxtəlif əlamətlər;
əgər b i =0 və a olarsa<0;
əgər a =0 olarsa;
0 əgər b i =0 və a >0 olarsa;
Qiymətləndirici münasibətlər sütununda minimum elementi tapırıq min g imkan verən sətiri təyin edir.
Minimum yoxdursa, problemin yekun I optimalı yoxdur və həll olunmazdır.
Həlledici sətir və sütunun kəsişməsində a gs həlledici element var.
5-ci addım. Aşağıdakı cədvəli quraq. Bunun üçün
Üçüncü addıma keçək.
M-metodu Bəzən, ZLP-ni həll edərkən, naməlum sistem məhdudiyyətləri üçün əmsallar matrisində vahid matrisin tərtib oluna biləcəyi vahid sütunlar yoxdur, yəni. bazis dəyişənlərinin seçilməsində problem yaranır və ya ilkin həll yolverilməzdir. Belə hallarda istifadə edin süni əsas metodu (M - üsul).Əsas dəyişənlərin olmadığı bütün məhdudiyyətlərdə, süni dəyişənlər. Süni dəyişənlər məqsəd funksiyasına max olan məsələlər üçün əmsalı (- M) və min ilə bağlı məsələlər üçün əmsallı (+ M) daxil edilir, burada M kifayət qədər böyük müsbət ədəddir.. Sonra uzadılmış məsələ simpleks metodunun qaydalarından istifadə etməklə həll edilir. Əgər bütün süni dəyişənlər sıfıra bərabərdirsə, yəni. əsasdan çıxarılsa, ya ilkin məsələnin optimal həlli alınacaq, ya da ilkin məsələ daha da həll edilərək onun optimal həlli tapılacaq və ya həll olunmazlığı müəyyən ediləcək. Əgər süni dəyişənlərdən ən azı birinin sıfırdan fərqli olduğu ortaya çıxarsa, ilkin problemin həlli yoxdur.
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Xəbərdarlıq
Bütün xanalar silinsin?
Bağlayın Təmizləyin
Məlumat daxil etmə təlimatları.Ədədlər tam ədədlər (məsələn: 487, 5, -7623 və s.), onluq (məs. 67., 102.54 və s.) və ya kəsr kimi daxil edilir. Kəsr a/b şəklində daxil edilməlidir, burada a və b (b>0) tam və ya onluq ədəddir. Nümunələr 45/5, 6.6/76.4, -7/6.7 və s.
Simpleks metodu
Simpleks metodundan istifadə edərək ZLP-nin həlli nümunələri
Nümunə 1. Aşağıdakı xətti proqramlaşdırma məsələsini həll edin:
Tənliklər sisteminin məhdudiyyətlərinin sağ tərəfi formaya malikdir:
Cari istinad planını yazaq:
Bu istinad planı optimal deyil, çünki sonuncu sırada mənfi elementlər var. Modulda ən böyük mənfi element (-3) təşkil edir, ona görə də vektor bazaya daxil edilir x saat . min(40:6, 28:2)=20/3 1-ci sətirə uyğundur. Vektor bazadan çıxır x 3. Sütun üçün Qauss eliminasiyasını edək x 2, aparıcı elementin 1-ci sətirə uyğun olduğunu nəzərə alaraq. Bu sütunun aparıcı elementdən başqa bütün elementlərini sıfırlayaq. Bunu etmək üçün 2, 3, 4-cü sətirləri müvafiq olaraq -1/3, 1/6, 1/2 ilə vurulan 1-ci sətirlə əlavə edin. Sonra, aparıcı elementi olan xətti aparıcı elementə bölürük.
Bu istinad planı optimal deyil, çünki sonuncu sıra mənfi elementə malikdir (-3), buna görə də əsas vektor daxildir x 1 . Bazadan hansı vektorun çıxdığını müəyyən edirik. Bunu etmək üçün hesablayırıq saat . min(44/3:11/3, 62/3:5/3)=4 2-ci sətirə uyğundur. Vektor bazadan çıxır x 4 . Sütun üçün Qauss eliminasiyasını edək x 1, aparıcı elementin 2-ci sətirə uyğun gəldiyini nəzərə alaraq. Bu sütunun aparıcı elementdən başqa bütün elementlərini sıfırlayaq. Bunun üçün müvafiq olaraq 1/11, -5/11, 9/11-ə vurulan 2-ci sətirlə 1, 3, 4-cü sətirləri əlavə edin. Sonra, aparıcı elementi olan xətti aparıcı elementə bölürük.
Simpleks cədvəli aşağıdakı formanı alacaq:
Cari istinad planı optimaldır, çünki dəyişənlər altında 4-cü sətirdə mənfi elementlər yoxdur.
Həll yolu belə yazıla bilər: .
Bu nöqtədə məqsəd funksiyasının dəyəri: F(X)=.
Misal 2. Funksiyanın maksimumunu tapın
Həll.
Əsas vektorlar x 4 , x 3 buna görə də sütunlardakı bütün elementlər x 4 , x 3 üfüqi xəttin altında sıfır olmalıdır.
Bütün sütun elementlərini sıfırlayın x 4, aparıcı element istisna olmaqla. Bunu etmək üçün 1-ci sətir 4-ə vurularaq 3-cü sətir əlavə edin. Sütunun bütün elementlərini sıfıra sıfırlayın x 3, aparıcı element istisna olmaqla. Bunu etmək üçün 3-cü sətri 1-ə vurulan 2-ci sətir əlavə edin.
Simpleks cədvəli aşağıdakı formanı alacaq:
Bu istinad planı optimal deyil, çünki sonuncu sıra mənfi elementə malikdir (-11), buna görə də əsas vektor daxildir x 2. Bazadan hansı vektorun çıxdığını müəyyən edirik. Bunu etmək üçün hesablayırıq saat . Buna görə də, məqsəd funksiyası yuxarıdan qeyri-məhduddur. Bunlar. xətti proqramlaşdırma problemi həll edilmir.
Süni əsas metodundan istifadə edərək ZLP-nin həlli nümunələri
Misal 1. Funksiyanın maksimumunu tapın
Həlli.Baza vektorlarının sayı 3 olmalıdır, ona görə biz süni dəyişən əlavə edirik və məqsəd funksiyasına bu dəyişəni −M-ə vururuq, burada M çox böyük ədəddir:
Tənliklər sisteminin əmsal matrisi aşağıdakı formaya malikdir:
Əsas vektorlar buna görə də üfüqi xəttin altındakı sütunlardakı bütün elementlər sıfır olmalıdır.
Aparıcı elementdən başqa sütunun bütün elementlərini sıfırlayaq. Bunu etmək üçün 5-ci sətirə -1 ilə vurulan 3-cü sətir əlavə edin.
Simpleks cədvəli aşağıdakı formanı alacaq:
Bu istinad planı optimal deyil, çünki sonuncu sırada mənfi elementlər var. Ən böyük mütləq mənfi element (-5) olduğu üçün vektor bazaya daxil edilir.Hansı vektorun bazisdən çıxdığını müəyyən edirik. Bunu etmək üçün hesablayırıq saat 3-cü sətirə uyğundur.Bazadan vektor çıxır.Aparıcı elementin 3-cü sıraya uyğun olduğunu nəzərə alaraq, sütun üçün Qauss istisnasını edək.Aparıcı elementdən başqa bu sütunun bütün elementlərini sıfırlayaq. Bunu etmək üçün sətirləri 5-ə əlavə edin, 3-cü sətir 1-ə vurulur. Sonra, aparıcı elementi olan xətti aparıcı elementə bölün.
Simpleks cədvəli aşağıdakı formanı alacaq:
Bu istinad planı optimal deyil, çünki sonuncu sırada mənfi elementlər var. Ən böyük mütləq mənfi element (-3) olduğundan vektor bazaya daxil edilir.Hansı vektorun bazisdən çıxdığını müəyyən edirik. Bunu etmək üçün hesablayırıq saat 1-ci sıraya uyğundur. Vektor bazadan çıxır x 2. Sütun üçün Qauss eliminasiyasını edək x 1 , aparıcı elementin sətir 1-ə uyğun olduğunu nəzərə alaraq. Bu sütunun aparıcı elementdən başqa bütün elementlərini sıfırlayaq. Bunun üçün müvafiq olaraq 3/2, -1/10, 3/2 ilə vurulan 1-ci sətirlə 2, 3, 4-cü sətirləri əlavə edin. Sonra, aparıcı elementi olan xətti aparıcı elementə bölürük.
Simpleks cədvəli aşağıdakı formanı alacaq:
Bu istinad planı optimal deyil, çünki sonuncu sırada mənfi elementlər var. Modulda ən böyük mənfi element (-13/2), buna görə də əsas vektoru ehtiva edir x 3. Bazadan hansı vektorun çıxdığını müəyyən edirik. Bunu etmək üçün hesablayırıq saat 3-cü sətirə uyğundur.Vektor bazadan çıxır x 5 . Sütun üçün Qauss eliminasiyasını edək x 3, aparıcı elementin 3-cü sıraya uyğun gəldiyini nəzərə alaraq. Bu sütunun aparıcı elementdən başqa bütün elementlərini sıfırlayaq. Bunu etmək üçün 1, 2, 4-cü sətirləri müvafiq olaraq 5/3, 25/9, 65/9 ilə vurulan 3-cü sətirlə əlavə edin. Sonra, aparıcı elementi olan xətti aparıcı elementə bölürük.
Simpleks cədvəli aşağıdakı formanı alacaq:
Cari istinad planı optimaldır, çünki 4−5-ci sətirlərdə dəyişənlərin altında mənfi elementlər yoxdur.
İlkin problemin həlli aşağıdakı kimi yazıla bilər:
Misal 2. Xətti proqramlaşdırma məsələsi üçün optimal planı tapın:
Tənliklər sisteminin əmsal matrisi aşağıdakı formaya malikdir:
Əsas vektorlar x 4 , x 5 , x 6 buna görə də sütunlardakı bütün elementlər x 4 , x 5 , x 6, üfüqi xəttin altında sıfır olmalıdır.
Bütün sütun elementlərini sıfırlayın x 4, aparıcı element istisna olmaqla. Bunu etmək üçün 4-cü sətirə -1 ilə vurulan 1-ci sətir əlavə edin. Bütün sütun elementlərini sıfırlayın x 5, aparıcı element istisna olmaqla. Bunu etmək üçün 5-ci sətirə -1 ilə vurulan 2-ci sətir əlavə edin. Bütün sütun elementlərini sıfırlayın x 6, aparıcı element istisna olmaqla. Bunu etmək üçün 5-ci sətirə -1 ilə vurulan 3-cü sətir əlavə edin.
Simpleks cədvəli aşağıdakı formanı alacaq:
5-ci sətirdə dəyişənlərə uyğun elementlər x 1 , x 2 , x 3 , x 4 , x 5 , x 6 qeyri-mənfidir və verilmiş sətir və sütunun kəsişməsində yerləşən ədəddir x 0 mənfidir. Sonra orijinal problemin istinad planı yoxdur. Buna görə də qərar verilməzdir.