Sorunların çözümü için Simpleks yöntemi. Simpleks yöntemi, problem çözme örnekleri

Sorunun çözülmesi gerekiyor doğrusal programlama.

Amaç fonksiyonu:

2x 1 +5x 2 +3x 3 +8x 4 → dk

Sınırlayıcı koşullar:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

Kısıtlamalar sistemini kanonik forma getirelim; bunun için ek değişkenlerin eklenmesiyle eşitsizliklerden eşitliklere geçmek gerekir.

Problemimiz bir minimizasyon problemi olduğundan onu maksimum arama problemine dönüştürmemiz gerekiyor. Bunu yapmak için amaç fonksiyonunun katsayılarının işaretlerini zıt işaretlerle değiştiririz. İlk eşitsizliğin elemanlarını değiştirmeden yazıyoruz, ek bir x 5 değişkeni ekliyoruz ve “≤” işaretini “=” olarak değiştiriyoruz. İkinci ve üçüncü eşitsizlikler “≥” işaretli olduğundan katsayılarının işaretlerini ters çevirerek bunlara sırasıyla x 6 ve x 7 ek değişkenlerini eklemek gerekir. Sonuç olarak, eşdeğer bir sorunla karşılaşıyoruz:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

İlk simpleks tablosunun oluşumuna geçiyoruz. Amaç fonksiyonunun zıt işaretli katsayıları tablonun F satırına girilir.

Serbest terimler sütununda negatif eleman bulunmadığından kabul edilebilir bir çözüm bulunmuştur, F satırı negatif elemanlar içermektedir, bu da ortaya çıkan çözümün optimal olmadığı anlamına gelmektedir. Baş sütunu tanımlayalım. Bunu yapmak için, F satırında maksimum mutlak değere sahip negatif elemanı bulalım - bu -1.988. Öndeki satır, serbest terimin ön sütunun karşılık gelen elemanına oranının minimum olduğu satır olacaktır. Baştaki satır X2'dir ve baştaki eleman: 0,313'tür.

F dizisinde negatif eleman olmadığından en uygun çözüm bulunmuştur. Asıl görev minimumu bulmak olduğundan, en iyi çözüm F dizisinin ters işaretle alınan serbest terimi olacaktır. F=1,924
değişken değerleri eşit olan: x 3 =0,539, x 1 =0,153. x 2 ve x 4 değişkenleri tabana dahil edilmediğinden x 2 =0 x 4 =0.

Doğrusal programlama sınırlı kaynakların kullanımını optimize etmek için tasarlanmış bir matematiksel modelleme tekniğidir. LP askeri alanda, endüstride başarıyla kullanılmaktadır. tarım, ulaştırma endüstrisi, ekonomi, sağlık sistemi ve hatta sosyal bilimlerde. Bu yöntemin yaygın kullanımı, bu yöntemi uygulayan yüksek verimli bilgisayar algoritmalarıyla da desteklenmektedir. Tamsayılı, doğrusal olmayan ve stokastik programlama da dahil olmak üzere diğer, daha karmaşık model türleri ve yöneylem araştırması (OR) problemleri için optimizasyon algoritmaları, doğrusal programlama algoritmalarına dayanmaktadır.

Optimizasyon sorunu amaç fonksiyonunun optimal (maksimum veya minimum) değerinin bulunmasından oluşan ve değişkenlerin değerlerinin belirli bir kabul edilebilir değerler aralığına ait olması gereken ekonomik ve matematiksel bir problemdir.

En genel haliyle doğrusal programlama problemi matematiksel olarak şu şekilde yazılır:

Nerede X = (x 1 , X 2 , ... , X N ) ; W– değişkenlerin izin verilen değerlerinin aralığı X 1 , X 2 , ... , X N ;f(X) – amaç fonksiyonu.

Bir optimizasyon problemini çözmek için optimal çözümünü bulmak yeterlidir; onu belirt her halükârda.

Bir optimizasyon problemi, eğer optimal bir çözümü yoksa çözülemez. Özellikle maksimizasyon problemi, amaç fonksiyonunun şu şekilde olması durumunda çözülemez olacaktır: f(X) kabul edilebilir kümede yukarıdan sınırlı değildir W.

Optimizasyon problemlerini çözme yöntemleri hem amaç fonksiyonunun türüne bağlıdır f(X) ve kabul edilebilir kümenin yapısından W. Problemdeki hedef fonksiyon bir fonksiyon ise N değişkenler varsa çözüm yöntemlerine matematiksel programlama yöntemleri denir.

Doğrusal programlama problemlerinin karakteristik özellikleri aşağıdaki gibidir:

optimallik indeksi f(X)çözüm elemanlarının doğrusal bir fonksiyonudur X = (x 1 , X 2 , ... , X N ) ;

Olası çözümlere uygulanan kısıtlayıcı koşullar, doğrusal eşitlikler veya eşitsizlikler biçimini alır.

Doğrusal programlama problemi matematiksel modeli şu şekilde olan yöneylem araştırması problemi olarak adlandırılır:

(2) (3)(4)(5)

Aynı zamanda sistem doğrusal denklemler(3) ve eşitsizlikler (4), (5), soruna kabul edilebilir çözüm kümesini belirler W, isminde kısıtlama sistemi doğrusal programlama problemleri ve doğrusal bir fonksiyon f(X) isminde hedef işlevi veya optimallik kriteri .

Geçerli çözüm sayıların bir koleksiyonudur ( plan ) X = (X 1 , X 2 , ... , X N ) , problemin kısıtlamalarını tatmin etmek. En uygun çözüm – bu, amaç fonksiyonunun maksimum (minimum) değerini aldığı bir plandır.

Doğrusal programlama probleminin matematiksel modeli şu şekilde ise:

sonra sorunun şu şekilde sunulduğunu söylüyorlar: kanonik form .

Herhangi bir doğrusal programlama problemi doğrusal programlama problemine indirgenebilir. kanonik form. Bunu yapmak için genel durumda maksimizasyon problemini minimizasyon problemine indirgemeniz gerekir; eşitsizlik kısıtlamalarından eşitlik kısıtlamalarına geçin ve negatif olmama koşuluna uymayan değişkenleri değiştirin. Belirli bir fonksiyonun maksimuma çıkarılması, zıt işaretle alınan aynı fonksiyonun minimuma indirilmesine eşdeğerdir ve bunun tersi de geçerlidir.

Doğrusal programlama problemini kanonik forma getirmenin kuralı aşağıdaki gibidir:

orijinal problemde doğrusal bir fonksiyonun maksimumunu belirlemek gerekiyorsa, işareti değiştirmeli ve bu fonksiyonun minimumunu aramalısınız;

kısıtlamalar varsa sağ kısım negatif ise bu limit -1 ile çarpılmalıdır;

kısıtlamalar arasında eşitsizlikler varsa, negatif olmayan ek değişkenler getirilerek bunlar eşitliğe dönüştürülür;

eğer bazı değişkenler X J işaret kısıtlaması yoksa, (amaç fonksiyonunda ve tüm kısıtlamalarda) negatif olmayan iki yeni değişken arasındaki farkla değiştirilir: X 3 = x 3 + -X 3 - , Nerede X 3 + , X 3 - ≥ 0 .

örnek 1. Doğrusal programlama problemini kanonik forma indirgemek:

en az L = 2x 1 +x 2 -X 3 ; 2 kere 2 -X 3 ≤ 5; X 1 +x 2 -X 3 ≥ -1; 2 kere 1 -X 2 ≤ -3; X 1 ≤ 0; X 2 ≥ 0; X 3 ≥ 0.

Kısıtlama sisteminin her denklemine seviyelendirme değişkenlerini dahil edelim X 4 , X 5 , X 6 . Sistem eşitlikler şeklinde yazılacak ve kısıtlar sisteminin birinci ve üçüncü denklemlerinde değişkenler yer alacaktır. X 4 , X 6 içine girilir Sol Taraf"+" işaretiyle ve ikinci denklemde değişken X 5 "-" işaretiyle girilir.

2 kere 2 -X 3 +x 4 = 5; X 1 +x 2 -X 3 -X 5 = -1; 2 kere 1 -X 2 +x 6 = -3; X 4 ≥ 0; X 5 ≥ 0; X 6 ≥ 0.

Kanonik formdaki serbest terimler pozitif olmalıdır; bunu yapmak için son iki denklemi -1 ile çarpın:

2 kere 2 -X 3 +x 4 = 5; -X 1 -X 2 +x 3 +x 5 = 1; -2 kere 1 +x 2 -X 6 = 3.

Doğrusal programlama problemlerinin çözümü için Simpleks yöntemi.

Simpleks yöntem algoritması, sınırlı sayıda uygun temel çözümü dikkate alarak en uygun çözümü bulur. Simpleks yöntemi algoritması her zaman bazı uygun temel çözümlerle başlar ve daha sonra amaç fonksiyonunun değerini "iyileştiren" başka bir uygun temel çözüm bulmaya çalışır. Bu ancak herhangi bir sıfır (temel olmayan) değişkendeki artışın amaç fonksiyonunun değerinde bir iyileşmeye yol açması durumunda mümkündür. Ancak temel olmayan bir değişkenin pozitif olabilmesi için mevcut temel değişkenlerden birinin sıfıra ayarlanması gerekir; temel olmayana dönüştürün. Yeni çözümün tam olarak içermesi için bu gereklidir. M temel değişkenler. Simpleks yönteminin terminolojisine uygun olarak seçilen sıfır değişkenine denir. giriş (tabana) ve silinecek temel değişken hariç tutuldu (temelden).

Simpleks yönteminde giriş ve dışlama değişkenlerini seçmek için iki kural çağıralım optimallik koşulu Ve kabul edilebilirlik koşulu . Bu kuralları formüle edelim ve ayrıca simpleks yöntemini uygularken gerçekleştirilen eylemlerin sırasını da göz önünde bulunduralım.

Optimallik koşulu. Maksimizasyon (minimizasyon) problemindeki girdi değişkeni, en büyük negatif (pozitif) katsayıya sahip olan temel olmayan bir değişkendir. hedef-astar. Eğer içindeyse hedef-line bu tür birkaç katsayı içeriyorsa, girilen değişkenin seçimi keyfi olarak yapılır. Optimum çözüme şu durumlarda ulaşılır: hedef-line, temel olmayan değişkenler için tüm katsayılar negatif olmayacaktır (pozitif olmayacaktır).

Kabul edilebilirlik koşulu. Hem maksimizasyon hem de minimizasyon problemlerinde, kısıtın sağ tarafının değerinin, ön sütunun pozitif katsayısına oranının minimum olduğu temel değişken, hariç tutulan değişken olarak seçilir. Bu özelliğe sahip birkaç temel değişken varsa, hariç tutulan değişkenin seçimi keyfidir.

Simpleks tabloları kullanarak bir maksimum bulma doğrusal programlama problemini çözmek için bir algoritma sunalım.

F = с 1 x 1 +с 2 x 2 +…+с n x n max

x 1 0, x 2 0,…, x n 0.

1. adım. Ek değişkenler ekliyoruz ve ortaya çıkan denklem sistemini ve doğrusal fonksiyonu genişletilmiş bir sistem biçiminde yazıyoruz.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.

2. adım. Başlangıç ​​simpleks tablosunu oluşturuyoruz.

3. adım. Optimallik kriterinin yerine getirilip getirilmediğini kontrol ediyoruz - son satır Negatif katsayılar. Hiçbiri yoksa, çözüm optimaldir ve F * =c o, temel değişkenler karşılık gelen b j katsayılarına eşittir, temel olmayan değişkenler sıfıra eşittir, yani X * =(b 1,b 2,…, b m, 0,…, 0).

4. adım. Optimallik kriteri karşılanmazsa, son (tahmini) satırdaki en büyük mutlak negatif katsayı, çözümleme sütunu s'yi belirler.

Çözüm çizgisini belirlemek için değerlendirme oranlarını hesaplıyoruz ve tablonun son sütununu doldurun.

İ'inci satırın tahmini oranı

 eğer b i ve a varsa farklı işaretler;

 eğer b i =0 ve a ise<0;

 a =0 ise;

0 eğer b i =0 ve a >0 ise;

Değerlendirme ilişkileri sütununda minimum öğeyi buluyoruz min bu, etkinleştirme dizesini tanımlar.

Minimum yoksa, problemin nihai optimumu yoktur ve çözülemezdir.

Çözen satır ve sütunun kesişiminde bir gs çözümleme elemanı vardır.

5. adım. Aşağıdaki tabloyu oluşturalım. Bunun için

Üçüncü adıma geçelim.

M-yöntemi Bazen bir ZLP'yi çözerken, bilinmeyen sistem kısıtlamaları için katsayılar matrisinde, bir birim matrisin oluşturulabileceği birim sütunlar bulunmaz; Temel değişkenlerin seçiminde bir sorun ortaya çıkar veya başlangıç ​​çözümü kabul edilemez. Bu gibi durumlarda kullanın yapay temel yöntemi (M - yöntemi). Temel değişkenlerin olmadığı tüm kısıtlamalarda, yapay değişkenler. Yapay değişkenler amaç fonksiyonuna maksimum problemler için bir katsayı (- M) ile ve min problemler için bir katsayı (+ M) ile dahil edilir; burada M yeterince büyük bir pozitif sayıdır. Daha sonra genişletilmiş problem simpleks yönteminin kuralları kullanılarak çözülür. Tüm yapay değişkenler sıfıra eşitse; temelden çıkarıldığında ya orijinal probleme optimal bir çözüm elde edilecek ya da orijinal problem daha da çözülerek optimal çözümü bulunacak ya da çözülemezliği ortaya konacaktır. Yapay değişkenlerden en az birinin sıfırdan farklı çıkması durumunda asıl problemin çözümü yoktur.

Ders 3. Simpleks tablolar. Simpleks yönteminin algoritması.

§ 3 SIMPLEX YÖNTEMİ

3.1. Simpleks yönteminin genel fikri. Geometrik yorumlama

Grafiksel yöntem, çok dar bir doğrusal programlama problemleri sınıfına uygulanabilir: ikiden fazla değişken içermeyen problemleri etkili bir şekilde çözebilir. Doğrusal programlamanın temel teoremleri dikkate alındı; buradan, eğer bir doğrusal programlama probleminin optimal bir çözümü varsa, o zaman çözüm çokyüzlüsünün en az bir köşe noktasına karşılık gelir ve kabul edilebilir temel çözümlerden en az biriyle çakışır. kısıtlama sistemi. Herhangi bir doğrusal programlama problemini çözmenin bir yolu gösterildi: Kısıtlamalar sisteminin sonlu sayıda uygulanabilir temel çözümlerini sıralamak ve bunlar arasından amaç fonksiyonunun optimal çözümü yapacağı çözümü seçmek. Geometrik olarak bu, çözüm çokyüzlüsünün tüm köşe noktalarının numaralandırılmasına karşılık gelir. Böylesine kapsamlı bir araştırma, en sonunda (varsa) optimal bir çözüme yol açacaktır, ancak bunun pratik uygulaması çok büyük zorluklarla ilişkilidir, çünkü gerçek problemler için uygulanabilir temel çözümlerin sayısı, sonlu olmasına rağmen son derece büyük olabilir.

Aramanın rastgele yapılmaması ancak doğrusal fonksiyondaki değişiklikler dikkate alınması durumunda, aranacak izin verilen temel çözümlerin sayısı azaltılabilir; Doğrusal fonksiyonun değerlerine göre her bir sonraki çözümün öncekinden “daha ​​iyi” (veya en azından “daha ​​kötü olmaması”) olmasını sağlamak (maksimum bulurken arttırmak, minimum bulurken azaltmak)
). Bu arama, optimumu bulurken adım sayısını azaltmanıza olanak tanır. Bunu grafiksel bir örnekle açıklayalım.

Bırakın alan kabul edilebilir çözümler bir çokgenle temsil edilir ABCDE. Diyelim ki köşe noktası A orijinal uygun temel çözüme karşılık gelir. Rastgele bir arama, poligonun beş köşe noktasına karşılık gelen beş uygun temel çözümün test edilmesini gerektirir. Ancak çizimden açıkça görülüyor ki, zirveden sonra A komşu bir köşeye geçmek avantajlıdır İÇİNDE, ve sonra en uygun noktaya İLE. Beş yerine yalnızca üç köşeden geçtik ve doğrusal fonksiyonu sürekli olarak geliştirdik.

Çözümü başarılı bir şekilde iyileştirme fikri, doğrusal programlama problemlerini çözmek için evrensel bir yöntemin temelini oluşturdu - Simpleks yöntemi veya planın sıralı olarak iyileştirilmesi yöntemi.

Simpleks yönteminin geometrik anlamı, kısıtlama çokyüzlüsünün bir köşesinden (ilk nokta olarak adlandırılır) komşuya sıralı bir geçişten oluşur; burada doğrusal fonksiyon, ilgili olarak en iyi (en azından en kötü değil) değeri alır. problemin amacı; optimal çözüm bulunana kadar - hedef fonksiyonunun optimal değerinin elde edildiği tepe noktası (eğer problemin nihai bir optimumu varsa).

Simpleks yöntemi ilk olarak 1949'da Amerikalı bilim adamı J. Danzig tarafından önerildi, ancak 1939'da yöntemin fikirleri Rus bilim adamı L.V. Kantoroviç.

Herhangi bir doğrusal programlama probleminin çözülmesine olanak sağlayan simpleks yöntemi evrenseldir. Şu anda bilgisayar hesaplamaları için kullanılıyor, ancak simpleks yöntemini kullanan basit örnekler manuel olarak çözülebilir.

Simpleks yöntemini uygulamak için - çözümün sıralı olarak iyileştirilmesi - ustalaşmak gerekir üç ana unsur:

bir problemin herhangi bir başlangıçtaki uygulanabilir temel çözümünü belirlemek için bir yöntem;

en iyi (daha doğrusu, daha kötü değil) çözüme geçiş kuralı;

Bulunan çözümün optimalliğini kontrol etme kriteri.

Simpleks yöntemini kullanmak için doğrusal programlama probleminin kanonik forma indirgenmesi gerekir; Kısıtlama sistemi denklemler şeklinde sunulmalıdır.

Literatür yeterince ayrıntılı olarak açıklanmaktadır: ilk destek planının bulunması (ilk kabul edilebilir temel çözüm), ayrıca yapay temel yönteminin kullanılması, en uygun destek planının bulunması, simpleks tabloların kullanılmasıyla problemlerin çözülmesi.

3.2. Simpleks yönteminin algoritması.

ZLP'nin çözümünü simpleks yöntemini kullanarak ele alalım ve bunu maksimizasyon problemiyle ilişkili olarak sunalım.

1. Problemin koşullarına göre matematiksel modeli derlenir.

2. Tamamlanan model kanonik forma dönüştürülür. Bu durumda, başlangıç ​​referans planına sahip bir temel belirlenebilir.

3. Sorunun kanonik modeli, tüm serbest terimlerin negatif olmamasını sağlayacak şekilde simpleks tablo biçiminde yazılmıştır. Başlangıç ​​referans planı seçilirse 5. adıma geçin.

Simpleks tablo: Kısıt denklemleri sistemi ve amaç fonksiyonu, başlangıç ​​esasına göre çözülmüş ifadeler biçiminde girilir. Amaç fonksiyonunun katsayılarını içeren bir çizgi
, isminde
– hedef işlevin bir dizesi veya dizesi.

4. Minimum simpleks ilişkilerine karşılık gelen pozitif çözümleyici elemanlarla ve elemanların işaretlerini dikkate almadan simpleks dönüşümleri gerçekleştirerek başlangıç ​​referans planını bulun.
–satırlar. Dönüşümler sırasında, serbest terim dışında tüm elemanları sıfır olan bir 0 satırıyla karşılaşılırsa, o zaman problemin kısıt denklemleri sistemi tutarsızdır. Serbest terim dışında başka pozitif unsurun bulunmadığı bir 0 satırıyla karşılaşırsak, kısıtlayıcı denklem sisteminin negatif olmayan çözümü yoktur.

(2.55), (2.56) sisteminin indirgenmesine yeni bir temel diyeceğiz. simpleks dönüşümü . Simpleks dönüşümü resmi bir cebirsel işlem olarak kabul edilirse, bu işlemin sonucunda rollerin belirli bir sisteme dahil olan iki değişken arasında yeniden dağıtıldığı fark edilebilir. doğrusal fonksiyonlar: Bir değişken bağımlıdan bağımsıza, diğeri ise tam tersine bağımsızdan bağımlıya gider. Bu işlem cebirde şu şekilde bilinir: Ürdün eleme adımı.

5. Bulunan başlangıç ​​destek planı optimallik açısından incelenir:

a) eğer
– satırda hiçbir olumsuz öğe yoksa (serbest süreyi saymazsak), o zaman plan optimaldir. Sıfır yoksa, o zaman tek bir optimal plan vardır; en az bir sıfır varsa, sonsuz sayıda optimal plan vardır;

b) eğer c
– satırda pozitif olmayan öğelerden oluşan bir sütuna karşılık gelen en az bir negatif öğe varsa, o zaman
;

c) eğer
– satırda en az bir negatif öğe varsa ve sütununda en az bir olumlu öğe varsa, o zaman optimal olana daha yakın olan yeni bir referans planına geçebilirsiniz. Bunu yapmak için, belirtilen sütunun minimum simpleks oranını kullanarak çözümleyen bir sütun olarak atanması, çözümlenen satırın bulunması ve bir simpleks dönüşümü gerçekleştirilmesi gerekir. Ortaya çıkan referans planı, optimallik açısından yeniden incelenir. Tanımlanan süreç, optimal bir plan elde edilene veya problemin çözülemezliği ortaya çıkana kadar tekrarlanır.

Temelde yer alan bir değişkenin katsayıları sütununa çözümleme denir. Böylece, negatif öğe tarafından tabana girilen bir değişkenin seçilmesi (veya bir çözümleme sütununun seçilmesi)
-strings, artan fonksiyon sağlıyoruz
.

Temelden çıkarılacak değişkenin belirlenmesi biraz daha zordur. Bunu yapmak için, serbest terimlerin çözümleme sütununun pozitif öğelerine oranlarını oluştururlar (bu tür ilişkilere simpleks denir) ve aralarında hariç tutulan değişkeni içeren satırı (çözümlemeyi) belirleyen en küçük olanı bulurlar. Minimum simpleks ilişkisine göre tabandan hariç tutulan bir değişkenin seçimi (veya çözümleme çizgisinin seçimi), daha önce de belirlendiği gibi, yeni referans planındaki temel bileşenlerin pozitifliğini garanti eder.

Algoritmanın 3. noktasında serbest terimler sütununun tüm öğelerinin negatif olmadığı varsayılmaktadır. Bu gereklilik gerekli değildir, ancak karşılanırsa, sonraki tüm simpleks dönüşümleri yalnızca hesaplamalar için uygun olan pozitif çözümleme elemanlarıyla gerçekleştirilir. Serbest terimler sütununda negatif sayılar varsa çözümleme elemanı şu şekilde seçilir:

1) örneğin bazı negatif serbest terimlere karşılık gelen çizgiye bakın – bir satır ve içindeki herhangi bir negatif öğeyi seçin ve karşılık gelen sütun çözümleyici olarak alınır (problemin kısıtlamalarının tutarlı olduğunu varsayarız);

2) serbest terimler sütununun öğelerinin, aynı işaretlere sahip çözümleme sütununun karşılık gelen öğeleriyle ilişkilerini oluşturmak (basit ilişkiler);

3) Simpleks ilişkilerin en küçüğünü seçin. Bu, etkinleştirme dizesini belirleyecektir. Mesela şöyle olsun R-astar;

4) çözümleyen sütun ve satırın kesişiminde bir çözümleyici öğe bulunur. Eğer öğe izin verici ise –strings ise simpleks dönüşümünden sonra bu stringin serbest terimi pozitif olacaktır. Aksi takdirde, bir sonraki adımda tekrar şuraya dönüyoruz: -astar. Sorun çözülebilirse, belirli sayıda adımdan sonra serbest terimler sütununda hiçbir olumsuz unsur kalmayacaktır.

Belirli bir gerçek üretim durumu PLP biçimine sokulursa, o zaman modelin kanonik biçime dönüştürülmesi sürecinde modele dahil edilmesi gereken ek değişkenlerin her zaman belirli bir ekonomik anlamı vardır.

Eğer problem cümlesi ≥ 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ımlayalım ve kısıtlamaları eşitlik formuna dönüştürelim

(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 olacak ve kısıtlamalar sistemine özel bir çözüm şu şekilde olacaktır:

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 aşağıdaki gibi temsil edebiliriz:

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

Başlangıç ​​simpleks tablosu (simpleks tablo 1), denklemler (2) ve (4) temel alınarak derlenir. Ek değişkenler x n+j'nin önüne (2)'deki gibi “+” işareti konulursa, xi değişkenlerinin ve serbest terim b j'nin önündeki tüm katsayılar değişiklik yapılmadan simpleks tabloya girilir. Hedef fonksiyonunu maksimize ederken katsayılar simpleks tablonun alt satırına zıt işaretlerle girilir. Simpleks tablodaki serbest terimler problemin çözümünü belirler.

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

1. adım. Ücretsiz üyeler sütununun üyeleri görüntülenir. Hepsi pozitifse, kabul edilebilir bir temel çözüm bulunmuştur ve algoritmanın en uygun çözümü bulmaya karşılık gelen 5. adımına geçilmelidir. Başlangıç ​​simpleks tablosunda negatif serbest terimler varsa çözüm geçerli değildir ve 2. adıma geçmelisiniz.

2. adım. Kabul edilebilir bir çözüm bulmak için gerçekleştirilir ve temel olmayan değişkenlerden hangisinin temele dahil edileceğine ve hangi değişkenin temelden çıkarılacağına karar verilmesi gerekir.

Tablo 1.

Bunu yapmak için, serbest terimler sütununun negatif elemanlarından herhangi birini seçin (önde gelen b 2 veya çözülen olsun. Negatif serbest terim içeren satırda hiçbir negatif eleman yoksa, o zaman kısıtlama sistemi tutarsızdır ve sorunun çözümü yok.

Aynı zamanda seçilen NP x l arttığında ilk işaret değiştiren değişken BP'nin dışında bırakılır. Bu, r endeksi koşuldan belirlenen x n+r olacaktır.

onlar. serbest terimin seçilen ön sütunun elemanına en küçük oranına sahip olan değişken. Bu ilişkiye denir simpleks ilişkisi. Yalnızca pozitif simpleks ilişkileri dikkate alınmalıdır.

x n+r değişkenine karşılık gelen satıra denir liderlik etmek veya izin vermek. Simpleks tablonun, ön sıra ile ön sütunun kesişiminde bulunan elemanına a rl, ön veya çözümleyici eleman denir. Baş elemanın bulunması, her normal simpleks tabloyla çalışmayı sonlandırır.

3. adım. Öğeleri önceki adımın simpleks tablosunun öğelerinden yeniden hesaplanan ve bir asal sayı ile işaretlenen yeni bir simpleks tablosu hesaplanır, yani. b" j , a" ji , c" i , F" 0 . Öğeler aşağıdaki formüller kullanılarak yeniden hesaplanır:

İlk olarak, yeni simpleks tablo, önceki simpleks tablonun başındaki satır ve sütunu dolduracaktır. İfade (5), baş eleman yerine a" rl elemanının önceki simpleks tablodaki elemanın tersine eşit olduğu anlamına gelir. a ri satırının elemanları baş elemana bölünür ve a ri satırının elemanları baş elemana bölünür ve a jl sütunu da baş elemana bölünür ancak ters işaretle alınır. b" r ve c" l elemanları aynı prensibe göre hesaplanır.

Formüllerin geri kalanı kullanılarak kolayca yazılabilir.

Dikdörtgen, eski simpleks tabloya göre, köşegenlerinden biri yeniden hesaplanan (a ji) ve öncü (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öşegendeki elemanların çarpımı baş elemana bölünür, a ji elemanından çıkarılır (bu, hücrenin yanındaki "-" işaretiyle gösterilir). b" j elemanları, (j≠r) ve c"i aynı şekilde yeniden hesaplanır. (i≠l).

4. adım. Yeni simpleks tablonun analizi algoritmanın 1. adımıyla başlar. Eylem, uygun bir temel çözüm bulunana kadar devam eder; kayan sütunun tüm elemanları pozitif olmalıdır.

5. adım. Kabul edilebilir bir temel çözümün bulunduğuna inanıyoruz. F(x) hedef fonksiyonu çizgisinin katsayılarına bakıyoruz. Simpleks tablonun optimalliğinin bir işareti, F satırındaki temel olmayan değişkenlere ilişkin katsayıların negatif olmamasıdır.

Pirinç. 1. Dikdörtgen kuralı

F satırının katsayıları arasında negatif olanlar varsa (serbest terim hariç), o zaman başka bir temel çözüme geçmeniz gerekir. Amaç fonksiyonunu maksimize ederken, temel, sütunu simpleks tablonun alt satırındaki negatif katsayı c l'nin maksimum mutlak değerine karşılık gelen temel olmayan değişkenlerden birini (örneğin x l) içerir. Bu, artışı hedef fonksiyonunda iyileşmeye yol açan değişkeni seçmenize olanak tanır. x l değişkenine karşılık gelen sütuna baş sütun denir. Aynı zamanda, r endeksi minimum simpleks ilişkisiyle belirlenen x n+r değişkeni temelin dışında bırakılır:

x n+r'ye karşılık gelen satıra satır başı adı verilir ve simpleks tablonun, satır ve satırdaki sütunun kesişiminde bulunan elemanı a rl olarak adlandırılır. öncü unsur.

6. adım. 3. adımda özetlenen kurallara göre. En uygun çözüm bulunana veya var olmadığı sonucuna varılıncaya kadar prosedür devam eder.

Çözüm optimizasyonu sırasında, eğer öndeki sütundaki tüm öğeler pozitif değilse, o zaman öndeki satır seçilemez. Bu durumda problemin uygun çözüm bölgesindeki fonksiyon yukarıda sınırlanmaz ve Fmax ->&∞ olur.

Bir ekstremumu aramanın bir sonraki adımında, temel değişkenlerden biri sıfıra eşit olursa, o zaman karşılık gelen temel çözüme dejenere denir. Bu durumda, aynı BP kombinasyonunun belirli bir frekansta tekrarlanmaya başlaması (F fonksiyonunun değeri korunur) ve yeni bir uygulanabilir temel çözüme geçmenin imkansız olmasıyla karakterize edilen sözde bir döngü meydana gelir. . Döngü, simpleks yönteminin temel dezavantajlarından biridir ancak nispeten nadirdir. Uygulamada, bu gibi durumlarda, genellikle sütunu hedef fonksiyonundaki negatif katsayının maksimum mutlak değerine karşılık gelen değişkeni tabana girmeyi reddederler ve rastgele yeni bir temel çözüm seçerler.

Örnek 1. Sorunu çö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öntemini kullanarak çözüm sürecinin geometrik yorumunu vermek.

Sorunun çözümünün grafiksel yorumu Şekil 1'de sunulmaktadır. 2. Hedef fonksiyonunun maksimum değeri ODZP'nin tepe noktasında koordinatlarla elde edilir. Simpleks tabloları kullanarak sorunu çözelim. İkinci kısıtı (-1) ile çarpalım ve eşitsizlikleri eşitlik formuna getirecek ek değişkenler ekleyelim, sonra

Başlangıç ​​değişkenleri x 1 ve x 2'yi temel olmayan olarak alıyoruz ve ek x 3, x 4 ve x 5'i temel olarak kabul edip bir simpleks tablo oluşturuyoruz (simplex tablo 2). Simpleks tabloya karşılık gelen çözüm. 2, geçerli değil; öncü elemanın ana hatları çizilir ve önceki algoritmanın 2. adımına göre seçilir. Aşağıdaki simpleks tablo. Şekil 3, kabul edilebilir bir temel çözümü tanımlar; Şekil 1'deki ODZP'nin tepe noktası buna karşılık gelir. 2 Öncü öğenin ana hatları çizilir ve problem çözme algoritmasının 5. adımına uygun olarak seçilir. Masa 4, problemin en uygun çözümüne karşılık gelir, dolayısıyla: x 1 = x 5 = 0; x2 = 4; x3 = 3; x4 = 8; Fmaks = 20.

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

Burada, simpleks yöntemini kullanarak problem çözme algoritmasını anlamak için ayrıntılı açıklamalarla birlikte simpleks yöntemini (applet çözümüne benzer) kullanan iki problemin manuel (applet değil) çözümü bulunmaktadır. İlk problem sadece “≤” eşitsizlik işaretlerini içeriyor (başlangıç ​​temelli problem), ikincisi “≥”, “≤” veya “=” (yapay temelli problem) işaretlerini içerebilir, farklı şekilde çözülürler.

Simpleks yöntemi, bir problemi başlangıç ​​esasına göre çözme

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

Sorunu yazalım kanonik form, yani Eşitsizlik kısıtlamalarını eşitlikler biçiminde yeniden yazıyoruz; bilanço değişkenler:

Bu sistem temelleri (temel s 1, s 2, s 3, her biri 1 katsayısı ile sistemin sadece bir denkleminde yer alan), x 1 ve x 2 serbest değişkenleri olan bir sistemdir. Simpleks yöntemi kullanılarak çözülecek problemler aşağıdaki iki özelliğe sahip olmalıdır: - Kısıtlamalar sistemi, temeli olan bir denklemler sistemi olmalıdır; -Sistemdeki tüm denklemlerin serbest terimleri negatif olmamalıdır.

Ortaya çıkan sistem, temeli olan bir sistemdir ve serbest şartları negatif değildir, dolayısıyla uygulayabiliriz. simpleks yöntemi. Sorunu çözmek için ilk simpleks tabloyu (Yineleme 0) oluşturalım. simpleks yöntemi yani amaç fonksiyonunun katsayılarının bir tablosu ve karşılık gelen değişkenler için bir denklem sistemi. Burada “BP” temel değişkenlerin sütunu, “Çözüm” ise sistem denklemlerinin sağ taraflarının sütunu anlamına gelir. Çözüm optimal değil çünkü z satırında negatif katsayılar vardır.

simpleks yöntemi yinelemesi 0

Çözümü iyileştirmek için bir sonraki yinelemeye geçelim simpleks yöntemi aşağıdaki simpleks tabloyu elde ederiz. Bunu yapmak için seçmeniz gerekir sütunu etkinleştir yani simpleks yönteminin bir sonraki yinelemesinde temele dahil edilecek bir değişken. Z satırındaki (maksimum problemde) en büyük mutlak negatif katsayıya göre seçilir - simpleks yönteminin ilk yinelemesinde bu, x 2 sütunudur (katsayı -6).

Sonra seçin dizeyi etkinleştir yani simpleks yönteminin bir sonraki yinelemesinde temel oluşturacak bir değişken. "Karar" sütununun, çözünürlük sütununun karşılık gelen pozitif öğelerine ("Oran" sütunu) en küçük oranıyla seçilir - ilk yinelemede bu, s 3 satırıdır (katsayı 20).

İzin verici unsurçözümleme sütunu ile çözümleme satırının kesişme noktasındadır, hücresi renkli olarak vurgulanır, 1'e eşittir. Bu nedenle, simpleks yönteminin bir sonraki yinelemesinde, x 2 değişkeni temelde s 1'in yerini alacaktır. İlişkinin z-dizgesinde aranmadığını unutmayın; buraya bir tire “-” konur. Eğer aynı minimal ilişkiler varsa bunlardan herhangi biri seçilir. Çözünürlük sütunundaki tüm katsayılar 0'dan küçük veya ona eşitse, problemin çözümü sonsuzdur.

Aşağıdaki “Yineleme 1” tablosunu dolduralım. Bunu “Yineleme 0” tablosundan alacağız. Daha sonraki dönüşümlerin amacı x2 çözünürlük sütununu bir birim sütuna dönüştürmektir (çözünürlük öğesi yerine bir ve geri kalan öğeler yerine sıfırlar).

1) “Yineleme 1” tablosunun satır x 2'sini hesaplayın. İlk olarak, “Yineleme 0” tablosunun çözümleme satırı s 3'ün tüm üyelerini çözümleme elemanına böleriz (bu, 1'e eşittir). bu durumda) bu tablonun "Yinelemeler 1" tablosundaki satır x 2'yi elde ederiz. Çünkü bu durumda çözümleme elemanı 1'e eşitse, "Yineleme 0" tablosunun 3. satırı "Yineleme 1" tablosunun x 2 satırıyla çakışacaktır. Aldığımız Iteration 1 tablosunun satır x 2'si 0 1 0 0 1 20, Iteration 1 tablosunun geri kalan satırları bu satırdan elde edilecek ve Iteration 0 tablosunun satırları aşağıdaki gibi olacaktır:

2) “Yineleme 1” tablosunun z satırının hesaplanması. Yineleme 0 tablosunun x2 sütunundaki ilk satırdaki (z satırı) -6 yerine, Yineleme 1 tablosunun ilk satırında 0 bulunmalıdır. Bunu yapmak için, "Yineleme 1" 0 1 0 0 1 20 tablosunun x 2 satırının tüm elemanlarını 6 ile çarpın, 0 6 0 0 6 120 elde ederiz ve bu satırı ilk satıra (z - satır) ekleriz "Yineleme 0" -4 -6 0 0 0 0 tablosundan -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 x 2'nin öğeleri kırmızı renkle vurgulanır.

3) “Yineleme 1” tablosunun 1. satırının hesaplanması. “Yineleme 0” tablosunun s 1 satırındaki 1 yerine “Yineleme 1” tablosunda 0 olmalıdır. Bunu yapmak için, "Yineleme 1" 0 1 0 0 1 20 tablosunun x 2 satırının tüm elemanlarını -1 ile çarpın, 0 -1 0 0 -1 -20 elde edin ve bu satırı s 1 - satırıyla ekleyin "Yineleme 0" 2 1 1 0 0 64 tablosunda, 2 0 1 0 -1 44 satırını elde ederiz. x 2 sütununda gerekli 0'ı elde ederiz.

4) “Yineleme 1” tablosunun 2. satırını hesaplayın. "Yineleme 0" tablosunun 2. satırındaki 3. yerde "Yineleme 1" tablosunda 0 olmalıdır. Bunu yapmak için, "Yineleme 1" 0 1 0 0 1 20 tablosunun x 2 satırının tüm elemanlarını -3 ile çarpın, 0 -3 0 0 -3 -60 elde ederiz ve bu satırı s 1 - satır ile ekleriz "Yineleme 0" tablosunda 1 3 0 1 0 72, 1 0 0 1 -3 12 satırını elde ederiz. x 2 sütununda gerekli 0 elde edilir. “Yineleme 1” tablosundaki x 2 sütunu şu şekilde olur: Birim, biri 1, geri kalanı 0'dan oluşur.

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

Yeni satır = Eski satır – (Eski satır çözünürlük sütunu katsayısı)*(Yeni çözünürlük satırı).

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

Eski z-string (-4 -6 0 0 0 0) -(-6)*Yeni çözümleme dizisi -(0 -6 0 0 -6 -120) =Yeni z-string (-4 0 0 0 6 120).

Aşağıdaki tablolarda tablo elemanlarının yeniden hesaplanması benzer şekilde yapıldığı için bunu atladık.

simpleks yöntemi yinelemesi 1

x 1 sütununun çözümlenmesi, s 2 satırının çözülmesi, s 2 tabanının çözülmesi, x 1 tabanının çözülmesi. Tamamen aynı şekilde, z satırındaki tüm pozitif katsayıları içeren bir tablo elde edene kadar geri kalan simpleks tabloları elde ederiz. Bu optimal bir tablonun işaretidir.

simpleks yöntemi yinelemesi 2

Sütun s 3 çözümlendiğinde, satır s 1, s 1 çözümlendiğinde tabandan çıkar, s 3 tabana girer.

simpleks yöntemi yinelemesi 3

Z satırında tüm katsayılar negatif değildir, dolayısıyla x 1 = 24, x 2 = 16, z max = 192 optimal çözümü elde edilir.