Doğrusal Programlama Practice Questions — KPSS İstatistik — Page 4

Question 61Question →

Bir maksimizasyon problemi için oluşturulan doğrusal programlama modelinin çözümü sırasında elde edilen ara simpleks tablosu aşağıda verilmiştir:

Temel	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$	Çözüm
$Z$	$-5$	$0$	$-8$	$4$	$0$	$0$	$200$
$x_2$	$2$	$1$	$-3$	$1$	$0$	$0$	$15$
$s_2$	$4$	$0$	$2$	$-2$	$1$	$0$	$12$
$s_3$	$-1$	$0$	$4$	$3$	$0$	$1$	$28$

Buna göre, standart simpleks algoritması kurallarına uygun olarak yapılacak bir sonraki iterasyon sonucunda elde edilecek yeni tabloda; amaç fonksiyonu ( $Z$ ) değeri ile $s_3$ temel değişkeninin çözüm (RHS) değeri sırasıyla aşağıdakilerden hangisidir?

248

ve

4

215

ve

31

160

ve

48

256

ve

0

248

ve

16

Show answer & explanation

Answer: $248$ ve $4$

Answer

Yeni tabloda amaç fonksiyonu değeri 248,

s_3

değişkeninin çözüm değeri ise 4 olacaktır.

Verilen tabloda

Z

satırındaki en küçük değer

-8

olduğu için anahtar sütun

x_3

'tür. Oran testinde negatifler atlanarak pozitif katsayılara bölme işlemi yapılır (

12/2=6

ve

28/4=7

). Minimum oran olan 6,

s_2

satırına ait olduğundan pivot eleman

2

'dir. Satır operasyonları uygulandığında yeni

Z

değeri

200 + (-(-8) \times 6) = 248

ve yeni

s_3

değeri

28 - 4 \times 6 = 4

olarak bulunur.

Step-by-Step Solution

1

Anahtar sütunu (giren değişkeni) belirleme.

Z

satırında en negatif değere sahip katsayı

-8

olduğundan,

x_3

giren değişkendir.

Maksimizasyon problemlerinde, amaca en fazla katkıyı sağlayacak değişken

Z

satırındaki en negatif (veya

C_j - Z_j

satırında en pozitif) katsayıya sahip değişkendir.

2

Anahtar satırı (çıkan değişkeni) belirleme.

Pozitif pivot sütun elemanları için oran testi yapılır:

x_2

satırı için

15 / (-3)

(negatif, dikkate alınmaz),

s_2

satırı için

12 / 2 = 6

,

s_3

satırı için

28 / 4 = 7

. En küçük oran 6 olduğundan

s_2

çıkan değişkendir. Pivot eleman 2'dir.

Çözüm alanının dışına çıkmamak (uygunluğu korumak) için, oranı en küçük olan temel değişken çözümden çıkarılır.

3

Yeni amaç fonksiyonu (

Z

) değerini hesaplama.

Yeni

Z

satırı işlemi:

Y_Z = E_Z - (-8) \times (Yeni Pivot Satırı)

. Çözüm değeri:

200 - (-8) \times (12 / 2) = 200 + 48 = 248

.

Pivot elemana göre satır işlemleri yapılarak

x_3

'ün

Z

satırındaki katsayısı sıfırlanmalıdır.

4

Yeni

s_3

satırının çözüm değerini hesaplama.

Yeni

s_3

satırı = Eski

s_3

satırı

- 4 \times (Yeni Pivot Satırı)

. Çözüm değeri:

28 - 4 \times (12 / 2) = 28 - 24 = 4

.

Temel değişkenlerin kendi sütunlarında birim matris formunu koruması için diğer satırlardaki değerler satır operasyonlarıyla sıfırlanır.

Key Concept

Simpleks tablosunda iterasyon adımları ve satır operasyonları

Alternative Method

Yeni tablodaki Z değerini tam matris işlemi yapmadan pratik olarak bulmak için şu formül kullanılabilir: Yeni Z = Mevcut Z + (Çıkan Değişkenin Oranı × |Giren Değişkenin Z Katsayısı|). Bu tabloda giren değişken x3 (katsayısı -8), çıkan değişken s2 (oranı 6) olduğundan, Yeni Z = 200 + (6 × |-8|) = 248 bulunur.

Estimated Time:3m 0s

Question 62Question →

Doğrusal programlama problemlerinin çözümünde kullanılan İki Evreli (Two-Phase) simpleks yönteminin 1. Evre (Phase-I) adımında, yapay değişkenlerin toplamından oluşan amaç fonksiyonu ( $W$ ) minimize edilmektedir.

Bir problemin 1. Evre optimum tablosuna ulaşıldığında amaç fonksiyonu değerinin $W = 0$ olduğu, ancak yapay değişkenlerden biri olan $R_1$ 'in temel değişkenler arasında ve çözüm değerinin sıfır ( $0$ ) olarak kaldığı görülmüştür. Bu optimum tablonun $R_1$ 'e ait satırında, temel olmayan asıl karar ve aylak/artık değişkenlerin katsayıları $a_{1j}^*$ ile gösterilmektedir.

Bu durumun teorik yorumu ve 2. Evre'ye (Phase-II) geçiş süreci ile ilgili aşağıdakilerden hangisi kesinlikle doğrudur?

Eğer tüm

a_{1j}^* = 0

ise, bu satır modeldeki kısıtlardan birinin diğerlerine doğrusal bağımlı olduğunu gösterir ve satır tablodan silinerek 2. Evre'ye geçilir; sıfırdan farklı bir

a_{1j}^*

varsa

R_1

pivot işlemiyle temelden çıkarılır.

Eğer tüm

a_{1j}^* \leq 0

ise, problemin uygun çözüm alanı sınırsızdır ve 2. Evre'ye geçilmeden simpleks algoritması sonlandırılarak çözümün sınırsız olduğu rapor edilir.

W = 0

koşulu sağlansa bile

R_1

'in temelde kalması, başlangıç matematiksel modelinde

\geq

veya

=

yönlü kısıtların yanlış kurgulandığını gösterir ve modelin düzeltilmesi gerekir.

R_1

değişkeni 2. Evre boyunca temel değişken olarak tablodaki yerini korumak zorundadır; ancak asıl amaç fonksiyonuna eklenirken Büyük-M (Big-M) yöntemi kuralları gereği

-M

katsayısı ile cezalandırılmalıdır.

Eğer herhangi bir

a_{1j}^* > 0

ise, problemde uygun çözüm yoktur (infeasible) kararı verilir, çünkü yapay değişkenin temelden çıkabilmesi için tüm katsayıların sıfır olması şarttır.

Show answer & explanation

Answer: Eğer tüm $a_{1j}^* = 0$ ise, bu satır modeldeki kısıtlardan birinin diğerlerine doğrusal bağımlı olduğunu gösterir ve satır tablodan silinerek 2. Evre'ye geçilir; sıfırdan farklı bir $a_{1j}^*$ varsa $R_1$ pivot işlemiyle temelden çıkarılır.

Answer

Eğer tüm

a_{1j}^* = 0

ise, satır tablodan silinir (doğrusal bağımlılık); sıfırdan farklı katsayı varsa pivot işlemiyle

R_1

temelden çıkarılır.

İki Evreli (Two-Phase) yöntemin 1. Evre'si sonunda

W=0

değerine ulaşılması, uygun çözümün varlığını kanıtlar. Ancak bir yapay değişken sıfır değeriyle temelde kalmışsa, bu durum incelenmelidir. Eğer bu satırdaki tüm karar ve artık değişken katsayıları sıfırsa (

a_{1j}^*=0

), elde edilen denklem

0x_1 + 0x_2 + ... + 1R_1 = 0

şeklindedir. Bu denklem

0=0

mantığına dönüştüğünden, kısıtın diğer kısıtların doğrusal bir birleşimi (redundant/gereksiz) olduğu anlaşılır ve satır tablodan tamamen silinir. Eğer sıfırdan farklı bir katsayı var ise, basit bir pivot işlemi yapılarak asıl değişken temele sokulur, yapay değişken temelden uzaklaştırılır ve 2. Evre'ye öyle geçilir. Doğru ifade bu durumu eksiksiz açıklamaktadır.

Step-by-Step Solution

1

1. Evre (Phase-1) sonunda amaç fonksiyonu değeri W = 0 olduğunda temel uygun çözümün varlığını değerlendirmek.

W = 0 olması, yapay değişkenlerin değerlerinin toplamının sıfırlandığını ve orijinal problemin uygun bir çözüm alanına (feasible region) sahip olduğunu kesin olarak kanıtlar.

Yapay değişkenler çözüm alanında olmayan noktaları yapay olarak var etmişti; toplamın sıfırlanması hedefe ulaşıldığını gösterir.

2

Yapay değişkenin (

R_1

) temelde kalması ve değerinin 0 olması durumunun (dejenerelik) analiz edilmesi.

Bu durum, kısıtlardan birinin doğrusal bağımlı (gereksiz) olabileceğine veya o anki köşede yoz (degenerate) bir temel çözümde bulunulduğuna işaret eder.

2. Evre'ye geçerken algoritmanın tıkanmaması için sıfır değerli yapay değişkenlerin temelden tamamen uzaklaştırılması veya zararsız hale getirilmesi gerekir.

3

İlgili satırdaki temel olmayan değişken katsayılarının (

a_{1j}^*

) kontrol edilmesi.

Tüm katsayılar sıfır ise

0 = 0

şeklinde etkisiz bir denklem elde edilir; bu kısıt gereksizdir ve satır silinir. Eğer sıfırdan farklı bir katsayı varsa, o değişken anahtar sütun seçilerek normal bir pivot işlemiyle

R_1

temelden çıkarılır.

Yapay değişkenler asıl problemde varlık göstermediğinden 2. Evre'deki hesaplamaları bozmamaları için bu temizlik matematiksel bir zorunluluktur.

Key Concept

İki Evreli Yöntemde 1. Evre Sonunda Dejenerelik ve Doğrusal Bağımlılık (Redundancy) Analizi

Estimated Time:2m 0s

Question 63Question →

Bir tedarik zinciri ağının optimizasyonu için geliştirilen doğrusal programlama primal modeli aşağıda verilmiştir:

\begin{aligned} \text{Maksimum } Z &= 9x_1 - 6x_2 + 4x_3 \\ \text{Kısıtlar:} \\ 3x_1 + 2x_2 - 5x_3 &\leq 40 \\ x_1 - 3x_2 + 2x_3 &\geq 15 \end{aligned}

İşaret Kısıtlamaları:

\begin{aligned} x_1 &\geq 0 \\ x_2 &\text{ işareti serbest (urs)} \\ x_3 &\leq 0 \end{aligned}

Bu primal modele karşılık gelen dual model aşağıdakilerden hangisinde doğru olarak verilmiştir?

\begin{aligned} \text{Minimum } W &= 40y_1 + 15y_2 \\ 3y_1 + y_2 &\geq 9 \\ 2y_1 - 3y_2 &\geq -6 \\ -5y_1 + 2y_2 &\geq 4 \\ y_1 &\geq 0, \ y_2 \geq 0 \end{aligned}

\begin{aligned} \text{Minimum } W &= 40y_1 + 15y_2 \\ 3y_1 + y_2 &\geq 9 \\ 2y_1 - 3y_2 &= -6 \\ -5y_1 + 2y_2 &\leq 4 \\ y_1 &\leq 0, \ y_2 \geq 0 \end{aligned}

\begin{aligned} \text{Minimum } W &= 40y_1 + 15y_2 \\ 3y_1 + y_2 &\geq 9 \\ 2y_1 - 3y_2 &= -6 \\ -5y_1 + 2y_2 &\leq 4 \\ y_1 &\geq 0, \ y_2 \leq 0 \end{aligned}

\begin{aligned} \text{Minimum } W &= 40y_1 + 15y_2 \\ 3y_1 + y_2 &\geq 9 \\ 2y_1 - 3y_2 &\leq -6 \\ -5y_1 + 2y_2 &\geq 4 \\ y_1 &\geq 0, \ y_2 \text{ işareti serbest} \end{aligned}

\begin{aligned} \text{Minimum } W &= 40y_1 + 15y_2 \\ 3y_1 + y_2 &\leq 9 \\ 2y_1 - 3y_2 &= -6 \\ -5y_1 + 2y_2 &\geq 4 \\ y_1 &\geq 0, \ y_2 \leq 0 \end{aligned}

Show answer & explanation

Answer: $\begin{aligned} \text{Minimum } W &= 40y_1 + 15y_2 \\ 3y_1 + y_2 &\geq 9 \\ 2y_1 - 3y_2 &= -6 \\ -5y_1 + 2y_2 &\leq 4 \\ y_1 &\geq 0, \ y_2 \leq 0 \end{aligned}$

Answer

Doğru dual modelde; amaç fonksiyonu Minimum W = 40y1 + 15y2 olmalı, dual kısıtlar sırasıyla büyük eşit, eşit ve küçük eşit yönlerinde olmalı ve dual değişkenlerden ilki sıfırdan büyük eşit, ikincisi ise sıfırdan küçük eşit olmalıdır.

Primal model bir maksimum problemidir. Bu nedenle dual model minimum problemi olacaktır. Primal kısıtların sağ taraf sabitleri (40 ve 15) dual amaç fonksiyonunun katsayılarıdır: Min W = 40y1 + 15y2. Dual değişkenlerin işaretleri primal kısıtların yönüne göre belirlenir: 1. kısıt (<=) standart olduğu için y1>=0, 2. kısıt (>=) standart dışı olduğu için y2<=0 olur. Dual yapısal kısıtların yönleri ise primal değişkenlerin işaretlerine göre belirlenir: x1>=0 (standart) olduğundan 1. kısıt >=, x2 işareti serbest olduğundan 2. kısıt =, x3<=0 olduğundan 3. kısıt <= olur. Primal modelin katsayı matrisinin transpozu alınarak bu kurallar uygulandığında doğru model elde edilir.

Step-by-Step Solution

1

Amaç fonksiyonunu dönüştürme

\text{Minimum } W = 40y_1 + 15y_2

Primal model 'Maksimum' olduğundan dual model 'Minimum' olur. Primal kısıtların sağ taraf sabitleri (40 ve 15), dual amaç fonksiyonunun katsayılarına dönüşür.

2

Dual değişkenlerin işaret kısıtlamalarını belirleme

y_1 \geq 0, \ y_2 \leq 0

Maksimum primal modelde; 1. kısıt (<=) standart yönde olduğu için

y_1 \geq 0

olur. 2. kısıt (>=) standart dışı (ters) yönde olduğu için

y_2 \leq 0

olur.

3

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

1. Kısıt:

\geq

, 2. Kısıt:

=

, 3. Kısıt:

\leq

Minimum dual modelde;

x_1 \geq 0

(standart) olduğu için 1. kısıt

\geq

olur.

x_2

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

=

olur.

x_3 \leq 0

(ters) olduğu için 3. kısıt

\leq

olur.

4

Katsayı matrisinin transpozunu alarak kısıtları yazma

3y_1 + y_2 \geq 9

,

2y_1 - 3y_2 = -6

,

-5y_1 + 2y_2 \leq 4

Primal modeldeki değişken katsayıları sütunlardan satırlara dönüştürülür ve primal amaç fonksiyonu katsayıları (9, -6, 4) dual kısıtların sağ taraf sabiti yapılarak model tamamlanır.

Key Concept

Dualite Kavramı ve Primal-Dual Dönüşüm Kuralları

Question 64Question →

Karar vericiler tarafından analiz edilen ve üç farklı faaliyetin incelendiği bir optimizasyon probleminin doğrusal programlama primal modeli aşağıda verilmiştir:

\begin{aligned} \text{Maks } Z &= 10x_1 - 5x_2 + 12x_3 \\ \text{Kısıtlar:} & \\ 4x_1 - 2x_2 + x_3 &\leq 50 \\ x_1 + 3x_2 - 2x_3 &\geq 30 \\ x_1, x_3 &\geq 0 \\ x_2 &\text{ işaretsiz} \end{aligned}

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

\begin{aligned} \text{Min } W &= 50y_1 + 30y_2 \\ 4y_1 + y_2 &\geq 10 \\ -2y_1 + 3y_2 &= -5 \\ y_1 - 2y_2 &\geq 12 \\ y_1 \geq 0&, y_2 \leq 0 \end{aligned}

\begin{aligned} \text{Min } W &= 50y_1 + 30y_2 \\ 4y_1 + y_2 &\geq 10 \\ -2y_1 + 3y_2 &= -5 \\ y_1 - 2y_2 &\geq 12 \\ y_1 \geq 0&, y_2 \geq 0 \end{aligned}

\begin{aligned} \text{Min } W &= 50y_1 + 30y_2 \\ 4y_1 + y_2 &\leq 10 \\ -2y_1 + 3y_2 &= -5 \\ y_1 - 2y_2 &\leq 12 \\ y_1 \geq 0&, y_2 \leq 0 \end{aligned}

\begin{aligned} \text{Min } W &= 50y_1 + 30y_2 \\ 4y_1 + y_2 &\geq 10 \\ -2y_1 + 3y_2 &\geq -5 \\ y_1 - 2y_2 &\geq 12 \\ y_1 \geq 0&, y_2 \leq 0 \end{aligned}

\begin{aligned} \text{Maks } W &= 50y_1 + 30y_2 \\ 4y_1 + y_2 &\leq 10 \\ -2y_1 + 3y_2 &= -5 \\ y_1 - 2y_2 &\leq 12 \\ y_1 \geq 0&, y_2 \leq 0 \end{aligned}

Show answer & explanation

Answer: $\begin{aligned} \text{Min } W &= 50y_1 + 30y_2 \\ 4y_1 + y_2 &\geq 10 \\ -2y_1 + 3y_2 &= -5 \\ y_1 - 2y_2 &\geq 12 \\ y_1 \geq 0&, y_2 \leq 0 \end{aligned}$

Answer

Doğru dual model, amaç fonksiyonunun 'Min W' olduğu, ikinci dual kısıtın eşitlik (=) içerdiği ve ikinci dual değişkenin sıfırdan küçük veya eşit (y2 <= 0) olduğu modeldir.

Primal model bir maksimizasyon problemidir. Dualite kurallarına göre: 1) Model minimizasyon (Min) olmalıdır. 2) Birinci kısıt (<=) olduğu için y1 >= 0 olmalıdır. İkinci kısıt (>=) olduğu için y2 <= 0 olmalıdır. 3) x1 ve x3 (>= 0) olduğu için dualde kendilerine karşılık gelen 1. ve 3. kısıtlar (>=) olmalıdır. 4) x2 işaretsiz olduğu için, 2. dual kısıt kesinlikle bir eşitlik (=) olmalıdır. Tüm bu şartları eksiksiz sağlayan tek model doğru cevaptaki modeldir.

Step-by-Step Solution

1

Amaç fonksiyonunun yönünü ve değerlerini belirleme.

Primal (Maks) -> Dual (Min) olur. Sağ taraf sabitleri (50 ve 30) amaç fonksiyonu katsayıları olur: Min W = 50y1 + 30y2.

Primal ve dual modellerin optimizasyon yönleri her zaman birbirinin tersidir. Primal kısıtların sağ taraf sabitleri, dualin amaç katsayılarıdır.

2

Dual değişkenlerin (y1, y2) işaretlerini belirleme.

1. kısıt (<=) olduğu için y1 >= 0 olur. 2. kısıt (>=) olduğu için y2 <= 0 olur.

Maksimizasyon probleminde, standart kısıt (<=) standart değişken (>= 0) üretir. Standart dışı kısıt (>=) ise standart dışı değişken (<= 0) üretir.

3

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

x1 >= 0 -> 1. kısıt (>=) olur. x2 işaretsiz -> 2. kısıt (=) olur. x3 >= 0 -> 3. kısıt (>=) olur.

Minimizasyon dualinde, primaldeki pozitif değişkenler (>= 0) standart kısıt olan (>=) üretir. İşaretsiz değişkenler ise daima eşitlik (=) kısıtı üretir.

4

Katsayı matrisinin transpozunu alarak dual modeli tamamlama.

1. Kısıt: 4y1 + 1y2 >= 10
2. Kısıt: -2y1 + 3y2 = -5
3. Kısıt: 1y1 - 2y2 >= 12

Primal modeldeki değişken katsayıları sütunları, dual modelin satırlarını (kısıtlarını) oluşturur.

Key Concept

Asimetrik Dualite Kuralları ve İşaretsiz Değişkenler

Question 65Question →

Bir kamu kurumu, yürüteceği bir sosyal destek programı için doğrusal programlama yaklaşımıyla bir kaynak tahsis modeli geliştirmiştir. Modelde $x_1$ birinci bölgeye, $x_2$ ise ikinci bölgeye aktarılacak fon birimini (milyon TL) temsil etmektedir.

Kurumun amacı, belirlenen sosyal hedeflere ulaşırken toplam maliyeti minimize etmektir. Kurulan doğrusal programlama modeli aşağıda verilmiştir:

\text{Minimum } Z = 300x_1 + 500x_2

Kısıtlayıcı Şartlar:

x_1 + 2x_2 \geq 16

x_1 + x_2 \leq 12

x_1 \geq 4

x_1, x_2 \geq 0

Bu model grafik çözüm yöntemiyle analiz edildiğinde, optimum çözümde amaç fonksiyonunun alacağı minimum değer kaçtır?

3600

4200

4400

4800

5200

Show answer & explanation

Answer: 4200

Answer

Doğrusal programlama modelinin uygun çözüm alanındaki köşe noktaları hesaplandığında, minimum maliyeti veren noktanın (4, 6) olduğu ve bu noktada değerin 4200 olduğu görülür.

Verilen doğrusal programlama modeli grafik üzerinde çözüldüğünde,

x_1 + 2x_2 \geq 16

,

x_1 + x_2 \leq 12

ve

x_1 \geq 4

kısıtlarının kesiştiği ortak bölge bir üçgendir. Bu üçgenin köşeleri (4, 6), (8, 4) ve (4, 8) koordinatlarında yer alır.

Z = 300x_1 + 500x_2

maliyet fonksiyonu bu köşelerde test edildiğinde minimum değer,

Z = 300(4) + 500(6) = 4200

ile (4, 6) noktasında elde edilir.

Step-by-Step Solution

1

Eşitsizlikleri denkleme çevirerek kısıt doğrularının eksenleri kestiği noktaları bulma.

x_1 + 2x_2 = 16

doğrusu eksenleri (16, 0) ve (0, 8) noktalarında;

x_1 + x_2 = 12

doğrusu (12, 0) ve (0, 12) noktalarında keser.

x_1 = 4

doğrusu yatay eksene diktir.

Grafik üzerinde uygun çözüm bölgesini (olabilirlik alanını) çizebilmek için sınır doğrularının belirlenmesi gerekir.

2

Kısıt yönlerine göre eşitsizlik bölgelerini tarayarak ortak çözüm alanını (uygun bölgeyi) belirleme.

x_1 + 2x_2 \geq 16

doğrusunun üstü,

x_1 + x_2 \leq 12

doğrusunun altı ve

x_1 \geq 4

doğrusunun sağı taranır. Kesişim bölgesi, birinci bölgede yer alan kapalı bir üçgendir.

Tüm kısıtları eşzamanlı olarak sağlayan noktalar kümesini tespit etmek için.

3

Uygun çözüm bölgesini oluşturan üçgenin köşe noktalarının koordinatlarını hesaplama.

1. Kesişim (

x_1=4

ile

x_1+2x_2=16

): (4, 6) noktası.
2. Kesişim (

x_1=4

ile

x_1+x_2=12

): (4, 8) noktası.
3. Kesişim (

x_1+2x_2=16

ile

x_1+x_2=12

): Denklemler ortak çözüldüğünde (8, 4) noktası.

Doğrusal programlamada optimum çözüm, daima uygun çözüm alanının köşe noktalarının en az birinde gerçekleşir.

4

Bulunan köşe noktalarını amaç fonksiyonunda (

Z = 300x_1 + 500x_2

) yerine koyarak minimum değeri tespit etme.

(4, 6) için

Z = 300(4) + 500(6) = 4200

.
(8, 4) için

Z = 300(8) + 500(4) = 4400

.
(4, 8) için

Z = 300(4) + 500(8) = 5200

.
En küçük (minimum) değer 4200 olarak bulunur.

Amacımız maliyeti (Z değerini) minimize eden köşe noktasını bulmaktır.

Key Concept

Grafik Çözüm Yöntemi ile Uygun Çözüm Bölgesinin ve Optimum Noktanın Belirlenmesi

Question 66Question →

Bir büyükşehir belediyesi, toplu taşıma filosu için "Standart" ( $x_1$ ) ve "Körüklü" ( $x_2$ ) olmak üzere iki tip yeni elektrikli otobüs alımı planlamaktadır. Bu otobüslerin günlük işletme maliyetleri standart tip için $1200$ TL, körüklü tip için ise $1800$ TL'dir.

Belediyenin günlük yolcu talebini karşılayabilmesi için bu yeni otobüslerin toplam taşıma kapasitesi en az $4500$ kişi olmalıdır. Bir standart otobüs $80$ kişi, bir körüklü otobüs ise $150$ kişi kapasitelidir. Otobüslerin park edileceği garajın kapasitesi sınırlı olduğundan, alınacak toplam otobüs sayısı $40$ 'ı aşmamalıdır. Ayrıca, dar sokaklarda manevra kabiliyetini korumak amacıyla, alınacak standart otobüs sayısı, körüklü otobüs sayısının en az iki katı olmalıdır.

Belediye, belirtilen tüm kısıtların karşılanmasını sağlarken günlük toplam işletme maliyetini en küçükleyen doğrusal programlama modelini kurmak istemektedir.

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

\begin{array}{l} \max Z = 1200x_1 + 1800x_2 \\ \text{Kısıtlar:} \\ 80x_1 + 150x_2 \geq 4500 \\ x_1 + x_2 \leq 40 \\ x_1 - 2x_2 \geq 0 \\ x_1, x_2 \geq 0 \end{array}

\begin{array}{l} \min Z = 1200x_1 + 1800x_2 \\ \text{Kısıtlar:} \\ 80x_1 + 150x_2 \leq 4500 \\ x_1 + x_2 \geq 40 \\ x_1 - 2x_2 \leq 0 \\ x_1, x_2 \geq 0 \end{array}

\begin{array}{l} \min Z = 1200x_1 + 1800x_2 \\ \text{Kısıtlar:} \\ 80x_1 + 150x_2 \geq 4500 \\ x_1 + x_2 \leq 40 \\ x_1 - 2x_2 \geq 0 \\ x_1, x_2 \geq 0 \end{array}

\begin{array}{l} \min Z = 1200x_1 + 1800x_2 \\ \text{Kısıtlar:} \\ 80x_1 + 150x_2 \geq 4500 \\ x_1 + x_2 \leq 40 \\ 2x_1 - x_2 \geq 0 \\ x_1, x_2 \geq 0 \end{array}

\begin{array}{l} \min Z = 1200x_1 + 1800x_2 \\ \text{Kısıtlar:} \\ 80x_1 + 150x_2 \geq 4500 \\ x_1 + x_2 \leq 40 \\ x_1 - x_2 \geq 2 \end{array}

Show answer & explanation

Answer: $\begin{array}{l} \min Z = 1200x_1 + 1800x_2 \\ \text{Kısıtlar:} \\ 80x_1 + 150x_2 \geq 4500 \\ x_1 + x_2 \leq 40 \\ x_1 - 2x_2 \geq 0 \\ x_1, x_2 \geq 0 \end{array}$

Answer

Amaç fonksiyonunun maliyet minimizasyonu (min Z) olduğu, kapasitenin en az 4500 (büyük eşit), araç sayısının en fazla 40 (küçük eşit) olduğu ve standart otobüs sayısının körüklünün en az iki katı olması kısıtının

x_1 - 2x_2 \geq 0

olarak modellendiği, ayrıca negatif olmama koşullarını barındıran seçenektir.

İşletme maliyeti minimize edilmek istendiği için amaç fonksiyonu

\min Z = 1200x_1 + 1800x_2

olmalıdır. Toplam kapasitenin en az 4500 kişi olması gerektiği için

80x_1 + 150x_2 \geq 4500

eşitsizliği, toplam araç sayısının 40'ı aşmaması gerektiğinden

x_1 + x_2 \leq 40

eşitsizliği yazılır. Standart otobüs sayısının (

x_1

), körüklü otobüs sayısının (

x_2

) en az iki katı olması şartı

x_1 \geq 2x_2

yani

x_1 - 2x_2 \geq 0

şeklinde modellenir. Otobüs sayısı reel bir fiziksel nesne olduğundan ve eksi değer alamayacağından

x_1, x_2 \geq 0

negatif olmama kısıtları da modele mutlaka eklenmelidir.

Step-by-Step Solution

1

Amaç fonksiyonunu oluşturma.

Maliyet en küçüklenmek istendiği için

\min Z = 1200x_1 + 1800x_2

fonksiyonu yazılır.

Problemde günlük işletme maliyetini en küçükleyen model kurulması istenmektedir.

2

Fiziksel kapasite ve limit kısıtlarını yazma.

Kapasite için

80x_1 + 150x_2 \geq 4500

ve garaj limiti için

x_1 + x_2 \leq 40

kısıtları elde edilir.

Metindeki 'en az 4500 kişi' ifadesi

\geq

(büyük eşit), '40'ı aşmamalıdır' ifadesi ise

\leq

(küçük eşit) kullanılarak matematikselleştirilir.

3

Oran kısıtını ve varsayım kısıtlarını modelleme.

x_1 \geq 2x_2

ifadesinden

x_1 - 2x_2 \geq 0

kısıtı elde edilir ve nicelik ifade edildiğinden

x_1, x_2 \geq 0

şartı eklenir.

Standart otobüs sayısının körüklü otobüsün iki katı olması gerektiği sözel orantısı mantıksal bir denkleme dönüştürülür ve araç sayısı negatif olamaz.

Key Concept

Sözel İfadelerin Doğrusal Eşitsizliklere Çevrilmesi ve Model Kurulumu

Question 67Question →

Bir kamu yatırım planlama teşkilatı, bütçe kısıtları altında beş farklı bölgesel altyapı projesi ( $X_1, X_2, \dots, X_5$ ) arasından seçim yapacaktır. Projelerin uygulanabilmesi için her bir projenin "ya tamamen finanse edilmesi ya da hiç finanse edilmemesi" gerekmektedir. Ayrıca, çevresel düzenlemeler gereği 1. ve 2. projelerden "en fazla birinin" desteklenmesi şartı bulunmaktadır.

Bir proje analiz uzmanı, problemi standart bir Doğrusal Programlama (DP) modeli olarak kurgularken, karar değişkenlerini $0 \leq X_j \leq 1$ ( $j=1,2,\dots,5$ ) şeklinde sürekli (kesirli değer alabilen) tanımlamış ve "en fazla birinin desteklenmesi" koşulunu modele $X_1 \cdot X_2 = 0$ kısıtı ile eklemiştir.

Uzman tarafından kurulan bu modelin, Doğrusal Programlama'nın temel varsayımları ve mantıksal modelleme kuralları açısından değerlendirilmesiyle ilgili aşağıdakilerden hangisi kesinlikle doğrudur?

Kısmi finansmanın yasaklanmış olması, modelin "Bölünebilirlik" varsayımının gerçek hayatla çelişmesine neden olmuştur. Ayrıca

X_1 \cdot X_2 = 0

ifadesi doğrusal bir denklem olmadığından "Toplanabilirlik" ve "Oransallık" varsayımlarını bozar; bu durum

X_1, X_2 \in \{0, 1\}

olmak üzere

X_1 + X_2 \leq 1

kısıtıyla Tamsayılı Programlama kapsamında modellenmelidir.

Değişkenlerin

0 \leq X_j \leq 1

aralığında sürekli tanımlanması DP'nin "Bölünebilirlik" varsayımı gereği doğrudur. Ancak

X_1 \cdot X_2 = 0

koşulu "Belirlilik" varsayımını zedeler; modelin geçerli olması için kısıt yönünün

X_1 + X_2 \geq 1

şeklinde düzeltilmesi yeterlidir.

Projelerin "ya hep ya hiç" mantığıyla seçilecek olması DP'nin "Oransallık" varsayımını bozar. Mantıksal kısıtların doğrusal modele entegrasyonu için

X_1 \cdot X_2 = 0

yerine, sürekli değişkenler korunarak kısıt yönünün değiştirilmesiyle elde edilen

X_1 = 1 - X_2

denklemi kullanılmalıdır.

Kısıt denkleminde karar değişkenlerinin çarpım durumunda olması, kaynakların ortak kullanıldığını gösterdiğinden "Toplanabilirlik" varsayımına uygundur. Temel hata, bütçe kısıtlarında eşitsizlik (

\leq

) yerine kesin eşitlik (

=

) kullanılarak "Bölünebilirlik" varsayımının ihlal edilmesidir.

Kısmi yatırım yapılamaması "Belirlilik" varsayımının doğrudan ihlalidir. Birbirini dışlayan projelerin seçimi sürekli değişkenlerle modellenemez; ancak tamsayı kullanılmadan

X_1 + X_2 \geq 0

gibi her zaman sağlanan kısıtlarla dolaylı olarak modelde ifade edilmelidir.

Show answer & explanation

Answer: Kısmi finansmanın yasaklanmış olması, modelin "Bölünebilirlik" varsayımının gerçek hayatla çelişmesine neden olmuştur. Ayrıca $X_1 \cdot X_2 = 0$ ifadesi doğrusal bir denklem olmadığından "Toplanabilirlik" ve "Oransallık" varsayımlarını bozar; bu durum $X_1, X_2 \in \{0, 1\}$ olmak üzere $X_1 + X_2 \leq 1$ kısıtıyla Tamsayılı Programlama kapsamında modellenmelidir.

Answer

Doğru yanıt, kısmi finansmanın yasaklanmasını 'Bölünebilirlik' varsayımının ihlali olarak tanımlayan ve kısıtlardaki çarpım formunun doğrusallığı bozduğunu belirterek 0-1 tamsayılı

X_1 + X_2 \leq 1

eşitsizliğini öneren seçenektir.

Doğrusal Programlamanın dört temel varsayımı vardır. 'Bölünebilirlik', değişkenlerin kesirli olabilmesini ifade eder. Yatırımların kısmi yapılamaması bu varsayımı gerçeklikten koparır ve tamsayılı modellemeyi zorunlu kılar. Kısıtlardaki

X_1 \cdot X_2 = 0

ifadesi değişkenlerin çarpımını içerdiğinden doğrusallığı sağlayan 'Toplanabilirlik' ve 'Oransallık' aksiyomlarını tamamen bozar. 'En fazla biri' mantıksal kısıtının 0-1 tamsayılı değişkenlerle

X_1 + X_2 \leq 1

şeklinde kurgulanması literatürdeki yegane doğru yaklaşımdır.

Step-by-Step Solution

1

Problemin doğası ile karar değişkeni tanımlamasını (Bölünebilirlik varsayımı) karşılaştırmak

Projenin kısmi fonlanamaması gerçeği, uzmanın değişkenleri

0 \leq X_j \leq 1

olarak kesirli (sürekli) almasıyla çelişmektedir. Bu, Bölünebilirlik varsayımının fiilen işlemediği anlamına gelir.

Bölünebilirlik varsayımı, karar değişkenlerinin her türlü kesirli değeri (örneğin 0.45) alabileceğini söyler. Tamsayılı doğası olan (var/yok) kararlarda bu varsayım geçersizdir.

2

Uzmanın kurduğu

X_1 \cdot X_2 = 0

kısıtını Toplanabilirlik ve Oransallık açısından analiz etmek

Değişkenlerin birbiriyle çarpılması doğrusal bir fonksiyon değildir. Toplanabilirlik varsayımı

f(x+y) = f(x)+f(y)

formunu, Oransallık ise

f(kx)=kf(x)

formunu gerektirir.

DP modellerinde amaç fonksiyonu ve kısıtlar doğrusal (lineer) olmalıdır. Çarpım terimleri her iki temel doğrusallık aksiyomunu da ihlal eder.

3

'En fazla biri' şeklindeki mantıksal koşulun doğru matematiksel modelini kurmak

Kararlar ikili yapıda olduğu için Sıfır-Bir (0-1) tamsayılı değişkenler kullanılmalı ve mantıksal önerme

X_1 + X_2 \leq 1

eşitsizliğine dönüştürülmelidir.

X_1, X_2 \in \{0, 1\}

şartı altında toplamın 1'den küçük veya eşit olması, ikisinin birden aynı anda 1 değerini alamamasını (ikisi birden seçilemez) garanti eder.

Key Concept

Doğrusal Programlama Varsayımları ve Sıfır-Bir Modelleme

Estimated Time:2m 0s

Question 68Question →

Bir büyükşehir belediyesinin katı atık yönetim merkezinde, üç farklı geri dönüşüm sürecinin entegrasyonu için geliştirilen doğrusal programlama primal modeli aşağıda verilmiştir:

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

Kısıtlayıcı fonksiyonlar:

3x_1 + 2x_2 - 4x_3 \le 500

x_1 - 3x_2 + 2x_3 \ge 150

2x_1 + x_2 + 5x_3 = 300

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

Buna göre, verilen primal modele karşılık gelen dual model aşağıdakilerden hangisidir?

\text{Min } W = 500y_1 + 150y_2 + 300y_3

3y_1 + y_2 + 2y_3 \ge 12

2y_1 - 3y_2 + y_3 = 8

-4y_1 + 2y_2 + 5y_3 \ge -5

y_1 \ge 0, \ y_2 \le 0, \ y_3 \text{ işaretsiz}

\text{Min } W = 500y_1 + 150y_2 + 300y_3

3y_1 + y_2 + 2y_3 \ge 12

2y_1 - 3y_2 + y_3 \ge 8

-4y_1 + 2y_2 + 5y_3 \ge -5

y_1 \ge 0, \ y_2 \ge 0, \ y_3 \text{ işaretsiz}

\text{Min } W = 500y_1 + 150y_2 + 300y_3

3y_1 + y_2 + 2y_3 \le 12

2y_1 - 3y_2 + y_3 = 8

-4y_1 + 2y_2 + 5y_3 \le -5

y_1 \ge 0, \ y_2 \le 0, \ y_3 \text{ işaretsiz}

\text{Min } W = 500y_1 + 150y_2 + 300y_3

3y_1 + y_2 + 2y_3 \ge 12

2y_1 - 3y_2 + y_3 = 8

-4y_1 + 2y_2 + 5y_3 \ge -5

y_1 \ge 0, \ y_2 \ge 0, \ y_3 \ge 0

\text{Maks } W = 500y_1 + 150y_2 + 300y_3

3y_1 + y_2 + 2y_3 \le 12

2y_1 - 3y_2 + y_3 = 8

-4y_1 + 2y_2 + 5y_3 \le -5

y_1 \ge 0, \ y_2 \le 0, \ y_3 \text{ işaretsiz}

Show answer & explanation

Answer: $\text{Min } W = 500y_1 + 150y_2 + 300y_3$
$3y_1 + y_2 + 2y_3 \ge 12$
$2y_1 - 3y_2 + y_3 = 8$
$-4y_1 + 2y_2 + 5y_3 \ge -5$
$y_1 \ge 0, \ y_2 \le 0, \ y_3 \text{ işaretsiz}$

Answer

Doğru dual modelde amaç fonksiyonu Min W = 500y_1 + 150y_2 + 300y_3 şeklinde olmalı; x_2 işaretsiz olduğu için 2. kısıt eşitlik (= 8) içermeli ve primal kısıtların yönlerine bağlı olarak y_1 ≥ 0, y_2 ≤ 0, y_3 işaretsiz olarak tanımlanmalıdır.

Doğru seçenekte dualite kuralları eksiksiz işletilmiştir. Primal model Maksimum olduğu için dual model Minimum yönlüdür. Primal değişken olan

x_2

işaretsiz olduğu için 2. dual kısıt eşitliktir (

=

). Primal kısıtlardan ikincisi

\ge

olduğu için dual değişken

y_2 \le 0

, üçüncü kısıt eşitlik olduğu için dual değişken

y_3

işaretsiz olarak doğru şekilde ifade edilmiştir.

Step-by-Step Solution

1

Amaç fonksiyonunun yönünü ve katsayılarını belirleme.

Primal model Maksimum olduğu için dual model Minimum olmalıdır. Primalin sağ taraf sabitleri dualin amaç fonksiyonu katsayıları olur: Min W = 500y_1 + 150y_2 + 300y_3.

Dualite teoremine göre primal ve dual modeller zıt amaçlıdır (Maksimum -> Minimum).

2

Dual değişkenlerin (y_1, y_2, y_3) işaret sınırlarını belirleme.

1. primal kısıt (≤) -> y_1 ≥ 0
2. primal kısıt (≥) -> y_2 ≤ 0 (Maksimum modelde standart olmayan yön)
3. primal kısıt (=) -> y_3 işaretsiz (serbest).

Maksimum modelin kısıt yönleri, dual model değişkenlerinin işaret durumunu tanımlar.

3

Dual kısıtların yönünü ve katsayılarını oluşturma.

Primal değişken sütunları dual kısıt satırlarını oluşturur.
x_1 ≥ 0 -> 3y_1 + y_2 + 2y_3 ≥ 12
x_2 işaretsiz -> 2y_1 - 3y_2 + y_3 = 8
x_3 ≥ 0 -> -4y_1 + 2y_2 + 5y_3 ≥ -5

Primal değişkenlerin (x_j) işaret sınırlamaları, dual modeldeki karşılık gelen kısıtların eşitsizlik yönünü belirler.

Key Concept

Doğrusal programlamada primal modelden dual modele geçiş kuralları (kısıt yönü ve değişken işareti ilişkileri).

Estimated Time:2m 30s

Question 69Question →

Bir tarım kooperatifi, farklı gübre türlerinin mahsul verimi üzerindeki etkisini optimize etmek amacıyla bir matematiksel model kurmaktadır. Yapılan saha testlerinde, toprağa uygulanan gübre miktarı ( $x_j$ ) arttıkça elde edilen ek ürün miktarının başlangıçta sabit bir oranla arttığı, ancak belirli bir dozajdan sonra toprağın doygunluğa ulaşması nedeniyle her ilave gübre biriminin sağladığı marjinal verim artışının giderek düştüğü (azalan verimler kanunu) tespit edilmiştir.

Buna rağmen modelleme uzmanı, gübre miktarı ile mahsul verimi arasındaki bu ilişkiyi tüm kullanım düzeyleri için tek bir sabit katsayı ( $c_j$ ) kullanarak Doğrusal Programlama modelinin amaç fonksiyonuna yansıtmıştır.

Bu durum, Doğrusal Programlama modellemesindeki temel varsayımlardan hangisinin ihlal edildiğini göstermektedir?

Oransallık

Toplanabilirlik

Bölünebilirlik

Belirlilik

Negatif olmama

Show answer & explanation

Answer: Oransallık

Answer

Doğrusal Programlama modellemesindeki temel varsayımlardan ihlal edilen 'Oransallık' varsayımıdır.

Oransallık (Proportionality) varsayımı, her bir karar değişkeninin modelin amaç fonksiyonuna ve kısıtlara olan katkısının, o değişkenin değeri ile tam bir doğru orantı içinde olmasını gerektirir. Matematiksel olarak bu, katkı katsayısının (

c_j

) değişkenin aldığı değerden (üretim miktarından, kullanılan kaynaktan vs.) bağımsız olarak sabit kalması demektir. Senaryoda belirtilen 'azalan verimler kanunu' (marjinal verim düşüşü), değişken arttıkça katkının yavaşladığını ve ilişkinin doğrusal olmadığını gösterir. Sabit bir katsayı kullanmak, ölçeğe göre değişen bu eğimi yoksaymak anlamına gelir ve doğrudan oransallık varsayımını ihlal eder.

Step-by-Step Solution

1

Sorudaki sistemin matematiksel davranışını analiz etme

Gübre miktarı (

x_j

) arttıkça mahsul verimindeki artışın sabit kalmadığı ve giderek azaldığı (doğrusal olmayan ilişki) tespit edilmiştir.

Modelin gerçek hayatla uyuşmadığı kırılma noktasını bulmak.

2

Sabit katsayı kullanımının modeldeki karşılığını değerlendirme

Uzman, doğrusal olmayan bu ilişkiyi amaç fonksiyonunda

c_j \cdot x_j

şeklinde sabit bir katkı eğimi ile doğrusal olarak temsil etmiştir.

Doğrusal programlamanın matematiksel formülasyon yapısını anlamak.

3

Durumu LP'nin temel varsayımlarıyla eşleştirme

Bir değişkenin amaca veya kaynak tüketimine katkısının kendi miktarıyla doğru orantılı olması (katsayının sabit kalması) zorunluluğu 'Oransallık' varsayımıdır. Azalan marjinal verim bu varsayıma tamamen aykırıdır.

Tespit edilen matematiksel sapmanın teorik adını ve karşılığını bulmak.

Key Concept

Oransallık Varsayımı

Estimated Time:1m 30s

Question 70Question →

Bir kamu kurumu, iki farklı hizmet bölgesine ( $x_1$ ve $x_2$ ) tahsis edeceği kaynakların maksimizasyonu için bir doğrusal programlama modeli kurmuş ve simpleks yöntemiyle aşağıdaki optimal tabloya ulaşmıştır:

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

Tabloda $s_1$ ve $s_2$ gevşek (aylak) değişkenleri, $Z$ ise amaç fonksiyonu satırını ( $Z_j - C_j$ formatında) göstermektedir.

Kurum yöneticisi, mevcut plandan farklı ancak aynı maksimum faydayı sağlayan alternatif bir hizmet dağılım planı olup olmadığını analiz etmek istemektedir.

Buna göre, alternatif optimal çözüme geçiş yapıldığında, $x_2$ hizmet bölgesine ayrılacak miktar (yeni $x_2$ değeri) aşağıdakilerden hangisi olur?

0

3/2

5/2

4

5

Show answer & explanation

Answer: $4$

Answer

Alternatif optimal çözümde

x_2

hizmet bölgesine ayrılacak yeni miktar

4

olur.

Alternatif optimal çözümün tespit edilebilmesi için

Z

satırında (

Z_j - C_j

) temel dışı olup değeri

0

olan değişkene bakılır. Bu değişken

s_2

'dir ve temele girmelidir. Oran testi yapıldığında,

x_2

satırındaki

s_2

sütunu değeri (

-1/2

) negatif olduğu için oran testine katılmaz.

x_1

satırı için oran

(5/2) / (1/2) = 5

olur. Bu durumda temelden

x_1

çıkar ve pivot eleman

1/2

olarak belirlenir. Yeni

s_2

satırının çözüm değeri

5/2 \times 2 = 5

olur.

x_2

'nin yeni değerini bulmak için satır işlemi yapılır: Yeni

x_2

Çözüm

= 3/2 - (-1/2) \times 5 = 3/2 + 5/2 = 4

olarak hesaplanır.

Step-by-Step Solution

1

Alternatif çözüm için temele girecek değişkeni belirle.

Temele giren değişken

s_2

'dir.

Optimal tabloda

Z

satırındaki katsayıların tümü

\geq 0

'dır. Ancak temel olmayan

s_2

değişkeninin

Z

satırındaki katsayısı

0

'dır. Bu durum alternatif bir optimal çözümün varlığını gösterir.

2

Oran testi ile temelden çıkacak değişkeni ve pivot elemanı bul.

Çıkan değişken

x_1

, pivot eleman

1/2

'dir.

Oran testi, Çözüm değerlerinin giren değişken sütunundaki pozitif elemanlara bölünmesiyle yapılır.

x_2

satırı için katsayı (

-1/2

) negatif olduğundan dikkate alınmaz.

x_1

satırı için oran:

(5/2) / (1/2) = 5

'tir. Tek pozitif oran

x_1

satırında olduğundan

x_1

çıkar.

3

Yeni tablo için temele giren

s_2

satırının çözüm değerini hesapla.

Yeni

s_2

satırı çözüm değeri

5

'tir.

Yeni satır değerleri, eski satır değerlerinin pivot elemana bölünmesiyle bulunur.

(5/2) / (1/2) = 5/2 \times 2/1 = 5

.

4

Yeni tabloda

x_2

satırının güncel çözüm değerini hesapla.

Yeni

x_2

değeri

4

'tür.

Yeni satır = Eski satır - (Giren sütundaki kesişim elemanı

\times

Yeni pivot satırı) formülü uygulanır. Yeni

x_2

Çözüm =

3/2 - (-1/2) \times 5 = 3/2 + 5/2 = 8/2 = 4

.

Key Concept

Simpleks Yönteminde Alternatif Optimal Çözüm ve Tablo Güncelleme

Question 71Question →

Bir büyükşehir belediyesi, şehir içi ulaşımda kullanılmak üzere elektrikli ( $x_1$ ) ve hibrit ( $x_2$ ) otobüslerden oluşan yeni bir filo kurmayı planlamaktadır. Belediyenin amacı, günlük maksimum çevresel faydayı ( $Z$ ) sağlamaktır. Bu probleme ait doğrusal programlama modeli aşağıda verilmiştir:

Maksimum \ Z = 80x_1 + 30x_2

Kısıtlar:

2x_1 + x_2 \leq 20 \quad \text{(Bütçe kısıtı)}

x_1 \leq 8 \quad \text{(Şarj altyapısı kısıtı)}

x_1 + x_2 \geq 10 \quad \text{(Minimum hizmet kısıtı)}

x_1, x_2 \geq 0

Buna göre, bu model grafik çözüm yöntemiyle çözüldüğünde elde edilen optimum çözümdeki $x_1$ , $x_2$ değerleri ve maksimum çevresel fayda ( $Z$ ) sırasıyla aşağıdakilerden hangisidir?

x_1 = 8, \ x_2 = 4, \ Z = 760

x_1 = 10, \ x_2 = 0, \ Z = 800

x_1 = 8, \ x_2 = 2, \ Z = 700

x_1 = 0, \ x_2 = 20, \ Z = 600

x_1 = 0, \ x_2 = 10, \ Z = 300

Show answer & explanation

Answer: $x_1 = 8, \ x_2 = 4, \ Z = 760$

Answer

Optimum çözüm, her iki aracın da kısıtlar dahilinde en uygun kombinasyonunu veren

x_1 = 8, \ x_2 = 4, \ Z = 760

noktasıdır.

Modelin uygun çözüm alanı, verilen üç kısıtın da aynı anda sağlandığı kapalı bölgedir. Bu bölgenin köşe noktaları

(0, 20)

,

(0, 10)

,

(8, 2)

ve

(8, 4)

'tür. Bu değerler

Z = 80x_1 + 30x_2

amaç fonksiyonunda yerine konduğunda sırasıyla

600

,

300

,

700

ve

760

değerlerini verir. Modelin amacı maksimizasyon olduğu için en yüksek değer olan

Z = 760

sonucunu veren

x_1 = 8

ve

x_2 = 4

noktası optimum çözümdür.

Step-by-Step Solution

1

Kısıt eşitsizliklerinin koordinat sisteminde doğrular halinde çizilmesi ve eksenleri kestiği noktaların bulunması.

1. doğru (

2x_1 + x_2 = 20

):

(10,0)

ve

(0,20)

noktalarından geçer. 2. doğru (

x_1 = 8

): y eksenine paraleldir. 3. doğru (

x_1 + x_2 = 10

):

(10,0)

ve

(0,10)

noktalarından geçer.

Grafik çözüm yönteminde uygun çözüm alanının sınırlarını belirlemek.

2

Eşitsizlik yönlerine (

\leq

ve

\geq

) göre uygun çözüm bölgesinin (taralı alanın) belirlenmesi.

Alan,

2x_1 + x_2 \leq 20

doğrusunun altında,

x_1 \leq 8

doğrusunun solunda ve

x_1 + x_2 \geq 10

doğrusunun üstünde kalan kapalı çokgendir.

Tüm kısıtları aynı anda sağlayan noktalar kümesini tespit etmek.

3

Uygun çözüm alanını çevreleyen çokgenin köşe noktalarının koordinatlarının hesaplanması.

Kesişim noktalarından 4 adet uygun köşe bulunur:

(0, 20)

,

(0, 10)

,

(8, 2)

ve

(8, 4)

.

Doğrusal programlamada optimum çözüm daima uygun çözüm alanının köşe noktalarının birinde (veya bir ayrıtı üzerinde) gerçekleşir.

4

Bulunan köşe noktalarının

Z = 80x_1 + 30x_2

amaç fonksiyonunda yerine konarak en yüksek (maksimum) değerin tespit edilmesi.

(0, 20)

için

Z=600

,

(0, 10)

için

Z=300

,

(8, 2)

için

Z=700

ve

(8, 4)

için

Z=760

bulunur. Maksimum değer 760'tır.

Modelin amacı çevresel faydayı (

Z

) maksimize etmektir.

Key Concept

Doğrusal Programlamada Grafik Çözüm Yöntemi ile Maksimizasyon

Question 72Question →

Bir havacılık şirketi, yeni nesil bir uçağın aerodinamik performans katsayısını en çoklamak amacıyla tasarım parametreleri ( $x_1, x_2, x_3$ ) üzerinden aşağıdaki doğrusal programlama primal modelini formüle etmiştir:

Maksimum $Z = 12x_1 + 18x_2 + 10x_3$

Kısıtlar:
$3x_1 + 4x_2 - 2x_3 \leq 50$
$x_1 - 2x_2 + 5x_3 \geq 20$
$2x_1 + x_2 + 3x_3 = 35$
$x_1 \geq 0, x_2 \geq 0, x_3 \text{ işaretsiz}$

Buna göre, verilen primal modelin dual (ikili) modeli aşağıdakilerden hangisidir?

Min

W = 50y_1 + 20y_2 + 35y_3

3y_1 + y_2 + 2y_3 \geq 12

4y_1 - 2y_2 + y_3 \geq 18

-2y_1 + 5y_2 + 3y_3 = 10

y_1 \geq 0, y_2 \leq 0, y_3 \text{ işaretsiz}

Min

W = 50y_1 + 20y_2 + 35y_3

3y_1 + y_2 + 2y_3 \geq 12

4y_1 - 2y_2 + y_3 \geq 18

-2y_1 + 5y_2 + 3y_3 = 10

y_1 \geq 0, y_2 \geq 0, y_3 \text{ işaretsiz}

Min

W = 50y_1 + 20y_2 + 35y_3

3y_1 + y_2 + 2y_3 \geq 12

4y_1 - 2y_2 + y_3 \geq 18

-2y_1 + 5y_2 + 3y_3 \geq 10

y_1 \geq 0, y_2 \leq 0, y_3 \text{ işaretsiz}

Min

W = 50y_1 + 20y_2 + 35y_3

3y_1 + y_2 + 2y_3 \geq 12

4y_1 - 2y_2 + y_3 \geq 18

-2y_1 + 5y_2 + 3y_3 = 10

y_1 \leq 0, y_2 \geq 0, y_3 \text{ işaretsiz}

Min

W = 50y_1 + 20y_2 + 35y_3

3y_1 + y_2 + 2y_3 \geq 12

4y_1 - 2y_2 + y_3 \geq 18

-2y_1 + 5y_2 + 3y_3 \geq 10

y_1 \geq 0, y_2 \geq 0, y_3 \geq 0

Show answer & explanation

Answer: Min $W = 50y_1 + 20y_2 + 35y_3$
$3y_1 + y_2 + 2y_3 \geq 12$
$4y_1 - 2y_2 + y_3 \geq 18$
$-2y_1 + 5y_2 + 3y_3 = 10$
$y_1 \geq 0, y_2 \leq 0, y_3 \text{ işaretsiz}$

Answer

Doğru dual modelde amaç fonksiyonu minimizasyon yönündedir, ilk iki kısıt büyük eşit, üçüncü kısıt eşitlik şeklindedir ve dual değişken işaretleri sırasıyla

y_1 \geq 0

,

y_2 \leq 0

,

y_3

işaretsiz olarak belirlenmiştir.

Doğru dual modelde, primal amaç fonksiyonu maksimizasyon olduğundan dual minimizasyon şeklindedir. Primal kısıtların sağ taraf sabitleri (50, 20, 35) dual amaç fonksiyonunun katsayılarıdır. Primaldeki değişkenlerin işaretleri (

x_1 \geq 0

,

x_2 \geq 0

,

x_3

işaretsiz) sırasıyla dual kısıtların yönlerini (

\geq

,

\geq

,

=

) belirler. Ayrıca primal kısıtların yönleri (

\leq

,

\geq

,

=

) dual değişkenlerin işaretlerini (

y_1 \geq 0

,

y_2 \leq 0

,

y_3

işaretsiz) doğrudan belirler. İşlem adımlarının tamamen doğru uygulandığı tek model budur.

Step-by-Step Solution

1

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

Primal model maksimizasyon olduğundan dual model minimizasyon olmalıdır. Dual amaç fonksiyonu

W = 50y_1 + 20y_2 + 35y_3

şeklini alır.

Primal modelin kısıtlarının sağ taraf sabitleri (50, 20, 35), dual modelin amaç fonksiyonu katsayılarını oluşturur.

2

Dual kısıt denklemlerinin katsayılarını ve yönlerini oluşturma

Kısıtlar sırasıyla

3y_1 + y_2 + 2y_3 \geq 12

,

4y_1 - 2y_2 + y_3 \geq 18

ve

-2y_1 + 5y_2 + 3y_3 = 10

olarak elde edilir.

Primal katsayılar matrisinin transpozu alınır. Primalde

x_1 \geq 0

ve

x_2 \geq 0

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

\geq

,

x_3

işaretsiz olduğu için üçüncü dual kısıt

=

işaretine sahip olur.

3

Dual değişkenlerin işaretlerini belirleme

y_1 \geq 0

,

y_2 \leq 0

ve

y_3

işaretsiz olarak belirlenir.

Maksimizasyon probleminde

\leq

yönlü 1. kısıt için

y_1 \geq 0

,

\geq

yönlü 2. kısıt için

y_2 \leq 0

ve

=

yönlü 3. kısıt için

y_3

işaretsiz (urs) olmalıdır.

Key Concept

Dualite Kavramı ve Dual Model Kurulumu (Primal-Dual İşaret Kuralları)

Question 73Question →

Bir kamu kurumu, iki farklı bölgeye ulaştırılacak yardım malzemelerinin dağıtımını planlamak için aşağıdaki doğrusal programlama modelini kurgulamıştır. Modelin amacı, ulaştırılan malzemelerin yaratacağı toplam sosyal faydayı maksimize etmektir:

\text{Maksimum } Z = 30x_1 + 40x_2

\text{Kısıtlar:}

2x_1 + x_2 \geq 12

x_1 + 3x_2 = 15

x_1, x_2 \geq 0

Bu model, Büyük-M (Big-M) yöntemi ile çözülmek üzere standart forma dönüştürülüp başlangıç simpleks tablosu oluşturulacaktır. Modelin maksimizasyon problemi olduğu dikkate alınarak yapay değişkenlere amaç fonksiyonunda $M > 0$ olmak üzere uygun ceza katsayıları atanmıştır.

Buna göre, oluşturulan başlangıç simpleks tablosunda $x_1$ ve $x_2$ karar değişkenlerine ait $Z_j - C_j$ (net değerlendirme) satırı değerleri sırasıyla aşağıdakilerden hangisidir?

-3M - 30

ve

-4M - 40

3M + 30

ve

4M + 40

3M - 30

ve

4M - 40

-M - 30

ve

-3M - 40

-3M

ve

-4M

Show answer & explanation

Answer: $-3M - 30$ ve $-4M - 40$

Answer

Başlangıç tablosunda

x_1

ve

x_2

değişkenlerinin

Z_j - C_j

değerleri sırasıyla

-3M - 30

ve

-4M - 40

'tır.

Büyük-M yönteminde maksimizasyon problemleri için yapay değişkenlere amaç fonksiyonunda -M katsayısı atanır. Başlangıç tablosunda temel değişkenler A_1 ve A_2 olup, her ikisinin de amaç fonksiyonu katsayısı -M'dir. Bu durumda x_1 sütunundaki katsayılar (2 ve 1) -M ile çarpılıp toplanarak Z_1 = -3M bulunur, C_1 değeri olan 30 çıkarıldığında -3M - 30 elde edilir. Benzer şekilde x_2 sütunundaki katsayılar (1 ve 3) -M ile çarpılıp toplanarak Z_2 = -4M bulunur, C_2 değeri olan 40 çıkarıldığında Z_2 - C_2 = -4M - 40 sonucuna ulaşılır.

Step-by-Step Solution

1

Modeli yapay değişkenler kullanarak standart forma dönüştür.

Maksimum Z =

30x_1 + 40x_2 + 0s_1 - MA_1 - MA_2

2x_1 + x_2 - s_1 + A_1 = 12

x_1 + 3x_2 + A_2 = 15

Büyük eşit (

\geq

) kısıtına bir artık değişken (

-s_1

) ve bir yapay değişken (

+A_1

) eklenirken; eşitlik (

=

) kısıtına yalnızca bir yapay değişken (

+A_2

) eklenir. Maksimizasyon için yapay değişken cezaları

-M

olmalıdır.

2

Başlangıç simpleks tablosu için temel değişkenleri ve bunların amaç fonksiyonu katsayılarını (

C_B

) belirle.

Temel değişkenler:

A_1

ve

A_2

. Her ikisinin de

C_B

katsayısı

-M

'dir.

İlk çözümde birim matrisi oluşturan

A_1

ve

A_2

sisteme girer.

3

x_1

değişkeni için

Z_1 - C_1

değerini hesapla.

Z_1 = (-M \times 2) + (-M \times 1) = -3M

.

C_1 = 30

.

Z_1 - C_1 = -3M - 30

.

Net değerlendirme satırı, sütun katsayılarının

C_B

ile çarpımlarının toplamından (

Z_j

), değişkenin kendi amaç fonksiyonu katsayısının (

C_j

) çıkarılmasıyla elde edilir.

4

x_2

değişkeni için

Z_2 - C_2

değerini hesapla.

Z_2 = (-M \times 1) + (-M \times 3) = -4M

.

C_2 = 40

.

Z_2 - C_2 = -4M - 40

.

Aynı

Z_j - C_j

mantığı

x_2

sütunu için de uygulanarak tablonun ilgili hücresi doldurulur.

Key Concept

Büyük-M Yönteminde Başlangıç Tablosu Kurulumu ve Z Satırı Denklemi

Question 74Question →

Bir İl Tarım ve Orman Müdürlüğü, toprak yapısı bozulan tarım arazilerinin ıslahı için "Nitrat-Bazlı" ( $x_1$ ) ve "Fosfat-Bazlı" ( $x_2$ ) hammaddeleri karıştırarak özel bir gübre harmanı hazırlayacaktır. Bu işlem için belirlenen maliyet ve içerik koşulları şöyledir:

- Nitrat-bazlı hammaddenin ton maliyeti $300$ TL, fosfat-bazlı hammaddenin ton maliyeti ise $400$ TL'dir. Müdürlük, harmanlama işlemini en düşük maliyetle gerçekleştirmeyi hedeflemektedir.
- Hazırlanacak harman, hektar başına en az $80$ birim azot ve en az $90$ birim fosfor ihtiyacını karşılamalıdır.
- Bir ton nitrat-bazlı hammadde $4$ birim azot ve $3$ birim fosfor içerirken; bir ton fosfat-bazlı hammadde $2$ birim azot ve $5$ birim fosfor içermektedir.
- Taşıma ve uygulama kapasitesi kısıtları nedeniyle, hektar başına uygulanacak toplam gübre harmanı miktarı $25$ tonu aşmamalıdır.
- Çevresel düzenlemeler gereği, kullanılacak nitrat-bazlı hammadde miktarı, fosfat-bazlı hammadde miktarının $3$ katını aşmamalıdır.

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

\begin{aligned} \min Z &= 300x_1 + 400x_2 \\ \text{Kısıtlar:} \\ 4x_1 + 2x_2 &\geq 80 \\ 3x_1 + 5x_2 &\geq 90 \\ x_1 + x_2 &\leq 25 \\ x_1 - 3x_2 &\leq 0 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \max Z &= 300x_1 + 400x_2 \\ \text{Kısıtlar:} \\ 4x_1 + 2x_2 &\geq 80 \\ 3x_1 + 5x_2 &\geq 90 \\ x_1 + x_2 &\leq 25 \\ x_1 - 3x_2 &\leq 0 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \min Z &= 300x_1 + 400x_2 \\ \text{Kısıtlar:} \\ 4x_1 + 2x_2 &\leq 80 \\ 3x_1 + 5x_2 &\leq 90 \\ x_1 + x_2 &\geq 25 \\ x_1 - 3x_2 &\leq 0 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \min Z &= 300x_1 + 400x_2 \\ \text{Kısıtlar:} \\ 4x_1 + 2x_2 &\geq 80 \\ 3x_1 + 5x_2 &\geq 90 \\ x_1 + x_2 &\leq 25 \\ 3x_1 - x_2 &\leq 0 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \min Z &= 300x_1 + 400x_2 \\ \text{Kısıtlar:} \\ 4x_1 + 2x_2 &\geq 80 \\ 3x_1 + 5x_2 &\geq 90 \\ x_1 + x_2 &\leq 25 \\ x_1 - 3x_2 &\geq 0 \end{aligned}

Show answer & explanation

Answer: $\begin{aligned} \min Z &= 300x_1 + 400x_2 \\ \text{Kısıtlar:} \\ 4x_1 + 2x_2 &\geq 80 \\ 3x_1 + 5x_2 &\geq 90 \\ x_1 + x_2 &\leq 25 \\ x_1 - 3x_2 &\leq 0 \\ x_1, x_2 &\geq 0 \end{aligned}$

Answer

Modelin doğru formülasyonu maliyet minimizasyonunu (

\min Z

), doğru yönlü besin ve kapasite eşitsizliklerini,

x_1 - 3x_2 \leq 0

oran kısıtını ve pozitiflik kısıtlarını içeren seçenektir.

Doğru model; amaç fonksiyonunun

\min Z

olmasını, asgari ihtiyaçlar için

\geq

, azami sınırlar için

\leq

eşitsizliklerinin kullanılmasını ve

x_1 \leq 3x_2

(

x_1 - 3x_2 \leq 0

) oran kısıtı ile birlikte pozitiflik kısıtının eksiksiz olarak denkleme dökülmesini sağlamaktadır.

Step-by-Step Solution

1

Amaç fonksiyonunu belirle.

Amaç, gübre harmanının maliyetini en aza indirmek olduğundan fonksiyon

\min Z = 300x_1 + 400x_2

olarak yazılır.

Problem metninde açıkça 'en düşük maliyetle gerçekleştirmek' ifadesi geçmektedir.

2

Besin içerik kısıtlarını oluştur.

Azot için

4x_1 + 2x_2 \geq 80

ve fosfor için

3x_1 + 5x_2 \geq 90

eşitsizlikleri elde edilir.

Her iki besin maddesi için de karşılanması gereken 'en az' değerler verilmiştir, bu durum

\geq

(büyük eşit) sembolü gerektirir.

3

Kapasite (tonaj) kısıtını oluştur.

x_1 + x_2 \leq 25

eşitsizliği yazılır.

Hektar başına uygulanacak toplam miktarın 25 tonu 'aşmamalıdır' kısıtı bir üst sınır (

\leq

) belirtir.

4

Çevresel oran kısıtını ve varsayılan kısıtları modele ekle.

Oran kısıtı

x_1 \leq 3x_2

(veya

x_1 - 3x_2 \leq 0

) olarak modellenir ve sonuna

x_1, x_2 \geq 0

kısıtı eklenir.

Nitrat miktarının (

x_1

), fosfat miktarının (

x_2

) 3 katını aşmaması mantıksal olarak

x_1

'in

3x_2

'den küçük veya eşit olması anlamına gelir. Üretim miktarları negatif olamayacağından pozitiflik koşulu şarttır.

Key Concept

Doğrusal programlama problemlerinde sözel ifadeleri (en az, en çok, katı, maliyet/kar) doğru matematiksel sembollerle modele dönüştürme

Question 75Question →

Bir kamu kurumunun lojistik ağındaki dağıtım maliyetlerini en küçükleme (minimizasyon) amacıyla kurduğu doğrusal programlama modelinin Simpleks algoritması ile çözümünde nihai (optimal) tabloya ulaşılmıştır.

Tabloda incelenen değerlere göre şu iki durum tespit edilmiştir:
I. Temel dışı (non-basic) bir karar değişkeninin net değerlendirme satırındaki ( $Z_j - C_j$ ) değeri tam olarak sıfırdır.
II. İlgili temel dışı değişkenin sütununda yer alan tüm yer değiştirme (teknolojik) katsayıları sıfır veya negatiftir ( $\leq 0$ ).

Buna göre, modellenen problem ve elde edilen çözüm durumu hakkında aşağıdakilerden hangisi kesinlikle doğrudur?

Problemin uygun çözüm alanı sınırsızdır, ancak amaç fonksiyonu değeri sınırlıdır ve birbirine eşit amaç fonksiyonu değeri veren sonsuz sayıda alternatif optimal çözüm bulunur.

Problemde amaç fonksiyonunu eksi sonsuza götüren bir sınırsızlık durumu vardır ve problemin herhangi bir optimal çözümü bulunamaz.

Simpleks algoritmasının önceki adımlarında en küçük oran testinde eşitlik çıkmış olup, çözüm dejenereliğe (bozulmaya) uğradığı için iterasyonlar tıkanmıştır.

Kurulan modeldeki kısıtlar birbiriyle çelişmektedir, bu nedenle problemin uygun çözüm alanı boştur ve yapay değişkenler temelden çıkmamıştır.

Uygun çözüm alanı her yönden kapalı (sınırlı) bir dışbükey çokgendir ve problemin yalnızca tek bir köşede gerçekleşen benzersiz (unique) bir optimal çözümü vardır.

Show answer & explanation

Answer: Problemin uygun çözüm alanı sınırsızdır, ancak amaç fonksiyonu değeri sınırlıdır ve birbirine eşit amaç fonksiyonu değeri veren sonsuz sayıda alternatif optimal çözüm bulunur.

Answer

Problemin uygun çözüm alanı sınırsızdır, ancak amaç fonksiyonu değeri sınırlıdır ve birbirine eşit amaç fonksiyonu değeri veren sonsuz sayıda alternatif optimal çözüm bulunur.

Verilen iki durumun birleşimi, yöneylem araştırmasında özel ve ileri düzey bir senaryoyu tanımlar. Optimal bir tabloda temel dışı bir karar değişkeninin net değerlendirme (fırsat maliyeti) değerinin sıfır olması, bu problemin çoklu (alternatif) optimal çözüme sahip olduğunu kanıtlar. Bu değişken temele sokulmak istendiğinde, sütunundaki tüm teknolojik katsayıların sıfır veya negatif olması ise oran testi yapılamayacağını, dolayısıyla o eksen boyunca çözüm alanının sınırsız (açık) olduğunu gösterir. Ancak değişken temele girse bile amaç fonksiyonuna net katkısı sıfır olduğundan, çözüm alanı sonsuza gitmesine rağmen amaç fonksiyonu değeri bozulmaz ve sabit kalır. Matematiksel ve grafiksel olarak bu durum; sınırsız bir uygun çözüm bölgesi üzerinde, amaç fonksiyonu doğrusuna paralel olan ve sonsuza uzanan bir optimal çözümler ışını (ray) elde edildiğini kesin olarak doğrular.

Step-by-Step Solution

1

Birinci öncülün (Temel dışı değişken için

Z_j - C_j = 0

) analiz edilmesi.

Problemin alternatif (çoklu) optimal çözümü olduğu tespit edilir.

Optimal bir tabloda temel dışı bir değişkenin amaca katkısının sıfır olması, bu değişkenin temele girmesi halinde amaç fonksiyonu değerinin değişmeyeceğini (mevcut optimal değerin korunacağını) gösterir.

2

İkinci öncülün (Sütundaki katsayıların

\leq 0

olması) analiz edilmesi.

Uygun çözüm alanının o değişken yönünde sınırsız olduğu tespit edilir.

Temele girecek değişkenin sütununda hiç pozitif katsayı olmaması, Simpleks oran testinin yapılamayacağı ve değişkenin mevcut kısıtları ihlal etmeden sonsuza kadar artırılabileceği anlamına gelir.

3

İki bilginin sentezlenerek çözümün genel yorumunun yapılması.

Uygun çözüm alanının sınırsız olduğu, ancak bu yönde ilerlerken amaç fonksiyonu değerinin değişmemesi sebebiyle amaç fonksiyonunun sınırlı kaldığı sonucuna varılır.

Değişken sonsuza giderken amaç fonksiyonuna katkısı sıfır olduğundan, amaç değeri sonsuza gitmez. Bu durum, sınırsız bir uygun çözüm alanı içinde, amaç fonksiyonu ile çakışan ve sonsuza uzanan bir 'alternatif optimal çözümler ışını' (ray) oluşturur.

Key Concept

Özel Durumlarda Çoklu Çözüm ve Sınırsız Alan İlişkisi

Question 76Question →

Bir devlet hastanesi, evde bakım hizmetleri kapsamında iki farklı sağlık paketi (Paket A ve Paket B) hazırlamaktadır. Paket A'nın ( $x_1$ ) birim başına toplumsal faydası $50$ birim, Paket B'nin ( $x_2$ ) ise $40$ birimdir. Paketlerin hazırlanması için gerekli kaynaklar ve kapasite kısıtları şu şekildedir:

* Bir adet Paket A için $2$ saat hemşire süresi ve $10$ birim tıbbi malzeme gereklidir.
* Bir adet Paket B için $1$ saat hemşire süresi ve $20$ birim tıbbi malzeme gereklidir.
* Toplam kullanılabilir hemşire süresi en çok $100$ saat, toplam tıbbi malzeme miktarı ise en fazla $500$ birimdir.

Hastanenin toplam toplumsal faydayı en üst düzeye çıkarmayı amaçladığı bu durum için kurulan doğrusal programlama modeli aşağıdakilerden hangisidir?

\begin{aligned} \text{Maks } Z &= 50x_1 + 40x_2 \\ \text{kısıtlar:} \\ 2x_1 + x_2 &\leq 100 \\ 10x_1 + 20x_2 &\leq 500 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \text{Min } Z &= 50x_1 + 40x_2 \\ \text{kısıtlar:} \\ 2x_1 + x_2 &\leq 100 \\ 10x_1 + 20x_2 &\leq 500 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \text{Maks } Z &= 50x_1 + 40x_2 \\ \text{kısıtlar:} \\ 2x_1 + x_2 &\geq 100 \\ 10x_1 + 20x_2 &\geq 500 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \text{Maks } Z &= 40x_1 + 50x_2 \\ \text{kısıtlar:} \\ 2x_1 + x_2 &\leq 100 \\ 10x_1 + 20x_2 &\leq 500 \\ x_1, x_2 &\geq 0 \end{aligned}

\begin{aligned} \text{Maks } Z &= 50x_1 + 40x_2 \\ \text{kısıtlar:} \\ 2x_1 + x_2 &\leq 100 \\ 10x_1 + 20x_2 &\leq 500 \\ x_1, x_2 &\in \{0, 1\} \end{aligned}

Show answer & explanation

Answer: $\begin{aligned} \text{Maks } Z &= 50x_1 + 40x_2 \\ \text{kısıtlar:} \\ 2x_1 + x_2 &\leq 100 \\ 10x_1 + 20x_2 &\leq 500 \\ x_1, x_2 &\geq 0 \end{aligned}$

Answer

Toplumsal faydayı maksimize eden, kısıtların üst sınırlarını (<=) doğru yansıtan ve değişkenlerin negatif olamayacağını (>= 0) belirten model doğru cevaptır.

Doğru modelde, amaç fonksiyonu Paket A (

50

) ve Paket B (

40

) birim faydalarını maksimize edecek şekilde kurulmuştur. Hemşire süresi (

2x_1 + x_2

) ve malzeme miktarı (

10x_1 + 20x_2

) toplam kapasiteyi aşamayacağı için küçük-eşit (

\leq

) işareti ile sınırlandırılmıştır.

Step-by-Step Solution

1

Karar değişkenlerini tanımla.

x_1

: Paket A sayısı,

x_2

: Paket B sayısı.

Modelin temel bileşenlerini belirlemek için değişkenler netleştirilmelidir.

2

Amaç fonksiyonunu oluştur.

\text{Maks } Z = 50x_1 + 40x_2

Problemde toplumsal faydanın 'en üst düzeye çıkarılması' istendiğinden maksimizasyon (Maks) modeli kurulur.

3

Kısıtlayıcı denklemleri yaz.

Hemşire süresi:

2x_1 + x_2 \leq 100

; Tıbbi malzeme:

10x_1 + 20x_2 \leq 500

.

Kaynaklar sınırlı olduğundan (en çok/en fazla), tüketilen toplam kaynak miktarı mevcut kapasiteden küçük veya eşit olmalıdır.

4

Negatif olmama kısıtını ekle.

x_1, x_2 \geq 0

.

Üretilen paket sayısı fiziksel olarak negatif bir değer alamaz.

Key Concept

Doğrusal programlama modeli; bir amaç fonksiyonu, kaynak kısıtları ve işaret kısıtlarından oluşan matematiksel bir yapıdır.

Practice More

Değişkenlerin işaret kısıtlarını (pozitiflik, tamsayılılık) ve kısıt yönlerini belirten anahtar kelimelere odaklanmak model kurma hatalarını azaltır.

Estimated Time:1m 30s

Question 77Question →

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

Maksimum \ Z = 10x_1 + 15x_2

Kısıtlar:

x_1 + x_2 \leq 5

x_2 \geq 2

x_1, x_2 \geq 0

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

30

50

60

75

45

Show answer & explanation

Answer: 75

Answer

En iyi amaç fonksiyonu değeri 75 olarak bulunur.

Optimum değer, uygun çözüm alanının uç noktalarından biri olan (0, 5) noktasında gerçekleşmektedir. Bu noktada x1 değeri 0 ve x2 değeri 5 olduğunda amaç fonksiyonu Z = 10(0) + 15(5) = 75 değerine ulaşır ve bu bölgedeki diğer köşe noktalarından (30 ve 60) daha büyüktür.

Step-by-Step Solution

1

Kısıt doğrularını çizerek uygun çözüm alanını belirleyin.

x_1 + x_2 = 5

doğrusu eksenleri

(5,0)

ve

(0,5)

noktalarında keser.

x_2 = 2

doğrusu ise yatay bir doğrudur.

Grafik çözüm yönteminde ilk adım, kısıtların sınırlarını belirleyerek uygun bölgeyi bulmaktır.

2

Eşitsizlik yönlerine göre uygun bölgeyi tarayın.

x_1 + x_2 \leq 5

doğrunun alt tarafını,

x_2 \geq 2

ise doğrunun üst tarafını gösterir.

x_1 \geq 0

dikey eksenin sağ tarafıdır.

Tüm kısıtların aynı anda sağlandığı bölge uygun çözüm alanıdır.

3

Uygun çözüm alanının köşe noktalarını tespit edin.

Köşe noktaları:

(0, 2)

,

(0, 5)

ve

(3, 2)

noktalarıdır.

Doğrusal programlama teorisine göre optimum çözüm mutlaka uygun bölgenin bir köşe noktasındadır.

4

Köşe noktalarını amaç fonksiyonunda yerine koyarak değerleri hesaplayın.

Z(0, 2) = 10(0) + 15(2) = 30

,

Z(0, 5) = 10(0) + 15(5) = 75

,

Z(3, 2) = 10(3) + 15(2) = 60

.

Maksimum amaç fonksiyonu değerini bulmak için tüm uç noktalar test edilir.

Key Concept

Grafik çözüm yönteminde optimum değer, kısıtların oluşturduğu uygun bölgenin köşe noktalarından birinde bulunur.

Question 78Question →

Bir doğrusal programlama probleminin simpleks yöntemiyle çözüm sürecinde elde edilen bir ara tabloda, amaca en fazla katkıyı sağlayacak giren değişken $x_1$ olarak belirlenmiştir. Bu değişkene ait anahtar sütundaki katsayılar sırasıyla $s_1$ , $s_2$ ve $s_3$ satırlarında $-2$ , $0$ ve $3$ olarak bulunmuştur. İlgili satırların çözüm (sağ taraf) sabitleri ise sırasıyla $10$ , $15$ ve $12$ 'dir.

Buna göre, oran testi (minimum oran kuralı) uygulaması ve temelden çıkacak değişkenin belirlenmesi ile ilgili aşağıdaki ifadelerden hangisi doğrudur?

Yalnızca pozitif katsayılar dikkate alındığından oran testi sadece

s_3

satırı için yapılır ve çıkan değişken

s_3

olarak belirlenir.

Tüm oranlar cebirsel olarak karşılaştırıldığından,

10/(-2) = -5

en küçük değer kabul edilir ve çıkan değişken

s_1

olur.

Katsayıların mutlak değerleri üzerinden işlem yapıldığından, sıfıra bölme hariç tutularak

|10/(-2)| = 5

ile

12/3 = 4

oranları karşılaştırılır ve çıkan değişken

s_3

olur.

Anahtar sütunda negatif ve sıfır değerleri bir arada bulunduğundan oran testi yapılamaz ve problemin sınırsız çözüme sahip olduğu sonucuna varılır.

Sağ taraf sabitleri sırasıyla katsayılara bölünür, ancak sıfıra bölme işlemi belirsizlik yarattığından iterasyon durdurularak mevcut çözüm optimal kabul edilir.

Show answer & explanation

Answer: Yalnızca pozitif katsayılar dikkate alındığından oran testi sadece $s_3$ satırı için yapılır ve çıkan değişken $s_3$ olarak belirlenir.

Answer

Yalnızca pozitif katsayılar dikkate alındığından oran testi sadece

s_3

satırı için yapılır ve çıkan değişken

s_3

olarak belirlenir.

Simpleks yönteminde, temelden çıkacak değişkeni belirlemek için yapılan oran testinde (minimum oran kuralı), sağ taraf sabitleri *yalnızca* anahtar sütundaki kesinlikle pozitif (sıfırdan büyük) katsayılara bölünür. Negatif ve sıfır olan katsayılar oran testine dahil edilmez ve bu satırlar çıkan değişken olamazlar. Verilen senaryoda sadece

s_3

satırındaki katsayı (

3

) pozitif olduğundan, bölme işlemi sadece bu satır için gerçekleştirilir (

12/3 = 4

). Hesaplanabilen tek geçerli oran bu olduğu için, minimum oran kuralı gereği çıkan değişken doğrudan

s_3

olarak belirlenir.

Step-by-Step Solution

1

Anahtar sütundaki katsayıların işaretlerini analiz et.

s_1

satırı için

-2

(negatif),

s_2

satırı için

0

(sıfır),

s_3

satırı için

3

(pozitif).

Oran testine hangi satırların dahil edileceğini belirlemek için katsayıların sıfırdan büyük olup olmadığı kontrol edilmelidir.

2

Uygun satırlar için oran testini (Sağ Taraf Sabiti / Katsayı) uygula.

s_1

ve

s_2

satırları katsayıları

\leq 0

olduğu için elenir. Sadece

s_3

satırı için hesaplama yapılır:

12 / 3 = 4

.

Temel değişkenlerin negatif değer almasını önlemek için sadece pozitif katsayılara bölme işlemi yapılır.

3

Hesaplanan pozitif oranlar arasından en küçük olanı seçerek çıkan değişkeni belirle.

Tek pozitif oran

s_3

satırına ait olduğundan (

4

), minimum oran bu satırdadır ve çıkan değişken

s_3

olur.

Minimum oran kuralı, yeni çözümü kısıtlara uygun (feasible) bölgede tutmak için gereklidir.

Key Concept

Simpleks Yönteminde Oran Testi (Minimum Oran Kuralı)

Question 79Question →

Endüstriyel bir sürecin performansını en üst düzeye çıkarmayı hedefleyen bir doğrusal modelin çözüm adımlarından birinde aşağıdaki ara tablo elde edilmiştir:

Temel	$Z$	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	Çözüm
$s_1$	$0$	$4$	$0$	$1$	$-1$	$0$	$28$
$x_2$	$0$	$2$	$1$	$0$	$1$	$0$	$10$
$s_3$	$0$	$3$	$0$	$0$	$0$	$1$	$18$
$Z$	$1$	$-6$	$0$	$0$	$5$	$0$	$50$

Standart simpleks algoritması kuralları işletilerek tablonun güncellenmesi gerekmektedir.

Buna göre, bir sonraki aşamaya geçildiğinde (yeni tablo oluşturulduğunda), $Z$ hedef fonksiyonu ile $s_3$ temel değişkeninin alacağı yeni değerler sırasıyla aşağıdakilerden hangisidir?

86

ve

0

110

ve

-12

20

ve

33

80

ve

3

92

ve

-3

Show answer & explanation

Answer: $80$ ve $3$

Answer

Hedef fonksiyonu (

Z

)

80

,

s_3

temel değişkeni ise

3

değerini alacaktır.

Enbüyükleme modelinde

Z

satırındaki en negatif katsayı (

-6

)

x_1

'e aittir, bu nedenle anahtar sütun

x_1

'dir. Oran testi uygulandığında pozitif değerler için oranlar hesaplanır (

28/4=7

,

10/2=5

,

18/3=6

). En küçük oran

5

olduğu için

x_2

satırı temelden çıkar. Pivot eleman

2

'dir. Yeni pivot satırının (

x_1

) çözüm değeri

10/2=5

olur. Gauss-Jordan yok etme yöntemiyle

Z

satırı güncellendiğinde

50 - (-6) \times 5 = 80

elde edilir.

s_3

satırı güncellendiğinde ise

18 - 3 \times 5 = 3

elde edilir.

Step-by-Step Solution

1

Anahtar sütunun (giren değişkenin) belirlenmesi

Enbüyükleme problemi olduğu için

Z

satırında en negatif katsayıya sahip olan

x_1

sütunu (

-6

) anahtar sütundur.

Simpleks algoritmasında amaca en büyük katkıyı sağlayacak olan değişken temele alınır.

2

Oran testi ile anahtar satırın (çıkan değişkenin) belirlenmesi

Çözüm sütunu değerleri

x_1

sütunundaki pozitif katsayılara bölünür:

s_1

için

28/4=7

,

x_2

için

10/2=5

,

s_3

için

18/3=6

. En küçük oran

5

olduğundan

x_2

satırı anahtar satırdır. Kesişimdeki

2

değeri pivot elemandır.

Çözümün uygunluk alanından çıkmaması (negatif değer almaması) için en küçük pozitif oranı veren değişken temelden çıkarılır.

3

Yeni pivot satırının oluşturulması

Temele giren

x_1

satırının yeni çözüm değeri, eski

x_2

satırının çözüm değerinin pivot elemana bölünmesiyle elde edilir:

10 / 2 = 5

.

Giren değişkenin temel değişken olması için kendi sütununda

1

katsayısına sahip olması gerekir.

4

Z

ve

s_3

satırlarının yeni değerlerinin hesaplanması

Yeni

Z

çözümü

= 50 - (-6) \times 5 = 80

. Yeni

s_3

çözümü

= 18 - 3 \times 5 = 3

olarak hesaplanır.

Anahtar sütundaki diğer katsayıların sıfırlanması için temel Gauss-Jordan yok etme operasyonları uygulanır.

Key Concept

Simpleks tablosunda iterasyon adımları, oran testi ve Gauss-Jordan satır operasyonları

Estimated Time:2m 30s

Doğrusal Programlama

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes