СМРЗДП / Методичні вказівки

Вступ

Cтворення програми в середовищі MATLAB здійснюється за допомогою встроєнного текстового редактора, який викликається автоматично. Вікно редактора появляється на екрані.

Для створення нового файлу вибираєте меню File – New – M-file, або якщо вибрано назву одного із існуючих М-файлів при виклику команди Open – M-file із меню File.

В першому випадку вікно редактора буде пустим, в другому, буде міститись текст вибраного М-файла. В обох випадках вікно текстового редактора готове для вводу нового тексту або корегування існуючого.

На мові MATLAB є програми двох типів: Script – файли (файли сценарії) і файли функції (процедури). Всі програми повинні мати розширення імен файлів. За допомогою Script – файлів оформлюються основні програми, що управляють від початку до кінця організацією всього обчислювального процесу. Як файл-функція оформляються окремі процедури і функції, тобто такі частини програми, які розраховані на неодноразове використання Script – файлами або іншими процедурами, при змінних значеннях вхідних параметрів і не можуть бути виконаними без попереднього задання значень змінних, які називають вхідними.

Головною зовнішньою відмінністю текстів цих двох видів файлів є те, що файл-функція має першу стрічку виду:

function « ПКВ » = « ім’я процедури » («ПВП»)

Script – файл такої стрічки немає. Тут ПКВ – перелік кінцевих величин, ПВВ – перелік вхідних величин.

Основні особливості оформлення М-файлів.

1. Зазвичай кожен оператор записується в окремій стрічці тексту програми. Ознакою кінця оператора є символ «возврат каретки» і перехід у наступну стрічку, який вводиться в програму при натисненні клавіші «Enter».

2. Можна розміщувати декілька операторів в одній стрічці, тоді попередній оператор цієї стрічки повинен закінчуватись символом « ; » або « , ».

3. Довгий оператор можна записувати в декількох стрічках. При цьому попередня стрічка оператора повинна закінчуватись трьома крапками ( … ).

4. Якщо черговий оператор не закінчується символом « ; », результати його дії при виконанні виконанні програми буде виведений в командне вікно. Для того щоб результат дії оператора програми не виводився на екран, запис цього оператора в тексті програми повинен закінчуватись « ; ».

5. Стрічка програми, що починається символом « % » не виконується. Ця стрічка сприймається системою MATLAB як коментар.

6. Стрічки коментаря, що передують першому виконуваному оператору програми ( такому який не є коментарем ) сприймаються MATLAB як опис програми. Саме ці стрічки виводяться в командне вікно, якщо в ньому набрана команда help «ім’я файлу».

7. В програмах на мові MATLAB відсутній оператор закінчення тексту програми.

8. На мові MATLAB змінні не описуються і не оголошуються. Будь-яке нове ім’я, що появляється в тексті програми сприймається системою MATLAB як ім’я матриці. Розмір цієї матриці встановлюється при попередньому вводі значень її елементів або визначаються діями по встановленню значень її елементів, описаними в попередньому операторі чи процедурі.

9. Імена змінних можуть містити лише букви латинського алфавіту або цифри і повинні починатись з букви. Загальне число символів в назві може досягати 19. В іменах можуть використовуватись як великі так і малі букви. Великі і малі букви в іменах розрізняються системою ( наприклад «а» і «А» можуть використовуватись в одній програмі для позначення різних величин).

10. Для відладки (виконання програм) використовують опцію Debug – Save, Run.

Лабораторна 1.

Малювання графа.

Для малювання графів і орграфів використовується функція:

function h = grPlot(V,E,p)

Вхідні параметри :

• V(n,2) або V(n,3) – координати вершин: перший стовпчик х, другий – у. Якщо є третій стовпчик, то це означає , що заданий граф зі зваженими вершинами, і третій стовпчик – це вага вершин. Вершини графа малюються кругами, в яких проставляються: для незваженого графа – номери вершин, а для зваженого – їх вага. Кількість вершин n не задається, воно визначається автоматично за розміром масиву V.

• Е(m,2) або Е(m,3) – список ребер графа (дуг орграфа) і, можливо, їх вага. Перший і другий елементи кожної стрічки – це номери вершин, які з’єднує дане ребро. Третій елемент, якщо він є, це вага ребра. Якщо заданий граф з незваженими ребрами, біля кожного ребра проставляється його номер, а якщо зі зваженими – то вага. Кількість ребер m визначається автоматично за розміром масиву Е. Для графа можна переставити 1-й та 2-й елементи кожної стрічки. Для орграфа вважатимемо, що початок кожної дуги - в вершині, номер якої заданий 1-м елементом, а кінець – 2-м.

• Р – символ, який визначає, що малювати: “d” – орграф, “ ” – граф. Це необов’язковий параметр, по замовчуванню малюємо граф.

Вихідний параметр h – дескриптор заданої фігури.

Алгоритм роботи функції наступний. Визначаються границі малюнка. Знаходиться мінімальна відстань між вершинами. Задається радіус кругів, якими будуть малюватись вершини, як 0.1 від мінімальної відстані між вершинами. Із списка ребер видаляються петлі (вони малюються окремо). Ребра малюються так, щоб 1-а вершина була менша 2-ї, 1-і номери йшли в порядку зростання, а при однакових 1-х номерах 2-і йшли також в порядку зростання. Це дає можливість виявити кратні ребра. Петлі також малюються в порядку зростання вершин. Малюємо вершини кругами, пароставляємо в кожному з них номер вершини або її вагу. Прості ребра малюємо відрізками прямих, а кратні - дугами різних радіусів. Петлі малюємо дугами кругів, причому кратні – різними радіусами. Якщо заданий орграф, замість ліній малюємо стрілки.

Розглянемо приклад малювання орграфа зі зваженими дугами.

Текст програми:

%Лабораторна робота №1

%Виконав ____________

%Варіант ____

clear all

V=[1 2; 1 1; 2 2; 2 1; 3 2; 3 1; 4 2; 4 1];

E=[1 2 1; 1 3 2; 1 4 3; 2 4 4; 4 3 5; 3 5 6; 3 6 7; 4 6 8; 5 6 9; 6 8 10; 5 7 11; 5 8 12; 7 8 13];

grPlot(V,E,'d','%d','%d'),

Мал.1 - Вихідний граф із зваженими вершинами

Лабораторна 2.

Максимальне паропоєднання.

Мінімальне вершинне покриття.

Задача про максимальне паро поєднання формулюється наступним чином: для заданого графа потрібно знайти таку підмножину ребер максимальної потужності, в якому ніякі два ребра не будуть інцидентні. Узагальненням цієї задачі є задача про максимальне зважене паропоєднання , коли потрібно знайти підмножину ребер максимальної сумарної ваги, серед яких немає інцидентних.

Дану задачу сформулюємо як задачу цілочисельного лінійного програмування. Введемо в розгляд змінні, асоційовані з ребрами. Позначимо їх так як і ребра : Кожне з них може приймати одне з двох значень: 1, якщо відповідне ребро входить в максимальне паропоєднання, і 0 , якщо ні. Тоді задача про максимальне реберне покриття зводиться до максимізації лінійної функції:

(1)

при умові, що в кожній вершині сума інцидент них їй змінних (ребер) не перевищують одиниці. Це обмеження можна записати у вигляді:

(2)

Тут А – матриця інцидентності графа розміром , е – вектор-стовпець змінних , 1 – одиничний вектор потрібної розмірності. В матриці інцидентності А елемент , якщо вершина інцидентна ребру і в протилежному випадку. Крім того на змінні накладаються умови цілочисельності:

(3)

Задача про максимальне зважене паро поєднання відрізняється тільки цільовою функцією: замість (1) маємо:

(4)

Розроблена функція по заданій структурі графа (і, при необхідності, вагах ребер) будує цільову функцію виду (1) або (4) і обмеження (2), доповнені умовами цілочисельності (3). Далі розв’язується задача ЦЛП, а результати повертаються в викликаючу програму. Заголовок функції:

function nMM=MaxMatch(E)

Вхідний параметр E(m,2) або E(m,3) – список ребер графа і, можливо. Їх вага. Якщо заданий граф з незваженими ребрами, вважатимемо, що всі ваги – одиничні. Вихідний параметр nMM – список номерів ребер, що входять в максимальне паро поєднання ( вектор-стовпець).

Для графа з мал.1 розв’язок задачі про максимальне паропоєднання виглядає так:

В задачі про мінімальне вершинне покриття потрібно знайти підмножину вершин мінімальної потужності, які були б інцидентні всім ребрам графа. Узагальнення – задача про мінімальне зважене вершинне покриття, коли потрібно мінімізувати сумарну вагу вершин, що входять в .

Дана задача також може бути приведена до задачі ЦЛП. Для цього введемо в розгляд змінні, асоційовані з вершинами. Ми їх позначимо так, як і вершини: . Кожна з них може приймати одне з двох значень: 1, якщо відповідна вершина входить в мінімальне вершинне покриття, і 0 , якщо ні. Маємо задачу ЦЛП: потрібно мінімізувати загальну кількість вершин:

(5)

при умові, що кожному ребру інцидент на хоча б одна вершина, т.т. сума , інцидент них кожному ребру, не менша одиниці. Це обмеження можна записати так:

(6)

де - вектор-стовпець змінних . Обмеження (6) доповнюються умовами цілочисельності змінних:

(7)

Для зваженої задачі замість цільової функції (5) маємо:

(8)

де d – вектор ваг вершин.

Функція MATLAB для розв’язку цієї задачі за заданою структурою графа (і, при необхідності, вагах вершин) будує цільову функцію виду (5) або (8) і обмеження (6), доповнені умовами цілочисельності (7). Далі розв’язується задача ЦДП, результати повертаються в викликаючи програму. Заголовок функції:

function nMC=MinVerCover(E,d)

Вхідні параметри:

• E(m,2) – список ребер графа, як в функції grPlot.

• d - вага вершин (необов’язковий параметр). Якщо вага не задана, то вона вважається рівною одиниці.

Вихідний параметр nMC – список номерів вершин, що входять в мінімальне вершинне покриття.

Для графа з мал.1 розв’язок задачі про мінімальне вершинне покриття можна отримати так:

Текст програми:

%Лабораторна робота №2

%Виконав ____________

%Варіант ______

clear all

V=[1 2; 1 1; 2 2; 2 1; 3 2; 3 1; 4 2; 4 1];

d=[1;2;3;4;5;6;7;8];

E=[1 2 1; 1 3 2; 1 4 3; 2 4 4; 4 3 5; 3 5 6; 3 6 7; 4 6 8; 5 6 9; 6 8 10; 5 7 11; 5 8 12; 7 8 13];

grPlot(V,E,'d','%d','%d'),

set(get(gcf,'CurrentAxes'),'FontName','Times New Cyr','FontSize',10)%установили шрифт

title('\bf Вихідний граф зі зваженими вершинами')

nMC=grMinVerCover(E,d);

fprintf('Кількість вершин в мінімальному вершинному покриті= %d\n',...

length(nMC));

disp('В мінімальне вершинне покриття ввійшли вершини з номерами');

fprintf('%d ' ,nMC);

fprintf('\nЗагальна вага=%d\n',sum(V(nMC,2)));

grPlot(V(nMC,:));%Малюємо

set(get(gcf,'CurrentAxes'),'FontName','Times New Cyr','FontSize',10)

title('\bf Мінімальне вершинне покриття')

Мал. 1 - Вихідний граф із зваженими вершинами

Мал. 2 – Мінімальне вершинне зважене покриття