Doğrusal Programlama

Doğrusal Programlama gerçek dünyada karşılaşılan problemlerin sayısal yöntemler ile çözülebilen mathematiksel modellemesidir. Bu yöntemde karar değişkenleri bulunacak amaç/hedef fonksiyonunu oluştururlar. En iyi çözüm  amaç fonksiyonunun çözümüdür. Kısıtlar ise sistemin fiziki sınırlarıdır. Doğrusal programlamanın ana varsayımları:

• Tek bir amaç vardır; en küçükleme (minimizasyon) veya en büyükleme (maksimizasyon)
• Tüm değişkenler süreklidir
• Amaç ve kısıtlar doğrusaldır
• Tüm kara değişkenleri pozitiftir (negatif olma durumu gerçek dünyada olmayacağı için).

Doğrusal programlama problemlerin çözümü için muhtelif yöntemler vardır; Simpleks, Criss-cross, Ellipsoid, Protective, vb. Bunlardan Simpleks yaygın kullanılan bir algoritmadır. Simpleks her bir adımda amaç fonksiyonu değerini daha iyileştiren ötelemeli yaklaşım özelliğindedir.

Simpleks (Standard) (Bkz. Örnek - 1)

• Simpleks yönteminin ana adımları;
• Gerçek dünya probleminin matematik modelinin oluşturulması (formül olarak gösterilimi)
• Sağ Taraf Değerinin (STD) negatif olma durumunun kontrolu. Eğer bu durum belirlenirse tüm katsayılar -1 ile çarpılır ve eşitlik işareti değiştirilir. Örneğin;

 1x1 - 2x2 <= -5  düzeltme sonrasında -1x1 + x2 >= 5 olur.

• Kısıtlar için eşitsizliklerin eşitlik haline dönüştürülmesi (Standard Form – formül şeklinde gösterilim). Bir çok durumda kısıtlar eşitsizlik (büyüktür veya küçüktür) şeklindedir. Bu nedenle eşitlik (=) haline dönüştürülür.
• Karar değişkenleri Temel Dışı Değişkenler olarak adlandırılır (başlangıç olarak “x” ile temsil edilir). Diğerleri ise Temel Değişkenler olarak adlandırılırlar. Temel değişkenler Gevşek Değişkenler, Yapay Değişkenler ve Ekstra Değişkneler olarak adlandırılırlar. Temel değişkenler problemleri Standard forma dönüştürmek için kullanılırlar;
• Gevşek Değişkenler <= formundaki kısıtlara eklenirler (başlangıç olarak “s” ile gösterilir)
• Yapay Değişkenler = ve >= formundaki kısıtlara eklenirler (başlangıç olarak “a” ile gösterilir)
• Ekstra Değişkenler >= formundaki kısıtlara eklenirler (başlangıç olarak “e” ile gösterilir)
• Standard Form’dan Başlangıç Matrisini oluşturma.
• Girecek değişkenleri seçme
• Çıkacak değişkenleri seçme
• Pivot işlemi
• Uygun çözümü ve dejenere durumunu kontrol etme
• Adımları tekrarlama veya işlemi bitirme
• Dört olası sonuç söz konusudur;
• Tek eniyi çözüm,  OPTİMAL
• Birden fazla iyi çözüm; ALTERNATİF
• En iyi çözüm olmama; FİZİBIL DEĞİL
• Sonsuz Çözüm; SINIRSIZ

İki Aşamalı Simpleks

Eğer tüm kısıtlar <= formundaysa, problem tek aşamada yukarıda ana hatları verildiği şekilde çözülür. Eğer kısıtlardan bir tanesi bile “>=” veya “=” formunda ise, İki Aşamalı Simpleks kuralları uygulanır. Birinci aşamada ana problemden bir yardımcı problem oluşturularak simpleks ile çözülür ve optimal çözüm olup olmadığı araştırılır. Eğer fizibıl olduğu görülür ve optimal çözüm bulunabilirse orijinal problemin amaç fonksiyonu işlemlere dahil edilerek ikinci aşamaya geçilerek simpleks işlemleri ile en iyi çözüm bulunur.

Revize Simpleks (Bkz. Örnek - 2)

Revize Simpleks Standard Simpleks yönteminin farklı bir uygulamasıdır. Büyük problemlerin (çok kara değişkenli ve çok sayıda kısıtlı) standard Simpleks sırasında ortaya çıkan büyük matrislerin bilgisayar uygulamalarında büyük bellek gerektirmesine çözüm olarak kullanılmaktadır. Revzide Simpleks çözüm sırasında Standard Simpleks adımlarını takip eder ama başlangıç matrisi Birim Matris dir.

Tek aşamalı ve İki Aşamalı Revize Simpleks, tek aşamalı ve İki Aşamalı Revize Simpleks ile aynıdır.

Dual Problem

Bir Doğrusal Programlama problemi Primal problem olarak adlandırılır. Bu problem kendisinin dual’i bulunarak primal problemin en iyi çözümünün üst sınırını verir. Bu işlemin gerçekleştirilebilmesi için amaç fonksiyonu karar değişkenleri sayısı ve kısıt sayısı birbiri ile aynı olmalıdır.

Bir problemin Dual’ini bulmanın ana adımları:

• Kısıt katsayı matrisinin devriği (transpozesi) alınır (STD harç olarak)
• “>=” işaretleri “<=” haline ve “<=” işaretleri “>=” haline çevrilir
• Amaç fonksiyonu katsayıları ve kısıt STD değerleri birbirleri ile değiştirilir.

Bu aşamadan sonra problem tek aşamalı veya iki aşamalı Simpleks veya Revize Simpleks yöntemleri ile çözülebilir.

Yöntemlerin SimpleLPsolver’da Uygulaması

Simpleks Çözücü (Bkz. Örnek - 1)

En büyükleme problemleri için Simpleks yöntemi kullanılmaktadır. Bu nedenle en küçükleme problemleri önce en büyükleme problemi haline çevrilir. Çözüm için aşağıdaki adımlar takip edilmektedir;

• Amaç fonksiyonu karar değişkenleri katsayılarının hepsinin sıfır olup olmadığı kontrol edilir.
• Kısıtlardaki değişkenlerin tüm katsayılarının sıfır olup olmadığı kontrol edilir.
• Birbirinin aynısı kısıt olup olmadığı kontrol edilir, varsa elimine edilir.
• Eksi işaretli (negatif) STD kontrol edilir, varsa düzeltilir.
• Eğer tüm kısıtlar “<=” ise Tek Aşamalı yöntem ile devam edilir, yoksa İki Aşamalı yönteme geçilir.
• Tek Aşamalı Simpleks yöntem;
• Tüm kısıtlara gevşek değişkenler (s) eklenerek eşitlik (=) haline getirilir.
• Aşağıda gösterildiği şekilde Başlangıç Simpleks tablosu oluşturulur;

x1 x2 ... e1 e2 ... s1 s2 ... Z 0                   Kısıt.1 STD 1                   Kısıt.2 STD 2                   Kısıtt.3 STD 3                   ... ...

• Problem en büyükleme kriterlerine göre çözülür.
• İki Aşamalı Simpleks yöntemi;
• Gevşek değişkenler (s), yapay değişkenler (a) ve ekstra değişkenler (e) eklenerek tüm kısıtlar eşitlik (=) haline getirilir.
• Aşağıda gösterildiği şekilde Başlangıç İki Aşamalı Sİmpleks tablosu oluşturulur;

W x1 x2 ... e1 e2 ... s1 s2 ... a1 a2 ... w 0                         Z 1                         Kısıt.1 STD 1                         Kısıt.2 STD 2                         Kısıt.3 STD 3                         ... ...

• Temel En İyi çözüm için w satırının başlangıç değerleri hesaplanır.  Aslında bu aşamada Z satırı gerekmemesine rağmen ikinci aşamada orijinal amaç fonksiyonu kullanıma uygun hale gelmiş olacağı için işlemlere dahil edilmesi yararlı olacaktır..
• Problem İlk Aşama için en büyükleme kriterlerine göre çözülür.
• Eğer ilk aşama sonunda en iyi değer bulunursa w satırı ve yapay değişkenler tablodan çıkartılır.
• Problemin çözümüne İkinci Aşama olarak en büyükleme kriterlerine göre devam edilir.

Revize Simpleks Çözücü (Bkz. Örnek - 2)

En küçükleme problemleri için Revize Simpleks yöntemi kullanılmaktadır. Bu nedenle en büyükleme problemleri önce en küçükleme problemi haline çevrilir. Çözüm için aşağıdaki adımlar takip edilmektedir;

• Amaç fonksiyonu karar değişkenleri katsayılarının hepsinin sıfır olup olmadığı kontrol edilir.
• Kısıtlardaki değişkenlerin tüm katsayılarının sıfır olup olmadığı kontrol edilir.
• Birbirinin aynısı kısıt olup olmadığı kontrol edilir, varsa elimine edilir.
• Eksi işaretli (negatif) STD kontrol edilir, varsa düzeltilir.
• Eğer tüm kısıtlar “<=” ise Tek Aşamalı yöntem ile devam edilir, yoksa İki Aşamalı yönteme geçilir.
• (Tek Aşamalı) Simpleks yöntemi;
• Tüm kısıtlara gevşek değişkenler (s) eklenerek eşitlik (=) haline getirilir.
• Aşağıda gösterildiği şekilde Başlangıç Revize Simpleks tablosu oluşturulur;

x1 x2 x3 ... Z 0         Kısıt.1 STD 1         Kısıt.2 STD 2         Kısıt.3 STD 3         ... ...

• Aşağıda gösterildiği şekilde yapay değişkenler ile Baz matrisin tersi (B^{-1 ) oluşturulur. Başlangıçta bu Birim Matris olacaktır;}

z s1 s2 s3 ... z 1         s1   1       s2     1     s3       1   ...         1

• Problem en küçükleme kriterlerine göre çözülür.
• ● İki Aşamalı Revize Simpleks yöntemi;
• Gevşek değişkenler (s), yapay değişkenler (a) ve ekstra değişkenler (e) eklenerek tüm kısıtlar eşitlik (=) haline getirilir.
• Aşağıda gösterildiği şekilde Başlangıç İki Aşamalı Revize Simpleks tablosu oluşturulur;

W x1 x2 x3 ... e1 e2 ... W 0               Z 1               Kısıt.1 STD 1               Kısıt.2 STD 2               Kısıt.3 STD 3               ... ...

• Aşağıda gösterildiği şekilde yapay değişkenler ile Baz matrisin tersi (B^{-1 ) oluşturulur. Başlangıçta bu Birim Matris olacaktır;}

w z s1 s2 s3 ... a1 a2 a3 ... W 1                   Z   1                 s1     1               s2       1             s3         1           ...           1         a1             1       a2               1     a3                 1   ...                   1

• Temel En İyi çözüm için w satırının başlangıç değerleri hesaplanır.  Aslında bu aşamada Z satırı gerekmemesine rağmen ikinci aşamada orijinal amaç fonksiyonu kullanıma uygun hale gelmiş olacağı için işlemlere dahil edilmesi yararlı olacaktır.
• Problem İlk Aşama için en küçükleme kriterlerine göre çözülür.
• Eğer ilk aşama sonunda en iyi değer bulunursa w satırı ve yapay değişkenler tablodan çıkartılır.
• Problemin çözümüne İkinci Aşama olarak en büyükleme kriterlerine göre devam edilir.

Dual Simpleks Çözücü

Kısıt katsayı matrisinin (STD hariç tutularak) devriği alınır, “>=” işaretleri “<=” haline ve “<=” işaretleri “>=” haline çevrilir ve amaç fonksiyonu katsayıları ve kısıt STD değerleri birbirleri ile değiştirilir. Bunların neticesinde problemin Dual’i bulunur.

Sonrasında Dual problem tek aşamalı veya iki aşamalı Simpleks yöntemi ile çözülür.

Dual Revize Simpleks Çözümü

Kısıt katsayı matrisinin (STD hariç tutularak) devriği alınır, “>=” işaretleri “<=” haline ve “<=” işaretleri “>=” haline çevrilir ve amaç fonksiyonu katsayıları ve kısıt STD değerleri birbirleri ile değiştirilir. Bunların neticesinde problemin Dual’i bulunur.

Sonrasında Dual problem tek aşamalı veya iki aşamalı Revize Simpleks yöntemi ile çözülür.