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

Cədvəl 9

i	Əsas	C b	P 0	doqquz	on	16	0	0	0
				S 1	S 2	S 3	səh 4	səh 5	R 6
1 2 3 4 1 2 3 4 1 2 3 4	S 4 səh 5 səh 6 S 4 səh 3 səh 6 S 2 səh 3 səh 6	0 0 0 0 16 0 0 16 0	360 192 180 0 72 24 108 384 səkkiz iyirmi 96 400	on səkkiz 6 5 -doqquz doqquz 3/4 11/4 3 1 1/4 5/4 5	15 4 3 -on doqquz 1/2 3/2 -2 1 0 0 0	12 səkkiz 3 -16 0 1 0 0 0 1 0 0	1 0 0 0 1 0 0 0 1/9 -1/18 -1/6 2/9	0 1 0 0 -3/2 1/8 -3/8 2 -1/6 5/24 -1/8 5/3	0 0 1 0 0 0 1 0 0 0 1 0

Misal 10.

Şərtlər altında bir funksiyanın maksimumunu tapın

Həll. Problemin tənliklər sistemini vektor şəklində yazırıq:

harada

Vektorlar arasında üç vahid vektor olduğu üçün bu plan üçün istinad planı birbaşa tapıla bilər. Bu plan X = (0, 0, 20, 24; 0; 18). Simpleks cədvəli yaradın (Cədvəl 10) və verilən bazanın optimal olub olmadığını yoxlayın. 

Cədvəl 10

i	Əsas	C b	P 0	2	-6	0	0	5	0
				S 1	S 2	S 3	səh 4	səh 5	R 6
1 2 3 4	səh 3 S 4 səh 6	0 0 0	20 24 18 0	-2 -1 3 -2	1 -2 -1 6	1 0 0 0	0 1 0 0	1 3 -12 -5	0 0 1 0

Cədvəldən göründüyü kimi. 10, orijinal istinad planı optimal deyil. Buna görə də yeni bir bazaya keçirik. Bunu etmək olar, çünki 4 -cü cərgəsində mənfi ədədlər olan P ₁ və p ₅ vektorlarının sütunlarında müsbət elementlər var. Yeni bir başlanğıc planına keçmək üçün p ₅ vektorunu bazaya daxil edirik və p ₄ vektorunu əsasdan xaric edirik . II təkrarlama üçün bir cədvəl tərtib edirik.

Cədvəl 11

i	Əsas	C b	P 0	2	-6	0	0	5	0
				S 1	S 2	S 3	səh 4	səh 5	R 6
1 2 3	səh 3 S 5 səh 6	0 5 0	12 səkkiz 114 40	-5/3 -1/3 -1 -11/3	5/3 -2/3 -doqquz 8/3	1 0 0 0	-1/3 1/3 4 5/3	0 1 0 0	0 0 1 0

Cədvəldən göründüyü kimi. 11 -də , problemin yeni təməl planı optimal deyil, çünki P ₁ vektorunun sütununun 4 -cü cərgəsində mənfi rəqəm -11/3 var. Bu vektorun sütununda müsbət elementlər olmadığı üçün bu problemin optimal dizaynı yoxdur.

 

 

 

 

Misal 1

Şirkət iki növ boya istehsal edir və satır: daxili və xarici işlər üçün. Boya istehsalı üçün iki ilkin A və B məhsullarından istifadə olunur. A və B məhsullarının 1 tona uyğun boyalar üçün istehlakı və bu məhsulların anbardakı ehtiyatları cədvəldə göstərilmişdir:

 

Orijinal	Məhsul istehlakı (1 ton boyada tonla)		Üçün məhsul ehtiyatı
məhsul	daxili işlər üçün boya	xarici boya	stok (ton)
A	1	2	3
B	3	1	3

 

1 ton daxili boyanın satış qiyməti 2000 rubl, xarici işlər üçün boya ton üçün 1000 rubla satılır. Maksimum gəlir əldə etmək üçün müəssisə tərəfindən hər növdən nə qədər boya istehsal edilməli olduğunu müəyyən etmək tələb olunur .

Aşağıdakı mərhələlərdən ibarət olan simplex üsulu ilə bu problemin addım-addım həllini nəzərdən keçirək: 1. Məsələnin riyazi modelinin tərtib edilməsi.2. Problemin standart bir formaya salınması, yəni obyektiv funksiyanın və əsas dəyişənlərin sərbəst dəyişənlər baxımından ifadəsi. 3. İlk simpleks cədvəlinin tərtib edilməsi . 4. ODR -dən kənara çıxmadan "+" işarəsi ilə obyektiv funksiyaya daxil olan sərbəst dəyişənlərin maksimum artımı.  

 

I. Məsələnin riyazi modelinin hazırlanması.

1) Dəyişən vəzifələr.

İşarə edək: x ₁ - üçün istehsal olunan boya miqdarı  

                           daxili işlər;

                     x ₂ - müvafiq boya miqdarı

                           açıq iş üçün.

2) Vəzifə dəyişənlərinin təmin etməli olduğu məhdudiyyətlər :

x ₁ , x ₂ 0; 

məhsul istehlakı ilə A: x ₁ + 2x ₂ 3;    

B məhsulu istehlakı ilə: 3x ₁ + x ₂ 3;   

Son iki bərabərsizliyin sol tərəfində A və B məhsullarının xərcləri, bərabərsizliklərin sağ tərəflərində isə bu məhsulların ehtiyatları qeydə alınır.

3) Tapşırığın obyektiv funksiyası.

Boya satışından əldə olunan gəliri (min rubla) Z ilə ifadə edirik, sonra problemin obyektiv funksiyası belə yazılır:

Z = 2x ₁ + x ₂ ,

beləliklə, vəzifə məhdudiyyətlərə tabe olaraq maksimum Z = 2x ₁ + x ₂ tapmaqdır :

x ₁ + 2x ₂ 3 (A)    

3x ₁ + x ₂ 3 (B)    

x ₁ , x ₂ 0. 

Məsələnin x ₁ və x ₂ dəyişənləri obyektiv funksiyaya və problemin məhdudiyyətlərinə xətti olaraq daxil olduğu üçün müvafiq optimallaşdırma problemi xətti proqramlaşdırma problemi (LP) adlanır.

2 Problemin standart formaya salınması.

(A) və (B) bərabərsizliklərinin sol tərəfində x ₃ və x ₄ köməkçi (balans) dəyişənlərini təqdim edərək, məhdudiyyətləri tənliklər şəklində yazırıq:

x ₁ + 2x ₂ + x ₃ = 3 (A)   

3x ₁ + x ₂ + x ₄ = 3 (B)   

Problemi standart formaya endirərkən Z = 2x ₁ + x ₂ məqsəd funksiyası belə yazılır:

Z - 2x ₁ - x ₂ = 0 (C)  

2) İlk sadə cədvəlin tərtib edilməsi.

Simplex cədvəli, x ₁ , x ₂ , x ₃ , x ₄ əmsallarından və problemin tənliyinin məhdudiyyətlərinin sağ tərəfindəki rəqəmlərdən ibarətdir: birinci sətir (A) tənliyinin elementlərini ehtiva edir. , ikincisi - (B). Simpleks cədvəlinin son sətrində məqsəd funksiyasının (C) əmsalları və sağ tərəfi var. Beləliklə, simpleks cədvəlində iki sıra əmsallar (problem məhdudiyyətlərinin sayına görə) və obyektiv funksiyanın bir sıra əmsalları var. Simpleks cədvəlindəki sütunların sayı problem dəyişənlərinin sayına və sağ tərəflərin bir sütununa bərabərdir (b):

 

X 1	X 2	X 3	X 4	b
1	2	1	0	3
3	1	0	1	3
-2	-1	0	0	0

 

Katsayı sütunlarının bir vahiddən və sıfırdan ibarət olduğu dəyişənlərə əsas deyilir (Verilən nümunədə x ₃ və x ₄ əsas dəyişənlərdir). Əsas dəyişənlərin sayı problem məhdudiyyətlərinin sayına bərabərdir və sadə çevrilmə zamanı dəyişmir. Qalan dəyişənlərə sərbəst deyilir (x ₁ və x ₂ ).

Simpleks cədvəli bir tənlik sisteminə xüsusi bir həll təyin edir:

x ₁ + 2x ₂ + x ₃ = 3 (A)

3x ₁ + x ₂ + x ₄ = 3 (A)

 

burada sərbəst dəyişənlər sıfıra bərabərdir (x ₁ = 0, x ₂ = 0) və əsas dəyişənlər müvafiq sətirlərin sağ tərəflərinə bərabərdir (x ₃ = 3, x ₄ = 3).

Z məqsəd funksiyasının dəyəri həmişə cədvəlin sağ alt küncündəki rəqəmə bərabərdir (Z = 2 * 0 + 1 * 0 = 0). Birinci sadə cədvəl LP probleminin ilkin həllinə uyğundur (x ₁ = 0, x ₂ = 0, x ₃ = 3, x ₄ = 3, Z = 0). Bu həll Şəkil 3 -də ABCD -nin çoxbucaqlı həllinin A nöqtəsinə uyğundur.  

4. Simpleks metodu, mümkün olan həllərin çoxbucağının ucları boyunca ardıcıl hərəkətdən ibarətdir. Hər bir təpə, sadə bir çevrilmə istifadə edərək əvvəlkindən əldə edilən öz sadə cədvəlinə uyğundur.

As həll sütun, onun əmsalı obyektiv funksiyası istiqamətində mənfi və modulus ən böyük sütun edir. Bu sadə cədvəldəki məqsəd funksiyasının sətrində mənfi əmsallar yoxdursa, LP məsələsinin həlli başa çatır və simpleks cədvəli, Z məqsəd funksiyasının maksimum dəyərini aldığı problemin həllini təyin edir.

Çözünürlük sırası, b sütununun əmsallarının qətnamə sütununun müvafiq əmsallarına nisbətləri ilə müəyyən edilir. Bu nisbətin minimal olduğu sıra həll olunacaq . Eyni zamanda, nisbətlər həll sütununun sıfır və mənfi əmsalları üçün hesablanmır.

İlk sadə cədvəl üçün həll sütunu birinci sütundur (pulsuz dəyişən x ₁ bazaya çevriləcək). B sütununun əmsallarının həll sütununun əmsallarına nisbətləri arasında: 3/1 və 3/3, 3/3 nisbəti minimum olacaq: ikinci sıra həll sırası olacaq (əsas dəyişən x ₄₎ pulsuza çevriləcək).

 

X 1	X 2	X 3	X 4	b
1       3	2 1	1 0	0 1	3 3
-2	-1	0	0	0

 

 

Həll sütunu ilə həll xəttinin kəsişməsində həll elementi var .

Simpleks çevrilməsinin vəzifəsi həll elementinin yerinə birini almaq və həll sütununun bütün digər elementlərini sıfır etməkdir.

Bu halda, simpleks cədvəlinin satırları ilə yalnız iki əməliyyata icazə verilir:

 a) həll olunan sətir istənilən saya bölünə (vurula) bilər;

 b) hər hansı bir sətirdən həll xəttinin elementlərini çıxara bilərsiniz və ya hər hansı bir sətrə həll xəttinin elementlərini əlavə edə bilərsiniz.

 İlk simpleks cədvəlini dəyişdirək.

1) Həll xəttinin elementlərini 3 -ə bölün:

 

X 1	X 2	X 3	X 4	b
1 1	2 1/3	1 0	0 1/3	3 1
-2	-1	0	0	0

 

2) İkinci sətrin elementlərini birinci sətrin elementlərindən çıxarın:

 

X 1	X 2	X 3	X 4	b
0 1	5/3 1/3	1 0	-1/3 1/3	2 1
-2	-1	0	0	0

 

3. Həll xəttinin elementlərini əvvəllər ikiyə vuraraq üçüncü sətrin elementlərinə əlavə edin:

 

X 1	X 2	X 3	X 4	b
0 1	5/3 1/3	1 0	-1/3 1/3	2 1
0	-1/3	0	2/3	2

 

 Dönüşüm tamamlandı. Nəticədə ortaya çıxan sadə cədvəl aşağıdakı həllə uyğundur:

əsas dəyişənlər: x ₁ = 1, x ₃ = 2

sərbəst dəyişənlər: x ₂ = 0, x ₄ = 0.

X ₁ = 1, x ₂ = 0 koordinatları olan nöqtə D nöqtəsidir (bax. Şəkil 3). Obyektiv funksiya dəyəri Z (D) = 2.

Obyektiv funksiya əmsallarının cərgəsində mənfi əmsal (ikinci sütunda -1/3) olduğu üçün çevrilmə davam edir. İkinci sütun həll olunur (x ₂ sərbəst dəyişən əsasa çevrilir), əlaqələr arasında minimum:  və  birinci nömrədir, buna görə birinci sıra həll sətiridir (əsas dəyişən x ₃ pulsuz olaraq tərcümə olunur) bir).

 

X 1	X 2	X 3	X 4	b
0 1	5/3 1/3	1 0	-1/3 1/3	2 1
0	-1/3	0	2/3	2

 

 

Simpleks çevrilməsini həyata keçirdikdən sonra əldə edirik:

 

 

X 1	X 2	X 3	X 4	b
0 1	1 0	3/5 0	-1/5 1/3	6/5 3/5
0	0	1/5	3/5	12/5

 

Obyektiv funksiya əmsalları sırasında mənfi əmsallar olmadığından problemin həlli başa çatdı.

 Optimal həll aşağıdakı kimidir:

  əsas dəyişənlər: x ₁ * = 3/5 = 0.6; x ₂ * = 6/5 = 1.2;

  sərbəst dəyişənlər: x ₃ * = 0; x ₄ * = 0.

 X ₁ * = 0.6 və x ₂ * = 1.2 koordinatları olan nöqtə C nöqtəsidir (bax. Şəkil 3)

 Maksimum gəlirin dəyəri (məqsəd funksiyası):

Z * (C) = 12/5 = 2.4