YÖNEYLEM ARAŞTIRMASI - Deneme Sınavı - 4

İki düğüm arasındaki yönlendirilmemiş yol

Döngü

Alan Turing 1955-1962 yılları arasında en kısa yol algoritmaları yayımlamış araştırmacılardan biri değildir

Bir ağ, noktalar kümesi ile bu kümedeki bazı noktaları birleştiren çizgilerden oluşur. Bu noktalara ağın düğüm noktaları veya tepe noktaları denir.

Döngülerin olmadığı bir ağa ağaç denir.

Tüm düğüm noktaları ikişer ikişer bağlı olan ağa, yani herhangi iki düğüm noktasının en az bir yönlendirilmemiş yol ile bağlantılı olduğu ağa bağlı ağ denir.

Başlangıç düğüm noktasından son düğüm noktasına, toplam maliyeti en küçük kılacak yolun bulunması problemine „en kısa yol problemi“ denir.

Ağlar üzerinde tanımlanmış en kısa yol problemlerinin çözümü için çok sayıda algoritma geliştirilmiştir. Bu algoritmaların en sadesi, bu problemleri ilk kez inceleyen bilim insanının adını taşıyan Dijkstra algoritmasıdır.

Ağlar üzerinde en kısa yol problemi, aslında en kısa uzaklığa sahip yol, en kısa süreli yol veya en düşük maliyetli yol olarak da tanımlanabilecek problemlerin ortak adı olup probleme göre yorum farklılığı taşısa da çözüm yöntemi açısından bir farklılık göstermemektedir.

Belirlenmiş keyfi bir düğüm noktasından, ağdaki tüm düğüm noktalarına erişim sağlanacak şekilde bir ağ oluşturmak ve bu ağı belirleyecek kenarlara atanmış uzaklıkların toplamını en küçük kılacak kapsayan ağacı bulmak amacına sahip problemelere „en küçük kapsayan ağaç problemi“ denir.

En küçük kapsayan ağacın bulunması için etkin bir algoritma J. B. Kruskal (1956) ve R. C. Prim (1957) tarafından önerilmiştir.

Her iki problemde de toplam maliyeti en küçükleyecek şekilde belirli özelliğe sahip kenarların seçilmesi talep edilmektedir. En kısa yol probleminde bu özelliğin başlangıç ve son olarak nitelendirilen düğüm noktaları arasındaki bir yol için sağlanması istenirken, en küçük kapsayan ağaç probleminde tüm düğüm noktalarını birbirine bağlayan yollar için sağlanması istenmektedir.

Tamsayı programlama modeli, bir veya daha fazla karar değişkeninin sadece tamsayı değerlerine sahip olması haricinde, doğrusal bir programlama modeline özdeş olan matematiksel temsile sahip bir modeldir.

Bir problemi TP problemi yapan unsur, karar değişkenlerinin “tamsayı” olarak
tanımlanmasıdır.

Saf Tamsayılı Programlama Problemleri: Karar değişkenlerinin tümünün alması gereken değerlerin tamsayı olduğu karar problemleridir.

Karar değişkenlerinin bir kısmının tamsayı, diğer kısmının da reel değer aldığı karar problemleridir. Örneğin, gazlı içecek üreten bir firma ilgili planlama döneminde en düşük maliyetle hangi içecek türünden, ne kadar miktarda üreteceğini araştırabilir. İlgili problemde hangi içecek türünün üretilip üretilmeyeceğini belirleyen karar değişkeni yj 0-1 ve üretim miktarını belirleten xj de negatif olmayan karar değişkenidir.

Kampa giderken alınacak çantaya neler konulacağını belirleme yöneylem kullanmak değildir. Ancak, bu eşyalarının her birinin belli hacmi, ağırlığı ve önemi olan eşyalardan hangilerini konması gerektiğinin hesaplanması yöneylem kullanımına bir örnek olabilir.

Firmalar belirlenen bir planlama dönemi boyunca bütçeleri sınırlı olduğu için, n tane aday projenin hepsini yatırım yapmak üzere seçememektedir. Dolayısıyla firma bütçesi aşılmayacak şekilde n tane projeden, toplam geliri en büyükleyecek
olanların seçimi sermaye bütçeleme problemi olarak tanımlanır.

Ürün Karması Belirleme Problemi, Hangi üründen ne kadar miktarda üretileceğinin belirlendiği ürün karması problemi bir saf tamsayılı programlama problemidir.

Küme kapsama problemi özellikle lojistik alanında karşılaşılan bir yöneylem araştırması problemidir. Belirli bir bölgede (şehir, mahalle vb.) hizmet verilecek tüm konumları kapsayacak bir dizi potansiyel konum vardır. Her bir potansiyel konumun, o konumda hizmet verilecek tesisin açılması için bir başlangıç yatırım maliyeti vardır. Bu nedenle, maliyeti en aza indirecek şekilde, tüm hizmet konumlarına hizmet verecek en az sayıda potansiyel konumu belirlemek amaçlanır.