Doğrusal Programlama Alıştırma Soruları — KPSS İstatistik

Soru 1Soru →

Bir finansal analist, bir yatırım portföyünün getirisini maksimize etmek için üç farklı karar değişkenine ( $x_1, x_2, x_3$ ) bağlı aşağıdaki doğrusal programlama primal modelini oluşturmuştur:

\text{Maksimum } Z = 8x_1 - 3x_2 + 5x_3

Kısıtlar:

2x_1 + 4x_2 - x_3 \le 15

3x_1 - 2x_2 + 2x_3 = 20

x_1 + 5x_2 + 3x_3 \ge 10

x_1 \ge 0, \quad x_2 \le 0, \quad x_3 \text{ işaretsiz}

Buna göre, bu primal modele ait dual model aşağıdakilerden hangisidir?

\begin{aligned} &\text{Min } W = 15y_1 + 20y_2 + 10y_3 \\ &2y_1 + 3y_2 + y_3 \ge 8 \\ &4y_1 - 2y_2 + 5y_3 \le -3 \\ &-y_1 + 2y_2 + 3y_3 = 5 \\ &y_1 \ge 0, \quad y_2 \ge 0, \quad y_3 \ge 0 \end{aligned}

\begin{aligned} &\text{Maks } W = 15y_1 + 20y_2 + 10y_3 \\ &2y_1 + 3y_2 + y_3 \le 8 \\ &4y_1 - 2y_2 + 5y_3 \ge -3 \\ &-y_1 + 2y_2 + 3y_3 = 5 \\ &y_1 \ge 0, \quad y_2 \text{ işaretsiz}, \quad y_3 \le 0 \end{aligned}

\begin{aligned} &\text{Min } W = 15y_1 + 20y_2 + 10y_3 \\ &2y_1 + 3y_2 + y_3 \ge 8 \\ &4y_1 - 2y_2 + 5y_3 \le -3 \\ &-y_1 + 2y_2 + 3y_3 = 5 \\ &y_1 \ge 0, \quad y_2 \text{ işaretsiz}, \quad y_3 \le 0 \end{aligned}

\begin{aligned} &\text{Min } W = 15y_1 + 20y_2 + 10y_3 \\ &2y_1 + 3y_2 + y_3 \ge 8 \\ &4y_1 - 2y_2 + 5y_3 \ge -3 \\ &-y_1 + 2y_2 + 3y_3 \ge 5 \\ &y_1 \ge 0, \quad y_2 \text{ işaretsiz}, \quad y_3 \text{ işaretsiz} \end{aligned}

\begin{aligned} &\text{Min } W = 15y_1 + 20y_2 + 10y_3 \\ &2y_1 + 3y_2 + y_3 \le 8 \\ &4y_1 - 2y_2 + 5y_3 \ge -3 \\ &-y_1 + 2y_2 + 3y_3 = 5 \\ &y_1 \le 0, \quad y_2 \text{ işaretsiz}, \quad y_3 \ge 0 \end{aligned}

Cevabı ve açıklamayı göster

Cevap: $\begin{aligned} &\text{Min } W = 15y_1 + 20y_2 + 10y_3 \\ &2y_1 + 3y_2 + y_3 \ge 8 \\ &4y_1 - 2y_2 + 5y_3 \le -3 \\ &-y_1 + 2y_2 + 3y_3 = 5 \\ &y_1 \ge 0, \quad y_2 \text{ işaretsiz}, \quad y_3 \le 0 \end{aligned}$

Cevap

Doğru model, amaç fonksiyonunun minimize edildiği, dual değişken işaretlerinin kısıt yönlerine göre (

y_1 \ge 0

,

y_2

işaretsiz,

y_3 \le 0

) belirlendiği ve dual kısıtların primal değişken işaretleriyle uyumlu olarak (

\ge

,

\le

,

=

) kurulduğu seçenektir.

Doğru cevapta primal modeldeki kısıt ve değişken işaretleri dual kurallarına eksiksiz dönüştürülmüştür. Maksimizasyon modelinden minimizasyona geçerken <= kısıtı >=0 değişkenine, = kısıtı işaretsiz değişkene, >= kısıtı ise <=0 değişkenine dönüşür. Aynı şekilde x_1>=0 değişkeni >= kısıtına, x_2<=0 değişkeni <= kısıtına, x_3 işaretsiz değişkeni ise = kısıtına karşılık gelmektedir.

Adım Adım Çözüm

1

Amaç fonksiyonunu belirleme.

Min W = 15y_1 + 20y_2 + 10y_3

Primal model Maksimum olduğundan, dual model Minimum olmalıdır. Primal sağ taraf sabitleri dual amaç fonksiyonu katsayıları olur.

2

Dual değişken işaretlerini belirleme.

y_1 \ge 0, y_2 işaretsiz, y_3 \le 0

Primal (Maks) modelde kısıt işaretleri sırasıyla <=, = ve >= olduğundan, dual değişkenler kurallara göre şekillenir.

3

Dual kısıt yönlerini belirleme.

1. kısıt \ge, 2. kısıt \le, 3. kısıt =

Primal değişkenler x_1 \ge 0, x_2 \le 0 ve x_3 işaretsiz olduğundan, Min dual modelde kısıtlar sırasıyla \ge, \le ve = yönlerinde olur.

4

Dual kısıt denklemlerini yazma.

2y_1+3y_2+y_3 \ge 8, \quad 4y_1-2y_2+5y_3 \le -3, \quad -y_1+2y_2+3y_3 = 5

Primal katsayılar matrisinin transpozu alınarak ve 3. adımdaki yönler kullanılarak dual kısıtlar oluşturulur.

Anahtar Kavram

Doğrusal programlamada asimetrik ve simetrik kuralları barındıran tam dualite dönüşümü (Dual Model Kurulumu)

Soru 2Soru →

Bir maksimizasyon problemi için oluşturulan başlangıç Simpleks tablosu aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm ( $RHS$ )
$s_1$	$2$	$-3$	$1$	$0$	$10$
$s_2$	$1$	$-1$	$0$	$1$	$20$
$Z_j - C_j$	$-2$	$-5$	$0$	$0$	$0$

Bu tabloya göre, söz konusu doğrusal programlama modelinin çözüm süreci ve sonucu ile ilgili aşağıdakilerden hangisi söylenebilir?

Modelin sınırsız (unbounded) çözümü vardır.

Modelin birden fazla (çoklu) optimal çözümü mevcuttur.

Modelin uygun bir çözüm kümesi yoktur (uygunsuzluk).

Modelde dejenere (yozlaşmış) bir çözüm oluşmuştur.

Tablo optimaldir ve amaç fonksiyonu değeri 0'dır.

Cevabı ve açıklamayı göster

Cevap: Modelin sınırsız (unbounded) çözümü vardır.

Cevap

Modelin sınırsız (unbounded) çözümü vardır; çünkü temele girecek değişkenin katsayıları oran testi yapılmasına izin vermeyecek şekilde negatif değerlerden oluşmaktadır.

Verilen Simpleks tablosunda amaç satırındaki en negatif değer

-5

olup

x_2

değişkenine aittir.

x_2

sütunundaki kısıt katsayıları ise

-3

ve

-1

şeklindedir. Bir maksimizasyon probleminde, temele girmesi gereken bir değişkenin sütununda hiç pozitif katsayı bulunmaması, o değişkenin değerinin sonsuza kadar artırılabileceği ve dolayısıyla amaç fonksiyonunun da sınırsızca büyüyeceği anlamına gelir. Bu durum 'sınırsız çözüm' (unboundedness) olarak tanımlanır.

Adım Adım Çözüm

1

Temele girecek (anahtar sütun) değişkenin belirlenmesi

x_2

değişkeni temele girmelidir.

Maksimizasyon problemlerinde amaç satırındaki (

Z_j - C_j

) en küçük negatif değer (

-5

) temele girecek değişkeni belirler.

2

Çıkan değişkenin (anahtar satır) belirlenmesi için oran testi yapılması

Pozitif bir oran elde edilememiştir (

10/(-3)

ve

20/(-1)

).

Çıkan değişkeni belirlemek için

RHS

değerleri, anahtar sütundaki pozitif katsayılara bölünmelidir. Sütundaki tüm katsayılar

\leq 0

ise bu test yapılamaz.

3

Özel durumun teşhis edilmesi

Sınırsızlık (Unboundedness) durumu teşhis edilmiştir.

Bir değişken amaç fonksiyonunu iyileştirmek için temele girmek istiyor ancak kısıtlar bu değişkenin artışını sınırlamıyorsa çözüm sınırsızdır.

Anahtar Kavram

Simpleks yönteminde sınırsızlık durumu, temele girmesi beklenen bir değişkenin kısıt sütunundaki tüm değerlerin sıfır veya negatif olmasıyla belirlenir.

Soru 3Soru →

Aşağıda bir doğrusal programlama probleminin primal modeli verilmiştir:

\text{Maks } Z = 4x_1 + 6x_2

Kısıtlar:

Bileşen	Katsayılar ve Yön	Sağ Taraf
1. Kısıt	$3x_1 + x_2 \leq 12$	$12$
2. Kısıt	$x_1 + 2x_2 \geq 8$	$8$
Değişkenler	$x_1 \geq 0, x_2$ serbest

Bu primal modelin matematiksel olarak doğru kurulmuş dual modeli aşağıdakilerden hangisidir?

\text{Min } W = 12y_1 + 8y_2

;

3y_1 + y_2 \geq 4

,

y_1 + 2y_2 = 6

;

y_1 \geq 0, y_2 \leq 0

\text{Min } W = 12y_1 + 8y_2

;

3y_1 + y_2 \geq 4

,

y_1 + 2y_2 = 6

;

y_1 \geq 0, y_2 \geq 0

\text{Min } W = 12y_1 + 8y_2

;

3y_1 + y_2 \geq 4

,

y_1 + 2y_2 \geq 6

;

y_1 \geq 0, y_2 \leq 0

\text{Min } W = 12y_1 + 8y_2

;

3y_1 + y_2 \leq 4

,

y_1 + 2y_2 = 6

;

y_1 \geq 0, y_2 \leq 0

\text{Maks } W = 12y_1 + 8y_2

;

3y_1 + y_2 \geq 4

,

y_1 + 2y_2 = 6

;

y_1 \geq 0, y_2 \leq 0

Cevabı ve açıklamayı göster

Cevap: $\text{Min } W = 12y_1 + 8y_2$ ; $3y_1 + y_2 \geq 4$ , $y_1 + 2y_2 = 6$ ; $y_1 \geq 0, y_2 \leq 0$

Cevap

Doğru model; amaç fonksiyonunun minimizasyon olduğu, ikinci dual değişkenin negatif değer alabildiği ve ikinci dual kısıtın eşitlik durumunda olduğu seçenektir.

Verilen primal modelde maksimizasyon yapıldığı için dual model minimizasyon olmalıdır.

x_2

değişkeni serbest (unrestricted) olduğu için ona karşılık gelen ikinci dual kısıt bir eşitlik (

=

) olmalıdır. Ayrıca ikinci primal kısıt

\geq

yönünde olduğu için, maksimizasyon probleminin doğası gereği ona karşılık gelen dual değişken

y_2 \leq 0

olmalıdır.

Adım Adım Çözüm

1

Amaç fonksiyonunu belirleme

\text{Min } W = 12y_1 + 8y_2

Primal modelin sağ taraf sabitleri (

12, 8

), dual modelin amaç fonksiyonu katsayıları olur ve maksimizasyon minimizasyona dönüşür.

2

Dual kısıtları oluşturma

3y_1 + y_2

ve

y_1 + 2y_2

Primal kısıt matrisinin transpozu alınarak dual kısıtların sol tarafları oluşturulur.

3

Dual kısıt sağ taraflarını ve yönlerini belirleme

3y_1 + y_2 \geq 4

ve

y_1 + 2y_2 = 6

x_1 \geq 0

olduğu için 1. dual kısıt

\geq 4

(amaç katsayısı) olur.

x_2

serbest olduğu için 2. dual kısıt

= 6

olur.

4

Dual değişkenlerin işaret sınırlamalarını belirleme

y_1 \geq 0

ve

y_2 \leq 0

Maksimizasyon probleminde

\leq

kısıtı (1. kısıt) pozitif değişken (

y_1 \geq 0

),

\geq

kısıtı (2. kısıt) ise negatif değişken (

y_2 \leq 0

) üretir.

Anahtar Kavram

Simetrik olmayan dualite kuralları

Daha Fazla Pratik

Dual modelin tekrar dualini alarak primal modele geri dönüp dönmediğinizi kontrol edebilirsiniz.

Tahmini Süre:1m 30s

Soru 4Soru →

Doğrusal programlama modellerinin geçerli olabilmesi için temel bazı varsayımların karşılanması gerekmektedir. Bir üretim modelinde, her bir ürün biriminin amaç fonksiyonuna olan katkısının (kâr veya maliyet) ve kısıtlardaki kaynak kullanım miktarının, o ürünün üretim miktarından bağımsız olarak sabit kaldığını ifade eden varsayım aşağıdakilerden hangisidir?

Oransallık

Toplanabilirlik

Bölünebilirlik

Belirlilik

Negatif olmama

Cevabı ve açıklamayı göster

Cevap: Oransallık

Cevap

Doğrusal programlamada, birim katkıların üretim miktarından bağımsız olarak sabit kalması 'Oransallık' varsayımı ile tanımlanır.

Oransallık varsayımı, hem amaç fonksiyonunda hem de kısıt denklemlerinde her bir karar değişkeninin katkısının o değişkenin değeriyle doğru orantılı olduğunu ifade eder. Yani, bir birim üretimin kârı

5

TL ise,

10

birimin kârı kesinlikle

50

TL olmalıdır (ölçek ekonomisi veya miktar indirimi olmadığını varsayar).

Adım Adım Çözüm

1

Problemin tanımını analiz etme

Tanım, birim başına katkının sabitliğini ve toplamın miktar ile doğru orantılı değişimini vurgulamaktadır.

Soruda sorulan özelliğin hangi varsayıma karşılık geldiğini belirlemek için anahtar kelimeler (sabit birim katkı, doğru orantı) tespit edilir.

2

Temel varsayımları hatırlama

Doğrusal programlama varsayımları: Oransallık (proportionality), Toplanabilirlik (additivity), Bölünebilirlik (divisibility) ve Belirlilik (certainty).

Seçeneklerdeki kavramların tanımları ile sorudaki tanım karşılaştırılır.

3

Uygun kavramı seçme

Oransallık varsayımı,

c_j x_j

ve

a_{ij} x_j

terimlerindeki katsayıların sabitliğini garanti eder.

Tanım doğrudan Oransallık kavramını karşıladığı için doğru cevap belirlenir.

Anahtar Kavram

Oransallık Varsayımı

Soru 5Soru →

Bir maksimizasyon problemine ait başlangıç simpleks tablosu aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm (RHS)
$s_1$	2	4	1	0	12
$s_2$	3	2	0	1	12
$Z$	-5	-10	0	0	0

Buna göre, simpleks algoritmasının ilk iterasyonu tamamlandığında amaç fonksiyonunun ( $Z$ ) değeri aşağıdakilerden hangisi olur?

12

20

30

60

120

Cevabı ve açıklamayı göster

Cevap: 30

Cevap

İlk iterasyon sonunda amaç fonksiyonunun (Z) değeri 30 olur.

Simpleks yönteminde maksimizasyon problemleri için Z satırındaki en negatif katsayı sisteme girecek değişkeni (anahtar sütun) belirler. Burada -10 katsayısı ile

x_2

sisteme girer. Oran testi yapıldığında (

12/4=3

ve

12/2=6

) en küçük oran olan 3 ile

s_1

değişkeni sistemden çıkar. Yeni iterasyonda Z değeri

0 - (-10 \times 3) = 30

olarak güncellenir.

Adım Adım Çözüm

1

Anahtar sütunun belirlenmesi

Sisteme girecek değişken

x_2

olarak seçilir.

Maksimizasyon probleminde Z satırındaki en negatif katsayı (-10), sisteme girecek değişkeni belirler.

2

Oran testi ile anahtar satırın belirlenmesi

s_1

değişkeni sistemden çıkar.

Çözüm değerlerinin anahtar sütun katsayılarına oranı (

12/4 = 3

ve

12/2 = 6

) incelendiğinde, en küçük pozitif oran olan 3 değeri

s_1

satırına aittir.

3

Yeni Z değerinin hesaplanması

Yeni

Z = 30

.

Simpleks tablosu satır işlemleri sonucunda yeni Z değeri; mevcut Z değeri ile (sisteme giren değişkenin katsayısı

\times

oran testinin sonucu) çarpımının farkı alınarak hesaplanır:

0 - (-10 \times 3) = 30

.

Anahtar Kavram

Simpleks Yönteminde İterasyon ve Pivot İşlemleri

Soru 6Soru →

Bir doğrusal programlama modelinin Simpleks algoritması ile çözümü sırasında elde edilen optimal tablo aşağıda verilmiştir. Tabloda $x_1$ ve $x_2$ karar değişkenlerini, $s_1$ ve $s_2$ ise dolgu değişkenlerini temsil etmektedir.

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm (RHS)
$Z$	$0$	$0$	$0$	$4$	$120$
$x_1$	$1$	$0$	$2$	$-1$	$20$
$x_2$	$0$	$1$	$1$	$3$	$30$

Bu tabloya göre, problemin çözüm kümesinin karakteristiği hakkında aşağıdakilerden hangisi söylenebilir?

Modelin çözüm kümesi boş olup uygun çözüm yoktur.

Amaç fonksiyonu değeri sonsuza gittiği için çözüm sınırsızdır.

Modelin tek bir optimal çözüm noktası bulunmaktadır.

Modelin sonsuz sayıda optimal çözüm noktası mevcuttur.

Sağ taraf değerlerinden biri sıfır olduğu için dejenerelik durumu vardır.

Cevabı ve açıklamayı göster

Cevap: Modelin sonsuz sayıda optimal çözüm noktası mevcuttur.

Cevap

Modelin amaç satırında, temel dışı bir değişken olan dolgu değişkeninin katsayısı sıfır olduğu için modelin sonsuz sayıda optimal çözüm noktası mevcuttur.

Verilen Simpleks tablosunda amaç satırı (

Z

) incelendiğinde, temelde bulunmayan

s_1

dolgu değişkeninin katsayısının

0

olduğu görülmektedir. Optimal bir tabloda (tüm katsayılar

\geq 0

iken) temel dışı bir değişkenin katsayısının sıfır olması, bu değişkenin temele alınabileceğini ancak amaç fonksiyonu değerini (

120

) değiştirmeyeceğini gösterir. Bu durum, modelin tek bir noktada değil, bir doğru parçası veya bölge üzerinde sonsuz sayıda optimal çözüme sahip olduğu anlamına gelir.

Adım Adım Çözüm

1

Tablodaki temel ve temel dışı değişkenleri belirleme

Temel Değişkenler:

x_1, x_2

; Temel Dışı Değişkenler:

s_1, s_2

Tablonun çözüm yapısını anlamak için hangi değişkenlerin temelde olduğunu saptamak gerekir.

2

Optimallik kontrolü ve temel dışı değişkenlerin amaç satırı (

Z

) katsayılarını inceleme

Z

satırında

s_1

değişkeninin katsayısı

0

,

s_2

değişkeninin katsayısı ise

4

'tür.

Optimal bir tabloda, eğer temel dışı bir değişkenin katsayısı

0

ise, bu durum çözümün tek olmadığını gösterir.

3

Özel durumu teşhis etme

Çoklu Optimal Çözüm (Multiple Optima)

Temel dışı

s_1

değişkeninin

Z

satırındaki katsayısının

0

olması, bu değişkenin temele girmesi durumunda amaç fonksiyonu değerinin değişmeyeceğini, yani başka optimal noktaların da olduğunu gösterir.

Anahtar Kavram

Çoklu Optimal Çözüm Koşulu

Tahmini Süre:1m 30s

Soru 7Soru →

Bir kamu kurumu matbaasında iki farklı türde broşür ( $x_1$ : Bilgilendirme ve $x_2$ : Tanıtım) basılmaktadır. Kurumun her bir Bilgilendirme broşüründen elde ettiği sosyal fayda puanı 60, her bir Tanıtım broşüründen elde ettiği sosyal fayda puanı ise 80'dir. Kurum, toplam sosyal faydayı en üst düzeye çıkarmayı hedeflemektedir. Basım sürecinde kullanılan kaynaklar ve kısıtlar şöyledir:

- Bilgilendirme broşürü 3 birim kağıt, Tanıtım broşürü 5 birim kağıt tüketmektedir. Toplam kağıt stoğu 500 birimdir ve bu miktar aşılamaz.
- Bilgilendirme broşürünün basımı 2 saat, Tanıtım broşürünün basımı 2 saat sürmektedir. Toplam çalışma süresi 200 saati geçmemelidir.
- Kurumsal politikalar gereği, basılan toplam broşür sayısının en az 80 adet olması gerekmektedir.

Buna göre, bu problemin doğrusal programlama modeli aşağıdakilerden hangisidir?

\text{Maks } Z = 60x_1 + 80x_2

3x_1 + 5x_2 \leq 500

2x_1 + 2x_2 \leq 200

x_1 + x_2 \geq 80

x_1, x_2 \geq 0

\text{Min } Z = 60x_1 + 80x_2

3x_1 + 5x_2 \leq 500

2x_1 + 2x_2 \leq 200

x_1 + x_2 \geq 80

x_1, x_2 \geq 0

\text{Maks } Z = 60x_1 + 80x_2

3x_1 + 5x_2 \geq 500

2x_1 + 2x_2 \geq 200

x_1 + x_2 \leq 80

x_1, x_2 \geq 0

\text{Maks } Z = 60x_1 + 80x_2

3x_1 + 5x_2 \leq 500

2x_1 + 2x_2 \leq 200

x_1 + x_2 \leq 80

x_1, x_2 \geq 0

\text{Maks } Z = 80x_1 + 60x_2

3x_1 + 5x_2 \leq 500

2x_1 + 2x_2 \leq 200

x_1 + x_2 \geq 80

x_1, x_2 \geq 0

Cevabı ve açıklamayı göster

Cevap: $\text{Maks } Z = 60x_1 + 80x_2$
$3x_1 + 5x_2 \leq 500$
$2x_1 + 2x_2 \leq 200$
$x_1 + x_2 \geq 80$
$x_1, x_2 \geq 0$

Cevap

Sosyal faydayı maksimize eden, kağıt ve zaman sınırlarını küçük-eşit (<=) kısıtlarıyla, asgari üretim miktarını ise büyük-eşit (>=) kısıtıyla temsil eden model doğrudur.

Doğru model, fayda puanlarını (60 ve 80) maksimize etmeye yönelik amaç fonksiyonunu kurar. Kağıt (500 birim) ve zaman (200 saat) gibi kısıtlı kaynakları 'küçük-eşit' (

\leq

) olarak, broşür üretim kotasını (80 adet) ise 'en az' şartı gereği 'büyük-eşit' (

\geq

) olarak ifade eder.

Adım Adım Çözüm

1

Karar değişkenlerini tanımlayın.

x_1

: Bilgilendirme broşürü sayısı,

x_2

: Tanıtım broşürü sayısı.

Modelin temel bileşenlerini belirlemek için değişken tanımı gereklidir.

2

Amaç fonksiyonunu oluşturun.

Maks

Z = 60x_1 + 80x_2

Problem toplam sosyal faydayı en üst düzeye çıkarmayı (maksimizasyon) hedeflemektedir.

3

Kaynak kısıtlarını (kağıt ve zaman) yazın.

Kağıt:

3x_1 + 5x_2 \leq 500

; Zaman:

2x_1 + 2x_2 \leq 200

Eldeki kaynaklar sınırlıdır ve bu miktarların aşılması mümkün değildir (küçük-eşit).

4

Politika (kota) kısıtını ekleyin.

x_1 + x_2 \geq 80

Toplam üretimin 'en az' belirli bir seviyede olması istenmektedir (büyük-eşit).

5

Negatif olmama kısıtlarını ekleyin.

x_1, x_2 \geq 0

Fiziksel üretim miktarları negatif değer alamaz.

Anahtar Kavram

Doğrusal Programlama Modeli Kurma

Tahmini Süre:2m 0s

Soru 8Soru →

Aşağıdaki doğrusal programlama modeli verilmiştir:

Minimize $Z = 2x_1 + 5x_2$

Kısıtlar:
$x_1 + x_2 \geq 2$
$2x_1 + x_2 \leq 6$
$x_1, x_2 \geq 0$

Bu model Büyük-M (Big-M) yöntemi ile çözülmek istendiğinde, yapay değişkenlerin temel değişkenler arasında yer aldığı başlangıç simpleks tablosunda amaç fonksiyonu satırındaki ( $Z$ satırı) $x_1$ değişkeninin katsayısı aşağıdakilerden hangisidir?

M - 2

2 - M

M + 2

2

-M

Cevabı ve açıklamayı göster

Cevap: $M - 2$

Cevap

Başlangıç simpleks tablosundaki amaç satırında

x_1

değişkeninin katsayısı

M - 2

olur.

Minimizasyon probleminde

Z = 2x_1 + 5x_2 + Ma_1

olan amaç fonksiyonunda,

a_1 = 2 - x_1 - x_2 + s_1

eşitliği yerine yazıldığında

Z = (2-M)x_1 + (5-M)x_2 + Ms_1 + 2M

elde edilir. Simpleks tablosundaki amaç satırı formatında (

Z

terimi katsayısı 1 olacak şekilde tüm değişkenlerin sol tarafa toplanması)

x_1

değişkeninin katsayısı

-(2-M)

yani

M-2

olur.

Adım Adım Çözüm

1

Kısıtların standart forma dönüştürülmesi

x_1 + x_2 - s_1 + a_1 = 2

ve

2x_1 + x_2 + s_2 = 6

Büyük eşit (>=) kısıtı için bir artık değişken (

s_1

) ve başlangıç temel uygun çözümü sağlamak için bir yapay değişken (

a_1

) eklenmelidir.

2

Amaç fonksiyonunun ceza parametresi (M) ile kurulması

Minimize

Z = 2x_1 + 5x_2 + Ma_1

Minimizasyon problemlerinde Büyük-M yönteminde yapay değişkenler amaç fonksiyonuna

+M

katsayısı ile eklenir.

3

Yapay değişkenin amaç satırından elenmesi

Z = 2x_1 + 5x_2 + M(2 - x_1 - x_2 + s_1) \Rightarrow Z = (2-M)x_1 + (5-M)x_2 + Ms_1 + 2M

Bir değişkenin temel değişken olabilmesi için başlangıç tablosundaki amaç satırı katsayısının 0 olması gerekir; bu nedenle

a_1

değişkeni amaç fonksiyonundan yok edilir.

4

Tablo formatına (Z satırı) dönüştürme

Z + (M-2)x_1 + (M-5)x_2 - Ms_1 = 2M

Simpleks tablosunda değişkenler sol tarafa, sabitler sağ tarafa alınarak standart satır formu oluşturulur.

Anahtar Kavram

Büyük-M yönteminde yapay değişkenin amaç fonksiyonundan elenerek başlangıç tablosu katsayılarının hesaplanması.

Alternatif Yöntem

Matris formunda amaç satırı katsayılarını hesaplamak için

c_B B^{-1} A_j - c_j

formülü de kullanılabilir.

Tahmini Süre:2m 0s

Soru 9Soru →

Bir minimizasyon (en küçükleme) problemi için Simpleks algoritması kullanılarak elde edilen ve optimalite koşullarını sağlayan son tablo aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Sağ Yan ( $RHS$ )
$Z$ (Amaç)	$0$	$0$	$-4$	$0$	$120$
$x_1$	$1$	$2$	$0,5$	$0$	$10$
$s_2$	$0$	$1$	$-1$	$1$	$5$

Tablodaki $x_1$ ve $x_2$ karar değişkenlerini, $s_1$ ve $s_2$ ise dolgu/artık değişkenleri temsil etmektedir. Bu tabloya göre, söz konusu doğrusal programlama modelinin çözüm kümesi hakkında aşağıdakilerden hangisi söylenebilir?

Modelin birden fazla (alternatif) optimal çözümü vardır.

Modelin çözüm kümesi sınırsızdır (unbounded).

Modelin uygun bir çözüm kümesi yoktur (uygunsuzluk).

Modelde dejenerelik (yozlaşma) durumu mevcuttur.

Modelin tek bir optimal çözüm noktası vardır.

Cevabı ve açıklamayı göster

Cevap: Modelin birden fazla (alternatif) optimal çözümü vardır.

Cevap

Modelin birden fazla (alternatif) optimal çözümü bulunmaktadır.

Verilen optimal Simpleks tablosunda, temelde yer almayan (non-basic)

x_2

değişkeninin amaç fonksiyonu satırındaki (

Z_j - C_j

) katsayısı

0

olarak görülmektedir. Bir minimizasyon probleminde optimalite sağlandıktan sonra temel dışı bir değişkenin katsayısının

0

olması, o değişkenin çözüme dahil edilmesi durumunda amaç fonksiyonu değerinin değişmeyeceğini ancak değişken değerlerinin değişeceğini gösterir. Bu durum, problemin birden fazla optimal çözüme (alternatif optima) sahip olduğu anlamına gelir.

Adım Adım Çözüm

1

Problemin tipini ve optimalite durumunu kontrol et.

Problem bir minimizasyon problemidir ve amaç satırındaki (

Z_j - C_j

) tüm değerler

\leq 0

olduğundan tablo optimaldir.

Minimizasyon problemlerinde optimalite için amaç satırı katsayılarının pozitif olmaması gerekir.

2

Temel ve temel dışı değişkenleri belirle.

Temel değişkenler:

x_1

ve

s_2

. Temel dışı değişkenler:

x_2

ve

s_1

.

Birim matris sütunlarına sahip olan değişkenler temelde yer alır.

3

Temel dışı değişkenlerin amaç satırı katsayılarını incele.

Temel dışı olan

x_2

değişkeninin amaç satırındaki katsayısı

0

'dır.

Optimal bir tabloda temel dışı bir değişkenin amaç satırı katsayısının

0

olması, bu değişkenin temele girmesi durumunda amaç fonksiyonu değerinin (Z=120) değişmeyeceğini, dolayısıyla başka bir optimal noktanın daha var olduğunu gösterir.

Anahtar Kavram

Simpleks Yönteminde Çoklu (Alternatif) Optimal Çözüm Analizi

Daha Fazla Pratik

Grafik yöntemde alternatif optimal çözümlerin, amaç fonksiyonu doğrusunun bir kısıt doğrusu ile çakışması (paralel olması) durumunda ortaya çıktığını hatırlayınız.

Tahmini Süre:1m 30s

Soru 10Soru →

Bir kamu kurumunun kaynak tahsis problemini çözmek amacıyla kurulan maksimizasyon (en büyükleme) yönlü doğrusal programlama modelinde, Simpleks algoritmasının bir adımında aşağıdaki ara tablo elde edilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm (Sağ Yan Değerler)
$s_1$	2	1	1	0	10
$s_2$	4	3	0	1	20
$Z_j - C_j$	-8	-5	0	0	0

Bu tabloda, en yüksek iyileştirme potansiyeline sahip olan $x_1$ değişkeninin temele girmesine karar verilmiştir. Bu seçime bağlı olarak gerçekleştirilecek olan pivot işlemi sonucunda ortaya çıkacak özel durum aşağıdakilerden hangisidir?

Dejenerelik

Sınırsızlık

Uygunsuzluk (Çözümün olmaması)

Çoklu optimal çözüm

Gereksiz (Atıl) kısıt bulunmaması

Cevabı ve açıklamayı göster

Cevap: Dejenerelik

Cevap

Minimum oran testinde eşitlik (bağ) oluştuğu için bir sonraki iterasyonda dejenerelik durumu ortaya çıkar.

Doğrusal programlamada Simpleks yöntemi uygulanırken, temelden çıkacak değişkeni belirlemek için yapılan minimum oran testinde birden fazla satırda aynı minimum değer elde edilirse, bir sonraki iterasyonda temel değişkenlerden biri sıfır değerini alır. Temel değişkenlerden en az birinin sıfır olması durumu 'dejenerelik' (degeneracy) olarak tanımlanır.

Adım Adım Çözüm

1

Temele girecek değişkenin belirlenmesi

x_1

değişkeni temele girer.

Maksimizasyon probleminde

Z_j - C_j

satırındaki en küçük (en negatif) değer -8'dir.

2

Temelden çıkacak değişken için minimum oran testinin uygulanması

s_1

için

10 / 2 = 5

;

s_2

için

20 / 4 = 5

.

Çözüm sütunundaki değerler, temele girecek değişkenin sütunundaki pozitif katsayılara bölünür.

3

Oran sonuçlarının yorumlanması

Oranlar birbirine eşittir (5 = 5).

Minimum oran testinde bir bağ (tie) olması, bir sonraki çözümde temel değişkenlerden birinin değerinin sıfıra düşeceğini gösterir.

Anahtar Kavram

Dejenerelik (Degeneracy)

Tahmini Süre:1m 30s

Soru 11Soru →

Bir kamu kurumu, sunduğu hizmetlerin toplam verimliliğini optimize etmek amacıyla bir doğrusal programlama modeli geliştirmektedir. Bu modelde, farklı hizmet birimlerinin her birinin sağladığı toplam katkının, birimlerin tek başına ürettiği katkıların aritmetik toplamına eşit olduğu ve birimler arasında birbirini güçlendirici (sinerji) veya engelleyici bir etkileşim bulunmadığı kabul edilmektedir. Buna göre, kurumun modelleme sürecinde esas aldığı bu kabul doğrusal programlamanın aşağıdaki temel varsayımlarından hangisidir?

Toplanabilirlik

Oransallık

Bölünebilirlik

Belirlilik

Karar Değişkenlerinin Pozitifliği

Cevabı ve açıklamayı göster

Cevap: Toplanabilirlik

Cevap

Modelde toplam çıktının parçaların toplamına eşit olması ve değişkenler arası etkileşim bulunmaması 'Toplanabilirlik' varsayımıyla açıklanır.

Toplanabilirlik varsayımı, doğrusal programlama modellerinde her bir karar değişkeninin amaç fonksiyonu değerine ve kısıt kaynak kullanımına olan katkısının diğer değişkenlerden bağımsız olduğunu ve toplam etkinin bu bağımsız katkıların toplamına eşit olduğunu garanti eder. Senaryoda belirtilen 'birimler arası etkileşim bulunmaması' ve 'toplam faydanın birimlerin toplamına eşit olması' ifadeleri doğrudan bu varsayımı tanımlamaktadır.

Adım Adım Çözüm

1

Metindeki temel kabulü analiz etme

Toplam faydanın, birim faydaların aritmetik toplamına eşit olduğu saptanmıştır.

Sorunun kökünde yatan matematiksel ilişkinin (Toplam = Parça1 + Parça2 + ...) tespiti için gereklidir.

2

Etkileşim durumunu değerlendirme

Değişkenler arasında sinerji veya olumsuz etkileşim olmadığı (çapraz etkilerin sıfır olduğu) görülmektedir.

Toplanabilirlik varsayımı, değişkenlerin birbirini etkilemeden bağımsız katkı sağladığını varsayar.

3

Tanımla eşleştirme

Bu özellikler doğrusal programlamanın 'Toplanabilirlik' (Additivity) varsayımının tanımıdır.

Teorik bilginin senaryo ile ilişkilendirilerek doğru şıkka ulaşılması sağlanır.

Anahtar Kavram

Toplanabilirlik Varsayımı

Daha Fazla Pratik

Doğrusal programlama modellerinde amaç fonksiyonundaki katsayıların kesin olarak bilinmediği durumların hangi varsayımı ihlal ettiğini araştırabilirsiniz.

Tahmini Süre:1m 15s

Soru 12Soru →

Aşağıda bir doğrusal programlama probleminin primal modeli verilmiştir:

\text{Maks } Z = 6x_1 + 4x_2

Kısıtlar:

x_1 + 2x_2 \leq 20

3x_1 + x_2 \geq 15

Değişkenler:

x_1 \geq 0, \quad x_2 \text{ serbest (işareti kısıtlanmamış)}

Buna göre, bu problemin dual modeli aşağıdakilerden hangisidir?

\text{Min } W = 20y_1 + 15y_2

Kısıtlar:

y_1 + 3y_2 \geq 6

,

2y_1 + y_2 = 4

; Değişkenler:

y_1 \geq 0, y_2 \leq 0

\text{Min } W = 20y_1 + 15y_2

Kısıtlar:

y_1 + 3y_2 \geq 6

,

2y_1 + y_2 = 4

; Değişkenler:

y_1 \geq 0, y_2 \geq 0

\text{Min } W = 20y_1 + 15y_2

Kısıtlar:

y_1 + 3y_2 \geq 6

,

2y_1 + y_2 \geq 4

; Değişkenler:

y_1 \geq 0, y_2 \leq 0

\text{Maks } W = 20y_1 + 15y_2

Kısıtlar:

y_1 + 3y_2 \geq 6

,

2y_1 + y_2 = 4

; Değişkenler:

y_1 \geq 0, y_2 \leq 0

\text{Min } W = 20y_1 + 15y_2

Kısıtlar:

y_1 + 3y_2 \leq 6

,

2y_1 + y_2 = 4

; Değişkenler:

y_1 \geq 0, y_2 \leq 0

Cevabı ve açıklamayı göster

Cevap: $\text{Min } W = 20y_1 + 15y_2$ Kısıtlar: $y_1 + 3y_2 \geq 6$ , $2y_1 + y_2 = 4$ ; Değişkenler: $y_1 \geq 0, y_2 \leq 0$

Cevap

Problemin dual modeli; minimizasyon amaçlı, ikinci kısıtı eşitlik olan ve ikinci dual değişkeni negatif işaretli olan modeldir.

Doğru modelde, primaldeki maksimizasyon minimizasyona dönüştürülmüştür.

x_2

değişkeni serbest olduğu için dualdeki ikinci kısıt eşitlik (

=

) halindedir. Ayrıca primaldeki ikinci kısıt

\geq

yönünde olduğu için (maksimizasyon için standart dışı), buna karşılık gelen

y_2

dual değişkeni

\leq 0

işaret kısıtına sahiptir.

Adım Adım Çözüm

1

Amaç fonksiyonu yönünü ve katsayılarını belirleme

Min

W = 20y_1 + 15y_2

Primal Maks ise Dual Min olur. Primal kısıtların sağ taraf sabitleri dual amaç katsayıları olur.

2

Kısıt katsayılarını transpoz alarak oluşturma

1. Kısıt:

y_1 + 3y_2

, 2. Kısıt:

2y_1 + y_2

Primal değişken katsayıları sütun bazında dual kısıtların satır katsayıları olur.

3

Dual değişkenlerin işaretlerini belirleme

y_1 \geq 0

ve

y_2 \leq 0

Maks probleminde

\leq

kısıtı

\geq 0

değişkenine,

\geq

kısıtı ise

\leq 0

değişkenine karşılık gelir.

4

Dual kısıtların yönlerini belirleme

1. Kısıt

\geq 6

, 2. Kısıt

= 4

Primalde

x_1 \geq 0

olduğu için dual kısıt

\geq

(standart) olur;

x_2

serbest olduğu için dual kısıt eşitlik olur.

Anahtar Kavram

Simetrik Dualite Kuralları

İpuçları

1

Primal modeldeki amaç fonksiyonunun yönüne (Maks/Min) ve değişkenlerin serbest olup olmadığına dikkat edin.

2

Maksimizasyon probleminde

\geq

yönlü kısıtlar standart dışıdır ve dual değişkenin işaretini negatif yapar.

3

Primal modeldeki

x_2

serbest değişkeni, dual modelin 2. kısıtının bir eşitlik (

=

) olmasını sağlar.

Daha Fazla Pratik

Dualden primale geçiş kurallarını ve gölge fiyat (shadow price) kavramını gözden geçirebilirsiniz.

Tahmini Süre:1m 30s

Soru 13Soru →

Aşağıda bir doğrusal programlama probleminin primal modeli verilmiştir:

\text{Maksimum } Z = 5x_1 + 2x_2

Kısıtlar:

x_1 + 3x_2 \leq 12

4x_1 + x_2 \geq 8

x_1 \geq 0, x_2 \text{ serbest (unrestricted)}

Buna göre, bu problemin dual modeli aşağıdakilerden hangisidir?

\text{Minimum } W = 12y_1 + 8y_2

y_1 + 4y_2 \geq 5

3y_1 + y_2 = 2

y_1 \geq 0, y_2 \leq 0

\text{Minimum } W = 12y_1 + 8y_2

y_1 + 4y_2 \geq 5

3y_1 + y_2 = 2

y_1 \geq 0, y_2 \geq 0

\text{Minimum } W = 12y_1 + 8y_2

y_1 + 4y_2 \leq 5

3y_1 + y_2 = 2

y_1 \geq 0, y_2 \leq 0

\text{Minimum } W = 12y_1 + 8y_2

y_1 + 4y_2 \geq 5

3y_1 + y_2 \geq 2

y_1 \geq 0, y_2 \leq 0

\text{Minimum } W = 12y_1 + 8y_2

y_1 + 4y_2 \geq 5

3y_1 + y_2 = 2

y_1 \text{ serbest}, y_2 \text{ serbest}

Cevabı ve açıklamayı göster

Cevap: $\text{Minimum } W = 12y_1 + 8y_2$
$y_1 + 4y_2 \geq 5$
$3y_1 + y_2 = 2$
$y_1 \geq 0, y_2 \leq 0$

Cevap

Minimizasyon yönünde kurgulanan, ilk kısıtı büyük-eşit, ikinci kısıtı eşittir olan ve değişken işaretleri y1 >= 0, y2 <= 0 şeklinde belirlenen model doğrudur.

Dual model kurulurken primal modelin sağ taraf sabitleri amaç fonksiyonu katsayıları olur ve amaç yönü tersine döner. Primal kısıt yönleri ile dual değişken işaretleri arasındaki ilişkiye göre; 'küçük-eşit' kısıtı 'pozitif' değişken, 'büyük-eşit' kısıtı ise 'negatif' değişken üretir. Ayrıca primal değişkenlerin işaretleri dual kısıtların yönünü belirler; serbest bir değişken her zaman bir eşitlik kısıtına yol açar.

Adım Adım Çözüm

1

Amaç fonksiyonu dönüşümünü yapınız.

Min

W = 12y_1 + 8y_2

Primal model Maksimum (Maks) ise Dual model Minimum (Min) olur. Primal sağ taraf sabitleri dual amaç katsayıları olur.

2

Kısıt katsayılarını ve yönlerini belirleyiniz.

1. Kısıt:

y_1 + 4y_2 \geq 5

, 2. Kısıt:

3y_1 + y_2 = 2

Primal katsayı matrisi transpoze edilir.

x_1 \geq 0

olduğu için ilk dual kısıt

\geq

olur;

x_2

serbest olduğu için ikinci dual kısıt

=

olur.

3

Dual değişkenlerin işaretlerini belirleyiniz.

y_1 \geq 0

ve

y_2 \leq 0

Maksimum probleminde

\leq

yönündeki primal kısıt

\geq 0

dual değişken üretir;

\geq

yönündeki primal kısıt

\leq 0

dual değişken üretir.

Anahtar Kavram

Simetrik Dualite ve İşaret Kuralları

Daha Fazla Pratik

Dual modelden tekrar dual alarak primal modele geri dönme (Dualin Duali) pratiği yapabilirsiniz.

Tahmini Süre:1m 30s

Soru 14Soru →

Bir işletme iki farklı ürün üretmektedir. Bu ürünlerin birim karlarını ve üretim sürecindeki kısıtları içeren doğrusal programlama modeli aşağıda verilmiştir:

Maksimum \ Z = 40x_1 + 50x_2

Kısıtlar:

x_1 + 2x_2 \leq 40

4x_1 + 3x_2 \leq 120

x_1 \geq 10

x_1, x_2 \geq 0

Grafik çözüm yöntemi kullanıldığında, bu modelin optimal amaç fonksiyonu değeri kaçtır?

1150

1200

1360

1000

1400

Cevabı ve açıklamayı göster

Cevap: 1360

Cevap

Modelin optimal amaç fonksiyonu değeri 1360'tır.

Grafik çözüm yöntemi ile belirlenen uygun çözüm bölgesinin köşe noktaları (10, 0), (30, 0), (24, 8) ve (10, 15) koordinatlarıdır. Bu noktalar amaç fonksiyonu olan

Z = 40x_1 + 50x_2

denkleminde yerine konulduğunda en büyük değer 1360 olarak (24, 8) noktasında elde edilmektedir.

Adım Adım Çözüm

1

Kısıt doğrularının eksenleri kestiği noktaları bulma

1. kısıt (x1 + 2x2 = 40) için (40, 0) ve (0, 20); 2. kısıt (4x1 + 3x2 = 120) için (30, 0) ve (0, 40) noktaları.

Doğruları grafik üzerinde çizebilmek için başlangıç noktalarını belirlemek gerekir.

2

Uygun çözüm bölgesini (UB) belirleme

Eksenlerin birinci bölgesinde, x1 + 2x2 ≤ 40 ve 4x1 + 3x2 ≤ 120 doğrularının altında, ancak x1 ≥ 10 doğrusunun sağında kalan bölge.

Kısıt yönlerine göre tüm eşitsizlikleri sağlayan ortak alanı tespit etmek çözümün temelidir.

3

Uygun bölgenin köşe noktalarını hesaplama

Köşe noktaları: A(10, 0), B(30, 0), C(24, 8) ve D(10, 15).

Doğrusal programlamada optimal çözüm her zaman uygun bölgenin köşe noktalarından birindedir.

4

Amaç fonksiyonu değerlerini karşılaştırma

Z(10,0)=400; Z(30,0)=1200; Z(24,8)=40(24)+50(8)=1360; Z(10,15)=40(10)+50(15)=1150.

Maksimum karı veren koordinat çiftini bulmak için tüm aday noktalar test edilir.

Anahtar Kavram

Grafik çözüm yönteminde optimal çözüm, uygun çözüm bölgesinin bir köşe noktasında gerçekleşir.

Soru 15Soru →

Doğrusal programlama modellerinin çözümünde kullanılan simpleks yönteminde, bir maksimizasyon problemi için oluşturulan başlangıç tablosu şu şekildedir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm
$Z$	-4	-6	0	0	0
$s_1$	1	3	1	0	18
$s_2$	2	1	0	1	16

Bu tabloya göre, yapılacak ilk iterasyonda çözüme girecek (temel değişken olacak) ve çözümden çıkacak (temel dışı kalacak) değişkenler aşağıdakilerin hangisinde doğru verilmiştir?

Giren:

x_2

, Çıkan:

s_1

Giren:

x_2

, Çıkan:

s_2

Giren:

x_1

, Çıkan:

s_2

Giren:

x_1

, Çıkan:

s_1

Giren:

s_1

, Çıkan:

x_2

Cevabı ve açıklamayı göster

Cevap: Giren: $x_2$ , Çıkan: $s_1$

Cevap

Çözüme giren değişken

x_2

, çözümden çıkan değişken ise

s_1

olmalıdır.

Maksimizasyon probleminde giren değişken, amaç fonksiyonu satırındaki en küçük negatif katsayıya sahip olan değişkendir (-6 katsayısıyla

x_2

). Çıkan değişken ise, sağ yan değerlerin anahtar sütun katsayılarına oranlanmasıyla bulunan en küçük pozitif oranlı satırın değişkenidir (18/3 = 6 oranıyla

s_1

).

Adım Adım Çözüm

1

Giren değişkenin (anahtar sütun) belirlenmesi

x_2

değişkeni (katsayısı -6)

Maksimizasyon problemlerinde

Z

satırındaki en küçük negatif katsayıya sahip değişken çözüme girer.

2

Oran testinin yapılması

s_1

satırı için 18/3 = 6;

s_2

satırı için 16/1 = 16

Çözüm (RHS) sütunundaki değerler, anahtar sütundaki pozitif katsayılara bölünerek oranlar bulunur.

3

Çıkan değişkenin (anahtar satır) belirlenmesi

s_1

değişkeni

Oran testi sonucunda elde edilen en küçük pozitif oran (6), çözümden çıkacak olan temel değişkeni belirler.

Anahtar Kavram

Simpleks yönteminde pivot seçimi kuralları (en küçük negatif katsayı ve en küçük pozitif oran).

Tahmini Süre:1m 30s

Soru 16Soru →

Bir maksimizasyon (en büyükleme) probleminin Simpleks yöntemi ile çözümü sırasında elde edilen bir ara tablo aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm
$Z$	$-5$	$0$	$3$	$0$	$50$
$x_2$	$-2$	$1$	$1$	$0$	$10$
$s_2$	$-4$	$0$	$2$	$1$	$20$

Bu tabloya göre, modelin çözümüne ilişkin aşağıdakilerden hangisi söylenebilir?

Modelin çözüm kümesi sınırsızdır.

Modelde dejenerelik (yozlaşma) durumu mevcuttur.

Modelin birden fazla (alternatif) optimal çözümü vardır.

Modelin uygun bir çözüm kümesi yoktur (uygunsuzluk).

Mevcut tablo optimal çözümü vermektedir ve

Z

değeri

50

'dir.

Cevabı ve açıklamayı göster

Cevap: Modelin çözüm kümesi sınırsızdır.

Cevap

Modelin çözüm kümesi sınırsızdır çünkü temele girmeye aday değişkenin sütununda pozitif bir katsayı bulunmamaktadır.

Verilen tabloda maksimizasyon yönlü bir problemde

x_1

değişkeninin amaç satırı katsayısı

-5

olduğundan bu değişken temele girmeye adaydır. Ancak

x_1

sütunundaki tüm kısıt katsayıları (

-2

ve

-4

) negatif veya sıfırdır. Bu durum,

x_1

değişkeni artırıldıkça kısıtların daralmak yerine esnediğini ve değişkenin değerinin sonsuza kadar artırılabileceğini gösterir. Dolayısıyla amaç fonksiyonu değeri de sınırsız olarak artacaktır.

Adım Adım Çözüm

1

Amaç satırındaki katsayıları incele

x_1

değişkeninin katsayısı

-5

olarak belirlenir.

Maksimizasyon probleminde amaç satırında (Z satırı) negatif katsayıya sahip değişkenler, amaç fonksiyonu değerini artırmak için temele girmeye adaydır.

2

Girecek değişkenin sütun katsayılarını kontrol et

x_1

sütunundaki katsayılar

\{-2, -4\}

'tür.

Temele girecek değişkenin kısıtları ne ölçüde daralttığını belirlemek için katsayıların pozitif olması gerekir.

3

Oran testini uygula

Pozitif katsayı bulunmadığından oran testi yapılamaz.

Simpleks algoritmasında çıkacak değişkeni belirlemek için yapılan oran testi (Çözüm / Pozitif Katsayı) paydadaki değerlerin

\leq 0

olması durumunda sonuçsuz kalır.

4

Sonucu yorumla

Sınırsızlık (Unboundedness) durumu teşhis edilir.

Bir değişken amaç fonksiyonunu sonsuza kadar iyileştirebiliyor ve hiçbir kısıt tarafından durdurulamıyorsa (oran testi yapılamıyorsa), çözüm sınırsızdır.

Anahtar Kavram

Simpleks Yönteminde Sınırsızlık Koşulu

Tahmini Süre:1m 30s

Soru 17Soru →

Bir kamu kurumu sosyal sorumluluk projesi kapsamında "Eğitim Desteği" ( $x_1$ ) ve "Sağlık Taraması" ( $x_2$ ) faaliyetleri yürütmektedir. Faaliyetlere ilişkin veriler aşağıdaki tabloda sunulmuştur:

Faaliyet Türü	Sosyal Fayda (Birim)	Maliyet (TL/Adet)	Personel Süresi (Saat/Adet)
Eğitim Desteği ( $x_1$ )	$10$	$200$	$2$
Sağlık Taraması ( $x_2$ )	$12$	$300$	$1$
Toplam Kapasite	-	$60.000$ TL	$400$ Saat

Kurum, sosyal politika gereği eğitim desteği faaliyetinden en az $50$ adet gerçekleştirmek zorundadır.

Buna göre, kurumun toplam sosyal faydasını maksimize edecek doğrusal programlama modeli aşağıdakilerden hangisidir?

\text{Maks } Z = 10x_1 + 12x_2

\text{Kısıtlar:}

200x_1 + 300x_2 \leq 60.000

2x_1 + x_2 \leq 400

x_1 \geq 50

x_1, x_2 \geq 0

\text{Min } Z = 10x_1 + 12x_2

\text{Kısıtlar:}

200x_1 + 300x_2 \leq 60.000

2x_1 + x_2 \leq 400

x_1 \geq 50

x_1, x_2 \geq 0

\text{Maks } Z = 10x_1 + 12x_2

\text{Kısıtlar:}

200x_1 + 300x_2 \geq 60.000

2x_1 + x_2 \geq 400

x_1 \geq 50

x_1, x_2 \geq 0

\text{Maks } Z = 12x_1 + 10x_2

\text{Kısıtlar:}

200x_1 + 300x_2 \leq 60.000

2x_1 + x_2 \leq 400

x_1 \geq 50

x_1, x_2 \geq 0

\text{Maks } Z = 10x_1 + 12x_2

\text{Kısıtlar:}

200x_1 + 300x_2 \leq 60.000

2x_1 + x_2 \leq 400

x_1 \leq 50

x_1, x_2 \geq 0

Cevabı ve açıklamayı göster

Cevap: $\text{Maks } Z = 10x_1 + 12x_2$
$\text{Kısıtlar:}$
$200x_1 + 300x_2 \leq 60.000$
$2x_1 + x_2 \leq 400$
$x_1 \geq 50$
$x_1, x_2 \geq 0$

Cevap

Sosyal faydayı maksimize eden, bütçe ve zaman kısıtlarını üst sınır (küçük-eşit) olarak belirleyen ve politika gereği eğitim desteğini en az 50 birim (büyük-eşit) olarak tanımlayan model doğrudur.

Doğru modelde, sosyal fayda katsayıları (

10

ve

12

) amaç fonksiyonunda toplama dahil edilerek maksimizasyon hedeflenmiştir. Bütçe (

60.000

) ve personel süresi (

400

) için verilen kapasiteler 'en fazla' olduğu için küçük-eşit

(\leq)

yönünde kısıtlanmıştır. Sosyal politika gereği belirtilen 'en az

50

' şartı ise büyük-eşit

(\geq)

sembolü ile doğru şekilde modele yansıtılmıştır.

Adım Adım Çözüm

1

Karar değişkenlerini tanımla.

x_1

: Eğitim Desteği adedi,

x_2

: Sağlık Taraması adedi.

Modelin temel bileşenlerini belirlemek için değişkenlerin tanımlanması gerekir.

2

Amaç fonksiyonunu oluştur.

Z_{max} = 10x_1 + 12x_2

Toplam sosyal faydanın maksimize edilmesi hedeflendiği için her faaliyetin birim faydası ilgili değişkenle çarpılır.

3

Kaynak kısıtlarını yaz.

Bütçe için

200x_1 + 300x_2 \leq 60.000

ve süre için

2x_1 + 1x_2 \leq 400

.

Bütçe ve süre kısıtlı kaynaklar olduğu için toplam kullanım kapasiteyi aşmamalıdır.

4

Politika ve işaret kısıtlarını ekle.

x_1 \geq 50

ve

x_1, x_2 \geq 0

.

En az 50 adet şartı büyük-eşit ile, fiziksel kısıtlar ise negatif olmama şartıyla ifade edilir.

Anahtar Kavram

Doğrusal programlamada sözel ifadelerin matematiksel kısıt yönlerine (<=, >=) ve amaç fonksiyonu yönüne (Maks, Min) doğru dönüştürülmesi.

Daha Fazla Pratik

Kısıtlara 'eğitim desteği miktarı, toplam faaliyetin en az %20'si olmalıdır' gibi oran kısıtları ekleyerek model kurma pratiği yapabilirsiniz.

Tahmini Süre:1m 30s

Soru 18Soru →

Bir doğrusal programlama maksimizasyon probleminde, başlangıç simpleks tablosu düzenlenmiş ve $x_2$ değişkeni "temele giren değişken" (anahtar sütun) olarak belirlenmiştir. Tablonun kısıtlar kısmına ait katsayılar ve çözüm değerleri aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm (Sağ Yan)
$s_1$	$1$	$2$	$1$	$0$	$10$
$s_2$	$2$	$1$	$0$	$1$	$8$

Bu bilgilere göre, simpleks algoritmasının "oran testi" (minimum ratio test) kuralı uygulandığında temelden çıkacak değişken (anahtar satır) aşağıdakilerden hangisidir?

s_1

s_2

x_1

x_2

Z

Cevabı ve açıklamayı göster

Cevap: $s_1$

Cevap

Temelden çıkacak değişken

s_1

değişkenidir.

Temele giren değişken

x_2

olarak belirlendiğinde, bu sütundaki katsayılar ile çözüm değerleri arasındaki oranlar incelenir.

s_1

satırı için oran

10/2=5

,

s_2

satırı için ise

8/1=8

değerini alır. Simpleks kuralı gereği en küçük pozitif orana sahip olan satır anahtar satırdır ve o satırdaki temel değişken (

s_1

) temelden çıkar.

Adım Adım Çözüm

1

Temele giren değişken olan

x_2

sütunundaki kısıt katsayılarını belirleyin.

s_1

satırı için katsayı

2

,

s_2

satırı için katsayı

1

olarak belirlenmiştir.

Oran testi yalnızca temele giren değişkenin sütunundaki katsayılar üzerinden yapılır.

2

Çözüm (Sağ Yan) sütunundaki değerleri, karşılık gelen

x_2

katsayılarına bölerek oranları hesaplayın.

s_1

satırı için

10 / 2 = 5

ve

s_2

satırı için

8 / 1 = 8

sonuçları elde edilir.

Oran testi, kısıtların sınırlarını ihlal etmeden temele girebilecek maksimum değeri bulmayı sağlar.

3

Hesaplanan pozitif oranlar arasından en küçük olanı seçin.

5 < 8

olduğu için en küçük oran

s_1

satırına aittir.

Simpleks yönteminde en küçük oran testini sağlayan satır, temelden çıkacak değişkeni ve anahtar satırı belirler.

Anahtar Kavram

Simpleks yönteminde temelden çıkacak değişken, temele giren değişkenin katsayılarına göre yapılan minimum oran testi ile belirlenir.

Tahmini Süre:1m 30s

Soru 19Soru →

Bir belediye, katı atık toplama hizmetlerinde kullanılmak üzere iki farklı tipte araç (Tip A ve Tip B) işletmektedir. Bu hizmete ilişkin veriler aşağıdaki tabloda sunulmuştur:

Parametre	Tip A ( $x_1$ )	Tip B ( $x_2$ )	Kısıt / Gereksinim
Günlük İşletme Maliyeti (TL)	$500$	$800$	En küçüklenmeli
Atık Toplama Kapasitesi (Ton/Gün)	$2$	$5$	En az $100$ ton
Gerekli Personel Sayısı (Kişi)	$2$	$3$	En çok $80$ kişi

Belediyenin toplam günlük işletme maliyetini en küçüklemek amacıyla kurması gereken doğrusal programlama modeli aşağıdakilerden hangisidir?

\begin{aligned} \min Z &= 500x_1 + 800x_2 \\ 2x_1 + 5x_2 &\geq 100 \\ 2x_1 + 3x_2 &\leq 80 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \max Z &= 500x_1 + 800x_2 \\ 2x_1 + 5x_2 &\geq 100 \\ 2x_1 + 3x_2 &\leq 80 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \min Z &= 500x_1 + 800x_2 \\ 2x_1 + 5x_2 &\leq 100 \\ 2x_1 + 3x_2 &\leq 80 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \min Z &= 500x_1 + 800x_2 \\ 2x_1 + 5x_2 &\geq 100 \\ 2x_1 + 3x_2 &\geq 80 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \min Z &= 800x_1 + 500x_2 \\ 5x_1 + 2x_2 &\geq 100 \\ 3x_1 + 2x_2 &\leq 80 \\ x_1, x_2 &\geq 0 \end{aligned}

Cevabı ve açıklamayı göster

Cevap: $\begin{aligned} \min Z &= 500x_1 + 800x_2 \\ 2x_1 + 5x_2 &\geq 100 \\ 2x_1 + 3x_2 &\leq 80 \\ x_1, x_2 &\geq 0 \end{aligned}$

Cevap

Maliyetin en küçüklenmesini hedefleyen, atık kapasitesi için büyük-eşit (≥ 100), personel sayısı için küçük-eşit (≤ 80) ve non-negatiflik kısıtlarını içeren model doğrudur.

Doğru modelde, maliyetlerin minimize edilmesi hedeflenmiş (

Z = 500x_1 + 800x_2

), atık toplama için gereken minimum seviye büyük-eşit (

\geq 100

) ile, personel kaynağının sınırlılığı ise küçük-eşit (

\leq 80

) ile doğru bir şekilde ifade edilmiştir.

Adım Adım Çözüm

1

Karar değişkenlerinin tanımlanması

x_1

: İşletilen Tip A araç sayısı,

x_2

: İşletilen Tip B araç sayısı.

Modelin temel bileşenlerini belirlemek için değişkenlerin tanımlanması gerekir.

2

Amaç fonksiyonunun oluşturulması

\min Z = 500x_1 + 800x_2

Problemde toplam günlük işletme maliyetinin en küçüklenmesi istenmektedir.

3

Kısıtlayıcı koşulların belirlenmesi

Atık kapasitesi:

2x_1 + 5x_2 \geq 100

; Personel sınırı:

2x_1 + 3x_2 \leq 80

.

'En az' ifadesi alt sınırı (\geq), 'en çok' ifadesi üst sınırı (\leq) temsil eder.

4

İşaret kısıtlarının eklenmesi

x_1, x_2 \geq 0

Araç sayıları negatif değer alamayacağı için doğrusal programlama varsayımları gereği eklenmelidir.

Anahtar Kavram

Doğrusal programlamada sözel ifadelerin matematiksel eşitsizliklere ve amaç fonksiyonuna dönüştürülmesi.

Soru 20Soru →

Doğrusal programlama modellerinde, karar değişkenlerinin tamsayı değerler alma zorunluluğunun bulunmaması ve her bir değişkenin kendi değişim aralığı içerisinde herhangi bir kesirli (reel) değeri alabilmesi öngörülmektedir. Bu öngörü, modelin çözüm kümesinin matematiksel olarak sürekli bir yapıda olmasını sağlamaktadır. Buna göre, doğrusal programlama modellerinde karar değişkenlerinin tamsayı olmayan (kesirli) değerler alabilmesine olanak tanıyan temel varsayım aşağıdakilerden hangisidir?

Oransallık

Toplanabilirlik

Bölünebilirlik

Belirlilik

Tamsayılılık

Cevabı ve açıklamayı göster

Cevap: Bölünebilirlik

Cevap

Bölünebilirlik varsayımı, karar değişkenlerinin tanımlı oldukları aralıkta herhangi bir reel (kesirli) değeri alabilmesine olanak tanır.

Bölünebilirlik varsayımı, bir doğrusal programlama modelindeki karar değişkenlerinin reel sayılar kümesinde tanımlı olduğunu ve herhangi bir kesirli değeri alabileceğini ifade eder. Bu, modelin çözüm kümesinin sürekli olmasını sağlar ve optimizasyonun tamsayı kısıtı olmadan yapılabilmesine imkan tanır.

Adım Adım Çözüm

1

Karar değişkenlerinin özelliklerini analiz etme

Soruda değişkenlerin tamsayı zorunluluğu olmadığı ve kesirli değerler alabildiği belirtilmiştir.

Bu durum, çözüm uzayının kesikli (discrete) değil, sürekli (continuous) olduğunu gösterir.

2

Doğrusal programlama varsayımları ile eşleştirme

Süreklilik ve kesirli değer alabilme özelliği 'Bölünebilirlik' (Divisibility) varsayımı ile tanımlanır.

Diğer varsayımlar (Oransallık, Toplanabilirlik, Belirlilik) modelin diğer yapısal özelliklerini (doğrusallık ve kesinlik) tanımlar.

Anahtar Kavram

Doğrusal Programlama Varsayımları: Bölünebilirlik

Alternatif Yöntem

Varsayımları eleme yöntemiyle de doğru cevaba ulaşılabilir: Soruda 'kesirli değer' vurgusu yapıldığı için, doğrusal ilişkiyle ilgili olan Oransallık, toplamayla ilgili olan Toplanabilirlik ve kesinlikle ilgili olan Belirlilik elenir.

Tahmini Süre:45s

Doğrusal Programlama

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Alternatif Yöntem

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

İpuçları

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram