![]()
Заглавная страница
Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь ![]() Мы поможем в написании ваших работ! КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Мы поможем в написании ваших работ! ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Суть метода искусственного базиса
В случаях, когда сразу не выделяются базисные переменные (а они сразу выделяются только после приведения к каноническому виду задачи, в которой имеются только неравенства типа «≤» при неотрицательных правых частях) можно применять так называемый метод искусственного базиса, который является по сути разновидностью симплекс-метода. Пусть задача приведена к каноническому виду (1.6), в котором в некоторых уравнениях, скажем в i1-м, i2-м, …, is-м, явно не выделяются базисные переменные. Добавим в эти уравнения искусственные переменныеxm+1, xm+2, …, xm+s, а в целевую функцию - слагаемые ±Mxm+1, ±Mxm+2, …, ±Mxm+s, где M>>1 (M - достаточно большое положительное число) причём «±» - это «+», если решается задача на min, и «±» - это «-», если решается задача на max. Получается новая задача, которая называется дополнительной или вспомогательной. Например, вспомогательная (дополнительная) задача с искусственными переменными для задачи (1.5) будет иметь вид c1x1+c2x2+…+cnxn+Mxn+m+1+Mxn+m+2+…+Mxn+2m®min Аналогично, если задача (2.1) решается на max и придётся вводить искусственные переменные во все ограничения, то получаем следующую вспомогательную задачу: c1x1+c2x2+…+cnxn-Mxn+1-Mxn +2-…-Mxn+m®max
5.1.1. Если ( Отсюда получаем, что для решения задачи линейного программирования, методом искусственного базиса достаточно: 1. Привести задачу к каноническому виду. 2. Если в задаче в каноническом виде нет базиса из единичных векторов, то составить вспомогательную задачу (если в задаче в каноническом виде имеется базис из единичных векторов, то задача решается обычным симплекс-методом). 3. Решить вспомогательную задачу, и если ( При этом к вспомогательной задаче применяется обычный симплекс-метод с некоторыми своими особенностями: 1. Так как целевая функция вспомогательной задачи имеет слагаемые с коэффициентами ±M, то оценки Dk имеют вид 2. Искусственные переменные по мере их выведения из базиса исключаются из дальнейшего рассмотрения. 3. После того, как все искусственные переменные будут выведены из базиса, коэффициенты Dk при M будут равны нулю, в таблице остаётся только строка Пример. Решить пример из предыдущего параграфа методом искусственного базиса. Решение. Напоминаем задачу: -3x1+x2+2x3 ® max(min) 1. Приведём задачу к каноническому виду: -3x1+x2+2x3 ® max(min) 2. В базис в виде единичного вектора входит только вектор при x4, то есть переменная во втором уравнении. В первое и третье уравнения системы ограничений вводим искусственные переменные x6 и x7: В целевую функцию они войдут с коэффициентами M или -M в зависимости от того, решается задача на min или на max. Решим задачу на максимум. Тогда вспомогательная задача - следующая: -3x1+x2+2x3-Mx6-Mx7 ® max 3. Решаем полученную вспомогательную задачу с применением симплекс-таблиц:
Здесь D2=-2M-1, D3=-3M-2. Коэффициенты при M записаны в строке
Так как Dk<0 только для одного значения k=1, а именно, D1=-2M+2<0 (напоминаем, что M - достаточно большое число, так что -2M<2 и D1<0), то ищем только отношения q1. Минимум этих отношений достигается в строке x7: min Искусственные переменные теперь исключены из базиса. Поэтому дальше работаем с обычной симплекс-таблицей, в которой новая третья строка (соответствующая переменной x1) получается делением старой третьей строки на 2. Затем эту новую третью прибавляем к старой первой и вычитаем из старой второй. В результате в новой таблице в столбце x1 появятся соответственно 0, 0 и 1:
В полученной таблице Dk³0 для всех k=1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X0=(2; 4; 0) является оптимальным решением, при котором значение целевой функции равно -2 (x4 в окончательном ответе не учитывается, так как она является дополнительной переменной, и не входит в первоначальную задачу). Решим задачу на минимум (min). Тогда вспомогательная задача - следующая: -3x1+x2+2x3-Mx6-Mx7 ® max Как и выше, решаем полученную вспомогательную задачу с применением симплекс-таблицы:
Критерий оптимальности нарушается для переменных x2 и x3: D2=2M-1>0, D3=3M-2>0. Так как -q2D2=-4M+2 по абсолютной величине превосходит -q3D3=-3M+2, то в базис включаем x2. При этом min
Теперь D1>0. Поэтому переход к новой таблице аналогичен соответствующему переходу при решении задачи на max: в базис вводится x1 вместо x7:
Имеем D3=1>0 и D5=1>0. Так как |-q5D5|=|-q3D3|, то вводим в базис x5 (вместо x4): сначала умножаем 2-ю строку на 2, а затем новую вторую строку, умноженную на ½, прибавляем к первой и третьей (фактически вторую старую прибавляем к первой и третьей):
В полученной таблице Dk£0 для всех k=1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X0=(4; 6; 0) является оптимальным решением, при котором значение целевой функции равно -6. Ответ: Fmin=-6, минимум достигается в точке X2=(4; 6; 0); Fmax=-2, максимум достигается в точке X1=(2; 4; 0). 5.2. Упражнение. Решить соответствующие задачи линейного программирования из Упражнения 1.3 методом искусственного базиса.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-08; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.230.173.111 (0.009 с.) |