Doğrusal programlama, optimal programlama yöntemlerini ifade eder. Doğrusal programlama kavramı. Doğrusal programlama problemlerinin türleri

Doğrusal programlama, 40'lı - 50'li yıllarda uygulamalı matematiğin ayrı bir bölümü olarak oluşturulmuştur. 20. yüzyıl Sovyet bilim adamının çalışmaları sayesinde Nobel Ödülü sahibi L.V. Kantoroviç. 1939'da, matematik kullanarak makinelerin en iyi şekilde yüklenmesi, malzemeleri en düşük maliyetle kesme, malları çeşitli taşıma modları arasında dağıtma ile ilgili ekonomik sorunları çözdüğü "Üretim Organizasyonu ve Planlamasının Matematiksel Yöntemleri" adlı eseri yayınladı. ve diğerleri, faktörleri çözme yöntemini öneren 8 .

L.V. Kantorovich, optimal plan, kaynakların optimal dağılımı, nesnel olarak belirlenmiş tahminler gibi yaygın olarak kullanılan ekonomik ve matematiksel kavramları formüle eden ve ekonominin uygulanabilecekleri sayısız alanını gösteren ilk kişiydi.

Doğrusal programlama kavramı, 1949'da bir doğrusal programlama problemini çözmek için "simpleks yöntem" olarak adlandırılan bir algoritma öneren Amerikalı matematikçi D. Danzig tarafından tanıtıldı.

Doğrusal programlamayı içeren matematiksel programlama, şu anda yöneylem araştırmasının alanlarından biridir. Çözülecek görevlerin türüne bağlı olarak, doğrusal, doğrusal olmayan, ayrık, ayrık gibi alanları ayırt eder. dinamik program ve diğerleri "Programlama" terimi, bir sorunu çözme sürecinde olan bilinmeyen değişkenlerin genellikle bazı ekonomik nesnelerin programını veya çalışma planını belirlemesi nedeniyle tanıtıldı.

Klasik matematiksel analizde, koşullu bir ekstremum belirleme probleminin genel formülasyonu incelenir. Ancak endüstriyel üretimin, ulaşımın, tarımsal sanayi kompleksinin ve bankacılık sektörünün gelişmesi nedeniyle, matematiksel analizin geleneksel sonuçları yeterli değildi. Uygulama ihtiyaçları ve bilgisayar teknolojisinin gelişmesi, karmaşık ekonomik sistemlerin analizinde optimal çözümlerin belirlenmesi ihtiyacını doğurmuştur.

Bu tür problemleri çözmenin ana aracı matematiksel modellemedir. Aynı zamanda, önce basit bir model inşa edilir, ardından nesnenin bütünleştirici özelliklerinden hangilerinin resmi şema tarafından yakalanmadığını anlamayı mümkün kılan çalışması gerçekleştirilir, ardından karmaşıklık nedeniyle. model, gerçeğe daha fazla yeterliliği sağlanır. Çoğu durumda, gerçeğe ilk yaklaşım, bir nesnenin durumunu karakterize eden değişkenler arasındaki tüm bağımlılıkların doğrusal olduğu bir modeldir. Uygulama, yeterli sayıda ekonomik sürecin doğrusal modellerle tam olarak tanımlandığını göstermektedir. Sonuç olarak, doğrusal denklemler ve eşitsizlikler tarafından verilen bir küme üzerinde koşullu bir ekstremum bulmayı sağlayan bir araç olarak doğrusal programlama, bu süreçlerin analizinde önemli bir rol oynar.

Doğrusal programlama, planlama ve kontrol alanındaki bir takım problemlerin, etkili yöntemlerin bulunduğu doğrusal programlama problemleri şeklinde formüle edilebileceğinin belirlenmesinden dolayı yaygın olarak geliştirilmiştir. Uzmanlara göre pratikte çözülen tüm optimizasyon problemlerinin yaklaşık %80-85'i doğrusal programlama problemleriyle ilgilidir.

Emek yoğun hesaplamalar yapan bilgisayar programları ile birlikte oluşturulan matematiksel aygıt, doğrusal programlama modellerinin ekonomi bilimi ve uygulamasında yaygın olarak kullanılmasını mümkün kılar.

tanım 1 9 . Doğrusal programlama (LP), matematiğin bir dalı olan ve bilinmeyenleri üzerinde doğrusal kısıtlamaları olan sonlu sayıda değişkenin doğrusal bir fonksiyonunun aşırı (en büyük ve en küçük) değerlerini bulmak için yöntemleri inceleyen bir matematiksel programlama alanıdır. empoze edilir.

Bu doğrusal fonksiyona hedef fonksiyon denir ve değişkenler arasındaki nicel ilişkileri temsil eden, ekonomik problemin koşullarını ve gereksinimlerini ifade eden ve matematiksel olarak denklemler veya eşitsizlikler olarak yazılan kısıtlamalara kısıtlama sistemi denir.

Ekonomik süreçlerin planlanmasıyla ilgili çok çeşitli sorular, en iyi (optimal) çözümü bulma görevinin ortaya konduğu doğrusal programlama problemlerine indirgenir.

Genel bir doğrusal programlama problemi (LPP), amaç 10 olarak adlandırılan doğrusal bir fonksiyonun uç değerini (maksimum veya minimum) bulmaktır:

itibaren n değişkenler x 1 , x 2 , …, x n uygulanan fonksiyonel kısıtlamalar ile:

(3.2)

ve doğrudan kısıtlamalar (değişkenlerin negatif olmaması şartı)

, (3.3)

nerede a ij , B i , C J sabitler verilir.

Kısıtlama sisteminde (3.2), "küçük veya eşittir", "eşittir", "büyüktür veya eşittir" işaretleri aynı anda ortaya çıkabilir.

Daha kısa bir gösterimde ZLP şu şekildedir:

,

kısıtlamalar ile:

;

.

vektör ` x = (x 1 , x 2 , …, x n) bileşenleri, problemin fonksiyonel ve doğrudan kısıtlamalarını karşılayanlara denir. plan(veya kabul edilebilir çözüm) ZLP.

Tüm kabul edilebilir çözümler formu ihtisas doğrusal programlama problemleri veya uygulanabilir çözüm yelpazesi (ODR). Amaç fonksiyonunun maksimum veya minimumunu sağlayan uygun çözüm F(`x), optimal problem planı olarak adlandırılır ve gösterilir F(`x * ), nerede ` x * =(x 1 * , x 2 * , …, x n * ).

ZLP yazmanın başka bir şekli:

,

nerede F(`x * ) maksimum (minimum) değerdir F(İTİBAREN, x) sette bulunan tüm çözümleri devraldı olası çözümler x .

tanım 2 11 . Amaç fonksiyonunun ve sınırlamalarının matematiksel ifadesi, ekonomik problemin matematiksel modeli olarak adlandırılır.

Matematiksel bir model derlemek için gereklidir:

1) değişkenleri belirlemek;

2) görevin amacına dayalı bir amaç fonksiyonu oluşturmak;

3) sorunun durumundaki göstergeleri ve nicel modellerini dikkate alarak bir kısıtlama sistemi yazın.

2. Doğrusal programlama kavramı. Doğrusal programlama problemlerinin türleri

Doğrusal programlama (LP), matematiksel programlamanın ilk ve en kapsamlı çalışılan bölümlerinden biridir. "Matematiksel programlama" disiplininin gelişmeye başladığı bölüm olan doğrusal programlamaydı. Disiplinin başlığındaki "programlama" teriminin "bilgisayar için programlama (yani bir program derleme)" terimiyle hiçbir ilgisi yoktur, çünkü bununla hiçbir ilgisi yoktur. "Doğrusal programlama" disiplini, bilgisayarların matematik, mühendislik, ekonomik ve diğer sorunları çözmek için yaygın olarak kullanılmaya başlandığı zamandan bile önce ortaya çıktı.

"Doğrusal programlama" terimi, İngilizce "doğrusal programlama"nın yanlış çevrilmesinin bir sonucu olarak ortaya çıktı. "Programlama" kelimesinin anlamlarından biri de plan yapmak, planlamaktır. Bu nedenle, İngilizce "doğrusal programlama"nın doğru çevirisi "doğrusal programlama" değil, disiplinin içeriğini daha doğru yansıtan "doğrusal planlama" olacaktır. Bununla birlikte, doğrusal programlama, doğrusal olmayan programlama, matematiksel programlama vb. literatürümüzde genel kabul görmüş ve bu nedenle korunacaktır.

Böylece, İkinci Dünya Savaşı'ndan sonra doğrusal programlama ortaya çıktı ve hızla gelişmeye başladı, geniş pratik uygulama olasılığı ve matematiksel uyumun yanı sıra matematikçilerin, ekonomistlerin ve mühendislerin dikkatini çekti.

Doğrusal programlamanın, gerçek dünyanın doğrusal bir temsilinin hipotezine dayanabilecek bu süreçlerin ve sistemlerin matematiksel modellerini çözmek için uygulanabilir olduğu söylenebilir.

Doğrusal programlama, ekonomik problemlerin çözümünde, yönetim ve üretim planlaması gibi problemlerde kullanılır; gemilerde, atölyelerde ekipmanın optimal yerleşimini belirleme görevlerinde; kargo taşımacılığı için en uygun planı belirleme görevlerinde (ulaşım sorunu); personelin optimal dağılımı vb.

Doğrusal programlama (LP) problemi, yukarıda söylenenlerden zaten açık olduğu gibi, doğrusal kısıtlamalar altında doğrusal bir fonksiyonun minimum (veya maksimum) değerini bulmaktır.

LP problemlerini çözmek için birkaç yöntem vardır. Bu yazıda, bunlardan bazıları özellikle ele alınacaktır:

LP problemini çözmek için grafiksel yöntem;

Simpleks yöntemi;

LP problemini Excel elektronik tablosunu kullanarak çözme;

3. Doğrusal olmayan programlama kavramı

Çoğu mühendislik probleminde matematiksel bir modelin inşası doğrusal programlama problemine indirgenemez.

Gerçek nesneleri veya teknolojik süreçleri tasarlama problemlerindeki matematiksel modeller, gerçek fiziksel ve kural olarak, içlerinde meydana gelen doğrusal olmayan süreçleri yansıtmalıdır. Bu nesnelerin veya süreçlerin değişkenleri, kütle veya enerjinin korunumu yasaları gibi doğrusal olmayan fiziksel yasalarla birbirine bağlıdır. Belirli bir nesne veya işlemin fiziksel fizibilitesini sağlayan aşırı aralıklarla sınırlıdırlar. Sonuç olarak, araştırma projelerinde ve tasarım problemlerinde karşılaşılan çoğu matematiksel programlama problemi doğrusal olmayan programlama (NP) problemleridir.

Bu yazıda, NP problemlerini çözmek için böyle bir yöntemi Lagrange çarpanları yöntemi olarak ele alacağız.

Lagrange çarpanı yöntemi, eşitlik kısıtlamaları altında bir fonksiyonun maksimum (veya minimum) değerini bulmanızı sağlar. Yöntemin ana fikri, koşullu ekstremum probleminden, oluşturulmuş bazı Lagrange fonksiyonunun koşulsuz ekstremumunu bulma problemine geçmektir.

4. Dinamik programlama

Dinamik programlama, analiz edilen durumun belirsizlik faktörleri içermediği durumlarda en uygun çözümü hızlı bir şekilde bulmanızı sağlayan matematiksel bir aparattır. çok sayıda aralarından en iyisini seçmenin gerekli olduğu farklı sonuçlar getiren davranışlar. Dinamik programlama, bir sınıf problemi, onları daha küçük, daha az karmaşık problemlere bölerek çözmeye yaklaşır. Prensipte, bu tür problemler, bütün problemlerin numaralandırılmasıyla çözülebilir. seçenekler ve aralarından en iyisini seçmek, ancak çoğu zaman böyle bir arama çok zordur. Bu durumlarda optimal karar verme süreci adımlara (aşamalara) bölünebilir ve dinamik programlama yöntemi kullanılarak araştırılabilir.

Dinamik programlama yöntemleriyle problem çözme, R.E. Bellman tarafından formüle edilen optimallik ilkesi temelinde gerçekleştirilir: optimal davranış, nasıl olursa olsun, orijinal durum sistem ve ilk karar, sonraki karar, ilk karar sonucunda elde edilen duruma göre optimal davranışı belirlemelidir.

Bu nedenle, her adımın planlaması, tüm sürecin sonunda elde edilen genel fayda dikkate alınarak yapılmalıdır, bu da nihai sonucun seçilen kritere göre optimize edilmesini sağlar.

Ancak dinamik programlama evrensel bir çözüm yöntemi değildir. Bu yöntemle çözülen hemen hemen her problem kendi özellikleri ile karakterize edilir ve çözümü için en uygun yöntem setinin aranmasını gerektirir. Ek olarak, birçok durumla çok adımlı problemlerin çözülmesinin büyük hacimleri ve karmaşıklığı, düşük boyutlu problemlerin seçilmesi veya sıkıştırılmış bilgilerin kullanılması ihtiyacına yol açar.

Dinamik programlama aşağıdaki gibi sorunları çözmek için kullanılır: kıt sermaye yatırımlarının yeni kullanım alanları arasında dağılımı; talep ve stokları yönetmek için kuralların geliştirilmesi; çizim yapmak takvim planları ekipmanın bakımı ve revizyonu ve değiştirilmesi; ulaşım ağındaki en kısa mesafeleri arayın, vb.

Optimizasyon süreci n adıma bölünsün. Her adımda, iki tür değişken tanımlamak gerekir - bir durum değişkeni S ve bir kontrol değişkeni X. Değişken S, sistemin hangi durumlarda olabileceğini belirler. verilen k-th adım. S'ye bağlı olarak, bu adımda, X değişkeni ile karakterize edilen bazı kontroller uygulanabilir. X kontrolünün k. adımda uygulanması, bazı sonuçlar Wk(S,Xk) getirir ve sistemi yeni bir S"(S durumuna getirir) ,Xk) k. adımdaki her olası durum için, tüm olası kontroller arasından optimal kontrol X*k, k'den n'ye kadar olan adımlarda elde edilen sonuç optimal olacak şekilde seçilir. Bu sonucun sayısal karakteristiği olarak adlandırılır. Bellman fonksiyonu Fk(S) ve k adım sayısına ve S sisteminin durumuna bağlıdır.

Soruna yönelik tüm çözümler iki aşamaya ayrılmıştır. Koşullu optimizasyon adı verilen ilk aşamada, sonuncusundan başlayarak her adımda olası tüm durumlar için Bellman işlevi ve optimal kontroller bulunur.

Bellman fonksiyonu ve ilgili optimal kontroller n'den birinciye kadar olan tüm adımlar için bulunduktan sonra, koşulsuz optimizasyon adı verilen problem çözmenin ikinci aşaması gerçekleştirilir.

İÇİNDE Genel görünüm Dinamik programlama problemi şu şekilde formüle edilmiştir: Sistemi S0 başlangıç ​​durumundan Sn son durumuna aktaran böyle bir X* kontrolünün belirlenmesi gerekmektedir, burada amaç fonksiyonu F(S0,X*) en büyük değeri alır ( en küçük) değer.

Dinamik programlamanın matematiksel modelinin özellikleri aşağıdaki gibidir:

optimizasyon problemi, son bir çok adımlı kontrol süreci olarak formüle edilir;

amaç fonksiyonu toplamsaldır ve her adımın amaç fonksiyonlarının toplamına eşittir

her adımda Xk kontrol seçimi sadece bu adım Sk-1 tarafından sistemin durumuna bağlıdır ve önceki adımları etkilemez (hayır geri bildirim);

Her kontrol adımından sonraki Sk sisteminin durumu, yalnızca sistemin Sk-1 önceki durumuna ve bu kontrol eylemi Xk'ye bağlıdır (sonraki etki yok) ve bir durum denklemi olarak yazılabilir:

her adımda, kontrol Xk sınırlı sayıda kontrol değişkenine bağlıdır ve sistemin durumu Sk sonlu sayıda değişkene bağlıdır;

optimal kontrol X*, optimal kademeli kontroller dizisi tarafından belirlenen bir vektördür:

X*=(X*1, X*2, …, X*k, …, X*n),

sayısı, görev adımlarının sayısını belirler.

Koşullu optimizasyon. Yukarıda belirtildiği gibi, üzerinde bu aşama Bellman fonksiyonu ve optimal kontroller, geri tarama algoritmasına göre sonuncusundan başlayarak her adımda tüm olası durumlar için bulunur. Üzerinde sonuncusu optimal kontrol X*n'yi ve Bellman fonksiyonu Fn(S)'nin değerini bulmak zor değildir, çünkü

Fn(S)=maks(Wn(S, Xn))),

Xn'nin tüm olası değerleri üzerinde maksimum aranır.

Bellman fonksiyonunu her adımda aynı fonksiyona bağlayan, ancak önceki adımda hesaplanan özyinelemeli ilişkiye göre daha fazla hesaplama yapılır:

Fk(S)=maks(Wk(S,Xk)+Fk+1(S"(S,Xk))). (1)

Bu maksimum (veya minimum), k ve S için kontrol değişkeni X'in tüm olası değerleri tarafından belirlenir.

Koşulsuz optimizasyon. Bellman fonksiyonu ve ilgili optimal kontroller n'den birinciye kadar olan tüm adımlar için bulunduktan sonra (ilk adımda k=1, sistemin durumu ilk durumuna eşittir S0'a eşittir), problem çözmenin ikinci aşaması gerçekleştirilmektedir. Optimal kontrol, ilk adımda X1'de bulunur, bunun uygulaması sistemi S1(S,x1*) durumuna getirecektir, koşullu optimizasyon sonuçlarını kullanarak ikinci adımda optimal kontrolü bulabileceğimizi bilerek ve son n'inci adıma kadar devam eder.

Laboratuvar işi#1 (Doğrusal programlama problemi)

LP probleminin belirli bir matematiksel formülasyonu için, değişkenlerin negatif olmaması ek koşulunu varsayarak, aşağıdaki eylemleri gerçekleştirin:

Problemi grafiksel olarak çözün;

Problemi kurallı gösterime getirin;

Simpleks bir tablo yapın;

Soruna bir çözüm üretin simpleks yöntemi manuel olarak veya bir bilgisayar kullanarak;

evreleme gerçekleştirin ikili problem LP;

Daha önce elde edilen simpleks tablodan ikili probleme bir çözüm elde edin ve elde edilen sonuçları analiz edin;

Çözüm sonuçlarını bir Excel elektronik tablosunda kontrol edin;

Her öğe için sonuçları içeren bir rapor hazırlayın.

Grafik yöntemi. Bir çözüm çokgeni oluşturmak için orijinal sistemi dönüştürüyoruz

, alırız

sınır çizgilerini çizin.

Doğrusal fonksiyon F=f(x), c1x1 + c2x2 = const düz çizgi denklemidir. f(x)=0 için hedef fonksiyonu çizelim. 3x1 + 4x2 = 0 düz bir çizgi oluşturmak için, N = (3; 4) yarıçap vektörünü oluştururuz ve 0 noktasından ona dik bir çizgi çizeriz. Oluşturulan F=0 doğrusunu kendisine paralel N vektörü yönünde hareket ettiriyoruz.

Şekil 1'den, bu çizginin, F fonksiyonunun maksimum değerini aldığı B noktasında oluşturulan çözümlerin çokgenine göre referans çizgisi olduğu sonucu çıkar. B noktası 0.7x1 + 2x2 ≤ 13.1 ve 2.3x1 + 2x2 = 23/ doğrularının kesiştiği noktada yer alır/ Koordinatlarını belirlemek için denklem sistemini çözeriz:

Optimal görev planı: x1 ​​= 6.187; х2 = 4.38, х1 ve х2 değerlerini amaç fonksiyonuna koyarak Fmax= 3*6.187+4*4.38=36.08 elde ederiz.

Bu nedenle, 36.06 $ 'lık maksimum karı elde etmek için 6 adet üretimi planlamanız gerekir. ürünler P1 ve 4 adet. ürünler P2.

LP probleminin kanonik formu. Kaynak tahsis problemini kanonik biçimde yazalım. Orijinal kısıtlama sistemine x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 negatif olmayan değişkenleri ekleyerek şunları elde ederiz:

Simpleks LP tablosu. Temel değişkenler (x3, x4, x5) durumunda, ilk simpleks tablosu şöyle görünecektir:

Tablo 1.

Zaten x(0) = T (serbest üyeler sütunu) temel planına karşılık gelir.

Bu yöntem, bir doğrusal programlama probleminin referans çözümlerinin amaçlı bir şekilde numaralandırılması yöntemidir. Optimum çözümü bulmak veya en uygun çözümün olmadığını belirlemek için sonlu sayıda adıma izin verir.

1. Optimum referans çözümünü bulmak için bir yöntem belirtin
2. Bir referans çözümünden diğerine, amaç fonksiyonunun değerinin optimale daha yakın olacağı geçiş yöntemini belirtin, yani. referans çözümünü iyileştirmenin bir yolunu belirtin
3. Optimal çözüm üzerinde destek çözümlerinin sayımını zamanında durdurmanıza veya hiçbir optimal çözüm olmadığı sonucunu takip etmenize izin veren kriterleri belirleyin.

Doğrusal programlama problemlerini çözmek için tek yönlü yöntemin algoritması

1. Sorunu kurallı forma getirin
2. "Birim bazında" bir başlangıç ​​referans çözümü bulun (referans çözümü yoksa, kısıtlamalar sisteminin uyumsuzluğundan dolayı problemin bir çözümü yoktur)
3. Referans çözüm bazında vektör açılımlarının tahminlerini hesaplayın ve simpleks yöntemi tablosunu doldurun
4. Optimal çözümün benzersizliği için kriter sağlanırsa, problemin çözümü sona erer.
5. Bir optimal çözüm kümesinin varlığı için koşul sağlanırsa, o zaman basit numaralandırma ile tüm optimal çözümler bulunur.

Simpleks yöntemiyle problem çözme örneği

Simpleks yöntemini kullanarak sorunu çözün:

Çözüm:

Problemi kanonik forma getiriyoruz.

Bunu yapmak için, birinci eşitsizlik kısıtlamasının sol tarafına +1 katsayılı ek bir x 6 değişkeni ekliyoruz. x 6 değişkeni, amaç fonksiyonuna sıfır katsayısı ile dahil edilir (yani dahil edilmez).

Alırız:

İlk referans çözümünü buluyoruz. Bunu yapmak için, serbest (çözülmemiş) değişkenleri sıfır x1 = x2 = x3 = 0 olarak eşitleriz.

alırız Referans çözümü X1 = (0.0.0.24.30.6) birim bazında B1 = (A4, A5, A6).

Hesaplamak vektör ayrıştırma tahminleri aşağıdaki formüle göre referans çözüm temelinde koşullar:

Δ k \u003d C b X k - c k

• C b = (с 1 , с 2 , ... , с m) temel değişkenli amaç fonksiyonu katsayılarının vektörüdür
• X k = (x 1k , x 2k , ... , x mk) referans çözüm bazında karşılık gelen A k vektörünün genişleme vektörüdür
• C k - x k değişkeni için amaç fonksiyonunun katsayısı.

Tabana dahil edilen vektörlerin tahminleri her zaman sıfıra eşittir. Referans çözümü, açılım katsayıları ve referans çözüm bazında koşul vektörlerinin açılımlarının tahminleri şu şekilde yazılır: tek yönlü tablo:

Tablonun üstünde, tahminlerin hesaplanmasında kolaylık olması için amaç fonksiyonunun katsayıları yazılmıştır. İlk sütun "B", referans çözüm bazında dahil edilen vektörleri içerir. Bu vektörlerin yazılma sırası, kısıtlama denklemlerinde izin verilen bilinmeyenlerin sayısına karşılık gelir. Tablonun ikinci sütununda "b ile" amaç fonksiyonunun katsayıları aynı sırada temel değişkenlerle yazılmıştır. "C b" sütunundaki amaç fonksiyonunun katsayılarının doğru düzenlenmesiyle, tabana dahil edilen birim vektörlerin tahminleri her zaman sıfıra eşittir.

Tablonun son satırında, "A 0" sütununda Δ k tahminleri ile amaç fonksiyonunun değerleri Z(X 1) referans çözümüne yazılır.

İlk referans çözümü optimal değildir, çünkü maksimum problemde A 1 ve A 3 vektörleri için Δ 1 = -2, Δ 3 = -9 tahminleri negatiftir.

Referans çözüm iyileştirme teoremine göre, maksimum problemdeki en az bir vektörün negatif bir tahmini varsa, o zaman amaç fonksiyonunun değerinin daha büyük olacağı yeni bir referans çözüm bulmak mümkündür.

İki vektörden hangisinin amaç fonksiyonunda daha büyük bir artışa yol açacağını belirleyelim.

Amaç fonksiyonu artışı şu formülle bulunur: .

Formülü kullanarak birinci ve üçüncü sütunlar için θ 01 parametresinin değerlerini hesaplıyoruz:

l = 1 için θ 01 = 6, l = 1 için θ 03 = 3 elde ederiz (tablo 26.1).

İlk vektör ΔZ 1 = - 6 * (- 2) = 12 tabana ve üçüncü vektör ΔZ 3 = - 3 * (- 9) = 27 olduğunda amaç fonksiyonunun artışını buluruz.

Bu nedenle, optimal çözüme daha hızlı bir yaklaşım için, ilk satırda θ 03 parametresinin minimumuna ulaşıldığından, A6 bazının ilk vektörü yerine A3 vektörünü referans çözümün bazına dahil etmek gerekir. (l = 1).

Jordan dönüşümünü X13 = 2 elemanı ile gerçekleştiriyoruz, ikinci referans çözümünü X2 = (0.0.3.21.42.0) B2 = (A3, A4, A5) bazında elde ediyoruz. (tablo 26.2)

Bu çözüm optimal değildir, çünkü A2 vektörü Δ2 = - 6 negatif bir tahmine sahiptir. Çözümü geliştirmek için, A2 vektörünü referans çözüm bazına dahil etmek gerekir.

Tabandan türetilen vektörün sayısını belirleriz. Bunu yapmak için, ikinci sütun için θ 02 parametresini hesaplıyoruz, l = 2 için 7'ye eşittir. Bu nedenle, ikinci taban vektörü A4'ü tabandan türetiyoruz. Jordan dönüşümünü x 22 = 3 elemanı ile gerçekleştiriyoruz, üçüncü referans çözümü X3 = (0.7.10.0.63.0) B2 = (A3, A2, A5) (tablo 26.3) elde ediyoruz.

Bu çözüm tek optimal çözümdür, çünkü tabana dahil olmayan tüm vektörler için tahminler pozitiftir.

Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 7/2.

Yanıt vermek: maks Z(X) = 201, X = (0,7,10,0,63)'de.

Ekonomik analizde doğrusal programlama yöntemi

Doğrusal programlama yöntemiüretimde kullanılan kaynaklarla (sabit varlıklar, malzemeler, işgücü kaynakları) ilgili ciddi kısıtlamalar karşısında en optimal ekonomik çözümün gerekçelendirilmesini mümkün kılar. Bu yöntemin ekonomik analizde uygulanması, esas olarak kuruluşun faaliyetlerinin planlanmasıyla ilgili sorunları çözmemize olanak tanır. Bu yöntem, çıktının optimal değerlerinin yanı sıra en çok yönün belirlenmesine yardımcı olur. etkili kullanım Kuruluşun kullanabileceği kaynaklar.

Bu yöntemi kullanarak, uç değerleri, yani değişkenlerin maksimum ve minimum işlevlerini bulmaktan oluşan aşırı uç problemlerin çözümü gerçekleştirilir.

Bu süre sistemin kararına bağlıdır. lineer denklemler analiz edilen ekonomik fenomenlerin doğrusal, kesinlikle işlevsel bir bağımlılıkla bağlandığı durumlarda. Doğrusal programlama yöntemi, belirli sınırlayıcı faktörlerin varlığında değişkenleri analiz etmek için kullanılır.

Sözde taşıma probleminin doğrusal programlama yöntemi kullanılarak çözümü oldukça yaygındır. Bu görevin içeriği, maksimum sayıda müşteriye hizmet verme ihtiyacı varsa, araç sayısı, taşıma kapasitesi, çalışma süresi ile ilgili mevcut kısıtlamalar altında araçların işletilmesiyle ilgili maliyetleri en aza indirmektir. .

Ayrıca, Bu methodçizelgeleme problemini çözmede geniş uygulama alanı bulur. Bu görev, hem bu personelin üyeleri hem de kuruluşun müşterileri için en kabul edilebilir olan bu kuruluş personelinin çalışma süresinin böyle bir dağılımından oluşur.

Amaç, mevcut personel sayısını ve çalışma saatlerini sınırlarken hizmet verilen müşteri sayısını en üst düzeye çıkarmaktır.

Bu nedenle, yerleştirme ve kullanım analizinde doğrusal programlama yöntemi çok yaygındır. Çeşitli türler kaynakların yanı sıra kuruluşların faaliyetlerini planlama ve tahmin etme sürecinde.

Bununla birlikte, matematiksel programlama, aralarında doğrusal olmayan bir ilişki olan ekonomik olaylara da uygulanabilir. Bu amaçla doğrusal olmayan, dinamik ve dışbükey programlama yöntemleri kullanılabilir.

Doğrusal olmayan programlama, amaç fonksiyonunun veya kısıtlamaların veya her ikisinin de doğrusal olmayan doğasına dayanır. Bu koşullar altında amaç fonksiyonu ve kısıt eşitsizliklerinin biçimleri farklı olabilir.

Doğrusal olmayan programlama, ekonomik analizde, özellikle kuruluşun faaliyetlerinin etkinliğini ifade eden göstergeler ile bu faaliyetin hacmi, üretim maliyetlerinin yapısı, piyasa koşulları vb. arasındaki ilişkiyi kurarken kullanılır.

Dinamik programlama, bir karar ağacı oluşturmaya dayanır. Bu ağacın her katmanı, önceki kararın sonuçlarını belirlemek ve bu kararın etkisiz değişkenlerini ortadan kaldırmak için bir aşama olarak hizmet eder. Böylece dinamik programlama çok adımlı, çok aşamalı bir karaktere sahiptir. Bu tür programlama, organizasyonun hem şimdi hem de gelecekte gelişimi için en iyi seçenekleri bulmak amacıyla ekonomik analizde kullanılır.

Dışbükey programlama, doğrusal olmayan bir programlama türüdür. Bu tür programlama, organizasyonun faaliyetlerinin sonuçları ile onun maruz kaldığı maliyetler arasındaki ilişkinin doğrusal olmayan doğasını ifade eder. Dışbükey (aksi takdirde içbükey) programlama dışbükey ayrıştırır amaç fonksiyonları ve dışbükey kısıtlama sistemleri (nokta izin verilen değerler). Maliyetleri en aza indirmek için ekonomik faaliyetin analizinde dışbükey programlama kullanılır ve analiz edilen göstergeleri ters yönde etkileyen faktörlerin etkisi üzerindeki mevcut kısıtlamalar koşullarında geliri en üst düzeye çıkarmak için içbükey programlama kullanılır. Sonuç olarak, incelenen programlama türleri altında, dışbükey amaç fonksiyonları minimize edilmiş ve içbükey olanlar maksimize edilmiştir.