![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Метод Баранкина и Дорфмана для задачи квадратичного программированияСодержание книги
Поиск на нашем сайте
Рассматривается задача квадратичного программирования вида:
в которой
и
где
Условие (3) может выполняться только для допустимого базисного решения системы (2), то есть для решения, в котором самое большее Задача формулируется следующим образом: среди допустимых базисных решений системы (2) найти такое, которое обращает в нуль величину Баранкин и Дорфман начинают с некоторого базисного решения системы (2), необязательно удовлетворяющему условию (3), и с помощью симплексных преобразований сводят к нулю выпуклую функцию
Алгоритм Все переменные систем представим в виде
Каждому такому вектору соответствует вектор
Очевидно, и условия (2) и (3) можно записать в следующем виде
Метод Баранкина и Дорфмана состоит в том, что исходя из некоторого базисного решения системы (4), совершают ряд симплексных преобразований, в результате каждого из которых выпуклая функция Пусть имеется некоторое допустимое базисное решение системы (4). Переменные входящие в базис обозначим
Число таких равенств где Для базисного решения, в котором независимые переменные равны нулю, Если включить в базис, например, переменную Переменную
Положив
а
Так как то можно записать где
Поскольку значение Величины Вычисления. В первую очередь получают некоторое базисное решение, затем дополняют симплексную таблицу строками для небазисных переменных, упорядочивают таблицу, строят дополнительную таблицу (в соответствии с (15)). В дополнительной таблице Если
Для тех
Таблица (15)
В качестве заменяющего столбца выбираем столбец с минимальным по модулю отрицательным значением Примечание: Если все
Если заменяющий столбец определен, дополнительная таблица больше не нужна. Преобразования таблицы производятся по следующим правилам. Пусть опорный элемент 1. Наверху 2. Делим 3. Для того, чтобы получить остальные столбцы новой таблицы необходимо из соответствующих столбцов старой таблицы вычесть новый
Пример 1. Решить задачу квадратичного программирования вида:
где Решение. Расширенная матрица, определяющая линейную систему
Найдем базисное решение (опорный план), с которого продолжим решение методом Баранкина и Дорфмана. Воспользуемся для этого методом последовательного улучшения плана. Исходная таблица
Исключаем 0-строки.
Найден опорный план. Составляем расширенную таблицу для метода Баранкина-Дорфмана. Исходная таблица метода Баранкина-Дорфмана
При построении дополнительной таблицы вычисляем
Следующая таблица должна быть оптимальной, так как
Оптимальный план задачи:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-09-05; просмотров: 393; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.12.151.240 (0.01 с.) |