Yardımla çözülen görevler arasında matematiksel programlama, çok adımlı (çok aşamalı) süreçlerin optimizasyonunu gerektiren ayrı bir problem sınıfı ayırt edilebilir. Bu tür görevler, çözümü birbiriyle ilişkili birkaç aşamaya bölme olasılığı ile ayırt edilir. Bu tür sorunları çözmek için dinamik programlama veya aynı zamanda çok aşamalı programlama da kullanılır. Yöntemleri, birkaç aşamaya, adıma vb. bölünebilen çok aşamalı problemlere en uygun çözümü bulmak için optimize edilmiştir.

terimin kökeni

Başlıkta "dinamik" kelimesinin kullanılması, başlangıçta alt görevlere bölünmenin öncelikle zaman içinde gerçekleşeceğini varsayıyordu. Zaman faktörünün ortaya çıktığı üretim, ekonomik ve diğer sorunları çözmek için dinamik yöntemler kullanırken, onu ayrı aşamalara ayırmak zor değildir. Ama tekniği kullan dinamik program bireysel aşamaların zamanla ilişkili olmadığı görevlerde de mümkündür. Her zaman çok adımlı bir görevde, ayrı adımlara bölebileceğiniz bir parametre veya özellik seçebilirsiniz.

Çok aşamalı problemleri çözmek için algoritma (yöntem)

Dinamik programlamanın algoritması veya yöntemi, çözüm olduğunda, problemin sıralı optimizasyonu ilkesinin kullanımına dayanır. ortak görev bireysel alt görevler için bir dizi çözüme ve ardından tek bir çözüme entegrasyona ayrılır. Çoğu zaman, bireysel alt görevler aynı olur ve bir ortak karar hesaplama süresini önemli ölçüde azaltır.

Yöntemin bir özelliği, sorunu her bir aşamada çözme özerkliğidir, yani, önceki aşamada sürecin nasıl optimize edildiğinden ve çözüldüğünden bağımsız olarak, mevcut hesaplamada yalnızca şu anda onu karakterize eden süreç parametreleri kullanılır. . Örneğin, bir yolda araba kullanan bir sürücü, daha önce ne kadar ve ne kadar sürdüğüne bakılmaksızın, mevcut dönüş hakkında bir karar verir.

Yukarıdan yöntem ve aşağıdan yöntem

Problemi çözmenin ayrı bir aşamasında hesaplama yapılırken, o andaki süreç parametrelerinin kullanılmasına rağmen, önceki aşamadaki optimizasyon sonucu, bir bütün olarak en iyi sonucu elde etmek için sonraki aşamaların hesaplamalarını etkiler. Dinamik programlama, bu çözüm ilkesini, ilk çözümler ve koşullar ne olursa olsun, sorunu çözmek için optimal stratejinin, tüm aşamalardaki sonraki çözümlerle, aşağıdakilere göre optimal bir strateji oluşturması gerektiğini belirleyen optimallik yöntemi olarak adlandırır. orijinal durum... Gördüğünüz gibi, problemi çözme süreci, ilkinden sonuncusuna kadar her ayrı aşamada sonucun sürekli bir optimizasyonudur. Bu yönteme üst programlama yöntemi denir. Şekil, şematik bir yukarıdan aşağıya çözüm algoritmasını göstermektedir. Ancak, son aşamadaki maksimum etkinin zaten bilindiği bir çok adımlı problemler sınıfı vardır, örneğin, A noktasından B noktasına çoktan ulaştık ve şimdi önceki her aşamada doğru bir şekilde sürüp sürmediğimizi öğrenmek istiyoruz. daha optimal bir şey yapmak mümkündü. Özyinelemeli bir aşama dizisi ortaya çıkar, yani, olduğu gibi "tersinden" gideriz. Bu çözüm yöntemine "aşağıdan yukarıya programlama yöntemi" denir.

Pratik kullanım

Dinamik programlama, bazı parametrelerle (zaman, miktar, sıcaklık vb.) birkaç özdeş küçük aşamaya bölünebilen süreçlerin olduğu herhangi bir faaliyet alanında kullanılabilir. Dinamik çözüm yöntemleri, en yaygın olarak kontrol teorisinde ve bilgisayar sistemlerinin geliştirilmesinde kullanılmaktadır.

Optimal yolu bulma

Dinamik optimizasyon yardımıyla, en kısa yolu bulma veya optimize etme konusunda geniş bir problem sınıfını ve "klasik" numaralandırma yönteminin kullanıldığı diğer problemleri çözmek mümkündür. olası seçeneklerçözüm, hesaplama süresinde bir artışa yol açar ve bazen genellikle kabul edilemez. Klasik sorun dinamik programlama bir sırt çantasıyla ilgili bir problemdir: size belirli bir kütle ve değere sahip belirli sayıda nesne verilir ve sırt çantasının hacmini aşmayan maksimum değere ve kütleye sahip bir nesne kümesi seçmeniz gerekir. Optimal çözüm arayışında tüm seçeneklerin klasik olarak sıralanması önemli miktarda zaman alacaktır ve dinamik yöntemler yardımıyla problem kabul edilebilir bir zaman çerçevesinde çözülür. Taşıma lojistiği için en kısa yolu bulma görevleri temeldir ve bunları çözmek için dinamik çözüm yöntemleri en uygunudur. Çoğu basit örnek böyle bir görev, bir araba GPS navigatörü ile en kısa rotayı oluşturmaktır.

Üretme

Dinamik programlama, herhangi bir zamanda gerekli sayıda bileşeni korumak için envanter yönetimi, zamanlama gibi çeşitli üretim görevlerinin çözümünde yaygın olarak kullanılır. üretim süreci, mevcut ve elden geçirmek ekipman, personelin tek tip iş yükü, yatırım fonlarının en verimli dağılımı vb. Dinamik programlama yöntemlerini kullanarak üretim problemlerini çözmek için özel yazılım paketleri entegre popüler sistemler SAP gibi kurumsal yönetim.

Bilimsel küre

Dinamik programlama yöntemleri çeşitli alanlarda yaygın olarak kullanılmaktadır. bilimsel araştırma... Örneğin, konuşma ve görüntü tanıma algoritmalarında, sosyolojide ve büyük veri dizilerinin işlenmesinde başarıyla kullanılmaktadırlar.

Üç ticaret işletmesinin gelişimi için 4 milyon ruble tahsis edildi. Doğrusal olmayan fonksiyonun değeri ile verilen her bir işletmedeki sermaye yatırımlarının etkinliği biliniyor mu? k (x k). Sermaye yatırımlarının işletmeler arasında dağılımı için optimal bir planın hazırlanması gerekmektedir. dağılımı olduğu varsayılmaktadır. Para x k, x k = 0, 1, 2, 3, 4 tamsayılarında gerçekleştirilir.

İlk veri.

Dinamik programlama yöntemini kullanarak sorunu para dağıtım hizmeti yardımıyla çözüyoruz.

Aşama I. Koşullu optimizasyon.

1. adım. k = 3.

2. adım. k = 2.

3. adım. k=1.

Tabloların yapımını ve hesaplama sırasını açıklayalım.

Sütun 1, 2 ve 3, üç tablonun tümü için aynıdır, dolayısıyla paylaşılabilirler. Sütun 4, gelir fonksiyonları hakkındaki ilk verilere göre doldurulur, sütun 5'teki değerler önceki tablonun 7. sütunundan alınır, sütun 6, sütun 4 ve 5'in değerlerinin toplamı ile doldurulur (içinde 3. adımın tablosu, sütun 5 ve 6 eksik).

7. sütun yazıyor maksimum değer sabit bir başlangıç ​​durumu için önceki sütunun ve 8. sütunda maksimum 7'ye ulaşılan 2 sütunun kontrolü yazılır.

Aşama II. Koşulsuz optimizasyon.

3. adımın tablosundan F * 3 (e 0 = 4) = 7.6'ya sahibiz. Yani, e 0 = 4 fon miktarı ile tüm sistemin maksimum geliri 7,6 milyon rubleye eşittir.

Aynı tablodan ilkinin ticaret işletmesi vurgula u * 1 (e 0 = 4) = 1

2. adımın tablosundan F * 2 (e 1 = 3) = 4.5'e sahibiz. Yani, tüm sistemin e 1 = 3 fon miktarıyla maksimum geliri 4,5 milyon rubleye eşittir.

Aynı tablodan, ikinci ticari işletmenin u * 2 (e 1 = 3) = 2'yi seçmesi gerektiğini bulduk.

Bu durumda, fon dengesi şöyle olacaktır:

Son ticaret şirketi 1 milyon ruble alıyor.

Böylece, dinamik programlama yöntemini kullanarak, 4 milyon ruble tutarında sermaye yatırımı bulduk. dağıtmak gerekiyor Aşağıdaki şekilde:

1 ticaret işletmesi seçin;

2. ticaret işletmesi için 2'yi seçin;

3. ticaret işletmesi için 1'i seçin;

Bu, 7,6 milyon rubleye eşit maksimum gelir sağlayacaktır.

MAKALE

"Dinamik yöntemler

programlama".

GİRİŞ

Günümüzde bilim, organizasyon ve yönetim konularına giderek daha fazla önem veriyor, bu da karmaşık amaçlı süreçleri yapıları ve organizasyonları açısından analiz etme ihtiyacına yol açıyor. Uygulamanın ihtiyaçları, "yönlem araştırması" adı altında rahatlıkla birleştirilebilecek özel yöntemlerin ortaya çıkmasına neden oldu. Bu terim, amaçlı insan faaliyetinin tüm alanlarında kararları haklı çıkarmak için matematiksel, nicel yöntemlerin kullanımına atıfta bulunur.

Yöneylem araştırmasının amacı, en iyi yol Belirli bir sorunu çözmeye yönelik eylemler. ana rol aynı zamanda matematiksel modelleme... Matematiksel bir model oluşturmak için, incelenen sistemin işleyişinin amacı hakkında kesin bir anlayışa sahip olmak ve izin verilen değerlerin aralığını belirleyen kısıtlamalar hakkında bilgi sahibi olmak gerekir. Amaç ve kısıtlamalar fonksiyonlar şeklinde sunulmalıdır.

Yöneylem araştırması modellerinde, kısıtlamaların ve amaç fonksiyonunun bağlı olduğu değişkenler ayrık (çoğunlukla tamsayı) ve sürekli (sürekli) olabilir. Buna karşılık, kısıtlamalar ve amaç fonksiyonu doğrusal ve doğrusal olmayan olarak ikiye ayrılır. var farklı yöntemler Bu modellerin çözümleri, en ünlüsü ve etkilisi, amaç fonksiyonu ve tüm kısıtlar doğrusal olduğunda doğrusal programlama yöntemleridir. Dinamik programlama yöntemleri, diğer türlerin matematiksel modellerini çözmeye yöneliktir, Tamsayılı programlama, doğrusal olmayan programlama, çok amaçlı optimizasyon ve ağ modelleri yöntemleri.

Hemen hemen tüm yöneylem araştırması yöntemleri, doğası gereği yinelemeli hesaplama algoritmaları üretir. Bu, her adımda (yineleme) kademeli olarak optimal çözüme yakınsayan bir çözüm elde ettiğimizde, problemin sırayla (yinelemeli olarak) çözüldüğü anlamına gelir.

Algoritmaların yinelemeli doğası genellikle aynı türden hacimli hesaplamalara yol açar. Bu algoritmaların temel olarak bilgisayar kullanarak uygulama için geliştirilmesinin nedeni budur.

DİNAMİK PROGRAMLAMANIN TEMEL KAVRAMLARI VE SEMBOLLERİ

Dinamik programlama matematiksel yöntemçok adımlı süreçlere özel olarak uyarlanmış optimum kontrol arayışı. Böyle bir işleme bir örnek düşünelim.

Bir grup işletmenin faaliyetlerinin planlanmasına izin verin.nyıllar. Buradaki adım bir yıldır. 1. yılın başında, bu işletmeler arasında bir şekilde dağıtılması gereken işletmelerin gelişimi için fonlar tahsis edilir. İşleyişleri sırasında tahsis edilen fonlar kısmen harcanır. Her işletme, yatırılan fonlara bağlı olarak, yıl için bir miktar gelir getirir. Yılın başında, mevcut fonlar işletmeler arasında yeniden dağıtılabilir: her birine belirli bir fon payı tahsis edilir.

Soru şudur: her yılın başında mevcut fonların işletmeler arasında nasıl dağıtılacağı, böylece tüm işletmelerden elde edilen toplam gelirinnyıl maksimum oldu?

Kontrollü bir sürecin dikkate alındığı tipik bir dinamik programlama sorunuyla karşı karşıyayız - bir grup işletmenin işleyişi. Süreç yönetimi, fonların dağıtılmasından (ve yeniden tahsis edilmesinden) oluşur. Yönetim etkisi (MC), yılın başında işletmelerin her birine bir miktar fon tahsis edilmesidir.

Her adımdaki HC, gelecekteki tüm sonuçları dikkate alınarak seçilmelidir. UV, bir bakış açısıyla ileriye dönük olmalıdır. Gelecekte diğer adımlardan en iyi sonuçların alınmasına engel olacaksa, düşünülen adımda en iyi SW'yi seçmenin bir anlamı yoktur. Her adımda, “Cgeleceğe bakmak ”, aksi takdirde ciddi hatalar mümkündür.

Gerçekten de, dikkate alınan işletmeler grubunda, bazılarının tüketim malları üretimi ile uğraştığını, bazılarının ise bunun için makineler ürettiğini varsayalım. Ayrıca, amaç için almaktırntüketim mallarının maksimum çıktı yılı. Sermaye yatırımı ilk yıl için planlansın. Bu adımın (yıl) dar çıkarlarına dayanarak, tüketim mallarının üretimine tüm araçları yatırmamız, tam güç ve yıl sonuna kadar maksimum üretime ulaşmak. Ancak böyle bir karar genel olarak doğru olur mu? Belli ki değil. Geleceği göz önünde bulundurarak, makinelerin üretimi için bir miktar fon ayırmak gerekiyor. Aynı zamanda, ilk yıldaki üretim hacmi doğal olarak azalacaktır, ancak sonraki yıllarda üretimini artıracak koşullar yaratılacaktır.

Dinamik programlama yöntemiyle problem çözme formalizminde aşağıdaki gösterim kullanılacaktır:

n- adım sayısı.

– sistemin durumunu açıklayan vektörk-inci adım.

– başlangıç ​​durumu, yaniC1. adımda durum.

– son durum, yani son adımdaki durum.

x k - kabul edilebilir devletlerin alanıkadım.

– SW vektörük-Sistemin durumdan geçişini sağlayan adımx k -1 bir eyalettex k .

sen k - kabul edilebilir hidrokarbonların alanıkadım.

W k - satış sonucunda elde edilen kazanç tutarıkadım.

S- için toplam kazançnadımlar.

– için optimal kontrol stratejisinin veya GLC'nin vektörünadımlar.

S k +1 ( ) Herhangi bir durumdan geçişte elde edilen maksimum getiri son duruma ('den başlayarak optimal kontrol stratejisi ilek+1) inci adım.

S 1 ( ) için maksimum kazançnsistemin başlangıç ​​durumundan geçişindeki adımlar Sonunda optimal bir kontrol stratejisi uygularken ... bariz kiS = S 1 ( ), Eğer - sabit.

Dinamik programlama yöntemi, art etkinin olmaması koşuluna ve amaç fonksiyonunun toplanabilirlik koşuluna dayanmaktadır.

Sonradan etki koşulu yok... Durum , sistemin içine taşındığı birk-th adım, duruma bağlıdır ve seçilen HC ve sistemin duruma nasıl geldiğine bağlı değildir , yani

Benzer şekilde, ödeme tutarıW k devlete bağlı ve seçilen HC , yani

Amaç fonksiyonunun toplanabilirlik koşulu.Toplam kazançnadımlar formülle hesaplanır

Tanım. Optimal yönetim stratejisi hidrokarbonlar kümesi denir , yani , sistemin uygulanması sonucundanilk durumdan adım geçişleri Sonunda ve aynı zamanda toplam getiriSen büyük değeri alır.

Son etkinin olmaması koşulu, Belman optimallik ilkesini formüle etmemize izin verir.

Optimallik ilkesi.

Sistemin kabul edilebilir durumu ne olursa olsun bir sonrakinden önceben-th adım, kabul edilebilir HC'yi seçmek gerekir bu adımda kazançW ben üzerindeben-th adım artı sonraki tüm adımlarda optimal getiri maksimumdu.

Optimal kontrol sorununu belirlemeye bir örnek olarak, bir grup işletmenin finansmanını yönetme sorununu ele almaya devam edeceğiz. Başlangıçta izin verbenşirketler grubunun yılı fonlar buna göre tahsis edilir: bu değerlerin toplamı üzerinde kontrol olarak kabul edilebilir.ben-inci adım, yani ... Kontrol bir bütün olarak süreç, hepsinin bir toplamıdır. adım kontrolleri, yani .

Yönetim iyi veya kötü, etkili veya etkisiz olabilir. Yönetim verimliliği gösterge ile ölçülürS... Soru ortaya çıkıyor: adım kontrollerinin nasıl seçileceği böylece değerSmaksimuma mı döndü?

Ortaya çıkan problem, optimal kontrol problemi ve göstergenin altında kontrol edildiği kontroldür.Smaksimuma ulaşana optimal denir. Optimum kontrol çok adımlı bir süreç, bir dizi optimal adım kontrolünden oluşur:

Böylece, görevle karşı karşıyayız: belirlemek optimal kontrol her adımda(i = 1,2, ... N ) ve bu nedenle, tüm sürecin optimal kontrolü .

DİNAMİK PROGRAMLAMA YÖNTEMİ FİKİRLERİ

Çok adımlı bir süreç planlarken, sonraki adımlarda gelecekteki sonuçlarını dikkate alarak her adımda bir HC seçilmesi gerektiğini belirtmiştik. Ancak bu kuralın bir istisnası vardır. Tüm adımlar arasında planlanabilecek bir adım var."geleceğe bakmadan". Bu adım nedir? Belli ki sonuncusubundan sonra başka bir adım yok. Bu adım, hepsinden sadece biri, öyle planlanabilir ki, en büyük fayda... Bu son adımı en iyi şekilde planladıktan sonra, sondan bir önceki adımı ona, sondan bir önceki adımı sondan bir öncekine vb. eklemek mümkündür.

Bu nedenle 1. aşamadaki dinamik programlama süreci uçtan uca ilerler, yani sonuncusu herkesten önce planlanır.

nadım. Bilmiyorsak nasıl planlayacağızsondan bir önceki nasıl bitti? Açıkçası, sondan bir öncekinin nasıl bittiğine dair tüm olası varsayımları yapmanız gerekiyor.( n - 1) inci adım ve her biri için son adımdaki kazancın (gelirin) maksimum olacağı şekilde bir kontrol bulun. Bu sorunu çözdükten sonra, koşullu optimal kontrol (CCC) bulacağız.n-inci adım, yani (n - 1) inci adım belli bir şekilde sona erdi.

Bu prosedürün gerçekleştirildiğini varsayalım, yani her sonuç için( n - 1) inci adımın, UOC'yi şurada biliyoruz:N-m adım ve karşılık gelen koşullu optimal getiri (OCW). Şimdi sondan bir önceki kontrol üzerindeki kontrolü optimize edebiliriz, (n- 1) inci adım. Sondan bir öncekinin nasıl bittiğine dair tüm olası varsayımları yapalım, yani( n - 2) inci adım ve bu varsayımların her biri için üzerinde böyle bir kontrol buluyoruz.(N- 1) inci adım, böylece son iki adımın getirisi (sonuncusu zaten optimize edilmiştir) maksimize edilir. Ayrıca, kontrol için optimize edilmiştir(N -2) inci adım, vb.

Kısacası, her adımda, belirli bir anda ulaşılan duruma göre sürecin optimal devamını sağlayan bir kontrol aranır. Bu kontrol seçimi ilkesine optimallik ilkesi denir. Belirli bir duruma göre sürecin en iyi şekilde devam etmesini sağlayan kendi kendini kontrol, üzerinde UOC olarak adlandırılır. bu adım.

Şimdi, her adımda UOC'yi bildiğimizi varsayalım: Her adımın başında süreç hangi durumda olursa olsun, bir sonraki adımda ne yapacağımızı biliyoruz. O zaman artık "koşullu" değil, her adımda gerçekten en uygun kontrolü bulabiliriz. |

Gerçekten de, sürecin ilk durumunu bize bildirin. Artık ilk adımda ne yapacağımızı biliyoruz: ilk adım ve ilk durum için bulunan VOC'yi uygulamamız gerekiyor. Bu kontrol sonucunda ilk adımdan sonra sistem başka bir duruma geçecek; ancak bu durum için UOC'yi biliyoruz, vb. Böylece, mümkün olan maksimum kazancı sağlayan optimal proses kontrolünü bulacağız.

Bu nedenle, dinamik programlama yöntemiyle kontrolü optimize etme sürecinde, çok adımlı süreç iki kez "yürür":

- ilk kez - UOC'nin her adımda bulunduğu ve verilen adımdan sürecin sonuna kadar tüm adımlarda optimal ödeme (ayrıca şartlı) bulunmasının bir sonucu olarak, baştan başa;

ikinci kez - sürecin tüm adımlarında optimal kontrollerin bulunmasının bir sonucu olarak baştan sona.

Optimal kontrolü oluşturma prosedürünün şöyle olduğunu söyleyebiliriz.

dinamik programlama yöntemi iki aşamaya ayrılır:

Ön hazırlık;

Son.

Ön aşamada, her adım için, sistemin durumuna (önceki adımların bir sonucu olarak elde edilen) ve verilen adımdan başlayarak kalan tüm adımlarda koşullu olarak optimal kazanıma bağlı olan bir ECA belirlenir. devlete bağlıdır. Son aşamada, her adım için (koşulsuz) optimal kontrol belirlenir. Ön (koşullu) optimizasyon, ters sırada adım adım gerçekleştirilir: son adımdan birinciye; nihai (koşulsuz) optimizasyon - ayrıca adım adım, ancak doğal bir sırayla: ilk adımdan son adıma. Optimizasyonun iki aşamasından ilki kıyaslanamayacak kadar önemli ve zahmetlidir. İlk aşamanın bitiminden sonra, ikinci zorluğun uygulanması mevcut değildir: sadece ilk aşamada hazırlanmış olan önerileri "okumak" için kalır.

Dinamik programlama problemlerine örnekler

Yöneylem araştırması yöntemlerinin çoğu, öncelikle çok özel bir içeriğin görevleriyle ilişkilidir. Klasik matematik aygıtının, aşağıdakiler de dahil olmak üzere birçok optimizasyon problemini çözmek için çok az faydası olduğu ortaya çıktı. Büyük sayı değişkenler ve/veya eşitsizlikler şeklinde kısıtlamalar. Büyük boyutlu bir problemi, sadece birkaç değişkeni içeren alt boyutlu alt problemlere bölme fikrinin çekiciliği ve daha sonra genel problemin kısımlar halinde çözümü şüphesiz çekicidir.

Dinamik programlama yönteminin temeli bu fikirdir.

Dinamik programlama (DP), yaratılması ve geliştirilmesi için kredi öncelikle Bellman'a ait olan matematiksel bir yöntemdir. Yöntem, kaynak tahsisi, değiştirme ve envanter yönetimi sorunları ve yükleme sorunları dahil olmak üzere çok çeşitli sorunları çözmek için kullanılabilir. Dinamik programlamanın bir özelliği, problemi her biri bir kontrollü değişkenle ilişkili olan aşamalar halinde çözme yaklaşımıdır. Kittekrarlayan hesaplama prosedürleri,çeşitli aşamaları birbirine bağlayarak, soruna uygun bir optimal çözüm sağlar.vbütünson aşamaya gelindiğinde.

adının kökenidinamik programmuhtemelen DP yöntemlerinin sabit aralıklarla karar verme problemlerinde (örneğin, envanter kontrol problemlerinde) kullanımı ile ilişkilidir. Ancak zaman faktörünün dikkate alınmadığı problemlerin çözümünde DP yöntemleri de başarıyla kullanılmaktadır. Bu sebeple terimçok aşamalı programlama,sorunu çözme sürecinin adım adım doğasını yansıtır.

DP teorisinin altında yatan temel ilke,optimallik ilkesi.Esasen, sırayı tanımlar adım adım çözüm tekrarlayan hesaplama prosedürlerini kullanarak problemin ayrıştırılmasına izin vermek (bu, problemin orijinal formülasyondaki doğrudan çözümünden daha kabul edilebilir bir yoldur).

Dinamik programlama, kontrollü süreçlerin optimum şekilde planlanmasını sağlar. "Kontrollü", seyri üzerinde bir dereceye kadar etkileyebileceğimiz süreçleri ifade eder.

Belirli bir amacı takip eden bir olayın veya bir dizi olayın ("operasyon") gerçekleştirildiği varsayılsın. Soru şudur: Bir operasyonun en etkili olabilmesi için nasıl organize edilmeli (planlanmalıdır)? Görevin nicel, matematiksel bir karakter kazanması için belirli bir sayısal kriteri dikkate almak gerekir.Woperasyonun kalitesini, başarısını, verimliliğini karakterize edeceğimiz. Her birinde verimlilik kriteri özel durumlar operasyonun hedef yönelimine ve araştırma görevine (hangi kontrol öğesinin optimize edildiği ve hangi amaç için) göre seçilir.

Tüm dinamik programlama problemlerinin çözümünün altında yatan genel ilkeyi ("optimite ilkesi") formüle edelim:

“Sistemin durumu ne olursa olsunSbir sonraki adımdan önce, bu adımdaki kazanç artı sonraki tüm adımlarda optimal getiri maksimum olacak şekilde bu adımdaki kontrolü seçmek gerekir. "

Dinamik programlama, her adımda yalnızca bir adımın optimize edildiği çok adımlı bir sürecin adım adım planlamasıdır. Her adımda yönetim, gelecekteki tüm sonuçları dikkate alınarak seçilmelidir.

Dinamik programlama problemlerini belirlerken aşağıdaki ilkelere göre hareket edilmelidir:

Durumu karakterize eden parametreleri (faz koordinatları) seçinSHer adımdan önce kontrollü sistem.

İşlemi aşamalara ayırın (adımlar).

Her adım için xi adım kontrolleri setini ve bunlara uygulanan kısıtlamaları öğrenin.

Eğer sistem bundan önce S durumundaysa, xi kontrolünün i-inci adımda hangi kazancı getirdiğini belirleyin, yani. "ödeme fonksiyonunu" yazın:

i. adımda xi kontrolünün etkisi altında S sisteminin S durumunun nasıl değiştiğini belirleyin: yeni bir duruma geçer

. (1.1)

Koşullu optimal getiriyi ifade eden temel tekrarlayan dinamik programlama denklemini yazınW ben ( S) (ile başlayanbensonuna kadar olan adım) zaten bilinen işlev aracılığıylaW ben +1 ( S):

. (1.2)

Bu getiri, koşullu optimal kontrole karşılık gelir.ben-inci adımx ben ( S) (ayrıca, zaten bilinen işleveW ben +1 ( S) yerine gereklidirSdeğiştirilen durumu değiştir

Sistemin ilk andaki durumu biliniyorsa (ki bu genellikle böyledir), o zaman ilk adımda sistemin durumunu değiştirmeye gerek yoktur - belirli bir başlangıç ​​durumu için doğrudan en uygun getiriyi buluruz.S 0 ... Bu, tüm operasyon için en uygun getiridir.

Bu aşamalar, tüm işlem için kazancın, bireysel adımlardaki kazanımların toplamına eşit olduğu toplamsal problemler için düşünülmüştür. Dinamik programlama yöntemi, bir çarpım biçimine sahip olan "çarpımsal" kriterle ilgili problemlere de uygulanabilir:

(eğer sadece kazançlarw ben pozitif). Bu problemler, toplama kriteri olan problemlerle aynı şekilde çözülür, tek fark, ana denklemde (1.2) artı işareti yerine çarpma işaretinin koyulmasıdır:

3.1. İş gücü planlama zorluğu

Bazı projelerde, bir projeyi tamamlamak için gereken işçi sayısı, işe alınıp işten çıkarılarak düzenlenir. Hem işçi alımı hem de işten çıkarma ek maliyetlerle ilişkilendirildiğinden proje uygulama döneminde işçi sayısının nasıl düzenlenmesi gerektiğinin belirlenmesi gerekmektedir.

Proje sırasında çalışacağını varsayalımnhaftalar ve asgari işgücü gereksinimiben-hafta olacakB ben işçiler. NS ideal koşullar için isterimben-th hafta tam olarak sahip olmakB ben işçiler. Ancak, maliyet göstergelerine bağlı olarak, işgücünün boyutunu asgari gereksinimlerden hem bir yönde hem de diğer yönde saptırmak daha avantajlı olabilir.

Eğerx ben ben-inci hafta, o zaman iki tür maliyet mümkündür: 1) C 1 ( x ben - B ben ) - fazlalığı içerme ihtiyacı ile ilgili maliyetlerx ben - B ben emek ve 2) C 2 ( x ben - x ben -1 ) - ek işe alma ihtiyacıyla ilişkili maliyetler (x ben - x ben -1 ) işçiler.

Dinamik programlama modelinin öğeleri aşağıdaki gibi tanımlanır:

Sahneі haftanın sıra numarası ile temsil edilirі , і =1,2,… n.

için çözüm seçenekleriі -inci aşama değerlerdirx ben - sırasında çalışan sayısıі- hafta.

açıkbenaşamax ben -1 - sırasında çalışan sayısı (і- 1) –. hafta (aşama).

Tekrarlayan dinamik programlama denklemi şu şekilde temsil edilir:

nerede

Hesaplamalar bir adımla başlarnNSx n = B n ve 1. aşamada sona erer.

3.2. Ekipman değiştirme sorunu

Mekanizma ne kadar uzun süre çalışır durumda kalırsa, bakım maliyeti o kadar yüksek ve verimliliği o kadar düşük olur. Mekanizmanın ömrü belli bir seviyeye ulaştığında değiştirilmesi daha karlı olabilir. Bu nedenle ekipmanı değiştirme görevi, mekanizmanın optimum hizmet ömrünü belirlemeye gelir.

Mekanizmaları değiştirmekle meşgul olduğumuzu varsayalım.nyıllar. Her yılın başında mekanizmanın bir yıl daha işletilmesine veya yenisiyle değiştirilmesine karar verilir.

ile belirtelimr( T) veC( T) operasyondan elde edilen karT- yıl boyunca mekanizma ve aynı dönem için bakım maliyeti. Daha fazla izins( T) - çalıştırılan mekanizmanın satış maliyetiTyıllar. Yeni bir mekanizma edinmenin maliyeti yıllar içinde değişmeden kalır ve şuna eşittir:ben.

Dinamik programlama modelinin unsurları aşağıdaki gibidir:

Sahneі yılın sıra numarası ile temsil edilirben, ben = 1,2, ...n.

için çözüm seçenekleriі -inci aşama (yani i için-Vayyıl) alternatiflerdir: çalışmaya devam edin veya mekanizmayı başlangıçta değiştirinі- vay yıl.

açıkі -inci aşama hizmet ömrüdürT(yaş) başlama mekanizmasıі yıl.

İzin vermekF ben ( T) yıllar içinde elde edilen maksimum kârdır.і öncenbaşlangıçta olması şartıylaі- hangi yıl bir mekanizma varT-yaşında.

Tekrarlayan denklem aşağıdaki gibidir:

(1) - mekanizmayı çalıştırırsanız,

(2) - mekanizma değiştirilirse.

3.3. Yatırım zorluğu

Aşağıdakilerin her birinin başında varsayalımnyıl yatırım yapılması gerekiyorP 1 , P 2 ,…, P n sırasıyla. İki bankaya yatırım yapma fırsatınız var: ilk banka yıllık bileşik faiz ödüyorr 1 , ve ikinci -r 2 ... Mevduatı teşvik etmek için her iki banka da yeni yatırımcılara yatırılan miktarın yüzdesi olarak prim öder.

Bonuslar yıldan yıla değişir veі yıl eşittirQ ben 1 veQ ben 2 sırasıyla birinci ve ikinci bankalarda. Mevduatın yapıldığı yılın sonuna doğru ödenir ve gelecek yıl iki bankadan birine yatırılabilir. Bu, iki bankadan birine yalnızca belirtilen faiz ve yeni paranın yatırılabileceği anlamına gelir. Bankaya yatırılan depozito, incelenen dönemin sonuna kadar orada kalmalıdır. -1) NSYılın.

İzin vermekF ben (x ben ) aralığı için en uygun yatırım tutarıdır.benöncenyıl başında olmak şartıylabenyıl bir miktar para varx ben n-th yıl için ifadelerde, yatırımlardan birikmiş nakit tutarının bir parçasıdır.s n katmaQ n 1 veQ n 2 .

yani bu durumda dinamik programlama algoritmasında geriye doğru süpürme için özyinelemeli denklem şu şekildedir:

neredex ben +1 aracılığıyla ifadex ben yukarıdaki formüle göre veF n +1 (x n +1 )=0.

4. Genel yapı dinamik program

Bir dizi ardışık karar vermek için en uygun stratejiyi bulmak, çoğu durumda şu şekilde gerçekleştirilir: ilk olarak, zaman içindeki son karar seçilir, daha sonra, zamanın akışının tersi yönde hareket ederken, diğer tüm kararlar alınır. ilkine kadar seçilir.

Böyle bir yöntemi uygulamak için, bir seçimin gerçekleşebileceği tüm durumları bulmak gerekir. son karar... Genellikle bir kararın verildiği koşullara sistemin "durumu" denir. Sistemin durumu, gelecekteki kararlar verildiğinde davranışını tahmin etmeye izin veren sistemin bir tanımıdır. Şu veya bu durumun nasıl ortaya çıktığını veya önceki kararların neler olduğunu öğrenmeye gerek yok. Bu, bir seferde yalnızca bir çözümü sırayla seçmenize olanak tanır. kullanarak en uygun çözümleri arayıp aramadıklarına bakılmaksızın tablo yöntemi ve sonraki arama veya analitik yolla, bir zamanda bir çözüme göre bir seçim yapmak, ardından bir sonraki ana geçmek vb. genellikle daha hızlı ve daha karlıdır. Ne yazık ki, tüm karar verme süreçleri bu yöntemle incelenemez. Dinamik programlama yönteminin uygulanması için gerekli bir koşul, tüm kararların fiyatlarının toplanmasının yanı sıra belirli bir devletin geçmişinden gelecekteki sonuçların bağımsızlığıdır.

Kararların sayısı çok büyükse, her bir ardışık karar çiftine karşılık gelen tahminler, karar başına ortalama "gelir" olan sabit bir değer ile birbirinden farklı olacak şekilde durumların göreceli tahminlerini oluşturmak mümkündür. Ayrıca gelecekteki kararlardan elde edilen gelirlerin iskonto edilmesini de gerçekleştirebilirsiniz. Buna ihtiyaç bazen, örneğin yılda bir kez, kararlar nadiren alındığında ortaya çıkar. O zaman çok sayıda çözüme ulaşmak için sırayla 1,2,3 ... çözümleri düşünmeye gerek kalmaz. Bunun yerine, genellikle önemli hesaplama tasarrufları sağlayan bir fonksiyonel denklemle doğrudan çalışmak mümkündür.

ÇÖZÜM

Pratik problemlerin çözümünde dinamik yöntemlerin uygulanmasının en az dört yönü vardır.

1. Sistemin iyileştirilmesi ekonomik bilgi. dinamik yöntemler ekonomik bilgi sistemini düzene sokmanıza, mevcut bilgilerdeki boşlukları belirlemenize ve eğitim gereksinimleri geliştirmenize olanak tanır yeni bilgi veya düzeltmeleri. Ekonomik ve matematiksel modellerin geliştirilmesi ve uygulanması, belirli bir planlama ve yönetim problemlerini çözmeye odaklanan ekonomik bilgileri iyileştirmenin yollarını gösterir. Ilerleme bilgi desteği planlama ve yönetim, hızla gelişen teknik ve yazılım bilişim.

2. Ekonomik hesaplamaların doğruluğunun yoğunlaştırılması ve iyileştirilmesi. Ekonomik sorunların resmileştirilmesi ve bilgisayarların kullanılması, standart, toplu hesaplamaları büyük ölçüde hızlandırır, doğruluğu artırır ve emek yoğunluğunu azaltır ve "manuel" teknolojinin egemenliği altında erişilemeyen karmaşık önlemler için çok değişkenli ekonomik gerekçelerin gerçekleştirilmesini mümkün kılar. .

3. Derinleşme nicel analiz ekonomik sorunlar... Dinamik programlama yönteminin uygulanması sayesinde, belirli nicel analiz olanakları önemli ölçüde artırılır, etkileyen birçok faktörün incelenmesi ekonomik süreçler, ekonomik nesnelerin gelişimi için koşullardaki değişikliklerin sonuçlarının nicel değerlendirmesi, vb.

küre pratik uygulama Bu yöntemlerin bir kısmı, ekonomik problemlerin ve durumların resmileştirilmesinin olasılıkları ve etkililiğinin yanı sıra bilgi, matematiksel, teknik Destek kullanılan modeller. Her ne pahasına olursa olsun, matematiksel bir model uygulama arzusu vermeyebilir. iyi sonuçlar gerekli koşulların en azından bazılarının olmaması nedeniyle.

Modern bilimsel kavramlara uygun olarak, ekonomik kararlar alma ve geliştirme sistemleri, resmi ve gayri resmi yöntemleri birleştirmeli, karşılıklı olarak pekiştirmeli ve birbirini tamamlamalıdır. Resmi yöntemler, her şeyden önce, yönetim süreçlerinde insan eylemleri için bilimsel olarak doğrulanmış materyal hazırlama araçlarıdır. Bu, bir kişinin deneyimini ve sezgisini, kötü resmileştirilmiş sorunları çözme yeteneğini verimli bir şekilde kullanmanızı sağlar.

SSCB İç Tahmincisi'nin yeterince genel kontrol teorisi

14. Algoritmik bir ifade olarak dinamik programlama yöntemi yeterlidir genel teori yönetmek

Dinamik programlama yönteminin özünü sunarken, “Course of Theory” kitabına güveniyoruz. otomatik kontrol”(Palu de La Barrière tarafından: Fransızca baskı 1966, Rus baskısı- "Makine Mühendisliği", 1973), sunumunu tekrar etmesek de. Yu.P. Zaichenko'nun "İşlem Araştırması" kursundan bazı hükümler alınmıştır (Kiev, "Vishcha Shkola", 1979).

Gerçek bir problemin biçimsel yorumu aşağıdaki koşulların karşılanmasına izin veriyorsa, dinamik programlama yöntemi verimlidir:

1. İncelenen problem şu şekilde temsil edilebilir: n-oranla açıklanan adımlı süreç:

X = f (XU, n), nerede n- setlerden birinin numarası olası durumlar tamamlandıktan sonra geçiş yaptığı sistem n-inci adım; x bahsedilen sisteme ait sistem durum vektörüdür n-inci küme; sen- adımda geliştirilen kontrol n(adım kontrolü), sistemi olası durumundan diğerine aktarır. n durumlardan birine ayarlayın ( n + 1) küme. Bunu görselleştirmek için Şek. 4 hangisi hakkında Olacak Daha öte.

2. Tahmini adım sayısı değiştirilirken görevin yapısı değişmemelidir. N.

3. Sistemin durumunu tanımlayan parametre uzayının boyutu, adım sayısına bağlı olarak değişmemelidir. N.

4. Herhangi bir adımdaki kontrol seçimi, önceki adımlardaki kontrol seçimini reddetmemelidir. Başka bir deyişle, olası durumlardan herhangi birinde optimal kontrol seçimi, sistemin söz konusu duruma girdiği sürecin parametreleri tarafından değil, incelenen durumun parametreleri tarafından belirlenmelidir.

Tamamen biçimsel olarak, eğer bir durum, sonraki optimal kontrolün seçimini etkileyen, oluşumunun farklı tarihçelerine karşılık geliyorsa, o zaman yöntem, tarih öncesi tanımlarının durum vektörüne dahil edilmesine izin verir, bu da boyutunda bir artışa yol açar. sistemin durum vektörü. Bu işlemden sonra, önce bir durum olarak tanımlanan şey, sürecin tarihöncesini tanımlayan durum vektörünün bileşenleri ile birbirinden farklı olan bir durumlar kümesi haline gelir.

5. Kriter optimal seçim adım kontrolleri dizisi sen ve uzayda karşılık gelen yörünge resmi parametrelerşuna benziyor:

V = V (X, U) + V (X, U) +…+ V (X, U) + V (X).

kriter V aramak adettendir tam galibiyet, ve içerdiği terimler - adım kazanır... Bulmanız gereken görevde adım kontrol sırasısen ve mümkün olan maksimuma karşılık gelen yörünge toplam kazanç... Esasen tam bir "kazan" V- yönetim kalitesinin bir ölçüsü tüm süreç... Adım kazanımları, bir bütün olarak süreç kontrolünün kalitesinin ölçüsüne dahil edilmekle birlikte, v Genel dava Yöntem, bir bütün olarak sürecin kontrolünü optimize etmek için tasarlandığından, ilgili adımlardaki kontrol kalitesinin ölçüleri değildir ve muhteşem adım kontrolleri büyük bir adım kazancıyla, ancak dışarıda uzanarak optimal yörünge, ilgi alanı değildir. Yöntemin yapısı, gerekirse, her adımda, adım kazancını belirlemek için kriterin kullanılmasını yasaklamaz. V, diğer adımlarda benimsenen kriterlerden farklıdır.

indeksli n- olası durum vektörleri kümelerinin bir gösterge-belirleyicisi - gerçek problemlerde, belirli bir değişen parametre ilişkilendirilebilir, örneğin: zaman, kat edilen mesafe, güç seviyesi, belirli bir kaynağın tüketim ölçüsü vesaire. Yani, yöntem sadece zaman içinde devam eden süreçlerin kontrolünü optimize etmek için değil, aynı zamanda çok değişkenli tek adımlı optimizasyon problemlerine veya hassasiyete duyarsız optimizasyon problemlerine de uygulanabilir. zamançözümler, eğer bu tür “zamansız”, “süreçsiz” problemler çok adımlı yorumlarını kabul ediyor.

Şimdi şek'e dönelim. 4 - şek. 6, birbirine bağlı Şek. P. de La Barrier'in otomatik kontrol teorisi dersinden 40, 41, 42.

Pirinç. 4. Dinamik programlama yönteminin özüne. Fırsat matrisi.

İncirde. Şekil 4, sistemin ilk durumunu - "0" ve olası sonraki durumlarının kümesini - "1", "2", "3" ve ayrıca her olası durumdan diğer olası durumlara olası geçişleri gösterir. Bütün bunlar birlikte, çiplerin hareket ettiği çocuklar için bir masa oyununun haritasına benziyor: her geçiş adımı, kendi adım kazancına karşılık geliyor ve süreci sona erdiren üçüncü sette, sistemin her bir durumu kendisine atanıyor. puan, bir dikdörtgene yerleştirilir. temel fark oyundan, çocuk oyunlarında kullanılan, zar atmaya veya top döndürmeye vb. dayalı yol seçimi hakkında falcılıktır. gerçek yönetim kabul edilemez, çünkü bu, kemik kaybını, tepenin dönmesini vb., yani. Oyunda seçilen "rastgele jeneratör"ün (hedeflerine göre) kontrollü bir cihaz için yeterli olduğu kişiler için.

İlk adımda optimal kontrolü seçersek, sonraki adımlarda tüm sonuçlarını öngörmek gerekir. Bu nedenle, dinamik programlama yönteminin algoritmasının açıklaması, genellikle, sürecin son durumlarından birine yol açan son adımda kontrol seçiminin bir açıklaması ile başlar. Aynı zamanda, algoritmayı son durumdan ilk duruma tanımlamadaki argümantasyonun algılanmasının daha kolay olduğunu kanıtlayan "pedagojik uygulamaya" atıfta bulunurlar. zaten kurulmuş gibi düşünülen adım koşullarının başlangıcına kadar, sürecin olası tamamlanması da belirlenir.

Pirinç. 5. Dinamik programlama yönteminin özüne. Geçişlerin analizi.

Buna göre, Şekil. Şekil 5, önceki "2" durum kümesindeki her olası durumdan son durum kümesi "3"e olası geçişleri analiz eder, sanki önceki yolun tamamı çoktan geçilmiş ve tamamlanacak en uygun adım kontrolünün son seçimi olarak kalır tüm süreç. Bu durumda, "2" kümesindeki durumların her biri için belirlenir. herşey toplam kazanç = "geçiş puanı" + "terminal durumu puanı". Her bir durum için elde edilen "2" setinde, olası toplam kazanç belirlenir ve hatırladı maksimum toplam getiri ve karşılık gelen geçiş (yörünge parçası). "2" kümesindeki durumların her biri için maksimum toplam getiri dikdörtgen bir çerçeve içinde gösterilir ve karşılık gelen geçiş bir okla işaretlenir. Prensipte, bir durumdan diğerine, toplam kazancın aynı değerine karşılık gelen bu tür birkaç optimal geçiş olabilir. Bu durumda, hepsi yöntemde ayırt edilemez ve sistemi tanımlayan parametreler uzayında bir yörünge seçiminin optimalliği için oluşturulmuş kriter anlamında birbirine eşdeğerdir.

Bundan sonra, son işlemden önce gelen "2" kümesi, "3" kümesi, olası durumlarının her birinin tahminleri (maksimum toplam kazançlar) bilindiğinden ve daha fazla optimizasyon olduğundan, son işlem olarak kabul edilebilir. adım kontrollerinin sırası ve optimal yörüngenin seçimi, yalnızca optimize edilmiş süreçte "2" kümesinden önce dikkate alınmayan başka kümeler için gerçekleştirilebilir (yani, "0" ve "1" kümelerinde).

Böylece, Şekil 2'de gösterilen prosedür. 5, geçişler üzerine yöntemin her algoritmik adımında etkilidir. n ince (n - 1)-th set, bitişten başlayarak n sistemin ilk durumuna ayarlayın.

Kümelerin sıralı ikili sayımının bir sonucu olarak, kümelerinin tamamından geçerken, ardışık adım kontrollerinin optimal sırası, mümkün olan maksimum toplam getiri ve karşılık gelen yörünge belirlenir. İncirde. Şekil 6'da, kalınlaştırılmış çizgi, dikkate alınan örnek için en uygun yörüngeyi göstermektedir.

Pirinç. 6. Dinamik programlama yönteminin özüne. Optimal yörünge.

Ele alınan örnekte, optimallik kriteri, adım kazançlarının toplamıdır. Ancak optimallik kriteri aynı zamanda bir ürün olarak da oluşturulabilir. mutlaka negatif olmayan faktörler.

Sonuç (toplam veya ürün), terimler veya faktörlerle yapılan işlemlerin sırası değiştirildiğinde değişmediğinden, algoritma, olası durum kümelerini, dikkate alınanın tersi sırayla sıralarken de etkilidir: yani. olası durumların ilk kümesinden son kümesine.

Olası durum kümeleri kronolojik sırayla sıralanırsa, bu, tasarım şemasının hem gerçek zamandan tahmin edilene hem de inşa edilebileceği anlamına gelir. kesin gelecek ve öngörülenden kesin geleceği gerçek şimdiki zamana. Bu durum iki gayri resmi ilişkiden bahsediyor gerçek hayat algoritma dışında:

1. Dinamik programlama yöntemi, neden-sonuç koşullarının doğasına resmi olarak algoritmik olarak duyarsızdır (özellikle, nedenler ve sonuçlar arasında ayrım yapmaz). Bu nedenle, yöntemin her bir özel yorumu, uygulamalı görevler Sonuçların nedenlere göre gerçek koşulluluğunun gayri resmi bir hesabıyla oluşturulmalıdır.

2. Öngörü, hiyerarşik olarak daha yüksek kapsayıcı kontrole uygunsa ve kapsayıcı kontrole gömülü özel, nitelikli gerçekleştirilirse, özel kontrol süreci hiyerarşik olarak daha yüksek kapsayıcı kontrol ile uyumlu olarak ilerler, o zaman ARASINDA YÖNETİM OLARAK ÖNEMLİ BİR FARK YOKTUR.

Süreç, her ne sebeple olursa olsun, ayrılmaz bir bütündür, henüz gerçekleşmemiş, ancak ahlaki olarak seçilmiş ve yukarıdan nesnel olarak yasaklanmamış olan gelecek, mevcut şimdiki zamanda, onu her düzeyde yaratanları korur: psişeyi takıntılardan korumaktan. amaçlı “fiziksel” saldırganlıktan korumaktır. Diğer bir deyişle, olası durumların matrisi (diğer bir deyişle olası geçişlerin matrisi), hiyerarşik olarak daha yüksek kapsamlı kontrol ile uyumlu olarak seçilirse, o zaman kendisi bir savunma ve bir silahtır, bir kontrol aracıdır ve genelleştirilmiş silahların altı önceliğinin tümü için bir kontrol aracıdır. ve kontrol kilitlenir.

nesnel varlık olası durumların ve geçişlerin matrisleri Körlükte kişinin bazı geçiş matrislerinde "gezinebilmesi" ve nesnel özelliklerini kendi üzerinde hissedebilmesi gerçeğinde kendini gösterir. İkincisi, bu özelliklere karşı tutuma bağlı olarak, nadir görülen bir şans dizisi veya sıkıcı bir "ilk kareye dönüş" veya ciddi bir kötü şans dizisi olarak öznel olarak değerlendirilir.

Ancak dinamik programlama yöntemini ve buna eşlik eden algoritmada resmileştirilmemiş gelişmeyi kullanmak geçiş matrislerinin hayati belirtileri, ana koşullara uymalısınız:

Kontrol süreçlerinin optimizasyonu problemlerinde, "gerçek gelecek: - varsayılan olarak" dinamik programlama yöntemi, yalnızca kontrol hedefleri vektörü tanımlanırsa, yani. sonlandırma işlemi seçilmelidir.

Gerçekte, bu nihai kesin durum, yöntem tarafından optimize edilen belirli bir süreci kucaklayan ve taşıyan, kasıtlı olarak kararlı ve kabul edilebilir bir süreç olmalıdır. Ancak, yöntemin algoritması tamamlandıktan sonra kontrollü sistemin girmesi gereken sürecin belirli özelliklerinin seçimi ve belirlenmesi, bu yöntemin dışında - "tasavvuf" alanında ya da esasen olmayan yöntemlerle geliştirilen yöntemler alanında yatmaktadır. matematiksel bilimler ve el sanatları.

“Bir sonraki adımdan önce sistemin durumu ne olursa olsun, bu adımdaki getiri artı sonraki tüm adımlardaki optimal getiri maksimum olacak şekilde bu adımda kontrolü seçmek gerekir”, - ES Ventzel, “İşlem Araştırması. Amaçlar, ilkeler, metodoloji. " (M., "Bilim", 1988, s. 109).

Kontrol hedeflerinin vektörünü belirleyememesi (bunun başarılması yöntemde optimize edilen süreci tamamlaması gerekir) ve (veya) kontrol nesnesinin ilk durumunu tanımlayamama, bu tavsiyenin izlenmesine izin vermez; objektif olarak kapsar dinamik programlama yöntemini kullanma olasılığı, sürecin başlangıcı ve sonu, yöntemin matematiksel (veya diğer) modelinin inşa edildiği, metrolojik olarak tutarlı olması gereken, temel olan parametreler alanında belirlenmelidir. gerçeklikle olan ilişkisi nedeniyle. Ayrıca, kesinlik tamamlama Optimize edilmiş sürecin, kontrol nesnesinin ilk durumunun tanımlanmasındaki (tanımlanması) hatalardan ve bazı belirsizliklerden yönetimsel olarak daha büyük bir önemi vardır.

Bu, olası durumların matrisi atasözüne uyuyorsa, ardışık çok değişkenli adım geçişleri için daha da doğrudur. "Tüm yollar Roma'ya çıkar"", ... Bu tür işlemler için tercih etmeniz halinde zaman içinde kararlı hedef ve birçok yörünge ona yol açar, daha sonra istikrarlı adım adım kontrol ile, farklı noktalardan aynı hedefe giden optimal yörüngeler arasındaki "mesafe" ilk durumlar, adımdan adıma, belirli bir adımdan başlayarak optimal yörüngelerin tam çakışmasına kadar azalır. Bu ifade, parametre uzayındaki son hedef vektörünün konumu ne kadar kesin olursa, o kadar doğrudur. Matematikle analojiyle buna şöyle denilebilir: yörüngeler kümesinin asimptotik doğası, "tüm yolların" Roma'ya "gittiği gerçeğiyle ifade edilir..."

Ve daha genel bir durumda, Yeni Ahit ve Kuran'ın tavsiyeleri, uyandığı ve onu gördüğü andaki ilk durumuna (bir kişinin günahkârlığı) bakılmaksızın, Yüce'nin merhametini, lütfunu kazanma olasılığını onaylar. oldukları gibi işler.

Başka bir açıklama zaten uygulamayla - geçiş matrisine girişle ilgilidir. Sistemin ilk durumu, gerçek başlangıç ​​durumundan seçilen son duruma geçiş matrisine girmek için izin verilenden daha büyük bir hatayla belirlenirse, dinamik programlama yönteminin kendisinin hatasız algoritmasına dayalı kontrol yol açacaktır. sistemin hesaplanan optimal durumuna değil, tamamen farklı sonuçlara. Kabaca söylemek gerekirse, açık bir pencereyi yüksek bir kattaki bir odayı terk etmekle karıştırmamak gerekir.

Yani, dinamik programlama yöntemi, hem sürecin son durumunun seçiminde kesinliğe hem de gerçek başlangıç ​​durumunun tanımlanmasına duyulan ihtiyaç, kendi kendine yokluğunda kontrol optimizasyonunun bilimsel taklidi için kullanılmasından korunur. Bu, özellikle dinamik programlama yöntemini, optimizasyon kriterlerinde ağırlık katsayılarının “uzmanları” tarafından doğaçlama tahminlerin yüklenmesinin mümkün olduğu doğrusal programlama aparatından ayırır. Minimum (Z) veya Maks (Z).

Bu kendi başına haksız kullanımdan korunma, modern ekonomi bilimi literatürüne dolaylı olarak yansır: devlet ekonomisiyle ilgili yönetim hedefleri vektörünün ne olduğuna karar vermediğinden, yönetimi optimize etmek için dinamik programlama aparatının kullanımı hakkında yayın yoktur. bölgelerin ve devletlerin makroekonomik sistemlerinin genel olarak tarihsel olarak uzun zaman aralıklarında

Bunun örnekleri “Matematiksel İktisat kişisel bilgisayar”Ed. Ekonomide yönetimle ilgili bölümün, doğrusal programlama aygıtının yalnızca makroekonomik yorumlarını içerdiği M. Kuboniva (bu, tam olarak “Ekonomide yönetim” olarak adlandırılan şeydir. Doğrusal programlama ve uygulaması ”), ancak kontrol hedefleri ve kontrollerinin vektörü hakkında hiçbir şey söylemez; Yu.P. Zaichenko tarafından daha önce alıntılanan ders kitabında, dinamik programlama yönteminin açıklaması da farklı nitelikteki sorunlara dayanmaktadır.

Bununla birlikte, dinamik programlama yönteminin makroekonomik yorumlarının reddedilmesini motive ederken, yazarlar genellikle, parametre uzayının boyutunun büyümesinin olduğu gerçeğiyle ifade edilen hesaplamalı matematikte “boyutluluğun laneti” olarak adlandırılır. problemin n ile orantılı olarak hesaplama miktarında bir artışa neden olur. N,üs nerede k "1. Hesaplama miktarındaki böyle doğrusal olmayan aşırı orantısal bir artış, aslında birçok hesaplamalı uygulanabilir prosedürü çözmede işe yaramaz hale getirir. pratik görevler hem bilgisayar zamanının çok fazla harcanması hem de yaklaşık hesaplamalardaki hataların birikmesi nedeniyle. Ancak bu “boyutluluk laneti” yalnızca dinamik programlama yöntemi için değil, aynı zamanda makroekonomik yorumlarında da karşılaşılan diğer yöntemler için de geçerlidir.

Anlayış kitabından yazar Efimov Viktor Alekseevich

4. Yeterince Genel Kontrol Teorisi (DOTU). Ülkenin gerçek yönetimi ancak tam işlevine göre mümkündür. Ülkede uygulanan yönetim ilkeleri (en iyisini istediler, ancak her zaman olduğu gibi ortaya çıktı) şemalar hakkında temel fikirlerin olmadığını gösteriyor.

"Uluslararası terörizm" küresel tehdidinin ortadan kaldırılması üzerine kitaptan yazar SSCB İç Tahmincisi

Konu 5'ten Sapma: Sibernetik ve Kontrol Teorisi Tarihi Yirminci yüzyılın ikinci yarısı boyunca sibernetik, N tarafından halka sunulduğu şekliyle olmasına rağmen, topluma genel olarak bir kontrol bilimi olarak sunulmaktadır. Wiener, gerçekten değil

yazar SSCB İç Tahmincisi

1. Oldukça genel bir yönetim teorisi: neden gerekli? Evrenin yapılarının karşılıklı yuvalanma hiyerarşisinde herhangi bir zihin - bireysel veya uzlaştırıcı - öncelikle hiyerarşik olarak daha düşük sistemlerle ilgili yönetim sorunlarını ve kendi kendini yönetme görevlerini çözer.

Kitaptan 12 konu. 21. yüzyıl pazarlaması yazar Grant J

2. Yeterince genel bir kontrol teorisinin kategorileri Kontrol teorisinde sadece iki problemi formüle etmek mümkündür: · İlk problem: nesneyi doğrudan işleyişi sürecinde kontrol etmek istiyoruz. Bu ikinci görev: süreçte nesneyi manipüle etmek istemiyoruz.

"Şu anda" kitabından 7 (79), 2008 yazar SSCB İç Tahmincisi

Gennady Shichko kitabından ve yönteminden yazar Drozdov Ivan

Bölüm 1. Tam işlev kalabalık- "elitizm" ve gerçek demokraside yönetim 1.1. Tam yönetim işlevi ve toplum yaşamında uygulanmasının ilkel uygulaması Oldukça genel bir yönetim teorisinde (DOTU) "tam yönetim işlevi" kavramı vardır. Tam işlev

Petrol Tükendiğinde, İklim Değişikliği Olduğunda ve Diğer Afetler Başladığında Bizi Neler Bekliyor kitabından yazar Kunstler James Howard

Yeni Oprichnina veya Rusça Modernleşme kitabından yazar Kalaşnikof Maksim

Petrol Tükendiğinde Bizi Neler Bekliyor, İklim Değişikliği ve 21. Yüzyılın Diğer Felaketleri kitabından yazar Kunstler James Howard

Yenilik döngülerinin küçülmesi bir ulusal hayatta kalma meselesidir: Dinamik Muhafazakarlık Enstitüsü'nün bir mutabakatı 10 Haziran 2009'da Dinamik Muhafazakarlık Enstitüsü'nde yenilikçi uygulayıcılar ve bilim adamlarından oluşan bir uzman toplantısı şu konu üzerine yapıldı: “Gerçek yenilikler ve onların

Anti-Semitizm: Kavramsal Nefret kitabından yazar Altman İlya

Kitaptan Genel yeterince kontrol teorisi yazar SSCB İç Tahmincisi

MARK WEIZMAN'a Teşekkür Bu kitap Simon Wiesenthal onuruna hazırlanmıştır. Genellikle bu tür koleksiyonlar seçkin bilim adamlarının onuruna yayınlandığından, kitabı Simon'a ithaf etme fikri son derece uygundu. Araştırmacı konumunu işgal etmeden veya

Kitaptan Ben Bir Dahi miyim? yazar Vengar Vin

1. Oldukça genel bir yönetim teorisi: neden gerekli? Evrenin yapılarının karşılıklı yuvalanma hiyerarşisinde herhangi bir zihin - bireysel veya uzlaştırıcı - öncelikle hiyerarşik olarak daha düşük sistemlerle ilgili yönetim sorunlarını ve kendi kendini yönetme görevlerini çözer.

Keynes'in Rusya'yı Nerede Aradığı kitabından? yazar Dzarasov Soltan

2. Yeterince genel bir kontrol teorisinin kategorileri Kontrol teorisinde sadece iki problemi formüle etmek mümkündür: · İlk problem: nesneyi doğrudan işleyişi sürecinde kontrol etmek istiyoruz. Bu.

Yazarın kitabından

14. Yeterince genel bir kontrol teorisinin algoritmik bir ifadesi olarak dinamik programlama yöntemi Dinamik programlama yönteminin özünü sunarken, "Otomatik kontrol teorisinde Ders" kitabına güveniyoruz (Palu de La Barrier tarafından: Fransızca

Yazarın kitabından

Teşekkür Yeniden Doğuş Projesi Hızlandırılmış Öğrenme Programı Ana konu Bu kitabın - çabalar sayesinde 25 yıl önce gerçekleştirilmeye başlandı büyük miktar insanlar, insan bilinci çalışmasında öncüler, katılanlar

Yazarın kitabından

3. Genel Bir Teoriye Doğru Aynı zamanda Rus devrimi onun tarafından ciddi bir uyarı olarak algılandı. Keynes, ona karşı tüm olumsuz tutumuna rağmen, onun öne sürdüğü sorunlara artan bir ilgiyle tepki gösterdi ve bu, dikkatini daha geniş bir alana yöneltmekten başka bir şey yapamadı.

Dinamik programlama, karar verme sürecinin adımlara bölünebildiği bir optimizasyon tekniğidir. Her adım, kontrol nesnesini kontrol yoluyla durumdan duruma aktarır. Eğer toplam tutar adımlar eşit , o zaman çeşitli kontrollerin eyleminin bir sonucu olarak aldığı sistemin durumlarının sırası hakkında konuşabiliriz.Sistemin amaç fonksiyonu, başlangıç ​​durumuna ve kontrole bağlıdır.

Sistemin th adım sonundaki durumunun sadece bir önceki duruma ve th adımdaki kontrole bağlı olduğu varsayılır. Daha sonra sistemin durum denklemi şu şekildedir:

Amaç fonksiyonu, her adımın etkinlik göstergesinin toplamı olarak kabul edilirse, o zaman adımda ve amaç fonksiyonu forma sahiptir

Dinamik programlama probleminin çözümü böyle bir kontrol tanımlamaktır. , sistemi durumdan duruma en yüksek (en düşük) değerde aktarır.

Dinamik programlama problemini çözmek için sözde optimallik ilkesi formüle edildi. Anlamı şu şekilde özetlenebilir: Herhangi bir sayıda adımın gerçekleştirilmesi sonucunda sistemin durumu ne olursa olsun, bir sonraki adımdaki kontrol, sonraki tüm adımlarda optimal kontrol ile birlikte maksimum değere ulaşacak şekilde seçilmelidir. dahil olmak üzere kalan tüm adımlarda kazanç elde edin.

Son adıma bir göz atalım. Adımın başlangıcında sistemin durumu, kontrol ve - hedef fonksiyon. Optimallik ilkesine göre, kontrol, herhangi bir durum için amaç fonksiyonunun koşullu maksimumu elde edilecek şekilde seçilmelidir.

Elde edilen karar, adımda koşullu optimal kontrol olarak adlandırılır. Son adımda sistemin tüm olası durumları için amaç fonksiyonunun koşullu maksimumu aranır. Daha sonra, son ve sondan bir önceki adımlar birlikte değerlendirilir. Bu durumda amaç fonksiyonu şu şekildedir:

Koşullu optimal kontrol iki son adımlar x sondan bir önceki adımda sistemin tüm olası durumları için

Bilinen bir kontrole sahip sistemin durumu şu şekilde tanımlanır: , bununla bağlantılı olarak amaç fonksiyonu sadece önceki adımdaki duruma ve mevcut kontrole bağlıdır. Daha sonra, üç, dört vb. değerlendirilir. son adımlar. Genel durumda, adım için, dinamik programlama yöntemini ilk geliştiren Belman denklemi elde edilir.

Sonuç olarak koşullu optimizasyon kriter fonksiyonunun değer dizileri ve koşullu kontroller elde edilebilir

Dinamik programlama probleminin çözümü, ilk adımda ve çözüm için ifadeye belirli bir değer konarak elde edilir. Ardından, ilk adımın durumu belirlenir

ve benzeri tüm adımlar için. Problemin optimal çözümü sıralı hesaplama ile elde edilir. optimal çözümler ve yeni devletler .

NS pratik uygulama bir bilgisayarda dinamik programlama yönteminde, özellikle kontrol nesnesinin durumunu tanımlama yöntemleriyle ilişkili bir takım zorluklar ortaya çıkar. Kural olarak, her adımda kontrol nesnesinin sonlu sayıda durumu dikkate alınır. Bununla birlikte, en büyük ilgi, bir nesnenin optimal durumunu aşağıdakilerden bulma durumudur. sonsuz sayı olası durumlar, örneğin matematiksel programlama yöntemiyle. Mevcut literatürde böyle bir malzeme yoktur, ayrıca dinamik programlama yönteminin yazılım uygulaması hakkında bilgi yoktur, ancak bu tür problemlerin çözümü için ihtiyaç oldukça fazladır. Söylenenlerden yola çıkarak dinamik programlama yöntemlerini pratik kullanım acil ve önemli bir araştırma görevini temsil eder.