KONU: DOĞRUSAL PROGRAMLAMA

GÖREV 2.A. Doğrusal programlama problemini çözme grafiksel yöntem

Dikkat!

Bu, 2073 numaralı çalışmanın DENEME VERSİYONU, orijinalin fiyatı 200 ruble. Tasarlandı Microsoft programı Kelime.

Ödeme. Kişiler.

Seçenek 7. Maksimum ve minimum değerleri bulundoğrusal fonksiyonФ = 2x 1 - 2 x 2kısıtlamalarla: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x ben ≥ 0, ben = 1,2.

Çözüm:

Eşitsizlik işaretlerini koşullu olarak eşitlik işaretleriyle değiştirerek x1 + x2 = 4 denklem sistemini elde ederiz;

-x1 + 2x2 = 2;

x1 + 2x2 = 10.

Bu denklemleri kullanarak düz çizgiler oluşturalım, ardından eşitsizliklerin işaretlerine göre yarım düzlemleri seçip ortak kısımlarını - ODR'nin kabul edilebilir çözüm bölgesi - dörtgen MNPQ'yu elde edelim.

Minimum fonksiyon değeri

ilişkiler - M(2; 2) noktasında

Ф dk = 2·2 - 2·2 = 0.

Maksimum değere N (10; 0) noktasında ulaşılır,

Ф maks = 2·10 - 2·0 = 20.

Seçenek 8. Maksimum ve minimum değerleri bulun

doğrusal fonksiyon Ф = x 1 + x 2

kısıtlamalarla: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x ben ≥ 0, ben = 1,2.

Çözüm:

Eşitsizlik işaretlerini koşullu olarak eşitlik işaretleriyle değiştirerek bir denklem sistemi elde ederiz x1 - 4 x2 = 4 ;

3x1 - x2 = 0;

Bu denklemleri kullanarak düz çizgiler oluşturalım, ardından eşitsizliklerin işaretlerine göre yarım düzlemleri seçip ortak kısımlarını - ODR'nin kabul edilebilir çözüm bölgesi - sınırsız MNPQ poligonunu elde edelim.

Minimum fonksiyon değeri

örneğin doğrudan NP'de

P(4; 0) noktasında

Ф dk = 4 + 0 = 4.

ODR yukarıdan sınırlı değildir, dolayısıyla Ф max = + ∞.

Seçenek 10. Maksimum ve minimum değerleri bulun

doğrusal fonksiyon Ф = 2 x 1 - 3 x 2

kısıtlamalarla: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x ben ≥ 0, ben = 1,2.

Eşitsizlik işaretlerini koşullu olarak eşitliklerle değiştirerek bir denklem sistemi elde ederiz

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Bu denklemleri kullanarak düz çizgiler oluşturalım, ardından eşitsizliklerin işaretlerine uygun olarak yarım düzlemleri seçip ortak kısımlarını - ODR'nin kabul edilebilir çözüm bölgesi - MNPQRS poligonunu elde edelim.

Г(2; -3) vektörünü oluşturalım ve koordinatların orijinini çizelim seviye çizgisi- dümdüz.

Seviye çizgisini yönünde hareket ettirdiğimizde Ф değeri artar. S(7; 0) noktasında amaç fonksiyonu maksimum Ф max =2·7–3·0= = 14 değerine ulaşır. Düzey çizgisini yönünde hareket ettirdiğimizde Ф değeri azalır. Fonksiyonun minimum değeri N(0; 5) noktasındadır.

Ф dk = 2·0 – 3·5 = –15.

GÖREV 2.B. Doğrusal programlama problemini çözme

analitik simpleks yöntemi

Seçenek 7. Amaç fonksiyonunu en aza indirin Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

kısıtlamalarla: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Çözüm:

Bilinmeyen sayısı n=6, denklem sayısı m=3. Dolayısıyla r = n-m = 3 bilinmeyen serbest olarak alınabilir. x 1, x 3 ve x 6'yı seçelim.

Temel değişkenler x 2 , x 4 ve x 5'i serbest olanlar cinsinden ifade edip sistemi birim bazına indirgeriz.

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

Amaç fonksiyonu şöyle görünecektir:

Ф = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2x1 – 5x3 – 7x6

x 1 = x 3 = x 6 = 0 koyalım ve temel değişkenler x 2 = 2 değerlerini alacaktır; x4 = 9; x 5 = 6, yani ilk uygun çözüm (0; 2; 0; 9; 6; 0), amaç fonksiyonu Ф 1 = 13.

X 3 ve x 6 değişkenleri negatif katsayılarla amaç fonksiyonuna dahil edilir, dolayısıyla değerleri arttıkça Ф değeri azalacaktır. Örnek olarak x 6'yı ele alalım. Sistemin 1. denkleminden (*) x 6 = 1'e kadar (x 2 ³ 0 iken) x 6 değerinde bir artışın mümkün olduğu açıktır. Bu durumda x 1 ve x 3 sıfıra eşit kalır. Şimdi x 4, x 5, x 6'yı temel değişkenler olarak, x 1, x 2, x 3'ü ise serbest değişkenler olarak alıyoruz. Yeni temel değişkenleri yeni serbest değişkenler cinsinden ifade edelim. Aldık

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

Ф = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Serbest değişkenlere sıfır değer yani x 1 = x 2 = x 3 = 0 iken x 6 = 1, x 4 = 3, x 5 = 4 yani üçüncü uygun çözüm (0) atayalım. 0; 3; 1); Bu durumda Ф 3 = 6.

x 3 değişkeni amaç fonksiyonuna negatif katsayı ile dahil edilmiştir, dolayısıyla x 3'ün sıfır değerine göre artması F'nin azalmasına yol açacaktır. 2. denklemden x 3'ün 1/4'e kadar artabileceği açıktır. , 3. denklemden - 2/3'e kadar. İkinci denklem daha kritiktir. x 3 değişkenini temel olanların sayısına, x 4 değişkenini de serbest olanların sayısına dönüştürelim.

Şimdi x 1, x 2 ve x 4'ü yeni serbest değişkenler olarak alıyoruz. Bunlar aracılığıyla yeni temel değişkenler x 3, x 5, x 6'yı ifade edelim. Sistemi alalım

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Amaç fonksiyonu şu şekli alacaktır:

Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

X 1 ve x 2 değişkenleri negatif katsayılarla amaç fonksiyonuna dahil edilir, dolayısıyla değerleri arttıkça Ф değeri azalacaktır. Örnek olarak x 2'yi ele alalım. Sistemin 2. denkleminden x 2 = 5'e kadar (x 5 ³ 0 iken) x 2 değerinde bir artışın mümkün olduğu açıktır. Bu durumda x 1 ve x 4 sıfır kalır, diğer değişkenlerin değerleri x 3 = 3/2'ye eşit olur; x 5 = 0, x 6 = 3/2, yani dördüncü uygun çözüm (0; 5; 3/2; 0; 0; 3/2). Bu durumda Ф 4 = 5/4.

Şimdi x 1, x 4 ve x 5'i yeni serbest değişkenler olarak alıyoruz. Bunlar aracılığıyla yeni temel değişkenler x 2, x 3, x 6'yı ifade edelim. Sistemi alalım

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Amaç fonksiyonu şu şekli alacaktır:

Ф = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

F ifadesindeki her iki değişkenin katsayıları pozitiftir, dolayısıyla F değerinde daha fazla azalma mümkün değildir.

Yani, Ф min = - 5'in minimum değeri, son uygun çözüm (0; 5; 3/2; 0; 0; 3/2) optimaldir.

Seçenek 8. Amaç fonksiyonunu maksimize edin Ф = 4 x 5 + 2 x 6

kısıtlamalarla: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Çözüm:

Denklem sayısı 4, bilinmeyen sayısı 6'dır. Dolayısıyla r = n – m = 6 – 4 = 2 değişken serbest değişken, 4 değişken ise temel değişken olarak seçilebilir. Serbest olanlar olarak x 5 ve x 6'yı, temel olanlar olarak x 1 , x 2 , x 3 , x 4'ü seçiyoruz. Temel değişkenleri serbest değişkenlerle ifade edelim ve denklem sistemini birim bazına indirgeyelim.

x1 = 12-x5-x6;

x2 = 30 - 5x5 + x6;

x3 = 6 - x5 + 2x6;

x4 = 9 - 3/2x5 + x6;

Amaç fonksiyonunu Ф = 4 x 5 + 2 x 6 formunda yazıyoruz. Serbest değişkenler x 5 = x 6 = 0'a sıfır değerleri atayalım. Bu durumda temel değişkenler x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 değerlerini alacaktır. yani ilk uygun çözümü (12, 30 , 6, 9, 0) ve F 1 = 0'ı elde ederiz.

Her iki serbest değişken de amaç fonksiyonuna pozitif katsayılarla girer, yani F'de daha fazla artış mümkündür. Örneğin x 6'yı temel sayıya dönüştürelim. Denklem (1)'den, x 5 = 12'de x 1 = 0'ın, (2) ÷ (4) x 6'ya pozitif katsayılarla dahil edildiği açıktır. Yeni bir temele geçelim: temel değişkenler - x 6, x 2, x 3, x 4, serbest - x 1, x 5. Yeni temel değişkenleri yeni serbest cinsinden ifade edelim.

x 6 = 12 - x 1 - x 5;

x2 = 42 - x1 - 6x5;

x 3 = 30 - 2 x 1 - 3 x 5;

x 4 = 21 - x 1 - 5/2 x 5;

Amaç fonksiyonu Ф = 24 - 2 x 1 + 2 x 5 formunu alacaktır;

Serbest değişkenler x 1 = x 5 = 0'a sıfır değerleri atayalım. Bu durumda temel değişkenler x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 değerlerini alacaktır. yani ikinci uygun çözümü (0, 42 , 30, 21, 0, 12) ve Ф 2 = 24'ü elde ederiz.

Hedef fonksiyon x 5 pozitif bir katsayıya dahil edilmiştir, yani F'de daha fazla bir artış mümkündür. Yeni bir temele geçelim: temel değişkenler - x 6, x 5, x 3, x 4, serbest - x 1. , x 2. Yeni temel değişkenleri yeni serbest yoluyla ifade edelim.

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2;

x 3 = 9 - 3/2 x 1 + 1/2 x 2;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5;

Amaç fonksiyonu Ф = 38 – 7/2 x 1 – 1/3 x 2 formunu alacaktır;

Serbest değişkenler x 1 = x 2 = 0'a sıfır değerleri atayalım. Bu durumda temel değişkenler x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 değerlerini alacaktır. /2, yani üçüncü uygun çözüm X 3 = (0, 0, 9, 7/2, 7, 5) ve Ф 3 = 38'i elde ederiz.

Her iki değişken de amaç fonksiyonuna negatif katsayılarla girer, yani Ф'da daha fazla artış mümkün değildir.

Bu nedenle son uygun çözüm optimaldir, yani X opt = (0, 0, 9, 7/2, 7, 5) ve Ф max = 38.

Seçenek 10. Amaç fonksiyonunu maksimize edin Ф = x 2 + x 3

kısıtlamalar altında: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Çözüm:

Denklem sistemi matrisinin ve genişletilmiş matrisin rütbeleri aynı ve 2'ye eşit olduğundan, denklem-kısıtlama sistemi tutarlıdır. Sonuç olarak, iki değişken serbest olarak alınabilir, diğer iki değişken - temel - iki serbest olan aracılığıyla doğrusal olarak ifade edilebilir.

x 2 ve x 3'ü serbest değişken olarak alalım. O halde temel değişkenler serbest terimlerle ifade edeceğimiz x 1 ve x 2 olacaktır.

x1 = 1 + x2 - x3; (*)

x4 = 2 - x2 + 2x3;

Amaç fonksiyonu zaten x 2 ve x 3 cinsinden ifade edilmiştir, yani Ф = x 2 + x 3.

x 2 =0 ve x 3 =0 için temel değişkenler x 1 = 1, x 4 = 2'ye eşit olacaktır.

F 1 = 0 ile ilk uygun çözüme X 1 = (1, 0, 0, 2) sahibiz.

Ф'da bir artış, örneğin, Ф ifadesinde pozitif bir katsayıyla yer alan x 3'ün değerini artırarak mümkündür (x 2 sıfıra eşit kalır). Sistemin ilk denklemi (*), x 3'ün (x 1 ³0 koşulundan) 1'e artırılabileceğini göstermektedir, yani bu denklem x 3 değerindeki artışa bir sınırlama getirmektedir. Sistemin ilk denklemi (*) çözümleniyor. Bu denkleme dayanarak x 1 ve x 3'ü değiştirerek yeni bir temele geçiyoruz. Artık temel değişkenler x 3 ve x 4, serbest değişkenler ise x 1 ve x 2 olacaktır. Şimdi x 3 ve x 4'ü x 1 ve x 2 cinsinden ifade edelim.

Şunu elde ederiz: x 3 = 1 - x 1 + x 2; (**)

x4 = 4 - 2x1 + x2;

Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Serbest değişkenleri sıfıra eşitleyerek ikinci kabul edilebilir temel çözümü X 2 = (0; 0; 1; 4) elde ederiz, bunun için Ф 2 = 1.

X2'deki artışla F'deki artış mümkündür. Son denklem sistemine (**) bakıldığında x2'deki artış sınırlı değildir. Sonuç olarak, Ф giderek daha büyük pozitif değerler alacaktır, yani Ф max = + ¥.

Yani amaç fonksiyonu F yukarıdan sınırlı değildir, dolayısıyla optimal bir çözüm yoktur.

GÖREV 2.D. Verilen problemin ikilisini oluşturun

orijinal görev.

Seçenek 7. Amaç fonksiyonunu maksimize edin Ф = 2× x 1 - x 4

kısıtlamalarla: x 1 + x 2 = 20,

x 2 + 2× x4 ≥5,

x 1 + x 2 + x 3 ≤ 8,

x ben ≥ 0 (i = 1, 2, 3, 4)

Çözüm:

2. ve 3. denklemlere ek değişkenler ekleyerek kısıtlama sistemini tek, örneğin kanonik bir forma getirelim.

x 1 + x 2 = 20,

x 2 + 2 × x4 – x5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

Tip 2 asimetrik bir problem elde ettik. İkili problem şuna benzeyecektir:

Amaç fonksiyonunu en aza indirin F = 20 × y 1 + 5 × y2+8 × y 3

y 1 - y 3'te ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Seçenek 8. Amaç fonksiyonunu maksimize edin Ф = x 2 - x 4 - 3× x 5

kısıtlamalarla: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x ben ≥ 0, (Ben = 1, 6)

Çözüm:

Denklem formundaki bir kısıtlamalar sistemi ile bir başlangıç ​​​​maksimizasyon problemimiz var, yani bir çift ikili problem asimetrik tip 2 tipine sahiptir, matris formundaki matematiksel modeli şu şekildedir:

Orijinal sorun: İkili sorun:

F = C × X maks F = B T × Ymin

A'da × A T'de X = B × Y ≥ C T

Orijinal problemde, amaç fonksiyonundaki değişkenler için katsayıların satır matrisi C = (0; 1; 0; -1; -3; 0) formundadır,

kısıtlama sistemindeki serbest terimlerin matris sütunu ve değişkenler için katsayılar matrisi şu şekildedir:

B = 2, A = 0 - 4 1 2 -1 0

Katsayıların aktarılmış matrisini, amaç fonksiyonundaki değişkenler için katsayıların bir satır matrisini ve serbest terimlerden oluşan bir sütun matrisini bulalım.

0 1 0 0 VT = (1; 2; 5)

A T = -1 2 0 C T = -1

İkili problem aşağıdaki biçimde yazılacaktır:

amaç fonksiyonunun minimum değerini bulun F = y 1 + 2 × y2+5 × y 3

y 1 ≥ 0 kısıtlamaları altında,

2× 1 - 4 × y2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Seçenek 10. Ф = x 1 + x 2 + x 3 fonksiyonunu en aza indirin

kısıtlamalarla: 3× x 1 + 9× x 2 + 7× x3 ≥2,

6 × x 1 + 4 x 2 + 5× x3 ≥3,

8 × x 1 + 2 x 2 + 4× x3 ≥4,

Çözüm:

Eşitsizlikler biçiminde bir kısıtlamalar sistemi ile bir başlangıç ​​minimizasyon problemimiz var, yani bir çift ikili problem, matris formundaki matematiksel modeli şu şekilde olan 3. tipte simetrik bir forma sahiptir:

Orijinal sorun İkili sorun

F = C × X dk F = B T × Ymaks

A'da × X ≥ B AT'de × e ≤ S T

X ≥ 0 Y ≥ 0

Orijinal problemde, amaç fonksiyonundaki değişkenler için katsayıların matris satırı, serbest terimlerin matris sütunu ve kısıtlar sistemindeki değişkenler için katsayılar matrisi şu şekildedir:

C = (1; 1; 1), B = 3, A = 6 4 5

İkili problemin matrislerini bulalım

B T = (2; 3; 4) C T = 3 A T = 9 4 2

İkili problem şu şekilde formüle edilmiştir:

Amaç fonksiyonunu maksimize edin F = 2y 1 + 3y 2 + 4y 3

kısıtlamalar altında 3 × 1 + 6 × y2+8 × y 3 ≤ 1,

9× 1 + 4 × y2+2 × y 3 ≤ 1,

7× y 1 + 5 × y2+4 × y 3 ≤ 1,

y ben ≥ 0 (i = 1, 2, 3)

GÖREV 2.C. Simpleks tabloları kullanarak doğrusal programlama problemini çözme.

Seçenek 7. Amaç fonksiyonunu maksimize edin Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

kısıtlamalarla: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Çözüm:

Kısıtlama sistemini kanonik forma getirelim

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

7 bilinmeyenli 3 denklemden oluşan bir sistemimiz var. Temel değişkenler olarak x 1 , z 1 , z 3 , serbest değişkenler olarak x 2 , x 3 , x 4 , z 2 adlı 3 değişken seçip temel değişkenleri bunlar üzerinden ifade edelim.

(2)'den x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6 elde ederiz

(1) ve (3)'ü yerine koyarsak şunu elde ederiz:

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Simpleks bir tablo oluşturalım

Yineleme Tablo 1

Temel AC	Özgürlük. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.

II yineleme Tablo 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.

III yineleme Tablo 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X3 = (1; 0; 6/7; 10/7; 0; 0; 0) F3 = 52/7.

IV yineleme Tablo 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F4 = 149/14.

Dizin satırında son tablo yok negatif sayılar yani amaç fonksiyonuna ilişkin ifadede tüm Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Cevap: Ф m ax = 149/14,

optimal çözüm (0; 0; 25/14; 37/14; 1/2; 0; 0)

Seçenek 8. Amaç fonksiyonunu en aza indirin Ф = 5 x 1 - x 3

kısıtlamalar altında: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 =1,

Çözüm:

Değişken sayısı 4, matrisin rütbesi 2, dolayısıyla serbest değişken sayısı r = 4 - 2 = 2, temel değişken sayısı da 2. x 3, x 4'ü şöyle alalım: serbest değişkenler, temel değişkenler x 1, x 2'yi serbest cinsinden ifade edelim ve sistemi birim bazında indirgeyelim:

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Denklem sistemini ve amaç fonksiyonunu simpleks tabloya uygun bir biçimde, yani x 2 + 2 x 4 = 1 olarak yazalım,

x 1 +2 x 3 - 3 x 4 = 2

F + 11x3 - 15x4 = 10

Hadi bir masa yapalım

Yineleme Tablo 1

Temel AC	Özgürlük. AC
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) F 1 = 10.

II yineleme Tablo 2

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) Ф 2 = -1.

III yineleme Tablo 3

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X3 = (0; 0; 7/4; 1/2) F3 = -7/4.

Son tablonun indeks satırında, yani amaç fonksiyonu ifadesinde tüm Г i > 0 pozitif sayılar yoktur. I. durum var, bu nedenle son temel çözüm optimaldir.

Cevap: Ф min = -7/4, optimal çözüm (0; 0; 7/4; 1/2)

********************

Seçenek 10. Amaç fonksiyonunu en aza indirin Ф = x 1 + x 2,

kısıtlamalar altında: x 1 –2 x 3 + x 4 = 2,

x 2 – x 3 + 2 x 4 = 1,

Çözüm:

Değişken sayısı 5, matrisin rütbesi 3 olduğundan serbest değişken sayısı r = 6-3 = 2 olur. Serbest değişken olarak x 3 ve x 4'ü, x 1 , x 2'yi alalım, x 5 temel olanlar olarak. Sistemin tüm denklemleri zaten birim bazına indirgenmiş (temel değişkenler serbest olanlarla ifade edilmiştir), ancak simpleks tabloların kullanımına uygun olmayan bir biçimde yazılmıştır. Denklem sistemini formda yazalım.

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4 . = 5

Amaç fonksiyonunu serbest değişkenler cinsinden ifade ediyoruz ve Ф - 3 x 3 +3 x 4 = 3 biçiminde yazıyoruz.

Hadi bir masa yapalım

Yineleme Tablo 1

Temel AC	Özgürlük. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X1 = (2; 3; 0; 0; 5) F1 = 3.

Tablo 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X2 = (3/2; 0; 0; 1/2; 11/2) F2 = 3/2.

Son tablonun indeks satırında, yani amaç fonksiyonu ifadesinde tüm Gi > 0 pozitif sayılar yoktur. Durum 1'e sahibiz, dolayısıyla son temel çözüm optimaldir.

Cevap: Ф min = 3/2, optimal çözüm (3/2; 0; 0; 1/2; 11/2).

Federal Eğitim Ajansı

Devlet bütçesi Eğitim kurumu

daha yüksek mesleki Eğitim

"Omsk Devlet Teknik Üniversitesi"

HESAP VE GRAFİK ÇALIŞMASI

disiplinle"OPTİMAL KONTROL TEORİSİ »

"konusuyla ilgiliOPTİMİZASYON YÖNTEMLERİ VE YÖNEYLEM ARAŞTIRMASI »

seçenek 7

Tamamlanmış:

yazışma öğrencisi

4. yıl grubu ZA-419

Tam adı: Kuzhelev S.A.

Kontrol:

Devyaterikova M.V.

Omsk – 2012
^

Görev 1. Doğrusal programlama problemlerini çözmek için grafiksel yöntem.

7) 7X 1 + 6X 2 → maksimum 20X 1 + 6X 2 ≤ 15 16X 1 − 2X 2 ≤ 18 8X 1 + 4X 2 ≤ 20 13X 1 + 3X 2 ≤ 4 X 1 , X 2 ≥ 0.

Adım 1: Uygun Bölgenin Oluşturulması

Değişkenlerin ve karelerin negatif olmama koşulları, izin verilen değerlerinin aralığını ilk çeyreğe kadar sınırlar. Modelin geri kalan dört eşitsizlik kısıtının her biri belirli bir yarı düzleme karşılık gelir. Bu yarım düzlemlerin birinci çeyrek daireyle kesişimi, problemin uygulanabilir çözüm kümesini oluşturur.

Modelin ilk kısıtlaması şu şekildedir: . İçindeki ≤ işaretini = işaretiyle değiştirerek denklemi elde ederiz . İncirde. Şekil 1.1'de düzlemi iki yarım düzleme bölen düz bir çizgiyi (1) tanımlar. bu durumdaçizginin üstünde ve altında. Hangisinin eşitsizliği karşıladığını seçmek belirli bir çizgi üzerinde yer almayan herhangi bir noktanın koordinatlarını (örneğin başlangıç ​​noktası) onun yerine koyun. X 1 = 0, X 2 = 0). Doğru ifadeyi (20 0 + 6 0 = 0 ≤15) elde ettiğimize göre, koordinatların kökenini içeren yarım düzlem (okla işaretlenmiş) eşitsizliği karşılar. Aksi takdirde başka bir yarım düzlem.

Sorunun geri kalan kısıtlamalarına da benzer şekilde devam ediyoruz. Tüm inşa edilmiş yarım düzlemlerin birinci çeyrek formlarıyla kesişimi ABCD(bkz. Şekil 1). Bu problemin uygulanabilir alanıdır.

Adım 2. Düzey çizgisi çizme Düzey çizgisi Amaç fonksiyonu, amaç fonksiyonunun sabit bir değer aldığı düzlemdeki noktalar kümesidir. Böyle bir set denklemle verilir F ( X) = yapı. Örneğin şunu koyalım: yapı = 0 ve seviyede bir çizgi çizin F ( X) = 0, yani bizim durumumuzda düz çizgi 7 X 1 + 6X 2 = 0.

Bu doğru orijinden geçer ve vektöre diktir. Bu vektör amaç fonksiyonunun (0,0) noktasındaki gradyanıdır. Bir fonksiyonun gradyanı, belirli bir fonksiyonun söz konusu noktadaki kısmi türevlerinin değerlerinin bir vektörüdür. DP probleminde amaç fonksiyonunun kısmi türevleri katsayılara eşittir. CBen, J = 1 , ..., N.

Gradyan, fonksiyonun en hızlı büyüme yönünü gösterir. Hedef fonksiyon düzeyi çizgisini taşıma F ( X) = yapı. degradenin yönüne dik olarak bölgeyle kesiştiği son noktayı buluruz. Bizim durumumuzda bu, amaç fonksiyonunun maksimum noktası olacak olan D noktasıdır (bkz. Şekil 2).

(2) ve (3) numaralı çizgilerin kesişme noktasında yer alır (bkz. Şekil 1) ve en uygun çözümü belirtir.

^ Amaç fonksiyonunun minimum değerini bulmak istiyorsanız seviye çizgisinin degrade yönünün tersi yönde hareket ettirildiğini unutmayın.

^ Adım 3. Maksimum (minimum) noktanın koordinatlarının ve amaç fonksiyonunun optimal değerinin belirlenmesi

C noktasının koordinatlarını bulmak için düz çizgilere karşılık gelen denklemlerden oluşan bir sistemi çözmek gerekir (bu durumda denklem 2 ve 3):

16X 1 − 2X 2 ≤ 18

8X 1 + 4X 2 ≤ 20

En uygun çözümü elde ederiz = 1.33.

^ Optimum değer amaç fonksiyonu F * = F (X*) = 7 * 0 + 6 * 1,33 = 7,8

DİSİPLİNDE KONTROL ÇALIŞMASI:

“İYİ ÇÖZÜM YÖNTEMLERİ”

Seçenek No.8

1. Doğrusal programlama problemini grafiksel olarak çözün. Verilen kısıtlamalarla  fonksiyonunun maksimum ve minimumunu bulun:

,

.

Çözüm

Kısıtlamalar sistemi altında amaç fonksiyonunun minimum değerini ve maksimumunu bulmak gerekir:

9x1 +3x2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Uygun çözümlerden oluşan bir bölge oluşturalım; Eşitsizlik sistemini grafiksel olarak çözelim. Bunu yapmak için, her bir düz çizgiyi oluştururuz ve eşitsizliklerle tanımlanan yarım düzlemleri tanımlarız (yarım düzlemler bir asal sayı ile gösterilir).

Yarım düzlemlerin kesişimi, nokta koordinatları problemin kısıtları sisteminin eşitsizliklerini karşılayan bir bölge olacaktır. Çözüm poligonunun alanının sınırlarını gösterelim.

F = 0 fonksiyonunun değerine karşılık gelen bir doğru çizelim: F = 2x 1 +3x 2 = 0. Amaç fonksiyonunun katsayılarından oluşan gradyan vektörü, F(X)'in minimizasyon yönünü gösterir. Vektörün başlangıcı (0; 0) noktası, sonu ise (2; 3) noktasıdır. Bu düz çizgiyi paralel olarak hareket ettireceğiz. Minimal çözümle ilgilendiğimiz için, düz çizgiyi belirlenen alana ilk değene kadar hareket ettiriyoruz. Grafikte bu düz çizgi noktalı çizgiyle gösterilmiştir.

Dümdüz
bölgeyi C noktasında keser. C noktası (4) ve (1) çizgilerinin kesişmesi sonucu elde edildiği için koordinatları bu çizgilerin denklemlerini karşılar:
.

Denklem sistemini çözdükten sonra şunu elde ederiz: x 1 = 3,3333, x 2 = 0.

Amaç fonksiyonunun minimum değerini nasıl bulabiliriz: .

Problemin amaç fonksiyonunu ele alalım.

F = 0 fonksiyonunun değerine karşılık gelen düz bir çizgi çizelim: F = 2x 1 +3x 2 = 0. Amaç fonksiyonunun katsayılarından oluşan gradyan vektörü, F(X)'in maksimuma çıkma yönünü gösterir. Vektörün başlangıcı (0; 0) noktası, sonu ise (2; 3) noktasıdır. Bu düz çizgiyi paralel olarak hareket ettireceğiz. Maksimum çözümle ilgilendiğimiz için, belirlenen alanın son dokunuşuna kadar düz çizgiyi hareket ettiriyoruz. Grafikte bu düz çizgi noktalı çizgiyle gösterilmiştir.

Dümdüz
bölgeyi B noktasında keser. B noktası (2) ve (3) çizgilerinin kesişmesi sonucu elde edildiği için koordinatları bu çizgilerin denklemlerini karşılar:

.

Amaç fonksiyonunun maksimum değerini nasıl bulabiliriz: .

Cevap:
Ve
.

2 . Simpleks yöntemini kullanarak doğrusal programlama problemini çözün:

.

Çözüm

Simpleks yöntemini ve simpleks tablosunu kullanarak doğrudan doğrusal programlama problemini çözelim.

Amaç fonksiyonunun minimum değerini belirleyelim
aşağıdaki koşullar-kısıtlamalar altında:
.

İlk referans planını oluşturmak için, ek değişkenler ekleyerek eşitsizlik sistemini bir denklem sistemine indirgeyebiliriz.

1. anlam eşitsizliğinde (≥) temel değişkeni tanıtıyoruz X 3 eksi işaretiyle. 2. anlam eşitsizliğinde (≤) temel değişkeni tanıtıyoruz X 4 . 3. anlam eşitsizliğinde (≤) temel değişken x 5'i tanıtıyoruz.

Yapay değişkenleri tanıtalım : 1. eşitlikte bir değişken tanıtıyoruz X 6 ;

Sorunu minimuma indirmek için amaç fonksiyonunu şu şekilde yazıyoruz: .

Amaç fonksiyonuna eklenen yapay değişkenlerin kullanımı için, genellikle belirtilmeyen çok büyük bir pozitif sayı olan M cezası uygulanır.

Ortaya çıkan temele yapay, çözüm yöntemine ise yapay temel yöntemi denir.

Üstelik yapay değişkenler problemin içeriğiyle ilgili olmayıp bir başlangıç ​​noktası oluşturulmasını mümkün kılmakta ve optimizasyon süreci bu değişkenleri sıfır değer almaya zorlayarak optimal çözümün kabul edilebilirliğini sağlamaktadır.

Denklemlerden yapay değişkenleri ifade ederiz: x 6 = 4-x 1 -x 2 +x 3, bunu amaç fonksiyonuna koyarız: veya.

Katsayı matrisi
bu denklem sistemi şu şekildedir:
.

Temel değişkenler için denklem sistemini çözelim: X 6 , X 4 , X 5.

Serbest değişkenlerin 0'a eşit olduğunu varsayarak ilkini elde ederiz. referans planı:

X1 = (0,0,0,2,10,4)

Negatif değilse, temel bir çözüme kabul edilebilir denir.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 4
X 5

Mevcut referans planı optimal değil çünkü indeks satırında pozitif katsayılar var. Öndeki sütun olarak x 2 değişkenine karşılık gelen sütunu seçeceğiz çünkü bu en büyük katsayıdır. Değerleri hesaplayalım D Ben ve bunlardan en küçüğünü seçiyoruz: min(4: 1, 2: 2, 10: 2) = 1.

Bu nedenle 2. satır önde gelen satırdır.

Çözümleme elemanı (2)'ye eşittir ve öndeki sütun ile ön sıranın kesişiminde bulunur.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 4
X 5

Simpleks tablonun bir sonraki bölümünü oluşturuyoruz. Plan 1, x4 değişkeni yerine x2 değişkenini içerecektir.

Plan 1'deki x 2 değişkenine karşılık gelen satır, plan 0'ın x 4 satırının tüm elemanlarının RE = 2 çözümleme elemanına bölünmesiyle elde edilir. Çözme elemanının yerine 1 elde ederiz. X 2 sütununun geri kalan hücrelerine sıfır yazıyoruz.

Böylece yeni planda 1. satır x 2 ve sütun x 2 doldurulmuş olur. İndeks satırının elemanları da dahil olmak üzere yeni plan 1'in diğer tüm elemanları dikdörtgen kuralına göre belirlenir.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 2
X 5
		1 1/2 +1 1/2 M

Mevcut referans planı optimal değil çünkü indeks satırında pozitif katsayılar var. Öndeki sütun olarak x 1 değişkenine karşılık gelen sütunu seçeceğiz çünkü bu en büyük katsayıdır. Değerleri hesaplayalım D Ben bölme bölümü olarak satır bazında: ve onlardan en küçüğünü seçiyoruz: min (3: 1 1 / 2, -, 8: 2) = 2.

Bu nedenle 1. satır önde gelen satırdır.

Çözme elemanı (1 1/2)'ye eşittir ve ön sütun ile ön sıranın kesişiminde bulunur.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6		1 1 / 2
X 2
X 5
		-1 1 / 2 +1 1 / 2 M

Simpleks tablonun bir sonraki bölümünü oluşturuyoruz. Plan 2, x 6 değişkeni yerine x 1 değişkenini içerecektir.

Yeni bir simpleks tablo elde ediyoruz:

		X 1	X 2	X 3	X 4	X 5	X 6
X 1
X 2
X 5

Index string değerleri arasında pozitif değer bulunmamaktadır. Dolayısıyla bu tablo problem için en uygun planı belirler.

Simpleks tablonun son hali:

		X 1	X 2	X 3	X 4	X 5	X 6
X 1
X 2
X 5

Optimal çözümde yapay değişkenler bulunmadığından (sıfıra eşit olduklarından) bu çözüm kabul edilebilirdir.

Optimal plan şu şekilde yazılabilir: x 1 = 2, x 2 = 2:.

Cevap:
,
.

3. Üç Şişman Adam şirketi, konserve etleri şehrin farklı yerlerinde bulunan üç deposundan üç mağazaya ulaştırıyor. Depolarda bulunan konserve yiyecek stoklarının yanı sıra mağaza siparişlerinin hacimleri ve teslimat oranları (geleneksel para birimleri cinsinden) taşıma tablosunda sunulmaktadır.

En düşük parasal maliyeti sağlayan bir ulaşım planı bulun (“kuzeybatı köşesi” yöntemini kullanarak ilk ulaşım planını gerçekleştirin).

Çözüm

Problemin çözülebilirliği için gerekli ve yeterli koşulu kontrol edelim:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Denge şartı sağlanmıştır. Eşit ihtiyaçları karşılar. Bu nedenle ulaştırma probleminin modeli kapalıdır.

Başlangıç ​​verilerini dağıtım tablosuna girelim.

İhtiyaçlar

Kuzeybatı köşe yöntemini kullanarak ulaşım probleminin ilk referans planını oluşturacağız.

Plan sol üst köşeden dolmaya başlar.

Gerekli eleman 4'tür. Bu eleman için stoklar 300, ihtiyaçlar 250'dir. Minimum 250 olduğundan çıkarıyoruz: .

			300 - 250 = 50
250 - 250 = 0

Gerekli eleman 2'ye eşittir. Bu eleman için stoklar 50, ihtiyaçlar 400'dür. Minimum 50 olduğundan çıkarıyoruz: .

			50 - 50 = 0
	400 - 50 = 350

Gerekli eleman 5'tir. Bu eleman için stoklar 300, ihtiyaçlar 350'dir. Minimum 300 olduğundan çıkarıyoruz:

			300 - 300 = 0
	350 - 300 = 50

Aradığınız eleman 3. Bu eleman için stoklar 200, gereksinimler 50. Minimum 50 olduğu için çıkarıyoruz:

			200 - 50 = 150
	50 - 50 = 0

Gerekli eleman 6'dır. Bu eleman için stoklar 150, ihtiyaçlar 150'dir. Minimum 150 olduğundan çıkarıyoruz:

			150 - 150 = 0
		150 - 150 = 0

İhtiyaçlar

giriiş

İnsani gelişmenin mevcut aşaması, enerji çağının yerini bilgisayar bilimi çağının almasıyla ayırt edilir. İnsan faaliyetinin tüm alanlarına yeni teknolojilerin yoğun bir şekilde tanıtılması söz konusudur. Eğitimin geliştirilmesinin öncelikli olması gereken bilgi toplumuna geçiş konusunda gerçek bir sorun var. Toplumdaki bilginin yapısı da değişmektedir. için giderek daha önemli pratik Yaşam Bireyin yaratıcı gelişimine katkıda bulunan temel bilgileri kazanır. Edinilen bilginin yapıcılığı ve amaca uygun olarak yapılandırılabilmesi de önemlidir. Bilgiye dayanarak yenileri oluşur bilgi kaynakları toplum. Yeni bilginin oluşumu ve edinimi, model yaklaşımının özel bir yer tuttuğu sistem yaklaşımının katı metodolojisine dayanmalıdır. Model yaklaşımının olanakları, hem kullanılan biçimsel modeller hem de modelleme yöntemlerinin uygulama yöntemleri açısından son derece çeşitlidir. Fiziksel modelleme oldukça basit sistemler için güvenilir sonuçlar elde edilmesini sağlar.

Şu anda, modelleme yöntemlerinin bir dereceye kadar kullanılmayacağı bir insan faaliyeti alanını adlandırmak mümkün değildir. Bu özellikle yönetim alanında geçerlidir çeşitli sistemler Ana süreçlerin alınan bilgilere dayanarak karar verme olduğu yer.

1. Sorunun beyanı

minimum amaç fonksiyonu

Görevin 16 numaralı seçeneğine uygun olarak çözüm poligonu tarafından belirtilen kısıtlamalar sistemi için amaç fonksiyonunun minimumunu bulma problemini çözün. Çözüm poligonu Şekil 1'de gösterilmektedir:

Şekil 1 - Sorunun çözüm poligonu

Kısıtlama sistemi ve problemin amaç fonksiyonu aşağıda sunulmaktadır:

Sorunu aşağıdaki yöntemleri kullanarak çözmek gerekir:

DP problemlerinin çözümü için grafiksel yöntem;

DP problemlerinin çözümünde cebirsel yöntem;

DP problemlerinin çözümü için Simpleks yöntemi;

LP problemlerine kabul edilebilir bir çözüm bulma yöntemi;

Çift LP probleminin çözümü;

Tamsayılı DP problemlerinin çözümünde dal ve sınır yöntemi;

Tamsayılı DP problemlerinin çözümü için Gomori yöntemi;

Boolean DP problemlerini çözmek için Balaz yöntemi.

Çözüm sonuçlarını karşılaştırın farklı yöntemlerÇalışmadan uygun sonuçları çıkarın.

2. Doğrusal programlama probleminin grafiksel çözümü

Doğrusal programlama problemlerinin çözümünde grafiksel yöntem, bilinmeyen sayısının üçü geçmediği durumlarda kullanılır. Çözümlerin özelliklerinin niteliksel araştırılması için uygundur ve diğer yöntemlerle (cebirsel, dal ve sınır vb.) birlikte kullanılır. Yöntemin fikri, doğrusal eşitsizlikler sisteminin grafiksel çözümüne dayanmaktadır.

Pirinç. 2 LP probleminin grafiksel çözümü

Asgari puan

A1 ve A2 noktalarından geçen bir doğrunun denklemi:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

kısıtlamalarla:

Cebirsel simpleks yöntemini kullanarak doğrusal programlama problemini çözme

Bir problemin çözümü için cebirsel bir yöntemin uygulanması, DP probleminin temsilinin genelleştirilmesini gerektirir. Eşitsizlikler biçiminde belirtilen orijinal kısıtlama sistemi, kısıtlamalar eşitlikler biçiminde belirlendiğinde standart gösterime dönüştürülür. Kısıtlama sisteminin dönüştürülmesi standart görünüm aşağıdaki adımları içerir:

Eşitsizlikleri, solda değişkenler ve serbest terimler, sağda 0 olacak şekilde dönüştürün; ile Sol Taraf sıfırdan büyük veya sıfıra eşitti;

Kısıtlama sistemindeki eşitsizliklerin sayısına eşit olan ek değişkenler ekleyin;

Eklenen değişkenlerin negatif olmamalarına ek kısıtlamalar getirerek eşitsizlik işaretlerini katı eşitlik işaretleriyle değiştirin.

Cebirsel yöntemi kullanarak bir DP problemini çözerken bir koşul eklenir: amaç fonksiyonu minimuma doğru yönelmelidir. Eğer bu durum sağlanmıyorsa amaç fonksiyonunu buna göre dönüştürmek (-1 ile çarpmak) ve minimizasyon problemini çözmek gerekir. Çözüm bulunduktan sonra değişkenlerin değerlerini orijinal fonksiyona yerleştirip değerini hesaplayın.

Cebirsel yöntemi kullanan bir problemin çözümü, tüm temel değişkenlerin değerleri negatif olmadığında ve amaç fonksiyonu denklemindeki serbest değişkenlerin katsayıları da negatif olmadığında optimal kabul edilir. Bu koşullar karşılanmazsa, yukarıdaki kısıtlamaların yerine getirilmesini sağlamak için bazı değişkenleri diğerleri cinsinden ifade ederek (serbest ve temel değişkenleri değiştirerek) eşitsizlikler sistemini dönüştürmek gerekir. Tüm serbest değişkenlerin değeri sıfıra eşit kabul edilir.

Doğrusal programlama problemlerini çözmek için cebirsel yöntem en çok kullanılan yöntemlerden biridir. etkili yöntemler küçük ölçekli problemleri manuel olarak çözerken çok sayıda aritmetik hesaplama gerektirmez. Bu yöntemin makinede uygulanması, örneğin simpleks yönteminden daha karmaşıktır çünkü Cebirsel yöntemi kullanan çözüm algoritması bir dereceye kadar buluşsaldır ve çözümün etkinliği büyük ölçüde kişisel deneyime bağlıdır.

Serbest değişkenler

St. şerit - ek olarak kiti

Negatif olmama koşulları sağlandığı için en uygun çözüm bulunmuştur.

3. Simpleks tablo kullanarak doğrusal programlama problemini çözme

Çözüm: Simpleks tablo kullanarak problemi standart çözüm şekline getirelim.

Sistemin tüm denklemlerini şu şekle indirgeyelim:

Simpleks bir tablo oluşturuyoruz:

Tablonun her hücresinin üst köşesine denklem sisteminden katsayıları giriyoruz;

F satırındaki maksimum pozitif öğeyi seçiyoruz, bunun genel sütun olması dışında;

Genel unsuru bulmak için tüm olumlu olanlara ilişkin bir ilişki kurarız. 3/3; 9/1;- x3 satırındaki minimum oran. Bu nedenle - genel dize ve =3 - genel öğe.

=1/=1/3'ü buluyoruz. Onu genel elemanın bulunduğu hücrenin alt köşesine getiriyoruz;

Genel çizginin tüm boş alt köşelerine hücrenin üst köşesindeki değerin çarpımını şu şekilde giriyoruz;

Genel çizginin üst köşelerini seçin;

Genel sütunun tüm alt köşelerinde, üst köşedeki değerin çarpımını - ile giriyoruz ve elde edilen değerleri seçiyoruz;

Tablonun geri kalan hücreleri, karşılık gelen seçilen öğelerin ürünleri olarak doldurulur;

Daha sonra genel sütun ve satırın elemanlarının hücrelerinin tanımlarının değiştirildiği (x2 ve x3) yeni bir tablo oluşturuyoruz;

Daha önce alt köşede bulunan değerler, eski genel satır ve sütunun üst köşesine yazılır;

Bir önceki tabloda bu hücrelerin üst ve alt köşelerinin değerlerinin toplamı, kalan hücrelerin üst köşesine yazılmıştır.

4. Kabul edilebilir bir çözüm bularak doğrusal programlama problemini çözmek

Bir doğrusal cebirsel denklem sistemi verilsin:

Her şeyin öyle olduğunu varsayabiliriz, aksi takdirde karşılık gelen denklemi -1 ile çarparız.

Yardımcı değişkenleri tanıtıyoruz:

Ayrıca bir yardımcı fonksiyon da sunuyoruz

Kısıtlamalar (2) ve koşullar altında sistemi minimuma indireceğiz.

İZİN VERİLEN BİR ÇÖZÜM BULMA KURALI: (1) sistemine kabul edilebilir bir çözüm bulmak için, (2) kısıtlamaları altında form (3)'ü en aza indiririz, xj'yi serbest bilinmeyenler olarak alırız ve xj'yi temel alırız.

Simpleks yöntemini kullanarak bir sorunu çözerken iki durum ortaya çıkabilir:

min f=0 ise tüm i'lerin sıfıra eşit olması gerekir. Ve ortaya çıkan xj değerleri sistem (1) için kabul edilebilir bir çözüm oluşturacaktır.

min f>0, yani orijinal sistemin uygun bir çözümü yoktur.

Kaynak sistemi:

Sorunun önceki konudaki durumu kullanılır.

Ek değişkenleri tanıtalım:

Orijinal problemin kabul edilebilir bir çözümü bulunmuştur: x1 = 3, x2 = 3, F = -12. Elde edilen uygun çözüme dayanarak, orijinal problemin optimal çözümünü simpleks yöntemini kullanarak bulacağız. Bunu yapmak için, yukarıda elde edilen tablodan yeni bir simpleks tablo oluşturacağız, yardımcı problemin hedef fonksiyonuyla satırı ve satırı kaldıracağız:

Oluşturulan simpleks tabloyu analiz ettiğimizde, orijinal problem için en uygun çözümün zaten bulunduğunu görüyoruz (amaç fonksiyonuna karşılık gelen satırdaki öğeler negatiftir). Böylece, yardımcı problem çözülürken bulunan uygun çözüm, orijinal problemin optimal çözümüyle örtüşür:

6. Çift doğrusal programlama problemi

Orijinal kısıt sistemi ve problemin amaç fonksiyonu aşağıdaki şekilde gösterilmektedir.

kısıtlamalarla:

Çözüm: Kısıtlama sistemini standart bir forma getirelim:

Bunun ikili sorunu şu şekilde olacaktır:

İkili problemin çözümü basit simpleks yöntemi kullanılarak gerçekleştirilecektir.

Minimizasyon problemini çözecek şekilde amaç fonksiyonunu dönüştürelim ve simpleks yöntemini kullanarak çözmek için kısıtlar sistemini standart formda yazalım.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

İkili DP problemini çözmek için bir başlangıç ​​simpleks tablosu oluşturalım.

Simpleks yönteminin ikinci adımı

Böylece simpleks yönteminin üçüncü adımında aşağıdaki sonuçlarla minimizasyon problemine optimal çözüm bulunmuştur: y2 = -7 /8, y1 = -11/8, Ф = 12. ikili problemin amaç fonksiyonu, temel ve serbest değişkenlerin bulunan değerlerini maksimizasyon fonksiyonuna koyarız:

Фmaks = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Direkt ve dual problemlerin amaç fonksiyonunun değeri çakıştığı için direkt problemin çözümü bulunmuş ve 12'ye eşit olmuştur.

Fmin = Фmaks = -12

7. Dal ve sınır yöntemini kullanarak tamsayılı doğrusal programlama problemini çözme

Orijinal problemi, geleneksel yöntemler kullanılarak çözüldüğünde tamsayı koşulu sağlanmayacak şekilde dönüştürelim.

Bir tamsayı programlama probleminin çözümlerinin başlangıç ​​poligonu.

Oluşturduğumuz dönüştürülmüş çözüm poligonu için yeni sistem kısıtlamalar.

Cebirsel yöntemle çözülmesi gereken kısıtlama sistemini eşitlikler biçiminde yazalım.

Çözüm sonucunda problem için en uygun plan bulunmuştur: x1 = 9/4, x2 = 5/2, F = -41/4. Bu çözüm, problemde belirlenen tamsayı koşulunu karşılamıyor. Orijinal çözüm poligonunu alan 3'ü hariç tutarak iki alana bölelim.

Değiştirilmiş problem çözüm poligonu

Çözüm poligonunun ortaya çıkan alanları için yeni kısıtlama sistemleri oluşturalım. Sol alan bir dörtgendir (yamuk). Çözüm poligonunun sol bölgesi için kısıtlama sistemi aşağıda sunulmuştur.

Sol alan için kısıtlama sistemi

Sağdaki alan C noktasını temsil eder.

Doğru karar bölgesi için kısıtlama sistemi aşağıda sunulmuştur.

Yeni kısıt sistemleri birbirinden bağımsız olarak çözülmesi gereken iki yardımcı problemi temsil etmektedir. Çözüm çokgeninin sol bölgesi için bir tamsayı programlama problemi çözelim.

Çözüm sonucunda problem için en uygun plan bulunmuştur: x1 = 3, x2 = 3, F = -12. Bu plan, problemdeki değişkenlerin tamsayı olması koşulunu sağlar ve orijinal tamsayılı doğrusal programlama problemi için en uygun referans plan olarak kabul edilebilir. Doğru çözüm bölgesini çözmenin bir anlamı yok. Aşağıdaki şekil bir tamsayılı doğrusal programlama problemini ağaç biçiminde çözmenin ilerlemesini göstermektedir.

Gomori yöntemini kullanarak bir tamsayılı doğrusal programlama probleminin çözümünde ilerleme.

Birçok pratik uygulamada, doğrusal eşitsizlikler sisteminin ve doğrusal bir formun verildiği bir tamsayılı programlama problemi büyük ilgi görmektedir.

Sistem (1)'e, amaç fonksiyonu F'yi en aza indiren bir tamsayı çözümünün bulunması gerekmektedir ve tüm katsayılar tam sayıdır.

Tamsayılı programlama problemini çözme yöntemlerinden biri Gomori tarafından önerildi. Yöntemin fikri, sürekli doğrusal programlama yöntemlerini, özellikle de simpleks yöntemini kullanmaktır.

1) Simpleks yöntemini kullanarak, tamsayı çözüm gereksinimini ortadan kaldıran (1), (2) probleminin çözümü belirlenir; çözümün tamsayı olduğu ortaya çıkarsa, tamsayı probleminin istenen çözümü de bulunacaktır;

2) Aksi takdirde, eğer bazı koordinatlar bir tam sayı değilse, problemin ortaya çıkan çözümü, bir tamsayı çözümünün (kabul edilebilir bir çokyüzlüde tamsayı noktalarının varlığı) var olma olasılığı açısından kontrol edilir:

kesirli serbest terimli herhangi bir satırda diğer tüm katsayılar tam sayı olarak ortaya çıkarsa, bu durumda kabul edilebilir çokyüzlüde hiçbir tam sayı veya nokta yoktur ve tamsayı programlama probleminin bir çözümü yoktur;

Aksi takdirde, tamsayı programlama problemine bir çözüm bulma konusunda ümit vermeyen, kabul edilebilir çokyüzlünün bir kısmını kesen ek bir doğrusal kısıtlama getirilir;

3) Ek bir doğrusal kısıtlama oluşturmak için, kesirli serbest terim içeren l'inci satırı seçin ve ek kısıtlamayı yazın

burada ve sırasıyla katsayıların kesirli kısımları ve serbest

üye. Kısıt (3)'e bir yardımcı değişken ekleyelim:

Kısıt (4)’e dahil edilen katsayıları belirleyelim:

nerede ve sırasıyla ve için aşağıdan en yakın tamsayılardır.

Gomori, sonlu sayıda benzer adımın, çözümü tamsayı ve dolayısıyla istenen çözüm olan bir doğrusal programlama problemine yol açtığını kanıtladı.

Çözüm: Doğrusal kısıtlar sistemini ve amaç fonksiyonunu kanonik forma getirelim:

Tamsayı koşulunu geçici olarak göz ardı ederek doğrusal kısıtlamalar sisteminin en uygun çözümünü belirleyelim. Bunun için simpleks yöntemini kullanıyoruz. Aşağıda tablolarda sırasıyla problemin orijinal çözümü sunulmakta ve problemin optimal çözümünü elde etmek için orijinal tablonun dönüşümleri verilmektedir:

Balazs yöntemini kullanarak Boolean DP problemlerini çözme.

Aşağıdaki kuralları dikkate alarak Boolean değişkenli bir tamsayılı doğrusal programlama problemi için kendi versiyonunuzu oluşturun: problem en az 5 değişken kullanır, en az 4 kısıtlama kullanır, kısıtlamaların katsayıları ve amaç fonksiyonu keyfi olarak seçilir, ancak bu şekilde Kısıtlamalar sisteminin uyumlu olmasının bir yolu. Görev, Balazs algoritmasını kullanarak LCLP'yi Boolean değişkenleriyle çözmek ve kapsamlı arama yöntemini kullanarak problemin çözümüne ilişkin hesaplamaların karmaşıklığındaki azalmayı belirlemektir.

Kısıtlamaların uygulanması

F değeri

Filtreleme sınırlaması:

Hesaplamalı efor azaltımının belirlenmesi

Kapsamlı arama yöntemini kullanarak sorunun çözümü 6*25=192 hesaplanmış ifadedir. Sorunun Balazs yöntemiyle çözümü 3*6+(25-3)=47 hesaplanmış ifadedir. Kapsamlı arama yöntemini kullanarak problemin çözümüne ilişkin hesaplamaların karmaşıklığındaki toplam azalma:

Çözüm

Yeni bilgi teknolojisini uygulayan bilgi sistemlerinin tasarlanma süreci sürekli olarak iyileştirilmektedir. Sistem mühendislerinin odak noktası giderek karmaşık sistemler üzerinde yoğunlaşıyor, bu da fiziksel modellerin kullanımını zorlaştırıyor ve sistemlerin matematiksel modellerinin ve makine simülasyonunun önemini artırıyor. Makine simülasyonu, karmaşık sistemleri incelemek ve tasarlamak için etkili bir araç haline geldi. Esneklikleri, gerçek süreçlere uygunlukları ve modern PC'ler temelinde düşük uygulama maliyetleri nedeniyle matematiksel modellerin önemi sürekli artmaktadır. Kullanıcıya, yani bilgisayar teknolojisini kullanan sistemleri modelleme konusunda uzmana giderek daha fazla fırsat sağlanmaktadır. Modellemenin kullanımı, hatalı kararların maliyetinin en yüksek olduğu otomatik sistem tasarımının ilk aşamalarında özellikle etkilidir.

Modern bilgi işlem araçları, sistemlerin incelenmesinde kullanılan modellerin karmaşıklığını önemli ölçüde arttırmayı mümkün kılmış; gerçek sistemlerde meydana gelen tüm çeşitli faktörleri dikkate alan birleşik, analitik ve simülasyon modelleri oluşturmak mümkün hale gelmiştir; incelenen olguya daha uygun modellerin kullanılması.

Edebiyat:

1. Lyashchenko I.N. Doğrusal ve doğrusal olmayan programlama / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. - K.: “Yüksek Okul”, 1975, 372 s.

2. Tam zamanlı ve yarı zamanlı çalışma biçimlerinin “Bilgisayar Sistemleri ve Ağları” uzmanlığı öğrencileri için “Uygulamalı Matematik” disiplininde bir ders projesini tamamlama yönergeleri / Derleyen: I.A. Balakireva, A.V. Yayınevi, 2003. - 15 s.

3. “Uygulamalı Matematik” disiplinini incelemek için yönergeler, “Küresel arama ve tek boyutlu minimizasyon yöntemleri” bölümü / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Yayınevi, 2000. - 31 s.

4. Tam zamanlı ve yarı zamanlı eğitim için “Bilgisayar Sistemleri ve Ağlar” bölümü “Tamsayılı doğrusal programlama problemlerini çözme” bölümü öğrencileri için “Uygulamalı Matematik” disiplinini incelemeye yönelik yönergeler / Derleyen: I.A. Balakireva, A.V. : SevNTU Yayınevi, 2000. - 13 s.

5. Akulich I.L. Örneklerde ve problemlerde matematiksel programlama:

6. Ders Kitabı İktisat öğrencilerine ödenek. uzman. üniversiteler.-M.: Daha yüksek. okul, 1986.- 319 s., hasta.

7. Andronov S.A. Optimal tasarım yöntemleri: Ders metni / SPbSUAP. St. Petersburg, 2001. 169 s.: hasta.

Benzer belgeler

Simpleks yöntemini kullanarak doğrusal programlama problemlerini çözmek için algoritma. Doğrusal programlama probleminin matematiksel modelinin oluşturulması. Excel'de doğrusal programlama problemini çözme. Kâr bulma ve en uygun üretim planı.

kurs çalışması, eklendi 03/21/2012


Grafik problem çözümü. Matematiksel bir modelin hazırlanması. Amaç fonksiyonunun maksimum değerinin belirlenmesi. Kanonik doğrusal programlama probleminin yapay temeli ile simpleks yöntemiyle çözüm. Çözümün optimalliğinin kontrol edilmesi.

test, eklendi: 04/05/2016


Doğrusal programlamanın teorik temelleri. Doğrusal programlama problemleri, çözüm yöntemleri. Optimum çözümün analizi. Tek indeksli doğrusal programlama probleminin çözümü. Sorunun beyanı ve veri girişi. Model yapımı ve çözüm aşamaları.

kurs çalışması, eklendi 12/09/2008


Matematiksel bir modelin oluşturulması. Simpleks tablo kullanarak simpleks yöntemini kullanarak doğrudan doğrusal programlama problemini çözme yönteminin seçimi, gerekçesi ve açıklaması. İkili bir problemin derlenmesi ve çözümü. Modelin duyarlılık analizi.

kurs çalışması, eklendi 31.10.2014


İşletmenin maksimum kârını elde etmek için matematiksel modelin oluşturulması, problemin grafiksel çözümü. SOLVER eklentisini kullanarak sorunu çözme. Kaynak rezervlerindeki değişikliklerin analizi. Amaç fonksiyonunun katsayılarını değiştirmek için limitlerin belirlenmesi.

kurs çalışması, eklendi 12/17/2014


Matematiksel programlama. Doğrusal programlama. Doğrusal programlama problemleri. Doğrusal programlama problemlerinin çözümü için grafiksel yöntem. Doğrusal programlama probleminin ekonomik formülasyonu. Matematiksel bir modelin oluşturulması.

kurs çalışması, 10/13/2008 eklendi


Doğrusal programlama problemini grafiksel yöntemle çözme, MS Excel'de kontrol etme. Bir programdaki bir problemi çözmenin iç yapısının analizi. Üretim planının optimizasyonu. Simpleks yöntemini kullanarak problemin çözümü. Çok kanallı kuyruk sistemi.

test, eklendi 05/02/2012


Simpleks yöntemini kullanarak doğrusal programlama problemini çözme: problemin ifade edilmesi, ekonomik ve matematiksel bir modelin oluşturulması. Potansiyel yöntemi kullanarak ulaştırma problemini çözmek: ilk referans planının oluşturulması, optimal değerinin belirlenmesi.

test, 04/11/2012 eklendi


Doğrusal olmayan programlama probleminin ifadesi. Durağan noktaların ve türlerinin belirlenmesi. Seviye çizgilerinin oluşturulması, amaç fonksiyonu ve kısıtların üç boyutlu grafiği. Sorunun grafik ve analitik çözümü. Kullanım kılavuzu ve algoritma diyagramı.

kurs çalışması, eklendi 12/17/2012


Doğrusal programlama probleminin çözümünün analizi. Simpleks tabloları kullanan Simpleks yöntemi. LP problemlerinin bilgisayarda modellenmesi ve çözülmesi. Sorunun optimal çözümünün ekonomik yorumu. Ulaştırma probleminin matematiksel formülasyonu.