11.4. ÇİFT SIMPLEX YÖNTEMİ
Önceki bölümlerin sonuçlarından, orijinal probleme bir çözüm elde etmek için ikili probleme geçebileceğimizi ve optimal tasarımının tahminlerini kullanarak orijinal problemin optimal çözümünü belirleyebileceğimizi izler.
İkili probleme geçiş gerekli değildir, çünkü bir birim ek bazına sahip ilk simpleks tabloyu düşünürsek, o zaman sütunların orijinal problemi içerdiğini ve ikili problemin satırlarda yazıldığını görmek kolaydır.
Gösterildiği gibi, herhangi bir yinelemede doğrudan problemi çözerken, fark, yani büyüklük -değişkenli katsayı, ikili problemin karşılık gelen kısıtının sağ ve sol tarafları arasındaki farka eşittir. Maksimize edilebilir bir amaç fonksiyonu ile doğrudan bir problem çözülürken, yineleme optimal bir çözüme yol açmazsa, o zaman en az bir değişken için ve sadece herkes için optimumda fark .
Bu durumu dualiteyi de göz önünde bulundurarak şöyle yazabiliriz:
.
Böylece, eğer, sonra . Bu, birincil problemin çözümü optimal olmadığında, ikili problemin çözümünün geçersiz olduğu anlamına gelir. Diğer taraftan 
. Bu, birincil problemin optimal çözümünün, ikili problemin kabul edilebilir bir çözümüne karşılık geldiği anlamına gelir.
Bu, başlangıçta kabul edilemez, ancak “optimumden daha iyi” bir çözümün elde edildiği doğrusal programlama problemlerini çözmek için yeni bir yöntem geliştirmeyi mümkün kıldı (olağan simpleks yönteminde, önce kabul edilebilir, ancak standart altıçözüm). adı verilen yeni bir yöntem ikili simpleks yöntemi, çözüm optimallik koşulunun yerine getirilmesini ve uygulanabilir çözümler alanına sistematik “yaklaşımını” sağlar. Elde edilen çözümün kabul edilebilir olduğu ortaya çıktığında, bu çözüm de optimal olduğu için yinelemeli hesaplama süreci sona erer.
İkili simpleks yöntemi, pozitif bir temele sahip kısıtlama sistemleri herhangi bir işaretin serbest terimlerini içeren doğrusal programlama problemlerinin çözülmesine izin verir. Bu yöntem, tek yönlü tablonun boyutunun yanı sıra kısıtlama sistemi dönüşümlerinin sayısını azaltmayı mümkün kılar. Bir örnek kullanarak ikili simpleks yönteminin uygulamasını düşünün.
Örnek. Bir fonksiyonun minimumunu bulun 
kısıtlamalar altında
.
Kanonik forma geçelim:
kısıtlamalar altında
İlk simpleks tablosu şu şekildedir:
|
Temel değişkenler |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Çözüm |
|
x 3 x 4 x 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
İlk temel çözümoptimal, ancak kabul edilebilir değil.
Her zamanki simpleks yöntemi gibi, söz konusu çözüm yöntemi de kabul edilebilirlik ve optimallik koşullarının kullanımına dayanmaktadır.
Kabul edilebilirlik koşulu. Mutlak değerdeki en büyük negatif temel değişken, hariç tutulan değişken olarak seçilir (alternatifler varsa, seçim keyfi yapılır). Tüm temel değişkenler negatif değilse, elde edilen çözüm uygulanabilir ve optimal olduğu için hesaplama süreci sona erer.
Şart optimallik. Baza dahil edilen değişken, temel olmayan değişkenler arasından aşağıdaki gibi seçilir. Sol tarafın katsayılarının oranları hesaplanır- hariç tutulan değişkenle ilişkili denklemin karşılık gelen katsayılarına denklemler. Pozitif veya sıfır paydalı ilişkiler dikkate alınmaz. Girdi değişkeninin minimizasyonu probleminde, belirtilen oranların en küçüğü, maksimizasyon probleminde en küçük mutlak değere sahip oran (alternatifler varsa, seçim keyfi olarak yapılır) karşılık gelmelidir. Tüm oranların paydaları sıfır veya pozitif ise, problemin uygulanabilir bir çözümü yoktur.
Temele dahil edilecek ve hariç tutulacak değişkenler seçildikten sonra, bir sonraki çözümü elde etmek için simpleks tablonun satırlarını dönüştürmenin olağan işlemi gerçekleştirilir.
Bu örnekte, hariç tutulan değişken. Yeni baz değişkeni belirlemek için hesaplanan oranlar aşağıdaki tabloda gösterilmiştir:
|
Değişkenler |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
denklem x 4 - denklem |
–2 –4 |
–1 –3 |
|||
|
Davranış |
Dahil edilecek değişken, x 2. Sonraki dize dönüştürme, yeni bir tek yönlü tabloyla sonuçlanır:
|
Temel değişkenler |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Çözüm |
|
x 3 x 2 x 5 |
–1 –1 |
|||||
Yeni Çözüm ayrıca optimal, ancak yine de geçersiz. Yeni bir hariç tutulan değişken olarak, (keyfi olarak) x 3. Dahil edilen bir değişken tanımlayalım.
|
Değişkenler |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
denklem x 4 - denklem |
|||||
|
davranış |
Simpleks yöntemi - bu, bir doğrusal programlama probleminin kısıtlamalar sisteminin bir temel çözümünden (çözüm polihedronunun tepe noktası), hedef fonksiyonu optimal değeri (maksimum veya minimum) alana kadar başka bir temel çözüme art arda geçiş yöntemidir.
Simpleks yöntemi, herhangi bir sorunu çözebilen evrensel bir yöntemdir. doğrusal programlama problemi, grafiksel yöntem ise yalnızca iki değişkenli bir kısıtlama sistemi için uygundur.
Simpleks yöntemi 1947'de Amerikalı matematikçi R. Danzig tarafından önerildi, o zamandan beri endüstrinin ihtiyaçları için bu yöntem genellikle binlerce değişken ve kısıtlama ile doğrusal programlama problemlerini çözüyor.
Simpleks yöntem algoritmasına geçmeden önce birkaç tanım.
Bir kısıtlar sistemine negatif olmayan herhangi bir çözüm denir. kabul edilebilir çözüm .
Bir sistem olsun m kısıtlamalar n değişkenler ( m n).
Kabul edilebilir temel çözüm içeren bir çözümdür m negatif olmayan ana (temel ) değişkenler ve n - m çekirdek olmayan . (temel olmayan veya Bedava ) değişkenler. Temel çözümdeki temel olmayan değişkenler sıfıra eşittir, ana değişkenler ise kural olarak sıfır değildir, yani pozitif sayılardır.
Hiç m sistem değişkenleri m lineer denklemler n değişkenler denir ana , içlerindeki katsayıların determinantı sıfırdan farklıysa. Sonra geri kalanı n - m değişkenler denir çekirdek olmayan (veya Bedava ).
Simpleks Yöntem Algoritması
- Aşama 1. Doğrusal programlama problemini kanonik forma getirin. Bunu yapmak için, serbest terimleri sağ tarafa taşıyın (bu serbest terimler arasında negatifse, karşılık gelen denklemi veya eşitsizliği - 1 ile çarpın) ve her kısıtlamaya ek değişkenler ekleyin (eğer varsa artı işaretiyle). orijinal eşitsizlik işareti "'den küçük veya eşittir ve "büyük veya eşit" ise eksi işaretiyle).
- Adım 2. Ortaya çıkan sistemde ise m denklemler, o zaman m değişkenleri ana değişkenler olarak alın, ana değişkenleri temel olmayanlar cinsinden ifade edin ve karşılık gelen temel çözümü bulun. Bulunan temel çözümün kabul edilebilir olduğu ortaya çıkarsa, kabul edilebilir temel çözüme gidin.
- Aşama 3. Amaç fonksiyonunu uygun temel çözümün küçük değişkenleri cinsinden ifade edin. Doğrusal formun maksimumu (minimumu) bulunursa ve ifadesinde negatif (pozitif) katsayılı temel olmayan değişkenler yoksa, optimallik kriteri karşılanır ve ortaya çıkan temel çözüm optimaldir - çözüm biter. Doğrusal bir formun maksimum (minimum) değerini bulurken, ifadesi negatif (pozitif) katsayılı bir veya daha fazla temel olmayan değişken içeriyorsa, yeni bir temel çözüme gidin.
- 4. Adım. Negatif (pozitif) katsayılarla doğrusal formda yer alan temel olmayan değişkenlerden en büyük (modulo) katsayıya karşılık gelen birini seçin ve ana olanlara aktarın. 2. adıma gidin.
Önemli koşullar
Bazı özel durumlar ayrı makalelerde tartışılmaktadır: ne zaman maksimum amaç fonksiyonu - sonsuzluk, ne zaman sistemin çözümü yok, ve ne zaman optimal çözüm tek çözüm değil .
Ardından, kısıtlamalar sistemi tutarlı olduğunda ve sonlu bir optimum ve yalnızca bir tane olduğunda tipik bir örneği analiz edeceğiz. Simpleks yönteminin bir varyasyonu taşıma sorununu çözmek için dağıtım yöntemi .
Simpleks tablolarla Simplex yöntemi
Simpleks tablolar oluşturarak, bir sonraki paragrafta gösterilen cebirsel dönüşümlerden ziyade bir doğrusal programlama problemini çözmek çok daha kolaydır. Simplex tablolar çok görseldir. Simpleks tablolarla çalışmak için birkaç tür kural vardır. En sık olarak önde gelen sütun ve önde gelen satır kuralı olarak adlandırılan kuralı analiz edeceğiz.
Kesirli manuel Eylemleri yeni bir pencerede açmak faydalı olacaktır: bunlardan yeterince var, basit bir şekilde söylemek gerekirse, simpleks yöntemindeki problemlerde kesirler.
Örnek.
Ek negatif olmayan değişkenler ekleriz ve bu eşitsizlik sistemini eşdeğer bir denklem sistemine indirgeriz.
.
Bu, şu kurala uygun olarak yapılmıştır: orijinal kısıtlamadaki işaret "küçük veya eşittir" ise, ek değişken eklenmelidir ve "büyük veya eşittir" ise, ek değişken olmalıdır. çıkarıldı.
Girilen ek değişkenler ana (temel) olarak alınır. Sonra ve temel olmayan (serbest) değişkenlerdir.
Ana (temel) değişkenleri temel olmayan (serbest) terimlerle ifade edersek, şunu elde ederiz:
Ayrıca amaç fonksiyonunu temel olmayan (serbest) değişkenler cinsinden ifade ederiz:
Değişkenlerin (bilinmeyenlerin) katsayılarından ilk tek yönlü tabloyu oluşturuyoruz.
| tablo 1 | ||||
| Temel bilinmeyenler | Ücretsiz üyeler | Gevşek bilinmeyenler | yardımcı katsayılar | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
Amaç fonksiyonunu ve içindeki serbest değişkenlerin katsayılarını içeren tablonun son satırına indeks satırı adı verilecektir.
İndeks satırındaki serbest değişkenlerin katsayıları negatif olduğu için ortaya çıkan çözüm optimal değildir. Yani optimal çözüm, indeks satırındaki serbest değişkenlerin katsayılarının sıfırdan büyük veya sıfıra eşit olacağı çözüm olacaktır.
Bir sonraki tabloya gitmek için sayıların en büyüğünü (modulo) bulun ve . Bu sayı 2'dir. Bu nedenle, önde gelen sütun, yazıldığı sütundur.
Baştaki satırı belirlemek için, serbest üyelerin önde gelen sütunun öğelerine oranlarının minimumunu buluruz ve pay pozitif bir sayıya sahipse ve payda negatifse, oran sonsuza eşit kabul edilir.
.
Bu nedenle, önde gelen satır, yazıldığı satırdır.
Öncü eleman böylece -2'dir.
İkinci simpleks tabloyu oluşturuyoruz.
Yeni temel öğeyi ilk satıra giriyoruz ve bulunduğu sütuna giriyoruz, yeni bir serbest değişken giriyoruz
İlk satırı doldurun. Bunu yapmak için, tablo 1'in önde gelen satırındaki tüm sayıları önde gelen elemana böleriz ve baştaki sütunun tersinin bulunduğu önde gelen sütundaki sayı hariç, tablo 2'nin ilk satırının ilgili sütununa yazarız. eleman yazılır (yani, önde gelen elemana bölünür).
Yardımcı katsayılar sütununu doldurun. Tablo 1'in önde gelen sütununun bu sayısı için, önde gelen elemana ek olarak, tablo 2'nin yardımcı katsayıları sütununda zıt işaretlerle yazıyoruz.
| Tablo 2 | ||||
| Temel bilinmeyenler | Ücretsiz üyeler | Gevşek bilinmeyenler | yardımcı katsayılar | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
Kesirli İşlemler manuelini henüz yeni bir pencerede açmamış olanlar şimdi yapabilir, çünkü zamanı geldi.
Tablo 2'nin kalan satırlarını elde etmek için, bu tablonun ilk satırında zaten bulunan sayılar, doldurulan satırdaki yardımcı katsayı ile çarpılır ve sonuca, aynı satırda bulunan tablo 1'deki sayıyı ekleriz. karşılık gelen değişken.
Örneğin, ikinci satırın boş üyesini almak için 1 sayısını 1 ile çarparız ve tablo 1'den -4 sayısını ekleriz. -3 alırız. İkinci satırdaki katsayısını da aynı şekilde buluyoruz: 
. Bir önceki tabloda yeni bir serbest değişkenli sütun olmadığı için yeni serbest değişkenin sütunundaki ikinci satırın katsayısı 
(yani, tablo 1'de c sütunu olmadığı için tablo 1'den 0 ekliyoruz).
Dizin satırı aynı şekilde doldurulur:
İndeks satırındaki serbest değişkenlerin katsayıları yine negatif olduğundan, bu şekilde elde edilen çözüm yine optimal değildir.
Bir sonraki tek yönlü tabloya geçmek için indeks satırındaki sayıların en büyüğünü (modulo) ve yani katsayıların modüllerini bulalım. Bu sayı 2'dir. Bu nedenle, önde gelen sütun, içeren sütundur.
Baştaki satırı aramak için, en az boş üyelerin önde gelen satırın öğelerine oranını bulalım. Alırız:
.
Bu nedenle, baştaki satır yazılı olandır ve önde gelen eleman -3/2'dir.
Üçüncü tek yönlü tablonun derlenmesi
Yeni temel değişkeni ilk satıra yazıyoruz. Bulunduğu sütuna yeni bir serbest değişken giriyoruz.
İlk satır:
Yardımcı katsayılar:
| Tablo 3 | ||||
| Temel bilinmeyenler | Ücretsiz üyeler | Gevşek bilinmeyenler | yardımcı katsayılar | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
İndeks satırındaki serbest bilinmeyenlerin katsayıları yine negatif olduğu için ortaya çıkan çözüm yine optimal değildir.
Dördüncü tek yönlü tabloya gitmek için sayıların en büyüğünü bulalım ve . Bu bir numara.
Bu nedenle, önde gelen sütun .
Serbest üyelerin önde gelen sütunun öğelerine minimum ilişki modülü:
.
Bu nedenle, önde gelen satır yazılı olandır ve önde gelen eleman 1/3'tür.
Dördüncü simpleks tablosunda ilk satıra yeni temel değişkeni yazıyoruz. Bulunduğu sütuna yeni bir serbest değişken yazıyoruz.
İlk satır:
Yardımcı katsayılar:
| Tablo 4 | ||||
| Temel bilinmeyenler | Ücretsiz üyeler | Gevşek bilinmeyenler | yardımcı katsayılar | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
İkinci satır örneğini kullanarak kalan satırların hesaplanması:
Ortaya çıkan çözüm de optimal değil, ancak dizin satırındaki serbest değişkenlerin katsayılarından biri negatif olmadığı için öncekilerden zaten daha iyi.
Planı geliştirmek için bir sonraki tek yönlü tabloya geçelim.
4 ve sayılarının en büyüğünü bulun. Bu sayı 4'tür. Bu nedenle, önde gelen sütun .
Baştaki satırı bulmak için
.
Bu nedenle, önde gelen satır içeren satırdır. Ama serbest değişkenler arasında zaten birlikteydiler. Bu nedenle, bir sonraki değişkeni serbestten temele aktarmak için, içinde yazılı olan başka bir önde gelen sütun seçeriz.
Baştaki satırı bulmak için
.
Bu nedenle, anahtar satır, içinde yazılı olandır ve önde gelen eleman 1'dir.
Beşinci tek yönlü tabloda ilk satıra yeni temel değişken yazılır. Bulunduğu sütuna yeni bir serbest değişken yazıyoruz.
İlk satır:
Yardımcı katsayılar:
| Tablo 5 | ||||
| Temel bilinmeyenler | Ücretsiz üyeler | Gevşek bilinmeyenler | yardımcı katsayılar | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
Çözümün optimal olup olmadığını hemen bulmaya çalışalım. Bu nedenle, kalan satırlar için sadece serbest terimleri (serbest değişkenler sıfıra eşit olduğunda temel değişkenlerin değerlerini bulmak için) ve indeks satırındaki serbest değişkenler için katsayıları hesaplıyoruz.
Ücretsiz üyeler:
İkinci satırda;
Üçüncü satırda;
Dördüncü satırda.
Dizin satırı:
Simpleks tablo 5'e bakıyoruz. İndeks satırındaki serbest bilinmeyenler için katsayılar negatif olmadığı için optimal çözümün elde edildiğini görüyoruz.
Cebirsel dönüşümlerle Simplex yöntemi
Bir önceki paragraftakiyle aynı örneği cebirsel dönüşümlerle çözelim. Unutulmamalıdır ki bu tip bir simpleks yöntemi çözerken, amaç fonksiyonunu formda yazmamak daha iyidir. , çünkü işaretlerde kafa karıştırmak kolaydır. Ancak bu durumda algoritmanın optimallik kriterini belirleyen noktası aşağıdaki gibi değiştirilecektir.
Doğrusal formun maksimumu (minimumu) bulunursa ve ifadesinde pozitif (negatif) katsayılı temel olmayan değişkenler yoksa, optimallik kriteri karşılanır ve ortaya çıkan temel çözüm optimaldir - çözüm biter. Doğrusal bir formun maksimum (minimum) değerini bulurken, ifadesi pozitif (negatif) katsayılı bir veya daha fazla temel olmayan değişken içeriyorsa, yeni bir temel çözüme gidin.
Örnek. Kısıtlamalar altında bir fonksiyonun maksimumunu bulun
Adım I. Ek negatif olmayan değişkenler ekler ve bu eşitsizlik sistemini eşdeğer bir denklem sistemine indirgeriz
.
Girilen ek değişkenler ana değişkenler olarak alınır, çünkü bu durumda sistemin temel çözümü kolayca bulunur. Sonra ve minör değişkenlerdir.
Ana değişkenleri temel olmayanlar cinsinden ifade edersek,
Sonuç olarak, değişkenlerin bu temel ve temel olmayan olarak bölünmesi, temel çözüme karşılık gelir. 
geçersizdir (iki değişken negatiftir) ve bu nedenle optimal değildir. Bu temel çözümden geliştirilmiş bir çözüme geçelim.
Hangi değişkenin anaparadan anaparaya aktarılması gerektiğine karar vermek için, son sistemin mevcut iki denkleminden birini negatif serbest terimli, örneğin ikincisini düşünün. Bu denklemde pozitif katsayılara sahip oldukları için ana değişkenlere çevrilebileceğini ve çevrilebileceğini gösterir (bu nedenle, arttığında ve bunlardan herhangi birini ana değişkenlere çevirirsek, değişken artacaktır).
Ana değişkene çevirmeye çalışalım. Hangi değişkenin temelden temel olmayana aktarılması gerektiğini belirlemek için, sistemin serbest üyelerinin en küçük oranının katsayılara oranının mutlak değerini . Sahibiz . Değişkenin orijinal temel çözümde pozitif olan temel olmayanlara dönüştürülmesi gerektiğini gösteren üçüncü denklemden elde edilir. Sonuç olarak, elde edilen temel çözüm, orijinali gibi, iki olumsuz bileşen içerir, yani böyle bir temel çözüme geçişte herhangi bir gelişme olmayacaktır.
Simpleks yöntemi- referans planların sıralı bir şekilde sıralanması yöntemidir (sıralama, sonraki plana geçiş sırasında amaç fonksiyonunun değerindeki monoton bir değişiklikle sağlanır). Bu durumda, ilkeyi gözlemlemek gerekir: sonraki her adım, amaç fonksiyonunun değerini iyileştirmeli veya aşırı durumlarda kötüleştirmemelidir.
LLP'yi çözmek için tek yönlü yöntem kanonik forma indirgenir, yani. kısıtlamalardan - eşitsizliklerden - kısıtlamalar yapmak gerekir - eşitlikler. Bunu yapmak için, her kısıtlama, negatif olmayan ek bir ek ile desteklenir. bilanço değişkeni eşitsizlik işareti “£” ise “+”, eşitsizlik işareti “³” ise “–” işareti ile gösterilir.
Amaç fonksiyonunda, bu ek değişkenler sıfır katsayı ile girer, yani. hedef fonksiyon girişi değişmeyecektir. Negatif olmama koşuluna tabi olmayan her değişken, negatif olmayan iki değişkenin farkı olarak gösterilebilir: .
Görev kısıtlamaları kaynakların varlığını ve tüketimini yansıtıyorsa, görev planındaki ek değişkenin kurallı biçimde yazılmış sayısal değeri, kullanılmayan kaynak miktarına eşittir.
Problemi simpleks yöntemiyle çözmek için kullanacağız lineer denklemler sisteminin kısaltılmış simpleks tabloları ve değiştirilmiş Jordan eliminasyon yöntemi.
1. İlk temel planı hazırlıyoruz
Görev aynı kalır. Eşitsizlikler sisteminin (1) standart biçimini, ek denge değişkenleri ekleyerek denklem sisteminin kanonik biçimine getirelim. x 3 , x 4 , x 5 ,x 6 .
Ekonomik anlamda, ek değişkenlerin değerleri x 3 , x 4 , x 5 Ürünlerin satışından sonra hammadde dengesini belirler.
Ortaya çıkan denklem sisteminin matrisi şu şekildedir:
Görüldüğü gibi matriste A 4. mertebenin temel minörü, ek değişkenler için birim katsayılardan oluşan determinanttır. x 3 , x 4 , x 5 ,x 6, sıfır olmadığı ve 1'e eşit olduğu için. Bu, bu değişkenler için sütun vektörlerinin doğrusal olarak bağımsız olduğu anlamına gelir, yani. biçim temel, ve karşılık gelen değişkenler x 3 , x 4 , x 5 ,x 6 temel(temel). Değişkenler x 1 , x 2 çağrılacak Bedava(küçük).
Serbest değişkenler ise x 1 ve x 2 farklı değerler ayarlamak için, daha sonra sistemi temel değişkenlere göre çözerek, sonsuz bir özel çözümler kümesi elde ederiz. Serbest değişkenler için yalnızca sıfır değerler ayarlanırsa, sonsuz bir dizi özel çözümden, temel çözümler- temel planlar.
Değişkenlerin temel olup olmadığını anlamak için bu değişkenlerin katsayılarından oluşan determinantı hesaplamak gerekir. Bu determinant sıfıra eşit değilse, bu değişkenler temel olabilir.
Temel çözümlerin sayısı ve karşılık gelen temel değişken gruplarının sayısı, burada 'den fazla olamaz. n toplam değişken sayısıdır, r temel değişkenlerin sayısıdır, r≤ m≤ n.
görevimiz için r = 4; n= 6. Sonra , yani. 4 temel değişkenden oluşan 15 grup (veya 15 temel çözüm) mümkündür.
Temel değişkenlere göre denklem sistemini çözelim x 3 , x 4 , x 5 ,x 6:
Serbest değişkenlerin olduğunu varsayarsak x 1 = 0, x 2 = 0, temel değişkenlerin değerlerini alıyoruz: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, yani temel çözüm = (0; 0; 312; 15; 24; -10) olacaktır.
Bu temel çözüm kabul edilemez, çünkü x 6 = –10 ≤ 0 ve kısıtlama koşuluna göre x 6 ≥ 0. Bu nedenle değişken yerine x 6 temel olarak, serbest değişkenler arasından başka bir değişken almanız gerekir. x 1 veya x 2 .
İlk tablonun satırlarını sistemin katsayıları ile aşağıdaki gibi doldurarak kısaltılmış simpleks tabloları kullanarak sonraki çözümü gerçekleştireceğiz (Tablo 1):
tablo 1
F- dize denir dizin. Zıt işaretlerle alınan amaç fonksiyonu katsayıları ile doldurulur, çünkü fonksiyonun denklemi şu şekilde temsil edilebilir: F = 0 – (– 4x 1 – 3x 2).
Ücretsiz üyeler sütununda ben olumsuz bir unsur var b 4 = -10, yani sistemin çözümü geçersiz. Geçerli bir çözüm (temel plan) elde etmek için öğe b 4 negatif olmayan yapılmalıdır.
Seçmek x 6 - negatif ücretsiz üyeye sahip bir satır. Bu satır negatif öğeler içeriyor. Bunlardan herhangi birini seçin, örneğin, "-1" x 1 -sütun ve x 1 - sütun olarak kabul et izin sütunu(değişkeni belirleyecektir x 1 ücretsizden temele geçecektir).
Ücretsiz üyeler paylaşıyoruz ben ilgili unsurlar üzerinde bir sütunu çözme, elde ederiz değerlendirici ilişkilerΘ i==(24, 15, 12, 10). Bunlardan en küçük pozitifi seçiyoruz (minΘ i=10), hangi karşılık gelecek izin satırı. İzin dizesi bir değişken tanımlar x j, bir sonraki adımda temelden çıkıntı yapan ve özgürleşen. Bu yüzden x 6 -line izin verilen bir satırdır ve "-1" öğesi etkinleştirme öğesi. Onu daire içine alıyoruz. Değişkenler x 1 ve x 6 değiştirilir.
Tahmini oranlar Θ i her satırda kurallarla belirlenir:
1) Θ i= eğer ben ve bir farklı işaretlere sahip;
2) Θ i= ∞ ise ben= 0 ve bir < 0;
3) Θ i= ∞ ise bir = 0;
4) Θ i= 0 ise ben= 0 ve bir > 0;
5) Θ i= eğer ben ve bir aynı işaretlere sahip.
İzin verilen bir öğe ile değiştirilmiş Ürdün eleme (MJJI) adımını atıyoruz ve aşağıdaki kurala göre yeni bir tablo (Tablo 2) derliyoruz:
1) çözümleme elemanının (RE) yerine bir değer ayarlanır, bunun tersi, yani. ;
2) izin verilen çizginin öğeleri RE'ye bölünmüştür;
3) çözümleme sütununun öğeleri RE'ye bölünür ve işaret değişir;
4) kalan elemanlar dikdörtgen kuralına göre bulunur:
Tablodan. 2, ücretsiz üyelerin ben-sütun negatif değildir, bu nedenle ilk kabul edilebilir çözüm elde edilir - ilk temel plan= (10; 0; 182; 5; 4; 0). Bu durumda fonksiyonun değeri F() = 40. Geometrik olarak bu, üst kısma karşılık gelir. F(10; 0) çözüm çokgeni (Şekil 1).
Tablo 2
2. Planı optimallik açısından kontrol ederiz. Temel plan optimal değil, çünkü F-line "-4" negatif katsayısına sahiptir. Planı iyileştiriyoruz.
3. Yeni bir temel bulma
İzin veren öğeyi kurala göre seçiyoruz:
En küçük negatif katsayıyı seçiyoruz F- etkinleştirme sütununu belirleyen satır "-4" - x 6; değişken x 6 temele çevir;
Oranları buluyoruz Θ i, aralarında izin verilen dizeye karşılık gelen en küçük pozitif olanı seçiyoruz:
dk Θ i = dk(14, 5, 2, ∞) = 2, dolayısıyla x 5 - satır - izin verilen, değişken x 5'i bedavaya çeviriyoruz (değişkenler x 5 ve x 6 değiştirilir).
İzin verilen satır ve sütunun kesişiminde "2" izin verilen öğe bulunur;
SHMZhI adımını gerçekleştiriyoruz, tabloyu oluşturuyoruz. 3'ü yukarıdaki kurala göre alın ve yeni bir referans planı alın = (12; 0; 156; 3; 0; 2).
Tablo 3
4. Optimallik için yeni temel planı kontrol etme
Temel plan da optimal değil, çünkü F-line "-1" negatif katsayısına sahiptir. fonksiyon değeri F() = 48, geometrik olarak tepeye karşılık gelir E(12; 0) çözüm çokgeni (Şekil 1). Planı iyileştiriyoruz.
5. Yeni bir temel bulma
x 2 sütuna izin verilir, çünkü F-line en küçük negatif katsayı "-1" x 2 sütunlu (Δ 2 = -1). En küçüğü bulmak Θ i: dk Θ i = dk(≈ 9, 6, ∞, 24) = 6, dolayısıyla x 4. satır - izin verici. İzin verilen eleman "1/2". Değişkenleri değiştirme x 2 ve x dört SHMZhI adımını gerçekleştiriyoruz, tabloyu oluşturuyoruz. 4, yeni bir referans planı elde ederiz = (9; 6; 51; 0; 0; 5).
6. Optimallik için temel planı kontrol etme
AT F-line, tüm katsayılar negatif değildir, bu nedenle referans planı optimaldir. Geometrik olarak bir noktaya karşılık gelir D(9;6) (bkz. Şekil 1). Optimal plan, amaç fonksiyonu c.u'nun maksimum değerini verir.
Ana LLP'yi çözmek için tek yönlü bir yöntem fikri LLP destek çözümlerinin tutarlı bir şekilde geliştirilmesinden oluşur.
Simpleks yöntemini yazmanın birkaç yolu vardır.
- Simpleks yönteminin temel şekli;
- Simplex tablosu şeklinde Simplex yöntemi;
- Değiştirilmiş simpleks yöntemi;
- Sütunlu formda Simpleks yöntemi;
- Satır biçiminde Simpleks yöntemi.
F(X) = 3x 1 +5x 2 +4x3 amaç fonksiyonunun maksimum değerini aşağıdaki kısıt koşulları altında tanımlayalım.
0.1x 1 +0.2x 2 +0.4x 3 ≤1100
0.05x 1 +0.02x 2 +0.02x 3 ≤120
3x1 +x2 +2x3 ≤8000
İlk referans planını oluşturmak için, ek değişkenler ekleyerek (kanonik forma geçiş) eşitsizlikler sistemini bir denklem sistemine indirgeriz.
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Simpleks yönteminin temel gösterimi
| Çözüm, temel değişkenleri temel olmayan değişkenler aracılığıyla ifade ederek gerçekleştirilir: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0.1x 1 -0.2x 2 -0.4x 3 x 5 = 120-0.05x 1 -0.02x 2 -0.02x 3 x 6 = 8000-3x 1 -x 2 -2x 3 |
Simpleks tablosu şeklinde Simplex yöntemi
Çözüm, basit bir tablo şeklinde gerçekleştirilir. Form, bir bilgisayarda bilgi işlem için tasarlanmıştır. Yapay bir temel kullanırken, özel bir M sayısı kullanılır (genellikle 10000).| Plan | temel | AT | x 1 | x2 | x 3 | x4 | x5 | x6 | dk |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| dizin satırı | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| dizin satırı | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| dizin satırı | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Değiştirilmiş simpleks yöntemi
| Katsayı matrisi A = a ij Matris b. |
Sütun şeklinde Simpleks yöntemi
| Simpleks yönteminin sütunlu formuna geçiyoruz. Her değişkeni temel olmayanlar cinsinden ifade ederiz. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0,1(-x 1)+0,2(-x 2)+0,4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0.05(-x 1)+0.02(-x 2)+0.02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Bu sistem T 0 tablosuna karşılık gelir.
|
dize biçiminde Simplex yöntemi
İlk kabul edilebilir temel olarak B 0 = alabiliriz.<4, 5, 6>. Aşağıdaki tabloya karşılık gelecektir.
|
Sistemin katsayılarından oluşan Q matrisine denir. tek yönlü tablo B tabanına karşılık gelen bir tek yönlü tabloya denir kabul edilebilir, veya doğrudan kabul edilebilir, eğer q i0 ≥ 0 ise. Simpleks tablosu Q'nun son satırının q i0 elemanlarına denir. göreceli tahminler.
Yapay temel yöntemiyle çözüm biçimleri
Amaç fonksiyonuna dahil edilen yapay değişkenlerin kullanımı için, genellikle belirtilmeyen çok büyük bir pozitif sayı olan M cezası olarak adlandırılan bir ceza uygulanır.Elde edilen temele yapay, çözüm yöntemine ise yapay temel yöntemi denir.
Üstelik yapay değişkenler, görevin içeriği ile ilgili değildir, ancak bir başlangıç noktası oluşturmanıza izin verir ve optimizasyon süreci bu değişkenleri sıfır değerleri almaya zorlar ve optimal çözümün kabul edilebilirliğini sağlar.
Yapay temel yöntemiyle çözüm biçimleri:
- M-yöntemi (simpleks tablo);
- iki aşamalı veya iki aşamalı simpleks yöntemi (Temel gösterim, Modifiye edilmiş simpleks yöntemi, Sütun biçiminde Simpleks yöntemi, Çizgi biçiminde Simpleks yöntemi).
Problem durumunda ≥ işaretli kısıtlamalar varsa, eşitsizliğin her iki kısmı -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 olacak ve kısıtlamalar sistemine özel bir çözüm şu şekilde olacak:
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 gösterebiliriz:
F(x)=∑c ben x ben + F 0 =0 (4)
Başlangıç tek yönlü tablosu (simpleks tablo 1), (2) ve (4) numaralı denklemlere göre derlenir. Eğer x n+j ek değişkenlerinden önce (2)'deki gibi "+" işareti geliyorsa, x i değişkenlerinden ve serbest terim b j'den önceki tüm katsayılar değişmeden simpleks tablosuna girilir. Maksimizasyonu sırasında hedef fonksiyonunun katsayıları, tek yönlü tablonun alt satırına zıt işaretlerle girilir. Simpleks tablosundaki ücretsiz üyeler sorunun çözümünü belirler.
Sorunu çözmek için algoritma aşağıdaki gibidir:
1. adım. Ücretsiz üyeler sütununun öğeleri aranır. Hepsi pozitifse, kabul edilebilir bir temel çözüm bulunmuştur ve optimal çözümü bulmaya karşılık gelen algoritmanın 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 gerçekleştirilir, temel olmayan değişkenlerden hangilerinin tabana alınacağına ve hangi değişkenin tabandan çekileceğine karar vermek gerekir.
Tablo 1.
| temel değişkenler | Kısıtlamalarda ücretsiz üyeler | temel olmayan değişkenler | |||||
| x 1 | x2 | ... | x l | ... | x n|||
| xn+1 | b1 | 11 | 12 | ... | 1l | ... | 1n |
| xn+2 | b2 | 21 | 22 | ... | 2l | ... | 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | bir r1 | bir r2 | ... | bir rl | ... | bir rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | ben | bir m1 | bir m2 | ... | aml | ... | amn |
| F(x)maks | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -cn |
Bunu yapmak için, serbest üyeler sütununun negatif öğelerinden herhangi birini seçin (b 2 önde olsun veya izin versin. Negatif serbest üyeli satırda negatif öğe yoksa, kısıtlama sistemi tutarsızdır 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, dizini r koşuldan belirlenen x n+r olacaktır.
şunlar. serbest terimin seçilen önde gelen sütunun öğesine en küçük oranına karşılık gelen değişken. Bu ilişki denir simpleks ilişkisi. Sadece pozitif simpleks ilişkiler dikkate alınmalıdır.
x n+r değişkenine karşılık gelen dizgeye öncülük etmek veya izin vermek. Simpleks tablosunun, baştaki satır ve satırdaki sütunun kesişim noktasında bulunan a rl öğesine, satır başı veya çözümleyici öğe denir.Önde gelen elemanı bulmak, sonraki her bir tek yönlü tablo ile çalışmayı bitirir.
3. adım. Elemanları önceki adımdaki simpleks tablosunun elemanlarından 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, önceki simpleks tablosunda önde gelen satır ve sütun, yeni simpleks tablosunda doldurulacaktır. İfade (5), önde gelen elemanın yerindeki a "rl öğesinin, önceki tek yönlü tablodaki elemanın karşılıklı değerine eşit olduğu anlamına gelir. a ri satırının elemanları, önde gelen elemana bölünür ve 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ı prensibe göre hesaplanır.
Formüllerin geri kalanı kullanılarak kolayca yazılabilir.
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 eleman bulmak için "ji, karşı köşegen elemanların çarpımı, önde gelen elemana bölünür, a ji elemanından çıkarılır (bu, hücrede" - "işaretiyle gösterilir). Benzer şekilde, b" elemanları j, (j≠r) ve c" i yeniden hesaplanır, (i≠l).
4. adım. Yeni bir simpleks tablosunun analizi, algoritmanın 1. adımından başlar. Eylem, uygun bir temel çözüm bulunana kadar devam eder, yani. ücretsiz üyeler sütununun tüm öğeleri pozitif olmalıdır.
5. adım. Kabul edilebilir bir temel çözümün bulunduğuna inanıyoruz. F(x) hedef fonksiyonunun doğrusunun katsayılarına bakıyoruz. Simpleks tablonun optimalliğinin bir işareti, 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 (serbest terim hariç), o zaman başka bir temel çözüme gitmeniz gerekir. Hedef fonksiyonunu maksimize ederken, temel, sütunu simpleks tablosunun alt satırındaki negatif katsayı cl'nin maksimum mutlak değerine karşılık gelen temel olmayan değişkenlerin (örneğin, x l) değerini içerir. Bu, artışı hedef işlevinde bir gelişmeye yol açan değişkeni seçmenize olanak tanır. x l değişkenine karşılık gelen sütuna, önde gelen sütun denir. Aynı zamanda, r indeksi minimum simpleks oranı ile belirlenen x n+r değişkeni temelden çıkarılır:
x n+r'ye karşılık gelen satıra, önde gelen satır denir ve tek yönlü tablonun, önde gelen satır ile satırdaki sütunun kesişiminde bulunan a rl elemanına denir. lider eleman.
6. adım. 3. adımda belirtilen kurallara göre. Prosedür, optimal bir çözüm bulunana veya var olmadığı sonucuna varılıncaya kadar devam eder.
Öndeki sütundaki çözümü optimize etme sürecinde tüm öğeler pozitif değilse, o zaman önde gelen satır seçilemez. Bu durumda, problemin kabul edilebilir çözümleri alanındaki fonksiyon yukarıdan ve F max ->&∞ ile sınırlı değildir.
Bir ekstremum arayışının bir sonraki adımında, temel değişkenlerden biri sıfıra eşit olursa, buna karşılık gelen temel çözüme dejenere denir. Bu durumda, aynı BP kombinasyonunun belirli bir frekansla tekrar etmeye başlamasıyla karakterize edilen sözde döngü meydana gelir (bu durumda F fonksiyonunun değeri korunur) ve geçiş yapmak imkansızdır. kabul edilebilir yeni bir temel çözüm. 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şkenin temele girilmesi genellikle reddedilir ve yeni bir temel çözüm için rastgele bir seçim yapılır.
Örnek 1. Bir sorunu çözün
max(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.
Sorunun çözümünün grafiksel yorumu, Şek. 2. Hedef fonksiyonunun 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 biçimine 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 derleriz (simpleks tablo 2). Simpleks tabloya karşılık gelen çözüm. 2, geçerli değil; önde gelen eleman, yukarıdaki algoritmanın 2. adımına göre ana hatlarıyla çizilir ve seçilir. Sonraki simpleks sekmesi. 3 kabul edilebilir bir temel çözümü tanımlar; 2 Öncü eleman, problemi çözmek için algoritmanın 5. adımına uygun olarak ana hatlarıyla belirlenir ve seçilir. Sekme. 4, problemin optimal çözümüne karşılık gelir, bu nedenle: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; Fmaks = 20.
Pirinç. 2. Problemin grafiksel çözümü
