Формализация решения задачи векторным методом
Как отмечали, критерий выбора решения на каждом этапе определяется двумя параметрами – длиной вектора решения и величиной угла вектора решения с идеальным вектором (n=0). Соответственно свести задачу к однокритериальной, можно рассматривая длину проекции вектора решения на идеальный |xno| = xn cosano
Если обозначить через xn1 = 1,n параметры n-ого варианта, то длина вектора равна: xn = m [∑x2ni] 1/2 i=1 Ортонормируем систему следующим образом. Примем xni= xni / xoi, i=1,n
m Получим длину проекции в ортонормированном базисе. xno =(1/√m) ∑ xni i=1
Замечание. Длина вектора и угол между векторами определяются по следующим формулам:
Данное выражение после соответствующих подстановок, в предположении, что нормированное значение идеального вектора равно 1:
Так как значение m фиксировано для всех вариантов решения, это значение можно опустить, таким образом, в качестве критерия выбора оптимального вектора, на каждом шаге, можно рассматривать параметр, определяемый следующим выражением:
m xno = ∑ xni i=1 (6) xni = xni / xoi
Видим, что эти формулы просты, что позволяет эффективно использовать данный метод решения задачи ЛП с использованием вычислительных средств. Таким образом, методика выбора оптимального решения сводится к следующему:
m xno = ∑ xni → max i=1
Пример: вернемся к задаче раскроя материала, рассмотренной ранее.
Для иллюстрации выполним несколько шагов решения задачи. Шаг 1. Считаем значения критерия для различных вариантов. Сравниваем – выбираем лучший вариант – это вариант1 (присваиваем х1 = 1). Формируем новые ограничения: . Задача не решена, следовательно, требуется следующий шаг решения (не все ограничения нулевые). Следующий шаг отличается от предыдущего тем, что в аддитивном критерии изменяется. Шаг 22. Рассчитываем значение критерия . И так далее (выбираем лучшее значение по данному критерию, фиксируем отложенный х, пересчитываем ограничения, проверяем, решена ли задача полностью или требуется следующий шаг решения). И т.д.
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (496)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |