DOĞRUSAL PROGRAMLAMA

Yöneylem araştırmasının en gelişmiş ve yaygın uygulama alanını oluşturan doğrusal programlama,
doğrusal karar problemleriyle ilgili kavram ve teknikler topluluğudur. Bu bölümde, önce doğrusal
problemlerin matematiksel modellemesi anlatılıp, sonra da örnek problemler ele alınıp modellenecektir.
Doğrusal programlama, belirli bir amaca ulaşmak için, bazı kısıtlayıcılar altında kıt kaynakların en
verimli şekilde kullanılmasını sağlayan bir matematiksel yöntemdir. Bu şekilde varılmak istenen amaç,
kâr maksimizasyonu (en büyükleme) veya maliyet minimizasyonu (en küçükleme) olarak belirlenebilir.
Doğrusal programlamada “doğrusal” sözcüğü, fonksiyonların doğrusallığını, “programlama” ise planlama
işlemini ifade etmektedir. Doğrusal programlama, tüm uygun seçenekler arasından optimum (eniyi)
sonucun elde edilmesini sağlayan planlama faaliyetlerini içermektedir. Doğal olarak böyle bir
programlama sürecinde, önce gerekli veriler toplanır, problem modellenir ve daha sonra modelin çözümü
araştırılır. Doğrusal programlama modeli kurulurken amacın, değişkenler arasında ilişkilerin ve
kullanılacak kıt kaynakların tanımlanması gerekir.

Günümüz sistemleri (üretim, dağıtım, vb.) büyük sistemlerdir. Bu büyük sistemlerin modelleri de çok
sayıda değişken ve kısıtlayıcıdan oluşmaktadır. Büyük modeller, bilgisayar yardımıyla
çözülebildiğinden, doğrusal programlamanın uygulama alanı sadece kıt kaynakların dağıtımı ile sınırlı
kalmamış, diğer birçok alanda da önemli uygulamalar ortaya konmuştur. Doğrusal programlamanın
uygulama alanları ile ilgili olarak aşağıdaki liste verilebilir.
• Ulaştırma ve lojistik problemleri,
• Endüstriyel üretim planlaması ve envanter (stok) kontrolü
• Personel programlaması
• Beslenme(diyet) problemleri
• Karışım problemleri
• Tarımsal planlama
• Finansal planlama
• Yatırım planlaması
• Sağlık sistemleri
• Askeri planlama
• Trafik planlaması
• Atama problemleri
• Reklam seçimi problemleri
• Karışım problemleri

Gerçek hayatta karşılaşılan çoğu karar problemi için, en azından uygun kabullerle, doğrusal karar modeli
geliştirmek mümkündür. Bir problem için karar modeli geliştirmek ve kurmak gerçek sistemi
matematiksel olarak ifade etmek demektir. Bu işlem yapılırken bilgi kaybı kaçınılmazdır. Önemli olan
en az bilgi kaybı ile dönüşümü gerçekleştirebilmektir. Bu nedenle modelden tutarlı sonuçlar elde
edilebilmesi için bir takım varsayımlar kabul edilmelidir.

Doğrusallık (Oranlılık) Varsayımı
Bu varsayım modelin amaç fonksiyonu ve kısıtlayıcı fonksiyonları ile ilgilidir. Doğrusallık varsayımı,
işletmenin girdileri ile çıktıları arasında doğrusal bir ilişkinin olduğunu gösterir. Üretim düzeyi artarken
aynı oranda üretim girdileri de artar.
Eğer, Xj’inci eylem için amacın oluşumu doğrusallık özelliği gösteriyorsa, Xj’nin her bir birim
değerinin kara katkısı cj iken, Xj’nin çözüm değerinin amaca katkısı cjXj kadar olur. Bunun yanında karar
problemine esas olan bi’inci kaynaktan her bir birim Xj için gerekli kaynak miktarı aij olmak üzere Xj için
kaynak gereksinimi aijXj kadar olur. Kısıtlar ve amaç fonksiyonu birinci dereceden fonksiyon olmalıdır.
Aksi takdirde, doğrusal olmayan programlama söz konusu olur.
Bu varsayım, her bir karar değişkeninin; gerek amaç fonksiyonu, gerekse tük kısıtlayıcılara etkisinin
söz konusu değişkenin (Xj ) değeriyle doğru orantılı olması gerektiğinin ifade eder.

Toplanabilirlik Varsayımı
Doğrusal programlamada her fonksiyon, ilişkili olduğu faaliyetlerin, bireysel katkılarının toplamıdır.
Karar değişkenlerine verilecek değerlere göre, her birinin sağladığı katkılar toplanıp, toplam katkıyı, yani amaç fonksiyonunu oluşturuyorsa, toplanabilirlik varsayımı geçerlidir demektir. Bu varsayımı, kısıtlayıcıların sol tarafındaki sabitler için ele alırsak; değişik üretim faaliyetlerine kaynak
olan, üretim girdilerinin toplamının, her bir işlem için ayrı ayrı kullanılan girdilerin toplamına eşit olduğunu gösterir.

Bölünebilirlik Varsayımı
Modelin karar değişkenleri Xj’ler, her türlü reel değerleri alabiliyorsa, bölünebilirlik varsayımı sağlanıyor
demektir. Böylece, karar değişkenleri, bazı faaliyetlerin düzeyini gösterdiğinden, faaliyetlerin kesirli
düzeylerde çalışabileceği varsayılır.
Bazen girdi ve çıktıların bölünmezlik sorunu nedeniyle, karar değişkenlerini tamamının veya
bazılarının tam sayı olması gerekebilir. Böyle durumlarda, tam sayılı programlama söz konusu olur.

Belirlilik (Kesinlik) Varsayımı
Doğrusal programlama modelindeki tüm parametrelerin (amaç fonksiyonu katsayıları-cj, sağ taraf sabitleri-bi ve teknoloji katsayıları- aij) biliniyor olduğu varsayımıdır. Parametre değerlerini kesin olarak biliniyor olması varsayımı, modelin deterministtik model olduğunun göstergesidir.
Bir problemde, karar değişkenleri ve parametrelerle ilgili olarak; doğrusallık, toplanabilirlik, bölünebilirlik ve belirlilik varsayımları geçerli ise bu problem doğrusal programlama problemi olarak modellenip çözülebilir. Burada dikkat edilmesi gereken husus, problemin doğru belirlenmesidir.
Parametre değerlerinden kesin değerleri bilinmeyenler için tahmin yoluna gidilebilir. Daha sonra matematiksel modelleme aşamasına geçilmelidir. Fakat modelin doğrusallık ve bölünebilirlik varsayımları, gerçek dünyadaki ilişkileri gözlemlendiğinde bir eksiklik gösterdiği söylenebilir. Denilebilir ki, bu iki varsayım doğrusal programlama yöntemini kısıtlamaktadır.

Model kelime anlamı gerçeğin benzeri demektir. Model kurma, sistemi oluşturan unsurların matematiksel terimlerle ifade edilmesidir. Başka bir deyişle problem, matematik diline tercüme edilir. Model doğrusal programlama gibi standart bir matematiksel model halinde ifade edilebiliyorsa, bilinen algoritmalar yardımıyla çözüme ulaşılabilir. Bir problemin, doğrusal programlama modeli kurulurken önce karar değişkenleri tanımlanır, sonrada amaç fonksiyonu ve kısıtlayıcılar formüle edilir.

Bir problemin doğrusal programlama modelinin kurulmasına, öncelikle karar değişkenlerinin
tanımlanmasıyla başlanır. Karar değişkeni: bir problemde karar vericinin kontrolü altında olup da, değeri
araştırılan eylemler, karar değişkenleridir. Herhangi bir doğrusal programlama modelinde karar değişkenleri,
alınacak kararları tamamen betimlemelidir. Karar değişkenleri, alınacak kararlara ilişkin faaliyetlerin
düzeyini göstermektedir.
Karar değişkenleri genellikle; Xj sembolü ile gösterilir.
Xj : j’ inci üründen üretilecek (veya taşınacak) miktar anlamındadır. (j=1,2,….,n)

Herhangi bir doğrusal programlama probleminde karar verici, karar değişkenlerinin bazı fonksiyonunu maksimum veya minimum yapmak ister. Maksimum veya minimum yapılmak istenen fonksiyona, amaç
fonksiyonu adı verilir. Doğrusal programlama modelinden beklenen sonucun alınabilmesi için, amacın açık olarak bilinmesi ve nicel olarak yazılımı gerekmektedir. Modelin amaç fonksiyonu yazılırken;
Karar değişkenleri: X1, X2 , ..., Xn
Birim kâr veya maliyet katsayıları c1,c2,….,cj,…,cn ile gösterildiğinde,

Amaç fonksiyonu:
Max/Min Z = c1X1 + c2X2+ … +cjXj+ … + cnXn
veya genel olarak
şeklinde de yazılabilir.

Ekonomide üretim kaynakları veya üretim faktörleri sınırlıdır. Bir işletmenin elindeki makine kapasitesi, teknolojisi, işgücü, enerji, sermaye, hammadde, yarı mamul madde, malzeme gibi üretim faktörleri ile
ürünlerine olan talep de sınırlıdır. Dolayısıyla karar değişkenlerinin miktarı da sınırlı olacaktır. Önemli olan, bu kısıtlayıcılar altında amaç fonksiyonunu sağlayan ürünler üretmektir.

Bir karar problemi için model geliştirme öncesinde amacın, karar değişkenlerinin ve parametrelerin tanımlanmış olması gerekir.

Doğrusal programlama işletmelerde minimum maliyetli işgücü gereksinimini karşılamada, eğitim öğretim planlaması gibi konularda etkin şekilde kullanılmaktadır.

Diyet günlük tüketilen yiyecek ve içeceklere verilen genel bir isimdir. Diyet problemi, sağlık için gerekli temel besinleri karşılayacak en ekonomik diyet ne olmalıdır? Şeklindedir. Bir başka ifade ile türlü yiyecek ve içeceklerden en uygununun seçimidir. Doğrusal programlama ile modellenip, çözülen
ilk ekonomik problemden biri de diyet problemidir. İlk önceleri diyet probleminin, sayısal bir örneği alınarak çözümü araştırılmış, daha sonra beslenmeyle ilgili ilginç uygulamaları yapılmıştır. Günümüzde toplu beslenme yerlerinde (öğrenci veya işçi yemekhanelerinde), büyük şantiyelerde, gemi-denizaltı vb. yerlerde beslenme planlaması doğrusal programlama ile yapılmaktadır.

Günümüz işletmeleri ürün ve hizmetlerini müşterilerine tanıtmak ve talebi artırmak için etkin reklam kampanyaları yürütürler. Reklamın amacına ulaşmasına yönelik olarak, etkili olacak reklam seçiminde doğrusal programlama kullanılmaktadır.

Çözüm: Karar değişkenleri:
X1 : üretilecek önlük miktarını,
X2 : üretilecek tulum miktarını, göstersin.

Amaç fonksiyonu;
Max Z = 10 X1 + 20X2
(Toplam kar. Üretilecek X1 adet önlük ve X2 adet tulumdan elde edilecek karların toplamı.)

Kısıtlayıcılar
2X1 + 4X2 ≤ 200 (kumaşkısıtı)
3X1 + 4X2 ≤ 200 (iş gücü kısıtı)
ve X1,X2 ≥ 0

Doğrusal programlama tarım sektöründe çiftçiler için en önemli problem olan en çok karı sağlamak için eldeki arazinin ürün türlerine göre taksimi nasıl olması gerektiği ve arazinin üretim verimliliğinin bilinmesi halinde, hangi üründen ne kadar üretim elde edilebileceğinin belirlenmesinde kullanılabilmektedir..

Çözüm: Karar değişkenleri:
X1 : mısır ekilecek arazi(dönüm) miktarını,
X2 : fasulye ekilecek arazi(dönüm) miktarını,
X3 : karpuz ekilecek arazi(dönüm) miktarını, göstersin.
Amaç karın maksimizasyonu olduğundan, öncelikle çiftçinin üreteceği üç ürün için birim karlarının
bulunması gerekmektedir.
Mısır kâr = (4/kg × 100kg/dönüm) – 4TL/kg × 20 kg/dönüm- 30/gün × 2 gün/dönüm
= 400– 80– 60 = 260TL/dönüm
Fasulye kâr = (3/kg × 160kg/dönüm) -3TL/kg × 10 kg/dönüm- 30TL/gün ×8/10 gün/dönüm
= 480– 30– 24 = 434/dönüm
Karpuz kâr = (0,30/kg × 2000kg/dönüm) – 3TL/kg × 5 kg/dönüm– 30TL/gün ×12/10 gün/dönüm
= 600– 15– 36 = 549TL/dönüm
Amaç fonksiyonu;
Max Z = 260X1 + 434X2 +549X3
Kısıtlayıcılar
X1 + X2 + X3 ≤ 200 (arazi kısıtı)
20X1 + 8X2 +12X3 ≤ 1000 (20 işçi × 10 saat × 5 gün) (iş gücü kısıtı)
ve X1, X2, X3≥ 0

Doğrusal programlama probleminin matematiksel modelini tamamlamak için her bir karar değişkeninin
negatif olmama varsayımını sağlaması gerekir. Karar değişkeni Xj’nin sadece pozitif değerli olduğu
varsayılırsa , “ Xj ≥ 0” işaret kısıtı modele eklenir.
Xj ≥ 0 (j=1,2, … n)
Şimdi doğrusal programlama modelinin matematiksel yazılımı aşağıdaki gibi olacaktır.
Max/Min Z = c1X1 + c2X2+ …… + cnXn
Kısıtlayıcılar
a11X1+a12X2+ … +a1nXn ≤ b1
a21X1+a22X2+ … +a2nXn ≤ b2

Kısıtlayıcıların sağ taraf sabitlerini oluşturan bi’ler elverişli kaynak
miktarını gösterir. Bu kaynak miktarları kısıtlayıcı fonksiyonuna göre her zaman sınırlı olmaz. Bazen karar değişkenlerinin istediğinden fazla veya tam eşitlikte olabilir. Bu nedenle kısıtlayıcı denklemler, “=” eşitlik şeklinde olabileceği gibi, eşitsizlik şeklinde de olabilir. Eşitsizlik durumu,  “≤” (küçük eşit) şeklinde olabileceği gibi, “≥” (büyük eşit) şeklinde de olabilir.

ai1X1+ai2X2+… +aijXj+… +ainXn ≥ bi
veya
ai1X1+ai2X2+… +aijXj+… +ainXn = bi