15 Uygulamalı Özet
Bu sayfa kitabın yöntemlerini ispatsız, soru çözmeye dönük bir kopya kâğıdı olarak toplar. Uygulama sorularının çoğu “şu durumu modelleyiniz”, “bütün temel çözümleri bulunuz”, “grafik yöntemle çözünüz”, “simpleks yöntemle çözünüz” ya da “dualini yazınız” biçimindedir. Sayfa, bu soru tiplerinin her biri için adım adım bir çözüm algoritması verir. Tek bir örnek problemi modelden grafiğe ve optimal tabloya kadar izleyeceğiz; simpleks kısmının sonunda kendi problemini tablo tablo çözen bir hesaplayıcı da var. Her kural, ayrıntısının ve gerekçesinin bulunduğu bölüme bağlanır.
15.1 Soru Tipine Göre Yöntem
Bir soruyu okuyunca ilk iş, hangi yöntemin istendiğini ya da hangisinin en kısa yol olduğunu belirlemektir. Aşağıdaki tablo soru kalıplarını yöntemlerle eşleştirir.
| Soruda istenen | Kullanılacak yöntem | Bu sayfada |
|---|---|---|
| Sözel bir durumu lineer programlama problemi olarak yaz | Model kurma | Bölüm 15.2 |
| Problemi kanonik ya da standart forma getir | Dönüştürme kuralları | Bölüm 15.3, Bölüm 15.4 |
| Bütün temel çözümleri bul, optimal olanı seç | Tablo yöntemi: \(C(n, m)\) seçimi tek tek dene | Bölüm 15.5 |
| İki değişkenli problemi grafikle çöz | Grafik yöntem: aday köşe noktalarını karşılaştır | Bölüm 15.6 |
| Simpleks yöntemle çöz; kısıtlar \(\le\), sağ taraflar \(\ge 0\) | Doğrudan simpleks | Bölüm 15.8, Bölüm 15.9 |
| Simpleks yöntemle çöz; \(\ge\) ya da \(=\) kısıt var | Büyük M ya da iki faz yöntemi | Bölüm 15.11 |
| Dualini yaz, dual çözümü bul | Dual yazma, optimal tablodan okuma | Bölüm 15.12 |
| Sağ tarafı negatif ama kriterleri optimal bir tablo | Dual simpleks algoritması | Bölüm 15.13 |
| Bir katsayı ya da sağ taraf hangi aralıkta değişebilir? | Duyarlılık analizi | Bölüm 15.14 |
| Değişkenler tam sayı olmalı | Dal-sınır yöntemi | Bölüm 15.15 |
15.2 Model Kurma
Sözel bir problemden model kurmak, bütün çözümün temelidir; model yanlışsa sonraki hesapların hepsi boşa gider. Kitaptaki reçeteye (Bölüm 1.3) pratik bir ön adım ekleyerek şöyle çalışırız.
- Verileri tabloya diz. Satırlara kaynakları ya da gereksinimleri, sütunlara ürünleri yaz; en sağa kapasiteyi ya da gereksinimi, en alta birim kâr ya da maliyeti koy.
- Karar değişkenlerini birimleriyle tanımla: “\(x_1\): günde üretilen A miktarı (birim)” gibi. Tablonun her sütunu bir değişkendir.
- Kısıtları yaz. Tablonun her satırı bir kısıttır: satırdaki katsayılar ile değişkenlerin çarpımlarının toplamı, satırın sonundaki sayıyla karşılaştırılır. Karşılaştırmanın yönünü aşağıdaki sözlükten oku; iki yanın birimi aynı olmalıdır.
- İşaret koşullarını ekle: \(x_j \ge 0\).
- Amacı yaz: en alttaki satır amaç fonksiyonudur; kâr ise \(\max\), maliyet ise \(\min\).
Soru metnindeki kalıpların matematik karşılıkları şöyledir:
| Soruda geçen ifade | Matematik karşılığı |
|---|---|
| “en az \(a\)”, “\(a\)’dan az olmamalı”, “gereksinim \(a\)” | \(\ldots \ge a\) |
| “en çok \(a\)”, “en fazla”, “geçmemeli”, “aşmamalı”, “kapasite \(a\)” | \(\ldots \le a\) |
| “tam olarak \(a\)”, “tamamı kullanılmalı” | \(\ldots = a\) |
| “\(x_1\), \(x_2\)’nin en az iki katı olmalı” | \(x_1 \ge 2x_2\), yani \(x_1 - 2x_2 \ge 0\) |
| “\(x_1\), toplamın en çok %40’ı olmalı” | \(x_1 \le 0{,}4(x_1 + x_2)\), yani \(0{,}6x_1 - 0{,}4x_2 \le 0\) |
| “kâr, gelir en büyük olsun” | \(\max z\) |
| “maliyet, süre en küçük olsun”, “en ucuz” | \(\min z\) |
| “adet”, “kişi”, “araç” gibi bölünemeyen miktarlar | tam sayı koşulu: dal-sınır yöntemi |
Oran içeren kısıtlarda değişkenleri hep sol tarafa toplayıp sağ tarafı sabit bırakırız; aksi hâlde standart forma geçerken karışıklık çıkar.
Örnek 15.1 (Atölye problemi) Bir atölye A ve B ürünlerini üretiyor. Bir birim A için 1 saat makine ve 1 saat işçilik, bir birim B için 1 saat makine ve 3 saat işçilik gerekiyor. Günde en çok 4 saat makine ve 6 saat işçilik kullanılabiliyor. Bir birim A’dan 2 TL, bir birim B’den 3 TL kâr ediliyor. Günlük kârı en büyük yapacak üretim miktarlarını bulmak için problemi bir lineer programlama problemi olarak ifade ediniz.
Çözüm
Veri tablosu. Kaynaklar satırlara, ürünler sütunlara yazılır:
| A | B | Kapasite | |
|---|---|---|---|
| Makine (saat) | \(1\) | \(1\) | \(4\) |
| İşçilik (saat) | \(1\) | \(3\) | \(6\) |
| Kâr (TL) | \(2\) | \(3\) |
Karar değişkenleri. \(x_1\): günde üretilen A miktarı (birim), \(x_2\): günde üretilen B miktarı (birim).
Kısıtlar. Makine satırı: harcanan makine saati \(x_1 + x_2\)’dir ve “en çok 4” olmalıdır. İşçilik satırı: \(x_1 + 3x_2\), “en çok 6” olmalıdır. Üretim negatif olamaz.
Amaç. Kâr satırı \(2x_1 + 3x_2\)’dir ve en büyük yapılmak isteniyor. Model: \[ \begin{aligned} x_1 + x_2 &\le 4 \\ x_1 + 3x_2 &\le 6 \\ x_1, x_2 &\ge 0 \\ \max z &= 2x_1 + 3x_2 \end{aligned} \] Bu problemi sayfa boyunca önce tablo yöntemiyle, sonra grafik yöntemle çözeceğiz; simpleks hesaplayıcının ilk hazır örneği de budur. \(\blacksquare\)
15.3 Hangi Forma Getiriyorum?
Üç formu birbirinden ayıran şey, her birinin probleme neye baktığıdır. Kanonik form eşitsizliklerin yönüne, standart form eşitliklere ve sağ tarafların işaretine, simpleks yöntem ile çözülebilir hal ise bir birim matrisin varlığına bakar. Tanımlar için bkz. Tanım 1.6, Tanım 1.7 ve Tanım 1.9; ayrıntılı karşılaştırma için bkz. Tablo 1.2.
Pratikte her kısıta tek tek bakıp aşağıdaki tablodan ne yapılacağını okuruz. Sağ tarafı negatif bir kısıt varsa önce son satır uygulanır; kısıtın yönü döner ve kısıt, yeni yönüne karşılık gelen satıra göre işlenir.
| Kısıt | Kanonik form (max) | Kanonik form (min) | Standart form | Çözülebilir hal |
|---|---|---|---|---|
| \(\le b_i\) | aynen kalır | \(-1\) ile çarp: \(\ge -b_i\) | aylak ekle: \(+x_s\) | aylak birim sütun verir, ek yok |
| \(\ge b_i\) | \(-1\) ile çarp: \(\le -b_i\) | aynen kalır | artık çıkar: \(-x_s\) | yapay ekle: \(+x_{u}\) |
| \(= b_i\) | \(\le b_i\) ve \(\ge b_i\) diye ayır; \(\ge\) olanı \(-1\) ile çarp: \(\le -b_i\) | \(\le b_i\) ve \(\ge b_i\) diye ayır; \(\le\) olanı \(-1\) ile çarp: \(\ge -b_i\) | aynen kalır | yapay ekle: \(+x_{u}\) |
| \(b_i < 0\) | dokunma | dokunma | önce \(-1\) ile çarp, yön döner | standart formdaki gibi |
Amaç fonksiyonu için üç kural yeter:
- Aylak ve artık değişkenlerin amaç katsayısı \(0\)’dır.
- Yapay değişkenin amaç katsayısı minimumda \(+M\), maksimumda \(-M\)’dir (Tanım 1.10).
- Maksimum ile minimum arasında \(\min z = -\max(-z)\) ile geçilir: amaç katsayılarının hepsi \(-1\) ile çarpılır, kısıtlara dokunulmaz ve sonunda optimal değerin işareti geri çevrilir (Önerme 1.3).
Dual yazarken eşitlik ikiye ayrılmadan da bırakılabilir; o zaman karşılık gelen dual değişken işaretsiz olur (Önerme 11.1). Standart form için kanonik formdan geçmek gerekmez; eşitlikleri ikiye ayırmadan doğrudan standart forma geçmek daha kısadır. Kanonik form asıl olarak dual yazarken gerekir.
15.4 Değişken Kısıtları Tek Tabloda
Bütün yöntemler değişkenlerin \(\ge 0\) olmasını ister. \(x_j \ge 0\) dışındaki her koşul, \(x_j\) yerine yeni bir değişken yazılarak bu kalıba getirilir. Aşağıdaki tablo İşaret kısıtlaması olmayan değişkenler ve Sınırlı değişkenler bölümlerindeki bütün durumları bir araya getirir (Tablo 9.1).
| Verilen koşul | Yerine yaz | Yeni koşul | Kısıtlara eklenen satır | Sonunda geri dönüş |
|---|---|---|---|---|
| \(x_j \ge 0\) | değişiklik yok | \(x_j \ge 0\) | yok | yok |
| \(x_j \le 0\) | \(x_j = -x_j'\) | \(x_j' \ge 0\) | yok | \(x_j = -x_j'\) |
| işaretsiz | \(x_j = x_j' - x_j''\) | \(x_j', x_j'' \ge 0\) | yok | \(x_j = x_j' - x_j''\) |
| \(x_j \ge d_j\) | \(x_j = x_j' + d_j\) | \(x_j' \ge 0\) | yok | \(x_j = x_j' + d_j\) |
| \(x_j \le s_j\) | \(x_j = -x_j' + s_j\) | \(x_j' \ge 0\) | yok | \(x_j = s_j - x_j'\) |
| \(0 \le x_j \le s_j\) | değişiklik yok | \(x_j \ge 0\) | \(x_j \le s_j\) | yok |
| \(d_j \le x_j \le s_j\) | \(x_j = x_j' + d_j\) | \(x_j' \ge 0\) | \(x_j' \le s_j - d_j\) | \(x_j = x_j' + d_j\) |
Yani kural hep aynıdır: alt sınırı olan değişken alt sınırı kadar ötelenir, yalnız üst sınırı olan değişken üst sınırından geriye doğru yansıtılır, hiç sınırı olmayan değişken iki negatif olmayan değişkenin farkı olarak yazılır. Tablonun yanında şu üç noktayı unutmamak gerekir:
- Sağ taraflar değişir. Öteleme ve yansıtmada sabit terimler sağ tarafa geçer. Sağ taraf negatif çıkarsa kısıt \(-1\) ile çarpılır ve yönü döner (Tablo 15.3).
- Amaçta sabit belirir. Amaç \(z = z' + k\) biçimine gelir. Tabloya yalnız \(z'\)’nün katsayıları yazılır ve asıl optimal değer sonunda \(z_0 + k\) olarak hesaplanır.
- İşaretsiz değişken iki zıt sütun verir. \(x_j = x_j' - x_j''\) dönüşümünde \(v_j'' = -v_j'\) ve \(c_j'' = -c_j'\)’dür. Her tabloda bu iki sütun birbirinin negatifidir ve ikisi aynı anda bazda bulunmaz (Önerme 8.2).
Örnek 15.2 (Üç farklı değişken kısıtını birlikte dönüştürmek) \(x_1 \ge 2\), \(x_2\) işaretsiz ve \(1 \le x_3 \le 5\) olmak üzere \[ \begin{aligned} x_1 + 2x_2 + x_3 &\le 8 \\ 2x_1 - x_2 + x_3 &\ge 1 \\ \max z &= 3x_1 + x_2 - 2x_3 \end{aligned} \] problemini bütün değişkenleri \(\ge 0\) olan ve simpleks yöntem ile çözülebilir halde olan bir probleme dönüştürünüz.
Çözüm
Dönüşümler. Değişken kısıtları tablosuna (Tablo 15.4) göre üç değişken üç farklı satıra girer:
- \(x_1 \ge 2\) alttan sınırlıdır: \(x_1 = x_1' + 2\), \(x_1' \ge 0\).
- \(x_2\) işaretsizdir: \(x_2 = x_2' - x_2''\), \(x_2', x_2'' \ge 0\).
- \(1 \le x_3 \le 5\) iki yanlı sınırlıdır: \(x_3 = x_3' + 1\), \(x_3' \ge 0\) ve üst sınır \(x_3' \le 5 - 1 = 4\) satırı olarak eklenir.
Kısıtlar. Yerine koyup sabitleri sağa atalım. Birinci kısıt \[ \begin{aligned} &(x_1' + 2) + 2(x_2' - x_2'') + (x_3' + 1) \le 8 \\[1mm] &\quad \Longrightarrow \quad x_1' + 2x_2' - 2x_2'' + x_3' \le 5 \end{aligned} \] olur. İkinci kısıt \[ \begin{aligned} &2(x_1' + 2) - (x_2' - x_2'') + (x_3' + 1) \ge 1 \\[1mm] &\quad \Longrightarrow \quad 2x_1' - x_2' + x_2'' + x_3' \ge -4 \end{aligned} \] olur. Sağ taraf negatif çıktığı için iki yanı \(-1\) ile çarparız ve yön döner: \[ -2x_1' + x_2' - x_2'' - x_3' \le 4 . \]
Amaç. Amaç fonksiyonunda da yerine koyalım: \[ \begin{aligned} z &= 3(x_1' + 2) + (x_2' - x_2'') - 2(x_3' + 1) \\[1mm] &= 3x_1' + x_2' - x_2'' - 2x_3' + 4 . \end{aligned} \] Sabit \(4\) tabloya girmez: \(z = z' + 4\).
Sonuç. Üç kısıt da \(\le\) biçiminde ve sağ tarafları negatif olmadığı için aylak değişkenler \(x_4, x_5, x_6\) bir birim matris verir; yapay değişkene gerek yoktur: \[ \begin{aligned} x_1' + 2x_2' - 2x_2'' + x_3' + x_4 &= 5 \\ -2x_1' + x_2' - x_2'' - x_3' + x_5 &= 4 \\ x_3' + x_6 &= 4 \\ x_1', x_2', x_2'', x_3', x_4, x_5, x_6 &\ge 0 \\ \max z' &= 3x_1' + x_2' - x_2'' - 2x_3' \end{aligned} \] Simpleks yöntemin verdiği optimal çözümden \(x_1 = x_1' + 2\), \(x_2 = x_2' - x_2''\), \(x_3 = x_3' + 1\) ile orijinal değişkenlere dönülür; optimal değer \(z_0 + 4\)’tür.
Dikkat edilirse ikinci kısıt başta \(\ge\) idi ve yapay değişken gerektirecekti. Ötelemeden sonra sağ tarafı negatif çıktı, \(-1\) ile çarpınca \(\le\) oldu ve yapay değişken gereği ortadan kalktı. \(\blacksquare\)
15.5 Bütün Temel Çözümler: Tablo Yöntemi
Standart formda \(m\) denklem ve \(n\) değişken varsa, \(n - m\) değişken sıfırlanıp kalan kare sistem çözülerek bir temel çözüm bulunur (Tanım 2.3). Soru bütün temel çözümleri istiyorsa bütün seçimler bir tabloda denenir; optimal çözüm, uygun olanlar arasında amaç değeri en iyi olandır (Teorem 3.4).
- Standart form. Aylak ve artık değişkenleri ekle; \(m\) ve \(n\)’yi belirle.
- Seçimleri say. Temel değişken olacak \(m\) değişkenin bütün seçimlerini sistemli sırayla yaz; en çok \(C(n, m) = \dfrac{n!}{m!\,(n - m)!}\) seçim vardır (Önerme 2.1).
- Determinant. Her seçimde temel değişkenlerin sütunlarından oluşan kare matrisin \(\Delta\)’sını hesapla. \(\Delta = 0\) ise bu seçimden temel çözüm çıkmaz.
- Çöz ve sınıflandır. \(\Delta \ne 0\) ise diğer değişkenleri \(0\) alıp sistemi çöz. Negatif bileşen varsa çözüm uygun değildir; yoksa uygun temel çözümdür; bir temel değişken \(0\) çıkmışsa dejeneredir (Tanım 2.6).
- Optimum. Yalnız uygun temel çözümlerde \(z\)’yi hesapla ve en iyisini seç.
Örnek 15.3 (Atölye probleminin bütün temel çözümleri) Atölye probleminin (Örnek 15.1) bütün temel çözümlerini bulunuz ve optimal çözümü belirleyiniz.
Çözüm
Standart form. İki kısıta \(x_3\) ve \(x_4\) aylak değişkenleri eklenir: \[ \begin{aligned} x_1 + x_2 + x_3 &= 4 \\ x_1 + 3x_2 + x_4 &= 6 \end{aligned} \] \(m = 2\), \(n = 4\) olduğundan her seçimde iki değişken sıfırlanır ve en çok \(C(4, 2) = 6\) seçim vardır.
Bir seçimin hesabı. Temel değişkenler \(x_1, x_2\) olsun; \(x_3 = x_4 = 0\) alınır: \[ \begin{cases} x_1 + x_2 = 4 \\ x_1 + 3x_2 = 6 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 1 \\ 1 & 3 \end{vmatrix} = 2 \ne 0. \] İkinci denklemden birinciyi çıkarınca \(2x_2 = 2\), yani \(x_2 = 1\) ve \(x_1 = 3\) bulunur. Çözüm \((3, 1, 0, 0)\)’dır; negatif bileşeni olmadığı için uygundur ve \(z = 2 \cdot 3 + 3 \cdot 1 = 9\)’dur. Diğer beş seçim aynı yolla hesaplanır.
| Temel değişkenler | \(\Delta\) | \((x_1, x_2, x_3, x_4)\) | Uygun mu? | \(z\) |
|---|---|---|---|---|
| \(x_1, x_2\) | \(2\) | \((3, 1, 0, 0)\) | evet | \(9\) |
| \(x_1, x_3\) | \(-1\) | \((6, 0, -2, 0)\) | hayır | \(-\) |
| \(x_1, x_4\) | \(1\) | \((4, 0, 0, 2)\) | evet | \(8\) |
| \(x_2, x_3\) | \(-3\) | \((0, 2, 2, 0)\) | evet | \(6\) |
| \(x_2, x_4\) | \(1\) | \((0, 4, 0, -6)\) | hayır | \(-\) |
| \(x_3, x_4\) | \(1\) | \((0, 0, 4, 6)\) | evet | \(0\) |
Sonuç. Altı temel çözümün dördü uygundur ve hiçbiri dejenere değildir. Uygun olanlar arasında en büyük değer \(z = 9\)’dur: optimal çözüm \(x_1 = 3\), \(x_2 = 1\) ve \(\max z = 9\)’dur. Aylaklar \(x_3 = x_4 = 0\) olduğundan makine ve işçilik saatlerinin hepsi kullanılır. \(\blacksquare\)
15.6 Grafik Yöntem ve Aday Köşe Noktaları
Uygun bölge boş değil ve sınırlıysa optimum bir köşede alınır (Teorem 3.1). Bölge sınırsızken optimum varsa yine bir köşededir, ama önce var olup olmadığı seviye doğrusuyla denetlenir. Bu yüzden grafik yöntemin özü, aday noktaları, yani uygun bölgenin köşelerini eksiksiz bulup amaç değerlerini karşılaştırmaktır. Uygun temel çözümler de tam olarak bu köşelerdir (Teorem 3.3); tablo yöntemindeki uygun satırlar, grafikte köşe olarak karşımıza çıkar.
- Doğruları çiz. Her kısıtı eşitlik olarak yaz ve doğruyu eksenleri kestiği iki noktadan çiz.
- Yarı düzlemi seç. Doğru üzerinde olmayan bir test noktası (çoğunlukla \(O(0, 0)\)) kısıtı sağlıyorsa o tarafı, sağlamıyorsa öbür tarafı al. \(x_1, x_2 \ge 0\) birinci bölgeyi verir.
- Uygun bölgeyi tara. Bütün yarı düzlemlerin ortak kısmıdır. Ortak kısım boşsa uygun çözüm yoktur; dur.
- Aday noktaları bul. Bölgenin her köşesi iki sınır doğrusunun kesişimidir: iki denklemi çöz. Kesişim noktasının bütün kısıtları sağladığını kontrol et; sağlamayan kesişim bölgenin dışındadır ve aday değildir.
- Karşılaştır. Her aday noktada \(z\)’yi hesapla ve tabloya yaz. Maksimumda en büyük, minimumda en küçük değer optimaldir.
- Seviye doğrusuyla doğrula. \(z = k\) doğrusunu maksimumda \(\vec{c}\) yönünde, minimumda \(-\vec{c}\) yönünde kaydır; bölgeye son değdiği nokta optimaldir. Bölge sınırsızsa köşe karşılaştırmasından önce bu adım zorunludur.
Örnek 15.4 (Atölye probleminin grafik çözümü) Atölye problemini (Örnek 15.1) grafik yöntemle çözünüz. Aday noktaları bir tabloda toplayınız ve sonucu tablo yöntemiyle karşılaştırınız.
Çözüm
Doğrular ve yarı düzlemler. \(x_1 + x_2 = 4\) doğrusu \((4, 0)\) ve \((0, 4)\)’ten, \(x_1 + 3x_2 = 6\) doğrusu \((6, 0)\) ve \((0, 2)\)’den geçer. \(O(0, 0)\) iki kısıtı da sağladığından (\(0 \le 4\), \(0 \le 6\)) iki doğrunun da orijin tarafı alınır.
Aday noktalar. Uygun bölgenin köşeleri eksenlerle ve iki doğruyla sınırlanan dört noktadır. \(B\) köşesi iki kısıt doğrusunun kesişimidir: denklemler taraf tarafa çıkarılınca \(2x_2 = 2\), yani \(x_2 = 1\), \(x_1 = 3\) bulunur.
| Aday nokta | Kesişen doğrular | \(z = 2x_1 + 3x_2\) |
|---|---|---|
| \(O(0, 0)\) | \(x_1 = 0\), \(x_2 = 0\) | \(0\) |
| \(A(4, 0)\) | \(x_2 = 0\), \(x_1 + x_2 = 4\) | \(8\) |
| \(B(3, 1)\) | \(x_1 + x_2 = 4\), \(x_1 + 3x_2 = 6\) | \(9\) |
| \(C(0, 2)\) | \(x_1 = 0\), \(x_1 + 3x_2 = 6\) | \(6\) |
Aday olmayan kesişimler. \(x_2 = 0\) ile \(x_1 + 3x_2 = 6\) doğrusu \((6, 0)\)’da kesişir, ama \(6 + 0 = 6 > 4\) olduğundan bu nokta birinci kısıtı sağlamaz. Aynı biçimde \((0, 4)\) ikinci kısıtı sağlamaz: \(0 + 12 = 12 > 6\). Bu iki nokta, tablo yönteminde uygun çıkmayan iki temel çözümdür (Tablo 15.5).
Sonuç. En büyük değer \(B(3, 1)\)’dedir: \(\max z = 9\). Seviye doğrusu \(2x_1 + 3x_2 = 9\), \(\vec{c} = (2, 3)\) yönünde kaydırıldığında bölgeye son olarak \(B\)’de değer. Tablo yöntemi de aynı cevabı vermişti; dört aday nokta, dört uygun temel çözümün ilk iki bileşenidir. \(\blacksquare\)
Grafikte bazen tek bir optimal köşe yerine başka bir sonuç görülür. Dört durumu şöyle tanırız (Bölüm 3.3):
| Grafikte görülen | Sonuç |
|---|---|
| Yarı düzlemlerin ortak kısmı boş | Uygun çözüm yok |
| Seviye doğrusu optimal yönde bir kenarla çakışıyor | Alternatif optimal çözüm: kenarın bütün noktaları optimaldir |
| Bölge sınırsız ve seviye doğrusu iyileşme yönünde sonsuza kayabiliyor | Sınırsız çözüm |
| Bölge sınırsız ama seviye doğrusu bir köşede takılıyor | Optimum vardır ve o köşededir |
15.7 Simpleks Tablosunun Okunuşu
Bütün simpleks tabloları aynı düzende yazılır (Bölüm 4.3). Sembollerle tablo şöyledir; \(v_k\) baza girecek vektördür.
| \(c_j\) | \(c_1\) | \(\cdots\) | \(c_n\) | |||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(\cdots\) | \(v_n\) | Oran |
| \(x_{B_1}\) | \(c_{B_1}\) | \(y_{10}\) | \(y_{11}\) | \(\cdots\) | \(y_{1n}\) | \(y_{10} / y_{1k}\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | |
| \(x_{B_m}\) | \(c_{B_m}\) | \(y_{m0}\) | \(y_{m1}\) | \(\cdots\) | \(y_{mn}\) | \(y_{m0} / y_{mk}\) |
| \(z_j - c_j\) | \(z_0\) | \(z_1 - c_1\) | \(\cdots\) | \(z_n - c_n\) |
Tablonun her parçası tek bir soruya cevap verir:
- \(v_0\) sütunu: Şu anki çözüm nedir? Baz değişkenlerinin değerleri buradadır; bazda olmayan değişkenler \(0\)’dır.
- \(v_j\) sütunları: \(v_j\) vektörü baz vektörleri cinsinden nasıl yazılır? Bazdaki vektörlerin sütunları birim vektördür.
- Son satır: Çözüm iyileşir mi? \(z_j = \vec{c}_B^{\,T} \vec{y}_j\), yani \(c_B\) sütunu ile \(v_j\) sütununun karşılıklı çarpımlarının toplamıdır; ondan \(c_j\) çıkarılır. \(z_0 = \vec{c}_B^{\,T} \vec{y}_0\) amaç değeridir. Bazdaki vektörlerin kriteri \(0\)’dır.
- Oran sütunu: Hangi vektör bazdan çıkar? Yalnız \(y_{ik} > 0\) olan satırlar için \(y_{i0} / y_{ik}\) yazılır, diğerlerine \(-\) konur.
Pivot köşeli parantezle, bazdan çıkan satır \(\Rightarrow\) ile, baza giren sütun \(\Uparrow\) ile işaretlenir.
15.8 Giren, Çıkan ve Durma Kuralları
Maksimum ve minimum problemlerinde kurallar yalnız işaretlerde ayrılır. Yöntemin bütün adımları Simpleks yöntem bölümündeki yedi adımlık reçetededir (Bölüm 4.5).
| Maksimum | Minimum | |
|---|---|---|
| Tablo optimaldir | bütün \(z_j - c_j \ge 0\) | bütün \(z_j - c_j \le 0\) |
| Baza giren \(v_k\) | en negatif \(z_j - c_j\) | en büyük pozitif \(z_j - c_j\) |
| Bazdan çıkan \(v_r\) | \(y_{ik} > 0\) olanlar arasında en küçük \(y_{i0} / y_{ik}\) | aynı |
| Yapay değişkenin amaç katsayısı | \(-M\) | \(+M\) |
| \(aM + b\) biçimli kriterler | önce \(M\)’nin katsayısı, eşitse sabit terim karşılaştırılır | aynı |
Tablo bazen normal bir optimumdan farklı bir şey söyler. Hangi belirtinin neyi gösterdiği aşağıda toplanmıştır.
| Tabloda görülen | Anlamı | Ayrıntı |
|---|---|---|
| Giren \(v_k\) sütununda hiç pozitif eleman yok, bazda pozitif yapay değişken yok | Sınırsız çözüm: amaç sonsuza gider | Teorem 7.1 |
| Optimal tabloda baz dışı bir \(v_k\) için \(z_k - c_k = 0\) | Alternatif optimal çözüm olabilir: \(v_k\)’yı baza al | Teorem 7.2 |
| Optimal tabloda bazda pozitif değerli yapay değişken | Uygun çözüm yok | Teorem 5.2 |
| \(v_0\) sütununda \(0\) değerli baz değişkeni (oran testindeki eşitlik bunu doğurur) | Dejenere çözüm | Tanım 2.6 |
| Bazda \(0\) değerli yapay değişken | Gerçek bir sütunla pivot yap; olmuyorsa satır gereksizdir | Önerme 5.3 |
15.9 Yeni İterasyon Tablosu: Dikdörtgen Kuralı
Giren ve çıkan vektör belli olunca yeni tablonun bütün sayıları eski tablodan hesaplanır (Teorem 4.4). Elle hesapta en hızlı yol dikdörtgen kuralıdır ve aşağıdaki beş adımda uygulanır. Adımların sırası önemlidir: önce hiç hesap gerektirmeyen hücreler doldurulur, dikdörtgen kuralı yalnız geriye kalan hücrelere uygulanır.
- Pivot satırı. Pivot satırını pivota böl. Satırın adı baza giren \(x_k\), \(c_B\) değeri de \(c_k\) olur.
- Pivot sütunu. Pivot sütununu birim vektör yap: pivotun yerine \(1\), diğer bütün hücrelere (\(z_k - c_k\) dahil) \(0\) yaz.
- Sıfır kısayolu. Pivot sütununda \(0\) olan satırları ve pivot satırında \(0\) olan sütunları aynen kopyala. Bazda kalan vektörlerin birim sütunları bu yüzden hiç değişmez.
- Dikdörtgen kuralı. Kalan her \(A\) hücresi için \(A^{*} = A - \dfrac{B\, C}{P}\) hesapla. Burada \(P\) pivot, \(B\) hücrenin satırının pivot sütunundaki elemanı, \(C\) hücrenin sütununun pivot satırındaki elemanıdır. Kural \(v_0\) sütununa ve \(z_j - c_j\) satırına da uygulanır.
- Sağlama. \(z_0 = \vec{c}_B^{\,T} \vec{y}_0\) ve birkaç \(z_j - c_j\) değerini yeni \(c_B\) sütunuyla yeniden hesapla. \(v_0\) sütununda negatif sayı çıkmamalı, bazdaki vektörlerin kriteri \(0\) olmalıdır.
Kuralın içinde hatırlamayı kolaylaştıran üç gözlem var:
- \(B = 0\) ya da \(C = 0\) ise \(BC/P = 0\) olur ve hücre değişmez. Üçüncü adımdaki sıfır kısayolu buradan gelir.
- Aynı satırdaki bütün hücrelerde \(B\) aynıdır ve \(C / P\), yeni pivot satırındaki elemandır. Bu yüzden bir satırı tek hamlede de hesaplayabilirsin: yeni satır = eski satır \(-\) \(B\) \(\times\) yeni pivot satırı. Bu, Simpleks yöntem bölümündeki elemanter satır işlemleri yöntemidir; iki yol aynı sayıları verir.
- Pivot \(1\) ise kural \(A^{*} = A - BC\)’ye, ayrıca \(B = -1\) ise \(A^{*} = A + C\)’ye iner.
Örnek 15.5 (Dikdörtgen kuralıyla iki iterasyon) \[ \begin{aligned} x_1 &\le 4 \\ 2x_2 &\le 12 \\ 3x_1 + 2x_2 &\le 18 \\ x_1, x_2 &\ge 0 \\ \max z &= 3x_1 + 5x_2 \end{aligned} \] problemini simpleks yöntemle çözünüz. Her yeni tabloyu beş adımlık reçeteyle, dikdörtgen kuralını yalnız gereken hücrelere uygulayarak hesaplayınız.
Çözüm
Başlangıç tablosu. Kısıtlar \(\le\) ve sağ taraflar negatif olmadığı için \(x_3, x_4, x_5\) aylak değişkenleri bir birim matris verir. \(\vec{c}_B = \vec{0}\) olduğundan \(z_j - c_j = -c_j\)’dir. Maksimum probleminde en negatif kriter \(-5\)’tir, \(v_2\) baza girer. Oranlar \(12/2 = 6\) ve \(18/2 = 9\)’dur; \(x_3\) satırında \(v_2\) elemanı \(0\) olduğundan o satıra \(-\) yazılır. En küçük oran \(x_4\) satırındadır: \(v_4\) bazdan çıkar, pivot \(2\)’dir.
| \(c_j\) | \(3\) | \(5\) | \(0\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | Oran |
| \(x_3\) | \(0\) | \(4\) | \(1\) | \(0\) | \(1\) | \(0\) | \(0\) | \(-\) |
| \(x_4\) | \(0\) | \(12\) | \(0\) | \([2]\) | \(0\) | \(1\) | \(0\) | \(\frac{12}{2} \Rightarrow\) |
| \(x_5\) | \(0\) | \(18\) | \(3\) | \(2\) | \(0\) | \(0\) | \(1\) | \(\frac{18}{2}\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-3\) | \(-5 \Uparrow\) | \(0\) | \(0\) | \(0\) |
Birinci iterasyon. Aşağıdaki şekil başlangıç tablosunun her hücresini, yeni değerini bulmak için gereken işe göre boyuyor.
- Pivot satırı \(2\)’ye bölünür ve \(x_2\) satırı olur (\(c_B = 5\)): \((6 \mid 0,\ 1,\ 0,\ \tfrac{1}{2},\ 0)\).
- \(v_2\) sütunu \((0, 1, 0)\) olur, kriteri \(0\)’dır.
- \(x_3\) satırının pivot sütunundaki elemanı \(0\) olduğundan bu satır aynen kalır. Pivot satırında \(v_1\), \(v_3\), \(v_5\) sütunlarının elemanı \(0\) olduğundan bu sütunlar da aynen kalır.
- Geriye yalnız dört hücre kalır. \(x_5\) satırında \(B = 2\), \(z_j - c_j\) satırında \(B = -5\)’tir; \(C\) değerleri pivot satırındaki \(12\) (\(v_0\)) ve \(1\) (\(v_4\))’dir: \[ \begin{aligned} x_5, v_0&: \ 18 - \frac{2 \cdot 12}{2} = 6, & x_5, v_4&: \ 0 - \frac{2 \cdot 1}{2} = -1, \\[1mm] z_0&: \ 0 - \frac{(-5) \cdot 12}{2} = 30, & z_4 - c_4&: \ 0 - \frac{(-5) \cdot 1}{2} = \frac{5}{2}. \end{aligned} \]
- Sağlama: \(\vec{c}_B = (0, 5, 0)\) ile \(z_0 = 5 \cdot 6 = 30\) ve \(z_4 - c_4 = 5 \cdot \tfrac{1}{2} - 0 = \tfrac{5}{2}\).
En negatif kriter \(-3\) olduğundan \(v_1\) baza girer. Oranlar \(x_3\) satırında \(4/1 = 4\), \(x_5\) satırında \(6/3 = 2\)’dir; \(x_2\) satırının elemanı \(0\) olduğundan oran yazılmaz. \(v_5\) bazdan çıkar, pivot \(3\)’tür.
| \(c_j\) | \(3\) | \(5\) | \(0\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | Oran |
| \(x_3\) | \(0\) | \(4\) | \(1\) | \(0\) | \(1\) | \(0\) | \(0\) | \(\frac{4}{1}\) |
| \(x_2\) | \(5\) | \(6\) | \(0\) | \(1\) | \(0\) | \(\frac{1}{2}\) | \(0\) | \(-\) |
| \(x_5\) | \(0\) | \(6\) | \([3]\) | \(0\) | \(0\) | \(-1\) | \(1\) | \(\frac{6}{3} \Rightarrow\) |
| \(z_j - c_j\) | \(z_0 = 30\) | \(-3 \Uparrow\) | \(0\) | \(0\) | \(\frac{5}{2}\) | \(0\) |
İkinci iterasyon. Aynı boyamayı birinci iterasyon tablosu için yapalım.
- Pivot satırı \(3\)’e bölünür ve \(x_1\) satırı olur (\(c_B = 3\)): \((2 \mid 1,\ 0,\ 0,\ -\tfrac{1}{3},\ \tfrac{1}{3})\).
- \(v_1\) sütunu \((0, 0, 1)\) olur, kriteri \(0\)’dır.
- \(x_2\) satırının pivot sütunundaki elemanı \(0\) olduğundan bu satır aynen kalır. Pivot satırında \(v_2\) ve \(v_3\) sütunlarının elemanı \(0\) olduğundan bu sütunlar da aynen kalır.
- Geriye altı hücre kalır. \(x_3\) satırında \(B = 1\), \(z_j - c_j\) satırında \(B = -3\)’tür; \(C\) değerleri pivot satırındaki \(6\), \(-1\) ve \(1\)’dir: \[ \begin{aligned} x_3, v_0&: \ 4 - \frac{1 \cdot 6}{3} = 2, & z_0&: \ 30 - \frac{(-3) \cdot 6}{3} = 36, \\[1mm] x_3, v_4&: \ 0 - \frac{1 \cdot (-1)}{3} = \frac{1}{3}, & z_4 - c_4&: \ \frac{5}{2} - \frac{(-3)(-1)}{3} = \frac{3}{2}, \\[1mm] x_3, v_5&: \ 0 - \frac{1 \cdot 1}{3} = -\frac{1}{3}, & z_5 - c_5&: \ 0 - \frac{(-3) \cdot 1}{3} = 1. \end{aligned} \]
- Sağlama: \(\vec{c}_B = (0, 5, 3)\) ile \(z_0 = 5 \cdot 6 + 3 \cdot 2 = 36\), \(z_4 - c_4 = 5 \cdot \tfrac{1}{2} + 3 \cdot \left(-\tfrac{1}{3}\right) = \tfrac{3}{2}\), \(z_5 - c_5 = 3 \cdot \tfrac{1}{3} = 1\).
| \(c_j\) | \(3\) | \(5\) | \(0\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) |
| \(x_3\) | \(0\) | \(2\) | \(0\) | \(0\) | \(1\) | \(\frac{1}{3}\) | \(-\frac{1}{3}\) |
| \(x_2\) | \(5\) | \(6\) | \(0\) | \(1\) | \(0\) | \(\frac{1}{2}\) | \(0\) |
| \(x_1\) | \(3\) | \(2\) | \(1\) | \(0\) | \(0\) | \(-\frac{1}{3}\) | \(\frac{1}{3}\) |
| \(z_j - c_j\) | \(z_0 = 36\) | \(0\) | \(0\) | \(0\) | \(\frac{3}{2}\) | \(1\) |
Bütün \(z_j - c_j \ge 0\) olduğundan tablo optimaldir. Optimal çözüm \(x_1 = 2\), \(x_2 = 6\) ve \(\max z = 3 \cdot 2 + 5 \cdot 6 = 36\)’dır. Aylak \(x_3 = 2\), birinci kısıtta \(2\) birim boşluk kaldığını söyler; ikinci ve üçüncü kısıtlar tam sağlanır.
İki iterasyonda tablonun \(4 \cdot 6 = 24\) sayısal hücresinden yalnız \(4\) ve \(6\) tanesi gerçek hesap istedi; geri kalanlar bölme, birim sütun ya da kopyalamayla doldu. \(\blacksquare\)
15.10 Simpleks Hesaplayıcı
Aşağıdaki hesaplayıcı bir problemi kitabın tablo düzeninde adım adım çözer. Her tabloda pivotu köşeli parantezle, bazdan çıkan satırı \(\Rightarrow\) ile, baza giren sütunu \(\Uparrow\) ile işaretler; her iterasyonun altına giren ve çıkan vektörün neden seçildiğini yazar. Kesirlerle tam hesap yapar, ondalığa yuvarlamaz. \(\ge\) ve \(=\) kısıtlarında Büyük M yöntemini kullanır ve bazdan çıkan yapay değişkenin sütununu sonraki tablolarda yazmaz (Bölüm 15.11).
Hesaplayıcıyı kendi çözümünü tablo tablo karşılaştırmak için kullan. Bir tabloda fark bulursan hatayı o iterasyonun dikdörtgen hesabında ara. Üç noktaya dikkat:
- Bütün değişkenler \(\ge 0\) kabul edilir. Başka bir değişken kısıtı varsa problemi önce Tablo 15.4 ile dönüştür.
- Katsayılar tam sayı (\(-3\)), kesir (\(3/4\)) ya da ondalık (\(0{,}5\)) olarak yazılabilir.
- Kriterlerde ya da oranlarda eşitlik olursa hesaplayıcı soldaki sütunu ve üstteki satırı seçer. Elle çözümde öbür seçim de doğrudur; ara tablolar farklı çıkabilir ama optimal değer aynıdır.
Simpleks Hesaplayıcı
Satırlar kısıtlardır; en üst satır amaç fonksiyonunun katsayılarıdır. Bütün değişkenler ≥ 0 kabul edilir.
15.11 Başlangıç Bazı Yoksa: Büyük M mi, İki Faz mı?
Kısıtlarda \(\ge\) ya da \(=\) varsa standart form birim matris içermeyebilir ve yapay değişken eklenir. Bundan sonra iki yol vardır; ikisi de aynı tabloları farklı bir amaçla yürütür. Büyük M yönteminde başlangıç tablosu şöyle kurulur.
- Standart form. Sağ tarafı negatif satırı \(-1\) ile çarp; \(\le\) kısıta aylak ekle, \(\ge\) kısıttan artık çıkar.
- Yapaylar. Birim sütunu olmayan her satıra (\(\ge\) ve \(=\) satırları) bir yapay değişken ekle; amaç katsayısı minimumda \(+M\), maksimumda \(-M\)’dir.
- Başlangıç bazı. \(\le\) satırlarında aylak, diğer satırlarda yapay değişken bazdadır; \(c_B\) sütununa bunların katsayıları (\(0\) ya da \(\pm M\)) yazılır.
- Son satır kısayolu. Aylakların maliyeti \(0\) olduğundan yalnız yapaylı satırlar katkı verir: her sütun için \[ \begin{aligned} z_j - c_j &= \pm M \cdot (\text{yapaylı satırlardaki elemanlar toplamı}) - c_j , \\[1mm] z_0 &= \pm M \cdot (\text{yapaylı satırların sağ tarafları toplamı}); \end{aligned} \] işaret minimumda \(+\), maksimumda \(-\)’dir.
- İterasyonlar. Kriterleri önce \(M\)’nin katsayısına göre karşılaştır; bazdan çıkan yapayın sütununu sil. Optimal tabloda bazda pozitif bir yapay kaldıysa uygun çözüm yoktur.
Örneğin minimum probleminde tek yapaylı satır \((2 \mid 2,\ 1,\ -1,\ 0,\ 0)\) ve \(c_1 = -3\), \(c_2 = 1\) ise kriterler \(z_1 - c_1 = 2M + 3\), \(z_2 - c_2 = M - 1\), \(z_3 - c_3 = -M\) ve \(z_0 = 2M\)’dir; Tablo 5.1 ile karşılaştır.
| Büyük M yöntemi | İki faz yöntemi | |
|---|---|---|
| Amaç | Orijinal amaç ve yapaylar için \(+M\) (min) ya da \(-M\) (max) | 1. faz: \(\min g = \sum x_{u_i}\) (max’ta \(\max g = -\sum x_{u_i}\)); 2. faz: orijinal amaç |
| Kriterler | \(aM + b\) biçiminde; önce \(M\)’nin katsayısı karşılaştırılır | Sayı; 1. fazda yapayların katsayısı \(\pm 1\) |
| Bazdan çıkan yapay | Sütunu sonraki tablolarda yazılmaz | Sütunu atılır |
| Uygun çözüm yok | Optimal tabloda bazda pozitif yapay değişken kalır | 1. fazın sonunda \(g \ne 0\) |
| Bazda \(0\) değerli yapay | Gerçek bir sütundaki sıfır olmayan elemanla pivot yap; hepsi sıfırsa satır gereksizdir, silinir | Aynı; sonra 2. faza geçilir |
| Geçiş | Yok, tek aşama | 1. fazın optimal tablosunda \(c_j\) satırı ve \(c_B\) sütunu orijinal katsayılarla değiştirilir, son satır yeniden hesaplanır |
Yani iki faz yöntemi, Büyük M yöntemindeki “\(M\) çok büyük” fikrini iki aşamaya böler: önce yalnız \(M\)’li kısım en iyilenir, sonra sabit kısım (Önerme 6.4). Elle hesapta \(M\)’li ifadelerle uğraşmak istemiyorsan iki faz yöntemini seç.
15.12 Dual Problemi Yazmak
Dual, kanonik formdaki primalin katsayı tablosunun sütun sütun okunmasıdır (Tanım 11.1). Primal maksimum problemiyse karşılıklar aşağıdaki gibidir; primal minimumsa bütün eşitsizlik yönleri ters döner.
| Maksimum primal | Minimum dual |
|---|---|
| \(m\) kısıt, \(n\) değişken | \(n\) kısıt, \(m\) değişken |
| \(i\). kısıt \(\le b_i\) | \(y_i \ge 0\) |
| \(i\). kısıt \(\ge b_i\) | önce \(-1\) ile çarp (\(\le -b_i\)), sonra \(y_i \ge 0\) |
| \(i\). kısıt \(= b_i\) | \(y_i\) işaretsiz (Önerme 11.1) |
| \(x_j \ge 0\) | \(j\). dual kısıt \(a_{1j}y_1 + \dots + a_{mj}y_m \ge c_j\) |
| \(x_j\) işaretsiz | \(j\). dual kısıt eşitlik: \(\dots = c_j\) (Önerme 11.1) |
| \(x_j \le 0\) | önce \(x_j = -x_j'\) yaz, sonra tanımı uygula |
| Amaç katsayıları \(c_j\) | Dual kısıtların sağ tarafları |
| Sağ taraflar \(b_i\) | Dual amacın katsayıları: \(\min g = b_1y_1 + \dots + b_my_m\) |
Sağ tarafları negatif olmayan bir problemde primalin optimal tablosu dualin çözümünü de verir (Önerme 11.2). Primal maksimumsa \(i\). kısıtın dual değişkeni, o kısıtın aylak sütununun kriteridir: \(y_i^{*} = z_{n+i} - c_{n+i}\). Primal minimumsa dual değişken, artık sütununun kriterinin negatifidir: \(y_i^{*} = -(z_{n+i} - c_{n+i})\). Güçlü dualite gereği iki optimal değer eşittir (Teorem 11.3).
Örnek 15.6 (Dual çözümü optimal tablodan okumak) Dikdörtgen kuralı örneğindeki (Örnek 15.5) problemin dualini yazınız ve dual optimal çözümü o örneğin optimal tablosundan (Tablo 15.13) okuyunuz.
Çözüm
Dual. Primal kanonik formdaki bir maksimum problemidir; üç kısıtına \(y_1, y_2, y_3 \ge 0\) karşılık gelir. Katsayı tablosunu sütun sütun okursak \[ \begin{aligned} y_1 + 3y_3 &\ge 3 \\ 2y_2 + 2y_3 &\ge 5 \\ y_1, y_2, y_3 &\ge 0 \\ \min g &= 4y_1 + 12y_2 + 18y_3 \end{aligned} \] bulunur.
Tablodan okuma. Aylak değişkenler \(x_3, x_4, x_5\) sırasıyla birinci, ikinci ve üçüncü kısıta aittir. Optimal tablodaki kriterleri \(0\), \(\tfrac{3}{2}\) ve \(1\)’dir. Buna göre \[ y_1^{*} = 0, \qquad y_2^{*} = \frac{3}{2}, \qquad y_3^{*} = 1 . \]
Sağlama. Dual kısıtlar \(0 + 3 \cdot 1 = 3 \ge 3\) ve \(2 \cdot \tfrac{3}{2} + 2 \cdot 1 = 5 \ge 5\) ile sağlanır. Amaç değeri \(g = 4 \cdot 0 + 12 \cdot \tfrac{3}{2} + 18 \cdot 1 = 36\)’dır ve primalin \(\max z = 36\) değerine eşittir. \(y_1^{*} = 0\) olmasının nedeni de tablodadır: aylak \(x_3\) bazdadır (\(x_3 = 2\)), bazdaki vektörlerin kriteri \(0\) olduğundan (Önerme 4.1) \(y_1^{*} = z_3 - c_3 = 0\) çıkar. \(\blacksquare\)
15.13 Dual Simpleks Algoritması
Dual simpleks algoritması simpleks yöntemin aynasıdır: önce satır, sonra sütun seçer (Tanım 12.2). İki yöntemi yan yana koyalım.
| Simpleks yöntem | Dual simpleks algoritması | |
|---|---|---|
| Tablonun durumu | Uygun: \(v_0\) sütunu \(\ge 0\) | Dual uygun: kriterler optimal işaretli, \(v_0\)’da negatif olabilir |
| Önce seçilen | Giren sütun: kritere göre | Çıkan satır: en negatif \(x_{Bi}\) |
| Sonra seçilen | Çıkan satır: \(y_{ik} > 0\) olanlarda en küçük \(y_{i0} / y_{ik}\) | Giren sütun: \(y_{rj} < 0\) olanlarda en küçük \(\left\lvert (z_j - c_j) / y_{rj} \right\rvert\) |
| Pivot | Pozitif | Negatif |
| Oranların yeri | Sağda, Oran sütunu | Altta, Oran satırı |
| Durma | Kriterler optimal işaretli | \(v_0\) sütunu \(\ge 0\) |
| Olumsuz sonuç | Giren sütunda pozitif eleman yok: sınırsız | Pivot satırında negatif eleman yok: uygun çözüm yok |
Dual simpleks iki yerde işe yarar. Birincisi, maliyetleri negatif olmayan ve \(\ge\) kısıtlı bir minimum probleminde \(\ge\) kısıtları \(-1\) ile çarpılınca yapay değişkene gerek kalmadan dual uygun bir başlangıç tablosu elde edilir (Önerme 12.2). İkincisi, duyarlılık analizinde sağ taraf değişince optimal tablonun \(v_0\) sütunu negatif olabilir; tablo hâlâ dual uygun olduğundan dual simpleks kaldığı yerden devam eder (Bölüm 12.6). Yeni tablo yine dikdörtgen kuralıyla hesaplanır.
15.14 Duyarlılık Analizi Formülleri
Duyarlılık analizinin bütün hesapları optimal bazın \(B\) matrisine dayanır (Tanım 10.2). \(B\), optimal tablodaki baz değişkenlerinin standart formdaki sütunlarından tablonun satır sırasıyla kurulur ve tablonun her parçası onunla yazılır (Teorem 10.1): \[ \vec{y}_j = B^{-1} v_j, \qquad v_0 \text{ sütunu} = B^{-1}\vec{b}, \qquad z_0 = \vec{c}_B^{\,T} B^{-1} \vec{b}. \] Bütün kısıtlar \(\le\) ise \(B^{-1}\)’i hesaplamaya gerek yoktur: optimal tablonun aylak sütunlarında hazır durur (Önerme 10.1). Örneğin Tablo 15.13 tablosunda \(v_3, v_4, v_5\) sütunları \(B^{-1}\)’in sütunlarıdır.
| Değişen veri | Ne hesaplanır | Optimallik korunur, eğer |
|---|---|---|
| Temel dışı \(x_k\)’nın \(c_k\)’sı | Yalnız \(z_k - c_k\) | max: \(c_k \le z_k\); min: \(c_k \ge z_k\) |
| Temelde olan \(x_r\)’nin \(c_r\)’si | \(c_r\)’yi sembol bırak, temel dışı bütün kriterleri \(c_r\) cinsinden yaz | Hepsi max’ta \(\ge 0\), min’de \(\le 0\); aralıkların kesişimi |
| Sağ taraf \(b_i\) | \(b_i\)’yi sembol bırak, \(B^{-1}\vec{b}\)’yi hesapla | \(B^{-1}\vec{b} \ge \vec{0}\); aralıkların kesişimi |
Aralığın dışına çıkılırsa tablo bozulur: kriter bozulduysa simpleks yöntemle, \(v_0\) bozulduysa dual simpleks algoritmasıyla devam edilir.
15.15 Dal-Sınır Yöntemi Kısaca
Tam sayılı bir problem, tam sayı şartı kaldırılmış LP problemleri çözülerek adım adım daraltılır (Bölüm 13.5). Maksimum probleminde:
- Başla. Rahatlatılmış problemi çöz. Değeri Ü.S olur; başta \(\text{A.S} = -\infty\).
- Dallandır. Kesirli bir \(x_j = a\) seç ve iki alt problem kur: birine \(x_j \le \lfloor a \rfloor\), öbürüne \(x_j \ge \lceil a \rceil\) kısıtını ekle.
- Buda. Her alt problemin rahatlatılmış çözümüne bak (Tanım 13.6):
| Durum | Karar |
|---|---|
| Uygun çözüm yok | Buda (D2) |
| Çözüm tam sayılı | Aday; \(z > \text{A.S}\) ise yeni A.S olur; buda (D3) |
| \(z \le \text{A.S}\) | Buda (D1) |
| Hiçbiri | Dallandırmak üzere beklet |
- Bitir. Bekleyen alt problem kalmayınca en iyi aday optimaldir; aday yoksa uygun tam sayılı çözüm yoktur.
Minimum probleminde Ü.S ile A.S yer değiştirir: rahatlatılmış değer A.S olur, başta \(\text{Ü.S} = +\infty\) alınır ve \(z \ge \text{Ü.S}\) olan alt problem budanır.
15.16 Son Kontrol Listesi
Bir çözümü bitirmeden önce şu soruları sor:
- Modelde her kısıtın iki yanının birimi aynı mı? “En az” ve “en çok” yönleri doğru mu?
- Tablo yönteminde \(C(n, m)\) seçimin hepsini yazdın mı, \(\Delta = 0\) olanları ayırdın mı?
- Grafik yöntemde bütün aday köşeleri buldun mu? Her kesişim noktasının bütün kısıtları sağladığını kontrol ettin mi?
- Standart formda bütün sağ taraflar \(\ge 0\) mı? Sağ taraf negatifse satırı \(-1\) ile çarpıp yapay değişkenden önce düzelttin mi?
- Yapay değişkenin katsayısı doğru mu: minimumda \(+M\), maksimumda \(-M\)?
- Giren vektörü doğru işaretle mi seçtin: maksimumda en negatif, minimumda en büyük pozitif kriter?
- Oran testinde yalnız pozitif elemanları mı kullandın?
- Her yeni tabloda baz sütunları birim vektör, kriterleri \(0\) mı? \(z_0 = \vec{c}_B^{\,T}\vec{y}_0\) sağlamasını yaptın mı?
- Dönüştürülmüş değişkenlerden (\(x_j'\), \(x_j''\)) orijinal değişkenlere döndün mü, amaçtaki sabiti optimal değere ekledin mi?
Kuralları bir bütün hâlinde uygulamak için Alıştırmalar bölümündeki çözümlü problemlere dönebilirsin.