Simplex yöntemi, bir çözümün basit bir örneğidir. Doğrusal programlama problemini simpleks yöntemiyle çözün

Doğrusal programlama problemlerini çözmek için grafiksel yöntemi zaten çözdüyseniz, devam etmenin zamanı geldi. tek yönlü yöntem... İlkinden farklı olarak, görev üzerinde pratikte hiçbir kısıtlaması yoktur (herhangi bir sayıda değişken, farklı işaretler vb.) ve problemin tipine bağlı olarak değiştirilir (örneğin, M-yöntemi veya yapay temelli yöntem).

Simpleks yöntemini kullanarak bir problem çözerken, hesaplamalar genellikle (kompaktlık ve netlik için) tablolarda (tablolar simpleks yöntemi) yapılır ve optimal çözüme sahip son tablo önemli ek bilgiler içerir: ikili problemin çözümü, kaynak dengeleri , kıt kaynaklarla ilgili bilgiler, vb. , bu bize bir doğrusal programlama probleminin ekonomik analizini yapmamızı sağlar (aşağıdaki örnek 3'e bakınız).

Simpleks yöntemiyle problem çözme örnekleri size kolaylık sağlamak için ücretsiz olarak düzenlenmiştir - çalışın, benzerlerini arayın, çözün. Bu tür görevlerle ilgili yardıma ihtiyacınız varsa, şu adrese gidin: Özel Doğrusal Programlama Çözümü.

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

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

Matematiksel bir modelin derlenmesi ve LPP'nin simpleks yöntemiyle çözümü (pdf, 33 Kb)

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

Yapay temelli tek yönlü çözüm (pdf, 45 Kb)

Amaç 3.İşletme iki çeşit hammadde kullanarak A1, A2, A3 olmak üzere 3 çeşit ürün üretmektedir. Her türden üretim birimi başına hammadde maliyetleri, planlanan dönem için hammadde stokları ve her türden bir üretim biriminden elde edilen kâr bilinmektedir.

1. Maksimum karı elde etmek için her türden kaç ürün üretilmesi gerekir?
2. Her bir hammadde türünün durumunu ve özel değerini belirleyin.
3. Optimal planın yapısının, yani. konunun isimlendirilmesi değişmeyecektir.
4. Kıt hammadde türlerinden birinin stokunda mümkün olan maksimum (verilen üretim terminolojisi sınırları dahilinde) bir artışla ürün sayısını ve serbest bırakmadan elde edilen karı belirleyin.
5. Elde edilen optimal planın değişmeyeceği her türden bir üretim biriminden elde edilen kârdaki değişim aralıklarını belirleyin.

Doğrusal programlama probleminin çözümü ekonomik analiz(pdf, 163 Kb)

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

Temel arama ile tablo tek yönlü yöntemiyle çözme (pdf, 44 Kb)

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

Tabular simpleks yöntemiyle çözme (pdf, 47 Kb)

Görev 6. Koşulda verilen planı ilk referans planı olarak kabul ederek problemi simpleks yöntemini kullanarak çözün:

Manuel tek yönlü çözüm (pdf, 60 Kb)

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

Değiştirilmiş simpleks yöntemiyle çözüm (pdf, 67 Kb)

Görev 8. Bulmak en uygun çözüm ikili simpleks yöntemi

Dual simpleks yöntemiyle çözüm (pdf, 43 Kb)

Doğrusal programlama problemlerini çözme örnekleri

Doğrusal programlama problemini çözme yöntemleri

Doğrusal programlama sorunu için destek çözümleri

Kanonik gösterimde bir doğrusal programlama problemi verilsin.

koşullar altında

(2) - (3) sistemine çözüm kümesi ile göstereceğiz. Diyelim ki matrisin rankı sistem (2)'deki denklem sayısı olsun.

Matrisin sütun vektörleri sisteminden, doğrusal olarak bağımsız bir vektör alt sistemi seçiyoruz. Vardır çünkü. Bu sistemin temelini oluşturur. ile gösterelim. Hadi arayalım temel değerler seti indeks, - temel alt matris matrisler. Vektörün koordinatları çağrılır temel , eğer ve temel olmayan aksi takdirde.

Sistem (2) şeklinde yazalım. Sol taraftaki terimleri temel ve temel olmayan olarak ayırdık, yani

Bu sistemin belirli bir çözümünü aşağıdaki gibi tanımlayalım. (4)'teki tüm temel olmayan değişkenleri sıfıra eşitliyoruz. Daha sonra sistem (4) şeklini alır

(5) arayalım temel alt sistem denklem sistemi (2). Vektörün temel koordinatlarından oluşan vektör ile gösterelim. Daha sonra sistem (2) vektör matrisi biçiminde yeniden yazılabilir.

Alt matris temel olduğundan,

dejenere olmayan. Bu nedenle, sistem (6), tek karar... Bu şekilde elde edilen sistem (2)'nin özel çözümüne denir. referans kararı temele karşılık gelen doğrudan doğrusal programlama problemi. (Bazen referans çözümü de denir temel ). Gördüğünüz gibi, temel, tek destek çözümüne karşılık gelir. Açıkçası, destek çözümlerinin sayısı sınırlıdır.

Bu temel için, ikili doğrusal programlama probleminin destek çözümünü de tanımlıyoruz. Kanonik olana ikili sorunun şu şekilde olduğunu hatırlayın:

koşullar altında

Sistem (8) şeklinde yazıyoruz

Sistem (8) için çözüm kümesinin ile gösterildiğini hatırlayın.

(9) sistemindeki temel kısıtların yerine getirilmesi koşulundan ikili değişkenlerin vektörünü eşitlikler olarak tanımlayalım. Aşağıdaki sistemi alıyoruz lineer denklemler:

ba-'dan oluşan bir vektör ile gösteririz.

vektör koordinatları. Daha sonra sistem (10) vektör-matris formunda yeniden yazılabilir.

Sistem (11) de benzersiz bir çözüme sahiptir.

diyelim destekleyici (temel )karar temeline karşılık gelen ikili doğrusal programlama probleminin Bu referans çözümü de benzersiz bir şekilde belirlenir.

Dolayısıyla, herhangi bir taban iki vektöre karşılık gelir - sırasıyla iki destek çözümü ve doğrudan ve ikili doğrusal programlama problemleri.

Aşağıdaki taban ve destek çözümlerini daha fazla tanımlayalım. Destek çözümünün tüm koordinatları negatif değilse, bu destek çözümünün karşılık geldiği temel denir. kabul edilebilir temel doğrudan doğrusal programlama problemi ve aynı temele karşılık gelen destek çözümü denir. sözde plan ikili görev Aslında bazın kabul edilebilirliği için temel koordinatların negatif olmaması yeterlidir. Temel planın, doğrudan doğrusal programlama probleminin () kabul edilebilir bir vektörü olduğuna dikkat edin.

Destek çözümü ikili problemin tüm kısıtlamalarını (9) karşılıyorsa, bu destek çözümünün karşılık geldiği temel denir. ikili olarak kabul edilebilir ... Bu durumda vektöre denir. temel ikili doğrusal programlama problemi ve aynı temele karşılık gelen destek çözümü

isminde sözde plan doğrudan görev.

Bir tabanın ikili kabul edilebilirliği için sadece temel olmayan eşitsizliklerin sağlanması yeterlidir. Taban çizgisinin ikili doğrusal programlama probleminin () kabul edilebilir bir vektörü olduğuna dikkat edin.

Eşitsizliklerin (9) sol ve sağ tarafları arasındaki farklar, ile gösterilecektir. Daha sonra, temelin ikili kabul edilebilirliği, tümünün olumsuzluğu kontrol edilerek kurulabilir. Doğrudan tanımdan aşağıdaki gibi, tüm temel artıkların sıfıra () eşit olduğuna dikkat edin.

Simpleks yöntemiyle doğrudan ve ikili problemlerin çözümüne bir örnek

Bu nedenle, eşitsizliklerin herkes için geçerli olduğundan emin olmak yeterlidir.

Teorem 1.İzin vermekve- bazı temellere karşılık gelen doğrusal programlama probleminin destek çözümleri, sonra eşitlik .

Kanıt . Destek çözümlerinin tanımlarından eşitlikleri elde etmek kolaydır.

teoremin geçerliliği buradan gelir.

Teorem 2. (Destek çözümlerinin optimallik kriteri) eğer temeleşzamanlı olarak kabul edilebilir ve ikili olarak kabul edilebilir ise, ilgili destek çözümlerivesırasıyla doğrudan ve ikili doğrusal programlama problemlerinin çözümleridir.

Kanıt. Bu ifadenin geçerliliği, doğrusal programlamadaki dualite teorisinden ve Teorem 1'den kaynaklanmaktadır.

Teorem 3.(1) - (3) problemine uygun bir çözüm, problemin temel planıdır, ancak ve ancak bu bir dışbükey çokyüzlü kümenin tepe noktasıysa.

Kanıt. İzin vermek - problemin temel planı (1) - (3). Bunu kanıtlayalım - setin üst kısmı . Tanım olarak, bir temel plan – bazı temellere karşılık gelen kabul edilebilir destek çözümü, yani – değişkenlerde lineer denklem sisteminin çözümü

Bu sistemin tek bir çözümü olduğunu görmek kolaydır. Bu nedenle, noktayı içeren yüzün yatak düzlemi , 0 boyutuna sahiptir. Sonuç olarak, - setin üst kısmı .

Geri. İzin vermek - setin üstü. Bunu kanıtlayalım - problemin temel planı (1) - (3). Köşe olduğu için, boyutu sıfıra eşit olan bir kümenin yüzüdür. Bu nedenle, vektör sayı kümesini belirttiğimiz en az sıfır bileşen var . Böylece, – sistemin tek çözümü

nerede . Bu nedenle, vektörler sisteminin doğrusal olarak bağımsız olduğunu kanıtlamak için kalır. Tam tersini varsayalım. O zaman hepsi sıfıra eşit olmayan sayılar vardır, öyle ki. Öyleyse

Bu, sistemin (12) farklı bir çözüme sahip olduğu anlamına gelir. , çözümünün benzersizliğiyle çelişir. Böylece, bir tabandır ve vektör - problemin ilgili temel planı (1) - (3). Hangisi gerekliydi.

(7), (8) numaralı problemin (problemin (1) - (3) ikilisi) kabul edilebilir bir çözümünün, ancak ve ancak kabul edilebilir bir kümenin tepe noktası olması durumunda bir destek planı olduğuna dikkat edin.

Yayın tarihi: 2015-01-10; Okuyun: 695 | Sayfa telif hakkı ihlali

Studopedia.org - Studopedia.Org - 2014-2018. (0,005 s) ...

Kesinlik için, minimumu bulma probleminin çözüldüğünü varsayıyoruz.

1. Doğrusal programlama problemini kanonik forma indirgeyin.

Ek değişkenleri girdikten sonra, denklem sistemini ve doğrusal fonksiyonu, genişletilmiş sistem olarak adlandırılan formda yazıyoruz:

Tüm ek değişkenlerin serbest üyelerle aynı işarete sahip olduğunu varsayıyoruz; aksi takdirde, sözde kullanırız m- aşağıda tartışılacak olan bir yöntem.

2. Temel ve serbest değişkenleri belirleyin.

3. İlk genişletilmiş sistem, ilk tek yönlü tabloya girilir. Hedefin doğrusal fonksiyonunun denklemini veren tablonun son satırına değerlendirici... Hedef fonksiyonunun katsayılarını belirtir. Tablonun sol sütununda ana değişkenleri (temel), aşağıda - serbest değişkenler için katsayıları yazıyoruz. Sondan bir önceki sütun, genişletilmiş sistemin serbest üyelerini içerir. Son sütun, ilişki bazında (6.29) temel değişkeni belirlemek için gerekli olan değerlendirici ilişkiler için hazırlanmıştır.

4. Problemi Teorem 6.7,…, 6.9'a göre değerlerle çözme olasılığını belirleyin.

5. Çözümleme (destekleyici) öğesini seçin.

Tablolu bir simpleks yöntemi kullanarak bir üretim problemini çözme

Optimallik kriteri karşılanmazsa (Teorem 6.7 veya 6.8'in koşulları karşılanmazsa), son satırdaki mutlak değerdeki en büyük negatif katsayı, çözümleme (destek) sütununu belirler. .

Her satır için tahmini ilişkileri aşağıdaki kurallara göre oluşturuyoruz:

10), hepsinin farklı işaretleri varsa;

2 0), eğer hepsi ve;

3 0) eğer;

4 0) 0, ise ve;

5 0), eğer ve aynı işaretlere sahipse.

tanımlayalım. Son minimum yoksa, problemin nihai optimumu yoktur (). Minimum sonluysa, çizgiyi seçin Q ulaşıldığı (birkaç tane varsa, herhangi biri) ve buna çözümleme (referans) dizesi diyoruz. İzin verilen satır ve sütunun kesiştiği yerde izin veren (destek) eleman bulunur.

6 0) Kurallara göre bir sonraki tabloya gidin:

a) sol sütuna yeni bir temel yazıyoruz: ana değişken yerine - bir değişken, yani. değişkenleri değiştirelim ve;

b) destek elemanının yerine 1'i koyun;

c) orijinal tablonun öğelerini yeni tabloda referans satırının kalan yerlerinde bırakın;

d) orijinal tablonun karşılık gelen öğelerini –1 ile çarpılarak pivot sütunun kalan yerlerine koyun;

e) öğelerin kalan boş yerlerine, yeni tabloda, aşağıdaki gibi sayıları yazın:

Bu formülleri kullanarak hesaplamaları basitleştirmek için şu şekilde formüle edilebilirler: "Dikdörtgen kuralları"(Şek. 6.8): köşeleri (veya,,,,,,,,) olan bir dikdörtgenin köşegenleri üzerindeki elemanlar çarpılır (bir pivot eleman içermeyen ürün eksi işareti ile alınır) ve elde edilen ürünler katma;

f) yeni tablonun alınan tüm öğelerini bir pivot öğeye bölün.

7 0) Elemanın değerine göre amaç fonksiyonunun optimal değerinin bulunup bulunmadığını belirleyiniz. Olumsuz bir cevap durumunda, çözüme devam edin (6. maddeye dönün).

Pirinç. 6.8. Sayıları tanımlamak için dikdörtgen kuralı:

a -, b -, c -.

Dejenere olmayan kabul edilebilir temel çözümler için tek yönlü tabloları dönüştürmek için bir algoritma göz önünde bulundurulur, yani. Teorem 6.9 tarafından açıklanan durum geçerlidir. Orijinal doğrusal programlama problemi dejenere ise, o zaman simpleks yöntemiyle çözümü sırasında dejenere temel çözümler ortaya çıkabilir. Bu durumda, tek yönlü yöntemin boş adımları mümkündür, yani. yinelemeler nerede F(x) değişmez. Döngü de mümkündür, yani. sonsuz boş adımlar dizisi. Bunu önlemek için özel algoritmalar geliştirildi - antiksiklinler. Bununla birlikte, çoğu durumda, boştaki adımların yerini, amaç fonksiyonunda bir azalma olan adımlar alır ve çözüm süreci, sonlu sayıda yinelemenin bir sonucu olarak sona erer.

Örnek 6.8. Simpleks yöntemini kullanarak Örnek 6.7'deki problemi çözün.

⇐ Önceki45678910111213Sonraki ⇒

Yayın tarihi: 2015-01-23; Okuyun: 174 | Sayfa telif hakkı ihlali

Studopedia.org - Studopedia.Org - 2014-2018. (0,002 s) ...

Ana Sayfa >> Örnek №3. Simpleks yöntemi. Bir fonksiyonun en büyük değerini bulma (yapay temel)

Simpleks yöntemi

Seçilen satır katsayıları arasında pozitif katsayı yoktur. Sonuç olarak, F fonksiyonunun en büyük değeri bulunur.

Cevap:

x 1 = 3 x 2 = 4

Fmaks = 13

Sorununuzu çözmeye gidin

© 2010-2018, tüm sorularınız için adrese yazınız [e-posta korumalı]

Görev

Üç mal grubunun satışı için, ticari bir işletmenin b 1 = 240, b 2 = 200, b 3 = 160 birim miktarında üç tür sınırlı maddi ve parasal kaynağı vardır. Aynı zamanda 1 grup malın satışı için 1 bin ruble. birinci tür kaynağın cirosu 11 = 2 birim, ikinci türün kaynağı 21 = 4 birim, üçüncü türün kaynağı 31 = 4 tane. 1 bin ruble için 2 ve 3 grup mal satışı için. ciro, sırasıyla, birinci tür kaynağın 12 = 3, 13 = 6 birim miktarında, ikinci türün kaynağının 22 = 2, 23 = 4 birim miktarında harcanır, 32 = 6, 33 = 8 birim miktarında üçüncü tür kaynak ... Üç grup malın 1 bine satışından elde edilen kar.

LPP'yi çözmek için tek yönlü yöntem

ovmak. ciro sırasıyla, c 1 = 4, c 2 = 5, c 3 = 4 (bin ruble). Ticaret girişiminin kârının maksimum olması için planlanan ciro hacmini ve yapısını belirleyin.

Doğrudan ciro planlama görevine, simpleks yöntemiyle çözülebilir, makyaj yapmak ikili görev doğrusal programlama.
Düzenlemek eşlenik değişken çiftleri doğrudan ve ikili görevler.
Eşlenik değişken çiftlerine göre, doğrudan problemin çözümünden, ikili problem çözümü hangisinde kaynak değerlendirmesi mal satışı için harcanır.

Problemi simpleks yöntemiyle çözme

x 1, x 2, x 3 - satılan mal sayısı, bin ruble, sırasıyla 1, 2, 3 - grupları. O zaman problemin matematiksel modeli şu şekildedir:

F = 4 x 1 + 5 x 2 + 4 x 3 -> maks

Simpleks yöntemini çözüyoruz.

Eşitsizlikleri eşitliklere dönüştürmek için ek değişkenler x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 girin.

x 4 = 240'ı temel alın; x 5 = 200; x6 = 160.

içine veri giriyoruz tek yönlü tablo

1 numaralı tek yönlü tablo

Amaç fonksiyonu:

0 240 + 0 200 + 0 160 = 0

Aşağıdaki formülü kullanarak puanları hesaplıyoruz:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Negatif derecelendirmeler olduğundan, plan optimal değildir. En düşük not:

x 2 değişkenini temele dahil ediyoruz.

Temelden ayrılan bir değişken tanımlıyoruz. Bunu yapmak için, x 2 sütunu için negatif olmayan en küçük oranı buluyoruz.

= 26.667

Negatif olmayan en küçük: Q 3 = 26.667. x 6 değişkenini temelden türetiyoruz

3. satırı 6'ya bölün.
1. satırdan 3. satırı 3 ile çarpıp çıkarın
2. satırdan 3. satırın 2 ile çarpımını çıkarın

Hesaplıyoruz:

Yeni bir tablo alıyoruz:

Simpleks tablo numarası 2

Amaç fonksiyonu:

0 160 + 0 440/3 + 5 80/3 = 400/3

Aşağıdaki formülü kullanarak puanları hesaplıyoruz:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 = 5/6

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

x 1 değişkenini temele dahil ediyoruz.

Temelden ayrılan bir değişken tanımlıyoruz. Bunu yapmak için, x 1 sütunu için negatif olmayan en küçük oranı bulun.

Negatif olmayan en küçük: Q 3 = 40. x 2 değişkenini temelden türetiyoruz

3. sırayı 2/3'e bölün.
2. sıradan, 3. satırı 8/3 ile çarparak çıkarın.

Hesaplıyoruz:

Yeni bir tablo alıyoruz:

Simpleks tablo numarası 3

Amaç fonksiyonu:

0 160 + 0 40 + 4 40 = 160

Aşağıdaki formülü kullanarak puanları hesaplıyoruz:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 = 1

Olumsuz bir değerlendirme olmadığı için plan optimaldir.

Sorunun çözümü:

Cevap

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; Fmaks = 160

Yani, birinci tip malları 40 bin tutarında satmak gerekiyor.

ovmak. 2. ve 3. tip malları satmak gerekli değildir. Bu durumda maksimum kar F max = 160 bin ruble olacaktır.

İkili sorunun çözümü

İkili sorun şudur:

Z = 240 y 1 + 200 y 2 + 160 y 3 -> dak

Eşitsizlikleri eşitliklere dönüştürmek için y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 ek değişkenleri girin.

Doğrudan ve ikili problemlerin eşlenik değişken çiftleri şu şekildedir:

Doğrudan problemin 3 numaralı tablosunun son simpleksinden, ikili problemin çözümünü buluyoruz:

Z min = Fmax = 160;
y 1 = Δ 4 = 0; y2 = Δ5 = 0; y3 = A6 = 1; y 4 = A 1 = 0; y5 = A2 = 1; y6 = A3 = 4;

Cevap

y 1 = 0; y2 = 0; y3 = 1; Zmin = 160;

Simpleks yöntemi, bir temel noktadan (temel çözüm) diğerine geçerken çözümlerin art arda iyileştirilmesi ilkesine dayanan bir hesaplama prosedürüdür. Bu durumda amaç fonksiyonunun değeri iyileşir.

Temel çözüm, kabul edilebilir değerler alanının köşelerinde bulunan uygun çözümlerden biridir. Optimallik için simpleksin tepe noktalarını kontrol ederek, istenen optimuma ulaşılır. Simpleks yöntemi bu prensibe dayanmaktadır.

Simpleks, bir hiper düzlemde yer almayan n + 1 köşesi olan n-boyutlu uzayda dışbükey bir çokgendir (hiperdüzlem uzayı iki yarım uzaya böler).

Örneğin, bütçe kısıtlamaları, malları erişilebilir ve kullanılamaz olarak ayırır.

Optimal bir çözüm varsa, "döngü" durumları dışında, sonlu sayıda yinelemeden (adımlardan) sonra mutlaka bulunacağı kanıtlanmıştır.

Simpleks yönteminin algoritması birkaç aşamadan oluşur.

İlk aşama. Bir ilk optimizasyon modeli oluşturulur. Ayrıca, koşulların ilk matrisi, diğer tüm kanonik formlar arasında öne çıkan indirgenmiş kanonik forma dönüştürülür:

a) koşulların sağ tarafları (serbest terimler bi) negatif olmayan niceliklerdir;

b) koşulların kendileri eşitliktir;

c) koşul matrisi tam bir birim alt matrisi içerir.

Serbest terimler negatif ise, eşitsizliğin her iki tarafı da - 1 ile çarpılır ve eşitsizliğin işareti tersine çevrilir. Eşitsizlikleri eşitliklere dönüştürmek için, genellikle yeterince kullanılmayan kaynakların miktarını gösteren ek değişkenler eklenir. Bu onların ekonomik anlamıdır.

Son olarak, ek değişkenler eklendikten sonra, koşullar matrisi tam bir birim alt matrisi içermiyorsa, ekonomik anlamı olmayan yapay değişkenler eklenir. Yalnızca bir birim alt matrisi elde etmek ve simpleks yöntemini kullanarak problemi çözme sürecine başlamak için tanıtılırlar.

Problemin optimal çözümünde tüm yapay değişkenler (AI) sıfıra eşit olmalıdır. Bunu yapmak için, problem maks için çözülürken büyük negatif katsayılarla (-M) ve problem min için çözüldüğünde büyük pozitif katsayılarla (+ M) yapay değişkenler problemin amaç fonksiyonuna dahil edilir. Bu durumda, yapay değişkenin sıfır olmayan önemsiz bir değeri bile, amaç fonksiyonunun değerini keskin bir şekilde azaltacaktır (arttıracaktır). Genellikle M, ana değişkenler için katsayı değerlerinden 1000 kat daha büyük olmalıdır.

İkinci aşama. Bir başlangıç ​​simpleks tablosu oluşturulur ve bazı başlangıç ​​temel çözümleri bulunur. Birim alt matrisi oluşturan değişkenler kümesi ilk temel çözüm olarak alınır. Bu değişkenlerin değerleri serbest üyelere eşittir. Diğer tüm temel dışı değişkenler sıfırdır.

Üçüncü aşama. Temel çözüm, amaç fonksiyonu katsayılarının özel tahminleri kullanılarak optimallik açısından test edilir. Amaç fonksiyonunun katsayılarının tüm tahminleri negatif veya sıfıra eşitse, mevcut temel çözüm optimaldir. Amaç fonksiyonunun katsayısının en az bir tahmini sıfırdan büyükse, mevcut temel çözüm optimal değildir ve iyileştirilmelidir.

Dördüncü aşama. Yeni bir temel çözüme geçiş. Açıkçası, optimal plan, amaç fonksiyonunu en büyük ölçüde artıran böyle bir değişken içermelidir. Problemleri maksimum kar için çözerken, optimal plan, üretimi en karlı olan ürünleri sunar. Bu, amaç fonksiyonu katsayısı tahmininin maksimum pozitif değeri ile belirlenir.

Bu yinelemede bu sayıya sahip simpleks tablonun sütununa genel sütun denir.

Genel satırı bulmak için, tüm ücretsiz üyeler (kaynaklar) genel sütunun karşılık gelen öğelerine bölünür (ürün birimi başına kaynak tüketim oranı). Elde edilen sonuçlardan en küçüğü seçilir. Bu yinelemede karşılık gelen satıra genel denir. Belirli bir yinelemede üretimi sınırlayan bir kaynağa karşılık gelir.

Genel bir sütunun ve bir satırın kesişimindeki bir simpleks tablo elemanına genel eleman denir.

Daha sonra genel çizginin tüm öğeleri (ücretsiz üye dahil) genel öğeye bölünür. Bu işlem sonucunda genel eleman bire eşit olur. Ayrıca, genel sütunun diğer tüm elemanlarının sıfıra eşit olması gerekir, yani. genel sütun tek olmalıdır. Tüm dizeler (genel olan hariç) aşağıdaki gibi dönüştürülür. Yeni satırın elde edilen elemanları, genel sütunun karşılık gelen elemanı ile çarpılır ve elde edilen ürün, eski satırın elemanlarından çıkarılır.

Yeni temel değişkenlerin değerleri, serbest üyeler sütununun karşılık gelen hücrelerinde elde edilir.

Beşinci aşama. Elde edilen temel çözüm, optimallik açısından kontrol edilir (üçüncü aşamaya bakınız). Optimal ise, hesaplamalar durdurulur. Aksi takdirde yeni bir temel çözüm (dördüncü aşama) vb. bulunması gerekir.

Simpleks yöntemi

Simpleks yöntemini kullanarak doğrusal programlamanın optimizasyon problemlerini çözme örneği

İki tip ürün (x1 ve x2) için optimal üretim planını bulmak gerekli olsun.

İlk veri:

Bir optimizasyon modeli oluşturalım

- A kaynağında sınırlama;

- kaynak sınırlaması V.

Sorunu indirgenmiş kanonik biçimine getirelim. Bunu yapmak için, X3 ve X4 ek değişkenlerini tanıtmak yeterlidir. Sonuç olarak, eşitsizlikler katı eşitliklere dönüştürülür.

Başlangıç ​​simpleks tablosunu oluşturalım ve ilk temel çözümü bulalım. Birim alt matrisine karşılık geldikleri için ek değişkenler olacaklar.

1. yineleme. Genel sütunu ve genel satırı bulun:

Genel eleman 5'tir.

2. yineleme. Bulunan temel çözüm optimal değildir, çünkü dereceler dizisi (Fj-Cj) bir pozitif öğe içerir. Genel sütunu ve genel satırı bulun:

maks (0,0.3, -1.4,0) = 0,2

Bulunan çözüm optimaldir, çünkü Fj - Cj amaç fonksiyonunun tüm özel tahminleri sıfıra veya negatife eşittir. F(x) = 29 x1 = 2; x2 = 5.

11.4. ÇİFT SIMPLEX YÖNTEMİ

Önceki paragrafların sonuçlarından, orijinal probleme bir çözüm elde etmek için, ikiliye gidilebilir ve optimal planının tahminlerini kullanarak orijinal problemin optimal çözümünü belirleyebilir.

İkili probleme geçiş gerekli değildir, çünkü bir birim ek bazına sahip ilk simpleks tablosunu düşünürsek, o zaman sütunların orijinal problemi içerdiğini ve satırların ikili olanı içerdiğini görmek kolaydır.

Gösterildiği gibi, herhangi bir yinelemede doğrudan problemi çözerken, fark, yani büyüklük - değişkendeki katsayı, ikili problemin karşılık gelen kısıtının sağ ve sol tarafları arasındaki farka eşittir. Maksimize edilmiş bir amaç fonksiyonu ile doğrudan bir problem çözerken, yineleme optimal bir çözüme yol açmazsa, o zaman en az bir değişken için ve sadece herkes için optimumda fark.

Bu durumu dualiteyi de göz önünde bulundurarak şöyle yazabiliriz:

.

Yani eğer, Daha sonra . Bu, doğrudan sorunun çözümü yetersiz olduğunda, ikili sorunun çözümünün kabul edilemez olduğu anlamına gelir. Diğer tarafta NS . Dolayısıyla, doğrudan problemin optimal çözümünün, ikili problemin kabul edilebilir bir çözümüne tekabül ettiği sonucu çıkar.

Bu, ilk başta kabul edilemez, ancak "optimumden daha iyi" bir çözümün elde edildiği doğrusal programlama problemlerini çözmek için yeni bir yöntem geliştirmeyi mümkün kıldı (olağan simpleks yönteminde, ilk önce bulunur. izin verilebilir, ancak standart altıçözüm). adı verilen yeni bir yöntem ikili simpleks yöntemi, çözüm için optimallik koşulunun yerine getirilmesini ve uygulanabilir çözümler bölgesine sistematik "yaklaşımını" sağlar. Elde edilen çözümün kabul edilebilir olduğu ortaya çıktığında, bu çözüm de optimal olduğu için yinelemeli hesaplama süreci sona erer.

İkili simpleks yöntemi, kısıtlama sistemleri pozitif bir temelde herhangi bir işaretin serbest terimlerini içeren doğrusal programlama problemlerinin çözülmesine izin verir. Bu yöntem, kısıtlama sisteminin dönüşüm sayısını ve ayrıca tek yönlü tablonun boyutunu azaltmanıza olanak tanır. Bir örnek kullanarak ikili simpleks yönteminin uygulamasını ele alalım.

Örnek... Bir fonksiyonun minimumunu bulun

kısıtlamalarla

.

Kanonik forma geçelim:

kısıtlamalarla

İlk simpleks tablosu

İlk temel çözümoptimal, ancak kabul edilebilir değil.

Her zamanki simpleks yöntemi gibi, dikkate alınan çözüm yöntemi de kabul edilebilirlik ve optimallik koşullarının kullanımına dayanmaktadır.

Kabul edilebilirlik koşulu... Mutlak değerdeki en büyük negatif temel değişken, hariç tutulan değişken olarak seçilir (alternatiflerin varlığında seçim keyfi yapılır). Tüm temel değişkenler negatif değilse, elde edilen çözüm uygulanabilir ve optimal olduğu için hesaplama süreci sona erer.

Durum optimallik... Baza dahil edilen değişken, baz olmayan değişkenler arasından aşağıdaki gibi seçilir. Sol tarafın katsayılarının oranları hesaplanır- hariç tutulan değişkenle ilişkili denklemin karşılık gelen katsayılarına denklemler. Pozitif veya sıfır paydalı ilişkiler yok sayılır. Girilen değişkenin minimizasyonu probleminde, belirtilen oranların en küçüğü karşılık gelmelidir ve maksimizasyon probleminde mutlak değerdeki en küçüğün oranı (alternatiflerin varlığında seçim keyfi olarak yapılır). Tüm oranların paydaları sıfır veya pozitif ise, problemin uygulanabilir bir çözümü yoktur.

Bir sonraki çözümü elde etmek için tabana dahil edilecek ve hariç tutulacak değişkenleri seçtikten sonra, bir simpleks tablonun satırlarını dönüştürmenin olağan işlemi gerçekleştirilir.

Bu örnekte, hariç tutulan değişken... Yeni temel değişkeni belirlemek için hesaplanan ilişkiler aşağıdaki tabloda gösterilmiştir:

Dahil edilen değişken seçilir x 2. Sonraki dize dönüştürme, yeni bir tek yönlü tabloyla sonuçlanır:

Yeni çözüm ayrıca optimal, ancak yine de geçerli değil. Yeni bir hariç tutulan değişken olarak (keyfi olarak) seçin x 3. Dahil edilen değişkeni tanımlayalım.

Burada, bir simpleks yöntemi kullanarak problem çözme algoritmasını anlamak için ayrıntılı açıklamalarla bir simpleks yöntemi (bir applet çözmeye benzer) kullanarak iki problemin manuel (bir uygulama değil) çözümü bulunmaktadır. İlk problem sadece "≤" (başlangıç ​​tabanlı bir problem) eşitsizlik işaretlerini içerir, ikincisi "≥", "≤" veya "=" (yapay tabanlı bir problem) işaretlerini içerebilir, bunlar farklı şekillerde çözülür .

Simpleks yöntemi, bir problemin başlangıç ​​bazında çözülmesi

1)Simpleks yöntemi başlangıç ​​temeli olan bir problem için (tüm eşitsizlik-kısıtlama işaretleri "≤").

Görevi yazalım kanonik biçim, yani eşitsizlik kısıtlamaları ekleyerek eşitlikler olarak yeniden yazılabilir bilanço değişkenler:

Bu sistem temelli bir sistemdir (temel s 1, s 2, s 3, her biri sistemin sadece bir denklemine 1 katsayısı ile dahil edilir), x 1 ve x 2 serbest değişkenlerdir. Çözümünde simpleks yönteminin kullanıldığı problemler aşağıdaki iki özelliğe sahip olmalıdır: - kısıtlama sistemi, temeli olan bir denklem sistemi olmalıdır; - sistemdeki tüm denklemlerin serbest terimleri negatif olmamalıdır.

Ortaya çıkan sistem, temeli olan bir sistemdir ve serbest terimleri negatif değildir; bu nedenle uygulayabiliriz. tek yönlü yöntem... Sorunu çözmek için ilk tek yönlü tabloyu (Yineleme 0) oluşturalım. tek yönlü yöntem, yani amaç fonksiyonunun katsayıları tablosu ve karşılık gelen değişkenler için bir denklem sistemi. Burada "BP", temel değişkenlerin sütunu anlamına gelir, "Çözüm" - sistemin denklemlerinin sağ taraflarının sütunu. Çözüm optimal değil çünkü z - satırında negatif katsayılar var.

simpleks yöntem yineleme 0

Çözümü geliştirmek için bir sonraki yinelemeye geçelim tek yönlü yöntem, aşağıdaki tek yönlü tabloyu elde ederiz. Bunu yapmak için seçmeniz gerekir izin verilen sütun, yani simpleks yönteminin bir sonraki yinelemesinde temele dahil edilecek bir değişken. Z-satırındaki (maksimum problemde) mutlak değerdeki en büyük negatif katsayı ile seçilir - simpleks yönteminin ilk yinelemesinde, bu x 2 sütunudur (katsayı -6).

Daha sonra seçilir izin verilen dize, yani simpleks yönteminin bir sonraki yinelemesinde temelden çıkacak değişken. "Karar" sütununun, çözümleme sütununun ("Oran" sütunu) karşılık gelen pozitif öğelerine en küçük oranı ile seçilir - ilk yinelemede, bu satır s 3'tür (katsayı 20).

izin verilen öğeçözümleme sütununun ve çözümleme satırının kesişimindedir, hücresi vurgulanır, 1'e eşittir. Bu nedenle, simpleks yönteminin bir sonraki yinelemesinde, x 2 değişkeni temelde s 1'in yerini alacaktır. İlişkinin z-çizgisinde aranmadığına dikkat edin; oraya bir tire "-" konur. Aynı minimum ilişkiler varsa, bunlardan herhangi biri seçilir. Çözüm sütununda tüm katsayılar 0'dan küçük veya 0'a eşitse, sorunun çözümü sonsuzdur.

Aşağıdaki tabloyu "Yineleme 1" dolduralım. "Yineleme 0" tablosundan alacağız. Daha ileri dönüşümlerin amacı, çözümleme sütunu x 2'yi bire (çözümleme öğesi yerine bir ve diğer öğeler yerine sıfırlarla) dönüştürmektir.

1) "Yineleme 1" tablosunun x 2 satırının hesaplanması. İlk olarak, "Yineleme 0" tablosunun çözümleme satırı s 3'ün tüm üyelerini bu tablonun çözümleme elemanına (bu durumda 1'e eşittir) böleriz, yineleme 1 tablosunda satır x 2 elde ederiz. Çünkü bu durumda çözümleme elemanı 1'e eşittir, daha sonra "Yineleme 0" tablosunun s 3 satırı, "Yineleme 1" tablosunun x 2 satırı ile çakışacaktır. "Yineleme 1" tablosunun x 2 satırını 0 1 0 0 1 20 aldık, "Yineleme 1" tablosunun geri kalan satırları bu satırdan ve "Yineleme 0" tablosunun satırları aşağıdaki gibi elde edilecektir:

2) "Yineleme 1" tablosunun z satırının hesaplanması. Yineleme 0 tablosunun x 2 sütunundaki ilk satırda (z-satır) -6 yerine, Yineleme 1 tablosunun ilk satırında 0 olmalıdır. Bunu yapmak için, "Yineleme 1" tablosunun x 2 satırının tüm öğelerini 0 1 0 0 1 20 6 ile çarparız, 0 6 0 0 6 120 elde ederiz ve bu satırı ilk satır (z - satır) ile ekleriz. "Yineleme 0" tablosundan -4 -6 0 0 0 0, -4 0 0 0 6 120 elde ederiz. x 2 sütununda sıfır 0 görünür, hedefe ulaşılır. İzin verilen sütun öğeleri x 2 kırmızıyla vurgulanır.

3) "Yineleme 1" tablosunun 1. satırının hesaplanması. "Yineleme 0" tablosunun 1 satırındaki 1 yerine, "Yineleme 1" tablosunda 0 olmalıdır. Bunu yapmak için, "Yineleme 1" tablosunun x 2 satırının tüm öğelerini 0 1 0 0 1 20 -1 ile çarparız, 0 -1 0 0 -1 -20 alırız ve bu satırı s 1 ile ekleriz - "Yineleme 0" tablosunun satırı 2 1 1 0 0 64, satır 2 0 1 0 -1 44'ü alıyoruz. x 2 sütununda gerekli 0'ı alıyoruz.

4) "Yineleme 1" tablosunun 2. satırının hesaplanması. "Yineleme 0" tablosunun 2 satırındaki 3 yerine, "Yineleme 1" tablosunda 0 olmalıdır. Bunu yapmak için, "Yineleme 1" tablosunun x 2 satırının tüm öğelerini 0 1 0 0 1 20 -3 ile çarparız, 0 -3 0 0 -3 -60 alırız ve bu satırı s 1 ile ekleriz - satır "Yineleme 0" tablosundan 1 3 0 1 0 72, 1 0 0 1 -3 12 satırını alırız. x 2 sütununda gerekli 0 elde edilir. "Yineleme 1" tablosundaki sütun x 2, bir, bir 1 ve geri kalan 0'ı içerir.

"Yineleme 1" tablosunun satırları aşağıdaki kurala göre elde edilir:

Yeni Satır = Eski Satır - (Eski Satırın Çözünürlük Sütunu Faktörü) * (Yeni Çözünürlük Satırı).

Örneğin, z-çizgisi için elimizde:

Eski z-çizgisi (-4 -6 0 0 0 0) - (- 6) * Yeni çözüm çizgisi - (0 -6 0 0 -6 -120) = Yeni z-çizgisi (-4 0 0 0 6 120).

Aşağıdaki tablolar için, tablo öğelerinin yeniden hesaplanması aynı şekilde yapılır, bu yüzden onu atlıyoruz.

simpleks yöntem yineleme 1

x 1 sütununa izin verildiğinde, s 2 satırını çözerek, s 2 temelden çıkar, x 1 temele girer. Tam olarak aynı şekilde, z-satırındaki tüm pozitif katsayıları olan bir tablo elde edene kadar simpleks tabloların geri kalanını elde ederiz. Bu, optimal bir tablonun işaretidir.

simpleks yöntem yineleme 2

Çözümleme sütunu s 3, çözümleme satırı s 1, s 1 tabandan çıkar, s 3 tabana girer.

simpleks yöntem yineleme 3

z satırında tüm katsayılar negatif değildir, bu nedenle x 1 = 24, x 2 = 16, z max = 192 optimal bir çözüm elde edilir.

Üç çeşit gömlek üretimi için iplik, düğme ve kumaş kullanılmaktadır. İplik, düğme ve kumaş stokları, bir gömlek dikmek için tüketim oranları tabloda gösterilmiştir. Maksimum karı ve bunu sağlayan en uygun ürün sürüm planını bulun (bul).

sorunun çözümü

Modeli oluşturmak

Serbest bırakılması amaçlanan 1., 2. ve 3. tip gömleklerin sayısı ve sayısı.

Ardından kaynak kısıtlamaları şöyle görünecektir:

Ayrıca problemin anlamı dahilinde

Elde edilen karı ifade eden amaç fonksiyonu:

Aşağıdaki doğrusal programlama problemini elde ederiz:

Doğrusal programlama problemini kanonik forma indirgemek

Sorunu kanonik bir forma getirelim. Ek değişkenleri tanıtalım. Tüm ek değişkenleri, sıfıra eşit bir katsayı ile amaç fonksiyonuna dahil ediyoruz. Tercih formu olmayan kısıtların sol taraflarına ek değişkenler ekliyoruz ve eşitlikler elde ediyoruz.

Simpleks yöntemini kullanarak sorunu çözme

Simpleks tablosunu dolduruyoruz:

Maksimum problemini çözdüğümüz için maksimum problemi çözerken indeks satırında negatif sayıların bulunması optimal bir çözüm elde edemediğimizi ve 0. iterasyon tablosundan diğerine geçmemiz gerektiğini gösterir.

Bir sonraki iterasyona geçiş şu şekilde gerçekleştirilir:

önde gelen sütun eşleşmeleri

Anahtar satır, serbest üyelerin ve önde gelen sütunun üyelerinin (simpleks ilişkiler) minimum oranı ile belirlenir:

Anahtar sütunun ve anahtar satırın kesişiminde, çözümleme öğesini, yani. dokuz.

Şimdi 1. yinelemeyi çizmeye başlıyoruz: Birim vektör yerine bir vektör giriyoruz.

Yeni tabloda, çözümleme öğesi yerine 1 yazın, anahtar sütunun diğer tüm öğeleri sıfırlanır. Anahtar satır öğeleri, izin veren öğelere bölünmüştür. Tablonun diğer tüm elemanları dikdörtgen kuralına göre hesaplanır.

1. yineleme eşleşmeleri için anahtar sütun

İzin verilen elemanlar 4/3 sayısıdır. Vektörü tabandan çıkarıyoruz ve bunun yerine vektörü giriyoruz. 2. yinelemenin tablosunu alıyoruz.

2. yineleme eşleşmeleri için anahtar sütun

Anahtar dizeyi buluyoruz, bunun için tanımlıyoruz:

Çözme elemanı 10/3 sayısıdır. Vektörü tabandan çıkarıyoruz ve bunun yerine vektörü giriyoruz. 3. yinelemenin tablosunu alıyoruz.

Dizin satırındaki tüm terimler negatif değildir, bu nedenle doğrusal programlama problemine aşağıdaki çözüm elde edilir (bunu serbest terimler sütunundan yazarız):

24 tip 1 gömlek, 7 tip 2 gömlek ve 3 tip 3 gömlek dikmek gerekir. Bu durumda, ortaya çıkan kar maksimum olacak ve 95 ruble olacak.

Simpleks tabloları kullanarak bir doğrusal programlama problemini çözmeniz gerekiyorsa, çevrimiçi hizmetimiz size çok yardımcı olacaktır. Simpleks yöntemi, fonksiyonun aşırı bir değer aldığı tepe noktasını bulmak için izin verilen değerler aralığının tüm köşelerinin sıralı bir şekilde numaralandırılmasını ifade eder. İlk aşamada, sonraki her adımda gelişen bir çözüm bulunur. Bu çözüme temel denir. Simpleks yöntemini kullanarak bir doğrusal programlama problemini çözerken bir dizi eylem:

İlk adım. Derlenen tabloda, öncelikle ücretsiz üyeler içeren sütunu görüntülemeniz gerekir. Negatif öğeler içeriyorsa, ikinci adıma, değilse beşinci adıma geçmek gerekir.

İkinci adım. İkinci adımda, simpleks tablosunu yeniden hesaplamak için hangi değişkenin temelden çıkarılacağına ve hangilerinin dahil edileceğine karar vermek gerekir. Bunu yapmak için, ücretsiz üyeler içeren sütuna bakın ve içinde olumsuz bir öğe bulun. Negatif elemanlı satıra ön satır adı verilir. İçinde mutlak değerdeki maksimum negatif öğeyi, karşılık gelen sütunu - takipçiyi buluyoruz. Serbest üyeler arasında negatif değerler varsa, ancak ilgili satırda değilse, böyle bir tablonun çözümü olmayacaktır. Önde gelen satırda değişiklik yapılarak, serbest üye sütunundaki baz dışı bırakılır ve önde gelen sütuna karşılık gelen değişken baza alınır.

Tablo 1.

Üçüncü adım. Üçüncü adımda, tüm simpleks tablosunu özel formüller kullanarak yeniden hesaplıyoruz, bu formüller kullanılarak görülebilir.

Dördüncü adım. Yeniden hesaplamadan sonra, serbest terimler sütununda negatif öğeler kalırsa, ilk adıma, böyle bir şey yoksa beşinci adıma gidin.

Beşinci adım. Beşinci adıma ulaştıysanız, kabul edilebilir bir çözüm buldunuz. Ancak bu, optimal olduğu anlamına gelmez. Yalnızca F satırındaki tüm öğeler pozitifse optimal olacaktır. Durum böyle değilse, sonraki yeniden hesaplama için önde gelen satır ve sütunu bulduğumuz çözümü aşağıdaki algoritmaya göre geliştirmek gerekir. Başlangıçta, fonksiyon değeri hariç, F satırındaki minimum negatif sayıyı buluyoruz. Bu numaraya sahip sütun önde gelen olacaktır. Baştaki satırı bulmak için, pozitif olmaları koşuluyla, karşılık gelen serbest üye ile önde gelen sütundaki elemanın oranını buluyoruz. Minimum ilişki, önde gelen satırı tanımlamanıza izin verecektir. Formülleri kullanarak tabloyu yeniden hesaplıyoruz, yani. 3. adıma gidin.