Лабораторная работа по скилаб. Алтынбаев Салават 4307. Ответы на контрольные вопросы 5. Ответ это раздел математики, где на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений
 Скачать 125.65 Kb.
|
|
Когда используются дискретные задачи. Ответ: это раздел математики, где на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений. Целочисленное программирование. Ответ: В случае, если дискретные задачи должны принимать целочисленные значения, то это подраздел дискретного программирования – целочисленное программирование. Примеры задач целочисленного программирования. Ответ: Такие задачи используются, когда вектор решений Х включает в себя неделимые компоненты: X={a1, a2,…,an}. Так предприятие не может выпускать с конвейера 23,7 автомобилей; 7,3 самолета, построить 1,6 зданий. Во всех этих случаях можно было бы использовать подход связанный с решением непрерывной задачи и округлением решения до ближайшего целого числа. Но такой подход может оказаться неэффективным вследствие того, что при округлении могут быть нарушены ограничения и получены не оптимальные значения целевой функции. Постановка задачи о ранце. Ответ: 1. Задача о ”рюкзаке”. Турист отправляется в поход. Чтобы получить от подхода удовольствие, он не хотел бы нести ранец, весящий более чем G кг. Набор продуктов питания, которые должны быть положены в ранец, необходимо чтобы были максимально калорийными. Пусть заданы продукты: P1, P2,…,Pn – продукты (неделимые), g1, g2,…,gn –вес, с1, с2,…,сn –калорийность, G – общий вес рюкзака. хi – переменная,  Эвристический алгоритм решения задачи о рюкзаке. Ответ:  Метод ветвей и границ. Ответ:  Комбинаторные задачи Ответ: Комбинаторные задачи • К этой группе задач относятся: • Задача теории расписаний. • Задача о коммивояжере (задача о бродячем торговце). • Например, составление расписания по оптимальной обработке деталей. • Пусть имеется n – деталей и два станка токарный и фрезерный. Каждая деталь должна быть последовательно обработана на каждом из этих станков. • Как загрузить эти детали, чтобы время было минимальным? От выбора порядка обработки деталей зависят простои оборудования. Задача коммивояжера Ответ: Известна как задача о бродячем торговце. Район, который должен посетить бродячий торговец, содержит некоторое количество городов, расстояние между которыми являются известными. Требуется найти маршрут, проходящий через все пункты по одному разу и возвращающийся в исходный. Если таких маршрутов много, требуется найти кратчайший из них Способы решения задачи коммивояжера Ответ: Методы решения 1.Метод перебора. 2. Жадный алгоритм. 3. Метод ветвей и границ. 4. Деревянный алгоритм. 5. Генетический алгоритм Жадный алгоритм Ответ: заключается в нахождении наикратчайшего расстояния путем выбора самого короткого, еще не выбранного ребра. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность |