Федеральное агентство по образованию государственное образовательное учреждение
Скачать 402.34 Kb.
|
| ^ Решение  — эффективное решение (по построению), его нельзя улучшить по одному критерию, не ухудшив по другому.Множество Парето — это отрезок [B,C] на прямой  .   (см. рис. 3).  (см. рис. 4).  (см. рис. 5). Чем отличается полученное решение от прочих решений из множества Парето?  — это компромиссное решение, которое удовлетворяет всем вышеописанным свойствам. Для него взвешенные относительные потери (весовые коэффициенты  ) равны между собой и минимальны: ,  .Таким образом,  .При этом, так как  , а  , то именно в таком соотношении делится угол между осями на рис. 5, а  — это пересечение отрезка, соответствующего множеству эффективных нормализованных оценок, и отрезка, делящего угол в оговоренном соотношении 1:2.
На исходную задачу ЛП накладывается дополнительное ограничение целочисленности переменных:  Решим эту задачу графически.
Ответ:  ,  .
Решим задачу ЦЛП методом ветвей и границ. Начальный шаг решения задачи состоит в нахождении решения задачи ЛП, получаемой при отбрасывании условия целочисленности  и  , обозначим ее через ЛП-0. Это задача была решена в п. 1.2:  ,  .Поскольку и , и принимают дробные значения, найденное решение не может быть оптимальным решением исходной задачи ЦЛП. Но найденное значение  представляет собой верхнюю границу истинного оптимального целочисленного значения, поскольку при выполнении требования целочисленности и значение целевой функции может лишь уменьшиться.Рассмотрим, например, координату  . Следующий шаг метода ветвей и границ состоит в просмотре целочисленных значений , больших или меньших 12.82. Это делается путем добавления к задаче ЛП-0 либо ограничения  , либо  . Таким образом, из задачи ЛП-0 получаются две новые задачи (ЛП(1) и ЛП(2)):
Из рис. 7 следует, что в задаче ЛП(2)система ограничений несовместна, а решением задачи ЛП(1) является точка  — целочисленное решение,  — нижняя оценка оптимального значения целевой функции исходной задачи ЦЛП.Построим дерево решений:
Рис. 8. Дерево решений для задачи ЦЛП (метод ветвей и границ). Таким образом, решение задачи ЛП(1) — это решение исходной задачи ЦЛП. Ответ:  ,  .Ответы на теоретические вопросы по пункту 3.2: Чем отличается метод ветвей и границ от метода простого перебора? Метод ветвей и границ представляет собой более эффективную процедуру перебора целочисленых допустимых решений, основанную на рассмотрении, в первую очередь, точек, полученных в результате округления нецелочисленного оптимального решения соответствующей задачи ЛП. Разбиения на каждом этапе множества допустимых решений на два подмножества и наличие условия останова позволяют в большинстве случаев избежать полного перебора.
 а) Решение задачи коммивояжера методом ветвей и границ. таблица 9 таблица 10
Таким образом, записываем по последней матрице маршрут: 2-5-4-3-1-2.
  
 Рис. 9. Дерево решений для задачи коммивояжера (метод ветвей и границ). б) Решение задачи коммивояжера с помощью Excel. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
,
Ø
Похожие:
 | Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский государственный... | | Государственное образовательное учреждение высшего профессионального образования |
 | Федеральное государственное бюджетно-образовательное учреждение высшего профессионального образования | | Федеральное государственное бюджетно-образовательное учреждение высшего профессионального образования |
| Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования | | Государственное образовательное учреждение высшего профессионального образования российский государственный торгово-экономический... |
| ТБ, хб, тс, тп, ос, бос, бп, пб, тк, ма, мк, мп, гт, ст, мт, бст, бмт, тэ, бтэ, гг, гр, гб, бгб, мз, бмз | | ТБ, хб, тс, тп, ос, бос, бп, пб, тк, ма, мк, мп, гт, ст, мт, бст, бмт, тэ, бтэ, гг, гр, гб, бгб, аэ, баэ, ат, аг, баг |
| ТБ, хб, тс, тп, ос, бос, бп, пб, тк, ма, мк, мп, гт, ст, мт, бст, бмт, тэ, бтэ, гг, гр, гб, бгб, аэ, баэ, ат, аг, баг | | МА, мз, мк, мп, мс, пб, бмз, бп, ос, тб, тк, тп, тс, бтб, бтп, бтс, гб, гг, гр, бгб, гт, мт, ст, тэ, бмт, аг, ат, аэ, баг, баэ |
