Bir problem çözümü örneği. LLP'yi çözmek için Simplex yöntemi. Doğrusal programlama problemlerini simpleks yöntemiyle çözme

Beğendin mi? Yer imi

Simpleks yöntemini kullanarak sorunları çözme: çevrimiçi örnekler

Görev 1.Şirket, A ve B olmak üzere iki boyutta banyo rafları üretmektedir. Satış acenteleri, pazarda haftada 550'ye kadar rafın satılabileceğini tahmin etmektedir. Her A tipi raf 2 m2, B tipi raf 3 m2 malzeme gerektirir. Firma haftada 1200 m2'ye kadar malzeme alabilmektedir. A tipi bir rafın imalatı için 12 dakika, B tipi bir rafın imalatı için 30 dakika makine süresi gereklidir; makine haftada 160 saat kullanılabilir. A tipi rafların satışından elde edilen kar 3 para birimi ve B tipi raflardan - 4 den ise. üniteler, her türden haftada kaç raf üretilmelidir?

Görev 2. Simpleks yöntemini kullanarak bir doğrusal programlama problemini çözün.

Görev 3. Firma A1, A2, A3 olmak üzere 2 çeşit hammadde kullanarak 3 çeşit ürün üretmektedir. Her türden üretim birimi başına hammadde maliyetleri, planlanan dönem için hammadde stokları ve her türden üretim birimi başına kâr bilinmektedir.

1. Kârı maksimize etmek için her türden kaç ürün üretilmelidir?
2. Her bir hammadde türünün durumunu ve özel değerini belirleyin.
3. En uygun planın yapısının, yani içinde bulunduğu her bir hammadde türünün stoklarını değiştirmek için maksimum aralığı belirleyin. sürüm isimlendirmesi değişmeyecek.
4. Kıt hammadde türlerinden birinin stoğu (verilen çıktı terminolojisi dahilinde) mümkün olan maksimum değere yükseltildiğinde çıktı miktarını ve çıktıdan elde edilen karı belirleyin.
5. Elde edilen optimal planın değişmeyeceği her türden bir üretim biriminden elde edilen kârdaki değişim aralıklarını belirleyin.

Görev 4. Simpleks yöntemini kullanarak doğrusal programlama problemini çözün:

Görev 5. Simpleks yöntemini kullanarak doğrusal programlama problemini çözün:

Görev 6. Problemi, aşağıdaki durumda verilen planı ilk referans planı olarak kabul ederek simpleks yöntemini kullanarak çözün:

Görev 7. Değiştirilmiş simpleks yöntemiyle sorunu çözün.
A ve B olmak üzere iki çeşit ürünün üretimi için üç çeşit teknolojik ekipman kullanılmaktadır. Bir birim A ürününün üretimi için, birinci tip ekipman a1=4 saat, ikinci tip ekipman a2=8 saat ve üçüncü tip ekipman a3=9 saat kullanılır. Bir birim B ürününün üretimi için, birinci tip ekipman b1 = 7 saat, ikinci tip ekipman b2 = 3 saat ve üçüncü tip ekipman b3 = 5 saat kullanılır.
Bu ürünlerin imalatı için, birinci tip teçhizat t1=49 saatten fazla, ikinci tip teçhizat t2=51 saatten fazla, üçüncü tip teçhizat t3=45 saatten fazla çalışamaz.
Bir birim bitmiş ürün A'nın satışından elde edilen kar, ALPHA = 6 ruble ve ürün B - BETTA = 5 ruble'dir.
Satışlarından maksimum karı sağlayan A ve B ürünlerinin üretimi için bir plan hazırlayın.

Görev 8. Dual simpleks yöntemiyle en uygun çözümü bulun

Problem durumunda ≥ işaretli kısıtlamalar varsa, eşitsizliğin her iki kısmı -1 ile çarpılarak bunlar ∑a ji b j formuna indirgenebilir. m ek değişken x n+j ≥0(j =1,m ) tanıtıyoruz ve kısıtlamaları eşitlik biçimine dönüştürüyoruz

(2)

x 1 , x 2 ,..., x n probleminin tüm başlangıç ​​değişkenlerinin temel olmadığını varsayalım. O zaman ek değişkenler temel olacak ve kısıtlamalar sistemine özel bir çözüm şu şekilde olacak:

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)

Bu durumda amaç fonksiyonunun değeri F 0 = 0 olduğundan, F(x)'i aşağıdaki gibi gösterebiliriz:

F(x)=∑c ben x ben + F 0 =0 (4)

Başlangıç ​​tek yönlü tablosu (simpleks tablo 1), (2) ve (4) numaralı denklemlere göre derlenir. Eğer x n+j ek değişkenlerinden önce (2)'deki gibi "+" işareti geliyorsa, x i değişkenlerinden ve serbest terim b j'den önceki tüm katsayılar değişmeden simpleks tablosuna girilir. Maksimizasyonu sırasında hedef fonksiyonunun katsayıları, tek yönlü tablonun alt satırına zıt işaretlerle girilir. Simpleks tablosundaki ücretsiz üyeler sorunun çözümünü belirler.

Sorunu çözmek için algoritma aşağıdaki gibidir:

1. adım. Ücretsiz üyeler sütununun öğeleri aranır. Hepsi pozitifse, kabul edilebilir bir temel çözüm bulunmuştur ve optimal çözümü bulmaya karşılık gelen algoritmanın 5. adımına geçilmelidir. İlk simpleks tablosunda negatif serbest terimler varsa, çözüm geçerli değildir ve 2. adıma gitmelisiniz.

2. adım. Uygulanabilir bir çözüm bulmak için gerçekleştirilir, temel olmayan değişkenlerden hangilerinin tabana alınacağına ve hangi değişkenin tabandan çekileceğine karar vermek gerekir.

Tablo 1.

x n

temel değişkenler	Kısıtlamalarda ücretsiz üyeler	temel olmayan değişkenler
		x 1	x2	...	x l	...
xn+1	b1	11	12	...	1l	...	1n
xn+2	b2	21	22	...	2l	...	2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+r	b2	bir r1	bir r2	...	bir rl	...	bir rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+m	ben	bir m1	bir m2	...	aml	...	amn
F(x)maks	F0	-c 1	-c 2	...	-c 1	...	-cn

Bunu yapmak için, serbest üyeler sütununun negatif öğelerinden herhangi birini seçin (b 2 önde olsun veya izin versin. Negatif serbest üyeli satırda negatif öğe yoksa, kısıtlama sistemi tutarsızdır ve sorunun çözümü yok.

Aynı zamanda, seçilen NP x l'de bir artışla işaretini ilk değiştiren değişken BP'den hariç tutulur. Bu, dizini r koşuldan belirlenen x n+r olacaktır.

şunlar. serbest terimin seçilen önde gelen sütunun öğesine en küçük oranına karşılık gelen değişken. Bu ilişki denir simpleks ilişkisi. Sadece pozitif simpleks ilişkiler dikkate alınmalıdır.

x n+r değişkenine karşılık gelen dizgeye öncülük etmek veya izin vermek. Simpleks tablosunun, baştaki satır ve satırdaki sütunun kesişim noktasında bulunan a rl öğesine, satır başı veya çözümleyici öğe denir.Önde gelen elemanı bulmak, sonraki her bir tek yönlü tablo ile çalışmayı bitirir.

3. adım. Elemanları önceki adımdaki simpleks tablosunun elemanlarından yeniden hesaplanan ve bir asal ile işaretlenen yeni bir simpleks tablosu hesaplanır, yani. b" j , a" ji , c" i , F" 0 . Elemanlar aşağıdaki formüllere göre yeniden hesaplanır:

İlk olarak, önceki simpleks tablosunda önde gelen satır ve sütun, yeni simpleks tablosunda doldurulacaktır. İfade (5), önde gelen elemanın yerindeki a "rl öğesinin, önceki tek yönlü tablodaki elemanın karşılıklı değerine eşit olduğu anlamına gelir. a ri satırının elemanları, önde gelen elemana bölünür ve a jl sütunu da önde gelen elemana bölünür, ancak zıt işaretle alınır.B" r ​​ve c" l elemanları aynı prensibe göre hesaplanır.

Formüllerin geri kalanı kullanılarak kolayca yazılabilir.

Dikdörtgen, eski simpleks tablosuna göre, köşegenlerinden biri yeniden hesaplanmış (a ji) ve önde gelen (a rl) elemanlardan oluşacak şekilde inşa edilmiştir (Şekil 1). İkinci köşegen benzersiz bir şekilde belirlenir. Yeni bir a "ji elemanı bulmak için, karşı köşegenin elemanlarının önde gelen elemana bölümü a ji elemanından çıkarılır (bu, hücrede" - "işaretiyle gösterilir). Benzer şekilde, b" j elemanları, (j≠r) ve c" i yeniden hesaplanır, (i≠l).

4. adım. Yeni bir simpleks tablosunun analizi, algoritmanın 1. adımından başlar. Eylem, uygun bir temel çözüm bulunana kadar devam eder, yani. ücretsiz üyeler sütununun tüm öğeleri pozitif olmalıdır.

5. adım. Kabul edilebilir bir temel çözümün bulunduğuna inanıyoruz. F(x) hedef fonksiyonunun doğrusunun katsayılarına bakıyoruz. Simpleks tablonun optimalliğinin bir işareti, F-satırındaki temel olmayan değişkenler için katsayıların negatif olmamasıdır.

Pirinç. 1. Dikdörtgen kuralı

F-satırının katsayıları arasında negatif olanlar varsa (serbest terim hariç), o zaman başka bir temel çözüme gitmeniz gerekir. Hedef fonksiyonunu maksimize ederken, temel, sütunu simpleks tablosunun alt satırındaki negatif katsayı cl'nin maksimum mutlak değerine karşılık gelen temel olmayan değişkenlerin (örneğin, x l) değerini içerir. Bu, artışı hedef işlevinde bir gelişmeye yol açan değişkeni seçmenize olanak tanır. x l değişkenine karşılık gelen sütuna, önde gelen sütun denir. Aynı zamanda, r indeksi minimum simpleks oranı ile belirlenen x n+r değişkeni temelden çıkarılır:

x n+r'ye karşılık gelen satıra, önde gelen satır denir ve tek yönlü tablonun, önde gelen satır ile satırdaki sütunun kesişiminde bulunan a rl elemanına denir. lider eleman.

6. adım. 3. adımda belirtilen kurallara göre. Prosedür, optimal bir çözüm bulunana veya var olmadığı sonucuna varılıncaya kadar devam eder.

Öndeki sütundaki çözümü optimize etme sürecinde tüm öğeler pozitif değilse, o zaman önde gelen satır seçilemez. Bu durumda, problemin kabul edilebilir çözümleri alanındaki fonksiyon yukarıdan ve F max ->&∞ ile sınırlı değildir.

Bir ekstremum arayışının bir sonraki adımında, temel değişkenlerden biri sıfıra eşit olursa, buna karşılık gelen temel çözüme dejenere denir. Bu durumda, aynı BP kombinasyonunun belirli bir frekansla tekrar etmeye başlamasıyla karakterize edilen sözde döngü meydana gelir (bu durumda F fonksiyonunun değeri korunur) ve geçiş yapmak imkansızdır. kabul edilebilir yeni bir temel çözüm. Döngü, simpleks yönteminin ana dezavantajlarından biridir, ancak nispeten nadirdir. Uygulamada, bu gibi durumlarda, sütunu hedef fonksiyonundaki negatif katsayının maksimum mutlak değerine karşılık gelen değişkenin temele girilmesi genellikle reddedilir ve yeni bir temel çözüm için rastgele bir seçim yapılır.

Örnek 1. Bir sorunu çözün

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Simpleks yöntemi ve çözüm sürecinin geometrik yorumunu verir.

Sorunun çözümünün grafiksel yorumu, Şek. 2. Hedef fonksiyonunun maksimum değerine, koordinatlarla ODZP'nin tepesinde ulaşılır. Problemi simpleks tabloları kullanarak çözelim. İkinci kısıtlamayı (-1) ile çarparız ve eşitsizlikleri eşitlik biçimine getirmek için ek değişkenler ekleriz, sonra

x 1 ve x 2 başlangıç ​​değişkenleri temel olmayan olarak alınır ve ek x 3 , x 4 ve x 5 temel kabul edilir ve bir simpleks tablosu derleriz (simpleks tablo 2). Simpleks tabloya karşılık gelen çözüm. 2, geçerli değil; önde gelen eleman, yukarıdaki algoritmanın 2. adımına göre ana hatlarıyla çizilir ve seçilir. Sonraki simpleks sekmesi. 3 kabul edilebilir bir temel çözümü tanımlar; 2 Öncü eleman, problemi çözmek için algoritmanın 5. adımına uygun olarak ana hatlarıyla belirlenir ve seçilir. Sekme. 4, problemin optimal çözümüne karşılık gelir, bu nedenle: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; Fmaks = 20.

Pirinç. 2. Problemin grafiksel çözümü

Adım 0. Hazırlık aşaması.

LP problemini özel bir forma indiriyoruz (15).

Aşama 1. derleme tek yönlü tabloözel bir forma karşılık gelen:

Bu tablonun kabul edilebilir bir temel çözüme karşılık geldiğine dikkat edin.
sorun (15). Bu çözümdeki amaç fonksiyonunun değeri

Adım 2 Optimalliği kontrol etme

Dizin satırının öğeleri arasında tek yönlü tablo ise
olumlu bir unsur yok
, LP probleminin optimal çözümü bulundu: Algoritma sonlandırılır.

Aşama 3Çözülemezliği kontrol edin

arasında ise
olumlu bir unsur var
, ve ilgili sütunda
olumlu bir unsur yok
, sonra amaç fonksiyonu L kabul edilebilir kümede aşağıdan sınırsızdır. Bu durumda optimal bir çözüm yoktur. Algoritma sonlandırılır.

4. AdımÖncü Sütun Seçme q

Elementler arasında
maksimum pozitif elemanı seçin
.Bu sütun, önde gelen (izin veren) olarak bildirilir.

Adım 5 Ana hat seçimi p

Sütunun olumlu unsurları arasında
eleman bul
, bunun için eşitlik

.

sicim pönde gelen (izin veren) ilan edin. eleman
ustayı ilan et (izin veriyor).

6. Adım Simpleks tablo dönüşümü

Aşağıdakileri içeren yeni bir simpleks tablosu oluşturuyoruz:

a) temel değişken yerine yazmak , temel olmayan bir değişken yerine yazmak ;

b) önde gelen eleman karşılıklı olarak değiştirilir
;

c) önde gelen sütunun tüm öğeleri (hariç
) ile çarpmak
;

d) ön çizginin tüm unsurları (hariç
) ile çarpmak ;

e) simpleks tablosunun kalan elemanları aşağıdaki "dikdörtgen" şemasına göre dönüştürülür.

Üç faktörün ürünü, elemandan çıkarılır:

ilki, önde gelen sütunun karşılık gelen öğesidir;

ikincisi, önde gelen çizginin karşılık gelen öğesidir;

üçüncüsü, önde gelen elemanın karşılığıdır
.

Dönüştürülmekte olan eleman ve ona karşılık gelen üç faktör tam olarak "dikdörtgenin" köşeleridir.

7. Adım Bir sonraki iterasyona geçiş, 2. adıma dönülerek gerçekleştirilir.

2.3. Maksimum Problem için Simpleks Yöntem Algoritması

Maksimum problem için simpleks yönteminin algoritması, minimum problem için algoritmadan sadece amaç fonksiyonundaki katsayıların indeks satırının işaretleri ile farklıdır.
, yani:

2. adımda:
:

3. adımda
. Amaç fonksiyonu, kabul edilebilir kümede yukarıdan sınırsızdır.

4. adımda:
.

2.4. Simpleks yöntemiyle bir problem çözme örneği

(15) formunda yazılan problemi çözünüz.

Şimdi bir simpleks tablosu oluşturalım:

Amaç fonksiyonu satırının katsayıları negatif olmadığından, ilk temel çözüm optimal değildir. Bu temel için amaç fonksiyonunun değeri L=0.

Önde gelen sütunu seçin - bu, değişkene karşılık gelen sütundur .

Önde gelen bir çizgi seçin. Bunun için bulduğumuz
. Bu nedenle, önde gelen satır değişkene karşılık gelir .

Bir değişken tanıtarak simpleks tablosunun dönüşümünü gerçekleştiriyoruz. temele ve değişkenin çıktısına temelinden. Bir tablo alalım:

Yöntemin bir yinelemesi tamamlandı. Yeni bir yinelemeye geçelim. Ortaya çıkan tablo yetersiz. Tabloya karşılık gelen temel çözüm forma sahiptir. Bu temelde amaç fonksiyonunun değeri L= -2.

Buradaki önde gelen sütun, değişkene karşılık gelen sütundur. . Önde gelen satır - değişkene karşılık gelen satır . Dönüşümleri gerçekleştirdikten sonra bir simpleks tablosu elde ederiz:

Bir yineleme daha tamamlandı. Yeni bir yinelemeye geçelim.

Amaç fonksiyonunun satırı pozitif değerler içermez, bu da karşılık gelen temel çözümün optimal olduğu ve algoritmanın sona erdiği anlamına gelir.

Optimizasyon problemlerini çözme yöntemlerinden biri ( genellikle minimum veya maksimumu bulmakla ilişkilidir) lineer programlama denir. Simpleks yöntemi doğrusal programlama problemlerini çözmek için bir dizi algoritma ve yöntem içerir. İlk verilerin kaydedilmesini ve özel bir tabloda yeniden hesaplanmasını içeren bu yöntemlerden birine denir. tablolu simpleks yöntemi.

Çözüm örneğinde tablolu simpleks yönteminin algoritmasını düşünün üretim görevi, maksimum kâr sağlayan bir üretim planı bulmaktan ibarettir.

Simpleks yöntemi için problemin ilk verileri

İşletme 4 çeşit ürün üretiyor ve bunları 3 makinede işliyor.

Ürünlerin makinelerde işlenmesi için zaman sınırları (min./adet) matris A ile verilmiştir:

Makine çalışma süresi fonu (min.) B matrisinde verilmektedir:

Ürünün her bir biriminin (ruble/parça) satışından elde edilen kar, C matrisi ile verilir:

Üretim görevinin amacı

İşletmenin kârının maksimize edileceği bir üretim planı hazırlayın.

Problemin tabular simpleks yöntemiyle çözümü

(1) X1, X2, X3, X4, her türden planlanan ürün sayısını göstersin. Ardından istenilen plan: ( X1, X2, X3, X4)

(2) Plan kısıtlamalarını bir denklem sistemi şeklinde yazalım:

(3) O zaman hedef kâr:

Yani, üretim planının uygulanmasından elde edilen kâr maksimum olmalıdır.

(4) Ortaya çıkan koşullu ekstremum problemini çözmek için, içine negatif olmayan ek değişkenler ekleyerek eşitsizlikler sistemini bir doğrusal denklem sistemi ile değiştiririz ( X5, X6, X7).

(5) Aşağıdakileri kabul ediyoruz referans planı:

X1=0, X2=0, X3=0, X4=0, X5=252, X6=144, X7=80

(6) Verileri girelim tek yönlü tablo:

Son satırda, amaç fonksiyonunun katsayılarını ve değerini ters işaretle giriyoruz;

(7) Son satırda seçin En büyük (modül) negatif bir sayı.

hesaplama b = N / Seçilmiş_sütun elementleri

B'nin hesaplanan değerleri arasında seçtiğimiz en az.

Seçilen sütun ve satırın kesişimi bize bir çözümleme elemanı verecektir. Temeli, etkinleştirme öğesine karşılık gelen bir değişkenle değiştiririz ( X5'ten X1'e).

• Enable öğesinin kendisi 1 olur.
• İzin verilen satırın öğeleri için - a ij (*) = a ij / RE ( yani, her öğeyi etkinleştiren öğenin değerine böleriz ve yeni veriler alırız.).
• Bir çözümleme sütununun öğeleri için, basitçe sıfıra sıfırlanırlar.
• Tablonun kalan elemanları dikdörtgen kuralına göre yeniden hesaplanır.

bir ij (*) = bir ij - (A * B / RE)

Gördüğünüz gibi, yeniden hesaplanan mevcut hücreyi ve etkinleştirme öğesinin bulunduğu hücreyi alıyoruz. Dikdörtgenin zıt köşelerini oluştururlar. Ardından, bu dikdörtgenin diğer 2 köşesinin hücrelerinden gelen değerleri çarpıyoruz. Bu iş ( A * B) çözümleme elemanına bölün ( TEKRAR). Ve mevcut yeniden hesaplanan hücreden çıkarın ( aij) ne oldu. Yeni bir değer elde ederiz - bir ij (*).

(9) Son satırı tekrar kontrol edin ( c) üzerinde negatif sayıların varlığı. Hiçbiri yoksa, en uygun plan bulundu, sorunu çözmenin son aşamasına geçiyoruz. Varsa, plan henüz optimal değildir ve simpleks tablonun yeniden hesaplanması gerekir.

Son satırda yine negatif sayılar olduğundan, yeni bir hesaplama yinelemesi başlatıyoruz.

(10) Son satırda olumsuz bir unsur bulunmadığından, bu, optimal üretim planını bulduğumuz anlamına gelir! Yani: "Temel" sütununa taşınan ürünleri üreteceğiz - X1 ve X2. Her bir çıktı biriminin üretiminden elde edilen karı biliyoruz ( matris C). Ürün 1 ve 2'nin bulunan çıktı hacimlerini 1 parça başına karla çarpmaya devam ediyor, finali alıyoruz ( maksimum! ) belirli bir üretim planı kapsamında kâr.

CEVAP:

X1=32 adet, X2=20 adet, X3=0 adet, X4=0 adet

P \u003d 48 * 32 + 33 * 20 \u003d 2.196 ruble.

Galyautdinov R.R.

© Materyali kopyalamaya yalnızca doğrudan bir köprü belirtirseniz izin verilir.