Nesne

3.5: Doğrusal Programlama Uygulamaları


Önceki bölümde, birçok değişkenli doğrusal programlama problemlerini çözmek için bir prosedür olan Simplex yöntemine baktık. Bu bölümün geri kalanında, amaç fonksiyonunu ve kısıtları kurmaya ve çözümü yorumlamaya odaklanacağız ve çözümün ayrıntılarını atlayacağız.

Örnek (PageIndex{1})

Bir yemek şirketi, bir iş toplantısı için öğle yemeği hazırlayacaktır. Jambonlu sandviçler, hafif jambonlu sandviçler ve vejeteryan sandviçler sunacak. Jambonlu sandviçte 1 porsiyon sebze, 4 dilim jambon, 1 dilim peynir ve 2 dilim ekmek bulunur. Hafif bir jambonlu sandviçte 2 porsiyon sebze, 2 dilim jambon, 1 dilim peynir ve 2 dilim ekmek bulunur. Bir vejetaryen sandviçte 3 porsiyon sebze, 2 dilim peynir bulunur. ve 2 dilim ekmek. Her biri 40 dilim olan toplam 10 torba jambon mevcuttur; Her biri 14 dilim olan 18 somun ekmek mevcuttur; 200 porsiyon sebze ve her biri 60 dilimli 15 torba peynir mevcuttur. Kaynaklar göz önüne alındığında, amaç sandviç sayısını maksimize etmekse, her bir sandviçten kaç tane üretilebilir?

Çözüm

Sandviç sayısını en üst düzeye çıkarmak istiyoruz, bu nedenle:
(x=) jambonlu sandviç sayısı
(y=) hafif jambonlu sandviç sayısı
(z=) vejetaryen sandviç sayısı

Toplam sandviç sayısı şu şekilde verilir: (quad S=x+y+z)

Kısıtlamalar, mevcut bileşenlerin toplam miktarı dikkate alınarak verilecektir. Yani şirketin sınırlı miktarda jambon, sebze, peynir ve ekmek bulunuyor.

Şirketin toplamda (10(40)=400) dilim jambon, (18(14)=252) dilim ekmeği var.
200 porsiyon sebze ve (15(60)=900) dilim peynir mevcuttur. en fazla,
şirket yukarıdaki tutarları kullanabilir.

Jambon kullanan iki sandviç vardır - ilki 4 dilim jambon gerektirir ve ikincisi sandviç başına sadece 2 dilim gerektirir ve toplam dilim jambon sayısı 400'ü geçemez

[4 x+2 y leq 400 umarasız]

Her sandviç 2 dilim ekmek gerektirir, bu nedenle:

[2 x+2 y+2 z leq 252 umber]

Jambonlu sandviçlerde sırasıyla 1 ve 2 porsiyon sebze bulunur ve vejeteryan sandviçte 3 porsiyon sebze bulunur. Böyle,

[1x + 2y + 3z leq 200 umber]

Her iki jambonlu sandviç de bir dilim peynir gerektirir ve vejeteryan sandviç iki dilim peynir gerektirir, yani,

[1x + 1y + 2z leq 900 umber]

Son kurulumumuz:

Büyüt: (S = x + y + z)

tabi:

[ egin{align*} 4x + 2y & leq 400 2x + 2y + 2z &leq 252 2x + 2y + 2z &leq 252end{align*} onumber]

Bunu çözerek elde ederiz

En uygun çözüm:

[S = 126; dörtlü x = 100, dörtlü y = 0, dörtlü z = 26 osayı]

Yapılan toplam sandviç sayısını en üst düzeye çıkarmak için 100 jambonlu sandviç, 26 vejetaryen sandviç ve 0 hafif jambonlu sandviç yapılması gerektiğini bulduk.

Bunun, ilk giden ekmeğin tamamını etkili bir şekilde kullanacağına dikkat edin.

Örnek (PageIndex{2})

Bir fabrika A, B ve C olmak üzere üç ürün üretmektedir. Her ürün, Makine I ve Makine II olmak üzere iki makinenin kullanılmasını gerektirir. Makine I ve Makine II'de aylık toplam kullanılabilir saat sırasıyla 180 ve 300'dür. Her ürün için zaman gereksinimleri ve birim başına kar aşağıda listelenmiştir.

A

B

C

Makine I

1

2

2

Makine II

2

2

4

Kâr

20

30

40

Karı maksimize etmek için her bir üründen kaç adet üretilmelidir ve maksimum kar nedir?

Çözüm

Her zamanki gibi, değişkenlerimizi tanımlayarak başlıyoruz:
(A=) üretilen A ürününün birim sayısı

(B=) üretilen B ürününün birim sayısı

(C=) üretilen B ürününün birim sayısı

Kârı maksimize etmeye çalışıyoruz. A maddesinin (A) birimlerinin üretilmesi (20 A) ile sonuçlanacak, (B) (B) birimlerinin üretilmesi (30 B) ve (C) ile sonuçlanacaktır. ) (C) öğesinin birimleri, amaç fonksiyonumuzu vererek (40 C) kâr edecektir:

[P=20 A+30 B+40 C umara]

Daha sonra, kısıtlamaları belirlemek için her makinede mevcut olan zamanı değerlendiririz. üreten A A öğesinin birimleri 1 gerektirecektirA Makine 1'deki saat, üretim B B öğesinin birimleri 2 gerektirecektirB saat ve üretim C C öğesinin birimleri 2 gerektirecektirC saatler. Bunların birlikte mevcut 180 saati aşmaması gerekir. Bu kısıtlamaya yol açar:

[1A + 2B + 2C leq 180 umber]

Makine 2'deki saatleri kullanarak benzer bir kısıtlama oluşturabiliriz:

[2A + 2B + 4C leq 300 umber]

Son kurulumumuz:

Büyüt (P = 20A + 30B + 40C)

tabi:

[egin{align*} 1A + 2B + 2C &leq 180 2A + 2B + 4C &leq 300 A geq 0, quad B geq 0, &; C geq 0 end{align*} umber]

Bunu çözmek:

En uygun çözüm:

[P = 3300; A = 120, B = 30, C = 0 umber]

120 birim (A), 30 birim (B) ve hiç bir birim (C) üreterek karı 3300$'da maksimize edeceğiz.

Maksimizasyon problemlerine ek olarak, lineer programlama da minimizasyon problemlerini çözmek için kullanılabilir. Elle yapıldığında bunlar, son bölümde gösterilen Simplex yönteminde bir değişiklik gerektirecektir, ancak bu problemler çoğu teknolojik yöntemle çözülebilir.

Örnek (PageIndex{3})

Bir şirket yemek değiştirme çubuğu oluşturuyor. Fıstık ezmesi, yulaf ve kuru kızılcıkları birincil bileşenler olarak dahil etmeyi planlıyorlar. Her birinin 10 gramlık besin içeriği, her bir bileşenin sent cinsinden maliyetiyle birlikte aşağıda listelenmiştir. Her bir bileşenden en az 15 g, en az 10 g protein ve en fazla 14 g yağ içeren bir bar üretmenin maliyetini en aza indirmek için kullanmaları gereken her bir bileşenin miktarını bulun.

Fıstık Ezmesi, 10g

Yulaf, 10g

kızılcık, 10 gr

Protein (gram)

2.5

1.7

0

Yağ (gram)

5

0.7

0.1

Maliyet (sent)

6

1

2

Çözüm

Değişkenleri tanıtarak başlıyoruz:

(p ​​=) 10 gr fıstık ezmesi porsiyon sayısı

(a =) 10g porsiyon yulaf sayısı

(c =) 10 gr kızılcık porsiyonu sayısı

Çubuğun sent cinsinden üretilmesinin toplam maliyeti (C), (C=6 p+1 a+2 c) olacaktır.


İlk kısıtlamalarımız, her bir bileşenin (15 mathrm{~g}) gereksiniminden gelir, yani porsiyon başına (1.5) porsiyon (1.5 porsiyon (10 mathrm{~g}) ( =15 mathrm{~g}) ). Bu kısıtlamaları oluşturmak (p geq 1.5, a geq 1.5, c geq 1.5)

Daha sonra besin bileşenlerine bakıyoruz. Protein için, (p) porsiyon fıstık ezmesi (2,5 p) gram protein içerecektir. Benzer şekilde, (a) porsiyon yulaf (1.7 a) gram protein içerecek ve (c) porsiyon kızılcık (0 c) gram protein içerecektir. Birlikte, bunların en az 10 gram olması gerekir, bu da (2,5 p+1,7 a+0 c geq 10) kısıtını verir.

Yağ için benzer bir kısıtlama oluşturabiliriz, bu durumda yağın en fazla (14 mathrm{~g}) olmasını istediğimizi not ederiz:
(5 p+0.7 a+0.1 c leq 14)

Artık tam problemimize sahip olabiliriz:

Küçültmek:

[C=6 p+1 a+2 c umara]
tabi:
[egin{align*} 2,5 p+1.7 a+0 c &geq 10 5 p+0.7 a+0.1 c &leq 14 p geq 1.5, a geq 1.5, c &geq 1.5end{hiza*}]

Teknolojiye dönerek bir çözüm buluyoruz:

En uygun çözüm:

[C=15.6765; quad p=1,5, quad a=3.67647, quad c=1,5 umarasız]

Bu sonucu yorumlayarak, 15 gram fıstık ezmesi, (36.8) gram yulaf ve 15 gram kuru kızılcık kullanarak çubuğu üretmenin minimum maliyeti yaklaşık (15,7) sent olacaktır.

Koşullarımızı doğrulayarak, tarifimizin her bir malzemeden en az (1.5) porsiyon içerdiğini görebiliriz. Protein içeriği (2.5(1.5)+1,7(3.68)+0(1.5) yaklaşık 10) gram olacaktır.
Yağ içeriği (5(1.5)+0.7(3.68)+0.1(1.5) yaklaşık 10.2) gram olacaktır.

Alıştırma (PageIndex{1})

Bir fabrika (A, B) ve (C) olmak üzere üç ürün üretir. Her ürün, toplam mevcut süre ve kâr ile birlikte aşağıda gösterilen belirli sayıda üretim, montaj ve bitirme süresi gerektirir. Kârı en üst düzeye çıkarmak için üretim seviyelerini bulun.

A

B

C

Toplam Saat

Üretme

4

5

2

300

toplantı

7

4

1

250

Bitiricilik

4

5

1

200

Kâr

175

130

40

Cevap

Sorun kurulumumuz:

Büyüt :

[P = 175A + 130B + 40C umarasız]

tabi:

[egin{align*} 4A + 5B + 2C &leq 300 7A + 4B + 1C &leq 250 4A + 5B + 1C &leq 200 end{align*} ]

Bunu çözerek çözümü elde ederiz:

En uygun çözüm:

[P = 7907.89; A = 18.4211, B = 5.26316, C = 100 umber ]

Yuvarlama, (A = 18), (B = 5) ve (C = 100) üretmek, 297 saat imalat, 246 saat montaj ve 197 saat son işlem kullanacak ve 7800$ kar elde edecektir. . Yakındaki birkaç tamsayı çözümüyle uğraşabiliriz:

(A = 18, B = 5) ve (C = 101): 7840$ kar

(A = 18, B = 6) ve (C = 98): 7850$ kar

(A = 19, B = 4) ve (C = 101): Kar 7885$

Gördüğünüz gibi, optimal tamsayı çözümleri bulmak daha zor bir problemdir.

Bazı durumlarda, gerçek uygulamanın gereksinimlerini karşılamaya devam ederken bir doğrusal programlama probleminin doğru biçimini korumak için kısıtlamalarımızı nasıl yarattığımız konusunda akıllı olmamız gerekir.

Örnek (PageIndex{4})

Bir dağıtım şirketinin ürünlerini iki deposundan üç perakendeciye göndermesi gerekir. A Deposunda 1000 ürün, B Deposunda ise 1200 ürün bulunmaktadır. Perakendeci 1'in 700 ürüne ihtiyacı var, Bayi 2'nin 500 ürüne ihtiyacı var ve Bayi 3'ün 600 ürüne ihtiyacı var Bir ürünü her bir depodan her bir perakendeciye göndermenin maliyeti aşağıda gösterilmiştir. Nakliye maliyetlerini en aza indirmek için şirketin her depodan her perakendeciye göndermesi gereken ürün sayısını bulun.

perakendeci 1

Perakendeci 2

perakendeci 3

Depo A

3

5

6

Depo B

4

7

5

Çözüm

Bu problemi başlatmak için önce değişkenlerimizi tanımlamamız gerekiyor. Altı farklı rota olduğu için altı değişken tanımlamamız gerekecek:

(A_1=) Depo A'dan Bayi 1'e sevk edilen ürün sayısı

(B_1=) Depo B'den Bayi 1'e sevk edilen ürün sayısı

(A_2=) Depo A'dan Bayi 2'ye sevk edilen ürün sayısı

(B_2, A_3) ve (B_3) değişkenlerini benzer şekilde tanımlayabiliriz.

Amaç fonksiyonumuz toplam nakliye maliyetidir. (A_1) öğelerinin Depo (A)'dan Perakendeci 1'e nakliyesi öğe başına 3 ABD dolarına mal olur, bu nedenle toplam maliyet (3A_1). Aynısını diğer değişkenler için yapmak toplam maliyet denklemimizi verir:

[C = 3{A_1} + 4{B_1} + 5{A_2} + 7{B_2} + 8{A_3} + 5{B_3} onumber]

Depo (A)'nın stoğunda 1000 ürün olduğunu biliyoruz, bu nedenle Depo (A)'dan gönderilen toplam ürün sayısının 1000'den fazla olmaması gerekiyor. Aynı şekilde Depo B 1200'den fazla ürün gönderemez. Bunlar kısıtlamaları verir:

[egin{align*}A_1 + A_2 + A_3 leq 1000 {B_1} + {B_2} + {B_3} leq 1200end{align*}]

Perakendeci 1'in 700 ürüne ihtiyacı var. Teknik olarak katı bir eşitlik olsa da, perakendeci 1'e gelen toplam ürün sayısının en az 700 ürün olması gerektiğini belirten bir eşitsizlik olarak kurabiliriz. Maliyeti en aza indirdiğimiz için, perakendeciye 700'den fazla ürün göndermemize imkan yok. Diğer üç perakendeci için bu kısıtlamayı ve benzerlerini ayarlama:

[egin{align*} {A_1} + {B_1} geq 700 {A_2} + {B_2} geq 500 {A_3} + {B_3} geq 600 end{align*}]

Son problem kurulumumuz:

Küçültmek:

[C = 3{A_1} + 4{B_1} + 5{A_2} + 7{B_2} + 8{A_3} + 5{B_3} onumber]

tabi:

[ egin{align*}{A_1} + {A_2} + {A_3} leq 1000 {B_1} + {B_2} + {B_3} leq 1200 {A_1} + {B_1} geq 700 {A_2} + {B_2} geq 500 {A_3} + {B_3} geq 600 {A_1} geq 0,{B_1} geq 0,{A_2} geq 0,{B_2} geq 0,{A_3} geq 0,{B_3} geq 0end{align*}]

Bunu çözerek, çözümü elde ederiz,

En uygun çözüm:

[C = 7800; A_1 = 500, B_1 = 200, A_2 = 500, B_2 = 0, A_3 = 0, B_3 = 600 umber]

Bu Bölümün Önemli Konuları

Bir uygulama için amaç ve kısıt denklemlerini kurma

Doğrusal programlama sorusunun çözümünü yorumlama


Videoyu izle: Python ile Doğrusal Programlama Optimizasyonu Simplex Çözümü Grafiksel Gösterim (Aralık 2021).