Görevlerin sınıflandırılması matematiksel programlama

PROGRAMLAMA

DOĞRUSAL OLMAYAN PROBLEMLERİ ÇÖZME YÖNTEMLERİ

Kontrol soruları 4. bölüme

Çözüm diyagramı ulaşım sorunu

Ulaşım sorununu çözmenin ana aşamalarını sıralayalım.

1. Kapalı durumu kontrol edin. Görev açıksa, taşıma tablosuna hayali bir tüketim noktası sütunu veya hayali bir tedarikçi satırı eklenir.

2. Bir referans planı oluşturun.

3. Dejenerasyon olup olmadığını kontrol etmek için destek planını kontrol edin. Dejenere olmama koşulunu sağlayacak kadar dolu hücre yoksa taşıma tablosunun hücrelerinden biri sıfıra eşit bir kaynakla doldurulur. Gerekirse, birkaç hücreye sıfır teslimatın kaydedilmesine izin verilir.

4. Planın optimalliği kontrol edilir.

5. Optimumluk koşulları karşılanmazsa malzemeleri yeniden dağıtarak bir sonraki plana geçin. Hesaplama süreci Optimal plan elde edilene kadar tekrarlanır.

1. Anlamı nedir amaç fonksiyonu bir ulaşım probleminin matematiksel modelinde mi?

2.Ulaştırma probleminin matematiksel modelindeki kısıtlamaların anlamı nedir?

3. Açık (kapalı olmayan) bir taşıma problemini çözmek için potansiyel yöntemi uygulamak mümkün müdür?

4. Sorunun potansiyel yöntemle çözülebilmesi için orijinal taşıma tablosunda ne gibi değişiklikler yapılması gerekiyor?

5. Yöntemin özü nedir minimum eleman? Bu yöntemin uygulanması sonucunda ulaşım sorununun çözümünde hangi aşama tamamlanmış olacaktır?

6. Ulaşım planının optimal olup olmadığını nasıl anlarsınız?

7. Malzemelerin nakliye açısından yeniden dağıtılması hangi durumda ve nasıl gereklidir?

8. İnşa edilen ulaşım planının dejenere olduğunu varsayalım. Potansiyel yöntemi kullanarak sorunu çözmeye devam etmek mümkün mü ve bunun için ne yapılması gerekiyor?

Genel matematiksel programlama problemi Bölüm 1.1'de formüle edilmiştir. (1.1)-(1.3) modelinde yer alan fonksiyonların türüne bağlı olarak problem, şu veya bu tür matematiksel programlama olarak sınıflandırılır. Doğrusal programlama (tüm işlevler doğrusaldır), tamsayı (çözüm tamsayılarla temsil edilir), ikinci dereceden (amaç işlevi ikinci dereceden bir formdur), doğrusal olmayan (problemin işlevlerinden en az biri doğrusal değildir) ve stokastik programlama ( doğası gereği olasılıksal olan parametreler dahil edilmiştir).

Görev sınıfı değil doğrusal programlama daha geniş sınıf doğrusal modeller. Örneğin, çoğu durumda üretim maliyetleri çıktı hacmiyle orantılı değildir, ancak buna doğrusal olmayan bir şekilde bağlıdır; üretim ürünlerinin satışından elde edilen gelir, fiyatların vb. doğrusal olmayan bir fonksiyonu olarak ortaya çıkar. Optimal planlama problemlerinde kriterler genellikle maksimum kar, minimum maliyet ve minimum sermaye maliyetidir. Değişken miktarlar çıktı hacimleridir çeşitli türlerürünler. Kısıtlamalar, ürün çıktısı ile hacmi sınırlı olan emek ve malzeme kaynaklarının maliyetleri arasındaki ilişkiyi karakterize eden üretim fonksiyonlarını içerir.

Doğrusal programlamanın aksine, evrensel yöntemçözümler (simpleks yöntem), doğrusal olmayan problemleri çözmek için modelde yer alan fonksiyonların biçimine bağlı olarak çok çeşitli yöntemler vardır. Çeşitli yöntemlerden yalnızca ikisini ele alacağız: Lagrange yöntemi ve dinamik programlama yöntemi.

İLE Lagrange yönteminin özü, koşullu ekstremum problemini koşulsuz ekstremum probleminin çözümüne indirgemektir. Doğrusal olmayan programlama modelini düşünün:

(5.2)

Nerede – bilinen işlevler,

A – verilen katsayılar.

Sorunun bu formülasyonunda kısıtlamaların eşitliklerle belirlendiğine ve değişkenlerin negatif olmama koşulunun bulunmadığına dikkat edin. Ayrıca, işlevlerin olduğuna inanıyoruz. birinci kısmi türevleriyle süreklidir.

Koşulları (5.2) eşitliklerin sol veya sağ tarafında olacak şekilde dönüştürelim. sıfır:

(5.3)

Lagrange fonksiyonunu oluşturalım. Katsayılarla sırasıyla alınan amaç fonksiyonunu (5.1) ve kısıtlamaların (5.3) sağ taraflarını içerir. . Problemdeki kısıtlamaların sayısı kadar Lagrange katsayısı olacaktır.

Fonksiyonun (5.4) ekstrem noktaları ekstrem noktalardır orijinal sorun ve bunun tersi de geçerlidir: (5.1)-(5.2) probleminin optimal planı Lagrange fonksiyonunun global uç noktasıdır.

Gerçekten bir çözüm bulunsun (5.1)-(5.2) problemleri varsa, o zaman koşullar (5.3) sağlanır. Planı değiştirelim fonksiyona (5.4) yerleştirin ve eşitliğin (5.5) geçerliliğini doğrulayın.

Bu nedenle, orijinal problem için en uygun planı bulmak amacıyla, Lagrange fonksiyonunun ekstremum için incelenmesi gerekmektedir. Fonksiyon, kısmi türevlerinin eşit olduğu noktalarda uç değerlere sahiptir sıfır. Bu tür noktalara denir sabit.

(5.4) fonksiyonunun kısmi türevlerini tanımlayalım.

,

.

Eşitlemeden sonra sıfır türevleri elde ettiğimiz sistem m+n ile denklemler m+n Bilinmeyen

, (5.6)

İÇİNDE Genel dava(5.6)-(5.7) sistemi için Lagrange fonksiyonunun tüm maksimum ve minimumlarını içeren birkaç çözümümüz olacak. Global maksimum veya minimumu vurgulamak için, bulunan tüm noktalarda amaç fonksiyonunun değerleri hesaplanır. Bu değerlerin en büyüğü global maksimum, en küçüğü ise global minimum olacaktır. Bazı durumlarda ortaya çıkıyor olası kullanım kesin bir ekstremum için yeterli koşullar sürekli fonksiyonlar (aşağıdaki Problem 5.2'ye bakın):

fonksiyonun sürekli ve durağan noktasının bir komşuluğunda (örn. ) iki kez türevlenebilir olmasına izin verin. Daha sonra:

A) Eğer ,(5.8)

o zaman fonksiyonun kesin maksimum noktasıdır;

B) Eğer ,(5.9)

o zaman fonksiyonun kesin minimum noktasıdır;

G ) Eğer ,

o zaman bir ekstremun varlığı sorusu açık kalır.

Ayrıca (5.6)-(5.7) sisteminin bazı çözümleri negatif olabilir. Bu da değişkenlerin ekonomik anlamı ile tutarsızdır. Bu durumda negatif değerleri sıfır değerlerle değiştirmeyi düşünmelisiniz.

Ekonomik anlamda Lagrange çarpanları. Optimum çarpan değeri kriter değerinin ne kadar değişeceğini gösterir Z kaynak arttığında veya azaldığında J bir birim kadar, çünkü

Kısıtların eşitsizlik olduğu durumlarda Lagrange yöntemi de kullanılabilir. Böylece fonksiyonun ekstremumunu bulmak koşullar altında

,

birkaç aşamada gerçekleştirilir:

1. Bir denklem sistemini çözecekleri amaç fonksiyonunun durağan noktalarını belirleyin

.

2. Sabit noktalardan koordinatları koşulları karşılayanları seçin

3. Lagrange yöntemini kullanarak problemi (5.1)-(5.2) eşitlik kısıtlarıyla çözün.

4. Küresel maksimum için ikinci ve üçüncü aşamalarda bulunan noktaları inceleyin: bu noktalardaki amaç fonksiyonunun değerlerini karşılaştırın - en yüksek değer optimal plana karşılık gelir.

Sorun 5.1 Birinci bölümde ele alınan problem 1.3'ü Lagrange yöntemini kullanarak çözelim. Optimum dağıtım su kaynakları matematiksel bir modelle tanımlanır

.

Lagrange fonksiyonunu oluşturalım

Bu fonksiyonun koşulsuz maksimumunu bulalım. Bunu yapmak için kısmi türevleri hesaplıyoruz ve bunları sıfıra eşitliyoruz.

,

Böylece sistemi elde ettik. doğrusal denklemler tür

Denklem sisteminin çözümü, su kaynaklarının sulanan alanlara dağıtımı için en uygun planı temsil eder.

Değerler yüzbinlerle ölçülür metreküp. - yüz bin metreküp sulama suyu başına net gelir miktarı. Dolayısıyla 1 m 3 sulama suyunun marjinal fiyatı şuna eşittir: den. birimler

Sulamadan elde edilecek maksimum ek net gelir

160·12,26 2 +7600·12,26-130·8,55 2 +5900·8,55-10·16,19 2 +4000·16,19=

172391.02 (den. birim)

Sorun 5.2 Doğrusal olmayan bir programlama problemini çözme

Sınırlamayı şu şekilde gösterelim:

.

Lagrange fonksiyonunu oluşturalım ve kısmi türevlerini belirleyelim

.

Lagrange fonksiyonunun durağan noktalarını belirlemek için kısmi türevlerinin sıfıra eşitlenmesi gerekir. Sonuç olarak bir denklem sistemi elde ederiz

Joseph Louis Lagrange, Torino'da (İtalya) İtalyan-Fransız bir ailenin çocuğu olarak dünyaya geldi. Topçu Okulu'nda okudu ve öğretmenlik yaptı. 1759'da Euler'in tavsiyesi üzerine 23 yaşındaki Lagrange, Berlin Bilimler Akademisi üyeliğine seçildi. 1766'da zaten başkanı oldu. Frederick II, Lagrange'ı Berlin'e davet etti. Frederick II'nin 1786'daki ölümünden sonra Lagrange Paris'e taşındı. 1722'den itibaren Paris Bilimler Akademisi üyesiydi, 1795'te Boylam Bürosu üyeliğine atandı ve metrik ölçü sisteminin oluşturulmasında aktif rol aldı. Daire bilimsel araştırma Lagrange alışılmadık derecede genişti. Kendilerini mekaniğe, geometriye adamışlardır. matematiksel analiz, cebir, sayılar teorisi ve teorik astronomi. Lagrange'ın araştırmasının ana yönü, mekanikteki çok çeşitli olayların birleşik bir bakış açısıyla sunulmasıydı. Kuvvetlerin etkisi altındaki herhangi bir sistemin davranışını tanımlayan bir denklem türetmiştir. Astronomi alanında Lagrange istikrar sorununu çözmek için çok şey yaptı Güneş Sistemi; özellikle üçgensel serbest kalma noktalarında bulunan küçük cisimler için bazı özel kararlı hareket durumlarını kanıtladı.

Lagrange yöntemi─ bu bir sorunu çözmek için kullanılan bir yöntemdir koşullu optimizasyonÖrtülü fonksiyonlar olarak yazılan kısıtlamaların amaç fonksiyonu ile yeni bir denklem şeklinde birleştirildiği, Lagrange.

Hadi düşünelim özel durum ortak görev Doğrusal olmayan programlama:

Doğrusal olmayan denklem sistemi verildiğinde (1):

(1) gi(x1,x2,…,xn)=bi (i=1..m),

Fonksiyonun en küçük (veya en büyük) değerini bulun (2)

(2) f(x1,x2,…,xn),

değişkenlerin negatif olmama koşulu yoksa ve f(x1,x2,…,xn) ve gi(x1,x2,…,xn) kısmi türevleriyle birlikte sürekli olan fonksiyonlarsa.

Bu soruna çözüm bulmak için aşağıdaki yöntemi uygulayabilirsiniz: 1. Lagrange çarpanları adı verilen λ1, λ2,…, λm değişkenlerini girin, Lagrange fonksiyonunu oluşturun (3)

(3) F(х1,х2,…,хn, λ1,λ2,…,λm) = f(х1,х2,…,хn)+ λi.

2. Lagrange fonksiyonunun xi ve λi değişkenlerine göre kısmi türevlerini bulun ve bunları sıfıra eşitleyin.

3. Denklem sistemini çözerek problemin amaç fonksiyonunun ekstremum olabileceği noktaları bulun.

4. Uç nokta değil şüpheli olan noktalardan uç noktaya ulaşılan noktaları bulun ve bu noktalardaki fonksiyonun değerlerini hesaplayın .

4. f fonksiyonunun elde edilen değerlerini karşılaştırın ve en iyisini seçin.

Üretim planına göre firmanın 180 adet ürün üretmesi gerekiyor. Bu ürünler iki teknolojik yöntemle üretilebilmektedir. Yöntem I kullanılarak x1 ürün üretilirken maliyetler 4*x1+x1^2 ruble, yöntem II kullanılarak x2 ürün üretilirken ise 8*x2+x2^2 ruble olur. Her yöntemi kullanarak kaç ürün üretilmesi gerektiğini belirleyin, böylece toplam tutarÜretim için minimum düzeydeydi.

Çözüm: Problemin matematiksel formülasyonunu belirlemektir. en düşük değer iki değişkenli fonksiyonlar:

f = 4*x1+x1^2 +8*x2 +x2^2, x1 +x2 = 180 olması koşuluyla.

Lagrange fonksiyonunu oluşturalım:

F(x1,x2,λ) = 4*x1+x1^2+8*x2+x2^2+λ*(180-x1-x2).

Kısmi türevlerini x1, x2, λ'ya göre hesaplayalım ve 0'a eşitleyelim:

λ'yı ilk iki denklemin sağ taraflarına taşıyıp sol taraflarını eşitlersek, 4 + 2*x1 = 8 + 2*x2 veya x1 − x2 = 2 elde ederiz.

Son denklemi x1 + x2 = 180 denklemiyle birlikte çözersek x1 = 91, x2 = 89 buluruz, yani koşulları sağlayan bir çözüm elde etmiş oluruz:

Değişkenlerin bu değerleri için amaç fonksiyonu f'nin değerini bulalım:

F(x1, x2) = 17278

Bu nokta uç bir nokta için şüphelidir. İkinci kısmi türevleri kullanarak (91.89) noktasında f fonksiyonunun minimuma sahip olduğunu gösterebiliriz.

an(t)z(n)(t) + an − 1(t)z(n − 1)(t) + ... + a1(t)z"(t) + a0(t)z(t) = f(t)

genel çözümdeki ck keyfi sabitlerinin değiştirilmesinden oluşur

z(t) = c1z1(t) + c2z2(t) + ...

Cnzn(t)

karşılık gelen homojen denklem

an(t)z(n)(t) + an − 1(t)z(n − 1)(t) + ... + a1(t)z"(t) + a0(t)z(t) = 0

Açık ikincil işlevler Türevleri doğrusal cebir sistemini karşılayan ck(t)

Sistem (1)'in determinantı, z1,z2,...,zn fonksiyonlarının Wronskian'ıdır ve bu, onun .'ye göre benzersiz çözülebilirliğini sağlar.

Entegrasyon sabitlerinin sabit değerlerinde alınan antiderivatifler varsa, o zaman fonksiyon

orijinal doğrusal homojen olmayan diferansiyel denklemin bir çözümüdür. Entegrasyon homojen olmayan denklem karşılık gelen homojen denklemin genel bir çözümünün varlığında, bu nedenle karelere indirgenir.

Lagrange yöntemi (keyfi sabitlerin değişimi yöntemi)

Belirli bir çözüm bulmadan homojen bir denklemin genel çözümünü bilerek, homojen olmayan bir denklemin genel çözümünü elde etmeye yönelik bir yöntem.

N'inci dereceden doğrusal homojen bir diferansiyel denklem için

y(n) + a1(x) y(n-1) + ... + an-1 (x) y" + an(x) y = 0,

burada y = y(x) - bilinmeyen işlev, a1(x), a2(x), ..., an-1(x), an(x) - bilinen, sürekli, doğru: 1) y1(x), y2 denkleminin doğrusal olarak bağımsız n çözümü vardır (x) , ..., yn(x); 2) c1, c2, ..., cn sabitlerinin herhangi bir değeri için, y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) fonksiyonu a'dır denklemin çözümü; 3) herhangi bir x0, y0, y0,1, ..., y0,n-1 başlangıç ​​değeri için c*1, c*n, ..., c*n değerleri vardır, öyle ki y çözümü *(x)= c*1 y1(x) + c*2 y2(x) + ... + c*n yn (x), x = x0'da y*(x0)=y0, (y) başlangıç ​​koşullarını sağlar *)"(x0) =y0,1 , ...,(y*)(n-1)(x0)=y0,n-1.

y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) ifadesi çağrılır genel karar n'inci dereceden doğrusal homojen diferansiyel denklem.

n'inci mertebeden y1(x), y2(x), ..., yn(x) doğrusal homojen diferansiyel denkleminin n doğrusal bağımsız çözüm kümesine denklemin temel çözüm sistemi denir.

Sabit katsayılı bir doğrusal homojen diferansiyel denklem için, temel bir çözüm sistemi oluşturmaya yönelik basit bir algoritma vardır. Denklemin çözümünü y(x) = exp(lx): exp(lx)(n) + a1exp(lx)(n-1) + ... + an-1exp(lx) formunda arayacağız. " + anexp(lx) = = (ln + a1ln-1 + ... + an-1l + an)exp(lx) = 0, yani l sayısı ln + a1ln-1 + karakteristik denkleminin köküdür. .. + an-1l + an = 0. Karakteristik denklemin sol tarafına doğrusal diferansiyel denklemin karakteristik polinomu denir: P(l) = ln + a1ln-1 + ... + an-1l + an. Böylece, sabit katsayılı n'inci dereceden doğrusal homojen bir denklemi çözme sorunu, cebirsel bir denklemin çözümüne indirgenir.

Karakteristik denklemin n farklı gerçek kökü l1№ l2 № ... № ln varsa, bu durumda temel çözüm sistemi y1(x) = exp(l1x), y2(x) = exp(l2x), , fonksiyonlarından oluşur. .., yn (x) = exp(lnx) ve homojen denklemin genel çözümü şöyledir: y(x)= c1 exp(l1x) + c2 exp(l2x) + ... + cn exp(lnx).

basit gerçek kökler durumu için temel bir çözüm sistemi ve genel bir çözüm.

Karakteristik denklemin gerçek köklerinden herhangi biri r kez tekrarlanırsa (r-çoklu kök), o zaman temel çözüm sisteminde buna karşılık gelen r fonksiyon vardır; eğer lk=lk+1 = ... = lk+r-1 ise, denklemin temel çözüm sistemi r fonksiyonlarını içerir: yk(x) = exp(lkx), yk+1(x) = xexp(lkx) ), yk +2(x) = x2exp(lkx), ..., yk+r-1(x) =xr-1 exp(lnx).

ÖRNEK 2. Temel çözüm sistemi ve çoklu reel kökler durumu için genel çözüm.

Karakteristik denklemin karmaşık kökleri varsa, temel çözüm sistemindeki her basit (çokluğu 1 olan) karmaşık kök çifti lk,k+1=ak ± ibk, bir yk(x) = exp(akx) fonksiyon çiftine karşılık gelir cos(bkx), yk+ 1(x) = exp(akx)sin(bkx).

ÖRNEK 4. Basit karmaşık kökler durumu için temel çözüm sistemi ve genel çözüm. Hayali kökler.

Karmaşık bir kök çiftinin r sayısı çokluğuna sahipse, bu durumda böyle bir lk=lk+1 = ... = l2k+2r-1=ak ± ibk çifti, temel çözüm sisteminde exp(akx)cos( fonksiyonlarına karşılık gelir. bkx), exp(akx )sin(bkx), xexp(akx)cos(bkx), xexp(akx)sin(bkx), x2exp(akx)cos(bkx), x2exp(akx)sin(bkx), .. ...... ........ xr-1exp(akx)cos(bkx), xr-1exp(akx)sin(bkx).

ÖRNEK 5. Temel çözüm sistemi ve çoklu karmaşık kökler durumu için genel çözüm.

Dolayısıyla, sabit katsayılı bir doğrusal homojen diferansiyel denklemin genel çözümünü bulmak için: karakteristik denklemin yazılması; l1, l2, ... , ln karakteristik denkleminin tüm köklerini bulun; y1(x), y2(x), ..., yn(x)'in temel çözüm sistemini yazın; y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) genel çözümünün ifadesini yazın. Cauchy problemini çözmek için, genel çözüm ifadesini başlangıç ​​koşullarına koymanız ve doğrusal sistemin çözümleri olan c1,..., cn sabitlerinin değerlerini belirlemeniz gerekir. cebirsel denklemler c1 y1(x0) + c2 y2(x0) + ... + cn yn(x0) = y0, c1 y"1(x0) + c2 y"2(x0) + ... + cn y"n(x0 ) =y0,1, ......... , c1 y1(n-1)(x0) + c2 y2(n-1)(x0) + ... + cn yn(n-1)( x0) = y0,n-1

N'inci dereceden doğrusal homojen olmayan diferansiyel denklem için

y(n) + a1(x) y(n-1) + ... + an-1 (x) y" + an(x) y = f(x),

burada y = y(x) bilinmeyen bir fonksiyondur, a1(x), a2(x), ..., an-1(x), an(x), f(x) bilinmektedir, sürekli, geçerlidir: 1 ) eğer y1(x) ve y2(x) homojen olmayan bir denklemin iki çözümü ise, o zaman y(x) = y1(x) - y2(x) fonksiyonu karşılık gelen homojen denklemin bir çözümüdür; 2) y1(x) homojen olmayan bir denklemin çözümüyse ve y2(x) karşılık gelen homojen denklemin çözümüyse, o zaman y(x) = y1(x) + y2(x) fonksiyonu aşağıdaki denklemin çözümüdür: homojen olmayan denklem; 3) eğer y1(x), y2(x), ..., yn(x) homojen bir denklemin n tane doğrusal bağımsız çözümü ise ve ych(x) - keyfi karar Homojen olmayan denklem, o zaman herhangi bir x0, y0, y0,1, ..., y0,n-1 başlangıç ​​değerleri için c*1, c*n, ..., c*n değerleri vardır, öyle ki çözüm y*(x )=c*1 y1(x) + c*2 y2(x) + ... + c*n yn (x) + ych(x) başlangıç ​​koşullarını sağlar y*(x0)=y0 , ( y*)"(x0)=y0,1 , ...,(y*)(n-1)(x0)=y0,n-1.

y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) + yч(x) ifadesine n'inci mertebeden doğrusal homojen olmayan diferansiyel denklemin genel çözümü denir.

Homojen olmayan problemlerin özel çözümlerini bulmak için diferansiyel denklemler formun sağ tarafında sabit katsayılar olan: Pk(x)exp(ax)cos(bx) + Qm(x)exp(ax)sin(bx), burada Pk(x), Qm(x) polinomlardır derece k ve m Buna göre, belirli bir çözümü oluşturmak için seçim yöntemi adı verilen basit bir algoritma vardır.

Seçim yöntemi veya yöntemi belirsiz katsayılar, Şöyleki. Denklemin gerekli çözümü şu biçimde yazılır: (Pr(x)exp(ax)cos(bx) + Qr(x)exp(ax)sin(bx))xs, burada Pr(x), Qr(x) ) derecesi r = max(k, m) olan ve katsayıları bilinmeyen pr , pr-1, ..., p1, p0, qr, qr-1, ..., q1, q0 polinomlarıdır. xs faktörüne rezonans faktörü denir. Rezonans, karakteristik denklemin kökleri arasında s çokluğunun l =a ± ib kökünün olduğu durumlarda ortaya çıkar. Onlar. karşılık gelen homojen denklemin karakteristik denkleminin kökleri arasında, gerçek kısmı üssün üssündeki katsayı ile çakışacak ve hayali kısmı argümandaki katsayı ile çakışacak şekilde bir tane varsa trigonometrik fonksiyon Denklemin sağ tarafında ve bu kökün çokluğu s ise, gerekli kısmi çözüm bir rezonans faktörü xs içerir. Eğer böyle bir tesadüf yoksa (s=0) rezonans faktörü de yoktur.

Belirli bir çözüm için ifadeyi yerine koymak Sol Taraf Denklemin sağ tarafındaki polinomla aynı formda, katsayıları bilinmeyen genelleştirilmiş bir polinom elde ederiz.

İki genelleştirilmiş polinom ancak ve ancak xtexp(ax)sin(bx), xtexp(ax)cos(bx) formundaki aynı t kuvvetlerine sahip faktörlerin katsayılarının eşit olması durumunda eşittir. Bu faktörlerin katsayılarını eşitleyerek 2(r+1) bilinmeyen için 2(r+1) doğrusal cebirsel denklem sistemi elde ederiz. Böyle bir sistemin tutarlı olduğu ve tek bir çözüme sahip olduğu gösterilebilir.

Çarpan yöntemiLagrange(İngiliz literatüründe “LaGrange'ın belirlenmemiş çarpanlar yöntemi”) ˗, optimizasyon problemlerini çözmek için amaç fonksiyonunun “koşullu” ekstremumunu (minimum veya maksimum değer) belirlemenize olanak tanıyan sayısal bir yöntemdir.

değişkenleri üzerinde eşitlik biçiminde belirtilen kısıtlamaların varlığında (yani izin verilen değerlerin aralığı tanımlanır)

˗ bunlar, fonksiyon değerinin uç noktaya yöneldiği gerçek etki alanındaki fonksiyon argümanının (kontrol edilebilir parametreler) değerleridir. “Koşullu” ekstremum isminin kullanılması değişkenlerin tabi olduğu gerçeğinden kaynaklanmaktadır. ek koşul Bir fonksiyonun ekstremumunu ararken kabul edilebilir değer aralığını sınırlayan.

Lagrange çarpan yöntemi, bir amaç fonksiyonunun koşullu bir ekstremumunu bir dizi kabul edilebilir değer üzerinde arama probleminin, bir fonksiyonun koşulsuz optimizasyon problemine dönüştürülmesine izin verir.

Fonksiyonların olması durumunda Ve kısmi türevleriyle birlikte sürekli ise, o zaman aynı anda sıfıra eşit olmayan ve aşağıdaki koşulun sağlandığı böyle λ değişkenleri vardır:

Böylece, Lagrange çarpanı yöntemine uygun olarak, amaç fonksiyonunun kabul edilebilir değerler kümesindeki ekstremumunu bulmak için, daha da optimize edilen Lagrange fonksiyonunu L(x, λ) oluşturuyorum:

burada λ˗ belirlenmemiş Lagrange çarpanları adı verilen ek değişkenlerin bir vektörüdür.

Böylece, f(x) fonksiyonunun koşullu ekstremumunu bulma problemi, L(x, λ) fonksiyonunun koşulsuz ekstremumunu bulma problemine indirgenmiştir.

Ve

Lagrange fonksiyonunun ekstremumu için gerekli koşul bir denklem sistemi tarafından verilir (sistem “n + m” denklemlerinden oluşur):

Bu denklem sistemini çözmek, L(x, λ) fonksiyonunun değerinin ve ayrıca f(x) hedef fonksiyonunun değerinin uç noktaya karşılık geldiği (X) fonksiyonunun argümanlarını belirlememize olanak tanır.

Lagrange çarpanlarının büyüklüğü (λ), eğer kısıtlamalar denklemde serbest bir terim (sabit) şeklinde sunulursa pratik açıdan ilgi çekicidir. Bu durumda denklem sistemindeki sabitin değerini değiştirerek amaç fonksiyonunun değerini daha da dikkate alabiliriz (arttırabilir/azaltabiliriz). Böylece Lagrange çarpanı, sınırlayıcı sabit değiştiğinde amaç fonksiyonunun maksimumundaki değişim oranını karakterize eder.

Ortaya çıkan fonksiyonun ekstremumunun doğasını belirlemenin birkaç yolu vardır:

Birinci yöntem: Uç noktanın koordinatları ve amaç fonksiyonunun karşılık gelen değeri olsun. Noktaya yakın bir nokta alınır ve amaç fonksiyonunun değeri hesaplanır:

Eğer , o zaman noktada bir maksimum vardır.

Eğer , o zaman bu noktada bir minimum vardır.

İkinci yöntem: Ekstremun doğasının belirlenebileceği yeterli koşul, Lagrange fonksiyonunun ikinci diferansiyelinin işaretidir. Lagrange fonksiyonunun ikinci diferansiyeli şu şekilde tanımlanır:

Eğer içindeyse verilen nokta minimum, eğer , o zaman amaç fonksiyonu f(x)'in koşullu bir değeri vardır maksimum.

Üçüncü yöntem: Ayrıca Lagrange fonksiyonunun Hessian'ı dikkate alınarak fonksiyonun ekstremumunun doğası belirlenebilir. Hessian matrisi simetriktir Kare matris bir fonksiyonun matris elemanlarının ana köşegen etrafında simetrik olduğu noktadaki ikinci kısmi türevleri.

Ekstremum tipini (bir fonksiyonun maksimumu veya minimumu) belirlemek için Sylvester kuralını kullanabilirsiniz:

1. Lagrange fonksiyonunun ikinci diferansiyelinin pozitif işaretli olabilmesi için fonksiyonun açısal küçüklerinin pozitif olması gerekir. Bu koşullar altında bu noktadaki fonksiyonun minimumu vardır.

2. Lagrange fonksiyonunun ikinci diferansiyelinin işaret olarak negatif olabilmesi için fonksiyonun açısal küçüklerinin değişmesi ve matrisin ilk elemanının negatif olması gerekir. Bu koşullar altında bu noktadaki fonksiyonun maksimumu vardır.

Açısal minör ile orijinal matrisin ilk k satırında ve k sütununda yer alan minörü kastediyoruz.

Temel bilgiler pratik önemi Lagrange yöntemi, koşullu optimizasyondan koşulsuz optimizasyona geçmenize ve buna göre cephaneliği genişletmenize olanak sağlamasıdır. mevcut yöntemler Sorunu çözmek. Bununla birlikte, bir denklem sistemini çözme sorunu, Bu method Genel durumda, bir ekstremum bulma probleminden daha basit değildir. Bu tür yöntemlere dolaylı denir. Kullanımları, aşırı bir soruna analitik biçimde (örneğin, belirli teorik hesaplamalar için) bir çözüm elde etme ihtiyacı ile açıklanmaktadır. Belirli çözerken pratik problemler Optimize edilen fonksiyonların değerlerinin hesaplanması ve karşılaştırılması için yinelemeli işlemlere dayanan doğrudan yöntemler genellikle kullanılır.

Hesaplama yöntemi

1 adım: Lagrange fonksiyonunu verilen amaç fonksiyonundan ve kısıtlama sisteminden belirleriz:

İleri

Yorumunuzu yazıya eklemek için lütfen siteye kayıt olunuz.

• öğretici

Herkes İyi günler. Bu yazıda bunlardan birini göstermek istiyorum grafik yöntemleri yapı Matematiksel modellerİçin dinamik sistemler buna denir bağ grafiği(“bağ” - bağlantılar, “grafik” - grafik). Rus edebiyatında bu yöntemin açıklamalarını yalnızca Tomsk Politeknik Üniversitesi A.V. Ders Kitabı'nda buldum. Voronin “MEKATRONİK SİSTEMLERİN MODELLENMESİ” 2008 Ayrıca 2. tür Lagrange denklemi aracılığıyla klasik yöntemi gösterir.

Lagrange yöntemi

Teoriyi anlatmayacağım, hesaplamaların aşamalarını göstereceğim ve küçük yorumlar. Şahsen benim için örneklerden öğrenmek, teoriyi 10 kez okumaktan daha kolaydır. Bana öyle geldi ki, Rus edebiyatında bu yöntemin açıklaması ve aslında genel olarak matematik veya fizik, karmaşık formüller açısından çok zengindir ve bu nedenle ciddi bir matematik arka planı gerektirir. Lagrange yöntemini çalışırken (İtalya Torino Politeknik Üniversitesi'nde okuyorum), hesaplama yöntemlerini karşılaştırmak için Rus edebiyatı okudum ve bu yöntemi çözme sürecini takip etmek benim için zordu. Kharkov Havacılık Enstitüsü'ndeki modelleme derslerini hatırlasak bile, bu tür yöntemlerin türetilmesi oldukça zahmetliydi ve kimse bu konuyu anlamaya çalışma zahmetine girmemişti. Lagrange'a göre matematiksel modeller oluşturmak için bir kılavuz yazmaya karar verdim, çünkü bunun hiç de zor olmadığı ortaya çıktı, zamana ve kısmi türevlere göre türevlerin nasıl hesaplanacağını bilmek yeterli. Daha karmaşık modeller için rotasyon matrisleri de eklenir, ancak bunlarda da karmaşık hiçbir şey yoktur.

Modelleme yöntemlerinin özellikleri:

• Newton-Euler: Dinamik dengeye dayalı vektör denklemleri güç Ve anlar
• Lagrange: kinetik ve potansiyel ile ilişkili durum fonksiyonlarına dayalı skaler denklemler enerjiler
• Tahvil Sayımı: akışa dayalı yöntem güç sistem elemanları arasında

İle başlayalım basit örnek. Yaylı ve sönümleyicili kütle. Yer çekimi kuvvetini görmezden geliyoruz.

Şekil 1. Yaylı ve sönümleyicili kütle

Her şeyden önce şunları belirliyoruz:

• başlangıç ​​sistemi koordinatlar(NSK) veya sabit sk R0(i0,j0,k0). Nerede? Parmağınızı gökyüzüne doğrultabilirsiniz, ancak beyindeki nöronların uçlarını hareket ettirerek, NSC'yi M1 gövdesinin hareket çizgisine yerleştirme fikri ortaya çıkar.
• kütleli her cisim için koordinat sistemleri(M1'imiz var R1(i1,j1,k1)), yönelim keyfi olabilir, ancak neden hayatınızı karmaşıklaştırın, onu NSC'den minimum farkla ayarlayın
• genelleştirilmiş koordinatlar q_i(hareketi açıklayabilecek minimum değişken sayısı), bu örnekte tek bir genelleştirilmiş koordinat, yalnızca j ekseni boyunca hareket

İncir. 2. Koordinat sistemlerini ve genelleştirilmiş koordinatları yazdık

Şek. 3. M1 gövdesinin konumu ve hızı

Daha sonra aşağıdaki formülleri kullanarak damperin kinetik (C) ve potansiyel (P) enerjilerini ve enerji tüketen fonksiyonunu (D) bulacağız:

Şekil 4. Tam formül kinetik enerji

Örneğimizde döndürme yoktur, ikinci bileşen 0'dır.

Şekil 5. Kinetik, potansiyel enerji ve enerji tüketen fonksiyonun hesaplanması

Lagrange denklemi aşağıdaki forma sahiptir:

Şekil 6. Lagrange Denklemi ve Lagrange Denklemi

Delta W_i Bu sanal çalışma uygulanan kuvvetler ve momentlerle mükemmelleştirilmiştir. Onu bulalım:

Şekil 7. Sanal işin hesaplanması

Nerede delta q_1 sanal hareket.

Her şeyi Lagrange denkleminde yerine koyarız:

Şekil 8. Ortaya çıkan yaylı ve sönümleyicili kütle modeli

Lagrange'ın yönteminin sona erdiği yer burasıdır. Gördüğünüz gibi o kadar da karmaşık değil ama yine de oldukça basit bir örnek; bunun için Newton-Euler yönteminin daha da basit olması muhtemeldir. Birbirine göre döndürülen birkaç gövdenin olacağı daha karmaşık sistemler için farklı açı Lagrange'ın yöntemi daha kolay olacaktır.

Bağ grafiği yöntemi

Kütle, yay ve sönümleyici örneği için bağ grafiğinde modelin nasıl göründüğünü size hemen göstereceğim:

Şekil 9. Yaylı ve sönümleyicili bağ grafiği kütleleri

Burada küçük bir teori anlatmanız gerekecek, bu da inşa etmek için yeterli olacak basit modeller. İlgilenenler kitabı okuyabilir ( Bond Grafiği Metodolojisi) veya ( Voronin A.V. Mekatronik sistemlerin modellenmesi: öğretici. – Tomsk: Tomsk Politeknik Üniversitesi Yayınevi, 2008).

Öncelikle şunu belirleyelim karmaşık sistemler birçok alan adından oluşur. Örneğin bir elektrik motoru, elektrikli ve mekanik parçalardan veya alanlardan oluşur.

bağ grafiği bu alanlar, alt sistemler arasındaki güç alışverişine dayanır. Hangi biçimde olursa olsun güç değişiminin her zaman iki değişken tarafından belirlendiğini unutmayın ( değişken güç) yardımıyla dinamik bir sistem içindeki çeşitli alt sistemlerin etkileşimini inceleyebiliriz (tabloya bakınız).

Tablodan da görüleceği üzere iktidarın ifadesi hemen hemen her yerde aynıdır. Özetle, Güç- Bu iş " akış - f" Açık " çaba - e».

Bir çaba(İngilizce) çaba) elektriksel alanda bu voltajdır (e), mekanik alanda kuvvet (F) veya torktur (T), hidrolikte ise basınçtır (p).

Akış(İngilizce) akış) elektrik alanında akım (i), mekanik alanda hız (v) veya açısal hız (omega), hidrolikte akışkanın akışı veya akış hızıdır (Q).

Bu gösterimleri alarak güç için bir ifade elde ederiz:

Şekil 10. Güç değişkenleri aracılığıyla güç formülü

Bağ-grafik dilinde, güç alışverişinde bulunan iki alt sistem arasındaki bağlantı bir bağ ile temsil edilir. bağlamak). Bu yüzden bu yönteme denir bağ grafiği veya g raf bağlantıları, bağlantılı grafik. Hadi düşünelim blok şeması elektrik motorlu bir modeldeki bağlantılar (bu henüz bir bağ grafiği değil):

Şekil 11. Etki alanları arasındaki güç akışının blok diyagramı

Bir voltaj kaynağımız varsa, buna göre voltaj üretir ve onu sarım için motora aktarır (bu nedenle ok motora doğru yönlendirilir), sarımın direncine bağlı olarak Ohm yasasına göre bir akım ortaya çıkar (yönlendirilmiş). motordan kaynağa). Buna göre değişkenlerden biri alt sisteme girdidir, ikincisi ise çıkış alt sistemden. Burada voltaj ( çaba) – giriş, akım ( akış) - çıkış.

Güncel bir kaynak kullanırsanız diyagram nasıl değişecek? Sağ. Akım motora, voltaj ise kaynağa yönlendirilecektir. Daha sonra akım ( akış) - Giriş gerilimi ( çaba) - çıkış.

Mekanikteki bir örneğe bakalım. Bir kütleye etki eden kuvvet.

Şekil 12. Kütleye uygulanan kuvvet

Blok şeması aşağıdaki gibi olacaktır:

Şekil 13. Blok şeması

Bu örnekte, Güç ( çaba) – kütle için giriş değişkeni. (Kütleye uygulanan kuvvet)
Newton'un ikinci yasasına göre:

Kütle hızla yanıt verir:

Bu örnekte, eğer bir değişken ( güç - çaba) dır-dir giriş mekanik alana, ardından başka bir güç değişkenine ( hız - akış) – otomatik olarak olur çıkış.

Girişin nerede olduğunu ve çıkışın nerede olduğunu ayırt etmek için kullanılır. dikey çizgi elemanlar arasındaki okun (bağlantının) sonundaki bu çizgiye denir nedensellik işareti veya nedensellik (nedensellik). Görünen o ki: uygulanan kuvvet sebep, hız ise sonuçtur. Bu işaret, bir sistem modelinin doğru inşası için çok önemlidir, çünkü nedensellik, iki alt sistemin fiziksel davranışının ve güç alışverişinin bir sonucudur, bu nedenle nedensellik işaretinin konumunun seçimi keyfi olamaz.

Şekil 14. Nedenselliğin belirlenmesi

Bu dikey çizgi hangi alt sistemin kuvveti aldığını gösterir ( çaba) ve sonuç olarak bir akış üretir ( akış). Kütleli örnekte şöyle olacaktır:

Şekil 14. Kütleye etki eden kuvvetin nedensel ilişkisi

Oktan kütle girişinin olduğu açıkça görülüyor - güç ve çıktı hız. Bu, diyagramı oklarla karıştırmamak ve modelin yapısını sistematikleştirmemek için yapılır.

Sonraki önemli nokta. Genelleştirilmiş dürtü(hareket miktarı) ve hareketli(enerji değişkenleri).

Farklı alanlardaki güç ve enerji değişkenleri tablosu

Yukarıdaki tabloda bağ-grafik yönteminde kullanılan iki ek fiziksel büyüklük tanıtılmaktadır. Onlar aranmaktadır genelleştirilmiş dürtü (R) Ve genelleştirilmiş hareket (Q) veya enerji değişkenleri ve güç değişkenlerinin zaman içinde entegre edilmesiyle elde edilebilirler:

Şekil 15. Güç ve enerji değişkenleri arasındaki ilişki

Elektrik alanında :

Faraday yasasına dayanarak, Gerilim iletkenin uçlarındaki bu iletken boyunca manyetik akının türevine eşittir.

A Mevcut güç - fiziksel miktar, bir t zamanında iletkenin kesitinden geçen Q yük miktarının bu zaman aralığının değerine oranına eşittir.

Mekanik alan:

Newton'un 2. yasasından, Güç– dürtünün zamana göre türevi

Ve buna bağlı olarak, hız- yer değiştirmenin zamana göre türevi:

Özetleyelim:

Basit elementler

Dinamik sistemlerdeki tüm elemanlar iki kutuplu ve dört kutuplu bileşenlere ayrılabilir.
Hadi düşünelim iki kutuplu bileşenler:

Kaynaklar
Hem çabanın hem de akışın kaynakları vardır. Elektrik alanındaki analoji: çabanın kaynağı – voltaj kaynağı, akış kaynağı – akım kaynağı. Kaynaklara ilişkin nedensel işaretler ancak bu şekilde olmalıdır.

Şekil 16. Nedensel bağlantılar ve kaynakların belirlenmesi

Bileşen R – enerji tüketen eleman

Bileşen I – eylemsizlik elemanı

Bileşen C – kapasitif eleman

Şekillerden de görüldüğü gibi aynı şeyin farklı unsurları R,C,I yazın aynı denklemlerle tanımlanır. YALNIZCA elektriksel kapasitans için bir fark vardır, sadece bunu hatırlamanız gerekir!

Dört kutuplu bileşenler:

İki bileşene bakalım: bir transformatör ve bir jiratör.

Son önemli bileşenler Bağ-grafik yönteminde bağlantılar kullanılır. İki tür düğüm vardır:

Bileşenlerde bu kadar.

Bir bağ grafiği oluşturduktan sonra nedensel ilişkiler kurmanın ana adımları:

1. Herkese nedensel bağlantılar verin kaynaklar
2. Tüm düğümleri gözden geçirin ve nedensel ilişkileri 1. noktadan sonra yazın
3. İçin bileşenler ben için bir girdi nedensel ilişkisi atayın (çaba bu bileşene dahildir), C bileşenleriçıktı nedenselliğini atayın (çaba bu bileşenden kaynaklanır)
4. 2. noktayı tekrarlayın
5. Nedensel bağlantılar ekleyin R bileşenleri

Bu, teoriye ilişkin mini kursu sonlandırıyor. Artık modeller oluşturmak için ihtiyacımız olan her şeye sahibiz.
Birkaç örnek çözelim. İle başlayalım elektrik devresi bağ grafiği oluşturmanın benzetmesini anlamak daha iyidir.

örnek 1

Gerilim kaynağıyla bir bağ grafiği oluşturmaya başlayalım. Sadece Se yazın ve bir ok koyun.

Bakın her şey çok basit! Daha ileriye bakalım, R ve L seri olarak bağlanmıştır, bu da güç değişkenleri açısından konuşursak, içlerinde aynı akımın aktığı anlamına gelir - aynı akış. Hangi düğüm aynı akışa sahip? Doğru cevap 1 düğümdür. Kaynağı, direnci (bileşen - R) ve endüktansı (bileşen - I) 1 düğüme bağlarız.

Daha sonra paralel olarak kapasitans ve direncimiz var, bu da aynı gerilime veya kuvvete sahip oldukları anlamına gelir. 0 düğümü başka hiçbir şeye benzemez. Kapasitansı (bileşen C) ve direnci (bileşen R) 0 düğümüne bağlarız.

Ayrıca 1 ve 0 nolu düğümleri birbirine bağlarız. Okların yönü keyfi olarak seçilir; bağlantının yönü yalnızca denklemlerdeki işareti etkiler.

Aşağıdaki bağlantı grafiğini alacaksınız:

Artık nedensel ilişkiler kurmamız gerekiyor. Yerleştirme sırasına ilişkin talimatları izleyerek kaynakla başlayalım.

1. Bir voltaj kaynağımız (çaba) var, böyle bir kaynağın yalnızca bir nedensellik seçeneği var - çıktı. Hadi giyelim.
2. Sonra bileşen I var, bakalım ne tavsiye edecekler. Koyduk
3. Bunu 1 düğüme indirdik. Yemek yemek
4. 0 düğümlü bir giriş ve tüm çıkış nedensel bağlantılarına sahip olmalıdır. Şimdilik bir gün tatilimiz var. C veya I bileşenlerini arıyoruz. Bulduk. Koyduk
5. Geriye kalanları listeleyelim

Bu kadar. Bond grafiği oluşturulur. Yaşasın, Yoldaşlar!

Geriye sadece sistemimizi tanımlayan denklemleri yazmak kalıyor. Bunu yapmak için 3 sütunlu bir tablo oluşturun. Birincisi sistemin tüm bileşenlerini içerecek, ikincisi her bir öğe için giriş değişkenini içerecek ve üçüncüsü aynı bileşen için çıkış değişkenini içerecektir. Girdi ve çıktıyı nedensel ilişkilerle zaten tanımladık. Yani herhangi bir sorun olmaması gerekiyor.

Seviyeleri kaydetme kolaylığı için her bağlantıyı numaralandıralım. Her element için denklemleri C, R, I bileşenleri listesinden alıyoruz.

Bir tablo derleyerek belirleriz durum değişkenleri, bu örnekte bunlardan 2 tane var, p3 ve q5. Daha sonra durum denklemlerini yazmanız gerekir:

İşte bu, model hazır.

Örnek 2. Fotoğrafın kalitesinden dolayı hemen özür dilemek istiyorum, asıl önemli olan okuyabilmeniz

Lagrange yöntemini kullanarak çözdüğümüz mekanik sistem için başka bir örneği çözelim. Yorum yapmadan çözümü göstereceğim. Bu yöntemlerden hangisinin daha basit ve daha kolay olduğunu kontrol edelim.

Matbala'da Lagrange yöntemi ve bağ grafiği ile elde edilen aynı parametrelere sahip her iki matematiksel model de derlendi. Sonuç aşağıdadır: Etiket ekle