Ek bir kısıtlama gomori yöntemi hazırlamak. Tamsayılı Doğrusal Programlama Modelleri

Problemin ekonomik ve geometrik yorumu Tamsayılı programlama... Değişkenleri yalnızca tamsayı değerleri alan ekstrem bir probleme tamsayı programlama problemi denir.

Tamsayı probleminin matematiksel modelinde programlama hem amaç fonksiyonu hem de kısıt sistemindeki fonksiyonlar lineer, lineer olmayan ve karışık olabilir. Kendimizi, problemin amaç fonksiyonu ve kısıtlamalar sisteminin doğrusal olduğu durumla sınırlandırıyoruz.

Örnek 20.

Alanın tahsis edildiği işletmenin atölyesine ek ekipman kurulmasına karar verildi. Ekipman alımı için bir işletme 10 bin ruble harcayabilirken, iki tür ekipman satın alabilir. I tipi bir ekipman seti 1000 rubleye ve tip II - 3000 rubleye mal oluyor. Bir takım tip I ekipmanın satın alınması, vardiya başına üretim çıktısının 2 birim ve bir takım tip II ekipmanın - 4 birim artmasını sağlar. Bir tip I ekipman setinin kurulumunun 2 m 2 alan ve tip II - 1 m 2 alan gerektirdiğini bilmek, üretim çıktısını en üst düzeye çıkarmayı mümkün kılan böyle bir ek ekipman setini belirlemek için

Çözüm. hadi besteleyelim matematiksel model görevler. İşletmenin x 1 tip I ekipman seti ve tip II ekipman seti satın aldığını varsayalım. O zaman değişkenler x 1 ve aşağıdaki eşitsizlikleri sağlamalıdır:

Şirket belirtilen miktarda ekipman satın alırsa, üretimdeki toplam artış olacaktır.

Ekonomik içerikleri açısından, x 1 ve değişkenleri yalnızca negatif olmayan tamsayı değerleri alabilir, yani.

x 1, - tam sayılar. (73)

Böylece, aşağıdakilere geliyoruz Matematik problemi: bulmak maksimum değer(70), (72) ve (73) koşulları altında lineer fonksiyon (71). Bilinmeyenler sadece tamsayı alabileceğinden (70) - (73) problemi bir tamsayı programlama problemidir. Problemin bilinmeyen sayısı ikiye eşit olduğundan, bu problemin çözümü geometrik yorumu kullanılarak bulunabilir. Bunu yapmak için, her şeyden önce, (70) ve (72) koşulları altında lineer fonksiyonun (71) maksimum değerinin belirlenmesinden oluşan probleme bir çözüm çokgeni oluşturuyoruz (Şekil 11). Oluşturulan çözüm çokgeninin tüm noktalarının koordinatları OAEU sistemi tatmin et doğrusal eşitsizlikler(70) ve durum olumsuzluk değişkenler (72). Aynı zamanda koşul (73), yani koşul tam sayı değişkenler, sadece 12 noktanın koordinatları, Şekil 2'de işaretlenmiştir. 11. Koordinatları orijinal problemin çözümünü belirleyen noktayı bulmak için çokgeni değiştirin OABSçokgen OKEMNF tüm geçerli noktaları tamsayı koordinatlarıyla içeren ve her bir köşenin koordinatları tamsayı olacak şekilde. Dolayısıyla, fonksiyonun (71) maksimum noktasını çokgen üzerinde bulursak OKEMNF, o zaman bu noktanın koordinatları problemin optimal planını belirleyecektir.

Bunun için çözüm çokgeninden geçen düz bir doğru da oluşturuyoruz. OKEMNF(12 sayısı keyfi olarak alınır). Oluşturulan düz çizgiyi, son çizgiden geçene kadar vektör yönünde hareket ettiririz. ortak nokta verilen çokgen ile. Bu noktanın koordinatları optimal planı ve değeri belirler. amaç fonksiyonu içinde maksimumdur.

V bu durum gereken nokta E(1; 3), amaç fonksiyonunun maksimum değeri C aldığı Bu nedenle, noktanın koordinatları E problemin optimal planını belirler (70) - (73). Bu plana göre işletme, bir takım tip 1 ekipman ve üç takım tip II ekipman satın almalıdır. Bu, işletmeye üretim alanı üzerindeki mevcut kısıtlamaları ve peşin maksimum artışüretim çıktısı 14 birime eşittir. vardiya başına.

Örnek 21.

İş yapmak için kullanılabilir NS mekanizmalar. Verim ben Th mekanizması gerçekleştirirken J – iş eşittir. Her mekanizmanın sadece bir işte kullanılabileceğini ve her işin sadece bir mekanizma tarafından yapılabileceğini varsayarak, maksimum verimliliği sağlayan işlere mekanizmaların atanmasını belirleyin. Problemin matematiksel bir modelini oluşturun.

Çözüm.Çalıştırırken, değeri 1'e eşit olan x ij değişkenini tanıtıyoruz. ben kullanılan iş J – th mekanizması ve aksi takdirde 0'a eşittir. Daha sonra her bir mekanizmayı sadece bir işte kullanma koşulları eşitliklerle ifade edilir.

(74)

ve sadece bir mekanizma tarafından iş yapma koşulları - eşitlikler

(75)

Böylece görev, bilinmeyenlerin bu tür değerlerini belirlemektir. (74) ve (75) denklem sistemlerini ve fonksiyonun maksimum değerinin olduğu koşul (76) sağlanması

Formüle edilmiş problem bir tamsayılı programlama problemidir.

Bir tamsayılı programlama problemi için optimal planın belirlenmesi. Hem amaç fonksiyonunun hem de kısıtlama sistemindeki fonksiyonların doğrusal olduğu tamsayılı programlama problemlerini düşünün. Bu bağlamda, ana sorunu formüle ediyoruz doğrusal programlama değişkenlerin yalnızca tamsayı değerleri alabildiği. Genel olarak, bu problem şu şekilde yazılabilir: maksimum fonksiyonu bulun

koşullar altında

(79)

- bütün (81)

Eğer bulursan sorunun çözümü (78) – (81) tek yönlü yöntem, o zaman hem tamsayı hem de tamsayı olmadığı ortaya çıkabilir (çözümünün her zaman tamsayı olduğu bir örnek, taşıma görevi). Genel durumda, problem (78) - (81) için optimal planı belirlemek için özel yöntemler gereklidir. Şu anda, en ünlüsü olan bu tür birkaç yöntem vardır. Gomori yöntemi, yukarıda açıklanan simpleks yöntemine dayanmaktadır.

Gomori yöntemi. Gomori yöntemi ile bir tamsayılı programlama problemine çözüm bulmak, problemin optimal planını (78) - (80) dikkate almadan simpleks yöntemiyle belirlemekle başlar. tam sayı değişkenler. Bu plan bulunduktan sonra bileşenleri incelenir. Bileşenler arasında kesirli sayılar yoksa, bulunan plan tamsayılı programlama problemi (78) - (81) için en uygun plandır. (78) - (80) probleminin optimal planında, değişken kesirli bir değer alırsa, eşitsizlik

(82)

ve (78) - (80), (82) sorununa bir çözüm bulun.

Eşitsizlikte (82) ve – dönüştürülmüş başlangıç ​​değerleri ve değerleri son simpleks tablosundan alınan ve ve – sayıların kesirli kısımları (bir sayının kesirli kısmı, negatif olmayan en küçük sayı anlamına gelir) Böyle ki aradaki fark a ve B bir bütün). Optimal problem planında (78) - (80), kesirli değerler birkaç değişken alırsa, ek eşitsizlik (82) tanımlanır. en büyük kesirli Bölüm.

(78) - (80), (82) problemlerinin bulunan planında değişkenler kesirli değerler alıyorsa, tekrar bir kısıtlama daha eklenir ve hesaplama işlemi tekrarlanır. Sonlu sayıda yineleme gerçekleştirerek, tamsayılı programlama probleminin (78) - (81) optimal planı elde edilir veya kararsızlığı belirlenir.

eğer gereklilik tam sayı(81) sadece bazı değişkenlere atıfta bulunur, o zaman bu tür problemler denir kısmen tamsayı. Çözümleri, her biri bir öncekinden ek bir kısıtlama getirilerek elde edilen problemleri sırayla çözerek de bulunur. Bu durumda, böyle bir kısıtlama şu şekildedir:

nerede aşağıdaki ilişkilerden belirlenir:

1) tamsayı olmayan değerler alabilen için,

(84)

2) sadece tamsayı değerleri alabilen için,

(85)

Yukarıdakilerden, bir tamsayılı programlama probleminin optimal planını Gomori yöntemiyle belirleme süreci aşağıdakileri içerir: ana adımlar:

1. Simpleks yöntemini kullanarak (78) - (80) problemine gereksinimi dikkate almadan bir çözüm bulun. tam sayı değişkenler.

2. Optimum problem planında (78) - (80) olan bir değişken için ek bir kısıtlama yapılır. maksimum kesirli değer ve optimal problem planında (78) - (81) tamsayı olmalıdır.

3. İkiliyi kullanarak, (78) - (80) probleminden kaynaklanan probleme ek bir kısıt ekleyerek bir çözüm bulun.

4. Gerekirse, bir ek kısıtlama daha oluşturun ve optimal problem planı (78) - (81) elde edilene veya kararsızlığı sağlanana kadar yinelemeli işleme devam edin.

Örnek 22.

Gomori yöntemini kullanarak fonksiyonun maksimum değerini bulun.

şartıyla

(87)

- bütün (89)

Çözüm.(86) - (89) problemi için optimal planı belirlemek için önce (86) - (88) problemi için optimal planı buluyoruz (Tablo 22).

Tablo 22

		C b	r 0

Tablodan da görebileceğiniz gibi. 22, en uygun planı buldum (86) - (88) problemi, (86) - (89) problemi için optimal plan değildir, çünkü iki bileşenlidir ve tamsayı olmayan değerlere sahiptir. Ayrıca bu sayıların kesirli kısımları birbirine eşittir. Bu nedenle, bu değişkenlerden biri için ek bir kısıtlama oluşturulur. Örneğin bir değişken için böyle bir kısıtlama oluşturalım.Son tek yönlü tablodan (Tablo 22)

Böylece, (86) - (89) probleminin kısıtları sistemine eşitsizliği ekliyoruz.

veya

Tablo 23

		C b	r 0

Şimdi (87), (88) ve (90) koşulları altında (86) fonksiyonunun maksimum değerini buluyoruz (Tablo 23).

Tablo 23 gösteriyor ki orijinal sorun tamsayı programlamanın optimal bir planı vardır NS Bu bağlamda, amaç fonksiyonunun değeri eşittir. Sorunun çözümünün geometrik bir yorumunu verelim. (86) - (88) problemine uygun çözümlerin alanı çokgendir. OABCD(şek. 12). İncir. 12, amaç fonksiyonunun noktada maksimum değeri aldığını gösterir. İLE BİRLİKTE(19/2; 7/2), yani. ne X =(19/2; 7/2; 0; 0; 34) optimal plandır. Bu, doğrudan Tablo 22'den görülebilir. NS= (19/2; 7/2; 0; 0; 34) problem için optimal plan değil (86) - (89) (sayılar ve kesirlidir), daha sonra ek bir kısıtlama getirilir. Ondan elimine ederek ve yerine kısıtlama sisteminin (87) denklemlerinden karşılık gelen değerleri değiştirerek, çokgenden kesme elde ederiz. OABCDüçgen EFC.

Olarak Şekil l'de görülebilir. 12, elde edilen problemin uygulanabilir çözümlerinin alanı çokgendir. OABEFD... Noktada E(9; 4), bu çokgenin amaç fonksiyonu maksimum değeri alır. Noktanın koordinatları olduğundan E- tamsayılar ve bilinmeyenler ve denklem (87) değerlerinde ikame edildiğinde tamsayı değerleri alır ve ardından problem için optimal plandır (86) - (89). Bu aynı zamanda Tablo 23'ten de kaynaklanmaktadır.

Örnek 23.

Gomori yöntemini kullanarak, fonksiyonun maksimum değerini belirleme sorununa bir çözüm bulun.

koşullar altında

- tüm. (94)

Problemin çözümünün geometrik bir yorumunu verin.

Çözüm. Formüle edilmiş problemi aşağıdaki gibi yeniden yazıyoruz: fonksiyonun maksimum değerini bulun

koşullar altında

(96)

- tüm. (98)

Problem (95) - (98) değişkenler ve tamsayı olmayan değerler alabildiği için kısmen tamsayıdır.

Simpleks yöntemiyle (95) - (97) probleminin çözümünü buluyoruz (Tablo 24).

Tablo 24

		C b	r 0
		C b	r 0
							–1 / 3 problemin bir planı değildir (95) - (98), çünkü değişken

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

· Doğrusal olmalıdır;

· Bulunan optimal tamsayı olmayan planı kesmeli;

· Herhangi bir tamsayılı planı kesmemelidir.

Belirtilen özelliklere sahip ek bir kısıtlama denir doğru kesim.

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

Gomori tarafından önerilen lineer tamsayılı programlama problemini (6.59)… (6.62) çözmek için algoritmalardan biri, simpleks yöntemine dayanır ve doğru bir kesim oluşturmak için oldukça basit bir yol kullanır.

Pirinç. 6.18. Grafik illüstrasyon tamsayı çözümü

Doğrusal programlama problemi (6.52) ... (6.55) sonlu bir optimuma sahip olsun ve son adım simpleks yöntemiyle çözümü, ana değişkenleri ifade eden aşağıdaki denklemler elde edilir. çekirdek olmayan değişkenler aracılığıyla en uygun çözüm

(6.56)

yani (6.52)… (6.55) probleminin optimal çözümü, örneğin β ben- integral olmayan bileşen. Bu durumda, eşitsizliğin kanıtlanması mümkündür.

tarafından oluşturulan ben Sistemin -th denklemi (6.56), doğru kesimin tüm özelliklerine sahiptir.

Eşitsizlik (6.57), bir sayının kesirli kısmını gösteren bir sembol içerir. Sayı a numaraya uygun denir v(belirtilen) ancak ve ancak fark varsa a- v bir tamsayıdır.

Sayının tamamı a aşmayan en büyük tam sayıdır a... Bir sayının kesirli kısmı, bu sayı ile onun arasındaki fark olarak tanımlanır. tüm parça, yani ... Örneğin, = 2 için, ; için = -3 ve .

(6.52) ... (6.55) tamsayılı doğrusal programlama problemini Gomori yöntemiyle çözmek için aşağıdaki algoritma kullanılır:

1. Problemi (6.52)… (6.55) tamsayı koşulunu dikkate almadan simpleks yöntemiyle çözün. Optimal planın tüm bileşenleri tamsayı ise, o zaman tamsayı programlama problemi (6.52)… (6.55) için de optimaldir. İlk problem (6.52)… (6.54) çözülemez ise (yani, sonlu bir optimumu yoksa veya şartları çelişkiliyse), o zaman ikinci problem (6.52)… (6.55) de çözülemez.

2. Optimal çözümün bileşenleri arasında integral olmayan bileşenler varsa, en büyük integral parçaya sahip bileşeni seçin ve karşılık gelen sistem denklemini (6.56) kullanarak doğru kesmeyi (6.57) oluşturun.

3. Eşitsizlik (6.57), ek bir negatif olmayan tamsayı değişkeni ekleyerek eşdeğer bir denkleme dönüşür

ve kısıtlamalar sistemine dahil edin (6.53).

4. Elde edilen genişletilmiş problem simpleks yöntemiyle çözülür. Bulunan optimal plan tamsayı ise, tamsayı programlama problemi (6.52)… (6.55) çözülür. Aksi takdirde, algoritmanın 2. adımına dönün.

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

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

Gomori yönteminin dezavantajı, tüm değişkenler için tamsayı değeri gerekliliğidir - hem temel (örneğin, bir üretim biriminin kaynaklarını kullanma probleminde ifade edilir) hem de ek değişkenler (kullanılmayan kaynakların miktarını ifade eder). ayrıca kesirli olabilir).

geçiş olduğunu unutmayın kanonik biçim kısıtlamalar - eşitsizlikler içeren tamamen tamsayılı bir doğrusal programlama probleminde

genel olarak konuşursak, dönüştürülmüş kısıtlamalarda (6.59) olduğundan, kanonik biçimde tamamen tamsayı değerli bir soruna yol açmaz.

yardımcı değişkenler xn + ben tamsayı şartına tabi değildir.

Ancak tüm katsayılar bir ij, ben(6.59) tamsayı ise, tamsayı koşulu şu şekilde genişletilebilir: xn + benörnek 6.10'u çözerken yapıldığı gibi.

(6.59)'da ise kanonik formda tamamen tamsayılı bir problem de elde edilebilir. bir ij, ben Rasyonel sayılardır. Bunu yapmak için, (6.59) katsayıların paydalarının ortak katı ile çarpın - bir ij, ben(yani, (6.59)'daki tamsayı katsayılarına gidin) ve ancak o zaman yardımcı değişkenleri tanıtın.

Örnek 6.20. Tamamen tamsayılı bir programlama problemini çözün

kısıtlamalarla

Çözüm. Ek negatif olmayan değişkenler ekleyerek sorunu kanonik forma indirgeyelim. Bir kısıtlama sistemi alıyoruz:

Problemi simpleks yöntemini kullanarak çözüyoruz. Anlaşılır olması için çözümü grafiksel olarak gösteriyoruz (Şekil 6.19).

Pirinç. 6.19. Sorunun çözümünün grafik gösterimi

İncirde. 6.19 0 KLM- soruna uygulanabilir çözümlerin alanı düz çizgiler (1), (2), (3) ve koordinat eksenleri ile sınırlandırılmıştır; L(2/3; 8) soruna optimal, ancak tamsayı olmayan çözümün noktasıdır ; (4) - bu tamsayı olmayan çözümü kesen satır; 0 KNM- genişletilmiş problemin uygulanabilir çözümlerinin alanı (6.64") n(2; 7) optimal tamsayı çözümünün noktasıdır.

ben adım

	NS 1	NS 2
NS 3
NS 4
NS 5

İlk temel çözüm NS 1 = (0; 0; 60; 34; 8) - geçerli. Doğrusal fonksiyonun karşılık gelen değeri F 1 = 0.

Değişkeni ana değişkenlere çeviriyoruz NS 2, en büyük pozitif katsayılı doğrusal fonksiyonun ifadesine dahil edilir. Değişkenin mümkün olan maksimum değerini bulun NS Karşılık gelen oranların minimum koşulundan kısıtlama sistemini kabul etmemize izin veren 2:

,

onlar. çözme (vurgulanan) üçüncü denklemdir. NS NS Bu denklemde 2 = 8 NS 5 = 0 ve birincil olmayan değişkenlere gider NS 5 .

II adım... Temel değişkenler; çekirdek olmayan değişkenler.

	NS 1	NS 5
NS 3		-5
NS 4		-4
NS 2
		-3	-24

NS 2 = (0;8;20;2;0); F= 24. Temel değişkenlere çeviriyoruz NS 1 , , ve küçük NS 4 .

Adım... Temel değişkenler; çekirdek olmayan değişkenler. Dönüşümlerden sonra şunu elde ederiz:

	NS 4	NS 5				NS 4	NS 5
NS 3	-3	-3		NS 3	-1	-1
NS 1		-4		NS 1	1/3	-4/3	2/3
NS 2				NS 2
	-2	-1	-76		-2/3	-1/3	-76/3

Temel çözüm NS görev için en uygun 3 , çünkü doğrusal fonksiyonun ifadesinde pozitif katsayılı küçük değişkenler yoktur.

Ancak, çözüm NS 3 tamsayı koşulunu (6.55 ") sağlamaz. Değişkenli ilk denkleme göre NS Optimum çözümde (2/3) tamsayı olmayan bir değer alan 1, ek bir kısıtlama (6,57) oluşturuyoruz:

(6.56) ve (6.57)'ye göre serbest terimin kesirli kısmını denklemde olduğu gibi aynı işaretle ve küçük değişkenler için katsayıların kesirli kısımlarını aldığımıza dikkat çekiyoruz. NS 4 ve NS 5 - zıt işaretlerle.

Kesirli kısımlar olduğundan

sonra son eşitsizlik şeklinde yazılabilir

Ek bir tamsayı değişkeni tanıtarak NS 6 ≥ 0, eşitsizliğe eşdeğer denklemi elde ederiz (6.57 ")

Denklem (6.58), orijinalin kısıtlamalar (6.56 ") sistemine dahil edilmelidir. kurallı görev ve daha sonra genişletilmiş problemle ilgili olarak simpleks yöntemini kullanarak problemi çözme sürecini tekrarlayın. Bu durumda, adım (yineleme) sayısını azaltmak için, problemi çözmenin son adımında (tamsayı koşulu olmadan) elde edilen sisteme ek bir denklem (6.58 ") eklenmesi önerilir.

IV adım... Temel değişkenler; çekirdek olmayan değişkenler.

	NS 4	NS 5
NS 1	1/3	-4/3	2/3
NS 2
NS 3	-1	-1
NS 6	-1/3	-2/3	-2/3
	-2/3	-1/3	-76/3

Temel çözüm - geçersiz. Doğru kesime karşılık gelen kısıtlama sistemine 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, serbest terimin negatif olduğu denklemde pozitif bir katsayı ile yer alan ana değişkene, yani. NS 4 veya NS 5 (bu aşamada doğrusal fonksiyon dikkate alınmaz). Temel olanlara, örneğin bir değişkene çeviriyoruz NS 5 .

V adım... Temel değişkenler; çekirdek olmayan değişkenler. Dönüşümlerden sonra elde ederiz:

	NS 4	NS 6				NS 4	NS 6
NS 1	-6/9	4/3	-12/9	NS 1		-2
NS 2	1/3	-1	-14/3	NS 2	-1/2	3/2
NS 3	1/3		38/3	NS 3	-1/2	-3/2
NS 5	-1/3		-2/3	NS 5	1/2	-3/2
	3/9	1/3	150/9		-1/2	-1/2	-25

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

Doğrusal bir fonksiyonun ifadesinde pozitif katsayılı ana değişken olmadığından, NS 5 en uygun çözümdür.

Yani, F maks = 25 optimal tamsayı çözümü için Altıncı bileşenin anlamlı bir anlamı yoktur.

0 düzleminde geometrik yorumlama için NS 1 NS 2 (bkz. Şekil 6.19) kesme (6.57 "), içerdiği değişkenler gereklidir NS 4 ve NS 5 değişkenler cinsinden ifade NS 1 ve NS 2. Elde ederiz (kısıtlamalar sisteminin (6.56 ") 2. ve 3. denklemlerine bakın:

(Şekil 6.19'daki düz çizgiyi (4) kesmeye bakın).

(5.1) - (5.3) problemi için simpleks yöntemiyle elde edilen optimal plan aşağıdaki gibi olsun:
Sonra son simpleks tablo şöyle görünür:

Tablo 5.1

Tamsayılı Programlama Problemi için Temel Tek Yönlü Tabloya Düşürülmüş

farz edelim ki
kesirli; sonra biraz
ayrıca kesirli (aksi takdirde sorunun tamsayı çözümü yoktur). ile belirtelim
ve
sayıların tam bölümleri ve , yani sayıları aşmayan en büyük tam sayılar ve ... Daha sonra kesirli kısımların değerleri ve sayılar ve farklılıklar olarak tanımlanır:

nerede ve

Örneğin,

.

koşula göre beri
Negatif olmayan tam sayılardır, o zaman fark da negatif olmayan bir tam sayıdır.

Bu eşitsizliği bir denkleme dönüştürmek, sol tarafından negatif olmayan bir tamsayı tamamlayıcı değişkeni çıkarmak
denklemi -1 ile çarparız, son simpleks tablosuna ekleriz ve simpleks yöntemini (tercihen ikili) kullanarak buluruz yeni plan... Tamsayı değilse, son tek yönlü tabloyu kullanarak yeni bir ek kısıtlama oluştururuz.

(5.1) - (5.3) probleminin optimal planında, birkaç kesirli
o zaman ek bir kısıtlama max içindir ... Bu, optimal tamsayı çözümünü elde etme sürecini hızlandırır.

Ek bir kısıtlama getirmenin geometrik anlamını düşünün (bkz. Şekil 5.2). noktada izin ver Açokyüzlü çözümler Q işlev Z maksimum değerine ulaşır Z(A) = max, ancak noktanın koordinatları A- kesirli. Daha sonra I ve II'nin tam sayılarına getirilen kısıtlamalar bölgeden Q alanı kesmek köşe noktası ile
, koordinatları tamsayı olan ve doğrusal fonksiyon maksimum değerine ulaşır.

Şekil 5.2. Gomori kısıtlamasının geometrik anlamı

Aşağıdaki problem örneğini kullanarak Gomori yöntemini ele alalım.

Örnek 5.1. Bir fonksiyonun maksimum değerini bulun

koşullar altında

Problemin çözümünün geometrik bir yorumunu verin.

Çözüm. Problem (5.5) - (5.8) için optimal planı belirlemek için önce problem (5.5) - (5.7) için optimal planı buluyoruz:

Tablo 5.2

temel
plan
- standart altı,
.

Tablo 5.3

Simpleks tablo temele indirildi

,
- yetersiz, temel
,
.

Tablo 5.4

Simpleks tablo temele indirildi

en uygun plan
, temel
... Bu optimal tasarım, problem (5.5) - (5.8) için optimal tasarım değildir, çünkü iki bileşen ve tamsayı olmayan bir değere sahiptir. Ayrıca bu sayıların kesirli kısımları
birbirine eşittir. Bu nedenle, bu değişkenlerden biri için ek bir kısıtlama oluşturulur. Örneğin, değişken için böyle bir kısıtlama oluşturalım. (daha sıklıkla ilk satırı alırlar). Son simpleks tablosundan elimizde:

.

Böylece, (5.5) - (5.7) probleminin kısıtları sistemine eşitsizliği ekliyoruz.

Şimdi (5.6), (5.7) ve (5.9) koşulları altında (5.5) fonksiyonunun maksimum değerini buluyoruz. (5.9) koşuluna ek bir değişken ekliyoruz:

Tablo 5.5

Simpleks tabloya ek bir değişken girme

hadi seçelim .
temel.

Tablo 5.6

Simpleks tablosunu temele indirgemek

temel
.
.

Orijinal problem için en uygun planı yazalım:
Bu plan ile amaç fonksiyonunun değeri
.

Problemin çözümünün geometrik yorumu.

Şekil 5.3. Problemin çözümünün geometrik yorumu

(5.5) - (5.7) probleminin uygulanabilir çözümlerinin alanı çokgendir. OABSNS(şek.5.3). Şekil, amaç fonksiyonunun noktada maksimum değeri aldığını göstermektedir.
onlar.
optimal plandır. Bu plan problem için en uygun plan olmadığından (5.5) - (5.8) (sayılar ve – kesirli), daha sonra ek bir kısıtlama getirilir

Bu eşitsizliği ortadan kaldırmak ve bunların yerine kısıtlamalar sisteminin denklemlerinden karşılık gelen değerleri değiştirerek (5.6), elde ederiz
.

.

Bu eşitsizlik, düz çizgiyle sınırlanan yarım düzleme karşılık gelir.
çokgenden kesmek OABSDüçgen EFC.

Şekilden de görülebileceği gibi, elde edilen problemin uygulanabilir çözümlerinin alanı çokgendir. OABEFD... Noktada E(9; 4) bu çokgenin amaç fonksiyonu maksimum değerini alır. Noktanın koordinatları olduğundan E- tamsayılar ve bilinmeyenler
ve değerlerin denklemlerine (5.6) yerleştirildiğinde tamsayı değerleri alın
ve
sonra
(5.5) - (5.8) problemi için optimal plandır. Bu aynı zamanda simpleks yönteminin tablosundan da gelir.

Gomori yönteminin kullanımına ilişkin bir not: Sorunun orijinal temeli yapay vektörleri içeriyorsa, ek bir kısıtlama oluştururken yapay değişkenler atlanmalıdır.

Kendi kendine test soruları

Tamsayılı programlamanın kapsamı.

Tamsayılı programlama probleminin ifadesi.

Bir tamsayılı programlama problemini çözmenin grafiksel bir yolu.

Gomori yönteminin algoritması.

Ek bir kısıtlama oluşturma kuralı (Gomori bölümü).

Gomori bölümünün tanıtımının geometrik anlamı.

Gomori yöntemi, doğrusal programlama problemlerinde tamsayılı bir çözüm bulmak için kullanılır.
LP sorununun çözümü bulunsun: L i çözümü, eğer bir tamsayı olacaktır: onlar. ... (β i) - kesirli kısım tamsayı olmayan optimal çözüm x i, (d i) - temel olmayan değişkenlerin kesirli kısmı. Bu oran belirler (şekle bakın).

Hizmet amacı... Çevrimiçi hesap makinesi, kesme yöntemini kullanarak doğrusal tamsayılı programlama problemlerini çözmek için kullanılır. Çözüm, simpleks tabloları kullanır. (Örneğe bakın).

Talimat. Değişken sayısını ve satır sayısını (kısıtlama sayısı) seçin, İleri'ye tıklayın. Ortaya çıkan çözüm kaydedilir Kelime dosyası(Gomori yöntemiyle bir çözüm örneğine bakın). Ayrıca Excel formatında bir çözüm şablonu oluşturulur.

Değişken sayısı 2 3 4 5 6 7 8 9 10
Satır sayısı (kısıtlama sayısı) 2 3 4 5 6 7 8 9 10

Ayrıca, tür kısıtlamaları x ben ≥ 0 sayma.

Gomori algoritmasının türleri

1. Tam sayı problemlerini çözmek için ilk Gomori algoritması.
2. Kısmen tamsayılı doğrusal programlama problemleri için ikinci Gomori algoritması.

Gomori'nin algoritması tamsayı problemleri için aşağıdaki adımları içerir:

1. Doğrusal programlama problemi tamsayı değeri dikkate alınmadan çözülmüştür.
2. Kesirli sayılar arasından kesirli kısmı en büyük olan eleman seçilir ve ek bir kısıtlama oluşturulur.
3. Negatif olmayan ek bir değişken eklenerek eşitsizlik bir denkleme dönüştürülür.
4. Ortaya çıkan problem dual simpleks yöntemi ile çözülür.

Tamsayısız serbest terimler b i ve tamsayı katsayıları a ij olan bir denklemi çözme sürecinde simpleks tabloda görünüyorsa, bu problemin tamsayılı bir optimal çözümü yoktur.

Bir örnek. Araştırma ve Üretim Derneği "Strela", askeri-sanayi kompleksi için bileşenlerin üretimi ile uğraşmaktadır. A tipi ve B tipi ürünlerin imalatında çelik ve demir dışı metaller kullanılmaktadır. Teknolojik süreç ayrıca ürünlerin torna tezgahlarında işlenmesini ve freze makineleri... A tipi bir ürün ve B tipi bir ürün üretimi için teknolojik standartlara göre, belli bir miktar atölyede takım tezgahlarında işlemek için hammadde ve belirli bir makine-saat miktarı. teknolojik veriler üretim süreci tabloda verilmektedir.
Çalıştay ayı boyunca, NPO "Strela", hammaddeler ve üretim atölyelerinde çalışma süresi için sınırlı kaynaklara sahiptir (tabloya bakınız). Bir A tipi ürünün satışından elde edilen kar 100 ruble ve bir B tipi ürün biriminden - 250 ruble.

	İşlenmemiş içerikler		Dükkanda çalışma, makine saati		Satışlardan kar edin, ovun.
	Demir olmayan metaller	Çelik	Torna işleri	freze işi
Ürün A	10	25	41	90	100
Ürün B	30	25	90	50	250
Kaynaklar	4500	6250	14100	18000

NPO Strela için en yüksek karı veren en uygun üretim planını bulun (A tipi ve B tipi ürün sayısı tam sayılardır).

Çözüm.
Problemin ekonomik ve matematiksel modeli.
x 1 - A tipi ürünler için üretim planı, x 2 - B tipi ürünler için üretim planı,
x 1, x 2 tam sayılardır.
Kaynak sınırları
10x 1 + 30x 2 ≤ 4500
25x 1 + 25x 2 ≤ 6250
41x 1 + 90x 2 ≤ 14100
90x 1 + 50x 2 ≤ 18000
Amaç fonksiyonu
100x 1 + 250x 2 → maks

Simplex yöntemini kullanarak doğrudan doğrusal programlama problemini çözelim. Sonuç olarak, aşağıdaki en uygun planı elde ederiz:

temel	B	x 1	x 2	x 3	x 4	x 5	x 6
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1
F (X3)	422500 / 11	0	0	125 / 33	0	50 / 33	0

x 1 = 54 6/11, x 2 = 131 9/11
F (X) = 250 131 9/11 + 100 54 6/11 = 38409 1/11

Ortaya çıkan optimal plan tamsayı değil, bu yüzden uyguluyoruz Gomori yöntemi... En büyük kesirli kısım, x 4 (10/11) değişkeni için ikinci denklemdedir. Ek bir kısıtlama oluşturuyoruz:
q 2 - q 21 x 1 - q 22 x 2 - q 23 x 3 - q 24 x 4 - q 25 x 5 - q 26 x 6 ≤0
q 2 = b 2 - = 1590 10/11 - 1590 = 10/11
q 2 1 = bir 2 1 - = 0 - 0 = 0
q 2 2 = a 2 2 - = 0 - 0 = 0
q 2 3 = a 2 3 - = 3 47/66 - 3 = 47/66
q 2 4 = a 2 4 - = 1 - 1 = 0
q 2 5 = a 2 5 - = -1 17/33 + 2 = 16/33
q 2 6 = a 2 6 - = 0 - 0 = 0

10/11 - 47/66 x 3 - 16/33 x 5 ≤ 0

10/11 - 47/66 x 3 - 16/33 x 5 + x 7 = 0

kadarıyla ikili simpleks yöntemi amaç fonksiyonunun minimumunu bulmak için kullanılır, F(x) = -F(X) dönüşümünü yaparız.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F (X0)	-422500 / 11	0	0	-125 / 33	0	-50 / 33	0	0

Gomori'nin ilk yinelemesi. 1. Optimallik kriterinin kontrol edilmesi. Simpleks tablosundaki plan bir sözde plandır, bu yüzden baştaki satır ve sütunu tanımlarız.
2. Yeni bir serbest değişkenin tanımı. Temel değişkenlerin negatif değerleri arasında mutlak değerde en büyüğünü seçiyoruz. Beşinci satır önde olacak ve x 7 değişkeni tabandan çıkarılmalıdır.
3. Yeni bir temel değişkenin belirlenmesi. En az değerθ beşinci sütuna karşılık gelir, yani. x 5 değişkeni temele girilmelidir. Öndeki satır ve sütunun kesişiminde, (-16 / 33) değerine eşit bir çözümleme elemanı (RE) vardır.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	131 9 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	1590 10 / 11	0	0	3 47 / 66	1	-1 17 / 33	0	0
x 1	54 6 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	18 1 / 3	0	-6 2 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F (X0)	-38409 1 / 11	0	0	-3 26 / 33	0	-1 17 / 33	0	0
θ		-	-	-3 26 / 33: (-47 / 66) = 5 15 / 47	-	-1 17 / 33: (-16 / 33) = 3 1 / 8	-	-

4. Simpleks tablosunun yeniden hesaplanması, Jordan-Gauss yöntemi kullanılarak gerçekleştirilir.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16
F (X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8

Ortaya çıkan optimal plan şunları içerir: kesirli sayılar... En büyük kesirli kısmı 7/8 olan optimal tasarımda tamsayı olmayan bir değer alan x 2 değişkenli ilk denkleme göre, ek bir kısıtlama oluşturuyoruz:
q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 ≤0
q 1 = b 1 - = 131 7/8 - 131 = 7/8


q 1 3 = a 1 3 - = 27/160 - 0 = 27/160



q 1 7 = 1 7 - = -1 / 16 + 1 = 15/16
Ek bir kısıtlama:
7/8 - 27/160 x 3 - 15/16 x 7 ≤ 0
Ortaya çıkan eşitsizliği denkleme dönüştürüyoruz:
7/8 - 27/160 x 3 - 15/16 x 7 + x 8 = 0
katsayıları ek bir satır tarafından optimal değere eklenen tek yönlü tablo.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8	0
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4	0
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F (X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8	0

Gomroy'un ikinci yinelemesi. 1. Optimallik kriterinin kontrol edilmesi. Simpleks tablodaki plan sözde plandır, bu yüzden baştaki satır ve sütunu tanımlarız.
2. Yeni bir serbest değişkenin tanımı. Temel değişkenlerin negatif değerleri arasında x 8 değişkeni mutlak değer olarak en büyüğüdür. Temelden çıkarılmalıdır.
3. Minimum θ değeri yedinci sütuna karşılık gelir, yani. x 7 değişkeni temele girilmelidir.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	131 7 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	1593 3 / 4	0	0	5 15 / 16	1	0	0	-3 1 / 8	0
x 1	54 3 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	6512 1 / 2	0	0	28 1 / 8	0	0	1	-13 3 / 4	0
x 5	1 7 / 8	0	0	1 15 / 32	0	1	0	-2 1 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F (X0)	-38406 1 / 4	0	0	-1 9 / 16	0	0	0	-3 1 / 8	0
θ		-	-	-1 9 / 16: (-27 / 160) = 9 7 / 27	-	-	-	-3 1 / 8: (-15 / 16) = 3 1 / 3	-

4. Yeni Gomori kesimlerinin dönüşümünü gerçekleştirin.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15
F (X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3

Optimal olarak, kesirli sayılar mevcuttur. x 2 (14/15) değişkeninin en büyük kesirli kısmı. Ek bir kısıtlama oluşturuyoruz: q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 - q 18 x 8 ≤0
q 1 = b 1 - = 131 14/15 - 131 = 14/15
q 1 1 = 1 1 - = 0 - 0 = 0
q 1 2 = a 1 2 - = 1 - 1 = 0
q 1 3 = a 1 3 - = 9/50 - 0 = 9/50
q 1 4 = a 1 4 - = 0 - 0 = 0
q 1 5 = 1 5 - = 0 - 0 = 0
q 1 6 = 1 6 - = 0 - 0 = 0
q 1 7 = 1 7 - = 0 - 0 = 0
q 1 8 = 1 8 - = -1 / 15 + 1 = 14/15
Ek bir kısıtlama:
14/15 - 9/50 x 3 - 14/15 x 8 ≤ 0
Ortaya çıkan eşitsizliği denkleme dönüştürüyoruz:
14/15 - 9/50 x 3 - 14/15 x 8 + x 9 = 0
katsayıları, optimal simpleks tablosuna ek bir satır olarak dahil edilir.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3	0
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3	0
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F (X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3	0

Gomori yöntemiyle üçüncü yineleme. x 9 değişkeni temelden çıkarılmalıdır. Minimum θ değeri sekizinci sütuna karşılık gelir, yani. x 8 değişkeni temele girilmelidir.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	131 14 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	1596 2 / 3	0	0	6 1 / 2	1	0	0	0	-3 1 / 3	0
x 1	54 1 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	6525 1 / 3	0	0	30 3 / 5	0	0	1	0	-14 2 / 3	0
x 5	3 4 / 5	0	0	1 21 / 25	0	1	0	0	-2 1 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-1 1 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F (X0)	-38403 1 / 3	0	0	-1	0	0	0	0	-3 1 / 3	0
θ		-	-	-1: (-9 / 50) = 5 5 / 9	-	-	-	-	-3 1 / 3: (-14 / 15) = 3 4 / 7	-

4. Dönüşümü gerçekleştiriyoruz.

temel	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	132	0	1	27 / 140	0	0	0	0	0	-1 / 14
x 4	1600	0	0	50 / 7	1	0	0	0	0	-25 / 7
x 1	54	1	0	-67 / 140	0	0	0	0	0	3 / 14
x 6	6540	0	0	234 / 7	0	0	1	0	0	-110 / 7
x 5	6	0	0	317 / 140	0	1	0	0	0	-33 / 14
x 7	2	0	0	27 / 70	0	0	0	1	0	-8 / 7
x 8	1	0	0	27 / 140	0	0	0	0	1	-15 / 14
F (X0)	-38400	0	0	-5 / 14	0	0	0	0	0	-25 / 7

Çözüm tamsayı çıktı. Optimal tamsayı tasarımı şu şekilde yazılabilir: x 1 = 54, x 2 = 132. F (X) = 38400