8 İşaret Kısıtlaması Olmayan Değişkenler
Şimdiye kadar çözdüğümüz bütün problemlerde değişkenlerin negatif olmaması istendi ve simpleks yöntem de bu koşula dayanıyor: başlangıç çözümü \(b_i \ge 0\) değerlerinden okunuyor, oran testi de hiçbir baz değişkeninin negatife düşmeyeceği adımı seçiyor. Oysa bazı büyüklükler doğal olarak negatif de olabilir. Bir deponun stok değişimi, bir yatırımın net kâr ya da zararı, bir fiyatın önceki döneme göre farkı bunlara örnektir. Böyle bir değişkene \(\ge 0\) koşulunu zorla eklemek problemi değiştirir ve gerçek optimumu kaçırmamıza yol açabilir.
İlk bölümdeki dönüştürme kuralları arasında (bkz. Bölüm 1.6) böyle bir değişkeni iki negatif olmayan değişkenin farkı olarak yazmayı görmüştük. Bu bölümde o kuralın problemi neden değiştirmediğini kanıtlayacak, iki yeni değişkenin simpleks tablosunda nasıl davrandığını inceleyecek ve üç örneği bütün tablolarıyla çözeceğiz. Örneklerin ikisinde optimum negatif koordinatlı bir noktada çıkacak, birinde ise problemin sınırsız olduğu ortaya çıkacak.
8.1 Dönüşüm ve Eşdeğerlik
Önce kuralı hatırlayalım, sonra onun problemi gerçekten değiştirmediğini kesin olarak gösterelim.
Lineer programlama problemindeki \(x_1, x_2, \dots, x_n\) değişkenlerinin negatif olmama koşulu, yani \(x_1, x_2, \dots, x_n \ge 0\) koşulu, bazı değişkenler için kaldırılmış olabilir. Örneğin \(x_r\) için işaret kısıtlaması kaldırılmışsa, yani \(x_r\) negatif değerler de alabiliyorsa
\[x_r = x_r' - x_r'', \qquad x_r', x_r'' \ge 0\]
dönüşümü yapılır: \(x_r\) kısıtlarda ve amaç fonksiyonunda geçtiği her yerde \(x_r' - x_r''\) ile değiştirilir. Böylece \(x_r\) yerine negatif olmayan iki değişken gelir ve problem işaretçe kısıtlı hale, yani bütün değişkenleri \(\ge 0\) olan bir probleme dönüşür. Birden çok değişken işaretsizse her birine ayrı bir çift ayrılır. (Bir değişken için \(x_r \le 0\) biliniyorsa tek bir yeni değişken yeter: \(x_r = -x_r'\). Bu bölüm işaretin hiç bilinmediği durumla ilgileniyor.)
Dönüşümün katsayılara etkisi basittir. \(i\). kısıttaki \(a_{ir}x_r\) terimi ve amaçtaki \(c_rx_r\) terimi
\[a_{ir}x_r = a_{ir}x_r' + (-a_{ir})x_r'', \qquad c_rx_r = c_rx_r' + (-c_r)x_r''\]
olur. Demek ki \(x_r'\)’nün kısıtlardaki sütunu \(v_r' = v_r\), amaç katsayısı \(c_r' = c_r\); \(x_r''\)’nün sütunu \(v_r'' = -v_r\), amaç katsayısı \(c_r'' = -c_r\)’dir. Katsayılar matrisinde \(v_r\) sütununun yerini, biri ötekinin negatifi olan iki sütun alır.
Önerme 8.1 (Dönüşüm problemi değiştirmez) \((P)\), \(x_r\) değişkeni işaretsiz, diğer değişkenleri \(\ge 0\) olan bir lineer programlama problemi; \((P')\) de \((P)\)’de \(x_r = x_r' - x_r''\) dönüşümü yapılarak elde edilen işaretçe kısıtlı problem olsun.
- \((P')\)’nün her uygun çözümünden, \(x_r = x_r' - x_r''\) alınarak, \((P)\)’nin amaç değeri aynı olan bir uygun çözümü elde edilir.
- \((P)\)’nin her uygun çözümü, \(x_r' = \max\{x_r, 0\}\) ve \(x_r'' = \max\{-x_r, 0\}\) alınarak, \((P')\)’nün amaç değeri aynı olan bir uygun çözümüne dönüşür.
Dolayısıyla iki problemin optimal değerleri aynıdır, \((P')\)’nün bir optimal çözümü 1. maddeyle \((P)\)’nin bir optimal çözümünü verir ve problemlerden biri sınırsızsa öteki de sınırsızdır.
İspat
Kısıtlar ve amaç fonksiyonu \(x_r\)’ye yalnız \(a_{ir}x_r\) (\(i = \overline{1,m}\)) ve \(c_rx_r\) terimleriyle bağlıdır; \((P')\)’de bu terimlerin yerini \(a_{ir}(x_r' - x_r'')\) ve \(c_r(x_r' - x_r'')\) alır. Diğer bütün terimler iki problemde aynıdır.
Birinci madde. \((P')\)’nün bir uygun çözümünde \(x_r = x_r' - x_r''\) sayısını alalım. Her kısıtın sol tarafı ve amaç fonksiyonu \((P)\)’de, \((P')\)’deki değerlerin aynısını verir; çünkü \(a_{ir}x_r = a_{ir}(x_r' - x_r'')\) ve \(c_rx_r = c_r(x_r' - x_r'')\)’dir. Diğer değişkenler aynen kalır ve \(\ge 0\)’dır; \(x_r\) için ise bir işaret koşulu yoktur. Yani elde edilen nokta \((P)\)’nin uygun bir çözümüdür ve amaç değeri aynıdır.
İkinci madde. \(x_r' = \max\{x_r, 0\} \ge 0\) ve \(x_r'' = \max\{-x_r, 0\} \ge 0\)’dır. \(x_r \ge 0\) ise \(x_r' - x_r'' = x_r - 0 = x_r\); \(x_r < 0\) ise \(x_r' - x_r'' = 0 - (-x_r) = x_r\) olur. Her iki durumda da \(x_r' - x_r'' = x_r\) olduğundan kısıtların sol tarafları ve amaç değeri değişmez; diğer değişkenler aynen kalır. Yani elde edilen nokta \((P')\)’nün uygun bir çözümüdür ve amaç değeri aynıdır.
Sonuç. İki madde birlikte şunu söyler: \((P)\)’nin uygun çözümlerinde amaç fonksiyonunun aldığı değerlerin kümesi, \((P')\)’nünkiyle aynıdır. Aynı kümenin en küçük (ya da en büyük) elemanı da aynıdır; küme alttan (ya da üstten) sınırsızsa bu, iki problem için birlikte geçerlidir. \((P')\)’nün bir optimal çözümü birinci maddeyle \((P)\)’nin aynı değerli bir uygun çözümüne gider; bu değer \((P)\)’nin de optimal değeri olduğundan o çözüm \((P)\)’nin optimal çözümüdür.
\(\blacksquare\)
İspat diğer değişkenlerin işaret koşulunu hiç kullanmıyor. Bu yüzden birden çok işaretsiz değişken varsa önerme her birine sırayla uygulanır ve sonuç yine geçerlidir.
Yani dönüşümün dayandığı gerçek şudur: her gerçel sayı iki negatif olmayan sayının farkıdır. Ama bu yazılış tek değildir: \(-6 = 0 - 6 = 1 - 7 = 2{,}5 - 8{,}5\). Genel olarak her \(t \ge 0\) için \((x_r' + t) - (x_r'' + t)\) farkı da aynı \(x_r\)’yi verir. Bu çokluk simpleks yöntemde sorun çıkarmaz, çünkü yöntem yalnız temel çözümler arasında dolaşır ve birazdan göreceğimiz gibi bir temel çözümde \(x_r'\) ile \(x_r''\)’den en az biri sıfırdır. Bu yüzden simpleks yöntemin bulduğu çözümde \(x_r\) pozitifse \(x_r'\) değişkeninde, negatifse \(x_r''\) değişkeninde görünür.
8.2 Simpleks Yöntemle Çözüm
Dönüşümden sonra elimizde bütün değişkenleri \(\ge 0\) olan sıradan bir problem vardır; onu şimdiye kadar öğrendiğimiz gibi çözeriz. Aşağıdaki reçete yalnız başa ve sona iki küçük adım ekler.
- Dönüşüm. Her işaretsiz \(x_r\) için \(x_r = x_r' - x_r''\) yaz. Katsayılar matrisinde \(v_r\) sütununun yerine \(v_r' = v_r\) ve \(v_r'' = -v_r\) sütunları, amaçta \(c_r\) yerine \(c_r\) ve \(-c_r\) katsayıları gelir. Diğer değişkenlerin numaraları değişmez; aylak ve artık değişkenler yine \(x_{n+1}, x_{n+2}, \dots\) indislerini alır.
- Simpleks. İşaretçe kısıtlı problemi standart forma, gerekirse yapay değişkenlerle simpleks yöntem ile çözülebilir hale getir ve simpleks yöntemle çöz. Tabloda \(v_r'\) ve \(v_r''\) sütunları yan yana, \(v_r\)’nin yerine yazılır.
- Geri dönüş. Son tablodan \(x_r'\) ve \(x_r''\) değerlerini oku, \(x_r = x_r' - x_r''\) hesapla ve sonucu orijinal değişkenlerle yaz.
Örnek 8.1 (Bir işaretsiz değişkenli minimum problemi) Aşağıdaki problemi simpleks yöntemle çözünüz. (\(x_1\) için işaret koşulu verilmemiştir.)
\[ \begin{aligned} -x_1 + 2x_2 &\le 6 \\ x_1 - x_2 &\le 4 \\ x_2 &\ge 0 \\ \min z &= x_1 + x_2 \end{aligned} \]
Çözüm
Dönüşüm. İşaret koşulu yalnız \(x_2\) için verilmiş; \(x_1\) değişkeninin işaret kısıtlaması yoktur. Bu nedenle \(x_1 = x_1' - x_1''\), \(x_1', x_1'' \ge 0\) dönüşümünü yaparız. Kısıtlarda ve amaçta yerine koyunca problem
\[ \begin{aligned} -(x_1' - x_1'') + 2x_2 &\le 6 \\ x_1' - x_1'' - x_2 &\le 4 \\ x_1', x_1'', x_2 &\ge 0 \\ \min z &= x_1' - x_1'' + x_2 \end{aligned} \]
işaretçe kısıtlı problemine dönüşür. Birinci kısıtta parantezi açınca \(-x_1' + x_1'' + 2x_2 \le 6\) olur.
Standart form. Bu bir minimum problemidir ve kısıtları \(\le\) biçimindedir; yani kanonik formda değildir, ama simpleks yöntem için kanonik form gerekmez. İki \(\le\) kısıta sırasıyla \(x_3\) ve \(x_4\) aylak değişkenlerini ekleriz. Orijinal problemde iki değişken olduğu için aylak değişkenler \(x_3\) ile başlar; \(x_1'\) ve \(x_1''\) yeni numara almaz:
\[ \begin{aligned} -x_1' + x_1'' + 2x_2 + x_3 &= 6 \\ x_1' - x_1'' - x_2 + x_4 &= 4 \\ x_1', x_1'', x_2, x_3, x_4 &\ge 0 \\ \min z &= x_1' - x_1'' + x_2 + 0x_3 + 0x_4 \end{aligned} \]
Bütün kısıtlar eşitlik, sağ taraflar \(6\) ve \(4\) negatif değil, bütün değişkenler \(\ge 0\); problem standart formdadır.
Çözülebilir hal. Sütunları sırasıyla \(v_1'\), \(v_1''\), \(v_2\), \(v_3\), \(v_4\) olan katsayılar matrisi
\[ \begin{bmatrix} -1 & 1 & 2 & 1 & 0 \\ 1 & -1 & -1 & 0 & 1 \end{bmatrix} \]
dir. \(v_3\) ve \(v_4\) sütunları \(2 \times 2\) birim matrisi oluşturur. Demek ki standart form zaten simpleks yöntem ile çözülebilir haldedir (Tanım 1.9); yapay değişken gerekmez. İlk iki sütunun birbirinin negatifi olduğuna, yani \(v_1'' = -v_1'\) olduğuna dikkat edelim.
Başlangıç tablosu. Başlangıç bazı \(B_0 = (v_3, v_4)\), başlangıç çözümü \(x_3 = 6\), \(x_4 = 4\) ve \(z_0 = 0\)’dır. \(\vec{c}_B = \vec{0}\) olduğundan her \(j\) için \(z_j - c_j = -c_j\)’dir (Önerme 4.3): \(v_1'\) için \(-1\), \(v_1''\) için \(1\), \(v_2\) için \(-1\).
Minimum probleminde simpleks kriteri pozitif olanlardan en büyüğü baza girer; bütün \(z_j - c_j \le 0\) olunca optimal çözüme ulaşılmıştır. Tek pozitif kriter \(1\) olduğundan \(v_1''\) baza girer. \(v_1''\) sütununda yalnız \(x_3\) satırının elemanı pozitiftir; \(x_4\) satırında \(-1\) bulunduğundan bu satır oran testine girmez. Oran \(6/1 = 6\) olur, \(v_3\) bazdan çıkar ve pivot, \(x_3\) satırı ile \(v_1''\) sütununun kesişimindeki \(1\)’dir.
| \(c_j\) | \(1\) | \(-1\) | \(1\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1'\) | \(v_1''\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(6\) | \(-1\) | \([1]\) | \(2\) | \(1\) | \(0\) | \(\frac{6}{1} \Rightarrow\) |
| \(x_4\) | \(0\) | \(4\) | \(1\) | \(-1\) | \(-1\) | \(0\) | \(1\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-1\) | \(1 \Uparrow\) | \(-1\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot \(1\) olduğundan \(x_3\) satırı aynen kalır ve \(c_B = -1\) ile \(x_1''\) satırı olur. \(x_4\) satırının pivot sütunundaki elemanı \(-1\) olduğundan bu satıra pivot satırı eklenir; \(z_j - c_j\) satırının pivot sütunundaki elemanı \(1\) olduğundan ondan pivot satırı çıkarılır:
\[ \begin{aligned} x_4&: \ (4 + 6 \mid 1 - 1,\ -1 + 1,\ -1 + 2,\ 0 + 1,\ 1 + 0) \\ &\quad = (10 \mid 0, 0, 1, 1, 1), \\[1mm] z_j - c_j&: \ (0 - 6 \mid -1 + 1,\ 1 - 1,\ -1 - 2,\ 0 - 1,\ 0 - 0) \\ &\quad = (-6 \mid 0, 0, -3, -1, 0). \end{aligned} \]
| \(c_j\) | \(1\) | \(-1\) | \(1\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1'\) | \(v_1''\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_1''\) | \(-1\) | \(6\) | \(-1\) | \(1\) | \(2\) | \(1\) | \(0\) |
| \(x_4\) | \(0\) | \(10\) | \(0\) | \(0\) | \(1\) | \(1\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = -6\) | \(0\) | \(0\) | \(-3\) | \(-1\) | \(0\) |
Simpleks kriterleri arasında pozitif olan kalmadı; bütün \(z_j - c_j \le 0\) olduğundan Sonuç 4.2 gereği optimal çözüme ulaşıldı (Tablo 8.2).
Geri dönüş. Tablodan \(x_1'' = 6\) ve \(x_4 = 10\) okunur; baz dışındaki \(x_1'\), \(x_2\), \(x_3\) sıfırdır. Orijinal değişkene dönersek
\[x_1 = x_1' - x_1'' = 0 - 6 = -6\]
olur. Böylece optimal çözüm
\[X^{*} = (x_1, x_2, x_3, x_4) = (-6, 0, 0, 10), \qquad \min z = -6 + 0 = -6\]
olarak bulunur. Sağlama: \(-(-6) + 2 \cdot 0 = 6 \le 6\) olduğundan birinci kısıt eşitlikle sağlanır (\(x_3 = 0\)); \(-6 - 0 = -6 \le 4\) olduğundan ikinci kısıtta \(4 - (-6) = 10 = x_4\) birim boşluk kalır. Optimalliği doğrudan da görebiliriz: birinci kısıttan \(x_1 \ge 2x_2 - 6\) çıkar, dolayısıyla her uygun noktada \(z = x_1 + x_2 \ge 3x_2 - 6 \ge -6\)’dır.
Grafikle karşılaştırma. Uygun bölge \(x_2 \ge 0\) yarı düzleminde \((-6, 0)\), \((4, 0)\) ve \((14, 10)\) köşeli üçgendir; köşelerdeki amaç değerleri sırasıyla \(-6\), \(4\) ve \(24\)’tür. Bölgenin bir kısmı \(x_1 < 0\) tarafındadır ve minimum tam orada, \((-6, 0)\) köşesinde alınır. Yanlışlıkla \(x_1 \ge 0\) koşulu da eklenseydi uygun bölge \((0, 0)\), \((4, 0)\), \((14, 10)\), \((0, 3)\) köşeli dörtgene küçülür ve minimum \((0, 0)\) noktasında \(z = 0\) çıkardı. İşaret koşulunu doğru okumak sonucu değiştirir.
Optimal tabloda \(v_1'\) ve \(v_1''\) sütunlarının kriterlerinin ikisinin de \(0\) olduğuna dikkat edelim; bunun nedenini bir sonraki kısımda göreceğiz.
\(\blacksquare\)
8.3 Tabloda Birbirinin Negatifi Olan Sütunlar
Örneğin tablolarına dikkatle bakınca \(v_1''\) sütununun her tabloda \(v_1'\) sütununun negatifi olduğu görülür. Başlangıç tablosunda (Tablo 8.1) bu sütunlar \((-1, 1)\) ve \((1, -1)\), kriterleri \(-1\) ve \(1\)’dir; optimal tabloda sütunlar \((-1, 0)\) ve \((1, 0)\), kriterlerin ikisi de \(0\)’dır. Bu bir rastlantı değildir.
Önerme 8.2 (Zıt sütunlar) \(x_r = x_r' - x_r''\) dönüşümü yapılmış bir problemde \(B\) herhangi bir baz olsun. \(v_r'\) ve \(v_r''\) vektörlerinin \(B\) bazına göre katsayıları (Tanım 4.2) \(\vec{y}\,' = (y_1', \dots, y_m')^T\) ve \(\vec{y}\,'' = (y_1'', \dots, y_m'')^T\), bunlara karşılık gelen amaç fonksiyonu değerleri (Tanım 4.3) de \(z'\) ve \(z''\) olsun. Bu durumda:
- \(v_r''\)’nün tablodaki sütunu \(v_r'\)’nünkinin negatifidir: \(\vec{y}\,'' = -\vec{y}\,'\).
- Simpleks kriterleri de birbirinin negatifidir: \(z'' - c_r'' = -(z' - c_r')\).
- \(v_r'\) ve \(v_r''\) aynı anda bazda bulunamaz. Dolayısıyla her temel çözümde \(x_r'\) ile \(x_r''\)’den en az biri sıfırdır.
İspat
Dönüşümden \(v_r'' = -v_r'\) ve \(c_r'' = -c_r'\) olduğunu biliyoruz. \(B\) bazının vektörleri \(w_1, \dots, w_m\) ve amaç katsayıları \(\vec{c}_B\) olsun.
Birinci madde. Tanım gereği \(v_r' = y_1'w_1 + \dots + y_m'w_m\)’dir. İki yanı \(-1\) ile çarparsak
\[v_r'' = -v_r' = (-y_1')w_1 + \dots + (-y_m')w_m\]
olur. Bir vektörün baz cinsinden yazılışı tek olduğundan \(v_r''\)’nün katsayıları \(y_i'' = -y_i'\), yani \(\vec{y}\,'' = -\vec{y}\,'\)’dür.
İkinci madde. Birinci maddeyi kullanarak \(z'' = \vec{c}_B^{\,T}\vec{y}\,'' = -\vec{c}_B^{\,T}\vec{y}\,' = -z'\) buluruz. Buradan
\[z'' - c_r'' = -z' + c_r' = -(z' - c_r')\]
çıkar.
Üçüncü madde. Bir bazın vektörleri lineer bağımsızdır. Oysa \(1 \cdot v_r' + 1 \cdot v_r'' = 0\) eşitliği, katsayıları sıfır olmayan bir lineer bileşimin sıfır vektörünü verdiğini söyler; yani \(v_r'\) ile \(v_r''\) lineer bağımlıdır ve aynı bazda bulunamaz. Bir temel çözümde baz dışındaki değişkenler sıfırdır (Tanım 2.3). Çiftten en az biri baz dışında olduğu için en az biri sıfırdır.
\(\blacksquare\)
Yani iki sütun tablodan tabloya birlikte değişir ve her zaman birbirinin “ayna görüntüsü” olarak kalır; bu yüzden tabloyu hesaplarken \(v_r''\) sütununu ayrıca hesaplamak gerekmez, \(v_r'\) sütununun işaretini değiştirmek yeter. Önermenin üç önemli sonucu var.
Sonuç 8.1 (Zıt sütunların sonuçları) \(x_r = x_r' - x_r''\) dönüşümü yapılmış bir problemde:
- Her uygun temel çözümde \(x_r' = \max\{x_r, 0\}\) ve \(x_r'' = \max\{-x_r, 0\}\)’dır. Yani simpleks yöntem \(x_r\)’yi pozitifse \(x_r'\), negatifse \(x_r''\) değişkeninde taşır.
- Bir tabloda çiftten en çok biri baza girmeye aday olabilir.
- Optimal tabloda iki kriter de sıfırdır: \(z' - c_r' = z'' - c_r'' = 0\).
İspat
Birinci madde. Önerme 8.2 gereği temel çözümde çiftin en az biri sıfırdır; çözüm uygun olduğundan ikisi de \(\ge 0\)’dır. \(x_r'' = 0\) ise \(x_r = x_r' \ge 0\) olur; bu durumda \(x_r' = x_r = \max\{x_r, 0\}\) ve \(x_r'' = 0 = \max\{-x_r, 0\}\)’dır. \(x_r' = 0\) ise \(x_r = -x_r'' \le 0\) olur; bu durumda \(x_r'' = -x_r = \max\{-x_r, 0\}\) ve \(x_r' = 0 = \max\{x_r, 0\}\)’dır.
İkinci madde. Minimum probleminde baza ancak kriteri pozitif olan vektör girer. \(z' - c_r' > 0\) ise \(z'' - c_r'' = -(z' - c_r') < 0\)’dır; yani ikisinin kriteri aynı anda pozitif olamaz. Maksimum probleminde baza ancak kriteri negatif olan vektör girer ve aynı akıl yürütme ikisinin kriterinin aynı anda negatif olamayacağını gösterir. Kriterler sıfırsa ikisi de aday değildir.
Üçüncü madde. Kısaca \(d = z' - c_r'\) yazalım; Önerme 8.2 gereği \(z'' - c_r'' = -d\)’dir. Minimum probleminin optimal tablosunda bütün kriterler \(\le 0\) olduğundan \(d \le 0\) ve \(-d \le 0\), yani \(d = 0\)’dır. Maksimum probleminin optimal tablosunda bütün kriterler \(\ge 0\) olduğundan yine \(d \ge 0\) ve \(-d \ge 0\), yani \(d = 0\) çıkar.
\(\blacksquare\)
Üçüncü madde bir yanılgıya karşı da uyarır. Baz dışında kalıp kriteri sıfır olan bir vektör genellikle alternatif optimal çözümün belirtisidir (Sınırsız çözüm ve alternatif optimal çözüm). Ama çiftten biri bazdaysa, baz dışındaki eşinin sıfır kriteri böyle bir anlam taşımaz. Örneğin Örnek 8.1 optimal tablosunda (Tablo 8.2) \(x_1''\) bazda ve \(v_1'\) baz dışında, kriteri \(0\)’dır. \(v_1'\) sütunu \((-1, 0)\)’dır ve pozitif elemanı yoktur, dolayısıyla baza alınamaz. \(x_1'\)’yü \(\lambda \ge 0\) kadar artırırsak birinci denklemden \(x_1'' = 6 + \lambda\) olur ve \(x_1 = \lambda - (6 + \lambda) = -6\) değişmez. Yani orijinal değişkenlerde yeni bir çözüm çıkmaz, yalnız aynı \(x_1 = -6\) sayısının başka bir fark olarak yazılışı ortaya çıkar. Genel olarak da \(v_r''\) bazda iken tablodaki sütunu bir birim vektördür ve Önerme 8.2 gereği \(v_r'\)’nün sütunu o birim vektörün negatifidir; pozitif elemanı olmadığı için baza giremez. \(v_r'\) bazdayken de durum aynıdır.
Şimdi önermeyi birkaç iterasyon süren bir örnekte izleyelim. Bu örnekte optimum yine negatif koordinatlı bir noktada çıkacak ve \(x_1 \ge 0\) koşulu yanlışlıkla eklenseydi simpleks yöntemin daha erken, yanlış bir noktada duracağını göreceğiz.
Örnek 8.2 (Optimumu negatif koordinatlı bir maksimum problemi) \(x_1\) işaretsiz olmak üzere
\[ \begin{aligned} -x_1 + x_2 &\le 4 \\ x_1 + 2x_2 &\le 2 \\ x_2 &\ge 0 \\ \max z &= x_1 + 4x_2 \end{aligned} \]
problemini simpleks yöntemle çözünüz. Sonucu grafik yöntemle ve \(x_1 \ge 0\) varsayılsaydı bulunacak sonuçla karşılaştırınız.
Çözüm
Dönüşüm ve standart form. \(x_1 = x_1' - x_1''\), \(x_1', x_1'' \ge 0\) yazarız. Kısıtlar \(-x_1' + x_1'' + x_2 \le 4\) ve \(x_1' - x_1'' + 2x_2 \le 2\), amaç \(z = x_1' - x_1'' + 4x_2\) olur. İki \(\le\) kısıta \(x_3\) ve \(x_4\) aylak değişkenlerini ekleyerek standart formu elde ederiz:
\[ \begin{aligned} -x_1' + x_1'' + x_2 + x_3 &= 4 \\ x_1' - x_1'' + 2x_2 + x_4 &= 2 \\ x_1', x_1'', x_2, x_3, x_4 &\ge 0 \\ \max z &= x_1' - x_1'' + 4x_2 + 0x_3 + 0x_4 \end{aligned} \]
Sağ taraflar negatif değildir ve \(v_3\), \(v_4\) sütunları birim matrisi oluşturur; problem simpleks yöntem ile çözülebilir haldedir.
Başlangıç tablosu. \(B_0 = (v_3, v_4)\), \(z_0 = 0\) ve \(z_j - c_j = -c_j\)’dir: \(v_1'\) için \(-1\), \(v_1''\) için \(1\), \(v_2\) için \(-4\). Maksimum probleminde en negatif \(z_j - c_j\) baza girer; bütün \(z_j - c_j \ge 0\) olunca optimal çözüme ulaşılmıştır. En negatif kriter \(-4\) olduğundan \(v_2\) baza girer. Oranlar \(4/1 = 4\) ve \(2/2 = 1\)’dir; en küçüğü \(x_4\) satırında olduğundan \(v_4\) bazdan çıkar, pivot \(2\)’dir.
| \(c_j\) | \(1\) | \(-1\) | \(4\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1'\) | \(v_1''\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(4\) | \(-1\) | \(1\) | \(1\) | \(1\) | \(0\) | \(\frac{4}{1}\) |
| \(x_4\) | \(0\) | \(2\) | \(1\) | \(-1\) | \([2]\) | \(0\) | \(1\) | \(\frac{2}{2} \Rightarrow\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-1\) | \(1\) | \(-4 \Uparrow\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot satırı \(2\)’ye bölünür ve \(c_B = 4\) ile \(x_2\) satırı olur: \(\big(1 \mid \tfrac{1}{2}, -\tfrac{1}{2}, 1, 0, \tfrac{1}{2}\big)\). \(x_3\) satırından bu satır çıkarılır, \(z_j - c_j\) satırına bu satırın \(4\) katı eklenir:
\[ \begin{aligned} x_3&: \ \Big(4 - 1 \ \Big|\ -1 - \frac{1}{2},\ 1 + \frac{1}{2},\ 0,\ 1,\ -\frac{1}{2}\Big) \\ &\quad = \Big(3 \ \Big|\ -\frac{3}{2}, \frac{3}{2}, 0, 1, -\frac{1}{2}\Big), \\[1mm] z_j - c_j&: \ (0 + 4 \mid -1 + 2,\ 1 - 2,\ 0,\ 0,\ 0 + 2) \\ &\quad = (4 \mid 1, -1, 0, 0, 2). \end{aligned} \]
| \(c_j\) | \(1\) | \(-1\) | \(4\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1'\) | \(v_1''\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_3\) | \(0\) | \(3\) | \(-\frac{3}{2}\) | \(\left[\frac{3}{2}\right]\) | \(0\) | \(1\) | \(-\frac{1}{2}\) | \(\frac{3}{3/2} \Rightarrow\) |
| \(x_2\) | \(4\) | \(1\) | \(\frac{1}{2}\) | \(-\frac{1}{2}\) | \(1\) | \(0\) | \(\frac{1}{2}\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = 4\) | \(1\) | \(-1 \Uparrow\) | \(0\) | \(0\) | \(2\) |
Bu tablonun çözümü \(x_1' = x_1'' = 0\), \(x_2 = 1\), yani \((x_1, x_2) = (0, 1)\) ve \(z = 4\)’tür. Önerme 8.2 burada da görülüyor: \(v_1'\) ve \(v_1''\) sütunları \(\big(-\tfrac{3}{2}, \tfrac{1}{2}\big)\) ve \(\big(\tfrac{3}{2}, -\tfrac{1}{2}\big)\), kriterleri \(1\) ve \(-1\)’dir.
Şimdi bir an \(x_1 \ge 0\) olduğunu varsayalım. O zaman \(x_1\) dönüşüme uğramaz ve tabloda \(v_1''\) sütunu hiç bulunmaz; \(v_1'\) sütunu \(v_1\)’in kendisi olur. Kalan kriterler \(1, 0, 0, 2\)’nin hepsi \(\ge 0\) olduğundan yöntem burada durur ve \(x_1 = 0\), \(x_2 = 1\), \(\max z = 4\) sonucunu verirdi. İşaretsiz \(x_1\) için ise \(v_1''\)’nün kriteri \(-1 < 0\)’dır; amaç daha da büyütülebilir.
Maksimumda en negatif kriter girer; tek negatif kriter \(-1\) olduğundan \(v_1''\) baza girer. \(v_1''\) sütununda \(x_2\) satırının elemanı \(-\tfrac{1}{2} < 0\) olduğundan bu satır teste girmez; tek oran \(3 / \tfrac{3}{2} = 2\)’dir. \(v_3\) bazdan çıkar, pivot \(\tfrac{3}{2}\)’dir.
İkinci iterasyon. Pivot satırı \(\tfrac{3}{2}\)’ye bölünür, yani \(\tfrac{2}{3}\) ile çarpılır ve \(c_B = -1\) ile \(x_1''\) satırı olur: \(\big(2 \mid -1, 1, 0, \tfrac{2}{3}, -\tfrac{1}{3}\big)\). \(x_2\) satırına bu satırın \(\tfrac{1}{2}\) katı, \(z_j - c_j\) satırına da \(1\) katı eklenir:
\[ \begin{aligned} x_2&: \ \Big(1 + 1 \ \Big|\ \frac{1}{2} - \frac{1}{2},\ -\frac{1}{2} + \frac{1}{2},\ 1,\ 0 + \frac{1}{3},\ \frac{1}{2} - \frac{1}{6}\Big) \\ &\quad = \Big(2 \ \Big|\ 0, 0, 1, \frac{1}{3}, \frac{1}{3}\Big), \\[1mm] z_j - c_j&: \ \Big(4 + 2 \ \Big|\ 1 - 1,\ -1 + 1,\ 0,\ 0 + \frac{2}{3},\ 2 - \frac{1}{3}\Big) \\ &\quad = \Big(6 \ \Big|\ 0, 0, 0, \frac{2}{3}, \frac{5}{3}\Big). \end{aligned} \]
| \(c_j\) | \(1\) | \(-1\) | \(4\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1'\) | \(v_1''\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_1''\) | \(-1\) | \(2\) | \(-1\) | \(1\) | \(0\) | \(\frac{2}{3}\) | \(-\frac{1}{3}\) |
| \(x_2\) | \(4\) | \(2\) | \(0\) | \(0\) | \(1\) | \(\frac{1}{3}\) | \(\frac{1}{3}\) |
| \(z_j - c_j\) | \(z_0 = 6\) | \(0\) | \(0\) | \(0\) | \(\frac{2}{3}\) | \(\frac{5}{3}\) |
Bütün \(z_j - c_j \ge 0\) olduğundan Sonuç 4.3 gereği tablo optimaldir (Tablo 8.5). \(v_1'\) ile \(v_1''\)’nün kriterleri, sonucun (Sonuç 8.1) üçüncü maddesinin söylediği gibi, ikisi de \(0\)’dır.
Geri dönüş. Tablodan \(x_1'' = 2\), \(x_2 = 2\) okunur; \(x_1' = x_3 = x_4 = 0\)’dır. Orijinal değişken \(x_1 = 0 - 2 = -2\) olur ve optimal çözüm
\[X^{*} = (x_1, x_2, x_3, x_4) = (-2, 2, 0, 0), \qquad \max z = -2 + 4 \cdot 2 = 6\]
olarak bulunur. Sağlama: \(-(-2) + 2 = 4\) ve \(-2 + 2 \cdot 2 = 2\); iki kısıt da eşitlikle sağlanır, bu yüzden iki aylak değişken de sıfırdır.
Grafikle karşılaştırma. \(x_2 \ge 0\) yarı düzleminde uygun bölge \((-4, 0)\), \((2, 0)\) ve \((-2, 2)\) köşeli üçgendir. Köşelerdeki amaç değerleri \(z(-4, 0) = -4\), \(z(2, 0) = 2\) ve \(z(-2, 2) = 6\)’dır; en büyüğü simpleks yöntemin bulduğu \(6\)’dır. \(x_1 \ge 0\) da istenseydi uygun bölge \((0, 0)\), \((2, 0)\), \((0, 1)\) köşeli küçük üçgene iner; köşe değerleri \(0\), \(2\) ve \(4\) olduğundan maksimum \((0, 1)\) noktasında \(z = 4\) çıkardı. Bu, simpleks yöntemin birinci iterasyon tablosunda bulduğu noktanın ta kendisidir.
\(\blacksquare\)
8.4 Sınırsız Çıkan Bir Örnek
Dönüşüm, birden çok işaretsiz değişkende de aynı biçimde uygulanır. Aşağıdaki örnekte iki değişken işaretsizdir ve problemin sınırsız olduğu ortaya çıkar; sınırsızlık belirtisi bu kez bir işaretsiz değişkenin sütununda görünür.
Örnek 8.3 (İki işaretsiz değişkenli bir minimum problemi) Aşağıdaki problemi simpleks yöntemle çözünüz. (\(x_3\) ve \(x_5\) için işaret koşulu verilmemiştir.)
\[ \begin{aligned} 4x_1 - 5x_2 - 9x_3 + x_4 - 2x_5 &\le 6 \\ 2x_1 + 3x_2 + 4x_3 - 5x_4 + x_5 &\le 9 \\ x_1 + x_2 - 5x_3 - 7x_4 + 11x_5 &\le 10 \\ x_1, x_2, x_4 &\ge 0 \\ \min z &= 3x_1 + x_2 - 4x_3 + 5x_4 + 9x_5 \end{aligned} \]
Çözüm
Dönüşüm. \(x_3\) ve \(x_5\) değişkenlerinin işaret kısıtlaması yoktur. Bu nedenle \(x_3 = x_3' - x_3''\), \(x_3', x_3'' \ge 0\) ve \(x_5 = x_5' - x_5''\), \(x_5', x_5'' \ge 0\) dönüşümlerini yaparız. Bu dönüşümler altında problem
\[ \begin{aligned} 4x_1 - 5x_2 - 9(x_3' - x_3'') + x_4 - 2(x_5' - x_5'') &\le 6 \\ 2x_1 + 3x_2 + 4(x_3' - x_3'') - 5x_4 + (x_5' - x_5'') &\le 9 \\ x_1 + x_2 - 5(x_3' - x_3'') - 7x_4 + 11(x_5' - x_5'') &\le 10 \\ x_1, x_2, x_3', x_3'', x_4, x_5', x_5'' &\ge 0 \\ \min z &= 3x_1 + x_2 - 4(x_3' - x_3'') \\ &\quad + 5x_4 + 9(x_5' - x_5'') \end{aligned} \]
işaretçe kısıtlı problemine dönüşür.
Standart form ve çözülebilir hal. Parantezleri açıp üç \(\le\) kısıta sırasıyla \(x_6\), \(x_7\), \(x_8\) aylak değişkenlerini ekleriz. Orijinal problemde beş değişken olduğu için aylak değişkenler \(x_6\) ile başlar:
\[ \begin{aligned} 4x_1 - 5x_2 - 9x_3' + 9x_3'' + x_4 - 2x_5' + 2x_5'' + x_6 &= 6 \\ 2x_1 + 3x_2 + 4x_3' - 4x_3'' - 5x_4 + x_5' - x_5'' + x_7 &= 9 \\ x_1 + x_2 - 5x_3' + 5x_3'' - 7x_4 + 11x_5' - 11x_5'' + x_8 &= 10 \\ x_1, x_2, x_3', x_3'', x_4, x_5', x_5'', x_6, x_7, x_8 &\ge 0 \\ \min z &= 3x_1 + x_2 - 4x_3' + 4x_3'' + 5x_4 \\ &\quad + 9x_5' - 9x_5'' + 0x_6 + 0x_7 + 0x_8 \end{aligned} \]
Bütün kısıtlar eşitlik, sağ taraflar \(6\), \(9\), \(10\) negatif değil ve bütün değişkenler \(\ge 0\); problem standart formdadır. \(v_6\), \(v_7\), \(v_8\) sütunları \(3 \times 3\) birim matrisi oluşturduğundan standart form simpleks yöntem ile çözülebilir haldedir; yapay değişken gerekmez.
Başlangıç tablosu. \(B_0 = (v_6, v_7, v_8)\), başlangıç çözümü \(x_6 = 6\), \(x_7 = 9\), \(x_8 = 10\) ve \(z_0 = 0\)’dır. Kriterler \(z_j - c_j = -c_j\)’dir. İki çiftin kriterleri beklendiği gibi zıt işaretlidir: \(v_3'\) ve \(v_3''\) için \(4\) ve \(-4\), \(v_5'\) ve \(v_5''\) için \(-9\) ve \(9\).
Minimum probleminde simpleks kriteri pozitif olanlardan en büyüğü girer; bütün \(z_j - c_j \le 0\) olunca optimal çözüme ulaşılmıştır. Pozitif kriterler \(4\) ve \(9\)’dur; en büyüğü \(9\) olduğundan \(v_5''\) baza girer. \(v_5''\) sütununun elemanları \(2\), \(-1\), \(-11\)’dir; yalnız \(x_6\) satırının elemanı pozitif olduğundan tek oran \(6/2 = 3\)’tür. \(v_6\) bazdan çıkar, pivot \(2\)’dir.
| \(c_j\) | \(3\) | \(1\) | \(-4\) | \(4\) | \(5\) | \(9\) | \(-9\) | \(0\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3'\) | \(v_3''\) | \(v_4\) | \(v_5'\) | \(v_5''\) | \(v_6\) | \(v_7\) | \(v_8\) | Oran |
| \(x_6\) | \(0\) | \(6\) | \(4\) | \(-5\) | \(-9\) | \(9\) | \(1\) | \(-2\) | \([2]\) | \(1\) | \(0\) | \(0\) | \(\frac{6}{2} \Rightarrow\) |
| \(x_7\) | \(0\) | \(9\) | \(2\) | \(3\) | \(4\) | \(-4\) | \(-5\) | \(1\) | \(-1\) | \(0\) | \(1\) | \(0\) | \(-\) |
| \(x_8\) | \(0\) | \(10\) | \(1\) | \(1\) | \(-5\) | \(5\) | \(-7\) | \(11\) | \(-11\) | \(0\) | \(0\) | \(1\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-3\) | \(-1\) | \(4\) | \(-4\) | \(-5\) | \(-9\) | \(9 \Uparrow\) | \(0\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot satırı \(2\)’ye bölünür ve \(c_B = -9\) ile \(x_5''\) satırı olur:
\[\Big(3 \ \Big|\ 2, -\frac{5}{2}, -\frac{9}{2}, \frac{9}{2}, \frac{1}{2}, -1, 1, \frac{1}{2}, 0, 0\Big).\]
\(v_5''\) sütunundaki elemanlar \(x_7\) satırında \(-1\), \(x_8\) satırında \(-11\), \(z_j - c_j\) satırında \(9\) olduğundan \(x_7\) satırına yeni satırın \(1\) katı, \(x_8\) satırına \(11\) katı eklenir; \(z_j - c_j\) satırından ise \(9\) katı çıkarılır. Birkaç eleman:
\[ \begin{aligned} x_7, v_0&: \ 9 + 3 = 12, & x_7, v_4&: \ -5 + \frac{1}{2} = -\frac{9}{2}, \\[1mm] x_8, v_0&: \ 10 + 11 \cdot 3 = 43, & x_8, v_3'&: \ -5 + 11 \cdot \Big(-\frac{9}{2}\Big) = -\frac{109}{2}, \\[1mm] z_0&: \ 0 - 9 \cdot 3 = -27, & v_3'&: \ 4 - 9 \cdot \Big(-\frac{9}{2}\Big) = \frac{89}{2}, \\[1mm] v_2&: \ -1 - 9 \cdot \Big(-\frac{5}{2}\Big) = \frac{43}{2}, & v_6&: \ 0 - 9 \cdot \frac{1}{2} = -\frac{9}{2}. \end{aligned} \]
Son iki satırdaki \(z_0\), \(v_3'\), \(v_2\), \(v_6\) değerleri \(z_j - c_j\) satırına aittir. \(v_3''\) sütununu ayrıca hesaplamaya gerek yoktur: Önerme 8.2 gereği \(v_3'\) sütununun negatifidir.
| \(c_j\) | \(3\) | \(1\) | \(-4\) | \(4\) | \(5\) | \(9\) | \(-9\) | \(0\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3'\) | \(v_3''\) | \(v_4\) | \(v_5'\) | \(v_5''\) | \(v_6\) | \(v_7\) | \(v_8\) | Oran |
| \(x_5''\) | \(-9\) | \(3\) | \(2\) | \(-\frac{5}{2}\) | \(-\frac{9}{2}\) | \(\frac{9}{2}\) | \(\frac{1}{2}\) | \(-1\) | \(1\) | \(\frac{1}{2}\) | \(0\) | \(0\) | \(-\) |
| \(x_7\) | \(0\) | \(12\) | \(4\) | \(\frac{1}{2}\) | \(-\frac{1}{2}\) | \(\frac{1}{2}\) | \(-\frac{9}{2}\) | \(0\) | \(0\) | \(\frac{1}{2}\) | \(1\) | \(0\) | \(-\) |
| \(x_8\) | \(0\) | \(43\) | \(23\) | \(-\frac{53}{2}\) | \(-\frac{109}{2}\) | \(\frac{109}{2}\) | \(-\frac{3}{2}\) | \(0\) | \(0\) | \(\frac{11}{2}\) | \(0\) | \(1\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = -27\) | \(-21\) | \(\frac{43}{2}\) | \(\frac{89}{2} \Uparrow\) | \(-\frac{89}{2}\) | \(-\frac{19}{2}\) | \(0\) | \(0\) | \(-\frac{9}{2}\) | \(0\) | \(0\) |
Bu tablonun temel çözümünde \(x_5'' = 3\), \(x_7 = 12\), \(x_8 = 43\) ve diğer değişkenler sıfırdır. Orijinal değişkenlerle \(x_5 = x_5' - x_5'' = 0 - 3 = -3\), yani
\[(x_1, x_2, \dots, x_8) = (0, 0, 0, 0, -3, 0, 12, 43), \qquad z = 9 \cdot (-3) = -27\]
olur. Bir temel çözümde orijinal bir değişkenin negatif çıkması, dönüşümün tam da izin verdiği şeydir.
Sınırsızlık. Pozitif kriterler \(\tfrac{43}{2}\) (\(v_2\)) ve \(\tfrac{89}{2}\) (\(v_3'\))’dir; en büyüğü \(\tfrac{89}{2}\) olduğundan \(v_3'\) baza girmelidir. Ama \(v_3'\) sütununun elemanları \(-\tfrac{9}{2}\), \(-\tfrac{1}{2}\), \(-\tfrac{109}{2}\)’nin hiçbiri pozitif değildir; oran testi yapılamaz. Simpleks kriteri pozitif olan \(v_3'\) vektörünün elemanlarının her biri negatif olduğundan, Önerme 4.2 gereği amaç fonksiyonu alttan sınırsızdır: problemin sınırsız çözümü vardır, minimumu yoktur (Sınırsız çözüm ve alternatif optimal çözüm). \(v_2\) sütununda pozitif eleman bulunması bu sonucu değiştirmez; kriteri iyileşme gösteren tek bir sütunda pozitif eleman olmaması sınırsızlık için yeter.
Sınırsız çözümü açıkça yazalım. \(\lambda \ge 0\) olmak üzere \(x_3' = \lambda\) alıp baz dışındaki diğer değişkenleri (\(x_1\), \(x_2\), \(x_3''\), \(x_4\), \(x_5'\), \(x_6\)) sıfır bırakırız. Baz değişkenleri \(v_3'\) sütununa göre değişir:
\[ \begin{aligned} x_5'' &= 3 - \lambda \Big(-\frac{9}{2}\Big) = 3 + \frac{9}{2}\lambda, \\[1mm] x_7 &= 12 - \lambda \Big(-\frac{1}{2}\Big) = 12 + \frac{1}{2}\lambda, \\[1mm] x_8 &= 43 - \lambda \Big(-\frac{109}{2}\Big) = 43 + \frac{109}{2}\lambda. \end{aligned} \]
Bunların hepsi \(\lambda \ge 0\) iken pozitiftir. Orijinal değişkenlere dönersek \(x_3 = x_3' - x_3'' = \lambda\) ve \(x_5 = x_5' - x_5'' = -3 - \tfrac{9}{2}\lambda\) olur. Böylece her \(\lambda \ge 0\) için
\[ \begin{aligned} X(\lambda) = \Big(&0,\ 0,\ \lambda,\ 0,\ -3 - \frac{9}{2}\lambda,\ 0, \\ &12 + \frac{1}{2}\lambda,\ 43 + \frac{109}{2}\lambda\Big) \end{aligned} \]
uygun bir çözümdür. Sağlama için \(x_3 = \lambda\) ve \(x_5 = -3 - \tfrac{9}{2}\lambda\) değerlerini orijinal kısıtların sol taraflarına koyalım (\(x_1 = x_2 = x_4 = 0\)):
\[ \begin{aligned} -9\lambda - 2\Big(-3 - \frac{9}{2}\lambda\Big) &= 6, \\[1mm] 4\lambda + \Big(-3 - \frac{9}{2}\lambda\Big) &= -3 - \frac{1}{2}\lambda \le 9, \\[1mm] -5\lambda + 11\Big(-3 - \frac{9}{2}\lambda\Big) &= -33 - \frac{109}{2}\lambda \le 10. \end{aligned} \]
Birinci kısıt eşitlikle sağlanır (\(x_6 = 0\)). İkinci ve üçüncü kısıtta sağ tarafa kalan boşluklar \(9 - \big(-3 - \tfrac{1}{2}\lambda\big) = x_7\) ve \(10 - \big(-33 - \tfrac{109}{2}\lambda\big) = x_8\)’dir. Bu çözümde amaç fonksiyonunun değeri
\[z = -4\lambda + 9\Big(-3 - \frac{9}{2}\lambda\Big) = -27 - \frac{89}{2}\lambda\]
olarak bulunur. Bu, Önerme 4.2 ispatındaki \(z_0 - \lambda(z_k - c_k) = -27 - \tfrac{89}{2}\lambda\) formülüyle aynıdır ve \(\lambda \to \infty\) iken \(-\infty\)’a gider. Yani \(x_3\) büyüdükçe \(x_5\) negatif yönde büyür; amaçta katsayısı \(9\) olan \(x_5\) negatife gittikçe \(z\) sınırsızca küçülür.
Son olarak birinci iterasyon tablosunda iki çifte bakalım. \(v_3'\) ve \(v_3''\) sütunları birbirinin negatifidir, kriterleri \(\tfrac{89}{2}\) ve \(-\tfrac{89}{2}\)’dir. \(x_5''\) bazda olduğundan sütunu birim vektör \((1, 0, 0)\), eşi \(v_5'\)’nün sütunu ise \((-1, 0, 0)\)’dır ve ikisinin de kriteri \(0\)’dır (Önerme 8.2).
\(\blacksquare\)
Bu bölümde işaret kısıtlaması olmayan bir değişkeni \(x_r = x_r' - x_r''\) ile iki negatif olmayan değişkene ayırmanın problemi değiştirmediğini, simpleks tablosunda bu iki değişkenin sütunlarının ve kriterlerinin her zaman birbirinin negatifi olduğunu ve bu yüzden ikisinin aynı anda bazda bulunamadığını gördük. Sonucu okurken \(x_r = x_r' - x_r''\) farkını almayı unutmamak yeter. Bir sonraki bölümde, Sınırlı değişkenler bölümünde, değişkenlerin yalnız işaretinin değil, alabileceği değerlerin de alttan ve üstten sınırlandığı problemleri ele alacağız.