Büyük M yöntemi
Bu madde hiçbir kaynak içermemektedir. (Temmuz 2015) (Bu şablonun nasıl ve ne zaman kaldırılması gerektiğini öğrenin) |
Bu madde, Vikipedi biçem el kitabına uygun değildir. (Temmuz 2015) |
Matematiksel modellerin çözümünde kullanılır. Model kısıtlarından en az birisinin = veya => olması gerekir. Bu çözüm yönteminin bir türevide iki aşamalı yöntemdir. Büyük M yönteminde amaç satırındaki katsayılar M katsayısını alırlar. M katsayısı model içerisindeki hiçbir katsayının ulaşamayacağı kadar büyük bir sayı kabul edilmektedir.
Programlama algoritmalarında ise long tipinde tanımlanarak çok büyük değerler atanarak problemler uygulamalara çözdürülür.
Uygulanması
değiştirBüyük M kaysayıları eklendikten sonraki aşamalar simpleks yöntemle aynıdır.
Model standart hale getirilirken = ve => olan kısıtlara +R yapay değişkeni eklenir. Sağ taraf değerlerinin negatif olmamasına dikkat edilir. Sağ taraf değerlerinde negatiflik varsa dual simpleks uygulanır.
+R yapay değişkenleri sol tarafta bırakılarak tüm değerler sağ tarafa atılarak R ler kısıtlardan çekilmiş olur. Maksimizasyon problemlerinde -MR Minimizasyon problemlerinde ise +MR olarak amaç fonksiyonuna eklenir. Amaç fonksiyonu MR ler eklendikten sonra düzenlenir ve ardından başlangıç tablosu oluşturularak simpleks algoritması uygulanır. Optimal tablo bize nihai çözümü verir.
Örnek
değiştirBir örnekle Büyük M yöntemini daha iyi ifade etmiş olalım.
Min Z = 4X1+X2 Amaç fonksiyonumuz olsun.
Kısıtlarımız ise;
3 X1 + X2 = 3
4 X1 + 3X2 >= 6
X1 + 2X2 =< 4
X1, X2 >= 0
Standart Hale getirip +R katsayılarını ekleyelim.
3 X1 + X2 + R1 = 3
4 X1 + 3X2 - X3 + R2 = 6
X1 + 2X2 + X4 = 4
X1, X2, X3, X4, R1, R2 >= 0
(X3 : artık değişken, X4 : dolgu değişkeni, R1,2 : yapay değişken, R ler matris oluşumuna yardım etmek için modele eklenir.)
Amaç fonksiyonu Min Z = 4X1+X2+MR1+MR2 olacaktır. (Min oldugu için +M)
R leri sol tarafta yalnız bırakıp amaç fonksiyonuna yerine yazıp düzenlediğimizde yeni amaç fonksiyonu şu şekilde olacaktır;
Min Z = (4-7M)X1 + (1-4M) X2 + MX3 + 9M
Sabit M değerleri sağ tarafda bırakılarak diğer değerler sola atılır ve amaç fonksiyonu başlangıç tablosuna geçmeden önceki son hali şu şekilde olur;
Z - (4-7M)X1 - (1-4M) X2 - MX3 = 9M
Başlangıç tablosunu oluştururken değişken isimleri sütünlara eklenme sırasına göre yazılır. Model standart haline getirilirken ilk önce artık değişken eklenecek ise eklenir ardından dolgu ve yapay değişkenler eklenir). Temeldeki olan değişkenler ise modele eklediğimiz dolgu ve yapay değişkenlerdir. (+ kaysayılı)
| Temel | X1 | X2 | X3 | R1 | R2 | X4 | Çözüm |
|---|---|---|---|---|---|---|---|
| Z | -4+7M | -1+4M | -M | 0 | 0 | 0 | 9M |
| R1 | 3 | 1 | 0 | 1 | 0 | 0 | 3 |
| R2 | 4 | 3 | -1 | 0 | 1 | 0 | 6 |
| X4 | 1 | 2 | 0 | 0 | 0 | 1 | 4 |
Temelde olmayan değişkenlerin Z satır değerlerine bakılır. Min problemlerde 0'a en uzak pozitif değer olan sütün temele girer ve çözüm değerleri bu sütun ile oranlarak 0 a en yakın pozitif değer temelden çıkar. X1 'in Z değerine bakalım. -4+7M değeri diğer değerlerden büyük ve pozitiftir ve R1 çözüm değeri bu sütun değeri ile oranlandıgında 0 a en yakın pozitif değeri vermiştir.
X1: anahtar sütun, R1 satırı ise anahtar satır olmuştur. X1 'i temele sokarken R1 satırının tüm değerleri pivot elemana bölünür. (Pivot: Anahtar satır ile Sütünun kesiştiği noktadaki değer) Böylece yeni X1 satırı bulunmuş olur. Bir sonraki satırlarda bu satır yardımıyla bulunur.
örneğin yeni Z satırı = Eski Z satırı - (İlgili satırın anahtar sütun elemanı) x (X1)
yeni R1 satırı = Eski R1 satırı - (İlgili satırın anahtar sütun elemanı) x (X1)
...
..
.
şeklinde devam ettikten sonra iterasyon işlemlerine 3. iterasyonda optimal tabloya ulaşmış oluruz. İterasyon işlemlerinin detayları için Simpleks yönteme bakınız.
| Temel | X1 | X2 | X3 | R1 | R2 | X4 | Çözüm |
|---|---|---|---|---|---|---|---|
| Z | 0 | 0 | 0 | 7/5 - M | -M | -1/5 | 17/5 |
| X1 | 1 | 0 | 0 | 2/5 | 0 | -1/5 | 2/5 |
| X2 | 0 | 1 | 0 | -1/5 | 0 | 3/5 | 9/5 |
| X3 | 0 | 0 | 1 | 1 | -1 | 1 | 1 |