Doğrusal programlama: model kurma, uygun bölge ve köşe noktası
İstatistik · Yöneylem Araştırması · Okuma 5 dk · 2 etkinlik
Önce hatırlaBasit doğrusal regresyonda en küçük kareler yöntemiyle eğim ve sabit terim nasıl hesaplanır?Bağlantılı konudan (Korelasyon ve regresyon). Önce kendin cevapla, sonra aç.
Basit doğrusal regresyon modeli Y = β₀ + β₁X + ε'dir. En küçük kareler (EKK) yöntemi, artıkların kareleri toplamını en küçük yapan doğruyu seçer: b₁ = Sxy/Sxx, b₀ = ȳ − b₁x̄. Bu doğru her zaman (x̄, ȳ) noktasından geçer ve artıkların toplamı sıfırdır. Eğim korelasyona bağlıdır: b₁ = r · sy/sx.
Basit doğrusal regresyon ve EKK
✎Konu anlatımı
Doğrusal programlama modeli nasıl kurulur, grafik çözümde en iyi nokta nasıl bulunur, sınırsız ve uygun çözümsüz durumlar nasıl anlaşılır?
Kısa cevap: Doğrusal programlama (DP), doğrusal bir amaç fonksiyonunu doğrusal kısıtlar ve negatif olmama koşulu altında en büyükler ya da en küçükler. Model üç parçadır: karar değişkenleri, amaç, kısıtlar. Kısıtların ortak bölgesi uygun bölgedir; en iyi çözüm varsa bir köşe noktasındadır. Özel durumlar: uygun çözümün olmaması, sınırsız çözüm, alternatif optimum ve gereksiz kısıt.Bir belediye şirketinin mobilya atölyesi masa ve dolap üretiyor. Montaj ve boya bölümlerinin haftalık saatleri sınırlı; hangi üretim bileşimi kârı en büyük yapar?
Korelasyon ve regresyon sayfasında gördüğümüz EKK de bir en iyileme problemiydi, ama kısıtsızdı. Yöneylem araştırmasında en iyi karar sınırlı kaynaklar içinde aranır. Model kurarken önce karar değişkenleri (x = haftalık masa, y = haftalık dolap), sonra amaç (kâr ya da maliyet), en son kısıtlar (saat, hammadde, talep) yazılır. Modelin doğrusal olması dört varsayıma dayanır: oransallık (iki masa iki kat saat ister), toplanabilirlik, bölünebilirlik (2,5 masa anlamlı sayılır) ve katsayıların kesin bilinmesi.
İki değişkenli modelde her kısıt düzlemi ikiye böler; bütün kısıtları sağlayan noktalar uygun bölgedir ve dışbükey bir bölgedir (sınırlıysa dışbükey bir çokgen). Köşe noktası teoremine göre doğrusal amacın en iyi değeri, varsa, bu bölgenin köşelerinden birinde alınır. Bu yüzden köşeler bulunur ve Z her birinde hesaplanır; ya da eş kâr doğrusu (3x + 5y = sabit) uygun bölgeden çıkmadan en uzağa kaydırılır.
Yukarıdaki modelin en iyi çözümünü bulun.
- Eksen köşeleri: (0, 0), boya kısıtından (6, 0), montaj kısıtından (0, 7). (14, 0) ve (0, 9) öbür kısıtı bozduğu için uygun değildir.
- İki kısıtın kesişimi: (3x + 2y) − (x + 2y) = 18 − 14 ⇒ x = 2, y = 6.
- Z: (0, 0) 0; (6, 0) 18; (0, 7) 35; (2, 6): 6 + 30 = 36.
Cevap: haftada 2 masa ve 6 dolap; kâr 36 bin TL. İki kısıt da bu noktada tam dolar (bağlayıcıdır).
| Durum | Grafikteki belirti |
|---|---|
| Uygun çözüm yok | kısıtların ortak bölgesi boş (ör. x + y ≤ 4 ve x + y ≥ 6) |
| Sınırsız çözüm | bölge amacın iyileştiği yönde açık; en büyüklemede Z sonsuza gider |
| Alternatif optimum | eş amaç doğrusu bağlayıcı bir kısıta paralel; iki köşe ve aradaki kenar en iyi |
| Gereksiz kısıt | kaldırılınca uygun bölge değişmez |
Nasıl sorulurKısa bir üretim ya da karışım problemi verilip model kurdurulur ya da köşelerden en iyi Z sorulur; grafikteki özel durum adlandırılır.
TuzakEksen kesim noktalarını öbür kısıtı sağlayıp sağlamadığına bakmadan değerlendirmek, iki kısıtın kesişim köşesini atlamak ve açık bölgeyi her zaman sınırsız çözüm sanmaktır (en küçüklemede açık bölgede de optimum olabilir).
?Soru çöz
maks Z = 4x + 3y; x + y ≤ 8, 2x + y ≤ 12, x, y ≥ 0 doğrusal programlama probleminin en iyi amaç değeri kaçtır?