Optimizasyon, kâr getiren, maliyetleri az altan veya iş süreci hatalarına neden olan bir parametre belirleyen en iyi sonucu bulmanıza yardımcı olur.
Bu işleme matematiksel programlama da denir. Optimizasyon probleminin başkanı tarafından belirlenen hedefe ulaşmak için gerekli olan sınırlı kaynakların dağılımını belirleme problemini çözer. Tüm olası seçeneklerden, örneğin kar veya maliyet gibi kontrol parametresini maksimize eden (veya az altan) olanı bulmak arzu edilir. Optimizasyon modelleri, işletme için uygulanabilir bir strateji bulmaya çalıştıkları için kuralcı veya normatif olarak da adlandırılır.
Geliştirme geçmişi
Doğrusal programlama (LP), tüm kısıtlamaların doğrusal olduğu bir sınıf optimizasyon problemi ile çalışır.
LP'nin gelişiminin kısa bir tarihini sunmak:
- 1762'de Lagrange eşitlik kısıtlamalarıyla basit optimizasyon problemlerini çözdü.
- 1820'de Gauss karar verdieleme kullanan lineer denklem sistemi.
- 1866'da Wilhelm Jordan, bir uyum kriteri olarak en küçük kareler hatalarını bulma yöntemini mükemmelleştirdi. Bu artık Gauss-Jordan yöntemi olarak adlandırılıyor.
- Dijital bilgisayar 1945'te ortaya çıktı.
- Danzig, 1947'de simpleks yöntemleri icat etti.
- 1968'de Fiacco ve McCormick, Inside Point yöntemini tanıttı.
- 1984'te Karmarkar, lineer programları çözmek için iç yöntemi uygulayarak yenilikçi analizini ekledi.
LP, hem gerçek dünya problemlerini modellemek için hem de yaygın olarak uygulanan bir matematik teorisi olarak son derece güçlü bir araç olduğunu kanıtlamıştır. Ancak, birçok ilginç optimizasyon problemi doğrusal değildir.
Bu durumda ne yapmalı? Bu tür problemlerin incelenmesi, lineer cebir, çok değişkenli analiz, sayısal analiz ve hesaplama yöntemlerinin çeşitli bir karışımını içerir. Bilim adamları, doğrusal programlama için iç nokta yöntemleri, geometri, dışbükey kümelerin ve fonksiyonların analizi ve ikinci dereceden programlama gibi özel olarak yapılandırılmış problemlerin incelenmesi dahil olmak üzere hesaplama algoritmaları geliştiriyorlar.
Doğrusal olmayan optimizasyon, matematiksel analizin temel bir anlayışını sağlar ve mühendislik, regresyon analizi, kaynak yönetimi, jeofizik keşif ve ekonomi gibi çeşitli alanlarda yaygın olarak kullanılır.
Optimizasyon problemlerinin sınıflandırılması
Önemli bir adımOptimizasyon süreci, çözüm algoritmaları belirli bir türe uyarlandığından modellerin sınıflandırılmasıdır.
1. Kesikli ve sürekli optimizasyon ile ilgili problemler. Bazı modeller, yalnızca değişkenler ayrı bir tamsayı alt kümesinden değerler alırsa anlamlıdır. Diğerleri, herhangi bir gerçek değer alabilen veriler içerir. Çözülmeleri genellikle daha kolaydır. Algoritmalardaki gelişmeler, bilgisayar teknolojisindeki gelişmelerle birleştiğinde, doğrusal programlama optimizasyon probleminin boyutunu ve karmaşıklığını önemli ölçüde artırdı.
2. Sınırsız ve sınırlı optimizasyon. Bir diğer önemli fark, değişkenler üzerinde herhangi bir kısıtlamanın olmadığı görevlerdir. Basit tahmincilerden, veriler arasındaki karmaşık ilişkileri modelleyen eşitlik ve eşitsizlik sistemlerine kadar geniş bir aralıkta olabilir. Bu tür optimizasyon problemleri, fonksiyonların doğasına göre daha fazla sınıflandırılabilir (doğrusal ve doğrusal olmayan, dışbükey ve pürüzsüz, türevlenebilir ve türevlenemez).
3. Fizibilite görevleri. Amaçları, herhangi bir belirli optimizasyon hedefi olmaksızın model kısıtlamalarını karşılayan değişken değerleri bulmaktır.
4. Tamamlayıcılık görevleri. Teknoloji ve ekonomide yaygın olarak kullanılırlar. Amaç, tamamlayıcılık koşullarını sağlayan bir çözüm bulmaktır. Uygulamada, birkaç hedefi olan görevler genellikle tek bir amaç için yeniden formüle edilir.
5. Deterministik ve stokastik optimizasyon. Deterministik optimizasyon, verilerinatamalar tamamen doğrudur. Ancak, birçok güncel konuda, çeşitli nedenlerle bilinemezler.
Birincisi basit bir ölçüm hatasıyla ilgili. İkinci neden daha temeldir. Bazı verilerin, örneğin bir ürüne olan talep veya gelecekteki bir zaman dilimi için fiyat gibi gelecekle ilgili bilgileri temsil etmesi gerçeğinde yatmaktadır. Stokastik optimizasyon koşulları altında optimizasyon yaparken, modele belirsizlik dahil edilir.
Ana Bileşenler
Amaç işlevi, minimize veya maksimize edilecek olandır. Çoğu optimizasyon problemi türünün tek bir amaç fonksiyonu vardır. Değilse, genellikle çalışacak şekilde yeniden formüle edilebilirler.
Bu kuralın iki istisnası:
1. Hedef arama görevi. Çoğu iş uygulamasında yönetici, model kısıtlamalarını yerine getirirken belirli bir hedefe ulaşmak ister. Kullanıcı özellikle bir şeyi optimize etmek istemez, bu nedenle bir amaç fonksiyonu tanımlamanın bir anlamı yoktur. Bu türe genellikle tatmin edicilik sorunu denir.
2. Çok sayıda nesnel özellik. Çoğu zaman, bir kullanıcı aynı anda birkaç farklı hedefi optimize etmek ister. Genellikle uyumsuzdurlar. Bir hedef için optimize edilen değişkenler, diğerleri için en iyisi olmayabilir.
Bileşen türleri:
- Kontrollü bir girdi, bir amaç fonksiyonunun değerini etkileyen bir dizi karar değişkenidir. Bir üretim görevinde değişkenler, çeşitli mevcut kaynakların dağılımını veya bunun için gereken emeği içerebilir.her eylem.
- Kısıtlamalar, karar değişkenleri ve parametreler arasındaki ilişkilerdir. Bir üretim sorunu için, herhangi bir faaliyete çok fazla zaman harcamak mantıklı değildir, bu nedenle tüm "geçici" değişkenleri sınırlayın.
- Olası ve optimal çözümler. Tüm kısıtlamaların karşılandığı değişkenler için kararın değerine tatmin edilebilir denir. Çoğu algoritma önce onu bulur, sonra iyileştirmeye çalışır. Son olarak, bir uygun çözümden diğerine geçmek için değişkenleri değiştirirler. Bu işlem, amaç fonksiyonu maksimum veya minimuma ulaşana kadar tekrarlanır. Bu sonuca optimal çözüm denir.
Aşağıdaki matematik programları için geliştirilen optimizasyon problemlerinin algoritmaları yaygın olarak kullanılmaktadır:
- Dışbükey.
- Ayrılabilir.
- Kuadratik.
- Geometrik.
Google Doğrusal Çözücüler
Doğrusal optimizasyon veya programlama, bir problemi optimal olarak çözmenin hesaplama sürecine verilen addır. Birçok bilim ve mühendislik disiplininde ortaya çıkan bir dizi doğrusal ilişki olarak modellenmiştir.
Google, doğrusal optimizasyon sorunlarını çözmek için üç yol sunar:
- Glop açık kaynak kitaplığı.
- Google E-Tablolar için Doğrusal Optimizasyon eklentisi.
- Google Apps Komut Dosyasında Doğrusal Optimizasyon Hizmeti.
Glop, Google'da yerleşik olarak bulunurlineer çözücü. Açık kaynak olarak mevcuttur. Glop için bir sarmalayıcı olan OR-Tools doğrusal çözücü sarmalayıcı aracılığıyla Glop'a erişebilirsiniz.
Google E-Tablolar için doğrusal optimizasyon modülü, verileri bir e-tabloya girerek optimizasyon sorununun doğrusal bir ifadesini gerçekleştirmenize olanak tanır.
Kuadratik programlama
Premium Çözücü platformu, 2000 karar değişkenine kadar LP ve QP problem işleme limitleriyle Simplex yönteminin genişletilmiş bir LP/Quadratic versiyonunu kullanır.
SQP Büyük ölçekli problemler için çözücü, ikinci dereceden programlama (QP) problemlerini çözmek için seyreklik ile aktif küme yönteminin modern bir uygulamasını kullanır. XPRESS Çözücü motoru, QP sorunlarını çözmek için "İç Nokta" veya Newton Bariyer yönteminin doğal bir uzantısını kullanır.
MOSEK Çözücü, gömülü "Inside Point" ve otomatik ikili yöntemleri uygular. Bu, özellikle gevşek bağlı QP sorunları için etkilidir. Ayrıca Ölçek İkinci Dereceden Kısıtlama (QCP) ve İkinci Dereceden Koni Programlama (SOCP) sorunlarını da çözebilir.
Çok işlemli hesaplamalar
Microsoft Office özelliklerinin kullanımıyla oldukça başarılı bir şekilde kullanılırlar, örneğin Excel'de optimizasyon sorunlarını çözme.
Yukarıdaki tabloda semboller şunlardır:
- K1 - K6 - mal sağlaması gereken müşteriler.
- S1 - S6, bunun için inşa edilebilecek potansiyel üretim alanlarıdır. oluşturulabilir1, 2, 3, 4, 5 veya 6 konumun tümü.
Sütun I'de (Düzeltme) listelenen her tesis için sabit maliyetler vardır.
Konum hiçbir şeyi değiştirmezse, sayılmaz. O zaman sabit maliyet olmayacak.
En düşük maliyeti elde etmek için potansiyel konumları belirleyin.
Bu koşullarda konum belirlenir veya kurulmaz. Bu iki durum şunlardır: "DOĞRU - YANLIŞ" veya "1 - 0". Altı konum için altı durum vardır, örneğin, 000001 yalnızca altıncıya, 111111 tümüne ayarlanmıştır.
İkili sayı sisteminde 000001 (1) ile 111111 (63) arasında tam olarak 63 farklı seçenek vardır.
L2-L64 şimdi {=ÇOKLU İŞLEM (K1)} olarak okunmalıdır, bunlar tüm alternatif çözümlerin sonuçlarıdır. O zaman minimum değer=Min (L) ve karşılık gelen alternatif INDEX (K)'dir.
CPLEX Tamsayılı Programlama
Bazen doğrusal bir ilişki, bir iş sorununun özüne inmek için yeterli değildir. Bu, özellikle belirli bir yerde bir depo açıp açmama gibi kararlar ayrı seçimler içerdiğinde geçerlidir. Bu durumlarda tamsayılı programlama kullanılmalıdır.
Sorun hem ayrık hem de sürekli seçimleri içeriyorsa, bu karma tamsayılı bir programdır. Doğrusal, dışbükey ikinci dereceden problemlere ve aynı ikinci dereceden kısıtlamalara sahip olabilir.
Tamsayılı programlar, doğrusal programlardan çok daha karmaşıktır, ancak önemli iş uygulamalarına sahiptirler. YazılımCPLEX yazılımı, tamsayı problemlerini çözmek için karmaşık matematiksel yöntemler kullanır. Yöntemleri, optimal çözümün değerindeki sınırları hesaplamak için doğrusal veya ikinci dereceden yazılım gevşemelerini kullanarak ayrık değişkenlerin olası kombinasyonlarını sistematik olarak aramayı içerir.
Ayrıca, kısıtlamaları hesaplamak için LP ve diğer optimizasyon problem çözme yöntemlerini kullanırlar.
Standart Microsoft Excel Çözücü
Bu teknoloji, LP sorunlarını çözmek için ana Simplex yönteminin temel uygulamasını kullanır. 200 değişkenle sınırlıdır. "Premium Çözücü", değişkenler için çift taraflı sınırları olan gelişmiş bir birincil tek yönlü yöntemi kullanır. Premium Çözücü platformu, 2000'e kadar karar değişkenli bir optimizasyon problemini çözmek için LP/Kuadratik Tek Yönlü Çözücü'nün genişletilmiş bir sürümünü kullanır.
Premium Çözücü platformu için büyük ölçekli LP, zamandan ve bellekten tasarruf etmek için LP modelinde seyrekliği, güncelleme ve yeniden düzenleme matrisleri, çoklu ve kısmi fiyatlandırma ve rotasyonlar ve dejenerasyonun üstesinden gelmek için. Bu motor üç versiyonda mevcuttur (8.000, 32.000'e kadar veya sınırsız değişken ve limiti işleme kapasitesine sahiptir).
MOSEK Çözücü, aynı zamanda seyreklikten yararlanan ve matris güncelleme ve "yeniden düzenleme" için gelişmiş stratejiler kullanan bir yöntem olan birincil ve ikili tek yönlü içerir. Sınırsız büyüklükteki sorunları çözer,milyonlarca karar değişkeni ile doğrusal programlama problemleri üzerinde test edilmiştir.
EXCEL'de adım adım örnek
Excel'de optimizasyon problemi modelini tanımlamak için aşağıdaki adımları uygulayın:
- Sorun için verileri mantıksal bir biçimde bir elektronik tabloda düzenleyin.
- Her değişkeni saklamak için bir hücre seçin.
- Optimizasyon probleminin hedef matematiksel modelini hesaplamak için hücrede bir formül oluşturun.
- Her kısıtlamanın sol tarafını hesaplamak için formüller oluşturun.
- Çözücü'ye karar değişkenleri, hedefler, kısıtlamalar ve bu parametreler üzerinde istenen sınırlar hakkında bilgi vermek için Excel'deki iletişim kutularını kullanın.
- En uygun çözümü bulmak için "Çözücü"yü çalıştırın.
- Bir Excel sayfası oluşturun.
- Hedef fonksiyonu ve kısıtlama formülünün hesaplandığı Excel'de problem için verileri düzenleyin.
Yukarıdaki tabloda, B4, C4, D4 ve E4 hücreleri, X 1, X 2, X 3 ve X 4 karar değişkenlerini temsil etmek üzere ayrılmıştır. Karar örnekleri:
- Ürün karması modeli (ürün başına 450$, $1150, 800$ ve 400$ kar) sırasıyla B5, C5, D5 ve E5 hücrelerine girildi. Bu, hedefin F5=B5B4 + C5C4 + D5D4 + E5E4 veya F5:=SUMPRODUCT (B5: E5, B4: E4) şeklinde hesaplanmasını sağlar.
- B8'e her bir ürün tipini üretmek için gereken kaynak miktarını girin.
- F8 formülü:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Bunu kopyalaF9'daki formül. $B$4:$E$4 içindeki dolar işaretleri, bu hücre aralığının sabit kaldığını gösterir.
- G8'de, sağdaki kısıtlamaların değerlerine karşılık gelen her türden kullanılabilir kaynak miktarını girin. Bu, onları şu şekilde ifade etmenizi sağlar: F11<=G8: G11.
- Bu, dört sınıra eşittir F8<=G8, F9 <=G9, F10 <=G10 ve F11=0
Yöntemin pratik uygulama alanları
Doğrusal optimizasyon, optimizasyon problemine örnek olarak birçok pratik uygulamaya sahiptir:
Bir şirket, bilinen bir katkı payı ile birkaç ürün yapabilir. Her öğenin bir biriminin üretimi, bilinen miktarda sınırlı kaynak gerektirir. Görev, kaynak kısıtlamalarını ihlal etmeden şirketin kârını en üst düzeye çıkarmak için her bir üründen ne kadar üretilmesi gerektiğini belirlemek için bir üretim programı oluşturmaktır.
Karıştırma problemleri, bileşenlerin nihai üründe birleştirilmesiyle ilgili optimizasyon problemlerinin çözümüdür. Bunun bir örneği, 1947'de George Danzig tarafından incelenen beslenme sorunudur. Yulaf, domuz ve ayçiçek yağı gibi bir takım hammaddelerin yanı sıra protein, yağ, A vitamini gibi besin içerikleri ve kilogram başına fiyatları verilmektedir. Buradaki zorluk, besin değerleri için minimum ve maksimum limitlere uyarken, ham maddelerden bir veya daha fazla nihai ürünü mümkün olan en düşük maliyetle harmanlamaktır.
Doğrusal optimizasyon probleminin klasik bir uygulaması, ihtiyaçlar için yönlendirmeyi belirlemektir.telekomünikasyon veya ulaşım ağlarındaki trafik. Aynı zamanda, akışlar, bant genişliği koşullarını ihlal etmeden tüm trafik gereksinimlerinin karşılanacağı şekilde ağ üzerinden yönlendirilmelidir.
Matematiksel teoride, iki kişi için sıfır toplamlı oyunlarda optimal stratejileri hesaplamak için doğrusal optimizasyon kullanılabilir. Bu durumda, her katılımcının stratejilerinin rastgele karıştırma katsayısı olan olasılık dağılımı hesaplanır.
Dünyada hiçbir başarılı iş süreci optimizasyon olmadan mümkün değildir. Birçok optimizasyon algoritması mevcuttur. Bazı yöntemler sadece belirli problem türleri için uygundur. Özelliklerini tanıyabilmek ve uygun çözüm yöntemini seçebilmek önemlidir.
