fy">. Завдання про комівояжера
6.Сімплекс метод
Введення
В даний час лінійне програмування є одним з найбільш уживаних апаратів математичної теорії оптимального прийняття рішень, у тому числі й у фінансовій математиці. Для вирішення завдань лінійного програмування розроблено складне програмне забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих обсягів. Ці програми і системи забезпечені розвиненими системами підготовки вихідних даних, засобами їх аналізу і представлення отриманих результатів. Володіння апаратом лінійного програмування необхідно кожному фахівцю в галузі прикладної математики. p align="justify"> Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
В· раціонального використання сировини та матеріалів;
В· задачі оптимального розкрою;
В· оптимізації виробничої програми підприємств;
В· оптимального розміщення і концентрації виробництва;
В· складання оптимального плану перевезень, роботи транспорту;
В· управління виробничими запасами;
В· і багато інших, що належать сфері оптимального планування.
Найбільш розробленим і широко застосовуваним розділом математичного програмування є лінійне програмування, метою якого служить відшукування оптимуму (max, min) заданої лінійної функції при наявності обмежень у вигляді лінійних рівнянь або нерівностей в цьому і полягає актуальність даної роботи. p align="justify"> Метою даного РГЗ є виконання розрахунково-графічної роботи, закріплення знань і навичок, необхідних для математичного моделювання соціально-економічних процесів. А також, придбання навичок роботи з програмними пакетами В«Лінійне програмуванняВ» і В«Дискретне програмуванняВ». br/>
Теоретична частина
Табличний симплекс-метод
Для спрощення процесу рішення вихідні дані задачі лінійного програмування при вирішенні її симплекс методом записуються в спеціальні симплекс-таблиці. Тому одна з модифікацій симплекс методу отримала назву табличний симплекс метод. Завдання лінійного програмування в канонічному вигляді:
F = a01x1 + a02x2 + ... a0nxn + b0? max
В
Вихідна таблиця для задачі має наступний вигляд:
x1x2 ... xn-1xnbF-a0 ,1-a0, 2 ...-a0, n-1- align = "justify">, x2, xn - вихідні змінні, xn +1, xn +2, xn + m - додаткові змінні. Всі додаткові змінні ми прийняли як базисні, а вихідні змінні як ...