Bəyəndinizmi? Əlfəcinlərə əlavə edin

Simpleks metodundan istifadə edərək problemlərin həlli: onlayn nümunələr

Tapşırıq 1.Şirkət iki ölçüdə vanna otağı rəfləri istehsal edir - A və B. Satış agentləri həftədə bazarda 550-ə qədər rəf satıla biləcəyini təxmin edirlər. Hər bir A tipli rəf üçün 2 m2 material, B tipli hər bir rəf üçün isə 3 m2 material tələb olunur. Şirkət həftədə 1200 m2-ə qədər material qəbul edə bilər. A tipli bir rəf hazırlamaq üçün 12 dəqiqə maşın vaxtı, B tipli bir rəf hazırlamaq üçün isə 30 dəqiqə tələb olunur; Maşın həftədə 160 saat istifadə edilə bilər. A tipli rəflərin satışından əldə edilən mənfəət 3 pul vahidi, B tipli rəflərdən isə 4 pul vahidi olduqda. ədəd, onda hər növdən həftədə neçə rəf istehsal edilməlidir?

Tapşırıq 2. Simpleks metodundan istifadə edərək xətti proqramlaşdırma məsələsini həll edin.

Tapşırıq 3.Şirkət iki növ xammaldan istifadə etməklə 3 növ məhsul istehsal edir: A1, A2, A3. Hər bir xammal növü üzrə istehsal vahidinə çəkilən məsrəflər, planlaşdırılan dövr üçün xammal ehtiyatları, eləcə də hər bir növ üzrə istehsal vahidindən əldə olunan mənfəət məlumdur.

1. Mənfəəti artırmaq üçün hər növdən neçə məhsul istehsal edilməlidir?
2. Hər bir xammal növünün vəziyyətini və onun xüsusi dəyərini müəyyənləşdirin.
3. Optimal planın strukturu daxilində hər bir xammal növünün ehtiyatlarında dəyişikliklər üçün maksimum intervalı müəyyənləşdirin, yəni. İstehsal nomenklaturası dəyişməyəcək.
4. Qıt xammal növlərindən birinin ehtiyatını mümkün olan maksimuma (verilmiş məhsul çeşidi daxilində) artırarkən istehsal olunan məhsulların kəmiyyətini və istehsaldan əldə edilən gəliri müəyyən edin.
5. Nəticədə optimal planın dəyişməyəcəyi hər bir növün istehsal vahidindən mənfəətin dəyişmə intervallarını müəyyən edin.

Tapşırıq 4. Simpleks metodundan istifadə edərək xətti proqramlaşdırma məsələsini həll edin:

Tapşırıq 5. Simpleks metodundan istifadə edərək xətti proqramlaşdırma məsələsini həll edin:

Tapşırıq 6.Şərtdə verilmiş planı ilkin istinad planı kimi nəzərə alaraq problemi simpleks üsulu ilə həll edin:

Tapşırıq 7. Dəyişdirilmiş simpleks metodundan istifadə edərək problemi həll edin.
İki növ A və B məhsulları istehsal etmək üçün üç növ texnoloji avadanlıqdan istifadə olunur. A məhsulunun vahidini istehsal etmək üçün birinci növ avadanlıq a1=4 saat, ikinci növ avadanlıq a2=8 saat, üçüncü növ avadanlıq a3=9 saat istifadə edir. B məhsulunun vahidini istehsal etmək üçün birinci növ avadanlıq b1=7 saat, ikinci növ avadanlıq b2=3 saat, üçüncü növ avadanlıq b3=5 saat istifadə edir.
Bu məhsulların istehsalı üçün birinci növ avadanlıqlar t1=49 saatdan, ikinci növ avadanlıqlar t2=51 saatdan, üçüncü növ avadanlıqlar t3=45 saatdan çox olmayan müddətdə işləyə bilər.
Hazır məhsul A vahidinin satışından əldə edilən mənfəət ALPHA = 6 rubl, B məhsulu isə BETTA = 5 rubl təşkil edir.
A və B məhsulları üçün istehsal planını tərtib edin, onların satışından maksimum gəlir əldə edin.

Tapşırıq 8. Dual simplex metodundan istifadə edərək optimal həlli tapın

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. dəyişənlərin sayı tənliklərin sayından çox olan xətti tənliklər sisteminə (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 süni əsas, ikincilər isə sərbəst adlanır.

Müəyyən bir nümunədən istifadə edərək simpleks metodunu nəzərdən keçirmək daha rahatdır. Xətti f(x) = 6x1 + 5x2 + 9x3 və məhdudiyyətlər sistemi verilsin: 5x1 + 2x2 + 3x3 ≤ 25 x1 + 6x2 + 2x3 ≤ 20 4x1 + 3x3 ≤ 18; f(x) funksiyasının qiyməti.

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. 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ə, ikincidə isə 0 əmsalı ilə eyni şey x5, x6 dəyişənləri və bazanın tərifinə uyğun gələn müvafiq tənliklər üçün də keçərlidir.

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. Əvvəlcə bu xəttin -9 olan ən kiçik elementini seçin. 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).

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. O, bir istinad planından digərinə keçidə əsaslanır, bu müddət ərzində məqsəd funksiyasının dəyəri 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. ≤ formasının bərabərsizlikləri üçün əlavə dəyişənlər işarəsi (+) ilə təqdim edilir, lakin ≥ formasındadırsa, (-) işarəsi ilə. Məqsəd funksiyasına əmsalı bərabər olan müvafiq işarələrlə əlavə dəyişənlər 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ə xəttinin 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 kanonik formaya gətiririk:

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

Simpleks metodundan istifadə etməklə məsələlərin həlli alqoritmini başa düşmək üçün burada ətraflı izahatlarla (applet həllinə bənzər) iki məsələnin əl ilə (applet deyil) həlli verilmişdir. Birinci məsələdə yalnız “≤” (ilkin əsaslı problem) bərabərsizlik işarələri var, ikincisində “≥”, “≤” və ya “=” işarələri ola bilər (süni əsaslı problem), onlar fərqli şəkildə həll olunur.

Simpleks metodu, problemin ilkin əsasla həlli

1)Simpleks metodu ilkin əsaslı problem üçün (bərabərsizlik məhdudiyyətlərinin bütün əlamətləri "≤").

Problemi yazaq kanonik forma, yəni. əlavə edərək bərabərsizlik məhdudiyyətlərini bərabərliklər şəklində yenidən yazırıq balans hesabatı dəyişənlər:

Bu sistem əsaslı sistemdir (əsas s 1, s 2, s 3, onların hər biri sistemin yalnız bir əmsalı 1 tənliyinə daxildir), x 1 və x 2 sərbəst dəyişənlərdir. Simpleks üsulu ilə həll ediləcək məsələlər aşağıdakı iki xüsusiyyətə malik olmalıdır: - məhdudiyyətlər sistemi əsaslı tənliklər sistemi olmalıdır; -sistemdəki bütün tənliklərin sərbəst şərtləri mənfi olmamalıdır.

Yaranan sistem əsaslı sistemdir və onun sərbəst şərtləri mənfi deyil, ona görə də müraciət edə bilərik simpleks üsulu. Problemi həll etmək üçün ilk simpleks cədvəlini (İterasiya 0) yaradaq simpleks üsulu, yəni. məqsəd funksiyasının əmsallar cədvəli və uyğun dəyişənlər üçün tənliklər sistemi. Burada “BP” əsas dəyişənlər sütunu, “Həll” sistem tənliklərinin sağ tərəflərinin sütunu deməkdir. Həll optimal deyil, çünki z cərgəsində mənfi əmsallar var.

simpleks üsulu iterasiyası 0

							Münasibət

Həllini təkmilləşdirmək üçün növbəti iterasiyaya keçək simpleks üsulu, aşağıdakı simpleks cədvəlini alırıq. Bunu etmək üçün seçmək lazımdır sütununu aktivləşdirin, yəni. simplex metodunun növbəti iterasiyası zamanı bazaya daxil ediləcək dəyişən. Z-sətirində (maksimum məsələdə) ən böyük mütləq mənfi əmsalla seçilir - simpleks metodunun ilkin iterasiyasında bu, x 2 sütunudur (əmsal -6).

Sonra seçin sətri aktivləşdirin, yəni. simplex metodunun növbəti iterasiyası zamanı əsası tərk edəcək dəyişən. "Qərar" sütununun qətnamə sütununun müvafiq müsbət elementlərinə ("Nisbət" sütunu) ən kiçik nisbəti ilə seçilir - ilkin iterasiyada bu, s 3-dür (əmsal 20).

İcazə verən element həlledici sütunla həlledici cərgənin kəsişməsində yerləşir, onun xanası rənglə vurğulanır, 1-ə bərabərdir. Buna görə də, simpleks metodunun növbəti iterasiyasında x 2 dəyişəni s 1-i əsasda əvəz edəcək. Qeyd edək ki, z-sətirində əlaqə axtarılmır, orada tire “-” qoyulur; Eyni minimal əlaqələr varsa, onlardan hər hansı biri seçilir. Əgər həlletmə sütunundakı bütün əmsallar 0-dan kiçik və ya bərabərdirsə, problemin həlli sonsuzdur.

Gəlin aşağıdakı “İterasiya 1” cədvəlini dolduraq. Onu “İterasiya 0” cədvəlindən alacağıq. Sonrakı transformasiyaların məqsədi x2 ayırdetmə sütununu vahid sütuna çevirməkdir (qətnamə elementi əvəzinə bir və qalan elementlər əvəzinə sıfırlarla).

1) “İterasiya 1” cədvəlinin x 2 sətirini hesablayın. Əvvəlcə “İterasiya 0” cədvəlinin s 3 həlledici sətirinin bütün üzvlərini bu cədvəlin həlledici elementinə (bu halda 1-ə bərabərdir) bölürük, “İterasiya 1” cədvəlində x 2 sətirini alırıq. . Çünki bu halda həlledici element 1-ə bərabərdir, onda “İterasiya 0” cədvəlinin s 3-cü sətri “İterasiya 1” cədvəlinin x 2-ci sətri ilə üst-üstə düşəcəkdir. İterasiya 1 cədvəlinin x 2 sətirində 0 1 0 0 1 20 əldə etdik, İterasiya 1 cədvəlinin qalan sətirləri bu sətirdən və İterasiya 0 cədvəlinin sətirləri aşağıdakı kimi alınacaq:

2) “İterasiya 1” cədvəlinin z-sətirinin hesablanması. İterasiya 0 cədvəlinin x2 sütununda birinci sətirdə (z-sətir) -6 yerinə, İterasiya 1 cədvəlinin birinci sətirində 0 olmalıdır. Bunu etmək üçün "İterasiya 1" cədvəlinin x 2 sətirinin bütün elementlərini 0 1 0 0 1 20-ni 6-ya vurun, 0 6 0 0 6 120 alın və bu cərgəni birinci sıra (z - sətir) ilə əlavə edin. cədvəl "İterasiya 0" -4 -6 0 0 0 0, biz -4 0 0 0 6 120 alırıq. x 2 sütununda sıfır 0 görünür, məqsədə nail olunur. Qətnamə x 2 sütununun elementləri qırmızı rənglə vurğulanır.

3) “İterasiya 1” cədvəlinin s 1-ci sətirlərinin hesablanması. “İterasiya 0” cədvəlinin s 1 sətirində 1-in yerinə “İterasiya 1” cədvəlində 0 olmalıdır. Bunu etmək üçün "Təkrar 1" cədvəlinin x 2 sətirinin bütün elementlərini -1-ə vurun, 0 -1 0 0 -1 -20 alın və bu cərgəni s 1 - sıra ilə əlavə edin. cədvəli "İterasiya 0" 2 1 1 0 0 64, biz sətir 2 0 1 0 -1 44 alırıq. x 2 sütununda tələb olunan 0-ı alırıq.

4) “İterasiya 1” cədvəlinin 2-ci sətirini hesablayın. "İterasiya 0" cədvəlinin s 2 sətirində 3-cü yerdə "İterasiya 1" cədvəlində 0 olmalıdır. Bunun üçün “İterasiya 1” 0 1 0 0 1 20 cədvəlinin x 2 sətirinin bütün elementlərini -3-ə vuraraq 0 -3 0 0 -3 -60 alırıq və bu sətri s 1 - sətirlə əlavə edirik. cədvəli "İterasiya 0" 1 3 0 1 0 72, biz sətir 1 0 0 1 -3 12 alırıq. x 2 sütununda tələb olunan 0 alındı ​​"İterasiya 1" cədvəlində x 2 sütunu oldu vahiddir, o, biri 1, qalanı isə 0-dan ibarətdir.

"İterasiya 1" cədvəlinin sətirləri aşağıdakı qaydaya uyğun olaraq alınır:

Yeni sətir = Köhnə sıra – (Köhnə sətir ayırdetmə sütununun əmsalı)*(Yeni ayırdetmə sırası).

Məsələn, z simli üçün bizdə:

Köhnə z-sətir (-4 -6 0 0 0 0) -(-6)*Yeni həlledici sətir -(0 -6 0 0 -6 -120) =Yeni z-sətir (-4 0 0 0 6 120).

Aşağıdakı cədvəllər üçün cədvəl elementlərinin yenidən hesablanması oxşar şəkildə aparılır, ona görə də onu buraxırıq.

simpleks üsulu iterasiyası 1

							Münasibət

Sütun x 1 həlli, sıra s 2 həlli, s 2 əsası tərk edir, x 1 əsas daxil olur. Eyni şəkildə, z-sətirində bütün müsbət əmsalları olan bir cədvəl əldə edənə qədər qalan simpleks cədvəllərini alırıq. Bu optimal cədvəlin əlamətidir.

simpleks üsulu iterasiyası 2

							Münasibət

Sütunların həlli s 3, sətirin həlli s 1, s 1 əsası tərk edir, s 3 əsası daxil edir.

simpleks üsulu iterasiyası 3

							Münasibət

Z-sətirində bütün əmsallar mənfi deyil, buna görə də optimal həll x 1 = 24, x 2 = 16, z max = 192 alınır.

Simpleks metodu tənliklər sisteminin addımlarla yönəldilmiş həllinin iterativ prosesidir, o, istinad həlli ilə başlayır və ən yaxşı variantı axtarmaq üçün mümkün həll sahəsinin künc nöqtələri boyunca hərəkət edir, məqsəd funksiyasının dəyərini yüksəldənə qədər yaxşılaşdırır. məqsəd funksiyası optimal qiymətə çatır.

Xidmətin məqsədi. Xidmət aşağıdakı qeyd formalarında simpleks metodundan istifadə edərək xətti proqramlaşdırma problemlərinin (LPP) onlayn həlli üçün nəzərdə tutulmuşdur:

• simpleks cədvəli şəklində (İordaniya çevrilmə üsulu); əsas qeyd forması;
• dəyişdirilmiş simpleks üsulu; sütun şəklində; xətt şəklində.

Təlimatlar. Dəyişənlərin sayını və sətirlərin sayını (məhdudiyyətlərin sayı) seçin. Nəticədə həll Word və Excel faylında saxlanılır.

Dəyişənlərin sayı 2 3 4 5 6 7 8 9 10
Sətirlərin sayı (məhdudiyyətlərin sayı) 1 2 3 4 5 6 7 8 9 10

Bu halda, x i ≥ 0 kimi məhdudiyyətləri nəzərə almayın. Bəzi x i üçün tapşırıqda heç bir məhdudiyyət yoxdursa, ZLP KZLP-yə çevrilməlidir və ya bu xidmətdən istifadə edilməlidir. Həll avtomatik olaraq istifadəni təyin edir M üsulu(süni əsaslı sadə üsul) və iki mərhələli simpleks metodu.

Bu kalkulyatorla aşağıdakılar da istifadə olunur:
ZLP-nin həlli üçün qrafik üsul
Nəqliyyat probleminin həlli
Matris oyununun həlli
Onlayn xidmətdən istifadə edərək, bir matris oyununun qiymətini (aşağı və yuxarı həddlər) təyin edə bilərsiniz, yəhər nöqtəsinin mövcudluğunu yoxlaya, aşağıdakı üsullardan istifadə edərək qarışıq strategiyanın həllini tapa bilərsiniz: minimax, simpleks metodu, qrafik (həndəsi) ) üsulu, Braun üsulu.
İki dəyişənli funksiyanın ekstremumu
Dinamik proqramlaşdırma problemləri
Satışdan maksimum gəlir əldə etmək üçün üç bazar arasında 5 eynicinsli mal paylayın. Hər bir bazarda satışdan əldə edilən gəlir G(X) X məhsulunun satılan partiyalarının sayından asılıdır və cədvəldə təqdim olunur.

Məhsulun həcmi X (lotlarla)	Gəlir G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Simpleks metod alqoritmi aşağıdakı addımları əhatə edir:

1. İlk əsas planın tərtib edilməsi. Mənfi olmayan əlavə balans dəyişənləri tətbiq etməklə xətti proqramlaşdırma məsələsinin kanonik formasına keçid.
2. Planın optimallığını yoxlamaq. Ən azı bir indeks xətti əmsalı sıfırdan azdırsa, plan optimal deyil və təkmilləşdirilməlidir.
3. Aparıcı sütunun və sıranın müəyyən edilməsi. İndeks xəttinin mənfi əmsallarından mütləq dəyərdə ən böyüyü seçilir. Sonra simpleks cədvəlinin sərbəst üzv sütununun elementləri aparıcı sütunun eyni işarəsinin elementlərinə bölünür.
4. Yeni istinad planının qurulması. Yeni plana keçid Simpleks cədvəlinin Jordan-Gauss metodu ilə yenidən hesablanması nəticəsində həyata keçirilir.

Əgər məqsəd funksiyasının ekstremumunu tapmaq lazımdırsa, onda söhbət minimum qiyməti (F(x) → min, funksiyanı minimuma endirmək üçün həll nümunəsinə baxın) və maksimum qiyməti ((F(x) tapmaqdan gedir. ) → max, funksiyanı maksimuma çatdırmaq üçün həll nümunəsinə baxın)

Çoxbucaqlının künc nöqtələrinin təpələrindən birində və ya iki bitişik künc nöqtəsi arasındakı seqmentdə mümkün həllər bölgəsinin sərhədində həddindən artıq həll əldə edilir.

Xətti proqramlaşdırmanın əsas teoremi. ZLP məqsəd funksiyası mümkün həllər bölgəsinin hansısa nöqtəsində ifrat dəyərə çatırsa, o zaman bu dəyəri künc nöqtəsində götürür. ZLP məqsəd funksiyası birdən çox künc nöqtəsində ifrat qiymətə çatırsa, bu nöqtələrin qabarıq xətti birləşmələrinin hər hansı birində eyni dəyəri alır.

Simpleks metodunun mahiyyəti. Optimal nöqtəyə hərəkət bir künc nöqtəsindən qonşuya doğru hərəkət etməklə həyata keçirilir ki, bu da X optinə daha da yaxınlaşdırır və daha sürətli edir. Nöqtələri sadalamaq üçün belə bir sxem, Simpleks metodu adlanır, R. Danzig tərəfindən təklif edilmişdir.
Künc nöqtələri m əsas dəyişən ilə xarakterizə olunur, buna görə də bir künc nöqtəsindən qonşuya keçid bazisdəki yalnız bir əsas dəyişəni qeyri-əsas dəyişənə dəyişdirməklə həyata keçirilə bilər.
Simpleks metodunun tətbiqi, LP problemlərinin müxtəlif xüsusiyyətləri və formulalarına görə müxtəlif dəyişikliklərə malikdir.

Simpleks cədvəllərinin qurulması optimal həll alınana qədər davam edir. Xətti proqramlaşdırma məsələsinin həllinin optimal olduğunu müəyyən etmək üçün simpleks cədvəlindən necə istifadə etmək olar?
Sonuncu sətirdə (məqsəd funksiyasının dəyərləri) mənfi elementlər yoxdursa, o, optimal planı tapacaqdır.

Qeyd 1. Əgər əsas dəyişənlərdən biri sıfıra bərabərdirsə, onda belə əsas həllə uyğun gələn ekstremal nöqtə degenerativdir. Bələdçi xəttin seçimində qeyri-müəyyənlik olduqda degenerasiya baş verir. Bələdçi olaraq başqa bir xətt seçsəniz, problemin degenerasiyasını ümumiyyətlə hiss etməyə bilərsiniz. Qeyri-müəyyənlik olduqda, döngədən qaçmaq üçün ən aşağı indeksə malik cərgə seçilməlidir.

Qeyd 2. Bəzi ifrat nöqtədə bütün simpleks fərqləri mənfi olmayan D k ³ 0 (k = 1..n+m), yəni. optimal həll əldə edilir və orada A k - qeyri-əsas vektoru üçün D k = 0. Sonra maksimuma ən azı iki nöqtədə nail olunur, yəni. alternativ optimal var. Bu x k dəyişənini bazisə daxil etsək, məqsəd funksiyasının qiyməti dəyişməyəcək.

Qeyd 3. İkili məsələnin həlli sonuncu simpleks cədvəlindədir. Simpleks fərqlər vektorunun sonuncu m komponentləri (balans dəyişənlərinin sütunlarında) ikili məsələnin optimal həllidir. Optimal nöqtələrdə birbaşa və ikili məsələlərin məqsəd funksiyalarının qiymətləri üst-üstə düşür.

Qeyd 4. Minimallaşdırma məsələsini həll edərkən bazaya ən böyük müsbət simpleks fərqi olan vektor daxil edilir. Sonra, maksimumlaşdırma problemi ilə eyni alqoritm tətbiq olunur.

“III növ xammalın tam istehlak edilməsi zəruridir” şərti göstərilibsə, müvafiq şərt bərabərlikdir.