Коротко про сайт

RefList.Su - це найбільша колекція рефератів. На сайті RefList.su Ви знайдете безліч цікавих робіт і статей: реферати, дипломні, курсові роботи, шпаргалки, контрольні та лабораторні роботи, топіки з англійської мови. На нашому порталі, Ви можете додавати свої матеріали, читати реферати користувачів, використовувати пошук по сайту. Також в RefList.su можна почитати викладу, доповіді, квитки, твори. Колекція рефератів доступна для всіх безкоштовно і без відправки смс, і реєстрації.

Реклама

Товари

Реферат на тему Застосування методу гілок і національних кордонів для завдань календарного планування скачати

Розділ: кібернетикаТип роботи: реферат

ФІНАНСОВА АКАДЕМІЯ ПРИ УРЯДІ РФ

КАФЕДРА МТЕМАТИКИ

КУРСОВАЯ РОБОТА

тема:

Застосування методу гілок і національних кордонів для завдань календарного планування

Студент групи МЕК 1-1 Клеймёнов І.Дз.

Науковий керівник Солодовников О.С.

МОСКВА, 2001 р.

План

КАФЕДРА МТЕМАТИКИ 2

1.Постановка завдання целочисленного програмування 4

2. Поняття методі гілок і національних кордонів 5

3.Применение методу гілок і національних кордонів для завдань календарного планування 14

Летература 21

1.Постановка завдання целочисленного програмування

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

Завдання лінійного целочисленного програмування формується так: знайти таке рішення (план) X = (x1,x2,...,xn), у якому лінійна функція

(1)

приймає максимальне чи мінімальне значення при обмеженнях

=bi , i=1, 2…, m. (2)

хj 0, j=1, 2,..., п. (3)

xj — цілі числа (4)

2. Поняття методі гілок і національних кордонів

Метод гілок і національних кордонів — одне із комбінаторних методів. Суть його залежить від упорядкованому переборі варіантів і розгляді тільки тих із них, які знаходяться за ознаками перспективними, і відкиданні безперспективних варіантів.

Метод гілок і національних кордонів ось у чому: безліч допустимих рішень (планів) деяким способом розбивається на підмножини, кожна з яких цим самим способом знову розбивається на підмножини. Процес триває до того часу, доки отримано оптимальне целочисленное рішення вихідної завдання.

Алгоритм рішення:

Спочатку знаходимо симплексным методом чи методом штучного базису оптимальний план завдання не враховуючи целочисленности змінних. Нехай таким є план X0. Якщо серед компонент цього плану немає дробових чисел, тим самим знайдено дані вирішення цього завдання і Fmax = F(Xo).

Якщо серед компонент плану X0 є дробные числа, то X0 не задовольняє умові целочисленности і потрібно здійснити упорядкований перехід до нових планам, поки що не знайдено вирішення завдання. Покажемо, як це можна зробити, попередньо зазначаючи, що F(X0) F(X) будь-кого наступного плану X.

Припускаючи, що знайдений оптимальний план X0 не задовольняє умові целочисленности змінних, цим вважаємо, що його компонент є дробные числа. Нехай, наприклад, змінна прийняла у плані X0 дробове значення. Тоді, у оптимальному целочисленном плані його значення буде по крайнього заходу або менше, або одно найближчому меншому цілому числу, або більше або одно найближчому більшого цілому числу + 1. Визначаючи ці числа, знаходимо симплексным методом рішення двох завдань лінійного програмування:

Знайдемо вирішення завдань лінійного програмування (I) і (II). Вочевидь, тут може бути одне із наступних чотирьох випадків:

1. Одне із завдань нерозв'язна, іншу має целочисленный оптимальний план. Тоді це план і значення цільової функції у ньому й прокурори дають рішення вихідної завдання.

2. Одне із завдань нерозв'язна, іншу має оптимальний план, серед компонент якого є дробные числа. Тоді розглядаємо другу завдання й у її оптимальному плані вибираємо жодну з компонент, значення одно дробному числу, й будуємо два завдання, аналогічні завданням (I) і (II).

3. Обидва завдання можна розв'язати. Одне із завдань має оптимальний целочисленный план, а оптимальному плані інший завдання є дробные числа. Тоді обчислюємо значення цільової функції цих плани та порівнюємо їх між собою. Коли целочисленном оптимальному плані значення цільової функції більше або одно її значенням на плані, серед компонент якого є дробные числа, то даний целочисленный план є оптимальним для вихідної завдання й він разом із значенням цільової функції у ньому дає дані рішення.

Якщо ж значення цільової функції понад плані, серед компонент якого є дробные числа, слід взяти одна з таких чисел й у завдання, план якої розглядається, необхідно побудувати два завдання, аналогічні (I) і (II).

4. Обидва завдання можна розв'язати, серед оптимальних планів обох завдань є дробные числа. Тоді обчислюємо значення цільової функції на даних оптимальних плани та розглядаємо ту із завдань, на яку значення цільової функції найбільший. У оптимальному плані це завдання вибираємо жодну з компонент, значення є дробовим числом, й будуємо два завдання, аналогічні (I) і (II).

Отже, описане вище итерационный процес то, можливо подано у вигляді деякого дерева, у якому вихідна вершина відповідає оптимальному плану Х0 завдання (1)-(3), а кожна сполучена із нею гілкою вершина відповідає оптимальним планам завдань (I) і (II). Кожна з цих вершин має розгалуження. У цьому кожному кроці вибирається та вершина, на яку значення функції найбільший. Коли деякому кроці отримають план, має целочисленные компоненти, і значення функції у ньому виявиться більше або одно, ніж значення функції за іншими можливих для розгалуження вершинах, то даний план є оптимальним планом вихідної завдання целочисленного програмування і значення цільової функції у ньому є межею.

Отже, процес знаходження рішення завдання целочисленного програмування (1)-(4) методом гілок і національних кордонів входять такі основні етапи:

1°. Знаходять вирішення завдання лінійного програмування (1)-(3).

2°. Становлять додаткових обмежень до котроїсь із пере-менных, значення в оптимальному плані завдання (1)-(3) є дробовим числом.

3°. Знаходять вирішення завдань (I) і (II), які виходять з завдання (1)-(3) внаслідок приєднання додаткових обмежень.

4°. У разі потреби становлять додаткових обмежень для перемінної, значення є дробовим, формулюють завдання, аналогічні завданням (I) і (II), і знаходять їхнє рішення. Итерационный процес продовжують до того часу, поки що не знайдено вершина, відповідна целочисленному плану завдання (1)-(3) і такі, що значення функції у цій вершині більше або одно значенням функції за іншими можливих для розгалуження вершинах.

Описаний вище метод гілок і національних кордонів має як просту логічний схему розрахунків, ніж метод Гомори. Тож у вона найчастіше перебування вирішення конкретних завдань целочисленного програмування з допомогою ЕОМ застосовується саме такий метод.

Проілюструємо метод гілок і національних кордонів з прикладу.

Вирішити завдання

Z = Зх1 + х2 — max

при обмеженнях:

4xl + Зх2 < 18,

x1 + 2x2 6,

0 x1 5,

0 x2 4,

х1, x2 — цілі числа.

Рішення. За нижню межу лінійної функції приймемо, наприклад, його значення у точці (0,0), тобто. Z0 = Z (0; 0) = 0.

I етап. Вирішуючи завдання симплексным методом, одержимо Zmax = 13 при Х1* = (4,5; 0; 0; 1,5; 0,5; 4); оскільки перша компонента х1* подрібнена, те з області рішення виключається смуга, яка містить дробове оптимальне значення х1*, тобто. 4 < х1 < 5. Поэтому задача 1 разбивается на две задачи 2 и 3:

Завдання 2

Z=3x1+x2

Поділіться рефератом Застосування методу гілок і національних кордонів для завдань календарного планування

html-посилання на реферат
BB-cсылка на скачать реферат
Пряме посилання на завантажити реферат

Роботи схожі на Застосування методу гілок і національних кордонів для завдань календарного планування

Рішення завдання лінійного програмування симплексным методом
Тип роботи: лабораторна робота

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОСВІТІ

Державне освітнє установа

Вищої професійної освіти

«Волгоградский державний технічний університет»

Камышинский технологічний інститут (філія)

Волгоградського державного технічного

Завантажити
Рішення транспортної завдання лінійного програмування серед MS Excel
Тип роботи: дипломна робота

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РЕСПУБЛІКИ КАЗАХСТАН

КАЗАХСКИЙ ДЕРЖАВНИЙ ЖІНОЧИЙ ПЕДАГОГІЧНИЙ ІНСТИТУТ

КАФЕДРА ІНФОРМАТИКИ

Дипломна робота ПО ТЕМЕ: «Рішення транспортної завдання лінійного програмування серед MS Excel»

Виконала:

Завантажити
Рішення завдання лінійного програмування симплекс-методом
Тип роботи: реферат

Державне освітнє установа вищого

професійної освіти

\"Московський державний технічний університет ім. Н.Э. Баумана\"

Калузький філія

Реферат

\"Рішення завдання лінійного програмування си

Завантажити
Завдання на найбільше і найменше значення функції
Тип роботи: доповідь
Потрібна виготовити конічну вирву з котра утворює l=10см. Якою має бути радіус підстави воронки, щоб їх обсяг був найбільший?
Потрібна виготовити закритий циліндричний бак ємністю V. При якому радіусі підстави на виготовлення бака піде най
Завантажити
Рішення завдання лінійного програмування
Тип роботи: реферат
Розглянемо завдання лінійного програмування (1)
Теорему. Якщо безліч планів завдання (1) не порожньо і цільова функція згори обмежена у цьому безлічі, то завдання (1) має рішення.
Теорему. Якщо безліч допустимих планів має кр
Завантажити
Постановка завдання лінійного програмування і двоїста завдання лінійного програмування.
Тип роботи: реферат
Линейное програмування є складовою розділу математики, який вивчає методи перебування умовного экстремума функції багатьох змінних і називається математичним програмуванням. У класичному математичному аналізі розглядається завдання відшукання умЗавантажити