Dışbükey kümeler ve özellikleri. Bir dışbükey kümenin özelliklerini incelemek için, bir dışbükey kümenin kesin bir tanımını vermek gerekir. Daha önce bir dışbükey küme, herhangi iki noktasıyla birlikte onları birbirine bağlayan bir doğru parçası içeren bir küme olarak tanımlanıyordu.

Bir segment kavramının birkaç nokta için genelleştirilmesi, bunların dışbükey doğrusal birleşimidir.

X noktasına denir dışbükey doğrusal kombinasyon puan, koşullar yerine getirilirse

Nokta kümesi dışbükey, herhangi iki noktasıyla birlikte bunların keyfi dışbükey, doğrusal birleşimini içeriyorsa.

Dışbükey çokyüzlülerin temsiliyle ilgili aşağıdaki teoremi kanıtlayabiliriz.

Teorem 1.1. Dışbükey n boyutlu bir çokyüzlü, köşe noktalarının dışbükey doğrusal bir birleşimidir.

Teorem 1.1'den, köşe noktaları veya köşe noktaları tarafından dışbükey bir çokyüzlünün oluşturulduğu sonucu çıkar: iki nokta ile bir parça, üç nokta ile bir üçgen, dört nokta ile bir tetrahedron, vb. Aynı zamanda, sınırsız bir küme olan dışbükey çokyüzlü bölge, köşe noktalarıyla benzersiz bir şekilde tanımlanmaz: noktalarından herhangi biri, köşe noktalarının dışbükey doğrusal birleşimi olarak temsil edilemez.

Doğrusal programlama probleminin özellikleri. Daha önce doğrusal programlama probleminin çeşitli biçimleri ele alınmıştı ve herhangi bir doğrusal programlama probleminin genel veya kanonik bir problem olarak temsil edilebileceği gösterilmişti.

Doğrusal programlama probleminin özelliklerini ve bunu çözme yöntemlerini doğrulamak için, kanonik problemin iki tür gösteriminin daha dikkate alınması tavsiye edilir.

Matris kayıt formu:

Burada İLE– satır matrisi, A– sistem matrisi, X– değişkenlerin matris-sütunları, İÇİNDE– serbest üyelerin matris sütunu:

Kaydın vektör biçimi:

burada vektörler bilinmeyenlerin katsayı sütunlarına karşılık gelir.

Aşağıdaki teorem yukarıda formüle edildi, ancak genel biçimde kanıtlanmadı.

Teorem 1.2. Bir doğrusal programlama probleminin kısıtlar sisteminin tüm uygulanabilir çözümlerinin kümesi dışbükeydir.

Kanıt:İzin vermek - Matris formunda verilen PLP'nin iki uygun çözümü. Daha sonra . Çözümlerin dışbükey doğrusal kombinasyonunu ele alalım;

ve bunun aynı zamanda (1.3) sisteminin kabul edilebilir bir çözümü olduğunu gösterin. Aslında

yani. çözüm X(1.3) sistemini karşılar. Ama o zamandan beri X>0, yani çözüm negatif olmama koşulunu karşılamaktadır.

Dolayısıyla, bir doğrusal programlama probleminin tüm uygulanabilir çözümlerinin kümesinin dışbükey olduğu veya daha doğrusu, bir dışbükey çokyüzlüyü veya bir dışbükey çokyüzlü bölgeyi temsil ettiği, buna ayrıca bir terimle adlandıracağımız kanıtlanmıştır - çözümlerin çokgeni.

Doğrusal programlama problemine çözüm çokyüzlüsünün hangi noktasında en uygun çözümün mümkün olduğu sorusunun cevabı aşağıdaki temel teoremde verilmektedir.

Teorem 1.3. Doğrusal programlama probleminin optimal bir çözümü varsa, o zaman doğrusal fonksiyon aşağıdakileri alır: maksimum değerçözüm çokyüzlünün köşe noktalarından birinde. Doğrusal bir fonksiyon birden fazla köşe noktasında maksimum değer alıyorsa, bunu bu noktaların dışbükey doğrusal birleşimi olan herhangi bir noktada alır.

Kanıt:Çözüm polihedronun sınırlı olduğunu varsayacağız. Köşe noktalarını şu şekilde gösterelim: , ve en uygun çözüm şu şekildedir: X*. Daha sonra F(X*)³ F(X) tüm noktalar için Xçözümlerin çokgeni. Eğer X* bir köşe noktası ise teoremin ilk kısmı kanıtlanmıştır.

Öyleymiş gibi yapalım X* O halde Teorem 1.1'e göre köşe noktası değildir. X*çözüm çokyüzlüsünün köşe noktalarının dışbükey doğrusal birleşimi olarak temsil edilebilir, yani.

Çünkü F(X) doğrusal bir fonksiyondur, şunu elde ederiz

Bu ayrıştırmada değerler arasından maksimumu seçiyoruz. Köşe noktasına karşılık gelmesine izin verin X k(1 £ k£ R); şununla belirtelim M, onlar. . İfadedeki (1.5) her değeri bu maksimum değerle değiştirelim M. Daha sonra

Varsayıma göre X* bu nedenle bir yandan en uygun çözümdür, ancak diğer yandan şu da kanıtlanmıştır:
F(X*)£ M, bu nedenle, nerede X k– köşe noktası. Yani bir köşe noktası var X k burada doğrusal fonksiyon maksimum değerini alır.

Teoremin ikinci kısmını kanıtlamak için amaç fonksiyonunun birden fazla köşe noktasında, örneğin noktalarda maksimum değer aldığını varsayalım. , Nerede , Daha sonra

İzin vermek X– bu köşe noktalarının dışbükey doğrusal birleşimi;

Bu durumda, fonksiyon göz önüne alındığında F(X)– doğrusal, şunu elde ederiz

onlar. doğrusal fonksiyon F keyfi bir noktada maksimum değeri alır X köşe noktalarının dışbükey doğrusal birleşimidir.

Yorum. Teoremde çözüm çokyüzlüsünün sınırlı olması gerekliliği önemlidir, çünkü Teorem 1.1'de belirtildiği gibi sınırsız çokyüzlü bölge durumunda böyle bir bölgenin her noktası köşe noktalarının dışbükey doğrusal birleşimi ile temsil edilemez.

Kanıtlanmış teorem temeldir çünkü doğrusal programlama problemlerini çözmenin temel bir yolunu gösterir. Aslında, bu teoreme göre, aralarında arzu edilen optimal çözümü bulmak için sonsuz sayıda uygulanabilir çözüm kümesini incelemek yerine, çözüm çokyüzlüsünün yalnızca sonlu sayıda köşe noktasını incelemek gerekir.

Bir sonraki teorem şuna adanmıştır: analitik metod köşe noktaları bulma.

Teorem 1.4. Bir doğrusal programlama probleminin kabul edilebilir her temel çözümü, çözüm çokyüzlünün bir köşe noktasına karşılık gelir ve bunun tersi de çözüm çokyüzlünün her köşe noktasına, kabul edilebilir bir temel çözüme karşılık gelir.

Kanıt: LLP'nin (1.4) kısıtlamalar sisteminin kabul edilebilir bir temel çözümü olsun, burada ilk T bileşen ana değişkenlerdir ve geri kalanı p - t bileşen – temel çözümde sıfıra eşit olan ana olmayan değişkenler (eğer durum böyle değilse, karşılık gelen değişkenler yeniden numaralandırılabilir). Hadi bunu gösterelim X

Tam tersini varsayalım, yani. Ne X bir köşe noktası değildir. Sonra işaret et Xçakışmayan iki farklı parçayı birleştiren bir doğru parçasının iç noktası ile temsil edilebilir. X, puan

başka bir deyişle noktaların dışbükey doğrusal birleşimi çözümlerin polihedron'u, yani.

nerede (bunu varsayıyoruz, çünkü aksi takdirde nokta X noktaya denk geliyor X 1 veya X 2).

Vektör eşitliğini (1.6) koordinat biçiminde yazalım:

Çünkü tüm değişkenler ve katsayılar negatif değildir, o zaman sonuncudan itibaren p-t eşitlikler bunu takip eder, yani. kararlarda X 1 , X 2 ve X denklem sistemi (1.4) değerleri p - t bileşenler eşittir bu durumda sıfır. Bu bileşenler birincil olmayan değişkenlerin değerleri olarak düşünülebilir. Ancak temel olmayan değişkenlerin değerleri, ana değişkenlerin değerlerini benzersiz bir şekilde belirler, bu nedenle,

Yani her şey Pçözümlerdeki bileşen X 1 , X 2 ve Xçakışıyor ve bu nedenle noktalar X 1 ve X 2 birleşme, bu da varsayımla çelişiyor. Buradan, X– çözüm çokyüzlünün köşe noktası.

Ters ifadeyi kanıtlayalım. Çözüm çokyüzlünün köşe noktası ve onun ilk noktası olsun T koordinatlar pozitiftir. Hadi bunu gösterelim X– kabul edilebilir temel çözüm. koşulla çelişen bir köşe noktası değildir. Bu nedenle varsayımımız yanlıştır, yani. vektörler doğrusal olarak bağımsızdır ve X(1.4) problemine kabul edilebilir bir temel çözümdür.

Teorem 1.3 ve 1.4'ten önemli bir sonuç doğrudan çıkar: Eğer bir doğrusal programlama probleminin optimal bir çözümü varsa, o zaman bu problem onun uygulanabilir temel çözümlerinden en az biriyle çakışıyor demektir.

Bu yüzden, Optimum doğrusal fonksiyon Doğrusal programlama problemleri sonlu sayıda uygulanabilir temel çözüm arasında aranmalıdır.

Doğrusal modellerin MS Excel'de optimizasyonu gerçekleştirilir simpleks yöntemi- Doğrusal programlama problemine yönelik referans çözümlerinin amaçlı araştırılması. Simpleks yöntem algoritması, çok boyutlu bir uzayda dışbükey bir çokyüzlü oluşturmaya ve ardından uç bir değer bulmak için köşelerini numaralandırmaya dayanır. amaç fonksiyonu.

Etkili araçlar doğrusal programlama Daha karmaşık optimizasyon problemlerini çözmek için hem tamsayılı hem de doğrusal olmayan programlamanın temelini oluşturur. Ancak bu yöntemler daha uzun hesaplama süreleri gerektirir.

Sonraki derslerde, MS Excel eklentisi "Çözüm arayın" kullanılarak tipik optimizasyon problemlerinin çözümü ve yönetim kararlarının alınmasına ilişkin örnekler ayrıntılı olarak tartışılacaktır. Bu araçla en iyi şekilde çözülen görevlerin üç ana özelliği vardır:

• optimize edilmesi gereken (maksimum, minimum veya belirli bir sayısal değeri bulmak için) sistemin diğer parametreleriyle işlevsel olarak ilişkili tek bir hedef vardır;
• Genellikle eşitsizlikler şeklinde ifade edilen kısıtlamalar vardır (örneğin, kullanılan hammaddelerin hacmi depodaki hammadde stokunu aşamaz veya makinenin günlük çalışma süresi bakım hariç 24 saatten fazla olmamalıdır) zaman);
• optimize edilmiş değerleri ve kısıtlamaları etkileyen bir dizi giriş değişkeni değeri vardır.

Görevlerin parametreleri aşağıdaki sınır göstergeleriyle sınırlıdır:

• bilinmeyenlerin sayısı – 200;
• bilinmeyenlere ilişkin kalıplaşmış kısıtlamaların sayısı – 100;
• Bilinmeyenler için sınırlayıcı koşulların sayısı 400'dür.

Optimum çözümleri bulmaya yönelik algoritma birkaç aşamadan oluşur:

• hazırlık çalışmaları;
• çözümde hata ayıklama;
• çözüm analizi.

MS Excel kullanarak ekonomik ve matematiksel modelleme problemlerini çözerken gerçekleştirilen gerekli hazırlık çalışmalarının sırası, Şekil 1.6'daki blok diyagramda gösterilmektedir.

Pirinç. 1.6.

Hazırlık çalışma planının beş noktasından yalnızca beşinci nokta resmileştirilebilir. İşin geri kalanı yaratıcılık gerektirir ve farklı insanlar bunu farklı şekillerde yapabilir. Plan maddelerinin lafzının özünü kısaca açıklayalım.

Problemi kurarken hedef katsayılar ve normalleştirilmiş katsayılar bilinmektedir. Önceki örnekte, amaç fonksiyonunu oluşturan katsayılar, raf türü başına normalleştirilmiş kârın değerleriydi ( ) ve bir raf tipi ( ). Normalleştirilmiş katsayılar, her türün raf başına malzeme tüketimi ve makine süresi normlarıydı. Matris şuna benziyordu:

Ayrıca kaynak değerleri her zaman bilinir. Önceki örnekte bu, bir haftalık pano temini ve makine süresini kullanma becerisiydi: , . Çoğu zaman problemlerde değişkenlerin değerlerinin sınırlandırılması gerekir. Bu nedenle değişim aralıklarının alt ve üst sınırlarının belirlenmesi gerekmektedir.

Bu nedenle, "Çözüm ara" optimizasyon programının iletişim kutusunda aşağıdaki hedef algoritmayı ayarlamamız gerekir:

Hedef fonksiyon, istenen değişken değerlerin vektörünün hedef katsayıların vektörü ile çarpımına eşittir.

Gerekli değişken değerlerinin vektörü için normalleştirilmiş katsayılar, verilen kaynak vektörünün değerini aşmamalıdır.

Değişken değerleri sistemin başlangıç ​​elemanlarının belirtilen limit sayısı dahilinde olmalıdır

Sistemin başlangıç ​​elemanlarının sayısı

Belirtilen kaynak türü sayısı

Program olumsuz sonuçlarla ilgili bir mesaj görüntülediğinde çözümde hata ayıklama gereklidir (Şekil 1.7):

Pirinç. 1.7.

• kabul edilebilir bir çözüm elde edilemiyorsa kaynak veri modelini ayarlayın;
• alınmadıysa en uygun çözüm, ardından ek kısıtlamalar ekleyin.

Program sorunları en uygun çözüm yalnızca gerçek sorunun bir modeli için, sorunun kendisine bir çözüm için değil. Modeli oluştururken gerçek durum hakkında çeşitli basitleştirici varsayımlarda bulunuldu. Bu, sistem parametreleri ile hedef arasındaki gerçek niceliksel ilişkileri yaklaşık olarak göstererek süreci resmileştirmeyi mümkün kıldı. Ve eğer gerçek parametreler modelde yer alan parametrelerden farklıysa çözüm nasıl değişecek? Bunu bulmak için yönetim kararı vermeden önce model çözümünün analizi yapılır.

Analiz en uygun çözüm Programın içine yerleştirilmiş olan , ekonomik süreçlerin matematiksel modellemesinin son aşamasını temsil eder. Optimum çözümün güvenilirliğinin yanı sıra modelin sürece uygunluğunun daha derinlemesine kontrol edilmesine olanak tanır. Verilere dayanmaktadır en uygun çözüm ve “Çözüm arayışı” kapsamında yayınlanan raporlar. Ancak bir yönetim kararı vermeden önce planın ekonomik açıdan geleneksel analizini dışlamaz veya değiştirmez.

Ekonomik analiz aşağıdaki hedeflere sahiptir:

• tanım Olası sonuçlar bir model parametresi değiştiğinde bir bütün olarak sistemde ve onun öğelerinde;
• problemin bireysel parametrelerindeki değişikliklere karşı optimal planın stabilitesinin değerlendirilmesi: çoğu parametredeki değişikliklere karşı stabil değilse, uygulanmasının ve hesaplanan optimumun elde edilmesinin garantisi azalır;
• düzeltmeler kullanarak problemi orijinal temelden çözmeden, varyant hesaplamaları yapmak ve yeni plan seçenekleri elde etmektir.

Olası analiz yöntemleri Şekil 1.8'deki şemada gösterilmektedir.

Optimum çözüm elde edildikten sonra alınan raporlara göre analiz yapılır. Kararlılık Analizi- bireysel model parametrelerindeki değişikliklerin optimal çözümün göstergeleri üzerindeki etkisinin incelenmesi. Limit Analizi- planın optimal kaldığı optimal planda izin verilen değişikliklerin analizi.

Ekonomik kabul etme sorumluluğu göz önüne alındığında Yönetim kararı Yönetici, ortaya çıkan optimal planın tek doğru plan olduğundan emin olmalıdır. Bunun için modele dayalı olarak aşağıdaki soruların cevaplarını almak gerekir:

• "olursa ne olur…"
• "neye ihtiyacı var..."

İlk soruyu cevaplamak için yapılan analize denir varyant analizi; ikinci soruyu cevaplamak için yapılan analize denir özel çözümler.

Varyant analizi aşağıdaki türlerde olabilir:

• Parametrik- belirli bir parametrenin farklı değerleri için bir problemin çözülmesinden oluşan analiz.
• Yapısal Analiz- Farklı bir kısıt yapısı altında bir optimizasyon problemine çözüm arandığında.
• Çok kriterli analiz Farklı amaç fonksiyonlarını kullanarak bir problemin çözümüdür.
• Koşullu başlangıç ​​verileriyle analiz- Bir sorunu çözmek için kullanılan ilk veriler ek koşulların yerine getirilmesine bağlı olduğunda.

Analiz sonrasında sonuçlar grafiksel olarak sunulmalı ve spesifik ekonomik durum dikkate alınarak karar alınmasına yönelik öneriler içeren bir rapor derlenmelidir.

Tanım. Kısıtlamalar sistemine yönelik herhangi bir çözüme PLP'nin kabul edilebilir çözümü denir.
Tanım. Amaç fonksiyonunun maksimum veya minimum değere ulaştığı uygun çözüme optimal çözüm denir.

Bu tanımlardan dolayı LP problemi şu şekilde formüle edilebilir: Kısıtlar sisteminin çözümü olan dışbükey bir bölgenin tüm noktaları arasından, koordinatları doğrusal fonksiyonu minimuma indiren (maksimize eden) bir nokta seçin. F = İle 1 X + İle 2 sen.
Değişkenlere dikkat edin X, sen ZLP'de kural olarak negatif olmayan değerler alırlar ( X≥ 0, sen≥ 0), dolayısıyla bölge koordinat düzleminin ilk çeyreğinde yer alır.

Doğrusal fonksiyonu düşünün F = İle 1 X + İle 2 sen ve değerinin bir kısmını düzeltin F. Örneğin, F= 0, yani İle 1 X + İle 2 sen= 0. Bu denklemin grafiği koordinatların (0;0) orijininden geçen düz bir çizgi olacaktır (Şek.).
Çizim
Bu sabit değeri değiştirirken F = D, dümdüz İle 1 X+ İle 2 y = d paralel olarak kayacak ve tüm düzlemin "ana hatlarını çizecek". İzin vermek D– çokgen – kısıtlamalar sisteminin çözüm alanı. Değiştiğinde D dümdüz İle 1 X + İle 2 sen = D, bir değerde D = D 1 çokgene ulaşacak D, bu noktaya diyelim A"giriş noktası" ve ardından çokgeni bir değerde geçtikten sonra D = D 2 onunla son ortak noktamız olacak İÇİNDE, Hadi arayalım İÇİNDE"çıkış noktası".
En az olduğu açıktır ve en yüksek değer amaç fonksiyonu F=İle 1 X + İle 2 sen giriş noktalarına ulaşacak A ve "çıkış" İÇİNDE.
Uygun çözümler kümesindeki optimal değerin göz önüne alındığında, amaç fonksiyonu bölgenin köşelerini alır. D Sorunun çözümü için aşağıdaki planı önerebiliriz:

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

Vektörün ( İle 1 , İle 2), düz çizgiye dik, amaç fonksiyonunun büyüme yönünü gösterir.

ZLP'yi grafiksel olarak çözerken, özel tartışma gerektiren iki durum mümkündür.

Dava 1
Şekil 6
Düz bir çizgiyi hareket ettirirken İle 1 X + İle 2 sen= D Poligonun kenarı boyunca “giriş” veya “çıkış” (şekildeki gibi) meydana gelecektir. Çokgenin çizgiye paralel kenarları varsa bu gerçekleşir İle 1 X+ İle 2 en = D .
Bu durumda sonsuz sayıda “çıkış” (“giriş”) noktası, yani parça üzerindeki herhangi bir nokta vardır. AB. Bu, amaç fonksiyonunun maksimum (minimum) değeri bir noktada değil, poligonun karşılık gelen tarafındaki tüm noktalarda aldığı anlamına gelir. D.

Durum 2
Bölgenin durumu düşünün kabul edilebilir değerler sınırsız.
Sınırsız bir alan söz konusu olduğunda, amaç fonksiyonu, karşılık gelen düz çizginin bir "çıkış" (veya "giriş") noktasına sahip olmayacağı şekilde belirtilebilir. O zaman fonksiyonun maksimum değerine (minimum) asla ulaşılamaz - fonksiyonun sınırsız olduğunu söylerler.
Çizim
Amaç fonksiyonunun maksimum değerini bulmak gerekir F = 4X + 6sen→ max , bir kısıtlama sistemiyle
Uygun çözümlerden oluşan bir bölge oluşturalım; Eşitsizlik sistemini grafiksel olarak çözelim. Bunu yapmak için her bir doğruyu oluşturuyoruz ve eşitsizliklerin tanımladığı yarım düzlemleri belirliyoruz.
X + sen = 18

X	12	9
sen	6	9

0,5X + sen = 12

X	12	18
sen	6	3

X= 12 – eksene paralel OY ;
sen= 9 – eksene paralel ÖKÜZ ;
X= 0 – eksen OY ;
sen = 0 – eksen ÖKÜZ;
X OY;
sen≥ 0 – eksenin üzerinde yarım düzlem ÖKÜZ;
sen≤ 9 – yarım düzlem aşağıda sen = 9;
X ≤ 12 – sola yarım düzlem X = 12;
0,5X + senX + sen = 12;
X + sen X + sen = 18.
Çizim
Tüm bu yarım düzlemlerin kesişimi açıkça bir beşgendir OAVSD, noktalarda köşeler bulunan HAKKINDA(0; 0), A(0; 9), İÇİNDE(6; 9), İLE(12; 6), D(12; 0). Bu beşgen problemin uygulanabilir çözüm bölgesini oluşturur.

F = 4X + 6sen→ maks.

X	3	0
sen	–2	0

F = 0: 4X + 6sen X+ 6sen İLE(12; 6). Bu onun içinde F = 4X + 6sen
Öyleyse ne zaman X = 12, sen= 6 fonksiyon F F= 4 ∙ 12 + 6 ∙ 6 = 84, 84'e eşit. Koordinatları (12; 6) olan nokta, kısıtlama sisteminin tüm eşitsizliklerini karşılar ve içinde amaç fonksiyonunun değeri optimaldir F* = 84 (en uygun değeri “*” olarak göstereceğiz).
Problem çözüldü. Yani 84 bin ruble karla 12 adet tip I ve 6 adet tip II ürün üretmek gerekiyor.

Grafik yöntemi Kısıtlama sisteminde yalnızca iki değişkeni olan problemleri çözmek için kullanılır. Bu yöntem aynı zamanda üç değişkenli eşitsizlik sistemleri için de kullanılabilir. Geometrik olarak durum farklı olacak, üç boyutlu uzayda düz çizgilerin rolünü uçaklar oynayacak, üç değişkendeki eşitsizliğin çözümü ise düzlemin bir tarafında yer alan yarım uzay olacaktır. Alanların rolü, yarı uzayların kesişimi olan çokyüzlüler tarafından oynanacak.

Örnek No.2. Maden iki damar geliştiriyor. Birinci katman için kültür verimi %a1'dir; ikincisi için -% a2. Maksimum performans ilk katmanın çalışma yüzü yılda B1 bin ton, ikinci katmanın çalışma yüzeyi ise yılda B2 bin tondur. Çalışma teknolojisine göre ikinci katmandaki üretim, birinci katmandaki üretimi geçemez. Taş ocağının madenden çıkan üretimi yılda 1 bin tonu geçmemelidir. İki katmandaki yıllık toplam yük, yılda 2 bin tondan az olmamalıdır. Matematiksel bir model oluşturun ve birinci ve ikinci katmanlar için yıllık izin verilen yük değerleri kümesini oluşturun.

Örnek No. 3. Mağazada 2 çeşit meşrubat satılıyor: Kola ve limonata. Bir kutu koladan elde edilen gelir 5 kuruş, bir kutu limonatadan elde edilen gelir ise 7 kuruş. Ortalama olarak bir mağaza her iki içecekten de günde 500 kutudan fazla satmıyor. Kolanın ünlüler tarafından üretilmesine rağmen marka Alıcılar limonatayı daha ucuz olduğu için tercih ediyor. Kola ve limonata satış hacminin en az 2:1 oranında olması gerektiği tahmin ediliyor; ayrıca mağazanın günde en az 100 kutu kola sattığı da biliniyor. Geliri en üst düzeye çıkarmak için mağazada günün başında her içecekten kaç kutu bulunmalıdır?

Örnek No. 4. Bir doğrusal programlama problemini yaklaşık olarak grafiksel olarak çözün, ardından amaç fonksiyonunun tam değerini ve maksimum(min) değerini hesaplayın.

Örnek No. 5. Bir seyahat şirketinin en fazla üç tonluk ve en fazla beş tonluk otobüslere ihtiyacı vardır. Birinci marka otobüslerin satış fiyatı 20.000 Dolar, ikinci marka otobüslerin satış fiyatı ise 40.000 Dolar. Bir seyahat şirketi otobüs alımına 1 dolardan fazla ayıramaz. Toplam (toplam) taşıma kapasitesinin maksimum olması için her markadan kaç adet otobüs ayrı ayrı satın alınmalıdır. Sorunu grafiksel olarak çözün.

Örnek No. 6. Tabloda verilen problemde grafiksel yöntemi kullanarak en uygun üretim planını bulun.

Örnek No. 7. Bir doğrusal programlama problemini, problemin kısıtlama sistemini Jordan-Gauss dönüşümlerine tabi tutarak grafiksel olarak çözün. Sorun kısıtlama sistemi şu şekildedir:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Yönergeler. Jordano-Gauss dönüşümleri bu hizmet kullanılarak veya SLAE çalışması aracılığıyla gerçekleştirilebilir.

Örnek No. 8. Şirket, üretiminde üç tip hammadde kullanılan iki tip A ve B ürünü üretmektedir. Bir birim A ürünü üretmek için, sırasıyla her a1, a2, a3 kg türünden hammaddelerin ve bir birim B - b1, b2, b3 kg ürünü için harcanması gerekir. Her cins hammaddeden sırasıyla P1, P2, P3 kg miktarında üretim sağlanmaktadır. Bir birim A ürününün maliyeti C1 ruble ve bir birim B ürününün maliyeti C2 ruble. A ve B ürünleri için bitmiş ürünün maksimum maliyetini sağlayacak bir üretim planının hazırlanması gerekmektedir.

Örnek No.2. Amaç fonksiyonunun maksimum değerini bulmak gerekir F = 4X + 6sen→ maksimum, bir kısıtlama sistemiyle:

Uygun çözümlerden oluşan bir bölge oluşturalım; Eşitsizlik sistemini grafiksel olarak çözelim. Bunu yapmak için kısıtlama sayısını 4'e eşit olarak seçiyoruz (Şekil 1).
Resim 1

Daha sonra değişkenlerin katsayılarını ve kısıtlamaları dolduruyoruz (Şekil 2).
şekil 2

Figür 3
X= 12 – eksene paralel OY;
sen= 9 – eksene paralel ÖKÜZ;
X> = 0 – eksen OY
sen= 0 – eksen ÖKÜZ;
X≥ 0 – eksenin sağındaki yarım düzlem OY;
sen≥0 – eksenin üzerinde yarım düzlem ÖKÜZ;
sen≤ 9 – yarım düzlem aşağıda sen = 9;
X≤ 12 – sola yarım düzlem X = 12;
0,5X + sen≤ 12 – düz çizginin altındaki yarım düzlem 0,5 X + sen = 12;
X + sen≤ 18 – düz çizginin altındaki yarım düzlem X + sen = 18.

Bütün bu yarım düzlemlerin kesişimi bir beşgendir ABCDE, noktalarda köşeler bulunan A(0; 0), B(0;9), C(6; 9), D(12;6), e(12;0). Bu beşgen problemin uygulanabilir çözüm bölgesini oluşturur.

Sorunun amaç fonksiyonunu düşünün F = 4X + 6sen→ maks.

X	3	0
sen	–2	0

Fonksiyonun değerine karşılık gelen düz bir çizgi çizelim F = 0: 4X + 6sen= 0. Bu doğruyu paralel olarak hareket ettireceğiz. Tüm 4 numaralı hat ailesinden X + 6sen= çokgen sınırından ayrılırken çizginin geçeceği son köşeyi oluşturmak köşe olacaktır İLE(12; 6). Bu onun içinde F = 4X + 6sen maksimum değerine ulaşacaktır.

Öyleyse ne zaman X = 12, sen= 6 fonksiyon F maksimum değerine ulaşır F= 4 ∙ 12 + 6 ∙ 6 = 84, 84'e eşit. Koordinatları (12;6) olan nokta, kısıtlama sisteminin tüm eşitsizliklerini karşılar ve burada amaç fonksiyonunun değeri optimaldir. F* = 84.

"Yöneylem Araştırması" disiplininde test

(doğru cevaplar ilk olanlardır)

1. “Yöneylem araştırması” terimi ortaya çıktı…

ikinci dünya savaşı sırasında

XX yüzyılın 50'li yıllarında

XX yüzyılın 60'larında

XX yüzyılın 70'lerinde

XX yüzyılın 90'lı yıllarında

21. yüzyılın başında

2. Yöneylem araştırması şu anlama gelir (en uygun seçeneği seçin) ...

sorunları çözmek için bir dizi bilimsel yöntem Etkili yönetim organizasyon sistemleri

belirli operasyonları uygulamak için alınan bir dizi önlem

planın uygulanmasına yönelik bir dizi yöntem

Üretimi organize ederken kaynak tahsisinin bilimsel yöntemleri

3. Herhangi bir operasyonel araştırmanın genel olarak geçtiği aşamaları sıralayın:

Sorunun formülasyonu

Söz konusu nesnenin (sürecin) anlamlı (sözlü) bir modelinin oluşturulması

matematiksel bir model oluşturmak

Oluşturulan matematiksel modele dayanarak formüle edilen problemleri çözme

Elde edilen sonuçların incelenen sistemin doğasına uygunluğu açısından kontrol edilmesi

Elde edilen çözümün pratikte uygulanması

4. Yöneylem araştırmasında operasyon şu anlama gelir:

Tek bir planla birleştirilen ve bir hedefe ulaşmayı amaçlayan herhangi bir olay (eylemler sistemi)

kontrol edilemeyen herhangi bir olay

tüketici ürünlerinin üretimini sağlamak için bir dizi teknik önlem

5. Çözüme optimal denir...

eğer bir nedenden dolayı diğerlerine tercih edilirse

eğer mantıklıysa

yetkililerle mutabakata varılması halinde

genel kurul tarafından onaylanması halinde

6. Matematiksel programlama...

ekstrem problemlerin incelenmesi ve bunları çözmek için yöntemlerin geliştirilmesi ile uğraşmaktadır

matematikçilerin rehberliğinde bilgisayar programları oluşturma sürecidir

bilgisayardaki matematik problemlerini çözer

7. Doğrusal programlama problemi...

doğrusal kısıtlamaların varlığında doğrusal bir fonksiyonun en büyük (en küçük) değerini bulma

Belirli bir sorunu çözmek için tasarlanmış, seçilen bir programlama dilinde doğrusal bir program oluşturmak

belirli bir sorunu çözmek için doğrusal bir algoritmanın tanımı

8. İkinci dereceden bir programlama probleminde...

amaç fonksiyonu ikinci derecedendir

uygun çözüm alanı bir karedir

kısıtlamalar ikinci dereceden fonksiyonlar içerir

9. Tamsayılı programlama problemlerinde...

bilinmeyenler yalnızca tam sayı değerleri alabilir

hedef fonksiyonun mutlaka bir tamsayı değeri alması gerekir ve bilinmeyenler herhangi bir değer olabilir.

amaç fonksiyonu sayısal bir sabittir

10. Parametrik programlama problemlerinde...

amaç fonksiyonu ve/veya kısıtlama sistemi parametre(ler)i içerir

uygun çözümlerin bölgesi bir paralelkenar veya paralelyüzdür

değişken sayısı yalnızca çift olabilir

11. Dinamik programlama problemlerinde...

Çözüm bulma süreci çok aşamalıdır

Dinamit üretiminin rasyonelleştirilmesi gerekiyor

hoparlör kullanımını optimize etmemiz gerekiyor

12. Aşağıdaki doğrusal programlama problemi ortaya atılmıştır:

F(X 1, X 2) = 5X 1 + 6X 2→ maksimum

0.2X 1 + 0.3X 2 ≤ 1.8,

0.2X 1 + 0.1X 2 ≤ 1.2,

0.3X 1 + 0.3X 2 ≤ 2.4,

X 1 ≥ 0, X 2 ≥ 0.

Bu göreve eşdeğer bir görev seçin.

F(X 1, X 2)= 5X 1 + 6X 2 → maksimum,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 6X 1 + 5X 2 → dk,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 50X 1 + 60X 2 → maksimum,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 5X 12 + 6X 22 → maksimum,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

3X 1 + X 2 ≤ 2.4,

X 1 ≥ 0,

X 2 ≥ 0.

13. Bir doğrusal programlama probleminin amaç fonksiyonu şu fonksiyon olabilir:

F=12x1+20x2–3 0x3→dk.

F= →dk.

F=→maksimum

F=→maks.

14. Bir doğrusal programlama probleminin kısıt sistemi aşağıdaki sistem olabilir:

15. Simpleks yöntemi:

temel doğrusal programlama problemini çözmek için analitik yöntem

bir doğrusal programlama problemine uygun çözümlerin bölgesini bulmak için bir yöntem;

ana doğrusal programlama problemini çözmek için grafiksel yöntem;

Genel bir doğrusal programlama problemini kanonik forma indirgemek için bir yöntem.

16. Doğrusal programlama problemi:

Doğrusal kısıtlamaların varlığında doğrusal bir fonksiyonun en büyük veya en küçük değerini bulma

Doğrusal bir algoritma geliştirmek ve bunu bilgisayarda uygulamak

sistemi derlemek ve çözmek doğrusal denklemler

açıklanan sürecin doğrusal bir gelişim yörüngesini aramak verilen sistem kısıtlamalar.

17. Doğrusal programlama probleminin uygulanabilir çözüm bölgesi yapamamak Bunun gibi:

18. Bir doğrusal programlama probleminin amaç fonksiyonu şu fonksiyon olabilir:

F=12x1+20x2–3 0x3→dk.

F= →dk.

F=→maksimum

F=→maks.

19. Bir doğrusal programlama probleminin kısıt sistemi şu şekilde olabilir:

20. Doğrusal programlama probleminin uygulanabilir çözüm bölgesi şu şekildedir:

F(X 1, X 2)= 3X 1 + 5X 2 eşittir...

21. Bir doğrusal programlama probleminin uygulanabilir çözüm bölgesi şu şekildedir:

Daha sonra fonksiyonun maksimum değeri F(X 1, X 2)= 5X 1 + 3X 2 eşittir...

22. Doğrusal programlama probleminin uygulanabilir çözüm bölgesi şu şekildedir:

Daha sonra fonksiyonun maksimum değeri F(X 1, X 2)= 2X 1 - 2X 2 eşittir...

23. Doğrusal programlama probleminin uygulanabilir çözüm bölgesi şu şekildedir:

F(X 1, X 2)= 2X 1 - 2X 2 eşittir...

24. Doğrusal olmayan programlama probleminin uygulanabilir çözüm bölgesi şu şekildedir:

Daha sonra fonksiyonun maksimum değeri F(X 1, X 2)= X 2 – X 12 eşittir...

25. Amaç fonksiyonunun maksimum değeri F(X 1, X 2)= 5X 1 + 2X 2 kısıtlamalarla
X 1 + X 2 ≤ 6,

X 1 ≤ 4,

X 1 ≥ 0, X 2 ≥ 0, eşittir...

26. Küçük bir işletme iki tür ürün üretmektedir. A tipi bir ürünün üretimi için 2 kg hammadde, B tipi bir ürünün üretimi için ise 1 kg hammadde gerekir. Toplamda 60 kg hammadde bulunmaktadır. A tipi bir ürünün satış fiyatı 3 c.u., B tipi - 1 c.u. ise en büyük gelirin elde edilmesini sağlayan bir üretim planı hazırlanması gerekmektedir. Yani A tipinde en fazla 25, B tipinde ise 30'dan fazla ürün gerekli değildir.

Bu görev...

doğrusal programlama problemi

Dinamik programlama yöntemiyle çözülen problem

ağ planlama sorunu

27. Küçük bir işletme iki tür ürün üretmektedir. A tipi bir ürünün üretimi için 2 kg hammadde, B tipi bir ürünün üretimi için ise 1 kg hammadde gerekir. Toplamda 60 kg hammadde bulunmaktadır. A tipi bir ürünün satış fiyatı 3 c.u., B tipi - 1 c.u. ise en büyük gelirin elde edilmesini sağlayan bir üretim planı hazırlanması gerekmektedir. Yani A tipinde en fazla 25, B tipinde ise 30'dan fazla ürün gerekli değildir.

Bu problemin amaç fonksiyonu fonksiyondur...

F(x1,x2)=3x1+x2→maksimum

F(x1,x2)=25x1+30x2→maksimum

F(x1,x2)=2x1+x2→maksimum

F(x1,x2)=60 -2x1 - x2→dk.

28. Küçük bir işletme iki tür ürün üretmektedir. A tipi bir ürünün üretimi için 2 kg hammadde, B tipi bir ürünün üretimi için ise 1 kg hammadde gerekir. Toplamda 60 kg hammadde bulunmaktadır. A tipi bir ürünün satış fiyatı 3 c.u., B tipi - 1 c.u. ise en büyük gelirin elde edilmesini sağlayan bir üretim planı hazırlanması gerekmektedir. e. ve A tipi ürünlerin en fazla 25 adet, B tipi ürünlerin ise en fazla 30 adet üretilmesi gerekir.

Bu görev için geçerli bir plan şu plandır:

X=(20, 20)

X=(25, 15)

X=(20, 25)

X=(30, 10)

29. A1 ve A2 noktalarında sırasıyla 60 ve 160 adet mal bulunmaktadır. Tüm mallar sırasıyla 80, 70 ve 70 adetlik miktarlarda B1, B2, B3 noktalarına taşınmalıdır. Tarife matrisi aşağıdaki gibidir: . Taşımanızı maliyeti minimum olacak şekilde planlayın.

Bu görev...

taşıma görevi

doğrusal olmayan programlama problemi

gezgin satıcı problemi

atama sorunu

30. A1 ve A2 noktalarında sırasıyla 60 ve 160 adet mal bulunmaktadır. Tüm mallar sırasıyla 80, 70 ve 70 adetlik miktarlarda B1, B2, B3 noktalarına taşınmalıdır. Tarife matrisi aşağıdaki gibidir: . Taşımanızı maliyeti minimum olacak şekilde planlayın

Bu görevin temel planı şu plandır:

;

31. A1 ve A2 noktalarında sırasıyla 60 ve 160 adet mal bulunmaktadır. Tüm mallar sırasıyla 80, 70 ve 70 adetlik miktarlarda B1, B2, B3 noktalarına taşınmalıdır. Tarife matrisi aşağıdaki gibidir: . Taşımanızı maliyeti minimum olacak şekilde planlayın.

Bu problemin amaç fonksiyonu aşağıdaki fonksiyondur:

F=4x11+6x12+ 8x13+5x21+8x22+7x23→dk.

F= →dk.

F=60x1+160x2+ 80x3+70x4+705 →maksimum

F=60x1+160x2– 80x3– 70x4– 705 →dk.

32. A1 ve A2 noktalarında sırasıyla 60 ve 160 adet mal bulunmaktadır. Tüm mallar sırasıyla 80, 70 ve 70 adetlik miktarlarda B1, B2, B3 noktalarına taşınmalıdır. Tarife matrisi aşağıdaki gibidir: . Taşımanızı maliyeti minimum olacak şekilde planlayın.

Bu problem için en uygun plan şu plandır:

;

.

;

;

33. Taşıma sorunu

halinde kapatılacaktır...

34. Taşıma sorunu

dır-dir…

açık

kapalı

çözülemez

35. Taşıma sorunu

dır-dir…

kapalı

açık

çözülemez

36. Aşağıdaki taşıma problemini çözmek için

girmek lazım...

hayali tüketici

hayali tedarikçi;

geçerli tarife

37. Aşağıdaki taşıma problemini çözmek için

girmek lazım...

hayali tedarikçi;

hayali tüketici

geçerli tarife

Etkin faiz oranı.

38. Bu taşıma görevleri arasında

kapalı...

39. Bir ulaşım sorunu için başlangıç ​​referans planı hazırlanabilir...

yukarıdaki yöntemlerin tümü

kuzeybatı köşe yöntemi

asgari tarife yöntemi

çift ​​tercih yöntemi

Vogel yaklaşım yöntemi

40. Bir doğrusal programlama probleminin amaç fonksiyonu maksimuma ayarlanırsa, o zaman… ikili problemin amaç fonksiyonu minimuma ayarlanır

İkili problemde hedef fonksiyon yoktur

ikili problemin çözümü yok

ikili problemin sonsuz sayıda çözümü vardır

41. Bir doğrusal programlama problemi verildiğinde:

F(X 1, X 2)= 2X 1 + 7X 2 → maksimum,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

Bu problemin ikilisi aşağıdaki gibidir...

F*(y1, y2)= 14y1 + 8y2 → dk.,

3 yıl 1 + y2 ³ 7,

sen 1 ≥ 0, y2 ≥ 0.

F*(y1, y2)= 2y1 + 7y2 → dk.,

2y1 + 3y2 ³ 14,

sen 1 + y2 ³ 8,

sen 1 £ 0, y2 £ 0.

F*(y1, y2)= 2y1 + 7y2 → dk.,

3 sen 1 + y2 ³ 7,

sen 1 £ 0, y2 £ 0.

F*(y1, y2)= 14y1 + 8y2 → dk.,

sen 1 + y2 ³ 7,

sen 1 ≥ 0, y2 ≥ 0.

42. Eğer ikili problemlerden birinin optimal planı varsa, o zaman...

ve diğerinin optimal bir planı var

diğerinin optimal bir planı yok

diğerinin uygulanabilir bir çözümü yok

43. Eğer ikili problemlerden birinin optimal planı varsa, o zaman...

diğerinin ise optimal planı vardır ve amaç fonksiyonlarının değerleri optimal planlarıyla birbirine eşittir.

ve diğerinin optimal planı var, ancak amaç fonksiyonlarının optimal planları için değerleri birbirine eşit değil

başka bir problemin optimal bir planı olmayabilir ama uygulanabilir çözümleri olabilir

44. Bir ikili problem çiftinden birinin amaç fonksiyonu sınırlı değilse (maksimum problem için - yukarıdan, minimum problem için - aşağıdan), o zaman

diğer görevin geçerli bir planı yok

başka bir problemin uygulanabilir planları var ancak optimal bir planı yok

diğer görevin amaç fonksiyonu da sınırsızdır

45. Bazı doğrusal olmayan programlama problemlerini çözerken...

Lagrange çarpanı yöntemi

Gauss yöntemi

Vogel yaklaşım yöntemi

Gomori yöntemi

46. ​​​​Doğrusal olmayan bir programlama problemi veriliyor

F(X 1, X 2)= X 12 + X 22 → maksimum,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

F(X 1, X 2) …

ulaşılamıyor (+ ¥)

47. Doğrusal olmayan bir programlama problemi veriliyor

F(X 1, X 2)= X 12 + X 22 → Miçinde,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

F(X 1, X 2) …

48. Doğrusal olmayan bir programlama problemi veriliyor

F(X 1, X 2)= X 12 + X 22 → maksimum,

X 1 + X 2 =6,

X 1, X 2 - herhangi biri.

Amaç fonksiyonunun en büyük değeri F(X 1, X 2) …

ulaşılamıyor (+ ¥)

49. Doğrusal olmayan bir programlama problemi veriliyor

F(X 1, X 2)= X 12 + X 22 → Miçinde,

X 1 + X 2 =6,

X 1, X 2 - herhangi biri.

Amaç fonksiyonunun minimum değeri F(X 1, X 2) …

ulaşılamıyor (- ¥)

50. Doğrusal olmayan bir programlama probleminin uygulanabilir çözüm bölgesi şu şekildedir:

Daha sonra fonksiyonun maksimum değeri F(X 1, X 2)= X 12 +X 22 eşittir...

51. Doğrusal olmayan bir programlama probleminin uygulanabilir çözüm bölgesi şu şekildedir:

O zaman fonksiyonun minimum değeri F(X 1, X 2)= X 12 +X 22 eşittir...

52. Bir ulaşım problemini çözmek için kullanılabilir...

potansiyel yöntem

Lagrange çarpanı yöntemi

Gauss yöntemi

yönelim bozukluğu yöntemi

53. Genel bir doğrusal programlama probleminin kısıtları sisteminde...

54. Standart (simetrik) doğrusal programlama probleminin kısıtlamaları sisteminde...

yalnızca eşitsizlikler mevcut olabilir

hem denklemler hem de eşitsizlikler mevcut olabilir

yalnızca denklemler mevcut olabilir

55. Kanonik (ana) doğrusal programlama probleminin kısıtlamaları sisteminde...

yalnızca denklemler mevcut olabilir (değişkenlerin negatif olmaması koşuluyla)

yalnızca eşitsizlikler mevcut olabilir (değişkenlerin negatif olmaması koşuluyla)

hem denklemler hem de eşitsizlikler mevcut olabilir (değişkenlerin negatif olmaması şartıyla)

56. Doğrusal programlama problemi

F(X 1, X 2)= 2X 1 + 7X 2 → maksimum,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

kaydedilmiş...

standart (simetrik) form

kanonik (temel) form

sözlü biçim

57. Bir görevi kaydetmek için

F(X 1, X 2)= 2X 1 + 7X 2 → maksimum,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

kanonik biçimde...

58. Bir görevi kaydetmek için

F(X 1, X 2)= 2X 1 + 7X 2 → maksimum,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

kanonik biçimde...

negatif olmayan üç ek değişken eklenmelidir

negatif olmayan iki ek değişkenin eklenmesi gerekir

dört ek negatif olmayan değişken eklenmelidir

59. Bir görevi kaydetmek için

F(X 1, X 2)= 2X 1 + 7X 2 → maksimum,

2X 1 + 3X 2 = 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

kanonik biçimde...

negatif olmayan iki ek değişkenin eklenmesi gerekir

negatif olmayan üç ek değişken eklenmelidir

dört ek negatif olmayan değişken eklenmelidir

negatif olmayan beş ek değişken eklenmelidir

60. Tamsayılı programlama problemlerini çözerken...

Gomori yöntemi

Lagrange çarpanı yöntemi

Gauss yöntemi

Vogel yaklaşım yöntemi

61. Dinamik programlama yöntemini kullanarak problem çözmenin temeli...

Occam'ın ustura prensibi

“Dişe diş, göze göz” ilkesi

Heisenberg prensibi

62. Çıkarları tamamen veya kısmen çatışan tarafların ortaya çıktığı duruma...

(çatışma, çatışma, çatışma, çatışma)

63. Her biri kendi hedeflerine ulaşmaya çalışan en az iki katılımcının (oyuncunun) bulunduğu gerçek veya resmi bir çatışmaya ... denir.

(oyun, oyun)

64. Her oyuncunun belirli bir hedefe ulaşmayı amaçlayan izin verilen eylemlerine... denir.

(oyunun kuralları, oyunun kuralları)

65. Bir oyunun sonuçlarının niceliksel değerlendirmesine... denir.

(ödeme, ödeme, ödeme)

66. Eğer oyuna sadece iki taraf (iki kişi) katılıyorsa, oyuna... denir.

(çiftler, çiftler, çiftler oyunu, çiftler oyunu)

67. Çiftli bir oyunda ödemelerin toplamı sıfırsa, yani bir oyuncunun kaybı diğerinin kazancına eşitse, o zaman oyuna oyun denir...

(sıfır toplam)

68. Bir oyuncunun kişisel bir hamle yapması gereken olası durumların her birinde yaptığı seçimin net bir açıklamasına denir..

(oyuncu stratejisi, oyuncu stratejisi, strateji, strateji)

69. Oyun birçok kez tekrarlandığında, oyuncuya mümkün olan maksimum ortalama kazancı (mümkün olan minimum ortalama kayıp) sağlayan bir strateji varsa, bu tür bir stratejiye... denir.

(optimum, optimal, optimal strateji, optimal strateji)

70. Sıfır toplamlı çiftler oyununun alt fiyatı a ve üst fiyatı b olsun. O zaman bu ifade doğrudur...

71. Sıfır toplamlı çiftler oyununun alt fiyatı a ve üst fiyatı b olsun. a = b = v ise v sayısına denir...

oyunun bedeli karşılığında

denge noktası

optimal strateji

karma strateji

72. Sıfır toplamlı çiftler oyununun alt fiyatı a ve üst fiyatı olsun. Eğer a = b ise oyunun adı...

eyer noktası oyunu

çözümsüz çatışma

kuralsız bir oyun

73. Her bir bileşeni, oyuncunun karşılık gelen saf stratejiyi kullanımının göreceli sıklığını gösteren bir vektöre ... denir.

karma strateji

kılavuz vektör

normal vektör

degrade

74. Kazanç matrisi tarafından verilen bir matris oyununun en düşük fiyatı...

Daha düşük fiyat

düşük fiyata eşit

bulunmuyor

81. Kazanç matrisinin verdiği matris oyunu, ...

bir eyer noktası var

eyer noktası yok

bir çift değil

82. Ödeme matrisinin verdiği bir oyunun fiyatı…

83. Kazanç matrisinin verdiği matris oyunu, ...

bir buhar odasıdır

bir eyer noktası var

bir çift değil

84. Getiri matrisi ile verilen sıfır toplamlı çiftler oyunu şuna indirgenebilir:

doğrusal programlama problemi

doğrusal olmayan programlama problemi

tamsayılı doğrusal programlama problemi

klasik optimizasyon problemi

85. Kazanç matrisi tarafından verilen bir matris oyununun düşük fiyatı...

Daha düşük fiyat

düşük fiyata eşit

bulunmuyor

92. Kazanç matrisi tarafından verilen matris oyunu, ...

eyer noktası yok

bir eyer noktası var

bir çift değil

93. Oyunun ödeme matrisinde belirtilen fiyatı limitler dahilindedir...

94. Bir olaylar akışında olaylar önceden belirlenmiş ve kesin olarak tanımlanmış zaman aralıklarında birbirini takip ediyorsa, böyle bir akışa ... denir.

düzenli

organize edilmiş

95. Herhangi bir sayıda olayın bir zaman aralığına düşme olasılığı yalnızca bu aralığın uzunluğuna bağlıysa ve bu aralığın zamanın başlangıcından ne kadar uzakta olduğuna bağlı değilse, o zaman karşılık gelen olay akışına şu ad verilir:

sabit

sonuçsuz akış

en basit

Poisson

96. Keyfi olarak seçilmiş zaman aralıklarından birine düşen olayların sayısı, yine keyfi olarak seçilmiş bir zaman aralığına düşen olayların sayısına bağlı değilse, bu aralıkların kesişmemesi koşuluyla, karşılık gelen olay akışı denir. ...

sonuçsuz akış

düzenli

gösterge niteliğinde

normal

97. Çok kısa bir sürede iki veya daha fazla olayın aynı anda meydana gelme olasılığı, yalnızca bir olayın meydana gelme olasılığına kıyasla ihmal edilebilir düzeydeyse, buna karşılık gelen olay akışına... denir.

sıradan

olağanüstü

normal

Poisson

98. Bir olay akışı aynı anda durağanlık, sıradanlık ve sonuçların yokluğu özelliklerine sahipse buna şöyle denir:

en basit (Poisson)

normal

99. Arızalı tek kanallı QS, araba yıkama için günlük bakım istasyonudur. Görevin dolu olduğu bir zamanda gelen bir arabaya yapılan başvuru, hizmet reddedilir. Araba akış yoğunluğu λ=1,0 (saatte araba). Ortalama hizmet süresi 1,8 saattir. Araba akışı ve servis akışı en basit olanıdır. Daha sonra kararlı durumda göreceli verim Q eşit...

100. Arızalı tek kanallı QS, araba yıkama için günlük bakım istasyonudur. Görevin dolu olduğu bir zamanda gelen bir arabaya yapılan başvuru, hizmet reddedilir. Araba akış yoğunluğu λ=1,0 (saatte araba). Ortalama hizmet süresi 1,8 saattir. Araba akışı ve servis akışı en basit olanıdır. O halde, sabit durumda, hizmet reddi alan arabaların yüzdesi şuna eşittir:

Doğrusal programlama probleminin (LPP) genel formülasyonu. PPP örnekleri

Doğrusal programlama, değişkenler arasında doğrusal bir ilişki ve doğrusal bir optimallik kriteri ile karakterize edilen aşırı problemleri çözme yöntemlerini inceleyen bir matematik dalıdır. Doğrusal programlama teriminin kendisi hakkında birkaç kelime. Talep ediyor doğru anlayış. Bu durumda programlama elbette bilgisayar programlarının derlenmesi değildir. Buradaki programlamayı planlamak, plan oluşturmak, eylem programı geliştirmek olarak yorumlamak gerekir. Doğrusal programlamanın matematik problemleri, şu veya bu şekilde sınırlı kaynakların optimal kullanımına ilişkin problemler olarak yorumlanan belirli üretim ve ekonomik durumlara ilişkin çalışmaları içerir. Doğrusal programlama yöntemleri kullanılarak çözülen problemlerin kapsamı oldukça geniştir. Bu örneğin:

• - üretim planlamasında kaynakların optimum kullanımı sorunu;
• - Karışımlarla ilgili problem (ürün kompozisyonunun planlanması);
• - depolarda depolama için farklı ürün türlerinin en uygun kombinasyonunu bulma sorunu (envanter yönetimi veya "sırt çantası sorunu");
• - taşıma görevleri (işletmenin konumunun analizi, malların taşınması). Doğrusal programlama, matematiksel programlamanın en gelişmiş ve en yaygın kullanılan bölümüdür (buna ek olarak tamsayılı, dinamik, doğrusal olmayan, parametrik programlama da dahildir). Bu şu şekilde açıklanmaktadır:
• - Matematiksel modellerçok sayıda ekonomik problem gerekli değişkenlere göre doğrusaldır;
• - bu tip sorunlar şu anda en çok çalışılan konulardır. Onun için tasarlandı özel yöntemler bu sorunların çözüldüğü ve ilgili bilgisayar programlarının yardımıyla;
• - çözülmüş olan birçok doğrusal programlama problemi geniş uygulama alanı bulmuştur;
• - Bir seriden sonra orijinal formülasyonda doğrusal olmayan bazı problemler ek kısıtlamalar ve varsayımlar doğrusal hale gelebilir veya doğrusal programlama yöntemleriyle çözülebilecek bir forma indirgenebilir. Herhangi bir doğrusal programlama probleminin ekonomik ve matematiksel modeli şunları içerir: optimal değerinin (maksimum veya minimum) bulunması gereken bir amaç fonksiyonu; doğrusal denklemler veya eşitsizlikler sistemi biçimindeki kısıtlamalar; değişkenlerin negatif olmaması gerekliliği. Genel olarak model şu şekilde yazılmıştır:
• - amaç fonksiyonu:

C1x1 + c2x2 + ... + cnxn > maks(min);- kısıtlamalar:

a11x1 + a12x2 + ... + a1nxn (? = ?) b1,

a21x1 + a22x2 + ... + a2nxn (? = ?) b2

am1x1 + am2x2 + ... + amnxn (? = ?) bm;

Olumsuz olmama şartı:

Bu durumda aij, bi, cj() değerlerine sabit değerler verilmektedir. Sorun, (2.2) ve (2.3) kısıtlamalarına tabi olarak fonksiyon (2.1)'in optimal değerini bulmaktır. Kısıtlamalar sistemine (2.2) problemin fonksiyonel kısıtlamaları, kısıtlamalara (2.3) ise doğrudan kısıtlamalar adı verilir. (2.2) ve (2.3) kısıtlarını karşılayan bir vektöre doğrusal programlama probleminin kabul edilebilir çözümü (planı) adı verilir. Fonksiyonun (2.1) maksimum (minimum) değerine ulaştığı plana optimal denir.

Aşağıda doğrusal programlama yöntemleri kullanılarak çözülen bazı tipik problemlerin örneklerini veriyoruz. Bu tür görevlerin gerçek ekonomik içeriği vardır. Şimdi bunları yalnızca PLP açısından formüle edeceğiz ve aşağıda bu tür sorunları çözme yöntemlerini ele alacağız.

1. Üretim planlamasında kaynakların optimum kullanımı sorunu. Genel anlam Bu sınıfın problemleri aşağıdakilere indirgenmiştir. Şirket n farklı ürün üretiyor. Üretimleri m farklı türde kaynak gerektirir (hammaddeler, malzemeler, çalışma süresi vb.). Kaynaklar sınırlıdır, planlama dönemindeki rezervleri sırasıyla b1, b2,..., bm konvansiyonel birimlerdir. J-th tipinde () bir birim ürün üretmek için kaç birim i-th kaynağının gerekli olduğunu gösteren aij teknolojik katsayıları da bilinmektedir. Bir işletmenin j tipi bir ürünün satışından elde ettiği kar cj'ye eşittir. Planlama döneminde aij, bi ve cj değerleri sabit kalır. İşletmenin kârının en fazla olacağı üretim planının hazırlanması gerekmektedir. Aşağıda bu sınıfa ait bir problemin basit bir örneğini veriyoruz.

Şirket hokey sopaları ve satranç takımlarının üretiminde uzmanlaşmıştır. Her çubuk şirkete 2$ kar getiriyor ve her satranç takımı 4$ kar getiriyor. Her bir sopa, A Alanında dört saat, B Alanında iki saat çalışma gerektirir. A Alanında altı saat, B Alanında altı saat ve C Alanında bir saatlik maliyetle bir satranç takımı üretilir. Mevcut üretim A Sitesinin kapasitesi günde 120 n-saat, B bölümünün kapasitesi 72 n-saat ve C bölümünün kapasitesi 10 n-saattir. Bir şirketin maksimum kar elde etmek için günde kaç tane sopa ve satranç takımı üretmesi gerekir?

Bu sınıftaki problemlerin koşulları genellikle tablo şeklinde sunulur (bkz. Tablo 2.1).

İle bu durum Doğrusal programlama problemini formüle edelim. Şunu belirtelim: x1 - günlük üretilen hokey sopası sayısı, x2 - günlük üretilen satranç takımı sayısı. PPP'nin formülasyonu:

4x1 + 6x2 ? 120,

İşlevsel kısıtlamalar sistemindeki her eşitsizliğin bu durumda bir veya başka bir üretim sahasına karşılık geldiğini vurguluyoruz: birincisi A sahasına, ikincisi B sahasına, üçüncüsü C sahasına.

Ürün rotasyonlarını dikkate alarak ekilen alanların yapısının optimize edilmesi problemindeki değişkenler sistemi