Doğrudan ve ikili problemlerin simpleks yöntemle çözülmesine bir örnek. Doğrusal programlama. tek yönlü yöntem

Tek yönlü tabloları kullanarak bir doğrusal programlama problemini çözmeniz gerekiyorsa, o zaman bizim çevrimiçi servis size çok yardımcı olacaktır. Simplex yöntemi, işlevin aşırı bir değer aldığı tepe noktasını bulmak için kabul edilebilir değerler aralığının tüm köşelerinin sıralı bir numaralandırmasını ifade eder. İlk aşamada, sonraki her adımda gelişen bir çözüm bulunur. Böyle bir çözüme temel denir. Simpleks yöntemini kullanarak bir doğrusal programlama problemini çözerken bir dizi eylem:

İlk adım. Derlenen tabloda öncelikle ücretsiz üyelerin olduğu sütuna bakmanız gerekiyor. Olumsuz unsurlar içeriyorsa, ikinci adıma, değilse beşinci adıma geçmek gerekir.

İkinci adım. İkinci adımda simpleks tablonun yeniden hesaplanabilmesi için hangi değişkenin tabandan çıkarılacağına ve hangilerinin dahil edileceğine karar verilmesi gerekir. Bunu yapmak için, ücretsiz üyeleri olan sütuna bakarız ve içinde negatif bir öğe buluruz. Negatif elemana sahip bir çizgi, baştaki çizgi olarak adlandırılacaktır. İçinde mutlak değerde maksimum negatif öğeyi buluruz, buna karşılık gelen sütun takipçidir. Ücretsiz üyeler arasında negatif değerler varsa, ancak karşılık gelen satırda değilse, böyle bir tablonun çözümü olmayacaktır. Serbest üyeler sütununda yer alan baştaki satırdaki değişken tabandan çıkarılır ve baştaki sütuna karşılık gelen değişken baza dahil edilir.

Tablo 1.

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

Dördüncü adım. Yeniden hesaplamadan sonra, ücretsiz üyeler sütununda negatif öğeler kalırsa, ilk adıma gidin, yoksa, beşinci adıma geçin.

Beşinci adım. Beşinci adıma ulaştıysanız, kabul edilebilir bir çözüm bulmuşsunuz demektir. 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 iyileştirmek gerekir. Önce minimumu buluruz negatif bir sayı F satırında, işlevin değeri hariç. Bu numaraya sahip sütun önde gelen sütun olacaktır. Baştaki satırı bulmak için, karşılık gelen serbest üye ile öncü sütundaki elemanın pozitif olması şartıyla oranını buluruz. Minimum oran, ön çizgiyi belirleyecektir. Tabloyu formüllere göre yeniden hesaplıyoruz, yani. 3. adıma gidin.

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

Simplex yöntemi, bir problemin başlangıç ​​temelli çözümü

1)tek yönlü yöntem başlangıç ​​temelli bir problem için (kısıt eşitsizliklerinin tüm işaretleri " ≤ " dir).

sorunu yazalım kanonik biçim, yani eşitsizlik kısıtlamalarını eşitlikler olarak yeniden yazarız, bilanço değişkenler:

Bu sistem, tabanı olan bir sistemdir (taban s 1, s 2, s 3, her biri 1 katsayılı sistemin sadece bir denkleminde yer alır), x 1 ve x 2 serbest değişkenlerdir. Simplex yönteminin kullanıldığı problemler aşağıdaki iki özelliğe sahip olmalıdır: - kısıtlamalar sistemi, tabanlı bir denklem sistemi olmalıdır; -Sistemdeki tüm denklemlerin serbest terimleri negatif olmamalıdır.

Ortaya çıkan sistem, tabanlı 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) derleyin. 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şkenler sütunu anlamına gelir, "Çözüm" - sistem denklemlerinin doğru bölümlerinin sütunu. Çözüm optimal değildir, çünkü z çizgisinde negatif katsayılar vardır.

tek yönlü yöntem yineleme 0

Çözümü iyileştirmek için bir sonraki iterasyona geçelim tek yönlü yöntem, aşağıdaki tek yönlü tabloyu elde ederiz. Bunun için seçmeniz gereken sütunu etkinleştir, yani simpleks yönteminin bir sonraki yinelemesinde tabana girecek bir değişken. Z-sırasındaki (maksimum problemde) en büyük negatif katsayı tarafından seçilir - tek yönlü yöntemin ilk yinelemesinde, bu sütun x 2'dir (katsayı -6).

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

izin veren öğe etkinleştirme sütunu ile etkinleştirme satırının kesiştiği noktada bulunur, hücresi renkli olarak 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-dizisinde aranmadığına dikkat edin, oraya kısa çizgi "-" konur. Aynı minimum oranlar varsa, bunlardan herhangi biri seçilir. Çözünürlük sütunundaki tüm katsayılar 0'dan küçük veya ona eşitse, sorunun çözümü sonsuzdur.

Aşağıdaki "İterasyon 1" tablosunu dolduralım. "İterasyon 0" tablosundan alacağız. Diğer dönüşümlerin amacı, x2 etkinleştirme sütununu tek bir sütuna dönüştürmektir (etkinleştirme öğesi yerine bir ve geri kalan öğeler yerine sıfırlar).

1) "Yineleme 1" tablosunun x 2 satırının hesaplanması. İlk olarak, "İterasyon 0" tablosunun çözümleme satırı s 3'ün tüm üyelerini çözümleme elemanına böleriz (1'e eşittir). bu durum) bu tablonun, İterasyon 1 tablosunda satır x 2'yi elde ederiz. Çünkü bu durumda çözme elemanı 1'e eşittir, o zaman "Yineleme 0" tablosunun s 3 satırı "Yineleme 1" tablosunun x 2 satırıyla eşleşecektir. Elde ettiğimiz "İterasyon 1" tablosunun x 2. satırı 0 1 0 0 1 20, "İterasyon 1" tablosunun kalan satırları bu satırdan elde edilecek ve "İterasyon 0" tablosunun satırları aşağıdaki gibi olacaktır:

2) "Yineleme 1" tablosunun z-sırasının hesaplanması. "İterasyon 0" tablosunun x2 sütunundaki ilk satırdaki (z-sırası) -6 yerine "İterasyon 1" tablosunun ilk satırında 0 olmalıdır. Bunun için "İterasyon 1" tablosu 0 1 0 0 1 20'nin x 2 satırının tüm elemanlarını 6 ile çarparız, 0 6 0 0 6 120 elde ederiz ve bu satırı ilk satırla (z - satır) toplarız "İterasyon 0" tablosunun -4 -6 0 0 0 0, -4 0 0 0 6 120 elde ederiz. x 2 sütununda sıfır 0 çıktı, hedefe ulaşıldı. x 2 izin sütununun öğeleri kırmızıyla vurgulanır.

3) "İterasyon 1" tablosunun 1. satırının hesaplanması. "İterasyon 0" tablosunun 1 satırında 1 yerine "İterasyon 1" tablosunda 0 olmalıdır. Bunu yapmak için, "İterasyon 1" tablosu 0 1 0 0 1 20'nin x 2 satırındaki tüm elemanları -1 ile çarparız, 0 -1 0 0 -1 -20 elde ederiz ve bu satırı s 1 - "İterasyon 0" tablosunun 2 1 1 0 0 64 satırı, 2 0 1 0 -1 44 satırını elde ederiz. x 2 sütununda gerekli 0 elde edilir.

4) "İterasyon 1" tablosunun 2. satırının hesaplanması. "İterasyon 0" tablosunun 2 satırındaki 3 yerine "İterasyon 1" tablosunda 0 olmalıdır. Bunu yapmak için, "İterasyon 1" tablosu 0 1 0 0 1 20'nin x 2 satırındaki tüm elemanları -3 ile çarparız, 0 -3 0 0 -3 -60 elde ederiz ve bu satırı s 1 - "İterasyon 0" tablosunun 1 3 0 1 0 72 satırı, 1 0 0 1 -3 12 satırını elde ederiz. x 2 sütununda gerekli 0 elde edilir. "İterasyon 1" tablosundaki x 2 sütunu, tek olur, bir 1 ve geri kalanı 0 içerir.

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

Yeni Satır = Eski Satır - (Eski Satır İzin Faktörü)*(Yeni Satır).

Örneğin, z çizgisi için şuna sahibiz:

Eski z dizisi (-4 -6 0 0 0 0) -(-6)*Yeni z dizisi -(0 -6 0 0 -6 -120) = Yeni z dizisi (-4 0 0 0 6 120) .

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

tek yönlü yöntem yineleme 1

İzin verilen sütun x 1 , izin verilen satır s 2 , s 2 tabanından çıkar, x 1 tabanına girer. Tam olarak aynı şekilde, z satırındaki tüm pozitif katsayıları içeren bir tablo elde edilene kadar kalan tek yönlü tabloları elde ederiz. Bu, optimal bir tablonun işaretidir.

tek yönlü yöntem yineleme 2

s 3 sütununun çözümlenmesi, s 1 , s 1 satırının çözümlenmesi tabandan çıkar, s 3 tabana girer.

tek yönlü yöntem yineleme 3

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

Simplex yönteminin fikri, bir temelden diğerine geçerek en azından mevcut olandan daha az olmayan bir işlev değeri elde etmektir (her bir temel, tek bir işlev değerine karşılık gelir).
Açıkçası, herhangi bir problem için olası temellerin sayısı sınırlıdır (ve çok büyük değildir).
Bu nedenle er ya da geç cevap alınacaktır.

Bir temelden diğerine geçiş nasıl yapılır?
Çözümü tablo şeklinde kaydetmek daha uygundur. Her satır, sistemin bir denklemine eşdeğerdir. Seçilen satır, işlevin katsayılarından oluşur (kendinizi karşılaştırın). Bu, değişkenleri her seferinde yeniden yazmanıza izin vermez, bu da çok zaman kazandırır.
Seçilen satırda en büyük pozitif katsayıyı seçin. Bu, en azından mevcut olandan daha az olmamak üzere, işlevin değerini elde etmek için gereklidir.
Sütun seçildi.
Seçilen kolonun pozitif katsayıları için Θ oranını hesaplayıp en küçük değeri seçiyoruz. Bu, dönüşümden sonra serbest üyeler sütununun pozitif kalması için gereklidir.
Satır seçildi.
Bu nedenle temel olacak eleman belirlenir. Sonra sayıyoruz.

Üç mal grubunun uygulanması için, bir ticari 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 1 bin ruble satışı için. ciro, birinci türdeki bir kaynak 11 = 2 birim miktarında, ikinci türdeki bir kaynak 21 = 4 birim miktarında, üçüncü türdeki bir kaynak 31 = 4 tutarında tüketilir. birimler. 1 bin ruble için 2 ve 3 grup mal satışı için. ciro sırasıyla birinci türdeki kaynak miktarında 12 = 3, a 13 = 6 birim, ikinci türdeki kaynak miktarında 22 = 2, a 23 = 4 birim, kaynak harcanır 32=6 miktarında üçüncü tip, 33=8 adettir. Üç grup malın 1 bin ruble satışından elde edilen kar. ciro sırasıyla c 1 \u003d 4, c 2 \u003d 5, c 3 \u003d 4'tür (bin ruble). Ticaret işletmesinin kârını maksimize etmek için ticaret cirosunun planlanan hacmini ve yapısını belirleyin.

Emtia dolaşım planlamasının doğrudan sorununa, çözülebilir simpleks yöntemi, beste ikili problem doğrusal programlama.
Düzenlemek eşlenik değişken çiftleri doğrudan ve ikili problem.
Eşlenik değişken çiftlerine göre, doğrudan problemin çözümünden şunu elde edin: ikili problem çözümü, hangisinde kaynak tahmini mal satışı için harcanır.

Simpleks probleminin yöntemle çözümü

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

0)))(~)" title="delim(lbrace)(matris(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Simplex'i yöntemle çözüyoruz.

Eşitsizlikleri eşitliğe dönüştürmek için x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 ek değişkenlerini tanıtıyoruz.

Temel olarak x 4 \u003d 240 alıyoruz; x5 = 200; x6 = 160.

Veri girilir tek yönlü tablo

Simplex tablo numarası 1

Hedef işlev:

0 240 + 0 200 + 0 160 = 0

Puanları aşağıdaki formüle göre hesaplıyoruz:

Δ 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ğu için plan optimal değil. En Düşük Puan:

x 2 değişkenini tabana dahil ediyoruz.

Tabanı terk ederek bir değişken tanımlıyoruz. Bunu yapmak için, x 2 sütunu için negatif olmayan en küçük oranı buluruz.

= 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 ile çarpılan 3. satırı çıkarın
2. satırdan 2 ile çarpılan 3. satırı çıkarın

Hesaplıyoruz:

Yeni bir tablo alıyoruz:

Simplex tablo numarası 2

Hedef işlev:

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

Puanları aşağıdaki formüle göre hesaplıyoruz:

Δ 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 Δ 1 = - 2/3 olduğundan, plan optimal değildir.

x 1 değişkenini tabana dahil ediyoruz.

Tabanı terk ederek bir değişken tanımlıyoruz. Bunu yapmak için, x 1 sütunu için negatif olmayan en küçük oranı buluyoruz.

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

3. satırı 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:

Simplex tablo numarası 3

Hedef işlev:

0 160 + 0 40 + 4 40 = 160

Puanları aşağıdaki formüle göre hesaplıyoruz:

Δ 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 tahminler olmadığı için plan optimaldir.

Sorunun çözümü:

Cevap

Yani birinci türden malları 40 bin ruble tutarında satmak gerekiyor. 2. ve 3. türdeki malların satılmasına gerek yoktur. Bu durumda, maksimum kar F max = 160 bin ruble olacaktır.

İkili sorunu çözme

İkili sorun şuna benzer:

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

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Eşitsizlikleri eşitliğe dönüştürmek için y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 ek değişkenlerini tanıtıyoruz.

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

Doğrudan problemin son tek yönlü tablosu No. 3'ten ikili problemin çözümünü buluyoruz:

Zmin = Fmaks = 160;
y 1 \u003d Δ 4 \u003d 0; y 2 \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;

Dikkate almak tek yönlü yöntem doğrusal programlama (LP) problemlerini çözmek için. Değerin bir referans plandan diğerine geçişine dayanır. amaç fonksiyonu artışlar.

Simplex yöntemi algoritması aşağıdaki gibidir:

1. Ek değişkenler ekleyerek orijinal problemi kanonik bir forma çeviriyoruz. ≤ biçimindeki bir eşitsizlik için, ek değişkenler bir işaretle (+), ancak ≥ biçimindeyse, o zaman bir işaretle (-) eklenir. Ek değişkenler, katsayıya eşit olan karşılık gelen işaretlerle amaç fonksiyonuna dahil edilir. 0 , Çünkü amaç fonksiyonu ekonomik anlamını değiştirmemelidir.
2. Vektörler verilir Pi değişkenlerin katsayılarından ve serbest terimler sütunundan. Bu eylem, birim vektörlerin sayısını belirler. Kural, kısıtlama sisteminde eşitsizlik sayısı kadar birim vektör olması gerektiğidir.
3. Bundan sonra, ilk veriler tek yönlü tabloya girilir. Birim vektörler tabana eklenir ve tabandan çıkarılarak en uygun çözüm bulunur. Amaç fonksiyonu katsayıları ters işaretli olarak yazılır.
4. LP problemi için optimallik kriteri, eğer çözümün optimal olmasıdır. F– sıra tüm katsayılar pozitiftir. İzin Sütunu Bulma Kuralı – Görüntülendi F bir dizidir ve negatif elemanları arasından en küçüğü seçilir. Vektör Pi içermesi izin verici hale gelir. Bir çözme elemanı seçme kuralı - çözme sütununun pozitif elemanlarının vektörün elemanlarına oranları derlenir P 0 ve en küçük oranı veren sayı, tek yönlü tablonun kendisine göre yeniden hesaplanacağı çözümleyici öğe olur. Bu öğeyi içeren dizeye etkinleştirme dizesi denir. Çözüm sütununda olumlu öğeler yoksa, sorunun çözümü yoktur. Çözme öğesini belirledikten sonra, yeni bir tek yönlü tablonun yeniden hesaplanmasına geçerler.
5. Yeni bir tek yönlü tablo doldurma kuralları. Çözücü öğenin yerine biri konur ve diğer öğelerin eşit olduğu varsayılır. 0 . Çözme vektörü, karşılık gelen sıfır vektörünün hariç tutulduğu tabana eklenir ve kalan temel vektörler değiştirilmeden yazılır. İzin verilen çizginin elemanları izin verilen elemana bölünür ve kalan elemanlar dikdörtgen kuralına göre yeniden hesaplanır.
6. Bu kadar yapılır F– dizenin tüm öğeleri pozitif olmaz.

Yukarıdaki algoritmayı kullanarak sorunun çözümünü düşünün.
verilen:

Sorunu kanonik forma getiriyoruz:

Vektörleri oluşturuyoruz:

Simplex tablosunu doldurun:

:
Vektörün ilk elemanını yeniden hesapla P 0, bunun için bir sayı dikdörtgeni yapıyoruz: ve şunu elde ederiz: .

Tek yönlü tablonun diğer tüm öğeleri için benzer hesaplamalar yapıyoruz:

Alınan planda F– dizi bir negatif eleman içeriyor – (-5/3), vektörler P1. Sütununda, çözümleyici öğe olacak tek pozitif öğeyi içerir. Tabloyu bu elemana göre yeniden hesaplayalım:

Negatif unsurların yokluğu F- string, bulunan anlamına gelir optimal plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S.A. Doğrusal programlama, M: Bilim, 1998,
• Wentzel E.Ş. Yöneylem Araştırması, M: Sovyet Radyosu, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. matematiksel programlama, E: Lise, 1986

Özel Doğrusal Programlama Çözümü

Web sitemizde bu disiplindeki herhangi bir ödevi sipariş edebilirsiniz. Şu adreste dosya ekleyebilir ve son tarihler belirleyebilirsiniz: