Tam sayılarda denklemler- Bu cebirsel denklemler iki veya daha fazla bilinmeyen değişken ve tamsayı katsayıları olan. Böyle bir denklemin çözümlerinin tümü, denklemi sağlayan bilinmeyen değişkenlerin tamsayı (bazen doğal veya rasyonel) değer kümeleridir. Bu tür denklemlere aynı zamanda denir diofantÇağımızdan önce bu tür denklemlerin bazı türlerini inceleyen eski Yunan matematikçisinin onuruna.

Diophantine problemlerinin modern formülasyonunu Fransız matematikçiye borçluyuz. Belirsiz denklemleri yalnızca tam sayılarla çözme sorununu Avrupalı ​​​​matematikçilerden önce gündeme getiren oydu. Tamsayılardaki en ünlü denklem Fermat'nın son teoremidir: denklem

tüm doğal n > 2 için sıfırdan farklı rasyonel çözümlere sahip değildir.

Tamsayılardaki denklemlere teorik ilgi oldukça büyüktür, çünkü bu denklemler sayılar teorisindeki birçok problemle yakından ilişkilidir.

1970 yılında Leningradlı matematikçi Yuri Vladimirovich Matiyasevich şunu kanıtladı: genel yöntem Rastgele Diophantine denklemlerinin sonlu sayıda adımda tamsayılarla çözülmesine izin veren, mevcut değildir ve olamaz. Bu nedenle aşağıdakiler için takip edilir farklı şekiller denklemler, kendi çözüm yöntemlerinizi seçin.

Tam sayılarda ve doğal sayılarda denklemleri çözerken kabaca aşağıdaki yöntemler ayırt edilebilir:

seçenekleri sıralamanın yolu;

Öklid algoritmasının uygulanması;

sayıların devam eden (devam eden) kesirler biçiminde temsili;

çarpanlara ayırma;

tamsayılardaki denklemlerin herhangi bir değişkene göre kare (veya başka) olarak çözülmesi;

artık yöntem;

sonsuz iniş yöntemi

Çözümlerle ilgili sorunlar

1. Tamsayılarda x 2 – xy – 2y 2 = 7 denklemini çözün.

Denklemi (x – 2y)(x + y) = 7 formunda yazalım.

x, y tam sayılar olduğundan orijinal denklemin çözümlerini aşağıdaki dört sistemin çözümleri olarak buluyoruz:

1) x – 2y = 7, x + y = 1;

2) x – 2y = 1, x + y = 7;

3) x – 2y = –7, x + y = –1;

4) x – 2y = –1, x + y = –7.

Bu sistemleri çözdükten sonra şu denklemin çözümlerini elde ederiz: (3; –2), (5; 2), (–3; 2) ve (–5; –2).

Cevap: (3; –2), (5; 2), (–3; 2), (–5; –2).

a) 20x + 12y = 2013;

b) 5x + 7y = 19;

c) 201x – 1999y = 12.

a) x ve y'nin herhangi bir tamsayı değeri için Sol Taraf Denklem ikiye bölünüyorsa ve sağ taraf tek sayıysa, denklemin tamsayılarda çözümü yoktur.

Cevap: Çözüm yok.

b) Önce belirli bir çözümü seçelim. İÇİNDE bu durumda, çok basit, örneğin,

x 0 = 1, y 0 = 2.

5x 0 + 7y 0 = 19,

5(x – x 0) + 7(y – y 0) = 0,

5(x – x 0) = –7(y – y 0).

5 ve 7 sayıları aralarında asal olduğundan

x – x 0 = 7k, y – y 0 = –5k.

Yani genel çözüm şudur:

x = 1 + 7k, y = 2 – 5k,

burada k keyfi bir tamsayıdır.

Cevap: (1+7k; 2–5k), burada k bir tam sayıdır.

c) Bu durumda seçim yaparak spesifik bir çözüm bulmak oldukça zordur. 1999 ve 201 sayıları için Öklid algoritmasını kullanalım:

OBEB(1999, 201) = OOB(201, 190) = OOB(190, 11) = OOB(11, 3) = OOB(3, 2) = OOB(2, 1) = 1.

Bu işlemi tersten yazalım:

1 = 2 – 1 = 2 – (3 – 2) = 2 2 – 3 = 2 (11 – 3 3) – 3 = 2 11 – 7 3 = 2 11 – 7(190 – 11 17) =

121 11 – 7 190 = 121(201 – 190) – 7 190 = 121 201 – 128 190 =

121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999.

Bu, (1273, 128) çiftinin 201x – 1999y = 1 denkleminin bir çözümü olduğu anlamına gelir. Daha sonra sayı çifti

x 0 = 1273 12 = 15276, y 0 = 128 12 = 1536

201x – 1999y = 12 denkleminin bir çözümüdür.

Bu denklemin genel çözümü şu şekilde yazılacaktır:

x = 15276 + 1999k, y = 1536 + 201k, burada k bir tam sayıdır,

veya yeniden tasarımdan sonra (15276 = 1283 + 7 1999, 1536 = 129 + 7 201'i kullanıyoruz),

x = 1283 + 1999n, y = 129 + 201n, burada n bir tam sayıdır.

Cevap: (1283+1999n, 129+201n), burada n bir tam sayıdır.

3. Denklemi tam sayılarla çözün:

a) x3 + y3 = 3333333;

b) x 3 + y3 = 4(x 2 y + xy 2 + 1).

a) x 3 ve y 3, 9'a bölündüğünde yalnızca 0, 1 ve 8 kalanlarını verebildiğinden (bölümdeki tabloya bakınız), bu durumda x 3 + y 3 yalnızca 0, 1, 2, 7 ve 8 kalanlarını verebilir. Ancak 3333333 sayısı 9'a bölündüğünde 3 kalanını verir. Dolayısıyla orijinal denklemin tamsayılarda çözümü yoktur.

b) Orijinal denklemi (x + y) 3 = 7(x 2 y + xy 2) + 4 formunda yeniden yazalım. Tamsayıların küpleri 7'ye bölündüğünde 0, 1 ve 6 kalanlarını verdiğinden ancak 4 vermediğinden, o zaman Denklemin tam sayı çözümleri yoktur.

Cevap: Tamsayı çözüm yoktur.

a) asal sayılarda x 2 – 7x – 144 = y 2 – 25y denklemi;

b) tam sayılarda x + y = x 2 – xy + y 2 denklemi.

a) Bu denklemi y değişkenine göre ikinci dereceden denklem olarak çözelim. Aldık

y = x + 9 veya y = 16 – x.

Tek x için x + 9 sayısı çift olduğundan, ilk eşitliği sağlayan tek asal sayı çifti (2; 11)'dir.

X, y basit olduğundan, y = 16 – x eşitliğinden elde ederiz

2 x 16,2 en 16.

Seçenekleri araştırarak kalan çözümleri buluruz: (3; 13), (5; 11), (11; 5), (13; 3).

Cevap: (2; 11), (3; 13), (5; 11), (11; 5), (13; 3).

b) Bu denklemi x için ikinci dereceden bir denklem olarak düşünün:

x 2 – (y + 1)x + y 2 – y = 0.

Bu denklemin diskriminantı –3y 2 + 6y + 1'dir. Yalnızca aşağıdaki y değerleri için pozitiftir: 0, 1, 2. Bu değerlerin her biri için, orijinal denklemden x için ikinci dereceden bir denklem elde ederiz. , kolayca çözülebilir.

Cevap: (0; 0), (0; 1), (1; 0), (1; 2), (2; 1), (2; 2).

5. Var mı sonsuz sayı x 2 + y 2 + z 2 = x 3 + y 3 + z 3 olacak şekilde x, y, z tamsayılarının üçlüsü?

y = –z olan üçlüleri seçmeye çalışalım. O zaman y 3 ve z 3 her zaman birbirini götürecektir ve denklemimiz şöyle görünecektir:

x 2 + 2y 2 = x 3

ya da,

x 2 (x–1) = 2y 2 .

Bir (x; y) tam sayı çiftinin bu koşulu sağlaması için x-1 sayısının tam sayının karesinin iki katı olması yeterlidir. Böyle sonsuz sayıda sayı vardır, yani bunların hepsi 2n 2 +1 formundaki sayılardır. Bu sayıyı x 2 (x–1) = 2y 2 olarak değiştirerek basit dönüşümlerden sonra şunu elde ederiz:

y = xn = n(2n 2 +1) = 2n 3 +n.

Bu şekilde elde edilen tüm üçlüler (2n 2 +1; 2n 3 +n; –2n 3 – n) formundadır.

Cevap: var.

6. x 2 + y 2 + z 2 + u 2 = 2xyzu olacak şekilde x, y, z, u tam sayılarını bulun.

X 2 + y 2 + z 2 + u 2 sayısı çifttir, dolayısıyla x, y, z, u sayıları arasında çift sayıda tek sayı vardır.

Dört sayının tümü x, y, z, u tek ise, o zaman x 2 + y 2 + z 2 + u 2 4'e bölünebilir, ancak 2xyzu 4'e bölünemez - bu bir tutarsızlıktır.

Eğer x, y, z, u sayılarından tam olarak ikisi tekse, o zaman x 2 + y 2 + z 2 + u 2 4'e bölünemez, ancak 2xyzu 4'e bölünebilir - yine bir tutarsızlık.

Bu nedenle tüm x, y, z, u sayıları çifttir. O zaman şunu yazabiliriz

x = 2x 1 , y = 2y 1 , z = 2z 1 , u = 2u 1 ,

ve orijinal denklem şu şekli alacaktır

x 1 2 + y 1 2 + z 1 2 + sen 1 2 = 8x 1 y 1 z 1 sen 1 .

Şimdi (2k + 1) 2 = 4k(k + 1) + 1'in 8'e bölündüğünde 1 kalanını verdiğine dikkat edin. Bu nedenle, eğer tüm x 1 , y 1 , z 1 , u 1 sayıları tek ise, o zaman x 1 2 + y 1 2 + z 1 2 + u 1 2, 8'e bölünemez. Ve eğer bu sayılardan tam olarak ikisi tekse, o zaman x 1 2 + y 1 2 + z 1 2 + u 1 2, 8'e bölünemez. 4. Bu şu anlama gelir:

x 1 = 2x 2, y 1 = 2y 2, z 1 = 2z 2, u 1 = 2u 2,

ve denklemi elde ederiz

x 2 2 + y 2 2 + z 2 2 + sen 2 2 = 32x 2 y 2 z 2 sen 2 .

Aynı mantığı bir kez daha tekrarlarsak, x, y, z, u'nun tüm doğal n'ler için 2 n'ye bölünebildiğini buluruz; bu yalnızca x = y = z = u = 0 için mümkündür.

Cevap: (0; 0; 0; 0).

7. Denklemin olduğunu kanıtlayın

(x – y) 3 + (y – z) 3 + (z – x) 3 = 30

tamsayılarda çözümü yoktur.

Aşağıdaki kimliği kullanalım:

(x – y) 3 + (y – z) 3 + (z – x) 3 = 3(x – y)(y – z)(z – x).

O zaman orijinal denklem şu şekilde yazılabilir:

(x – y)(y – z)(z – x) = 10.

a = x – y, b = y – z, c = z – x şeklinde gösterelim ve elde edilen eşitliği formda yazalım.

Ayrıca a + b + c = 0 olduğu açıktır. Permütasyona kadar abc = 10 eşitliğinin |a|, |b|, |c| sayılarına işaret ettiğini doğrulamak kolaydır. 1, 2, 5 veya 1, 1, 10'a eşittir. Ancak tüm bu durumlarda, a, b, c işaretlerinin herhangi bir seçimi için a + b + c toplamı sıfır değildir. Dolayısıyla orijinal denklemin tamsayı çözümleri yoktur.

8. Denklem 1'i tam sayılarla çözün! + 2! + . . . +x! = y 2 .

Açıkça görülüyor ki

eğer x = 1 ise y 2 = 1,

x = 3 ise y 2 = 9 olur.

Bu vakalar aşağıdakilere karşılık gelir: sonraki çiftler sayılar:

x1 = 1, y1 = 1;

x2 = 1, y2 = –1;

x3 = 3, y3 = 3;

x4 = 3, y4 = –3.

X = 2 için 1'e sahip olduğumuzu unutmayın! + 2! = 3, x = 4 için 1 var! + 2! +3! + 4! = 33 ve ne 3 ne de 33 tamsayıların karesi değil. Eğer x > 5 ise, o zaman

5! + 6! + . . . +x! = 10n,

bunu yazabiliriz

1! + 2! +3! + 4! + 5! + . . . +x! = 33 + 10n.

33 + 10n, sonu 3 ile biten bir sayı olduğundan bir tam sayının karesi değildir.

Cevap: (1; 1), (1; –1), (3; 3), (3; –3).

9. Doğal sayılarda aşağıdaki denklem sistemini çözün:

a 3 – b 3 – c 3 = 3abc, a 2 = 2(b + c).

3abc > 0 ise a 3 > b3 + c3;

böylece elimizde

Bu eşitsizlikleri topladığımızda şunu elde ederiz:

Son eşitsizliği dikkate alarak sistemin ikinci denkleminden şunu elde ederiz:

Ancak sistemin ikinci denklemi de a'nın çift sayı olduğunu gösteriyor. Böylece a = 2, b = c = 1 olur.

Cevap: (2; 1; 1)

10. x 2 + x = y 4 + y 3 + y 2 + y denklemini sağlayan tüm x ve y tam sayı çiftlerini bulun.

Bu denklemin her iki tarafını da çarpanlarına ayırdığımızda şunu elde ederiz:

x(x + 1) = y(y + 1)(y 2 + 1),

x(x + 1) = (y 2 + y)(y 2 + 1)

Böyle bir eşitlik, sol ve sağ tarafların sıfıra eşit olması veya ardışık iki tam sayının çarpımı olması durumunda mümkündür. Bu nedenle, belirli faktörleri sıfıra eşitleyerek 4 çift istenen değişken değeri elde ederiz:

x1 = 0, y1 = 0;

x2 = 0, y2 = –1;

x3 = –1, y3 = 0;

x4 = –1, y4 = –1.

(y 2 + y)(y 2 + 1) çarpımı, yalnızca y = 2 olduğunda ardışık sıfır olmayan iki tam sayının çarpımı olarak düşünülebilir. Dolayısıyla x(x + 1) = 30, dolayısıyla x 5 = 5, x 6 = –6. Bu, orijinal denklemi sağlayan iki tam sayı çiftinin daha olduğu anlamına gelir:

x5 = 5, y5 = 2;

x 6 = –6, y 6 = 2.

Cevap: (0; 0), (0; –1), (–1; 0), (–1; –1), (5; 2), (–6; 2.)

Çözümü olmayan sorunlar

1. Denklemi tam sayılarla çözün:

a) xy = x + y + 3;

b) x 2 + y 2 = x + y + 2.

2. Denklemi tam sayılarla çözün:

a) x 3 + 21y 2 + 5 = 0;

b) 15x 2 – 7y 2 = 9.

3. Denklemi doğal sayılarla çözün:

a) 2 x + 1 = y2;

b) 3 2 x + 1 = y 2.

4. Rasyonel sayılarda x 3 + 3y 3 + 9z 3 = 9xyz denkleminin tek bir çözümü olduğunu kanıtlayın

5. Tam sayılarda x 2 + 5 = y 3 denkleminin çözümü olmadığını kanıtlayın.

Genellikle görevlerde doğrusal programlama Plan koordinatlarının tam sayı olması zorunlu değildir. Ancak pratikte optimal planların koordinatlarının tamsayı olması gerektiği problemlerle sıklıkla karşılaşılır ve bu tür problemlere problem denir. . Doğrusal programlama problemlerini grafiksel yöntem ve simpleks yöntemi kullanarak çözerken, optimal planın koordinatlarının tamsayı olacağının garantisi yoktur.

Bazı durumlarda sonuçlar yuvarlanabilir. Örneğin, eğer optimal plan 499683.3 arabanın üretilmesini şart koşuyorsa, o zaman sonucu 499683'e, hatta 500000'e yuvarlamak ekonomik olarak haklıdır.

Ancak bu tür yuvarlamanın büyük hata yaratabileceği sorunlar da vardır. Örneğin, optimal plan 0,67 tesisin inşa edilmesini şart koşuyorsa, o zaman resmi olarak 0 veya 1'e yuvarlama kabul edilemez.

Bu nedenle harika pratik önemi Koordinatları tam sayı olan en uygun planı bulabileceğiniz doğrusal programlama problemlerini çözmek için yöntemleriniz var. Görevler Tamsayılı programlama tam olarak bu yöntemler kullanılarak çözülür.

Eğer tamsayı programlama problemi yerleştirmek kanonik form aşağıdaki gibi formüle edilir:

amaç fonksiyonunun maksimumunu bulun (doğrusal form)

kısıtlama sistemi altında

Böylece görev Tamsayılı programlama ve buna karşılık gelen doğrusal programlama problemi yalnızca bilinmeyenlerin tam sayı olması durumunda farklılık gösterir.

Doğrusal programlama problemlerinde olduğu gibi, tamsayılı programlama problemleri de optimal planın amaç fonksiyonunu maksimuma çıkarmasını gerektirir ( doğrusal form).

Tamsayılı programlama problemlerini çözmek için Gomori yöntemi

Gomori yöntemi dır-dir evrensel yöntem tamsayılı programlama problemlerini çözme, bunun yardımıyla sınırlı sayıda yinelemeden sonra en uygun planı bulabilir veya problemin hiçbir çözümü olmadığından emin olabilirsiniz. Ancak Gomori yönteminin pratik değeri çok sınırlıdır çünkü problem çözerken çok fazla yineleme yapılması gerekir.

Gomori yöntemini kullanarak tamsayı programlama problemlerini çözerken, tamsayı planları içermeyen alt kümeler, bir doğrusal programlama problemi için optimal planlar kümesinden kademeli olarak çıkarılır.

İlk yinelemede, doğrusal programlama problemini simpleks yöntemini kullanarak çözmeniz gerekir. Eğer bulunan bilinmeyenler tam sayı şartını sağlıyorsa tamsayı programlama problemi çözülür. Bilinmeyen bilinmeyenlerden en az biri kesirli sayı ise, o zaman biri oluşturulmalıdır ek koşul(nasıl oluşturulacağı - daha fazlası aşağıda) ve onu tamsayı programlama probleminin kısıtlama sistemine ekleyin. Böylece plan kümesinden tamsayı plan içermeyen alt küme çıkarılır. Bu şekilde genişletilmiş problemin optimal planı tamsayı ise tamsayılı programlama problemi çözülür. Çözüm süreci, bir iterasyonda bir tamsayı optimal planı bulunana veya problemin bir çözümü olmadığı doğrulanıncaya kadar devam eder.

Şimdi söz konusu ek koşulun nasıl oluşturulacağından bahsedelim. Ek bir koşul, aşağıdaki formüle göre bilinmeyenlerin ve bilinmeyenlerin katsayılarından kısıtlama sisteminin denklemlerinden birinden elde edilir.

, nerede kıvırcık parantez- sırasıyla serbest terimin kesirli kısımları ve bilinmeyenlerin katsayıları.

Örneğin, tek taraflı masa aşağıdaki denklemi elde ederiz:

.

Serbest terimin kesirli kısmını, tamsayı kısmını sayıdan çıkararak şu şekilde elde ederiz:

Benzer şekilde bilinmeyenler için katsayıların kesirli kısımlarını elde ederiz:

(saatte X3 ),

(saatte X4 ).

A Genel kural Kesirli parçaların bulunması şu şekildedir: Bütün parça gerçek Numara A En büyük tam sayıya [ denir A] , aşırı değil A; reel sayının kesirli kısmı A fark denir {A} = A - [A] sayının kendisi A ve tamamı [ A] .

.

Örneğimizde yukarıdaki formülü kullanarak aşağıdaki denklem elde edilir:

.

Örnek 1. Aşağıdaki tamsayı programlama problemini Gomori yöntemini kullanarak çözün. Maksimumu bul amaç fonksiyonu

kısıtlama sistemi altında

Çözüm. Simpleks yöntemini kullanarak sorunu çözüyoruz. sahip olduğumuzdan beri simpleks yöntemini kullanarak doğrusal programlama problemlerini çözme dersi Burada yöntemin kendisi anlatılmayacak, sadece simpleks tablolar verilecektir.

Ek bilinmeyenler X3 Ve X4 Bunu temel olarak kabul edelim. Temel bilinmeyenleri ve amaç fonksiyonunu temel olmayan değişkenler cinsinden ifade edelim:

Katsayılardan simpleks bir tablo oluşturalım:

En uygun planı elde edene kadar aşağıdaki tabloları derliyoruz:

Tablo 3
Temel bilinmeyenler	Ücretsiz üyeler	Ücretsiz bilinmeyenler		Yardımcı katsayılar
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
İLE	65/7	10/7	1/7	1/2

Tablo 3'ten en uygun planı buluyoruz . Bu optimal plan tamsayı koşulunu sağlamadığından ek bir koşul yaratmamız gerekir. Kesirli kısım koordinatlar bir sayıdır ve bir koordinatın kesirli kısmı bir sayıdır.

Tabloya dayalı ilk denklem şu şekilde yazılacaktır:

.

Bilinmeyenler ve serbest terimler için katsayıların kesirli kısımlarını belirledikten sonra aşağıdaki ek koşulu elde ederiz:

veya ek bir değişken ekleyerek,

.

Aldık Yeni hat Tablo 3'ten elde edilen simpleks tabloda ve yeni elde edilen denklemden katsayıların eklenmesiyle:

Tablo 4
Temel bilinmeyenler	Ücretsiz üyeler	Ücretsiz bilinmeyenler		Yardımcı katsayılar
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
X5	-5/7	-4/7	-6/7
İLE	65/7	10/7	1/7	1/2

Simpleks yöntemi adımını tamamlayıp tabloyu elde ediyoruz:

Tablo 5
Temel bilinmeyenler	Ücretsiz üyeler	Ücretsiz bilinmeyenler		Yardımcı katsayılar
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
İLE	55/6	4/3	1/6	-1/7

En uygun planı aldık . Bu plan, önceki plan gibi, tamsayı koşulunu karşılamıyor. Bu nedenle yine ek bir koşul aranmaktadır. Bu durumda birinci veya üçüncü denklemi kullanabilirsiniz. Aşağıdaki ek koşulu elde ederiz:

.

Aşağıdaki tabloyu oluşturalım:

Tablo 6
Temel bilinmeyenler	Ücretsiz üyeler	Ücretsiz bilinmeyenler		Yardımcı katsayılar
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
X6	-5/6	-2/3	-5/6
İLE	55/6	4/3	1/6	-1/7

Optimum plan aşağıdaki final tablosundan elde ederiz:

Tablo 7
Temel bilinmeyenler	Ücretsiz üyeler	Ücretsiz bilinmeyenler		Yardımcı katsayılar
		X3	X6
X1	3	4/5	-1/5	1/6
X2	0	-3/5	2/5	-1/3
X4	2	8/5	-7/5	7/6
X5	1	4/5	-6/5
İLE	9	6/5	1/5	-1/6

Bulunan optimal plan tamsayı koşulunu sağladığından tamsayı programlama problemi çözülmüştür. Koordinatlar X5 Ve X6 Problemin başlangıç ​​koşulları yalnızca dört bilinmeyen içerdiğinden göz ardı edilebilir. Bu nedenle nihai optimal plan şu şekilde yazılacaktır:

,

ve amaç fonksiyonunun maksimumu 9'dur.

Tamsayılı programlama problemlerini çözmek için dal ve sınır yöntemi

Dal ve sınır yöntemi, bilinmeyenlerin sayısının az olduğu veya tamsayı gereksinimlerinin tüm bilinmeyenlere uygulanmadığı tamsayı programlama problemlerinin çözümü için uygundur. Dal ve sınır yönteminin özü, tamsayı şartının geçerli olduğu bilinmeyenler için, bu bilinmeyenlerin değerlerinin içinde bulunabileceği sınırların belirlenmesinin gerekli olmasıdır. Daha sonra karşılık gelen doğrusal programlama problemleri çözülür.

Bir tamsayılı programlama probleminde bilinmeyenlerin değerlerinin içinde bulunması gereken sınırların belirtilmesi şu şekilde yazılabilir:

Pratikte pek çok durumda bilinmeyen değerlerin sınırları tamsayılı programlama probleminin kısıtlar sistemine zaten dahil edilmiştir veya problemin ekonomik içeriğine göre belirlenebilmektedir. Aksi halde alt sınırın ve üst sınırın olduğunu varsayabiliriz; burada M- oldukça büyük bir pozitif sayı.

Dal ve sınır yöntemi, bilinmeyenlerin kabul edilebilir değerlerinin sınırlarının netleştirilmesine nasıl yardımcı olur?

İlk olarak, bir tamsayılı programlama problemine karşılık gelen bir doğrusal programlama problemi, örneğin simpleks yöntemi kullanılarak çözülür. Bu problemdeki en uygun plan bulunsun ve koordinatlarından herhangi birinin değeri şöyle olsun: kesirli bir sayı. O zaman iki yeni doğrusal programlama problemi oluşturmanız gerekecek. Nasıl yapılır?

Koordinatın tamsayı kısmını olarak gösterelim. Yeni doğrusal programlama problemlerinden birinde koordinat değerinin alt sınırı sayı yani koordinat değerinin tamsayı kısmının bir artırılmış hali olacaktır. Aşağıdaki gibi yazılacaktır:

.

Başka bir yeni doğrusal programlama probleminde üst sınır koordinat değeri, koordinat değerinin tamsayı kısmı olacaktır. Bu şekilde yazılacaktır:

Böylece, bir bilinmeyenin izin verilen değerlerinin sınırlarının değiştiği ilk doğrusal programlama probleminden iki yeni problem “dallara ayrıldı”. Bu sorunların her birini çözerken üç durum mümkündür:

• optimal plan bir tamsayı değil,
• optimal plan tam sayıdır,
• sorunun çözümü yok.

Yalnızca ilk durumda yeni görevleri yukarıda gösterilen şekilde "dallara ayırmak" mümkündür. İkinci ve üçüncü durumlarda “dallanma” durur.

Tamsayılı programlama probleminin her çözümünde bir problem çözülür. Şimdi kavramı tanıtalım: çözülmesi gereken doğrusal programlama problemlerinin bir listesi. Listeden ilgili yinelemede çözülecek sorunu seçin. Daha sonraki yinelemelerde, çözülen sorunlar artık listeye dahil edilmediğinden liste değişir ve bunların yerine önceki görevlerden "dallanan" yeni görevler listeye dahil edilir.

“Dallanmayı” sınırlandırmak, yani çözülmesi gereken problem sayısını azaltmak için her yinelemede alt sınırın belirlenmesi gerekir. maksimum değer hedef işlevi. Bu şu şekilde yapılır:

Dal ve sınır yöntemini kullanarak bir tamsayı programlama problemini çözmeye yönelik algoritmaya göre, her birinde P Bu yineleme 4 adım gerektirir.

Örnek 2. Aşağıdaki tamsayı programlama problemini dal ve sınır yöntemini kullanarak çözün. Amaç fonksiyonunun maksimumunu bulun

kısıtlama sistemi altında

Çözüm. Bilinmeyenlerin optimal değerlerinin aşağıdaki sınırlarının verildiğini veya belirlendiğini varsayalım:

.

Görev verildiği için normal biçim tamsayı bir tasarıma ve amaç fonksiyonunun maksimum değeri üzerinde bir alt sınıra sahiptir.

Çözülmesi gereken görevlerin listesi 1. görevi içerir:

Yineleme 1.

Aşama 1. Kullanarak simpleks yöntemi 1. sorunun çözümü elde edildi:

Bulunan plan tamsayı olmadığı için 4. adım takip eder.

Adım 4. Optimal planın kesirli koordinatı 1,2 olduğundan, o zaman . 1. problemin bilinmeyen değerlerine sınırları uygulayarak yeni problemler elde ederiz. 2. problemde alt sınır , 3. problemde ise üst sınır dır.

giriiş

2.2 Tamsayılı programlama problemini çözmeye bir örnek

3. Parametrik programlama

3.1 Amaç fonksiyonundaki bir parametreyle ilgili sorun

3.2 Kısıtlama sisteminin serbest terimlerindeki bir parametreyle ilgili sorun

3.3 Problem, amaç fonksiyonu ve sağ kısım parametrenin içerdiği kısıtlamalar

4. Tam Sayılı Parametrik Programlama

4.1 Amaç fonksiyonundaki bir parametreyle tamsayı programlama problemini çözmeye bir örnek

4.2 Kısıtlama sisteminin serbest terimlerindeki bir parametreyle tamsayı programlama problemini çözmeye bir örnek

Çözüm

Kaynakça

giriiş

Matematiksel programlama ekstrem problemlerin incelenmesi ve bunları çözmek için yöntemlerin geliştirilmesiyle ilgilenen bir matematik disiplinidir.

İÇİNDE Genel görünüm ekstrem problemin matematiksel formülasyonu, amaç fonksiyonunun en büyük veya en küçük değerinin belirlenmesinden oluşur

koşullar altında ve – belirtilen işlevler ve bazı gerçek sayılardır.

Fonksiyonların özelliklerine bağlı olarak

ve matematiksel programlama, belirli problem sınıflarının çözümüne yönelik yöntemlerin incelenmesi ve geliştirilmesiyle ilgilenen bir dizi bağımsız disiplin olarak düşünülebilir.

Öncelikle matematiksel programlama problemleri doğrusal ve doğrusal olmayan programlama problemleri olarak ikiye ayrılır. Ayrıca, eğer tüm işlevler

ve doğrusalsa, karşılık gelen problem bir doğrusal programlama problemidir. Eğer en az biri belirtilen işlevler doğrusal değilse, karşılık gelen problem doğrusal olmayan bir programlama problemidir.

Matematiksel programlamanın en çok çalışılan dalı doğrusal programlamadır. Doğrusal programlama problemlerini çözmek için geliştirilmiştir. bütün çizgi etkili yöntemler, algoritmalar ve programlar.

Matematiksel programlama problemlerinin ayrı sınıfları tamsayılı, parametrik ve kesirli doğrusal programlama problemleridir.

Bu çalışmanın ilk bölümünde doğrusal programlamanın temel kavramları incelenmektedir.

İkinci bölümde bir tamsayılı programlama problemi formüle edilmiş ve çözüm yöntemleri ele alınmıştır. Bir tamsayılı programlama probleminin çözümüne bir örnek verilmiştir.

Üçüncü bölümde görevler tartışılıyor parametrik programlama ve örnekler çözüm yöntemlerini göstermektedir çeşitli görevler bu tip.

Dördüncü bölümde tamsayılı parametrik programlamanın problemleri formüle edilmiş ve incelenmiştir. Amaç fonksiyonundaki bir parametre ile tamsayılı parametrik programlama problemi bağımsız olarak iki şekilde çözüldü. Bu problemin çözümüne göre bu tip problemlerin çözümüne yönelik bir yöntem belirlenir. Kısıtlama sisteminin serbest terimlerindeki bir parametreye sahip bir tamsayı programlama problemi de çözülmüştür.

Diplomayı yazarken aşağıdaki referans literatürü kullanıldı: Kuznetsov Yu.N., Kuzubov V.I., Voloshchenko A.B. Matematiksel programlama, Ashmanov S.A. Doğrusal programlama. V.I. Kopylov'un kitaplarından bazı örnekler alınmıştır. Dersler ve pratik dersler matematiksel programlamada Akulich I.L. Örneklerde ve problemlerde matematiksel programlama. Bana göre tamsayılı ve parametrik programlama problemlerini çözme yöntemlerine yönelik algoritmalar, I.L. Akulich'in kitabında en erişilebilir ve eksiksizdir.

1. Doğrusal programlamanın temel kavramları

Farklı kısıtlama türlerine bağlı olarak doğrusal programlama problemlerinin üç ana biçimi vardır.

Standart görev

(1.1) (1.2)

Matris formunda problem (1.1) - (1.2) şu şekildedir:

- katsayılar matrisi. Bir vektöre doğrusal formun katsayılarının vektörü, bir vektöre kısıtlamaların vektörü denir.

Kanonik sorun Doğrusal programlama şu şekildedir:

veya matris formunda:

Genel görev Doğrusal programlama - bazı kısıtlamalar eşitsizlikler şeklinde, bazıları ise denklemler şeklinde ifade edilir. Ayrıca negatif olmama koşulu tüm değişkenler için geçerli değildir:

Teorem. Standart, kanonik ve genel görevler Doğrusal programlama eşdeğerdir.

Yorum. Durum ne zaman standart görev Doğrusal bir formu en aza indirmek gerekir, maksimum için kolayca bir probleme indirgenebilir - problemi bir fonksiyonun maksimumu için düşünmeliyiz

orijinal problemdeki gibi değişkenler üzerindeki aynı kısıtlamalar altındadır.

2. Tamsayı programlama

Doğrusal programlama problemleriyle ilgili ekonomik problemlerin önemli bir kısmı tamsayılı çözüm gerektirmektedir. Bunlar, değişkenlerin bölünemez ürünlerin birim sayısı anlamına geldiği görevleri içerir; örneğin, üretim görevlerinin işletmeler arasındaki dağıtımı, kesme malzemeleri, yükleme ekipmanı, gemilerin hatlar boyunca dağıtımı, uçuşlar arasında uçakların yanı sıra, bölünmez ürünlerin üretimi. Bir birim toplam üretimin küçük bir bölümünü temsil ediyorsa, o zaman en uygun çözüm sıradan bul simpleks yöntemi, problemin anlamına bağlı olarak onu tam birimlere yuvarlıyoruz. Aksi takdirde yuvarlama, optimal tamsayı çözümünden uzak bir çözümle sonuçlanabilir.

2.1 Sorun bildirimi ve çözüm yöntemleri

Tamsayılı programlama problemi doğrusal programlama problemiyle aynı şekilde formüle edilir ancak aşağıdakileri içerir: ek gereksinim Optimal çözümü oluşturan değişkenlerin değerlerinin negatif olmayan tamsayılar olması gerçeğinden oluşur.

Bulmak gerek Minimum değer doğrusal fonksiyon

(2.1.1)

kısıtlamalar altında

(2.1.2) (2.1.3)
- tüm. (2.1.4)

Doğrusal programlama probleminin Şekil 2.1'de gösterilen çokyüzlü çözümlere sahip olduğunu varsayalım. Tamsayı gerekliliğini uygularsak, bu tür bir problemin kabul edilebilir çözüm kümesi, izole edilmiş tamsayı noktalarının bir koleksiyonudur ve

dışbükeydir. Dış tamsayı noktalarını bağlayan yeni kısıtlamalar eklersek ve ardından koordinat eksenleri ile sınırlanan tüm dışbükey kümeyi ve yeni konturu bir çözüm çokyüzlü olarak kullanırsak, şunu elde ederiz: Yeni görev Aşağıdaki özelliklere sahip doğrusal programlama:

1) yeni çözüm çokyüzlü, orijinal çözüm çokyüzlünün içerdiği tüm tamsayı noktalarını içerir; köşe noktalarından herhangi biri tam sayıdır;

2) beri doğrusal fonksiyonçözüm polihedronun köşe noktasında optimuma ulaşırsa, böyle bir polihedronun yapısı optimal çözümün bütünlüğünü sağlar.

Simpleks yöntemini kullanarak (2.1.1)-(2.1.4) problemine bir çözüm bulursanız, o zaman tamsayı olabilir veya olmayabilir (çözümünün her zaman tamsayı olduğu doğrusal programlama problemine bir örnek) , dır-dir ulaşım sorunu). Genel durumda, (2.1.1)-(2.1.4) problemine yönelik optimal planı belirlemek için özel yöntemler gereklidir. Şu anda, en ünlüsü Gomori yöntemi olan bu tür birkaç yöntem vardır.

Gomori yöntemi. Gomori tarafından önerilen problemin çözümüne yönelik yöntem, simpleks yöntemine dayanmaktadır ve aşağıdakilerden oluşur. Simpleks yöntemi, tamsayı koşulunu dikkate almadan problem için en uygun planı bulmak için kullanılır. Optimum plan tamsayı ise hesaplamalar tamamlanır, ancak optimal plan en az bir kesirli bileşen içeriyorsa

Daha sonra plan bileşenlerinin tamsayı yapısını dikkate alan ek bir kısıtlama getirilir ve simpleks yöntemi kullanılarak yapılan hesaplamalara yeni bir optimal plan elde edilene kadar devam edilir. Aynı zamanda tam sayı değilse tamsayı dikkate alınarak aşağıdaki kısıtlama yapılır. Ek kısıtlamaların eklenmesi işlemi, bir tamsayı optimal planı bulunana veya problemin tamsayı planlara sahip olmadığı kanıtlanana kadar tekrarlanır. Bu durum, bir kesir için bu satırdaki her şeyin tamsayı olduğu ortaya çıkarsa meydana gelir.

6 cevap

Bu örneği takip edin: denklemlerin şöyle olduğunu varsayalım:

7 = x + 3y + 4z + 9w 12 = 4x + 2y + 3z + 7w

2 denklem ve 4 bilinmeyen var. Bilinmeyenlerden 2 tanesini parametre olarak ayarlayabilirsiniz, böylece sistemde bilinmeyenlerin sayısı kadar denklem bulunur:

7 - (4z + 9w) = x + 3y 12 - (3z + 7w) = 4x + 2y

Bilinmeyen olarak x ve y'yi kullanacağız. Çözülebilir ve doğrusal çözümde w ve z parametre olarak bırakılabilir:

X = (22 - 3w - z)/10 y = (16 - 29w - 13z)/10

Şimdi payları payda olan 10'a bölünebilir hale getirmeniz gerekiyor. Çözüm varsa 1'den 10'a kadar tüm parametreleri kontrol edebilirsiniz.

Genel olarak şunu yaparsınız:

• Parametreleri denklem sayısı kadar bilinmeyen olacak şekilde seçin. Determinant için en küçük mutlak değeri üreten bilinmeyenleri bırakmaya çalışın (örnekte 10'du, ancak |det|=3 olacağından y ve z'yi seçmek daha iyi olurdu)
• Karar vermek doğrusal sistem ve parametrelere bağlı olarak bir yanıt oluşturun
• 1'den det'in mutlak değerine kadar olan parametre değerlerini kontrol edin (eğer bir çözüm varsa o noktada bulursunuz) tüm bilinmeyenler için tamsayı bir çözüm bulunana kadar (bu yüzden önce en küçük determinant değerini seçersiniz) ve pozitif olup olmadığını kontrol edin (örnekte gösterilmemiştir).

Eğer kaba kuvvet kullandıysa özür dilerim son adım ancak en azından test aralığını en aza indirmek mümkündür. Belki En iyi yol Diophantine denklemlerinin son sistemini çözüyorum ama herhangi bir yöntem bilmiyorum.

DÜZENLEME1

Son kısımda kaba zorlamayı önlemenin bir yöntemi var. Yine örnekte yapmanız gerekenler:

22 = 3w + z (uyumlu, mod 10) 16 = 29w + 13z (uyumlu, mod 10)

Modülün uygulanması:

2 = 3w + z (uyumlu, mod 10) 6 = 9w + 3z (uyumlu, mod 10)

Eşliği ters modulo 10 ile çarpıp diğerlerini toplayarak eşlik sistemini üçgen (Gauss eliminasyonu) yapabilirsiniz. 9 modulo 10'un tersi -1 olduğundan son uyumu çarpıyoruz:

2 = 3w + z (uyumlu, mod 10) -6 = -9w + -3z (uyumlu, mod 10)

Eş değer:

2 = 3w + z (uyumlu, mod 10) 4 = w + 7z (uyumlu, mod 10)

Daha sonra -3 ile çarpın ve ilkine ekleyin:

2 - 3*4 = 3w + z -3w - 21z (uyumlu, mod 10) 4 = w + 7z (uyumlu, mod 10)

Eş değer:

10 = -20z (uyumlu, mod 10) 4 = w + 7z (uyumlu, mod 10)

Daha sonra yukarıdan aşağıya doğru çözersiniz (bu örnek z'nin herhangi bir değeri için doğru gibi görünmektedir). Eşliklerden daha fazla parametreniz varsa bir miktar özgürlük olabilir, ancak bunlar eşdeğerdir ve fazlalık parametreleri tercihen herhangi bir değere ayarlayabilirsiniz. en küçük değer, 1'e eşit.

Açık olmayan başka bir şey varsa bana bildirin!

Sorunu doğru anladıysam, her biri farklı posta ücreti olan birden fazla paketiniz var. Bu posta ücretini elinizdeki pul havuzundan ödemek istiyorsunuz. Sorunu tüm programlamayla çözebilirsiniz. Aşağıdaki çözüm tüm paketler için aynı anda çözüm sağlar. numPackages * numStampDenominations'a eşit sayıda değişkene sahip olacaksınız (muhtemelen büyük miktar paketleri).

Eşitlik kısıtı Aeqx = beq gibi görünür. Dört markalı (numVarsnumPackages) iki paket için Aeq matrisi şuna benzer:

21 .68 .47 .01 .00 .00 .00 .00 .89 * x = .00 .00 .00 .00 .21 .68 .47 .01 .50

İlk satır 1. grup için kısıtlama katsayılarıdır (damga değerleri). Sıfır olmayan katsayılar damga değerleridir. Diğer paketlerle ilişkili null değişkenine dikkat edilmez.

İkinci kısıtlama grubu (eşitsizlik) sahip olduğum marka havuzuyla ilgilidir. Eşitsizlik kısıtı A * x = b gibi görünür. 4 damga ve 8 değişken (numPackages * numStampDenominations) için Matris A şuna benzer:

1 0 0 0 1 0 0 0 10 0 1 0 0 0 1 0 0 10 * x<= 0 0 1 0 0 0 1 0 10 0 0 0 1 0 0 0 1 20

Maliyet fonksiyonu, toplam kalıp sayısını temsil eden f"*x'tir. Katsayıları, sütun vektörü olarak belirtilen basit birimlerdir.

Matlab'da sorunu anlatılan şekilde çözen bir komut dosyası bulunmaktadır. Muhtemelen Matlab'a benzer şekilde GNU'nun sunduğu oktavlarla aynı şekilde formüle edilecektir. Matlab veya Octave sizin için doğru çözüm olmayabilir ama en azından size neyin işe yaradığını söylerler ve çözüm geliştirebilmeniz için size bir sanal alan sunarlar.

% 4x1 matris olarak mevcut olan her damganın değeri sv = [.21; 0,68; 0,47; 0,01]; % 4x1 matris olarak mevcut olan her damganın sayısı sq = ; % Gösterim sayısı m = size(sv, 1); % Her paket için 4x1 matris olarak gereken posta ücreti % -- muhtemelen bir dosya posta ücretinden okunmuştur = [.89;.50;1.01;.47;.47]; % Paket sayısı -- yalnızca posta ücreti satırlarının sayısı packageCount = size(postage, 1); % Değişken sayısı m*packageCount numVar = m*packageCount; % alt sınır -- belirli bir değerin sıfır damgaları lb = sıfırlar(numVar,1); % üst sınır - üst sınır için kısıtlamaları kullanın ub =; % Maliyet fonksiyonu -- kullanılan damga sayısını en aza indirin % min(f"*x) f = birler(numVar,1); % tamsayı kısıtlamaları intcon = 1:numVar; % Posta ücreti kısıtlama matrisini oluştur Aeq = sıfırlar(numVar, packageCount ); for i = 1:packageCount ilk = i*m - 3; son = ilk + 3; Aeq(ilk:son,i) = sv(:); end % Damga sayısı kısıtlama matrisini oluştur A = sıfırlar(numVar, m ); r = 1:m için j = 1:m için c = (j-1)*m + 1; A(c,r) = 1; end end x = intlinprog(f, intcon, A", b, Aeq) ", beq, lb, ub)

Aşağıdaki yaklaşımı deneyeceğim (bu sorunla hiçbir zaman uğraşmak zorunda olmadığımı unutmayın, bu nedenle bu cevabı, gerçek bir analitik cevap yerine sorunu sizinle çözme girişimi olarak kabul edin).

Çözümleri sanki normal bir sistemmiş gibi bulursunuz, böylece sonsuz sayıda çözüm bulabilirsiniz:

Örnek:

Y=x+3

o zaman gerçek sayı çifti (2,5) bu sistem için olası bir gerçek çözümdür; sonsuz sayıda çözümünüz olduğunda, tamsayılar tarafından üretilen çözümlerin alt kümesini sınırlandırırsınız.

Elbette sınırlamalarınız var, bizim durumumuzda çözümün yalnızca 1 serbest değişkeni var, dolayısıyla tüm çözümleri şu şekilde yazabiliriz:

(x, x+3)

Şaşkınlık:

Eğer orada bir yerde irrasyonel bir sayı varsa, tamsayı çözüm yoktur:

(x, x+pi) => buradaki ne 1. ne de 2. sayı aynı anda tam olamaz

Böylece bulabilirsin tamsayı çözümleri ancak ve ancak "sonsuz sayıda çözümünüz" tam sayılarla veya rasyonel sayılarla sınırlıysa.

Diyelim ki aşağıdaki vektöre sahipsiniz:

(3x, (2/5)y, y, x, x+y)

O zaman tüm çözüm şöyle olabilir:

X=3 y=10/2

Cevabın size uygun olmadığını düşünüyorsanız şunu söylemeniz yeterli: Bonus puan almamak için sileceğim.