Yapay zekadan makale özeti
- Kısa
- Ayrıntılı
- Bu video, bir eğitmen tarafından sunulan tam sayılı doğrusal programlama konulu bir eğitim dersidir.
- Ders, tam sayılı doğrusal programlamaya giriş yaparak başlayıp, model kurma teknikleri, kısıtların nasıl yazılacağı ve çözüm yöntemleri üzerine odaklanmaktadır. Video boyunca projelerin değerlendirilmesi, yatırımların seçimini kısıtlama, set kapsama problemi, sabit ödemeler problemi ve iş sıralama problemleri gibi çeşitli örnekler üzerinden konu detaylı olarak ele alınmaktadır.
- Ders içeriğinde yuvarlama yöntemlerinin geçerliliği tartışılırken, kesme düzlemi ve dal sınır algoritması gibi çözüm teknikleri anlatılmaktadır. Ayrıca, telefon hattı seçimi ve iş çizelgeleme gibi pratik problem örnekleri matematiksel modellerle ifade edilmekte ve değişkenler tanımlanarak amaç fonksiyonları oluşturulmaktadır. Dersin sonunda, bir sonraki derste bu modellerin çözüm yöntemlerinin anlatılacağı belirtilmektedir.
- 00:02Tam Sayılı Doğrusal Programlama Giriş
- Tam sayılı doğrusal programlamada önce model kurma örnekleri, "ya ya da" ve "eğer öyleyse" kısıtlarının olduğu örnekler yapılacaktır.
- Tam sayılı doğrusal programlamada değişkenlerden bazılarının veya tümünün tam sayılı değer alması söz konusudur.
- Tam sayılı doğrusal programlamaya özel bir çözüm yöntemi yoktur, doğrusal programlama çözüm teknikleriyle tam sayılı sonuçlara ulaşmaya çalışılır.
- 03:24Tam Sayılı Programlama Türleri
- Tüm değişkenlerin tam sayılı olduğu tam sayılı programlama problemleri incelenecektir.
- Değişkenlerin kimisi tam sayı, kimisi ondalıklı olabilen durumlar "karma tam sayılı" olarak adlandırılır.
- Doğrusal programlama çözüm yöntemleriyle çözdükten sonra yuvarlama kurallarıyla tam sayıya ulaşmanın doğru olup olmadığı ilk örnekte gösterilecektir.
- 05:04Örnek Problemin Model Kurulması
- Örnek problemde önümüzdeki üç yıllık planlama dönemi için beş projenin değerlendirilmesi isteniyor ve yıllık bütçeler yirmibeş milyon para biriminden fazla olmamalıdır.
- Projelerin seçilip seçilmemesi için x₁, x₂, x₃, x₄, x₅ değişkenleri 0 veya 1 değerini alacak şekilde tanımlanmıştır.
- Amaç fonksiyonu projelerden elde edilecek toplam kazançları maksimize etmektir ve yıllık bütçelerin kısıtlarını oluşturur.
- 11:10Çözüm Sonuçları
- Tam sayılı olarak çözüldüğünde x₁'den x₄'e kadar olan projelerin yapılması gerektiği, x₅'in yapılmaması gerektiği ve elde edilebilecek en fazla karda doksanbeş milyon para birimi olduğu bulunmuştur.
- Doğrusal programlama ile çözüldüğünde x₁'in 0,789, x₂, x₃, x₄'ün 1, x₅'in 0,7368 olduğu ve amaç değeri 108,68 olarak daha iyi bir sonuç elde edildiği görülmüştür.
- 13:15Doğrusal Programlama Sonuçlarının Tam Sayı Olması
- Doğrusal programlama sonuçlarında tam sayı değeri olmayan sonuçlar elde edildiğinde, yuvarlama kuralları uygulanması düşünülebilir.
- Tüm projelerin yapılması durumunda, bütçe kısıtlamaları sağlanmaz ve kısıtlar bozulur.
- Doğrusal programlama ile sonuç bulup bunları yuvarlamak bir çözüm yöntemi olamaz, kesme düzlemi ve dal sınır algoritması gibi yöntemler kullanılmalıdır.
- 16:43Tam Sayı Değişkenlerin Matematiksel İfadeleri
- Yatırım değerleri yalnızca 0 veya 1 değerini alabilir; 0 ise yatırımı yapma, 1 ise yatırımı yap demektir.
- Örnek olarak, 1, 3, 5 ve 6 yatırımlarından en az ikisinin seçilmeli olması durumunda, x1 + x3 + x5 + x6 ≥ 2 şeklinde ifade edilir.
- En fazla iki yatırımanın yapılması durumunda, x1 + x3 + x5 + x6 ≤ 2 şeklinde kısıtlanır.
- 21:46Farklı Kısıtların Matematiksel İfadeleri
- Sadece iki yatırımanın yapılması durumunda, x1 + x3 + x5 + x6 = 2 şeklinde ifade edilir.
- 1 ve 3 yatırımlarından mutlaka birinin yapılması durumunda, x1 + x3 = 1 şeklinde kısıtlanır.
- 5 ile 6 yatırımlarının aynı değerlendirilmesi durumunda, x5 = x6 şeklinde ifade edilir.
- 25:26Tam Sayılı Programlama Kısıtları
- İlk kısımda "bir ile yedi yapılırsa dört yapılsa da olur yapılmasa da olur" ifadesi, x4 ≤ x1 + x7 şeklinde modellenir ve x4'ün mecburiyeti yoktur.
- İkinci kısımda "bir ile yedi yapılırsa dört mutlaka yapılsın" ifadesi, x4 ≥ x1 + x7 - 1 şeklinde modellenir ve x1 ile x7'nin birden bir değer alması durumunda x4 de bir değer almalıdır.
- 28:44Set Kapsama Problemleri
- Set kapsama problemleri, tesislerin kurulması ile bazı bölgelerdeki servislerin kesişmesi veya tekrarlanması durumlarında tüm bölgeye hizmet verilmesi amaçlanırken en az sayıda tesisin kurulması gerektiği problem türüdür.
- Örnek olarak su arıtma tesisleri veya baz istasyonları gibi, kesişim yerlerinde hizmet veren ancak boşluk olmaması gereken tesislerin yerleştirilmesi problemi ele alınabilir.
- 30:36Kampüs Güvenlik Örneği
- Bir üniversitede kampüs güvenliği için kablolu acil telefon hattı çekilmesi isteniyor ve her ana yolda en az bir telefonun hizmet vermesi amaçlanıyor.
- Problemin çözümü için her telefonun en az iki yola hizmet vermesini sağlayacak şekilde yerleştirilmesi ve minimum sayıda telefon kullanılması gerekiyor.
- Modelde x1, x2, ..., x8 değişkenleri tanımlanarak telefonların konumlandırılacağı noktalar belirleniyor ve amaç fonksiyonu ∑x'i minimum yaparak telefon sayısını azaltmayı hedefliyor.
- 34:49Model Kısıtları ve Çözüm
- Her yola en az bir telefonun hizmet vermesi için kısıtlar yazılır, örneğin A yolu için x1 + x2 ≥ 1 şeklinde.
- Tüm değişkenlerin 0 veya 1 değerini alması isteniyor ve negatif olmama kısıtları uygulanıyor.
- Çözümde x1, x2, x5 ve x7 değişkenlerinin 1 değerini aldığı görülüyor, yani bu noktalara telefon konulması gerekiyor ve dört telefonla tüm yollara hizmet verilmiş oluyor.
- 39:15Sabit Ödemeler Problemi
- Sabit ödemeler problemi, tam sayılı programlama tipi bir problemdir ve birçok farklı alanda kullanılabilir.
- Bu probleminde iki tür maliyet vardır: sabit maliyet (faaliyeti başlatmak için gerekli olan maliyet) ve değişken maliyet (faaliyet esnasında oluşan miktar ile doğru orantılı olan maliyet).
- Sabit maliyet örneğin kalıp üretim maliyeti, üretim hazırlık maliyeti olabilirken, değişken maliyet ise işçilik ve malzeme maliyetleridir.
- 41:55Sabit Ödemeler Probleminin Matematiksel Gösterimi
- Sabit ödemeler probleminde toplam maliyet, sabit maliyet (m) ve birim maliyet (c) ile üretilen miktar (x) çarpımlarının toplamı şeklinde gösterilir.
- Cep telefonu hattı seçimi örneğinde, üç farklı telefon şirketi için sabit ve değişken ücretler farklılık göstermektedir.
- Bir kişi ayda ortalama 200 dakikalık uluslararası görüşme yapacaksa, hangi şirketlerden ne kadar konuşma yapması minimum maliyetle bu konuşmaları gerçekleştireceğini belirlemek gerekir.
- 44:20Tam Sayılı Değişkenlerin Kullanımı
- Sabit ödemeler probleminde, hangi hattı kullanacağımızı belirlemek için yardımcı bir değişken (y) kullanmak gerekir.
- x değişkenleri her bir operatörden görüşeceğimiz aylik uluslararası süreleri, y değişkenleri ise operatörü kullanacak mıyız, kullanmayacak mıyız bilgisini gösterir.
- x'in pozitif olması durumunda y'nin 1'e eşit olması gerekir, böylece sabit ücret oluşur; x sıfır ise y de sıfır olmalıdır.
- 52:15İş Çizelgeleme Problemi
- İş çizelgeleme problemi, tam sayılı değişkenler kullanılarak modellenen bir problem türüdür.
- Örnek problemde bir atölyede üç iş için tek bir makine kullanılıyor ve her iş için işlem süreleri ve teslim zamanları gün olarak verilmiştir.
- İşlerin gecikme cezaları da gün başına farklı para birimleriyle belirlenmiştir.
- 53:59İş Sıralama Problemi ve Gecikme Maliyeti
- Üç işin teslim zamanı otuzbeş gün ve gecikme cezası gün başına otuzdört para birimi olarak belirlenmiştir.
- Gecikme cezası, işlerin teslim zamanından geçerse gün başına hesaplanır; örneğin birinci iş yirmibeş günü bir gün geçerse ondokuz para birimi ceza ödenecek.
- Amacımız üç işin minimum gecikme cezasıyla sıralanmasını sağlamak ve her bir işin başlayacağı günü belirlemektir.
- 55:14Matematiksel Modelleme
- X ile işlerin başlangıç günleri, Yij ile işlerin sıralaması gösterilir; Yij=1 ise i işi j işinden önce yapılır, Yij=0 ise tersi durum söz konusudur.
- İşlerin çakışmaması için kısıtlar oluşturulur; aynı anda sadece bir iş yapılabilir ve işler birbirini takip etmelidir.
- Teslim zamanı kısıtları için, işin tamamlanma zamanı (başlangıç + işlem süresi) teslim zamanından büyükse gecikme oluşur.
- 53:09Gecikme Değişkenleri ve Amaç Fonksiyonu
- Gecikme durumunu göstermek için Sj+ (gecikme) ve Sj- (erken teslim) değişkenleri kullanılır.
- Sj+ değeri sıfırdan büyükse gecikme vardır, Sj- değeri sıfırdan büyükse erken teslim vardır.
- Amaç fonksiyonunda gecikme maliyetlerinin minimum yapılması hedeflenir: 19S1+ + 12S2+ + 34S3+.
- 1:07:06Model Kurulumu ve Çözüm Yöntemleri
- İşlerin sıralaması için oluşturulan kısıtlar, değişkenlerin sol tarafta ve sabit sayıların sağ tarafta olacak şekilde düzenlenir.
- Gecikme kısıtları için her iş için ayrı eşitlikler oluşturulur ve gecikme değişkenleri kullanılır.
- Tam sayılı programlamada modeller kurma yöntemleri anlatıldı ve sonraki derste çözüm yöntemleri ve e-çözüm yöntemleri anlatılacak.