zlp'nin kanonik biçimi. Doğrusal Programlama Problemleri (LPP)

Sayfa 1

Problemin kurallı biçimi aşağıdaki üç özellikle karakterize edilir: 1) bir denklem sistemi biçiminde homojen bir kısıtlar sistemi; 2) problemde yer alan tüm değişkenler için geçerli olan homojen negatif olmayan koşullar ve 3) doğrusal bir fonksiyonun maksimizasyonu. Bu problemde, bu özelliklerin üçü de ihlal edilmiştir.

Problemin kurallı biçimi aşağıdaki üç özellikle karakterize edilir: 1) bir denklem sistemi biçiminde homojen bir kısıtlar sistemi; 2) problemde yer alan tüm değişkenler için geçerli olan homojen negatif olmayan koşullar ve 3) doğrusal bir fonksiyonun maksimizasyonu. Bu problemde, bu özelliklerin üçü de ihlal edilmiştir.

Sorunun kanonik formu doğrusal programlama kabul edilebilir bölgenin ilk tepe noktasını bulmanın kolay olması açısından uygundur.

Doğrusal programlama probleminin kanonik biçimini ve Jordan-Gauss eleme yöntemini düşünün.

Doğrusal programlama probleminin kanonik biçimi genellikle uygun olur.

Kısıtlamalar sistemini dönüştürürken kanonik biçim doğrusal programlama problemleri, eşitsizlikler (12) ve (13) eşitlikleri ile değiştirilmelidir. Bunun için, ek negatif olmayan değişkenler tanıtılır.

Çift yönlü değişmeli gerçek matrislerin, bir ortogonal matris aracılığıyla bir benzerlik dönüşümü ile aynı anda problem 1128'in kanonik formuna indirgenebileceğini kanıtlayın.

Özünde, (4) - (5), Böl. Genellikle doğrusal olmayan programlama problemlerinde tamsayı değişkenleri için gereksinim ortaya konulmaz.

Kısıtlama türleri ve dönüşümleri için yöntemler.

Problemin kanonik biçimi, bir denklem sistemi biçimindeki kısıtlamalar sisteminin homojenliği ile karakterize edilir; amaç fonksiyonunu maksimize etmek; problemde yer alan tüm değişkenlerin negatif olmama durumu.

Hiçbiri Ek özellikler düşünülen problemlerin kanonik biçimi hesaplama devresi eklemez.

Önce minimum problemin ikinci kanonik biçimini ele alalım.

Simplex-meta algoritması iki aşamaya ayrılabilir. İlk aşamada değişkenler elenerek temel çözüme ulaşılır. Bulunursa, ikinci aşamaya geçiş için problemin kanonik formuna sahibiz. İkinci aşamada, sınırlı bir optimumun olup olmadığını kontrol ederiz. Varsa, kabul edilebilir temel çözümler belirlenir ve en uygun olanı seçilir.

Problem kurallı biçimde çözülürse, ikinci paragrafta tanıtılan işlemlerin yalnızca bir kısmı kullanılır. Bu nedenle, kanonik minimum problem için, sadece 3.4.1 maddesinin durumu uygulanır ve sadece kolonların döngüsel permütasyon işlemleri, kolonu dikey sınır bölgesinden geçirme, yapısal ihlalleri düzeltme ve kesme işleminin bir kısmına ihtiyaç vardır. . Simetrik olarak, kanonik problemi maksimuma çözerken, sadece 3.4.2 maddesi durumu gerçekleştirilir ve dizelerin döngüsel permütasyon işlemleri, dizeyi yatay sınır bölgesinden geçirme, yapısal ihlalleri düzeltme ve kesmenin başka bir kısmı. operasyona ihtiyaç vardır. Aksi takdirde, sorunun kurallı biçimi herhangi bir ek özellik eklemez.

Giriş bölümünün ilk paragrafında, genel bir doğrusal programlama probleminin nasıl kanonik formlardan birine indirgenebileceği gösterildi. Kanonik olarak (aynı problemler, ardışık iyileştirme yönteminin açıklaması resmi olarak basitleştirilmiştir, çünkü optimallik koşullarını ihlal etmek için iki seçeneği ve bir sonraki tepe noktasına ulaşmak için iki seçeneği dikkate almaya gerek yoktur. Ancak, bu durumda boyutlar Temel olarak karmaşıklığı belirleyen temel matris A [ /, J ] Bununla birlikte, birçok durumda yöntemin problemin kanonik biçimlerine uygulanması tercih edilir ve bu bölümde doğrusal programlamanın belirli problemleri için elde edilen yöntem.

Sayfalar:      1

kanonik biçim, amaç fonksiyonunu maksimize etmek gerekirse, tüm sistem kısıtlamaları denklemlerdir ve tüm değişkenler negatif olmama koşuluna tabidir.

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

Sayı kümesi denir kabul edilebilir çözüm (plan) LLP kısıtlama sistemini karşılıyorsa.

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

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

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

Her üç form PLP kayıtları bir biçimden diğerine geçmek için algoritmalar olması anlamında eşdeğerdir. Bu nedenle, bir problemi formlardan birinde çözmenin bir yolu varsa, o zaman başka bir formda verilen bir problem için en uygun planı belirlemek her zaman mümkündür. Problem simetrik bir biçimde çözülür. grafik yöntemi, ve simpleks yöntemiyle kanonik biçimde.

Bir formdan diğerine geçiş için algoritmaları düşünün.

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

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

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

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

örnek 1

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

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

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

Teorem 2 İki keyfi nokta olsun ve uzayda R n. Sonra segmentin herhangi bir noktası için [ PQ] olmalıdır: .where .

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

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

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

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

çokyüzlü bir veya daha fazla yarım uzayın kesişimi olarak adlandırılır. İki boyutlu durumdaki bir çokyüzlüye çokgen denir.

Örnek 2

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

sınırlı set

Sınırsız set

tek nokta

Boş küme

Bir dışbükey kümenin bir noktasına denir açısal, kümeden diğer iki noktayı birleştiren herhangi bir parçanın içinde değilse.

Örnek 3

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

Bir çokyüzlülüğün köşe noktasına onun adı verilir. toplantı.

Simetrik bir biçimde verilen bir LLP'yi ele alalım.

teorem 4 Optimum LLP planı, kısıtlama sistemi tarafından tanımlanan karar polihedronunun tepe noktasına karşılık gelir.

Herhangi bir doğrusal programlama problemi, kanonik formda bir doğrusal programlama problemine indirgenebilir. Bunun için Genel dava maksimizasyon problemini minimizasyon problemine indirgeyebilmeniz gerekir; eşitsizlik kısıtlamalarından eşitlik kısıtlamalarına geçmek ve negatif olmama koşuluna uymayan değişkenleri değiştirmek. Bazı fonksiyonların maksimizasyonu, aynı fonksiyonun zıt işaretli minimizasyonuna eşdeğerdir ve bunun tersi de geçerlidir.

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

• eğer içindeyse orijinal sorun bir lineer fonksiyonun maksimumunu belirlemek gerekir, o zaman işaretini değiştirmeli ve bu fonksiyonun minimumunu aramalısınız;
• sınırlıysa sağ kısım negatifse, bu limit -1 ile çarpılmalıdır;
• kısıtlamalar arasında eşitsizlikler varsa, negatif olmayan ek değişkenler dahil edilerek bunlar eşitliklere dönüştürülür;
• eğer bazı değişkenler x j işaret kısıtlaması yoksa, (amaç fonksiyonunda ve tüm kısıtlamalarda) iki yeni negatif olmayan değişken arasındaki farkla değiştirilir:
  x 3 \u003d x 3 + - x 3 - , nerede x 3 + , x 3 - ≥ 0 .

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

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

Kısıtlama sisteminin her 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şareti ile girilir ve ikinci denklemde değişken x5"-" işareti ile girilir.

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 \u003d -1;
2x 1 - x 2 + x 6 = -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 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x1 + x2 - x6 = 3.

Doğrusal programlama problemlerinin kanonik yazım biçiminde, kısıtlama sistemine dahil edilen tüm değişkenler negatif olmalıdır. varsayalım ki x 1 = x 1 "- x 7 , nerede x 1" ≥ 0, x 7 ≥ 0 .

değiştirme verilen ifade kısıtlamalar sistemine ve amaç fonksiyonuna ve değişkenleri indeksin artan sırasına göre 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 - x 3 + x 4 = 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.

Optimallik koşulu temel plan kanonik LP sorunu. Simpleks yöntemi ve yakınsaklığı.

Simpleks yöntemi evrensel, yazılmış hemen hemen her doğrusal programlama probleminin çözülmesine izin verdiği için kanonik form.

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

Amaç fonksiyonunun değeri, görevler için maksimuma bu yer değiştirme ile azalmaz.

Referans çözümlerinin sayısı sonlu olduğundan, sonlu sayıda adımdan sonra optimal referans çözümünü elde ederiz.

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

Simpleks Yöntem Algoritması

1. Matematiksel model görevler olmalı kanonik. Kanonik değilse, kanonik forma indirgenmelidir.

2. İlk referans çözümünü buluyoruz ve optimallik için kontrol ediyoruz.
Bunu yapmak için doldurun tek yönlü tablo 1.
1. adım tablosunun 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. Eğer tüm katsayılar son satır tek yönlü tablolar Dj³ 0, sonra bulundu

karar en uygun.

2 En az bir katsayı ise DJ £ 0, ancak karşılık gelen değişkenle tek bir pozitif tahmin edilen ilişki yoktur, o zaman çözüm görevleri durduruyoruz, çünkü F(X) ® ¥ , 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.

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

5. Eğer en az bir katsayı Dk ise< 0 ,o zamanlar k - inci sütun kabul lider için.

6. İçin lider çizgi uygun olanı kabul et asgariücretsiz üye oranı iki pozitif katsayılara lider, k - bu kolon.

7. Önde gelen satır ve sütunların kesiştiği noktada bulunan elemana denir. lider eleman.

Simpleks tablo 2'yi doldurma :

· temel sütunu sıfır ve bir ile doldurun

· baştaki satırı, önde gelen öğeye bölerek yeniden yazın

baştaki satırda sıfırlar 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ü alıyoruz optimallik için:

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

Değilse, 8. adımın simpleks tablosunu doldururuz, vb.

amaç fonksiyonu ise F(X) bulmayı gerektirir Minimum değer, ardından kriter problem optimalliği bir katsayıların pozitif olmaması D j hepsi için j = 1,2,...n.

Simpleks yönteminin yakınsaklığı. LP problemlerinde yozlaşma. Herhangi bir hesaplama algoritmasının en önemli özelliği yakınsamadır, yani uygulama sırasında sonlu sayıda adımda (yinelemelerde) istenen sonuçları (belirli bir doğrulukla) elde etme olasılığıdır.

Simpleks yönteminin yakınsaması ile ilgili problemlerin, aynı olduğu durumda r'nin (bölüm 2") değerinin seçilmesi aşamasında potansiyel olarak ortaya çıkabileceğini görmek kolaydır. minimum değerler ilişki

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

Doğrusal programlama problemini çözmek için analitik bir yöntem, simpleks yöntemi. Uygulaması için, çeşitli şekillerde sunulan DP problemleri kanonik bir forma indirgenmelidir. (2.1.1)-(2.1.3) biçiminde yazılan doğrusal programlama problemi, genişletilmiş bir yazı biçimidir. ortak görev doğrusal programlama (LLP).

Aşağıdaki problem, kanonik doğrusal programlama problemi (CLPLT) olarak adlandırılacaktır:

eşitlik şeklinde kısıtlamalar altında,

(2.3.1)-(2.3.4) şeklindeki problem koşulu sağlıyorsa t = n, daha sonra çözümü denklem sistemini çözmeye indirgenir

• (2.3.2) . Bu durumda, koşul varsa sorunun çözümü olmayacaktır.
• (2.3.3) sağlanmadı veya denklem sisteminin çözümü yok.

koşul t

• 1. gitmek maksimizasyon probleminden amaç fonksiyonu (2.3.1) minimizasyon sorunu yeterli tüm katsayıları al Cj amaç fonksiyonu ters işaretli ve ortaya çıkan sorunu maksimuma çıkarın. Maksimumu bulduktan sonra, amaç fonksiyonunun değeri ters işaretli olarak alınmalıdır. Optimal çözüm aynı kalır.
• 2. gitmek eşit veya küçükten kısıtlamaya eşit ihtiyacı var artı işaretiyle:

3. gitmek büyük veya eşittirden kısıtlamaya, eşitliğe ihtiyacı var negatif olmayan ek bir değişken tanıtın eksi işaretiyle:

Aynı zamanda, her eşitsizlik kendi (n +/) ek bir değişkendir.

• 4. Hepsi negatif serbest terimleri olan eşitlikler ile bölünebilir-1 koşulu sağlamak için (2.3.4).
• 5. Eğer bazı değişkenler için Xj, negatif olmama koşuluna tabi değildir, o zamanlar Xj=x" değişkenlerinin değişimini yapın.- X" x"j> 0, x "> 0. Dönüştürülen problemde tüm değişkenler negatif değildir.

Herhangi bir ZLP'nin kanonik bir forma indirgenebileceğine dair bir açıklama var.

Örnek 2.3.1. Örnek 2.2.2'de verilen problemi kanonik forma çevirelim. Amaç fonksiyonu ve kısıtlama sistemi şöyle görünür:

Birinci eşitsizliğe, ikinci eşitsizliğe artı işaretli ek bir jc 3 > 0 değişkeni ekliyoruz. x 4> eksi işareti ile 0 ve üçüncü x 5> 0 ayrıca artı işaretiyle. Sonuç olarak, problem için kurallı biçimde bir kısıtlar sistemi elde ederiz:

Bu kısıtlamalar altında, bulmamız gerekiyor maksimum değerözellikleri:

Düşünmek Ekonomik anlamda kaynakların optimal kullanımının kanonik probleminde ek değişkenler.

Örnek 2.3.2. Kaynakların optimal kullanımı sorunu (halı sorunu)[17J.

fabrika var belli bir miktarüç tür kaynak: işçilik (80 adam-gün), hammadde (480 kg) ve ekipman (130 makine saati). Fabrika dört çeşit halı üretebilmektedir. Her türden bir halının üretimi için gerekli olan her bir kaynağın birim sayısı ve işletmenin her türden maldan bir birim elde ettiği gelire ilişkin bilgiler Tablo'da verilmiştir. 2.3.1.

Toplam maliyetinin maksimum olacağı böyle bir üretim planının bulunması gerekmektedir.

Problemin ekonomik ve matematiksel modeli Değişkenler: x x, x 2, x 3, x 4 - her türden halı sayısı. Hedef işlevi - maksimize edilecek toplam çıktı maliyeti:

Kaynak sınırları:

x 5 ek değişkenleri ekleyerek sorunu kanonik forma getiriyoruz, x 6 ve x 7:

Ayrıca, optimal üretim planının vektör olduğu gösterilecektir. X* =(0; 30; 10; 0), amaç fonksiyonu değeri 150'dir, yani. toplam üretim maliyetini maksimize etmek için ikinci tipten 30 halı ve üçüncü tipten 10 halı üretmek gerekir. Vekil optimal değerler vektör X KZLP sınırları dahilinde:

"Emek" ve "ekipman" kaynaklarının tamamen kullanıldığını, "hammadde" kaynağının bolca mevcut olduğunu anlıyoruz:

Bu durumda x içinde 200 kg hammadde kaldığını göstermektedir.

Yani ana değişkenler x v x 2, x 3, x l her tipteki halı sayısı ve ek değişkenler anlamına gelir x 5, x 6 onların 7 - az kullanılan kaynakların miktarı.

Cevap. Optimum üretim planı X* = (0; 30;

10; 0).

plan, veya kabul edilebilir çözüm, QZLP vektör olarak adlandırılır X=(jc p X 2 ,..., x n) tatmin edici koşullar (2.3.2)-(2.3.4).

QZLP kısıtlama sisteminin temel çözümünün tüm bileşenleri negatif değilse, böyle bir çözüme denir. Referans çözümü veya temel plan. Temel planın pozitif bileşenlerinin sayısı aşağıdakileri aşamaz: t.

Temel plan denir dejenere olmayan, içeriyorsa t pozitif bileşenler, aksi takdirde denir dejenere.

Optimal Plan veya en uygun çözüm ZLP, doğrusal bir fonksiyonun (2.3.1) en büyük (en küçük) değerini veren bir plandır.

Tüm LLP planları kümesi (varsa) dışbükey çokyüzlü.Çözüm polihedronunun her köşesi (en uç) noktası şuna karşılık gelir: referans planı(QZLP denklem sisteminin negatif olmayan temel çözümleri). Her temel sistem tarafından tanımlanır t verilen sistemde bulunan lineer bağımsız vektörler P vektörler D, D,..., bir p. Optimal bir plan varsa, o zaman çözüm çokyüzlüsünün bir köşe noktası vardır. doğrusal fonksiyon maksimum (en küçük) değerine ulaşır.

Optimal planı bulmak için sadece temel planları incelemek yeterlidir. Üst sınır görevde yer alan temel planların sayısı, kombinasyonların sayısına göre belirlenir C t p (bkz. paragraf 1.4).

Örnek 2.3.3. Sınırlı kaynakların optimal kullanımı sorununa bir çözüm bulun (LP P'yi çözün):

Karar. Ek değişkenler ekleyerek sorunu kanonik forma getirelim. x 3, x 4 ve x 5:

Verilen KZLP'nin kısıtlamalar sisteminin tüm temel planlarını bulalım (n? - 5; /77 - 3); sayıları 10'u geçmez:

Jordan-Gauss yöntemini kullanarak (bkz. paragraf 1.4), denklem sisteminin tüm temel çözümlerini yazıyoruz (Tablo 2.3.2).

Sayı temel ayak çözümler	temel						Plan

On temel çözüm arasında beş temel çözüm vardır:

Şekil l'de belirtilen referans planları. 2.3.1 sırasıyla aşağıdaki köşe noktalarına ve bunlardaki dijital filtrenin değerlerine karşılık gelir:

Pirinç. 2.3.1.

teoriye göre LP en uygun çözüm temel planlarda yer almaktadır.

Böylece, 2300'e eşit maksimum değere, noktada amaç fonksiyonu tarafından ulaşılır. AT temelde X5 = (70; 80; 0; 60; 0).

Cevap. Optimal görev planı: x (= 70, x 2 = 80, amaç fonksiyonu değeri f(x v x 2) = 2300.

ax = b biçiminde bir doğrusal programlama problemi, burada a bir katsayılar matrisi, b bir kısıtlama vektörüdür.
Misal :

Her bir LP görevinde, aşağıdakilerin sağlanması koşuluyla değişkenlerin değerleri aranır:

• bu değerler bazı sistemleri tatmin etti lineer denklemler veya eşitsizlikler;
• bu değerler için amaç fonksiyonu minimuma veya maksimuma dönecektir.

Talimat. Değişken sayısını ve satır sayısını (kısıtlama sayısı) seçin. Ortaya çıkan çözüm bir Word dosyasına kaydedilir.

Biri evrensel yöntemler LP tek yönlü bir yöntemdir, ancak LP probleminin kanonik bir formu varsa uygulanabilmektedir.

Tanım. Sistemin tüm kısıtları sadece denklemlerden oluşuyorsa (değişkenlerin negatif olmama durumunu ifade eden eşitsizlikler hariç) ve amaç fonksiyonunun minimize edilmesi gerekiyorsa, LP problemi kanonik bir forma sahiptir.
Kurallı biçimde böyle bir LP problemine bir örnek problem 1'dir - bir kısıtlama sistemi (1) ve amaç fonksiyonu (2).
Bununla birlikte, çoğu ekonomik problemde, çoğu zaman, kısıtlamalar sistemi başlangıçta sadece denklemleri değil, aynı zamanda eşitsizlikleri de içerir.

İfade. Herhangi bir genel LP problemi kanonik bir forma indirgenebilir.
Genel DP probleminin kanonik forma indirgenmesi, yeni (bunlara ek olarak adlandırılır) değişkenler getirilerek elde edilir.
Bu problemin kısıt sistemi (3) dört eşitsizlikten oluşmaktadır. Ek değişkenler tanıtarak y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, kısıtlama sistemine geçebiliriz:

Bu ek değişkenler y kesinlikle net bir ekonomik anlamım var, yani, kullanılmayan çalışma süresi anlamına geliyorlar (makine arıza süresi ben-th tipi).
Örneğin, birinci tip makineler 18 saatin tamamında çalıştıysa, x + y = 18, bu nedenle, y 1 = 0. Ancak ilk makinenin zamanının eksik kullanılması olasılığına izin veriyoruz. x + y<18. В этом случае y 1 pozitif olur ve kullanılmayan bir zaman sınırı olarak kabul edilebilir. Örneğin, paragraf 3.3.2'den bu sorunun çözümünü bilmek, x = 12, y= 6, kısıtlar sisteminden (3.9) şu sonucu çıkarabiliriz: y 1 = y 2 = y 3 = 0 ve y 4 \u003d 12 - 6 \u003d 6. Yani, birinci, ikinci, üçüncü tipteki makineler çalışma sürelerini tam olarak kullanır. Ancak dördüncü makine sadece yarı yüklü, 6 saat ve belirli bir optimal planla boşta. Belki de, bu tür sonuçlardan sonra, işletmenin başkanı onu başka işlerle yüklemek, bu sefer kiralamak vb.
Böylece, ek değişkenler ekleyerek, herhangi bir eşitsizlik türü kısıtlamasını bir denkleme indirebiliriz.

Karışım problemini düşünün. Kısıtlama sistemi şöyle görünür:
Eşitsizlikler "daha büyük"e çevrildi, bu nedenle, y 1 , y 2 , y 3 ≥ 0 ek değişkenleri dahil edildi, sağ tarafla eşitlemek için sol taraftan çıkarılmaları gerekiyor. Kanonik biçimde bir kısıtlama sistemi elde ederiz:
Değişkenler y ayrıca ekonomik anlamda da mantıklı olacaktır. Sorunun pratik içeriğini hatırlarsanız, y 1 değişkeni, karışımdaki fazla A maddesi miktarı, y 2 - fazla madde miktarı anlamına gelecektir. AT karışımda y 3 - fazlalık İle karışımda.
Amaç fonksiyonunun maksimum değerini bulma görevi, fonksiyon için minimumu bulmaya indirgenebilir - F maks F = –min (– F) ifadesinin açıklığı göz önüne alındığında. Şekle bakın: eğer bir noktada x= x 0 işlevi y= F(x) maksimum değerine ulaşır, ardından fonksiyon y= –F(x) eksen etrafında simetrik ÖKÜZ, aynı noktada x 0 minimuma ulaşacak ve F maks = - (- F dk) de x = x 0 .

Çözüm. LP problemini kanonik biçimde temsil etmek için gereklidir:

• ek değişkenler ekleyerek problemin kısıtlar sisteminde yer alan eşitsizlikleri denklemlere dönüştürmek;
• amaç fonksiyonu ise F→max (maksimize edildi), bir fonksiyon ile değiştirilir - F→ min (küçültülmüş).