5 Büyük M Yöntemi
Simpleks yöntem bölümünde yalnız bütün kısıtları \(\le\) olan ve sağ tarafları negatif olmayan problemleri çözdük. Böyle bir problemin standart formunda aylak değişkenlerin sütunları kendiliğinden bir birim matris oluşturur; başlangıç bazı ve başlangıç tablosu (Bölüm 4.3) hiç hesap yapmadan yazılır. Kısıtlarda \(\ge\) ya da \(=\) bulununca bu kolaylık kaybolur. Artık değişkenin sütununda \(-1\) vardır, eşitlik kısıtına ise hiç yeni değişken eklenmez. Standart form birim matris içermediği için problem henüz simpleks yöntem ile çözülebilir halde değildir.
Bu durumda birim sütunu eksik olan denklemlere yapay değişkenler ekleyip başlangıç bazını kendimiz kurarız. Kurulan baz orijinal problemin bir çözümünü vermez, bu yüzden yapay değişkenlerden sonunda kurtulmamız gerekir. Bunun iki yolu vardır: Büyük M yöntemi ve İki faz yöntemi. Bu bölümde birincisini göreceğiz. Büyük M yöntemi simpleks yöntemin bir türüdür: tablolar, oran testi ve dönüşüm kuralı aynen kalır, yalnız amaç fonksiyonuna yapay değişkenler için çok büyük bir ceza eklenir.
5.1 Yapay Değişkenler ve M Problemi
Önce yapay değişkenlerin problemi nasıl değiştirdiğine bakalım.
Yapay değişkeni Lineer programlama problemi bölümünde tanımlamıştık (Tanım 1.10): birim sütunu olmayan bir denkleme, yalnız o denklemde katsayısı \(1\) ile görünecek biçimde eklenen negatif olmayan değişkendir ve \(x_{u_1}, x_{u_2}, \dots\) ile gösterilir. Yapay değişkenin problemin kendisinde bir anlamı yoktur. Aylak değişken kullanılmayan kaynağı, artık değişken aşılan gereksinimi ölçer; yapay değişken ise yalnız bir başlangıç çözümü kurabilmek için eklenen yardımcı bir değişkendir. Yapay değişkenleri eklenmiş probleme bir ad verelim.
Tanım 5.1 (M problemi) Standart formdaki
\[ \begin{aligned} A\vec{x} &= \vec{b} \\ \vec{x} &\ge 0 \\ \min z &= \vec{c}^{\,T}\vec{x} \end{aligned} \]
problemine orijinal problem diyelim. Birim sütunu olmayan denklemlere \(x_{u_1}, \dots, x_{u_p}\) yapay değişkenleri eklensin ve \(R\), sütunları bu değişkenlerin \(v_{u_1}, \dots, v_{u_p}\) sütunları olan \(m \times p\) matris olsun. \(M\) çok büyük bir pozitif sayı olmak üzere
\[ \begin{aligned} A\vec{x} + R\,\vec{x}_u &= \vec{b} \\ \vec{x} \ge 0, \quad \vec{x}_u &\ge 0 \\ \min z &= \vec{c}^{\,T}\vec{x} + M(x_{u_1} + \dots + x_{u_p}) \end{aligned} \]
problemine orijinal problemin M problemi denir; burada \(\vec{x}_u = (x_{u_1}, \dots, x_{u_p})\)’dir. Orijinal problem maksimum problemiyse M probleminin amacı \(\max z = \vec{c}^{\,T}\vec{x} - M(x_{u_1} + \dots + x_{u_p})\) olur.
Yani M problemi, orijinal problemin simpleks yöntem ile çözülebilir hale (Tanım 1.9) getirilmiş biçimidir: kısıtlarına yapay değişkenler, amacına da onların cezası eklenmiştir. Aylak ve artık değişkenler zaten \(\vec{x}\)’in içindedir, çünkü orijinal problem standart formdadır. \(R\)’nin her sütunu, eklendiği denklemde \(1\), diğer denklemlerde \(0\) taşır.
İki problem arasındaki bağ, yapay değişkenlerin sıfır olduğu çözümlerden geçer.
Önerme 5.1 (Orijinal problem ile M probleminin uygun çözümleri) Bir \(\vec{x}\) vektörü için şu iki ifade denktir:
- \(\vec{x}\) orijinal problemin uygun çözümüdür;
- yapay değişkenlerin hepsi sıfır alınarak elde edilen \((\vec{x}, \vec{0})\), M probleminin uygun çözümüdür.
Bu durumda M probleminin \((\vec{x}, \vec{0})\) noktasındaki amaç değeri, orijinal problemin \(\vec{x}\) noktasındaki değeri olan \(\vec{c}^{\,T}\vec{x}\)’e eşittir.
İspat
\(\vec{x}_u = \vec{0}\) iken \(R\,\vec{x}_u = \vec{0}\) olduğundan M probleminin kısıtları \(A\vec{x} = \vec{b}\)’ye, işaret koşulları da \(\vec{x} \ge 0\)’a iner. Bunlar tam olarak orijinal problemin kısıtlarıdır; dolayısıyla 1 ile 2 denktir. Amaçtaki ceza terimi \(\pm M(x_{u_1} + \dots + x_{u_p})\) sıfır olduğundan amaç değeri \(\vec{c}^{\,T}\vec{x}\)’tir.
\(\blacksquare\)
Yani orijinal problemin çözümleri, M probleminin yapay değişkenleri sıfır olan çözümleridir. Başlangıç tablosunun çözümü genellikle bunlardan biri değildir: orada yapay değişkenler eklendikleri denklemlerin sağ taraflarını üstlenir ve sağ taraf sıfır olmadıkça pozitiftir. Simpleks yöntemden istediğimiz, yapay değişkenleri sıfıra indirip orijinal problemin bir çözümüne ulaşması ve oradan optimuma devam etmesidir.
Amaçtaki ceza tam olarak bunu sağlar. Minimum probleminde her birim yapay değişken maliyete \(M\) ekler. \(M\) çok büyük olduğundan yapay değişkenlerin toplamını azaltmak, \(\vec{c}^{\,T}\vec{x}\) üzerindeki her kazançtan daha değerlidir. Maksimum probleminde \(-M\) katsayısı aynı işi kârdan düşerek yapar. Böylece simpleks yöntem kendi seçim kuralını izlerken önce yapay değişkenleri bazdan çıkarmaya yönelir.
\(M\) için belirli bir sayı seçmeyiz. Seçilen sayı yeterince büyük değilse ceza, amaçtaki gerçek katsayılar karşısında etkisiz kalabilir. Bu yüzden \(M\) tabloda bir sembol olarak taşınır ve “karşılaştırıldığı her sayıdan büyük” diye yorumlanır. Bunun hesapta ne anlama geldiğini şimdi görelim.
5.2 \(M\)’li Simpleks Kriterleri
M problemi çözülürken tabloya \(M\) yalnız amaç katsayılarından girer.
Tablonun gövdesi, yani \(v_0\) sütunu ve bütün \(y_{ij}\) değerleri, yalnız kısıtlara ve baza bağlıdır; amaç katsayılarını hiç kullanmaz. Dolayısıyla gövdede \(M\) bulunmaz. \(M\) yalnız en üstteki \(c_j\) satırında ve \(c_B\) sütununda görünür. \(z_j = \vec{c}_B^{\,T} v_j\) çarpımında bazdaki her yapay değişken \(\pm M\) katsayısını taşıdığı için her simpleks kriteri ve amaç değeri
\[z_j - c_j = a_jM + b_j, \qquad z_0 = sM + q\]
biçimindedir; \(a_j\), \(b_j\), \(s\), \(q\) sıradan sayılardır. Minimum probleminde \(s\), bazdaki yapay değişkenlerin değerlerinin toplamıdır; maksimum probleminde bu toplamın \(-1\) katıdır. Bir tablodan ötekine geçerken hangi kriterin daha büyük olduğuna karar vermemiz gerekir; bunun kuralı şudur.
Önerme 5.2 (M’li sayıların karşılaştırılması) \(a\), \(b\), \(a'\), \(b'\) gerçel sayılar olsun. \(M > M_0\) olan her \(M\) için
\[aM + b > a'M + b'\]
eşitsizliğini sağlayan bir \(M_0\) sayısının var olması için gerek ve yeter koşul, ya \(a > a'\) ya da \(a = a'\) ve \(b > b'\) olmasıdır. Özel olarak \(a' = b' = 0\) alınırsa: \(aM + b\) sayısının yeterince büyük her \(M\) için pozitif olması için gerek ve yeter koşul, \(a > 0\) ya da \(a = 0\) ve \(b > 0\) olmasıdır.
İspat
Farkı \(d(M) = (a - a')M + (b - b')\) ile gösterelim ve üç durumu ayıralım.
- \(a > a'\) ise \(M > \dfrac{b' - b}{a - a'}\) olan her \(M\) için \(d(M) > 0\)’dır.
- \(a = a'\) ise \(d(M) = b - b'\) sabittir; her \(M\) için pozitif olması \(b > b'\) demektir, aksi halde hiçbir \(M\) için pozitif değildir.
- \(a < a'\) ise \(M > \dfrac{b - b'}{a' - a}\) olan her \(M\) için \(d(M) < 0\)’dır; yani eşitsizlik yeterince büyük hiçbir \(M\) için sağlanmaz.
Böylece \(d(M) > 0\) eşitsizliği yeterince büyük her \(M\) için tam olarak ifadedeki iki durumda sağlanır. Özel durum, \(a' = b' = 0\) yazılarak hemen elde edilir.
\(\blacksquare\)
Yani iki \(M\)’li sayıyı karşılaştırırken önce \(M\)’nin katsayılarına bakarız; katsayısı büyük olan büyüktür. Katsayılar eşitse sabit terimlere bakarız. Örneğin \(2M + 3 > M + 1000\)’dir, çünkü \(2 > 1\); \(M\) büyüdükçe aradaki fark da büyür. Bir çözüm boyunca yalnız sonlu sayıda karşılaştırma yapıldığından hepsine birden yetecek bir \(M_0\) vardır. Dolayısıyla sembolik \(M\) ile yapılan her seçim, \(M_0\)’dan büyük herhangi bir sayının \(M\) yerine konduğu simpleks yöntemin seçimiyle aynıdır.
Optimallik de aynı anlamda okunur. Minimum probleminde bir tablonun her kriteri için ya \(a_j < 0\) ya da \(a_j = 0\) ve \(b_j \le 0\) ise, yeterince büyük her \(M\) için bütün \(z_j - c_j \le 0\) olur. Maksimum probleminde her kriter için ya \(a_j > 0\) ya da \(a_j = 0\) ve \(b_j \ge 0\) istenir. Böyle bir tabloya kısaca optimal tablo diyeceğiz. Tablonun gövdesi \(M\)’ye bağlı olmadığından, optimal tablonun temel çözümü yeterince büyük her \(M\) için M probleminin optimal çözümüdür (Simpleks yöntem bölümündeki optimallik koşulu). Yol boyunca yapay sütunlar atılmışsa bu, atılan yapay değişkenlerin kaldırıldığı küçültülmüş M problemi için geçerlidir; bunun neden yeterli olduğunu aşağıda göreceğiz.
Örnek 5.1 (M’li kriterleri sıralamak) Bir minimum probleminin tablosunda simpleks kriterleri
\[ \begin{aligned} z_1 - c_1 &= 2M - 5, & z_2 - c_2 &= \tfrac{1}{3}M - 1, \\ z_3 - c_3 &= 100, & z_4 - c_4 &= 0, \\ z_5 - c_5 &= -M + 50, & z_6 - c_6 &= 2M + 3 \end{aligned} \]
bulunmuş olsun. Bu sayıları yeterince büyük \(M\) için büyükten küçüğe sıralayarak baza girecek vektörü belirleyiniz.
Çözüm
Her sayıyı \(aM + b\) biçiminde okuyup \(M\)’nin katsayılarını yazalım: sırasıyla \(2\), \(\tfrac{1}{3}\), \(0\), \(0\), \(-1\), \(2\).
- En büyük katsayı \(2\)’dir ve iki kriterde görünür: \(2M - 5\) ve \(2M + 3\). Katsayılar eşit olduğu için sabit terimlere bakarız: \(3 > -5\), dolayısıyla \(2M + 3 > 2M - 5\).
- Sonra katsayısı \(\tfrac{1}{3}\) olan \(\tfrac{1}{3}M - 1\) gelir.
- Katsayısı \(0\) olan iki sayı \(100\) ve \(0\)’dır; \(100 > 0\).
- En küçüğü, katsayısı \(-1\) olan \(-M + 50\)’dir.
Sıralama
\[2M + 3 > 2M - 5 > \tfrac{1}{3}M - 1 > 100 > 0 > -M + 50\]
olur. \(\tfrac{1}{3}M - 1\) sayısının \(100\)’den büyük olduğuna şaşırmamak gerekir: bu yalnız \(M > 303\) için doğrudur, ama \(M\) zaten karşılaştırıldığı her sayıdan büyük kabul ediliyor. \(M = 1000\) alarak sağlayalım: sayılar sırasıyla \(2003\), \(1995\), \(332{,}3\ldots\), \(100\), \(0\) ve \(-950\) olur; sıralama aynıdır.
Minimum probleminde en büyük pozitif kriterin sütunu baza girer. Pozitif kriterler ilk dördüdür ve en büyüğü \(z_6 - c_6 = 2M + 3\)’tür; \(v_6\) baza girer. (Aynı kriterler bir maksimum probleminde bulunsaydı en negatif kriter, yani \(-M + 50\) seçilir ve \(v_5\) baza girerdi.)
\(\blacksquare\)
5.3 Bazdan Çıkan Yapay Değişkenin Sütunu
Simpleks yöntemden farklı olarak Büyük M yönteminde tablolar ilerledikçe daralır. Bir yapay değişken bazdan çıktığında değeri \(0\) olur. Amacımız zaten onu sıfırda tutmak olduğundan, onu yeniden baza almanın hiçbir yararı yoktur.
Not. Bazdan çıkan bir yapay değişkenin sütunu sonraki tablolarda yazılmaz.
Bu kuralın gerekçesi şudur. Sütunu atmak, o yapay değişkeni kalıcı olarak \(0\)’a sabitlemek demektir. Geriye kalan tablo, bu yapay değişkenin hiç eklenmediği küçültülmüş M probleminin tablosudur: diğer sütunlar baz vektörleri cinsinden aynı biçimde yazılır ve atılan sütun hiçbir hesaba girmez. Orijinal problemin her uygun çözümü \(\vec{x}\) için \((\vec{x}, \vec{0})\) bu küçültülmüş M probleminin de uygun çözümüdür (Önerme 5.1); dolayısıyla sütunu atmakla orijinal problemin hiçbir çözümünü kaybetmeyiz. Kazancımız, her tabloda bir sütun daha az hesaplamaktır.
5.4 Yöntemin Sonuçları
Simpleks yöntem M problemini çözüp optimal tabloya ulaşınca yapay değişkenlerin durumuna bakılır. Üç durum vardır: yapay değişkenlerin hepsi bazdan çıkmıştır; bazda pozitif değerli bir yapay değişken kalmıştır; bazda yalnız sıfır değerli yapay değişkenler kalmıştır. Birinci ve üçüncü durum aşağıdaki teoremde birlikte ele alınır.
Teorem 5.1 (Yapay değişkenleri sıfır olan optimal tablo) M probleminin optimal tablosunda bütün yapay değişkenlerin değeri \(0\) olsun; yani yapay değişkenler ya bazda değildir ya da bazda \(0\) değeriyle bulunur. Bu tablonun temel çözümünden yapay değişkenler atılarak elde edilen \(\hat{\vec{x}}\) orijinal problemin optimal çözümüdür ve optimal değer \(\vec{c}^{\,T}\hat{\vec{x}} = z_0\)’dır.
İspat
Minimum problemi için yapalım. Tablonun temel çözümü \((\hat{\vec{x}}, \vec{0})\) M probleminin uygun çözümüdür. Önerme 5.1 gereği \(\hat{\vec{x}}\) orijinal problemin uygun çözümüdür ve amaç değeri \(\vec{c}^{\,T}\hat{\vec{x}}\)’tir. Bu değer \(z_0\)’a eşittir, çünkü \(c_B\) sütunundaki \(M\)’ler sıfır değerli yapay değişkenlerle çarpılır ve \(z_0\)’da \(M\) kalmaz.
Şimdi \(\bar{\vec{x}}\) orijinal problemin herhangi bir uygun çözümü olsun. Önerme 5.1 gereği \((\bar{\vec{x}}, \vec{0})\) M probleminin uygun çözümüdür ve amaç değeri \(\vec{c}^{\,T}\bar{\vec{x}}\)’tir. Tablo optimal olduğundan yeterince büyük her \(M\) için \((\hat{\vec{x}}, \vec{0})\) M probleminin (sütunlar atılmışsa küçültülmüş M probleminin; son paragrafa bakınız) optimal çözümüdür; o halde
\[\vec{c}^{\,T}\hat{\vec{x}} \le \vec{c}^{\,T}\bar{\vec{x}}\]
olur. \(\bar{\vec{x}}\) keyfi olduğundan \(\hat{\vec{x}}\) orijinal problemin optimal çözümüdür. Maksimum probleminde eşitsizlik ters yönde yazılır, gerisi aynıdır.
Yol boyunca bazı yapay sütunlar atılmışsa, tablo bu yapay değişkenlerin kaldırıldığı küçültülmüş M probleminin tablosudur. \((\bar{\vec{x}}, \vec{0})\) o problemin de uygun çözümü olduğundan akıl yürütme değişmez.
\(\blacksquare\)
Yani optimal tabloda yapay değişkenlerin hepsi sıfırsa iş bitmiştir: tablonun gösterdiği çözüm orijinal problemin optimal çözümüdür. İkinci durum ise tam tersini söyler.
Teorem 5.2 (Bazda pozitif yapay değişken kalması) M probleminin optimal tablosunda bazda pozitif değerli bir yapay değişken varsa orijinal problemin uygun çözümü yoktur.
İspat
Minimum problemi için yapalım. Tablonun temel çözümü \((\hat{\vec{x}}, \hat{\vec{x}}_u)\) olsun. Bu değerler \(v_0\) sütununda durur ve \(M\)’ye bağlı değildir. Yapay değişkenlerin değerlerinin toplamını \(s\) ile gösterelim; varsayım gereği \(s > 0\)’dır. Tablonun amaç değeri
\[z_0 = \vec{c}^{\,T}\hat{\vec{x}} + Ms\]
dir. Orijinal problemin bir \(\bar{\vec{x}}\) uygun çözümü olduğunu varsayalım. Önerme 5.1 gereği \((\bar{\vec{x}}, \vec{0})\), M probleminin amaç değeri \(\vec{c}^{\,T}\bar{\vec{x}}\) olan bir uygun çözümüdür. Tablo optimal olduğundan bir \(M_0\)’dan büyük her \(M\) için
\[\vec{c}^{\,T}\hat{\vec{x}} + Ms \le \vec{c}^{\,T}\bar{\vec{x}}, \quad \text{yani} \quad M \le \frac{\vec{c}^{\,T}\bar{\vec{x}} - \vec{c}^{\,T}\hat{\vec{x}}}{s}\]
olmalıdır. Sağ taraf \(M\)’den bağımsız bir sayıdır; \(M\) onu aştığı anda eşitsizlik bozulur. Bu çelişki, orijinal problemin uygun çözümü olmadığını gösterir.
Maksimum probleminde amaç değeri \(\vec{c}^{\,T}\hat{\vec{x}} - Ms\)’dir ve optimallik \(\vec{c}^{\,T}\hat{\vec{x}} - Ms \ge \vec{c}^{\,T}\bar{\vec{x}}\) verir; bu da \(M \le (\vec{c}^{\,T}\hat{\vec{x}} - \vec{c}^{\,T}\bar{\vec{x}})/s\) demektir ve aynı biçimde çelişkiye varılır. Atılmış yapay sütunlar varsa, Teorem 5.1 ispatındaki gibi küçültülmüş M problemiyle aynı akıl yürütme yapılır.
\(\blacksquare\)
Yani yöntem, orijinal problemin uygun çözümü olup olmadığını kendiliğinden söyler. Optimal tabloda bazda pozitif bir yapay değişken kaldıysa, \(M\)’nin büyük cezasına rağmen yapay değişken sıfıra indirilememiştir; bunun tek nedeni kısıtların birlikte sağlanamamasıdır. Bu durumda en iyi çözümden söz edilemez. Böyle bir sonuçla karşılaşınca modelin kuruluşunu da gözden geçirmek gerekir: çoğu zaman bir kısıtın yönü yanlış yazılmıştır ya da veriler birbiriyle çelişir.
Geriye üçüncü durum kalıyor: yapay değişken bazda, ama değeri \(0\). Teorem 5.1 bu durumda da çözümün optimal olduğunu söyler; tablonun gösterdiği çözüm dejenere bir temel çözümdür (Tanım 2.6). Aşağıdaki önerme, bazda kalan yapay değişkenden nasıl kurtulunacağını anlatır.
Önerme 5.3 (Bazda sıfır değerli yapay değişken) Bir tabloda \(x_u\) yapay değişkeni \(r\). satırda \(y_{r0} = 0\) değeriyle bazda olsun.
- Yapay olmayan bir \(v_k\) sütunu için \(y_{rk} \ne 0\) ise \(y_{rk}\) pivot alınarak \(x_u\) bazdan çıkarılabilir. Yeni tablonun \(v_0\) sütunu eskisiyle aynıdır; yani aynı çözüm, \(x_u\)’yu içermeyen bir bazla elde edilir.
- Yapay olmayan bütün \(v_j\) sütunları için \(y_{rj} = 0\) ise orijinal problemin kısıtlarından biri diğerlerinin lineer kombinasyonudur, yani gereksizdir. Yapay değişkenler sıfırken \(r\). satır \(0 = 0\) denklemine dönüşür ve tablodan silinebilir.
İspat
1. Pivot sıfırdan farklı olduğu için dönüşüm kuralı (Bölüm 4.4) uygulanabilir. Yeni tabloda \(x_k\) satırının değeri \(y_{r0} / y_{rk} = 0\) olur. Diğer her \(i\) satırının yeni değeri
\[y_{i0} - \frac{y_{ik}\, y_{r0}}{y_{rk}} = y_{i0} - 0 = y_{i0}\]
dır. Demek ki bütün değişkenlerin değerleri aynı kalır ve hiçbiri negatif olmaz. Oran testi pivotu pozitif seçiyordu, çünkü değerlerin negatif olmaması gerekiyordu; burada değerler hiç değişmediği için \(y_{rk}\) negatif de olabilir.
2. Simpleks tablosunun her satırı, başlangıç tablosunun satırlarından elemanter satır işlemleriyle elde edilir. Bu yüzden \(r\). satır, başlangıç tablosunun \(m\) satırının \(w_1, \dots, w_m\) katsayılı bir lineer kombinasyonudur. Bu katsayıların hepsi sıfır olamaz, çünkü \(r\). satırın \(x_u\) sütununda \(1\) vardır. Başlangıç tablosunun \(i\). satırının yapay olmayan sütunlardaki ve \(v_0\) sütunundaki elemanları, orijinal problemin \(i\). kısıtının katsayıları \(a_{ij}\) ve sağ tarafı \(b_i\)’dir. \(r\). satırın bu sütunlardaki bütün elemanları sıfır olduğundan
\[\sum_{i=1}^{m} w_i\, a_{ij} = 0 \ \ \text{(her } j \text{ için)}, \qquad \sum_{i=1}^{m} w_i\, b_i = 0\]
olur. \(w_l \ne 0\) olan bir \(l\) seçelim. \(l\). kısıtın iki yanı, diğer kısıtların \(-w_i / w_l\) katsayılarıyla toplamına eşittir; yani \(l\). kısıt diğerlerinden kendiliğinden çıkar ve gereksizdir. Son olarak \(r\). satırın yapay olmayan sütunlardaki elemanları ve \(y_{r0}\) sıfır olduğundan, yapay değişkenler sıfır alınınca bu satır \(0 = 0\) der; silinmesi hiçbir bilgiyi kaybettirmez.
\(\blacksquare\)
Yani bazda sıfır değerle kalan yapay değişken bir sorun değildir: çözüm uygundur ve optimaldir. İstenirse yapay değişken birinci maddedeki pivotla bazdan çıkarılır; bu mümkün değilse problemde gereksiz bir kısıt vardır ve onun satırı atılır. Birinci maddedeki pivot yalnız bazı değiştirir: yeni tablonun \(z_j - c_j\) satırı optimallik biçimini korumayabilir, ama gösterdiği çözüm aynı olduğundan bu çözüm optimal kalır.
5.5 Büyük M Yöntemiyle Çözüm
Şimdi yöntemi adım adım toplayalım ve örneklerde uygulayalım.
- Standart form. Sağ tarafı negatif olan satırları \(-1\) ile çarp. \(\le\) kısıtlara aylak değişken ekle, \(\ge\) kısıtlardan artık değişken çıkar (Tanım 1.8); eşitliklere dokunma.
- Yapay değişkenler. Birim sütunu olmayan her denkleme bir yapay değişken ekle; amaç katsayısı minimumda \(+M\), maksimumda \(-M\)’dir. Problem artık simpleks yöntem ile çözülebilir haldedir.
- Başlangıç tablosu. Birim sütunları veren değişkenler (aylaklar ve yapaylar) başlangıç bazıdır. \(c_B\) sütununda \(\pm M\) bulunduğu için \(z_j - c_j\) satırı artık \(-c_j\) değildir: her sütun için \(z_j = \vec{c}_B^{\,T} v_j\) hesaplanır ve \(c_j\) çıkarılır; ayrıca \(z_0 = \vec{c}_B^{\,T} v_0\).
- Giren vektör. Minimum probleminde en büyük pozitif, maksimum probleminde en negatif \(z_j - c_j\) girer. \(aM + b\) biçimindeki kriterler karşılaştırılırken önce \(M\)’nin katsayısına, eşitse sabit terime bakılır (Önerme 5.2).
- Çıkan vektör ve yeni tablo. Oran testi ve dönüşüm kuralı simpleks yöntemdekinin aynısıdır (Bölüm 4.4). Bazdan çıkan yapay değişkenin sütunu yeni tabloda yazılmaz. Giren sütunda pozitif eleman yoksa oran testi yapılamaz; bu durum Sınırsız çözüm ve alternatif optimal çözüm bölümünde incelenir.
- Sonuç. Optimal tabloda yapay değişkenlerin hepsi sıfırsa tablonun çözümü orijinal problemin optimal çözümüdür (Teorem 5.1). Bazda pozitif bir yapay değişken kaldıysa orijinal problemin uygun çözümü yoktur (Teorem 5.2).
Örnek 5.2 (Büyük M yöntemiyle bir minimum problemi) Aşağıdaki problemi Büyük M yöntemiyle çözünüz.
\[ \begin{aligned} 2x_1 + x_2 &\ge 2 \\ x_1 + 3x_2 &\le 3 \\ x_2 &\le 4 \\ x_1, x_2 &\ge 0 \\ \min z &= -3x_1 + x_2 \end{aligned} \]
Çözüm
Standart form. Önce problemi standart forma getirelim. Birinci kısıt \(\ge\) olduğundan \(x_3\) artık değişkenini çıkarırız; ikinci ve üçüncü kısıtlar \(\le\) olduğundan \(x_4\) ve \(x_5\) aylak değişkenlerini ekleriz. Sağ taraflar \(2, 3, 4\) negatif değildir:
\[ \begin{aligned} 2x_1 + x_2 - x_3 &= 2 \\ x_1 + 3x_2 + x_4 &= 3 \\ x_2 + x_5 &= 4 \\ x_j \ge 0, \quad j &= \overline{1,5} \\ \min z &= -3x_1 + x_2 + 0x_3 + 0x_4 + 0x_5 \end{aligned} \]
Çözülebilir hal. \(x_4\) yalnız ikinci, \(x_5\) yalnız üçüncü denklemde ve katsayısı \(1\) ile görünür; bu iki denklemin birim sütunu hazırdır. Birinci denklemde ise \(x_3\)’ün katsayısı \(-1\)’dir. Standart form birim matris içermediği için henüz simpleks yöntem ile çözülebilir halde değildir. Yalnız birinci denkleme \(x_{u_1}\) yapay değişkenini ekleriz; minimum problemi olduğundan amaç katsayısı \(+M\)’dir:
\[ \begin{aligned} 2x_1 + x_2 - x_3 + x_{u_1} &= 2 \\ x_1 + 3x_2 + x_4 &= 3 \\ x_2 + x_5 &= 4 \\ x_1, \dots, x_5, x_{u_1} &\ge 0 \\ \min z &= -3x_1 + x_2 + 0x_3 + 0x_4 \\ &\quad + 0x_5 + Mx_{u_1} \end{aligned} \]
Artık \(v_{u_1}\), \(v_4\), \(v_5\) sütunları \(3 \times 3\) birim matrisi oluşturur. Başlangıç bazı \(B_0 = (v_{u_1}, v_4, v_5)\), başlangıç çözümü \(x_{u_1} = 2\), \(x_4 = 3\), \(x_5 = 4\) ve diğer değişkenler \(0\)’dır.
Simpleks kriterleri. Baz maliyetleri \(\vec{c}_B = (M, 0, 0)\)’dır. Her sütun için \(z_j = \vec{c}_B^{\,T} v_j\) çarpımını, \(c_B\) sütunuyla \(v_j\) sütununun karşılıklı çarpımlarını toplayarak hesaplar ve \(c_j\)’yi çıkarırız:
\[ \begin{aligned} z_1 - c_1 &= (M \cdot 2 + 0 \cdot 1 + 0 \cdot 0) - (-3) = 2M + 3, \\[1mm] z_2 - c_2 &= (M \cdot 1 + 0 \cdot 3 + 0 \cdot 1) - 1 = M - 1, \\[1mm] z_3 - c_3 &= (M \cdot (-1) + 0 \cdot 0 + 0 \cdot 0) - 0 = -M, \\[1mm] z_{u_1} - c_{u_1} &= (M \cdot 1 + 0 \cdot 0 + 0 \cdot 0) - M = 0, \\[1mm] z_0 &= M \cdot 2 + 0 \cdot 3 + 0 \cdot 4 = 2M. \end{aligned} \]
\(v_4\) ve \(v_5\) de baz vektörleri olduğundan kriterleri \(0\)’dır. Amaç değerindeki \(2M\), bazdaki yapay değişkenin değeri olan \(2\)’nin cezasıdır.
Giren ve çıkan vektör. Minimum probleminde en büyük pozitif \(z_j - c_j\) girer. Pozitif kriterler \(2M + 3\) ve \(M - 1\)’dir. \(M\)’nin katsayıları \(2 > 1\) olduğundan en büyüğü \(2M + 3\)’tür (Önerme 5.2) ve \(v_1\) baza girer. Oran testi \(v_1\) sütununun pozitif elemanlarıyla yapılır; \(x_5\) satırında eleman \(0\) olduğundan o satır dikkate alınmaz:
\[\min\left( \frac{2}{2}, \frac{3}{1} \right) = \min(1, 3) = 1.\]
En küçük oran \(x_{u_1}\) satırındadır; \(v_{u_1}\) bazdan çıkar ve pivot \(2\)’dir.
| \(c_j\) | \(-3\) | \(1\) | \(0\) | \(0\) | \(0\) | \(M\) | |||
|---|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | \(v_{u_1}\) | Oran |
| \(x_{u_1}\) | \(M\) | \(2\) | \([2]\) | \(1\) | \(-1\) | \(0\) | \(0\) | \(1\) | \(\frac{2}{2} \Rightarrow\) |
| \(x_4\) | \(0\) | \(3\) | \(1\) | \(3\) | \(0\) | \(1\) | \(0\) | \(0\) | \(\frac{3}{1}\) |
| \(x_5\) | \(0\) | \(4\) | \(0\) | \(1\) | \(0\) | \(0\) | \(1\) | \(0\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = 2M\) | \(2M+3 \Uparrow\) | \(M-1\) | \(-M\) | \(0\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot satırı \(2\)’ye bölünür ve \(x_1\) satırı olur; \(c_B\) değeri \(c_1 = -3\)’tür:
\[(1 \mid 1,\ \tfrac{1}{2},\ -\tfrac{1}{2},\ 0,\ 0).\]
\(x_4\) satırının \(v_1\) sütunundaki elemanı \(1\) olduğundan bu satırdan yeni pivot satırı bir kez çıkarılır:
\[ \begin{aligned} &(3 - 1 \mid 1 - 1,\ 3 - \tfrac{1}{2},\ 0 + \tfrac{1}{2},\ 1,\ 0) \\[1mm] &\quad = (2 \mid 0,\ \tfrac{5}{2},\ \tfrac{1}{2},\ 1,\ 0). \end{aligned} \]
\(x_5\) satırının \(v_1\) sütunundaki elemanı \(0\) olduğundan bu satır değişmez. \(x_{u_1}\) bazdan çıktığı için \(v_{u_1}\) sütunu artık yazılmaz. \(z_j - c_j\) satırını yeni \(\vec{c}_B = (-3, 0, 0)\) ile yeniden hesaplayalım:
\[ \begin{aligned} z_2 - c_2 &= (-3) \cdot \tfrac{1}{2} + 0 \cdot \tfrac{5}{2} + 0 \cdot 1 - 1 = -\tfrac{5}{2}, \\[1mm] z_3 - c_3 &= (-3) \cdot \left(-\tfrac{1}{2}\right) + 0 \cdot \tfrac{1}{2} + 0 \cdot 0 - 0 = \tfrac{3}{2}, \\[1mm] z_0 &= (-3) \cdot 1 + 0 \cdot 2 + 0 \cdot 4 = -3. \end{aligned} \]
Dönüşüm kuralı (Bölüm 4.4) da aynı sayıları verir. Örneğin \(v_2\) sütunu için eski kriterden, pivot sütunundaki \(2M + 3\) ile yeni pivot satırındaki \(\tfrac{1}{2}\)’nin çarpımı çıkarılır: \((M - 1) - (2M + 3) \cdot \tfrac{1}{2} = -\tfrac{5}{2}\). Bazda yapay değişken kalmadığı için \(M\)’ler birbirini götürdü ve satırdan tamamen kayboldu.
| \(c_j\) | \(-3\) | \(1\) | \(0\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | Oran |
| \(x_1\) | \(-3\) | \(1\) | \(1\) | \(\frac{1}{2}\) | \(-\frac{1}{2}\) | \(0\) | \(0\) | \(-\) |
| \(x_4\) | \(0\) | \(2\) | \(0\) | \(\frac{5}{2}\) | \([\frac{1}{2}]\) | \(1\) | \(0\) | \(\frac{2}{1/2} \Rightarrow\) |
| \(x_5\) | \(0\) | \(4\) | \(0\) | \(1\) | \(0\) | \(0\) | \(1\) | \(-\) |
| \(z_j - c_j\) | \(z_0 = -3\) | \(0\) | \(-\frac{5}{2}\) | \(\frac{3}{2} \Uparrow\) | \(0\) | \(0\) |
Birinci iterasyon tablosunda (Tablo 5.2) \(B_0\) bazından \(B_1 = (v_1, v_4, v_5)\) bazına geçildi; çözüm \(X_1 = (x_1, \dots, x_5) = (1, 0, 0, 2, 4)\)’tür. Yapay değişken \(0\) olduğu için bu, orijinal problemin uygun bir çözümüdür: \((x_1, x_2) = (1, 0)\) uygun bölgenin bir köşesidir.
Pozitif kriter \(z_3 - c_3 = \tfrac{3}{2}\) kaldığı için minimuma ulaşılmadı; en büyük (ve tek) pozitif kriter bu olduğundan \(v_3\) baza girer. \(v_3\) sütununda yalnız \(x_4\) satırının elemanı pozitiftir. Oran \(2 / \tfrac{1}{2} = 4\)’tür; \(v_4\) bazdan çıkar ve pivot \(\tfrac{1}{2}\)’dir.
İkinci iterasyon. Pivot satırı \(\tfrac{1}{2}\)’ye bölünür, yani \(2\) ile çarpılır ve \(x_3\) satırı olur: \((4 \mid 0,\ 5,\ 1,\ 2,\ 0)\). \(x_1\) satırının \(v_3\) sütunundaki elemanı \(-\tfrac{1}{2}\) olduğundan bu satıra yeni pivot satırının \(\tfrac{1}{2}\) katı eklenir:
\[ \begin{aligned} &(1 + 2 \mid 1,\ \tfrac{1}{2} + \tfrac{5}{2},\ -\tfrac{1}{2} + \tfrac{1}{2},\ 0 + 1,\ 0) \\[1mm] &\quad = (3 \mid 1,\ 3,\ 0,\ 1,\ 0). \end{aligned} \]
\(x_5\) satırı yine değişmez. Kriterler \(\vec{c}_B = (-3, 0, 0)\) ile:
\[ \begin{aligned} z_2 - c_2 &= (-3) \cdot 3 + 0 \cdot 5 + 0 \cdot 1 - 1 = -10, \\[1mm] z_4 - c_4 &= (-3) \cdot 1 + 0 \cdot 2 + 0 \cdot 0 - 0 = -3, \\[1mm] z_0 &= (-3) \cdot 3 + 0 \cdot 4 + 0 \cdot 4 = -9. \end{aligned} \]
| \(c_j\) | \(-3\) | \(1\) | \(0\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) |
| \(x_1\) | \(-3\) | \(3\) | \(1\) | \(3\) | \(0\) | \(1\) | \(0\) |
| \(x_3\) | \(0\) | \(4\) | \(0\) | \(5\) | \(1\) | \(2\) | \(0\) |
| \(x_5\) | \(0\) | \(4\) | \(0\) | \(1\) | \(0\) | \(0\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = -9\) | \(0\) | \(-10\) | \(0\) | \(-3\) | \(0\) |
İkinci iterasyon tablosunda (Tablo 5.3) \(B_2 = (v_1, v_3, v_5)\) bazına geçildi. Pozitif kriter kalmadı: bütün \(z_j - c_j \le 0\), tablo optimaldir. Bazda yapay değişken bulunmadığından Teorem 5.1 gereği optimal çözüm
\[X^{*} = (x_1, x_2, x_3, x_4, x_5) = (3, 0, 4, 0, 4), \qquad \min z = -3 \cdot 3 + 0 = -9\]
olur. Aylak ve artık değişkenler de anlamlıdır: birinci kısıtta \(2 \cdot 3 + 0 = 6\) olup gereksinim \(x_3 = 4\) birim aşılmıştır; ikinci kısıt \(3 + 0 = 3\) ile tam sağlanır (\(x_4 = 0\)); üçüncü kısıtta \(x_5 = 4\) birim boşluk vardır.
Çözümün başındaki şekil yöntemin izlediği yolu grafik yöntemle karşılaştırıyor. Başlangıç çözümü \((x_1, x_2) = (0, 0)\) uygun bölgenin dışındadır: \(2x_1 + x_2 \ge 2\) kısıtı sağlanmaz ve eksik kalan \(2\) birimi \(x_{u_1} = 2\) üstlenir. Birinci iterasyon yapay değişkeni sıfıra indirip uygun bölgenin \((1, 0)\) köşesine, ikinci iterasyon optimal \((3, 0)\) köşesine gider. Uygun bölge üç köşeli bir üçgendir ve köşelerdeki amaç değerleri \((1, 0)\)’da \(-3\), \((3, 0)\)’da \(-9\), \((\tfrac{3}{5}, \tfrac{4}{5})\)’te \(-\tfrac{9}{5} + \tfrac{4}{5} = -1\)’dir; en küçüğü gerçekten \(-9\)’dur.
\(\blacksquare\)
İki yapay değişkenli bir örnekte \(M\)’nin katsayısının adım adım nasıl küçüldüğünü daha açık görürüz.
Örnek 5.3 (İki yapay değişkenli bir minimum problemi) Örnek 1.20 diyetinin modelini Büyük M yöntemiyle çö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
Çözülebilir hal. Standart formda iki kısıttan da artık değişken çıkarılır (\(x_3\) ve \(x_4\)). Artık değişkenler birim sütun vermediği için iki denkleme de yapay değişken ekleriz; minimum problemi olduğundan katsayıları \(+M\)’dir (bkz. Örnek 1.20):
\[ \begin{aligned} x_1 + x_2 - x_3 + x_{u_1} &= 4 \\ x_1 + 3x_2 - x_4 + x_{u_2} &= 6 \\ x_1, x_2, x_3, x_4, x_{u_1}, x_{u_2} &\ge 0 \\ \min z &= 2x_1 + 3x_2 + 0x_3 + 0x_4 \\ &\quad + Mx_{u_1} + Mx_{u_2} \end{aligned} \]
Başlangıç bazı \(B_0 = (v_{u_1}, v_{u_2})\), \(\vec{c}_B = (M, M)\)’dir.
Simpleks kriterleri.
\[ \begin{aligned} z_1 - c_1 &= (M \cdot 1 + M \cdot 1) - 2 = 2M - 2, \\[1mm] z_2 - c_2 &= (M \cdot 1 + M \cdot 3) - 3 = 4M - 3, \\[1mm] z_3 - c_3 &= (M \cdot (-1) + M \cdot 0) - 0 = -M, \\[1mm] z_4 - c_4 &= (M \cdot 0 + M \cdot (-1)) - 0 = -M, \\[1mm] z_0 &= M \cdot 4 + M \cdot 6 = 10M. \end{aligned} \]
Minimum probleminde en büyük pozitif kriter girer. Pozitif kriterler \(2M - 2\) ve \(4M - 3\)’tür; \(4 > 2\) olduğundan \(v_2\) baza girer. Oranlar \(\tfrac{4}{1} = 4\) ve \(\tfrac{6}{3} = 2\)’dir; \(v_{u_2}\) bazdan çıkar ve pivot \(3\)’tür.
| \(c_j\) | \(2\) | \(3\) | \(0\) | \(0\) | \(M\) | \(M\) | |||
|---|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_{u_1}\) | \(v_{u_2}\) | Oran |
| \(x_{u_1}\) | \(M\) | \(4\) | \(1\) | \(1\) | \(-1\) | \(0\) | \(1\) | \(0\) | \(\frac{4}{1}\) |
| \(x_{u_2}\) | \(M\) | \(6\) | \(1\) | \([3]\) | \(0\) | \(-1\) | \(0\) | \(1\) | \(\frac{6}{3} \Rightarrow\) |
| \(z_j - c_j\) | \(z_0 = 10M\) | \(2M-2\) | \(4M-3 \Uparrow\) | \(-M\) | \(-M\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot satırı \(3\)’e bölünür ve \(x_2\) satırı olur: \(\big(2 \mid \tfrac{1}{3},\ 1,\ 0,\ -\tfrac{1}{3},\ 0\big)\); burada son eleman \(v_{u_1}\) sütunundadır. \(x_{u_1}\) satırından yeni pivot satırı bir kez çıkarılır:
\[ \begin{aligned} &(4 - 2 \mid 1 - \tfrac{1}{3},\ 0,\ -1,\ 0 + \tfrac{1}{3},\ 1) \\[1mm] &\quad = (2 \mid \tfrac{2}{3},\ 0,\ -1,\ \tfrac{1}{3},\ 1). \end{aligned} \]
\(v_{u_2}\) sütunu atılır. Yeni \(\vec{c}_B = (M, 3)\) ile kriterler:
\[ \begin{aligned} z_1 - c_1 &= M \cdot \tfrac{2}{3} + 3 \cdot \tfrac{1}{3} - 2 = \tfrac{2}{3}M - 1, \\[1mm] z_3 - c_3 &= M \cdot (-1) + 3 \cdot 0 - 0 = -M, \\[1mm] z_4 - c_4 &= M \cdot \tfrac{1}{3} + 3 \cdot \left(-\tfrac{1}{3}\right) - 0 = \tfrac{1}{3}M - 1, \\[1mm] z_0 &= M \cdot 2 + 3 \cdot 2 = 2M + 6. \end{aligned} \]
| \(c_j\) | \(2\) | \(3\) | \(0\) | \(0\) | \(M\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_{u_1}\) | Oran |
| \(x_{u_1}\) | \(M\) | \(2\) | \([\frac{2}{3}]\) | \(0\) | \(-1\) | \(\frac{1}{3}\) | \(1\) | \(\frac{2}{2/3} \Rightarrow\) |
| \(x_2\) | \(3\) | \(2\) | \(\frac{1}{3}\) | \(1\) | \(0\) | \(-\frac{1}{3}\) | \(0\) | \(\frac{2}{1/3}\) |
| \(z_j - c_j\) | \(z_0 = 2M+6\) | \(\frac{2}{3}M-1 \Uparrow\) | \(0\) | \(-M\) | \(\frac{1}{3}M-1\) | \(0\) |
Pozitif kriterler \(\tfrac{2}{3}M - 1\) ve \(\tfrac{1}{3}M - 1\)’dir; \(\tfrac{2}{3} > \tfrac{1}{3}\) olduğundan \(v_1\) baza girer. Oranlar \(2 / \tfrac{2}{3} = 3\) ve \(2 / \tfrac{1}{3} = 6\)’dır; \(v_{u_1}\) bazdan çıkar ve pivot \(\tfrac{2}{3}\)’tür.
İkinci iterasyon. Pivot satırı \(\tfrac{2}{3}\)’e bölünür, yani \(\tfrac{3}{2}\) ile çarpılır ve \(x_1\) satırı olur: \(\big(3 \mid 1,\ 0,\ -\tfrac{3}{2},\ \tfrac{1}{2}\big)\). \(x_2\) satırından yeni pivot satırının \(\tfrac{1}{3}\) katı çıkarılır:
\[ \begin{aligned} &(2 - 1 \mid \tfrac{1}{3} - \tfrac{1}{3},\ 1,\ 0 + \tfrac{1}{2},\ -\tfrac{1}{3} - \tfrac{1}{6}) \\[1mm] &\quad = (1 \mid 0,\ 1,\ \tfrac{1}{2},\ -\tfrac{1}{2}). \end{aligned} \]
\(v_{u_1}\) sütunu da atılır. \(\vec{c}_B = (2, 3)\) ile:
\[ \begin{aligned} z_3 - c_3 &= 2 \cdot \left(-\tfrac{3}{2}\right) + 3 \cdot \tfrac{1}{2} - 0 = -\tfrac{3}{2}, \\[1mm] z_4 - c_4 &= 2 \cdot \tfrac{1}{2} + 3 \cdot \left(-\tfrac{1}{2}\right) - 0 = -\tfrac{1}{2}, \\[1mm] z_0 &= 2 \cdot 3 + 3 \cdot 1 = 9. \end{aligned} \]
| \(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}\) |
Bütün \(z_j - c_j \le 0\) olduğundan tablo optimaldir ve bazda yapay değişken yoktur. Optimal diyet \(x_1 = 3\) kg \(B_1\) ve \(x_2 = 1\) kg \(B_2\)’dir; en küçük maliyet \(\min z = 2 \cdot 3 + 3 \cdot 1 = 9\) TL’dir. Artık değişkenler \(x_3 = x_4 = 0\) olduğundan iki vitamin gereksinimi de tam karşılanır: \(3 + 1 = 4\) ve \(3 + 3 = 6\).
Amaç değerindeki \(M\)’nin katsayısı \(10 \to 2 \to 0\) diye azaldı. Bu katsayı bazdaki yapay değişkenlerin toplamıdır, yani eksik kalan vitamin miktarıdır: başlangıçta \(4 + 6 = 10\) birim, birinci iterasyonda yalnız \(x_{u_1} = 2\) birim A vitamini eksiktir. Uygun bölgenin köşeleri \((0, 4)\), \((3, 1)\), \((6, 0)\)’dır ve amaç değerleri \(12\), \(9\), \(12\)’dir; grafik yöntem de aynı sonucu verir.
\(\blacksquare\)
Maksimum probleminde yöntem aynıdır; yalnız yapay değişkenlerin amaç katsayısı \(-M\) olur ve seçim kuralı tersine döner.
Örnek 5.4 (Eşitlik ve büyük-eşit kısıtlı bir maksimum problemi) Aşağıdaki problemi Büyük M yöntemiyle çözünüz.
\[ \begin{aligned} x_1 + x_2 &\ge 3 \\ x_1 - x_2 &= 1 \\ x_1 + 2x_2 &\le 10 \\ x_1, x_2 &\ge 0 \\ \max z &= 2x_1 + x_2 \end{aligned} \]
Çözüm
Standart form. Birinci kısıttan \(x_3\) artık değişkenini çıkarır, üçüncü kısıta \(x_4\) aylak değişkenini ekleriz. İkinci kısıt eşitliktir ve sağ tarafı \(1 \ge 0\)’dır; olduğu gibi kalır:
\[ \begin{aligned} x_1 + x_2 - x_3 &= 3 \\ x_1 - x_2 &= 1 \\ x_1 + 2x_2 + x_4 &= 10 \\ x_j \ge 0, \quad j &= \overline{1,4} \\ \max z &= 2x_1 + x_2 + 0x_3 + 0x_4 \end{aligned} \]
Çözülebilir hal. Üçüncü denklemin birim sütunu \(x_4\)’tür. Birinci denklemde \(x_3\)’ün katsayısı \(-1\)’dir; ikinci denkleme ise hiç yeni değişken eklenmedi. Standart form birim matris içermediği için henüz simpleks yöntem ile çözülebilir halde değildir. Bu iki denkleme \(x_{u_1}\) ve \(x_{u_2}\) yapay değişkenlerini ekleriz; maksimum problemi olduğundan katsayıları \(-M\)’dir:
\[ \begin{aligned} x_1 + x_2 - x_3 + x_{u_1} &= 3 \\ x_1 - x_2 + x_{u_2} &= 1 \\ x_1 + 2x_2 + x_4 &= 10 \\ x_1, \dots, x_4, x_{u_1}, x_{u_2} &\ge 0 \\ \max z &= 2x_1 + x_2 + 0x_3 + 0x_4 \\ &\quad - Mx_{u_1} - Mx_{u_2} \end{aligned} \]
Başlangıç bazı \(B_0 = (v_{u_1}, v_{u_2}, v_4)\), \(\vec{c}_B = (-M, -M, 0)\)’dır.
Simpleks kriterleri.
\[ \begin{aligned} z_1 - c_1 &= (-M \cdot 1 - M \cdot 1 + 0 \cdot 1) - 2 = -2M - 2, \\[1mm] z_2 - c_2 &= (-M \cdot 1 - M \cdot (-1) + 0 \cdot 2) - 1 = -1, \\[1mm] z_3 - c_3 &= (-M \cdot (-1) - M \cdot 0 + 0 \cdot 0) - 0 = M, \\[1mm] z_0 &= -M \cdot 3 - M \cdot 1 + 0 \cdot 10 = -4M. \end{aligned} \]
\(v_2\) sütununda iki yapay satırın elemanları \(1\) ve \(-1\) olduğundan \(M\)’ler birbirini götürdü.
Giren ve çıkan vektör. Maksimum probleminde en negatif \(z_j - c_j\) girer. Negatif kriterler \(-2M - 2\) ve \(-1\)’dir. \(M\)’nin katsayıları \(-2 < 0\) olduğundan en negatifi \(-2M - 2\)’dir ve \(v_1\) baza girer. Oranlar \(\tfrac{3}{1}\), \(\tfrac{1}{1}\), \(\tfrac{10}{1}\)’dir; en küçüğü \(1\) olduğundan \(v_{u_2}\) bazdan çıkar ve pivot \(1\)’dir.
| \(c_j\) | \(2\) | \(1\) | \(0\) | \(0\) | \(-M\) | \(-M\) | |||
|---|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_{u_1}\) | \(v_{u_2}\) | Oran |
| \(x_{u_1}\) | \(-M\) | \(3\) | \(1\) | \(1\) | \(-1\) | \(0\) | \(1\) | \(0\) | \(\frac{3}{1}\) |
| \(x_{u_2}\) | \(-M\) | \(1\) | \([1]\) | \(-1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(\frac{1}{1} \Rightarrow\) |
| \(x_4\) | \(0\) | \(10\) | \(1\) | \(2\) | \(0\) | \(1\) | \(0\) | \(0\) | \(\frac{10}{1}\) |
| \(z_j - c_j\) | \(z_0 = -4M\) | \(-2M-2 \Uparrow\) | \(-1\) | \(M\) | \(0\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot \(1\) olduğundan \(x_{u_2}\) satırı aynen kalır ve \(x_1\) satırı olur: \((1 \mid 1,\ -1,\ 0,\ 0,\ 0)\); son eleman \(v_{u_1}\) sütunundadır. \(x_{u_1}\) ve \(x_4\) satırlarının \(v_1\) elemanları \(1\) olduğundan ikisinden de yeni pivot satırı bir kez çıkarılır:
\[ \begin{aligned} x_{u_1}&: \ (3 - 1 \mid 0,\ 1 + 1,\ -1,\ 0,\ 1) = (2 \mid 0,\ 2,\ -1,\ 0,\ 1), \\[1mm] x_4&: \ (10 - 1 \mid 0,\ 2 + 1,\ 0,\ 1,\ 0) = (9 \mid 0,\ 3,\ 0,\ 1,\ 0). \end{aligned} \]
\(v_{u_2}\) sütunu atılır. \(\vec{c}_B = (-M, 2, 0)\) ile:
\[ \begin{aligned} z_2 - c_2 &= -M \cdot 2 + 2 \cdot (-1) + 0 \cdot 3 - 1 = -2M - 3, \\[1mm] z_3 - c_3 &= -M \cdot (-1) + 2 \cdot 0 + 0 \cdot 0 - 0 = M, \\[1mm] z_0 &= -M \cdot 2 + 2 \cdot 1 + 0 \cdot 9 = -2M + 2. \end{aligned} \]
| \(c_j\) | \(2\) | \(1\) | \(0\) | \(0\) | \(-M\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_{u_1}\) | Oran |
| \(x_{u_1}\) | \(-M\) | \(2\) | \(0\) | \([2]\) | \(-1\) | \(0\) | \(1\) | \(\frac{2}{2} \Rightarrow\) |
| \(x_1\) | \(2\) | \(1\) | \(1\) | \(-1\) | \(0\) | \(0\) | \(0\) | \(-\) |
| \(x_4\) | \(0\) | \(9\) | \(0\) | \(3\) | \(0\) | \(1\) | \(0\) | \(\frac{9}{3}\) |
| \(z_j - c_j\) | \(z_0 = -2M+2\) | \(0\) | \(-2M-3 \Uparrow\) | \(M\) | \(0\) | \(0\) |
Tek negatif kriter \(-2M - 3\)’tür; \(v_2\) baza girer. \(x_1\) satırındaki \(-1\) oran testine girmez; oranlar \(\tfrac{2}{2} = 1\) ve \(\tfrac{9}{3} = 3\)’tür. \(v_{u_1}\) bazdan çıkar ve pivot \(2\)’dir. Bu tablonun çözümü \((x_1, x_2) = (1, 0)\) henüz uygun değildir: \(x_1 - x_2 = 1\) sağlanır ama \(x_1 + x_2 = 1 < 3\)’tür ve eksik \(2\) birimi \(x_{u_1} = 2\) taşır.
İkinci iterasyon. Pivot satırı \(2\)’ye bölünür ve \(x_2\) satırı olur: \(\big(1 \mid 0,\ 1,\ -\tfrac{1}{2},\ 0\big)\). \(x_1\) satırına yeni pivot satırı bir kez eklenir, \(x_4\) satırından üç kez çıkarılır:
\[ \begin{aligned} x_1&: \ (1 + 1 \mid 1,\ 0,\ 0 - \tfrac{1}{2},\ 0) = (2 \mid 1,\ 0,\ -\tfrac{1}{2},\ 0), \\[1mm] x_4&: \ (9 - 3 \mid 0,\ 0,\ 0 + \tfrac{3}{2},\ 1) = (6 \mid 0,\ 0,\ \tfrac{3}{2},\ 1). \end{aligned} \]
\(v_{u_1}\) sütunu da atılır. \(\vec{c}_B = (1, 2, 0)\) ile:
\[ \begin{aligned} z_3 - c_3 &= 1 \cdot \left(-\tfrac{1}{2}\right) + 2 \cdot \left(-\tfrac{1}{2}\right) + 0 \cdot \tfrac{3}{2} - 0 = -\tfrac{3}{2}, \\[1mm] z_0 &= 1 \cdot 1 + 2 \cdot 2 + 0 \cdot 6 = 5. \end{aligned} \]
| \(c_j\) | \(2\) | \(1\) | \(0\) | \(0\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | Oran |
| \(x_2\) | \(1\) | \(1\) | \(0\) | \(1\) | \(-\frac{1}{2}\) | \(0\) | \(-\) |
| \(x_1\) | \(2\) | \(2\) | \(1\) | \(0\) | \(-\frac{1}{2}\) | \(0\) | \(-\) |
| \(x_4\) | \(0\) | \(6\) | \(0\) | \(0\) | \([\frac{3}{2}]\) | \(1\) | \(\frac{6}{3/2} \Rightarrow\) |
| \(z_j - c_j\) | \(z_0 = 5\) | \(0\) | \(0\) | \(-\frac{3}{2} \Uparrow\) | \(0\) |
Yapay değişkenlerin hepsi bazdan çıktı; \((x_1, x_2) = (2, 1)\) orijinal problemin uygun bir çözümüdür ve \(z = 5\)’tir. Ama \(z_3 - c_3 = -\tfrac{3}{2} < 0\) olduğundan maksimuma ulaşılmadı; \(v_3\) baza girer. \(v_3\) sütununda yalnız \(x_4\) satırının elemanı pozitiftir: oran \(6 / \tfrac{3}{2} = 4\), \(v_4\) bazdan çıkar ve pivot \(\tfrac{3}{2}\)’dir.
Üçüncü iterasyon. Pivot satırı \(\tfrac{2}{3}\) ile çarpılır ve \(x_3\) satırı olur: \(\big(4 \mid 0,\ 0,\ 1,\ \tfrac{2}{3}\big)\). \(x_2\) ve \(x_1\) satırlarının \(v_3\) elemanları \(-\tfrac{1}{2}\) olduğundan ikisine de yeni pivot satırının \(\tfrac{1}{2}\) katı eklenir:
\[ \begin{aligned} x_2&: \ (1 + 2 \mid 0,\ 1,\ 0,\ 0 + \tfrac{1}{3}) = (3 \mid 0,\ 1,\ 0,\ \tfrac{1}{3}), \\[1mm] x_1&: \ (2 + 2 \mid 1,\ 0,\ 0,\ 0 + \tfrac{1}{3}) = (4 \mid 1,\ 0,\ 0,\ \tfrac{1}{3}). \end{aligned} \]
\(\vec{c}_B = (1, 2, 0)\) ile:
\[ \begin{aligned} z_4 - c_4 &= 1 \cdot \tfrac{1}{3} + 2 \cdot \tfrac{1}{3} + 0 \cdot \tfrac{2}{3} - 0 = 1, \\[1mm] z_0 &= 1 \cdot 3 + 2 \cdot 4 + 0 \cdot 4 = 11. \end{aligned} \]
| \(c_j\) | \(2\) | \(1\) | \(0\) | \(0\) | ||
|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
| \(x_2\) | \(1\) | \(3\) | \(0\) | \(1\) | \(0\) | \(\frac{1}{3}\) |
| \(x_1\) | \(2\) | \(4\) | \(1\) | \(0\) | \(0\) | \(\frac{1}{3}\) |
| \(x_3\) | \(0\) | \(4\) | \(0\) | \(0\) | \(1\) | \(\frac{2}{3}\) |
| \(z_j - c_j\) | \(z_0 = 11\) | \(0\) | \(0\) | \(0\) | \(1\) |
Maksimum probleminde bütün \(z_j - c_j \ge 0\) olunca tablo optimaldir; bu tabloda öyledir. Bazda yapay değişken olmadığından optimal çözüm
\[X^{*} = (x_1, x_2, x_3, x_4) = (4, 3, 4, 0), \qquad \max z = 2 \cdot 4 + 3 = 11\]
dir. Sağlama: \(4 + 3 = 7 \ge 3\) (fazla \(x_3 = 4\)), \(4 - 3 = 1\) ve \(4 + 6 = 10\) (\(x_4 = 0\)).
Eşitlik kısıtı yüzünden uygun çözümler bir doğru parçası oluşturur: \(x_1 = x_2 + 1\) yazılırsa birinci kısıt \(x_2 \ge 1\), üçüncü kısıt \(x_2 \le 3\) verir. Parçanın uç noktaları \((2, 1)\) ve \((4, 3)\)’tür ve amaç değerleri \(5\) ile \(11\)’dir. Yöntem uygun olmayan iki noktadan geçip önce \((2, 1)\) ucuna, sonra optimal \((4, 3)\) ucuna ulaştı.
\(\blacksquare\)
5.6 Uygun Çözümü Olmayan Problem
Şimdi Teorem 5.2 teoreminin öngördüğü durumu bir örnekte görelim.
Örnek 5.5 (Uygun çözümü olmayan bir maksimum problemi) Aşağıdaki problemi Büyük M yöntemiyle çözmeye çalışınız.
\[ \begin{aligned} x_1 + x_2 &\le 2 \\ 2x_1 + 3x_2 &\ge 12 \\ x_1, x_2 &\ge 0 \\ \max z &= 3x_1 + 2x_2 \end{aligned} \]
Çözüm
Standart form ve çözülebilir hal. Birinci kısıta \(x_3\) aylak değişkenini ekler, ikinci kısıttan \(x_4\) artık değişkenini çıkarırız. İkinci denklemin birim sütunu olmadığı için ona \(x_{u_1}\) yapay değişkenini ekleriz; maksimum problemi olduğundan katsayısı \(-M\)’dir:
\[ \begin{aligned} x_1 + x_2 + x_3 &= 2 \\ 2x_1 + 3x_2 - x_4 + x_{u_1} &= 12 \\ x_1, x_2, x_3, x_4, x_{u_1} &\ge 0 \\ \max z &= 3x_1 + 2x_2 + 0x_3 + 0x_4 - Mx_{u_1} \end{aligned} \]
Başlangıç bazı \(B_0 = (v_3, v_{u_1})\), \(\vec{c}_B = (0, -M)\)’dir.
Simpleks kriterleri.
\[ \begin{aligned} z_1 - c_1 &= (0 \cdot 1 - M \cdot 2) - 3 = -2M - 3, \\[1mm] z_2 - c_2 &= (0 \cdot 1 - M \cdot 3) - 2 = -3M - 2, \\[1mm] z_4 - c_4 &= (0 \cdot 0 - M \cdot (-1)) - 0 = M, \\[1mm] z_0 &= 0 \cdot 2 - M \cdot 12 = -12M. \end{aligned} \]
Maksimum probleminde en negatif kriter girer. \(M\)’nin katsayıları \(-3 < -2\) olduğundan en negatifi \(-3M - 2\)’dir ve \(v_2\) baza girer. Oranlar \(\tfrac{2}{1} = 2\) ve \(\tfrac{12}{3} = 4\)’tür; \(v_3\) bazdan çıkar ve pivot \(1\)’dir.
| \(c_j\) | \(3\) | \(2\) | \(0\) | \(0\) | \(-M\) | |||
|---|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_{u_1}\) | Oran |
| \(x_3\) | \(0\) | \(2\) | \(1\) | \([1]\) | \(1\) | \(0\) | \(0\) | \(\frac{2}{1} \Rightarrow\) |
| \(x_{u_1}\) | \(-M\) | \(12\) | \(2\) | \(3\) | \(0\) | \(-1\) | \(1\) | \(\frac{12}{3}\) |
| \(z_j - c_j\) | \(z_0 = -12M\) | \(-2M-3\) | \(-3M-2 \Uparrow\) | \(0\) | \(M\) | \(0\) |
Birinci iterasyon. Pivot \(1\) olduğundan \(x_3\) satırı aynen kalır ve \(x_2\) satırı olur: \((2 \mid 1,\ 1,\ 1,\ 0,\ 0)\). \(x_{u_1}\) satırından yeni pivot satırının \(3\) katı çıkarılır:
\[ \begin{aligned} &(12 - 6 \mid 2 - 3,\ 3 - 3,\ 0 - 3,\ -1 - 0,\ 1 - 0) \\[1mm] &\quad = (6 \mid -1,\ 0,\ -3,\ -1,\ 1). \end{aligned} \]
\(\vec{c}_B = (2, -M)\) ile:
\[ \begin{aligned} z_1 - c_1 &= 2 \cdot 1 - M \cdot (-1) - 3 = M - 1, \\[1mm] z_3 - c_3 &= 2 \cdot 1 - M \cdot (-3) - 0 = 3M + 2, \\[1mm] z_4 - c_4 &= 2 \cdot 0 - M \cdot (-1) - 0 = M, \\[1mm] z_0 &= 2 \cdot 2 - M \cdot 6 = -6M + 4. \end{aligned} \]
| \(c_j\) | \(3\) | \(2\) | \(0\) | \(0\) | \(-M\) | ||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_{u_1}\) |
| \(x_2\) | \(2\) | \(2\) | \(1\) | \(1\) | \(1\) | \(0\) | \(0\) |
| \(x_{u_1}\) | \(-M\) | \(6\) | \(-1\) | \(0\) | \(-3\) | \(-1\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = -6M+4\) | \(M-1\) | \(0\) | \(3M+2\) | \(M\) | \(0\) |
Kriterlerde \(M\)’nin katsayıları \(1\), \(3\), \(1\) pozitiftir; yeterince büyük \(M\) için bütün \(z_j - c_j \ge 0\)’dır ve tablo optimaldir. Ama bazda \(x_{u_1} = 6 > 0\) yapay değişkeni kaldı. Teorem 5.2 gereği problemin uygun çözümü yoktur; dolayısıyla optimal çözümden de söz edilemez.
Bunu doğrudan da görebiliriz. \(x_1, x_2 \ge 0\) iken birinci kısıttan
\[2x_1 + 3x_2 \le 3x_1 + 3x_2 = 3(x_1 + x_2) \le 3 \cdot 2 = 6\]
çıkar; oysa ikinci kısıt \(2x_1 + 3x_2 \ge 12\) istiyor. Tablonun gösterdiği \((x_1, x_2) = (0, 2)\) noktasında \(2x_1 + 3x_2 = 6\)’dır ve eksik kalan \(12 - 6 = 6\) birimi yapay değişken taşır. Yukarıdaki eşitsizlik bu eksiğin \(6\)’dan aşağı inemeyeceğini gösteriyor: yöntem, eksiği olabildiğince küçültüp durmuştur.
\(\blacksquare\)
Lineer programlama problemi bölümündeki diyet problemi (Örnek 1.2) de böyledir. Orada kolesterol sınırı yüzünden C vitamini gereksiniminin karşılanamayacağını elle göstermiştik. Büyük M yöntemi bunu kendiliğinden fark eder. A, C ve D vitamini kısıtları \(\ge\) biçiminde olduğu için bu üç denkleme birer yapay değişken eklenir; kolesterol kısıtının aylak değişkeni ise hazır bir birim sütun verir. Üç iterasyon sonunda ulaşılan optimal tabloda \(x_2 = \tfrac{8}{5}\) kg et bulunur ve A ile C vitamini satırlarının yapay değişkenleri \(x_{u_1} = \tfrac{67}{5}\) ve \(x_{u_2} = 14\) değerleriyle bazda kalır. Teorem 5.2 gereği diyetin uygun çözümü yoktur. Yapay değişkenler burada da eksik kalan vitamini ölçer: kolesterol sınırının izin verdiği \(1{,}6\) kg et \(1{,}6\) mg A ve \(16\) mg C vitamini verir; A vitamininden \(15 - 1{,}6 = 13{,}4\) mg, C vitamininden \(30 - 16 = 14\) mg eksik kalır.
5.7 Bazda Sıfır Değerli Yapay Değişken
Son olarak Önerme 5.3 önermesinin ikinci maddesini, yani gereksiz bir kısıt yüzünden yapay değişkenin bazda sıfır değerle kaldığı durumu görelim.
Örnek 5.6 (Gereksiz kısıtlı bir problem) Aşağıdaki problemi Büyük M yöntemiyle çözünüz.
\[ \begin{aligned} x_1 + x_2 &= 2 \\ 2x_1 + 2x_2 &= 4 \\ x_1, x_2 &\ge 0 \\ \min z &= x_1 + 2x_2 \end{aligned} \]
Çözüm
Çözülebilir hal. İki kısıt da eşitliktir ve sağ tarafları negatif değildir; problem standart formdadır. Hiçbir denklemde birim sütun olmadığı için ikisine de yapay değişken ekleriz; minimum problemi olduğundan katsayıları \(+M\)’dir:
\[ \begin{aligned} x_1 + x_2 + x_{u_1} &= 2 \\ 2x_1 + 2x_2 + x_{u_2} &= 4 \\ x_1, x_2, x_{u_1}, x_{u_2} &\ge 0 \\ \min z &= x_1 + 2x_2 + Mx_{u_1} + Mx_{u_2} \end{aligned} \]
Simpleks kriterleri. \(\vec{c}_B = (M, M)\) ile
\[ \begin{aligned} z_1 - c_1 &= (M \cdot 1 + M \cdot 2) - 1 = 3M - 1, \\[1mm] z_2 - c_2 &= (M \cdot 1 + M \cdot 2) - 2 = 3M - 2, \\[1mm] z_0 &= M \cdot 2 + M \cdot 4 = 6M. \end{aligned} \]
Minimum probleminde en büyük pozitif kriter girer. İki kriterde de \(M\)’nin katsayısı \(3\)’tür; sabit terimlerde \(-1 > -2\) olduğundan \(3M - 1\) daha büyüktür ve \(v_1\) baza girer. Oranlar \(\tfrac{2}{1} = 2\) ve \(\tfrac{4}{2} = 2\) eşittir. Eşitlik durumunda iki satırdan biri seçilebilir; birinci satırı seçelim. \(v_{u_1}\) bazdan çıkar ve pivot \(1\)’dir.
| \(c_j\) | \(1\) | \(2\) | \(M\) | \(M\) | |||
|---|---|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_{u_1}\) | \(v_{u_2}\) | Oran |
| \(x_{u_1}\) | \(M\) | \(2\) | \([1]\) | \(1\) | \(1\) | \(0\) | \(\frac{2}{1} \Rightarrow\) |
| \(x_{u_2}\) | \(M\) | \(4\) | \(2\) | \(2\) | \(0\) | \(1\) | \(\frac{4}{2}\) |
| \(z_j - c_j\) | \(z_0 = 6M\) | \(3M-1 \Uparrow\) | \(3M-2\) | \(0\) | \(0\) |
Birinci iterasyon. Pivot \(1\) olduğundan \(x_{u_1}\) satırı aynen kalır ve \(x_1\) satırı olur: \((2 \mid 1,\ 1,\ 0)\); son eleman \(v_{u_2}\) sütunundadır. \(x_{u_2}\) satırından yeni pivot satırının \(2\) katı çıkarılır:
\[(4 - 4 \mid 2 - 2,\ 2 - 2,\ 1 - 0) = (0 \mid 0,\ 0,\ 1).\]
\(v_{u_1}\) sütunu atılır. \(\vec{c}_B = (1, M)\) ile
\[ \begin{aligned} z_2 - c_2 &= 1 \cdot 1 + M \cdot 0 - 2 = -1, \\[1mm] z_0 &= 1 \cdot 2 + M \cdot 0 = 2. \end{aligned} \]
| \(c_j\) | \(1\) | \(2\) | \(M\) | ||
|---|---|---|---|---|---|
| \(x_B\) | \(c_B\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_{u_2}\) |
| \(x_1\) | \(1\) | \(2\) | \(1\) | \(1\) | \(0\) |
| \(x_{u_2}\) | \(M\) | \(0\) | \(0\) | \(0\) | \(1\) |
| \(z_j - c_j\) | \(z_0 = 2\) | \(0\) | \(-1\) | \(0\) |
Bütün \(z_j - c_j \le 0\) olduğundan tablo optimaldir. Bazda \(x_{u_2}\) yapay değişkeni kaldı, ama değeri \(0\)’dır. Teorem 5.1 gereği optimal çözüm \(x_1 = 2\), \(x_2 = 0\) ve \(\min z = 2\)’dir.
\(x_{u_2}\) satırının yapay olmayan \(v_1\) ve \(v_2\) sütunlarındaki elemanları sıfırdır; Önerme 5.3 önermesinin ikinci maddesi gereği kısıtlardan biri gereksizdir. Gerçekten ikinci kısıt birincinin \(2\) katıdır: \(2(x_1 + x_2) = 2 \cdot 2\). Önermenin ispatındaki katsayılar da görünür: tablonun \(x_{u_2}\) satırı, başlangıç tablosunun ikinci satırından birinci satırın \(2\) katı çıkarılarak elde edildi, yani \(w_1 = -2\), \(w_2 = 1\)’dir. \(x_{u_2}\) satırı yapay değişkenler sıfırken \(0 = 0\) der ve silinebilir; geriye tek denklemli \(x_1 + x_2 = 2\) problemi kalır.
Sonucu doğrudan da sağlayabiliriz: \(x_1 + x_2 = 2\) üzerinde \(z = x_1 + 2x_2 = 2 + x_2 \ge 2\)’dir ve eşitlik yalnız \(x_2 = 0\) için sağlanır. Oran testinde ikinci satırı seçseydik bu kez \(x_{u_1}\) bazda \(0\) değeriyle kalırdı; sonuç değişmezdi.
\(\blacksquare\)
Bu bölümde Büyük M yöntemiyle, standart formu birim matris içermeyen problemleri simpleks tablosunda çözmeyi öğrendik. Yöntem yapay değişkenleri büyük bir cezayla bazdan çıkarır; optimal tabloda yapay değişken kalıp kalmadığına bakarak da problemin uygun çözümü olup olmadığını söyler. Yöntemin bir zorluğu, her kriteri \(aM + b\) biçiminde iki parçalı taşımaktır; \(M\) için büyük bir sayı seçip hesabı sayısal yapmak ise yuvarlama hatalarına yol açabilir. Bir sonraki bölümde, İki faz yöntemi bölümünde, aynı işi \(M\) kullanmadan iki ayrı aşamada yapmayı göreceğiz: önce yalnız yapay değişkenlerin toplamı sıfıra indirilir, sonra orijinal amaç fonksiyonuyla devam edilir.