Lineer matematiksel modellerin formları ve dönüşümleri. Doğrusal programlama probleminin matematiksel modelini oluşturma Doğrusal programlama modeline genel bakış

Ekonomik problemleri çözmenin temeli matematiksel modellerdir.

matematiksel model problem, problemin özünü tanımlayan bir dizi matematiksel ilişkidir.

• görev değişkeni seçimi
• bir kısıtlama sistemi hazırlamak
• amaç fonksiyonu seçimi

Görev değişkenleri ekonomik süreci tamamen karakterize eden X1, X2, Xn miktarları olarak adlandırılır. Genellikle bir vektör olarak yazılırlar: X=(X 1 , X 2 ,...,X n).

Kısıtlama sistemi görevler, ele alınan problemdeki sınırlı kaynakları tanımlayan bir dizi denklem ve eşitsizliktir.

hedef fonksiyon görev, görevin kalitesini karakterize eden ve uç noktasının bulunması gereken görev değişkenlerinin bir işlevi olarak adlandırılır.

Genel olarak bir doğrusal programlama problemi şu şekilde yazılabilir:

Bu giriş şu anlama gelir: amaç fonksiyonunun (1) uç noktasını ve karşılık gelen X=(X 1 , X 2 ,...,X n) değişkenlerini, bu değişkenlerin (2) kısıtlama sistemini karşılaması koşuluyla bulun ve -olumsuzluk durumları (3) .

Kabul Edilebilir Çözüm Bir doğrusal programlama probleminin (planı), kısıtlamalar sistemini ve negatif olmama koşullarını sağlayan herhangi bir n-boyutlu X=(X 1 , X 2 ,...,X n) vektörüdür.

Sorun formlarının uygulanabilir çözümleri (planları) kümesi uygulanabilir çözüm yelpazesi(ODR).

optimum çözüm Bir doğrusal programlama probleminin (planı), problemin, amaç fonksiyonunun bir uç noktaya ulaştığı uygulanabilir bir çözümüdür (planı).

Matematiksel bir model derleme örneği

Kaynakları kullanma görevi (hammaddeler)

Durum: n çeşit ürünün üretimi için m çeşit kaynak kullanılır. Matematiksel bir model yapın.

Bilinen:

• b ben (i = 1,2,3,...,m) her i'inci kaynak türünün rezervleridir;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n), birim hacim üretimi için her bir i'inci kaynak türünün maliyetidir. j-th tipi ürün;
• c j (j = 1,2,3,...,n), j'inci tip ürünün birim hacminin satışından elde edilen kârdır.

Kaynaklar (hammaddeler) üzerinde belirli kısıtlamalar ile maksimum kar sağlayan ürünlerin üretimi için bir plan yapılması gerekmektedir.

Çözüm:

X=(X 1 , X 2 ,...,X n) değişkenlerinin bir vektörünü tanıtıyoruz, burada x j (j = 1,2,...,n), j'inci tip üretim hacmidir. ürün.

Belirli bir xj ürün hacminin üretimi için i. tür kaynağın maliyetleri a ij xj'ye eşittir, bu nedenle, her tür ürünün üretimi için kaynakların kullanımına ilişkin kısıtlama şu şekildedir:
j'inci tip ürünün satışından elde edilen kâr c j x j'ye eşittir, yani amaç fonksiyonu şuna eşittir:

Cevap- Matematiksel model şuna benzer:

Doğrusal programlama probleminin kanonik formu

Genel durumda, bir doğrusal programlama problemi, hem denklemler hem de eşitsizlikler kısıtlama olacak ve değişkenler negatif olmayacak veya keyfi olarak değişebilecek şekilde yazılır.

Tüm kısıtlamaların denklem olduğu ve tüm değişkenlerin negatif olmama koşulunu sağladığı durumda, doğrusal programlama problemi denir. kanonik.

Koordinat, vektör ve matris notasyonu ile temsil edilebilir.

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

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

• A, denklem sisteminin katsayılarının matrisidir
• X, görev değişkenlerinin bir sütun matrisidir
• Ao, kısıtlama sisteminin sağ kısımlarının matris sütunudur.

Genellikle, simetrik olanlar olarak adlandırılan ve matris notasyonunda şu şekilde olan doğrusal programlama problemleri kullanılır:

Genel bir doğrusal programlama probleminin kanonik forma indirgenmesi

Doğrusal programlama problemlerini çözmeye 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 modellerini derlerken, kısıtlamalar esas olarak bir eşitsizlikler sistemi şeklinde oluşturulur, bu nedenle bir eşitsizlikler sisteminden bir denklem sistemine geçebilmek gerekir.

a 1 x 1 +a 2 x 2 +...+a n x n ≤b doğrusal eşitsizliğini alın ve sol tarafına x n+1 değerini ekleyin, böylece eşitsizlik a 1 x 1 +a 2 x 2 + eşitliği olur ...+a n x n +x n+1 =b. Üstelik bu x n+1 değeri negatif değildir.

Her şeyi bir örnekle ele alalım.

Doğrusal programlama problemini kanonik forma indirin:

Çözüm:
Amaç fonksiyonunun maksimumunu bulma problemine geçelim.
Bunu yapmak için amaç fonksiyonunun katsayılarının işaretlerini değiştiririz.
Kısıtlama sisteminin ikinci ve üçüncü eşitsizliklerini denklemlere dönüştürmek için, x 4 x 5 negatif olmayan ek değişkenleri tanıtıyoruz (bu işlem matematiksel modelde D harfi ile işaretlenmiştir).
Eşitsizlik "≤" biçiminde olduğu için x 4 değişkeni ikinci eşitsizliğin soluna "+" işaretiyle girilir.
Eşitsizlik "≥" biçiminde olduğu için x 5 değişkeni üçüncü eşitsizliğin soluna "-" işaretiyle girilir.
x 4 x 5 değişkenleri amaç fonksiyonuna bir katsayı ile girilir. sıfıra eşittir.
Problemi kanonik formda yazıyoruz.

DOĞRUSAL PROGRAMLAMA MODELİ

1 Doğrusal programlama modelinin matematiksel açıklaması

2 Doğrusal programlama modellerini uygulama yöntemleri

3 Çift doğrusal programlama problemi

Doğrusal programlama modeli(LP), çalışılan sistemde (nesnede) değişkenler ve amaç fonksiyonu üzerindeki kısıtlamalar varsa gerçekleşir doğrusal.

LP modelleri, iki ana uygulamalı problemi çözmek için kullanılır:

1) insan faaliyetinin herhangi bir alanında - sosyal, ekonomik, bilimsel, teknik ve askeri - optimal planlama. Örneğin, optimum üretim planlaması ile: finansal, işgücü ve diğer kaynakların dağıtımı, hammadde tedariki, envanter yönetimi vb.

2) ulaşım görevi (çeşitli ulaşım türleri için en uygun planı bulmak, çeşitli araçların çeşitli amaçlar için nesneler üzerinde dağıtılması için en uygun planı bulmak vb.)

DOĞRUSAL PROGRAMLAMA MODELİNİN MATEMATİKSEL AÇIKLAMASI

Değişkenlerin negatif olmayan değerlerini bulmak gerekir

eşitlikler ve eşitsizlikler şeklinde tatmin edici doğrusal kısıtlamalar

,

Nerede - verilen numaralar,

ve doğrusal amaç fonksiyonunun bir uç noktasını sağlamak

,

olarak yazılan sayılar nerede verilir?

Kabul Edilebilir Çözüm herhangi bir küme denir , koşulları karşılıyor.

Kabul edilebilir çözümler alanı tüm kabul edilebilir çözümlerin kümesidir.

En uygun çözüm
, hangisi için .

Notlar

1. İndirgenmiş LP modeli genel. Ayrıca orada standart Ve kanonik LP modellerinin formları.

2. varoluş koşulları LP modelinin uygulanması:

– kabul edilebilir çözümler kümesi boş değildir;

- amaç fonksiyonu tarafından sınırlandırılır (maksimum ararken en azından yukarıdan ve minimum ararken aşağıdan).

3.LP iki teorem üzerine kuruludur

teorem 1. Bir demet G, formun kısıtlama sistemi tarafından tanımlanan, dışbükey kapalı bir kümedir ( dışbükey çokyüzlü köşe noktalarında - zirveler.)

Teorem 2. Doğrusal form , dışbükey bir çokyüzlü üzerinde tanımlı

J=1,2,…,S

ben=s+1,s+2,…, M,

bu çokyüzlünün köşelerinden birinde bir uç noktaya ulaşır.

Bu teoreme lineer form ekstremum teoremi denir.

Weierstrass teoremine göre, optimal çözüm benzersizdir ve global bir ekstremumdur.

Genel bir analitik yaklaşım vardır. LP modelinin uygulanmasına - tek yönlü yöntem. Doğrusal programlama problemlerini çözerken, genellikle çözüm yoktur. Bu, aşağıdaki nedenlerle olur.

Birinci sebebi bir örnekle açıklayalım.

Böyle bir nedenle kısıtlamaların tutarsız olduğunu söylüyorlar. Kabul edilebilir çözümlerin alanı boş kümedir.

İkinci neden aşağıdaki örnekle yorumlanmıştır:

Bu durumda, uygulanabilir çözümlerin alanı yukarıdan sınırlandırılmamıştır. Kabul edilebilir çözümlerin alanı sınırlı değildir.

Doğrusal programlama geleneklerini izleyerek, LP problemine ekonomik bir yorum vereceğiz. Alalım M kaynak türleri. Tür kaynağı sayısı J eşittir . Bu kaynaklar üretmek için gereklidir. N mal türleri. Bu malların miktarını sembollerle gösterelim. sırasıyla. Öğe türü Ben maliyetler. Mal tipi imalatı Ben ile sınırlı olmalıdır sırasıyla. tipinde bir mal biriminin üretimi için Ben tüketilen kaynak türü J. Malların üretimi için böyle bir plan belirlemek gerekir ( ) böylece toplam maliyetleri minimum olur.

Gerçek nesnelerin işleyişini optimize etmek için kullanılan doğrusal programlama problemleri, önemli sayıda değişken ve kısıtlama içerir. Bu, onları grafiksel yöntemlerle çözmeyi imkansız kılar. Çok sayıda değişken ve kısıtlama ile yinelemeli hesaplama prosedürlerine dayanan cebirsel yöntemler kullanılır. Doğrusal programlamada, uygun bir başlangıç ​​çözümü oluşturma yollarında ve bir iterasyondan diğerine geçiş koşullarında farklılık gösteren birçok cebirsel yöntem geliştirilmiştir. Ancak, tüm bu yöntemler genel teorik ilkelere dayanmaktadır.

Ana teorik hükümlerin genelliği, doğrusal programlama problemlerini çözmek için cebirsel yöntemlerin büyük ölçüde birbirine benzemesine yol açar. Özellikle, hemen hemen her biri, bir doğrusal programlama probleminin standart (kanonik) bir forma önceden indirgenmesini gerektirir.

LP problemini çözmek için cebirsel yöntemler, onu şuna indirgemekle başlar: standart (kanonik) form:

,

,

Ben=1,..,N;J=1,..,M.

Herhangi bir doğrusal programlama problemi standart bir forma indirgenebilir. Genel modelin kanonik modelle karşılaştırılması, LP problemini standart forma indirgemek için önce eşitsizlikler sisteminden eşitliklere geçmek ve ikinci olarak tüm değişkenleri bu şekilde dönüştürmek gerektiği sonucuna varmamızı sağlar. negatif olmadıklarını.

Eşitliğe geçiş, türündeki eşitsizlikler için kısıtlamaların sol tarafına negatif olmayan bir artık değişkenin eklenmesi ve türündeki eşitsizlikler için soldan negatif olmayan bir fazla değişkenin çıkarılmasıyla gerçekleştirilir. Örneğin, eşitsizlik standart forma geçildiğinde ise eşitliğe dönüştürülür. ve eşitsizlik - eşitliğe . Bu durumda, hem artık değişken hem de fazla değişken negatif değildir.

Eşitsizliklerin sağ tarafının negatif olmadığı varsayılır. Aksi takdirde, bu, eşitsizliğin her iki tarafını "-1" ile çarparak ve işaretini ters çevirerek elde edilebilir.

Orijinal doğrusal programlama probleminde değişken işaretle sınırlı değilse, negatif olmayan iki değişkenin farkı olarak temsil edilebilir. , Nerede .

Değişkenlerin önemli bir özelliği herhangi bir kabul edilebilir çözüm için bunlardan yalnızca birinin pozitif bir değer alabilmesidir. Bunun anlamı, eğer , O ve tersi. Bu nedenle, artık olarak kabul edilebilir, ancak - gereksiz bir değişken olarak.

Örnek Bir doğrusal programlama problemi verilsin:

,

.

Standart bir forma getirmeniz gerekiyor. Orijinal problemin ilk eşitsizliğinin işaretine sahip olduğuna dikkat edin, bu nedenle, ona artık değişkeni dahil etmek gerekir. Sonuç olarak alıyoruz.

İkinci eşitsizliğin bir işareti vardır ve standart forma dönüşüm için artık bir değişkenin eklenmesini gerektirir, bu işlemi gerçekleştirerek elde ederiz.

Ayrıca, değişken işaretle sınırlı değildir. Bu nedenle, hem amaç fonksiyonunda hem de her iki kısıtlamada, fark ile değiştirilmelidir. . Yerine koymayı gerçekleştirdikten sonra, standart formda, orijinal probleme eşdeğer bir doğrusal programlama problemi elde ederiz:

.

Standart formda yazılan doğrusal programlama problemi, negatif olmama koşullarını dikkate alarak, doğrusal denklemler sisteminin çözümleri olan vektörler kümesi üzerinde amaç fonksiyonunun uç noktasını bulma problemidir. Bildiğiniz gibi, bir doğrusal denklem sisteminin çözümü olmayabilir, tek bir çözümü olabilir veya sonsuz sayıda çözümü olabilir. Amaç fonksiyonunun optimizasyonu ancak sistem sonsuz var birçok çözüm. Bir lineer denklem sistemi, eğer tutarlıysa (ana matrisin sırası, genişletilmiş olanın sırasına eşittir) ve ana matrisin sırası, sayısından küçükse, sonsuz sayıda çözüme sahiptir. bilinmeyenler

Kısıtlama sistemi matrisinin rankı şuna eşit olsun: M. Bu, matrisin en az bir küçük değere sahip olduğu anlamına gelir. M inci sıra sıfıra eşit değildir. Genelliği kaybetmeden, minörün matrisin sol üst köşesinde yer aldığını varsayabiliriz. Bu, her zaman değişkenlerin numaralandırılması değiştirilerek elde edilebilir. Bu sıfır olmayan sıra küçük M taban denir. Baştan bir sistem yapalım M sistemin denklemleri aşağıdaki gibi yazılır:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

FEDERAL EĞİTİM AJANSI

"PSKOV İNŞAAT VE EKONOMİ KOLEJİ" ÜZERİNE FGOU

Konu “Matematiksel Yöntemler”

Doğrusal programlama problemi

Ders çalışması

Öğrenci grubu 315-PO

Andreev Dimitri Aleksandroviç

Ders Sorumlusu

Vasilieva Natalia Anatolievna

Pskov 2009

giriiş

Bölüm Ι Doğrusal Programlama

§ 1 Doğrusal programlama probleminin genel formülasyonu

§ 2 Doğrusal programlama probleminin matematiksel modeli

§ 3 Doğrusal programlama probleminin kanonik formu

Bölüm ΙΙ Problemin simpleks yöntemle çözümü

§ 1 Sorunun bildirimi

§ 2 Problemin matematiksel bir modelini oluşturmak

§ Simplex yöntemiyle sorunu çözmek için 3 Algoritmalar

§ 4 Gauss yöntemiyle ilk referans çözümünün oluşturulması

§ 5 Problem çözümü

Çözüm

Edebiyat

giriiş

Şu anda, ulusal ekonomi sektörlerindeki planlama ve yönetim sorunlarının yanı sıra çok sayıda özel uygulamalı sorun, matematiksel programlama yöntemleriyle çözülmektedir. Optimizasyon problemlerini çözme alanında en gelişmiş doğrusal programlama yöntemleridir. Bu yöntemler, satış planlaması gibi çok çeşitli ticari faaliyet görevlerini yeterli doğrulukla tanımlamayı mümkün kılar; şehrin perakende ticaret ağının konumu; şehrin, ilçenin emtia arzının planlanması; ticari işletmeleri tedarikçilere bağlamak; malların rasyonel nakliyesinin organizasyonu; ticaret çalışanlarının pozisyonlara dağılımı; gıda ürünlerinin rasyonel satın alımlarının organizasyonu; kaynakların tahsisi; yatırım planlaması; sektörler arası ilişkilerin optimizasyonu; ticari ekipmanın değiştirilmesi; sınırlı bir alanda optimum ürün yelpazesinin belirlenmesi; rasyonel bir çalışma tarzının kurulması.

Doğrusal programlama problemlerinde, kısıtlama sistemindeki verimlilik kriteri ve fonksiyonları doğrusaldır.

Bir matematiksel programlama probleminde bir zaman değişkeni varsa ve etkinlik kriteri, işlemlerin zaman içindeki seyrini açıklayan denklemlerle ifade ediliyorsa, o zaman böyle bir problem dinamik programlama problemidir.

Birçok ekonomik modelde, sabit ve değişken faktörler arasındaki ilişki doğrusal olarak kabul edilebilir.

Ticari faaliyetlerde matematiksel programlama yöntemlerinin kullanılması, bir işadamı, ekonomist, finansör tarafından gerekli bilgilerin toplanması ve ardından matematik ile birlikte problemin kurulması ile ilişkilendirilir. Matematiksel programlama yöntemleri, standart programlar paketi biçiminde bir bilgisayarda zaten uygulandığından, bunlara erişim genellikle basit, otomatiktir ve herhangi bir özel zorluk teşkil etmez.

Daha sonra modelin çalışması, bilgilerin toplanmasını ve işlenmesini, işlenmiş bilgilerin bir bilgisayara girilmesini, gelişmiş program programlarına dayalı hesaplamaları ve son olarak, hesaplama sonuçlarının (kullanıcılar için uygun bir biçimde) yayınlanmasını içerir. üretim faaliyeti alanında kullanımları.

Bölüm Ι Doğrusal Programlama

§ 1 Doğrusal programlama probleminin genel formülasyonu

Doğrusal programlama, değişkenler arasında doğrusal bir ilişki ve doğrusal bir amaç fonksiyonu ile karakterize edilen aşırı sorunları çözme yöntemlerini inceleyen bir matematiksel programlama yönüdür. Doğrusal programlama problemlerini çözmek için problemin matematiksel modeli derlenir ve bir çözüm yöntemi seçilir.

Amaç fonksiyonu doğrusal bir form olarak temsil edilebiliyorsa ve sınırlı kaynaklarla olan ilişki doğrusal denklemler veya eşitsizlikler kullanılarak açıklanabiliyorsa, ticari faaliyet probleminin ifadesi doğrusal programlamanın matematiksel bir modeli olarak temsil edilebilir. Ek olarak, ek bir kısıtlama getirilmiştir - değişkenlerin değerleri, ciro, çalışma saatleri, maliyetler ve diğer ekonomik göstergeler gibi miktarları temsil ettikleri için negatif olmamalıdır.

Ekonomik problemlerin geometrik yorumu, yapılarını görselleştirmeyi, özellikleri tanımlamayı mümkün kılar ve daha karmaşık özellikleri incelemenin yollarını açar. İki değişkenli bir doğrusal programlama problemi her zaman grafiksel olarak çözülebilir. Bununla birlikte, halihazırda üç boyutlu bir uzayda, böyle bir çözüm daha karmaşık hale gelir ve boyutları üçten fazla olan alanlarda, genel olarak konuşursak, grafiksel bir çözüm imkansızdır. İki değişkenin durumu özel bir pratik öneme sahip değildir, ancak dikkate alınması doğrusal programlama problemlerinin özelliklerini netleştirir, çözümü fikrine yol açar, geometrik olarak açık çözüm yöntemleri ve pratik uygulama yolları yapar.

§ 2 Doğrusal programlama probleminin matematiksel modeli

Problemi çözmeden önce matematiksel modelini yaparız.

Matematiksel bir model, doğrusal bir amaç fonksiyonundan ve bir değişken üzerindeki doğrusal kısıtlamalardan oluşan bir ilişkiler kümesidir.

Matematiksel bir model oluşturma ilkesi.

1. Görev değişkenlerini seçin.

Problemin değişkenleri miktarlardır.

Görevde açıklanan ekonomik süreci tam olarak karakterize eden. Genellikle bir vektör olarak yazılır X = () Ayrıca, )

2. Sorunu sınırlamak için bir sistem oluşturun.

Bir kısıtlama sistemi, problemin değişkenleri tarafından sağlanan ve problemin sınırlı ekonomik koşullarından kaynaklanan bir dizi denklem ve eşitsizliktir.

Genel olarak sistem şu şekilde yazılır:

3. Hedef işlevi ayarlandı.

Amaç fonksiyonu, ekstremumunun bulunması gereken görevin kalitesini karakterize eden bir Z(X) fonksiyonudur. Genel olarak amaç fonksiyonu Z(X) = şeklinde yazılır.

O. matematiksel model problemin değişkenlerini bul şeklindedir.

kısıtlama sisteminin karşılanması:

ve negatif olmama koşulu

0 (j = ), Z(Y) = amaç fonksiyonunun uç noktasını sağlar

Doğrusal bir programlama problemine kabul edilebilir bir çözüm, kısıtlamalar sistemini ve koşullu olumsuzlukları karşılayan herhangi bir değişken değerler kümesidir.

Kabul edilebilir çözümler kümesi, sorunun kabul edilebilir çözümleri alanını (ODD) oluşturur.

Optimal çözüm, amaç fonksiyonunun bir uç noktaya ulaştığı problemin uygulanabilir çözümüdür.

§ 3 Doğrusal programlama probleminin kanonik formu

Problemin matematiksel modeli kanonik bir forma sahip olmalıdır.

Kısıtlama sistemi sadece bir denklemden oluşuyorsa ve tüm değişkenler negatif olmama koşulunu sağlıyorsa, problem kanonik bir forma sahiptir.

Sistemde en az bir eşitsizlik varsa veya herhangi bir değişken negatif olmama koşuluyla sınırlandırılmamışsa, problem standart bir forma sahiptir. Sorunu kanonik forma getirmek için yapmanız gerekenler:

eşitsizliklerden denkleme şu şekilde gidin: eşitsizliklerin sol tarafında eşitsizlik (+1) katsayısı ile ek bir değişken ekliyoruz (

) ve (-1) eşitsizlik için () ek değişkenler, negatif olmayan hedef tarafından empoze edilmez, ardından negatif olmayan iki değişkenin farkı ile değiştirilir, yani: = - (

Kanonik formun genel görünümü:

Bölüm ΙΙ Problemin simpleks yöntemle çözümü

Simplex yöntemi, en etkili olan ve herhangi bir doğrusal programlama problemini çözmek için kullanılan planın (çözüm) art arda iyileştirilmesi yöntemidir.

Yöntemin adı Latince simplecx'den gelir - basit çünkü. Sorunun kabul edilebilir çözümlerinin başlangıç ​​bölgesinden en basit şekline sahipti. Yöntemin fikirleri Rus matematikçi Kontarovich L.V. 1939'da ve daha sonra bu fikir 1949'da J. Danzig tarafından geliştirildi ve geliştirildi.

Simplex yöntemi, en uygun çözümü bulmak veya var olmadığını kanıtlamak için sınırlı sayıda adıma izin verir.

§ 1 Sorunun bildirimi

Şirket üretim sürecinde Ι, ІΙ, ІΙІ olmak üzere 3 tip makine kullanmaktadır. Aynı zamanda hammaddeler, işgücü kaynakları tüketilir ve genel giderler dikkate alınır.

Herhangi bir doğrusal programlama problemi, kanonik biçimde bir doğrusal programlama problemine indirgenebilir. Bunu yapmak için, genel durumda, maksimizasyon problemini minimizasyon problemine indirgeyebilmeniz gerekir; eşitsizlik kısıtlamalarından eşitlik kısıtlamalarına geçin ve negatif olmama koşuluna uymayan değişkenleri değiştirin. Bir fonksiyonun maksimizasyonu, aynı fonksiyonun ters işaretle minimizasyonuna eşdeğerdir ve bunun tersi de geçerlidir.

Bir doğrusal programlama problemini kanonik bir forma indirgeme kuralı aşağıdaki gibidir:

• eğer orijinal problemde bir lineer fonksiyonun maksimumunun belirlenmesi gerekiyorsa, o zaman işareti değiştirmeli ve bu fonksiyonun minimumunu aramalısınız;
• kısıtlamaların sağ tarafı negatif ise bu kısıtlama -1 ile çarpılmalıdır;
• kısıtlamalar arasında eşitsizlikler varsa, negatif olmayan ek değişkenler eklenerek bunlar eşitliklere dönüştürülür;
• eğer bazı değişkenler xj işaret kısıtlaması yoksa, (amaç fonksiyonunda ve tüm kısıtlamalarda) negatif olmayan iki yeni değişken arasındaki farkla değiştirilir:
  x 3 \u003d x 3 + - x 3 - , Nerede x 3 + , x 3 - ≥ 0 .

örnek 1. Bir doğrusal programlama probleminin kanonik formuna indirgeme:

min L \u003d 2x 1 + x 2 - x 3;
2x2 - x3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x1 ≤ 0; x2 ≥ 0; x3 ≥ 0.

Kısıtlama sisteminin her bir denklemine eşitleyici değişkenler ekleyelim x 4 , x 5 , x 6. Sistem eşitlikler şeklinde yazılacak ve kısıtlar sisteminin birinci ve üçüncü denklemlerinde değişkenler x 4 , x 6 sol tarafa "+" işaretiyle girilir ve ikinci denklemde değişken x5"-" işareti ile girilir.

2x 2 - x3 + x4 \u003d 5;
x 1 + x 2 - x 3 - x 5 \u003d -1;
2x 1 - x 2 + x 6 \u003d -3;
x4 ≥ 0; x5 ≥ 0; x6 ≥ 0.

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

2x 2 - x3 + x4 \u003d 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x1 + x2 - x6 = 3.

Doğrusal programlama problemlerini yazmanın kanonik biçiminde, kısıtlamalar sistemine dahil olan tüm değişkenler negatif olmalıdır. Diyelim ki x 1 \u003d x 1 '- x 7 , Nerede x 1 ‘ ≥ 0, x 7 ≥ 0 .

Bu ifadeyi kısıtlamalar sistemine ve amaç fonksiyonuna yerleştirerek ve değişkenleri indeksin artan düzeninde yazarak, kanonik biçimde sunulan bir doğrusal programlama problemi elde ederiz:

L min \u003d 2x 1 ' + x 2 - x 3 - 2x 7;
2x 2 - x3 + x4 \u003d 5;
-x 1'- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1' + x 2 - x 6 + 2x 7 = 3;
x 1 ' ≥ 0; x ben ≥ 0, i=2, 3, 4, 5, 6, 7.

Kanonik DP probleminin temel tasarımı için optimallik koşulu. Simplex yöntemi ve yakınsaması.

Simplex yöntemi evrensel, yazılmış neredeyse tüm doğrusal programlama problemlerini çözmeye izin verdiği için kanonik biçim.

Simplex yöntemi fikri planın art arda iyileştirilmesi, bazı başlangıç ​​referans çözümlerinden yola çıkarak, sıralı yönlendirilmiş hareket problemin çözümlerini optimal olana referansla.

Görevler için bu yer değiştirme ile amaç fonksiyonunun değeri maksimuma düşmez.

Referans çözümlerin sayısı sonlu olduğundan, sonlu sayıda adımdan sonra en uygun referans çözümü elde ederiz.

Negatif olmayan temel bir çözüme destek çözümü denir.

Simpleks Yöntem Algoritması

1. Problemin matematiksel modeli şu şekilde olmalıdır: kanonik. Kanonik değilse, kanonik forma indirgenmesi gerekir.

2. Başlangıç ​​referans çözümünü buluyoruz ve optimallik açısından kontrol ediyoruz.
Bunu yapmak için, tek yönlü tablo 1'i doldurun.
1. adımdaki tablonun tüm satırları, kısıtlama sistemi ve amaç fonksiyonu verilerine göre doldurulur.

Sorunları çözerken aşağıdaki durumlar mümkündür: maksimum:

1. Simpleks tablonun son satırının tüm katsayıları ise Dj³ 0, sonra bulundu

çözüm en uygun.

2 En az bir katsayı ise DJ £ 0, ancak karşılık gelen değişkenle tek bir pozitif tahmini ilişki yok, o zaman çözüm görevleri durdururuz, F(X) ® ¥ olduğundan, yani amaç fonksiyonu, kabul edilebilir çözümler alanında sınırlı değildir.

Son satırın en az bir katsayısı negatifse ve karşılık gelen değişken en az bir olumlu değerlendirici ilişki, o zaman gitmelisin başka bir temele.

e eğer son satırda birkaç negatif katsayı var, o zaman temel değişken sütununa(BP) bunu tanıtın değişken karşılık gelen mutlak değerdeki en büyük negatif katsayı.

5. En az bir katsayı Dk ise< 0 ,O k - inci sütun kabul lider için.

6. için öncü çizgi eşleşeni kabul et minimumücretsiz üye oranı bi pozitif katsayılara lider, k - bu kolon.

7. Öndeki satırların ve sütunların kesişme noktasındaki elemana denir. öncü unsur.

Simplex tablo 2'yi doldurma :

· taban sütununu sıfır ve bir ile doldurun

· baştaki çizgiyi baştaki elemana bölerek yeniden yazmak

baştaki satırda sıfır varsa, karşılık gelen sütunlar bir sonraki tek yönlü tabloya aktarılabilir

· kalan katsayılar “dikdörtgen” kuralına göre bulunur.

Kontrol ettiğimiz yeni bir referans çözümü elde ederiz. optimallik için:

Son satırın tüm katsayıları ise Dj³ 0, ardından bulunan çözüm maksimum.

Değilse, 8. adımın tek yönlü tablosunu doldururuz vb.

amaç fonksiyonu ise F(X) bulmayı gerektirir Minimum değer, sonra kriter problem optimalliği dır-dir katsayıların pozitif olmaması D tüm j = 1,2,…n için j.

Simplex yönteminin yakınsaması. LP problemlerinde dejenerasyon. Herhangi bir hesaplama algoritmasının en önemli özelliği, yakınsamadır, yani, uygulaması sırasında sınırlı sayıda adımda (yinelemelerde) istenen sonuçları (belirli bir doğrulukla) elde etme olasılığıdır.

Oranın aynı minimum değerlerinin olması durumunda, r (bölüm 2") değerini seçme aşamasında, tek yönlü yöntemin yakınsamasıyla ilgili sorunların potansiyel olarak ortaya çıkabileceğini görmek kolaydır.

T(q) tablosunun birkaç satırı için aynı anda ulaşılacaktır. Sonra bir sonraki yinelemede b(β(q+1)) sütunu sıfır eleman içerecektir.

⇐ Önceki12345Sonraki ⇒

yayın tarihi: 2015-11-01; Okuyun: 4190 | Sayfa telif hakkı ihlali

Studopedia.org - Studopedia.Org - 2014-2018. (0.002 s) ...

Optimal Çözüm - Problem - Doğrusal Programlama

Sayfa 1

Doğrusal programlama probleminin optimal çözümü, en az k n - m değişkenin sıfıra eşit olduğu referans noktalarından birinde elde edilir.

Doğrusal programlama probleminin optimal çözümünü kullanarak, DS'de L'nin hala sabit kaldığı kabul edilebilir değişiklikleri bulmak mümkündür.

Bir doğrusal programlama probleminin optimal bir çözümü varsa, o zaman temel bir optimal çözüm vardır.

Doğrusal programlama probleminin optimal çözümünün, n-boyutlu uzayda bir polihedron olan ve bir doğrusal kısıtlamalar sistemi tarafından tanımlanan kontrollü değişkenlerin kabul edilebilir değerleri bölgesinin sınırında yer aldığı kanıtlanmıştır.

Z, m kısıtlamalı bir doğrusal programlama probleminin optimal çözümü olduğundan, bu çözüm en fazla m kesinlikle pozitif değişken içerir.

Doğrusal programlama probleminin en uygun çözümünün, bir doğrusal kısıtlama sistemi tarafından tanımlanan / r-boyutlu bir çokyüzlü olan kontrollü değişkenlerin kabul edilebilir değerleri bölgesinin sınırında yer aldığı kanıtlanmıştır. Her tepe noktasının koordinatları, bir denklem sistemi (kısıtlar) çözülerek belirlenir ve n kontrollü değişken ve m kısıtlama varlığında St p, m denklem sistemini çözmek zorundadır. Spn n (m - n) kombinasyonu, artan tiple birlikte çok hızlı büyür, bu nedenle bir çözüm arayışı, bir bilgisayarın bile erişemeyeceği çok sayıda hesaplama gerektirir.

Böylece, D 1 durumunda, doğrusal programlama probleminin optimal çözümü otomatik olarak tamsayı olur.

Bölüm 1'de gösterildiği gibi, bir doğrusal programlama probleminin optimal çözümü kesinlikle tamsayı değildir ve aynı zamanda doğası gereği çözümün tamsayı olmasını gerektiren birçok problem vardır. Bu problemlerden bazıları ilk bakışta tamsayılı programlama problemleri değildir, ancak bu şekilde formüle edilebilirler.

Açıkçası, her temel çözüm bir doğrusal programlama probleminin optimal çözümü değildir. Bununla birlikte, dejenere olmayan bir problemin optimal çözümü her zaman denklem sisteminin temeli olmalıdır (VIII, 42) ve dolayısıyla optimal çözümü bulma problemi, sadece denklem sisteminin temel çözümlerinin sıralanmasından ibarettir (VIII, 42). 42), bunlardan en uygun olanı bulunur.

Açıkçası, her temel çözüm bir doğrusal programlama probleminin optimal çözümü değildir. Bununla birlikte, dejenere olmayan bir problemin optimal çözümü her zaman denklem sisteminin temeli olmalıdır (VIII42) ve bu nedenle, optimal çözümü bulma problemi denklem sisteminin sadece temel çözümlerinin sıralanmasından ibarettir (VIII42) ), aralarında en uygun olanı bulunur.

3. adımda birkaç yineleme gerçekleştirdikten sonra, doğrusal programlama problemine çok sayıda alternatif optimal çözüm görünebilir.

DOĞRUSAL PROGRAMLAMA SORUNU

Bu döngüye bazen sürekli yozlaşma denir. Ne yazık ki, bu fenomen genellikle yüksek boyutlu orta PI problemlerinde ortaya çıkar. Yakınsama sağlamak için binlerce yineleme gerektiren birçok düşük boyutlu problem örneği (en fazla 10 değişken ve denklem) vardır.

Bu durumlarda, doğrusal programlama problemine en uygun çözümü belirlemek için yinelemeli (adım adım) bir prosedür olan simpleks yöntemi kullanılır. Simpleks yöntemi ile hesaplamalar, uygun bir çözümün belirlenmesi ile başlar ve daha sonra diğer uygun çözümler bulunur ve bunları iyileştirme olasılıkları kontrol edilir. Bir çözümden diğerine geçiş, yeni iyileştirmeler mümkün olmayana kadar devam eder. Doğrusal programlama problemleri olarak temsil edilebilecek bu tür yönetim problemlerini çözmek için simpleks yöntemini kullanan yaygın standart bilgisayar programları vardır.

Doğrusal kısıtlamalar sisteminin özel bir yapısı varsa, örneğin bir ağ modeli oluşturuyorsa, 2. adımda doğrusal programlama problemine en uygun çözümü bulurken bu durum kullanılabilir.

Orantılı dağılım fikri, I.I. Dikin tarafından önerilen ve esasen doğrusal bir programlamaya en uygun çözümler kümesinin nispeten iç noktasını geliştirmek için iç noktalar yönteminin özelliğini kullanan iki aşamalı bir hesaplama algoritması biçiminde uygulandı. sorun. Bu özellik, (2.3.2) - (2.3.4) eşitsizlik koşullarına göre sınır değerlerinin, yalnızca diğer herhangi bir optimal çözüm için bu sınır değerlerine sahip değişkenler için elde edildiği anlamına gelir.

Sayfalar:      1    2

Doğrusal Programlama Problemini Çözmek İçin Grafik Yöntem

İki değişkenli durum için ZLP'yi standart formda düşünün:

(10)

Eşitsizlikler sistemi (10) uyumlu olsun (en az bir çözümü var). Bu sistemin herhangi bir eşitsizliği, geometrik olarak sınır çizgisi olan bir yarım düzlemi tanımlar. Negatif olmayan koşullar, karşılık gelen sınır çizgileriyle yarım düzlemleri tanımlar Ve.

Sistem uyumlu olduğu için, dışbükey kümeler gibi kesişen yarım düzlemler, bir dışbükey küme olan ve her birinin koordinatları bu sistemin çözümü olan noktaların bir koleksiyonu olan ortak bir parça oluşturur. Tüm bu noktaların toplamına denir. çözüm poligonu Bir nokta, doğru parçası, ışın, doğru, kapalı çokgen, sınırsız çokgen alan olabilir.

LLP'nin çözümü, koordinatları amaç fonksiyonuna en büyük (en küçük) değeri veren böyle bir çözüm çokgeni noktasının geometrik olarak aranmasıdır. Ayrıca, çokyüzlünün tüm noktaları kabul edilebilir çözümlerdir.

Sözde düşünün seviye çizgisi amaç fonksiyonu z, yani bu fonksiyonun aynı sabit değeri aldığı çizgi : veya

Bir doğrusal programlama problemini grafik yöntemle (değişken sayısı) çözmek için algoritma.

1. Kısıtlamalara karşılık gelen düzlemde çokgen bir uygulanabilir çözüm alanı inşa edilir. Sonra bir gradyan vektörü oluşturulur

amaç fonksiyonu z herhangi bir noktada, uygulanabilir çözümlerin alanı.

2. Düz çizgi (fonksiyon seviyesi çizgisi z) gradyan vektörüne dik maksimum problem durumunda gradyan vektörü yönünde kendisine paralel (minimum problem durumunda ters yönde) olurlu çözümler bölgesinden ayrılana kadar hareket eder. Bölgenin sınır noktası (veya noktaları) optimal noktalardır.

3. Optimum noktanın koordinatlarını bulmak için, kesişimi bu noktayı oluşturan düz çizgilere karşılık gelen bir denklem sistemini çözmek gerekir.

Ana DP problem türlerinin formülasyonu, matematiksel modellerinin oluşturulması

Bu noktadaki amaç fonksiyonunun değeri optimal olacaktır ve noktanın koordinatlarının kendisi DP probleminin çözümü olacaktır. .

Örnek. Bir geometrik problemi çözün:

Tüm kabul edilebilir çözümlerden oluşan bir çokgen oluşturalım OABCD ve amaç fonksiyonunun yön vektörü (Şekil 1). Gradyan vektörünün yönü, artan amaç fonksiyonunun yönünü gösterir. Ele alınan problem maksimumu bulmak olduğundan, vektöre dik olan çizgiyi bu vektör yönünde kendisine paralel olarak bu çizgi kabul edilebilir çözümler alanından ayrılana kadar hareket ettiriyoruz. Bölge sınırında, bizim durumumuzda noktada İLE, ve soruna bir çözüm olacaktır. Nokta İLE ve çizgilerinin kesiştiği noktadadır. Bu nedenle, koordinatları bu denklem sisteminin çözümü ile belirlenir:

nereden yani nokta İLE(6, 4) koordinatlarına sahiptir.

Maksimum (amaç fonksiyonunun maksimum değeri) şuna eşittir: Cevap: optimal çözümde, yani birinci üründen 6 adet, ikinci üründen 4 adet üretilerek maksimum kar elde edilebilir.

GİRİİŞ

Hem mikro hem de makro düzeyde modern iktisat teorisi, doğal, gerekli bir unsur olarak matematiksel modelleri ve yöntemleri içerir. Matematiğin ekonomide kullanılması, öncelikle ekonomik değişkenler ve nesneler arasındaki en önemli, temel ilişkileri tanımlamayı ve resmi olarak tanımlamayı mümkün kılar: böylesine karmaşık bir nesnenin incelenmesi, yüksek derecede soyutlama gerektirir. İkinci olarak, açıkça formüle edilmiş ilk verilerden ve ilişkilerden, yapılan varsayımlarla aynı ölçüde incelenen nesne için yeterli olan sonuçlar elde etmek için tümdengelim yöntemleri kullanılabilir. Üçüncüsü, matematik ve istatistik yöntemleri, bir nesne hakkında tümevarım yoluyla yeni bilgiler edinmeyi mümkün kılar: mevcut gözlemle en tutarlı olan değişkenlerinin bağımlılıklarının biçimini ve parametrelerini değerlendirmek. Son olarak, dördüncü olarak, matematik dilinin kullanılması, ekonomik teorinin hükümlerini doğru ve kompakt bir şekilde ifade etmemize, kavramlarını ve sonuçlarını formüle etmemize olanak tanır.

Ekonomide kullanılan matematiksel modeller, modellenen nesnenin özellikleri, modellemenin amacı ve kullanılan araçlarla ilgili bir dizi özelliğe göre sınıflara ayrılabilir: mikro ve makro ekonomik modeller, teorik ve denge, istatistiksel ve dinamik.

Optimizasyon yöntemlerinin özü, belirli kaynakların mevcudiyetine bağlı olarak, bizi ilgilendiren göstergenin maksimum (minimum) değerini sağlayan böyle bir kullanım (dağıtım) yönteminin seçilmesi gerçeğinde yatmaktadır.

Ekonomide optimizasyon yöntemleri olarak, matematiksel programlamanın (planlama) tüm ana bölümleri kullanılır.

Aşırı (maksimum veya minimum) yönetim, planlama problemlerini ve bunları çözmek için yöntemler geliştirmeyi inceleyen matematiksel disipline denir. matematiksel programlama

Genel olarak, uç problemin matematiksel formülasyonu, amaç fonksiyonunun en büyük veya en küçük değerinin belirlenmesinden oluşur.
verilen ,

nerede ve fonksiyonları verilir ve bazı gerçek sayılardır.

Hedef fonksiyonun türüne ve kısıtlamalara bağlı olarak, matematiksel programlama doğrusal ve doğrusal olmayan olarak ayrılır. En

matematiksel programlamanın çalışılan bölümü doğrusal programlamadır.

Tanım.

Doğrusal programlama problemi (sayfa 1/3)

Doğrusal programlama - doğrusal kısıtlamaların uygulandığı bilinmeyenler üzerinde doğrusal bir fonksiyonun uç (maksimum ve minimum) değerlerini kullanma ve bulma yöntemleri bilimi.

Bu doğrusal fonksiyona amaç fonksiyonu denir ve denklemler veya eşitsizlikler biçimindeki kısıtlamalara kısıtlamalar sistemi denir.

Tanım. Amaç fonksiyonunun ve kısıtlamalarının matematiksel ifadesi denir. ekonomik problemin matematiksel modeli.

Doğrusal programlamanın (LPP) bazı problemlerini ele alalım.

1. Kaynakların kullanımı sorunu (üretim planlama sorunu).

Çeşitli ürünlerin üretimi için Şirket üç farklı türde hammadde kullanmaktadır. Bir ürünün üretimi için hammadde tüketim oranları toplamın yanı sıra

İşletmenin kullanabileceği her çeşit hammadde tabloda verilmiştir.

İşletme tarafından üretilen tüm ürünlerin toplam maliyetinin maksimum olduğu ürünlerin üretimi için bir plan yapın.

Bu sorunun matematiksel bir modelini oluşturalım.

Ürünlerin istenen çıktısı ile gösterilir , ara ürünler ,

aracılığıyla - ürünler.

Her bir hammadde türü için maliyet normları olduğundan, tüm ürünlerin imalatı için her bir hammadde türünün toplam maliyetini bulabiliriz. Tablodan, I tipindeki toplam hammadde hacminin, II - olacağı sonucu çıkar.
,

III-
. Ve hammadde fonunda kısıtlamalar olduğundan, bu nedenle, her türdeki toplam hammadde hacmi, toplam hammadde miktarından fazla olmamalıdır, yani.

aşağıdaki eşitsizlik sistemini elde ederiz

(1)

Ekonomik olarak, değişkenler yalnızca negatif olmayan değerler alabilir:

(2)

Bu türdeki tüm ürünlerin maliyeti – – Buna göre işletmenin ürettiği ürünlerin toplam maliyeti (3) olacaktır.

Bulmalıyız bu fonksiyon Bu nedenle, (1) sisteminin tüm negatif olmayan çözümleri arasında, (3) fonksiyonunun en büyük değeri aldığı bir tane bulmak gerekir.

Bu sorun, ham madde (kaynak) türleri kullanılarak ürün türlerinin serbest bırakılması durumuna kolaylıkla genelleştirilebilir.

ile göster - Üretimi planlanan ürün birimi sayısı, - -th tipinde kaynak stoğu, -th ürünlerin üretimi için -th kaynağın -özgül tüketimi. - bir ürün biriminin satışından elde edilen kar - tür.

Daha sonra genel ortamda kaynakların kullanımı probleminin ekonomik ve matematiksel modeli şu şekilde olacaktır: böyle bir plan bulun
ana kısıtlama sistemini karşılayan çıktı

ek kısıtlama sistemi

amaç fonksiyonu nerede

maksimum değeri alır.

Yorum. ZLP'nin matematiksel bir modelini yapmak için yapmanız gerekenler:

– değişkenlerin gösterimini girin;

- ekonomik araştırmanın amacına dayalı olarak, bir amaç fonksiyonu oluşturun;

- görevin ekonomik göstergelerinin kullanımındaki sınırlamaları ve bunların nicel modellerini dikkate alarak, bir kısıtlama sistemi yazın.

Doğrusal programlama problemlerinin çözümü, -boyutlu vektör uzayında analitik geometri kavramlarına dayanmaktadır.

Genel LLP'nin kanonik forma indirgenmesi.

ZLP'nin genel görünümü şu şekildedir:

(1)

(2)

(3)

burada ilişki (1) amaç fonksiyonudur, (2) temel kısıtlamalar sistemidir, (3) ek kısıtlamalar sistemidir.

(2) ve (3) ilişkileri tam bir kısıtlama sistemi oluşturur.

Temel kısıtlamalar sisteminin kanonik forma indirgenmesi, eşitsizliklerin sol kısımlarına, eşitsizlikler formdaysa "+1" ve eşitsizliklerse "-1" katsayılarıyla negatif olmayan ek değişkenler eklenerek gerçekleştirilir. şeklindedir. Ek değişkenler amaç fonksiyonuna sıfır katsayı ile girer.

Tanım . Temel kısıtlamalar sistemi denklemlerle temsil ediliyorsa LLP'nin kanonik formda verildiği söylenir.

Tanım. Aşağıdaki koşullar karşılanırsa LLP'nin standart kanonik formda verildiği söylenir:

1) temel kısıtlamalar sistemi denklemlerle temsil edilir ve hepsi doğrusal olarak bağımsızdır;

2) denklem sayısı değişken sayısından azdır;

3) amaç fonksiyonunu en aza indirme sorunu çözüldü;

4) temel kısıtlamalar sisteminin doğru kısımları negatif değildir;

5) tüm değişkenler de negatif değildir.

Doğrusal programlama problemlerini çözmeye 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, birçok problemin modellerini derlerken, kısıtlamalar esas olarak bir eşitsizlik sistemi şeklinde oluşturulur, bu nedenle bir eşitsizlik sisteminden bir denklem sistemine geçebilmek gerekir.

Bu şu şekilde yapılabilir:

Doğrusal eşitsizliği alın

ve sol tarafına bir miktar değer ekleyin, öyle ki eşitsizlik eşitliğe dönüşsün

Bu durumda, bu değer negatif değildir.

Örnek

Doğrusal programlama problemini kanonik forma indirin:

Çözüm:

Amaç fonksiyonunun maksimumunu bulma problemine geçelim.

Bunu yapmak için amaç fonksiyonunun katsayılarının işaretlerini değiştiririz.

Kısıtlama sisteminin ikinci ve üçüncü eşitsizliklerini denklemlere dönüştürmek için, x 4 x 5 negatif olmayan ek değişkenleri tanıtıyoruz (bu işlem matematiksel modelde D harfi ile işaretlenmiştir).

Eşitsizlik "≤" biçiminde olduğu için x 4 değişkeni ikinci eşitsizliğin soluna "+" işaretiyle girilir.

Eşitsizlik "≥" biçiminde olduğu için x 5 değişkeni üçüncü eşitsizliğin soluna "-" işaretiyle girilir.

x 4 x 5 değişkenleri amaç fonksiyonuna bir katsayı ile girilir. sıfıra eşittir.

Problemi kanonik formda yazıyoruz:

DOĞRUSAL PROGRAMLAMA PROBLEMLERİNİ ÇÖZMEK İÇİN BASİT YÖNTEM

Bu yöntem, bir doğrusal programlama probleminin referans çözümlerinin amaçlı olarak sıralanması yöntemidir. Optimum çözümü bulmak veya optimal çözüm olmadığını belirlemek için sınırlı sayıda adıma izin verir.

Doğrusal programlama problemlerini çözmek için tek yönlü yöntemin algoritması

Sorunu simpleks yöntemiyle çözmek için aşağıdakileri yapmanız gerekir:

1. Sorunu standart forma getirin

Konu 8. Doğrusal programlama

"Birim bazında" bir başlangıç ​​referans çözümü bulun (referans çözüm yoksa, kısıtlama sisteminin uyumsuzluğundan dolayı sorunun çözümü yoktur)

3. Vektör açılımlarının tahminlerini referans çözüm temelinde hesaplayın ve tek yönlü yöntem tablosunu doldurun

4. Optimal çözümün teklik kriteri karşılanırsa, problemin çözümü sona erer.

5. Bir optimal çözüm kümesinin var olma koşulu karşılanırsa, o zaman basit numaralandırma ile tüm optimal çözümler bulunur.

Simplex yöntemiyle problem çözme örneği

örnek 1

Simplex yöntemini kullanarak sorunu çözün:

İşlev değerini en aza indirin

F = 10×1 - 4×3 maks.

Eşitsizlik şeklinde kısıtlamaların varlığında

Sorunu kanonik forma getiriyoruz.

Bunu yapmak için, birinci eşitsizlik kısıtlamasının sol tarafına +1 katsayılı ek bir x 5 değişkeni ekliyoruz. x 5 değişkeni amaç fonksiyonuna sıfır katsayı ile dahil edilir (yani dahil edilmez).

Biz:

F = 10×1 - 4×3+0∙x5 maks.

Eşitsizlik şeklinde kısıtlamaların varlığında

Başlangıç ​​referans çözümünü buluyoruz. Bunu yapmak için, serbest (çözümlenmemiş) değişkenleri sıfır x1 = x3 = 0'a eşitliyoruz.

Birim bazında B1 = (A4, A5, A6) ile X1 = (0.0.0.5.9/15.6) referans çözümünü elde ederiz.

Koşul vektörlerinin genişleme tahminlerini, aşağıdaki formülü kullanarak referans çözüm temelinde hesaplıyoruz:

Δ k \u003d C b X k - c k

· Cb = (с 1 , с 2 , … , с m) - temel değişkenli amaç fonksiyonu katsayılarının vektörü

· X k = (x 1k , x 2k , … , x mk) - ilgili vektör A'nın referans çözüm bazında genişleme vektörü

· C ila - x ila değişkeni için amaç fonksiyonunun katsayısı.

Tabana dahil edilen vektörlerin tahminleri her zaman sıfıra eşittir.

Referans çözüm, genişleme katsayıları ve koşul vektörlerinin genişleme tahminleri, referans çözümün temeli açısından tek yönlü bir tabloda yazılır:

Tablonun üstünde, tahminlerin hesaplanmasında kolaylık olması için amaç fonksiyonunun katsayıları yazılmıştır. İlk "B" sütunu, referans çözüm temelinde yer alan vektörleri içerir. Bu vektörlerin yazılma sırası, kısıtlama denklemlerinde izin verilen bilinmeyenlerin sayısına karşılık gelir. "B ile" tablosunun ikinci sütununda amaç fonksiyonunun katsayıları temel değişkenlerle aynı sırada yazılır. Amaç fonksiyonunun katsayılarının "C b" sütununda doğru düzenlenmesi ile tabana dahil edilen birim vektörlerin tahminleri her zaman sıfıra eşittir.

"A 0 "sütununda Δ k tahminlerini içeren tablonun son satırında amaç fonksiyonunun değerleri referans çözüm Z(X 1) üzerine yazılır.

Başlangıç ​​referans çözümü optimal değildir, çünkü maksimum problemde Aı ve A3 vektörleri için Aı = -2, A3 = -9 tahminleri negatiftir.

Referans çözüm iyileştirme teoremine göre, maksimum problemdeki en az bir vektörün negatif bir tahmini varsa, amaç fonksiyonunun değerinin daha büyük olacağı yeni bir referans çözüm bulmak mümkündür.

İki vektörden hangisinin amaç fonksiyonunda daha büyük bir artışa yol açacağını belirleyelim.

Amaç fonksiyonu artışı aşağıdaki formülle bulunur:

Aşağıdaki formülü kullanarak birinci ve üçüncü sütunlar için θ 01 parametresinin değerlerini hesaplıyoruz:

l = 1 için θ 01 = 6, l = 1 için θ 03 = 3 elde ederiz (tablo 26.1).

İlk vektör tabana eklendiğinde amaç fonksiyonunun artışını buluyoruz

ΔZ 1 \u003d - 6 * (- 2) \u003d 12,

ve üçüncü vektör ΔZ 3 = - 3*(- 9) = 27.

Bu nedenle, optimal çözüme daha hızlı bir yaklaşım için, θ 03 parametresinin minimumuna ilk satırda ulaşıldığından, A6 tabanının ilk vektörü yerine referans çözümün tabanına A3 vektörünü sokmak gerekir. (l = 1).

X13 = 2 elemanı ile Jordan dönüşümünü gerçekleştiriyoruz, ikinci referans çözümü elde ediyoruz

X2 = (0.0.3.21.42.0)

B2 = (A3, A4, A5) temelinde.

(tablo 26.2)

A2 vektörünün negatif bir tahmini Δ2 = - 6 olduğundan, bu çözüm optimal değildir.

Çözümü geliştirmek için, A2 vektörünü referans çözümün tabanına dahil etmek gerekir.

Tabandan türetilen vektörün sayısını belirliyoruz. Bunu yapmak için ikinci sütun için θ 02 parametresini hesaplıyoruz, l = 2 için 7'ye eşittir.

Bu nedenle, tabandan A4 tabanının ikinci vektörünü çıkarıyoruz.

x 22 = 3 elemanı ile Ürdün dönüşümünü gerçekleştiriyoruz, üçüncü referans çözümü elde ediyoruz

X3 = (0.7.10.0.63.0)

B2 \u003d (A3, A2, A5) (tablo 26.3).

Bu çözüm tek optimal çözümdür çünkü temele dahil olmayan tüm vektörler için tahminler pozitiftir.

Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 7/2.

Cevap: X = (0.7,10,0.63) konumunda maksimum Z(X) = 201.

⇐ Önceki123456789Sonraki ⇒

Uygulamada, bir doğrusal programlama problemindeki kısıtlamalar genellikle denklemlerle değil, eşitsizliklerle verilir.

Eşitsizlik kısıtlamalı bir problemden doğrusal programlamanın ana problemine nasıl geçilebileceğini gösterelim.

Değişkenlere uygulanan kısıtlamaların doğrusal eşitsizlikler biçiminde olduğu, değişkenlerle ilgili bir doğrusal programlama problemi olsun. Bazılarında eşitsizlik işareti olabilir ve diğerleri (ikinci tip, her iki parçanın işaretinin basit bir değişikliği ile birinciye indirgenir). Bu nedenle, tüm eşitsizlik kısıtlamalarını standart formda belirledik:

Eşitsizlikleri (4.1) karşılayacak ve ek olarak doğrusal işlevi en aza indirecek böyle bir negatif olmayan değerler kümesi bulmak gerekir:

Bu şekilde kurulan problemden doğrusal programlamanın ana problemine geçmek kolaydır. Aslında, notasyonu tanıtıyoruz:

"ek" olarak adlandıracağımız bazı yeni değişkenler nerede. Koşullara (4.1) göre, bu ek değişkenler olması gerektiği gibi negatif olmamalıdır.

Böylece, aşağıdaki formülasyonda doğrusal programlama sorunuyla karşı karşıyayız: denklem sistemini (4.3) karşılayan değişkenlerin negatif olmayan değerlerini bulmak ve aynı zamanda bu değişkenlerin doğrusal işlevini en aza indirmek:

Gördüğünüz gibi, önümüzde saf haliyle doğrusal programlamanın (LPP) ana sorunu var. Denklemler (4.3), serbest değişkenler cinsinden ifade edilen temel değişkenlere göre çözülmüş formda verilmiştir. L işlevi yalnızca "başlangıç" değişkenleri cinsinden ifade edilir ("ilave" değişkenlerin katsayıları sıfıra eşittir).

Böylece, eşitsizlik kısıtlamaları ile doğrusal programlama problemini doğrusal programlamanın ana problemine indirgemiş olduk, ancak problemin orijinalinde olduğundan daha fazla sayıda değişken var.

Örnek 1 Eşitsizlik kısıtlamaları olan bir doğrusal programlama problemi var: koşulları sağlayan değişkenlerin negatif olmayan değerlerini bulun

ve lineer fonksiyonun minimize edilmesi

Bu sorunun OLP formuna indirgenmesi gerekmektedir.

Çözüm. Eşitsizlikleri (4.4) standart forma getiriyoruz;

Ek değişkenler sunuyoruz:

Görev, değişkenlerin negatif olmayan değerlerini bulmaktır.

denklemleri sağlamak (4.6) ve lineer fonksiyonu minimize etmek (4.5).

Eşitsizlik kısıtlamaları olan bir doğrusal programlama probleminden eşitlik kısıtlamaları (ELP) içeren bir probleme geçmenin nasıl mümkün olduğunu gösterdik. Tersine geçiş her zaman mümkündür - LLP'den eşitsizlik kısıtlamalarıyla ilgili soruna. İlk durumda değişken sayısını artırdıysak, ikinci durumda azaltacağız, temel değişkenleri eleyeceğiz ve sadece serbest olanları bırakacağız.

Örnek 2. Eşitlik kısıtlamaları (OLP) olan bir doğrusal programlama problemi var:

ve minimize edilecek fonksiyon

Eşitsizlik kısıtlamaları olan bir doğrusal programlama problemi olarak yazılması gerekmektedir.

Çözüm. olduğundan, değişkenlerden ikisini serbest olarak seçiyoruz. Denklemlerin ilkiyle ilişkili olduklarından değişkenlerin serbest olarak seçilemeyeceğini unutmayın (4 7): birinin değeri tamamen diğerinin değeri tarafından belirlenir ve serbest değişkenler bağımsız olmalıdır

Aynı nedenle, değişkenleri serbest olarak seçmek imkansızdır (ikinci denklemle bağlanırlar). Serbest değişkenler olarak seçiyoruz ve geri kalan her şeyi onlar cinsinden ifade ediyoruz:

Koşullar (4 9) eşitsizliklerle değiştirilebileceğinden:

Lineer fonksiyon L'nin ifadesini L'de Yerine Geçen serbest değişkenlere ve bunların ifadelerine geçelim (4.9). elde etmek.

3.1. Doğrusal programlamanın genel problemi

Doğrusal programlama- bu, matematiksel programlamanın en gelişmiş bölümüdür, bunun yardımıyla aşırı problemlerin doğrusal bağlantılar ve kısıtlamalarla analizi ve çözümü gerçekleştirilir.

Doğrusal programlama, belirli koşullar altında üretim problemlerini çözmek için tüm olası seçeneklerden en iyisini ve en uygununu seçmeye izin veren bir dizi buluşsal (yaklaşık) çözüm yöntemini içerir. Bu yöntemler aşağıdakileri içerir - grafiksel, basit, potansiyel yöntem (değiştirilmiş dağıtım yöntemi - MOD), Khichkov, Kreko, Vogel yaklaşım yöntemi ve diğerleri.

Bu yöntemlerden bazıları ortak bir adla birleştirilir - dağıtım veya taşıma yöntemi.

Doğrusal programlamanın doğum yeri Rusya'dır. İlki, geleceğin akademisyeni L.V.'nin doğrusal programlama üzerine çalışıyor. Kantorovich 1939'da yayınlandı. 1975'te doğrusal programlama yöntemlerini geliştirdiği için Nobel Ekonomi Ödülü'nü aldı. Akademisyen L.V.'nin eserlerinin çoğundan beri. Kantorovich kendini ulaşım sorunlarını çözmeye adamış olsa da, bahsi geçen Nobel Ödülü'nün aynı zamanda Rus ulaşım biliminin esasına da işaret ettiği düşünülebilir.

Karayolu taşımacılığında, 1960'lardan beri en önemli üretim problemlerinin çoğunu çözmek için doğrusal programlama yöntemleri kullanılmaktadır, yani: kargo taşımacılığının mesafesini azaltmak; optimal bir ulaşım şeması hazırlamak; en kısa hareket yollarının seçimi; farklı, ancak değiştirilebilir yüklerin taşınması görevleri; vardiya-günlük planlama; küçük parti yüklerin taşınmasının planlanması; otobüslerin rotalar ve diğerleri boyunca dağılımı.

Doğrusal programlama modelinin özellikleri aşağıdaki gibidir:

Amaç fonksiyonu ve kısıtlamalar doğrusal bağımlılıklarla (eşitlikler veya eşitsizlikler) ifade edilir;

Bağımlılıkların sayısı her zaman bilinmeyenlerin sayısından azdır (belirsizlik durumu);

Gerekli değişkenlerin negatif olmaması. Bir doğrusal programlama modelini kısaltılmış biçimde yazmanın genel biçimi şu şekildedir:

Bulmak X ij ≥ 0 (j = 1, 2…n) aşağıdaki kısıtlama türleri altında:

Bu kısıtlamalar, amaç fonksiyonunu en aza indirir (veya en üst düzeye çıkarır)

Bir doğrusal programlama modeli yazmanın standart biçimi, şu şekilde yazılmış bir doğrusal denklemler sistemidir: kanonik form, yani doğrusal eşitlikler biçiminde, negatif olmayan sayılarda:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n \u003d b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n \u003d b 2 ; (3.1)

……………………………..

bir m x 1 + bir m 2 x 2 + ...+ bir mn x n = b m ..

Model, negatif olmayan sayılarda eşitsizlikler şeklinde yazılırsa, yani şu şekildedir:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n ≤ b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)

……………………………..

bir m x 1 + bir m 2 x 2 + …+ bir mn x n ≤ b m ,..

daha sonra bu giriş şuna indirgenir: kanonik ek değişkenler ekleyerek form (3.1) x n +1> 0 (Ben=1,2…M) eşitsizliğin sol tarafına (veya eşitsizlik işareti ters yöndeyse değişken sayısının azaltılması). Ek değişkenler temeli oluşturur.

Bir doğrusal programlama problemini çözmenin standart biçimi, amaç fonksiyonunu en aza indiren negatif olmayan sayılarda bir doğrusal denklem sistemine çözümler bulmaktır. Amaç fonksiyonu daha sonra forma sahiptir

L = c 1 x 1 + c 2 x 2 ... c n x n → dk, (3.3)

Nerede s 1 , s 2 … s n amaç fonksiyon katsayılarıdır L değişkenlerle X J .

Ek değişkenler amaç fonksiyonuna sıfır katsayı ile girer.

Amaç fonksiyonunu maksimize etme durumunda L amaç fonksiyonunun değişkenlerinin işaretleri tersine çevrilmeli ve yine minimizasyon problemine, yani bir görev başka bir ikameye indirgenir L Açık - L veya maks. L=dk(- L).

Bir doğrusal denklem sisteminin (3.1) temel çözümü, temel olmayan değişkenlere sıfır değerlerin verildiği bir çözümdür.

Temelde yer alan değişkenlerin negatif olmadığı temel bir çözüme kabul edilebilir denir.

Amaç fonksiyonunu (3.3) maksimize eden (veya minimize eden) kabul edilebilir bir çözüme optimal denir.

Her doğrusal programlama problemi, ikili doğrusal programlama problemi olarak adlandırılan bir diğerine karşılık gelir. İkili olana göre orijinal probleme doğrudan problem denir. Asal ve ikili problemler, doğrusal programlamada ikili çift olarak adlandırılan bir çift oluşturur. Asal ve ikili çift, asal problem kanonik formda yazıldığında asimetrik bir çift ve problemlerin koşulları eşitsizlikler olarak yazıldığında simetrik bir çift oluşturur.

İkili bir problemin matematiksel modelini derlemek için kurallar, matris hesabının kurallarına dayanmaktadır.

İkilik kavramı, doğrusal programlama problemlerinin analizinde yaygın olarak kullanılmaktadır. Dualitenin özelliği, her özel durumda ayrıntılı olarak ele alınır.

3.2. Grafik-analitik yöntem

Grafik-analitik yöntem, doğrusal programlamanın en basit yöntemlerinden biridir. Doğrusal programlamanın özünü, geometrik yorumunu açıkça ortaya koyuyor. Dezavantajı, 2 veya 3 bilinmeyenli problemleri çözmenize izin vermesidir, yani dar bir problem yelpazesine uygulanabilir. Yöntem, analitik geometri kurallarına dayanmaktadır.

İki değişkenli bir problem çözme x 1 Ve x 2 problemin anlamına göre negatif olmaması gereken , Kartezyen koordinat sisteminde gerçekleştirilir. Denklemler x 1=0 ve x 2= 0, birinci çeyreğin koordinat sisteminin eksenleridir

Belirli bir örnek kullanarak çözüm yöntemini ele alalım.

Örnek 3.1. Stokta 300 ton köpük beton ürünleri ve 200 ton çelik ürünleri bulunmaktadır. Otomobil işletmesinin bu ürünleri yapımı devam eden tesise teslim etmesi gerekiyor. Otomobil şirketinin KAMAZ - 5320 kamyonları var ve

ZIL-4314. Bir yolculuk için KamAZ-5320 6 ton köpük beton ve 2 ton çelik teslim edebilir ve yolculuktan elde edilen kâr 4 bin ruble olacaktır. ZIL-4314, bir yolculukta 2 ton köpük beton ve 4 ton çelik teslim ediyor, yolculuktan elde edilen kâr 6 bin ruble. Taşımacılığı, otomobil işletmesine en fazla karı sağlayacak şekilde düzenlemek gerekiyor.

Problemin matematiksel bir modelini oluşturalım. KamAZ-5320 ve üzerinden istenen yolculuk sayısını x 1 ile belirtin X 2 gerekli sayıda ZIL-4314 sürücüsü.

Ton köpük beton ürünlerinde toplam taşıma 6 adettir. x 1+ 2x 2 ve çelikten 2 x 1+ 4x 2. Mevcut ürün sayısına göre gönderim limiti 6'dır. x 1+ 2x 2 ≤ Köpük beton için 300t ve 2 x 1+ 4x 2 ≤Çelik için 200 ton.

Bin ruble cinsinden toplam kar. 4 olarak ifade edilir X 1 + 6X 2 , maksimize edilmesi gereken ve incelenmekte olan problemdeki optimallik kriteridir. Böylece problemin matematiksel modeli aşağıdaki gibi görünür. Amaç fonksiyonunu maksimize etmek gerekir.

L = 4x 1+ 62 → koşullar altında maks.: 6 x 1+ 2x 2 ≤ 300; 2x 1+ 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.

Denklem 6'yı düşünün x 1+ 2x2 = 300. Bu denklemle tanımlanan bir doğru oluşturmak için, bu doğru üzerinde uzanan iki nokta buluyoruz. -de x 1= 0 bir doğrunun denkleminden 2 buluruz x2 = 300, buradan x 2 \u003d 150. Bu nedenle, koordinatları (0.150) olan A noktası istenen çizgi üzerinde yer alır. -de x 2= 0 elimizde 6 var x 1\u003d 300, buradan x 1 \u003d 50 ve nokta D(50,0) koordinatları ile de istenilen satırdadır. Bu iki noktadan bir çizgi çizin AD(Şekil 3.1).

Doğrusal eşitsizlik 6 x 1+ 2x 2 ≤ 300, oluşturulmuş çizginin bir tarafında bulunan bir yarım düzlemdir 6 x 1+ 2x2 = 300. İstenen yarım düzlemin noktalarının bu doğrunun hangi tarafında olduğunu bulmak için, 6 eşitsizliğini yerine koyarız. x 1+ 2x 2 ≤ Sınır çizgisi üzerinde olmayan bir noktanın 300 koordinatı. Örneğin, orijin 0-(0,0)'dır. 6∙0 + 2∙0 = 0 eşitsizliğini sağlar< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD ve şek. 3.1 gölgeli.

Denklem 2 x 1+ 4x 2= 200 iki noktadan inşa edilecektir. -de x 1 = 0 4x2 = 200 nereden x2 = 50. Sonra nokta e koordinatları (0,50) vardır ve gerekli satıra aittir. -de x 2= 0, 2x2 = 200 nokta İle(100,0) koordinatlarıyla verilen doğru üzerindedir. Noktanın koordinatlarını eşitsizliğe koymak İle(0,0), 2∙0 + 4∙0 = 0 elde ederiz< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

Görev kısıtlama sistemi, planları gerektirir ( x 1; x 2) dört eşitsizliği de karşılar, yani kabul edilebilir tasarımlar noktalardır ( x 1; x 2) aynı anda dört yarım düzlemde de olmalıdır. Bu gereksinim yalnızca çokgenin içinde ve sınırında bulunan noktalar tarafından karşılanır. OKD, kabul edilebilir çözümlerin çokgenidir.

Uygulanabilir çözümler çokgeninin köşeleri, noktalardır. O, E, K, D doğru parçaları OE, EK, KD, OD- kaburgaları. Çokgenin herhangi bir noktası OKD görevin tüm koşullarını sağlayan planıdır. Çokgenin köşeleri, iki düz çizginin kesişmesinden oluşur ve aralarında en iyi (optimal) plan olan problemin temel planlarına karşılık gelir. Böylece, olurlu çözümler çokgenindeki köşe sayısı kadar referans plan olacaktır.

Amaç fonksiyonu için görsel bir geometrik temsil de elde edilebilir. L = 4x 1+ 6x 2. Amaç fonksiyonunun bazı değerlerini sabitleriz, örneğin L= 120. denklem 4 x 1+ 6x2 = 120, bir noktadan geçen bir çizgiyi tanımlar İÇİNDE koordinatlarla (x 1 \u003d 0; x 2 \u003d 20) ve bir nokta L koordinatlarla (( X 1 = 30; X 2 = 0). Çizgi segmenti BLçokgenin içinde yer alır OKD. Bu nedenle, bu segmentin tüm planları (noktaları) için amaç fonksiyonunun değeri aynıdır ve 120'ye eşittir. Amaç fonksiyonunun diğer değerlerini vererek, denilen paralel çizgiler elde ederiz. seviye çizgileri hedef işlevi.

çizgiyi taşıma L kendisine bir yönde paralel olarak, amaç fonksiyonunda bir artış ve ters yönde - azalmasını elde ederiz. Bu örnekte, düz bir çizginin hareketi BL sağdaki, maksimize ettiğimiz amaç fonksiyonundaki artışı belirler. Bunu satıra kadar yapıyoruz BL kabul edilebilir çözümler poligonu ile en az bir ortak noktaya sahip olacaktır OKD. Şek. 3.1 bundan, amaç fonksiyonu seviyesinin düz çizgisinin kesiştiği son noktanın nokta olacağı sonucu çıkar. İLE. Bunun anlamı, nokta İLE optimal görev planını belirler.

Seviye çizgisine dik olan artış yönüne denir. en büyük artışın yönü amaç fonksiyonu ve maksimum kazancını belirler. Bu yön, seviye çizgileri çizilmeden ayarlanabilir. Bunun için eksenlerde gerekli x 1 Ve x 2 amaç fonksiyonunun katsayılarına eşit segmentleri ayırın ve bunları koordinatlarda olduğu gibi kullanarak amaç fonksiyonundaki en büyük artışın bir vektörünü oluşturun. matematikte buna denir gradyan ve grad işareti ile gösterilir. Bir özellik için gradyan L = 4x1 + 6x2 vektör olacak N| 4; 6 | . Yapımının rahatlığı için koordinatları örneğin 10 kat artırıyoruz, yani. n | 40; 60 | . Amaç fonksiyonunun gradyanını oluşturalım L, bunun için noktayı koordinatlarla (40; 60) orijine bağlarız. Amaç fonksiyonu seviye çizgileri, gradyan yönüne dik olarak çizilir.

Yani, şu ya da bu şekilde, noktanın tespit edildiği tespit edilmiştir. İLE değişkenlerin değerleri verilen noktanın koordinatlarına karşılık gelen optimal görev planını belirler. Koordinatları oluşturmak için, bu köşeyi oluşturan düz çizgilerin denklem sistemini çözmek gerekir:

6x 1+ 2x 2= 300;

2x 1+ 4x 2= 200.

İkinci denklemi 3 ile çarparak x 1'deki katsayıları eşitliyoruz ve birinci denklemi ikinci denklemden çıkarıyoruz. hadi 10 yapalım x 2= 300,x2 = 30. x 2 \u003d 30 değerini denklemlerden herhangi birine, örneğin birincisine koyarak, değeri belirleriz X 1:

6x 1+ 2X · 30 = 300,

nereden 6 x 1 = 300 - 60 = 240, bu nedenle, x 1 = 40.

Dolayısıyla bir otomobil firmasının en fazla karı elde edebilmesi için KamAZ-5320'ye 40, ZIL-4314'e 30 sefer tamamlaması gerekmektedir. Bu durumda maksimum kar

L = 4x 1+ 6x 2\u003d 4 40 + 6 30 \u003d 340 bin ruble.

Ele alınan örneğe ve iki değişkenli optimizasyon probleminin geometrik yorumuna dayanarak, aşağıdaki sonuçları çıkarabiliriz:

1) iki boyutlu uzayda, uygun çözümlerin alanı bir çokgendir;

2) çokgenin her bir tarafı sıfıra eşit bir değişkenin değerine karşılık gelir;

3) kabul edilebilir çözümler poligonunun her köşesi, sıfıra eşit iki değişkenin değerlerine karşılık gelir;

4) amaç fonksiyonunun her değeri bir düz çizgiye karşılık gelir;

5) problemin optimal çözümü, amaç fonksiyonunun optimal değeri elde ettiği çokgenin tepe noktasına karşılık gelirken, optimal değişkenler bu tepe noktasının koordinatlarıdır.

Genel durumda, optimizasyon problemleri benzer bir geometrik yoruma sahiptir. Görev planları kümesi, köşeleri referans planlara karşılık gelen bir polihedron olacaktır. Problemi çözerken, çokyüzlünün bir köşesinden diğerine büyük bir amaç fonksiyonu değerine geçiş, optimal değeri elde edilene kadar gerçekleştirilir. Optimizasyon yöntemlerinin etkinliğinin, tam olarak, köşelerin numaralandırılmasının (yineleme) yalnızca amaç fonksiyonundaki en büyük artış yönünde gerçekleştirilmesinde yattığına dikkat edin. Bu nedenle, çok sayıda olan tüm köşeler dikkate alınmaz, yalnızca aşırı olana daha yakın olanlar dikkate alınır.

Bir optimizasyon problemi sınıfını belirlerken ve onu çözmek için bir yöntem seçerken, uygulanabilir çözümler kümesinin dışbükey mi yoksa dışbükey mi olduğunu, doğrusal mı yoksa doğrusal olmayan bir amaç fonksiyonu mu olduğunu bilmek gerekir.

Tanım olarak, bir küme denir dışbükey herhangi iki nokta için, bu noktaları birleştiren parçanın tamamı bu kümeye aitse. Dışbükey kümelere örnek olarak, örneğin bir segment (Şekil 3.2, a), daire şeklinde bir düzlem, bir küp, bir paralelyüz ve tamamen her bir tarafının bir tarafında bulunan çokgenler verilebilir. , vesaire.

Şek. 3.2b dışbükey olmayan kümeleri gösterir. Dışbükey olmayan kümelerde, AB segmentinin söz konusu kümeye ait olmayan en az iki noktası belirtilebilir.

3.3. tek yönlü yöntem

tek yönlü yöntem doğrusal programlama problemlerini çözmek için yaygın olarak kullanılan bir yöntemdir. Yöntem, adını, köşe sayısı her zaman uzayın boyutundan bir fazla olan en basit dışbükey çokgeni ifade eden "tek yönlü" kelimesinden almıştır. Simplex yöntemi, 1940'ların sonunda matematikçi J. Dantzig tarafından ABD'de geliştirildi.

Simplex yöntemi, (3.1) tipi bir kanonik lineer denklem sisteminin negatif olmayan bir temel çözümünün elde edilmesini, ardından amaç fonksiyonunun (3.3) en aza indirilmesini (maksimizasyon) ve bu şekilde en uygun değerlerin bulunmasını içerir. gerekli değişkenler x 1, x 2… x n.

Simplex yönteminin fikri, hesaplama sırasında sırayla birinci temel çözümden ikinci, üçüncü vb.'ye geçilmesi gerçeğinde yatmaktadır. aracılığıyla sözde basit dönüşümler. Dönüşümler, hesaplamaları büyük ölçüde basitleştiren ve hızlandıran tek yönlü tablolar biçiminde yapılır.

Bir lineer denklem sisteminin negatif olmayan temel çözümlerini elde etmek için, bilinmeyenleri eleme sürecini, sürecin tüm aşamalarında denklemlerin serbest terimleri negatif olmayacak şekilde yürütmek gerekir. Bu durumda, aşağıdaki kurala uyulmalıdır: En az bir pozitif katsayıya sahip herhangi bir serbest değişken, yeni bir temel değişken olarak alınır; denklemlerin serbest terimlerinin, temele eklenen değişkenle denklemlerin karşılık gelen pozitif katsayılarına en küçük oranına karşılık gelen tabandan bir değişken türetilir. Bu tür dönüşümlere denir tek yönlü dönüştürücüler.

Bu çok önemlidir, çünkü belirtilen değişkenin varyasyon aralığını belirlemek ve yerine koymak yerine, diğer serbest değişkenlerin sıfır değerleri ile bir serbest değişkenin mümkün olan en büyük değerine karşılık gelen negatif olmayan belirli bir çözüm bulmak için mümkün olan en büyük değeri genel çözüme girerse, bu değişkeni temel olarak almak ve sistemi basit bir dönüşüme tabi tutmak, yeni bir tabana geçmek yeterlidir, bu da hesaplamaları büyük ölçüde basitleştirir.

Hesaplamalar, basit tablolar kullanılarak uygun bir şekilde gerçekleştirilir. Bir tablodan diğerine geçiş, bir yinelemeye, yani bir temelden diğerine geçişe karşılık gelirken, amaç fonksiyonunun değeri azalır. Belirli sayıda iterasyon için, amaç fonksiyonunun optimal (minimum veya maksimum) değerinin elde edildiği tabana geçerler. Simplex yöntemini genel olarak ele alalım.

Doğrusal programlamanın genel görevi, negatif olmama koşuluna bağlı olarak, değişkenleri bir doğrusal denklem sistemi ile birbirine bağlanan amaç fonksiyonunu en aza indirmek (maksimumlaştırmaktır).

Doğrusal formu en aza indirmek gerekli olsun

L = c 1 x 1 + c 2 x 2 + ... c n x n.

Aşağıdaki koşullar altında (netlik için, sıfır ve birim katsayılar denklemlerde tutulur):

1x 1+ 0x 2 + ... 0x m + a 1m+ 1x m+1 ... + a 1n x n \u003d b 1;

0x 1+ 1x 2+… 0x m + a 2m+ 1x m+1 ... + a 2n x n \u003d b 2;

……………………………………………

0x 1+ 0x 2 + ... 1x m + bir mm + 1x m +1 ... + bir mn x n \u003d b m.

Bu denklem sisteminin zaten hazır bir temeli vardır, çünkü her kısıtlama denklemi, diğer denklemlerde olmayan, yani değişkenlerin katsayılarından, bire eşit katsayılı bir bilinmeyen içerir. X 1 , X 2 …, x m bir kimlik matrisi oluşturabilirsiniz.

Temel değişkenler için denklemleri çözelim:

x 1 \u003d b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);

x 2 \u003d b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

………………………………

x m \u003d b m - (bir mm + 1x m + 1 ... + bir mn x n),

ve amaç fonksiyonunu serbest değişkenler cinsinden ifade edeceğiz, bunun yerine temel değişkenlerin yerine serbest değişkenler cinsinden ifadelerini koyacağız:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Değişkenler x 1, x 2 ..., x m, yardımı ile ilk temel planın bulunduğu, temel ve geri kalanı x m +1 , x m +2 ,…x n –özgür. Sistemde her zaman denklem sayısı kadar temel değişken olmalıdır. Negatif olmama koşuluna göre, serbest değişkenlerin en küçük değeri sıfıra eşittir. Denklem sisteminin ortaya çıkan temel çözümü, onun ilk uygulanabilir çözümüdür, yani x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, x n = 0.

Bu çözüm, amaç fonksiyonunun değerine karşılık gelir.

L = c 1 b 1 + c 2 b 2 + ... c m b m.

Başlangıç ​​çözümü optimallik açısından kontrol edilir. Optimal değilse, o zaman temele serbest değişkenler eklenerek, amaç fonksiyonunun daha küçük bir değeri ile aşağıdaki uygun çözümler bulunur. Bunun için tabana girilmesi gereken bir serbest değişken ve tabandan çıkarılması gereken bir değişken belirlenir. Daha sonra önceki sistemden bir sonraki eşdeğer sisteme geçerler. Bu, tek yönlü tablolar kullanılarak yapılır. Amaç fonksiyonunun optimal değeri elde edilene kadar problemin çözümüne devam edilir.

Simpleks tablolar aşağıdaki gibi derlenir (bkz. Tablo 3.1). Tüm değişkenleri tablonun en üstüne yerleştirin X 1 , X 2 …, x n ve katsayılar cj karşılık gelen değişkenlerin amaç fonksiyonuna dahil edildiği. İlk sütun c ben tabanda yer alan değişkenler için amaç fonksiyonunun katsayısından oluşur. Bunu, temel değişkenlerden oluşan bir sütun ve denklemlerin serbest terimleri izler. Tablonun geri kalan sütunlarının öğeleri, değişkenlerin denklem sistemine girdiği değişkenlerin katsayılarıdır. Böylece tablonun her satırı, sistemin temel değişkene göre çözülmüş denklemine karşılık gelir. Tablo ayrıca, belirli bir temel için amaç fonksiyonuna karşılık gelen planın bir varyantını da gösterir.

Tablonun alt satırına denir dizin. Öğelerinin her biri (tahmin) ∆ J tanımlamak

∆j = zj – cj ,

Nerede cj amaç fonksiyonundaki karşılık gelen değişkenlerin katsayılarıdır; zj – amaç fonksiyonunun katsayılarının temel değişkenlerle ve karşılık gelen değişkenlerle çarpımlarının toplamı - elemanlar J tablonun -inci sütunu.

Masa 3.1

İlk geçerli olan tek yönlü tablo