Örnek 5.1. Aşağıdaki doğrusal programlama problemini simpleks yöntemini kullanarak çözün:

Çözüm:

BEN yineleme:

x3, x4, x5, x6 x1,x2. Temel değişkenleri serbest değişkenler cinsinden ifade edelim:

Amaç fonksiyonunu aşağıdaki forma indirgeyelim:

Elde edilen probleme dayanarak başlangıç ​​simpleks tablosunu oluşturacağız:

Tablo 5.3

Orijinal simpleks masa

Temel çözümün tanımına göre, serbest değişkenler sıfıra eşittir ve temel değişkenlerin değerleri, serbest sayıların karşılık gelen değerlerine eşittir, yani:

Aşama 3: PAP kısıtlama sisteminin uyumluluğunun kontrol edilmesi.

Bu yinelemede (Tablo 5.3'te), kısıtlama sisteminin uyumsuzluk işareti (işaret 1) tanımlanmamıştır (yani, negatif serbest sayıya sahip bir satır yoktur (satır hariç) amaç fonksiyonu), en az bir negatif öğenin olmayacağı (yani, serbest bir değişken için negatif bir katsayı)).

Bu yinelemede (Tablo 5.3'te), amaç fonksiyonunun sınırsızlığının işareti (işaret 2) tanımlanmamıştır (yani, amaç fonksiyonu satırında negatif elemanlı bir sütun yoktur (serbest sayılar sütunu hariç) ) en az bir olumlu unsurun olmayacağı) .

Bulunan temel çözüm olumsuz bileşenler içermediğinden kabul edilebilir.

Aşama 6: optimallik kontrolü.

Bulunan temel çözüm optimal değildir, çünkü optimallik kriterine göre (işaret 4) amaç fonksiyonu doğrultusunda hiçbir negatif unsur olmamalıdır (bu kriter dikkate alınırken bu satırın serbest sayısı dikkate alınmaz). Bu nedenle simpleks yöntemi algoritmasına göre 8. aşamaya geçiyoruz.

Bulunan temel çözüm kabul edilebilir olduğundan, çözüm sütununu aşağıdaki şemaya göre arayacağız: amaç fonksiyonu satırındaki negatif öğelere sahip sütunları belirliyoruz (serbest sayılar sütunu hariç). Tablo 5.3'e göre bu tür iki sütun vardır: sütun " x1" ve sütun " x2" Bu sütunlardan hedef fonksiyonun satırındaki en küçük elemanı içeren sütun seçilir. İzin veren kişi o olacak. Kolon " x2" sütuna kıyasla en küçük öğeyi (–3) içerir " x1

Çözümleme doğrusunu belirlemek için serbest sayıların çözümleme sütununun elemanlarına pozitif tahmin edilen oranları bulunur; en küçük pozitif değerlendirme oranına karşılık gelen çizgi çözümlenmiş olarak kabul edilir.

Tablo 5.4

Orijinal simpleks masa

Tablo 5.4'te en küçük pozitif değerlendirme ilişkisi "" satırına karşılık gelmektedir. x5"Bu nedenle hoşgörülü olacaktır.

Etkinleştirme sütunu ile etkinleştirme satırının kesişiminde yer alan öğe etkinleştirme olarak kabul edilir. Örneğimizde bu, “doğrusunun kesişiminde yer alan elemandır” x5" ve sütunlar " x2».

Çözümleme öğesi, yeni bir "geliştirilmiş" temel çözüme geçmek için simpleks tabloda değiştirilmesi gereken bir temeli ve bir serbest değişkeni gösterir. İÇİNDE bu durumda bunlar değişkenler x5 Ve x2, yeni simpleks tablosunda (Tablo 5.5) bunları değiştiriyoruz.

9.1. Çözücü elemanın dönüşümü.

Tablo 5.4'ün çözünürlük öğesi aşağıdaki gibi dönüştürülür:

Ortaya çıkan sonucu Tablo 5.5'teki benzer bir hücreye giriyoruz.

9.2. Çözünürlük dizisi dönüşümü.

Tablo 5.4'ün çözümleme satırının elemanlarını bu simpleks tablonun çözümleme elemanına böleriz, sonuçlar yeni simpleks tablonun benzer hücrelerine uyar (tablo 5.5). Çözünürlük dizisi elemanlarının dönüşümleri Tablo 5.5'te verilmiştir.

9.3. Çözünürlük sütununun dönüştürülmesi.

Tablo 5.4'ün çözünürlük sütununun elemanlarını bu simpleks tablonun çözünürlük elemanına böleriz ve sonuç ters işaretle alınır. Elde edilen sonuçlar yeni simpleks tablonun benzer hücrelerine uyuyor (Tablo 5.5). Çözünürlük sütununun elemanlarının dönüşümleri Tablo 5.5'te verilmiştir.

9.4. Simpleks tablonun geri kalan elemanlarının dönüşümü.

Simpleks tablonun geri kalan elemanlarının (yani çözümleme satırında ve çözümleme sütununda bulunmayan öğeler) dönüşümü "dikdörtgen" kuralına göre gerçekleştirilir.

Örneğin, " çizgisinin kesişiminde bulunan bir öğeyi dönüştürmeyi düşünün. x3" ve sütunlar "", bunu şartlı olarak göstereceğiz " x3" Tablo 5.4'te, bir köşesi değerini dönüştürdüğümüz hücrede (yani "hücrede") bulunan bir dikdörtgeni zihinsel olarak çiziyoruz. x3") ve diğeri (çapraz tepe noktası), çözümleyici öğeye sahip bir hücrededir. Diğer iki köşe (ikinci köşegenin) benzersiz bir şekilde belirlenir. Daha sonra hücrenin dönüştürülmüş değeri " x3", paydasında çözümleme elemanı olan (Tablo 5.4'ten) ve payda kullanılmayan diğer iki köşenin çarpımı olan bu hücrenin önceki değeri eksi kesirine eşit olacaktır, yani:

« x3»: .

Diğer hücrelerin değerleri de benzer şekilde dönüştürülür:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Bu dönüşümler sonucunda yeni bir simpleks tablo elde edildi (Tablo 5.5).

II yineleme:

Aşama 1: Simpleks bir tablonun hazırlanması.

Tablo 5.5

Simpleks tabloII yinelemeler

Aşama 2: Temel çözümün belirlenmesi.

Simpleks dönüşümler sonucunda yeni bir temel çözüm elde edildi (Tablo 5.5):

Gördüğünüz gibi, bu temel çözümde amaç fonksiyonunun değeri = 15 olup, önceki temel çözümden daha büyüktür.

Tablo 5.5'teki özellik 1'e göre kısıtlama sisteminin tutarsızlığı tespit edilmemiştir.

Aşama 4: amaç fonksiyonunun sınırlılığının kontrol edilmesi.

Tablo 5.5'te 2. kritere göre amaç fonksiyonunun sınırsızlığı ortaya çıkmamıştır.

Aşama 5: Bulunan temel çözümün kabul edilebilirliğinin kontrol edilmesi.

Kriter 4'e göre bulunan temel çözüm optimal değildir, çünkü simpleks tablonun amaç fonksiyonu satırı (Tablo 5.5) negatif bir öğe içerir: –2 (bu satır dikkate alınırken bu satırın serbest sayısı dikkate alınmaz) karakteristik). Bu nedenle 8. aşamaya geçiyoruz.

Aşama 8: Çözücü unsurun belirlenmesi.

8.1. Çözünürlük sütununun tanımı.

Bulunan temel çözüm kabul edilebilir; amaç fonksiyonu satırındaki negatif elemanlı sütunları belirleriz (serbest sayılar sütunu hariç). Tablo 5.5'e göre böyle yalnızca bir sütun vardır: " x1" Bu nedenle izin verildiği gibi kabul ediyoruz.

8.2. Etkinleştirme dizesinin tanımı.

Tablo 5.6'da pozitif değerlendirme ilişkilerinin elde edilen değerlerine göre minimum "" çizgisine karşılık gelen ilişkidir. x3" Bu nedenle izin verildiği gibi kabul ediyoruz.

Tablo 5.6

Simpleks tabloII yinelemeler

Aşama 9: Simpleks tablonun dönüştürülmesi.

Simpleks tablonun (Tablo 5.6) dönüşümleri önceki yinelemedekiyle aynı şekilde gerçekleştirilir. Simpleks tablonun elemanlarının dönüşümlerinin sonuçları Tablo 5.7'de verilmiştir.

III yineleme

Önceki yinelemenin simpleks dönüşümlerinin sonuçlarına dayanarak yeni bir simpleks tablosu derliyoruz:

Tablo 5.7

Simpleks tabloIII yinelemeler

Aşama 2: Temel çözümün belirlenmesi.

Simpleks dönüşümler sonucunda yeni bir temel çözüm elde edildi (Tablo 5.7):

Aşama 3: kısıtlama sisteminin uyumluluğunun kontrol edilmesi.

Tablo 5.7'deki özellik 1'e göre kısıtlama sisteminin tutarsızlığı tespit edilmemiştir.

Aşama 4: amaç fonksiyonunun sınırlılığının kontrol edilmesi.

Tablo 5.7'de 2. kritere göre amaç fonksiyonunun sınırsızlığı ortaya çıkmamıştır.

Aşama 5: Bulunan temel çözümün kabul edilebilirliğinin kontrol edilmesi.

Kriter 3'e göre bulunan temel çözüm, olumsuz bileşenler içermediğinden kabul edilebilir.

Aşama 6: Bulunan temel çözümün optimalliğinin kontrol edilmesi.

Kriter 4'e göre bulunan temel çözüm optimal değildir, çünkü simpleks tablonun amaç fonksiyonu satırı (Tablo 5.7) negatif bir öğe içerir: –3 (bu satır dikkate alınırken bu satırın serbest sayısı dikkate alınmaz) karakteristik). Bu nedenle 8. aşamaya geçiyoruz.

Aşama 8: Çözücü unsurun belirlenmesi.

8.1. Çözünürlük sütununun tanımı.

Bulunan temel çözüm kabul edilebilir; amaç fonksiyonu satırındaki negatif elemanlı sütunları belirleriz (serbest sayılar sütunu hariç). Tablo 5.7'ye göre böyle bir sütun vardır: " x5" Bu nedenle izin verildiği gibi kabul ediyoruz.

8.2. Etkinleştirme dizesinin tanımı.

Tablo 5.8'de pozitif değerlendirme ilişkilerinin elde edilen değerlerine göre minimum "" çizgisine karşılık gelen ilişkidir. x4" Bu nedenle izin verildiği gibi kabul ediyoruz.

Tablo 5.8

Simpleks tabloIII yinelemeler

Aşama 9: Simpleks tablonun dönüştürülmesi.

Simpleks tablonun (Tablo 5.8) dönüşümleri önceki yinelemedekiyle aynı şekilde gerçekleştirilir. Simpleks tablonun elemanlarının dönüşümlerinin sonuçları Tablo 5.9'da verilmiştir.

IV yineleme

Aşama 1: yeni bir simpleks tablonun oluşturulması.

Önceki yinelemenin simpleks dönüşümlerinin sonuçlarına dayanarak yeni bir simpleks tablosu derliyoruz:

Tablo 5.9

Simpleks tabloIV yinelemeler

Aşama 2: Temel çözümün belirlenmesi.

Simpleks dönüşümler sonucunda Tablo 5.9'a göre yeni bir temel çözüm elde edilmiş olup, çözüm aşağıdaki gibidir;

Aşama 3: kısıtlama sisteminin uyumluluğunun kontrol edilmesi.

Tablo 5.9'daki özellik 1'e göre kısıtlama sisteminin tutarsızlığı tespit edilmemiştir.

Aşama 4: amaç fonksiyonunun sınırlılığının kontrol edilmesi.

Tablo 5.9'da 2. kritere göre amaç fonksiyonunun sınırsızlığı ortaya çıkmamıştır.

Aşama 5: Bulunan temel çözümün kabul edilebilirliğinin kontrol edilmesi.

Kriter 3'e göre bulunan temel çözüm, olumsuz bileşenler içermediğinden kabul edilebilir.

Aşama 6: Bulunan temel çözümün optimalliğinin kontrol edilmesi.

Özellik 4'e göre bulunan temel çözüm optimaldir, çünkü simpleks tablonun amaç fonksiyonu satırında hiçbir negatif öğe yoktur (Tablo 5.9) (bu özellik dikkate alınırken bu satırın serbest sayısı dikkate alınmaz) .

Aşama 7: Çözümün alternatifliğinin kontrol edilmesi.

Bulunan çözüm benzersizdir, çünkü amaç fonksiyonu satırında sıfır eleman yoktur (Tablo 5.9) (bu özellik dikkate alınırken bu satırın serbest sayısı dikkate alınmaz).

Cevap: optimum değer Söz konusu problemin amaç fonksiyonu =24'te elde edilir.

Örnek 5.2. Yukarıdaki doğrusal programlama problemini amaç fonksiyonunun en aza indirilmesi koşuluyla çözün:

Çözüm:

BEN yineleme:

Aşama 1: Başlangıç ​​simpleks tablosunun oluşturulması.

Orijinal doğrusal programlama problemi standart biçimde verilmiştir. Eşitsizlik kısıtlamalarının her birine negatif olmayan ek bir değişken ekleyerek bunu kanonik forma getirelim;

Ortaya çıkan denklem sisteminde izin verilen (temel) değişkenler olarak alıyoruz x3, x4, x5, x6, o zaman serbest değişkenler şöyle olacaktır: x1,x2. Temel değişkenleri serbest değişkenler cinsinden ifade edelim.

Kısa teori

Doğrusal programlama problemlerinin çözümü için birçok farklı yöntem önerilmiştir. Ancak simpleks yönteminin aralarında en etkili ve evrensel olduğu ortaya çıktı. Bazı problemleri çözerken diğer yöntemlerin daha etkili olabileceğini unutmamak gerekir. Örneğin iki değişkenli bir ZLP için en uygun yöntem dir ve çözümü için potansiyel yöntem kullanılır. Simpleks yöntemi temeldir ve kanonik biçimdeki herhangi bir PPL'ye uygulanabilir.

Doğrusal programlamanın ana teoremi ile bağlantılı olarak, LLP'yi herhangi bir sayıda değişkenle çözmenin aşağıdaki yolu düşünmesi doğal olarak ortaya çıkar. Bir şekilde planların çokyüzlüsünün tüm uç noktalarını bulun (bunlardan daha fazlası yoktur) ve amaç fonksiyonunun değerlerini bunlarla karşılaştırın. Nispeten az sayıda değişken ve kısıtlamayla bile böyle bir çözüm pratik olarak imkansızdır, çünkü uç noktaları bulma süreci, orijinal sorunu çözme zorluğuyla karşılaştırılabilir ve dahası, planların çokyüzlüsünün uç noktalarının sayısı çok büyük olduğu ortaya çıktı. Bu zorluklarla bağlantılı olarak uç noktaların rasyonel olarak numaralandırılması sorunu ortaya çıktı.

Simpleks yönteminin özü aşağıdaki gibidir. Eğer bir uç nokta ve amaç fonksiyonunun değeri biliniyorsa, o zaman amaç fonksiyonunun en kötü değeri aldığı tüm uç noktalara açıkça ihtiyaç duyulmaz. Bu nedenle doğal arzu, belirli bir uç noktadan kenara bitişik daha iyi bir noktaya, oradan daha iyi (daha kötü olmayan) bir noktaya vb. geçmenin bir yolunu bulmaktır. Bunu yapmak için, şunu gösteren bir işarete sahip olmanız gerekir: Belirli bir uç noktadan daha iyi bir uç nokta yoktur. Bu ne genel fikir ZLP'yi çözmek için şu anda en yaygın olarak kullanılan simpleks yöntemi (planın sıralı iyileştirme yöntemi). Yani cebirsel açıdan simpleks yöntemi şunu varsayar:

1. bir başlangıç ​​referans planı bulma yeteneği;
2. referans planının optimallik işaretinin varlığı;
3. en kötü olmayan referans planına geçme yeteneği.

Sorun çözümü örneği

Sorun durumu

Bir ticari işletmenin üç grup malı satabilmesi için , , , adet miktarında üç çeşit sınırlı maddi ve parasal kaynağı vardır. Aynı zamanda 1 grup malın 1 bin rubleye satışı için. emtia cirosu, birinci türden kaynağı birim sayısıyla, ikinci türün kaynağını birim sayısıyla, üçüncü türün kaynağını birim sayısıyla tüketir. 1 bin ruble karşılığında 2 ve 3 grup malın satışı için. Emtia cirosu, birinci türdeki kaynağa göre, birim miktarında, ikinci tür kaynaklara göre, birim miktarında, üçüncü tür kaynaklara göre, birim miktarında harcanır. 1 bin ruble karşılığında üç grup malın satışından elde edilen kar. ciro sırasıyla bin ruble.

• Ticari işletmenin kârını en üst düzeye çıkarmak için planlanan ticaret cirosunun hacmini ve yapısını belirleyin.
• Simpleks yöntemle çözülen doğrudan ciro planlaması problemi için ikili doğrusal programlama problemi oluşturun.
• Doğrudan ve ikili problemlerin eşlenik değişken çiftlerini oluşturun.
• Eşlenik değişken çiftlerine göre, doğrudan problemin çözümünden, mal satışına harcanan kaynakların tahmin edildiği ikili problemin çözümü elde edilir.

Oturuma kabulünüz bir dizi problemin çözülmesine bağlıysa ve hesaplamalar için oturmaya ne zamanınız ne de isteğiniz varsa, web sitesinin yeteneklerini kullanın. Görevleri sıralamak yalnızca birkaç dakika sürer. Doğrusal programlama problemlerine çözümler satın alın sayfasında detaylı olarak (nasıl talep gönderilir, fiyatlar, koşullar, ödeme yöntemleri) okuyabilirsiniz...

Sorun çözümü

Model oluşturma

Sırasıyla 1., 2. ve üçüncü tür malların cirosunu belirtelim.

Daha sonra elde edilen karı ifade eden amaç fonksiyonu:

Maddi ve parasal kaynaklar üzerindeki sınırlamalar:

Ayrıca görevin anlamına göre

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

ZLP'nin kanonik biçimine indirgeme

Sorunu kanonik forma getirelim. Eşitsizlikleri eşitliklere dönüştürmek için ek değişkenler sunuyoruz. Değişkenler 1 katsayısı ile kısıtlamalara dahil edilir. Tüm ek değişkenleri sıfıra eşit bir katsayı ile amaç fonksiyonuna dahil ederiz.

Sağ taraf negatif değilse kısıtlamanın tercih edilen bir biçimi vardır sol taraf bire eşit bir katsayıya sahip bir değişkene ve sıfıra eşit bir katsayıya sahip geri kalan eşitlik kısıtlamalarına sahiptir. Bizim durumumuzda 1., 2., 3. kısıtlamalar karşılık gelen temel değişkenlerle tercih edilen bir forma sahiptir.

Simpleks yöntemini kullanarak çözüm

0. yinelemenin simpleks tablosunu dolduruyoruz.

Problemi maksimuma çözdüğümüz için, problemi maksimuma çözerken indeks doğrusunda negatif sayıların bulunması, optimal çözümü elde edemediğimizi ve 0. iterasyondaki tablodan 0. iterasyona geçmemiz gerektiğini gösterir. bir sonraki.

Bir sonraki iterasyona şu şekilde geçiyoruz:

Öndeki sütun şuna karşılık gelir:

Anahtar satır, serbest üyelerin ve ön sütundaki üyelerin minimum oranı (basit ilişkiler) ile belirlenir:

Anahtar sütun ile anahtar satırın kesişiminde etkinleştirici öğeyi, yani 7'yi buluruz.

Şimdi 1. yinelemeyi derlemeye başlıyoruz. Birim vektör yerine vektörü tanıtıyoruz.

Yeni tabloda 1 yazdığımız etkinleştirme elemanı yerine anahtar sütununun diğer tüm elemanları sıfırdır. Anahtar dize öğeleri etkinleştirme öğesine bölünmüştür. Tablonun diğer tüm elemanları dikdörtgen kuralı kullanılarak hesaplanır.

1. yinelemenin tablosunu alıyoruz:

1. yinelemenin anahtar sütunu şuna karşılık gelir: .

Anahtar çizgiyi buluyoruz, bunun için şunu tanımlıyoruz:

Anahtar sütun ile anahtar satırın kesişiminde etkinleştirici öğeyi buluruz, yani. 31/7.

Vektör tabandan türetilir ve vektör tanıtılır.

2. yinelemenin tablosunu alıyoruz:

İndeks satırında tüm terimler negatif değildir, dolayısıyla doğrusal programlama problemine aşağıdaki çözüm elde edilir (bunu serbest terimler sütunundan yazıyoruz):

Dolayısıyla 7,1 bin ruble satmak gerekiyor. 1. tip mallar ve 45,2 bin ruble. 3. tip mallar. 2. tip bir ürünü satmak karlı değildir. Bu durumda kar maksimum olacak ve 237,4 bin ruble olacak. Optimum plan uygulanırsa 3. tipte kalan kaynak 701 birim olacaktır.

Çift LP sorunu

İkili problemin bir modelini yazalım.

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

1) doğrudan problem maksimuma çözülürse, ikili problem minimuma çözülür ve bunun tersi de geçerlidir;

2) maksimum problemde eşitsizlik kısıtları ≤, minimizasyon probleminde ise ≥ anlamını taşır;

3) doğrudan problemin her kısıtlaması ikili problemin bir değişkenine karşılık gelir ve bunun tersi de geçerlidir, ikili problemin her kısıtlaması doğrudan problemin bir değişkenine karşılık gelir;

4) ikili problemin kısıtlama sistemi matrisi, orijinal problemin kısıtlama sistemi matrisinden aktarım yoluyla elde edilir;

5) doğrudan problemin kısıtlamalar sisteminin serbest terimleri, ikili problemin amaç fonksiyonunun karşılık gelen değişkenlerinin katsayılarıdır ve bunun tersi de geçerlidir;

6) eğer doğrudan problemin değişkenine negatif olmama koşulu empoze edilirse, o zaman ikili problemin karşılık gelen kısıtı bir eşitsizlik kısıtı olarak yazılır, eğer değilse o zaman bir eşitlik kısıtı olarak yazılır;

7) Doğrudan problemin herhangi bir kısıtlaması eşitlik olarak yazılırsa, ikili problemin karşılık gelen değişkenine negatif olmama koşulu getirilmez.

Orijinal problemin matrisini değiştiriyoruz:

Sorunu kanonik 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ıtlamaların sol taraflarına ek değişkenler ekleyerek eşitlikler elde ediyoruz.

Çift LP probleminin çözümü

Orijinal ve ikili problemin değişkenleri arasındaki yazışma:

Simpleks tabloya dayanarak ikili doğrusal programlama probleminin aşağıdaki çözümü elde edildi (en alt satırdan yazıyoruz):

Bu nedenle, birinci türün kaynağı en kıt olanıdır. Puanı maksimum ve eşittir. Üçüncü türün kaynağı gereksizdir - ikili değeri sıfırdır. Satılan 2. grup malların her ek birimi optimal karı azaltacaktır.
İki değişkenli bir doğrusal programlama problemini (LPP) çözmek için grafiksel bir yöntem ele alınmıştır. Görevin bir örneği verilmiştir detaylı açıklama Bir çizim oluşturmak ve bir çözüm bulmak.

Ulaşım sorununun çözümü
Ulaştırma problemi, matematiksel modeli ve çözüm yöntemleri ayrıntılı olarak ele alınır; minimum eleman yöntemiyle referans planının bulunması ve potansiyel yöntemle en uygun çözümün aranması.

Belirsizlik koşullarında karar verme
Belirsizlik koşulları altında istatistiksel bir matris oyununun çözümü Wald, Savage, Hurwitz, Laplace ve Bayes kriterleri kullanılarak değerlendirilmektedir. Örnek bir problem kullanılarak ödeme matrisi ve risk matrisinin oluşturulması ayrıntılı olarak gösterilmiştir.

Doğrusal programlama problemini çözmek gerekir.

Amaç fonksiyonu:

2x 1 +5x 2 +3x 3 +8x 4 → dk

Sınırlayıcı koşullar:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

Kısıtlama sistemini kanonik forma getirelim; bunun için ek değişkenlerin eklenmesiyle eşitsizliklerden eşitliklere geçmek gerekir.

Problemimiz bir minimizasyon problemi olduğundan onu maksimum arama problemine dönüştürmemiz gerekiyor. Bunu yapmak için amaç fonksiyonunun katsayılarının işaretlerini zıt işaretlerle değiştiririz. İlk eşitsizliğin elemanlarını değiştirmeden yazıyoruz, ek bir x 5 değişkeni ekliyoruz ve “≤” işaretini “=” olarak değiştiriyoruz. İkinci ve üçüncü eşitsizlikler “≥” işaretli olduğundan katsayılarının işaretlerini ters çevirerek bunlara sırasıyla x 6 ve x 7 ek değişkenlerini eklemek gerekir. Sonuç olarak, eşdeğer bir sorunla karşılaşıyoruz:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

İlk simpleks tablosunun oluşumuna geçiyoruz. Tablonun F satırı, amaç fonksiyonunun katsayılarını içerir. karşıt işaret.

Serbest terimler sütununda negatif eleman bulunmadığından kabul edilebilir bir çözüm bulunmuştur. F satırı negatif elemanlar içermektedir, bu da ortaya çıkan çözümün optimal olmadığı anlamına gelmektedir. Baş sütunu tanımlayalım. Bunu yapmak için, F satırında maksimum modüle sahip negatif elemanı bulacağız - bu -1,988'dir. Öndeki satır, serbest terimin ön sütunun karşılık gelen elemanına oranının minimum olduğu satır olacaktır. Baştaki satır X2'dir ve baştaki eleman: 0,313'tür.

F dizisinde negatif öğe olmadığından şunu bulduk: optimal çözüm. Asıl görev minimumu bulmak olduğundan, en iyi çözüm F dizisinin ters işaretle alınan serbest terimi olacaktır. F=1.924
değişken değerleri eşit olan: x 3 =0,539, x 1 =0,153. x 2 ve x 4 değişkenleri tabana dahil edilmediğinden x 2 =0 x 4 =0.

Burada, simpleks yöntemini kullanarak problem çözme algoritmasını anlamak için ayrıntılı açıklamalarla birlikte simpleks yöntemini (applet çözümüne benzer) kullanan iki problemin manuel (applet değil) çözümü bulunmaktadır. İlk problem sadece “≤” eşitsizlik işaretlerini içeriyor (başlangıç ​​temelli problem), ikincisi “≥”, “≤” veya “=” (yapay temelli problem) işaretlerini içerebilir, farklı şekilde çözülürler.

Simpleks yöntemi, bir problemi başlangıç ​​esasına göre çözme

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

Sorunu yazalım kanonik form, yani Eşitsizlik kısıtlamalarını eşitlikler biçiminde yeniden yazıyoruz; bilanço değişkenler:

Bu sistem temelleri (temel s 1, s 2, s 3, her biri 1 katsayısı ile sistemin sadece bir denkleminde yer alan), x 1 ve x 2 serbest değişkenleri olan bir sistemdir. Simpleks yöntemi kullanılarak çözülecek problemler aşağıdaki iki özelliğe sahip olmalıdır: - Kısıtlamalar sistemi, temeli olan bir denklemler sistemi olmalıdır; -Sistemdeki tüm denklemlerin serbest terimleri negatif olmamalıdır.

Ortaya çıkan sistem, temeli olan bir sistemdir ve serbest şartları negatif değildir, dolayısıyla uygulayabiliriz. simpleks yöntemi. Sorunu çözmek için ilk simpleks tabloyu (Yineleme 0) oluşturalım. simpleks yöntemi, yani amaç fonksiyonunun katsayılarının bir tablosu ve karşılık gelen değişkenler için bir denklem sistemi. Burada “BP” temel değişkenlerin sütununu, “Çözüm” ise sistem denklemlerinin sağ taraflarındaki sütunu ifade eder. Çözüm optimal değil çünkü z satırında negatif katsayılar vardır.

simpleks yöntemi yinelemesi 0

Çözümü iyileştirmek için bir sonraki yinelemeye geçelim simpleks yöntemi aşağıdaki simpleks tabloyu elde ederiz. Bunu yapmak için seçmeniz gerekir sütunu etkinleştir, yani simpleks yönteminin bir sonraki yinelemesinde temele dahil edilecek bir değişken. Z satırındaki (maksimum problemde) en büyük mutlak negatif katsayıya göre seçilir - simpleks yönteminin ilk yinelemesinde bu, x 2 sütunudur (katsayı -6).

Daha sonra seçin dizeyi etkinleştir, yani simpleks yönteminin bir sonraki yinelemesinde temel oluşturacak bir değişken. "Karar" sütununun, çözünürlük sütununun karşılık gelen pozitif öğelerine ("Oran" sütunu) en küçük oranıyla seçilir - ilk yinelemede bu, s 3 satırıdır (katsayı 20).

İzin verici unsurçözümleme sütunu ile çözümleme satırının kesişme noktasındadır, 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-dizgesinde aranmadığını unutmayın; buraya bir tire “-” konur. Eğer aynı minimal ilişkiler varsa bunlardan herhangi biri seçilir. Çözünürlük sütunundaki tüm katsayılar 0'dan küçük veya ona eşitse, problemin çözümü sonsuzdur.

Aşağıdaki “Yineleme 1” tablosunu dolduralım. Bunu “Yineleme 0” tablosundan alacağız. Daha sonraki dönüşümlerin amacı x2 çözünürlük sütununu bir birim sütuna dönüştürmektir (çözünürlük öğesi yerine bir ve geri kalan öğeler yerine sıfırlar).

1) “Yineleme 1” tablosunun satır x 2'sini hesaplayın. Öncelikle “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ölüyoruz, “Yineleme 1” tablosunda satır x 2’yi elde ediyoruz . Çünkü bu durumda çözümleme elemanı 1'e eşitse, "Yineleme 0" tablosunun 3. satırı "Yineleme 1" tablosunun x 2 satırıyla çakışacaktır. Aldığımız Iteration 1 tablosunun satır x 2'si 0 1 0 0 1 20, Iteration 1 tablosunun geri kalan satırları bu satırdan elde edilecek ve Iteration 0 tablosunun satırları aşağıdaki gibi olacaktır:

2) “Yineleme 1” tablosunun z satırının hesaplanması. Yineleme 0 tablosunun x2 sütunundaki ilk satırdaki (z satırı) -6 yerine, Yineleme 1 tablosunun ilk satırında 0 bulunmalıdır. Bunu yapmak için, "Yineleme 1" 0 1 0 0 1 20 tablosunun x 2 satırının tüm elemanlarını 6 ile çarpın, 0 6 0 0 6 120 elde ederiz ve bu satırı ilk satıra (z - satır) ekleriz "Yineleme 0" -4 -6 0 0 0 0 tablosundan -4 0 0 0 6 120 elde ederiz. X 2 sütununda sıfır 0 görünür, hedefe ulaşılır. Çözünürlük sütunu x 2'nin öğeleri kırmızı renkle vurgulanır.

3) “Yineleme 1” tablosunun 1. satırının hesaplanması. “Yineleme 0” tablosunun s 1 satırındaki 1 yerine “Yineleme 1” tablosunda 0 olmalıdır. Bunu yapmak için, "Yineleme 1" 0 1 0 0 1 20 tablosunun x 2 satırının tüm elemanlarını -1 ile çarpın, 0 -1 0 0 -1 -20 elde edin ve bu satırı s 1 - satırıyla ekleyin "Yineleme 0" 2 1 1 0 0 64 tablosunda, 2 0 1 0 -1 44 satırını elde ederiz. x 2 sütununda gerekli 0'ı elde ederiz.

4) “Yineleme 1” tablosunun 2. satırını hesaplayın. "Yineleme 0" tablosunun 2. satırındaki 3. yerde "Yineleme 1" tablosunda 0 olmalıdır. Bunu yapmak için, "Yineleme 1" 0 1 0 0 1 20 tablosunun x 2 satırının tüm elemanlarını -3 ile çarpın, 0 -3 0 0 -3 -60 elde ederiz ve bu satırı s 1 - satır ile ekleriz "Yineleme 0" tablosunda 1 3 0 1 0 72, 1 0 0 1 -3 12 satırını elde ederiz. x 2 sütununda gerekli 0 elde edilir. “Yineleme 1” tablosundaki x 2 sütunu haline gelmiştir. Bir birim, biri 1 ve geri kalanı 0'dan oluşur.

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

Yeni satır = Eski satır – (Eski satır çözünürlük sütunu katsayısı)*(Yeni çözünürlük satırı).

Örneğin, bir z-string'i için elimizde:

Eski z-string (-4 -6 0 0 0 0) -(-6)*Yeni çözümleme dizisi -(0 -6 0 0 -6 -120) =Yeni z-string (-4 0 0 0 6 120).

Aşağıdaki tablolarda tablo elemanlarının yeniden hesaplanması benzer şekilde yapıldığı için bunu atladık.

simpleks yöntemi yinelemesi 1

x 1 sütununun çözümlenmesi, s 2 satırının çözümlenmesi, s 2 tabanının çözülmesi, x 1 tabanının çözülmesi. Tamamen aynı şekilde, z satırındaki tüm pozitif katsayıları içeren bir tablo elde edene kadar geri kalan simpleks tabloları elde ederiz. Bu optimal bir tablonun işaretidir.

simpleks yöntemi yinelemesi 2

Sütun s 3 çözümlendiğinde, satır s 1, s 1 çözümlendiğinde tabandan çıkar, s 3 tabana girer.

simpleks yöntemi yinelemesi 3

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

11.4. ÇİFT SIMPLEX YÖNTEMİ

Önceki paragrafların sonuçlarından, orijinal soruna bir çözüm elde etmek için ikili çözüme gidilebileceği ve onun optimal planının tahminlerini kullanarak orijinal soruna en uygun çözümün belirlenebileceği anlaşılmaktadır.

Dual probleme geçiş gerekli değildir, çünkü ilk simpleks tabloyu birim ek bazında ele alırsak, orijinal problemin sütunlara, dual problemin ise satırlara yazıldığını fark etmek kolaydır.

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

Dualiteyi hesaba katarak bu durumu göz önünde bulundurarak şunu yazabiliriz:

.

Böylece eğer, O . Bu, doğrudan problemin çözümü optimalin altında olduğunda, ikili problemin çözümünün mümkün olmadığı anlamına gelir. Diğer tarafta . Buradan, doğrudan problemin optimal çözümünün, ikili problemin kabul edilebilir bir çözümüne karşılık geldiği sonucu çıkmaktadır.

Bu, doğrusal programlama problemlerini çözmek için, ilk önce kabul edilemez ancak "optimumdan daha iyi" bir çözüm üreten yeni bir yöntem geliştirmeyi mümkün kıldı (olağan simpleks yönteminde, ilk önce bulunanlar). kabul edilebilir, Ancak optimalin altındaçözüm). Yeni yöntem, isminde ikili simpleks yöntemi, çözümün optimalliği için koşulların yerine getirilmesini ve uygulanabilir çözüm bölgesine sistematik "yakınlaştırılmasını" sağlar. Ortaya çıkan çözüm uygun olduğu ortaya çıktığında, bu çözüm de optimal olduğundan, yinelemeli hesaplama süreci sona erer.

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

Örnek. Bir fonksiyonun minimumunu bulun

kısıtlamalar altında

.

Kanonik forma geçelim:

kısıtlamalar altında

İlk simpleks tablo şu şekildedir:

İlk temel çözümoptimal, ancak kabul edilemez.

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

Kabul edilebilirlik koşulu. En büyük değişken dışlanan değişken olarak seçilir. mutlak değer Negatif temel değişken (alternatifler varsa seçim keyfi olarak yapılır). Temel değişkenlerin tümü negatif değilse, ortaya çıkan çözüm mümkün ve optimal olduğundan hesaplama işlemi sona erer.

Durum optimallik. Temele dahil edilen değişken temel olmayan değişkenler arasından aşağıdaki gibi seçilir. Sol taraftaki katsayıların oranları hesaplanır-hariç tutulan değişkenle ilişkili denklemin karşılık gelen katsayılarına ait denklemler. Olumlu veya olumsuz ilişkiler sıfır değer paydalar dikkate alınmaz. Minimizasyon probleminde girdi değişkeni belirlenen oranların en küçüğüne, maksimizasyon probleminde ise mutlak değer olarak en küçük olan orana (alternatifler varsa seçim keyfi olarak yapılır) karşılık gelmelidir. 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 temele dahil edilecek ve hariç tutulacak değişkenleri seçtikten sonra, bir simpleks tablonun satırlarını dönüştürme olağan işlemi gerçekleştirilir.

Bu örnekte, hariç tutulan değişken. Yeni temel değişkenin belirlenmesi amacıyla hesaplanan oranlar aşağıdaki tabloda yer almaktadır:

Dahil edilen değişken seçilir X 2. Sonraki dize dönüşümü yeni bir simpleks tabloyla sonuçlanır:

Yeni çözüm aynı zamanda optimal, ancak yine de kabul edilemez. Yeni bir dışlanan değişken olarak seçiyoruz (keyfi olarak) X 3. Dahil edilecek değişkeni tanımlayalım.