Міністерство освіти Російської Федерації
Уфімський державний авіаційний технічний університет
Кафедра автоматизованих технологічних систем
Курсова робота
За дисципліни: Програмування систем
На тему: Дискретне програмування
Уфа 2011
Зміст
1. Введення
2. Завдання з неподільних
2.1 Приклад коду на мові Java
2.2 Приклад коду на мові C #
3. Комбінаторні задачі
4. Завдання з розривними цільовими функціями
4.1 Основні ідеї та принципи
4.2 Опис алгоритму
4.3 Приклад рішення ЦЗЛП методом Гоморі
4.3.1 Ітерація 1
4.3.1 Ітерація 2
5. Метод гілок і меж
5.1 Загальна схема методу "гілок і кордонів "
5.2 Рішення ЦЗЛП методом гілок і меж
6. Висновок
1. Введення
Основні поняття. Багато економічні завдання характеризуються тим, що обсяги керованих ресурсів (у силу тих чи інших об'єктивних властивостей) можуть приймати тільки цілі значення. Математична формалізація даних ситуацій призводить до моделей дискретного програмування. В загальному вигляді задача дискретного програмування може бути сформульована як задача знаходження максимуму (або мінімуму) цільової функції f (x1, x2, ..., xn) на множині D, визначеному системою обмежень
де О© - деякий кінцевий, або рахункове *, безліч. Умова хОµО©. називається умовою дискретності. Особливе місце серед дискретних задач займає целочисленная задача лінійного програмування в канонічній формі (ЦКЗЛП):
* Нагадаємо, що прикладами рахункових множин є множини натуральних, цілих і раціональних чисел.
де Z + = {0; 1; 2; ...} - безліч невід'ємних цілих чисел.
Зауважимо, що в деяких ситуаціях вимога "цілочисельності" може бути накладено лише на деякі змінні xj, що кардинально не змінює характеру завдання.
Принципова складність, яка викликається наявністю умов цілочисельності в системі обмежень оптимізаційної задачі, полягає в тому, що в значній кількості випадків неможливо замінити дискретну задачу її безперервним аналогом і, знайшовши відповідне рішення, округлити його компоненти до найближчих цілих значень. Приклад, показаний на рис.1, демонструє, що при округленні оптимального плану х * звичайної задачі ЛП до цілих значень виходить точка ([х1 *], [x2 *]), яка не належить області допустимих планів задачі D. Домовимося цілу частину числа хj. позначати [хj], а дробову - як {хj}. Тоді хj = [хj] + {хj}. Окремо слід додати, що якщо навіть оптимальний план безперервної завдання, округлений до цілих значень компонент, виявиться припустимим, то цільова функція може вести себе так, що її значення буде на ньому істотно "гірше", ніж на оптимальному плані цілочисельний завдання.
Перераховані проблеми зумовили необхідність розробки спеціальних методів вирішення дискретних і цілочисельних задач. Але перш ніж говорити власне про методи вирішення, більш докладно зупинимося на класифікації задач дискретного програмування. У літературі, як правило, виділяють наступні класи дискретних оптимізаційних задач:
Г? завдання з неподільних;
Г? екстремальні комбінаторні завдання;
Г? завдання з розривними цільовими функціями;
Г? завдання на незв'язних і неопуклих областях та ін
2. Завдання з неподільних
У переважній більшості випадків наявність умов неподільності визначається фізичними властивостями модельованих об'єктів. Так, наприклад, вони можуть з'явитися в якості додаткових обмежень в уже розглядалася нами вище задачі виробничого планування, якщо в ній здійснюється управління випуском великої штучної продукції.
Класичним представником завдань даного класу стала так звана задача про ранці. Її фабула носить досить умовний характер і полягає в тому, що солдат (або турист), що збирається в похід, може нести вантаж вагою не більше W кг. Цей вантаж може складатися з набору предметів n типів, кожен предмет типу j важить wj кг і характеризується деякою "корисністю" uj, j <1: n. В рамках описаної ситуації цілком природним представляється питання: скільки предметів кожного виду потрібно покласти в ранець, щоб його сумарна корисність була максимальною? Якщо в Як компонент плану хj. прийняти кількість укладаються предметів типу j, то дану задачу можна записати:
Як неважко помітити, представлена ​​математична модель носить універсальний характер, і до неї можуть бути зведені багато економічні завдання. Яскравим підтвердженням цьому служить і той факт, що в літературі вона також відома як задача про завантаження судна.
2.1 Приклад коду на мові Java
int knapsack (int weights [], int costs [], int needed) {
int n = weights.length;
int dp [] [] = new int [needed + 1] [n + 1];
for (Int j = 1; j <= n; j + +) {
for (Int w = 1; w <= needed; w + +) {
if (Weights [j-1] <= w) {
dp [w] [j] = Math.max (dp [w] [j - 1], dp [w - weights [j-1]] [j - 1] + costs [j-1]);
} else {
dp [w] [j] = Dp [w] [j - 1];}
}
}
return dp [needed] [n];
}
2.2 Приклад коду на мові C #
int knapsack (int [] weights, int [] costs, int needed)
{ int n = weights.Length;
int [,] dp = new int [needed + 1, n + 1];
for (Int j = 1; j <= n; j + +)
{ for (int w = 1; w <= needed; w + +)
{ if (weights [j - 1] <= w)
{ dp [w, j] = Math.Max ​​(dp [w, j - 1], dp [w - weights [j - 1], j - 1] + costs [j - 1]);
}
else
{ dp [w, j] = dp [w, j - 1];}
}
}
return dp [needed, n];}
3. Комбінаторні задачі
До даного класу відносяться задачі оптимізації функції, заданої на кінцевому безлічі, елементами якого служать вибірки з n об'єктів.
Класичним представником математичних проблем такого роду стала задача про комівояжера. Вона полягає в складанні маршруту відвідування торговим агентом, що знаходяться в деякому початковому пункті, n інших міст за умови, що задана матриця вартостей переїздів з міста в місто
(з урахуванням початкового). Причому допустимим є такий маршрут, який передбачає одноразове відвідування всіх міст і повернення у вихідний пункт. Очевидно, що найкращий маршрут повинен мінімізувати сумарну вартість переїздів.
Планом завдання є маршрут комівояжера, і його можна задати за допомогою так званої матриці суміжності
дискретний програмування ітерація комбінаторний
елементи якої визначаються наступним чином:
1, якщо в маршруті передбачений переїзд з пункту i в j,
xi, j = 0, якщо в маршруті не передбачений переїзд із пункту i в j,
причому за умовою завдання xii = 0, i <1: n.
Допустимими планами служать зв'язкові маршрути, однозначно визначаються впорядкованим набором відвідуваних пунктів:
Кожен такий маршрут можна ототожнити з перестановкою n чисел (впорядкованої вибіркою з n елементів по n). У свою чергу, таким
перестановок взаємно однозначно відповідають матриці X, у яких в кожному рядку і кожному стовпці міститься точно одна одиниця.
З урахуванням сказаного задача комівояжера приймає вид цілочисельний завдання лінійного програмування:
Умови 6 і 7 з змістовної точки зору означають, що в кожен пункт можна в'їхати і виїхати тільки один раз. Наведена форма запису задачі комівояжера 4-8 не є самою раціональною і призначена тільки для того, щоб підкреслити її спільність з іншими завданнями дискретного програмування. Існує і інша форма, яка більш яскраво відображає комбінаторний характер даної проблеми:
...
