Doğrusal programlama Standart şekil

[iGrand]

Bir doğrusal programlama probleminin tanımlanması için en uygun ve alışılmış olan şekline standart şekil adı verilmektedir. Bu standart şekilde bir doğrusal programlama problemi üç özel parçadan oluşmaktadır:
Her doğrusal program problemi bir genel standart doğrusal program problemine (yani kanonik şekile) dönüştürülebilir. Matematiksel olarak bir genel standart doğrusal program problemi basitçe bir şekilde şöyle ifade edilir:

• Amaç fonksiyonu - Bir maksimize edilecek doğrusal amaç fonksiyonu

• • Genel olarak n değişkenli problem için:

maks

veyamaks

.

• • Örnek olarak 2 değişkenli problem için:

maksimum bul

• Kısıtlamalar - doğrusal eşitsizlik veya eşitlik halinde kısıtlayıcı koşullar:

• • Genel olarak n değişkenli m kısıtlamalı problem için:

sk

veya

......................................................................

• • Örnek olarak 2 değişkenli ve 3 kısıtlamalı problem için

• Negatif olmama kısıtlamaları - sonuç değişken değerlerinin 0 veya pozitif değerde olmaları:

• • Genel olarak n değişkenli problem için:

veya

,

.....

• • Örnek olarak 2 değişkenli problem için

ve

Bu problem kolaylıkla matris şekline dönüştürülebilir:
maksimum bul: maks.

kısıtlamalar: kis.

Doğrusal programlama diğer şekiller de alabilir. Bunlardan birkaç örnek verelim: minimizasyon problemleri; değişik şekillerde (

veya = halinde) verilen kısıtlamalar; negatif değişkenkapsayan problem vb. Bütün bu değişik şekiller uygun dönüşümler kullanılarak standart forma dönüştürülebilirler.