← Ünite 7
Yöneylem Araştırması

Ünite 7: Tamsayılı Programlama Modelleri

Hedef Programlamanın Doğuşu
Hedef programlama yaklaşımı, 1961 yılında Abraham Charnes ve William Cooper tarafından literatüre kazandırılmıştır. Bu yöntem, geleneksel doğrusal programlamanın katı kısıtlarını esneterek daha gerçekçi çözümler sunar.
Ahmet'in Araba Seçimi Örneği
Ahmet, 5 farklı araba (A1-A5) arasından fiyat ve yakıt tüketimi kriterlerine göre seçim yapmaya çalışmaktadır. Bu örnek, çelişen amaçların birbiriyle nasıl ödünleştiğini gösteren klasik bir çok amaçlı karar verme senaryosudur.
Kamyon Şirketi ve Mandıracı
Mandıracı, 3 farklı dükkâna ürün göndermek için K1 ve K2 tipi kamyonlar kullanmaktadır. 6000 TL bütçe kısıtı altında, dükkânlara gönderilecek ürün miktarlarını maksimize etmeye çalışması çok amaçlı doğrusal programlamaya örnektir.
Tercih Katsayılarının Etkisi
w1=3, w2=2, w3=1 ağırlık katsayıları kullanıldığında Mandıracı için 1. dükkân en önemliyken, katsayılar w1=1, w2=3, w3=5 olduğunda 3. dükkânın önemi artmış ve çözüm kümesi tamamen değişmiştir.

Anahtar Kavramlar

Çok Amaçlı Karar VermeBirden fazla çelişen amaç fonksiyonunun aynı anda en iyilenmesi gereken karar problemidir. Örneğin, bir yatırımda hem kârın maksimize edilmesi hem de riskin minimize edilmesi.
Baskın ÇözümBir çözümün tüm amaç fonksiyonlarındaki değerlerinin, başka bir çözümün değerlerinden daha iyi olması durumudur. Eğer A çözümü B çözümüne baskınsa, A her açıdan B'den daha iyidir.
Etkin ÇözümUygun çözüm alanında kendisine baskın olan başka bir çözümün bulunmadığı noktadır. Bu noktada bir amacı iyileştirmek için diğerinden ödün vermek gerekir.
Pareto-Maksimal NoktaEtkin bir çözüme karşı gelen amaç fonksiyonu değerlerinden oluşan vektördür. Bu noktalar, tüm amaçların aynı anda iyileştirilemeyeceği sınır değerleri temsil eder.
SkalerleştirmeÇok amaçlı bir problemin, ağırlık katsayıları kullanılarak tek amaçlı bir probleme indirgenmesi işlemidir. Böylece standart optimizasyon yöntemleri kullanılabilir.
Ağırlıklandırılmış Toplam YöntemiAmaç fonksiyonlarının önem derecelerini yansıtan ağırlık katsayıları ile çarpılıp toplanmasıyla tek bir amaç fonksiyonu oluşturma yöntemidir.
Ödünleşim YaklaşımıKarar vericinin amaçlar arasında tercih yaparak, bazı amaçlara alt/üst sınırlar koyup bunları kısıt kümesine eklemesi ve geriye kalan amaçları en iyilemesi yöntemidir.
Hedef ProgramlamaAmaçların tam olarak gerçekleşemeyeceği durumlarda, hedeflenen değerlerden sapmaları en küçüklemeyi amaçlayan bir yöneylem araştırması tekniğidir.
Hedef Değer (hi)Karar vericinin her bir amaç fonksiyonu için ulaşmak istediği ideal başarı seviyesidir. Örneğin, günlük 50 ton ürün taşıma hedefi.
Pozitif Sapma (si+)Hedeflenen değerin üzerine çıkılan miktarı gösterir. Örneğin, 50 ton hedeflenmişken 55 ton üretilmesi durumunda 5 tonluk pozitif sapma vardır.
Negatif Sapma (si-)Hedeflenen değerin altına düşülen miktarı gösterir. Örneğin, 50 ton hedeflenmişken 45 ton üretilmesi durumunda 5 tonluk negatif sapma vardır.
DoğrusallaştırmaHedef programlamada mutlak değerli amaç fonksiyonlarını, sapma değişkenleri (si+, si-) kullanarak doğrusal bir forma dönüştürme işlemidir.
Çelişen AmaçlarBirinin iyileştirilmesinin diğerinin kötüleşmesine yol açtığı amaçlardır. Örneğin, hızın artmasıyla yakıt tüketiminin artması.
Karar KuralıÇok amaçlı problemlerde en büyükleme, en küçükleme veya ödünleşim gibi yöntemleri kapsayan genel bir terimdir.
Etkin DeğerBir etkin çözüme karşı gelen amaç fonksiyonu değerlerinden oluşan vektördür. Sistemin ulaşılabilecek en iyi performans noktalarını gösterir.
Tercih Katsayısı (wi)Karar vericinin her bir amaç fonksiyonuna verdiği önem derecesidir. Katsayı ne kadar büyükse o amaç o kadar önemlidir.
Bütçe KısıtıKaynakların sınırlı olması nedeniyle, hedeflere ulaşırken aşılmaması gereken parasal veya fiziksel sınırdır.
Grafik Yöntemİki karar değişkenli problemlerde, uygun çözüm alanını ve amaç fonksiyonunu çizerek en iyi çözümün görsel olarak bulunmasıdır.
Simpleks YöntemiDoğrusal programlama problemlerini çözmek için kullanılan, köşe noktaları üzerinden ilerleyen cebirsel bir algoritmadır.
Ulaşılamaz HedefUygun çözüm alanı içinde tam olarak gerçekleşmesi mümkün olmayan başarı seviyesidir. Hedef programlama burada devreye girer.
Sistem VerimliliğiKaynakların en iyi şekilde kullanılarak amaçlara en yakın değerlerin elde edilmesidir.
Karar DeğişkeniProblemin çözümünde kontrol edebildiğimiz, değerini belirlememiz gereken değişkenlerdir (örneğin kamyon sayısı).
Kısıt KümesiKarar değişkenlerinin uyması gereken matematiksel sınırların (eşitlik/eşitsizlik) oluşturduğu bölgedir.
Sapma DeğişkeniHedef programlamada hedeften ne kadar uzaklaşıldığını ölçmek için kullanılan yardımcı değişkenlerdir.
OptimizasyonBelirli kısıtlar altında amaç fonksiyonunu en iyi (en büyük veya en küçük) yapan değerleri bulma sürecidir.

Diğer Önemli Bilgiler

Pareto-Maksimal Noktaların Doğası

Çok amaçlı problemlerde [42, 60, 30] ve [30, 50, 40] gibi iki farklı çözüm vektörü karşılaştırıldığında, hiçbirinin diğerine baskın olmadığı görülür. Bu durum, her iki çözümün de etkin olduğunu kanıtlar.

Ödünleşim Senaryosu

Mandıracı, 7200 TL bütçe ile 1. dükkâna en az 44 ton, 3. dükkâna en az 52 ton ürün gönderme şartı koymuştur. Bu kısıtlar, çok amaçlı problemi tek amaçlı bir ödünleşim problemine dönüştürmüştür.

Hava Yolu Şirketi Örneği

Bir hava yolu şirketi, koltuk sayısını artırarak kârı maksimize etmeye çalışırken konforun düşmesiyle müşteri kaybetmiştir. Şirket, kâr ve konfor arasında bir denge kurmak için yatırım-kar ödünleşimi yapmıştır.

Skalerleştirme İşlemi

Çok amaçlı bir problemi, ağırlıklandırılmış toplam yöntemi ile tek bir amaç fonksiyonuna indirgeme işlemidir. Bu yöntem, karmaşık vektörel problemleri basit doğrusal programlama problemlerine dönüştürür.

Sapma Değişkenlerinin Tanımı

Hedef programlamada si+ ve si- değişkenleri, hedeften sapmaları ölçer. Bu değişkenlerin toplamının en küçüklenmesi, hedefe en yakın çözümü bulmayı sağlar.

Doğrusallaştırma Tekniği

Hedef programlamadaki mutlak değerli |fi(x) - hi| ifadesi, si+ ve si- değişkenleri kullanılarak doğrusal bir forma getirilir. Bu, problemin Simpleks gibi algoritmalarla çözülmesine olanak tanır.

Baskın Çözümün Yokluğu

Çok amaçlı problemlerde, bir çözümün diğerine baskın olmaması, karar vericinin kendi tercihlerini (ağırlıklarını) devreye sokması gerektiğini gösterir.

Kamyon Kapasiteleri ve Maliyet

K1 tipi kamyonun günlük kira maliyeti 1000 TL iken, K2 tipi kamyonun maliyeti 800 TL'dir. Bu maliyet farkı, bütçe kısıtı altında hangi kamyondan kaç adet kullanılacağını belirleyen temel değişkendir.

Etkin Çözüm vs En İyi Çözüm

Çok amaçlı problemlerde 'en iyi çözüm' yoktur; sadece 'etkin çözüm' vardır. Çünkü tüm amaçları aynı anda mükemmel kılan tek bir nokta nadiren mevcuttur.

Matematiksel Programlamanın Temeli

Yöneylem araştırması, kısıtlı kaynakların belirlenen amaçlara en verimli şekilde ulaşılması için bilimsel eylemlerin araştırılmasıdır.

Grafik Çözümün Sınırları

Grafik çözüm yöntemi, sadece 2 karar değişkenli problemlerde kullanılabilir. Değişken sayısı arttıkça Simpleks gibi cebirsel yöntemlere geçiş zorunludur.

Sınavda Dikkat Et

  • Etkin çözüm ile baskın çözüm arasındaki farkı iyi kavrayın; baskın çözüm her zaman daha iyiyken, etkin çözümde birinden ödün vermeden diğerini iyileştiremezsiniz.
  • Ağırlık katsayılarının (wi) toplamının değil, her bir amaç için belirlenen önem derecesinin sonucu nasıl değiştirdiğine dikkat edin; katsayı artarsa o amacın değeri genellikle iyileşir.
  • Hedef programlamada sapma değişkenlerinin (si+, si-) mutlak değerin yerini aldığını unutmayın; amaç fonksiyonunda bu değişkenlerin katsayıları (önem dereceleri) ile çarpılması gerekir.
  • Çok amaçlı problemlerde 'en iyi çözüm' ifadesi yerine 'etkin çözüm' ifadesinin kullanıldığını sınavda karıştırmayın.
  • Ödünleşim yaklaşımında, bir amacın kısıt olarak eklenmesi durumunda problemin tek amaçlı bir doğrusal programlama problemine dönüştüğünü hatırlayın.
  • Sapma değişkenlerinin her zaman negatif olmayan değerler aldığını ve hedef programlamada amaç fonksiyonunun bu sapmaları minimize ettiğini unutmayın.