Simpleks yöntemi basit bir çözüm örneğidir. Simplex yöntemi, problem çözme örnekleri

Problemi simpleks yöntemle çözmenin bir örneği ve ayrıca bir çözme örneği ele alınır. ikili problem.

Görev

Üç 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 harcanır, birinci türdeki kaynak a 12 = 3, a 13 = 6 birim, ikinci türdeki kaynak 22 = 2, a 23 = 4 birim, kaynak 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 problemler.
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;

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.

Optimizasyon problemlerini çözme yöntemlerinden biri ( genellikle minimum veya maksimumu bulmakla ilişkilendirilir) doğrusal programlama denir. tek yönlü yöntem doğrusal programlama problemlerini çözmek için bir dizi algoritma ve yöntem içerir. İlk verilerin kaydedilmesini ve özel bir tabloda yeniden hesaplanmasını içeren bu yöntemlerden birine denir. tablosal simpleks yöntemi.

Çözüm örneğinde tablo tek yönlü yönteminin algoritmasını düşünün üretim görevi , maksimum kar sağlayan bir üretim planı bulmaya indirgenir.

Simplex yöntemi için problemin ilk verileri

İşletme, 3 makinede işleyerek 4 tip ürün üretiyor.

Ürünlerin makinelerde işlenmesi için süre limitleri (dk./adet) matris A ile verilmiştir:

Makine çalışma süresi fonu (min.) matris B'de verilmiştir:

Ürünün her bir biriminin (ruble/adet) satışından elde edilen kar, C matrisiyle verilir:

Üretim görevinin amacı

İşletmenin karının maksimize edileceği bir üretim planı hazırlayın.

Problemin tabular simpleks yöntemi ile çözümü

(1) X1, X2, X3, X4 her türden planlanan ürün sayısını göstersin. Ardından istenen plan: ( X1, X2, X3, X4)

(2) Plan kısıtlamalarını bir denklem sistemi şeklinde yazalım:

(3) O zaman hedef kar:

Yani, üretim planının uygulanmasından elde edilen kar maksimum olmalıdır.

(4) Ortaya çıkan sorunu koşullu bir ekstremum için çözmek için, eşitsizlikler sistemini sistemle değiştiririz. lineer denklemler içine negatif olmayan ek değişkenler ekleyerek ( X5, X6, X7).

(5) Aşağıdakileri kabul ediyoruz referans planı:

X1=0, X2=0, X3=0, X4=0, X5=252, X6=144, X7=80

(6) içine verileri girelim tek yönlü tablo:

Son satırda amaç fonksiyonunun katsayılarını ve değerinin kendisini ters işaretle giriyoruz;

(7) seçin son satır En büyük (modulo) negatif bir sayı.

bilgi işlem b = N / Elements_of_chosen_column

b'nin hesaplanan değerleri arasından seçiyoruz en az.

Seçilen sütun ve satırın kesişimi bize çözümleyici bir öğe verecektir. Tabanı, etkinleştiren öğeye karşılık gelen bir değişkene değiştiririz ( X5'ten X1'e).

• Enable öğesinin kendisi 1 olur.
• İzin verilen çizginin öğeleri için - a ij (*) = a ij / RE ( yani, her bir öğeyi etkinleştiren öğenin değerine böleriz ve yeni veriler elde ederiz.).
• Bir çözümleme sütununun öğeleri için, basitçe sıfırlanırlar.
• Tablonun geri kalan öğeleri dikdörtgen kuralına göre yeniden hesaplanır.

bir ij (*) = bir ij - (A * B / RE)

Gördüğünüz gibi, yeniden hesaplanan mevcut hücreyi ve etkinleştirme öğesinin bulunduğu hücreyi alıyoruz. Dikdörtgenin zıt köşelerini oluştururlar. Ardından, bu dikdörtgenin diğer 2 köşesinin hücrelerinden gelen değerleri çarpıyoruz. Bu iş ( A * B) çözümleme elemanına bölün ( TEKRAR). Ve mevcut yeniden hesaplanan hücreden çıkarın ( aij) Ne oldu. Yeni bir değer elde ediyoruz - bir ij (*).

(9) Son satırı tekrar kontrol edin ( C) Açık negatif sayıların varlığı. Hiçbiri yoksa, en uygun plan bulundu, sorunu çözmenin son aşamasına geçiyoruz. Varsa, plan henüz optimal değildir ve tek yönlü tablonun yeniden hesaplanması gerekir.

Yine son satırda olduğumuz için negatif sayılar, yeni bir hesaplama yinelemesine başlarız.

(10) Son satırda hiçbir olumsuz unsur bulunmadığından, bu, en uygun üretim planını bulduğumuz anlamına gelir! Yani: "Temel" sütununa taşınan ürünleri üreteceğiz - X1 ve X2. Her çıktı biriminin üretiminden elde edilen karı biliyoruz ( matris C). Ürün 1 ve 2'nin bulunan çıktı hacimlerini 1 parça başına kârla çarpmaya devam ediyor, finali alıyoruz ( maksimum! ) belirli bir üretim planı kapsamında kâr.

CEVAP:

X1=32 adet, X2=20 adet, X3=0 adet, X4=0 adet

P \u003d 48 * 32 + 33 * 20 \u003d 2.196 ruble.

Galyautdinov R.R.

© Materyalin kopyalanmasına yalnızca doğrudan bir köprü belirtmeniz durumunda izin verilir.

Bu yöntem, bir doğrusal programlama probleminin referans çözümlerinin amaçlı olarak sıralanması yöntemidir. Optimum çözümü bulmak veya optimal çözüm olmadığını belirlemek için sınırlı sayıda adıma izin verir.

1. Optimum referans çözümü bulmak için bir yöntem belirleyin
2. Amaç fonksiyonunun değerinin optimale daha yakın olacağı bir referans çözümden diğerine geçiş yöntemini belirtin, yani. referans çözümü iyileştirmenin bir yolunu gösterir
3. Optimal çözüme ilişkin destek çözümlerinin numaralandırılmasını zamanında durdurmanıza veya optimum çözüm olmadığı sonucuna varmanıza izin veren kriterleri belirleyin.

Doğrusal programlama problemlerini çözmek için tek yönlü yöntemin algoritması

1. Sorunu kanonik forma getirin
2. "Birim bazında" bir başlangıç ​​referans çözümü bulun (referans çözüm yoksa, kısıtlama sisteminin uyumsuzluğundan dolayı sorunun çözümü yoktur)
3. Referans çözüm temelinde vektör açılımlarının tahminlerini hesaplayın ve tek yönlü yöntem tablosunu doldurun
4. Optimal çözümün teklik kriteri sağlanırsa, problemin çözümü sona erer.
5. Bir optimal çözüm kümesinin var olma koşulu sağlanıyorsa, o zaman basit numaralandırma ile tüm optimal çözümler bulunur.

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

Simplex yöntemini kullanarak sorunu çözün:

Çözüm:

Sorunu kanonik forma getiriyoruz.

Bunun için Sol Tarafİlk eşitsizlik kısıtlamasında, +1 katsayılı ek bir x 6 değişkeni sunuyoruz. x 6 değişkeni, amaç fonksiyonuna sıfır katsayısı ile dahil edilir (yani dahil edilmez).

Biz:

Başlangıç ​​referans çözümünü buluyoruz. Bunu yapmak için, serbest (çözümlenmemiş) değişkenleri sıfır x1 = x2 = x3 = 0'a eşitliyoruz.

biz alırız Referans çözümü X1 = (0.0.0.24.30.6) birim bazında B1 = (A4, A5, A6).

Hesaplamak vektör ayrıştırma tahminleri aşağıdaki formüle göre referans çözüm temelinde koşullar:

Δ k \u003d C b X k - c k

• C b = (с 1 , с 2 , ... , с m) temel değişkenli amaç fonksiyonu katsayılarının vektörüdür
• X k = (x 1k , x 2k , ... , x mk) ilgili A k vektörünün referans çözüm bazında genişleme vektörüdür
• C k - x k değişkeni için amaç fonksiyonunun katsayısı.

Tabana dahil edilen vektörlerin tahminleri her zaman sıfıra eşittir. Referans çözüm, açılım katsayıları ve koşul vektörlerinin açılım tahminleri, referans çözümün temeli cinsinden yazılır. tek yönlü tablo:

Tablonun üstünde, tahminlerin hesaplanmasında kolaylık olması için amaç fonksiyonunun katsayıları yazılmıştır. İlk "B" sütunu, referans çözüm temelinde yer alan vektörleri içerir. Bu vektörlerin yazılma sırası, kısıtlama denklemlerinde izin verilen bilinmeyenlerin sayısına karşılık gelir. "B ile" tablosunun ikinci sütununda amaç fonksiyonunun katsayıları temel değişkenlerle aynı sırada yazılır. -de doğru konum Amaç fonksiyonunun katsayıları sütunundaki "Cb" birim vektörlerinin tahminleri temelinde yer alır, her zaman sıfıra eşittir.

"A 0 "sütununda Δ k tahminlerini içeren tablonun son satırında amaç fonksiyonunun değerleri referans çözüm Z(X 1) üzerine yazılır.

Başlangıç ​​referans çözümü optimal değildir, çünkü maksimum problemde Aı ve A3 vektörleri için Aı = -2, A3 = -9 tahminleri negatiftir.

Referans çözüm iyileştirme teoremine göre, maksimum problemdeki en az bir vektörün negatif bir tahmini varsa, amaç fonksiyonunun değerinin daha büyük olacağı yeni bir referans çözüm bulmak mümkündür.

İki vektörden hangisinin amaç fonksiyonunda daha büyük bir artışa yol açacağını belirleyelim.

Amaç fonksiyonu artışı aşağıdaki formülle bulunur: .

Aşağıdaki formülü kullanarak birinci ve üçüncü sütunlar için θ 01 parametresinin değerlerini hesaplıyoruz:

l = 1 için θ 01 = 6, l = 1 için θ 03 = 3 elde ederiz (tablo 26.1).

İlk vektör ΔZ 1 = - 6 * (- 2) = 12 tabana eklendiğinde ve üçüncü vektör ΔZ 3 = - 3 * (- 9) = 27 olduğunda amaç fonksiyonunun artışını buluyoruz.

Bu nedenle, optimal çözüme daha hızlı bir yaklaşım için, θ 03 parametresinin minimumuna ilk satırda ulaşıldığından, A6 tabanının ilk vektörü yerine referans çözümün tabanına A3 vektörünü sokmak gerekir. (l = 1).

X13 = 2 elemanı ile Jordan dönüşümünü gerçekleştiriyoruz, B2 = (A3, A4, A5) bazında ikinci referans çözümü X2 = (0.0.3.21.42.0) elde ediyoruz. (tablo 26.2)

A2 vektörünün negatif bir tahmini Δ2 = - 6 olduğu için bu çözüm optimal değildir. Çözümü iyileştirmek için, A2 vektörünü referans çözümün tabanına dahil etmek gerekir.

Tabandan türetilen vektörün sayısını belirliyoruz. Bunu yapmak için ikinci sütun için θ 02 parametresini hesaplıyoruz, l = 2 için 7'ye eşittir. Bu nedenle, ikinci taban vektörü A4'ü tabandan türetiyoruz. x 22 = 3 elemanı ile Jordan dönüşümünü gerçekleştiriyoruz, X3 = (0.7.10.0.63.0) B2 = (A3, A2, A5) (tablo 26.3) üçüncü referans çözümünü elde ediyoruz.

Bu çözüm tek optimal çözümdür çünkü temele dahil olmayan tüm vektörler için tahminler pozitiftir.

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

Cevap: X = (0.7,10,0.63)'te maksimum Z(X) = 201.

Ekonomik analizde doğrusal programlama yöntemi

Doğrusal programlama yöntemiüretimde kullanılan kaynaklarla (duran varlıklar, malzemeler, işgücü kaynakları) ilgili ciddi kısıtlamalar karşısında en uygun ekonomik çözümün gerekçelendirilmesini mümkün kılar. Bu yöntemin ekonomik analizde uygulanması, esas olarak kuruluşun faaliyetlerinin planlanmasıyla ilgili sorunları çözmemizi sağlar. Bu yöntem, çıktının optimal değerlerinin yanı sıra kuruluşa sunulan üretim kaynaklarının en verimli şekilde kullanılmasına yönelik yönergelerin belirlenmesine yardımcı olur.

Bu yöntemi kullanarak, aşırı değerlerin, yani değişkenlerin fonksiyonlarının maksimum ve minimumunun bulunmasından oluşan uç problemlerin çözümü gerçekleştirilir.

Bu dönem, analiz edilen ekonomik fenomenlerin doğrusal, katı bir şekilde birbirine bağlı olduğu durumlarda bir doğrusal denklem sisteminin çözülmesine dayanmaktadır. işlevsel 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.

Sözde taşıma probleminin doğrusal programlama yöntemi kullanılarak çözümü oldukça yaygındır. Bu görevin içeriği, maksimum sayıda müşteriye hizmet verilmesi gerekiyorsa, araç sayısı, taşıma kapasitesi, çalışma süresi ile ilgili mevcut kısıtlamalar kapsamında araçların işletilmesiyle bağlantılı olarak ortaya çıkan maliyetleri en aza indirmektir. .

Ayrıca, Bu methodçizelgeleme probleminin çözümünde geniş uygulama alanı bulur. Bu görev, hem bu personelin üyeleri hem de kuruluşun müşterileri için en kabul edilebilir olan, bu kuruluşun personelinin çalışma süresinin böyle bir dağılımından oluşur.

Amaç, mevcut personel sayısını ve çalışma saatlerini sınırlarken hizmet verilen müşteri sayısını en üst düzeye çıkarmaktır.

Bu nedenle, doğrusal programlama yöntemi, yerleşim ve kullanım analizinde çok yaygındır. Çeşitli türler kaynakların yanı sıra kuruluşların faaliyetlerini planlama ve tahmin etme sürecinde.

Henüz matematiksel programlama arasındaki ilişki doğrusal olmayan ekonomik olaylara da uygulanabilir. Bu amaçla doğrusal olmayan, dinamik ve konveks programlama yöntemleri kullanılabilir.

Doğrusal olmayan programlama, amaç fonksiyonunun veya kısıtlamaların veya her ikisinin doğrusal olmayan doğasına dayanır. Bu koşullar altında amaç fonksiyonu ve kısıtlama eşitsizliklerinin biçimleri farklı olabilir.

Doğrusal olmayan programlama ekonomik analizde, özellikle kuruluşun faaliyetlerinin etkinliğini ifade eden göstergeler ile bu faaliyetin hacmi, üretim maliyetlerinin yapısı, piyasa koşulları vb. arasındaki ilişkiyi kurarken kullanılır.

Dinamik programlama, bir karar ağacı oluşturmaya dayanır. Bu ağacın her katmanı, önceki kararın sonuçlarını belirlemek ve bu kararın etkisiz varyantlarını ortadan kaldırmak için bir aşama görevi görür. Böylece, dinamik programlama çok adımlı, çok aşamalı bir karaktere sahiptir. Bu tür programlama, ekonomik analizde bulmak için kullanılır. en iyi seçenekler organizasyon hem şimdi hem de gelecekte.

Dışbükey programlama, doğrusal olmayan bir programlama türüdür. Bu tür programlama, kuruluşun faaliyetlerinin sonuçları ile bunlardan kaynaklanan maliyetler arasındaki ilişkinin doğrusal olmayan doğasını ifade eder. Dışbükey (aksi takdirde içbükey) programlama, dışbükey amaç fonksiyonlarını ve dışbükey kısıtlama sistemlerini (özellik noktaları) analiz eder. Maliyetleri en aza indirmek için ekonomik faaliyetin analizinde dışbükey programlama kullanılır ve analiz edilen göstergeleri ters yönde etkileyen faktörlerin etkisi üzerindeki mevcut kısıtlamalar koşullarında geliri en üst düzeye çıkarmak için içbükey programlama kullanılır. Sonuç olarak, ele alınan programlama türleri altında, dışbükey amaç fonksiyonları minimize edilir ve içbükey olanlar maksimize edilir.

Ders 3 Simpleks tablolar. Simplex yönteminin algoritması.

§ 3 BASİT YÖNTEM

3.1. Simplex yönteminin genel fikri. Geometrik yorumlama

Grafik yöntem, çok dar bir doğrusal programlama problemleri sınıfına uygulanabilir: ikiden fazla değişken içermeyen problemleri etkili bir şekilde çözebilir. Doğrusal programlamanın ana teoremleri göz önünde bulundurularak, eğer bir doğrusal programlama probleminin optimal bir çözümü varsa, o zaman çözüm çokyüzlünün en az bir köşe noktasına karşılık gelir ve kabul edilebilir temel çözümlerden en az biriyle çakışır. kısıtlama sistemi. Herhangi bir doğrusal programlama problemini çözmenin bir yolu belirtilmiştir: kısıtlar sisteminin sonlu sayıda uygulanabilir temel çözümlerini sıralamak ve aralarından hedef fonksiyonunun en uygun kararı verdiği birini seçmek. Geometrik olarak bu, çözüm polihedronunun tüm köşe noktalarının numaralandırılmasına karşılık gelir. Böyle bir numaralandırma sonunda (eğer varsa) optimal bir çözüme yol açacaktır, ancak pratik uygulaması çok büyük zorluklarla ilişkilidir, çünkü gerçek problemler için uygulanabilir temel çözümlerin sayısı, sonlu olmasına rağmen, son derece büyük olabilir.

Numaralandırılacak kabul edilebilir temel çözümlerin sayısı, eğer numaralandırma rasgele değil, doğrusal fonksiyondaki değişiklikleri hesaba katarak yapılırsa azaltılabilir, örn. doğrusal fonksiyonun değerleri açısından bir sonraki her çözümün bir öncekinden "daha iyi" (veya en azından "daha kötü değil") olmasını sağlamaya çalışmak (maksimumu bulurken artırın, minimumu bulurken azaltın)
). Böyle bir numaralandırma, optimumu bulmadaki adım sayısını azaltmaya izin verir. Bunu grafiksel bir örnekle açıklayalım.

Uygulanabilir çözümlerin alanı bir çokgen ile temsil edilsin ABCDE. Diyelim ki köşe noktası A orijinal kabul edilebilir temel çözüme karşılık gelir. Rastgele bir numaralandırma, çokgenin beş köşe noktasına karşılık gelen beş uygulanabilir temel çözümü denemek zorunda kalacaktır. Bununla birlikte, çizim, üst kısımdan sonra olduğunu göstermektedir. A bir sonraki zirveye çıkmak avantajlı İÇİNDE, ve sonra optimum noktaya İLE. Beş yerine, yalnızca üç köşe geçilerek lineer fonksiyon sürekli olarak iyileştirildi.

Çözümün sıralı olarak iyileştirilmesi fikri, doğrusal programlama problemlerini çözmek için evrensel bir yöntemin temelini oluşturdu - simpleks yöntemi veya planın art arda iyileştirilmesi yöntemi.

Simplex yönteminin geometrik anlamı, kısıtlama polihedronunun bir köşesinden (başlangıç ​​​​olarak adlandırılır) komşu olana sıralı bir geçişten oluşur; burada doğrusal fonksiyon, en iyi (en azından en kötü değil) değeri alır. sorunun amacı; optimal çözüm bulunana kadar - hedef fonksiyonun optimal değerine ulaşıldığı tepe noktası (sorunun sonlu bir optimumu varsa).

Simpleks yöntemi ilk olarak 1949'da Amerikalı bilim adamı J. Danzig tarafından önerildi, ancak daha 1939'da, yöntemin fikirleri Rus bilim adamı L.V. Kantoroviç.

Simplex Yöntemi Herhangi bir doğrusal programlama problemini çözmeye izin veren evrenseldir. Şu anda bilgisayar hesaplamaları için kullanılmaktadır, ancak simpleks yöntemi kullanılarak basit örnekler manuel olarak da çözülebilir.

Simplex yöntemini uygulamak için - çözümün art arda iyileştirilmesi - ustalaşmak gerekir üç ana unsur:

probleme bazı uygulanabilir temel çözümlerin belirlenmesi için bir yöntem;

en iyi (daha doğrusu en kötü değil) çözüme geçiş kuralı;

bulunan çözümün optimalliğini kontrol etme kriteri.

Simplex yöntemini kullanmak için, doğrusal programlama problemi kanonik forma, yani kısıtlama sistemi denklemler şeklinde sunulmalıdır.

Literatür yeterince ayrıntılı olarak açıklamaktadır: ilk referans planının bulunması (ilk uygulanabilir temel çözüm), ayrıca yapay temel yönteminin kullanılması, optimal referans planının bulunması, tek yönlü tablolar kullanılarak problemlerin çözülmesi.

3.2. Simplex yönteminin algoritması.

LLP'nin çözümünü simpleks yöntemle ele alalım ve bunu maksimizasyon problemi ile ilişkili olarak sunalım.

1. Problemin durumuna göre matematiksel modeli derlenir.

2. İnşa edilen model şuna dönüştürülür: kanonik biçim. Bu durumda, başlangıç ​​referans planı olan bir temel öne çıkabilir.

3. Problemin kanonik modeli, tüm serbest terimler negatif olmayacak şekilde tek yönlü bir tablo şeklinde yazılmıştır. Başlangıç ​​referans planı seçilirse 5. adıma gidin.

Tek yönlü tablo: kısıtlama denklemleri sistemi uyuyor ve amaç fonksiyonu başlangıç ​​esasına göre izin verilen ifadeler biçiminde. Amaç fonksiyonunun katsayılarının girildiği satır
, isminde
–string veya nesnel işlev dizisi.

4. Elementlerin işaretlerini hesaba katmadan, minimum simpleks oranlarına karşılık gelen pozitif çözme elemanları ile simpleks dönüşümler yaparak ilk destek planını bulun.
-Teller. Dönüşümler sırasında, serbest terim dışında tüm öğeleri sıfır olan bir 0 satırı varsa, o zaman problemin kısıtlayıcı denklem sistemi tutarsızdır. Öte yandan, serbest terim dışında başka pozitif öğenin olmadığı bir 0-satırı varsa, o zaman kısıtlayıcı denklemler sisteminin negatif olmayan çözümü yoktur.

(2.55), (2.56) sisteminin yeni bir temele indirgenmesi çağrılacaktır. tek yönlü dönüşüm . Simplex dönüşümü formal bir cebirsel işlem olarak kabul edilirse, bu işlemin bir sonucu olarak rollerin bazı sistemlerde yer alan iki değişken arasında yeniden dağıtıldığı görülebilir. doğrusal fonksiyonlar: bir değişken bağımlıdan bağımsıza, diğeri ise tam tersi - bağımsızdan bağımlıya gider. Bu işlem cebirde şöyle bilinir: Ürdün eleme adımı.

5. Bulunan ilk temel plan, optimallik açısından incelenir:

a) içinde ise
-line (serbest terim dışında) negatif öğe içermiyorsa, plan optimaldir. Sıfır yoksa, optimal plan benzersizdir; en az bir sıfır varsa, sonsuz sayıda optimal plan vardır;

b) eğer
– satır, pozitif olmayan öğelerden oluşan bir sütuna karşılık gelen en az bir negatif öğeye sahiptir, ardından
;

c) içinde ise
-row'da en az bir negatif öğe ve sütununda en az bir pozitif öğe varsa, optimal olana daha yakın olan yeni bir referans planına gidebilirsiniz. Bunu yapmak için, belirtilen sütunun çözümleme olarak atanması gerekir, minimum simpleks oranına göre çözümleme satırını bulun ve bir tek yönlü dönüşüm gerçekleştirin. Elde edilen temel plan, optimallik açısından yeniden incelenir. Tanımlanan süreç, optimal bir plan elde edilene veya problem çözülemez hale gelene kadar tekrarlanır.

Temelde yer alan bir değişken için katsayılar sütununa çözümleme denir. Bu nedenle, negatif öğe tarafından temele eklenen bir değişkenin seçilmesi (veya bir çözümleme sütununun seçilmesi)
–strings, fonksiyonun artmasını sağlıyoruz
.

Bazdan çıkarılacak değişkeni belirlemek biraz daha zordur. Bunu yapmak için, serbest üyelerin çözümleme sütununun pozitif öğelerine oranlarını oluştururlar (bu tür ilişkilere tek yönlü denir) ve bunlar arasında, hariç tutulan değişkeni içeren satırı (çözümleme) belirleyen en küçük olanı bulurlar. Minimum tek yönlü orana göre temelden çıkarılacak bir değişkenin seçimi (veya bir çözümleme dizisinin seçimi), halihazırda belirlendiği gibi, yeni referans tasarımında temel bileşenlerin pozitifliğini garanti eder.

Algoritmanın 3. adımında, serbest terimler sütununun tüm öğelerinin negatif olmadığı varsayılır. Bu gereklilik zorunlu değildir, ancak karşılanırsa, sonraki tüm tek yönlü dönüşümler, yalnızca hesaplamalar için uygun olan pozitif çözünürlük öğeleriyle gerçekleştirilir. Serbest üyeler sütununda negatif sayılar varsa, çözümleme elemanı aşağıdaki gibi seçilir:

1) bazı negatif serbest üyelere karşılık gelen dizeyi tarayın, örneğin –row ve içindeki bazı olumsuz öğeleri seçin ve karşılık gelen sütun çözme olarak alınır (problemin kısıtlamalarının uyumlu olduğunu varsayıyoruz);

2) serbest üyeler sütununun öğelerinin, aynı işaretlere sahip (simpleks oranlar) çözme sütununun karşılık gelen öğelerine oranlarını oluşturmak;

3) simpleks ilişkilerin en küçüğünü seçin. İzin dizesini belirleyecektir. Olsun, örneğin, R-astar;

4) çözme sütunlarının ve satırlarının kesişme noktasında bir çözme elemanı bulunur. Öğeye izin verilirse –string, daha sonra simpleks dönüşümünden sonra bu dizgenin serbest terimi pozitif olacaktır. Aksi takdirde, bir sonraki adımda tekrar -sicim. Sorun çözülebilir ise, belirli sayıda adımdan sonra serbest terimler sütununda hiçbir olumsuz unsur olmayacaktır.

Bazı gerçek üretim durumları LLP biçiminde giydirilirse, o zaman onu kanonik forma dönüştürme sürecinde modele dahil edilmesi gereken ek değişkenler her zaman belirli bir ekonomik anlama sahiptir.