Doğrusal Programlamaya Giriş

Doğrusal programlama nedir?

Doğrusal programlama, ilgilenilen problemi bir matematiksel modelle tanımlar. Adın iki parçası ayrı ayrı anlam taşır:

Yani doğrusal programlama, etkinlikleri en iyi sonucu verecek şekilde planlamaktır: matematiksel modele göre, bütün olurlu seçenekler arasında belirlenen hedefe en iyi ulaşan sonucu.

20. yüzyıl ortasının en önemli bilimsel ilerlemelerinden biri sayılır. Tipik kullanımı, sınırlı kaynakları birbiriyle yarışan etkinliklere dağıtmaktır. Uygulama örnekleri:

• üretim tesislerinin ürünlere tahsisi,
• portföy seçimi,
• sevkiyat düzenlerinin seçimi,
• radyoterapi planlaması,
• ağ akışı optimizasyonu (rotalama problemleri).

Prototip örnek: Wyndor Glass Co.

Wyndor Glass Co. pencere ve cam kapı gibi cam ürünleri üretir. Üç fabrikası vardır:

• Fabrika 1: alüminyum çerçeveler ve donanım,
• Fabrika 2: ahşap çerçeveler,
• Fabrika 3: cam üretimi ve montaj.

Kazançlar düştüğü için üst yönetim ürün yelpazesini yenilemeye karar verir. Kârsız ürünler bırakılır ve açılan kapasiteyle, satış potansiyeli yüksek iki yeni ürün üretilecektir:

• Ürün 1: alüminyum çerçeveli, 8 fit yüksekliğinde cam kapı. Fabrika 1 ve 3'te kapasite kullanır, Fabrika 2'de kullanmaz.
• Ürün 2: ahşap çerçeveli, 4 × 6 fit sürme pencere. Yalnızca Fabrika 2 ve 3'ü kullanır.

Pazarlama bölümüne göre şirket iki üründen de üretebildiği kadarını satabilir. Ama iki ürün Fabrika 3'teki aynı kapasite için yarıştığından, hangi üretim karışımının en kârlı olduğu açık değildir.

Yöneylem araştırması ekibi şu verilerin toplanması gerektiğini belirler: (1) her fabrikada yeni ürünler için haftada ayrılabilecek üretim saati; (2) her ürünün bir partisinin her fabrikada kullandığı üretim saati; (3) her ürünün parti başına kârı.

LP olarak formülasyon

\(x_1\)

haftada üretilen ürün 1 partisi sayısı

\(x_2\)

haftada üretilen ürün 2 partisi sayısı

\(Z\)

bu iki ürünün üretiminden elde edilen haftalık toplam kâr (bin dolar)

\(x_1\) ve \(x_2\) modelin karar değişkenleridir. Amaç, \(Z = 3x_1 + 5x_2\)'yi, \(x_1\) ve \(x_2\)'nin değerlerine üç fabrikanın kapasitelerinin getirdiği kısıtlar altında en büyüklemektir. Her fabrika bir kısıt verir:

• Fabrika 1: ürün 1'in partisi 1 saat, kapasite 4 saat → \(x_1 \le 4\)
• Fabrika 2: ürün 2'nin partisi 2 saat, kapasite 12 saat → \(2x_2 \le 12\)
• Fabrika 3: partiler 3 ve 2 saat, kapasite 18 saat → \(3x_1 + 2x_2 \le 18\)

Grafik çözüm

İki karar değişkenli bir LP düzlemde çözülebilir:

• 2 karar değişkeni → 2 boyutlu uzay,
• her kısıt → bir doğru (ve onun bir tarafındaki yarı düzlem),
• olurlu bölge → doğruların çevrelediği alan,
• amaç fonksiyonu → bir doğru (eş-kâr doğrusu),
• optimal çözüm → \(Z\)'yi en büyükleyen nokta.

1. Negatif olmama kısıtları aramayı ilk çeyreğe sınırlar.
2. Her kısıtın sınır doğrusunu çiz (\(x_1 = 4\), \(2x_2 = 12\), \(3x_1 + 2x_2 = 18\)) ve kısıtın izin verdiği tarafı işaretle. Bütün kısıtları sağlayan noktalar olurlu bölgeyi oluşturur.
3. \(Z = 3x_1 + 5x_2\)'yi sabit bir değere eşitleyip doğruyu çiz; örneğin \(Z = 10\) ve \(Z = 20\). Bu doğrular birbirine paraleldir.
4. Doğruyu, olurlu bölgeyle en az bir ortak noktası kalacak şekilde \(Z\)'nin arttığı yönde olabildiğince kaydır. Son temas noktası optimumdur: \(Z = 36\) doğrusu bölgeye yalnızca \((2, 6)\)'da dokunur.

Laboratuvarda amaç katsayılarını \(c_1, c_2\) değiştirerek optimumun hangi köşeye kaydığını görebilirsin. Kesikli turuncu çizgi optimumdan geçen eş-kâr doğrusudur. \(c_1 : c_2 = 3 : 2\) olduğunda doğru, \(3x_1 + 2x_2 = 18\) kenarına paralel olur ve çoklu optimum ortaya çıkar; diğer düğmeler özel durumları gösterir.

Genel doğrusal programlama modeli

Kaynakları etkinliklere dağıtma probleminde yaygın kullanılan simgeler:

\(Z\)

genel başarım ölçüsünün değeri.

\(x_j\)

etkinlik \(j\)'nin düzeyi (\(j = 1, 2, \dots, n\)).

\(c_j\)

etkinlik \(j\)'nin düzeyindeki her birim artışın \(Z\)'de yarattığı artış.

\(b_i\)

kaynak \(i\)'nin etkinliklere dağıtılabilecek miktarı (\(i = 1, 2, \dots, m\)).

\(a_{ij}\)

etkinlik \(j\)'nin her biriminin tükettiği kaynak \(i\) miktarı.

Model, problemi etkinliklerin düzeylerine dair kararlar olarak kurar; bu yüzden \(x_1, \dots, x_n\) karar değişkenleridir. \(c_j\), \(b_i\) ve \(a_{ij}\) değerleri modelin girdi sabitleri, yani parametreleridir.

Standart form

Matris gösterimiyle aynı model kısaca \(\max \{\, c^T x : Ax \le b,\ x \ge 0 \,\}\) olarak yazılır.

Amaç fonksiyonu

En büyüklenen fonksiyon, \(c_1x_1 + c_2x_2 + \dots + c_nx_n\).

Fonksiyonel kısıtlar (functional / structural constraints)

Sol tarafında bütün değişkenlerin bir fonksiyonu, \(a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n\), bulunan ilk \(m\) kısıt.

Negatif olmama kısıtları (nonnegativity constraints)

\(x_j \ge 0\) kısıtları.

Diğer biçimler

Aşağıdaki değişiklikler de LP olarak kalır:

1. Amaç fonksiyonunu en büyüklemek yerine en küçüklemek: \(\min Z = c_1x_1 + \dots + c_nx_n\).
2. Bazı fonksiyonel kısıtların \(\ge\) biçiminde olması: bazı \(i\) için \(a_{i1}x_1 + \dots + a_{in}x_n \ge b_i\).
3. Bazı fonksiyonel kısıtların eşitlik olması: bazı \(i\) için \(a_{i1}x_1 + \dots + a_{in}x_n = b_i\).
4. Bazı karar değişkenlerinde negatif olmama kısıtının kaldırılması: bazı \(j\) için \(x_j\) işaretçe serbest.

Hepsi standart forma çevrilebilir: \(\min Z\) yerine \(\max (-Z)\); \(\ge\) kısıtı \(-1\) ile çarpılarak \(\le\) olur; bir eşitlik iki eşitsizliğe (\(\le\) ve \(\ge\)) ayrılır; işaretçe serbest bir değişken iki negatif olmayan değişkenin farkı olarak yazılır: \(x_j = x_j^+ - x_j^-\).

Dönüşüm kuralları slaytta yok; simpleks yöntemi (Hafta 4) modeli standart biçimde beklediği için eklendi.

LP varsayımları

Orantılılık (proportionality)

Her etkinliğin amaç fonksiyonu \(Z\)'ye katkısı, etkinliğin düzeyi \(x_j\) ile orantılıdır (\(c_j x_j\) terimi). Benzer şekilde her etkinliğin her fonksiyonel kısıtın sol tarafına katkısı da \(x_j\) ile orantılıdır (\(a_{ij} x_j\) terimi). Bu varsayım 1'den farklı üsleri dışlar; örneğin ilk partide ödenen sabit bir kurulum maliyeti orantılılığı bozar.

Toplanabilirlik (additivity)

Orantılılık 1'den farklı üsleri dışlar, ama iki ya da daha fazla değişkenin çarpımını içeren çapraz çarpım terimlerini (\(x_1 x_2\) gibi) dışlamaz. Toplanabilirlik bunu da dışlar: LP modelindeki her fonksiyon (amaç fonksiyonu ya da bir fonksiyonel kısıtın sol tarafı) ilgili etkinliklerin bireysel katkılarının toplamıdır.

Kesinlik (certainty)

Modelin parametrelerine, yani amaç katsayıları \(c_j\)'ye, fonksiyonel kısıt katsayıları \(a_{ij}\)'ye ve sağ taraf değerleri \(b_i\)'ye atanan her değerin bilinen bir sabit olduğu varsayılır.

Bölünebilirlik (divisibility)

Karar değişkenleri, kesirli değerler dahil, herhangi bir gerçel değeri alabilir. Slaytlarda yer almıyor; ders kitabındaki dördüncü varsayımdır. Değişkenlerin tamsayı olması gerektiğinde bu varsayım bozulur ve model bir tamsayılı programlama modeline dönüşür. Ayrık optimizasyonun başladığı yer burasıdır.

Örnek: Save-It Co. — katı atıkların geri kazanımı

• Dört tür katı atık toplanıyor; şirket bunları işleyip karıştırarak satılabilir ürünlere dönüştürüyor.
• Kullanılan malzeme karışımına göre üç kalite ürün var: A, B ve C.
• Haftalık 30.000 $'lık bir hibe yalnızca işleme (treatment) maliyetinin tamamını karşılamak için kullanılacak.
• Her malzemenin mevcut miktarının en az yarısı toplanıp işlenmeli.
• Amaç: haftalık net kârı, yani toplam satış eksi toplam karıştırma (amalgamation) maliyetini en büyüklemek.

Ek kısıtlar: (1) her malzemenin haftalık mevcut miktarının en az yarısı toplanıp işlenmeli; (2) bu malzemeleri işlemek için haftada 30.000 $ kullanılmalı.

Karar değişkenleri

Karar değişkenlerini tanımlamak en kritik adımdır. Burada:

• \(x_{ij}\): haftada ürün kalitesi \(i\)'ye (\(i \in \{A, B, C\}\)) ayrılan malzeme \(j\)'nin (\(j \in \{1, 2, 3, 4\}\)) libre cinsinden miktarı. Toplam 12 değişken.
• \(\dfrac{x_{ij}}{x_{i1} + x_{i2} + x_{i3} + x_{i4}}\): kalite \(i\)'deki malzeme \(j\)'nin oranı.

Kesirli kısıtı doğrusallaştırmak

“A kalitesinde malzeme 1 en fazla %30” şartı ilk bakışta doğrusal değildir:

Payda (A'nın toplam üretimi) negatif olmadığı için iki taraf paydayla çarpılabilir ve terimler bir tarafa toplanır:

Bütün karışım şartları bu yolla doğrusal kısıtlara çevrilir. Bu, oran ve yüzde içeren modellerde sık kullanılan bir tekniktir.

Tam model

Amaç fonksiyonunda her kalitenin birim net kârı “satış fiyatı − karıştırma maliyeti”dir: A için 8,50 − 3,00 = 5,50; B için 7,00 − 2,50 = 4,50; C için 5,50 − 2,00 = 3,50. İşleme maliyeti hibeyle karşılandığı için amaçta yer almaz, bir kısıt olarak girer.

1. Karışım şartları:

2. Malzeme mevcudiyeti ve 3. işlenecek en az miktar (mevcudun yarısı):

4. İşleme maliyeti ve 5. negatif olmama:

Çözüm

Amaç değeri \(Z = 35.109{,}65\) $. Problem çözüldükten sonra tablodaki diğer büyüklükler (oranlar, toplamlar) \(x_{ij}\) değerlerinden hesaplanır. Dikkat çeken noktalar: C kalitesi hiç üretilmez; malzeme 1'in tamamı kullanılır, malzeme 3 ise tam en az sınırında (2.000 lb) kalır.

Örnek: Union Airways — personel çizelgeleme

Union Airways uçuş programına sefer eklediği için yeni müşteri hizmetleri personeli alacaktır. Günün farklı saatlerinde görevde olması gereken en az personel sayısı analiz edilmiştir. Yöneylem araştırması ekibi, personeli en düşük personel maliyetiyle yeterli hizmet verecek şekilde vardiyalara yerleştirmek istiyor.

Her personel haftada 5 gün, 8 saatlik vardiyalarda çalışır. Vardiyalar: 1: 06:00–14:00, 2: 08:00–16:00, 3: 12:00–20:00, 4: 16:00–24:00, 5: 22:00–06:00.

Formülasyon

• Etkinlikler vardiyalara karşılık gelir; bir etkinliğin düzeyi o vardiyaya atanan personel sayısıdır. Karar değişkenleri her zaman etkinliklerin düzeyleridir.
• Beş karar değişkeni: \(x_j\), \(j = 1, 2, 3, 4, 5\) (vardiya \(j\)'deki personel sayısı).
• Ana kısıtlar, tablonun son sütunundaki en az personel gereksinimleridir. Her zaman dilimi için, o dilimi kapsayan vardiyalardaki personelin toplamı gereksinimi karşılamalıdır. Örneğin 14:00–16:00 dilimini vardiya 2 ve 3 kapsar: \(x_2 + x_3 \ge 64\).

• Bazı kısıtlar fazladır (redundant): \(x_1 + x_2 \ge 79\) sağlanıyorsa \(x_1 + x_2 \ge 65\) kendiliğinden sağlanır; \(x_3 + x_4 \ge 82\) de \(x_3 + x_4 \ge 73\)'ü kapsar.
• Optimal çözüm: \((x_1, x_2, x_3, x_4, x_5) = (48, 31, 39, 43, 15)\), amaç değeri \(Z = 30.610\) $ (günlük).

Tamsayı meselesi

• Her vardiyaya atanan personel sayısı tamsayı olmalıdır.
• Modelde her \(x_j\) için tamsayı değer zorlayan ek bir kısıt bulunmalıdır. Bu kısıtlar eklenince LP modeli bir tamsayılı programlama modeline dönüşür (Hafta 13).
• Bu örnekte tamsayı kısıtları olmadan bile çözüm tamsayı çıkıyor.
• Ya optimal çözümde bazı değişkenler tamsayı olmasaydı? Yuvarlamak her zaman işe yaramaz: yuvarlanan nokta olursuz olabilir ya da optimal olmayabilir. Alıştırma 4 bunun bir örneğidir.

Çözüm terminolojisi ve özel durumlar

Çözüm (solution)

\((x_1, x_2, \dots, x_n)\) için herhangi bir değer ataması; olurlu olması gerekmez.

Olurlu çözüm (feasible solution)

Bütün kısıtların sağlandığı çözüm.

Olursuz çözüm (infeasible solution)

En az bir kısıtın ihlal edildiği çözüm.

Olurlu bölge (feasible region)

Bütün olurlu çözümlerin kümesi.

Optimal çözüm (optimal solution)

Amaç fonksiyonunun en elverişli değerine sahip olurlu çözüm. En elverişli değer, amaç en büyükleniyorsa en büyük, en küçükleniyorsa en küçük değerdir.

Özel durumlar

Her LP'nin tek bir optimumu olmak zorunda değildir. Wyndor modelinde küçük değişikliklerle üç özel durum elde edilir; hepsi yukarıdaki laboratuvarda düğmelerle görülebilir.

Köşe noktası olurlu (CPF) çözümler

Olurlu çözümü olan ve olurlu bölgesi sınırlı olan bir LP için:

• Problemin CPF çözümleri ve en az bir optimal çözümü vardır.
• En iyi CPF çözümü bir optimal çözümdür.
• Bu yüzden problemin tam olarak bir optimal çözümü varsa, o bir CPF çözüm olmalıdır.
• Birden fazla optimal çözüm varsa, bunlardan en az ikisi CPF çözüm olmalıdır.

Wyndor modelinin beş CPF çözümü vardır: \((0, 0)\), \((4, 0)\), \((4, 3)\), \((2, 6)\) ve \((0, 6)\). En iyisi \((2, 6)\)'dır. Bu özellik çok önemlidir: optimumu bulmak için sonsuz sayıdaki olurlu noktanın değil, sonlu sayıdaki köşenin incelenmesi yeter. Simpleks yöntemi (Hafta 4) tam olarak bunu yapar; köşeden komşu köşeye geçerek ilerler.

Slayt bu özellikleri koşulsuz yazıyor; “olurlu çözümü var ve olurlu bölge sınırlı” koşulu Hillier & Lieberman'daki ifadeden eklendi. Sınırsız bölgede optimum olmayabilir (yukarıdaki üçüncü durum).

Büyük modeller ve yazılım araçları

• Gerçek dünyadaki LP'ler çok büyük olabilir. Orta boy sayılan bir modelde bile binlerce fonksiyonel kısıt ve binlerce karar değişkeni bulunabilir.
• Böyle modeller pratikte bir modelleme dili ile formüle edilir. Geliştirilmiş dillerden bazıları: AMPL, MPL, GAMS, LINGO.
• Çok güçlü bir endüstriyel çözücü: CPLEX.

Öneri: LP çözmek için SciPy ile başla; model formülasyonu ön plandaysa PuLP ya da Pyomo kullan. Wyndor modeli SciPy ile:

from scipy.optimize import linprog

# linprog her zaman minimize eder: max 3x1 + 5x2  yerine  min -3x1 - 5x2
c = [-3, -5]
A_ub = [[1, 0],   # Fabrika 1:  x1        <= 4
        [0, 2],   # Fabrika 2:       2x2  <= 12
        [3, 2]]   # Fabrika 3:  3x1 + 2x2 <= 18
b_ub = [4, 12, 18]

res = linprog(c, A_ub=A_ub, b_ub=b_ub,
              bounds=[(0, None), (0, None)], method="highs")
print(res.x, -res.fun)   # [2. 6.] 36.0

\(\ge\) kısıtları A_ub'a \(-1\) ile çarpılarak, eşitlikler A_eq ve b_eq ile verilir. Save-It ve Union Airways modelleri de aynı şekilde çözülebilir; bu notta verilen optimum değerler (35.109,65 $ ve 30.610 $) SciPy ile doğrulandı.

Alıştırmalar

Slaytlardaki alıştırmalar. Önce kendin formüle edip çöz, sonra çözümü aç. Çözümler slaytlarda yok; burada hazırlanıp SciPy ile doğrulandı.

Özet

• LP'de bütün fonksiyonlar doğrusaldır; “programlama” planlama demektir.
• Bir LP; karar değişkenleri \(x_j\), parametreler \(c_j, a_{ij}, b_i\), amaç fonksiyonu, fonksiyonel kısıtlar ve negatif olmama kısıtlarından oluşur.
• Orantılılık, toplanabilirlik ve kesinlik LP'nin varsayımlarıdır; bölünebilirlik bozulduğunda tamsayılı programlamaya geçilir.
• Oran içeren kısıtlar paydayla çarpılarak doğrusallaştırılır (Save-It); kapsama kısıtları “her dilimi kapsayan vardiyaların toplamı ≥ gereksinim” biçimindedir (Union Airways).
• İki değişkenli LP grafikle çözülür: olurlu bölge çizilir, eş-kâr doğrusu kaydırılır.
• Bir LP'nin tek optimumu, çoklu optimumu olabilir, hiç olurlu çözümü olmayabilir ya da amaç sınırsız olabilir.
• Optimal çözüm varsa en iyi köşe noktası (CPF) çözümü optimaldir; simpleks yöntemi bu gerçeğe dayanır.