Gomori yöntemine göre çözüm örnekleri. N.Yu. Kolomarova Doğrusal tamsayılı programlama problemlerini Gomory yöntemiyle çözme

Kesme yöntemlerinin özü, problemin önce tamsayı koşulu olmadan çözülmesidir. Ortaya çıkan plan tamsayı ise problem çözülür. Aksi takdirde, görev kısıtlamalarına aşağıdaki özelliklere sahip yeni bir kısıtlama eklenir:

Doğrusal olmalıdır;

Bulunan optimal tamsayı olmayan planı kesmeli;

Herhangi bir tamsayı planı kısaltmamalıdır.

Bu özelliklere sahip ek bir kısıtlamaya uygun kesim denir.

Geometrik olarak, her bir lineer kısıtlamanın eklenmesi, çözüm çokgeninin (çokyüzlü) bir kısmını tamsayı olmayan koordinatlarla en uygun noktayla birlikte kesen bir düz çizgi (hiperdüzlem) çizmeye karşılık gelir, ancak tamsayı noktalarından hiçbirini etkilemez. bu çokyüzlü. Sonuç olarak, yeni çözüm politopu, orijinal çözüm politopunda bulunan ve buna uygun olarak bu politopla elde edilen tüm tamsayı noktalarını içerir. en uygun çözüm tamsayı olacaktır (Şekil 8.1).

ana değişkenler *1, *2, yeni değişkenler Xm+1, Xm+2, ..., Xm+1, çözümler

xm ile neox- x„ optimal

(8.5)

tamsayı olmayan bileşen Bu durumda eşitsizliğin ispatı yapılabilir.

(P, ) - (a," m+\)xm+1 ■ -~(am)Xn ^ 0, (* )

Sistemin (8.5) /-inci denklemine göre oluşturulmuş, doğru kesimin tüm özelliklerine sahiptir.

Tamsayılı doğrusal programlama (8.1)-(8.4) problemini Gomory yöntemiyle çözmek için aşağıdaki algoritma kullanılır:

1. (8.1)-(8.3) problemini bütünlük koşulunu dikkate almadan çözmek için simpleks yöntemini kullanın. Optimal planın tüm bileşenleri tamsayı ise, o zaman tamsayı programlama problemi (8.1)-(8.4) için de optimaldir. İlk görev (8.1) ise

(8.3) çözülemez (yani, sonlu bir optimumu yoktur veya koşulları çelişkilidir), o zaman ikinci problem (8.1)-(8.4) de çözülemez.

2. Optimal çözümün bileşenleri arasında tamsayı olmayan bileşenler varsa, en büyük olan bileşeni seçin. tüm parça ve sistemin (8.5) karşılık gelen denklemine göre doğru kesmeyi (8.6) oluşturun.

3. Negatif olmayan ek bir tamsayı değişkeni ekleyerek eşitsizlik (8.6) eşdeğer bir denkleme dönüştürülür

(P() - |a/ m+1)*m+1- ■-(a|"l)xn + xn+1 > (®*^)

ve kısıtlama sistemine (8.2) dahil edin.

4. Ortaya çıkan genişletilmiş problemi simpleks yöntemini kullanarak çözün. Bulunan optimal plan tamsayı ise,

o zaman görev Tamsayılı programlama(8.1)-(8.4) çözülür. Aksi takdirde, algoritmanın 2. adımına dönün.

Problem tamsayılarla çözülebilirse, sonlu sayıda adımdan (yineleme) sonra optimal tamsayı planı bulunacaktır.

Bir denklemi çözme sürecinde (ana değişkeni temel olmayanlar cinsinden ifade ederek) tamsayı olmayan bir serbest terim ve tamsayı diğer katsayılarla ortaya çıkarsa, karşılık gelen denklemin tamsayılarda bir çözümü yoktur. Bu durumda ve verilen görev tamsayı optimal çözümü yoktur.

^ 8.1. Çiftçi, tahılı sınıflandırmak için ekipman satın almak için 34 den tahsis eder. birimler Ekipman, 60 metrekareyi geçmeyen bir alana yerleştirilmelidir. m.Bir çiftçi iki tür ekipman sipariş edebilir: 3 den değerinde daha az güçlü A tipi makineler. 3 m2 üretim alanı gerektiren üniteler. m (geçişler dahil) ve vardiya başına 2 ton tahıl verimi sağlayan ve 4 denye mal olan daha güçlü B tipi makineler. 5 metrekarelik bir alanı kaplayan birimler. m ve vardiya başına verimlilik sağlayan 3 ton yüksek kaliteli tahıl.

Çiftçinin 8'den fazla B tipi makine satın almaması koşuluyla, maksimum toplam üretkenlik sağlayan ekipman satın alımı için optimal bir plan yapılması gerekmektedir.

Çözüm. A ve B tipindeki makinelerin sayısını Z'ye kadar sırasıyla x\, x2 ile gösterelim - Genel performans. O zamanlar matematiksel model görevler şöyle görünecek:

Şek. 8.2 OKM - düz çizgiler (1), (2), (3) ve koordinat eksenleri ile sınırlanan soruna (8.1") - (8.3") kabul edilebilir çözüm alanı; />(2/3; 8) - problemin optimal, ancak tamsayı olmayan çözüm noktası (8.1") - (8.3"); (4) bu tamsayı olmayan çözümü kesen düz bir çizgidir; 0№M - genişletilmiş problemin uygulanabilir çözüm alanı (8.1') - (8.3'), (8.61); M2; 7) - optimal tamsayı çözümünün noktası.

ben adım. Ana değişkenler x3, x4, *5; minör değişkenler X\, X2.

x3	= 60 -	Zx! - 5x2,
x4	= 34 -	Zx) - 4x2,
x5	= 8	- *2>
	Z = 2x)	+ Zx2.

Birinci temel çözüm X\ = (0; 0; 60; 34; 8) kabul edilebilir. Doğrusal fonksiyonun karşılık gelen değeri = 0.

En büyük pozitif katsayılı doğrusal bir fonksiyonun ifadesine dahil edilen XI değişkenini ana değişkenlere çeviriyoruz. Kısıtlama sistemini kabul etmeye “izin veren” хі değişkeninin mümkün olan maksimum değerini, karşılık gelen oranların minimum koşulundan buluyoruz:

Хг = 1ШП |t;t;T | = 8,

şunlar. üçüncü denklem çözülüyor (vurgulanmış). Bu denklemde *2 = 8 ile X5 = 0 olur ve X5 değişkeni temel olmayanlara geçer.

II adım. Ana değişkenler x2, x3, x*; minör değişkenler Xx X5.

{

(8.6)

Ek bir tamsayı değişkeni x6 > 0 ekleyerek, eşitsizliğe (8.6") ​​eşdeğer bir denklem elde ederiz.

~1 * 5 + Xb \u003d ° "^8"7 ^

Denklem (8.7"), orijinal kanonik problemin kısıtlamalar (8.5") sistemine dahil edilmelidir, bundan sonra problemi çözme süreci tekrarlanmalıdır. simpleks yöntemi Genişletilmiş bir sorun için. Bu durumda, adım (yineleme) sayısını azaltmak için, elde edilen sisteme ek bir denklem (8.7") eklenmesi önerilir. son adım problemin çözümü (tamsayı koşulu olmadan).

IV adım. Temel değişkenler X), *2, xs> *b'> temel olmayan değişkenler *1, *2-

X1 \u003d s - 3 * 4 +

x3 = 18 + x4 +___ x5,

x6 - + ^x4 + z "x5-

Temel çözüm X4 = (y; 8; 18; 0; 0; -y) geçersiz. (Kısıtlamalar sisteminde doğru kesime karşılık gelen ek bir denklemin dahil edilmesinden sonra, her zaman geçersiz bir temel çözüm elde edileceğine dikkat edin).

Kabul edilebilir bir temel çözüm elde etmek için, denkleme pozitif katsayılı, negatif terimin daha serbest olduğu, yani ana değişkene giren ana değişkene dönüştürmek gerekir. *1 veya x$ (bu aşamada doğrusal fonksiyonu dikkate almayız). Ana olanlara, örneğin X5 değişkenine çeviriyoruz.

Adım. Ana değişkenler X\, X2, X3, X5; temel olmayan değişkenler R], X£

Dönüşümlerden sonra elde ederiz:

LG| \u003d 2 - x4 + 2x6,

*2 = 7 + 2x* ~ 2x("

x3 = 19 + -x4 + -x6,

*5 = 1 - 2x* + 2x6’

2 = 25-|x4--|x6.

^5 =(2; 7; 19; 0; 1;0);^ = 25.

Doğrusal bir fonksiyonun ifadesinde pozitif katsayılı ana değişken olmadığından X5 optimal çözümdür.

Dolayısıyla, optimal tamsayı çözümü X* - X$ =(2; 7; 19; 0; 1; 0) için 2max = 25, yani. maksimum performans 2 adet A tipi ve 7 adet B\ tipi makine satın alınarak vardiya başına 25 ton yüksek kaliteli tahıl elde edilebilirken, tesisin boş alanı 19 metrekare olacaktır. m, kalıntılar Para seçilenlerden 0'a eşittir, satın alma rezervinde - 1 B tipi araba (altıncı bileşenin anlamlı bir anlamı yoktur).

Yorum. Kesimin (8.6 ") Ox \ Xr düzleminde (bkz. Şekil 8.2) geometrik bir yorumu için, içerdiği x4 ve x$ değişkenlerini XI ve x2 değişkenleri aracılığıyla ifade etmek gerekir. Kısıtlamalar sisteminin (8.5") 2. ve 3. denklemleri:

y - y (34 - 3x, - 4x2) - y (8 - x2) £ 0 veya x, + 2x2 £ 16.

(Şekil 8.2'deki düz çizgiyi (4) kesmeye bakın)>

^ 8.2. yeterince var çok sayıda 3 m uzunluğunda kütükler Kütükler iki tür boşluk halinde kesilmelidir: 1,2 m uzunluğunda ve 0,9 m uzunluğunda ve her türden en az 50 adet elde edilmelidir. ve 81 adet. sırasıyla. Her kütük, belirtilen boşluklara çeşitli şekillerde kesilebilir: 1) 1,2 m'lik 2 boşluk; 2) 1,2 m'lik 1 boşluk ve 0,9 m'lik 2 boşluk için; 3) her biri 0,9 m'lik 3 boşluk için Kütük sayısını bulun,

her yöntemle kesilmiş, böylece en az sayıda kütükten herhangi bir tür parça elde edilebilir.

Çözüm. x\, xi, xm, kesilen kütüklerin sayısını sırasıyla 1, "2- ve 3 yol ile belirtin. Bunlardan 2 m 2xi + *2 boşluk 1,2 m ve 2n\ + Zx2 boşluk 0,9 m alabilirsiniz. Toplam I ile gösterdiğimiz günlükler. Daha sonra problemin matematiksel modeli şu şekilde olacaktır:

ben 2x, + x2 - x4 = 50,+ (?y), nerede [y] - bütün kısım ve (y) \u003d Y ~ [y] ~ kesirli kısım.

[h] Kabul edilebilir bir temel çözüm buluyoruz, Yeni hat izin veren, yani ben = P + 1.

• a) Tüm katsayılar ise uts> 0 ise problemin çözümü yoktur (yani tamsayı problemi çözülmüştür).
• b) Aksi takdirde, dizini bulun ileöyle ki

(giriş kriteri yeni temel). Etkinleştirme öğesinin seçiminin deve* kriterlerin işaretini değiştirmez Aj.

[4] İçinde ise yeni masa en az bir tane var x 3 s ve belirtilen prosedürleri gerektiği kadar tekrarlayın.

[~5~| Ortaya çıkan optimal çözüm tamsayı ise, problem çözülür. Aksi takdirde, noktaya dönün.

Örnek 4.6.1. Gomory tamsayı problemini çözün

Çözüm. Yardımcı değişkenleri ekledikten sonra aşağıdaki görev vardır. doğrusal programlama standart formda:

matrislerle

tablo 1
	X4

ile= 1 T

Döndürme yöntemini kullanarak aşağıdaki tabloları doldurun. İzin verilen öğe - 6*.

Tablo 2				X 2
		„ _ 1 VEZ ~_3_

k" = 2 ton

İzin verilen öğe - 1/2*.

X içinde^0). Bu nedenle, program (xi = 11/3, X 2 = 5) maksimum ekonomik fonksiyonu verecektir z, 1370/3 = 45b |, t.s'ye eşittir. z= zmaks = 456§. "

Bundan beri optimal program tamsayı değil, bir tamsayı optimal programı bulmak için Gomory algoritmasını kullanırız. Tüm öğelerin kesirli kısımlarından ek bir dize oluşturduğumuz bir dize olarak, ikinci dizeyi seçiyoruz (indeks 7' = 1). Tablo 3'e ek değişken Zh5 için kesirli parçalar içeren ek bir satır (4.14) ekleyerek tablo 3"ü dolduralım ve ek sütun. alırız

k" = 4T

Yeni bir satır ekledikten sonra, tek yönlü tablo 3", tanımladığı problem için kabul edilebilir bir temel çözüme karşılık gelmez. Çözülecek yeni satırı dikkate alarak kabul edilebilir bir temel çözüm buluyoruz, yani /" = 5.

Çözme sütununu buluyoruz, t.s. dizin ile"öyle ki

(yeni bir temele girmek için kriterler). İzin verilen öğe - (-2/3*). Çözümleme elemanının böyle bir seçiminin kriterlerin işaretini değiştirmediğine dikkat edin. Aj.

Simpleks tablosunu doldurun 4.

Tablo 4				X2
	X2

Tüm kriterlerin değerleri ^ 0, ( X içinde^0). Bu nedenle program (xi = 3, x 2 = 6, x±= 1) 450'ye eşit ekonomik fonksiyonun maksimumunu verir, t.s. z = zma^= 450. Bu optimal program tam sayıdır. ?

Örnek 4.6.2. Gomory tamsayı problemini çözün

Çözüm. Matrislerle ilgili doğrusal bir programlama sorunu var

Simpleks tablosunu başlangıç ​​programı ile dolduralım.

tablo 1

ile= 1 T

Döndürme yöntemini kullanarak aşağıdaki tabloları doldurun. İzin verilen öğe - 1*.

Tablo 2				X2

İzin verilen öğe - 5*.

Tablo 3

Tüm kriterlerin değerleri ^ 0, ( X içinde^0). Bu nedenle, program (xi = 12/5, 24 = 1/5, 25 = 28/5), -11/5 = -2.2, t.s'ye eşit olan r ekonomik fonksiyonunun minimumunu verir. z =

~dak = -2.2.

Bu optimal program tamsayı olmadığından, bir tamsayı optimal programı bulmak için Gomory'nin algoritmasını kullanırız. Temel olarak, cc öğelerinin kesirli kısımlarından ek bir dize oluşturduğumuz bir dize olarak, örneğin, maksimum kesirli kısmı olan üçüncü alt dizeyi (indeks r = 5) seçiyoruz. Ek bir değişken için üçüncü satırın kesirli kısımlarıyla tablo 3'e ek bir satır (4.14) ekleyerek tablo 3"ü dolduralım. xq (bu satır, program alanından sayısal olmayan koordinatlara sahip noktaları içeren parçaları kesmenizi sağlar) ve ek bir sütun. alırız

Tablo 3"
		G - -VE

k" = 3 ton

Yeni bir satır ekledikten sonra, tek yönlü tablo 3", tanımladığı problemin kabul edilebilir bir temel çözümüne karşılık gelmez. Çözülecek yeni satırı dikkate alarak kabul edilebilir bir temel çözüm buluyoruz, yani. ben" = 6.

Çözümleme sütununu buluyoruz, yani. dizin ile"öyle ki

(yeni bir temele girmek için kriterler). İzin verilen öğe - (-3/5*). Çözümleme elemanının böyle bir seçiminin kriterlerin işaretini değiştirmediğine dikkat edin. Aj.

Simpleks tablosunu doldurun 4.

Tablo 4

Tüm kriterlerin değerleri ^ 0, ( X içinde^0). Bu nedenle program (x = 2, X2 = 0, xs = 1, X 4 = 0, x 5 = 5) ekonomik fonksiyonun minimumunu verecektir. z 9 eşittir (-2), t.s. z=-min = - 2. Bu optimal program tamsayıdır. ?

Sorun 4.6.1. Gomory tamsayı problemini çözün

Cevap. programı

(-31), t.s'ye eşit ekonomik fonksiyon z'nin minimumunu verir. z= 2 m ben n = -31. Bu optimal program tamsayıdır.

Tamsayılı programlama problemlerinde, doğrusal programlama problemlerinin aksine, değişkenler üzerinde ek bir kısıtlama getirilmiştir: sadece tamsayı değerleri alabilirler.

Taşıma türü gibi bazı problemlerde, ilk veriler (gönderilen ve alınan malların miktarı) tamsayı olarak ifade edilirse bu koşul otomatik olarak karşılanır. Ancak genel doğrusal programlama probleminde, tamsayıları çözmek için olağan yöntemler, başlangıç ​​değerlerinin tamsayı mı yoksa kesirli mi olduğuna bakılmaksızın garanti etmez.

AT matematiksel gösterim ortak görev tamsayı programlama benziyor Aşağıdaki şekilde:

maksimize etmek

koşullar altında

x j≥ 0, x j - tüm.

Doğrusal programlamanın ekonomik sorunları çoğunlukla tamsayılı bir çözüm gerektirir. Bu, değişkenlerin bölünmez ürün, ekipman, işçi (görevler) birimlerinin sayısını gösterdiği görevler için geçerlidir. en iyi dağıtım işletmeler arası üretim görevleri, optimizasyon problemleri üretim programı bireysel işletmeler, optimum ekipman yükleme görevleri vb.). Genellikle bu tür problemler, elde edilen değişken değerlerinin tam sayılara yuvarlanmasıyla olağan simpleks yöntemiyle çözülür. Ancak bu durumda, gerçekten optimal tamsayı planına yalnızca bir miktar yaklaşım elde edilebilir.

Doğrusal programlama problemlerinin bir diğer grubunda, belirlenecek miktarlar, belirli bir talebi en etkin şekilde karşılayan üretim kapasiteleridir. Üretim kapasitesinin "taşıyıcıları" bireysel işletmeler, bölünmez ekipman parçaları vb. olduğundan, bu problemler aynı zamanda tamsayılı doğrusal programlama problemlerine de indirgenmektedir.

Boyutlu malzemenin rasyonel olarak kesilmesi sorunları (minimum atık için görevler) de tam sayılardır, çünkü içlerindeki değişkenler, bir kural olarak, şu ya da bu şekilde kesilen ilk boşlukların sayısını gösterir.

Yukarıda bahsedilen tüm problemlerde, çözüm, sonraki ayarlamalar ve optimal olana az ya da çok yakın bir tamsayı planı elde etme ile birlikte olağan doğrusal programlama yöntemleriyle bulunabilir. Ancak tamsayı olmayan çözümü mantıklı olmayan problemler var. Bunlar, değişkenlerin sayısal değerlerinin yalnızca alternatifi (“ya - ya da”, “evet - hayır”) belirlemeye hizmet ettiği seçim problemlerini içerir.

Tamsayı seçim modelleri, çeşitli ürünleri (parçaları) üretime sokmak için en uygun sıradaki görevler gibi bazı operasyonel programlama görevlerini içerir. Fırlatma sırasını belirlemenin gerekli olduğunu varsayalım n her biri birkaç makinede sırayla işlenen parçalar. Değişkenler x ij parçası ise bire eşittir j detay için çalışmalı i , ve diğer tüm durumlarda sıfır. Her sabit için j , ayrıca her biri için i , sadece biri n değişkenler bire eşit olabilir, bu nedenle problemin kısıtlamaları şunları içerir:

Bu gruptaki makinelerde tüm parçaların toplam işlem süresi minimize edilmiştir. Böyle bir soruna tamsayı olmayan bir çözüm anlamsızdır.

Tamsayılı programlama problemlerini çözmek için birkaç yöntem vardır. En ünlü gomory yöntemi, simpleks yönteminin kullanımına dayanmaktadır.

Matematiksel kavramları düşünün: uyum sayılar, tüm ve bir sayının kesirli kısmı. Sayı a sayıya uygun b eğer ve sadece fark varsa a - b bir tamsayıdır. Uyum üç yatay çizgi ile gösterilir ( ≡ ); böylece, a ≡ b , eğer a - b bir tamsayıdır.

Örneğin: 5 / 3 ≡ 2 / 3 , çünkü 5 / 3 - 2 / 3 = 1;

- 1 / 3 ≡ 2 / 3 , çünkü - 1 / 3 - 2 / 3 = 1.

Tüm tamsayılar birbirine ve sıfıra eşittir. Tamsayı olmayan elemanlar, sayının tamsayı ve kesirli kısımlarının toplamı olarak gösterilebilir. a = [a ] + {a ). Köşeli parantezler, içinde yer alan sayının tamsayı kısmını, küme parantezleri ise sayının kesirli kısmını almak anlamına gelir.

bir sayının tamsayı kısmı a en büyük tam sayı olarak adlandırılır [ a ], aşırı değil a .

Bir sayının kesirli kısmı a negatif olmayan en küçük sayı olarak tanımlanır ( a ), sayıya uygun a . Bir sayının kesirli kısmı a sayı arasındaki farka eşit a ve bütün kısmı :( a }=a - [a ]

örneğin, için a = 2 1 / 3 [a ]= 2 (a) = 1 / 3

için = - 2 1 / 3 [a ]= -3 (a) = 2 / 3

Sayı uyumu özellikleri:

1. Eğer a ≡ b , sonra ( a } = {b }.

2. {a +b } = {a } + {b }.

3. Eğer n bir tamsayıdır, o zaman herhangi biri için a

hayır ≡ {hayır } ≡ n {a }.

Gomory yöntemiyle tamsayılı programlama problemlerini çözerken, ilk aşama olağan hesaplama ile çakışır. simpleks algoritması. Elde edilen çözüm Genel görünüm tamsayı şartı dışında problemin tüm koşullarını karşılayacaktır (tabii ki ilk aşamada bir tamsayı çözümü elde etmek mümkündür). Optimum plandaki değişkenlerin değerleri arasında (Şekil 13'teki A noktası) kesirli olanlar varsa, o zaman çözümün kesirli kısmını “kesiyormuş” gibi ek bir kısıtlama oluşur (Şekil 1'deki satır 1) 13), ancak optimal planı karşılaması gereken problemin tüm kısıtlamalarını yürürlükte bırakarak. Problemin orijinal kısıtlarına ek bir kısıt eklenir ve genişletilmiş sisteme tekrar simpleks prosedürü uygulanır. Optimal çözüm tekrar tamsayı olmadığı ortaya çıkarsa (Şekil 13'teki B noktası), bir ek kısıtlama daha eklenir (Şekil 13'teki satır 2) ve hesaplama işlemi tekrarlanır. Algoritma, optimal tamsayı çözümüne (eğer varsa) ulaşmak için sonlu sayıda adıma izin verir (Şekil 13'teki C noktası).

Pirinç. 13. Gomory kesme yöntemi

Örnek tamsayılı programlama probleminin çözümü. Yeni bir üretim tesisi için ekipman alımı için 20 den birim tahsis edildi. Ekipman 38 m2'yi geçmeyen bir alana yerleştirilmelidir. Bir işletme iki tür ekipman sipariş edebilir: 5 den.ye mal olan, 8 m 2 (koridorlar dahil) üretim alanı gerektiren ve vardiya başına 7 bin adet üretim verimliliği sağlayan daha güçlü A tipi makineler; 2 den.ye mal olan, 4 m 2 alan kaplayan ve vardiya başına 3 bin adet üretim yapan daha az güçlü B tipi makineler.

ile belirtmek X 1 adet satın alınan makine A ve üzeri X 2 - satın alınan makine sayısı B, problemin matematiksel koşullarını elde ederiz:

maksimum 7x 1 + 3x 2 → maks

koşullar altında: 5x 1 + 2x 2 ≤ 20

8x 1 + 4x 2 ≤ 38

x 1, x 2 ≥ 0 (bütün).

Ek değişkenler x 3 ve x 4 yardımıyla, başlangıçtaki eşitsizlikler denklemlere dönüştürülür (azaltılmış kanonik biçim):

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

Eğer x 1 ve x 2 ana değişkenleri tamsayı ise, o zaman doğrudan denklemlerden x 3 ve x 4 değişkenlerinin sadece tamsayı değerleri alabileceği sonucu çıkar.

Problem önce tamsayı şartı dikkate alınmadan çözülür.

Simpleks tablosu şöyle görünür:

temel	İTİBAREN	Plan					θ
1	2	3	4
X 1 → X 3							20/5=4 dk
4							38/8=4,75
f(x) = 0	-7	-3
x1				2/5	1/5		4:2/5=10
X 2 →X 4				4/5	-8/5		6:4/5=7,5 dk
f(x)=28		-1/5	7/5
x1						-1/2
x2		7,5			-2	5/4
f(x)=29,5				1/4

Optimal planda X 1 =1, X 2 =7.5; maksimum amaç fonksiyonu 29.5'dir. Bu nedenle, bir A tipi makine ve 7 B tipi makine satın almak gerekir (8 makine için ne para ne de yer yeterlidir), o zaman çıktı f (x) = 7 × 1 + 3 × 7 = 28 bin adet olacaktır. üretim.

Gomory'nin yöntemiyle bir tamsayı çözümü bulalım. Planda tamsayı olmayan bir değer alan X 2 değişkeni için, doğrudan yukarıdaki denklemi takip eden aşağıdaki denklemi oluşturuyoruz. tek yönlü tablo:

7.5 \u003d X 2 - 2X 3 + 1.25X 4.

X 2 \u003d 7.5 + 2X 3 - 1.25X 4.

Bu denklem, açıkçası, problemin kabul edilebilir bir tamsayı çözümü için de geçerli olmalıdır.

X 2 bir tam sayı olduğundan, denklemin sağ tarafındaki ifade de bir tamsayıdır; bu nedenle, bu denklemin sağ tarafının değeri sıfıra eşittir:

7.5 + 2X 3 - 1.25X 4 ≡ 0,

-2X 3 + 1.25X 4 ≡ 7,5.

Yukarıdaki uygunluk özellikleri ve X 3 ve X 4'ün tamsayı olduğu gerçeği göz önüne alındığında, bu ifade aşağıdakine dönüştürülebilir:

(-2)X 3 + (1.25)X 4 ≡ {7,5} ;

buradan şunu elde ederiz:

0.25X4 ≡ 0,5.

X 4 negatif olmayan bir tam sayı olduğundan, elimizde:

0,25X 4 \u003d 0,5 veya 1,5 veya 2,5, ...;

Sonuç olarak,

0,25X 4 ≥ 0,5.

Ortaya çıkan eşitsizlik bir denkleme dönüştürülür ve şimdi aşağıdaki üç denklemi içeren orijinal kısıtlama sistemine eklenir:

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

0,25x4 - x5 = 0,5.

Genişletilmiş kısıtlama sistemi ile ilgili olarak simpleks yöntemiyle çözme sürecini tekrarlayarak, temele dahil edilen değişkenlerin değerlerinin şu şekilde olduğu yeni bir optimal plan elde ederiz: X 1 = 2; X2 = 5; X 4 \u003d 2 (kalan boş alan).

Böylece, problemin optimal tamsayılı çözümü elde edilmiştir: bu kısıtlamalar altında, 2 A tipi makine ve 5 B tipi makine satın alınarak maksimum verimlilik (29 bin adet üretim) sağlanır.

PRATİK DERS

ŞUBE VE BAĞLAMA YÖNTEMİ

Bu yöntem hem tamamen hem de kısmen çözmek için kullanılabilir. tamsayı görevleri ayrık programlama

modeli düşünün

kısıtlamalar altında

Her tamsayı değişkeni için, tabii ki içinde bulunduğu üst ve alt sınırları ayarlayabildiğinizi varsayalım. optimal değerler

Hj ≤ Xj ≤ Vj ; j=1,2,…,k,…,n.

Genellikle hj = 0, ancak bu koşul gerekli değildir. Problem simpleks yöntemiyle çözülür. Eğer bir x k kesirli değerler alırsa, problemin optimal çözümünün lineer kısıtlamayı karşılayacağını varsayarız. X k ≤ D k veya doğrusal bir kısıtlama X k ≤ D k + 1 , nerede d k =[x k ] değerden aşağı en yakın tam sayıdır x k ; Dk + 1 en yakın tam sayıdır büyük taraf itibaren x k . nerede H j ≤ D k ≤ V j – 1 . Ardından, simpleks yöntemini kullanarak birkaç doğrusal programlama problemini çözmek gerekir:

ANCAK.

AT.

Tepe noktası çözüme karşılık gelen bir ağaç olarak temsil edilen yinelemeli bir süreç elde ederiz. orijinal sorun, ve ona bağlı iki dal, bir çift doğrusal programlama problemi A ve B'nin çözümleridir. Bu durumda amaç fonksiyonlarının elde edilen değerleri, orijinal problemin amaç fonksiyonunun değerinden küçük veya ona eşit olabilir. f(X) A ≤ f(X)­ 0 ; f(X) B ≤ f(X)­ 0 . Yeni elde edilen iki dal köşesinin her biri kendi ek dallarına sahip olabilir.

1) Yinelemeli dallanma işlemi, elde edilen planlar arasında tamsayılı bir çözüm elde edilene kadar devam eder ve amaç fonksiyonunun değeri büyük veya eşittir diğer dallanma köşelerinin hedeflerinin işlevleri.

2) Bir sonraki iterasyon adımında her iki problemin de tamsayı olmayan çözümleri varsa, daha fazla dallanma için bir tepe noktası seçilir, buna karşılık gelen problem hedef fonksiyonun büyük bir değerine sahiptir. Kesirli değerler alan değişkenlerden biri için aşağıdaki doğrusal programlama problemleri için yeni kısıtlar derlenir.

3) Bir sonraki iterasyon adımında problemlerden birinin tamsayı çözümü varsa ve ikinci problemdeki değişkenlerin değerleri arasında kesirli olanlar varsa, o zaman problem en yüksek değer amaç fonksiyonları. Bu, tamsayılı bir çözüm alan bir sorunsa, işlem sona erer, ancak bu sorun değişkenlerin kesirli değerlerine sahipse, o zaman ileri işlem dallanma.

4) Bir sonraki iterasyon adımında görevlerden birinin çözümü yoksa ve ortaya çıkan çözümdeki değişkenlerin değerleri arasında ikinci görevin kesirli değerleri varsa. Daha sonra, ilk problem için dallanma süreci durur ve ikinci problemin daha fazla dönüştürülmesi için, yeni bir doğrusal programlama problemi çifti için ek kısıtlamaların yapıldığı tamsayı olmayan değişkenlerden biri seçilir.

5) Bir sonraki iterasyon adımında problemlerden birinin çözümü yoksa ve diğeri için bir tamsayı çözümü elde edilirse ve hedef fonksiyonun büyük tamsayı değerine sahip ve dallanmaya devam edilebilecek başka bir seçenek yoksa, o zaman süreç sona erer ve bulunan çözüm, orijinal görevlerin optimal tamsayı çözümüdür.

Seçilen görev bir ara veriyorsa (çıkmaz) veya işlevin değeri görev B.1'dekinden küçükse f(X) A.4< f(X)­ В,1 ., sonra B.1 problemine geri dönülür ve yeni bir dallanma meydana gelir.

Şekil 14. Dal ve sınır algoritmasının blok diyagramı

Pirinç. 15. "Dallar ve sınırlar" yöntemi

Genellikle doğrusal programlama problemlerinde plan koordinatlarının tamsayı olması gerekmez. Bununla birlikte, pratikte, optimal planların koordinatlarının tamsayı olması gereken problemlerle sık sık karşılaşılır ve bu tür problemlere problem denir. . Doğrusal programlama problemlerini grafik yöntemi ve tek yönlü yöntemle çözerken, optimal planın koordinatlarının tamsayı olacağının garantisi yoktur.

Bazı durumlarda sonuçların yuvarlanmasına izin verilir. Örneğin, optimal plan 499.683.3 otomobilin üretilmesini şart koşuyorsa, sonucu 499.683'e, hatta 500.000'e yuvarlamak ekonomik olarak haklıdır.

Ancak, bu tür yuvarlamaların büyük bir hataya yol açabileceği sorunlar vardır. Örneğin, optimal plan 0,67 fabrika kurulmasını şart koşuyorsa, resmi olarak 0 veya 1'e yuvarlanmasına izin verilmez.

Bu nedenle, büyük bir pratik değer koordinatları tamsayı olan en uygun planı bulabileceğiniz doğrusal programlama problemlerini çözmek için yöntemlere sahiptir. Görevler Tamsayılı programlama bu yollarla çözülür.

Eğer bir tamsayı programlama sorunu verilen kanonik biçim, aşağıdaki gibi formüle edilir:

amaç fonksiyonunun maksimumunu bulun (doğrusal form)

kısıtlama sistemi ile

Böylece görev Tamsayılı programlama ve karşılık gelen doğrusal programlama problemi, yalnızca bilinmeyenlerin integral olması koşuluyla farklılık gösterir.

Doğrusal programlama problemlerinde olduğu gibi, tamsayılı programlama problemleri, optimal planın hedef fonksiyonu (doğrusal form) maksimize etmesini gerektirir.

Gomori'nin Tamsayılı Programlama Problemlerini Çözme Yöntemi

Gomory Yöntemi dır-dir evrensel yöntem tamsayılı programlama problemlerini çözme, bunun yardımıyla, sınırlı sayıda yinelemeden sonra, optimal 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 oldukça fazla yineleme yapılması gerekir.

Gomory yöntemiyle tamsayılı programlama problemleri çözülürken, tamsayı planları içermeyen alt kümeler, bir doğrusal programlama problemi için optimal planlar kümesinden kademeli olarak çıkarılır.

İlk iterasyonda, bir doğrusal programlama problemini çözmek için simpleks yöntemi kullanılır. Bulunan bilinmeyenler tamsayı gereksinimini karşılıyorsa, tamsayı programlama problemi çözülür. Bulunan bilinmeyenlerden en az biri kesirli sayı ise, ek koşul(nasıl oluşturulacağı - aşağıda daha fazlası) ve tamsayı programlama probleminin kısıtlama sistemine ekleyin. Böylece, tamsayı planları içermeyen bir alt küme, plan kümesinden çıkarılır. Bu şekilde eklenen problemin optimal planı tamsayı ise, tamsayı programlama problemi çözülür. Çözüm süreci, bir yinelemede tamsayılı bir optimal plan bulunana veya problemin çözümü olmadığı doğrulanıncaya kadar devam eder.

Şimdi bahsedilen ek koşulun nasıl yapılacağı hakkında. Ek bir koşul, kısıtlamalar sisteminin denklemlerinden birinden bilinmeyenlerin katsayılarından ve bilinmeyenlerin kendilerinden formülle elde edilir.

, nerede kıvırcık parantezler sırasıyla serbest terimin kesirli kısımları ve bilinmeyenlerin katsayılarıdır.

Örneğin, simpleks tablosundan aşağıdaki denklemi elde ederiz:

.

Serbest terimin kesirli kısmı, tamsayı kısmı sayının kendisinden aşağıdaki gibi çıkarılarak elde edilir:

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

(en x3 ),

(en x4 ).

ANCAK Genel kural kesirli kısımları bulmak şu şekildedir: bir gerçek sayının tamsayı kısmı a en büyük tamsayıdır [ a] , aşırı değil a; gerçek sayının kesirli kısmı a fark denir {a} = a - [a] sayının kendisi a ve tamsayı kısmı [ a] .

.

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

.

örnek 1 Aşağıdaki tamsayılı programlama problemini Gomori yöntemini kullanarak çözün. Maksimum amaç fonksiyonunu bulun

kısıtlama sistemi ile

Çözüm. Problemi simpleks yöntemiyle çözüyoruz. sahip olduğumuzdan beri simpleks yöntemini kullanarak doğrusal programlama problemlerini çözme dersi, burada yöntemin kendisi anlatılmayacaktır, sadece tek yönlü tablolar verilecektir.

Ek bilinmeyenler x3 ve x4 temel olarak alın. Temel bilinmeyenleri ve amaç fonksiyonunu temel olmayan değişkenler cinsinden ifade ediyoruz:

Katsayılardan tek yönlü bir tablo yaparız:

Optimal bir plan elde edilene kadar aşağıdaki tabloları derliyoruz:

Tablo 3
Temel bilinmeyenler	Ücretsiz üyeler	Gevşek bilinmeyenler		yardımcı katsayılar
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
İTİBAREN	65/7	10/7	1/7	1/2

Tablo 3'ten en uygun planı buluyoruz . Bu optimal plan tamsayı koşulunu sağlamadığı için ek bir koşul yapmamız gerekiyor. kesirli kısım koordinat bir sayıdır ve koordinatın kesirli kısmı bir sayıdır.

Tabloya dayalı ilk denklem aşağıdaki gibi yazılır:

.

Bilinmeyen ve serbest terimlerdeki 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,

.

Tablo 3'ten elde edilen tek yönlü tabloda yeni bir satır alıyoruz ve yeni elde edilen denklemden katsayıları ekliyoruz:

Tablo 4
Temel bilinmeyenler	Ücretsiz üyeler	Gevşek 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
İTİBAREN	65/7	10/7	1/7	1/2

Simpleks yönteminin adımını atıyoruz ve tabloyu alıyoruz:

Tablo 5
Temel bilinmeyenler	Ücretsiz üyeler	Gevşek 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
İTİBAREN	55/6	4/3	1/6	-1/7

En iyi planı aldım . Bu plan, bir önceki gibi, tamsayı koşulunu sağlamaz. Bu nedenle yine ek bir koşul aranmaktadır. AT bu durum birinci veya üçüncü denklemi kullanabilirsiniz. Aşağıdaki ek koşulu alırsınız:

.

Aşağıdaki tabloyu yapıyoruz:

Tablo 6
Temel bilinmeyenler	Ücretsiz üyeler	Gevşek 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
İTİBAREN	55/6	4/3	1/6	-1/7

Optimal Plan aşağıdaki nihai tablodan alıyoruz:

Tablo 7
Temel bilinmeyenler	Ücretsiz üyeler	Gevşek 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
İTİBAREN	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ı sadece dört bilinmeyen içerdiğinden ihmal edilebilir. Bu nedenle, nihai optimal plan aşağıdaki gibi yazılacaktır:

,

ve amaç fonksiyonunun maksimumu 9'dur.

Tamsayılı Programlama Problemlerini Çözmek İçin Dal ve Sınır Yöntemi

Dal ve sınır yöntemi, bilinmeyenlerin sayısının küçük olduğu veya tamsayı gereksinimlerinin tüm bilinmeyenler için geçerli olmadığı bu tür tamsayılı programlama problemlerini çözmek için uygundur. Dal ve sınır yönteminin özü, tamsayı gereksiniminin 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 ilgili doğrusal programlama problemleri çözülür.

Bir tamsayılı programlama probleminde bilinmeyenlerin değerlerinin içinde bulunması gereken sınırların özellikleri aşağıdaki gibi yazılabilir:

Uygulamada, birçok durumda, bilinmeyenlerin değerlerinin sınırları, tamsayılı programlama probleminin kısıtlamalar sistemine zaten dahil edilmiştir veya problemin ekonomik içeriğine göre belirlenebilir. Aksi takdirde, alt sınırın ve üst sınırın olduğunu varsayabiliriz, burada M yeterince büyük bir pozitif sayıdır.

Dal ve sınır yöntemi, bilinmeyenlerin kabul edilebilir değerlerinin sınırlarının rafine edilmesini nasıl mümkün kılar?

İlk olarak, simpleks yönteminin bir tamsayı programlama problemine karşılık gelen bir doğrusal programlama problemini çözdüğünü varsayalım. Bu problemdeki optimal plan bulunsun ve herhangi bir koordinatının değeri kesirli sayı. O zaman iki yeni doğrusal programlama problemi yaratmamız gerekiyor. Nasıl yapılır?

Koordinatın tamsayı kısmını olarak gösterelim. Doğrusal programlamanın yeni problemlerinden birinde, koordinat değerinin alt sınırı sayı olacaktır, yani koordinat değerinin tamsayı kısmı, bir artırılır. Bu aşağıdaki gibi yazılacaktır:

.

Başka Yeni görev doğrusal programlama üst sınır koordinat değeri, koordinat değerinin kendisinin tamsayı kısmı olacaktır. Şu şekilde yazılacak:

Böylece, bir bilinmeyenin kabul edilebilir değerlerinin sınırlarının değiştiği ilk doğrusal programlama probleminden iki yeni problem "dallandı". Bu sorunların her birini çözerken, üç durum mümkündür:

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

Sadece ilk durumda, yeni görevleri yukarıda gösterilen şekilde "dallandırmak" mümkündür. İkinci ve üçüncü durumlarda, "dallanma" durur.

Bir tamsayılı programlama probleminin çözümünün her yinelemesinde bir problem çözülür. Bir kavram sunalım: çözülebilir doğrusal programlama problemlerinin bir listesi. Listeden ilgili yinelemede çözülecek sorunu seçin. Daha sonraki yinelemelerde, liste değişir, çünkü çözülen görevler artık buna dahil değildir, bunların yerine liste önceki görevlerden "dallanan" yeni görevleri içerir.

"Dallanmayı" sınırlamak, yani çözülecek görev sayısını azaltmak için her yinelemede alt sınırın belirlenmesi gerekir. maksimum değer hedef işlevi. Bu, aşağıdaki şekilde yapılır:

Dal ve sınır yöntemiyle tamsayı programlama problemini çözme algoritmasına göre, her birinde p yineleme 4 adım yapmak için gereklidir.

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

kısıtlama sistemi ile

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

.

Görev verildiği için normal form, bir tamsayı planı ve amaç fonksiyonunun maksimum değeri üzerinde bir alt sınırı vardır .

Çözülecek görevler listesinde - 1. görev:

yineleme 1.

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

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

4. Adım Optimal planın kesirli koordinatı 1.2 olduğundan, o zaman ve . 1. problemin bilinmeyenlerinin değerlerine sınırlar uygulayarak yeni problemler elde ederiz. 2. problemde için alt sınır , 3. problemde için üst sınır .