МІНІСТЕРСТВО АГЕНТСТВО ПО ОСВІТІ
ФГТУ ПО "Псковська КОЛЕДЖ БУДІВНИЦТВА ТА ЕКОНОМІКИ"
Предмет "Математичні методи"
Задача лінійного програмування
Курсова робота
Студента групи 315-ПО
Андрєєва Дмитра Олександровича
Керівник курсової роботи
Васильєва Наталія Анатоліївна
Псков 2009
Зміст
Введення
Глава О™ Лінійне програмування
В§ 1 Загальна постановка задачі лінійного програмування
В§ 2 Математична модель задачі лінійного програмування
В§ 3 Канонічна форма задачі лінійного програмування
Глава О™О™ Рішення задачі симплексним методом
В§ 1 Постановка завдання
В§ 2 Складання математичної моделі задачі
В§ 3 Алгоритми рішення задачі симплексним методом
В§ 4 Побудова початкового опорного рішення методом Гаусса
В§ 5 Рішення задачі
В§ 6 Висновок
Висновок
Література
Введення
В даний час безліч завдань планування та управління в галузях народного господарства, а також великий обсяг приватних прикладних задач вирішуються методами математичного програмування. Найбільш розвиненими в області розв'язання оптимізаційних задач є методи лінійного програмування. Ці методи дозволяють описати з достатньою точністю широкого кола завдань комерційної діяльності, таких, як планування товарообігу; розміщення роздрібній торговельній мережі міста; планування товаропостачання міста, району; прикріплення торгових підприємств до постачальників; організація раціональних перевезень товарів; розподіл працівників торгівлі посадами; організація раціональних закупівель продуктів харчування; розподіл ресурсів; планування капіталовкладень; оптимізація міжгалузевих зв'язків; заміна торгового устаткування; визначення оптимального асортименту товарів в умовах обмеженої площі; встановлення раціонального режиму роботи.
У задачах лінійного програмування критерій ефективності і функції в системі обмежень лінійний.
Якщо змістовний глузд вимагає отримання рішення в цілих числах, то така задача є завданням цілочисельного програмування.
Якщо в задачі математичного програмування є змінна часу, а критерій ефективності виражається через рівняння, що описують перебіг операцій під часу, то така задача є задачею динамічного програмування.
У багатьох економічних моделях залежності між постійними і змінними факторами можна вважати лінійними.
Використання методів математичного програмування в комерційній діяльності пов'язано зі збором необхідної інформації комерсантом, економістом, фінансистом, потім постановкою завдання разом із математикою. Оскільки методи математичного програмування вже реалізовані на комп'ютері у вигляді пакету стандартних програм, то доступ до них зазвичай простий, автоматизований і не становить особливих труднощів.
Тоді експлуатація моделі включає в себе збір та обробку інформації, введення обробленої інформації в ЕОМ, розрахунки на основі розроблених програм календарних планів і, нарешті, видачу результатів обчислень (в зручному для користувачів вигляді) для їх використання у сфері виробничої діяльності.
Глава О™ Лінійне програмування
В§ 1 Загальна постановка задачі лінійного програмування
Лінійне програмування - це напрямок математичного програмування вивчає методи вирішення екстремальних задач, які характеризуються лінійною залежністю між змінними і лінійної цільової функцією. Для вирішення завдань лінійного програмування складається математична модель задачі та вибирається метод рішення.
Постановка завдання комерційної діяльності може бути представлена ​​у вигляді математичної моделі лінійного програмування, якщо цільова функція може бути представлена ​​у вигляді лінійної форми, а зв'язок з обмеженими ресурсами описати за допомогою лінійних рівнянь або нерівностей. Крім того, вводиться додаткове обмеження - значення змінних повинні бути ненегативні, оскільки вони представляють такі величини, як товарообіг, час роботи, витрати та інші економічні показники.
Геометрична інтерпретація економічних задач дає можливість наочно уявити, їх структуру, виявити особливості і відкриває шляхи дослідження більш складних властивостей. Задача лінійного програмування з двома змінними завжди можна вирішити графічно. Проте вже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більше трьох, графічне рішення, взагалі кажучи, неможливо. Випадок двох змінних не має особливого практичного значення, проте його розгляд прояснює властивості задач лінійного програмування, призводить до ідеї її вирішення, робить геометрично наочними способи вирішення та шляхи їх практичної реалізації.
В§ 2 Математична модель задачі лінійного програмування
Перед рішенням завдання складаємо її математичну модель.
Математична модель - це сукупність співвідношень складаються з лінійної цільової функції і лінійних обмежень на змінну.
Принцип складання математичної моделі.
1. Вибирають змінні завдання.
Змінними завдання називаються величини які повністю характеризують економічний процес, описаний в задачі. Зазвичай записуються у вигляді вектора X = () Причому)
2. Складають систему обмеження задачі.
Система обмежень - це сукупність рівнянь і нерівностей, яким задовольняють змінні завдання і яка випливає з обмеженості економічних умов завдання.
В загальному вигляді система записується у вигляді
3. Задають цільову функцію.
Цільова функція - це функція Z (X) яка характеризує якість виконання завдання, екстремум якої треба знайти. У загальному вигляді цільова функція записується Z (X) = (Max, min)
т.ч. математична модель має вигляд знайти змінні завдання задовольняють системі обмежень:
і умові неотрицательности 0 (j =), Яка забезпечує екстремум цільової функції Z (Y) =
Допустимим рішенням задачі лінійного програмування називається будь-який набір значень змінних задовольняє системі обмежень і умовної неотрицательности.
Безліч допустимих рішень утворює область допустимих рішень задачі (ОДР).
Оптимальним рішенням називається допустиме рішення задачі, при якому цільова функція досягає екстремуму.
В§ 3 Канонічна форма задачі лінійного програмування
Математична модель завдання повинна мати канонічну форму.
Якщо система обмеження складається тільки з рівняння і всі змінні задовольняють умові неотрицательности, то задача має канонічну форму.
Якщо в системі є хоча б одне нерівності або яка-небудь змінна необмежена умові неотрицательности, то задача має стандартну форму. Щоб привести задачу до канонічного виду треба:
перейти від нерівностей до рівнянню наступним чином: в ліву частину нерівностей вводимо додаткову змінну з коефіцієнтом (+1) для нерівності () і (-1) для нерівності () додаткові змінні не накладені цільові неотрицательности, то її замінюють різницею двох невід'ємних змінних, тобто:
= - (
Загальний вигляд канонічної форми:
Глава О™О™ Рішення задачі симплексним методом
Симплексний метод - це метод послідовного поліпшення плану (рішення), найбільш ефективний і застосовується для вирішення будь-якої задачі лінійного програмування.
Назва методу від латинського simplecx - простий тому з початкового область допустимих рішень задачі мала найпростіший вид. Ідеї методу запропонував російський математик Контаровіч Л.В. в 1939 році і потім цю ідею розвинув і розробив Дж. Данциг в 1949 році.
Симплексний метод дозволяє за кінцеве число кроків або знайти оптимальне рішення або довести що його немає.
В§ 1 Пос...
