ATÖLYE

DOĞRUSAL PROBLEMLERİ ÇÖZMEK İÇİN

MATEMATİKSEL PROGRAMLAMA

giriiş

matematiksel programlama arama kuramını ve yöntemlerini inceleyen bir matematik dalıdır. en iyi seçenekler hem belirli bir işletmede hem de belirli bir endüstride veya ayrı bir bölgede veya tüm eyalette insan ekonomik faaliyetinin planlanması.

En iyi seçenekler, başaranlardır. maksimum performans emek, minimum maliyet, maksimum kar, minimum kaynak kullanımı vb. Matematik açısından, bu bir optimizasyon problemleri sınıfıdır. Onları çözmek için ana araç matematik modelleme. Matematiksel bir model, incelenmekte olan olgunun resmi bir tanımı ve onunla ilgili mevcut tüm bilgilerin denklemler, özdeşlikler ve eşitsizlikler biçiminde matematik diline "çevrilmesi" dir. Tüm bu ilişkiler doğrusal ise, o zaman problemin tamamı problem olarak adlandırılır. doğrusal programlama(ZLP). Bu modelin etkinliği için kriter, hedef adı verilen belirli bir işlevdir.

Doğrusal programlama probleminin ifadesi ve gösterimi

formüle edelim ortak görev doğrusal programlama.

Sisteme izin ver m lineer denklemler ve eşitsizlikler n değişkenler (kısıtlama sistemi):

ve doğrusal fonksiyon

Doğrusal fonksiyonun maksimum (minimum) değeri aldığı (1) sistemine böyle bir çözüm bulmak gerekir.

AT Genel dava LLP'nin sonsuz sayıda çözümü olabilir. Genellikle kısıtlamaları (1) karşılayan bir çözüm denir plan. için tüm bileşenler (3) ise, o zaman diyoruz kabul edilebilir çözüm .

optimum çözüm veya optimal plan doğrusal programlama problemine böyle bir çözüm denir sistem (1), koşul (3)'ün tüm kısıtlamalarını karşılayan ve aynı zamanda maksimumu (minimum) veren amaç fonksiyonu (2).

kanonik	Standart	Genel
1) Kısıtlamalar
Denklemler	eşitsizlikler	denklemler ve eşitsizlikler
2) Olumsuzluk olmama koşulları
Tüm değişkenler	Tüm değişkenler	Değişkenlerin bir kısmı
3) amaç fonksiyonu
(maks. veya dakika)

Burada: - görev değişkenleri; – amaç fonksiyonundaki değişkenler için katsayılar; – problemin ana kısıtlamalarındaki değişkenler için katsayılar; kısıtlamaların doğru parçalarıdır.

Örnek. Problemin ekonomik-matematiksel bir modelini oluşturun: A ve B olmak üzere iki tür ürünün üretimi için tesis dört tür hammadde kullanır (I, II, III, IV). A ürününün üretimi için ihtiyacınız olan: 2 birim. birinci tip hammaddeler, 1 birim. ikinci tip, 2 adet. üçüncü tip ve 1 birim. dördüncü tür. B ürününün üretimi için gereklidir: 3 adet. birinci tip hammaddeler, 1 birim. ikinci tip, 1 birim. üçüncü tür. Hammadde stokları I tip - 21 adet, II tip - 8 adet, III tip - 12 adet, IV tip - 5 adettir. A tipi bir ürünün piyasaya sürülmesi 3 UDE karı ve B tipi bir ürün - 2 UDE getirir. En büyük karı sağlayan bir üretim planı çizin.

Çözüm Oldukça sık olarak, bir ekonomik problemin matematiksel bir modelini derlerken, bu koşulları bir tablo şeklinde sunmak uygundur:

Let - piyasaya sürülmesi planlanan sırasıyla A ve B tipi ürünlerin sayısı (, ).

O zaman kar: , üretim planı en büyük karı sağlaması gerektiğinden, o zaman problemin amaç fonksiyonu: .

Verilen hammadde sınırlılığını kullanarak bir kısıtlama sistemi oluşturacağız. Planlanan üretim hacimleri ile, 21 birimlik stoğu aşmaması gereken tip I hammaddeler tüketilir: (adet). O. eşitsizliği elde ederiz: . Her bir hammadde türü için eşitsizlikleri derleyerek, sistemi elde ederiz:

Doğrusal programlama probleminin matematiksel bir modelini elde ederiz:

Örnek. Problemin matematiksel modelini yapın: Dört makinede (I, II, III, IV) iki tür parça (A ve B) işlenir. Her parça tüm makinelerde işlenir. Her makinedeki parçaların işlem süresi, makinelerin bir üretim döngüsü boyunca çalışma süresi ve bir parçanın üretiminden elde edilen kar bilinmektedir. Veriler tabloda verilmiştir:

B tipi parça sayısının A tipi parça sayısından az olmaması şartıyla en büyük karı sağlayan bir üretim planı yapın.

Çözüm Let - piyasaya sürülmesi planlanan sırasıyla A ve B tipi parçaların sayısı (, ). Görev bir öncekine benzer, ancak modeli derlerken şu ifade gözden kaçırılmamalıdır: B tipi parçaların sayısı, matematiksel olarak temsil edilebilen A tipi parçaların sayısından az olmamalıdır. eşitsizlik: .

Daha sonra doğrusal programlama probleminin matematiksel modeli şu şekildedir:

Herhangi bir LPP, kanonik, standart veya genel bir soruna indirgenebilir.

görevleri getirmek kanonik biçim

bir görevimiz olsun Genel görünüm, kanonik forma indirgenmesi gereken, yani eşitsizlik kısıtlamalarından eşitlik kısıtlamaları yapmak için. Bunu yapmak için, eşitsizlik işareti "" ise "+" işaretiyle ve eşitsizlik işareti "" ise "-" işaretiyle her kısıtlamaya negatif olmayan ek bir denge değişkeni eklenir. Bu değişkenler amaç fonksiyonuna sıfır katsayı ile girerler, yani amaç fonksiyonunun değeri değişmez.

Not : 1) B kanonik biçim eşitlikler genellikle kısıtlamaların sağ tarafları negatif olmayacak şekilde yazılır. Herhangi bir negatif ise, o zaman çarpma i(–1) üzerindeki kısıtlama, sağ tarafta pozitif bir sayı elde ederiz. Bu durumda, eşitsizlik işareti tersine çevrilmelidir.

2) Kısıt "=" işaretini içeriyorsa, ek bir değişken girmeye gerek yoktur.

Örnek. Doğrusal programlama problemini kanonik formda yazın.

maks. (dakika)

Çözüm. Sistemin ikinci kısıtı sağ tarafta yer almaktadır. negatif bir sayı-2. İkinci kısıtlamayı (–1) ile çarpın ve eşitsizlik işareti tersine dönecektir. Görev şu şekli alacaktır:

maks. (dakika)

Birinci ve ikinci kısıtlamalara sırasıyla ek bir değişken ekleriz ve üçüncüsünden ek bir değişken çıkarırız. Sorunun aşağıdaki kanonik formuna sahibiz:

maks. (dakika)

.

Aşağıdaki görevlerin ekonomik ve matematiksel modellerini derleyin:

1. İki tip ürün P1 ve P2'nin üretimi için dört tip kaynak S1 , S2 , S3 ve S4 kullanılır. Kaynak stokları, bir üretim biriminin üretimi için harcanan kaynak birimi sayısı tabloda verilmiştir:

Bir üretim biriminden alınan kar R 1 ve R 2 - sırasıyla 2 UAH. ve 3 UAH.

3. Toplam alanı 375 m 2 olan yeni bir üretim sahası için ekipman alımı için işletme gerekli miktara sahiptir. Para. Bir işletme iki tür ekipman sipariş edebilir: 10.000 UAH değerinde birinci tip makineler, 6 m 2'lik bir üretim alanı (koridorlar dahil) gerektiren, vardiya başına 4.000 birim ürün üreten makineler ve maliyeti UAH olan ikinci tür makineler 20.000, 10 m 2 alan kaplıyor, vardiya başına 5000 birim üretiyor. Genel performans Bu üretim sahasının her vardiyasında en az 221.000 adet ürün olmalıdır. İşletmenin ekipman satın alması için en iyi seçeneğin en düşük toplam maliyeti sağlayan seçenek olması koşuluyla sorunun bir modelini oluşturun.

4. Çiftçi en az 120 ton buğday, 70 ton mısır ve 15 ton karabuğday üretmeyi planlıyor. Bunun için 1000 ve 800 hektarlık iki dizi tarım arazisi kullanabilirsiniz. Tablo, farklı alanlardaki her mahsulün verimini (üst gösterge) ve çeşitli mahsullerin üretiminde 1 hektar tarım arazisi başına maliyeti (alt gösterge) göstermektedir. Brüt tahıl hasadının planlanan hedefi karşılaması ve maliyetlerin maliyetinin en düşük olması için böyle bir ekim planı hazırlamak gerekir.

5. Şirket ürünlerinin reklamını televizyon, radyo ve gazeteler aracılığıyla yapma imkanına sahiptir. Şirketin bütçesindeki reklam maliyetleri 8.000 UAH ile sınırlıdır. her ay. Geçmiş yılların deneyimi, televizyon reklamcılığına harcanan 1 Grivnası'nın şirkete 10 Grivnası kar sağladığını ve radyo ve gazete reklamlarına harcanan - sırasıyla 4 ve 8 Grivnası olduğunu göstermiştir.

Şirket, TV ve radyo reklamlarına %70'ten fazla harcama yapma niyetinde değil reklam bütçesi ve gazete reklamlarının maliyeti, radyo reklamlarının maliyetinin iki katından fazla olmamalıdır.

6. Fabrika ürünleri standart genişlik - 2 m kağıt rulolar şeklinde üretilmektedir.Tüketicilerin özel talebi üzerine fabrika standart ruloları keserek diğer boyutlarda rulolar da tedarik etmektedir. Rulolar için tipik uygulamalar özel boyutlar tabloda gösterilmiştir:

Tanımlamak en iyi seçenek gelen tüm özel isteklerin yerinde karşılanacağı standart ruloların kesilmesi minimum maliyet kağıt.

Doğrusal Programlama Problemlerini Çözmek için Grafik Yöntem

1. Doğrusal eşitsizliklerin çözüm alanı.

İki değişkenli doğrusal bir eşitsizlik verilsin ve

(1)

Nicelikler ve düzlemdeki bir noktanın koordinatları olarak kabul edilirse, düzlemde koordinatları eşitsizliği (1) karşılayan noktalar kümesine bu eşitsizliğin çözüm bölgesi denir. Bu nedenle, eşitsizliğin (1) çözüm alanı, sınır düz çizgisi olan bir yarım düzlemdir. .

örnek 1

Çözüm. İki noktadan, örneğin koordinat eksenleri (0; 4) ve (6; 0) ile kesişme noktalarından düz bir çizgi oluşturuyoruz. Bu çizgi, uçağı iki parçaya ayırır, yani. iki yarım düzleme bölünür. Düzlemde çizilen çizgi üzerinde olmayan herhangi bir noktayı alıyoruz. Bir noktanın koordinatları verilen bir eşitsizliği sağlıyorsa, çözüm alanı bu noktanın bulunduğu yarı düzlemdir. Hatalı bir sayısal eşitsizlik elde edersek, çözüm alanı bu noktanın ait olmadığı yarı düzlemdir. Genellikle kontrol için bir nokta (0; 0) alınır.

Verilen eşitsizliğin yerine ve koyun. biz alırız Bu nedenle, "sıfıra doğru" yarım düzlem, bu eşitsizliğin çözüm bölgesidir (Şekil 1'in gölgeli kısmı).

Örnek 2 Eşitsizlik tarafından tanımlanan yarım düzlemi bulun

Çözüm. Örneğin (0; 0) ve (1; 3) noktalarına göre düz bir çizgi oluşturuyoruz. Çünkü çizgi orijinden, noktadan (0; 0) geçer, o zaman onu kontrol altına alamazsınız. Örneğin (– 2; 0) noktasını alın ve koordinatlarını verilen eşitsizliğe yerleştirin. biz alırız Bu doğru değil. Dolayısıyla, bu eşitsizliğin çözüm bölgesi, ait olmayan bu yarım düzlem olacaktır. kontrol Noktası(Şekil 2'deki gölgeli kısım).

2. Doğrusal eşitsizlikler sisteminin çözüm alanı.

Örnek. Eşitsizlik sisteminin çözüm alanını bulun:

Çözüm. 1. eşitsizlik (Şekil 1) ve 2. eşitsizlik (Şekil 2) için çözüm alanını bulun.

Taramanın üst üste bindiği düzlem parçasının tüm noktaları hem birinci hem de ikinci eşitsizlikleri sağlayacaktır. Böylece verilen eşitsizlik sistemi için çözüm bölgesi elde edilmiş olur (Şekil 3).

Eğer verilen sistem eşitsizlikler koşulları ekleyin ve ardından eşitsizlikler sisteminin çözüm alanı sadece I koordinat çeyreğinde yer alacaktır (Şekil 4).

Sisteme çözüm bulma ilkesi doğrusal eşitsizlikler sistemdeki eşitsizliklerin sayısına bağlı değildir.

Not : Kabul edilebilir çözümler bölgesi (ODD), eğer varsa, kapalı veya kapalı olmayan bir dışbükey çokgendir.

3. LLP'yi çözmek için grafik yöntemin algoritması

Bir doğrusal programlama problemi sadece iki değişken içeriyorsa çözülebilir. grafik yöntem aşağıdaki işlemleri gerçekleştirerek:

1) Sistemin kısıtlamalarına karşılık gelen tüm yarım düzlemleri inşa ediyoruz.

2) Uygulanabilir çözümlerin alanını (ODD), tüm inşa edilmiş yarım düzlemlerin kesiştiği bir dizi nokta olarak buluyoruz.

3) Koordinatların orijininden başlayarak bir vektör oluşturuyoruz, burada ve amaç fonksiyonundaki bilinmeyenlerin katsayılarıdır. Bu vektör artan amaç fonksiyonunun yönünü gösterir.

4) Vektöre dik olarak, sözde seviye çizgisini çiziyoruz (yani, orijinden geçen düz bir çizgi).

5) Seviye çizgisini vektör yönünde kendisine paralel hareket ettirin (görev maksimumda ise ( maks.)) veya ters yönde (görev en aza indirmek ise ( dakika)) seviye çizgisinde en az bir tane olduğu sürece ortak nokta ODR ile.

6) Bu ortak uç noktanın koordinatlarını, bulunduğu kesişme noktasındaki çizgilerin denklem sistemini çözerek buluruz.

7) Bu koordinatları amaç fonksiyonunda yerine koyuyoruz ve buluyoruz maks.(veya dakika).

Örnek. Bir grafik yöntemi kullanarak bir doğrusal programlama problemini çözün

Çözüm. Sistemin üçüncü ve dördüncü kısıtlamaları çifte eşitsizliklerdir; elde edilen eşitsizliklerden birincisi (veya ) negatif olmama koşulunu, ikincisi ise kısıtlamalar sistemini ifade eder. Benzer şekilde, bu ve .

O. görev şeklini alacak

Eşitsizlik işaretlerini tam eşitlik işaretleri ile değiştirerek, çizgi denklemleri için uygun çözümler alanı oluşturuyoruz:

Eşitsizliklerin çözüm alanı beşgendir. ABCDE .

Bir vektör oluşturalım, vektöre dik koordinatların orijinden geçen bir düz çizgi çizelim. Ve sonra uygun çözümler bölgesinden çıkış noktasına vektör yönünde kendisine paralel hareket ettireceğiz. nokta bu olacak İTİBAREN. Birinci ve dördüncü doğruların denklemlerinden oluşan sistemi çözerek bu noktanın koordinatlarını bulalım:

Noktanın koordinatlarını değiştirin İTİBAREN amaç fonksiyonuna girin ve maksimum değerini bulun Örnek. Düzey çizgileri oluşturun ve bir doğrusal programlama problemi için:

maks. (dakika)

Çözüm. Uygulanabilir çözümlerin alanı açık bir alandır (Şekil 6). Seviye çizgisi noktadan geçer AT. İşlev Z bu noktada minimuma sahiptir. Uygulanabilir çözümler bölgesinden çıkış noktası olmadığı için seviye çizgisi çizilemez, yani .

Bağımsız çalışma için görevler .

1. Eşitsizlik sisteminin çözüm alanını bulun:

2. Doğrusal programlama problemini grafiksel olarak çözün

3. Ekonomik ve matematiksel bir model derleyin ve doğrusal programlama problemini grafiksel olarak çözün

Şirket A ve B olmak üzere iki tip ürün üretmektedir. Her tip ürün iki makinede (I ve II) işlenmektedir. Her türden bir ürünün makinelerde işlenme süresi, makinelerin vardiya, şirketin A tipi ve B tipi bir ürünün satışından elde ettiği kar tabloda listelenmiştir:

Satış piyasası üzerine yapılan bir araştırma, B tipi ürünlere olan günlük talebin A tipi ürünlere olan talebi hiçbir zaman 40 birimden fazla geçmediğini ve A tipi ürünlere olan talebin günde 90 birimi geçmediğini gösterdi.

En büyük karı sağlayan ürünlerin üretim planını belirleyin.

Doğrusal Programlama Problemlerini Çözmek için Simplex Yöntemi

Simplex yöntemi, planı art arda iyileştirme yöntemidir. Bu yöntem, herhangi bir sayıda değişken ve kısıtlama ile doğrusal programlama problemlerini çözmek için kullanılabilir.

Bu yöntem üç ana adımı içerir:

2) En iyi (daha doğrusu en kötü değil) çözüme geçiş kuralı.

3) Bulunan çözümün optimallik açısından kontrol edilmesi için kriter.

Simplex yönteminde, aynı türdeki hesaplama prosedürleri (yinelemeler), optimal bir görev planı elde edilene veya olmadığı anlaşılana kadar belirli bir sırayla gerçekleştirilir.

1) İlk temel planın inşası.

Bu doğrusal programlama problemi önce kanonik forma indirgenmelidir; bu durumda kısıtlamaların sağ tarafları negatif olmamalıdır.

Bir başlangıç ​​referans planı oluşturma olasılığının bir işareti, negatif olmayan her bir eşitlik kısıtlamasının varlığıdır. Sağ Taraf temel değişken.

temel yalnızca bir denklemde yer alan (diğerlerinde olmayan) ve aynı zamanda bire eşit bir katsayıya sahip olan planlı bir değişken olarak adlandırılır.

Doğrusal programlama probleminin kanonik forma indirgenmesine izin verin ve kısıtlama sisteminin tüm denklemlerinin kendi temel değişkenleri olsun. Temel değişkenleri kısıtlamaların karşılık gelen sağ taraflarına ve geri kalan değişkenleri sıfıra eşitleyerek, soruna bir referans veya temel çözüm elde ederiz.

Örnek. Belirli bir doğrusal programlama problemi için bir başlangıç ​​referans planı (temel çözüm) bulun.

Çözüm. İkinci ve üçüncü eşitsizliklerin işaretlerini –1 ile çarparak tersine çevirelim. Kısıtlama sistemi şimdi şöyle görünecek:

Soldaki her kısıtta sırasıyla bir pozitif değişken ekliyoruz, problemin kanonik formunu yazıyoruz:

Temel değişkenler. Bunları kısıtlamaların doğru kısımlarına eşitliyoruz: Diğer tüm değişkenler serbest, sıfıra eşitliyoruz:

İlk temel planı yazalım

(0; 0; 0; 0; 16; 4; 0).

2) Simpleks tabloların derlenmesi. Optimallik kriteri.

Simpleks yöntemi, tek yönlü tabloların oluşturulması kullanılarak rahatlıkla uygulanır. İlk plana karşılık gelen ilk tek yönlü tablo:

temel		AT			…
					…
					…
					…
…	…	…	…	…	…	…
					…
					…

Aşağıdaki notasyon burada benimsenmiştir.

Temel sütunu, temel değişkenlerdir.

"" Sütunu, amaç fonksiyonundaki temel değişkenlerin katsayılarıdır.

Sütun "B" - kısıtlamaların doğru kısımları;

kısıtlamalardaki değişkenler için katsayılar;

amaç fonksiyonundaki değişkenlerin katsayılarıdır.

Tablodaki () son satır bir kontrol veya değerlendirme satırıdır.

oluşturulan başlangıç ​​planına karşılık gelen amaç fonksiyonunun değeridir. Şu şekilde bulunur: sütunun her bir elemanı, B sütununun karşılık gelen elemanı ile çarpılır ve ürünler eklenir, yani.

- tahminler veya tek yönlü farklar olarak adlandırılır ve şu şekilde bulunur: sütunun öğeleri, sütunun karşılık gelen öğeleriyle çarpılır, sonuçlar toplanır ve çıkarılır.

Örneğin,

Temel değişkenlerin tahminleri () her zaman sıfıra eşittir.

Temel planın uygunluğunun işareti aşağıdakilerden oluşur:

Referans plan, ancak ve ancak tüm tahminler

üzerinde bir görev için maks. ve

üzerinde bir görev için dakika .

Optimallik kriterleri karşılanmazsa, daha kötü olmayan bir referans planına geçmek gerekir, yani. bazı değişkenleri temelden çıkarmak ve onun yerine serbest değişkenler arasından yenisini getirmek.

Temele dahil edilecek değişken, optimallik koşulunu sağlamayan tahmine karşılık gelir. Bu tür birkaç tahmin varsa, aralarından mutlak değer bakımından en büyüğü seçilir ve buna karşılık gelen değişken temele dahil edilir. Bu değişkene sahip sütuna denir müsamahakâr .

Tabandan türetilecek değişkeni belirlemek için şu şekilde hareket edilir: B sütunundaki elemanlar sadece çözümleme sütununun pozitif elemanlarına bölünür ve tek yönlü ilişkiler bulunur. En küçüğünden seçin. Temele girilecek değişkeni isimlendirir. Karşılık gelen tablo satırı denir müsamahakâr .

Etkinleştirme sütunu ile etkinleştirme satırının kesiştiği noktada etkinleştiren öğe .

Şimdi aşağıdaki tabloyu doldurmaya başlıyoruz. Bu işlemi gösterelim özel örnek.

Örnek. Simplex yöntemini kullanarak bir doğrusal programlama problemini çözün.

Çözüm. 1) Sorunu kanonik forma getiriyoruz, yani. eşitsizliklerin kısıtlamalarından eşitlikler yaparız.

2) Temel değişkenleri tanımlarız - bu .

3) İlk tabloyu doldurun

temel		AT	2	3	0	0	0	0
	0	18	1	3	1	0	0	0
	0	16	2	1	0	1	0	0
	0	5	0	1	0	0	1	0
	0	21	3	0	0	0	0	1	–

Burada ve sıfırdan küçük oldukları için optimallik koşulunu sağlamazlar. Aralarından en büyük moduloyu seçiyoruz. BT . Bu nedenle, değişken sütunu izinlidir. Yani içinde yeni temel bir değişken girmeniz gerekir.

Bulmak: ; ;

Bu sayıların en küçüğü, temel değişken dizisine karşılık gelen 5 sayısıdır. Bu, temel değişken dizisinin çözüldüğü anlamına gelir, bu nedenle değişkeni temelden türetmek gerekir. Eleman =1 müsamahakardır. Yeni temel: .

Aşağıdaki tabloyu "Temel" ve "" sütunlarıyla doldurmaya başlıyoruz. Ardından, izin verilen çizgiyi her bir elemanını izin verilen, yani izin veren olarak bölerek dolduruyoruz. Çözümleme sütununun tüm elemanları sıfır olacaktır, her zaman 1'e eşit olan çözümleme sütunu hariç. Bu değişkenler tabanda kaldığı için altındaki sütunları değiştirmeden yeniden yazıyoruz. Diğer unsurlar yeni masa dikdörtgen kuralına göre bulunuz. Örneğin, bir dikdörtgenden bir eleman bulalım.

Veya eleman = dikdörtgenden

Yeni tablo için tahminler aynı kural kullanılarak bulunabilir.

Genel olarak, bu sorunun tablo şeklinde simpleks yöntemiyle çözümü şu şekilde olacaktır:

temel		AT	2	3	0	0	0	0
	0	18	1	3	1	0	0	0	6
	0	16	2	1	0	1	0	0	16
	0	5	0	1	0	0	1	0	5
	0	21	3	0	0	0	0	1	–
		0	–2	–3	0	0	0	0	sekme. bir
	0	3	1	0	1	0	–3	0	3
	0	11	2	0	0	1	–1	0	5,5
	3	5	0	1	0	0	1	0	–
	0	21	3	0	0	0	0	1	7
		15	–2	0	0	0	3	0	sekme. 2

temel		AT	2	3	0	0	0	0
	2	3	1	0	1	0	–3	0	–
	0	5	0	0	–2	1	5	0	1
	3	5	0	1	0	0	1	0	5
	0	12	0	0	–3	0	9	1
		21	0	0	2	0	–3	0	sekme. 3
	2	6	1	0	–0,2	0,6	0	0
	0	1	0	0	–0,4	0,2	1	0
	3	4	0	1	0,4	–0,2	0	0
	0	3	0	0	0,6	–1,8	0	1
		24	0	0	0,8	0,6	0	0	sekme. dört

Dördüncü tablonun tahmini satırı, tüm .

B sütunundaki değerlerdir, yani , , , .

Ücretsiz (temel olmayan) değişkenler.

Yani, = (6; 4; 0; 0; 1; 3),

Not: Kontrol için tablodan tabloya geçerken, maksimum görev için öncekinden daha az ve minimum görev için öncekinden daha fazla olmaması gereken karşılaştırırlar.

kullanma tek yönlü yöntem aşağıdaki durumlar mümkündür.

1) Simplex tablosunun değerlendirme satırında puan = 0, serbest bir değişkene karşılık geliyorsa, bu, LLP'nin benzersiz bir optimal planı olmadığı anlamına gelir.

2) Bir referans plandan diğerine geçiş sırasında çözüm sütununda pozitif öğeler yoksa, bu, LLP amaç fonksiyonunun sınırsız olduğu ve optimal planların olmadığı anlamına gelir.

Bağımsız çalışma için görevler .

Doğrusal programlama problemlerini çözmek için tek yönlü yöntemi kullanarak en uygun görev planını belirleyin:

a)

b)

m içinde

dualite kavramı

1) Simetrik ikili problemler

Üretim planlama problemini ele alalım. Şirketin sahip olmasına izin ver m birim cinsinden kaynak türleri. Bu kaynaklar serbest bırakmak için kullanılmalıdır. nürün türleri. Izin vermek tüketim oranı i-birim üretim başına kaynak türü j-inci ürünler; - satış fiyatı j-inci ürünler; - üretim hacmi jşirkete maksimum gelir sağlayan ürün.

Üretim planı, kaynakların kullanımındaki kısıtlamalar altında toplam üretim maliyetini maksimize etme koşulundan hazırlanmalıdır.

Veya kısaca, problemin matematiksel modeli şu şekildedir:

(1)

Problem (1) - (3) orijinal olarak adlandırılır.

Problem (1) - (3)'ün ilk verilerine dayanarak, başka bir ekonomik problem oluşturacağız.

İşletmenin belirtilen tüm kaynakları kendi takdirine bağlı olarak satmasına izin verildiğini varsayalım. Aşağıdaki hususları kullanarak - , onlar için fiyatlar belirlemek gereklidir:

- alıcı, toplam maliyetlerini en aza indirmeye çalışır;

- şirket, üretilen ürünlerin satışından elde edebileceği gelirden daha az olmayan bir kâr sağlayan fiyatlarla satış yapmayı kabul eder.

Bu gereksinimler aşağıdaki LLP olarak yazılabilir:

Veya kısaca:

(4)

Ortaya çıkan problem (4) - (6) ikili olarak adlandırılır. Değişkenlere ikili değerlemeler veya gölge fiyatlar denir.

(1) - (3) ve (4) - (6) problemlerine, aşağıdaki özelliklere sahip oldukları için bir çift karşılıklı ikili simetrik problem denir:

1. Bir görevde amaç fonksiyonunun maksimumu aranıyorsa, diğerinde - minimum.

2. Bir problemin amaç fonksiyonundaki değişkenlerin katsayıları, başka bir problemin kısıtlamalarının doğru parçalarıdır ve bunun tersi de geçerlidir.

3. Her problemde, kısıtlamalar sistemi eşitsizlikler şeklinde verilir ve hepsi aynı anlama gelir: eğer problem açıksa maks., o zaman tüm eşitsizlikler "" işaretlerini içerir, eğer açıksa dakika, o zaman tüm eşitsizlikler "" işaretleri içerir.

4. Direkt ve kısıtlama matrisleri ikili görevler birbirine aktarılır.

5. Bir problemin kısıtlama sistemindeki eşitsizliklerin sayısı, başka bir problemin değişken sayısına eşittir.

6. Her iki problemde de değişkenlerin negatif olmama koşulu korunmuştur.

Not: "Doğrudan" ve "ikili" problem kavramı koşulludur.

2) İkili problemin bir modelini oluşturmak

Özellikleri (1-6) kullanarak, belirli bir örnek kullanarak ikili bir problemin yapısını gösteriyoruz.

Örnek.İzin vermek ilk görevşuna benziyor:

Bunun için bir dual yapmalısın.

Çözüm. Kısıt sisteminin genişletilmiş matrisini yazalım ve transpoze edelim.

1	–1	2	2	1	2	5	11	2
2	1	–3	4	bir T =	–1	1	–1	1	3
ANCAK =	5	–1	1		3	2	–3	1	2	1
11	1	2	1	2	4	3	1	dakika
2	3	1	maks.

Şimdi ikili problemi şu şekilde yazıyoruz: bir T değişkenlerle , .

Örnek. Verilen problem için ikiliyi yazın:

Çözüm. görev olduğu için dakika, o zaman tüm eşitsizliklerin "" işaretleri olmalıdır. Bunun için ikinci kısıtı (–1) ile çarpıyoruz; bu durumda eşitsizlik işareti tersine dönecektir. Şimdi görev şöyle görünecek:

matrisleri yazalım ANCAK ve bir T .

1	1	1	1	–2	5
ANCAK =	–2	–3	–5	bir T =	1	–3	2
5	2	dakika	1	–5	maks.

İkili görev:

3) Dualite teoremlerinin bir çift simetrik ikili problemin optimal çözümlerinin analizine uygulanması

Aşağıdaki problemi göz önünde bulundurun. İşletme 3 tip ürün üretmeyi planlıyor - P 1, P 2, P 3. Bunu yapmak için 3 tip kaynağa sahiptir R 1 , R 2 , R 3 . Bir üretim biriminin üretimi için her bir kaynağın maliyeti ve bir üretim biriminin fiyatı tabloda verilmiştir:

	S 1	S 2	S 3
R 1	4	2	1	180
R 2	3	1	1	210
R 3	1	2	5	244
	10	14	12

Gerekli:

1) orijinal ve ikili problemlerin bir modelini oluşturun;

2) asıl problemi simpleks yöntemle çöz;

3) son kontrol çizgisini kullanarak ikili problem için en uygun çözümü bulun tek yönlü tablo;

4) her iki soruna da optimal çözümlerin ana ve ek değişkenlerinin ekonomik bir analizini vermek;

5) cevapta, her iki problemin en uygun çözümlerini ve amaç fonksiyonlarının değerlerini yazın; en kıt kaynağı ve en kârsız ürün türünü gösterir.

Çözüm. 1. Orijinal problemin bir modelini oluşturun

Burada X 1 , X 2 , X 3 - üretim planı.

Dual problemin matematiksel bir modelini oluşturalım:

2. Asıl problemi simpleks yöntemi ile çözelim.

Kanonik biçimini yazıyoruz:

X 4 , X 5 , X 6 - ek ve aynı zamanda temel değişkenlerdir. Başlangıç ​​referans planı (0; 0; 0; 180; 210; 244).

temel		AT	10	14	12	0	0	0
	0	180	4	2	1	1	0	0	90
	0	210	3	1	1	0	1	0	210
	0	244	1	2	5	0	0	1	122
		0	–10	–14	–12	0	0	0	sekme. bir

temel		AT	10	14	12	0	0	0
	14	90	2	1	0,5	0,5	0	0	180
	0	120	1	0	0,5	–0,5	1	0	240
	0	64	–3	0	4	–1	0	1	16
		1260	18	0	–5	7	0	0	sekme. 2
	14	82	2,375	1	0	0,625	0	–0,125
	0	80	1,375	0	0	0,125	1	–0,625
	12	16	–0,75	0	1	–0,25	0	0,25
		1340	14,25	0	0	5,75	0	1,25	sekme. 3

Tüm tahminler olduğundan, optimal plan elde edilir:

= (0; 82; 16; 0; 80; 0); = 1340.

3. Tek yönlü tablonun son kontrol satırını ve doğrudan ve ikili problemlerin değişkenleri arasındaki ilişkiyi kullanarak ikili problemin optimal çözümünü bulun.

ana değişkenler			ek değişkenler
ek değişkenler			ana değişkenler

Gönderen: 5.75; 0; 1.25; 14.25; 0; 0.

= (5,75; 0; 1,25; 14,25; 0; 0); 1340.

Böylece alınan = 1340.

4. Her iki problemin optimal çözümlerinin ana ve ek değişkenlerini analiz edelim. Orijinal problemin ana değişkenleri planlanan çıktıdır.

1. tipin üretiminin piyasaya sürülmesi planlanmamıştır, 2. tipin - 82 adet miktarında. ve ІІІ-th türleri - 16 birim miktarında.

Orijinal sorunun ek değişkenleri, kalan ham maddeleri gösterir.

І ve ІІІ tipi hammaddeler tamamen tükendi. Ve II tipindeki hammaddeler 80 birim miktarında kaldı.

İkili problemin ana değişkenleri, hammadde kıtlığını karakterize eder: eğer , o zaman hammadde kıttır; ise, o zaman hammadde kıt değildir.

Bu nedenle, І ve ІІІ tipindeki hammaddeler azdır ve І-th tipindeki hammaddeler en azdır. İkinci tip ham maddeler kıt değildir.

İkili sorunun ek değişkenleri, ürünlerin karlılığını karakterize eder. Aynı zamanda, eğer , o zaman üretim kârsızdır.

Bu oran, I. tip ürünlerin kârsız, II. ve III. tip ürünlerin ise kârlı olduğunu göstermektedir.

Cevap: = (0; 82; 16; 0; 80; 0); = 1340;

= (5,75; 0; 1,25; 14,25; 0; 0); 1340

1. türün en kıt hammaddeleri. En kârsız I üretim türü.

Bağımsız çalışma için görevler .

Dört çeşit ürünün (P 1, P 2, P 3, P 4) üretimi için üç çeşit kaynak kullanılır. Her türden bir üretim birimini üretmek için kullanılan kaynakların maliyet oranı, bir üretim biriminin fiyatı ve kaynak rezervleri tabloda gösterilmektedir.

Doğrudan ve ikili problemlerin bir modelini oluşturun. Hem görevler hem de amaç fonksiyonlarının uç değerleri için en uygun planı bulun. Orijinal ve ikili problemlerin ana ve ek değişkenlerinin ekonomik bir yorumunu verin.

Kaynak Ürünleri	Çıktı birimi başına kaynak maliyetleri				kaynaklar
	S 1	S 2	S 3	P 4
R 1	2	3	4	4	2100
R 2	5	5	0	7	2800
R 3	8	7	10	9	3000
	60	65	55	62

Taşıma görevi (TK)

Nakliye sorunu, malların rasyonel nakliyesini planlarken ortaya çıkar. Matematiksel model taşıma görevi en basit durumda şöyle görünür:

maks. (1)

(2)

Burada: - tedarikçi stokları;

- tüketici talebi;

– tarifeler, yani -inci tedarikçiden -inci tüketiciye bir birim kargo taşıma maliyeti;

Z- Ücret;

i. tedarikçiden i. tüketiciye taşınan ürün miktarı.

Genellikle, bir taşıma görevi üç matrisle tanımlanır: tedarikçiler matrisi, tüketiciler matrisi ve tarifeler matrisi.

Anlaşılır olması için, taşıma görevi bir dağıtım tablosu şeklinde sunulur.

Herhangi bir ulaşım probleminin uygulanabilir bir çözümü (trafik matrisi) vardır:

Koşul (4) sağlanıyorsa, ulaşım sorununa ulaşım sorunu denir. kapalı tip .

Bir ulaşım sorununa uygulanabilir bir çözüm genellikle ulaşım planı olarak adlandırılır.

1) İlk temel planın inşası. Dejenerasyonu veya yozlaşmaması. Sistem matrisinin sıralaması.

a) Kuzeybatı köşe yöntemi.

Dağıtım tablosunda doldurma işlemi (1; 1) hücresinden başlarken . Ayrıca, ya çizgi boyunca sağa ya da sütun boyunca hücreye doğru kaydırılırlar. Doldurulmuş hücreler, bağlantıları karşılıklı olarak dik olan kesik bir çizgi ile bağlanabilecek şekilde yayılmalıdır.

Örnek. Kuzeybatı köşesi yöntemini kullanarak bir nakliye görevi için bir ilk referans planı oluşturun: tedarikçiler a

Ulaşım maliyetini bulun.

Çözüm. Bir dağıtım tablosu oluşturuyoruz ve yükü buluyoruz X 11 = min (20; 15) = 15. Tüketici I'in talebi karşılandığı için ilk sütunda ilerlemiyoruz. 1. satır boyunca hücreye geçiyoruz (1; 2):

X 12 = dk ( a 1 – X 11 ; b 2) = min(5; 35) = 5.

Şimdi ikinci sütun boyunca hücreye geçiyoruz (2; 2):

X 22 = dak(30; b 2 – X 12) = dak(30; 30) = 30.

İkinci tüketicinin talebi karşılandığı ve ikinci tedarikçinin ürünleri zaten seçildiği için hücreye (3; 3) geçiyoruz:

X 33 = dk(40; 20) = 20.

X 34 = dk ( a 3 – X 33 ; b 4) = min(20; 20) = 20.

Böylece, ulaşım planı elde edilir:

	15		35		20		20
20	4	6	12	5
	15		5
30	2	7	8	10
	30
40	5	3	4	6
	20		20

Nakliye ücretini hesaplamak için her dolu hücredeki kargo miktarını bu hücredeki ilgili tarife ile çarpmanız ve sonuçları eklemeniz gerekir.

b) Minimum eleman (en düşük maliyet) yöntemi.

Bir dağıtım tablosu oluşturuyoruz ve en düşük tarifeli hücreden doldurmaya başlıyoruz.

Örnek. Minimum maliyet yöntemini kullanarak bir başlangıç ​​temel planı oluşturun ve nakliye görevi için nakliye maliyetlerini bulun: tedarikçiler a= (20; 30; 40); tüketiciler = (15; 35; 20; 20); ulaşım oranları

Çözüm. Bir dağıtım tablosu oluşturuyoruz ve en düşük tarifeye sahip olduğu için hücreden (2; 1) doldurmaya başlıyoruz. X 21 = dk(30; 15) = 15.

	15		35		20		20
20	4	6	12	5
	20
30	2	7	8	10
	15		15
40	5	3	4	6
	35		5

Ardından hücreyi (3; 2) tarife ile dolduruyoruz İle birlikte 32 = 3;

X 32 = dak(40; 35) = 35.

X 14 = dak(20; 20) = 20;

X 23 = dk( a 2 – X 21 ; b 3 – X 33) = dak(15; 15) = 15.

karşılaştırma değeri Z a) ve b)'de, nakliye maliyeti dikkate alındığında, ikinci yöntemin maliyetlerinin çok daha az olduğunu görüyoruz.

Sistem matrisinin sıralaması(2) numarayı arayın , yani satır sayısı artı sütun sayısı ve eksi bir. Dağıtım tablosundaki dolu hücrelerin sayısı matrisin sırasına eşitse, ortaya çıkan plana denir. dejenere değil. Aksi halde - dejenere .

a) ve b) paragraflarında ve dolu hücrelerin sayısı 5'tir. Bu nedenle, ortaya çıkan tasarımlar dejeneredir.

2) Potansiyel yöntemi. Temel planın optimalliğinin bir işareti.

Ulaştırma sorununa uygulanabilir bir çözüm, ancak ve ancak şu sayılar bulunabilirse optimaldir: potansiyeller, ve , aşağıdaki koşulları sağlayan:

II. tüm dolu hücreler için; (5)

III. tüm boş hücreler için. (6)

İlk optimallik koşuluna bağlı olarak, koşullardan potansiyeller bulunur ve keyfi olarak seçilen bir potansiyel, örneğin sıfıra eşittir.

İkinci optimallik koşulunu kontrol ederken, tüm boş hücreler için, referans plan optimaldir ve amaç fonksiyonunun karşılık gelen değeri Z minimum maliyeti belirler. Bunun için en az bir hücre varsa , o zaman plan optimal değildir ve daha kötü olmayan bir referans planına gidebilirsiniz.

3) En kötü olmayan bir referans planına geçiş.

Daha kötü olmayan bir temel plana geçiş, bir yük yeniden dağıtım döngüsü kullanılarak gerçekleştirilir. Döngü bağlantıları karşılıklı olarak dik olan ve döngünün biri hariç köşeleri dolu hücrelerde olan kapalı bir kırık çizgidir.

Döngü formlarının çeşitlerine örnekler:

Her durumda, boş bir hücrede yalnızca bir döngü tepe noktası bulunur. Buna döngünün başlangıcı denir ve optimallik koşulunun (6) en büyük ihlali ile belirlenir, yani. maksimum derecelendirmeye göre . Döngünün başlangıcındaki hücreye "+" işareti atanır, döngünün diğer tüm köşelerinde, işaretler "-", "+" vb. "-" İşaretli döngü hücrelerinden minimum yükün bulunduğu hücreyi seçin. Bu, döngü boyunca yeniden dağıtılması gereken kargo miktarı olacaktır, örn. “+” işaretli bir hücrede bu miktar yük eklenir ve “–” işaretli bir hücrede bu miktar çıkarılır. Döngüye dahil olmayan hücreler değişmeden kalır.

Böylece yeni bir temel plan elde ederiz. Öncekilerden daha fazla olmaması gereken nakliye maliyetlerini hesaplıyoruz. Yoksa bir yerlerde bir yanlışlık var. Yeni plan yine (5) ve (6) koşullarını kullanarak optimalliği kontrol ederiz. Plan optimal ise, sorun çözülür. Plan yine optimal değilse, optimal planı elde edene ve bulana kadar 3. paragrafa göre çalışırız. Zmin .

Açık tip taşıma görevi

Taşıma görevi için aşağıdaki koşullardan biri karşılanırsa

o zaman problem modeli denir açık. Böyle bir sorunun çözümünün olabilmesi için kapalı tipe yani kapalı tipe getirilmesi gerekir. böylece eşitlik devam eder.

Bunu şu şekilde yaparlar: eğer , o zaman talebi olan hayali bir tüketici ekleyin (dağıtım tablosunda, ek sütun), eğer ise, hayali bir tedarikçiyi teklifle birlikte ekleyin (dağıtım tablosunda ek bir satır görünecektir). Her iki durumda da tarifelerin sıfır olduğu varsayılır. Ayrıca, sorun daha önce ele alındığı sırayla çözülür.

hadi yazalım ulaşım problemi çözme algoritması :

1) TK modelinin türünün kontrol edilmesi.

2) Başlangıç ​​referans planının oluşturulması (herhangi bir şekilde).

3) Planın yozlaşma açısından kontrol edilmesi.

4) Potansiyel yöntemle planın optimallik açısından kontrol edilmesi:

a) sistemden potansiyelleri bulma

(tüm dolu hücreler için);

b) ikinci optimallik koşulunun doğrulanması

(tüm boş hücreler için).

5) En kötü olmayan bir referans planına geçiş (gerekirse).

Örnek. Depolarda aynı cins mallardan miktar olarak stok bulunur. a(35; 40; 40; 50) tüketiciye ulaştırılması zorunludur. Tüketicilerin ihtiyaçları vektör tarafından belirlenir b(31; 52; 17; 20). Bir birim malın nakliyesi için maliyet matrisi i Tedarikçi j-inci tüketici:

.

Çözüm. Ulaştırma problem modelinin türünü tanımlayalım. Tedarikçilerin toplam kapasitesi: 35+40+40+50=165 (mal birimi); Tüketicilerin toplam talebi: 31+52+17+20=120 (mal birimi).

Çünkü , o zaman açık tip bir modelimiz var.

Talebi şuna eşit olan hayali bir tüketiciyi tanıtıyoruz:

165 -120 = 45 (mal birimi).

Tarifeler 0. Yani. kapalı tip bir model elde ederiz, m= 4 – tedarikçi sayısı, n= 5 - tüketici sayısı. Görev matrisi sıralaması. Yönteme göre ilk temel planı oluşturalım minimum eleman(en düşük maliyetli).

	31		52		17		20		45
35	5	4	3	1	0	0
	15		20
40	2	3	5	8	0	1
	31		9
40	6	8	7	10	0	4
	40
50	5	6	7	2	0	4
	43		2		5
	1		2		3		1		– 4		Tab.1

r= 8, dolayısıyla destek tasarımı dejenere değildir.

(den. birimler).

Potansiyeller yöntemini kullanarak optimallik için temel planı araştırıyoruz.

Tablo 1'i bir sütun ve bir sıra potansiyel ve ile tamamlayalım. İlk optimallik koşulunu kullanarak potansiyel sistemini bulalım: teslimatlarla dolu hücreler için.

Yazılı sistemden şunu buluruz: , , ,, , , , , .

.

(1; 1) 0 + 1 – 5 = –40;

(1; 2) 0 + 2 – 4 = –20;

(1; 5) 0 – 4 – 0 = –40;

(2; 3) 1 + 3 – 5 = –10;

(2; 4) 1 + 1 – 8 = –60;

(2; 5) 1 – 4 – 0 = –40;

(3; 1) 4 + 1 – 6 = –10;

(3; 2) 4 + 2 – 8 = –20;

(3; 3) 4 + 3 – 7 = 00;

(3; 4) 4 + 1 – 10 = –50;

(4; 1) 4 + 1 – 5 = 00;

(4; 4) 4 + 1 – 2 = 30.

Çünkü serbest hücreler arasında, ikinci optimallik koşulunun karşılanmadığı hücreler vardır, bu durumda plan optimal değildir.

Daha kötü olmayan bir referans planına geçiş yapalım. Doldurma için en umut verici hücre (4; 4), çünkü en yüksek pozitif puana karşılık gelir.

4 + 1 – 2 = 3.

Bu hücre için yük yeniden dağıtım döngüsünü bulalım.

Doldurmak için seçilen hücreye “+” işaretini atarız, ardından işaretleri değiştiririz. “-” İşaretli köşeler arasından en küçük teslimatı seçiyoruz.

- fazla arzın hacmi.

Teslimatları döngüye göre yeniden dağıtalım, böylece yeni bir temel plana geçelim.

	31		52		17		20		45
35	5	4	3	1	0	0
	17		18
40	2	3	5	8	0	–2
	31		9
40	6	8	7	10	0	1
	40
50	5	6	7	2	0	1
	43		2		5
	4		5		3		1		–1		Tab.2

Temel plana karşılık gelen nakliye maliyetleri:

(den. birimler).

Optimallik için temel planı inceliyoruz. İlk optimallik koşulunu kullanarak potansiyellerin değerlerini bulalım. Sarf malzemeleriyle dolu hücreler için.

, , , , , , , , .

İkinci optimallik koşulunun yerine getirilip getirilmediğini kontrol edelim. Tüm boş hücreler için aşağıdaki eşitsizlik geçerli olmalıdır: .

Koşulun ihlal edildiği hücreleri yazın:

(1; 2) 0 + 5 – 4 = 10.

Daha kötü olmayan bir referans planına geçiş yapalım. Doldurma için en umut verici hücre (1; 2), çünkü pozitif bir 1 tahminine karşılık gelir. Bu hücre için yük yeniden dağıtım döngüsünü bulalım.

- fazla arzın hacmi.

Dağıtım tablosu 8'deki dolu hücrelerin sayısı, görev matrisinin sırasına eşittir r= 8, bu nedenle destekleyici tasarım (Tablo 3) dejenere değildir.

	31		52		17		20		45
35	5	4	3	1	0	0
	18		17
40	2	3	5	8	0	–1
	31		9
40	6	8	7	10	0	2
	40
50	5	6	7	2	0	2
	25		20		5
	3		4		3		0		–2		Tab.3

Temel plana karşılık gelen nakliye maliyetleri:

(den. birimler).

Optimallik için temel planı inceliyoruz.

İlk optimallik koşulunu kullanarak potansiyellerin değerlerini bulalım. Sarf malzemeleriyle dolu hücreler için.

, , ,, , , , , .

İkinci optimallik koşulunun yerine getirilip getirilmediğini kontrol edelim. Tüm boş hücreler için aşağıdaki eşitsizlik geçerli olmalıdır: .

İkinci optimallik koşulu, tüm serbest hücreler için karşılanır, bu nedenle plan optimaldir.

En düşük nakliye maliyetleri.

Cevap: ; Sarf malzemelerinin dağıtımı için en uygun plan sekmesinde yer almaktadır. 3.

Bağımsız çalışma için görevler .

Minimum nakliye maliyeti ile bir ulaşım planı yapın .

a)

b)

Excel ile optimizasyon problemlerini çözme

Ekonomik optimizasyon problemlerini çözerken aşağıdaki aşamalardan geçmek gerekir:

· Ekonomik problemin matematiksel bir modelini yapın;

Ortaya çıkan uç noktayı çözün Matematik problemi;

Cevabın ekonomik bir yorumunu yapın.

Kaynak kullanımı sorunu örneğinde bu aşamaların geçişini ele alalım.

Örnek. A ve B olmak üzere iki tür ürünün üretimi için tesis dört tür hammadde kullanır (І, ІІ, ІІІ, IV). A ürününü üretmek için 2 birim tip I hammadde gereklidir; 1 ünite tip II hammaddeler; 2 adet tip III hammaddeler; 1 ünite tip IV hammaddeler. B kaleminin üretimi için 3 birim tip I hammadde gereklidir; 1 ünite tip II hammaddeler; 1 ünite tip III hammaddeler. Hammadde stokları I tip - 21 adet, II tip - 8 adet, III tip - 12 adet, IV tip - 5 adettir. Bir A tipi ürünün piyasaya sürülmesi 3 UAH getiriyor. kar ve B tipi bir ürün - 2 UAH. ulaşmış. En büyük karı sağlayan bir üretim planı çizin.

· Matematiksel bir model oluşturma.

Formda formüle edilen problemin sorusu "en yüksek karı sağlayan bir üretim planı hazırlayın", (en yüksek kârı elde etmek için) kaç adet A ve B ürününün üretilmesi gerektiğinin belirlenmesi gerektiği anlamına gelir.

A ve B ürünlerinin sayısını belirlemek gerektiğinden, aşağıdaki gösterimi sunuyoruz:

- piyasaya sürülmesi planlanan A ürünlerinin sayısı;

- piyasaya sürülmesi planlanan B ürünlerinin sayısı;

Z(görevin nesnel işlevi) kendi yolunda Ekonomik anlamda kârdır. (Çünkü problemin durumundan, kelimenin "En büyük" ekstremum ile ilişkili kara karşılık gelir).

– problemin matematiksel modeli.

Ortaya çıkan aşırı problemin çözümü:

Sorunu çözmek için Microsoft Excel'in yeteneklerini kullanacağız.

Microsoft Excel'i açın.

İlk sıranın hücrelerinde (içinde bu durum A1 ve B1) görevde bulunan değişkenlerin tanımlarını girin (dil ve yazı tipi önemli değil, çünkü bunlara karşılık gelen sayıların anlamlarını anlamak için atamalar gereklidir).

Birinci sıranın dolu hücrelerine karşılık gelen ikinci sıranın hücrelerinde (bu durumda A2 ve B2), değişkenlerin rasgele değerlerini girin (basitlik için, 1, aslında bunlar herhangi bir sayı olabilir). Böylece, şimdiye kadar 1 değerlerini atadık.

A4 hücresine, Z= amaç fonksiyonunun tanımını girin.

B4 hücresine, problemin matematiksel modelinden amaç fonksiyonunu hesaplamak için formülü girin.

(), ve yerine A2 ve B2 hücrelerinden karşılık gelen değerleri değiştirerek. (Formülün girişinin = işaretiyle başladığını unutmayın)

Enter düğmesine bastıktan sonra, monitör ekranında aşağıdaki görünmelidir. (Başka değerler ve örneğin 1 değil 2 girerseniz resmin nasıl değişeceğini düşünün. Şimdi deney yapın. Tahmininiz gerçekleşti mi?)

A5 ve B5 hücrelerinde sırasıyla şu kelimeleri girin: A5 - Kısıtlama, B5 - sağ kısım kısıtlamalar.

A6 hücresinde, ilk kısıtlamanın sol tarafını hesaplamak için formülü girin ve A2 ve B2 hücrelerinden karşılık gelen değerlerle değiştirin.

B6 hücresine, ilk kısıtlamanın serbest terimini girin - 21. Enter düğmesine bastıktan sonra, monitör ekranında aşağıdaki görünmelidir.

Benzer şekilde, A7 hücresine ikinci kısıtlamanın sol tarafını hesaplamak için formülü girin ve B7'de serbest terimi 8'dir; A8 hücresine üçüncü kısıtlamanın sol tarafını hesaplamak için formülü girin ve B8'de serbest terimi 12'dir; A9 hücresine dördüncü kısıtlamanın sol tarafını hesaplamak için formülü girin ve B9'da serbest terimi 5'tir;

Enter düğmesine bastıktan sonra, monitör ekranında aşağıdaki görünmelidir.

Böylece problemin tüm bu şartlarını bilgisayara girdik ve problemi çözmek için hazırlandık.

Menüde Hizmet takım seç Çözüm Bulmak (optimizasyon problemlerine çözüm bulmak için bir araç olan odur)

Bu komut sizden hedef hücreyi ayarlamanızı isteyecektir. bu kelime "hedef" ne olduğunu hatırlamana yardım et söz konusu. Tabii ki, amaç fonksiyonunun değeri hakkında. B4 hücresindeki farenin sol düğmesine tıklayarak bu değeri girin (bu durumda amaç fonksiyonunun sayısal değerini içerir). Almak:

Çünkü bu problemde, Z fonksiyonu maksimuma kadar araştırılır, sonra ayrılırız Eşit: maksimum değer .

Sorunu en aza indirirsek, kelimelerin önüne bir işaret koymanız gerekir. Minimum değer.

Ortaya çıkan alana, görevde değişen değişkenlerin aralığını girmelisiniz (örn. Sayısal değerler ve , tam olarak ve farklı sayısal değerler alabildiğinden, aralarında soruna en uygun çözümü bulmaya çalıştığımız).

Şunlar. doldurulmuş hücre şöyle görünmelidir:

Bundan sonra, hücrenin boşluğunu doldurun Kısıtlamalar: neden butona tıklayın Ekle , ekranda görünen yeni bir pencereyle sonuçlanır:

Sunulan seçeneklerden matematiksel modele göre kısıtlamanın işaretini seçin (bu durumda<=, т. к. первое ограничение со знаком )

AT sınırlama: kısıtlamanın serbest üyesini içeren hücrenin numarasını girin (bu durumda, ilk kısıtlama için bu, B6 hücresidir).

O. Ekranınızda aşağıdaki resmi görmelisiniz:

Yalnızca ilk kısıtlamaya giren sizdiniz, ancak başkaları da var, bu yüzden düğmeye tıklayın Ekle ve benzer şekilde ikinci, üçüncü ve dördüncü kısıtlamaları girin.

Ancak sistemin tüm kısıtlamaları getirildikten sonra, basmak için henüz çok erken. TAMAM , çünkü matematiksel modelde değişkenlerin () olumsuz olmaması koşulu vardır ve bilgisayar için sorunun açıklamasında bundan henüz bahsedilmemiştir.

Bu nedenle, son kısıtlamanın getirilmesinden sonra düğmeye tekrar basın Ekle ve Hücre bağlantısı: sayısal değeri içeren hücrenin numarasını girin; >= işaretini seçin; ve sınırlama: 0 girin.

tekrar tıklayın Ekle ve benzer şekilde, için olumsuzluk olmayan bir koşul yaratın.

Böylece bilgisayar, sorun durumunda olan tüm kısıtlamaları almıştır, bu nedenle artık tıklayabilirsiniz TAMAM . Sonuç olarak, ekranda aşağıdakiler görünecektir:

Göründü? EVET ise, o zaman basın Koşmak .

Şimdi Z'nin hangi değerleri aldığına dikkat edin.

dört; = 4; Z = 20 - Bu, soruna () ve karşılık gelen en uygun çözüme sahiptir.

amaç fonksiyonunun uç değeri ().

Matematiksel olarak problem çözüldü. Ekonomik vermek kalır

alınanın yorumlanması.

Cevabın ekonomik bir yorumunu yapalım.

En büyük karı elde etmek için 20 UAH. 4 ürün A ve 4 ürün B üretmek gerekmektedir.

Edebiyat

1. Vitlinsky V.V., Nakonechny S.I., Tereshchenko T.O. Matematiksel programlama. - K.: KNEU, 2001.

2. Ekonomide araştırma işlemleri / Ed. prof. N.Ş. Kremer. - M .: Bankalar ve borsalar, UNITI, 2000.

3. Konyukhovsky P.V. Matematiksel Yöntemler ekonomide yöneylem araştırması: öğretici. Petersburg. - Moskova - Harkov - Minsk, 2005.

4. Kulyan V.R. vb. Matematiksel programlama. – K.: MAUP, 2005.

5. Taha, Hemdi. Yöneylem araştırmasına giriş. - M.: Williams Yayınevi, 2001.

Temel planın uygunluğunun işareti

Bazı temel tasarımları içeren tek yönlü bir tabloda, f-sırasının tüm öğeleri (serbest terim hariç) negatif değilse, bu durumda bu temel tasarım optimaldir. 2.b 0j > (i=1, ..., n m). Bu tabloda yer alan x 0 referans planında, tüm x m+j serbest değişkenlerinin değerleri sıfıra eşittir ve f(x 0) =b 00 . Ancak, x m + j serbest değişkenlerinden biri artırılırsa, eşitlikten (2.5) de görülebileceği gibi, b 0j'nin negatif olmamasından dolayı, f(х)'nin değeri azalmaya başlayacaktır. Bu nedenle, xo'da f(x) işlevi maksimum değerine ulaşır, bu da x 0'ın gerçekten de en uygun referans plan olduğu anlamına gelir.

Bir taban çizgisinden diğerine geçme yeteneği

Yukarıda bahsedildiği gibi, tek yönlü yöntemin özü, aşağıdaki kriteri kanıtlama sürecindedir: bazı temel tasarımları içeren bir tek yönlü tablonun f-sırasında en az bir negatif öğe varsa (serbest terim sayılmaz), bu da şuna karşılık gelir: en az bir pozitif öğeye sahip bir sütun, daha sonra temeli dönüştürerek, amaç fonksiyonunun büyük bir değerine sahip başka bir referans planına gitmek mümkündür.

Bu özelliği kanıtlayalım. İlk temel B'nin yaklaşık x 0 referans planı ile yeni bir temel B 1'e x 1 referans planı ile böyle bir dönüşümü için değişken seçme kurallarını belirleyelim; f fonksiyonunun değeri artar, yani f(x i)>f(x 0). Ardından, tek yönlü tablodan öğeleri yeniden hesaplama kuralına göre, yeni temel planın bileşenlerini bulmamızı sağlayacak yeni bir temele geçiyoruz.

Tabloda olduğunu varsayalım. 2.1 örneğin b 0s<0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) x m+s değişkenine yer açmak için değişkenlerden hangisi önceki temelden çıkarılmalıdır;

2) yeni taban çizgisinde yeni temel değişken x m+s hangi değeri almalıdır?

Sorulan soruları çözmek için, eşitliklerde (2.4) x m+s hariç tüm x m+j'nin sıfıra eşit olduğunu varsayıyoruz. O zamanlar

x ben = b io -b, x m+s'dir (i=l, ..., m)

Bu eşitliklerden, x m + s arttıkça, katsayıların b olduğu temel değişkenlerin x i değerlerinin arttığı görülebilir.<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. x m+s arttıkça bu değişkenlerin değerleri azalacak ve bir an gelecek ki negatif değerler alacaklar ve (2.3) koşulu artık sağlanamayacak. Buna izin verilemez. Bu nedenle, temel değişkenlerin negatif olmama koşulunu ihlal etmeden x m+s'nin hangi sınır değerine yükseltilebileceğini bulalım. Bu amaçla, (2.6) sisteminden b'nin >0 olduğu eşitlikleri yazıyoruz. Bunun i=d,…,k,…,p numaralı eşitliklerle ilgili olduğunu varsayalım:

x d =b yap -- b ds x m+s ,

…………………..

x k =b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

x d , ..., x k , ..., x p temel değişkenleri, x m+s eşitsizlik sistemini sağladığı sürece negatif olmayacak

b do - b ds x m+s >0, x m+s

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

b k0 - b ks x m +s >0 veya x m+s< b ko /b ks

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

b p0 - b ps x m+s >0 x m+s< b po /b ps

yani x m+s için

b io /b kesirlerinin en küçüğünün i = k'ye karşılık gelmesine izin verin, yani

min (b io /b is )= b k0 /b ks .

O zaman x m+s, b k0 /b ks değerini aşmadığı sürece, yani x m+s diyebiliriz. 0, o zaman x k değişkeni mermiye eşit olacaktır: x k \u003d b k0 - b ks b ko /b ks \u003d 0 ve böylece temel dönüştürülecektir B o \u003d (x 1 ; ...; x k ; ...; x m ) serbest gruptan x m+s değişkeninin temel olanlara gittiği ve x k değişkeninin serbest gruptaki x m+s'nin yerini aldığı yeni bir tabana. Bu durumda, diğer tüm serbest değişkenler hala sıfıra eşittir ve geri kalan temel değişkenler hala pozitiftir. Bu nedenle, yeni temeldeki x 1 temel planı B 1 =(x 1 ; ...; x m+s ; ...; x m ) m pozitif bileşene ve m-n sıfır bire sahip olacaktır. x 1 açısından bazı temel değişkenler iki durumda sıfır değer alabilir:

1) x 0 planında sıfıra eşit temel değişkenler olduğunda;

2) b io /b kesirlerinin en küçüğü iki veya daha fazla i sayısına karşılık geldiğinde, bizim durumumuzda yalnızca i = k'ye karşılık gelir.

Tabana dahil edilecek değişken, f-sırasının negatif elemanı tarafından belirlenir. f =b oo - b os x m+s eşitliğinden, b için 0s olduğu açıktır.<0 и фиксированном x m+s >0, f(x)'in değeri b 0s katsayısının mutlak değerine bağlıdır: ne kadar çok |b 0s |, yeni temelde f(x)'in değeri o kadar büyük olur. Ancak bu eşitlik aynı zamanda amaç fonksiyonunun yeni tabandaki değerinin yeni temel değişken x m+s tarafından alınan değere de bağlı olduğunu gösterir. Yalnızca f-sırasının olumsuz öğelerine odaklanarak temele eklenen bir değişken seçeceğiz. Bu nedenle, f satırında birkaç negatif öğe olduğunda, en büyük mutlak değere sahip negatif öğeye karşılık gelen x m + j değişkenini tabana dahil edeceğiz. Temelde yer alan bir değişken için katsayılar sütununa çözümleme denir. Böylece, f-sırasının negatif elemanı tarafından tabana eklenen bir değişkeni seçerek (veya bir çözümleme sütunu seçerek), f fonksiyonunun artmasını sağlarız.

Bazdan çıkarılacak değişkeni belirlemek biraz daha zordur. Bunu yapmak için, serbest üyelerin çözümleme sütununun pozitif öğelerine oranlarını oluştururlar (bu tür ilişkilere tek yönlü denir) ve bunlar arasında, hariç tutulan değişkeni içeren satırı (çözümleme) belirleyen en küçük olanı bulurlar. Temelden çıkarılacak değişkenin seçimi (veya çözümleme dizisinin seçimi) minimum simpleks oranı ile yeni referans tasarımında temel bileşenlerin pozitifliğini garanti eder.

Böylece, özellikte belirtilen koşullar altında, f(x) amaç fonksiyonunun büyük bir değeriyle bir referans plandan diğerine geçmenin gerçekten mümkün olduğunu kanıtladık.

Yeni taban çizgisindeki yeni temel değişken x m+s'nin değerini zaten bildiğimize dikkat edin: b ko /b ks'ye eşittir. Yeni referans planında kalan temel değişkenlerin sayısal değerleri ve buna karşılık gelen f(x) değerine gelince, bunlar ancak x 1 ;..., x m+s temel değişkenler sistemi değiştirildikten sonra bulunabilir. ; ...,x m, x m+1 ,…,x k ,…, xn serbest değişkenlerinin değiştirilmiş sistemi aracılığıyla ifade edilecektir. Bunu yapmak için kurun; problemin koşullarının bir temelden diğerine dönüştürüldüğü kurallar.

Bu denklemdeki x m + s için b ks \u003d 0 katsayısına çözme elemanı denir. Eşitlikte (2.7), yeni temel değişken x m+s, aralarında artık eski temel değişken x k'nin de bulunduğu serbest değişkenler cinsinden ifade edilir. Böylece, x m+s ve x k değişkenlerinin rolleri değişmiştir.

Benzer şekilde, yeni serbest değişkenler kümesi ve diğer temel değişkenler cinsinden ifade ederiz. Bunun için x m + s değerini kalan eşitliklere yerine koyarız (f'yi x 0 ile gösteririz, i= 0 olduğunda eşitlik sisteme girer)

Sistemin yeni bir temele oturtulması işlemine simpleks dönüşüm denir. Bir tek yönlü dönüşüm resmi bir cebirsel işlem olarak kabul edilirse, bu işlemin bir sonucu olarak rollerin belirli bir doğrusal fonksiyonlar sistemine dahil olan iki değişken arasında yeniden dağıtıldığı görülebilir: bir değişken bağımlıdan bağımsıza gider ve diğeri ise tam tersine, bağımsızdan bağımlıya. Böyle bir işlem cebirde Jordan yok etme adımı olarak bilinir.

Temel planın optimalliğinin bir işareti. tek yönlü tablo

Problemleri çözmek için koşullar genellikle simpleks denilen bir tabloya girilir. Kısıtlama sistemine girmeden önce tercih edilen forma yönlendirilir.

kısıtlamalar altında

Bu problem için kısıtlama sistemi tercih edilen bir forma sahiptir. Simpleks tablo oluşturalım.

İlk temel çizgiyi bulma

B ile temel değişkenler kümesini, C ile serbest değişkenler kümesini gösterin. Açıkçası, ne zaman. Değerlere serbest değişkenlerin tahminleri denir.

Temel planın uygunluğunun işareti:

1) Referans plan amaç fonksiyonunu sağlar Minimum değer, eğer bunun için tüm serbest değişken tahminleri pozitif değilse.

2) Serbest değişkenlerin tüm tahminleri negatif değilse, referans plan amaç fonksiyonuna maksimum değeri verir.

Hedef işlev dizisine Z-dizisi veya dizin dizisi denir. Başlangıç ​​referans planı X 0 =(1/2;3/2;0;2;0) ve Z(X 0)=-9/2. Çünkü indeks satırının tüm tahminleri pozitif değilse, X 0 planı optimaldir.

Daha kötü olmayan bir temel plana geçiş. tek yönlü dönüşümler

Sorunu düşünün

İlk temel plan

Tüm tahminler serbest değişkenler ise, o zaman X 0 planı optimaldir. Serbest değişkenlerin pozitif tahminleri varsa, o zaman en büyük?j değerine karşılık gelen sütun çözümleme olarak adlandırılır. Onun sayısını belirleyelim j o ve x jo değerini tabana yerleştirelim.

Çünkü ? jо > 0 ise, tüm serbest değişkenlerin sıfır değerlerini değiştirmeden, x jo değerini artırarak Z fonksiyonu azaltılabilir.

Yeni bir baz plana geçmek için değişkenlerden birinin bazdan çıkarılması gerekir.

xj o'nun değeri, x i temel değişkenlerinin değerlerinden hiçbiri negatif olmayacak şekilde artırılmalıdır. Şunlar.

İki durum mümkündür.

1) j o çözümleme sütununun tüm öğeleri pozitif değildir, yani bir ijo? 0. Min (max) için bir problem çözerken, indeks satırında serbest değişkenlerin pozitif (negatif) tahminleri varsa ve xj o değişkeni sütununda tek bir pozitif öğe yoksa, o zaman amaç fonksiyonu değildir. sorunun kabul edilebilir planları kümesinde aşağıdan (yukarıdan) sınırlanmıştır.

2) Çözüm sütununun öğeleri arasında pozitif olanlar varsa, eşitsizlik sistemi ihlal edilene kadar x jo artırılabilir:

buradan anlıyoruz

İzin vermek verilen ifade i=i o olduğunda gerçekleştirilir, o zaman

Birkaç i için koşul sağlanıyorsa, herhangi bir i o seçilebilir. i o dizisi izin verici olarak adlandırılır, eleman izin vericidir.

Amaç fonksiyonunun yeni değeri:

Dönüşümler sonucunda amaç fonksiyonu azalmıştır. Şimdi yeni temel değişken, serbest olanlar cinsinden ifade edilmeli ve kısıtlamalar sistemi ve amaç fonksiyonunda değiştirilmelidir. Ayrıca, eski temel değişken serbest hale gelir.

Simpleks dönüştürme kuralları:

1) Tek yönlü tablonun dizin satırında en büyük pozitif (veya negatif) öğeyi bulun. Bu öğeye karşılık gelen sütun izinlidir.

2) Denklemin serbest terimlerinin çözme sütununun pozitif elemanlarına oranını hesaplayın. Bu ilişki simpleks ilişki denir. Çözünürlük dizesiyle eşleşen en küçük tek yönlü oranı bulun.

3) Etkinleştirme satırı ile etkinleştirme sütununun kesiştiği noktada bir etkinleştirme elemanı bulunur. Aynı değere sahip birkaç tek yönlü ilişki varsa, bunlardan herhangi birini seçin.

4) İzin verilen sütuna ve satıra karşılık gelen bilinmeyen öğeler değiştirilir.

5) Bir sonraki tabloya gidin. Yeni tablo izin satırının öğeleri şuna eşit olacaktır:

6) Etkinleştirme sütununun öğeleri sıfırdır, hariç x jo - temel değer.

7) Diğer tüm öğeler formüllerle bulunur.

Kaynak tablodaki öğeleri bulmak için, köşeleri hesaplama için gereken öğeler olan bir dikdörtgen seçilir. Yeni tablonun çözülen ve istenilen elemanını içeren köşegene ana, diğerine yan taraf denir. Ana köşegenin köşe elemanlarının çarpımından, ikincil köşegenin köşe elemanlarının çarpımı çıkarılır ve elde edilen sayı, çözümleme elemanına bölünür. Bu dikdörtgen kuralıdır.

8) dizin satırının öğelerini hesaplayın

Hesaplamaları kontrol etmek için hesaplayabilirsiniz

9) algoritma, optimallik koşuluna ulaşılana kadar devam eder.

a) Destek planı, kendisi için serbest değişkenlerin tüm tahminleri pozitif değilse, amaç fonksiyonuna minimum değeri verir.

b) Serbest değişkenlerin tüm tahminleri negatif değilse, referans tasarım amaç fonksiyonuna maksimum değeri verir.

Örnek: Simplex yöntemini kullanarak bir doğrusal programlama problemini çözün

En uygun plan X (7;0;0;42;2) ve Z(x)=72'dir.

Yapay temelli bir problem örneği.

Sorunu kanonik forma getirelim:

2. ve 3. denklemlere yapay değişkenler ekliyoruz:

Bir tek yönlü tablo oluşturalım:

Vektör formundaki kanonik doğrusal programlama problemi şu şekildedir:

Kabul edilebilir çözümlerin pozitif koordinatlarına, koşul vektörleri atanır. Bu vektör sistemleri bağımlıdır, çünkü içlerinde bulunan vektörlerin sayısı vektörlerin boyutundan daha fazladır.

Sistemin temel çözümü temel olmayan değişkenlerin sıfır değerlerine sahip olduğu bir bölüm olarak adlandırılır. Herhangi bir denklem sisteminin sonlu sayıda temel çözümü vardır, burada bilinmeyenlerin sayısı koşul vektörleri sisteminin sıralamasıdır. Koordinatları negatif olmama koşulunu sağlayan temel referanstır.

Referans çözümü Pozitif koordinatlara karşılık gelen koşul vektörlerinin olduğu doğrusal programlama problemi kabul edilebilir olarak adlandırılır. , lineer bağımsızdır.

Sıfır olmayan referans koordinatlarının sayısı, Koşul Vektörleri Sisteminin sırasını (yani, kısıtlamalar sisteminin doğrusal olarak bağımsız denklemlerinin sayısını) aşamaz.

Sıfır olmayan koordinatların sayısı ise Referans çözümü eşittir, o zaman böyle bir çözüm denir dejenere olmayan , aksi takdirde, referans çözümün sıfır olmayan koordinatlarının sayısı 'den küçükse, böyle bir çözüme denir. dejenere .

Referans çözümün temeli referans çözümün sıfır olmayan koordinatlarına karşılık gelen vektörleri içeren problemin koşullarının vektör sisteminin temeli olarak adlandırılır.

teorem . Herhangi bir referans çözüm, uygulanabilir çözümler alanının bir köşe noktasıdır. .

teorem . Uygulanabilir çözümler bölgesinin herhangi bir köşe noktası bir referans çözümdür. .

Örnek.

Problemi çözmek için grafik yöntem doğrusal optimizasyon Aşağıdakiler için bir üretim planlama problemi örneğini ele alalım:
= 2.

İşletme A ve B olmak üzere iki tip ürün üretmektedir. Ürünlerin üretimi için sırasıyla 600, 480 ve 240 adet olmak üzere C, D ve E olmak üzere üç çeşit hammaddeye sahiptir. Her türün üretim birimi başına kaynak tüketim oranları bilinmekte ve Tablo'da sunulmaktadır. 14.1

Çözüm:

A ürününün satışından elde edilen kar 40 milyon ruble ve B ürünü - 50 milyon ruble. A ve B ürünlerinin maksimum kar sağlayan üretim hacimlerini bulmak gerekmektedir.

Sırasıyla A ve B ürünlerinin üretim hacimlerini - gösterdiğimiz problemin matematiksel bir modelini oluşturalım.

O zaman işletmenin A ve B ürünlerinin satışından elde ettiği kâr şu olacaktır:

Kaynak sınırları şöyle görünecektir:

Doğal olarak, üretim hacimleri negatif olmamalıdır .

Formüle edilmiş problemin çözümünü geometrik bir yorum kullanarak bulacağız. İlk olarak, eşitsizlikler üzerindeki kısıtlama sistemini denklem biçiminde yazdığımız ve numaralandırdığımız çözüm poligonunu tanımlıyoruz:

Yazılan denklemlerin her biri, 4. ve 5. çizgiler koordinat eksenleri olmak üzere düzlemde birer çizgidir.

İlk düz çizgiyi oluşturmak için, koordinat eksenleriyle kesişme noktalarını buluruz: , ve ne zaman . Daha sonra, çizginin hangi tarafının birinci eşitsizliğe karşılık gelen yarım düzlem olacağıyla ilgileniyoruz. İstenen yarım düzlemi belirlemek için bir nokta alırız ve koordinatlarını eşitsizliğe koyarak tatmin olduğunu görürüz. Nokta ilk düz çizginin solunda yer aldığından, yarı düzlem de düz çizginin solunda olacaktır. . Şek. 14.1 İlk düz çizgiye göre yarım düzlemin konumu oklarla işaretlenmiştir.

2. ve 3. doğrular benzer şekilde kurulur ve 2. ve 3. eşitsizliklere karşılık gelen yarım düzlemler bulunur. Kısıtlamaları Karşılayan Noktalar , birinci kadrandadır.

Tüm kısıtlamaları aynı anda karşılayan noktalar kümesi, kısıtlama sisteminin ODS'sidir. Grafikteki böyle bir alan (Şekil 14.1) bir çokgendir.

Çözüm poligonunun herhangi bir noktası, problemin kısıtlama sistemini karşılar ve bu nedenle çözümüdür. Bu, bu doğrusal optimizasyon probleminin birçok uygun çözümü olduğunu, yani çok değişkenli olduğunu göstermektedir. Maksimum kar sağlayan bir çözüm bulmamız gerekiyor.

Bu noktayı bulmak için fonksiyonu sıfıra eşitliyoruz ve ona karşılık gelen doğruyu oluşturuyoruz. Doğrudan Fonksiyon Gradyan Vektörü koordinatları var .

Pirinç. 14.1

Vektörü grafik üzerinde çizelim ve fonksiyonun doğrusunu Şekil 2'deki vektöre dik olarak çizelim. 14.1. Direkt fonksiyonu vektör yönünde kendisine paralel hareket ettirirsek, şunu görürüz: son nokta fonksiyon çizgisinin kesiştiği çözüm poligonunun köşe noktası B'dir. Dolayısıyla B noktasında fonksiyon maksimum değerine ulaşır. Doğruları belirli bir noktada kesişen bir denklem sistemini çözerek B noktasının koordinatlarını buluyoruz.

Bu sistemi çözerek, bunu anlıyoruz.

Bu nedenle, şirket bulunan hacimlerde ürün üretirse, maksimum karı şuna eşit alacaktır:

(milyon ruble).

Bir doğrusal programlama problemini grafik yöntemle çözmek için algoritma aşağıdaki gibidir:

1. Kabul edilebilir çözümler alanı oluşturulur;

2. Uygulama noktası orijinde olacak şekilde seviye çizgisine normal bir vektör oluşturulur;

3. Orijinden geçen seviye çizgilerinden biri normal vektöre dik olarak çizilir;

4. Seviye çizgisi, referans çizgisinin konumuna hareket eder. Bu düz çizgi üzerinde, fonksiyonun bir maksimumu veya minimumu olacaktır.

Uygulanabilir çözümler alanının türüne ve amaç fonksiyonuna bağlı olarak, problemin tek bir çözümü olabilir, sonsuz sayıda çözümü olabilir veya optimal çözümü olmayabilir.

Şek. 14.3, doğrudan fonksiyonun ODR'ye ait AB segmentine paralel olduğu durumu gösterir. Fonksiyonun maksimumuna A noktasında ve B noktasında ve sonuç olarak AB doğru parçasının herhangi bir noktasında ulaşılır, çünkü bu noktalar A ve B köşe noktalarının doğrusal bir kombinasyonu olarak ifade edilebilir.

Lineer programlama problemini çözmek için simpleks yöntemin temel kavramları.

Arasında evrensel yöntemler doğrusal programlama çözümleri, en yaygın olanı Amerikalı bilim adamı J. Danzig tarafından geliştirilen simplex yöntemidir (veya simplex yöntemidir). Bu yöntemin özü, ilk başta tüm kısıtlamaları karşılayan geçerli bir varyantın elde edilmesinde yatmaktadır, ancak mutlaka optimal olan (sözde ilk referans çözüm) değildir; optimallik ardışık iyileştirme ile elde edilir Orijinal versiyon başına belirli sayı aşamalar (yinelemeler). Başlangıç ​​referans çözümünün bulunması ve bir sonraki referans çözüme geçiş, orijinal doğrusal programlama probleminin önceden olması gereken, kanonik formdaki bir doğrusal denklem sistemi için yukarıda ele alınan Jordan-Gauss yönteminin uygulanması temelinde gerçekleştirilir. -yazılı; bir referans çözümden diğerine geçiş yönü, bu durumda orijinal problemin optimallik kriteri (amaç fonksiyonu) temelinde seçilir.

tek yönlü yöntem bir doğrusal programlama probleminin aşağıdaki özelliklerine dayanmaktadır:

· Küresel olandan farklı bir yerel ekstremum yoktur. Başka bir deyişle, bir uç nokta varsa, o zaman benzersizdir.

· Bir doğrusal programlama probleminin tüm planlarının kümesi dışbükeydir.

· LLP amaç fonksiyonu, karar polihedronunun köşe noktasında (tepe noktasında) maksimum (minimum) değerine ulaşır. Amaç fonksiyonu birden fazla köşe noktasında optimal değerini alıyorsa, bu noktaların dışbükey doğrusal birleşimi olan herhangi bir noktada aynı değere ulaşır.

· Çözüm polihedronunun her bir köşe noktası, LLP temel planına karşılık gelir.

Simplex yönteminin iki çeşidini ele alalım: doğal temelli simpleks yöntemi ve yapay temelli (veya M yöntemi) simpleks yöntemi.

Doğal temelli simpleks yöntemi

Bu yöntemi uygulamak için, doğrusal programlama problemi kanonik biçimde formüle edilmeli ve denklem sisteminin matrisi, boyut alt matrisini içermelidir. Bu durumda, ilk destek planı (olumsuz olmayan temel çözüm) açıktır.

Kesinlik için, varsayalım ki ilk T Sistem matris vektörleri kimlik matrisi. O zaman ilk temel plan açıktır: .

Referans planın optimallik kontrolü, optimallik kriteri kullanılarak gerçekleştirilir, başka bir referans plana geçiş, Jordan-Gauss dönüşümleri ve optimallik kriteri kullanılarak gerçekleştirilir.

Ortaya çıkan temel plan, optimallik açısından tekrar kontrol edilir ve bu böyle devam eder.Süreç, sınırlı sayıda adımla sona erer ve devam eder. son adım ya problemin çözülemezliği ortaya çıkar (sonlu optimum yoktur) ya da optimal destek planı ve buna karşılık gelen amaç fonksiyonunun optimal değeri elde edilir.

Optimalliğin işareti aşağıdaki iki teoremde yatmaktadır.

teorem 1.Temelde yer almayan bazı vektörler için aşağıdaki koşul sağlanırsa:

, nerede ,

Ardından, amaç fonksiyonunun değerinin orijinalinden daha büyük olacağı yeni bir referans plan elde edebilirsiniz; iki durum olabilir:

1. Tabana girilecek vektörün tüm koordinatları pozitif değilse doğrusal programlama probleminin çözümü yoktur;

2. Temele girilecek vektörün en az bir pozitif koordinatı varsa, yeni bir temel plan elde edilebilir.

Teorem 2.Koşul tüm vektörler için sağlanıyorsa , o zaman ortaya çıkan plan optimaldir.

Optimallik işaretine dayanarak, vektör, tek yönlü farkın minimum negatif değerini veren temele dahil edilir: .

Referans plan değerlerinin negatif olmama koşulunu yerine getirmek için vektör tabandan türetilmiştir. G, Bu minimum pozitif oranı verir:

; , .

Astar aranan kılavuz , Kolon ve eleman
— rehberler (ikincisi de denir müsamahakâr eleman).

Yeni tek yönlü tablodaki kılavuz çizgiye karşılık gelen giriş satırının öğeleri aşağıdaki formüllerle hesaplanır:

Ve diğerlerinin unsurları inci Satırlar aşağıdaki formüllere göre yeniden hesaplanır:

,,

Yeni temel planın temel değişkenlerinin değerleri ("plan" sütununun göstergeleri) aşağıdaki formüllerle hesaplanır:

İçin ; , için .

Eğer bir en küçük değer birkaç temel vektör için elde edilirse, döngü olasılığını (temelin tekrarı) ortadan kaldırmak için aşağıdaki yöntem uygulanabilir.

Bölümler, aynı minimum değeri veren satırların tüm öğelerinin kılavuz öğelerine bölünmesiyle elde edilen hesaplanır. Ortaya çıkan bölümler, hem sıfır hem de negatif değerler dikkate alınarak soldan sağa sütun sütun eşleştirilir. Tarama sırasında, büyük oranlı satırlar atılır ve daha önce küçük bölümün bulunduğu satıra karşılık gelen tabandan bir vektör türetilir.

Doğrusal formu en aza indirmek için tek yönlü yöntemin yukarıdaki prosedürünü kullanmak için, işlevin maksimumu aranmalıdır. , ardından zıt işaretli elde edilen maksimum değeri alın. Bu, orijinal doğrusal programlama probleminin istenen minimum değeri olacaktır.

Yapay temelli tek yönlü yöntem (M yöntemi)

Kanonik formda yazılmış orijinal doğrusal programlama probleminin başlangıç ​​destek planının bulunmasının zor olduğu durumlarda yapay temelli simpleks yöntem kullanılmaktadır.

M-yöntem, tek yönlü yöntemin kurallarının sözde yönteme uygulanmasından oluşur. M-sorunu. Orijinal doğrusal programlama probleminin kanonik formundaki denklem sisteminin sol tarafına bu tür yapay birim vektörler ile karşılık gelen negatif olmayan yapay değişkenler eklenerek orijinalden elde edilir, böylece yeni elde edilen matris bir sistem içerir. birim lineer bağımsız vektörler. AT doğrusal biçim Maksimizasyonu durumunda, toplam, sayının ürünü olan orijinal probleme eklenir ( -M ) yapay değişkenlerin toplamı ile, burada M yeterince büyük bir pozitif sayıdır.

Ortaya çıkan problemde, başlangıçtaki temel plan açıktır. Simplex yöntemini bu probleme uygularken, tahminler artık sayıya bağlı olacaktır. M . Puanları karşılaştırmak için şunu unutmayın M - yeterince büyük bir pozitif sayı, bu nedenle yapay değişkenler her şeyden önce temelden türetilecektir.

karar sürecinde M- Yapay vektörlerin simpleks tablosunda problemler tabandan çıktıkça üzeri çizilmelidir. Tüm yapay vektörler temelin dışındaysa, o zaman orijinal sorunu elde ederiz. Eğer optimal çözüm M- Görev yapay vektörler içeriyor veya M- Sorun çözülemez, o zaman asıl sorun da çözülemez.

Dönüşümler yoluyla, oluşturan girdi değişkenlerinin sayısı yapay temel, bire düşürülebilir.

Simplex yöntemini doğal bir temelde uygulamak için, QZLP'nin mxm boyutunda bir birim alt matrisi içermesi gerekir - bu durumda, ilk destek tasarımı (QZLP kısıtlama sisteminin negatif olmayan temel çözümü) açıktır.
Kesinlik için, denklem sisteminin matrisinin ilk m vektörünün birim matrisi oluşturduğunu varsayıyoruz. O zaman başlangıçtaki temel plan açıktır - (b 1 , b 2 ,…, b m ,0,…,0).
Referans planın optimalliği için kontrol, optimallik kriteri kullanılarak gerçekleştirilir, başka bir referans plana geçiş, matematiksel optimallik kriteri kullanılarak Jordan-Gauss dönüşümleri kullanılarak gerçekleştirilir. Ortaya çıkan temel plan, optimallik açısından yeniden kontrol edilir ve bu böyle devam eder. Süreç sınırlı sayıda adımda sona erer ve son adımda ya problemin çözülemezliği ortaya çıkar (sonlu bir optimum yoktur) ya da bir optimal referans planı ve buna karşılık gelen sayısal filtrenin optimal değeri elde edilir.
Optimallik için matematiksel kriter aşağıdaki iki teoremden oluşur:
1. Tüm А 1 , А 2 ,…, А vektörleri için koşul
nerede ,
o zaman ortaya çıkan taban çizgisi optimaldir.
2. Temelde yer almayan bazı vektörler için koşul , o zaman dijital filtrenin değerinin orijinalinden daha büyük olacağı yeni bir referans planı alabilirsiniz, ancak iki durum olabilir:
- tabana girilecek vektörün tüm bileşenleri pozitif değilse, LLP'nin çözümü yoktur (nihai optimum yoktur);
- Temele girilecek vektörün en az bir pozitif bileşeni varsa, yeni bir temel plan elde edilebilir.
Optimallik işaretine dayanarak, tek yönlü farkın minimum negatif değerini veren A k vektörü tabana dahil edilir:
Referans plan değerlerinin negatif olmama koşulunu yerine getirmek için, minimum pozitif tahmini oranı veren bazdan Ar vektörü türetilir.

A r satırına kılavuz, A k sütununa ve a r k öğesine kılavuz denir.
Yeni tek yönlü tablodaki kılavuz satırının öğeleri aşağıdaki formüllerle hesaplanır:
a i'inci elemanlarçizgiler - formüllere göre:
Yeni taban çizgisinin değerleri, aşağıdaki formüller kullanılarak hesaplanır:
ben = r için;
Çözüm süreci, optimal bir plan elde edilene kadar veya sayısal filtrenin sınırsızlığı sağlanana kadar sürdürülür. Optimal tasarımın simpleks farkları (tahminleri) arasında yalnızca temel vektörlere karşılık gelen tahminler sıfır ise, bu, optimal tasarımın benzersizliğini gösterir. Sıfır tahmini, dahil edilmeyen bir vektöre karşılık geliyorsa, genel durumda bu, optimal planın benzersiz olmadığı anlamına gelir.
Not. En aza indirmek için yukarıdaki prosedürü kullanmak için doğrusal fonksiyon f (x 1 ,x 2 ,…, x n) maksimumu aramalı - f (x 1 ,x 2 ,…, x n), ardından zıt işaretli maksimumu almalıdır. En uygun çözüm Aynı.
Örnek. Modele göre çözüm alın:
Bu, doğrusal programlamanın bir problemidir (modelidir), x 3 ve x4 ek değişkenlerini tanıtarak onu kanonik forma getiriyoruz:
QZLP, gerekli sayıda tek sütuna sahiptir, örn. bariz bir başlangıç ​​referans planına sahiptir (0,0,300,150). Çözüm, tek yönlü tablolarda hesaplamaların yürütülmesi ile doğal bir temelde basit yöntemle gerçekleştirilir:

j. optimum değerler değişkenler şunlardır: x1*=75, x2* =75 (temel değişkenler), x3* =0, x4* =0 (ek değişkenler). Maksimum değer amaç fonksiyonu 375'tir.
Dolayısıyla, yukarıda ele alınan sınırlı kaynakların optimal kullanımı probleminde, optimal üretim programı 75 birimin piyasaya sürülmesinden oluşur. birinci tip ürünler ve 75 adet. ikinci tür ürünler. Bu program, maksimum satış geliri ile ilişkilidir bitmiş ürün- 375 Dolar

Sayı			AT	2	3	0	0
basit-	temel		plan					Q
masalar
	A3	0	300	1	3	1	0	100
0	A4	0	150	1	1	0	1	150
		f(x)	0	-2	-3	0	0
	A2	3	100	1/3	1	1/3	0	300
ben	A4	0	50	2/3