Yöneylem araştırması kavramının doğru tanımı şu şekildedir: Yöneylem araştırmasının konusu ve görevleri

1. Yapay zekanın temel kavramları

VE HAKKINDA – Çeşitli örgütsel sistemlerin en etkili yönetimi için yöntemlerin geliştirilmesi ve pratik uygulanmasıyla ilgilenen bilimsel muhalefet.

IO aşağıdaki bölümleri içerir:

1) matematik programı. (planların gerekçesi, ekonomik faaliyet programları); şu bölümleri içerir: doğrusal program, doğrusal olmayan program, dinamik program

2) rastgele süreçler teorisine dayanan kuyruk teorisi;

3) eksik bilgi koşulları altında alınan kararların gerekçelendirilmesine olanak tanıyan oyun teorisi.

Belirli bir kontrol problemini çözerken yapay zeka yöntemlerinin kullanımı şunları içerir:

Karmaşık durumlarda veya belirsizlik koşullarında karar verme problemlerine yönelik ekonomik ve matematiksel modellerin oluşturulması;

Daha sonra karar almayı belirleyen ilişkilerin incelenmesi ve belirli bir eylem planının avantajının değerlendirilmesine olanak tanıyan performans kriterlerinin oluşturulması.

IO'nun temel kavramları ve tanımları.

Operasyon – Bir hedefe ulaşmayı amaçlayan her türlü kontrollü faaliyet. Operasyonun sonucu, uygulama yöntemine, organizasyonuna, aksi takdirde belirli parametrelerin seçimine bağlıdır. Bir operasyon her zaman kontrollü bir olaydır, yani organizasyonunu karakterize eden bazı parametreleri nasıl seçeceğimize bağlıdır. Burada "organizasyon", operasyonda kullanılan teknik araçlar kümesini de içeren, kelimenin geniş anlamıyla anlaşılmaktadır.

Herhangi bir özel parametre seçimine denir karar . Kararlar başarılı ve başarısız, makul ve mantıksız olabilir. En uygun şu ya da bu nedenle diğerlerine tercih edilen çözümleri düşünün. Yöneylem araştırmasının asıl görevi, optimal çözümlerin ön niceliksel gerekçelendirilmesidir.

Operasyon modeli – bu, matematiksel aygıtlar (çeşitli işlevler, denklemler, denklem ve eşitsizlik sistemleri vb.) kullanılarak yapılan işlemin oldukça doğru bir açıklamasıdır. Bir operasyonun modelini hazırlamak, açıklanan olgunun özünün anlaşılmasını ve matematiksel aparatın bilinmesini gerektirir.

Operasyon verimliliği – göreve uyarlanabilirlik derecesi niceliksel olarak bir verimlilik kriteri (hedef fonksiyon) şeklinde ifade edilir. Etkililik kriterinin seçimi çalışmanın pratik değerini belirler. (Yanlış seçilen bir kriter zararlı olabilir, çünkü bu tür bir verimlilik kriterine göre düzenlenen operasyonlar bazen haksız maliyetlere yol açabilmektedir.)

Ağ planlama ve yönetim görevleri Büyük bir operasyon kompleksinin (işlerin) tamamlanma tarihleri ​​ile kompleksin tüm operasyonlarının başlangıç ​​​​zamanları arasındaki ilişkiyi düşünün. Bu görevler, bir dizi operasyonun minimum süresini, maliyet değerlerinin optimal oranını ve bunların uygulanma zamanlamasını bulmaktan oluşur.

Kuyruk sorunları uygulama kuyrukları veya gereksinimleri olan hizmet sistemlerinin incelenmesine ve analizine ayrılmıştır ve sistemlerin performans göstergelerinin, bunların optimal özelliklerinin, örneğin hizmet kanallarının sayısının, hizmet süresinin vb. belirlenmesinden oluşur.

Envanter yönetimi görevleri stok seviyesinin (sipariş noktası) ve sipariş boyutunun optimal değerlerini bulmaktan oluşur. Bu tür görevlerin özelliği, stok seviyesinin artmasıyla birlikte bir yandan bunları depolama maliyetlerinin artması, diğer yandan depolanan üründeki olası bir kıtlıktan kaynaklanan kayıpların azalmasıdır.

Kaynak Tahsisi Sorunları Sınırlı mevcut kaynaklarla gerçekleştirilmesi gereken belirli bir dizi operasyon (iş) sırasında ortaya çıkar ve kaynakların operasyonlar arasında en uygun dağılımını veya operasyonların bileşimini bulmak gerekir.

Ekipman onarımı ve değiştirme görevleri ekipmanın aşınması ve yıpranması ve zaman içinde değiştirilmesi ihtiyacı nedeniyle geçerlidir. Görevler, optimum zamanlamanın, önleyici onarım ve denetimlerin sayısının ve ayrıca ekipmanın ne zaman modernleştirilmiş ekipmanla değiştirileceğinin belirlenmesine kadar uzanır.

Görevleri zamanlama (zamanlama) çeşitli ekipman türlerinde en uygun işlem sırasının (örneğin parçaların işlenmesi) belirlenmesinden oluşur.

Planlama ve yerleştirme görevleri nia mevcut nesnelerle ve birbirleriyle etkileşimlerini dikkate alarak yeni nesnelerin en uygun sayısını ve konumunu belirlemeyi içerir.

Rota seçimi sorunları veya ağ ulaşım ve iletişim sistemlerindeki çeşitli problemlerin incelenmesinde en sık karşılaşılan problemler ve en ekonomik güzergahların belirlenmesinden ibarettir.

2. Genel doğrusal program problemi. Çözümü optimize etme

Ekonomik-matematiksel model

LP, birçok değişkenin doğrusal bir fonksiyonunun, doğrusal kısıtlamaların, yani bu değişkenleri birbirine bağlayan eşitlikler veya eşitsizliklerin varlığında ekstremumunu (maksimum veya minimum) bulma problemlerini çözmek için teori ve sayısal yöntemler geliştiren bir matematik dalıdır.

LP yöntemleri aşağıdaki pratik problemlere uygulanır: 1) çeşitli olası çözümlerden en iyi çözümün (optimal plan) seçilmesinin gerekli olduğu; 2) çözüm, bazı değişkenlerin bir dizi değeri olarak ifade edilebilir; a) problemin belirli koşulları tarafından uygulanabilir çözümlere getirilen kısıtlamalar, doğrusal denklemler veya eşitsizlikler biçiminde formüle edilir; 4) amaç, ana değişkenlerin doğrusal bir fonksiyonu şeklinde ifade edilir. Farklı çözümlerin karşılaştırılmasına olanak sağlayan amaç fonksiyonunun değerleri, çözümün kalitesi için bir kriter görevi görür.

Bir ekonomik problemi matematiksel yöntemler kullanarak pratik olarak çözmek için, öncelikle ekonomik-matematiksel bir model kullanılarak yazılması gerekir. Ekonomik-matematiksel model, incelenen ekonomik sürecin veya nesnenin matematiksel bir açıklamasıdır. Bu model, ekonomik sürecin yasalarını matematiksel ilişkileri kullanarak soyut bir biçimde ifade eder.

Model oluşumunun genel şeması: I

1) belirli sayıda değişken niceliğin seçimi; sayısal değerlerin atanması, incelenen olgunun olası durumlarından birini benzersiz bir şekilde belirler;

2) incelenen olgunun doğasında var olan ilişkilerin matematiksel ilişkiler (denklemler, eşitsizlikler) biçiminde ifadesi. Bu ilişkiler problem için bir kısıtlamalar sistemi oluşturur;

3) seçilen optimallik kriterinin amaç fonksiyonu biçiminde niceliksel ifadesi; BEN

4) değişkenlere uygulanan kısıtlamaların yerine getirilmesine bağlı olarak, amaç fonksiyonunun ekstremumunu bulma problemi olarak problemin matematiksel formülasyonu.

Genel doğrusal programlama problemişu forma sahiptir:

n değişkenli m doğrusal denklem ve eşitsizliklerden oluşan bir sistem verildiğinde

ve doğrusal fonksiyon

F doğrusal fonksiyonunun optimal (yani maksimum veya minimum) değeri aldığı X=(x1,x2,…,xj,…,xn) sistemine bir çözüm bulmak gerekir.

Sistem (1) kısıt sistemi olarak adlandırılır ve F fonksiyonuna doğrusal fonksiyon, doğrusal form, amaç fonksiyonu veya amaç fonksiyonu denir.

Daha kısaca genel doğrusal programlama problemi şu şekilde temsil edilebilir:

kısıtlamalarla:

Optimum çözüm (veya optimal plan) Bir LP probleminin çözümü X=(x1,x2,…,xj,…,xn), bir kısıtlar sistemi (1), koşulu (3) karşılayan ve doğrusal fonksiyonun (2) optimal değeri üstlendiği bir çözümdür. (maksimum veya minimum) değer.

Tüm değişkenlerin negatif olmaması koşuluyla, kısıtlama sistemi (1) yalnızca eşitsizliklerden oluşur - böyle bir doğrusal programlama problemine standart (simetrik) denir; Kısıtlama sistemi yalnızca denklemlerden oluşuyorsa soruna kanonik denir.

Kanonik bir problemin özel bir durumu, kısıt vektörünün tüm katsayılarının olmasıyla karakterize edilen, temel formdaki bir problemdir. B negatif değildir ve her denklemde, diğer denklemlerin hiçbirinde yer almayan, katsayısı 1 olan bir değişken vardır. Bu özelliğe sahip bir değişkene temel denir.

Standart ve kanonik problemler genel problemlerin özel durumlarıdır. Her biri kendi alanında kullanılmaktadır. Üstelik her üç formülasyon da birbirine eşdeğerdir: herhangi bir doğrusal programlama problemi, basit matematiksel dönüşümler kullanılarak kanonik, standart veya genel bir probleme indirgenebilir.

4 . Doğrusal cebirin elemanları

N değişkenli m doğrusal denklem sistemi şu şekildedir:

veya kısaca

n değişkenli m doğrusal denklem sisteminin herhangi bir m değişkeni (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

(2.1) sistemini m koşulu altında çözmek< n сформулируем утверждение.

Açıklama 2.1. Sistem için iseMile doğrusal denklemlerNdeğişkenler (M < N) değişkenler için katsayılar matrisinin sırası m'ye eşittir, yani. En az bir grup temel değişken varsa, o zaman bu sistem belirsizdir ve temel olmayan değişkenlerin her keyfi değer kümesi, sistemin bir çözümüne karşılık gelir.

Çözüm Sistem (2.1)'in X=(x1,x2,…,xn)'si yalnızca negatif olmayan bileşenler içeriyorsa kabul edilebilir olarak adlandırılır; Herhangi bir j=1,n için xj>=0. Aksi takdirde çözüm geçersiz olarak adlandırılır.

Sistemin sonsuz sayıdaki çözümleri arasında temel çözümler olarak adlandırılanlar öne çıkıyor.

Temel çözüm n değişkenli m doğrusal denklem sisteminin çözümü, tüm n-m küçük değişkenlerin sıfıra eşit olduğu bir çözümdür.

Doğrusal programlama problemlerinde kabul edilebilir temel çözümler veya diğer adıyla referans planları özellikle ilgi çekicidir. Ana değişkenlerden en az birinin sıfıra eşit olduğu temel çözüme dejenere denir.

Dışbükey nokta kümeleri

Dışbükey bir çokgeni dışbükey olmayan bir çokgenden ayıran ortak tanımlayıcı özellik, herhangi iki noktasından alıp bunları bir doğru parçasıyla birleştirirseniz, parçanın tamamının o çokgene ait olmasıdır. Bu özellik dışbükey bir nokta kümesi tanımlamak için kullanılabilir.

Bir dizi noktaya dışbükey denir, eğer herhangi iki noktasıyla birlikte bu noktaları birleştiren doğru parçasının tamamını içeriyorsa.

Dışbükey kümelerin önemli bir özelliği vardır. mülk: Herhangi bir sayıda dışbükey kümenin kesişimi (ortak kısmı) bir dışbükey kümedir.

Dışbükey bir kümenin noktaları arasında iç, sınır ve köşe noktaları ayırt edilebilir.

Bir kümenin bir noktasına iç nokta denir, eğer komşuluklarından bazıları yalnızca bu kümenin noktalarını içeriyorsa.

Bir kümenin bir noktasına sınır noktası denir, eğer mahallelerinden herhangi biri hem verilen kümeye ait noktaları hem de ona ait olmayan noktaları içeriyorsa.

Doğrusal programlama problemlerinde özellikle ilgi çekici olan köşe noktalarıdır. Kümenin noktasına denir açısal(veya aşırı), eğer verilen kümeye tamamen ait olan herhangi bir bölümün içinde değilse.

İncirde. 2.4 çokgenin çeşitli noktalarının örneklerini gösterir: iç (M noktası), sınır (N noktası) ve köşe (A, B, C, D, E noktaları). A noktası bir köşe noktasıdır, çünkü tamamen bir çokgene ait olan herhangi bir parça için, örneğin AP parçası için, bu iç değildir; A noktası KL doğru parçasının içindedir ancak bu doğru parçası tamamen çokgene ait değildir.

Dışbükey bir küme için köşe noktaları her zaman çokgenin (çokyüzlü) köşeleriyle çakışırken, dışbükey olmayan bir küme için bu gerekli değildir. Bir nokta kümesi, tüm sınır noktalarını içeriyorsa kapalı olarak adlandırılır. Noktalar kümesine denir sınırlı, verilen kümeyi tamamen içeren, kümenin herhangi bir noktasında merkezi olan sonlu uzunlukta yarıçaplı bir top (daire) varsa; aksi takdirde kümenin sınırsız olduğu söylenir.

Sonlu sayıda köşe noktasına sahip bir düzlemdeki dışbükey kapalı noktalar kümesi, sınırlıysa dışbükey çokgen, sınırsızsa dışbükey çokgen bölge olarak adlandırılır.

Eşitsizliklerin, denklemlerin ve sistemlerinin çözümlerinin geometrik anlamı

Eşitsizliklerin çözümlerini düşünelim.

İfade 1. İki değişkenli a11x1+a12x2 eşitsizliğinin çözüm kümesi<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

İstenilen yarım düzlemi (üst veya alt) belirlemek için, sınırında - inşa edilmiş düz çizgide - yer almayan rastgele bir kontrol noktasının ayarlanması önerilir. Bir eşitsizlik bir kontrol noktasında geçerliyse, kontrol noktasını içeren yarı düzlemin tüm noktalarında geçerli olur, diğer yarı düzlemin tüm noktalarında geçerli olmaz. Tersine, eğer bir eşitsizlik bir kontrol noktasında sağlanmıyorsa, kontrol noktasını içeren yarı düzlemin tüm noktalarında sağlanmaz ve diğer yarı düzlemin tüm noktalarında sağlanır. Oluşturulan çizgi üzerinde yer almayan O (0;0) koordinatlarının kökenini kontrol noktası olarak almak uygundur.

Eşitsizlik sistemlerinin bir dizi çözümünü ele alalım.

İfade 2. İki değişkenli doğrusal eşitsizliklerin ortak sisteminin çözüm kümesi bir dışbükey çokgendir (veya bir dışbükey çokgen bölgedir).

Eşitsizliklerin her biri, Açıklama 1'e göre, dışbükey bir nokta kümesi olan yarım düzlemlerden birini tanımlar. Doğrusal eşitsizliklerin ortak sisteminin çözüm kümesi, tüm eşitsizliklerin çözümlerinin yarı düzlemlerine ait olan noktalardır; bunların kesişimine aittir. Dışbükey kümelerin kesişimiyle ilgili açıklamaya göre bu küme dışbükeydir ve sonlu sayıda köşe noktası içerir; dışbükey bir çokgendir (dışbükey çokgen alandır).

Köşe noktalarının koordinatları - çokgenin köşeleri - karşılık gelen çizgilerin kesişme noktalarının koordinatları olarak bulunur.

Eşitsizlik sistemleri için çözüm alanları oluştururken başka durumlar da ortaya çıkabilir: çözüm kümesi dışbükey bir çokgen alandır (Şekil 2.9, a); bir nokta (Şekil 2.9, b); eşitsizlik sistemi tutarsız olduğunda boş bir küme (Şekil 2.9, c).

5 . LP problemlerini çözmek için geometrik yöntem

LP problemine optimal çözüm

Teorem 1. DP probleminin optimal bir çözümü varsa, doğrusal fonksiyon maksimum değerini çözüm çokyüzlüsünün köşe noktalarından birinde alır. Doğrusal bir fonksiyon birden fazla köşe noktasında maksimum değer alıyorsa, bu değeri bu noktaların dışbükey doğrusal birleşimi olan herhangi bir noktada alır.

Teorem DP problemlerini çözmenin temel yolunu gösterir. Aslında, bu teoreme göre, aralarında arzu edilen optimal çözümü bulmak için sonsuz sayıda uygulanabilir çözüm kümesini incelemek yerine, çözüm çokyüzlüsünün yalnızca sonlu sayıda köşe noktasını incelemek gerekir.

Bir sonraki teorem köşe noktalarını bulmanın analitik yöntemine ayrılmıştır.

Teorem 2. DP probleminin kabul edilebilir her temel çözümü, çözüm çokyüzlünün bir köşe noktasına karşılık gelir ve bunun tersi de çözüm çokyüzlünün her köşe noktasına, kabul edilebilir bir temel çözüme karşılık gelir.

Doğrudan Teorem 1 ve 2'den önemli bir sonuç çıkar: Eğer bir DP probleminin optimal bir çözümü varsa, o zaman kabul edilebilir temel çözümlerden en az biriyle örtüşüyor demektir.

Bu yüzden, DP probleminin doğrusal fonksiyonunun optimumu, kabul edilebilir temel çözümlerinin sonlu sayısı arasında aranmalıdır.

Dolayısıyla, DP probleminin uygulanabilir çözümleri (çözüm çokyüzlü) kümesi, dışbükey bir çokyüzlüdür (veya dışbükey çokyüzlü bölge) ve problemin en uygun çözümü, çözüm çokyüzlüsünün köşe noktalarından en az birinde yer alır.

Sorunu iki değişkenli standart formda düşünün (P = 2).

Kısıtlama sisteminin geometrik görüntüsü bir çokgen olsun ABCDE(Şekil 4.1). Bu çokgenin noktaları arasında F=c1x1+c2x2 doğrusal fonksiyonunun maksimum (veya minimum) değerini alacağı bir nokta bulmak gerekir.

Hadi sözde düşünelim seviye çizgisi doğrusal fonksiyon F yani bu fonksiyonun aynı sabit değeri aldığı çizgi A yani F = A, veya c1x1+c2x2=a.

Çözüm poligonunda fonksiyon düzeyi çizgisinin geçtiği noktayı bulun F en yüksek (eğer doğrusal fonksiyon maksimuma çıkarılıyorsa) veya en düşük (eğer minimuma indiriliyorsa) seviyeye sahip.

c1x1+c2x2=a fonksiyonunun seviye çizgi denklemi düz çizgi denklemidir. Farklı seviyelerde A seviye çizgileri paraleldir, çünkü açısal katsayıları yalnızca c1 ve c2 katsayıları arasındaki ilişkiyle belirlenir ve bu nedenle eşittir. Böylece fonksiyon seviyesi çizgileri F – Bunlar, genellikle koordinat eksenlerine açılı olarak yerleştirilmiş tuhaf "paralelliklerdir".

Doğrusal bir fonksiyonun seviye çizgisinin önemli bir özelliği, çizgi bir yönde paralel olarak kaydırıldığında yalnızca seviyenin artması, diğer yönde kaydırıldığında ise yalnızca azalmasıdır. Orijinden çıkan c=(c1,c2 vektörü, F fonksiyonunun en hızlı artış yönünü gösterir. Doğrusal fonksiyonun seviye çizgisi c=(c1,c2 vektörüne diktir).

LP problemini grafiksel olarak çözme prosedürü:

1. Çözümlerden oluşan bir çokgen oluşturun.

2. Bir c=(c1,c2) ​​vektörü oluşturun ve önce bunun için doğrusal bir fonksiyon düzeyi çizgisi çizin Förneğin F=0.

3. F=0 düz çizgisinin c(-c) vektörü yönünde paralel hareketi ile F'nin maksimuma (minimum) ulaştığı Amax(Bmin) noktasını bulun.

1. Optimum noktada kesişen doğruların denklemlerini ortak çözerek koordinatlarını bulun.

2.Fmax(Fmin)'i hesaplayın.

Yorum. Minimum nokta çözüm poligonuna “giriş” noktası, maksimum nokta ise poligondan “çıkış” noktasıdır.

6. Simpleks yönteminin genel fikri. Geometrik yorumlama

Grafiksel yöntem, çok dar bir doğrusal programlama problemleri sınıfına uygulanabilir: ikiden fazla değişken içermeyen problemleri etkili bir şekilde çözebilir. Doğrusal programlamanın temel teoremleri dikkate alındı; buradan, eğer bir doğrusal programlama probleminin optimal bir çözümü varsa, o zaman çözüm çokyüzlüsünün en az bir köşe noktasına karşılık gelir ve kabul edilebilir temel çözümlerden en az biriyle çakışır. kısıtlama sistemi. Herhangi bir doğrusal programlama problemini çözmenin bir yolu gösterildi: Kısıtlamalar sisteminin sonlu sayıda uygulanabilir temel çözümlerini sıralamak ve bunlar arasından amaç fonksiyonunun optimal çözümü yapacağı çözümü seçmek. Geometrik olarak bu, çözüm çokyüzlüsünün tüm köşe noktalarının numaralandırılmasına karşılık gelir. Böylesine kapsamlı bir araştırma, en sonunda (varsa) optimal bir çözüme yol açacaktır, ancak bunun pratik uygulaması çok büyük zorluklarla ilişkilidir, çünkü gerçek problemler için uygulanabilir temel çözümlerin sayısı, sonlu olmasına rağmen son derece büyük olabilir.

Aramanın rastgele yapılmaması ancak doğrusal fonksiyondaki değişiklikler dikkate alınması durumunda, aranacak izin verilen temel çözümlerin sayısı azaltılabilir; Doğrusal fonksiyonun değerlerine göre sonraki her çözümün bir öncekinden “daha ​​iyi” (veya en azından “daha ​​kötü olmaması”) olmasını sağlamak (maksimumu bulurken arttırmak, minimumu bulurken azaltmak) . Bu arama, optimumu bulurken adım sayısını azaltmanıza olanak tanır. Bunu grafiksel bir örnekle açıklayalım.

Uygun çözümlerin bölgesi bir çokgenle temsil edilsin ABCDE. Diyelim ki köşe noktası A orijinal uygun temel çözüme karşılık gelir. Rastgele bir arama, poligonun beş köşe noktasına karşılık gelen beş uygun temel çözümün test edilmesini gerektirir. Ancak çizimden açıkça görülüyor ki, zirveden sonra A komşu bir köşeye geçmek avantajlıdır İÇİNDE, ve sonra en uygun noktaya İLE. Beş yerine yalnızca üç köşeden geçtik ve doğrusal fonksiyonu sürekli olarak geliştirdik.

Çözümü başarılı bir şekilde iyileştirme fikri, doğrusal programlama problemlerini çözmek için evrensel bir yöntemin temelini oluşturdu - Simpleks yöntemi veya planın sıralı olarak iyileştirilmesi yöntemi.

Simpleks yönteminin geometrik anlamı, kısıtlama çokyüzlüsünün bir köşesinden (ilk nokta olarak adlandırılır) komşuya sıralı bir geçişten oluşur; burada doğrusal fonksiyon, ilgili olarak en iyi (en azından en kötü değil) değeri alır. problemin amacı; optimal çözüm bulunana kadar - hedef fonksiyonunun optimal değerinin elde edildiği tepe noktası (eğer problemin nihai bir optimumu varsa).

Simpleks yöntemi ilk olarak 1949'da Amerikalı bilim adamı J. Danzig tarafından önerildi, ancak 1939'da yöntemin fikirleri Rus bilim adamı L.V. Kantoroviç.

Herhangi bir doğrusal programlama probleminin çözülmesine olanak sağlayan simpleks yöntemi evrenseldir. Şu anda bilgisayar hesaplamaları için kullanılıyor, ancak simpleks yöntemini kullanan basit örnekler manuel olarak çözülebilir.

Simpleks yöntemini uygulamak için - çözümün sıralı olarak iyileştirilmesi - ustalaşmak gerekir üç ana unsur:

bir problemin herhangi bir başlangıçtaki uygulanabilir temel çözümünü belirlemek için bir yöntem;

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

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

Simpleks yöntemini kullanmak için doğrusal programlama probleminin kanonik forma indirgenmesi gerekir; Kısıtlama sistemi denklemler şeklinde sunulmalıdır.

Literatür yeterince ayrıntılı olarak açıklanmaktadır: ilk destek planının bulunması (ilk kabul edilebilir temel çözüm), ayrıca yapay temel yönteminin kullanılması, en uygun destek planının bulunması, simpleks tabloların kullanılmasıyla problemlerin çözülmesi.

7 . Simpleks yönteminin algoritması.

ZLP'nin çözümünü simpleks yöntemini kullanarak ele alalım ve bunu maksimizasyon problemiyle ilişkili olarak sunalım.

1. Problemin koşullarına göre matematiksel modeli derlenir.

2. Tamamlanan model kanonik forma dönüştürülür. Bu durumda, başlangıç ​​referans planına sahip bir temel belirlenebilir.

3. Problemin kanonik modeli, tüm serbest terimlerin negatif olmamasını sağlayacak şekilde simpleks tablo şeklinde yazılmıştır. Başlangıç ​​referans planı seçilirse 5. adıma geçin.

Simpleks tablo: Kısıt denklemleri sistemi ve amaç fonksiyonu, başlangıç ​​esasına göre çözülmüş ifadeler biçiminde girilir. F amaç fonksiyonunun katsayılarının yazıldığı çizgiye F çizgisi veya amaç fonksiyonu doğrusu denir.

4. Başlangıç ​​referans planı, F-sıralı elemanların işaretleri dikkate alınmadan, minimum simpleks ilişkilerine karşılık gelen pozitif çözümleyici elemanlarla simpleks dönüşümleri yapılarak bulunur. Dönüşümler sırasında, serbest terim dışında tüm elemanları sıfır olan bir 0 satırıyla karşılaşılırsa, o zaman problemin kısıt denklemleri sistemi tutarsızdır. Serbest terim dışında başka pozitif unsurun bulunmadığı bir 0 satırıyla karşılaşırsak, kısıtlayıcı denklem sisteminin negatif olmayan çözümü yoktur.

(2.55), (2.56) sisteminin indirgenmesine yeni bir temel diyeceğiz. simpleks dönüşümü . Simpleks dönüşümü resmi bir cebirsel işlem olarak kabul edilirse, bu işlemin bir sonucu olarak rollerin belirli bir doğrusal fonksiyonlar sisteminde yer alan iki değişken arasında yeniden dağıtıldığı fark edilebilir: bir değişken bağımlıdan bağımsıza, diğeri ise bağımlıdan bağımsıza gider tam tersine, bağımsızdan bağımlıya. Bu işlem cebirde şu şekilde bilinir: Ürdün eleme adımı.

5. Bulunan başlangıç ​​destek planı optimallik açısından incelenir:

a) F satırında hiçbir olumsuz unsur yoksa (serbest terimi saymazsak), o zaman plan optimaldir. Sıfır yoksa, o zaman tek bir optimal plan vardır; en az bir sıfır varsa, sonsuz sayıda optimal plan vardır;

b) F satırında pozitif olmayan öğelerden oluşan bir sütuna karşılık gelen en az bir negatif öğe varsa; o zaman;

c) F satırında en az bir negatif öğe varsa ve sütununda en az bir olumlu öğe varsa, o zaman optimal olana daha yakın yeni bir referans planına geçebilirsiniz. Bunu yapmak için, belirtilen sütunun minimum simpleks oranını kullanarak çözümleyen bir sütun olarak atanması, çözümlenen satırın bulunması ve bir simpleks dönüşümü gerçekleştirilmesi gerekir. Ortaya çıkan referans planı, optimallik açısından yeniden incelenir. Tanımlanan süreç, optimal bir plan elde edilene veya problemin çözülemezliği ortaya çıkana kadar tekrarlanır.

Temelde yer alan bir değişkenin katsayıları sütununa çözümleme denir. Böylece, F satırının negatif elemanına göre tabana eklenen bir değişkeni seçerek (veya bir çözümleme sütunu seçerek), F fonksiyonunun artmasını sağlarız. .

Temelden çıkarılacak değişkenin belirlenmesi biraz daha zordur. Bunu yapmak için, serbest terimlerin çözümleme sütununun pozitif öğelerine oranlarını oluştururlar (bu tür ilişkilere simpleks denir) ve aralarında hariç tutulan değişkeni içeren satırı (çözümlemeyi) belirleyen en küçük olanı bulurlar. Minimum simpleks ilişkisine göre tabandan hariç tutulan bir değişkenin seçimi (veya çözümleme çizgisinin seçimi), daha önce de belirlendiği gibi, yeni referans planındaki temel bileşenlerin pozitifliğini garanti eder.

Algoritmanın 3. noktasında serbest terimler sütununun tüm öğelerinin negatif olmadığı varsayılmaktadır. Bu gereklilik gerekli değildir, ancak karşılanırsa, sonraki tüm simpleks dönüşümleri yalnızca hesaplamalar için uygun olan pozitif çözümleme elemanlarıyla gerçekleştirilir. Serbest terimler sütununda negatif sayılar varsa çözümleme elemanı şu şekilde seçilir:

1) bir negatif serbest terime, örneğin bir t satırına karşılık gelen satıra bakın ve içindeki bazı negatif öğeleri seçin ve karşılık gelen sütun çözümleyici olarak alınır (problemin kısıtlamalarının tutarlı olduğunu varsayarız);

2) serbest terimler sütununun öğelerinin, aynı işaretlere sahip çözümleme sütununun karşılık gelen öğeleriyle ilişkilerini oluşturmak (basit ilişkiler);

3) Simpleks ilişkilerin en küçüğünü seçin. Bu, etkinleştirme dizesini belirleyecektir. Mesela şöyle olsun R-astar;

4) çözümleyen sütun ve satırın kesişiminde bir çözümleyici öğe bulunur. Eğer y satırının elemanı çözümleniyorsa, simpleks dönüşümünden sonra bu satırın serbest terimi pozitif olacaktır. Aksi halde bir sonraki adımda t satırına tekrar erişilir. Sorun çözülebilirse, belirli sayıda adımdan sonra serbest terimler sütununda hiçbir olumsuz unsur kalmayacaktır.

8. Ters matris yöntemi

Şu formdaki bir LP'yi ele alalım:

A – kısıtlama matrisi;

C=(c1,c2,…,cn)–satır vektörü;

X=(x1,x2,…,xn) – değişkenler;

sağ tarafın vektörüdür.

Tüm denklemlerin doğrusal olarak bağımsız olduğunu varsayıyoruz; sıra(a)=m. Bu durumda baz, A matrisinin mertebesinden küçük bir değerdir. Yani, |B| olacak şekilde m mertebesinden en az bir B alt matrisi vardır.<>0. B'ye karşılık gelen tüm bilinmeyenlere temel denir. Diğerlerinin tümü ücretsizdir.

B bir taban olsun. Daha sonra A matrisinin sütunlarını yeniden düzenleyerek A'yı her zaman A=(B|N) formuna indirgeyebiliriz.

burada N, A matrisinin tabana ait olmayan sütunlarından oluşan bir alt matristir. Aynı şekilde, x vektörünü temel değişkenlerden oluşan bir vektöre bölmek mümkündür.

Problem (1)'in herhangi bir çözümü A*x=b koşulunu karşılar ve dolayısıyla sistem aşağıdaki formu alır:

Çünkü |B|<>0 ise ters bir matris vardır. Soldan tersiyle çarptığımızda şunu elde ederiz:

- ortak karar.

Temel çözüm (B tabanına göre), bu koşul altında elde edilen problem (2)'nin özel bir çözümüdür. Daha sonra benzersiz bir şekilde belirlenir.

Temel çözüm denir gerçekleştirilebilir, Eğer.

Uygulanan temel çözüme karşılık gelen temel. İsminde uygulanabilir esas. Vektörün sıfır bileşeni varsa temel çözüme dejenere denir.

Genel çözüm mevcut tüm çözümleri içerir. Amaç fonksiyonuna dönelim. Temel değişkenlerin önüne Cb – katsayılarını, geri kalanını ise Cn'ye dahil ediyoruz.

Böylece elde ederiz. Genel çözümden şunu değiştiriyoruz:

İfade. Temel çözüm için eniyilik kriteri.

Diyelimki. O halde temel çözüm optimaldir. Eğer öyleyse, temel çözüm optimal değildir.

Belge:İzin vermek. Temel çözümü ele alalım, .

Bu nedenle temel çözüm için amaç fonksiyonunun değeridir.

Başka bir çözüm olsun: (Xb,Xn).

O zaman bakalım

Böylece temel çözüm en min. Aksine yerine getirilmesin, yani. var.

O zaman amaç fonksiyonunun değerinin temel çözüme ait amaç fonksiyonunun değerinden küçük olacağı bir çözüm vardır.

Xi:Xj serbest değişkenine karşılık gelsin, bir değer atayıp onu tabana girelim ve başka bir değişken türetip ona serbest diyoruz.

Nasıl belirlenir? dışındaki tüm serbest değişkenler de hala 0'a eşittir.

Sonra genel çözümde nerede.

Hadi şunu çıkaralım: – gerekli bir koşul.

Temel bir çözüme düzenli if adı verilir. Değişkeni tabandan türetiyoruz. Yeni bir çözümle amaç fonksiyonu azalır çünkü

Algoritma:

1.LP problemi standart formda.

2. Doğrusal bağımsız denklemleri bırakıyoruz.

3. |B| olacak şekilde bir B matrisi bulun.<>0 ve temel çözüm.

Hesaplıyoruz:

eğer öyleyse, o zaman bir optimal çözüm vardır – bu temel çözümdür;

eğer öyleyse bileşeni buluruz, ekleriz ve böylece başka bir çözüm buluruz; – temel değişkenlerden biri =0. Bu değişkeni temelden çıkarıyoruz ve xi'yi tanıtıyoruz. B1 bazına eşlenik yeni bir B2 bazı elde ettik. Daha sonra tekrar hesaplıyoruz.

1. Eğer bir optimal çözüm varsa, sınırlı sayıda adımdan sonra onu elde ederiz.

Geometrik olarak prosedür, X kümesinin - problemin çözüm kümesinin - sınırı boyunca bir köşe noktasından birleşik köşe noktasına geçiş olarak yorumlanır. Çünkü sonlu sayıda köşe noktası vardır ve F(x) fonksiyonunun kesin azalması aynı uç noktadan iki kez geçmeyi yasaklar, o zaman eğer bir optimal çözüm varsa, o zaman sonlu sayıda adımdan sonra onu elde ederiz.

9. Kaynak kullanımı sorunuyla ikili olarak sorunun ekonomik yorumu

Görev. P1 ve P2 olmak üzere iki tür ürün üretmek için S1, S2, S3, S4 olmak üzere dört tür kaynak kullanılır. Kaynak rezervleri, yani bir üretim biriminin üretimi için harcanan kaynak birimi sayısı verilmektedir. P1 ve P2 üretim birimlerinden elde edilen kar bilinmektedir. Satışından elde edilen kârın maksimum olacağı bir üretim planı hazırlamak gerekmektedir.

GörevBEN(orijinal):

Kısıtlamalarla F=c1x1+c2x2+…+CnXn->max:

ve negatif olmama durumu x1>=0, x2>=0,…,Xn>=0

Her bir ürün türü için kaynak tüketiminin mevcut rezervleri aşmaması koşuluyla, ürün satışlarından elde edilen kârın (gelirin) maksimum olacağı bir X=(x1,x2,…,Xn) üretim planı hazırlayın.

GörevII(çift)

Z=b1y1+b2y2+…+BmYm->dak

kısıtlamalarla:

ve olumsuz olmama durumu

y1>=0, y2>=0,…,yn>=0.

Her bir ürün tipinin üretimindeki kaynak maliyetlerinin eşit olması koşuluyla, kaynakların toplam maliyetinin minimum olacağı Y=(y1,y2,…,yn) kaynaklarının fiyatlarını (tahminlerini) bulun. bu ürünlerin satışından elde edilen kardan (gelirden) az olmamak üzere

Yukarıdaki modelde bi(i=1,2,…,m) Si kaynak rezervini belirtir; aij- bir birim çıktının üretiminde tüketilen Si kaynağının sayısı Pj(j=1,2,…,n); cj- Bir birim üretim Pj'nin (veya ürün fiyatı Pj) satışından elde edilen kâr (gelir) .

Bazı kuruluşların işletmenin S1, S2,..., Sm kaynaklarını satın almaya karar verdiğini ve bu kaynaklar için y1, y2,..., ym için optimal fiyatların belirlenmesinin gerekli olduğunu varsayalım. Açıkçası, satın alma organizasyonu tüm Z kaynaklarına b1,b2,…,bm miktarlarında harcama yapmakla ilgileniyor sırasıyla y1,y2,…,ym fiyatlarında minimum düzeydeydi, yani. Z=b1,y1+b2y2+…+bmym->min.

Öte yandan, kaynak satan bir işletme, elde edilen gelirin, işletmenin kaynakları bitmiş ürünlere dönüştürürken alabileceği miktardan daha az olmamasını sağlamakla ilgilenmektedir.

Bir birim P1 ürünü üretmek için, a11 birim S1 kaynağı, a21 birim S2 kaynağı,...., aj1 birim Si1 kaynağı,......, am1 birim Sm kaynağı y1 fiyatıyla tüketilir. ,y1,...,yi,...,ym, sırasıyla. Bu nedenle, satıcının gereksinimlerini karşılamak için, bir birim P1 ürününün üretiminde tüketilen kaynakların maliyeti, c1 fiyatından az olmamalıdır, yani. a11y1+a21y2+…+am1ym>=c1.

Benzer şekilde, her P1, P2,…Pn ürün türü için eşitsizlikler şeklinde kısıtlamalar oluşturabilirsiniz. Bu şekilde elde edilen ikili problem II'nin ekonomik-matematiksel modeli ve anlamlı yorumu tablonun sağ tarafında verilmektedir.

Kaynak fiyatları y1,y1,…,yi,…,ym ekonomi literatüründe çeşitli isimler almıştır: muhasebe, örtülü, gölge . Bu isimlerin anlamı şudur: koşullu , "sahte" fiyatlar. Kural olarak üretimin başlamasından önce bilinen ürünler için c1,c2,…,cn “dış” fiyatlarının aksine, kaynak fiyatları y1,y2,…,ym öyle dahili , çünkü dışarıdan verilmezler, doğrudan problemin çözülmesi sonucunda belirlenirler, bu yüzden daha çok adlandırılırlar. tahminler kaynaklar.

10. Karşılıklı dual DP problemleri ve özellikleri

Ekonomik ve matematiksel modellerinde yer alan parametrelerin anlamlı yorumlarından soyutlayarak tabloda sunulan iki doğrusal programlama problemi I ve II'yi resmi olarak ele alalım.

Her iki görev de aşağıdakilere sahiptir özellikler:

1. Problemlerden birinde doğrusal bir fonksiyonun maksimumu, diğerinde ise minimumu aranır.

2. Bir problemin doğrusal fonksiyonundaki değişkenlerin katsayıları, diğerindeki kısıtlamalar sisteminin serbest üyeleridir.

3.Problemlerin her biri standart formda verilmiştir ve maksimizasyon probleminde formdaki tüm eşitsizlikler "<=", а в задаче минимизации – все неравенства вида ">=".

4. Her iki problemin kısıt sistemlerindeki değişkenlere ait katsayı matrisleri birbirine aktarılır.

5. Bir problemin kısıtlar sistemindeki eşitsizliklerin sayısı, başka bir problemdeki değişkenlerin sayısıyla örtüşmektedir.

6. Her iki problemde de değişkenlerin negatif olmama koşulları korunmuştur.

Yorum. Orijinal problemin j'inci değişkenine negatif olmama koşulu uygulanırsa ikili problemin j'inci kısıtı bir eşitsizlik olacaktır, ancak j'inci değişken hem pozitif hem de negatif değerler alabiliyorsa o zaman ikili problemin j'inci kısıtı bir denklem olacaktır; Orijinal problemin kısıtlamaları ve ikilinin değişkenleri benzer şekilde ilişkilidir.

Belirtilen özelliklere sahip iki doğrusal programlama problemi I ve II'ye simetrik ikili problemler denir. Aşağıda basitlik açısından bunları basitçe adlandıracağız. ikili görevler.

Her DP problemi kendi ikili göreviyle ilişkilendirilebilir.

11. İkili problem oluşturma algoritması:

1. Orijinal problemin kısıtlama sistemindeki tüm eşitsizlikleri tek bir anlama indirgeyin: orijinal problemde maksimum doğrusal fonksiyonu arıyorlarsa, o zaman kısıtlama sisteminin tüm eşitsizliklerini forma indirin "<=", а если минимум – к виду ">=". Bu şartın sağlanmadığı eşitsizlikler için –1 ile çarpın.

2. Değişkenler için bir katsayılar matrisi, kısıtlamalar sisteminin serbest terimlerinin bir sütunu ve doğrusal bir fonksiyondaki değişkenler için bir dizi katsayı içeren A sisteminin genişletilmiş bir matrisini oluşturun.

3. A matrisine aktarılan matrisi bulun .

4. Ortaya çıkan matrise dayanarak ikili bir problem formüle edin ve değişkenlerin negatif olmama koşulları: orijinal problemin kısıtlamalar sisteminin serbest üyelerini değişkenler için katsayılar olarak alarak ikili problemin amaç fonksiyonunu oluştururlar; matris elemanlarını değişkenler için katsayılar olarak ve orijinal problemin amaç fonksiyonundaki değişkenler için katsayıları serbest terimler olarak alarak ikili problem için bir kısıtlama sistemi oluşturun ve zıt anlamdaki eşitsizlikleri yazın; Dual problemin değişkenlerinin negatif olmama koşulunu yazınız.

12. Birinci dualite teoremi

Dual problemlerin optimal çözümleri arasındaki bağlantı dualite teoremleri kullanılarak kurulur.

Yeterli bir optimallik işareti.

Eğer X*=(x1*,x2*,…,xn*) Ve Y*=(y1*,y2*,…,ym*) - eşitliğin geçerli olduğu karşılıklı ikili sorunların kabul edilebilir çözümleri,

o zaman orijinal problem I'in ve ikili problem II'nin en iyi çözümüdür.

Karşılıklı ikili problemlerin optimalliklerinin yeterli işaretine ek olarak, bunların çözümleri arasında başka önemli ilişkiler de vardır. Her şeyden önce şu sorular ortaya çıkıyor: her ikili problem çifti için her zaman aynı anda en uygun çözümler var mıdır; İkili sorunlardan birinin çözümü varken diğerinin olmaması mümkün mü? Bu soruların cevabı aşağıdaki teorem ile verilmektedir.

İlk (ana) dualite teoremi. Karşılıklı ikili problemlerden birinin optimal çözümü varsa, diğeri de buna sahiptir ve doğrusal fonksiyonlarının optimal değerleri eşittir:

Fmaks = Zmin veya F(X*)=Z(Y*) .

Problemlerden birinin doğrusal fonksiyonu sınırlı değilse diğer problemin koşulları çelişkilidir (problemin çözümü yoktur).

Yorum. Ana dualite teoreminin ikinci kısmının tersi olan ifade genel durumda doğru değildir; Orijinal problemin koşullarının çelişkili olması, ikili problemin doğrusal fonksiyonunun sınırsız olduğu anlamına gelmez.

Birinci dualite teoreminin ekonomik anlamı.

Üretim planı X*=(x1*,x2*,…,xn*) ve kaynakların fiyatları (tahminleri) kümesi Y*=(y1*,y2*,…,ym*) ancak ve ancak “dış” (önceden bilinen) c1, c2,…, cn fiyatlarında bulunan ürünlerden elde edilen kar (gelir), “iç” (yalnızca belirlenen) kaynak maliyetlerine eşitse optimal olur. problemin çözümünden) fiyatlar y1 ,y2,…,ym. Diğer tüm planlar için X Ve e Her iki problemde de ürünlerden elde edilen kar (gelir), her zaman kaynak maliyetlerinden azdır (veya ona eşittir).

Birinci dualite teoreminin ekonomik anlamı şu şekilde yorumlanabilir: İşletme, ürünleri X*=(x1*,x2*,…,xn*) optimal planına göre üretip üretmeyeceği ve maksimum kar (gelir) Fmax elde edip etmeyeceği konusunda kayıtsızdır. veya kaynakları en uygun fiyatlarla satmak Y* =(y1*,y2*,…,ym*) ve satıştan kaynak Zmin'in minimum maliyetini geri ödeyin.

13. İkinci dualite teoremi

Karşılıklı olarak ikili iki problem verilsin. Bu problemlerin her biri simpleks yöntemi kullanılarak çözülürse, o zaman onları Kanonik forma getirmek gerekir, bunun için Problem I'in kısıtlama sistemine dahil edilmesi gerekir (kısa gösterimle) T negatif olmayan değişkenler ve Problem II'nin kısıtlamaları sistemine () – N negatif olmayan değişkenler; burada i(j), ek değişkenin dahil edildiği eşitsizliğin sayısıdır.

Karşılıklı ikili problemlerin her biri için kısıtlama sistemleri şu şekli alacaktır:

İkili problemlerden birinin başlangıç ​​değişkenleri ile diğer problemin (tablo) ek değişkenleri arasında bir yazışma kuralım.

Teorem. Karşılıklı ikili problemlerden birinin optimal çözümünün pozitif (sıfır olmayan) bileşenleri, diğer problemin optimal çözümünün sıfır bileşenlerine karşılık gelir; herhangi bir i=1,2,…,m u j=1,2,…,n için: eğer X*j>0 ise; Eğer , o zaman ve benzer şekilde,

eğer öyleyse ; eğer öyleyse.

Bu teoremden önemli bir sonuç çıkar: Optimuma ulaşıldığında (yani her problemin simpleks yöntemini kullanarak çözülmesinin son adımında) karşılıklı ikili problemlerin değişkenleri arasında ortaya çıkan yazışmalar arasındaki yazışmayı temsil eder. ana(kural olarak sıfıra eşit değildir) ikili problemlerden birinin değişkenleri ve çekirdek olmayan Uygun temel çözümleri oluşturduklarında başka bir problemin (sıfıra eşit) değişkenleri.

İkinci dualite teoremi. İkili problemin optimal çözümünün bileşenleri, orijinal problemin doğrusal fonksiyonunun karşılık gelen değişkenleri için, optimal çözümünün temel olmayan değişkenleri aracılığıyla ifade edilen katsayıların mutlak değerlerine eşittir.

Yorum. Karşılıklı ikili problemlerden birinde optimal çözümün benzersizliği ihlal edilirse, ikili problemin optimal çözümü dejenere olur. Bunun nedeni, orijinal problemin optimal çözümünün benzersizliğinin ihlal edilmesi durumunda, optimal çözümünün doğrusal fonksiyonunun temel olmayan değişkenler cinsinden ifadesinde ana değişkenlerden en az birinin eksik olmasıdır.

14. Objektif olarak belirlenen değerlendirmeler ve anlamları

İkili problemin optimal çözümünün bileşenlerine orijinal problemin optimal (ikili) tahminleri denir. Akademisyen L.V. Kantorovich onları aradı objektif olarak belirlenmiş" tahminler ( literatürde bunlara gizli gelir de denir) .

Orijinal problem I'in S1, S2, S3, S4 kaynaklarının bi rezervleri arasındaki farkı temsil eden ek değişkenleri ve bunların tüketimi, ifade kalan kaynaklar , ve bunlardan bir birim çıktı üretmek için kaynakların maliyetleri ile P1, P2 ürünlerinin cj fiyatları arasındaki farkı temsil eden ikili problem II'nin ek değişkenleri , ifade etmek maliyetlerin fiyattan fazla olması.

Böylece, kaynakların nesnel olarak belirlenmiş değerlendirmeleri, kaynakların kıtlık derecesini belirler: optimal üretim planına göre, kıt (yani tamamen kullanılmış) kaynaklar sıfır olmayan değerlendirmeler alır ve kıt olmayan kaynaklar sıfır değerlendirme alır. y*i değeri, i. kaynağın bir değerlendirmesidir. Y*i tahmininin değeri ne kadar yüksek olursa, kaynağın kıtlığı da o kadar yüksek olur. Kıt olmayan bir kaynak için y*i=0.

Dolayısıyla, optimum üretim planına yalnızca karlı, kârlı olmayan ürün türleri dahil edilebilir (ancak buradaki karlılık kriteri benzersizdir: ürünün fiyatı, üretiminde tüketilen kaynakların maliyetini aşmaz, ancak tam olarak onlara eşit).

Üçüncü dualite teoremi . İkili problemin optimal çözümünün bileşenleri, doğrusal fonksiyonun kısmi türevlerinin değerlerine eşittir Fmaks(B1, B2,…, BM)karşılık gelen argümanlara göre, yani.

Nesnel olarak belirlenen kaynak tahminleri, ilgili kaynağın stoğu bir birim değiştiğinde ürün satışlarından elde edilecek maksimum kârın (gelirin) kaç parasal birim değişeceğini gösterir.

İkili değerlendirmeler, sürekli değişen üretim koşullarında analiz yapmak ve doğru kararları vermek için bir araç görevi görebilir. Örneğin, objektif olarak belirlenmiş kaynak tahminlerinin yardımıyla, optimum koşullu maliyetleri ve üretim sonuçlarını karşılaştırmak mümkündür.

Kaynakların nesnel olarak belirlenmiş tahminleri, kaynaklardaki herhangi bir değişikliğin değil, yalnızca nispeten küçük değişikliklerin etkisini değerlendirmemize olanak tanır. Ani değişikliklerle tahminlerin kendisi farklılaşabilir ve bu da bunların üretim verimliliğini analiz etmede kullanılmasını imkansız hale getirir. Nesnel olarak belirlenen değerlendirmelerin oranlarına dayanarak, ikili değerlendirmelerin istikrar sınırları dahilinde gerçekleştirilen değişikliklerin optimal planın etkinliğini etkilememesine bağlı olarak hesaplanan kaynak ikame edilebilirliği normları belirlenebilir. Çözüm.İkili tahminler şunlardır:

1. Kaynak ve ürün kıtlığının göstergesi.

2. Kısıtlamaların amaç fonksiyonunun değeri üzerindeki etkisinin bir göstergesi.

3. Optimumluk kriteri açısından belirli ürün türlerinin üretim verimliliğinin bir göstergesi.

4. Toplam koşullu maliyetleri ve sonuçları karşılaştırmak için bir araç.

15. Maliyet kriterine göre ulaşım sorununun ifade edilmesi.

Homojen veya değiştirilebilir bir ürünün üretim noktasından (kalkış istasyonları) tüketim noktalarına (varış istasyonları) taşınması için en ekonomik plan sorunu olan TK, geniş pratik uygulamalara sahip olan LP'nin en önemli özel sorunudur. sadece ulaşım sorunları için değil.

Teknik spesifikasyon, LP'de ekonomik özelliklerinin kesinliği, matematiksel modelin özellikleri ve özel çözüm yöntemlerinin varlığı ile ayırt edilir.

Teknik şartnamelerin maliyet kriterine göre en basit formülasyonu şu şekildedir: T A1,…,Am kalkış noktalarında sırasıyla teslim edilmesi gereken homojen kargo (kaynaklar) a1,…,am birimleri var N tüketiciler B1,…,Bn b1,…,bn birim miktarlarında (ihtiyaçlar). Bir kargo biriminin i'inci kalkış noktasından j'inci tüketim noktasına taşınmasının Cij nakliye maliyetleri bilinmektedir.

Taşıma planının yapılması, yani ihtiyaçların tam olarak karşılanması ve toplam taşımanın sağlanması için i'inci kalkış noktasından j'inci tüketim noktasına kadar kaç adet kargo gönderilmesi gerektiğinin bulunması gerekmektedir. maliyetler minimum düzeydedir.

Açıklık sağlamak için, teknik şartnamenin koşullarını, adı verilen bir tablo şeklinde sunuyoruz. dağıtım .

Sağlayıcı	Tüketici			Kargo stoğu
İhtiyaç

Burada i'inci hareket noktasından j'inci varış noktasına taşınan kargo miktarı xij'ye eşit olup, i'inci hareket noktasındaki kargo stoğu ai>=0 değeri ile belirlenir ve j'inci varış noktasında kargo ihtiyacı bj>=0'dır. Tüm xij>=0 olduğu varsayılmaktadır.

Matris denir tarife matrisi (maliyetler veya nakliye masrafları).

Taşıma görev planı matris olarak adlandırılır; burada her xij sayısı, i'inci kalkış noktasından j'inci varış noktasına teslim edilmesi gereken kargo birimi sayısını belirtir. xij matrisi denir ulaşım matrisi.

Ulaştırma planının uygulanmasıyla ilgili toplam toplam maliyetler, amaç fonksiyonu ile temsil edilebilir.

Değişkenler xij stoklar, tüketiciler ve negatif olmama koşulları üzerindeki kısıtlamaları karşılamalıdır:

– rezervlere ilişkin kısıtlamalar (2);

– tüketicilere yönelik kısıtlamalar (2);

– olumsuz olmayan koşullar (3).

Böylece matematiksel olarak taşıma problemi aşağıdaki gibi formüle edilir. Koşul (3) altındaki kısıtlama sistemi (2) ve amaç fonksiyonu (1) verilmiştir. (2) sisteminin çözüm kümesinden, (1) fonksiyonunu minimuma indiren, negatif olmayan bir çözümün bulunması gerekmektedir.

Problem (1) – (3)'ün kısıt sistemi, m+n denklem içerir. TN değişkenler. Toplam rezervlerin toplam ihtiyaçlara eşit olduğu varsayılmaktadır;

16. Ulaştırma sorununun çözülebilirliğine dair işaret

Bir ulaştırma sorununun kabul edilebilir planlara sahip olabilmesi için eşitliğin sağlanması gerekli ve yeterlidir.

İki tür ulaşım sorunu vardır: kapalı , Tedarikçilerin toplam kargo hacminin tüketicilerin toplam talebine eşit olduğu ve açık , Tedarikçilerin toplam üretim kapasitesinin tüketici talebini aştığı veya tüketici talebinin tedarikçilerin fiili toplam kapasitesinden daha büyük olduğu durumlar;

Açık bir model kapalı bir modele dönüştürülebilir. Dolayısıyla, eğer ulaştırma probleminin matematiksel modeline hayali (n+1). varış noktası dahil edilirse. Bu amaçla, görev matrisinde talebin tedarikçilerin toplam kapasitesi ile tüketicilerin fiili talebi arasındaki farka eşit olduğu ek bir sütun sağlanmıştır:

Bu noktaya kadar kargo teslimatına ilişkin tüm tarifeler sıfıra eşit sayılacaktır. Bu, problemin açık modelini kapalı bir modele dönüştürür. Yeni bir problem için, ek taşıma fiyatları sıfıra eşit olduğundan amaç fonksiyonu her zaman aynıdır. Başka bir deyişle, hayali tüketici, kısıtlamalar sisteminin uyumluluğunu ihlal etmemektedir.

Eğer o zaman, eşit bir kargo stokunun atandığı hayali (m+1)'inci bir hareket noktası eklenirse.

Bu hayali tedarikçiden mal teslimine ilişkin tarifeler yeniden sıfıra ayarlandı. Matrise bir satır eklenecek, bu amaç fonksiyonunu etkilemeyecek ve problemin kısıtları sistemi birleşik hale gelecek, yani en uygun planı bulmak mümkün hale gelecektir.

Taşıma problemi için aşağıdaki teorem önemlidir.

Teorem. Taşıma problemi matrisinin sırası denklem sayısından bir eksiktir, yani. R ( A )= M + N -1.

Teoremden her referans tasarımının sıfıra eşit (m-1)(n-1) serbest değişkene ve m+n-1 temel değişkene sahip olması gerektiği sonucu çıkar.

Taşıma görevinin taşıma planını doğrudan dağıtım tablosunda arayacağız. xij değişkeni bir değer alırsa bu değeri karşılık gelen (I,j) hücresine yazacağımızı, ancak xij=0 ise (I,j) hücresini boş bırakacağımızı varsayalım. Dağıtım tablosundaki matrisin sırasına ilişkin teoremi dikkate alarak referans planı şunları içermelidir: m+n-1 işgal edilmiş hücreler ve geri kalanı ücretsiz olacak.

Referans planı için belirtilen gereksinimler yalnızca bunlarla sınırlı değildir. Referans planlarının döngülerle ilgili başka bir gereksinimi karşılaması gerekir.

İki ve yalnızca iki bitişik hücrenin bir satırda veya bir sütunda yer aldığı ve kümenin son hücresinin, ilk hücreyle aynı satır veya sütunda yer aldığı bir taşıma matrisinin hücreleri kümesine kapalı denir. döngü .

Grafiksel olarak bir döngü, köşeleri tablonun dolu hücrelerinde bulunan ve bağlantılar yalnızca satırlarda veya sütunlarda bulunan kapalı bir kesik çizgidir. Dahası, döngünün her köşesinde biri satırda, diğeri sütunda olmak üzere tam olarak iki bağlantı vardır. Bir döngü oluşturan kesikli bir çizgi kendisiyle kesişiyorsa, o zaman kendi kendine kesişen noktalar köşe değildir.

Taşıma problemi planlarının aşağıdaki önemli özellikleri bir dizi döngü hücresi ile ilişkilidir:

1) bir taşıma sorunu için kabul edilebilir bir plan, ancak ve ancak bu plan tarafından işgal edilen hücrelerden hiçbir döngü oluşturulamıyorsa referans plandır;

2) eğer bir referans planımız varsa, o zaman her serbest hücre için, bu hücreyi ve işgal edilen hücrelerin bir kısmını içeren yalnızca bir döngü oluşturulabilir.

17. Başlangıç ​​referans planının oluşturulması

"Kuzeybatı köşesi" kuralı.

İlk ulaşım planını hazırlamak için aşağıdaki “kuzeybatı köşesi” kuralını kullanmak uygundur.

Geleneksel olarak "kuzeybatı köşesi" olarak adlandırılan sol üst köşeden başlayarak, çizgi boyunca sağa veya sütunun altına doğru ilerleyerek dolduracağız. (1; 1) hücresine a1 ve b1 sayılarından küçük olanı koyalım, yani . Eğer öyleyse, ilk sütun “kapalı” ise, yani. ilk tüketicinin talebi tamamen karşılanmıştır. Bu, ilk sütunun diğer tüm hücreleri için kargo miktarının .

Eğer öyleyse, o zaman ilk satır da benzer şekilde "kapalı", yani . İçine girdiğimiz bitişik hücreyi (2; 1) doldurmaya devam ediyoruz.

İkinci hücreyi (1; 2) veya (2; 1) doldurduktan sonra, ikinci satır veya ikinci sütundaki sonraki üçüncü hücreyi doldurmaya devam ediyoruz. Bir aşamada kaynaklar ve ihtiyaçlar tükenene kadar bu süreci sürdüreceğiz. Son doldurulan hücre, son n'inci sütunda ve son m'inci satırda olacaktır.

"Minimum eleman" kuralı.

“Kuzeybatı köşesi” kuralına göre inşa edilen ilk referans planı, genellikle optimal olmaktan çok uzaktır, çünkü belirlenmesi cij maliyet değerlerini hesaba katmaz. Bu nedenle, daha ileri hesaplamalar, optimum plana ulaşmak için birçok yineleme gerektirecektir. Başlangıç ​​planının “minimum unsur” kuralına göre oluşturulması durumunda yineleme sayısı azaltılabilir. Bunun özü, her adımda yükün bir kafese mümkün olan maksimum “hareketinin” minimum tarife cij ile gerçekleştirilmesi gerçeğinde yatmaktadır. Tabloyu doldurmaya tarife matrisinin en küçük cij elemanına karşılık gelen hücreden başlıyoruz. ai veya bj sayılarından küçük olanı en düşük tarifeli hücreye yerleştirilir . Daha sonra stoğu tamamen tükenen tedarikçiye karşılık gelen satır veya talebi tamamen karşılanan müşteriye karşılık gelen sütun değerlendirme dışı bırakılır. Tedarikçinin stokunun tamamen tükenmiş olması ve müşterinin talebinin tamamen karşılanması durumunda, bir satırın ve bir sütunun aynı anda ortadan kaldırılması gerekli olabilir. Daha sonra tablonun geri kalan hücrelerinden yine en düşük tarifeye sahip hücre seçilir ve stokların dağıtım işlemi hepsi dağıtılıp talep karşılanıncaya kadar devam eder.

18. Potansiyeller yöntemi

Potansiyel yöntemini kullanarak bir ulaştırma problemi için en uygun planı belirlemenin genel ilkesi, simpleks yöntemini kullanarak bir DP problemini çözme ilkesine benzer, yani: önce bir ulaştırma problemi için bir referans planı bulunur ve daha sonra başarılı bir şekilde planlanır. Optimal bir plan elde edilene kadar iyileştirmeler yapılır.

Potansiyel yöntemin özü aşağıdaki gibidir. Başlangıç ​​referans ulaşım planı bulunduktan sonra, her tedarikçiye (her satıra) tedarikçi potansiyeli Ai adı verilen belirli bir sayı atanır ve her tüketiciye (her sütuna) tüketici potansiyeli adı verilen belirli bir sayı atanır.

Bir ton yükün bir noktadaki maliyeti, bir ton yükün taşıma öncesi maliyeti + taşıma maliyetine eşittir: .

Potansiyel yöntemi kullanarak bir taşıma problemini çözmek için şunları yapmanız gerekir:

1. Belirtilen kurallardan birine göre temel bir ulaşım planı oluşturun. Doldurulan hücre sayısı m+n-1 olmalıdır.

2. Potansiyelleri ve buna bağlı olarak tedarikçileri ve tüketicileri (işgal edilen hücreler için) hesaplayın: . Dolu hücre sayısı m+n-1, denklem sayısı ise m+n'dir. Çünkü Denklem sayısı bilinmeyen sayısından bir eksikse, bilinmeyenlerden birinin serbest olduğu ve herhangi bir sayısal değer alabileceği ortaya çıkar. Örneğin, . Belirli bir referans çözümü için kalan potansiyeller benzersiz bir şekilde belirlenecektir.

3. Optimumluğu kontrol edin, yani. serbest hücreler için tahminleri hesaplayın. Eğer öyleyse, ulaşım uygunsa ve X planı optimalse, bu bir optimallik işaretidir. En az bir fark varsa yeni bir referans planına geçin. Ekonomik anlamda değer, i. tedarikçinin j. tüketiciye tek bir teslimatı nedeniyle toplam taşıma maliyetlerinde meydana gelecek değişimi karakterize eder. Eğer öyleyse, o zaman tek bir teslimat nakliye maliyetlerinde tasarrufa yol açacak, ancak eğer - bunlarda bir artışa yol açacaksa. Sonuç olarak, serbest tedarik yönleri arasında nakliye maliyetlerinden tasarruf sağlayan yönler yoksa, ortaya çıkan plan optimaldir.

4. Pozitif sayılar arasından maksimum seçilir ve karşılık geldiği serbest hücre için yeniden hesaplama döngüsü oluşturulur. Seçilen serbest hücre için döngü oluşturulduktan sonra yeni bir referans planına geçmelisiniz. Bunu yapmak için, belirli bir serbest hücreye bağlı hücreler içindeki yüklerin bir yeniden hesaplama döngüsü ile taşınması gerekir.

a) Belirli bir serbest hücreye bir döngü ile bağlanan hücrelerin her birine belirli bir işaret atanır ve bu serbest hücreye “+” ve diğer tüm hücrelere (döngünün köşelerine) dönüşümlü olarak “-” ve “işaretleri atanır. +”. Bu hücrelere eksi ve artı diyeceğiz.

b) Döngünün negatif hücrelerinde, ile gösterdiğimiz minimum arzı buluruz. Eksi hücrelerde bulunan xij sayılarından küçük olanı bu serbest hücreye aktarılır. Aynı zamanda bu sayı “+” işaretli hücrelerde karşılık gelen sayılara eklenir ve eksi hücrelerdeki sayılardan çıkarılır. Daha önce serbest olan bir hücre işgal edilir ve destek düzlemine girer; ve xij sayılarının minimumunu içeren eksi hücresi serbest kabul edilir ve destek planından ayrılır.

Böylece yeni bir referans planı belirlendi. Yukarıda açıklanan bir referans planından diğerine geçişe, yeniden hesaplama döngüsündeki değişim denir. Yeniden hesaplama döngüsü boyunca kaydırıldığında, işgal edilen hücrelerin sayısı değişmeden kalır, yani m+n-1'e eşit kalır. Üstelik, negatif hücrelerde iki veya daha fazla aynı sayı xij varsa, o zaman bu hücrelerden yalnızca biri serbest bırakılır ve geri kalanı sıfır malzemeyle meşgul kalır.

5. Ortaya çıkan referans planı optimallik açısından kontrol edilir; 2. adımdan itibaren tüm adımları tekrarlayın.

19. Dinamik programlama kavramı.

DP (planlama), çok adımlı (çok aşamalı) problemlere en uygun çözümleri bulmaya yönelik matematiksel bir yöntemdir. Bu sorunlardan bazıları doğal olarak ayrı adımlara (aşamalara) bölünür, ancak DP yöntemiyle çözülebilmeleri için bölümün yapay olarak getirilmesi gereken sorunlar da vardır.

Tipik olarak DP yöntemleri, etkisi değerlendirilen bazı kontrollü sistemlerin çalışmasını optimize eder. katkı, veya çarpımsal, amaç fonksiyonu. Katkı Birkaç değişkenli f(x1,x2,…,xn) fonksiyonu çağrılır ve bu fonksiyonun değeri, yalnızca bir xj değişkenine bağlı olan bazı fj fonksiyonlarının toplamı olarak hesaplanır: . Toplamsal amaç fonksiyonunun koşulları, kontrollü sürecin bireysel aşamalarında alınan kararların etkisine karşılık gelir.

R. Bellman'ın optimallik ilkesi.

Dinamik programlamada uygulanan yaklaşımın anlamı, orijinal çok boyutlu problemin çözümünü daha düşük boyutlu bir dizi problemle değiştirmektir. Görevler için temel gereksinimler:

1. araştırmanın amacı şu olmalıdır: kontrollü sistem (nesne) verilen geçerli eyaletler ve kabul edilebilir bölümler;

2. Görev, her adımı kabulden oluşan çok adımlı bir süreç olarak yorumlamaya izin vermelidir. çözümlerÖ kabul edilebilir kontrollerden birinin seçilmesi durum değişikliği sistemler;

3. Görev, adım sayısına bağlı olmamalı ve her adımda tanımlanmalıdır;

4. Sistemin her adımdaki durumu aynı (bileşim açısından) parametreler dizisiyle tanımlanmalıdır;

5. Bir çözümü seçtikten sonra sistemin kendisini içinde bulduğu sonraki durum k-m adım, yalnızca verilen karara ve başlangıçtaki başlangıç ​​durumuna bağlıdır k- Adım. Bu özellik, dinamik programlama ideolojisi açısından temeldir ve denir. sonuç yok .

Dinamik programlama modelini genelleştirilmiş bir biçimde uygulama konularını ele alalım. Görevin farklı durumlarda olabilecek bazı soyut nesneleri kontrol etmek olmasına izin verin. Nesnenin mevcut durumu, ayrıca S ile gösterilecek ve çağrılacak olan belirli bir parametre seti ile tanımlanacaktır. durum vektörü. Tüm olası durumları içeren bir S kümesinin verildiği varsayılmaktadır. Nesne için tanımlanmış bir küme de vardır. kabul edilebilir kontroller(kontrol eylemleri) X, genelliği kaybetmeden sayısal bir küme olarak kabul edilebilir. Kontrol eylemleri zaman içinde farklı anlarda gerçekleştirilebilir ve yönetim çözüm kontrollerden birini seçmekten ibarettir. Plan görevler veya Yönetim stratejisi bileşenleri sürecin her adımında seçilen kontroller olan x=(x1,x2,…,xn-1) vektörü olarak adlandırılır. Beklenenler göz önüne alındığında sonradan etki yok Sk ve Sk+1 nesnesinin her iki ardışık durumu arasında, seçilen kontrolü de içeren bilinen bir işlevsel ilişki vardır: . Böylece nesnenin başlangıç ​​durumunun belirlenmesi ve bir plan seçilmesi X açıkça tanımlamak davranış yörüngesi nesne.

Verimliliği her adımda kontrol edin k mevcut Sk durumuna, seçilen kontrol xk'ye bağlıdır ve fk(xk,Sk) fonksiyonları kullanılarak ölçülür. toplamsal amaç fonksiyonu , Tesis yönetiminin genel verimliliğini karakterize eder. ( Not , fk(xk,Sk) fonksiyonunun tanımının izin verilen değerler aralığını içerdiği xk , ve bu alan kural olarak Sk'nin mevcut durumuna bağlıdır). Optimum kontrol , belirli bir S1 başlangıç ​​durumu için böyle bir optimal planın seçilmesine gelir x* , hangi noktada elde edilir en yüksek miktar karşılık gelen yörüngedeki fk değerleri.

Dinamik programlamanın temel ilkesi, her adımda fk(xk,Sk) fonksiyonunun yalıtılmış optimizasyonu için çabalamamak, ancak sonraki tüm adımların optimal olduğu varsayımı altında optimal kontrol x*k'yi seçmektir. Resmi olarak bu prensip her adımda bulunarak uygulanır. k koşullu optimal kontroller , mevcut durumun S olduğunu varsayarak bu adımdan başlayarak en büyük toplam verimliliği sağlar.

Zk(s), fk fonksiyonlarının toplamının maksimum değerini göstersin itibaren tüm adımlar boyunca könce P(sürecin belirli bir bölümünde optimum kontrol ile elde edilir), nesnenin adımın başında olması koşuluyla k S durumundadır. O halde Zk(s) fonksiyonları yineleme ilişkisini sağlamalıdır:

Bu orana denir temel yineleme ilişkisi (temel fonksiyonel denklem) dinamik program. Olarak da bilinen dinamik programlamanın temel ilkesini uygular. Bellman optimallik ilkesi :

Optimum kontrol stratejisi aşağıdaki koşulu karşılamalıdır: başlangıç ​​durumu ne olursa olsun Sk k. adımda ve bu adımda seçilen kontrol xk, sonraki yönetim (yönetim kararları) aşağıdakilerle ilgili olarak optimal olmalıdır: kokmo Ianiya ,k adımında verilen karardan kaynaklanan .

Ana ilişki Zk(s) fonksiyonlarını bulmamızı sağlar. sadece V ile kombine başlangıç ​​koşulu, bizim durumumuzda hangisi eşitliktir.

Yukarıda formüle edilen optimallik ilkesi, yalnızca optimal kontrolün seçiminin kontrollü sürecin arka planına, yani sistemin mevcut durumuna nasıl geldiğine bağlı olmadığı nesnelerin kontrolüne uygulanabilir. Sorunu ayrıştırmamıza ve pratik çözümünü mümkün kılmamıza olanak sağlayan da bu durumdur.

Her özel görev için, fonksiyonel denklemin kendine özgü bir formu vardır, ancak (*) ifadesinin doğasında bulunan ve optimallik ilkesinin temel fikrini somutlaştıran yinelenen doğayı kesinlikle korumalıdır.

20. Oyun modelleri kavramı.

Bir çatışma durumunun matematiksel modeline denir oyun , çatışmaya katılan taraflar - oyuncular, ve çatışmanın sonucu kazanç.

Her resmileştirilmiş oyun için, tüzük , onlar. şunları belirleyen bir koşullar sistemi: 1) oyuncuların eylemlerine ilişkin seçenekler; 2) her oyuncunun partnerlerinin davranışları hakkında sahip olduğu bilgi miktarı; 3) her bir eylem dizisinin yol açtığı kazanç. Tipik olarak kazanma (veya kaybetme) ölçülebilir; örneğin, mağlubiyeti sıfır, galibiyeti bir ve beraberliği 1/2 olarak değerlendirebilirsiniz. Bir oyunun sonuçlarının ölçülmesine ne ad verilir? ödeme .

Oyunun adı buhar odası , iki oyuncuyu içeriyorsa ve çoklu , Oyuncu sayısı ikiden fazla ise. Sadece çiftli oyunları değerlendireceğiz. İki oyuncuyu içeriyorlar A Ve İÇİNDE,çıkarları zıt olan ve oyun derken, bir dizi eylemi kastediyoruz. A Ve İÇİNDE.

Oyunun adı sıfır toplamlı oyun veya düşmanca gökyüzü , oyunculardan birinin kazancı diğerinin kaybına eşitse; her iki tarafın kazancının toplamı sıfırdır. Oyun görevini tamamlamak için bunlardan birinin değerini belirtmeniz yeterlidir. . Eğer belirlersek A– oyunculardan birinin kazancı, B – diğerinin kazancı, ardından sıfır toplamlı bir oyun için b = –A, bu nedenle örneğin dikkate alınması yeterlidir A.

Kuralların öngördüğü eylemlerden birinin seçimi ve uygulanmasına denir. ilerlemek oyuncu. Hareketler olabilir kişisel Ve rastgele . Kişisel hareket – bu, oyuncunun olası eylemlerden birinin (örneğin satranç oyunundaki bir hamle) bilinçli bir seçimidir. Her kişisel hamle için olası seçenekler oyunun kurallarına göre düzenlenir ve her iki tarafın önceki hamlelerinin toplamına bağlıdır.

Rastgele hareket – rastgele seçilen bir eylemdir (örneğin, karıştırılmış bir desteden bir kart seçmek). Bir oyunun matematiksel olarak tanımlanabilmesi için, oyunun kurallarının her rastgele hamleyi belirtmesi gerekir. olasılık dağılımı Olası sonuçlar.

Bazı oyunlar yalnızca rastgele hamlelerden (saf kumar olarak adlandırılan) veya yalnızca kişisel hamlelerden (satranç, dama) oluşabilir. Kart oyunlarının çoğu karma türdeki oyunlara aittir, yani hem rastgele hem de kişisel hamleler içerirler. İlerleyen süreçte oyuncuların sadece kişisel hamlelerini ele alacağız.

Oyunlar yalnızca hamlelerin niteliğine (kişisel, rastgele) göre değil, aynı zamanda her oyuncunun diğerinin eylemlerine ilişkin olarak kullanabileceği bilgilerin niteliğine ve miktarına göre de sınıflandırılır. Özel bir oyun sınıfı, "tam bilgi içeren oyunlar" olarak adlandırılanlardır. Tam bilgi içeren bir oyun her oyuncunun, her kişisel hamleyle, hem kişisel hem de rastgele önceki tüm hamlelerin sonuçlarını bildiği bir oyundur. Eksiksiz bilgi içeren oyunlara örnek olarak satranç, dama ve iyi bilinen “tic-tac-toe” oyunu verilebilir. Pratik öneme sahip oyunların çoğu, tam bilgi içeren oyunlar sınıfına ait değildir, çünkü düşmanın eylemlerine ilişkin belirsizlik genellikle çatışma durumlarının temel bir unsurudur.

Oyun teorisinin temel kavramlarından biri kavramdır. stratejiler .

Strateji Oyuncu, mevcut duruma bağlı olarak her kişisel hamlede yapacağı eylemin seçimini belirleyen bir kurallar dizisidir. Genellikle oyun sırasında, oyuncu her kişisel hamlede özel duruma göre bir seçim yapar. Ancak prensipte tüm kararların oyuncu tarafından önceden verilmesi (herhangi bir duruma tepki olarak) mümkündür. Bu, oyuncunun bir kurallar listesi veya program olarak belirtilebilecek belirli bir stratejiyi seçtiği anlamına gelir. (Bu şekilde oyunu bilgisayar kullanarak oynayabilirsiniz.) Oyunun adı nihai , Her oyuncunun sınırlı sayıda stratejisi varsa ve sonsuz .– aksi takdirde.

İçin karar vermek oyun , veya bul oyun çözümü , her oyuncu için koşulu karşılayan bir strateji seçmeliyiz optimallik , onlar. oyunculardan birinin alması gerekir maksimum kazanç, ikincisi stratejisine sadık kaldığında, aynı zamanda ikinci oyuncunun da sahip olması gerekir minimum kayıp , eğer ilki stratejisine sadık kalırsa. Bu tür stratejilere denir en uygun . Optimal stratejiler aynı zamanda koşulu da karşılamalıdır Sürdürülebilirlik , onlar. Bu oyunda her iki oyuncunun da stratejisinden vazgeçmesi dezavantajlı olmalıdır.

Eğer oyun birkaç kez tekrarlanırsa, oyuncular her bir oyunda kazanmak ve kaybetmekle ilgilenmeyebilirler, ancak A ortalama kazanç (mağlubiyet) tüm partilerde.

Oyun teorisinin amacı her oyuncu için en uygun stratejiyi belirlemektir.

21. Ödeme matrisi. Oyunun alt ve üst fiyatı

Oyuncunun oynadığı nihai oyun A Var T stratejiler ve oyuncu V-p stratejilere m×n oyun denir.

m×n sayıda iki oyuncudan oluşan bir oyun düşünün A Ve İÇİNDE(“biz” ve “düşman”).

Oyuncuya izin ver A sahip olmak T A1,A2,…,Am olarak adlandırdığımız kişisel stratejiler. Oyuncuya izin ver İÇİNDE mevcut N kişisel stratejiler, bunları B1,B2,…,Bn olarak gösterelim.

Her iki tarafın da belirli bir strateji seçmesine izin verin; bizim için Ai, düşman için Bj olacak. Oyuncuların Ai ve Bj () stratejilerinden herhangi birini seçmesi sonucunda oyunun sonucu benzersiz bir şekilde belirlenir; oyuncunun kazancı aij A(pozitif veya negatif) ve oyuncunun kaybı (-aij) İÇİNDE.

Herhangi bir strateji çifti (Ai,Bj) için aij değerlerinin bilindiğini varsayalım. . Matris P=aij , unsurları Ai ve Bj stratejilerine karşılık gelen getiriler olan, isminde ödeme matrisi veya Oyunun matrisi. Bu matrisin satırları oyuncunun stratejilerine karşılık gelir A, ve sütunlar – oyuncunun stratejileri B. Bu stratejilere saf denir.

m×n oyununun matrisi şu şekildedir:

Matrisli bir m×n oyun düşünün ve A1,A2,…,Am stratejileri arasından en iyisini belirleyin . Strateji seçimi AI oyuncusu A oyuncunun bunu beklemesi gerekir İÇİNDE buna oyuncunun kazandığı Bj stratejilerinden biriyle cevap verecektir A minimum (oyuncu İÇİNDE oyuncuya "zarar vermek" istiyor A).

Oyuncunun en küçük kazancını belirtelim A olası tüm oyuncu stratejileri için Ai stratejisini seçtiğinde İÇİNDE(en küçük sayı Benödeme matrisinin inci satırı), yani

Tüm sayılar () arasında en büyüğünü seçiyoruz: .

Hadi arayalım oyunun en düşük fiyatı, veya maksimum kazanç (maxmin). Bu, B oyuncusunun herhangi bir stratejisi için A oyuncusunun garantili bir kazancıdır. Buradan,

Maksimuma karşılık gelen stratejiye denir maksimuma çıkarma stratejisi . oyuncu İÇİNDE oyuncunun kazancını azaltmakla ilgileniyor A, Bj stratejisini seçerken mümkün olan maksimum getiriyi dikkate alır. A. Haydi belirtelim

Tüm sayılar arasından en küçüğünü seçin

ve hadi arayalım Oyunun en yüksek fiyatı veya minimaks galibiyet(minimaks). Ego, B oyuncusunun kaybını garantiledi. Öyleyse,

Minimax'a karşılık gelen stratejiye denir minimaks stratejisi.

Oyuncuların en "temkinli" minimaks ve maksimizasyon stratejilerini seçmelerini sağlayan prensibe ne ad verilir? minimaks prensibi . Bu prensip, her oyuncunun rakibinin hedefinin tersi bir hedefe ulaşmaya çalıştığı yönündeki makul varsayımdan kaynaklanmaktadır.

Teorem. Oyunun alt fiyatı her zaman oyunun üst fiyatını aşmaz .

Oyunun üst ve alt fiyatları aynı ise oyunun üst ve alt fiyatlarının toplamına denir. Oyunun saf fiyatı, veya oyunun bedeli karşılığında. Oyunun fiyatına karşılık gelen Minimax stratejileri: optimal stratejiler , ve onların bütünlüğü - en uygun çözüm veya Oyunun çözümü. Bu durumda oyuncu A garanti edilen maksimum değeri alır (oyuncunun davranışından bağımsız olarak) İÇİNDE) kazançlar v ve oyuncu İÇİNDE garanti edilen minimum seviyeye ulaşır (oyuncunun davranışından bağımsız olarak) A) kaybetmek v. Oyunun çözümünün bu olduğunu söylüyorlar Sürdürülebilirlik , onlar. Eğer bir oyuncu kendi optimal stratejisine sadık kalırsa, diğerinin optimal stratejisinden sapması karlı olamaz.

Eğer oyunculardan biri (örneğin A) kendi optimal stratejisine sadık kalır ve diğer oyuncu (İÇİNDE) herhangi bir şekilde optimal stratejisinden sapacaksa, Sapmayı yapan oyuncu için bu asla karlı olamaz; böyle bir oyuncu sapması İÇİNDE en iyi ihtimalle kazançları değiştirmeden bırakabilir. ve en kötü durumda artırın.

Tam tersine eğer İÇİNDE optimal stratejisine bağlı kalır ve A kendinden sapıyorsa bunun hiçbir şekilde kendisine faydası olamaz. A.

Bir çift saf strateji ve ancak ve ancak karşılık gelen öğe varsa oyuna en uygun çözümü verir hem sütununun en büyüğü hem de satırının en küçüğüdür. Bu duruma, eğer varsa denir. priz. Geometride, bir yüzey üzerinde aynı anda bir koordinatta minimum ve diğerinde maksimuma sahip olma özelliğine sahip bir noktaya denir. güç Bu nokta, benzetme yoluyla bu terimin oyun teorisinde kullanıldığı anlamına gelir.

Hangi oyun için , isminde bir güç noktasıyla oynamak. Bu özelliğe sahip bir eleman matrisin kuvvet noktasıdır.

Yani, güç noktası olan her oyun için, her iki taraf için de aşağıdaki özelliklerde farklılık gösteren bir çift optimal stratejiyi belirleyen bir çözüm vardır.

1) Her iki taraf da kendi optimal stratejilerine sadık kalırsa, ortalama getiri oyunun net maliyetine eşit olur v, bu aynı anda hem alt hem de üst fiyatıdır.

2) Taraflardan biri kendi optimal stratejisine bağlı kalırken diğeri kendi stratejisinden saparsa, sapan taraf yalnızca kaybedebilir ve hiçbir durumda kazancını artıramaz.

Oyun teorisinde, özellikle tam bilgiye sahip her oyunun bir güç noktası olduğu ve dolayısıyla bu tür her oyunun bir çözümü olduğu, yani her iki tarafın da ortalama getiri sağlayan bir çift optimal stratejisi olduğu kanıtlanmıştır. oyunun maliyetine eşittir. Tam bilgiye sahip bir oyun yalnızca kişisel hamlelerden oluşuyorsa, her iki taraf da kendi optimal stratejisini uyguladığında, oyun her zaman iyi tanımlanmış bir sonuçla, yani oyunun maliyetine tam olarak eşit bir kazançla sonuçlanmalıdır.

22. Oyunun karma stratejilerle çözümü.

Pratik öneme sahip sonlu oyunlar arasında kuvvet puanına sahip oyunlar nispeten nadirdir; Daha tipik bir durum, oyunun alt ve üst fiyatının farklı olmasıdır. Bu tür oyunların matrislerini analiz ederek, her oyuncuya tek bir strateji seçeneği verilirse, o zaman makul şekilde hareket eden bir rakibe güvenerek bu seçimin minimax ilkesine göre belirlenmesi gerektiği sonucuna varıyoruz. Maksimum stratejimize bağlı kalarak, düşmanın herhangi bir davranışı için, α oyununun daha düşük fiyatına eşit bir kazancı kendimize garanti ederiz.Birkaç saf stratejinin kullanımından oluşan bu tür birleşik stratejiler, rastgele bir yasaya göre bir rastgele yasaya göre dönüşümlü olarak değişir. oyun teorisinde belirli bir frekans oranına denir karma stratejiler

Karma strateji Sa A oyuncusu A1,A1,…,Ai,…,Am saf stratejilerinin p1,p2,…pi,…pm olasılıklarıyla uygulanmasıdır ve olasılıkların toplamı 1:'e eşittir. Oyuncu A'nın karma stratejileri bir matris olarak yazılır

veya Sa=(p1,p2,…,pi,…,pm) dizisi olarak.

Benzer şekilde B oyuncusunun karma stratejileri şu şekilde ifade edilir:

Veya Sb=(q1,q2,…,qi,…,qn),

stratejilerin ortaya çıkma olasılıklarının toplamı 1: .

Açıkçası, her saf strateji, biri hariç tüm stratejilerin sıfır frekansla (olasılıkla) uygulandığı ve bu stratejinin 1 frekansıyla (olasılıkla) kullanıldığı karma stratejinin özel bir durumudur.

Sadece saf değil, aynı zamanda karma stratejiler kullanarak, her sonlu oyun için bir çözüm elde etmenin mümkün olduğu ortaya çıktı, yani her iki oyuncu da bunları kullandığında bu tür (genel durumda karma) stratejilerden bir çift, Kazanç oyunun fiyatına eşit olacaktır ve optimal stratejiden herhangi bir tek taraflı sapma, getiriyi yalnızca sapkın tarafın aleyhine yönde değiştirebilir. Böylece minimaks prensibine göre belirlenir. en uygun çözüm (veya çözüm) oyunlar: bunlar bir çift optimal stratejidir genel durumda karışıktır ve şu özelliğe sahiptir: eğer oyunculardan biri optimal stratejisine bağlı kalırsa, diğerinin kendi stratejisinden sapması karlı olamaz. Optimum çözüme karşılık gelen getiriye denir oyunun bedeli karşılığında v . Oyunun fiyatı eşitsizliği karşılıyor:

Burada α ve β oyunun alt ve üst fiyatlarıdır.

Belirtilen beyan sözde içeriğin içeriğini oluşturmaktadır. Oyun teorisinin temel teoremi. Bu teorem ilk olarak 1928'de John von Neumann tarafından kanıtlandı. Teoremin bilinen kanıtları nispeten karmaşıktır; Bu nedenle sadece formülasyonunu vereceğiz.

Her sonlu oyunun muhtemelen karma stratejiler arasında en az bir optimal çözümü vardır.

Ana teoremden her sonlu oyunun bir fiyatı olduğu sonucu çıkar.

Bırak olsun – bir çift optimal strateji. Eğer bir saf strateji, sıfırdan farklı olasılığa sahip bir optimal karma stratejiye dahil edilirse buna denir. aktif (faydalı) .

Adil aktif stratejiler teoremi: oyunculardan biri optimal karma stratejisine sadık kalırsa, ikinci oyuncu aktif stratejilerinin sınırlarını aşmazsa getiri değişmeden kalır ve oyunun maliyetine eşit olur.

Oyuncu aktif stratejilerinden herhangi birini saf haliyle kullanabilir ve bunları herhangi bir oranda karıştırabilir.

Bu teoremin pratik önemi büyüktür; bir eyer noktasının yokluğunda en uygun stratejileri bulmak için özel modeller sağlar.

Hadi düşünelim 2x2 boyutlu oyun Bu, sonlu bir oyunun en basit durumudur. Eğer böyle bir oyunun bir eyer noktası varsa, o zaman en iyi çözüm bu noktaya karşılık gelen bir çift saf stratejidir.

Oyun teorisinin temel teoremine uygun olarak eyer noktasının olmadığı bir oyun optimal çözüm mevcuttur ve bir çift karma stratejiyle belirlenir Ve.

Bunları bulmak için aktif stratejiler teoremini kullanıyoruz. Eğer oyuncu A optimal stratejisine bağlı kalıyor , o zaman ortalama kazancı oyunun fiyatına eşit olacaktır v oyuncunun kullandığı aktif strateji ne olursa olsun İÇİNDE. 2x2'lik bir oyunda orta nokta yoksa herhangi bir saf rakibin stratejisi aktiftir. Oyuncunun kazancı A(oyuncu kaybı İÇİNDE)– matematiksel beklentisi (ortalama değeri) oyunun fiyatı olan rastgele bir değişken. Bu nedenle ortalama oyuncunun kazancı A(optimum strateji) şuna eşit olacaktır: v hem 1. hem de 2. düşman stratejileri için.

Oyunun bir getiri matrisi ile verilebilmesine izin verin.

Ortalama oyuncu kazancı A, eğer optimal bir karma strateji kullanıyorsa ve oyuncu İÇİNDE - saf strateji B1 (bu, kazanç matrisinin 1. sütununa karşılık gelir) R), oyunun fiyatına eşit v: .

Oyuncu aynı ortalama kazancı alır A 2. oyuncu B2 stratejisini kullanıyorsa, yani. . Bunu göz önünde bulundurarak, optimal stratejiyi belirlemek için bir denklem sistemi elde ederiz. ve oyun fiyatları v:

Bu sistemi çözerek en uygun stratejiyi elde ederiz

ve oyunun fiyatı.

Arama yaparken aktif stratejilerle ilgili teoremin uygulanması – oyuncunun optimal stratejisi İÇİNDE, bunu herhangi bir saf oyuncu stratejisi için buluyoruz A (A1 veya A2) ortalama oyuncu kaybı İÇİNDE oyunun fiyatına eşit v yani

Daha sonra en uygun strateji aşağıdaki formüllerle belirlenir: .

Bir oyunu çözme sorunu, eğer matrisi bir eyer noktası içermiyorsa, değerler ne kadar büyük olursa o kadar zordur. M Ve N. Bu nedenle, matris oyunları teorisinde, bazı oyunların çözümünün diğerlerinin, daha basit olanların çözümüne, özellikle de matrisin boyutunun azaltılmasına indirgendiği yöntemler dikkate alınır. Matris boyutu hariç tutularak azaltılabilir çoğaltılıyor ve açıkçası kârsız stratejiler.

Kopyalamak ödeme matrisindeki öğelerin aynı değerlerine karşılık gelen stratejilere denir, yani. matris aynı satırları (sütunları) içerir.

Matrisin i'inci satırının tüm elemanları k'inci satırın karşılık gelen elemanlarından daha azsa, o zaman oyuncu için i'inci strateji A kârsız (daha az kazanç).

Matrisin r'inci sütununun tüm elemanları j'inci sütunun karşılık gelen elemanlarından büyükse, o zaman oyuncu için İÇİNDE R'inci strateji kârsızdır (kayıp daha fazladır).

Tekrarlanan ve açıkça kârsız olan stratejileri ortadan kaldırma prosedürü her zaman oyunun çözümünden önce gelmelidir.

23. 2x2 oyununun geometrik yorumu

Oyun çözümü 2x2 net bir geometrik yoruma olanak sağlar.

Oyunun ödeme matrisi P=(aij), i, j=1,2 ile belirtilmesine izin verin.

Apsis ekseninde (Şek.) çizeceğiz birim A1A2 segmenti; A1 noktası ( X=0) A1 stratejisini, A2 noktasını gösterir ( X=1) A2 stratejisini gösterir ve bu bölümün tüm ara noktaları ilk oyuncunun Sa karma stratejileridir ve Sa'dan bölümün sağ ucuna kadar olan mesafe A1 stratejisinin p1 olasılığıdır , sol uca olan mesafe – A2 stratejisinin p2 olasılığı .

A1 ve A2 noktalarından apsis eksenine iki dik çizelim: eksen I-I ve eksen II-II. I-I ekseninde A1 stratejisinin kazançlarını çizeceğiz; II-II ekseninde – A2 stratejisinin getirileri.

Eğer A oyuncusu A1 stratejisini kullanıyorsa, B oyuncusunun B1 stratejisiyle elde ettiği getiri a11'dir ve B2 stratejisiyle getirisi a12'ye eşittir. I eksenindeki a11 ve a12 sayıları B1 ve B2 noktalarına karşılık gelir.

Eğer A oyuncusu A2 stratejisini kullanıyorsa, B oyuncusunun B1 stratejisiyle elde ettiği getiri a21'dir ve B2 stratejisiyle getirisi a22'ye eşittir. a21 ve a22 sayıları eksen II üzerindeki B1 ve B2 noktalarına karşılık gelir.

B1 (I) ve B1 (II) noktalarını bağlarız; B2 (I) ve B2 (II). İki düz çizgimiz var. Doğrudan B1B1– eğer oyuncu A karma bir strateji uygular (p1 ve p2 olasılıklarıyla A1 ve A2 stratejilerinin herhangi bir kombinasyonu) ve B oyuncusu B1 stratejisini kullanır. Oyuncu kazanır A bu çizgi üzerinde bulunan bir noktaya karşılık gelir. Karma stratejiye karşılık gelen ortalama getiri a11p1+a21p2 formülüyle belirlenir ve M1 noktasıyla temsil edilir. düz B1B1'de.

Benzer şekilde, ikinci oyuncunun B2 stratejisini kullanmasına karşılık gelen B2B2 segmentini oluşturuyoruz. Bu durumda ortalama kazanç a12p1+a22p2 formülüyle belirlenir ve M2 noktasıyla temsil edilir. doğrudan B2B2'de.

En uygun strateji S*a'yı bulmamız gerekiyor, yani minimum getirisi (herhangi bir davranış için) İÇİNDE) maksimuma dönecektir. Bunun için inşa edeceğiz kazanç alt limiti B1B2 stratejileri için , yani, Şekil 2'de işaretlenen kesikli B1NB2 çizgisi. kalın çizgi. Bu alt sınır oyuncunun minimum kazancını ifade edecektir A karma stratejilerinden herhangi biriyle; noktaN , Bu minimum kazancın maksimuma ulaştığı ve çözümü (optimal strateji) ve oyunun fiyatını belirlediği yer. Ordinat noktası N oyunun bir bedeli var v. Nokta koordinatları N B1B1 ve B2B2 doğrularının kesişme noktalarının koordinatları olarak buluyoruz. Bizim durumumuzda oyunun çözümü stratejilerin kesişme noktasıyla belirlendi. Ancak bu her zaman böyle olmayacaktır.

Geometrik olarak bir oyuncu olarak en uygun strateji belirlenebilir. A, oyuncu da öyle İÇİNDE; her iki durumda da minimax ilkesi kullanılır, ancak ikinci durumda kazancın alt değil üst sınırı oluşturulur, maksimum değil minimum buna göre belirlenir.

Ödeme matrisi negatif sayılar içeriyorsa, sorunu grafiksel olarak çözmek için negatif olmayan öğeler içeren yeni bir matrise geçmek daha iyidir; Bunu yapmak için karşılık gelen pozitif sayıyı orijinal matrisin elemanlarına eklemek yeterlidir. Oyunun çözümü değişmeyecek ancak oyunun fiyatı bu rakam kadar artacak. 2×n, m×2 oyununu çözmek için grafiksel yöntem kullanılabilir.

24. Bir matris oyununu doğrusal programlama problemine indirgemek

Genel durumda m×n oyununun net bir geometrik yorumu yoktur. Çözümü büyük şirketler için oldukça emek yoğundur. T Ve N, ancak doğrusal programlama probleminin çözümüne indirgenebildiği için temel bir zorluğu yoktur. Hadi gösterelim.

m×n oyununun getiri matrisi tarafından verilse . oyuncu A A1,A2,..Ai,..Am stratejileri vardır , oyuncu İÇİNDE - stratejiler B 1,B 2,..B Ben,.. B N. Optimum stratejilerin ve bunların nerede olduğunun belirlenmesi gereklidir. karşılık gelen Ai, Bj saf stratejilerini kullanma olasılıkları,

Optimal strateji aşağıdaki gereksinimi karşılar. Oyuncuya sağlar A ortalama kazanç, oyunun fiyatından az olmamak üzere v, herhangi bir oyuncu stratejisi için İÇİNDE ve oyunun fiyatına eşit kazançlar v, oyuncunun optimal stratejisiyle İÇİNDE. Genelliği kaybetmeden şunu varsayıyoruz: v> 0; bu, tüm unsurları yaparak başarılabilir . Eğer oyuncu A Bj oyuncusunun herhangi bir saf stratejisine karşı karma bir strateji uygular İÇİNDE, sonra alır ortalama kazanç , veya Matematiksel kazanma beklentisi (yani elementler J-GÖödeme matrisinin sütunları A1, A2,..Ai,..Am stratejilerinin karşılık gelen olasılıkları ile terim terim çarpılır ve sonuçlar toplanır).

Optimal bir strateji için tüm ortalama getiriler oyun fiyatından az değildir v dolayısıyla bir eşitsizlik sistemi elde ederiz:

Eşitsizliklerin her biri bir sayıya bölünebilir. Yeni değişkenleri tanıtalım: . Daha sonra sistem şu formu alır:

Oyuncu hedefi A - garantili kazancınızı en üst düzeye çıkarın, yani. oyun fiyatı v.

Eşitliğe bölerek değişkenlerin şu koşulu karşıladığını buluruz: . Oyunun fiyatını maksimuma çıkarmak v miktarı en aza indirmeye eşdeğerdir , Bu nedenle problem şu şekilde formüle edilebilir: değişkenlerin değerlerini belirlemek , anneböylece doğrusal kısıtlamaları karşılarlar(*) Ve doğrusal fonksiyon iken (2*) minimuma kadar uygulanır.

Bu bir doğrusal programlama problemidir. (1*)–(2*) problemini çözerek en uygun çözümü elde ederiz ve optimal strateji .

Optimum stratejiyi belirlemek için oyuncunun İÇİNDE garanti edilen kazancı en aza indirmeye çalışır, yani. maksimumu bul Değişkenler eşitsizlikleri karşılar

bu da bir oyuncunun ortalama kaybının İÇİNDE Oyuncunun kullandığı saf strateji ne olursa olsun oyunun fiyatını aşmaz A.

(4*)'ı belirtirsek, bir eşitsizlik sistemi elde ederiz:

Değişkenler koşulu karşılıyor.

Oyun bir sonraki soruna geldi.

Değişken Değerleri Belirleyin eşitsizlik sistemini tatmin eden (5*)Ve doğrusal fonksiyonu maksimuma çıkar

Doğrusal programlama probleminin çözümü (5*), (6*) optimal stratejiyi belirler. Aynı zamanda oyunun fiyatı. (7*)

(1*), (2*) ve (5*), (6*) problemleri için genişletilmiş matrisleri derledikten sonra, bir matrisin diğerinden aktarma yoluyla elde edildiğinden emin oluruz:

Dolayısıyla doğrusal programlama problemleri (1*), (2*) ve (5*), (6*) karşılıklı olarak dualdir. Açıkçası, belirli problemlerde optimal stratejileri belirlerken, çözümü daha az zahmetli olan karşılıklı ikili problemlerden birini seçmek ve diğer soruna dualite teoremlerini kullanarak çözüm bulmak gerekir.

M×n boyutunda rastgele sonlu bir oyunu çözerken aşağıdaki şemaya uyulması önerilir:

1. Diğer stratejilerle karşılaştırıldığında açıkça kârsız olan ödeme matrisi stratejilerini hariç tutun. Oyuncu için bu tür stratejiler A

1. İktisatta yöneylem araştırmasının konusu ve amaçları. Yöneylem araştırması teorisinin temel kavramları.

Yöneylem araştırmasının konusu, birbirleriyle her zaman tutarlı olmayan ve zıt olabilen çok sayıda etkileşimli birimden oluşan organizasyonel yönetim sistemleri veya organizasyonlardır.

Yöneylem araştırmasının amacı, organizasyonları yönetmek için alınan kararları niceliksel olarak doğrulamaktır.

Organizasyonun tamamı için en faydalı olduğu ortaya çıkan çözüme optimal denir ve bir veya daha fazla bölüme en faydalı olan çözüm suboptimal olacaktır.

Yöneylem araştırması, organizasyonel sistemlerin en uygun şekilde yönetilmesi için yöntemlerin geliştirilmesi ve pratik uygulamasıyla ilgilenen bir bilimdir.

Operasyon, tek bir planla birleştirilen ve belirli bir hedefe ulaşmayı amaçlayan herhangi bir olaydır (eylemler sistemi).

Yöneylem araştırmasının amacı, optimal çözümlerin ön niceliksel gerekçelendirilmesidir.

Bize bağlı olan herhangi bir parametre seçimine çözüm denir. Optimal çözümler, belirli özelliklere dayalı olarak diğerlerine tercih edilen çözümlerdir.

Birleşimleri çözümü oluşturan parametrelere çözüm elemanları denir.

Uygun çözüm kümesine sabit ve ihlal edilemeyecek koşullar verilmiştir.

Verimlilik göstergesi, farklı çözümleri verimlilik açısından karşılaştırmanıza olanak tanıyan niceliksel bir ölçümdür.

2. Ağ planlama ve yönetimi kavramı. Sürecin ağ modeli ve unsurları.

Ağ grafikleriyle çalışma yöntemi - ağ planlaması - grafik teorisine dayanmaktadır. Yunancadan tercüme edilen bir grafik (grafpho - yazıyorum) bir nokta sistemini temsil eder, bazıları çizgiler - yaylar (veya kenarlar) ile birbirine bağlanır. Bu, etkileşimli sistemlerin topolojik (matematiksel) bir modelidir. Grafikleri kullanarak yalnızca ağ planlama sorunlarını değil, diğer sorunları da çözebilirsiniz. Ağ planlama yöntemi, birbiriyle ilişkili bir dizi işi planlarken kullanılır. Organizasyonel ve teknolojik iş sırasını görselleştirmenize ve aralarındaki ilişkiyi kurmanıza olanak tanır. Ek olarak, değişen karmaşıklık derecelerindeki operasyonların koordinasyonuna ve tüm işin süresinin (yani organizasyonel olayın) bağlı olduğu operasyonların tanımlanmasına ve ayrıca her operasyonun zamanında tamamlanmasına odaklanmaya olanak tanır.

Ağ planlama ve yönetiminin temeli, belirli bir hedefe ulaşma sürecini yansıtan bir dizi birbirine bağlı iş ve olayı modelleyen ağ modelidir (NM). Grafik veya tablo şeklinde sunulabilir.

Ağ modelinin temel kavramları:

Olay, iş, yol.

Olaylar bir veya daha fazla işin sonucudur. Bunların süre uzatımı yoktur.

Yol, birbirini takip eden, başlangıç ​​ve bitiş köşelerini birbirine bağlayan bir iş zinciridir.

Yolculuğun süresi, onu oluşturan işlerin sürelerinin toplamı ile belirlenir.

3. Bir ağ diyagramının oluşturulması ve organizasyonu.

Ağ planlama ve yönetim sistemlerinde (NPS) inşaat ve montaj iş sürecinin teknolojik ve organizasyonel ilişkilerini yansıtan bir model olarak ağ modeli kullanılmaktadır.

Bir ağ modeli, uygulanması bir veya daha fazla belirlenmiş hedefe ulaşılmasına yol açan ve bu süreçler arasında yerleşik ilişkileri gösteren süreçlerin grafiksel bir temsilidir. Ağ diyagramı, hesaplanan zaman parametrelerine sahip bir ağ modelidir.

Faaliyetlerin ve olayların karşılıklı bağımlılığını belirleyen ağ diyagramının yapısına topolojisi denir.

İş, zaman, emek ve maddi kaynak gerektiren, tamamlandığında belirli sonuçların elde edilmesini sağlayan bir üretim sürecidir.

Zaman gerektirmeyen bir bağımlılık (kurgusal çalışma) noktalı okla gösterilmiştir. Kurgusal çalışma, olaylar ve faaliyetler arasındaki ilişkileri göstermek için bir ağ diyagramında kullanılır.

Ağ şeması işin zamanını, maliyetini ve diğer özelliklerini kullanır.

Sürekli çalışma - bu işi iş günlerinde veya ağ çizelgesindeki tüm işler için aynı olan diğer zaman birimlerinde tamamlamak için gereken süre. İşin süresi belirli (deterministik) veya dağılım yasasıyla belirlenen rastgele bir değişken olabilir.

İşin maliyeti, bu işin süresine ve koşullarına bağlı olarak, işi tamamlamak için gerekli olan doğrudan maliyetlerdir.

Kaynaklar, belirli bir işi tamamlamak için gereken fiziksel birimlere olan ihtiyaçla karakterize edilir.

İşin kalitesi, güvenilirliği ve diğer göstergeleri işin ek özellikleri olarak hizmet eder.

Bir olay, bir veya daha fazla işin başlaması için gerekli ve yeterli olan bir veya daha fazla işin tamamlanması olgusudur. Her olaya kod adı verilen bir numara atanır. Her iş iki olayla tanımlanır: i ile gösterilen bir başlangıç ​​olay kodu ve j ile gösterilen bir bitiş olay kodu.

Daha önce hiçbir çalışması olmayan olaylara başlangıç ​​denir; kendisinden sonra gelen olaylar sonludur.

1 Ağ yapısının yönü farklı nitelikte olabilir. Ağ şeması, ilk olaydan son olaya ve son olaydan ilk olaya kadar, ayrıca herhangi bir olaydan ilk veya son olaya kadar oluşturulabilir.

2 Bir ağ oluştururken aşağıdaki sorunlar çözülür:

Bu çalışmaya başlamak için hangi iş(ler)in tamamlanması gerekir;

Bu çalışmaya paralel olarak hangi işin yapılması tavsiye edilir;

3 İlk ağ programı, ağı oluşturan işin süresi dikkate alınmadan oluşturulur.

4 Grafiğin biçimi basit ve görsel olarak algılanması kolay olmalıdır.

5 İki olay arasında yalnızca bir iş meydana gelebilir. Bina ve yapıların inşası sırasında işler sıralı, paralel veya eş zamanlı, bazıları sıralı, bazıları paralel olarak yapılabilmekte, bunun sonucunda bireysel işler arasında çeşitli bağımlılıklar gelişmektedir.

Olayların numaralandırılması (kodlanması), ilk olaydan son olaya kadar ağ inşaatının tamamlanmasından sonra gerçekleştirilir.

4. Ağ diyagramının kritik yolu. Zaman rezervleri. Ağ programında olayların erken ve geç tarihleri ​​ve çalışmaları.

Bir ağ diyagramında başlangıç ​​ve bitiş olayları arasında birden fazla yol olabilir. En uzun süreye sahip olan yola kritik denir. Kritik yol, aktivitenin toplam süresini belirler. Diğer tüm yolların süresi daha kısadır ve bu nedenle bu yollarda yapılan işin zaman rezervi vardır.

Kritik yol, ağ diyagramında kalın veya çift çizgilerle (oklar) gösterilir.

Bir ağ şeması çizilirken iki kavram özellikle önemlidir:

İşe erken başlama, kabul edilen teknolojik sırayı ihlal etmeden bu işe başlanmasının mümkün olmadığı dönemdir. İlk olaydan bu çalışmanın başlangıcına kadar olan en uzun yol tarafından belirlenir.

İşin geç tamamlanması, toplam çalışma süresinin artmadığı, işin tamamlanması için en son son tarihtir. Belirli bir olaydan tüm işin tamamlanmasına kadar olan en kısa yol ile belirlenir.

Erken bitirme, işin daha önce tamamlanamayacağı son teslim tarihidir. Erken başlangıç ​​artı bu işin süresine eşittir

Geç başlangıç ​​- toplam inşaat süresini artırmadan işin başlatılamadığı süre. Geç bitirme eksi bu işin süresine eşittir.

Bir olay yalnızca bir işin sonuysa (yani ona yalnızca bir ok yönlendirilmişse), bu işin erken sonu bir sonraki işin erken başlangıcına denk gelir.

Genel (tam) rezerv, işin toplam süresini artırmadan belirli bir işin tamamlanmasının ertelenebileceği maksimum süredir. Geç ve erken başlangıç ​​(veya geç ve erken bitiş - ki bu aynı şeydir) arasındaki farka göre belirlenir.

Özel (ücretsiz) rezerv, bir sonraki işin erken başlatılmasını değiştirmeden belirli bir işin yürütülmesinin ertelenebileceği maksimum süredir. Bu ayırma yalnızca etkinlik iki veya daha fazla iş (bağımlılık) içerdiğinde mümkündür; iki veya daha fazla ok (düz veya noktalı) ona doğru yönlendirilir. O zaman bu işlerden yalnızca birinin bir sonraki işin erken başlangıcına denk gelen erken bitişi olacaktır, ancak geri kalanı için bunlar farklı değerler olacaktır. Bu fark her işin kendine özel rezervi olacaktır.

5. Dinamik programlama. Bellman'ın optimallik ve kontrol ilkesi.

Dinamik programlama en güçlü optimizasyon tekniklerinden biridir. Çeşitli profillerdeki uzmanlar, rasyonel kararlar verme, en iyi seçenekleri seçme ve optimum yönetim sorunlarıyla ilgilenmektedir. Optimizasyon yöntemleri arasında dinamik programlama özel bir yere sahiptir. Bu yöntem, temel ilkesinin (optimalite ilkesi) basitliği ve açıklığı nedeniyle son derece çekicidir. Optimallik ilkesinin uygulama kapsamı son derece geniştir; uygulanabileceği problemlerin kapsamı henüz tam olarak belirlenmemiştir. En başından beri dinamik programlama, optimizasyon problemlerini pratik olarak çözmenin bir yolu olmuştur.

Ana araştırma yöntemi olan optimallik ilkesine ek olarak, dinamik programlama aparatında, belirli bir optimizasyon probleminin benzer problemler ailesine daldırılması fikri büyük bir rol oynar. Onu diğer optimizasyon yöntemlerinden ayıran üçüncü özelliği ise nihai sonucun şeklidir. Optimumluk ilkesinin ve çok adımlı, ayrık süreçlere daldırma ilkesinin uygulanması, kalite kriterinin optimal değeriyle ilgili tekrarlanan fonksiyonel denklemlere yol açar. Ortaya çıkan denklemler, orijinal problem için tutarlı bir şekilde optimal kontrollerin yazılmasını mümkün kılar. Buradaki fayda, tüm süreç için kontrolün hesaplanması sorununun, sürecin bireysel aşamaları için kontrolün hesaplanmasına ilişkin bir dizi daha basit probleme bölünmesidir.

Yöntemin ana dezavantajı, Bellman'ın deyimiyle "boyutsallığın laneti"dir; sorunun boyutu arttıkça karmaşıklığı da felaket derecede artar.

6. İşletmeler arasında fon dağıtımı sorunu.

Dinamik programlama yöntemini kullanarak optimum kontrolü oluşturma prosedürünün iki aşamaya ayrıldığını söyleyebiliriz: ön ve son. Ön aşamada, her adım için, SOE, sistemin durumuna (önceki adımların sonucunda elde edilen) bağlı olarak belirlenir ve bundan başlayarak, yine duruma bağlı olarak geri kalan tüm adımlardaki koşullu olarak optimal kazanç belirlenir. . Son aşamada her adım için (koşulsuz) optimal kontrol belirlenir. Ön (koşullu) optimizasyon adım adım ters sırayla gerçekleştirilir: son adımdan birinciye; nihai (koşulsuz) optimizasyon - yine adımlarla, ancak doğal bir sırayla: ilk adımdan son adıma. İki optimizasyon aşamasından ilki kıyaslanamayacak kadar daha önemli ve zaman alıcıdır. İlk aşamayı tamamladıktan sonra ikinciyi tamamlamak herhangi bir zorluk yaratmaz: Geriye yalnızca ilk aşamada hazırlanmış olan önerileri "okumak" kalır.

7. Doğrusal programlama probleminin ifadesi.

Doğrusal programlama, tek bir kriterin varlığıyla karakterize edilen ekonomik sorunları çözmek için popüler bir araçtır (örneğin, bir üretim programının en uygun seçimi yoluyla üretimden elde edilen gelirin en üst düzeye çıkarılması veya örneğin nakliye maliyetlerinin en aza indirilmesi vb.). Ekonomik sorunlar kaynak sınırlamalarıyla (maddi ve/veya mali) karakterize edilir. Eşitsizlikler sistemi şeklinde, bazen de eşitlikler şeklinde yazılırlar.

Genelleştirilmiş parametrik olmayan yöntem çerçevesinde kabul edilebilir fiyat aralıklarının (veya satış hacimlerinin) tahmin edilmesi açısından doğrusal programlamanın kullanılması şu anlama gelir:

Kriter, f ilgi grubundan bir sonraki ürünün MAX fiyatıdır.

Kontrollü değişkenler f grubundaki tüm ürünlerin fiyatlarıdır.

Genelleştirilmiş parametrik olmayan yöntemi kullanan tahmin problemimizin sınırlamaları şunlardır:

a) bir eşitsizlik sistemi (tüketici davranışının rasyonelliği üzerindeki kısıtlamalar) (bkz. 4.2. Genelleştirilmiş parametrik olmayan yöntem çerçevesinde tahmin);

b) kontrol edilen değişkenlerin negatif olmaması gerekliliği (tahmin problemimizde, f grubundaki ürünlerin fiyatlarının son zaman noktasındaki fiyat değerlerinin %80'inin altına düşmemesini isteyeceğiz);

c) eşitlik biçimindeki bütçe kısıtlaması - f grubundan ürünlerin satın alınmasına ilişkin maliyet miktarının sabit olması gerekliliği (örneğin %15 enflasyon dikkate alınarak).

8. Doğrusal programlama problemlerini çözmek için grafiksel yöntem.

Grafiksel yöntem, doğrusal programlama probleminin geometrik yorumuna dayanır ve aşağıdaki gibi oluşturulan bir çözüm polihedronunu oluşturmak oldukça zor olduğundan, esas olarak iki boyutlu uzaydaki problemleri çözerken ve yalnızca üç boyutlu uzaydaki bazı problemleri çözerken kullanılır. yarım uzayların kesişmesinin bir sonucudur. Üçten büyük boyutlu bir uzayda bir problemi grafiksel olarak göstermek genellikle imkansızdır.

Doğrusal programlama probleminin iki boyutlu bir uzayda belirtilmesine izin verin, yani kısıtlamalar iki değişken içerir.

Bir fonksiyonun minimum değerini bulun

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2,3) x1 0, x2 0

(2.3) koşulu altında sistemin (2.2) tutarlı olduğunu ve çözüm poligonunun sınırlı olduğunu varsayalım. Eşitsizliklerin (2.2) ve (2.3) her biri, yukarıda belirtildiği gibi, sınır çizgileri olan bir yarım düzlemi tanımlar: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Z'nin sabit değerleri için doğrusal fonksiyon (2.1), düz bir çizginin denklemidir: C1x1 + C2x2 = sabit. Kısıtlar sisteminin (2.2) çözümlerinden oluşan bir çokgen ve Z = 0'da doğrusal fonksiyonun (2.1) bir grafiğini oluşturalım (Şekil 2.1). Daha sonra ortaya atılan doğrusal programlama problemine aşağıdaki yorum yapılabilir. Çözüm poligonunda C1x1 + C2x2 = const destek çizgisinin ve Z fonksiyonunun minimuma ulaştığı noktayı bulun.

Z = C1x1 + C2x2 değerleri N = (C1, C2) vektörü yönünde artar, bu nedenle Z = 0 düz çizgisini X vektörü yönünde kendisine paralel olarak hareket ettiririz. 2.1'de, düz çizginin çözüm çokgenine göre (A ve C noktalarında) iki kez referans çizgisi haline geldiği ve A noktasında minimum değeri aldığı sonucu çıkar. A noktasının (x1, x2) koordinatları, aşağıdaki denklem çözülerek bulunur: AB ve AE düz çizgilerinin denklem sistemi.

Çözüm çokgeni sınırsız bir çokgen alan ise iki durum mümkündür.

Durum 1. N vektörü yönünde veya ona zıt yönde hareket eden C1x1 + C2x2 = const doğrusu sürekli olarak çözüm çokgeniyle kesişir ve ona hiçbir noktada destek değildir. Bu durumda doğrusal fonksiyon çözüm poligonunun hem üstünden hem de altından sınırlı değildir (Şekil 2.2).

Durum 2. Hareket eden düz çizgi yine de çözüm poligonuna göre bir destek haline gelir (Şekil 2.2, a - 2.2, c). Daha sonra, alanın türüne bağlı olarak, doğrusal fonksiyon yukarıdan sınırlanabilir ve aşağıdan sınırsız olabilir (Şekil 2.2, a), aşağıdan sınırlanabilir ve yukarıdan sınırsız olabilir (Şekil 2.2, b) veya hem alttan hem de alttan sınırlanabilir yukarıdan (Şekil 2.2, c).

9. Simpleks yöntemi.

Simpleks yöntemi doğrusal programlamanın ana yöntemidir. Problemin çözümü, koşullar çokyüzlüsünün köşelerinden birinin dikkate alınmasıyla başlar. İncelenen tepe noktası maksimuma (minimum) karşılık gelmiyorsa, komşuya doğru hareket ederler, sorunu çözerken hedef fonksiyonunun değerini maksimuma çıkarırlar ve sorunu minimuma çözerken azaltırlar. Böylece bir köşeden diğerine geçmek hedef fonksiyonunun değerini artırır. Çokyüzlünün köşe sayısı sınırlı olduğundan, sınırlı sayıda adımda en uygun değerin bulunması veya sorunun çözülemez olduğu gerçeğinin belirlenmesi garanti edilir.

Bu yöntem evrenseldir ve kanonik formdaki herhangi bir doğrusal programlama problemine uygulanabilir. Buradaki kısıtlama sistemi, bilinmeyenlerin sayısının denklem sayısından daha fazla olduğu bir doğrusal denklem sistemidir. Sistemin rütbesi r ise, o zaman geri kalan bilinmeyenler cinsinden ifade ettiğimiz r bilinmeyeni seçebiliriz. Kesinlik için, ardışık ilk bilinmeyenler X1, X2, ..., Xr'nin seçildiğini varsayıyoruz. O halde denklem sistemimiz şu şekilde yazılabilir:

Simpleks yöntemi, simpleks yönteminin temel teoremi adı verilen bir teoreme dayanmaktadır. Kanonik formdaki bir doğrusal programlama probleminin optimal planları arasında mutlaka kısıtlama sistemine yönelik bir referans çözüm bulunur. Eğer problemin optimal planı benzersizse, o zaman bazı referans çözümlerle örtüşür. Kısıtlama sistemine yönelik sınırlı sayıda farklı destekleyici çözüm vardır. Bu nedenle referans çözümler arasında arama yapılarak ve bunlar arasından F değeri en büyük olanı seçilerek kanonik formda soruna çözüm aranabilir. Ancak, öncelikle, tüm referans çözümleri bilinmiyor ve bulunması gerekiyor ve ikincisi, gerçek problemlerde bu çözümlerin çoğu var ve doğrudan arama pek mümkün değil. Simpleks yöntemi, destek çözümlerinin yönlendirilmiş numaralandırılmasına yönelik belirli bir prosedürdür. Simpleks yönteminin belirli bir algoritmasını kullanarak önceden bulunan belirli bir referans çözümüne dayanarak, F amaç fonksiyonunun değerinin eskisinden daha az olmadığı yeni bir referans çözümü hesaplıyoruz. Bir dizi adımdan sonra en uygun plan olan referans çözüme ulaşıyoruz.

10. Taşıma sorununun beyanı. Referans planlarını belirleme yöntemleri.

Bazı özdeş ürünlerin m adet kalkış noktası (“tedarikçiler”) ve n adet tüketim noktası (“tüketiciler”) vardır. Her öğe için aşağıdakiler tanımlanır:

ai - i'inci tedarikçinin üretim hacimleri, i = 1, …, m;

вj - j'inci tüketicinin talebi, j= 1,…,n;

сij, bir birim ürünün i'inci tedarikçi olan Ai noktasından j'inci tüketici olan Bj noktasına taşınmasının maliyetidir.

Açıklık sağlamak için, verileri nakliye maliyetleri tablosu olarak adlandırılan bir tablo şeklinde sunmak uygundur.

Tüm tüketicilerin talebini tam olarak karşılayacak, aynı zamanda yeterli tedarikçi arzının olacağı ve toplam nakliye maliyetlerinin minimum düzeyde olacağı bir nakliye planının bulunması gerekmektedir.

Ulaşım planı, ulaşım hacmini ifade eder; i'inci tedarikçiden j'inci tüketiciye taşınması gereken mal miktarı. Problemin matematiksel bir modelini oluşturmak için m·n değişken xij, i= 1,..., n, j= 1,..., m girmek gerekir; her bir xij değişkeni noktadan itibaren taşıma hacmini belirtir. Ai'den Bj noktasına. X = (xij) değişkenleri kümesi, problemin formülasyonuna dayalı olarak bulunması gereken plan olacaktır.

Bu, kapalı ve açık ulaştırma sorunlarının (CTZ) çözümü için bir koşuldur.

Açıkçası, Problem 1'in çözülebilir olması için toplam talebin tedarikçilerden gelen üretim hacmini aşmaması gerekir:

Bu eşitsizlik tam olarak sağlanıyorsa sorun "açık" veya "dengesiz" olarak adlandırılır, ancak bu durumda sorun "kapalı" taşıma sorunu olarak adlandırılır ve (2) formuna sahip olur:

Denge durumu.

Bu, kapalı taşıma problemlerinin (CTP) çözümü için bir koşuldur.

11. Taşıma problemini çözmek için algoritma.

Algoritmanın uygulanması bir dizi önkoşulun yerine getirilmesini gerektirir:

1. Bir birim ürünün her üretim noktasından her varış noktasına taşınmasının maliyeti bilinmelidir.

2. Üretimin her noktasındaki ürün stoğu bilinmelidir.

3. Her tüketim noktasındaki ürün gereksinimleri bilinmelidir.

4. Toplam arz toplam talebe eşit olmalıdır.

Ulaştırma problemini çözmeye yönelik algoritma dört aşamadan oluşur:

Aşama I: Verileri standart bir tablo biçiminde sunun ve uygun kaynak tahsisini bulun. Kabul edilebilir, varış noktalarındaki tüm talebi karşılamanıza ve ürün stoğunun tamamını üretim noktalarından çıkarmanıza olanak tanıyan bir kaynak dağıtımıdır.

Aşama 2. Ortaya çıkan kaynak tahsisinin optimallik açısından kontrol edilmesi

Aşama 3. Kaynakların sonuçta ortaya çıkan tahsisi optimal değilse, kaynaklar yeniden dağıtılarak taşıma maliyeti azaltılır.

Aşama 4. Ortaya çıkan kaynak tahsisinin optimalliğinin yeniden kontrol edilmesi.

Bu yinelemeli süreç, optimal çözüm elde edilene kadar tekrarlanır.

12. Envanter yönetimi modelleri.

Herhangi bir envanter yönetimi modelinin iki ana soruyu (ne zaman ve ne kadar) yanıtlamak üzere tasarlanmış olmasına rağmen, yapımında çeşitli matematiksel araçların kullanıldığı önemli sayıda model vardır.

Bu durum başlangıç ​​koşullarının farklılığı ile açıklanmaktadır. Envanter yönetimi modellerini sınıflandırmanın ana temeli, depolanan ürünlere olan talebin doğasıdır (daha genel bir derecelendirme açısından bakıldığında, şu anda yalnızca bağımsız talebin olduğu durumları ele aldığımızı hatırlayın).

Dolayısıyla talebin niteliğine bağlı olarak envanter yönetimi modelleri

deterministik;

olasılıksal.

Buna karşılık, deterministik talep, tüketim yoğunluğunun zaman içinde değişmediği durumlarda statik veya güvenilir talebin zamanla değişebildiği durumlarda dinamik olabilir.

Olasılıksal talep, talebin olasılık yoğunluk fonksiyonu zaman içinde değişmediğinde durağan olabilir ve olasılık yoğunluk fonksiyonunun zamana bağlı olarak değiştiği durumda durağan olmayabilir. Yukarıdaki sınıflandırma şekilde gösterilmiştir.

En basit durum, ürünlere yönelik deterministik statik talep durumudur. Ancak bu tür tüketim pratikte oldukça nadirdir. En karmaşık modeller durağan olmayan tipteki modellerdir.

Envanter yönetimi modelleri oluşturulurken ürünlere olan talebin doğasına ek olarak diğer birçok faktörün de dikkate alınması gerekir, örneğin:

siparişin yerine getirilmesi için son tarihler. Tedarik süresinin süresi sabit olabileceği gibi rastgele bir değişken de olabilir;

Envanter yenileme süreci. Anlık veya zamana dağıtılmış olabilir;

işletme sermayesi, depo alanı vb. ile ilgili kısıtlamaların varlığı.

13. Kuyruk sistemleri (QS) ve bunların etkinliğinin göstergeleri.

Kuyruk sistemleri (QS), benzer görevlerin tekrar tekrar yürütülmesini sağlayan özel tipte sistemlerdir. Bu tür sistemler ekonomi, finans, üretim ve günlük yaşamın birçok alanında önemli bir rol oynamaktadır. Finansal ve ekonomik alanda QS örnekleri olarak; Bu alanda çeşitli türlerdeki bankaları (ticari, yatırım, ipotek, yenilikçi, tasarruf), sigorta kuruluşlarını, devlet anonim şirketlerini, şirketleri, firmaları, dernekleri, kooperatifleri, vergi müfettişliklerini, denetim hizmetlerini, çeşitli iletişim sistemlerini (dahil) sayabiliriz. telefon santralleri), yükleme ve boşaltma kompleksleri (limanlar, yük istasyonları), benzin istasyonları, çeşitli işletmeler ve hizmet kuruluşları (mağazalar, bilgi masaları, kuaförler, bilet gişeleri, döviz büroları, tamir atölyeleri, hastaneler). Bilgisayar ağları, bilgi toplama, depolama ve işleme sistemleri, taşıma sistemleri, otomatik üretim alanları, üretim hatları, çeşitli askeri sistemler, özellikle hava veya füze savunma sistemleri gibi sistemler de bir tür QS olarak değerlendirilebilir.

Her QS, yapısında servis kanalları (cihazlar, hatlar) olarak adlandırılan belirli sayıda servis cihazını içerir. Kanalların rolü çeşitli cihazlar, belirli işlemleri gerçekleştiren kişiler (kasiyerler, operatörler, kuaförler, satış görevlileri), iletişim hatları, arabalar, vinçler, tamir ekipleri, demiryolu rayları, benzin istasyonları vb. tarafından oynanabilir.

Kuyruk sistemleri tek kanallı veya çok kanallı olabilir.

Her QS, çoğunlukla düzenli olarak değil, rastgele zamanlarda sistem girişine gelen belirli bir uygulama (gereksinim) akışına hizmet vermek (yerine getirmek) için tasarlanmıştır. Bu durumda uygulamaların hizmeti de sabit, önceden bilinen bir süre değil, birçok rastgele, bazen bizim tarafımızdan bilinmeyen nedenlere bağlı olan rastgele bir süre sürer. İsteğe hizmet verildikten sonra kanal serbest bırakılır ve bir sonraki isteği almaya hazır olur. İstek akışının rastgele doğası ve hizmet verme süresi, QS'nin eşit olmayan bir şekilde yüklenmesine yol açar: diğer zamanlarda, hizmet verilmeyen uygulamalar QS'nin girişinde birikebilir, bu da QS'nin aşırı yüklenmesine neden olur ve bazen QS girişinde boş kanallar var, hiçbir uygulama olmayacak, bu da QS'nin yetersiz yüklenmesine yol açıyor, yani. kanallarının boşluğuna. QS girişinde biriken uygulamalar ya kuyruğa "katılır" ya da kuyrukta daha fazla kalmanın imkansızlığı nedeniyle QS'yi hizmetsiz bırakır.

Tüketicinin tüm uygulama seti veya bazı kaynakları (örneğin, CMO'nun birim zaman başına getirdiği ortalama gelir vb.) olarak anlaşıldığı "CMO - tüketici" çiftinin işleyişinin etkinliğinin göstergeleri. ). Bu gösterge grubu, hizmet uygulamalarından elde edilen gelirlerin bir kısmı ile hizmet maliyetlerinin aynı birimlerde ölçüldüğü durumlarda faydalı olmaktadır. Bu göstergeler genellikle çok spesifik bir yapıya sahiptir ve QS'nin özelliklerine, sunulan taleplere ve hizmet disiplinine göre belirlenir.

14. Olasılıklı durumlar için dinamik denklemler (Kolmogorov denklemleri). Durumların olasılıklarını sınırlamak.

Kolmogorov-Chapman denkleminin s = 0'daki s'ye göre resmi olarak türevini alarak doğrudan Kolmogorov denklemini elde ederiz:

Kolmogorov-Chapman denkleminin t = 0'da t'ye göre resmi olarak türevini alarak ters Kolmogorov denklemini elde ederiz.

Sonsuz boyutlu uzaylar için operatörün artık zorunlu olarak sürekli olmadığı ve her yerde, örneğin dağılım uzayında diferansiyel bir operatör olarak tanımlanamayabileceği vurgulanmalıdır.

Eğer S sisteminin durum sayısı sonluysa ve her durumdan (belli sayıda adımla) diğer duruma geçmek mümkün görünüyorsa, durumların sınırlayıcı olasılıkları mevcuttur ve başlangıç ​​durumuna bağlı değildir. sistemin.

İncirde. belirtilen koşulu karşılayan durumların ve geçişlerin bir grafiği gösterilir: sistem er ya da geç herhangi bir durumdan başka bir duruma geçebilir. Şekildeki grafikte 4-3 okunun yönü değiştiğinde bu durum karşılanmayacak, tam tersi yönde olacaktır.

Belirtilen koşulun karşılandığını ve dolayısıyla sınırlayıcı olasılıkların mevcut olduğunu varsayalım:

Sınırlayıcı olasılıklar, durumların olasılıklarıyla aynı harflerle gösterilecektir; ancak bunlar değişkenleri (zamanın fonksiyonları) değil, sayıları ifade eder.

Durumların sınırlayıcı olasılıklarının toplamının birliğe ulaşması gerektiği açıktır: Sonuç olarak, sistemde belirli bir sınırlayıcı durağan rejim kurulur: sistem kendi durumlarını rastgele değiştirse bile, bu durumların her birinin olasılığı değişmez. zamana bağlıdır ve her biri sabit bir olasılıkla meydana gelir; bu da sistemin bu durumda kaldığı ortalama bağıl süredir.

15. Ölüm ve üreme süreci.

Markov'un sürekli zamanlı ölüm ve üreme süreci adını verdiğimiz, ancak negatif olmayan tamsayı değerleri alabilen bir süreç; Bu süreçteki değişiklikler t zamanındaki herhangi bir noktada meydana gelebileceği gibi, herhangi bir zamanda bir birim artabilir veya değişmeden kalabilir.

Yeniden üretim akışları λi(t), X(t) fonksiyonunda bir artışa yol açan Poisson akışları olarak adlandırılacaktır. Buna göre μi(t), X(t) fonksiyonunda azalmaya yol açan ölüm akışlarıdır.

Grafikten Kolmogorov denklemini oluşturalım:

Akış sonlu durum ise:

Sınırlı sayıda durumla ölüm ve üreme süreci için Kolmogorov'un denklem sistemi şu şekildedir:

Saf yeniden üretim süreci, tüm ölüm akışlarının yoğunluğunun sıfıra eşit olduğu bir ölüm ve yeniden üretim sürecidir.

Saf ölüm süreci, tüm yeniden üretim akışlarının yoğunluğunun sıfıra eşit olduğu bir ölüm ve yeniden üretim sürecidir.

16. Arızalı kuyruk sistemleri.

Kuyruk teorisi çerçevesinde ele alınan problemlerin en basiti, arızalı veya kayıplı tek kanallı QS modelidir.

Bu durumda kanal sayısının 1 () olduğunu belirtmekte fayda var. Bu kanal, yoğunluğu eşit olan bir Poisson istek akışı alır. Zaman yoğunluğu etkiler:

Şu anda ücretsiz olmayan bir kanala başvuru gelmesi durumunda reddedilir ve artık sistemde listelenmez. Uygulamaların servisi, dağılımı üstel yasaya uygun olarak aşağıdaki parametreye göre uygulanan rastgele bir zamanda gerçekleştirilir:

17. Beklemeli kuyruk sistemleri.

Kanal meşgul olduğunda alınan istek sıraya alınır ve hizmet beklenir.

Sınırlı kuyruk uzunluğuna sahip sistem. Öncelikle kuyruktaki yer sayısının m ile sınırlı olduğunu varsayalım, yani kuyrukta zaten m uygulamanın olduğu bir zamanda bir uygulama gelirse, sistemi hizmetsiz bırakır. Gelecekte m'yi sonsuza yönlendirerek, kuyruk uzunluğu kısıtlaması olmaksızın tek kanallı bir QS'nin özelliklerini elde edeceğiz.

QS'nin durumlarını sistemdeki uygulamaların (hem hizmet verilen hem de hizmet bekleyen) sayısına göre numaralandıracağız:

— kanal ücretsizdir;

— kanal meşgul, sıra yok;

— kanal meşgul, sırada bir istek var;

—kanal meşgul, k - 1 istek sırada;

— kanal meşgul, tonlarca başvuru sırada.

18. Çatışma koşullarında karar verme yöntemleri. Matris oyunları. Saf ve karma strateji oyunları.

Bir matris oyunu, iki oyunculu sonlu sıfır toplamlı bir oyundur; burada oyuncu 1'in getirisi bir matris şeklinde belirlenir (matrisin satırı, oyuncu 2'nin uygulanan stratejisinin sayısına karşılık gelir, sütun buna karşılık gelir). Oyuncu 2'nin uyguladığı strateji sayısına göre; matrisin satır ve sütununun kesişiminde, uygulanan stratejilere uygun olarak Oyuncu 1'in getirisi bulunur).

Matris oyunları için bunlardan herhangi birinin bir çözümü olduğu ve oyunun bir doğrusal programlama problemine indirgenmesiyle kolaylıkla bulunabileceği kanıtlanmıştır.

İki oyunculu sıfır toplamlı bir matris oyunu, aşağıdaki soyut iki oyunculu oyun olarak düşünülebilir.

Birinci oyuncunun m stratejisi i = 1,2,...,m, ikinci oyuncunun n stratejisi j = 1,2,...,n'dir. Her bir (i,j) strateji çifti, ilk oyuncunun i'inci stratejisini kabul etmesi durumunda oyuncu 1'in, oyuncu 2'nin pahasına kazancını ve 2'nin j'inci stratejisini kabul ettiği bir aij sayısıyla ilişkilidir.

Her oyuncu bir hamle yapar: 1. oyuncu i'inci stratejisini (i=), 2 - j'inci stratejisini (j=) seçer, bundan sonra oyuncu 1, oyuncu 2'nin pahasına aij getirisini alır (eğer aij ise)

i oyuncusunun her stratejisi=; j = genellikle saf strateji olarak adlandırılır.

Tanım. Bir oyuncunun karma stratejisi, saf stratejilerini kullanma olasılıklarının tam kümesidir.

Dolayısıyla, eğer oyuncu 1'in m saf stratejisi 1,2,...,m varsa, o zaman onun karma stratejisi x, ilişkileri sağlayan x = (x1,..., xm) sayılarının bir kümesidir.

xi³ 0 (i= 1,m), =1.

Benzer şekilde, n saf stratejisi olan 2. oyuncu için karma strateji y sayılar kümesidir

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

Bir oyuncunun her defasında bir saf stratejiyi kullanması diğerinin kullanımını dışladığından, saf stratejiler uyumsuz olaylardır. Üstelik bunlar mümkün olan tek olaylardır.

Saf strateji, karma stratejinin özel bir durumudur. Aslında, eğer bir karma stratejide herhangi bir i-inci saf strateji 1 olasılıkla uygulanırsa, o zaman diğer tüm saf stratejiler uygulanmaz. Ve bu i'inci saf strateji, karma stratejinin özel bir durumudur. Gizliliği korumak için her oyuncu, diğer oyuncunun tercihlerinden bağımsız olarak kendi stratejilerini uygular.

19. Bir matris oyununu çözmek için geometrik yöntem.

2xn veya nx2 boyutundaki oyunların çözümü net bir geometrik yoruma olanak tanır. Bu tür oyunlar grafiksel olarak çözülebilir.

Apsis ekseni boyunca XY düzleminde tek bir A1A2 parçasını çiziyoruz (Şekil 5.1). Parçanın her noktasına bazı karma strateji U = (u1, u2) atayalım. Ayrıca, bu parçanın bazı ara noktalarından U'ya kadar olan mesafe, A1 stratejisini seçme olasılığı u1'dir, sol uca olan mesafe ise A2 stratejisini seçme olasılığı u2'dir. A1 noktası saf strateji A1'e, A2 noktası ise saf strateji A2'ye karşılık gelir.

A1 ve A2 noktalarında dikeyleri yeniden oluşturacağız ve oyuncuların kazançlarını bunların üzerine koyacağız. İlk dikeyde (OY eksenine denk gelen), A oyuncusunun A1 stratejisini kullanırken, ikincisinde ise A2 stratejisini kullanırken kazandığı getiriyi gösteriyoruz. A oyuncusu A1 stratejisini kullanıyorsa, B oyuncusunun B1 stratejisiyle elde ettiği getiri 2'ye, B2 stratejisiyle ise 5'e eşittir. OY eksenindeki 2 ve 5 sayıları B1 ve B2 noktalarına karşılık gelir. Benzer şekilde, ikinci dikmede B"1 ve B"2 noktalarını buluyoruz (kazançlar 6 ve 4).

B1 ve B"1, B2 ve B"2 noktalarını birleştirerek iki düz çizgi elde ederiz; OX eksenine olan mesafe, ilgili stratejilerin herhangi bir kombinasyonu için ortalama getiriyi belirler.

Örneğin, B1B"1 segmentindeki herhangi bir noktadan OX eksenine olan mesafe, A1 ve A2 stratejileri (u1 ve u2 olasılıklarıyla) ve B oyuncusunun B1 stratejisinin herhangi bir kombinasyonu için A oyuncusunun ortalama getirisini belirler.

B1MB"2 kesikli çizgisine ait noktaların ordinatları, A oyuncusunun herhangi bir karma strateji kullandığında minimum getirisini belirler. Bu minimum değer M noktasında en büyüktür, dolayısıyla bu nokta optimal stratejiye karşılık gelir U* = ( ,) ve ordinatı oyunun maliyetine eşittir v .

M noktasının koordinatlarını B1B"1 ve B2B"2 doğrularının kesişme noktasının koordinatları olarak buluyoruz.

Bunu yapmak için çizgi denklemlerini bilmeniz gerekir. İki noktadan geçen bir çizginin denklemi formülünü kullanarak bu tür denklemler oluşturabilirsiniz:

Problemimiz için düz çizgi denklemleri oluşturalım.

B1B"1 doğrusu: = veya y = 4x + 2.

Doğrudan B2B"2: = veya y = -x + 5.

Sistemi elde ederiz: y = 4x + 2,

Hadi çözelim: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Böylece U = (2/5, 3/5), v = 22/5 olur.

20. Bi-matris oyunları.

Bimatris oyunu, her oyuncunun getirilerinin karşılık gelen oyuncu için ayrı ayrı matrislerle belirlendiği, toplamı sıfır olmayan iki oyuncudan oluşan sonlu bir oyundur (her matriste bir satır, oyuncu 1'in stratejisine karşılık gelir, bir sütun Oyuncu 2'nin stratejisine karşılık gelir, ilk matriste satır ve sütunun kesişiminde oyuncunun getirisi 1, ikinci matriste ise oyuncu 2'nin getirisi bulunur.)

Bimatris oyunları için de optimal oyuncu davranışı teorisi geliştirilmiştir, ancak bu tür oyunları çözmek sıradan matris oyunlarına göre daha zordur.

21. İstatistik oyunları. Tam ve kısmi belirsizlik koşullarında karar verme ilkeleri ve kriterleri.

Yöneylem araştırmasında üç tür belirsizliği ayırt etmek yaygındır:

hedeflerin belirsizliği;

çevre ve bu olguya etki eden faktörler hakkındaki bilgilerimizin belirsizliği (doğanın belirsizliği);

Aktif veya pasif bir ortağın veya düşmanın eylemlerinin belirsizliği.

Yukarıdaki sınıflandırmada belirsizlik türü, matematiksel modelin bir veya başka unsuru açısından ele alınmaktadır. Örneğin, hedeflerin belirsizliği, bireysel kriterlerin veya faydalı etkinin tüm vektörünün seçiminde bir görev belirlerken yansıtılır.

Öte yandan, diğer iki tür belirsizlik esas olarak kısıt denklemlerinin amaç fonksiyonunun formülasyonunu ve karar yöntemini etkiler. Elbette yukarıdaki ifade, herhangi bir sınıflandırma gibi oldukça koşulludur. Bunu yalnızca karar verme sürecinde akılda tutulması gereken belirsizliklerin bazı diğer özelliklerini vurgulamak amacıyla sunuyoruz.

Mesele şu ki, yukarıda tartışılan belirsizliklerin sınıflandırılmasına ek olarak, bunların türlerinin (veya "cinslerinin") rastgelelikle olan ilişkileri açısından dikkate alınması gerekir.

Bu temelde, bilinmeyen faktörler istatistiksel olarak kararlı olduğunda ve bu nedenle olasılık teorisinin sıradan nesnelerini - rastgele değişkenleri (veya rastgele fonksiyonlar, olaylar vb.) temsil ettiğinde stokastik (olasılıksal) belirsizlik ayırt edilebilir. Bu durumda problem belirlenirken gerekli tüm istatistiksel özelliklerin (dağılım yasaları ve bunların parametreleri) bilinmesi veya belirlenmesi gerekir.

Bu tür görevlerin bir örneği, özellikle her türlü ekipmanın bakım ve onarımı için bir sistem, inceltmelerin organize edilmesi için bir sistem vb. olabilir.

Diğer bir aşırı durum, stokastik stabiliteye ilişkin hiçbir varsayımın bulunmadığı, stokastik olmayan tipteki belirsizlik (E.S. Ventzel'in ifadesiyle - “kötü belirsizlik”) olabilir. Son olarak, rastgele değişkenlerin dağılım yasalarına ilişkin bazı hipotezlere dayanarak karar verildiğinde, orta düzeyde bir belirsizlikten bahsedebiliriz. Aynı zamanda karar vericinin, sonuçları ile gerçek koşullar arasındaki tutarsızlık tehlikesini de aklında tutması gerekir. Bu uyumsuzluk riski, risk katsayıları kullanılarak resmileştirilir.

Risk koşullarında karar verme aşağıdaki kriterlerden birine dayanabilir:

beklenen değer kriteri;

beklenen değer ve varyansın kombinasyonları;

bilinen limit seviyesi;

gelecekte gerçekleşmesi en muhtemel olay.

Operasyon Tek bir planla birleştirilen ve belirli bir hedefe ulaşmayı amaçlayan her türlü olaya (eylemler sistemine) denir. Her zaman bir operasyon var kontrollü olay, yani Organizasyonunu karakterize eden belirli parametrelerin nasıl seçileceğine karar vermek mümkündür. Bu parametreler denir kontrol değişkenleri.

Bu tür değişkenlerin herhangi bir özel seçimine denir karar. Kararlar başarılı ve başarısız, makul ve mantıksız olabilir. En uygun Bazı kriterlere göre diğerlerine göre tercih edilen çözümleri adlandırın.

Yöneylem araştırmasının amacı, birden fazla olabilecek optimal çözümlerin ön niceliksel gerekçelendirilmesidir. Nihai karar seçimi yöneylem araştırmasının kapsamının ötesine geçer ve karar teorisi adı verilen yöntemle yapılır.

Herhangi bir yöneylem araştırması görevinin başlangıçta “disiplin altına alma” koşulları vardır; bu tür ilk veriler en başından sabittir ve ihlal edilemez. Birlikte ele alındıklarında olası çözümler kümesi olarak adlandırılan kümeyi oluştururlar.

Farklı çözümleri etkililik açısından karşılaştırmak için niceliksel bir kritere sahip olmanız gerekir. performans göstergesi(veya amaç fonksiyonu). Bu gösterge operasyonun hedef yönelimini yansıtacak şekilde seçilmiştir.

Çoğunlukla operasyona rastgele faktörlerin etkisi eşlik eder. Daha sonra verimliliğin bir göstergesi olarak optimize etmek istenen değerin kendisi değil, ortalama değeri (veya matematiksel beklentisi) alınır.

Bazen rastgele faktörlerin eşlik ettiği bir operasyon böyle bir amacın peşinde koşar A ya tamamen başarılabilir ya da hiç başarılamaz (“evet-hayır” gibi). Daha sonra bu hedefe ulaşma olasılığı, verimliliğin bir göstergesi olarak seçilir. P(A). (Eğer P(A) = 0 veya 1 ise sibernetikte bilinen “kara kutu” problemine geliyoruz.)

Yanlış performans göstergesini seçmek çok tehlikelidir. Başarısız seçilmiş bir kritere göre düzenlenen operasyonlar, haksız maliyetlere ve kayıplara yol açabilir. (Örneğin, bir işletmenin ekonomik faaliyetini değerlendirmede ana kriter olarak “şaft”.)

1.3. Yöneylem araştırması probleminin genel ifadesi

Yöneylem araştırması sorunları iki kategoriye ayrılır: a) ileri ve b) geriye doğru.

Doğrudan görevlerşu soruyu cevaplayın: verimlilik göstergesi neye eşit olacak? Z, eğer verilen koşullar altındaysa sen  e bazı kararlar verilecek X  X. Böyle bir sorunu çözmek için, verimlilik göstergesinin belirli koşullar ve bir çözüm aracılığıyla ifade edilmesine olanak tanıyan bir matematiksel model oluşturulur:

Nerede
belirtilen faktörler (başlangıç ​​verileri),

kontrol değişkenleri (karar),

Z– verimlilik göstergesi (hedef işlevi),

F– değişkenler arasındaki fonksiyonel bağımlılık.

Bu bağımlılık farklı modellerde farklı şekilde ifade edilmektedir. Arasındaki bağımlılık Ve genellikle kısıtlamalar şeklinde ifade edilir.

Bağımlılığın türü ise F biliniyorsa gösterge Z doğrudan yerine koyma yoluyla bulunur Ve bu işlevselliğe.

Ters problemlerşu soruyu cevapla: bu koşullar altında nasıl bir çözüm seç
böylece performans göstergesi Z maksimuma (minimum) döndü. Bu probleme çözüm optimizasyon problemi denir.

Doğrudan sorunun çözülmesine izin verin, yani. operasyon modeli belirtildi ve bağımlılık türü belirtildi Fünlü. Daha sonra ters problem (yani optimizasyon problemi) aşağıdaki gibi formüle edilebilir.

Bulmak gerek böyle bir karar
verimlilik göstergesi nerede Z = tercih:

Bu formül şu şekilde okunur: Z optimal bir değer var
olası çözümler kümesinde yer alan tüm çözümleri devraldı X.

Verimlilik göstergesinin ekstremumunu bulma yöntemi Z ve ilgili optimal çözüm her zaman fonksiyonun özelliklerine göre seçilmelidir F ve çözüme uygulanan kısıtlamaların türü. (Örneğin klasik bir doğrusal programlama problemi.)

Yöneylem Araştırması Problemi

Giriş…………………………………………………………………………………3

1. Yöneylem araştırmasının temel kavramları ve tanımları……..……..5

2. Yöneylem araştırması probleminin genel ifadesi…………..…………6

Sonuç………………………………………………………………………..13

Edebiyat……………………………………………………………………………………14

giriiş

Yöneylem araştırması -Çeşitli organizasyonel sistemlerin en etkili yönetimi için yöntemlerin geliştirilmesi ve pratik uygulamasıyla ilgilenen bilimsel bir disiplin.

Herhangi bir sistemin yönetimi belirli yasalara uyan bir süreç olarak uygulanır. Onların bilgisi bu sürecin uygulanması için gerekli ve yeterli koşulların belirlenmesine yardımcı olur. Bunu yapmak için, süreci ve dış koşulları karakterize eden tüm parametrelerin sayısallaştırılması ve ölçülmesi gerekir. Bu nedenle yöneylem araştırmasının amacı Alınan kararların niceliksel gerekçesi Yönetim organizasyonu hakkında.

Belirli bir yönetim problemini çözerken yöneylem araştırması yöntemlerinin kullanımı şunları içerir:

Karmaşık durumlarda veya belirsizlik koşullarında karar verme problemlerine yönelik ekonomik ve matematiksel modellerin oluşturulması;

Daha sonra karar almayı belirleyen ilişkilerin incelenmesi ve belirli bir eylem planının avantajının değerlendirilmesine olanak tanıyan performans kriterlerinin oluşturulması.

Spesifikliğini yansıtan yöneylem araştırması görevlerine örnekler aşağıdaki görevleri içerir.

Görev 1. Üretilen ürünlerin yüksek kalitesini sağlamak için tesiste bir numune alma kontrol sistemi düzenlenir. Gerekli kaliteyi minimum maliyetle sağlamak için bu tür organizasyon biçimlerini seçmek gerekir - örneğin, kontrol partilerinin boyutlarını atamak, kontrol işlemlerinin sırasını belirtmek, reddetme kurallarını belirlemek -.

Görev 2. Belirli bir sezonluk ürün grubunu satmak için geçici perakende satış mağazalarından oluşan bir ağ oluşturulur. Satışın maksimum ekonomik verimliliğini sağlamak için ağ parametrelerini (nokta sayısı, konumları, personel sayısı) seçmek gerekir.

Görev 3. Belirli bir tarihe kadar, belirli hastalıkları tanımlamak için nüfusun bir grubunun toplu tıbbi muayenesinin yapılması gerekmektedir. Sınav için malzeme, ekipman ve personel tahsis edilmiştir. Hastaların mümkün olan en büyük yüzdesini belirlemek için tıbbi mevkilerin sayısını, konumlarını, türlerini ve test sayısını belirlemek için böyle bir muayene planı geliştirmek gereklidir.

Kaynak kullanımı, karışımlar, kapasite kullanımı, malzemelerin kesilmesi, nakliye sorunu vb. ile ilgili sorunların da dikkate alınması gerekir; bunlar bazı durumlarda çözüm bulmanın gerekli olduğu durumlardır. performans kriteri(örneğin kâr, gelir, kaynak maliyetleri vb.) maksimum veya minimum değer alır.

Verilen görevler farklı uygulama alanlarıyla ilgilidir ancak ortak özelliklere sahiptirler: her durumda bazı konulardan bahsediyoruz. kontrollü olay (çalışma), belli bir şeyin peşinden koşmak hedef. Görev 1'de - bu, ürünlerin kalitesini sağlamak amacıyla numune alma kontrolünün organizasyonudur; görev 2'de - sezonluk satışları gerçekleştirmek amacıyla geçici perakende satış mağazalarının düzenlenmesi; görev 3'te - vakaların yüzdesini belirlemek için toplu tıbbi muayene.

Her görev bazı içerir koşullar bu etkinliğin düzenlenmesi, çerçevesinde alınması gereken çözüm -öyle ki olay bir miktar fayda sağlıyor. Her görevde operasyonu gerçekleştirme koşulları elimizdeki araçlar, zaman, ekipman, teknolojidir ve Görev 1'deki çözüm, kontrol biçimini seçmektir - kontrol partilerinin boyutu, ret kuralları; Görev 2'de - yerleştirme noktası sayısı ve personel sayısının seçiminde; Görev 3'te - tıbbi görev sayısını, test türünü ve sayısını seçerken.

1. Yöneylem araştırmasının temel kavramları ve tanımları

Operasyon- Bir hedefe ulaşmayı amaçlayan herhangi bir kontrollü olay. Operasyonun sonucu, uygulama yöntemine, organizasyonuna, aksi takdirde belirli parametrelerin seçimine bağlıdır.

Herhangi bir özel parametre seçimine denir karar.

En uygunşu ya da bu nedenle diğerlerine tercih edilen çözümleri düşünün. Bu yüzden ana görev yöneylem araştırması ön nicelikseldir optimal çözümlerin gerekçelendirilmesi.

Not 1. Sorunun ifadesine dikkat edilmelidir: Karar vermek Yöneylem araştırmasının kapsamının ötesine geçer ve matematiksel olarak gerekçelendirilenler dışındaki hususları dikkate alabilecek sorumlu kişi veya kişi grubunun sorumluluğundadır.

Not2. Bazı yöneylem araştırması problemlerinde en uygun çözüm, bazı verimlilik kriterlerinin dikkate alındığı çözümdür.

maksimum veya minimum değer, o zaman diğer görevlerde bu hiç gerekli değildir. Bu nedenle, görev 2'de, ortalama müşteri hizmet süresi örneğin 5 dakikayı geçmeyecek ve herhangi bir zamanda ortalama kuyruk uzunluğu artık olmayacak şekilde en uygun perakende satış noktası ve personel sayısı düşünülebilir. 3 kişiden fazla.

Nicel araştırma yöntemlerini uygulamak için aşağıdakileri oluşturmak gerekir: Operasyonun matematiksel modeli. Bir model oluştururken, işlem kural olarak basitleştirilir, şematize edilir ve işlem şeması şu veya bu matematiksel aparat kullanılarak açıklanır.

Modeli operasyonlar - bu, matematiksel aygıtlar (çeşitli işlevler, denklemler, denklem ve eşitsizlik sistemleri vb.) kullanılarak yapılan işlemin oldukça doğru bir açıklamasıdır. Bir operasyonun modelini hazırlamak, açıklanan olgunun özünün anlaşılmasını ve matematiksel aparatın bilinmesini gerektirir.

Operasyon verimliliği - göreve uyarlanabilirlik derecesi niceliksel olarak bir verimlilik kriteri (hedef fonksiyon) şeklinde ifade edilir. Örneğin, kaynak kullanımı probleminde verimlilik kriteri, maksimize edilmesi gereken, üretilen ürünlerin satışından elde edilen kârdır; ulaştırma probleminde ise, minimuma indirilmesi gereken, malların tedarikçilerden tüketicilere taşınmasına ilişkin toplam maliyetler. . Etkililik kriterinin seçimi çalışmanın pratik değerini belirler. (Yanlış seçilen bir kriter zararlı olabilir, çünkü bu tür bir verimlilik kriterine göre düzenlenen operasyonlar bazen haksız maliyetlere yol açabilmektedir.)

2. Yöneylem araştırması probleminin genel ifadesi

Yöneylem araştırması problemlerinin modellerini oluşturma metodolojisini anlamak önemlidir. Operasyonun açıklamasında yer alan tüm faktörler iki gruba ayrılabilir:

sabit faktörler(çalışma koşulları), etkileyemeyeceğimiz. Bunları şu şekilde belirtelim a1, a2, ... ;

bağımlı faktörler(çözümün unsurları) X 1, x2, ...; bunu belirli sınırlar dahilinde kendi takdirimize bağlı olarak seçebiliriz.

Örneğin, kaynakları kullanma probleminde, sabit faktörler, her türün kaynak rezervlerini, her türün çıktı birimi başına her türün hammadde tüketimini belirleyen üretim matrisini içermelidir. Çözümün unsurları – her ürün türü için bir üretim planı.

Bazı işlevler tarafından ifade edilen bir performans kriteri hedef, her iki grubun faktörlerine bağlı olduğundan amaç fonksiyonu Zşeklinde yazılabilir

z= F (x1, x2, ..., α1, α2, ...)

Yöneylem araştırmasının tüm modelleri, operasyonun niteliğine ve özelliklerine, çözülen problemlerin niteliğine ve kullanılan matematiksel yöntemlerin özelliklerine bağlı olarak sınıflandırılabilir.

Her şeyden önce şunu belirtmek gerekir ki, büyük optimizasyon modelleri sınıfı. Bu tür sorunlar, başta ekonomik sistemler olmak üzere karmaşık sistemlerin planlanması ve yönetimini optimize etmeye çalışırken ortaya çıkar. Optimizasyon problemi genel biçimde formüle edilebilir: x1 değişkenlerini bul, x2, ..., x N , eşitsizlik sisteminin sağlanması (denklemler)

G Ben (x1, x2, x3,..., X N )<= B Ben , ben = 1, 2,..., N (0.1)

Ve amaç fonksiyonunu maksimuma (veya minimuma) çevirmek, yani.

z= F (x1, x2, ..., X N ) - M ah (m içinde ) (0.2)

(Varsa değişkenlerin negatif olmama koşulları kısıtlamalara (0,1) dahil edilmiştir)

Yöneylem araştırması için tipik olan başka bir problemi ele alalım: klasik tüketim problemi, ekonomik analizde büyük önem taşımaktadır.

Olsun P miktarları (doğal birimler halinde) mal ve hizmet türleri x1, x2, ..., X N, buna göre fiyatlarla P 1, P 2, ..., P N bir birim için. Bu mal ve hizmetlerin toplam maliyeti ∑ P Ben X Ben .

Tüketim düzeyi Z bazı işlevlerle ifade edilebilir z= F (x1, x2, ..., X N ) ,isminde fayda fonksiyonu. Böyle bir dizi mal ve hizmet bulmak gerekiyor x1, x2, ..., X N verildi gelir miktarı I, ile Maksimum tüketim düzeyinin sağlanması, onlar.

z= F (x1, x2, ..., X N ) - M Ah (0.3)

verilen

∑ P Ben X Ben <= BEN (0.4)

X Ben >= 0 ( Ben = 1, 2,..., N ) (0.5)

Bu sorunun fiyatlara bağlı çözümleri P 1, P 2, ..., P N ve gelir miktarı BEN, arandı talep fonksiyonları.

Dikkate alınan tüketim probleminin (0.3)-(0.5) ve diğerlerinin, fonksiyonun ekstremumunu belirlemek için yukarıda formüle edilen genel problemin (0.1)-(0.2) özel bir durumu olduğu açıktır. P belirli kısıtlamalar altındaki değişkenler; için görev koşullu ekstremum.

Fonksiyonların olduğu durumlarda F Ve G Ben(0.1)-(0.2) probleminde en az iki kez türevlenebilirse şunu kullanabiliriz: klasik optimizasyon yöntemleri. Bununla birlikte, i değişkenli bir fonksiyonun koşullu ekstremumunu belirleme görevi teknik olarak çok zor olduğundan, bu yöntemlerin yöneylem araştırmasında kullanımı çok sınırlıdır: yöntem, yerel ekstremumun belirlenmesini mümkün kılar ve çok boyutlu olması nedeniyle Maksimum (veya minimum) değerini (küresel ekstremum) belirleyen fonksiyon, özellikle bu ekstremumun çözüm bölgesinin sınırında mümkün olması nedeniyle çok emek yoğun olabilir. Geçerli argüman değerleri kümesi ayrıksa veya işlev varsa klasik yöntemler hiç çalışmaz. Z bir tablo halinde verilmektedir. Bu durumlarda problemi çözmek için (0.1)-(0.2) yöntemleri kullanılır. matematiksel programlama.

Performans kriteri ise z= F (x1, x2, ..., X N ) (0.2) doğrusal bir işlevi temsil eder ve işlevler G Ben (x1, x2, x3,..., X N ) Kısıtlar sisteminde (0.1) de doğrusaldır, o zaman böyle bir problem bir problemdir doğrusal programlama.İçeriğe göre çözümlerinin tamsayı olması gerekiyorsa, bu sorun tamsayılı doğrusal programlama. Verimlilik kriteri ve/veya kısıtlama sistemi doğrusal olmayan fonksiyonlarla belirtiliyorsa, o zaman sorunla karşı karşıyayız demektir. Doğrusal olmayan programlama.Özellikle belirtilen fonksiyonlar dışbükeylik özelliklerine sahipse, ortaya çıkan sorun bir sorundur dışbükey programlama.

Bir matematiksel programlama probleminde bir zaman değişkeni varsa ve verimlilik kriteri (0.2) açıkça değişkenlerin bir fonksiyonu olarak değil, dolaylı olarak - zaman içindeki işlemlerin akışını tanımlayan denklemler yoluyla ifade ediliyorsa, o zaman böyle bir problem bir problemdir dinamik program.

Verimlilik kriteri (0.2) ve kısıtlama sistemi (0.1) formun işlevleriyle belirtilirse İle*( X 1^α 1 )*( X 2^α 2 )...( X N ^α N ) , o zaman bir sorunumuz var geometrik programlama. Eğer işlevler F ve/veya G Ben(0.2) ve (0.1) ifadelerinde parametrelere bağlıdır, o zaman sorunu elde ederiz parametrik programlama, eğer bu işlevler doğası gereği rastgele ise, görev Stokastik programlama.Çözüm seçeneklerinin çok fazla olması nedeniyle algoritmik olarak tam optimumu bulmak mümkün değilse, yöntemlere başvurunuz. sezgisel programlama, Baktığınız seçeneklerin sayısını önemli ölçüde azaltmanıza ve optimal değilse bile pratik açıdan tatmin edici, oldukça iyi bir çözüm bulmanıza olanak tanır.

Listelenen matematiksel programlama yöntemlerinden en yaygın ve gelişmiş olanı doğrusal programlamadır. Çok çeşitli yöneylem araştırması görevlerini kapsar.

Ağ planlama ve yönetim görevleri Büyük bir operasyon kompleksinin (işlerin) tamamlanma tarihleri ​​ile kompleksin tüm operasyonlarının başlangıç ​​​​zamanları arasındaki ilişkiyi düşünün. Bu görevler, bir dizi operasyonun minimum süresini, maliyet değerlerinin optimal oranını ve bunların uygulanma zamanlamasını bulmaktan oluşur.

Kuyruk sorunları uygulama kuyrukları veya gereksinimleri olan hizmet sistemlerinin incelenmesine ve analizine ayrılmıştır ve sistemlerin performans göstergelerinin, bunların optimal özelliklerinin, örneğin hizmet kanallarının sayısının, hizmet süresinin vb. belirlenmesinden oluşur.

Envanter yönetimi görevleri stok seviyesinin (sipariş noktası) ve sipariş boyutunun optimal değerlerini bulmaktan oluşur. Bu tür görevlerin özelliği, stok seviyesinin artmasıyla birlikte bir yandan bunları depolama maliyetlerinin artması, diğer yandan depolanan üründeki olası bir kıtlıktan kaynaklanan kayıpların azalmasıdır.

Kaynak Tahsisi Sorunları Sınırlı mevcut kaynaklarla gerçekleştirilmesi gereken belirli bir dizi operasyon (iş) sırasında ortaya çıkar ve kaynakların operasyonlar arasında en uygun dağılımını veya operasyonların bileşimini bulmak gerekir.

Ekipman onarımı ve değiştirme görevleri ekipmanın aşınması ve yıpranması ve zaman içinde değiştirilmesi ihtiyacı nedeniyle geçerlidir. Görevler, optimum zamanlamanın, önleyici onarım ve denetimlerin sayısının ve ayrıca ekipmanın ne zaman modernleştirilmiş ekipmanla değiştirileceğinin belirlenmesine kadar uzanır.

Görevleri zamanlama (zamanlama)çeşitli ekipman türlerinde en uygun işlem sırasının (örneğin parçaların işlenmesi) belirlenmesinden oluşur.

Planlama ve yerleştirme görevleri mevcut nesnelerle ve birbirleriyle etkileşimlerini dikkate alarak yeni nesnelerin en uygun sayısını ve konumunu belirlemeyi içerir.

Rota seçimi sorunları veya ağ ulaşım ve iletişim sistemlerindeki çeşitli problemlerin incelenmesinde en sık karşılaşılan problemler ve en ekonomik güzergahların belirlenmesinden ibarettir.

Yöneylem araştırması modelleri arasında, çatışma durumlarında en uygun kararları alma modelleri, oyun Teorisi. Farklı hedefler peşinde koşan iki (veya daha fazla) tarafın çıkarlarının çatıştığı çatışma durumları, ekonomi, hukuk, askeri işler vb. alanlardaki bir dizi durumu içerir. Oyun teorisi problemlerinde, çözüm önerileri geliştirmek gerekir. Çatışmadaki katılımcıların makul davranışları, optimal stratejilerini belirlemek için.

Uygulamada, çoğu durumda, bir operasyonun başarısı tek bir kriterle değil, aynı anda birkaç kriterle değerlendirilir; bunlardan biri maksimuma çıkarılmalı, diğerleri minimuma indirilmelidir. Matematiksel aygıt bazı durumlarda da yararlı olabilir. çok kriterli yöneylem araştırması problemleri, en azından açıkça başarısız olan çözümlerin atılmasına yardımcı olur.

Birbirleriyle çelişenler de dahil olmak üzere (örneğin kâr ve gider) çeşitli kriterler arasından bir amaç fonksiyonu seçmek için, bir öncelik Kriterler. Haydi belirtelim F 1 (x), f 2 (X), ..., F N (X)(Burada X - koşullu argüman). Azalan öncelik sırasına göre sıralansınlar. Belirli koşullara bağlı olarak temel olarak iki seçenek vardır:

Kriter amaç fonksiyonu olarak seçilir F 1 (X), en yüksek önceliğe sahip olan;

Kombinasyon düşünülüyor

F ( X ) = ω 1 * F 1 ( X ) + ω 2 * F 2 ( X ) + …+ ω N * F N ( X ) , (0.6)

Nerede ω 1 , ω 2 , … ω N- bazı katsayılar (ağırlıklar).

Büyüklük F (X) Amaç fonksiyonu olarak tüm kriterleri belirli ölçüde dikkate alan , seçilmiştir.

Kesinlik koşullarında ω Ben- sayılar, F Ben (X)- işlevler. Belirsizlik koşullarında F Ben (X) rastgele ortaya çıkabilir ve bunun yerine F Ben (X) toplamın matematiksel beklentisi (0,6) amaç fonksiyonu olarak dikkate alınmalıdır.

Çok kriterli bir problemi tek verimlilik kriteri (amaç fonksiyonu) olan bir probleme indirgeme girişimi çoğu durumda tatmin edici sonuçlar vermez. Başka bir yaklaşım, kabul edilebilir çözümler kümesinden, diğerlerinden daha düşük olan ve açıkça başarısız olan çözümleri atmayı ("ayırma") içerir. tüm kriterler. Bu işlemin sonucunda sözde etkili(veya " Pareto") kümesi genellikle orijinalinden önemli ölçüde daha küçük olan çözümler. Ve “uzlaşmacı” bir çözümün son seçimi (kural olarak mevcut olmayan tüm kriterlere göre optimal değil, ancak kabul edilebilir bu kriterlere göre) karar verici olan kişiye kalır.

Çözüm

Rus bilim adamları L.V., modern bir matematik aparatının oluşturulmasına ve birçok yöneylem araştırması alanının geliştirilmesine büyük katkı sağladı. Kantorovich, N.P. Buslenko, E.S. Ventzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin ve diğerleri. Akademisyen L.V.'nin rolü özellikle dikkate değerdir. 1939'da kontrplak fabrikası birimlerinin operasyonunu planlamaya başlayan Kantorovich, çeşitli sorunları çözdü: ekipmanın en iyi şekilde yüklenmesi, malzemelerin minimum kayıpla kesilmesi, kargonun çeşitli taşıma türleri arasında dağıtılması vb. L.V. Kantorovich, koşullu olarak ekstrem problemlerin yeni bir sınıfını formüle etti ve bunları çözmek için evrensel bir yöntem önererek uygulamalı matematikte yeni bir yön olan doğrusal programlamanın temelini attı.

Yöneylem araştırmasının oluşumuna ve gelişimine önemli katkılar yabancı bilim adamları R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman ve diğerleri tarafından yapılmıştır.

Yöneylem araştırması yöntemleri, herhangi bir matematiksel yöntem gibi, sorunu her zaman bir dereceye kadar basitleştirir ve kabalaştırır, bazen doğrusal olmayan süreçleri doğrusal modellerle, stokastik sistemleri deterministik olanlarla, dinamik süreçleri statik modellerle vb. yansıtır. Hayat herhangi bir plandan daha zengindir. Bu nedenle yöneylem araştırmasında nicel yöntemlerin önemi ne abartılmalı, ne de başarısız çözüm örneklerine yer verilerek küçümsenmelidir. Bu bağlamda, yaratıcılarından biri olan T. Saaty'nin yöneylem araştırmasının mizahi ve paradoksal tanımını "başka yöntemlerle daha da kötü yanıtlanabilecek pratik sorulara kötü yanıtlar verme sanatı" şeklinde alıntılamak yerinde olacaktır.

Edebiyat

1. Kremer N. Sh., Putko B. A., Trishin I. M., Fridman M. N. Ekonomide operasyon araştırması: Üniversiteler için ders kitabı - M.: UNITI, 2002.

2. Ventzel E.S. Operasyon araştırması. Amaçlar, ilkeler, metodoloji - M.: Nauka, 1980.

3. Görelik V.A., Ushakov I.A. Operasyon araştırması. - Yüksek Lisans: Makine Mühendisliği, 1986.

İÇİNDE. Slinkin

Pedagojik üniversite öğrencileri için ders kitabı

Bilgisayar Bilimleri alanında uzmanlaşmak

Şadrinsk, 2003

Slinkina I.N.

Operasyon araştırması. Eğitimsel ve metodolojik el kitabı. – Shadrinsk: Shadrinsk Devlet Pedagoji Enstitüsü yayınevi, 2002. - 106 s.

Slinkina I.N. – Pedagojik Bilimler Adayı

Ders kitabı Yöneylem Araştırması dersinin teorik kısmını sunmaktadır. “Bilişim” uzmanlığını sürdüren fakültelerin tam zamanlı ve yarı zamanlı öğrencilerine yöneliktir.

© Shadrinsk Devlet Pedagoji Enstitüsü

© Slinkina I.N., 2002

“Yöneylem Araştırması” dersindeki ünitelere yönelik sorular 5

1.1. Yöneylem araştırmasının konusu ve görevleri 7

1.2. Yöneylem araştırmasının temel kavramları ve ilkeleri 8

1.3. İşlemlerin matematiksel modelleri 10

1.4. Doğrusal programlama kavramı 12

1.5. Ekonomik doğrusal programlama problemlerine örnekler. Kaynakların En İyi Kullanımı Problem 13

1.6. Ekonomik doğrusal programlama problemlerine örnekler. Optimum teknolojileri seçme sorunu 15

1.7. Ekonomik doğrusal programlama problemlerine örnekler. Karışım problemi 16

1.8. Ekonomik doğrusal programlama problemlerine örnekler. Taşıma sorunu 17

1.9. Doğrusal programlama problemlerini kaydetmenin temel türleri 19

1.10. 21 dönüşüm yöntemi

1.11. Kanonik forma geçiş 22

1.12. Simetrik kayıt biçimine geçiş 25

2.1. Doğrusal programlama probleminin geometrik yorumu 28

2.2. Doğrusal programlama problemlerini grafiksel yöntemle çözme 29

2.3. Doğrusal programlama problemlerinin çözümlerinin özellikleri 34

2.4. Simpleks yönteminin genel fikri 35

2.5. Simpleks yöntemini kullanarak doğrusal programlama problemlerini çözerken ilk referans planının oluşturulması 36

2.6. Referans planının optimalliğinin işareti. Simpleks tablolar 40

2.7. En kötü durum referans planına geçiş. 44

2.8. Simpleks dönüşümleri 46

2.9. Alternatif optimum (referans planları kümesinin sonsuzluk işareti) 51

2.10. Amaç fonksiyonunun sınırsızlığının işareti 52

2.11. Dejenerasyon kavramı. Simpleks yönteminin monotonluğu ve sonluluğu. Döngü 53

2.12. Simetrik doğrusal programlama problemleri için dualite kavramı 54

3.1. Asimetrik ikili problemler 57

3.2. Ulaştırma probleminin açık ve kapalı modelleri 61

3.3. İlk referans planının oluşturulması. Kuzeybatı Köşesi Kural 63

3.4. İlk referans planının oluşturulması. Minimum eleman kuralı 64

3.5. İlk referans planının oluşturulması. Vogel yöntemi 64

3.6. Potansiyel yöntem 65

3.7. Kapasite kısıtlamaları nedeniyle ulaşım sorunlarının çözülmesi 69

3.8. Ayrık programlama problemlerine örnekler. Konteyner taşıma sorunu. Ödev problemi 71

3.9. Ayrık optimizasyon yöntemlerinin özü 72

3.10. Dışbükey programlama problemi 74

3.11. Lagrange çarpanı yöntemi 75

3.12. Gradyan yöntemleri 77

4.1. Ceza yöntemleri ve bariyer fonksiyonları 78

4.2. Dinamik program. Temel konseptler. Çözüm yöntemlerinin özü 79

4.3. Stokastik programlama. Temel kavramlar 81

4.4. Sıfır toplamlı matris oyunları 83

4.5. Saf ve karma stratejiler ve özellikleri 85

4.6. Saf ve karma stratejilerin özellikleri 88

4.7. Bir matris oyununu ZLP 92'ye düşürmek

4.8. Kuyruk teorisinin sorunları. Kuyruk sistemlerinin sınıflandırılması 94

4.9. Etkinlik akışları 96

4.10. Ölüm ve üreme şeması 97

4.11. Little'ın Formülü 99

4.12. En basit kuyruk sistemleri 101

“Yöneylem Araştırması” dersindeki bloklara yönelik sorular

Blok 1

1. Yöneylem araştırmasının konusu ve amaçları.

2. Yöneylem araştırmasının temel kavram ve ilkeleri.

3. İşlemlerin matematiksel modelleri.

4. Doğrusal programlama kavramı.

5. Ekonomik doğrusal programlama problemlerine örnekler. Görev

6. Ekonomik doğrusal programlama problemlerine örnekler. Optimum teknolojileri seçme sorunu.

7. Ekonomik doğrusal programlama problemlerine örnekler. Karışımlarla ilgili problem.

8. Ekonomik doğrusal programlama problemlerine örnekler. Taşıma sorunu.

9. Doğrusal programlama problemlerinin temel yazım türleri.

10. Dönüşüm yöntemleri.

11. Kanonik forma geçiş.

12. Simetrik kayıt biçimine geçiş.

Blok 2

1. Doğrusal programlama probleminin geometrik yorumu.

2. Doğrusal programlama problemlerini grafiksel yöntemle çözmek.

3. Doğrusal programlama probleminin çözümlerinin özellikleri.

4. Simpleks yönteminin genel fikri.

5. Simpleks yöntemini kullanarak doğrusal programlama problemlerini çözerken ilk referans planının oluşturulması.

6. Referans planının optimalliğinin işareti. Simpleks tablolar.

7. En kötü olmayan referans planına geçiş.

8. Simpleks dönüşümleri.

9. Alternatif optimum (referans planları kümesinin sonsuzluğunun işareti).

10. Amaç fonksiyonunun sınırsızlığının işareti.

11. Dejenerasyon kavramı. Simpleks yönteminin monotonluğu ve sonluluğu. Döngü.

12. Simetrik doğrusal programlama problemleri için dualite kavramı.

Blok 3

1. Asimetrik ikili problemler.

2. Ulaştırma probleminin açık ve kapalı modelleri.

3. Başlangıç ​​referans planının oluşturulması. "Kuzeybatı köşesi" kuralı.

4. Başlangıç ​​referans planının oluşturulması. Minimum eleman kuralı.

5. Başlangıç ​​referans planının oluşturulması. Vogel yöntemi.

6. Potansiyeller yöntemi.

7. Kapasite sınırlamaları olan ulaştırma sorunlarının çözülmesi.

8. Ayrık programlama problemlerine örnekler. Konteyner taşıma sorunu. Atama sorunu.

9. Ayrık optimizasyon yöntemlerinin özü.

10. Dışbükey programlama problemi.

11. Lagrange çarpanı yöntemi.

12. Gradyan yöntemleri.

Blok 4

1. Ceza yöntemi ve bariyer fonksiyonları.

2. Dinamik programlama. Temel konseptler. Çözüm yöntemlerinin özü.

3. Stokastik programlama. Temel konseptler.

4. Sıfır toplamlı matris oyunları.

5. Saf ve karma stratejiler.

6. Saf ve karma stratejilerin özellikleri.

7. Bir matris oyununu PLP'ye indirgemek

8. Kuyruk teorisinin sorunları. Kuyruk sistemlerinin sınıflandırılması.

9. Olay akışları.

10. Ölüm ve üreme şeması.

11. Little'ın formülü.

12. En basit kuyruk sistemleri.

Blok 1.

Yöneylem araştırmasının konusu ve görevleri

Bilim ve teknolojinin mevcut durumu, özellikle bilgisayar hesaplama araçlarının geliştirilmesi ve teorilerin matematiksel olarak doğrulanması, çeşitli bilim dallarının karşılaştığı birçok sorunun çözümünü önemli ölçüde basitleştirmeyi mümkün kılmıştır. Sorunların çoğu, üretim optimizasyonu ve optimum süreç kontrolü sorununun çözülmesinden kaynaklanmaktadır.

Uygulamanın ihtiyaçları, "yöneylem araştırması" adı altında uygun bir şekilde birleştirilen özel bilimsel yöntemlerin ortaya çıkmasına neden olmuştur.

Tanım: Yöneylem araştırması derken, amaçlı insan faaliyetinin tüm alanlarında kararları gerekçelendirmek için matematiksel, niceliksel yöntemlerin uygulanmasını kastediyoruz.

Belirli bir hedefe ulaşmak için bazı eylemler yapılmasına izin verin. Etkinliği düzenleyen kişi (veya insan grubu) her zaman bir miktar seçim özgürlüğüne sahiptir: öyle ya da böyle organize edilebilir. Karar, organizatörün elindeki çeşitli olasılıklar arasından yapılan bir seçimdir.

Karar verme ve önerilen çözüm hipotezini test etme ihtiyacı matematiksel olarak aşağıdaki örneklerle doğrulanmaktadır:

Görev 1. Kaynakların en iyi kullanımı hakkında.

Şirket birkaç çeşit ürün üretmektedir. Bunları yapmak için bazı kaynaklar kullanılır (insan, enerji vb. dahil). Kaynak maliyetlerinin minimum olması ve kârın maksimuma çıkması için işletmenin çalışmasının nasıl planlanacağını hesaplamak gerekir.

Görev 2. Karışımlar hakkında.

Belirli özelliklere sahip bir karışım hazırlamak gerekir. Bunu yapmak için bazı “ürünleri” kullanabilirsiniz (diyetlerin hesaplanması için - gıda ürünleri, yem karışımları için - hayvanlar için gıda ürünleri, teknik karışımlar için - alaşımlar, teknik amaçlı sıvılar). görev, karışımın optimum miktarını elde etmek için optimum ürün sayısını (fiyata göre) seçmektir.

Görev 3. Taşıma sorunu.

Aynı kalitede benzer ürünler üreten işletmelerden oluşan bir ağ ve bu ürünlerin tüketicilerinden oluşan bir ağ bulunmaktadır. Tüketiciler ve tedarikçiler iletişim yolları (karayolları, demiryolu hatları, havayolu hatları) ile birbirine bağlıdır. Ulaşım ücretleri belirlendi. Taşıma maliyetlerinin minimum düzeyde olması, tüm tüketicilerin ihtiyaçlarının karşılanması ve tüm malların tedarikçilerden çıkarılması için ürünlerin taşınması için en uygun planın hesaplanması gerekir.

Verilen örneklerin her birinde, belirli bir amacı güden bir tür olaydan bahsediyoruz. Durumu karakterize eden bazı koşullar belirtilmiştir (özellikle elden çıkarılabilecek araçlar). Bu koşullar içerisinde planlanan etkinliğin bir anlamda daha karlı olabilmesi için bir karar verilmesi gerekmektedir.

Bu genel özelliklere uygun olarak, benzer sorunları çözmek için genel yöntemler geliştirilir ve bunlar birlikte yöneylem araştırmasının metodolojik şemasını ve aygıtını oluşturur.

Günümüzde bilgisayar teknolojisinin kullanımına dayalı otomatik kontrol sistemleri (ACS) yaygınlaşmaktadır. Otomatik bir kontrol sisteminin oluşturulması, kontrollü sürecin matematiksel modelleme yöntemleri kullanılarak ön incelemesi yapılmadan mümkün değildir. Olayların ölçeği ve karmaşıklığının artmasıyla birlikte, kararları doğrulamaya yönelik matematiksel yöntemler giderek daha önemli hale geliyor.

Yöneylem araştırmasının temel kavramları ve ilkeleri

Tanım: Operasyon, tek bir planla birleştirilen ve belirli bir hedefe ulaşmayı amaçlayan herhangi bir olaydır (eylemler sistemi).

Bir operasyon her zaman kontrollü bir olaydır; Organizasyonunu karakterize eden parametrelerin nasıl seçileceği hesaplamalara bağlıdır. Burada "organizasyon", operasyonda kullanılan teknik araçlar kümesini de içeren, kelimenin geniş anlamıyla anlaşılmaktadır.

Tanım: Belirleyici parametrelere bağlı olarak yapılan herhangi bir özel seçime karar denir.

Tanım: Optimal çözümler, şu ya da bu nedenle diğerlerine tercih edilen çözümlerdir.

Yöneylem Araştırmasının Amacı– optimal çözümlerin ön niceliksel gerekçesi.

Bazen, çalışmanın bir sonucu olarak, kesin olarak tanımlanmış tek bir çözümü belirtmek mümkündür; daha sıklıkla, nihai seçimin yapılabileceği neredeyse eşdeğer optimal çözümlerin bulunduğu bir alanı tanımlamak mümkündür.

Karar vermenin kendisi yöneylem araştırmasının kapsamının ötesine geçer ve sorumlu kişinin, çoğunlukla da nihai seçimi yapma hakkı verilen ve bu seçimin sorumluluğuyla görevlendirilen bir grup insanın yetki alanına girer.

Tanım: Birleşimleri çözümü oluşturan parametrelere çözüm elemanları denir.

Çözümün elemanları çeşitli sayıları, vektörleri, fonksiyonları, fiziksel özellikleri vb. içerebilir. Basitlik açısından çözümün tüm elemanlarını x ile göstereceğiz.

Herhangi bir yöneylem araştırması probleminde çözüm unsurlarının yanı sıra, problemin durumunda sabit olan ve ihlal edilemeyecek verilen koşullar da vardır. Özellikle bu tür koşullar, elden çıkarılabilecek araçları (madde, teknik, insan) ve karara getirilen diğer kısıtlamaları içerir. Birlikte ele alındıklarında, "olası çözümler kümesi" olarak adlandırılanları oluştururlar. Bu kümeyi X olarak gösterelim ve x çözümünün bu kümeye ait olduğu gerçeği şöyle yazılacaktır: xОХ.

Farklı çözümleri verimlilik açısından karşılaştırmak için, verimlilik göstergesi (amaç fonksiyonu) adı verilen bir tür niceliksel kritere sahip olmanız gerekir. Bu gösterge operasyonun hedef yönelimini yansıtacak şekilde seçilmiştir. En iyi çözüm, hedefe ulaşmaya maksimum ölçüde katkıda bulunan çözüm olarak kabul edilecektir. Bir performans göstergesi Z seçmek için öncelikle sorunun çözümünün neye yol açması gerektiğini belirlemelisiniz. Bir çözüm seçerken, verimlilik göstergesi Z'yi maksimum veya minimuma çeviren çözüm tercih edilir. Örneğin bir operasyondan elde edilen geliri maksimuma çıkarmak istiyorum; Verimlilik göstergesi maliyetler ise, bunların minimuma indirilmesi tavsiye edilir.

Çoğu zaman operasyona rastgele faktörler eşlik eder: doğanın “kaprisleri”, arz ve talepteki dalgalanmalar, teknik cihazların arızaları vb. Bu gibi durumlarda, genellikle maksimuma çıkarmak (minimum seviyeye indirmek) istenen değerin kendisi değil, verimliliğin göstergesi olarak alınan ortalama değerdir (matematiksel beklenti).

Bir performans göstergesi seçme görevi her sorun için ayrı ayrı çözülür.

Görev 1. Kaynakların en iyi kullanımı hakkında.

Operasyonun amacı maksimum sayıda mal üretmektir. Verimlilik göstergesi Z – minimum kaynak maliyetiyle (maks Z) mal satışından elde edilen kar.

Görev 2. Karışımlar hakkında.

Sorunun formülasyonunun önerdiği doğal bir verimlilik göstergesi, karışımın belirtilen özelliklerini (min Z) koruma ihtiyacına bağlı olarak, karışım için gerekli ürünlerin fiyatıdır.

Görev 3. Taşıma sorunu.

Operasyonun amacı, malların tüketicilere minimum nakliye maliyeti ile tedarikini sağlamaktır. Verimlilik göstergesi Z, birim zaman başına mal taşımanın toplam maliyetidir (min Z).