7 Sınırsız Çözüm ve Alternatif Optimal Çözüm
Simpleks yöntem her iterasyonda iki soru sorar: Amacı iyileştiren bir vektör var mı, varsa onu baza alırken hangi vektör bazdan çıkar? Simpleks yöntem, Büyük M yöntemi ve İki faz yöntemi bölümlerindeki örneklerde bu soruların cevabı hep sonunda tek bir optimal çözüme götürdü. Ama iki şey ters gidebilir. Birincisi, iyileştiren bir vektör bulunur ama oran testi yapılamaz, çünkü sütununda hiç pozitif eleman yoktur. İkincisi, optimal tabloya ulaşılır ama baz dışındaki bir vektörün simpleks kriteri sıfırdır.
Bu bölümde bu iki durumu inceleyeceğiz. Birincisi sınırsız çözüm demektir: amaç fonksiyonu istenildiği kadar iyileştirilebilir ve optimal çözüm yoktur. İkincisi alternatif optimal çözüm demektir: aynı optimal değeri veren birden fazla, hatta sonsuz çok çözüm vardır. Her ikisini de önce tabloda nasıl tanıyacağımızı söyleyip sonra nedenini ispatlayacak, sonra da uygun bölgenin şekli üzerinde göreceğiz.
7.1 Tablodan Okunan İki Eşitlik
İki durumun ispatında da aynı araç işimize yarayacak: Bir simpleks tablosu, yalnız o anki uygun temel çözümü değil, kısıtları sağlayan her çözümü baz dışındaki değişkenler cinsinden yazmamızı sağlar.
Simpleks yöntem bölümündeki gibi standart formdaki (Tanım 1.7) problemi \(x_1 v_1 + \dots + x_n v_n = v_0\), \(x_j \ge 0\) biçiminde yazalım ve değişkenleri, bazın vektörleri ilk \(m\) sütun olacak şekilde numaralandıralım: \(B_0 = (v_1, \dots, v_m)\). Bu bazın uygun temel çözümü \(X_0\), baz değişkenlerinin değerleri \(x_i = y_{i0}\), amaç değeri \(z_0\) olsun. Tablonun \(v_j\) sütununda \(v_j\)’nin bu baza göre \(y_{1j}, \dots, y_{mj}\) katsayıları, en alt satırda da \(z_j - c_j\) simpleks kriteri durur.
Lemma 7.1 (Tablodan okunan eşitlikler) \(\vec{u} = (u_1, \dots, u_n)\), \(u_1 v_1 + \dots + u_n v_n = v_0\) eşitliğini sağlayan herhangi bir vektör olsun. Bu durumda her \(i = \overline{1,m}\) için \[ u_i = x_i - \sum_{j=m+1}^{n} y_{ij}\, u_j \tag{1} \] ve \[ z(\vec{u}) = z_0 - \sum_{j=m+1}^{n} (z_j - c_j)\, u_j \tag{2} \] olur. Toplamlar yalnız baz dışındaki değişkenler üzerindendir.
İspat
(1) eşitliği. Her \(v_j\)’yi baz cinsinden yazalım: \(v_j = \sum_{i=1}^{m} y_{ij} v_i\). Baz vektörleri için bu yazım \(v_i = 1 \cdot v_i\) yazılışıdır, yani \(j \le m\) ise \(y_{jj} = 1\) ve \(i \ne j\) için \(y_{ij} = 0\)’dır. Yerine koyarsak \[ v_0 = \sum_{j=1}^{n} u_j v_j = \sum_{i=1}^{m} \Big( \sum_{j=1}^{n} y_{ij}\, u_j \Big) v_i \] bulunur. Öte yandan \(v_0 = \sum_{i=1}^{m} x_i v_i\)’dir. Baz vektörleri lineer bağımsız olduğundan bir vektörün baz cinsinden yazılışı tektir; katsayıları eşitleriz: \[ \sum_{j=1}^{n} y_{ij}\, u_j = x_i , \qquad i = \overline{1,m}. \] Soldaki toplamda \(j \le m\) terimlerinden yalnız \(j = i\) terimi kalır ve \(u_i\)’ye eşittir. Böylece \(u_i + \sum_{j=m+1}^{n} y_{ij} u_j = x_i\), yani (1) elde edilir.
(2) eşitliği. Amaç fonksiyonunu baz değişkenleri ve baz dışındaki değişkenler diye ikiye ayıralım, baz değişkenlerine (1)’i koyalım: \[ \begin{aligned} z(\vec{u}) &= \sum_{i=1}^{m} c_i u_i + \sum_{j=m+1}^{n} c_j u_j \\[1mm] &= \sum_{i=1}^{m} c_i x_i - \sum_{j=m+1}^{n} \Big( \sum_{i=1}^{m} c_i y_{ij} \Big) u_j \\[1mm] &\quad + \sum_{j=m+1}^{n} c_j u_j . \end{aligned} \] İlk toplam \(z_0\), parantez içindeki toplam da \(z_j = \vec{c}_B^{\,T} \vec{y}_j\)’dir. Son iki toplamı birleştirince (2) eşitliği elde edilir.
\(\blacksquare\)
Yani tablonun her satırı bir baz değişkenini, en alt satırı da amaç fonksiyonunu baz dışındaki değişkenler cinsinden verir. Baz dışındaki değişkenlerin hepsi sıfırken (1) ve (2) eşitlikleri \(X_0\)’ı ve \(z_0\)’ı geri verir. Baz dışındaki \(x_j\) bir birim artırılırsa baz değişkeni \(x_i\), \(y_{ij}\) kadar azalır, amaç değeri de \(z_j - c_j\) kadar azalır. Bu okuma bu bölümün bütün sonuçlarının anahtarıdır.
7.2 Sınırsız Çözüm
Önce amaç fonksiyonunun hiçbir sınır tanımadığı durumu tanımlayalım.
Tanım 7.1 (Sınırsız çözüm) Uygun çözümü olan bir minimum probleminde amaç fonksiyonu alttan sınırlı değilse, yani her \(K\) sayısı için \(z(\vec{x}) < K\) olan bir uygun çözüm \(\vec{x}\) varsa, problemin sınırsız çözümü vardır denir. Maksimum probleminde her \(K\) için \(z(\vec{x}) > K\) olan bir uygun çözüm varsa, yani amaç fonksiyonu üstten sınırlı değilse, yine problemin sınırsız çözümü vardır denir.
Yani sınırsız çözümlü bir problemde uygun çözüm bol bol vardır, ama “en iyisi” yoktur: hangi uygun çözümü alırsak alalım, ondan daha iyi bir uygun çözüm bulunur. Bu yüzden sınırsız çözümlü problemin optimal çözümü yoktur. Uygun çözümü hiç olmayan problemle karıştırmamak gerekir; orada optimal çözümün yokluğu, aday bulunmamasından kaynaklanır.
Amaç fonksiyonunu sınırsız iyileştirmek için uygun bölgede sonsuza kadar gidebilmek gerekir. Bunu bir vektörle ifade edelim.
Tanım 7.2 (Uygun bölgenin yön vektörü) \(A\vec{x} = \vec{b}\), \(\vec{x} \ge 0\) uygun bölgesi için \[ \vec{d} \ne \vec{0}, \qquad \vec{d} \ge 0, \qquad A\vec{d} = \vec{0} \] koşullarını sağlayan \(\vec{d}\) vektörüne uygun bölgenin bir yön vektörü denir.
Yani \(\vec{d}\) bir yön vektörüyse, herhangi bir uygun \(\vec{x}\) çözümünden \(\vec{d}\) yönünde ne kadar gidersek gidelim uygun bölgede kalırız: her \(\lambda \ge 0\) için \(A(\vec{x} + \lambda \vec{d}) = A\vec{x} + \lambda A\vec{d} = \vec{b}\) ve \(\vec{x} + \lambda \vec{d} \ge 0\)’dır. Özellikle yön vektörü olan boş olmayan bir uygun bölge sınırsızdır. Amaç değeri bu yarı doğru boyunca \(z(\vec{x} + \lambda \vec{d}) = z(\vec{x}) + \lambda\, \vec{c}^{\,T} \vec{d}\) biçiminde değişir; \(\vec{c}^{\,T} \vec{d}\)’nin işareti, bu yönde gidince amacın arttığını mı azaldığını mı söyler.
Simpleks yöntem bölümünde, baza girecek sütunda pozitif eleman yoksa oran testinin yapılamadığını ve problemin sınırsız olduğunu kısaca görmüştük. Aşağıdaki teorem bu durumu yön vektörüyle ifade ediyor ve tablodan gidilecek yönü doğrudan okumayı sağlıyor.
Teorem 7.1 (Sınırsız çözüm teoremi) \(X_0\), \(B_0 = (v_1, \dots, v_m)\) bazına karşılık gelen bir uygun temel çözüm olsun. Baz dışındaki bir \(v_k\) vektörünün sütununda hiç pozitif eleman bulunmasın: her \(i = \overline{1,m}\) için \(y_{ik} \le 0\). \(\vec{d}\) vektörünün bileşenleri \[ d_i = -y_{ik} \ (i = \overline{1,m}), \qquad d_k = 1, \] diğerleri \(0\) olsun. Bu durumda:
- \(\vec{d}\) uygun bölgenin bir yön vektörüdür ve her \(\lambda \ge 0\) için \(X(\lambda) = X_0 + \lambda \vec{d}\) uygun bir çözümdür. Bileşen bileşen \(X(\lambda)\)’da \(x_k = \lambda\), her baz değişkeni \(x_i - \lambda y_{ik}\), diğer değişkenler \(0\)’dır.
- \(X(\lambda)\)’nın amaç değeri \(z_0 - \lambda (z_k - c_k)\)’dır.
- Minimum probleminde \(z_k - c_k > 0\) ise, maksimum probleminde \(z_k - c_k < 0\) ise problemin sınırsız çözümü vardır.
- \(X_0\) dejenere değilse her \(\lambda > 0\) için \(X(\lambda)\)’nın tam \(m + 1\) bileşeni pozitiftir; dolayısıyla \(X(\lambda)\) bir temel çözüm değildir.
İspat
1. \(\vec{d} \ne \vec{0}\)’dır, çünkü \(d_k = 1\). Her \(y_{ik} \le 0\) olduğundan \(d_i = -y_{ik} \ge 0\); yani \(\vec{d} \ge 0\). \(A\vec{d}\), \(A\)’nın sütunlarının \(\vec{d}\)’nin bileşenleriyle ağırlıklı toplamıdır: \[ A\vec{d} = \sum_{i=1}^{m} (-y_{ik})\, v_i + 1 \cdot v_k = v_k - \sum_{i=1}^{m} y_{ik}\, v_i = \vec{0}, \] çünkü \(y_{ik}\) sayıları tam olarak \(v_k = \sum_{i=1}^{m} y_{ik} v_i\) eşitliğini sağlayan katsayılardır. Böylece \(\vec{d}\) bir yön vektörüdür ve Tanım 7.2 altındaki açıklama gereği her \(\lambda \ge 0\) için \(X(\lambda)\) uygundur. \(X_0\)’ın baz dışı bileşenleri \(0\) olduğundan \(X(\lambda)\)’nın bileşenleri iddia edildiği gibidir.
2. \(X(\lambda)\)’da baz dışındaki değişkenlerden yalnız \(x_k = \lambda\) sıfırdan farklıdır. Lemma 7.1 içindeki (2) eşitliğinde toplamdan yalnız \(j = k\) terimi kalır: \(z\big(X(\lambda)\big) = z_0 - \lambda (z_k - c_k)\).
3. Minimum probleminde \(z_k - c_k > 0\) olsun ve \(K\) herhangi bir sayı olsun. \(\lambda > (z_0 - K)/(z_k - c_k)\) ve \(\lambda \ge 0\) seçersek \(\lambda (z_k - c_k) > z_0 - K\), yani \(z\big(X(\lambda)\big) < K\) olur. Amaç fonksiyonu alttan sınırlı değildir. Maksimumda \(z_k - c_k < 0\) ise aynı hesap \(-\lambda (z_k - c_k) = \lambda\, |z_k - c_k|\) terimini istenildiği kadar büyütür; amaç fonksiyonu üstten sınırlı değildir. İki durumda da Tanım 7.1 gereği problemin sınırsız çözümü vardır.
4. \(X_0\) dejenere değilse her \(x_i > 0\)’dır. \(\lambda > 0\) için \(x_i - \lambda y_{ik} \ge x_i > 0\) ve \(x_k = \lambda > 0\); bunlar \(m + 1\) tane pozitif bileşendir, geri kalan bileşenler \(0\)’dır. Bir temel çözümün sıfırdan farklı bileşenleri bir baza ait olduğu için en fazla \(m\) tanedir (Tanım 2.3). Demek ki \(X(\lambda)\) temel çözüm değildir.
\(\blacksquare\)
Yani iyileştiren bir \(v_k\) baza alınmak istendiğinde oran testi “\(x_k\) en fazla ne kadar büyüyebilir?” sorusuna cevap verir. Sütunda pozitif eleman yoksa hiçbir baz değişkeni \(x_k\) büyüdükçe azalmaz, hiçbiri sıfıra düşmez; \(x_k\) sınırsız artırılabilir. Bu sırada amaç değeri, Lemma 7.1 altında söylediğimiz gibi, \(x_k\)’nın her birim artışında \(|z_k - c_k|\) kadar iyileşir. Geometrik olarak \(X_0\) köşesinden uygun bölgenin sınırsız bir kenarı boyunca sonsuza gidilir. \(X_0\) dejenere değilse bu kenar üzerindeki noktalar \(m + 1\) pozitif bileşenli oldukları için köşe değildir; kenarın öbür ucunda bir köşe yoktur, simpleks yöntem de bu yüzden yeni bir tablo kuramaz.
- Baza girecek \(v_k\) vektörünü her zamanki gibi seç: minimumda en büyük pozitif \(z_j - c_j\), maksimumda en negatif \(z_j - c_j\).
- Oran testinden önce \(v_k\) sütununa bak. Hiç pozitif eleman yoksa dur: problemin sınırsız çözümü vardır (Teorem 7.1).
- Sınırsızlığı göstermek için \(x_k = \lambda\) al, baz değişkenlerini \(x_i - \lambda y_{ik}\) olarak, amaç değerini \(z_0 - \lambda (z_k - c_k)\) olarak yaz ve \(\lambda \to \infty\) iken amacın \(+\infty\) ya da \(-\infty\)’a gittiğini göster.
Örnek 7.1 (İki değişkenli bir sınırsız çözüm) \[ \begin{aligned} x_1 - x_2 &\le 2 \\ -2x_1 + x_2 &\le 2 \\ x_1, x_2 &\ge 0 \\ \max z &= 2x_1 + x_2 \end{aligned} \] problemini simpleks yöntemle çözünüz.
Çözüm
Standart form. İki kısıt da \(\le\) biçimindedir ve sağ tarafları negatif değildir. Problemi standart forma (Tanım 1.7) getirmek için \(x_3\) ve \(x_4\) aylak değişkenlerini ekleriz: \[ \begin{aligned} x_1 - x_2 + x_3 &= 2 \\ -2x_1 + x_2 + x_4 &= 2 \\ x_1, x_2, x_3, x_4 &\ge 0 \\ \max z &= 2x_1 + x_2 + 0x_3 + 0x_4 \end{aligned} \] \(v_3\) ve \(v_4\) sütunları \(2 \times 2\) birim matrisi oluşturduğu için bu standart form simpleks yöntem ile çözülebilir haldedir (Tanım 1.9). Başlangıç bazı \(B_0 = (v_3, v_4)\)’tür.
Başlangıç tablosu. Maksimumda en negatif \(z_j - c_j\) baza girer ve bütün \(z_j - c_j \ge 0\) olunca durulur. Kriterler \(z_1 - c_1 = -2\) ve \(z_2 - c_2 = -1\)’dir; \(v_1\) baza girer. \(v_1\) sütununda \(x_4\) satırının elemanı \(-2 < 0\) olduğundan oran yalnız \(x_3\) satırında hesaplanır: \(2/1 = 2\). \(v_3\) bazdan çıkar, pivot \(1\)’dir.
| \(c_j\) | \(2\) | \(1\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(2\) | \([1]\) | \(-1\) | \(1\) | \(0\) | \(\frac{2}{1} \Rightarrow\) |
| \(x_4\) | \(0\) | \(2\) | \(-2\) | \(1\) | \(0\) | \(1\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-2 \Uparrow\) | \(-1\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot \(1\) olduğundan \(x_3\) satırı aynen kalır ve \(x_1\) satırı olur: \((2 \mid 1, -1, 1, 0)\). \(x_4\) satırına bu satırın \(2\) katını, \(z_j - c_j\) satırına da \(2\) katını ekleriz (Bölüm 4.4): \[ \begin{aligned} x_4&: \ (2 + 4 \mid -2 + 2,\ 1 - 2,\ 0 + 2,\ 1) = (6 \mid 0, -1, 2, 1), \\ z_j - c_j&: \ (0 + 4 \mid -2 + 2,\ -1 - 2,\ 0 + 2,\ 0) = (4 \mid 0, -3, 2, 0). \end{aligned} \]
| \(c_j\) | \(2\) | \(1\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_1\) | \(2\) | \(2\) | \(1\) | \(-1\) | \(1\) | \(0\) | \(-\) |
| \(x_4\) | \(0\) | \(6\) | \(0\) | \(-1\) | \(2\) | \(1\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = 4\) | \(0\) | \(-3 \Uparrow\) | \(2\) | \(0\) |
Birinci iterasyon tablosunda (Tablo 7.2) \(X_1 = (2, 0, 0, 6)\) ve \(z = 4\)’tür. Negatif kriter \(z_2 - c_2 = -3\) kaldığı için optimal değiliz ve \(v_2\) baza girmelidir. Ama \(v_2\) sütununun elemanları \(-1\) ve \(-1\)’dir; hiçbiri pozitif değildir ve oran testi yapılamaz. Teorem 7.1 gereği problemin sınırsız çözümü vardır.
Sınırsızlığın gösterilmesi. \(x_2 = \lambda \ge 0\) alalım; \(x_3\) baz dışında \(0\) kalır. Tablonun satırları (Lemma 7.1) \[ x_1 = 2 - (-1)\lambda = 2 + \lambda, \qquad x_4 = 6 - (-1)\lambda = 6 + \lambda \] verir. Kontrol: \((2 + \lambda) - \lambda = 2\) ve \(-2(2 + \lambda) + \lambda + (6 + \lambda) = 2\). Amaç değeri \[ z = 2(2 + \lambda) + \lambda = 4 + 3\lambda \] olur; bu, \(z_0 - \lambda (z_2 - c_2) = 4 - \lambda(-3)\) ile aynıdır. \(\lambda \to \infty\) iken \(z \to +\infty\); maksimum yoktur. Yön vektörü \(\vec{d} = (1, 1, 0, 1)\)’dir: \(x_1\) ile \(x_2\) aynı hızla artarken birinci kısıt hep eşitlikle sağlanır.
Çözümün başındaki şekilde uygun bölge ve bu yarı doğru görülüyor.
\(\blacksquare\)
Şimdi yapay değişken gerektiren bir problemde aynı durumu, iki faz yöntemiyle çözerken görelim.
Örnek 7.2 (İki faz yöntemiyle çözülen sınırsız bir problem) \[ \begin{aligned} -x_1 + x_2 &\le 2 \\ x_1 + 4x_2 &\ge 4 \\ x_1, x_2 &\ge 0 \\ \min z &= -x_1 - 2x_2 \end{aligned} \] problemini iki faz yöntemi ile çözünüz.
Çözüm
Standart form. Birinci kısıta \(x_3\) aylak değişkenini ekler, ikinci kısıttan \(x_4\) artık değişkenini çıkarırız: \[ \begin{aligned} -x_1 + x_2 + x_3 &= 2 \\ x_1 + 4x_2 - x_4 &= 4 \\ x_1, x_2, x_3, x_4 &\ge 0 \\ \min z &= -x_1 - 2x_2 + 0x_3 + 0x_4 \end{aligned} \] Birinci denklemin birim sütunu \(x_3\)’tür, ama ikinci denklemde \(x_4\)’ün katsayısı \(-1\)’dir. Standart form birim matris içermediği için henüz simpleks yöntem ile çözülebilir halde değildir.
Çözülebilir hal. İkinci denkleme \(x_{u_1}\) yapay değişkenini ekleriz (Tanım 1.10): \[ \begin{aligned} -x_1 + x_2 + x_3 + 0x_4 + 0x_{u_1} &= 2 \\ x_1 + 4x_2 + 0x_3 - x_4 + x_{u_1} &= 4 \\ x_1, x_2, x_3, x_4, x_{u_1} &\ge 0 \\ \min z &= -x_1 - 2x_2 + 0(x_3 + x_4) \\ &\quad + Mx_{u_1} \end{aligned} \] \(v_3\) ve \(v_{u_1}\) sütunları birim matrisi oluşturur. İki faz yönteminde \(M\) ile hesap yapmayız: Faz 1’de yapay değişkeni sıfıra indirecek yardımcı problemi, Faz 2’de asıl amaç fonksiyonunu çözeriz (İki faz yöntemi).
Faz 1. Yardımcı problemin amaç fonksiyonu \(\min g = x_{u_1}\)’dir; tablonun en üst satırına bu fonksiyonun katsayıları, en alt satırına \(g_j - c_j\) yazılır. Başlangıç bazı \((v_3, v_{u_1})\), maliyetleri \(0\) ve \(1\)’dir. Kriterler, \(x_{u_1}\) satırının \(1\) katından ilgili \(c_j\) çıkarılarak bulunur: örneğin \(g_2 - c_2 = 0 \cdot 1 + 1 \cdot 4 - 0 = 4\). Minimumda en büyük pozitif kriter girer: \(v_2\). Oranlar \(2/1 = 2\) ve \(4/4 = 1\)’dir; en küçüğü \(x_{u_1}\) satırındadır, \(v_{u_1}\) bazdan çıkar ve pivot \(4\)’tür.
| \(c_j\) | \(0\) | \(0\) | \(0\) | \(0\) | \(1\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_{u_1}\) | Oran |
| \(x_3\) | \(0\) | \(2\) | \(-1\) | \(1\) | \(1\) | \(0\) | \(0\) | \(\frac{2}{1}\) |
| \(x_{u_1}\) | \(1\) | \(4\) | \(1\) | \([4]\) | \(0\) | \(-1\) | \(1\) | \(\frac{4}{4} \Rightarrow\) |
| \(g_j - c_j\) | \(g_0 = 4\) | \(1\) | \(4 \Uparrow\) | \(0\) | \(-1\) | \(0\) |
Pivot satırını \(4\)’e böleriz: \(x_2\) satırı \(\big(1 \mid \tfrac{1}{4}, 1, 0, -\tfrac{1}{4}\big)\) olur. \(x_3\) satırından bu satırı çıkarırız, \(g_j - c_j\) satırından da \(4\) katını: \[ \begin{aligned} x_3&: \ \big(2 - 1 \mid -1 - \tfrac{1}{4},\ 0,\ 1,\ 0 + \tfrac{1}{4}\big) = \big(1 \mid -\tfrac{5}{4}, 0, 1, \tfrac{1}{4}\big), \\[1mm] g_j - c_j&: \ (4 - 4 \mid 1 - 1,\ 0,\ 0,\ -1 + 1) = (0 \mid 0, 0, 0, 0). \end{aligned} \] Yapay değişken bazdan çıktığı için onun sütununu artık yazmıyoruz.
| \(c_j\) | \(0\) | \(0\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_3\) | \(0\) | \(1\) | \(-\frac{5}{4}\) | \(0\) | \(1\) | \(\frac{1}{4}\) |
| \(x_2\) | \(0\) | \(1\) | \(\frac{1}{4}\) | \(1\) | \(0\) | \(-\frac{1}{4}\) |
| \(g_j - c_j\) | \(g_0 = 0\) | \(0\) | \(0\) | \(0\) | \(0\) |
Bütün \(g_j - c_j \le 0\) ve \(\min g = 0\)’dır: yapay değişken sıfıra indi. Elimizde asıl problemin \((x_1, x_2, x_3, x_4) = (0, 1, 1, 0)\) uygun temel çözümü vardır.
Faz 2. Aynı tabloyu asıl amaç katsayılarıyla yeniden yazarız: en üst satır \(-1, -2, 0, 0\); \(c_B\) sütunu \(x_3\) için \(0\), \(x_2\) için \(-2\) olur. Kriterler: \[ \begin{aligned} z_1 - c_1 &= 0 \cdot \big(-\tfrac{5}{4}\big) + (-2) \cdot \tfrac{1}{4} - (-1) = \tfrac{1}{2}, \\[1mm] z_4 - c_4 &= 0 \cdot \tfrac{1}{4} + (-2) \cdot \big(-\tfrac{1}{4}\big) - 0 = \tfrac{1}{2}, \end{aligned} \] \(z_0 = (-2) \cdot 1 = -2\); baz vektörlerinin kriterleri \(0\)’dır.
Minimumda en büyük pozitif kriter girer ve bütün \(z_j - c_j \le 0\) olunca durulur. Burada iki kriter eşittir. Eşitlikte küçük indisli vektörü seçme alışkanlığımız \(v_1\)’i seçtirirdi, ama eşitlikte seçim serbesttir; ikisi de amacı iyileştirir. Önce \(v_4\)’ü seçelim, çözümün sonunda \(v_1\)’i seçmenin de aynı sonuca götürdüğünü göreceğiz. \(v_4\) sütununda yalnız \(x_3\) satırının elemanı pozitiftir; oran \(\frac{1}{1/4} = 4\), \(v_3\) bazdan çıkar ve pivot \(\tfrac{1}{4}\)’tür.
| \(c_j\) | \(-1\) | \(-2\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(1\) | \(-\frac{5}{4}\) | \(0\) | \(1\) | \([\frac{1}{4}]\) | \(\frac{1}{1/4} \Rightarrow\) |
| \(x_2\) | \(-2\) | \(1\) | \(\frac{1}{4}\) | \(1\) | \(0\) | \(-\frac{1}{4}\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = -2\) | \(\frac{1}{2}\) | \(0\) | \(0\) | \(\frac{1}{2} \Uparrow\) |
Pivot satırını \(\tfrac{1}{4}\)’e bölmek \(4\) ile çarpmaktır: \(x_4\) satırı \((4 \mid -5, 0, 4, 1)\) olur. \(x_2\) satırına bu satırın \(\tfrac{1}{4}\) katını ekleriz, \(z_j - c_j\) satırından \(\tfrac{1}{2}\) katını çıkarırız: \[ \begin{aligned} x_2&: \ \big(1 + 1 \mid \tfrac{1}{4} - \tfrac{5}{4},\ 1,\ 0 + 1,\ 0\big) = (2 \mid -1, 1, 1, 0), \\[1mm] z_j - c_j&: \ \big(-2 - 2 \mid \tfrac{1}{2} + \tfrac{5}{2},\ 0,\ 0 - 2,\ 0\big) = (-4 \mid 3, 0, -2, 0). \end{aligned} \]
| \(c_j\) | \(-1\) | \(-2\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_4\) | \(0\) | \(4\) | \(-5\) | \(0\) | \(4\) | \(1\) | \(-\) |
| \(x_2\) | \(-2\) | \(2\) | \(-1\) | \(1\) | \(1\) | \(0\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = -4\) | \(3 \Uparrow\) | \(0\) | \(-2\) | \(0\) |
Sınırsızlık. Birinci iterasyon tablosunda (Tablo 7.6) \(v_1\)’in simpleks kriteri \(3 > 0\)’dır; \(v_1\) baza girebilir. Fakat \(v_1\) sütununun bileşenleri \(-5\) ve \(-1\)’dir, hepsi negatiftir. Oran testi yapılamaz ve Teorem 7.1 gereği problemin sınırsız çözümü vardır.
Bunu açıkça görelim. \(x_1 = \lambda \ge 0\) değeriyle çözüme girer, \(x_3 = 0\) kalır. Kısıtlardan \[ \begin{aligned} -x_1 + x_2 + x_3 = 2 &\ \Longrightarrow\ x_2 = 2 + \lambda, \\ x_1 + 4x_2 - x_4 = 4 &\ \Longrightarrow\ x_4 = 4 + 5\lambda \end{aligned} \] bulunur; bunlar tablonun satırlarının söylediği \(x_2 = 2 - (-1)\lambda\) ve \(x_4 = 4 - (-5)\lambda\) değerleridir. \(\lambda > 0\) için üç değişkeni pozitif olan bir uygun çözüm elde ederiz: \[ X(\lambda) = (\lambda,\ 2 + \lambda,\ 0,\ 4 + 5\lambda), \] \[ z = -\lambda - 2(2 + \lambda) = -4 - 3\lambda . \] \(\lambda > 0\) sayısı istenildiği kadar büyük seçilebildiğinden \(z = -4 - 3\lambda\) istenildiği kadar küçük yapılabilir; amaç fonksiyonu alttan sınırlı değildir. Yön vektörü \(\vec{d} = (1, 1, 0, 5)\)’tir. \(x_3 = 0\) kaldığı için bu yarı doğru \(-x_1 + x_2 = 2\) doğrusu üzerindedir.
Eşitlikte \(v_1\) seçilseydi. Faz 2 başlangıç tablosunda (Tablo 7.5) \(v_1\)’i baza alalım. \(v_1\) sütununda yalnız \(x_2\) satırının elemanı \(\tfrac{1}{4}\) pozitiftir; oran \(\frac{1}{1/4} = 4\), \(v_2\) bazdan çıkar. Pivot satırı \(4\) ile çarpılınca \(x_1\) satırı \((4 \mid 1, 4, 0, -1)\) olur; \(x_3\) satırına bunun \(\tfrac{5}{4}\) katı eklenir, \(z_j - c_j\) satırından \(\tfrac{1}{2}\) katı çıkarılır:
| \(c_j\) | \(-1\) | \(-2\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(6\) | \(0\) | \(5\) | \(1\) | \(-1\) | \(-\) |
| \(x_1\) | \(-1\) | \(4\) | \(1\) | \(4\) | \(0\) | \(-1\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = -4\) | \(0\) | \(-2\) | \(0\) | \(1 \Uparrow\) |
Bu kez \(z_4 - c_4 = 1 > 0\) ile \(v_4\) baza girmek ister, ama sütunu \((-1, -1)\)’dir. Yine sınırsız çözüm vardır: \(x_4 = \lambda\) alınırsa \(x_3 = 6 + \lambda\), \(x_1 = 4 + \lambda\), \(x_2 = 0\) ve \(z = -4 - \lambda\) olur. Bu da uygun bölgenin öbür sınırsız kenarıdır: \((4, 0)\) köşesinden \(x_1\) ekseni boyunca sağa gidilir. Hangi yoldan gidilirse gidilsin problemin minimumu yoktur.
\(\blacksquare\)
7.3 Sınırsız Bölge ile Sınırsız Çözüm Aynı Şey Değildir
Son örnekte uygun bölge sınırsızdı ve amaç fonksiyonu da sınırsızdı. Bu ikisinin arasındaki bağ tek yönlüdür.
Önerme 7.1 (Sınırlı bölgede sınırsız çözüm olmaz) Bir lineer programlama probleminin uygun bölgesi sınırlıysa, yani bütün uygun çözümler için \(0 \le x_j \le K\) (\(j = \overline{1,n}\)) olacak şekilde bir \(K\) sayısı varsa, problemin sınırsız çözümü yoktur. Başka bir deyişle, sınırsız çözümü olan bir problemin uygun bölgesi sınırsızdır.
İspat
Her uygun çözüm için üçgen eşitsizliğiyle \[ |z(\vec{x})| = \Big| \sum_{j=1}^{n} c_j x_j \Big| \le \sum_{j=1}^{n} |c_j|\, x_j \le K \sum_{j=1}^{n} |c_j| \] olur. Amaç fonksiyonu uygun bölgede hem alttan hem üstten \(K \sum_j |c_j|\) ile sınırlıdır; dolayısıyla Tanım 7.1 koşulu sağlanamaz. İkinci cümle birincinin karşıt tersidir.
\(\blacksquare\)
Yani sınırsız çözüm için sınırsız bölge gereklidir, ama yeterli değildir. Bölge sonsuza uzansa bile amaç fonksiyonu o yönde kötüleşiyorsa, bölgenin sınırsızlığı optimumu etkilemez. Aşağıdaki örnekte bir önceki örneğin bölgesini değiştirmeden yalnız amaç fonksiyonunu değiştiriyoruz.
Örnek 7.3 (Sınırsız bölgede sonlu optimum) \[ \begin{aligned} -x_1 + x_2 &\le 2 \\ x_1 + 4x_2 &\ge 4 \\ x_1, x_2 &\ge 0 \\ \min z &= 2x_1 - x_2 \end{aligned} \] problemini iki faz yöntemi ile çözünüz.
Çözüm
Kısıtlar bir önceki örnektekilerle (Örnek 7.2) aynıdır; standart form ve çözülebilir hal de aynıdır. Faz 1 amaç fonksiyonuna hiç bakmaz, bu yüzden Faz 1 tabloları da aynen geçerlidir: Faz 1 optimal tablosunda (Tablo 7.4) baz \((v_3, v_2)\) ve uygun temel çözüm \((0, 1, 1, 0)\)’dır.
Faz 2. Tabloyu yeni amaç katsayılarıyla yazarız: en üst satır \(2, -1, 0, 0\); \(c_B\) sütunu \(x_3\) için \(0\), \(x_2\) için \(-1\). Kriterler: \[ \begin{aligned} z_1 - c_1 &= (-1) \cdot \tfrac{1}{4} - 2 = -\tfrac{9}{4}, \\[1mm] z_4 - c_4 &= (-1) \cdot \big(-\tfrac{1}{4}\big) - 0 = \tfrac{1}{4}, \end{aligned} \] \(z_0 = (-1) \cdot 1 = -1\). Minimumda en büyük pozitif kriter girer; tek pozitif kriter \(\tfrac{1}{4}\) olduğundan \(v_4\) girer. Oran yalnız \(x_3\) satırında hesaplanır: \(\frac{1}{1/4} = 4\); \(v_3\) çıkar, pivot \(\tfrac{1}{4}\)’tür.
| \(c_j\) | \(2\) | \(-1\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(1\) | \(-\frac{5}{4}\) | \(0\) | \(1\) | \([\frac{1}{4}]\) | \(\frac{1}{1/4} \Rightarrow\) |
| \(x_2\) | \(-1\) | \(1\) | \(\frac{1}{4}\) | \(1\) | \(0\) | \(-\frac{1}{4}\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = -1\) | \(-\frac{9}{4}\) | \(0\) | \(0\) | \(\frac{1}{4} \Uparrow\) |
Tablonun gövdesi bir önceki örnektekiyle aynı biçimde dönüşür: \(x_4\) satırı \((4 \mid -5, 0, 4, 1)\), \(x_2\) satırı \((2 \mid -1, 1, 1, 0)\) olur. \(z_j - c_j\) satırından yeni \(x_4\) satırının \(\tfrac{1}{4}\) katını çıkarırız: \[ \big(-1 - 1 \mid -\tfrac{9}{4} + \tfrac{5}{4},\ 0,\ 0 - 1,\ 0\big) = (-2 \mid -1, 0, -1, 0). \]
| \(c_j\) | \(2\) | \(-1\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_4\) | \(0\) | \(4\) | \(-5\) | \(0\) | \(4\) | \(1\) |
| \(x_2\) | \(-1\) | \(2\) | \(-1\) | \(1\) | \(1\) | \(0\) |
| \(z_j - c_j\) | \(z_0 = -2\) | \(-1\) | \(0\) | \(-1\) | \(0\) |
Bütün \(z_j - c_j \le 0\); tablo optimaldir. Optimal çözüm \(x_1 = 0\), \(x_2 = 2\) ve \(\min z = -2\)’dir.
Bu tablonun gövdesi, sınırsız çözümlü örneğin birinci iterasyon tablosunun (Tablo 7.6) gövdesinin aynısıdır. \(v_1\) sütunu yine \((-5, -1)\)’dir, yani Teorem 7.1 içindeki \(\vec{d} = (1, 1, 0, 5)\) yine bir yön vektörüdür ve bölge yine sınırsızdır. Fark en alt satırdadır: \(z_1 - c_1 = -1 < 0\). Bu yönde gidersek amaç değeri \(z_0 - \lambda (z_1 - c_1) = -2 + \lambda\) olur, yani artar. Minimum probleminde bu yön işimize yaramaz. Sınırsız çözüm için “sütunda pozitif eleman yok” koşulu tek başına yetmez; o sütunun kriteri de iyileştiren yönde olmalıdır.
Grafik bunu doğrular. Köşeler \((0, 1)\), \((0, 2)\) ve \((4, 0)\)’dır; bunlarda \(z\) sırasıyla \(-1\), \(-2\) ve \(8\)’dir. Bölgenin sınırsız iki kenarı boyunca, \((0, 2)\)’den \((1, 1)\) yönünde ve \((4, 0)\)’dan \((1, 0)\) yönünde, \(z\) sırasıyla \(1\) ve \(2\) hızıyla artar.
\(\blacksquare\)
7.4 Alternatif Optimal Çözüm
Şimdi ikinci durumu, optimal tabloda baz dışındaki bir vektörün simpleks kriterinin sıfır olduğu durumu ele alalım.
Tanım 7.3 (Alternatif optimal çözüm) Bir lineer programlama probleminin birden fazla optimal çözümü varsa, bulunan bir optimal çözümden farklı her optimal çözüme bir alternatif optimal çözüm denir.
Yani alternatif optimal çözümler aynı optimal değeri veren farklı çözümlerdir. Karar verici açısından bu iyi bir haberdir: amacı feda etmeden, modelde yer almayan başka ölçütlere (kolaylık, güvenlik, alışkanlık) göre bir seçim yapma serbestliği vardır.
Optimal tablodaki simpleks kriterleri, Lemma 7.1 içindeki (2) eşitliği sayesinde, optimal çözümün tek olup olmadığını söyler.
Teorem 7.2 (Alternatif optimal çözüm teoremi) Bir minimum probleminin tablosunda bütün \(z_j - c_j \le 0\) (maksimum probleminde bütün \(z_j - c_j \ge 0\)) olsun; yani tablo optimal olsun. Baz dışındaki bir \(v_k\) vektörü için \(z_k - c_k = 0\) olsun ve \(v_k\) sütununda en az bir pozitif eleman bulunsun. \(v_k\) baza alınır ve bazdan çıkacak vektör oran testiyle seçilirse:
- yeni tablonun \(z_j - c_j\) satırı eskisinin aynısıdır, dolayısıyla yeni tablo da optimaldir;
- yeni uygun temel çözümün amaç değeri eskisine eşittir;
- oran testinin verdiği \(\lambda\) pozitifse (özellikle \(X_0\) dejenere değilse) yeni çözüm eskisinden farklıdır; yani problemin alternatif optimal çözümü vardır.
İspat
Optimallik. Önce, bütün kriterleri \(\le 0\) olan bir tablonun gerçekten optimal olduğunu Lemma 7.1 ile görelim. Her uygun \(\vec{u}\) için \(u_j \ge 0\) ve \(z_j - c_j \le 0\) olduğundan (2) eşitliğindeki toplam \(\le 0\)’dır, yani \(z(\vec{u}) \ge z_0\). Maksimumda eşitsizlikler döner ve \(z(\vec{u}) \le z_0\) olur.
1 ve 2. Pivot \(y_{rk}\) olsun. Tablonun dönüşüm kuralına (Bölüm 4.4) göre yeni kriterler ve yeni amaç değeri \[ \begin{aligned} (z_j - c_j)' &= (z_j - c_j) - \frac{(z_k - c_k)\, y_{rj}}{y_{rk}}, \\[1mm] z_0' &= z_0 - \frac{(z_k - c_k)\, y_{r0}}{y_{rk}} \end{aligned} \] olur. \(z_k - c_k = 0\) olduğundan çıkarılan terimler sıfırdır: \((z_j - c_j)' = z_j - c_j\) ve \(z_0' = z_0\). Kriter satırı değişmediği için bütün kriterler yine \(\le 0\) (maksimumda \(\ge 0\)) kalır ve yukarıdaki gözlem gereği yeni çözüm de optimaldir.
3. Eski çözümde \(x_k\) baz dışında olduğundan \(x_k = 0\)’dır. Yeni çözümde \(x_k = \lambda = y_{r0}/y_{rk}\)’dır. \(\lambda > 0\) ise iki çözümün \(k\). bileşenleri farklıdır. \(X_0\) dejenere değilse \(y_{r0} = x_r > 0\) ve \(y_{rk} > 0\) olduğundan \(\lambda > 0\)’dır.
\(\blacksquare\)
Yani optimal tabloda sıfır kriterli bir baz dışı vektör, “bu vektörü baza alırsan amaç değeri ne iyileşir ne kötüleşir” demektir. Onu baza almak bizi aynı amaç değerli yeni bir optimal uç noktaya götürür. Yeni tabloda bu kez bazdan çıkan \(v_r\)’nin kriteri sıfırdır, çünkü eski tabloda \(v_r\) baz vektörüydü ve kriter satırı değişmedi. \(X_0\) dejenere değilse, \(v_r\) yeniden baza alındığında oran testi \(v_k\)’yı çıkarır ve ilk optimal uç noktaya geri dönülür.
Tersine, baz dışındaki bütün kriterler sıfırdan farklıysa başka optimal çözüm aranmaz.
Sonuç 7.1 (Optimal çözümün tekliği) Bir minimum probleminin optimal tablosunda baz dışındaki bütün vektörler için \(z_j - c_j < 0\) ise (maksimum probleminde \(z_j - c_j > 0\) ise) optimal çözüm tektir.
İspat
Minimum durumunu ele alalım. \(\vec{u}\) optimal bir çözüm olsun: \(z(\vec{u}) = z_0\). Lemma 7.1 içindeki (2) eşitliğinden \[ \sum_{j=m+1}^{n} (z_j - c_j)\, u_j = 0 \] çıkar. Toplamın her terimi \(\le 0\)’dır, çünkü \(z_j - c_j < 0\) ve \(u_j \ge 0\). Terimleri pozitif olmayan bir toplam ancak her terimi sıfırsa sıfırdır; \(z_j - c_j \ne 0\) olduğundan baz dışındaki her \(j\) için \(u_j = 0\) olur. Bu durumda (1) eşitliği \(u_i = x_i\) verir. Demek ki \(\vec{u} = X_0\)’dır. Maksimum durumu aynı biçimde ispatlanır.
\(\blacksquare\)
İki optimal çözüm bulduktan sonra aralarında kalan her noktanın da optimal olduğunu görelim. Hatırlatalım: \(X^{(1)}, \dots, X^{(p)}\) noktalarının bir konveks kombinasyonu, \(t_i \ge 0\) ve \(t_1 + \dots + t_p = 1\) olmak üzere \(t_1 X^{(1)} + \dots + t_p X^{(p)}\) biçimindeki bir noktadır (bkz. Temel çözümler ve konveks kümeler). İki nokta için bunlar \(0 \le t \le 1\) olmak üzere \(t X^{(1)} + (1 - t) X^{(2)}\) noktalarıdır, yani iki noktayı birleştiren doğru parçası.
Önerme 7.2 (Optimal çözümlerin konveks kombinasyonları) \(X^{(1)}, \dots, X^{(p)}\) bir lineer programlama probleminin optimal çözümleri, \(z^*\) optimal değer olsun. \(t_1, \dots, t_p \ge 0\) ve \(t_1 + \dots + t_p = 1\) ise \[ X = t_1 X^{(1)} + t_2 X^{(2)} + \dots + t_p X^{(p)} \] de bir optimal çözümdür. Özel olarak iki farklı optimal çözüm varsa sonsuz çok optimal çözüm vardır.
İspat
\(X\) uygundur. Her \(X^{(i)}\) uygun olduğundan \(AX^{(i)} = \vec{b}\) ve \(X^{(i)} \ge 0\)’dır. Buna göre \[ AX = \sum_{i=1}^{p} t_i\, AX^{(i)} = \Big( \sum_{i=1}^{p} t_i \Big) \vec{b} = \vec{b} \] olur. Negatif olmayan sayıların negatif olmayan katsayılarla toplamı da negatif değildir: \(X \ge 0\).
\(X\) optimaldir. Amaç fonksiyonu lineer olduğundan \[ z(X) = \sum_{i=1}^{p} t_i\, z(X^{(i)}) = \Big( \sum_{i=1}^{p} t_i \Big) z^* = z^* . \] Uygun bir çözüm optimal değeri veriyorsa optimaldir.
Sonsuz çok çözüm. \(X^{(1)} \ne X^{(2)}\) ise \(X(t) = t X^{(1)} + (1 - t) X^{(2)}\) noktaları, \(0 \le t \le 1\) için, yukarıdakine göre optimaldir. \(t \ne s\) ise \[ X(t) - X(s) = (t - s)\big(X^{(1)} - X^{(2)}\big) \ne \vec{0}; \] farklı \(t\) değerleri farklı çözümler verir.
\(\blacksquare\)
Yani optimal çözümler kümesi konvekstir. Simpleks yöntemle \(X^{(1)}, \dots, X^{(p)}\) optimal uç noktaları bulununca, bunların bütün konveks kombinasyonlarını tek bir formülde toplayan \[ X = \sum_{i=1}^{p} t_i X^{(i)}, \qquad t_i \ge 0, \quad \sum_{i=1}^{p} t_i = 1 \] ifadesine problemin genel optimal çözümü denir. Uygulamada en sık karşılaşılan durum iki optimal uç noktadır; o zaman genel optimal çözüm \(X = t X^{*} + (1 - t) X^{**}\), \(0 \le t \le 1\) olur. Önerme bu noktaların optimal olduğunu söyler; optimal çözümlerin bunlardan ibaret olup olmadığını ise ayrıca kontrol etmek gerekir. Optimal çözümler kümesi sınırsız olabilir (Bölüm 7.5), o zaman hiçbir sonlu konveks kombinasyon onu tüketmez. Aşağıdaki örneklerde bu kontrolü Lemma 7.1 içindeki (2) eşitliğiyle yapacağız.
- Simpleks yöntemle optimal tabloya ulaş (minimumda bütün \(z_j - c_j \le 0\), maksimumda bütün \(z_j - c_j \ge 0\)).
- Baz dışındaki vektörlerin kriterlerine bak. Hiçbiri sıfır değilse optimal çözüm tektir (Sonuç 7.1).
- Kriteri sıfır olan baz dışı bir \(v_k\) varsa sütununa bak. Pozitif eleman varsa \(v_k\)’yı baza al, bazdan çıkacak vektörü oran testiyle seç ve pivot yap; yeni tablo aynı amaç değerli bir optimal uç nokta verir (Teorem 7.2). Pozitif eleman yoksa optimal çözümler sınırsız bir ışın boyunca uzanır (Önerme 7.3).
- Bulunan optimal uç noktaların konveks kombinasyonunu yazarak genel optimal çözümü ver (Önerme 7.2).
Örnek 7.4 (İki değişkenli bir alternatif optimal çözüm) \[ \begin{aligned} x_1 + 2x_2 &\le 8 \\ 3x_1 + 2x_2 &\le 12 \\ x_1, x_2 &\ge 0 \\ \max z &= x_1 + 2x_2 \end{aligned} \] problemini simpleks yöntemle çözünüz ve varsa alternatif optimal çözümleri bulunuz.
Çözüm
Standart form. İki \(\le\) kısıtına \(x_3\) ve \(x_4\) aylak değişkenlerini ekleriz: \[ \begin{aligned} x_1 + 2x_2 + x_3 &= 8 \\ 3x_1 + 2x_2 + x_4 &= 12 \\ x_1, x_2, x_3, x_4 &\ge 0 \\ \max z &= x_1 + 2x_2 + 0x_3 + 0x_4 \end{aligned} \] \(v_3\) ve \(v_4\) birim matrisi oluşturur; problem simpleks yöntem ile çözülebilir haldedir.
Başlangıç tablosu. Maksimumda en negatif kriter girer: \(z_1 - c_1 = -1\), \(z_2 - c_2 = -2\); \(v_2\) girer. Oranlar \(8/2 = 4\) ve \(12/2 = 6\); en küçüğü \(x_3\) satırındadır, \(v_3\) çıkar, pivot \(2\)’dir.
| \(c_j\) | \(1\) | \(2\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(8\) | \(1\) | \([2]\) | \(1\) | \(0\) | \(\frac{8}{2} \Rightarrow\) |
| \(x_4\) | \(0\) | \(12\) | \(3\) | \(2\) | \(0\) | \(1\) | \(\frac{12}{2}\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-1\) | \(-2 \Uparrow\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot satırını \(2\)’ye böleriz: \(x_2\) satırı \(\big(4 \mid \tfrac{1}{2}, 1, \tfrac{1}{2}, 0\big)\). \(x_4\) satırından bunun \(2\) katını çıkarır, \(z_j - c_j\) satırına \(2\) katını ekleriz: \[ \begin{aligned} x_4&: \ \big(12 - 8 \mid 3 - 1,\ 0,\ 0 - 1,\ 1\big) = (4 \mid 2, 0, -1, 1), \\[1mm] z_j - c_j&: \ \big(0 + 8 \mid -1 + 1,\ 0,\ 0 + 1,\ 0\big) = (8 \mid 0, 0, 1, 0). \end{aligned} \]
| \(c_j\) | \(1\) | \(2\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_2\) | \(2\) | \(4\) | \(\frac{1}{2}\) | \(1\) | \(\frac{1}{2}\) | \(0\) | \(\frac{4}{1/2}\) |
| \(x_4\) | \(0\) | \(4\) | \([2]\) | \(0\) | \(-1\) | \(1\) | \(\frac{4}{2} \Rightarrow\) |
| \(z_j - c_j\) | \(z_0 = 8\) | \(0 \Uparrow\) | \(0\) | \(1\) | \(0\) |
Bütün \(z_j - c_j \ge 0\); tablo optimaldir. Optimal çözüm \(X^{*} = (0, 4, 0, 4)\), yani \(x_1 = 0\), \(x_2 = 4\) ve \(\max z = 8\)’dir.
Alternatif çözüm. Baz dışındaki \(v_1\)’in kriteri \(z_1 - c_1 = 0\)’dır ve sütununda pozitif elemanlar vardır. Teorem 7.2 gereği \(v_1\)’i baza almak yeni bir optimal çözüm verir. Oranlar \(\frac{4}{1/2} = 8\) ve \(\frac{4}{2} = 2\); \(v_4\) çıkar, pivot \(2\)’dir. Pivot satırını \(2\)’ye böleriz: \(x_1\) satırı \(\big(2 \mid 1, 0, -\tfrac{1}{2}, \tfrac{1}{2}\big)\). \(x_2\) satırından bunun \(\tfrac{1}{2}\) katını çıkarırız: \[ \big(4 - 1 \mid 0,\ 1,\ \tfrac{1}{2} + \tfrac{1}{4},\ 0 - \tfrac{1}{4}\big) = \big(3 \mid 0, 1, \tfrac{3}{4}, -\tfrac{1}{4}\big). \] \(z_j - c_j\) satırının pivot sütunundaki elemanı \(0\) olduğundan bu satır değişmez.
| \(c_j\) | \(1\) | \(2\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_2\) | \(2\) | \(3\) | \(0\) | \(1\) | \(\frac{3}{4}\) | \(-\frac{1}{4}\) |
| \(x_1\) | \(1\) | \(2\) | \(1\) | \(0\) | \(-\frac{1}{2}\) | \(\frac{1}{2}\) |
| \(z_j - c_j\) | \(z_0 = 8\) | \(0\) | \(0\) | \(1\) | \(0\) |
Alternatif optimal çözüm \(X^{**} = (2, 3, 0, 0)\), yani \(x_1 = 2\), \(x_2 = 3\); amaç değeri \(2 + 2 \cdot 3 = 8\). Bu tabloda bu kez baz dışındaki \(v_4\)’ün kriteri sıfırdır; onu baza almak (oran \(\frac{2}{1/2} = 4\), \(v_1\) çıkar) bizi \(X^{*}\)’a geri götürür.
Genel optimal çözüm. Önerme 7.2 gereği \(0 \le t \le 1\) için \[ X = t\,(0, 4) + (1 - t)(2, 3) = (2 - 2t,\ 3 + t) \] noktalarının hepsi optimaldir: \(z = (2 - 2t) + 2(3 + t) = 8\). Bu formül bütün optimal çözümleri verir. Gerçekten, optimal tabloda (Tablo 7.11) Lemma 7.1 içindeki (2) eşitliği \(z = 8 - 0 \cdot x_1 - 1 \cdot x_3 = 8 - x_3\) verir; bir uygun çözüm ancak \(x_3 = 0\) ise, yani \(x_1 + 2x_2 = 8\) doğrusu üzerindeyse optimaldir. Bu doğrunun uygun bölgede kalan parçası tam olarak \(X^{*}\) ile \(X^{**}\) arasındaki kenardır.
Geometrik olarak amaç fonksiyonunun seviye doğruları \(x_1 + 2x_2 = \text{sabit}\), birinci kısıtın doğrusuna paraleldir. Seviye doğrusu \(z\) artırılarak kaydırıldığında bölgeyi bir köşede değil, bütün bir kenar boyunca terk eder.
\(\blacksquare\)
Örnek 7.5 (Üç değişkenli bir alternatif optimal çözüm) \[ \begin{aligned} x_1 + 2x_2 + x_3 &\le 1 \\ -4x_1 - 2x_2 + 3x_3 &\le 2 \\ x_1, x_2, x_3 &\ge 0 \\ \min z &= 14x_1 + 4x_2 - 14x_3 \end{aligned} \] lineer programlama problemini çözünüz ve varsa alternatif optimal çözümü bulunuz.
Çözüm
Standart form ve çözülebilir hal. Önce problemi simpleks yöntem ile çözülebilir hale getirelim. İki kısıt da \(\le\) biçiminde ve sağ tarafları negatif olmadığından \(x_4\) ve \(x_5\) aylak değişkenlerini eklemek yeter: \[ \begin{aligned} x_1 + 2x_2 + x_3 + x_4 + 0x_5 &= 1 \\ -4x_1 - 2x_2 + 3x_3 + 0x_4 + x_5 &= 2 \\ x_1, x_2, x_3, x_4, x_5 &\ge 0 \\ \min z &= 14x_1 + 4x_2 - 14x_3 \\ &\quad + 0(x_4 + x_5) \end{aligned} \] \(v_4\) ve \(v_5\) birim matrisi oluşturur; başlangıç bazı \((v_4, v_5)\)’tir.
Başlangıç tablosu. \(\vec{c}_B = \vec{0}\) olduğundan \(z_j - c_j = -c_j\): kriterler \(-14\), \(-4\), \(14\), \(0\), \(0\). Minimumda en büyük pozitif kriter girer ve bütün \(z_j - c_j \le 0\) olunca durulur; tek pozitif kriter \(14\) olduğundan \(v_3\) girer. Oranlar \(1/1 = 1\) ve \(2/3\); en küçüğü \(x_5\) satırındadır, \(v_5\) çıkar, pivot \(3\)’tür.
| \(c_j\) | \(14\) | \(4\) | \(-14\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | Oran |
| \(x_4\) | \(0\) | \(1\) | \(1\) | \(2\) | \(1\) | \(1\) | \(0\) | \(\frac{1}{1}\) |
| \(x_5\) | \(0\) | \(2\) | \(-4\) | \(-2\) | \([3]\) | \(0\) | \(1\) | \(\frac{2}{3} \Rightarrow\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-14\) | \(-4\) | \(14 \Uparrow\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot satırını \(3\)’e böleriz: \(x_3\) satırı \(\big(\tfrac{2}{3} \mid -\tfrac{4}{3}, -\tfrac{2}{3}, 1, 0, \tfrac{1}{3}\big)\). \(x_4\) satırından bu satırı çıkarırız, \(z_j - c_j\) satırından da \(14\) katını: \[ \begin{aligned} x_4&: \ \big(1 - \tfrac{2}{3} \mid 1 + \tfrac{4}{3},\ 2 + \tfrac{2}{3},\ 0,\ 1,\ -\tfrac{1}{3}\big) \\[1mm] &\quad = \big(\tfrac{1}{3} \mid \tfrac{7}{3}, \tfrac{8}{3}, 0, 1, -\tfrac{1}{3}\big), \\[1mm] z_j - c_j&: \ \big(0 - \tfrac{28}{3} \mid -14 + \tfrac{56}{3},\ -4 + \tfrac{28}{3},\ 0,\ 0,\ -\tfrac{14}{3}\big) \\[1mm] &\quad = \big(-\tfrac{28}{3} \mid \tfrac{14}{3}, \tfrac{16}{3}, 0, 0, -\tfrac{14}{3}\big). \end{aligned} \] En büyük pozitif kriter \(\tfrac{16}{3}\) olduğundan \(v_2\) girer. \(v_2\) sütununda yalnız \(x_4\) satırının elemanı pozitiftir; oran \(\frac{1/3}{8/3} = \frac{1}{8}\), \(v_4\) çıkar, pivot \(\tfrac{8}{3}\)’tür.
| \(c_j\) | \(14\) | \(4\) | \(-14\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | Oran |
| \(x_4\) | \(0\) | \(\frac{1}{3}\) | \(\frac{7}{3}\) | \([\frac{8}{3}]\) | \(0\) | \(1\) | \(-\frac{1}{3}\) | \(\frac{1}{8} \Rightarrow\) |
| \(x_3\) | \(-14\) | \(\frac{2}{3}\) | \(-\frac{4}{3}\) | \(-\frac{2}{3}\) | \(1\) | \(0\) | \(\frac{1}{3}\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = -\frac{28}{3}\) | \(\frac{14}{3}\) | \(\frac{16}{3} \Uparrow\) | \(0\) | \(0\) | \(-\frac{14}{3}\) |
İkinci iterasyon. Pivot satırını \(\tfrac{8}{3}\)’e bölmek \(\tfrac{3}{8}\) ile çarpmaktır: \(x_2\) satırı \(\big(\tfrac{1}{8} \mid \tfrac{7}{8}, 1, 0, \tfrac{3}{8}, -\tfrac{1}{8}\big)\). \(x_3\) satırına bunun \(\tfrac{2}{3}\) katını ekleriz, \(z_j - c_j\) satırından \(\tfrac{16}{3}\) katını çıkarırız: \[ \begin{aligned} x_3&: \ \big(\tfrac{2}{3} + \tfrac{1}{12} \mid -\tfrac{4}{3} + \tfrac{7}{12},\ 0,\ 1,\ \tfrac{1}{4},\ \tfrac{1}{3} - \tfrac{1}{12}\big) \\[1mm] &\quad = \big(\tfrac{3}{4} \mid -\tfrac{3}{4}, 0, 1, \tfrac{1}{4}, \tfrac{1}{4}\big), \\[1mm] z_j - c_j&: \ \big(-\tfrac{28}{3} - \tfrac{2}{3} \mid \tfrac{14}{3} - \tfrac{14}{3},\ 0,\ 0,\ -2,\ -\tfrac{14}{3} + \tfrac{2}{3}\big) \\[1mm] &\quad = (-10 \mid 0, 0, 0, -2, -4). \end{aligned} \]
| \(c_j\) | \(14\) | \(4\) | \(-14\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | Oran |
| \(x_2\) | \(4\) | \(\frac{1}{8}\) | \([\frac{7}{8}]\) | \(1\) | \(0\) | \(\frac{3}{8}\) | \(-\frac{1}{8}\) | \(\frac{1/8}{7/8} \Rightarrow\) |
| \(x_3\) | \(-14\) | \(\frac{3}{4}\) | \(-\frac{3}{4}\) | \(0\) | \(1\) | \(\frac{1}{4}\) | \(\frac{1}{4}\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = -10\) | \(0 \Uparrow\) | \(0\) | \(0\) | \(-2\) | \(-4\) |
Simpleks kriterleri arasında pozitif olan kalmadığından optimal çözüme ulaşılmıştır: \[ X^{*} = \big(0,\ \tfrac{1}{8},\ \tfrac{3}{4},\ 0,\ 0\big), \qquad z^{*} = -10 . \] Kontrol: \[ 14 \cdot 0 + 4 \cdot \tfrac{1}{8} - 14 \cdot \tfrac{3}{4} = \tfrac{1}{2} - \tfrac{21}{2} = -10 . \]
Alternatif çözüm. İkinci iterasyon tablosunda (Tablo 7.15) baz dışındaki \(x_1\) değişkeninin simpleks kriteri \(0\)’dır ve \(v_1\) sütununda pozitif bir eleman (\(\tfrac{7}{8}\)) vardır. Teorem 7.2 gereği \(v_1\) vektörünü baza alırsak, yani \(x_1\)’i temel değişken yaparsak yeni bir optimal çözüme geçeriz. Oran yalnız \(x_2\) satırında hesaplanır: \(\frac{1/8}{7/8} = \frac{1}{7}\); \(v_2\) çıkar, pivot \(\tfrac{7}{8}\)’dir.
Pivot satırını \(\tfrac{8}{7}\) ile çarparız: \(x_1\) satırı \(\big(\tfrac{1}{7} \mid 1, \tfrac{8}{7}, 0, \tfrac{3}{7}, -\tfrac{1}{7}\big)\). \(x_3\) satırına bunun \(\tfrac{3}{4}\) katını ekleriz: \[ \begin{aligned} x_3&: \ \big(\tfrac{3}{4} + \tfrac{3}{28} \mid 0,\ \tfrac{6}{7},\ 1,\ \tfrac{1}{4} + \tfrac{9}{28},\ \tfrac{1}{4} - \tfrac{3}{28}\big) \\[1mm] &\quad = \big(\tfrac{6}{7} \mid 0, \tfrac{6}{7}, 1, \tfrac{4}{7}, \tfrac{1}{7}\big). \end{aligned} \] \(z_j - c_j\) satırı değişmez, çünkü pivot sütunundaki elemanı \(0\)’dır.
| \(c_j\) | \(14\) | \(4\) | \(-14\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) |
| \(x_1\) | \(14\) | \(\frac{1}{7}\) | \(1\) | \(\frac{8}{7}\) | \(0\) | \(\frac{3}{7}\) | \(-\frac{1}{7}\) |
| \(x_3\) | \(-14\) | \(\frac{6}{7}\) | \(0\) | \(\frac{6}{7}\) | \(1\) | \(\frac{4}{7}\) | \(\frac{1}{7}\) |
| \(z_j - c_j\) | \(z_0 = -10\) | \(0\) | \(0\) | \(0\) | \(-2\) | \(-4\) |
Yeni optimal çözüm \[ X^{**} = \big(\tfrac{1}{7},\ 0,\ \tfrac{6}{7},\ 0,\ 0\big), \qquad z^{**} = -10 \] olarak bulunur. Kontrol: \(14 \cdot \tfrac{1}{7} - 14 \cdot \tfrac{6}{7} = 2 - 12 = -10\). Buradaki \(X^{**}\) çözümüne alternatif optimal çözüm denir.
Genel optimal çözüm. Önerme 7.2 gereği \(X^{*}\) ve \(X^{**}\) optimal çözümlerinin konveks kombinasyonlarının her biri de amaç fonksiyonunu minimum yapar. \(0 \le t \le 1\) olmak üzere \[ \begin{aligned} X &= t X^{*} + (1 - t) X^{**} \\[1mm] &= t \big(0, \tfrac{1}{8}, \tfrac{3}{4}, 0, 0\big) + (1 - t) \big(\tfrac{1}{7}, 0, \tfrac{6}{7}, 0, 0\big) \\[1mm] &= \Big(\frac{1 - t}{7},\ \frac{t}{8},\ \frac{24 - 3t}{28},\ 0,\ 0\Big). \end{aligned} \] Üçüncü bileşen \(\tfrac{3t}{4} + \tfrac{6(1 - t)}{7} = \tfrac{21t + 24 - 24t}{28}\) hesabından gelir. Bu çözümlerin her birinde amaç fonksiyonu aynı değeri alır: \[ \begin{aligned} \min z &= 14 \cdot \frac{1 - t}{7} + 4 \cdot \frac{t}{8} - 14 \cdot \frac{24 - 3t}{28} \\[1mm] &= (2 - 2t) + \frac{t}{2} - \Big(12 - \frac{3t}{2}\Big) = -10 . \end{aligned} \]
Bu formül bütün optimal çözümleri verir. Optimal tabloda (Tablo 7.15) Lemma 7.1 içindeki (2) eşitliği \[ z = -10 - 0 \cdot x_1 - (-2)\, x_4 - (-4)\, x_5 = -10 + 2x_4 + 4x_5 \] verir. Demek ki bir uygun çözüm ancak \(x_4 = x_5 = 0\) ise optimaldir. O zaman (1) eşitlikleri \(x_2 = \tfrac{1}{8} - \tfrac{7}{8} x_1\) ve \(x_3 = \tfrac{3}{4} + \tfrac{3}{4} x_1\) verir; \(x_2 \ge 0\) koşulu \(0 \le x_1 \le \tfrac{1}{7}\) demektir. \(x_1 = \tfrac{1 - t}{7}\) yazınca tam olarak yukarıdaki \(X\) çıkar.
Uygun bölge \(\mathbb{R}^3\)’te altı köşeli bir çokyüzlüdür. Simpleks \(O\) köşesinden \(C = (0, 0, \tfrac{2}{3})\) köşesine (birinci iterasyon), oradan \(X^{*}\)’a (ikinci iterasyon) gitmiştir. Amaç fonksiyonunun \(14x_1 + 4x_2 - 14x_3 = -10\) seviye düzlemi bölgeye \(X^{*} X^{**}\) kenarı boyunca değer.
\(\blacksquare\)
7.5 Optimal Çözümlerin Sınırsız Olduğu Durum
Alternatif optimal çözüm teoreminde (Teorem 7.2) sıfır kriterli sütunda pozitif bir eleman olduğunu varsaydık. Pozitif eleman yoksa pivot yapılamaz; ama bu durumda alternatif optimal çözümler yine vardır, üstelik sonsuza uzanırlar.
Önerme 7.3 (Optimal ışın) Bir problemin optimal tablosunda baz dışındaki bir \(v_k\) için \(z_k - c_k = 0\) olsun ve \(v_k\) sütununda hiç pozitif eleman bulunmasın: her \(i\) için \(y_{ik} \le 0\). Bu durumda her \(\lambda \ge 0\) için \(x_k = \lambda\), her baz değişkeni \(x_i - \lambda y_{ik}\) (\(i = \overline{1,m}\)) ve diğer değişkenler \(0\) olan \(X(\lambda)\) çözümü optimaldir. Optimal değer \(z_0\) sonludur, ama optimal çözümler kümesi sınırsızdır.
İspat
\(v_k\) sütununda pozitif eleman olmadığı için Teorem 7.1 içindeki \(\vec{d}\) vektörü bir yön vektörüdür ve her \(\lambda \ge 0\) için \(X(\lambda) = X_0 + \lambda \vec{d}\) uygundur. Aynı teoremin 2. maddesine göre amaç değeri \[ z\big(X(\lambda)\big) = z_0 - \lambda (z_k - c_k) = z_0 - \lambda \cdot 0 = z_0 \] olur. Tablo optimal olduğundan \(z_0\) optimal değerdir; demek ki her \(X(\lambda)\) optimaldir. \(X(\lambda)\)’nın \(k\). bileşeni \(\lambda\) olduğundan bu çözümler \(\lambda\) büyüdükçe sınırsız büyür; optimal çözümler kümesi sınırlı değildir.
\(\blacksquare\)
Yani optimalde temel olmayan bir değişkenin simpleks kriteri sıfırsa ve bu değişkene ait sütunda pozitif eleman yoksa, optimal çözümler sınırsızdır: \(X_0\) köşesinden başlayan bir ışının bütün noktaları optimaldir. Burada sınırsız olan amaç fonksiyonu değildir; optimal değer sonlu bir sayıdır ve bu yüzden bu durum sınırsız çözümden (Tanım 7.1) farklıdır. \(v_k\) pivot yapılamadığı için yeni bir optimal uç nokta vermez, ama sonsuz çok alternatif optimal çözüm vardır. Baz dışında sıfır kriterli başka bir sütun yoksa, (2) eşitliği gereği optimal çözümler kümesi tam olarak bu ışındır.
Örnek 7.6 (Optimal çözümleri bir ışın oluşturan problem) \[ \begin{aligned} x_1 - x_2 &\le 1 \\ -x_1 + x_2 &\le 2 \\ x_1, x_2 &\ge 0 \\ \max z &= x_1 - x_2 \end{aligned} \] problemini simpleks yöntemle çözünüz ve bütün optimal çözümleri bulunuz.
Çözüm
Standart form. \(x_3\) ve \(x_4\) aylak değişkenleriyle \[ \begin{aligned} x_1 - x_2 + x_3 &= 1 \\ -x_1 + x_2 + x_4 &= 2 \\ x_1, x_2, x_3, x_4 &\ge 0 \\ \max z &= x_1 - x_2 + 0x_3 + 0x_4 \end{aligned} \] olur; \(v_3\) ve \(v_4\) birim matrisi oluşturur ve problem simpleks yöntem ile çözülebilir haldedir.
Başlangıç tablosu. Maksimumda en negatif kriter girer: \(z_1 - c_1 = -1\), \(z_2 - c_2 = 1\); \(v_1\) girer. \(v_1\) sütununda yalnız \(x_3\) satırının elemanı pozitiftir; oran \(1/1\), \(v_3\) çıkar, pivot \(1\)’dir.
| \(c_j\) | \(1\) | \(-1\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(1\) | \([1]\) | \(-1\) | \(1\) | \(0\) | \(\frac{1}{1} \Rightarrow\) |
| \(x_4\) | \(0\) | \(2\) | \(-1\) | \(1\) | \(0\) | \(1\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-1 \Uparrow\) | \(1\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot satırı aynen kalır ve \(x_1\) satırı olur: \((1 \mid 1, -1, 1, 0)\). Bu satırı \(x_4\) satırına da \(z_j - c_j\) satırına da ekleriz: \[ \begin{aligned} x_4&: \ (2 + 1 \mid -1 + 1,\ 1 - 1,\ 0 + 1,\ 1) = (3 \mid 0, 0, 1, 1), \\ z_j - c_j&: \ (0 + 1 \mid -1 + 1,\ 1 - 1,\ 0 + 1,\ 0) = (1 \mid 0, 0, 1, 0). \end{aligned} \]
| \(c_j\) | \(1\) | \(-1\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_1\) | \(1\) | \(1\) | \(1\) | \(-1\) | \(1\) | \(0\) |
| \(x_4\) | \(0\) | \(3\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = 1\) | \(0\) | \(0\) | \(1\) | \(0\) |
Bütün \(z_j - c_j \ge 0\); tablo optimaldir: \(X_1 = (1, 0, 0, 3)\) ve \(\max z = 1\).
Alternatif çözümler. Baz dışındaki \(v_2\)’nin kriteri \(z_2 - c_2 = 0\)’dır, ama sütunu \((-1, 0)\)’dır; pozitif eleman yoktur ve pivot yapılamaz. Önerme 7.3 gereği her \(\lambda \ge 0\) için \(x_2 = \lambda\) ve \[ x_1 = 1 - (-1)\lambda = 1 + \lambda, \qquad x_4 = 3 - 0 \cdot \lambda = 3 \] olan çözüm optimaldir. Kontrol: \((1 + \lambda) - \lambda = 1\), \(-(1 + \lambda) + \lambda + 3 = 2\) ve \(z = (1 + \lambda) - \lambda = 1\).
Başka optimal çözüm de yoktur. Optimal tabloda (2) eşitliği (Lemma 7.1) \(z = 1 - 0 \cdot x_2 - 1 \cdot x_3 = 1 - x_3\) verir; bir uygun çözüm ancak \(x_3 = 0\) ise optimaldir. \(x_3 = 0\) iken (1) eşitlikleri \(x_1 = 1 + x_2\) ve \(x_4 = 3\) verir. Böylece bütün optimal çözümler \[ (x_1, x_2) = (1 + \lambda,\ \lambda), \qquad \lambda \ge 0 \] noktalarıdır. Bunlar \((1, 0)\) köşesinden başlayıp \(x_1 - x_2 = 1\) doğrusu boyunca sonsuza uzanan bir ışın oluşturur. Amacın seviye doğruları \(x_1 - x_2 = \text{sabit}\) bu kenara paraleldir; en büyük değer \(1\) bu kenarın tamamında alınır. Optimal değer sonludur, optimal çözümler kümesi ise sınırsızdır.
\(\blacksquare\)
Bu bölümde gördüklerimizi, simpleks yöntemin son tablosunda karşılaşılabilecek durumlar olarak özetleyelim. Aşağıdaki tabloda “iyileştiren kriter” minimumda pozitif, maksimumda negatif \(z_j - c_j\) demektir.
| Son tablodaki belirti | Sonuç |
|---|---|
| İyileştiren kriterli bir \(v_k\) var ve sütununda pozitif eleman yok | Sınırsız çözüm; optimal çözüm yok |
| Tablo optimal, baz dışındaki bütün kriterler sıfırdan farklı | Optimal çözüm tek |
| Tablo optimal, baz dışı bir \(v_k\) için \(z_k - c_k = 0\) ve sütununda pozitif eleman var | Alternatif optimal uç nokta (dejenere değilse); aradaki bütün noktalar optimal |
| Tablo optimal, baz dışı bir \(v_k\) için \(z_k - c_k = 0\) ve sütununda pozitif eleman yok | Optimal çözümler bir ışın içerir (başka sıfır kriter yoksa tam olarak bu ışındır); optimal değer sonlu |
Şimdiye kadar bütün değişkenlerin negatif olmadığını varsaydık; simpleks yöntem de bu varsayıma dayanıyor. Oysa bazı problemlerde bir değişken negatif değerler de alabilir. Bir sonraki bölümde, İşaret kısıtlaması olmayan değişkenler bölümünde, böyle değişkenleri negatif olmayan değişkenlerin farkı olarak yazıp problemi yine simpleks yöntemle çözmeyi göreceğiz.