Qərar vermək probleminin ümumi ifadəsi

Cədvəl 3



Cədvəl 4

Üçüncü xəttin elementlərini tapmağın iki yolunun olması  hesablamaların düzgünlüyünü idarə etməyə imkan verir.

Düsturdan (27) belə çıxır ki, bir baza planından digərinə keçərkən , rəqəmi mütləq dəyərdə maksimum olan j  indeksinə malik olan vektoru bazaya daxil etmək ən məqsədəuyğundur . Bununla birlikdə, hesablama prosesini asanlaşdırmaq üçün gələcəkdə mənfi ədədlərin maksimum mütləq dəyəri əsasında bazaya daxil edilən vektor müəyyən ediləcək . Bir neçə belə ədəd varsa, bu rəqəmlərlə təyin olunan ədədlərin maksimumu ilə eyni indeksi olan bir vektoru əsas olaraq təqdim edəcəyik.

Beləliklə, bir əsas plandan digərinə keçid bir sadə cədvəldən digərinə keçməyə endirilir. Yeni simpleks cədvəlinin elementləri həm təkrarlanan (25) - (28) düsturların köməyi ilə, həm də onlardan dərhal gələn qaydalara əsasən hesablana bilər. Bu qaydalar aşağıdakı kimidir.

Baza daxil olan vektorların sütunlarında, eyni adlı vektorların satır və sütunlarının kəsişməsində olanlar qoyulur və bu sütunların bütün digər elementlərinin sıfır olduğu qəbul edilir.

İstiqamətini elementləri  və  əsasında daxil vektor qeyd olan yeni simpleks masa xəttində, həll element ölçüsü onları bölərək orijinal masa eyni xətt elementləri əldə edilir.  Giriş vektorunun satırındakı sütunda dəyər qoyulur  , burada k - giriş vektorunun indeksidir.

Vektorun sütunlarının qalan elementləri  və  yeni simpleks cədvəli üçbucaq qaydasına əsasən hesablanır. Bu elementlərdən birini hesablamaq üçün üç ədəd tapılır:

1) yeni simpleks cədvəlinin istədiyiniz elementi yerinə orijinal sadə cədvəldə duran ədəd;

2) yeni simpleks cədvəlinin istədiyiniz elementinin yerləşdiyi xəttin kəsişməsindəki orijinal simpleks cədvəlindəki rəqəm və əsasda daxil edilən vektora uyğun sütun;

3) tələb olunan elementin yerləşdiyi sütunun kəsişməsindəki yeni simpleks cədvəlində duran nömrə və bazaya yeni daxil edilmiş vektor cərgəsi (yuxarıda qeyd edildiyi kimi, bu sətir orijinal sadə sətrin sətrindən alınmışdır) cədvəl, elementlərini həll elementinə bölməklə).

Bu üç ədəd iki ucu orijinal simpleks cədvəlindəki rəqəmlərə, üçüncüsü isə yeni simpleks cədvəlindəki rəqəmə uyğun gələn bir növ üçbucaq meydana gətirir. Yeni simpleks cədvəlinin tələb olunan elementini təyin etmək üçün birinci və üçüncü ədədin məhsulu çıxılır.

Yeni simpleks cədvəlini doldurduqdan sonra  -ci cərgənin elementləri skan edilir . Hamısı  budursa, yeni təməl xətt optimaldır. Göstərilən nömrələr arasında mənfi ədədlər varsa, yuxarıda təsvir olunan hərəkətlərin ardıcıllığından istifadə edərək yeni bir istinad planı tapılır. Bu proses ya problemin optimal planı əldə olunana, ya da qeyri -müəyyənliyi müəyyən olunana qədər davam etdirilir.

Xətti proqramlaşdırma probleminə həll taparkən, bu problemin dəstək planları olduğunu və hər bir planın pisləşmədiyini güman etdik. Problemin pozulmuş ilkin planları varsa, təkrarlamalardan birində əsas planın bir və ya daha çox dəyişənləri sıfıra bərabər ola bilər. Beləliklə, bir baza planından digərinə keçərkən, funksiyanın dəyəri eyni qala bilər. Üstəlik, funksiya bir neçə təkrarlama üçün dəyərini saxladıqda mümkündür və eyni zamanda orijinal əsasına qayıtmaq mümkündür. İkinci vəziyyətdə, ümumiyyətlə bir döngənin meydana gəldiyi deyilir . Ancaq praktiki problemləri həll edərkən, bu hal çox nadirdir, buna görə də bunun üzərində dayanmayacağıq.

Beləliklə, simpleks metodundan istifadə edərək optimal planı tapmaq aşağıdakı addımları əhatə edir:

1. Plana istinad tapın.

2. Simpleks cədvəli yaradın.

3. Ən azı bir mənfi ədədin olub olmadığını öyrənin  . Əks təqdirdə, tapılan əsas plan optimaldır. Nömrələr arasında mənfi ədədlər varsa  , ya problemin həll olunmayacağını təyin edər, ya da yeni bir istinad planına keçirlər.

4. Sütun və satır bələdçilərini tapın.  İstiqamət sütunu mütləq dəyərdə ən böyük mənfi rəqəmlə təyin olunur və istiqamət sətri vektor sütun komponentlərinin müsbət istiqamət sütun komponentlərinə nisbətlərinin minimumudur  .

5. By düsturlar (25) - (28), yeni bir sened planı müsbət komponentləri, istiqamətini genişləndirilməsi əmsalları Pj yeni əsasında və sayı istiqamətini baxımından  , ki, müəyyən  . Bütün bu ədədlər yeni bir sadə cədvəldə qeyd olunur.

6. Tapılan istinad planını optimallıq üçün yoxlayın. Plan optimal deyilsə və yeni bir başlanğıc plana keçmək lazımdırsa, 4 -cü mərhələyə qayıdın və optimal plan əldə olunarsa və ya həll olunmazsa, problemin həlli prosesi başa çatır.