Tiesinis programavimas

Namų darbas Nr.1 Tiesinis programavimas Atliko: Priėmė: doc. I.Mikuckienė 2004.03.26 1. Grafinė sprendinio interpretacija Mūsų tikslas būtų: a) GSS sudarymas; b) Rasti tikslo funkcijos optimalų sprendinį ir jį atitinkančią optimalią reikšmę; c) atlikti resursų (deficitinių ir nedeficitinių) analizę; d) deficitinių resursų papildomo vieneto kainos analizę; e) atlikti tikslo funkcijos koeficientų analizę. 1.1. Galimų sprendinių srities formavimas. 1.2. Optimalus sprendinys ir jį atitinkanti optimali reikšmė Sprendinys, gali būti tik ant GSS ribos. Be to, optimalus sprendinys visada yra viršūnėje. Todėl norint rasti optimalų sprendinį, pakanka išnagrinėti visas GSS viršūnes. Mūsų nagrinėjamą GSS sudaro 5 apribojimai, tai turime rasti 5 taškų (A, B, C, D, E) koordinates. A = ( 1.5; 4.5) B = (2.6667; 3.3333) C = (1; 0) D = (1; 0) E = (0; 3.6) Suradę daugiakampio viršūnių koordinates, apskaičiuojame tikslo funkcijos reikšmes šiuose taškuose. Maksimali funkcijos reikšmė atitiks optimalią tikslo funkcijos reikšmę, o atitinkamas taškas – optimalų sprendinį. Taigi, tikslo funkcijos reikšmės taškuose: A: . B:. C:. D:. E:. Kaip matome iš gautų rezultatų, tikslo funkcijos optimali reikšmė – , o jį atitinkantis optimalus sprendinys, tai taško A koordinatės – . 1.3. Deficitinių resursų analizė Šio metodo analizė – kiek galima didinti deficitinių resursų atsargas, kad pagerėtų optimali reikšmė. Be to, tiesinio programavimo uždavinio (TPU) apribojimai klasifikuojami į aktyvius (deficitinius) ir neaktyvius (nedeficitinius). Apribojimas laikomas aktyviu, jei jo tiesė eina per optimumo tašką (šiuo atveju per tašką A). Jei apribojimai aktyvūs, tai jie yra deficitiniai, nes visas šiuos apribojimus atitinkantis resursas yra sunaudojamas. Taigi, deficitinius resursus atitinka pirmas (A resursas) ir trečias (B resursas) apribojimai. Taigi, A resurso analizė, kai kiti resursai nekinta, t.y. Bres = 18 = const. Randame taško F koordinates, išsprendę trečio ir ketvirto apribojimų lygčių sistemą: (4;6) . . Optimalus sprendinys bus pirmo ir trečio apribojimų susikirtimo taške, jei , kai Bres = 18 = const. B resurso analizė, kai likę resursai nekinta, t.y. Ares = 6 = const. Randame taško G koordinates, išsprendę pirmo ir penkto apribojimų lygčių sistemą: G(0; 6) . Turėdami taško B koordinates, randame . B resursai gali kisti , kai Ares = 6 = const. Nustatyti deficitinių resursų A ir B kitimo intervalai, kuriuose optimalus reiškinys išlieka aktyvių apribojimų susikirtimo taške. 1.4. Nedeficitinių resursų analizė Resursai, kurie asocijuojasi su neaktyviu apribojimu, laikomi nedeficitiniais, t.y. pertekliniais. Mūsų atveju, perteklinį resursą atitiktų antras apribojimas. Taigi, tikslas – sužinoti, kiek galima mažinti nedeficitinio resurso atsargas, kad turima tikslo funkcijos reikšmė nepakistų. Keičiant šiuos resursus, optimalus sprendinys turi išlikti aktyvių apribojimų susikirtimo taške. Taigi, turėdami optimalų sprendinį ir įstatę jį į neaktyvaus resurso, lygtį, gauname atsakymą, kuris leidžia sužinoti, kiek galima pakeisti nedeficitinių resursų kiekį. . Kadangi nedeficitinių resursų kiekis lygus 2, o galime sumažinti 3,5, tai galime teigti, kad šio resurso galime ir nenaudoti, nes jo nebuvimas neturi jokios įtakos optimaliai tikslo funkcijos reikšmei. 1.5. Deficitinių resursų papildomo vieneto kainos analizė Tai resurso vieneto santykinė kaina. Kitaip dar vadinama dualia arba šešėline kaina. Šešėlinė kaina parodo resurso vieneto pelningumą ir išreiškiama per tikslo funkcijos optimalios reikšmės pokytį, t.y. kiek deficitinį resursą padidinus vienetu, pakinta tikslo funkcijos reikšmė. E(0; 3,6) F(6; 0) G(0; 6) Taigi, A resurso papildomo vieneto kaina: . A resursui pakitus vienu vienetu intervale [3,6; 10], kai Bres = 18 = const, optimali reikšmė pakis 2,125. B resurso papildomo vieneto kaina: . B resursui pakitus vienu vienetu intervale [8,67; 30], kai Ares = 6 = const, optimali reikšmė pakis 0,375. 1.6. Tikslo funkcijos koeficientų analizė Tikslas – nustatyti tikslo funkcijos () koeficientų c1 ir c2 kitimo intervalus, kad optimalus sprendinys išliktų tame pačiame taške. Tiriame tik po vieną koeficiento kitimo intervalą atskirai. Koeficientų intervalams nustatyti naudojamės šia sąlyga: , , kur , , , , , . Koeficiento c1 kitimo ribos: , kai c2 = 4 = const. Koeficiento c2 kitimo ribos: , kai c1 = 1 = const. Koeficientų c1 ir c2 kitimo ribos pavaizduotos grafike. 2. TPU sprendimo rezultatai Kinatamieji Optimalūs sprendiniai Z koeficientai Įtaka x1 1,5 1 1,5  8,3 % x2 4,5 4 18  91,7 % Apribojimai Resursai Resursų mažinimas/didinimas 1 6 0 2 2 3,5– 3 18 0 Sprendinių jautrumo analizės rezultatai Kinatamieji Z koeficientai min(Z) c max(Z) c x1 1 -2,4 4 kai c2 = 4 = const x2 4 1  kai c1 = 1 = const Apribojimai Resursai minres maxres Šešėlinė kaina 1 6 3,6 6 2,125 2 5 0  0 3 18 18 30 0,375 3. MATLAB programos tekstas clc; close all; clear all; x1=0:1:12; x2=6-x1; x3=-2+2*x1; x4=(18-5*x1)/-3; figure plot(x1,x2,x4,x1,x1,x3);%,x1,x3,x1,x4); hold on; grid on; axis equal; axis([0 13 0 13]); title('TPU grafinis vaizdavimas (Nr.12)','Fontsize',14,'Fontname','Times New Roman Baltic'); text(-0.5,13.5,'X2'); text(13.5,-0.5,'X1'); disp(' Pradiniai duomenys:'); disp(' '); disp(' max Z=x1+4*x2'); disp(' x1+x2=max) max = ZZ; viet=[X(i) Y(i)]; raid=K(i); j=i; end end disp('*************************************'); disp([' Optimalus sprendiniai taske ',raid,': X1=', num2str(viet(1)), ' X2=', num2str(viet(2))]); disp([' Optimali funkcijos reiksme: max Z(',raid,')=',num2str(max)]); disp(' '); z=-4*(x2-viet(1))+viet(2); text(1,7,'x1+4*x2=0'); plot(x2,z,'m--'); disp('*************************************'); disp(' Deficitiniu resursu analize (A resursas(3 apribojimas) ir B resursas(1 apribojimas))'); disp(' '); text(0.5,6,'A res=6','Fontsize',9,'Fontname','Times New Roman Baltic'); disp(' -------------------------------------'); disp(' A resurso analize, kai Bres=18=const'); F=[-3 5; 2 -1]\[18;2]; Ares_max=[1 1]*F plot(F(1),F(2),'mp'); text(F(1)+0.1,F(2)+0.1,'F','Fontsize',12,'Fontname','Times New Roman Baltic'); x2=Ares_max-x1; plot(x2,x1); text(5,5,['A res_m_a_x=',num2str(Ares_max)],'Fontsize',9,'Fontname','Times New Roman Baltic'); E=[-3 5;1 0]\[18;0]; Ares_min=[1 1]*E x2=Ares_min-x1; plot(x1,x2); text(0.7,2.9,['A res_m_i_n=',num2str(Ares_min)],'Fontsize',9,'Fontname','Times New Roman Baltic'); disp(' -------------------------------------'); text(6.9,1.5,'B res=18','Fontsize',9,'Fontname','Times New Roman Baltic'); disp(' B resurso analize, kai Ares=6=const'); G=[1 1; 1 0]\[6;0]; Bres_max=[-3 5]*G plot(G(1),G(2),'mp'); text(G(1)+0.2,G(2)+0.2,'G','Fontsize',12,'Fontname','Times New Roman Baltic'); x4=(Bres_max+5*x1)/3; plot(x3,x4,'r'); text(1,12,['B res_m_a_x=',num2str(Bres_max)],'Fontsize',9,'Fontname','Times New Roman Baltic'); Bres_min=[-3 5]*B x4=(Bres_min-5*x1)/-3; plot(x4,x4,'r'); text(8,8,['B res_m_i_n=',num2str(Bres_min)],'Fontsize',9,'Fontname','Times New Roman Baltic'); disp('*************************************'); disp(' Nedeficitiniu resursu analize (2 apribojimas)'); delta2=2+[-2 1]*A disp(' Nedeficitiniai resursai optimaliai reiksmei itakos neturi!'); disp(' '); disp('*************************************'); disp(' Deficitiniu resursu papildomo vieneto kainos analize'); disp(' '); disp([' A resurso: ', num2str(([1 4]*A-[1 4]*E)/([1 1]*A-[1 1]*E))]); disp([' B resurso: ', num2str(([1 4]*B-[1 4]*G)/([-3 5]*B-[-3 5]*G))]); disp(' '); disp('*************************************'); disp(' Tikslo funkcijos koeficientu analize'); disp(' '); disp([' ',num2str(-3*4/5),'

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!