Simplex Doğrusal Programlama Yöntemi

Simplex Doğrusal Programlama Yöntemi!

İki değişken içeren herhangi bir doğrusal programlama problemi, iki boyutlu grafikle başa çıkmak daha kolay olduğundan, grafiksel yöntem yardımıyla kolayca çözülebilir. Grafik yöntemindeki tüm uygulanabilir çözümler, grafikteki uygulanabilir alan içerisinde yer alır ve uygun alanın köşe noktalarını en iyi çözüm için, yani uygun alanın köşe noktalarından en iyi çözüm olarak test etmek için kullandık. Köşe noktalarını bu fonksiyonu objektif fonksiyona koyarak test ettik.

Fakat değişken sayısı ikiden artarsa, problem çok karmaşık hale geldikçe grafiğini çizerek sorunu çözmek çok zorlaşır. Simpleks metodu, Amerikalı bir matematikçi olan GB Dantzig tarafından geliştirilmiştir.

Bu yöntem, grafik yöntemin matematiksel tedavisidir. Burada ayrıca uygulanabilir alanın çeşitli köşe noktaları iyimserlik için test edilir. Ancak, bütün köşe noktalarını test etmek mümkün değildir, çünkü köşe noktası sayısı denklem ve değişken sayısı arttıkça manifoldları arttırır. Test edilecek bu noktaların maksimum sayısı

m + n m = m + 1! / m! n!

burada m, sayıdır ve n, değişkenlerin sayısıdır.

Bu nedenle simpleks yönteminde, test edilecek köşe noktalarının sayısı, sadece birkaç tekrarlamayla en uygun çözüm köşe noktasına yönlendiren çok etkili bir algoritma kullanılarak önemli ölçüde azaltılır. Bir örnek ele alalım ve adım adım ilerleyelim.

Amaç, Z = 12x 1 + 15x 2 + 14x 3 en üst düzeye çıkarmaktır

Koşullara tabi

Aşama 1:

(a) Tüm kısıtlamaların sağ tarafı ya sıfır ya da + ve olmalıdır. Eğer öyleyse, o zaman her iki tarafı da (-1) ile çarparak + ve yapılması gerekir ve eşitsizlik işareti tersine çevrilir. Bu örnekte, RHS zaten + ve veya sıfırdır.

(b) Bütün eşitsizlikler, durgunluk ya da fazla değişkenleri toplayarak ya da çıkararak eşitliklere dönüştürülür. Bu gevşek veya fazla değişkenler, matematiksel işlemdeki eşitsizliklerden ziyade eşitliklerle uğraşmanın daha kolay olması nedeniyle ortaya çıkmıştır.

Eğer kısıt ≤ tip ise, kısıt ≥ tip ise gevşek değişkenler eklenir, sonra fazla değişken çıkarılır. Burada slack değişkenleri s,, s 2 ve s3 eşit olarak üçe eklenir (i), (ii) ve (iii), elde ederiz.

Ve nesnel işlev olur

Z = 12x1 + 15x2 + 14x3 + os 1 + os 2 + os 3

Adım 2:

İlk Temel Yapılabilir Çözümü bulun:

Uygun bir çözümle başlıyoruz ve daha sonraki yinelemelerde optimum çözüme doğru ilerliyoruz. İlk uygulanabilir çözüm tercihen orijinli olarak seçilir, yani normal değişkenlerin örneğin bu durumda x v x 2, x 3'ün sıfır değerler aldığı durumlarda. yani x 1 x 2, x 3 = 0

ve eşitsizliklerden (i), (ii) ve (iii) 'den s 1 = 0, s 2 = 0 ve s 3 = 100 alıyoruz

Temel Değişkenler şu anda çözümde bulunan değişkenlerdir; örneğin, Sv S2 ve S3 ilk çözümdeki temel değişkenlerdir.

Temel Olmayan Değişkenler, sıfıra eşit olarak ayarlanmış ve mevcut çözümde bulunmayan değişkenlerdir; örneğin, x 1 ve x 2 ve x 3, başlangıç ​​çözümündeki temel olmayan değişkenlerdir.

Yukarıdaki bilgiler Tablo 1'de ifade edilebilir.

Tabloda, ilk satır objektif fonksiyonun katsayılarını, ikinci satır ise farklı değişkenleri temsil eder (önce normal değişkenler sonra gevşek / fazla değişkenler). Üçüncü dördüncü ve beşinci sıra, tüm kısıtlardaki değişkenlerin katsayılarını temsil eder.

Birinci sütun, objektif (e i ) 'deki temel değişkenlerin (mevcut çözüm değişkenleri) katsayılarını temsil eder; ikinci sütun, temel formdaki değişkenleri (mevcut çözüm değişkenleri) temsil eder ve son sütun, standart formdaki kısıtlamaların sağ tarafını temsil eder. Yani, bütün eşitsizlikleri eşitliklere sıkıştırdıktan sonra, herhangi bir tabloda, mevcut çözüm değişkenlerinin (temel değişkenler) mevcut değerleri RHS tarafından verilmektedir.

Tablo 1'de mevcut çözüm şudur:

S 1 = 0, S 2 = 0, S 3 = 100

Elbette temel olmayan değişkenler X v X 2 ve X3 de sıfır olacak

Herhangi bir temel değişken sıfır değer aldığında dejenerasyon, mevcut çözümün mevcut problemde olduğu gibi dejenere olduğu söylenir. S 1 = 0 ve S 2 = 0 ise, sorun S 1 = t ve S 2 = t yerine geçerek çözülebilir. çok küçük + ve sayı.

Aşama 3:

İyimserlik Testi.

Mevcut çözümün optimal olup olmadığını bulmak için optimizasyon testi yapılabilir. Bunun için ilk satırı (E j ) şeklinde yazınız.

Ej = Σ ei. Bir ij.

Bir ij, satır ve jth sütunu için vücut kimliği matrisindeki katsayıları temsil ettiği zaman, yani tablonun ilk sütununu temsil eder. Son satırda, (Cj - Ej) değerini yazın ; c ; ilk satırın değerlerini temsil eder ve E j son satırın değerlerini temsil eder. (Cj - Ej) herhangi bir temel değişkeni mevcut çözüme getirme, yani basit hale getirme avantajını temsil eder.

Tablo 2'de Cj - Ej değerleri X v X 2 ve X3 için 12, 15 ve 14'tür. Cj - Ej'nin değerlerinden herhangi biri + ve ise, o zaman en pozitif değerlerin mevcut çözüme getirilen değişkeni temsil ettiği, objektif işlevi maksimum ölçüde artıracağı anlamına gelir. Mevcut durumda, X2, bir sonraki yineleme için çözüme giren potansiyel değişkendir. (Cj - Ej) satırındaki tüm değerler negatifse, en iyi çözüme ulaşıldığı anlamına gelir.

4. Adım:

Optimal çözüme doğru tekrarlayın:

En fazla Cj - Ej değeri Tabloda işaretlendiği gibi Anahtar sütun verir

Bu nedenle X 2 giriş değişkenidir, yani basitleşir ve çözüme girer. Var olan temel olmayan değişken dışında, biri çıkıp temel olmamak zorundadır. Hangi değişkenin çıkarılacağını bulmak için, Oran Sütununu elde etmek için RHS sütunundaki katsayıları anahtar sütundaki karşılık gelen katsayılara bölerim. Şimdi Oran Sütununda en düşük pozitif değere bakın ve bu anahtar satırı verir. Mevcut problemde üç değerimiz var, yani t, µ ve 100 ve bunlardan en az + ve. Dolayısıyla, Oran sütununda t'ye karşılık gelen Satır, anahtar satır olur. S., bırakma değişkeni olacaktır. Anahtar satır ve anahtar sütun kesişimindeki öğe anahtar unsurdur.

Şimdi, anahtar sütununda, anahtar eleman hariç tüm elemanlar sıfır, anahtar eleman ise birlik haline getirilecek. Bu işlem, satır işlemlerinin yardımı ile yapıldığı gibi matrislerdir. Burada anahtar eleman zaten birliktir ve anahtar sütundaki diğer eleman, üçüncü satırına -1 kez ilk satır eklenerek sıfır yapılır ve bir sonraki tabloya alınır.

Bu nedenle ikinci uygulanabilir çözüm olur

X1 = 0, X2 = t ve X3 = 0, z = 15t ile

Yeni tabloda, s1, temel değişkenlerde X2 ile değiştirildi ve buna karşılık ei sütunu da değiştirildi.

Adım 5:

Tablo 3'teki Cj-Ej değerlerine baktığımızda, x1'in 27 değerinin en fazla + ve değerine sahip olduğunu tespit ettik, böylece x1'i çözeltiye getirerek, yani bazik hale getirerek çözeltinin daha da geliştirilebileceğini belirttik. Bu nedenle x1 sütunu anahtar sütundur, ayrıca daha önce açıklandığı gibi anahtar satırı da bulun ve Tablo 5'i tamamlayın.

Tablo 5'teki anahtar eleman 2 olarak ortaya çıkıyor ve birlik yapılıyor ve anahtar sütundaki diğer tüm elemanlar satır işlemleri yardımıyla sıfırlanıyor ve son olarak Tablo 6'yı alıyoruz. İlk anahtar eleman bu satırı bölüştürerek birliği sağlıyor 2. Sonra bu satırın uygun katlarını başka satırlara ekleyerek tablo 6'yı elde ederiz.

Tablo 6'dan, Cj-Ej'nin hala + ve değerleri 1/2 olduğu için hala çözelti optimal olmadığı görülebilir, bu, anahtar sütunu verir ve karşılık gelen anahtar sırası bulunur, anahtar eleman Tablo 7'de verilen şekilde yapılır.

Şimdi uygun sıra işlemleriyle anahtar kolondaki diğer elemanları Tablo 8'de gösterildiği gibi sıfırdır.

Cj-Ej sırasındaki tüm değerlerin -veya ya da sıfır olduğu için optimal çözüme ulaşıldığı görülebilir.

Nihai çözüm x 1 = 40 ton

x 2 = 40 ton

x 3 = 20 ton

t çok küçük olduğundan ihmal edilir.

Örnek 1:

Simpleks yöntemiyle aşağıdaki problemi çözün

Z = 5x 1 + 4x 2 büyüt

6x 1 + 4x 2 ≤ 24 tabi

x 1 + 2x 2 ≤ 6

-x 1 + x 2 ≤ 1

x 2 ≤ 2

ve x 1 x 2 ≥0

Çözüm:

Eşitsizlikleri gidermek için dört kısıtlamaya gevşek değişkenler S1, S2, S3, S4 ekleyin.

6x 1 + 4x 2 + s 1 = 24 alıyoruz

x 1 + 2x 2 + s 2 = 6

-x 1 + x 2 + s 3 = 1

x 2 + s 4 = 2

X 1, x 2, s 1, s 2, s 3 & s'ye tabi 4 > 0

Amaç işlevi olur

Z = 5x 1 + 4x 2 0s 1 + 0s 2 + 0s 3 + 0s 4 büyüt

Oluşan Tablo 1 aşağıda verilmiştir. X1'in giriş değişkeni olduğu ve S'nin çıkış değişkeni olduğu görülebilir. Tablo 1'deki anahtar eleman birliktir ve bu sütundaki tüm diğer elemanlar sıfır yapılır.

Tablo 2'den X2'nin giriş değişkeni olduğu ve S2'nin çıkış değişkeni olduğu gösterilebilir.

Tablo 5'ten, Cj-Ej sırasının tüm değerlerinin ya -ve ya da sıfır olduğu görülebilir. Bu nedenle en uygun çözüm elde edilmiştir.

Çözüm x 1 = 3, x 2 = 3/2

Z maks = 5x3 + 4x = 3/2

= 15 + 6 = 21 Ans.

Büyük m- yöntemi

Büyük M-Yöntemini göstermek için aşağıdaki problemi ele alalım.

Z'yi en aza indir = 2y 1 + 3y 2

kısıtlamalara tabi y 1 + y 2 ≥ 5

y 1 + 2y 2 ≥ 6

y 1, y 2 ≥ 0

Standart forma dönüştürme:

Z = -2y 1 - 3y 2 + Os, + 0s 2 büyüt

yani Minimizasyon problemi, objektif fonksiyonun RHS'sini -1 ile çarparak maksimizasyon problemine dönüştürülür.

Kısıtlamalar y 1 + y 2 - s 1 = 6… (i)

y, + y 2 - s 2 = 6… (ii)

y 1 y 2, s 1 s 2 ≥ 0

Burada s1, s2 değişkenleri ve fazlalıklar sırasıyla (i) ve (ii) sınırlarından çıkarılır.

Şimdi y 1, y 2 temel değişkenler olarak alınabilir ve s v s 2 'yi temel değişkenler olarak almak için sıfıra eşit olabilir, burada s 1 = -5, s 2 = -6.

Bu, s 1 ve s 2 değişkenlerinin get -ve değerlerine sahip olması nedeniyle mümkün olmayan bir çözümdür. Bu sorunun üstesinden gelmek için, eşdeğerde A 1 ve A 2 yapay değişkenlerini ekliyoruz. (i) ve (ii) sırasıyla

y 1 + y 2 –s 1 + A 1 = 5… (iii)

y 1 + 2y 2 - s 2 + A 2 = 6… (iv)

Burada y 1 y 2, s 1, s 2, A 1, A 2 ≥ 0

ve nesnel işlev olur

Z 1'i maksimize et = -2y 1 - 3y 2 + 0s 1 + 0s 2 - MA 1 - MA 2

Objektif fonksiyondaki yapay değişkenlere kasıtlı olarak çok ağır cezalar uyguladık, M'nin çok büyük + ve sayı olduğu -MA1 ve MA2 şeklinde gözlendik. Bunun amacı yapay değişkenlerin başlangıçta başlangıçtaki temel çözümde ortaya çıkmasıdır.

Yapay değişkenler, objektif işlevi büyük ölçüde ceza durumunda düşürdüğü için, simpleks algoritması, yapay değişkenleri başlangıçtaki yinelemelerde çözümün dışına çıkarır ve bu nedenle sorunu daha da çözmek için getirdiğimiz yapay değişkenler finalde görünmez. çözüm. Yapay değişkenler sadece hesaplamalı bir cihazdır. Başlangıç ​​denklemlerini dengede tutarlar ve başlangıç ​​çözümü elde etmek için matematiksel bir numara sunarlar.

İlk Tablo olur

Cj-Ej bazı sütunların altında ve + olduğundan, Tablo 1'de verilen çözüm uygun değildir. -2 + 2M ve -3 + 3M'den -3 + 3M'den en fazla + M olduğu ve M + çok büyük olduğu görülebilir. Anahtar eleman, Tablo 1'de gösterildiği gibi bulunur ve birlik yapılır ve bu sütundaki diğer tüm elemanlar sıfır yapılır. Tablo 2'yi alıyoruz.

Tablo 2'den, optimal çözüme hala ulaşılmadığı ve daha iyi bir çözüme sahip olduğu görülebilir. Y1 gelen değişkendir ve A 1 giden değişkendir. Tablo 3'ü alıyoruz.

Tablo 3'ten optimal çözüme ulaşıldığı ve çözüme ulaştığı görülmektedir.

Y 1 = 4, Y 2 = 1

Minimum Z Değeri = 2x 4 + 3x 1 = 11 birim Ans.

Sınırsız Çözüm:

Doğrusal Programlama Probleminin oran sütununda sınırsız bir çözüme sahip olduğu söylenir, tüm girişleri -ve ya da sıfır alırız + giriş yoktur. Bu, anahtar sütundan seçilen gelen değişkenin değerinin, uygulanabilir durumu ihlal etmeden istediğimiz kadar büyük olabileceğini ve sorunun sınırsız bir çözüme sahip olduğu söylenir.

Sonsuz Çözüm Sayısı:

Doğrusal Programlama Probleminin, herhangi bir yinelemede, Cj-Ej satırında, sıfır veya -ve tüm değerlere sahip olmamız halinde sonsuz sayıda çözüme sahip olduğu söylenir. En uygun değerin ulaştığını gösterir. Ancak normal değişkenlerden biri Cj-Ej satırında sıfır değere sahip olduğundan, alternatif bir optimal çözüm olduğu sonucuna varılabilir.

Bu tür bir tablo örneği aşağıda verilmiştir.

Cj-Ej sırasındaki tüm değerlerin sıfır veya -ve olduğu için optimum çözüme ulaşıldığı görülebilir. Ancak X1 temel değişken değildir ve Cj-Ej sırasındaki sıfır değere sahiptir, X'in getirilebileceğini belirtir çözüm, ancak nesnel fonksiyonun değerini artırmayacak ve alternatif optimal var olacaktır.

No: Uygun Çözüm Örneği:

Bazı LPP'lerde yapay değişkenlerle problem çözülürken, Cj-Ej sırasının optimal çözüme ulaştığını gösterdiği halde mevcut çözümde bazı + vp değerine sahip yapay değişkene sahip olduğumuzu göstermektedir. Bu gibi durumlarda, sorunun herhangi bir uygulanabilir çözümü olmadığı sonucuna varılabilir.

Örnek 2:

Çözüm:

Sorunu çözmek için, ilk temel uygulanabilir çözümü elde etmek için yapay değişkenlerin LHS'ye eklenmesi gerekecektir. Yapay değişkenler sunalım: A 1, A 2, A 3, yukarıdaki kısıtlamalar olarak yazılabilir.

Şimdi eğer bu yapay değişkenler nihai çözümde bazı + değerlere sahip olarak belirirse, o zaman denklemin (i), (ii) veya (iii) eşitliği bozulur. Bu nedenle yapay değişkenlerin nihai çözümde görünmemesini istiyoruz ve bu nedenle objektif işlevinde olduğu gibi yazılabilecek büyük cezalar uyguluyoruz.

Z = Y, + 2Y 2 + 3Y 3 - Y 4 - MA, - MA 2 - MA 3 değerlerini maksimize edin

Şimdi eğer y 1 Y2, y3 ve y4'ü temel olmayan değişkenler olarak alırsak ve Y 1 = Y 2 = y 4 = 0 koyarsak ilk çözümü A 1 = 15, A 2 = 20 & A 3 = 10 olarak alırız. ve 1, A2, A3 ve A4 ile başlamak için temel değişkenlerdir (mevcut çözümdeki değişkenler). Yukarıdaki bilgiler Tablo 1'de gösterilebilir.

Cj- Ej pozitif olduğu için mevcut çözüm optimal değildir ve bu nedenle daha iyi bir çözüm vardır.

Optimal bir çözüme doğru yineleyin

Aşağıdaki tabloda gösterildiği gibi en uygun çözümü elde etmek için yinelemeler yapmak

Cj-Ej, tüm sütunların altında sıfır veya negatif olduğundan, en uygun temel uygulanabilir çözüm elde edilmiştir. Optimal değerler

Y1 = 5/2, Y2 = 5/2, Y3 = 5/2, Y4 = 0

Ayrıca A 1 = A 2 = 0 ve Z maks = 15 Ans.