Hedef fonksiyon ve biçimleri. Modelin temel kavramları

Sistemin eylemi, davranışı, yalnızca hedefe ulaşma gerçeğinin oluşturulmasıyla değil, aynı zamanda amaç işlevi tarafından belirlenen başarı derecesi ile de karakterize edilir.

amaç fonksiyonu - sistemin hedefine ulaşma derecesini karakterize eden, sistemin genelleştirilmiş bir göstergesidir. Amaç fonksiyonunun derlenmesi, sistem tasarımındaki en önemli görevlerden biridir. Bununla birlikte, amaç fonksiyonlarını oluşturmak için genel bir teori yoktur, sadece bazı öneriler vardır.

Amaç fonksiyonu, sistemin harici parametrelerini ve bunlar üzerindeki kısıtlamaları analiz ederek görev tanımının optimizasyon kriteri üzerindeki talimatlarına göre derlenir.

Amaç fonksiyonu esas olarak harici parametrelere veya bunların bir kısmına bağlı olmalıdır. Aksi takdirde, bu amaç fonksiyonu için optimizasyon bir anlam ifade etmez. Amaç fonksiyonu bir vektörü temsil eder. M sistemin dış parametrelerinin boyutsal alanı

Tipik olarak, amaç fonksiyonu skaler formda belirtilir.

Aşağıdaki dört amaç fonksiyonu formu kullanılır.

1. Bir harici parametrenin en sık kullanılan amaç fonksiyonu

Bu durumda, amaç fonksiyonu basitçe dış parametrelerden birine veya onun tersine eşittir.

Diğer ( M– 1) harici parametreler bir kısıtlama sistemine dönüştürülür.

İndirgenmiş türlerin amaç fonksiyonunun fiziksel anlamı, parametrenin ne kadar büyük (veya daha küçük) olduğudur. y Ben, ceteris paribus daha iyi bu sistem, ve diğer koşulların eşitliği, geriye kalanlar üzerindeki kısıtlamalar anlamında anlaşılmaktadır. harici parametreler. Amaç fonksiyonunun indirgenmiş formuyla ilgili tipik problemler: sistemin güvenilirlik açısından optimizasyonu ( y = P(T)), gürültü bağışıklığı, maliyet ve diğer harici parametreler. Böyle bir amaç fonksiyonunun açık bir fiziksel (teknik veya ekonomik) anlamı vardır, sistemi nesnel olarak karakterize eder ve bu nedenle sıklıkla kullanılır. Yani bu durumda amaç fonksiyonu sistemin bir dış parametresidir. Buna sistemin amaç fonksiyonu denir. Bunlar şunlar olabilir: doğruluk, hız, zaman, maliyet, güvenilirlik, ağırlık, boyutlar, bir tür teknolojik gösterge vb.

2. Amaç fonksiyonunun ikinci şekli, aynı boyuttaki parametrelerin toplamı veya bu parametrelerden gelen fonksiyonların toplamıdır.

Bu form, ekonomik kriterlere, karmaşıklık kriterlerine vb. göre optimizasyon için tipiktir.

Örneğin, sistemin yıllık mevcut maliyetlerini en aza indirirken, amaç fonksiyonu iki dış parametrenin toplamıdır: yıllık işletme maliyetleri ve sistemin geri ödeme süresiyle ilgili sermaye maliyetleri. Bu durumda, sistemin bu harici parametrelerinin her biri karmaşık fonksiyon dahili (bulunacak) parametreleri.

Karmaşıklık kriterine göre optimizasyon problemlerinin amaç fonksiyonları da ikinci forma sahiptir, çünkü bireysel alt sistemlerin veya sistem bloklarının karmaşıklıklarının toplamı olarak sunulurlar.

3. Amaç fonksiyonunun üçüncü formu - sıralanmış form - öncelikleri olan birinci formun sıralı bir amaç fonksiyonları kümesidir.

İlk amaç fonksiyonu en önemli, son amaç fonksiyonu ise en az önemli olandır.

Belirli bir durumda, bu tipteki amaç fonksiyonu aşağıdaki gibi yazılır:

Bir sıralama örneği (örneğin) böyle bir amaç fonksiyonları dizisidir: doğruluk, güvenilirlik, maliyet. Üçüncü formun amaç fonksiyonunun anlamı aşağıdaki gibidir. En önemlisi - sıralamada birinci olan - bazıları olarak kabul edilir Ben sistemin -inci parametresi - y Ben(örneğin, doğruluk). Bazı sistemlerde buna sahipse Ben th parametresi diğer tüm sistemlerden daha büyüktür, o zaman diğer parametrelerin değerleri ne olursa olsun (kısıtları karşılamaları şartıyla), bu sistem en iyisi olarak kabul edilir. Sonra ikinci parametrede vb.

Bu durumda optimizasyon prosedürü, kural olarak, çok adımlıdır. Bu tür bir optimizasyon genellikle teknik sistemlerde bilinçsizce uygulanır. İlk olarak, birkaç sistemin aynı doğruluğuna sahip, daha güvenilir ve daha sonra daha ucuz olan en iyi doğruluğa sahip bir sistem seçilir. Optimizasyonun her adımında, konseptle çelişmeyen tek bir kriter kullanılır. sistem yaklaşımı(tek bir kritere göre optimizasyon, aşağıya bakın).

4. Amaç fonksiyonunun dördüncü - en genel - biçimi, heterojen dış parametrelerin tamamına veya bir kısmına (ancak ikiden az olmamak üzere) keyfi bir bağımlılıktır.

Bu durumda, heterojen parametreler boyutsuz (veya tek boyutlu) dönüştürülür ve elde edilen boyutsuz göstergelerin belirli bir bileşimi (örneğin, aritmetik ortalama) olarak amaç fonksiyonu oluşturulur.

Dördüncü formun tek bir amaç fonksiyonu, üçüncü formun amaç fonksiyonlarından ağırlık katsayıları ile çarpılarak ve sonra toplanarak elde edilebilir:

Nerede F S (y Ben) - biri küçüncü formun amaç fonksiyonları;

ω S ağırlıklandırma faktörüdür.

Ancak aynı yerde belirtildiği gibi bireysel amaç fonksiyonlarının ağırlıklarının belirlenmesi oldukça zordur.

Alınan miktarın aşırı değeri optimal olarak kabul edilecektir.

Böylece, çoğu durumda (1. ve 3. formlar) sistemin kalite göstergelerinin, vektör amaç fonksiyonunun bileşenlerinin sayısal değerleri ile değerlendirildiği belirtilebilir. fonksiyoneller :

- - - - - - - - - - - - - - - - - -

Sistemler rastgele etkiler altında çalıştığından, fonksiyonellerin değerleri genellikle rastgele değişkenler olarak ortaya çıkar. Bu, kalite göstergeleri biçimindeki işlevleri kullanırken elverişsizdir. Bu nedenle, bu gibi durumlarda genellikle karşılık gelen fonksiyonellerin ortalama değerleri kullanılır. Örneğin: vardiya başına üretilen ortalama ürün sayısı; ortalama üretim maliyeti vb.

Bazı durumlarda, kalite göstergeleri bazı rastgele olayların olasılıklarıdır. Bu durumda amaç fonksiyonu olarak olasılık seçilir.
belirlenen hedefin (görev) sistem tarafından yerine getirilmesi

Örneğin, radar vb. ile hedef tespit olasılığı.

Amaç fonksiyonu, optimalliğe ulaşmanın doğrudan bağlı olduğu bazı değişkenlere sahip bir fonksiyondur. Belirli bir nesneyi karakterize eden birkaç değişken olarak da hareket edebilir. Aslında hedefimize ulaşma yolunda ne kadar ilerlediğimizi gösteriyor diyebiliriz.

Bu tür işlevlere bir örnek, yapının mukavemetinin ve kütlesinin, tesisatın gücünün, çıktı hacminin, nakliye maliyetinin ve diğerlerinin hesaplanmasıdır.

Amaç işlevi, birkaç soruyu yanıtlamanıza olanak tanır:

Şu veya bu olay karlı mı, değil mi;

Hareket doğru yönde mi?

Seçimin ne kadar iyi yapıldığı vb.

Fonksiyonun parametrelerini etkileyemezsek, belki sadece analiz etmek dışında hiçbir şey yapamayacağımızı söyleyebiliriz, hepsi bu. Ancak bir şeyi değiştirebilmek için genellikle değiştirilebilir parametreler fonksiyonlar. Ana görev, değerleri işlevin optimal hale geldiği değerlere değiştirmektir.

Amaç fonksiyonları her zaman bir formül olarak temsil edilemez. Örneğin bir masa olabilir. Ayrıca, koşul birkaç amaç fonksiyonu şeklinde olabilir. Örneğin, maksimum güvenilirlik sağlamak istiyorsanız, asgari masraflar ve minimum malzeme tüketimi.

Optimizasyon problemleri en önemli başlangıç ​​koşuluna sahip olmalıdır - amaç fonksiyonu. Eğer buna sahipsek, optimizasyonun var olmadığını varsayabiliriz. Başka bir deyişle, eğer bir hedef yoksa, o zaman ona ulaşmanın hiçbir yolu yoktur, elverişli koşullar çok daha azdır.

Optimizasyon görevleri koşullu ve koşulsuz olabilir. İlk tip, bir görev belirlenirken kısıtlamalar, yani belirli koşullar içerir. İkinci tür, maksimum veya mevcut parametreler için bulmaktır. Genellikle bu tür problemler bir minimum bulmayı içerir.

Klasik optimizasyon anlayışında, amaç fonksiyonunun istenen sonuçları sağladığı parametre değerleri seçilir. Mümkün olan en iyi seçeneği seçme süreci olarak da tanımlanabilir. Örneğin, en iyi kaynak tahsisini, tasarım seçeneğini vb. seçin.

Eksik optimizasyon diye bir şey var. Birkaç nedenden dolayı oluşabilir. Örneğin:

Maksimum noktaya ulaşan sistemlerin sayısı sınırlıdır (bir tekel veya oligopol zaten kurulmuştur);

Tekel yoktur, ancak kaynak da yoktur (herhangi bir rekabette nitelik eksikliği);

En çok ya da daha doğrusu "cehaletinin" olmaması (bir erkek güzel bir kadının hayalini kurar, ancak doğada böyle bir kadının var olup olmadığı bilinmemektedir), vb.

Firmaların ve işletmelerin satış ve üretim faaliyetlerinin yönetiminde pazar ilişkileri koşullarında, karar vermenin temeli pazar hakkında bilgidir ve bu kararın geçerliliği, ilgili ürün veya hizmetle pazara girildiğinde zaten kontrol edilir. . Bu durumda, başlangıç ​​noktası tüketici talebinin incelenmesidir. Çözüm bulmak için objektif bir tüketim fonksiyonu ayarlanır. Tüketilen mal miktarını ve tüketici ihtiyaçlarının tatmin derecesini ve aralarındaki ilişkiyi gösterir.

Tanım. Kısıtlama sistemine yönelik herhangi bir çözüme kabul edilebilir LLP çözümü denir.
Tanım. Amaç fonksiyonunun maksimum veya minimum değere ulaştığı olurlu çözüme optimal çözüm denir.

Bu tanımlar sayesinde, LP problemi şu şekilde formüle edilebilir: kısıtlamalar sistemine bir çözüm olan bir dışbükey alanın tüm noktaları arasından, koordinatları doğrusal fonksiyonu en aza indiren (maksimumlaştıran) birini seçin. F = İle 1 X + İle 2 y.
değişkenlerin X, y LLP'de kural olarak negatif olmayan değerler alır ( X≥ 0, y≥ 0), dolayısıyla bölge koordinat düzleminin ilk çeyreğinde yer almaktadır.

Doğrusal işlevi göz önünde bulundurun F = İle 1 X + İle 2 y ve bazı değerleri düzeltin F. Örneğin, F= 0, yani İle 1 X + İle 2 y= 0. Bu denklemin grafiği orijinden (0; 0) geçen bir doğru olacaktır (Şek.).
Çizim
Bu sabit değeri değiştirirken F = D, dümdüz İle 1 X+ İle 2 y=d paralel hareket edecek ve tüm düzlemi "çizecektir". İzin vermek D- çokgen - kısıtlama sisteminin çözüm alanı. Ne zaman değişir D dümdüz İle 1 X + İle 2 y = D, bazı değerler için D = D 1 poligona ulaşacak D, bu noktayı arayalım A"giriş noktası" ve ardından çokgeni geçtikten sonra belirli bir değerde D = D 2 onunla son ortak noktamız olacak İÇİNDE, Hadi arayalım İÇİNDE"çıkış noktası".
Açıktır ki, en küçük ve en büyük değerlerinin amaç fonksiyonu F=İle 1 X + İle 2 y giriş noktalarına ulaşmak A ve "çıkış" İÇİNDE.
Amaç fonksiyonunun, bölgenin köşelerindeki uygun çözümler kümesinde en uygun değeri aldığını dikkate alarak D, LLP'yi çözmek için aşağıdaki planı önerebiliriz:

1. kısıtlama sisteminin çözüm alanını oluşturmak;
2. amaç fonksiyonuna karşılık gelen bir düz çizgi oluşturun ve bu düz çizginin paralel çevirisi ile "giriş" veya "çıkış" noktasını bulun (amaç fonksiyonunu en aza indirme veya en üst düzeye çıkarma gereksinimine bağlı olarak);
3. bu noktanın koordinatlarını belirleyin, içlerindeki amaç fonksiyonunun değerini hesaplayın.

grafik ile PLP kararıÖzel tartışma gerektiren iki durum vardır.

Dava 1
Şekil 6
Düz hareket ederken İle 1 X + İle 2 y= DÇokgenin kenarı boyunca "giriş" veya "çıkış" (şekildeki gibi) oluşacaktır. Bu, çokgenin çizgiye paralel kenarları varsa olur. İle 1 X+ İle 2 de = D .
Bu durumda, sonsuz sayıda "çıkış" ("giriş") noktası, yani segmentin herhangi bir noktası vardır. AB. Bu, amaç fonksiyonunun maksimum (minimum) değeri bir noktada değil, çokgenin karşılık gelen tarafında bulunan tüm noktalarda aldığı anlamına gelir. D.

Durum 2
Kabul edilebilir değerler aralığının sınırsız olduğu durumu düşünün.
Sınırsız bir alan söz konusu olduğunda, amaç fonksiyonu, ona karşılık gelen çizginin bir "çıkış" (veya "giriş") noktası olmayacak şekilde belirtilebilir. O zaman fonksiyonun maksimum değerine (minimum) asla ulaşılmaz - fonksiyonun sınırlı olmadığını söylerler.
Çizim
Amaç fonksiyonunun maksimum değerini bulmak gerekir. F = 4X + 6y→ max , bir kısıtlama sistemi ile
Kabul edilebilir çözümler alanını oluşturalım, yani eşitsizlik sistemini grafiksel olarak çözer. Bunu yapmak için, her düz çizgiyi oluşturuyoruz ve eşitsizlikler tarafından verilen yarım düzlemleri tanımlıyoruz.
X + y = 18

0,5X + y = 12

Problemin amaç fonksiyonunu göz önünde bulundurun F = 4X + 6y→ maks.

Fonksiyonun değerine karşılık gelen düz bir çizgi çizelim. F = 0: 4X + 6y= 0. Bu doğruyu paralel olarak hareket ettireceğiz. Tüm hat ailesinden 4 X+ 6y= const içinden geçtiği son köşeye göre düz bir çizgi geçecekçokgenin sınırının ötesine geçerken bir tepe noktası olacaktır İLE(12; 6). onun içinde F = 4X + 6y onun ulaşacak maksimum değer.
Yani, de X = 12, y= 6 fonksiyon F maksimum değerine ulaşır F= 4 ∙ 12 + 6 ∙ 6 = 84, 84'e eşittir. (12; 6) koordinatlı nokta, kısıtlama sisteminin tüm eşitsizliklerini karşılar ve içindeki amaç fonksiyonunun değeri optimaldir. F* = 84 (en uygun değer "*" ile gösterilecektir).
Sorun çözüldü. Bu nedenle, kar 84 bin ruble olurken, 12 tip I ve 6 tip II ürün üretmek gerekiyor.

Kısıtlama sisteminde sadece iki değişkeni olan problemleri çözmek için grafik yöntem kullanılır. Bu yöntem aynı zamanda üç değişkenli eşitsizlik sistemlerine de uygulanabilir. Geometrik olarak durum farklı olacak, üç boyutlu uzayda düz çizgilerin rolünü uçaklar oynayacak ve üç değişkendeki eşitsizliğin çözümü düzlemin bir tarafında yer alan bir yarım uzay olacaktır. Bölgelerin rolü, yarı boşlukların kesiştiği çokyüzlüler tarafından oynanacaktır.

amaç fonksiyonu- bazı optimizasyon problemlerini çözmek için optimizasyona (minimizasyon veya maksimizasyon) tabi olan birkaç değişkenin gerçek veya tamsayı fonksiyonu. Terim matematiksel programlama, yöneylem araştırması, doğrusal programlama, istatistiksel kararlar teorisi ve esas olarak uygulamalı nitelikteki matematiğin diğer alanları, ancak optimizasyonun amacı aynı zamanda gerçek problemin çözümü de olabilir. matematik problemi. Optimizasyon probleminde amaç fonksiyonuna ek olarak, değişkenler bir eşitlik veya eşitsizlik sistemi şeklinde kısıtlamalara tabi olabilir. Genel durumda, amaç fonksiyonu bağımsız değişkenleri isteğe bağlı kümelerde belirtilebilir.

örnekler

Pürüzsüz fonksiyonlar ve denklem sistemleri

Herhangi bir denklem sistemini çözme problemi

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matris) )\Sağ.)

amaç fonksiyonunun minimizasyonu problemi olarak formüle edilebilir.

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\toplam _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1))

Fonksiyonlar pürüzsüz ise, minimizasyon problemi gradyan yöntemlerle çözülebilir.

Herhangi bir düzgün amaç fonksiyonu için, tüm değişkenlere göre kısmi türevler 0'a (\ displaystyle 0) eşitlenebilir. Optimal amaç fonksiyonu, böyle bir denklem sisteminin çözümlerinden biri olacaktır. (1) (\displaystyle (1)) işlevi durumunda, bu bir en küçük kareler (LSM) denklemleri sistemi olacaktır. Orijinal sistemin herhangi bir çözümü, en küçük kareler sisteminin bir çözümüdür. Orijinal sistem tutarsızsa, her zaman bir çözümü olan LSM sistemi, orijinal sistemin yaklaşık bir çözümünü elde etmeyi mümkün kılar. LSM sisteminin denklem sayısı, bilinmeyenlerin sayısıyla çakışır, bu da bazen ortak başlangıç ​​sistemlerinin çözümünü kolaylaştırır.

Doğrusal programlama

Amaç fonksiyonunun iyi bilinen başka bir örneği, doğrusal programlama problemlerinde ortaya çıkan bir doğrusal fonksiyondur. İkinci dereceden amaç fonksiyonunun aksine, optimizasyon doğrusal fonksiyon ancak doğrusal eşitlikler veya eşitsizlikler sistemi şeklinde kısıtlamalar varsa mümkündür.

kombinatoryal optimizasyon

Kombinatoryal amaç fonksiyonunun tipik bir örneği, gezgin satıcı probleminin amaç fonksiyonudur. Bu fonksiyon, grafikteki Hamilton döngüsünün uzunluğuna eşittir. Grafik köşelerinin n − 1 (\displaystyle n-1) permütasyon kümesinde verilir ve grafiğin kenar uzunluğu matrisi tarafından belirlenir. Bu tür problemlerin kesin çözümü genellikle seçeneklerin sıralanmasıyla gerçekleşir.

Bölüm 1. Doğrusal programlamanın ana probleminin ifadesi

1. Doğrusal programlama

Doğrusal programlama, aşağıdakilerle karakterize edilen aşırı problemleri çözmek için yöntemleri inceleyen bir matematiksel programlama dalıdır: doğrusal bağımlılık değişkenler ve doğrusal bir test arasında. Bu tür görevler, insan faaliyetinin çeşitli alanlarında kapsamlı uygulamalar bulur. Bu tür sorunların sistematik bir incelemesi 1939-1940'ta başladı. L.V.'nin eserlerinde Kantoroviç.

Doğrusal programlamanın matematiksel problemleri, belirli üretim ve ekonomik durumların incelenmesini içerir;

Doğrusal programlama yöntemleri kullanılarak çözülen problemlerin aralığı oldukça geniştir, örneğin:

üretim planlamasında kaynakların optimal kullanımı sorunu;

karışım sorunu (ürünlerin bileşiminin planlanması);

optimal kombinasyonu bulma sorunu Çeşitli türler depolarda depolama için ürünler (envanter yönetimi veya);

nakliye görevleri (işletmenin bulunduğu yerin analizi, malların hareketi).

Doğrusal programlama, matematiksel programlamanın en gelişmiş ve yaygın olarak kullanılan bölümüdür (ayrıca buna şunlar dahildir: tamsayı, dinamik, doğrusal olmayan, parametrik programlama). Bu şu şekilde açıklanmaktadır:

çok sayıda ekonomik problemin matematiksel modelleri, gerekli değişkenlere göre doğrusaldır;

bu tür problemler şu anda en çok çalışılan problemdir. Onun için bu sorunların çözüldüğü özel yöntemler ve bunlara karşılık gelen bilgisayar programları geliştirilmiştir;

Çözülmekte olan birçok doğrusal programlama problemi geniş uygulama alanı bulmuştur;

bir seriden sonra orijinal formülasyonda doğrusal olmayan bazı problemler ek kısıtlamalar ve varsayımlar doğrusal hale gelebilir veya doğrusal programlama yöntemleriyle çözülebilecek bir forma indirgenebilir.

Herhangi bir doğrusal programlama probleminin ekonomik ve matematiksel modeli şunları içerir: optimal değeri (maksimum veya minimum) bulunması gereken bir amaç fonksiyonu; bir sistem şeklinde kısıtlamalar lineer denklemler veya eşitsizlikler; değişkenlerin negatif olmaması gerekliliği.

Genel olarak model şu şekilde yazılır:

amaç fonksiyonu

(1.1) kısıtlamalar altında

(1.2) olumsuzluk olmaması gereksinimleri

(1.3) nerede X J– değişkenler (bilinmeyenler);

- doğrusal programlama probleminin katsayıları.

Problem, (1.2) ve (1.3) kısıtlamalarına bağlı olarak (1.1) fonksiyonunun optimal değerini bulmaktır.

Kısıt sistemi (1.2) problemin işlevsel kısıtlamaları olarak adlandırılır ve kısıtlamalar (1.3) doğrudan kısıtlamalar olarak adlandırılır.

(1.2) ve (1.3) kısıtlamalarını karşılayan bir vektöre, doğrusal programlama probleminin uygun çözümü (planı) denir. Fonksiyonun (1.1) maksimum (minimum) değerine ulaştığı plana optimal denir.

1.2. Doğrusal programlama problemlerini çözmek için tek yönlü yöntem

Simpleks yöntemi, 1947 yılında Amerikalı matematikçi J. Dantzig tarafından problem çözmek için geliştirilmiş ve uygulanmıştır.

İki boyutlu doğrusal programlama problemleri grafiksel olarak çözülür. N=3 durumu için, üç boyutlu bir uzay düşünebiliriz ve amaç fonksiyonu çokyüzlünün köşelerinden birinde optimal değerine ulaşacaktır.

Standart formda verilen bir LP probleminin kabul edilebilir bir çözümü (kabul edilebilir bir plan), kısıtlamaları karşılayan sıralı bir sayılar dizisidir (x1, x2, ..., xn); n boyutlu uzayda bir noktadır.

Kabul edilebilir çözümler kümesi, LP sorununun kabul edilebilir çözümler alanını (SDR) oluşturur. ODR, dışbükey bir çokyüzlüdür (çokgen).

Genel olarak, probleme N-bilinmeyenler dahil edildiğinde, sınırlayıcı koşullar sistemi tarafından belirtilen uygulanabilir çözümlerin alanının n-boyutlu uzayda dışbükey bir çokyüzlü ile temsil edildiğini ve hedefin optimal değerini söyleyebiliriz. fonksiyon bir veya birkaç köşede elde edilir.

Tüm serbest değişkenler sıfıra eşitse, çözüm temel olarak adlandırılır.

Referans çözüm, negatif olmayan temel bir çözümdür. Destek çözümü dejenere olmayan ve dejenere olabilir. Bir destek çözümü, sıfır olmayan koordinatlarının sayısı sistemin sırasına eşitse, dejenere olmayan, aksi takdirde dejenere olarak adlandırılır.

Amaç fonksiyonunun uç değerine ulaştığı uygun bir çözüme optimal denir ve gösterilir. .

Değişken sayısı 3'ten fazla olduğunda bu problemleri grafiksel olarak çözmek çok zordur. var evrensel yol Simplex yöntemi olarak adlandırılan doğrusal programlama problemlerini çözme.

Simplex yöntemi evrensel yöntem tek bir çözümle başlayan ve en iyi seçeneği aramak için yinelemeli bir süreç olan LP problemlerini çözmek, optimum değere ulaşana kadar uygulanabilir çözümler alanının köşe noktaları boyunca hareket eder.

Herhangi bir doğrusal programlama problemini çözmek için kullanılabilir.

Simplex yöntemi, ortaya çıkan çözümün ardışık olarak iyileştirilmesi fikrine dayanmaktadır.

Simplex yönteminin geometrik anlamı, kısıtlama polihedronunun bir köşesinden, en uygun çözüm bulunana kadar amaç fonksiyonunun en iyi (veya en azından en kötü değil) değeri aldığı bir sonrakine sırayla hareket etmektir - tepe noktası burada optimal değere ulaşılır hedef fonksiyonu (problemin sonlu bir optimumu varsa).

Böylece, kanonik forma indirgenmiş bir kısıtlamalar sistemine sahip olarak (tüm fonksiyonel kısıtlamalar eşitlik biçimindedir), kişi bu sistemin herhangi bir temel çözümünü mümkün olduğu kadar basit bulmaya özen göstererek bulur. Bulunan ilk temel çözümün uygulanabilir olduğu ortaya çıkarsa, optimallik açısından kontrol edilir. Optimal değilse, o zaman başka bir, zorunlu olarak kabul edilebilir, temel çözüme geçiş yapılır. Simplex yöntemi, bu yeni çözümle amaç fonksiyonunun optimuma ulaşmaması durumunda ona yaklaşmasını (veya en azından ondan uzaklaşmamasını) garanti eder. Kabul edilebilir yeni bir temel çözümle, optimal olan bir çözüm bulunana kadar aynı şey yapılır.

Simplex yöntemini uygulama süreci, üç ana unsurunun uygulanmasını içerir:

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

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

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

Simplex yöntemi birkaç adım içerir ve açık bir algoritma (sıralı işlemleri gerçekleştirmek için açık bir talimat) olarak formüle edilebilir. Bu, başarılı bir şekilde programlamanıza ve bir bilgisayarda uygulamanıza izin verir. Az sayıda değişken ve kısıtlama içeren problemler çözülebilir tek yönlü yöntem manuel olarak.

6.1 Giriş

optimizasyon. Bölüm 1

Optimizasyon yöntemleri seçmenize izin verir en iyi seçenek hepsinden tasarımlar seçenekler. Son yıllarda bu yöntemlere çok dikkat edilmiş ve sonuç olarak, bulmak için oldukça verimli bir dizi algoritma geliştirilmiştir. en iyi seçenek bilgisayar kullanarak tasarlar. Bu bölüm, optimizasyon teorisinin temellerini özetlemekte, optimal çözümler için algoritmaların oluşturulmasının altında yatan ilkeleri ele almakta, en iyi bilinen algoritmaları açıklamakta ve bunların avantajlarını ve dezavantajlarını analiz etmektedir.

6.2 Optimizasyon teorisinin temelleri

Literatürde "optimizasyon" terimi, rafine bir çözüm elde etmenizi sağlayan bir işlem veya işlem dizisi anlamına gelir. Optimizasyonun nihai amacı en iyi veya "optimal" çözümü bulmak olsa da, genellikle bilinen çözümleri mükemmelleştirmek yerine iyileştirmekle yetinmek gerekir. Bu nedenle, optimizasyon, belki de elde edilemeyecek olan mükemmellik arayışı olarak anlaşılma olasılığı daha yüksektir.

n bilinmeyenli m denklem tarafından tanımlanan keyfi bir sistemi göz önünde bulundurarak, üç ana problem tipini ayırt edebiliriz. Eğer m=n ise problem cebirsel olarak adlandırılır. Böyle bir sorunun genellikle tek bir çözümü vardır. m>n ise, sorun yeniden tanımlanır ve kural olarak çözümü yoktur. Son olarak, m için

Optimizasyon konularının tartışılmasına geçmeden önce, bir dizi tanım sunacağız.

Tasarım parametreleri

Bu terim, çözülmekte olan tasarım problemini tamamen ve açık bir şekilde tanımlayan bağımsız değişken parametrelerini ifade eder. Tasarım parametreleri, optimizasyon işlemi sırasında değerleri hesaplanan bilinmeyen miktarlardır. Sistemi nicel olarak tanımlamaya hizmet eden herhangi bir temel veya türev nicelik, tasarım parametreleri olarak işlev görebilir. Yani bilinmeyen uzunluk, kütle, zaman, sıcaklık değerleri olabilir. Tasarım parametrelerinin sayısı, bu tasarım probleminin karmaşıklık derecesini karakterize eder. Genellikle tasarım parametrelerinin sayısı n ile ve tasarım parametrelerinin kendisi x ile karşılık gelen indekslerle gösterilir. Böylece, bu problemin n tasarım parametresi şu şekilde gösterilecektir:

X1, x2, x3,...,xn.

amaç fonksiyonu

Bu, mühendisin değerini en üst düzeye çıkarmaya veya en aza indirmeye çalıştığı ifadedir. Amaç işlevi, iki alternatif çözümü nicel olarak karşılaştırmanıza olanak tanır. Matematiksel bir bakış açısından, amaç fonksiyonu bazı (n + 1) - boyutlu yüzeyi tanımlar. Değeri, tasarım parametreleri tarafından belirlenir.

M=M(x 1 , x 2 ,...,x n).

Mühendislik uygulamalarında sıklıkla karşılaşılan amaç fonksiyonu örnekleri maliyet, ağırlık, güç, boyutlar, verimliliktir. Yalnızca bir tasarım parametresi varsa, amaç işlevi bir düzlem üzerinde bir eğri ile temsil edilebilir (Şekil 6.1). İki tasarım parametresi varsa, hedef fonksiyon üç boyutlu uzayda bir yüzeyle temsil edilecektir (Şekil 6.2). Üç veya daha fazla tasarım parametresi ile, amaç fonksiyonu tarafından belirtilen yüzeyler hiper yüzeyler olarak adlandırılır ve tasvir edilemez.

zheniya geleneksel anlamına gelir. Amaç fonksiyon yüzeyinin topolojik özellikleri, en verimli algoritmanın seçimi bunlara bağlı olduğundan, optimizasyon sürecinde önemli bir rol oynar.

Bazı durumlarda amaç fonksiyonu en beklenmedik biçimleri alabilir. Örneğin, bunu ifade etmek her zaman mümkün değildir.

Şekil 1. Tek boyutlu amaç fonksiyonu.

Şekil.6.2.İki boyutlu amaç fonksiyonu.

kapalı matematiksel form, diğer durumlarda olabilir

parçalı düzgün bir fonksiyon olsun. Bir amaç fonksiyonu bazen bir teknik veri tablosu (örneğin bir buhar durumu tablosu) gerektirebilir veya bir deney yapmak gerekli olabilir. Bazı durumlarda, tasarım parametreleri yalnızca tamsayı değerleri alır. Bir dişlideki diş sayısı veya bir flanştaki cıvata sayısı buna bir örnek olabilir. Bazen tasarım parametrelerinin yalnızca iki değeri vardır - evet veya hayır. Müşteri memnuniyeti, güvenilirlik, estetik gibi niteliksel parametrelerin optimizasyon sürecinde hesaba katılması zordur çünkü bunların nicelleştirilmesi neredeyse imkansızdır. Bununla birlikte, amaç fonksiyonu hangi biçimde sunulursa sunulsun, tasarım parametrelerinin tek değerli bir fonksiyonu olmalıdır.

Bazı optimizasyon problemlerinde birden fazla amaç fonksiyonunun kullanılması gerekir. Bazen biri diğeriyle uyumsuz olabilir. Bir örnek, aynı anda maksimum güç, minimum ağırlık ve minimum maliyet sağlamak gerektiğinde uçak tasarımıdır. Bu gibi durumlarda, tasarımcı bir öncelikler sistemi getirmeli ve her amaç fonksiyonuna boyutsuz bir çarpan atamalıdır. Sonuç olarak, optimizasyon sürecinde bir bileşik amaç fonksiyonunun kullanılmasına izin veren bir "uzlaşma fonksiyonu" ortaya çıkar.

Minimum ve maksimumu bulma

Bazı optimizasyon algoritmaları maksimumu bulmak için, diğerleri minimumu bulmak için uyarlanmıştır. Bununla birlikte, çözülen ekstremum probleminin türü ne olursa olsun, aynı algoritma kullanılabilir, çünkü minimizasyon problemi, amaç fonksiyonunun işaretini ters çevirerek kolayca bir maksimum bulma problemine dönüştürülebilir. Bu teknik Şekil 6.3'te gösterilmektedir.

Tasarım alanı

Bu, tüm n tasarım parametresi tarafından tanımlanan alanın adıdır. Tasarım alanı göründüğü kadar büyük değildir, çünkü genellikle bir dizi ile sınırlıdır.

sorunun fiziksel özü ile ilişkili koşullar. Kısıtlamalar o kadar güçlü olabilir ki, görevin herhangi bir kısıtlaması olmayacaktır.

Şekil 6.3 Amaç fonksiyonunun işaretini tersine çevirme

Maksimum görev, minimum görev haline gelir.

tatmin edici çözüm Kısıtlar iki gruba ayrılır: kısıtlamalar - eşitlikler ve kısıtlamalar - eşitsizlikler.

Kısıtlamalar - eşitlik

Kısıtlamalar - eşitlikler - bu, bir çözüm bulunurken dikkate alınması gereken tasarım parametreleri arasındaki bağımlılıktır. Doğa kanunlarını, ekonomiyi, hakları, hakim zevkleri ve mevcudiyeti yansıtırlar. gerekli malzemeler. Kısıtlamaların sayısı - eşitlikler herhangi biri olabilir. benziyorlar

C 1 (x 1 , x 2 ,...,x n)=0,

C 2 (x 1 , x 2 ,...,x n)=0,

..................

C j (x 1 , x 2 ,...,x n)=0.

Bu ilişkilerden herhangi biri, tasarım parametrelerinden birine göre çözülebilirse, bu, verilen parametre optimizasyon sürecinden Bu, tasarım uzayının boyut sayısını azaltmakta ve problemin çözümünü basitleştirmektedir.

Kısıtlamalar - eşitsizlikler

Bu, eşitsizliklerle ifade edilen özel bir kısıtlama türüdür. Genel durumda, herhangi bir sayıda olabilir ve hepsi şu şekle sahiptir:

z 1 r 1 (x 1 , x 2 ,...,x n) Z 1

z 2 r 2 (x 1 , x 2 ,...,x n) Z 2

.......................

z k r k (x 1 , x 2 ,...,x n) Z k

Sıklıkla, sınırlamalar nedeniyle, amaç fonksiyonunun optimal değerine, yüzeyinin sıfır eğime sahip olduğu durumlarda ulaşılamadığı not edilmelidir. Sıklıkla en iyi karar tasarım alanının sınırlarından birine karşılık gelir.

yerel optimum

Bu, amaç fonksiyonunun tasarım uzayındaki noktanın adıdır. en yüksek değer yakın çevresindeki diğer tüm noktalardaki değerleri ile karşılaştırılır.

Şekil 6.4. Rastgele bir amaç fonksiyonu birkaç taneye sahip olabilir.

yerel optimum

Şek. Şekil 6.4, iki yerel optimuma sahip tek boyutlu bir amaç fonksiyonunu göstermektedir. Genellikle tasarım alanı birçok yerel optimum içerir ve problemin en iyi çözümü için ilkini karıştırmamaya özen gösterilmelidir.

Küresel Optimum

Global optimum, tüm tasarım alanı için en uygun çözümdür. Yerel optimuma karşılık gelen diğer tüm çözümlerden daha iyidir ve tasarımcının aradığı da budur. Bulunan birkaç eşit küresel optimum durumu farklı parçalar tasarım alanı. Optimizasyon probleminin nasıl ortaya çıktığı en iyi şekilde bir örnekle gösterilmektedir.

Örnek 6.1

Ambalajsız elyafı taşımak için tasarlanmış 1 m hacimli dikdörtgen bir kap tasarlamak istensin. Daha ucuz olacağından, bu tür kapların imalatı için mümkün olduğu kadar az malzeme harcanması arzu edilir (sabit bir duvar kalınlığı varsayıldığında, bu, yüzey alanının minimum olması gerektiği anlamına gelir). Konteynerin forklift ile alınmasını kolaylaştırmak için genişliği en az 1,5 m olmalıdır.

Bu problemi optimizasyon algoritmasını uygulamak için uygun bir biçimde formüle edelim.

Tasarım parametreleri: x 1 , x 2 , x 3 .

Amaç fonksiyonu (en aza indirilmesi gereken), kabın yan yüzeyinin alanıdır:

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.

Kısıtlama - eşitlik:

Hacim \u003d x 1 x 2 x 3 \u003d 1m3.

Kısıtlama - eşitsizlik:

Doğrusal programlama problemleri

Doğrusal Programlama (LP) matematiksel programlamanın bölümlerinden biridir - aşırı (optimizasyon) problemleri inceleyen ve bunları çözmek için yöntemler geliştiren bir disiplin.

Optimizasyon sorunu amaç fonksiyonunun optimal (yani maksimum veya minimum) değerini bulmaktan oluşan bir matematik problemidir ve değişkenlerin değerleri belirli bir kabul edilebilir değerler alanına (ODV) ait olmalıdır.

Genel olarak, bir matematiksel programlama probleminin formülasyonu, fonksiyonun en büyük veya en küçük değerinin belirlenmesinden oluşur. amaç fonksiyonu, koşullar (kısıtlamalar) altında, burada ve fonksiyonları verilir ve sabitler verilir. Aynı zamanda, eşitlikler ve eşitsizlikler biçimindeki kısıtlamalar, uygulanabilir çözümlerin (ODS) kümesini (bölgesini) belirler ve buna denir. Tasarım parametreleri.

Fonksiyonların türüne ve matematiksel programlama problemlerine bağlı olarak bir dizi sınıfa ayrılır (doğrusal, doğrusal olmayan, dışbükey, tamsayı, stokastik, dinamik programlama, vb.).

İÇİNDE Genel görünüm LP problemi aşağıdaki forma sahiptir:

, (5.1)

, , (5.2)

, , (5.3)

, , sabitleri verilir.

Fonksiyon (5.1) amaç fonksiyonu olarak adlandırılır; sistemler (5.2), (5.3) - bir kısıtlama sistemi ile; (5.4) koşulu, tasarım parametrelerinin olumsuz olmaması koşuludur.

(5.2), (5.3) ve (5.4) kısıtlamalarını sağlayan tasarım parametreleri kümesine denir. kabul edilebilir çözüm veya plan.

optimum çözüm veya optimal plan LP sorunu denir kabul edilebilir çözüm, burada amaç fonksiyonu (5.1) optimal (maksimum veya minimum) değeri alır.

standart görev LP, (5.2) ve (5.4) koşulu altında amaç fonksiyonunun (5.1) maksimum (minimum) değerini bulma problemi olarak adlandırılır, burada , , yani. onlar. sadece eşitsizlikler (5.2) biçimindeki kısıtlamalar ve tüm tasarım parametreleri olumsuz olmama koşulunu sağlar ve eşitlikler biçiminde hiçbir koşul yoktur:

,

, , (5.5)

.

Kanonik (ana) görev LP, (5.3) ve (5.4) koşulu altında amaç fonksiyonunun (5.1) maksimum (minimum) değerini bulma problemi olarak adlandırılır, burada , , yani. onlar. sadece eşitlikler (5.3) şeklinde kısıtlamalar ve tüm tasarım parametreleri negatif olmama koşulunu sağlar ve eşitsizlikler şeklinde hiçbir koşul yoktur:

,

.

Kanonik LP problemi matris ve vektör formunda da yazılabilir.

matris formu kanonik sorun LP aşağıdaki forma sahiptir:

Kanonik LP probleminin vektör formu.

) bazı optimizasyon problemlerini çözmek için. Terim, matematiksel programlama, yöneylem araştırması, doğrusal programlama, istatistiksel karar teorisi ve matematiğin diğer alanlarında, öncelikle uygulamalı bir yapıda kullanılır, ancak optimizasyonun amacı aynı zamanda uygun bir matematiksel problemin çözümü olabilir. Optimizasyon probleminde amaç fonksiyonuna ek olarak, değişkenler bir eşitlik veya eşitsizlik sistemi şeklinde kısıtlamalara tabi olabilir. Genel durumda, amaç fonksiyonu bağımsız değişkenleri isteğe bağlı kümelerde belirtilebilir.

örnekler

Pürüzsüz fonksiyonlar ve denklem sistemleri

amaç fonksiyonunun minimizasyonu problemi olarak formüle edilebilir.

$S\; =\; \backslash sum\_(j=1)^N\; F\_j^2(x\_1,\; x\_2,\; \backslash ldots,\; x\_M)\; \backslash qquad\; (1)$

Fonksiyonlar pürüzsüz ise, minimizasyon problemi gradyan yöntemlerle çözülebilir.

Herhangi bir pürüzsüz amaç fonksiyonu için, şuna eşit olabilir: $0$ tüm değişkenlere göre kısmi türevler. Optimal amaç fonksiyonu, böyle bir denklem sisteminin çözümlerinden biri olacaktır. fonksiyon durumunda $(1)$ en küçük kareler (LSM) denklemleri sistemi olacaktır. Orijinal sistemin herhangi bir çözümü, en küçük kareler sisteminin bir çözümüdür. Orijinal sistem tutarsızsa, her zaman bir çözümü olan LSM sistemi, orijinal sistemin yaklaşık bir çözümünü elde etmeyi mümkün kılar. LSM sisteminin denklem sayısı, bilinmeyenlerin sayısıyla çakışır, bu da bazen ortak başlangıç ​​sistemlerinin çözümünü kolaylaştırır.

Doğrusal programlama

Amaç fonksiyonunun iyi bilinen başka bir örneği, doğrusal programlama problemlerinde ortaya çıkan bir doğrusal fonksiyondur. İkinci dereceden amaç fonksiyonunun aksine, doğrusal bir fonksiyonun optimizasyonu ancak doğrusal eşitlikler veya eşitsizlikler sistemi şeklinde kısıtlamalar varsa mümkündür.

kombinatoryal optimizasyon

Kombinatoryal amaç fonksiyonunun tipik bir örneği, gezgin satıcı probleminin amaç fonksiyonudur. Bu fonksiyon, grafikteki Hamilton döngüsünün uzunluğuna eşittir. Permütasyon kümesinde verilir $n-1$ grafiğin köşeleri ve grafik kenar uzunluklarının matrisi tarafından belirlenir. Bu tür problemlerin kesin çözümü genellikle seçeneklerin sıralanmasıyla gerçekleşir.

"Amaç işlevi" makalesi hakkında bir inceleme yazın

notlar

Ayrıca bakınız

Edebiyat

• Burak Ya.I., Ogirko IV Sıcaklığa bağlı malzeme özelliklerine sahip silindirik bir kabuğun optimum şekilde ısıtılması // Mat. yöntemler ve fiz.-mekh. alanlar. - 1977. - Sayı. 5. - S.26-30

Amaç fonksiyonunu karakterize eden bir alıntı