Yöneylem Araştırması Dersi 4. Ünite Sorularla Öğrenelim

Temel ve temel dışı değişkenleri tanımlayınız.

m denklem ve n değişkenin olduğu (mxn’lik ve m<n) bir sistemin çözümünde, diğer (n-m) tane değişken sıfır değerini almak üzere, ancak denklem sayısı (m) kadar değişkene değer bulunabilir. Burada sıfır değeri verilen değişkenlere temel dışı, değer alması için çözüme alınan değişkenlere ise temel değişken denir.

Analitik yöntemde problemin en iyi çözümü nasıl bulunur?

Analitik yöntem, kısıtları eşitlik haline getirilmiş bir denklem sisteminin belirtilen şekilde tüm çözümlerini elde ederek  içlerinden temel uygun çözüm (uç nokta) olanlarını bulmaktadır. Temel uygun çözüm olma özelliği sağlayanlar arasından amaç  fonksiyonu değerini eniyileyen, problemin eniyi çözümünü verecektir.

Temel çözümü ve temel uygun çözümü tanımlayınız.

Temel dışı değişkenler sıfır iken temel değişkenler için bulunan çözüme temel çözüm denir. Bir temel çözümde tüm temel değişkenler sıfır veya sıfırdan büyük değer aldıysa bu çözüme bir temel uygun çözüm denir.

Simpleks Algoritmasının çözüm bulmada izlediği yolu açıklayınız.

Simpleks Algoritması, grafik ve analitik yöntemlerin uygulamadaki güçlüklerini taşımayan, ardışık sayısal çözüm tekniği sınıfında bir yöntemdir. Basitce izlediği yol, bir uç noktadan başlayarak amaca göre daha iyi çözüm verecek başka bir uç noktaya geçmek (eğer varsa) ve istenen yönde iyileşmenin olmadığı durumda da durmaktır. Simpleks Algoritması ile problemin denklem sistemini çözen, uç nokta olsun olmasın tüm noktalarını bulmak gerekmediği gibi, sadece uç noktaların bile tümünün sınanmasına gerek kalmayabilmektedir. Algoritma, her adımda, uygun çözüm alanının bir uç noktasını bulup irdelemekte ve bu noktanın eniyi çözüm olup olamayacağını sınamaktadır. Nokta eniyi çözüm değilse, amaca göre daha iyi bir çözüm verecek izleyen uç noktayı bulur. 

AX=b şeklindeki, doğrusal bağımsız vektörlerden oluşan, 3 denklem ve 7 değişkenin olduğu bir sistemin çözümünde kaç değişkene sıfır vererek diğer değişkenlere değer bulabiliriz?

AX=b şeklindeki, doğrusal bağımsız vektörlerden oluşan, m denklem ve n değişkenin olduğu (mxn’lik ve m<n) bir sistemin çözümünde, diğer (n-m) tane değişken sıfır değerini almak üzere, ancak denklem sayısı (m) kadar değişkene değer bulunabilir.

Bu durumda bizim sorumuzda; 7-3=4 değişkene sıfır verilerek 3 değişkene değer bulunabilir

2x₁ + x₂ + 5x₃ + 3x₄ = 9

3x₁ + 2x₂ + 4x₃ + x₄ = 11 

Denklem sistemi için x₁ ve x₃ temelde, x₂ ve x₄ temel dışı değerde iken karşı gelen temel çözümü hesaplayınız.

x₁ ve x₃ temelde, x₂ ve x₄ temel dışı değerde (=0) ise denklemler şu şekilde olacaktır:

2x₁ + 5x₃ = 9

3x₁ + 4x₃ = 11      Birinci denklemi (-3) ile ikinci denklemi 2 ile çarpalım.

-6x₁ - 15x₃ = -27

6x₁ + 8x₃ = 11

==>

-7x₃ = -16

==>

x₃ = 16/7

x₁ = 205 / 42

Dejenere çözümü tanımlayınız.

Bir temel çözümde, tüm değişkenler  sıfıra eşit veya sıfırdan büyük olmakla birlikte, temelde olduğu halde sıfır değerini alan bir değişken var ise, elde edilen çözüme dejenere (bozulmuş) çözüm denir.

Simpleks tabloda x₀ ile gösterilen satır hangi bilgiyi içerir?

Böyle bir tabloda x₀ ile gösterilen satır amaç fonksiyonuna karşılık gelir.

Karar modellerinin çözümü için geliştirilmiş yazılımlara örnekler veriniz.

• LINDO
• LINGO
• GAMS gibi yazılımlar karar modellerinin çözümü için geliştirilmiştir.

Enküçükleme problemi için eniyilik koşullarının sağlandığının simpleks tablodaki göstergesi nedir?

Enküçükleme problemi için eniyilik koşullarının sağlandığının göstergesi x₀ satırında, temelde olmayan değişkenlerin hiç birisi için pozitif değerin olmamasıdır.

Kısıtları eşitlik haline getirildiğinde A katsayılar matrisinde birim matris içermeyen durumlarda izlenecek yol nedir?

Her probleme karşı gelen matematiksel model, kısıtları eşitlik haline getirildiğinde A’da birim matris içermeyebilir. Bu gibi durumlarda denklem sistemine başlangıç çözüme karşı gelmek üzere, birim matrisi oluşturacak şekilde, gerektiği sayıda yeni değişken eklenir ve Simpleks Algoritması’nın özel bir hali kullanılır.

X* = (0, 1/2, 3)

X** = (-2, 0, 1)

X*** = (1, 1, 0)

Yukarıda verilen çözümlerin hangisi ya da hangileri temel uygun çözümdür?

X* ve X*** temel uygun çözüm ve uç noktadır. 

X** ise negatif değer içerdiği için temel uygun çözüm değildir.

Amaç fonksiyonunu veren ifadede kısıtların bulunması (? , ? gibi) durumunda modelin Simpleks Algoritmasında çözülebilmesi için neler yapılır?

Modelin Simpleks Algoritması ile çözülebilmesi için önce kısıtların eşitlik haline getirilmesi gerekir.  ? (? ) şeklindeki kısıtların eşitlik haline getirilmesi için kısıtın küçük (büyük) olan tarafına yeni bir değişken eklentisi gerekir.

Aylak değişken ve artık değişkeni tanımlayınız.

Kısıt içeren bir amaç fonksiyonu olduğunda; modelin Simpleks Algoritması ile çözülebilmesi için önce kısıtların eşitlik haline getirilmesi gerekir. ?  ( ?) şeklindeki kısıtların eşitlik haline getirilmesi için kısıtın küçük (büyük) olan tarafına yeni bir değişken eklentisi gerekir

Modeli eşitlik haline getirmek için bu şekilde eklenen değişkenlere aylak (? kısıtı için) ve artık (? kısıtı için) değişken denir.

Simpleks Algoritmalarda yapay değişkeni tanımlayınız.

Simpleks Algoritması’nı uygulayabilmek için verilen denklem sisteminin kısıtlarının eştlik haline getirilmesi gerekir. Bu durumda m denklem ve n değişkenli AX=b sisteminde mxm’lik bir birim matris varsa, karşı gelen değişkenler başlangıç temel değişkenler olarak alınırlar. Öte yandan birim matrisin denklem sistemi eşitlik haline getirildiğinde kendiliğinden elde edilmediği durumlarda, sisteme, gerektiği kadar yeni değişken eklentisiyle bu eksiklik giderilmektedir. Bu tür değişkenlere yapay değişken denir. 

Simpleks Tablolarda x₀ satırının altında kaç tane satırın yer alacağı nasıl belirlenir?

Modeldeki kısıt sayısı kaç ise tabloda, x₀ satırının alt kısmında o kadar sayıda satır yer alır.

Ardıştırma işleminin aşamalarını yazınız.

Ardıştırma;

1. Bir çözümün eniyi çözüm olmaması halinde temele girecek ve çıkacak olan değişkenlere karar verme,
2. Temele girecek değişkenin tabloda kısıtlar bölümüne karşı gelen kısmındaki katsayılarının birim matrisin ilgili sütununa dönüştürülmesi
3. x₀ satırında karşı gelen değerinin sıfırlanması aşamalarından oluşur.

Simpleks tabloya bakarak problemin sınırsız çözümü olup olmadığı nasıl belirlenir?

Temele girecek değişkenin bulunduğu sütunda, x₀ satırı dışındaki değerlerin tümü ? 0 ise problemin sınırsız çözümü var demektir.