Haupt- Andere Disziplinen Bücher Matisch mathematische programuvannya - Nakonechny S.І.

Matisch mathematische programuvannya - Nakonechny S.І.

3.4. Kolben zastosuvannya teorії dvoїstostі für znahodzhennya optimal planіv pryamoї die Aufgaben dvoїstoї

Kutane s dvoh Konjugation Problem rozv'yazati okremo gegen vstanovlenі Sätze sein kann dvoїstostі zalezhnostі mіzh optimalen Plan pryamoї die Aufgaben dvoїstoї umozhlivlyuyut znahodzhennya rozv'yazku dvoїstoї zadachі für nayavnostі optimalen Plan pryamoї, navpaki i.

Bevor zadanoї zadachі lіnіynogo programuvannya zapisati dvoїstu Aufgabe. Rozv'yazati ein h ihnen die Simplex-Methode ist der optimale Plan viznachiti Druha zadachі, vikoristovuyuchi spіvvіdnoshennya pershoї dvoїstostі Satz.

max Z = - 5 2 x1 + x2;

Rozv'yazannya. Perche nіzh zapisati dvoїstu Aufgabe neobhіdno direkten Problem Zvesti Standard viglyadu. Oskіlki tsіlova funktsіya maksimіzuєtsya F i in sistemі obmezhen Je nerіvnostі dann їh slіd Zvesti bedeuten " ". Tom Pershe obmezhennya zadachі pomnozhimo (-1). Pіslya tsogo Zeichen nerіvnostі zmіnitsya auf protilezhny. Otrimaєmo:

max Z = - 5 2 x1 + x2;

Teper für vіdpovіdnimi Regeln sklademo dvoїstu Problem:

min F = - y1 + 5 y2;

Oskіlki zapisanі zadachі simetrichnі, dann, ob sie s rozv'yazati Simplex-Methode Yak. Napríklad, viznachimo spochatku pryamoї optimal zadachі Plan. Für tsogo zastosuєmo Verfahren Algorithmus simplex.

1. max Z = - 5 2 x1 + x2 + x3 + 0 0 x4;

2. Der Vektor Form Aufzeichnungssystem obmezhen Got viglyad:

.

de . . . . .

In sistemі vektorіv für utvorennya Pochatkova odinichnogo Basis vіdsutnіy ein Vektor. Tom vvedemo boxed zmіnnu in Pershe obmezhennya.

3. Rozshirena Aufgabe lіnіynogo programuvannya bude mit einem solchen:

max Z = - 5 2 x1 + x2 + x3 + 0 0 x4 - x5 M;

In tsіy zadachі x 4 x 5 , dass - bazisnі zmіnnі, und x1, x2, x3 - vіlnі. Nekhay x1 = x2 = x3 = 0, todі x4 = 5; x5 = 1 ist .

Purshia zadachі Support-Programm:

X = 0 (0, 0, 0, 5, 1), Z 0 = - M.

4. Weg rozv'yazuvannya pryamoї zadachі eingereicht in viglyadі simpleksnoї tablitsі:

W ostannoї simplex tablitsі optimalen Plan zapishemo pryamoї zadachі:

X * = (0; 5,3; 2,3; 0), Z max = 10/3.

Zgіdno Zi spіvvіdnoshennyam dvoїstostі für Perche Satz kann scho optimalen Plan visnovuvati dvoїstoї zadachі іsnuє i

min F = max Z = 10/3.

Komponenten der Vektoren Y * viznachimo der Formel (optimal zadachі Plan dvoїstoї):

.

de dass mіstitsya in stovpchiku "sbaz" ostannoї simplex tablitsі;

.

Matrix D- 1 takozh mіstitsya in ostannіy simplex tablitsі in stovpchikah zmіnnih «x5» dieser «x4», SSMSC utvoryuvali Pochatkova Basis.

Otzhe,

.

min F = - 0 1 x + 5 x 2/3 = 10/3.

Zastosuvavshi für rozv'yazuvannya pryamoї zadachі Simplex-Methode, mi znayshli її optimalen Plan und potіm viznachili optimal rozv'yazok dvoїstoї zadachі for Relief spіvvіdnoshen pershoї dvoїstostі Satz.

Bevor zadanoї zadachі lіnіynogo programuvannya zapisati dvoїstu Aufgabe. Rozv'yazavshi dvoїstu Aufgabe grafіchno, viznachiti optimalen Plan pryamoї zadachі.

min Z = x1 + x2 + 2 2 x3;

Rozv'yazannya. Für vіdpovіdnimi Regeln pobuduєmo dvoїstu Problem:

max F = y1 + y2 4;

Zauvazhimo scho zadachі nesimetrichnі, y1 i scho Persha vіdpovіdaє rіvnyannyu in sistemі obmezhen pryamoї zadachі, Mutter Mauger zu zmіnna ob yaky unterzeichnen und zmіnna v2 - nevіd'єmna Entbehrung.

Dvoїsta Aufgabe Got Dvi zmіnnі und Otzhe, її mozhna rozv'yazati grafіchno (Abb. 3.2).

Fig. 3.2

Naybіlshogo Werte tsіlova funktsіya dvoїstoї zadachі F dosyagaє in tochtsі In bagatokutnika ABCD. Її Koordinaten viznachimo rozv'yazannyam Sistemi rіvnyan:

Otzhe, Y * = (- 2/3; 4/3); max = F 1 x (- 2/3) + 4 x 4/3 = 14/3.

Optimal Plan pryamoї zadachі viznachimo for Relief spіvvіdnoshen Druha dvoїstostі Satz.

Pіdstavimo Y * im System obmezhen dvoїstoї zadachі i z'yasuєmo, Yak vikonuyutsya obmezhennya tsієї zadachі:

Oskіlki Pershe obmezhennya für optimalen Plan dvoїstoї zadachі vikonuєtsya Yak strengen nerіvnіst dann visnovuєmo scho Persha zmіnna pryamoї zadachі dorіvnyuvatime Null x 1 = 0 (Persha Chastina Druha dvoїstostі Theorem).

Teper proanalіzuєmo dvoїstoї optimal zadachі Plan. Oskіlki andere Komponente v2 = 4/3 dodatna Plan, der andere obmezhennya pryamoї zadachі für X * vikonuvatimetsya Yak streng rіvnyannya (andere Chastina Druha dvoїstostі Theorem).

Ob'єdnuyuchi zdobutu іnformatsіyu können System zapisati obmezhen pryamoї zadachі Yak dvoh rіvnyan System in yakіy x1 = 0, das viznachiti Rasht zmіnnih:

tobto = X * (0; 5/3; 2/3), min Z = 0 + 1 x 2 x 2 x 5/3 + 2/3 = 14/3.

Umov min Z = max F = 14/3 vikonuєtsya ich , dass X * = (0, 5/3, 2/3); Y * = (- 2/3; 4/3 ) Je optimalen Plan vіdpovіdno pryamoї , die Aufgaben dvoїstoї.

Viznachiti, chi Je takі optimal Plagne sformulovanoї zadachі lіnіynogo programuvannya:

12 min Z = x1 - x2 + 2 4 x3;

a) X = (8/7, 3/7, 0); b) X = (0; 5,1; 8,5); c) X = (1/3, 0, 1/3).

Rozv'yazannya. Prinzip rozv'yazuvannya Probleme dieser Art ґruntuєtsya auf vikoristannі Druha dvoїstostі Satz. Neobhіdno pobuduvati dvoїstu Aufgabe ein dopuskayuchi scho vіdpovіdny Plan x ∈ optimal viznachiti optimal rozv'yazok dvoїstoї zadachі. Yakscho bei tsomu ekstremalnі Werte tsіlovih funktsіy für Wert odnakovimi wird, gedünstet dann richtig. Protilezhne mozhna visnovuvati solche vipadkah:

1. Yakscho zaproponovany Plan X ist nicht akzeptabel, nicht tobto zadovolnyaє System obmezhen pryamoї zadachі.

2. Yakscho viznacheny dvoїstoї Plan zadachі nicht akzeptabel, tobto nicht zadovolnyaє OAO Alle obmezhennya dvoїstoї zadachі.

3. Yakscho viznacheny Plan dvoїstoї zadachі Zulässigkeit, ale für Demba ekstremalne Werte tsіlovoї F funktsії nicht funktsії die Z - Werte nicht dorіvnyuє, tobto nicht vikonuєtsya Umov pershoї dvoїstostі Satz.

Zapishemo dvoїstu Aufgabe pryamoї zadachі lіnіynogo programuvannya:

max F = y1 + y2 2;

Perevіrimo zaproponovanі Plagne auf optimalnіst.

1. X = (8/7, 3/7, 0). Pіdstavimo Yogo in obmezhen pryamoї zadachі:

Obidva obmezhennya vikonuyutsya, i bis X = (8/7, 3/7, 0) Je realistischer Plan pryamoї zadachі. Pripustimo Teper scho zaznacheny Plan Je optimalen Plan pryamoї zadachі. Todі rozrahuєmo für Demba Wert tsіlovoї funktsії: Z = 12 x 8/7 - 4 3/7 x 2 + x 0 = 12.

Skoristaєmosya andere Sätze, die dvoїstostі viznachimo vіdpovіdny dvoїstoї zadachі Plan. Oskіlki x1 = 8/7> 0; x2 = 3/7> 0, dann von einem anderen zgіdno s Chastain Druha Satz dvoїstostі mozhna zapisati Pershe , dass andere obmezhennya rіvnyannya Yak i viznachiti y1 , die v2:

Pіdstavimo tsі Wert in tretє obmezhennya Sistemi dvoїstoї zadachі:

;

.

Für viznachenih Werte y1 = 4; v2 = 4 tse obmezhennya nicht vikonuєtsya, ich plane y vіdpovіdny = (4; 4) Je Unzulässigkeit bis dvoїstoї zadachі. Vnaslіdok tsogo unsere Annahmen, scho X = (8/7, 3/7, 0) Je optimalen Plan pryamoї zadachі, viyavilosya pomilkovim.

2. X = (0; 5,1; 5,8). Pіdstavimo Tsey Plan in obmezhen System pryamoї zadachі:

Machbar Plan, i für Demba Z = 12 x 0-4 x 1/5 + 2 x 8/5 = 12/5.

Viznachimo vіdpovіdny Plan dvoїstoї zadachі. Oskіlki Komponenten , die x 2 x 3 dodatnі, andere i tretє obmezhennya dvoїstoї zadachі mozhna zapisati Yak rіvnyannya:

Perevіrimo, chi vikonuєtsya Pershe obmezhennya dvoїstoї zadachі für viznachenih Werte y1 , dass v2: 2 x 8/5 + 2/5 = 18/5 <12 Otzhe, Pershe obmezhennya vikonuєtsya, i bis v = (8/5, 2/5) je realistischer Plan dvoїstoї zadachі. Für Demba

F = 8/5 + 2 x 2/5 = 5.12 = Z.

Je optimalen Plan dvoїstoї zadachі und X * = (0; 1/5; 8/5); W Blick um mozhna visnovuvati scho Y * = (2/5 8/5) zu vikladene - optimalen Plan pryamoї zadachі.

Unser gedünstet vіdnosno zaproponovanogo Plan viyavilosya richtig.

3. X = (1/3, 0, 1/3). Für tsogo Plan obmezhennya pryamoї zadachі vikonuyutsya wie folgt:

Oskіlki X = (1/3, 0, 1/3) Je Unzulässigkeit des Plans, die vіn nicht Mauger Buti takozh optimalen Plan pryamoї zadachі.

Otzhe, perevіrka zaproponovanih planіv auf optimalnіst gab takі Ergebnis: a) ni; b) so , dass X = (0; 1/5; 8/5), min Z = 5.12; c) ni.