: Görevler doğrusal programlama(LPP)

1. Doğrusal programlama

2. Doğrusal programlama problemlerinin türleri

3. LPP kayıt biçimleri

4. Doğrusal programlama problemlerinin kanonik formu

Doğrusal programlama

Doğrusal programlama, doğrusal programlama için çeşitli değişkenlerin doğrusal fonksiyonlarının uç noktalarını bulmak için yöntemlerin geliştirilmesinde kullanılan matematiksel programlamanın bir dalıdır. ek kısıtlamalar değişkenlere yüklenir.

LP yöntemleri, çözülen problemlerin türüne göre evrensel ve özel yöntemler olarak ikiye ayrılır. Kullanarak evrensel yöntemler herhangi bir doğrusal programlama problemi (LPP) çözülebilir. Özel olanlar, problem modelinin özelliklerini, amaç fonksiyonunu ve kısıtlamalar sistemini dikkate alır.

Doğrusal programlama problemlerinin temel özelliği, amaç fonksiyonunun ekstremumunun uygulanabilir çözümler bölgesinin sınırında olmasıdır.

Şekil 1 - Amaç fonksiyonunun ekstremumu

LPP'nin matematiksel modeli yazılır Aşağıdaki şekilde:

maks (veya min) Z = z (X), (1)

ODR sistem tarafından temsil edilebilir lineer denklemler veya eşitsizlikler.

Vektör X = (x 1, x 2, .... x p) bir kontrol veya kontrol eylemi vektörüdür.

Z = z (X) optimallik kriterinin uç bir değere ulaştığı uygulanabilir bir tasarım X'e optimal denir ve X * ile gösterilir, amaç fonksiyonunun uç değerine Z * = z (X *) denir.

Doğrusal programlama problemlerinin türleri

Doğrusal programlama yöntemleri yaygın olarak kullanılmaktadır. endüstriyel Girişimcilik optimize ederken üretim programı, atölyeler arasında ve zaman aralıklarına göre dağılımı, ekipman çeşitlerinin yüklenmesi, kargo akışlarının planlanması, bir ciro planının belirlenmesi vb.

En yaygın görev türü kaynakların optimal kullanımı sorunu. Piyasa koşullarına göre bir miktar üretim birimi (atölye, işletme, dernek vb.) Tekniksel kabiliyetler ve mevcut kaynaklar, n'yi serbest bırakabilir farklı şekiller j olarak bilinen ürünler

Ürün üretirken, işletme, sayısı m ile gösterilecek olan mevcut kaynaklar ve B = (b 1, b 2, ..., b т) kaynak vektörü ile sınırlıdır. j'inci ürünün bir biriminin üretimi için i-inci kaynağın tüketim oranını gösteren teknolojik katsayılar a ij de bilinmektedir. Birim çıkış verimliliği j ürünleri bir kar p j ile karakterize edilir.

Verilen kaynaklar için işletmenin karını maksimize eden X = (x 1, x 2, ..., x p) üretim planının belirlenmesi gerekmektedir.

Amaç fonksiyonu şuna benzer

kısıtlamalarla

Genellikle ürün yelpazesi ana kuruluş tarafından belirlenir, yani hacimleri bazı D n j ve D sınırları içinde j'de kapatılmalıdır: ardından aşağıdaki kısıtlama belirlenir:

Kaynakların optimal kullanımı probleminin modelinin altında yatan şey işletmenin yıllık üretim programının optimizasyon modelleri... Model, ekipman işletim süresi fonu üzerinde kısıtlamalar içermektedir.

Önceki gösterimi koruyarak sırasıyla b j ve c j ile satış fiyatını ve birim maliyetleri yazıyoruz. j-th ürünleri... Aşağıdakiler bir optimallik kriteri olarak alınabilir:

1) maksimum kar

2) minimum üretim maliyetleri

3) değer açısından maksimum çıktı (ürün satışlarından elde edilen gelir)

Örnek. Firma 1, 2, 3 ve 4 çeşit ürün üretebilmektedir. Her hacimde satış sağlanmaktadır. Çeyrek boyunca, işletme 100 adam vardiyası, 260 kg ağırlığında yarı mamul ürünler, 370 makine vardiyası için makine teçhizatı iş gücüne sahiptir. Her bir ürün türünün kaynak tüketimi ve birim başına kâr oranları Tablo 1'de sunulmuştur.

Gerekli:

a) maksimum kârın elde edildiği üretim planını belirleme probleminin matematiksel bir modelini hazırlamak;

b) Sorunu, üçüncü ürünün birim sayısı 3 katı olacak şekilde eksiksiz bir set şartıyla çözün. daha fazla miktar birincinin birimleri;

c) ne zaman optimal ürün çeşitliliğini bulun ek koşullar: ilk ürün en az 25 adet, üçüncüsü - 30'dan fazla değil ve ikinci ve dördüncü - 1: 3 oranında üretilmelidir.

tablo 1

İlk veri

Problemin matematiksel modeli:

amaç fonksiyonu:

maks: Z = 40x 1 + 50x 2 + 100x 3 + 80x 4

kısıtlamalar ile:

a) emek kaynakları için:

2.5x 1 + 2.5x 2 + 2x 3 + 1.5x 4? 100;

yarı mamul ürünler için:

4x 1 + 10x 2 + 4x 3 + 6x 4? 260;

makine ekipmanında:

8x 1 + 7x 2 + 4x 3 + 10x 4? 370;

negatif olmama koşulu:

B) ek gereksinim tamamlama koşulu ile ifade edilecektir

3x 1 = x 3, yani 3x 1 x 3 = 0;

c) Sınır koşulları ve ekipmanın durumu şu şekilde sunulur: x 1? 25,

x 3? 30, 3 * x 2 = x 4.

Sipariş verme veya değiştirilebilir ekipman gruplarını yükleme sorunu. Bu farklı üretim ve teknolojik özelliklere sahip, ancak siparişleri yerine getirme anlamında değiştirilebilir m (i = 1,…, m) işletmeler (atölyeler, takım tezgahları, sanatçılar) arasındaki siparişlerin dağılımına ilişkin. Görevin tamamlanacağı ve verimlilik göstergesinin aşırı bir değere ulaşacağı siparişlerin verilmesi için böyle bir plan yapılması gerekiyor.

Problemi matematiksel olarak formüle edelim. m homojen ekipman grubu üzerinde n çeşit ürün üretmek gerekli olsun. Her ürün türü için yayın planı belirli bir süre x j (j = 1,2, ... p) kümesi tarafından verilir. Her tür ekipmanın gücü sınırlıdır ve b i'ye eşittir. Bilinen teknolojik matris A = || a ij ||, burada bir ij, birim zaman başına üretilen j'inci ürünün birim sayısıdır. i. ekipman... Matris С - maliyet matrisi, burada c ij - sürümle ilgili maliyetler birim j-th i-th ekipmanındaki ürünler. X, üretilen ürünlerin hacminin vektörüdür.

Problem modeli aşağıdaki formu alacaktır:

amaç fonksiyonu, tüm siparişlerin uygulanmasının maliyetlerini en aza indirmektir.

kısıtlamalar ile:

a) ekipman gücü ile

b) üretim için

c) negatif olmama koşulu

Bu soruna dağıtım sorunu veya dağıtım sorunu denir.

Bazı ürün türleri için planı aşmasına izin verilirse, kısıtlama (b) biçimini alacaktır.

Ayrıca hedef kâr olarak da alabilirsiniz:

a) maksimum kar

b) takım tezgahı süresinin minimum maliyetleri

Çünkü herhangi bir model basitleştirici önkoşullar içerir; elde edilen sonuçların doğru uygulanması için, bu basitleştirmelerin özünün net bir şekilde anlaşılması gerekir, bu da nihayetinde kabul edilebilirliği veya kabul edilemezliği hakkında bir sonuca varmamızı sağlar. Ele alınan modellerdeki en önemli sadeleştirme, kaynak tüketim hacmi ile üretim hacmi arasında, a ij maliyet oranları kullanılarak belirlenen doğru orantılı (doğrusal) bir ilişkinin varsayımıdır. Açıkçası, bu varsayım her zaman yerine getirilmez. Bu nedenle, X üretim programındaki değişikliğe bağlı olarak birçok kaynağın (örneğin sabit kıymetlerin) tüketim hacimleri hızla değişir. Diğer basitleştirici varsayımlar, j fiyatlarının xj hacimlerinden bağımsız olduğu varsayımını içerir, bu yalnızca geçerlidir. değişimlerinin belirli sınırları için. Bu "güvenlik açıklarını" bilmek de önemlidir, çünkü bunlar modeli geliştirmek için temel yönergeleri gösterir.

LPP kayıt formları

LPP kaydının 3 biçimi vardır:

1) fonksiyonlar olarak

maks (veya min) Z =, maks (veya min) Z =,

2) vektör formu

(vektörlerin nokta çarpımı)

kısıtlamalarla

A 1 x 1 + A 2 x 2 + .. + A n x n = B

vektörler nerede

C = (C 1, C 2 .. Cn), X = (X 1, X 2 .. X n) ve.

3) matris formu

kısıtlamalarla

burada С = (с 1, с 2, ... с n),

Doğrusal Programlama Problemlerinin Kanonik Biçimi

Bir lineer programlama problemindeki tüm kısıtlar denklemlerse ve tüm değişkenler x j'ye negatif olmayan koşullar empoze ediliyorsa, buna kanonik formda bir lineer programlama problemi veya bir kanonik lineer programlama problemi (CLP) denir.

kısıtlamalarla

LPP'den CLPP'ye geçebilmek için eşitsizlik kısıtlarından eşitlik kısıtlarına geçmek ve negatif olmama koşullarına uymayan değişkenleri değiştirmek gerekir.

tüzük ZLP'yi getirmek kanonik forma:

1) kısıtlamalarda ise sağ kısım negatif ise, bu limit -1 ile çarpılmalıdır;

2) Kısıtlar arasında eşitsizlikler varsa, ek negatif olmayan değişkenler dahil edilerek bunlar eşitliklere dönüştürülür;

3) bazı xk değişkeninin işaret kısıtlaması yoksa, o zaman amaç fonksiyonunda ve tüm kısıtlamalarda iki yeni negatif olmayan değişken arasındaki farkla değiştirilir: xk = x * k - xl, burada l bileşik indekstir, x * k> =, xl > = 0.

Bir örneğe bakalım. Kanonik forma getirelim:

x 4, x 5, x 6 değişkenlerini eşitleyen kısıtlamalar sisteminin her bir denklemine giriş yapalım. Sistem eşitlikler şeklinde yazılacak ve kısıtlamalar sisteminin birinci ve üçüncü denklemlerinde x 4, x 6 değişkenleri girilecektir. Sol Taraf"+" işaretiyle ve ikinci denklemde "-" işaretiyle x 5 girilir.

Kanonik formdaki serbest terimler pozitif olmalıdır, bunun için son iki denklemi -1 ile çarpıyoruz:

Doğrusal programlama problemlerini yazmanın kanonik biçiminde, kısıtlama sistemine dahil edilen tüm değişkenler negatif olmamalıdır. varsayalım ki

değiştirme verilen ifade kısıtlama sistemine ve hedef fonksiyon ve değişkenleri indeksin artan sırasına göre yazarsak, kanonik biçimde sunulan bir doğrusal programlama problemi elde ederiz:

optimizasyon simpleks doğrusal programlama

Milletvekilinin Görevleri

Genel LPP arandı <,=,>=) bi (i = 1, n) (2) sağlanan xj>

Simetrik < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > kanonik karışık.

min f (x) = -maks (-f (x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Amaç fonksiyonunun ve LPP kısıtlamalarının geometrik yorumu. ZLP'nin geometrik formülasyonu.

Problem f = c1x1 + c2x2-max (1) olsun

a11x1 + a12x2<=b1 }

am1x1 + am2x2<=bm}

x1> = 0, x2> = 0 (3)

Problemin planı (x1, x2) düzlemde bir noktadır. Her eşitsizliği ile-biz 2 temsil eder. yarı düzlemdir. Yarım düzlem bir dışbükey kümedir. dışbükey bu kümeye ait doğru parçayı bağlayan (x1 ve x2) noktalarının da kümeye ait olduğu kümedir. C-ma 2, yarım düzlemlerin kesişimidir. Geçerken şunları alabilirsiniz:

1) dışbükey çokgen kapalı alan.

2) dışbükey açık çokgen alan

3) tek nokta

4) boş küme

5) ışın ve segment

Amaç fonksiyonunun geometrik yorumu: f-tion 1, seviye çizgileri (amaç fonksiyonunun sabit değerindeki çizgiler) olarak adlandırılan bir paralel düz çizgiler ailesidir. Fonksiyonun x1 ve x2'ye göre kısmi türevleri, eksenlerin koordinatları boyunca amaç fonksiyonunun artış oranını gösterir. vektör gradyan amaç fonksiyonunda en hızlı artışın yönünü gösterir Problem 1-3 için vektör-gradyan = (с1; с2) (0,0) noktasından ayrılır ve koordinatları (с1; с2) olan noktaya yönlendirilir. . Gradyan vektörü, seviye çizgilerine diktir. Yarım düzlemlerin kesişimine denir. kabul edilebilir çözümlerin alanı (ODS).

Ana LP teoremi. Şematik diyagram Bu teoremden çıkan LPP'nin çözümleri.

LPP'nin bir çözümü varsa, amaç fonksiyonu uç değerine, tasarım çokyüzlülüğünün uç noktalarından en az birinde ulaşır. Amaç fonksiyonu birden fazla uç noktada uç değere ulaşırsa, bunların dışbükey lineer birleşimi olan bir ve buna ulaşır.Herhangi bir noktada aynı değer. NS LPP'nin kararı bir tablo girişini manuel olarak kullanmak uygundur.

BP		SP -Xm + 1 -Xm + 2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
F	yuh	bo1 bo2 bon-m

Simpleks yöntemi algoritması.

1. problem modelini kanonik forma getirmek;

2. ilk referans planını bulun;

3. Problemi daha basit bir şekilde yazın. tablo;

5. Yeni bir temel plana, yeni bir sim'e gidin. tablo. Yeni bir temel plana geçmek için bir temel değişkeni ücretsiz olanla değiştirmek yeterlidir. Temele dahil edilen değişken ve karşılık gelen çözümleme sütunu, mutlak değerdeki f-satırının en büyük negatif öğesi tarafından belirlenir. Temelden hariç tutulan değişken ve karşılık gelen çözümleme çizgisi, en küçük tek yönlü ilişki ile belirlenir, yani. tek bir sütunun elemanlarının, çözümleme sütununun karşılık gelen elemanına oranı. Simpleks oranı, negatif olmayan bir değerdir. Çözümleme çizgisinin ve çözümleme sütununun kesişiminde, buna göre bir çözümleme elemanı vardır. tek yönlü dönüşüm bir sonrakinde. kurala göre: 1. izin veren çizginin öğeleri, izin veren öğeye bölünür; 2. izin verilen sütunun öğeleri izin verilen öğeye bölünür ve işareti tersine değiştirir; 3.Tablo elemanlarının geri kalanı dikdörtgen kuralına göre kaydırılır.:

bij bis bkj = (bkj * bis-bij * bks) / bi

Aya dualite teoremi.

ikili problemlerden birinin optimal bir planı varsa, diğeri çözülebilir, yani. bir opt.plana sahiptir. Bu durumda amaç fonksiyonlarının uç değerleri çakışır (j = 1'den n'ye) Σcjxj * = (i = 1'den m'ye) Σbiyi * orijinalde ise. amaç fonksiyonu planlar setinde sınırsızdır, o zaman ikili görev kısıtlama sistemi tutarsız.

TK matrisinin rankı üzerindeki teorem.

Taşıma probleminin A matrisinin rankı, denklem sayısından bir eksiktir: r (A) = m + n-1.

39. LPP'nin ilk temel planını oluşturmak için algoritma.

İlk referans planını bulmak için aşağıdakileri önerebilirsiniz: algoritma:

1.Serbest üyeler sütununun tüm elemanları negatif olmayacak şekilde problemi bir Jordan tablosu şeklinde yazın, yani. eşitsizliği аio> = 0 (i = 1, m) tutar. Serbest terimlerin negatif olduğu bu-biz denklemleri önceden -1 ile çarpılır.

		-x1 ... .. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	aşk	am1… .. amn
f =		-c1…. -cn

Sol sütundaki sıfırları karşılık gelen x ile değiştirerek tabloyu Jordan istisna adımlarında dönüştürün. Ayrıca her adımda izinli seçilebilir en az bir pozitif öğe içeren herhangi bir sütun. İzin verilen satır, serbest üyelerin izin verilen sütunun karşılık gelen pozitif öğelerine oranlarının en küçüğü tarafından belirlenir. İstisnalar sürecinde, tüm elemanları sıfır olan ve serbest terim sıfır olmayan bir 0 satırı varsa, o zaman kısıtlayıcı denklemlerin s-ma'sının çözümü yoktur. Serbest terimin yanı sıra başka pozitif öğe olmayan bir 0 satırı varsa, o zaman c-ma kısıtlayıcı denklemlerin negatif olmayan çözümleri yoktur Eğer c-ma kısıtlayıcı denklemler ise eklem yeri, daha sonra belirli sayıda adımdan sonra sol sütundaki tüm sıfırlar x ile değiştirilecek ve böylece belirli bir temel ve sonuç olarak ilgili destek planı elde edilecektir.

40. LPP'nin optimal temel planını oluşturmak için algoritma.

Ho'nun ilk destek planı optimallik açısından test edilir.

f-sırasında (kesme dışında) hiçbir olumsuz unsur yoksa, -plan optimaldir. f-satırı da sıfır eleman içermiyorsa, optimal plan benzersizdir; elemanlar arasında en az bir sıfır varsa, sonsuz sayıda optimal tasarım vardır. f-sırasında en az bir negatif eleman varsa ve karşılık gelen sütunda pozitif eleman yoksa, amaç fonksiyonu kabul edilebilir bölgede sınırlı değildir. Sorun çözülemez. F-satırında en az bir negatif unsur varsa ve böyle bir unsurun bulunduğu her sütunda en az bir pozitif unsur varsa, o zaman optimal olana daha yakın olan yeni bir referans planına gidebiliriz. Bunu yapmak için, f-satırında negatif elemanlı sütun şu şekilde alınır: müsamahakar; çözümleme dizisi minimal simpleks bağıntısı ile belirlenir ve Jordan eliminasyonu adımı alınır. Ortaya çıkan referans planı, optimallik için yeniden incelenir. Bu, optimal bir temel plan bulunana veya problemin karar verilemez olduğu bulunana kadar tekrarlanır.

Gomori yönteminin algoritması.

1. Problemin optimal planı simpleks yöntemi ile bulunur. Optimal planın tüm bileşenleri ayrılmazsa, o zaman optimaldir. Aksi takdirde, 2. adıma gidin

2. İntegral olmayan bileşenlerden aşağıdakileri içereni seçin: kesirli kısım en büyüğüdür ve tek yönlü tablonun ilgili satırına göre, formülle doğru kesmeyi formüle edin

(n-m, s = 1) ∑ (αkm + 1) Xm + 1≥ (βk)

3. Formüle edilmiş eşitsizliği eşdeğer bir sıfır eşitliğe dönüştürün ve tek yönlü tablo tamsayı olmayan bir optimal planla

4. Elde edilen genişletilmiş problem simpleks yöntemiyle çözülür. Ortaya çıkan plan bir tamsayı nova değilse 2. adıma gidin.

Tamsayısız serbest terimli ve tamsayılı bir çizgiyi çözme sürecinde diğer katsayılar ortaya çıkarsa, karşılık gelen denklemin tamsayılarda çözümü yoktur. Bu durumda, orijinal problem de tamsayılarda çözülemez.Gomori yönteminin uygulaması sınırlıdır. Yardımı ile küçük sorunları çözmeniz önerilir, çünkü etkileşimlerin sayısı çok büyük olabilir.

çeşitli şekiller LPP kayıtları (genel, kanonik, simetrik)

Milletvekilinin Görevleri: optimal planın belirlenmesi, optimal üretim hacminin belirlenmesi, mahsullerin / çiftlik mahsulleri ile optimal kombinasyonunun belirlenmesi, optimal varlık paketinin oluşturulması, bankanın kârının maksimize edilmesi, vb.

Ortak LPP denir maksimizasyon (minimizasyon) problemi doğrusal fonksiyon f = Σcj * xj-maks (min) (1) doğrusal kısıtlamalar altında ∑aij * xj (=<,=,>=) bi (i = 1, n) (2) sağlanır xj> = 0 (j = 1, n1), xj-keyfi (j = n1 + 1, n) (3) burada cj, aij, bi-sabit sayılar .

Simetrik LPP için gösterim şekli, işaretli eşitsizliklerde doğrusal kısıtlamalar altında fonksiyonu (1) maksimize etme problemidir.< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >veya = ve negatif olmayan değişkenler. kanonik LPP için gösterim şekli, doğrusal kısıtlamalar, eşitlikler ve negatif olmayan değişkenler altındaki maksimum fonksiyon (1) problemidir. Başka herhangi bir form denir karışık.

min f (x) = -maks (-f (x))

Bir eşitsizliğin bir denkleme dönüştürülmesi ve bunun tersi, Lemma temelinde gerçekleştirilir: bir eşitsizliğin her x1 ... xn çözümü a1x1 + ... + anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>= 0 (7) ve tersi. Denklem 6'nın herhangi bir x1… xn, xn + 1 çözümü ve 7 eşitsizliği, 5 eşitsizliğinin x1… xn çözümüne karşılık gelir.

Sim formunun arkasından kanonik formun arkasına gitmek için şunu girmelisiniz: denge (düzeyleme) değişkenleri. Bu, eşitsizlik teoremine dayanmaktadır: herhangi bir eşitsizlik, ur-i veya en basit eşitsizlik olarak temsil edilebilir.

doğrusal programlama problemleri

2.1. Girişin tanımı ve şekli

Tüm kısıtların denklem olması ve tüm değişkenlerin negatif olmama koşulunu sağlaması durumunda doğrusal programlama problemi denir. kanonik. Koordinat, vektör veya matris notasyonu biçiminde gösterilebilir.

a) Koordinat formundaki kanonik LP problemi şu şekildedir:

,
.

Bu problem toplama işareti kullanılarak yazılabilir:

,

,

,
,
.

b) vektör biçimindeki kanonik LP problemi şu şekildedir:,

,

nerede
;
;

,
;;
.

c) matris formundaki kanonik LP problemi şu şekildedir:

,
,

nerede
,,.

2.2. Genel lineer problemin azaltılması

kanonik forma programlama

Ekonomik problemlerin matematiksel modellerini derlerken, kısıtlamalar esas olarak eşitsizlik sistemlerine dönüştürülür. Bu nedenle, onlardan denklem sistemlerine geçebilmek gerekir. Örneğin, doğrusal eşitsizliği düşünün

ve sol tarafına biraz değer ekleyin
böylece eşitsizlik eşitliğe dönüşür.

Negatif olmayan değişken
ek değişken denir. Aşağıdaki teorem, böyle bir dönüşümün olasılığı için bir temel sağlar.

Teorem 2.2.1. her karara
(2.2.1) eşitsizliği, denklem (2.2.2) ve eşitsizliğin benzersiz bir çözümüne karşılık gelir
, ve tersine, denklem (2.2.2)'nin her çözümü için
maç çözümü
eşitsizlik (2.2.1).

Kanıt.İzin vermek
eşitsizliğin çözümü (2.2.1). Sonra. numarayı alalım
... açık ki
... (2.2.2) denklemini yerine koyarsak, şunu elde ederiz:

Teoremin ilk kısmı ispatlandı.

Şimdi vektöre izin ver (2.2.2) denklemini şu şekilde karşılar:
, yani, son eşitliğin sol tarafındaki negatif olmayan değerin atılması
, alırız vb.

Böylece, ispatlanmış teorem aslında herhangi bir LP problemini kanonik forma indirgeme olasılığını ortaya koymaktadır. Bunu yapmak için, her bir kısıtlamaya eşitsizlik şeklinde negatif olmayan ek bir değişken eklemek yeterlidir. Ayrıca, (1.2.1) biçimindeki eşitsizliklerde bu değişkenler "+" işaretiyle ve (1.2.2) biçimindeki eşitsizliklerde "-" işaretiyle girecektir. Amaç fonksiyonuna sıfır katsayılı ek değişkenler eklenir ve bu nedenle değerini etkilemez.

Yorum Yap. Bundan sonra, minimum için amaç fonksiyonunun çalışmasında kanonik LP problemi için simpleks yöntemini tanımlayacağız. Maksimumu bulmanız gereken görevlerde
, işlevi dikkate almak yeterlidir
, minimum değerini bulun ve ardından işareti tersine değiştirerek istenen maksimum değeri belirleyin
.

3. Problemleri çözmek için grafiksel yöntem

doğrusal programlama

3.1. Genel kavramlar, örnekler

LP probleminde sadece iki değişkenin olduğu durumlarda, çözmek için kullanılabilir. grafiksel yöntem... Fonksiyonun maksimum (minimum) değerini bulmamız istensin.
kısıtlamalarla

(3.1.1)

Bu yöntem, soruna uygulanabilir çözümlerin bölgesini grafiksel olarak temsil etme yeteneğine dayanmaktadır, yani. tatmin edici sistem (3.1.1) ve bunlar arasında en uygun çözümü bulma. Problemin uygulanabilir çözümlerinin alanı, verilen kısıtlamaların her birine (3.1.1) yönelik çözüm alanlarının kesişimi (ortak kısım) olarak oluşturulur. Her biri sınırı olan bir yarım düzlem tanımlar.
,
... İki yarım düzlemden hangisinin çözümlerin alanı olduğunu belirlemek için, düz bir çizgi üzerinde yer almayan bir noktanın koordinatlarını eşitsizliğe koymak yeterlidir: eğer bu sağlanıyorsa, o zaman çözümler alanıdır. içeren yarım düzlem bu nokta, eğer eşitsizlik sağlanmazsa, o zaman çözümlerin alanı bu noktayı içermeyen bir yarım düzlemdir.

Bu yarım düzlemlerin kesişimi, bir dışbükey küme olan çözüm çokgeni adı verilen belirli bir bölgeyi oluşturur. (Kısıtlar sisteminin uyumlu olduğunu ve çözümlerinin çokgeninin sınırlandırıldığını varsayalım.) Uygulanabilir çözümler arasında en uygun çözümü bulmak için seviye çizgileri ve destek çizgileri kullanılır.

Seviye çizgisi amaç fonksiyonunun üzerinde bulunduğu çizgiye denir. sabit bir değer alır. Seviye çizgisi denklemi şu şekildedir:

, nerede
... Tüm seviye çizgileri birbirine paraleldir. onların normali
.

destek hattı uygun çözümler bölgesi ile en az bir ortak noktası olan ve bu bölgenin yarı düzlemlerden birinde yer aldığı bir seviye çizgisi denir (Şekil 1).

Değerler
vektör yönünde artış
... Bu nedenle, seviye çizgisini hareket ettirmek gerekir.
bu vektörün kendisine referans çizgisine paralel yönünde L 1 maksimum problemde ve ters yönde - minimum problemde (referans çizgisine L 2).

Örnek 1.1'in çözümünü verelim. Fonksiyonun maksimumunu bulmanız gerektiğini hatırlayın.
kısıtlamalarla

Çözüm. Uygulanabilir çözümlerin alanını inşa ediyoruz. Problemin kısıtlarını numaralandıralım. Dikdörtgen bir Kartezyen koordinat sisteminde (Şekil 2) düz bir çizgi oluşturuyoruz

(1) numaralı kısıtlamaya karşılık gelir. Bu doğrunun tüm koordinat düzlemini böldüğü yarım düzlemlerden hangisinin eşitsizliğin çözüm alanı olduğunu buluruz (1).

Bunu yapmak için, düz bir çizgi üzerinde olmayan bir noktanın koordinatlarını eşitsizliğe yerleştirmek yeterlidir. düz beri orijinden geçmez, ikame
ilk kısıtlamaya girer. Kesin eşitsizliği elde ederiz
... Bu nedenle nokta
çözümlerin yarı düzleminde yer alır. Benzer şekilde, düz bir çizgi oluşturuyoruz

ve (2) kısıtının çözüm alanı. Kısıtları dikkate alarak çözümlerin yarım düzlemlerinin ortak kısmını bulun (3). Elde edilen uygulanabilir çözüm alanı, Şekil 2'de koyu renkle vurgulanacaktır.

Seviye çizgisi oluşturma
ve vektör
fonksiyonun artış yönünü gösteren ve düz çizgiye dik

... Seviye çizgisi
yönde kendisine paralel hareket etmek
referans hattına. Noktada amaç fonksiyonunun maksimum değerine ulaştığını elde ederiz.
çizgilerin kesiştiği nokta ve ... Bu düz çizgilerin denklem sistemini çözme
, noktanın koordinatlarını alıyoruz
... Bu nedenle ve
,
en uygun çözüm.

Örnek 3.1. Bir fonksiyonun minimumunu bulun
bir kısıtlama sistemi altında

Çözüm. Kabul edilebilir çözümler bölgesini oluşturuyoruz (bkz. Şekil 3), vektör
ve seviye çizgilerinden biri
... Seviye çizgisini ters yönde hareket ettirin
, fonksiyonun minimumunu bulma problemi çözüldüğü için. Bu durumda, destek hattı, koordinatları sistemin çözümünden bulunabilen A noktasından (Şekil 3) geçer.

Yani,
... hesaplıyoruz.

Yorum Yap. Aslında, uygulanabilir çözümlerin bölgesinin şekli ve amaç fonksiyonu
LP probleminin tek bir çözümü, sonsuz sayıda çözümü olabilir veya tek bir çözümü olmayabilir.

Örnek 3.2. Bir fonksiyonun minimumunu bulun
kısıtlamalarla

Çözüm. Seviye çizgilerinin normali olan kabul edilebilir çözümlerin alanını inşa ediyoruz
ve seviye çizgilerinden biri sahip ortak noktalar bu alanla. Seviye çizgisini hareket ettirmek normalin tersi yönde , fonksiyonun minimumunu bulma problemi çözüldüğü için. Seviye çizgisi normal
ve sınır çizgisinin normali , seviye çizgilerinin hareket ettiği yönde paraleldir, çünkü koordinatları orantılıdır
... Bu nedenle, destek çizgisi sınır çizgisi ile çakışmaktadır. uygulanabilir çözümlerin bölgesi ve bu bölgenin iki köşe noktasından geçer. ve (şekil 4).

Problem, segmentin noktaları olan sonsuz bir optimal çözüm kümesine sahiptir.
... Bu noktalar
,
karşılık gelen denklem sistemlerini çözerek buluruz:

;
;

,
;
,
;

;
.

hesaplıyoruz.

Cevap:
NS
,
.

Örnek 3.3. Doğrusal programlama problemini çözün

Çözüm. Uygun çözümler bölgesini inşa ediyoruz, normal
ve seviye çizgilerinden biri. Bu problemde amaç fonksiyonunun maksimumunu, dolayısıyla seviye çizgisini bulmak gerekir. normal yönde hareket ettirin. Bu doğrultuda uygulanabilir çözümlerin bölgesi sınırlı olmadığından, seviye çizgisi sonsuza gider (Şekil 5).

Amaç fonksiyonunun sınırsızlığından dolayı problemin çözümü yoktur.

Cevap:
.

Herhangi bir doğrusal programlama problemi, kanonik formda bir doğrusal programlama problemine indirgenebilir. Bunun için Genel dava maksimizasyon problemini minimizasyon problemine indirgeyebilmeniz gerekir; eşitsizlik kısıtlamalarından eşitlik kısıtlamalarına gidin ve negatif olmama koşuluna uymayan değişkenleri değiştirin. Bazı fonksiyonların maksimizasyonu, aynı fonksiyonun zıt işaretli olarak minimizasyonuna eşdeğerdir ve bunun tersi de geçerlidir.

Doğrusal bir programlama problemini kanonik forma indirgeme kuralı aşağıdaki gibidir:

• eğer içinde asıl sorun bir lineer fonksiyonun maksimumunu belirlemek gerekir, o zaman işaretini değiştirmeli ve bu fonksiyonun minimumunu aramalısınız;
• kısıtların sağ tarafı negatif ise, bu kısıt -1 ile çarpılmalıdır;
• kısıtlamalar arasında eşitsizlikler varsa, ek negatif olmayan değişkenler dahil edilerek bunlar eşitliklere dönüştürülür;
• eğer bazı değişkenler x j işaret kısıtlaması yoksa, (amaç fonksiyonunda ve tüm kısıtlamalarda) iki yeni negatif olmayan değişken arasındaki farkla değiştirilir:
  x 3 = x 3 + - x 3 - , nerede x 3 +, x 3 - ≥ 0 .

örnek 1... Doğrusal programlama problemini kanonik forma indirgemek:

min L = 2x 1 + x 2 - x 3;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Kısıtlama sisteminin her bir denklemine tesviye değişkenlerini tanıtıyoruz. x 4, x 5, x 6... Sistem eşitlikler şeklinde yazılacak ve kısıtlamalar sisteminin birinci ve üçüncü denklemlerinde değişkenler yazılacaktır. x 4, x 6 sol tarafa "+" işareti ile girilir ve ikinci denklemde değişken x 5"-" işareti ile girilir.

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Kanonik formdaki serbest terimler pozitif olmalıdır, bunun için son iki denklemi -1 ile çarpıyoruz:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

Doğrusal programlama problemlerinin kanonik yazım biçiminde, kısıtlar sistemine dahil edilen tüm değişkenler negatif olmalıdır. varsayalım ki x 1 = x 1 "- x 7 , nerede x 1 "≥ 0, x 7 ≥ 0 .

Bu ifadeyi kısıtlar sistemine ve amaç fonksiyonuna koyarak ve değişkenleri indeksin artan sırasına göre yazarak, kanonik biçimde sunulan bir doğrusal programlama problemi elde ederiz:

L min = 2x 1"+ x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 = 5;
-x 1"- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1"+ x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x ben ≥ 0, ben = 2, 3, 4, 5, 6, 7.

Kanonik LP probleminin temel planı için optimallik koşulu. Simpleks yöntemi ve yakınsaklığı.

Simpleks yöntemi bir evrensel, yazılmış hemen hemen tüm doğrusal programlama problemlerini çözmenize izin verdiği için kanonik olarak.

Simpleks yöntemi fikri planın sürekli iyileştirilmesi, bazı ilk destek çözümlerinden başlayarak, sürekli yönlendirilmiş hareket problemin destek çözümleri ile optimal olana.

Amaç fonksiyonunun değeri, görevler için maksimuma bu hareketle azalmaz.

Destek çözümlerinin sayısı sonlu olduğundan, sonlu sayıda adımdan sonra optimal olanı elde ederiz. Referans çözümü.

Negatif olmayan temel bir çözüme referans çözüm denir.

Simpleks Yöntem Algoritması

1. Problemin matematiksel modeli şu şekilde olmalıdır: kanonik. Kanonik değilse, kanonik forma getirilmelidir.

2. Orijinal destek çözümünü bulun ve optimal olup olmadığını kontrol edin.
Bunu yapmak için tek yönlü tablo 1'i doldurun.
Kısıtlama sistemi ve amaç fonksiyonu verilerine göre 1. adımdaki tablonun tüm satırlarını dolduruyoruz.

Sorunları çözerken aşağıdaki durumlar mümkündür: maksimum:

1. Eğer tüm katsayılar son satır tek yönlü tablolar Dj ³ 0, sonra bulundu

çözüm en uygun.

2 En az bir katsayı ise DJ £ 0, ancak karşılık gelen değişken için tek bir pozitif değerlendirme oranı yoktur, o zaman çözüm görevleri durduruyoruz, F (X) ® ¥'den beri, yani, amaç fonksiyonu, uygulanabilir çözümler alanında sınırlı değildir.

Son satırın en az bir katsayısı negatifse ve karşılık gelen değişken için en az bir olumlu değerlendirici ilişki, o zaman gitmelisin başka bir referans çözümüne.

4.E Eğer son satırda birkaç negatif katsayı var, o zaman temel değişken sütununa(Bp) tanıtmak değişken hangi karşılık gelir mutlak değerdeki en büyük negatif katsayı.

5. Eğer en az bir katsayı Dk ise< 0 ,sonra k - inci kabul ettiğimiz sütun sunucu için.

6. İçin lider çizgi uygun olanı kabul ediyoruz en azücretsiz üye tutumu iki pozitif katsayılara lider, k - bu kolon.

7. Öndeki satırların ve bir sütunun kesişiminde bulunan bir öğeye denir. lider eleman.

Simpleks tablo 2'yi doldurma :

· temel sütunu sıfırlar ve birlerle doldurun

· baştaki öğeye bölerek baştaki satırı yeniden yazın

Baştaki satırda sıfırlar varsa, karşılık gelen sütunlar bir sonraki tek yönlü tabloya aktarılabilir.

· katsayıların geri kalanı "dikdörtgen" kuralıyla bulunur

Kontrol ettiğimiz yeni bir destek çözümü alıyoruz optimallik için:

Son satırın tüm katsayıları ise Dj ³ 0, sonra bulunan çözüm maksimum.

Değilse, 8. adım simpleks tablosunu doldurun vb.

amaç fonksiyonu ise F (X) bulmayı gerektirir en az değer, ardından kriter problemin optimalliği bir pozitif olmayan oranlar NS j hepsi için j = 1,2, ... n.

Simpleks yönteminin yakınsaklığı. LP problemlerinde yozlaşma. Herhangi bir hesaplama algoritmasının en önemli özelliği yakınsamadır, yani uygulaması sırasında istenen sonuçları (belirli bir doğrulukla) sonlu sayıda adımda (yinelemeler) elde etme olasılığıdır.

Simpleks yönteminin yakınsaması ile ilgili sorunların, aynı olduğunda r (madde 2 ") değerinin seçilmesi aşamasında potansiyel olarak ortaya çıkabileceğini görmek kolaydır. minimum değerler ilişki

T(q) tablosunun birkaç satırına aynı anda ulaşılacaktır. Daha sonra bir sonraki yinelemede sütun b (β (q + 1)) sıfır eleman içerecektir.

Genel durumda, hem denklemler hem de eşitsizlikler kısıtlayıcı olacak şekilde bir doğrusal programlama problemi yazılır ve değişkenler hem negatif olmayan hem de keyfi değişken olabilir. Tüm kısıtların denklem olması ve tüm değişkenlerin negatif olmama koşulunu sağlaması durumunda, doğrusal programlama problemine kanonik denir. Koordinat, vektör veya matris notasyonu ile temsil edilebilir.

1. Koordinat notasyonundaki kanonik doğrusal programlama problemi şu şekildedir:

.

Daha kompakt bir biçimde bu görev toplama işareti kullanılarak yazılabilir,

(1.7)

2. Vektör notasyonundaki kanonik doğrusal programlama problemi şu şekildedir:

(1.8)

nerede ,

.

3. Matris notasyonundaki kanonik doğrusal programlama problemi şu şekildedir:

(1.9)

, .

Buraya A- denklem sisteminin katsayı matrisi, NS- matris-sütun görev değişkenleri, Kısıtlama sisteminin sağ taraflarının matris sütunudur.

Genellikle kullanılan doğrusal programlama problemleridir. simetrik, matris notasyonunda forma sahip olan

(1.10)

(1.11)

1.4. getirmek ortak görev doğrusal programlama
kanonik forma

Doğrusal programlama problemlerinin çözümüne yönelik çoğu yöntemde, kısıtlar sisteminin, değişkenlerin negatif olmaması için denklemlerden ve doğal koşullardan oluştuğu varsayılır. Bununla birlikte, ekonomik problemlerin matematiksel modellerini derlerken, kısıtlamalar esas olarak eşitsizlik sistemlerine dönüştürülür, bu nedenle bir eşitsizlik sisteminden bir denklem sistemine geçebilmek gerekir. Bunun için aşağıdaki teoremi ispatlıyoruz.

Teorem 1.1. Eşitsizliği bir denklemle değiştirme. her karara eşitsizlikler

denklemin benzersiz bir çözümü var

ve eşitsizlik

, (1.14)

ve tersine, denklem (1.13) ve eşitsizliğin (1.14) her çözümüne, eşitsizliğin (1.12) benzersiz bir çözümüne karşılık gelir.

Kanıt.İzin vermek (1.12) eşitsizliğinin bir çözümüdür, o zaman. Bu eşitsizliğin sağ ve sol tarafları arasındaki farkı şu şekilde ifade ederiz:

Açıkça ... (1.13) denkleminde yerine değişken değerler , alırız

Böylece (1.13) denklemini ve (1.14) eşitsizliğini sağlar. Bu, teoremin ilk bölümünün kanıtlandığı anlamına gelir.

Şimdi denklem (1.13) ve eşitsizliği (1.14) sağlamasına izin verin, yani

VE

Son eşitliğin solundaki negatif olmayan niceliği atarak,

yani eşitsizliği (1.12) karşılar. Teorem ispatlandı.

Eşitsizlik varsa, eksi işaretiyle sol tarafına negatif olmayan ek bir değişken eklenmelidir, yani.

Denklemlere dönüştürmek için eşitsizlik kısıtlamalarına dahil edilen negatif olmayan değişkenlere denir. ek değişkenler... Amaç fonksiyonuna sıfır katsayılı ek değişkenler eklenir ve bu nedenle değerini etkilemez.

Problemin keyfi olarak değişen değişkenlere sahip olması durumunda, bu tür herhangi bir değişken, negatif olmayan iki değişkenin farkı ile değiştirilir, yani. , nerede ve .

Bazen problemde minimumu bulmaktan maksimumu bulmaya ya da tam tersini yapmak gerekir. Bunu yapmak için, amaç fonksiyonunun tüm katsayılarının işaretlerini tersine değiştirmek ve sorunun geri kalanını değiştirmeden bırakmak yeterlidir. Bu şekilde elde edilen maksimum ve minimum problemlerin optimal çözümleri ve amaç fonksiyonlarının değerleri örtüşmektedir. optimal çözümler sadece işarette farklılık gösterir.

Örnek 1.1. Doğrusal programlama problemini kanonik forma getirin.

NS

Çözüm... Şimdi amaç fonksiyonunun maksimumunu bulma problemine dönelim. Bunu yapmak için amaç fonksiyonu katsayılarının işaretlerini değiştiririz. Kısıtlar sistemini ikinci ve üçüncü eşitsizliklerin denklemlerine dönüştürmek için negatif olmayan ek değişkenler sunuyoruz ( matematiksel model bu işlem D harfi ile işaretlenmiştir). Değişken, ikinci eşitsizliğin sol tarafında "+" işaretiyle tanıtılır, çünkü eşitsizlik formdadır. Değişken, eşitsizlik şeklinde olduğundan, üçüncü eşitsizliğin sol tarafında "-" işaretiyle tanıtılır. Değişkenler, sıfıra eşit bir katsayı ile amaç fonksiyonuna girilir. Negatif olmama koşuluna tabi olmayan değişken, fark ile değiştirilir. , ... Problemi kanonik biçimde yazma

Bazı durumlarda, kanonik problemi simetrik bir probleme indirgemek gerekli hale gelir. Bir örneğe bakalım.

Örnek 1.2. Doğrusal programlama problemini simetrik forma indirgeyin