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






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

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

Является ли полученное решение эффективным решением? Почему?



Решение — эффективное решение (по построению), его нельзя улучшить по одному критерию, не ухудшив по другому.
Множество Парето — это отрезок [B,C] на прямой .

(см. рис. 3).
(см. рис. 4).
(см. рис. 5).
Чем отличается полученное решение от прочих решений из множества Парето?

— это компромиссное решение, которое удовлетворяет всем вышеописанным свойствам. Для него взвешенные относительные потери (весовые коэффициенты ) равны между собой и минимальны:

, .

Таким образом, .

При этом, так как , а , то именно в таком соотношении делится угол между осями на рис. 5, а — это пересечение отрезка, соответствующего множеству эффективных нормализованных оценок, и отрезка, делящего угол в оговоренном соотношении 1:2.


  1. ^ РЕШЕНИЕ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ




    1. Графическое решение задачи целочисленного программирования (ЦЛП).


На исходную задачу ЛП накладывается дополнительное ограничение целочисленности переменных:



Решим эту задачу графически.




Рис. 6. Графическое решение задачи ЦЛП.



Ответ: , .





    1. Решение задачи ЦЛП методом ветвей и границ.




Решим задачу ЦЛП методом ветвей и границ.
Начальный шаг решения задачи состоит в нахождении решения задачи ЛП, получаемой при отбрасывании условия целочисленности и , обозначим ее через ЛП-0. Это задача была решена в п. 1.2: , .

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

Рассмотрим, например, координату . Следующий шаг метода ветвей и границ состоит в просмотре целочисленных значений , больших или меньших 12.82. Это делается путем добавления к задаче ЛП-0 либо ограничения , либо . Таким образом, из задачи ЛП-0 получаются две новые задачи (ЛП(1) и ЛП(2)):

ЛП(1)

ЛП(2)
















Рис. 7.1. Решение задачи ЛП(1).



Рис. 7.2. Решение задачи ЛП(2).


Из рис. 7 следует, что в задаче ЛП(2)система ограничений несовместна, а решением задачи ЛП(1) является точка — целочисленное решение, нижняя оценка оптимального значения целевой функции исходной задачи ЦЛП.
Построим дерево решений:


ЛП(0)











ЛП(1)


ЛП(2)

,



Ø


Рис. 8. Дерево решений для задачи ЦЛП (метод ветвей и границ).
Таким образом, решение задачи ЛП(1) — это решение исходной задачи ЦЛП.
Ответ: , .
Ответы на теоретические вопросы по пункту 3.2:

Чем отличается метод ветвей и границ от метода простого перебора?

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


    1. ^ Решение задачи коммивояжера методом ветвей и границ и с помощью программной системы Excel.



а) Решение задачи коммивояжера методом ветвей и границ.
таблица 9 таблица 10




1

2

3

4

5










1

2

3

4

5




1



8

13

18

10

8




1



0 5

5

11

5




2

15



13

18

10

10




2

5



3

8

0

0

3

12

12



18

13

12




3

0 0

0 0



6

1

0

4

19

14

10



17

10




4

9

4

0 4



7

0

5

5

5

5

5



5




5

0 0

0 0

0 0

0 6



0



















45







0

0

0

0

0

45




Таблица 11




1

2

3

5































1



0

5

5

0




























2

5



9

0

0




























3

9

0



1

0




























4

9

4

0



0































9

0

0

0

54




























Из текущего шага видно, что оценка r(5,4)>45, тогда рассмотрим (1,2),т.к. быть может r(1,2)=45

Таблица 12 таблица 13




1

2

3

4

5










1

3

4

5







1



0 5

5

11

5

0




2



3

8

0 4

0




2

5



3

8

0

0




3

11



6

1

0




3

0 0

0 0



6

1

0




4

9

0 7



7

0




4

9

4

0 4



7

0




5

0 0

0 0

0 6



0




5

0 0

0 0

0 0

0 6



0







0

0

0

0

45







0

0

0

0

0

45

























Таблица 14 таблица 15




1

4

5



















1

4










2



8

0 9

0













3

0



0







3

0 1



1

0













5

0 0

0

0







5

0 0

0 8



0
















0

0

45










0

0

0

45
































Таким образом, записываем по последней матрице маршрут: 2-5-4-3-1-2.



































































































Рис. 9. Дерево решений для задачи коммивояжера (метод ветвей и границ).
б) Решение задачи коммивояжера с помощью Excel.
1   2   3   4   5   6   7

Похожие:

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

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

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

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

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

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

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

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

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

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



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


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

Поиск