Doğrusal programlama yöntemleri. Doğrusal programlama

Yöntemler doğrusal programlama Ekonomide sıklıkla karşılaşılan birçok aşırı problemi çözmek için kullanılır. Bu tür problemleri çözmek, değişken miktarlardaki bazı fonksiyonların uç değerlerini (maksimum ve minimum) bulmaktan ibarettir.
Doğrusal programlama, incelenen fenomenler arasındaki ilişki kesinlikle işlevsel olduğunda, bir doğrusal denklem sisteminin (denklemlere ve eşitsizliklere dönüştürülerek) çözülmesine dayanır. Değişkenlerin matematiksel ifadesi, belirli bir sıra, hesaplama sırası (algoritma) ve mantıksal analiz ile karakterize edilir. Yalnızca incelenen değişkenlerin ve faktörlerin matematiksel kesinliğe ve niceliksel sınırlamalara sahip olduğu, bilinen bir hesaplama dizisi sonucunda faktörlerin birbirinin yerine geçebileceği, hesaplamalardaki mantık, matematiksel mantık ile birleştirildiği durumlarda kullanılabilir. incelenen olgunun özünün mantıksal olarak anlaşılması.
Endüstriyel üretimde bu yöntemi kullanarak, örneğin, makinelerin, birimlerin, üretim hatlarının optimum genel verimliliği hesaplanır (belirli bir ürün yelpazesi ve diğer belirli değerler için) ve malzemelerin rasyonel kesilmesi sorunu çözülür (optimum verimle). iş parçaları). Tarımda, belirli bir miktardaki yem için (türüne ve içerdiği besin maddelerine göre) minimum yem rasyonunun maliyetini belirlemek için kullanılır. Karışım problemi aynı zamanda dökümhane üretiminde de uygulama alanı bulabilir (metalurjik yükün bileşimi). Aynı yöntem, tüketici işletmelerinin üretici işletmelere rasyonel olarak bağlanması sorunu olan ulaştırma sorununu çözmek için de kullanılıyor.
Doğrusal programlama kullanılarak çözülen tüm ekonomik problemler, alternatif çözümler ve belirli sınırlayıcı koşullarla ayırt edilir. Böyle bir sorunu çözmek, kabul edilebilir tüm olası (alternatif) seçenekler arasından en iyisini, yani Optimal'i seçmek anlamına gelir. Ekonomide doğrusal programlama yönteminin kullanılmasının önemi ve değeri, çok önemli sayıda seçenek arasından en uygun seçeneğin seçilmesidir. alternatif seçenekler. Bu tür sorunları başka yöntemlerle çözmek neredeyse imkansızdır.

Örnek olarak, üretim ekipmanının çalışma süresinin rasyonel kullanımı sorununu çözmeyi düşünün.
Operasyon planına uygun olarak taşlama bölümünde Aralık ayının ilk haftasında A tipi rulmanlar için 500 adet, B tipi rulmanlar için 300 adet ve B tipi rulmanlar için 450 adet ring üretildi.Tüm ringler değiştirilebilir iki makinede taşlandı. farklı performans. Her makinenin makine süresi 5000 dakikadır. Çeşitli halkaların imalatındaki işlemlerin karmaşıklığı (halka başına dakika olarak) aşağıdaki verilerle karakterize edilir (Tablo 6.5).
Tablo 6.5
Operasyonların makineler arasında dağıtılması için en uygun seçeneğin ve bu optimum seçenekle harcanacak zamanın belirlenmesi gerekmektedir. Görevi tamamlayalım simpleks yöntemi.
Bu problemin matematiksel modelini derlemek için aşağıdakileri tanıtıyoruz: semboller: jc, x2, xъ, - sırasıyla makine I'de üretilen L, B, V tipi rulmanlar için halka sayısı; x4, x5, x6 - sırasıyla makine II'de üretilen A, B, C tipi rulmanlar için halka sayısı.
Optimallik kriterini yansıtan doğrusal form şöyle görünecektir:
min a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 kısıtlamalarla
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
x, = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=l, ..., 6

Ek (yardımcı) ve hayali değişkenler ekleyerek problem durumunu dönüştürelim. Koşulu şu şekilde yazalım:
başak lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
Bilgisayar zamanının kısıtlayıcı koşullarını ve üretilen ürün miktarını yansıtan bir denklem sistemi:
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Bu sorunun çözümü tabloda sunulmaktadır. 6.6. Optimum seçenek yedinci aşamada (yineleme) elde edildi. Makine I 125 adet A tipi rulman halkası, 450 adet B tipi rulman halkası üretmiş olsaydı ve makine II 375 adet A tipi rulman halkası ve 300 adet B tipi rulman bileziği üretseydi, bu tür bir ekipman yüküyle 350 dakikalık makine süresi olurdu. makine II için serbest bırakıldı. Harcanan toplam süre optimal seçenek 9650 dakikaya tekabül ederken gerçekte 10.000 dakika bilgisayar zamanı harcandı.
Doğrusal programlama kullanılarak çözülen çok tipik bir problem, ulaştırma problemidir. Bunun anlamı, tüketici mallarını üreticiden tüketiciye, toptan depolardan ve üslerden perakende satış noktalarına teslim ederken kargo cirosunu en aza indirmektir. Simpleks yöntemi veya dağıtım yöntemi kullanılarak çözülebilir.
Dağıtım sorununun dağıtım yöntemini kullanarak çözümü, “Ekonomik Analiz Teorisi” ders kitabının üçüncü baskısında (“Finans ve İstatistik”, 1996) verilmiştir.

Takım tezgahlarının rasyonel kullanımı sorununun simpleks yöntemini kullanarak çözülmesi

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

Doğrusal programlama (LP), ilk ve en kapsamlı şekilde çalışılan bölümlerden biridir. matematiksel programlama. “Matematiksel programlama” disiplininin gelişmeye başladığı bölüm doğrusal programlamaydı. Disiplinin başlığındaki “programlama” teriminin “bilgisayar için programlama (yani program derlemek)” terimiyle hiçbir ortak yanı yoktur, çünkü "Doğrusal programlama" disiplini, bilgisayarların matematik, mühendislik, ekonomik ve diğer problemleri çözmek için yaygın olarak kullanılmaya başlandığı zamandan önce bile 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. Sonuç olarak, İngilizce “doğrusal programlama”nın doğru çevirisi “doğrusal programlama” değil, disiplinin içeriğini daha doğru şekilde yansıtan “doğrusal planlama” olacaktır. Ancak doğrusal programlama, doğrusal olmayan programlama, matematiksel programlama vb. terimler literatürümüzde genel kabul görmüş ve dolayısıyla korunacaktır.

Böylece, İkinci Dünya Savaşı'ndan sonra ortaya çıkan ve hızla gelişmeye başlayan doğrusal programlama, geniş bir alana yayılma olasılığı nedeniyle matematikçilerin, iktisatçıların ve mühendislerin dikkatini çekmiştir. pratik uygulama ve matematiksel uyum.

Doğrusal programlamanın, gerçek dünyanın doğrusal temsili hipotezine dayanabilen süreç ve sistemlerin matematiksel modellerinin çözümünde uygulanabilir olduğunu söyleyebiliriz.

Doğrusal programlama, yönetim ve üretim planlaması gibi ekonomik sorunların çözümünde kullanılır; Ekipmanın optimum yerleşimini belirleme problemlerinde deniz gemileri atölyelerde; optimal kargo taşıma planının belirlenmesi problemlerinde (nakliye problemi); optimal personel dağılımı vb. problemlerinde.

Doğrusal programlamanın (LP) görevi, yukarıda açıklandığı gibi, minimum (veya maksimum) değeri bulmaktır. doğrusal fonksiyon doğrusal kısıtlamalar altındadır.

LP problemlerini çözmek için çeşitli yöntemler vardır. Bu yazıda bunlardan bazıları tartışılacaktır, özellikle:

DP probleminin çözümü için grafiksel yöntem;

Simpleks yöntemi;

LP probleminin Excel elektronik tablosunu kullanarak çözülmesi;

3. Doğrusal olmayan programlama kavramı

Çoğu mühendislik probleminde matematiksel modelin oluşturulması doğrusal programlama problemine indirgenemez.

Gerçek nesnelerin veya teknolojik süreçlerin tasarlanması problemlerindeki matematiksel modeller, gerçek fiziksel ve kural olarak bunlarda 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. Fiziksel fizibilite sağlayan aşırı aralıklarla sınırlıdırlar bu nesnenin veya süreç. Sonuç olarak araştırma projelerinde ve tasarım problemlerinde karşılaşılan matematiksel programlama problemlerinin çoğu doğrusal olmayan programlama (NP) problemleridir.

Bu çalışmada NP problemlerini çözmek için Lagrange çarpanları yöntemi gibi bir yöntemi ele alacağız.

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

4. Dinamik programlama

Dinamik programlama matematiksel aparat analiz edilen durumun belirsizlik faktörleri içermediği ancak mevcut olduğu durumlarda en uygun çözümü hızlı bir şekilde bulmanızı sağlar. çok sayıda Farklı sonuçlar getiren davranışsal seçenekler arasından en iyisini seçmek gerekir. Dinamik programlama, belirli bir sınıftaki problemleri daha küçük, daha az karmaşık problemlere bölerek çözmeye yaklaşır. Prensipte bu tür problemler tüm unsurların sıralanmasıyla çözülebilir. olası 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 incelenebilir.

Dinamik programlama yöntemlerini kullanarak problem çözme, R.E. Bellman tarafından formüle edilen optimallik ilkesi temelinde gerçekleştirilir: optimal davranış, ne olursa olsun, orijinal durum Sistem ve ilk çözüm, sonraki çözüm, ilk çözümden kaynaklanan duruma göre en uygun davranışı belirlemelidir.

Bu nedenle, her adımın planlanması, tüm sürecin tamamlanmasından sonra elde edilen genel fayda dikkate alınarak gerçekleştirilmelidir; bu, seçilen kritere göre nihai sonucun optimize edilmesine olanak tanır.

Ancak dinamik programlama evrensel yöntemçözümler. Bu yöntemle çözülen hemen hemen her problem, kendine has özelliklerle karakterize edilir ve onu çözmek için en uygun yöntem kümesinin araştırılmasını gerektirir. Ek olarak, çok adımlı problemlerin birçok durumla çö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çmaktadır.

Dinamik programlama şu gibi sorunları çözmek için kullanılır: kıt sermaye yatırımlarının yeni kullanım alanları arasında dağıtılması; talep ve envanteri yönetmek için kuralların geliştirilmesi; ekipmanın mevcut ve büyük onarımları ve değiştirilmesi için takvim planlarının hazırlanması; en kısa mesafeleri arayın ulaşım ağı vesaire.

Optimizasyon sürecini n adıma bölelim. Her adımda, iki tip değişkenin tanımlanması gerekir; durum değişkeni S ve kontrol değişkeni X. S değişkeni, sistemin belirli bir zamanda hangi durumlarda olabileceğini belirler. k. adım. S'ye bağlı olarak, bu adımda X değişkeni ile karakterize edilen bazı kontrolleri uygulamak mümkündür. X kontrolünün k. adımda uygulanması, Wk(S,Xk) sonucunu getirir ve sistemi bazı yeni S durumuna aktarır"( S,Xk).K'inci adımdaki her olası durum için, tüm olası kontroller arasında, k'inci adımdan n'inci dönüşe kadar adımlarda elde edilen sonucu sağlayacak şekilde bir optimal kontrol X*k seçilir. Bu sonucun sayısal karakteristiği Bellman fonksiyonu Fk(S) olarak adlandırılır ve k adım sayısına ve S sisteminin durumuna bağlıdır.

Sorunun tüm çözümleri iki aşamaya ayrılmıştır. Koşullu optimizasyon olarak adlandırılan ilk aşamada, son adımdan başlayarak her adımda olası tüm durumlar için Bellman fonksiyonu ve optimal kontroller bulunur.

Bellman fonksiyonu ve buna karşılık gelen optimal kontroller, n'inci adımdan birinci adıma kadar tüm adımlar için bulunduktan sonra, kısıtsız optimizasyon adı verilen problemin çözümünün ikinci aşaması gerçekleştirilir.

Genel olarak dinamik programlama problemi şu şekilde formüle edilir: Sistemi başlangıç ​​durumu S0'dan amaç fonksiyonu F(S0,X*)'in aldığı son durum Sn'ye aktaracak bir X* kontrolünün belirlenmesi gerekir. en büyük (en küçük) değer.

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

optimizasyon problemi sonlu, çok adımlı bir kontrol süreci olarak formüle edilmiştir;

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

Her adımdaki Xk kontrolünün seçimi yalnızca bu Sk-1 adımındaki sistemin durumuna bağlıdır ve önceki adımları etkilemez (hiçbir geri bildirim);

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

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

optimal kontrol X*, optimal adım adım kontrollerin sırası ile belirlenen bir vektördür:

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

bunların sayısı görevin adım sayısını belirler.

Koşullu optimizasyon. Yukarıda belirtildiği gibi, bu aşamada Bellman fonksiyonu ve optimal kontroller, geriye doğru tarama algoritmasına uygun olarak son adımdan başlayarak her adımda olası tüm durumlar için bulunur. Açık sonuncu Adımda, optimal kontrol X*n'yi ve Bellman fonksiyonunun Fn(S) değerini bulmak zor değildir, çünkü

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

Xn'nin tüm olası değerleri üzerinde maksimumun arandığı yer.

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

Fk(S)=max(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 buna karşılık gelen optimal kontroller, n'inci adımdan birinci adıma kadar tüm adımlar için bulunduktan sonra (ilk adımda k=1 sistemin durumu, başlangıç ​​durumu S0'a eşittir), problemin çözümünün ikinci aşaması: gerçekleştirillen. Optimum kontrol ilk X1 adımında bulunur ve bunun uygulanması sistemi S1(S,x1*) durumuna götürecektir; bunun mümkün olduğunu bilerek, koşullu optimizasyon sonuçlarını kullanarak ikinci adımda optimal kontrolü bulmanın mümkün olduğunu bilin. adım vb. son n'inci adıma kadar devam eder.

Laboratuvar işi No. 1 (Doğrusal programlama problemi)

Belirli bir şey için matematiksel formülasyon LP probleminin çözümü için değişkenlerin negatif olmaması koşulunu ek olarak kabul ederek aşağıdaki işlemleri gerçekleştirin:

Problemi grafiksel olarak çözün;

Sorunu kanonik notasyon biçimine getirin;

Simpleks bir tablo oluşturun;

Simpleks yöntemini kullanarak sorunu çözün manuel olarak veya bilgisayar kullanarak;

İkili DP probleminin formülasyonunu gerçekleştirin;

Daha önce elde edilen simpleks tablodan ikili problemin çözümünü bulun ve elde edilen sonuçları analiz edin;

Çözüm sonuçlarını kontrol edin masa işlemcisi Excel;

Her öğenin sonuçlarını içeren bir rapor yazın.

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

, alıyoruz

Sınır çizgilerini çizelim.

Doğrusal fonksiyon F=f(x) bir doğrunun c1x1 + c2x2 = sabit denklemidir. Bir grafik oluşturalım amaç fonksiyonu f(x)=0 olduğunda. 3x1 + 4x2 = 0 doğrusunu oluşturmak için N = (3; 4) yarıçap vektörünü oluşturun ve 0 noktası boyunca ona dik bir çizgi çizin. Oluşturulan F=0 düz çizgisini kendisine paralel olarak N vektörü yönünde hareket ettiriyoruz.

Şekil 1'den, bu düz çizginin, F fonksiyonunun maksimum değerini aldığı B noktasında oluşturulan çözüm çokgenine göre referans çizgisi haline geldiği anlaşılmaktadır. B noktası 0,7x1 + 2x2 ≤ 13,1 ve 2,3x1 + 2x2 =23/ doğrularının kesişim noktasında yer alır. Koordinatlarını belirlemek için denklem sistemini çözeriz:

Optimum görev planı: x1 ​​= 6,187; x2 = 4,38, x1 ve x2 değerlerini amaç fonksiyonunda yerine koyarsak Fmax = 3*6,187+4*4,38=36,08 elde ederiz.

Dolayısıyla maksimum 36,06$ kar elde etmek için 6 adet üretimin planlanması gerekmektedir. ürünler P1 ve 4 adet. P2 ürünleri.

LP probleminin kanonik formu. Kaynak tahsis problemini kanonik formda yazalım. Negatif olmayan değişkenler x3 ≥ 0, x4 ≥ 0, x5 ≥ 0'ı orijinal kısıtlama sistemine ekleyerek şunu elde ederiz:

LP'nin Simpleks tablosu. Temel değişkenler (x3, x4, x5) durumunda, başlangıç ​​simpleks tablosu şöyle görünecektir:

Tablo 1.

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

Karar teorisindeki optimizasyon problemleri arasında en ünlüsü, maksimize edilmiş F(X) fonksiyonunun doğrusal olduğu ve A kısıtlamalarının doğrusal eşitsizliklerle belirtildiği doğrusal programlama problemleridir. Bir örnekle başlayalım (bkz.).

Üretim görevi. Atölye sandalye ve masa üretebilmektedir. Bir sandalye üretmek için 5 birim, masa üretmek için ise 20 birim (ayak maun) malzeme gerekmektedir. Bir sandalye için 10 adam-saat, bir masa için 15 adam-saat gerekiyor. 400 adet malzeme ve 450 adam-saat var. Sandalye üretiminin karı 45 dolar, masa üretiminin karı ise 80 dolar. Maksimum kar elde etmek için kaç tane sandalye ve masa yapmanız gerekiyor?

Şunu belirtelim: X 1 - yapılan sandalye sayısı, X 2 - yapılan masa sayısı. Optimizasyon problemi şu şekildedir:

45 X 1 + 80 X 2 → maks,

5 X 1 + 20 X 2 ≤ 400,

10 X 1 + 15 X 2 ≤ 450,

İlk satır amaç fonksiyonunu içerir - X 1 sandalye ve X 2 masa üretirken kar. X 1 ve X 2 değişkenlerinin optimal değerleri seçilerek maksimize edilmesi gerekir. Bu durumda malzeme kısıtlamalarına uyulmalıdır (ikinci sıra) - 400 feet'ten fazla maun ağacı kullanılmamıştır. Ve ayrıca emek kısıtlamaları (üçüncü satır) - harcanan 450 saatten fazla değil. Ayrıca masa sayısı ile sandalye sayısının negatif olmadığını da unutmamalıyız. X 1 = 0 ise sandalye üretilmiyor demektir. En az bir sandalye yapılmışsa X 1 pozitiftir. Ancak negatif bir çıktı hayal etmek imkansızdır - X 1, ekonomik açıdan negatif olamaz, ancak matematiksel açıdan böyle bir sınırlama görülemez. Problemin dördüncü ve beşinci satırları değişkenlerin negatif olmadığını belirtmektedir.

Koşullar üretim görevi koordinat düzleminde gösterilebilir. X 1 değerlerini yatay apsis ekseni boyunca, X 2 değerlerini ise dikey ordinat ekseni boyunca çizeceğiz. Daha sonra malzeme kısıtlamaları ve optimizasyon probleminin son iki satırı, çıktı hacimlerinin olası değerlerini (X 1, X 2) bir üçgen şeklinde vurgular (Şekil 1).

Bu nedenle, malzeme kısıtlamaları dışbükey bir çokgen, özellikle bir üçgen olarak tasvir edilir. Bu üçgen, orijine bitişik bölgenin birinci çeyrekten kesilmesiyle elde edilir. Kesme, eşitsizliği eşitlikle değiştiren, orijinal problemin ikinci çizgisine karşılık gelen düz bir çizgi ile gerçekleştirilir. Düz çizgi sandalyelere karşılık gelen X1 eksenini (80.0) noktasında keser. Bu, tüm malzemenin sandalye yapmak için kullanılması durumunda 80 sandalye yapılacağı anlamına geliyor. Aynı düz çizgi tablolara karşılık gelen X2 eksenini (0.20) noktasında kesmektedir. Bu, masa yapmak için tüm malzemenin kullanılması durumunda 20 masa yapılacağı anlamına gelir. Üçgenin içindeki tüm noktalarda eşitsizlik sağlanır, ancak eşitlik sağlanmaz - malzeme kalacaktır.

İşgücü kısıtlamaları da benzer şekilde gösterilebilir (Şekil 2).

Böylece çalışma kısıtlamaları da bir üçgen olarak tasvir ediliyor. Bu üçgen aynı zamanda orijine bitişik bölgenin birinci çeyrekten kesilmesiyle de elde edilir. Kesme, eşitsizliği eşitlikle değiştiren, orijinal problemin üçüncü çizgisine karşılık gelen düz bir çizgi ile gerçekleştirilir. Düz çizgi sandalyelere karşılık gelen X1 eksenini (45.0) noktasında keser. Bu, tüm emek kaynaklarının sandalye yapmak için kullanılması durumunda 45 sandalye yapılacağı anlamına gelir. Aynı düz çizgi tablolara karşılık gelen X2 eksenini (0.30) noktasında kesmektedir. Bu, eğer tüm işçiler masa yapımında görevlendirilirse 30 masa yapılacağı anlamına gelir. Üçgenin içindeki tüm noktalarda eşitlik değil eşitsizlik sağlanır - işçilerin bir kısmı boşta kalır.

Görünür bir çözüm olmadığını görüyoruz: 80 sandalyenin üretimi için malzeme var ama yeterli işçi yok, 30 masanın üretimi için ise emek var ama malzeme yok. ikisi birden. Ama hangi oranda?

Bu soruyu cevaplamak için Şekil 1 ile Şekil 2'yi "birleştirmeniz" ve alanı elde etmeniz gerekir. Muhtemel çözümler ve ardından amaç fonksiyonunun bu sette hangi değerleri aldığını takip edin (Şekil 3).

Böylece sandalye ve masaların üretim hacimleri için olası değerler kümesi (X 1, X 2) veya başka bir deyişle genel optimizasyon probleminde kontrol parametresine kısıtlamalar getiren A kümesi şu ifadeyi temsil eder: iki üçgenin kesişimi, yani Şekil 3'te gösterilen dışbükey dörtgen. Üç köşesi açıktır; bunlar (0.0), (45.0) ve (0.20). Dördüncüsü, iki düz çizginin kesişimidir - Şekil 1 ve Şekil 2'deki üçgenlerin sınırları, yani. bir denklem sistemini çözme

5 X 1 + 20 X 2 = 400,

10X1 + 15X2 = 450.

İlk denklemden: 5 X 1 = 400 - 20 X 2, X 1 = 80 - 4 X 2. İkinci denklemde yerine şunu koyun: 10 (80 - 4 X 2) + 15 X 2 = 800 - 40X 2 + 15 X 2 = 800 - 25 X 2 = 450, dolayısıyla 25 X 2 = 350, X 2 = 14, dolayısıyla X 1 = 80 - 4 x 14 = 80 -56 = 24. Yani dörtgenin dördüncü köşesi (24, 14)'tür.

Dışbükey bir çokgen üzerinde doğrusal bir fonksiyonun maksimumunu bulmamız gerekiyor. (Doğrusal programlamanın genel durumunda, sonlu boyutlu bir doğrusal uzayda yer alan dışbükey bir çokyüzlü üzerindeki doğrusal bir fonksiyonun maksimumu.) Doğrusal programlamanın temel fikri, maksimumun çokgenin köşelerinde elde edilmesidir. Genel durumda - bir tepe noktasında ve bu tek maksimum noktadır. Özellikle - ikide ve sonra bunları birbirine bağlayan segment de maksimum noktalardan oluşur.

45 X 1 + 80 X 2 amaç fonksiyonu tepe noktasında (0,0) minimum 0 değerini alır. Argümanlar arttıkça bu fonksiyonun boyutu da artar. Tepe noktasında (24.14) 2200 değerini alır. Bu durumda 45 X 1 + 80 X 2 = 2200 düz çizgisi, 5 X 1 + 20 X 2 = 400 ve 10 X 1 + 15 X 2 doğrudan kısıtlamaları arasından geçer. = 450, aynı noktada kesişiyor. Bundan ve geri kalan iki köşenin doğrudan doğrulanmasından, 2200'e eşit olan amaç fonksiyonunun maksimumunun tepe noktasında (24,14) elde edildiği sonucu çıkar.

Böylece optimum çıktı: 24 sandalye ve 14 masa. Bu durumda tüm malzeme ve tüm işgücü kaynakları kullanılır ve kâr 2.200$'a eşit olur.

İkili sorun. Her doğrusal programlama probleminin karşılık gelen ikili problemi vardır. Orijinal problemle karşılaştırıldığında satırlar sütunlara dönüşüyor, eşitsizlikler işaret değiştiriyor, maksimum yerine minimum aranıyor (ya da tam tersi, minimum yerine maksimum aranıyor). İkilinin ikilisi olan görev, asıl görevin kendisidir. Orijinal problemi (solda) ve ikilisini (sağda) karşılaştıralım:

45 X 1 + 80 X 2 → maks, 400 W 1 + 450 W 2 → min,

5 X 1 + 20 X 2 ≤ 400, 5 W 1 + 10 W 2 ≥ 45,

10 X 1 + 15 X 2 ≤ 450, 20 W 1 + 15 W 2 ≥ 80,

X 1 ≥ 0, W 1 ≥ 0,

X 2 ≥ 0. W 2 ≥ 0.

İkili görev neden bu kadar önemli? Orijinal ve ikili problemlerdeki amaç fonksiyonlarının optimal değerlerinin çakıştığı kanıtlanabilir (yani, orijinal problemdeki maksimum, ikilideki minimumla çakışır). Bu durumda W 1 ve W 2'nin optimal değerleri, amaç fonksiyonuna katkılarına göre değerlendirilirse sırasıyla malzeme ve işçilik maliyetini gösterir. Bu üretim faktörlerinin piyasa fiyatlarıyla karıştırılmaması için W 1 ve W 2'ye hammadde ve emeğin "objektif olarak belirlenmiş tahminleri" adı verilir.

Bilimsel ve pratik bir disiplin olarak doğrusal programlama. Tüm optimizasyon problemlerinden doğrusal programlama problemleri, kısıtlamalarının doğrusal eşitsizlikler veya eşitlik sistemleri olması gerçeğiyle ayırt edilir. Kısıtlamalar, sonlu bir doğrusal uzayda dışbükey doğrusal çokyüzlüyü tanımlar. Amaç fonksiyonları da doğrusaldır.

Bu tür problemler ilk olarak Sovyet matematikçi L.V. Kantorovich (1912-1986) 1930'larda üretim organizasyonunu optimize etmek için üretim yönetiminin görevleri olarak görev yaptı ve üretim süreçleriörneğin, makinelerin yüklenmesi ve malzeme levhalarının kesilmesi işlemleri. İkinci Dünya Savaşı'ndan sonra ABD'de de benzer görevler üstlenildi. 1975 yılında T. Koopmans (1910-1985, Hollanda'da doğdu, çoğunlukla ABD'de çalıştı) ve SSCB Bilimler Akademisi Akademisyeni L.V. Kantorovich'e ekonomi alanında Nobel Ödülü verildi.

Birkaç doğrusal programlama problemini ele alalım.

Karışım optimizasyon problemi (basitleştirilmiş versiyon). Optimizasyon için bir kimya tesisinde teknolojik süreç gerekli miktarda belirli maddeyi içeren en ucuz karışımı oluşturmanız gerekir (bunları T ve H olarak gösterelim). Karışımın enerji değeri (kalori cinsinden) belirtilen değerden az olmamalıdır. Basit olması açısından, karışımın iki bileşenden (K ve C) oluşmasına izin verin. Karışıma her birinden ne kadar dahil edilmelidir? Hesaplamalara ilişkin başlangıç ​​verileri Tablo 3'te verilmiştir.

Tablo 3. Karışım optimizasyon problemindeki başlangıç ​​verileri.

3,8 K + 4,2 C → dk,

0,10 K + 0,25 C ≥ 1,00,

1,00 K + 0,25 C ≥ 5,00,

110,00 K + 120,00 C ≥ 400,00,

Grafiksel çözümü Şekil 4'te sunulmaktadır.

Şekil 4. Grafik çözümü Karışım optimizasyon problemleri.

Şekil 4'te algılama kolaylığı açısından dört düz çizgi (1) - (4) rakamlarıyla gösterilmiştir. Düz çizgi (1), 1,00K + 0,25C = 5,00 (H maddesinin sınırı) düz çizgidir. Şekilde görüldüğü gibi apsis eksenindeki (5,0) ve ordinat eksenindeki (0,20) noktalarından geçer. Önceki üretim probleminde daha önce dikkate alınan durumların aksine, parametrelerin (K, C) kabul edilebilir değerlerinin düz çizginin (1) üzerinde yer aldığını lütfen unutmayın.

Düz (2) düz 110,00 K + 120,00 C = 400,00 (kalori limiti). Negatif olmayan C bölgesinde her yerde düz çizginin (1) altında bulunduğunu belirtelim. Gerçekten de K = 0 olduğunda bu doğrudur, düz çizgi (1) (0.20) noktasından geçer ve düz çizgi (2) (0, 400/120) noktasından geçer. Denklem sistemini çözerken iki düz çizginin kesişme noktası bulunur

1,00 K + 0,25 C = 5,00,

110,00K + 120,00C = 400,00.

İlk denklemden K = 5 - 0,25 C. İkinciye şunu yazın: 110 (5 - 0,25 C) + 120 C = 400, buradan 550 - 27,5 C + 120 C = 400. Dolayısıyla 150 = - 92 ,5 C yani çözüm negatif C'de elde edilir. Bu, tüm pozitif C için düz çizginin (2) düz çizginin (1) altında olduğu anlamına gelir. Bu, eğer H kısıtlamaları karşılanırsa, kalori kısıtlamalarının da zorunlu olarak karşılandığı anlamına gelir. Yeni bir olguyla karşı karşıyayız; matematiksel açıdan bazı kısıtlamalar gereksiz hale gelebilir. Ekonomik açıdan bakıldığında bunlar gereklidir ve problem tanımının temel özelliklerini yansıtırlar, ancak bu durumda Sorunun iç yapısının, kalori kısıtlamasının kabul edilebilir bir parametre aralığının oluşumuna ve bir çözüm bulmaya katılmadığı şekilde ortaya çıktı.

Düz çizgi (4), 0,1 K + 0,25 C = 1 düz çizgisidir (T maddesiyle ilgili sınırlama). Şekilde görüldüğü gibi apsis eksenindeki (10,0) ve ordinat eksenindeki (0,4) noktalarından geçer. Lütfen parametrelerin (K, C) izin verilen değerlerinin, düz çizgide (1) olduğu gibi düz çizginin (4) üzerinde bulunduğunu unutmayın.

Sonuç olarak, parametrelerin (K, C) izin verilen değerlerinin aralığı yukarıdan sınırsızdır. Koordinat eksenleri (birinci çeyrekte bulunur) ve düz çizgiler (1) ve (4) (bu düz çizgilerin üzerinde yer alır) ile tüm düzlemden ayrılır. Parametrelerin (K, C) izin verilen değerlerinin bölgesi “sınırsız çokgen” olarak adlandırılabilir. 3,8 K + 4,2 C amaç fonksiyonunun minimumuna yalnızca bu “poligonun” köşelerinde ulaşılabilir. Sadece üç zirve var. Bunlar, (1) ve (4) düz çizgilerinin apsis (10,0) ve ordinat (0,20) eksenleriyle kesişimleridir (her durumda, her iki kısıtlamayı da karşılayan, iki kesişimden alınır). Üçüncü köşe, denklem sistemini çözerken koordinatları bulunan (1) ve (4) çizgilerinin kesişme noktasıdır.

0,10 K + 0,25 C = 1,00,

1,00 K + 0,25 C = 5,00.

İkinci denklemden K = 5 - 0,25 C, ilkinden 0,10 (5 - 0,25 C) + 0,25 C = 0,5 - 0,025 C + 0,25 C = 0,5 + 0,225 C = 1, buradan C = 0,5/0,225 = 20/ 9 ve K = 5 - 5/9 = 40/9. Yani A = (40/9; 20/9).

Şekil 4'teki düz çizgi (3), 3,8 K + 4,2 C hedef fonksiyonuna karşılık gelen düz bir çizgidir. Kısıtlamaları belirleyen düz çizgiler (1) ve (4) arasından geçer ve minimuma A noktasında ulaşılır. , içinden düz bir çizgi (3) geçer. Dolayısıyla minimum 3,8x40/9 + 4,2x20/9 = 236/9 olur. Karışımı optimize etme sorunu tamamen çözüldü.

Yukarıda açıklanan kurallara göre oluşturulan ikili problem aşağıdaki forma sahiptir (ikili problemin oluşturulmasına yönelik teknolojiyi açıkça göstermek için burada orijinal karışım optimizasyon problemini tekrarlıyoruz):

3,8 K + 4,2 C → min, W 1 + 5 W 2 + 400 W 3 → maks,

0,10 K + 0,25 C ≥ 1,00, 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8,

1,00 K + 0,25 C ≥ 5,00, 0,25W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2,

110,00 K + 120,00 C ≥ 400,00, W 1 ≥ 0,

K ≥ 0, W 2 ≥ 0,

C ≥ 0. W3 ≥ 0.

Doğrudan problemdeki minimum değer olması gerektiği gibi eşittir maksimum değer V ikili problem yani her iki sayı da 236/9'dur. İkili değişkenlerin yorumlanması: W1, bir birim T maddesinin "maliyetidir" ve W2, bir birim H maddesinin, amaç fonksiyonuna "katkılarıyla" ölçülen "maliyetidir". Bu durumda W 3 = 0, çünkü kalori sayısındaki sınırlama hiçbir şekilde optimal çözümün oluşumuna katılmaz. Yani W 1, W 2, W 3 sözdedir. kaynakların (T ve H maddeleri, kaloriler) nesnel olarak belirlenmiş değerlendirmeleri (L.V. Kantorovich'e göre).

Ürün yelpazesinin ve üretim hacimlerinin planlanması.Üretim organizasyonuna dönelim. Firma otomatik mutfak (tencere tipi), kahve makinesi ve semaver üretebilmektedir. Tablo 4'te işletmedeki mevcut üretim kapasitesine ilişkin veriler (ürün birimleri cinsinden) gösterilmektedir.

Tablo 4. Üretim kapasitesi (adet olarak)

Bu durumda damgalama ve son işlem aynı ekipman üzerinde gerçekleştirilir. Damgalamanızı sağlar belirli zaman veya 20.000 mutfak veya 30.000 kahve makinesi veya her ikisi de daha az miktarda değil. Ancak montaj ayrı alanlarda gerçekleştirilir.

Doğrusal programlama problemi şu şekildedir:

X 1 ≥ 0, X 2 ≥ 0, X 3 ≥ 0, (0)

X 1/200 + X 2/300 + X 3/120 ≤ 100, (1)

X 1/300 + X 2/100 + X 3/100 ≤ 100, (2)

X 1/200 ≤ 100, (3)

X 2/120 ≤ 100, (4)

X 3/80 ≤ 100, (5)

F = 15 X 1 + 12 X 2 + 14 X 3 → maks.

Burada:
(0) ekonomide değişkenlerin negatif olmamasının olağan koşuludur,
(1) - Damgalama yeteneklerindeki sınırlama (algı kolaylığı açısından yüzde olarak ifade edilir),
(2) - sonlandırma seçeneklerinde sınırlama,
(3) - mutfaklara yönelik montaj kısıtlamaları,
(4) - kahve öğütücüler için de aynısı,
(5) - semaverler için de aynısı (daha önce de belirtildiği gibi, her üç tip ürün de ayrı hatlarda monte edilir).

Son olarak F amaç fonksiyonu işletmenin toplam karıdır.

Eşitsizliğin (3) eşitsizlikten (1) ve eşitsizliğin (4) de (2)'den kaynaklandığını unutmayın. Bu nedenle (3) ve (4) eşitsizlikleri hemen atılabilir.

Hemen ilginç bir gerçeği not edelim. Belirleneceği gibi, optimal planda X 3 = 0, yani. Semaver üretmek karlı değil.

Doğrusal programlama

Doğrusal programlama- doğrusal denklemler ve eşitsizlik sistemleri tarafından tanımlanan boyutlu vektör uzayı kümeleri üzerindeki ekstrem problemleri çözme teorisi ve yöntemlerine adanmış bir matematik disiplini.

Doğrusal programlama, dışbükey programlamanın özel bir durumudur ve bu da matematiksel programlamanın özel bir durumudur. Aynı zamanda tamsayılı ve doğrusal olmayan programlama problemlerinin çözümüne yönelik çeşitli yöntemlerin de temelini oluşturur. Doğrusal programlamanın bir genellemesi kesirli doğrusal programlamadır.

Doğrusal programlama problemlerinin birçok özelliği aynı zamanda çokyüzlülerin özellikleri olarak da yorumlanabilir ve dolayısıyla geometrik olarak formüle edilebilir ve kanıtlanabilir.

Hikaye

İç nokta yönteminden ilk kez 1967 yılında I. I. Dikin bahsetmiştir.

Görevler

Ana (standart) doğrusal programlama problemi doğrusal bir amaç fonksiyonunun minimumunu bulma problemi olarak adlandırılır ( doğrusal şekil) şeklinde:

koşullar altında

Doğrusal programlama probleminin kanonik görünüm , eğer ana problemde ilk eşitsizlik sistemi yerine bir denklem sistemi varsa:

Ek değişkenler eklenerek asıl sorun kanonik hale getirilebilir.

En genel formdaki doğrusal programlama problemleri (karışık kısıtlamalı problemler: eşitlikler ve eşitsizlikler, kısıtlamalardan arınmış değişkenlerin varlığı), değişkenleri değiştirerek ve eşitlikleri bir çift ile değiştirerek eşdeğer problemlere (aynı çözüm kümesine sahip) indirgenebilir. eşitsizlikler.

Maksimumu bulma probleminin, ters işaretli katsayılar alınarak minimumu bulma görevinin yerini alabileceğini görmek kolaydır.

Örnek problemler

Maksimum eşleştirme

İki parçalı bir grafikte maksimum eşleştirme problemini düşünün: birden fazla erkek ve kız var ve her erkek ve kız çocuğunun birbirlerine çekici gelip gelmediği biliniyor. Maksimum sayıda çifti karşılıklı anlayışla evlendirmeliyiz.

-boy ve -girl çiftine karşılık gelen ve kısıtlamaları karşılayan değişkenleri tanıtalım:

amaç fonksiyonu ile. Bu problemin optimal çözümleri arasında bir tam sayının olduğu gösterilebilir. 1'e eşit olan değişkenler evlenmesi gereken çiftlere karşılık gelecektir.

Maksimum akış

Her kenarın kendi değerini gösterdiği (yönlendirilmiş kenarları olan) bir grafik olsun. verim. Ve iki köşe verilmiştir: drenaj ve kaynak. Kaynaktan drenaja toplam akışı en üst düzeye çıkarmak için her kenar için içinden ne kadar sıvı akacağını (kapasitesinden fazla olmamak kaydıyla) belirtmek gerekir (sıvı, drenaj ve kaynak dışındaki tüm köşelerde görünemez veya kaybolamaz).

Kaburgadan akan sıvı miktarını değişken olarak alalım. Daha sonra

o kenarın kapasitesi nerede? Bu eşitsizlikler, drenaj ve kaynak hariç, her köşe için içeri akan ve dışarı akan sıvı miktarının eşitliği ile desteklenmelidir. Fonksiyon olarak kaynaktan çıkan ve içeri giren akışkan miktarı arasındaki farkın alınması doğaldır.

Önceki problemin bir genellemesi, minimum maliyetin maksimum akışıdır. Bu problemde her bir kenar için maliyetler verilmektedir ve maksimum akışlar arasından minimum maliyetli akışı seçmeniz gerekmektedir. Bu problem iki doğrusal programlama problemine indirgenmektedir: ilk önce maksimum akış problemini çözmeniz ve daha sonra bu probleme maksimum akışın değerinin nerede olduğu kısıtını eklemeniz ve problemi şu şekilde çözmeniz gerekir: yeni özellik- akış maliyeti.

Denklemlerin ve eşitsizliklerin özel yapısı nedeniyle bu problemler, doğrusal programlama problemlerinin çözümü için genel algoritmalara göre daha hızlı çözülebilir.

Taşıma görevi

Depolardan fabrikalara aktarılması gereken belli bir homojen kargo var. Her deponun ne kadar kargo içerdiği bilinmektedir ve her fabrikanın kargo talebi de bilinmektedir. Taşıma maliyeti depodan fabrikaya olan mesafe ile orantılıdır (depodan fabrikaya olan tüm mesafeler bilinmektedir). En çok beste yapmak gerekiyor ucuz plan toplu taşıma.

Bu durumda belirleyici değişkenler, depodan tesise taşınan kargo miktarlarıdır. Kısıtlamalara uyuyorlar:

Amaç fonksiyonu, küçültülmesi gereken: biçimine sahiptir.

Sıfır toplamlı oyun

Bir boyut matrisi var. İlk oyuncu 1'den 'e kadar bir sayı seçer, ikincisi ise 1'den 'e kadar bir sayı seçer. Daha sonra sayıları kontrol ederler ve birinci oyuncu puan alır, ikinci oyuncu da puan alır (ilk oyuncunun seçtiği sayı ikinciyi alır). İlk oyuncu için en uygun stratejiyi bulmamız gerekiyor.

Örneğin, optimal bir stratejide ilk oyuncunun olasılıklı bir sayı seçmesi gerektiğini varsayalım. O halde optimal strateji aşağıdaki doğrusal programlama probleminin çözümüdür:

Burada fonksiyonun maksimize edilmesi gerekiyor. Optimal çözümdeki değer, en kötü durumda ilk oyuncunun kazancının matematiksel beklentisi olacaktır.

Çözüm algoritmaları

Genel bir doğrusal programlama (LP) problemini çözmek için pratikte en ünlü ve yaygın olarak kullanılan, simpleks yöntemidir. Simpleks yönteminin oldukça etkili bir algoritma olmasına rağmen iyi sonuçlar karar verirken uygulamalı problemler LP, üstel karmaşıklığa sahip bir algoritmadır. Bunun nedeni, çokyüzlünün köşeleri üzerinde sırayla yinelenen simpleks yönteminin kombinatoryal doğasıdır. kabul edilebilir çözümler Optimum çözümü ararken.

İlk polinom algoritması olan elipsoid yöntemi, 1979 yılında Sovyet matematikçi L. Khachiyan tarafından önerildi ve böylece problem çözüldü. uzun zamandırçözümsüz kaldı. Elipsoid yöntemi, simpleks yönteminden tamamen farklı, kombinatoryal olmayan bir yapıya sahiptir. Ancak, hesaplamalı olarak bu yöntemin ümit verici olmadığı ortaya çıktı. Bununla birlikte, problemlerin polinom karmaşıklığı gerçeği, bütün bir etkili LP algoritmaları sınıfının yaratılmasına yol açtı - iç nokta yöntemleri Bunlardan ilki N. Karmarkar'ın 1984'te önerdiği algoritmaydı. Bu tür algoritmalar, LP probleminin çözümlerinin çokyüzlünün köşelerini sıralamak yerine, uzaydaki yörüngeler boyunca bir arama yürütüldüğünde, LP probleminin sürekli bir yorumunu kullanır. problem değişkenleri, çokyüzlünün köşelerinden geçmiyor. Simpleks yönteminden farklı olarak uygun bölgenin iç kısmındaki noktaları geçen iç nokta yöntemi, 1960'larda Fiacco ve McCormick tarafından geliştirilen log-bariyerli doğrusal olmayan programlama yöntemlerini kullanır.

Ayrıca bakınız

• Doğrusal programlama problemini çözmek için grafiksel yöntem

Notlar

Edebiyat

• Thomas H. Corman ve ark. Bölüm 29. Doğrusal programlama // Algoritmalar: yapım ve analiz = ALGORİTMALARA GİRİŞ. - 2. baskı. - M .: “Williams”, 2006. - S. 1296. - ISBN 5-8459-0857-4
• Akulich I.L. Bölüm 1. Doğrusal programlama problemleri, Bölüm 2. Özel doğrusal programlama problemleri // Örneklerde ve problemlerde matematiksel programlama. - M .: Yüksekokul, 1986. - 319 s. - ISBN 5-06-002663-9
• Karmanov V. G. Matematiksel programlama. - 3. baskı. - M .: Nauka, 1986. - 288 s.
• Danzig George Bernard "Doğrusal Programlamanın Başlangıcına İlişkin Anılar"

Bağlantılar

• - Doğrusal, tam sayı ve hedef programlama problemlerini çözmek için tasarlanmış ücretsiz optimizasyon paketi.
• Vershik A. M. “L. V. Kantorovich ve doğrusal programlama hakkında”
• Bolshakova I.V., Kuralenko M.V. “Doğrusal programlama. Test için eğitimsel ve metodolojik el kitabı."
• Barsov A. S. “Doğrusal programlama nedir”, Matematik üzerine popüler dersler, Gostekhizdat, 1959.
• M. N. Vyalyi Doğrusal eşitsizlikler ve kombinatorik. -MCNMO, 2003.

Wikimedia Vakfı. 2010.

• Salten, Felix
• Glagow, Martina

Diğer sözlüklerde “Doğrusal programlama”nın ne olduğuna bakın:

doğrusal programlama- - doğrusal programlama Aşağıdakilerle karakterize edilen aşırı problemleri çözme teorisine ve yöntemlerine ayrılmış bir matematiksel programlama alanı: doğrusal bağımlılık arasında… … Teknik Çevirmen Kılavuzu

Doğrusal programlama

Doğrusal programlama- değişkenler arasındaki doğrusal bir ilişki ile karakterize edilen aşırı problemleri çözme teorisine ve yöntemlerine ayrılmış bir matematiksel programlama alanı. En genel haliyle L.p. bu şekilde yazılabilir. Verilmiştir… … Ekonomik ve matematiksel sözlük

15. Analitik yöntemler. Doğrusal programlama yöntemleri.

15.1. Analitik Yöntemler

Tüm evrimi boyunca insan, belirli eylemleri gerçekleştirirken, belirli bir eylemin sonucu olarak elde edilen sonucun bir anlamda en iyisi olmasını sağlayacak şekilde davranmaya çalıştı. Bir noktadan diğerine geçerek mümkün olan en kısa yolu bulmaya çalıştı. Bir konut inşa ederken, en az yakıt tüketimiyle kabul edilebilir yaşam koşullarını sağlayacak bir geometri aradı. Gemileri inşa ederken onlara suyun en az direnç göstereceği bir şekil vermeye çalıştı. Benzer örneklerin listesine kolaylıkla devam edilebilir.

Belirli bir anlamda sorunlara en iyi çözümler genellikle denir en uygun. Şu anda optimizasyon ilkeleri kullanılmadan hiçbir problem çözülemez. karmaşık sorun. Optimizasyon problemlerini belirlerken ve çözerken iki soru ortaya çıkıyor: neyi ve nasıl optimize etmeliyim?

İlk sorunun cevabı, çözülmesi gereken problemin derinlemesine incelenmesi sonucunda elde edilir. Ortaya çıkan problemin çözümünün mükemmellik derecesini belirleyen parametre belirlenir. Bu parametreye genellikle denir hedef işlevi veya kalite kriteri. Daha sonra amaç fonksiyonunu belirleyen bir dizi büyüklük oluşturulur. Son olarak, problemi çözerken dikkate alınması gereken tüm kısıtlamalar formüle edilir. Bundan sonra, amaç fonksiyonunun tüm argümanlara analitik bağımlılığının ve problemle ilgili kısıtlamaların analitik formülasyonunun kurulmasından oluşan bir matematiksel model oluşturulur. Daha sonra ikinci sorunun cevabını aramaya başlıyoruz.

Böylece, uygulanan problemin formalizasyonu sonucunda amaç fonksiyonunun olduğu tespit edilsin, burada X kümesi kısıtlamaların bir genellemesidir, buna uygun çözümler kümesi denir. Optimizasyon probleminin özü, böyle bir çözümü X kümesinde (uygun çözümler kümesi) aramaktır.
, burada hedef fonksiyon F minimum veya maksimum değerine ulaşır.

Optimizasyon yöntemlerinin ayrılmaz bir parçası doğrusal programlamadır.

15.2. Doğrusal programlamanın temel kavramları

Etkin üretim yönetiminde matematiksel yöntemlerden ilk söz (1938) Sovyet matematikçi L. V. Kantorovich'e aittir. Bir yıl sonra, 1939'da L. V. Kantorovich, “Üretimi organize etmenin ve planlamanın matematiksel yöntemleri” çalışmasını yayınladı ve elde edilen sonuçları pratik olarak uyguladı. “Doğrusal programlama” terimi, 40'lı yılların sonlarında Amerikalı matematikçiler J. Danzig ve T. Koopmans tarafından tanıtıldı. J. Dantzig, doğrusal programlama problemlerini çözmek için simpleks yönteminin matematiksel aygıtını geliştirdi (1951). Simpleks yöntemi çok çeşitli doğrusal programlama problemlerini çözmek için kullanılır ve hala ana yöntemlerden biridir.

Doğrusal programlama, tanımlanan problemlerde bir ekstremum (maksimum veya minimum) bulmaya odaklanan bir matematik dalıdır. doğrusal denklemler. Dahası, doğrusal denklemler hem amaç fonksiyonunun kendisini hem de girdi parametrelerini (değişkenleri) ve girdi parametreleri üzerindeki kısıtlama koşullarını tanımlar. Doğrusal programlama problemleri için gerekli bir koşul, kaynaklar (hammaddeler, malzemeler, finans, üretilen ürünlere talep vb.) üzerinde zorunlu kısıtlamaların bulunmasıdır. Sorunu çözmenin bir diğer önemli koşulu, algoritmayı durdurma kriterinin seçimidir, yani amaç fonksiyonu bir anlamda optimal olmalıdır. Amaç fonksiyonunun optimalliği niceliksel olarak ifade edilmelidir. Hedef fonksiyon bir veya iki denklemle temsil edilirse pratikte bu tür problemler oldukça kolay çözülebilir. Algoritma durdurma kriteri (veya optimallik kriteri) aşağıdaki gereksinimleri karşılamalıdır:

belirli bir görev için tek kişi olmak;

miktar birimleriyle ölçülür;

giriş parametrelerine doğrusal olarak bağlıdır.

Yukarıdakilere dayanarak doğrusal programlama problemini genel biçimde formüle edebiliriz:

amaç fonksiyonunun ekstremumunu bulun

eşitlik biçimindeki kısıtlamalar altında:

(2.2)

eşitsizlikler biçimindeki kısıtlamalar altında:

(2.3)

ve giriş parametrelerinin negatif olmama koşulları:

Doğrusal programlama problemi kısaca şu şekilde yazılabilir:

(2.5)

verilen

Nerede
- giriş değişkenleri;

Sayılar pozitif, negatif ve sıfıra eşittir.

Matris formunda bu problem şu şekilde yazılabilir:

Doğrusal programlama problemleri analitik ve grafiksel olarak çözülebilir.

15.3. Kanonik doğrusal programlama problemi

, i=1,…,m,

, j=1,…,n.

Doğrusal programlama problemlerini çözmek için kullanılan ana hesaplama yöntemleri, özellikle kanonik problem için geliştirilmiştir.

15.4. Genel doğrusal programlama problemi

Doğrusal bir fonksiyonu en üst düzeye çıkarmak (en aza indirmek) gereklidir. N değişkenler.

kısıtlamalar altında

, Ben=1,…, k,

, Ben=1+ k,…, M,

, …,

Burada k≤ M, R≤ N. Standart problem genel problemin özel bir durumu olarak elde edilir. k= M, R= N; kanonik – en k=0, R= N.

Örnek.

Şekerleme fabrikasında çeşitli tatlılar üretilmektedir. Onlara "A", "B" ve "C" diyelim. On kilogram "A" tatlısının satışının 90 ruble, "B" - 100 ruble ve "C" - 160 ruble kar sağladığı biliniyor. Şeker istenilen miktarda üretilebilir (satış garantilidir), ancak hammadde tedariki sınırlıdır. Satışlardan elde edilen toplam kârın maksimum olması için ne tür tatlıların kaç on kilogram üretilmesi gerektiğinin belirlenmesi gerekir. Her türden 10 kg şekerleme üretimi için hammadde tüketim oranları Tablo 1'de verilmiştir.

Tablo 1. Hammadde tüketim oranları

prodüksiyon için

Sorunun ekonomik ve matematiksel formülasyonu şu şekildedir:

Bu tür değişken değerleri bulun X=(x1, x2, x3), ile

amaç fonksiyonu

koşullar-kısıtlamalar altında: