2  Temel Çözümler ve Konveks Kümeler

Önceki bölümde bir lineer programlama problemini standart forma getirmeyi öğrendik: bütün kısıtlar eşitlik, bütün sağ taraflar ve bütün değişkenler negatif olmayan. Standart formdaki kısıtlar \(m\) denklemli, \(n\) bilinmeyenli bir doğrusal denklem sistemidir ve \(m < n\) olduğu için bu sistemin genellikle sonsuz sayıda çözümü vardır. Sonsuz sayıda aday arasından en iyisini aramak umutsuz görünür. Bölümün ilk yarısında bu sonsuz adayı sonlu sayıya indiren kavramı, temel çözümü, tanıyacağız: bazı değişkenleri sıfır alıp geri kalanlar için kare bir sistem çözerek bulunan özel çözümler.

İkinci yarıda işin geometrisine geçeceğiz. Uygun çözümlerin kümesinin konveks olduğunu, yani iki uygun çözümü birleştiren doğru parçasının tamamen uygun çözümlerden oluştuğunu göreceğiz. Yol boyunca temel çözümlerin uygun bölgenin köşeleriyle yakından ilgili olduğunu da fark edeceğiz; bu bağı bir sonraki bölümde kesin olarak kuracağız.

2.1 Çözüm ve Uygun Çözüm

Önce hangi problemle çalıştığımızı sabitleyelim. Bu bölüm boyunca standart formdaki (Tanım 1.7) bir problemi ele alacağız:

\[ \begin{aligned} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &= b_2 \\ &\;\;\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &= b_m \end{aligned} \tag{1} \]

\[x_1 \ge 0, \ x_2 \ge 0, \ \dots, \ x_n \ge 0 \tag{2}\]

\[\min z = c_1x_1 + c_2x_2 + \dots + c_nx_n \quad (\text{veya } \max) \tag{3}\]

Matris gösterimiyle (1) sistemi \(A\vec{x} = \vec{b}\), (2) koşulları ise \(\vec{x} \ge 0\) demektir. \(A\) katsayılar matrisi \(m \times n\) boyutludur ve \(m < n\)’dir.

Tanım 2.1 (Çözüm)  

1. sistemini sağlayan her \(\vec{x} = (x_1, x_2, \dots, x_n)^T\) vektörüne ya da \(X = (x_1, x_2, \dots, x_n)\) noktasına lineer programlama probleminin bir çözümü denir.

Tanım 2.2 (Uygun çözüm)  

1. sistemini ve (2) koşullarını birlikte sağlayan her \(\vec{x} = (x_1, x_2, \dots, x_n)^T\) vektörüne ya da \(X = (x_1, x_2, \dots, x_n)\) noktasına lineer programlama probleminin bir uygun çözümü denir.

Yani çözüm yalnız denklemlere bakar; uygun çözüm ayrıca her değişkenin negatif olmamasını ister. Her uygun çözüm bir çözümdür, ama tersi doğru değildir. Vektörü ve noktayı aynı nesne sayıyoruz: \(\vec{x}\) yazımı hesaplarda, \(X\) yazımı geometrik yorumlarda işimize yarar. Amaç fonksiyonu bu iki tanımda hiç rol oynamaz; uygun çözümler arasından seçim yaparken devreye girecek (Tanım 2.7).

Örnek 2.1 (Çözüm mü, uygun çözüm mü?) \(x_1 + 2x_2 + x_3 = 4\) denklemi ve \(x_1, x_2, x_3 \ge 0\) koşulları veriliyor (\(m = 1\), \(n = 3\)). \((1, 1, 1)\), \((4, 0, 0)\), \((6, -1, 0)\) ve \((0, 0, 5)\) noktalarından hangileri çözüm, hangileri uygun çözümdür?

Çözüm

Her noktada önce denklemin sol tarafını hesaplayalım, sonra işaretlere bakalım.

• \((1, 1, 1)\): \(1 + 2 + 1 = 4\), denklem sağlanır. Bileşenlerin hepsi negatif olmadığından uygun çözümdür.
• \((4, 0, 0)\): \(4 + 0 + 0 = 4\) ve bileşenler negatif değil; uygun çözümdür.
• \((6, -1, 0)\): \(6 - 2 + 0 = 4\), denklem sağlanır; bu nokta bir çözümdür. Ama \(x_2 = -1 < 0\) olduğu için uygun çözüm değildir.
• \((0, 0, 5)\): \(0 + 0 + 5 = 5 \ne 4\). Bileşenleri negatif olmadığı halde denklemi sağlamadığı için çözüm bile değildir.

Uygun çözüm olmak için iki koşulun birlikte sağlanması gerekir: denklemler ve işaret koşulları.

\(\blacksquare\)

Örnek 2.2 (Uygun çözümleri bulmak) \[ \begin{aligned} x_1 + 2x_2 + 3x_3 + 4x_4 &= 7 \\ 2x_1 + x_2 + x_3 + 2x_4 &= 3 \\ x_1, x_2, x_3, x_4 &\ge 0 \end{aligned} \]

koşullarını ele alalım. Bu problemin uygun çözümlerini bulunuz. Uygun çözüm nasıl bulunur?

Çözüm

İki denklem ve dört bilinmeyen var. Değişkenlerden ikisine değer verirsek geri kalan ikisi denklemlerden hesaplanır. Örneğin \(x_3 = 2\) ve \(x_4 = 0\) alalım. Denklemler

\[x_1 + 2x_2 = 1, \qquad 2x_1 + x_2 = 1\]

olur. Birinciden \(x_1 = 1 - 2x_2\) çıkar; ikincide yerine koyarsak \(2 - 4x_2 + x_2 = 1\), yani \(x_2 = \tfrac{1}{3}\) ve \(x_1 = \tfrac{1}{3}\) bulunur. Böylece

\[X = \left(\tfrac{1}{3}, \tfrac{1}{3}, 2, 0\right)\]

noktası (1) denklemlerini sağlar ve bütün bileşenleri negatif olmadığı için (2) koşullarını da sağlar. Bu nokta bir uygun çözümdür.

Aynı işi bir kez genel olarak yapalım. \(x_3\) ve \(x_4\)’ü serbest bırakıp denklemleri \(x_1\), \(x_2\) için çözelim:

\[ \begin{aligned} x_1 + 2x_2 &= 7 - 3x_3 - 4x_4 \\ 2x_1 + x_2 &= 3 - x_3 - 2x_4 \end{aligned} \]

İkinci denklemi \(2\) ile çarpıp birinciyi çıkarırsak

\[3x_1 = (6 - 2x_3 - 4x_4) - (7 - 3x_3 - 4x_4) = x_3 - 1\]

olur. Birinci denklemi \(2\) ile çarpıp ikinciyi çıkarırsak

\[3x_2 = (14 - 6x_3 - 8x_4) - (3 - x_3 - 2x_4) = 11 - 5x_3 - 6x_4\]

olur. Demek ki (1) sisteminin bütün çözümleri

\[x_1 = \frac{x_3 - 1}{3}, \qquad x_2 = \frac{11 - 5x_3 - 6x_4}{3}\]

biçimindedir; \(x_3\) ve \(x_4\) istenen her değeri alabilir. Bu çözümün uygun olması için dört değişkenin de negatif olmaması gerekir:

\[x_3 \ge 1, \qquad x_4 \ge 0, \qquad 5x_3 + 6x_4 \le 11.\]

Burada \(x_1 \ge 0\) koşulu \(x_3 \ge 1\)’e, \(x_2 \ge 0\) koşulu \(5x_3 + 6x_4 \le 11\)’e dönüştü; \(x_3 \ge 1\) zaten \(x_3 \ge 0\)’ı içerir. Bu üç eşitsizliği sağlayan her \((x_3, x_4)\) seçimi bir uygun çözüm verir. Böyle sonsuz sayıda seçim olduğundan problemin sonsuz sayıda uygun çözümü vardır. Örneğin:

• \(x_3 = 1\), \(x_4 = 0\) için \(X = (0, 2, 1, 0)\) bulunur. Sağlama: \(0 + 4 + 3 + 0 = 7\) ve \(0 + 2 + 1 + 0 = 3\).
• \(x_3 = \tfrac{11}{5}\), \(x_4 = 0\) için \(X = \left(\tfrac{2}{5}, 0, \tfrac{11}{5}, 0\right)\) bulunur. Sağlama: \(\tfrac{2}{5} + \tfrac{33}{5} = 7\) ve \(\tfrac{4}{5} + \tfrac{11}{5} = 3\).

Öte yandan \(x_3 = x_4 = 0\) seçilirse \(X = \left(-\tfrac{1}{3}, \tfrac{11}{3}, 0, 0\right)\) çıkar. Bu nokta (1) denklemlerini sağlar (\(-\tfrac{1}{3} + \tfrac{22}{3} = 7\), \(-\tfrac{2}{3} + \tfrac{11}{3} = 3\)), yani bir çözümdür. Ama \(x_1 < 0\) olduğundan (2) koşulunu sağlamaz ve uygun çözüm değildir.

Bu örnek genel bir durumu gösteriyor: bir lineer programlama probleminin birden fazla, hatta sonsuz sayıda uygun çözümü olabilir.

\(\blacksquare\)

2.2 Temel Çözümler

Önceki örnekte uygun çözümler iki serbest parametreye bağlıydı ve sonsuz sayıdaydı. Bunları tek tek denemek mümkün değildir. İşimize yarayacak özel çözümler, serbest bırakılabilecek değişkenlerin hepsine sıfır verilerek bulunanlardır: \(n\) değişkenden \(n - m\) tanesi sıfır yapılırsa geriye \(m\) bilinmeyenli \(m\) denklem kalır ve bu kare sistemin çoğu zaman tek bir çözümü vardır.

Tanım 2.3 (Temel çözüm)  

1. sistemindeki \(n\) değişken (\(m < n\)) içinden \(n - m\) tanesi keyfi olarak seçilip sıfır yapılsın. Geriye kalan \(m\) değişkenli ve \(m\) denklemli doğrusal denklem sisteminin katsayılar matrisinin determinantı sıfırdan farklıysa, bu sistemin çözümü ile sıfır yapılan değişkenlerin birlikte oluşturduğu vektöre (1) sisteminin bir temel çözümü denir.

Yani bir temel çözüm üç adımda bulunur: \(n - m\) değişkeni sıfırla, kalan \(m \times m\) sistemin determinantına bak, determinant sıfırdan farklıysa sistemi çöz. Determinantı kısaca \(\Delta\) ile göstereceğiz. \(\Delta \ne 0\) olması, kare sistemin tek bir çözümü olmasını garanti eder (bkz. Lineer Cebir, Cramer kuralı). \(\Delta = 0\) ise sistemin ya hiç çözümü yoktur ya da sonsuz çözümü vardır; iki durumda da o seçimden bir temel çözüm elde edilmez.

Kalan \(m\) değişkenin katsayılar matrisi, \(A\)’nın bu değişkenlere ait \(m\) sütunundan oluşur. Lineer programlama problemi bölümündeki vektörel gösterimle, yani \(A\)’nın sütunlarını \(v_1, v_2, \dots, v_n\) ile göstererek söylersek: \(\Delta \ne 0\) olması, seçilen \(m\) sütun vektörünün lineer bağımsız olması demektir (bkz. Lineer Cebir, regülerliğin determinant ölçütü).

Tanım 2.4 (Temel değişken) Bir temel çözümde keyfi olarak seçilip sıfır yapılan \(n - m\) değişkenin dışında kalan \(m\) değişkene temel değişken, sıfır yapılan değişkenlere de temel olmayan (keyfi) değişken denir. Temel değişkenlerin sütun vektörlerine temel (baz) vektörleri, bu vektörlerin oluşturduğu kümeye de o temel çözümün bazı denir.

Yani bir temel çözümde temel olmayan değişkenler tanım gereği sıfırdır; temel değişkenler ise denklemlerden hesaplanır. Temel değişkenlerin değeri çoğunlukla sıfırdan farklıdır, ama sıfır da çıkabilir (bkz. Tanım 2.6). Temel değişkenler bir temel çözümün “kimliğidir”: hangi \(m\) değişkenin temel olduğunu söylemek, o temel çözümü tamamen belirler.

Temel çözümlerin sayısı sonludur; bunun için bir üst sınır verebiliriz.

Önerme 2.1 (Temel çözüm sayısının üst sınırı) \(m < n\) olmak üzere \(m\) denklemli ve \(n\) değişkenli (1) sisteminin en fazla

\[C(n, m) = \binom{n}{m} = \frac{n!}{(n - m)!\,m!}\]

tane temel çözümü vardır.

İspat

Bir temel çözüm, hangi \(n - m\) değişkenin sıfır yapılacağı seçilerek bulunur. Sıfırlanacak \(n - m\) değişkeni seçmek, geri kalan \(m\) temel değişkeni seçmekle aynı şeydir ve \(n\) değişken arasından \(m\) tanesi \(C(n, m)\) farklı biçimde seçilir.

Her seçimde iki durum vardır. \(\Delta = 0\) ise o seçimden temel çözüm çıkmaz. \(\Delta \ne 0\) ise kare sistemin tek bir çözümü vardır ve seçim tam olarak bir temel çözüm verir. Demek ki her seçim en fazla bir temel çözüm verir. Farklı seçimler aynı noktayı da verebilir (bkz. Örnek 2.6); bu yalnız farklı temel çözümlerin sayısını azaltır. Böylece farklı temel çözümlerin sayısı en fazla \(C(n, m)\)’dir.

\(\blacksquare\)

Yani sonsuz sayıdaki çözüm arasında ilgilenmemiz gereken temel çözümler sonlu sayıdadır. Örneğin \(m = 2\), \(n = 4\) için en fazla \(C(4, 2) = \frac{4!}{2!\,2!} = 6\), \(m = 3\), \(n = 5\) için en fazla \(C(5, 3) = 10\) temel çözüm vardır. Ne var ki bu sayı hızla büyür: \(m = 10\), \(n = 20\) için \(C(20, 10) = 184\,756\) olur. Temel çözümleri akıllıca dolaşan bir yönteme bu yüzden ihtiyaç duyacağız (Simpleks yöntem).

Örnek 2.3 (Üç değişkenli bir sistemin temel çözümleri) \[ \begin{aligned} x_1 + x_2 + x_3 &= 4 \\ x_1 - x_2 + 3x_3 &= 2 \end{aligned} \]

sisteminin bütün temel çözümlerini bulunuz.

Çözüm

Burada \(m = 2\) ve \(n = 3\)’tür. Her seferinde \(n - m = 1\) değişken sıfırlanır; en fazla \(C(3, 2) = 3\) temel çözüm vardır. Üç seçimi sırayla deneyelim.

\(x_3 = 0\) seçilsin. Temel değişkenler \(x_1\), \(x_2\) olur:

\[ \begin{cases} x_1 + x_2 = 4 \\ x_1 - x_2 = 2 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 1 \\ 1 & -1 \end{vmatrix} = -2 \ne 0. \]

İki denklemi toplarsak \(2x_1 = 6\), yani \(x_1 = 3\) ve \(x_2 = 1\) bulunur. Temel çözüm \((3, 1, 0)\)’dır.

\(x_2 = 0\) seçilsin. Temel değişkenler \(x_1\), \(x_3\) olur:

\[ \begin{cases} x_1 + x_3 = 4 \\ x_1 + 3x_3 = 2 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 1 \\ 1 & 3 \end{vmatrix} = 2 \ne 0. \]

İkinci denklemden birinciyi çıkarırsak \(2x_3 = -2\), yani \(x_3 = -1\) ve \(x_1 = 5\) bulunur. Temel çözüm \((5, 0, -1)\)’dir.

\(x_1 = 0\) seçilsin. Temel değişkenler \(x_2\), \(x_3\) olur:

\[ \begin{cases} x_2 + x_3 = 4 \\ -x_2 + 3x_3 = 2 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 1 \\ -1 & 3 \end{vmatrix} = 4 \ne 0. \]

İki denklemi toplarsak \(4x_3 = 6\), yani \(x_3 = \tfrac{3}{2}\) ve \(x_2 = \tfrac{5}{2}\) bulunur. Temel çözüm \(\left(0, \tfrac{5}{2}, \tfrac{3}{2}\right)\)’dir.

Üç seçimin üçünde de \(\Delta \ne 0\) olduğu için üst sınıra ulaşıldı: sistemin tam 3 temel çözümü var. İkinci temel çözümde \(x_3 = -1\) negatiftir; bir temel çözümün negatif bileşenleri olabilir. Bu ayrımı şimdi bir tanımla yapacağız.

\(\blacksquare\)

2.3 Uygun Temel Çözümler ve Dejenerelik

Temel çözüm tanımı yalnız (1) denklemlerine bakar, (2) işaret koşullarını hiç kullanmaz. İşaret koşullarını da hesaba katınca asıl ilgilendiğimiz çözümler ortaya çıkar.

Tanım 2.5 (Uygun temel çözüm)  

1. sisteminin temel çözümleri arasından (2) koşullarını da sağlayanların her birine uygun temel çözüm denir.

Yani uygun temel çözüm iki süzgeçten geçen çözümdür: önce temel olmalıdır (\(n - m\) değişken sıfır, kalan sistemin \(\Delta \ne 0\)), sonra uygun olmalıdır (hiçbir bileşeni negatif değil). Uygun temel çözümler hem temel çözümlerin hem de uygun çözümlerin içinde yer alır.

Uygun çözümde bütün \(x_j\) değişkenleri sıfır ya da pozitiftir. Temel çözümde ise değişkenler negatif olabilir. Bir temel çözüm negatif bileşen içermiyorsa uygun temel çözüm adını alır.

Örnek 2.4 (Hangi temel çözümler uygun?) Örnek 2.3 sistemine (\(x_1 + x_2 + x_3 = 4\), \(x_1 - x_2 + 3x_3 = 2\)) \(x_1, x_2, x_3 \ge 0\) koşulları eklensin. Bulunan üç temel çözümden hangileri uygun temel çözümdür?

Çözüm

Üç temel çözümün bileşenlerinin işaretlerine bakalım:

• \((3, 1, 0)\): bileşenlerin hiçbiri negatif değil; uygun temel çözümdür.
• \((5, 0, -1)\): \(x_3 = -1 < 0\); bu bir temel çözümdür ama uygun temel çözüm değildir.
• \(\left(0, \tfrac{5}{2}, \tfrac{3}{2}\right)\): bileşenlerin hiçbiri negatif değil; uygun temel çözümdür.

Sistemin iki uygun temel çözümü vardır.

\(\blacksquare\)

Bir temel çözümde temel olmayan \(n - m\) değişken zorunlu olarak sıfırdır. Bazen temel değişkenlerden biri de sıfır çıkar; bu durumun kendine özgü bir adı vardır.

Tanım 2.6 (Dejenere ve dejenere olmayan uygun temel çözüm) Bir uygun temel çözümdeki temel değişkenlerden bir ya da daha fazlası sıfırsa bu uygun temel çözüme dejenere (yozlaşmış) uygun temel çözüm denir. Temel değişkenlerinin hepsi pozitif olan uygun temel çözüme dejenere olmayan uygun temel çözüm denir.

Yani bir uygun temel çözümde sıfır olan değişkenleri sayarız. Dejenere olmayan uygun temel çözümde tam \(n - m\) değişken sıfır, \(m\) değişken pozitiftir. Dejenere uygun temel çözümde ise temel olmayanlara ek olarak en az bir temel değişken de sıfırdır; sıfır olan değişken sayısı \(n - m\)’den fazladır. Örneğin ısınma örneğindeki (Örnek 2.4) iki uygun temel çözüm de dejenere değildir: \((3, 1, 0)\)’da temel değişkenler \(x_1 = 3\) ve \(x_2 = 1\), \(\left(0, \tfrac{5}{2}, \tfrac{3}{2}\right)\)’de \(x_2 = \tfrac{5}{2}\) ve \(x_3 = \tfrac{3}{2}\)’dir.

Aksi söylenmedikçe bir uygun temel çözümden söz edilirken onun dejenere olmadığı, yani temel değişkenlerinin hiçbirinin sıfır olmadığı varsayılır. Dejenere çözümler karşımıza çıktığında bunu ayrıca belirteceğiz.

Örnek 2.5 (Dejenere bir uygun temel çözüm) \[ \begin{aligned} x_1 + 5x_2 + x_3 &= 5 \\ 3x_1 + 8x_2 + 7x_3 &= 8 \\ x_1, x_2, x_3 &\ge 0 \end{aligned} \]

koşullarını göz önüne alalım. \(x_3\) keyfi değişken seçilerek bulunan temel çözümün dejenere bir uygun temel çözüm olduğunu gösteriniz.

Çözüm

\(m = 2\), \(n = 3\) olduğundan bir değişken sıfırlanır. \(x_3 = 0\) alınca temel değişkenler \(x_1\), \(x_2\) olur:

\[ \begin{cases} x_1 + 5x_2 = 5 \\ 3x_1 + 8x_2 = 8 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 5 \\ 3 & 8 \end{vmatrix} = 8 - 15 = -7 \ne 0. \]

Birinci denklemden \(x_1 = 5 - 5x_2\); ikincide yerine koyarsak \(15 - 15x_2 + 8x_2 = 8\), yani \(7x_2 = 7\) ve \(x_2 = 1\) bulunur. O halde \(x_1 = 0\)’dır ve temel çözüm

\[X = (0, 1, 0)\]

olur. Bütün bileşenler negatif olmadığı için \(X\) bir uygun temel çözümdür. Fakat temel değişkenlerinden biri, \(x_1\), sıfırdır. Dolayısıyla \(X\) dejenere bir uygun temel çözümdür. Sayarak da görebiliriz: \(X\)’te iki değişken sıfırdır, oysa dejenere olmayan bir temel çözümde tam \(n - m = 1\) değişken sıfırdır.

\(\blacksquare\)

Örnek 2.6 (Aynı noktayı veren iki baz) Aynı sistemin (\(x_1 + 5x_2 + x_3 = 5\), \(3x_1 + 8x_2 + 7x_3 = 8\), \(x_1, x_2, x_3 \ge 0\)) diğer iki temel çözümünü bulunuz. Kaç farklı temel çözüm vardır?

Çözüm

Geriye \(x_2 = 0\) ve \(x_1 = 0\) seçimleri kaldı.

\(x_2 = 0\) seçilsin. Temel değişkenler \(x_1\), \(x_3\) olur:

\[ \begin{cases} x_1 + x_3 = 5 \\ 3x_1 + 7x_3 = 8 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 1 \\ 3 & 7 \end{vmatrix} = 4 \ne 0. \]

\(x_1 = 5 - x_3\) yazıp ikincide yerine koyarsak \(15 + 4x_3 = 8\), yani \(x_3 = -\tfrac{7}{4}\) ve \(x_1 = \tfrac{27}{4}\) bulunur. Temel çözüm \(\left(\tfrac{27}{4}, 0, -\tfrac{7}{4}\right)\)’tür; \(x_3 < 0\) olduğu için uygun değildir.

\(x_1 = 0\) seçilsin. Temel değişkenler \(x_2\), \(x_3\) olur:

\[ \begin{cases} 5x_2 + x_3 = 5 \\ 8x_2 + 7x_3 = 8 \end{cases}, \qquad \Delta = \begin{vmatrix} 5 & 1 \\ 8 & 7 \end{vmatrix} = 27 \ne 0. \]

\(x_3 = 5 - 5x_2\) yazıp ikincide yerine koyarsak \(8x_2 + 35 - 35x_2 = 8\), yani \(27x_2 = 27\), \(x_2 = 1\) ve \(x_3 = 0\) bulunur. Temel çözüm yine \((0, 1, 0)\)’dır. Bu kez temel değişken \(x_3\) sıfırdır; çözüm yine dejeneredir.

Böylece üç seçimin üçü de temel çözüm verdi, ama bunlardan ikisi aynı noktadır: sistemin farklı temel çözümleri \((0, 1, 0)\) ve \(\left(\tfrac{27}{4}, 0, -\tfrac{7}{4}\right)\) olmak üzere iki tanedir. Dejenere bir noktada sıfır olan değişken sayısı \(n - m\)’den fazla olduğundan, sıfırlanacak \(n - m\) değişkeni bu sıfırlar arasından birden fazla biçimde seçebiliriz; \(\Delta \ne 0\) olan her seçim aynı noktayı verir. Simpleks yöntemde bu durum, bazın değiştiği halde noktanın yerinde saydığı adımlar olarak karşımıza çıkacak.

\(\blacksquare\)

Örnek 2.7 (Üç doğrunun kesiştiği köşe) \[ \begin{aligned} x_1 + x_2 &\le 2 \\ x_1 &\le 1 \\ x_2 &\le 1 \\ x_1, x_2 &\ge 0 \end{aligned} \]

kısıtlarını standart forma getirip uygun bölgenin \((1, 1)\) köşesine karşılık gelen temel çözümleri bulunuz ve dejenere olduklarını gösteriniz.

Çözüm

x₁ + x₂ ≤ 2, x₁ ≤ 1, x₂ ≤ 1 kısıtlarının uygun bölgesi birim karedir. (1, 1) köşesinden üç kısıt doğrusu birden geçer: bu noktada x₃, x₄, x₅ aylak değişkenlerinin üçü de sıfırdır. Temel çözümde yalnız iki değişken sıfırlandığı için üçüncü sıfır bir temel değişkendir; köşe dejenere bir uygun temel çözümdür.

Önce kısıtları standart forma getirelim. Üç kısıt da \(\le\) biçiminde ve sağ tarafları negatif değil; sırasıyla \(x_3\), \(x_4\), \(x_5\) aylak değişkenlerini ekleriz:

\[ \begin{aligned} x_1 + x_2 + x_3 &= 2 \\ x_1 + x_4 &= 1 \\ x_2 + x_5 &= 1 \\ x_1, x_2, x_3, x_4, x_5 &\ge 0 \end{aligned} \]

Burada \(m = 3\) ve \(n = 5\)’tir; bir temel çözümde \(n - m = 2\) değişken sıfırlanır.

\((1, 1)\) noktasında aylak değişkenler \(x_3 = 2 - 1 - 1 = 0\), \(x_4 = 1 - 1 = 0\), \(x_5 = 1 - 1 = 0\)’dır. Yani bu köşeye karşılık gelen nokta \(X = (1, 1, 0, 0, 0)\)’dır ve üç değişkeni sıfırdır. Bir temel çözüm elde etmek için bu üç sıfırdan ikisini temel olmayan değişken olarak seçebiliriz; üç seçim vardır ve her birinde temel değişkenler \(x_1\), \(x_2\) ile kalan aylak değişkendir:

• \(x_4 = x_5 = 0\) seçilirse temel değişkenler \(x_1, x_2, x_3\) olur ve \[\Delta = \begin{vmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{vmatrix} = 1;\]
• \(x_3 = x_5 = 0\) seçilirse temel değişkenler \(x_1, x_2, x_4\) olur ve \[\Delta = \begin{vmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{vmatrix} = -1;\]
• \(x_3 = x_4 = 0\) seçilirse temel değişkenler \(x_1, x_2, x_5\) olur ve \[\Delta = \begin{vmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{vmatrix} = -1.\]

Üç determinant da sıfırdan farklı, dolayısıyla her seçim bir temel çözüm verir. Örneğin ilk seçimde ikinci denklemden \(x_1 = 1\), üçüncüden \(x_2 = 1\), birinciden \(x_3 = 0\) bulunur. Diğer iki seçim de aynı \(X = (1, 1, 0, 0, 0)\) noktasını verir. Her seçimde temel değişkenlerden biri (sırasıyla \(x_3\), \(x_4\), \(x_5\)) sıfırdır; üç temel çözüm de dejeneredir.

Şekilde durumun geometrisi görülüyor. Düzlemde bir köşe normalde iki kısıt doğrusunun kesişimidir ve orada iki değişken sıfırdır. \((1, 1)\) köşesinden ise üç doğru birden geçer ve orada üç değişken sıfırdır. Bu fazladan sıfır dejenereliği doğurur. Dikkat edilirse \(x_1 + x_2 \le 2\) kısıtı bölgeyi hiç küçültmez; birim kareye yalnız köşesinde değer.

\(\blacksquare\)

2.4 Bütün Temel Çözümleri Hesaplamak

Şimdi daha büyük bir sistemin bütün temel çözümlerini düzenli biçimde bulalım. İşi aşağıdaki reçeteyle yürüteceğiz.

İpucuDört adımda bütün temel çözümleri bulma

1. Sayı: \(m\) ve \(n\)’yi belirle. En fazla \(C(n, m)\) seçim vardır; hiçbirini atlamamak için seçimleri sistemli sırala.
2. Determinant: Her seçimde \(n - m\) değişkeni sıfırla ve kalan \(m \times m\) sistemin \(\Delta\)’sını hesapla. \(\Delta = 0\) ise bu seçimden temel çözüm çıkmaz.
3. Çözüm: \(\Delta \ne 0\) ise kalan sistemi yok etme yöntemiyle ya da Cramer kuralıyla çöz.
4. Sınıflandırma: Negatif bileşen yoksa çözüm uygun temel çözümdür; ayrıca bir temel değişken sıfırsa dejeneredir. Amaç fonksiyonu varsa \(z\) değerini hesapla. Sonuçları bir tabloda topla.

Örnek 2.8 (Dört değişkenli sistemin bütün temel çözümleri) Örnek 2.2 sisteminin

\[ \begin{aligned} x_1 + 2x_2 + 3x_3 + 4x_4 &= 7 \\ 2x_1 + x_2 + x_3 + 2x_4 &= 3 \end{aligned} \]

bütün temel çözümlerini bulunuz.

Çözüm

\(m = 2\), \(n = 4\) ve \(n - m = 2\) olduğundan \(x_1, x_2, x_3, x_4\) değişkenlerinden herhangi ikisi keyfi değişken seçilerek sıfır yapılır. En fazla \(C(4, 2) = 6\) seçim vardır.

a) \(x_3\), \(x_4\) keyfi değişken seçilsin.

\[ x_3 = x_4 = 0 \;\Rightarrow\; \begin{cases} x_1 + 2x_2 = 7 \\ 2x_1 + x_2 = 3 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 2 \\ 2 & 1 \end{vmatrix} = -3 \ne 0. \]

İkinci denklemden \(x_2 = 3 - 2x_1\); birincide yerine koyarsak \(x_1 + 6 - 4x_1 = 7\), yani \(x_1 = -\tfrac{1}{3}\) ve \(x_2 = 3 + \tfrac{2}{3} = \tfrac{11}{3}\) bulunur. O halde

\[X_1 = \left(-\tfrac{1}{3}, \tfrac{11}{3}, 0, 0\right)\]

bir temel çözümdür ve bu temel çözümdeki temel değişkenler \(x_1\), \(x_2\)’dir.

b) \(x_2\), \(x_4\) keyfi değişken seçilsin.

\[ x_2 = x_4 = 0 \;\Rightarrow\; \begin{cases} x_1 + 3x_3 = 7 \\ 2x_1 + x_3 = 3 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 3 \\ 2 & 1 \end{vmatrix} = -5 \ne 0. \]

İkinci denklemden \(x_3 = 3 - 2x_1\); birincide yerine koyarsak \(x_1 + 9 - 6x_1 = 7\), yani \(x_1 = \tfrac{2}{5}\) ve \(x_3 = 3 - \tfrac{4}{5} = \tfrac{11}{5}\) bulunur. O halde

\[X_2 = \left(\tfrac{2}{5}, 0, \tfrac{11}{5}, 0\right)\]

bir temel çözümdür ve temel değişkenler \(x_1\), \(x_3\)’tür.

c) \(x_2\), \(x_3\) keyfi değişken seçilsin.

\[ x_2 = x_3 = 0 \;\Rightarrow\; \begin{cases} x_1 + 4x_4 = 7 \\ 2x_1 + 2x_4 = 3 \end{cases}, \qquad \Delta = \begin{vmatrix} 1 & 4 \\ 2 & 2 \end{vmatrix} = -6 \ne 0. \]

İkinci denklemden \(x_1 = \tfrac{3}{2} - x_4\); birincide yerine koyarsak \(\tfrac{3}{2} + 3x_4 = 7\), yani \(x_4 = \tfrac{11}{6}\) ve \(x_1 = \tfrac{3}{2} - \tfrac{11}{6} = -\tfrac{1}{3}\) bulunur. O halde

\[X_3 = \left(-\tfrac{1}{3}, 0, 0, \tfrac{11}{6}\right)\]

bir temel çözümdür ve temel değişkenler \(x_1\), \(x_4\)’tür.

d) \(x_1\), \(x_4\) keyfi değişken seçilsin.

\[ x_1 = x_4 = 0 \;\Rightarrow\; \begin{cases} 2x_2 + 3x_3 = 7 \\ x_2 + x_3 = 3 \end{cases}, \qquad \Delta = \begin{vmatrix} 2 & 3 \\ 1 & 1 \end{vmatrix} = -1 \ne 0. \]

İkinci denklemden \(x_2 = 3 - x_3\); birincide yerine koyarsak \(6 + x_3 = 7\), yani \(x_3 = 1\) ve \(x_2 = 2\) bulunur. O halde

\[X_4 = (0, 2, 1, 0)\]

bir temel çözümdür ve temel değişkenler \(x_2\), \(x_3\)’tür.

e) \(x_1\), \(x_3\) keyfi değişken seçilsin.

\[ x_1 = x_3 = 0 \;\Rightarrow\; \begin{cases} 2x_2 + 4x_4 = 7 \\ x_2 + 2x_4 = 3 \end{cases}, \qquad \Delta = \begin{vmatrix} 2 & 4 \\ 1 & 2 \end{vmatrix} = 0. \]

Determinant sıfır olduğundan bu seçimden bir temel çözüme ulaşılmaz. Gerçekten ikinci denklemi \(2\) ile çarparsak \(2x_2 + 4x_4 = 6\) çıkar; bu, birinci denklemle çelişir. Sistemin hiç çözümü yoktur.

f) \(x_1\), \(x_2\) keyfi değişken seçilsin.

\[ x_1 = x_2 = 0 \;\Rightarrow\; \begin{cases} 3x_3 + 4x_4 = 7 \\ x_3 + 2x_4 = 3 \end{cases}, \qquad \Delta = \begin{vmatrix} 3 & 4 \\ 1 & 2 \end{vmatrix} = 2 \ne 0. \]

İkinci denklemden \(x_3 = 3 - 2x_4\); birincide yerine koyarsak \(9 - 2x_4 = 7\), yani \(x_4 = 1\) ve \(x_3 = 1\) bulunur. O halde

\[X_5 = (0, 0, 1, 1)\]

bir temel çözümdür ve bu temel çözümdeki temel değişkenler \(x_3\) ve \(x_4\)’tür.

Bu örnekte \(n = 4\) ve \(m = 2\) olduğundan en fazla 6 temel çözüm elde edilebilirdi. e) seçiminde determinant sıfır çıktığı için bu sistemin 5 temel çözümü vardır.

\(\blacksquare\)

Örnek 2.9 (Dört değişkenli sistemin uygun temel çözümleri) Aynı sisteme (\(x_1 + 2x_2 + 3x_3 + 4x_4 = 7\), \(2x_1 + x_2 + x_3 + 2x_4 = 3\)) \(x_1, x_2, x_3, x_4 \ge 0\) koşulları eklensin. Uygun temel çözümleri belirleyiniz. Bunlardan dejenere olan var mıdır?

Çözüm

Önceki örnekte (Örnek 2.8) bulunan beş temel çözümün işaretlerine sırayla bakalım.

• \(X_1 = \left(-\tfrac{1}{3}, \tfrac{11}{3}, 0, 0\right)\) temel çözümü (2) koşullarını sağlamadığından bir uygun temel çözüm değildir.
• \(X_2 = \left(\tfrac{2}{5}, 0, \tfrac{11}{5}, 0\right)\) temel çözümü (2) koşullarını sağladığından bir uygun temel çözümdür.
• \(X_3 = \left(-\tfrac{1}{3}, 0, 0, \tfrac{11}{6}\right)\) temel çözümü (2) koşullarını sağlamadığından bir uygun temel çözüm değildir.
• \(X_4 = (0, 2, 1, 0)\) temel çözümü (2) koşullarını sağladığından bir uygun temel çözümdür.
• \(X_5 = (0, 0, 1, 1)\) temel çözümü (2) koşullarını sağladığından bir uygun temel çözümdür.

Demek ki \(X_2\), \(X_4\) ve \(X_5\) noktaları birer uygun temel çözümdür. Bu noktalarda temel değişkenler sıfırdan farklıdır (\(X_2\)’de \(x_1 = \tfrac{2}{5}\), \(x_3 = \tfrac{11}{5}\); \(X_4\)’te \(x_2 = 2\), \(x_3 = 1\); \(X_5\)’te \(x_3 = x_4 = 1\)). Bu yüzden üçü de dejenere olmayan uygun temel çözümlerdir.

Bütün hesabı aşağıdaki tabloda (Tablo 2.1) toplayalım. Dejenerelik yalnız uygun temel çözümler için tanımlandığından uygun olmayan satırlarda o sütun boş bırakılmıştır.

Tablo 2.1: Dört değişkenli sistemin bütün temel çözümleri

Seçim	Sıfırlanan	Temel değişkenler	\(\Delta\)	Temel çözüm	Uygun mu?	Dejenere mi?
a)	\(x_3, x_4\)	\(x_1, x_2\)	\(-3\)	\(X_1 = \left(-\frac{1}{3}, \frac{11}{3}, 0, 0\right)\)	Hayır (\(x_1 < 0\))	\(-\)
b)	\(x_2, x_4\)	\(x_1, x_3\)	\(-5\)	\(X_2 = \left(\frac{2}{5}, 0, \frac{11}{5}, 0\right)\)	Evet	Hayır
c)	\(x_2, x_3\)	\(x_1, x_4\)	\(-6\)	\(X_3 = \left(-\frac{1}{3}, 0, 0, \frac{11}{6}\right)\)	Hayır (\(x_1 < 0\))	\(-\)
d)	\(x_1, x_4\)	\(x_2, x_3\)	\(-1\)	\(X_4 = (0, 2, 1, 0)\)	Evet	Hayır
e)	\(x_1, x_3\)	\(x_2, x_4\)	\(0\)	yok	\(-\)	\(-\)
f)	\(x_1, x_2\)	\(x_3, x_4\)	\(2\)	\(X_5 = (0, 0, 1, 1)\)	Evet	Hayır

\(\blacksquare\)

2.5 Optimal Çözüm

Şimdiye kadar amaç fonksiyonunu hiç kullanmadık. Problemin asıl sorusu ise uygun çözümler arasından amaç fonksiyonunu en iyi yapanı bulmaktır.

Tanım 2.7 (Optimal çözüm) \(X^{*}\) bir uygun çözüm olsun. Her uygun çözüm \(X\) için minimum probleminde \(z(X^{*}) \le z(X)\), maksimum probleminde \(z(X^{*}) \ge z(X)\) oluyorsa \(X^{*}\)’a problemin bir optimal çözümü, \(z^{*} = z(X^{*})\) sayısına da optimal değer denir.

Yani optimal çözüm hem uygun olmalı hem de hiçbir uygun çözüm ondan daha iyi olmamalıdır. Uygun olmayan bir noktanın amaç değeri ne kadar iyi olursa olsun aday değildir. Optimal çözüm tek olmayabilir; bir problemin hiç optimal çözümü de olmayabilir. Örneğin uygun çözüm hiç yoksa ya da amaç fonksiyonu uygun çözümler üzerinde maksimumda sınırsız büyüyebiliyor, minimumda sınırsız küçülebiliyorsa optimal çözüm yoktur. Bu durumları Sınırsız çözüm ve alternatif optimal çözüm bölümünde inceleyeceğiz.

Uç noktalar ve grafik yöntem bölümünde önemli bir gerçeği ispatlayacağız: optimal çözüm varsa uygun temel çözümlerden en az biri optimaldir. O halde optimumu ararken sonlu sayıdaki uygun temel çözümleri karşılaştırmak yeter. Aşağıdaki örnekte bu fikri önceden deneyelim ve bulduğumuz noktanın gerçekten optimal olduğunu ayrıca doğrulayalım.

Örnek 2.10 (Aylak değişkenli bir problemin bütün temel çözümleri) \[ \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} \]

problemini standart forma getirip bütün temel çözümlerini bulunuz ve uygun temel çözümler arasından optimal çözümü seçiniz.

Çözüm

Uygun bölge boyalı dörtgendir. Her kısıt doğrusu üzerinde bir değişken sıfırdır (eksenlerde x₁ = 0 ya da x₂ = 0); iki doğrunun her kesişimi, o iki değişken sıfırlanarak bulunan bir temel çözümdür. Dolu noktalar O, A, B, C uygun temel çözümlerdir ve bölgenin köşeleridir; boş noktalar D(0, 4) ve E(6, 0) uygun olmayan temel çözümlerdir ve bölgenin dışında kalır. Kesikli z = 9 doğrusu bölgeye yalnız B(3, 1) köşesinde değer.

Standart form. İki kısıt da \(\le\) biçiminde ve sağ tarafları negatif değil. Birinci kısıta \(x_3\), ikinciye \(x_4\) aylak değişkenini ekleriz; amaçtaki katsayıları \(0\)’dır:

\[ \begin{aligned} x_1 + x_2 + x_3 &= 4 \\ x_1 + 3x_2 + x_4 &= 6 \\ x_1, x_2, x_3, x_4 &\ge 0 \\ \max z &= 2x_1 + 3x_2 + 0x_3 + 0x_4 \end{aligned} \]

Artık \(m = 2\), \(n = 4\)’tür; en fazla \(C(4, 2) = 6\) temel çözüm vardır.

Temel çözümler. Her seçimde iki değişkeni sıfırlayıp kalan \(2 \times 2\) sistemi çözelim.

• \(x_1 = x_2 = 0\) (\(x_3\), \(x_4\) temel): denklemler doğrudan \(x_3 = 4\), \(x_4 = 6\) verir; \(\Delta = 1 \cdot 1 - 0 \cdot 0 = 1\). Çözüm \((0, 0, 4, 6)\).
• \(x_1 = x_3 = 0\) (\(x_2\), \(x_4\) temel): \(x_2 = 4\) ve \(3x_2 + x_4 = 6\); \(\Delta = 1 \cdot 1 - 0 \cdot 3 = 1\). \(x_4 = 6 - 12 = -6\) ve çözüm \((0, 4, 0, -6)\).
• \(x_1 = x_4 = 0\) (\(x_2\), \(x_3\) temel): \(x_2 + x_3 = 4\) ve \(3x_2 = 6\); \(\Delta = 1 \cdot 0 - 1 \cdot 3 = -3\). \(x_2 = 2\), \(x_3 = 2\) ve çözüm \((0, 2, 2, 0)\).
• \(x_2 = x_3 = 0\) (\(x_1\), \(x_4\) temel): \(x_1 = 4\) ve \(x_1 + x_4 = 6\); \(\Delta = 1 \cdot 1 - 0 \cdot 1 = 1\). \(x_4 = 2\) ve çözüm \((4, 0, 0, 2)\).
• \(x_2 = x_4 = 0\) (\(x_1\), \(x_3\) temel): \(x_1 + x_3 = 4\) ve \(x_1 = 6\); \(\Delta = 1 \cdot 0 - 1 \cdot 1 = -1\). \(x_3 = -2\) ve çözüm \((6, 0, -2, 0)\).
• \(x_3 = x_4 = 0\) (\(x_1\), \(x_2\) temel): \(x_1 + x_2 = 4\) ve \(x_1 + 3x_2 = 6\); \(\Delta = 3 - 1 = 2\). İkinciden birinciyi çıkarırsak \(2x_2 = 2\), yani \(x_2 = 1\), \(x_1 = 3\) ve çözüm \((3, 1, 0, 0)\).

Altı seçimin hepsinde \(\Delta \ne 0\) olduğundan tam 6 temel çözüm vardır. Geometrik yorumda kullanmak için bunları \(x_1x_2\) düzlemindeki izdüşümlerine göre \(O\), \(D\), \(C\), \(A\), \(E\), \(B\) diye adlandıralım ve tabloda (Tablo 2.2) toplayalım. \(z\) sütununu uygun olmayan satırlar için de hesapladık; bunun nedeni birazdan anlaşılacak.

Tablo 2.2: Aylak değişkenli problemin bütün temel çözümleri

Nokta	Sıfırlanan	Temel değişkenler	\(\Delta\)	Temel çözüm	Uygun mu?	Dejenere mi?	\(z\)
\(O\)	\(x_1, x_2\)	\(x_3, x_4\)	\(1\)	\((0, 0, 4, 6)\)	Evet	Hayır	\(0\)
\(D\)	\(x_1, x_3\)	\(x_2, x_4\)	\(1\)	\((0, 4, 0, -6)\)	Hayır (\(x_4 < 0\))	\(-\)	\(12\)
\(C\)	\(x_1, x_4\)	\(x_2, x_3\)	\(-3\)	\((0, 2, 2, 0)\)	Evet	Hayır	\(6\)
\(A\)	\(x_2, x_3\)	\(x_1, x_4\)	\(1\)	\((4, 0, 0, 2)\)	Evet	Hayır	\(8\)
\(E\)	\(x_2, x_4\)	\(x_1, x_3\)	\(-1\)	\((6, 0, -2, 0)\)	Hayır (\(x_3 < 0\))	\(-\)	\(12\)
\(B\)	\(x_3, x_4\)	\(x_1, x_2\)	\(2\)	\((3, 1, 0, 0)\)	Evet	Hayır	\(9\)

Optimumun seçimi. Uygun temel çözümler \(O\), \(C\), \(A\), \(B\)’dir ve amaç değerleri sırasıyla \(0\), \(6\), \(8\), \(9\)’dur. En büyüğü \(B = (3, 1, 0, 0)\) noktasındaki \(z = 9\)’dur. Uygun olmayan \(D\) ve \(E\)’nin \(z\) değeri \(12\) ile daha büyüktür, ama bu noktalar kısıtları ihlal ettiği için aday değildir. Örneğin \(D\)’de \(x_4 = -6\)’dır, yani ikinci kısıtın sol tarafı \(0 + 3 \cdot 4 = 12\) olur ve \(6\)’yı aşar.

\(B\) gerçekten optimal mi? Bunu doğrudan gösterebiliriz. Amaç fonksiyonunu iki kısıtın sol taraflarının negatif olmayan katsayılarla alınmış bir toplamı olarak yazalım:

\[2x_1 + 3x_2 = \tfrac{3}{2}(x_1 + x_2) + \tfrac{1}{2}(x_1 + 3x_2).\]

Sağ tarafı açarsak gerçekten

\[\tfrac{3}{2}x_1 + \tfrac{3}{2}x_2 + \tfrac{1}{2}x_1 + \tfrac{3}{2}x_2 = 2x_1 + 3x_2\]

olur. Her uygun çözümde \(x_1 + x_2 \le 4\) ve \(x_1 + 3x_2 \le 6\) olduğundan

\[z = \tfrac{3}{2}(x_1 + x_2) + \tfrac{1}{2}(x_1 + 3x_2) \le \tfrac{3}{2} \cdot 4 + \tfrac{1}{2} \cdot 6 = 9\]

bulunur. \(B\)’de \(z = 9\) olduğuna göre hiçbir uygun çözüm \(B\)’den iyi değildir. Optimal çözüm \(x_1 = 3\), \(x_2 = 1\) (ve \(x_3 = x_4 = 0\)), optimal değer \(z^{*} = 9\)’dur. Bu katsayıların nasıl bulunduğu Dualite bölümünün konusudur.

Geometrik yorum. Çözümün başındaki şekil tablonun geometrisini gösteriyor. \(x_1 = 0\) ve \(x_2 = 0\) eksenleri ile iki kısıt doğrusu (\(x_3 = 0\) ve \(x_4 = 0\)) düzlemde dört doğrudur. Bir temel çözüm iki değişkeni sıfırladığına göre, bu dört doğrudan ikisinin kesişim noktasıdır; dört doğrudan \(C(4, 2) = 6\) çift seçilir ve her çift bir temel çözüm verir. Uygun temel çözümler \(O\), \(A\), \(B\), \(C\) uygun bölgenin tam olarak dört köşesidir. Uygun olmayan \(D\) ve \(E\) ise kısıt doğrularının eksenleri bölgenin dışında kestiği noktalardır.

Köşelerle uygun temel çözümler arasındaki bu bağ bir rastlantı değildir. Onu bir sonraki bölümde genel olarak ispatlayacağız.

\(\blacksquare\)

2.6 Konveks Kümeler

Önceki örnekte uygun temel çözümlerin uygun bölgenin köşeleri olduğunu gördük. “Köşe” kavramını her boyutta kullanabilmek ve uygun bölgenin biçimini anlamak için lineer programlamanın çözümünde kullanılan birkaç geometrik kavrama ihtiyacımız var. Bu kavramlar Konveks Analiz dersinde ayrıntılı işlenir; burada lineer programlamada kullanacağımız kadarını kısaca veriyoruz.

Konveks kombinasyon ve doğru parçası

İlk kavram, birkaç noktanın “ağırlıklı ortalaması”dır.

Tanım 2.8 (Konveks kombinasyon) \(A_1, A_2, \dots, A_k\) noktaları (ya da vektörleri) ve

\[\lambda_i \ge 0, \quad i = \overline{1,k}, \qquad \sum_{i=1}^{k} \lambda_i = 1\]

koşullarını sağlayan \(\lambda_1, \lambda_2, \dots, \lambda_k\) sayıları verilsin. Bu koşullar altında oluşturulan

\[A = \lambda_1A_1 + \lambda_2A_2 + \dots + \lambda_kA_k\]

noktasına (vektörüne) \(A_1, A_2, \dots, A_k\) noktalarının (vektörlerinin) bir konveks kombinasyonu denir.

Yani konveks kombinasyon, noktaların ağırlıklı ortalamasıdır: ağırlıklar negatif değildir ve toplamları \(1\)’dir. İki nokta için \(\lambda_1 = \lambda\), \(\lambda_2 = 1 - \lambda\) (\(0 \le \lambda \le 1\)) yazılır ve kombinasyon \(\lambda A_1 + (1 - \lambda)A_2\) olur. Daha ayrıntılı bir anlatım için bkz. Konveks Analiz.

Örnek 2.11 (Bir noktayı konveks kombinasyon olarak yazmak) \(A_1 = (0, 0)\), \(A_2 = (4, 0)\), \(A_3 = (0, 4)\) olsun. \(A = (1, 1)\) noktasını bu üç noktanın bir konveks kombinasyonu olarak yazınız.

Çözüm

\(\lambda_1 A_1 + \lambda_2 A_2 + \lambda_3 A_3 = (4\lambda_2, 4\lambda_3)\) olduğundan \((1, 1)\) noktasını elde etmek için \(4\lambda_2 = 1\) ve \(4\lambda_3 = 1\), yani \(\lambda_2 = \lambda_3 = \tfrac{1}{4}\) olmalıdır. Katsayıların toplamı \(1\) olacağından \(\lambda_1 = 1 - \tfrac{1}{4} - \tfrac{1}{4} = \tfrac{1}{2}\) bulunur. Üç katsayı da negatif olmadığından

\[A = \tfrac{1}{2}A_1 + \tfrac{1}{4}A_2 + \tfrac{1}{4}A_3\]

bir konveks kombinasyondur. Aynı yolu \((3, 3)\) noktası için izlersek \(\lambda_2 = \lambda_3 = \tfrac{3}{4}\) ve \(\lambda_1 = -\tfrac{1}{2} < 0\) çıkar. \((3, 3)\) bu üç noktanın konveks kombinasyonu değildir; gerçekten de \(A_1A_2A_3\) üçgeninin dışındadır (\(3 + 3 > 4\)).

\(\blacksquare\)

İki noktanın bütün konveks kombinasyonları, düzlemde ve uzayda bildiğimiz doğru parçasını verir. Bu gözlem doğru parçasını her boyutta tanımlamamızı sağlar.

Tanım 2.9 (Doğru parçası) \(n\) boyutlu uzayda \(A = (a_1, a_2, \dots, a_n)\) ve \(B = (b_1, b_2, \dots, b_n)\) noktalarının konveks kombinasyonu olan

\[X = (x_1, x_2, \dots, x_n) = \lambda A + (1 - \lambda)B, \qquad 0 \le \lambda \le 1\]

noktalarının kümesine \(AB\) doğru parçası denir.

Yani \(X\) noktasının her \(x_i\) bileşeni

\[x_i = \lambda a_i + (1 - \lambda)b_i, \qquad i = \overline{1,n}\]

biçimindedir: \(X\)’in her bileşeni, \(A\) ve \(B\)’nin karşılık gelen \(a_i\) ve \(b_i\) bileşenlerinin, bütün bileşenler için aynı \(\lambda\) ile alınmış konveks kombinasyonudur. \(\lambda = 1\) için \(A\), \(\lambda = 0\) için \(B\), \(\lambda = \tfrac{1}{2}\) için orta nokta elde edilir. \(A \ne B\) ise doğru parçasının her noktası için bu \(\lambda\) tektir. \(\lambda\) sayısı \([0, 1]\) aralığının dışına çıkarsa aynı doğrunun parçanın dışında kalan noktaları elde edilir.

Örnek 2.12 (Bir nokta doğru parçası üzerinde mi?) \(A = (1, 2, 0)\) ve \(B = (3, 0, 4)\) olsun. \(C = (2, 1, 2)\) ve \(D = (5, -2, 8)\) noktalarından hangileri \(AB\) doğru parçası üzerindedir?

Çözüm

Doğru parçasının noktaları

\[X = \lambda(1, 2, 0) + (1 - \lambda)(3, 0, 4) = (3 - 2\lambda,\ 2\lambda,\ 4 - 4\lambda)\]

biçimindedir. Bir nokta üç bileşeni de aynı \(\lambda\) ile veriyorsa ve bu \(\lambda\) \([0, 1]\) aralığındaysa doğru parçası üzerindedir.

\(C = (2, 1, 2)\): Birinci bileşenden \(3 - 2\lambda = 2\), yani \(\lambda = \tfrac{1}{2}\). Bu değerle ikinci bileşen \(2 \cdot \tfrac{1}{2} = 1\), üçüncü bileşen \(4 - 2 = 2\) olur; ikisi de tutar. \(\lambda = \tfrac{1}{2} \in [0, 1]\) olduğundan \(C\) doğru parçası üzerindedir; üstelik \(AB\)’nin orta noktasıdır.

\(D = (5, -2, 8)\): Birinci bileşenden \(3 - 2\lambda = 5\), yani \(\lambda = -1\). Bu değerle ikinci bileşen \(-2\), üçüncü bileşen \(4 + 4 = 8\) olur; üçü de tutar. Demek ki \(D\), \(A\) ile \(B\)’den geçen doğru üzerindedir. Ama \(\lambda = -1 \notin [0, 1]\) olduğundan \(D\) doğru parçası üzerinde değildir. Gerçekten \(B\), \(A\) ile \(D\)’nin orta noktasıdır: \(\tfrac{1}{2}(A + D) = (3, 0, 4) = B\). Yani \(D\), doğru parçasının \(B\) ucunun ötesindedir.

\(\blacksquare\)

Konveks küme

Artık bu bölümün ana kavramını tanımlayabiliriz.

Tanım 2.10 (Konveks küme) \(n\) boyutlu Öklid uzayının bir \(C\) alt kümesi verilsin. \(C\)’nin her nokta çiftinin her konveks kombinasyonu yine \(C\)’de ise, yani her \(A, B \in C\) ve her \(0 \le \lambda \le 1\) için

\[\lambda A + (1 - \lambda)B \in C\]

oluyorsa \(C\)’ye konveks küme (konveks bölge) denir. Eşdeğer olarak: \(C\)’deki her \(A\), \(B\) nokta çifti için \(AB\) doğru parçasının her \(X\) noktası yine \(C\)’ye aitse \(C\) konveks kümedir.

Yani konveks küme, herhangi iki noktasını birleştiren doğru parçasından hiç dışarı taşmayan kümedir. İki tanım aynı şeyi söyler, çünkü \(AB\) doğru parçası tam olarak \(A\) ile \(B\)’nin konveks kombinasyonlarından oluşur. Boş küme ve tek noktalı kümeler de konvekstir, çünkü koşulu bozacak iki farklı nokta yoktur. Karşılaştırma için bkz. Konveks Analiz.

Soldaki çokgen ve ortadaki elips konvekstir: içlerinden hangi iki nokta alınırsa alınsın, UV doğru parçası kümenin içinde kalır. Sağdaki L biçimli küme konveks değildir: U ve V kümededir ama UV doğru parçasının bir kısmı kümenin dışından geçer.

Örnek 2.13 (Dairesel bölge konvekstir) \(\|(x_1, x_2)\| = \sqrt{x_1^2 + x_2^2}\) olmak üzere \(C = \{(x_1, x_2) : x_1^2 + x_2^2 \le 1\}\), yani \(\|X\| \le 1\) koşulunu sağlayan noktaların kümesi verilsin. \(C\)’nin konveks olduğunu gösteriniz.

Çözüm

\(U, V \in C\) ve \(0 \le \lambda \le 1\) alalım; \(W = \lambda U + (1 - \lambda)V\) noktasının \(C\)’de olduğunu göstereceğiz. Üçgen eşitsizliğine göre iki vektörün toplamının uzunluğu uzunluklarının toplamını aşmaz: \(\|P + Q\| \le \|P\| + \|Q\|\). Ayrıca bir vektörü negatif olmayan bir \(t\) sayısıyla çarpmak uzunluğunu \(t\) ile çarpar: \(\|tP\| = t\|P\|\). Bu iki bilgiyle

\[\|W\| \le \|\lambda U\| + \|(1 - \lambda)V\| = \lambda\|U\| + (1 - \lambda)\|V\| \le \lambda + (1 - \lambda) = 1\]

bulunur. Son adımda \(\|U\| \le 1\), \(\|V\| \le 1\) ve \(\lambda \ge 0\), \(1 - \lambda \ge 0\) olduğunu kullandık. Demek ki \(W \in C\)’dir ve \(C\) konvekstir.

\(\blacksquare\)

Örnek 2.14 (Koordinat eksenlerinin birleşimi) \(C = \{(x_1, x_2) : x_1x_2 = 0\}\) kümesi, yani iki koordinat ekseninin birleşimi konveks midir?

Çözüm

\(U = (1, 0)\) ve \(V = (0, 1)\) noktaları \(C\)’dedir, çünkü \(1 \cdot 0 = 0\) ve \(0 \cdot 1 = 0\)’dır. \(\lambda = \tfrac{1}{2}\) ile konveks kombinasyonları

\[\tfrac{1}{2}U + \tfrac{1}{2}V = \left(\tfrac{1}{2}, \tfrac{1}{2}\right)\]

olur ve \(\tfrac{1}{2} \cdot \tfrac{1}{2} = \tfrac{1}{4} \ne 0\) olduğundan bu nokta \(C\)’de değildir. \(C\) konveks değildir.

Bir kümenin konveks olmadığını göstermek için tek bir karşı örnek yeter. Konveks olduğunu göstermek için ise bütün nokta çiftleri ve bütün \(\lambda\) değerleri için akıl yürütmek gerekir, önceki örnekte (Örnek 2.13) yaptığımız gibi.

\(\blacksquare\)

Hiperdüzlemler ve yarı uzaylar

Bir lineer programlama probleminin her kısıtı doğrusal bir eşitlik ya da eşitsizliktir. Bu tür denklem ve eşitsizliklerin tanımladığı kümelerin özel adları vardır.

Tanım 2.11 (Hiperdüzlem ve yarı uzaylar) \(a_1, a_2, \dots, a_n\) hepsi birden sıfır olmayan sabitler ve \(b\) bir sabit olsun. \(n\) boyutlu uzayda

\[a_1x_1 + a_2x_2 + \dots + a_nx_n = b\]

denklemini sağlayan noktaların kümesine bir hiperdüzlem denir. Bu hiperdüzlem uzayı ikiye böler:

\[a_1x_1 + a_2x_2 + \dots + a_nx_n \ge b\]

eşitsizliği üst yarı uzayı (üst yarı hiperdüzlemi),

\[a_1x_1 + a_2x_2 + \dots + a_nx_n \le b\]

eşitsizliği ise alt yarı uzayı (alt yarı hiperdüzlemi) ifade eder.

Yani \(n = 2\) iken hiperdüzlem bir doğru, yarı uzaylar da onun iki yanındaki yarı düzlemlerdir; \(n = 3\) iken hiperdüzlem bir düzlemdir; \(n > 3\) iken gözümüzde canlandıramadığımız ama aynı biçimde davranan bir “düzlem”dir. Bir lineer programlama probleminde her eşitlik kısıtı bir hiperdüzlem, her \(\le\) ya da \(\ge\) kısıtı ve her \(x_j \ge 0\) koşulu bir yarı uzay tanımlar. Ayrıntılar için bkz. Konveks Analiz, hiperdüzlem ve yarı uzaylar.

Önerme 2.2 (Hiperdüzlemler ve yarı uzaylar konvekstir) Her hiperdüzlem ve her yarı uzay konveks bir kümedir.

İspat

Kısaca \(\vec{a} = (a_1, \dots, a_n)\) yazalım; bir \(X = (x_1, \dots, x_n)\) noktası için \(\vec{a}^{\,T}X = a_1x_1 + \dots + a_nx_n\) olsun. Bu ifade doğrusaldır: her \(U\), \(V\) ve her \(\lambda\) için

\[\vec{a}^{\,T}\big(\lambda U + (1 - \lambda)V\big) = \lambda\,\vec{a}^{\,T}U + (1 - \lambda)\,\vec{a}^{\,T}V.\]

Alt yarı uzay. \(\vec{a}^{\,T}U \le b\), \(\vec{a}^{\,T}V \le b\) ve \(0 \le \lambda \le 1\) olsun. \(\lambda \ge 0\) ve \(1 - \lambda \ge 0\) olduğundan eşitsizlikleri bu sayılarla çarpabiliriz:

\[\vec{a}^{\,T}\big(\lambda U + (1 - \lambda)V\big) = \lambda\,\vec{a}^{\,T}U + (1 - \lambda)\,\vec{a}^{\,T}V \le \lambda b + (1 - \lambda)b = b.\]

Yani \(\lambda U + (1 - \lambda)V\) de alt yarı uzaydadır.

Üst yarı uzay. Aynı hesap bütün eşitsizlikler ters çevrilerek yapılır: \(\ge b\) olan iki değerin negatif olmayan ağırlıklı ortalaması da \(\ge b\)’dir.

Hiperdüzlem. \(\vec{a}^{\,T}U = \vec{a}^{\,T}V = b\) ise hesap \(\lambda b + (1 - \lambda)b = b\) verir. Ayrıca hiperdüzlem, iki yarı uzayın kesişimi olarak da düşünülebilir.

\(\blacksquare\)

Konveks kümelerin özellikleri

Konveks kümelerin lineer programlamada sürekli kullanacağımız üç özelliği var. İlki, konveks kombinasyon koşulunun iki noktadan çok noktaya genişletilebilmesidir.

Önerme 2.3 (Konveks küme noktalarının konveks kombinasyonlarını içerir) \(A_1, A_2, \dots, A_k\) noktaları \(C\) konveks kümesine ait ise, bunların her konveks kombinasyonu olan

\[A = \sum_{i=1}^{k} \lambda_i A_i, \qquad \lambda_i \ge 0, \ i = \overline{1,k}, \qquad \sum_{i=1}^{k} \lambda_i = 1\]

noktası da \(C\) kümesindedir.

İspat

Nokta sayısı \(k\) üzerinden tümevarım yapalım.

\(k = 1\) ve \(k = 2\). \(k = 1\) için \(\lambda_1 = 1\) ve \(A = A_1 \in C\)’dir. \(k = 2\) için \(A = \lambda A_1 + (1 - \lambda)A_2\) olur; \(C\) konveks olduğundan tanım gereği \(A \in C\)’dir.

Tümevarım adımı. Özelliğin \(k - 1\) nokta için doğru olduğunu kabul edelim: \(C\)’ye ait \(k - 1\) noktanın her konveks kombinasyonu \(C\)’dedir. Şimdi \(A_1, \dots, A_k \in C\) ve \(A = \sum_{i=1}^{k} \lambda_i A_i\) bir konveks kombinasyon olsun.

\(\lambda_k = 1\) ise diğer bütün katsayılar sıfırdır ve \(A = A_k \in C\) olur. \(\lambda_k < 1\) ise

\[t = \lambda_1 + \lambda_2 + \dots + \lambda_{k-1} = 1 - \lambda_k > 0\]

diyelim ve \(\alpha_i = \lambda_i / t\) (\(i = \overline{1,k-1}\)) tanımlayalım. \(\alpha_i \ge 0\) ve

\[\sum_{i=1}^{k-1} \alpha_i = \sum_{i=1}^{k-1} \frac{\lambda_i}{t} = \frac{t}{t} = 1\]

olduğundan

\[B = \sum_{i=1}^{k-1} \alpha_i A_i\]

noktası \(A_1, \dots, A_{k-1}\) noktalarının bir konveks kombinasyonudur ve tümevarım varsayımından \(B \in C\)’dir. \(\lambda_i = t\alpha_i\) olduğunu kullanırsak

\[A = \sum_{i=1}^{k-1} \lambda_i A_i + \lambda_k A_k = t\sum_{i=1}^{k-1} \alpha_i A_i + \lambda_k A_k = tB + \lambda_k A_k\]

olur. Burada \(t > 0\), \(\lambda_k \ge 0\) ve \(t + \lambda_k = 1\)’dir; yani \(A\), \(B\) ile \(A_k\)’nın bir konveks kombinasyonudur. \(B\) ve \(A_k\) noktaları \(C\) konveks kümesinde olduğundan onların konveks kombinasyonu olan \(A\) da \(C\)’dedir.

\(\blacksquare\)

Yani konveks bir kümeden istediğimiz kadar nokta alıp ağırlıklı ortalamalarını alsak da kümenin dışına çıkamayız. Aynı sonucun bir başka ispatı için bkz. Konveks Analiz.

İkinci özellik, konveks kümelerin kesişim ve birleşim altında nasıl davrandığıyla ilgilidir.

Önerme 2.4 (Kesişim ve birleşim) İki konveks kümenin kesişimi yine konvekstir. İki konveks kümenin birleşiminin ise her zaman konveks olması gerekmez.

İki dairesel bölge konvekstir. Solda kesişimleri (koyu boyalı mercek) yine konvekstir. Sağda birleşimleri konveks değildir: U birinci, V ikinci bölgededir, ama UV doğru parçasının ortası iki bölgenin de dışında kalır.

İspat

Kesişim. \(C_1\) ve \(C_2\) konveks kümeler olsun. \(A, B \in C_1 \cap C_2\) ve \(0 \le \lambda \le 1\) alalım. \(A\) ve \(B\) hem \(C_1\)’de hem \(C_2\)’de olduğundan, iki kümenin konveksliği gereği \(\lambda A + (1 - \lambda)B\) noktası hem \(C_1\)’de hem \(C_2\)’dedir; yani \(C_1 \cap C_2\)’dedir. Demek ki kesişim konvekstir.

Birleşim. Bir karşı örnek yeter. \(C_1 = \{(x_1, x_2) : x_2 = 0\}\) (\(x_1\) ekseni) ve \(C_2 = \{(x_1, x_2) : x_1 = 0\}\) (\(x_2\) ekseni) birer doğrudur, yani düzlemde hiperdüzlemdir; Önerme 2.2 gereği ikisi de konvekstir. Birleşimleri ise \(\{(x_1, x_2) : x_1x_2 = 0\}\) kümesidir ve Örnek 2.14 bu kümenin konveks olmadığını gösterdi.

\(\blacksquare\)

Kesişim özelliği tümevarımla sonlu sayıda kümeye genişler: \(C_1, \dots, C_p\) konveks ise \(C_1 \cap C_2\) konvekstir, onun \(C_3\) ile kesişimi de konvekstir ve böyle devam edilir. (Aslında sonsuz sayıda konveks kümenin kesişimi de konvekstir; bkz. Konveks Analiz.) Lineer programlamada uygun bölge tam olarak böyle bir kesişim olacak.

Uç noktalar

Üçüncü özellik için köşe kavramını her boyutta geçerli olacak biçimde tanımlamamız gerekiyor. Bir çokgenin köşesini ötekilerden ayıran şey, iki başka noktanın arasında kalmamasıdır.

Tanım 2.12 (Uç (ekstrem) nokta) \(C\) konveks bir küme ve \(X \in C\) olsun. \(X\) noktası \(C\)’nin \(X\)’ten başka ve birbirinden farklı iki noktasının konveks kombinasyonu olarak ifade edilemiyorsa, yani

\[X = \lambda U + (1 - \lambda)V, \qquad U, V \in C, \quad U \ne V, \quad 0 < \lambda < 1\]

eşitliğini sağlayan \(U\), \(V\) ve \(\lambda\) bulunamıyorsa \(X\) noktasına \(C\)’nin bir uç noktası (ekstrem noktası) denir.

Yani uç nokta, \(C\)’nin içinde kalan hiçbir doğru parçasının “iç” noktası, uçları dışındaki bir noktası olamayan noktadır. (\(U \ne V\) ve \(0 < \lambda < 1\) iken \(X\) ne \(U\)’ya ne \(V\)’ye eşit olabilir; tanımdaki “\(X\)’ten başka” koşulu bu yüzden formüle kendiliğinden yerleşmiştir.) Bir çokgende uç noktalar köşelerdir; bu yüzden uç noktaya köşe noktası da denir. Karşılaştırma için bkz. Konveks Analiz.

Bir konveks bölgenin sonlu sayıda uç noktası olabileceği gibi, daire, elips, küre, elipsoit gibi bölgelerin sınırlarındaki sonsuz sayıdaki noktanın her biri de uç noktadır. Yarı düzlem gibi bazı konveks kümelerin ise hiç uç noktası yoktur.

Solda çokgenin uç noktaları beş köşesidir. Bir kenarın ortasındaki P noktası uç nokta değildir: o kenar üzerinde P'nin iki yanındaki iki noktanın konveks kombinasyonudur. İçteki Q noktası da kendisinden geçen kısa bir doğru parçasının ortasıdır. Sağda elipsin sınırındaki her nokta uç noktadır; içteki noktalar değildir.

Örnek 2.15 (Karenin uç noktaları) \(0 \le x_1 \le 2\) ve \(0 \le x_2 \le 2\) koşullarını sağlayan \((x_1, x_2)\) noktalarının oluşturduğu \(C\) karesi verilsin. \((2, 2)\), \((2, 1)\) ve \((1, 1)\) noktalarından hangileri \(C\)’nin uç noktasıdır?

Çözüm

\((2, 1)\): \((2, 0)\) ve \((2, 2)\) noktaları \(C\)’dedir, birbirinden farklıdır ve

\[(2, 1) = \tfrac{1}{2}(2, 0) + \tfrac{1}{2}(2, 2)\]

olur. \((2, 1)\) uç nokta değildir.

\((1, 1)\): Benzer biçimde \((1, 1) = \tfrac{1}{2}(0, 0) + \tfrac{1}{2}(2, 2)\) olduğundan uç nokta değildir.

\((2, 2)\): Tersine, \((2, 2) = \lambda U + (1 - \lambda)V\) olacak biçimde \(U = (u_1, u_2)\), \(V = (v_1, v_2) \in C\) ve \(0 < \lambda < 1\) bulunduğunu varsayalım. Birinci bileşenler

\[2 = \lambda u_1 + (1 - \lambda)v_1, \qquad \text{yani} \qquad \lambda(2 - u_1) + (1 - \lambda)(2 - v_1) = 0\]

verir. \(U, V \in C\) olduğundan \(2 - u_1 \ge 0\) ve \(2 - v_1 \ge 0\)’dır; \(\lambda > 0\) ve \(1 - \lambda > 0\) olduğundan iki terim de negatif değildir. Toplamları sıfır olduğuna göre ikisi de sıfırdır: \(u_1 = v_1 = 2\). İkinci bileşenler için aynı akıl yürütme \(u_2 = v_2 = 2\) verir. O halde \(U = V = (2, 2)\) olur; bu, \(U \ne V\) koşuluyla çelişir. \((2, 2)\) bir uç noktadır.

Aynı akıl yürütmeyle karenin dört köşesi de uç noktadır. Başka uç noktası yoktur: bir kenarın köşe olmayan her noktası, o kenar üzerinde kendi iki yanındaki iki noktanın orta noktasıdır; içteki her nokta da kendisinden geçen kısa bir yatay doğru parçasının orta noktasıdır.

\(\blacksquare\)

Üçüncü özellik, uç noktaların bir konveks kümeyi “ürettiğini” söyler. Bunu, lineer programlamada en çok karşılaşacağımız durum olan sınırlı düzlemsel bölgeler için ifade edip ispatlayalım.

Önerme 2.5 (Konveks çokgenin noktaları uç noktalardan üretilir) Düzlemde sonlu sayıda doğru parçasıyla sınırlanan sınırlı ve konveks bir \(C\) bölgesinin (sınırı dahil konveks çokgenin) her noktası, \(C\)’nin uç noktalarının (köşelerinin) bir konveks kombinasyonu olarak yazılabilir.

Konveks çokgenin bir noktasını uç noktaların konveks kombinasyonu olarak yazmak. Solda A sınırdadır ve X₆X₁ kenarı üzerinde olduğu için X₆ ile X₁'in konveks kombinasyonudur. Sağda A içtedir: X₆'dan A'ya giden ışın sınırı X₂X₃ kenarındaki B noktasında keser; A, X₆ ile B'nin, B de X₂ ile X₃'ün konveks kombinasyonudur.

İspat

\(C\)’nin köşeleri \(X_1, X_2, \dots, X_p\) olsun. Önce köşelerin gerçekten uç nokta olduğunu görelim; akıl yürütme kare örneğindekinin (Örnek 2.15) aynısıdır. Bir \(X_j\) köşesinden geçen iki kenarın doğruları \(\vec{a}^{\,T}X = b\) ve \(\vec{d}^{\,T}X = e\) olsun. \(C\) konveks olduğundan her kenar doğrusunun bir yanında kalır; diyelim ki \(C\)’nin her noktasında \(\vec{a}^{\,T}X \le b\) ve \(\vec{d}^{\,T}X \le e\)’dir. \(X_j = \lambda U + (1 - \lambda)V\), \(U, V \in C\), \(0 < \lambda < 1\) olsun. O zaman

\[b = \vec{a}^{\,T}X_j = \lambda\,\vec{a}^{\,T}U + (1 - \lambda)\,\vec{a}^{\,T}V\]

olur. Sağdaki iki değer \(b\)’yi aşmadığı ve ağırlıklar pozitif olduğu için ikisi de \(b\)’ye eşittir; yani \(U\) ve \(V\) birinci doğru üzerindedir. Aynı biçimde ikinci doğru üzerindedirler. İki doğru yalnız \(X_j\)’de kesiştiğinden \(U = V = X_j\) çıkar. Demek ki \(X_j\) iki farklı noktanın konveks kombinasyonu olarak yazılamaz ve bir uç noktadır.

Şimdi \(A \in C\) alalım. Şekildeki altıgende (\(p = 6\)) iki durumu ayrı ayrı inceleyelim.

Durum 1: \(A\) sınırda. \(C\)’nin sınırı kenarlardan oluşur; \(A\) bir kenar üzerindedir. Şekilde \(A\), \(X_6X_1\) kenarı üzerindedir. Doğru parçasının tanımına göre bir \(0 \le \lambda \le 1\) için

\[A = \lambda X_6 + (1 - \lambda)X_1\]

olur; yani \(A\), \(X_6\) ve \(X_1\) uç noktalarının bir konveks kombinasyonudur.

Durum 2: \(A\) içte. Bir köşe seçelim, örneğin \(X_6\), ve \(X_6\)’dan başlayıp \(A\)’dan geçen ışını düşünelim: \(X_6 + s(A - X_6)\), \(s \ge 0\). \(C\) sınırlı olduğundan bu ışın bir yerde \(C\)’den çıkar; \(C\) sınırını içerdiğinden ışının \(C\)’de kalan en uzak noktası vardır. Bu noktaya \(B\) diyelim: \(B = X_6 + s^{*}(A - X_6)\). \(B\) sınırdadır ve şekilde \(X_2X_3\) kenarı üzerindedir. \(A\) içte olduğundan ışın \(A\)’yı geçtikten sonra da bir süre \(C\)’de kalır; bu yüzden \(s^{*} > 1\)’dir. \(B\)’nin tanımından

\[A = X_6 + \frac{1}{s^{*}}(B - X_6) = \lambda X_6 + (1 - \lambda)B, \qquad \lambda = 1 - \frac{1}{s^{*}}\]

bulunur ve \(0 < \lambda < 1\)’dir; \(A\), \(X_6B\) doğru parçası üzerindedir. \(B\) noktası da \(X_2X_3\) doğru parçası üzerinde olduğundan \(0 \le \alpha \le 1\) olmak üzere \(B = \alpha X_2 + (1 - \alpha)X_3\)’tür. Buradan

\[ \begin{aligned} A &= \lambda X_6 + (1 - \lambda)B = \lambda X_6 + (1 - \lambda)\big(\alpha X_2 + (1 - \alpha)X_3\big) \\ &= \lambda X_6 + \alpha(1 - \lambda)X_2 + (1 - \lambda)(1 - \alpha)X_3 \end{aligned} \]

elde edilir. Katsayılar

\[\lambda \ge 0, \qquad \alpha(1 - \lambda) \ge 0, \qquad (1 - \lambda)(1 - \alpha) \ge 0\]

koşullarını sağlar ve toplamları

\[\lambda + \alpha(1 - \lambda) + (1 - \lambda)(1 - \alpha) = \lambda + (1 - \lambda)\big(\alpha + 1 - \alpha\big) = 1\]

olur. Yani \(A\) noktası \(X_6\), \(X_2\), \(X_3\) uç noktalarının bir konveks kombinasyonu olarak ifade edilir. Işın başka bir kenarda çıksaydı aynı hesap o kenarın iki ucuyla yapılırdı.

\(\blacksquare\)

Önermedeki sınırlılık koşulu gereklidir. Örneğin yarı düzlem konvekstir ama hiç uç noktası yoktur; onun noktalarını uç noktaların kombinasyonu olarak yazmak mümkün değildir. Sınırlı ve sınırını içeren konveks kümeler için aynı özellik her boyutta geçerlidir; bunun genel ifadesi Konveks Analiz dersinin konusudur.

2.7 LP Probleminin Uygun Çözümleri

Artık bölümün ana teoremine hazırız: uygun çözümlerin kümesi konvekstir. Bu, uygun bölgede “delik” ya da “girinti” olmadığı anlamına gelir.

Teorem 2.1 (Uygun çözümler konveks küme oluşturur) Bir lineer programlama probleminin uygun çözümleri konveks bir küme oluşturur.

İspat

Lineer programlama problemi

\[ \begin{aligned} A\vec{x} &= \vec{b} && (1) \\ x_i &\ge 0, \quad i = \overline{1,n} && (2) \\ \min z &= \vec{c}^{\,T}\vec{x} && (3) \end{aligned} \]

olsun. Uygun çözümü hiç yoksa uygun çözümler kümesi boştur ve boş küme konvekstir. Aksi halde problemin herhangi iki uygun çözümü \(U = (u_1, u_2, \dots, u_n)\) ve \(V = (v_1, v_2, \dots, v_n)\) olmak üzere, bu noktaların bir konveks kombinasyonu

\[W = (w_1, w_2, \dots, w_n) = \lambda U + (1 - \lambda)V, \qquad 0 \le \lambda \le 1\]

olsun. Teoremin ispatı için \(W\) noktasının bir uygun çözüm olduğunu göstermek yeterlidir.

1. \(W\) noktası (1) eşitliğini sağlar. \(U\) ve \(V\) uygun çözüm olduğundan \(AU = \vec{b}\) ve \(AV = \vec{b}\)’dir. Matris çarpımının dağılma özelliğini kullanarak

\[AW = A\big[\lambda U + (1 - \lambda)V\big] = \lambda AU + (1 - \lambda)AV = \lambda\vec{b} + (1 - \lambda)\vec{b} = \vec{b}\]

elde edilir.

2. \(W\) noktasının hiçbir bileşeni negatif değildir. \(W = \lambda U + (1 - \lambda)V\) eşitliği bileşen bileşen

\[w_i = \lambda u_i + (1 - \lambda)v_i, \qquad i = \overline{1,n}\]

demektir. \(u_i \ge 0\), \(v_i \ge 0\) ve \(0 \le \lambda \le 1\) (yani \(\lambda \ge 0\) ve \(1 - \lambda \ge 0\)) olduğundan iki terim de negatif değildir; \(w_i\) değerleri (2) koşulunu sağlar.

1 ve 2 nedeniyle \(W\) bir uygun çözümdür.

\(\blacksquare\)

Yani herhangi iki uygun çözümün herhangi bir konveks kombinasyonu da bir uygun çözümdür; uygun çözümlerin kümesi bu yüzden konvekstir. Amaç fonksiyonu ispatta hiç kullanılmadı; teorem maksimum problemleri için de aynen geçerlidir. Aynı sonuca geometrik bir yoldan da varılabilir: (1) sisteminin katsayıları hepsi birden sıfır olmayan her denklemi bir hiperdüzlem (katsayıları hepsi sıfır olan bir denklem ya bütün uzayı ya da boş kümeyi verir; ikisi de konvekstir), (2)’deki her koşul bir yarı uzaydır; uygun çözümler kümesi bu sonlu sayıda konveks kümenin kesişimidir (Önerme 2.2, Önerme 2.4). Bu ikinci yol, kısıtları eşitsizlik biçiminde verilen problemler için de doğrudan işler, çünkü her \(\le\) ya da \(\ge\) kısıtı da bir yarı uzaydır.

Sonuç 2.1 (Uygun bölgenin biçimi)  

• İki boyutlu Öklid uzayında (düzlemde), kısıtları \(x_1\) ve \(x_2\) cinsinden eşitsizlikler olan bir lineer programlama probleminin uygun çözümleri, sonlu sayıda doğruyla sınırlanan konveks bir düzlemsel bölge oluşturur.
• Üç boyutlu uzayda uygun çözümlerin kümesi, sonlu sayıda düzlemle sınırlanan konveks bir uzay bölgesidir. Daha yüksek boyutlu Öklid uzaylarında uygun çözümlerin kümesi, sonlu sayıda hiperdüzlemle sınırlanan konveks bir bölge (polihedron, yani sonlu sayıda yarı uzayın kesişimi olan küme) oluşturur.
• Bir lineer programlama probleminin uygun çözümlerinin oluşturduğu konveks küme \(K\) ile gösterilecektir. \(K\) konveks bölgesi bazı doğrultularda (doğrularla, düzlemlerle, …) sınırlandırılmış ya da sınırlandırılmamış olabilir.

İspat

Problemin her kısıtı ve her işaret koşulu bir hiperdüzlem (eşitlik) ya da bir yarı uzay (eşitsizlik) tanımlar ve bunların sayısı sonludur. (Katsayıları hepsi sıfır olan bir kısıt ya her noktada sağlanır ve atılabilir ya da hiçbir noktada sağlanmaz ve \(K\) boş olur; boş küme de konvekstir. Bu yüzden böyle kısıtların olmadığını varsayabiliriz.) Uygun çözümlerin kümesi \(K\), bu kümelerin hepsini birlikte sağlayan noktalardan oluştuğu için onların kesişimidir. Önerme 2.2 gereği her biri konvekstir ve Önerme 2.4 tümevarımla uygulanınca \(K\) konveks çıkar. Bir hiperdüzlem de iki yarı uzayın kesişimi olduğundan \(K\) sonlu sayıda yarı uzayın kesişimidir, yani bir polihedrondur (bkz. Konveks Analiz).

\(K\)’nın sınırı bu yarı uzayların sınırlarından, yani sonlu sayıda hiperdüzlemin parçalarından oluşur: düzlemde her yarı düzlemin sınırı bir doğru, üç boyutta her yarı uzayın sınırı bir düzlemdir. Böylece ilk iki madde elde edilir.

Son madde için iki örnek yeter: Örnek 2.10 problemindeki \(K\) bir dörtgendir ve sınırlıdır; aşağıdaki örnekteki (Örnek 2.16) \(K\) ise bir yönde sonsuza uzanır.

\(\blacksquare\)

Örnek 2.16 (Sınırsız bir uygun bölge) \[ \begin{aligned} x_1 + x_2 &\ge 2 \\ -x_1 + x_2 &\le 1 \\ x_1, x_2 &\ge 0 \end{aligned} \]

kısıtlarının belirlediği \(K\) uygun bölgesi sınırlı mıdır? \(K\)’nın köşelerini bulunuz.

Çözüm

x₁ + x₂ ≥ 2, −x₁ + x₂ ≤ 1, x₁, x₂ ≥ 0 kısıtlarının uygun bölgesi. Bölge iki doğru ve x₁ ekseniyle sınırlanır ama sağa ve sağ yukarı doğru sonsuza uzanır; sınırsız bir konveks bölgedir. Yalnız iki köşesi vardır: (2, 0) ve (1/2, 3/2).

\(K\), dört yarı düzlemin kesişimidir ve Sonuç 2.1 gereği konvekstir.

Sınırlı mı? \(t \ge 2\) olmak üzere \((t, 0)\) noktalarına bakalım: \(t + 0 \ge 2\), \(-t + 0 \le 1\), \(t \ge 0\) ve \(0 \ge 0\) sağlanır. Demek ki \(x_1\) ekseninin \(t \ge 2\) kısmının tamamı \(K\)’dadır ve \(K\), \(x_1\) yönünde sonsuza uzanır. \(K\) sınırsızdır.

Köşeler. Köşeler, sınır doğrularından ikisinin \(K\)’da kalan kesişim noktalarıdır. Dört sınır doğrusu \(x_1 + x_2 = 2\), \(-x_1 + x_2 = 1\), \(x_1 = 0\) ve \(x_2 = 0\)’dır; altı çiftin kesişimine bakalım:

• \(x_1 + x_2 = 2\) ile \(x_2 = 0\): \((2, 0)\). \(-2 + 0 \le 1\) sağlanır; köşedir.
• \(x_1 + x_2 = 2\) ile \(-x_1 + x_2 = 1\): toplarsak \(2x_2 = 3\), yani \(\left(\tfrac{1}{2}, \tfrac{3}{2}\right)\). İki koordinat da pozitif; köşedir.
• \(x_1 + x_2 = 2\) ile \(x_1 = 0\): \((0, 2)\). \(-0 + 2 = 2 > 1\) olduğundan \(K\)’da değildir.
• \(-x_1 + x_2 = 1\) ile \(x_1 = 0\): \((0, 1)\). \(0 + 1 = 1 < 2\) olduğundan \(K\)’da değildir.
• \(-x_1 + x_2 = 1\) ile \(x_2 = 0\): \((-1, 0)\). \(x_1 < 0\) olduğundan \(K\)’da değildir.
• \(x_1 = 0\) ile \(x_2 = 0\): \((0, 0)\). \(0 + 0 < 2\) olduğundan \(K\)’da değildir.

\(K\)’nın yalnız iki köşesi vardır: \((2, 0)\) ve \(\left(\tfrac{1}{2}, \tfrac{3}{2}\right)\). Sınırsız bir bölgenin her noktası köşelerinin konveks kombinasyonu olarak yazılamaz; örneğin \((5, 0)\) noktası iki köşeyi birleştiren doğru parçasının çok uzağındadır. Bu yüzden Önerme 2.5 sınırlı bölgeler için ifade edildi. Sınırsız bir uygun bölgede amaç fonksiyonunun optimumu olmayabilir; bu durumu Sınırsız çözüm ve alternatif optimal çözüm bölümünde inceleyeceğiz.

\(\blacksquare\)

Bölümü, ilk yarının dört değişkenli örneğine geometrik gözle yeniden bakarak bitirelim. Dört değişkenli bir problemin uygun bölgesini doğrudan çizemeyiz, ama bu örnekte uygun çözümler yalnız iki serbest değişkene bağlı olduğu için bir düzlemde çizilebilir.

Örnek 2.17 (Temel çözümler ve uygun bölgenin köşeleri) Örnek 2.2 koşullarının (\(x_1 + 2x_2 + 3x_3 + 4x_4 = 7\), \(2x_1 + x_2 + x_3 + 2x_4 = 3\), \(x_j \ge 0\)) uygun çözümler kümesini \(x_3x_4\) düzleminde çiziniz ve temel çözümlerin bu çizimde nerede bulunduğunu belirleyiniz.

Çözüm

Örneğin uygun çözümleri x₃x₄ düzleminde: x₁ = (x₃ − 1)/3 ve x₂ = (11 − 5x₃ − 6x₄)/3 olduğundan x₁ ≥ 0 koşulu x₃ ≥ 1, x₂ ≥ 0 koşulu 5x₃ + 6x₄ ≤ 11 demektir. Uygun bölge boyalı üçgendir ve köşeleri üç uygun temel çözüm X₂, X₄, X₅'tir. Uygun olmayan X₁ ve X₃ üçgenin dışındadır. x₁ = 0 ile x₃ = 0 doğruları paraleldir; bu yüzden x₁ ve x₃ birlikte sıfırlanınca temel çözüm çıkmaz. P noktası (1/3, 1/3, 2, 0) uygun çözümüdür.

Örnek 2.2 çözümünde her çözümün \(x_3\) ve \(x_4\) tarafından belirlendiğini gördük:

\[x_1 = \frac{x_3 - 1}{3}, \qquad x_2 = \frac{11 - 5x_3 - 6x_4}{3}.\]

Böylece her çözüme \(x_3x_4\) düzleminde bir \((x_3, x_4)\) noktası karşılık gelir ve bu eşleme birebirdir. Çözümün uygun olması

\[x_3 \ge 1, \qquad x_4 \ge 0, \qquad 5x_3 + 6x_4 \le 11\]

demektir; yani uygun çözümler düzlemde üç yarı düzlemin kesişimi olan bir \(T\) üçgenine karşılık gelir. \(T\)’nin köşeleri, sınır doğrularının ikişer ikişer kesişimidir:

• \(x_3 = 1\) ile \(x_4 = 0\): \((1, 0)\);
• \(5x_3 + 6x_4 = 11\) ile \(x_4 = 0\): \(\left(\tfrac{11}{5}, 0\right)\);
• \(x_3 = 1\) ile \(5x_3 + 6x_4 = 11\): \(6x_4 = 6\), yani \((1, 1)\).

Formüllere göre bu üç nokta sırasıyla \(X_4 = (0, 2, 1, 0)\), \(X_2 = \left(\tfrac{2}{5}, 0, \tfrac{11}{5}, 0\right)\) ve \(X_5 = (0, 0, 1, 1)\) çözümleridir. Tablodaki (Tablo 2.1) üç uygun temel çözüm, \(T\)’nin tam olarak üç köşesidir.

Uygun olmayan temel çözümler de çizimde görünür. \(X_1\) (\(x_3 = x_4 = 0\)) başlangıç noktasına, \(X_3\) (\(x_2 = x_3 = 0\)) \(\left(0, \tfrac{11}{6}\right)\) noktasına karşılık gelir; ikisi de \(T\)’nin dışındadır. Temel çözüm vermeyen e) seçiminin (\(x_1 = x_3 = 0\)) nedeni de açıktır: \(x_1 = 0\) doğrusu \(x_3 = 1\), \(x_3 = 0\) doğrusu ise \(x_4\) eksenidir; bu iki doğru paraleldir ve kesişmez.

Son olarak ilk bulduğumuz uygun çözüm \(P = \left(\tfrac{1}{3}, \tfrac{1}{3}, 2, 0\right)\) düzlemde \((2, 0)\) noktasına, yani \(X_4X_2\) kenarı üzerine düşer. \(2 = \lambda \cdot 1 + (1 - \lambda) \cdot \tfrac{11}{5}\) eşitliğinden \(\lambda = \tfrac{1}{6}\) bulunur ve gerçekten

\[\tfrac{1}{6}X_4 + \tfrac{5}{6}X_2 = \left(0 + \tfrac{1}{3},\ \tfrac{1}{3} + 0,\ \tfrac{1}{6} + \tfrac{11}{6},\ 0\right) = \left(\tfrac{1}{3}, \tfrac{1}{3}, 2, 0\right) = P\]

olur. Yani \(P\), iki uygun temel çözümün konveks kombinasyonudur. \(x_1\) ve \(x_2\), \(x_3\) ile \(x_4\)’ün birinci dereceden ifadeleri olduğundan konveks kombinasyonlar bu eşlemede korunur; bu yüzden \(T\) için geçerli olan Önerme 2.5, uygun çözümlerin her birini \(X_2\), \(X_4\), \(X_5\) uygun temel çözümlerinin bir konveks kombinasyonu olarak yazabileceğimizi söyler.

\(\blacksquare\)

Bu bölümde standart formdaki bir problemin çözümlerini sınıflandırdık: çözüm, uygun çözüm, temel çözüm, uygun temel çözüm, dejenere uygun temel çözüm ve optimal çözüm. Temel çözümlerin sayısının en fazla \(C(n, m)\) olduğunu, uygun çözümlerin kümesinin ise konveks olduğunu gördük. İki örnekte uygun temel çözümler uygun bölgenin köşeleri, yani uç noktaları çıktı. Bir sonraki bölümde, Uç noktalar ve grafik yöntem bölümünde, bunun her zaman böyle olduğunu ve optimal çözüm varsa bir uç noktada bulunduğunu ispatlayacak, iki değişkenli problemleri grafik yöntemle çözeceğiz.