TĒMA: LINEĀRĀ PROGRAMMĒŠANA

UZDEVUMS 2.A. Lineārās programmēšanas problēmas risināšana grafiskā metode

Uzmanību!

Šī ir darba Nr.2073 IZMĒĢINĀJUMA VERSIJA, oriģināla cena ir 200 rubļi. Projektēts iekšā Microsoft programma Vārds.

Maksājums. Kontakti.

7. iespēja. Atrodiet maksimālo un minimālo vērtībulineārā funkcijaФ = 2x1 - 2x2ar ierobežojumiem: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Risinājums:

Nosacīti aizvietojot nevienlīdzības zīmes ar vienādības zīmēm, iegūstam vienādojumu sistēmu x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2x2 = 10.

Konstruēsim taisnes, izmantojot šos vienādojumus, pēc tam atbilstoši nevienādību zīmēm izvēlamies pusplaknes un iegūstam to kopīgo daļu - ODR pieļaujamo atrisinājumu apgabalu - četrstūri MNPQ.

Minimālā funkcijas vērtība

cijas - punktā M(2; 2)

Ф min = 2 · 2 - 2 · 2 = 0.

Maksimālā vērtība tiek sasniegta punktā N (10; 0),

Ф max = 2 · 10 - 2 · 0 = 20.

8. iespēja. Atrodiet maksimālo un minimālo vērtību

lineārā funkcija Ф = x 1 + x 2

ar ierobežojumiem: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Risinājums:

Nosacīti aizvietojot nevienlīdzības zīmes ar vienādības zīmēm, iegūstam vienādojumu sistēmu x1 - 4 x2 = 4 ;

3 x1 - x2 = 0;

Konstruēsim taisnes, izmantojot šos vienādojumus, pēc tam atbilstoši nevienādību zīmēm izvēlamies pusplaknes un iegūstam to kopīgo daļu - ODR pieļaujamo atrisinājumu apgabalu - neierobežotu daudzstūri MNPQ.

Minimālā funkcijas vērtība

piemēram, tiešā NP

punktā P(4; 0)

Ф min = 4 + 0 = 4.

ODR no augšas nav ierobežots, tāpēc Ф max = + ∞.

10. iespēja. Atrodiet maksimālo un minimālo vērtību

lineārā funkcija Ф = 2 x 1 - 3 x 2

ar ierobežojumiem: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1,2.

Nosacīti aizstājot nevienlīdzības zīmes ar vienādības zīmēm, iegūstam vienādojumu sistēmu

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Konstruēsim taisnes, izmantojot šos vienādojumus, pēc tam atbilstoši nevienādību zīmēm atlasīsim pusplaknes un iegūstam to kopīgo daļu - ODR pieļaujamo atrisinājumu apgabalu - MNPQRS daudzstūri.

Konstruēsim vektoru Г(2; -3) un zīmēsim cauri koordinātu sākumpunktam līmeņa līnija- taisni.

Pārvietojam līmeņa līniju virzienā, Ф vērtība palielinās. Punktā S(7; 0) mērķa funkcija sasniedz maksimumu Ф max =2·7–3·0= = 14. Pārvietojam līmeņa līniju virzienā, Ф vērtība samazinās. Funkcijas minimālā vērtība ir punktā N(0; 5)

Ф min = 2·0 – 3·5 = –15.

UZDEVUMS 2.B. Lineārās programmēšanas problēmas risināšana

analītiskā simpleksa metode

7. iespēja. Samaziniet mērķa funkciju Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

ar ierobežojumiem: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Risinājums:

Nezināmo skaits n=6, vienādojumu skaits m=3. Tāpēc r = n-m = 3 nezināmie var tikt uzskatīti par brīviem. Izvēlēsimies x 1, x 3 un x 6.

Mēs izsakām pamata mainīgos x 2 , x 4 un x 5 kā brīvos un reducējam sistēmu uz vienības pamata

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 - x 1 - 6 x 6 (*)

x 5 = 6 - x 1 - 2 x 3 - 2 x 6

Mērķa funkcija izskatīsies šādi:

Ф = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

Uzliksim x 1 = x 3 = x 6 = 0, un pamata mainīgie ņems vērtības x 2 = 2; x 4 = 9; x 5 = 6, tas ir, pirmais iespējamais risinājums (0; 2; 0; 9; 6; 0), mērķa funkcija Ф 1 = 13.

Mainīgie lielumi x 3 un x 6 ir iekļauti mērķa funkcijā ar negatīviem koeficientiem, tāpēc, to vērtībām palielinoties, Ф vērtība samazināsies. Ņemsim, piemēram, x 6. No sistēmas 1. vienādojuma (*) ir skaidrs, ka x 6 vērtības palielinājums ir iespējams līdz x 6 = 1 (kamēr x 2 ³ 0). Šajā gadījumā x 1 un x 3 paliek vienādi ar nulli. Tagad mēs ņemam x 4, x 5, x 6 kā pamata mainīgos un x 1, x 2, x 3 kā brīvos mainīgos. Izteiksim jaunos pamata mainīgos jauno brīvo mainīgo izteiksmē. Mēs saņemam

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

Ф = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Piešķirsim brīvajiem mainīgajiem nulles vērtības, tas ir, x 1 = x 2 = x 3 = 0, savukārt x 6 = 1, x 4 = 3, x 5 = 4, tas ir, trešais iespējamais risinājums (0 0; 4; Šajā gadījumā Ф 3 = 6.

Mainīgais x 3 ir iekļauts mērķa funkcijā ar negatīvu koeficientu, tāpēc x 3 pieaugums attiecībā pret nulles vērtību novedīs pie F samazināšanās. No 2. vienādojuma ir skaidrs, ka x 3 var palielināties līdz 1/4 , no 3. vienādojuma - uz 2/3 . Otrais vienādojums ir kritiskāks. Pārveidosim mainīgo x 3 par pamata skaitu un x 4 par brīvo skaitu.

Tagad mēs ņemam x 1, x 2 un x 4 kā jaunus brīvos mainīgos. Izteiksim caur tiem jaunos pamata mainīgos x 3, x 5, x 6. Iegūsim sistēmu

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Mērķa funkcijai būs forma

Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Mainīgie lielumi x 1 un x 2 ir iekļauti mērķa funkcijā ar negatīviem koeficientiem, tāpēc, to vērtībām palielinoties, Ф vērtība samazināsies. Ņemsim, piemēram, x 2. No sistēmas 2. vienādojuma ir skaidrs, ka x 2 vērtības palielinājums ir iespējams līdz x 2 = 5 (kamēr x 5 ³ 0). Šajā gadījumā x 1 un x 4 paliek nulle, citu mainīgo vērtības ir vienādas ar x 3 = 3/2; x 5 = 0, x 6 = 3/2, tas ir, ceturtais iespējamais risinājums (0; 5; 3/2; 0; 0; 3/2). Šajā gadījumā Ф 4 = 5/4.

Tagad mēs ņemam x 1, x 4 un x 5 kā jaunus brīvos mainīgos. Izteiksim caur tiem jaunos pamata mainīgos x 2, x 3, x 6. Iegūsim sistēmu

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Mērķa funkcijai būs forma

Ф = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Koeficienti abiem mainīgajiem Ф izteiksmē ir pozitīvi, tāpēc turpmāka Ф vērtības samazināšanās nav iespējama.

Tas ir, minimālā vērtība Ф min = - 5, pēdējais iespējamais risinājums (0; 5; 3/2; 0; 0; 3/2) ir optimāls.

8. variants. Maksimizējiet mērķa funkciju Ф = 4 x 5 + 2 x 6

ar ierobežojumiem: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Risinājums:

Vienādojumu skaits ir 4, nezināmo ir 6. Līdz ar to r = n – m = 6 – 4 = 2 mainīgie var tikt izvēlēti kā brīvie mainīgie, 4 mainīgie kā pamata. Mēs izvēlamies x 5 un x 6 kā brīvus, un x 1 , x 2 , x 3 , x 4 kā pamata. Izteiksim pamatmainīgos ar brīvajiem un reducēsim vienādojumu sistēmu uz vienības bāzi

x 1 = 12 - x 5 - x 6;

x 2 = 30 - 5 x 5 + x 6;

x 3 = 6 - x 5 + 2 x 6;

x 4 = 9 - 3/2 x 5 + x 6;

Mērķa funkciju rakstām formā Ф = 4 x 5 + 2 x 6. Piešķirsim nulles vērtības brīvajiem mainīgajiem x 5 = x 6 = 0. Šajā gadījumā pamata mainīgie saņems vērtības x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , tas ir, mēs iegūstam pirmo iespējamo risinājumu (12, 30 , 6, 9, 0,) un Ф 1 = 0.

Abi brīvie mainīgie ievada mērķa funkciju ar pozitīviem koeficientiem, tas ir, ir iespējama tālāka F palielināšana. Pārveidosim, piemēram, x 6 par pamatu skaitu. No (1) vienādojuma ir skaidrs, ka x 1 = 0 pie x 5 = 12, (2) ÷ (4) x 6 ir iekļauts ar pozitīviem koeficientiem. Pāriesim uz jaunu pamatu: pamata mainīgie - x 6, x 2, x 3, x 4, brīvie - x 1, x 5. Izteiksim jaunos pamata mainīgos jaunos brīvos

x 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 x 5;

x 3 = 30 - 2 x 1 - 3 x 5;

x 4 = 21 - x 1 - 5/2 x 5;

Mērķa funkcija būs Ф = 24 - 2 x 1 + 2 x 5 ;

Piešķirsim nulles vērtības brīvajiem mainīgajiem x 1 = x 5 = 0. Šajā gadījumā pamata mainīgie pieņems vērtības x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , tas ir, mēs iegūstam otro iespējamo risinājumu (0, 42 , 30, 21, 0, 12) un Ф 2 = 24.

Mērķa funkcija x 5 ir iekļauta ar pozitīvu koeficientu, tas ir, ir iespējama turpmāka F palielināšana. Pārejam uz jaunu pamatu: pamata mainīgie - x 6, x 5, x 3, x 4, brīvie - x 1. , x 2. Izteiksim jaunos pamata mainīgos caur new free

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2;

x 3 = 9 - 3/2 x 1 + 1/2 x 2;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5 ;

Mērķa funkcija būs formā Ф = 38 – 7/2 x 1 – 1/3 x 2 ;

Piešķirsim nulles vērtības brīvajiem mainīgajiem x 1 = x 2 = 0. Šajā gadījumā pamata mainīgajiem būs vērtības x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 /2, tas ir, iegūstam trešo iespējamo risinājumu X 3 = (0, 0, 9, 7/2, 7, 5) un Ф 3 = 38.

Abi mainīgie ieiet mērķa funkcijā ar negatīviem koeficientiem, tas ir, turpmāks Ф pieaugums nav iespējams.

Tāpēc pēdējais iespējamais risinājums ir optimāls, tas ir, X opt = (0, 0, 9, 7/2, 7, 5) un Ф max = 38.

10. variants. Maksimizējiet mērķa funkciju Ф = x 2 + x 3

ar ierobežojumiem: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Risinājums:

Vienādojumu-ierobežojumu sistēma ir konsekventa, jo vienādojumu sistēmas matricas un paplašinātās matricas rindas ir vienādas un vienādas ar 2. Līdz ar to divus mainīgos var uzskatīt par brīviem, pārējos divus mainīgos - pamata. jāizsaka lineāri caur diviem brīviem.

Ņemsim x 2 un x 3 kā brīvos mainīgos. Tad pamata mainīgie būs x 1 un x 2, ko izteiksim brīvā izteiksmē

x 1 = 1 + x 2 - x 3; (*)

x 4 = 2 - x 2 + 2 x 3;

Mērķa funkcija jau ir izteikta ar x 2 un x 3, tas ir, Ф = x 2 + x 3.

Ja x 2 =0 un x 3 =0, pamata mainīgie būs vienādi ar x 1 = 1, x 4 = 2.

Mums ir pirmais iespējamais risinājums X 1 = (1, 0, 0, 2), ar Ф 1 = 0.

Ф palielinājums ir iespējams, palielinot, piemēram, x 3 vērtību, kas ir iekļauta izteiksmē Ф ar pozitīvu koeficientu (x 2 paliek vienāda ar nulli). Sistēmas pirmais vienādojums (*) parāda, ka x 3 var palielināt līdz 1 (no nosacījuma x 1 ³0), tas ir, šis vienādojums uzliek ierobežojumu x 3 vērtības pieaugumam. Sistēmas pirmais vienādojums (*) tiek atrisināts. Pamatojoties uz šo vienādojumu, mēs pārejam uz jaunu bāzi, nomainot x 1 un x 3. Tagad pamata mainīgie būs x 3 un x 4, un brīvie mainīgie būs x 1 un x 2. Tagad izteiksim x 3 un x 4 kā x 1 un x 2.

Mēs iegūstam: x 3 = 1 - x 1 + x 2 ; (**)

x 4 = 4 - 2 x 1 + x 2;

Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Pielīdzinot brīvos mainīgos ar nulli, iegūstam otro pieļaujamo pamatrisinājumu X 2 = (0; 0; 1; 4), kuram Ф 2 = 1.

Ф palielinājums ir iespējams, palielinoties x2. Pieaugums x 2, spriežot pēc pēdējās vienādojumu sistēmas (**), nav ierobežots. Līdz ar to Ф iegūs arvien lielākas pozitīvās vērtības, tas ir, Ф max = + ¥.

Tātad mērķa funkcija Ф nav ierobežota no augšas, tāpēc nav optimāla risinājuma.

UZDEVUMS 2.D. Izveidojiet uzdevumu, kas ir duāls ar doto

sākotnējais uzdevums.

7. variants. Maksimizējiet mērķa funkciju Ф = 2× x 1 - x 4

ar ierobežojumiem: x 1 + x 2 = 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Risinājums:

Savedīsim ierobežojumu sistēmu vienā, piemēram, kanoniskā formā, 2. un 3. vienādojumā ieviešot papildu mainīgos.

x 1 + x 2 = 20,

x 2 + 2 × x 4 – x 5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

Mēs esam ieguvuši 2. tipa asimetrisku problēmu. Dubultā problēma izskatīsies šādi:

Samaziniet mērķa funkciju F = 20 × y 1 + 5 × y2+8 × g 3

1. g. — 3. g ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

g 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

g 3 ≥ 0.

8. variants. Maksimizējiet mērķa funkciju Ф = x 2 - x 4 - 3× x 5

ar ierobežojumiem: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Risinājums:

Mums ir sākotnējā maksimizācijas problēma ar ierobežojumu sistēmu vienādojumu veidā, tas ir, duālo problēmu pārim ir asimetrisks 2. tipa tips, kura matemātiskais modelis matricas formā ir šāds:

Sākotnējā problēma: dubultā problēma:

F = C × X max F = B T × Y min

pie A × X = B pie A T × Y ≥ C T

Sākotnējā uzdevumā mainīgo koeficientu matricas rindai mērķa funkcijā ir forma C = (0; 1; 0; -1; -3; 0),

brīvo terminu matricas kolonnai un mainīgo lielumu koeficientu matricai ierobežojumu sistēmā ir forma

B = 2, A = 0 - 4 1 2 -1 0

Atradīsim transponēto koeficientu matricu, koeficientu rindu matricu mērķfunkcijas mainīgajiem un brīvo terminu kolonnu matricu

0 1 0 0 V T = (1; 2; 5)

A T = -1 2 0 C T = -1

Duālā problēma tiks uzrakstīta šādā formā:

atrodiet mērķa funkcijas F = y 1 + 2 minimālo vērtību × y2+5 × g 3

saskaņā ar ierobežojumiem y 1 ≥ 0,

2× g 1-4 × y2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

10. iespēja. Samaziniet funkciju Ф = x 1 + x 2 + x 3

ar ierobežojumiem: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Risinājums:

Mums ir sākotnējā minimizēšanas problēma ar ierobežojumu sistēmu nevienlīdzību veidā, tas ir, duālo problēmu pārim ir simetriska 3. tipa forma, kuras matemātiskajam modelim matricas formā ir šāda forma:

Sākotnējā problēma Duāla problēma

F = C × X min F = B T × Ymaks

pie A × X ≥ B pie A T × Y ≤ S T

X ≥ 0 Y ≥ 0

Sākotnējā uzdevumā mainīgo mainīgo koeficientu rindai mērķa funkcijā, brīvo terminu matricas kolonnai un ierobežojumu sistēmas mainīgo lielumu koeficientu matricai ir šāda forma

C = (1; 1; 1), B = 3, A = 6 4 5

Atradīsim duālās problēmas matricas

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Dubultā problēma ir formulēta šādi:

Maksimizējiet mērķa funkciju F = 2y 1 + 3y 2 + 4y 3

saskaņā ar ierobežojumiem 3 × y 1 + 6 × y2+8 × y 3 ≤ 1,

9× y 1 + 4 × y2+2 × y 3 ≤ 1,

7× y 1 + 5 × y2+4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

UZDEVUMS 2.C. Lineārās programmēšanas problēmas risināšana, izmantojot vienkāršās tabulas.

7. iespēja. Palieliniet mērķa funkciju Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

ar ierobežojumiem: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Risinājums:

Novedīsim ierobežojumu sistēmu līdz kanoniskajai formai

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Mums ir 3 vienādojumu sistēma ar 7 nezināmajiem. Izvēlēsimies 3 mainīgos x 1 , z 1 , z 3 kā pamata lielumus, x 2 , x 3 , x 4 , z 2 kā brīvos un izteiksim caur tiem pamata mainīgos.

No (2) mums ir x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Aizvietojot ar (1) un (3), mēs iegūstam

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Izveidosim simpleksa tabulu

I iterācija 1. tabula

Pamata AC	Brīvība. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.

II iterācija 2. tabula

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.

III iterācija 3. tabula

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.

IV iterācija 4. tabula

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

Indeksa rindā nav pēdējās tabulas negatīvi skaitļi, tas ir, mērķa funkcijas izteiksmē visi Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Atbilde: Ф m ax = 149/14,

optimālais risinājums (0; 0; 25/14; 37/14; 1/2; 0; 0)

8. variants. Samaziniet mērķa funkciju Ф = 5 x 1 - x 3

ar ierobežojumiem: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 =1,

Risinājums:

Mainīgo skaits ir 4, matricas rangs ir 2, tāpēc brīvo mainīgo skaits ir r = 4 - 2 = 2, pamata mainīgo skaits arī ir 2. Ņemsim x 3, x 4 kā brīvos mainīgos, izsaka pamatmainīgos x 1, x 2 kā brīvo un Reducēsim sistēmu uz vienības bāzi:

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Uzrakstīsim vienādojumu sistēmu un mērķa funkciju tādā formā, kas ir ērta simpleksa tabulai, tas ir, x 2 + 2 x 4 = 1,

x 1 + 2 x 3 - 3 x 4 = 2

F + 11 x 3 - 15 x 4 = 10

Taisām galdu

I iterācija 1. tabula

Pamata AC	Brīvība. AC
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) Ф 1 = 10.

II iterācija 2. tabula

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) Ф 2 = -1.

III iterācija 3. tabula

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 = (0; 0; 7/4; 1/2) F 3 = -7/4.

Pēdējās tabulas indeksa rindā nav pozitīvu skaitļu, tas ir, mērķa funkcijas izteiksmē visi Г i > 0. Mums ir I gadījums, tāpēc pēdējais pamatrisinājums ir optimāls.

Atbilde: Ф min = -7/4, optimālais risinājums (0; 0; 7/4; 1/2)

********************

10. iespēja. Samaziniet mērķa funkciju Ф = x 1 + x 2,

ar ierobežojumiem: x 1–2 x 3 + x 4 = 2,

x 2 – x 3 + 2 x 4 = 1,

Risinājums:

Mainīgo skaits ir 5, matricas rangs ir 3, tāpēc brīvo mainīgo skaits ir r = 6-3 = 2. Ņemsim x 3 un x 4 kā brīvos mainīgos, un x 1 , x 2 , x 5 kā pamata. Visi sistēmas vienādojumi jau ir reducēti uz vienības bāzi (pamata mainīgie tiek izteikti brīvos), bet ir rakstīti formā, kas nav ērta simpleksu tabulu lietošanai. Uzrakstīsim vienādojumu sistēmu formā

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4 . = 5

Mērķa funkciju izsakām brīvo mainīgo izteiksmē un ierakstām formā Ф - 3 x 3 +3 x 4 = 3

Taisām galdu

I iterācija 1. tabula

Pamata AC	Brīvība. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 = 3.

2. tabula

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 = (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.

Pēdējās tabulas indeksa rindā nav pozitīvu skaitļu, tas ir, mērķa funkcijas izteiksmē visi Gi > 0. Mums ir 1. gadījums, tāpēc pēdējais pamatrisinājums ir optimāls.

Atbilde: Ф min = 3/2, optimālais risinājums (3/2; 0; 0; 1/2; 11/2).

Federālā izglītības aģentūra

valsts budžets izglītības iestāde

augstāks profesionālā izglītība

"Omskas Valsts tehniskā universitāte"

APRĒĶINS UN GRAFISKS DARBS

pēc disciplīnas"OPTIMĀLĀS VADĪBAS TEORIJA »

par tēmu"OPTIMIZĀCIJAS METODES UN DARBĪBU IZPĒTE »

7. variants

Pabeigts:

neklātienes students

4.kursa grupa ZA-419

Pilns vārds: Kužeļevs S.A.

Pārbaudīts:

Devjaterikova M.V.

Omska - 2012
^

Uzdevums 1. Grafiskā metode lineārās programmēšanas uzdevumu risināšanai.

7) 7x 1 + 6x 2 → maks 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

1. darbība. Iespējamā reģiona izveide

Mainīgo un kvadrātu nenegatīvisma nosacījumi ierobežo to pieļaujamo vērtību diapazonu līdz pirmajam kvadrantam. Katrs no atlikušajiem četriem modeļa nevienlīdzības ierobežojumiem atbilst noteiktai pusplaknei. Šo pusplakņu krustojums ar pirmo kvadrantu veido iespējamo problēmas risinājumu kopumu.

Pirmajam modeļa ierobežojumam ir forma . Aizstājot tajā zīmi ≤ ar = zīmi, iegūstam vienādojumu . Attēlā 1.1 tas nosaka taisni (1), kas sadala plakni divās pusplaknēs, in šajā gadījumā virs un zem līnijas. Lai izvēlētos, kurš apmierina nevienlīdzību , aizstājiet tajā jebkura punkta koordinātas, kas neatrodas uz noteiktas līnijas (piemēram, sākumpunktu X 1 = 0, X 2 = 0). Tā kā mēs iegūstam pareizo izteiksmi (20 0 + 6 0 = 0 ≤15), tad pusplakne, kas satur koordinātu sākumpunktu (atzīmēta ar bultiņu), apmierina nevienādību. Citādi cita puslidmašīna.

Līdzīgi rīkojamies ar atlikušajiem problēmas ierobežojumiem. Veidojas visu konstruēto pusplakņu krustpunkts ar pirmo kvadrantu ABCD(skat. 1. att.). Šī ir problēmas iespējamā joma.

2. solis. Līmeņa līnijas zīmēšana Līmeņa līnija Mērķa funkcija ir plaknes punktu kopa, kurā mērķa funkcija iegūst nemainīgu vērtību. Šādu kopu dod vienādojums f ( x) = konst. Pieņemsim, piemēram, konst = 0 un uzzīmējiet līniju līmenī f ( x) = 0, t.i. mūsu gadījumā taisnā līnija 7 x 1 + 6x 2 = 0.

Šī līnija iet caur sākuma punktu un ir perpendikulāra vektoram. Šis vektors ir mērķa funkcijas gradients punktā (0,0). Funkcijas gradients ir noteiktas funkcijas daļējo atvasinājumu vērtību vektors attiecīgajā punktā. LP uzdevuma gadījumā mērķa funkcijas daļējie atvasinājumi ir vienādi ar koeficientiem Ces, j = 1 , ..., n.

Gradients parāda funkcijas ātrākās izaugsmes virzienu. Mērķa funkcijas līmeņa līnijas pārvietošana f ( x) = konst. perpendikulāri gradienta virzienam, mēs atrodam pēdējo punktu, kurā tas krustojas ar reģionu. Mūsu gadījumā tas ir punkts D, kas būs mērķfunkcijas maksimālais punkts (skat. 2. att.)

Tas atrodas līniju (2) un (3) krustpunktā (sk. 1. att.) un norāda optimālo risinājumu.

^ Ņemiet vērā, ka, ja vēlaties atrast mērķa funkcijas minimālo vērtību, līmeņa līnija tiek pārvietota virzienā, kas ir pretējs gradienta virzienam.

^ 3. solis. Maksimālā (minimālā) punkta koordinātu un mērķa funkcijas optimālās vērtības noteikšana

Lai atrastu punkta C koordinātas, ir jāatrisina sistēma, kas sastāv no vienādojumiem, kas atbilst taisnēm (šajā gadījumā vienādojumi 2 un 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Iegūstam optimālo risinājumu = 1,33.

^ Optimāla vērtība mērķa funkcija f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

DISCIPLINAS KONTROLES DARBS:

“OPTIMĀLO RISINĀJUMU METODES”

Variants Nr.8

1. Grafiski atrisiniet lineārās programmēšanas uzdevumu. Atrodiet funkcijas maksimumu un minimumu ar dotajiem ierobežojumiem:

,

.

Risinājums

Ir jāatrod mērķfunkcijas minimālā un maksimālā vērtība ierobežojumu sistēmā:

9 x 1 +3 x 2 ≥30, (1)

X 1 + x 2 ≤ 4, (2)

x 1 + x 2 ≤ 8, (3)

Konstruēsim iespējamo risinājumu reģionu, t.i. Atrisināsim nevienādību sistēmu grafiski. Lai to izdarītu, mēs izveidojam katru taisni un definējam pusplaknes, ko nosaka nevienādības (pusplaknes tiek norādītas ar pirmskaitli).

Pusplakņu krustpunkts būs apgabals, kura punktu koordinātas apmierina problēmas ierobežojumu sistēmas nevienādības. Apzīmēsim risinājuma daudzstūra laukuma robežas.

Konstruēsim taisni, kas atbilst funkcijas F = 0 vērtībai: F = 2x 1 +3x 2 = 0. Gradienta vektors, kas sastāv no mērķa funkcijas koeficientiem, norāda F(X) minimizēšanas virzienu. Vektora sākums ir punkts (0; 0), beigas ir punkts (2; 3). Mēs pārvietosim šo taisnu līniju paralēli. Tā kā mūs interesē minimālais risinājums, mēs virzām taisno līniju, līdz tā vispirms pieskaras norādītajai vietai. Diagrammā šī taisne ir norādīta ar punktētu līniju.

Taisni
krusto apgabalu punktā C. Tā kā punkts C ir iegūts taisnes (4) un (1) krustošanās rezultātā, tā koordinātas atbilst šo taisnes vienādojumiem:
.

Atrisinot vienādojumu sistēmu, iegūstam: x 1 = 3,3333, x 2 = 0.

Kā mēs varam atrast mērķa funkcijas minimālo vērtību: .

Apskatīsim problēmas objektīvo funkciju.

Konstruēsim taisni, kas atbilst funkcijas F = 0 vērtībai: F = 2x 1 +3x 2 = 0. Gradienta vektors, kas sastāv no mērķa funkcijas koeficientiem, norāda F(X) maksimizācijas virzienu. Vektora sākums ir punkts (0; 0), beigas ir punkts (2; 3). Mēs pārvietosim šo taisnu līniju paralēli. Tā kā mūs interesē maksimālais risinājums, mēs virzām taisno līniju līdz pēdējam pieskārienam norādītajā zonā. Diagrammā šī taisne ir norādīta ar punktētu līniju.

Taisni
krusto apgabalu punktā B. Tā kā punkts B ir iegūts taisnes (2) un (3) krustošanās rezultātā, tā koordinātas atbilst šo taisnes vienādojumiem:

.

Kā mēs varam atrast mērķa funkcijas maksimālo vērtību: .

Atbilde:
Un
.

2 . Atrisiniet lineārās programmēšanas problēmu, izmantojot simplekso metodi:

.

Risinājums

Atrisināsim tiešās lineārās programmēšanas uzdevumu, izmantojot simplekso metodi, izmantojot simpleksa tabulu.

Noteiksim mērķa funkcijas minimālo vērtību
ar šādiem nosacījumiem un ierobežojumiem:
.

Lai izveidotu pirmo atsauces plānu, mēs reducējam nevienādību sistēmu līdz vienādojumu sistēmai, ieviešot papildu mainīgos.

1. nozīmes nevienādībā (≥) ieviešam pamata mainīgo x 3 ar mīnusa zīmi. 2. nozīmes nevienādībā (≤) ieviešam pamata mainīgo x 4 . 3. nozīmes nevienādībā (≤) ieviešam pamata mainīgo x 5 .

Ieviesīsim mākslīgos mainīgos : 1. vienādībā mēs ieviešam mainīgo x 6 ;

Lai problēmu iestatītu līdz minimumam, mērķa funkciju rakstām šādi: .

Par mērķa funkcijā ievadīto mākslīgo mainīgo izmantošanu tiek uzlikts tā sauktais sods M, ļoti liels pozitīvs skaitlis, kas parasti netiek norādīts.

Iegūto bāzi sauc par mākslīgo, un risinājuma metodi sauc par mākslīgo bāzes metodi.

Turklāt mākslīgie mainīgie nav saistīti ar problēmas saturu, bet ļauj konstruēt sākumpunktu, un optimizācijas process liek šiem mainīgajiem pieņemt nulles vērtības un nodrošināt optimālā risinājuma pieļaujamību.

No vienādojumiem izsakām mākslīgos mainīgos: x 6 = 4-x 1 -x 2 +x 3, kurus aizvietojam mērķa funkcijā: vai.

Koeficientu matrica
šai vienādojumu sistēmai ir šāda forma:
.

Atrisināsim vienādojumu sistēmu pamata mainīgajiem: x 6 , x 4 , x 5.

Pieņemot, ka brīvie mainīgie ir vienādi ar 0, mēs iegūstam pirmo atsauces plāns:

X1 = (0,0,0,2,10,4)

Pamatrisinājumu sauc par pieņemamu, ja tas nav negatīvs.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Pašreizējais atskaites plāns nav optimāls, jo indeksa rindā ir pozitīvi koeficienti. Kā galveno kolonnu mēs izvēlēsimies kolonnu, kas atbilst mainīgajam x 2, jo tas ir lielākais koeficients. Aprēķināsim vērtības D i un no tiem mēs izvēlamies mazāko: min(4: 1, 2: 2, 10: 2) = 1.

Tāpēc 2. rinda ir vadošā.

Izšķirošais elements ir vienāds ar (2) un atrodas vadošās kolonnas un vadošās rindas krustpunktā.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Mēs veidojam nākamo vienkāršās tabulas daļu. Mainīgā x 4 vietā 1. plānā tiks iekļauts mainīgais x 2.

Rinda, kas atbilst mainīgajam x 2 plānā 1, tiek iegūta, visus plāna 0 rindas x 4 elementus dalot ar atrisināšanas elementu RE = 2. Izšķirošā elementa vietā iegūstam 1. Atlikušajās x 2 kolonnas šūnās ierakstām nulles.

Tādējādi jaunajā plānā 1 ir aizpildīta rinda x 2 un kolonna x 2. Visus pārējos jaunā plāna 1 elementus, ieskaitot indeksa rindas elementus, nosaka taisnstūra noteikums.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 + 1 1/2 milj

Pašreizējais atskaites plāns nav optimāls, jo indeksa rindā ir pozitīvi koeficienti. Kā galveno kolonnu mēs izvēlēsimies kolonnu, kas atbilst mainīgajam x 1, jo tas ir lielākais koeficients. Aprēķināsim vērtības D i pēc rindas kā dalījuma koeficients: un no tiem mēs izvēlamies mazāko: min (3: 1 1 / 2, -, 8: 2) = 2.

Tāpēc 1. rinda ir vadošā.

Izšķirošais elements ir vienāds ar (1 1/2) un atrodas vadošās kolonnas un vadošās rindas krustpunktā.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Mēs veidojam nākamo vienkāršās tabulas daļu. Mainīgā x 6 vietā 2. plānā tiks iekļauts mainīgais x 1.

Mēs iegūstam jaunu simpleksa tabulu:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Starp indeksa virknes vērtībām nav pozitīvu vērtību. Tāpēc šī tabula nosaka optimālo problēmas plānu.

Simpleksās tabulas galīgā versija:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Tā kā optimālajā risinājumā nav mākslīgu mainīgo (tie ir vienādi ar nulli), šis risinājums ir pieļaujams.

Optimālo plānu var uzrakstīt šādi: x 1 = 2, x 2 = 2:.

Atbilde:
,
.

3. Uzņēmums Three Fat Men piegādā gaļas konservus no trim noliktavām, kas atrodas dažādās pilsētas vietās, uz trim veikaliem. Transporta tabulā ir uzrādīti noliktavās pieejamie konservu krājumi, kā arī veikalu pasūtījumu apjomi un piegādes tarifi (konvencionālajās naudas vienībās).

Atrodiet transporta plānu, kas nodrošina viszemākās naudas izmaksas (sākotnējo transporta plānu veiciet, izmantojot “ziemeļrietumu stūra” metodi).

Risinājums

Pārbaudīsim nepieciešamo un pietiekamo problēmas risināmības nosacījumu:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Līdzsvara nosacījums ir izpildīts. Nodrošina vienādas vajadzības. Līdz ar to transporta problēmas modelis ir slēgts.

Ievadīsim sākotnējos datus sadalījuma tabulā.

Vajadzības

Izmantojot ziemeļrietumu stūra metodi, mēs izveidosim pirmo transporta problēmas atskaites plānu.

Plāns sāk aizpildīt no augšējā kreisā stūra.

Nepieciešamais elements ir 4. Šim elementam krājumi ir 300, prasības ir 250. Tā kā minimums ir 250, mēs to atņemam: .

			300 - 250 = 50
250 - 250 = 0

Nepieciešamais elements ir vienāds ar 2. Šim elementam krājumi ir 50, prasības ir 400. Tā kā minimums ir 50, mēs to atņemam: .

			50 - 50 = 0
	400 - 50 = 350

Nepieciešamais elements ir 5. Šim elementam krājumi ir 300, prasības ir 350. Tā kā minimums ir 300, mēs to atņemam:

			300 - 300 = 0
	350 - 300 = 50

Nepieciešamais elements ir 3. Šim elementam krājumi ir 200, prasības ir 50. Tā kā minimums ir 50, mēs to atņemam:

			200 - 50 = 150
	50 - 50 = 0

Nepieciešamais elements ir 6. Šim elementam krājumi ir 150, prasības ir 150. Tā kā minimums ir 150, mēs to atņemam:

			150 - 150 = 0
		150 - 150 = 0

Vajadzības

Ievads

Pašreizējais cilvēces attīstības posms izceļas ar to, ka enerģētikas laikmetu nomaina datorzinātņu laikmets. Notiek intensīva jauno tehnoloģiju ieviešana visās cilvēka darbības sfērās. Pastāv reāla pāreja uz informācijas sabiedrību, kuras prioritātei jākļūst izglītības attīstībai. Mainās arī zināšanu struktūra sabiedrībā. Aizvien svarīgāks priekš praktiskā dzīve iegūt fundamentālas zināšanas, kas veicina indivīda radošo attīstību. Svarīga ir arī iegūto zināšanu konstruktivitāte un spēja tās strukturēt atbilstoši mērķim. Balstoties uz zināšanām, veidojas jaunas informācijas resursi sabiedrību. Jaunu zināšanu veidošanai un apguvei jābalstās uz stingru sistēmpieejas metodoloģiju, kurā īpašu vietu ieņem modeļa pieeja. Modeļa pieejas iespējas ir ārkārtīgi dažādas gan izmantoto formālo modeļu, gan modelēšanas metožu ieviešanas metožu ziņā. Fiziskā modelēšana ļauj iegūt ticamus rezultātus diezgan vienkāršām sistēmām.

Pašlaik nav iespējams nosaukt cilvēka darbības jomu, kurā modelēšanas metodes vienā vai otrā pakāpē netiktu izmantotas. Īpaši tas attiecas uz vadības jomu dažādas sistēmas, kur galvenie procesi ir lēmumu pieņemšana, pamatojoties uz saņemto informāciju.

1. Problēmas izklāsts

minimālā mērķa funkcija

Atrisiniet uzdevumu par mērķfunkcijas minimuma atrašanu risinājuma daudzstūra noteikto ierobežojumu sistēmai saskaņā ar uzdevuma variantu Nr.16. Risinājuma daudzstūris ir parādīts 1. attēlā:

1. attēls — problēmas risinājumu daudzstūris

Ierobežojumu sistēma un problēmas mērķa funkcija ir parādīta zemāk:

Problēma ir jāatrisina, izmantojot šādas metodes:

Grafiskā metode LP uzdevumu risināšanai;

Algebriskā metode LP uzdevumu risināšanai;

Simplex metode LP uzdevumu risināšanai;

LP problēmu pieļaujamā risinājuma atrašanas metode;

Duālās LP problēmas risinājums;

Sazarojuma un saistīšanas metode veselu skaitļu LP uzdevumu risināšanai;

Gomori metode veselu skaitļu LP uzdevumu risināšanai;

Balaža metode Būla LP uzdevumu risināšanai.

Salīdziniet risinājumu rezultātus dažādas metodes no darba izdarīt atbilstošus secinājumus.

2. Lineārās programmēšanas problēmas grafiskais risinājums

Grafiskā metode lineārās programmēšanas uzdevumu risināšanai tiek izmantota gadījumos, kad nezināmo skaits nepārsniedz trīs. Ērts risinājumu īpašību kvalitatīvai izpētei un tiek izmantots kopā ar citām metodēm (algebriskām, sazarotajām un saistošajām u.c.). Metodes ideja ir balstīta uz lineāro nevienādību sistēmas grafisko risinājumu.

Rīsi. 2 LP uzdevuma grafiskais risinājums

Minimālais punkts

Taisnes vienādojums, kas iet caur diviem punktiem A1 un A2:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

ar ierobežojumiem:

Lineārās programmēšanas uzdevuma risināšana, izmantojot algebrisko simplekso metodi

Algebriskās metodes pielietošana problēmas risināšanā prasa LP uzdevuma attēlojuma vispārināšanu. Sākotnējā ierobežojumu sistēma, kas norādīta nevienlīdzību veidā, tiek pārveidota par standarta apzīmējumu, kad ierobežojumi ir norādīti vienādību formā. Ierobežojumu sistēmas transformācija uz standarta skats ietver šādas darbības:

Pārveidojiet nevienādības tā, lai kreisajā pusē būtu mainīgie un brīvie termini, bet labajā pusē - 0, t.i. uz kreisā puse bija lielāka vai vienāda ar nulli;

Ieviest papildu mainīgos, kuru skaits ir vienāds ar nevienlīdzību skaitu ierobežojumu sistēmā;

Ieviešot papildu ierobežojumus pievienoto mainīgo lielumu nenegatīvumam, nevienlīdzības zīmes aizstājiet ar stingrām vienādības zīmēm.

Atrisinot LP uzdevumu, izmantojot algebrisko metodi, tiek pievienots nosacījums: mērķa funkcijai ir jātiecas uz minimumu. Ja šis nosacījums nav apmierināts, nepieciešams attiecīgi pārveidot mērķa funkciju (reizināt ar -1) un atrisināt minimizēšanas problēmu. Kad risinājums ir atrasts, aizstājiet mainīgo vērtības ar sākotnējo funkciju un aprēķiniet tās vērtību.

Problēmas risinājums, izmantojot algebrisko metodi, tiek uzskatīts par optimālu, ja visu pamata mainīgo vērtības nav negatīvas, un arī brīvo mainīgo koeficienti mērķa funkcijas vienādojumā nav negatīvi. Ja šie nosacījumi nav izpildīti, ir nepieciešams pārveidot nevienādību sistēmu, izsakot vienus mainīgos ar citiem (mainot brīvos un pamata mainīgos), lai panāktu augstāk minēto ierobežojumu izpildi. Visu brīvo mainīgo vērtību uzskata par vienādu ar nulli.

Algebriskā metode lineārās programmēšanas uzdevumu risināšanai ir viena no visvairāk efektīvas metodes risinot neliela mēroga problēmas manuāli, jo neprasa lielu skaitu aritmētisko aprēķinu. Šīs metodes mašīnas ieviešana ir sarežģītāka nekā, piemēram, vienkāršās metodes gadījumā, jo Risinājuma algoritms, izmantojot algebrisko metodi, zināmā mērā ir heiristisks, un risinājuma efektivitāte lielā mērā ir atkarīga no personīgās pieredzes.

Bezmaksas mainīgie

St josla - papildu komplekts

Nenegatīvisma nosacījumi ir izpildīti, tāpēc ir atrasts optimālais risinājums.

3. Lineārās programmēšanas uzdevuma risināšana, izmantojot simpleksa tabulu

Risinājums: izveidosim problēmu standarta formā risinājumam, izmantojot simpleksa tabulu.

Reducēsim visus sistēmas vienādojumus līdz formai:

Mēs veidojam simpleksa tabulu:

Katras tabulas šūnas augšējā stūrī ievadām koeficientus no vienādojumu sistēmas;

Mēs izvēlamies maksimālo pozitīvo elementu rindā F, izņemot to, ka šī būs vispārējā kolonna;

Lai atrastu vispārējo elementu, mēs veidojam attiecības visiem pozitīvajiem. 3/3; 9/1;- minimālā attiecība rindā x3. Tāpēc - vispārējā virkne un =3 - vispārējais elements.

Mēs atrodam =1/=1/3. Mēs to ievietojam šūnas apakšējā stūrī, kur atrodas vispārējais elements;

Visos tukšajos vispārīgās rindas apakšējos stūros ievadām vērtības reizinājumu šūnas augšējā stūrī by;

Atlasiet vispārīgās līnijas augšējos stūrus;

Visos vispārīgās kolonnas apakšējos stūros ievadām vērtības reizinājumu augšējā stūrī ar - un atlasām iegūtās vērtības;

Pārējās tabulas šūnas tiek aizpildītas kā atbilstošo atlasīto elementu reizinājums;

Tad mēs veidojam jaunu tabulu, kurā tiek apmainīti vispārējās kolonnas un rindas elementu šūnu apzīmējumi (x2 un x3);

Vērtības, kas iepriekš bija apakšējā stūrī, tiek ierakstītas iepriekšējās vispārējās rindas un kolonnas augšējā stūrī;

Šo šūnu augšējā un apakšējā stūra vērtību summa iepriekšējā tabulā ir ierakstīta atlikušo šūnu augšējā stūrī

4. Lineārās programmēšanas problēmas risināšana, atrodot pieļaujamo risinājumu

Dota lineāro algebrisko vienādojumu sistēma:

Mēs varam pieņemt, ka viss ir, pretējā gadījumā mēs reizinām atbilstošo vienādojumu ar -1.

Mēs ieviešam papildu mainīgos:

Mēs arī ieviešam palīgfunkciju

Mēs samazināsim sistēmu, ievērojot ierobežojumus (2) un nosacījumus.

ATĻAUJAMĀ RISINĀJUMA ATRAŠANAS NOTEIKUMS: Lai atrastu pieņemamu risinājumu sistēmai (1), mēs minimizējam veidlapu (3) saskaņā ar ierobežojumiem (2), ņemot xj kā brīvus nezināmos un ņemot xj kā pamata.

Risinot problēmu, izmantojot simplekso metodi, var rasties divi gadījumi:

min f=0, tad visam i jābūt vienādam ar nulli. Un iegūtās xj vērtības veidos pieņemamu sistēmas (1) risinājumu.

min f>0, t.i. oriģinālajai sistēmai nav realizējama risinājuma.

Avotu sistēma:

Tiek izmantots problēmas nosacījums no iepriekšējās tēmas.

Ieviesīsim papildu mainīgos:

Ir atrasts pieļaujamais sākotnējās problēmas risinājums: x1 = 3, x2 = 3, F = -12. Pamatojoties uz iegūto iespējamo risinājumu, mēs atradīsim optimālo sākotnējās problēmas risinājumu, izmantojot simpleksa metodi. Lai to izdarītu, no iepriekš iegūtās tabulas izveidosim jaunu simpleksa tabulu, noņemot rindu un rindu ar palīgproblēmas mērķa funkciju:

Analizējot konstruēto simpleksa tabulu, redzam, ka sākotnējās problēmas optimālais risinājums jau ir atrasts (mērķfunkcijai atbilstošajā rindā elementi ir negatīvi). Tādējādi iespējamais risinājums, kas atrasts, risinot palīgproblēmu, sakrīt ar sākotnējās problēmas optimālo risinājumu:

6. Duālās lineārās programmēšanas problēma

Sākotnējā ierobežojumu sistēma un problēmas mērķa funkcija ir parādīta attēlā zemāk.

ar ierobežojumiem:

Risinājums: izveidosim ierobežojumu sistēmu standarta formā:

Dubultā problēmai būs šāda forma:

Duālās problēmas risinājums tiks veikts, izmantojot vienkāršu simpleksa metodi.

Pārveidosim mērķa funkciju tā, lai minimizēšanas problēma būtu atrisināta, un uzrakstīsim ierobežojumu sistēmu standarta formā risināšanai, izmantojot simpleksa metodi.

y6 = 1 – (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 — (3 g1 + 9 g2 + 3 g3 + y4) ??min

Izveidosim sākotnējo simpleksa tabulu duālās LP problēmas risināšanai.

Simpleksās metodes otrais solis

Tātad simpleksās metodes trešajā solī tika atrasts optimāls minimizācijas problēmas risinājums ar šādiem rezultātiem: y2 = -7 /8, y1 = -11/8, Ф = 12. Lai atrastu vērtību duālās problēmas mērķfunkcija, mēs aizvietojam atrastās pamata un brīvo mainīgo vērtības ar maksimizācijas funkciju:

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Tā kā tiešās un duālās problēmas mērķfunkcijas vērtība sakrīt, tiek atrasts tiešās problēmas risinājums un ir vienāds ar 12.

Fmin = Фmax = -12

7. Veselo skaitļu lineārās programmēšanas uzdevuma risināšana, izmantojot sazarojuma un saistīšanas metodi

Pārveidosim sākotnējo problēmu tā, lai vesela skaitļa nosacījums netiktu izpildīts, ja to risina ar parastajām metodēm.

Vesela skaitļa programmēšanas problēmas risinājumu sākotnējais daudzstūris.

Pārveidotajam risinājumu daudzstūrim mēs konstruējam jauna sistēma ierobežojumiem.

Pierakstīsim ierobežojumu sistēmu vienādību veidā, kas jāatrisina ar algebrisko metodi.

Risinājuma rezultātā tika atrasts optimālais uzdevuma plāns: x1 = 9/4, x2 = 5/2, F = -41/4. Šis risinājums neatbilst uzdevumā iestatītajam vesela skaitļa nosacījumam. Sadalīsim sākotnējo risinājuma daudzstūri divos apgabalos, no tā izslēdzot 3. apgabalu

Modificēts problēmas risinājuma daudzstūris

Izveidosim jaunas ierobežojumu sistēmas risinājuma daudzstūra iegūtajiem laukumiem. Kreisais laukums ir četrstūris (trapece). Risinājuma daudzstūra kreisā reģiona ierobežojumu sistēma ir parādīta zemāk.

Kreisās zonas ierobežošanas sistēma

Labais apgabals apzīmē punktu C.

Ierobežojumu sistēma pareizā lēmuma reģionam ir parādīta zemāk.

Jaunās ierobežojumu sistēmas ir divas palīgproblēmas, kas ir jāatrisina neatkarīgi viena no otras. Atrisināsim veselu skaitļu programmēšanas uzdevumu risinājuma daudzstūra kreisajam apgabalam.

Risinājuma rezultātā tika atrasts optimālais uzdevuma plāns: x1 = 3, x2 = 3, F = -12. Šis plāns atbilst nosacījumam, ka uzdevumā esošie mainīgie ir veseli skaitļi, un tos var pieņemt kā optimālo atsauces plānu sākotnējās veselo skaitļu lineārās programmēšanas problēmas risināšanai. Nav jēgas risināt pareizo risinājumu reģionu. Zemāk redzamajā attēlā parādīts veselu skaitļu lineāras programmēšanas uzdevuma risināšanas gaita koka veidā.

Vesela skaita lineārās programmēšanas problēmas risināšanas gaita, izmantojot Gomori metodi.

Daudzos praktiskos lietojumos lielu interesi rada veselu skaitļu programmēšanas problēma, kurā ir dota lineāro nevienādību sistēma un lineāra forma.

Sistēmai (1) jāatrod veselu skaitļu risinājums, kas samazina mērķa funkciju F, un visi koeficienti ir veseli skaitļi.

Vienu no metodēm veselo skaitļu programmēšanas problēmas risināšanai piedāvāja Gomori. Metodes ideja ir izmantot nepārtrauktas lineārās programmēšanas metodes, jo īpaši simplekso metodi.

1) Izmantojot simplekso metodi, tiek noteikts (1), (2) uzdevuma risinājums, kuram tiek noņemta vesela skaitļa atrisinājuma prasība; ja risinājums izrādīsies vesels skaitlis, tad tiks atrasts arī vēlamais veselo skaitļu uzdevuma risinājums;

2) Pretējā gadījumā, ja kāda koordināta nav vesels skaitlis, iegūtais uzdevuma risinājums tiek pārbaudīts, lai noteiktu vesela skaitļa risinājuma esamību (vesela skaitļa punktu klātbūtne pieļaujamajā daudzskaldnī):

ja kādā rindā ar daļēju brīvo terminu visi pārējie koeficienti izrādās veseli skaitļi, tad pieļaujamajā daudzskaldnī nav veselu skaitļu vai punktu un veselo skaitļu programmēšanas problēmai nav risinājuma;

Pretējā gadījumā tiek ieviests papildu lineārs ierobežojums, kas nogriež daļu no pieļaujamā daudzskaldņa, kas nav perspektīva veselo skaitļu programmēšanas problēmas risinājuma atrašanai;

3) Lai izveidotu papildu lineāro ierobežojumu, atlasiet l-to rindu ar daļēju brīvo terminu un uzrakstiet papildu ierobežojumu

kur un ir attiecīgi koeficientu daļdaļas un brīvas

biedrs. Ieviesīsim ierobežojumā (3) palīgmainīgo:

Nosakīsim ierobežojumā (4) iekļautos koeficientus:

kur un ir attiecīgi tuvākie veselie skaitļi no apakšas un.

Gomori pierādīja, ka ierobežots skaits līdzīgu darbību noved pie lineāras programmēšanas problēmas, kuras risinājums ir vesels skaitlis un līdz ar to vēlamais.

Risinājums: izveidosim lineāro ierobežojumu sistēmu un mērķa funkciju kanoniskajā formā:

Noteiksim optimālo risinājumu lineāro ierobežojumu sistēmai, uz laiku atmetot vesela skaitļa nosacījumu. Šim nolūkam mēs izmantojam simpleksa metodi. Zemāk tabulās secīgi tiek parādīts uzdevuma sākotnējais risinājums un dotas sākotnējās tabulas transformācijas, lai iegūtu optimālu problēmas risinājumu:

Būla LP uzdevumu risināšana, izmantojot Balaža metodi.

Izveidojiet savu versiju veselu skaitļu lineāras programmēšanas uzdevumam ar Būla mainīgajiem, ņemot vērā šādus noteikumus: uzdevumā tiek izmantoti vismaz 5 mainīgie, vismaz 4 ierobežojumi, ierobežojumu koeficienti un mērķa funkcija tiek izvēlēti patvaļīgi, bet veids, kā ierobežojumu sistēma ir saderīga. Uzdevums ir atrisināt LCLP ar Būla mainīgajiem, izmantojot Balaža algoritmu un noteikt aprēķinu sarežģītības samazinājumu saistībā ar problēmas risināšanu, izmantojot izsmeļošās meklēšanas metodi.

Ierobežojumu izpilde

F vērtība

Filtrēšanas ierobežojums:

Skaitļošanas piepūles samazināšanas noteikšana

Problēmas risinājums, izmantojot izsmeļošu meklēšanas metodi, ir 6*25=192 aprēķinātās izteiksmes. Problēmas risinājums, izmantojot Balaža metodi, ir 3*6+(25-3)=47 aprēķinātās izteiksmes. Kopējais aprēķinu sarežģītības samazinājums saistībā ar problēmas risināšanu, izmantojot izsmeļošu meklēšanas metodi, ir:

Secinājums

Informācijas sistēmu projektēšanas process, kas ievieš jaunas informācijas tehnoloģijas, tiek nepārtraukti pilnveidots. Sistēmu inženieru uzmanība arvien vairāk tiek pievērsta sarežģītām sistēmām, apgrūtinot fizisko modeļu izmantošanu un palielinot matemātisko modeļu un sistēmu mašīnmodelēšanas nozīmi. Mašīnu simulācija ir kļuvusi par efektīvu instrumentu sarežģītu sistēmu izpētei un projektēšanai. Matemātisko modeļu aktualitāte nepārtraukti pieaug, pateicoties to elastībai, piemērotībai reāliem procesiem un zemajām ieviešanas izmaksām, pamatojoties uz moderniem personālajiem datoriem. Arvien vairāk iespēju tiek nodrošinātas lietotājam, t.i., speciālists sistēmu modelēšanā, izmantojot datortehnoloģiju. Modelēšanas izmantošana ir īpaši efektīva automatizēto sistēmu projektēšanas sākumposmā, kad kļūdainu lēmumu izmaksas ir visnozīmīgākās.

Mūsdienu skaitļošanas rīki ir ļāvuši ievērojami palielināt sistēmu izpētē izmantoto modeļu sarežģītību, ir kļuvis iespējams izveidot kombinētus, analītiskos un simulācijas modeļus, kas ņem vērā visu faktoru daudzveidību, kas notiek reālās sistēmās, t. , tādu modeļu izmantošana, kas ir adekvātāki pētāmajām parādībām.

Literatūra:

1. Ļaščenko I.N. Lineārā un nelineārā programmēšana / I. N. Ļaščenko, E. A. Karagodova, N. V. Čerņikova, N. Z. - K.: “Augstskola”, 1975, 372 lpp.

2. Metodiskie norādījumi kursa projekta izpildei disciplīnā “Lietišķā matemātika” pilna laika un nepilna laika studiju formu studentiem / Sastādīja: I.A., A.V. Skatkovs - Sevastopols. Izdevniecība SevNTU , 2003. - 15 lpp.

3. Vadlīnijas disciplīnas “Lietišķā matemātika” apguvei, sadaļa “Globālās meklēšanas metodes un viendimensionālās minimizācijas” / Sast. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31 lpp.

4. Norādījumi disciplīnas “Lietišķā matemātika” studijām specialitātes “Datorsistēmas un tīkli” sadaļa “Integer lineārās programmēšanas uzdevumu risināšana” pilna laika un nepilna laika izglītībai / Sastādīja: I.A.Balakireva, A.V.Skatkovs : SevNTU izdevniecība, 2000. - 13 lpp.

5. Akulich I.L. Matemātiskā programmēšana piemēros un uzdevumos:

6. Mācību grāmata pabalsts ekonomikas studentiem. speciālists. augstskolas.-M.: Augstākās. skola, 1986.- 319 lpp., ill.

7. Andronovs S.A. Optimālās projektēšanas metodes: Lekciju teksts / SPbSUAP. Sanktpēterburga, 2001. 169 lpp.: ill.

Līdzīgi dokumenti

Algoritms lineārās programmēšanas uzdevumu risināšanai, izmantojot simplekso metodi. Lineārās programmēšanas problēmas matemātiskā modeļa konstruēšana. Lineārās programmēšanas problēmas risināšana programmā Excel. Peļņas un optimālā ražošanas plāna atrašana.

kursa darbs, pievienots 21.03.2012


Grafiskā problēmu risināšana. Matemātiskā modeļa sastādīšana. Mērķa funkcijas maksimālās vērtības noteikšana. Risinājums ar simpleksa metodi ar kanoniskās lineārās programmēšanas uzdevuma mākslīgo bāzi. Risinājuma optimāluma pārbaude.

tests, pievienots 04.05.2016


Lineārās programmēšanas teorētiskā bāze. Lineārās programmēšanas problēmas, risināšanas metodes. Optimālā risinājuma analīze. Viena indeksa lineārās programmēšanas uzdevuma risinājums. Problēmas izklāsts un datu ievade. Modeļa uzbūves un risinājuma stadijas.

kursa darbs, pievienots 09.12.2008


Matemātiskā modeļa konstruēšana. Tiešās lineārās programmēšanas problēmas risināšanas metodes izvēle, pamatojums un apraksts, izmantojot simplekso metodi, izmantojot simpleksa tabulu. Duālas problēmas formulēšana un risinājums. Modeļa jutīguma analīze.

kursa darbs, pievienots 31.10.2014


Matemātiskā modeļa konstruēšana, lai gūtu maksimālu peļņu uzņēmumam, uzdevuma grafiskais risinājums. Problēmas risināšana, izmantojot papildinājumu SOLVER. Resursu rezervju izmaiņu analīze. Mērķa funkcijas koeficientu maiņas robežu noteikšana.

kursa darbs, pievienots 17.12.2014


Matemātiskā programmēšana. Lineārā programmēšana. Lineārās programmēšanas problēmas. Grafiskā metode lineārās programmēšanas uzdevumu risināšanai. Lineārās programmēšanas problēmas ekonomiskais formulējums. Matemātiskā modeļa konstruēšana.

kursa darbs, pievienots 13.10.2008


Lineārās programmēšanas uzdevuma risināšana ar grafisko metodi, pārbaude MS Excel. Problēmas risināšanas iekšējās struktūras analīze programmā. Ražošanas plāna optimizācija. Problēmas risināšana, izmantojot simplekso metodi. Daudzkanālu rindu sistēma.

tests, pievienots 05.02.2012


Lineārās programmēšanas uzdevuma risināšana ar simpleksa metodi: uzdevuma formulējums, ekonomiskā un matemātiskā modeļa konstruēšana. Transporta problēmas risināšana, izmantojot potenciālo metodi: sākotnējā atskaites plāna sastādīšana, tā optimālās vērtības noteikšana.

tests, pievienots 11.04.2012


Nelineārās programmēšanas problēmas izklāsts. Stacionāro punktu un to veida noteikšana. Līmeņu līniju konstruēšana, mērķa funkcijas trīsdimensiju grafiks un ierobežojumi. Problēmas grafiskais un analītiskais risinājums. Lietotāja rokasgrāmata un algoritmu diagramma.

kursa darbs, pievienots 17.12.2012


Lineārās programmēšanas problēmas risinājuma analīze. Simplex metode, izmantojot simpleksas tabulas. LP uzdevumu modelēšana un risināšana datorā. Problēmas optimālā risinājuma ekonomiskā interpretācija. Transporta problēmas matemātiskā formulēšana.