- •Задача планирования производства
- •Задача о смесях
- •Задача о распределении производства
- •Задача о раскрое
- •2. Определение интенсивности использования рациональных способов раскроя.
- •Симплекс-метод решения задач линейного программирования
- •Реализация симплекс-метода на компьютере
- •Решение задачи на компьютере.
- •Взаимно двойственные задачи линейного программирования Алгоритм построения взаимно-двойственных задач
- •Решение
- •Экономическая интерпретация взаимно-двойственных задач
- •Действительно, выражение в левой части -го неравенства есть сумма от продажи ресурсов, идущих на изготовление j -го изделия, в правой части – прибыль от продажи единицы j-го изделия:
- •Экономическая интерпретация ограничений двойственной задачи.
- •7.4 Экономическая интерпретация теорем двойственности
- •7.5 Исследование моделей задач лп на чувствительность.
- •Специальные виды задач линейного программирования Транспортная задача
- •Методы решения транспортной задачи.
- •Задача о назначениях
- •0’ Помеченный ноль вычеркнутый ноль
- •Математическая модель задачи.
- •Решение задачи в процедуре excel «Поиск решения»
- •Задача коммивояжера
- •Экономико-математическая модель межотраслевого баланса (модель Леонтьева).
- •1. Задание Исходных данных задачи
- •2. Вычисление матрицы коэффициентов полных материальных затрат b.
- •3. Проверка продуктивности матрицы а.
- •4. Вычисление вектора валового выпуска X.
- •5. Вычисление межотраслевых поставок продукции xij
- •Механизм принятия решений на рынке ценных бумаг
- •Фундаментальный анализ
- •Технический анализ
- •Экспоненциальная скользящая средняя.
- •Управление проектами
- •Задания для самостоятельной работы
Задача коммивояжера
В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.
Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений – задача коммивояжера,
Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения. В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из I в J.
Примером реализации задачи на практике является составление оптимального маршрута человека для доставки продуктов в магазины с оптового склада; доставки бутилированной воды; обновления программных продуктов автоматизированного учета на предприятии; пополнения банкоматов наличными деньгами; сбора сотрудников для доставки вахтовым методом; расклейки афиш; сбора наличных денежных средств их терминалов и др. В этом случае вершинами являются места установки терминалов (банкоматов и т.д.) и «базовый пункт». Стоимостью каждого ребра (отрезка маршрута) является время в пути между двумя точками (вершинами) на маршруте.
Сверлильный станок изготавливает металлические листы с некоторым количеством отверстий. Координаты отверстий известны. Необходимо найти кратчайший путь через все отверстия, а значит, и наименьшее время, затрачиваемое на изготовление одной детали. В данном случае, если такой станок делает миллион деталей в год, то даже миллиметровая выгода может сэкономить приличные средства.
Решение задачи коммивояжера при помощи надстройки MS Excel «Поиск решения»
Мощным средством анализа данных MS Excel является надстройка «Поиск решения». С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки, данные которых, определяют значение целевой ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.
Программа Поиск решений – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации, используется с 1991 года.
Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями: количество неизвестных (decision variable) – 200; количество формульных ограничений (explicit constraint) на неизвестные – 100; количество предельных условий (simple constraint) на неизвестные – 400.
Постановка задачи коммивояжера, которую необходимо решить посредством надстройки «Поиск решения» методом полного перебора следующая:
Требуется побывать в пяти организациях: А, Б, В, Г и Д., начиная с организации А и, вернутся в пункт А. В каком порядке следует обходить организации, чтобы замкнутый тур был кратчайшим? Расстояния между каждой парой организаций заданы следующей матрицей
Решение:
Разместим исходные данные на рабочем
листе (рис 2.1). З
аменим
знак
числом
10000 (на результат решения не влияет)
Рисунок 2.1 Исходные данные задачи
Вводим формулы:
Таблица 1
Ячейка |
Формула |
Примечание |
B9 |
= СУММ(B4:B8) |
Распространяем на диапазон B9:F9 |
G4 |
= СУММ(B4:F4) |
Распространяем на диапазон G4:G8 |
C19 |
=СУММПРОИЗВ(B4:F8;B13:F17) |
Целевая функция |
E19 |
=B4+C5+D6+E7+F8 |
Исключение пути |
B23 |
=$C$10-C10+4*C5 |
Распространяем на диапазон B23:E23 |
B24 |
=$D$10-C10+4*C6 |
Распространяем на диапазон B24:E24 |
B25 |
=$E$10-C10+4*C7 |
Распространяем на диапазон B25:E25 |
B26 |
=$F$10-C10+4*C8 |
Распространяем на диапазон B26:E26 |
Сценарий решения. 1. Запускаем надстройку MS Excel «Поиск решения» командой Сервис/ Поиск решения. И заполняем (рис. 2.2). 2. Для того чтобы выполнялись условия однократного посещения сотрудником организаций и в то же время запланированный Петровым маршрут был пройден полностью, введем ограничения: в строки B9, G4 заводим формулы из таблицы 1 и распространяем их на соответствующие диапазоны B9:F9 и G4:G8. Задаем следующие данные $B$9:$F$9=1 и $G$4:$G$8=1 в Ограничения окна «Поиск решения». Таким образом, мы можем отследить порядок обхода организаций сотрудником, оценить правильность выбора и оптимальность его маршрута. 3. Выбираем ячейку B19 и устанавливаем ее адрес в Целевую ячейку окна «Поиск решения», чтобы определить длину наикратчайшего маршрута. Для этого в ячейку B19 предварительно заносим соответствующую формулу из таблицы 1. Когда программа «Поиск решения» вычислит оптимальный маршрут Петрова и станет известен порядок обхода организаций (из Матрицы переменных) будут известны и расстояния между конкретными парами организаций. Затем при помощи простых математических подсчетов программа рассчитает протяженность оптимального маршрута.
4. Устанавливаем еще одно ограничение в окно «Поиск решения»: $E$19=0. В указанную ячейку вводим формулу из таблицы 1 и исключаем таким образом, заведомо ложный порядок движения Петрова в порядке обхода организаций.
5. В связи с тем, что ячейки диапазона B4:F8 – изменяемые, в Ограничение окна «Поиск решения» необходимо добавить строку B$4$:F$8$=двоичное.
6. Заводим в ячейки B23; B24; B25; B26 соответствующие формулы из таблицы 1 и распространяем их на следующие диапазоны: B23:E23 B24:E24; B25:E25; B26:E26 для учета всех возможных вариантов обхода организаций сотрудником и выбора из них оптимального. Формулы задаем таким образом, чтобы обеспечить исключение ложного пути, соблюдая условие задачи об обходе всех организаций по одному разу.
7. Добавляем в
Ограничения окна «Поиск решения»
$B$23:$E$26 ≤ 3.
Рисунок 2.2 Окно «Поиск решения»
В окне «Параметры поиска решений» отметить Линейная модель и Неотрицательные значения (рис. 2.3)
«OK»
Рисунок 2.3 Окно «Параметры поиска решения»
«Сохранить найденное решение» и ОК.
Найденная минимальная величина находится в целевой ячейке, а в переменных ячейках - оптимальные значения переменных,
В диапазоне B4:F8
отражается порядок перемещений. Если
в ячейке, В стоит единица, значит сотрудник
посетил эту организацию следующей за
А. Если в ячейке ноль – сотрудник
организацию не посещал.
Рисунок 2.4 Результаты решения задачи коммивояжера
