Московський Авіаційний Інститут
(Технічний Університет)
Кафедра 308
Курсова робота
Вибір параметрів контролю з використанням методу динамічного програмування і методу гілок і меж
Варіант II (2)
групи КТ-515
Прийняв
Зміст
Завдання
1. Метод динамічного програмування
1.1 Теоретична частина
2.2 Практична частина
- Ручний рахунок
- Лістинг програми
2. Метод гілок і меж
2.1 Теоретична частина
2.2 Практична частина
- Ручний рахунок
- Лістинг програми
Висновок
Література
Завдання
Варіант II (2)
Вибір параметрів контролю з використанням методу динамічного програмування і методу гілок і меж при непересічних елементах об'єкту контролю і обмеження по витратах на контроль З ≤ 16.
Вихідні дані: вірогідність відмов елементів і витрати на контроль параметрів.
1. Метод динамічного програмування
1.1 Теоретична частина
Математично завдання вибору набору параметрів із заданої їх сукупності можна сформулювати наступним чином.
Нехай працездатність об'єкта контролю характеризується сукупністю n взаємопов'язаних параметрів, що утворюють множину S = {x 1, x 2, ..., x n}. Перевірка всіх параметрів з S тягне контроль всіх N елементів системи і дає однозначну відповідь: об'єкт справний, якщо все N елементів справні, або несправний, якщо принаймні один з елементів відмовив. Для "x i визначено підмножина R (x i) елементів, що перевіряються при контролі i-го параметра, причому припускаємо, що ці підмножини можуть перетинатися, тобто $ i, j: R (x i) ÇR (x j). Нехай W - деякий набір параметрів з множини S, тобто WÍS. Тоді WÇW = Æ і WÈW = S. Значення x i з S можна представити булевим вектором, причому
x i = 1, якщо x i ÎW,
0, якщо x i ÎW.
Завдання вибору параметрів у цьому випадку формулюється двояко:
1) знайти набір Ω, для якого
P (Ω) = max
при Σx i · c (x i) ≤ C; iЄΩ
2) знайти набір Ω, для якого
Σx i · c (x i) = min
при P (Ω) ≥ P з,
де P (Ω) - апостеріорна ймовірність працездатного стану об'єкта контролю при позитивному результаті контролю вибраних параметрів WÍS; с (x i) - витрати на контроль i-го параметра; Р з - необхідна достовірність контролю; С - обмеження на загальну вартість контролю.
Значення P (Ω) залежить від прийнятих припущень і може бути знайдено за формулою Байєса. Так, якщо припускати у виробі наявність лише однієї відмови, то
P (Ω) = Р 0 / 1-ΣР i,
iЄR (Ω)
де Р 0 = Π (1-р i) - апріорна ймовірність безвідмовної роботи об'єкта:
iЄR (S)
Р 0 = 1-ΣР i;
iЄR (S)
Q k = ΣP k
kЄR (x k)
При можливості наявності в ОК довільного числа відмов
P (Ω) = Π (1-p i) / Π (1-p i)
iЄR (S) iЄR (Ω)
Можна використовувати простий перебір варіантів, однак виникають при цьому обчислювальні труднощі не дозволяють зробити цього навіть для простих систем (при n> 10). У зв'язку з цим комплектування набору будемо трактувати як багатокроковий процес, що складається з послідовного вибору окремих параметрів.
Відповідно до загального принципу оптимальності розіб'ємо весь наявний ресурс вартості З на С відрізків одиничної довжини. (У практичних випадках задані позитивні величини з (x i) і С можна вважати завжди цілими. Якщо це не так, то необхідно перейти до більш дрібним вартісним одиницям залежно від розрядності дробової частини.). Розглянемо поряд з цікавій для нас вихідної завданням безліч аналогічних завдань
f (Y) = max λ (x), Y Є [0, C],
xЄX Y
де через X Y позначено множину невід'ємних цілочисельних векторів Ω, що відповідають наборам, до яких загальна вартість перевірки параметрів не перевершує величини Υ.
Нехай Υ 0 = min c (x i).
i = 1, ..., n
Тоді при всіх Υ Є [0, Υ 0] відповідні множини Χ Υ складаються, з одного нульового елемента і f (Y) = 0 для всіх таких Υ. Для ресурсу Υ Є [Υ 0, С] за загальною схемою динамічного програмування справедливі наступні рекурентні співвідношення:
f (Y k) = max [Q i + f [Y k - c (x i)] - G i (1)
iЄI Y
де k = Y 0, Y 0 +1, ..., C; I Y - безліч тих i, для яких з (x i) ≤ Y k, починаючи з номера k = max c (x i) рівняння (1) вирішується для всіх i = 1, ..., n;
G i = ΣP i - сума ймовірностей елементів i-го параметра, які перетинаються з
IЄR (x i) ∩ Ω l *
елементами підмножини Ω l *, утвореного на кроці Y k - c (x i).
Якщо "i, j; R (x i) ∩ R (x j) = Æ, то G i = 0 і
f (Y k) = max {Q i + f [Y k - c (x i)]} (2)
iЄI Y
Для вирішення цікавить нас завдання опишемо простий чисельний метод, який не потребує попереднього визначення всіх допустимих наборів і заснований на рекурентних співвідношеннях (1). Для всіх цілих Υ = Υ 0, С за формулою (1) обчислюються величини f (Y k) і при цьому фіксуються індекси i Yk *, на яких досягаються максимуми в (1). Шуканий вектор Ω формується послідовно включенням в набір параметра i Yk і підмножини Ω l *, зафіксованого на кроці Y k - c (x i). При цьому, якщо Y k Є Ω l *, то на даному кроці цей параметр виключається з розгляду, тому що кожен параметр може включатися в набір не більше одного разу. Якщо на деякій ν-му кроці виявиться, що f (Y ν) <f (Y ν -1), то в якості Ω ν * приймається підмножина Ω ν -1 * і фіксується параметр i Y ν -1, причому за f ( Y ν) <приймається значення f (Y ν -1). Зауважимо, що якщо в задачі P (Ω) = max при
Σx i · c (x i) ≤ C
iЄΩ
прийняти більш жорстке обмеження, а саме Σc (x i) = C, то останнє не допустимо, iЄΩ так як в цьому випадку max f (Y k) може бути менше max f (Y k -1) через те, що він досягається на іншому підмножині параметрів.
Загальна складність методу, очевидно, φ (n) ≤ c (n +1), тобто експонентна функція при переборі замінена лінійної функцією. При цьому для запам'ятовування проміжних значень необхідно k ≤ 2c осередків пам'яті. Якщо в якості максімізіруемого критерію використовувати P (Ω) = Π (1-p i) / Π (1-p i), то необхідно вирішити задачу динамічного iЄR (S) iЄR (Ω) програмування з мультиплікативним критерієм. Для цього достатньо прологаріфміровать цей вислів і позначити
V = lgP (Ω) = lgР 0-Σlg (1-p i). (3)
iЄR (Ω)
Так як вираз, що стоїть під знаком Σ в (3), негативно, то, V = V max тоді, коли максимальна величина суми, тобто в цьому випадку отримаємо нову цільову функцію
V = Σν i, де ν i = lg (1-p i),
iЄR (Ω)
володіє властивістю адитивності і обертається в максимум одночасно з P (Ω).
1.2 Практична частина
Ручний рахунок
Дані для розрахунку:
Обчислення зведемо в таблицю 3:
Оптимальний набір включає параметри Ω * = {1,2,7,3,4,10,9} при цьому
P (Ω) = 0,61 +0,16 = 0,77 і С = 16.
Лістинг програми
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ToolWin, ComCtrls, mdCONTROLS, Grids, StdCtrls, ExtCtrls, Unit2,
Buttons;
type
TForm1 = class (TForm)
sgH: TStringGrid;
sgP: TStringGrid;
sgC: TStringGrid;
sgQ: TStringGrid;
lbC: TLabeledEdit;
BitBtn1: TBitBtn;
Label1: TLabel;
sgW: TStringGrid;
Label2: TLabel;
procedure FormCreate (Sender: TObject);
procedure BitBtn1Click (Sender: TObject);
procedure sgExit (Sender: TObject);
private
{Private declarations}
public
H: TH;
P: TP;
C: TC;
W: TW;
end;
var
Form1: TForm1;
implementation
{$ R *. dfm}
procedure TForm1.FormCreate (Sender: TObject);
var i, j: integer;
x: Byte;
f: TextFile;
begin
AssignFile (f, 'data.txt');
Reset (f);
sgW.Cells [0,0]: = 'W';
/ / Введення вихідної матриці
readln (f);
for j: = 1 to 10 do
begin
sgH.Cells [0, j]: = IntToStr (j);
sgW.Cells [0, j]: = IntToStr (j);
for i: = 1 to 10 do
begin
sgH.Cells [i, 0]: = IntToStr (i);
read (f, x);
sgH.Cells [i, j]: = IntToStr (x);
if x = 1 then
H [i-1, j-1]: = true
else
H [i-1, j-1]: = false;
end;
readln (f);
end;
/ / Введення ймовірностей
readln (f);
readln (f);
sgP.Cells [0,0]: = 'P';
for i: = 1 to 10 do
begin
read (f, P [i-1]);
sgP.Cells [i, 0]: = FloatToStr (P [i-1]);
end;
readln (f);
/ / Введення вартостей
readln (f);
readln (f);
sgC.Cells [0,0]: = 'C';
for j: = 1 to 10 do
begin
read (f, C [j-1]);
sgC.Cells [0, j]: = IntToStr (C [j-1]);
end;
CloseFile (f);
/ / Введення ймовірностей виявлення відмови
sgQ.Cells [0,0]: = 'Q';
for j: = 1 to 10 do
sgQ.Cells [0, j]: = FloatToStr (Q (j-1, H, P));
lbC.Text: = '1 ';
end;
procedure TForm1.BitBtn1Click (Sender: TObject);
var i: integer;
begin
label1.Caption: = FloatToStr (maxf (1, StrToInt (lbC.Text), H, P, C, W));
for i: = 1 to 10 do
begin
sgW.Cells [2, i]: = IntToStr (W [i-1]. N);
if W [i-1]. E then
sgW.Cells [1, i]: = '1 '
else
sgW.Cells [1, i]: = '0 ';
end;
end;
procedure TForm1.sgExit (Sender: TObject);
var i, j: integer;
begin
for j: = 1 to 10 do
for i: = 1 to 10 do
if sgH.Cells [i, j] = '1 'then
H [i-1, j-1]: = true
else
H [i-1, j-1]: = false;
for i: = 1 to 10 do
P [i-1]: = StrToFloat (sgP.Cells [i, 0]);
for j: = 1 to 10 do
C [j-1]: = StrToInt (sgC.Cells [0, j]);
/ / Введення ймовірностей виявлення відмови
for j: = 1 to 10 do
sgQ.Cells [0, j]: = FloatToStr (Q (j-1, H, P));
end;
end.
unit Unit2;
interface
type
TH = array [0 .. 9, 0 .. 9] of boolean;
TP = array [0 .. 9] of extended;
TC = array [0 .. 9] of integer;
TDateW = record
E: boolean;
N: integer;
end;
TW = array [0 .. 9] of TDateW;
function Q (j: integer; H: TH; P: TP): extended;
function maxf (n, Yk: integer; H: TH; P: TP; C: TC; var W: TW): extended;
implementation
function Q (j: integer; H: TH; P: TP): extended;
var i: integer;
begin
Result: = 0;
for i: = 0 to 9 do
if H [i, j] then
Result: = Result + P [i];
end;
function G (j: integer; H: TH; P: TP; W: TW): extended;
var i, k: integer;
begin
Result: = 0;
for i: = 0 to 9 do
if H [i, j] then
for k: = 0 to 9 do
if W [k]. E and H [i, k] then
begin
Result: = Result + P [i];
Break;
end;
end;
function f (n, Yk, j: integer; H: TH; P: TP; C: TC; var W: TW): extended;
begin
Result: = Q (j, H, P) + maxf (n +1, Yk - C [j], H, P, C, W) - G (j, H, P, W);
end;
function maxf (n, Yk: integer; H: TH; P: TP; C: TC; var W: TW): extended;
var j, i: integer;
ft: extended;
Wt: TW;
begin
Result: = 0;
for i: = 0 to 9 do
begin
W [i]. E: = false;
W [i]. N: = 0;
end;
for j: = 0 to 9 do
if C [j] <= Yk then
begin
for i: = 0 to 9 do
begin
Wt [i]. E: = false;
Wt [i]. N: = 0;
end;
ft: = f (n, Yk, j, H, P, C, Wt);
if Result <ft then
begin
Result: = ft;
W: = Wt;
W [j]. E: = true;
W [j]. N: = n;
end;
end;
end;
end.
2. Метод гілок і меж
2.1 Теоретична частина
Розглянемо таку задачу цілочисельного програмування. Потрібно максимізувати вираз:
n
L = Σc j ∙ x j (4)
j = 1
при обмеженнях
n
Σа ij ∙ x j ≤ b i, i = 1, ..., m (5)
j = 1
x j Є {0, 1}, j = 1, ..., n
причому з j ≥ 0, a ij ≥ 0.
Метод гілок і меж використовує послідовно-паралельну схему побудови дерева можливих варіантів. Спочатку шукають допустимий план і для кожного можливого варіанту визначають верхню межу цільової функції. Гілки дерева можливих варіантів, для яких верхня межа нижче наближеного рішення, з подальшого розгляду виключають.
Ефективність обчислювальних алгоритмів залежить від точності і простоти способу визначення верхньої межі можливих рішень і точності визначення наближеного рішення. Чим точніше спосіб визначення верхньої межі цільової функції, тим більше безперспективних гілок відсікається в процесі оптимізації. Однак збільшення точності розрахунку верхніх меж пов'язано зі зростанням обсягу обчислень. Наприклад, якщо для оцінки верхньої межі використовувати симплекс-метод, то результат буде досить точним, але зажадає великого обсягу обчислювальної роботи.
Розглянемо алгоритм вирішення задачі методом гілок і меж з простим і ефективним способом оцінки верхньої межі цільової функції.
Позначимо: U - множина змінних x j; S - безліч фіксованих змінних, що увійшли до допустиме рішення; E s - безліч залежних змінних, які не можуть бути включені в безліч S, так як для них виконується нерівність
а ij> b i - Σа ij ∙ x j, i = 1, ..., m
x j Єs
G S - безліч вільних змінних, з яких проводиться вибір для включення в S черговий змінної.
Розглянемо спочатку одновимірну задачу, коли m = 1 і завдання (4) має тільки одне обмеження виду (5).
Позначимо h 1 j = c j / a 1 j і припустимо, що x j Єs (j = 1, ..., k <n) і виконуються умови
h 1, k +1 ≥ h 1, k +2 ≥ ... ≥ h 1 l, l ≤ n,
l
Σa 1 j> b 1 - Σ a 1 j ∙ x j,
j = k +1 x j Єs
l-1
Σa 1 j ≤ b 1 - Σ a 1 j ∙ x j,
j = k +1 x j Єs
Умови означають, що в безліч S без порушення нерівності (5) можна додатково ввести елементи x k +1, x k +2, ..., x l -1. При введенні в безліч S елементів x k +1, x k +2, ..., x l нерівність (5) не виконується.
Для визначення верхньої межі рішення може бути використано вираз
H s = Σc j ∙ x j + L s ',
(Технічний Університет)
Кафедра 308
Курсова робота
Вибір параметрів контролю з використанням методу динамічного програмування і методу гілок і меж
Варіант II (2)
Виконала
студенткагрупи КТ-515
Прийняв
Москва
2008р.Зміст
Завдання
1. Метод динамічного програмування
1.1 Теоретична частина
2.2 Практична частина
- Ручний рахунок
- Лістинг програми
2. Метод гілок і меж
2.1 Теоретична частина
2.2 Практична частина
- Ручний рахунок
- Лістинг програми
Висновок
Література
Завдання
Варіант II (2)
Вибір параметрів контролю з використанням методу динамічного програмування і методу гілок і меж при непересічних елементах об'єкту контролю і обмеження по витратах на контроль З ≤ 16.
Вихідні дані: вірогідність відмов елементів і витрати на контроль параметрів.
Вибрати такі параметри, щоб З ≤ 16 при Q = Q max.
N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Qi | 0.17 | 0.03 | 0.15 | 0.09 | 0.13 | 0.08 | 0.07 | 0.02 | 0.06 | 0.04 |
| с (xi) | 5 | 1 | 4 | 2 | 6 | 3 | 2 | 3 | 1 | 1 |
1. Метод динамічного програмування
1.1 Теоретична частина
Математично завдання вибору набору параметрів із заданої їх сукупності можна сформулювати наступним чином.
Нехай працездатність об'єкта контролю характеризується сукупністю n взаємопов'язаних параметрів, що утворюють множину S = {x 1, x 2, ..., x n}. Перевірка всіх параметрів з S тягне контроль всіх N елементів системи і дає однозначну відповідь: об'єкт справний, якщо все N елементів справні, або несправний, якщо принаймні один з елементів відмовив. Для "x i визначено підмножина R (x i) елементів, що перевіряються при контролі i-го параметра, причому припускаємо, що ці підмножини можуть перетинатися, тобто $ i, j: R (x i) ÇR (x j). Нехай W - деякий набір параметрів з множини S, тобто WÍS. Тоді WÇW = Æ і WÈW = S. Значення x i з S можна представити булевим вектором, причому
x i = 1, якщо x i ÎW,
0, якщо x i ÎW.
Завдання вибору параметрів у цьому випадку формулюється двояко:
1) знайти набір Ω, для якого
P (Ω) = max
при Σx i · c (x i) ≤ C; iЄΩ
2) знайти набір Ω, для якого
Σx i · c (x i) = min
при P (Ω) ≥ P з,
де P (Ω) - апостеріорна ймовірність працездатного стану об'єкта контролю при позитивному результаті контролю вибраних параметрів WÍS; с (x i) - витрати на контроль i-го параметра; Р з - необхідна достовірність контролю; С - обмеження на загальну вартість контролю.
Значення P (Ω) залежить від прийнятих припущень і може бути знайдено за формулою Байєса. Так, якщо припускати у виробі наявність лише однієї відмови, то
P (Ω) = Р 0 / 1-ΣР i,
iЄR (Ω)
де Р 0 = Π (1-р i) - апріорна ймовірність безвідмовної роботи об'єкта:
iЄR (S)
Р 0 = 1-ΣР i;
iЄR (S)
Р i - Нормована ймовірність відмови системи через відмову i-го елемента:
Р i = (p i / (1-p i)) / (1 + Σ p k / (1-p k);
kЄR (S)
p i - апріорна ймовірність відмови i-го елемента. Тоді ймовірність того, що відмова буде виявлено при перевірці k-го параметра, можна обчислити за формулою:Q k = ΣP k
kЄR (x k)
При можливості наявності в ОК довільного числа відмов
P (Ω) = Π (1-p i) / Π (1-p i)
iЄR (S) iЄR (Ω)
Можна використовувати простий перебір варіантів, однак виникають при цьому обчислювальні труднощі не дозволяють зробити цього навіть для простих систем (при n> 10). У зв'язку з цим комплектування набору будемо трактувати як багатокроковий процес, що складається з послідовного вибору окремих параметрів.
Відповідно до загального принципу оптимальності розіб'ємо весь наявний ресурс вартості З на С відрізків одиничної довжини. (У практичних випадках задані позитивні величини з (x i) і С можна вважати завжди цілими. Якщо це не так, то необхідно перейти до більш дрібним вартісним одиницям залежно від розрядності дробової частини.). Розглянемо поряд з цікавій для нас вихідної завданням безліч аналогічних завдань
f (Y) = max λ (x), Y Є [0, C],
xЄX Y
де через X Y позначено множину невід'ємних цілочисельних векторів Ω, що відповідають наборам, до яких загальна вартість перевірки параметрів не перевершує величини Υ.
Нехай Υ 0 = min c (x i).
i = 1, ..., n
Тоді при всіх Υ Є [0, Υ 0] відповідні множини Χ Υ складаються, з одного нульового елемента і f (Y) = 0 для всіх таких Υ. Для ресурсу Υ Є [Υ 0, С] за загальною схемою динамічного програмування справедливі наступні рекурентні співвідношення:
f (Y k) = max [Q i + f [Y k - c (x i)] - G i (1)
iЄI Y
де k = Y 0, Y 0 +1, ..., C; I Y - безліч тих i, для яких з (x i) ≤ Y k, починаючи з номера k = max c (x i) рівняння (1) вирішується для всіх i = 1, ..., n;
G i = ΣP i - сума ймовірностей елементів i-го параметра, які перетинаються з
IЄR (x i) ∩ Ω l *
елементами підмножини Ω l *, утвореного на кроці Y k - c (x i).
Якщо "i, j; R (x i) ∩ R (x j) = Æ, то G i = 0 і
f (Y k) = max {Q i + f [Y k - c (x i)]} (2)
iЄI Y
Σx i · c (x i) ≤ C
iЄΩ
прийняти більш жорстке обмеження, а саме Σc (x i) = C, то останнє не допустимо, iЄΩ так як в цьому випадку max f (Y k) може бути менше max f (Y k -1) через те, що він досягається на іншому підмножині параметрів.
Загальна складність методу, очевидно, φ (n) ≤ c (n +1), тобто експонентна функція при переборі замінена лінійної функцією. При цьому для запам'ятовування проміжних значень необхідно k ≤ 2c осередків пам'яті. Якщо в якості максімізіруемого критерію використовувати P (Ω) = Π (1-p i) / Π (1-p i), то необхідно вирішити задачу динамічного iЄR (S) iЄR (Ω) програмування з мультиплікативним критерієм. Для цього достатньо прологаріфміровать цей вислів і позначити
V = lgP (Ω) = lgР 0-Σlg (1-p i). (3)
iЄR (Ω)
Так як вираз, що стоїть під знаком Σ в (3), негативно, то, V = V max тоді, коли максимальна величина суми, тобто в цьому випадку отримаємо нову цільову функцію
V = Σν i, де ν i = lg (1-p i),
iЄR (Ω)
володіє властивістю адитивності і обертається в максимум одночасно з P (Ω).
1.2 Практична частина
Ручний рахунок
Дані для розрахунку:
З ≤ 16
Таблиця 1
N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Qi | 0.17 | 0.03 | 0.15 | 0.09 | 0.13 | 0.08 | 0.07 | 0.02 | 0.06 | 0.04 |
| с (xi) | 5 | 1 | 4 | 2 | 6 | 3 | 2 | 3 | 1 | 1 |
Для зручності розрахунків проранжіруем табліцу1 наступним чином:
Таблиця 2
N | 9 | 10 | 2 | 4 | 7 | 6 | 8 | 3 | 1 | 5 |
| Qi | 0.06 | 0.04 | 0.03 | 0.09 | 0.07 | 0.08 | 0.02 | 0.15 | 0.17 | 0.13 |
| с (xi) | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 6 |
Таблиця 3
| Yk | f (Yk) | iYk | Ωl * |
| 1 | 0,06 | 9 | 9 |
| 2 | 0,1 | 10 | 9,10 |
| 3 | 0,15 | 4 | 4,9 |
| 4 | 0,19 | 4 | 4,10,9 |
| 5 | 0,22 | 7 | 7,4,9 |
| 6 | 0,26 | 7 | 7,4,10,9 |
| 7 | 0,3 | 3 | 3,4,9 |
| 8 | 0,34 | 3 | 3,4,10,9 |
| 9 | 0,37 | 3 | 3,7,4,9 |
| 10 | 0,41 | 7 | 7,3,4,10,9 |
| 11 | 0,44 | 2 | 2,7,3,4,10,9 |
| 12 | 0,47 | 1 | 1,3,4,9 |
| 13 | 0,51 | 1 | 1,3,4,10,9 |
| 14 | 0,54 | 2 | 2,1,3,4,10,9 |
| 15 | 0,58 | 7 | 7,1,3,4,10,9 |
| 16 | 0,61 | 1 | 1,2,7,3,4,10,9 |
P (Ω) = 0,61 +0,16 = 0,77 і С = 16.
Лістинг програми
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ToolWin, ComCtrls, mdCONTROLS, Grids, StdCtrls, ExtCtrls, Unit2,
Buttons;
type
TForm1 = class (TForm)
sgH: TStringGrid;
sgP: TStringGrid;
sgC: TStringGrid;
sgQ: TStringGrid;
lbC: TLabeledEdit;
BitBtn1: TBitBtn;
Label1: TLabel;
sgW: TStringGrid;
Label2: TLabel;
procedure FormCreate (Sender: TObject);
procedure BitBtn1Click (Sender: TObject);
procedure sgExit (Sender: TObject);
private
{Private declarations}
public
H: TH;
P: TP;
C: TC;
W: TW;
end;
var
Form1: TForm1;
implementation
{$ R *. dfm}
procedure TForm1.FormCreate (Sender: TObject);
var i, j: integer;
x: Byte;
f: TextFile;
begin
AssignFile (f, 'data.txt');
Reset (f);
sgW.Cells [0,0]: = 'W';
/ / Введення вихідної матриці
readln (f);
for j: = 1 to 10 do
begin
sgH.Cells [0, j]: = IntToStr (j);
sgW.Cells [0, j]: = IntToStr (j);
for i: = 1 to 10 do
begin
sgH.Cells [i, 0]: = IntToStr (i);
read (f, x);
sgH.Cells [i, j]: = IntToStr (x);
if x = 1 then
H [i-1, j-1]: = true
else
H [i-1, j-1]: = false;
end;
readln (f);
end;
/ / Введення ймовірностей
readln (f);
readln (f);
sgP.Cells [0,0]: = 'P';
for i: = 1 to 10 do
begin
read (f, P [i-1]);
sgP.Cells [i, 0]: = FloatToStr (P [i-1]);
end;
readln (f);
/ / Введення вартостей
readln (f);
readln (f);
sgC.Cells [0,0]: = 'C';
for j: = 1 to 10 do
begin
read (f, C [j-1]);
sgC.Cells [0, j]: = IntToStr (C [j-1]);
end;
CloseFile (f);
/ / Введення ймовірностей виявлення відмови
sgQ.Cells [0,0]: = 'Q';
for j: = 1 to 10 do
sgQ.Cells [0, j]: = FloatToStr (Q (j-1, H, P));
lbC.Text: = '1 ';
end;
procedure TForm1.BitBtn1Click (Sender: TObject);
var i: integer;
begin
label1.Caption: = FloatToStr (maxf (1, StrToInt (lbC.Text), H, P, C, W));
for i: = 1 to 10 do
begin
sgW.Cells [2, i]: = IntToStr (W [i-1]. N);
if W [i-1]. E then
sgW.Cells [1, i]: = '1 '
else
sgW.Cells [1, i]: = '0 ';
end;
end;
procedure TForm1.sgExit (Sender: TObject);
var i, j: integer;
begin
for j: = 1 to 10 do
for i: = 1 to 10 do
if sgH.Cells [i, j] = '1 'then
H [i-1, j-1]: = true
else
H [i-1, j-1]: = false;
for i: = 1 to 10 do
P [i-1]: = StrToFloat (sgP.Cells [i, 0]);
for j: = 1 to 10 do
C [j-1]: = StrToInt (sgC.Cells [0, j]);
/ / Введення ймовірностей виявлення відмови
for j: = 1 to 10 do
sgQ.Cells [0, j]: = FloatToStr (Q (j-1, H, P));
end;
end.
unit Unit2;
interface
type
TH = array [0 .. 9, 0 .. 9] of boolean;
TP = array [0 .. 9] of extended;
TC = array [0 .. 9] of integer;
TDateW = record
E: boolean;
N: integer;
end;
TW = array [0 .. 9] of TDateW;
function Q (j: integer; H: TH; P: TP): extended;
function maxf (n, Yk: integer; H: TH; P: TP; C: TC; var W: TW): extended;
implementation
function Q (j: integer; H: TH; P: TP): extended;
var i: integer;
begin
Result: = 0;
for i: = 0 to 9 do
if H [i, j] then
Result: = Result + P [i];
end;
function G (j: integer; H: TH; P: TP; W: TW): extended;
var i, k: integer;
begin
Result: = 0;
for i: = 0 to 9 do
if H [i, j] then
for k: = 0 to 9 do
if W [k]. E and H [i, k] then
begin
Result: = Result + P [i];
Break;
end;
end;
function f (n, Yk, j: integer; H: TH; P: TP; C: TC; var W: TW): extended;
begin
Result: = Q (j, H, P) + maxf (n +1, Yk - C [j], H, P, C, W) - G (j, H, P, W);
end;
function maxf (n, Yk: integer; H: TH; P: TP; C: TC; var W: TW): extended;
var j, i: integer;
ft: extended;
Wt: TW;
begin
Result: = 0;
for i: = 0 to 9 do
begin
W [i]. E: = false;
W [i]. N: = 0;
end;
for j: = 0 to 9 do
if C [j] <= Yk then
begin
for i: = 0 to 9 do
begin
Wt [i]. E: = false;
Wt [i]. N: = 0;
end;
ft: = f (n, Yk, j, H, P, C, Wt);
if Result <ft then
begin
Result: = ft;
W: = Wt;
W [j]. E: = true;
W [j]. N: = n;
end;
end;
end;
end.
2. Метод гілок і меж
2.1 Теоретична частина
Розглянемо таку задачу цілочисельного програмування. Потрібно максимізувати вираз:
n
L = Σc j ∙ x j (4)
j = 1
при обмеженнях
n
Σа ij ∙ x j ≤ b i, i = 1, ..., m (5)
j = 1
x j Є {0, 1}, j = 1, ..., n
причому з j ≥ 0, a ij ≥ 0.
Метод гілок і меж використовує послідовно-паралельну схему побудови дерева можливих варіантів. Спочатку шукають допустимий план і для кожного можливого варіанту визначають верхню межу цільової функції. Гілки дерева можливих варіантів, для яких верхня межа нижче наближеного рішення, з подальшого розгляду виключають.
Ефективність обчислювальних алгоритмів залежить від точності і простоти способу визначення верхньої межі можливих рішень і точності визначення наближеного рішення. Чим точніше спосіб визначення верхньої межі цільової функції, тим більше безперспективних гілок відсікається в процесі оптимізації. Однак збільшення точності розрахунку верхніх меж пов'язано зі зростанням обсягу обчислень. Наприклад, якщо для оцінки верхньої межі використовувати симплекс-метод, то результат буде досить точним, але зажадає великого обсягу обчислювальної роботи.
Розглянемо алгоритм вирішення задачі методом гілок і меж з простим і ефективним способом оцінки верхньої межі цільової функції.
Позначимо: U - множина змінних x j; S - безліч фіксованих змінних, що увійшли до допустиме рішення; E s - безліч залежних змінних, які не можуть бути включені в безліч S, так як для них виконується нерівність
а ij> b i - Σа ij ∙ x j, i = 1, ..., m
x j Єs
G S - безліч вільних змінних, з яких проводиться вибір для включення в S черговий змінної.
Розглянемо спочатку одновимірну задачу, коли m = 1 і завдання (4) має тільки одне обмеження виду (5).
Позначимо h 1 j = c j / a 1 j і припустимо, що x j Єs (j = 1, ..., k <n) і виконуються умови
h 1, k +1 ≥ h 1, k +2 ≥ ... ≥ h 1 l, l ≤ n,
l
Σa 1 j> b 1 - Σ a 1 j ∙ x j,
j = k +1 x j Єs
l-1
Σa 1 j ≤ b 1 - Σ a 1 j ∙ x j,
j = k +1 x j Єs
Умови означають, що в безліч S без порушення нерівності (5) можна додатково ввести елементи x k +1, x k +2, ..., x l -1. При введенні в безліч S елементів x k +1, x k +2, ..., x l нерівність (5) не виконується.
Для визначення верхньої межі рішення може бути використано вираз
H s = Σc j ∙ x j + L s ',
x j Єs
де
l-1
L s '= Σс j + h 1 l Δ b 1,
j = k +1
l-1
Δ b 1 = b 1 - Σ a 1 j ∙ x j - Σa 1 j.
x j Єs j = k +1
З умов випливає, що L s ' не менше максимального значення величини
Σc j ∙ x j
x j ЄG S
при обмеженнях
Σ a 1j ∙ x j b 1 - Σ a 1j ∙ x j = b 1 ',
x j ЄG S x j Єs
x j Є {0, 1}, x j ЄG S,
Вибір черговий змінної для включення в безліч S проводиться за допомогою умови
h 1r (x r) = max h 1j (x j)
x j ЄG S
Усі вершини дерева можливих варіантів, для яких виконуються умови
H s ≤ L 0, з подальшого розгляду виключаються.
З решти гілок вибирається гілка з максимальним значенням H s, і процес пошуку оптимального варіанту продовжується. Якщо в процесі вирішення буде знайдено L s = Σc j ∙ x j > L 0, то отримане рішення приймається
x j Єs
в якості нового наближеного результату. Обчислювальна процедура закінчується, якщо для решти гілок виконується умова H s ≤ L 0.
2.2 Практична частина
Ручний рахунок
Дані для розрахунку:
Для формування таблиці 6 зробимо розрахунки:
1)
8
Σс j = 19> b 1 - Σ c j ∙ x j = 16-0 = 16;
j = 1 x j Єs
7
Σс j = 16 £ 16;
j = 1
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-0-16 = 0
x j Єs j = 1
H s (x 1) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
8
Σс j = 18> b 1 - Σ c j ∙ x j = 16-0 = 16;
j = 2 x j Єs
7
Σс j = 15 £ 16;
j = 2
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-0-15 = 1
x j Єs j = 2
H s (x 1) = q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.5767
2)
8
Σс j = 18> b 1 - Σ c j ∙ x j = 16-1 = 15;
j = 2 x j Єs
7
Σс j = 15 £ 15;
j = 2
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-15 = 0
xjЄS j = 2
H s (x 2) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
8
Σс j = 16> b 1 - Σ c j ∙ x j = 16-1 = 15;
j = 3 xjЄS
7
Σс j = 13 £ 15;
j = 3
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-13 = 2
xjЄS j = 3
H s (x 2) = q1 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.5734
3)
8
Σс j = 16> b 1 - Σ c j ∙ x j = 16-1-2 = 13;
j = 3 xjЄS
7
Σс j = 13 £ 13;
j = 3
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-13 = 0
xjЄS j = 3
H s (x 3) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
8
Σс j = 15> b 1 - Σ c j ∙ x j = 16-1-2 = 13;
j = 4 xjЄS
7
Σс j = 12 £ 13;
j = 4
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-12 = 1
xjЄS j = 4
H s (x 3) = q1 + q2 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.5967
4)
8
Σс j = 15> b 1 - Σ c j ∙ x j = 16-1-2-1 = 12;
j = 4 xjЄS
7
Σс j = 12 £ 12;
j = 4
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-12 = 0
xjЄS j = 4
H s (x 4) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
9
Σс j = 17> b 1 - Σ c j ∙ x j = 16-1-2-1 = 12;
j = 5 xjЄS
8
Σс j = 11 £ 12;
j = 5
8
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-11 = 1
xjЄS j = 5
H s (x 4) = q1 + q2 + q3 + q5 + q6 + q7 + q8 + h 9 Δ з = 0.56167
5)
8
Σс j = 11> b 1 - Σ c j ∙ x j = 16-1-2-1-4 = 8;
j = 5 xjЄS
7
Σс j = 8 £ 8;
j = 5
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-4-8 = 0
xjЄS j = 5
H s (x 5) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
8
Σс j = 9> b 1 - Σ c j ∙ x j = 16-1-2-1-4 = 8;
j = 6 xjЄS
7
Σс j = 6 £ 8;
j = 6
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-4-6 = 2
xjЄS j = 6
H s (x 5) = q1 + q2 + q3 + q4 + q6 + q7 + h 8 Δ з = 0.5934
6)
8
Σс j = 9> b 1 - Σ c j ∙ x j = 16-1-2-1-4-2 = 6;
j = 6 xjЄS
7
Σс j = 6 £ 6;
j = 6
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-4-2-6 = 0
xjЄS j = 6
H s (x 6) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
9
Σс j = 10> b 1 - Σ c j ∙ x j = 16-1-2-1-4-2 = 6;
j = 7 xjЄS
8
Σс j = 4 £ 6;
j = 7
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-4-2-4 = 2
xjЄS j = 6
H s (x 6) = q1 + q2 + q3 + q4 + q5 + q7 + q8 + h 9 Δ з = 0.56334
7) C s = Σ c j ∙ x j, перевіряємо умову С-С s. Якщо з (x j)> С-С s, то ці
xjЄS
елементи вводяться в безліч E s.
E s = {x8, x9, x10}
з 7 = 1> b 1 - Σ c j ∙ x j = 16-1-2-1-4-2-5 = 1;
xjЄS
з 7 = 1 £ 1;
Умова не виконується.
8) L s = q1 + q2 + q3 + q4 + q5 + q6 + q7 = 0.61
L s приймається як наближеного рішення L 0. Так як всі вершини дерева, для яких виконується умова H s £ L 0, з подальшого розгляду виключаються, то процес розрахунку припиняється.
Таблиця 6
Для контролю системи необхідно використовувати наступні параметри контролю: x1, x2, x3, x4, x5, x6, x7.
Перейдемо на стару нумерацію елементів і побудуємо дерево можливих варіантів рішення. Воно представлено на рис.1. Біля кожної вершини вказана верхня межа рішення. Тому що всі ці оцінки не перевищують величини 0,61, то, отже, отримане рішення L 0 = 0,61 є оптимальним. Таким чином необхідно використовувати наступні параметри контролю: x9, x4, x10, x3, x7, x1, x2.
де
l-1
L s '= Σс j + h 1 l Δ b 1,
j = k +1
l-1
Δ b 1 = b 1 - Σ a 1 j ∙ x j - Σa 1 j.
x j Єs j = k +1
З умов випливає, що L s ' не менше максимального значення величини
Σc j ∙ x j
x j ЄG S
при обмеженнях
Σ a 1j ∙ x j b 1 - Σ a 1j ∙ x j = b 1 ',
x j ЄG S x j Єs
x j Є {0, 1}, x j ЄG S,
Вибір черговий змінної для включення в безліч S проводиться за допомогою умови
h 1r (x r) = max h 1j (x j)
Для обраної змінної x r визначаються величини H s (x r) і H s (x r), тобто в S включаються x r = 1 або x r = 0.
Якщо в процесі вирішення виявиться, що в множині G S немає елементів, які можуть бути введені в безліч S без порушення обмеження (5), то отримане рішення L s = Σc j ∙ x j приймається в якості першого наближеного x j Єs рішення L 0.Усі вершини дерева можливих варіантів, для яких виконуються умови
H s ≤ L 0, з подальшого розгляду виключаються.
З решти гілок вибирається гілка з максимальним значенням H s, і процес пошуку оптимального варіанту продовжується. Якщо в процесі вирішення буде знайдено L s = Σc j ∙ x j > L 0, то отримане рішення приймається
x j Єs
в якості нового наближеного результату. Обчислювальна процедура закінчується, якщо для решти гілок виконується умова H s ≤ L 0.
2.2 Практична частина
Ручний рахунок
Дані для розрахунку:
З ≤ 16
Таблиця 4
N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Qi | 0.17 | 0.03 | 0.15 | 0.09 | 0.13 | 0.08 | 0.07 | 0.02 | 0.06 | 0.04 |
| с (xi) | 5 | 1 | 4 | 2 | 6 | 3 | 2 | 3 | 1 | 1 |
| hj | 0.034 | 0.03 | 0.0375 | 0.045 | 0.0217 | 0.0267 | 0.035 | 0.0067 | 0.06 | 0.04 |
Для зручності розрахунків проранжіруем таблицю 4 в порядку убування h j і привласнимо нові номери елементів, наступним чином:
Таблиця 5N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
n | 9 | 4 | 10 | 3 | 7 | 1 | 2 | 6 | 5 | 8 |
| Qi | 0.06 | 0.09 | 0.04 | 0.15 | 0.07 | 0.17 | 0.03 | 0.08 | 0.13 | 0.02 |
| с (xi) | 1 | 2 | 1 | 4 | 2 | 5 | 1 | 3 | 6 | 3 |
| hj | 0.06 | 0.045 | 0.04 | 0.0375 | 0.035 | 0.034 | 0.03 | 0.0267 | 0.02167 | 0.0067 |
1)
8
Σс j = 19> b 1 - Σ c j ∙ x j = 16-0 = 16;
j = 1 x j Єs
7
Σс j = 16 £ 16;
j = 1
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-0-16 = 0
x j Єs j = 1
H s (x 1) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
8
Σс j = 18> b 1 - Σ c j ∙ x j = 16-0 = 16;
j = 2 x j Єs
7
Σс j = 15 £ 16;
j = 2
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-0-15 = 1
x j Єs j = 2
H s (x 1) = q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.5767
2)
8
Σс j = 18> b 1 - Σ c j ∙ x j = 16-1 = 15;
j = 2 x j Єs
7
Σс j = 15 £ 15;
j = 2
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-15 = 0
xjЄS j = 2
H s (x 2) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
8
Σс j = 16> b 1 - Σ c j ∙ x j = 16-1 = 15;
j = 3 xjЄS
7
Σс j = 13 £ 15;
j = 3
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-13 = 2
xjЄS j = 3
H s (x 2) = q1 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.5734
3)
8
Σс j = 16> b 1 - Σ c j ∙ x j = 16-1-2 = 13;
j = 3 xjЄS
7
Σс j = 13 £ 13;
j = 3
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-13 = 0
xjЄS j = 3
H s (x 3) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
8
Σс j = 15> b 1 - Σ c j ∙ x j = 16-1-2 = 13;
j = 4 xjЄS
7
Σс j = 12 £ 13;
j = 4
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-12 = 1
xjЄS j = 4
H s (x 3) = q1 + q2 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.5967
4)
8
Σс j = 15> b 1 - Σ c j ∙ x j = 16-1-2-1 = 12;
j = 4 xjЄS
7
Σс j = 12 £ 12;
j = 4
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-12 = 0
xjЄS j = 4
H s (x 4) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
9
Σс j = 17> b 1 - Σ c j ∙ x j = 16-1-2-1 = 12;
j = 5 xjЄS
8
Σс j = 11 £ 12;
j = 5
8
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-11 = 1
xjЄS j = 5
H s (x 4) = q1 + q2 + q3 + q5 + q6 + q7 + q8 + h 9 Δ з = 0.56167
5)
8
Σс j = 11> b 1 - Σ c j ∙ x j = 16-1-2-1-4 = 8;
j = 5 xjЄS
7
Σс j = 8 £ 8;
j = 5
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-4-8 = 0
xjЄS j = 5
H s (x 5) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
8
Σс j = 9> b 1 - Σ c j ∙ x j = 16-1-2-1-4 = 8;
j = 6 xjЄS
7
Σс j = 6 £ 8;
j = 6
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-4-6 = 2
xjЄS j = 6
H s (x 5) = q1 + q2 + q3 + q4 + q6 + q7 + h 8 Δ з = 0.5934
6)
8
Σс j = 9> b 1 - Σ c j ∙ x j = 16-1-2-1-4-2 = 6;
j = 6 xjЄS
7
Σс j = 6 £ 6;
j = 6
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-4-2-6 = 0
xjЄS j = 6
H s (x 6) = q1 + q2 + q3 + q4 + q5 + q6 + q7 + h 8 Δ з = 0.61
9
Σс j = 10> b 1 - Σ c j ∙ x j = 16-1-2-1-4-2 = 6;
j = 7 xjЄS
8
Σс j = 4 £ 6;
j = 7
7
Δ з = з - Σ з j ∙ x j - Σс j = 16-1-2-1-4-2-4 = 2
xjЄS j = 6
H s (x 6) = q1 + q2 + q3 + q4 + q5 + q7 + q8 + h 9 Δ з = 0.56334
7) C s = Σ c j ∙ x j, перевіряємо умову С-С s. Якщо з (x j)> С-С s, то ці
xjЄS
елементи вводяться в безліч E s.
E s = {x8, x9, x10}
з 7 = 1> b 1 - Σ c j ∙ x j = 16-1-2-1-4-2-5 = 1;
xjЄS
з 7 = 1 £ 1;
Умова не виконується.
8) L s = q1 + q2 + q3 + q4 + q5 + q6 + q7 = 0.61
L s приймається як наближеного рішення L 0. Так як всі вершини дерева, для яких виконується умова H s £ L 0, з подальшого розгляду виключаються, то процес розрахунку припиняється.
Таблиця 6
| S | Es | Gs | Hs | xr | Hs (xr) | Hs (xr) | L0 | |
| 1 | Æ | Æ | 1 ... 10 | 0.61 | x1 | 0.61 | 0.5767 | |
| 2 | x1 | Æ | 2 ... 10 | 0.61 | x2 | 0.61 | 0.5734 | |
| 3 | x1, x2 | Æ | 3 ... 10 | 0.61 | x3 | 0.61 | 0.5967 | |
| 4 | x1, x2, x3 | Æ | 4 ... 10 | 0.61 | x4 | 0.61 | 0.56167 | |
| 5 | x1, x2, x3, x4 | Æ | 5 ... 10 | 0.61 | x5 | 0.61 | 0.5934 | |
| 6 | x1, x2, x3, x4, x5 | Æ | 6 ... 10 | 0.61 | x6 | 0.61 | 0.56334 | |
| 7 | x1, x2, x3, x4, x5, x6 | 8,9,10 | 7 | 0.61 | x7 | 0.61 | 0.56334 | |
| 8 | x1, x2, x3, x4, x5, x6, x7 | 8,9,10 | Æ | - | - | - | - | 0.61 |
Перейдемо на стару нумерацію елементів і побудуємо дерево можливих варіантів рішення. Воно представлено на рис.1. Біля кожної вершини вказана верхня межа рішення. Тому що всі ці оцінки не перевищують величини 0,61, то, отже, отримане рішення L 0 = 0,61 є оптимальним. Таким чином необхідно використовувати наступні параметри контролю: x9, x4, x10, x3, x7, x1, x2.
S = Æ |
х9 |
х4 |
х9 |
х2 |
х3 |
х4 |
х1 |
х10 |
х7 |
х3 |
х10 |
х2 |
х7 |
х1 |
0,61 |
0,5734 |
0,5967 |
0,56167 |
0,5934 |
0,56334 |
0,56334 |
0,61 |
0,61 |
0,61 |
0,61 |
0,61 |
0,61 |
0,61 |
0,5767 |
| |||
Лістинг програми
program vetvi;
const
maxmatrix = 1000;
maxsize = 200;
type linear = array [1 .. 10000] of integer;
label skip;
var matrix: array [1 .. 1000] of pointer;
n: integer;
sizeofm: word;
q, w, e, r: integer;
start_m: integer;
sm: ^ linear;
bestx, besty: integer;
bz: integer;
ochered: array [1 .. 1000] of
record
id: integer;
ocenka: integer;
end;
nochered: integer;
workm, workc: integer;
leftm, rightm: integer;
first, last: integer;
best: integer;
bestmatr: array [1 .. maxsize] of integer;
bestmatr1: array [1 .. maxsize] of integer;
curr: integer;
procedure swapo (a, b: integer);
begin
ochered [1000]: = ochered [a];
ochered [a]: = ochered [b];
ochered [b]: = ochered [1000];
end;
procedure addochered (id, ocenka: integer);
var
curr: integer;
begin
inc (nochered);
ochered [nochered]. id: = id;
ochered [nochered]. ocenka: = ocenka;
{Uravnoveshivanie ocheredi}
curr: = nochered;
while true do
begin
if curr = 1 then break;
if ochered [curr]. ocenka <ochered [curr div 2]. ocenka
then
begin
swapo (curr, curr div 2);
curr: = curr div 2;
end
else break;
end;
end;
procedure getochered (var id, ocenka: integer);
var
curr: integer;
begin
id: = ochered [1]. id;
ocenka: = ochered [1]. ocenka;
ochered [1]: = ochered [nochered];
dec (nochered);
curr: = 1;
while true do
begin
if (curr * 2 +1> nochered) then break;
if (ochered [curr * 2]. ocenka <ochered [curr]. ocenka) or
(Ochered [curr * 2 +1]. Ocenka <ochered [curr]. Ocenka) then
begin
if ochered [curr * 2]. ocenka> ochered [curr * 2 +1]. ocenka
then
begin
swapo (curr * 2 +1, curr);
curr: = curr * 2 +1;
end
else
begin
swapo (curr * 2, curr);
curr: = curr * 2;
end;
end else break;
end;
end;
function getid: integer;
var q: integer;
qw: ^ linear;
begin
if memavail <10000 then
begin
q: = ochered [nochered]. id;
{Exit;}
end else
begin
for q: = 1 to maxmatrix do
if matrix [q] = nil then break;
getmem (matrix [q], sizeofm);
end;
qw: = matrix [q];
fillchar (qw ^, sizeofm, 0);
getid: = q;
end;
procedure freeid (id: integer);
begin
freemem (matrix [id], sizeofm);
matrix [id]: = nil;
end;
function i (x, y: integer): integer;
begin
i: = (y-1) * n + x +1;
end;
function simplize (id: integer): integer;
var
q, w: integer;
t: ^ linear;
add: integer;
min: integer;
begin
t: = matrix [id];
add: = 0;
for q: = 1 to n do
begin
min: = maxint;
for w: = 1 to n do
if t ^ [i (w, q)] <> -1 then
if min> t ^ [i (w, q)] then min: = t ^ [i (w, q)];
if min <> 0 then
for w: = 1 to n do
if t ^ [i (w, q)] <> -1 then
dec (t ^ [i (w, q)], min);
if min> 32000 then min: = 0;
inc (add, min);
end;
for q: = 1 to n do
begin
min: = maxint;
for w: = 1 to n do
if t ^ [i (q, w)] <> -1 then
if min> t ^ [i (q, w)] then min: = t ^ [i (q, w)];
if min <> 0 then
for w: = 1 to n do
if t ^ [i (q, w)] <> -1 then
dec (t ^ [i (q, w)], min);
if min> 32000 then min: = 0;
inc (add, min);
end;
simplize: = add;
end;
function bestziro (id: integer): integer;
var
t: ^ linear;
q, w, e, x, y: integer;
min1, min2: integer;
l1, l2: array [1 .. maxsize] of integer;
begin
t: = matrix [id];
fillchar (l1, sizeof (l1), 0);
fillchar (l2, sizeof (l2), 0);
for q: = 1 to n do
begin
min1: = maxint; min2: = maxint;
for w: = 1 to n do
if t ^ [i (w, q)] <> -1 then
begin
if min2> t ^ [i (w, q)] then min2: = t ^ [i (w, q)];
if min1> min2 then
begin
e: = min1;
min1: = min2;
min2: = e;
end;
end;
if min1 <> 0 then min2: = 0;
if min2> 32000 then min2: = 0;
l2 [q]: = min2;
end;
for q: = 1 to n do
begin
min1: = maxint; min2: = maxint;
for w: = 1 to n do
if t ^ [i (q, w)] <> -1 then
begin
if min2> t ^ [i (q, w)] then min2: = t ^ [i (q, w)];
if min1> min2 then
begin
e: = min1;
min1: = min2;
min2: = e;
end;
end;
if min1 <> 0 then min2: = 0;
if min2> 32000 then min2: = 0;
l1 [q]: = min2;
end;
bz: =- 32000;
bestx: = 0; besty: = 0;
for y: = n downto 1 do
for x: = 1 to n do
if (t ^ [i (x, y)] = 0) then
if l1 [x] + l2 [y]> bz then
begin
bestx: = x;
besty: = y;
bz: = l1 [x] + l2 [y];
end;
bestziro: = bz;
end;
begin
assign (input, 'input.txt');
assign (output, 'vetvi.out');
reset (input);
rewrite (output);
nochered: = 0;
read (n);
sizeofm: = n * (n +2) * 2 +2;
start_m: = getid;
sm: = matrix [start_m];
for q: = 1 to n do
for w: = 1 to n do
read (sm ^ [i (w, q)]);
addochered (start_m, 0);
{;
bestziro (start_m);}
{Sobstvenno reshenie}
best: = maxint;
while true do
begin
if nochered = 0 then break;
getochered (workm, workc);
{Process MATRIX}
inc (workc, simplize (workm));
if workc> best then goto skip;
sm: = matrix [workm];
if sm ^ [1] = n-1 then
begin
best: = workc;
for q: = 1 to n do
begin
bestmatr [q]: = sm ^ [i (q, n +2)];
bestmatr1 [q]: = sm ^ [i (q, n +1)];
end;
goto skip;
end;
q: = bestziro (workm);
if q =- 32000 then goto skip;
{Pravaia vetka}
if (bestx = 0) or (besty = 0) then goto skip;
rightm: = getid;
move (matrix [workm] ^, matrix [rightm] ^, sizeofm);
sm: = matrix [rightm];
sm ^ [i (bestx, besty )]:=- 1;
addochered (rightm, workc + q);
{Levaia vetka}
leftm: = getid;
move (matrix [workm] ^, matrix [leftm] ^, sizeofm);
sm: = matrix [leftm];
{Dobavliaetsia rebro iz bestx v besty}
inc (sm ^ [1]);
sm ^ [i (bestx, n +2)]: = besty;
sm ^ [i (besty, n +1)]: = bestx;
first: = bestx; last: = besty;
if sm ^ [1] <> n-1 then
begin
while true do
begin
if sm ^ [i (last, n +2)] = 0 then break;
last: = sm ^ [i (last, n +2)];
end;
while true do
begin
if sm ^ [i (first, n +1)] = 0 then break;
first: = sm ^ [i (first, n +1)];
end;
sm ^ [i (last, first )]:=- 1;
sm ^ [i (first, last )]:=- 1;
sm ^ [i (besty, bestx )]:=- 1;
end;
for w: = 1 to n do
begin
sm ^ [i (w, besty )]:=- 1;
sm ^ [i (bestx, w )]:=- 1;
end;
addochered (leftm, workc);
skip:
{Free Matrix}
freeid (workm);
end;
{Freeid (start_m);}
if best = maxint then
begin
writeln ('Шлях не існує');
end else
begin
writeln ('Довжина шляху:', best);
for q: = 1 to n do
if bestmatr [q] = 0 then break;
e: = q;
for curr: = 1 to n do
if bestmatr [curr] = q then break;
while true do
begin
write (curr, '');
curr: = bestmatr1 [curr];
if curr = 0 then
begin
writeln (e);
break;
end;
end;
end;
close (input);
close (output);
end.
Висновок
При вирішенні поставленого завдання обидва методи дали однаковий результат, що показує правильність розуміння та виконання курсової роботи. Таким чином, необхідно використовувати наступні параметри контролю: x9, x4, x10, x3, x7, x1, x2.
Метод динамічного програмування досить простий для виконання, але має суттєвий недолік: при його використанні для рахунку вручну виникають обчислювальні труднощі навіть для простих систем.
Метод гілок і меж є більш складним для розуміння, але він виявився простішим при ручному рахунку. Недоліком є велика складність програмування методу.
Література
1. Селезньов А.В., Добриця Б.Т., убар Р.Р. «Проектування автоматизованих систем контролю бортового обладнання літальних апаратів» стор 90-95
2. Алексєєв О.Г. «Комплексне застосування методів дискретної оптимізації» стор 18-25