Sveikaskaitinis programavimas

 Kauno Technologijos universitetas informatikos fakultetas Operacijų tyrimas Namų darbas Nr.2 Sveikaskaitinis programavimas Atliko: Priėmė: doc. I.Mikuckienė 2004.04.09 1. Ribų ir šakų metodas bei algoritmas Tai metodas naudojamas pilnai ar dalinai sveikaskaitinio tiesinio programavimo uždaviniui (SVTPU) spręsti. Jo efektyvumas tame,kad parenka tik visus leistinus sveikaskaitinius sprendinius. Turėdami SVTPU: I Sprendžiamas TPU–1. Gauta tikslo funkcijos Z1 reikšmė yra viršutinė tikslo funkcijos riba. II Atliekamas šakojimasis, kol vienoje iš viršūnių gaunamas sveikaskaitinis optimalus sprendinys. Jį atitinkanti tikslo funkcijos reikšmė Z vadinama apatine pradinio TPU–1 optimalios reikmės riba. Čia atmetamos visos viršūnės, kuriose optimali funkcijos reikšmė neviršija šios apatinės ribos, nes jose nėra sveikaskaitinių sprendinių didesnių už šį gautąjį. III Viršūnė laikoma patikrinta, kai tenkinama viena iš šių sąlygų: a) Gautas sveikaskaitinis sprendinys b) Nėra galimų sprendinių srities, t.y. neegzistuoja GSS. c) Optimali reikšmė mažesnė už apatinę ribą Šakojimasis tęsiamas tol, kol egzistuoja bent viena nepatikrinta viršūnė. IV Optimali SVTPU reikšmė yra didžiausia tikslo funkcijos reikšmė, gauta viršūnėje, tenkinančioje TPU–1 apribojimus 2. Galimų sprendinių srities formavimas Turime dvimatę tikslo funkciją ir kintamųjų (resursų) apribojimus: Mūsų tikslas būtų: a) Sudaryti naują GSS, atsižvelgiant į gautus optimalius sprendinius; b) Rasti tikslo funkcijos optimalius sprendinius ir juos atitinkančią optimalią reikšmę; c) Visa tai kartojame kol tenkinama pirmo punkto (pateikto algoritmo) III-ioji dalis; 3. Sprendinių medis Šakų ir ribų metodą patogu atvaizduoti medžiu su viršūnėmis. TPU – 1 Z1 = 19,5 X1 = 1,5 X2 = 4,5 X11 X12 TPU – 2 TPU – 3 Z2 = 17,8 Z3 = 18 X1 = 1 X1 = 2 X2 = 4,2 X2 = 4 X24 X25 TPU – 5 TPU – 4 Z5 = 18 X1 = 2 Neegzistuoja X2 = 4 4. MATLAB programų tekstai Funkcija antras.m – formuoja atskiras GSS ir atlieka jų analizę. clc; clear all; close all; f=[-1; -4]; A=[1 1 2 -1 -3 5]; b=[6; 2; 18]; % TP-1 figura ('Pradine GSS'); Z = [1.5; 2.67; 1; 1; 0; 0]; C = [4.5; 3.33; 0; 0; 0; 3.6]; GSS('TP-1', Z, C, 'b'); [opt1, Z1]=optimalus(f, A, b); [tx, ty]=tiese(f', Z1, 1); plot(tx, ty, '-b'); plot(opt1(1),opt1(2),'kh'); legend('Z1=19.5','X1=1.5','X2=4.5'); pause % TP-2, kai x1=3 figura ('TP-3, kai X1>=2'); [TP31, TP32]=polybool('intersection', Z, C, [2 2 10 10]', [0 10 10 0]'); fill([2 10 10 2],[0 0 10 10],'r'); GSS('TP-3', Z, C, 'b'); GSS('TP-3', TP31, TP32, 'c'); A=[1 1 2 -1 -1 0]; b=[6; 2; -2]; [opt3, Z3]=optimalus(f, A, b); disp('TP3 susikirtimo taskas'); disp(opt3); disp('TP3 Z reiksme'); disp(Z3); [tx, ty]=tiese(f', Z3, 1); plot(tx, ty, '-b'); plot(opt3(1),opt3(2),'kh'); legend('Z3=18','X1=2','X2=4'); text(2.2,3,'GSS-3'); pause % TP-4, kai x2>=5 figura ('TP-4, kai X2>=5'); [TP41, TP42]=polybool('intersection', Z, C, [5 0 0 5]', [0 0 10 10]'); fill([0 0 10 10],[5 10 10 5],'r'); GSS('TP-4', Z, C, 'b'); GSS('TP-4', TP41, TP42, 'c'); legend('neegzistuoja'); %text(3,5,'GSS-4'); pause % TP-5, kai x2

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!