Сутність і методи лінійного програмування - раздел Математика, З ДИСЦИПЛІНИ ЕКОНОМІКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ
Лінійне Програмування Використовує Математичний Інструментарі...
Лінійне програмування використовує математичний інструментарій, який базується на теорії і методах вирішення задач про екстремуми лінійних функцій, що задаються системами лінійних рівнянь. Термін «програмування» визначається як «планування».
Найбільш універсальним методом є диференціальний алгоритм, логічно випливає з диференціального алгоритму загальної задачі математичного програмування. Диференціальний алгоритм, як і широко відомий симплекс-метод, дозволяє вирішувати будь-які задачі лінійного програмування. однак для деяких класів задач лінійного програмування доцільно використовувати більш прості методи. Так, для вирішення задач із кількістю змінних, рівною двом, використовують графічний метод, що відзначається простотою і наочністю, але потребує графічних побудов. Для вирішення задач лінійного програмування, відомих як транспортні, використовують метод потенціалів.
Методичною основою обчислювальних процедур будь-якого методу є принцип аналізу і послідовного поліпшення деякого початкового плану розподілу і використання ресурсів. План поліпшують доти, поки не буде знайдений найкращий (оптимальний) варіант. Іншими словами, спочатку складається деякий початковий план, що аналізується за конкретними строго розробленими правилами. На підставі аналізу визначаються можливість і напрямок поліпшення початкового варіанта плану. Потім обчислюється новий план, що піддається такому ж аналізу і подальшому поліпшенню, тобто наближенню до оптимуму. Обчислювальний процес продовжується доти, поки аналіз не покаже неможливість дальшого поліпшення.
Слід декілька слів сказати про симплекс-метод. Він використовується до вирішення будь-якої задачі лінійного програмування. Сутність симплекс-методу полягає в тому, що, відправляючись з деякої довільної вершини багатокутника обмежень, переходять до обчислення тільки такої вершини, в якій значення лінійної форми буде більше, ніж в попередній. Решта варіантів не обчислюється. Тоді при кінцевому порівняно малому числі кроків може бути знайдений оптимальний план. Таким чином, проводиться впорядкований перебір вершин, при якому відбувається постійне збільшення лінійної форми. В цьому аспекті симплексний метод називається також методом послідовного поліпшення плану.
Вирішення задач лінійного програмування симплекс-методом полягає:
- по-перше, в розробці базового рішення на оптимальність. Якщо воно оптимальне, то задача вирішена, в іншому випадку виконують другий етап;
- по-друге, визначаються вектор , який повинен бути введений в базис, і вектор , який повинен бути виключений з нього, тобто виходить новий базисний план з великим значенням лінійної форми. Щоб знайти вектори і , заміна яких забезпечує найбільше зростання лінійної форми, виразимо всі вектори, що не входять в базис, через базисні вектори
(3.1)
де aij - проекції вектора на вектор . Запишемо систему обмежень у векторній формі в наступному вигляді:
(3.1)
Оскільки то
(3.2)
Співвідношення (3.2) дає рішення тільки у тому випадку, коли коефіцієнти при векторах і нового базису будуть ненегативними, тобто
і (3.3)
Відповідне нове значення лінійної форми прийме вигляд
(3.4)
Позначимо
(3.5)
Тоді значення лінійної форми в новій вершині багатокутника рішення можна знайти з рівняння
(3.6)
Величину dj називають оцінкою плану. В симплексному методі параметри dj відіграють важливу роль: їх знаки дозволяють визначити, чи є опорний план оптимальним. Якщо dj0 для всіх j, то даний опорний план є оптимальним, оскільки на підставі (3.6) і зважаючи на q ³ 0 перехід до будь-якої нової вершини веде до убування лінійної форми. Якщо опорний план неоптимальний, то можливі два випадки:
1. Є хоча б один індекс j = k для якого dk < 0 і всі відповідні компоненти В цьому випадку лінійна форма не обмежена зверху і задача нерозв'язна.
2. Для деяких j dj < 0 і для кожного такого j, принаймні, одна з проекцій aij >0. Тоді при переході до наступної вершини лінійна форма зростає і план поліпшується. Для найшвидшого зростання L необхідно в базис включити той вектор , для якого оцінка dk < 0 і максимальна по модулю, а вектор , для якого значення позитивно і мінімально, виключити.
Також при лінійному програмуванні використовують методи еліпсоїдів, метод внутрішніх крапок, методи логарифмічних бар'єрних функцій нелінійного програмування. В цих методах вирішення задач лінійного програмування здійснюється шляхом пошуку уздовж траєкторій в просторі змінних задачі, що не проходять через вершини багатокутника.
ХАРКІВСЬКА НАЦІОНАЛЬНА АКАДЕМІЯ МІСЬКОГО ГОСПОДАРСТВА... Мамонов К А Скоков Б Г Чечетова Н Ф... НАВЧАЛЬНИЙ ПОСІБНИК...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Сутність і методи лінійного програмування
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Випадкові події і величини, їх числові характеристики
З позиції теорії пізнання спостережувані в природі й суспільстві явища можна підрозділити на наступні види:
- достовірні (визначені), які обов'язково відбудуться, якщо буде
Закони розподілу випадкової величини
Законом розподілу випадкової величини називається співвідношення, що встановлює зв'язок між можливими значеннями випадкової величини і відповідними їм ймовірностями.
Найпро
Статистичні гіпотези та їх перевірка
При вибіркових обстеженнях допускаються різного роду похибки, при цьому розрізняють грубі, систематичні й випадкові помилки.
Грубі помилки за абсолютними величинами значно відрізняються ві
Сутність економіко-математичних моделей оптимізації
На якому рівні не знаходилося суспільне виробництво, які великі не були трудові, матеріальні й фінансові ресурси, перед господарськими керівниками завжди стоїть завдання найкращого
Загальна характеристика задач математичного програмування
Математичне програмування відіграє винятково важливу роль у підготовці фахівців економічного профілю. Використання математичних методів економічній діяльності дозволяє вирішувати оп
Види економіко-математичних моделей оптимізації
При здійсненні господарської діяльності підприємством можуть бути сформовані наступні види економіко-математичних моделей оптимізації:
1. Економіко-математичні моделі оптимізації випуску п
Аналіз лінійних моделей оптимізаційних задач
Аналіз лінійних моделей оптимізаційних задач спрямований на прийняття оптимального рішення. Лінійна оптимізаційна модель включає систему обмежень, цільову функцію, області допустимих рішень, критер
Основні поняття і сутність цілочислового програмування
Цілочислове програмування – це різновид задач лінійного програмування, в якому змінні та отримані результати повинні бути цілими числами.
Задачі цілочислового програмування можуть б
Алгоритм розв’язування задач цілочислового програмування
Алгоритм розв’язування задач цілочислового програмування наступний:
1. Розв'язується задача лінійного програмування без обмежень на цілочисельність, наприклад, симплекс-методом.
Метод Гомори
Перший алгоритм Р. Гомори полягає в наступному:
Хай задана повністю цілочисельна лінійна задача:
(5
Метод віток і меж
Метод віток і меж використовується як до повністю цілочисельних задач, так і до частково цілочисельних задач.
Спочатку розв'язується ослаблена задача без обмежень на
Сутність нелінійних зв’язків в економічних системах
Найважливішою задачею економічної науки є цілеспрямоване управління поведінкою складних динамічних систем, у тому числі економічних, господарських, технічних та інш. Для цього сучасна наука має в р
Аналіз заходів управління ризиком в економіці
На підприємстві аналіз заходів щодо управління ризиком спрямований на досягнення основної мети їх діяльності – забезпечення розвитку і складається з декількох етапів. На першому етапі в процесі
Напрями кількісного оцінювання ступеня ризику
Оцінка ризику – це систематичний процес виявлення факторів і видів ризику та їх кількісна оцінка, тобто методологія аналізу ризиків поєднує взаємодоповнюючи кількісний і якісний під
Допустимий та критичний ризик
В системі оцінки ризику необхідно визначити границі або інтервали, де можна допускати відповідний рівень ризику, а де він є критичним. Тобто визначають зони ризику. При цьому
Оцінка ризику ліквідності
Підприємства на кожному етапі господарської діяльності здійснює відповідні інвестування грошових коштів в економічний процес. Тому необхідно постійно моніторити цей процес, виявляти негативні явища
Принципи побудови економетричних моделей
В економіко-математичному моделюванні важливе місце займають економетричні моделі, які дозволяють встановити причинно-наслідковий зв’язок між економічними факторами. На основі економетричних моделе
Сутність мультиколінеарності, напрями її виявлення
В економетричному моделюванні необхідно враховувати також явище мультиколінеарності.
Мультиколінеарність – це явище, яке використовується для опису проблеми, коли не
Парна лінійна регресія
Парний регресійний аналіз спрямований на визначення ступеню зв’язку між змінними і яким чином вони пов’язані в побудові парної моделі. Слід відзначити, що не слід очікувати отримання точного
Сутність кількісного регресійного аналізу
Кількісний регресійний аналіз є продовженням парного регресійного аналізу у випадках, коли залежна змінна у пов’язана з двома або більше незалежними змінними х.
Напрями побудови лінійної моделі множинної регресії
Для побудови лінійної моделі множинної регресії використовується статистична інформація про діяльність підприємства і здійснюються такі етапи: математико-статистичний аналіз, побудова багатофакторн
Сутність динамічних процесів в економіці
Динамічні процеси, які здійснюються в економічних системах, проявляються у вигляді ряду послідовно розташованих в хронологічному порядку значень того чи іншого показника, який в сво
Альтернативні прості тест-завдання
Обведіть правильну відповідь, визначену літерою під запитанням:
1.1. Твердження «На ідеї моделювання по суті базується будь-який метод на
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
1. Альгин А.П. Грани экономического риска. М., - 1991.
2. Ашманов С. А. Введення в математичну економіку. М.: Наука 1984.
3. Балабанов И.Т. Риск-менеджмент. М.: Фи
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
, який повинен бути введений в базис, і вектор 
, який повинен бути виключений з нього, тобто виходить новий базисний план з великим значенням лінійної форми. Щоб знайти вектори 
(3.1)
на вектор 
. Запишемо систему обмежень у векторній формі в наступному вигляді:
(3.1)
то
(3.2)
і 
і 
(3.3)
(3.4)
(3.5)
(3.6)
0 для всіх j, то даний опорний план є оптимальним, оскільки на підставі (3.6) і зважаючи на q ³ 0 перехід до будь-якої нової вершини веде до убування лінійної форми. Якщо опорний план неоптимальний, то можливі два випадки:
В цьому випадку лінійна форма не обмежена зверху і задача нерозв'язна.
Новости и инфо для студентов