Yapay değişkenler simpleks yöntemi. Yapay temel yöntemiyle doğrusal programlama problemlerinin çözümü

Yöntem yapay temel(M-sorunu).

Ana problem şeklinde yazılan ve referans planları olan birçok doğrusal programlama problemi için, P j vektörleri arasında her zaman m birim vektör yoktur.

Aşağıdaki sorunu göz önünde bulundurun:

fonksiyonunun maksimumunu bulması istensin.

F = C 1 x 1 + C 2 x 2 + ……+ C n x n (1)

koşullar altında

……………………………………… (2)

nerede B ben  0 ( ben= l, m), m<.>n ve P 1, P 2, ..., P n vektörleri arasında m birim vektör yoktur.

Tanım... Bir fonksiyonun maksimum değerini belirleme görevi

F= c 1 x 1 + C 2 x 2 + ……+ C n x n -Mx n +1 - ... - Mx n + m (3)

koşullar altında

……………………………………… (4)

M, belirli bir değeri genellikle belirtilmeyen, yeterince büyük bir pozitif sayı olduğunda, problem (1) - (2) ile ilgili olarak genişletilmiş problem (M-problemi) olarak adlandırılır.

Genişletilmiş sorunun bir temeli var

X = (0; 0; ...; 0; b1; B 2 ; ...; b m).

birim vektörler sistemi tarafından belirlenir P n +1; r n + 2 , … r n + t , olarak adlandırılan m-ro vektör uzayının bir temelini oluşturan yapay. Vektörlerin kendileri ve değişkenler x n + ben ( ben= ben, m), arandı yapay. Genişletilmiş problemin temel bir planı olduğu için çözümü bulunabilir. tek yönlü yöntem.

teorem Optimal planda ise X * = ( x * 1 , x* 2 , ...; x* n , x* n +1 ; ...; x* n + m) genişletilmiş görev (3) - (4) yapay değişken değerleri x* n + ben = 0 ( ben=1, m), sonra X * = ( x * 1 , x* 2 , ...; x* n) en uygun görev planıdır (1) - (2).

Böylece, genişletilmiş problemin bulunan optimal planında, yapay değişkenlerin değerleri sıfıra eşitse, orijinal problemin optimal planı elde edilir.

∆ 0, ∆ 1,…, ∆ n dizin satırının değerleri, biri aşağıdakilere bağlı olan iki bölümden oluşur. M, ve diğeri değil. Tek yönlü doldurun - normal bir tek yönlü tablodan bir satır fazla içeren bir tablo. Bu durumda, (m + 2). satır aşağıdaki katsayıları içerir: M, ve (m + 1) th - içermeyen terimlerde M. Bir referans plandan diğerine geçerken, (m + 2) inci satırdaki en büyük negatif sayıya karşılık gelen vektör tabana dahil edilir. Temelden hariç tutulan yapay vektör, sonraki tek yönlü tabloya kaydedilmez. Bir temel plandan diğerine geçiş sırasında simpleks tabloların yeniden hesaplanması aşağıdakilere göre yapılır: Genel kurallar simpleks yöntemi.

(m + 2) -ve satırı boyunca yinelemeli süreç şuna kadar devam eder:

ya tüm yapay vektörler temelden dışlanmayacaktır;

veya tüm yapay vektörler hariç tutulmaz, ancak (m + 2). satır ∆ 1,…, ∆ n endekslerinde daha fazla negatif öğe içermez.

İlk durumda, temel, orijinal problemin bazı temel planına karşılık gelir ve optimal planının belirlenmesine (m + 1). sıra boyunca devam edilir.

İkinci durumda, eğer ∆ 0 değeri negatifse, asıl problemin çözümü yoktur; ∆ 0 = 0 ise, orijinal problemin bulunan destek planı dejeneredir ve taban, yapay temelin vektörlerinden en az birini içerir.

Probleme çözüm bulma aşamaları (1) - (2)

yapay temel yöntemi:

Genişletilmiş problem (3) - (4) oluşturulur.

Genişletilmiş görevin temel planını bulun.

Simpleks yönteminin olağan hesaplamaları, yapay değişkenleri temelden hariç tutar. Sonuç olarak, ya asıl problemin (1) - (2) temel planı bulunur, ya da kararsızlığı kurulur.

(1) - (2) numaralı problemin bulunan destek planı kullanılarak, simpleks yöntemiyle ya orijinal problemin optimal planı bulunur ya da kararsızlığı belirlenir.

Örnek.

Bir fonksiyonun minimumunu bulun F= - 2x 1 + 3x 2 - 6x 3 - x 4

NS Kısıtlamalarla:

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2x 2 + 4x 3 ≤22

x 1 -x 2 + 2x 3 ≥10

x ben ≥0, ben=1,4

Çözüm.

hadi yazalım bu görev ana görev şeklinde: maksimum işlevi bulun F= 2x 1 - 3x 2 + 6x 3 + x 4

kısıtlamalar ile:

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2x 2 + 4x 3 + x 5 = 22

x 1 -x 2 + 2x 3 - x 6 = 10

x ben ≥0, ben=1, 6

Son problemin denklem sisteminde, bilinmeyenlerdeki katsayılardan vektörleri ele alıyoruz:

P 1 vektörleri arasında, r 2 , … P 6 sadece iki single (P 4 ve P 5). Bu nedenle, Sol Taraf problemin kısıtlamalar sisteminin üçüncü denklemi, negatif olmayan ek bir değişken x ekleriz 7 ve işlevi maksimize etmenin genişletilmiş problemini düşünün

F= 2x 1 - 3x 2 + 6x 3 + x 4 - Мх7

kısıtlamalar ile:

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2x 2 + 4x 3 + x 5 = 22

x 1 -x 2 + 2x 3 - x 6 + x 7 = 10

Genişletilmiş problem, üç birim vektörden oluşan bir sistem tarafından belirlenen bir X = (0; 0; 0; 24; 22; 0; 10) taban çizgisine sahiptir: P 4, P 5, P 7.

İkili (eşlenik) problem kavramı doğrusal programlama.

İnşaat kuralları ikili görev.

Her bir doğrusal programlama problemi (LPP) ile, orijinal probleme göre ikili problem (veya birleşik) olarak adlandırılır ve buna doğrudan denir.

İkili problem, standart biçimde yazılmış, doğrudan problemle ilgili olarak oluşturulmuştur:

F = c 1 x 1 + c 2 x 2 +… + c n x n  maks (3,6)

a 11 x 1 + a 12 x 2 +… + a 1n x n ≤ b 1,

a 21 x 1 + a 22 x 2 +… + a 2n x n ≤ b 2,

………………………………

a k1 x 1 + bir k2 x 2 +… + bir kn x n ≤ = b k, (3.7)

bir k + 1,1 x 1 + bir k + 1,2 x 2 +… + bir k + 1, n x n = b k + 1,

………………………………

bir m1 x 1 + bir m2 x 2 +… + bir mn x n = b m,

x j ≥ 0,, ben≤ n (3.8)

Bir fonksiyonun minimum değerini bulma problemi

L = b 1 y 1 + b 2 y 2 +… + b m y m (3,9)

koşullar altında

a 11 yıl 1 + bir 12 yıl 2 +… + bir m1 y m ≥ c 1

a 21 yıl 1 + 22 yıl 2 +… + bir m2 y m ≥ c 2

………………………………

1 ben y 1 + bir 2 ben y 2 +… + bir m ben y m ≥ c ben (3.10)

a ben+1,1 y 1 + bir ben+1,2 y 2 + ... + bir ben+ 1, m y m = c l + 1

………………………………

bir m1 y 1 + bir m2 y 2 +… + bir mn y m = c m

y ben ≥ 0,, k ≤ m (3.11)

(3.6) - (3.8) problemine göre ikili denir.

İkili problem oluşturma kuralları tabloda verilmiştir:

ZLP'nin yapısal özellikleri	Doğrusal programlama sorunu
		Çift
1. Amaç işlevi	Maksimizasyon (maks)	Minimize etme (dk)
2. Değişken sayısı	n değişken	Doğrudan problemin (3.7) kısıtlarının sayısına eşit, y i, yani. m
3. Kısıtlama sayısı	m kısıtlamaları	Doğrudan problemin değişkenlerinin sayısına eşittir x j, yani. n
4. Kısıtlamalar sistemindeki katsayıların matrisi
5. Amaç fonksiyonundaki değişkenlerin katsayıları	c 1, c 2, ..., cn	b 1, b 2, ..., b m
6. Sağ kısım kısıtlama sistemleri	b 1, b 2, ..., b m	c 1, c 2, ..., cn
7. Kısıtlama sistemindeki işaretler	a) x j ≥ 0- negatif olmama koşulu	j-th kısıtlaması "≥" işaretine sahiptir
	b) x j değişkeni negatif olmama koşuluna tabi değildir	j-th kısıtlamasında "=" işareti var
	c) i-inci kısıtlama "≤" işaretine sahiptir	değişken y ben ≥0
	d) i. kısıtlama "=" işaretine sahiptir	y i değişkeni negatif olmama koşuluna tabi değildir

Not

Maksimuma doğrudan sorun ve minimuma ikili, karşılıklı olarak ikili sorunlardır. Bu nedenle, (3.9) - (3.11) problemini doğrudan bir LPP ve (3.6) - (3.8) problemini ikili problemi olarak kabul edebiliriz. Bu durumda, ikili bir LPP oluşturma kuralları yalnızca aşağıdakilerle geçerli kalır: bu değişiklik minimum problemin ilk problem olduğu kabul edilir.

Orijinal problem maksimumda (min) ve kısıtlamalar sisteminde çözülürse) ben-e ( J-f) kısıtlama "≤" ("≥") işaretine sahipse, ikili problemi oluşturmak için gereklidir:

a) ya her iki parçayı da çarpın ben NS ( J-th) (-1) ile eşitsizlik ve işareti "≤" ("≥") olarak değiştirin

b) ya getirmek ben-e ( J-f) ek bir x değişkeni ekleyerek eşitlik kısıtlaması n + ben ≥0

Simpleks yöntemini kullanmak için gerekli bir koşul, bir destek planının, yani kanonik denklem sisteminin kabul edilebilir bir temel çözümünün varlığıdır. Bunun için aşağıdaki koşulların karşılanması gerekir:

• sistem kanonik (kademeli) bir yapıya sahip olmalıdır;
• sadece eşitlik kısıtlamaları vardır;
• kısıtlamaların sağ tarafları pozitiftir;
• değişken görevler pozitif.

Bu koşullar olmadan, temel bir plan elde edemezsiniz. Bununla birlikte, gerçek problemlerde, listelenen koşullar her zaman yerine getirilmekten uzaktır.

Herhangi bir doğrusal programlama problemi için bir başlangıç ​​taban çizgisi elde etmenizi sağlayan yapay temel adı verilen özel bir teknik vardır.

Doğrusal programlama probleminin standart forma indirgenmesine izin verin:

Tüm /? > 0, ancak temel değişkenlerin bazıları veya tümü negatif, X; 0. Bu nedenle referans planı yoktur.

Kısıt denklemlerini yapay değişkenlerle destekliyoruz (tüm x j j - 1, NS).

Tanıtmak T değişkenler (denklem sayısına göre): x 1M t, hangi yeni sistem temel ve olumsuz olacak NS-

Sonuç olarak, aşağıdaki eşdeğer problemi elde ederiz.

Burada değişkenler xn + ben orijinal doğrusal programlama problemi ile ilgisi yoktur. Yalnızca bir referans planı elde etmeye hizmet ederler ve kukla değişkenler olarak adlandırılırlar. ve yeni

Problemin tam olması için amaç fonksiyonu /(.t) oluşturulur.

Optimal bir referans planında kukla değişkenler sıfır olmalıdır. Aksi takdirde, orijinal sorunun durumu ihlal edilecektir.

Başlangıç ​​referans planında kukla değişkenler temeldir, yani sıfıra eşit değildir ve optimal planda kukla değişkenler sıfıra eşit olmalıdır. Bu, yapay değişkenlerin optimal şekilde serbest olması gerektiği anlamına gelir. Bu çeviri, yöntemin ana fikridir: yapay değişkenlerin temel değişkenlerden serbest olanlara çevrilmesi. Bir örnek kullanarak böyle bir çevirinin mekanizmasını ele alalım.

PLP'yi standart bir biçimde yeniden yazalım. Bunu yapmak için ek değişkenler tanıtıyoruz x), xA, x 5, x 6 ve görevi yaz kanonik biçim.

Serbest değişkenler x, NS 2 = 0, temel değişkenler ise x 3 = -5, x 4 = -5, x 5 = 7, x 6 = 9 değerlerini alacak. Baz değişkenlerin bazıları negatif olduğu için mevcut bir plan yoktur. Başlangıç ​​temel planını elde etmek için, ilk iki kısıt denkleminde x 7, x 8 değişkenlerini tanıtıyoruz ve yardımcı bir problem formüle ediyoruz:

Böylece, başlangıç ​​temeli

Yapay temelli tek yönlü masa

	NS4

Referans planlarının sıralarını yazalım.

Artışın ilk üç adımı için ve yalnızca yapay değişkenlere dahil edilen yapay değişkenler tarafından hesaplanır. hedef fonksiyon/(NS) = x 7 + x 8 katsayısı c, = 1.

Üçüncü adımda, yapay değişkenler hariç tutulur, çünkü tüm ve pozitif.

Bu nedenle, yapay değişkenlerin tanıtıldığı simpleks yöntemi iki aşama içerir.

Yapay değişkenlerin tanıtılmasıyla yardımcı DP probleminin oluşumu ve çözümü. İlk referans planındaki mankenler temeldir. Kukla amaç fonksiyonu yalnızca kukla değişkenleri içerir. Bitişik referans planları elde ederken, yapay değişkenleri temelden serbest olanlara aktarıyoruz. Sonuç olarak, yardımcı problem f(x)=0 için optimal bir temel plan elde edilmiştir.

Yardımcı LP görevi için en uygun destek planı, ana LP görevi için ilk referans planıdır. Problem, orijinal amaç fonksiyonu f(x) için olağan simpleks yöntemiyle çözülür.

Uyarılar

• 1. Yapay değişkenlerin tanıtılması iki durumda gereklidir:
  • bir dizi temel değişken x kanonik biçimde negatiftir;
  • kanonik forma indirgemek zorsa, herhangi bir denklem kısıtlamasına yapay bir değişken eklemeniz yeterlidir.
• 2. Pratikte bulundu otomatik kontrol doğrusal programlama problemleri 500 ila 1500 arasında kısıt ve 1000'den fazla değişken içerir. Bu boyuttaki sorunların ancak bir bilgisayar ve özel bir bilgisayar yardımı ile çözülebileceği açıktır. yazılım... Algoritmanın karmaşıklığı şudur:
  • RFP standart bir form gerektirir;
  • Bu boyuttaki problemler için PPP ana bilgisayarlar(ve paralel hesaplama), çünkü tek yönlü yöntem tüm tabloyu depolar.
• 3. Simpleks yönteminin hesaplama verimliliği aşağıdaki göstergelerle tahmin edilebilir:
  • adım sayısı (bitişik taban çizgileri);
  • bilgisayar zamanının maliyeti.

için böyle teorik tahminler var. standart görev ile doğrusal programlama T kısıtlamalar ve "" değişkenler:

• ortalama adımlar * 2 T ve aralıkta yatıyor)