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. 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. 

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

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.

Karar değişkenlerine kontrol edilebilen değişkenler denir. İstatistikte değişken Xi-tesadüfi değişkendir ve serbestçe değerler alabilen değişken olarak tanımlanır.

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.

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.

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.

Algoritma: Problem çözümünde izlenen yol olarak isimlendirilebilir.

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.

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.

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.

Doğrusal programlamanın en yaygın kullanıldığı alanlardan birisi, üretim işletmelerin de maksimum karlı veya minimum maliyetli üretim bileşenlerini belirlemede kullanılmasıdır.

Örnek 2.1. Bir marangoz işletmesi masa ve sandalye üretmektedir. Bir masa yapımı için 30 metre tahtaya ve 5 saat iş gücüne gerek vardır. Bir sandalye yapımı için de 20 metre tahtaya ve 10 saat iş gücüne gerek vardır. İşletmenin elinde 300 metre tahta ile 110 saat iş gücü vardır. Ayrıca bir masanın satışından elde edilen kâr
6 ve bir sandalyenin satışından elde edilen kâr
8’dir. İşletmenin amacı maksimum kara ulaşmaktır. Buna göre marangoz işletmesi ne kadar masa ve sandalye üretmelidir. Problemi doğrusal programlama modeli olarak ifade ediniz.

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

Amaç fonksiyonu; Max Z = 6 X1 + 8 X2 (Toplam kar. Üretilecek X1 adet masa ve X2 adet sandalyeden elde edilecek karların toplamı.) Kısıtlayıcılar 30X1 + 20X2 ? 300 (tahta kısıtı) 5X1 + 10X2 ? 110 (iş gücü kısıtı) ve X1,X2 ? 0

Tarım sektöründe çiftçiler için en önemli problem, en çok karı sağlamak için eldeki arazinin ürün türlerine göre taksimi nasıl olmalıdır? Ayrıca arazinin üretim verimliliğinin bilinmesi halinde, hangi üründen ne kadar üretim elde edilebileceği de belirlenebilmektedir.

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

Örnek: Eskişehir’de 4 perakende dükkânından oluşan bir dükkân zincirinin reklam yöneticisi 2 medya seçeneğini göz önünde tutuyor. Biri yerel bir gazetede yarım sayfalık ilanlar, diğeri TVA’ daki reklamlardır. Reklam yöneticisi reklama maruz kalma oranının reklam kampanyasının sonunda şehir merkezinde en az %40, il genelinde de en az % 60 olmasını istiyor.

Söz konusu TV reklamı başına bu oran şehir civarında %5, il genelinde %3’tür. Yarım sayfalık gazete ilanı başına bu oran şehir merkezinde %4, il genelinde %3’tür. Yarım sayfalık gazete ilanının maliyeti
9.250, televizyon reklamının maliyeti
20.000‘dır.

Amaç arzulanan hedefi karşılayacak en az maliyetli reklam stratejisini seçmektir. Doğrusal programlama modelini kurunuz.

Çözüm: Karar değişkenleri;

X1 : Yarım sayfalık gazete ilanı sayısı (kaç gün çıkacak)

X2 : TV reklamı sayısı

Amaç fonksiyonu;

Min Z = 9.250X1 + 20.000X2

Kısıtlayıcılar

0,05X1 + 0,04X2 ? 0,40

0,03X1 + 0,03X2 ? 0,60

ve X1, X2 ? 0

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.

Doğrusal programlama modeli kurulurken amacın, değişkenler arasında ilişkilerin ve kullanılacak kıt kaynakların tanımlanması gerekir.