Федеральное агентство по образованию государственное образовательное учреждение






Скачать 402.34 Kb.
НазваниеФедеральное агентство по образованию государственное образовательное учреждение
страница7/7
Дата публикации15.12.2013
Размер402.34 Kb.
ТипДокументы
top-bal.ru > Экономика > Документы
1   2   3   4   5   6   7

Чтобы избавиться от неполных замкнутых циклов, в задаче введено 10 дополнительных ограничений вида и т. д. все возможные переборы. Эти ограничения исключают возможность построения частичных циклов из 2-х городов. Если при решении будет построен цикл из 3-х городов, то с оставшимися 2-мя городами нельзя будет сделать ничего иного, кроме как тоже связать их в цикл, а, следовательно, 10 введенных ограничений избавляют нас и от циклов из 3-х городов. Цикл «из одного города» заведомо исключен, так как на диагонали матрицы издержек стоят бесконечности, а это значит, что и цикл из 4-х городов не может быть построен. А цикл из 5-ти городов — это то, что мы ищем в задаче.


таблица 16

Ограничения на замкнутость цикла

1










1

0







0

0

1




0

1

0

1

таблица 17




Матрица затрат С













10000

8

13

19

13










15

10000

13

18

10










12

12

10000

18

13










19

14

10

10000

17










5

5

5

5

10000











таблица 18




Матрица ответов X




1

2

3

4

5







1

0

1

0

0

0

1




2

0

0

0

0

1

1




3

1

0

0

0

0

1




4

0

0

1

0

0

1




5

0

0

0

1

0

1







1

1

1

1

1












таблица 19







C*X













Сумма по строкам




s

8

0

0

0

8







0

0

0

0

10

10







12

0

0

0

0

12







0

0

10

0

0

10







0

0

0

5

0

5
















Целевая ячейка:

45

































таблица 20




Ответ:






















*

1--2

*

*

*










*

*

*

*

2--5










3--1

*

*

*

*










*

*

4--3

*

*










*

*

*

5--4

*








^

Ответ:

, то есть маршрут 2-5-4-3-1-2.


Суммарные затраты = 45
^

Ответы на теоретические вопросы по пункту3.3:


Как записывается в общем виде модель задачи коммивояжера? Чем эта модель отличается от модели задачи о назначении? Как представить ответ задачи в матричном виде?
^ Постановка задачи:

Имеется n городов. Затраты (стоимостные, временные, расстояния) на переезд между i-ым и j-ым городом заданы в виде матрицы сij, , . Коммивояжер, выехав из исходного города должен объехать все города, посетив каждый однажды, и вернуться в исходный. Определить в каком порядке нужно объезжать города, чтобы суммарные затраты были минимальными.
Модель:

Пусть


Различия задачи коммивояжера и задачи о назначении:

^

Задача коммивояжера


Задача о назначении

,

но



Существует ограничение

на полный замкнутый цикл

Подобных ограничений нет.


Результат решения задачи может быть представлен в виде матрицы вида:
^

, то есть маршрут 2-5-4-3-1-2.



Эта модель не учитывает условие, не допускающее появление неполных замкнутых циклов. Чтобы избавиться от неполных замкнутых циклов, необходимо вводить дополнительные ограничения вида и т. д.
ЗАКЛЮЧЕНИЕ
При выполнении расчетно-графического задания были получены навыки в решения разнообразных типов оптимизационных задач различными методами, в том числе с использованием программных систем Mathcad и Excel.

Была возможность сравнения методов решения некоторых задач, что даёт делать вывод об эффективности их использования в различных случаях. Например, иногда нагляднее и быстрее использовать графический метод при решении оптимизационных задач. Но с точки зрения программирования алгоритмов, удобнее всего использовать симплекс-метод.

Также проводилось исследование задачи ЛП в рамках экономической интерпретации задачи, что позволяло наглядно сопоставить абстрактные математические понятия (формулы, термины) с реальными задачами экономического характера.

Ручной счёт некоторых алгоритмов (симплекс-метод, метод ветвей и границ) позволял оценить примерную их трудоёмкость, и то, как она может изменяться в зависимости от начальных условий задачи, например, количества ограничений, переменных.
^ СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


  1. Вентцель Е. С. Исследование операций. Задачи, принципы, методология. — М.: Высш. шк, 2001. — 208 с.

  2. Зайченко Ю. П. Исследование операций. — Киев: Выща школа, 1975. — 320 c.

  3. Исследование операций и методы оптимизации: Метод. указания к выполнению первого домашнего индивидуального задания / Составитель О.В. Казанская; Новосиб. электротехн. ин-т. — Новосибирск, 1990. — 31 c.

  4. Реклейтис Т. и др. Оптимизация в технике: В 2-х кн. — M.: Мир, 1986.

1 Все расчеты и операции над матрицами выполнены в этом пункте при помощи пакета Mathсad.

1   2   3   4   5   6   7

Похожие:

Федеральное агентство по образованию государственное образовательное учреждение iconРоссийской федерации федеральное агентство по образованию
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский государственный...

Федеральное агентство по образованию государственное образовательное учреждение iconФедеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования

Федеральное агентство по образованию государственное образовательное учреждение iconМинистерство образования и наукироссийской федерации федеральное агентство по образованию
Федеральное государственное бюджетно-образовательное учреждение высшего профессионального образования

Федеральное агентство по образованию государственное образовательное учреждение iconМинистерство образования и наукироссийской федерации федеральное агентство по образованию
Федеральное государственное бюджетно-образовательное учреждение высшего профессионального образования

Федеральное агентство по образованию государственное образовательное учреждение iconМинистерство образования и науки российской федерации федеральное агентство по образованию
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Федеральное агентство по образованию государственное образовательное учреждение iconФедеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования российский государственный торгово-экономический...

Федеральное агентство по образованию государственное образовательное учреждение iconРоссийской Федерации Федеральное агентство по образованию Государственное...
ТБ, хб, тс, тп, ос, бос, бп, пб, тк, ма, мк, мп, гт, ст, мт, бст, бмт, тэ, бтэ, гг, гр, гб, бгб, мз, бмз

Федеральное агентство по образованию государственное образовательное учреждение iconРоссийской Федерации Федеральное агентство по образованию Государственное...
ТБ, хб, тс, тп, ос, бос, бп, пб, тк, ма, мк, мп, гт, ст, мт, бст, бмт, тэ, бтэ, гг, гр, гб, бгб, аэ, баэ, ат, аг, баг

Федеральное агентство по образованию государственное образовательное учреждение iconРоссийской Федерации Федеральное агентство по образованию Государственное...
ТБ, хб, тс, тп, ос, бос, бп, пб, тк, ма, мк, мп, гт, ст, мт, бст, бмт, тэ, бтэ, гг, гр, гб, бгб, аэ, баэ, ат, аг, баг

Федеральное агентство по образованию государственное образовательное учреждение iconРоссийской Федерации Федеральное агентство по образованию Государственное...
МА, мз, мк, мп, мс, пб, бмз, бп, ос, тб, тк, тп, тс, бтб, бтп, бтс, гб, гг, гр, бгб, гт, мт, ст, тэ, бмт, аг, ат, аэ, баг, баэ



Школьные материалы


При копировании материала укажите ссылку © 2018
контакты
top-bal.ru

Поиск