Категория
Информатика
Тип
реферат
Страницы
8 стр.
Дата
26.04.2014
Формат файла
.html — Html-документ
Архив
1023981.zip — 5.89 kb
  • osnovnye-principy-reshenija-transportnoj-zadachi_1023981_1.html — 20.11 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы


/>Реферат

В данной работе изложены основныепринципы решения транспортной задачи, в частности ¾ задача о коммивояжере.

В работе использовано 5 источников,она содержит 29 страниц, 2 приложения, программу, написанную на языке Си.



/>Содержание

Реферат

Содержание

Введение

1.Постановка задачи окоммивояжере

2. Метод ветвей и границ

3. Использование верхних оценок

4. Решение с заданной точностью

Заключение

Список используемой литературы

Приложение 1

Приложение 2



Введение

Проблема оптимизации является вопределенном смысле, пожалуй, самой острой проблемой современности. В любойсфере деятельности человек всегда ищет оптимальное решение.

Существует класс задач, которые неудовлетворяют принципу оптимальности, и, следовательно, для этих задач методдинамического программирования непосредственно использован быть не может. Ихрешение требует развития специальных способов последовательного анализавариантов. В частности, к такому классу задач относится задача о коммивояжере(бродячем торговце).

Данная работа описывает нахождениеоптимального решения задачи о коммивояжере, применяя метод ветвей и границ.


1.Постановказадачи о коммивояжере

Рассмотрим задачу о коммивояжере(бродячем торговце). Предположим, что бродячий торговец должен, покинув город,которому мы присвоим номер 1 (рис. 1), объехать еще N-1 городов и вернуться снова в город номер 1. В егораспоряжении есть дороги, соединяющие эти города. Он должен выбрать своймаршрут — порядок посещения городов так, чтобы путь, который ему придетсяпройти, был как можно короче. Основное условие этой задачи состоит в том, чтокоммивояжер не имеет права возвращаться снова в тот город, в котором он однаждыуже побывал. Это условие будем называть условием (a). Мы считаем, что расстояние междудвумя



Ваше мнение



CAPTCHA