Doğrusal Programlamada İki Aşamalı Problem Çözme Yöntemi: Birinci ve İkinci Aşama

Bu yöntemde problem, aşağıda verildiği gibi iki aşamada çözülür.

İlk etap:

(a) RHS ile ilgili tüm terimler olumsuz olmamalıdır. Bazıları ise -ve o zaman daha önce açıklandığı gibi yapılmalıdır.

(b) Kısıtlamaları standart biçimde ifade edin.

(d) Tüm yapay değişkenlerin toplamından oluşan yeni bir nesnel fonksiyon W oluşturun.

W = A ₁ + A ₂ + ……………………… + A _m

İşlev (W) olanaksızlık formu olarak bilinir.

(e) W işlevi asıl sorunun kısıtlamalarına tabi tutularak en aza indirilecek ve optimum temel uygulanabilir çözüm elde edilecektir.

Aşağıdaki üç durumdan herhangi biri ortaya çıkabilir:

(varım. W> 0 ve en az bir yapay değişken “Temel değişkenler” sütununda Pozitif seviyede görünür. Bu durumda, orijinal LPP için uygulanabilir bir çözüm yoktur ve prosedür durdurulur.

(ii) Min. W = 0 ve en az bir yapay değişken “Temel Değişkenler” sütununda sıfır düzeyde görünüyor. Böyle bir durumda, uygulanabilirlik formuna optimum temel uygulanabilir çözüm verilen (orijinal) LPP'ye temel bir uygulanabilir çözüm olabilir veya olmayabilir Temel bir uygulanabilir çözüm elde etmek için, I. aşamaya devam eder ve tüm yapay değişkenleri dışına çıkarmaya çalışırız. temeli ve sonra aşama II'ye geçin.

(iii) Min. W = 0'dır ve “temel değişkenler” güncel çözümü ”sütununda yapay değişken yoktur. Böyle bir durumda, orijinal LPP'ye temel bir uygulanabilir çözüm bulunmuştur. II. Aşamaya geçin.

İkinci aşama:

Orijinal LPP için bir başlangıç çözümü olarak, faz I'in optimum temel uygulanabilir çözümünü kullanın. Simpleks yöntemini kullanarak, bunun için optimal bir temel uygulanabilir çözüm elde edilinceye kadar yinelemeler yapın.

Yeni nesnel fonksiyonun (W) verilen (orijinal) LPP'nin maksimizasyon veya minimizasyon tipinden bağımsız olarak daima minimizasyon tipinde olduğu not edilebilir. Aşağıdaki örneği ele alalım.

Örnek 1 (İki fazlı tek yönlü Yöntem):

İki fazlı simpleks Yöntemi kullanın

Küçült Z = -3X - 2Y - 2Z

5X + 7Y + 4Z <7’ye tabi

-4X + 7Y + 5Z> –2

3X + 4 V - 6Z> 29/7

X, Y, Z> 0

Çözüm:

İlk etap

Aşağıdaki adımlardan oluşur.

(a) İkinci kısıtlamada, RHS, -ve, orada her iki taraftaki eksi işareti ile çarpılarak + ve yapılır.

4X - 7Y - 5Z <2

(b) Kısıtlamalara gevşeklik değişkenleri ekleme

5X + 7Y + 4Z + S ₁ = 7

4X - 7Y - 5Z + S2 = 2

3X + 4Y - 6Z - S3 = 29/7

burada X, Y, Z, S ₁, S ₂, S ₃ > 0

(c) X = Y = Z = 0 koyun, S1 = 7, S2 = 2, S3 = -29/7 olur. ilk çözüm olarak. Fakat S3 serisi -ve, yapay değişken A ekleyeceğiz, yani

3X + 4Y - 6Z - S ₃ + A ₁ = 29/7

(d) Minimizasyon tipi olan objektif fonksiyon maksimizasyon tipinde yapılır.

Z = 3X + 2Y + 2Z büyüt

(e) Minimize edilmesi gereken ilk aşama için W = A ₁ yeni amaç fonksiyonunu tanıtıyoruz.

(f) Sınırlamalarda X = Y = Z = S3 = 0 ikame edilmesi, ilk temel uygulanabilir çözelti halinde S ₁ = 7, S ₂ = 2, / A ₁ = 29/7 elde edilir.

Önceden oluşturulmuş optimallik testi

Cj-Ej aynı kolonlar altında negatif olduğundan (minimize etme sorunu) mevcut temel uygulanabilir çözüm geliştirilebilir.

Doğru tekrarlayın ve optimum çözüm:

Optimal bir çözüm elde etmek için yinelemeler yapmak.

S _1'i X _{2 ile} değiştirin. bu aşağıdaki tabloda gösterilmiştir

Tabloda, X sütunu anahtar sütunu için bir anahtar vardır ve y sütunu kimliğin ilk sütunudur. Kravat kırma yöntemini takip ederek y sütunun bağ kırmadığını görüyoruz. Kimliğin bir sonraki sütunu yani S2-sütun, anahtar satır olarak A _1- satırını verir. Böylece (1/7) anahtar unsur tabloda birliği yapılır

A1'i X ile aşağıdaki tabloda gösterildiği gibi değiştirin

Tablo 5 en uygun çözümü vermektedir. Ayrıca minimum W = 0 olduğundan ve temel değişkenlerde yapay bir değişken olmadığından, yani mevcut çözümde, Tablo5 Faz-ll için temel uygulanabilir bir çözüm sunar

İkinci aşama:

Orijinal amaç işlevi

Z = 3x + 2y + 2Z + İşletim Sistemi + 0S ₂ + 0S ₃

Orijinal kısıtlamalar kullanılarak maksimize edilmelidir. Faz II çözümünü faz II için başlangıç çözümü olarak kullanmak ve simpleks algoritmasını kullanarak hesaplama yapmak