міністерство освіти і науки україниКиївський національний лінгвістичний університетк о н т р о л ь н а р о б о т аЗ математичного програмуванняДля студентів факультету заочного та вечірнього навчанняІ курс (ІІ семестр)Укладач: доц. Комаров Ю.А.Затвердженона засіданні кафедри інформатикита комп’ютерних технологійпротокол № 11 від 08.06.2006Зав. кафедридоц. Коваль Т.І.Київ - 2006Загальні положення.Завдання з контрольної роботи з математичного програмування складається з 3-х частин, що відповідає 3-м розділам навчальної дисципліни.Кожний студент має виконати усі завдання з кожного розділу.Розв’язання завдань має бути виконано з необхідним поясненням і обгрунтуванням виконуваних дій.Контрольна робота має бути акуратно оформлена; порядок запису виконаних завдань має відповідати їх нумерації.Студент, який не виконав усіх завдань і не оформив належним чином контрольну роботу, не допускається до захисту контрольної роботи з виставленням оцінки “не зараховано”.^ Захист контрольної роботи здійснюється за таким порядком: студент отримує індивідуальний варіант завдань, аналогічних завданням з контрольної роботи і протягом обмеженого часу демонструє володіння методами розв´язання відповідних задач. Подальше уточнення степеня володіння необхідними методами та навичками здійснюється на співбесіді. По ходу співбесіди викладач має право задавати питання щодо застосованих термінів, понять, формул, теорем.Успішний захист контрольної роботи може бути врахований при виставленні екзаменаційної оцінки.^ Факультет заочного тавечірнього навчання КНЛУ2006/2007 н.р.Контрольна робота з математичного програмуванняРозділ І1. Задача про інвестування. Розв’язати методом динамічного програмування. 0 1 2 3 4 5 0 5 15 40 80 90 0 5 15 50 70 80 0 4 26 55 70 75 ^ 2. Задача про призначення. Розв’язати угорським методом:2.1. Задачу про мінімально-витратне призначення;2.2. Задачу про максимально-ефективне призначення,інтерпретуючи матрицю відповідно як матрицю витрат та як матрицю ефективностей^ 3. Транспортна задача без обмежень на пропускні спроможності.Двома способами (методом з північно-західного кута та методом мінімального елемента) знайти початковий допустимий план перевезень (дпп). Для кожного дпп обчислити сумарні транспортні витрати. Зробити один крок методу потенціалів (виділення базисних клітин в транспортній таблиці; долучення при потребі до множини базисних клітин умовно базисних клітин; обчислення потенціалів; обчислення оцінок; перевірка виконання чи невиконання критерію оптимальності; вибір клітини з найбільшим порушенням критерію оптимальності; побудова компенсаторного циклу з допомогою методу викреслювання; вибір величини перевезення для циклічного перекидання по компенсаторному циклу; покращення поточного дпп). Виписати оптимальний дпп. Числові дані – перша таблиця з завдання 4.^ 4. Транспортна задача з обмеженнями (ТЗО).Виконати таке саме завдання, що й для ТЗ без обмежень на пропускні спроможності. 15 30 65 20 10 50 14 10 2 5 10 20 11 5 4 11 3 30 9 8 12 1 18 40 1 4 9 17 18 15 35 14 10 5 8 4 20 12 18 10 7 32 20 14 11 15 25 14 12 ^ 5. Задача знаходження найкоротшого шляху на мережі.Знайти найкоротший шлях на мережі методом Мінті.^ 6. Задача знаходження допустимого транспортного потоку на транспортній мережі.Розширити траспортну мережу допоміжним джерелом і допоміжним стоком та відповідними комунікаціями. Звести задачу про знаходження допустимого транспортного потоку до задачі про знаходження максимального потоку. Зробити 3 кроки методу Форда-Фалкерсона (виписати 3 ланцюжки, по яких здійснювалось збільшення потоку). Виписати максимальний потік на розширеній мережі та вказати, як по ньому визначити шуканий допустимий транспортний потік. На мережі залишити позначки, які доводять максимальність потоку (неможливість його збільшення). ^ 7. Задача про рюкзак. Розв’язати задачу про рюкзак методом віток і границь. 1 2 3 4 5 5 4 5 4 4 15 12 10 8 8 ^ Факультет заочного тавечірнього навчання КНЛУ2006/2007 н.р.Контрольна робота з математичного програмуванняРозділ ІІЗавдання.1. Розв’язати дану задачу лінійного програмуванняграфічним методом. Зробити малюнок допустимої множини, лінії рівня цільової функції з вказанням напрямків зростання і спадання; точно обчислити координати кутових точок допустимої множини. 2.Розв’язати задачі лінійного програмування з п.1 (окремо: задачу мінімізації та задачу максимізації) симплексним методом, початковий опорний план знайти методом штучного базису.3.Отримані розв’язки порівняти.^ Факультет заочного тавечірнього навчання КНЛУ2006/2007 н.р.Контрольна робота з математичного програмуванняРозділ ІІІЗавдання.Для даної задачі нелінійного програмування (ЗНЛП)1. Дати геометричну iнтерпретацiю даної ЗНЛП: зробити малюнок допустимої множини, ліній рівня цільової функції з вказанням точки глобального екстремуму; точно обчислити координати кутових точок допустимої множини; наближено, з геометричних міркувань, відшукати точку мінімуму цільової функції на допустимій області.2. Знайти розв’язок задачі безумовної оптимізації (точку глобального екстремуму цільової функції) за теоремою Ферма.3. Знайти розв’язок задачі безумовної оптимізації методом найскорiшого спуску.3.1. Першу iтерацю зробити з використанням методу золотого перерiзу. 3.2. Другу iтерацю зробити з використанням методу половинного дiлення (дiхотомiї).4. Розв’язати дану ЗНЛП методом множників Лагранжа.