Метод віток і меж - раздел Математика, З ДИСЦИПЛІНИ ЕКОНОМІКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ
Метод Віток І Меж Використовується Як До Повністю Ціло...
Метод віток і меж використовується як до повністю цілочисельних задач, так і до частково цілочисельних задач.
Спочатку розв'язується ослаблена задача без обмежень на цілочисельність.
. (5.14)
повинна бути цілочисельною .
Тоді сфера допустимих рішень розбивається на дві підмножини і таким чином, що:
:
: . (5.15)
Таким чином виключається інтервал , який не містить цілочисельних точок.
Початкова задача розбивається на дві підзадачі. В кожній з областей , знаходяться оптимальні точки, і, якщо вони не задовольняють умові цілочисельності, знову здійснюється розгалуження. Якщо отриманий оптимум виявляється допустимим (цілочисельним) для даної задачі, він фіксується і наголошується як найкращий. При цьому немає необхідності продовжувати галуження цієї підзадачі, оскільки поліпшити це рішення не вдасться.
Як тільки отримане допустиме (цілочисельне) рішення іншої підзадачі виявляється краще, воно фіксується замість попереднього.
Процес галуження продовжується до тих пір, поки кожна підзадача не призведе до цілочисельного рішення, або не буде встановлена неможливість поліпшення наявного рішення. Висновок про необхідність подальшого розбиття задачі робиться на основі введення межі.
Як межа використовується значення цільової функції отриманого допустимого цілочисельного рішення. Якщо будь-яке оптимальне рішення підзадачі забезпечує гірше значення цільової функції, ніж наявне рішення (прийняте як межа), то цю підзадачу розглядати далі не слід.
Алгоритм методу віток і меж є ітеративним.
- номер ітерації; - оцінка (для задачі мінімізації ).
При використанні алгоритму потрібне вирішення послідовності задач лінійного програмування без обмежень на цілочисельність. Послідовність задач, що підлягають вирішенню називається основним списком.
1. Якщо основний список порожній – закінчення алгоритму, інакше – вибирають задачу з основного списку і знаходять її оптимальне рішення.
2. Якщо вибрана задача не має рішення, або її оптимальне рішення гірше прийнятої оцінки, то необхідно виключити цю задачу із списку і перейти до п. 1, інакше – до п. 3.
3. Якщо отримане рішення цілочисельне – сформувати нову оцінку , яка відповідає якнайкращому оптимальному рішенню поточної задачі. Перехід до п. 1. Якщо рішення поточної задачі нецілочисельне, то оцінка залишається у наступному вигляді: .
4. Вибирається одна із змінних , яка за умовою повинна бути цілочисельною. Проводиться розгалуження, тобто в основний список додається дві підзадачі, для яких зберігаються ті ж обмеження, але для однієї:
, (5.16)
а для іншої:
. (5.17)
Перехід до п. 1.
Слід відзначити, що вибір змінної може бути довільним (за збільшенням номерів) або визначатися таким чином:
1) представлена змінна є важливим рішенням, що приймається в рамках розробленої моделі;
2) коефіцієнт в цільовій функції істотно перевершує всі інші.
ХАРКІВСЬКА НАЦІОНАЛЬНА АКАДЕМІЯ МІСЬКОГО ГОСПОДАРСТВА... Мамонов К А Скоков Б Г Чечетова Н Ф... НАВЧАЛЬНИЙ ПОСІБНИК...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Метод віток і меж
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Випадкові події і величини, їх числові характеристики
З позиції теорії пізнання спостережувані в природі й суспільстві явища можна підрозділити на наступні види:
- достовірні (визначені), які обов'язково відбудуться, якщо буде
Закони розподілу випадкової величини
Законом розподілу випадкової величини називається співвідношення, що встановлює зв'язок між можливими значеннями випадкової величини і відповідними їм ймовірностями.
Найпро
Статистичні гіпотези та їх перевірка
При вибіркових обстеженнях допускаються різного роду похибки, при цьому розрізняють грубі, систематичні й випадкові помилки.
Грубі помилки за абсолютними величинами значно відрізняються ві
Сутність економіко-математичних моделей оптимізації
На якому рівні не знаходилося суспільне виробництво, які великі не були трудові, матеріальні й фінансові ресурси, перед господарськими керівниками завжди стоїть завдання найкращого
Загальна характеристика задач математичного програмування
Математичне програмування відіграє винятково важливу роль у підготовці фахівців економічного профілю. Використання математичних методів економічній діяльності дозволяє вирішувати оп
Види економіко-математичних моделей оптимізації
При здійсненні господарської діяльності підприємством можуть бути сформовані наступні види економіко-математичних моделей оптимізації:
1. Економіко-математичні моделі оптимізації випуску п
Сутність і методи лінійного програмування
Лінійне програмування використовує математичний інструментарій, який базується на теорії і методах вирішення задач про екстремуми лінійних функцій, що задаються системами лінійних р
Аналіз лінійних моделей оптимізаційних задач
Аналіз лінійних моделей оптимізаційних задач спрямований на прийняття оптимального рішення. Лінійна оптимізаційна модель включає систему обмежень, цільову функцію, області допустимих рішень, критер
Основні поняття і сутність цілочислового програмування
Цілочислове програмування – це різновид задач лінійного програмування, в якому змінні та отримані результати повинні бути цілими числами.
Задачі цілочислового програмування можуть б
Алгоритм розв’язування задач цілочислового програмування
Алгоритм розв’язування задач цілочислового програмування наступний:
1. Розв'язується задача лінійного програмування без обмежень на цілочисельність, наприклад, симплекс-методом.
Метод Гомори
Перший алгоритм Р. Гомори полягає в наступному:
Хай задана повністю цілочисельна лінійна задача:
(5
Сутність нелінійних зв’язків в економічних системах
Найважливішою задачею економічної науки є цілеспрямоване управління поведінкою складних динамічних систем, у тому числі економічних, господарських, технічних та інш. Для цього сучасна наука має в р
Аналіз заходів управління ризиком в економіці
На підприємстві аналіз заходів щодо управління ризиком спрямований на досягнення основної мети їх діяльності – забезпечення розвитку і складається з декількох етапів. На першому етапі в процесі
Напрями кількісного оцінювання ступеня ризику
Оцінка ризику – це систематичний процес виявлення факторів і видів ризику та їх кількісна оцінка, тобто методологія аналізу ризиків поєднує взаємодоповнюючи кількісний і якісний під
Допустимий та критичний ризик
В системі оцінки ризику необхідно визначити границі або інтервали, де можна допускати відповідний рівень ризику, а де він є критичним. Тобто визначають зони ризику. При цьому
Оцінка ризику ліквідності
Підприємства на кожному етапі господарської діяльності здійснює відповідні інвестування грошових коштів в економічний процес. Тому необхідно постійно моніторити цей процес, виявляти негативні явища
Принципи побудови економетричних моделей
В економіко-математичному моделюванні важливе місце займають економетричні моделі, які дозволяють встановити причинно-наслідковий зв’язок між економічними факторами. На основі економетричних моделе
Сутність мультиколінеарності, напрями її виявлення
В економетричному моделюванні необхідно враховувати також явище мультиколінеарності.
Мультиколінеарність – це явище, яке використовується для опису проблеми, коли не
Парна лінійна регресія
Парний регресійний аналіз спрямований на визначення ступеню зв’язку між змінними і яким чином вони пов’язані в побудові парної моделі. Слід відзначити, що не слід очікувати отримання точного
Сутність кількісного регресійного аналізу
Кількісний регресійний аналіз є продовженням парного регресійного аналізу у випадках, коли залежна змінна у пов’язана з двома або більше незалежними змінними х.
Напрями побудови лінійної моделі множинної регресії
Для побудови лінійної моделі множинної регресії використовується статистична інформація про діяльність підприємства і здійснюються такі етапи: математико-статистичний аналіз, побудова багатофакторн
Сутність динамічних процесів в економіці
Динамічні процеси, які здійснюються в економічних системах, проявляються у вигляді ряду послідовно розташованих в хронологічному порядку значень того чи іншого показника, який в сво
Альтернативні прості тест-завдання
Обведіть правильну відповідь, визначену літерою під запитанням:
1.1. Твердження «На ідеї моделювання по суті базується будь-який метод на
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
1. Альгин А.П. Грани экономического риска. М., - 1991.
2. Ашманов С. А. Введення в математичну економіку. М.: Наука 1984.
3. Балабанов И.Т. Риск-менеджмент. М.: Фи
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов