Задача.
Экзаменационный билет № 5
Этапы решения задач принятия решений на ЭВМ
Программирование (programming) - теоретическая и практическая деятельность, связанная с созданием программ. Решение задач на компьютере включает в себя следующие основные этапы, часть из которых осуществляется без участия компьютера.
1. Постановка задачи:
• сбор информации о задаче;
• формулировка условия задачи;
• определение конечных целей решения задачи;
• определение формы выдачи результатов;
• описание данных (их типов, диапазонов величин, структуры и т. п.).
2. Анализ и исследование задачи, модели:
• анализ существующих аналогов;
• анализ технических и программных средств;
• разработка математической модели;
• разработка структур данных.
3. Разработка алгоритма:
• выбор метода проектирования алгоритма;
• выбор формы записи алгоритма (блок-схемы, псевдокод и др.);
• выбор тестов и метода тестирования;
• проектирование алгоритма.
4. Программирование:
• выбор языка программирования;
• уточнение способов организации данных;
• запись алгоритма на выбранном языке
программирования.
5. Тестирование и отладка:
• синтаксическая отладка;
• отладка семантики и логической структуры;
• тестовые расчеты и анализ результатов тестирования;
• совершенствование программы.
6. Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5.
7. Сопровождение программы:
• доработка программы для решения конкретных задач;
• составление документации к решенной задаче, к математической модели, к алгоритму, к программе, к набору тестов, к использованию.
Целочисленное программирование. Примеры задач
Целочисленное программирование – один из наиболее молодых, перспективных и быстро развивающихся разделов математического программирования. Можно перечислить большое количество разнообразных задач планирования экономики, организации производства, исследования конфликтных ситуаций, синтеза схем автоматического регулирования, которые формально сводятся к выбору лучших, в некотором смысле, значений параметров из определенной дискретной совокупности заданных величин. К ним можно отнести и экстремальные комбинаторные задачи, возникающие в различных разделах дискретной математики.
Задачи и методы, относящиеся к перечисленному кругу вопросов, в литературе именуются по-разному. Наибольшее распространение получил термин «целочисленное программирование», однако встречаются и такие как «дискретное программирование», реже «комбинаторное (или диофантово) программирование».
Наиболее изученными задачами этого класса являются целочисленные задачи линейного программирования, в которых на все переменные (или на их часть) наложено дополнительное требование целочисленности. От них принято отличать так называемые дискретные задачи линейного программирования, в которых область допустимого изменения каждой переменной – не множество целых неотрицательных чисел, а некоторое заданное конечное множество.
Целочисленные задачи математического программирования могут возникать различными путями.
1. Существуют задачи линейного программирования, которые формально к целочисленным не относятся, но при соответствующих исходных данных всегда обладают целочисленным планом. Примеры таких задач – транспортная задача и ее модификации (задачи о назначениях, о потоках в сетях).
2. Толчком к изучению целочисленных задач в собственном смысле слова явилось рассмотрение задач линейного программирования, в которых переменные представляли физически неделимые величины. Они были названы задачами с неделимостью. Таковы, например, задачи об оптимизации комплекса средств доставки грузов, о нахождении минимального порожнего пробега автомобилей при выполнении заданного плана перевозок, об определении оптимального машинного парка и его оптимального распределения по указанным работам при условии минимизации суммарной стоимости (машинного парка и производимых работ), о нахождении минимального количества судов для осуществления данного графика перевозок и т. п.
3. Другим важным толчком к построению теории целочисленного программирования стал новый подход к некоторым экстремальным комбинаторным задачам. В них требуется найти экстремум целочисленной линейной функции, заданной на конечном множестве элементов. Такие задачи принято называть задачами с альтернативными переменными. В качестве примеров можно назвать задачи коммивояжера (бродячего торговца), об оптимальном назначении, теории расписания, или календарного планирования, и задачи с дополнительными логическими условиями (например, типа «или – или», «если – то» и т. п.).
Исторически первой задачей целочисленного типа является опубликованная в 1932 г. венгерским математиком Е. Эгервари задача о назначении персонала. В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце.