YÖNEYLEM ARAŞTIRMASI I - Deneme Sınavı - 18

Doğrusal programlama probleminin uygun çözüm alanı her zaman kapalı (veya açık) yarı uzayların kesişimi şeklinde verildiğinden, ve bu yarı uzaylar her zaman dışbükey küme olduklarından, onların kesişimi de dışbükeydir. a şıkkındaki cevap her zaman doğru olmayabilir, zira bir doğrusal programlama probleminin en iyi çözümler kümesi, iki uç noktayı birleştiren doğru parçası üzerindeki sonsuz sayıda noktayı içerebilir ve bu noktalar da uç nokta olamayabilir. Ayrıca, uygun çözüm alanı boş küme iken hiç bir uç nokta içermez.

Soruda tarif edilen küme, tepe noktaları (-1, 0), (0, 1) ve (1, 0) noktalarında olan bir üçgeni belirtir. Tepe noktaları aynı zamanda bu kümenin uç noktaları olacaktır.

Soruda verilen küme grafik olarak gösterildiğinde, bir tanesi (1, 0) ve (0, 1) noktalarından, diğeri de (-1, 0) ve (0, 1) noktalarından geçen doğruların alt taraflarında kalan yarı uzayların kesişmesinden oluştuğu görülmektedir. Bu yarı uzayların her biri dışbükey olduklarından, onların kesişimi de dışbükey bir küme olacaktır. Bu doğrular tek bir noktada kesiştiğine göre doğal olarak, bu kesişme noktası da bu kümenin tek uç noktası olacaktır.

Bu problemin amaç fonksiyonunu belirleyen z=x1 + x2 doğruları, uygun çözüm alanının bir kenarını belirleyen x1 + x2 =1 doğrusuna paralel olduğundan bu doğrunun uygun çözüm alanı içinde kalan parçasının tamamı bize en iyi çözümler kümesini verecektir. Bu durumda problem sonsuz sayıda optimum çözüme sahip olup, bu çözümler kümesi (0, 1) ve (1, 0) noktalarını birleştiren doğru parçasıdır.

Bu problemin amaç fonksiyonunu tanımlayan x1 + x2 = z doğru denklemlerinin sağ tarafı, uygun çözüm alanı sınırsız bir küme olduğundan, uygun çözüm alanında sınırsız olarak artmaktadır. Bu yüzden problem en iyi çözüme sahip olmamaktadır.

Problemin amaç fonksiyonu minimizasyon şeklinde verildiğinden, bu fonksiyonu belirleyen doğruyu, amaç fonksiyonunun normal vektörü olan (1, 2) vektörünün tersi yönünde, uygun çözüm alanını terk edinceye kadar kaydırırsak, bu doğru uygun çözüm alanını (1, 0) noktasında terk eder.

Bir çö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

Bir temel çözümde, tüm değişkenler sıfırdan büyük veya eşit 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.

Birden fazla değişkenin katsayısı pozitif ise en büyük olanı alınır, iki tane aynı değer var ise herhangi birisi alınır

Önce Temel değişkenler, temel olmayan değişkenler cinsinden ifade edilir. Sonra Temel değişkenlerin değerleri amaç fonksiyonunda yerine konur. Daha sonra Temele alınacak ve amaç fonksiyonunun değerini iyileştirecek bir değişken aranır. En son Temelden çıkan değişken sıfır değerini alırken, temelde kalan pozitif değer alır.

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 denip, bu durumda bilinen Simpleks Algoritması’nın özel bir hali uygulanır.

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. Basitçe 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.

2 denklem (m=2) ve 4 değişkenin (n=4) olduğu bir sistemde, her seferinde 2 (n-m=2) değişkene sıfır değerini vererek, denklem sayısı (m=2) kadar değişken için çözüm bulunabilir. Burada, sıfır değeri verilen değişkenlere temel dışı denir.

En küçük negatif değer -5'tir, bu yüzden bu değer temele alınmalıdır.

Simpleks algoritma bir doğrusal programlama probleminin uygun çözüm alanında en iyi çözümü bulmak üzere tasarlanmıştır.

Bir doğrusal programlama probleminin amaç fonksiyonu, enbüyükleme veya enküçükleme şeklinde tanımlanabileceğinden, doğru cevap, E şıkkında tarif edilmiştir.

Birden fazla seçenek çözüm söz konusu değilse, bir problem de yok demektir.

Problemin varlığının ortaya konması ve doğru tanımlanması, çözüm sürecinde en önemli aşamadır.

doğru çözüm e) şıkkıdır.

Doğru çözüm a) şıkkıdır.