Doğrusal programlama problemlerinin çözümü için Simpleks yöntemi. Doğrusal programlama problemlerini çözmek için dikkate alınan yöntemler pratikte yaygın olarak kullanılmaktadır. Ancak şunu belirtmek gerekir ki

Simpleks yöntemi

1. Simpleks yöntemi fikri

Hadi düşünelim evrensel yöntem kanonik LP probleminin çözümleri.

simpleks yöntemi olarak bilinir.

Bölüm 2'de belirlendiği gibi, kanonik bir problemin plan kümesi, sonlu sayıda köşe noktasına sahip dışbükey çokyüzlü bir kümedir. Ve eğer bu problemin optimal bir çözümü varsa, o zaman bu çözüme en azından bir köşe noktasında ulaşılır.

Herhangi bir köşe noktasıyla ilişkili temel plan değişkenlerin sıfıra eşit olduğu ve geri kalan değişkenlerin durum matrisinin doğrusal olarak bağımsız sütunlarına karşılık geldiği problem. Bu doğrusal olarak bağımsız sütunlar, tekil olmayan bir temel matris oluşturur.

Tüm köşe noktalarının yinelenmesi hesaplama açısından pahalıdır ve bu nedenle etkisizdir. 1944'te J. Dantzig, köşe noktalarının numaralandırılması için düzenli bir prosedür önerdi; burada en uygun çözümü bulmak için köşe noktalarının yalnızca küçük bir kısmını incelemek yeterliydi. Bu prosedüre simpleks yöntemi denir.

J. Danzig, bir uç noktadan diğerine hareket ederken temel matristeki yalnızca bir vektörün değiştirilmesini önerdi. Bu, böyle bir geçiş sırasında temel değişkenlerden birini hariç tutmamız - onu temel olmayan (sıfıra eşit) hale getirmemiz ve onun yerine temel olmayan (sıfır) arasından yeni bir değişken eklememiz - onu temel (pozitif) hale getirmemiz gerektiği anlamına gelir. ).

Geometrik olarak böyle bir değiştirmenin, bir köşe noktasından bitişik noktaya, önceki noktaya ortak bir kenarla bağlanan bir geçişe yol açtığı ortaya çıktı.

Komşu noktalardan amaç fonksiyonunun en fazla arttığı nokta seçilir. Köşe noktalarının sayısı sonlu olduğundan, sonlu sayıda geçiş yoluyla tepe noktası en yüksek değer Amaç fonksiyonu veya amaç fonksiyonunun sınırsızlığı sınırsız sayıda plan üzerine kurulacaktır.

Genel şema Simpleks yöntemi aşağıdaki temel adımlardan oluşur.

· 0 adım. Başlangıç ​​temelinin ve karşılık gelen başlangıç ​​köşe noktasının (taban çizgisi) belirlenmesi.

· 1 adım. Mevcut temel planın optimallik açısından kontrol edilmesi. Eğer optimallik kriteri karşılanıyorsa plan optimaldir ve çözüm tamamlanmıştır. Aksi takdirde 2. adıma gidin.

· Adım 2. Temel olanlara eklenen değişkeni bulma. (Amaç fonksiyonunun arttırılması koşulundan).

· Aşama 3. Temel değişkenlerin dışında kalan bir değişkenin bulunması (Problemin kısıtlarının korunması şartıyla).

· 4. Adım. Yeni taban çizgisinin (bitişik köşe noktası) koordinatlarını bulma. 1. adıma gidin.

Tekrarlanan 1-4 adımları, simpleks yönteminin bir yinelemesini oluşturur.

Bu şemadan, ilk olarak, simpleks yöntemini başlatmak için, bir tür köşe noktasına (bir başlangıç ​​temel planı) sahip olmanız gerektiği ve ikinci olarak, tüm bitişikleri hesaplamadan mevcut köşe noktasını optimallik açısından inceleyebilmeniz gerektiği anlaşılmaktadır. köşeler. Eğer kanonik DP problemi belirli bir değere sahipse bu problemler kolayca çözülebilir. özel Tip.

Tanım. Kanonik DP probleminin “tercih edilen bir forma” sahip olduğunu söyleyeceğiz.

1.Denklemlerin sağ tarafları, .

Koşul matrisi boyutunda bir birim alt matris içerir

Başka bir deyişle, herhangi bir denklemde katsayılı bir değişken vardır. bire eşit diğer denklemlerde eksik. Koşul 1 zahmetli değildir, çünkü bazı denklemlerin sağ tarafının negatif olması durumunda bunu (-1) ile çarpmak yeterlidir. Tercihli türde bir problemde başlangıç ​​taban çizgisini bulmak çok basittir.

Örnek .

Koşul matrisi ve kısıtlamaların sağ taraflarının vektörü şu şekildedir:

Bir temel matris hemen bellidir: birim vektörlerle

Sonuç olarak, temel değişkenlerdir ve x2, x4 temel değildir. Denklem sisteminde x2=x4 =0 olduğunu varsayarsak, hemen x1 =10, x3 =20, x5 =8'i buluruz. Temel değişkenlerin değerlerinin kısıtların sağ taraflarına eşit olduğunu görüyoruz. Bundan bi'nin sağ taraflarının pozitif olması gerekliliği açıktır.

Gelecekte temel değişkenleri bir vektörde birleştireceğiz XB.

Böylece, kanonik sorun Tercih edilen formda, birim alt matrisi AB =E başlangıç ​​temel matrisi olarak alınır ve karşılık gelen temel değişkenler kısıtlamaların sağ taraflarına eşittir: xB =b.

. Simpleks yönteminin en basit uygulaması

Simpleks yönteminin en basit uygulaması (“basit C-yöntemi”), “tercih edilen biçime” sahip olan kanonik DP problemine uygulanır. Genelliği kaybetmeden, kimlik alt matrisinin ilk m sütununda yer aldığını varsayacağız. Daha sonra kanonik problem yazılacaktır. Aşağıdaki şekilde

f(x) = c 1X 1+ c 2X 2+… + c M X M + c m+1 X m+1 +… + c N X N ??maks(3.1)x 1+bir 1 ay+1 X m+1 + … + bir 1n X N = b 1(3.2)x 2+bir 2 ay+1 X m+1 + … + bir 2n X N = b 2………………………………………………………….X M +bir mm+1 X m+1 + … + bir milyon X N = b M X J ³ 0, j=1,2,…, n.(3.3)

Durum Matrisi

ilk m sütununda m x m boyutunda bir birim alt matrisi içerir, dolayısıyla AB =(A1, A2,…, Am)=E.

Simpleks yönteminin temel adımları (teori)

Birim taban matrisi, koşul matrisinin ilk m sütununda yer aldığından, başlangıç ​​temel planının ilk m koordinatları temel, son n - m koordinatları ise temel değildir, yani sıfıra eşittir:

o = (x1, x2,…, xm, 0,…, 0).

Xo noktasının koordinatlarını kısıtlamalara (3.2) yerleştirdiğimizde ve m+1 =... = xn = 0 olduğunu dikkate aldığımızda şunu elde ederiz: x1 = b1, x2 = b2,..., xm = bm, yani, xoB = b.

Yani ilk temel plan şöyle görünür:

xo = (b1,…, bm, 0,…, 0),

burada сБ = (с1,…, сm) temel değişkenler için amaç fonksiyonunun katsayılarından oluşan bir vektördür.

1 adım.

Kısıtlamalar sisteminden (3.2), temel değişkenleri temel olmayanlar cinsinden ifade ediyoruz:

X 1= b 1 -A 1 ay+1 X m+1 - ... - A 1n X N, X 2= b 2-A 2 ay+1 X m+1 - ... - A 2n X N, ………………………………………… X M = b M -A mm+1 X m+1 - ... - amk X N, (3.4)

Bu ifadeleri yerine koyalım hedef işlevi (3.1).

f(x)=c 1(B 1-A 1 ay+1 X m+1 - ... - A 1n X N) + c 2(B 2-A 2 ay+1 X m+1 - ... - a2n X N ) +

………………………………………………..

C M (B M -A mm+1 X m+1 - ... - A milyon X N ) + c m+1 X m+1 +… +cn X N .

Terimleri aynı temel olmayan değişkenlerle gruplayalım:

f (x) = - (c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1).xm+1 - …-

- (C 1 A 1n + c 2 A 2n + … + c M A milyon - C N). X N. (3.5)

Buradaki ifadelere dikkat edin parantezşeklinde yazılabilir

C 1 A 1 ay+1 + c 2 A 2 ay+1 + … + c M A mm+1 - C m+1 = < cB , A m+1 > - c m+1 = D m+1 ,

…………………………………………………………………………………………………………………………1 A 1n + c 2 A 2n + … + c M A milyon - C n= < cB , A N > - c n= D N ,

nerede B = (ile 1,…, İle M ) temel değişkenler için amaç fonksiyonunun katsayılarından oluşan bir vektördür, A m+1 ,…, A N - temel olmayan değişkenler için A koşul matrisinin sütunları x m+1,…, x N .

İfade

D J = < сB , A J > - cj , j = m+1,…, n,(3.6)

simpleks farkları veya simpleks temel tahminleri denir.

(3.6) dikkate alınarak amaç fonksiyonu için formül (3.5) şu şekilde yeniden yazılabilir:

Bu formül, temel planın optimalliğine dair bir işaret elde etmemizi sağlar. Temel olmayan sayılara sahip tüm simpleks tahminleri D j ³ 0 ise, mevcut temel plan optimaldir.

Aslında, eğer en az bir tahmin, örneğin ?k, kesinlikle negatifse, o zaman karşılık gelen temel olmayan değişken xk'ye pozitif bir değer veririz ve x planının geri kalan temel olmayan değişkenlerini sıfıra eşitlersek, şunu elde ederiz:

f(x) = f(x Ö ) - D k X k =f(x Ö ) + | D k | X k > f(x Ö ),(3.7)

yani bu durumda plan x Ö geliştirilebilir.

Birim bazlı sütunlara karşılık gelen simpleks tahminlerinin her zaman 0'a eşit olup olmadığını kontrol etmek kolaydır.

Adım 2. Temel değişkenlere eklenen değişkenin bulunması.

Formül (3.7)'den takip edildiği gibi, temel değişkenlere temel olmayan bir x değişkeni dahil edilerek (onu pozitif hale getirerek) amaç fonksiyonu artırılabilir. J hangisi olumsuz bir derecelendirmeye karşılık gelir? J < 0. Если таких оценок несколько, то обычно в состав базисных вводят небазисную переменную хİle en büyük mutlak negatif tahmine sahip olan, yani

burada D j =< CБ, Aj >- cj, j = m+1,…, n (temel olmayan değişkenlerin sayısı).

Bu şekilde elde ederiz yeni plan

x1 = (x1,…, xm,0,…, xk,…, 0,…, 0).

Ancak x1 temel olmayan bir plandır, pozitif koordinatların sayısı m+1'e eşit olduğundan sıfır koordinatların sayısı n - m -1'e eşittir.

Yeni bir köşe noktası elde etmek için temel değişkenlerden birini sıfıra ayarlayalım, yani temel değişkenlerden bir değişkeni çıkaralım.

Aşama 3.

x1 noktasının koordinatlarını (3.4) koşullarına koyalım ve xj değişkenlerinin negatif olmaması gerektiğini hesaba katalım.

X 1= b 1-A 1 bin X k ³ 0x 2= b 2-A 2 bin X k ³ 0 …………………………. X M = b M -A mk xk ³ 0(3.8)

Formül (3.7)'den, x'in değerinin ne kadar büyük olduğu açıktır. İle > 0 ise amaç fonksiyonu arttıkça artar. x'in maksimum değerini bulmaya çalışalım İle problemin kısıtlarını ihlal etmeden ve olumsuzluk içermeme koşullarını (3.8) yerine getirmeden.

Eşitsizlikler (3.8) şu şekilde yeniden yazılabilir:

A 1 bin X k £ B 1 A 2 bin X k £ B 2 ………………A mk X k £ B M (3.9)

Eşitsizlik sistemini (3.9) çözerken iki durum mümkündür: x'in katsayıları arasında İle olumlu değil: a pek £ 0, i=1,2,…, m. b'den beri Ben > 0 ise, herhangi bir keyfi durum için eşitsizlikler (3.9) sağlanır. büyük önem X İle. Bu, amaç fonksiyonunun planlar kümesiyle sınırlı olmadığını göstermektedir (max f(x) ® ¥ ) ve dolayısıyla DP probleminin bir çözümü yoktur.) x'in katsayıları arasında İle pozitif bir var pek > 0. Eşitsizlik sistemini (3.9) çözerek şunu elde ederiz:

X İle £ B Ben /A pek , her şey için, hangi aik için > 0.(3.10)

En büyük x değeri İle Tüm kısıtlamaları (3.10) sağlayan, bu eşitsizliklerin sağ tarafındaki oranların en küçüğüne eşittir

X İle =dakika(b Ben /A pek ) her şey için: aik > 0.

Minimumun i = r'de, yani x'te elde edilmesine izin verin. İle ? B R /A rk . Bu, temel değişken x'in olduğu anlamına gelir R (3.8) koşulları altında yok olur.

X R = b R -A rk X k = b R -A rk (B R /ark ) = 0, 1 ??r ??m.

Değişken x R esastan hariç tutulmuştur. Bu nedenle, elimizde yeni kadro temel ve temel olmayan değişkenler, orijinalinden bir temel ve bir temel olmayan koordinatta farklılık gösterir.

4. Adım

Yeni temel şöyle görünecek

1= (x 1, X 2,…, 0,…, x M , 0,…, xk ,0,…, 0),

x'in yeri nerede R maliyeti sıfır ve x İle > 0.bu temel plan yeni bir temel matrise karşılık gelir:

Yeni bir x1 köşe noktasının koordinatlarını bulmak için kanonik DP problemi yeni bir tercih edilen forma, yani matrisin özdeşlik (= E) olacağı bir forma indirgenir. Bunu yapmak için Ak sütununun birim temsiline dönüştürülmesi gerekir,

R-inci çizgi,

hangi katsayı = 1 ve diğer tüm elemanlar =0, ben ??r. Bu, sistemin denklemleri üzerindeki temel işlemler kullanılarak başarılabilir. Çözüm, bir noktada tüm tahminlerin Dj ³ 0 olması durumunda sona erer.

3. Simpleks yönteminin bir örnek kullanılarak uygulanması

Bölüm 2'deki bir örneği kullanarak simpleks yönteminin uygulanmasını gösterelim.

Kanonik LP problemini düşünün

f(x) = x 1+ 2x 2 +0x 3 +0x 4maksimum(3.11)-x 1+ 2x 2+x 3= 4,(3,12)3 x 1 +2x 2+x 4= 12,(3.13)x J? 0,j = 1,2,3,4.(3.14)

Koşul matrisi A = (A 1, A 2, A 3 A 4), Nerede

Hedef vektör c =(c1, c2, c3, c4)=(1, 2, 0, 0); sağ tarafların vektörü b=(b1, b2) = (4, 12).

0 adım. Başlangıç ​​köşe noktasını (taban çizgisi) bulma.

Denklemlerin sağ tarafları pozitif olduğundan ve A3, A4 koşulları matrisinin sütunları bir birim alt matris oluşturduğundan problem tercih edilebilir bir forma sahiptir. Bu, başlangıç ​​temel matrisi = (A3, A4); x3 ve x4 temel değişkenlerdir, x1 ve x2 temel olmayan değişkenlerdir, cB = (c3, c4) = (0, 0).

İlk temel şuna benziyor

x0 = (0, 0, x3, x4) = (0, 0, 4, 12); f(xo) = 0.

1 adım. Temel planın optimallik açısından kontrol edilmesi.

Temel olmayan değişkenler için simpleks tahminlerini formül (3.6) kullanarak hesaplayalım.

D1 =< cБ, A1 >- c1 = 0 ·(-1) + 0 ·3 - 1 = -1.

D2 =< cБ, A2 >- c2 = 0 · 2 + 0 · 2 - 2 = -2.

Tahminler negatif olduğundan plan xo optimal değildir. Amaç fonksiyonunun daha büyük değerine sahip yeni bir taban çizgisi (bitişik köşe noktası) arayacağız.

Adım 2. Tabana eklenen değişkeni bulma.

Her iki tahmin de Dj olduğundan, temel olmayan x1 veya x2 değişkenlerinden biri temel değişkenlere dahil edilirse (pozitif hale getirilirse) amaç fonksiyonu artırılabilir.< 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x2.

Aşama 3. Temelden türetilen bir değişkenin tanımı.

Temele x2 değişkeni girildikten sonra yeni plan1 = (0, x2, x3, x4) formuna sahip olacaktır.

Bu plan temel bir plan değildir, çünkü yalnızca bir sıfır koordinatı içerir, bu da x3 veya x4 değişkenlerinden birini sıfır yapmak (temelden hariç tutmak) gerektiği anlamına gelir.

Plan koordinatlarını x1 = (0, x2, x3, x4) problem kısıtlarına koyalım. Aldık

Buradan x3 ve x4 temel değişkenlerini tabana eklenen x2 değişkeni üzerinden ifade edelim.

X 3= 4 - 2x 2,(3.15)x 4= 12 - 2x2 .(3.16)

Yani değişkenler x 3ve x 4 negatif olmamalıdır, bir eşitsizlik sistemi elde ederiz

4 - 2x 2 ³ 0 ,(3.17)12 - 2x 2 ³ 0 .(3.18)

X değeri ne kadar büyükse 2amaç fonksiyonu arttıkça artar. Problemin kısıtlarını ihlal etmeyen, yani (3.17), (3.18) koşullarını sağlayan yeni temel değişkenin maksimum değerini bulalım.

Eşitsizlikleri formda yeniden yazalım.

x2 £ 4,

x2 £ 12,

x'in maksimum değeri nerede 2= min (4/2, 12/2) = 2. Bu değeri x için (3.15), (3.16) ifadelerinde yerine koyarsak 3ve x 4, x'i elde ederiz 3= 0. Bu nedenle x 3 temelden türetilmiş .

4. AdımYeni taban çizgisinin koordinatlarının belirlenmesi.

Yeni taban çizgisi (bitişik köşe noktası):

X 1= (0, x2, 0.x 4).

Bu noktanın temeli A2 ve A4 sütunlarından oluşur, yani = (A2, A4). A2 = (2, 2) vektörü olduğundan ve bu nedenle (3.11) - (3.14) probleminin yeni tabana göre tercih edilen bir formu olmadığından bu tabanın üniter olmadığına dikkat edin. Problemin koşullarını (3.12), (3.13) yeni temel değişkenler x2, x4'e göre tercih edilen formu alacak şekilde dönüştürelim, yani x2 değişkeni bir katsayı ile ilk denkleme dahil olsun. bire eşittir ve ikinci denklemde mevcut değildir. Problemin denklemlerini yeniden yazalım.

x1+ 2x2+ x3 = 4, (p1)

x1 +2x2 + x4 = 12. (p2)

İlk denklemi x2 katsayısına bölelim. Orijinaline eşdeğer yeni bir denklem = p1 / 2 elde ediyoruz

1/2 x1+ x2+ 1/2 x3 = 2. ()

Çözümleme dediğimiz bu denklemi ikinci denklemdeki x2 değişkenini elemek için kullanıyoruz. Bunu yapmak için denklemi 2 ile çarpıp p2'den çıkarmanız gerekir. = p2 - 2 = p2 - p1 denklemini elde ederiz.

x1 - x3 + x4 = 8. ()

Sonuç olarak, yeni bir "tercih edilen" temsil aldık orijinal sorun(3.11) - (3.14) yeni temel değişkenler x2, x4'e göre:

f(x) = x1+ 2x2 + 0 x3 + 0 x4® maks

1/2 x1+ x2+ 1/2 x3 = 2. ()

x1 - x3 + x4 = 8. ()

xj ³ 0, j = 1,2,3,4.

Burada yeni temel plan x1 = (0, x2,0, x4) gösterimini değiştirerek, temel değişkenlerin değerleri denklemlerin sağ taraflarına eşit olduğundan koordinatlarını hemen buluruz.

x1 = (0,2,0,8); f(x1)=4.

Bu ilk yinelemeyi tamamlar simpleks yöntemi. Daha sonra, problem çözme süreci, bulunan planın optimallik açısından kontrol edilmesini içeren 1. adımdan itibaren devam eder. Çözüm, mevcut temel planın tüm simpleks tahminlerinin negatif olmadığı ortaya çıktığında sona erer.

Simpleks yönteminin tüm hesaplamalarını tablo şeklinde yapmak daha uygun olduğundan, ikinci yinelemeyi birincinin şemasına göre yapmayacağız.

simpleks değişkeni kanonik programlama

Edebiyat

1. Ekonometri: Ders Kitabı / Ed. I.I. Eliseeva. - M.: Finans ve İstatistik, 2002. - 344 s.: hasta.

Ekonometri çalıştayı: Proc. harçlık / I.I. Eliseeva, S.V. Kurysheva, N.M. Gordeenko ve diğerleri; Ed. I.I. Eliseeva. - M .: Finans ve İstatistik, 2002. - 192 s .: hasta.

Kremer N.Ş., Putko B.A. Ekonometri: Üniversiteler için ders kitabı. - M.: BİRLİK-DANA, 2002. - 311 s.

Magnus Y.R., Katyshev P.K., Peresetsky A.A. Ekonometri. Başlangıç ​​kursu: ders kitabı. - M .: Delo, 2001. - 400 s.

Katyshev P.K., Magnus Y.R., Peresetsky A.A. Sorunların toplanması başlangıç ​​kursu Ekonometri. - 3. baskı, rev. - M .: Delo, 2003. - 208 s.

Dougherty K. Ekonometriye giriş. - M .: Finans ve İstatistik, 1999.

Johnston J. Ekonometrik yöntemler. - M .: İstatistikler, 1980.

Kane E. Ekonomik istatistik ve ekonometri. Niceliksel ekonomik analize giriş. Cilt 1. - M .: İstatistikler, 1977.

Lange O. Ekonometriye giriş / Çev. Polonya'dan - M .: İlerleme, 1964.

Lizer S. Ekonometrik yöntemler ve problemler. - M .: İstatistikler, 1971.

Malenvo E. Ekonometrinin istatistiksel yöntemleri. - M .: İstatistikler, 1976.

Tintner G. Ekonometriye giriş. - M .: Finans ve İstatistik, 1965.

Ayvazyan S.A., Mkhitaryan V.S. Uygulamalı istatistik ve ekonometrinin temelleri: üniversiteler için bir ders kitabı. - M.: BİRLİK, 1998.

Ventzel E.S. Olasılık teorisi: Üniversiteler için ders kitabı. - 6. baskı. - M.: Daha yüksek. okul, 1999.

• Daha önce, bir doğrusal programlama probleminin optimal bir çözümü varsa, o zaman optimal çözümlerden birinin, sistemin kabul edilebilir çözümlerinin çokyüzlüsünün belirli bir köşe noktasına karşılık gelen, kısıtlamalar sistemine yönelik kabul edilebilir bir temel çözüm olduğu gösterilmişti.

• Problemin kısıtları sistemine yönelik temel çözümlerin sonlu bir aramasını kullanarak bu optimal çözümün nasıl bulunacağı gösterilmiştir. Bununla birlikte, problem kısıtlama sisteminin boyutu arttıkça, temel çözümlerin kapsamlı bir şekilde numaralandırılması yöntemiyle problemin çözümüne yönelik hesaplamaların hacmi katlanarak büyür ve pratikte uygunsuz hale gelir.

Yalnızca mümkün olan temel çözümlerin bir listesini düzenlemek ve sıralanan çözümlerin sayısını keskin bir şekilde azaltmak, eğer müteakip kabul edilebilir temel çözümlerin her biri, amaç fonksiyonunun karşılık gelen değerini iyileştirecek veya en azından bozulmayacak şekilde seçilirse mümkündür. Bu yaklaşım, en uygun temel çözümü bulurken adım sayısını azaltmanıza olanak tanır. Bu fikri grafiksel olarak açıklayalım.

ABCDEFGH poligonunun iki değişkenli PLP'nin uygulanabilir çözüm kümesini temsil etmesine izin verin ve N vektörü şöyle olsun: amaç fonksiyonunun gradyanı.

• Bu çokgenin amaç fonksiyonunun en küçük değeri aldığı noktayı bulmamız gerekiyor.

• Problemin B köşe noktasına karşılık gelen ilk uygun temel çözümü belirlensin.

• Tüm uygun temel çözümlerin tam olarak araştırılmasıyla, çokgenin sekiz köşe noktasına karşılık gelen bu tür sekiz çözümün incelenmesi gerekecektir.

• Bununla birlikte, N eğiminin yönü dikkate alındığında, problemin optimal temel çözümüne karşılık gelen komşu C köşesine, ardından komşu D köşesine hareket etmenin daha karlı olduğu şekilde açıkça görülmektedir.

• Bu nedenle sekiz çözüm yerine yalnızca üç uygun temel çözümün dikkate alınması gerekecektir.

• Çözümün sıralı olarak iyileştirilmesi fikri, doğrusal programlama problemlerini çözmek için evrensel yöntemin - simpleks yönteminin - temelini oluşturur.

Simpleks yönteminin geometrik anlamı, uygun çözümlerin çokyüzlünün bir köşesinden probleme, amaç fonksiyonunun önceki tepe noktasından daha kötü olmayan bir değer aldığı komşuya sıralı bir geçişin gerçekleştirilmesidir. Bu geçiş, en uygun çözüm bulunana veya problemin böyle bir çözüme sahip olmadığı anlaşılana kadar devam eder.

• Simpleks yöntemi ve adı ilk kez 1947'de Amerikalı matematikçi John Dantzig tarafından önerildi, ancak yöntemin fikirleri Rus matematikçi L.V. Kantorovich, 1939'da "Üretimi organize etmenin ve planlamanın matematiksel yöntemleri" makalesinde geri döndü.

Simpleks yöntemi üç ana unsurdan oluşur:

• soruna bazı ilk uygulanabilir temel çözümlerin belirlenmesi;

• bir sonraki en kötü olmayan kabul edilebilir temel çözüme geçiş kuralları;

• Bulunan çözümün optimalliğinin kontrol edilmesi.

• Simpleks yöntemi, kanonik biçimde yazılmış bir doğrusal programlama problemine uygulanır.

Bir doğrusal denklem sisteminin simpleks dönüşümleri

• ZLP'yi kanonik formda ele alalım. Bir doğrusal denklem sistemi verilsin:

• Bu sisteme doğrusal fonksiyonu en aza indirecek, negatif olmayan bir çözüm bulmamız gerekiyor.

• Denklem sisteminin matrisini (1) gösterelim,

• – bu sistemin genişletilmiş matrisi.

A ve B matrislerinin sıralarının eşit olduğu durumu ele alacağız: , yani. Sistem (1)'in sonsuz sayıda çözümü olduğunda. Görevimiz bu durumda soruna en uygun çözümlerin olup olmadığını ve bunların nasıl bulunacağını bulmaktır.

• Kesinlik sağlamak için, A matrisinin ilk r sütunlarının doğrusal olarak bağımsız olduğunu varsayıyoruz, ardından sistem (1) Gauss eleme yöntemini kullanarak şu forma dönüştürülebilir:

• Bu sistem denklem sistemine (1) eşdeğerdir. Oran Sütunları

• (2) sisteminin matrisinin sütun sisteminin temelini oluşturur ve bu nedenle değişkenler temeldir ve küme bir temel kümedir.

• Kısaltmak adına, değişkenlerin temel kümesini aynı zamanda katsayı sütunlarının karşılık gelen temeli anlamına gelen temel olarak adlandıracağız. Geriye kalan değişkenler ücretsizdir.

Sistem (3)'teki temel değişkenleri serbest olanlar cinsinden ifade edelim ve sistem (4)'ü elde edelim:

• (4)

• (4)'ün (1) denklem sisteminin genel bir çözümü olduğunu söylemek gelenekseldir. Serbest değişkenlere sıfır değerler atayarak temel değişkenlerin değerlerini belirliyor ve oluşturulan temel değişken kümesine karşılık gelen temel bir çözüm oluşturuyoruz.

• Yani (1) sisteminin temel çözümü.

• Aşağıda, eğer sistem (1)'in kabul edilebilir çözümleri varsa, o zaman (5) koşulu sağlanacak şekilde biçim (3)'e dönüştürülebileceği gösterilecektir.

• Bu nedenle (5) numaralı koşulun sağlandığını varsayacağız. O halde temel çözüm uygun bir temel çözümdür.

Eşitlikleri (4) kullanarak, f fonksiyonunu serbest değişkenler cinsinden ifade edebiliriz: (6) Şimdi, temel çözüme karşılık gelen f fonksiyonunun değerini hesaplayabiliriz.

• Simpleks yöntemi fikrini uygulayarak, uygulanabilir bir temel çözümden diğerine geçmeyi öğreneceğiz. Bunu yapmak için, temel değişkenlerden biri olan xi tabandan çıkarılır ve yerine bazı serbest değişken xj konur.

• Temeldeki bu değişiklikle denklem sistemi (4) ve doğrusal fonksiyon (6) dönüştürülür. Bunu yapmak için, sistem (3)'ün i'inci denkleminin şuna göre çözülmesi gerekir: xj.

• Ortaya çıkan denklem:

• (7)'deki ifadesini xj yerine sistem (4)'ün geri kalan denklemlerinde ve fonksiyon (6)'da yerine koyarsak, sistem (1)'e eşdeğer yeni bir sistem elde ederiz ve bu sistem yeni tabana göre çözülecektir.

xi tabanında serbest bir değişken xj ile değiştirildiğini gösteren aij katsayısına simpleks tablonun çözümleyici elemanı denir. Eşitlik (7)'den şu sonuç çıkar:

• Yeni temel çözümün kabul edilebilir (negatif olmayan) olması gerektiğinden,

• o zaman koşulun yerine getirilmesi gerekir, yani . Başka bir deyişle, j'inci sütundaki çözümleme elemanı aij'nin (xi serbest bir değişkendir) pozitif seçilmesi gerekmektedir. Eğer çözümleme elemanı aij aşağıdaki kurala göre seçilirse, açıklanan dönüşüme simpleks adını vereceğiz:

• 1. Öğe aij pozitif öğeler içeren j'inci sütundan seçim yapın.

• 2. Bu sütunda birden fazla pozitif eleman varsa, o zaman bk serbest terimlerinin akj>0 katsayılarına oranını hesaplayacağız.

• Tüm oranlardan en küçüğünü seçiyoruz. Bırak olsun :

• (8)

• Bu kesrin paydasını çözümleme elemanı olarak seçiyoruz. Bu oranların birkaçı minimum (eşit) ise bu paydalardan herhangi birini seçeceğiz.

Teorem. Doğrusal denklemler sisteminde (4) tüm serbest terimler negatif değilse, simpleks dönüşümü uygulandıktan sonra negatif olmayacaklardır.

• Kanıt. (4)'teki simpleks dönüşümünden sonra yeni serbest terimleri şu şekilde gösterelim:

• Daha sonra en

• Eğer akj>0 ise (8)'den şu sonuç çıkar:

• eğer akj

• akj =0 ise, o zaman

• Sonuçlar. Simpleks dönüşümü kullanarak, ZLP'nin kabul edilebilir bir temel çözümünden bu problemin kabul edilebilir başka bir temel çözümüne gidebilirsiniz.

Simpleks yöntemi, LP problemine çözüm olan bir köşenin (açı) bulunması ve test edilmesinden oluşur. Her aşamada yöntem, minimum (maksimum) hareketi sağlayan bir köşe ve ona karşılık gelen değişkenleri seçer. en yüksek hız. Seçilen değişken en kısıtlayıcı olan diğer değişkenin yerini alır. Simpleks yöntemi ayrıca bir çözümün mevcut olup olmadığını belirlemenize de olanak tanır. Simpleks yöntemini uygulayan algoritma şu şekilde yazılabilir:

Aşama 1. ODR'de, matristen çıkarılarak bulunan temel kabul edilebilir çözümlere (değişkenlere) karşılık gelen belirli bir tepe noktası belirlenir. T- doğrusal olarak bağımsız sütunlar ve matrisin diğer sütunlarına karşılık gelen tüm diğer değişkenlerin sıfıra eşitlenmesi.

Adım 2. Geriye kalan tüm olasılar arasından seçilmiş p - t temel olmayan değişkenlere karşılık gelen kenarlar, üzerinde hareket ederken amaç fonksiyonunda en hızlı azalmaya yol açan bir kenar (değişken).

Aşama 3. Sanki başlangıç ​​tepe noktasından seçilen kenar boyunca başka bir tepe noktasına doğru bir hareket gerçekleştiriliyormuş gibi, bu da yeni bir çözüm verir. düşük değer CF. Temel değişkenin (kenar) yeni bir temel değişkenle (kenar) değiştirilmesiyle yeni bir tepe noktası oluşturulur.

Vektörlerin sütunları ve elemanları genellikle aşağıda gösterilecek olan basit bir tablo biçiminde sıralanır ve yazılır.

Simpleks yöntemi DP problemini standart biçimde çözer.

x > 0 koşulları altında işlevi en aza indirin (maksimize edin); Balta = b.

Matris A gerçektir ve boyuta sahiptir T x "ve sıralama T.

Formüle edilen DP problemi şu şekilde de yazılabilir:

LP probleminin (8Л) formunda kaydedilmesine dayanarak, genişletilmiş matrisin şunu söyleyebiliriz:

boyutlar (t + 1) (n + 2)[x/]t çözümlerine karşılık gelir.

A matrisini bir sütun kümesi olarak temsil edelim

A matrisinin sıralaması olduğundan T, o zaman olacak T A matrisinin doğrusal olarak bağımsız sütunları, örneğin (a V1 ,...,a V/i Bir x° > 0 vektörü düşünün, öyle ki tümü p - t elemanlar 0 ve Ax° = b'dir. Bunlar sayıları olan elemanlar olsun..., ben n_m . Ayrıca A matrisinin doğrusal bağımsız sütunlarının aw konumunun 0 vektörlerindeki sıfır olmayan elemanların konumuna karşılık geldiğini varsayalım. Geometrik olarak, § 7.6'daki Açıklama 3'e göre bu, x°'nin ODR'nin tepe noktası (açı) olduğu ve ek olarak şu şartları karşıladığı anlamına gelir: verilen koşullar. Bu çözüme denir kabul edilebilir temel çözüm Kabul edilebilir setin açıları Kabul edilebilir temel çözümler.

Temel çözüm kümesinin DP probleminin optimal çözümü için gerekli tüm bilgileri içerdiğini hatırlayın. § 7.6'da ele alınan iki boyutlu durum için temel çözümlerin tümü 6 noktadır ve kabul edilebilir temel çözümler de noktalardır. L, V, Si 0.

Böylece, x°'ye benzer herhangi bir x vektörü şu şekilde yazılabilir:

Nerede x giriş- elemanları A matrisinin doğrusal olarak bağımsız sütunlarına karşılık gelen bir vektör; xF - sıfır elemanlı vektör.

Benzer şekilde vektörleri tanımlayalım

Bir vektörün elemanları olan değişkenler x inç, arandı temel değişkenler ve vektörün elemanları olan değişkenler x F arandı özgür (temel olmayan) değişkenler.

Çünkü x°F=0 ise, başlangıç ​​vektörü x° için amaç fonksiyonunun değeri şuna eşit olacaktır:

burada /°, /'nin x° noktasındaki değeridir.

x > 0 için [x°/°]t formunun çözümü (8.1) denir açık (açık) çözüm. Dolayısıyla temel olmayan değişkenleri sıfıra eşitlersek bariz bir çözüm elde ederiz.

Kolaylık sağlamak için yeniden düzenleyelim T A matrisinin doğrusal bağımsız sütunları Sol Taraf ve matrisi forma yazın

Burada B matrisi karşılık gelir T doğrusal bağımsız sütunlar boyutu var txt ve rütbe T, ve F matrisi

dır-dir inci (p - t) matris. B matrisi doğrusal olarak bağımsız sütunlardan oluştuğu için ters B -1 ve detB'ye sahiptir. φ 0. B matrisini oluşturmak için herhangi birini seçebileceğinizi unutmayın. T A matrisinin doğrusal bağımsız sütunları.

Verilen notasyonu dikkate alarak problemi (8.1) temsil edelim.

Bu gösterim genişletilmiş matrise karşılık gelir.

nereden geliyor

Eğer vektör x ise V Bx d = b sisteminin bir çözümü olacak, o zaman temel çözüm olacak. Eşitsizlik geçerliyse V= B -1 b > O ise x giriş kabul edilebilir bir çözüm olacaktır.

Böylece mevcut çözüm aşağıdaki denklemi karşılar:

Matris (8.4)'ü ele alalım. B matrisini birim matris I ile değiştirirsek temel değişkenler açık biçimde sunulacaktır. Soldaki matrisin (8.4) ilk satırını B~ 1 ile çarparsak, şunu elde ederiz:

burada B_1 b > O, yani T Sağ sütundaki üst öğeler negatif değildir ve değişkenlerin geçerli değerini temsil eder.

Sol tarafta üst çizgi Sonuç bir birim matristir: B -1 B = I. Bu sunumçok kullanışlı çünkü bir vektörle çarparken x giriş her değişken ayrı bir satırda olacaktır.

Dolayısıyla, kabul edilebilir olarak değerlendireceğimiz ve B tabanına karşılık gelen temel çözüm, x m = [0'da x]'tir; burada x'te == B_1 b. Temel çözüm şu varsayımdan kaynaklanır: x F = 0. Ancak eğer xF* 0 ise x^, x 5 = = B~"b - B^"Fx/r olarak hesaplanabilir. Bu ifadeyi amaç fonksiyonuna (maliyet fonksiyonu) koyarsak, şunu elde ederiz:

Maliyetin temel olmayan değişkenlere bağımlılığını belirlemek gerektiğinden, bunlardan biri daha sonra temel olanlara dahil edilir, o zaman Sonuç olarak matrisin altında I sıfır olmalı. Bunu yapmak için (8.7)'de (matrisin) ilk satırını şu şekilde çarpıyoruz: itibaren ve ikincisiyle ekleyin

ilk yüzyıl için amaç fonksiyonunun değeri nerede

(8.3)'ten simit x 0.

Matris (8.8) denir Simpleks tablo. Onu getirmek bu tür dır-dir İlk aşama simpleks algoritması. Algoritmanın yürütülmesi sırasında, tablonun sağ alt elemanı maksimum veya minimum oluncaya kadar bir tablodan diğerine geçiş yapılır.

Simpleks tablo kullanarak geçerli bir çözümü görmek kolaydır. Değişkenler X F sıfır alt matrisine, değişkenlere karşılık gelir x giriş- birim matris:

DP probleminin standart forma indirgendiğini, simpleks tablonun hesaplandığını ve çözüm çokyüzlüsünün tepe noktasına karşılık gelen başlangıç ​​temel çözümünün seçildiğini varsayalım.

Daha sonra - problemin çözümü (8.1). Bu yüzden

b > Oh gibi, bu kabul edilebilir temel bir çözümdür.

Matris (8.9)'u daha fazla temsil edelim uygun form, temel gösterimi koruyarak:

Maksimum ve minimizasyon problemlerini ayrı ayrı ele alalım.

Kanonik problemi çözmek için evrensel bir yöntem düşünelim doğrusal programlama

İle N değişkenler ve M Simpleks yöntemi olarak bilinen eşitlik kısıtlamaları.

Kanonik bir problemin plan kümesi, sonlu sayıda köşe noktasına sahip dışbükey çokyüzlü bir kümedir. Ve eğer bu problemin optimal bir çözümü varsa, o zaman bu çözüme en azından bir köşe noktasında ulaşılır.

Herhangi bir köşe noktası, değişkenlerin sıfıra eşit olduğu ve geri kalan değişkenlerin durum matrisinin doğrusal olarak bağımsız sütunlarına karşılık geldiği problemin temel planıyla ilişkilendirilir. Bu doğrusal olarak bağımsız sütunlar, tekil olmayan bir temel matris oluşturur.

Tüm köşe noktalarının yinelenmesi hesaplama açısından pahalıdır ve bu nedenle etkisizdir. 1947'de J. Danzig, köşe noktalarının numaralandırılması için düzenli bir prosedür önerdi; burada en uygun çözümü bulmak için yalnızca küçük bir kısmını incelemek yeterliydi. Bu prosedür denir simpleks yöntemi.

J. Danzig, bir uç noktadan diğerine hareket ederken temel matristeki yalnızca bir vektörün değiştirilmesini önerdi. Bu, böyle bir geçiş sırasında temel değişkenlerden birini hariç tutmamız - onu temel olmayan (sıfıra eşit) hale getirmemiz ve onun yerine temel olmayan (sıfır) arasından yeni bir değişken eklememiz - onu temel (pozitif) hale getirmemiz gerektiği anlamına gelir. ).

Geometrik olarak böyle bir değiştirmenin, bir köşe noktasından bitişik noktaya, önceki noktaya ortak bir kenarla bağlanan bir geçişe yol açtığı ortaya çıktı.

Komşu noktalardan amaç fonksiyonunun en fazla arttığı nokta seçilir. Köşe noktalarının sayısı sonlu olduğundan, sonlu sayıda geçiş yoluyla amaç fonksiyonunun en büyük değerine sahip tepe noktası bulunacak veya sınırsız sayıda plan üzerinde amaç fonksiyonunun sınırsızlığı kurulacaktır.

Simpleks yönteminin genel şeması aşağıdaki ana adımlardan oluşur.

· adım 0. Başlangıç ​​temelinin ve karşılık gelen başlangıç ​​köşe noktasının (taban çizgisi) belirlenmesi.

· Aşama 1. Mevcut temelin optimallik açısından kontrol edilmesi . Optimallik kriteri sağlanırsa, O plan optimaldir ve çözüm tamamlanmıştır. Aksi takdirde 2. adıma gidin.

· Adım 2. Temel olanlara eklenen değişkeni bulma. (Amaç fonksiyonunun arttırılması koşulundan).

· Aşama 3. Temel değişkenlerin dışında kalan bir değişkenin bulunması (Problemin kısıtlarının korunması şartıyla).

· adım 4 . Yeni taban çizgisinin (bitişik köşe noktası) koordinatlarını bulma. 1. adıma gidin.

Tekrarlanan 1-4 adımları, simpleks yönteminin bir yinelemesini oluşturur.

Bu şemadan, ilk olarak, simpleks yöntemini başlatmak için, bir tür köşe noktasına (bir başlangıç ​​temel planı) sahip olmanız gerektiği ve ikinci olarak, tüm bitişikleri hesaplamadan mevcut köşe noktasını optimallik açısından inceleyebilmeniz gerektiği anlaşılmaktadır. köşeler. Kanonik DP probleminin özel bir formu varsa, bu problemler kolaylıkla çözülebilir.

Tanım. Kanonik DP probleminin “tercih edilen bir forma” sahip olduğunu söyleyeceğiz.

1. Denklemlerin sağ tarafları, .

2. koşul matrisi boyutunda bir birim alt matris içerir

Yani herhangi bir denklemde katsayısı bire eşit olan, diğer denklemlerde bulunmayan bir değişken vardır. İlk koşul külfetli değildir, çünkü bazı denklemlerin sağ tarafının negatif olması durumunda bunu (-1) ile çarpmak yeterlidir. Tercihli türde bir problemde başlangıç ​​taban çizgisini bulmak çok basittir.

Örnek 2.1.

Durum Matrisi A ve kısıtlamaların sağ taraflarının vektörü B gibi görünmek

ve hedef vektör c = (1, -3, 0, 4, 2).

Bir temel matris hemen bellidir: koşulların birim vektörleriyle.

Bu nedenle temel değişken olarak seçilmesi X 1 , X 3 ,X 5 , ve denklem sistemini yerleştirmek X 2 =x 4 = 0 (temel olmayan değişkenler) , hemen buluruz X 1 = 10,X 3 = 20,X 5 = 8, yani ilk taban çizgisi X 0 = (10, 0, 20, 0, 8). Temel değişkenlerin değerlerinin kısıtların sağ taraflarına eşit olduğunu görüyoruz. Buradan sağ tarafların pozitif olması gerektiği açıktır. B Ben .

Gelecekte temel değişkenleri bir vektörde birleştireceğiz X B.

Böylece tercih edilen formun kanonik probleminde birim alt matrisi başlangıç ​​temel matrisi olarak alınır. A B = e ve karşılık gelen temel değişkenler kısıtlamaların sağ taraflarına eşittir:

X B = B.

Bu türden temel bir plan için test edilmesi yeterince basit olan bir optimallik kriteri formüle edilebilir. Miktarları tanıtalım

? J = < с B , A J > - c J , j = 1,...,n,(2.1)

Nerede İle B- temel değişkenler için amaç fonksiyonunun katsayılarının vektörü X B , A J -J- bu durum matrisi sütunu, C J -J- amaç fonksiyonunun katsayısı. Farklılıklar ? J simpleks farkları veya simpleks tahminleri denir.

Temel plan için optimallik kriteri. Birim bazlı matrise sahip bir temel plan için tüm simpleks tahminleri negatif değilse, bu plan optimaldir.

Temel planın optimalliğini kontrol etmek için bu kriteri uygulayalım X 0 = (10, 0, 20, 0, 8) örnek 2.1'den.

Bu bakımdan temel değişkenlerin vektörü X B =(X 1 , X 3 ,X 5 ), O İle B = (C 1 , C 3 ,C 5 ) = (1, 0, 2).

Buradan,

? 1 = < с B , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.

Değerlendirmeden bu yana ? 4 < 0, то базисный план X 0 optimal değil. Temel değişkenlere karşılık gelen simpleks tahminlerin her zaman sıfıra eşit olduğunu, dolayısıyla yalnızca temel olmayan tahminlerin kontrol edilmesinin yeterli olduğunu unutmayın.

2. Doğal temel değişkenlerin tanıtılması. Simpleks masanın yapımı. Sıfır planının tanımı.

Simpleks yöntemi. Simpleks yönteminin algoritması.

Simpleks yöntemi- çok boyutlu bir uzayda dışbükey bir çokyüzlünün köşelerini numaralandırarak doğrusal programlamanın optimizasyon problemini çözmeye yönelik bir algoritma. Yöntem 1947'de Amerikalı matematikçi George Danzig tarafından geliştirildi.

Simpleks yönteminin fikri, ortaya atılan tanımlayıcı problemin matematiksel forma çevrilmesidir. Sorunun matematiksel formülasyonu, istenen sonucu gösteren amaç fonksiyonunun denklemini içerir - amaç fonksiyonunun minimum veya maksimumunu belirler; eşitlikler veya eşitsizliklerle belirlenen doğrusal kısıtlama sistemleri. Kabul edilmiş matematiksel açıklama matris formuna yol açar. Daha sonra problemin matris tanımı şuna yol açar: kanonik form. Sistemden sonra doğrusal denklemler kanonik forma indirgendiğinde doğrusal programlama problemini çözmeye başlarız. Bu sorunu çözmek için kullanılan algoritma, bir dizi yapı matrisinden oluşur. Çözümün her adımı sizi istediğiniz sonuca ulaşmaya bir adım daha yaklaştırır.

İÇİNDE bilgi işlem devresi Simpleks yöntemi, başlangıçta kabul edilebilir bir köşe noktasından (genellikle orijin) başlayarak, kabul edilebilir bir uç noktadan diğerine ardışık geçişlerin, optimal çözüme karşılık gelen bir nokta bulunana kadar gerçekleştirildiği sıralı bir süreci uygular.

Simpleks yöntemi algoritması

1. Kısıtlama sistemini kanonik forma getiriyoruz (sistem sınırlı olduğunda). Ayrıca sistemde tek bir baz belirlenebilmektedir.

2. Orijinali bulun referans planı(KZLP denklem sisteminin negatif olmayan temel çözümleri). Referans planlarının her biri, belirli bir n vektör sisteminde bulunan m doğrusal bağımsız vektörden oluşan bir sistem tarafından belirlenir. A 1 , A 2 ,…, Bir. Üst sınır Belirli bir problemin içerdiği referans planlarının sayısı, kombinasyon sayısına göre belirlenir. nm ile);

3. İnşa ediyoruz tek taraflı masa (tek taraflı masa Simpleks yöntemini kullanarak çözerken (dejenere olmayan) bir doğrusal programlama probleminin kabul edilebilir temel çözümlerini numaralandırma aracı olarak hizmet eden bir matris. Kanonik forma indirgenmiş bir doğrusal programlama denklemleri sisteminin katsayıları matrisinden oluşur, sözde göre sıralı dönüşümü simpleks algoritması istenen sonucu elde etmek için sınırlı sayıda adıma (yineleme) izin verir - amaç fonksiyonunun uç değerini sağlayan bir plan).

4.B tek taraflı masa vektörleri olumsuzluk açısından kontrol ediyoruz, yani. değerlendirmeler Zj – Сj Satırda yazılanların ≤ 0 (minimum) olması gerekir, Zj – Cj ≥ 0(maksimum seviyeye kadar). Eğer tahminler optimallik koşullarını sağlıyorsa problem çözülmüştür.

5. Bazı vektörler için optimallik koşulları ihlal edilirse, aşağıdakilere karşılık gelen bir vektörün temele dahil edilmesi gerekir:

maksimum[θ 0 j (Zj – Сj)] ; min[θ 0 j (Zj – Сj)] ; θ 0 j = dk, Nerede x ben> 0

Vektör öğesi θ j hangisi karşılık gelir θ 0j izin verici denir; bulunduğu satır ve sütuna kılavuz denir; kılavuz satırındaki vektör tabandan ayrılır.

6. Yeni tabandaki tüm vektörler için genişleme katsayısını bulalım. Giordano Gauss yöntemini uygulayalım

En uygun referans planını kontrol edelim. Eğer tahmin optimallik koşullarını sağlıyorsa problem çözülür, değilse 5-7. adımlar gerçekleştirilir.

2. Doğal temel değişkenlerin tanıtılması. Simpleks masanın yapımı. Sıfır planının tanımı.

Simpleks yöntemi, karmaşık sorunların çözümünde en etkili yöntemdir ve ile başlayan yinelemeli (adım adım) bir süreci temsil eder. sıfır(referans) çözüm (tepe noktası) N boyutlu çokyüzlü). Sonraki aramada optimal seçenek Plan, amaç fonksiyonunun değeri maksimum (minimum) değere ulaşana kadar köşe noktaları (çok yüzlünün köşeleri) boyunca hareketi varsayar. Sınırlı hammadde kaynaklarına sahip bir ciro planlama problemi örneğini kullanarak simpleks yönteminin algoritmasını ele alalım.

Şirket satıyor Nürün gruplarına sahip M sınırlı maddi ve parasal kaynaklar B ben ≥0 (1 ≤ Ben≤m) . Herkesin kaynak maliyeti biliniyor Ben- bir matris şeklinde sunulan, her grubun bir birim malının üretim ve satış türü ( A ij) ve teşebbüsün bir birim malın satışından elde ettiği kâr J- amaç fonksiyonuna dahil edilen grup Z(X). Doğrusal programlama yöntemi sistem (1) - (2)'den farklı değildir:

Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)

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 (2)

a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,

X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0

Simpleks yöntemini kullanarak problemi çözme aşamaları şunları içerir:

1) Sıfır referans planının hazırlanması. Eşitsizlik sisteminin (2) bir denklem sistemi haline gelmesi sayesinde yeni negatif olmayan (temel) değişkenler sunuyoruz:

a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1

a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)

……………………………………..

a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,

Giriş değişkenlerini sütun vektörleri olarak alırsak, bunlar temsil eder Bekar (temel) vektörler. Temel değişkenlerin basit bir yapıya sahip olduğunu unutmayın. fiziksel anlam- Bu kalan belirli bir üretim planı için depodaki belirli kaynak, bu nedenle bu temele denir doğal. Sistem (3)'ü temel değişkenlere göre çözüyoruz:

X n+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n

X n+2 = b 2 - a 21 X 1 - a 22 X 2 -…a 2n X n (4)

………………………………………..

X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n

Amaç fonksiyonunu formda yeniden yazıyoruz

Z(X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -…-с n Х n) (5)

Gerekli ana değişkenlerin X 1 = X 2 = X 3 = ... = X n = 0 olduğunu varsayarsak, sıfır referans planı X = (0, 0, ...0, b 1, b 2, b 3) elde ederiz. ... b m), burada Z(X) = 0 (tüm kaynaklar stokta, hiçbir şey üretilmiyor). Planı simpleks bir tabloya giriyoruz.

Plan	Temel	C i /Cj	Anlam X ben	X 1	X 2	Xn	Xn+1	Xn+2	X n+ 3	Q dk.
	Xn+1		b 1	11	12	13				b 1/a 12
Xn+2		b2	21	22	23				b 2 / a 22
Xn+3		b3	31	32	33				b 3 / a 32
Z(X) = 0	-C1	- C2	- C3				Dizin. astar

2) Endeks çizgisinin negatif katsayılarından, önde gelen sütunu belirleyen ve bir sonraki yinelemede (adım) hangi değişkenin ana (serbest) temelden (aslında,) hareket edeceğini gösteren mutlak değerdeki en büyüğü seçiyoruz. satışları en fazla gelir getiren ürün grubu seçilir). Daha sonra hammadde rezervlerini b i karşılık gelen maliyet katsayılarına bölüyoruz, sonuçları bir tabloya giriyoruz ve minimum Q min değerini belirliyoruz (rezervleri seçilen ürün grubunun çıktısını en güçlü şekilde sınırlayan kaynak seçilir). Bu değer, ön çizgiyi ve Xi değişkenini seçer; Sonraki adım(yineleme) temelden ayrılacak ve özgürleşecektir.

3) Yeni plana geçiş, simpleks tablonun Jordan-Gauss yöntemi kullanılarak yeniden hesaplanması sonucunda gerçekleştirilir. Öncelikle tabandaki X j'yi baş sütundaki X i ile değiştiririz. Ön çizginin tüm elemanlarını çözümleme elemanına (RE) bölelim, bunun sonucunda RE'nin öncü çizgideki yeri 1 olacaktır. X i temel hale geldiğinden kalan katsayıları 0'a eşit olmalıdır. Bu planın yeni elemanları dikdörtgen kuralına göre bulunur.

KD=GD – (A*B)/KD (6)

Ortaya çıkan plan, indeks çizgisinin katsayıları kullanılarak değerlendirilir: eğer hepsi pozitifse, o zaman plan optimaldir; değilse, o zaman plan bir sonraki yineleme (adım) gerçekleştirilerek geliştirilebilir.

Örnek.Üretim sahası için ekipman alımına 20 bin ruble tahsis edildi. Ekipman 72 m2'yi aşmayan bir alana yerleştirilebilir. İki tip ekipman sipariş edebilirsiniz: 6 m2 üretim alanı gerektiren ve 6 bin adet sağlayan A tipi. vardiya başına ürünler (fiyat 5.000 ruble) ve B tipi, 12 m2 alan gerektirir ve 3 bin adet üretim (fiyat 2.000 ruble). Bunu sağlamak için en uygun ekipman satın alma planı nedir? maksimum performans komplo?

A ve B tipi satın alınan ekipmanın miktarını sırasıyla X 1 ve X 2 ile gösterelim.

Saha üretkenliği (amaç fonksiyonu): Z(X) =6Х 1 +3Х 2.

Ana sınırlamalar aşağıdakilerle ilgilidir:

nakit ile: 5Х 1 +2Х 2 ≤ 20,

üretim sahası alanıyla birlikte: 6Х 1 +12Х 2 ≤ 72.

Yeni temel değişkenleri tanıtıyoruz X 3 (kalan Para ekipman satın alındıktan sonra) ve X 4 (ekipman yerleştirildikten sonra kalan alan) ve kısıtlamaları bir denklem sistemi biçiminde yeniden yazın:

5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)

6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)

Bu durumda amaç fonksiyonu: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .

Referans (0.) planı yapıyoruz: X = (0, 0, 20, 72), yani. henüz hiçbir şey satın alınmadı (hiç para harcanmadı, alan boş). Simpleks tablo yapma

Plan	Temel	C i /Cj	Anlam X ben	X 1	X 2	X 3	X 4	Q dk.
	X 3							20/5=4
X 4							72/6=12
Z(X) = 0	- 6	- 3			Dizin çizgisi
	→X 1				0,4	0,2		4/0,4=10
X 4				9,6	-1,2		48/9,6=5
Z(X) = 6*4=24		-0,6	1,2		Dizin çizgisi
	X 1					0,25	-1/24	-
→X 2					-1/8	5/48	-
Z(X) =6*2+3*5=27			9/8	1/16	Dizin çizgisi

Açıkçası, en büyük indeks 6'ya sahip olduğundan, öndeki sütun X 1'e karşılık gelir. Q min = 4'ün minimum değerini (en şiddetli kaynak kısıtlaması), X 3'ün temel değişkenlerden türetildiğini gösteren bir ön satır tanımlayarak buluruz. ve 1 yerine X girilir. Ön çizginin elemanlarını 5'e bölerek yeniden hesaplıyoruz ve formül (6)'yı kullanarak ikinci ve indeks çizgilerinin elemanlarını belirliyoruz. 1. planın amaç fonksiyonu Z(X) = 6*4+3*0 = 24'e eşittir.

Bununla birlikte, X 2 sütunu için indeks satırının katsayılarından biri negatif -0,6 olarak kalır, bu nedenle bu plan optimal değildir ve onu geliştirmek için başka bir yineleme (adım) gerekir. 2. sütunu öncü olarak seçin ve Minimum değer Q min = 5 temel değişkeni X 4 ile öncü çizgiyi tanımlarız. Aynı dönüşümleri gerçekleştirerek tüm endeks katsayıları pozitif olduğundan optimal olacak 2. planı elde ediyoruz.

Elde edilen sonuçları analiz edelim. Şu tarihte: en uygun çözüm amaç fonksiyonunun maksimum değeri 27 bin ruble olup, her iki kaynak da temelden çıkarılır, dolayısıyla tamamen harcanır.

Şundan emin olalım: 5*2+2*5 = 20 bin ruble, 6*2+12*5=72 m2. Gerekli çözüm X = (2; 5;0;0)'dır. Bu her zaman gerçekleşmez.

10 Numaralı Ders

Konu: Yapay temelli problemler için simpleks yöntemi

Simpleks çözüm yöntemi, formül oluşturmayı mümkün kılan ek (temel) değişkenlerin eklenmesine dayanmaktadır. kimlik matrisi. Eğer problem kısıtları eşitsizlikler şeklinde sunulursa:

a i1 X 1 + a i2 X 2 +…a in X n ≥ b i (1)

veya denklemler:

a i1 X 1 + a i2 X 2 +…a, X n = b i (1*),

o zaman referans planının istenilen biçimde elde edilmesi mümkün değildir. Bu durumda eşitliklere (1*) uymak için, yapay temel e i ve yapay değişkenler doğrudan görevin içeriğiyle ilgili değildir ancak bir referans (başlangıç) planı oluşturmayı mümkün kılar:

a i1 X 1 + a i2 X 2 +…a in X n +Y i = b i (2)

Problemi maksimuma çözerken amaç fonksiyonu şu şekilde yazılacaktır:

Z(X) =∑C j X j +(-M)∑Y i (3),

en azından benzer bir sorunu çözerken:

Z(X)=∑C j X j +(M)∑Y i (3*),

burada M çok büyük bir pozitif sayıdır; yapay değişkenlerin kullanılmasının bir tür cezasıdır.

Eşitsizlikler (1) durumunda, başlangıçta eksi işaretiyle ek değişkenler X n + i'yi tanıtıyoruz. Matrisleri üniter olmayacak, bu nedenle sistem (1)'in her eşitsizliğine yapay değişkenler У i'yi dahil ediyoruz:

a i1 X 1 +a i2 X 2 +…a in X n –X n+i +Y i =b i (4)

Bu durumda amaç fonksiyonu Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i'dir (maksimumu bulmak için). Başvuru yapay temel verir simpleks yöntemi Daha fazla esneklik ve çok çeşitli görevlerde kullanılmasına olanak tanır.

Örnek . Bir birim ürünün üretim maliyetleri ve satışından elde edilen karlılık tabloda verilmişse, A ve B olmak üzere iki tür ürünün üretimi için maksimum ve minimum kar değerlerini belirleyin. Ana koşul, işletmedeki işçilerin tam istihdamıdır.

Matematiksel olarak üretim çıktı kısıtlamaları şu şekilde yazılacaktır: karma sistem:

1X 1 + 1X 2 ≤ 6,

2X1 + 1X2 =8.

Birinci eşitsizlik için temel değişken X 3'ü, ikinci denklem için ise yapay Y 1 değişkenini tanıtalım:

1X1 + 1X2 + X3 = 6,

2X 1 + 1X 2 +Y 1 =8.

Ortaya çıkan denklem sisteminden X 3 ve Y 1'i ifade edelim ve maksimumu belirlemek için amaç fonksiyonunu hayal edelim:

Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=

3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M

Referans planı için - X=(0,0,6,8). Simpleks bir tablo oluşturalım:

Plan	Temel	C i /Cj	Anlam X ben	X 1	X 2	X 3	Y 1	Q dk.
	X 3							6/1=6
Y 1	-M						8/2=4
Z(X) = -8M	-2M-3	-M-2			Dizin çizgisi
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		M+1,5	Dizin çizgisi
	→X 2						-1	-
X 1					-1		-
Z(X) =3*2+2*4=14				M+1	Dizin çizgisi

Kural olarak, referans planının iyileştirilmesi yapay Y 1 değişkeninin temelden çıkarılmasıyla başlar.İkinci yinelemede maksimum 14 gelirle optimal plan X = (2,4,0,0) elde edildi. bin. ovmak. ve indeks satırının katsayıları negatif değildir. Bu görevde optimal bir planla kaynakların tam olarak kullanıldığını doğrulamak kolaydır (2*1+4*1=6; 2*2+1*4=8).

Minimum karlılığı bulurken amaç fonksiyonunu farklı formüle ediyoruz (+MY 1 terim olarak girilir:

Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=

3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M

Referans planı aynı fakat simpleks tablodaki indeks satır katsayıları farklıdır. Öndeki sütun, daha önce olduğu gibi, X 1 için mutlak değerdeki en büyük pozitif katsayıya göre seçilir, öndeki satır ise Q min = 4'ün minimum değeriyle belirlenir. İlk yinelemede yapay değişken Y 1, şu formülden türetilir: temel.

Plan	Temel	C i /Cj	Anlam X ben	X 1	X 2	X 3	Y 1	Q dk.
	X 3							6/1=6
Y 1	M						8/2=4
Z(X) = 8M	2M-3	M-2			Dizin çizgisi
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		-M+1,5	Dizin çizgisi

X i endeks satırındaki katsayıların ortaya çıkan negatif değerleri, 1. planın optimalliğini gösterirken, minimum gelir 12 bin ruble.

Yalnızca A ürününün çıktısı ile sağlanır (B ürünü üretilmez), hammaddeler tam olarak kullanılmaz (kalan X 3 = 2t), ana koşul karşılanırken, işçiler üretimde tamamen istihdam edilir.

Ders No. 11

Konu: Kapalı taşıma sorunu

1. Kapalı devrenin matematiksel formülasyonu ulaşım sorunu. Gerekli bilinmeyen sayısının belirlenmesi.

2. Ulaştırma sorununu çözmek için bir plan belirleme aşamaları.