Simpleks YöntemDoğrusal programlama problemlerinin en iyi (optimal) çözümünü aramak için komşu temel uygun çözümler üzerinden yinelemeli (iteratif) olarak ilerleyen cebirsel bir çözüm algoritmasıdır. Yöntem, bir uç noktadan başlayıp amaç fonksiyonunu iyileştiren komşu uç noktaya geçerek optimal çözüme ulaşır.
Temel DeğişkenBir kanonik denklem sisteminde sadece tek bir denklemde katsayısı +1, amaç fonksiyonu dahil diğer tüm denklemlerde katsayısı 0 olan değişkendir. Temel değişkenlerin değerleri, bulundukları satırın sağ taraf sabitine eşittir.
Temel Dışı DeğişkenKanonik denklem sisteminde temel değişken olarak seçilmeyen ve çözüme başlarken değeri sıfıra (0) eşitlenen karar veya aylak değişkendir. İterasyonlar sırasında temele girerek pozitif değer alabilirler.
Kanonik ŞekilBir DP probleminin tüm fonksiyonel kısıtlarının eşitlik biçiminde olduğu ve her kısıtta isolated (izole edilmiş) bir temel değişkenin yer aldığı denklem formudur. Ayrıca temel değişkenlerin amaç fonksiyonundaki katsayıları da sıfırlanmış durumdadır.
Pivot İşlemiTemele girmesi seçilen bir değişkenin katsayısını pivot satırda +1 yapma, amaç satırı dahil diğer tüm satırlarda ise sıfıra eşitleme işlemidir. Bu işlem Gauss-Jordan satır operasyonları ile gerçekleştirilir.
Pivot SatırTemele girmesi kararlaştırılan değişkenin en küçük oran testini sağladığı kısıt satırıdır. Bu satırdaki temel değişken, temelden çıkarak yerini yeni temele giren değişkene bırakır.
En Küçük Oranlar YöntemiTemele girecek değişken belirlendikten sonra, kısıtlardaki sağ taraf sabitlerinin temele girecek değişkenin pozitif katsayılarına bölünmesiyle en küçük pozitif oranın arandığı yöntemdir. Negatif olmama kısıtlarının korunmasını ve temelden çıkacak değişkenin doğru seçilmesini sağlar.
Cebirsel En İyilik KriteriKanonik formdaki bir en büyükleme probleminde, amaç fonksiyonu satırındaki tüm temel dışı değişkenlerin katsayılarının negatif veya sıfır ($\le 0$) olması durumudur. Bu kural sağlandığında mevcut temel uygun çözümün optimal olduğu ilan edilir.
Dejenere ÇözümPivot satırındaki sağ taraf sabiti sıfır olduğunda ortaya çıkan ve temele yeni bir değişken girmesine rağmen amacın değerinin değişmediği temel uygun çözümdür. Temeldeki değişkenlerden en az birinin değeri sıfıra eşittir.
Alternatif ÇözümOptimal çözüme ulaşıldığında, amaç fonksiyonu satırında katsayısı sıfır olan temel dışı bir değişkenin bulunmasıyla ortaya çıkan durumdur. Bu değişken temele alındığında amaç fonksiyonu değeri değişmeden ikinci bir optimal temel uygun çözüm türetilir.
Uç-Nokta Uygun (UNU) ÇözümDoğrusal programlama probleminin uygun çözüm alanının sınır doğrularının/hiper-düzlemlerinin kesişmesiyle oluşan ve tüm kısıtları sağlayan köşe noktalarıdır. DP problemlerinin optimal çözümü her zaman bir UNU noktasındadır.
Komşu Uç Noktalarn karar değişkenli bir DP probleminde n - 1 adet sınır doğrusunu/düzlemini ortak olarak sağlayan iki uç noktaya verilen addır. İki komşu uç nokta bir kenar ile birbirine bağlıdır.
Uygun Çözüm Alanının Kenarıİki komşu uç-nokta uygun çözümü birbirine bağlayan ve uygun çözüm alanının sınırını oluşturan doğru parçasıdır. Simpleks algoritması bir uç noktadan diğerine bu kenarlar boyunca hareket eder.
Geometrik En İyilik KriteriBir uç-nokta uygun çözümün, kendisine komşu olan tüm uç-nokta uygun çözümlerden amaç fonksiyonuna daha büyük (veya eşit) bir değer sağlaması durumudur. Bu kriter sağlandığında tüm alanı taramadan o noktanın en iyi çözüm olduğu anlaşılır.
Aylak DeğişkenKüçük veya eşit ($\le$) şeklindeki fonksiyonel kısıtları eşitlik (=) haline getirmek amacıyla denklemlerin sol tarafına eklenen ve kullanılmayan kaynak miktarını temsil eden negatif olmayan ($s_i \ge 0$) ek değişkendir.
Genişletilmiş ProblemEşitsizlik kısıtlarına aylak veya yapay değişkenler eklenerek kanonik eşitlik formuna dönüştürülmüş ve orijinal problem ile tamamen aynı uygun çözüm alanını tarif eden denklem sistemidir.
Temel Uygun Çözüm (TU)Kanonik bir denklem sisteminde temel dışı değişkenler 0 yapılarak elde edilen ve tüm temel değişkenlerin negatif olmama kısıtını ($x_j \ge 0$) sağladığı çözümdür. Geometrikteki UNU çözümlere tam olarak karşılık gelir.
Komşu Temel Uygun ÇözümlerAralarındaki tek fark sadece bir temel değişkenin yer değiştirmesi (birinin temele girip diğerinin temelden çıkması) olan iki temel uygun çözümdür. Geometrik komşu uç noktalara denk gelirler.
Gauss-Jordan YöntemiBir doğrusal denklem sisteminde bir satırı belirli bir katsayı ile çarparak diğer satırlara ekleme veya çıkarma yoluyla bir değişkeni izole etmeye ve katsayılarını sıfırlamaya yarayan lineer cebir yöntemidir.
Simpleks Tablo ŞekliCebirsel simpleks algoritmasının denklem metinleri yazılmaksızın sadece katsayı matrisleri, sağ taraf sabitleri ve temel değişken isimleriyle temsil edildiği pratik matris düzenidir.
İterasyon (Yineleme)Simpleks algoritmasında mevcut temel uygun çözümden en iyilik testi ve pivot işlemleri uygulanarak bir sonraki daha iyi temel uygun çözüme geçilmesi sürecindeki tekrarlanan adımların her biridir.
Pivot SütunTemele girmesi kararlaştırılan karar değişkenine ait katsayıların bulunduğu sütundur. En büyükleme problemlerinde amaç satırında en büyük pozitif katsayıya sahip değişkenin sütunudur.
Standart ŞekilAmaç fonksiyonu en büyükleme (Enb), tüm fonksiyonel kısıtları küçük-eşit ($\le$) ve tüm karar değişkenleri negatif olmayan ($\ge 0$) doğrusal programlama problemi biçimidir.
Sınırsız Amaç FonksiyonuTemele girmesi gereken pozitif katsayılı bir değişkenin yer aldığı sütunda hiç pozitif katsayı bulunmaması ($a_{ij} \le 0$) durumu sonucu amaç fonksiyonunun sonsuza gitmesi durumudur.
