Simplex yöntemi, çevrimiçi yeni bir temel plandır. Doğrusal programlama probleminin kanonik forma indirgenmesi. Simpleks yöntemini kullanarak sorunu çözme

İşte, simpleks yöntemini kullanarak problem çözme algoritmasını anlamak için ayrıntılı açıklamalarla simpleks yöntemiyle (bir uygulama ile çözüme benzer) iki problemin manuel (bir uygulama değil) çözümü. İlk problem sadece "≤" (başlangıç ​​temeli olan bir problem) eşitsizlik işaretlerini içerir, ikincisi "≥", "≤" veya "=" (yapay tabanlı bir problem) işaretlerini içerebilir, bunlar farklı şekillerde çözülür. yollar.

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. Çözümünde simpleks yönteminin kullanıldığı 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, temeli olan bir sistemdir ve serbest terimleri negatif değildir; bu nedenle uygulayabiliriz. tek yönlü yöntem... Sorunu çözmek için ilk tek yönlü tabloyu (Yineleme 0) oluşturalım. tek yönlü yöntem, 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.

simpleks yöntem yineleme 0

							Davranış

Çözümü geliştirmek için bir sonraki yinelemeye geçelim tek yönlü yöntem, aşağıdaki tek yönlü tabloyu elde ederiz. Bunu yapmak için seçmeniz gerekir izin verilen sütun, yani simpleks yönteminin bir sonraki yinelemesinde temele dahil edilecek bir değişken. Z-sırasındaki (maksimum problemde) en büyük modulo negatif katsayısı ile seçilir - simpleks yönteminin ilk yinelemesinde, bu sütun x 2'dir (katsayı -6).

Daha sonra seçilir izin verilen dize, yani simpleks yönteminin bir sonraki yinelemesinde 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ütununun ve çözümleme satırının kesişiminde bulunur, hücresi 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-ç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" tablosu -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 1 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-çizgisi için elimizde:

Eski z-çizgisi (-4 -6 0 0 0 0) - (- 6) * Yeni çözüm çizgisi - (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.

simpleks yöntem yineleme 1

							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.

simpleks yöntem yineleme 2

							Davranış

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

simpleks yöntem yineleme 3

							Davranış

z-satırında, tüm katsayılar negatif değildir; bu nedenle, elde ettik en uygun çözüm x 1 = 24, x 2 = 16, z maks = 192.

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)

Diyelim ki tüm orijinal değişken görevler x 1, x 2, ..., x n temel değildir. 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 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), 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. Prosedür, optimal bir çözüm bulunana veya var olmadığı sonucuna varılana kadar devam eder.

Ö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

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 problem sınıfına uygulanabilir. doğrusal programlama: ikiden fazla değişken içermeyen problemleri etkili bir şekilde çözebilirler. Doğrusal programlamanın ana teoremlerinden yola çıkarak, bir doğrusal programlama probleminin optimal bir çözümü varsa, o zaman çözüm politopunun en az bir köşe noktasına karşılık gelir ve kabul edilebilir temel çözümlerinden en az biriyle çakışır. kısıtlamalar sistemi. Herhangi bir doğrusal programlama problemini çözmenin bir yolu gösterildi: kısıtlamalar sisteminin sonlu sayıda kabul edilebilir temel çözümlerini sıralamak ve aralarından hedef fonksiyonunun en uygun çözümü yaptığı çözümü seçmek. Geometrik olarak bu, çözüm politopunun tüm köşe noktalarının bir numaralandırmasına karşılık gelir. Böyle bir numaralandırma (eğer varsa) eninde sonunda optimal bir çözüme götürecektir, ancak pratik uygulaması muazzam zorluklarla ilişkilidir, çünkü gerçek problemler için kabul edilebilir temel çözümlerin sayısı sonlu olmasına rağmen son derece büyük olabilir.

Numaralandırma rastgele değil de lineer fonksiyondaki değişiklikler hesaba katılarak yapılırsa, yani kabul edilebilir temel çözümlerin sayısı azaltılabilir. her birinin olduğundan emin olmak sonraki karar doğrusal fonksiyonun değerleri açısından öncekinden "daha iyi" (veya en azından "daha kötü değil") idi (maksimumu bulurken arttırıyor, minimumu bulurken azaltıyor)
). Böyle bir numaralandırma, kişinin optimumu bulmadaki adım sayısını azaltmasını sağlar. Bunu grafik bir örnekle açıklayalım.

Uygulanabilir çözümlerin bölgesi bir çokgen ile gösterilsin. ABCDE... köşe noktasını varsayalım A orijinal kabul edilebilir temel çözüme karşılık gelir. Rastgele bir numaralandırma, çokgenin beş köşe noktasına karşılık gelen beş kabul edilebilir temel çözümü test etmelidir. Ancak çizimden anlaşılacağı üzere üst kısımdan sonra A komşu tepe noktasına gitmek karlı V, ve sonra - en uygun noktaya İLE BİRLİKTE. Beş yerine, yalnızca üç köşe dizildi ve doğrusal işlevi tutarlı bir şekilde geliştirdi.

Çözümün sürekli iyileştirilmesi fikri, doğrusal programlama problemlerini çözmek için evrensel bir yöntemin temelini oluşturdu - planın sıralı iyileştirilmesi için simpleks yöntemi veya yöntemi.

Simpleks yönteminin geometrik anlamı, kısıtlama polihedronunun bir köşesinden (ilk olan olarak adlandırılır) komşu olana sıralı bir geçişten oluşur; burada doğrusal fonksiyon, aşağıdakine göre en iyi (en azından daha kötü değil) değeri alır. sorunun amacı; optimal çözüm bulunana kadar - hedef fonksiyonun optimal değerinin elde edildiği tepe noktası (sorunun sonlu bir optimumu varsa).

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

Simpleks yöntemi, herhangi bir doğrusal programlama problemini çözmeye izin veren evrenseldir. Şu anda bilgisayar hesaplamaları için kullanılmaktadır, ancak simpleks yöntemini kullanan basit örnekler manuel olarak çözülebilir.

Simpleks yöntemini uygulamak için - çözümün tutarlı bir şekilde iyileştirilmesi - ustalaşmak gerekir üç ana unsur:

soruna herhangi bir ilk kabul edilebilir temel çözümü belirlemek için bir yöntem;

en iyi (daha doğrusu en 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 biçim, yani kısıtlamalar sistemi denklemler şeklinde temsil edilmelidir.

Literatür yeterli ayrıntıda açıklamaktadır: başlangıç ​​temel planının bulunması (ilk kabul edilebilir temel çözüm), ayrıca yapay temel yönteminin kullanılması, optimal temel planın bulunması, problemleri tek yönlü tablolar kullanarak çözme.

3.2. Simpleks yönteminin algoritması.

LPP'nin simpleks yöntemiyle çözümünü ele alalım ve maksimizasyon problemi ile ilgili olarak sunalım.

1. Problemin durumuna göre matematiksel modeli çizilir.

2. Derlenen model şuna dönüştürülür: kanonik biçim... Aynı zamanda, ilk referans planı ile temel öne çıkabilir.

3. Problemin kanonik modeli, tüm serbest terimlerin negatif olmaması için bir simpleks tablo şeklinde yazılmıştır. İlk temel plan vurgulanmışsa, 5. adıma gidin.

Tek yönlü tablo: kısıtlayıcı denklemler sistemine uyar ve amaç fonksiyonu ilk temele göre izin verilen ifadeler şeklinde. Amaç fonksiyonunun katsayılarını içeren çizgi
arandı
– Amaç fonksiyonunun dizesi veya satırı.

4. Minimum simpleks ilişkilerine karşılık gelen pozitif çözünürlüklü elemanlarla simpleks dönüşümleri gerçekleştirerek ve elemanların işaretlerini dikkate almadan ilk referans tasarımı bulun.
-Teller. Dönüşümler sırasında, serbest terim hariç tüm elemanları sıfır olan bir 0-string ile karşılaşılırsa, problemin kısıtlayıcı denklemler sistemi uyumsuzdur. Serbest terimin yanı sıra başka pozitif öğe olmayan bir 0 satırı varsa, kısıtlayıcı denklemler sisteminin negatif olmayan çözümleri yoktur.

Sistemin (2.55), (2.56) yeni bir esasa indirgenmesi olarak adlandırılacaktır. tek yönlü dönüşüm . Simpleks dönüşümü formal bir cebirsel işlem olarak kabul edilirse, bu işlem sonucunda bazı sistemlerde yer alan iki değişken arasında rollerin yeniden dağıtıldığı görülebilir. doğrusal fonksiyonlar: bir değişken bağımlıdan bağımsıza, diğeri ise tam tersi bağımsızdan bağımlıya gider. Böyle bir işlem cebirde şu şekilde bilinir: Ürdün eleme aşaması.

5. Bulunan başlangıç ​​durumu planı, optimallik açısından araştırılır:

a) içinde ise
- dizide (kesme dışında) hiçbir olumsuz unsur yoktur, o zaman plan en uygunudur. Aynı zamanda sıfır olan yoksa, o zaman tek plan en uygun plandır; en az bir sıfır varsa, sonsuz sayıda optimal plan vardır;

b) içinde ise
–Satır, pozitif olmayan öğelerden oluşan bir sütuna karşılık gelen en az bir negatif öğeye sahipse,
;

c) içinde ise
–Satırda en az bir negatif öğe var ve sütunu en az bir pozitif öğe içeriyor, ardından en uygun olana daha yakın olan yeni bir referans planına gidebilirsiniz. Bunu yapmak için, izin verilen dizeyi bulmak ve bir tek yönlü dönüşüm gerçekleştirmek için belirtilen sütun minimum tek yönlü ilişki ile izinli olarak atanmalıdır. Ortaya çıkan referans planını optimallik açısından yeniden inceleyin. Tanımlanan süreç, optimal bir plan elde edilene veya problem çözülemez hale gelene kadar tekrarlanır.

Temelde yer alan bir değişken için katsayılar sütununa çözümleme denir. Böylece, negatif eleman tarafından temele dahil edilecek değişkenin seçilmesi (veya çözümleme sütununun seçilmesi)
–Strings, artan fonksiyon sağlıyoruz
.

Temelden çıkarılacak değişkeni belirlemek biraz daha zordur. Bunu yapmak için, serbest üyelerin çözümleme sütununun pozitif öğeleriyle ilişkileri yapılır (bu tür ilişkilere simpleks denir) ve aralarında, hariç tutulan değişkeni içeren çizgiyi (çözümleme) belirleyen en küçük olanı bulunur. Asgari simpleks ilişkisine göre temelden çıkarılacak değişkenin seçimi (veya çözüm çizgisinin seçimi), daha önce belirtildiği gibi, yeni referans planındaki temel bileşenlerin pozitifliğini garanti eder.

Algoritmanın 3. noktasında, serbest üye sütununun tüm elemanlarının negatif olmadığı varsayılır. Bu gereklilik gerekli değildir, ancak karşılanırsa, sonraki tüm tek yönlü dönüşümler yalnızca hesaplamalar için uygun olan pozitif çözme öğeleriyle gerçekleştirilir. Serbest üyeler sütunu negatif sayılar içeriyorsa, çözümleme öğesi aşağıdaki gibi seçilir:

1) bazı negatif kesişmelere karşılık gelen bir satıra bakın, örneğin - bir satır ve içinde bazı negatif öğeler seçilir ve ilgili sütun izin verilen bir sütun olarak alınır (sorunun kısıtlamalarının uyumlu olduğunu varsayıyoruz);

2) serbest üyelerden oluşan sütunun elemanlarının, aynı işaretlere sahip olan (basit ilişkiler) çözme sütununun karşılık gelen elemanlarına oranlarını oluşturur;

3) Simpleks bağıntılarından en küçüğü seçilir. Çözüm çizgisini belirleyecek. Örneğin olsun, r-hat;

4) Çözümleme sütunu ve satırın kesişiminde, çözümleme elemanı bulunur. eğer eleman –String, sonra simpleks dönüşümden sonra bu stringin serbest terimi pozitif olur. Aksi takdirde, bir sonraki adımda tekrar dönerler. -Sicim. Sorun çözülebilirse, serbest terimler sütununda belirli sayıda adımdan sonra hiçbir olumsuz unsur kalmayacaktır.

Bazı gerçek üretim durumları bir LPP biçimindeyse, modele kanonik forma dönüştürme sürecinde dahil edilmesi gereken ek değişkenlerin her zaman belirli bir ekonomik anlamı vardır.

Üç çeşit gömlek üretimi için iplik, düğme ve kumaş kullanılmaktadır. İplik, düğme ve kumaş stokları, bir gömlek dikmek için tüketim oranları tabloda gösterilmiştir. Maksimum karı ve bunu sağlayan en uygun ürün sürüm planını bulun (bul).

gömlek 1

gömlek 2

gömlek 3

Hisse senetleri

iplik (m)

1

9

3

96

düğmeler (adet)

20

10

30

640

bez (

1

2

2

44

Kar (s.)

2

5

4

sorunun çözümü

Modeli oluşturmak

Serbest bırakılması amaçlanan 1., 2. ve 3. tip gömleklerin sayısı ve sayısı.

Ardından kaynak kısıtlamaları şöyle görünecektir:

Ayrıca problemin anlamı dahilinde

Elde edilen karı ifade eden amaç fonksiyonu:

Aşağıdaki doğrusal programlama problemini elde ederiz:

Doğrusal programlama problemini kanonik forma indirgemek

Sorunu kanonik bir forma getirelim. Ek değişkenleri tanıtalım. Tüm ek değişkenleri, sıfıra eşit bir katsayı ile amaç fonksiyonuna dahil ediyoruz. Tercih formu olmayan kısıtların sol taraflarına ek değişkenler ekliyoruz ve eşitlikler elde ediyoruz.

Simpleks yöntemini kullanarak sorunu çözme

Simpleks tablosunu dolduruyoruz:

Sorunu maksimumda çözdüğümüz için - dizin satırındaki varlık negatif sayılar problemi maksimuma çözerken, optimal çözümü elde etmediğimizi ve 0. iterasyon tablosundan diğerine geçmenin gerekli olduğunu gösterir.

Bir sonraki iterasyona geçiş şu şekilde gerçekleştirilir:

önde gelen sütun eşleşmeleri

Anahtar satır, serbest üyelerin ve önde gelen sütunun üyelerinin (simpleks ilişkiler) minimum oranı ile belirlenir:

Anahtar sütunun ve anahtar satırın kesişiminde, çözümleme öğesini, yani. dokuz.

Şimdi 1. yinelemeyi çizmeye başlıyoruz: Birim vektör yerine bir vektör giriyoruz.

V yeni masa 1 yazdığımız çözümleme elemanının yerine, anahtar sütunun diğer tüm elemanları sıfırdır. Anahtar satır öğeleri, izin veren öğelere bölünmüştür. Tablonun diğer tüm elemanları dikdörtgen kuralına göre hesaplanır.

1. yineleme eşleşmeleri için anahtar sütun

İzin verilen elemanlar 4/3 sayısıdır. Vektörü tabandan çıkarıyoruz ve bunun yerine vektörü giriyoruz. 2. yinelemenin tablosunu alıyoruz.

2. yineleme eşleşmeleri için anahtar sütun

Anahtar dizeyi buluyoruz, bunun için tanımlıyoruz:

Çözme elemanı 10/3 sayısıdır. Vektörü tabandan çıkarıyoruz ve bunun yerine vektörü giriyoruz. 3. yinelemenin tablosunu alıyoruz.

№

BP

cB

bir o

x 1

x 2

x 3

x 4

x 5

x 6

Basit

2

5

4

0

0

0

ilişki

0

x 4

0

96

1

9

3

1

0

0

32/3

x 5

0

640

20

10

30

0

1

0

64

x 6

0

44

1

2

2

0

0

1

22

F j - c j

0

-2

-5

-4

0

0

0

1

x 2

5

32/3

1/9

1

1/3

1/9

0

0

32

x 5

0

1600/3

170/9

0

80/3

-10/9

1

0

20

x 6

0

68/3

7/9

0

4/3

-2/9

0

1

17

F j - c j

160/3

-13/9

0

-7/3

5/9

0

0

2

x 2

5

5

-1/12

1

0

1/6

0

-1/4

--

x 5

0

80

10/3

0

0

10/3

1

-20

24

x 3

4

17

7/12

0

1

-1/6

0

3/4

204/7

F j - c j

93

-1/12

0

0

1/6

0

7/4

3

x 2

5

7

0

1

0

1/4

1/40

-3/4

x 1

2

24

1

0

0

1

3/10

-6

x 3

4

3

0

0

1

-3/4

-7/40

17/4

F j - c j

95

0

0

0

1/4

1/40

5/4

Dizin satırındaki tüm terimler negatif değildir, bu nedenle doğrusal programlama problemine aşağıdaki çözüm elde edilir (bunu serbest terimler sütunundan yazarız):

24 tip 1 gömlek, 7 tip 2 gömlek ve 3 tip 3 gömlek dikmek gerekir. Bu durumda, ortaya çıkan kar maksimum olacak ve 95 ruble olacak.

VKontakte'den, Viber'den mesaj göndererek veya formu doldurarak bu konudaki sorunlarınızın çözümü için yardım alabilirsiniz. Çözüm maliyeti ödev 7 BYN'den başlar görev başına (200 ruble), ancak en az 10 Belarus rublesi. (RUB 300) tüm sipariş için. Detaylı tasarım... Çevrimiçi sınav yardımının maliyeti (bu durumda, %100 ön ödeme gereklidir) - 30 BYN'den. (1000 Rus rublesi) bileti çözmek için.

Beğendin mi? Yer imi

Simpleks yöntemini kullanarak sorunları çözme: çevrimiçi örnekler

Amaç 1.Şirket, A ve B olmak üzere iki boyutta banyo rafları üretmektedir. Satış temsilcileri, pazarda haftada 550'ye kadar rafın satılabileceğini tahmin etmektedir. Her A tipi raf için 2 m2 malzeme, B tipi raf ise 3 m2 malzeme gerektirir. Firma haftada 1200 m2'ye kadar malzeme alabilmektedir. A tipi bir rafın imalatı için 12 dakika, B tipi bir rafın imalatı için 30 dakika makine süresi gereklidir; makine haftada 160 saat kullanılabilir. A tipi rafların satışından elde edilen kâr 3 ise para birimleri, ve B - 4 den tipi raflardan. adet, her tipten haftada kaç adet raf üretilmelidir?

Amaç 2. Simpleks yöntemini kullanarak doğrusal programlama problemini çözün.

Amaç 3.Şirket, A1, A2, A3 olmak üzere iki çeşit hammadde kullanarak 3 çeşit ürün üretmektedir. Her türden üretim birimi başına hammadde maliyetleri, planlanan dönem için hammadde stokları ve her türden bir üretim biriminden elde edilen kâr bilinmektedir.

1. Maksimum karı elde etmek için her türden kaç ürün üretilmesi gerekir?
2. Her bir hammadde türünün durumunu ve özel değerini belirleyin.
3. Optimal planın yapısının, yani. konunun isimlendirilmesi değişmeyecektir.
4. Kıt hammadde türlerinden birinin stokunda mümkün olan maksimum değere (verilen üretim terminolojisi dahilinde) bir artışla serbest bırakmadan elde edilen ürün miktarını ve karı belirleyin.
5. Elde edilen optimal planın değişmeyeceği, her türden bir üretim biriminden elde edilen kârdaki değişim aralıklarını belirleyin.

Görev 4. Simpleks yöntemini kullanarak doğrusal programlama problemini çözün:

Görev 5. Simpleks yöntemini kullanarak doğrusal programlama problemini çözün:

Görev 6. Koşulda verilen planı ilk referans planı olarak kabul ederek problemi simpleks yöntemini kullanarak çözün:

Görev 7. Değiştirilmiş simpleks yöntemini kullanarak sorunu çözün.
A ve B olmak üzere iki tip ürünün üretimi için üç tip kullanılmaktadır. teknolojik ekipman... Bir birim A ürününün üretimi için birinci tip ekipman a1 = 4 saat, ikinci tip ekipman a2 = 8 saat ve üçüncü tip ekipman a3 = 9 saat kullanılır. Bir birim B ürününün üretimi için, birinci tip ekipman b1 = 7 saat, ikinci tip ekipman, b2 = 3 saat ve üçüncü tip ekipman, b3 = 5 saat kullanılır.
Bu ürünlerin imalatı için, birinci tip ekipman t1 = 49 saatten fazla, ikinci tip ekipman t2 = 51 saatten fazla, üçüncü tip ekipman t3 = 45 saatten fazla çalışamaz.
Bir birim bitmiş ürün A'nın satışından elde edilen kar, ALPHA = 6 ruble ve B ürünü için - BETTA = 5 ruble.
A ve B ürünlerinin üretimi için satışlarından maksimum karı sağlayan bir plan hazırlayın.

Sorun 8. Dual simpleks yöntemiyle en uygun çözümü bulun