Examkin

Yapay Değişkenli Yöntemler (Büyük-M ve İki Evreli)

11 questions

Question 1Question →

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

Minimize Z=2x1+5x2Z = 2x_1 + 5x_2

Kısıtlar:
x1+x2≥2x_1 + x_2 \geq 2
2x1+x2≤62x_1 + x_2 \leq 6
x1,x2≥0x_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 (ZZ satırı) x1x_1 değişkeninin katsayısı aşağıdakilerden hangisidir?

Show answer & explanation

Answer: M−2M - 2

Answer

Başlangıç simpleks tablosundaki amaç satırında x1x_1 değişkeninin katsayısı M−2M - 2 olur.
Minimizasyon probleminde Z=2x1+5x2+Ma1Z = 2x_1 + 5x_2 + Ma_1 olan amaç fonksiyonunda, a1=2−x1−x2+s1a_1 = 2 - x_1 - x_2 + s_1 eşitliği yerine yazıldığında Z=(2−M)x1+(5−M)x2+Ms1+2MZ = (2-M)x_1 + (5-M)x_2 + Ms_1 + 2M elde edilir. Simpleks tablosundaki amaç satırı formatında (ZZ terimi katsayısı 1 olacak şekilde tüm değişkenlerin sol tarafa toplanması) x1x_1 değişkeninin katsayısı −(2−M)-(2-M) yani M−2M-2 olur.

Step-by-Step Solution

1
Kısıtların standart forma dönüştürülmesi
x1+x2−s1+a1=2x_1 + x_2 - s_1 + a_1 = 2 ve 2x1+x2+s2=62x_1 + x_2 + s_2 = 6
Büyük eşit (>=) kısıtı için bir artık değişken (s1s_1) ve başlangıç temel uygun çözümü sağlamak için bir yapay değişken (a1a_1) eklenmelidir.
2
Amaç fonksiyonunun ceza parametresi (M) ile kurulması
Minimize Z=2x1+5x2+Ma1Z = 2x_1 + 5x_2 + Ma_1
Minimizasyon problemlerinde Büyük-M yönteminde yapay değişkenler amaç fonksiyonuna +M+M katsayısı ile eklenir.
3
Yapay değişkenin amaç satırından elenmesi
Z=2x1+5x2+M(2−x1−x2+s1)⇒Z=(2−M)x1+(5−M)x2+Ms1+2MZ = 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 a1a_1 değişkeni amaç fonksiyonundan yok edilir.
4
Tablo formatına (Z satırı) dönüştürme
Z+(M−2)x1+(M−5)x2−Ms1=2MZ + (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.

Key Concept

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

Alternative Method

Matris formunda amaç satırı katsayılarını hesaplamak için cBB−1Aj−cjc_B B^{-1} A_j - c_j formülü de kullanılabilir.
Estimated Time:2m 0s
Question 2Question →

Bir karar verici, aşağıdaki doğrusal programlama modelini Büyük-M (Çok Büyük Katsayılar) yöntemini kullanarak çözmek amacıyla standart forma dönüştürmek istemektedir:

Maks Z=2x1+4x2Maks \ Z = 2x_1 + 4x_2
Kısıtlar:
x1+x2≥10x_1 + x_2 \geq 10
x1,x2≥0x_1, x_2 \geq 0

MM çok büyük bir pozitif sayıyı temsil ettiğine göre; bu yönteme uygun olarak modele dahil edilmesi gereken ek değişkenler ve oluşturulacak yeni amaç fonksiyonu (ZyeniZ_{yeni}) aşağıdakilerin hangisinde doğru olarak verilmiştir?

Show answer & explanation

Answer: s1s_1 artık (surplus) ve a1a_1 yapay değişkenleri modele dahil edilir; Zyeni=2x1+4x2−Ma1Z_{yeni} = 2x_1 + 4x_2 - Ma_1

Answer

Modelde s1s_1 artık ve a1a_1 yapay değişkenleri kullanılmalı; amaç fonksiyonu Zyeni=2x1+4x2−Ma1Z_{yeni} = 2x_1 + 4x_2 - Ma_1 şeklinde kurulmalıdır.
Doğru seçenek olan artık değişken çıkarma ve yapay değişken ekleme işlemi, 'büyük eşit' kısıtlarının standart formdaki temel gerekliliğidir. Maksimizasyon problemlerinde yapay değişkenlerin katsayısının -M olarak seçilmesi, optimal çözümde bu değişkenlerin değerinin sıfır olmasını zorlayan bir ceza mekanizmasıdır.

Step-by-Step Solution

1
Kısıt yapısını analiz et.
x1+x2≥10x_1 + x_2 \geq 10 kısıtı 'büyük eşit' tipindedir.
Yapay değişkenli yöntemler, başlangıçta uygun bir temel çözüm bulunamadığında (özellikle >= veya = kısıtlarında) kullanılır.
2
Kısıtı eşitlik haline getir.
x1+x2−s1+a1=10x_1 + x_2 - s_1 + a_1 = 10
>= kısıtını dengelemek için bir artık (surplus) değişken (s1s_1) çıkarılır. Ancak başlangıçta orijin (0,00,0) uygun olmadığından bir yapay değişken (a1a_1) eklenerek başlangıç temeli oluşturulur.
3
Amaç fonksiyonunu ceza katsayısı ile güncelle.
Maksimizasyon için −Ma1-Ma_1 eklenir.
Büyük-M yönteminde amaç, yapay değişkenleri mümkün olan en kısa sürede temelden çıkarmaktır. Maksimizasyon probleminde bunu sağlamak için yapay değişken çok küçük (negatif büyük) bir değerle çarpılır.

Key Concept

Büyük-M Yönteminde Değişken Dönüşümleri

Practice More

İki evreli (Two-Phase) yöntemde birinci evrenin amaç fonksiyonunun nasıl kurulduğunu inceleyerek bu iki yöntemi karşılaştırabilirsiniz.
Estimated Time:1m 30s
Question 3Question →

Bir karar verici, aşağıdaki doğrusal programlama modelini İki Evreli (Two-Phase) yöntemini kullanarak çözmek istemektedir:

Minimize Z=4x1+x2Z = 4x_1 + x_2

Kısıtlar:
3x1+x2≥63x_1 + x_2 \geq 6
4x1+3x2≤124x_1 + 3x_2 \leq 12
x1,x2≥0x_1, x_2 \geq 0

Bu model standart forma dönüştürüldüğünde (sis_i dolgu/artık değişkenleri, aia_i yapay değişkenleri temsil etmektedir), İki Evreli yöntemin 1. Evre (Phase 1) amaç fonksiyonu aşağıdakilerden hangisidir?

Show answer & explanation

Answer: Minimize W=a1W = a_1

Answer

İki Evreli yöntemin 1. Evre amaç fonksiyonu Minimize W=a1W = a_1 şeklindedir.
İki Evreli yöntemde, problemin başlangıçta uygun bir temel çözümü yoksa (≥ veya = kısıtları nedeniyle), yapay değişkenler eklenir. 1. Evrenin amacı bu yapay değişkenleri sıfıra indirerek orijinal problem için uygun bir bölge bulmaktır. Bu nedenle amaç fonksiyonu her zaman yapay değişkenlerin toplamını minimize edecek şekilde (Minimize W=∑aiW = \sum a_i) kurulur. Bu modelde sadece a1a_1 değişkeni olduğu için fonksiyon 'Minimize W=a1W = a_1' olur.

Step-by-Step Solution

1
Kısıtları standart forma dönüştürün.
3x1+x2−s1+a1=63x_1 + x_2 - s_1 + a_1 = 6 ve 4x1+3x2+s2=124x_1 + 3x_2 + s_2 = 12 elde edilir.
Büyük eşit (≥) kısıtı için artık değişken çıkarılıp yapay değişken eklenirken, küçük eşit (≤) kısıtı için sadece dolgu değişkeni eklenir.
2
Yapay değişkenleri belirleyin.
Sadece ilk kısıtta bir yapay değişken (a1a_1) bulunmaktadır.
Yapay değişkenler sadece başlangıç temel uygun çözümü sağlamak için gerekli olan kısıtlara (≥ ve =) eklenir.
3
1. Evre amaç fonksiyonunu kurun.
Minimize W=a1W = a_1
İki Evreli yöntemin 1. Evresinde temel amaç, tüm yapay değişkenleri sistemden çıkarmak için onların toplamını minimize etmektir.

Key Concept

İki Evreli Yöntemde 1. Evre Amaç Fonksiyonu Kurulumu
Question 4Question →

Bir doğrusal programlama modeli Büyük-M (Big-M) yöntemi kullanılarak çözülmek istenmektedir. Problemin amaç fonksiyonu minimizasyon (minZmin Z) yönünde ise, modele eklenen aia_i yapay değişkenlerinin amaç fonksiyonundaki katsayısı aşağıdakilerden hangisidir?

Show answer & explanation

Answer: +M+M

Answer

Minimizasyon problemlerinde yapay değişkenlerin amaç fonksiyonundaki katsayısı pozitif yönde çok büyük bir değer olan +M+M olmalıdır.
Doğrusal programlamada Büyük-M yöntemi uygulanırken, minimizasyon amaçlı modellerde yapay değişkenlerin (artificial variables) amaç fonksiyonundaki katsayısı +M+M olarak belirlenir. Buradaki +M+M değeri, problemin asıl değişkenlerinin katsayılarından çok daha büyük pozitif bir sayıyı temsil eder. Amaç, bu değişkenleri temel çözümde tutmanın maliyetini aşırı derecede artırarak algoritmayı bu değişkenleri sıfıra indirmeye ve temelden çıkarmaya zorlamaktır.

Step-by-Step Solution

1
Problemin amaç yönünü belirleyin.
Problem minimizasyon (minZmin Z) yönündedir.
Yapay değişkenlerin ceza katsayısının işareti amaç fonksiyonunun yönüne bağlıdır.
2
Yapay değişkenlerin fonksiyonunu analiz edin.
Yapay değişkenler uygun bir başlangıç çözümü sağlamak için eklenir ancak optimum çözümde değerlerinin sıfır olması istenir.
Bu değişkenlerin çözümde kalması durumunda çözümün uygun olmadığı anlaşılır.
3
Cezalandırma kuralını uygulayın.
Minimizasyon probleminde maliyeti artırmak (cezalandırmak) için değişkene pozitif ve çok büyük bir katsayı (+M+M) verilir.
Böylece simpleks algoritması bu değişkenleri temelden çıkarmaya zorlanır.

Key Concept

Büyük-M Yönteminde Ceza Katsayıları

Practice More

Aynı problemin maksimizasyon durumunda ceza katsayısının nasıl değişeceğini ve kısıt tiplerine göre (==, ≥\geq) hangi değişkenlerin eklendiğini gözden geçirebilirsiniz.
Estimated Time:45s
Question 5Question →

Bir karar verici, aşağıda verilen doğrusal programlama modelini İki Evreli (Two-Phase) yöntem kullanarak çözmek istemektedir:

Minimize Z=5x1+4x2Z = 5x_1 + 4x_2

Kısıtlar:
x1+2x2=8x_1 + 2x_2 = 8
3x1+x2≥63x_1 + x_2 \geq 6
x1,x2≥0x_1, x_2 \geq 0

Buna göre, bu problemin çözümünde kullanılacak olan Birinci Evre (Phase 1) amaç fonksiyonu (WW) aşağıdakilerden hangisidir? (Not: aia_i yapay değişkenleri, s1s_1 ise artık değişkeni temsil etmektedir.)

Show answer & explanation

Answer: Minimize W=a1+a2W = a_1 + a_2

Answer

Birinci evre amaç fonksiyonu, modele eklenen tüm yapay değişkenlerin toplamının minimize edilmesiyle oluşur (Minimize W=a1+a2W = a_1 + a_2).
İki Evreli yöntemde, Birinci Evre'nin (Phase 1) tek amacı modele eklenen yapay değişkenleri sıfıra indirerek orijinal problem için uygun bir temel başlangıç çözümü bulmaktır. Bu nedenle, orijinal amaç fonksiyonu (ZZ) geçici olarak devre dışı bırakılır ve yerine modele eklenen tüm yapay değişkenlerin toplamından oluşan yeni bir minimizasyon fonksiyonu (W=∑aiW = \sum a_i) tanımlanır. Bu problemde hem '==' hem de '≥\geq' kısıtları için birer yapay değişken (a1a_1 ve a2a_2) gerektiğinden, doğru fonksiyon yapay değişkenlerin toplamının minimizasyonudur.

Step-by-Step Solution

1
Kısıtları standart forma dönüştürerek yapay değişken ihtiyacını belirleyin.
Birinci kısıt (==) için bir yapay değişken (a1a_1) eklenir: x1+2x2+a1=8x_1 + 2x_2 + a_1 = 8. İkinci kısıt (≥\geq) için bir artık değişken (s1s_1) çıkarılır ve bir yapay değişken (a2a_2) eklenir: 3x1+x2−s1+a2=63x_1 + x_2 - s_1 + a_2 = 6.
Eşitlik ve büyük-eşit kısıtları, başlangıç simpleks tablosu için bir birim matris oluşturabilmek adına yapay değişken gerektirir.
2
Birinci Evre (Phase 1) amaç fonksiyonunu kurgulayın.
Minimize W=a1+a2W = a_1 + a_2
İki evreli yöntemin ilk aşamasında, orijinal amaç fonksiyonu yerine sadece yapay değişkenlerin toplamını sıfıra indirmeyi hedefleyen yeni bir fonksiyon kullanılır.

Key Concept

İki Evreli Yöntemde Birinci Evre Amaç Fonksiyonu Kurulumu

Hints

1
Hangi kısıt türlerinin (=,≤,≥=, \leq, \geq) yapay değişken gerektirdiğini hatırlayın.
2
İki evreli yöntemin ilk aşamasında orijinal amaç fonksiyonu katsayılarının (5 ve 4) tamamen göz ardı edildiğini unutmayın.

Practice More

Yapay değişkenlerin Birinci Evre sonunda sıfıra düşmemesi durumunda problemin uygun çözüm alanı (feasible region) hakkında ne söylenebileceğini araştırın.
Estimated Time:1m 30s
Question 6Question →

Aşağıdaki maksimizasyon problemi Büyük-M (Big-M) yöntemi kullanılarak çözülmek istenmektedir:

Maksimum Z=5x1+3x2\text{Maksimum } Z = 5x_1 + 3x_2
Kısıtlar:\text{Kısıtlar:}
x1+2x2=10x_1 + 2x_2 = 10
x1,x2≥0x_1, x_2 \geq 0

Bu model Büyük-M yöntemi kurallarına göre standart forma dönüştürüldüğünde, amaç fonksiyonuna eklenen a1a_1 yapay değişkeninin katsayısı aşağıdakilerden hangisi olur? (MM çok büyük bir pozitif sayıyı temsil etmektedir.)

Show answer & explanation

Answer: −M-M

Answer

Maksimizasyon problemlerinde yapay değişkenlerin amaç fonksiyonu katsayısı −M-M olmalıdır.
Maksimizasyon problemlerinde amaç ZZ değerini en büyük yapmaktır. Yapay değişkenlerin gerçek modelde bir yeri yoktur; bu nedenle çözümden atılmaları gerekir. Bunu sağlamak için yapay değişkenlere amaç fonksiyonunda çok büyük negatif bir katsayı (−M-M) verilir. Böylece simpleks algoritması, ZZ değerini maksimize etmeye çalışırken bu değişkenleri temelden çıkarıp değerlerini sıfır yapmaya zorlanır.

Step-by-Step Solution

1
Modelin amaç yönünü ve kısıt tiplerini belirleme
Amaç fonksiyonu maksimizasyon yönündedir ve x1+2x2=10x_1 + 2x_2 = 10 kısıtı bir yapay değişken (a1a_1) gerektirir.
Yapay değişkenin katsayısı, problemin maksimizasyon mu yoksa minimizasyon mu olduğuna göre değişir.
2
Büyük-M yöntemi ceza kuralını uygulama
Maksimizasyon problemi için ceza katsayısı −M-M olarak belirlenir.
Maksimizasyonun amacı ZZ değerini en büyük yapmaktır; yapay değişkenin katsayısı −M-M (çok büyük negatif bir sayı) yapılarak bu değişkenin çözümde yer alması engellenir.
3
Amaç fonksiyonunu düzenleme
Yapay değişken amaç fonksiyonuna Z=5x1+3x2−Ma1Z = 5x_1 + 3x_2 - Ma_1 şeklinde eklenir.
Böylece yapay değişkenin değeri pozitif olduğunda ZZ değeri aşırı küçülür ve algoritma bu değişkeni sıfıra zorlar.

Key Concept

Büyük-M yönteminde amaç fonksiyonu yönüne göre yapay değişken katsayısının belirlenmesi.

Practice More

Aynı problem minimizasyon yönünde olsaydı katsayının nasıl değişeceğini inceleyebilirsiniz.
Estimated Time:45s
Question 7Question →

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

Minimize Z=6x1+4x2\text{Minimize } Z = 6x_1 + 4x_2
Kısıtlar:\text{Kısıtlar:}
3x1+2x2≥123x_1 + 2x_2 \geq 12
x1,x2≥0x_1, x_2 \geq 0

Bu model Büyük-M (Big-M) yöntemi kullanılarak çözülmek istendiğinde, artık değişken (s1s_1) ve yapay değişken (a1a_1) eklendikten sonra oluşturulan **amaç fonksiyonu (ZZ)** aşağıdakilerden hangisidir?

Show answer & explanation

Answer: Z=6x1+4x2+0s1+Ma1Z = 6x_1 + 4x_2 + 0s_1 + Ma_1

Answer

Minimizasyon amaçlı bir modelde Büyük-M yöntemi uygulanırken, amaç fonksiyonu değişken katsayıları korunarak yapay değişken için pozitif ceza katsayısı (+M) ve artık değişken için sıfır katsayısı eklenerek oluşturulur.
Doğrusal programlama problemlerinde minimizasyon amaçlandığında, Büyük-M yönteminin mantığı yapay değişkenin maliyetini 'çok büyük' yaparak onu temel çözümdür dışına itmektir. Bu nedenle amaç fonksiyonunda yapay değişkenin önüne pozitif M (+M+M) katsayısı gelir. Artık değişkenler ise amaç fonksiyonuna katkı sağlamadıkları için katsayıları sıfır olarak kalır.

Step-by-Step Solution

1
Kısıt türünü belirleyin
Kısıt ≥\geq (büyük eşit) formundadır.
Hangi değişkenlerin ekleneceğini belirlemek için kısıt yönü incelenmelidir.
2
Değişkenleri ekleyin
3x1+2x2−s1+a1=123x_1 + 2x_2 - s_1 + a_1 = 12
Büyük eşit kısıtlarında bir artık değişken (çıkarılır) ve bir yapay değişken (eklenir) kullanılır.
3
Amaç fonksiyonunu (Z) oluşturun
Z=6x1+4x2+0s1+Ma1Z = 6x_1 + 4x_2 + 0s_1 + Ma_1
Minimizasyon problemlerinde yapay değişkenler, modelin uygun çözüm bölgesine zorlanması için amaç fonksiyonuna +M katsayısı ile ceza olarak eklenir.

Key Concept

Büyük-M Yönteminde Ceza Katsayıları

Practice More

Benzer bir problemi maksimizasyon amacı için çözerek ceza katsayısının işaret değişimini gözlemleyebilirsiniz.
Estimated Time:45s
Question 8Question →

Endüstriyel bir üretim sürecinin optimizasyonu için kurgulanan matematiksel model aşağıda verilmiştir:

Maksimum Z=50x1+80x2\text{Maksimum } Z = 50x_1 + 80x_2
Kısıtlar:\text{Kısıtlar:}
x1+2x2≤30x_1 + 2x_2 \leq 30
3x1+x2≥243x_1 + x_2 \geq 24
x1+x2=18x_1 + x_2 = 18
x1,x2≥0x_1, x_2 \geq 0

Bu problemin başlangıç temel uygun çözümünü bulmak amacıyla Büyük-M (Big-M) yöntemi uygulanacaktır. Model standart forma getirilip ilk simpleks tablosu oluşturulduğunda ve yapay değişkenler amaç fonksiyonu satırından yok edilerek tablo iterasyona hazır hale getirildiğinde; x1x_1, x2x_2 ve ikinci kısıta ait fazlalık (artık) değişkeni olan e1e_1'in **Zj−CjZ_j - C_j (net değerlendirme)** satırındaki değerleri sırasıyla aşağıdakilerden hangisidir?

Show answer & explanation

Answer: −4M−50-4M - 50, −2M−80\quad -2M - 80, M\quad M

Answer

Standart formda Zj−CjZ_j - C_j hesaplamaları sonucunda x1x_1 için −4M−50-4M - 50, x2x_2 için −2M−80-2M - 80 ve e1e_1 için MM değerleri elde edilir.
Doğrusal programlama modelinin başlangıç temel uygun çözümü oluşturulurken s1s_1, a1a_1 ve a2a_2 temel değişkenler olarak seçilir. CBC_B vektörü maksimizasyon problemi olduğu için [0,−M,−M][0, -M, -M] olur. Zj−CjZ_j - C_j formülü her değişkenin sütun vektörü ile CBC_B çarpılıp kendisinin amaç fonksiyonundaki katsayısı çıkarılarak (CjC_j) bulunur. x1x_1 için 0(1)−M(3)−M(1)−50=−4M−500(1)-M(3)-M(1)-50 = -4M-50; x2x_2 için 0(2)−M(1)−M(1)−80=−2M−800(2)-M(1)-M(1)-80 = -2M-80; e1e_1 için 0(0)−M(−1)−M(0)−0=M0(0)-M(-1)-M(0)-0 = M doğru sonucunu verir.

Step-by-Step Solution

1
Modeli standart forma dönüştürün ve maksimizasyon problemi için amaç fonksiyonunu güncelleyin.
Kısıt 1: x1+2x2+s1=30x_1 + 2x_2 + s_1 = 30
Kısıt 2: 3x1+x2−e1+a1=243x_1 + x_2 - e_1 + a_1 = 24
Kısıt 3: x1+x2+a2=18x_1 + x_2 + a_2 = 18
Amaç: Maks. Z=50x1+80x2+0s1+0e1−Ma1−Ma2Z = 50x_1 + 80x_2 + 0s_1 + 0e_1 - Ma_1 - Ma_2
Eşitsizlikleri ve eşitlikleri denklem haline getirmek ve Büyük-M mantığıyla yapay değişkenleri cezalandırmak (-M) gereklidir.
2
Başlangıç temel çözümünü ve bu değişkenlerin amaç fonksiyonundaki katsayı vektörünü (CBC_B) belirleyin.
Temel değişkenler: s1s_1, a1a_1, a2a_2. Bunların katsayıları sırasıyla CB=[0,−M,−M]C_B = [0, -M, -M] şeklindedir.
Orijine en yakın ilk geçerli kimlik matrisini oluşturan değişkenler başlangıç temelini oluşturur.
3
x1x_1 değişkeni için Zj−CjZ_j - C_j değerini hesaplayın.
Z1−C1=[0,−M,−M]⋅[1,3,1]T−50=(0⋅1)+(−M⋅3)+(−M⋅1)−50=−4M−50Z_1 - C_1 = [0, -M, -M] \cdot [1, 3, 1]^T - 50 = (0\cdot1) + (-M\cdot3) + (-M\cdot1) - 50 = -4M - 50
Net değerlendirme satırı formülü: Zj−Cj=∑(CBi⋅yij)−cjZ_j - C_j = \sum (C_{Bi} \cdot y_{ij}) - c_j
4
x2x_2 değişkeni için Zj−CjZ_j - C_j değerini hesaplayın.
Z2−C2=[0,−M,−M]⋅[2,1,1]T−80=(0⋅2)+(−M⋅1)+(−M⋅1)−80=−2M−80Z_2 - C_2 = [0, -M, -M] \cdot [2, 1, 1]^T - 80 = (0\cdot2) + (-M\cdot1) + (-M\cdot1) - 80 = -2M - 80
Aynı formül x2x_2'nin sütun vektörü ve amaç fonksiyonu katsayısı kullanılarak uygulanır.
5
e1e_1 (fazlalık) değişkeni için Zj−CjZ_j - C_j değerini hesaplayın.
Ze1−Ce1=[0,−M,−M]⋅[0,−1,0]T−0=(0⋅0)+(−M⋅−1)+(−M⋅0)−0=MZ_{e1} - C_{e1} = [0, -M, -M] \cdot [0, -1, 0]^T - 0 = (0\cdot0) + (-M\cdot-1) + (-M\cdot0) - 0 = M
Fazlalık değişkenleri kısıt denkleminden çıkarıldığı için sütun vektöründe ilgili satırda -1 değerini alır.

Key Concept

Büyük-M (Big-M) Yönteminde Başlangıç Tablosu Net Değerlendirme (Zj−CjZ_j - C_j) Hesaplamaları
Question 9Question →

Bir tarım müdürlüğü, çiftçilere dağıtılacak tohum ve gübre destek paketlerini planlamak için aşağıdaki doğrusal programlama modelini kurmuştur:

min⁡Z=10x1+15x2 \min Z = 10x_1 + 15x_2
Kısıtlar:
x1+x2≥10(Minimum destek kotası) x_1 + x_2 \geq 10 \quad \text{(Minimum destek kotası)}
2x1+x2=12(Bu¨tc¸e denklik kısıtı) 2x_1 + x_2 = 12 \quad \text{(Bütçe denklik kısıtı)}
x1≤8(Stok sınırı) x_1 \leq 8 \quad \text{(Stok sınırı)}
x1,x2≥0 x_1, x_2 \geq 0

Bu model, başlangıç uygun temel çözümü bulmak amacıyla İki Evreli (Two-Phase) yöntem kullanılarak çözülecektir. Karar verici, birinci evre (Phase 1) için modeli standart forma dönüştürürken; birinci kısıt için s1s_1 artık (surplus) ve a1a_1 yapay değişkenini, ikinci kısıt için a2a_2 yapay değişkenini, üçüncü kısıt için ise s2s_2 aylak (slack) değişkenini modele eklemiştir.

Birinci evrenin amacı yapay değişkenlerin toplamını minimize etmek (min⁡W \min W ) olarak belirlenmiştir.

Buna göre, birinci evrenin başlangıç simpleks tablosu oluşturulurken temel değişkenlerin (a1a_1 ve a2a_2) sıfırıncı satırdaki (WW amaç fonksiyonu satırı) katsayılarını sıfırlamak için yapılan cebirsel işlemler sonucunda, tabloya yazılacak olan **WW satırı denklemi** aşağıdakilerden hangisidir?

Show answer & explanation

Answer: W+3x1+2x2−s1=22W + 3x_1 + 2x_2 - s_1 = 22

Answer

İki evreli yöntemin birinci evresi için hazırlanan başlangıç simpleks tablosunda doğru W satırı denklemi W+3x1+2x2−s1=22W + 3x_1 + 2x_2 - s_1 = 22 şeklinde olmalıdır.
İki evreli yöntemin birinci evresinde amaç, eklenen yapay değişkenlerin toplamını minimize etmektir (min W = a_1 + a_2). Kısıtlardan yapay değişkenler çekildiğinde a_1 = 10 - x_1 - x_2 + s_1 ve a_2 = 12 - 2x_1 - x_2 bulunur. Bunlar W fonksiyonunda yerine yazıldığında W = 22 - 3x_1 - 2x_2 + s_1 elde edilir. Simpleks tablosuna aktarım için tüm değişkenler eşitliğin sol tarafına taşındığında işaretleri değişir ve doğru denklem olan W + 3x_1 + 2x_2 - s_1 = 22 denklemi bulunur.

Step-by-Step Solution

1
Kısıtları standart forma dönüştür.
1. Kısıt: x1+x2−s1+a1=10x_1 + x_2 - s_1 + a_1 = 10
2. Kısıt: 2x1+x2+a2=122x_1 + x_2 + a_2 = 12
3. Kısıt: x1+s2=8x_1 + s_2 = 8
Yapay değişkenler (a_1 ve a_2), büyük eşit ve eşitlik kısıtlarında başlangıç temel çözümünü sağlamak için eklenir. Büyük eşit kısıtından ayrıca artık değişken (-s_1) çıkarılır.
2
Birinci evre amaç fonksiyonunu (W) tanımla ve yapay değişkenleri yalnız bırak.
Amacımız: min⁡W=a1+a2\min W = a_1 + a_2
Kısıtlardan:
a1=10−x1−x2+s1a_1 = 10 - x_1 - x_2 + s_1
a2=12−2x1−x2a_2 = 12 - 2x_1 - x_2
Simpleks tablosunda temel değişkenlerin sıfırıncı satırdaki katsayıları sıfır olmalıdır. Bu yüzden W fonksiyonundaki a_1 ve a_2 yerine kısıtlardaki eşitlikleri yazılmalıdır.
3
Yalnız bırakılan ifadeleri W fonksiyonunda yerine koy.
W=(10−x1−x2+s1)+(12−2x1−x2)W = (10 - x_1 - x_2 + s_1) + (12 - 2x_1 - x_2)
W=22−3x1−2x2+s1W = 22 - 3x_1 - 2x_2 + s_1
Bu işlem, W amaç fonksiyonunu temel olmayan değişkenler (x1,x2,s1x_1, x_2, s_1) cinsinden ifade etmemizi sağlar.
4
Denklemi simpleks tablosu formatına uygun hale getir.
Tüm değişkenleri sol tarafa, sabit sayıyı sağ tarafa alarak:
W+3x1+2x2−s1=22W + 3x_1 + 2x_2 - s_1 = 22 elde edilir.
Simpleks tablosu sıfırıncı satırına katsayıları aktarabilmek için tüm değişkenlerin eşitliğin aynı tarafında toplanması standart prosedürdür.

Key Concept

İki Evreli Yöntemde (Two-Phase Method) birinci evre amaç fonksiyonunun (W) kurulması ve temel değişkenlerin sıfırıncı satırdan yok edilerek başlangıç tablosuna aktarılması.
Estimated Time:2m 0s
Question 10Question →

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 (WW) minimize edilmektedir.

Bir problemin 1. Evre optimum tablosuna ulaşıldığında amaç fonksiyonu değerinin W=0W = 0 olduğu, ancak yapay değişkenlerden biri olan R1R_1'in temel değişkenler arasında ve çözüm değerinin sıfır (00) olarak kaldığı görülmüştür. Bu optimum tablonun R1R_1'e ait satırında, temel olmayan asıl karar ve aylak/artık değişkenlerin katsayıları a1j∗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?

Show answer & explanation

Answer: Eğer tüm a1j∗=0a_{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 a1j∗a_{1j}^* varsa R1R_1 pivot işlemiyle temelden çıkarılır.

Answer

Eğer tüm a1j∗=0a_{1j}^* = 0 ise, satır tablodan silinir (doğrusal bağımlılık); sıfırdan farklı katsayı varsa pivot işlemiyle R1R_1 temelden çıkarılır.
İki Evreli (Two-Phase) yöntemin 1. Evre'si sonunda W=0W=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 (a1j∗=0a_{1j}^*=0), elde edilen denklem 0x1+0x2+...+1R1=00x_1 + 0x_2 + ... + 1R_1 = 0 şeklindedir. Bu denklem 0=00=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 (R1R_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 (a1j∗a_{1j}^*) kontrol edilmesi.
Tüm katsayılar sıfır ise 0=00 = 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 R1R_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 11Question →

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:

Maksimum Z=30x1+40x2\text{Maksimum } Z = 30x_1 + 40x_2
Kısıtlar:\text{Kısıtlar:}
2x1+x2≥122x_1 + x_2 \geq 12
x1+3x2=15x_1 + 3x_2 = 15
x1,x2≥0x_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>0M > 0 olmak üzere uygun ceza katsayıları atanmıştır.

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

Show answer & explanation

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

Answer

Başlangıç tablosunda x1x_1 ve x2x_2 değişkenlerinin Zj−CjZ_j - C_j değerleri sırasıyla −3M−30-3M - 30 ve −4M−40-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 = 30x1+40x2+0s1−MA1−MA230x_1 + 40x_2 + 0s_1 - MA_1 - MA_2
2x1+x2−s1+A1=122x_1 + x_2 - s_1 + A_1 = 12
x1+3x2+A2=15x_1 + 3x_2 + A_2 = 15
Büyük eşit (≥\geq) kısıtına bir artık değişken (−s1-s_1) ve bir yapay değişken (+A1+A_1) eklenirken; eşitlik (==) kısıtına yalnızca bir yapay değişken (+A2+A_2) eklenir. Maksimizasyon için yapay değişken cezaları −M-M olmalıdır.
2
Başlangıç simpleks tablosu için temel değişkenleri ve bunların amaç fonksiyonu katsayılarını (CBC_B) belirle.
Temel değişkenler: A1A_1 ve A2A_2. Her ikisinin de CBC_B katsayısı −M-M'dir.
İlk çözümde birim matrisi oluşturan A1A_1 ve A2A_2 sisteme girer.
3
x1x_1 değişkeni için Z1−C1Z_1 - C_1 değerini hesapla.
Z1=(−M×2)+(−M×1)=−3MZ_1 = (-M \times 2) + (-M \times 1) = -3M. C1=30C_1 = 30. Z1−C1=−3M−30Z_1 - C_1 = -3M - 30.
Net değerlendirme satırı, sütun katsayılarının CBC_B ile çarpımlarının toplamından (ZjZ_j), değişkenin kendi amaç fonksiyonu katsayısının (CjC_j) çıkarılmasıyla elde edilir.
4
x2x_2 değişkeni için Z2−C2Z_2 - C_2 değerini hesapla.
Z2=(−M×1)+(−M×3)=−4MZ_2 = (-M \times 1) + (-M \times 3) = -4M. C2=40C_2 = 40. Z2−C2=−4M−40Z_2 - C_2 = -4M - 40.
Aynı Zj−CjZ_j - C_j mantığı x2x_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
Yapay Değişkenli Yöntemler (Büyük-M ve İki Evreli) Practice Questions — KPSS İstatistik | Examkin