3  Uç Noktalar ve Grafik Yöntem

Temel çözümler ve konveks kümeler bölümünde iki şey gördük: bir lineer programlama probleminin uygun çözümleri konveks bir küme oluşturur ve standart formdaki kısıt sisteminin temel çözümleri, bazı değişkenler sıfır alınarak sonlu sayıda adaydan hesaplanır. Bu bölümde bu iki yapıyı birleştiriyoruz. Önce amaç fonksiyonunun en iyi değerini uygun çözümler kümesinin bir uç noktasında aldığını, sonra da uç noktaların tam olarak uygun temel çözümler olduğunu ispatlayacağız. İki sonuç birlikte çok güçlü bir şey söyler: sonsuz çok uygun çözüm arasında optimumu aramak yerine sonlu sayıdaki uygun temel çözüme bakmak yeter.

Bölümün ikinci yarısında iki değişkenli problemleri grafik yöntemle çözeceğiz. Düzlemde uygun çözümler kümesi bir çokgendir, uç noktaları da bu çokgenin köşeleridir; teoremlerin söylediği her şey burada gözle görülür. Grafik yöntem yalnız iki değişkende işe yarar, ama simpleks yöntemin arkasındaki geometriyi anlamanın en kısa yoludur.

3.1 Optimum Bir Uç Noktada Alınır

Önce kullanacağımız çerçeveyi kuralım. Bir lineer programlama probleminin uygun çözümlerinin kümesini \(K\) ile gösteriyoruz; \(K\)’nın noktalarını, yani uygun çözümleri \(X = (x_1, x_2, \dots, x_n)\) gibi büyük harflerle yazıyoruz. Amaç fonksiyonunu da noktanın bir fonksiyonu olarak düşünelim:

\[z = f(X) = c_1x_1 + c_2x_2 + \dots + c_nx_n = \vec{c}^{\,T}X.\]

Konveks küme, konveks kombinasyon ve uç nokta kavramlarını Temel çözümler ve konveks kümeler bölümünde tanımladık. Kısaca hatırlayalım: \(X_1, \dots, X_k\) noktalarının bir konveks kombinasyonu, \(\lambda_i \ge 0\) ve \(\lambda_1 + \dots + \lambda_k = 1\) olmak üzere \(\lambda_1X_1 + \dots + \lambda_kX_k\) biçimindeki bir noktadır. \(K\)’nın bir \(X\) noktası, \(K\)’nın \(X\)’ten farklı iki ayrı noktasının konveks kombinasyonu olarak yazılamıyorsa \(X\)’e \(K\)’nın bir uç noktası denir. Uygun çözümler kümesi \(K\) bir polihedrondur, yani sonlu sayıda yarı uzayın kesişimidir. \(K\) sınırlıysa uç noktalarının sayısı sonludur ve \(K\)’nın her noktası uç noktalarının bir konveks kombinasyonu olarak yazılabilir. Düzlemdeki sınırlı bölgeler için bunu önceki bölümde ispatladık; daha yüksek boyutta bu gerçeği ispatsız kullanacağız. (Standart formdaki problemler için bu kabulü hiç kullanmayan tam bir ispat aşağıda Teorem 3.4 ile gelecek.)

İspatlarda amaç fonksiyonunun tek bir özelliğini kullanacağız: \(f\) lineer bir fonksiyondur. Bu yüzden her konveks kombinasyon için

\[f\Big(\sum_{i=1}^{k} \lambda_iX_i\Big) = \sum_{i=1}^{k} \lambda_i\,\vec{c}^{\,T}X_i = \sum_{i=1}^{k} \lambda_if(X_i)\]

olur. Yani noktaların ağırlıklı ortalamasında \(f\)’nin değeri, \(f\) değerlerinin aynı ağırlıklarla alınmış ortalamasıdır. Ağırlıklı bir ortalama da ortalanan sayıların en küçüğünden küçük, en büyüğünden büyük olamaz. Aşağıdaki teoremin bütün fikri budur.

Teorem 3.1 (Optimum bir uç noktada alınır) Bir lineer programlama probleminin uygun çözümler kümesi \(K\) boş olmayan, sınırlı bir polihedron olsun. Bu durumda:

1. \(z\) amaç fonksiyonu minimum (maksimum) değerini \(K\)’nın uç noktalarından birinde alır.
2. \(z\) amaç fonksiyonu minimum (maksimum) değerini \(K\)’nın birden fazla uç noktasında alıyorsa, bu uç noktaların konveks kombinasyonu olan her noktada da aynı değeri alır.

İspat

\(K\) sınırlı olduğundan uç noktaları sonlu sayıdadır; bunlar \(X_1, X_2, \dots, X_k\) olsun. İspatı minimum problemi için yapıyoruz.

1. \(f(X_1), f(X_2), \dots, f(X_k)\) sayılarının en küçüğü \(f(X_t)\) olsun; burada \(t\), \(1\) ile \(k\) arasındaki bir indistir. \(X\), \(K\)’nın herhangi bir noktası olsun. \(K\) sınırlı bir polihedron olduğundan \(X\) uç noktaların bir konveks kombinasyonudur:

\[X = \sum_{i=1}^{k} \lambda_iX_i, \qquad \lambda_i \ge 0, \qquad \sum_{i=1}^{k} \lambda_i = 1.\]

\(f\) lineer olduğundan

\[ \begin{aligned} f(X) &= \sum_{i=1}^{k} \lambda_if(X_i) \ge \sum_{i=1}^{k} \lambda_if(X_t) \\[1mm] &= (\lambda_1 + \lambda_2 + \dots + \lambda_k)\,f(X_t) = f(X_t) \end{aligned} \]

elde edilir. Eşitsizlik adımında her \(i\) için \(\lambda_i \ge 0\) ve \(f(X_i) \ge f(X_t)\) olmasını, son adımda da ağırlıkların toplamının \(1\) olmasını kullandık. Demek ki \(K\)’nın her \(X\) noktası için \(f(X) \ge f(X_t)\)’dir, yani \(z\) minimum değerini \(X_t\) uç noktasında alır.

\(z\) minimum değerini başka bir \(X_0\) noktasında da alıyorsa, \(X_0\) minimum noktası olduğu için \(f(X_0) \le f(X_t)\)’dir; yukarıdaki eşitsizlik \(X = X_0\) için \(f(X_0) \ge f(X_t)\) verir. İki durum birlikte \(f(X_0) = f(X_t)\) demektir. O halde amaç fonksiyonunu minimum yapan bir uç nokta her zaman vardır.

2. \(z\) minimum değerini \(X_1, X_2, \dots, X_r\) uç noktalarında alsın ve bu ortak minimum değere \(f(X_0)\) diyelim: \(f(X_i) = f(X_0)\), \(i = \overline{1,r}\). Bu noktaların herhangi bir konveks kombinasyonu

\[Y = \sum_{i=1}^{r} \lambda_iX_i, \qquad \lambda_i \ge 0, \qquad \sum_{i=1}^{r} \lambda_i = 1\]

olsun. \(K\) konveks olduğundan \(Y \in K\)’dır, yani \(Y\) bir uygun çözümdür. Ayrıca

\[f(Y) = \sum_{i=1}^{r} \lambda_if(X_i) = f(X_0)\sum_{i=1}^{r} \lambda_i = f(X_0)\]

olur. Yani \(Y\) noktası da amaç fonksiyonunun aynı minimum değerini verir.

Maksimum probleminde \(f(X_t)\) olarak en büyük değer seçilir ve eşitsizliklerin yönü döner: her \(X \in K\) için \(f(X) \le f(X_t)\) çıkar. İkinci kısmın ispatı hiç değişmez. (Ya da Önerme 1.3 ile maksimum problemi \(-z\)’nin minimumuna çevrilir.)

\(\blacksquare\)

Yani sınırlı bir uygun bölgede optimum hiçbir zaman “bölgenin ortasında bir yerde” saklanmaz; mutlaka bir uç noktada da alınır. Optimum birden fazla uç noktada alınıyorsa bu uç noktaları birleştiren bütün noktalar da optimaldir; bu durumda sonsuz çok optimal çözüm vardır.

Teoremdeki sınırlılık koşulu ispatın tek bir yerinde kullanıldı: \(K\)’nın her noktasını uç noktaların konveks kombinasyonu olarak yazarken. Sınırsız bir bölgede bu yazım mümkün olmayabilir ve amaç fonksiyonunun optimumu hiç olmayabilir (bkz. Örnek 3.11). Optimum varsa bölge sınırsız olsa bile bir uç noktada alındığını ise aşağıdaki Teorem 3.4 gösterecek.

Sonuç 3.1 (Uç noktaları tarama) \(K\) boş olmayan, sınırlı bir polihedron ise \(z\) amaç fonksiyonunun \(K\)’nın uç noktalarında aldığı değerler taranarak optimal çözüme (Tanım 2.7) ulaşılabilir: minimum probleminde en küçük, maksimum probleminde en büyük \(z\) değerini veren uç nokta bir optimal çözümdür.

İspat

Teorem 3.1 teoreminin ilk kısmının ispatında, uç noktalardaki değerlerin en küçüğünü veren \(X_t\) noktası için her \(X \in K\) noktasında \(f(X) \ge f(X_t)\) olduğunu gösterdik. Demek ki uç noktalardaki değerleri karşılaştırıp en küçüğünü seçmek, bütün \(K\) üzerindeki minimumu verir. Maksimum için aynı akıl yürütme en büyük değerle yapılır.

\(\blacksquare\)

Örnek 3.1 (Köşeleri tarayarak optimum) Aşağıdaki problemin optimal çözümünü uygun bölgenin uç noktalarını tarayarak bulunuz.

\[ \begin{aligned} x_1 + 2x_2 &\le 8 \\ 3x_1 + 2x_2 &\le 12 \\ x_1, x_2 &\ge 0 \\ \max z &= x_1 + x_2 \end{aligned} \]

Çözüm

x₁ + 2x₂ ≤ 8, 3x₁ + 2x₂ ≤ 12, x₁, x₂ ≥ 0 kısıtlarının uygun bölgesi OABC dörtgenidir. z = x₁ + x₂ amaç fonksiyonu dört uç noktada 0, 4, 5, 4 değerlerini alır; en büyük değer B(2, 3) noktasındadır.

Uygun bölge dört yarı düzlemin kesişimidir: \(x_1 \ge 0\) ve \(x_2 \ge 0\) birinci bölgeyi, diğer iki kısıt da iki doğrunun alt tarafını verir. Bölge bir dörtgendir ve köşeleri kısıt doğrularının ikişer ikişer kesişimleridir.

• \(O(0, 0)\): iki eksenin kesişimi.
• \(A\): \(x_2 = 0\) ile \(3x_1 + 2x_2 = 12\) doğrusunun kesişimi, \(x_1 = 4\). Diğer kısıt \(4 + 0 = 4 \le 8\) sağlanır; \(A(4, 0)\).
• \(B\): iki kısıt doğrusunun kesişimi. İkinci denklemden birinciyi çıkarırsak \(2x_1 = 4\), yani \(x_1 = 2\) ve \(x_2 = 3\) olur; \(B(2, 3)\).
• \(C\): \(x_1 = 0\) ile \(x_1 + 2x_2 = 8\) doğrusunun kesişimi, \(x_2 = 4\). Diğer kısıt \(0 + 8 = 8 \le 12\) sağlanır; \(C(0, 4)\).

Doğruların diğer iki kesişimi köşe değildir. \(x_1 + 2x_2 = 8\) doğrusu \(x_1\) eksenini \((8, 0)\)’da keser, ama orada \(3 \cdot 8 = 24 > 12\) olur. \(3x_1 + 2x_2 = 12\) doğrusu \(x_2\) eksenini \((0, 6)\)’da keser, ama orada \(2 \cdot 6 = 12 > 8\) olur. Bu iki nokta uygun değildir.

Bölge sınırlıdır: her uygun noktada \(x_1 \le 4\) ve \(x_2 \le 4\)’tür. O halde Sonuç 3.1 uygulanabilir. Dört köşede amaç değerleri şöyledir:

Tablo 3.1: Uç noktalarda amaç değerleri

Uç nokta	\(O(0, 0)\)	\(A(4, 0)\)	\(B(2, 3)\)	\(C(0, 4)\)
\(z = x_1 + x_2\)	\(0\)	\(4\)	\(5\)	\(4\)

En büyük değer \(B\) noktasındadır: optimal çözüm \(x_1 = 2\), \(x_2 = 3\) ve \(\max z = 5\)’tir.

Sonucu bağımsız olarak da doğrulayabiliriz. Amaç fonksiyonu iki kısıtın sol taraflarının bir birleşimidir:

\[x_1 + x_2 = \tfrac{1}{4}(x_1 + 2x_2) + \tfrac{1}{4}(3x_1 + 2x_2) \le \tfrac{8}{4} + \tfrac{12}{4} = 5.\]

Yani hiçbir uygun noktada \(z\) değeri \(5\)’i geçemez ve \(B\)’de bu değere ulaşılır.

\(\blacksquare\)

Örnek 3.2 (Birden fazla uç noktada optimum) Örnek 3.1 örneğindeki kısıtlar (\(x_1 + 2x_2 \le 8\), \(3x_1 + 2x_2 \le 12\), \(x_1, x_2 \ge 0\)) altında \(\max z = 3x_1 + 2x_2\) problemini çözünüz.

Çözüm

Aynı bölgede z = 3x₁ + 2x₂. En büyük değer z = 12, A ve B uç noktalarında alınır; z = 12 seviye doğrusu AB kenarının üzerine oturduğu için kalın çizilen kenarın her noktası optimaldir. Ok gradyan yönünü, yani z'nin arttığı yönü gösterir.

Uygun bölge ve köşeleri aynıdır: \(O(0, 0)\), \(A(4, 0)\), \(B(2, 3)\), \(C(0, 4)\). Köşelerde

\[z(O) = 0, \quad z(A) = 12, \quad z(B) = 6 + 6 = 12, \quad z(C) = 8\]

olur. En büyük değer \(12\)’dir ve iki uç noktada, \(A\) ile \(B\)’de alınır. Teorem 3.1 teoreminin ikinci kısmına göre \(A\) ile \(B\)’nin her konveks kombinasyonu da optimaldir. Bunu doğrudan görelim: \(0 \le \lambda \le 1\) için

\[\lambda A + (1 - \lambda)B = \big(4\lambda + 2(1 - \lambda),\ 3(1 - \lambda)\big) = (2 + 2\lambda,\ 3 - 3\lambda)\]

noktasında

\[z = 3(2 + 2\lambda) + 2(3 - 3\lambda) = 6 + 6\lambda + 6 - 6\lambda = 12\]

olur. Örneğin \(\lambda = \tfrac12\) için \(AB\) kenarının orta noktası \((3, \tfrac32)\)’de de \(z = 9 + 3 = 12\)’dir. Problemin sonsuz çok optimal çözümü vardır: \(AB\) kenarının bütün noktaları. Nedeni de açıktır: amaç fonksiyonu \(3x_1 + 2x_2\), ikinci kısıtın sol tarafıyla aynıdır ve bu kısıt \(3x_1 + 2x_2 \le 12\) der; en büyük değer tam olarak kısıt doğrusu üzerinde alınır.

\(\blacksquare\)

3.2 Uç Noktalar ve Uygun Temel Çözümler

Önceki kısım optimumu uç noktalarda aramamızı söylüyor; ama uç nokta geometrik bir kavramdır ve ikiden fazla değişkende uç noktaları çizerek bulamayız. Bu kısımda uç noktaları cebirsel olarak tanıyacağız: uç noktalar, denklem sisteminden hesaplanabilen uygun temel çözümlerin ta kendisidir.

Problemi standart formda (Tanım 1.7) ve vektörel gösterimle ele alalım:

\[ \begin{aligned} x_1v_1 + x_2v_2 + \dots + x_mv_m + \dots + x_nv_n &= v_0 && (1) \\[1mm] x_1 \ge 0, \ x_2 \ge 0, \ \dots, \ x_n &\ge 0 && (2) \\[1mm] \min z &= c_1x_1 + c_2x_2 + \dots + c_nx_n && (3) \end{aligned} \]

Burada \(v_1, \dots, v_n\) katsayılar matrisi \(A\)’nın sütunları, \(v_0\) sağ taraf vektörüdür; hepsi \(m\) bileşenlidir. \(m < n\) olduğunu ve \(A\)’nın rankının \(m\) olduğunu, yani \(v_1, \dots, v_n\) arasında \(m\) tane lineer bağımsız vektör bulunduğunu varsayıyoruz. \(K\), (1) ve (2) koşullarını sağlayan \(X = (x_1, \dots, x_n)\) noktalarının kümesidir.

Temel çözüm tanımını (Tanım 2.3) hatırlayalım: \(v_1, \dots, v_n\) arasından \(m\) tane lineer bağımsız vektör seçilir; bunlara karşılık gelen değişkenler temel değişkenlerdir, geri kalan \(n - m\) değişkene sıfır verilir ve (1) sisteminin bu durumdaki tek çözümü bir temel çözümdür. Bütün bileşenleri negatif olmayan temel çözüm bir uygun temel çözümdür (Tanım 2.5); temel değişkenlerinden en az biri sıfır olan uygun temel çözüm dejeneredir (Tanım 2.6).

Teorem 3.2 (Uç noktanın pozitif bileşenleri) \(X = (x_1, x_2, \dots, x_n)\), (1)–(3) probleminin uygun çözümler kümesi \(K\)’nın bir uç noktası olsun. Bu durumda pozitif \(x_j\) değerlerini katsayı olarak kabul eden \(v_j\) vektörleri lineer bağımsızdır.

İspat

Gerekirse değişkenleri yeniden numaralayarak \(X\)’in ilk \(k\) bileşeninin pozitif, diğerlerinin sıfır olduğunu varsayalım: \(x_1, \dots, x_k > 0\) ve \(x_{k+1} = \dots = x_n = 0\). (\(k = 0\) ise, yani \(X = 0\) ise, iddia edilen vektör kümesi boştur ve boş küme lineer bağımsız sayılır.) Bu durumda (1) eşitliği

\[x_1v_1 + x_2v_2 + \dots + x_kv_k = v_0 \qquad \text{(a)}\]

biçimine dönüşür. \(v_1, \dots, v_k\) vektörlerinin lineer bağımlı olduğunu varsayalım. O zaman en az biri sıfırdan farklı \(y_1, \dots, y_k\) sayıları için

\[y_1v_1 + y_2v_2 + \dots + y_kv_k = 0 \qquad \text{(b)}\]

yazılabilir. \(t > 0\) bir sayı olsun. (b) eşitliğini \(t\) ile çarpıp (a) eşitliğine önce ekleyelim, sonra ondan çıkaralım:

\[ \begin{aligned} (x_1 + ty_1)v_1 + \dots + (x_k + ty_k)v_k &= v_0, \\[1mm] (x_1 - ty_1)v_1 + \dots + (x_k - ty_k)v_k &= v_0. \end{aligned} \]

\(t\) sayısını, \(x_i \mp ty_i\) sayılarının hepsi pozitif kalacak kadar küçük seçebiliriz: \(y_i \ne 0\) olan indisler için \(x_i/|y_i|\) oranlarının en küçüğünden küçük bir \(t > 0\) almak yeter. Çünkü \(y_i = 0\) ise \(x_i \mp ty_i = x_i > 0\), \(y_i \ne 0\) ise \(t|y_i| < x_i\) olduğundan \(x_i \mp ty_i \ge x_i - t|y_i| > 0\) olur. Böyle bir \(t\) için

\[ \begin{aligned} X_1 &= (x_1 + ty_1, \ \dots, \ x_k + ty_k, \ 0, \ \dots, \ 0), \\[1mm] X_2 &= (x_1 - ty_1, \ \dots, \ x_k - ty_k, \ 0, \ \dots, \ 0) \end{aligned} \]

noktaları (1) ve (2) koşullarını sağlar, yani \(K\) konveks kümesindedir. \(y_i\)’lerin en az biri sıfırdan farklı ve \(t > 0\) olduğundan \(X_1 - X_2 = 2t(y_1, \dots, y_k, 0, \dots, 0) \ne 0\)’dır; \(X_1\) ile \(X_2\) farklı noktalardır ve ikisi de \(X\)’ten farklıdır. Öte yandan yukarıdaki iki eşitliğin bileşenlerini taraf tarafa toplayıp \(2\)’ye bölersek

\[X = \tfrac{1}{2}X_1 + \tfrac{1}{2}X_2\]

elde ederiz. Yani \(X\) uç noktası, \(K\)’nın kendisinden farklı iki ayrı noktasının konveks kombinasyonu olarak yazılmış olur. Uç nokta tanımına göre bu mümkün değildir. Demek ki \(v_1, \dots, v_k\) vektörlerinin lineer bağımlı olduğu varsayımı yanlıştır; bu vektörler lineer bağımsızdır.

\(\blacksquare\)

Yani bir uç noktada pozitif olan değişkenlerin sütunları arasında “gereksiz” bir sütun yoktur. Gereksiz bir sütun olsaydı, pozitif değişkenleri bu sütunlar arasındaki bağıntı yönünde biraz artırıp biraz azaltarak noktayı iki uygun noktanın tam ortasına yerleştirebilirdik. Lineer bağımsızlığın tanımı için bkz. Lineer Cebir.

Örnek 3.3 (Uç nokta olmayan bir noktada bağımlı sütunlar) Örnek 3.1 örneğindeki kısıtları (\(x_1 + 2x_2 \le 8\), \(3x_1 + 2x_2 \le 12\), \(x_1, x_2 \ge 0\)) standart forma getiriniz. \(AB\) kenarının orta noktası \(P(3, \tfrac32)\) için pozitif bileşenlere ait sütunların lineer bağımlı olduğunu gösteriniz ve Teorem 3.2 teoreminin ispatındaki \(X_1\), \(X_2\) noktalarını bulunuz.

Çözüm

P(3, 3/2) noktası AB kenarının ortasındadır ve uç nokta değildir. İspattaki kaydırma, t = 1/4 için P'yi X₁(7/2, 3/4) ile X₂(5/2, 9/4) noktalarının orta noktası olarak yazar; t = 1/2 alınınca X₁ ve X₂ tam A ve B uç noktalarına ulaşır.

Önce problemi standart forma getirelim. İki kısıt da \(\le\) biçimindedir ve sağ tarafları negatif değildir; birinciye \(x_3\), ikinciye \(x_4\) aylak değişkenini ekleriz:

\[ \begin{aligned} x_1 + 2x_2 + x_3 &= 8 \\ 3x_1 + 2x_2 + x_4 &= 12 \\ x_1, x_2, x_3, x_4 &\ge 0 \end{aligned} \]

Sütun vektörleri

\[v_1 = \begin{bmatrix} 1 \\ 3 \end{bmatrix}, \quad v_2 = \begin{bmatrix} 2 \\ 2 \end{bmatrix}, \quad v_3 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \quad v_4 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \quad v_0 = \begin{bmatrix} 8 \\ 12 \end{bmatrix}\]

olur. \(P(3, \tfrac32)\) noktasında aylak değişkenler \(x_3 = 8 - 3 - 3 = 2\) ve \(x_4 = 12 - 9 - 3 = 0\)’dır. Standart formdaki nokta \(P = (3, \tfrac32, 2, 0)\)’dır ve üç bileşeni pozitiftir: \(x_1\), \(x_2\), \(x_3\).

\(v_1\), \(v_2\), \(v_3\) vektörleri iki bileşenlidir ve iki bileşenli üç vektör daima lineer bağımlıdır. Bağıntıyı bulalım: \(y_1v_1 + y_2v_2 + y_3v_3 = 0\) eşitliği

\[y_1 + 2y_2 + y_3 = 0, \qquad 3y_1 + 2y_2 = 0\]

sistemine denktir. \(y_1 = 2\) seçersek ikinci denklemden \(y_2 = -3\), birinciden \(y_3 = -2 + 6 = 4\) çıkar. Sağlama:

\[2v_1 - 3v_2 + 4v_3 = (2 - 6 + 4,\ 6 - 6 + 0) = (0, 0).\]

İspattaki gibi \(t > 0\) için

\[ \begin{aligned} X_1 &= (3 + 2t,\ \tfrac32 - 3t,\ 2 + 4t,\ 0), \\[1mm] X_2 &= (3 - 2t,\ \tfrac32 + 3t,\ 2 - 4t,\ 0) \end{aligned} \]

noktalarını kuralım. Bileşenlerin pozitif kalması için \(\tfrac32 - 3t > 0\) ve \(2 - 4t > 0\), yani \(t < \tfrac12\) gerekir. \(t = \tfrac14\) seçelim:

\[X_1 = \big(\tfrac72,\ \tfrac34,\ 3,\ 0\big), \qquad X_2 = \big(\tfrac52,\ \tfrac94,\ 1,\ 0\big).\]

İkisi de kısıtları sağlar: \(X_1\) için \(\tfrac72 + \tfrac32 + 3 = 8\) ve \(\tfrac{21}{2} + \tfrac32 + 0 = 12\); \(X_2\) için \(\tfrac52 + \tfrac92 + 1 = 8\) ve \(\tfrac{15}{2} + \tfrac92 + 0 = 12\). Orta noktaları da

\[\tfrac12X_1 + \tfrac12X_2 = \big(3,\ \tfrac32,\ 2,\ 0\big) = P\]

olur. Böylece \(P\), iki farklı uygun noktanın orta noktası olarak yazıldı; \(P\) uç nokta değildir. \(t\)’yi sınıra kadar büyütüp \(t = \tfrac12\) alırsak \(X_1 = (4, 0, 4, 0)\) ve \(X_2 = (2, 3, 0, 0)\) olur: bunlar tam \(A\) ve \(B\) uç noktalarıdır.

Karşılaştırma için \(B = (2, 3, 0, 0)\) uç noktasına bakalım. Pozitif bileşenler \(x_1\) ve \(x_2\)’dir ve

\[\det\,[\,v_1 \;\; v_2\,] = \begin{vmatrix} 1 & 2 \\ 3 & 2 \end{vmatrix} = 2 - 6 = -4 \ne 0\]

olduğundan \(v_1\), \(v_2\) lineer bağımsızdır; teoremin söylediği gibi.

\(\blacksquare\)

Teoremden iki önemli sonuç çıkar.

Sonuç 3.2 (Uç noktada en fazla m pozitif bileşen) (1)–(3) probleminde \(K\)’nın her uç noktasında pozitif bileşenlerin sayısı en fazla \(m\)’dir; başka bir deyişle en az \(n - m\) bileşen sıfırdır.

İspat

\(v_1, \dots, v_n\) vektörlerinin her biri \(m\) bileşenlidir, yani \(m\) boyutlu uzayın elemanıdır. \(m\) boyutlu uzayda en fazla \(m\) tane lineer bağımsız vektör vardır; \(m + 1\) tane vektör daima lineer bağımlıdır (bkz. Lineer Cebir). Başka bir ifadeyle \(A\) matrisinin (\(m < n\)) en fazla \(m\) tane lineer bağımsız sütunu vardır. Teorem 3.2 teoremine göre bir uç noktanın pozitif bileşenlerine ait sütunlar lineer bağımsızdır; bu yüzden pozitif bileşenlerin sayısı en fazla \(m\)’dir ve geri kalan en az \(n - m\) bileşen sıfırdır.

\(\blacksquare\)

Sonuç 3.3 (Her uç nokta bir uygun temel çözümdür) (1)–(3) probleminde \(K\)’nın uç noktalarından her biri bir uygun temel çözüme karşılık gelir. Özel olarak \(K\)’nın uç noktalarının sayısı en fazla \(\binom{n}{m}\)’dir.

İspat

\(X\) bir uç nokta olsun ve pozitif bileşenleri yine \(x_1, \dots, x_k\) olsun. Teorem 3.2 teoremine göre \(v_1, \dots, v_k\) lineer bağımsızdır ve Sonuç 3.2 sonucuna göre \(k \le m\)’dir.

\(k = m\) ise \(v_1, \dots, v_m\) tam bir baz oluşturur. \(k < m\) ise bu \(k\) vektörü \(A\)’nın sütunlarından seçilen \(m - k\) vektörle tamamlayarak \(m\) tane lineer bağımsız sütun elde edebiliriz: \(A\)’nın rankı \(m\) olduğundan sütunları \(m\) boyutlu uzayı doğurur ve lineer bağımsız bir küme, doğuran bir kümenin elemanlarıyla bir tabana tamamlanabilir (bkz. Lineer Cebir).

Her iki durumda da \(X\)’in sıfırdan farklı bileşenlerinin hepsi, seçilen \(m\) sütuna karşılık gelen değişkenler arasındadır. Bu \(m\) sütunun oluşturduğu \(B\) matrisi lineer bağımsız sütunlardan oluştuğu için tersinirdir; diğer değişkenler sıfırken (1) sistemi \(B\vec{x}_B = v_0\) biçimini alır ve tek çözümü vardır. \(X\) bu sistemi sağladığı için o tek çözüm \(X\)’tir. Demek ki \(X\), bu baza ait temel çözümdür. Bütün bileşenleri negatif olmadığından \(X\) bir uygun temel çözümdür; \(k < m\) ise bazı temel değişkenleri sıfır olduğundan dejeneredir.

\(m\) sütunluk bir baz, \(n\) sütun arasından \(m\) tanesini seçerek oluşur; bunun en fazla \(\binom{n}{m}\) yolu vardır ve her baz en fazla bir temel çözüm verir. Her uç nokta bir temel çözüm olduğundan uç noktaların sayısı en fazla \(\binom{n}{m}\)’dir.

\(\blacksquare\)

Bu sonucun tersi de doğrudur; ispatı tanımlardan doğrudan çıkar.

Teorem 3.3 (Her uygun temel çözüm bir uç noktadır) (1)–(3) probleminin her uygun temel çözümü, \(K\)’nın bir uç noktasıdır.

İspat

\(X = (x_1, \dots, x_n)\) bir uygun temel çözüm olsun. Temel değişkenlerin indis kümesine \(J\) diyelim; \(J\)’ye ait \(m\) sütunun oluşturduğu \(B\) matrisi tersinirdir ve \(j \notin J\) için \(x_j = 0\)’dır.

\(X\)’in uç nokta olmadığını varsayalım. O zaman \(X\)’ten farklı ve birbirinden farklı \(X_1, X_2 \in K\) noktaları ve \(0 < \lambda < 1\) sayısı için

\[X = \lambda X_1 + (1 - \lambda)X_2\]

yazılabilir. \(X_1\)’in ve \(X_2\)’nin bileşenlerini \(x_j^{(1)}\) ve \(x_j^{(2)}\) ile gösterelim. \(j \notin J\) için

\[0 = x_j = \lambda x_j^{(1)} + (1 - \lambda)x_j^{(2)}\]

olur. Sağdaki iki terim de negatif değildir (\(\lambda > 0\), \(1 - \lambda > 0\) ve \(X_1, X_2 \in K\)); toplamları sıfır olduğundan ikisi de sıfırdır. Demek ki \(X_1\) ve \(X_2\)’nin de temel olmayan bileşenleri sıfırdır. Bu durumda \(X_1\) ve \(X_2\) de, temel olmayan değişkenler sıfırken (1) sistemini, yani \(B\vec{x}_B = v_0\) sistemini sağlar. \(B\) tersinir olduğundan bu sistemin tek çözümü vardır; o da \(X\)’in temel bileşenleridir. O halde \(X_1 = X\) ve \(X_2 = X\) olur. Bu, \(X_1\) ile \(X_2\)’nin \(X\)’ten farklı olmasıyla çelişir. Demek ki \(X\) bir uç noktadır.

\(\blacksquare\)

Yani Sonuç 3.3 ile Teorem 3.3 birlikte şunu söyler:

\[X \text{ uç noktadır} \iff X \text{ uygun temel çözümdür}.\]

Geometrik kavram (uç nokta) ile cebirsel kavram (uygun temel çözüm) aynı nesneyi iki farklı dilde anlatır. Tek bir inceliğe dikkat edelim: dejenere bir uç nokta, birden fazla baza ait temel çözüm olabilir; yani bazlar ile uç noktalar arasındaki eşleme her zaman birebir değildir (bkz. Örnek 3.5).

Örnek 3.4 (Temel çözümler ve köşeler) Örnek 3.3 örneğindeki standart formun (\(x_1 + 2x_2 + x_3 = 8\), \(3x_1 + 2x_2 + x_4 = 12\), \(x_j \ge 0\)) bütün temel çözümlerini bulunuz ve uygun olanların uygun bölgenin köşeleriyle eşleştiğini gösteriniz.

Çözüm

Standart formun altı baz adayı. Dolu noktalar uygun temel çözümlerdir ve tam olarak bölgenin dört köşesidir; içi boş noktalar (8, 0) ile (0, 6) uygun olmayan temel çözümlerdir. Her noktanın yanında baz değişkenleri yazılıdır; bir kısıt doğrusu üzerinde o kısıtın aylak değişkeni sıfırdır.

\(m = 2\) denklem ve \(n = 4\) değişken vardır; baz adayı sayısı \(\binom{4}{2} = 6\)’dır. Sütunlar \(v_1 = (1, 3)\), \(v_2 = (2, 2)\), \(v_3 = (1, 0)\), \(v_4 = (0, 1)\) olmak üzere her ikilinin determinantı sıfırdan farklıdır:

\[ \begin{aligned} \det[v_1\,v_2] &= -4, & \det[v_1\,v_3] &= -3, & \det[v_1\,v_4] &= 1, \\ \det[v_2\,v_3] &= -2, & \det[v_2\,v_4] &= 2, & \det[v_3\,v_4] &= 1. \end{aligned} \]

Yani altı ikilinin hepsi bir baz oluşturur. Her baz için temel olmayan iki değişkene sıfır verip kalan \(2 \times 2\) sistemi çözelim.

• \(\{x_3, x_4\}\): \(x_1 = x_2 = 0\) alınınca \(x_3 = 8\), \(x_4 = 12\). Çözüm \((0, 0, 8, 12)\); uygun.
• \(\{x_1, x_3\}\): \(x_2 = x_4 = 0\) alınınca ikinci denklemden \(3x_1 = 12\), \(x_1 = 4\); birinciden \(x_3 = 8 - 4 = 4\). Çözüm \((4, 0, 4, 0)\); uygun.
• \(\{x_1, x_2\}\): \(x_3 = x_4 = 0\) alınınca \(x_1 + 2x_2 = 8\) ve \(3x_1 + 2x_2 = 12\); çıkarma \(2x_1 = 4\) verir, \(x_1 = 2\), \(x_2 = 3\). Çözüm \((2, 3, 0, 0)\); uygun.
• \(\{x_2, x_4\}\): \(x_1 = x_3 = 0\) alınınca \(2x_2 = 8\), \(x_2 = 4\); ikinci denklemden \(x_4 = 12 - 8 = 4\). Çözüm \((0, 4, 0, 4)\); uygun.
• \(\{x_1, x_4\}\): \(x_2 = x_3 = 0\) alınınca \(x_1 = 8\); ikinci denklemden \(x_4 = 12 - 24 = -12\). Çözüm \((8, 0, 0, -12)\); \(x_4 < 0\) olduğu için uygun değil.
• \(\{x_2, x_3\}\): \(x_1 = x_4 = 0\) alınınca \(2x_2 = 12\), \(x_2 = 6\); birinci denklemden \(x_3 = 8 - 12 = -4\). Çözüm \((0, 6, -4, 0)\); \(x_3 < 0\) olduğu için uygun değil.

Dört uygun temel çözümün ilk iki bileşeni \((0, 0)\), \((4, 0)\), \((2, 3)\), \((0, 4)\)’tür: bunlar tam olarak Örnek 3.1 örneğindeki \(O\), \(A\), \(B\), \(C\) köşeleridir. Uygun olmayan iki temel çözüm ise \((8, 0)\) ve \((0, 6)\) noktalarına karşılık gelir; bunlar kısıt doğrularının bölge dışında kalan kesişim noktalarıdır.

Geometrik anlamı şudur: \(x_3 = 0\), noktanın birinci kısıt doğrusu üzerinde; \(x_4 = 0\), ikinci kısıt doğrusu üzerinde; \(x_1 = 0\) ve \(x_2 = 0\) de eksenler üzerinde olması demektir. İki değişkeni sıfır yapmak, dört doğrudan ikisini seçip kesiştirmektir. Her temel çözümde tam iki bileşen sıfırdan farklıdır; dört uygun temel çözümde bu iki bileşen pozitiftir. Bu, Sonuç 3.2 sonucuyla uyumludur (\(m = 2\)) ve uygun temel çözümlerin hiçbiri dejenere değildir.

Uygunluk kontrolünün neden şart olduğunu amaç fonksiyonu \(z = x_1 + x_2\) ile görelim: uygun olmayan \((8, 0, 0, -12)\) temel çözümünde \(z = 8\) olur ve bu, gerçek optimum \(5\)’ten büyüktür. Tarama yalnız uygun temel çözümler üzerinden yapılır.

\(\blacksquare\)

Teorem 3.1 teoremi sınırlı bölgeler içindi. Şimdi optimumun var olduğu her durumda, bölge sınırsız olsa bile, bir uygun temel çözümde alındığını gösterelim.

Teorem 3.4 (Optimum varsa bir uygun temel çözümde de alınır) (1)–(3) probleminin bir optimal çözümü varsa, uygun temel çözüm olan bir optimal çözümü de vardır. Yani amaç fonksiyonu optimum değerini \(K\)’nın bir uç noktasında da alır.

İspat

İspatı minimum problemi için yapıyoruz. Bütün optimal çözümler arasından pozitif bileşen sayısı en az olanı seçelim ve \(X\) diyelim; pozitif bileşenleri yine \(x_1, \dots, x_k\) olsun. \(v_1, \dots, v_k\) vektörlerinin lineer bağımsız olduğunu göstereceğiz.

Bağımlı olduklarını varsayalım: en az biri sıfırdan farklı \(y_1, \dots, y_k\) için \(y_1v_1 + \dots + y_kv_k = 0\) olsun ve \(i > k\) için \(y_i = 0\) diyerek \(Y = (y_1, \dots, y_n)\) vektörünü kuralım. Her \(t\) sayısı için \(X + tY\) noktası (1) sistemini sağlar, çünkü \(\sum_j (x_j + ty_j)v_j = v_0 + t \cdot 0 = v_0\)’dır. Amaç değeri

\[f(X + tY) = f(X) + t\,\vec{c}^{\,T}Y\]

olur.

\(\vec{c}^{\,T}Y = 0\)’dır. \(|t|\) yeterince küçükse, önceki teoremin ispatındaki gibi, \(X + tY\) noktasının ilk \(k\) bileşeni pozitif kalır, diğerleri sıfırdır; yani \(X + tY \in K\)’dır. \(\vec{c}^{\,T}Y \ne 0\) olsaydı, küçük bir \(t\)’yi \(t\,\vec{c}^{\,T}Y < 0\) olacak işarette seçerek \(f(X + tY) < f(X)\) elde ederdik; bu, \(X\)’in optimal olmasıyla çelişir. Demek ki \(\vec{c}^{\,T}Y = 0\)’dır ve \(K\)’da kalan her \(X + tY\) noktası da optimaldir.

Daha az pozitif bileşenli bir optimal çözüm. Gerekirse \(Y\) yerine \(-Y\) alarak \(Y\)’nin en az bir bileşeninin negatif olduğunu varsayabiliriz. \(y_i < 0\) olan indisler üzerinden

\[\bar{t} = \min\Big\{ \frac{x_i}{-y_i} \ : \ y_i < 0 \Big\} > 0\]

diyelim. \(0 \le t \le \bar{t}\) için \(X + tY\) noktasının bileşenleri negatif olmaz: \(y_i \ge 0\) olan bileşenler azalmaz, \(y_i < 0\) olanlar ise ancak \(t = x_i/(-y_i)\) değerinde sıfıra iner. Dolayısıyla \(X + \bar{t}Y \in K\)’dır ve bu nokta da optimaldir. Üstelik minimumu veren indiste bileşen sıfır olur ve \(i > k\) için bileşenler sıfır kalır. Böylece \(X + \bar{t}Y\), \(X\)’ten daha az pozitif bileşeni olan bir optimal çözümdür. Bu, \(X\)’in seçimiyle çelişir.

O halde \(v_1, \dots, v_k\) lineer bağımsızdır. Sonuç 3.3 ispatındaki gibi bu vektörler \(m\) lineer bağımsız sütuna tamamlanır ve \(X\) bu baza ait bir uygun temel çözüm olur. Teorem 3.3 teoremine göre \(X\) aynı zamanda bir uç noktadır. Maksimum problemi için \(-z\)’nin minimumuna bakmak yeter (Önerme 1.3).

\(\blacksquare\)

Sonuç 3.4 (Uygun temel çözümleri tarama) (1)–(3) probleminin bir optimal çözümü varsa, amaç fonksiyonunun \(K\)’nın uç noktalarında alacağı değerler taranarak optimal çözüme ulaşılabilir. Özetle, \(z\) amaç fonksiyonunun uygun temel çözümler için alacağı değerlere bakılarak optimal çözüme ulaşılabilir: en fazla \(\binom{n}{m}\) tane olan uygun temel çözümler arasında, minimum probleminde \(z\)’yi en küçük, maksimum probleminde en büyük yapan uygun temel çözüm bir optimal çözümdür. \(K\) boş olmayan ve sınırlı ise optimal çözüm her zaman vardır.

İspat

Teorem 3.4 teoremine göre optimal çözüm varsa uygun temel çözümlerden biri optimaldir. Uygun temel çözümlerin her biri bir uygun çözüm olduğu için hiçbiri optimumdan daha iyi bir değer veremez. O halde uygun temel çözümler arasında en iyi \(z\) değerini veren, bütün \(K\) üzerinde de en iyisidir. Uygun temel çözümlerin sayısı Sonuç 3.3 ispatındaki sayma gereği en fazla \(\binom{n}{m}\)’dir. \(K\) boş olmayan ve sınırlı ise Teorem 3.1 optimumun var olduğunu da garanti eder.

\(\blacksquare\)

Bu sonuç çizim yapamadığımız problemlerde de işe yarar. Ama optimumun var olduğunu bilmeden tarama yapmak yanıltıcıdır: uygun bölge sınırsızsa amaç fonksiyonu sınırsız büyüyebilir ve köşelerdeki en iyi değer optimum olmaz (bkz. Örnek 3.11). Bir de tarama sayısı hızla büyür: 10 denklem ve 20 değişkenli bir problemde \(\binom{20}{10} = 184\,756\) baz adayı vardır. Simpleks yöntem bütün adaylara bakmak yerine uygun temel çözümden daha iyi bir komşu uygun temel çözüme geçerek ilerler.

Örnek 3.5 (Dört değişkenli bir problemde tarama) Aşağıdaki problemi bütün temel çözümleri hesaplayarak çözünüz.

\[ \begin{aligned} x_1 + x_2 + x_3 + 2x_4 &= 4 \\ 2x_1 - x_2 + x_3 + x_4 &= 2 \\ x_j \ge 0, \quad j &= \overline{1,4} \\ \min z &= x_1 + 2x_2 - x_3 + x_4 \end{aligned} \]

Çözüm

Problem standart formdadır: iki kısıt da eşitliktir, sağ taraflar \(4\) ve \(2\) negatif değildir ve bütün değişkenler \(\ge 0\)’dır. \(m = 2\), \(n = 4\) olduğundan \(\binom{4}{2} = 6\) baz adayı vardır. Sütunlar

\[v_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \quad v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \quad v_3 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \quad v_4 = \begin{bmatrix} 2 \\ 1 \end{bmatrix}\]

ve her ikilinin determinantı sıfırdan farklıdır (\(-3\), \(-1\), \(-3\), \(2\), \(3\), \(-1\)); altı adayın hepsi bazdır.

Optimumun var olduğunu önceden bilebiliriz: birinci denklemin bütün katsayıları pozitiftir, bu yüzden her uygun çözümde \(0 \le x_j \le 4\)’tür ve \(K\) sınırlıdır. \(K\) boş da değildir (örneğin \((2, 2, 0, 0)\) uygundur). Sonuç 3.4 gereği optimal çözüm uygun temel çözümlerden biridir.

Her baz için temel olmayan iki değişkene sıfır verip \(2 \times 2\) sistemi çözelim:

• \(\{x_1, x_2\}\): \(x_1 + x_2 = 4\), \(2x_1 - x_2 = 2\). Toplarsak \(3x_1 = 6\), \(x_1 = 2\), \(x_2 = 2\).
• \(\{x_1, x_3\}\): \(x_1 + x_3 = 4\), \(2x_1 + x_3 = 2\). Çıkarırsak \(x_1 = -2\), \(x_3 = 6\).
• \(\{x_1, x_4\}\): \(x_1 + 2x_4 = 4\), \(2x_1 + x_4 = 2\). İkincinin iki katından birinciyi çıkarırsak \(3x_1 = 0\), \(x_1 = 0\), \(x_4 = 2\).
• \(\{x_2, x_3\}\): \(x_2 + x_3 = 4\), \(-x_2 + x_3 = 2\). Toplarsak \(2x_3 = 6\), \(x_3 = 3\), \(x_2 = 1\).
• \(\{x_2, x_4\}\): \(x_2 + 2x_4 = 4\), \(-x_2 + x_4 = 2\). Toplarsak \(3x_4 = 6\), \(x_4 = 2\), \(x_2 = 0\).
• \(\{x_3, x_4\}\): \(x_3 + 2x_4 = 4\), \(x_3 + x_4 = 2\). Çıkarırsak \(x_4 = 2\), \(x_3 = 0\).

Tablo 3.2: Dört değişkenli problemin temel çözümleri

Baz	\((x_1, x_2, x_3, x_4)\)	Uygun mu?	\(z\)
\(\{x_1, x_2\}\)	\((2, 2, 0, 0)\)	evet	\(6\)
\(\{x_1, x_3\}\)	\((-2, 0, 6, 0)\)	hayır (\(x_1 < 0\))	\(-\)
\(\{x_1, x_4\}\)	\((0, 0, 0, 2)\)	evet, dejenere	\(2\)
\(\{x_2, x_3\}\)	\((0, 1, 3, 0)\)	evet	\(-1\)
\(\{x_2, x_4\}\)	\((0, 0, 0, 2)\)	evet, dejenere	\(2\)
\(\{x_3, x_4\}\)	\((0, 0, 0, 2)\)	evet, dejenere	\(2\)

Uygun temel çözümlerin \(z\) değerleri \(6\), \(2\) ve \(-1\)’dir. En küçüğü \(-1\)’dir: optimal çözüm \(x_1 = 0\), \(x_2 = 1\), \(x_3 = 3\), \(x_4 = 0\) ve \(\min z = -1\)’dir. Uygun olmayan \((-2, 0, 6, 0)\) temel çözümünde \(z = -2 - 6 = -8\) olurdu; bu değer optimumdan küçüktür ama bir uygun çözüme ait olmadığı için hesaba katılmaz.

Tabloda ilginç bir şey var: altı bazdan üçü aynı \((0, 0, 0, 2)\) noktasını veriyor. Bu noktada yalnız bir bileşen pozitiftir (\(x_4 = 2\)), yani \(m = 2\)’den az; nokta dejenere bir uygun temel çözümdür (Tanım 2.6). \(x_4\)’ün yanında bazda sıfır değerli bir değişken daha bulunur; bu değişken \(x_1\), \(x_2\) ya da \(x_3\) olabildiği için üç farklı baz aynı noktayı verir. Böylece \(K\)’nın beş değil yalnız üç uç noktası vardır: \((2, 2, 0, 0)\), \((0, 0, 0, 2)\) ve \((0, 1, 3, 0)\).

Sonucu bağımsız olarak doğrulayalım. İki denklemi toplarsak \(3x_1 + 2x_3 + 3x_4 = 6\), buradan \(x_3 = 3 - \tfrac32x_1 - \tfrac32x_4\) çıkar. Bunu birinci denklemde yerine koyarsak \(x_2 = 1 + \tfrac12x_1 - \tfrac12x_4\) bulunur. Amaç fonksiyonunda yerine yazarsak

\[ \begin{aligned} z &= x_1 + 2\big(1 + \tfrac12x_1 - \tfrac12x_4\big) - \big(3 - \tfrac32x_1 - \tfrac32x_4\big) + x_4 \\[1mm] &= -1 + \tfrac72x_1 + \tfrac32x_4 \end{aligned} \]

olur. \(x_1, x_4 \ge 0\) olduğundan her uygun çözümde \(z \ge -1\)’dir ve eşitlik ancak \(x_1 = x_4 = 0\) iken, yani \((0, 1, 3, 0)\) noktasında sağlanır. Amaç fonksiyonunu temel olmayan değişkenler cinsinden yazıp katsayılarının işaretine bakmak, simpleks yöntemin optimallik testinin özüdür.

\(\blacksquare\)

3.3 Grafik Yöntem

İki değişkenli problemler basit bir şekilde grafik yöntemle çözülebilir. Bu durumda her kısıt düzlemde bir yarı düzlem ya da bir doğru belirtir, uygun çözümler kümesi \(K\) bu yarı düzlemlerin kesişimi olan konveks bir çokgensel bölgedir ve uç noktalar bu bölgenin köşeleridir. Amaç fonksiyonunun davranışını anlamak için önce onun sabit değer aldığı noktalara bakalım.

Tanım 3.1 (Seviye doğrusu) \(z = c_1x_1 + c_2x_2\) amaç fonksiyonu ve bir \(k\) sayısı için \(c_1x_1 + c_2x_2 = k\) doğrusuna amaç fonksiyonunun \(k\) seviye doğrusu denir. Amaç katsayılarından oluşan \(\vec{c} = (c_1, c_2)\) vektörü \(z\)’nin gradyanıdır: \(\nabla z = \big(\tfrac{\partial z}{\partial x_1}, \tfrac{\partial z}{\partial x_2}\big) = (c_1, c_2)\).

Yani \(z\) bir parametre olarak düşünülürse \(z = c_1x_1 + c_2x_2\) denklemi bir doğru ailesi belirtir. \(z\)’nin her değerine bu ailenin tek bir doğrusu, ailenin her doğrusuna da \(z\)’nin tek bir değeri karşılık gelir. Aynı seviye doğrusu üzerindeki bütün noktalarda amaç fonksiyonu aynı değeri alır. Önemli olan, doğru hangi yönde ötelenirse \(z\)’nin artacağını belirlemektir.

Önerme 3.1 (Seviye doğruları ve gradyan) \(\vec{c} = (c_1, c_2) \ne 0\) olsun.

1. Bütün seviye doğruları birbirine paraleldir ve \(\vec{c}\) vektörüne diktir.
2. Her \(X\) noktası ve her \(t > 0\) için \(z(X + t\vec{c}) > z(X)\)’tir. Yani \(z\), gradyan yönünde ilerledikçe artar, gradyanın zıt yönünde ilerledikçe azalır.

İspat

1. \(k\) seviye doğrusu üzerinde iki nokta \(X = (x_1, x_2)\) ve \(Y = (y_1, y_2)\) olsun. \(c_1x_1 + c_2x_2 = k\) ve \(c_1y_1 + c_2y_2 = k\) eşitliklerini taraf tarafa çıkarırsak

\[c_1(x_1 - y_1) + c_2(x_2 - y_2) = 0\]

olur; yani doğrunun doğrultusu olan \(X - Y\) vektörü ile \(\vec{c}\)’nin iç çarpımı sıfırdır. Her seviye doğrusu \(\vec{c}\)’ye dik olduğundan hepsi aynı doğrultudadır, yani birbirine paraleldir. Farklı \(k\) değerleri için doğrular ortak nokta içermez; çünkü bir noktada \(z\) tek bir değer alır.

2. \(X = (x_1, x_2)\) için

\[ \begin{aligned} z(X + t\vec{c}) &= c_1(x_1 + tc_1) + c_2(x_2 + tc_2) \\[1mm] &= z(X) + t(c_1^2 + c_2^2) \end{aligned} \]

olur. \(\vec{c} \ne 0\) olduğundan \(c_1^2 + c_2^2 > 0\)’dır; \(t > 0\) için \(z\) artar, \(t < 0\) için (zıt yönde) azalır.

\(\blacksquare\)

Yani bir seviye doğrusunu kendine paralel olarak gradyan yönünde kaydırdıkça \(z\) büyür. Maksimum probleminde amaç fonksiyonu optimum değerini konveks bölgenin bir uç noktasında alır ve bu noktaya gradyan yönünde ilerleyerek varılır: seviye doğrusu, uygun bölgeyle ortak noktası kalacak şekilde gradyan yönünde olabildiğince kaydırılır ve bölgeye son değdiği nokta optimaldir. Minimum probleminde optimum değere gradyanın zıt yönünde ilerleyerek varılır.

İpucuBeş adımda grafik yöntem

1. Kısıt doğrularını çiz. Her kısıtı eşitlik olarak yaz ve doğruyu iki noktasından (çoğunlukla eksenleri kestiği noktalardan) çiz.
2. Yarı düzlemi test noktasıyla belirle. Doğru üzerinde olmayan bir nokta (çoğunlukla \(O(0, 0)\)) kısıtı sağlıyorsa o noktanın bulunduğu tarafı, sağlamıyorsa öbür tarafı al. \(x_1, x_2 \ge 0\) koşulları birinci bölgeyi verir.
3. Uygun bölgeyi bul. Uygun bölge bütün yarı düzlemlerin kesişimidir. Kesişim boşsa problemin uygun çözümü yoktur.
4. Köşe noktalarını hesapla. Her köşe iki kısıt doğrusunun kesişimidir: iki denklemli sistemi çöz ve bulunan noktanın diğer kısıtları sağladığını kontrol et.
5. Optimumu bul. Bir seviye doğrusu çiz ve onu maksimum probleminde gradyan \(\vec{c}\) yönünde, minimum probleminde \(-\vec{c}\) yönünde, bölgeyle ortak noktası kalana kadar kaydır; bölgeye son değdiği köşe optimaldir. Ya da köşelerde \(z\) değerlerini hesaplayıp karşılaştır; bu karşılaştırma optimum varken geçerlidir, bölge sınırsızsa önce seviye doğrusuyla optimumun var olduğunu gör.

Örnek 3.6 (Grafik yöntemle bir maksimum problemi) Aşağıdaki problemin grafik çözümünü bulunuz.

\[ \begin{aligned} x_1 + 4x_2 - 4 &\ge 0 \\ -x_1 + x_2 + 4 &\ge 0 \\ x_1 - 6 &\le 0 \\ x_1 - 2x_2 + 20 &\ge 0 \\ x_1, x_2 &\ge 0 \\ \max z &= x_1 + 2x_2 \end{aligned} \]

Çözüm

Uygun bölge ABCDE beşgenidir. Kesikli doğrular z = x₁ + 2x₂ amaç fonksiyonunun z = 20 ve z = 32 seviye doğrularıdır; ok gradyan yönünü gösterir. Seviye doğrusu gradyan yönünde kaydırıldığında bölgeden en son A(6, 13) köşesinde ayrılır: max z = 32.

Sabitleri sağa alırsak kısıtlar \(x_1 + 4x_2 \ge 4\), \(-x_1 + x_2 \ge -4\), \(x_1 \le 6\) ve \(x_1 - 2x_2 \ge -20\) olur.

1–2. Kısıt doğruları ve yarı düzlemler. Her doğruyu iki noktasından çizip \(O(0, 0)\) test noktasını yerine koyalım:

• \(x_1 + 4x_2 = 4\) doğrusu \((4, 0)\) ve \((0, 1)\)’den geçer. \(O\)’da \(0 \ge 4\) yanlıştır; uygun taraf \(O\)’nun karşı tarafıdır.
• \(-x_1 + x_2 = -4\) doğrusu \((4, 0)\) ve \((6, 2)\)’den geçer. \(O\)’da \(0 \ge -4\) doğrudur; uygun taraf \(O\)’nun bulunduğu taraftır.
• \(x_1 = 6\) düşey doğrusu için \(O\)’da \(0 \le 6\) doğrudur; uygun taraf doğrunun solu.
• \(x_1 - 2x_2 = -20\) doğrusu \((0, 10)\) ve \((6, 13)\)’ten geçer. \(O\)’da \(0 \ge -20\) doğrudur; uygun taraf \(O\)’nun bulunduğu taraftır.

3. Uygun bölge. Bu yarı düzlemlerin birinci bölgedeki kesişimi \(ABCDE\) beşgenidir.

4. Köşeler. Her köşe iki doğrunun kesişimidir:

• \(A\): \(x_1 = 6\) ve \(x_1 - 2x_2 = -20\); \(2x_2 = 26\), \(A(6, 13)\).
• \(B\): \(x_1 = 0\) ve \(x_1 - 2x_2 = -20\); \(x_2 = 10\), \(B(0, 10)\).
• \(C\): \(x_1 = 0\) ve \(x_1 + 4x_2 = 4\); \(x_2 = 1\), \(C(0, 1)\).
• \(D\): \(x_2 = 0\) ve \(x_1 + 4x_2 = 4\); \(x_1 = 4\), \(D(4, 0)\).
• \(E\): \(x_1 = 6\) ve \(-x_1 + x_2 = -4\); \(x_2 = 2\), \(E(6, 2)\).

Her köşenin diğer kısıtları sağladığını kontrol edelim. Örneğin \(A(6, 13)\) için \(6 + 52 = 58 \ge 4\) ve \(-6 + 13 = 7 \ge -4\); \(E(6, 2)\) için \(6 + 8 = 14 \ge 4\) ve \(6 - 4 = 2 \ge -20\)’dir. Diğer köşeler de aynı biçimde bütün kısıtları sağlar.

5. Optimum. \(z\) bir parametre olarak düşünülürse \(x_1 + 2x_2 = z\) paralel bir doğru ailesidir ve gradyan \(\vec{c} = (1, 2)\)’dir. Amaç maksimum olduğundan seviye doğrusunu \(\vec{c}\) yönünde, yani sağ yukarıya doğru kaydırırız. Örneğin \(B\)’den geçen \(z = 20\) seviye doğrusu bölgeyi keser; bölgenin bu doğrunun üstünde kalan kısmında \(z\) daha büyüktür. Doğruyu kaydırmaya devam edince bölgeden en son \(A(6, 13)\) köşesinde ayrılır: \(A\)’dan geçen \(z = 32\) seviye doğrusunun üstünde bölgenin hiçbir noktası yoktur.

Aynı sonucu köşe tablosuyla da görebiliriz (bölge sınırlı olduğu için Sonuç 3.1 geçerlidir):

Tablo 3.3: Grafik örneğinde köşelerdeki amaç değerleri

Köşe	\(A(6, 13)\)	\(B(0, 10)\)	\(C(0, 1)\)	\(D(4, 0)\)	\(E(6, 2)\)
\(z = x_1 + 2x_2\)	\(32\)	\(20\)	\(2\)	\(4\)	\(10\)

Bütün kısıtların sağlandığı \(A(6, 13)\) noktasından geçen \(z = x_1 + 2x_2\) doğrusunda amaç fonksiyonu maksimum değerini alır. Optimal çözüm \(x_1 = 6\), \(x_2 = 13\) ve \(\max z = 32\)’dir.

\(D(4, 0)\) köşesinde ilginç bir şey olur: \(-x_1 + x_2 = -4\) doğrusu da bu noktadan geçer. Yani \(D\)’de üç doğru (\(x_2 = 0\), \(x_1 + 4x_2 = 4\), \(-x_1 + x_2 = -4\)) kesişir. Problemi standart forma getirelim: birinci kısıttan \(x_3\) artık değişkenini çıkarırız; ikinci kısıtın sağ tarafı negatif olduğu için önce \(-1\) ile çarparız (\(x_1 - x_2 \le 4\)) ve \(x_4\) aylak değişkenini ekleriz; üçüncüye \(x_5\) aylak değişkenini ekleriz; dördüncüyü \(-1\) ile çarparız (\(-x_1 + 2x_2 \le 20\)) ve \(x_6\) aylak değişkenini ekleriz:

\[ \begin{aligned} x_1 + 4x_2 - x_3 &= 4 \\ x_1 - x_2 + x_4 &= 4 \\ x_1 + x_5 &= 6 \\ -x_1 + 2x_2 + x_6 &= 20 \\ x_j \ge 0, \quad j &= \overline{1,6} \\ \max z &= x_1 + 2x_2 + 0x_3 + 0x_4 + 0x_5 + 0x_6 \end{aligned} \]

Burada \(m = 4\)’tür. \(A(6, 13)\)’te \(x_3 = 54\), \(x_4 = 11\), \(x_5 = x_6 = 0\) olur ve tam dört bileşen pozitiftir (\(x_1, x_2, x_3, x_4\)). \(D(4, 0)\)’da ise \(x_2 = x_3 = x_4 = 0\), \(x_5 = 2\), \(x_6 = 24\) olur: yalnız üç bileşen (\(x_1\), \(x_5\), \(x_6\)) pozitiftir. \(D\) bir dejenere uygun temel çözümdür (Tanım 2.6). Düzlemde dejenerelik, bir köşeden gereğinden fazla kısıt doğrusunun geçmesi olarak görünür.

\(\blacksquare\)

Reçeteyi bir kez daha, bu kez ilk bölümde kurduğumuz üretim modelinde uygulayalım.

Örnek 3.7 (Üretim planlamasının grafik çözümü) Örnek 1.3 modelini (\(2x_1 + x_2 \le 100\), \(x_1 + x_2 \le 80\), \(x_1 \le 40\), \(x_1, x_2 \ge 0\), \(\max z = 30x_1 + 20x_2\)) grafik yöntemle çözünüz.

Çözüm

Üretim modelinin uygun bölgesi OABCD. z = 30x₁ + 20x₂ seviye doğruları gradyan yönünde kaydırıldığında bölgeden en son C(20, 60) köşesinde ayrılır: 20 masa ve 60 sandalye ile max z = 1800 TL.

Kısıt doğruları. \(2x_1 + x_2 = 100\) doğrusu \((50, 0)\) ve \((0, 100)\)’den, \(x_1 + x_2 = 80\) doğrusu \((80, 0)\) ve \((0, 80)\)’den geçer; \(x_1 = 40\) düşey bir doğrudur. \(O(0, 0)\) üç kısıtı da sağlar (\(0 \le 100\), \(0 \le 80\), \(0 \le 40\)); uygun taraflar hep \(O\)’nun bulunduğu taraftır.

Uygun bölge ve köşeler. Uygun bölge \(OABCD\) beşgenidir:

• \(O(0, 0)\);
• \(A\): \(x_2 = 0\) ve \(x_1 = 40\); \(A(40, 0)\);
• \(B\): \(x_1 = 40\) ve \(2x_1 + x_2 = 100\); \(x_2 = 20\), \(B(40, 20)\). Kontrol: \(40 + 20 = 60 \le 80\);
• \(C\): \(2x_1 + x_2 = 100\) ve \(x_1 + x_2 = 80\); çıkarırsak \(x_1 = 20\), \(x_2 = 60\), \(C(20, 60)\). Kontrol: \(20 \le 40\);
• \(D\): \(x_1 = 0\) ve \(x_1 + x_2 = 80\); \(D(0, 80)\). Kontrol: \(0 + 80 = 80 \le 100\).

Optimum. Gradyan \(\vec{c} = (30, 20)\)’dir. Örneğin \(z = 1200\) seviye doğrusu \((40, 0)\) ve \((0, 60)\)’tan geçer. Doğruyu \(\vec{c}\) yönünde kaydırdıkça \(z\) artar; bölgeden en son \(C(20, 60)\) köşesinde ayrılır. \(C\)’den geçen seviye doğrusu \(30x_1 + 20x_2 = 1800\)’dür. Köşe değerleri de bunu doğrular:

Tablo 3.4: Üretim modelinde köşelerdeki amaç değerleri

Köşe	\(O\)	\(A(40, 0)\)	\(B(40, 20)\)	\(C(20, 60)\)	\(D(0, 80)\)
\(z = 30x_1 + 20x_2\)	\(0\)	\(1200\)	\(1600\)	\(1800\)	\(1600\)

Optimal plan haftada \(x_1 = 20\) masa ve \(x_2 = 60\) sandalye üretmektir; en büyük kâr \(\max z = 1800\) TL’dir. Bu planda işçilik (\(2 \cdot 20 + 60 = 100\) saat) ve ahşap (\(20 + 60 = 80\) birim) tamamen kullanılır, masa talebinden ise \(40 - 20 = 20\) masalık pay boşta kalır. Yani optimal köşede sıfır olan aylak değişkenler işçilik ve ahşap kısıtlarınınkilerdir.

\(\blacksquare\)

Minimum problemlerinde de aynı reçete geçerlidir; yalnız seviye doğrusu gradyanın zıt yönünde kaydırılır. \(\ge\) kısıtlı minimum problemlerinde uygun bölge çoğu zaman sınırsızdır; bu durumda köşe tablosunu kullanmadan önce optimumun var olduğunu görmek gerekir.

Örnek 3.8 (Sınırsız bölgede bir minimum problemi) Örnek 1.10 diyetinin modelini grafik yöntemle çözünüz:

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

Çözüm

Uygun bölge sağa ve yukarı doğru sınırsızdır. Minimum problemi olduğu için z = 2x₁ + 3x₂ seviye doğrusu gradyanın tersi yönünde kaydırılır; bölgeye son dokunduğu nokta B(3, 1) köşesidir: min z = 9.

Kısıt doğruları ve yarı düzlemler. \(x_1 + x_2 = 4\) doğrusu \((4, 0)\) ve \((0, 4)\)’ten, \(x_1 + 3x_2 = 6\) doğrusu \((6, 0)\) ve \((0, 2)\)’den geçer. \(O(0, 0)\) iki kısıtı da sağlamaz (\(0 \ge 4\) ve \(0 \ge 6\) yanlıştır); uygun taraflar \(O\)’nun karşı taraflarıdır. Uygun bölge iki doğrunun “üstünde” kalan ve sağa, yukarı doğru sınırsız uzanan bölgedir.

Köşeler.

• \(A\): \(x_1 = 0\) ve \(x_1 + x_2 = 4\); \(A(0, 4)\). Kontrol: \(0 + 12 = 12 \ge 6\).
• \(B\): iki kısıt doğrusunun kesişimi. İkinci denklemden birinciyi çıkarırsak \(2x_2 = 2\), \(x_2 = 1\) ve \(x_1 = 3\); \(B(3, 1)\).
• \(C\): \(x_2 = 0\) ve \(x_1 + 3x_2 = 6\); \(C(6, 0)\). Kontrol: \(6 + 0 = 6 \ge 4\).

Diğer kesişimler uygun değildir: \((0, 2)\)’de \(0 + 2 = 2 < 4\), \((4, 0)\)’da \(4 + 0 = 4 < 6\) olur.

Optimumun varlığı. Gradyan \(\vec{c} = (2, 3)\)’tür; minimum problemi olduğu için seviye doğrusunu \(-\vec{c}\) yönünde, yani sol aşağıya doğru kaydırırız. Örneğin \(z = 18\) seviye doğrusu bölgeyi keser. Doğru aşağı indikçe \(z\) azalır ve doğru bölgeye en son \(B(3, 1)\) köşesinde değer; \(z = 9\) seviye doğrusunun altında bölgenin hiçbir noktası yoktur. Bölge sınırsız olduğu halde minimum vardır, çünkü \(z\) uygun bölge üzerinde alttan sınırlıdır; bunu şimdi kesin olarak gösterelim.

Bunu kesin olarak da görebiliriz. Amaç fonksiyonu, iki kısıtın sol taraflarının pozitif katsayılı bir birleşimidir:

\[2x_1 + 3x_2 = \tfrac32(x_1 + x_2) + \tfrac12(x_1 + 3x_2) \ge \tfrac32 \cdot 4 + \tfrac12 \cdot 6 = 9.\]

Yani her uygun noktada \(z \ge 9\)’dur ve \(B\)’de \(z = 9\)’dur.

Köşe tablosuyla karşılaştırma. Optimumun var olduğunu bildiğimiz için köşelerdeki değerleri karşılaştırabiliriz:

Tablo 3.5: Diyet probleminde köşelerdeki amaç değerleri

Köşe	\(A(0, 4)\)	\(B(3, 1)\)	\(C(6, 0)\)
\(z = 2x_1 + 3x_2\)	\(12\)	\(9\)	\(12\)

En küçük değer \(B\)’dedir: optimal diyet \(x_1 = 3\) kg \(B_1\) ve \(x_2 = 1\) kg \(B_2\) besinidir, en düşük maliyet \(\min z = 9\) TL’dir.

Aynı bölgede amaç maksimum yapılmak istenseydi optimum olmazdı: \(x_2 = 0\), \(x_1 = s \ge 6\) noktaları uygundur ve bu noktalarda \(z = 2s\) istenildiği kadar büyür. Köşelerdeki en büyük değer olan \(12\) o durumda bir anlam taşımazdı.

\(\blacksquare\)

Örnek 3.9 (Eşitlik kısıtlı karışım problemi) Örnek 1.4 yem karışımı modelini grafik yöntemle çözünüz:

\[ \begin{aligned} x_1 + x_2 &= 100 \\ x_1 + 5x_2 &\ge 300 \\ x_1 + 3x_2 &\le 250 \\ x_1, x_2 &\ge 0 \\ \min z &= 4x_1 + 10x_2 \end{aligned} \]

Çözüm

Karışım probleminde eşitlik kısıtı yüzünden uygun çözümler x₁ + x₂ = 100 doğrusunun kalın çizilen PQ parçasıdır; açık boyalı bant iki eşitsizliğin ortak bölgesidir. Uç noktalar P ve Q'dur. z = 4x₁ + 10x₂ seviye doğrusu gradyanın tersi yönünde kaydırıldığında parçadan en son Q(50, 50) noktasında ayrılır: min z = 700.

Eşitlik kısıtı bir yarı düzlem değil, bir doğru verir: uygun çözümler \(x_1 + x_2 = 100\) doğrusunun üzerindedir. Diğer iki kısıt bu doğrudan bir parça keser.

Doğru üzerinde \(x_2 = 100 - x_1\) yazalım. İkinci kısıt

\[x_1 + 5(100 - x_1) \ge 300 \iff 500 - 4x_1 \ge 300 \iff x_1 \le 50,\]

üçüncü kısıt

\[x_1 + 3(100 - x_1) \le 250 \iff 300 - 2x_1 \le 250 \iff x_1 \ge 25\]

olur. \(x_1 \ge 0\) ve \(x_2 = 100 - x_1 \ge 0\) koşulları bu aralıkta zaten sağlanır. Demek ki uygun bölge, uç noktaları \(P(25, 75)\) ve \(Q(50, 50)\) olan \(PQ\) doğru parçasıdır. \(P\), eşitlik doğrusu ile \(x_1 + 3x_2 = 250\) doğrusunun; \(Q\) ise eşitlik doğrusu ile \(x_1 + 5x_2 = 300\) doğrusunun kesişimidir.

Uygun bölge sınırlıdır; Sonuç 3.1 gereği iki uç noktaya bakmak yeter:

\[z(P) = 100 + 750 = 850, \qquad z(Q) = 200 + 500 = 700.\]

Minimum \(Q\)’dadır: \(x_1 = 50\) kg mısır, \(x_2 = 50\) kg soya küspesi ve \(\min z = 700\) TL. Gradyan \(\vec{c} = (4, 10)\)’dur; seviye doğrusu \(-\vec{c}\) yönünde kaydırılınca parçadan en son \(Q\)’da ayrılır. Bunu doğrudan da görebiliriz: doğru üzerinde \(z = 4x_1 + 10(100 - x_1)\), yani \(z = 1000 - 6x_1\)’dir ve \(x_1\) büyüdükçe azalır; \(x_1\)’in alabileceği en büyük değer \(50\) olduğundan en küçük maliyet \(1000 - 300 = 700\) TL’dir.

\(\blacksquare\)

3.4 Özel Durumlar

Şimdiye kadarki örneklerin hepsinde tek bir optimal köşe ya da bir optimal kenar bulduk. Grafik yöntem, bir problemin optimal çözümünün hiç olmayabileceğini ya da sonsuz çok olabileceğini de gözle gösterir. Üç durumu kısaca görelim; bunların simpleks tablosunda nasıl tanındığı Sınırsız çözüm ve alternatif optimal çözüm bölümünün konusudur.

Örnek 3.10 (Uygun çözümü olmayan problem) Aşağıdaki problemi grafik yöntemle inceleyiniz.

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

Çözüm

x₁ + x₂ ≤ 2 kısıtının bölgesi (alttaki üçgen) ile x₁ + 2x₂ ≥ 6 kısıtının bölgesi birinci bölgede ortak nokta içermez. Uygun çözüm yoktur; bu yüzden optimal çözüm de yoktur.

\(x_1 + x_2 = 2\) doğrusu \((2, 0)\) ve \((0, 2)\)’den geçer; \(O\) birinci kısıtı sağladığı için uygun taraf alttaki üçgendir. \(x_1 + 2x_2 = 6\) doğrusu \((6, 0)\) ve \((0, 3)\)’ten geçer; \(O\) ikinci kısıtı sağlamadığı için uygun taraf doğrunun üstüdür. Birinci bölgede bu iki bölgenin ortak noktası yoktur: üçgenin bütün noktaları ikinci doğrunun altında kalır.

Bunu cebirle de gösterelim. \(x_1, x_2 \ge 0\) ve \(x_1 + x_2 \le 2\) ise \(x_2 \le x_1 + x_2 \le 2\)’dir. O halde

\[x_1 + 2x_2 = (x_1 + x_2) + x_2 \le 2 + 2 = 4 < 6\]

olur ve ikinci kısıt sağlanamaz. Uygun çözümler kümesi boştur: \(K = \varnothing\). Uygun çözüm olmadığı için optimal çözüm de yoktur; amaç fonksiyonunun ne olduğu hiç önemli değildir. İki doğru aslında \((-2, 4)\) noktasında kesişir; işaret koşulları olmasaydı uygun çözüm bulunurdu. Demek ki \(x_1, x_2 \ge 0\) koşulları da kısıtlar kadar önemlidir.

\(\blacksquare\)

Örnek 3.11 (Sınırsız problem) Aşağıdaki problemi grafik yöntemle inceleyiniz.

\[ \begin{aligned} -x_1 + x_2 &\le 1 \\ x_1 - 2x_2 &\le 2 \\ x_1, x_2 &\ge 0 \\ \max z &= x_1 + x_2 \end{aligned} \]

Çözüm

Uygun bölge sağ yukarı doğru sınırsızdır ve z = x₁ + x₂ seviye doğruları gradyan yönünde ne kadar kaydırılırsa kaydırılsın bölgeyi kesmeye devam eder. z istenildiği kadar büyür; maksimum yoktur.

\(-x_1 + x_2 = 1\) doğrusu \((0, 1)\) ve \((1, 2)\)’den, \(x_1 - 2x_2 = 2\) doğrusu \((2, 0)\) ve \((4, 1)\)’den geçer. \(O(0, 0)\) iki kısıtı da sağlar; uygun bölge iki doğrunun arasında kalan ve sağ yukarı doğru sınırsız uzanan bölgedir. Köşeleri \((0, 0)\), \((0, 1)\) ve \((2, 0)\)’dır.

Gradyan \(\vec{c} = (1, 1)\)’dir. Seviye doğrusunu \(\vec{c}\) yönünde ne kadar kaydırırsak kaydıralım bölgeyi kesmeye devam eder. Bunu bir ışın üzerinde görelim: \(t \ge 0\) için \((2 + 2t,\ t)\) noktası

\[-(2 + 2t) + t = -2 - t \le 1, \qquad (2 + 2t) - 2t = 2 \le 2\]

olduğundan uygundur ve bu noktada \(z = 2 + 3t\)’dir. \(t\) büyüdükçe \(z\) sınırsız büyür; maksimum yoktur. Bu tür bir probleme sınırsız problem denir.

Köşelerdeki değerler \(0\), \(1\) ve \(2\)’dir. Köşe tablosuna bakıp “\(\max z = 2\)” demek yanlış olurdu; çünkü optimum hiç yoktur. Bu yüzden sınırsız bölgelerde köşeleri karşılaştırmadan önce optimumun var olduğunu seviye doğrularıyla görmek gerekir. Aynı bölgede \(\min z\) istenseydi ise optimum vardı: her uygun noktada \(z = x_1 + x_2 \ge 0\)’dır ve \(z(0, 0) = 0\)’dır.

\(\blacksquare\)

Örnek 3.12 (Sonsuz çok optimal çözüm) Aşağıdaki problemi grafik yöntemle çözünüz.

\[ \begin{aligned} x_1 + 2x_2 &\le 10 \\ x_1 &\le 6 \\ x_1, x_2 &\ge 0 \\ \max z &= x_1 + 2x_2 \end{aligned} \]

Çözüm

Amaç doğrusu z = x₁ + 2x₂, x₁ + 2x₂ = 10 kısıtına paraleldir. Seviye doğrusu kaydırıldığında bölgeden bir köşede değil, BC kenarının tamamı boyunca ayrılır; BC üzerindeki her nokta max z = 10 veren bir optimal çözümdür.

\(x_1 + 2x_2 = 10\) doğrusu \((10, 0)\) ve \((0, 5)\)’ten geçer, \(x_1 = 6\) düşey doğrudur; \(O\) iki kısıtı da sağlar. Uygun bölge köşeleri

\[O(0, 0), \quad A(6, 0), \quad B(6, 2), \quad C(0, 5)\]

olan dörtgendir; \(B\), \(x_1 = 6\) ile \(x_1 + 2x_2 = 10\) doğrularının kesişimidir (\(2x_2 = 4\)). Köşelerde \(z\) değerleri \(0\), \(6\), \(10\), \(10\)’dur.

Gradyan \(\vec{c} = (1, 2)\)’dir ve seviye doğruları \(x_1 + 2x_2 = 10\) kısıt doğrusuna paraleldir. Seviye doğrusu \(\vec{c}\) yönünde kaydırılınca bölgeden bir köşede değil, \(BC\) kenarının tamamı boyunca ayrılır. Teorem 3.1 teoreminin ikinci kısmına göre \(B\) ile \(C\)’nin her konveks kombinasyonu optimaldir. Gerçekten \(0 \le \lambda \le 1\) için

\[\lambda B + (1 - \lambda)C = (6\lambda,\ 5 - 3\lambda)\]

noktasında \(z = 6\lambda + 10 - 6\lambda = 10\)’dur. Problemin sonsuz çok optimal çözümü vardır ve \(\max z = 10\)’dur. Optimal değer tektir; tek olmayan, bu değeri veren noktalardır. Böyle çözümlere alternatif optimal çözümler denir.

\(\blacksquare\)

Bu bölümde amaç fonksiyonunun optimumunu, varsa, uygun bölgenin bir uç noktasında aldığını; uç noktaların da tam olarak uygun temel çözümler olduğunu gördük. İki değişkende uç noktalar köşelerdir ve grafik yöntemle bulunur. Daha büyük problemlerde ise bütün uygun temel çözümleri taramak çok pahalıdır. Bir sonraki bölümde, Simpleks yöntem bölümünde, bir uygun temel çözümden başlayıp amaç değerini iyileştiren komşu bir uygun temel çözüme geçen ve optimuma sonlu adımda ulaşan yöntemi kuracağız.