10 Duyarlılık Analizi
Buraya kadar bir lineer programlama problemini hep sabit verilerle çözdük: amaç katsayıları \(c_j\), kısıt katsayıları \(a_{ij}\) ve sağ taraflar \(b_i\) kesin olarak biliniyordu. Gerçek bir modelde bu sayılar çoğu zaman tahmindir. Bir ürünün kârı piyasaya göre değişir, eldeki hammadde miktarı bir sonraki ay farklı olabilir. O zaman doğal bir soru ortaya çıkar: Bulduğumuz optimal çözüm bu sayılardaki değişimlere ne kadar dayanıklıdır? Kâr biraz artarsa aynı üretim planı yine en iyisi midir? Hammadde azalırsa hangi değişkenler üretilmeye devam eder?
Bu soruları her seferinde problemi baştan çözerek cevaplamak gerekmez. Optimal tablo, değişimin etkisini okumak için gereken her şeyi zaten içerir. Bu bölümde önce optimal tablonun optimal bazın tersiyle nasıl doğrudan yazıldığını göreceğiz. Sonra amaç katsayılarındaki ve sağ taraf sabitlerindeki değişimlerin tabloda hangi sayıları etkilediğini bulup optimumluğu bozmayan değişim aralıklarını hesaplayacağız. Önceki bölümlerdeki simpleks yöntem (Simpleks yöntem, Büyük M yöntemi) burada başlangıç noktasıdır: duyarlılık analizi problem çözüldükten sonra yapılır.
10.1 Duyarlılık Analizi Nedir?
Önce neyi incelediğimizi kesinleştirelim.
Tanım 10.1 (Duyarlılık analizi) Bir lineer programlama probleminin optimal çözümünün, sağ taraf sabitlerinde (\(b_i\)) ve amaç fonksiyonu katsayılarında (\(c_j\)) meydana gelebilecek değişimler göz önüne alınarak incelenmesine duyarlılık analizi denir.
Yani duyarlılık analizinde problemi çözdükten sonra verilerden birini değiştiririz ve “optimal tablo ne kadar değişir?” diye sorarız. En sık sorulan soru bir aralık sorusudur: Bir \(c_j\) ya da bir \(b_i\) hangi aralıkta değişirse optimumluk bozulmaz, yani optimal tablonun bazı (temeldeki değişkenler) aynı kalır? Bu aralığa o sayının değişim aralığı diyeceğiz.
Bu bölümde iki tür değişimi inceleyeceğiz:
- Amaç fonksiyonu katsayılarındaki (\(c_j\)) değişim. Burada da iki durum ayrılır: değişen katsayı temel dışı (bazda olmayan) bir değişkene ya da temelde olan (bazdaki) bir değişkene ait olabilir.
- Sağ taraf sabitlerindeki (\(b_i\)) değişim.
Değişimlerin her birinde yalnız bir sayının değiştiğini, diğer bütün verilerin sabit kaldığını varsayacağız.
10.2 Optimal Tablonun \(B^{-1}\) ile Yazılması
Duyarlılık analizinin anahtarı şu gözlemdir: bir baz seçildiği anda o baza ait simpleks tablosunun her sayısı, bazın sütunlarından kurulan matrisin tersiyle hesaplanabilir. Simpleks iterasyonlarını tekrar yapmaya gerek kalmaz.
Problemin standart formu (Tanım 1.7) \[ \begin{aligned} A\vec{x} &= \vec{b} \\ \vec{x} &\ge 0 \\ \max \ (\text{ya da } \min) \ z &= \vec{c}^{\,T}\vec{x} \end{aligned} \] olsun. \(A\)’nın sütunları \(v_1, \dots, v_n\), sağ taraf vektörü \(v_0 = \vec{b}\)’dir.
Tanım 10.2 (Baz matrisi) Bir simpleks tablosunun \(x_B\) sütununda yukarıdan aşağı \(x_{B_1}, x_{B_2}, \dots, x_{B_m}\) değişkenleri bulunsun. Standart formun bu değişkenlere ait \(v_{B_1}, \dots, v_{B_m}\) sütunlarını aynı sırayla yan yana yazarak elde edilen \(m \times m\) matrise tablonun baz matrisi denir ve \(B\) ile gösterilir: \[ B = \begin{bmatrix} v_{B_1} & v_{B_2} & \cdots & v_{B_m} \end{bmatrix}. \] Baz maliyetleri de aynı sırayla \(\vec{c}_B = (c_{B_1}, \dots, c_{B_m})^T\) vektörünü oluşturur.
Yani \(B\), temel değişkenlerin ilk baştaki (standart formdaki) katsayılar matrisidir. Tablodaki \(y_{ij}\) değerlerinden değil, problemin kendi katsayılarından kurulur. Baz vektörleri lineer bağımsız olduğundan \(B\)’nin tersi vardır. Sütunların sırası tablonun satır sırasını izler; sıra değişirse \(B^{-1}\)’in satırları da aynı biçimde yer değiştirir.
Teorem 10.1 (Tablonun \(B^{-1}\) ile hesabı) Baz matrisi \(B\) olan simpleks tablosunda
- tablonun \(v_j\) sütunu \(\vec{y}_j = B^{-1} v_j\) (\(j = 1, \dots, n\)) ve \(v_0\) sütunu \(B^{-1}\vec{b}\)’dir;
- simpleks kriterleri \(z_j - c_j = \vec{c}_B^{\,T} B^{-1} v_j - c_j\), amaç değeri \(z_0 = \vec{c}_B^{\,T} B^{-1} \vec{b}\)’dir.
İspat
1. Tablonun \(v_j\) sütunundaki \(y_{1j}, \dots, y_{mj}\) sayıları, \(v_j\)’nin baz vektörleri cinsinden yazılışının katsayılarıdır (Simpleks yöntem bölümündeki tanım): \[ v_j = y_{1j} v_{B_1} + y_{2j} v_{B_2} + \dots + y_{mj} v_{B_m}. \] Sağ taraf, sütunları \(v_{B_i}\) olan \(B\) matrisinin \(\vec{y}_j = (y_{1j}, \dots, y_{mj})^T\) vektörüyle çarpımıdır; yani eşitlik \(v_j = B\vec{y}_j\) demektir. \(B\) tersinir olduğundan iki yanı soldan \(B^{-1}\) ile çarparak \(\vec{y}_j = B^{-1} v_j\) buluruz. Aynı akıl yürütme \(j = 0\) için \(v_0 = \vec{b}\)’ye uygulanır ve \(v_0\) sütunu \(B^{-1}\vec{b}\) olur.
2. Tanım gereği \(z_j = \vec{c}_B^{\,T} \vec{y}_j\) ve \(z_0 = \vec{c}_B^{\,T} \vec{y}_0\)’dır. Birinci kısımdaki ifadeleri yerine koymak yeter. \(\blacksquare\)
Yani optimal baz bir kez bilindiğinde tablonun gövdesi (\(v_0\) sütunu ve bütün \(y_{ij}\)’ler) yalnız \(B^{-1}\), \(A\) ve \(\vec{b}\)’ye; son satırı ise bunlara ek olarak amaç katsayılarına bağlıdır. Duyarlılık analizinin bütün hesapları bu ayrıma dayanır.
\(B^{-1}\)’i her seferinde ayrıca hesaplamak da gerekmeyebilir; çoğu zaman tablonun içinde hazır durur.
Önerme 10.1 (\(B^{-1}\) tablonun içinde) Standart formda \(v_{k_1}, \dots, v_{k_m}\) sütunları sırasıyla \(m \times m\) birim matrisin \(e_1, \dots, e_m\) sütunları olsun (örneğin \(\le\) kısıtların aylak değişkenlerinin sütunları). Bu durumda herhangi bir tabloda \(v_{k_1}, \dots, v_{k_m}\) sütunları, sırasıyla, o tablonun baz matrisinin tersi \(B^{-1}\)’in sütunlarıdır.
Bir \(\ge\) kısıtın artık değişkeninin sütunu \(-e_i\) ise o tablodaki sütununun \(-1\) katı \(B^{-1}\)’in \(i\). sütunudur.
İspat
Teorem 10.1 gereği tablonun \(v_{k_i}\) sütunu \(B^{-1} v_{k_i} = B^{-1} e_i\)’dir. Bir matrisi \(e_i\) ile çarpmak onun \(i\). sütununu verir; o hâlde bu sütun \(B^{-1}\)’in \(i\). sütunudur. Artık değişken için tablonun sütunu \(B^{-1}(-e_i) = -B^{-1}e_i\) olur; \(-1\) ile çarpınca yine \(B^{-1}\)’in \(i\). sütunu elde edilir. \(\blacksquare\)
Yani bütün kısıtları \(\le\) olan bir problemde \(B^{-1}\), optimal tablonun aylak değişken sütunlarında okunur. \(\ge\) kısıtlı bir problemde yapay değişkenin sütunu bazdan çıkınca atıldığı için (Büyük M yöntemi) o kısıtın birim sütunu tabloda kalmaz; bu durumda \(B^{-1}\) ya artık değişkenin sütunundan işaret değiştirilerek okunur ya da \(B\)’nin tersi doğrudan alınır. \(2 \times 2\) bir matrisin tersi \[ B = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \ \Longrightarrow \ B^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}, \quad ad - bc \ne 0 \] formülüyle bulunur (bkz. Lineer Cebir, tersin ek matrisle formülü).
- Standart form. Problemi standart forma getir; \(A\)’nın \(v_j\) sütunlarını, \(\vec{b}\)’yi ve \(c_j\)’leri yaz. Yapay değişkenlere gerek yoktur.
- Baz matrisi. Optimal bazdaki değişkenlerin standart formdaki sütunlarını, tablonun satır sırasıyla yan yana yazarak \(B\)’yi kur ve \(B^{-1}\)’i hesapla.
- Gövde. \(v_0\) sütunu \(B^{-1}\vec{b}\), her \(v_j\) sütunu \(B^{-1}v_j\)’dir. Baz vektörlerinin sütunları birim vektördür.
- Son satır. \(z_j - c_j = \vec{c}_B^{\,T}\vec{y}_j - c_j\) ve \(z_0 = \vec{c}_B^{\,T} B^{-1}\vec{b}\). Minimumda bütün \(z_j - c_j \le 0\), maksimumda bütün \(z_j - c_j \ge 0\) ise tablo optimaldir.
Bölüm boyunca kullanacağımız problemi önce simpleks yöntemle çözelim, sonra optimal tablosunu \(B^{-1}\) ile doğrudan yazalım.
Örnek 10.1 (Duyarlılık örneğinin simpleks çözümü) \[ \begin{aligned} \tfrac{1}{3}x_1 + \tfrac{1}{3}x_2 + \tfrac{1}{3}x_3 &\le 1 \\ \tfrac{1}{3}x_1 + \tfrac{4}{3}x_2 + \tfrac{7}{3}x_3 &\le 3 \\ x_1, x_2, x_3 &\ge 0 \\ \max z &= 2x_1 + 3x_2 + x_3 \end{aligned} \] problemini simpleks yöntemle çözünüz.
Çözüm
Standart form. İki \(\le\) kısıtına \(x_4\) ve \(x_5\) aylak değişkenlerini ekleriz: \[ \begin{aligned} \tfrac{1}{3}x_1 + \tfrac{1}{3}x_2 + \tfrac{1}{3}x_3 + x_4 &= 1 \\ \tfrac{1}{3}x_1 + \tfrac{4}{3}x_2 + \tfrac{7}{3}x_3 + x_5 &= 3 \\ x_j &\ge 0, \quad j = \overline{1,5} \\ \max z &= 2x_1 + 3x_2 + x_3 + 0x_4 + 0x_5 \end{aligned} \] Sağ taraflar negatif değildir ve \(v_4\), \(v_5\) birim matrisi oluşturur; standart form simpleks yöntem ile çözülebilir haldedir (Tanım 1.9). Başlangıç bazı \((v_4, v_5)\)’tir ve \(z_j - c_j = -c_j\) olur.
Başlangıç tablosu. Maksimum probleminde en negatif \(z_j - c_j\) girer, bütün \(z_j - c_j \ge 0\) olunca optimal tabloya ulaşılır. En negatif kriter \(-3\) olduğundan \(v_2\) baza girer. Oranlar \(1 / \tfrac{1}{3} = 3\) ve \(3 / \tfrac{4}{3} = \tfrac{9}{4}\); en küçüğü \(x_5\) satırındadır, \(v_5\) bazdan çıkar ve pivot \(\tfrac{4}{3}\)’tür.
| \(c_j\) | \(2\) | \(3\) | \(1\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | Oran |
| \(x_4\) | \(0\) | \(1\) | \(\frac{1}{3}\) | \(\frac{1}{3}\) | \(\frac{1}{3}\) | \(1\) | \(0\) | \(\frac{1}{1/3} = 3\) |
| \(x_5\) | \(0\) | \(3\) | \(\frac{1}{3}\) | \([\frac{4}{3}]\) | \(\frac{7}{3}\) | \(0\) | \(1\) | \(\frac{3}{4/3} = \frac{9}{4} \Rightarrow\) |
| \(z_j - c_j\) | \(z_0 = 0\) | \(-2\) | \(-3 \Uparrow\) | \(-1\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot satırı \(\tfrac{4}{3}\)’e bölünür, yani \(\tfrac{3}{4}\) ile çarpılır ve \(x_2\) satırı olur: \[ \big(3 \mid \tfrac{1}{3}, \tfrac{4}{3}, \tfrac{7}{3}, 0, 1\big) \cdot \tfrac{3}{4} = \big(\tfrac{9}{4} \mid \tfrac{1}{4}, 1, \tfrac{7}{4}, 0, \tfrac{3}{4}\big). \] \(x_4\) satırından yeni satırın \(\tfrac{1}{3}\) katını çıkarırız; \(z_j - c_j\) satırına yeni satırın \(3\) katını ekleriz. Örneğin \(x_4\) satırının \(v_0\) değeri \(1 - \tfrac{1}{3} \cdot \tfrac{9}{4} = \tfrac{1}{4}\), \(v_3\) sütununun kriteri \(-1 + 3 \cdot \tfrac{7}{4} = \tfrac{17}{4}\) olur.
Tek negatif kriter \(-\tfrac{5}{4}\) olduğundan \(v_1\) baza girer. Oranlar \(\tfrac{1}{4} / \tfrac{1}{4} = 1\) ve \(\tfrac{9}{4} / \tfrac{1}{4} = 9\); \(v_4\) bazdan çıkar, pivot \(\tfrac{1}{4}\)’tür.
| \(c_j\) | \(2\) | \(3\) | \(1\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | Oran |
| \(x_4\) | \(0\) | \(\frac{1}{4}\) | \([\frac{1}{4}]\) | \(0\) | \(-\frac{1}{4}\) | \(1\) | \(-\frac{1}{4}\) | \(\frac{1/4}{1/4} = 1 \Rightarrow\) |
| \(x_2\) | \(3\) | \(\frac{9}{4}\) | \(\frac{1}{4}\) | \(1\) | \(\frac{7}{4}\) | \(0\) | \(\frac{3}{4}\) | \(\frac{9/4}{1/4} = 9\) |
| \(z_j - c_j\) | \(z_0 = \frac{27}{4}\) | \(-\frac{5}{4} \Uparrow\) | \(0\) | \(\frac{17}{4}\) | \(0\) | \(\frac{9}{4}\) |
İkinci iterasyon. Pivot satırı \(4\) ile çarpılır ve \(x_1\) satırı olur: \((1 \mid 1, 0, -1, 4, -1)\). \(x_2\) satırından bu satırın \(\tfrac{1}{4}\) katını çıkarırız: \[ \big(\tfrac{9}{4} - \tfrac{1}{4} \mid 0,\ 1,\ \tfrac{7}{4} + \tfrac{1}{4},\ -1,\ \tfrac{3}{4} + \tfrac{1}{4}\big) = (2 \mid 0, 1, 2, -1, 1). \] \(z_j - c_j\) satırına bu satırın \(\tfrac{5}{4}\) katını ekleriz: \(z_0 = \tfrac{27}{4} + \tfrac{5}{4} = 8\), \(v_3\) için \(\tfrac{17}{4} - \tfrac{5}{4} = 3\), \(v_4\) için \(0 + 5 = 5\), \(v_5\) için \(\tfrac{9}{4} - \tfrac{5}{4} = 1\).
| \(c_j\) | \(2\) | \(3\) | \(1\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) |
| \(x_1\) | \(2\) | \(1\) | \(1\) | \(0\) | \(-1\) | \(4\) | \(-1\) |
| \(x_2\) | \(3\) | \(2\) | \(0\) | \(1\) | \(2\) | \(-1\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = 8\) | \(0\) | \(0\) | \(3\) | \(5\) | \(1\) |
Bütün \(z_j - c_j \ge 0\) olduğundan tablo optimaldir. Optimal çözüm \(x_1 = 1\), \(x_2 = 2\), \(x_3 = x_4 = x_5 = 0\) ve \(\max z = 2 \cdot 1 + 3 \cdot 2 = 8\)’dir. Temel değişkenler \(x_1\) ve \(x_2\), temel dışı değişkenler \(x_3\), \(x_4\) ve \(x_5\)’tir. \(\blacksquare\)
Örnek 10.2 (Optimal tablonun doğrudan yazılması) Önceki örnekteki (Örnek 10.1) problemin optimal bazının \((v_1, v_2)\) olduğu, \(x_1\) satırının üstte, \(x_2\) satırının altta yazıldığı biliniyor. Optimal tabloyu simpleks iterasyonları yapmadan, \(B^{-1}\) ile yazınız.
Çözüm
Baz matrisi. Temel değişkenler \(x_1\) ve \(x_2\)’dir; standart formdaki sütunları \(v_1 = (\tfrac{1}{3}, \tfrac{1}{3})^T\) ve \(v_2 = (\tfrac{1}{3}, \tfrac{4}{3})^T\)’tür. Tablonun satır sırasıyla \[ B = \begin{bmatrix} v_1 & v_2 \end{bmatrix} = \begin{bmatrix} \tfrac{1}{3} & \tfrac{1}{3} \\[1mm] \tfrac{1}{3} & \tfrac{4}{3} \end{bmatrix}. \] \(\det B = \tfrac{4}{9} - \tfrac{1}{9} = \tfrac{1}{3} \ne 0\) olduğundan \[ B^{-1} = 3 \begin{bmatrix} \tfrac{4}{3} & -\tfrac{1}{3} \\[1mm] -\tfrac{1}{3} & \tfrac{1}{3} \end{bmatrix} = \begin{bmatrix} 4 & -1 \\ -1 & 1 \end{bmatrix}. \] Kontrol: \(B B^{-1}\)’in ilk satırı \(\big(\tfrac{4}{3} - \tfrac{1}{3},\ -\tfrac{1}{3} + \tfrac{1}{3}\big) = (1, 0)\), ikinci satırı \(\big(\tfrac{4}{3} - \tfrac{4}{3},\ -\tfrac{1}{3} + \tfrac{4}{3}\big) = (0, 1)\).
Gövde. Teorem 10.1 gereği: \[ \begin{aligned} B^{-1}\vec{b} &= \begin{bmatrix} 4 & -1 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 3 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \\[2mm] B^{-1} v_3 &= \begin{bmatrix} 4 & -1 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} \tfrac{1}{3} \\[1mm] \tfrac{7}{3} \end{bmatrix} = \begin{bmatrix} -1 \\ 2 \end{bmatrix}, \\[2mm] B^{-1} v_4 &= B^{-1} e_1 = \begin{bmatrix} 4 \\ -1 \end{bmatrix}, \qquad B^{-1} v_5 = B^{-1} e_2 = \begin{bmatrix} -1 \\ 1 \end{bmatrix}. \end{aligned} \] Örneğin \(B^{-1}v_3\)’ün ilk bileşeni \(4 \cdot \tfrac{1}{3} - \tfrac{7}{3} = -1\), ikincisi \(-\tfrac{1}{3} + \tfrac{7}{3} = 2\)’dir. \(v_1\) ve \(v_2\) baz vektörleri olduğundan sütunları \((1, 0)^T\) ve \((0, 1)^T\)’dir.
Son satır. \(\vec{c}_B = (2, 3)^T\) ile \[ \begin{aligned} z_3 - c_3 &= (2,\ 3)\begin{pmatrix} -1 \\ 2 \end{pmatrix} - 1 = 4 - 1 = 3, \\[1mm] z_4 - c_4 &= (2,\ 3)\begin{pmatrix} 4 \\ -1 \end{pmatrix} - 0 = 5, \\[1mm] z_5 - c_5 &= (2,\ 3)\begin{pmatrix} -1 \\ 1 \end{pmatrix} - 0 = 1, \\[1mm] z_0 &= (2,\ 3)\begin{pmatrix} 1 \\ 2 \end{pmatrix} = 8 . \end{aligned} \] Bulunan sayılar optimal tablodaki (Tablo 10.3) sayıların aynısıdır. Tabloya bakınca Önerme 10.1 da doğrulanır: aylak değişkenlerin \(v_4\) ve \(v_5\) sütunları yan yana \(B^{-1}\)’i verir. Bütün \(z_j - c_j \ge 0\) olduğundan bu tablonun optimal olduğunu iterasyonlara bakmadan da söyleyebiliriz. \(\blacksquare\)
Aynı yolu biri maksimum, biri minimum olan iki küçük problemde deneyelim.
Örnek 10.3 (İki değişkenli bir maksimum probleminin optimal tablosu) \[ \begin{aligned} x_1 + x_2 &\le 4 \\ 2x_1 + x_2 &\le 6 \\ x_1, x_2 &\ge 0 \\ \max z &= 3x_1 + 2x_2 \end{aligned} \] probleminin optimumu \((2, 2)\) köşesindedir. Optimal tabloyu \(B^{-1}\) ile yazınız ve optimal olduğunu gösteriniz.
Çözüm
Standart form. \(x_3\), \(x_4\) aylak değişkenleriyle \[ \begin{aligned} x_1 + x_2 + x_3 &= 4 \\ 2x_1 + x_2 + x_4 &= 6 \\ x_j &\ge 0, \quad j = \overline{1,4} \\ \max z &= 3x_1 + 2x_2 + 0x_3 + 0x_4 \end{aligned} \] \((2, 2)\) köşesinde \(x_1 = x_2 = 2\) ve iki kısıt da eşitlikle sağlanır (\(2 + 2 = 4\), \(4 + 2 = 6\)), yani \(x_3 = x_4 = 0\). Temel değişkenler \(x_1\) ve \(x_2\)’dir.
Baz matrisi. Satırları \(x_1\), \(x_2\) sırasıyla yazalım: \[ B = \begin{bmatrix} 1 & 1 \\ 2 & 1 \end{bmatrix}, \quad \det B = 1 - 2 = -1, \quad B^{-1} = -\begin{bmatrix} 1 & -1 \\ -2 & 1 \end{bmatrix} = \begin{bmatrix} -1 & 1 \\ 2 & -1 \end{bmatrix}. \]
Gövde. \(B^{-1}\vec{b} = (2, 2)^T\) (\(-4 + 6 = 2\) ve \(8 - 6 = 2\)). Aylak sütunlar \(e_1\) ve \(e_2\) olduğundan \(B^{-1}v_3 = (-1, 2)^T\) ve \(B^{-1}v_4 = (1, -1)^T\), yani \(B^{-1}\)’in sütunlarıdır (Önerme 10.1).
Son satır. \(\vec{c}_B = (3, 2)^T\): \[ \begin{aligned} z_3 - c_3 &= (3,\ 2)\begin{pmatrix} -1 \\ 2 \end{pmatrix} - 0 = 1, & z_4 - c_4 &= (3,\ 2)\begin{pmatrix} 1 \\ -1 \end{pmatrix} - 0 = 1, \end{aligned} \] \(z_0 = 3 \cdot 2 + 2 \cdot 2 = 10\).
| \(c_j\) | \(3\) | \(2\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_1\) | \(3\) | \(2\) | \(1\) | \(0\) | \(-1\) | \(1\) |
| \(x_2\) | \(2\) | \(2\) | \(0\) | \(1\) | \(2\) | \(-1\) |
| \(z_j - c_j\) | \(z_0 = 10\) | \(0\) | \(0\) | \(1\) | \(1\) |
Maksimum probleminde bütün \(z_j - c_j \ge 0\) olduğundan tablo optimaldir: \(x_1 = x_2 = 2\), \(\max z = 10\). Köşelerle karşılaştıralım: uygun bölgenin köşeleri \((0, 0)\), \((3, 0)\), \((2, 2)\), \((0, 4)\)’tür ve \(z\) bunlarda sırasıyla \(0\), \(9\), \(10\), \(8\) değerini alır. \(\blacksquare\)
Örnek 10.4 (Artık değişkenli bir minimum probleminin optimal tablosu) \[ \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} \] probleminin optimumu \((3, 1)\) köşesindedir (Örnek 3.8). Optimal tabloyu \(B^{-1}\) ile yazınız ve \(B^{-1}\)’in tabloda nerede göründüğünü belirtiniz.
Çözüm
Standart form. \(\ge\) kısıtlardan \(x_3\), \(x_4\) artık değişkenlerini çıkarırız: \[ \begin{aligned} x_1 + x_2 - x_3 &= 4 \\ x_1 + 3x_2 - x_4 &= 6 \\ x_j &\ge 0, \quad j = \overline{1,4} \\ \min z &= 2x_1 + 3x_2 + 0x_3 + 0x_4 \end{aligned} \] Bu standart form birim matris içermez; simpleks yöntemle çözerken yapay değişken gerekirdi. Optimal tabloyu \(B^{-1}\) ile yazarken ise yapay değişkene hiç ihtiyaç yoktur. \((3, 1)\)’de iki kısıt da eşitlikle sağlanır, \(x_3 = x_4 = 0\); temel değişkenler \(x_1\), \(x_2\)’dir.
Baz matrisi. \[ B = \begin{bmatrix} 1 & 1 \\ 1 & 3 \end{bmatrix}, \quad \det B = 3 - 1 = 2, \quad B^{-1} = \frac{1}{2}\begin{bmatrix} 3 & -1 \\ -1 & 1 \end{bmatrix} = \begin{bmatrix} \tfrac{3}{2} & -\tfrac{1}{2} \\[1mm] -\tfrac{1}{2} & \tfrac{1}{2} \end{bmatrix}. \]
Gövde. \(B^{-1}\vec{b} = (3, 1)^T\) (\(6 - 3 = 3\) ve \(-2 + 3 = 1\)). Artık sütunları \(v_3 = -e_1\), \(v_4 = -e_2\) olduğundan \[ B^{-1}v_3 = -B^{-1}e_1 = \begin{bmatrix} -\tfrac{3}{2} \\[1mm] \tfrac{1}{2} \end{bmatrix}, \qquad B^{-1}v_4 = -B^{-1}e_2 = \begin{bmatrix} \tfrac{1}{2} \\[1mm] -\tfrac{1}{2} \end{bmatrix}. \]
Son satır. \(\vec{c}_B = (2, 3)^T\): \[ \begin{aligned} z_3 - c_3 &= (2,\ 3)\begin{pmatrix} -\tfrac{3}{2} \\[1mm] \tfrac{1}{2} \end{pmatrix} - 0 = -3 + \tfrac{3}{2} = -\tfrac{3}{2}, \\[1mm] z_4 - c_4 &= (2,\ 3)\begin{pmatrix} \tfrac{1}{2} \\[1mm] -\tfrac{1}{2} \end{pmatrix} - 0 = 1 - \tfrac{3}{2} = -\tfrac{1}{2}, \end{aligned} \] \(z_0 = 2 \cdot 3 + 3 \cdot 1 = 9\).
| \(c_j\) | \(2\) | \(3\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_1\) | \(2\) | \(3\) | \(1\) | \(0\) | \(-\frac{3}{2}\) | \(\frac{1}{2}\) |
| \(x_2\) | \(3\) | \(1\) | \(0\) | \(1\) | \(\frac{1}{2}\) | \(-\frac{1}{2}\) |
| \(z_j - c_j\) | \(z_0 = 9\) | \(0\) | \(0\) | \(-\frac{3}{2}\) | \(-\frac{1}{2}\) |
Minimum probleminde bütün \(z_j - c_j \le 0\) olduğundan tablo optimaldir: \(x_1 = 3\), \(x_2 = 1\), \(\min z = 9\). Tabloda \(B^{-1}\)’in sütunları doğrudan görünmez; artık değişkenlerin \(v_3\) ve \(v_4\) sütunlarının \(-1\) katları \(B^{-1}\)’i verir (Önerme 10.1). \(\blacksquare\)
Teorem 10.1’nun en önemli sonucu, hangi verinin tablonun hangi kısmını etkilediğini söylemesidir.
Sonuç 10.1 (Değişimin tablodaki etkisi) Bir optimal tabloda bazı değiştirmeden:
- Amaç katsayıları \(c_j\) değişirse tablonun gövdesi (\(v_0\) sütunu ve bütün \(y_{ij}\)’ler) aynı kalır; yalnız \(z_j - c_j\) satırı ve \(z_0\) değişir.
- Sağ taraf \(\vec{b}\) değişirse bütün \(y_{ij}\)’ler ve bütün \(z_j - c_j\) (\(j \ge 1\)) değerleri aynı kalır; yalnız \(v_0\) sütunu ve \(z_0\) değişir.
İspat
Teorem 10.1 gereği \(y_{ij}\)’ler \(B^{-1}v_j\)’den, \(v_0\) sütunu \(B^{-1}\vec{b}\)’den gelir. Birincisinde \(\vec{c}\) yoktur; ikincisinde yalnız \(\vec{b}\) vardır. \(z_j - c_j = \vec{c}_B^{\,T} B^{-1} v_j - c_j\) ifadesinde \(\vec{b}\) bulunmaz, amaç katsayıları bulunur. \(z_0 = \vec{c}_B^{\,T} B^{-1}\vec{b}\) ise ikisine de bağlıdır. \(\blacksquare\)
Yani:
- \(c_j\) değişince uygunluk (\(v_0 \ge 0\)) bozulmaz, yalnız optimallik koşulu yeniden kontrol edilir.
- \(b_i\) değişince optimallik koşulu bozulmaz, yalnız uygunluk koşulu yeniden kontrol edilir.
Bölümün geri kalanı bu iki kontrolden ibarettir.
10.3 Amaç Fonksiyonu Katsayılarındaki Değişim
Bir \(c_j\) değişince tablonun gövdesi aynı kaldığı için optimal çözümün değişkenleri de aynı kalır; bu çözümün optimal olmaya devam edip etmediği yalnız son satıra bağlıdır. Değişen katsayının temel dışı ya da temelde olan bir değişkene ait olmasına göre son satırın ne kadarının değiştiği farklıdır.
Temel Dışı Değişkenlerin Katsayılarındaki Değişim
Temel dışı bir değişkenin katsayısı \(c_B\) vektöründe görünmez. Bu yüzden değişim yalnız kendi sütununa dokunur.
Önerme 10.2 (Temel dışı değişkenin katsayısı) Optimal tabloda \(x_k\) temel dışı bir değişken olsun ve \(c_k\) yerine \(c_k'\) gelsin. Bu durumda yalnız \(v_k\) sütununun simpleks kriteri değişir ve \(z_k - c_k'\) olur; \(z_0\) ve diğer bütün \(z_j - c_j\) değerleri aynı kalır. Tablo
- maksimum probleminde \(c_k' \le z_k\) iken,
- minimum probleminde \(c_k' \ge z_k\) iken
optimal kalır. Bu aralıkta optimal çözüm ve optimal değer değişmez.
İspat
\(c_k\), \(x_k\) temel dışı olduğu için \(\vec{c}_B\)’nin bileşeni değildir. \(z_j = \vec{c}_B^{\,T}\vec{y}_j\) değerleri ve \(z_0 = \vec{c}_B^{\,T} B^{-1}\vec{b}\) yalnız \(\vec{c}_B\)’ye bağlı olduğundan hiçbiri değişmez. \(z_j - c_j\) farkları arasında \(c_k\)’yı içeren tek fark \(j = k\) olanıdır; o da \(z_k - c_k'\) olur. Tablonun gövdesi zaten değişmez (Sonuç 10.1).
Maksimum probleminde optimallik koşulu bütün \(z_j - c_j \ge 0\)’dır. Diğer kriterler optimal tablodakilerle aynı olduğundan zaten \(\ge 0\)’dır; geriye \(z_k - c_k' \ge 0\), yani \(c_k' \le z_k\) kalır. Minimumda koşul \(z_k - c_k' \le 0\), yani \(c_k' \ge z_k\)’dır. Bu durumda tablonun temel çözümü Teorem 4.3 gereği optimaldir; çözüm ve \(z_0\) değişmediği için optimal değer de aynıdır. \(\blacksquare\)
Yani temel dışı bir değişkenin katsayısının sınırı, o sütunun \(z_k\) değeridir. Maksimum probleminde \(c_k\), \(z_k\)’yı aşarsa \(x_k\)’yı üretmek kârlı hâle gelir ve \(v_k\) baza girmek ister; minimumda \(c_k\), \(z_k\)’nın altına inerse aynı şey olur. Sınırın tam üstünde \(z_k - c_k = 0\)’dır; bulunan çözüm yine optimaldir; \(v_k\) sütununda pozitif eleman varsa ve çözüm dejenere değilse alternatif optimal çözüm de vardır (Teorem 7.2).
- Optimal tablonun \(c_j\) satırında \(c_k\) yerine sembol olarak \(c_k\) yaz; tablonun geri kalanı aynen kalır.
- Yalnız \(v_k\) sütununun kriterini hesapla: \(z_k - c_k = \vec{c}_B^{\,T}\vec{y}_k - c_k\).
- Maksimumda \(z_k - c_k \ge 0\), minimumda \(z_k - c_k \le 0\) eşitsizliğini \(c_k\) için çöz.
Örnek 10.5 (Temel dışı \(x_3\)’ün katsayısının değişim aralığı) Optimal tablosu Tablo 10.3 olan \[ \begin{aligned} \tfrac{1}{3}x_1 + \tfrac{1}{3}x_2 + \tfrac{1}{3}x_3 &\le 1 \\ \tfrac{1}{3}x_1 + \tfrac{4}{3}x_2 + \tfrac{7}{3}x_3 &\le 3 \\ x_1, x_2, x_3 &\ge 0 \\ \max z &= 2x_1 + 3x_2 + x_3 \end{aligned} \] probleminde \(c_3\) hangi aralıkta değişirse optimumluk bozulmaz, yani optimal çözümdeki temel değişkenlerin değerleri değişmez?
Çözüm
Optimal tabloda temel dışı değişkenler \(x_3\), \(x_4\), \(x_5\)’tir; soru temel dışı \(x_3\)’ün \(c_3\) katsayısıyla ilgilidir. \(c_3\)’ü artık \(1\) olarak almayız, bir değişken olarak tabloya yazarız. Gövde değişmez; son satırda yalnız \(v_3\)’ün kriteri değişir:
| \(c_j\) | \(2\) | \(3\) | \(c_3\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) |
| \(x_1\) | \(2\) | \(1\) | \(1\) | \(0\) | \(-1\) | \(4\) | \(-1\) |
| \(x_2\) | \(3\) | \(2\) | \(0\) | \(1\) | \(2\) | \(-1\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = 8\) | \(0\) | \(0\) | \(4 - c_3\) | \(5\) | \(1\) |
Problem maksimum problemi olduğu için optimal tabloda bütün \(z_j - c_j \ge 0\) olmalıdır: \[ z_3 - c_3 = (2,\ 3)\begin{pmatrix} -1 \\ 2 \end{pmatrix} - c_3 = 4 - c_3 \ge 0 \ \Longrightarrow \ c_3 \le 4 . \] Diğer kriterler \(0\), \(0\), \(5\), \(1\)’dir ve \(c_3\)’e bağlı değildir. Demek ki \(c_3 \le 4\) olduğu sürece optimumluk bozulmaz: optimal çözüm \(x_1 = 1\), \(x_2 = 2\), \(x_3 = 0\) ve \(\max z = 8\) olarak kalır. \(c_3 = 4\) iken \(z_3 - c_3 = 0\) olur ve \(v_3\) baza alınarak aynı \(z = 8\) değerli alternatif bir optimal çözüm bulunur. \(c_3 > 4\) olursa \(z_3 - c_3 < 0\) olur, \(v_3\) baza girer ve simpleks yöntem bu tablodan devam ettirilerek yeni optimum bulunur. \(\blacksquare\)
Örnek 10.6 (Temel dışı bir değişkenin katsayısı ve amaç doğrusunun eğimi) \[ \begin{aligned} x_1 + x_2 &\le 4 \\ 2x_1 + x_2 &\le 6 \\ x_1, x_2 &\ge 0 \\ \max z &= 5x_1 + 2x_2 \end{aligned} \] probleminin optimal tablosunu \(B^{-1}\) ile yazınız ve \(c_2\)’nin optimumluğu bozmayan değişim aralığını bulup grafik üzerinde yorumlayınız.
Çözüm
Optimal tablo. Standart formda aylak değişkenler \(x_3\), \(x_4\)’tür (\(x_1 + x_2 + x_3 = 4\), \(2x_1 + x_2 + x_4 = 6\)). Köşelerdeki değerler \((0, 0)\): \(0\), \((3, 0)\): \(15\), \((2, 2)\): \(14\), \((0, 4)\): \(8\) olduğundan optimum \((3, 0)\)’dadır. Burada \(x_1 = 3\) ve birinci kısıtta \(4 - 3 = 1\) birim boşluk kalır: \(x_3 = 1\). Temel değişkenler \(x_3\) ve \(x_1\)’dir. Satırları bu sırayla yazarsak \[ B = \begin{bmatrix} v_3 & v_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 0 & 2 \end{bmatrix}, \qquad B^{-1} = \frac{1}{2}\begin{bmatrix} 2 & -1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & -\tfrac{1}{2} \\[1mm] 0 & \tfrac{1}{2} \end{bmatrix}. \] \(B^{-1}\vec{b} = (4 - 3,\ 3)^T = (1, 3)^T\), \(B^{-1}v_2 = \big(1 - \tfrac{1}{2},\ \tfrac{1}{2}\big)^T = \big(\tfrac{1}{2}, \tfrac{1}{2}\big)^T\) ve \(B^{-1}v_4 = B^{-1}e_2 = \big(-\tfrac{1}{2}, \tfrac{1}{2}\big)^T\) bulunur.
Sembolik tablo. \(c_2\)’yi sembol olarak yazalım; \(\vec{c}_B = (0, 5)^T\) ve \(x_2\) temel dışıdır: \[ \begin{aligned} z_2 - c_2 &= (0,\ 5)\begin{pmatrix} \tfrac{1}{2} \\[1mm] \tfrac{1}{2} \end{pmatrix} - c_2 = \tfrac{5}{2} - c_2, \\[1mm] z_4 - c_4 &= (0,\ 5)\begin{pmatrix} -\tfrac{1}{2} \\[1mm] \tfrac{1}{2} \end{pmatrix} - 0 = \tfrac{5}{2}. \end{aligned} \]
| \(c_j\) | \(5\) | \(c_2\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_3\) | \(0\) | \(1\) | \(0\) | \(\frac{1}{2}\) | \(1\) | \(-\frac{1}{2}\) |
| \(x_1\) | \(5\) | \(3\) | \(1\) | \(\frac{1}{2}\) | \(0\) | \(\frac{1}{2}\) |
| \(z_j - c_j\) | \(z_0 = 15\) | \(0\) | \(\frac{5}{2} - c_2\) | \(0\) | \(\frac{5}{2}\) |
\(c_2 = 2\) için \(z_2 - c_2 = \tfrac{1}{2} \ge 0\) ve tablo optimaldir. Maksimum problemi olduğundan koşul \[ \tfrac{5}{2} - c_2 \ge 0 \ \Longrightarrow \ c_2 \le \tfrac{5}{2} \] olur. \(c_2 \le \tfrac{5}{2}\) iken optimal çözüm \((3, 0)\) ve \(\max z = 15\) olarak kalır.
Geometrik yorum. \((3, 0)\) köşesinden geçen seviye doğrusu \(5x_1 + c_2x_2 = 15\)’tir. \(c_2\) büyüdükçe bu doğru \((3, 0)\) etrafında dönerek yatıklaşır. \(c_2 = \tfrac{5}{2}\) olunca doğru \(5x_1 + \tfrac{5}{2}x_2 = 15\), yani \(2x_1 + x_2 = 6\) olur ve bölgenin \((3, 0)\)–\((2, 2)\) kenarının üzerine oturur. Bu kenarın her noktası optimaldir. \(c_2 > \tfrac{5}{2}\) olunca \((2, 2)\) köşesinde \(z = 10 + 2c_2\) olur ve bu değer \(15\)’i aşar; optimum \((2, 2)\)’ye geçer (\(c_2 > 5\) olunca da \((0, 4)\)’e).
Böylece \(c_2 > 0\) için \(c_2\)’nin değişim aralığı, amaç doğrusunun eğiminin \(-5/c_2 \le -2\) kaldığı, yani doğrunun \(2x_1 + x_2 = 6\) kenarından daha dik olduğu aralıktır. \(\blacksquare\)
Temel Değişkenlerin Katsayılarındaki Değişim
Temelde olan bir değişkenin katsayısı \(c_B\) sütununda da görünür. \(z_j = \vec{c}_B^{\,T}\vec{y}_j\) her sütunda \(c_B\)’yi kullandığı için değişim bu kez bütün temel dışı sütunlara yayılır.
Önerme 10.3 (Temelde olan değişkenin katsayısı) Optimal tabloda \(x_r\) temelde olan bir değişken olsun, \(r\). satırda bulunsun ve katsayısı \(c_r\) yerine \(c_r + \Delta\) olsun. Bu durumda
- temel değişkenlerin kriterleri \(0\) kalır;
- temel dışı her \(v_j\) için yeni kriter \((z_j - c_j) + \Delta\, y_{rj}\) olur;
- amaç değeri \(z_0 + \Delta\, y_{r0}\) olur; burada \(y_{r0}\), \(x_r\)’nin değeridir.
Tablo maksimum probleminde temel dışı her \(j\) için \((z_j - c_j) + \Delta\, y_{rj} \ge 0\) iken, minimum probleminde temel dışı her \(j\) için \((z_j - c_j) + \Delta\, y_{rj} \le 0\) iken optimal kalır.
İspat
Yeni baz maliyet vektörü \(\vec{c}_B + \Delta\, e_r\)’dir; \(e_r\), \(r\). bileşeni \(1\) olan birim vektördür. Her \(j = 0, 1, \dots, n\) için \[ z_j' = (\vec{c}_B + \Delta e_r)^T \vec{y}_j = \vec{c}_B^{\,T}\vec{y}_j + \Delta\, e_r^T \vec{y}_j = z_j + \Delta\, y_{rj}. \] \(j = 0\) için bu 3. maddedir. \(j \ne r\) iken \(c_j\) değişmediğinden yeni kriter \((z_j - c_j) + \Delta\, y_{rj}\) olur; bu 2. maddedir. Başka bir temel değişkenin sütunu, \(r\). bileşeni \(0\) olan bir birim vektördür, dolayısıyla \(y_{rj} = 0\) ve kriteri \(0\) kalır. \(j = r\) için \(y_{rr} = 1\)’dir ve \(c_r\) de \(\Delta\) kadar artar: \((z_r + \Delta) - (c_r + \Delta) = 0\). Böylece 1. madde de gösterilmiş olur.
Tablonun gövdesi değişmediğinden (Sonuç 10.1) temel çözüm uygun kalır. Temel değişkenlerin kriterleri sıfırdır; optimallik koşulu (Teorem 4.3) yalnız temel dışı sütunlar için kontrol edilir ve ifadedeki eşitsizlikler elde edilir. \(\blacksquare\)
Yani temelde olan bir değişkenin katsayısı değişince her temel dışı kriter, o değişkenin satırındaki \(y_{rj}\) ile orantılı olarak kayar. Her temel dışı sütun \(\Delta\) için bir eşitsizlik verir; değişim aralığı bu eşitsizliklerin hepsini birden sağlayan, yani bu eşitsizliklerin ortak kısmı olan aralıktır. Maksimum probleminde \(y_{rj} > 0\) olan sütunlar \(\Delta\)’ya alt sınır, \(y_{rj} < 0\) olanlar üst sınır koyar; \(y_{rj} = 0\) olan sütun hiçbir sınır koymaz.
Pratikte \(\Delta\) yerine doğrudan \(c_r\) sembolüyle çalışmak daha kolaydır: \(c_B\) sütununa ve \(c_j\) satırına \(c_r\) yazılır, son satır \(c_r\) cinsinden hesaplanır. İki yazım aynı aralığı verir, çünkü \(c_r\) sembolü, eski değer artı \(\Delta\)’dır.
- Optimal tabloda \(c_r\)’yi hem \(c_j\) satırına hem \(x_r\) satırının \(c_B\) hücresine sembol olarak yaz.
- Temel dışı her \(v_j\) için \(z_j - c_j = \vec{c}_B^{\,T}\vec{y}_j - c_j\)’yi \(c_r\) cinsinden hesapla; temel sütunların kriteri \(0\)’dır.
- Maksimumda her birinin \(\ge 0\), minimumda \(\le 0\) olmasını iste ve her eşitsizliği \(c_r\) için çöz.
- Bulunan aralıkların kesişimini al. Amaç değeri \(z_0 = \vec{c}_B^{\,T} B^{-1}\vec{b}\) de \(c_r\)’ye bağlı olarak yazılır.
Örnek 10.7 (Temelde olan \(x_1\)’in katsayısının değişim aralığı) Optimal tablosu Tablo 10.3 olan problemde (\(\tfrac{1}{3}x_1 + \tfrac{1}{3}x_2 + \tfrac{1}{3}x_3 \le 1\), \(\tfrac{1}{3}x_1 + \tfrac{4}{3}x_2 + \tfrac{7}{3}x_3 \le 3\), \(x_j \ge 0\), \(\max z = 2x_1 + 3x_2 + x_3\)) temelde olan \(x_1\) değişkeninin katsayısı \(c_1\) hangi aralıkta değişirse optimumluk bozulmaz?
Çözüm
Optimal tabloda temel değişkenler \(x_1\) ve \(x_2\)’dir. \(x_1\) temelde olduğu için \(c_1\) hem \(c_j\) satırına hem \(c_B\) sütununa yazılır ve bütün temel dışı kriterleri etkiler; bu yüzden her bir \(z_j - c_j\) değerine bakmak gerekir. \(\vec{c}_B = (c_1, 3)^T\): \[ \begin{aligned} z_1 - c_1 &= (c_1,\ 3)\begin{pmatrix} 1 \\ 0 \end{pmatrix} - c_1 = c_1 - c_1 = 0, \\[1mm] z_2 - c_2 &= (c_1,\ 3)\begin{pmatrix} 0 \\ 1 \end{pmatrix} - 3 = 3 - 3 = 0, \\[1mm] z_3 - c_3 &= (c_1,\ 3)\begin{pmatrix} -1 \\ 2 \end{pmatrix} - 1 = -c_1 + 5 \ge 0 \ \Longrightarrow \ c_1 \le 5, \\[1mm] z_4 - c_4 &= (c_1,\ 3)\begin{pmatrix} 4 \\ -1 \end{pmatrix} - 0 = 4c_1 - 3 \ge 0 \ \Longrightarrow \ c_1 \ge \tfrac{3}{4}, \\[1mm] z_5 - c_5 &= (c_1,\ 3)\begin{pmatrix} -1 \\ 1 \end{pmatrix} - 0 = -c_1 + 3 \ge 0 \ \Longrightarrow \ c_1 \le 3 . \end{aligned} \] Amaç değeri \(z_0 = (c_1,\ 3)(1,\ 2)^T = c_1 + 6\)’dır.
| \(c_j\) | \(c_1\) | \(3\) | \(1\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) |
| \(x_1\) | \(c_1\) | \(1\) | \(1\) | \(0\) | \(-1\) | \(4\) | \(-1\) |
| \(x_2\) | \(3\) | \(2\) | \(0\) | \(1\) | \(2\) | \(-1\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = c_1 + 6\) | \(0\) | \(0\) | \(5 - c_1\) | \(4c_1 - 3\) | \(3 - c_1\) |
Üç koşulu birden sağlayan aralık \[ \tfrac{3}{4} \le c_1 \le 3 \] olarak bulunur. Yani \(c_1\), \(\tfrac{3}{4}\) ile \(3\) arasında değişirse optimumluk bozulmaz: temel değişkenler ve değerleri (\(x_1 = 1\), \(x_2 = 2\)) aynı kalır, optimal değer \(c_1 + 6\) olur. \(c_1 \le 5\) koşulu \(c_1 \le 3\)’ün içinde kaldığı için aralığa bir şey eklemez.
Aynı sonucu Önerme 10.3 ile de bulalım. \(c_1 = 2 + \Delta\) yazalım. \(x_1\) satırında temel dışı sütunların elemanları \(y_{13} = -1\), \(y_{14} = 4\), \(y_{15} = -1\), kriterleri \(3\), \(5\), \(1\)’dir. Koşullar \(3 - \Delta \ge 0\), \(5 + 4\Delta \ge 0\) ve \(1 - \Delta \ge 0\), yani \(-\tfrac{5}{4} \le \Delta \le 1\)’dir. \(c_1 = 2 + \Delta\) olduğundan yine \(\tfrac{3}{4} \le c_1 \le 3\) bulunur. \(\blacksquare\)
Örnek 10.8 (Temelde olan \(x_2\)’nin katsayısının değişim aralığı) Aynı problemde (\(\tfrac{1}{3}x_1 + \tfrac{1}{3}x_2 + \tfrac{1}{3}x_3 \le 1\), \(\tfrac{1}{3}x_1 + \tfrac{4}{3}x_2 + \tfrac{7}{3}x_3 \le 3\), \(x_j \ge 0\), \(\max z = 2x_1 + 3x_2 + x_3\); optimal tablo Tablo 10.3) temelde olan \(x_2\) değişkeninin katsayısı \(c_2\) hangi aralıkta değişirse optimumluk bozulmaz?
Çözüm
Bu kez \(c_2\) sembolü \(c_j\) satırına ve \(x_2\) satırının \(c_B\) hücresine yazılır; \(\vec{c}_B = (2, c_2)^T\): \[ \begin{aligned} z_1 - c_1 &= (2,\ c_2)\begin{pmatrix} 1 \\ 0 \end{pmatrix} - 2 = 2 - 2 = 0, \\[1mm] z_2 - c_2 &= (2,\ c_2)\begin{pmatrix} 0 \\ 1 \end{pmatrix} - c_2 = c_2 - c_2 = 0, \\[1mm] z_3 - c_3 &= (2,\ c_2)\begin{pmatrix} -1 \\ 2 \end{pmatrix} - 1 = -2 + 2c_2 - 1 \ge 0 \ \Longrightarrow \ c_2 \ge \tfrac{3}{2}, \\[1mm] z_4 - c_4 &= (2,\ c_2)\begin{pmatrix} 4 \\ -1 \end{pmatrix} - 0 = 8 - c_2 \ge 0 \ \Longrightarrow \ c_2 \le 8, \\[1mm] z_5 - c_5 &= (2,\ c_2)\begin{pmatrix} -1 \\ 1 \end{pmatrix} - 0 = -2 + c_2 \ge 0 \ \Longrightarrow \ c_2 \ge 2 . \end{aligned} \] Amaç değeri \(z_0 = (2,\ c_2)(1,\ 2)^T = 2 + 2c_2\)’dir.
| \(c_j\) | \(2\) | \(c_2\) | \(1\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) |
| \(x_1\) | \(2\) | \(1\) | \(1\) | \(0\) | \(-1\) | \(4\) | \(-1\) |
| \(x_2\) | \(c_2\) | \(2\) | \(0\) | \(1\) | \(2\) | \(-1\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = 2 + 2c_2\) | \(0\) | \(0\) | \(2c_2 - 3\) | \(8 - c_2\) | \(c_2 - 2\) |
Üç koşulu birden sağlayan aralık \[ 2 \le c_2 \le 8 \] olarak bulunur. Yani \(c_2\), \(2\) ile \(8\) arasında değişirse optimumluk bozulmaz; optimal çözüm \(x_1 = 1\), \(x_2 = 2\) kalır ve optimal değer \(2 + 2c_2\) olur. \(c_2 \ge \tfrac{3}{2}\) koşulu \(c_2 \ge 2\)’nin içinde kalır. \(\blacksquare\)
İki değişkenli bir problemde bu aralığın geometrik anlamı açıktır: optimal köşe, amaç doğrusunun eğimi o köşede birleşen iki kenarın eğimleri arasında kaldıkça optimal kalır.
Örnek 10.9 (Temelde olan bir değişkenin katsayısı ve köşedeki yelpaze) \(x_1 + x_2 \le 4\), \(2x_1 + x_2 \le 6\), \(x_1, x_2 \ge 0\), \(\max z = 3x_1 + 2x_2\) probleminin optimal tablosu Tablo 10.4’tır. Temelde olan \(x_1\)’in katsayısı \(c_1\) hangi aralıkta değişirse optimumluk bozulmaz? Sonucu grafik üzerinde yorumlayınız.
Çözüm
\(\vec{c}_B = (c_1, 2)^T\) alıp temel dışı \(v_3\) ve \(v_4\) sütunlarının kriterlerini hesaplarız: \[ \begin{aligned} z_3 - c_3 &= (c_1,\ 2)\begin{pmatrix} -1 \\ 2 \end{pmatrix} - 0 = 4 - c_1 \ge 0 \ \Longrightarrow \ c_1 \le 4, \\[1mm] z_4 - c_4 &= (c_1,\ 2)\begin{pmatrix} 1 \\ -1 \end{pmatrix} - 0 = c_1 - 2 \ge 0 \ \Longrightarrow \ c_1 \ge 2 . \end{aligned} \] Amaç değeri \(z_0 = 2c_1 + 2 \cdot 2 = 2c_1 + 4\)’tür.
| \(c_j\) | \(c_1\) | \(2\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_1\) | \(c_1\) | \(2\) | \(1\) | \(0\) | \(-1\) | \(1\) |
| \(x_2\) | \(2\) | \(2\) | \(0\) | \(1\) | \(2\) | \(-1\) |
| \(z_j - c_j\) | \(z_0 = 2c_1 + 4\) | \(0\) | \(0\) | \(4 - c_1\) | \(c_1 - 2\) |
İki koşulu birden sağlayan aralık \(2 \le c_1 \le 4\)’tür. Bu aralıkta optimal çözüm \((2, 2)\) kalır ve optimal değer \(2c_1 + 4\) olur.
Geometrik yorum. \((2, 2)\) köşesinde \(x_1 + x_2 = 4\) ve \(2x_1 + x_2 = 6\) kenarları birleşir; eğimleri \(-1\) ve \(-2\)’dir. \(c_1x_1 + 2x_2 = k\) seviye doğrusunun eğimi \(-c_1/2\)’dir. \(c_1 = 2\) iken eğim \(-1\) olur ve seviye doğrusu birinci kenara, \(c_1 = 4\) iken eğim \(-2\) olur ve ikinci kenara oturur. Aradaki her \(c_1\) için seviye doğrusu bölgeye yalnız \((2, 2)\)’de değer. Aynı şeyi gradyanla da söyleyebiliriz: gradyan \(\vec{c} = (c_1, 2)\), iki kenarın dik vektörleri \((1, 1)\) ve \((2, 1)\) arasında kaldıkça \((2, 2)\) optimaldir.
Uç değerlerde alternatif optimal çözüm ortaya çıkar: \(c_1 = 2\) iken \((0, 4)\)–\((2, 2)\) kenarının, \(c_1 = 4\) iken \((2, 2)\)–\((3, 0)\) kenarının her noktası optimaldir. \(\blacksquare\)
Temelde olan değişken bir aylak ya da artık değişken de olabilir. Bu değişkenlerin amaç katsayısı \(0\)’dır, ama aynı soru onlar için de sorulabilir: Kullanılmayan kaynağın birimine bir değer (ya da maliyet) biçilirse çözüm değişir mi?
Örnek 10.10 (Temelde olan bir aylak değişkenin katsayısı) \(x_1 + x_2 \le 4\), \(2x_1 + x_2 \le 6\), \(x_1, x_2 \ge 0\), \(\max z = 5x_1 + 2x_2\) probleminin optimal tablosu Tablo 10.7’dir (\(c_2 = 2\) için); temelde \(x_3 = 1\) ve \(x_1 = 3\) vardır. Temelde olan \(x_3\) aylak değişkeninin katsayısı \(c_3\) hangi aralıkta değişirse optimumluk bozulmaz?
Çözüm
\(x_3\) birinci satırdadır; \(\vec{c}_B = (c_3, 5)^T\). Temel dışı sütunlar \(v_2\) ve \(v_4\)’tür: \[ \begin{aligned} z_2 - c_2 &= (c_3,\ 5)\begin{pmatrix} \tfrac{1}{2} \\[1mm] \tfrac{1}{2} \end{pmatrix} - 2 = \frac{c_3 + 5}{2} - 2 = \frac{c_3 + 1}{2} \ge 0 \ \Longrightarrow \ c_3 \ge -1, \\[1mm] z_4 - c_4 &= (c_3,\ 5)\begin{pmatrix} -\tfrac{1}{2} \\[1mm] \tfrac{1}{2} \end{pmatrix} - 0 = \frac{5 - c_3}{2} \ge 0 \ \Longrightarrow \ c_3 \le 5 . \end{aligned} \] Amaç değeri \(z_0 = c_3 \cdot 1 + 5 \cdot 3 = c_3 + 15\)’tir.
| \(c_j\) | \(5\) | \(2\) | \(c_3\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_3\) | \(c_3\) | \(1\) | \(0\) | \(\frac{1}{2}\) | \(1\) | \(-\frac{1}{2}\) |
| \(x_1\) | \(5\) | \(3\) | \(1\) | \(\frac{1}{2}\) | \(0\) | \(\frac{1}{2}\) |
| \(z_j - c_j\) | \(z_0 = c_3 + 15\) | \(0\) | \(\frac{c_3 + 1}{2}\) | \(0\) | \(\frac{5 - c_3}{2}\) |
Değişim aralığı \(-1 \le c_3 \le 5\)’tir. Yorumu şöyledir: birinci kaynağın kullanılmayan her birimi için en fazla \(1\) birim ceza ödenirse (\(c_3 \ge -1\)) ya da en fazla \(5\) birim kazanılırsa (\(c_3 \le 5\)) üretim planı \(x_1 = 3\), \(x_2 = 0\) olarak kalır. Ceza \(1\)’i aşarsa kaynağın boşta kalan kısmını da kullanmak, yani \(v_2\)’yi baza almak kârlı olur. \(\blacksquare\)
Minimum probleminde eşitsizliklerin yönü ters döner; gerisi aynıdır.
Örnek 10.11 (Minimum probleminde temelde olan bir değişkenin katsayısı) \(x_1 + x_2 \ge 4\), \(x_1 + 3x_2 \ge 6\), \(x_1, x_2 \ge 0\), \(\min z = 2x_1 + 3x_2\) probleminin optimal tablosu Tablo 10.5’dir. Temelde olan \(x_1\)’in katsayısı \(c_1\) hangi aralıkta değişirse optimumluk bozulmaz?
Çözüm
Minimum probleminde optimal tabloda bütün \(z_j - c_j \le 0\) olmalıdır. \(\vec{c}_B = (c_1, 3)^T\) ile temel dışı \(v_3\) ve \(v_4\) sütunları: \[ \begin{aligned} z_3 - c_3 &= (c_1,\ 3)\begin{pmatrix} -\tfrac{3}{2} \\[1mm] \tfrac{1}{2} \end{pmatrix} - 0 = \frac{3 - 3c_1}{2} \le 0 \ \Longrightarrow \ c_1 \ge 1, \\[1mm] z_4 - c_4 &= (c_1,\ 3)\begin{pmatrix} \tfrac{1}{2} \\[1mm] -\tfrac{1}{2} \end{pmatrix} - 0 = \frac{c_1 - 3}{2} \le 0 \ \Longrightarrow \ c_1 \le 3 . \end{aligned} \] Amaç değeri \(z_0 = 3c_1 + 3 \cdot 1 = 3c_1 + 3\)’tür.
| \(c_j\) | \(c_1\) | \(3\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_1\) | \(c_1\) | \(3\) | \(1\) | \(0\) | \(-\frac{3}{2}\) | \(\frac{1}{2}\) |
| \(x_2\) | \(3\) | \(1\) | \(0\) | \(1\) | \(\frac{1}{2}\) | \(-\frac{1}{2}\) |
| \(z_j - c_j\) | \(z_0 = 3c_1 + 3\) | \(0\) | \(0\) | \(\frac{3 - 3c_1}{2}\) | \(\frac{c_1 - 3}{2}\) |
Değişim aralığı \(1 \le c_1 \le 3\)’tür; bu aralıkta optimal çözüm \((3, 1)\) ve \(\min z = 3c_1 + 3\) olur. Geometrik olarak \(c_1x_1 + 3x_2 = k\) seviye doğrusunun eğimi \(-c_1/3\)’tür ve \((3, 1)\)’de birleşen \(x_1 + 3x_2 = 6\) ile \(x_1 + x_2 = 4\) kenarlarının eğimleri olan \(-\tfrac{1}{3}\) ile \(-1\) arasında kalmalıdır.
\(0 \le c_1 < 1\) olursa \(x_1\) o kadar ucuzlar ki çözüm \(x_1\) ekseni üzerindeki \((6, 0)\) köşesine kayar; \(c_1 > 3\) olursa \((0, 4)\) köşesine kayar. \(\blacksquare\)
10.4 Sağ Taraf Sabitlerindeki Değişim
Şimdi soruyu sağ taraf sabitleri için soralım: Kısıtların sağ taraf değerleri hangi aralıkta değişirse mevcut temel değişkenler temel değişken olarak kalır? Burada “optimumluğun bozulmaması” farklı bir anlam taşır. Sağ taraf değişince çözümün değerleri de amaç fonksiyonunun değeri de değişir; aynı kalması istenen, temeldeki değişkenlerin kendisidir.
Önerme 10.4 (Sağ taraf sabitlerinin değişimi) \(B\), optimal tablonun baz matrisi olsun ve \(\vec{b}\) yerine \(\vec{b}\,'\) gelsin. Bu durumda
- \(B^{-1}\vec{b}\,' \ge \vec{0}\) ise aynı baz optimal kalır; yeni optimal çözümde temel değişkenlerin değerleri \(B^{-1}\vec{b}\,'\), temel dışı değişkenler \(0\) ve optimal değer \(z_0 = \vec{c}_B^{\,T} B^{-1}\vec{b}\,'\) olur;
- \(B^{-1}\vec{b}\,'\)’nün bir bileşeni negatifse bu bazın temel çözümü uygun değildir, yani optimal tablo bozulur.
İspat
Sonuç 10.1 gereği \(\vec{b}\) değişince bütün \(y_{ij}\)’ler ve \(j \ge 1\) için bütün \(z_j - c_j\) değerleri aynı kalır; yalnız \(v_0\) sütunu \(B^{-1}\vec{b}\,'\) ve \(z_0\) değeri \(\vec{c}_B^{\,T} B^{-1}\vec{b}\,'\) olur (Teorem 10.1).
1. \(B^{-1}\vec{b}\,' \ge \vec{0}\) ise tablonun temel çözümü uygun bir temel çözümdür. Son satır değişmediği için optimallik koşulu hâlâ sağlanır; Teorem 4.3 gereği bu çözüm yeni problemin optimal çözümüdür.
2. Bu bazın temel çözümünde temel değişkenlerin değerleri tek türlü \(B^{-1}\vec{b}\,'\)’dür; bir bileşeni negatifse çözüm \(\vec{x} \ge 0\) koşulunu sağlamaz. \(\blacksquare\)
Yani sağ taraf değişiminde önemli olan tek koşul \[ B^{-1}\vec{b} \ge \vec{0} \] eşitsizliğinin gerçekleşmesidir; burada \(B^{-1}\), temel değişkenlerin ilk baştaki katsayılar matrisinin tersidir. Tek bir \(b_i\) değişiyorsa, diğer sağ taraflar sabit tutularak \(B^{-1}\vec{b} \ge \vec{0}\) sisteminin her satırı \(b_i\) için bir eşitsizlik verir; değişim aralığı bunların kesişimidir.
- Optimal tablodaki temel değişkenlerin standart formdaki sütunlarından \(B\)’yi kur ve \(B^{-1}\)’i bul (ya da aylak sütunlarından oku).
- \(\vec{b}\)’de incelenen \(b_i\)’yi sembol olarak bırak, diğerlerini yerine koy.
- \(B^{-1}\vec{b} \ge \vec{0}\) eşitsizliğinin her satırını \(b_i\) için çöz.
- Bulunan aralıkların ortak kısmını, yani hepsini birden sağlayan aralığı al. Bu aralıkta yeni çözüm \(B^{-1}\vec{b}\), optimal değer \(\vec{c}_B^{\,T} B^{-1}\vec{b}\)’dir.
Örnek 10.12 (Birinci kısıtın sağ tarafının değişim aralığı) Optimal tablosu Tablo 10.3 olan problemde (\(\tfrac{1}{3}x_1 + \tfrac{1}{3}x_2 + \tfrac{1}{3}x_3 \le b_1\), \(\tfrac{1}{3}x_1 + \tfrac{4}{3}x_2 + \tfrac{7}{3}x_3 \le 3\), \(x_j \ge 0\), \(\max z = 2x_1 + 3x_2 + x_3\); başta \(b_1 = 1\)) \(b_1\) hangi aralıkta değişirse mevcut temel değişkenler \(x_1\) ve \(x_2\) temel değişken olarak kalır?
Çözüm
Temel değişkenler \(x_1\) ve \(x_2\)’dir. Tablonun satır sırasıyla \[ B = \begin{bmatrix} \tfrac{1}{3} & \tfrac{1}{3} \\[1mm] \tfrac{1}{3} & \tfrac{4}{3} \end{bmatrix} \ \Longrightarrow \ B^{-1} = \begin{bmatrix} 4 & -1 \\ -1 & 1 \end{bmatrix}, \qquad \vec{b} = \begin{bmatrix} 1 \\ 3 \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \end{bmatrix} \] şeklindedir (Örnek 10.2). \(B^{-1}\), optimal tablonun \(v_4\) ve \(v_5\) sütunlarında da okunur. \(b_2 = 3\) sabit tutulur: \[ B^{-1}\vec{b} = \begin{bmatrix} 4 & -1 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} b_1 \\ 3 \end{bmatrix} = \begin{bmatrix} 4b_1 - 3 \\ -b_1 + 3 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}. \] Birinci satırdan \(4b_1 - 3 \ge 0\), yani \(b_1 \ge \tfrac{3}{4}\); ikinci satırdan \(-b_1 + 3 \ge 0\), yani \(b_1 \le 3\) bulunur. İki aralığın ortak kısmı alınırsa \[ \tfrac{3}{4} \le b_1 \le 3 \] elde edilir. Yani \(b_1\), \(\tfrac{3}{4}\) ile \(3\) arasında değişirse mevcut temel değişkenler \(x_1\) ve \(x_2\) temel değişken olarak kalır. Bu aralıkta optimal çözüm \(x_1 = 4b_1 - 3\), \(x_2 = 3 - b_1\) ve optimal değer \[ z_0 = 2(4b_1 - 3) + 3(3 - b_1) = 5b_1 + 3 \] olur; \(b_1 = 1\) için \(x_1 = 1\), \(x_2 = 2\), \(z_0 = 8\) bulunur. Aralığın uçlarında temel değişkenlerden biri sıfır olur (\(b_1 = \tfrac{3}{4}\) iken \(x_1 = 0\), \(b_1 = 3\) iken \(x_2 = 0\)); çözüm dejenere olur ama baz hâlâ optimaldir. \(\blacksquare\)
Örnek 10.13 (İkinci kısıtın sağ tarafının değişim aralığı) Aynı problemde (\(\tfrac{1}{3}x_1 + \tfrac{1}{3}x_2 + \tfrac{1}{3}x_3 \le 1\), \(\tfrac{1}{3}x_1 + \tfrac{4}{3}x_2 + \tfrac{7}{3}x_3 \le b_2\), \(x_j \ge 0\), \(\max z = 2x_1 + 3x_2 + x_3\); başta \(b_2 = 3\)) \(b_2\) hangi aralıkta değişirse optimumluğun bozulmadığı, yani \(x_1\) ve \(x_2\)’nin temel değişken olarak kaldığı durumu inceleyiniz.
Çözüm
\(B^{-1}\) aynıdır (Örnek 10.12); bu kez \(b_1 = 1\) sabit tutulur: \[ B^{-1}\vec{b} = \begin{bmatrix} 4 & -1 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ b_2 \end{bmatrix} = \begin{bmatrix} 4 - b_2 \\ -1 + b_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}. \] Birinci satırdan \(4 - b_2 \ge 0\), yani \(b_2 \le 4\); ikinci satırdan \(-1 + b_2 \ge 0\), yani \(b_2 \ge 1\) bulunur. İki aralığın ortak kısmı alınırsa \[ 1 \le b_2 \le 4 \] elde edilir. Yani \(b_2\), \(1\) ile \(4\) arasında değişirse mevcut temel değişkenler \(x_1\) ve \(x_2\) temel değişken olarak kalır. Bu aralıkta optimal çözüm \(x_1 = 4 - b_2\), \(x_2 = b_2 - 1\) ve optimal değer \[ z_0 = 2(4 - b_2) + 3(b_2 - 1) = b_2 + 5 \] olur. \(\blacksquare\)
İki değişkenli bir problemde sağ tarafın değişmesi, kısıt doğrusunun kendine paralel olarak kayması demektir. Optimal köşe de onunla birlikte yer değiştirir.
Örnek 10.14 (Sağ taraf değişince optimal köşenin kayması) \(x_1 + x_2 \le b_1\), \(2x_1 + x_2 \le 6\), \(x_1, x_2 \ge 0\), \(\max z = 3x_1 + 2x_2\) problemi \(b_1 = 4\) için çözülmüş, optimal tablosu Tablo 10.4 bulunmuştur. \(b_1\) hangi aralıkta değişirse temel değişkenler \(x_1\), \(x_2\) olarak kalır? Optimal çözümü ve optimal değeri \(b_1\) cinsinden yazıp grafik üzerinde yorumlayınız.
Çözüm
Örnek 10.3’ta \(B^{-1} = \begin{bmatrix} -1 & 1 \\ 2 & -1 \end{bmatrix}\) bulunmuştu; tablonun \(v_3\), \(v_4\) sütunlarında da görünür. \(b_2 = 6\) sabit tutulur: \[ B^{-1}\vec{b} = \begin{bmatrix} -1 & 1 \\ 2 & -1 \end{bmatrix} \begin{bmatrix} b_1 \\ 6 \end{bmatrix} = \begin{bmatrix} 6 - b_1 \\ 2b_1 - 6 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}. \] Birinci satır \(b_1 \le 6\), ikinci satır \(b_1 \ge 3\) verir; değişim aralığı \(3 \le b_1 \le 6\)’dır. Bu aralıkta \[ x_1 = 6 - b_1, \quad x_2 = 2b_1 - 6, \quad z_0 = 3(6 - b_1) + 2(2b_1 - 6) = b_1 + 6 . \] Örneğin \(b_1 = 5\) için \((1, 4)\) ve \(z_0 = 11\) bulunur. Kontrol: \(1 + 4 = 5\), \(2 + 4 = 6\) ve \(3 + 8 = 11\).
Geometrik yorum. \(b_1\) değişince \(x_1 + x_2 = b_1\) doğrusu kendine paralel kayar; \(2x_1 + x_2 = 6\) doğrusu yerinde kalır. Optimal köşe iki doğrunun kesişimi olan \((6 - b_1,\ 2b_1 - 6)\) noktasıdır ve \(2x_1 + x_2 = 6\) doğrusu üzerinde yürür. \(b_1 = 3\) iken köşe \((3, 0)\)’a, \(b_1 = 6\) iken \((0, 6)\)’ya ulaşır. \(b_1 < 3\) olursa kesişim noktasında \(x_2 < 0\), \(b_1 > 6\) olursa \(x_1 < 0\) olur; kesişim uygun bölgenin dışına düşer ve optimum başka bir bazda bulunur.
Aralığın içinde amaç değeri \(b_1\)’in her birim artışında \(1\) artar. \(\blacksquare\)
Örnek 10.15 (İkinci kısıtın sağ tarafı) \(x_1 + x_2 \le 4\), \(2x_1 + x_2 \le b_2\), \(x_1, x_2 \ge 0\), \(\max z = 3x_1 + 2x_2\) problemi \(b_2 = 6\) için çözülmüş, optimal tablosu Tablo 10.4 bulunmuştur. \(b_2\) hangi aralıkta değişirse temel değişkenler \(x_1\), \(x_2\) olarak kalır?
Çözüm
\(B^{-1} = \begin{bmatrix} -1 & 1 \\ 2 & -1 \end{bmatrix}\) ve \(b_1 = 4\) sabit tutulur: \[ B^{-1}\vec{b} = \begin{bmatrix} -1 & 1 \\ 2 & -1 \end{bmatrix} \begin{bmatrix} 4 \\ b_2 \end{bmatrix} = \begin{bmatrix} b_2 - 4 \\ 8 - b_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}. \] Birinci satır \(b_2 \ge 4\), ikinci satır \(b_2 \le 8\) verir; değişim aralığı \(4 \le b_2 \le 8\)’dir. Bu aralıkta \(x_1 = b_2 - 4\), \(x_2 = 8 - b_2\) ve \(z_0 = 3(b_2 - 4) + 2(8 - b_2)\), yani \(z_0 = b_2 + 4\) olur. Geometrik olarak \(2x_1 + x_2 = b_2\) doğrusu kayar ve optimal köşe \(x_1 + x_2 = 4\) doğrusu üzerinde \(b_2 = 4\) iken \((0, 4)\)’ten \(b_2 = 8\) iken \((4, 0)\)’a kadar yürür. \(\blacksquare\)
Örneklerde optimal değerin sağ tarafa doğrusal olarak bağlı olduğunu gördük: Örnek 10.12’de \(z_0 = 5b_1 + 3\), Örnek 10.13’de \(z_0 = b_2 + 5\). Bu katsayıların, optimal tablonun aylak sütunlarındaki \(z_4 - c_4 = 5\) ve \(z_5 - c_5 = 1\) kriterleriyle aynı olması tesadüf değildir; bu sayıların anlamını Dualite bölümünde göreceğiz.
Aralığın dışına çıkıldığında tablo optimal olmaktan çıkar ama bütünüyle işe yaramaz hâle gelmez. Amaç katsayısı aralığın dışına çıkarsa tablo uygun kalır, yalnız bir ya da birkaç kriter yanlış işaretli olur; simpleks yöntem bu tablodan devam ettirilir. Sağ taraf aralığın dışına çıkarsa kriterler doğru işaretli kalır ama \(v_0\) sütununda negatif bir değer belirir; bu durumu Dual simpleks algoritması çözer.
10.5 Özet
Bu bölümün hesaplarını tek tabloda toplayalım.
| Değişen veri | Tabloda değişen | Optimumluğun korunma koşulu |
|---|---|---|
| Temel dışı \(x_k\)’nın \(c_k\)’sı | Yalnız \(z_k - c_k\) | max: \(c_k \le z_k\); min: \(c_k \ge z_k\) |
| Temelde olan \(x_r\)’nin \(c_r\)’si | Temel dışı bütün \(z_j - c_j\) ve \(z_0\) | Temel dışı her \(j\) için max: \(z_j - c_j \ge 0\); min: \(z_j - c_j \le 0\) |
| Sağ taraf \(b_i\) | \(v_0\) sütunu ve \(z_0\) | \(B^{-1}\vec{b} \ge \vec{0}\) |
Bölümün örneğinde (Örnek 10.1) bulunan aralıklar da şöyledir:
| Değişen | Değişim aralığı | Aralıkta optimal değer |
|---|---|---|
| \(c_1\) (temelde) | \(\tfrac{3}{4} \le c_1 \le 3\) | \(c_1 + 6\) |
| \(c_2\) (temelde) | \(2 \le c_2 \le 8\) | \(2 + 2c_2\) |
| \(c_3\) (temel dışı) | \(c_3 \le 4\) | \(8\) |
| \(b_1\) | \(\tfrac{3}{4} \le b_1 \le 3\) | \(5b_1 + 3\) |
| \(b_2\) | \(1 \le b_2 \le 4\) | \(b_2 + 5\) |
Duyarlılık analizi, optimal tablonun yalnız bir çözüm değil, problemin verileri hakkında bir bilgi kaynağı olduğunu gösterdi. Aynı tablonun içinde saklı olan bir başka problem daha vardır: her lineer programlama probleminin bir eşi, bir dual problemi bulunur ve optimal tablo onun da çözümünü taşır. Bir sonraki bölüm Dualite bu problemi inceliyor.