1.2.MAXİMİZASYON PROBLEMLERİNİN GRAFİK ÇÖZÜMÜ

Lineer programlama problemlerini değişken sayısı üçü geçmedikçe grafik metodu ile çözmemiz mümkündür. Her ne kadar grafik metodu en uygun metod değilse de olayın özünü anlamak bakımından oldukça yararlıdır. Burada ele alacağımız örnek küçük ölçekli ve sadece iki ürün ürettiği varsayılan bir işletme olacaktır.

Örnek problem: Boyut Ltd şirketi masa ve iskemle üretmektedir. Her iki ürün de birincisi montaj, ikincisi ise cilalama aşamaları olmak üzere iki aşamadan geçmek zorundadır. Montaj bölümünün iş kapasitesi 60 saat, cilalama bölümünün iş kapasitesi ise 48 saattır. Bir masanın üretilebilmesi için montaj bölümünün 4 saat, cilalama bölümünün ise 2 saat çalışması gerekmektedir. Bir iskemlenin üretilebilmesi için ise montaj bölümümün 2 saat, cilalama bölümünün 4 saat çalışması gerekmektedir. Şirket masa başına 8 $ iskemle başına da 6 $ kazandığına göre en fazla karı elde edebilmesi için kaçar iskemle ve masa üretmelidir?

1.AŞAMA:

Problemi çözmeye başlayabilmek için öncelikle verileri matematiksel olarak ifade etmemiz gerekir.

İ = iskemle M = masa olsun.

Cebirsel olarak problemi şöyle ifade edebiliriz:

-----------------------------------------------------------

Kısıtlamalar: Montaj: 4.M + 2.İ £ 60

Cilalama: 2.M + 4.İ £ 48

M ³ 0

İ ³ 0

Maximum olması istenen fonksiyon:

Kar = 8.M + 6.İ

-----------------------------------------------------------------------

2.AŞAMA:

Yukarıda verilen eşitsizlikleri grafiğe dökerek çözüm bölgesini oluştururuz.

3.AŞAMA:

D noktasının koordinatlarını hesaplarız.

4.M + 2.İ = 60

2.M + 4.İ = 48

denklem sisteminin çözümü bize D noktasının koordinatlarını verecektir. Buradan D (12,6) olarak bulunur. Grafikte elde edilen konveks bölgenin diğer köşe noktalarının koordinatlarını zaten biliyorduk. A (0,0) , E (0,12) , C (15,0) ve D (12,6) bu bölgenin köşe noktalarını oluştururlar.

4.AŞAMA:

Dört ayrı köşe noktasının değerlerini hedef fonksiyonda yerleştirerek hangisinin daha fazla kar getirdiğini saptarız.

A (0,0) noktası için : 8.(0) + 6.(0) = 0$

E (0,12) noktası için : 8.(0) + 6.(12) = 72$

C (15,0) noktası için : 8.(15) + 6.(0) = 120$

D (12,6) noktası için : 8.(12) + 6.(6) = 132$

En büyük karı getiren nokta 132$ ile D noktası olmuştur ve D noktası bize aradığımız optimal çözümü vermektedir. Çünkü şu bilinmektedir ki bir lineer programlama probleminde eğer optimal bir çözüm varsa bu çözüm mutlaka elde edilen konveks bölgenin uç (köşe) noktalarından birinde olacaktır.

LİNEER PROGRAMLAMADA BAZI TEKNİK SORUNLAR

Uç Noktalar:

Tüm sınırlamalar aynen korunarak masalardan ve iskemlelerden elde edilecek kar değiştirilsin. Bu durumda yeni bir köşe noktası optimal çözümü verebileceği gibi aynı nokta korunabilir de. Hangi durumun söz konusu olduğunu yeni hedef fonksiyonda köşe noktalarının koordinatları yerine yazılmak suretiyle anlaşılabilecektir. Ancak her iki durumda da optimal çözüm mevcut ise bu çözüm mutlaka köşe noktalarından birinde oluşacaktır.

Çözümsüzlük:

Çözümsüzlük matematiksel anlamda tüm kısıtlamaları geçerli kılan bir ortak çözüm alanının bulunamaması yani tüm kısıtlamalara ait çözüm kümelerinin arakesitlerinin boş küme olmasıdır. Örneğin Boyut Ltd. örneğimize iki yeni kısıtlama getirerek pazarlama departmanının en az 16 masa ve yine en az 12 iskemle talebi olduğunu söyleyecek olursak, bunları grafiğe döktüğümüzde, montaj ve cilalama bölümlerinin kapasite arttırımına gitmedikleri durumda tüm kısıtlamaları aynı anda gerçekleştirecek bir çözüm kümesi olmadığını görürüz.

Sınırsızlık:

Çözümün, problemin kısıtlamalarının hiçbirini ihlal etmeksizin sonsuz büyük değerler alabilecek olması bir lineer programlama problemi için sınırsızlık anlamına gelmektedir. Ancak gerçek hayattan alınma problemlerin çözümünde bu türden bir sınırsızlık bulduğumuz takdirde problemi doğru formüle edemediğimiz anlamını çıkarmalıyız, çünkü hiçbir koşulda ve hiçbir firma sonsuz büyüklükte bir çözüme, yani sonsuz büyüklükte bir kara sahip olamaz.

Gereksiz Kısıtlamalar:

Çözüm bölgesini etkilemeyen kısıtlamalar gereksiz kısıtlamalardır. Bu kısıtlamalar problemin çözümüne zarar vermemekle birlikte gerçek hayattan alınma çok parametreli çözümlerde, bilgisayarlara oldukça büyük bir yük getirmeleri nedeniyle teşhis edilerek devre dışı bırakılmalarında yarar vardır. Yine kendi örneğimize dönecek olursak Satılabilecek iskemle sayısının , pazarlama departmanı tarafından yirmi olarak saptandığını varsayalım. Ancak biz üretim birimlerinin kapasite sınırlamaları nedeniyle zaten en fazla 12 iskemle üretebildiğimizi biliyoruz. Böylelikle en fazla yirmi iskemle kısıtlaması gereksiz bir kısıtlamadır ve devre dışı bırakılması gerekmektedir.

Birden Fazla Optimal Çözüm ( Alternatif Çözüm ):

Eğer hedef fonksiyon yardımıyla oluşturacağımız eş-kar doğrularının eğimi konveks çokgensel bölgemizin kenarlarından biri ile aynı eğime sahip ise, eş-kar doğrusu ile bu kenarın çakıştığı doğru parçası ( arakesitleri ) üzerindeki tüm noktalar alternatif çözümler oluşturur. Bu durum da firma açısından istediği ürün kombinasyonunu seçebilme açısından çok büyük bir esnekliğe sahip olmak anlamına gelmektedir.

1.3. MİNİMİZASYON PROBLEMLERİNİN GRAFİK ÇÖZÜMÜ

Teorik olarak minimizasyon problemlerinin grafik çözümünün maximizasyon problemlerininkinden bir farkı olmamakla birlikte, minimizasyon problemlerinde ortaya çıkan konveks çokgensel bölgenin kapalı bir alan oluşturmayabileceğine dikkat etmek gereklidir.

Örnek problem: Bebek mamaları üreten bir şirket, yeni bür ürün çıkarmayı planlamaktadır. Bu ürünün toplam ağırlığı 500 gram olacak ve içeriğinde P1 ve P2 adlı iki hammadde kullanacaktır. P1 nin gramı 5 TL ve P2 nin gramı 8 TL maliyetlidir. Kimyasal olarak ta bu ürünün en az 200 gram P2 ve en fazla 400 gram P1 içermesi gerekmektedir. Şirket bu ürünü en düşük maliyetle üretmeye çabalamaktadır.

1.AŞAMA:

Problemi çözmeye başlayabilmek için öncelikle verileri matematiksel olarak ifade etmemiz gerekir.

-----------------------------------------------------------

Kısıtlamalar: P1 ≤ 400 gram

P2 ≥ 200 gram

P1+P2 = 500 gram

P1 ≥ 0 ve P2 ≥ 0

Minimum olması istenen fonksiyon:

Maliyet = 5.P1 + 8.P2

-----------------------------------------------------------------------

2.AŞAMA:

Yukarıda verilen eşitsizlikleri grafiğe dökerek çözüm bölgesini oluştururuz.

3.AŞAMA:

Buradaki grafikte elde edilen bir konveks çokgensel alan değil, bir doğru parçasıdır. Bu doğru parçasını bir çokgensel bölgenin kenarlarından biri olarak düşünecek olursak köşe çözümlerinden biri doğru parçasının bir ucu, diğeri de diğer ucu olacaktır. Bu noktaların koordinatları da ( P1 , P2 ) = ( 300 , 200 ) ve ( P1 , P2 ) = ( 0 , 500 ) olduğuna göre her iki değeri de hedef fonksiyonda ayrı ayrı yerleştirecek olursak ( 300 , 200 ) noktasının en az maliyeti sağlayacak çözüm olduğunu ve minimum maliyetin de 4000 TL olacağını buluruz.