: Görevler doğrusal programlama(LPP)

1. Doğrusal programlama

2. Doğrusal programlama problemlerinin türleri

3. LPP kayıt biçimleri

4. Doğrusal programlama problemlerinin kanonik formu

Doğrusal programlama

Doğrusal programlama, doğrusal programlama için çeşitli değişkenlerin doğrusal fonksiyonlarının uç noktalarını bulmak için yöntemlerin geliştirilmesinde kullanılan matematiksel programlamanın bir dalıdır. ek kısıtlamalar değişkenlere yüklenir.

LP yöntemleri, çözülen problemlerin türüne göre evrensel ve özel yöntemler olarak ikiye ayrılır. Kullanarak evrensel yöntemler herhangi bir doğrusal programlama problemi (LPP) çözülebilir. Özel olanlar, problem modelinin özelliklerini, amaç fonksiyonunu ve kısıtlamalar sistemini dikkate alır.

Doğrusal programlama problemlerinin temel özelliği, amaç fonksiyonunun ekstremumunun uygulanabilir çözümler bölgesinin sınırında olmasıdır.

Şekil 1 - Amaç fonksiyonunun ekstremumu

LPP'nin matematiksel modeli yazılır Aşağıdaki şekilde:

maks (veya min) Z = z (X), (1)

ODR sistem tarafından temsil edilebilir lineer denklemler veya eşitsizlikler.

Vektör X = (x 1, x 2, .... x p) bir kontrol veya kontrol eylemi vektörüdür.

Z = z (X) optimallik kriterinin uç bir değere ulaştığı uygulanabilir bir tasarım X'e optimal denir ve X * ile gösterilir, amaç fonksiyonunun uç değerine Z * = z (X *) denir.

Doğrusal programlama problemlerinin türleri

Doğrusal programlama yöntemleri yaygın olarak kullanılmaktadır. endüstriyel Girişimcilik optimize ederken üretim programı, atölyeler arasında ve zaman aralıklarına göre dağılımı, ekipman çeşitlerinin yüklenmesi, kargo akışlarının planlanması, bir ciro planının belirlenmesi vb.

En yaygın görev türü kaynakların optimal kullanımı sorunu. Piyasa koşullarına göre bir miktar üretim birimi (atölye, işletme, dernek vb.) Tekniksel kabiliyetler ve mevcut kaynaklar, n'yi serbest bırakabilir farklı şekiller j olarak bilinen ürünler

Ürün üretirken, işletme, sayısı m ile gösterilecek olan mevcut kaynaklar ve B = (b 1, b 2, ..., b т) kaynak vektörü ile sınırlıdır. j'inci ürünün bir biriminin üretimi için i-inci kaynağın tüketim oranını gösteren teknolojik katsayılar a ij de bilinmektedir. Serbest bırakma verimliliği birim j veüretim, bir kar p j ile karakterize edilir.

Verilen kaynaklar için işletmenin karını maksimize eden X = (x 1, x 2, ..., x p) üretim planının belirlenmesi gerekmektedir.

Amaç fonksiyonu şuna benzer

kısıtlamalarla

Genellikle ürün yelpazesi ana kuruluş tarafından belirlenir, yani hacimleri bazı D n j ve D sınırları içinde j'de kapatılmalıdır: ardından aşağıdaki kısıtlama belirlenir:

Kaynakların optimal kullanımı probleminin modelinin altında yatan şey işletmenin yıllık üretim programının optimizasyon modelleri... Model, ekipman işletim süresi fonu üzerinde kısıtlamalar içermektedir.

Önceki gösterimi koruyarak sırasıyla b j ve c j ile satış fiyatını ve birim maliyetleri yazıyoruz. j-th ürünleri... Aşağıdakiler bir optimallik kriteri olarak alınabilir:

1) maksimum kar

2) minimum üretim maliyetleri

3) değer açısından maksimum çıktı (ürün satışlarından elde edilen gelir)

Örnek. Firma 1, 2, 3 ve 4 çeşit ürün üretebilmektedir. Her hacimde satış sağlanmaktadır. Çeyrek boyunca, işletme 100 adam vardiyası, 260 kg ağırlığında yarı mamul ürünler, 370 makine vardiyası için makine teçhizatı iş gücüne sahiptir. Her bir ürün türünün kaynak tüketimi ve birim başına kâr oranları Tablo 1'de sunulmuştur.

Gerekli:

a) maksimum kârın elde edildiği üretim planını belirleme probleminin matematiksel bir modelini hazırlamak;

b) Sorunu, üçüncü ürünün birim sayısı 3 katı olacak şekilde eksiksiz bir set şartıyla çözün. daha fazla miktar birincinin birimleri;

c) ne zaman optimal ürün çeşitliliğini bulun ek koşullar: ilk ürün en az 25 adet, üçüncüsü - 30'dan fazla değil ve ikinci ve dördüncü - 1: 3 oranında üretilmelidir.

tablo 1

İlk veri

Problemin matematiksel modeli:

amaç fonksiyonu:

maks: Z = 40x 1 + 50x 2 + 100x 3 + 80x 4

kısıtlamalar ile:

a) emek kaynakları için:

2.5x 1 + 2.5x 2 + 2x 3 + 1.5x 4? 100;

yarı mamul ürünler için:

4x 1 + 10x 2 + 4x 3 + 6x 4? 260;

makine ekipmanında:

8x 1 + 7x 2 + 4x 3 + 10x 4? 370;

negatif olmama koşulu:

B) ek gereksinim tamamlama koşulu ile ifade edilecektir

3x 1 = x 3, yani 3x 1 x 3 = 0;

c) Sınır koşulları ve ekipmanın durumu şu şekilde sunulur: x 1? 25,

x 3? 30, 3 * x 2 = x 4.

Sipariş verme veya değiştirilebilir ekipman gruplarını yükleme sorunu. Bu farklı üretim ve teknolojik özelliklere sahip, ancak siparişleri yerine getirme anlamında değiştirilebilir m (i = 1, ..., m) işletmeler (atölyeler, takım tezgahları, sanatçılar) arasındaki siparişlerin dağılımına ilişkin. Görevin tamamlanacağı ve verimlilik göstergesinin aşırı bir değere ulaşacağı siparişlerin verilmesi için böyle bir plan yapılması gerekiyor.

Problemi matematiksel olarak formüle edelim. m homojen ekipman grubu üzerinde n çeşit ürün üretmek gerekli olsun. Her ürün türü için yayın planı belirli bir süre x j (j = 1,2, ... p) kümesi tarafından verilir. Her tür ekipmanın gücü sınırlıdır ve b i'ye eşittir. A = || a ij || teknolojik matrisi bilinmektedir; burada a ij, birim zaman başına üretilen j'inci ürünün birim sayısıdır. i. ekipman... C matrisi, bir maliyet matrisidir; burada c ij, j'inci ürünün bir biriminin i'inci ekipmana bırakılmasıyla ilişkili maliyetlerdir. X, üretilen ürünlerin hacminin vektörüdür.

Problem modeli aşağıdaki formu alacaktır:

amaç fonksiyonu, tüm siparişlerin uygulanmasının maliyetlerini en aza indirmektir.

kısıtlamalar ile:

a) ekipman gücü ile

b) üretim için

c) negatif olmama koşulu

Bu soruna dağıtım sorunu veya dağıtım sorunu denir.

Bazı ürün türleri için planı aşmasına izin verilirse, kısıtlama (b) biçimini alacaktır.

Ayrıca hedef kâr olarak da alabilirsiniz:

a) maksimum kar

b) takım tezgahı süresinin minimum maliyetleri

Çünkü herhangi bir model basitleştirici önkoşullar içerir; elde edilen sonuçların doğru uygulanması için, bu basitleştirmelerin özünün net bir şekilde anlaşılması gerekir, bu da nihayetinde kabul edilebilirliği veya kabul edilemezliği hakkında bir sonuca varmamızı sağlar. Ele alınan modellerdeki en önemli sadeleştirme, kaynak tüketim hacmi ile üretim hacmi arasında, a ij maliyet oranları kullanılarak belirlenen doğru orantılı (doğrusal) bir ilişkinin varsayımıdır. Açıkçası, bu varsayım her zaman yerine getirilmez. Bu nedenle, X üretim programındaki değişikliğe bağlı olarak birçok kaynağın (örneğin sabit kıymetlerin) tüketim hacimleri hızla değişir. Diğer basitleştirici varsayımlar, j fiyatlarının xj hacimlerinden bağımsız olduğu varsayımını içerir, bu yalnızca geçerlidir. değişimlerinin belirli sınırları için. Bu "güvenlik açıklarını" bilmek de önemlidir, çünkü bunlar modeli geliştirmek için temel yönergeleri gösterir.

LPP kayıt formları

LPP kaydının 3 biçimi vardır:

1) fonksiyonlar olarak

maks (veya min) Z =, maks (veya min) Z =,

2) vektör formu

(vektörlerin nokta çarpımı)

kısıtlamalarla

A 1 x 1 + A 2 x 2 + .. + A n x n = B

vektörler nerede

C = (C 1, C 2 .. Cn), X = (X 1, X 2 .. X n) ve.

3) matris formu

kısıtlamalarla

burada С = (с 1, с 2, ... с n),

Doğrusal Programlama Problemlerinin Kanonik Biçimi

Bir lineer programlama problemindeki tüm kısıtlamalar denklem ise ve tüm x j değişkenlerine negatif olmayan koşullar empoze ediliyorsa, buna kanonik formda lineer programlama problemi veya kanonik lineer programlama problemi (LPC) denir.

kısıtlamalarla

LPP'den CLPP'ye geçebilmek için eşitsizlik kısıtlarından eşitlik kısıtlarına geçmek ve negatif olmama koşullarına uymayan değişkenleri değiştirmek gerekir.

tüzük ZLP'yi getirmek kanonik forma:

1) kısıtlamalarda ise sağ kısım negatif ise, bu limit -1 ile çarpılmalıdır;

2) Kısıtlar arasında eşitsizlikler varsa, ek negatif olmayan değişkenler dahil edilerek bunlar eşitliklere dönüştürülür;

3) bazı xk değişkeninin işaret kısıtlaması yoksa, o zaman amaç fonksiyonunda ve tüm kısıtlamalarda iki yeni negatif olmayan değişken arasındaki farkla değiştirilir: xk = x * k - xl, burada l bileşik indekstir, x * k> =, xl > = 0.

Bir örneğe bakalım. Kanonik forma getirelim:

x 4, x 5, x 6 değişkenlerini eşitleyen kısıtlamalar sisteminin her bir denklemine giriş yapalım. Sistem eşitlikler şeklinde yazılacak ve kısıtlamalar sisteminin birinci ve üçüncü denklemlerinde x 4, x 6 değişkenleri girilecektir. Sol Taraf"+" işaretiyle ve ikinci denklemde "-" işaretiyle x 5 girilir.

Kanonik formdaki serbest terimler pozitif olmalıdır, bunun için son iki denklemi -1 ile çarpıyoruz:

Doğrusal programlama problemlerini yazmanın kanonik biçiminde, kısıtlama sistemine dahil edilen tüm değişkenler negatif olmamalıdır. varsayalım ki

değiştirme verilen ifade kısıtlama sistemine ve hedef fonksiyon ve değişkenleri indeksin artan sırasına göre yazarsak, kanonik biçimde sunulan bir doğrusal programlama problemi elde ederiz:

optimizasyon simpleks doğrusal programlama

kanonik biçim, amaç fonksiyonunu maksimize etmek isteniyorsa, sistemin tüm kısıtları denklemlerdir ve tüm değişkenlere negatif olmama koşulu uygulanır.

Doğrusal programlama problemi şu şekilde verilmektedir: simetrik şekil, amaç fonksiyonunu maksimize etmek isteniyorsa, sistemin tüm kısıtlamaları "" eşitsizliğidir (veya amaç fonksiyonunu en aza indirmek için sistemin tüm kısıtlamaları "" eşitsizliğidir) ve tüm değişkenlere negatif olmama koşulu uygulanır.

Sayı kümesi denir kabul edilebilir karar (plan) LPP kısıtlama sistemini karşılıyorsa.

Tüm uygun çözümlerin kümesine denir. uygulanabilir çözümlerin alanı(ODR).

Fonksiyonun maksimum (minimum) değerine ulaşılan uygun bir çözüme denir. LPP'nin optimal planı.

"Plan" ve "optimal plan" terimleri ekonomik uygulamalardan doğmuştur.

LPP gösteriminin üç biçimi de, bir biçimden diğerine geçiş için algoritmalar olması anlamında eşdeğerdir. Böylece, bir problemi formlardan birinde çözmenin bir yolu varsa, o zaman başka herhangi bir formda verilen bir problem için en uygun planı her zaman belirleyebilirsiniz. Problem simetrik bir biçimde çözülür. grafiksel olarak, ve kurallı biçimde - simpleks yöntemiyle.

Bir formdan diğerine geçiş için algoritmaları ele alalım.

• 
  Simetrik  kanonik. Geçiş, her eşitsizliğin sol tarafına negatif olmayan bir değişken eklenerek gerçekleştirilir. Eşitsizlik “≤” ise denge değişkeni eşitsizliğin sol tarafına “+” işareti ile eklenir. Eşitsizlik "" ise, denge değişkeni eşitsizliğin sol tarafına "-" işaretiyle eklenir. Tanıtılan yeni değişkenler denir bilanço... Z fonksiyonunu minimize etme problemi, fonksiyonu (–Z) maksimize etme problemi ile değiştirilir ve min Z = –max (–Z) şeklinde kullanılır.
• 
  Kanonik  simetrik. Böyle bir geçişi uygulamak için, denklem sisteminin genel bir çözümü - kısıtlamalar bulunur, amaç fonksiyonu serbest değişkenler cinsinden ifade edilir. Ayrıca, temel değişkenlerin negatif olmamasını kullanarak, onları problemden hariç tutabilirsiniz. Problemin simetrik formu, sadece serbest değişkenleri ilişkilendiren eşitsizlikleri ve sadece serbest değişkenlere bağlı olan bir amaç fonksiyonunu içerecektir. Temel değişkenlerin değerleri, orijinal denklem sisteminin genel çözümünden bulunur.
• 
  Genel  kanonik. Negatif olmama koşuluna tabi olmayan her değişken, negatif olmayan iki yeni değişkenin farkı olarak temsil edilir. Simetrikten kanonik forma geçişte anlatıldığı gibi, her eşitsizliğin sol tarafına bir denge değişkeni getirilerek eşitsizlikler denklemlere dönüştürülür. Simetrikten kanonik forma geçişte anlatıldığı gibi Z fonksiyonunu minimize etme probleminin yerini (–Z) fonksiyonunu maksimize etme problemi almıştır.

1. Doğrusal programlama problemini çözmek için grafiksel bir yöntem

Simetrik bir biçimde verilen LPP'yi çözmek için grafiksel yöntem kullanılır. Bu yöntem en etkili şekilde iki değişkenli problemleri çözmek için kullanılır, çünkü grafik yapılar gerektirir. Üç değişken durumunda, yapılar r 3 , dört değişken olması durumunda, r 4 vesaire.

nokta kümesi denir dışbükey kümenin herhangi iki noktası için onları bağlayan bir parça içeriyorsa.

örnek 1

Düzlemde aşağıdaki nokta kümeleri dışbükeydir:

Düzlemde aşağıdaki nokta kümeleri dışbükey değildir:

teorem 1 Herhangi bir sayıda dışbükey kümenin kesişimi bir dışbükey kümedir.

Teorem 2 İki keyfi nokta olsun ve uzayda r n... Sonra segmentin herhangi bir noktası için [ PQ] yürütülmelidir:. nerede.

hiper düzlem boşlukta r n denklemi sağlayan noktalar kümesidir. İki boyutlu durumda hiperdüzlemin düz bir çizgi olduğuna dikkat edin.

Yarım boşluk veya eşitsizliklerinden birini sağlayan noktalar kümesidir. Hiperdüzlem uzayın noktalarını iki yarım uzaya böler. İki boyutlu durumda, hiperdüzlem bir yarı düzlemdir.

teorem 3 Yarım uzay dışbükey bir kümedir.

Sonuç Herhangi bir sayıda yarım uzayın kesişimi bir dışbükey kümedir.

çokyüzlü bir veya daha fazla yarım uzayın kesişimine denir. İki boyutlu durumdaki bir çokyüzlüye çokgen denir.

Örnek 2

Aşağıdaki kümeler çokgenlerdir.

Sınırlı set

Sınırsız set

Tek nokta

Boş küme

Bir dışbükey kümenin bir noktasına denir açısal kümeden diğer iki noktayı birleştiren herhangi bir doğru parçasının içinde yer almıyorsa.

Örnek 3

Bir üçgenin köşe noktaları köşeleridir (üç tane vardır). Bir dairenin köşe noktaları, onu sınırlayan dairenin noktalarıdır (sonsuz sayıda vardır).

Bir polihedronun köşe noktasına denir tepe.

Simetrik bir biçimde verilen bir LPP'yi düşünün.

teorem 4 LPP'nin optimal tasarımı, kısıtlama sistemi tarafından belirlenen çözüm politopunun tepe noktasına karşılık gelir.

Milletvekilinin Görevleri

Genel LPP arandı <,=,>=) bi (i = 1, n) (2) sağlanan xj>

Simetrik < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > kanonik karışık.

min f (x) = -maks (-f (x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Amaç fonksiyonunun ve LPP kısıtlamalarının geometrik yorumu. ZLP'nin geometrik formülasyonu.

Problem f = c1x1 + c2x2-max (1) olsun

a11x1 + a12x2<=b1 }

am1x1 + am2x2<=bm}

x1> = 0, x2> = 0 (3)

Problemin planı (x1, x2) düzlemde bir noktadır. Her eşitsizliği ile-biz 2 temsil eder. yarı düzlemdir. Yarım düzlem bir dışbükey kümedir. dışbükey bu kümeye ait doğru parçayı bağlayan (x1 ve x2) noktalarının da kümeye ait olduğu kümedir. C-ma 2, yarım düzlemlerin kesişimidir. Geçerken şunları alabilirsiniz:

1) dışbükey çokgen kapalı alan.

2) dışbükey açık çokgen alan

3) tek nokta

4) boş küme

5) ışın ve segment

Amaç fonksiyonunun geometrik yorumu: f-tion 1, seviye çizgileri (amaç fonksiyonunun sabit değerindeki çizgiler) olarak adlandırılan bir paralel düz çizgiler ailesidir. Fonksiyonun x1 ve x2'ye göre kısmi türevleri, eksenlerin koordinatları boyunca amaç fonksiyonunun artış oranını gösterir. vektör gradyan amaç fonksiyonunda en hızlı artışın yönünü gösterir Problem 1-3 için vektör-gradyan = (с1; с2) (0,0) noktasından ayrılır ve koordinatları (с1; с2) olan noktaya yönlendirilir. . Gradyan vektörü, seviye çizgilerine diktir. Yarım düzlemlerin kesişimine denir. kabul edilebilir çözümlerin alanı (ODS).

Ana LP teoremi. Şematik diyagram Bu teoremden çıkan LPP'nin çözümleri.

LPP'nin bir çözümü varsa, amaç fonksiyonu uç değerine, tasarım çokyüzlülüğünün uç noktalarından en az birinde ulaşır. Amaç fonksiyonu birden fazla uç noktada uç değere ulaşırsa, bunların dışbükey lineer birleşimi olan bir ve buna ulaşır.Herhangi bir noktada aynı değer. NS LPP'nin kararı bir tablo girişini manuel olarak kullanmak uygundur.

BP		SP -Xm + 1 -Xm + 2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
F	yuh	bo1 bo2 bon-m

Simpleks yöntemi algoritması.

1. problem modelini kanonik forma getirmek;

2. ilk referans planını bulun;

3. Problemi daha basit bir şekilde yazın. tablo;

5. Yeni bir temel plana, yeni bir sim'e gidin. tablo. Yeni bir temel plana geçmek için bir temel değişkeni ücretsiz olanla değiştirmek yeterlidir. Temele dahil edilen değişken ve karşılık gelen çözümleme sütunu, mutlak değerdeki f-satırının en büyük negatif öğesi tarafından belirlenir. Temelden hariç tutulan değişken ve karşılık gelen çözümleme çizgisi, en küçük tek yönlü ilişki ile belirlenir, yani. tek bir sütunun elemanlarının, çözümleme sütununun karşılık gelen elemanına oranı. Simpleks oranı, negatif olmayan bir değerdir. Çözümleme çizgisinin ve çözümleme sütununun kesişiminde, buna göre bir çözümleme elemanı vardır. tek yönlü dönüşüm bir sonrakinde. kurala göre: 1. izin veren çizginin öğeleri izin veren öğeye bölünür; 2. izin verilen sütunun öğeleri, izin veren öğeye bölünür ve işareti tersine değiştirir; 3.Tablo elemanlarının geri kalanı dikdörtgen kuralına göre kaydırılır.:

bij iki bkj = (bkj * bis-bij * bks) / bi

Aya dualite teoremi.

ikili problemlerden birinin optimal bir planı varsa, diğeri çözülebilir, yani. bir opt.plana sahiptir. Bu durumda amaç fonksiyonlarının uç değerleri çakışır (j = 1'den n'ye) Σcjxj * = (i = 1'den m'ye) Σbiyi * orijinalde ise. amaç fonksiyonu planlar setinde sınırsızdır, o zaman ikili görev kısıtlama sistemi tutarsız.

TK matrisinin rankı üzerindeki teorem.

Taşıma probleminin A matrisinin rankı, denklem sayısından bir eksiktir: r (A) = m + n-1.

39. LPP'nin ilk temel planını oluşturmak için algoritma.

İlk referans planını bulmak için aşağıdakileri önerebilirsiniz: algoritma:

1.Serbest üyeler sütununun tüm elemanları negatif olmayacak şekilde problemi bir Jordan tablosu şeklinde yazın, yani. eşitsizliği аio> = 0 (i = 1, m) tutar. Serbest terimlerin negatif olduğu bu-biz denklemleri önceden -1 ile çarpılır.

		-x1 ... .. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	aşk	am1… .. amn
f =		-c1…. -cn

Sol sütundaki sıfırları karşılık gelen x ile değiştirerek tabloyu Jordan istisna adımlarında dönüştürün. Ayrıca her adımda izinli seçilebilir en az bir pozitif öğe içeren herhangi bir sütun. İzin verilen satır, serbest üyelerin izin verilen sütunun karşılık gelen pozitif öğelerine oranlarının en küçüğü tarafından belirlenir. İstisnalar sürecinde, tüm elemanları sıfır olan ve serbest terimi sıfır olmayan bir 0 satırı varsa, o zaman kısıtlayıcı denklemlerin s-ma'sının çözümü yoktur. Serbest terim dışında başka pozitif öğe olmayan bir 0 satırı varsa, o zaman c-ma kısıtlayıcı denklemlerin negatif olmayan çözümleri yoktur Eğer c-ma kısıtlayıcı denklemler ise eklem yeri, daha sonra belirli sayıda adımdan sonra sol sütundaki tüm sıfırlar x ile değiştirilecek ve böylece belirli bir temel ve sonuç olarak ilgili destek planı elde edilecektir.

40. LPP'nin optimal temel planını oluşturmak için algoritma.

Ho'nun ilk destek planı optimallik açısından test edilir.

f-sırasında (kesme dışında) hiçbir olumsuz unsur yoksa, -plan optimaldir. f-satırı da sıfır eleman içermiyorsa, optimal plan benzersizdir; elemanlar arasında en az bir sıfır varsa, sonsuz sayıda optimal tasarım vardır. f-sırasında en az bir negatif eleman varsa ve karşılık gelen sütunda pozitif eleman yoksa, amaç fonksiyonu kabul edilebilir bölgede sınırlı değildir. Sorun çözülemez. F-satırında en az bir negatif unsur varsa ve böyle bir unsurun bulunduğu her sütunda en az bir pozitif unsur varsa, o zaman optimal olana daha yakın olan yeni bir referans planına gidebiliriz. Bunu yapmak için, f-satırında negatif elemanlı sütun şu şekilde alınır: müsamahakar; çözümleme dizisi minimal simpleks bağıntısı ile belirlenir ve Jordan eliminasyonu adımı alınır. Ortaya çıkan referans planı, optimallik için yeniden incelenir. Bu, optimal bir temel plan bulunana veya problemin karar verilemez olduğu bulunana kadar tekrarlanır.

Gomori yönteminin algoritması.

1. Problemin optimal planı simpleks yöntemi ile bulunur. Optimal planın tüm bileşenleri ayrılmazsa, o zaman optimaldir. Aksi takdirde, 2. adıma gidin

2. İntegral olmayan bileşenlerden aşağıdakileri içereni seçin: kesirli kısım en büyüğüdür ve tek yönlü tablonun ilgili satırına göre, formülle doğru kesmeyi formüle edin

(n-m, s = 1) ∑ (αkm + 1) Xm + 1≥ (βk)

3. Formüle edilmiş eşitsizliği eşdeğer bir sıfır eşitliğe dönüştürün ve tek yönlü tablo tamsayı olmayan bir optimal planla

4. Elde edilen genişletilmiş problem simpleks yöntemiyle çözülür. Ortaya çıkan plan bir tamsayı nova değilse 2. adıma gidin.

Tamsayısız serbest terimli ve tamsayılı bir çizgiyi çözme sürecinde diğer katsayılar ortaya çıkarsa, karşılık gelen denklemin tamsayılarda çözümü yoktur. Bu durumda, orijinal problem de tamsayılarda çözülemez.Gomori yönteminin uygulaması sınırlıdır. Yardımı ile küçük sorunları çözmeniz önerilir, çünkü etkileşimlerin sayısı çok büyük olabilir.

çeşitli şekiller LPP kayıtları (genel, kanonik, simetrik)

Milletvekilinin Görevleri: optimal planın belirlenmesi, optimal üretim hacminin belirlenmesi, ürünlerin / ev bitkileri ile optimal kombinasyonunun belirlenmesi, optimal varlık paketinin oluşturulması, bankanın kârının maksimize edilmesi, vb.

Ortak LPP denir maksimizasyon (minimizasyon) problemi doğrusal fonksiyon f = Σcj * xj-maks (min) (1) doğrusal kısıtlamalar altında ∑aij * xj (=<,=,>=) bi (i = 1, n) (2) sağlanır xj> = 0 (j = 1, n1), xj-keyfi (j = n1 + 1, n) (3) burada cj, aij, bi-sabit sayılar .

Simetrik LPP için gösterim şekli, işaretli eşitsizliklerde doğrusal kısıtlamalar altında fonksiyonu (1) maksimize etme problemidir.< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >veya = ve negatif olmayan değişkenler. kanonik LPP için gösterim şekli, doğrusal kısıtlamalar, eşitlikler ve negatif olmayan değişkenler altındaki maksimum fonksiyon (1) problemidir. Başka herhangi bir form denir karışık.

min f (x) = -maks (-f (x))

Bir eşitsizliğin bir denkleme dönüştürülmesi ve bunun tersi, Lemma temelinde gerçekleştirilir: bir eşitsizliğin her x1 ... xn çözümü a1x1 + ... + anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>= 0 (7) ve tersi. Denklem 6'nın herhangi bir x1… xn, xn + 1 çözümü ve 7 eşitsizliği, 5 eşitsizliğinin x1… xn çözümüne karşılık gelir.

Sim formunun arkasından kanonik formun arkasına gitmek için şunu girmelisiniz: denge (düzeyleme) değişkenleri. Bu, eşitsizlik teoremine dayanmaktadır: herhangi bir eşitsizlik, ur-i veya en basit eşitsizlik olarak temsil edilebilir.

Amaç fonksiyonu ve kısıtlar sisteminin yazılması farklı görevler doğrusal programlama aynı değildir: bazı problemlerde amaç fonksiyonunun minimumunu ve diğerlerinde maksimumu bulmak gerekir; bazı durumlarda aranan değişkenler bir indekse, diğerlerinde ise iki indekse bağlıdır; bazı problemlerde kısıtlamalar bir sistem şeklinde verilir doğrusal eşitsizlikler, ve diğerlerinde - bir doğrusal denklem sistemi şeklinde. Pratikte, bazı kısıtların lineer eşitsizlikler ve bazılarının lineer denklemler şeklinde olduğu problemler de mümkündür. Ayrıca, tüm problemler değişkenlerin negatif olmamasını gerektirmeyebilir.

Bu kadar çeşitli doğrusal programlama problemlerini hesaba katmak, kendi sınıflarını çözmek için özel yöntemlerin geliştirilmesini gerektirir. Dikkatimizi, sözde kanonik formda yazılan doğrusal programlamanın genel özellikleri ve yöntemlerinin incelenmesine odaklayacağız.

Doğrusal bir programlama probleminde, başlangıç ​​kısıtlamaları sistemi şu türden denklemler biçimini alırsa,

ve doğrusal amaç fonksiyonunun maksimumunu bulmanız gerekir.

daha sonra doğrusal programlama probleminin kanonik formda yazıldığı kabul edilir.

Herhangi bir doğrusal programlama problemi kolaylıkla kanonik forma indirgenebilir. V Genel dava Bunun için, ilk olarak, amaç fonksiyonu minimize etme problemini, onu maksimize etme problemine indirgemek, ikinci olarak, eşitsizlik kısıtlamalarından eşitlik kısıtlamalarına geçmek ve üçüncü olarak, özne olmayan değişkenleri değiştirmek yeterlidir. negatif olmama durumuna.

Fonksiyonun minimumunu bulmanız gerektiğinde , fonksiyonun maksimumunu bulmaya devam edebiliriz. , ifade doğru olduğundan:
.

eşitsizlik kısıtlaması asıl sorun, formu olan ", Sol tarafına negatif olmayan ek bir değişken ve formun eşitsizlik kısıtı eklenerek denklem kısıtına dönüştürülebilir" "- sol tarafından negatif olmayan ek bir değişken çıkararak.

Girilen ek negatif olmayan değişkenlerin sayısının her zaman orijinal kısıtlama sistemindeki eşitsizliklerin sayısına eşit olduğuna dikkat edin.

Girilen ek değişkenlerin çok özel bir ekonomik anlamı vardır. Dolayısıyla, orijinal doğrusal programlama probleminin kısıtlamaları, üretim kaynaklarının maliyetlerini ve kullanılabilirliğini yansıtıyorsa, o zaman Sayısal değer ek bir değişken, karşılık gelen kullanılmayan kaynağın miktarını gösterir.

Ayrıca bazı değişkenlerin negatif olmama koşuluna uymuyorsa, negatif olmayan iki değişkenle değiştirilmelidir. ve evlat edinme
.

Örnek... Aşağıdaki doğrusal optimizasyon problemini kurallı biçimde yazın: fonksiyonun minimumunu bulun
kısıtlamalarla

Çözüm

Bu problemde, amaç fonksiyonunun minimumunu bulmanız gerekiyor ve kısıtlamalar sistemi dört eşitsizlik içeriyor. Kanonik biçimde yazmak için eşitsizlik kısıtlarından denklem kısıtlarına geçmek ve ayrıca amaç fonksiyonunu dönüştürmek gerekir.

Problemin kısıtlar sistemine dahil edilen eşitsizlik sayısı dörde eşit olduğundan, bu geçiş negatif olmayan dört ek değişkenin eklenmesiyle gerçekleştirilmelidir. Bu durumda, ikinci ve dördüncü eşitsizlikler “işaretini içerir. ", Böylece sol taraflarına ek değişkenler ekliyoruz. Birinci ve üçüncü eşitsizliklerde - “işareti” ", Sonra ek değişkenleri sol taraflarından çıkarıyoruz.

Ayrıca tüm işaretleri tersine çevirerek amaç fonksiyonunu dönüştürüyoruz ve maksimumunu buluyoruz.

Böylece, bu doğrusal programlama problemi aşağıdaki gibi yazılacaktır. kanonik olarak:

maksimum fonksiyonu bul

kısıtlamalarla

Genel durumda, hem denklemler hem de eşitsizlikler kısıtlayıcı olacak şekilde bir doğrusal programlama problemi yazılır ve değişkenler hem negatif olmayan hem de keyfi değişken olabilir. Tüm kısıtların denklem olması ve tüm değişkenlerin negatif olmama koşulunu sağlaması durumunda, doğrusal programlama problemine kanonik denir. Koordinat, vektör veya matris notasyonu ile temsil edilebilir.

1. Koordinat notasyonundaki kanonik doğrusal programlama problemi şu şekildedir:

.

Daha kompakt bir biçimde bu görev toplama işareti kullanılarak yazılabilir,

(1.7)

2. Vektör notasyonundaki kanonik doğrusal programlama problemi şu şekildedir:

(1.8)

nerede ,

.

3. Matris notasyonundaki kanonik doğrusal programlama problemi şu şekildedir:

(1.9)

, .

Buraya A- denklem sisteminin katsayı matrisi, NS- matris-sütun görev değişkenleri, Kısıtlama sisteminin sağ taraflarının matris sütunudur.

Genellikle kullanılan doğrusal programlama problemleridir. simetrik, matris notasyonunda forma sahip olan

(1.10)

(1.11)

1.4. getirmek ortak görev doğrusal programlama
kanonik forma

Doğrusal programlama problemlerinin çözümüne yönelik çoğu yöntemde, kısıtlar sisteminin, değişkenlerin negatif olmaması için denklemlerden ve doğal koşullardan oluştuğu varsayılır. Bununla birlikte, ekonomik problemlerin matematiksel modellerini derlerken, kısıtlamalar esas olarak eşitsizlik sistemlerine dönüştürülür, bu nedenle bir eşitsizlik sisteminden bir denklem sistemine geçebilmek gerekir. Bunun için aşağıdaki teoremi ispatlıyoruz.

Teorem 1.1. Eşitsizliği bir denklemle değiştirme. her karara eşitsizlikler

denklemin benzersiz bir çözümü var

ve eşitsizlik

, (1.14)

ve tersine, denklem (1.13) ve eşitsizliğin (1.14) her çözümüne, eşitsizliğin (1.12) benzersiz bir çözümüne karşılık gelir.

Kanıt.İzin vermek (1.12) eşitsizliğinin bir çözümüdür, o zaman. Bu eşitsizliğin sağ ve sol tarafları arasındaki farkı şu şekilde ifade ederiz:

Açıkça ... (1.13) denkleminde yerine değişken değerler , alırız

Böylece (1.13) denklemini ve (1.14) eşitsizliğini sağlar. Bu, teoremin ilk bölümünün kanıtlandığı anlamına gelir.

Şimdi denklem (1.13) ve eşitsizliği (1.14) sağlamasına izin verin, yani

VE

Son eşitliğin solundaki negatif olmayan niceliği atarak,

yani eşitsizliği (1.12) karşılar. Teorem ispatlandı.

Eşitsizlik varsa, eksi işaretiyle sol tarafına negatif olmayan ek bir değişken eklenmelidir, yani.

Denklemlere dönüştürmek için eşitsizlik kısıtlamalarına dahil edilen negatif olmayan değişkenlere denir. ek değişkenler... Amaç fonksiyonuna sıfır katsayılı ek değişkenler eklenir ve bu nedenle değerini etkilemez.

Problemin keyfi olarak değişen değişkenlere sahip olması durumunda, bu tür herhangi bir değişken, negatif olmayan iki değişkenin farkı ile değiştirilir, yani. , nerede ve .

Bazen problemde minimumu bulmaktan maksimumu bulmaya ya da tam tersini yapmak gerekir. Bunu yapmak için, amaç fonksiyonunun tüm katsayılarının işaretlerini tersine değiştirmek ve sorunun geri kalanını değiştirmeden bırakmak yeterlidir. Bu şekilde elde edilen maksimum ve minimum problemlerin optimal çözümleri ve amaç fonksiyonlarının değerleri örtüşmektedir. optimal çözümler sadece işarette farklılık gösterir.

Örnek 1.1. Doğrusal programlama problemini kanonik forma getirin.

NS

Çözüm... Şimdi amaç fonksiyonunun maksimumunu bulma problemine dönelim. Bunu yapmak için amaç fonksiyonu katsayılarının işaretlerini değiştiririz. Kısıtlar sistemini ikinci ve üçüncü eşitsizliklerin denklemlerine dönüştürmek için negatif olmayan ek değişkenler sunuyoruz ( matematiksel model bu işlem D harfi ile işaretlenmiştir). Değişken, ikinci eşitsizliğin sol tarafında "+" işaretiyle tanıtılır, çünkü eşitsizlik formdadır. Değişken, eşitsizlik şeklinde olduğundan, üçüncü eşitsizliğin sol tarafında "-" işaretiyle tanıtılır. Değişkenler, sıfıra eşit bir katsayı ile amaç fonksiyonuna girilir. Negatif olmama koşuluna tabi olmayan değişken, fark ile değiştirilir. , ... Problemi kanonik biçimde yazma

Bazı durumlarda, döküm yapmak gerekli hale gelir kurallı görev simetrik bir problem için Bir örneğe bakalım.

Örnek 1.2. Doğrusal programlama problemini simetrik forma indirgeyin