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