Simplex Metod Hedef özelliği. Doğrusal programlama. Simpleks Yöntemi

Bu yöntem, doğrusal bir programlama probleminin referans çözümlerinin hedeflenen etkileşiminin bir yöntemidir. Sonlu sayıda adımdan oluşur veya en uygun çözümü bulur veya optimum bir çözüm olmadığını belirlemek için.

Simplex yönteminin ana içeriği aşağıdaki gibidir:

1. Optimum referans çözeltisini bulma yöntemini belirtin.
2. Bir referans çözeltisinden diğerine geçiş yöntemini belirtin, üzerine hedef fonksiyonun değerinin optimal, yani Referans çözümünü iyileştirmenin bir yolunu belirtin.
3. Referans çözümlerinin kaba kuvvetinin optimum bir çözelti üzerinde durdurulmasını veya optimum bir çözeltinin yokluğuyla ilgili sonucu izlemeyi mümkün kılan kriterleri belirleyin.

Lineer Programlama Görevlerinin Simpleks Yöntemi Çözümünün Algoritması

Görevi çözmek için simpleks Yöntemi Aşağıdakileri yapmalısınız:

1. Görevi canonical olarak getir
2. "Tek Temel" ile ilk referans çözümünü bulun (referans çözümü yoksa, Kısıtlama sisteminin uyumsuzluğu nedeniyle görev çözülmez)
3. Referans çözeltisi temelinde vektörlerin genişlemelerinin tahminlerini hesaplayın ve simpleks yönteminin tablosunu doldurun
4. Optimum çözeltinin benzersizliğinin bir işareti yapılırsa, görev çözümü biter
5. Bir dizi optimal çözeltinin varlığının durumunun yapılması durumunda, o zaman tüm optimal çözümler basitçe bulunur.

Simplex yöntemiyle sorunu çözme örneği

Örnek 26.1.

Görevin simpleks yöntemini çözün:

Karar:

Kanonik formda bir görev veriyoruz.

Bunu yapmak için, birinci eşitsizlik sınırının sol kısmında, +1 katsayısına sahip ek bir X 6'yı tanıtıyoruz. Hedef fonksiyonda, X 6 değişkeni sıfır katsayıya (yani dahil değildir) girer.

Alıyoruz:

İlk referans çözümünü buluruz. Bunun için, ücretsiz (çözülmemiş) değişkenler sıfır x1 \u003d x2 \u003d x3 \u003d 0'a eşittir.

Teslim almak referans çözümü X1 \u003d (0.0,0,24,30,6) tek bir bazda B1 \u003d (A4, A5, A6).

Hesaplamak genişletme vektörlerini tahmin etme Formül tarafından referans çözümünün temelindeki koşullar:

Δ K \u003d C B X K - C K

• C B \u003d (Cı, C 2, ..., C M) - Temel değişkenlerle hedef fonksiyon katsayılarının vektörü
• X k \u003d (x 1k, x 2k, ..., x mk) - Karşılık gelen vektörün A referans çözümünün temelini oluşturma
• C K - Bir değişken x için hedef fonksiyon katsayısı.

Temeldeki dahil edilen vektörlerin tahminleri her zaman sıfıra eşittir. Referans çözümü, genişlemelerin katsayıları ve referans çözümünün referans çözümlerinin referans çözümlerinin vektörlerinin genişletilmelerini değerlendirme simplex Tablo:

Hesaplamaları değerlendirme rahatlığı için masanın üst üstü, hedef fonksiyon katsayıları kaydedilir. "B" ilk sütun, referans bazında bulunan vektörleri kaydeder. Bu vektörlerin kaydedilmesinin sırası, kısıtlamaların denklemlerinde bilinmeyen izin verilen sayılara karşılık gelir. "C B" tablosunun ikinci sütununda, hedef fonksiyon katsayıları aynı sırayla temel değişkenlerle kaydedilir. Temelde dahil olan tek vektörlerin değerlendirilmesinin "C B" sütununda hedef fonksiyon katsayılarının doğru konumu ile her zaman sıfıra eşittir.

Tablonun son satırında, "A 0" sütununda Δ K'teki, Hedef fonksiyonun Z (x 1) referans çözümü üzerindeki değerleri kaydedilir.

İlk referans çözümü, optimum değil, çünkü görevde maksimum tahminde δ 1 \u003d -2, δ 3 \u003d -9 için 1 ve 3 negatif.

Referans çözümünü geliştirme konusundaki teorem tarafından, maksimum bir görevde ise, en az bir vektörün olumsuz bir tahmini varsa, hedef fonksiyonun değerinin daha büyük olacağı yeni bir referans çözümü bulabilirsiniz.

İki vektörün tanıtımını, hedef fonksiyonun daha fazla artışlarına yol açacağını tanımlarız.

Hedef fonksiyonun artışı formüldür.

Formül tarafından birinci ve üçüncü sütunlar için θ 01 parametresinin değerlerini hesaplayın:

L \u003d 1'de L \u003d 1, θ 03 \u003d 3'te θ 01 \u003d 6 elde ediyoruz (Tablo 26.1).

İlk vektörün Δz 1 \u003d - 6 * (- 2) \u003d 12'ye ve üçüncü vektör ΔZ 3 \u003d - 3 * (- 9) \u003d 27'ye dayanarak hedef fonksiyonun artışını buluruz.

Sonuç olarak, optimal çözeltiye daha hızlı bir yaklaşım için, A6 tabanının ilk vektörü yerine temel çözelti bazında bir vektör A3'ü tanıtmak gerekir, çünkü θ 03 parametresi ilk satırda (l) elde edilir. \u003d 1).

Jordan'ın dönüştürülmesini X13 \u003d 2 elemanı ile üretiyoruz, ikinci referans çözeltisini X2 \u003d (0.0.3,21,42.0), B2 \u003d (A3, A4, A5) temeli olarak elde ediyoruz. (Tablo 26.2)

Bu çözüm optimal değildir, çünkü Vektör A2'nin negatif bir tahmini Δ2 \u003d - 6'ya sahip olduğundan, çözümü iyileştirmek için, Referans Çözümü bazında Vector A2'yi girmeniz gerekir.

Vektör çıktısının sayısını tabandan tanımlıyoruz. Bunu yapmak için, ikinci sütun için θ 02 parametresini hesaplayın, sonuç olarak 7'de 7'dir. Sonuç olarak, temelden, A4'ün temelinin temelinden itibaren ikinci vektörünü elde ediyoruz. Jordan'ın dönüştürülmesini X 22 \u003d 3 elemanı ile üretiyoruz, üçüncü referans çözeltisini x3 \u003d (0.7,10,0,0,63,0) B2 \u003d (A3, A2, A5) (Tablo 26.3) elde ediyoruz.

Bu çözüm, pozitif değerlendirmeye dahil olmayan tüm vektörler için, o zamandan beri tek optimal olandır.

Δ 1 \u003d 7/2, δ 4 \u003d 2, δ 6 \u003d 7/2.

Cevap: X \u003d (0.7.10,0,63) 'de Max Z (x) \u003d 201.

Ekonomik analizde doğrusal programlama yöntemi

Doğrusal Programlama Yöntemi Üretimde kullanılan kaynakla ilgili ciddi kısıtlamalar karşısında en iyi ekonomik kararı (sabit varlıklar, malzemeler, işçilik kaynakları) kanıtlamayı mümkün kılar. Bu yöntemin ekonomik analizde kullanımı, kuruluşun faaliyetlerinin planlanmasına bağlı olarak sorunları çözmemize izin verir. Bu yöntem, en uygun çıkış değerlerinin yanı sıra en iyisinin talimatlarını belirlemeye yardımcı olur. etkili Kullanım Üretim kaynaklarının organizasyonu mevcuttur.

Bu yöntemle, sözde aşırı görevler, aşırı değerleri bulmak, yani değişkenlerin maksimum ve minimum olanıdır.

Bu süre sistem çözme işlemine dayanmaktadır lineer denklemler Analiz edilen ekonomik fenomenlerin birbirine bağlandığı durumlarda, kesinlikle fonksiyonel bağımlılık. Doğrusal programlama yöntemi, belirli sınırlayıcı faktörlerin varlığında değişkenleri analiz etmek için kullanılır.

Doğrusal programlama yöntemini kullanarak sözde taşıma görevinin çözümü çok yaygındır. Bu görevin içeriği, araçların çalışma koşullarında mevcut kısıtlamaların koşullarında, taşıma kapasiteleri, işlerinin süresini, maksimumun sürdürülmesine ihtiyaç duyulduğunda, araçların çalışması ile ilgili maliyetleri en aza indirmektir. müşteri sayısı.

Dışında, bu method Bir program çizme görevini çözerken yaygın olarak kullanılır. Bu görev, bu kuruluşun personelinin işleyen zamanının, hem bu personelin hem üyelerine hem de kuruluşun müşterileri için en çok kabul edilebilir olacağını sağlamak.

Bu zorluk, mevcut personel üyesi sayısındaki kısıtlamalar bağlamında sunulan müşteri sayısını ve çalışma süresi fonu.

Böylece, doğrusal programlama yöntemi yerleştirme ve kullanım analizinde çok yaygındır farklı türler kaynakların yanı sıra kuruluşların planlanması ve öngörülmesi sürecinde.

Bununla birlikte, matematiksel programlama, bu ekonomik fenomenlerle ilgili olarak, Lineer'in ilişkisi ile ilgili olarak uygulanabilir. Bu amaçla doğrusal olmayan, dinamik ve dışbükey programlama yöntemleri kullanılabilir.

Doğrusal olmayan programlama, hedef fonksiyonun veya kısıtlamaların veya her ikisinin de doğrusal olmayan doğasına dayanır. Hedef fonksiyonun formları ve bu koşullar altında kısıtlamaların eşitsizlikleri farklı olabilir.

Doğrusal olmayan programlama, özellikle organizasyonun etkinliğini ve bu faaliyetin hacmini, üretim maliyetinin yapısı, piyasa koşulları ve diğerlerinin yapısı arasındaki ilişkiyi belirlerken, ekonomik analizde uygulanır.

Dinamik programlama, ahşap çözümleri bina dayanmaktadır. Bu ağacın her kademesi, önceki çözümün sonuçlarını belirlemek ve bu çözümün verimsiz seçeneklerini ortadan kaldırmak için bir aşama olarak hizmet vermektedir. Böylece, dinamik program Çok aşamalı, çok aşamalı bir karaktere sahiptir. Bu tür bir programlama, hem şu anda hem de gelecekte kuruluşun gelişimi için en uygun seçenekleri bulmak için ekonomik analizde uygulanır.

Dışbükey programlama, doğrusal olmayan bir programlama türüdür. Bu tür bir programlama, kuruluşun faaliyetleri ve maliyetlerinin sonuçları arasındaki bağımlılığın doğrusal olmayan bir yapısını ifade eder. Dışbükey (aksi halde içbükey) programlama analizleri dışbükey hedef fonksiyonları ve dışbükey kısıtlama sistemleri (puan İzin verilen değerler). Dışbükey programlama, maliyetleri en aza indirmek için ekonomik faaliyetlerin analizinde ve içbükeyleri en aza indirmek için uygulanır. Sonuç olarak, programlama türlerinin türleri altında, dışbükey hedef fonksiyonları en aza indirilir ve içbükey - en üst düzeye çıkarılır.

Kısa teori

Doğrusal programlama görevlerini çözmek için birçok farklı yöntem vardır. Bununla birlikte, aralarındaki en verimli ve evrensel, simpleks yöntemdi. Bazı görevleri çözerken diğer yöntemler daha verimli olabileceği belirtilmelidir. Örneğin, iki değişkenli ZLP optimal olduğunda ve potansiyel yöntem çözülürken. Simplex yöntemi, kanonik biçimde herhangi bir SAP için ana ve uygulanabilir.

Ana Doğrusal Programlama Teoremi ile bağlantılı olarak, bir sonraki yolun doğal olarak gerçekleşmesi fikri karar ZLP. Herhangi bir sayıda değişkenle. Polyhedron'un tüm aşırı noktalarını bulmak için (en fazla) (daha fazla) ve içindeki hedef işlevin değerlerini karşılaştırır. Böyle bir çözme şekli, nispeten az sayıda değişken ve kısıtlamada bile, pratik olarak imkansız, çünkü aşırı noktalar bulma işlemi, ilk görevi çözmede zorluklarla karşılaştırılabilir olduğundan, ayrıca, polihedron planlarının aşırı noktaları sayısının sayısı olabilir. çok büyük. Bu zorluklarla bağlantılı olarak, aşırı noktaların rasyonel entegrasyonu görevi ortaya çıkmıştır.

Simpleks yönteminin özü aşağıdaki gibidir. Bazı aşırı nokta biliniyorsa ve içindeki değer bir hedef fonksiyondur, daha sonra hedef fonksiyonun en kötü değeri aldığı tüm aşırı noktalar, mutlaka ihtiyaç duyulmaz. Dolayısıyla, doğal olarak, bu aşırı noktadan kenardan en iyi bitişik noktalara geçiş yapmanın bir yolunu bulma arzusu, bunu daha iyi (daha kötü değil), vb. Bunu yapmak için, bir tabela sahip olmak gerekir. Bu aşırı noktadan daha iyi nokta hiç değil. Bu, zll'yi çözmek için en yaygın kullanılan basitlik yönteminin (tutarlı iyileştirme planı yöntemi) genel bir fikridir. Bu nedenle, cebirsel terimlerle, simpleks yöntemi önermektedir:

1. İlk referans planını bulma yeteneği;
2. referans planının bir optimizasyon işareti varlığı;
3. referans dışı bir plana doğru hareket etme yeteneği.

Sorunu çözme örneği

Görev

Üç mal grubunun uygulanması için, ticari bir işletme, miktarda,, birimlerde üçlü sınırlı malzeme ve nakit kaynakları vardır. Aynı zamanda, 1 bin ruble başına 1 mal grubunun satışı için. Ciro, birim sayısındaki ilk türlerin kaynağı tarafından tüketilir, birim sayısındaki ikinci tipin kaynağı, birim sayısındaki üçüncü tür kaynağı. 1 bin ruble başına 2 ve 3 mal grupları için. Ciro, ilk türün kaynağına göre tüketilir, birimler, birimler, birimler, birimler, birimlerde, birimler, birimler, birimlerde üçüncü tip kaynaklar. 1 bin ruble başına üç mal grubunun satışından elde edilir. Emtia sırasıyla, bin ruble.

• Ticaret kuruluşunun karının maksimum olması için planlanan hacmi ve ciro yapısını belirleyin.
• Simpleks yöntemiyle çözülen ciroyu planlamanın doğrudan görevi, doğrusal programlamanın bir çift görevidir.
• Eşlenik çiftleri değişken ve çift görevleri takın.
• Bir karar almak için doğrudan görev çözeltisinden eşlenik çiftlerin eşlenik çiftlerine göre Çift görevMalların satışına harcanan kaynaklar üretir.

Oturuma kabul edişiniz, görev biriminin çözümüne bağlıdır ve zamanınız yok veya hesaplamalar için oturma arzusu yok - Site sitesini kullanın. Görev siparişi bir dakika meselesidir. Detaylar (bir uygulama, fiyatlar, son teslim tarihleri, ödeme yöntemleri), lineer programlama için görevlere çözümler satın almak için sayfada okunabilir ...

Sorunun çözümü

Bina modeli

Sırasıyla 1., 2. ve üçüncü tip malların cirosu sayesinde.

Sonra hedef fonksiyon ortaya çıkan karı ifade eder:

Malzeme ve parasal kaynaklar hakkındaki sınırlamalar:

Ek olarak, sorun anlamında

Aşağıdaki lineer programlama görevini alıyoruz:

Kanonik Tipi ZLP'ye Getirmek

Görevi kanonik formda veriyoruz. Eşitlikleri eşitlikte dönüştürmek için ek değişkenler sunuyoruz. Değişkenler katsayısı ile sınırlamalar halindedir. Hedef fonksiyonda, tüm ilave değişkenler sıfıra eşit bir katsayıya sahip ekler.

Kısıtlama, sağ parçanın olumsuzluğuyla, sol kısmın, bire eşit katsayılı ve kalan eşitlik kısıtlamaları ile birlikte, sıfıra eşit bir katsayılı olan bir değişkeye sahipse, sol kısmın bir değişkeni vardır. Bizim durumumuzda, 1., 2., 3. kısıtlamalar, ilgili taban değişkenleriyle tercih edilen bir forma sahiptir.

Çözüm semptomu

0th yinelemenin simpleks tablosunu doldurun.

Bp

Basit ilişkiler

8

6

4

0

0

0

0

520

16

18

9

1

0

0

65/2

0

140

7

7

2

0

1

0

20

0

810

9

2

1

0

0

1

90

0

-8

-6

-4

0

0

0

Görevi maksimum olarak çözdüğümüzden - sorunu maksimum bir şekilde çözerken, olumsuz sayıların endeks çizgisindeki varlığı, en uygun çözümü alamadığımızı ve 0. yinelemenin tablosundan bir sonrakine gitmeniz gerektiğini belirtir. .

Bir sonraki yineleme geçişi aşağıdaki gibidir:

Sunucu sütunu karşılık gelir.

Anahtar çizgi, ücretsiz üyelerin ve kurşun sütununun üyelerinin asgari oranında belirlenir (Simplex ilişkileri):

Anahtar sütununun kesişimi ve anahtar hattında, izin veren elemanı, yani.7.

Şimdi ilk yinelemenin hazırlanmasına devam edin. Tek bir vektör yerine vektöre girelim.

Çözünürlük öğesinin sitesindeki yeni masada, 1, anahtar kolonunun diğer tüm elemanlarını yazıyoruz. Anahtar çizgi elemanları bir çözünürlük öğesine ayrılır. Tablonun diğer tüm elemanları, dikdörtgenin kuralına göre hesaplanır.

1. Yineleme'nin bir tablosunu alıyoruz:

Bp

Basit ilişkiler

8

6

4

0

0

0

0

200

0

2

31/7

1

-16/7

0

1400/31

8

20

1

1

2/7

0

1/7

0

70

0

630

0

-7

-11/7

0

-9/7

1

-

160

0

2

-12/7

0

8/7

0

1. yineleme için anahtar sütun karşılık gelir.

Bunun için önemli bir dize buluruz:

Anahtar sütununun kesiştiği ve anahtar hattında, izin veren öğeyi buluruz, yani. 31/7.

Vektör tabandan görüntülenir ve vektörü girin.

2. Yineleme'nin bir tablosunu alıyoruz:

Bp

Basit ilişkiler

8

6

4

0

0

0

4

1400/31

0

14/31

1

7/31

-16/31

0

8

220/31

1

27/31

0

-2/31

9/31

0

0

21730/31

0

-195/31

0

11/31

-65/31

1

7360/31

0

86/31

0

12/31

8/31

0

Endeks hattında, tüm üyeler negatif değildir, bu nedenle doğrusal programlama probleminin aşağıdaki çözümü elde edilir (ücretsiz üye sütunundan yazarız):

Böylece, 7.1 bin ruble satmak gerekir. 1. tip ve 45.2 bin ruble ürünleri 3. görünümün malları. 2. satış türünün ürünü kârsızdır. Aynı zamanda, kar maksimum olacak ve 237.4 bin ruble olacak. Optimum planı uygularken, 3. görünümün kalıntısı 701 birim olacaktır.

Çift görev lp

İkili görevin modelini yazıyoruz.

İkili bir görev oluşturmak için aşağıdaki kuralları kullanmanız gerekir:

1) Doğrudan iş maksimum olarak çözülürse, daha sonra çift - en azından ve bunun tersi;

2) Maksimum eşitsizlik sınırındaki problemde, anlam ifade eder ≤ ve minimizasyon probleminde ≥;

3) Doğrudan bir problemin her bir kısıtlaması, çift problemin değişkenine karşılık gelir ve bunun tersi, çift problemin her bir kısıtlaması doğrudan bir görev değişkenine karşılık gelir;

4) İkili problemin kısıtlamaları sisteminin matrisi, başlangıçtaki problemin kısıtlama sisteminin matrisinden elde edilir;

5) Doğrudan problem kısıtlamaları sisteminin serbest üyeleri, çift görevin hedef fonksiyonunun karşılık gelen değişkenlerine sahip katsayılardır ve bunun tersidir;

6) Doğrudan görevin değişkeni olumsuzluk koşulu ile üst üste bindirilirse, çift problemin karşılık gelen kısıtlaması, eşitlik limiti olarak değilse, bir sınırlama-eşitsizlik olarak yazılır;

7) Doğrudan görevin herhangi bir kısıtlaması eşitlik olarak kaydedilirse, ikili sorunun ilgili değişkeni uygulanmaz.

Orijinal görevin matrisini dönüştürüyoruz:

Görevi kanonik formda veriyoruz. Ek değişkenler tanıtıyoruz. Hedef fonksiyonda, sıfıra eşit bir katsayı ile tanıttığımız tüm ek değişkenler. Ek değişkenler, tercih edilen türlere sahip olmayan ve eşit almayan sol kısıtlamaların sol parçalarına eklenecektir.

LP'nin ikili görevinin çözümü

Orijinal ve ikili görevin değişkenleri arasında uyum:

Simplex tablosuna göre, çift doğrusal programlama görevinin aşağıdaki çözeltisi elde edilir (alt satırdan boşalma):

Böylece, ilk türün kaynağı en açık olandır. Tahmini maksimum ve eşittir. Üçüncü form kaynağı, sıfıra eşit gereksiz çift puandır. İki grubun ek olarak satılan her mal birimi optimum karları azaltacaktır.
Doğrusal bir programlama problemini (ZLP) iki değişkenle çözmenin grafiksel yöntemi göz önünde bulundurulur. Örnekte, görev verildi detaylı Açıklama Çizme ve bir çözüm bulma bina.

Taşıma görevinin çözümü
Taşıma sorunu ayrıntılı olarak kabul edilir, matematiksel model ve çözüm yöntemleri - referans planını minimum eleman yöntemi ile bulma ve potansiyel yöntemleriyle en uygun çözümü araması.

Belirsizlikte Karar Verme
Wald Kriterleri, Savage, Gurvitsa, Laplas, Bayes yardımıyla belirsizlik koşullarında istatistiksel matris oyununun kararı kabul edilir. Görev örneğini kullanarak, bir ödeme matrisi ve risk matrisinin yapımı ayrıntılı olarak gösterilmiştir.

Sorun durumunda, ≥ bir işaretli sınırlamalar vardır, daha sonra -1'deki eşitsizliğin her iki bölümünü çarparak ΣA JI B J biçimine verilebilir. M ek değişkenleri x n + j ≥0 (j \u003d 1, m) tanıtıyoruz ve sınırlamaları denklemlerin türüne dönüştürüyoruz.

(2)

X 1, x 2, ..., x n görevinin tüm orijinal değişkenlerinin pastırma olmadığını varsayalım. Ardından ek değişkenler temel olacak ve kısıtlama sisteminin belirli bir çözümü formu vardır.

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

F0 \u003d 0 işlev fonksiyonunun değeri, f (x) aşağıdaki gibi gönderilebilir:

F (x) \u003d Σc i x i + f 0 \u003d 0 (4)

İlk Simpleks Tablo (Simplex Tablo. 1), denklemler (2) ve (4) temelinde derlenir. Ek değişkenler x n + j'den önce ise, (2) 'de olduğu gibi bir "+" işareti vardır, daha sonra X I ve serbest eleman b j J'sinden önceki tüm katsayılar, bir değişiklik olmadan Simplex tablosunda kaydedilir. En üst düzeye çıkarıldığında hedef fonksiyonun katsayıları, basitleştirilmiş tablonun alt çizgisine zıt işaretlerle girilir. Simplex tablosundaki ücretsiz üyeler, sorunun çözümünü belirler.

Problem çözme algoritması aşağıdaki gibidir:

1. adım. Ücretsiz üyelerin sütununun unsurlarını görüyoruz. Hepsi pozitifse, izin verilen temel çözüm bulunur ve optimum çözeltiye karşılık gelen algoritmanın 5. adımına gidin. İlk Simplex tablosunda negatif ücretsiz üyeler varsa, çözüm izin verilmez ve 2. adıma gidin.

2. adım. İzin verilen bir çözüm bulmak için, bağlantısız olmayan değişkenlerden hangisinin temelde etkinleştirileceğine ve tabandan nasıl çekileceğine karar vermek gerekir.

Tablo 1.

X N.

Temel değişkenler	Sınırlamalarda ücretsiz üyeler	Nebase değişkenleri
		x 1	x 2	...	x L.	...
x n + 1	b 1.	11.	a 12.	...	1L	...	1n.
x n + 2	b 2.	21.	22.	...	2L	...	2n.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + r	b2.	bir r1	bir r2.	...	bir rl	...	bir rn.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + m	b M.	bir m1.	bir m2.	...	bir ml.	...	bir mn.
F (x) maks	F 0.	-C1.	-C2.	...	-C1.	...	-C N.

Bunu yapmak için, bir serbest elemanın sütununun negatif elemanlarından herhangi birini seçin (b2 lideri olsun veya izin verilir. Negatif ücretsiz bir üyeye sahip bir arka arkaya negatif eleman yoksa, kısıtlamalar sistemi anlaşılmaz ve Görevin çözümü yok.

Aynı zamanda, değişken, işaretini seçilen NP X L'de bir artışla değiştiren ilk olan BP'den elimine edilir. R'nin durumundan belirlenen X N + R olacaktır.

şunlar. Seçilen kurşun sütununun elemanına serbest elemanın en küçük oranına karşılık gelen değişken. Bu ilişki denir simpleks tutum. Sadece pozitif simpleks ilişkiler düşünülmelidir.

X N + R değişkenine karşılık gelen dize denir Önde gelen veya izin verilmesi. Simplex tablosunun bir RL'nin elemanı, ana dizgenin kesişiminde duran ve ana sütun, önde gelen veya izin veren bir eleman denir. Ana öğe bulma, her bir sonraki Simplex tablosunda çalışır.

3. adım. Yeni Simpleks tablosu, elemanları bir önceki basamağın simpleks tablosunun elemanlarından yeniden hesaplanır ve bir inme ile işaretlenmiştir. b "j, bir" ji, c "i, f" 0. Elementlerin yeniden hesaplanması, aşağıdaki formüllere göre yapılır:

İlk olarak, yeni Simpleks tablosu, önceki Simplex tablosunda liderlik ettiği bir dize ve sütunla doldurulur. Ekspresyon (5), "Ustanın bölgesindeki bir" RL'nin, önceki Simplex tablosunun elemanının ters boyutuna eşit olduğu anlamına gelir. RI satırının elemanları kurşun elemana ve elemanlarına ayrılır. Bir JL sütunu ayrıca önde gelen bir elemana bölünür, ancak zıt işaret ile alınır. ELEMİK B "R ve C" L aynı prensip ile hesaplanır.

Kalan formüllerin kaydedilmesi kolaydır.

Dikdörtgen, eski simpleks tabloya göre, diyagonal formlarından birinin yeniden hesaplanması (JI) ve kurşun (bir RL) elemanlarını (Şekil 1) yapacak şekilde oluşturulmuştur. İkinci diyagonal benzersiz olarak tanımlanır. Yeni bir öğe "ji elementinden bir" ji bulmak için, kesilir ("-" hücrenin işareti burası bunun için belirtilmiştir) zıt köşegenlerin elemanlarının kurşun elemanına bölünür. Benzer şekilde, elementler b " J, (j ≠ r) ve c "i, (ben ≠ l).

4. adım. Yeni simpleks masanın bir analizi, algoritmanın 1. adımı ile başlar. Geçerli bir temel çözelti bulunana kadar eylem devam eder, yani. Serbest üyelerin kolonunun tüm unsurları pozitif olmalıdır.

5. Adım. İzin verilen temel çözümün bulunduğuna inanıyoruz. F (x) fonksiyonunun satır katsayılarını görüyoruz. Simplex tablosunun optimalliğinin bir işareti, F-LINE'teki bağlantısız olmayan değişkenlerle katsayıların olumsuzluğudur.

İncir. 1. Dikdörtgenin Kuralı

F-row katsayıları arasında negatif (ücretsiz üye hariç) varsa), daha sonra başka bir temel çözüme geçmeniz gerekir. Hedef fonksiyonu en üst düzeye çıkarırken, temel, sütunun, sütunun, simpleks masanın alt satırındaki maksimum mutlak katsayının maksimum mutlak değerine karşılık gelen, bağlayıcı olmayan değişkenlerin (örneğin X L) içerir. Bu, bu değişkeni, işlev fonksiyonundaki bir gelişmeye yol açan artış seçmenizi sağlar. X L değişkenine karşılık gelen bir sütun lider olarak adlandırılır. Aynı zamanda, X N + R değişkeni, R indisi, minimum basitlik oranı ile belirlenen olarak belirlenir:

X N + R'ye karşılık gelen dize, ana denir ve Simplex tablosunun bir RL'nin elemanı, ana dizgenin geçerken ve ana bilgisayar sütununda durur, Önde gelen element.

6. adım. 3. adımda belirtilen kurallara göre. Prosedür, optimum çözelti bulunana kadar devam eder veya mevcut olmadığı sonucuna varılmıştır.

Usta sütundaki çözümü optimize etme işleminde, tüm elemanlar pozitif değildir, sonra önde gelen satır seçilemez. Bu durumda, sorunun izin verilen çözümleri alanındaki fonksiyon, yukarıdaki ve F MAX -\u003e & ∞ ile sınırlı değildir.

Extremum aramanın bir sonraki adımında, temel değişkenlerden biri sıfır olursa, karşılık gelen temel çözeltinin dejenere denir. Bu durumda, sözde döngü, belirli bir frekansın, aynı BP kombinasyonunun tekrarlamaya başladığı gerçeği ile karakterize edilir (f fonksiyonunun işlevi korunur) ve yeni izin verilen bir temele gitmek imkansızdır. çözüm. Döngü, simpleks yönteminin ana eksikliklerinden biridir, ancak nispeten nadirdir. Uygulamada, bu gibi durumlarda, genellikle değişkeni, sütunun, fonksiyon fonksiyonundaki negatif katsayının maksimum mutlak değerine karşılık gelen ve yeni bir temel çözeltinin rastgele bir seçimini oluşturan temel olarak girmeyi reddederek.

Örnek 1. Görevi çözün

maks (F (x) \u003d -2x 1 + 5x2 | 2x 1 + x 2 ≤7; x 1 + 4x2 ≥8; x 2 ≤4; x 1.2 ≥0)

Simplex yöntemi ve çözelti işleminin geometrik yorumunu verir.

Sorunun çözeltisinin grafik yorumlanması, Şekil 2'de sunulmuştur. 2. Hedef fonksiyonun maksimum değeri, OTWP'nin üst kısmında koordinatlarla elde edilir. Simplex tabloları kullanarak görevi çözeceğiz. İkinci sınırı (-1) ile çarpacağım ve eşitsizliklerin denklem türüne yol açması için ek değişkenler tanıtıyoruz, sonra

X 1 ve x 2 ilk değişkenleri, kötüye kullanılmaz olarak alınır ve ek x 3, x 4 ve x 5, bazını göz önünde bulundurur ve basit bir tablo (Simplex Tablo. 2). Simplex tablosuna karşılık gelen çözüm. 2 İzin Verilmez; Tahrik elemanı, bir devre ile daire içine alınır ve daha önce verilen algoritmanın 2. aşamasına göre seçilir. Sonraki Simplex Tablo. 3 İzin verilen bir temel çözümü tanımlar, Şekil l'deki OCP'nin tepesine karşılık gelir. 2 Önde gelen eleman, bir devre ile daire içine alınır ve problem çözme algoritmasının 5. basamağına göre seçilir. Masa. 4, sorunun optimum çözeltisine karşılık gelir, bu nedenle: x 1 \u003d x 5 \u003d 0; x 2 \u003d 4; x 3 \u003d 3; x 4 \u003d 8; F max \u003d 20.

İncir. 2. Grafik Çözüm Sorunu

Sevdim? Yer imlerine ekle

Görevlerin Çözümü Simpleks Yöntem: Online Örnekler

Görev 1. Şirket, iki boyuttaki banyolar için raflar üretir - A ve V. Satış ajanları, piyasada bir hafta kadar 550 rafın uygulanabileceğine inanmaktadır. Tip A, malzemeden 2 m2'lik bir raf için gereklidir ve malzemenin B - 3 m2 raf tipi içindir. Şirket haftada 1200 m2'ye kadar malzeme alabilir. Bir raf tipinin üretimi için A, 12 dakikalık makine süresi gereklidir ve bir raf tipi B - 30 dak; Makine haftada 160 saat kullanılabilir. Tip bir rafın satışından elde edilen kar 3 parasal birimdir ve B - 4 den tipi satırından. un., her türün kaç rafı haftada serbest bırakılmalıdır?

Görev 2. Doğrusal Programlama Simplex-Metod'un görevini çözün.

Görev 3. Şirket 3 çeşit ürün üretir: A1, A2, A3, iki tür ham maddeleri kullanarak. Üretim birimi başına her türün hammaddelerinin maliyeti, planlanan süre için hammadde rezervleri, ayrıca her türün ürün biriminden elde edilen karlar.

1. Her türün kaç ürününün maksimum kar elde etmek için üretilmesi gerekir?
2. Her bir hammadde tipinin durumunu ve özel değerini belirleyin.
3. Optimal planın yapısının, yani, yani, yani, her bir hammadde türünün rezervlerinde maksimum değişiklik aralığını belirleyin. Sürümün isimlendirilmesi değişmez.
4. Üretilen ürünlerin miktarını belirleyin ve kıtlık türlerinden birinin rezervinde (serbest bırakılmasının bu adlandırma nomitesi dahilinde) bir artışla ilgili ürün miktarını belirleyin.
5. Elde edilen en uygun planın değişmeyeceği her türün ürün biriminden elde edilen karların aralıklarını belirleyin.

Görev 4. Lineer programlama görevini basit bir yöntemle çözün:

Görev 5. Doğrusal programlama Simplex-yönteminin görevini çözün:

Görev 6. İlk referans planı olarak kabul edilen basitleştirici yönteminin görevini çözün, durumda verilen plan:

Görev 7. Değiştirilmiş bir simpleks yöntemin görevini çözün.
A ve B iki tür ürünün üretimi için üç tür teknolojik ekipman kullanılmaktadır. Bir ürünün bir biriminin üretimi için, birinci tipin ekipmanı A1 \u003d 4 saat, ikinci tip A2 \u003d 8 saatin ekipmanı ve üçüncü tip A3 \u003d 9 saatin ekipmanını kullanır. Bir ürün biriminin üretimi için, birinci tipte kullanılan ekipmanın üretimi için B1 \u003d 7 saat, ikinci tip B2 \u003d 3 saatin ekipmanı ve üçüncü tip B3 \u003d 5 saatin ekipmanı.
Bu ürünlerin üretimi için, birinci tipin ekipmanı, T1 \u003d 49 saatten fazla çalışabilir, ikinci tipin ekipmanı T2 \u003d 51 saatten fazla değildir, üçüncü tipin ekipmanı T3'den başka bir şey değildir \u003d 45 saat.
Bitmiş bir ürünün satışından elde edilen kar, A alfa \u003d 6 ruble ve B - Betta ürünleri \u003d 5 ruble.
A ve B ürünlerinin üretimi için bir plan yapın, uygulamalarından maksimum kar sağlar.

Görev 8. Çift Simplex yöntemine en uygun çözümü bulun

Simplex probleminin sorununu çözme örneği ve ayrıca bir çift görevi çözme örneği.

Görev

Üç mal grubunun uygulanması için, ticari bir işletme, B1 \u003d 240, B2 \u003d 200, B3 \u003d 160 ünite miktarında üç sınırlı malzeme ve para kaynağı türüne sahiptir. Aynı zamanda, 1 bin ruble başına 1 mal grubunun satışı için. Ciro, ilk türlerin kaynağı, bir 11 \u003d 2 birimin miktarında, ikinci tipin kaynağı, bir 21 \u003d 4 ünite miktarında, üçüncü formun kaynağını 31 \u003d 4 tutarında kaynak olarak tüketilir. birimler. 1 bin ruble başına 2 ve 3 mal grupları için. Ciro, birinci tipin kaynağına göre, A 12 \u003d 3, A 13 \u003d 6 birim, ikinci tipin kaynağı, 22 \u003d 2, A 23 \u003d 4 birim miktarında kaynağı, kaynağı 32 \u003d 6, 33 \u003d 8 birim miktarındaki üçüncü form. 1 bin ruble başına üç mal grubunun satışından elde edilir. Ciro C1 \u003d 4, C2 \u003d 5, C3 \u003d 4, sırasıyla (bin ruble). Ticaret kuruluşunun karının maksimum olması için planlanan hacmi ve ciro yapısını belirleyin.

Ciro planlama doğrudan görevine, Çözülen Simpleks Yöntemi, çizin Çift görev Doğrusal programlama.
Ayarlamak değişkenlerin eşlenik çiftleri Doğrudan ve İkili Görev.
Konjugatın değişken çiftlerine göre, almak için doğrudan bir görevi çözmekten İkili görevin çözümüiçinde üretilir derecelendirme kaynaklarımal satışına harcandı.

Simplex yönteminin sorununun çözümü

X 1, x 2, x 3, bin ruble cinsinden satılan mal sayısıdır., Sırasıyla 1, 2, 3 - buna gruplar. O zaman sorunun matematiksel modeli:

F \u003d 4 · x 1 + 5 · x 2 + 4 · x 3 -\u003e Maks

0))) (~) "Title \u003d" (! Lang: Delim (LBACE) (matris (4) (1) ((2x_1 + 3x_2 + 6x_3 \u003d 0)))) (~)">!}

Simplex yöntemini çözüyoruz.

Eşitsizliklerin eşitliğe dönüştürülmesi için X 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, ek değişkenleri tanıtıyoruz.

Temel olarak, x 4 \u003d 240 alın; x 5 \u003d 200; x 6 \u003d 160.

Veriler B'ye girdik. simplex Tablo

Simplex Tablo No. 1

Hedef özelliği:

0 · 240 + 0 · 200 + 0 · 160 \u003d 0

Formül tarafından değerlendirmeleri hesaplayın:

Δ 1 \u003d 0 · 2 + 0 · 4 + 0 · 4 - 4 \u003d - 4
Δ 2 \u003d 0 · 3 + 0 · 2 + 0 · 6 - 5 \u003d - 5
Δ 3 \u003d 0 · 6 + 0 · 4 + 0 · 8 - 4 \u003d - 4
Δ 4 \u003d 0 · 1 + 0 · 0 + 0 · 0 - 0 \u003d 0
Δ 5 \u003d 0 · 0 + 0 · 1 + 0 · 0 - 0 \u003d 0
Δ 6 \u003d 0 · 0 + 0 · 0 + 0 · 1 - 0 \u003d 0

Olumsuz tahminler olduğundan, plan optimal değildir. En küçük puan:

X 2 değişkenini temel almak için giriyoruz.

Temelden gelen değişkeni belirler. Bunu yapmak için, x 2 sütun için en küçük olumsuz ilişkiyi buluruz.

= 26.667

En küçüğü, ilgili değildir: q3 \u003d 26.667. X 6 değişkenini temel almak

3. satır 6'da DELIM.
1. satırdan, 3. çizgiyi 3 ile çarpılarak çıkardık.
2. hatlardan, 3 çizgisini 2 ile çarpılarak çıkardık.

Hesaplamak:

Teslim almak yeni masa:

Simplex Tablo No. 2

Hedef özelliği:

0 · 160 + 0 · 440/3 + 5 · 80/3 \u003d 400/3

Formül tarafından değerlendirmeleri hesaplayın:

Δ 1 \u003d 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 \u003d - 2/3
Δ 2 \u003d 0 · 0 + 0 · 0 + 5 · 1 - 5 \u003d 0
Δ 3 \u003d 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 \u003d 8/3
Δ 4 \u003d 0 · 1 + 0 · 0 + 5 · 0 - 0 \u003d 0
Δ 5 \u003d 0 · 0 + 0 · 1 + 5 · 0 - 0 \u003d 0
Δ 6 \u003d 0 · (-1) / 2 + 0 · (-1) / 3 + 5 · 1/6 - 0 \u003d 5/6

Negatif bir tahmin olduğundan, 1 \u003d - 2/3, plan optimal değildir.

X 1 değişkenini temel alıyoruz.

Temelden gelen değişkeni belirler. Bunu yapmak için, x 1 sütun için en küçük olumsuz ilişkiyi buluruz.

En küçüğü nazik değildir: Q3 \u003d 40. X 2 değişkenini temelden alın

2/3'te 3. Line Delim.
2. satırlardan, 8/3 ile çarpılan 3. satırı çıkardık

Hesaplamak:

Yeni bir masa alıyoruz:

Simplex Tablo No. 3

Hedef özelliği:

0 · 160 + 0 · 40 + 4 · 40 \u003d 160

Formül tarafından değerlendirmeleri hesaplayın:

Δ 1 \u003d 0 · 0 + 0 · 0 + 4 · 1 - 4 \u003d 0
Δ 2 \u003d 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 \u003d 1
Δ 3 \u003d 0 · 2 + 0 · (-4) + 4 · 2 - 4 \u003d 4
Δ 4 \u003d 0 · 1 + 0 · 0 + 4 · 0 - 0 \u003d 0
Δ 5 \u003d 0 · 0 + 0 · 1 + 4 · 0 - 0 \u003d 0
Δ 6 \u003d 0 · (-1) / 2 + 0 · (-1) + 4 · 1/4 - 0 \u003d 1

Olumsuz tahmin olmadığından, plan optimaldir.

Sorunun çözümü:

Cevap

x 1 \u003d 40; x 2 \u003d 0; x 3 \u003d 0; x 4 \u003d 160; x 5 \u003d 40; x 6 \u003d 0; F max \u003d 160

Yani, ilk türün ürününü 40 bin ruble miktarına uygulamak gerekir. 2. ve 3. türlerin ürünü uygulanmaz. Aynı zamanda, maksimum kar, f max \u003d 160 bin ruble olacaktır.

İkili görevin çözümü

İkili görev:

Z \u003d 240 · y 1 + 200 · y2 + 160 · y3 -\u003e min

Title \u003d "(! Lang: DELIM (LBACE) (Matris (4) (1) ((2y_1 + 4Y_2 + 4Y_3\u003e \u003d 4) (3Y_1 + 2Y_2 + 6Y_3\u003e \u003d 5) (6Y_1 + 4Y_2 + 8Y_3\u003e \u003d 4) (Y_1, Y_2, Y_3\u003e \u003d 0))))) (~)">!}

Ek değişkenleri y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0'a giriyoruz, böylece eşitsizlik eşitliğe dönüştürülür.

Doğrudan ve çift görevlerin eşlenik çiftleri:

Son Simpleks Tablo No. 3 Doğrudan Görevlerden, İkili Görevin Çözümünü Buluyoruz:

Z min \u003d f max \u003d 160;
Y 1 \u003d δ 4 \u003d 0; Y2 \u003d δ 5 \u003d 0; y3 \u003d δ 6 \u003d 1; y 4 \u003d δ 1 \u003d 0; y 5 \u003d δ 2 \u003d 1; y 6 \u003d δ 3 \u003d 4;