Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Метод искусственных переменных
Задачи ЛП с использованием СМ легко решаются лишь при ограничениях типа ≤. При ограничениях-равенствах или ограничениях типа ≥, когда имеют дело с остаточными пере- менными, возникают трудности, связанные с получением на- чального допустимого базисного решения. Для получения этого решения используются искусствен- ные переменные, которые включаются в левые части уравне- ний, не содержащих очевидных базисных решений. Обеспечивая получение НДБР, эти переменные играют роль остаточных переменных, но, не имея физического смыс- ла, в процессе оптимизации они должны оказаться равными нулю. С применением искусственных переменных связаны два основных метода: метод больших штрафов (М-метод) и двух- этапный метод. Метод больших штрафов. В этом методе в задачу ЛП вводится обратная связь, которая обеспечивает получение оптимального решения при нулевых искусственных перемен- ных. В качестве такой обратной связи используется штраф, накладываемый на ЦФ за использование искусственных пе- ременных. Пример 9.6. Рассмотрим задачу ЛП примера 9.1, введя в условия дополнительное ограничение: определить max W(x) = x1 + 4x2 при ограничениях: x1 + x2 ≤ 4 -x1 + x2 ≤ 2 x1 + 3x2 ≥ 3 x1, x2 ≥ 0. После приведения задачи ЛП к стандартному виду, по- лучим: найти max W(x) = x1 + 4x2 + 0s1 + 0s2 + 0s3 при ограничениях: x1 + x2+ s1 = 4; - x1 + x2 + s2 = 2; x1 + 3x2 − s3 = 3; x1, x2 ≥ 0, s1, s2, s3 ≥ 0. При обычном подходе для получения начального допус- тимого базисного решения необходимо приравнять нулю не- базисные переменные x1, x2, а базисные переменные s1, s2, s3 приравнять правым частям уравнений. Однако в этом слу- чае переменная s3 имеет отрицательное значение, что про- тиворечит условию неотрицательности всех переменных задачи ЛП. Введем в третье уравнение искусственную пе- ременную R1, которая будет играть роль остаточной пере- менной. За использование этой переменной в ЦФ вводится штраф — достаточно большой отрицательный коэффициент М. В задачах минимизации ЦФ этот коэффициент является положительным. В результате задача ЛП приводится к сле- дующему виду: найти max W(x) = x1 + 4x2 + 0s1 + 0s2 + 0s3 − MR1 при ограничениях: x1 + x2+ s1 = 4;
- x1 + x2 + s2 = 2; x1 + 3x2 − s3 + R1 = 3; x1, x2 ≥ 0, s1, s2, s3, R1 ≥ 0. Cистема линейных равенств содержит m = 3 уравнения и n = 6 переменных, поэтому начальное базисное решение долж- но содержать n − m = 3 нулевых переменных и 3 базисных пере- менных. Если положить равными нулю свободные переменные x1, x2, s3, то сразу будет получено требуемое начальное базисное решение: s1 = 4, s2 = 2, R1 = 3. После этого условия задачи переформулируются таким образом, чтобы процесс решения можно было представить в удобной табличной форме (табл. 9.3). Таблица 9.3
Для этого необходимо, чтобы начальное решение в явном виде присутствовало в столбце, характеризующем правые час- ти всех уравнений задачи. С этой целью в уравнение ЦФ под- ставляется выражение для искусственной переменной, полу- ченное из соответствующего ограничения: R1 = 3 − x1 − 3x2 + s3. В результате получается следующее выражение для ЦФ: W(x) = x1 + 4x2 − М(3 − x1 − 3x2 + s3). После приведения подобных членов Z-уравнение в симп- лекс-таблице будет иметь вид: W(x) − (1 + М)x1 − (4 + 3М)x2 + + Мs3 = − 3M. Последовательность решения задачи представлена в табл. 9.3. Оптимальному решению соответствует точка x1 = 1, x2 = 3, где ЦФ W(x) = 13. Так как в решении отсутствует искусствен- ная переменная, то оно является допустимым оптимальным ре- шением задачи. Двухэтапный метод. Недостаток М-метода обусловлен большой величиной штрафа М, что зачастую приводит к ошиб- кам в вычислениях из-за процедуры округления чисел. В двух- этапном методе штраф не используется, поэтому он лишен такого недостатка. Процедура поиска оптимального решения здесь организована как бы в два этапа (отсюда и название этого метода).
На первом этапе вводятся искусственные переменные, необходимые для получения стартовой точки; формируется фиктивная ЦФ ϕ как сумма искусственных переменных, вы- раженных из соответствующих ограничений. Решается задача минимизации функции ϕ. Если минимальное значение функции ϕ равно нулю, то исходная задача имеет допустимое решение, в противном случае задача решения не имеет. Основная цель пер- вого этапа — получение начального решения исходной задачи. На втором этапе решается исходная задача, при этом в качестве начального решения используется оптимальное ре- шение, полученное на первом этапе. В симплекс-таблице для двухэтапного метода вводится еще одна строка для фиктивной ЦФ ϕ. На первом этапе усло- вие оптимальности проверяется только по элементам ϕ-строки, а с элементами Z-строки выполняются обычные для симплекс- метода процедуры расчетов. С достижением нулевого значения функции ϕ-строка, соответствующая этой функции, из симп- лекс-таблицы исключается и дальнейшие итерации, составля- ющие второй этап, осуществляются с использованием элемен- тов Z-строки. Пример 9.7. Рассмотрим задачу примера 9.6. После приве- дения исходной задачи ЛП к стандартному виду и введения ис- кусственной переменной формируется фиктивная ЦФ: ϕ = R1 = 3 − x1 − 3x2 + s3. Для включения в симплекс-таблицу функция приводится к виду: ϕ + x1 + 3x2 − s3 = 3. Решение задачи симплекс-методом представлено в табл. 9.4. Таблица 9.4
Опти- мум) |
Z | 0 | 0 | 5/2 | 1/2 | 0 | 0 | 13 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x1 | 1 | 0 | 1/2 | -1/2 | 0 | 0 | 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
s3 | 0 | 0 | 1 | 0 | 1 | -1 | 7 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x2 | 0 | 1 | 1/2 | 1/2 | 0 | 0 | 3 |
Количество необходимых итераций М-метода и двухэтап- ного метода всегда одинаково. Преимуществом двухэтапного метода является то, что при его применении не требуется ис- пользование в расчетах постоянной М.
| Поделиться: |
Читайте также:
Последнее изменение этой страницы: 2021-01-14; просмотров: 111; Нарушение авторского права страницы; Мы поможем в написании вашей работы!
infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.135.186.12 (0.01 с.)