lagrangean relaxation ^*

• lineer programlamada çözülmesi çok zor ^* tamsayılı^* veya karışık tamsayılı^* problemleri çözebilmek için kullanılan sezgisel^* bir yöntemdir. mantığı problemi zorlaştıran kısıtların^* dualize edilip bir penaltı değeri (ki buna lagrange multiplier denir) ile amaç fonksiyonuna^* eklenmesidir. bu şekilde problem çözülmesi ve genellikle parçalanması kolay alt problemlere bölünür ve kolaylıkla çözülür.
  
  fakat bu yöntemin zor olan kısmı problemin gevşetilmesi^* sonucunda elde edilen amaç fonksiyonu turevlendirilemez^* bir halde olduğu için bu penalty değerlerini "dene ve yanıl"a benzer bir şekilde bulmamız gerekmektedir. deneme yanılmada kullanacağımız değerleri oluşturmak için subgradient algoritması, adjusted multiplier algoritması gibi harici bir algortima kullanılmaktadır.
  
  lagrangian relaxation sonucunda bulduğumuz sonuçlar bazı kısıtlar problem çözülmeden önce gevşetildiği için çoğu zaman orjinal problem için feasible sonuç olmaz bu sonuçlar sadece bizim problemimiz için bir alt sınır^* oluştururlar. bu altsınırı yine bulduğumuz bir üst sınır^* ile birleştirdiğimizde optimal sonucun içinde olduğu bir aralık^* ve bilinmeyen değişkenlerimiz için feasible değerler bulmuş oluruz. verimli gevşetimler, lagrange multiplier algoritmaları ve etkili bir upperbound algoritması ile genellikle bu aralık %0.1'den daha küçüktür. yani optimal değere çok yakındır.
  
  upperbound u bulmak için kesin sonuç veren^* branch and bound, branch and price gibi algoritmaların yanında bir çok sezgisel method^* de bulunur. eğer lagrange relaxation bu tip bir sezgiselle birleştirilse ortaya çıkan algoritmaya lagrangian heuristic denir.
  
  bi de avrupalılar bu tekniğe lagrangian relaxation da diyebilir. bu operations research ve operational research kavramları arasındaki tartışmaya benzetilebilir. hangisi doğru bilen varsa beri gelsin.
  
  tezden sonra gelen edit: ömrümü yedin lan allahsız