- •Государственный комитет рсфср по делам науки и высшей школы
- •Введение
- •Лабораторная работа I одномерная оптимизация
- •Постановка задачи
- •Краткие общие сведения Метод Пассивного поиска
- •Метод Фибоначчи
- •Метод золотого сечения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 3 симплексный метод
- •Постановка задачи
- •Краткие общие сидения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 4 решение прямой и двойственной задач
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Тексты исходных задач Вариант I
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Лабораторная работа 5 транспортная задача
- •Постановка задачи
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 6 задача 0 коммивояжере
- •Постановка задачи
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Содержание
- •197376, Санкт-Петербург, ул. Проф. Попова, 5
Порядок проведения лабораторной работы
Работа проводится в режиме диалога. После запуска программы COMMYстудент вводит номер варианта задания исходных данных, и затем его задача сводится к ответам на следующие вопросы:
1. К разбиению какого подмножества следует перейти на очередном ваге?
2. По какому пути осуществлять разбиение?
3. Какой путь следует исключить во избежание преждевременного замыкания маршрута?
4. Чему равны оценки снизу стоимости маршрутов, входящих в подмножества, получающиеся после разбиения?
5. Следует ли сменить "рекорд"?
6. Получено ли оптимальное решение?
Следует отметить, что ради экономии памяти и лабораторной Ра-боте используется специфический метод построения дерева подмножеств. Этот метод позволяет хранить дерево (точнее, его часть, содержащую все маршруты, кроме уже отброшенных и "рекордного") в виде ветви, от которой на каждом уровне влево ответвляется по одному листу. Поясним это утверждение.
На первом этапе, вплоть до получения первого решения (автоматически становящегося "рекордным") дерево строится вниз, причем разбиению подвергаются всякий раз подмножества, включающие выбираемый для разбиения путь. Далее, если существует несколько листьев, для которых оценки меньше "рекорда", то для разбиения выбирается самый низкий, а не тот, для которого оценка минимальная, что было бы эффективнее. Нетрудно показать, что такой способ выбора для разбиения очередного подмножества:
а) обеспечивает просмотр всего множества маршрутов;
б) не выводит в процессе построения дерева за пределы описанной выше структуры.
Отметим, наконец, что на экран дерево выводится в виде двух столбцов чисел.
Числа в левом столбце — это оценки стоимости на подмножест-вах, ответвляющихся от основной ветви, в нижнее число в правом столбце - оценка на подмножестве, которое должно подвергнуться разбиению (если только это число не больше, чем "рекорд").
- 29 -
Требования к отчету
Отчет должен содержать:
а) постановку задачи;
б) полный протокол ее решения, включающий построенное в ходе решения дерево подмножеств;
в) ответы на контрольные вопросы.
Контрольные вопросы
1. В чем заключается содержательный смысл ограничений (6.1) и (6.2)?
2. Почему стоимость любого маршрута не меньше, чем редукционная сумма исходной матрицы стоимостей?
3. Почему после включения очередного пути в маршрут достаточ-но запретить движение лишь по одному пути во избежание внутреннего цикла?
4. Почему "запретный" путь из 2-го вопроса может отличаться от пути, противоположного включенному в маршрут?
б. Какова максимальная длина ветви дерева подмножеств, ведущей к оптимальному решению?
Список литературы
Поляк Б.Т. Введение в оптимизацию.-М.:Наука,1983.
Банди Б. Основы линейного программирования.-М.:.Радио и связь, 1989.
Йенсен П., Барнес Д. Потоковое программирование.-М.:Радио и связь, 1984.
Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.-М.:Мир,1981.
Содержание
Введение.....................................................3
Лабораторная работа 1 ОДНОМЕРНАЯ МИНИМИЗАЦИЯ................3
Лабораторная работа 2 МНОГОМЕРНАЯ МИНИМИЗАЦИЯ...............8
Лабораторная работа 3 СИМПЛЕКСНЫЙ МЕТОД....................10
Лабораторная работа 4 РЕШЕНИЕ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧИ.15
Лабораторная работа 5 ТРАНСПОРТНАЯ ЗАДАЧА..................20
Лабораторная работа 6 ЗАДАЧА О КОММИВОЯЖЕРЕ................25
Список литературы ....................................31
Редактор А.В. Крейцер
Подп. К печ. 27,12,91. Формат 60х84 1/16.
Бумага тип. №2. Офсетная печать.
Усл. Печ. л. 1, 86. Усл. Кр.-отт. 1, 98. Уч.-изд. Л. 2.0.
Тираж 100 экз. План 1991г. Изд. №64. Зак. №49. Бесплатно.
Редакционно-издательский отдел ЛЭТИ им. В. И. Ульянова (Ленина)
Ротапринт ЛЭТИ