Doğrusal Programlama — Simpleks Yöntemi ve Grafiksel Çözüm

Doğrusal programlama, maksimum kâr veya minimum maliyet gibi doğrusal bir amaç fonksiyonunun en iyi değerini, doğrusal kısıtlar altında bulma yöntemidir. İki değişkenli bir problemde grafiksel çözüm, uygun bölgeyi bulur ve köşe noktalarını kontrol eder. Daha büyük problemlerde ise simpleks yöntemi aynı köşe noktası fikrini cebirsel olarak kullanır.

Doğrusal programlamayı yalnızca amaç fonksiyonu ve kısıtlar doğrusal olduğunda kullanın. İlişki bükülüyorsa, eğriyse veya $xy$ gibi çarpımlara bağlıysa, model doğrusal programlama modeli değildir.

Doğrusal Programlama Tanımı

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

şu tür kısıtlar altında:

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

ve benzer doğrusal eşitsizliklerle birlikte, negatif değerlerin anlamlı olmadığı durumlarda $x_i \ge 0$ gibi koşullar da eklenir.

Her kısıtı sağlayan tüm noktaların kümesine uygun bölge denir. Doğrusal programlama şu soruyu sorar: Bu uygun noktalar arasında amaç fonksiyonuna en iyi değeri veren hangisidir?

Grafiksel Yöntem Nasıl Çalışır?

Yalnızca iki karar değişkeni varsa, her kısıtı $xy$-düzleminde çizebilirsiniz. İzin verilen tüm bölgelerin kesişimi uygun bölgedir.

Bu bölgedeki her nokta geçerli bir çözümdür. Amaç fonksiyonu her birine bir değer atar.

Doğrusal programlamada temel gerçeklerden biri şudur: Eğer optimal bir çözüm varsa, en az bir optimal çözüm uygun bölgenin bir köşe noktasında gerçekleşir. Bu yüzden grafiksel yöntem, taralı bölgedeki her noktayı kontrol etmek yerine köşe noktalarına odaklanır.

Çözümlü Örnek: Bir Doğrusal Programlama Problemini Grafiksel Olarak Çözme

Bir atölyenin iki ürün ürettiğini düşünelim: $A$ ve $B$.

• $A$ ürününün birim başına kârı: $3$
• $B$ ürününün birim başına kârı: $5$
• Makine süresi sınırı: $A$'nın her birimi $1$ saat, $B$'nin her birimi $2$ saat kullanıyor ve en fazla $8$ saat var
• Montaj sınırı: $A$'nın her birimi $1$ saat, $B$'nin her birimi $1$ saat kullanıyor ve en fazla $5$ saat var

$A$ ürününün miktarı $x$, $B$ ürününün miktarı $y$ olsun.

Maksimize edin:

$$P = 3x + 5y$$

şu kısıtlar altında:

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Köşe noktalarını bulun

Eksenlerden ve kısıt doğrularından, uygun köşe noktaları şunlardır:

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

$(2,3)$ noktası, sınır denklemlerini çözerek elde edilir:

$$x + 2y = 8,\quad x + y = 5$$

Taraf tarafa çıkarınca $y = 3$ bulunur, ardından $x = 2$ olur.

Her köşede amaç fonksiyonunu test edin

Her köşe noktasındaki kârı hesaplayın:

• $(0,0)$ noktasında, $P = 0$
• $(5,0)$ noktasında, $P = 15$
• $(0,4)$ noktasında, $P = 20$
• $(2,3)$ noktasında, $P = 21$

Dolayısıyla maksimum kâr

$$P = 21$$

değeridir ve şu noktada elde edilir:

$$(x,y) = (2,3)$$

Grafiksel yöntemi tek cümlede şöyle özetleyebiliriz: uygun bölgeyi çiz, köşe noktalarını bul ve amaç fonksiyonunu bu noktalarda hesapla.

Simpleks Yönteminin Sezgisi

Grafiksel yöntem yalnızca iki değişken olduğunda pratiktir; bazen üç değişken için de, 3B bir bölgeyi hayal etmeye razıysanız kullanılabilir. Gerçek optimizasyon problemlerinde ise çoğu zaman çok sayıda değişken vardır, bu yüzden uygun bölgeyi çizmek artık gerçekçi değildir.

Simpleks yöntemi aynı köşe noktası mantığını korur, ama bunu cebirsel olarak yapar. Genel olarak, amaç fonksiyonunu iyileştiren bir uygun köşe noktasından diğerine geçer ve komşu bir hareket daha iyi bir değer vermediğinde durur.

Bu yüzden iyi bir zihinsel model şudur:

• Grafiksel yöntem: köşe noktalarını görürsünüz
• Simpleks yöntemi: onları çizmeden köşe noktaları arasında ilerlersiniz

Bu açıklama sezgiyi verir, tam algoritmayı değil. Gerçek simpleks prosedürü, her adımda hangi değişkenin gireceğine ve hangisinin çıkacağına karar vermek için bir tablo veya eşdeğer bir cebirsel biçim kullanır.

Köşe Noktaları Neden Önemlidir?

Doğrusal amaç fonksiyonları şu tür seviye doğruları oluşturur:

$$3x + 5y = k$$

burada $k$ farklı değerler alabilir. Bu doğruyu daha yüksek kâr yönünde kaydırdığınızda, uygun bölgeye hâlâ değdiği son nokta maksimumun gerçekleştiği yerdir.

Birçok şekilde bu son temas tek bir köşe noktasında olur. Eğer amaç doğrusu bir sınır kenarına paralelse, o kenar üzerindeki birden fazla nokta optimal olabilir. Bu durumda bile en az bir optimal köşe noktası vardır.

Yaygın Hatalar

Uygun ile optimali karıştırmak

Bir nokta tüm kısıtları sağlayabilir ama yine de amaç fonksiyonunu maksimize veya minimize etmeyebilir. Uygun olmak yalnızca izin verildiği anlamına gelir.

Negatif olmama koşullarını unutmak

Eğer $x$ ve $y$ ürettiğiniz veya taşıdığınız miktarları temsil ediyorsa, negatif değerler genellikle anlamlı değildir. $x \ge 0$ veya $y \ge 0$ koşullarını dışarıda bırakmak problemi değiştirebilir.

Her cevabın tam sayı olması gerektiğini sanmak

Temel doğrusal programlama kesirli değerlere izin verir. Eğer değişkenlerin kamyon sayısı veya işçi sayısı gibi tam sayı olması gerekiyorsa, tamsayılı programlama modeli ya da ek bir tamsayılılık koşulu gerekir.

Her problemin en iyi bir cevabı olduğunu sanmak

Bazı doğrusal programlama problemleri uygunsuzdur; yani hiçbir nokta tüm kısıtları sağlamaz. Bazıları ise sınırsızdır; yani amaç fonksiyonu sınırsız biçimde iyileştirilebilir. Sonlu bir optimum ancak kısıtlar problemi gerçekten yeterince sınırlıyorsa elde edilir.

Çok fazla değişken varken grafiksel yöntemi kullanmak

Değişken sayısı arttığında grafik çizmek artık doğru araç değildir. İşte bu noktada simpleks veya diğer optimizasyon yöntemleri gerekli hale gelir.

Doğrusal Programlama Ne Zaman Kullanılır?

Doğrusal programlama, kararların sınırlı kaynaklar için yarıştığı ve hem amaç hem de sınırların doğrusal olarak modellenebildiği durumlarda kullanılır. Tipik örnekler arasında üretim planlama, taşımacılık, personel planlama, karışım problemleri, çizelgeleme ve bütçe dağıtımı yer alır.

Model, varsayımları kadar iyidir. Gerçek ilişki doğrusal olmaya yakın değilse veya değişkenlerin tam sayı olması gerekiyorsa, temel bir doğrusal programlama modeli yalnızca bir başlangıç noktası olabilir.

Benzer Bir Problem Deneyin

İki ürün, iki kaynak sınırı ve bir kâr fonksiyonu içeren küçük bir sözel problem alın. Değişkenleri yazın, kısıtları grafikte gösterin ve köşe noktalarını kendiniz test edin. Bu fikir oturduğunda, simpleks yöntemini anlamak çok daha kolay olur; çünkü aynı mantığı daha yüksek boyutlara genişletir.