Doğrusal Programlama

Doğrusal Programlama Nedir?

Doğrusal Optimizasyon Problemlerini Çözün

Doğrusal programlama (Linear Programming, LP), sınırlara, doğrusal eşitliğe ve eşitsizlik kısıtlamalarına tabi doğrusal bir amaç işlevini en aza indirgemek veya en üst düzeye çıkarmaktır. Örnek problemler, proses endüstrilerinde harmanlamayı, imalatta üretim planlamayı, finansta nakit akışı eşleştirmeyi veya enerji ve ulaşımda planlamayı içerir.

Doğrusal programlama, işlevi en aza indiren bir x vektörü bulmanın matematiksel problemidir:

min x {f T  x}

Kısıtlamalara tabi olarak:

Ax ≤ b (inequality constraint)

Aeqx = beq (equality constraint)

lb ≤ x ≤ ub (bound constraint)

Doğrusal optimizasyon problemlerini çözmek için yaygın olarak kullanılan aşağıdaki algoritmaları uygulamak için MATLAB® kullanabilirsiniz:

• İç nokta (Interior point): İlkel, ikili tahmin edici, düzeltici algoritma kullanır ve özellikle yapısı olan veya seyrek matrisler kullanılarak tanımlanabilen büyük ölçekli doğrusal programlar için kullanışlıdır.
• Simplex: Doğrusal bir programa aday tepe noktası çözümleri oluşturmak ve test etmek için sistematik bir prosedür kullanır. Simplex algoritması ve ilgili dual-simpleks algoritması, doğrusal programlama için en yaygın kullanılan algoritmalardır.

Kısıtlamaların bir ağ yapısına sahip olduğu bazı özel doğrusal program durumları için algoritmalar, tipik olarak genel amaçlı iç nokta ve tek yönlü algoritmalardan daha hızlıdır.

Optimization Toolbox™ içindeki linprog çözücüsü bu doğrusal optimizasyon tekniklerini uygular.

Özel durumlar şunları içerir:

• Maksimum ağ akışı: Genişletme yolu ve yeniden etiketleme algoritmalarını kullanır.
• En kısa yol: Dijkstra, Bellman-Ford ve arama algoritmalarını kullanır.
• Doğrusal atama: İki parçalı bir eşleştirme algoritması kullanır.

Algoritmalar ve doğrusal programlama hakkında daha fazla bilgi için bkz. Optimization Toolbox™.

Örnekler ve Nasıl Yapılır

• Getting Started with Linear Programming in MATLAB – Örnek
• From Problem Description to Mathematical Program | Mathematical Modeling with Optimization, Part 1 (8:51) – Video
• Mathematical Modeling with Optimization, Part 2a: Problem-Based Linear Programming (6:04) – Video
• Maximize Long-Term Investments Using Linear Programming – Örnek
• Production Planning – Örnek
• Graph and Digraph Classes (5:44) – Video
• Constrained Optimization: Intuition behind the Lagrangian (10:48) – Video

Kullanım Örnekleri

• Canada’s Institute for Biodiagnostics Develops Imaging Tool – Kullanıcı Hikayesi
• Gas Natural Fenosa (now Naturgy Energy Group S.A.) Predicts Energy Supply and Demand – Kullanıcı Hikayesi
• Operations, Logistics, and Supply Chain Management – MathWorks Danışmanlık
• Reduce Waste and Increase Efficiency with Process Optimization (46:55) – Webinar
• Optimizing Scheduling and Blending Operations in the Process Industries (32:00) – Webinar

Yazılım Referansı

• Problem-Based Optimization – Dokümantasyon
• linprog: Linear programming – Fonksiyon
• Graph and Network Algorithms – Dokümantasyon
• Investigate Linear Infeasibilities – Örnek

Ayrıca bkz: Optimization Toolbox, Global Optimization Toolbox, integer programming, quadratic programming, nonlinear programming, multiobjective optimization, prescriptive analytics, convex optimization, microgrid, smart grid, and charging infrastructure, power system simulation and optimization