Bir doğrusal programlama problemini oluşturmak için problem hedefini, aktiviteleri, sınırlanmış kaynakları belirlemekle işe başlarsınız. Aktivitelerin hedefe katkı ve kaynakları kullanım katsayılarını da belirledikten sonra problemin matematiksel fonksiyonlarını oluşturursunuz.
Burada çözüm amaçlı değilse de bazı küçük örnek problem sunumlarının oluşturulmasını göstereceğiz:
Bir çitftçinin 10 dönüm ekilebilir arazisi vardır. Ürün satışından mümkün olan en yüksek geliri elde etmesi için nohut ve fasulyeden hangisine kaç dönüm ayırması gerektiğini soruyor.
Hedef değişken toplam satış geliridir. Orası apaçık belli.
Aktiviteler nohut ve fasulye ekimidir. Aktivite değişkenleri ise bu iki ürüne ayrılan ekim alanlarıdır.
Performans fonksiyonunu oluşturmak için ürünlerin kilo veya ton başına satış fiyatlarını öğrenmelisiniz.
Ama dikkat edin: aktivite değişkenleri ekilen ürün miktarları değil, ürünlere ayrılan ekim alanlarıdır. Demek ki birim alan (metrekare veya dönüm) başına elde edilecek satış gelirini öğrenmeniz gerekecek. Bunun için de nohut ve fasulyenin dönüm başına rekoltesini (hasat miktarını) ve ayrıca kilo ya da ton satış fiyatını bilmelisiniz.
Tek sınırlı kaynak ekilebilir arazi alanıdır. O da 10 dönümdür.
Size verilen bilgilere göre,
Fasulye rekoltesi 500 kg/dönüm
Nohut rekoltesi 200 kg/dönüm
Fasulye fiyatı 5 TL/kg
Nohut fiyatı 2 TL/kg
(örnek çiftçimiz tarladan pazara doğrudan satış yapıyor galiba)
Demek ki ürünlerin dönüm fiyatları
Fasulye için 2500 TL/dönüm
Nohut için 400 TL/dönüm.
Fasulye ekilen dönüm sayısını (ondalıklı olabilir) x1,
Nohut ekilen dönüm sayısını (ondalıklı olabilir) x2
olarak gösterirseniz,
Performans fonksiyonunu
Z = 2500 x1 + 400 x2
veya, sonucu 100 ile çarpmayı unutmamanız koşuluyla,
Z = 25 x1 + 4 x2
şeklinde yazabilirsiniz.
Problemin tek kısıtını da
x1 + x2 ≤ 10
şeklinde yazarsınız.
Aynı çiftçi, aynı rekolte ve fiyat değerleri geçerli olmak üzere, fasulye/nohut ekim problemini işçiliği de hesaba katarak çözdürmek istiyor.
Hasat için çalıştırabileceği işçi sayısı 10.
Bir işçi en fazla 0,3 dönüm fasulye,
Bir işçi en fazla 2,0 dönüm nohut hasat edebilirmiş.
Bu son bilgiyle problem sunumuna ikinci bir kısıt eklersiniz.
Fasulye hasadı için gereken işçi sayısı x1 / 0,3 yani 3,33 x1
Nohut hasadı için gerekli işçi sayısı 2 x2 olacaktır.
Böylece, ekleyeceğiniz ikinci kısıt ifadesi
3,33 x1 + 2 x2 ≤ 10
olacaktır.
İşçilik giderinin performans fonksiyonunda hesaba katılması gerektiğini düşünebilirsiniz, ve haklıdırsınızdır, ama çiftçinin hasat için çalıştıracağı işçi sayısı belli olduğuna göre, toplam satış gelirinden düşmesi gereken işçilik gideri de bellidir.
Sonuç olarak, maksimize edilecek hedef değişken yine toplam satış geliridir.
Bir reklamcı en yüksek kârı elde edecek şekilde kaç tabela veya afiş hazırlatabileceğini soruyor.
Size verdiği bilgilere göre,
Bir tabela 2 kg, 100 afiş 1 kg boya gerektiriyor.
Bir tabela 3 saat işçilik, 1 afiş 3 dk işçilik gerektiriyor.
İşçi saat ücreti 10 TL, boya kg fiyatı 5 TL.
Bir tabela 400 TL, bir afiş 2,5 TL gelir getiriyor.
Reklam atölyesinde aynı anda en fazla 6 işçi çalışabiliyor.
Reklam atölyesi günde en fazla 10 saat açık olabilir.
Ortamda boya kullanılıyor olması nedeniyle bir işçi günde 4 saatten fazla çalışamaz.
(Doğrudan belirtilmemiş, ama aynı anda çalışabilecek işçi sayısı, toplam mesai saati vb. sınırlamalarına uymak koşuluyla, gerektikçe bir saatliğine veya daha kısa sürelerle geçici işçi çalıştırmanın mümkün olduğunu varsayabilirsiniz)
Bu problemin çözümünde yardımcı olmak için (kendiniz deneyecekseniz gözünüzü ve bu sayfayı kapatıp sonra gelin) ilk bir kaç adımı gösterelim:
Gelir getirebilecek aktiviteler tabela ve afiş üretimidir; değişkenlerimizi
x1 : tabela üretim adedi,
x2: afiş üretim adedi
diye belirleyebiliriz.
Afişler için üretim miktarını 100'lük lotlar gibi düşünmek daha mantıklı olabilir.
Biz öyle yapmadık, ama siz isterseniz öyle deneyin.
Hedef fonksiyon toplam gelirin matematiksel ifadesidir:
Z = 400 x1 + 2,5 x2
İşçilik için birden fazla kısıt verilmiş, ama biraz düşünürseniz, tüm bu kısıtların aslında fazlalık olduğunu fark edeceksiniz:
10 saatlik mesainin her anında en fazla 6 işçi çalıştırabileceğimize göre, günde 60 saatlik işçilik kullanacağız. Yok ortamda boya varmış, bir işçiyi 4 saatten fazla maruz bırakamazmışız, tüm bunlar gereksiz ayrıntılar. İşçinin birinin nefesi yetmez, çıkar ya da düşer kalır, diğeri gelir, sonuçta bir işçi çalışıyor olacak. İşçiler 10'ar dakikalık mikro-vardiyalarla bile çalışsalar, sonuçta günlük işçilik toplamı 60 saat olacaktır.
Açgözlü patronun bakış açısı bu ama siz yine de kendi bakış açınızla bir daha bakın çözümün bu adımına.
Günlük işçilik toplamı değişmeyeceğine göre, işçilik masrafını dikkate almamıza da gerek yoktur; patronun eli mahkum, ödeyecek o ücretleri. Günlük kar hesabı istenmişse, bulduğunuz sonuçtan 300 TL işçilik toplamını çıkartırsınız, yeter.
Maksimum 4'er saatlik vardiyalar nedeniyle tam zamanlı çalıştıramayacağı işçiler için sigorta primi ödemek zorunda kalmayacağı için patron zaten halinden memnun.
İşçilik kısıtlarını şu matematiksel ifadeyle birleştirebiliriz:
3 x1 + x2 / 20 ≤ 60
Boya kısıtını, ... yazamıyoruz, çünkü kısıt-mısıt yok. Kimse bize an fazla şu kadar boya kullanabilirsiniz dememiş. Ortamda oluşacak hava kirliliğini belli bir seviyenin altında tutmak için bir saat içinde en fazla şu kadar gram boya kullanabilirsiniz demiş olsalar, öyle bir kısıt olurdu, ama o da yok.
Sonuç olarak, tek yapmanız gereken şey boya kısıtının eğimini hedef fonksiyonun eğimiyle karşılaştıracaksınız. Tek bir kısıt olunca, mecburen ya sadece tabela, ya da sadece afiş basıyor olacak patron.
Metal A.Ş. hammadde olarak üç tip alaşım kullanarak iki tip (A ve B) ürün üretmektedir. Alaşımlar aşağıdaki tabloda gösterilen oranlarda kalay, çinko ve kurşun içermektedir.
(Kaynak: https://web.itu.edu.tr/topcuil/ya/END331gecmissinavsorulari.pdf)
A ve B ürünlerinin metal içerikleri hakkında da şu kısıtlar konmuştur:
A ürününde en fazla %50 kalay ve en az %30 kurşun olmalıdır,
B ürünü %35 çinko içermelidir.
Firmanın her bir alaşımdan aylık en fazla 400 kg temin edebileceği, A ve B ürünlerinin her ikisi için de aylık talebin 700 kg olduğu bilgilerine dayanarak, firmanın toplam maliyetinin minimizasyon problemi için LP modelini oluşturun.
(Ek bilgi: Talebin tam karşılanamaması halinde A ürünü için kg başına 30 TL, B ürünü için 35 TL ceza ödeyecektir)
Bu problemin çözümü için bir kaç ipucu verecek olursak,
Problemin hedef değişkenleri (kg cinsinden) A ve B üretim miktarları olsun dersek, bu üretim miktarlarından karşılanamayan talep için ödenecek cezayı bulabiliriz, ama hammadde temin masraflarına doğrudan ulaşamayabiliriz. Belki hedef değişkenler olarak olarak hammadde alım miktarlarını kullanmak daha doğru olacaktır:
Temin edilen Alaşım-1 miktarına X1, Alaşım-2 miktarına X2 , Alaşım-3 miktarına da X3 diyelim.
Problemin hedef fonksiyonu bu üretimin toplam maliyetidir. Seçtiğimiz hedef değişkenleri kullanarak, bu toplam maliyet içindeki alaşım satın alma maliyetini bulmak kolaydır:
Z = 22 X1 + 20 X2 + 25 X3
Ama toplam maliyet bundan ibaret değildir. A ve B üretim miktarları talebi karşılayacak kadar değilse ödenecek ceza da toplam maliyete dahil edilmelidir. Maliyetin bu kısmını belirlemek için satın alınan alaşım miktarlarından üretim miktarlarına geçiş için formül oluşturmalıyız.
Hammadde miktarlarından A ve B üretim miktarlarına geçiş yapmaya çalışırken şunu farkedeceksiniz: A ve B ürünleri de aslında kalay, çinko ve kurşun metallerinin belli miktarlarda karışımlarından ibarettir. Tek sorun, ikisi için de hangi metalden tam olarak ne kadar gerektiği belli değildir. Yalnızca B için gereken çinko oranını biliyoruz, ama onun için bile diğer metallerin ne kadar kullanılacağı belirlenmemiş.
İşte bu noktada bir şey daha farkedeceksiniz: Metal A.Ş. hammadde temin ederken, Alaşım-1, 2 veya 3'den sadece istediği metalleri çekip alamaz; alaşımları olduğu gibi almak zorundadır. Bunlardan B üretmek için de hammadeleri gerekli çinko oranını tutturacak şekilde karıştırmalıdır. Daha da ilginci, sırf çinko oranına bakarak B üretmeye çalışırken, A üretiminde kullanabileceği hammadeleri B üretimine yönlendirmiş olacaktır. Bu durumda A ürünü için talebi karşılayamazsa da belirlenen miktarda ceza ödeyecektir.
Her neyse, lafı uzatmadan, size Metal A.Ş. nin de gerekirse eksik üretim cezasına razı gelerek A ve B üretim miktarlarını serbestçe belirleyebileceğini belirtelim. Yani bu problemde A üretim miktarını X4, B üretim miktarını da X5 diye ek değişkenler olarak modele dahil edebilirsiniz.
Bu durumda talep eksikliklerinin cezasını da toplam maliyeti belirleyen hedef fonksiyona ekleyebileceksiniz:
Z = 22 X1 + 20 X2 + 25 X3 + 30 * (700 - X4) + 35 * (700 - X5)
Parantezlerin açılmasını ve çarpmanın toplama üzerine dağılım prensibinin uygulanmasını size bırakıyoruz. Unutmayın, hedef fonksiyonda gözükecek sabit tutarları son çözüm aşamasına kadar dışarıda bırakabilirsiniz.
Şimdi gelelim kısıtlara:
Şu kısıtlar hammadde olarak kullanılacak alaşımlardan temin edilebilecek miktarların sınırlı olduğunu gösteriyor:
X1 ≤ 400
X2 ≤ 400
X3 ≤ 400
Üretim miktarlarının talebi geçmeyeceğinden emin olmak için de şu kısıtları eklemeliyiz:
X4 ≤ 700
X5 ≤ 700
Yoksa hedef fonksiyona eklediğimiz karşılanamayan talebin cezası siye eklediğimiz tutar talep fazlası üretim için ödüle dönüştür ve çözüm sınırsızlığa doğru kayabilir (olmaz, ama ya olursa?)
B ürününde olması gereken çinko oranını hammadelerden gelen çinko oranına bağlayarak şu kısıtı elde ederiz:
35 X5 ≤ 10 X1 + 15 X2 + 45 X3
Bu kısıtı eşitlik olarak yazmadık, çünkü B'nin geri kalan %65'i de herhalde hammadelerden gelen diğer metallerden ibaret olacaktır. B üretiminde kullanılmayan çinko da onun oranını önemsemeyen A üretiminde kullanılacaktır. Yani, aslında çinko fazla gelsin de yeter ki eksik kalmasın. Belki de yanlış düşünüyoruz; siz isterseniz metalik dumanlar solumayacağınız bir yerde bir rüyaya yatın.
A ürünündeki kurşun oranını tutturmak için şu kısıtı oluşturduk:
30 X4 ≤ 30 X1 + 60 X2 + 10 X3
A ürünündeki kalay oranıyla ilgili olarak da şu kısıtımız var:
60 X1 + 25 X2 + 45 X3 ≤ 50 X4
Bu iki kısıt ile A için en az kurşun oranıyla en fazla kalay oranını tutturacağımızdan emin oluruz.
Kısıtlar hakkında ek bir not: A ve B metal oranlarıyla ilgili kısıtları X'li terimleri bir tarafa toplayıp diğer tarafta sıfır bırakacak şekilde düzenleyebilirsiniz.
Bir elektronik şirketi tuşlu ve grafikli bilimsel hesap makineleri üretiyor.
Size verilen şu bilgilere göre en yüksek karı sağlayacak günlük üretim planını belirleyecek problemi tanımlayıp grafik çözümünü yapın:
(Kaynak: http://www.purplemath.com/modules/linprog3.htm)
Uzun vadeli tahminlerine göre her gün en az 100 tuşlu ve 80 grafikli hesap makinesi satılabilir.
Tuşlu hesap makinesi üretimi günde 200'ü geçemez.
Grafikli hesap makinesi üretimi günde 170'den fazla olamaz.
Bir teknoloji marketleri zinciriyle yapılan anlaşma gereği günde 200 (tuşlu veya grafikli) hesap makinesi gönderilmesi gerekiyor. Anlaşmanın belirlediği sabit fiyatlara göre
Bir tuşlu hesap makinesi satışı $2 zarar,
Bir grafikli hesap makinesi satışı $5 karla sonuçlanıyor.
Bir şirket A ve B makinelerini kullanarak iki ürün (diyelim, X ve Y) üretiyor.
Size verilen bilgilere göre:
X üretimi parça başına
A makinesinde 50 dakika
B makinesinde 35 dakika işlem gerektiriyor.
Y üretimi parça başına
A makinesinde 24 dakika,
B makinesinde 33 dakika işlem gerektiriyor.
Halihazırda stokta 30 parça X ve 90 parça Y ürünü var.
Haftalık çalışma limitleri
A makinesi için 40 saat,
B makinesi için 35 saat.
Ürünlerin haftalık talepleri
X için 75 parça,
Y için 95 parça.
Şirketin hedefi hafta bitiminde stokta kalan X ve Y parça sayılarını maksimize etmek. Bunun için haftalık üretim planını belirlemek istiyorlar.
Bu problemin matematiksel modelini oluşturun ve grafik yöntemiyle çözün.
(Kaynak: http://people.brunel.ac.uk/~mastjjb/jeb/or/morelp.html)
Bir çiftçinin (bu seferki Amerikalı) ekecek 10 hektar (100 dönüm) arazisi var. Arazinin kaç hektarına buğday, kaç hektarına yulaf ekmesi gerektiğini soruyor.
(Kaynak: http://www.sonoma.edu/users/w/wilsonst/courses/Math_131/lp/default.html)
En az 7 hektar ekmesi gerekiyor.
Ekim faliyetlerinde harcayabileceği $1200 parası var.
Bir hektara buğday ekmenin masrafı $200.
Bir hektara yulaf ekmenin masrafı $100.
Ekim faliyetlerine ayırabileceği 12 saati var.
Bir hektara buğday ekmek 1 saat,
bir hektara yulaf ekmek 2 saat harcatıyor.
Toplam karı maksimize etmek istiyor.
Bir hektar buğday $500,
bir hektar yulaf $300 kar getiriyor.
Bu problemin matematiksel modelini oluşturun ve grafik yöntemiyle çözün.
Bir okul 400 öğrenciyi mümkün olan en az harcamayla okul gezisine götürmek istiyor. Bağlantı kurdukları bir tur firmasının iki farklı otobüsünden kaç tane kiralamaları gerektiğini soruyorlar.
(Esin kaynağı: http://www.vitutor.com/alg/linear_programming/problems_solutions.html)
Tur firmasının
10 adet 50 kişilik (büyük),
8 adet 40 kişilik (küçük) otobüsleri,
ama bu gezi için yalnızca 9 şoför bulabilirler.
Tur firmasının istediği ücretler:
Büyük otobüs için 2500 TL,
Küçük otobüs için 1800 TL.
Şoförler için ayrıca ücret talep etmiyorlar (Belki de kaçak göçmen çalıştırıyorlar).
Bu problemin matematiksel modelini oluşturun ve grafik çözümünü yapın.
Üç ürün imal eden bir fabrikada üretim hatları her mesai gününde yalnızca bir ürün üretecek şekilde ayarlanabiliyor. Her ay 22 mesai günü vardır. Aşağıdaki bilgilere göre maksimum kar için ayın kaç gününde hangi ürünleri üretmeleri gerektiğini soruyorlar. (Kaynak: ???)
Ürünlerin aylık talepleri:
Ürün-1 için 530bin
Ürün-2 için 450bin
Ürün-3 için 540bin
Ürün birim karları:
Ürün-1 için 51 kuruş
Ürün-2 için 56 kuruş
Ürün-3 için 50 kuruş
Ürünlerin günlük üretim limitleri:
Ürün-1 için 50bin
Ürün-2 için 45bin
Ürün-3 için 55bin
Problemin bu haliyle matematiksel modelini oluşturun ve çözmeye çalışın.
Üretim hatlarının kurulum masraflarının da olduğu varsayımıyla problemin tanımını yeniden oluşturun ve çözmeyi deneyin:
Ürün-1 için 170bin TL
Ürün-2 için 150bin TL
Ürün-3 için 100bin TL
Ürünlerin aylık üretimleri en az aşağıdaki gibi olmalıysa problem sunumu ve çözümü nasıl olur?
Ürün-1 en az 2000
Ürün-2 en az 2000
Ürün-3 en az 1600
Koltuk ve kanepe üreten bir mobilya imalatçısı maksimum kar için hangi üründen günde ne kadar üretmesi gerektiğini soruyor.
(Esin kaynağı: http://www.math.tamu.edu/~jwhitfld/TQG_AlgII/2006-2007/LinearProgramming.pdf)
Her iki ürünün marangozluk, cilalama ve döşeme aşamalarından geçmesi gerekiyor.
Bir koltuğun imali
3 saat marangozluk
9 saat cilalama
2 saat döşeme gerektiriyor.
Bir kanepe imali
2 saat marangozluk
4 saat cilalama
10 saat döşeme gerektiriyor.
Bu işlemler için ayrılan işçilik saatleri:
Marangozluk için 66 saat
Cilalama için 180 saat
Döşeme için 200 saattir.
(NOT: Bu değerler bu işlere ayrılan işçi sayıları çarpı günlük çalışma saatleridir.)
Bir koltuk 280 TL, Bir kanepe 230 TL kar bırakıyor.