Doğrusal Programlama Problemleri, Çözümleri ve Uygulamaları [Örnekle]

Veri biliminin birçok uygulaması vardır, bunlardan en öne çıkanlarından biri optimizasyondur. Hepimiz bir şeyleri optimize etmeye odaklanma eğilimindeyiz. Optimizasyon, sahip olduğunuz sınırlı kaynaklarla en çok istenen sonuçları elde etmeye odaklanır.

Her türden optimizasyon problemi mevcuttur, bazıları küçük, bazıları oldukça karmaşıktır. Bunları incelerken, doğrusal programlama sorunları adı verilen belirli bir kategori bulacaksınız. Bu yazıda, bunların ne olduğunu ve bunlar üzerinde nasıl çalışabileceğinizi tartıştık.

Diyelim ki portakal veya elma ya da her ikisinin belirli bir kombinasyonunu alabilen bir meyve satıcısısınız. Ancak, yalnızca 5.000 INR bütçeniz var ve bunlardan yalnızca 30 torba saklayabilirsiniz. Şimdi bunları size en yüksek kârı sağlayacak şekilde satın almalısınız.

Şimdi bir torba portakal size 500 INR, bir torba elma ise 750 INR'ye mal oluyor. Bir torba portakal satışından 100 INR ve bir torba elma satışından 200 INR kazanabilirsiniz.

Bu sorunun çeşitli olasılıkları vardır. Yalnızca portakal almayı tercih edebilirsiniz, ancak o zaman deponuzda yalnızca 10 torba olur ve karınız 1000 INR olur. Benzer şekilde, yalnızca elma almayı ve 1500 INR'yi kar olarak tercih edebilirsiniz. İkisinin bir kombinasyonunu da satın alabilirsiniz.

Bu tür problemlere doğrusal programlama problemleri denir ve bunları detaylı olarak tartışacağız. Başlayalım:

Doğrusal Programlama Nedir?

Doğrusal programlama, doğrusal fonksiyonları kullanarak karmaşık ilişkileri gösteren bir yöntemdir. Doğrusal programlama ile amacımız bu fonksiyonlara en uygun çözümleri bulmaktır. İki nokta arasındaki gerçek ilişki oldukça karmaşık olabilir, ancak bunları basit bir şekilde göstermek için doğrusal programlamayı kullanabiliriz. Doğrusal programlama birçok endüstride uygulama bulur.

Doğrusal Programlamanın Temelleri

Doğrusal programlamanın bazı temel terimleri şunlardır:

Kısıtlama

Karar değişkenlerinizin sınırlamalarına (veya kısıtlamalarına) kısıtlamalar denir. Zaman kısıtlamalarının çoğu, bir sorunu çözmek için kaynaklarınız üzerinde sahip olduğunuz sınırlamalardır.

Karar Değişkeni

Bu değişkenler çıktınızı tanımlar. Sonucunuz bu değişkenlere bağlıdır, bu yüzden onlara 'karar değişkenleri' diyoruz.

Olumsuzluk Kısıtlaması

Doğrusal programlama probleminin karar değişkenleri sadece negatif olmayan değere sahip olabilir. Bu, karar değişkenlerinizin değerlerinin yalnızca sıfıra eşit veya sıfırdan büyük olabileceği anlamına gelir.

Amaç fonksiyonu

Amaç fonksiyonu, kararınızı vermenin amacıdır. Basit bir ifadeyle, doğrusal programlama probleminizin nihai sonucudur. Örneğin, belirli bir kaynak grubuyla elde edebileceğiniz maksimum karı bulduğunuzda, maksimum kar amaç fonksiyonudur.

Doğrusal Programlama Problemlerini Formüle Etmek

Gerçek hayatta uygulamak için doğrusal programlamayı nasıl formüle edeceğinizi bilmelisiniz. Bir oyuncak üreticisi olduğunuzu ve yalnızca iki oyuncak ürettiğinizi varsayalım: A ve B. Kabaca söylemek gerekirse, oyuncaklarınızın üretilmesi için iki X ve Y kaynağı gerekir. İşte oyuncaklarınızın gereksinimleri:

• Bir birim A oyuncak için bir birim X kaynağı ve üç birim Y kaynağı gerekir.

• Bir birim B oyuncağı, bir birim X kaynağı ve iki birim Y kaynağı gerektirir

Beş adet X kaynağınız ve 12 adet Y kaynağınız var. Bu oyuncakların satışından elde ettiğiniz kar marjlarınız:

• A oyuncağının satılan her birimi için 6 INR
• B oyuncağının satılan her birimi için 5 INR

Maksimum karı elde etmek için her bir oyuncaktan kaç adet üretirsiniz?

Çözüm

Doğrusal programlama problemimizi bir denklemde temsil edelim:

Z = 6a + 5b

Burada, z toplam karı, a oyuncak A birimlerinin toplam sayısını ve b, B birimlerinin toplam sayısını temsil eder. Amacımız Z'nin (karın) değerini maksimize etmektir.

Şimdi, şirketiniz bu oyuncaklardan mümkün olduğunca çok sayıda üretmek isteyecektir, ancak sınırlı kaynaklarınız var. Kaynaklarımızdaki sınırlamalar bu sorunun kısıtlamalarıdır. Biz sadece toplam var

a + b5

Şimdi A ve B oyuncağının her birimi sırasıyla 3 ve 2 birim Y kaynağı gerektirir. Ve matematiksel olarak yalnızca toplam 12 birim Y kaynağımız var, şöyle görünür:

3a + 2b 12

A oyuncağının birimlerinin değerlerinin yalnızca tam sayılarda olabileceğini unutmayın. Bu, a->0 ve b<-0 kısıtlamalarına da sahip olduğumuz anlamına gelir.

Yani, şimdi uygun bir doğrusal programlama probleminiz var. Bu örneği takip ederek diğer doğrusal programlama problemlerini formüle edebilirsiniz. Bu örnek oldukça basit olsa da, LP problemleri oldukça karmaşık hale gelebilir.

Okuyun: Doğrusal Programlama Proje Fikirleri ve Konuları

Doğrusal Programlama Problemlerini Formüle Etme Adımları

Doğrusal programlama problemini formüle etmek için şu adımları izleyin:

• Karar değişkenlerini bulun
• Amaç fonksiyonunu bulun
• Kısıtlamaları tanımlayın
• Negatif olmayan kısıtlamayı hatırla

Bir problem yukarıdaki kriterleri karşılıyorsa, lineer programlama problemidir. Sorunun türünü belirlemeye çalışırken bu kriteri akılda tutmak en iyi uygulamadır.

R ile Doğrusal Programlama Problemlerini Çözme

R kullanıyorsanız, doğrusal programlama problemlerini çözmek çok daha kolay hale gelir. Bunun nedeni, R'nin bu tür sorunları çözmek için özel olarak tasarlanmış çeşitli işlevlerle birlikte gelen lpsolve paketine sahip olmasıdır. Bir veri bilimcisi olarak LP sorunlarını çözmek için R'yi çok sık kullanıyor olmanız kuvvetle muhtemeldir. Bu nedenle, uygulamasını daha iyi anlamanıza yardımcı olmak için iki farklı örnek paylaştık:

Örnek vermek

Temel bir problemle başlayalım. Bir kuruluşun satış fiyatları 25 INR ve 20 INR olan iki ürünü vardır ve bunlar sırasıyla A ve B ürünleri olarak adlandırılır. Her gün bu ürünleri üretmek için 1800 birim kaynağa sahipler. Ürün A, 20 kaynak birimi gerektirir ve B, 12 kaynak birimi gerektirir. Bu ürünlerin her ikisinin de üretim süresi dört dakikadır ve kuruluş her gün toplam sekiz çalışma saati alır. Sorun şu ki, şirketin karını maksimize etmek için bu ürünlerin her birinin üretim miktarı ne olmalıdır?

Çözüm:

Amaç fonksiyonunu tanımlayarak bu problemi çözmeye başlayacağız:

max(Satış) = max( 25 y 1 + 20 y 2 )

Burada 25 ve 20 sırasıyla A ve B ürününün fiyatları, y1, üretilen A ürününün toplam adetlerini ve y2, üretilen B ürününün toplam adetlerini göstermektedir. Karar değişkenlerimiz y1 ve y2'dir.

Şimdi problemimiz için kısıtlamaları ayarlayacağız:

Kaynak kısıtlaması:

20 yıl 1 + 12 yıl 2 1800

Zaman kısıtlaması:

4 yıl 1 + 4 yıl 2 8*60

Maksimum karı elde etmek için üretmemiz gereken doğru sayıda ürünü bulmayı hedefliyoruz.

Sorunu Çözmek için R'yi Kullanmak:

Bu LP problemini çözmek için lpsolve kullanacağız ve amaç fonksiyonunu ayarlayarak başlayacağız:

> gerektirir(lpSolve)

Gerekli paketin yüklenmesi: lpSolve

> objektif.in <- c(25, 20)

> objektif.in

[1] 25 20

Ardından kısıtlamalar için bir matris oluşturacağız:

> const <- matrix(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> sabit

[,1] [,2]

[1,] 20 12

[2,] 4 4

> zaman kısıtlamaları <- (8*60)

> resource_kısıtlamalar <- 1800

> zaman_kısıtlamaları

[1] 480

> resource_kısıtlamalar

[1] 1800

Şimdi önceden tanımlanmış denklemleri oluşturalım:

> rhs <- c(resource_constraints, time_constraints)

> sağ

[1] 1800 480

> yön <- c(“<=”, “<=”)

> yön

[1] “<=” “<=”

Gerekli tüm bilgiler eklendikten sonra en uygun cevabı bulmaya başlayabiliriz. Paketimizin sözdizimi şöyledir:

lp( yön, amaç, const.mat, const.dir, const.rhs)

> optimum <- lp(yön=”maks”, amaç.in, sabit, yön, rhs)

> optimum

Başarı: amaç fonksiyonu 2625

> özet(optimum)

Uzunluk Sınıf Modu

yön 1 -yok- sayısal

x.count 1 -none- sayısal

amaç 2 -yok- sayısal

const.count 1 -none- sayısal

kısıtlamalar 8 -yok- sayısal

int.count 1 -none- sayısal

int.vec 1 -none- sayısal

bin.count 1 -none- sayısal

binary.vec 1 -none- sayısal

num.bin.solns 1 -none- sayısal

objval 1 -none- sayısal

çözüm 2 -yok- sayısal

önceden çöz 1 -none- sayısal

hesap.sens 1 -none- sayısal

sens.coef.from 1 -none- sayısal

sens.coef.to 1 -none- sayısal

çiftler 1 -none- sayısal

duals.from 1 -none- sayısal

duals.to 1 -none- sayısal

ölçek 1 -yok- sayısal

use.dense 1 -none- sayısal

yoğun.col 1 -none- sayısal

yoğun.val 1 -none- sayısal

yoğun.const.nrow 1 -none- sayısal

yoğun.ctr 1 -none- sayısal

use.rw 1 -none- sayısal

tmp 1 -none- karakter

durum 1 -yok- sayısal

Yukarıdaki kodu çalıştırdıktan sonra problemimiz için istediğiniz çözümlere ulaşabilirsiniz.

y1 ve y2 için optimum değerler:

y1 ve y2'nin üretmek zorunda olduğumuz A ürününün ve B ürününün birimleri olduğunu unutmayın:

> optimum$çözüm

[1] 45 75

Optimum satış rakamı:

Elde edilen y1 ve y2 değerleri ile elde edebileceğimiz maksimum kar:

> optimum$nesne

[1] 2625

Ayrıca Okuyun: Makine Öğrenimi İçin Lineer Cebir

Doğrusal Programlamanın Kullanım Alanları

Daha önce de belirttiğimiz gibi, doğrusal programlama birçok endüstride uygulama alanı bulmaktadır. Kullandığımız bazı alanlar şunlardır:

• Teslimat hizmetlerinin artan popülaritesi ile doğrusal programlama, optimum rotaları bulmak için en çok tercih edilen yöntemlerden biri haline geldi. Bir Ola veya Uber aldığınızda, yazılım en iyi rotayı bulmak için doğrusal programlama kullanır. Amazon ve FedEx gibi teslimat şirketleri de teslimat görevlileri için en iyi rotaları belirlemek için bunu kullanıyor. Teslimat süresini ve maliyetini azaltmaya odaklanırlar.
• Makine öğreniminin denetimli öğrenmesi, doğrusal programlamanın temel kavramları üzerinde çalışır. Denetimli öğrenmede, sağlanan girdi verilerine göre çıktıyı tahmin etmek için en uygun matematiksel modeli bulmanız gerekir.
• Perakende sektörü, raf alanını optimize etmek için doğrusal programlama kullanır. Bu kadar çok marka ve ürün mevcutken, bunları mağazada nereye yerleştireceğinizi belirlemek çok titiz bir iştir. Bir ürünün mağazaya yerleştirilmesi, satışlarını büyük ölçüde etkileyebilir. Big Bazaar, Reliance, Walmart gibi büyük perakende zincirleri, ürün yerleşimini belirlemek için doğrusal programlama kullanır. Maksimum kar elde etmek için en iyi ürün yerleştirmeyi sağlarken tüketicilerin ilgisini akılda tutmak zorundadırlar.
• Şirketler tedarik zincirlerini geliştirmek için doğrusal programlama kullanır. Bir tedarik zincirinin verimliliği, seçilen rotalar, zamanlamalar vb. gibi birçok faktöre bağlıdır. Doğrusal programlama kullanarak, verimliliklerini optimize etmek için en iyi rotaları, zamanlamaları ve diğer kaynak tahsislerini bulabilirler.

Doğrusal Programlama ve Veri Bilimi Hakkında Daha Fazla Bilgi Edinin

Doğrusal programlama, veri biliminin en hayati kavramlarından biridir. Ayrıca, yetkin bir veri bilimcisi olmak için bilmeniz gereken temel bir konudur. Tartıştığımız gibi, bu konsept için birçok uygulama var ve günlük yaşamınızda kullanım örneklerini bulabilirsiniz.

Blogumuza giderek veri bilimi ve ilgili kavramlar hakkında daha fazla bilgi edinebilirsiniz. Daha fazlasını öğrenmenize yardımcı olacak birçok değerli kaynağımız var. İşte daha fazla okumanız için bazıları:

• Veri Bilimcisi olmak için En Önemli Nedenler
• Her Veri Bilimcisinin Bilmesi Gereken Algoritmalar
• Nasıl Veri Bilimcisi Olunur?

Öte yandan, endüstri uzmanlarından öğrenmek için bir veri bilimi kursu alabilirsiniz. Videolar, testler ve projeler aracılığıyla etkileşimli bir şekilde öğreneceksiniz. Bir kurs almak, profesyonel bir veri bilimcisi olmak için gerekli becerileri öğrenmenize yardımcı olacaktır. IIIT-B & upGrad'ın çalışan profesyoneller için oluşturulan ve 10'dan fazla vaka çalışması ve proje, uygulamalı uygulamalı atölye çalışmaları, endüstri uzmanlarıyla mentorluk, endüstri danışmanlarıyla bire bir, 400+ saat sunan Veri Biliminde PG Diplomasına göz atın en iyi firmalarla öğrenme ve iş yardımı.