Doğrusal programlama problemlerini çözmek için tek yönlü yöntem. Excel'de Jordan-Gauss dönüşümü ve simpleks yöntemi

Problem ifadesi ≥ işaretli kısıtlamalar içeriyorsa, eşitsizliğin her iki tarafı -1 ile çarpılarak bunlar ∑a ji b j formuna indirgenebilir. m ek değişken x n + j ≥0 (j = 1, m) tanıtıyoruz ve kısıtlamaları eşitlik biçimine dönüştürüyoruz

(2)

x 1, x 2, ..., x n probleminin tüm başlangıç ​​değişkenlerinin temel olmadığını varsayalım. O zaman ek değişkenler temel olacaktır ve kısıtlamalar sisteminin özel çözümü şu şekildedir:

x 1 = x 2 = ... = x n = 0, x n + j = b j, j = 1, m. (3)

Bu durumda amaç fonksiyonunun değeri F 0 = 0 olduğundan, F(x)'i temsil edebiliriz. Aşağıdaki şekilde:

F (x) = ∑c ben x ben + F 0 = 0 (4)

Başlangıç ​​tek yönlü tablosu (simpleks tablo 1), denklem (2) ve (4) temelinde derlenir. Eğer x n + j ek değişkenlerinden önce (2)'de olduğu gibi bir "+" işareti geliyorsa, x i değişkenlerinden ve serbest terim b j'den önceki tüm katsayılar değişmeden tek yönlü tabloya girilir. Hedef fonksiyonunun katsayıları, maksimize edildiğinde, zıt işaretlerle simpleks tablonun alt satırına girilir. Simpleks tablosundaki serbest terimler problemin çözümünü belirler.

Sorunu çözmek için algoritma aşağıdaki gibidir:

1. adım. Ücretsiz üye sütununun üyeleri kaydırılır. Hepsi pozitifse, uygun bir temel çözüm bulunmuştur ve algoritmanın optimal çözümü bulmaya karşılık gelen 5. adımına geçilmelidir. İlk simpleks tablosunda negatif serbest terimler varsa, çözüm geçerli değildir ve 2. adıma gitmelisiniz.

2. adım. Uygulanabilir bir çözüm bulmak için yapılırken, temel olmayan değişkenlerden hangilerinin temele dahil edileceğine ve hangi değişkenin temelden çıkarılacağına karar vermek gerekir.

Tablo 1.

x n

temel değişkenler	Kısıtlamalarda ücretsiz üyeler	temel olmayan değişkenler
		x 1	x 2	...	x l	...
x n + 1	b1	11	12	...	1l	...	1n
x n + 2	b2	21	22	...	2l	...	2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn + r	b2	bir r1	bir r2	...	bir rl	...	bir rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn + m	ben	bir m1	bir m2	...	bir ml	...	bir dakika
F (x) maks	0	-c 1	-c 2	...	-c 1	...	-c n

Bunu yapmak için, serbest üye sütununun negatif öğelerinden herhangi birini seçin (b 2 önde gelen veya çözümleyen olsun. Negatif serbest üyeli satırda hiçbir negatif öğe yoksa, kısıtlamalar sistemi uyumsuzdur ve sorunun çözümü yok.

Aynı zamanda, seçilen NP x l'de bir artışla işaretini ilk değiştiren değişken BP'den hariç tutulur. Bu, r indisi koşuldan belirlenen x n + r olacaktır.

onlar. serbest üyenin seçilen pivot sütunun üyesine en küçük oranına karşılık gelen değişken. Bu ilişki denir simpleks ilişkisi. Yalnızca pozitif simpleks ilişkiler dikkate alınmalıdır.

x n + r değişkenine karşılık gelen dize denir öncü veya izin verici. Simpleks tablonun elemanı a rl, baştaki satır ve satırdaki sütunun kesişiminde duran, satır başı veya çözümleyici eleman olarak adlandırılır. Pivot elemanı bulmak, birbirini takip eden her tek yönlü tabloyla çalışmayı sona erdirir.

3. adım. Öğeleri önceki adımdaki simpleks tablosunun öğelerinden yeniden hesaplanan ve bir asal ile işaretlenen yeni bir simpleks tablosu hesaplanır, yani. b "j, a" ji, c "i, F" 0. Elemanlar aşağıdaki formüllere göre yeniden hesaplanır:

İlk olarak, yeni simpleks tablosu, önceki simpleks tablosunda önde gelen satır ve sütunu dolduracaktır. İfade (5), önde gelen elemanın yerindeki a "rl öğesinin, önceki simpleks tablosunun elemanının karşılıklılığına eşit olduğu anlamına gelir. a ri satırının elemanları, önde gelen elemana bölünür ve elemanları a jl sütunu da önde gelen elemana bölünür, ancak zıt işaretle alınır.B "r ve c" l elemanları aynı şekilde hesaplanır.

Formüllerin geri kalanını kullanarak yazmak kolaydır.

Dikdörtgen, eski simpleks tablosuna göre, köşegenlerinden biri yeniden hesaplanmış (a ji) ve önde gelen (a rl) elemanlardan oluşacak şekilde inşa edilmiştir (Şekil 1). İkinci köşegen benzersiz bir şekilde belirlenir. Yeni bir a "ji elemanı bulmak için, karşı köşegenin elemanlarının önde gelen elemana bölünmesiyle elde edilen ürün a ji elemanından çıkarılır (bu, hücrenin yanındaki" - "işaretiyle gösterilir). b" j elemanları , (j ≠ r) ve c "i, (i ≠ l).

4. adım. Yeni bir simpleks tablosunun analizi, algoritmanın 1. adımıyla başlar. Eylem, uygun bir temel çözüm bulunana kadar devam eder, yani. ücretsiz üye sütununun tüm üyeleri pozitif olmalıdır.

5. adım. Uygulanabilir bir temel çözümün bulunduğuna inanıyoruz. Hedef fonksiyonu F (x) doğrusunun katsayılarına bakıyoruz. Simpleks tablonun optimalliği için bir kriter, F-satırındaki temel olmayan değişkenler için katsayıların negatif olmamasıdır.

Pirinç. 1. Dikdörtgen kuralı

F-satırının katsayıları arasında negatif olanlar varsa (kesme hariç), o zaman başka bir temel çözüme gitmeniz gerekir. Hedef fonksiyonunu maksimize ederken, temel, sütunu negatif katsayı cl'nin maksimum mutlak değerine karşılık gelen temel olmayan değişkenlerden birini (örneğin, x l) içerir. Sonuç olarak simpleks tablolar. Bu, artışı hedef fonksiyonunda bir gelişmeye yol açan değişkeni seçmeyi mümkün kılar. x l değişkenine karşılık gelen sütuna, önde gelen sütun denir. Aynı zamanda, bu x n + r değişkeni, r indeksi minimum simpleks ilişkisi tarafından belirlenen temelden hariç tutulur:

x n + r'ye karşılık gelen satıra satır aralığı denir ve tek yönlü tablonun elemanına, önde gelen satır ile önde gelen sütunun kesişiminde duran a rl denir. lider eleman.

6. adım. 3. adımda belirtilen kurallara göre. bulana kadar işlem devam eder. en uygun çözüm veya var olmadığı sonucuna varılır.

Öndeki sütundaki çözümün optimizasyonu sırasında tüm öğeler pozitif değilse, o zaman önde gelen satır seçilemez. Bu durumda, problemin uygulanabilir çözümlerinin etki alanındaki fonksiyon, yukarıda ve F max -> & ∞ ile sınırlı değildir.

Bir ekstremum arayışındaki bir sonraki adımda, temel değişkenlerden biri sıfıra eşit olursa, buna karşılık gelen temel çözüme dejenere denir. Bu durumda, belirli bir frekansta aynı BP kombinasyonunun tekrar etmeye başlaması (F fonksiyonunun değeri korunur) ve yeni bir kabul edilebilir temel çözüme geçmenin imkansız olması ile karakterize edilen bir döngü meydana gelir. Döngü, simpleks yönteminin ana dezavantajlarından biridir, ancak nispeten nadirdir. Uygulamada, bu gibi durumlarda, sütunu hedef fonksiyonundaki negatif katsayının maksimum mutlak değerine karşılık gelen değişkeni temele almayı genellikle reddeder ve üretirler. rastgele seçim yeni temel çözüm.

Örnek 1. Problemi çözün

maks (F (x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Simpleks yöntemi ve çözüm sürecinin geometrik yorumunu verir.

Problemin çözümünün grafik yorumu Şekil 2'de gösterilmektedir. 2. Hedef fonksiyonun maksimum değerine, koordinatlarla ODZP'nin tepesinde ulaşılır. Problemi simpleks tabloları kullanarak çözelim. İkinci kısıtlamayı (-1) ile çarparız ve eşitsizlikleri eşitlik formuna getirmek için ek değişkenler ekleriz, sonra

x 1 ve x 2 başlangıç ​​değişkenleri temel olmayan olarak alınır ve ek x 3, x 4 ve x 5 temel kabul edilir ve bir simpleks tablosu oluştururuz (simpleks tablo 2). Simpleks tabloya karşılık gelen çözüm. 2 geçerli değil; pivot elemanın ana hatları çizilir ve önceki algoritmanın 2. adımına göre seçilir. Bir sonraki simpleks tablo. 3, kabul edilebilir temel çözümü belirler; Şekil l'deki ODZP'nin tepe noktasına karşılık gelir. 2 Pivot eleman, problemi çözmek için algoritmanın 5. adımına göre ana hatlarıyla çizilir ve seçilir. Sekme. 4, problemin optimal çözümüne karşılık gelir, bu nedenle: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; Fmaks = 20.

Pirinç. 2. Grafik çözüm görevler

Gauss-Jordan yöntemi doğrusal sistemleri çözmek için tasarlanmıştır. cebirsel denklemler(YAVAŞ). Gauss yönteminin bir modifikasyonudur. Gauss yöntemi iki aşamada (ileri ve geri) gerçekleştirilirse, Gauss-Jordan yöntemi sistemin tek aşamada çözülmesine izin verir. Gauss-Jordan yöntemini uygulamak için ayrıntılar ve doğrudan bir şema örneklerde açıklanmıştır.

Tüm örneklerde $ A $ sistem matrisini, $ \ widetilde (A) $ ise genişletilmiş sistem matrisini temsil eder. SLAE gösteriminin matris formu hakkında bilgi edinebilirsiniz.

Örnek 1

SLAE $ \ left \ (\ start (hizalı) & 4x_1-7x_2 + 8x_3 = -23; \\ & 2x_1-4x_2 + 5x_3 = -13; \\ & -3x_1 + 11x_2 + x_3 = 16. \ End (hizalı) ) \ sağ. $ Gauss-Jordan yöntemiyle.

Aldığımız son matristen sisteme geçelim:

$$ \ sol \ (\ başla (hizalı) & 0 \ cdot x_1 + 1 \ cdot x_2 + 0 \ cdot x_3 = 1; \\ & 1 \ cdot x_1 + 0 \ cdot x_2 + 0 \ cdot x_3 = -2; \\ & 0 \ cdot x_1 + 0 \ cdot x_2 + 1 \ cdot x_3 = -1. \ Son (hizalı) \ sağa. $$

Ortaya çıkan sistemi basitleştirerek, elimizde:

$$ \ sol \ (\ başlangıç ​​(hizalı) & x_2 = 1; \\ & x_1 = -2; \\ & x_3 = -1. \ bitiş (hizalı) \ sağa. $$

Tam çözüm açıklama olmadan şuna benziyor:

Çözme elemanlarını seçmeye yönelik bu yöntem oldukça kabul edilebilir olsa da, sistem matrisinin köşegen elemanlarının çözümleme elemanları olarak seçilmesi tercih edilir. Aşağıda bu yönteme bakacağız.

Sistem matrisinin ana köşegenindeki öğeleri çözme seçimi.

Bu çözüm öncekine tamamen benzer olduğundan (çözünürlük öğelerinin seçimi hariç), ayrıntılı açıklamaları atlayacağız. İzin verilen öğeleri seçme ilkesi basittir: ilk sütunda ilk satırın bir öğesini seçeriz, ikinci sütunda ikinci satırın bir öğesini alırız, üçüncü sütunda üçüncü satırın bir öğesini alırız ve böylece üzerinde.

İlk adım

İlk sütunda, ilk satırın öğesini seçin, yani. çözme elemanı olarak 4'e sahibiz. Bu sayı hala 4'ten küçük olduğu için 2 sayısının seçiminin daha tercih edilebilir göründüğünü anlıyorum. İlk sütundaki 2 sayısının ilk sıraya taşınması için, takas edeceğiz birinci ve ikinci satırlar:

$$ \ sol (\ başlangıç ​​(dizi) (ccc | c) 4 & -7 & 8 & -23 \\ 2 & -4 & 5 & -13 \\ -3 & 11 & 1 & 16 \ end (dizi) \ sağ) \ sağ ok \ sol (\ başlangıç ​​(dizi) (ccc | c) 2 & -4 & 5 & -13 \\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \ end (dizi ) \ sağ) $$

Böylece, çözümleme öğesi 2 sayısıyla temsil edilir. Daha önce olduğu gibi, ilk satırı 2'ye bölün ve ardından ilk sütunun öğelerini sıfırlayın:

$$ \ left (\ start (dizi) (ccc | c) 2 & -4 & 5 & -13 \\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \ end (dizi) \ sağ) \ başlangıç ​​(dizi) (l) I: 2 \\\ hayalet (0) \\ \ hayalet (0) \ bitiş (dizi) \ sağ ok \ sol (\ başlangıç ​​(dizi) (ccc | c) 1 & - 2 & 5/2 & -13/2 \\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \ end (dizi) \ sağ) \ başlangıç ​​(dizi) (l) \ hayalet (0 ) \\ II-4 \ cdot I \\ III + 3 \ cdot I \ end (dizi) \ rightarrow \ sol (\ başlangıç ​​(dizi) (ccc | c) 1 & -2 & 5/2 & -13 /2 \ \ 0 & 1 & -2 & 3 \\ 0 & 5 & 17/2 & -7/2 \ end (dizi) \ sağ). $$

İkinci adım

İkinci adım, ikinci sütunun öğelerini sıfırlamaktır. Çözümleme elemanı olarak ikinci satırın elemanını seçiyoruz, yani. 1. İzin veren unsur zaten bire eşittir, bu yüzden herhangi bir satırı değiştirmeyeceğiz. Bu arada, satırları değiştirmek isteseydik, ilk adımda zaten kullanıldığı için ilk satıra dokunmazdık. Ancak ikinci ve üçüncü satırlar kolayca değiştirilebilir. Ancak tekrar ediyorum, bu durumda satırları değiştirmeye gerek yok, çünkü çözümleme elemanı zaten optimal - bire eşit.

$$ \ sol (\ başla (dizi) (ccc | c) 1 & -2 & 5/2 & -13/2 \\ 0 & 1 & -2 & 3 \\ 0 & 5 & 17/2 & -7 / 2 \ bitiş (dizi) \ sağ) \ başlangıç ​​(dizi) (l) I + 2 \ cdot II \\ \ phantom (0) \\ III-5 \ cdot II \ bitiş (dizi) \ sağ ok \ sol (\ start (dizi) (ccc | c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3 \\ 0 & 0 & 37/2 & -37/2 \ end (dizi ) \ sağ). $$

İkinci adım bitti. Üçüncü adıma geçelim.

Üçüncü adım

Üçüncü adım, üçüncü sütunun öğelerini sıfırlamaktır. Çözümleme elemanı olarak üçüncü sıranın elemanını seçiyoruz, yani. 37/2. Üçüncü satırın öğelerini 37/2'ye böleriz (böylece çözümleme öğesi 1'e eşit olur) ve sonra üçüncü sütunun karşılık gelen öğelerini sıfırlarız:

$$ \ sol (\ başlangıç ​​(dizi) (ccc | c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3 \\ 0 & 0 & 37/2 & -37 / 2 \ bitiş (dizi) \ sağ) \ başlangıç ​​(dizi) (l) \ hayalet (0) \\ \ hayalet (0) \\ III: \ frac (37) (2) \ bitiş (dizi) \ sağ ok \ sol (\ başla (dizi) (ccc | c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3 \\ 0 & 0 & 1 & -1 \ end (dizi) \ sağ) \ başlangıç ​​(dizi) (l) I + 2 \ cdot III \\ II + 3/2 \ cdot III \\ \ hayalet (0) \ bitiş (dizi) \ sağ ok \ sol (\ başlangıç ​​(dizi) ( ccc | c) 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -1 \ end (dizi) \ sağ). $$

Cevap alındı: $ x_1 = -2 $, $ x_2 = 1 $, $ x_3 = -1 $. Tam çözüm, açıklama olmadan şöyle görünür:

Bu sayfadaki diğer tüm örnekler tam olarak ikinci şekilde çözülecektir: sistem matrisinin köşegen elemanlarını çözümleyici olarak seçeceğiz.

Cevap: $ x_1 = -2 $, $ x_2 = 1 $, $ x_3 = -1 $.

Örnek 2

SLAE $ \ left \ (\ start (hizalı) & 3x_1 + x_2 + 2x_3 + 5x_4 = -6; \\ & 3x_1 + x_2 + 2x_4 = -10; \\ & 6x_1 + 4x_2 + 11x_3 + 11x_4 = -27; \\ & -3x_1-2x_2-2x_3-10x_4 = 1. \ Son (hizalı) \ sağa $ Gauss-Jordan yöntemiyle.

Verilen sistemin genişletilmiş matrisini yazalım: $ \ widetilde (A) = \ left (\ start (dizi) (cccc | c) 3 & 1 & 2 & 5 & -6 \\ 3 & 1 & 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \ end (dizi) \ sağ) $.

Elemanları çözmek olarak sistem matrisinin köşegen elemanlarını seçeceğiz: ilk adımda ilk satırın bir elemanını, ikinci adımda ikinci satırın bir elemanını vb.

İlk adım

İlk sütundaki karşılık gelen öğeleri sıfırlamamız gerekiyor. İlk satırın öğesini çözümleme öğesi olarak alalım, yani. 3. Buna göre, çözümleme elemanının bire eşit olması için ilk satırın 3'e bölünmesi gerekecektir. Ardından, ilk sütunun tüm öğelerini, çözümleyen hariç, sıfırlayın:

$$ \ sol (\ başla (dizi) (cccc | c) 3 & 1 & 2 & 5 & -6 \\ 3 & 1 & 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \ \ -3 & -2 & -2 & -10 & 1 \ bitiş (dizi) \ sağ) \ başlangıç ​​(dizi) (l) I: 3 \\ \ hayalet (0) \\\ hayalet (0) \\\ hayalet (0) \ bitiş (dizi) \ sağ ok \ sol (\ başla (dizi) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 3 & 1 & 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \ end (dizi) \ sağ) \ başlangıç ​​(dizi) (l) \ hayalet (0) \\ II-3 \ cdot I \\ III-6 \ cdot I \\ IV + 3 \ cdot I \ end (dizi) \ rightarrow \\ \ rightarrow \ sol (\ başlangıç ​​(dizi) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 0 & -2 & -3 & -4 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & -1 & 0 & - 5 & ​​​​5 \ bitiş (dizi) \ sağ). $$

İkinci adım

İkinci sütunun karşılık gelen öğelerini sıfırlamaya devam ediyoruz. İkinci satırın öğesini bir çözümleme öğesi olarak almaya karar verdik, ancak bunu yapamayız, çünkü gerekli eleman sıfır. Sonuç: hatları değiştireceğiz. İlk satırda zaten kullanıldığı için ilk satıra dokunulamıyor. Seçim zengin değil: ya ikinci ve üçüncü satırları değiştiririz ya da dördüncü ve ikinciyi değiştiririz. Dördüncü satır (-1) içerdiğinden, dördüncü satırın "değişim"de yer almasına izin verin. Şimdi ikinci ve dördüncü satırları değiştirelim:

$$ \ sol (\ başla (dizi) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 0 & -2 & -3 & -4 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & -1 & 0 & -5 & -5 \ end (dizi) \ sağ) \ sağ ok \ sol (\ başlangıç ​​(dizi) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & -1 & 0 & -5 & -5 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & 0 & -2 & -3 & -4 \ bitiş (dizi) \ sağ) $$

Şimdi her şey normal: çözümleme elemanı (-1)'e eşittir. Bu arada, çizgilerin yerlerini değiştirmek imkansızdır, ancak bunu bir sonraki örnek №3'te tartışacağız. Şimdilik ikinci satırı (-1)'e bölün ve ardından ikinci sütundaki öğeleri sıfırlayın. Lütfen ikinci sütunda dördüncü satırda bulunan öğenin zaten sıfıra eşit olduğunu, bu nedenle dördüncü satıra dokunmayacağımızı unutmayın.

$$ \ sol (\ başlangıç ​​(dizi) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & -1 & 0 & -5 & -5 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & 0 & -2 & -3 & -4 \ end (dizi) \ sağ) \ başlangıç ​​(dizi) (l) \ fantom (0) \\ II: (- 1) \\\ hayalet (0) \\\ hayalet (0) \ bitiş (dizi) \ sağ ok \ sol (\ başlangıç ​​(dizi) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & 0 & -2 & -3 & -4 \ end (dizi) \ sağ) \ start (dizi) (l) I-1/3 \ cdot II \\ \ phantom (0) \\ III-2 \ cdot II \\\ phantom (0) \ bitiş (dizi) \ sağ ok \\ \ sağ ok \ sol (\ başla ( dizi) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 7 & -9 & -25 \\ 0 & 0 & -2 & -3 & -4 \ end (dizi) \ sağ). $$

Üçüncü adım

Üçüncü sütunu işlemeye başlayalım. Çözümleme elemanı olarak sistem matrisinin köşegen elemanlarını almaya karar verdik. Üçüncü adım için bu, üçüncü satırda bulunan öğenin seçilmesi anlamına gelir. Ancak, çözümleyici olarak sadece eleman 7'yi alırsak, o zaman üçüncü satırın tamamının 7'ye bölünmesi gerekecektir. Bana göre (-2) ile bölmek daha kolay. Bu nedenle, üçüncü ve dördüncü satırların konumlarını değiştireceğiz ve ardından çözümleme öğesi (-2) olacaktır:

$$ \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 7 & -9 & -25 \\ 0 & 0 & -2 & -3 & -4 \ end (dizi) \ sağ) \ sağ ok \ sol (\ başlangıç ​​(dizi) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & -2 & -3 & -4 \\ 0 & 0 & 7 & -9 & -25 \ end (dizi) \ sağ) $$

İzin verilen öğe - (-2). Üçüncü satırı (-2)'ye bölün ve üçüncü sütunun karşılık gelen öğelerini sıfırlayın:

$$ \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & -2 & - 3 & -4 \\ 0 & 0 & 7 & -9 & -25 \ bitiş (dizi) \ sağ) \ başlangıç ​​(dizi) (l) \ hayalet (0) \\ \ hayalet (0) \\ III :( -2) \\\ hayalet (0) \ bitiş (dizi) \ sağ ok \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 7 & -9 & -25 \ end (dizi) \ sağ) \ start (dizi) (l) I-2 / 3 \ cdot III \\ \ phantom (0) \\ \ phantom (0) \\ IV-7 \ cdot III \ end (dizi) \ rightarrow \\ \ rightarrow \ sol (\ başlangıç ​​(dizi) (cccc | c) ) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & -39/2 & - 39 \ bitiş (dizi) \ sağ). $$

Dördüncü adım

Dördüncü sütunu sıfırlamaya geçelim. Çözümleme elemanı dördüncü satırda bulunur ve $ - \ frac (39) (2) $ sayısına eşittir.

$$ \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & -39/2 & -39 \ bitiş (dizi) \ sağ) \ başlangıç ​​(dizi) (l) \ hayalet (0) \\ \ hayalet (0) \\ \ hayalet (0) \\ IV: \ sol (- \ frac (39) (2) \ sağ) \ bitiş (dizi) \ sağ ok \ sol (\ başlangıç ​​(dizi) (cccc | c) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & 1 & 2 \ end (dizi) \ sağ) \ start (dizi) (l ) I + IV \\ II-5 \ cdot IV \\ III-3/2 \ cdot IV \\ \ phantom (0) \ end (dizi) \ rightarrow \\ \ rightarrow \ sol (\ başlangıç ​​(dizi) (cccc) | c) 1 & 0 & 0 & 0 & -3 \\ 0 & 1 & 0 & 0 & -5 \\ 0 & 0 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 2 \ end (dizi) \ sağ). $$

Karar bitti. Cevap: $ x_1 = -3 $, $ x_2 = -5 $, $ x_3 = -1 $, $ x_4 = 2 $. Açıklama yapmadan tam çözüm:

Cevap: $ x_1 = -3 $, $ x_2 = -5 $, $ x_3 = -1 $, $ x_4 = 2 $.

Örnek No. 3

SLAE $ \ left \ (\ start (hizalanmış) & x_1-2x_2 + 3x_3 + 4x_5 = -5; \\ & 2x_1 + x_2 + 5x_3 + 2x_4 + 9x_5 = -3; \\ & 3x_1 + 4x_2 + 7x_3 + 4x_4'ü çözün + 14x_5 = -1; \\ & 2x_1-4x_2 + 6x_3 + 11x_5 = 2; \\ & -2x_1 + 14x_2-8x_3 + 4x_4-7x_5 = 20; \\ & -4x_1-7x_2-9x_3-6x_4-21x_5 = - 9. \ uç (hizalı) \ sağa $ Gauss-Jordan yöntemiyle Sistem tanımsız ise, temel çözümü belirtin.

Benzer örnekler "Bir SLAE'nin genel ve temel çözümleri" konusunda ele alınmıştır. Bahsedilen konunun ikinci bölümünde verilen örnek Gauss yöntemi kullanılarak çözülmüştür. Gauss-Jordan yöntemini kullanarak çözeceğiz. Önceki örneklerde zaten yapıldığı için çözümü adım adım açıklamayacağız.

$$ \ sol (\ başla (dizi) (cccc | c) 1 & -2 & 3 & 0 & 4 & -5 \\ 2 & 1 & 5 & 2 & 9 & -3 \\ 3 & 4 & 7 & 4 & 14 & -1 \\ 2 & -4 & 6 & 0 & 11 & 2 \\ -2 & 14 & -8 & 4 & -7 & 20 \\ -4 & -7 & -9 & -6 & -21 & -9 \ end (dizi) \ sağ) \ başlangıç ​​(dizi) (l) \ phantom (0) \\ II-2 \ cdot I \\ III-3 \ cdot I \\ IV-2 \ cdot I \\ V + 2 \ cdot I \\ VI + 4 \ cdot I \ end (dizi) \ rightarrow \ sol (\ başlangıç ​​(dizi) (cccc | c) 1 & -2 & 3 & 0 & 4 & -5 \ \ 0 & 5 & -1 & 2 & 1 & 7 \\ 0 & 10 & -2 & 4 & 2 & 14 \\ 0 & 0 & 0 & 0 & 3 & 12 \\ 0 & 10 & -2 & 4 & 1 & 10 \\ 0 & -15 & 3 & -6 & -5 & -29 \ end (dizi) \ sağ) \ başlangıç ​​(dizi) (l) \ fantom (0) \\ II: 5 \\ \ hayalet (0) \\ \ hayalet (0) \\ \ hayalet (0) \\ \ hayalet (0) \ bitiş (dizi) \ sağ ok \\ \ sol (\ başla (dizi) (ccccc | c) 1 & - 2 & 3 & 0 & 4 & -5 \\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5 \\ 0 & 10 & -2 & 4 & 2 & 14 \\ 0 & 0 & 0 & 0 & 3 & 12 \\ 0 & 10 & -2 & 4 & 1 & 10 \\ 0 & -15 & 3 & -6 & -5 & -29 \ bitiş (dizi) \ sağ) \ başlangıç (dizi) (l) I + 2 \ cdot II \\ \ phantom (0) \\ III-10 \ cdot II \\ IV: 3 \\ V-10 \ cdot II \\ VI + 15 \ cdot II \ end (dizi) \ sağ ok \ sol (\ başlangıç ​​(dizi) (cccc | c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\ 0 & 1 & -1/5 & 2/5 & 1 / 5 & ​​7/5 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & -1 & -4 \\ 0 & 0 & 0 & 0 & -2 & -8 \ end (dizi) \ sağ). $$

Yapılan dönüşümlerden birinin hala açıklamaya ihtiyacı olduğuna inanıyorum: $ IV: 3 $. Dördüncü satırın tüm öğeleri tamamen üçe bölünebilirdi, bu nedenle, yalnızca basitlik nedeniyle, bu satırın tüm öğelerini üçe böldük. Dönüştürülen matristeki üçüncü satır sıfır oldu. Sıfır çizgisini çaprazlayın:

$$ \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & -1 & -4 \\ 0 & 0 & 0 & 0 & -2 & -8 \ bitiş (dizi) \ sağ) $$

Üçüncü sütunun öğelerinin sıfırlanması gereken üçüncü adıma geçmemizin zamanı geldi. Ancak köşegen eleman (üçüncü sıra) sıfırdır. Ve çizgilerin yerlerini değiştirmek hiçbir şey yapmaz. Birinci ve ikinci satırları zaten kullandık, bu yüzden onlara dokunamıyoruz. Ve dördüncü ve beşinci satırlara dokunmanın bir anlamı yok, çünkü çözümleme elemanının sıfıra eşitlik sorunu hiçbir yere gitmeyecek.

Bu durumda sorun son derece basit bir şekilde çözülür. Üçüncü sütunu halledemez miyiz? Tamam, dördüncüye geçelim. Belki dördüncü sütunda, üçüncü satırdaki eleman sıfırdan farklı olacaktır. Bununla birlikte, dördüncü sütun, üçüncü ile aynı sorundan muzdariptir. Dördüncü sütundaki üçüncü satır öğesi sıfırdır. Ve çizgilerin yerlerini değiştirmek yine hiçbir şey yapmaz. Dördüncü sütunu da idare edemiyor musunuz? Tamam, beşinciye geçelim. Ancak beşinci sütunda üçüncü satırın elemanı sıfır bile değil. Bire eşit, ki bu oldukça iyi. Böylece, beşinci sütundaki çözümleme elemanı 1'dir. Çözümleme elemanı seçilir, bu nedenle Gauss-Jordan yönteminin daha ileri dönüşümlerini gerçekleştireceğiz:

$$ \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & -1 & -4 \\ 0 & 0 & 0 & 0 & -2 & -8 \ bitiş (dizi) \ sağ) \ başlangıç ​​(dizi) (l) I-22/5 \ cdot III \\ II-1/5 \ cdot III \\ \ phantom (0) \\ IV + III \\ V + 2 \ cdot III \ bitiş (dizi) \ sağ ok \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5 \\ 0 & 1 & -1 / 5 & 2/5 & 0 & 3/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \ end (dizi) \ sağ) \ sağ ok \\ \ sağ ok \ sol | \ metin (boş satırları sil) \ sağ | \ sağ ok \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5 \\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \ end (dizi) \ sağ) $$

Sistem matrisini ve genişletilmiş sistem matrisini kademeli bir forma getirdik. Her iki matrisin sıraları $ r = 3 $'a eşittir, yani. 3 temel değişken seçmeniz gerekiyor. Bilinmeyenlerin sayısı $ n = 5 $, yani $ n-r = 2 $ serbest değişken seçmeniz gerekiyor. $ r'den beri< n$, то согласно следствию из теоремы Кронекера-Капелли данная система является неопределённой (т.е. имеет бесконечное количество решений). Для нахождения решений системы составим "ступеньки":

"Adımlarda" 1, No. 2, No. 5 sütunlarından öğeler bulunur. Bu nedenle, temel değişkenler $ x_1 $, $ x_2 $, $ x_5 $ olacaktır. Serbest değişkenler sırasıyla $ x_3 $, $ x_4 $ olacaktır. Serbest değişkenlere karşılık gelen 3 ve 4 numaralı sütunlar, elbette, işaretlerini değiştirmeyi unutmadan çizgi üzerinde hareket ettirilecektir.

$$ \ sol (\ başla (dizi) (cccc | c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5 \\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \ end (dizi) \ sağ) \ sağ ok \ sol (\ başlangıç ​​(dizi) (ccc | ccc) 1 & 0 & 0 & -99/5 & -13/5 & -4/5 \\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5 \\ 0 & 0 & 1 & 4 & 0 & 0 \ end (dizi) \ sağ) ... $$

Son matristen genel çözümü elde ederiz: $ \ left \ (\ start (hizalı) & x_1 = - \ frac (99) (5) - \ frac (13) (5) x_3- \ frac (4) (5 ) x_4; \\ & x_2 = \ frak (3) (5) + \ frak (1) (5) x_3- \ frak (2) (5) x_4; \\ & x_3 \ R'de; \\ & x_4 \ içinde R; \\ & x_5 = 4. \ end (hizalı) \ sağ. $ Temel çözüm, sıfıra eşit serbest değişkenler alarak bulunur, yani $ x_3 = 0 $, $ x_4 = 0 $:

$$ \ left \ (\ start (hizalı) & x_1 = - \ frac (99) (5); \\ & x_2 = \ frac (3) (5); \\ & x_3 = 0; \\ & x_4 = 0; \\ & x_5 = 4. \ Bitiş (hizalanmış) \ sağa. $$

Sorun çözüldü, sadece cevabı yazmak kalıyor.

Cevap: Ortak karar: $ \ sol \ (\ başla (hizalı) & x_1 = - \ frac (99) (5) - \ frac (13) (5) x_3- \ frac (4) (5) x_4; \\ & x_2 = \ frac (3) (5) + \ frac (1) (5) x_3- \ frac (2) (5) x_4; \\ & x_3 \ R'de; \\ & x_4 \ R'de; \\ & x_5 = 4 . \ bitiş (hizalı) \ sağa. $, temel çözüm: $ \ sol \ (\ başlangıç ​​(hizalı) & x_1 = - \ frac (99) (5); \\ & x_2 = \ frac (3) (5) ; \\ & x_3 = 0; \\ & x_4 = 0; \\ & x_5 = 4. \ bitiş (hizalı) \ sağa.

Applet'in bilgisayarınızda çalışmasını sağlamak için aşağıdakileri yapmanız gerekir - Başlat> Denetim Masası> Programlar> Java'yı tıklayın. V Java penceresi Kontrol Paneli Güvenlik sekmesini seçin, Site Listesini Düzenle düğmesini tıklayın, ekle düğmesini ekleyin ve bu sayfanın yolunu adres çubuğu tarayıcı. Ardından OK butonlarına basıyoruz ardından bilgisayarı yeniden başlatıyoruz.

Uygulamayı başlatmak için "Simplex" düğmesine tıklayın. Bu satırın üzerinde "Simplex" düğmesi görünmüyorsa, bilgisayarda Java yüklü değildir.

"Simplex" butonuna tıkladıktan sonra, simpleks yöntemi için değişken sayısı ve görev kısıtlamalarının sayısını girmek için ilk pencere görüntülenir.

“Tamam” düğmesine tıkladıktan sonra, simpleks yöntemi için görev verilerinin geri kalanını girmek için bir pencere görüntülenir: görüntüleme modu (ondalık kesirler veya sıradan kesirler), görev kriteri türü min veya maks, amaç fonksiyonu katsayılarını girme ve “≤”, “ ≥ "veya" = " işaretli kısıtlama sisteminin katsayılarının, х ben ≥ 0 biçimindeki kısıtlamaların girilmesine gerek yoktur, Algoritmalarında bunları dikkate alır.

"Çöz" düğmesine tıkladıktan sonra, sorunu çözmenin sonuçlarını içeren bir pencere görüntülenir. .Pencere iki bölümden oluşur, üst kısımda orijinal probleme dönüştürmenin açıklamasını içeren bir metin alanı vardır. kanonik biçim ilk tek yönlü tabloyu oluşturmak için kullanılır. Pencerenin altında, sekmeli bir bölmede, her yinelemenin küçük bir Metin kutusu en altta çözünürlük sütunu, çözünürlük satırı ve programı öğretici yapan diğer bilgiler bulunur. Optimal (son) tablonun bulunduğu sekmede, probleme elde edilen optimal çözüm metin alanında gösterilir.

Lütfen uygulamada fark edilen hataları ve yorumları şu adrese gönderin: [e-posta korumalı] veya size minnettar olacağımız 8 962 700 77 06 numaralı telefonu arayın.

M-yöntemi programı

Çözüm programı ulaşım sorunu

İşte iki problemin tek yönlü bir yöntemle (bir uygulama çözümüne benzer) manuel (bir uygulama değil) çözümü: detaylı açıklamalar problem çözme algoritmasını anlamak için. İlk problem sadece "≤" (başlangıç ​​temeli olan bir problem) eşitsizlik işaretlerini içerir, ikincisi "≥", "≤" veya "=" (bir problem ile ilgili bir problem) işaretlerini içerebilir. yapay temel), farklı şekillerde çözülürler.

Simpleks yöntemi, bir problemin başlangıç ​​bazında çözülmesi

1)Simpleks yöntemi başlangıç ​​temeli olan bir problem için (tüm eşitsizlik-kısıtlama işaretleri "≤").

Görevi yazalım kanonik biçim, yani eşitsizlik kısıtlamaları ekleyerek eşitlikler olarak yeniden yazılabilir bilanço değişkenler:

Bu sistem, temeli olan bir sistemdir (temel s 1, s 2, s 3, her biri sistemin sadece bir denklemine 1 katsayısı ile dahil edilir), x 1 ve x 2 serbest değişkenlerdir. Simpleks yöntemi kullanılarak çözülen problemler aşağıdaki iki özelliğe sahip olmalıdır:
- kısıtlama sistemi, temeli olan bir denklem sistemi olmalıdır;
- sistemdeki tüm denklemlerin serbest terimleri negatif olmamalıdır.

Ortaya çıkan sistem, tabanlı bir sistemdir ve serbest terimleri negatif değildir, bu nedenle simpleks yöntemi uygulanabilir. İlk tek yönlü tabloyu oluşturalım (Yineleme 0), yani. bir amaç fonksiyonu katsayıları tablosu ve karşılık gelen değişkenler için bir denklem sistemi. Burada "BP", temel değişkenlerin sütunu anlamına gelir, "Çözüm" - sistemin denklemlerinin sağ taraflarının sütunu. Çözüm optimal değil çünkü z - satırında negatif katsayılar var.

yineleme 0

BP						Çözüm	Davranış

Çözümü geliştirmek için bir sonraki yinelemeye geçin, aşağıdaki tek yönlü tabloyu elde ederiz. Bunu yapmak için seçmeniz gerekir izin verilen sütun, yani bir sonraki yinelemede temele dahil edilecek bir değişken. Z satırındaki (maksimum problemde) mutlak değerdeki en büyük negatif katsayı tarafından seçilir - ilk yinelemede bu, x 2 sütunudur (katsayı -6).

Daha sonra seçilir izin verilen dize, yani bir sonraki yinelemede temelden çıkacak değişken. "Karar" sütununun, çözümleme sütununun ("Oran" sütunu) karşılık gelen pozitif öğelerine en küçük oranı ile seçilir - ilk yinelemede, bu satır s 3'tür (katsayı 20).

izin verilen öğeçözümleme sütunu ve çözümleme satırının kesişimindedir, hücresi vurgulanır, 1'e eşittir. Bu nedenle, bir sonraki yinelemede x 2 değişkeni temeldeki s 3'ün yerini alacaktır. İlişkinin z-çizgisinde aranmadığına dikkat edin; oraya bir tire "-" konur. Aynı minimum ilişkiler varsa, bunlardan herhangi biri seçilir. Çözümleme sütunundaki tüm katsayılar 0'dan küçük veya 0'a eşitse, sorunun çözümü sonsuzdur.

Aşağıdaki tabloyu "Yineleme 1" dolduralım. "Yineleme 0" tablosundan alacağız. Daha ileri dönüşümlerin amacı, çözümleme sütunu x 2'yi bire (çözümleme öğesi yerine bir ve diğer öğeler yerine sıfırlarla) dönüştürmektir.

1) "Yineleme 1" tablosunun x 2 satırının hesaplanması. İlk olarak, "Yineleme 0" tablosunun çözümleme satırı s 3'ün tüm üyelerini çözümleme elemanına böleriz (bu, 1'de 1'e eşittir). bu durumda) bu tablonun "Yinelemeler 1" tablosunda x 2 satırını alıyoruz. Çünkü bu durumda çözümleme elemanı 1'e eşittir, daha sonra "Yineleme 0" tablosunun s 3 satırı, "Yineleme 1" tablosunun x 2 satırı ile çakışacaktır. "Yineleme 1" tablosunun x 2 satırını 0 1 0 0 1 20 aldık, "Yineleme 1" tablosunun geri kalan satırları bu satırdan ve "Yineleme 0" tablosunun satırları aşağıdaki gibi elde edilecektir:

2) "Yineleme 1" tablosunun z satırının hesaplanması. Yineleme 0 tablosunun x 2 sütunundaki ilk satırda (z-satır) -6 yerine, Yineleme 1 tablosunun ilk satırında 0 olmalıdır. Bunu yapmak için, "Yineleme 1" tablosunun x 2 satırının tüm öğelerini 0 1 0 0 1 20 ile çarparız, 0 6 0 0 6 120 elde ederiz ve bu satırı ilk satır (z - satır) ile ekleriz. "Yineleme 0" tablosundan -4 -6 0 0 0 0, -4 0 0 0 6 120 elde ederiz. x 2 sütununda sıfır 0 görünür, hedefe ulaşılır. Çözünürlük sütunu öğeleri x 2 kırmızıyla vurgulanır.

3) "Yineleme 1" tablosunun 1. satırının hesaplanması. "Yineleme 0" tablosunun 1 satırındaki 1 yerine, "Yineleme 1" tablosunda 0 olmalıdır. Bunu yapmak için, "Yineleme 1" tablosunun x 2 satırının tüm öğelerini 0 1 0 0 1 20 -1 ile çarparız, 0 -1 0 0 -1 -20 alırız ve bu satırı s 1 ile ekleriz - "Yineleme 0" tablosunun satırı 2 1 1 0 0 64, satır 2 0 1 0 -1 44'ü alıyoruz. x 2 sütununda gerekli 0'ı alıyoruz.

4) "Yineleme 1" tablosunun 2. satırının hesaplanması. "Yineleme 0" tablosunun 2 satırındaki 3 yerine, "Yineleme 1" tablosunda 0 olmalıdır. Bunu yapmak için, "Yineleme 1" tablosunun x 2 satırının tüm öğelerini 0 1 0 0 1 20 -3 ile çarparız, 0 -3 0 0 -3 -60 alırız ve bu satırı s 2 ile ekleriz - "Yineleme 0" tablosunun satırı 1 3 0 1 0 72, satır 1 0 0 1 -3 12'yi alıyoruz. x 2 sütununda gerekli 0 elde ediliyor. "Yineleme 1" tablosundaki sütun x 2 bir oldu , bir 1 ve geri kalan 0'ı içerir.

"Yineleme 1" tablosunun satırları aşağıdaki kurala göre elde edilir:

Yeni Satır = Eski Satır - (Eski Satırın Çözünürlük Sütunu Faktörü) * (Yeni Çözünürlük Satırı).

Örneğin, z -string için elimizde:

Eski z-string (-4 -6 0 0 0 0)
- (- 6) * Yeni çözünürlük dizisi - (0-6 0 0 -6 -120)
= Yeni z-çizgisi(-4 0 0 0 6 120) .

Aşağıdaki tablolar için, tablo öğelerinin yeniden hesaplanması aynı şekilde yapılır, bu yüzden onu atlıyoruz.

yineleme 1

						Çözüm	Davranış

x 1 sütununa izin verildiğinde, s 2 satırını çözerek, s 2 temelden çıkar, x 1 temele girer. Tam olarak aynı şekilde, z-satırındaki tüm pozitif katsayıları olan bir tablo elde edene kadar simpleks tabloların geri kalanını elde ederiz. Bu, optimal bir tablonun işaretidir.

yineleme 2

						Çözüm	Davranış

Çözümleme sütunu s 3, çözümleme satırı s 1, s 1 tabandan çıkar, s 3 tabana girer.

yineleme 3

						Çözüm	Davranış

z satırında tüm katsayılar negatif değildir, bu nedenle optimal çözüm x 1 = 24, x 2 = 16, z max = 192'dir.

Simplex yöntemi, yapay bir temele sahip bir problem çözme

2) Problemi yapay bir temelle çözelim (en az bir eşitsizlik-kısıtlama işareti "≥" veya "=").

Problemi kurallı biçimde yazalım (simpleks yöntemini gerektiren bir denklem sistemi biçiminde), bunun için x 3 ≥ 0 ve x 4 ≥ 0 olmak üzere iki değişkeni tanıtıyoruz:

Kısıtlama sistemi yalnızca bir kabul edilebilir temel değişken x 4 sunar, yalnızca üçüncü denklemde 1 katsayısı ile yalnızca bir denkleme dahil edilir, bu nedenle birinci ve ikinci denklemlere R 1 ≥ 0 ve R 2 ≥ 0 yapay değişkenleri ekleriz Denklemler-kısıtlar, temeli olan bir sistem olmalıdır, yani. Her denklemde, sistemin sadece bir denkleminde yer alan 1 katsayılı bir değişken olmalıdır, bizim durumumuzda R 1, R 2 ve x 4'tür. Sözde M-problemimiz var:

Bu sistem R 1, R 2 ve x 4'ün temel değişkenler olduğu ve x 1, x 2 ve x 3'ün serbest değişkenler olduğu, tüm denklemlerin serbest terimlerinin negatif olmadığı bir tabanlı sistemdir. Bu nedenle, sorunu çözmek için simpleks yöntemi kullanılabilir. İlk simpleks tablosunu yazalım:

yineleme 0

							Çözüm	Davranış
		-16

Yapay temelli görevler için tabloya "Değerlendirme" satırı eklendi. Zıt işaretli yapay değişkenler (R) ile satırların karşılık gelen katsayılarının toplanmasıyla elde edilir. Yapay değişkenlerden en az biri bazda olduğu sürece tabloda yer alacaktır. "Puan" satırının en büyük modulo negatif katsayısı ile, tablo içindeyken çözümleme sütunu belirlenir. "Puan" satırı tablodan ayrıldığında (temelde kukla değişkenler yoktur), çözümleme sütunu, başlangıç ​​bazındaki problemde olduğu gibi z-satırı tarafından belirlenir. Bu tabloda, çözümleme sütunu x 2'dir, en büyük modülo negatif tahmine (-7) göre seçilir.Çözümleme satırı R2, yapay değişkenlerin olmadığı problemde olduğu gibi, "Karar" sütununun çözüm sütununun karşılık gelen pozitif öğelerine en küçük oranına göre seçilir. Bu, bir sonraki yinelemede x 2 değişkeninin serbestten temele ve R2 değişkeninin temelden serbeste gideceği anlamına gelir. Aşağıdaki simpleks tablosunu yazalım:

Müsaade sütunu x 1, Müsaade satırı R 1, R 1 taban dışı, x 1 tabana dahil edilmiştir. Bundan sonra, temelde hiçbir yapay değişken kalmadığından, aşağıdaki tabloda "Değerlendirme" satırı yoktur:

yineleme 2

							Çözüm	Davranış

Ardından, çözümleme sütunu z satırı tarafından seçilir. Z-satırında, kukla temelin dışında olduğunda optimalliği etkilemeyen kukla R1 katsayısı dışında tüm katsayılar negatif değildir. Bu nedenle, optimal bir çözüm elde edilir x 1 = 6/5; x 2 = 3/5; z maks = 72/5.

Simpleks Yönteminin Özel Durumları

1) Düz çizgi (iki boyutlu bir problem düşünüldüğünde) doğrusal programlama ve Genel dava hiperdüzlem) (optimum noktada tam bir eşitlik olarak yerine getirilen) eşitsizlik-kısıtlamalardan birine karşılık gelen düz çizgiye (hiperdüzlem) paraleldir. amaç fonksiyonu aynı şeyi alır optimal değer uygun çözümler bölgesinin sınırının bazı noktalarında. Bu çözümler denir alternatif optimal çözümler... kullanılabilirlik alternatif çözümler optimal simpleks tablosundan belirlenebilir. Optimal tablonun z satırı, temel olmayan değişkenlerin sıfır katsayılarını içeriyorsa, alternatif çözümler vardır.

2) Simpleks tablosunun çözümleme sütununda tüm katsayılar sıfırdan küçük veya sıfıra eşitse, o zaman çözümleme satırı seçilemez, bu durumda çözüm sınırsızdır.

3) Bir doğrusal programlama probleminin kısıtlamaları tutarsızsa (yani, aynı anda yürütülemezler), o zaman problemin uygulanabilir çözümleri yoktur. Kısıtlar sistemini oluşturan tüm eşitsizlikler, negatif olmayan sağ taraflarla "≤" türündeyse bu durum ortaya çıkamaz, çünkü bu durumda, ek değişkenler uygun bir çözüm oluşturabilir. Diğer kısıtlama türleri için yapay değişkenler kullanılır. Sorunun bir çözümü varsa, temeldeki optimal tabloda yapay değişkenler (R i) yoktur. Eğer oradalarsa, sorunun çözümü yoktur.

Bildiğiniz gibi, bilinmeyenlerin ardışık eleme yöntemi olarak da bilinen Jordan-Gauss yöntemi, Gauss yönteminin lineer cebirsel denklem sistemlerini (SLAE) çözmeye yönelik bir modifikasyonudur.

Yöntem dayanmaktadır temel dönüşümler(sistemi bir eşdeğere çevirerek) şunları içerir:

• sistemin denkleminin her iki tarafına sıfırdan farklı bir sayı ile çarpılan aynı sistemin başka bir denkleminin eklenmesi;
• sistemdeki denklemlerin yeniden düzenlenmesi;
• 0 = 0 biçimindeki denklem sisteminden çıkarılması.

Gauss yönteminden farklı olarak, her adımda biri hariç tüm denklemlerden bir değişken çıkarılır.

Yöntem adımı aşağıdaki gibidir:

• sonraki denklemde sıfır olmayan katsayılı bir bilinmeyen seçin (çözümleme elemanı);
• seçilen denklemi çözme elemanına bölün;
• çözümleme elemanındaki bilinmeyeni diğer tüm denklemlerden hariç tutmak için seçilen denklemi kullanmak;
• üzerinde Sonraki adım benzer şekilde, bir bilinmeyen hariç tüm denklemlerden başka bir bilinmeyen çıkarılır;
• tüm denklemler kullanılıncaya kadar süreç devam eder.

Şu şekilde algoritmalaştırılabilir:

A * x = b matris biçimindeki SLAE için (m * n boyutunun A matrisi, kare olması gerekmez), aşağıdaki tablo derlenir:

Tabloda çözümleme öğesi a r, s ≠ 0 seçilir, ardından r çözümleme satırıdır, s çözümleme sütunudur.

Bir sonraki tabloya geçiş kurallara göre yapılır:

1. Çözümleme satırının öğeleri hesaplanır: a "r, j = a r, j / a r, s - yani, tablonun r satırı, çözümleme öğesine bölünür;

2. a r, s hariç, çözümleme sütununun tüm öğeleri, bire eşit, sıfıra eşit ol;

3. Çözümleme satırı ve sütunu dışındaki öğeler, aşağıda gösterilen formül kullanılarak hesaplanır:

Bu formülün payının 2'ye 2 matrisin determinantını hesaplamaya benzer olduğunu gördüğünüzde kafanız karışmaz.

4. Manuel hesaplamada, son kontrol sütunundaki değer, önceki satır öğelerinin toplamı ile karşılaştırılır. Değerler uyuşmuyorsa bu satırdaki hataları aramalısınız. Otomatik hesaplama için kontrol sütunu atlanabilir.

Aşağıdaki durumlar mümkündür:

1. İstisnalar sürecinde Sol Taraf sistemin denklemleri kaybolur ve sağdaki b ≠ 0 ise sistemin çözümü yoktur.

2. 0 = 0 kimliği ortaya çıkıyor - denklem, diğerlerinin doğrusal bir birleşimidir ve sıfır dizisi sistemden silinebilir.

3. Bilinmeyenleri ortadan kaldırmak için tüm denklemleri kullandıktan sonra, tablo ya istenen çözümü içerir ya da kısıtlar sisteminin tutarsızlığını gösterir.

Excel'deki yöntemi, değiştirilmesi çok zaman almaması gereken tek bir formülle programlayalım. Örneğin, SLAE'yi çözmek için

A1'den D4'e kadar olan yaprak hücrelerinin katsayılarını doldurun, a 1,1 = 1 çözümleme öğesini seçin ve Ürdün için "evrensel" formülü kullanacağımız A6 hücresindeki yöntemin ilk adımını atın- Gauss dönüşümü:

EĞER (SATIR ($ A $ 1) = HAT (A1); A1 / $ A $ 1;
EĞER (SÜTUN ($ A $ 1) = SÜTUN (A1); 0; (A1 * $ A $ 1-)
DOLAYLI (ADRES (SATIR (A1), SÜTUN ($ A $ 1))) *
DOLAYLI (ADRES (SATIR ($ A $ 1); SÜTUN (A1)))) / $ A $ 1))

Sonraki adımda, çözümleme öğesi örneğin 2,2 = 1 (hücre B7) olabilir. Formülü A6'dan A11'e kopyalamak bize kalır ( boş satır Yöntemin adımlarını görsel olarak ayırmaya bırakın), formül düzenleme moduna girin ( çift ​​tıklama veya onu seçin ve F2 tuşuna basın) ve A1 hücresinden B7'ye tüm bağlantılı bağlantıları düzeltin (fareyi kenarlığın üzerine hafifçe sürükleyin).

Tabii ki, formüldeki her yerde $ A $ 1 sabit referansını DOLAYLI (HÜCRE) formunun bir yapısı ile değiştirebilirsiniz. dinamik adres bağlantılar. DOLAYLI (F8) diyelim ve F8 hücresinde çözümleme öğesinin hücre adresi otomatik olarak oluşturulacaktır. belirli bir kullanıcı tarafından satır ve sütun numaraları. Daha sonra bu satır ve sütun numaraları için ayrı hücreler sağlamanız gerekir, örneğin şöyle:

Ne yazık ki, tüm bunlar hiçbir şey vermeyecek - $ A $ 1 yerine, formülde DOLAYLI ($ F $ 8) düzeltmemiz gerekecek ve yine de formülü kopyalarken aynı sayıda bağlantıyı sürükleyip bırakacağız. Ayrıca "manuel" olarak girilen satır ve sütun numaralarının da geçerliliği kontrol edilmelidir (en azından şekildeki gibi), bu nedenle varlıkları çarpmayacağız.

Ekli belgenin ilk iki sayfasında yöntemin çalıştığını görebilirsiniz. Excel dosyası(2 farklı örnek).

Aşağıdaki Jordan-Gauss dönüşümüne dayanmaktadır evrensel yöntem doğrusal optimizasyon problemlerinin çözümü tek yönlü yöntem... Açıklamaları genellikle korkutucu, uzun ve teoremlerle dolu. Basit bir açıklama yapmaya çalışalım ve Excel'de hesaplamaya uygun bir algoritma geliştirelim. Aslında, simpleks yöntemi standart Analiz Paketi eklentisinde zaten yerleşiktir ve onu "manuel" olarak programlamaya gerek yoktur, bu nedenle kodumuz oldukça eğitici bir değere sahiptir.

İlk olarak, minimum teori.

SLAE'nin sütun vektörleri doğrusal olarak bağımsızsa, karşılık gelen değişkenler temel ve geri kalanı Bedava... Örneğin, SLAE'de

x 2 ve x 4 değişkenleri temel, x 1 ve x 3 serbesttir. Temel değişkenler kendi aralarında bağımsızdır ve örneğin sıfırlar ve (x 2 = 2, x 4 = 1) gibi serbest değişkenler yapılabilir - temel çözüm sistemler.

Farklı çözücü elemanlar seçilerek, SLAE'nin farklı bazlara sahip çözümleri elde edilebilir. Bir SLAE'nin negatif olmayan herhangi bir temel çözümüne denir. destekleyici.

Simpleks yöntemi, birinden bir geçiş sağlar. Referans çözümü ulaşana kadar bir başkasına en uygun Amaç fonksiyonunun minimumunu veren çözüm.

Simpleks yönteminin algoritması aşağıdaki gibidir:

1. LP problemi kanonik forma dönüştürülür:

Bu her zaman şu şekilde yapılabilir: standart ayarda yazılan probleme

ek olarak bilanço değişkenleri, sayısı eşitsizlik kısıtlamalarının sayısına karşılık gelen m (bilinmeyenlerin değerlerinin negatif olmamasına ilişkin kısıtlamalar dikkate alınmaz). Bundan sonra, "≤" işaretli eşitsizlikler, örneğin bir formun kısıtlamaları sistemi gibi eşitliklere dönüşür.

2 * x 1 + 3 * x 2 ≤20
3 * x 1 + x 2 ≤15
4 * x 1 ≤16
3 * x 2 ≤12
x 1, x 2 ≥0

formu alacak

2 * x 1 + 3 * x 2 + x 3 = 20
3 * x 1 + x 2 + x 4 = 15
4 * x 1 + x 5 = 16
3 * x 2 + x 6 = 12
x 1, x 2, ..., x 6 ≥0

Yani, denge değişkenlerinin "ekonomik" anlamı çok basittir - bunlar her türden kullanılmayan kaynakların "artıklarıdır".

eğer asıl sorun minimum değil, maksimum arandı, amaç fonksiyonu Z, Z 1 = -Z ile değiştirilecektir. Sorunların çözümleri, min Z = - maks Z 1 ile çakışmaktadır. Örneğin, hedef

Z (x 1, x 2) = 2 * x 1 + 5 * x 2 (maks)

olarak yeniden yazıldı

Z 1 (x 1, x 2) = - 2 * x 1 -5 * x 2 (dk)

Orijinal problemde "≤" yerine "≥" işaretli eşitsizlik denklemleri varsa, bu tür her bir eşitsizliğin her iki tarafı -1 ile çarpılır ve eşitsizliğin işareti tersine çevrilir, örneğin,

3 * x 1 + x 2 + x 4 ≥15

dönüşür

3 * x 1 -x 2 -x 4 ≤15

Modelin kanonik formu elde edilir, çünkü yazılır tek yönlü tablo:

Henüz seçilmemişlerse, temel değişkenler (BP) sol sütuna yazılır - boş.

2. Jordan – Gauss adımlarını kullanarak ilk referans planı bulunur, yani. SLAE, negatif olmayan serbest terimler b i> 0 ile temel forma indirgenir. Bu durumda, amaç fonksiyonu Z sadece serbest bilinmeyenler cinsinden ifade edilmelidir (Z-satırındaki sıfır katsayılar sadece temeldeki x i değişkenleri altında görünür). a r, s çözümleme elemanını seçerken, BP sütununun r satırına x s değişkenini yazarız, zaten bir değişken varsa onu sileriz (temelden çıkarıyoruz).

3. X * referans planını x i sütunlarının altına yazın: serbest değişkenlerin altında - sıfırlar, temel olanların altında - temel değişkene karşılık gelen b sütunundaki katsayılar.

Aşağıda R vektörünü kurala göre yazıyoruz: temel değişkenler altında - sıfırlar, serbest R i = Z i altında.

Tüm R i ≥0 ise, optimal çözüm X * ve hedefin değeri Z min = -q bulunur, aksi takdirde ihtiyacınız vardır yeni plan, sizde var mı, yoldaş Zhyukov? (s. 4).

4. Çözümleme sütunu s'yi seçmek için, vektör R'nin maksimum modulo negatif bileşenini seçiyoruz, çözümleme sütunu s seçiliyor. Ardından, kısıtlama sisteminin matrisinin s-inci sütununun katsayılarını analiz ederiz. Tüm a i, s ≤0 ise, çözüm yoktur ve Z min eksi sonsuz olma eğilimindeyse, aksi takdirde 5. adıma gidin.

5. Çözümleme doğrusu r'yi seçmek için, b i / A i, s ≥0, i = 1,2, ..., m negatif olmayan oranlarını oluşturun ve aralarından en küçüğünü seçin. Birkaç satır için minimuma ulaşılırsa, bunlardan herhangi biri çözümleyici olarak alınabilirken, yeni referans tasarımında bazı temel değişkenlerin değerleri 0'a eşit olacak, yani dejenere bir referans tasarımı elde edeceğiz.

6. Jordan-Gauss dönüşümünü a r, s çözümleme elemanı ile gerçekleştirin ve 3. adıma gidin

Geometrik olarak, simpleks yöntemi, problemin uygulanabilir çözümlerinin alanını oluşturan n-boyutlu bir dışbükey polihedronun köşelerinin en kısa geçişine karşılık gelir:

Burada çok boyutlu bir çokgenin köşelerinden biri olan temel plan C'den en uygun E = X * planına geçtik.

Tüm bunları Excel'de programlamak kolay değil, ancak mümkün. Ekli belge, problemlerin çözümünü simpleks yöntemiyle uygulayan 3 örnek içermektedir. Doğru, bir adım gerçekleştirirken, 3 formülü değiştirmeniz gerekecek, bunlar tek yönlü yöntem için ilk örneğin sayfasında vurgulanmıştır. sarı: I2 hücresinde bir çözünürlük satırı seçmek için oranların hesaplanması, A12 hücresinde BP sütununun doldurulması, B12 hücresinde Jordan-Gauss dönüşümünün adımı. Jordan-Gauss dönüşümü örneğinde olduğu gibi, formüllerdeki değişiklik sadece şuna başvurma ihtiyacı ile ilişkilidir. Yeni hat izin verilen öğeye sahip hücrenin adresini içerir (ilk adım için - C9 hücresi).

“0-satır” (eşitlik kısıtlamaları) ve “serbest” değişkenler (yani, negatif olmama şartına tabi olmayan değişkenler) olmaması şartıyla.

2. Eşitlik kısıtlamalarının ve “serbest” değişkenlerin olması durumunda aşağıdaki gibi ilerleyin.

"0-satırında" bir etkinleştirme öğesi seçilir ve değiştirilmiş bir Jordan istisna adımı atılır, ardından bu etkinleştirme sütunu silinir. Bu eylem dizisi şu ana kadar devam eder: tek yönlü tablo en az bir “0-satır” kalır (böylece tablo kısaltılır).

Serbest değişkenler de varsa, bu değişkenler temel hale getirilmelidir. Serbest değişken temel hale geldikten sonra, referans ve optimal planlar aranırken çözümleme unsurunun belirlenmesi sürecinde verilen dize sayılmaz (ancak dönüştürülür).

Doğrusal programlama problemlerinde yozlaşma

Simpleks yöntemi göz önüne alındığında, doğrusal programlama probleminin dejenere olmadığını varsaydık, yani. her referans planı tam olarak şunları içerir:
pozitif bileşenler, nerede
- görevdeki kısıtlamaların sayısı. Dejenere bir referans tasarımında, pozitif bileşenlerin sayısı kısıtlamaların sayısından daha azdır: belirli bir referans tasarıma karşılık gelen bazı temel değişkenler sıfır değerleri alır. En basit durum için geometrik bir yorum kullanma
(temel olmayan değişkenlerin sayısı 2'dir), dejenere bir problemi dejenere olmayan bir problemden ayırt etmek kolaydır. Dejenere problemde, koşulların çokyüzlülüğünün bir köşesinde, form denklemleriyle tanımlanan ikiden fazla düz çizgi kesişir.
... Bu, koşul poligonunun bir veya daha fazla tarafının bir noktaya daraltıldığı anlamına gelir.

A vergiye tabi
dejenere bir problemde, bir tepe noktasında 3'ten fazla düzlem kesişir
.

Sorunun dejenere olmadığı varsayımı altında, yalnızca bir değer vardı.
, hangi bazdan türetilen koşullar vektörünün indeksi (temel değişkenlerin sayısından türetilmiştir) belirlendi. Dejenere bir problemde
aynı anda birkaç indekse ulaşılabilir (birkaç satır için). Bu durumda bulunan referans planında birkaç temel değişken sıfır olacaktır.

Doğrusal programlama probleminin dejenere olduğu ortaya çıkarsa, o zaman temelden türetilen koşulların vektörünün kötü bir seçimiyle, aynı referans planının temeli boyunca sonsuz bir hareket ortaya çıkabilir. Sözde döngü fenomeni. Doğrusal programlamanın pratik problemlerinde döngü son derece nadir görülen bir olgu olmasına rağmen, olasılığı dışlanmaz.

Dejenerasyonla başa çıkmanın yöntemlerinden biri, değerler üzerindeki kısıtlamalar sisteminin sağ taraflarının vektörünü "önemsiz ölçüde" değiştirerek sorunu dönüştürmektir. , böylece problem dejenere olmaz ve aynı zamanda bu değişiklik problemin optimal planını gerçekten etkilemez.

Daha yaygın olarak uygulanan algoritmalar, döngülerin oluşma olasılığını azaltmak veya bunların üstesinden gelmek için bazı basit kurallar içerir.

Değişkene izin ver temel hale getirilmelidir. Endeks kümesini düşünün bunlardan oluşan hangisi için
... Çok sayıda indeks , bu koşulun yerine getirildiği için, ... Eğer bir öğeden oluşursa, koşulların vektörü temelden çıkarılır (değişken temel olmayan hale gelir).

Eğer birden fazla elemandan oluşur, ardından bir küme hangi oluşur
hangi
... Eğer bir indeksten oluşur , daha sonra değişken temelden türetilir ... Aksi takdirde, set oluşur vesaire.

Uygulamada, döngü zaten algılanmışsa kural kullanılmalıdır.