Державна освітня установа вищої професійної освіти
Санкт-Петербурзький Державний Технологічний інститут (Технічний університет)
Кафедра Економіки та логістики Факультет наукоємних технологій
Навчальна дисципліна Математика
Курсова робота
В«Цілочисельне програмування. Задача про призначення В»
Студентка Савінова Д.І.
Керівник Межевич К.Г.
Санкт-Петербург 2010р.
Введення
Цілочисельне програмування - один з найбільш молодих, перспективних і швидко розвиваються розділів математичного програмування. Можна перерахувати велику кількість різноманітних завдань планування економіки, організації виробництва, дослідження конфліктних ситуацій, синтезу схем автоматичного регулювання, які формально зводяться до вибору кращих, в деякому сенсі, значень параметрів з певної дискретної сукупності заданих величин. До них можна віднести і екстремальні комбінаторні завдання, що у різних розділах дискретної математики. p align="justify"> Завдання і методи, пов'язані з перерахованого кола питань, в літературі іменуються по-різному. Найбільшого поширення набув термін В«цілочисельне програмуванняВ», однак зустрічаються й такі як В«дискретне програмуванняВ», рідше В«комбинаторное (або диофантово) програмуванняВ». p align="justify"> Найбільш вивченими завданнями цього класу є цілочисельні задачі лінійного програмування, в яких на всі змінні (або на їх частину) накладено додаткову вимогу цілочисельності. Від них прийнято відрізняти так звані дискретні задачі лінійного програмування, в яких область допустимого зміни кожної змінної - не безліч цілих невід'ємних чисел, а деякий заданий кінцевий безліч. p align="justify"> Цілочисельні задачі математичного програмування можуть виникати різними шляхами.
. Існують задачі лінійного програмування, які формально до цілочисловим не належать, але при відповідних вихідних даних завжди володіють цілочисловим планом. Приклади таких завдань - транспортна задача і її модифікації (задачі про призначення, про потоки в мережах). p align="justify">. Поштовхом до вивчення цілочисельних завдань у власному розумінні слова стало розгляд завдань лінійного програмування, в яких змінні представляли фізично неподільні величини. Вони були названі завданнями з неделимостью. Такі, наприклад, завдання про оптимізацію комплексу засобів доставки вантажів, про знаходження мінімального порожнього пробігу автомобілів при виконанні заданого плану перевезень, про визначення оптимального машинного парку та його оптимального розподілу по вказаних робіт за умови мінімізації сумарної вартості (машинного парку і вироблених робіт), про знаходженні мінімальної ...
