dışbükey programlama

Bir matematiksel programlama probleminde bir fonksiyonun ekstremumunun bulunması gerekiyorsa, örneğin:

kısıtlamalar tarafından verilen kabul edilebilir çözümler kümesinde

1) amaç fonksiyonu türevlenebilir ve içbükeydir, yani. bunun için aşağıdaki koşul sağlanır:

Herhangi

2) tüm kısıtlamaların sol kısımları ise - türevlenebilir ve dışbükey fonksiyonlar, yani onlar için şartlar yerine getirildi:

Herhangi

O zaman problem (4.7)-(4.8) problem olarak adlandırılır. dışbükey programlama.

Herhangi bir doğrusal fonksiyon aynı anda hem dışbükeylik hem de içbükeylik koşullarını karşılar; şunlar. hem dışbükey hem de içbükey olarak kabul edilebilir. Bu, doğrusal problemleri dışbükey programlama problemlerinin özel bir durumu olarak düşünmemizi sağlar.

Genel durumda matematiksel programlama problemleri için çözümün varlığı ve kararlılığı konusunda hala tutarlı bir teori yoksa, dışbükey programlama problemleri için böyle bir teori vardır.

Üç tanım sunuyoruz:

bir). Dışbükey programlama probleminin (4.7)-(4.8) Lagrange fonksiyonu şu fonksiyondur:

,

, (4.9)

2). Dışbükey programlama probleminin (4.7)-(4.8) tatmin edici olduğu söylenir. düzenlilik koşulu, (4.8)'den elde edilen katı eşitsizliklerle tanımlanan uygun çözümler kümesinin en az bir iç noktası varsa (yani, ).

3). nokta denir sele hepsi için ise işlev noktası gerçekleştirilen:

Eğer amaç fonksiyonu (kaldır)

Doğrusal olmayan programlama teorisinde, merkezi yer, klasik Lagrange çarpanları yöntemini, doğrusal olmayan bir problemin kısıtlamaları ile birlikte eşitlik şeklindeki kısıtlamaların da kısıtlamalar içerdiği duruma genelleyen Kuhn-Tucker teoremi tarafından işgal edilir. eşitsizlikler şeklindedir.

Kuhn-Tucker teoremi. Eğer dışbükey programlama problemi (4.7)-(4.8) düzenlilik koşulunu sağlıyorsa, nokta bu problem için en uygun çözümdür, ancak ve ancak negatif olmayan koordinatlara sahip, yani Lagrange'ın eyer noktası olan böyle bir nokta varsa. Bu sorunun işlevi.

Karush koşulları - Kuna - Diferansiyel formda Tucker:

Lagrange işlevi dışbükey içbükey, içbükey ve tümü ve 'de sürekli türevlenebilir ise, çiftin Lagrange işlevinin eyer noktası olması için aşağıdaki koşulların sağlanması gerekli ve yeterlidir:

,

,

,

Örnek.Kuhn-Tucker teoremi, dışbükey programlama probleminin Lagrange fonksiyonunun eyer noktasını bulma problemine indirgenmesini doğrular. Böyle bir indirgemenin pratik anlamı olması için, ortaya çıkan sorunun orijinalinden biraz daha basit olması gerekir. Bu her zaman gerçekleşmez, bu nedenle doğrusal olmayan probleme (4.5), (4.6) bir çözüm bulmak için bir dizi doğrudan yöntem geliştirilmiştir. Bunlardan bazılarını ele alalım.

Bu problem sınıfının ele alınması genellikle bir sunumla başlar. belirsiz Lagrange çarpanları yöntemi. Bunu yapmak için /(x b..., X") ve g(xb ..., X")- kısmi türevleriyle birlikte sürekli fonksiyonlar, şimdilik değişkenlerin negatif olmama koşullarını ortadan kaldırıyoruz ve bir koşullu ekstremum için aşağıdaki problemi formüle ediyoruz:

Çözümünü bulmak için tanıtıyoruz Lagrange çarpanları y / = 1, t ve sözde yapmak Lagrange işlevi:

tüm değişkenlere göre kısmi türevlerini bul ve sıfıra eşitle

sistemi aldıktan n + t bilinmeyenler için denklemler x b x p,

Ui -, Yukarı-

eğer fonksiyon f(x h ..., X") noktada bir ekstremumu varsa, böyle bir Y vektörü vardır (0> = (y, 0 ,..., y°) noktasının (А r(0) , F (0)) sisteminin (2.23) bir çözümü olduğunu. Bu nedenle, (2.23) sistemini çözerek, (2.20) fonksiyonunun bir ekstremum değerine sahip olabileceği noktaları elde ederiz. Ayrıca, bulunan noktalar, koşulsuz bir ekstremum için problemi çözerken olduğu gibi incelenir.

Böylece, Lagrange çarpan yöntemi aşağıdaki adımları içerir.

• 1. Lagrange fonksiyonunu oluşturun.
• 2. Kısmi türevleri bulun Xj ve y, Lagrange işlevinden alın ve bunları sıfıra eşitleyin.
• 3. Çözüm sistemi (2.23), amaç fonksiyonunun bir ekstremum değerine sahip olabileceği noktaları bulun.
• 4. Bir ekstremum için puan adayları arasında, ekstremumun ulaşıldığı noktaları bulun ve fonksiyonun değerlerini hesaplayın f(x, ..., X") bu noktalarda.

Açıklanan yöntem, dışbükey programlama sorunlarına, yani. amaç fonksiyonunun dışbükey (veya içbükey) olduğu ve kısıtlamalar tarafından belirlenen uygun çözümlerin alanı da dışbükey olduğu durumlara.

Tanım 1.İşlev f(x,..., xn), dışbükey bir kümede tanımlanmış x, herhangi bir nokta için dışbükey denir X, X2 itibaren hee herhangi bir sayı için x, 0 X 1

Tanım 2.İşlev/(*, X„) dışbükey bir kümede tanımlanmış x, herhangi bir nokta için içbükey denir X X, 2 itibaren hee herhangi bir sayı için x, 0 X

Tanım 3. Bir dışbükey programlama problemine uygulanabilir çözümler seti, eğer en az bir nokta varsa, düzenlilik koşulunu sağlar. xj, kabul edilebilir çözümler alanına ait olan, g^XJ) =ben = 1, t.

Teorem 1. Bir dışbükey programlama probleminin herhangi bir yerel ekstremumu globaldir.

Tanım 4. Dışbükey programlama probleminin Lagrange işlevi, işlevdir.

burada y, Lagrange çarpanıdır.

Tanım 5. Nokta (X (0) , T(0)) = (x,°,..., X (',y, 0 ,...," ) aranan Lagrange fonksiyonunun eyer noktası, eğer

Yardımcı nitelikte iki kısa teorem veriyoruz.

Teorem 2. Optimal Plan X (0) görevler NP- bu

burada DA) koşulları sağlayan doğrusal olmayan türevlenebilir bir fonksiyondur.

fonksiyonun gradyanı nerede /

A" (0) noktasında.

Kanıt.

Bir Taylor serisinde amaç fonksiyonunu nokta civarında genişletelim. X (())

nerede AH- artış vektörü X (0) ;

I - vektörün normunun (uzunluğun) belirlenmesi.

(2.26) ifadesinden, x| vektörünün koordinatının herhangi bir değeri varsa bunu takip eder. 0) > 0, sonra türev

, çünkü aksi halde koordinat x k Yapabilmek,

kalan değişkenlerin sabit değerleri ile amaç fonksiyonunu minimize etmeye, türev sıfırdan büyükse x[ 0) değerini düşürmeye veya arttırmaya devam edin. xf türev daha az ise

sıfır. eğer x| 0) = 0, o zaman olmalıdır Çünkü

aksi takdirde değeri düşürmek mümkün olurdu f(X m), 4 0) diğer değişkenlerin değerlerini değiştirmeden Ax* değeri kadar artırma. Bu nedenle, herhangi biri için ile eşitlik tutar:

Teorem kanıtlanmıştır.

Şimdi Lagrange fonksiyonunun bir eyer noktasının varlığı için gerekli ve yeterli koşulları tanımlayalım.

Teorem 3. Negatif olmayan koordinatlara sahip (A 10 *, VE 0) noktasının türevlenebilir bir fonksiyonun eyer noktası olması için L(X, Y), koşullar yerine getirilmelidir:

Kanıt.

1) İhtiyaç.(X (0) , Y "(0)) bir eyer noktası olsun, yani:

Formül (2.29) ifadesine eşdeğerdir

(2.29) ve (2.30) temelinde, (2.27) ve (2.28) koşulları sağlanır. Böylece gerekliliği kanıtlanmıştır.

• 2) Yeterlilik(2.27) ve (2.28) koşullarının sağlandığını varsayalım. İşlevi genişlet L(X, Y) nokta civarında bir Taylor serisinde

Genişlemeden (2.31) ve (2.27) ve (2.28) koşulları dikkate alındığında, şu şekildedir:

Son iki ifade formül (2.29) ile eşdeğerdir. Teorem kanıtlanmıştır.

Yukarıdaki teoremlerden sonra, artık pratik olarak açık olan Kuhn-Tucker teoremini formüle ediyoruz.

Teorem 4 (Kuhn - Tucker). Uygun çözümler kümesi düzenlilik özelliğine sahip olan bir dışbükey programlama problemi (2.20) - (2.21) için, nokta X (0) =(xj 0 *,..., x' 0)), x, - 0> >0, / = 1, P eğer ve sadece böyle bir vektör varsa optimal bir plandır T =(y 1 (0) ,..., yi 0)), Y/ 0) >0, / = 1, t,(T (0) , H 0>) noktasının Lagrange fonksiyonunun bir eyer noktası olduğunu.

Dışbükey programlama (2.20) - (2.21) probleminde amaç fonksiyonu ve kısıtlamalar sürekli türevlenebilirse, Kuhn - Tucker teoremi (X (0)) noktası için gerekli ve yeterli koşulları belirleyen analitik ifadelerle desteklenebilir. , Y i (l), ) Lagrange fonksiyonunun eyer noktasıydı, yani. dışbükey programlama sorununa bir çözümdü. Bunlar (2.27) ve (2.28) ifadeleridir. İkinci dereceden programlama probleminden memnunlar. Son formülasyonu için birkaç tanım ve bir teorem veriyoruz.

Tanım 6. X[, ..., değişkenlerine göre ikinci dereceden biçim X"şu şekle sahip olan bu değişkenlerin sayısal bir fonksiyonu olarak adlandırılır:

Tanım 7. ikinci dereceden biçim F pozitif/negatif tanımlı ise F(X) > 0/F(X) 0 vektörü oluşturan değişkenlerin tüm değerleri için x.

Tanım 8. ikinci dereceden biçim F pozitif/negatif yarı kesin olarak adlandırılırsa F(X") > O / EVET") X ve ek olarak, böyle bir dizi değişken var - vektörün bir bileşeni X", ne F(X") = 0.

Teorem 5.İkinci dereceden bir form, pozitif/negatif yarı tanımlıysa, dışbükey/içbükey bir işlevdir.

Tanım 9. Bir fonksiyonun değerini minimize etme/maksimumlaştırma görevi

kısıtlamalar altında

olarak adlandırılan pozitif/negatif yarı tanımlı ikinci dereceden bir form nerede ikinci dereceden programlama problemi(ZKP).

Bu problem için Lagrange fonksiyonu şu şekildedir:

Lagrange fonksiyonunun bir eyer noktası varsa, o zaman (2.27), (2.28) koşulları sağlanır. Şimdi eşitsizlikleri eşitliklere dönüştüren ek değişkenleri tanıtarak (bu teknik aynı zamanda LP problemlerinin çözümünde de kullanılır), bu koşulları şu şekilde yazıyoruz:

IQP'ye bir çözüm bulmak için, lineer cebirsel denklemler sistemine (2.32) negatif olmayan bir çözüm belirlemek gerekir. Böyle bir çözüm bulunabilir yapay temel yöntemi, yapay amaç fonksiyonunun minimum değerini bulmak için uygulanır F = ^Pj, nerede-yapay değişkenler. Yöntem, nasıl-

Sonlu sayıda adımda optimal planı bulacağı veya problemin çözülemezliğini kuracağı bilinmektedir.

Dolayısıyla RFP'ye çözüm bulma süreci aşağıdaki adımları içerir.

• 1. Lagrange fonksiyonunu oluşturun.
• 2. Lagrange fonksiyonunun bir eyer noktasının varlığı için gerekli ve yeterli koşulları (2.27), (2.28) ifadeleri şeklinde yazın.
• 3. Yapay temel yöntemini kullanarak, Lagrange fonksiyonu için bir eyer noktasının yokluğu belirlenir veya koordinatları bulunur.
• 4. Asıl problemin optimal çözümünü yazın ve amaç fonksiyonunun değerini bulun.

İlköğretimi düşünün Sayısal örnek(No. 1) I. L. Akulich'in "Örneklerde ve Problemlerde Matematiksel Programlama" kitabından. Üretim planına göre işletme 180 adet ürün üretmelidir. İki teknoloji kullanılarak yapılabilirler. Üretimde X 1. şekilde ürünler, maliyetler xf+4x, ovmak. ve imalatta x 2ürünler 2. şekilde eşittirler x + 8x 2 ovmak. Siparişin maliyetini en aza indirmek için her yöntemin kaç tane ürün üretmesi gerektiğini belirleyin.

Çözüm. Aşağıdaki işlev en aza indirilmelidir:

koşullar altında:

Bu durumda Lagrange işlevi şöyle görünecektir:

Bu fonksiyonun kısmi türevlerini aşağıdakine göre hesaplayalım: X, x 2, y ve onları sıfıra eşitleyin:

Birinci ve ikinci denklemde taşıma de sağ tarafa ve sol tarafları eşitleyerek, bariz indirimlerden sonra elde ederiz:

Bu denklemi sistemin üçüncü denklemi ile birlikte çözerek şunu buluruz: Bu nokta bir ekstremum için bir yarışmacıdır.

İkinci kısmi türevleri kullanarak, bulunan noktanın / fonksiyonunun koşullu minimumu olduğunu göstermek kolaydır.

Yukarıda ele alınan soruna benzer sorunlar birçok ekonomik uygulamada ortaya konmaktadır. Doğru, gerçek problemler genellikle çok sayıda değişken ve kısıtlama içerir, bu da onları bilgisayar kullanmadan çözmeyi imkansız kılar. Ancak, standartlaştırılmış yazılım kullanmanın etkinliği, araştırmacının bilgisayar tarafından gerçekleştirilen dönüşümlerin özüne ilişkin bilgisi ile belirlenir. Bu, optimizasyon problemlerini çözmek için önerilen yöntemler, hesaplama prosedürleri ve yazılım sistemleri kümesinde kendisini doğru bir şekilde yönlendirmesine yardımcı olur.

Konuyu pekiştirmek için başka bir konuyu düşünün Sayısal örnek(No. 2). Bir fonksiyonun maksimum değerini bulun

koşullar altında:

Çözüm./ işlevi içbükeydir çünkü doğrusal bir işlevin toplamıdır f \u003d 2x 2 + 4x b içbükey olarak kabul edilebilecek ve ikinci dereceden form / 2 = -x -2x1, hangi negatif tanımlı. Kısıtlamalar yalnızca doğrusal kısıtlamalar içerir. Bu nedenle, Kuhn-Tucker teoremi ve ZKP'yi çözmek için şema kullanılabilir.

1. Lagrange işlevini oluşturun:

2. Fonksiyonun eyer noktasının varlığı için gerekli ve yeterli koşulları yazalım. L.

3. Doğrusal eşitsizlikler sistemine ek negatif olmayan değişkenler v b V2 ekleyelim, w, w2, eşitsizlikleri eşitliğe dönüştürmek. Bir denklem sistemi elde ederiz:

Bu durumda, elbette, aşağıdaki koşullar karşılanır:

Lagrange fonksiyonunun eyer noktasının koordinatlarını belirlemek için denklem sisteminin (2.33) temel çözümünü bulmak gerekir. Bunun için yapay temel yöntemini kullanıyoruz. Yapay amaç fonksiyonunun minimize edilmesi

nerede Zi, Zi- şu koşullar altında yapay değişkenler:

Burada, bariz bir temel uygulanabilir çözüm şöyle görünür:

hedef fonksiyon F temel olmayan değişkenler cinsinden ifade edin:

Tartışmayı sonlandırırken, bunun Xj (0) = 1, = 1 ve sıfır değerli diğer değişkenler için ortadan kalktığını not ediyoruz. Böylece, T (0) = (1, 1) orijinal problem için en uygun plandır,

fonksiyon denir dışbükey

fonksiyon denir içbükey dışbükey bir kümede, eğer herhangi bir nokta için ve keyfi bir sayı, aşağıdaki eşitsizlik geçerlidir:

Bazen bir dışbükey işleve, bazen yukarı dışbükey olarak adlandırılan içbükey bir işlevin aksine aşağı dışbükey denir. Bu isimlerin anlamı, tipik bir dışbükey (Şekil 3.3) ve içbükey (Şekil 3.4) fonksiyonunun geometrik temsilinden açıktır.

Pirinç. 3.3. dışbükey fonksiyon

Pirinç. 3.4. içbükey fonksiyon

Dışbükey ve içbükey fonksiyonların tanımlarının yalnızca dışbükey bir küme için anlamlı olduğunu vurguluyoruz. X, çünkü sadece bu durumda nokta mutlaka aittir X.

Dışbükey programlama sorunu Amaç fonksiyonu ve kısıtlama fonksiyonları bir dışbükey küme üzerinde içbükey olduğunda, matematiksel programlamanın (3.7), (3.8) genel probleminin özel bir durumudur. R.

Bir fonksiyonu maksimize etme problemi, bu fonksiyonu eksi işaretiyle minimize etme problemine eşdeğer olduğundan, kısıtlama bir eşitsizliğe eşdeğerdir ve konkavlıktan dışbükeylik gelir ve bunun tersi de geçerlidir. Buradan

Dışbükey programlama problemi aynı zamanda bir dışbükey fonksiyonu kısıtlamalar altında en aza indirme problemi olarak da adlandırılır:

, ,

dışbükey fonksiyonlar nerede; R dışbükey bir kümedir. Bu sadece görevin başka bir şeklidir.

Unutulmamalıdır ki, dışbükey programlama problemi maksimum problem olarak formüle edilirse, amaç fonksiyonu mutlaka içbükeydir ve minimum problem olarak formüle edilirse dışbükeydir.Kısıtlar olarak yazılırsa, o zaman, kısıtlama işlevleri içbükeydir, kısıtlamalar olarak yazılırsa, kısıtlama işlevleri dışbükeydir. Bu bağlantı, dışbükey programlama probleminin belirli özelliklerinin varlığından kaynaklanmaktadır ve bu tür bir bağlantı koptuğunda mevcut olmayabilir. Bu tür iki ana özellik aşağıdaki lemmada formüle edilmiştir.

Önlem 1

Bir dışbükey programlama problemi için kabul edilebilir planlar seti

dışbükeydir. Bir içbükey fonksiyonun herhangi bir yerel maksimumu X küreseldir.

Kısıtlama fonksiyonları dışbükey ise, tanımlanan küme için X(3.14) dışbükeylik artık takip etmeyecektir. Bu durumda, kümenin dışbükeyliği kanıtlanabilir:

Amaç fonksiyonu dışbükey olsaydı, lemmanın maksimumu ile ilgili iddiası yanlış olurdu, ancak benzer bir iddia minimum için kanıtlanabilirdi.

fonksiyon denir kesinlikle dışbükey dışbükey bir kümede, eğer herhangi bir nokta için ve rastgele bir sayı eşitsizliği sağlar.

fonksiyon denir kesinlikle içbükey dışbükey bir kümede, eğer herhangi bir nokta için ve rastgele bir sayı, aşağıdaki eşitsizlik geçerlidir:

Önem 2

Dışbükey (içbükey) fonksiyonların toplamı dışbükeydir (içbükey). Dışbükey (içbükey) bir fonksiyon ile pozitif bir sayının çarpımı dışbükeydir (içbükey). Dışbükey (içbükey) ve kesinlikle dışbükey (kesinlikle içbükey) bir fonksiyonun toplamı kesinlikle dışbükeydir (kesinlikle içbükey).

Teorem 1

Bir dışbükey kümede bir işlev kesinlikle içbükey (kesinlikle dışbükey) ise X, o zaman yalnızca bir maksimum (minimum) noktası olabilir.

Kanıt

Bunun tersini varsayın, yani. iki nokta olduğunu üzerinde kesinlikle içbükey bir fonksiyonun maksimum noktaları olan , , X. Belirtmek, biz var . O zaman herhangi biri için doğrudur:

şunlar. çelişkiye geldi. Kesinlikle dışbükey bir fonksiyonun minimumu için benzer şekilde kanıtlanmıştır.

Doğrusal bir işlev, hem dışbükey hem de içbükey olan bir işlevin tek örneğidir, bu nedenle kesinlikle dışbükey (kesinlikle içbükey) değildir. ikinci dereceden fonksiyon dışbükey (içbükey) olmayabilir, ancak kesinlikle dışbükey (kesinlikle içbükey) olabilir; tüm bunlar matris tarafından belirlenir D. matris öğeleri D ikinci dereceden fonksiyonun ikinci kısmi türevleridir, yani.

.

İkinci kısmi türevlerin matrisini ile gösteriniz.

Önem 3

İkinci dereceden fonksiyon için uzay boyunca dışbükeydir (içbükey), matrisin olması gerekli ve yeterlidir D olumlu (olumsuz) olarak belirlendi. Eğer bir D pozitif (olumsuz) olarak belirlenir, yani.

sonra kesinlikle dışbükey (kesinlikle içbükey).

Doğrusal kısıtlamalar altında ikinci dereceden bir fonksiyonu maksimize etme (minimizasyon) problemi, burada D negatif (pozitif) belirli bir matristir ve D T= D, denir ikinci dereceden programlama problemi .

İkinci dereceden programlama problemi gibi, Bölüm 2'de ele alınan lineer programlama probleminin, konveks programlama probleminin özel bir durumu olduğu lemmadan çıkar.

Bir değişken grubunda dışbükey ve diğerinde içbükey olan fonksiyonlar vardır. Bu tür işlevler, kesinlikle bir eyer noktasına sahip olan ana işlev sınıflarından birini temsil eder.

Teorem 2

(İçbükey-dışbükey bir fonksiyon için bir eyer noktasının varlığı hakkında). İzin vermek X ve Y sonlu boyutlu Öklid uzaylarının dışbükey kapalı sınırlı alt kümeleridir ve fonksiyon ve içinde süreklidir, içbükey içbükey ve dışbükeydir, o zaman bir eyer noktasına sahiptir.

Bir dışbükey programlama problemi için Lagrange fonksiyonunu düşünün:

(3.15)

doğrudan ürün üzerinde tanımlanmıştır, burada . Bu fonksiyon, 'nin içbükeyliğinden dolayı içbükey ve doğrusaldır ve dolayısıyla 'de dışbükeydir.

Ancak, semer noktasına sahip olduğu Teorem 1'e dayanarak iddia edilemez. R mutlaka kapalı ve sınırlı değildir, ancak Y açıkçası sınırsız. Bununla birlikte, belirli koşullar altında bir eyer noktasının hala var olacağı beklenebilir.

Bu konuyla ilgili en ünlü teorem, dışbükey bir programlama probleminin çözümünün varlığı ile Lagrange fonksiyonunun bir eyer noktası arasında bağlantı kuran Kuhn-Tucker teoremidir. Slater koşulları : bir dışbükey programlama problemi, koşulun karşılandığı bir nokta varsa, Slater koşulunu karşılar: .

Kuhn-Tucker teoremi

Bir dışbükey programlama problemi Slater koşulunu karşılıyorsa, tasarımın optimal olması için gerekli ve yeterli koşul, çiftin üzerinde Lagrange fonksiyonunun (3.15) bir eyer noktası olacak şekilde varlığıdır.

Slater koşulunun gerekli olduğu aşağıdaki örnekte gösterilmiştir.

örnek 1

Dışbükey bir programlama problemi verildiğinde:

Burada açıkça görülüyor ki x = 0'ın soruna bir çözümü var, ancak Lagrange işlevi minimax probleminde dış kenara ulaşılmadığı için eyer noktası yoktur:

Bir dışbükey programlama problemindeki kısıtlamaları bölümleme ve , daha önce de belirtildiği gibi, şartlı. Bu nedenle, genellikle R basit bir form kümesi olarak anlaşılır, ya bütün uzaydır E n, veya negatif olmayan bir ortant veya paralel yüzlü. Dışbükey programlama probleminin karmaşıklığı, kısıtlamalar sistemi tarafından belirlenir:

.

Lagrange fonksiyonunun eyer noktası kümelerin çarpımı üzerinde arandığından, Y aynı zamanda bir basit form kümesidir (negatif olmayan ortant), o zaman Kuhn-Tucker teoreminin anlamı, değişkenler üzerinde karmaşık kısıtlamalara sahip bir fonksiyonun ekstremumunu bulma problemini, yeni bir fonksiyonun ekstremumunu bulma problemine indirgemektir. basit kısıtlamalarla çalışır.

eğer küme R ile çakışır E n, o zaman bilindiği gibi ekstremum koşullar şu şekildedir:

Üstelik bu koşullar, fonksiyonun o noktada maksimuma ulaşması için sadece gerekli değil, aynı zamanda yeterlidir. Bu, içbükey fonksiyonların önemli bir özelliğidir ve dışbükey programlama problemi için içbükeydir.

Teorem 3

Sürekli türevlenebilir bir içbükey fonksiyonun bir noktada maksimum olması için E n, fonksiyonun noktadaki gradyanının sıfıra eşit olması gerekli ve yeterlidir, yani. .

Fonksiyonun gradyanının şöyle olduğunu hatırlayın:

.

Böylece, Lagrange fonksiyonunun ürün üzerindeki eyer noktasını bulmak ve sonuç olarak, dışbükey programlama problemine çözüm bulmak için R= E n(3.16) denklem sistemini çözmek gerekir. Ama bu sistemde n denklemler ve bilinmeyenler n+ m, çünkü ek olarak n-boyutlu vektör bizim için bilinmiyor ve m Lagrange çarpanlarının boyutlu vektörü. Ancak, Lagrange fonksiyonunun eyer noktası için çok önemli bir özellik vardır:

. (3.17)

Denklem (3.17), , veya , veya her ikisinin aynı anda olduğunu ima eder. Bu özellik, doğrusal programlamanın ikinci dualite teoremine (Bölüm 2.5) benzer. Bir noktada eşitlik olarak tutulan kısıtlamalara denir. aktif .

Bu nedenle, yalnızca bu Lagrange çarpanları sıfırdan farklı olabilir ve bu noktada etkin olan kısıtlamalara karşılık gelir. Bu özelliği göz önünde bulundurarak bir dışbükey programlama problemine çözüm bulmak için aşağıdaki yöntemi göz önünde bulundurun.

Çalışması matematiksel programlamanın konusu olan çok sayıda pratik ekonomik durum, ya hiçbir şekilde doğrusal problemlere indirgenemez ya da (bu tür bir doğrusallaştırma bir aşamada gerçekleştirilse bile) daha ayrıntılı bir değerlendirme girişiminde bulunur. doğrusal olmamaya yol açar.

En genel doğrusal olmayan programlama problemi şu şekilde formüle edilebilir:

m denklemlerini veya formun eşitsizliklerini karşılayan x 1 , x 2 , ..., x n değişkenlerinin değerlerini belirlemek gerekir.

ben = 1, 2, ..., m.

ve maksimum (veya minimum) hedef işlevine dönüştürün

f (X) \u003d f (x 1, x 2, ..., x n).(2.2)

f ve gi'nin lineer olmayan verilen fonksiyonlar olduğunu, b i'nin bilinen sabitler olduğunu varsayalım. Genel olarak, değişkenlerin tümünün veya en azından bir kısmının negatif olmaması gerektiği varsayılır.

Doğrusal programlamanın özel durumunda, f ve gi fonksiyonlarının doğrusal olduğu varsayılır, yani.

Bunun dışındaki herhangi bir matematiksel programlama problemi, doğrusal olmayan bir problem olarak kabul edilir.

Matematiğin ilgili dallarında, çeşitli türlerdeki fonksiyonların maksimum ve minimumlarını belirlemek için genel (klasik) yöntemler geliştirilmiştir. Bununla birlikte, problem çözmeye yönelik bu tür genel bir yaklaşım, birçok bilinmeyenli doğrusal olmayan denklem sistemlerini çözme ihtiyacına yol açtığı ve uç ekstremleri bulmak için uygun olmadığı için, sayısal sonuçların elde edilmesi için pratik olarak sınırlı bir kullanıma sahiptir. Bu nedenle, matematiksel programlamada, esas olarak bir algoritma, yani belirli ekonomik uygulamaları olan özel problemlerin sayısal çözümü için bir hesaplama prosedürü olarak hizmet edebilecek yöntemler incelenir. Bu sorunlardan bazılarını belirtelim.

Doğrusal kısıtlamalar ve doğrusal olmayan bir hedef fonksiyonu ile ilgili problemler en kapsamlı şekilde incelenmiştir. Ancak bu problemler için bile, yalnızca hedef fonksiyonunun belirli özelliklere sahip olduğu durumlarda hesaplama yöntemleri geliştirilmiştir. Özellikle, örneğin, hedef işlevi şu şekilde temsil edilebilir:

burada f j (x j) fonksiyonlarının da belirli kısıtlamalara tabi olması gerekir. Bu sözde ayrılabilir fonksiyondur. Başka bir durumda amaç fonksiyonu, doğrusal ve ikinci dereceden fonksiyonların toplamı olarak yazılabilir:

Bu tür doğrusal olmayan problemlere ikinci dereceden programlama problemleri denir. Optimal çözümü bulmak için d ij değerlerine bazı ek kısıtlamalar getirilmelidir.

Doğrusal olmayan kısıtlamaları olan problemler, doğrusal olanlardan daha zordur. Bu problemlerde optimal bir çözüm elde etmek için gi ve f fonksiyonlarına çok katı gereksinimler getirilmelidir. Özellikle, doğrusal olmayan eşitsizlikler tarafından verilen gi kısıtlamaları Değişkenler uzayında bir dışbükey küme tanımlıyorsa (bkz. Bölüm 1, § 3) ve amaç fonksiyonu doğrusal olmayan bir düz dışbükey veya içbükey fonksiyon ise, doğrusal olmayan bir problemin optimal çözümü elde edilebilir. . Aşağıda, dışbükey ve içbükey fonksiyonların kesin bir tanımı verilecektir. Burada, f fonksiyonlarının dışbükeylik özelliğinin yalnızca bir minimumun varlığını, f'nin içbükeylik özelliğinin ise kısıtlamalarla belirtilen bölge içinde yalnızca bir maksimum f'nin varlığını sağladığını belirtmek gerekir. Bu, hedef fonksiyonunun optimal değerini belirleyen algoritmaların temelidir. Dışbükeylik veya içbükeylik olmadığında, matematiksel programlama probleminin çözümü, genel durumda klasik yöntemlerle bulunabilen yerel minimum veya maksimumların varlığıyla karşılaşır.

(Belge)

Kurs projesi - Programlama stilleri. Pratik kısım - 100 maçlık oyun (Kurs)

Laboratuvar çalışması №4. Çok boyutlu arama. Doğrusal olmayan programlama. Kısıtlanmamış Minimizasyon Teknikleri (Lab)

Veselov S.L. PBX Samsung ve Panasonic Programlama (Belge)

Sunum - Doğrusal programlama (Özet)

Tikhomirova L.S. Boole İşlevlerini Küçültmeye Yönelik Yöntemler (Belge)

Kirsanova O.V., Semyonova G.A. Matematiksel programlama (tipik hesaplama) (Belge)

Kozyrev D.V. 1C: Kurumsal 7.7 Yapılandırma ve programlama. Muhasebe bileşeni. Uzaktan Eğitim Kursu (Belge)

Laboratuvar çalışması №1. Koşulsuz Tek Boyutlu Optimizasyon (Lab)

Moshchevikin A.P. Ders sunumları "Karar Teorisi" (Belge)

n1.doc

1. 
   Konveks programlama. Kuhn-Tucker teoremi. Kuhn-Tucker koşulları

Dışbükey programlama teorisinde temel sorun dışbükey bir fonksiyonun minimizasyonudur.

Koşullar altında

(1.3)

fonksiyonlar nerede
konveks olduğu varsayılır.

Eğer bir
ve içbükey fonksiyonlar, o zaman maksimizasyon problemimiz var
kısıtlamalar altında
ve

Bu problem için Lagrange fonksiyonunu oluşturalım:

Nokta, fonksiyonun minimum noktasıysa, bir noktaya fonksiyonun (1.4) eyer noktası denir.
ve nokta, işlevin maksimum noktasıdır. Başka bir deyişle, herkes için bir eyer noktası için
ve ilişki

(1.5)

Teorem 1 (Kuhn-Tacker teoremi). En az bir nokta olsun
, hangisi için
. O zaman vektörün optimalliği için gerekli ve yeterli bir koşul
(1.1)-(1.5) probleminin uygulanabilir çözümlerinin alanına ait olan , böyle bir vektörün varlığıdır.
, herkes içindir ve
eşitsizlikler (1.5)

Bu teoremi ispatsız kabul ediyoruz.

Kuhn-Tucker teoremi aynı zamanda eyer noktası teoremi olarak da adlandırılır.

Eğer bir
ve
türevlenebilir fonksiyonlarsa, (1.5)'teki eşitsizlikler aşağıdaki yerel Kuhn-Tucker koşullarına eşdeğerdir:

Bu ifadeler, türevlerin değerlerinin noktada alındığı anlamına gelir.
.

1.2. Kuadratik programlama. Barankin-Dorfman yöntemi.

Dışbükey programlama probleminin özel bir durumu, ikinci dereceden bir programlama problemidir. İkinci dereceden programlamada temel problem olarak, doğrusal ve ikinci dereceden bir fonksiyonun toplamı olan Z fonksiyonunun en küçüklenmesi problemi ele alınmaktadır:

Doğrusal kısıtlamalar ile

D matrisinin simetrik ve negatif olmayan tanımlı olduğu varsayılır. Bu durumda (2.1) fonksiyonu dışbükey olacaktır.

(2.1) - (2.3) problemi için (2.1) - (2.3) probleminin çözümünün optimalliği için gerekli ve yeterli şartlar olan yerel Kuhn-Tucker koşullarını (1.6) - (1.7) oluşturalım.

Bu durumda Lagrange işlevi şu şekildedir:

Bu fonksiyonun kısmi türevlerini bulalım:

belirtmek

Bu gösterimler, (2.4) ve (2.5) bağıntıları dikkate alındığında, Kuhn-Tucker koşulları (1.6) - (1.7) aşağıdaki formu alacaktır.

(2.6) ve (2.7) eşitlikleri, 2N=2(n+m) bilinmeyenli N=n+m lineer denklemlerden oluşan bir sistem oluşturur: .

Böylece Kuhn-Tucker teoremine göre çözüm
problem (2.1) - (2.3) ikinci dereceden programlamanın optimal olması durumunda ve ancak çözümle birlikte
çözümler var
ve
eşitliğin (2.9) sağlanması koşuluyla (2.6) – (2.8) sisteminin bir çözümüdür.

Problem (2.1) için koşul (2.9) – (2.3) koşula eşdeğerdir

İkinci dereceden bir programlama problemini çözmek için birkaç yöntem vardır. Bunlardan birini düşünün - Barankin-Dorfman yöntemi.

Bu yöntemle ilk olarak (2.6) - (2.7) denklem sistemi şu şekle indirgenir:

Neresi (temel değişkenler) ve
(serbest değişkenler) değişkenlerin bazı permütasyonlarının farklı öğeleridir ve tümü negatif olmayan sayılardır (i=1,2,…,N).

Daha sonra sistemden (2.11) ilk referans çözümü bulunur.

Sistemler (2.6) – (2.8) ve vektörün bileşenleri sıraya dizilmiştir.

bir çözüm için ise (2.10) koşulu sağlandığında (2.1) – (2.3) problemi çözülür ve optimal çözümü
vektörün karşılık gelen bileşenlerinden bulunur.

Eğer (2.10) koşulu sağlanmazsa, başka bir referans çözümüne geçiş için aşağıdaki tablo derlenir (Tablo 2.1). Bu tablonun gövdesi, sırayla tüm değişkenler için satırlar içerir. Temel değişkenler için satır elemanları sistemden (2.11) ve serbest değişkenler için ilişkilerden alınır.

Tablo 2.1'in ek bölümünün parametreleri aşağıdaki gibidir:

ANCAK) formülden bulunur nerede - tablonun ana bölümünün s-inci sütununun öğelerinden oluşan vektör;

B) olanlar için
, kalan parametreler hesaplanır:

(minimum sağlayan ilgili sütunların öğeleri , yıldızla işaretlenmiş)
.

Negatifin en küçüğüne karşılık gelen sütun , çözümleme sütunu olarak atanır, bu sütunda yıldızla işaretlenmiş bir öğeye sahip bir satır bir çözümleme dizesidir ve bu öğenin kendisi bir çözümleme öğesidir ve onların yardımıyla tablo 2.1'in tek yönlü dönüşümü gerçekleştirilir.

Burada:

Sonuç olarak (2.6) – (2.8) sisteminin yeni bir referans çözümü elde edilir. Bu işlem (2.10) koşulu sağlanana kadar devam eder. Düştüm
, a
, daha sonra ilk çözüm olarak başka bir çözüm seçilir.

1.3 Barankin-Dorfman yöntemiyle bir problem çözme örneği
İşlevi Küçült

Kısıtlamalarla:

;
.

Çözüm

(2.12) sisteminin başlangıç ​​destek çözümünü buluyoruz. Bu durumda, amaç fonksiyonunun değeri eşittir.

O zaman koşul (2.10) sağlanmaz ve sonuç olarak çözüm optimal değildir.

(2.12) - (2.13) sisteminin yeni bir referans çözümüne geçiş için tablo 2.2'yi yapalım. Bu tablonun ana kısmını sistem (2.12) kullanarak dolduruyoruz.

A) Tablonun ek kısmı için bulduğumuz:

B) pozitif için ve Parametrelerin geri kalanını hesaplayalım:

En küçük negatife karşılık gelen dördüncü sütun , bir çözümleme sütunu, bu sütunun 3. öğesi olan bir satır - bir çözümleme dizesi ve öğe 3'ün kendisi - bir çözümleme öğesi atarız ve onların yardımıyla tablo 2.2'nin tek yönlü dönüşümünü gerçekleştiririz.

Sonuç olarak, yeni bir referans çözüm içeren Tablo 2.3'ü elde ederiz.

Bu çözüm için

Bu nedenle, sistemin (2.12) - (2.13) yeni bir referans çözümüne geçmek için Tablo 2.3'ün ek bölümünü önceki durumda olduğu gibi dolduruyoruz.

Tablo 2.3'ü 13.30 çözünürlük öğesiyle tek yönlü bir dönüşüme tabi tutarak, referans çözümü olan başka bir tablo elde ederiz, bunun için
.

Böylece optimal çözüm bulunur
, burada bu problemin amaç fonksiyonu Z minimize edilmiştir. nerede

1.4 Bireysel görev: sorunu Barankin-Dorfman yöntemiyle çözme

;

Çözüm

(2.6) - (2.7) ilişkilerinden aşağıdaki denklem sistemini elde ederiz:

Basit dönüşümlerden sonra bu sistemi şu şekle getiriyoruz:

(2.14)

Negatif olmamayı hesaba katarak

İlk temel çözümü bulma
sistemler (2.14). Bu durumda amaç fonksiyonunun değeri şuna eşittir:
.

(2.10) koşulu sağlanmadığı için çözüm optimal değildir.

Sistemin (2.14) - (2.15) yeni bir temel çözümüne geçiş için tablo 2.4'ü yapalım.
Tablo 2.4

, ve sonra ilk referans çözümünün seçimi yeniden yapılmalıdır.

	1	-	-	-
	0	-1	0	0
	0	0	-1	0
	4	1	-2	0
	0	0	0	-1
	2	4 *	-6	-2
	4	2	0	-1
	32
		12	-10	-4
		4
		1/2		Tablo 2.5	0	0	-1
	0	-1	0	0
	3	-1/2	3 *	0
	110,25
		-2,5	9	-2
			-3