İyi çalışmanızı bilgi tabanına göndermek basittir. Aşağıdaki formu kullanın

Bilgi tabanını çalışmalarında ve çalışmalarında kullanan öğrenciler, yüksek lisans öğrencileri, genç bilim adamları size minnettar olacaklar.

Yayınlanan http://www.allbest.ru/

1. Üretim ve ekonomik sorunların çözümünde doğrusal programlama yöntemleri

Doğrusal programlama teknikleri, parametreler veya girdi değişkenleri üzerinde doğrusal kısıtlamalara sahip doğrusal uygunluk veya akış işlevlerini içeren optimizasyon problemleri için tasarlanmıştır. Doğrusal programlama, varlık tahsis problemlerini çözmek için yaygın olarak kullanılır. Ticaret dünyasında, doğrusal programlamanın olası uygulamalarından biri, maksimum kar için çeşitli finansal araçlarda fonların optimum dağılımını bulmaktır. Kâr, olası risk dikkate alınarak optimize edilirse, doğrusal yöntemler uygulanamaz. Riske göre ayarlanmış getiri, toplam portföydeki çeşitli yatırımların ağırlıklarının doğrusal bir fonksiyonu değildir; burada başka yöntemler, örneğin genetik algoritmalar gereklidir.

2. Grafik yöntem tabanlıgeometrik yorumlama üzerinedoğrusal programlama vermek

1. Grafiksel olarak çözülebilir:

İkiden fazla değişken içermeyen standart bir biçimde belirtilen görevler;

Bir dizi serbest değişkenle kanonik biçimde belirtilen problemler (r, kısıtlama sisteminin matrisinin sıralamasıdır);

Kanonik biçime indirgendikten sonra en fazla iki serbest değişken içerecek genel problemler.

2. Grafik çözümün ana biçimi, birinci tür problemdir. Bu nedenle, ikinci veya üçüncü tip bir problemle karşılaşılırsa, o zaman onların modeli ilk olarak birinci türe indirgenmelidir.

3. DP problemlerini grafik yöntemle çözme tekniği

I. Problemin kısıtlamalarında, eşitsizlik işaretlerini tam eşitlik işaretleriyle değiştirin ve karşılık gelen çizgileri oluşturun.

II. Problemin eşitsizlik kısıtlamalarının her biri tarafından çözülen yarım düzlemleri bulun ve gölgelendirin. Bunu yapmak için, bir noktanın koordinatlarını [örneğin, (0; 0)] belirli bir eşitsizlikle değiştirmeli ve ortaya çıkan eşitsizliğin doğruluğunu kontrol etmelisiniz. Eşitsizlik doğruysa, verilen noktayı içeren yarı düzlemi gölgelendirmek gerekir; aksi takdirde (eşitsizlik yanlıştır), verilen noktayı içermeyen yarı düzlemi gölgelendirmek gerekir.

Negatif olmaması ve olmaması gerektiğinden, izin verilen değerleri her zaman eksenin üzerinde ve eksenin sağında olacaktır, yani. I çeyreğinde.

Eşitlik kısıtlamaları yalnızca karşılık gelen çizgide bulunan noktalara izin verir. Bu nedenle, grafikte bu tür düz çizgileri vurgulamak gerekir.

III. Eş zamanlı olarak tüm izin verilen alanlara ait olan bir düzlemin parçası olarak bir ODR tanımlayın ve onu seçin. Bir IDT'nin yokluğunda, sorunun çözümü yoktur.

IV. ODR boş bir küme değilse, o zaman bir hedef hat oluşturmanız gerekir, örn. seviye çizgilerinden herhangi biri (burada L keyfi bir sayıdır, örneğin, bir katı ve yani hesaplamalar yapmak için uygundur). İnşaat yöntemi, doğrudan kısıtlamaların inşasına benzer.

V. (0; 0) noktasında başlayan ve noktasında biten bir vektör oluşturun. Hedef çizgi ve vektör doğru yapılandırılırsa, dik olacaklardır.

VI Maksimum CF'yi ararken, hedef çizgiyi vektör yönünde hareket ettirmek gerekir, CF'nin minimumunu ararken, vektörün yönüne karşı hareket etmek gerekir. Hareket sırasında ODR'nin son tepesi, CF'nin maksimum veya minimum noktası olacaktır. Böyle bir nokta (puan) yoksa, CF'nin yukarıdan (maksimum ararken) veya aşağıdan (minimum ararken) plan setinde sınırsız olduğu sonucuna varabiliriz.

Vii. CF'nin maks. (Min) noktasının koordinatlarını belirleyin ve CF'nin değerini hesaplayın. Optimal noktanın koordinatlarını hesaplamak için, kesişme noktasındaki düz çizgilerin denklem sistemini çözmek gerekir.

4 ... Tek yönlü bir yöntemde bir DP problemi için bir başlangıç \u200b\u200bplanı nasıl oluşturulur ve optimalliği nasıl kontrol edilir

Referans bir çözüm bulmak için, ana değişkenleri eşitlemek gerekir (kısıtlar sistemindeki değişkenler, onu kanonik forma getirmeden önce, problemin ana değişkenleri olarak adlandırılır), ardından ek değişkenler eşit olacaktır karşılık gelen ücretsiz üyeler. Dizin satırında negatif katsayı yoksa, maksimum problemi çözerken plan optimal kabul edilir. Asgari problemi çözerken, aksine, C satırı katsayıları pozitif değildir.

5 ... Temele dahil edilecek bir değişken (vektör) ve tabandan çıkarılacak bir değişken (vektör) nasıl tanımlanır

Hangi değişkenlerin temele girilmesi gerektiğini belirlemek için çözümleme sütununu bulmak gerekir. Bunu yapmak için, simpleks tablonun indeks satırına bakarız: mutlak değerdeki en büyük negatif öğeyi içerir, eğer minimum problemi çözersek, sonra en büyük pozitif olanı. Temelden türetilmesi gereken değişkeni belirlemek için çözümleme dizisi tanımlanır. Bunu belirlemek için, problemi maksimuma çözersek hesaplamak gerekir, o zaman sütun, simpleks ilişki çözücü olacaktır.

Tek yönlü ilişki (Q) \u003d Ücretsiz üye sütununun üyeleri

Eşleşen İzin Sütunu Öğeleri

Tek yönlü oran değerleri tablo halinde verilmiştir.

Elde edilen oranlar arasında, hem problemi minimumda çözerken hem de maksimum çözerken en küçük negatif olmayan simpleks oranı seçilir. Sıfır tek yönlü ilişki, bu oranın paydası pozitif bir sayı içeriyorsa çözümleme dizgisini tanımlar. Birkaç özdeş tek yönlü ilişki elde edilirse, çözümleme olarak herhangi bir çizgi seçilir. Çözümleyen satır ve sütunun kesişme noktasında çözümleyici unsur bulunur.

6 ... Doğrusal denklem sistemlerini çözmenin hangi yöntemi, simpleks yönteminin temelidir

İlk destek çözümünün belirlenmesi ve bir sonraki destek çözümüne geçiş, ilk LPP'nin önceden yazılmış olması gereken kanonik formdaki doğrusal denklemler sistemi için Jordan-Gauss yönteminin uygulanması temelinde gerçekleştirilir. ; bir referans çözümden diğerine geçişin yönü, orijinal problemin optimallik kriterine (amaç işlevi) göre seçilir.

7. Simpleks yönteminin algoritmasını tanımla

Simpleks yöntemini kullanarak bir doğrusal programlama problemini çözme şeması aşağıdaki ana aşamalardan oluşur. 1. Problemin matematiksel biçimlendirilmesi; 2. Kısıtlama sistemini kanonik biçime getirmek; 3. Referans bir çözüm arayın ve sorunun temelini bulun; 4. İlk simpleks tablonun oluşturulması; 5. Optimallik için planı kontrol etmek; 6. Optimal olanı elde etmek için planın art arda iyileştirilmesi.

8. İkili DP problemini oluşturmak için kuralları tanımlayın

İkili problemler oluşturmanın kuralları:

Orijinal problemin kaydı sıralanır (amaç işlevi maksimize edilmişse, eşitsizlik kısıtlamaları formunda olmalıdır.<= если минимизируется то >\u003d), bu koşulların yerine getirilmesi, karşılık gelen kısıtların -1 ile çarpılmasıyla sağlanır.Doğrudan problem maksimumda çözülürse, o zaman minimumda ikili olur ve bunun tersi de geçerlidir. Doğrudan problemin her bir kısıtlaması için ikili problemin bir değişkenine karşılık gelir ve bunun tersi de geçerlidir. İkili problemin kısıtlar sisteminin matrisi, doğrudan problemin kısıtlar sisteminin matrisinden elde edilir.Doğrudan problemin kısıtlar sisteminin serbest terimleri, hedefin karşılık gelen değişkenlerinin katsayılarıdır. ikilinin işlevi ve tersi, ama hayır, eşitliğin bir sınırlaması gibi değildir. Doğrudan problemin herhangi bir kısıtlaması eşitlik olarak yazılırsa, ikili problemin karşılık gelen değişkenine negatif olmama koşulu empoze edilmez.

9 ... İkili değerlendirmelerin ekonomik yorumu nedir

Ekonomik açıdan, ikili görev şu şekilde yorumlanabilir:

verilen kaynak miktarı b i ve birim maliyet C j değerleri için toplam maliyet maliyetini en aza indirmek için her bir kaynağın birim fiyatı ne olmalıdır? Ve ilk problemi şu şekilde tanımlıyoruz: verilen maliyetler için C j (j \u003d 1,2, ...,) xj (j \u003d 1,2, ..., n) kaç ve hangi ürünlerin üretilmesi gerektiğini n) Üretimi değer açısından maksimize etmek için bir üretim birimi ve mevcut kaynakların büyüklüğü bi (i \u003d 1,2, ..., n).

1 0 ... Son simpleks tablosundaki ikili tahminler nasıl belirlenir

İkili soruna çözüm bulmak için önce yapay temel yöntemiyle orijinal soruna çözüm buluyoruz. Son simpleks tablosu, dual problemin bir çözümü olduğunu göstermektedir.

1 1 ... Optimal üretim planlaması problemini formüle edin ve bir LP modeli olarak yazın

Bazı işletmeler, m tür kaynakları harcarken n çeşit ürün üretir. Aşağıdaki parametreler bilinmektedir: aij - j'inci ürünün bir birim miktarının üretimi için gerekli i-inci kaynak miktarı; aij0 (i \u003d 1,…, m; j \u003d 1,…, n);

işletmedeki i-inci kaynağın iki stoku, bi\u003e 0;

cj, j'inci ürünün birim miktarının fiyatıdır, cj\u003e 0.

Üretim hacmi ile doğru orantılı olarak kaynak maliyetlerinin arttığı varsayılmaktadır. Xj, j'inci ürünün planlanan üretim hacmi olsun. O zaman sadece böyle bir ürün setine x \u003d (x1, x2, ..., xn) izin verilir, bunun için i-inci kaynağın her bir türünün toplam maliyeti stokunu aşmaz:

Ek olarak, aşağıdaki kısıtlamaya sahibiz: xj0; j \u003d 1,…, n. (2)

Bir dizi ürünün maliyeti x şu şekilde ifade edilir: (3)

Üretim planlama problemi şu şekilde ortaya konur: tüm x vektörleri arasından (1), (2) değerine uyan, (3) değerinin en büyük değeri aldığı bir tane bulun.

1 2 ... Karışımın optimal bileşimi problemini formüle edin ve bunu bir DP modeli olarak yazın

Rezervleri sırasıyla d1, ..., dm olan m çeşit hammadde olsun. Bu hammaddeden, karışımın teknik özelliklerini belirleyen n madde içeren bir karışım yapmak gerekir. İ-inci tip hammadde birimindeki j'inci maddenin miktarını belirleyen, fiyatı ci (i \u003d 1, m) ve ayrıca bj (j \u003d 1, n), karışımdaki j'inci maddenin izin verilen en küçük miktarıdır.

En düşük hammadde maliyetiyle istenilen özelliklere sahip bir karışım elde etmek gerekir.

Görevin amacı (amaç işlevi) toplam hammadde maliyetini en aza indirmektir.

Kısıtlama sistemini karşılayan bir X \u003d (x 1, x 2,…, x n) vektörü bulun:

ve asgari değeri amaç fonksiyonuna ulaştırmak.

1 3 ... LP taşıma problemini formüle edin ve modelini yazın

Ulaşım problemi, matematiksel programlamadaki en yaygın problemlerden biridir (genellikle doğrusal). Genel olarak, şu şekilde temsil edilebilir: Tedarikçilerden tüketicilere malların teslimi için böyle bir plan bulmak gerekir, böylece nakliye maliyeti (veya toplam mesafe veya taşıma hacmi ton-kilometre cinsinden çalışır) en azdır. Sonuç olarak, üreticilerin tüketicilere en rasyonel bağlılığına ya da tam tersine kaynar. En basit şekliyle, bir ürün türü dağıtıldığında ve tüketiciler onu hangi tedarikçiden alacaklarını önemsemediğinde, sorun aşağıdaki gibi formüle edilir.

Arkaplan bilgisi:

Mi, i-inci hareket noktasındaki yük birimlerinin sayısıdır (i \u003d 1, 2,…, k);

Nj - j'inci varış yeri ihtiyacı (j \u003d 1, 2,…, l) (kargo birimlerinde);

aij - i-inci noktadan j-inci noktaya bir birim kargo taşıma maliyeti.

İ-ro noktasından j-inci noktaya nakliye için planlanan kargo birimi sayısını xij ile gösterelim.

Kabul edilen gösterimde:

Toplam (toplam) nakliye maliyeti;

İ-ro noktasından ihraç edilen kargo miktarı;

J noktasına teslim edilen kargo miktarı.

En basit durumda, aşağıdaki bariz koşullar karşılanmalıdır:

Böylece, taşıma probleminin matematiksel formülasyonu şöyle olacaktır:

koşullar altında:

Bu soruna kapalı (kapalı, dengeli) taşıma modeli denir. Koşulun, kapalı bir taşıma sorununun çözülebilirliği için doğal bir koşul olduğuna dikkat edin. Daha genel bir taşıma sorunu, sözde açık (dengesiz) taşıma modelidir:

koşullar altında:

1 4 . Hangi taşıma problemi modelleri açık olarak adlandırılır ve açık bir model nasıl kapalı bir modele dönüştürülür?

Taşıma sorununun çözülebilmesi için hareket noktalarındaki stokların varış noktalarındaki kargo ihtiyacına eşit olması gerekli ve yeterlidir. Denge koşulu karşılanırsa, taşıma problemi modeli kapalı olarak adlandırılır. Denge koşulu karşılanmazsa, taşıma sorunu modeli açık olarak adlandırılır. Kapalı bir model elde etmek için, bir eksik kargo stoğu ile ek (hayali) bir taban getirilir.

Modele, kargo stokunun tüketicilerin toplam talebi ile gerçek tedarikçi stoğu arasındaki farka eşit olduğu hayali (m + 1) -ci bir tedarikçi tanıtılmışsa. Hayali bir tedarikçiden mal teslimi için tüm tarifeler 0: 'a eşit kabul edilir. Taşıma tablosuna bir satır eklenir.

Modele, talebin tedarikçilerin toplam arzı arasındaki farka eşit olduğu hayali (n + 1) bir tüketici tanıtıldı. Hayali ihtiyaçları olan malların teslimi için tüm tarifeler 0: 'a eşit kabul edilir. Taşıma tablosuna bir sütun eklenir.

15 ... Potansiyel yöntem

Potansiyeller yöntemi, ulaşım sorunlarını çözmek için yaygın bir yöntemdir. Taşımacılık sorununun uygulanabilir bir çözümü (i \u003d 1,2, ..., m; j \u003d 1,2, ... n) optimalse, o zaman tedarikçilerin potansiyelleri (sayıları) (i \u003d 1,2 , ..., m) ve tüketiciler (j \u003d 1,2, ..., n). Tahminler tüm koşul vektörleri (tablodaki hücreler) için pozitif değilse destek çözümü optimaldir. Potansiyel yöntemle ulaşım problemlerini çözmek için algoritma:

a) Sorunun çözülebilirliği için gerekli ve yeterli koşulun yerine getirildiğini kontrol edin. Görevin bakiyesi yanlışsa, hayali bir tedarikçi veya tüketici, eksik stoklar veya taleplerle ve sıfır nakliye maliyetiyle ortaya çıkar. b) ilk destek çözümünü oluşturun (minimum maliyet yöntemini veya başka bir yöntemi kullanarak), yapımının doğruluğunu işgal edilen hücre sayısına göre kontrol edin (m + n-1 olmalıdır) ve koşulların vektörlerinin olduğundan emin olun. doğrusal olarak bağımsız (silme yöntemi kullanılır). c) referans çözüme karşılık gelen bir potansiyeller sistemi oluşturun. Bunun için sonsuz sayıda çözümü olan bir denklem sistemi çözülür. Sisteme belirli bir çözüm bulmak için, potansiyellerden birine (genellikle daha fazla sayıda işgal edilmiş hücreye karşılık gelen) keyfi olarak bir değer (genellikle sıfır) atanır. Potansiyellerin geri kalanı benzersiz şekilde formüllerle belirlenir. d) tablonun serbest hücreleri için optimallik koşulunun yerine getirildiğini kontrol edin. Bunu yapmak için, tüm serbest hücrelere ilişkin tahminler formüller kullanılarak hesaplanır ve sıfırdan büyük olanlar hücrelerin sol alt köşelerine yazılır. Tüm serbest hücreler için, o zaman amaç fonksiyonunun değeri hesaplanır ve elde edilen çözüm optimal olduğu için problemin çözümü sona erer. Pozitif puana sahip en az bir hücre varsa, destek çözümü optimal değildir.

e) Amaç fonksiyonunun değerinin daha az olacağı referans çözüme gidin. Bunu yapmak için, en yüksek pozitif puana karşılık gelen görev tablosunun hücresini bulun. Bu hücreyi ve destek çözümünün işgal ettiği hücrelerin bir bölümünü içeren bir döngü oluşturulur. Döngünün hücrelerinde, "+" ve "-" işaretleri, en yüksek pozitif puana sahip hücrede "+" ile başlayarak dönüşümlü olarak yerleştirilir. Döngü boyunca bir miktar kayma (yükün yeniden dağıtılması) gerçekleştirilir. Ulaşıldığı "-" işaretli hücre boş kalır. Birkaç hücrede minimum değere ulaşılırsa, bunlardan biri boş kalır ve kalan hücrelerin sayısı eşit kalacak şekilde geri kalanına temel sıfırlar konur. Ardından bu algoritmanın 3. adımına gidin.

AĞ PLANLAMA MODELLERİ

1. SPM yöntemlerini uygulamanın hedefleri nelerdir? Ağ yöntemlerinin uygulama alanını tanımlayınfer ekonomi

Ağ planlaması, karmaşık projelerin ve gelişmelerin uygulanması için bir planın modellenmesini, analiz edilmesini ve dinamik olarak yeniden yapılandırılmasını sağlayan, örneğin: herhangi bir nesnenin inşası ve yeniden inşası; araştırma ve geliştirme çalışmalarının performansı; üretim için üretimin hazırlanması; ordunun yeniden silahlanması. Bu tür projelerin karakteristik bir özelliği, bir dizi ayrı, temel çalışmadan oluşmalarıdır. Birbirlerini öyle şartlandırırlar ki, bazıları tamamlanmadan bazı işler başlatılamaz. Ağ planlaması ve yönetiminin temel amacı proje süresini en aza indirmektir. Ağ planlaması ve yönetiminin görevi, nihai hedeflere zamanında ve sistematik olarak ulaşılmasını sağlayan işlerin, eylemlerin veya faaliyetlerin sırasını ve birbirine bağımlılığını grafiksel, görsel ve sistematik olarak görüntülemek ve optimize etmektir.

SPU sistemi şunları sağlar:

Belirli bir dizi çalışmanın uygulanması için bir program oluşturun; zaman, emek, malzeme ve mali kaynak rezervlerini belirlemek ve harekete geçirmek; - çalışma sırasında olası aksaklıkların öngörülmesi ve önlenmesi ile "öncü bağlantı" ilkesine dayalı işlerin karmaşıklığını yönetmek; - farklı seviyelerdeki yöneticiler ve işin icracıları arasında net bir sorumluluk dağılımı ile bir bütün olarak yönetimin verimliliğini artırmak; - Çözülmekte olan sorunun kapsamını ve yapısını net bir şekilde gösterin, problem çözme sürecinin tek bir kompleksini oluşturan çalışmayı gerekli herhangi bir ayrıntı derecesiyle tanımlayın; - - Komisyonun belirlenen hedeflere ulaşmak için gerekli olduğu olayları belirlemek; - Bir ağ modeli inşa etme yöntemi, nesnenin durumu ve dış ve iç çevrenin koşulları nedeniyle tüm bağımlılıkların doğru bir yansımasını içerdiğinden, işler arasındaki ilişkiyi belirlemek ve kapsamlı bir şekilde analiz etmek; - bilgisayar teknolojisini kapsamlı şekilde kullanmak; - büyük miktarlardaki raporlama verilerini hızlı bir şekilde işleyin ve yönetime program uygulamasının gerçek durumu hakkında zamanında ve kapsamlı bilgiler sağlayın; - - raporlama belgelerini basitleştirmek ve birleştirmek için.

2. Ağ grafiği nedir?

Bir ağ modeli, grafik gösterimi ağ diyagramı olarak adlandırılan, bir ağ biçiminde belirtilen, birbiriyle ilişkili belirli bir dizi çalışmanın uygulanmasına yönelik bir plandır.

3. İş ve olaylar terimleri ile ne kastedilmektedir, nasıle bildiğiniz iş türleri?

Ağ modelleri aşağıdaki üç unsurdan oluşur:

İş (veya görev) Olay (kilometre taşları) İletişim (bağımlılık)

İş (Etkinlik), kural olarak belirli (verilen) bir sonuç elde etmek için yapılması gereken ve sonraki işlemlere devam edilmesine izin veren bir işlemdir. "Görev" ve "iş" terimleri aynı olabilir, ancak bazı durumlarda görevler genellikle doğrudan üretimin ötesine geçen eylemlerin yürütülmesi olarak adlandırılır, örneğin "Tasarım belgelerinin gözden geçirilmesi" veya "Müşteri ile görüşmeler". Bazen "görev" terimi, hiyerarşideki en alt düzeydeki etkinlikleri temsil etmek için kullanılır. Olay (Düğüm) - Sistemin durumunun değiştiği an, özellikle herhangi bir işin başlangıcı veya bitişi doğası gereği bir olaydır ve her işin zorunlu olarak bir ilk ve son olayı vardır. İş, bir ilk olaydan bir bitiş olayına geçmek için gerçekleşmesi gereken bir eylem veya süreçtir. Bazı olaylar birkaç iş için ortaktır; bu durumda, olayın meydana gelmesi, bu olaydan hemen önceki son işlerin tamamlanmasına karşılık gelen zamandır. Dönüm noktası, önemli ara sonuçlara (projenin ayrı aşamaları) ulaşılmasını karakterize eden bir olay türüdür. Bağlantı (Bağlantı), bireysel çalışmanın zamanlaması ile olayların meydana gelmesi arasındaki mantıksal bir ilişkidir. Bazı işleri yapmaya başlamak için başka bir işi tamamlamak gerekiyorsa, bu çalışmaların bir bağlantıyla (bağlı) bağlı olduğunu söylüyorlar. Özünde ilişkiler, çalışma teknolojisi veya organizasyonları tarafından belirlenebilir. Buna göre, teknolojik ve örgütsel bağ türleri ayırt edilir. İlişkiler ayrıca bağımlılıklar (İlişki) veya kukla işler (Kukla Aktivite) olarak da adlandırılabilir. Bağlantılar, sanatçılar ve doğrudan zaman yatırımı gerektirmez, ancak uzatma süresi (pozitif, negatif veya sıfır) ile karakterize edilebilirler.

4. Olması gereken temel gereksinimleri tanımlayınağ programını tatmin edebilir

Bir ağ diyagramı oluştururken, bir dizi kural izlenmelidir.

1. Ağ modelinde hiçbir "çıkmaz" olay, yani bitiş olayı dışında hiçbir işin çıkmadığı olaylar olmamalıdır. Burada, ya işe gerek yoktur ve iptal edilmesi gerekir ya da bir sonraki olayın gerçekleşmesi için bir olayın ardından belirli bir işe ihtiyaç duyulmaz. Bu tür durumlarda, ortaya çıkan yanlış anlamayı düzeltmek için olayların ve çalışmaların ilişkisini dikkatlice incelemek gerekir.

2. Ağ programında en az bir işten önce gelmeyen hiçbir "kuyruk" olayı olmamalıdır (ilk olan hariç). Ağda bu tür olayları bulduktan sonra, önceki işlerin icracılarını belirlemek ve bu işleri ağa dahil etmek gerekir.

3. Ağın kapalı döngüleri ve döngüleri, yani bazı olayları kendilerine bağlayan yollar olmamalıdır. Bir kontur göründüğünde (ve karmaşık ağlarda, yani karmaşıklık indeksi yüksek ağlarda, bu oldukça sık meydana gelir ve yalnızca bir bilgisayar yardımıyla tespit edilir), orijinal verilere geri dönmek ve işin kapsamını revize etmek, ortadan kaldırılmasını sağlamak.

4. Herhangi iki olay, birden fazla ok çalışmasıyla doğrudan ilişkilendirilmelidir. Paralel çalışmayı tasvir ederken bu koşulun ihlali meydana gelir. Bu eserler olduğu gibi bırakılırsa iki farklı eserin aynı isme sahip olacağından dolayı kafa karışıklığı olacaktır. Ancak, bu işlerin içeriği, dahil olan müteahhitlerin bileşimi ve işe harcanan kaynak miktarı önemli ölçüde farklılık gösterebilir.

5. İşlerin ve olayların zaman tahminleri nasıl belirleniyor?

Herhangi bir çalışmanın başlangıcı ve bitişi, başlangıç \u200b\u200bve bitiş olayları adı verilen bir çift olay ile tanımlanır. Bu nedenle, belirli bir çalışmayı belirtmek için, ilk (i-inci) ve son (j-inci) olayların numaralarından oluşan çalışma kodu P i, j kullanılır (Şekil 1, a). Şekil 1, b, kabul edilen gösterimdeki kodlama çalışması ve olaylarının bir örneğini göstermektedir: t ij - çalışmanın süresi Р i, j, t - olayın erken tarihi (beklenen an), t * - geç tarih (maksimum an) olay, n - olay numarası, n cm - önceki (bitişik) olayın numarası.

Şekil 1. Ağ diyagramı elemanlarının belirlenmesi: a - iş kodu; b - kabul edilen atamalarda kodlama olaylarına bir örnek; c - yukarıdaki gösterimde bir olay görüntüsü örneği.

Şekil 1c, yukarıdaki gösterimde bir olay görüntüsünün bir örneğini göstermektedir. J-th olayına dahil olan işler dizisiyle ve i-th olayından ortaya çıkan iş dizisiyle gösterelim. J'inci olayın erken tarihi (beklenen an), olayın gerçekleşemeyeceği zamandır ve formülle hesaplanır.

İ-th olayının geç zamanı (sınırlama anı), bu olayın meydana geldiği zamandaki maksimum gecikmeyi gösterir:

6. Kritik yolun içeriğini, tanım yöntemini ve anlamını genişletinağ planlama modellerinde

Kritik yol, ağın ilk ve son olayları arasında zaman açısından en uzun süreye sahip olan bir dizi faaliyettir. Ağ bağlantılı bir projeyi tamamlamak için gereken minimum süre, kritik yolun uzunluğuna eşittir. Bir ağ diyagramı bir değil, birkaç kritik yol içerebilir. Bu yolda bulunan işler ve olaylara da kritik denir. Kritik yolda yer alan olaylar için t'den t * 'ye kadar rezerv aralığı 0'dır. Nihai ağ olayı için, olayın geç tarihi, erken tarihine, yani tp \u003d t * p'ye eşit olmalıdır. kritik yol, olayın erken tamamlanmasına eşittir, yani t cr \u003d t p \u003d t * p.

KİTLE HİZMET TEORİSİNİN SORUNLARI

1. Kuyruk teorisi kullanılarak hangi sistemler araştırılıyor?

Kuyruklama sürecinin modellenmesi açısından, hizmet için talep (talep) kuyruklarının oluştuğu durumlar aşağıdaki gibi ortaya çıkar. Hizmet sistemine girdikten sonra, istek, diğer isteklerin (önceden alınmış) isteklerinin sırasına katılacaktır. Hizmet kanalı, hizmet vermeye başlamak için kuyruktaki kişilerden bir istek seçer. Bir sonraki talep için servis prosedürünü tamamladıktan sonra, servis kanalı, bekleme bloğunda bir tane varsa bir sonraki talebe hizmet vermeye başlar. Bu tür bir kuyruk sisteminin işleyiş döngüsü, hizmet sisteminin tüm işlem süresi boyunca birçok kez tekrarlanır. Bu durumda, önceki müşteriye hizmet verildikten sonra sistemin bir sonraki müşteriye hizmet vermeye geçişinin anlık olarak rastgele zamanlarda gerçekleştiği varsayılır.

2. Kuyruk sistemi örneklerine bakıniya ekonomide, üretimde

Kuyruk sistemi örnekleri şunlardır: · araba bakım noktaları; · Gelen uygulamalara veya belirli sorunları çözmek için gereksinimlere hizmet eden kişisel bilgisayarlar; · İşletmelerin mevcut raporlamalarının kabulü ve doğrulanması ile uğraşan vergi müfettişliği bölümleri; · Denetim firmaları; · Telefon santralleri vb.

3. Kuyruk sistemleri nasıl sınıflandırılır?

CMO'lar, bileşime ve hizmetin başlamasından önce kuyrukta geçirilen süreye ve hizmet taleplerinin disiplinine bağlı olarak farklı gruplara ayrılır. CMO'nun yapısına göre, tek kanal (bir servis cihazı ile) ve çok kanallı (çok sayıda servis cihazı ile). Çok kanallı sistemler, aynı veya farklı performansa sahip hizmet cihazlarından oluşabilir.

Taleplerin hizmete başlamadan önce kuyrukta kalış sürelerine göre sistemler üç gruba ayrılır:

1) sınırsız bekleme süresi ile (bekleme ile),

2) retler ile;

3) karışık tip.

4. En basit akışın özellikleri nelerdir?

En basit akış aşağıdaki önemli özelliklere sahiptir:

1) Olasılıksal akış rejiminin zaman içindeki değişmezliğini ifade eden durağanlık özelliği. Bu, düzenli aralıklarla sisteme giren istek sayısının ortalama olarak sabit olması gerektiği anlamına gelir. Örneğin, günde ortalama yükleme için gelen vagon sayısı, örneğin on yılın başında ve sonunda farklı zaman dilimleri için aynı olmalıdır.

2) Bir veya daha fazla sayıda hizmet talebinin çakışmayan zaman aralıklarında gelişinin karşılıklı bağımsızlığını belirleyen bir sonradan etkinin yokluğu. Bu, belirli bir zaman aralığında gelen isteklerin sayısının, önceki zaman aralığında sunulan isteklerin sayısına bağlı olmadığı anlamına gelir. Örneğin, materyaller için ayın onuncu gününde gelen araçların sayısı, ayın dördüncü veya önceki herhangi bir gününde servis edilen araçların sayısına bağlı değildir.

3) Sıradanlığın özelliği, iki veya daha fazla talebin eşzamanlı olarak gelişinin pratik imkansızlığını ifade eder (böyle bir olayın olasılığı, ikincisi sıfıra yönlendirildiğinde, dikkate alınan zaman süresine göre ölçülemeyecek kadar küçüktür).

En basit talep akışıyla, sisteme giren taleplerin dağılımı Poisson dağıtım yasasına uyar:

t zamanında hizmet sisteminin tam olarak k müşteri alma olasılığı:

nerede. - birim zaman başına hizmet için alınan ortalama istek sayısı.

5. Servis süresinin genellikle hangi dağılımı vardır?

Tüm sistemin verimini belirleyen servis cihazlarının en önemli özelliklerinden biri servis süresidir. Bir isteğin hizmet süresi (), geniş bir aralıkta değişebilen rastgele bir değişkendir. Bu, servis cihazlarının kendilerinin çalışmasının stabilitesine ve ayrıca sisteme giren çeşitli parametrelere, gereksinimlere (örneğin, yükleme veya boşaltma için gelen araçların farklı taşıma kapasitelerine) bağlıdır. Rastgele değişken, istatistiksel testler temelinde belirlenen dağıtım yasasıyla tamamen karakterize edilir.

Uygulamada, hizmet süresinin üstel dağılım yasası hakkındaki hipotez çoğunlukla kabul edilir.

Servis süresinin üstel dağılım yasası, dağıtım yoğunluğu artan t süresi ile keskin bir şekilde azaldığında gerçekleşir. Örneğin, isteklerin büyük kısmı hızlı bir şekilde sunulduğunda ve uzun vadeli hizmet nadir olduğunda. Hizmet süresinin üstel dağılım yasasının varlığı, istatistiksel gözlemlere dayanılarak oluşturulmuştur.

Servis süresinin üstel dağılım yasasıyla, servis süresinin t'den fazla sürmeyeceği bir olayın olasılığı:

v orandan belirlenen bir hizmet cihazıyla bir müşteriye hizmet verme yoğunluğudur:

bir servis cihazının bir talebine ortalama servis süresi nerede.

Hizmet süresinin dağıtım yasası üstel ise, aynı güce sahip birkaç hizmet cihazının varlığında, hizmet süresinin birkaç cihaz tarafından dağıtılması yasasının da gösterge olacağı unutulmamalıdır:

burada n, servis cihazlarının sayısıdır.

6. Kuyruk teorisinin işleyişinin analizinde pratik uygulaması nedir?üretim tembelliği?

Kuyruklama sisteminin uygulanması, hizmet talepleri daha sonraki tatminleri ile toplu halde alındığında sorunlarda kullanılır. Pratikte bu, hammaddelerin, malzemelerin, yarı mamullerin, ürünlerin depoya alınması ve depodan serbest bırakılması olabilir; aynı teknolojik ekipman üzerinde çok çeşitli parçaların işlenmesi; ekipman ayarlama ve onarımının organizasyonu; taşıma işlemleri; kaynakların rezerv ve güvenlik stoklarının planlanması; işletmenin optimal departman ve hizmet sayısının belirlenmesi; planlama ve raporlama belgelerinin işlenmesi.

ŞUBE ARASI DENGE MODELLERİ

1. Dallar arası uygulama alanısol ve ürünler arası bakiyeler

Sektörler arası denge (MOB, girdi-çıktı yöntemi), ülke ekonomisindeki sektörler arası üretim ilişkilerini karakterize eden ekonomik ve matematiksel bir denge modelidir. Bir endüstrideki çıktı ile bu çıktıyı sağlamak için gerekli olan tüm katılımcı endüstrilerin ürün harcamaları, maliyetleri arasındaki ilişkiyi karakterize eder. Girdi-çıktı dengesi nakit ve ayni olarak düzenlenir.

2. Bilanço modelleri neyi gösterir ve yansıtır?

Sektörler arası denge, bir doğrusal denklem sistemi biçiminde sunulur. Girdi-çıktı dengesi (IOB), sektörel bağlamda toplam sosyal ürünün oluşum ve kullanım sürecini yansıtan bir tablodur. Tablo, her ürün için üretim maliyetlerinin yapısını ve ekonomideki dağılımının yapısını göstermektedir. Sütunlar, ekonominin sektörlerinin brüt çıktısının ara tüketim ve katma değer unsurlarına göre değer bileşimini yansıtır. Çizgiler, her sektördeki kaynakların kullanımını yansıtır.

3. Karakter verdenge modelinin kene bölümleri

SNA metodolojisine göre MOB şemasında, iyi bilinen açık istatistiksel modelde olduğu gibi, üç ana bölüm (kadranlar) vardır: iç (veya birinci) kadran (I); yan (veya sağ) kanat (II kadran); alt kanat (III kadran). IV kadran geliştirilmiyor. MOB'un genel şeması aşağıdaki gibidir:

İç (veya birinci) kadran (I), endüstrilerin ara bağlantısını karakterize eder, ara tüketimi yansıtır; II çeyreğinde gayri safi yurtiçi hasılanın (GSYİH) nihai kullanımının yapısı verilmiştir; III kadran, elemanlar tarafından brüt katma değerin yapısını gösterir. I kadranında ("satranç masası"), ekonominin dalları satırlar ve sütunlar halinde kaydedilir. Her sektör için I kadranının sütunlarında, ürünlerin, işlerin, hizmetlerin (hammadde, malzeme, yakıt, enerji, hizmetlerin maliyeti) üretim maliyetleri sunulur ve satırlar her bir sektörün ürünlerinin nasıl olduğunu gösterir. tüm endüstriler arasında dağıtılmıştır. IOB'nin sağ tarafında (// çeyrek), çizgiler tüketici endüstrilerine karşılık gelir. Sütunlar nihai kullanım kategorilerini temsil eder: nihai tüketim (hanehalklarına hizmet veren hükümet ve kar amacı gütmeyen kuruluşların nihai tüketim harcamaları), brüt sermaye oluşumu (brüt sabit sermaye oluşumu, envanterlerdeki değişiklikler, net değer edinimi), ihracat dengesi - mal ve hizmet ithalatı. III çeyreğinde GSYİH'nın maliyet yapısı sunulmaktadır. III çeyreğin sütunları, imalat sanayilerine karşılık gelir ve satırlar, brüt katma değerin (çalışanların ücretleri, brüt kar, brüt karma gelir, üretimle ilgili vergiler ve sübvansiyonlar) ana maliyet bileşenlerine ve ürünler üzerindeki vergiler ve sübvansiyonlara karşılık gelir. . Bu nedenle, MOB verilerini dikey olarak ele alırsak, sütunlar, ara tüketim (I kadran) ve brüt katma değerden (III çeyrek) oluşan ve yatay olarak - satırlara göre - doğal olarak oluşan tek tek endüstrilerin çıktılarının maliyet yapısını gösterir. ara tüketim (I çeyrek) ve son kullanım (II çeyrek) için harcanan ürünlerin malzeme bileşimi. Ekonominin her şubesi için, ürünlerin kaynakları kullanımlarına eşittir.Dördüncü bölüm ikincinin altında yer almaktadır. Finans ve kredi sistemi aracılığıyla yürütülen ekonomideki yeniden dağıtım ilişkilerini karakterize eder. Planlı hesaplamalarda, kural olarak dördüncü bölüm kullanılmamaktadır ve bu nedenle kursumuz çerçevesinde değerlendirilmeyecektir.

4 . Denge modellerinde doğrudan maliyet katsayıları oluşturma yöntemlerini betimler. Bu oranlar nasıl hesaplanıyor?

Mantıksal katsayılar veya aynı zamanda da adlandırıldıkları gibi, doğrudan üretim içi maliyet katsayıları, i-th endüstrisinin ürününün ne kadarının j-th'nin brüt ürününün bir biriminin üretimi için harcanması gerektiğini gösterir. endüstri. Statik sektörler arası modellerde doğrudan maliyet katsayıları sabit kabul edilir, aij katsayılarının değerleri nasıl elde edilir? İki ana yol var.

1. İstatistik. Aij katsayıları, önceki yıllara ait bilanço analizine göre belirlenir. Bu durumda, doğrudan maliyet katsayılarının zaman içindeki değişmezliği, girdi-çıktı dengesinin uygun bir sektör seçimi ile elde edilir. Uygulamada görüldüğü gibi, yeterince büyük endüstrilerin doğru seçimiyle, aij katsayıları oldukça kararlı hale gelir.

xij ve Xj bilançodan alınır.

2. Normatif. Girdi-çıktı sektörünün bir modeli oluşturuluyor. Bu modelde endüstri, her biri için maliyet standartları zaten geliştirilmiş olan bir dizi ayrı endüstri olarak kabul edilir. Sektör tarafından ne tür ürünlerin üretileceğini önceden biliyorsanız, maliyet standartlarına göre, endüstri ortalama doğrudan maliyet katsayılarını hesaplayabilirsiniz.

Аij katsayıları belirlendikten sonra sistem (4) kullanılarak yukarıda formüle edilen 1 - 3 arasındaki problemler çözülebilir.

Teknolojik katsayılar aşağıdaki özelliklere sahiptir:

EKONOMİDE OYUN MODELLERİ

1. Oyunun sonuçlarındaki belirsizliğin nedenleri nelerdir?

Belirsizliğin ortaya çıkmasının ve neden olduğu riskin aşağıdaki neden grupları ayırt edilir: Ekonomiyi etkileyen birçok işlemin ve olgunun belirsizliği (bilimsel ve teknik ilerleme, doğal afetler, rakiplerin ve tüketicilerin davranışları); hem elde etme ve işlemedeki teknik zorluklardan hem de tamamen ekonomik nedenlerden kaynaklanan bilginin eksikliği, yanlışlığı ve tutarsızlığı - sahip olmanın olası faydalarını aşan bilgi edinmenin çok yüksek maliyetleri.

pazar anlaşmalarındaki katılımcıların, örneğin satıcılar ve alıcıların, anlaşmaların konusu ve koşulları hakkında eşit olmayan farkındalık düzeyi (bilgi asimetrisi); kişinin bilinçli olarak taviz vermesi gerekiyorsa, kararların değerlendirilmesinde çok kriterli ve çatışmalı Örneğin, bir emtia sirkülasyon sistemi oluştururken, işlem hızı siparişleri ile bitmiş mal stokunu muhafaza etme maliyetleri arasında uzlaşma sağlanmalıdır.

2. Bir matris oyununun alt ve üst fiyatları nasıl belirlenir ve aralarındaki ilişki nedir?

Matrisli bir m × n oyunu düşünün ve A 1, A 2,…, A m stratejileri arasında en iyi stratejiyi belirleyin. A i stratejisini seçerken, oyuncu A, B oyuncusunun kendisine A oyuncusu için getirisinin minimum olduğu strateji B j ile yanıt vermesini beklemelidir (B oyuncusu A oyuncusuna "zarar vermek" ister). A Bir strateji seçtiğinde VE; B oyuncusunun tüm olası stratejileri için (ödeme matrisinin i'inci sırasındaki en küçük sayı) b'ye oyunun düşük fiyatı veya maksimum getiri (maksimin) diyelim. Bu, oyuncu B'nin herhangi bir stratejisi için A oyuncusunun garantili getirisidir. Bu nedenle,

Maximin'e karşılık gelen stratejiye maximin stratejisi denir. Oyuncu B, Oyuncu A'nın kazancını azaltmakla ilgilenir; B j stratejisini seçerken, A için olası maksimum kazancı hesaba katar. B'yi üst oyun fiyatı veya minimum kazanç (minimax) olarak adlandıralım. Bu, oyuncu B'nin garantili kaybıdır. Bu nedenle ,.

Minimax'a karşılık gelen stratejiye minimax stratejisi denir. Oyunculara en "dikkatli" minimax ve maximin stratejilerinin seçimini dikte eden ilkeye minimax ilkesi denir. Bu ilke, her oyuncunun rakibinin hedefinin tersi bir hedefe ulaşmaya çalıştığına dair makul varsayımdan kaynaklanır.Eğer oyunun üst ve alt fiyatları aynıysa, oyunun üst ve alt fiyatlarının toplam değeri b \u003d c \u003d n, oyunun net fiyatı veya oyunun fiyatı olarak adlandırılır.

3. Temel formüle edinmatris oyunları teorisinin teoremi

Matrix oyunları teorisinin ana teoremi (Neumann'ın minimax teoremi), herhangi bir Matrix oyununda elde edilebilir "minimax" ın eşit olduğu (toplam değerleri oyunun değeridir) optimal karma stratejiler x *, y * olduğunu ileri sürer. ).

Veya Herhangi bir A matrisine sahip bir matris oyunu için, değerler ve birbirine eşittir, yani.

Ayrıca, karma stratejilerde ilişkinin kendisiyle ilgili olduğu en az bir durum vardır.

4. Basitleştirme yöntemleri nelerdir oyunlar?

Bir matrisin boyutunu azaltmak için kullanılan ilk yöntem, oyun teorisindeki en önemli kavramlardan birine dayanmaktadır - kavram hakimiyet stratejileri.

Eğer i'inci satır, j'ninci sıranın en azından (?) Elemanı ise, o zaman i'inci sıranın j'inci sıraya hakim olduğu söylenir. Bu nedenle, A oyuncusu j-inci stratejisini kullanmaz, çünkü i-inci stratejisi için getirisi, B oyuncusunun nasıl oynadığına bakılmaksızın j-inci stratejisinden daha az değildir. Benzer şekilde, i-inci sütun eleman ise - en azından j'inci sütunun (?) yönünde, o zaman j'inci sütunun i'inci sütuna hakim olduğu söylenir. Bu nedenle, B oyuncusu i-inci stratejisini kullanmaz, çünkü j-inci stratejisiyle kaybı (A oyuncusunun kazancına eşittir), i-inci stratejiden daha büyük değildir (?), A oyuncusu nasıl olursa olsun, i-inci stratejiden Diğer stratejilerin hakim olduğu stratejiler atılmalı ve sıfır olasılık atanmalıdır. Bu, oyunun fiyatını etkilemeyecektir. Ancak oyun matrisinin boyutu azalacaktır. Oyunu çözmeye başlamanız gereken yer burasıdır. Belirli bir hakimiyet durumu çoğaltma stratejiler... Eğer bir oyun ödeme matrisi birkaç özdeş satır (sütun) içerir, sonra bunlardan yalnızca bir satır bırakırız ve kalan satırları (sütunları) atarız. Atılan stratejilere sıfır olasılık atarız.Aşağıdakilerden dolayı açıkça elverişsiz saf stratejileri ortadan kaldırarak ödeme matrislerinin basitleştirilmesi (boyutta azalma) mümkündür. Baskın strateji teoremleri:

İlk oyuncunun i-inci stratejisinin i + 1'in matrisine hakim olduğu ve G'nin matrisi I + 1 stratejisini (satır) ortadan kaldırarak I matrisinden elde edilen bir oyun olalım. Sonra:

1. I oyununun fiyatı, G oyununun fiyatına eşittir;

2. G oyunundaki ikinci oyuncunun optimal karma stratejisi Q * \u003d (q 1 *, q 2 *,…, q n *) aynı zamanda I oyunundaki en iyi karma stratejisidir;

3. P * \u003d (p 1 *, p 2 *,…, pi *, p * i + 2,…, pm *) G oyunundaki ilk oyuncunun en uygun karma stratejisi ise, ardından karma stratejisi P * \u003d (p 1 *, p 2 *,…, pi *, p * i + 2,…, pm *) I. oyun için idealdir.

Yukarıdakilerden, hem birinci hem de ikincinin hükmedilen stratejiyi kullanmak için bir anlam ifade etmediği anlaşılır, bu nedenle hakim olunan tüm stratejiler atılabilir, yani. aslında, bu satırlara karşılık gelen orijinal A matrisinin satırları ve sütunları atılır. Bu dönüşüm, orijinal ödeme matrisi A'nın boyutunu küçülterek en uygun çözüm arayışını basitleştirir.

5. 2_ matrisli oyunları çözmek için geometrik yöntemler_nvem 2 ve uygulamaları

Oyunun karma stratejilerdeki çözümü, net bir geometrik yoruma izin verir. Oyunu çözmenin geometrik yöntemi aşağıdaki aşamaları içerir. 1. Apsis boyunca Kartezyen koordinat sisteminde, uzunluğu 1 olan segment A1A2 işaretlenir (Şekil 2.1.). Segmentin sol ucu, x \u003d 0 noktası, A1 stratejisine karşılık gelir, sağdaki ise x \u003d 1,0 - strateji A2. Bu segmentin tüm ara noktaları karma stratejilere S1 \u003d (p1, p2) karşılık gelir. 2. O noktasından itibaren koordinat ekseninde, kazançlar A1 stratejisi için işaretlenir. 3. Ordinat eksenine paralel bir çizgide, 1. noktadan itibaren, kazançlar A2 stratejisi için yatırılır. Getir matrisi olan bir oyun yapalım:

Eğer oyuncu II B1 stratejisini uygularsa, o zaman A1 ve A2 saf stratejilerini kullanırken I oyuncunun getirisi sırasıyla a11 \u003d 0.4 ve a21 \u003d 0.6'dır. Bu noktaları düz bir В1В1 çizgisiyle birleştirelim. B1 stratejisine sahip oyuncu I karma bir strateji uygularsa, o zaman matematiksel beklenti g1 \u003d a11p1 + a21p2 formülüyle belirlenen ortalama getiri, B1B1 düz çizgisi üzerindeki N noktasının koordinatı ile temsil edilir. Düz çizgi B1B1, strateji B1 olarak adlandırılır. B1B1 segmentinin herhangi bir noktasının koordinatı, A1 ve A2 stratejilerini karşılık gelen p1 ve p2 olasılıklarıyla uyguladığında oyuncu I'in getirisinin değerine eşittir. Benzer şekilde, oyuncu tarafından B2 stratejisinin uygulamasına karşılık gelen B2B2 segmentini oluşturuyoruz. II. Segmentin noktalarının koordinatları, karşılık gelen p1 ve p2 olasılıkları ve g2 \u003d a12p1 + a22p2'ye eşit olan A1 ve A2 stratejilerinin ortalamasını belirler.

6. Bir matris oyunu ile doğrusal programlama problemi arasındaki bağlantı neye dayanır?

Başlangıçta, stratejik matris oyunları teorisinin gelişimi paralel olarak ve doğrusal programlamadan bağımsız olarak gerçekleştirildi. Daha sonra stratejik bir matris oyununun bir çift ikili doğrusal programlama problemine indirgenebileceği tespit edildi. Bunlardan birini çözdükten sonra, 1. oyuncunun optimal stratejilerini elde ederiz; Diğerini çözerek, 2. oyuncunun optimal stratejilerini elde ederiz. Stratejik matris oyunları ile doğrusal programlama arasındaki matematiksel karşılıklılık, oyun teorisinin ana teoremini 1951'de formüle eden ve kanıtlayan JB Danzig tarafından oluşturuldu.

Teorem. Her sıfır toplamlı matris oyununda her zaman karma bir strateji çözümü vardır, örn. Sırasıyla 1 ve 2 oyuncularının bir v sayısı ve U * ve W * stratejileri vardır, öyle ki aşağıdaki eşitsizlikler geçerlidir:

İspatlanmakta olan eşitsizliklerin anlamını açıklığa kavuşturalım: 1. oyuncu optimal stratejisinden saparsa, getirisi oyun fiyatına göre artmaz; 2. oyuncu optimal stratejisinden saparsa, bu durumda kaybı oyunun fiyatına göre azalmaz.

7. Doğa ile oynamak arasındaki fark nedir?

Doğası gereği oyunun ayırt edici bir özelliği, katılımcılardan yalnızca birinin bilinçli olarak oyunda hareket etmesidir, çoğu durumda oyuncu 1 olarak adlandırılır. Oyuncu 2 (doğa) kasıtlı olarak 1. oyuncuya karşı hareket etmez, ancak belirli bir hedefi yokmuş gibi davranır ve rastgele seçim yapar. oyundaki bir sonraki "Hamle" ortağı. Bu nedenle, "doğa" terimi, doğanın gerçekten bir "oyuncu" 2 olabileceği durumlar olsa da, kelimenin tam anlamıyla alınmaması gereken bazı nesnel gerçekleri karakterize eder (örneğin, hava koşulları veya doğanın doğal güçleriyle ilgili koşullar ).

8. Doğa ile oyun çözmenin ana kriterlerini ve bu kriterler için hesaplama formüllerinin neler olduğunu listeleyin.

Bayes kriteri.

Bayes'in kriterine göre, optimum strateji, ortalama getiriyi a maksimize eden veya ortalama riski r en aza indiren (saf) A i stratejisidir.

Değerleri sayar mıyız? (A ij p j)

Laplace kriteri.

Doğa durumlarının olasılıkları makul ise, tüm doğa durumlarının eşit derecede olası olduğu varsayıldığı Laplace yetersiz temeli ilkesini kullanırlar, yani:

q 1 \u003d q 2 \u003d ... \u003d q n \u003d 1 / n.

Wald kriteri.

Wald kriterine göre, optimum strateji, en kötü koşullarda maksimum getiriyi garanti eden saf bir strateji olarak kabul edilir, yani.

a \u003d max (min a ij)

Wald kriterleri, doğanın en olumsuz koşullarına ilişkin istatistikleri yönlendirir, yani. bu kriter durumun kötümser bir değerlendirmesini ifade eder.

Savage kriteri.

a \u003d min (maks r ij)

Savage kriteri istatistikleri doğanın en elverişsiz koşullarına yönlendirir, yani. bu kriter durumun kötümser bir değerlendirmesini ifade eder.

Hurwitz kriteri.

Hurwitz kriteri karamsarlık - iyimserlik için bir kriterdir. Çünkü (optimal strateji, ilişkinin yerine getirildiği stratejidir:

nerede s i \u003d y min (a ij) + (1-y) max (a ij)

Y \u003d 1 için Walde kriterini, y \u003d 0 için iyimser kriteri (maksimax) elde ederiz.

Hurwitz kriteri, insanlar için doğanın hem en kötü hem de en iyi davranışının olasılığını hesaba katar. Nasıl seçilir? Hatalı kararların sonuçları ne kadar kötü olursa, hatalara karşı sigorta etme arzusu o kadar büyük, y 1'e o kadar yakın olur.

Maximax kriteri.

Maximax kriteri, istatistikleri doğanın en uygun koşullarına, yani. bu kriter durumun iyimser bir değerlendirmesini ifade eder.

Pratik görevler

Görev numarası 1

Direkt doğrusal programlama problemini simpleks yöntemi kullanarak simpleks tablo kullanarak çözelim.

Aşağıdaki kısıtlama koşulları altında F (X) \u003d 2x 1 + 5x 2 + 6x 3 amaç fonksiyonunun maksimum değerini belirleyin.

7x 1 + 8x 2 + 3x 3? 81

4x 1 + x 2 + 6x 3? 68

5x 1 + x 2 + 7x 3? 54

İlk referans planını oluşturmak için, eşitsizlikler sistemi, ek değişkenler (kanonik forma geçiş) eklenerek bir denklem sistemine indirgenir.

1. anlamdaki eşitsizlik (?) Temel değişken x 4'ü tanıtıyoruz. İkinci anlam eşitsizliğinde (?), X 5 temel değişkenini tanıtıyoruz. 3. anlamında eşitsizlik (?), X 6 temel değişkenini tanıtıyoruz.

7x 1 + 8x 2 + 3x 3 + 1x 4 + 0x 5 + 0x 6 \u003d 81

4x 1 + 1x 2 + 6x 3 + 0x 4 + 1x 5 + 0x 6 \u003d 68

5x 1 + 1x 2 + 7x 3 + 0x 4 + 0x 5 + 1x 6 \u003d 54

Bu denklem sisteminin katsayı matrisi A \u003d a (ij) şu şekildedir:

Temel değişkenler, kısıtlama sisteminin yalnızca bir denklemine dahil edilen ve ayrıca bir birim katsayısı olan değişkenlerdir.

Ek değişkenlerin ekonomik anlamı: DP görevindeki ilave değişiklikler, belirli bir optimal planın üretiminde kalan fazla hammaddeleri, zamanı ve diğer kaynakları ifade eder.

Temel değişkenler için denklem sistemini çözelim: x 4, x 5, x 6

Serbest değişkenlerin 0 olduğunu varsayarsak, ilk temeli elde ederiz:

X1 \u003d (0,0,0,81,68,54)

Negatif değilse temel çözüme kabul edilebilir denir.

Simpleks yönteminin temel algoritmasına geçelim.

Yineleme # 0.

1. Optimallik kriterinin kontrol edilmesi.

Mevcut referans planı optimal değildir çünkü indeks satırında negatif oranlar vardır.

2. Yeni bir temel değişkenin tanımı.

Önde gelen olarak, x 3 değişkenine karşılık gelen sütunu seçeriz, çünkü bu modüldeki en büyük katsayıdır.

...

Benzer belgeler

Doğrusal programlama probleminin matematiksel formülasyonu. Problemleri çözmek için simpleks yönteminin uygulanması. Doğrusal bir programlama probleminin geometrik yorumu. Doğrusal programlama yöntemlerinin aşırı ekonomik problemlere uygulanması.

dönem ödevi 10/05/2014 tarihinde eklendi


Doğrusal programlama problemini grafik bir yöntemle çözmek için kabul edilebilir değer aralığını ve amaç fonksiyonunun optimumunu bulmak. Simpleks yöntemi ve dualite teorisini kullanarak ikili değişkenlerin optimal değerlerini bulma.

test, 04/09/2012 eklendi


Doğrusal programlama problemini grafiksel bir şekilde çözmek. Uç noktanın belirlenmesi. Optimallik için planı kontrol ediyorum. Dikdörtgen kuralı. Simpleks yöntemini kullanarak doğrusal programlama problemlerini çözmenin sonuçlarının analizi ve düzeltilmesi.

test, 05/04/2014 eklendi


Doğrusal programlama problemlerini çözmek için simpleks yöntem. Oyun teorisinin unsurları. Kuyruk sistemleri. Taşıma sorunu. Doğrusal programlama problemlerini çözmek için grafik analitik bir yöntem. Walde kriteri ile optimal stratejinin belirlenmesi.

test, 08/24/2010 eklendi


Dijital bilgi işlem teknolojisinin yaratılış tarihi. Doğrusal programlama yöntemleri ve modelleri. Sorunun ekonomik ifadesi. Görevi uygulamak için yöntem seçimi Programlama dili seçiminin özellikleri. Problemin ağ planlama yöntemi ile çözülmesi.

dönem ödevi, 02/19/2015 eklendi


Optimal çözümleri bulma problemlerini çözmenin teorik temeli olan matematiğin bir dalı olarak matematiksel programlama kavramı. Ekonomik sorunlara en uygun çözümleri bulmanın ana aşamaları. Doğrusal programlama problemlerine örnekler.

06/15/2015 tarihinde eğitim eklendi


Ekonomik sistemlerin modellenmesi: temel kavramlar ve tanımlar. Matematiksel modeller ve hesaplama yöntemleri. Matematikten bazı bilgiler. Doğrusal programlama problemlerine örnekler. Doğrusal programlama problemlerini çözme yöntemleri.

06/15/2004 tarihinde ders eklendi


Maksimum kar elde etmek için ekonomik ve matematiksel bir model, grafik bir yöntemle çözümü. Simpleks yöntemini kullanarak doğrusal programlama problemini çözmek için algoritma. İkili problemin derlenmesi ve grafiksel çözümü. Ödeme matrisi çözümü.

test, 05/11/2014 eklendi


Doğrusal programlama problemlerinin grafik çözümü. Simpleks yöntemini kullanarak doğrusal programlama problemlerini çözme. Ekonomik problemlerin çözümünde matematiksel programlama ve ekonomik ve matematiksel yöntemlerin pratik kullanım olanakları.

dönem ödevi 10/02/2014 tarihinde eklendi


Modellemenin temel kavramları. Modelin genel kavramları ve tanımı. Optimizasyon problemlerinin beyanı. Doğrusal programlama yöntemleri. Doğrusal programlamada genel ve tipik görev. Doğrusal programlama problemlerini çözmek için simpleks yöntem.

RUSYA FEDERASYONU TARIM BAKANLIĞI

İstatistik Bölümü

ve bilgi sistemleri

ekonomide

B2.B4 optimal çözüm yöntemleri

Disiplin kuralları

Eğitim yönü 080100 Ekonomi

Temel hazırlık profilleri

Finans ve kredi

Vergiler ve vergilendirme

Muhasebe, analiz ve denetim

İşletmelerin ve kuruluşların ekonomisi

Mezunun niteliği (derecesi)

Lisans

Derleyen: kıdemli öğretmen Sagadeeva E.F.

Hakem: Sosyal Bilimler Adayı, Matematik Bölümü Doçenti Gilmanova G. Kh.

Serbest bırakılmasından sorumlu: kafa. İktisatta İstatistik ve Bilgi Sistemleri Bölümü, İktisadi Bilimler Adayı, Doçent A.Ableeva

Giriş
1. Doğrusal programlama problemlerinin geometrik yorumu
2. Doğrusal programlama problemini çözmek için simpleks yöntem
3. Dualite teorisinin temel kavramları
4 çift simpleks yöntemi
5. Yapay temelli simpleks yöntemi
6. Tamsayı programlama. Gomori Yöntemi
7. Kesirli doğrusal programlama
8. Doğrusal olmayan programlama problemleri. Lagrange çarpanı yöntemi
9. Bağımsız çalışma görevleri
10. Test görevleri
11. Yazışma öğrencileri tarafından hesaplamalı ve grafik çalışmaları ve kontrol çalışmalarını gerçekleştirme görevleri
12. Test sorularının kaynağı
13. Sınav biletleri
14. Kaynakça

Giriş

Optimal karar yöntemleri, hem belirli bir işletmede hem de belirli bir endüstride veya belirli bir bölgede veya tüm eyalette beşeri ekonomik faaliyetlerin planlanması için en iyi seçenekleri bulma teori ve yöntemlerini inceleyen bir matematik dalıdır.

En iyi seçenekler, maksimum iş gücü verimliliği, minimum maliyet, maksimum kar, minimum kaynak kullanımı vb. Sağlayanlardır. Matematik açısından bakıldığında, bu bir optimizasyon problemleri sınıfıdır. Bunları çözmek için ana araç matematiksel modellemedir. Matematiksel bir model, incelenen olgunun resmi bir açıklaması ve onunla ilgili mevcut tüm bilgilerin denklemler, özdeşlikler ve eşitsizlikler biçiminde matematik diline "tercümesidir". Tüm bu ilişkiler doğrusal ise, tüm soruna doğrusal programlama problemi (LPP) denir. Bu modelin etkililiği için kriter, hedef işlev adı verilen belirli bir işlevdir.

Genel bir doğrusal programlama problemini formüle edelim.

Sistem verilsin m doğrusal denklemler ve eşitsizlikler n değişkenler (kısıtlama sistemi):

(1)

ve doğrusal fonksiyon

Doğrusal fonksiyonun maksimum (minimum) değeri aldığı sistem (1) için bir çözüm bulmak gerekir.

Genel durumda, bir LPP'nin sonsuz sayıda çözümü olabilir. Genellikle kısıtlamaları karşılayan bir çözüme (1) denir plan... Tüm bileşenler (3) toner için ise kabul edilebilir çözüm.

En uygun çözüm veya optimal plan Doğrusal programlama probleminin çözümü, sistemin (1), koşul (3) 'ün tüm kısıtlamalarını karşılayan ve aynı zamanda amaç fonksiyonunun (2) maksimumunu (minimum) veren çözümü olarak adlandırılır.

Kanonik	Standart	Genel
1) Sınırlamalar
Denklemler	Eşitsizlikler	Denklemler ve eşitsizlikler
2) Negatif olmayan koşullar
Tüm değişkenler	Tüm değişkenler	Değişkenlerin bir kısmı
3) Amaç fonksiyonu
(maxveya min)

Burada: - problem değişkenleri; - amaç fonksiyonundaki değişkenler için katsayılar; - problemin ana kısıtlamalarındaki değişkenler için katsayılar; - kısıtlamaların sağ tarafı.

Doğrusal programlama bilinmeyenleri doğrusal kısıtlamalara tabi olan bir doğrusal fonksiyonun en büyük ve en küçük değerlerini bulma ve araştırma yöntemleri bilimidir. Dolayısıyla, doğrusal programlama problemleri bir fonksiyonun koşullu uç noktasıyla ilgili problemlerle ilgilidir. Koşullu bir uç nokta için birçok değişkenin doğrusal bir fonksiyonunu incelemek için, iyi geliştirilmiş matematiksel analiz yöntemlerini uygulamak yeterlidir, ancak bunları kullanmanın imkansızlığı oldukça basit bir şekilde gösterilebilir.

Aslında, doğrusal fonksiyonun uç noktası için yol araştırılmalıdır.

Z \u003d C 1 x 1 + C 2 x 2 + ... + C N x N

doğrusal kısıtlamalarla

bir 11 x 1 + bir 22 x 2 + ... + bir 1N X N \u003d b 1

bir 21 x 1 + bir 22 x 2 + ... + bir 2N X N \u003d b 2

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

bir M 1 x 1 + bir M 2 x 2 + ... + bir M N X N \u003d b M

Z doğrusal bir fonksiyon olduğundan, o zaman Z \u003d Сj, (j \u003d 1, 2, ..., n), o zaman doğrusal fonksiyonun tüm katsayıları sıfıra eşit olamaz, bu nedenle, sistem tarafından oluşturulan bölge içinde kısıtlamaların uç noktaları mevcut değildir. Alanın sınırında olabilirler, ancak kısmi türevler sabit olduğundan sınırın noktalarını araştırmak imkansızdır.

Doğrusal programlama problemlerini çözmek, özel yöntemlerin oluşturulmasını gerektiriyordu. Doğrusal programlama özellikle ekonomide yaygındır, çünkü birçok ekonomik problemde bulunan miktarlar arasındaki bağımlılıkların incelenmesi, bilinmeyenlere dayatılan doğrusal kısıtlamalarla doğrusal bir işleve yol açar.

Günümüzde ekonomi, finans ve yönetimle ilgili uzmanlıkların eğitim programı "Optimal kararlar için yöntemler" adı verilen bir disiplini içermektedir. Bu disiplinde öğrenciler optimizasyon, yöneylem araştırması, karar verme ve modellemenin matematiksel yönünü inceler. Bu disiplinin temel özelliği, matematiksel yöntemlerin ekonomik problemleri çözme uygulamalarıyla birlikte çalışmasıyla belirlenir.

Optimizasyon görevleri: genel bilgiler

Genel durumu ele alırsak, optimizasyon probleminin anlamı, belirli koşullar-kısıtlamaları altında amaç fonksiyonunu maksimize eden (en aza indiren) sözde optimal çözümü bulmaktır.

Fonksiyonların özelliklerine bağlı olarak optimizasyon problemleri iki türe ayrılabilir:

• doğrusal programlama problemi (tüm fonksiyonlar doğrusaldır);
• doğrusal olmayan programlama problemi (fonksiyonlardan en az biri doğrusal değildir).

Optimizasyon problemlerinin özel durumları doğrusal-kesirli, dinamik ve stokastik programlama problemleridir.

En çok incelenen optimizasyon problemleri, çözümleri yalnızca tamsayı değerleri alan doğrusal programlama problemleridir (LPP).

ZLP: formülasyon, sınıflandırma

Genel durumda, doğrusal bir programlama problemi, bazı doğrusal kısıtlamalar altında bir doğrusal fonksiyonun minimumunu (maksimumunu) bulmaktır.

Genel LPP'ye form sorunu denir

kısıtlamalarla

nerede - değişkenler, - verilen gerçek sayılar, - amaç fonksiyonu, - görev planı, (*) - (***) - kısıtlamalar.

LPP'nin önemli bir özelliği, objektif fonksiyonun uç noktasına, uygulanabilir çözümler bölgesi sınırında ulaşılmasıdır.

Optimal çözüm yöntemleri, aşağıdaki türlerdeki problemleri çözerken pratik bir ekonomik uygulama bulur:

• harmanlama görevleri (yani ürün kompozisyonunun planlanması);
• üretim planlamasında optimal kaynak tahsisi sorunu;

ZLP: örnekler

Karışım sorunu

Karışımlar sorununun çözümü, istenen özelliklere sahip bir karışım sağlayan belirli başlangıç \u200b\u200bmalzemelerinden oluşan en ucuz kümeyi bulmaktan ibarettir.

Kaynak tahsisi sorunu

İşletme üretir n üretimi için gerekli olan çeşitli ürünler m farklı kaynak türleri. Kullanılan kaynakların rezervleri sınırlıdır ve buna göre miktar b 1, b 2,…, b m cu Ek olarak, teknolojik katsayılar bilinmektedir bir ijkaç birim gösterir ben-Ürünün bir biriminin üretimi için kaynak gereklidir j-th tür (). Şirketin ürünün satışından elde ettiği kar j-th tür c j para birimleri Uygulama sırasında işletmenin karı en büyük olacak olan ürünlerin piyasaya sürülmesi için bir plan hazırlamak gerekir.

Karıştırma ve kaynak tahsisi sorunları için koşullar genellikle tablo biçiminde yazılır.

Kaynaklar	İhtiyaçlar			Hisse senetleri
	B 1	…	B n
A 1				b 1
…				…
Bir m				b m
Kar	c 1	…	c n

Karıştırma ve kaynak tahsisi sorunları birkaç yolla çözülebilir:

• grafiksel yöntem (matematiksel modelde az sayıda değişken olması durumunda);
• simpleks yöntemi (matematiksel modelde ikiden fazla değişken olması durumunda).

Taşıma görevi, belirli bir yapıya sahip bir görevler sınıfıdır. En basit nakliye problemi, bir ürünün tüm ürünlerin en düşük nakliye maliyetiyle hareket noktalarından varış noktalarına taşınması sorunudur.

Netlik ve algılama kolaylığı için, taşıma sorununun durumu genellikle aşağıdaki biçimde bir tabloya yazılır:

Genel olarak, nakliye sorununun çözümü birkaç aşamada gerçekleştirilir:

• Aşama I: ilk referans planının oluşturulması;
• Aşama II: optimallik için referans planın kontrol edilmesi;
• Aşama III: optimal değilse, referans planın netleştirilmesi.

İlk temel planı elde etmenin birkaç yöntemi vardır, örneğin, Northwest Corner Yöntemi, Vogel Yöntemi ve Düşük Maliyet Yöntemi.

Optimallik için planın kontrol edilmesi, potansiyel yöntem kullanılarak gerçekleştirilir:

- dolu hücreler için,
- boş hücreler için.

Plan optimal değilse, döngü oluşturma ve trafiğin yeniden dağıtımı gerçekleştirilir.

Sonuç

Tek bir makale çerçevesinde, optimal çözüm yöntemlerinin tüm teori ve pratiğini kapsamak mümkün değildir, bu nedenle, bu disiplin, problemler ve çözüm yöntemleri hakkında genel bir fikir vermeye izin veren yalnızca bazı noktalar dikkate alınmıştır.

Ek olarak, optimizasyon problemlerinin elde edilen çözümlerini kontrol etmek için MS Excel'deki "Bir çözüm ara" eklentisini çok etkili bir şekilde kullanabileceğinizi belirtmekte fayda var. Ancak bu aslında başka bir hikaye ve optimizasyon problemlerini çözme yöntemlerinin ayrıntılı bir değerlendirmesidir.

Optimum çözüm yöntemlerini öğrenmek için bazı öğreticiler şunlardır:

1. Bundy B.Doğrusal Programlamanın Temelleri: Per. İngilizceden - M .: Radyo ve iletişim, 1989. - 176 s.
2. Kremer N.Sh. Ekonomide Yöneylem Araştırması: Ders Kitabı. üniversiteler için el kitabı / N. Sh. Kremer, BA. Putko, I.M. Trishin, M.N. Friedman; Ed. prof. N.Sh. Kremer. - M .: ÜNİTE, 2005. - 407 s.

Sipariş için optimizasyon yöntemlerinin çözümü

En uygun çözüm yöntemleriyle her türlü sorunun çözümünde size yardımcı olabiliriz. Web sitemiz üzerinden sorunların çözümünü sipariş edebilirsiniz. Tek yapmanız gereken, son tarihi belirtmek ve görevle birlikte bir dosya eklemektir. siparişiniz ücretsizdir.

Optimal karar yöntemleri

İÇERİK

"Optimal çözüm yöntemleri" disiplininin ana hükümleri, bu uzmanlık için ana eğitim programı tarafından sağlanan özel disiplinlerin başarılı çalışması için önemli olan bir mezunun matematiksel eğitiminin temelidir.

Eğitim materyalinin etkili bir şekilde özümsenmesi ve nihai sertifikanın alınması için, müfredat tarafından sağlanan zaman çerçevesi içinde, kontrol görevlerini tamamlamak ve bunları öğretmene e-posta ile doğrulama için sağlamak gerekir. Disipline göre çalışma ve raporlama programı Tablo 1'de gösterilmektedir.

Tablo 1. "Optimal çözüm yöntemleri" disiplinindeki bağımsız çalışma takvimi

İçerik	Teslimat için son tarih	Değerlendirme kriterleri
1. teorik materyalin incelenmesi
2. Kontrol çalışmasının görevlerini çözme	Seanstan 1.5 ay önce	Her göreve on puanlık bir sistemde puan verilir
3. Son katılım için hazırlıkmülkler	Seans sırasında

1. GİRİŞ. PROBLEMİN GENEL BEYANI

Karar verme süreçleri, herhangi bir amaca yönelik faaliyetin merkezinde yer alır. Ekonomide, endüstriyel ve ekonomik organizasyonların yaratılmasından önce gelirler, optimal işleyişlerini ve etkileşimlerini sağlarlar. Bilimsel araştırmada - en önemli bilimsel problemleri vurgulamaya, onları incelemenin yollarını bulmaya, deneysel temelin ve teorik aparatın gelişimini önceden belirlemeye izin veriyorlar. Yeni teknoloji yaratırken, makinelerin, cihazların, cihazların, komplekslerin, binaların tasarımında, inşaatları ve işletmeleri için teknolojinin geliştirilmesinde önemli bir aşamayı oluştururlar; sosyal alanda, sosyal süreçlerin işleyişini ve gelişimini, ekonomik ve ekonomik süreçlerle koordinasyonunu organize etmek için kullanılırlar. Optimal (etkili) çözümler, hedefinize minimum işçilik, malzeme ve hammadde harcamasıyla ulaşmanızı sağlar.

Klasik matematikte, optimal çözümleri bulma yöntemleri, matematiksel programlamada ek fonksiyonların incelenmesi ile ilgili bölümlerde ele alınır.

Optimal karar yöntemleri, pratik örgütsel problemleri çözmek için kullanılan uygulamalı bir sibernetiğin yönü olan yöneylem araştırmasının bölümlerinden biridir. Matematiksel programlama problemleri, olası eylem modlarından birini (eylem programları) seçmenin gerekli olduğu çeşitli insan faaliyet alanlarında kullanılır.

Toplumda ortaya çıkan önemli sayıda görev, kontrollü fenomenlerle, yani bilinçli olarak alınan kararlar temelinde düzenlenen olaylarla ilişkilidir. Toplumun gelişiminin erken aşamalarında mevcut olan sınırlı miktarda bilgi ile, sezgi ve deneyime dayalı olarak ve daha sonra, incelenen fenomen hakkındaki bilgi miktarındaki artışla, bir dizi kullanılarak optimal bir karar verildi. doğrudan hesaplamalar. Bu, örneğin, endüstriyel işletmelerin çalışmaları için programların oluşturulması oldu.

Örneğin, çok partili ve çoklu ürün üretimine sahip modern bir sanayi kuruluşunda, girdi bilgilerinin hacmi o kadar büyük olduğunda, belirli bir karar vermek için işlenmesi modern kullanılmadan imkansız olduğunda tamamen farklı bir resim ortaya çıkar. elektronik bilgisayarlar. En iyi kararı verme sorunuyla bağlantılı olarak daha da büyük zorluklar ortaya çıkar.

"Optimal karar yöntemleri" dersinde karar verme, aşağıdaki ana aşamaların ayırt edilebildiği karmaşık bir süreç olarak anlaşılmaktadır:

1. aşama. İncelenen sorunun nitel bir modelini oluşturmak, yani en önemli gibi görünen faktörleri belirlemek ve uydukları kalıpları oluşturmak. Genellikle bu aşama matematiğin ötesine geçer.

2. aşama. İncelenen problemin matematiksel bir modelinin oluşturulması, yani nitel bir modelin matematiksel terimleriyle yazılması. Bu nedenle, matematiksel bir model, matematiksel sembollerle yazılmış gerçek bir fenomenin bir soyutlamasıdır, böylece analizi olgunun özüne nüfuz etmeyi mümkün kılar. Matematiksel model, fenomeni kontrol etmenin parametreleri olan bir dizi değişken arasındaki ilişkileri kurar. Bu aşama aynı zamanda değişkenlerin amaç fonksiyonunun, yani daha büyük (veya daha düşük) değeri karar açısından en iyi duruma karşılık gelen böyle bir sayısal karakteristiğin inşasını da içerir.

Böylece, bu iki aşamanın bir sonucu olarak, karşılık gelen matematik problemi oluşur. Dahası, ikinci aşama zaten matematiksel bilginin dahil edilmesini gerektirir.

3. aşama. Değişkenlerin amaç fonksiyonunun değeri üzerindeki etkisinin incelenmesi. Bu aşama, karar verme sürecinin ikinci aşamasında ortaya çıkan matematiksel problemleri çözmek için matematiksel aygıtın ustalığını sağlar.

Değişkenler üzerindeki koşulların eşitlikler ve eşitsizliklerle belirlendiği matematiksel modellerde, geniş bir kontrol problemleri sınıfı, bu tür uç problemlerden oluşur. Bu problemleri çözmek için kullanılan teori ve yöntemler tam olarak matematiksel programlamanın içeriğidir. Üçüncü aşamada, matematiksel aparat kullanılarak, karşılık gelen aşırı problemlere bir çözüm bulunur. Pratik sorunların çözülmesiyle ilişkili matematiksel programlama problemlerinin kural olarak çok sayıda değişken ve kısıtlamaya sahip olduğuna dikkat edelim. Uygun çözümleri bulmak için yapılan hesaplama işi o kadar fazladır ki, tüm süreç modern elektronik bilgisayarlar (bilgisayarlar) kullanılmadan tasarlanamaz, bu da ya belirli algoritmaları uygulayan bilgisayar programlarının oluşturulmasını ya da mevcut standart programlar.

4. aşama. 3. aşamada elde edilen hesaplama sonuçlarının simüle edilen nesne ile karşılaştırılması, yani sonuçların uzman doğrulaması (uygulama kriteri). Böylelikle bu aşamada modelin ve modellenen nesnenin yeterlilik derecesi ilk bilginin doğruluğu dahilinde belirlenir. Burada iki durum mümkündür:

1. durum. Karşılaştırma sonuçları tatmin edici değilse (modelleme sürecinin ilk aşamasında yaygın bir durum), o zaman sürecin ikinci döngüsüne geçin. Aynı zamanda modellenen nesneye ilişkin girdi bilgileri belirlenir ve gerekirse sorunun formülasyonu belirlenir (1. aşama); matematiksel model rafine edilir veya yeniden oluşturulur (2. aşama); karşılık gelen matematik problemi çözülür (aşama 3) ve son olarak karşılaştırma tekrar yapılır (aşama 4).

2. durum. Eşleşen sonuçlar tatmin ediciyse model kabul edilir. Hesaplamaların sonuçlarının pratikte tekrar tekrar kullanılması söz konusu olduğunda, modelin operasyon için hazırlanması sorunu ortaya çıkar. Örneğin, bir simülasyonun amacının bir işletme için üretim programları oluşturmak olduğunu varsayalım. Daha sonra modelin işleyişi, bilgilerin toplanmasını ve işlenmesini, işlenen bilgilerin bir bilgisayara girilmesini, geliştirilen program programlarına dayalı hesaplamaları ve son olarak hesaplama sonuçlarının (kullanıcılar için uygun bir biçimde) yayınlanmasını içerir. üretim faaliyetleri alanında kullanımları.

Matematiksel programlamada iki yön vardır.

İlk, zaten tam olarak belirlenmiş yön - matematiksel programlama doğru - tüm ilk bilgilerin tam olarak tanımlandığı varsayılarak deterministik problemleri içerir.

İkinci yön - sözde stokastik programlama - ilk bilginin belirsizlik unsurları içerdiği veya problemin bazı parametrelerinin bilinen olasılık özelliklerine sahip rastgele bir doğaya sahip olduğu problemleri içerir. Bu nedenle, üretim faaliyetlerinin planlanması genellikle, planın uygulanacağı gerçek durum hakkında eksik bilgi koşullarında gerçekleştirilir. Ya da, örneğin, aşırı bir problem otomatik cihazların çalışmasını simüle ettiğinde, rastgele girişimin eşlik ettiği durumlarda. Stokastik programlamanın temel zorluklarından birinin, esas olarak ilk bilgilerin analizinin karmaşıklığından dolayı, problemlerin tam olarak formüle edilmesinde yattığını unutmayın.

Geleneksel olarak, matematiksel programlamada aşağıdaki ana bölümler ayırt edilir:

Doğrusal programlama - amaç işlevi doğrusaldır ve amaç işlevinin uç noktasının arandığı küme, doğrusal eşitlikler ve eşitsizlikler sistemi tarafından belirlenir. Buna karşılık, doğrusal programlamada, yapısı genel problemleri çözme yöntemlerinden olumlu şekilde farklı olan, çözümleri için özel yöntemler oluşturmanıza izin veren problem sınıfları vardır. Böylece, doğrusal programlamada taşıma problemlerinin bir bölümü ortaya çıktı.

Doğrusal olmayan programlama - amaç işlevi ve kısıtlamalar doğrusal değildir. Doğrusal olmayan programlama genellikle aşağıdaki gibi alt bölümlere ayrılır:

Dışbükey programlama - amaç işlevi dışbükeydir (en aza indirilmesi sorunu dikkate alınırsa) ve aşırı problemin çözüldüğü küme dışbükeydir.

İkinci dereceden programlama - amaç işlevi ikinci dereceden ve kısıtlamalar doğrusal eşitlikler ve eşitsizliklerdir.

Çok uç görevler. Uzmanlaşmış problem sınıfları genellikle burada ayırt edilir ve uygulamalarda sıklıkla karşılaşılır, örneğin dışbükey bir içbükey fonksiyonlar setinde en aza indirme problemleri.

Matematiksel programlamanın önemli bir bölümü, değişkenlere tamsayı koşulları empoze edildiğinde tamsayı programlamadır.

Matematiksel programlamanın amacı, mümkün olduğunda, çözümü belirlemek için analitik yöntemler oluşturmak ve bu tür yöntemlerin yokluğunda, yaklaşık bir çözüm elde etmek için etkili hesaplama yöntemleri oluşturmaktır.

Son olarak, konunun adının - "optimal çözüm yöntemleri" - problem çözmenin amacının bir eylem programı seçmek olduğu gerçeğiyle ilişkili olduğunu not ediyoruz. Doğrusal programlama problemini daha ayrıntılı olarak ele alalım

2. DOĞRUSAL PROGRAMLAMA PROBLEMİNİN GEOMETRİK YORUMU

Doğrusal Programlama Problemi (LPP):

doğrusal formu maksimize eden bir X \u003d (x 1, x 2, ..., x n) vektörü bulun

F \u003d Σ c j x j → maks (2.1)

J \u003d 1

ve koşulları yerine getirmek:

Σa ij x j ≤ b ben (2.2)

J \u003d 1

x j ≥0, j \u003d 1,…, n (2.3)

Doğrusal fonksiyon F, problemin amaç fonksiyonu olarak adlandırılır.

Bu problemi vektör biçiminde yeniden yazalım:

Max fonksiyonunu bulalım:

F \u003d c 1 x 1 + c 2 x 2 +… + c n x n (2,4)

x 1 P 1 + x 2 P 2 +… + x n P n \u003d P 0, (2,5)

x j ≥0, j \u003d 1,…, n (2.6)

burada P 1, ..., P n ve P 0 m boyutlu vektör sütunlardır, problemin denklem sisteminin bilinmeyen ve serbest terimlerindeki katsayılardan:

B 1 a 11 a 12 a 1n

P 0 \u003d (b 2); P 1 \u003d (bir 21); P 2 \u003d (bir 22); ……. P n \u003d (bir 2n); (2.7)

… … … …

B n a m1 a m2 a mn

X \u003d (x 1, x 2, ..., x n) planı, pozitif katsayılar x j doğrusal olarak bağımsız P j vektörlerini temsil ediyorsa, ana LPP'nin temel planı olarak adlandırılır.

Temel doğrusal programlama probleminin herhangi bir boş olmayan tasarım setine çözüm politopu ve çözüm politopunun herhangi bir köşe noktasına tepe noktası denir.

Teoremi

Ana LPP'nin optimal bir planı varsa, sorunun nesnel işlevi, karar polihedronunun köşelerinden birinde maksimum değeri alır.

Problemin amaç işlevi birden fazla tepe noktasında maksimum değeri alırsa, bu köşelerin dışbükey doğrusal kombinasyonu olan herhangi bir noktada onu alır.

Bulgular:

Temel LPP'nin boş olmayan plan seti, dışbükey bir çokyüzlü oluşturur;

Bu çokyüzlünün her köşesi bir referans planı tanımlar;

Polihedronun köşelerinden birinde, amaç fonksiyonunun değeri maksimumdur.

İki boyutlu LPP durumu

Fonksiyonun maksimum değerini belirlemekten oluşan soruna bir çözüm bulalım.

F \u003d c 1 x 1 + c 2 x 2 (2,8)

koşullar altında

bir ben1 x 1 + bir ben2 x 2 ≤ b ben, (i \u003d 1, ..., k) (2.9)

x j ≥0 (j \u003d 1,2) (2,10)

Doğrusal programlama problemi, F amaç fonksiyonunun maksimum değerini aldığı çözüm poligonunun bir noktasını bulmaktır. Bu nokta, çözüm poligonu boş olmadığında ve amaç fonksiyonu yukarıdan sınırlandırıldığında mevcuttur.

Bu tepe noktasını belirlemek için, çözüm poligonundan geçen bir c 1 x 1 + c 2 x 2 \u003d h düzey çizgisi oluşturuyoruz (burada h bir sabittir) ve onu C \u003d (vektörü) yönünde hareket ettireceğiz. c 1, c 2) çözüm poligonu ile son ortak noktasından geçene kadar. Belirtilen noktanın koordinatları bu görev için en uygun planı belirler.

LPP'yi geometrik yöntemle çözme aşamaları:

1. (2.9), (2.10) denklemlerine göre düz çizgiler oluşturun.

2. Problemin kısıtlamalarının her biri tarafından tanımlanan yarı düzlemleri bulun.

3. Çokgen çözümlerini bulun.

4. Vektör C'yi oluşturun.

5. Çözüm çokgeninden geçen bir c 1 x 1 + c 2 x 2 \u003d h doğrusu oluşturun.

6. c 1 x 1 + c 2 x 2 \u003d h doğrusunu C vektörü yönünde hareket ettirin.

7. Fonksiyonun maksimum noktasının koordinatlarını belirleyin ve bu noktada amaç fonksiyonunun değerini hesaplayın.

Örnek 1.

Şirket, A ve B olmak üzere iki tür ürünün üretimi için üç tür hammadde kullanmaktadır. Bu tür bir ürünün bir biriminin üretimi için her tür hammadde tüketim oranları Tablo 2.1'de gösterilmektedir. Aynı zamanda, her türden bir ürünün satışından elde edilen karı ve bu türden işletmenin kullanabileceği toplam hammadde miktarını gösterir.

Tablo 2.1

İÇİNDEidy ham maddeler	Hammadde tüketim oranları (kg) bir ürün için		Toplam hammadde miktarı (kg)
	VE	İÇİNDE
1	12	4	300
2	4	4	120
3	3	12	252
Bir ürünün satışından elde edilen kâr (RUB)	30	40

A ve B ürünlerinin her oranda üretilebileceğini düşünmekniyah (satış sağlandı), serbest bırakılmaları için böyle bir plan hazırlamak gerekir.işletmenin tüm ürünlerin satışından elde ettiği kazanç maksimumdurküçük.

Karar:

х1 - A tipi ürünlerin üretimi

х2 - B tipi ürünlerin üretimi

O zaman sorun kısıtlamaları şunlardır:

A ve B tipi ürünlerin satışından elde edilen toplam kar: F \u003d 30x 1 + 40x 2 olacaktır.

Geometrik yorumunu kullanarak probleme bir çözüm bulalım.

Bunun için, kısıtlama sisteminin eşitsizliklerinde eşitliklere geçiyoruz ve karşılık gelen düz çizgileri oluşturuyoruz:

B noktasının koordinatlarını bulalım - düz çizgilerin kesişimleri:

Bu denklem sistemini çözdükten sonra şunu elde ederiz: x 1 \u003d 12; x 2 \u003d 18

Bu nedenle, işletme 12 A tipi ürün ve 18 B tipi ürün üretiyorsa, o zaman maksimum kar elde edecektir.

F max \u003d 30 12 + 40 18 \u003d 1080 ruble.

Örnek 2.

LPP'yi çözün

maks (min) F \u003d 2x 1 + 3x 2;

Karar. Uygulanabilir çözümlerin bölgesini oluşturmak için, x 1 Ox 2 sisteminde bu eşitsizlik kısıtlamalarına karşılık gelen sınır çizgilerini oluşturuyoruz:

x 1 + x 2 ≤ 6, x 1 + 4x 2 ≥ 4, 2x 1 -x 2 ≥ 0.

Bu eşitsizliklerin tuttuğu yarı düzlemleri bulun. Bunu yapmak için, herhangi bir yarı düzlemin dışbükeyliğinden dolayı, karşılık gelen sınır çizgisinin geçmediği keyfi bir noktayı almak ve bu test noktasının eşitsizlik kısıtlamasını karşılayıp karşılamadığını kontrol etmek yeterlidir. Varsa, bu eşitsizlik deneme noktasını içeren yarı düzlemde de geçerlidir. Aksi takdirde, numune noktası içermeyen bir yarım düzlem alınır. O (0; 0) koordinatlarının başlangıç \u200b\u200bnoktasını test noktası olarak almak genellikle uygundur. Örneğimiz için, uygulanabilir çözümlerin alanı ABCD dörtgeninin nokta kümesidir (Şekil 6).

Bir c \u003d (c 1; c 2) \u003d (2; 3) vektörü oluşturuyoruz. Sadece amaç fonksiyonunun artış yönünü açıklığa kavuşturmak gerektiğinden, bazen daha fazla netlik için, λс (λ\u003e 0) oluşturmak uygundur. C vektörüne dik olan bir F \u003d 0 seviye çizgisi çizin. Düz F \u003d 0 çizgisinin paralel yer değiştirmesiyle, amaç fonksiyonunun maksimum değeri aldığı ve minimum değere ulaşıldığı A noktasını aldığı en uç B noktasını buluruz.

B noktası koordinatları sistem tarafından belirlenir

Buradan Fmax \u003d F (A) \u003d 32/9

BAĞIMSIZ ÇÖZÜM İÇİN GÖREVLER

1.1-1.10 görevleri grafiksel olarak çözün.

Çok değişkenli problem

Aşağıdaki doğrusal programlama problemini düşünün

Bunu grafiksel olarak çözmek için, kısıtlama sistemini, ana görev biçiminde sistem 2'den fazla değişken içermeyecek şekilde dönüştürmek gerekir.

Bu, değişkenler veya Jordan-Gauss yöntemi hariç olmak üzere sıralı olarak yapılabilir. Jordan-Gauss yöntemini düşünün.

tablo 1

	x 1	x 2	x 3	x 4	x 5	b
	7 3 2 2	3 1 1 1	6 3 3 -1	1 1 0 0	1 0 1 -1	10 3 4 0

(-3) 1 , (-1) 3,4

Tablo 2

x 2

-2 3 1 -1

0 1 0 0

-3 3 0 -4

-2 1 1 -1

1 0 -1 -1

1 3 -1 -3

(2) 1 , (-1) 2 ,(1) 3

Tablo 3

x 2 x 4

0 2 1 0

0 1 0 0

3 3 0 -4

0 0 1 0

1 1 -1 -2

1 4 -1 -4

(-1) 2 , (1) 3 ,(2) 4

Tablo 4

x 5 x 2 x 4

0 2 1 0

0 1 0 0

3 0 3 2

0 0 1 0

1 0 0 0

1 3 0 -2

(-1) 2 , (1) 3 ,(2) 4

Sınırlama denklemlerinde negatif olmayan izin verilen bilinmeyenleri atıyoruz

x 2, x 4, x 5 ve eşittir işaretini eşitsizlik işaretleri ile değiştirirsek, iki değişkenli bir yardımcı doğrusal programlama problemi elde ederiz:

F (x) \u003d 2 x 3 +2 → en fazla

F (x) \u003d 0: 2 x 3 +2-0 (0; -1); (5; -1)

F max \u003d 2, x 1 \u003d 0'da; x 3 \u003d 0

3. BİR DOĞRUSAL PROGRAMLAMA PROBLEMİNİ ÇÖZMEK İÇİN BASİT BİR YÖNTEM

3.1. Simpleks yönteminin geometrik yorumu

Doğrusal programlama problemi optimize edilirse, optimum O.D.R.'nin köşe noktasına (en az bir) karşılık gelir. ve negatif olmayan temel çözümlerin en az biriyle çakışır. Böylece, sistemin negatif olmayan sınırlı sayıda temel çözümüne bakarak, bunlardan nesnel fonksiyonun aşırı değerine karşılık gelen çözümü seçeriz. Grafiksel olarak bu, çözüm polihedronunun köşe noktaları üzerinde yinelediğimiz ve amaç fonksiyonunun değerini artırdığımız anlamına gelir.

Tek yönlü yöntem şunlardan oluşur:

1) soruna ilk kabul edilebilir temel çözümün belirlenmesi;

2) daha iyi bir çözüme geçmek;

3) en uygun uygulanabilir çözümün kontrol edilmesi.

3.2. Simpleks yönteminin tablo şeklinde yorumlanması

Tek yönlü yöntem, kanonik biçimde yazılmış doğrusal programlama problemlerini çözmek için kullanılır:

En uygun çözümü bulun

X \u003d (x 1, x 2, ..., x n) (3.1)

kısıtlar sistemini tatmin etmek (denklemler)

Σa ij x j \u003d b ben (ben \u003d 1, m) (3.2)

j \u003d 1

ve x j ≥ 0 (j \u003d 1, n) koşulları

ve amaç fonksiyonunun en uç değerini vermek

Z (x) \u003d Σ c j x j (3,3)

j \u003d 1

X 1, x 2, x 3… x m temel bilinmeyenler ve x m + 1, x m + 2,…, x n serbest bilinmeyenler olduğunda, sistemin (3.2) negatif olmayan ilk temel çözümünü bulun.

Daha sonra sistem (3.2) izin verilen bir sisteme dönüşür

(3.4)

Bu sistem, formun negatif olmayan bir temel çözümüne karşılık gelir

X 0 \u003d (b 1, b 2, ..., b m, 0,0 ... 0)

Ortaya çıkan çözümü amaç işleviyle değiştirin

Δ 0 \u003d L (X 0) \u003d Σ C j B j (3,5)

J \u003d 1

ve onu yalnızca özgür bilinmeyenlere bağlı olacak şekilde dönüştürün x m + 1, x m + 2, ... x n

Tüm temel bilinmeyenleri x 1, x 2, x 3 ... x m serbest olarak ifade ediyoruz x m + 1, x m + 2, ... x nve onu amaç işlevine koyun.

Ardından amaç işlevi (3.6) şeklini alır

Serbest bilinmeyenlerin Δ j tahmini kavramını sunuyoruz

(3.7)

Daha sonra amaç işlevi biçimi alır

(3.8)

C \u003d (c 1, c 2, ..., c m) ve B \u003d (a 1j, a 2j,…, a mj) (j \u003d m + 1, n) vektörlerini tanıtalım eşitlik (3.7) vektör formunda yazılabilir

Δ j \u003d CB j -c j (3,9)

Eşitlik (3.8), yazı karakteri açısından sistemin denklemlerinden farklı değildir, bu nedenle onu bu sisteme ekliyoruz ve genişletilmiş bir sistem elde ediyoruz:

Bir sistem şeklinde kaydedilen, gerçekleştirilen dönüşümlerin sonuçları aşağıdaki simpleks tabloya girilebilir:

B.N.	C	B	c 1	c 2	...	santimetre	c m + 1	...	c j	...	c n
			x 1	x 2	...	x m	x m + 1	...	x j	...	x n
x 1	c 1	β 1	1	0	...	0	bir 1 (m + 1)	...	bir 1j	...	bir 1n
x 2	c 2	β 2	0	1	...	0	bir 2 (m + 1)	...	bir 2j	...	bir 2n
...	...	...	...	...	...	...	...	...	...	...	...
x m	santimetre	β m	0	0	...	1	bir m (m + 1)	...	bir mj	...	bir dakika
L (X)	Δ j ≥0	Δ 0	0	0	...	0	Δ m + 1	...	Δ j	...	Δ n

ilk sütun temel bilinmeyenleri içerir x 1, x 2,…, x m; c sütunu, bu temel bilinmeyenlere karşılık gelen amaç işlevinden katsayıları içerir; B sütununda - orijinal negatif olmayan temel çözüm X 0'ın pozitif bileşenleri ile çakışan sistemin denklemlerinin serbest terimleri. Bilinmeyenler x 1, x 2,…, x n altında, sütunlar sistemden katsayıları içerir.

Puan veya dizin adı verilen bu tablonun son satırı, p formüllerle hesaplanır. Bir temel çözümdendiğerine göre, değerlendirme satırı doğrudan kural ile de hesaplanabilir gon (Jordan-Gauss yöntemi).

Tahmin edilen satırda, Δ j ≥0 eşitsizliği, temel planın optimallik kriterini ifade eder.

Simpleks yöntemini kullanarak LPP'yi çözmek için algoritma.

1. Bir referans planı bulun.

2. Bir tek yönlü tablo oluşturun.

3. En az bir negatif sayı olup olmadığını öğrenin Δ j

Değilse, bulunan temel plan en uygunudur. Rakamlar arasında Δ j negatif varsa, o zaman sorunun karar verilemezliği belirlenir. chi veya yeni bir başlangıç \u200b\u200bnoktasına gidin.

4. Baştaki sütunu ve satırı bulun. En büyük sütun, mutlak değer Δ j'deki en büyük negatif sayı ile belirlenir. ve kılavuz sıra, Р 0 vektörünün sütun bileşenlerinin, kılavuz sütunun pozitif bileşenlerine oranlarının minimumudur.

5. Formülleri (3.7) - (3.9) kullanarak, pozitif bileşenleri belirleyinyeni temel plan, vektörlerdeki P j vektörlerinin genişleme katsayıları yeni temel ve sayı. Tüm bu sayılar yeni bir simpleks ile yazılmıştırtablo.

6. Optimallik için bulunan planı kontrol edin. Plan optimal değilse ve yeni bir temel plana geçmek gerekiyorsa, 4. adıma dönün ve optimal bir planın elde edilmesi veya bir sorunu çözme sürecini çözer.

Örnek 3.1.

Şirket, A, B ve C gibi çeşitli ürünlerin üretimi için üç farklı türde hammadde kullanıyor. Her türden bir ürünün üretimi için hammadde tüketim oranları, bir ürün A, B ve C'nin fiyatı ve toplam miktar yapmak için kullanılabilecek her türden hammaddebiz tabloda verilmiştir.

Toplam maliyetin olduğu ürünler için bir üretim planı hazırlayın Üretilen tüm ürünlerin oranı maksimize edilecektir.

Karar:

Matematiksel bir model yapalım. Biz şunu belirtiyoruz:

x 1 - A tipi ürünlerin üretimi;

x 2 - B tipi ürünlerin üretimi;

х3 - C tipi ürünlerin üretimi

Kısıtlama sistemini yazalım:

Üretilen malların toplam değeri:

F \u003d 9x 1 + 10x 2 + 16x 3

Ekonomik içerik açısından, x 1, x 2, x 3 değişkenleri yalnızca negatif olmayan değerler alabilir:

x 1, x 2, x 3 ≥0

Bu sorunu ana LPP şeklinde yazıyoruz, bunun için eşitsizlikler sisteminden eşitliklere geçiyoruz, bunun için üç ek değişken ekliyoruz:

Yeni değişkenlerin ekonomik anlamı, belirli bir üretim planı için kullanılmayan bir veya diğer türdeki hammadde miktarıdır.

Dönüştürülmüş denklem sistemini vektör biçiminde yazalım:

x 1 P 1 + x 2 P 2 + x 3 P 3 + x 4 P 4 + x 5 P 5 + x 6 P 6 \u003d P 0

nerede

Рj vektörleri arasında üç birim vektör olduğu için, bu problem için, Р 4, Р 5 birim vektörleri sistemi tarafından belirlenen referans plan X \u003d (0, 0, 0, 360, 192, 180) yazmak mümkündür. , Р 6, üç boyutlu uzayın temelini oluşturur.

I yinelemesinin bir simpleks tablosunu çizip F 0, z j -c j değerlerini hesaplıyoruz.

Optimallik için orijinal planı kontrol ediyoruz:

F 0 \u003d (C, P 0) \u003d 0; z 1 \u003d (C, P 1) \u003d 0; z 2 \u003d (C, P2) \u003d 0; z 3 \u003d (C, P 3) \u003d 0;

z1-c 1 \u003d 0-9 \u003d -9; z2-c2 \u003d 0-10 \u003d -10; z3-c3 \u003d 0-16 \u003d -16;

Temel vektörler için z j -c j \u003d 0 (j \u003d 4,5,6).

Maksimum negatif sayı Δ j, P 3 sütununun 4. satırındadır. Bu nedenle, Р 3 vektörünü temele dahil ediyoruz. Bir vektör konusu tanımlayalım temelden eleme, bunun için i3\u003e 0 için Θ 0 \u003d min (b i / a ij), yani Θ \u003d dk (360/12; 192/8; 180/3) \u003d 192/8 \u003d 24.

Şunlar. C ürünlerinin üretimi için sınırlayıcı faktör iI tipi mevcut hammadde hacmi. İşletme, mevcudiyetini hesaba katarak 24 C ürününü üretebilirken, tip II hammadde tamamen tüketilecektir.vano.

Bu nedenle, Р 5 vektörü temelden çıkarılmalıdır. Sütun р 3 ve 2. sıra vektörleri kılavuzlardır.

II yinelemesinin bir tablosunu oluşturalım. İlk olarak, temele yeni girilen vektörün satırını dolduruyoruz, yani. kılavuz çizgisi 2. Bu çizginin elemanları, tablo 1'deki karşılık gelen elemanların izin veren eleman (yani 8). Bu durumda, C b sütununa katsayıları yazıyoruzcient С 3 \u003d 16, tabana eklenen Р 3 vektörünün sütununda duruyor

Tablo II'nin kalan unsurlarını belirlemek için üçgen kuralını uyguluyoruz.

Tablo II'nin elemanlarını P 0 sütununda hesaplayalım.

İlk öğe - üç sayı bulun

1) P0 sütunu ile 1. sıranın (360) kesiştiği noktada 1. noktada duran sayı;

2) P3 sütunu ile 1. sıranın (12) kesiştiği noktada 1. noktada duran sayı;

3) P0 sütunu ile 2. sıranın (24) kesiştiği noktada 2. noktada duran sayı.

360-12 24 \u003d 72

İkinci eleman daha önce hesaplandı (Θ 0 \u003d 192/8 \u003d 24)

Üçüncü unsur

1) P0 sütunu ile 3. sıranın (180) kesiştiği noktada 1. noktada duran sayı;

2) P3 sütunu ile 3. sıranın (3) kesiştiği noktada 1. noktada duran sayı;

3) P0 sütunu ile 2. sıranın (24) kesiştiği noktada 2. noktada duran sayı.

180-324 \u003d 108

Aynı sütunun 4. satırındaki F 0 değeri iki şekilde bulunabilirbami:

1) F 0 \u003d (C, P 0) \u003d formülüne göre 0 72 + 16 24 + 0 108 \u003d 384;

2) üçgen kuralına göre:

Р 1 v.2 vektörünün elemanlarını hesaplayalım. Sütundan ilk iki sayıyı alıyoruztsov R 1 ve R 3 cilt 1,

ve üçüncü sayı - 2. satırın ve Р1 sütununun kesişme noktasındaki 2. noktadan.

18-12 (3/ 4) = 9; 5-3 (3/ 4)=11/ 4.

Tablo 2'deki P 1 vektörünün sütununun 4. satırındaki z 1-c 1 sayısı

iki şekilde bulunabilir:

1) z 1 -с 1 \u003d (C, P 1) -c 1 formülüne göre:

0 9 + 16 3/4 + 0 11 / 4-9 \u003d 3

2) elde ettiğimiz üçgen kuralına göre:

-9-(-16) 3/ 4 = 3

Benzer şekilde, P 2 vektörünün sütununun elemanlarını buluyoruz.

Р 5 vektörünün sütun elemanları, üçgen kuralına göre hesaplanır.

farklı görünüyor; ancak, bu unsurları tanımlamak için oluşturulan üçgenler

Belirtilen sütunun 1. satırının elemanını hesaplarken,0; 12 ve 1/8 sayılarından oluşan üçgen. Bu nedenle arananeleman eşittir

0 – 12 (1/8) = -3/2.

Bu sütunun 3. satırındaki öğe

0 - 3 (1 /8) = -3/8.

Tüm unsurların hesaplanmasının sonunda, içindeki Tablo II yeni aldıtemel plan ve temel olarak Р j vektörlerinin genişleme katsayılarıp 4, P 3, P 6 vektörleri ve F 0 "Δ j" değerleri.

Bu tablodan da görebileceğiniz gibi, sorun için yeni temel planplan X \u003d (0; 0; 24; 72; 0; 108).

II yinelemesinde bulunan problem planı optimal değildir.

bu satırın negatif bir numarası vardır - 2. Bu, P 2 vektörünün sütununda olduğu için Tablo 2'nin 4. satırından da görülebilir. .

Bu, P 2 vektörünün temele sokulması gerektiği, yani yeni planın V'nin serbest bırakılmasını sağlaması gerektiği anlamına gelir.

B ürünlerinin olası üretim sayısını belirlerken, her türden mevcut hammadde miktarı, yani: b ürünlerinin çıktısı i2 "\u003e 0 için min (bi" / ai 2 ") ile belirlenir, yani Θ 0 \u003d min (72/9; 24 · 2/1; 108 · 2/3) \u003d 72 buluruz / 9 \u003d 8.

Sonuç olarak, P4 vektörü temelden muaf tutulmaya tabidir, başka bir deyişle, B ürünlerinin çıktısı, işletme için mevcut olan tip I hammaddelerle sınırlıdır. Bu hammaddenin mevcut hacimlerini hesaba katarak, işletme 8 ürün B yapmalıdır. 9 sayısı çözümleyici unsurdur ve P2 vektörünün sütunu ve Tablo 2'nin 1. satırı kılavuzlardır.

III yineleme için bir tablo oluşturalım.

Tablo III'te, önce tabana yeni eklenen P2 vektörünün satırı olan 1. sıranın elemanlarını dolduruyoruz. Bu sıranın elemanları, Tablo 2'nin 1. sırasının elemanlarından, ikincisini çözümleyici elemana (yani 9'a) bölerek elde edilir.

Bu durumda bu satırın C b sütununa 2 \u003d 10 olarak yazıyoruz.

Ardından, temel vektörlerin sütunlarının elemanlarını doldururuz ve üçgen kuralına göre kalan sütunların elemanlarını hesaplar.

Sonuç olarak, Tablo III'te yeni bir referans planı X \u003d (0; 8; 20; 0; 0; 96) ve P j vektörlerinin P 1, P 2 ve P temel vektörleri aracılığıyla genişleme katsayılarını elde ediyoruz. 3 karşılık gelen değerler F 0 "" ve Δ j ...

Verilen temel planın optimal olup olmadığını kontrol ederiz. Bunu yapmak için 4. sıra, tablo 3'ü düşünün. Bu satır negatif sayı içermez. Bu, bulunan temel planın optimal olduğu ve Fmax \u003d 400 olduğu anlamına gelir.

Bu nedenle, 8 ürün B ve 20 ürün C üretimini içeren üretim planı optimaldir. Bu üretim planı ile I ve II tipi hammaddeler tamamen kullanılmakta ve 96 kg tip III ham madde kullanılmadan kalmaktadır ve üretilen ürünlerin maliyeti 400 € 'dur.

Optimal üretim planı, A ürünlerinin imalatını sağlamaz. A tipi ürünlerin üretim planına dahil edilmesi, belirtilen toplam maliyette bir düşüşe yol açacaktır. Bu, P1 vektörünün sütununun 4. satırından görülebilir; burada 5 sayısı, belirli bir plan için, A ürününün bir biriminin serbest bırakılmasına dahil edilmesinin yalnızca toplam değerde bir azalmaya yol açtığını gösterir. maliyetin 5 € 'dur.

Örnek 3.2

Aşağıdaki LPP için ilk simpleks tablosunu tamamlayın:

Karar:

Aşağıdakileri gösterilen sırayla yapalım:

-İkinci satıra bilinmeyenleri x 1, x 2,…, x 5 yazıyoruz;

- üstlerindeki ilk satırda - amaç fonksiyonundan karşılık gelen 3, -2, 1.4, -1 katsayıları;

- x 1, x 2,…, x 5 bilinmeyenlerin altında, orijinal sistemin denklemlerinin sol taraflarının karşılık gelen katsayılarından oluşan sütunları doldurun;

Sütuna 3,1,5 denklemlerinin serbest terimlerini yazıyoruz;

- ilk sütun B'de s. bilinmeyenleri koy x 2 , x 3 , x 5 , altlarında birim sütunlar olduğu için onları temel olarak ele alacağız; temel bilinmeyenler, sütunlardaki birimler aynı bilinmeyenlerin kesişme noktasında olacak şekilde düzenlenmiştir;

- sütuna, seçilen temel bilinmeyenlerle amaç fonksiyonundan -2,1, -1 katsayılarını yazıyoruz x 2 , x 3 , x 5 ;

-Tahmini satırı aşağıdaki gibi doldurun: B sütununun altına formül (3.5) ile hesaplanan Δ 0 sayısını yerleştiririz; temel bilinmeyenlerin altında x 2 , x 3 , x 5 - eşitlikten de elde edilebilen sıfırlar (3.9); serbest değişkenler altında x 1 , x 4 - eşitlikten elde edilen değerleri yazıyoruz (3.9).

Bu eylemlerin sonuçlarını aşağıdaki tabloya yazacağız:

Çözümleme sütununu x 4 olarak en "kötü" olarak seçelim (mutlak değerdeki en büyük negatif tahmine karşılık gelir). Ardından, çözümleme satırını şu şekilde tanıtıyoruz: x 4 sütununun pozitif katsayıları için, b i / a i4 oranlarını hesaplıyoruz ve bunları grafiğe θ yazıyoruz.

En küçük sayı çözümleme dizesini belirleyecektir. Sistemin denklemlerinin sağ tarafındaki obsesiflik olmaması ve en azından amaç fonksiyonunun azalmaması gerekliliği nedeniyle negatif ve sıfır katsayıları dikkate almıyoruz.

Çözümleme çizgisi ile çözümleme sütununun kesişme noktasında, çözümleyici öğeyi seçin. Çözümleme elemanını, ilk satırı ikiye böldüğümüz bire eşit yapalım. Sonra, tabloyu Jordan-Gauss yöntemini kullanarak dönüştürüyoruz.

Böylece, zaten ikinci adımın tablosunda, optimallik kriteri yerine getirilmiş olur. Optimal plan X (0; 0; 11/2; 3/2; 13/2), maks L (X) \u003d 5'i aldık.

GÖREV 1. Doğrusal programlama problemlerini çözmek için simpleks yöntem
Çeşitli ürün 1, 2, 3 ve 4 türlerinin üretimi için işletme, A, B ve C olmak üzere üç tür hammadde kullanır.Her bir ürün türünün bir biriminin üretimi için hammadde tüketim oranları, bir ürünün fiyatı ve her tür kaynağın stoğu bilinmekte ve Tablo 1.1'de gösterilmektedir.
Şirketin maksimum kar elde edeceği ürünlerin üretimi için bir plan yapın.

Sorunun ilk verilerini seçeneğe göre Tablo 1.1, 1.2'de seçin.

Tablo 1.1 - Her türden ürün birimi başına kaynak maliyeti oranları (tüm seçenekler için ortak)

KAYNAK	ÜRÜN TİPLERİ				Stok
	1	2	3	4
VE	6	8	4	7	bir 5
İÇİNDE	0,75	0,64	0,5	0,8	bir 6
FROM	8	12	10	14	bir 7
EKONOMİK			bir 3	bir 4	MAX

Problem çözme planı:

1. sürümünüzün kaynak verilerini tablolardan seçin;
2. bilinmeyen görevleri belirleyin;
3. bir kısıtlama sistemi ve görevin hedef işlevini oluşturmak;
4. ek değişkenler belirleyerek ve ekleyerek kısıtlama sistemini kanonik biçime getirmek;
5. simpleks bir tablo çizin ve orijinal temel planla doldurun;
6. simpleks yönteminin algoritmasını kullanarak, soruna en uygun çözümü bulun;

PROBLEM 2
Potansiyel yöntemi kullanarak açık bir ulaşım probleminin çözümü
Toptan satış depoları A 1, A 2, A 3, A 4, B 1, B 2, B 3, B 4, B 5 mağazalarına teslim edilmesi gereken bazı ürünlerin bilinen miktarlarda stoklarına sahiptir. bir ürünün bir biriminin her depodan her mağazaya taşınması.
Mağazaları, nakliye maliyetlerinin minimum olacağı depolara eklemek için bir seçenek bulun.
Sorunun ilk verilerini seçeneğe göre Tablo 2.1, 2.2'de seçin.
Tablo 2.1 - Tarife matrisi (tüm seçenekler için ortaktır)

Toptan depolar	Dükkanlar					Hisse senetleri
	1 İÇİNDE	2 İÇİNDE	3 İÇİNDE	AT 4	AT 5
A 1	5	4	10	7	8	bir 6
A 2	7	6	7	10	6	bir 7
A 3	2	9	5	3	4	bir 8
A 4	6	11	4	12	5	bir 9
İhtiyaçlar			bir 3	bir 4

Problem çözme planı:

1. Çözülen sorunun kapalı mı yoksa açık mı olduğunu kontrol edin.
2. Sorun açıksa, çözmeye başlamayı mümkün kılan işlemleri gerçekleştirin.
3. Ulaştırma probleminin matrisini çizin ve bildiğiniz üs planını oluşturma yöntemlerinden birini kullanarak (kuzey-batı köşesinin yöntemi, en iyi tarife, çift tercih) temel planı buna yazın.
4. Dejenerasyon için inşa edilmiş destek planını kontrol edin. Gerekirse destek planındaki yozlaşmanın üstesinden gelmek için önlemler alın.
5. Temel plan için amaç fonksiyon değerini hesaplayın.
6. Potansiyel yöntemin kurallarını kullanarak satırların ve sütunların potansiyellerini hesaplayın.
7. Bulunan potansiyelleri kullanarak, optimallik için inşa edilmiş destek planını kontrol edin.
8. Çözüm optimumsa 13. adıma gidin.
9. Çözüm optimal değilse iyileştirilmesi gerekir. Bunu yapmak için, geliştirilecek taşıma problem matrisinin bir hücresini bulmanız, bunun için kapalı bir döngü oluşturmanız ve bu döngünün köşeleri boyunca hareket edecek kaynakların miktarını belirlemeniz gerekir.
10. Kaynakları, matrisin satırları ve sütunları arasındaki dengeyi bozmadan döngünün köşeleri boyunca taşıyın.
11. 6. adıma gidin.
12. En uygun çözümü yazın ve ekonomik analizini yapın.

GÖREV 3. Optimum kaynak tahsisi.
Firmanın yönetim kurulu, firmanın sahip olduğu dört işletmede homojen ürün çıktısını artırmak için üretim kapasitesini artırma önerisini değerlendiriyor.
İşletmeleri modernize etmek için Yönetim Kurulu 250 milyon ruble yatırım yapacak. 50 milyon ruble farkla. Çıktıdaki artış, tahsis edilen miktara bağlıdır, değerleri işletmeler tarafından sağlanır ve tabloda yer almaktadır.
Firmaya maksimum çıktı artışı sağlayan işletmeler arasında bir yatırım teklifi bulun ve işletme başına yalnızca bir yatırım yapılabilir.
Sorunun ilk verilerini seçeneğe göre Tablo 3.1, 3.2'de seçin.
Tablo 3.1 - Görev parametrelerinin değerleri

Yatırımlar, milyon ruble	Üretim çıktısında artış, milyon ruble
	şirket	şirket	şirket	şirket
50	bir 11	bir 12	bir 13	bir 14
100	bir 21	bir 22	bir 23	bir 24
150	31	bir 32	bir 33	bir 34
200	bir 41	bir 42	bir 43	bir 44
250	51	bir 52	bir 53	bir 54

Problem çözme planı:

1. Tablolardan sürümünüzün kaynak verilerini seçin.
2. Yatırım yapılması gereken işletme sayısına göre sorunun çözümünü aşamalara ayırın.
3. Yineleme ilişkileri oluşturun
4. Yatırımlar sadece ilk işletmeye tahsis edildiğinde, hesaplamanın ilk aşamasını gerçekleştirin
5. Yatırımlar birinci ve ikinci işletmelere tahsis edildiğinde, hesaplamanın ikinci aşamasını gerçekleştirin
6. Yatırımlar 1-3 işletmeye tahsis edildiğinde hesaplamanın üçüncü aşamasını gerçekleştirin
7. Yatırımlar dört işletmeye dağıtıldığında, hesaplamanın dördüncü aşamasını gerçekleştirin
8. En uygun çözümü yazın ve ekonomik analizini yapın.