Yöneylem araştırması ve simülasyon için simpleks yöntem

En büyük erdemi sadeliği olan simpleks yöntemi, sadece amaç fonksiyonunun katsayıları ve kısıtlamalarla çalıştığı için oldukça pratik bir yöntemdir.

İşleyişini bir örnekle göstereceğiz, ancak daha önce giren değişkeni, ayrılanı, büyük M'yi ve optimumda olduğumuzu nasıl belirleyeceğimizi belirlemek için karar kurallarını göstereceğiz; Tüm bu karar kuralları cebirsel yöntemden türetilmiştir, ancak burada kullanılacak simpleks tahta türünde kullanılmak üzere düzenlenmiştir.

simpleks-yöntemi-araştırma simülasyon ve operasyonları-1

KISITLAMA TÜRLERİ

Kısıtlamalar

Amaç fonksiyonunda maliyet (veya kar) 0'a eşit olacak şekilde bir gevşek değişken eklenir.

EJM:

2X1 - 4X2 <= 1, kalır:

2X1 - 4X2 + X3 = 1 Cj of X3 0 olacaktır.

Kısıtlamalar ³

Hedef fonksiyondaki maliyet (veya kar) 0'a eşit olacak şekilde bir fazla değişken çıkarılır ve maksimizasyon veya minimizasyon olmasına bağlı olarak maliyet + M veya –M olan yapay bir değişken eklenir.

EJM:

2X1 + 3X2> = 1, kalır:

2X1 + 3X2 - X3 + X4 = 1 Cj X3'ün amaç fonksiyonunda 0 olacaktır ve X4'ün Cj'si (yapay) ± M

Kısıtlamalar =

Maksimizasyon veya minimizasyon olmasına bağlı olarak maliyet + M veya –M ile yapay bir değişken eklenir.

EJM:

2X1 + 3X2 = 8, kalır:

2X1 + 3X2 + X3 = 8 Cj X3'ün amaç fonksiyonunda ± M olacaktır

Ek olarak, aşağıdaki notlar dikkate alınması için sunulmuştur:

Optimal çözümün simpleks tahtasında, temel değişkenler içinde değeri> 0 olan en az bir fazla veya yapay değişken varsa, sorunun çözümü yoktur, bu, en az iki özel kısıtlamanın olduğu anlamına gelir, bu nedenle Uygulanabilir bir çözüm alanı yoktur ve çözüm eksiktir, bu durumda sorunun formülasyonu gözden geçirilmelidir.Çıkan değişkeni seçerken temel değişkenlerden hiçbiri girilmek üzere seçilen temel olmayan değişkenin büyümesini kısıtlamıyorsa, Belirsiz çözüm ve formülasyon, ilk formülasyonda dikkate alınmayan yeni bir kısıtlama arayışında gözden geçirilmelidir Optimum simpleks tahtasında, temel olmayan değişkenlerden en az birinin fonksiyonda sıfır katsayısı (0) varsa hedef, bu sizin Zj - Cj = 0,sorunun birden fazla çözümü var ve bunlardan biri bize sunuluyor.

örnek 1

Xi üretilecek ürün i'nin miktarıdır.

Z = X1 + X2 {Tabanlardaki toplam kazanç} maksimize edin

5X1 + 3X2 <= 15 {Mevcut saat dep. TO}

3X1 + 5X2 <= 15 {Kullanılabilir saat. B}

Xj> = 0; j = 1, 2

Maksimizasyon problemleri, tüm kısıtlamaları <= ve negatif olmama koşuluyla, Standart Form veya Normal Form olarak adlandırılır.

Burada, gevşek ve / veya yapay değişkenleri kullanarak uygulanabilir bir temel çözüme ulaşmalı ve denklem sistemini şöyle bırakmalıyız:

Z = X1 + X2'yi büyüt

5X1 + 3X2 + X3 = 15

3X1 + 5X2 + X4 = 15

Xj> = 0; j = 1,2,3,4

Temel değişkenler, katsayıları birim matrisi oluşturanlardır.

Bu kaosta tesadüfen gevşek değişkenler X3 ve X4 vardır.

Z hedef fonksiyonunun değeri, Zj - Cj kutusunun önündedir, bu durumda sıfır (0) değerindedir ve satır vektörünün çarpılmasıyla hesaplanır (tabloda VB temel değişkenlerinin hemen önündeki sütundur.) bağımsız terimlerin sütun vektörü ile orijinal amaç fonksiyonundaki temel değişkenlerin katsayılarını içeren

CX _B = Mevcut temel değişkenlerin orijinal amaç fonksiyonundaki katsayıların satır vektörü, değerleri panonun ilk sütunundadır.

b = Aynı zamanda mevcut temel değişkenlerin değerleri olan kısıtlamaların bağımsız terimlerinin sütun vektörü, değerleri b adlı sütunun altındadır.

CX _B = (0.0); b = (15,15) ' Z = CX _B * b = (0) (15) + (0) (15) = 0

Zj - Cj'nin değeri, satır vektörü CX _B ile j-inci değişkeninin sütununun işaret vektörü aj eksi Cj ile çarpılarak hesaplanır, yani:

Zj - Cj = CX _B. aj - Cj;

Hesaplamalar şu şekilde yapılır:

Z1 - C1 = CX _B a1 - C1 = (0,0). (5,3) '- 1 = (0) (5) + (0) (3) - 1 = -1

Z2 - C2 = CX _B a2 - C2 = (0,0). (3,5) '- 1 = (0) (3) + (0) (5) - 1 = -1

Z3 - C3 = CX _B a3 - C3 = (0,0). (1,0) '- 0 = (0) (1) + (0) (0) - 0 = 0

Z4 - C4 = CX _B a4 - C4 = (0,0). (0,1) '- 0 = (0) (0) + (0) (1) - 0 = 0

Çıkan değişken ve gelen değişken aşağıda listelenmiştir:

Cj	bir	bir	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
0	X3	onbeş	5	3	bir	0	15/5 = 3
0	X4	onbeş	3	5	0	bir	15/3 = 5
Zj - Cj	0	-bir	-bir	0	0

Değişken giriş X1

Değişken çıktı X3

En negatif Zj-Cj'ye sahip değişken X1 veya X2'dir. X1 rastgele seçilir.

Bu yinelemede b / a şunu verir: 15/5 = 3 ve 15/3 = 5;

Bu, temel değişken X3'ün girdi değişkeni X1'in büyümesini 3 ile sınırladığı (3'ten daha yüksek değerler almasına izin vermediği) ve temel değişken X4'ün girdi değişkeni X1'in büyümesini 5'e sınırladığı anlamına gelir (5'ten büyük değerler alalım).

Elbette , girdi değişkeni X1'in büyümesini en çok kısıtlayan temel değişken X3'tür, bu nedenle bırakılmak üzere seçilen temel değişkendir.

Çıkmak için seçilen temel değişkenin satırı, söz konusu satırın giriş değişkeninin sütunu ile kesişme noktasında bulunan öğeye bölünür, ortaya çıkan satır pivot satırıdır ve yeni bir tahtaya yerleştirilir. Pivot sırasının katları, önceki panonun diğer satırlarına, girmek için seçilen değişken her birinden çıkarılacak şekilde eklenir, bizim durumumuzda X1, bu prosedür denir, kesişimde bir (1) yapın ve sütun sıfırlarının geri kalanı (0), bu nedenle söz konusu sütunda bir birim vektör görünecektir, tüm Zj - Cj maksimize etme veya daha küçük olması durumunda sıfıra eşit veya büyük olana kadar her yinelemede prosedür tekrarlanır. veya küçültme durumunda sıfıra eşittir.

Aşağıda tüm yinelemeler yer almaktadır ve her satırda diğer satırlara eklenmek üzere çarpıldıkları değerler, bu, bir satırdan diğerine katların eklenmesi olarak ifade edilir.

Temel değişkenleri ondan çıkarmak için kısıtlamaların katlarının amaç fonksiyonuna eklendiğine dikkat edin.

Cj	bir	bir	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
bir	X1	3	bir	3/5	1/5	0	5
0	X4	6	0	16/5	-3/5	bir	15/08
Zj - Cj	3	0	-2/5	1/5	0

Değişken giriş X2

Değişken çıktı X4

Cj	bir	bir	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
bir	X1	15/08	bir	0	5/16	0
bir	X2	15/08	0	bir	-3/16	5/16
Zj - Cj	15/4	0	0	1/8	1/8

En uygun çözüm:

X1 * = 15/8

X2 * = 15/8

Z * = 15/4

Çözüm benzersizdir: X1 * = 15/8; X2 * = 15/8; Z * = 14/4

Örnek 2

Minimize Z = 6X1 + 4X2 + 2X3

6X1 + 2X2 + 6X3> = 6

6X1 + 4X2 = 12

2X1 - 2X2 <= 2

Xj> = 0; j = 1, 2, 3

Z = 6X1 + 4X2 + 2X3 + MX5 + MX6'yı küçült

6X1 + 2X2 + 6X3 - X4 + X5 = 6

6X1 + 4X2 + X6 = 12

2X1 - 2X2 + X7 = 2

Xj> = 0; j = 1, 2, 3, 4, 5, 6, 7

Temel değişkenler X5 = 6, X6 = 12, X7 = 2'dir.

En uygun çözüm:

Karar değişkenleri:

X1 = 0, X2 = 3, X3 = 0, Z = 12

Gevşek değişkenler: X4 = 0, X7 = 8

Yapay değişkenler: X5 = 0, X6 = 0

POST-OPTİMAL ANALİZDE BİR ATILIM

Z = X1 + X2 {Tabanlardaki toplam kazanç} maksimize edin

5X1 + 3X2 <= 15 {Mevcut saat dep. TO}

3X1 + 5X2 <= 15 {Kullanılabilir saat. B}

Xj> = 0; j = 1, 2

Optimal tahta:

Cj	bir	bir	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
bir	X1	15/08	bir	0	5/16	0
bir	X2	15/08	0	bir	-3/16	5/16
Zj - Cj	15/4	0	0	1/8	1/8

En uygun çözüm:

X1 * = 15/8

X2 * = 15/8

Z * = 15/4

Düşük maliyet:

Birimler = (para birimi) / (ürün birimi) = (um) / (yukarı) = Cj ile aynı birimler

İkili fiyat:

Birimler = (para birimi) / (kaynak birimi) = (um) / (ur)

İndirgenmiş maliyetin yorumlanması:

Kaç para biriminde, üretilmeyen bir ürünün bir birimini üretirken nesnel işlev kötüleşir.

Minimizasyonda: (Dz / Dx) Maksimizasyonda: (Ñz / Dx)

Değişken temel ise indirgenmiş maliyet 0'dır. Değişken temel değilse> = 0'dır. 0 olduğunda alternatif çözümler anlamına gelir.

İkili Fiyatın Yorumlanması:

Kaç para biriminde amaç işlevi, sınırlayıcı bir kaynak biriminde değişiklik göstererek değişir.

> 0 olduğunda: (Dz / Db) veya (Ñz / Ñb)

<0 olduğunda: (Dz / Ñb) veya (Ñz / Db)

Bir kısıtlama, amaç işlevini sınırladığında sınırlayıcıdır. Bu, kısıtlamanın eşitliği sağlandığında olur.

Kısıtlama sınırlayıcı değilse, ikili fiyat 0'dır.

Kısıtlama sınırlayıcıysa, herhangi bir pozitif, negatif veya 0 değerini alabilir.

KÖTÜ HAYVANLAR

Bir Doldurulmuş Hayvanlar Şirketi, doldurulmuş güvercinler ve şahinler üretiyor. Mevcut piyasa koşullarında, sırasıyla 20.00 $ ve 12.00 $ karla şahin ve güvercin satabilir.

Şahinlerin derileri daha serttir ve çalışması güvercin derilerinden daha fazla zaman alır. Kürk makinesi aynı kapasiteyi kullanarak dakikada 4 şahin derisini veya güvercinler için 8 postu işleyebilir. Dolum hattı dakikada 5 şahin veya 4 güvercin doldurabilir. Dakikada 3,5 şahin kapasiteli gaga bileme makinesinde son operasyona çıkan şahinler bölümdeki çalışma günü 8 saattir.

Vakayı çözen doğrusal programlama modelini formüle edin (a) 'da formüle edilen modelin ikili problemini formüle edin Modeli çözün ve çözümün yönetimsel bir yorumunu yapın Doğrudan optimal tablodan okuyarak ikili problemin optimal çözümünü belirleyin c sorusunda bulundu.

Aksi belirtilmedikçe, aşağıdaki sorular birbirinden bağımsızdır ve sorunun ilk ifadesine dayanmaktadır.

Deri makinesinde, dolum hattında ve bileme makinesinde fazla mesai yapma imkanı vardır. Her bir bölümde her bir fazla mesai için elde edilen en büyük kar nedir? Şirket Müdürü şahin ve güvercin hattını ziyaret ederek bazı süreçlerde atıl kapasite olduğunu gözlemler. Sürecin tüm merkezlerinin tüm kurulu kapasiteleri ile kullanılmasına karar verdi. Ne dersiniz, her bir güvercinin karı ne kadar düşerse en uygun çözüme ne olur? 9.00? Oyuncaklara daha iyi bir yüzey kazandırmak için bir cila hattı kuruldu; laklama hattı aynı anda dakikada 5 şahin veya 4 güvercin doldurabilir, ayrıca gün 8 saattir. Optimal çözümü etkiler mi? öyleyse, yeni çözümü bulun.

TEORİK NOT:

Bu soruda mevcut çözümle yeni kısıtlamanın yerine getirilip getirilmediğini gözlemleyin, öyleyse fazlalık bir kısıtlama olacak ve mevcut çözümü etkilemeyecek, ancak mevcut çözüm buna uymuyorsa, bunu dikkate alarak sorunu yeniden çözmek gerekecektir. yeni kısıtlama.

MODEL:

X1 = gün içinde üretilecek güvercin sayısı

X2 = gün içinde üretilecek şahin sayısı

MAKS 12X1 + 20X2

KONU

0.125X1 + 0.25X2 <= 480 kürk makinesi

0.25X1 + 0.2X2 <= 480 doldurma satırı

0.2857143X2 <= 480 tepe keskinleştirme

SON

2.ADIMDA LP OPTİMUM BULUNDU

AMAÇ FONKSİYON DEĞERİ

1) 39680.00