Задачі цілочисельного програмування та спеціальні методи знаходження їх оптимальних розвязків - Дипломная работа

ЗАДАЧІ ЦІЛОЧИСЕЛЬНОГО ПРОГРАМУВАННЯ ТА СПЕЦІАЛЬНІ МЕТОДИ ЗНАХОДЖЕННЯ ЇХ ОПТИМАЛЬНИХ РОЗВ’ЯЗКІВ Зміст Вступ Розділ 1. Цілочисельне програмування 1.1 Деякі історичні відомості 1.2 Постановка задачі 1.2 Приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом Розділ 2. Методи розв´язання задач цілочислового програмування 2.1 Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині 2.2 Методи відтинання. Метод Гоморі 2.3 Комбінаторні методи. Розробка математичної моделі складання розкладу занять на математичному факультеті ВНУ 3.1 Формулювання завдання складання розкладу занять на математичному факультеті 3.2 Математична модель розкладу у вузі Висновки Література Додаток а. бібліографія Вступ Дипломна робота присвячена задачам цілочисельного програмування та спеціальним методам знаходження їх оптимальних розв’язків. Робота складається із вступу, трьох розділів, висновків та списку використаної літератури, додатку в якому подано відомості про вчених, авторів основних результатів роботи У першому розділі наведені деякі історичні відомості, подано загальну постановку задач цілочисельного програмування та вказано спеціальні методи для знаходження оптимальних розв’язків таких задач. Математичні основи для вирішення завдань лінійного програмування були створені в 1939 році академіком Л.В. Канторовичем і його учнями. Тому знання системи лінійного програмування необхідні кожному спеціалісту в області прикладної математики. Об’єктом дослідження є оптимізація навчального процесу студентів,що забезпечується ефективним розподілом навчальних аудиторій, та щоденним академічним навантаженням викладачів. цілочисельне програмування математичний розклад Предметом дослідження є задача пошуку оптимального розв’язку, що математично зводиться до задачі знаходження умовного екстремуму функції багатьох змінних. Результати роботи доповідались на IV науково­ практичній конференції студентів та аспірантів Волинь очима науковців: минуле, сучасне, майбутнє (12-13 травня 2010р., м. Луцьк). Сам термін лінійне програмування був введений дещо пізніше, в 1951 році, у працях американських вчених Дж. Данцига та Г. Кумпанса. В 1947 році Дж. Данциг розробив основний метод розв’язування задач лінійного програмування - симплексний метод, що стало початком формування лінійного програмування як самостійного напрямку в математичному програмуванні. У період найбурхливішого розвитку математичного програмування за кордоном у Радянському Союзі не спостерігалося значних досягнень через штучні ідеологічні обмеження. Першою задачею цілочислового типу яка була опублікована угорським математиком Б. Егерварі в 1932 році, задача про призначення персоналу. Розробляються банки економіко-математичних моделей, які в поєднанні з потужною, швидкодіючою обчислювальною технікою та сучасними програмними продуктами утворюватимуть системи ефективної підтримки прийняття рішень у різних галузях економіки. 1.2 Постановка задачі Існує доволі широкий клас задач математичного програмування, в економіко - математичних моделях яких одна або кілька змінних мають набувати цілих значень. Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Тоді математична модель задачі матиме вигляд: , ; , - цілі числа, Приклад 1.1: Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Аналогічне значення цільової функції ( ) дає оптимальний план, за яким виготовляється більша кількість кінцевої продукції та витрачається весь наявний матеріал: .