![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Суть метода искусственного базисаСодержание книги
Поиск на нашем сайте
В случаях, когда сразу не выделяются базисные переменные (а они сразу выделяются только после приведения к каноническому виду задачи, в которой имеются только неравенства типа «≤» при неотрицательных правых частях) можно применять так называемый метод искусственного базиса, который является по сути разновидностью симплекс-метода. Пусть задача приведена к каноническому виду (1.6), в котором в некоторых уравнениях, скажем в i 1-м, i 2-м, …, is -м, явно не выделяются базисные переменные. Добавим в эти уравнения искусственные переменныеxm +1, xm +2, …, xm + s, а в целевую функцию - слагаемые ± Mxm +1, ± Mxm +2, …, ± Mxm + s, где M >>1 (M - достаточно большое положительное число) причём «±» - это «+», если решается задача на min, и «±» - это «-», если решается задача на max. Получается новая задача, которая называется дополнительной или вспомогательной. Например, вспомогательная (дополнительная) задача с искусственными переменными для задачи (1.5) будет иметь вид c 1 x 1+ c 2 x 2+…+ cnxn + Mxn + m +1+ Mxn + m +2+…+ Mxn +2 m ®min Аналогично, если задача (2.1) решается на max и придётся вводить искусственные переменные во все ограничения, то получаем следующую вспомогательную задачу: c 1 x 1+ c 2 x 2+…+ cnxn - Mxn +1- Mxn +2-…- Mxn + m ®max
5.1.1. Если ( Отсюда получаем, что для решения задачи линейного программирования, методом искусственного базиса достаточно: 1. Привести задачу к каноническому виду. 2. Если в задаче в каноническом виде нет базиса из единичных векторов, то составить вспомогательную задачу (если в задаче в каноническом виде имеется базис из единичных векторов, то задача решается обычным симплекс-методом). 3. Решить вспомогательную задачу, и если (
При этом к вспомогательной задаче применяется обычный симплекс-метод с некоторыми своими особенностями: 1. Так как целевая функция вспомогательной задачи имеет слагаемые с коэффициентами ± M, то оценки D k имеют вид 2. Искусственные переменные по мере их выведения из базиса исключаются из дальнейшего рассмотрения. 3. После того, как все искусственные переменные будут выведены из базиса, коэффициенты D k при M будут равны нулю, в таблице остаётся только строка Пример. Решить пример из предыдущего параграфа методом искусственного базиса. Решение. Напоминаем задачу: -3 x 1+ x 2+2 x 3 ® max(min) 1. Приведём задачу к каноническому виду: -3 x 1+ x 2+2 x 3 ® max(min) 2. В базис в виде единичного вектора входит только вектор при x 4, то есть переменная во втором уравнении. В первое и третье уравнения системы ограничений вводим искусственные переменные x 6 и x 7: В целевую функцию они войдут с коэффициентами M или - M в зависимости от того, решается задача на min или на max. Решим задачу на максимум. Тогда вспомогательная задача - следующая: -3 x 1+ x 2+2 x 3- Mx 6- Mx 7 ® max 3. Решаем полученную вспомогательную задачу с применением симплекс-таблиц:
Здесь D2=-2 M -1, D3=-3 M -2. Коэффициенты при M записаны в строке
Так как D k <0 только для одного значения k =1, а именно, D1=-2 M +2<0 (напоминаем, что M - достаточно большое число, так что -2 M <2 и D1<0), то ищем только отношения q 1. Минимум этих отношений достигается в строке x 7: min Искусственные переменные теперь исключены из базиса. Поэтому дальше работаем с обычной симплекс-таблицей, в которой новая третья строка (соответствующая переменной x 1) получается делением старой третьей строки на 2. Затем эту новую третью прибавляем к старой первой и вычитаем из старой второй. В результате в новой таблице в столбце x 1 появятся соответственно 0, 0 и 1:
В полученной таблице D k ³0 для всех k =1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X 0=(2; 4; 0) является оптимальным решением, при котором значение целевой функции равно -2 (x 4 в окончательном ответе не учитывается, так как она является дополнительной переменной, и не входит в первоначальную задачу). Решим задачу на минимум (min). Тогда вспомогательная задача - следующая: -3 x 1+ x 2+2 x 3- Mx 6- Mx 7 ® max Как и выше, решаем полученную вспомогательную задачу с применением симплекс-таблицы:
Критерий оптимальности нарушается для переменных x 2 и x 3: D2=2 M -1>0, D3=3 M -2>0. Так как - q 2D2=-4 M +2 по абсолютной величине превосходит - q 3D3=-3 M +2, то в базис включаем x 2. При этом min
Теперь D1>0. Поэтому переход к новой таблице аналогичен соответствующему переходу при решении задачи на max: в базис вводится x 1 вместо x 7:
Имеем D3=1>0 и D5=1>0. Так как |- q 5D5|=|- q 3D3|, то вводим в базис x 5 (вместо x 4): сначала умножаем 2-ю строку на 2, а затем новую вторую строку, умноженную на ½, прибавляем к первой и третьей (фактически вторую старую прибавляем к первой и третьей):
В полученной таблице D k £0 для всех k =1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X 0=(4; 6; 0) является оптимальным решением, при котором значение целевой функции равно -6. Ответ: F min=-6, минимум достигается в точке X 2=(4; 6; 0); F max=-2, максимум достигается в точке X 1=(2; 4; 0). 5.2. Упражнение. Решить соответствующие задачи линейного программирования из Упражнения 1.3 методом искусственного базиса.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-08; просмотров: 538; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.222.13.30 (0.009 с.) |