Simpleks üsulu ilə problemin həlli nümunəsi, eləcə də ikili məsələnin həlli nümunəsi nəzərdən keçirilir.

Problemli vəziyyət

Üç qrup malların satışı üçün kommersiya müəssisəsi b 1 = 240, b 2 = 200, b 3 = 160 vahid məbləğində üç növ məhdud maddi və pul ehtiyatına malikdir. Eyni zamanda, 1 qrup malların satışı üçün 1 min rubl. əmtəə dövriyyəsi üzrə birinci növ resurs a 11 = 2 vahid, ikinci növ resurs a 21 = 4 vahid, üçüncü növ resurs a 31 = məbləğində istehlak edilir. 4 ədəd. 1 min rubl üçün 2 və 3 qrup malların satışı üçün. dövriyyə birinci növ resursa uyğun olaraq a 12 = 3, a 13 = 6 vahid, ikinci növ resurs a 22 = 2, a 23 = 4 vahid, resurs miqdarında istehlak edilir. üçüncü növ 32 = 6, a 33 = 8 ədəddir. 1 min rubl üçün üç qrup malın satışından qazanc. dövriyyə müvafiq olaraq c 1 = 4, c 2 = 5, c 3 = 4 (min rubl). Ticarət dövriyyəsinin planlaşdırılan həcmini və strukturunu müəyyən edin ki, mənfəət əldə etsin ticarət müəssisəsi maksimum idi.

Birbaşa dövriyyənin planlaşdırılması probleminə, simpleks üsulu ilə həll edilir, tərtib etmək ikili problem xətti proqramlaşdırma.
Quraşdırın konjugat cüt dəyişənlər birbaşa və ikili problemlər.
Dəyişən cütlüklərə görə birbaşa məsələnin həllindən alırıq ikili problemin həlli, hansında istehsal olunur resursun qiymətləndirilməsi, malların satışına sərf edilmişdir.

Simpleks metodundan istifadə etməklə məsələnin həlli

X 1, x 2, x 3 satılan malların sayı, min rubl, müvafiq olaraq 1, 2, 3 qrup olsun. Sonra riyazi model tapşırığın forması var:

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(matris(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Simpleks metodunu həll edirik.

Bərabərsizlikləri bərabərliyə çevirmək üçün x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 əlavə dəyişənləri təqdim edirik.

Əsas kimi x 4 = 240 götürək; x 5 = 200; x 6 = 160.

Məlumatları daxil edirik simpleks cədvəli

Simpleks cədvəli №1

Məqsəd funksiyası:

0 240 + 0 200 + 0 160 = 0

Düsturdan istifadə edərək təxminləri hesablayırıq:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Mənfi hesablamalar olduğu üçün plan optimal deyil. Ən aşağı xal:

Biz x 2 dəyişənini bazaya daxil edirik.

Bazadan çıxan dəyişəni təyin edirik. Bunun üçün x2 sütunu üçün ən kiçik mənfi olmayan nisbəti tapırıq.

= 26.667

Ən kiçik qeyri-mənfi: Q 3 = 26,667. Bazadan x 6 dəyişənini çıxarırıq

3-cü sətri 6-ya bölün.
1-ci sətirdən 3-ə vurulan 3-cü sətri çıxarın
2-ci sətirdən 2-yə vurulan 3-cü sətri çıxarın

Hesablayırıq:

alırıq yeni masa:

Simpleks cədvəli № 2

Məqsəd funksiyası:

0 160 + 0 440/3 + 5 80/3 = 400/3

Düsturdan istifadə edərək təxminləri hesablayırıq:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Mənfi qiymətləndirmə Δ 1 = - 2/3 olduğundan, plan optimal deyil.

Biz x 1 dəyişənini bazaya daxil edirik.

Bazadan çıxan dəyişəni təyin edirik. Bunun üçün x 1 sütunu üçün ən kiçik mənfi olmayan nisbəti tapırıq.

Ən kiçik qeyri-mənfi: Q 3 = 40. Biz x 2 dəyişənini bazadan çıxarırıq

3-cü sətri 2/3-ə bölün.
2-ci sətirdən 8/3-ə vurulan 3-cü sətri çıxarın

Hesablayırıq:

Yeni bir cədvəl alırıq:

Simpleks cədvəli №3

Məqsəd funksiyası:

0 160 + 0 40 + 4 40 = 160

Düsturdan istifadə edərək təxminləri hesablayırıq:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Mənfi reytinqlər olmadığı üçün plan optimaldır.

Problemin həlli:

Cavab verin

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

Yəni, 40 min rubl məbləğində birinci növ mal satmaq lazımdır. 2 və 3-cü növ malların satışına ehtiyac yoxdur. Bu halda, maksimum mənfəət F max = 160 min rubl olacaq.

İkili problemin həlli

İkili problemin forması var:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Başlıq="delim(lbrace)(matris(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Bərabərsizlikləri bərabərliyə çevirmək üçün əlavə y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 dəyişənləri təqdim edirik.

Birbaşa və ikili problemlərin cüt dəyişənləri aşağıdakı formaya malikdir:

Birbaşa məsələnin 3 nömrəli sonuncu simpleks cədvəlindən ikili məsələnin həllini tapırıq:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Gəlin nəzərdən keçirək simpleks üsulu xətti proqramlaşdırma (LP) məsələlərinin həlli üçün. Birindən keçidə əsaslanır istinad planı dəyəri olan digərinə məqsəd funksiyası artır.

Simpleks metod alqoritmi aşağıdakı kimidir:

1. Biz əlavə dəyişənlər təqdim etməklə orijinal məsələni kanonik formaya çeviririk. ≤ formalı bərabərsizliklər üçün əlavə dəyişənlər işarəsi (+) ilə təqdim edilir, lakin ≥ formasındadırsa, (-) işarəsi ilə. Əlavə dəyişənlər məqsəd funksiyasına əmsalı bərabər olan müvafiq işarələrlə daxil edilir 0 , çünki hədəf funksiyası iqtisadi mənasını dəyişməməlidir.
2. Vektorlar yazılır P i dəyişənlərin əmsallarından və sərbəst şərtlər sütunundan. Bu hərəkət vahid vektorların sayını təyin edir. Qayda budur ki, məhdudiyyətlər sistemində bərabərsizliklər olduğu qədər vahid vektor olmalıdır.
3. Bundan sonra mənbə məlumatları simpleks cədvəlinə daxil edilir. Vahid vektorlar bazaya daxil edilir və onları bazadan çıxarmaqla optimal həll tapılır. Məqsəd funksiyasının əmsalları əks işarə ilə yazılır.
4. LP problemi üçün optimallıq əlaməti, əgər varsa, həllin optimal olmasıdır f– cərgədə bütün əmsallar müsbətdir. Aktivləşdirmə sütununun tapılması qaydası - baxıldı f– sətir və onun mənfi elementləri arasından ən kiçiyi seçilir. Vektor P i onun ehtiva edəni icazəli olur. Həlledici elementin seçilməsi qaydası - həlledici sütunun müsbət elementlərinin vektorun elementlərinə nisbətləri tərtib edilir. P 0 və ən kiçik nisbəti verən ədəd, simpleks cədvəlinin yenidən hesablanacağı həlledici elementə çevrilir. Bu elementi ehtiva edən xətt aktivləşdirmə xətti adlanır. Qətnamə sütununda müsbət elementlər yoxdursa, problemin həlli yoxdur. Həlledici elementi təyin etdikdən sonra onlar yeni simpleks cədvəlinin yenidən hesablanmasına keçirlər.
5. Yeni simpleks cədvəlinin doldurulması qaydaları. Vahid həlledici elementin yerinə qoyulur və digər elementlərin bərabər olduğu qəbul edilir 0 . Həlledici vektor bazaya əlavə edilir, ondan müvafiq sıfır vektor çıxarılır, qalan bazis vektorları isə dəyişmədən yazılır. Qətnamə sətirinin elementləri ayırdetmə elementi ilə bölünür, qalan elementlər isə düzbucaqlı qaydasına uyğun olaraq yenidən hesablanır.
6. Bu qədər edilir f– sətirin bütün elementləri müsbət olmayacaq.

Yuxarıda müzakirə olunan alqoritmdən istifadə edərək məsələnin həllini nəzərdən keçirək.
Verildi:

Problemi azaldırıq kanonik forma:

Vektorları tərtib edirik:

Simpleks cədvəlini doldurun:

:
Vektorun birinci elementini yenidən hesablayaq P 0, bunun üçün ədədlərdən düzbucaqlı düzəldirik: və alırıq: .

Simpleks cədvəlinin bütün digər elementləri üçün oxşar hesablamalar aparırıq:

Alınan planda f– xəttdə bir mənfi element var – (-5/3), vektor P 1. Onun sütununda imkan verən element olacaq tək müsbət element var. Bu elementlə bağlı cədvəli yenidən hesablayaq:

Mənfi elementlər yoxdur f– xətt tapılmış deməkdir optimal plan :
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Xətti proqramlaşdırma, M: Nauka, 1998,
• Ventzel E.S. Əməliyyat Araşdırması, M: Sovet Radiosu, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Riyazi proqramlaşdırma, M: Ali məktəb, 1986.

Xüsusi Xətti Proqramlaşdırma Həlli

Bu fənn üzrə istənilən tapşırığı saytımızda sifariş edə bilərsiniz. Siz faylları əlavə edə və son tarixləri təyin edə bilərsiniz

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.

Simpleks metodunun əsas məzmunu aşağıdakılardır:

1. Optimal istinad həllini tapmaq üçün metodu 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 daha 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ı barədə nəticə çıxarmağa imkan verən meyarlar təyin edin.

Xətti proqramlaşdırma məsələlərinin həlli üçün simpleks metodunun alqoritmi

Simpleks metodundan istifadə edərək problemi həll etmək üçün aşağıdakıları etməlisiniz:

1. Problemi kanonik formaya gətirin
2. İlkin dəstək həllini "vahid əsası" ilə tapın (əgər dəstək həlli yoxdursa, məhdudiyyətlər sisteminin uyğunsuzluğu səbəbindən problemin həlli yoxdur)
3. İstinad həlli əsasında vektor parçalanmalarının təxminlərini hesablayın və simpleks metodunun cədvəlini doldurun.
4. Əgər optimal həllin unikallığı meyarı təmin edilirsə, problemin həlli başa çatır.
5. Əgər optimal həllər toplusunun mövcudluğu şərti yerinə yetirilirsə, bütün optimal həllər sadə sadalama yolu ilə tapılır.

Simpleks metodundan istifadə edərək problemin həlli nümunəsi

Misal 26.1

Simpleks metodundan istifadə edərək problemi həll edin:

Həlli:

Problemi kanonik formaya gətiririk.

Bu məqsədlə ildə sol tərəf Birinci bərabərsizlik məhdudiyyəti üçün +1 əmsalı olan əlavə x 6 dəyişənini təqdim edirik. Dəyişən x 6 məqsəd funksiyasına sıfır əmsalı ilə daxil edilir (yəni daxil edilmir).

Biz əldə edirik:

İlkin dəstək həllini tapırıq. Bunun üçün sərbəst (həll edilməmiş) dəyişənləri sıfıra bərabərləşdiririk x1 = x2 = x3 = 0.

alırıq istinad həlli X1 = (0,0,0,24,30,6) vahid əsaslı B1 = (A4, A5, A6).

Hesablayırıq vektor parçalanmalarının təxminləri düstura uyğun olaraq istinad həlli əsasında şərtlər:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - əsas dəyişənlər üçün məqsəd funksiyasının əmsallarının vektoru
• X k = (x 1k, x 2k, ..., x mk) - istinad həllinin əsasına görə müvafiq A k vektorunun genişlənmə vektoru
• C k - x k dəyişəni üçün məqsəd funksiyasının əmsalıdır.

Baza daxil edilmiş vektorların təxminləri həmişə sıfıra bərabərdir. İstinad həlli, genişlənmə əmsalları və istinad həlli əsasında şərtlər vektorlarının genişlənməsinin təxminləri yazılır. simpleks cədvəli:

Cədvəlin yuxarı hissəsində təxminlərin hesablanmasının asanlığı üçün məqsəd funksiyasının əmsalları yazılır. “B” birinci sütununda istinad həllinin əsasına daxil olan vektorlar yazılır. Bu vektorların yazılma sırası məhdudiyyət tənliklərində icazə verilən naməlumların nömrələrinə uyğun gəlir. “C b” cədvəlinin ikinci sütununda əsas dəyişənlər üçün məqsəd funksiyasının əmsalları eyni ardıcıllıqla yazılır. At düzgün yer Baza daxil olan vahid vektorların qiymətləndirilməsinin “C b” sütununda məqsəd funksiyasının əmsalları həmişə sıfıra bərabərdir.

IN son sətirΔ k təxminləri olan cədvəllərdə "A 0" sütununda Z(X 1) istinad həllində məqsəd funksiyasının dəyərləri yazılır.

İlkin dəstək həlli optimal deyil, çünki maksimum problemdə A 1 və A 3 vektorları üçün Δ 1 = -2, Δ 3 = -9 qiymətləndirmələri mənfidir.

Dəstək həllinin təkmilləşdirilməsi teoreminə görə, əgər maksimum problemdə ən azı bir vektor mənfi qiymətə malikdirsə, onda məqsəd funksiyasının dəyərinin daha böyük olacağı yeni dəstək həlli tapa bilərsiniz.

İki vektordan hansının məqsəd funksiyasında daha böyük artıma səbəb olacağını müəyyən edək.

Məqsəd funksiyasının artımı düsturla tapılır: .

Düsturdan istifadə edərək birinci və üçüncü sütunlar üçün θ 01 parametrinin dəyərlərini hesablayırıq:

l = 1 üçün θ 01 = 6, l = 1 üçün θ 03 = 3 alırıq (Cədvəl 26.1).

Birinci vektor ΔZ 1 = - 6*(- 2) = 12, üçüncü vektor ΔZ 3 = - 3*(- 9) = 27-ni bazaya daxil edərkən məqsəd funksiyasının artımını tapırıq.

Nəticə etibarilə, optimal həllə daha sürətli yanaşmaq üçün A6 əsasının birinci vektoru əvəzinə istinad həllinin bazasına A3 vektorunu daxil etmək lazımdır, çünki birinci sətirdə θ 03 parametrinin minimumuna nail olunur ( l = 1).

X13 = 2 elementi ilə İordaniya çevrilməsini həyata keçiririk, B2 = (A3, A4, A5) əsası ilə ikinci istinad həllini X2 = (0,0,3,21,42,0) alırıq. (Cədvəl 26.2)

Bu həll optimal deyil, çünki A2 vektoru mənfi qiymətə malikdir Δ2 = - 6. Həllini təkmilləşdirmək üçün istinad həllinin əsasına A2 vektorunu daxil etmək lazımdır.

Bazadan alınan vektorun sayını təyin edirik. Bunun üçün ikinci sütun üçün θ 02 parametrini hesablayırıq, l = 2 üçün 7-yə bərabərdir. Deməli, bazisdən ikinci bazis vektorunu A4 alırıq. X 22 = 3 elementi ilə İordaniya çevrilməsini həyata keçiririk, üçüncü istinad həllini əldə edirik X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Cədvəl 26.3).

Bu həll yeganə optimaldır, çünki bazaya daxil edilməyən bütün vektorlar üçün qiymətləndirmələr müsbətdir

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Cavab: max Z(X) = 201-də X = (0.7,10,0.63).

İqtisadi təhlildə xətti proqramlaşdırma metodu

Xətti proqramlaşdırma üsuluən optimalını əsaslandırmağa imkan verir iqtisadi qərar istehsalda istifadə olunan resurslara (əsas fondlar, materiallar, əmək resursları) aid ciddi məhdudiyyətlər şəraitində. İqtisadi təhlildə bu metoddan istifadə əsasən təşkilatın fəaliyyətinin planlaşdırılması ilə bağlı problemləri həll etməyə imkan verir. Bu üsul optimal çıxış səviyyələrini, eləcə də ən çox istiqamətləri müəyyən etməyə kömək edir səmərəli istifadə təşkilat üçün mövcud olan istehsal resursları.

Bu üsuldan istifadə edərək, ekstremal dəyərləri, yəni funksiyaların maksimum və minimumunu tapmaqdan ibarət olan ekstremal problemlər həll edilir. dəyişənlər.

Bu müddət sistemin həllinə əsaslanır xətti tənliklər təhlil edilən iqtisadi hadisələrin xətti, ciddi şəkildə bağlı olduğu hallarda funksional asılılıq. Xətti proqramlaşdırma metodu müəyyən məhdudlaşdırıcı amillərin mövcudluğunda dəyişənləri təhlil etmək üçün istifadə olunur.

Xətti proqramlaşdırma metodundan istifadə edərək sözdə nəqliyyat problemini həll etmək çox yaygındır. Bu tapşırığın məzmunu əməliyyatla əlaqədar çəkilən xərcləri minimuma endirməkdən ibarətdir nəqliyyat vasitələri nəqliyyat vasitələrinin sayı, onların daşıma qabiliyyəti, istismar müddəti ilə bağlı mövcud məhdudiyyətlər altında və texniki xidmətə ehtiyac olduqda maksimum miqdar müştərilər.

Bundan başqa, bu üsul planlaşdırma məsələlərinin həllində geniş istifadə olunur. Bu vəzifə, həm bu heyətin üzvləri, həm də təşkilatın müştəriləri üçün ən məqbul olan müəyyən bir təşkilatın işçiləri üçün iş vaxtının belə bölüşdürülməsindən ibarətdir.

Bu vəzifə mövcud işçi heyətin sayına, habelə iş vaxtı fonduna məhdudiyyətlər şəraitində xidmət göstərilən müştərilərin sayını maksimuma çatdırmaqdır.

Beləliklə, xətti proqramlaşdırma üsulu yerləşdirmə və istifadə təhlilində kifayət qədər geniş yayılmışdır. müxtəlif növlər resursları, habelə təşkilatların fəaliyyətinin planlaşdırılması və proqnozlaşdırılması prosesində.

Buna baxmayaraq, riyazi proqramlaşdırma, aralarındakı əlaqə xətti olmayan iqtisadi hadisələrə də tətbiq edilə bilər. Bu məqsədlə qeyri-xətti, dinamik və qabarıq proqramlaşdırma metodlarından istifadə etmək olar.

Qeyri-xətti proqramlaşdırma məqsəd funksiyasının və ya məhdudiyyətlərin və ya hər ikisinin qeyri-xətti təbiətinə əsaslanır. Bu şərtlərdə məqsəd funksiyasının formaları və məhdudiyyətlərin bərabərsizlikləri müxtəlif ola bilər.

Qeyri-xətti proqramlaşdırma iqtisadi təhlildə, xüsusən də təşkilatın fəaliyyətinin səmərəliliyini ifadə edən göstəricilər ilə bu fəaliyyətin həcmi, istehsal xərclərinin strukturu, bazar şəraiti və s. arasında əlaqə qurarkən istifadə olunur.

Dinamik proqramlaşdırma qərar ağacının qurulmasına əsaslanır. Bu ağacın hər bir təbəqəsi nəticələri müəyyən etmək üçün bir mərhələ rolunu oynayır əvvəlki qərar və bu həll üçün səmərəsiz variantları aradan qaldırmaq. Beləliklə, dinamik proqramlaşdırmaçoxpilləli, çoxpilləli xarakterə malikdir. Bu tip proqramlaşdırma tapmaq üçün iqtisadi təhlildə istifadə olunur optimal variantlar təşkilatın həm indi, həm də gələcəkdə inkişafı.

Konveks proqramlaşdırma qeyri-xətti proqramlaşdırma növüdür. Bu tip proqramlaşdırma təşkilatın fəaliyyətinin nəticələri ilə onun xərcləri arasındakı əlaqənin qeyri-xətti xarakterini ifadə edir. Konveks (aka konkav) proqramlaşdırma qabarıq məqsəd funksiyalarını və qabarıq məhdudiyyət sistemlərini (nöqtələr) təhlil edir məqbul dəyərlər). Konveks proqramlaşdırma, təsərrüfat fəaliyyətinin təhlilində xərclərin minimuma endirilməsi məqsədi ilə, konkav proqramlaşdırma isə təhlil edilən göstəricilərə əks istiqamətdə təsir göstərən amillərin fəaliyyətinə mövcud məhdudiyyətlər zamanı maksimum gəlir əldə etmək məqsədi ilə istifadə olunur. Nəticə etibarilə, nəzərdən keçirilən proqramlaşdırma növləri ilə qabarıq məqsəd funksiyaları minimuma endirilir, konkav məqsəd funksiyaları isə maksimumlaşdırılır.

Xətti proqramlaşdırma problemləri. O, nəzərdən keçirilən prosesi xarakterizə edən ardıcıl tikintidədir. Həlli üç əsas mərhələyə bölünür: dəyişənlərin seçilməsi, məhdudiyyətlər sisteminin qurulması və məqsəd funksiyasının axtarışı.

Bu bölgü əsasında məsələnin şərtini aşağıdakı kimi ifadə etmək olar: Z(X) = f(x1, x2, … ,xn) → max (min) məqsəd funksiyasının ekstremumu və uyğun dəyişənlər, əgər məlumdursa, onların məhdudiyyətlər sistemini təmin edin: Φ_i ( x1, x2, … ,xn) = 0 üçün i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) i = k+1, k+ üçün 0 2, …, m.

Məhdudiyyətlər sistemi kanonik formaya gətirilməlidir, yəni. xətti tənliklər sisteminə, burada dəyişənlərin sayı daha çox nömrə tənliklər (m > k). Bu sistemdə, şübhəsiz ki, digər dəyişənlər vasitəsilə ifadə edilə bilən dəyişənlər olacaq və əgər belə deyilsə, onda onlar süni şəkildə təqdim edilə bilər. Bu halda birincilər əsas və ya adlanır süni əsas, ikincilər isə pulsuzdur.

Simpleks metodunu nəzərdən keçirmək daha rahatdır konkret misal. Qoy verilsin xətti funksiya f(x) = 6x1 + 5x2 + 9x3 və məhdudiyyətlər sistemi: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20. Tapmaq lazımdır maksimum dəyər f(x) funksiyaları.

Həlli Birinci mərhələdə, verilmiş məhdudiyyətlər sistemini təmin etməli olan tənliklər sisteminin ilkin (istinad) həllini mütləq ixtiyari şəkildə təyin edin. IN bu halda süni tətbiqi tələb olunur, yəni. əsas dəyişənlər x4, x5 və x6 aşağıdakı kimi: 5x1 + 2x2 + 3x3 + x4 = 25 x1 + 6x2 + 2x3 + x5 = 20 4x1 + 3x3 + x6 = 18;

Göründüyü kimi, qeyri-mənfi kəmiyyətlər olan x4, x5, x6 əlavə olunan dəyişənlər sayəsində bərabərsizliklər bərabərliyə çevrilmişdir. Beləliklə, sistemi öz kanonik formasına gətirdiniz. Dəyişən x4 əmsalı 1 olan birinci tənliyə, əmsalı 0 olan ikinci tənliyə də x5, x6 dəyişənləri və bazisin tərifinə uyğun gələn müvafiq tənliklər üçün də eynidir.

Siz sistemi hazırladınız və ilkin istinad həllini tapdınız – X0 = (0, 0, 0, 25, 20, 18). İndi dəyişənlərin əmsallarını və tənliklərin sərbəst şərtlərini (“=” işarəsinin sağındakı rəqəmlər) sonrakı hesablamaları optimallaşdırmaq üçün cədvəl şəklində təqdim edin (şəklə bax).

Simpleks metodunun mahiyyəti bu cədvəli L sətirindəki bütün ədədlərin mənfi olmayan qiymətlər olacağı bir forma gətirməkdir. Əgər bunun qeyri-mümkün olduğu ortaya çıxarsa, o zaman sistemin ümumiyyətlə optimal həlli yoxdur. Başlamaq üçün ən çoxunu seçin minimum element bu xəttin -9-dur. Nömrə üçüncü sütundadır. Uyğun x3 dəyişənini əsas dəyişənə çevirin. Bunu etmək üçün xətti 3-ə bölün ki, xana 1 ilə bitsin.

İndi hüceyrələrə ehtiyacınız var və 0-a çevirin. Bunu etmək üçün üçüncü sıranın müvafiq nömrələrindən 3-ə çıxın. İkinci cərgənin elementlərindən - üçüncünün elementləri 2-yə vurulur. Və nəhayət, L sətirinin elementləri - (-9) ilə vurulur. Siz ikinci istinad həllini əldə etdiniz: f(x) = L = 54, x1 = (0, 0, 6, 7, 8, 0).

Optimallaşdırma problemlərinin həlli üsullarından biri ( adətən minimum və ya maksimumun tapılması ilə əlaqələndirilir) xətti proqramlaşdırma adlanır. Simpleks metodu xətti proqramlaşdırma məsələlərinin həlli üçün bütün alqoritmlər və metodlar qrupu daxildir. Mənbə məlumatlarının qeyd edilməsini və onların xüsusi cədvəldə yenidən hesablanmasını nəzərdə tutan bu üsullardan biri adlanır cədvəlli simpleks üsulu .

Həll nümunəsindən istifadə edərək cədvəlli simplex metodunun alqoritmini nəzərdən keçirək istehsal vəzifəsi, təmin edən bir istehsal planı tapmaq üçün gəlir maksimum mənfəət.

Simpleks metod problemi üçün məlumat daxil edin

Müəssisə 3 maşında emal edərək 4 növdə məhsul istehsal edir.

Maşınlarda məhsulların emalı üçün vaxt standartları (dəqiqə/dəqiqə) A matrisi ilə müəyyən edilir:

Maşının işləmə vaxtı fondu (dəq.) B matrisində göstərilmişdir:

Hər bir məhsul vahidinin satışından əldə edilən mənfəət (RUB/parça) C matrisi ilə verilir:

İstehsal tapşırığının məqsədi

Müəssisənin mənfəətini maksimuma çatdıracaq bir istehsal planı tərtib edin.

Cədvəl Simpleks metodundan istifadə etməklə məsələnin həlli

(1) X1, X2, X3, X4 ilə hər növ məhsulun planlaşdırılmış sayını işarə edək. Sonra istədiyiniz plan: ( X1, X2, X3, X4)

(2) Plan məhdudiyyətlərini tənliklər sistemi şəklində yazaq:

(3) Sonra hədəf mənfəət:

Yəni istehsal planının yerinə yetirilməsindən əldə edilən gəlir maksimum olmalıdır.

(4) Yaranan şərti ekstremum problemini həll etmək üçün bərabərsizliklər sistemini ona əlavə qeyri-mənfi dəyişənlər daxil etməklə xətti tənliklər sistemi ilə əvəz edirik ( X5, X6, X7).

(5) Gəlin aşağıdakıları qəbul edək istinad planı:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Məlumatları daxil edək simpleks cədvəli:

Sonuncu sətirdə məqsəd funksiyasının əmsallarını və onun dəyərinin özünü əks işarə ilə daxil edirik;

(7) Son sətirdə seçin ən böyük (modulu) mənfi ədəddir.

Gəlin hesablayaq b = N / Seçilmiş_sütunun elementləri

b-nin hesablanmış dəyərləri arasından seçirik ən azı.

Seçilmiş sütun və sıranın kəsişməsi bizə həlledici element verəcəkdir. Əsası həlledici elementə uyğun dəyişənə dəyişdiririk ( X5 - X1).

• Həlledici elementin özü 1-ə çevrilir.
• Qətnamə xəttinin elementləri üçün – a ij (*) = a ij / RE ( yəni hər bir elementi həlledici elementin qiymətinə bölüb yeni məlumatlar əldə edirik).
• Qətnamə sütununun elementləri üçün onlar sadəcə sıfıra sıfırlanır.
• Cədvəlin qalan elementlərini düzbucaqlı qaydasından istifadə edərək yenidən hesablayırıq.

a ij (*) = a ij – (A * B / RE)

Gördüyünüz kimi, yenidən hesablanan cari xananı və həlledici elementi olan xananı götürürük. Onlar düzbucaqlının əks künclərini təşkil edirlər. Sonra, bu düzbucağın digər 2 küncünün xanalarından dəyərləri çarpırıq. Bu iş ( A * B) həlledici elementə bölün ( RE). Və yenidən hesablanan cari xanadan çıxın ( a ij) nə oldu. Yeni bir dəyər alırıq - a ij (*).

(9) Son sətri yenidən yoxlayın ( c) açıqdır mənfi ədədlərin olması. Əgər onlar yoxdursa, optimal plan tapılıb, gedin son mərhələ problemin həlli. Əgər varsa, plan hələ optimal deyil və simpleks cədvəlini yenidən hesablamaq lazımdır.

Son sətirdə yenə mənfi ədədlər olduğundan, hesablamaların yeni iterasiyasına başlayırıq.

(10) Sonuncu sətirdə heç bir mənfi element olmadığı üçün bu, optimal istehsal planını tapdığımız deməkdir! Məhz: "Əsas" sütununa keçən məhsulları istehsal edəcəyik - X1 və X2. Biz hər bir məhsul vahidinin istehsalından qazancı bilirik ( matrisi C). 1 və 2-ci məhsulların tapılmış istehsal həcmini 1 ədədə görə mənfəətlə vurmaq qalır, son nəticəni alırıq ( maksimum! ) müəyyən istehsal planı üzrə mənfəət.

CAVAB:

X1 = 32 əd., X2 = 20 əd., X3 = 0 əd., X4 = 0 əd.

P = 48 * 32 + 33 * 20 = 2,196 rub.

Galyautdinov R.R.

© Materialın surətinə yalnız birbaşa hiperlink olduqda icazə verilir