Duālās lineārās programmēšanas uzdevumu sastādīšanas noteikumi. Duālās lineārās programmēšanas problēmas jēdziens Nenulles kontroles parametri optimālajam duāla risinājumam

Duālās problēmas struktūra un īpašības

Jebkuru LP maksimizēšanas problēmu no ekonomiskā viedokļa var uzskatīt par ierobežotu resursu b 1 ,b 2 ,…,b m sadales problēmu starp dažādiem patērētājiem, piemēram, starp dažiem tehnoloģiskiem procesiem, kurus attēlo ailes A 1 , Problēmas ierobežojumu matricas A 2 ,…A n. Jebkurš iespējamais problēmas risinājums LPx 1 ,x 2 ,…x n dod konkrētu sadalījumu, norādot katra resursa daļu, kas būtu jāizmanto attiecīgā tehnoloģiskā procesa realizācijā.

Apskatīsim piemēru. Rūpnīcā tiek ražoti trīs veidu izstrādājumi x 1, x 2 un x 3, no kuriem katram nepieciešams laiks, kas pavadīts apstrādei uz virpām, frēzēšanas un urbjmašīnām. Mašīnas laiks katrai iekārtai ir ierobežots. Letc 1,c 2,c 3 – peļņa no attiecīgā produkta veida vienības pārdošanas. Jānosaka, cik no katra produkta veida nedēļas laikā jāsaražo, lai gūtu maksimālu peļņu.

Formāli šis uzdevums ir uzrakstīts šādi:

palielināt (c 1 x 1 + c 2 x 2 + c 3 x 3) (1)

saskaņā ar ierobežojumiem

a 11 x 1 + a 12 x 2 + a 13 x 3 ≤ b 1;

a 21 x 1 + a 22 x 2 + a 23 x 3 ≤ b 2;

a 31 x 1 +a 32 x 2 +a 33 x 3 ≤ b 3, (2)

kur a 1 j , a 2 j , a 3 j ir laiks, kas nepieciešams, lai apstrādātu j-tā veida izstrādājuma vienību attiecīgi uz virpas, frēzēšanas un urbjmašīnām (j = 1, 2, 3); b 1 , b 2 , b 3 – iknedēļas mašīnas laika resurss attiecīgi virpošanas, frēzēšanas un urbjmašīnām.

Apzīmēsim y 1 , y 2 un y 3 – virpu, frēzēšanas un urbjmašīnu darbības laika vienības cenu. Tad 11 y 1 +a 21 y 2 +a 31 y 3 – var interpretēt kā pirmā veida produkta vienības ražošanas izmaksas; a 12 y 1 +a 22 y 2 +a 32 y 3 – izmaksas otrā veida izstrādājuma vienības izgatavošana utt. d.

Pieņemsim, ka resursu cenas y 1 ,y 2 ,…,y m ir izvēlētas tā, lai tiktu izpildītas šādas attiecības:

a 11 y 1 + a 21 y 2 + a 31 y 3 ≥ c 1;

a 12 y 1 + a 22 y 2 + a 32 y 3 ≥ c 2;

a 13 g 1 +a 23 g 2 +a 33 g 3 ≥ c 3. (3)

Tā kā b 1 , b 2 un b 3 ir katrai mašīnai izmantotie mašīnas laika resursi, tad b 1 y 1 + b 2 y 2 + b 3 y 3 ir kopējās ražošanas izmaksas.

Ir jāatrod tādi y 1 , y 2 un y 3, kas atbilst nosacījumiem (3), saskaņā ar kuriem tiek samazinātas kopējās ražošanas izmaksas:

minimizējiet g(y 1 ,y 2 ,y 3)=b 1 y 1 +b 2 y 2 +b 3 y 3 (4)

apstākļos

y 1 ≥0;y 2 ≥0;y 3 ≥0.

Šo problēmu sauc duāls uzdevums saistībā ar problēmu (1), ko sauc par tiešo.

Tagad pierakstīsim tiešās un duālās problēmas vispārējā gadījumā.

Tiešais uzdevums:

maksimāli palielināt

apstākļos

(7)

Duāla problēma:

minimizēt

apstākļos

(10)

Matricas formā duālo uzdevumu pāris tiek uzrakstīts šādi:

maksimāli palielināt

apstākļos

minimizēt

apstākļos

A T y≥c; (15)

Salīdzinot tiešās un duālās problēmas ierakstīšanas formas, starp tām var izveidot šādas attiecības:

ja tiešā problēma ir maksimizācijas problēma, tad duālā problēma būs minimizēšanas problēma un otrādi;

tiešās problēmas mērķfunkcijas koeficienti c 1 , c 2 ,…, c n kļūt par brīviem dalībniekiem no duālās problēmas ierobežojumiem;

brīvi tiešās problēmas ierobežojumu nosacījumi b 1 , b 2 ,…, b m kļūt par duālās problēmas objektīvās funkcijas koeficientiem;

duālās problēmas ierobežojumu matricu iegūst, transponējot tiešās problēmas ierobežojumu matricu;

ierobežojumu nevienlīdzības pazīmes ir apgrieztas;

tiešās problēmas ierobežojumu skaits ir vienāds ar duālās problēmas mainīgo lielumu skaitu, un duālās problēmas ierobežojumu skaits ir vienāds ar tiešās problēmas mainīgo lielumu skaitu.

Duālās problēmas mainīgos y 1 , y 2 ,…, y m dažreiz sauc par ēnu cenām.

Ir izdevīgāk atrisināt duālu problēmu nekā sākotnējā taisne, ja tā atrodas taisnā līnijā

problēma ir ar nelielu mainīgo skaitu liels skaits ierobežojumi (m n).

Saikne starp tiešās un duālās problēmas optimālajiem risinājumiem tiek noteikta, izmantojot šādas dualitātes teorēmas.

1. TEORĒMA. Ja - pieļaujami tiešo un dubulto problēmu risinājumi, t.i., tad

tie. tiešās problēmas objektīvās funkcijas vērtības nekad nepārsniedz duālās problēmas objektīvās funkcijas vērtības.

2. TEORĒMA (fundamentālā dualitātes teorēma).Ja -pieļaujamie tiešo un dubulto problēmu risinājumi un ja , Tas – optimāli risinājumi divkāršu problēmu pārim.

3. TEORĒMA.Ja tiešās problēmas optimālajā risinājumā(5) – (7) i-th ierobežojumu apmierina kā stingru nevienādību, tad atbilstošā duālā mainīgā optimālā vērtība ir vienāda ar nulli, t.i.

Kur - imatricas A rinda.

3. teorēmas nozīme ir šāda. Ja noteikts resurss ir pieejams pārpalikumā un i-tais ierobežojums optimālajā risinājumā tiek izpildīts kā stingra nevienādība, tad tas kļūst nenozīmīgs, un atbilstošā resursa optimālā cena ir vienāda ar 0.

3. teorēmu papildina 4. teorēma, kas nosaka sakarību starp tiešās problēmas optimālo risinājumu un duālās problēmas ierobežojumiem.

4. TEORĒMA. Ja duālās problēmas optimālajā risinājumā ierobežojumsjtiek apmierināta kā stingra nevienādība, tad tiešās problēmas atbilstošā mainīgā optimālajai vērtībai jābūt vienādai ar nulli, t.i., ja Tas

Sniegsim 4. teorēmas ekonomisko interpretāciju.

Tā kā daudzumi atspoguļo attiecīgo resursu cenas, tad

ir j-tā tehnoloģiskā procesa izmaksas, vērtība ir peļņa no pārdošanas uz vienu produkta vienību. Tāpēc no ekonomiskā viedokļa 2.7. teorēma nozīmē sekojošo: ja j-tais tehnoloģiskais process izrādās strikti neizdevīgs no optimālo resursu cenu viedokļa, tad tiešās problēmas optimālā risinājumā intensitāte šim tehnoloģiskajam procesam jābūt vienādam ar 0.

Tādējādi 4. teorēma izsaka rentabilitātes princips optimāli organizēta ražošana.

No tā arī izriet, ka

(20)

Pieņemsim, ka starp tiešās problēmas mainīgajiem x 1 ,x 2 ,…,x n ir tādu mmainīgo kopa, kuru vērtība optimālajā risinājumā nav nulle. Ļaujiet, piemēram, tie ir pirmie mainīgie secībā.

Pēc tam, pamatojoties uz (22) vienādojumu, tiek iegūti rentabilitātes nosacījumi:

(21)

Iesniegsim vēl divas svarīgas dualitātes teorijas teorēmas.

5. TEORĒMA (esamības teorēma).Tiešajām un duālajām problēmām ir optimāli risinājumi tad un tikai tad, ja abām ir iespējami risinājumi.

6. TEORĒMA (dualitātes teorēma).Derīgs vektorsx 0 ir optimāls tad un tikai tad, ja duālajai problēmai ir tik iespējams risinājumsy 0 , Kas

Starp tiešo un duālo problēmu optimālajiem risinājumiem un vienkāršās tabulas indeksu rindu elementiem, kas atbilst šiem risinājumiem, pastāv šāda saistība:

i=1, 2, …,m;j=1, 2, …,n,

kur n ir tiešās problēmas mainīgo skaits, m ir tās ierobežojumu skaits; ir attiecīgi tiešās un duālās problēmas indeksa līnijas elementi. Turklāt, ja n+i, kur 1 ≤i≤m ir lielāks par atbilstošās problēmas paplašinātās formas ierobežojumu matricas kolonnu vektoru skaitu, tad elementi tiek atrasti, cikliski pārkārtojot indeksa rindas elementus, sākot ar elementu

Vispārējs dualitātes gadījums

Iepriekšējā sadaļā tika izveidotas pamata sakarības divkāršu LP problēmu pārim ar ierobežojumiem nevienlīdzību veidā. Tagad vispārināsim šos rezultātus patvaļīgu ierobežojumu gadījumā.

Ļaujiet tiešajai LP problēmai norādīt formā:

maksimāli palielināt

apstākļos

Tad dubultā problēma attiecībā uz (24)-(26) (vai konjugāciju ar to) ir samazināt lineāro formu:

minimizēt

apstākļos

Tādējādi problēma, kas saistīta ar problēmu ar jauktiem apstākļiem, tiek apkopota saskaņā ar šādiem noteikumiem:

Ja pieņem, ka tiešās problēmas mainīgais x j ir nenegatīvs, tad ierobežojumu sistēmas (28) j-tais nosacījums ir nevienādība.

Ja x j šāds ierobežojums netiek uzlikts, tad duālās problēmas j-tais ierobežojums būs vienlīdzība.

Duālās problēmas y i mainīgo zīmes un tiešās problēmas atbilstošie ierobežojumi ir saistīti līdzīgi. Ņemiet vērā, ka, ja mēs ievietojam m 1 = min 1 = n, mēs iegūstam īpašs gadījums duālo problēmu pāri ar ierobežojumiem nevienlīdzības veidā.

Lineārā programmēšana. Lineārās programmēšanas problēmu izklāsts

Lineārā programmēšana ir tādu ārkārtēju problēmu risinājumu izpēte, kuras raksturo lineāra sakarība starp mainīgo un lineāro kritēriju. Priekšnoteikums tādi uzdevumi - resursu ierobežojumu esamība, pieprasījuma apjoms, ražošanas jauda utt.

ZLP matemātiskais modelis:

1. Mērķa funkcijas maksimums vai minimums (optimalitātes kritērijs).

2. Ierobežojumu sistēma formā lineārie vienādojumi un nevienlīdzības.

3. Mainīgo lielumu nenegatīvisms.

Ir pieļaujams risinājums, kas apmierina ierobežojumu sistēmu un risinājumu nenegatīvisma prasības, un tiek optimizēti risinājumi, kas vienlaikus atbilst min/max nosacījumiem.

ZLP vispārīgs skats

Maks.(min)F(x)=c1x1+c2x2+…cnxn

A11x1+a12x2+…a1nxn<=b1

A21x1+a22x2+…a2nxn<=b2

Am1x1+am2x2+…amnxn<=bnm, x1,x2,…xn>=0

ZLP īpašības:

1. ZLP pieļaujamā risinājumu kopa ir vai nu tukšs, vai izliekts daudzskaldnis.

2. Ja pieļaujamā kopa nav tukša un mērķa funkcija ir ierobežota augšpusē, lai palielinātu, un zemāk par minimizēšanu, tad tai ir optimāls risinājums.

3. Optimālais risinājums lineārās programmēšanas problēmām (ja tādas pastāv) atrodas uz robežas, t.i. ja ir optimāls risinājums, tad tā ir viena no pieļaujamo atrisinājumu daudzskaldņa virsotnēm, ja pieļaujamie atrisinājumi ir 2 vai vairākas virsotnes, tad jebkura to kombinācija ir optimāls risinājums.

Grafiskā metode ZLP risināšanai

Ja nezināmo skaits ir 2, tad to var atrisināt grafiski. Atrodi risinājumu X=(x1,x2)? Nosacījuma max(min)z=c1x1+c2x2 izpilde. Ja summas j ir ierobežotas no 1 līdz n (aij*xj)<=bj, x1, x2 >=0.

Katra no nevienādībām 2 nosaka pusplakni koordinātu plaknē, un nevienādību sistēma 2 un 3, ja tā ir saderīga, nosaka plakņu krustpunktu. Tā būs izliekta kopa, ko var attēlot kā:

1. Izliekts daudzstūris.

2. Izliekts neierobežots daudzstūra apgabals.

3.Segments.

5.Viens punkts.

6. Tukšs komplekts.

Mērķa funkcijas ģeometriskā interpretācija:

Z=C 1 X 1 + C 2 X 2 (1)

Fiksētām vērtībām Z=Z 0 definē līniju z0=c1x1+c2x.

Kad Z mainās, mēs iegūstam paralēlu taisnu līniju saimi, ko sauc par līmeņa līnijām.

Vektors C=(C 1, C 2) ar koordinātām x1 un x2 ir perpendikulārs katrai no līmeņa līnijām.

Vektors C parāda mērķa funkcijas lielākā pieauguma (samazinājuma) virzienus.

Ja vienā attēlā konstruējat vektora C iespējamo risinājumu apgabalu un vienu no līmeņa līnijām, piemēram, Z = 0, tad problēma tiek reducēta uz iespējamo risinājumu apgabala noteikšanu vektora C virziena punktam, caur kuru tiek sasniegts līmenis. iet līnija Z max(min), kas atbilst lielākajai (mazākai) funkcijas Z vērtībai. Ja problēma ir atrisināma, var rasties šādi gadījumi:

1. Problēmai ir unikāls risinājums.

2. Problēmai ir bezgalīgi daudz risinājumu (alternatīvais optimums).

3. Mērķa funkcija nav ierobežota, iespējamo risinājumu apgabals ir viens punkts (1. att.).

Vienkāršā metode

Sākotnējā atsauces plāna izveide

Apskatīsim 3 gadījumus.

1) Ļaujiet ierobežojumu sistēmai iegūt formu

X i + ij X j =b i , b i =>0,(i=1,m)

X 0 =(0,0,…,0,b i)

Kanoniskās lineārās programmēšanas problēmas ierobežojumam ir vēlamā forma, ja ar tā nenegatīvo pusi kreisajā pusē ir mainīgais, kas tiek ievadīts ar koeficientu, kas vienāds ar 1, bet pārējā pusē ir koeficients, kas vienāds ar 0. Ja katrs ierobežojums kanoniskās lineārās programmēšanas problēmai ir vēlamā forma, t.i. ierobežojumu sistēma tiek reducēta uz vienu nenegatīvu bāzi, tad sākotnējais atsauces plāns tiek konstruēts šādi: Vēlamie mainīgie tiek atlasīti kā pamata mainīgie, un visi pārējie ir brīvi.

Ij X j<=b i , b i >=0

Tiek ieviests papildu mainīgais ar koeficientu, kas vienāds ar 0

Ij X j +X n+1 =b i , b i >=0

X 0 =(0,…,0,b 1,...,b m)

Ij X j >=b i , b i >=0

Ij X j -X n+i =b i

Maks.(min)Z= j X j -(+)M i

Vienkāršas tabulas

Atsauces plāna optimāluma zīme. Maksimizācijas problēma

Ja kādam atsauces plānam visi aprēķini dj nav negatīvi, tad šāds plāns ir optimāls. Ja sākotnējā minimālā problēma un dj nav pozitīvi, tad šāds plāns ir optimāls.

Apskatīsim pāreju uz ne-sliktāko atsauces plānu, izmantojot LP problēmas piemēru pie max.

Ja indeksa rindā dj< 0, то план не оптимален и его можно улучшить. Среди отрицательных оценок находят максимальную по абсолютной величине.

Ja problēma ir minimāla, tad atrisināšanas kolonna Max|dj|=|dj 0 |

Mainīgais Xj 0 jāievada bāzē. Lai noteiktu no bāzes iegūto mainīgo, atrodiet attiecības: B i /A ij , A ij >0

Min = B i 0 /A i 0 j 0

Atļauju rindas un atļaujas kolonnas krustpunktā ir atļaujas elements.

1. Jaunās tabulas I 0 rindas elementi ir vienādi ar iepriekšējās tabulas atļauju rindas atbilstošajiem elementiem, kas dalīti ar atļaujas elementu.

2. Visi J 0 kolonnu elementi ir vienādi ar 0, izņemot izšķirošo elementu.

3. Visi pārējie jaunās tabulas elementi tiek aprēķināti saskaņā ar noteikumu: galvenās diagonāles reizinājums mīnus sekundārās diagonāles reizinājums, dalīts ar izšķirošo elementu.

Trīs pazīmes:

1. Alternatīvais optimums (optimālo plānu kopas bezgalības zīme). Ja pēdējās simpleksās tabulas indeksa rindā (kas satur optimālo plānu) ir vismaz viens nulles novērtējums, kas atbilst brīvam mainīgajam, tad LP problēmai ir bezgalīgs skaits optimālo plānu.

2. Mērķa funkcijas neierobežotības pazīme. Ja rezolūcijas ailē nav neviena pozitīva elementa, tad pieļaujamo plānu kopas mērķa funkcija nav ierobežota.

3. Ierobežojumu sistēmas nesaderības pazīme. Ja M-problēmas optimālajā plānā ne visi mākslīgie mainīgie ir vienādi ar 0, tad sākotnējās problēmas ierobežojumu sistēma ir nekonsekventa.

Duālās lineārās programmēšanas problēmas

Ar katru lineārās programmēšanas problēmu ir cieši saistīta vēl viena lineāra problēma, ko sauc par duālo problēmu. Sākotnējais uzdevums ir tiešs vai sākotnējais. Simetrisko dubulto LP problēmu pārim ir šāda forma:

Taisni - maxZ = Xj>=0

Dual minZ = Xj>=0

Divu problēmu pāri var interpretēt ekonomiski:

Tiešais – Cik daudz un kāda veida produktu Xj jāsaražo, lai, ņemot vērā ražošanas vienības izmaksas Cj, resursu Bi apjomus un patēriņa rādītājus Aij, tas maksimāli palielinātu produkcijas izlaidi vērtības izteiksmē.

Dual – kādai jābūt katra resursa vienības aplēsei, lai līdz minimumam samazinātu kopējo izmaksu tāmi visiem resursiem konkrētajam Bi Cj Aij.

Būvniecības noteikumi:

1. Sākotnējā uzdevuma ieraksts tiek organizēts, t.i. ja uzdevuma mērķa funkcija ir maksimizēta, tad nevienlīdzības ierobežojumiem jābūt > vai =(lai samazinātu< или =) Достигается умножением ограничений на -1.

2. Ja tiešā problēma ir atrisināta maksimāli, tad duālā problēma tiek atrisināta līdz minimumam.

3. Katrs tiešās problēmas ierobežojums atbilst duālās problēmas mainīgajam un otrādi.

4. Duālās problēmas ierobežojumu sistēmas matrica tiek iegūta no tiešās problēmas ierobežojumu sistēmas matricas, transponējot.

5. Tiešās problēmas ierobežojumu sistēmas brīvie termini ir tiešās problēmas mērķfunkcijas atbilstošo mainīgo koeficienti un otrādi.

6.Ja tiešās problēmas pārnešanai tiek uzlikts nenegatīvisma nosacījums, tad atbilstošo duālās problēmas ierobežojumu raksta kā nevienlīdzības ierobežojumu, ja nē, kā vienlīdzības ierobežojumu.

7. Ja kāds tiešās problēmas ierobežojums ir uzrakstīts kā vienādība, tad nenegatīvisma nosacījums netiek uzlikts atbilstošajam duālās problēmas mainīgajam.

Transporta uzdevums

Transporta problēmu izklāstīsim pēc izmaksu kritērija tabulas veidā

Tabulā norādīti piegādātāji A1..., kuriem noliktavā ir attiecīgi 1... viendabīgas kravas vienība. Šī krava jāpiegādā n patērētājiem, 1... vienību daudzumā, ņemot vērā ij kravas transportēšanas izmaksas no i piegādātāja j līdz patērētājam. Nepieciešams plānot transportēšanu (norādīt, cik kravas vienību jānosūta no I šī piegādātāja j patērētājam, lai maksimāli apmierinātu patērētāja pieprasījumu un lai transportēšanas kopējās izmaksas būtu minimālas).

c 1 – cena.

Problēmas, kurās kopējais preču piegādes apjoms no piegādātājiem ir vienāds ar kopējām vajadzībām, tiek sauktas par slēgtām.

I != Es – tad problēma ir atklāta.

Risinot transporta problēmas, svarīga ir teorēma par matricas rangu:

Transporta problēmas matricas rangs ir par 1 mazāks par vienādojumu skaitu (r=m+n-1).

Tas ir tas, cik daudz šūnu transporta problēmā ir jāaizņem X. Transporta problēmas risinājums tiek veikts, izmantojot vispārējā uzņemšana konsekventa plāna uzlabošana, kas ietver šādus posmus:

1. Sākotnējā atskaites plāna noteikšana.

2.Šā plāna izvērtēšana.

3. Pāreja uz nākamo plānu, vienreizēji aizstājot vienu no pamata mainīgajiem ar brīvu.

Ir dažādi veidi, kā īstenot transporta problēmas risināšanas posmus:

Ziemeļrietumu stūra noteikums

Minimālā elementa noteikums

Vogela metode4

Potenciālā metode

Potenciālā metode

Pāriesim pie optimāla transporta plāna sastādīšanas. Saskaņā ar šo atsauces plānu, kurā ir aizņemto šūnu skaits m+n-1. Katram piegādātājam un katram patērētājam tiek piešķirts skaitlis, ko sauc par potenciālu. Potenciāli tiek izvēlēti tā, lai to summa par katru ar kravu iekrauto kameru būtu vienāda ar kravas vienības pārvadāšanas tarifu. Tātad, ja šūna (I,k) ir pamata (aizņemta), tad u i +v k =C ik kur y ir piegādātāja kopējais potenciāls.

Pēc tam mēs aprēķinām brīvo šūnu aprēķinus, izmantojot formulu: S ij =C ij -(U i +V j)

Ja brīvām šūnām visi S ij aprēķini ir lielāki vai vienādi ar 0, tad iegūtais transportēšanas plāns ir optimāls. Ja ir vismaz viens novērtējums S ij< 0 число базисных вводят в клетку, для которой оценка S ij минимальной. Для такой клетки строится цикл и производится перемещение груза так, чтобы баланс цикла сохранялся.

U 3 =
Aizpildītā šūnā tarifs ir vienāds ar potenciālu summu

F=320+150+140+150+1020+120=1900

Tiek saukta metode, kurā viena no savstarpēji duālām problēmām vispirms tiek atrisināta ar simpleksa metodi, bet pēc tam tiek atrasts otras problēmas optimālais un optimālais risinājums, izmantojot dualitātes teorēmas. duālā vienkāršā metode.

1. teorēma (pirmā dualitātes teorēma). Ja vienai no savstarpēji duālām problēmām ir optimāls risinājums, tad arī ir

citu, un to mērķa funkciju optimālās vērtības ir vienādas ar:

Ja sākotnējās problēmas mērķa funkcija ir neierobežota, tad duālās problēmas ierobežojumu sistēma ir nekonsekventa.

Piezīme: pirmās dualitātes teorēmas otrās daļas apvērstais nav patiess vispārējā gadījumā.

2. teorēma. Duālās problēmas optimālā plāna sastāvdaļas ( kam ir nenegatīvisma nosacījums) ir vienādi koeficientu absolūtās vērtības

Duālās problēmas optimālā plāna sastāvdaļas ( nav ierobežots ar zīmi) ir vienādi koeficientu vērtības ar atbilstošiem sākotnējās problēmas mērķa funkcijas mainīgajiem, kas izteikti tās brīvo mainīgo izteiksmē optimāls risinājums.

3. teorēma. Pozitīvas (ne nulles) vienas problēmas optimālā risinājuma komponentes simetrisks dubultpāris atbilst citas problēmas optimālā risinājuma nulles komponentēm, t.i. jebkuram un:

4. teorēma (trešā dualitātes teorēma). Duālās problēmas optimālā dizaina komponenti ir vienādi ar lineārās funkcijas daļējo atvasinājumu vērtībām pēc atbilstošajiem argumentiem, t.i.

. (7.2)

Trešās dualitātes teorēmas ekonomiskā interpretācija: duālās problēmas optimālā plāna komponentes parāda, par cik naudas vienībām mainīsies maksimālā peļņa (ieņēmumi) no produkcijas realizācijas, mainoties attiecīgā resursa krājumam par vienu vienību.

Piemērs 9.1. Balstoties uz 5.2. piemēra risinājumu (datne “Simpleksās metodes algoritms un piemēri”), mēs izmantosim duālās simpleksa metodi, lai noteiktu optimālo duālās problēmas risinājumu.

Šis dubultais pāris ir simetrisks. Problēmas ir uzrakstītas standarta formā, reducēsim tās līdz kanoniskajai formai:

Nodibināsim atbilstību starp savstarpēji duālu problēmu mainīgajiem.

Pamatojoties uz 5.2. piemēra risinājumu. Pēdējās iterācijas vienkāršā tabula (5.10. tabula) izskatās šādi:

9.3. tabula

Saskaņā ar 2. teorēmu mainīgo lielumu un optimālās vērtības būs vienādas ar sākotnējās problēmas mērķa funkcijas atbilstošo mainīgo koeficientu absolūtajām vērtībām, kas izteiktas ar tā optimālā risinājuma brīvajiem mainīgajiem.

Izmantojot 9.3. tabulu, mēs izrakstām sākotnējās problēmas mērķa funkciju, kas izteikta ar tās optimālā risinājuma brīvajiem mainīgajiem:

Līdz ar to, , .

Mērķa funkcijā mainīgie , un nav (t.i., to koeficienti ir vienādi ar nulli), tāpēc atbilstošo mainīgo , un optimālās vērtības ir vienādas ar nulli.

Saskaņā ar 1. teorēmu, .

Tādējādi mērķa funkcijas optimālā vērtība, kas tiek sasniegta pie .

Piemērs 9.2. Pamatojoties uz sākotnējās problēmas risinājumu, atrodiet optimālo duālās problēmas risinājumu, izmantojot duālās vienkāršās metodes metodi.

Šis dubultais pāris ir asimetrisks. Novedīsim duālo problēmu kanoniskā formā.

Lai noteiktu atbilstību starp duālā pāra mainīgajiem, sākotnējā problēmā mēs ieviešam divus trūkstošus fiktīvus mainīgos.

Nodibināsim atbilstību starp savstarpēji duālu problēmu mainīgajiem.

9.4. tabula

Duālā pāra atbilstības mainīgie

Atrisināsim sākotnējo problēmu, izmantojot simplekso metodi.

Izmantojot Jordan-Gauss metodi, sākotnējās problēmas ierobežojumu sistēmā atlasām mainīgos un ( Piezīme: neizmantojiet fiktīvus mainīgos kā pamata mainīgos).

Pārveidojumu rezultātā iegūstam šādu koeficientu matricu:

.

Sākotnējās problēmas ierobežojumu sistēmai būs šāda forma:

Izteiksim galvenos mainīgos kā brīvus, kā rezultātā sākotnējā problēma būs šāda:

Aizstājot iegūtās pamata mainīgo vērtības mērķa funkcijā, tas izpaudīsies šādā formā:

Atrisinot pārveidoto sākotnējo problēmu, izmantojot simpleksa metodi pēdējā iterācijā, mēs iegūstam šādu simpleksa tabulu:

9.5. tabula

Sākotnējās problēmas optimālā risinājuma vienkāršā tabula

Ir izklāstīti dubultuzdevumu sastādīšanas noteikumi. Tiek ņemti vērā simetriski, asimetriskie un jaukti pāri. Tiek analizēti duālo problēmu sastādīšanas piemēri.

Duālās jeb konjugētās lineārās programmēšanas uzdevumiem ir īpašība, ka no vienas problēmas risinājuma var iegūt citas problēmas risinājumu. Šeit mēs apskatīsim duālu uzdevumu sastādīšanas noteikumus.

Simetriska dubultproblēma

Apsveriet lineāras programmēšanas problēmu ar nenegatīviem mainīgajiem un šādas formas ierobežojumu sistēmas nevienādībām:
(1.1) ;
(1.2)
Šeit ir daži skaitļi. Visas sistēmas rindas (1.2) ir zīmētas nevienādības.

(2.1) ;
(2.2)
Šeit visas sistēmas (2.2) rindas ir zīmētas nevienādības. Ierobežojumu sistēmas (2.2.) koeficientu matrica ir sistēmas (1.2.) transponētā matrica. Tajā ir rindas un kolonnas. Duālajai problēmai ir mainīgie. Visi mainīgie nav negatīvi.

Sākotnējo problēmu (1) bieži sauc par tiešo problēmu, un problēmu (2) sauc par duālo problēmu. Ja mēs pieņemam problēmu (2) kā sākotnējo, tad problēma (2) būs tieša problēma, un problēma (1) būs duāla. Problēma (1) un (2) tiek sauktas par simetriskām duālām problēmām.

Tādējādi simetrisku duālu problēmu var sastādīt tikai tad, ja visi sākotnējās problēmas mainīgie ir nenegatīvi un ierobežojumu sistēma nesatur vienādības. Ja tiek meklēts mērķfunkcijas maksimums, tad nevienādības jāpārvērš formā . Ja tiek meklēts minimums, tad nevienādības jāpārvērš formā . Lai mainītu zīmi, abas nevienlīdzības puses jāreizina ar -1 .

Simetriskas duālas problēmas sastādīšanas piemērs

;

Sākotnējā problēma ir minimuma atrašanas problēma. Tāpēc visām nevienlīdzībām ir jābūt zīmēm. Pirmā un trešā nevienādība satur zīmi. Sareizināsim tos ar -1 :

Transponēsim šo matricu. Tas ir, mēs rakstīsim pirmo rindu kā pirmo kolonnu, mēs rakstīsim otro rindu kā otro kolonnu, un mēs rakstīsim trešo rindu kā trešo kolonnu.

Divkāršajai problēmai ir šāda forma:
;

;

Asimetriska duāla problēma

Maksimālais izaicinājums

Apsveriet kanoniskās maksimālās lineārās programmēšanas problēmu ar nenegatīviem mainīgajiem un ierobežojumu sistēmas vienādībām:
(3.1) ;
(3.2)
Šeit ir daži skaitļi. Visas sistēmas rindas (3.2) ir vienādības. Visi mainīgie nav negatīvi.

Divkāršajai problēmai ir šāda forma:
(4.1) ;
(4.2)
Šeit visas sistēmas (4.2) rindas ir zīmētas nevienādības. Ierobežojumu sistēmas (4.2.) koeficientu matrica ir sistēmas (3.2.) transponētā matrica. Duālajai problēmai ir mainīgie. Mainīgie lielumi var būt gan pozitīvi, gan negatīvi.

Atšķirība starp asimetrisko uzdevumu pāri (3) un (4) no simetriskā pāra (1) un (2) ir tāda, ka ierobežojumu sistēma (3.2) satur tikai vienādības, un sistēmā (4.2) nav nosacījumu. mainīgo lielumu nenegatīvumam.

Minimālais uzdevums

Tagad apsveriet kanoniskās minimālās lineārās programmēšanas problēmu:
(5.1) ;
(5.2)

Divkāršajai problēmai ir šāda forma:
(6.1) ;
(6.2)

Ierobežojumu sistēma (6.2) atšķiras no (4.2) ar to, ka nevienādībām ir zīmes.

Saistība ar simetrisku duālo problēmu pāri

Parādīsim, ka no simetriska pāra (1)-(2) var iegūt asimetrisku uzdevumu pāri (3)-(4).

Tātad, pieņemsim, ka mums ir tieša problēma ar mērķa funkciju
(3.1)
un ierobežojumu sistēma
(3.2)
Katru vienlīdzību var attēlot ar divām nevienādībām:

Mēs reizinām nevienādības ar zīmēm ar -1 :

Ierobežojumu sistēmā ir nevienlīdzība.

Izmantojot formulas (1)-(2), iegūstam dubultu uzdevumu:
;


duālajai problēmai ir nenegatīvi mainīgie:
.
Ir viegli redzēt, ka šie mainīgie iekļūst problēmā atšķirību veidā
.

Veiksim aizvietotājus
.
Kopš un , mainīgie var būt pozitīvi vai negatīvi.

Un mēs iegūstam dubultu problēmu (4):
(4.1) ;
(4.2)

Ja par sākotnējo uzdevumu ņemam (4), tad, veicot visas darbības apgrieztā secībā, iegūstam duālo uzdevumu (3).

Izmantojot to pašu metodi, var iegūt dubultu uzdevumu (6) no uzdevuma (5) un dubultu uzdevumu (5) no uzdevuma (6).

Jaukta problēma

Tagad aplūkosim jauktu problēmu.

Pieņemsim tiešu problēmu (1) maksimumam, kura ierobežojumu sistēmā rinda ir vienādība. Tad duālajai problēmai ir forma (2) ar vienu izņēmumu - mainīgais var būt pozitīvs vai negatīvs. Tas ir, ierobežojumu nav.

Tas pats notiks, ja mums ir tieša problēma (2) minimumam, kura ierobežojumu sistēmā rinda ir vienādība. Duālajai problēmai ir forma (1) ar vienu izņēmumu - mainīgais var būt ar jebkuru zīmi.

Tagad mums ir tieša problēma (1) maksimāli, bet nav nekādu ierobežojumu. Tas nozīmē, ka mainīgais var būt pozitīvs vai negatīvs. Tad duālajai problēmai ir forma (2) ar vienu izņēmumu - ierobežojumu sistēmas rinda ir vienādība.

Un visbeidzot, lai mums būtu tieša problēma (2) par minimumu, bet nav nekādu ierobežojumu . Tad duālajai problēmai ir forma (1) ar vienu izņēmumu - ierobežojumu sistēmas rinda ir vienādība.

Tas viss ļauj formulēt noteikumus duālu problēmu sastādīšanai.

Duālu uzdevumu sastādīšanas noteikumi

1. Sākotnējai maksimālajai problēmai mēs samazinām visas ierobežojumu sistēmas nevienlīdzības līdz formai:
.
Sākotnējai minimālajai problēmai mēs samazinām visas nevienlīdzības līdz formai:
.
Ja jums ir jāmaina zīme, reiziniet abas nevienādības puses ar -1 .
2. Mēs veidojam duālu problēmu tāpat kā simetrisku problēmu pāri.
3. Ja sākotnējā uzdevumā ierobežojumu sistēmas rinda ir vienādība, tad izsvītrojam duālās problēmas th mainīgā nenegatīvuma nosacījumu.
4. Ja sākotnējā uzdevumā th mainīgajam nav nenegatīvisma nosacījuma, tad duālā uzdevuma rindā nevienlīdzības zīmi mainām uz vienādības zīmi.

Jauktas duālas problēmas sastādīšanas piemērs

Ņemot vērā lineārās programmēšanas problēmu:
;

Izveidojiet dubultu problēmu.

Mērķa funkcijai ir brīvs termins 5. Lai to sakārtotu formā (2.1), mēs ievadām mainīgo un pievienojam vienādību . Tad problēmai būs šāda forma:

;

Šī problēma ir minimuma atrašanas problēma. Tāpēc visām nevienlīdzībām ir jābūt zīmēm. Trešā nevienlīdzība satur zīmi. Tāpēc reizināsim to ar -1 :

Pārrakstīsim ierobežojumu sistēmu, skaidri norādot mainīgo koeficientus:

Ierobežojumu sistēmas koeficientu matricai ir šāda forma:

Transponēsim šo matricu. Tas ir, pirmo rindu rakstīsim kā pirmo kolonnu, otro rindu rakstīsim kā otro kolonnu un tā tālāk.

Izveidosim duālu problēmu kā simetriskajam pārim.
;

Tā kā sākotnējā uzdevumā ierobežojumu sistēmas 1., 2. un 4. rinda ir vienādības, tad duālajā uzdevumā mainīgajiem , un var būt jebkura zīme. Vienīgais nenegatīvais mainīgais ir . Tāpēc mainīgo lielumu nenegatīvisma nosacījumiem ir šāda forma:
.

Tā kā sākotnējā uzdevumā mainīgajiem un var būt patvaļīgas zīmes, tad duālās problēmas ierobežojumu sistēmas 3. un 4. rinda ir vienādības.

Tādējādi duālajai problēmai ir šāda forma:
;

No ceturtā vienādojuma. Aizstāt mainīgo ar tā vērtību un reiziniet trešo rindiņu ar -1 .

Simpleksā metode ir universāla. Ar tās palīdzību var atrisināt jebkuru lineārās programmēšanas problēmu. Tomēr tā daudzpusības dēļ tas nav brīvs no dažiem trūkumiem. Dažos gadījumos lineārās programmēšanas problēmu risināšanai piemērotāka ir tā sauktā duālā metode. Šīs metodes pamatā ir dualitātes teorija, kas ir viena no svarīgākajām lineārās programmēšanas vispārējās teorijas sastāvdaļām.

Dualitātes teorija tiek izmantota, lai izstrādātu metodes daudzu praktiski svarīgu lineārās optimizācijas uzdevumu klašu risināšanai: transporta tipa uzdevumi, lineāri veseli skaitļi u.c. Apskatīsim šīs teorijas galvenos noteikumus.

Katra lineārās programmēšanas problēma atbilst citai problēmai, savā ziņā tai pretējai. Ja pirmo problēmu sauc par tiešo, tad pretējo sauc par duālo. Tā kā duālās problēmas duālā problēma ir sākotnējā tiešā problēma, nav svarīgi, kuru problēmu sauc par tiešo un kuru duālo. Tāpēc tiešās un duālās problēmas sauc par divu pāru problēmām.

Duālā problēma tiek formulēta tieši no tiešās, izmantojot noteiktus noteikumus. Tā kā tiešajām problēmām var būt ierobežojumi tipa, veida vai vienādību formā, dubultproblēmu iegūšanas noteikumi tām izrādās atšķirīgi.

Ir simetriskas, asimetriskas un jauktas duālas problēmas. Simetrisko problēmu gadījumā tiešās problēmas ierobežojumiem ir forma . Asimetriskās problēmas ierobežojumos tiešās problēmas ierobežojumi izmanto vienādības zīmes. Jauktās problēmās tiek izmantotas abu veidu attiecības “mazāks vai vienāds ar” un “vienāds”. Asimetriskajās un jauktajās problēmās jaunizveidotajiem mainīgajiem netiek izvirzīta to nenegatīvuma prasība.

Aprēķini, kuru pamatā ir dualitātes attiecības, sākas, reducējot tiešās un duālās problēmas līdz standarta formai. Tāpēc mēs varam aprobežoties ar noteikumu formulēšanu tādas problēmas veidošanai, kas ir dubultā standarta lineārās programmēšanas problēmai. Noteikumus duālās problēmas iegūšanai cita veida LP problēmām var iegūt no šiem noteikumiem.

Uzrakstīsim LP problēmu standarta formā:

,

,

i=1,..,m; j=1,...,n.

Sauksim šo problēmu par tiešu. Tad uzdevums saistībā ar to būs divkāršs:

,

i=1,..,m; j=1,...,n.

Pēc uzdevumu analīzes varam izdarīt šādus secinājumus:

1. Katrs tiešās problēmas ierobežojums atbilst duālās problēmas mainīgajam.

2. Katrs tiešās problēmas mainīgais atbilst duālās problēmas ierobežojumam.

3. Jebkura mainīgā koeficienti tiešās problēmas ierobežojumos kļūst par duālās problēmas ierobežojuma koeficientiem, kas atbilst šim mainīgajam, un ģenerētā ierobežojuma labā puse ir vienāda ar šī mainīgā koeficienta izteiksmē. mērķa funkcija.

4. Duālās problēmas ekstrēma veids ir pretējs tiešās problēmas galējības veidam;

5. Vektori B un C tiešajā un duālajā uzdevumā maina vietas;

6. Matrica A duālā problēma tiek iegūta, transponējot matricu A tiešais uzdevums;

7. Visiem duālās problēmas ierobežojumiem ir forma maksimizācijas uzdevumam un forma lineārās formas minimizēšanas uzdevumam.

Simetriskas duālas problēmas gadījumā:

Asimetriskas problēmas gadījumā:

Divkāršajai problēmai ir šāda forma:

Jauktās problēmas satur ierobežojumus vienlīdzības un nevienlīdzības veidā. Sastādot duālo problēmu, ir jāizmanto pārejas noteikumi simetriskām un asimetriskām problēmām.

Tālāk sniegtie piemēri ir paredzēti, lai ilustrētu dubultproblēmu iegūšanas noteikumus.

Piemērs Tiek dota lineāra programmēšanas problēma (pa kreisi no katra ierobežojuma ir ar to saistītais dubultais mainīgais). Šī problēma ir asimetriska.

,

Formulēsim šai problēmai dubultu problēmu. Duālās problēmas mērķfunkcija ir lineāra forma, kas iegūta kā vektora b=(10,20,60,80) reizinājums ar duālās problēmas Y =( ). Turklāt, tā kā tiešajā uzdevumā mērķa funkcija ir maksimizēta, duālajā uzdevumā tā tiek samazināta līdz minimumam. Ņemot vērā izteiktos komentārus, mēs iegūstam

Duālās problēmas pirmā ierobežojuma kreisā puse ir tiešās problēmas ierobežojumu sistēmas vektora reizinājums, kas saistīts ar mainīgo , un duālās problēmas mainīgo lielumu vektors. Šī ierobežojuma labā puse ir vienāda ar mainīgā koeficientu tiešās problēmas mērķa funkcijā.

Un tā kā turklāt tiešā problēma ir maksimuma atrašanas problēma, pirmajam ierobežojumam ir šāda forma:

Līdzīgi spriežot, mēs iegūstam duālās problēmas otro ierobežojumu: . Mainīgā neesamība šajā ierobežojumā ir saistīta ar faktu, ka tiešās problēmas otrajā ierobežojumā nav mainīgā.

Mainīgais, kas saistīts ar duālās problēmas trešo mainīgo, parādās tikai tiešās problēmas pirmajā ierobežojumā. Šī iemesla dēļ mēs iegūstam trešo ierobežojumu . Spriežot pēc analoģijas, mēs iegūstam ceturto, piekto un sesto ierobežojumu: .

Tādējādi, neskatoties uz to, ka nenegatīvisma nosacījums nebija īpaši uzlikts duālās problēmas mainīgajiem lielumiem, tas tomēr izrādījās izpildīts visiem.

Piemērs Dota lineārās programmēšanas problēma nestandarta formā

,

,

,

Neierobežota zīme .

Rakstīsim šo problēmu standarta formā. Lai to izdarītu, mainīsim mainīgos , ieviesīsim otrajā ierobežojumā lieku mainīgo, bet trešajā – papildu mainīgo. Mēs saņemam

,

.

Formulēsim duālu problēmu. Tā kā tiešajā uzdevumā mērķa funkcija ir samazināta līdz minimumam, duālās problēmas objektīvajai funkcijai ir forma .

Tā paša iemesla dēļ duālās problēmas pirmais, otrais un trešais ierobežojums, kas attiecīgi saistīti ar mainīgajiem ir rakstīti šādi:

,

Tā kā mainīgais parādās tikai tiešās problēmas otrajā vienādojumā un mainīgais tikai trešajā vienādojumā, duālās problēmas saistītie ierobežojumi ir:

.

Tādējādi no trim duālās problēmas mainīgajiem viens izrādījās neierobežots zīmē.

Izmantojot dualitātes teorēmas, zinot vienas problēmas risinājumu, var atrast optimālo risinājumu otrai, to neatrisinot.

Apskatīsim jauktu problēmu.

Divkāršajai problēmai būs šāda forma:

Ja mēs izmantojam lineārās programmēšanas problēmas kanonisko formu, tad mums ir darīšana ar asimetriskas lineārās programmēšanas problēmu.

Problēmas kanoniskā forma ir šāda:

Dubultā problēma izskatīsies šādi:

Teorēma 1. Jebkuram tiešās un duālās problēmas iespējamu risinājumu pārim mērķfunkcijas vērtība maksimizēšanas uzdevumā nepārsniedz mērķa funkcijas vērtību minimizēšanas uzdevumā.

Šīs teorēmas praktiskā vērtība ir šāda. Praksē dažreiz ir labāk iegūt risinājumu tuvu optimālajam, bet īsā laikā, nekā iegūt optimālu risinājumu, bet ievērojami ilgākā laikā. Šajā gadījumā pēdējā nevienādība var kalpot kā aplēse par risinājuma tuvumu, kas iegūts nākamajā iterācijā līdz optimālajam.

2. teorēma. Ja vienai no duālajām problēmām ir optimāls risinājums, tad arī otrai ir optimāls risinājums, un mērķfunkciju vērtības abiem risinājumiem sakrīt. Ja vienai no duālajām problēmām ir neierobežota mērķa funkcija, tad otra ir neatrisināma, tas ir, tai nav reālu risinājumu.

Teorēma. Lai pieļaujamie risinājumi būtu optimāli, ir nepieciešams un pietiekami, lai tie atbilstu vienādojumu sistēmai

.

Šī teorēma nozīmē, ka jebkura uzdevuma viens no mainīgajiem ir stingri lielāks par nulli, tad otras duālās problēmas atbilstošais ierobežojums tiek izpildīts kā stingra vienādība, un otrādi, ja ar optimālu risinājumu jebkurš ierobežojums tiek izpildīts kā stingra nevienādība. , tad atbilstošais mainīgais optimālajā risinājumā ir nulle.

Piemērs Atrisināsim simetrisko uzdevumu. Ļaujiet sākotnējai problēmai iegūt formu

Atrisinot problēmu grafiski, mēs iegūstam

Izveidosim tam dubultu problēmu

Tātad mērķa funkcijas optimālajā punktā ir vienādas

Tā kā mainīgie
, tad atbilstošie ierobežojumi duālajā uzdevumā satur vienādības zīmi. Šiem ierobežojumiem ir forma

Aizstāsim vērtības ar ierobežojumiem . Mēs saņemam

.

Šajā sistēmā stingra ir tikai pirmā nevienlīdzība. Tāpēc . Mēs atradīsim citas mainīgo vērtības no vienādojumu sistēmas

.

Šīs lineārās sistēmas risināšanas rezultātā algebriskie vienādojumi, saņemam

Atrisināsim to pašu problēmu, taču pieņemsim, ka risinājums ir zināms

Tā kā otrais un trešais mainīgais ir stingri lielāks par nulli, attiecīgais ierobežojums tiek izpildīts kā stingra vienlīdzība.

.

Atrisinot šo vienādojumu sistēmu, mēs iegūstam

Ja sākotnējo uzdevumu risina ar simpleksa metodi un koeficientus iegūst gala mērķa funkcijā - matricā - koeficientu rindā, tad duālā uzdevuma risinājumu var atrast, izmantojot formulu kur ir koeficientu matrica mērķa funkcijas pamata mainīgajiem sākotnējās problēmas optimālajā risinājumā.

Apskatīsim duālās problēmas ekonomisko interpretāciju.

Teorēma. Mainīgo vērtības dubultās problēmas optimālajā risinājumā atspoguļo sākotnējās problēmas ierobežojumu brīvo nosacījumu ietekmes aplēses uz tās mērķa funkcijas optimālo vērtību. Jo

Tad duālie mainīgie parāda, kā mērķa funkcija mainās, ja resurss mainās par vienu