Belirsiz çarpanların Lagrange yönteminin ispatı. Lagrange Belirsiz Çarpan Yöntemi

Sorunu ele alalım koşullu optimizasyon yalnızca eşitlik biçimindeki kısıtlamaları içeren

dk.

kısıtlamalara tabi

,
.

Prensip olarak bu problem, verilen eşitlikler kullanılarak m bağımsız değişkenin amaç fonksiyonundan çıkarılmasıyla elde edilen kısıtsız bir optimizasyon problemi olarak çözülebilir. Eşitlik biçimindeki kısıtlamaların varlığı aslında boyutu azaltmanıza olanak tanır orijinal sorun. Yeni görev uygun bir kısıtsız optimizasyon yöntemi kullanılarak çözülebilir.

Örnek. Fonksiyonu en aza indirmek gerekir

sınırlı olduğunda

Değişkeni hariç tutarak Denklemi kullanarak, kısıtlama olmaksızın iki değişkenli bir optimizasyon problemi elde ederiz:

küçültmek ,

koşulsuz optimizasyon yöntemlerinden biri kullanılarak çözülebilir.

Ancak değişkenlerin eliminasyonu yöntemi yalnızca kısıtları temsil eden denklemlerin belirli bir değişken kümesine göre çözülebildiği durumlarda uygulanabilir. Eşitlik şeklinde çok sayıda kısıtlama varsa değişkenlerin ortadan kaldırılması süreci oldukça emek yoğun bir prosedür haline gelir. Ayrıca denklemin bir değişkene göre çözülemediği durumlar da olabilir. Bu durumda Lagrange çarpanı yönteminin kullanılması tavsiye edilir.

Lagrange çarpanı yöntemini kullanarak, eşitlik kısıtlamaları olan optimizasyon problemlerinde optimum noktaların belirlenmesine olanak sağlamak için gerekli koşullar esas olarak oluşturulur.

Sorunu ele alalım

dk.

kısıtlamalara tabi

,
.

Kurstan matematiksel analiz fonksiyonun koşullu minimum noktasının olduğu iyi bilinmektedir. Lagrange fonksiyonunun eyer noktasıyla çakışır:

,

bu durumda eyer noktası değişkenler açısından minimumu sağlamalıdır ve maksimum parametreler . Bu parametrelere Lagrange çarpanları denir. Fonksiyonların kısmi türevlerini eşitleme İle ve tarafından sıfıra ulaşırız gerekli koşullar sabit nokta:

,
,

,
.

Sistem çözümü
denklemler Lagrange fonksiyonunun durağan noktasını belirler. Orijinal problemin minimumunun varlığı için yeterli koşullar, yukarıda bahsedilenlere ek olarak Hessian matrisinin pozitif tanımlılığını da içerir. amaç fonksiyonu.

4.2. Coon-tucker koşulları

Sorunun olmadığını düşünelim doğrusal programlama eşitsizlik biçimindeki kısıtlamalarla

dk.

kısıtlamalar altında

,
.

Eşitsizlik şeklindeki kısıtları her birine zayıflatan değişkenler ekleyerek eşitlik kısıtlarına indirgeyelim. ,
:

.

Lagrange fonksiyonunu oluşturalım:

Daha sonra minimum için gerekli koşullar şu şekli alır:

,
;

,
;

,
.

Son denklemi şu şekilde çarpabilirsiniz: ve zayıflatıcı değişkenleri ikinci denklemden ifade ederek değiştirin. İkinci denklem, zayıflatıcı değişkenlerin atılması ve eşitsizlik kısıtlamalarına geçilmesiyle dönüştürülebilir. Bir koşul daha eklenmeli
Koşullu minimum noktada yerine getirilmesi gereken.

Son olarak, Kuhn-Tucker koşulları adı verilen, eşitsizlik kısıtlamalarına sahip minimum doğrusal olmayan programlama probleminin varlığı için gerekli koşulları elde ederiz:

,
; (1)

,
; (2)

,
; (3)

,
. (4)

Eşitsizlik kısıtlaması
bir noktada aktif olarak adlandırılır eğer eşitliğe dönüşürse
ve eğer aktif değilse denir
. Problemi doğrudan çözmeden önce, optimum noktada aktif olmayan kısıtların tespit edilmesi mümkünse, bu kısıtlar modelin dışında tutularak modelin boyutu küçültülebilir.

Denklem (3) şu anlama gelir:
, veya
. Eğer
, O
ve kısıtlama aktiftir ve bir eşitlik kısıtlamasını temsil eder. Öte yandan, eğer kısıtlama katı bir eşitsizlik ise
, o zaman Lagrange çarpanı şu forma sahip olacaktır:
onlar. sınırlama
etkin değildir ve göz ardı edilebilir. Elbette hangi kısıtlamaların ihmal edilebileceği önceden bilinmemektedir.

Lagrange çarpan yöntemi.

Lagrange çarpanı yöntemi doğrusal olmayan programlama problemlerini çözmenize olanak sağlayan yöntemlerden biridir.

Doğrusal olmayan programlama bir bölümdür matematiksel programlama, doğrusal olmayan bir amaç fonksiyonu ve doğrusal olmayan kısıtlamalarla tanımlanan uygun çözümlerin bir bölgesi ile ekstrem problemleri çözme yöntemlerinin incelenmesi. Ekonomide bu, sonuçların (verimliliğin), kaynak kullanımı ölçeğindeki (veya aynı anlama gelen üretim ölçeğindeki) değişikliklerle orantısız bir şekilde artması veya azalması gerçeğine karşılık gelir: örneğin, üretim maliyetlerinin üretim ölçeğindeki bölünmesi nedeniyle. işletmeleri değişken ve yarı sabit olarak ikiye ayırıyoruz; mallara olan talebin doygunluğu nedeniyle, sonraki her birimin satışının bir öncekinden daha zor olması vb.

Doğrusal olmayan programlama problemi, belirli bir amaç fonksiyonunun optimumunu bulma problemi olarak ortaya konmuştur.

F(x 1 ,…xn), F (X) → maksimum

koşullar karşılandığında

g j (x 1 ,…x n)≥0, G (X) ≤ B , X ≥ 0

Nerede X-gerekli değişkenlerin vektörü;

F (X) -amaç fonksiyonu;

G (X) - kısıtlama fonksiyonu (sürekli türevlenebilir);

B - kısıtlama sabitlerinin vektörü.

Doğrusal olmayan bir programlama probleminin çözümü (küresel maksimum veya minimum), kabul edilebilir kümenin sınırına veya iç kısmına ait olabilir.

Doğrusal programlama probleminden farklı olarak, doğrusal olmayan programlama probleminde optimumun mutlaka kısıtlamalarla tanımlanan bölgenin sınırında olması gerekmez. Başka bir deyişle görev, belirli bir fonksiyonun maksimum (veya minimum) elde edildiği, eşitsizlikler biçimindeki bir kısıtlama sistemine tabi olan değişkenlerin bu tür negatif olmayan değerlerini seçmektir. Bu durumda ne amaç fonksiyonunun ne de eşitsizliklerin formları belirtilmez. Olabilir farklı durumlar: amaç fonksiyonu doğrusal değildir ve kısıtlamalar doğrusaldır; amaç fonksiyonu doğrusaldır ve kısıtlamalar (bunlardan en az biri) doğrusal değildir; hem amaç fonksiyonu hem de kısıtlamalar doğrusal değildir.

Doğrusal olmayan programlama problemi şu şekilde ortaya çıkar: Doğa Bilimleri, teknoloji, ekonomi, matematik, iş ilişkileri ve hükümet bilimi.

Örneğin doğrusal olmayan programlama temel bir ekonomik sorunla ilgilidir. Dolayısıyla, sınırlı kaynakların tahsisi probleminde, ya verimlilik, ya da eğer tüketici inceleniyorsa, kaynak kıtlığı koşullarını ifade eden kısıtlamaların varlığında tüketim maksimuma çıkarılmaktadır. Böyle genel bir formülasyonda problemin matematiksel formülasyonu imkansız olabilir, ancak özel uygulamalarda tüm fonksiyonların niceliksel formu doğrudan belirlenebilir. Örneğin, sanayi kuruluşu plastik ürünler üretmektedir. Burada üretim verimliliği kârla ölçülür ve kısıtlamalar mevcut işgücü, üretim alanı, ekipman verimliliği vb. olarak yorumlanır.

Maliyet etkinliği yöntemi aynı zamanda doğrusal olmayan programlama şemasına da uyar. Bu method Hükümette karar almada kullanılmak üzere geliştirildi. Genel işlev verimlilik refahtır. Burada doğrusal olmayan iki programlama problemi ortaya çıkıyor: Birincisi sınırlı maliyetlerle etkiyi maksimuma çıkarmak, ikincisi ise etkinin belirli bir minimum seviyenin üzerinde olması koşuluyla maliyetleri minimuma indirmek. Bu problem genellikle doğrusal olmayan programlama kullanılarak iyi bir şekilde modellenir.

Doğrusal olmayan bir programlama problemini çözmenin sonuçları, hükümet kararlarının alınmasında faydalıdır. Ortaya çıkan çözüm elbette tavsiye edilir, dolayısıyla nihai bir karar vermeden önce doğrusal olmayan programlama probleminin varsayımlarını ve doğruluğunu incelemek gerekir.

Doğrusal olmayan problemler karmaşıktır; genellikle doğrusal olanlara yol açarak basitleştirilirler. Bunu yapmak için geleneksel olarak belirli bir alanda amaç fonksiyonunun bağımsız değişkenlerdeki değişimle orantılı olarak arttığı veya azaldığı varsayılır. Bu yaklaşıma parçalı doğrusal yaklaşımlar yöntemi denir; ancak yalnızca belirli türdeki doğrusal olmayan problemlere uygulanabilir.

Doğrusal olmayan problemler belirli koşullar Lagrange fonksiyonu kullanılarak çözülür: bulduktan sonra Eyer noktası böylece soruna çözüm bulunur. Bilimsel araştırmalara yönelik hesaplamalı algoritmalar arasında gradyan yöntemleri büyük bir yer tutar. Doğrusal olmayan problemler için evrensel bir yöntem yoktur ve son derece çeşitli oldukları için görünüşe göre de olmayabilir. Multiekstremal problemlerin çözümü özellikle zordur.

Doğrusal olmayan bir programlama problemini bir denklem sisteminin çözümüne indirgemenizi sağlayan yöntemlerden biri, belirsiz çarpanların Lagrange yöntemidir.

Lagrange çarpanı yöntemini kullanarak, eşitlik kısıtlamaları olan optimizasyon problemlerinde optimum noktaların belirlenmesine olanak sağlamak için gerekli koşullar esas olarak oluşturulur. Bu durumda, kısıtlı problem, Lagrange çarpanları adı verilen bazı bilinmeyen parametreleri içeren eşdeğer bir koşulsuz optimizasyon problemine dönüştürülür.

Lagrange çarpanı yöntemi, problemleri azaltmayı içerir. koşullu aşırı koşulsuz bir ekstremumdaki problemlere yardımcı fonksiyon- Lafta Lagrange fonksiyonları.

Bir fonksiyonun ekstremum problemi için F(x 1, x 2,..., x n) koşullar altında (kısıt denklemleri) φ Ben(x 1 , x 2 , ..., x n) = 0, Ben= 1, 2,..., M Lagrange fonksiyonu şu şekle sahiptir:

L(x 1, x 2… x n,λ 1, λ 2,…λm)=f(x 1, x 2… x n)+∑ i -1 m λ ben φ i (x 1, x 2… x n)

Çarpanlar λ 1 , λ 2 , ..., λm isminde Lagrange çarpanları.

Eğer değerler x 1 , x 2 , ..., x n , λ 1 , λ 2 , ..., λm Lagrange fonksiyonunun durağan noktalarını belirleyen denklemlerin çözümlerinin özü, yani diferansiyellenebilir fonksiyonlar için denklem sisteminin çözümleridir

bu durumda, oldukça genel varsayımlar altında, x 1 , x 2 , ..., x n f fonksiyonunun bir ekstremumunu sağlar.

Eşitlik biçiminde bir kısıtlamaya tabi olan n değişkenli bir fonksiyonu en aza indirme problemini düşünün:

f(x 1, x 2… x n)'yi en aza indirin (1)

h 1 (x 1, x 2… x n)=0 (2) kısıtlamaları altında

Lagrange çarpanı yöntemine göre bu problem aşağıdaki kısıtsız optimizasyon problemine dönüştürülür:

L(x,λ)=f(x)-λ*h(x)'i en aza indir (3)

L(x;λ) Fonksiyonuna Lagrange fonksiyonu denir,

λ, Lagrange çarpanı adı verilen bilinmeyen bir sabittir. λ işareti için herhangi bir gereklilik yoktur.

Belirli bir λ=λ 0 değeri için, L(x,λ) fonksiyonunun x'e göre koşulsuz minimumunun x=x 0 noktasında elde edilmesine ve x 0'ın h 1 (x 0)=0 denklemini sağlamasına izin verin. . Daha sonra, görülmesi kolay olduğu gibi, x 0, (2)'yi hesaba katarak (1)'i en aza indirir, çünkü x'in (2) tatmin edici tüm değerleri için h 1 (x)=0 ve L(x,λ)=min f(x).

Elbette, koşulsuz minimum nokta x 0'ın koordinatının eşitliği (2) sağlaması için λ=λ 0 değerini seçmek gereklidir. Bu, λ'yı bir değişken olarak dikkate alarak, fonksiyonun (3) koşulsuz minimumunu λ fonksiyonu biçiminde bulursanız ve ardından eşitliğin (2) sağlandığı λ değerini seçerseniz yapılabilir. Bunu spesifik bir örnekle açıklayalım.

En aza indirge f(x)=x 1 2 +x 2 2 =0

h 1 (x)=2x 1 +x 2 -2=0=0 kısıtı altında

Karşılık gelen kısıtsız optimizasyon problemi şu şekilde yazılır:

en aza indirgemek L(x,λ)=x 1 2 +x 2 2 -λ(2x 1 +x 2 -2)

Çözüm. L gradyanının iki bileşenini sıfıra eşitleyerek şunu elde ederiz:

→ x 1 0 =λ

→ x 2 0 =λ/2

Sabit x° noktasının minimuma karşılık gelip gelmediğini kontrol etmek için, x'in bir fonksiyonu olarak kabul edilen L(x;u) fonksiyonunun Hessian matrisinin elemanlarını hesaplıyoruz,

bunun pozitif tanımlı olduğu ortaya çıkıyor.

Bu, L(x,u)'nun x'in dışbükey bir fonksiyonu olduğu anlamına gelir. Sonuç olarak, x 1 0 =λ, x 2 0 =λ/2 koordinatları global minimum noktayı belirler. Optimum değerλ, x 1 0 ve x 2 0 değerlerinin 2x 1 + x 2 =2 denkleminde değiştirilmesiyle bulunur; buradan 2λ+λ/2=2 veya λ 0 =4/5 olur. Böylece koşullu minimuma x 1 0 =4/5 ve x 2 0 =2/5'te ulaşılır ve min f(x) = 4/5'e eşittir.

Örnek problemi çözerken, L(x;λ)'yi iki değişken x 1 ve x 2'nin bir fonksiyonu olarak ele aldık ve ayrıca λ parametresinin değerinin kısıtlamanın karşılanacağı şekilde seçildiğini varsaydık. Sistemin çözümü ise

J=1,2,3,…,n

λ açık fonksiyonlar şeklinde elde edilemiyorsa, n+1 bilinmeyenli n+1 denklemden oluşan aşağıdaki sistemin çözülmesiyle x ve λ değerleri bulunur:

J=1,2,3,…,n., h 1 (x)=0

Herkesi bulmak için Muhtemel çözümler Bu sistem sayısal arama yöntemlerini (örneğin Newton yöntemi) kullanabilir. Çözümlerin her biri için (), x'in bir fonksiyonu olarak kabul edilen L fonksiyonunun Hessian matrisinin elemanlarını hesaplamalı ve bu matrisin pozitif tanımlı (yerel minimum) veya negatif tanımlı (yerel maksimum) olup olmadığını bulmalıyız. ).

Lagrange çarpanı yöntemi, problemin eşitlikler şeklinde çeşitli kısıtlamalara sahip olduğu duruma genişletilebilir. gerektiren genel bir problem düşünün.

f(x)'i en aza indirin

h k =0, k=1, 2, ..., K kısıtlamaları altında.

Lagrange fonksiyonu aşağıdaki formu alır:

Burada λ 1 , λ 2 , ..., λk-Lagrange çarpanları, yani değerlerinin belirlenmesi gereken bilinmeyen parametreler. L'nin x'e göre kısmi türevlerini sıfıra eşitleyerek, n ​​bilinmeyenli aşağıdaki n denklem sistemini elde ederiz:

Yukarıdaki sisteme λ vektörünün fonksiyonları şeklinde bir çözüm bulmanın zor olduğu ortaya çıkarsa, eşitlikler biçiminde kısıtlamalar ekleyerek sistemi genişletebilirsiniz.

n + K bilinmeyenli n + K denklemlerinden oluşan genişletilmiş sistemin çözümü, L fonksiyonunun durağan noktasını belirler. Daha sonra, hesaplama temelinde gerçekleştirilen bir minimum veya maksimumun kontrol edilmesi için bir prosedür uygulanır. L fonksiyonunun Hessian matrisinin elemanları, tek kısıtlamalı bir problem durumunda yapıldığına benzer şekilde, x'in bir fonksiyonu olarak kabul edilir. Bazı problemler için, n+K bilinmeyenli, n+K denklemlerden oluşan genişletilmiş bir sistemin çözümü olmayabilir ve Lagrange çarpan yönteminin uygulanamaz olduğu ortaya çıkar. Ancak bu tür görevlerin pratikte oldukça nadir olduğunu belirtmek gerekir.

Hadi düşünelim özel durum ortak görev Doğrusal olmayan programlama, kısıtlama sisteminin yalnızca denklemler içerdiğini varsayarsak, değişkenlerin negatif olmama koşulu yoktur ve fonksiyonlar kısmi türevleriyle birlikte süreklidir. Bu nedenle, denklem sistemini (7) çözerek, fonksiyonun (6) uç değerlere sahip olabileceği tüm noktaları elde ederiz.

Lagrange çarpanı yöntemi için algoritma

1. Lagrange fonksiyonunu oluşturun.

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

3. Denklem sistemini (7) çözüyoruz, problemin amaç fonksiyonunun ekstremum olabileceği noktaları buluyoruz.

4. Bir ekstremum için şüpheli noktalardan ekstrema ulaşılan noktaları buluyoruz ve bu noktalardaki fonksiyon (6) değerlerini hesaplıyoruz.

Örnek.

İlk veri:Üretim planına göre firmanın 180 adet ürün üretmesi gerekiyor. Bu ürünler iki teknolojik yöntemle üretilebilmektedir. 1. yöntemle x 1 ürün üretirken maliyetler 4x 1 +x 1 2 ruble, 2. yöntemle x 2 ürün üretirken ise 8x 2 +x 2 2 ruble oluyor. Üretim maliyetinin minimum düzeyde olması için her yöntemi kullanarak kaç ürün üretilmesi gerektiğini belirleyin.

Belirtilen problemin amaç fonksiyonu şu şekildedir:
® dk. x 1 + x 2 =180, x 2 ≥0 koşulları altında.
1. Lagrange fonksiyonunu oluşturun
.
2. Kısmi türevleri x 1, x 2, λ'ya göre hesaplıyoruz ve bunları sıfıra eşitliyoruz:

3. Ortaya çıkan denklem sistemini çözerek x 1 =91,x 2 =89'u buluruz

4. Amaç fonksiyonu x 2 =180-x 1'i değiştirerek tek değişkenli bir fonksiyon elde ederiz, yani f 1 =4x 1 +x 1 2 +8(180-x 1)+(180-x 1) ) 2

4x 1 -364=0 hesaplıyoruz,

buradan x 1 * =91, x 2 * =89 elde ederiz.

Cevap: Birinci yöntemle üretilen ürün sayısı x 1 =91, ikinci yöntemle x 2 =89 olup, amaç fonksiyonunun değeri 17.278 rubleye eşittir.

Vektör argümanının iki katı sürekli türevlenebilir skaler fonksiyonları olsun ve olsun. Argümanın kısıtlama sistemini sağlaması koşuluyla, fonksiyonun ekstremumunu bulmak gerekir:

(son durum bağlantı koşulu da denir).

En basit yöntem Koşullu bir ekstremum bulmak, bağlantı denklemini aşağıdakilere göre çözerek sorunu koşulsuz bir ekstremum bulmaya indirgemektir. M değişkenler ve bunların amaç fonksiyonuna daha sonra ikame edilmesi.

Örnek 3. koşulu altında fonksiyonun ekstremumunu bulun.

Çözüm. İfade ettiğimiz bağlantı denkleminden x 2 başından sonuna kadar x 1 ve elde edilen ifadeyi fonksiyonda değiştirin en:

Bu fonksiyonun tek bir ekstremumu (minimum) vardır. x 1=2. Sırasıyla, x 2=1. Böylece koşullu ekstremum noktası (minimum) verilen fonksiyon nokta budur.

Ele alınan örnekte, birleştirme denklemi değişkenlerden birine göre kolayca çözülebilir. Ancak daha fazlasında zor vakalar Değişkenleri ifade etmek her zaman mümkün değildir. Buna göre yukarıda açıklanan yaklaşım her soruna uygulanamaz.

Daha evrensel yöntem Koşullu bir ekstremum bulma problemlerinin çözümü Lagrange çarpanı yöntemi. Aşağıdaki teoremin uygulanmasına dayanmaktadır. Bir nokta, denklemlerle tanımlanan bölgedeki bir fonksiyonun ekstremum noktası ise, o zaman (bazıları için) ek koşullar) böyle bir şey var M noktanın fonksiyonun sabit bir noktası olduğu boyutlu vektör

Lagrange çarpanı yöntemi için algoritma

Aşama 1. Lagrange fonksiyonunu oluşturun:

Lagrange çarpanı nereye karşılık gelir? Ben-inci kısıtlama.

Adım 2. Lagrange fonksiyonunun kısmi türevlerini bulun ve bunları sıfıra eşitleyin

Aşama 3. Ortaya çıkan sistemi çözdükten sonra N+M Denklemler, durağan noktaları bulun.

Durağan noktalarda fonksiyonun ekstremumu için gerekli ancak yeterli olmayan koşulun karşılandığı dikkate alınmalıdır. İçinde bir ekstremum varlığı için sabit bir noktanın analizi bu durumda oldukça karmaşık. Bu nedenle, Lagrange çarpanı yöntemi esas olarak, incelenen fonksiyonun minimum veya maksimum varlığının geometrik veya temel hususlardan önceden bilindiği durumlarda kullanılır.

Bazı ekonomik problemleri çözerken Lagrange çarpanlarının belirli bir anlamsal içeriği vardır. Öyleyse, eğer - işletmenin üretim planı kapsamındaki karı N mallar, - maliyetler Ben-inci kaynak, o zaman ben ben- değişime bağlı olarak amaç fonksiyonunun optimumundaki değişim oranını karakterize eden bu kaynağın değerlendirilmesi Ben-inci kaynak.

Örnek 4. koşulu altında fonksiyonun ekstremumunu bulun.

Çözüm. Fonksiyonlar hem süreklidir hem de sürekli kısmi türevleri vardır. Lagrange fonksiyonunu oluşturalım:

Kısmi türevleri bulup sıfıra eşitleyelim.

İki sabit nokta elde ederiz:

Düzey çizgileri düzlem olan amaç fonksiyonunun ve fonksiyonun (elips) doğasını dikkate alarak, fonksiyonun noktada minimum, noktada maksimum değer aldığı sonucuna varırız.

Örnek 5. Sistem çözümleri alanında

koşulu verilen fonksiyonun maksimum ve minimum değerini bulun.

Çözüm. Uygun çözümlerin bölgesi ile düz bir çizginin kesişimi segmenttir. MN: M(0,6), N(6.0). Bu nedenle fonksiyon ya durağan noktalarda ya da noktalarda uç değerler alabilir M Ve N. Durağan bir nokta bulmak için Lagrange yöntemini uygularız. Lagrange fonksiyonunu oluşturalım

Lagrange fonksiyonunun kısmi türevlerini bulup sıfıra eşitleyelim

Sistemi çözerek sabit bir nokta elde ederiz k(2.2;3.8). Amaç fonksiyonunun değerlerini noktalarda karşılaştıralım k, M, N:

Buradan,

Örnek 6. Belirli bir ürüne yönelik pazar talebinin 180 adet olduğu biliniyor. Bu ürün, aynı endişeye sahip iki işletme tarafından şu şartlara göre üretilebilir: çeşitli teknolojiler. Üretimde x 1Ürünler ilk işletme tarafından, maliyetleri ise ovmak ve üretim sırasında x 2 oluşturdukları ikinci işletmenin ürünleri ovmak.

Üretiminin toplam maliyetinin minimum düzeyde olması için endişenin sunabileceği her teknoloji kullanılarak kaç ürünün üretilebileceğini belirleyin.

Çözüm. Problemin matematiksel modeli:

Bulmak Minimum değer amaç fonksiyonu sağlandı x 1+ x 2=180, yani Değişkenlerin negatif olmaması gerekliliğini hesaba katmadan Lagrange fonksiyonunu oluşturuyoruz:

Lagrange fonksiyonunun birinci türevlerini şuna göre bulalım: x 1, x 2, ben ve bunları 0'a eşitleyin. Bir denklem sistemi elde ederiz:

Bu sistemi çözerek aşağıdaki kökleri buluruz: yani ekstremum olduğundan şüphelenilen bir noktanın koordinatlarını elde ederiz.

Bir noktanın olup olmadığını belirlemek için ( ) yerel minimum, amaç fonksiyonunun ikinci kısmi türevlerini hesapladığımız Hessian determinantını inceliyoruz:

Çünkü

bu durumda Hessian determinantı pozitif tanımlıdır; bu nedenle amaç fonksiyonu dışbükeydir ve ( ) yerel bir minimumumuz var:

Lagrange Çarpan Yöntemi matematiksel programlama problemlerini (özellikle dışbükey programlamayı) çözmek için klasik bir yöntemdir. Ne yazık ki, ne zaman pratik uygulama Yöntem, kullanım kapsamını daraltan önemli hesaplama zorluklarıyla karşılaşabilir. Burada Lagrange yöntemini ele alıyoruz çünkü bu yöntem, pratikte yaygın olarak kullanılan çeşitli modern sayısal yöntemleri doğrulamak için aktif olarak kullanılan bir aygıttır. Lagrange fonksiyonu ve Lagrange çarpanları ise bağımsız ve özel bir rol oynamaktadır. önemli rol teoride ve uygulamalarda sadece matematiksel programlamada değil.

Klasik optimizasyon problemini düşünün

maks (min) z=f(x) (7,20)

Bu problem (7.18), (7.19) probleminden farklı olarak, kısıtlamalar (7.21) arasında eşitsizliklerin olmaması, değişkenlerin negatif olmama koşullarının bulunmaması, kesikli olmaları ve f(x) fonksiyonlarının şu şekilde olmasıyla öne çıkmaktadır: süreklidir ve en azından ikinci dereceden kısmi türevleri vardır.

(7.20), (7.21) problemini çözmeye yönelik klasik yaklaşım, x* noktası tarafından karşılanması gereken bir denklem sistemi (gerekli koşullar) verir; bu, f(x) fonksiyonuna aşağıdakileri sağlayan noktalar kümesinde yerel bir ekstremum sağlar: kısıtlamalar (7.21) (problem için dışbükey programlama bulunan x* noktası, Teorem 7.6'ya göre aynı anda küresel bir ekstremum noktası olacaktır).

x* fonksiyonunun (7.20) noktasında yerel bir koşullu ekstremuma sahip olduğunu ve matrisin rütbesinin 'ye eşit olduğunu varsayalım. Daha sonra gerekli koşullar forma yazılacaktır:

(7.22)

bir Lagrange fonksiyonu var; - Lagrange çarpanları.

Denklem sisteminin (7.22) çözümünün f(x) fonksiyonunun uç noktasını belirlediği yeterli koşullar da vardır. Bu soru Lagrange fonksiyonunun ikinci diferansiyelinin işaretinin incelenmesine dayanarak çözülmüştür. Bununla birlikte, yeterli koşullar esas olarak teorik açıdan ilgi çekicidir.

Lagrange çarpanı yöntemini kullanarak (7.20), (7.21) problemini çözmek için aşağıdaki prosedürü belirleyebilirsiniz:

1) Lagrange fonksiyonunu (7.23) oluşturur;

2) Lagrange fonksiyonunun tüm değişkenlere göre kısmi türevlerini bulun ve bunları sıfıra eşitleyin. Bunun sonucunda denklemlerden oluşan (7.22) sistemi elde edilecektir. Ortaya çıkan sistemi çözün (eğer bu mümkünse!) ve böylece Lagrange fonksiyonunun tüm durağan noktalarını bulun;

3) Koordinatlar olmadan alınan sabit noktalardan, f(x) fonksiyonunun kısıtlamaların (7.21) varlığında koşullu yerel ekstrema sahip olduğu noktaları seçin. Bu seçim, örneğin yerel bir ekstremum için yeterli koşullar kullanılarak yapılır. Sorunun belirli koşulları kullanılırsa çalışma genellikle basitleştirilir.

Örnek 7.3. Bulmak optimum dağıtım bir birimde sınırlı kaynak. n tüketici arasında, x j kaynak biriminin j'inci tüketiciye tahsis edilmesinden elde edilen kar aşağıdaki formülle hesaplanırsa.

Çözüm. Problemin matematiksel modeli aşağıdaki forma sahiptir:

Lagrange fonksiyonunu oluşturuyoruz:

.

Bulduk Lagrange fonksiyonunun kısmi türevlerini bulun ve bunları sıfıra eşitleyin:

Bu denklem sistemini çözerek şunu elde ederiz:

Böylece j'inci tüketiciye birimler tahsis edilir. kaynak, o zaman toplam kar maksimum değerine ve miktarına ulaşacaktır. birimler

Lagrange metodunun uygulandığı şekliyle inceledik. klasik problem optimizasyon. Bu yöntem, değişkenlerin negatif olmadığı ve bazı kısıtlamaların eşitsizlikler şeklinde verildiği duruma genelleştirilebilir. Ancak bu genelleme öncelikle teoriktir ve belirli hesaplama algoritmalarına yol açmaz.

Sonuç olarak Lagrange çarpanlarına ekonomik bir yorum verelim. Bunu yapmak için en basit klasik optimizasyon problemine dönelim

maksimum (min) z=F(X 1 , X 2); (7.24)

𝜑(x 1, x 2)=b. (7.25)

Koşullu ekstremuma noktada ulaşıldığını varsayalım. Fonksiyonun karşılık gelen ekstrem değeri F(X)

Kısıtlamalarda (7.25) miktarın olduğunu varsayalım. B değişebilirse, uç noktanın koordinatları ve dolayısıyla uç değer F* işlevler F(X) bağlı olarak miktarlar haline gelecektir B yani ,ve dolayısıyla fonksiyonun türevi (7.24)

1.9 Lagrange'ın belirlenemeyen çarpanlar yöntemi

Doğal olarak kısıtlı optimizasyon problemlerini çözmek önemli ölçüde önemlidir. daha zor çözümler kısıtsız optimizasyon problemleri Koşullu optimizasyon problemini (göreceli bir ekstremum arama) daha basit bir koşulsuz optimizasyon problemine (mutlak bir ekstremum arama) indirgemeye çalışmak doğaldır. Bu işlem Lagrange yöntemiyle gerçekleştirilir. Bu yöntemin özünü ele alalım.

Doğrusal olmayan fonksiyonun koşullu ekstremumunu bulmak gerekir

m kısıtlamalı n değişken

(1.56)

Eşitsizlik kısıtlamaları eşitliklere dönüştürülür ve serbest terimler kısıtlamaların sol taraflarına aktarılır; sistem (1.56) formuna indirgenmiştir

(1.57)

Lagrange yöntemine göre, (1.57) kısıtlamaları altındaki fonksiyonun (1.55) bağıl ekstremumu yerine, Lagrange fonksiyonunun aşağıdaki forma sahip mutlak ekstremumu aranır:

Değişkenler gibi istenen değişkenler olan belirlenmemiş Lagrange çarpanları nerede?

Lagrange fonksiyonunun amaç fonksiyonu artı her kısıtlamanın Lagrange çarpanı ile çarpılmasını içerdiği görülebilir.

Kısıtlar (1.57) altında amaç fonksiyonunun (1.55) bağıl ekstremumunun Lagrange fonksiyonunun (1.58) mutlak ekstremumu ile çakıştığı kanıtlanmıştır.

(1.58) fonksiyonunun mutlak ekstremumunun araştırılması gerçekleştirilir. bilinen yöntemler. Özellikle Lagrange fonksiyonunun kısmi türevleri belirlenir ve sıfıra eşitlenir:

(1.59)

Son m denklemi optimizasyon probleminin kısıtlamalarını (1.57) temsil eder.

Sistem (1.59), (m+n) denklem ve aynı sayıda bilinmeyen içermektedir.

Çözüm sistemi (1.59), kısıtlamalar (1.57) altında Lagrange fonksiyonunun mutlak minimumunun (1.58) veya amaç fonksiyonunun göreceli minimumunun (1.55) koordinatlarını verecektir.

(1.59) sisteminin çözümü, iyi bilinen hesaplamalı matematik yöntemleri kullanılarak gerçekleştirilir. Sistem (1.59) doğrusal ise genellikle Gauss yöntemi kullanılır. Sistem (1.59) doğrusal değilse – Newton yöntemi.

1.10 Bir optimizasyon yöntemi seçme

Bir optimizasyon yöntemi seçmeden önce şunları gerçekleştireceğiz: kısa analiz geliştirilen yazılımın çözmesi gereken görevler:

program koşullu minimizasyon problemini çözmelidir, yani. göreceli ekstremumu bulun, çünkü matematiksel model Doğrusal sınırlamalara ek olarak doğrusal olmayan sınırlamalar da ortaya çıkacaktır;

Amaç fonksiyonu birçok değişkenin bir fonksiyonu olduğundan, birden fazla ekstremum değeri olabilir, bu durumda programın yerel minimumu araması gerekir.

Bu amaca ulaşmak için en sık kullanılan optimizasyon yöntemleri analiz edildikten sonra, yukarıdaki gradyan yöntemlerinden en etkilisi olan ikinci dereceden programlamanın polinom yaklaşım yöntemleriyle değiştirilmiş gradyan yöntemi seçilmiştir.

Amaç fonksiyonu ve sınır koşullarının ikinci dereceden bağımlılıklar veya ikinci dereceden polinomlarla tahmin edildiği varsayılmaktadır. Bu yöntem daha sonra “Geliştirme” bölümünde daha ayrıntılı olarak tartışılacaktır. yazılım optimizasyon yöntemi".

Bu yöntem oluşturmanıza olanak sağlar güvenilir program, yukarıdaki gereksinimlerin tümünü karşılıyor.

2. Bir optimizasyon yönteminin geliştirilmesi tekrar aktif güç

Elektrik güç sisteminde (EPS) gerekli olan kompanzasyon cihazlarının toplam gücü, reaktif güç dengesi denkleminden (6.1) belirlenir. Bu güç düğümlere yerleştirilmelidir elektrik ağıİle minimum maliyetler.

komşu EPS'den gelen reaktif güç de dahil olmak üzere EPS'de üretilen toplam reaktif güç nerede;

Komşu EPS'ye sağlanan reaktif güç dahil, EPS tüketicilerinin toplam reaktif gücü;

Santrallerin kendi ihtiyacı olan toplam reaktif güç;

Toplam reaktif güç kayıpları;

EPS cinsinden toplam reaktif güç tüketimi.

En basit şemayı ele alalım mevcut ağ(Şekil 2.1). U voltajına sahip bir güç kaynağından, R ağ direnci aracılığıyla yük, S=P+jQ gücüyle beslenir. Yük baralarına Qk kapasiteli kompanzasyon cihazı monte edilmiştir.

Şekil 2.1 – En basit şema reaktif güç kompanzasyonu

Tüketicinin kompanzasyon cihazı olmaması durumunda hattaki aktif güç kayıpları ()

. (2.2)

Tüketiciye bir dengeleme cihazı () takarken, bu kayıplar değere düşecektir.

. (2.3)

Böylece reaktif güç kompanzasyonu, bir güç kaynağı devresindeki aktif güç kayıplarının azaltılmasını ve dolayısıyla bu devrenin teknik ve ekonomik göstergelerinin iyileştirilmesini mümkün kılar.

CG'nin ağ maliyetleri üzerindeki etkisini değerlendirelim.

Isı eşanjörünü kurarken yüke güç aktarmanın toplam maliyetinin ifadesi şu şekilde olacaktır:

(2.4)

burada ZK – CG maliyetleri;

соΔР – ağdaki aktif güç kayıplarını karşılama maliyetleri;

с – kayıp aktif gücün birim başına maliyeti;

зк – CG için birim maliyetler.

Fonksiyon 3'ün minimumunu belirlemek için QK değişkeninin türevini sıfıra eşitleriz:

(2.5)

(2.5)'ten, kaynaktan tüketiciye aktarımı minimum maliyete karşılık gelen ekonomik açıdan uygun reaktif güç belirlenir.

(2.6)

QE'nin değeri aktif güce (P) bağlı değildir, yalnızca zk ve co maliyet göstergelerinin oranına ve gücün iletildiği U ve R ağının parametrelerine bağlıdır.

Kompanzasyon cihazlarının gerçek bir EPS'nin elektrik ağına yerleştirilmesi konusu karmaşık bir optimizasyon problemidir. Buradaki zorluk, elektrik güç sistemlerinin birbirine bağlı alt sistemlerden oluşan büyük sistemler olmasıdır. Özellikleri nedeniyle her bir alt sistemi ayrı ayrı ele almak imkansızdır. büyük sistemler Bireysel alt sistemlerin karşılıklı ilişkilerinin doğası tarafından belirlenir.

Büyük sistemleri analiz ederken, analizin buna göre yapıldığı bir sistem yaklaşımı kullanılır. büyük sistem birbirleriyle doğrudan ilişkili olmayan, ancak sistem aracılığıyla birbirlerini daha fazla etkileyen alt sistemlere bölünerek gerçekleştirilir. yüksek seviye.

İncelenmekte olan konuyla ilgili olarak, elektrik şebekesi farklı seviyelerdeŞekil 2'de gösterildiği gibi. 2.2. üst seviye 110 kV ve üzeri gerilime sahip bir elektrik şebekesidir. Tam bir eşdeğer devre ile temsil edilen bu karmaşık elektrik ağı, geleneksel olarak ES1 olarak Şekil 2.2'de gösterilmektedir. QES enerji santrallerinin jeneratörleri, QK dengeleme cihazları, QС güç hatları tarafından üretilen reaktif güçlerin yanı sıra komşu ES2 ve ES3 (Q12, Q21, Q13, Q31) ile bağlantılardan akan reaktif güçler, ES1'de mevcut Qр1 reaktif gücünü sağlar.

Şekil 2.2 - Kontrol ünitesinin elektrik şebekesindeki yerleşimi

İkinci seviye, elektrik ağının n düğümüne bağlı, voltajı 35 kV ve altında olan n açık yerel dağıtım ağı kümesidir. Üst düzey T transformatörleri aracılığıyla. Bu yerel dağıtım ağları birbirine doğrudan bağlı değildir, ancak üst düzey ağ aracılığıyla birbirlerini etkiler. Senkron jeneratörler, bu tür dağıtım ağlarının her birinde bulunan kompansatörler ve motorlar, bir eşdeğer senkron makine G ile temsil edilir. Düşük voltajlı tüketiciler P+jQ, dağıtım transformatörleri T1 aracılığıyla yerel elektrik ağlarından güç alır.

Kompanzasyon cihazları, T transformatörlerinin yüksek gerilim (jQkv) ve alçak gerilim (jQks) veri yollarına, ayrıca T1 dağıtım transformatörlerinin 0,4 kV veri yollarına ve 0,4 kV ağın kendisine (jQkn) kurulabilir. Bu HRSG'lerin güç değeri tespite tabidir.

İÇİNDE Genel görünüm CP'nin yerleşimini optimize etme sorunu formüle edildi Aşağıdaki şekilde: 6…35 kV düğümlerinde mevcut reaktif güçleri belirleyin senkron makineler G, tüm Qkv, Qks, Qkn voltajlarındaki ağlarda ısı eşanjörünün gücü ve ayrıca minimumun olduğu tüketici ağlarına iletilen reaktif güçlerin Qеi (i=1, 2, …n) değerleri toplam maliyetler sağlanır.

Her türlü ağ için reaktif güç kompanzasyonunun hesaplamaları, hem elektrik ağlarının geliştirilmesini tasarlarken hem de çalışma koşulları altında gerçekleştirilir. Tasarım sırasında ısı eşanjörünün gücü belirlenir ve elektrik şebekesindeki dağıtım sorunu çözülür. Çalışma koşulları altında, belirleyin optimum modlar gün boyunca mevcut CU'lar. Bu durumda optimallik kriterleri minimum güç ve enerji kayıpları ve voltaj sapmalarının kabul edilebilir değerlere uygunluğudur.

Bir güç kaynağı devresi tasarlarken, kural olarak, bu devrenin parasal maliyetleri en aza indirilir. Isı eşanjörlerinin kurulumundan kaynaklanan güç kayıplarının azaltılması, devrenin maliyetini düşürür. aşağıdaki nedenler:

Kaybedilen her kW güç santrallerde üretilmeli ve dolayısıyla harcanmalıdır. peşin;

Santrallerde kaybedilen reaktif gücün üretimi, tüketimden çok daha pahalıdır (3 kat!).

Ancak dengeleme cihazları aynı zamanda mali maliyetler de gerektirir.

Bu bağlamda, minimum toplam maliyeti karşılayan dengeleme cihazlarının optimal gücünün belirlenmesi sorunu ortaya çıkmaktadır. Bu problem, kısıtsız optimizasyon problemine aittir ve örneğin gradyan yöntemleriyle çözülebilir.

Ana güç kaynağı devresi için böyle bir sorunu ele alalım (Şekil 2.3). Bu cihazların kurulumu ve devredeki aktif güç kayıplarının karşılanması için minimum toplam maliyet koşuluna bağlı olarak düğüm 1 ve 2'deki QK1 ve QK2 dengeleme cihazlarının gücünün belirlenmesi gerekir.

Şekil 2.3 - Güç kaynağı şeması

İlk veri:

devre voltajı U;

hat dirençleri R1 ve R2;

reaktif yükler düğümler 1 ve 2 Q1 ve Q2;

telafi edici cihazların kurulumuna ilişkin özel maliyetler;

Aktif güç kayıplarının karşılanması için özel maliyetler c.

Kompanzasyon cihazlarının kurulumunun ve devredeki aktif güç kayıplarının karşılanmasının toplam maliyetini temsil eden amaç fonksiyonu aşağıdaki forma sahiptir:

burada a1=R1∙co∙10-3/U2=0,0006;

a2=R2∙co∙10-3/U2=0,0004.

Amaç fonksiyonunun tüm bileşenlerini tek bir boyuta (cu) getirmek için 10-3 sayısal katsayısının eklenmesi gerekir.

Sorunu çözmek için koordinat iniş yöntemini seçiyoruz. Z amaç fonksiyonunun Q1 ve Q2 değişkenlerine göre kısmi türevlerini belirleyelim:

(2.8)

İlk yaklaşımı ele alalım:

Bu değerler için amaç fonksiyonunun değerlerini ve kısmi türevlerini hesaplıyoruz.

Qk2 değişkeni yönünde Z amaç fonksiyonunun Qk1 değişkeni yönünde olduğundan daha güçlü bir şekilde azaldığını varsayalım, yani.

(2.10)

Qk2 değişkeni yönünde inişimize başlayacağız.

Adım boyutunu =400 kvar alalım. İlk yaklaşım (ilk adım) Qk11=0, Qk21=400 kvar olacaktır. Z1 amaç fonksiyonunun değerini hesaplıyoruz.

İkinci adım: Qk12=0, Qk22=400 kvar. Z2 amaç fonksiyonunun değerini hesaplıyoruz.

Qk2 koordinatı boyunca iniş Zn'ye kadar devam etmelidir.

Başka bir değişken olan Qk1 yönünde yeni bir adım atalım. Z amaç fonksiyonunun yeni bir değeri bulunur.Bu değişken boyunca iniş, Zm'ye kadar Qk2 yönünde olduğu gibi devam eder.

Elde edilen Qk1m-1, Qk2n-1 koordinatlarına sahip nokta, amaç fonksiyonu Z'nin minimumunun yakınında yer almaktadır. Kabul edilen adım uzunluğu = 400kvar ile daha doğru bir çözüm elde edilemez. Daha doğru bir çözüm elde etmek için adımı azaltıp inişe devam etmek gerekir. Adım ne kadar küçük olursa sonucun o kadar doğru olacağı kesinlikle kesindir. Bu doğruluğu manuel hesaplamayla elde edemeyiz. Bu sorunu çözmek için, doğrusal olmayan kısıtlamalara sahip doğrusal olmayan programlama problemlerini çözecek şekilde tasarlanmış yazılımların kullanılması tavsiye edilir. Böyle bir programlama dili C++'dır.

Bu, kısıtlanmamış bir optimizasyon problemi olarak kabul edildi, yani. mutlak minimumu bulmak. Ortaya çıkan problemi çözerken, OJSC Ilyich Iron and Steel Works ağının en uygun çalışma modunu bulmak için, kısıtlama sistemi doğrusal olmayan bir forma sahip olacağından göreceli bir minimum bulmak gerekir (aşağıya bakınız “Yazılım Geliştirme) ”). Bu nedenle, daha önce seçilen ikinci dereceden programlamanın gradyan yöntemini kullandığımız reaktif güç için koşullu optimizasyon göreviyle karşı karşıyayız.

“OJSC Ilyich Iron and Steel Works elektrik ağlarının çalışma modlarının analizi ve güç tüketimi modları için uyarlanabilir bir kontrol sisteminin geliştirilmesi” çalışması hakkında bilgi